MDPとPOMDPって結局なんやねん

# まえがき
MDPはMarkov Decision Processの略で，POMDPはPartially Observable MDPの略です．
MDPについては，「[ゼロから作るDeep Learning ❹](https://www.oreilly.co.jp/books/9784873119755/)」（以下ゼロつく4）を既に読んでいるという前提で話を進めていきます．
この本は，私が強化学習初学者の頃にいくつかの本や資料を読んだ中で，最も強化学習初学者に易しくわかりやすい本でした．
ですので，まずはこの記事を読む前にゼロつく4を読んでいただけるとよいと思います．
一応，初歩的な部分にも注釈等を入れていますが，再確認をしなくて済むように入れているだけなので，ゼロつく4を読む前の初学者の方向けには書いていません．

POMDPについては，機械学習プロフェッショナルシリーズの「[強化学習](https://www.kspub.co.jp/book/detail/5155912.html)」（以下森村強化学習）を既に読んでいるという前提で話を進めていきます（第7章の部分観測マルコフ決定過程だけ読んでいれば追えます）．
また，MDPについてもゼロつく4からだけでなく，森村強化学習も参考にしながら記述していきます．

ゼロつく4と森村強化学習を読んでいく中で，MDPとPOMDPを学んだ上で結局何がしたかったんだ？というモヤモヤがあったので，自分なりに順を追って整理してみました．
ややこしくなりすぎないように基本的にはゼロつく4の進め方準拠，かつ，一部端折りながらでMDPとPOMDPを説明していきます．結果的に，部分的に厳密性などが損なわれている点があるので，そこは整理用の資料ということで大目に見ていただけますと幸いです．
一方，POMDPにおいては端折りながらも，森村強化学習において行間が広い部分を補いながら可能な限り平易に説明していきます（そういう意味で，POMDPについては教科書読めばわかる部分は端折っているけれども，一部だけ詳しく説明しているという不思議な資料に仕上がってしまいました）．

別件ですが，リンクをつけた引用の書き方がわからないので，本文に直接リンクを埋め込みますがご了承ください（いい埋め込み方をご存知の方がいらっしゃいましたら，コメントしていただけますと幸いです）．


# 結論
### MDPとPOMDPの目的
期待収益の最大化をする最適方策を得る

### MDPの解き方
Q関数のベルマン最適方程式にargmaxを取ることで最適方策を取得する

### POMDPの解き方
1. belief MDPをPOMDPの問題として帰着させる
1. belief MDPのQ関数のベルマン最適方程式にargmaxを取ることで最適方策を取得する


# 1. MDPとは
まず始めに，MDPを理解するために確率過程，マルコフ性，マルコフ過程を簡単に（乱暴に）説明しておきます．

:::note info
[確率過程](https://ja.wikipedia.org/wiki/%E7%A2%BA%E7%8E%87%E9%81%8E%E7%A8%8B)とは，条件によって変化する確率変数の数理モデルのことです．
例えば，株価の変動を数学的に記述したものです．
:::

:::note info
[マルコフ性](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E6%80%A7)とは，乱暴に言うと未来の状態が現在の状態にのみ依存している性質です．
wikipediaでは以下のように記述されています．
>確率過程の持つ特性の一種で、その過程の将来状態の条件付き確率分布が、現在状態のみに依存し、過去のいかなる状態にも依存しない特性を持つことをいう。
:::

:::note info
[マルコフ過程](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E9%81%8E%E7%A8%8B)とは，マルコフ性を持つ確率過程のことです．
:::

MDPはMarkov Decision Process（マルコフ決定過程）の略であり，マルコフ過程 + 行動選択（意思決定）と思ってもらえれば簡単かもしれません．
続いてMDPの目的から解き方の流れを説明するにあたって，報酬，収益，期待収益を説明します．

:::note info
報酬とは，MDPにおいて，各状態（この状態とはMDPのstateのことです）で発生する利益のような値です．
状態によっては報酬が0という場合もあります．
:::

:::note info
収益とは，MDPの終端で得られる累積報酬のことです．
:::

:::note info
期待収益とは，収益の期待値のことであり，平均的な収益ということです．
:::

MDPの目的は[前述](#mdpとpomdpの目的)の通りで，期待収益の最大化と書きました．
言い換えると，期待収益を最大化するための行動選択，すなわち**最適方策**を得たいということになります．
MDPを解く流れは
1. 価値関数を定義する
1. 価値関数のベルマン方程式を求める
1. Q関数のベルマン方程式を求める
1. 価値関数，Q関数のベルマン最適方程式を求める
1. Q関数のベルマン最適方程式の行動に対してargmaxを取って最適方策を得る

となっています．
それでは順を追って見ていきましょう．

## 1.1. 価値関数を定義する
まずは収益から定義していきましょう．

```math
G_t \triangleq R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \tag{1}
```

ただし，$G_t$は時刻$t (t \in \mathbb{N})$の収益，$\triangleq$は定義の意味，$R_t$は時刻$t$の報酬，$\gamma$は割引率です．
続いて，価値関数を定義します．

```math
v_\pi(s) \triangleq\mathbb{E}[G_t | S_t = s] \tag{2}
```

$v_\pi(s)$は方策$\pi$に従って状態$s$を入力とした価値関数，$\mathbb{E}[\cdot]$は期待値です．方策とは，行動を出力する関数です．
結果的に，価値関数とは**時刻$t$の状態$S_t=s$を条件として方策$\pi$に従った時の期待収益を吐き出す関数です．**
また，価値とは，価値関数に具体的な状態を入力した際に得られる期待収益の期待値です．価値関数はあたかも実現値$s$を入力としているように見えますが，これは時刻情報を取り除いた状態という変数を入力しています．

## 1.2 価値関数のベルマン方程式を求める
価値関数の定義が終わったら，次は価値関数のベルマン方程式を求めます．
ベルマン方程式は再帰的方程式になっており，式1で定義した収益の無限の長さから解放されます．
まず，収益を変形していきます．

```math
\begin{align}
G_t &\triangleq R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \tag{1} \\
G_{t+1} &\triangleq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \tag{3}
\end{align}
```

式1の$\gamma R_{t+1}$以降は式3と共通部分があり，式3を式1に代入すると

```math
G_t = R_t + \gamma G_{t+1} \tag{4}
```

このように，収益は無限の長さから解放されました．
式4を式2の価値関数に代入して，期待値の線形性で分解すると以下の式になります．

```math
\begin{align}
v_\pi(s) &= \mathbb{E}[R_t + \gamma G_{t+1} | S_t = s] \\
&= \mathbb{E}[R_t| S_t = s] + \mathbb{E}[\gamma G_{t+1}|S_t = s] \tag{5}
\end{align}
```

式5の第一項は報酬関数について，方策による期待値であり，以下の式になります．

```math
\mathbb{E}[R_t | S_t = s] = \Sigma_{a} \pi(a | s)r(s, a) \tag{6}
```

ただし，$\pi(a|s)$は現在の状態を条件とした行動の条件付き確率（方策），$r(s, a)$は現在の状態と現在の行動を入力とした報酬関数を表しています．

続いて，式5の第二項は現在の状態から次時刻の収益について，方策と状態遷移関数による期待値であり，以下の式になります．

```math
\begin{align}
\mathbb{E}[\gamma G_{t+1} | S_t = s] &= \Sigma_{a, s'} \pi(a|s) p_T(s'|s, a)\mathbb{E}[\gamma G_{t+1} | S_{t+1} = s']　\tag{7} \\
&= \Sigma_{a, s'} \pi(a|s) p_T(s'|s, a) \gamma v_\pi(s')　(\because \text{式2}) \tag{8}
\end{align}
```

式7の導出はゼロつく4のp.68, 69を参照してください．
式6, 8を式5に代入すると以下の価値関数のベルマン方程式が導かれます．

```math
v_\pi(s) = \Sigma_{a}\pi(a|s)\{r(s, a) + \Sigma_{s'} p_T(s'|s, a) \gamma v_\pi(s')\} \tag{9}
```

:::note warn
ゼロつく4では報酬関数は$r(s, a, s')$とされており，次時刻の状態$s'$にも依存する形で記載されています．しかしながら，強化学習の論文や森村強化学習では次時刻の状態$s'$に依存しない$r(s, a)$として記載されています．
報酬とは，次時刻の状態$s'$が確定したときに得られるものですから，状態遷移が決定的でないと$r(s, a)$とは記載できないと私は考えています（要するにゼロつく4の記載が正しいと考えています）．
ですが，強化学習の論文や他の文献でゼロつく4のように，次時刻の状態を入力とする報酬関数を扱っているものは見たことがないので，ひとまずここでは一般的な報酬関数の形$r(s, a)$に倣おうと思います．
ここについて何かご存知の方がいればコメントしていただけますと幸いです．
:::

## 1.3 Q関数のベルマン方程式を求める

価値関数の次は，Q関数のベルマン方程式を求めていきます．
Q関数とは，現在の状態に加えて，現在の行動も条件とした期待収益です．

MDPを考える上で混乱する点として，現在の行動は現在の状態と報酬と得られる時系列が一致していないことです．
例えば，現在の状態行動報酬のタプルとして$(s, a, r)$が得られる場合，現在の状態$s$と現在の報酬$r$は前時刻の行動$a`$によって得られるものであり，現在の行動$a$は現在の状態$s$を入力として得られるものです．
要するにズレとしては$(s, r)$が得られた後に$a$が得られるということです．

このズレがQ関数を考えるときに混乱を招きます（私は初学者の頃に混乱しました）．
Q関数は現在の状態と行動を条件とした期待収益と書きましたが，現在の行動を強制的に決定して条件としてしまうのがQ関数です．

前置きが長くなりましたが，まずは式2, 5の価値関数と同様にQ関数を定義，変形します．

```math
\begin{align}
v_\pi(s) &\triangleq\mathbb{E}[G_t | S_t = s] \tag{2} \\
&= \mathbb{E}[R_t| S_t = s] + \mathbb{E}[\gamma G_{t+1}|S_t = s] \tag{5} \\
q_\pi(s, a) &\triangleq\mathbb{E}[G_t | S_t = s, A_t=a] \tag{10} \\
&= \mathbb{E}[R_t| S_t = s, A_t = a] + \mathbb{E}[\gamma G_{t+1}|S_t = s, A_t = a] \tag{11}
\end{align}
```

式11のQ関数を価値関数と同様に変形していきます．
式11の第一項は，式5の価値関数の第一項式6と対比すると以下のようになります．

```math
\begin{align}
\mathbb{E}[R_t | S_t = s] &= \Sigma_{a} \pi(a | s)r(s, a) \tag{6} \\
\mathbb{E}[R_t| S_t = s, A_t = a] &= r(s, a) \tag{12}
\end{align}
```

Q関数は現在の行動$a$を強制的に決定して条件としているため，方策で期待値を取る必要はありません．ただの報酬関数です．
式11の第二項は，式5の価値関数の第二項式7, 8と対比すると以下のようになります．

```math
\begin{align}
\mathbb{E}[\gamma G_{t+1} | S_t = s] &= \Sigma_{a, s'} \pi(a|s) p_T(s'|s, a)\mathbb{E}[\gamma G_{t+1} | S_{t+1} = s']　\tag{7} \\
&= \Sigma_{a, s'} \pi(a|s) p_T(s'|s, a) \gamma v_\pi(s')　(\because \text{式2}) \tag{8}\\
\mathbb{E}[\gamma G_{t+1} | S_t = s, A_t = a] &= \Sigma_{s'} p_T(s'|s, a)\mathbb{E}[\gamma G_{t+1} | S_{t+1} = s'] \tag{13} \\
&= \Sigma_{s'} p_T(s'|s, a) \gamma v_\pi(s')　　(\because \text{式2}) \tag{14}
\end{align}
```

式13は価値関数同様にゼロつく4のp.68, 69, 76, 77を参照してください．
ちなみに，式13の$\mathbb{E}[\gamma G_{t+1} | S_{t+1} = s']$で$A_{t+1} = a'$が消えている理由は，Q関数は現在の行動だけ選択してあとは方策に従うためです．
さて，式12, 14を式11のQ関数に代入すると，Q関数のベルマン方程式が導かれます．

```math
q_\pi(s, a) =  r(s, a) + \Sigma_{s'}p_T(s'|s, a) \gamma v_\pi(s') \tag{15}
```

Q関数のベルマン方程式の導出についてはここで終わらずに，さらに**価値関数とQ関数の関係**と，**最終的なQ関数のベルマン方程式**求めておきます．
価値関数とは，Q関数の全ての行動についての重み付き和となります．すなわち，価値関数はQ関数の期待値であり，以下のようになります．

```math
v_\pi(s) = \Sigma_a \pi(a|s) q_\pi(s, a) \tag{16}
```

最後に，式15のQ関数のベルマン方程式に式16を代入すると，最終的なQ関数のベルマン方程式が導かれます．

```math
q_\pi(s, a) =  r(s, a) + \gamma \Sigma_{a, s'}p_T(s'|s, a) \pi(a'|s') q_\pi(s', a') \tag{17}
```

## 1.4 価値関数，Q関数のベルマン最適方程式を求める
このセクションで大事になってくるのは，**最適価値関数**と**最適Q関数**とは何かです．
最適価値関数とは，価値が最大となる行動を必ず取る方策に従う価値関数のことです．
最適Q関数とは，次時刻からQ値が最大となる行動を必ず取る方策に従うQ関数のことです．

そして，ベルマン最適方程式とは，最適価値関数，または最適Q関数を用いたベルマン方程式のことです．

では，最適価値関数$v_*(s)$を式9の価値関数と対比させて導出します．

```math
\begin{align}
v_\pi(s) &= \Sigma_{a}\pi(a|s)\{r(s, a) + \Sigma_{s'} p_T(s'|s, a) \gamma v_\pi(s')\} \tag{9} \\
v_*(s) &= \text{max}_a \{r(s, a) + \Sigma_{s'} p_T(s'|s, a) \gamma v_*(s')\}  \tag{18}
\end{align}
```

$\text{max}_a$は，現在の行動$a$を操作して$\text{max}$関数内が最大になる値を取り出す操作になります．

次は，最適Q関数$q_*(s, a)$を式17のQ関数と対比させて導出します．

```math
\begin{align}
q_\pi(s, a) &= r(s, a) + \gamma \Sigma_{a, s'}p_T(s'|s, a) \pi(a'|s') q_\pi(s', a') \tag{17} \\
q_*(s, a) &= r(s, a) + \gamma \Sigma_{s'}p_T(s'|s, a) \text{max}_{a'} q_*(s', a') \tag{19}
\end{align}
```

## 1.5 Q関数のベルマン最適方程式の行動に対してargmaxを取って最適方策を得る
ついにMDPも大詰めです！
MDPの目的は，期待収益を最大化する最適方策を得ることです．
先に式16について最適価値関数に書き換えたものを求めておきます．

```math
\begin{align}
v_\pi(s) &= \Sigma_a \pi(a|s) q_\pi(s, a) \tag{16} \\
v_*(s) &= \text{max}_a q_*(s, a) \tag{20}
\end{align}
```

それでは，式19のQ関数のベルマン最適方程式の行動に対してargmaxを取って最適方策を得ていきます．

```math
\begin{align}
\mu_*(s) &= \text{argmax}_a q_*(s, a) \tag{21} \\
&= \text{argmax}_a \{r(s, a) + \gamma \Sigma_{s'}p_T(s'|s, a) \text{max}_{a'} q_*(s', a')\} \tag{22} \\
&= \text{argmax}_a  \{r(s, a) + \gamma \Sigma_{s'}p_T(s'|s, a) v_*(s')\} \qquad (\because \text{式20}) \tag{23}
\end{align}
```

式23がMDPの解き方です！
$\text{argmax}_a$は，$\text{argmax}$関数内が最大になる値をとる行動$a$を取り出す操作になります．

実際に最適方策を求める際には，価値やQ値がテーブルで保管できるくらいの状態数のケースであれば，モデルベースであれば方策反復法などを使ったりします．
ただ，今回は実際の最適方策の求め方については今回のスコープ外なので省略します．


# 2. POMDPとは
POMDPはPartially Observable MDP（部分観測マルコフ決定過程）の略であり，MDPにおいて**マルコフ性が成り立たない確率過程**のことを指します．というのも，POMDPは状態のうち一部分の「観測」しか受け取れないためです．

マルコフ性を満たしていないと，一つ前の状態だけでなく，過去全ての状態・行動・報酬のタプルを保管しておかなくてはいけないため，タイムステップが増えるといずれ状態・行動・報酬のタプルの数は発散してしまいます．

ですので，戦略としては**POMDPをマルコフ性を満たす確率過程のbelief MDPに変換**し，belief MDPにおいてMDPと同様の手順で最適方策を取得します．POMDPをbelief MDPに変換したことで，belief MDPで最適方策を取得することは実質的にPOMDPで最適方策を取得することになります（belief MDPがPOMDPとして帰着しているということです）．

POMDPをbelief MDPに変換する流れは
1. POMDP，belief MDP，方策，目的関数，価値関数の定義
1. POMDPの最適方策の探索問題を，belief MDPにおける最適方策の探索問題に帰着させる

となっています．
POMDPを解く流れはMDPと同様

1. 価値関数のベルマン方程式を求める
1. Q関数のベルマン方程式を求める
1. 価値関数，Q関数のベルマン最適方程式を求める
1. Q関数のベルマン最適方程式の行動に対してargmaxを取って最適方策を得る

となっています．
POMDPはMDPと比べて結構険しい道のりですが，順に追っていきましょう．

## 2.1 POMDP，belief MDP，方策，目的関数，価値関数の定義
### 2.1.1 POMDPの定義
MDPの説明では，定義をすっ飛ばして厳密性を犠牲する代わりに，シンプルな理解経路を意識しました．
代わりに，POMDPではbelief MDPの最適方策の探索問題をPOMDPの最適方策の探索問題に帰着する際に，定義に則った説明が必要になるところがあるので，MDPの説明よりも険しい道のりになります．

まずはMDPの定義から入っていきます．
MDPは，有限状態集合，有限行動集合，初期状態確率関数，状態遷移確率関数，報酬関数の5つから成る確率過程です．
以下にMDPと，5つの要素の定義を記載します．

```math
\begin{align}
\text{MDP：}&\text{M} \triangleq \{\mathcal{S, A}, p_{s_0}, p_T, g \} \\
\text{有限状態集合：}&\mathcal{S} \triangleq \{s^1, \ldots, s^{|\mathcal{S}|}\} \ni s \tag{1} \\
\text{有限行動集合：}&\mathcal{A} \triangleq \{a^1, \ldots, a^{|\mathcal{A}|}\} \ni a \tag{2} \\
\text{初期状態確率関数：}&p_{s_0} : \mathcal{S} \rightarrow [0, 1] : p_{s_0}(s) \triangleq \text{Pr}(S_0 = s) \tag{3} \\
\text{状態遷移確率：}&p_T: \mathcal{S \times S \times A} \rightarrow [0, 1] : p_T(s' | s, a) \triangleq \text{Pr}(S_{t+1}=s' | S_t = s, A_t = a), \quad \forall t \in \mathbb{N}_0 \tag{4} \\
\text{報酬関数：}&g: \mathcal{S \times A} \rightarrow \mathbb{R} \tag{5}
\end{align}
```

数式番号についてはMDPの説明からは引き継がずにリセットして使います．
こちらの定義はp.7の森村強化学習に則っていますが，式1についてだけ本の記載と異なっています．
森村強化学習の有限状態集合は$\mathcal{S} \triangleq \\{1, \ldots, |\mathcal{S}|\\} \ni s$となっていますが，おそらくこれは誤記であると私は考えています．

続いて，POMDPの定義に移ります．
POMDPは，MDPに有限観測集合，観測確率関数を追加した確率過程です．
以下にPOMDP，追加の2つの要素，POMDPで必要になる履歴（history）の定義を記載します．

```math
\begin{align}
\text{POMDP：}&\text{P} \triangleq \{\mathcal{S, A}, p_{s_0}, p_T, g, \mathcal{O}, p_o\} \\
\text{有限観測集合：}&\mathcal{O} \triangleq \{o^1, \ldots, o^{|\mathcal{O}|}\} \ni o \tag{6}\\
\text{観測確率集合：}&p_o: \mathcal{O \times A \times S} \rightarrow [0, 1]: p_o(o| \grave{a}, s) \triangleq \text{Pr}(O_t = o | A_{t-1} = \grave{a}, S_t = s), \quad \forall t \in \mathbb{N} \tag{7}\\
\text{履歴：}&\check{h}_t \triangleq \{a_0, r_0, o_1, \ldots, a_{t-1}, r_{t-1}, o_t\} \tag{8}
\end{align}
```

Qiitaの数式だとなぜか式7にある前時刻のアクセントが巨大化してしまいます😭

### 2.1.2 belief MDPの定義
belief MDPの定義を行います．
belief MDPは信念状態集合，有限行動集合，初期信念状態確率関数，信念状態遷移確率関数，信念状態報酬関数の5つから成る確率過程です．
先にbelief MDPを定義するための，信念状態，信念状態集合，信念作用素，信念状態の更新式についてを記載します．

```math
\begin{align}
\text{信念状態：}&b_t: \mathcal{S \times \check{H}_t} \rightarrow [0, 1]: b_t(s; \check{h}_t) \triangleq \text{Pr}(S_t = s | \check{H}_t = \check{h}_t, \text{P}), \quad \forall s \in \mathcal{S} \tag{9}\\
\text{信念状態集合：}&\mathcal{B} \triangleq \{b:\mathcal{S} \rightarrow[0, 1]: \Sigma_{s\in\mathcal{S}} b(s) = 1\} \tag{10} \\
\text{信念状態更新式（準備）：}&b_{t+1}(s') = \text{Pr}(S_{t+1} = s'| \check{H}_{t+1} = \check{h}_{t+1}) \\
&= \frac{p_o(o_{t+1}|a_t, s') \Sigma_{s \in \mathcal{S}} p_T(s'|s, a_t)\mathbb{I}_{\{g(s, a_t)=r_t\}}b_t(s)}{\Sigma_{s' \in \mathcal{S}}p_o(o_{t+1}|a_t, s') \Sigma_{s \in \mathcal{S}} p_T(s'|s, a_t)\mathbb{I}_{\{g(s, a_t)=r_t\}}b_t(s)}, \quad \text{where} \quad \forall s' \in \mathcal{S} \tag{11} \\
\text{信念作用素：}&(\Psi(b, a, r, o'))(s') \triangleq \frac{p_o(o'|a, s') \Sigma_{s \in \mathcal{S}} p_T(s'|s, a)\mathbb{I}_{\{g(s, a)=r\}}b(s)}{\Sigma_{s' \in \mathcal{S}}p_o(o'|a, s') \Sigma_{s \in \mathcal{S}} p_T(s'|s, a)\mathbb{I}_{\{g(s, a)=r\}}b(s)} \quad (\because \text{式11}) \tag{12}\\
\text{信念状態更新式：}&b_{t+1} = \Psi(b_t, a_t, r_t, o_{t+1}) \tag{13}
\end{align}
```

式11，12，13の導出過程は森村強化学習p.198を参照してください．
以下にbelief MDPと，belief MDPの5つの要素の定義を記載します．

```math
\begin{align}
\text{belief MDP：}&\text{M}_\text{b} \triangleq \{\mathcal{B, A}, b_0, p_\text{b}, g_\text{b}\}\\
\text{信念状態集合：}&\mathcal{B} \triangleq \{b:\mathcal{S} \rightarrow[0, 1]: \Sigma_{s\in\mathcal{S}} b(s) = 1\} \tag{14}\\
\text{有限行動集合：}&\mathcal{A} \triangleq \{a^1, \ldots, a^{|\mathcal{A}|}\} \ni a \tag{15}\\
\text{初期信念状態確率関数：}&b_0 : \mathcal{B} \rightarrow [0, 1] : b_0(s) \triangleq \text{Pr}(B_0 = b) \tag{16}\\
\text{信念状態遷移確率関数：}&p_\text{b}: \mathcal{B \times B \times A} \rightarrow \bar{\mathbb{R}}_{\ge 0}: \int_{b' \in \mathcal{B}} p_\text{b}(b'|b, a)db' = 1: p_\text{b}(b'| b, a) = \Sigma_{z \in \tilde{\mathcal{Z}}} \delta_{\{b'=\Psi(b, a, z)\}} p_\text{z}^\text{ba}(z | b, a) \tag{17}\\
\text{信念状態報酬関数：}&g_\text{b}: \mathcal{B \times A} \rightarrow \mathbb{R}: g_\text{b}(b, a) \triangleq \Sigma_{s \in \mathcal{S}} b(s)g(s, a) \tag{18}
\end{align}
```

ただし，式16の初期信念状態確率関数については，森村強化学習で触れられてはいませんが，おそらく定義域からもMDPと同様の確率関数として設定してよいはずなので，私が勝手に定義しました（要出典です）．
また，式17の導出は森村強化学習p.204-206を参照してください．$z$の定義はこれ以降この記事では使わないので，森村強化学習に任せます．

ここで重要になってくるのが，belief MDPはどんな便利な性質があるゆえに定義されたのか，ということです．
belief MDPはマルコフ性を持つ確率過程であり，**MDPと同様の便利な性質をほとんど利用できます**．
ただし，MDPはPOMDPのように状態数が有限でしたが，belief MDPでは信念状態が実数空間であり，$t \rightarrow \infty$のときに履歴が発散するので，信念状態が条件となると状態数が発散する点がMDPと異なります．
この問題点については，実際に解くときに様々な近似が行われますが．今回の記事のスコープ外なので紹介はしません．

### 2.1.3 方策の定義
belief MDPの信念状態を条件とした確率的と決定的の2つの方策の定義をしていきます．

```math
\begin{align}
\text{確率的方策：}&\check{\Pi} \triangleq \{ \check{\pi}: \mathcal{A \times B} \rightarrow [0, 1]: \Sigma_{a \in \mathcal{A}}\check{\pi}(a|b)=1, \forall s \in \mathcal{S}\} \tag{19}\\
\text{決定的方策：}&\check{\Pi}^d \triangleq \{ \check{\pi}^d:\mathcal{B \rightarrow A}\} \tag{20}
\end{align}
```

続いて，信念状態の確率的方策の系列を用意します．

```math
\begin{align}
\check{\pi}^\text{m} = \{\check{\pi}_0 \in \check{\Pi}, \check{\pi}_1 \in \check{\Pi},\ldots\} \in \check{\Pi}^\text{M} \tag{21}
\end{align}
```

### 2.1.4 目的関数の定義
POMDPの目的関数を定義します．

```math
\begin{align}
f_\text{P}(\check{\pi}) &\triangleq \mathbb{E}[\Sigma_{t=0}^\infty \gamma R_t | \text{P}(\check{\pi})] \\
&=  \mathbb{E}[R_t + \gamma G_{t+1} | \text{P}(\check{\pi})] \tag{22}
\end{align}
```

ここの最初の収益の記述はゼロつく4ではなく，森村強化学習に準拠しています．式22でゼロつく4に寄せています．
目的関数とは，最大化または最小化したい関数に使われる名称です．
一方，損失関数は最小化したい関数のみに使われる名称です．

そして，POMDPで解く問題は以下の最適方策の探索になります．

```math
\check{\pi}^* = \text{argmax}_{\check{\pi} \in \check{\Pi}^\text{M}} f_\text{P}(\check{\pi}) \tag{23}
```

### 2.1.5 価値関数の定義
belief MDPにおける方策系列$\check{\pi} \in \check{\Pi}$の価値関数の定義をします．

```math
V_\text{b}^{\check{\pi}}: \mathcal{B \rightarrow \mathbb{R}}: V_\text{b}^{\check{\pi}}(b) \triangleq \mathbb{E}[\Sigma_{t=0}^\infty \gamma^t g_\text{b}(B_t, A_t) | B_0 = b, \text{M}_\text{b}(\check{\pi})], \quad \text{where} \quad \forall b \in \mathcal{B} \tag{24}
```

式24以降，belief MDP $M_b$において方策$\check{\pi}$に従い行動選択する確率過程を$M_b(\check{\pi})$と表記します（Qiitaはインライン数式でtextコマンドを入れた後に下付き文字が入れられないようなので，やむを得ずbelief MDPを斜体にしています）．
また，ここでの注意点として，期待値の中の条件付けされている側を収益として記していないのは，Belief MDPの価値関数をPOMDPの価値関数として帰着させるためです．

## 2.2 POMDPの最適方策の探索問題を，belief MDPにおける最適方策の探索問題に帰着させる
やっと定義が終わったので，ここからはbelief MDPの価値関数をPOMDPの目的関数として帰着させた後に，POMDPの最適方策の探索問題をbelief MDPにおける最適方策の探索問題に帰着させます．
まずは，belief MDPの価値関数の変形を行う際に便利なので，確率過程$M_b(\check{\pi})$に従う初期信頼状態$B_0 = b$を条件とした，ある時間$t\in \mathbb{N}$の信頼状態の履歴についての期待値を，確率過程$\text{P}(\check{\pi})$に従う形に変形します．
まずは，期待値を展開します．

```math
\mathbb{E}[B_t(s) | B_0 = b, \text{M}_\text{b}(\check{\pi})] = \Sigma_{h\in\check{\mathcal{H}}_t} b_t(s; h) \text{Pr}(\check{H_t} = h | p_{s_0} = b, \text{P}(\check{\pi})) \tag{25}
```

式25は森村強化学習p.205に記載されていますが，変形が唐突すぎて私は理解するまでに時間を要しました．

式25の行間が広い原因として2点あり，1点目は初期信頼状態$B_0 = b$としていたのに，次に初期状態確率関数$p_{s_0}$を持ち出していて，なぜ初期信頼状態確率関数$b_0(s)$を最初にだしていないのかについです．
これは，明示的に信頼状態$b$を初期状態確率関数$p_{s_0}$に信頼状態$b$を代入したいためです．

2点目は，なぜ確率過程$\text{P}(\check{\pi})$に従う初期状態確率関数$p_{s_0} = b$を条件とした，ある時間$t\in \mathbb{N}$の履歴の確率を持ち出したかについてです．
これは，確率過程$\text{M}_\text{b}(\check{\pi})$を確率過程$\text{P}(\check{\pi})$に書き換えたいためです．履歴自体は確率過程$\text{P}(\check{\pi})$に従って初期状態確率関数から生成されています．

続いて，式25を式9の信念状態を用いてして変形します．

```math
\begin{align}
&b_t(s; \check{h}_t) \triangleq \text{Pr}(S_t = s | \check{H}_t = \check{h}_t, \text{P}), \quad \forall s \in \mathcal{S} \tag{9}　\\
&\Sigma_{h\in\check{\mathcal{H}}_t} b_t(s; h) \text{Pr}(\check{H_t} = h | p_{s_0} = b, \text{P}(\check{\pi})) \\
&\qquad= \Sigma_{h\in\check{\mathcal{H}}_t} \text{Pr}(S_t = s | \check{H_t} = h, \text{P}) \text{Pr}(\check{H_t} = h | p_{s_0} = b, \text{P}(\check{\pi})) \\
&\qquad= \text{Pr}(S_t = s | p_{s_0} = b, \text{P}(\check{\pi})), \quad \text{where} \quad \forall(s, b, \pi) \in \mathcal{S \times B \times \check{\Pi}} \tag{26}\\
&\mathbb{E}[B_t(s) | B_0 = b, \text{M}_\text{b}(\check{\pi})] = \text{Pr}(S_t = s | p_{s_0} = b, \text{P}(\check{\pi})), \quad \text{where} \quad \forall(s, b, \pi) \in \mathcal{S \times B \times \check{\Pi}} \quad (\because \text{式25, 26}) \tag{27}
\end{align}
```

さて，式27を使ってbelief MDPの価値関数を変形します．

```math
\begin{align}
V_\text{b}^{\check{\pi}}(b) &= \Sigma_{t=0}^\infty \gamma^t \mathbb{E}[g_\text{b}(B_t, A_t) | B_0 = b, \text{M}_\text{b}(\check{\pi})] \\
&= \Sigma_{t=0}^\infty \gamma^t \mathbb{E}[\Sigma_{s\in\mathcal{S}}B_t(s)g(s, A_t) | B_0 = b, \text{M}_\text{b}(\check{\pi})] \quad (\because \text{式18}) \\
&= \Sigma_{t=0}^\infty \gamma^t \Sigma_{s\in\mathcal{S}}\Sigma_{a \in \mathcal{A}} \text{Pr}(S_t = s, A_t = a| p_{s_0} = b, \text{P}(\check{\pi})) g(s, a) \quad (\because \text{式27}, \mathcal{A}\text{について周辺化}) \\
&= \mathbb{E}[\Sigma_{t=0}^\infty \gamma^t R_t | p_{s_0} = b, \text{P}(\check{\pi})], \quad \text{where} \quad \forall b \in \mathcal{B} \\
&= \mathbb{E}[R_t + \gamma G_{t+1} | p_{s_0} = b, \text{P}(\check{\pi})] \tag
{28}\\
&\tag{29}
\end{align}
```

式28から式29への変形は森村強化学習では記載されていませんが，ゼロつく4の表記に寄せるために導入しました．

次にbelief MDPの価値関数をPOMDPの目的関数として帰着させます．
任意の$\check{\pi} \in \check{\Pi}$について，式22のPOMDPの目的関数を信念状態の価値関数$V_\text{b}^{\check{\pi}}$を用いて表します．

```math
\begin{align}
f_\text{P}(\check{\pi}) &=  \mathbb{E}[R_t + \gamma G_{t+1} | \text{P}(\check{\pi})] \tag{22} \\
f_\text{P}(\check{\pi}) &= V_\text{b}^{\check{\pi}}(p_{s_0}) \quad (\because \text{式29}) \tag{30}
\end{align}
```

最後に仕上げです．
式23のPOMDPの最適方策の探索問題を，式30を用いてBelief MDPにおける最適方策の探索問題に帰着させます．

```math
\begin{align}
\check{\pi}^* = \text{argmax}_{\check{\pi} \in \check{\Pi}^\text{M}} f_\text{P}(\check{\pi}) \tag{23} \\
\check{\pi}^* = \text{argmax}_{\check{\pi} \in \check{\Pi}^\text{M}}V_\text{b}^{\check{\pi}}(p_{s_0}) \tag{31}
\end{align}
```

式31によってbelief MDPでPOMDPと同様の問題を扱える上に，belief MDPはMDPの性質も多く満たしているので，**MDPと同様の議論が色々できる**ようになります．

## 2.3 POMDPを解く流れ
POMDPを解く流れはMDPと同様なので，部分部分の結論のみを書き下して本記事を終わろうと思います．

### 2.3.1 価値関数のベルマン方程式
```math
V_\text{b}^{\check{\pi}}(b) = \Sigma_{a\in\mathcal{A}}  \check{\pi}(a | b) \delta_{\{b' = \Psi(b, a, z)\}}\{g_\text{b}(b, a) + \gamma \Sigma_{z\in\tilde{\mathcal{Z}}} p_\text{z}^\text{ba} (z | b, a) V_b^{\check{\pi}}(b')\}
```

### 2.3.2 Q関数のベルマン方程式
```math
\begin{align}
Q_\text{b}^{\check{\pi}}(b, a) &=  \delta_{\{b' = \Psi(b, a, z)\}}\{g_\text{b}(b, a) + \gamma \Sigma_{z\in\tilde{\mathcal{Z}}} p_\text{z}^\text{ba} (z | b, a) V_b^{\check{\pi}}(b')\} \\
&=  \delta_{\{b' = \Psi(b, a, z)\}}\{g_\text{b}(b, a) + \gamma \Sigma_{a'\in\mathcal{A}}\Sigma_{z\in\tilde{\mathcal{Z}}}p_\text{z}^\text{ba} (z | b, a)\check{\pi}(a'|b') Q_\text{b}^{\check{\pi}}(b', a')\}
\end{align}
```

### 2.3.3 価値関数，Q関数のベルマン最適方程式
```math
\begin{align}
V_\text{b}^* (b) &= \max_{a\in\mathcal{A}}  \delta_{\{b' = \Psi(b, a, z)\}} \{g_\text{b}(b, a) + \gamma \Sigma_{z\in\tilde{\mathcal{Z}}}p_\text{z}^\text{ba} (z | b, a) V_b^* (b')\}\\
Q_\text{b}^*(b, a) &=   \delta_{\{b' = \Psi(b, a, z)\}}\{g_\text{b}(b, a) + \gamma \Sigma_{z\in\tilde{\mathcal{Z}}}p_\text{z}^\text{ba} (z | b, a) \max_{a'\in \mathcal{A}} Q_\text{b}^*(b', a')\}
\end{align}
```

### 2.3.4 Q関数のベルマン最適方程式の行動に対してargmaxを取って最適方策を得る
```math
\begin{align}
\check{\pi}^{d*}(b) &= \text{argmax}_{a\in\mathcal{A}} Q_\text{b}^*(b, a) \\
&= \text{argmax}_{a\in\mathcal{A}}  \delta_{\{b' = \Psi(b, a, z)\}}\{g_\text{b}(b, a) + \gamma \Sigma_{z\in\tilde{\mathcal{Z}}}p_\text{z}^\text{ba} (z | b, a) \max_{a'\in \mathcal{A}} Q_\text{b}^*(b', a')\} \\
&= \text{argmax}_{a\in\mathcal{A}}  \delta_{\{b' = \Psi(b, a, z)\}}\{g_\text{b}(b, a) + \gamma \Sigma_{z\in\tilde{\mathcal{Z}}}p_\text{z}^\text{ba} (z | b, a) V_\text{b}^*(b')\}
\end{align}
```


# おわりに
RLについて学ぶためにMDPやPOMDPを学ぶことになりますが，結局何がいいたかったんだ？わからないところがわからない，，，といったモヤモヤが初学者の頃は付き纏っていました．
同じような悩みを抱える方に少しでも助けになればと思い，かなり端折りながら整理用の資料として作成しました．
RLはシンプルにエージェントの訓練のみならず，近年ではRLHF（RL from Human Feedback）でも注目を集めており，非常に魅力的な分野になっています．
素晴らしい近年の発展を理解するための後押しができれば幸いです．

解釈が間違っていたり，ゼロつく4や森村強化学習についてわからないこと（行間が広くて理解が難しい）等ありましたら，気軽にコメントしていただければと思います．