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

ある小売店の売り場は、各期のはじめに「通常」（状態 $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$ 期の状態によらない）。

ある掃除ロボットのバッテリーの状態は、各時刻 $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))$ で求めよ。

ある工場の機械は、各期のはじめに「良好」（状態 $1$）、「劣化」（状態 $2$）、「故障」（状態 $3$）のいずれかの状態にある。各期のはじめに状態を観測して行動を $1$ つ選ぶ。行動を選ぶと、その期の費用がかかる。次の期のはじめの状態は、現在の状態と選んだ行動だけで、次の確率で決まる。

• 状態 $1$：
• 行動「運転」：費用 $0$。次の状態は確率 $\frac{3}{4}$ で $1$、確率 $\frac{1}{4}$ で $2$。
• 行動「予防点検」：費用 $\frac{3}{2}$。次の状態は確率 $1$ で $1$。
• 状態 $2$：
• 行動「運転」：費用 $2$。次の状態は確率 $\frac{1}{2}$ で $2$、確率 $\frac{1}{2}$ で $3$。
• 行動「修理」：費用 $9$。次の状態は確率 $1$ で $1$。
• 状態 $3$：
• 行動「交換」（これしか選べない）：費用 $10$。次の状態は確率 $1$ で $1$。

第 $t$ 期（$t=0,1,2,\dots$）にかかる費用を $c_t$ とし、割引率を $\beta =\frac{4}{5}$ とする。無限期間の期待割引総費用 $E\left[\sum _{t=0}^{\infty }{\beta }^t{c}_t\right]$ を最小にするように行動を選ぶとき、第 $0$ 期のはじめの状態が $1$ である場合の期待割引総費用の最小値 $V^{\ast }(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)$ を求めよ。

ある人の体調は、毎日のはじめに「元気」（状態 $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)$ を求めよ。