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

ある工場の機械の状態は、各期のはじめに「良好」「劣化」「故障」のいずれかである。各期のはじめに機械の状態を見て行動を 1 つ選ぶと、その期の利益（負の値は費用）が得られ、次の期のはじめの状態が次の確率で決まる。

• 良好のとき：行動は「運転」だけである。利益 $10$ を得て、次の期は確率 $\frac{7}{10}$ で良好、確率 $\frac{3}{10}$ で劣化になる。
• 劣化のとき：「運転」か「修理」を選ぶ。
• 運転：利益 $6$ を得て、次の期は確率 $\frac{1}{2}$ で劣化、確率 $\frac{1}{2}$ で故障になる。
• 修理：利益 $-2$ を得て、次の期は確率 $1$ で良好になる。
• 故障のとき：行動は「交換」だけである。利益 $-8$ を得て、次の期は確率 $1$ で良好になる。

第 $1$ 期のはじめに機械が良好であるとき、第 $1$ 期から第 $3$ 期までの $3$ 期間の利益の合計の期待値を最大にするように各期の行動を選ぶ。第 $3$ 期の終わりの機械の状態には価値がない（$0$ とする）ものとし、割引は行わない。このとき、利益の合計の期待値の最大値を求めよ。

ある農家の畑の状態は、各期のはじめに「やせ地」（状態 $1$）か「肥沃地」（状態 $2$）のどちらかである。各期のはじめに状態を見て行動を 1 つ選ぶと、その期の報酬が得られ、次の期のはじめの状態が次の確率で決まる。

• 状態 $1$ で行動「耕作」：報酬 $1$、次の状態は確率 $1$ で状態 $1$
• 状態 $1$ で行動「土壌改良」：報酬 $0$、次の状態は確率 $\frac{1}{2}$ で状態 $1$、確率 $\frac{1}{2}$ で状態 $2$
• 状態 $2$ で行動「集約栽培」：報酬 $3$、次の状態は確率 $\frac{3}{4}$ で状態 $2$、確率 $\frac{1}{4}$ で状態 $1$
• 状態 $2$ で行動「休耕併用」：報酬 $2$、次の状態は確率 $1$ で状態 $2$

割引率を $\gamma =\frac{4}{5}$ とし、無限期間にわたる割引総報酬の期待値 $E\left[\sum _{t=0}^{\infty }{\gamma }^t{r}_t\right]$（$r_t$ は第 $t$ 期の報酬）を最大化する。状態 $1$ から始めたときの最適価値 $V^{\ast }(1)$ と、状態 $2$ から始めたときの最適価値 $V^{\ast }(2)$ を、この順に組 $(V^{\ast }(1),V^{\ast }(2))$ で求めよ。

倉庫内を移動する配送ロボットを考える。ロボットの位置は、各時刻に地点 $1$、地点 $2$、出口 $G$ のいずれかであり、出口 $G$ に着いた時点で移動は終了する。地点 $1,2$ では、各時刻に行動を $1$ つ選ぶと、その時刻の費用がかかり、次の時刻の位置が次の確率で決まる。

• 地点 $1$ で行動 $a$：費用 $2$、確率 $1$ で地点 $2$ へ
• 地点 $1$ で行動 $b$：費用 $1$、確率 $\frac{1}{5}$ で出口 $G$ へ、確率 $\frac{3}{5}$ で地点 $1$ にとどまり、確率 $\frac{1}{5}$ で地点 $2$ へ
• 地点 $2$ で行動 $c$：費用 $5$、確率 $1$ で出口 $G$ へ
• 地点 $2$ で行動 $d$：費用 $1$、確率 $\frac{1}{3}$ で出口 $G$ へ、確率 $\frac{2}{3}$ で地点 $1$ へ

遷移はマルコフ性をもち、行動は各時刻の位置を見て選べる。地点 $1$ から出発して出口 $G$ に着くまでにかかる費用の合計（割引なし）の期待値を、行動の選び方（方策）全体にわたって最小化したときの最小値を求めよ。

ある小売店の売り場は、各期のはじめに「通常」（状態 $1$）か「繁盛」（状態 $2$）のどちらかの状態にある。各期のはじめに状態を見て行動を 1 つ選ぶと、その期の報酬が得られ、次の期のはじめの状態が次の確率で決まる。

• 状態 $1$ で行動「通常営業」: 報酬 $4$。次の期は確率 $\frac{4}{5}$ で状態 $1$、確率 $\frac{1}{5}$ で状態 $2$。
• 状態 $1$ で行動「宣伝」: 報酬 $1$。次の期は確率 $1$ で状態 $2$。
• 状態 $2$ で行動「値上げ」: 報酬 $10$。次の期は確率 $1$ で状態 $1$。
• 状態 $2$ で行動「維持」: 報酬 $8$。次の期は確率 $\frac{4}{5}$ で状態 $2$、確率 $\frac{1}{5}$ で状態 $1$。

第 $t$ 期（$t=1,2,\dots$）の報酬を $R_t$ とする。過去の状態と行動の履歴に基づいて行動を選ぶ規則（方策）$\pi$ に対し、長期平均報酬を
$$g^{\pi }=\underset{N\to \infty }{\mathrm{liminf}}\frac{1}{N}{E}^{\pi }\left[\sum _{t=1}^N{R}_t\right]$$
で定める。すべての方策の中での $g^{\pi }$ の最大値を求めよ（この値は第 $1$ 期の状態によらない）。

状態が $1,2$ の 2 つであるマルコフ決定過程を考える。各時刻に、現在の状態で行動を 1 つ選ぶと、即時報酬を受け取り、次の状態へ確率的に遷移する。行動・報酬・遷移確率は次のとおりである。

• 状態 $1$ で行動 $a$：報酬 $1$ を受け取り、確率 $1$ で状態 $1$ にとどまる。
• 状態 $1$ で行動 $b$：報酬 $0$ を受け取り、確率 $1$ で状態 $2$ へ移る。
• 状態 $2$ で行動 $c$：報酬 $4$ を受け取り、確率 $\frac{1}{2}$ で状態 $2$ にとどまり、確率 $\frac{1}{2}$ で状態 $1$ へ移る。
• 状態 $2$ で行動 $d$：報酬 $2$ を受け取り、確率 $1$ で状態 $2$ にとどまる。

割引率を $\gamma =\frac{1}{2}$ とし、無限期間の期待割引総報酬 $E\left[\sum _{t=0}^{\infty }{\gamma }^t{r}_t\right]$（$r_t$ は時刻 $t$ の報酬）を最大化する。状態 $1$ から始めたときの最適価値 $V^{\ast }(1)$ を求めよ。