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

ある通販サイトは、各顧客を毎月のはじめに「常連」（状態 $1$）か「離脱しかけ」（状態 $2$）のどちらかに分類している。サイトは次の方策 $\pi$ に固定して運営している。

• 状態 $1$ の顧客には通常対応をする。その月の報酬（利益）は $5$ で、翌月は確率 $\frac{3}{4}$ で状態 $1$、確率 $\frac{1}{4}$ で状態 $2$ になる。
• 状態 $2$ の顧客にはクーポンを送る。その月の報酬は $-1$（クーポンの費用が利益を上回る）で、翌月は確率 $\frac{1}{2}$ で状態 $1$、確率 $\frac{1}{2}$ で状態 $2$ になる。

時刻 $t=0,1,2,\dots$ の状態を $s_t$、その月の報酬を $r(s_t)$ とし、割引率を $\gamma =\frac{4}{5}$ とする。状態 $s$ から始めたときの期待割引総報酬
$$V(s)=E\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)|s_0=s\right]$$
について、$V(1)$ と $V(2)$ をこの順に組 $(V(1),V(2))$ で求めよ。

ある書店は、アプリ会員 1 人の状態を各期のはじめに「よく来店する」（状態 $1$）と「ときどき来店する」（状態 $2$）の 2 つに分けている。書店は方策 $\pi$ として「どちらの状態でも毎期クーポンを配る」ことに決めた。この方策のもとで、その期に得られる利益（即時報酬）$r(s)$ と、次の期の状態への推移確率 $P(s^{\prime }\mid s)$ は次のとおりである。

• 状態 $1$：$r(1)=18$，$P(1\mid 1)=\frac{1}{2}$，$P(2\mid 1)=\frac{1}{2}$
• 状態 $2$：$r(2)=2$，$P(1\mid 2)=\frac{1}{4}$，$P(2\mid 2)=\frac{3}{4}$

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

ある掃除ロボットのバッテリーの状態は、各時刻 $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$）のどちらかである。毎日のはじめに体調を見て行動を $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)$ を求めよ。

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