マルコフ決定過程と方策の価値

ある会員制サービスの会員は、各週のはじめに「利用中」（状態 $1$）か「休眠中」（状態 $2$）のどちらかの状態にある。運営会社は各週のはじめに会員の状態を見て施策を $1$ つ選ぶ。ここでは方策を次のように固定する。

• 状態 $1$ では「お知らせメールを送る」。このとき、その週の利益は $10$ であり、次の週のはじめの状態は確率 $\frac{3}{4}$ で状態 $1$、確率 $\frac{1}{4}$ で状態 $2$ になる。
• 状態 $2$ では「割引クーポンを送る」。このとき、その週の利益は $2$ であり、次の週のはじめの状態は確率 $\frac{1}{2}$ で状態 $1$、確率 $\frac{1}{2}$ で状態 $2$ になる。

割引率を $\gamma =0.8$ とし、状態 $s$ から始めたときのこの方策による期待割引総利益（第 $t$ 週（$t=0,1,2,\dots$）の利益に ${\gamma }^t$ を掛けて足し合わせたものの期待値）を $V(s)$ とする。$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))$ で求めよ。

ある通販サイトは、各顧客を毎月のはじめに「常連」（状態 $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,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$、出口 $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$）、「故障」（状態 $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)$ を求めよ。