この記事は自作している強化学習フレームワーク SimpleDistributedRL の解説記事です。
また、前提知識として必要なマルコフ決定過程についてはこちらをご覧ください。
部分観測マルコフ決定過程
マルコフ決定過程では全ての状態が観測できることが前提でした。
しかし、状態が一部分しか観測されない事は十分に考えられます。
これを仮定したモデルが部分観測マルコフ決定過程（partially observable Markov decision process; POMDP）です。
マルコフ決定過程の要素は以下でした。
\begin{align}
S = \{s_1, s_2, ..., s_N \} &: 状態の有限集合\\
A = \{a_1, a_2, ..., a_M \} &: アクションの有限集合\\
p(s'|s, a) &: sにてaを選んだ後にs'に遷移する確率(状態遷移関数)\\
R = r(s) &: 即時報酬(報酬関数)
\end{align}
これに以下を加えたのが部分観測マルコフ決定過程です。
\begin{align}
o &: エージェントが観測した状態\\
\Omega = \{o_1, o_2, ..., o_L \} &: エージェントが観測する状態の有限集合\\
O(s',a,o) = p(o|a,s') &: aを選んでs'の状態になった後、oが観測される確率\\
\end{align}
エージェントは直接状態 $s$ を観測できず、代わりに不確かな状態 $o$ を観測します。
$o$ は $s$ によって確率的に決まる状態です。
信念状態(belief state)
次にPOMDPを考える上で新しく信念状態(belief state)という状態を考えます。
(信念状態が取りうる空間を $b \in B$ とします)
信念状態 $b$ は実際の状態 $s$ に今どのくらいいるかを表す確率です。
（イメージとしては、目隠ししている状態でマウスを右にずらしたら、多分カーソルがこの位置にあるだろうと信じている確率です）
$$
b(s) = P(s|h)
$$
$P$ は確率を表し、$h$ は現時点までの状態と行動の履歴です。
すなわち、信念状態は過去の履歴から一意に決まります。
（過去の履歴を全て見れば、今どこの状態にいるか確率で分かる）
信念状態は確率を表しているので、各信念状態は0～1を取り、合計すると1になります。
\begin{align}
0 \leqq b(s) \leqq 1 \\
\sum_{s \in S} b(s) = 1 \\
\end{align}
また、信念状態はマルコフ性を持っており、直前の信念、行動、観測された状態から次の信念を予測する事ができます。
ある信念状態 $b$ にて行動 $a$ を取り $o$ が観測された場合の次の信念状態 $b^{a,o}$ は以下となります。
b'(s') = b^{a,o}(s') = \frac{P(o|a,s') \sum_{s \in S} P(s'|s,a)b(s)}
{\sum_{s \in S}b(s) \sum_{s'' \in S}P(s''|s,a) P(o|a,s'')} \\
分母は正規化定数らしく、メインは分子です。
日本語で書くと、「次の信念 = oが観測される確率 × 次の状態になる確率 × 今の信念」でしょうか。
belief MDP
(ここが少し弱いです)
信念状態を状態とし、信念状態上でMDPを考える事で、POMDPをMDPの問題とみることができます。
これを belief MDP といいます。
belief MDP 上では状態遷移関数 $\tau$ と報酬関数 $ R_{B} $ は以下になるようです。
\begin{align}
\tau(b,a,b') &= \sum_{o \in \Omega} P(o|b,a) P(b'|b,a,o) \\
R_B(b)&= \sum_{s \in S} b(s) R(s) \\
\end{align}
$P(b'|b,a,o)$ は信念$b$が更新された場合に $a,o$ を使って更新された $b$ を返し、そうじゃない場合は0を返します。
上記を元にした belief MDP 上の状態価値は多分以下です。（独自に計算しています、間違っていたらすいません）
\begin{align}
V_{\pi}(b) &= \sum_{a \in A} \pi(a|b) \sum_{b' \in B} \tau(b,a,b') \Big( R_B(b') + \gamma V_{\pi}(b') \Big) \\
&= \sum_{a \in A} \pi(a|b) \sum_{o \in \Omega}P(o|b,a) \Big( R_B(b^{a,o}) + \gamma V_{\pi}(b^{a,o}) \Big) \\
&= \sum_{a \in A} \pi(a|b) \sum_{o \in \Omega}P(o|b,a) \Big( \sum_{s \in S} b^{a,o}(s)R(s) + \gamma V_{\pi}(b^{a,o}) \Big) \\
\end{align}
MDP通りなら、ある時刻tにおける行動価値は以下になると思います。
$$
Q_{\pi}^{'}(b_t, a_t) = \sum_{s \in S} b^{a_t, o_{t+1}}(s)R(s) + \gamma V_{\pi}(b^{a_t,o_{t+1}})
$$
トラ問題
POMDPとして一般的なトラ問題を考えます。
プレイヤーからトラは見えません。
状態は「トラが左、トラが右」の2つで初期位置はランダムに決まります。
アクションは「左に行く(aL)、右に行く(aR)、音を聞く(aC)」の3つです。
\begin{align}
S &= \{sL, sR \} \\
A &= \{aL, aR, aC \} \\
\end{align}
左または右に行った後、トラがいると報酬-100で、トラがいない場合は10の報酬が手に入ります。
（報酬は前の状態とアクションから決まるとします）
\begin{align}
R(sL, aL) &= -100 \\
R(sL, aR) &= 10 \\
R(sL, aC) &= -1 \\
R(sR, aL) &= 10 \\
R(sR, aR) &= -100 \\
R(sR, aC) &= -1 \\
\end{align}
また音を聞く aC を実行すると-1の報酬が手に入る代わりにトラの位置を聞くことができます。
ただし、正しい位置から音が聞こえる確率は85%です。
これがエージェントが観測可能な状態になります。
\begin{align}
\Omega =& \{oL, oR \} \\
p(oL|aC, sL) &= 0.85 \\
p(oR|aC, sL) &= 0.15 \\
p(oL|aC, sR) &= 0.15 \\
p(oR|aC, sR) &= 0.85 \\
\end{align}
ここで、初期状態と初期信念が以下の場合を元に考えてみます。
\begin{align}
s_0 = sL \\
b_0(sL) = 0.5 \\
b_0(sR) = 0.5 \\
\end{align}
この場合の $aL,aR,aC$ の行動価値は以下です。
（$aL$ と $aR$ は次の状態が終了なので次の価値の計算は不要）
（$aR$ は $aL$ と同じ結果になるので省略しています）
\begin{align}
Q_{\pi}(b_0, aL) &= b_0(sL)R(sL, aL) + b_0(sR)R(sR, aL)\\
&= 0.5 \times -100 + 0.5 \times 10 \\
&= -45 \\
\end{align}
報酬期待値が-45はちょっと挑戦したくない数値ですね…
$aC$ は次の状態価値を求める必要があるので展開しないと分かりません。途中までです。
\begin{align}
Q_{\pi}(b_0, aR) &= \Big( b_0(sL)R(sL, aC) + \gamma V_\pi(b_1) \Big) + snip \\
&= (0.5 \times -1 + \gamma V_\pi(b_1)) + (0.5 \times -1 + \gamma V_\pi(b_1)) \\
&= -1 + 2\gamma V_\pi(b_1) \\
\end{align}
aC を選んだ場合に oL が観測された場合の信念の更新を計算してみます。
まず、共通部分の分母は以下です。
(長くなるので確率0%は省略しています)
\begin{align}
\sum_{s \in S}b(s) \sum_{s' \in S}P(s'|s,aC) P(oL|aC,s') &= b(sL)P(sL|sL, aC)P(oL|aC, sL) + b(sR)P(sR|sR, aC)P(oL|aC, sR) \\
&= 0.5 \times 1.0 \times 0.85 + 0.5 \times 1.0 \times 0.15 \\
&= 0.5
\end{align}
それぞれの更新は以下です。
\begin{align}
b_1(sL) &= \frac{P(oL|aC, sL) \sum_{s \in S} P(sL|s,aC)b_0(s)}
{0.5} \\
&= \frac{0.85 \times (1.0 \times 0.5 + 0.0 \times 0.5)}{0.5} \\
&= 0.85 \\
\end{align}
\begin{align}
b_1(sR) &= \frac{P(oL|aC, sR) \sum_{s \in S} P(sR|s,aC)b_0(s)}
{0.5} \\
&= \frac{0.15 \times (0.0 \times 0.5 + 1.0 \times 0.5)}{0.5} \\
&= 0.15 \\
\end{align}
この場合、それぞれの行動価値は以下となります。
\begin{align}
Q_{\pi}(b_1, aL) &= b_1(sL)R(sL, aL) + b_1(sR)R(sR, aL)\\
&= 0.85 \times -100 + 0.15 \times 10 \\
&= -83.5 \\
\end{align}
\begin{align}
Q_{\pi}(b_1, aR) &= b_1(sL)R(sL, aR) + b_1(sR)R(sR, aR)\\
&= 0.85 \times 10 + 0.15 \times -100 \\
&= -6.5 \\
\end{align}
右を選んだほうが良い事がよくわかりますね。(ただ、-6.5はまだ不安が残りますね…)
この後更に aC を選んで oR が観測されるとまた信念状態が 0.5,0.5 に戻ります。
また、この後 aC を選んで oL が観測されると更に以下に更新されます。
$$
0.85 \times 1.0 \times 0.85 + 0.15 \times 1.0 \times 0.15 = 0.745
$$
\begin{align}
b_2(sL) &= \frac{0.85 \times (1.0 \times 0.85 + 0.0 \times 0.15)}{0.745} \\
&= 0.96979865771 \\
\end{align}
\begin{align}
b_2(sR) &=\frac{0.15 \times (0.0 \times 0.85 + 1.0 \times 0.15)}{0.745} \\
&= 0.03020134228 \\
\end{align}
\begin{align}
Q_{\pi}(b_2, aL) &= 0.96979865771 \times -100 + 0.03020134228 \times 10 \\
&= -96.6778523482 \\
\end{align}
\begin{align}
Q_{\pi}(b_2, aR) &= 0.96979865771 \times 10 + 0.03020134228 \times -100 \\
&= 6.6778523491 \\
\end{align}
実験
Q学習で実験してみます。
コードは以下で window_length=1 の数字部分を変えていきます。
import numpy as np
import srl
from srl import runner
# --- env & algorithm load
from srl.envs import tiger # isort: skip
from srl.algorithms import ql # isort: skip
env_config = srl.EnvConfig("Tiger")
rl_config = ql.Config()
rl_config.window_length = 1
# --- train
config = runner.Config(env_config, rl_config)
parameter, remote_memory, history = runner.train(config, timeout=30)
history.plot(left_ymin=-100, left_ymax=10)
rewards = runner.evaluate(config, parameter, timeout=30)
print(f"Average reward for 100 episodes: {np.mean(rewards)}")
runner.render(config, parameter)
window_length=1
まずは1つ前の履歴を見る場合です
（普通のQ学習です）
（POMDPなので学習できません）
Average reward for 100 episodes: -11.0
### 0, action 0, rewards [0.], next 0
env None
work0 None
state: State.LEFT, tiger: State.RIGHT
*c : -5.81563
← : -73.25240
→ : -9.71380
### 1, action 0, rewards [-1.], next 0
env {}
work0 {}
state: State.RIGHT, tiger: State.RIGHT
*c : -5.72745
← : -12.73239
→ : -79.15219
### 2, action 0, rewards [-1.], next 0
env {}
work0 {}
state: State.LEFT, tiger: State.RIGHT
*c : -5.81563
← : -73.25240
→ : -9.71380
### 3, action 0, rewards [-1.], next 0
env {}
work0 {}
state: State.LEFT, tiger: State.RIGHT
*c : -5.81563
← : -73.25240
→ : -9.71380
以降繰り返し
チェック(aC)ばかり選んで報酬がマイナスですね。
トラを引くリスクの方が高いのでチェックで終わらせた方がお得になっています。
window_length=3
3step見る場合です。
Average reward for 100 episodes: 6.2
### 0, action 0, rewards [0.], next 0
env None
work0 None
state: State.LEFT, tiger: State.RIGHT
*c : -0.27630
← : -67.71500
→ : -22.61441
### 1, action 0, rewards [-1.], next 0
env {}
work0 {}
state: State.RIGHT, tiger: State.RIGHT
*c : 0.72014
← : -39.25872
→ : -55.71902
### 2, action 0, rewards [-1.], next 0
env {}
work0 {}
state: State.RIGHT, tiger: State.RIGHT
*c : 3.12024
← : -1.15364
→ : -90.30930
### 3, action 1, rewards [-1.], next 0
env {}
work0 {}
state: State.RIGHT, tiger: State.RIGHT
c : -1.84137
*← : 8.87474
→ : -99.53198
### 4, action 1, rewards [10.], done(env), next 0
env {}
work0 {}
state: State.RIGHT, tiger: State.RIGHT
報酬がプラスになっていますね。
3回チェックしてから扉を選んでいます。
window_length=10
Tigerは最大10stepの設定にしているので、これでMDPになります。
Average reward for 100 episodes: 3.02
### 0, action 0, rewards [0.], next 0
env None
work0 None
state: State.RIGHT, tiger: State.LEFT
*c : 2.19000
← : -54.61756
→ : -47.82339
### 1, action 0, rewards [-1.], next 0
env {}
work0 {}
state: State.LEFT, tiger: State.LEFT
*c : 3.49856
← : -88.91712
→ : -4.59851
### 2, action 0, rewards [-1.], next 0
env {}
work0 {}
state: State.LEFT, tiger: State.LEFT
*c : 5.37993
← : -99.91441
→ : -1.71566
### 3, action 0, rewards [-1.], next 0
env {}
work0 {}
state: State.LEFT, tiger: State.LEFT
*c : 7.20845
← : -99.72350
→ : 6.51089
### 4, action 2, rewards [-1.], next 0
env {}
work0 {}
state: State.LEFT, tiger: State.LEFT
c : 6.86379
← : -100.00000
*→ : 10.00000
### 5, action 2, rewards [10.], done(env), next 0
env {}
work0 {}
state: State.LEFT, tiger: State.LEFT
4回チェックしていますね。
学習時間は30秒ですが、それでも全状態は学習しきれていなそうでした。(Qテーブル数が増え続けました)
こんな小さい規模でも状態数がすごい事になってますね
参考
・マルコフ過程・マルコフ報酬過程・マルコフ決定過程・部分観測マルコフ決定過程
・《第4回》部分観測マルコフ決定過程と強化学習
・部分観測マルコフ決定過程下での強化学
・部分観測マルコフ決定過程(wikipedia)