オペレーションズ・リサーチの問題

ある掃除ロボットのバッテリーの状態は、各時刻 $t=0,1,2,\dots$ に「十分」（状態 $1$）か「残りわずか」（状態 $2$）のどちらかである。各時刻に状態を見て行動を $1$ つ選ぶと、その時刻の報酬が得られ、次の時刻の状態が次の確率で決まる。

• 状態 $1$ で行動「通常掃除」：報酬 $4$。次の状態は確率 $\frac{1}{2}$ で状態 $1$、確率 $\frac{1}{2}$ で状態 $2$。
• 状態 $1$ で行動「待機」：報酬 $1$。次の状態は確率 $1$ で状態 $1$。
• 状態 $2$ で行動「充電」：報酬 $0$。次の状態は確率 $1$ で状態 $1$。
• 状態 $2$ で行動「省電力掃除」：報酬 $2$。次の状態は確率 $1$ で状態 $2$。

割引率を $\gamma =\frac{1}{2}$ とし、状態 $s$ から始めたときの期待割引総報酬の最大値（最適価値）を $V^{\ast }(s)$ とする。$V^{\ast }$ はベルマン最適方程式
$$V^{\ast }(s)=\underset{a}{\max }\{r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })\}$$
を満たす。$V^{\ast }(1)$ と $V^{\ast }(2)$ をこの順に組 $(V^{\ast }(1),V^{\ast }(2))$ で求めよ。

$n\ge 2$ を整数とし、頂点集合 $\{1,2,\dots ,n\}$ と有向辺の集合 $\mathcal{A}$ からなる有向グラフ（PERT のアローダイアグラム）を考える。各辺 $(i,j)\in \mathcal{A}$ は $i<j$ を満たし、作業時間 $d_{ij}$（実数）をもつ。また、$j=2,3,\dots ,n$ のどの頂点 $j$ にも、$j$ に入る辺 $(i,j)\in \mathcal{A}$ が少なくとも 1 本あるとする。

最早結合点時刻 $E(1),E(2),\dots ,E(n)$ を
$$E(1)=0,E(j)=\underset{i:(i,j)\in \mathcal{A}}{\max }(E(i)+d_{ij})(j=2,3,\dots ,n)$$
により $j$ の小さい順に定める。また、頂点 $1$ から頂点 $j$ への有向路（辺を 0 本以上つないだもの。$1$ から $1$ へは辺を 1 本も含まない路だけを考える）について、含まれる辺の作業時間の和をその路の長さとよぶ。

各 $j=1,2,\dots ,n$ について、頂点 $1$ から頂点 $j$ への有向路が存在し、$E(j)$ はそれらの有向路の長さの最大値に等しいことを証明せよ。

ある大学生の体調は、毎日のはじめに「元気」（状態 $1$）か「疲労」（状態 $2$）のどちらかである。毎日のはじめに体調を見て行動を $1$ つ選ぶと、その日の報酬が得られ、翌日のはじめの状態が次の確率で決まる。

• 状態 $1$ で行動「長時間アルバイト」：報酬 $6$。翌日は確率 $\frac{1}{2}$ で状態 $1$、確率 $\frac{1}{2}$ で状態 $2$
• 状態 $1$ で行動「短時間アルバイト」：報酬 $4$。翌日は確率 $1$ で状態 $1$
• 状態 $2$ で行動「休養」（状態 $2$ で選べる行動はこれだけ）：報酬 $0$。翌日は確率 $1$ で状態 $1$

割引率を $\gamma =\frac{1}{2}$ とし、無限期間の期待割引総報酬を最大化する。最適価値 $V^{\ast }(s)$ はベルマン最適方程式
$$V^{\ast }(s)=\underset{a}{\max }\left\{r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })\right\}$$
を満たす。最適価値 $V^{\ast }(1)$, $V^{\ast }(2)$ をこの順に組で求めよ。

状態が $1,2,3$ の $3$ つであるマルコフ決定過程を考える。各時刻 $t=0,1,2,\dots$ に現在の状態を見て行動を $1$ つ選ぶと、その時刻の報酬を受け取り、次の時刻の状態が次の確率で決まる（$p_{ij}$ は状態 $i$ から状態 $j$ へ遷移する確率）。

• 状態 $1$ で行動 $a$：報酬 $2$、$(p_{11},p_{12},p_{13})=\left(\frac{1}{2},\frac{1}{2},0\right)$
• 状態 $1$ で行動 $b$：報酬 $0$、$(p_{11},p_{12},p_{13})=(0,0,1)$
• 状態 $2$ で行動 $a$：報酬 $4$、$(p_{21},p_{22},p_{23})=\left(\frac{1}{3},\frac{2}{3},0\right)$
• 状態 $2$ で行動 $b$：報酬 $1$、$(p_{21},p_{22},p_{23})=\left(0,\frac{1}{2},\frac{1}{2}\right)$
• 状態 $3$ で行動 $c$（選べる行動はこれのみ）：報酬 $6$、$(p_{31},p_{32},p_{33})=\left(\frac{1}{2},\frac{1}{4},\frac{1}{4}\right)$

方策 $\pi$ のもとで時刻 $t$ に得る報酬を $R_t$ とし、初期状態 $i$ からの長期平均報酬を
$$g^{\pi }(i)=\underset{N\to \infty }{\lim }\frac{1}{N}{E}^{\pi }\left[\sum _{t=0}^{N-1}{R}_t|X_0=i\right]$$
で定める。この長期平均報酬のすべての方策にわたる最大値（最適平均報酬）を求めよ。なお、状態と行動が有限のこのマルコフ決定過程では、最適な方策が定常な決定的方策（各状態で常に同じ行動を選ぶ方策）の中に存在し、その最適平均報酬は初期状態によらないことを用いてよい。

ある人の体調は、毎日のはじめに「元気」（状態 $1$）か「疲労」（状態 $2$）のどちらかである。毎日のはじめに体調を見て行動を $1$ つ選ぶと、その日の報酬（満足度）が得られ、翌日のはじめの状態が次の確率で決まる。

• 状態 $1$ で行動「働く」：報酬 $4$。翌日は確率 $\frac{1}{2}$ で状態 $1$、確率 $\frac{1}{2}$ で状態 $2$。
• 状態 $1$ で行動「休む」：報酬 $3$。翌日は確率 $1$ で状態 $1$。
• 状態 $2$ で行動「休む」（選べる行動はこれだけ）：報酬 $0$。翌日は確率 $1$ で状態 $1$。

割引率を $\gamma =\frac{1}{2}$ とし、無限に続く期間の期待割引総報酬を最大にする。最適価値 $V^{\ast }(s)$ は
$$V^{\ast }(s)=\underset{a}{\max }\{r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })\}$$
を満たす。状態 $1$ から始めたときの最適価値 $V^{\ast }(1)$ を求めよ。