部分観測マルコフ決定過程
すべての状態に関する信念の値を状態とみなすことで、POMDP はマルコフ決定過程として計算することができる。 このようにして得られた MDP を信念空間における MDP (belief MDP) と呼ぶ。 POMDP に無限個の信念が存在することから、belief MDP は連続状態空間上に定義される。
belief MDP は組 ⟨ B , A , τ , r ⟩ {\displaystyle \langle B,A,\tau ,r\rangle } で定義される.ここで
B = { ( b ( s ) ) s ∈ S ∈ [ 0 , 1 ] N ∣ ∑ s b ( s ) = 1 } {\textstyle {\mathcal {B}}=\{(b(s))_{s\in {\mathcal {S}}}\in [0,1]^{N}\mid \sum _{s}b(s)=1\}} : 信念状態の集合
A {\textstyle {\mathcal {A}}} : 元のPDMDP と同じ行動の集合
τ : B × A × B → [ 0 , 1 ] {\displaystyle \tau :{\mathcal {B}}\times {\mathcal {A}}\times {\mathcal {B}}\to [0,1]} : 信念状態空間における状態遷移確率
r : B × A → R {\displaystyle r:{\mathcal {B}}\times A\to \mathbb {R} } : 信念状態空間における報酬関数
最適政策 (optimal policy) は π ∗ {\displaystyle \pi ^{*}} で表され,任意の信念状態において期待報酬の最大値(最適価値関数 (optimal value function) V ∗ {\displaystyle V^{*}} で表す)を与える. 価値関数はベルマンの最適性方程式の解である:
有限ホライズンの POMDP では,最適な価値関数は凸な区分線形関数となる . これは有限個のベクトルの集合で表現することが出来る. 無限ホライズンでは,有限次元ベクトルを用いることで凸性を維持するよう任意に綿密に V ∗ {\displaystyle V^{*}} を近似することができる.
価値反復法は動的計画法を用いて,区分線形性と収束性は区分線形性と凸性を維持しながら,収束するまで価値関数の値を更新する. 価値関数の値を更新することで,政策は改善される. もう一つの動的計画法に基づくテクニックは政策反復法と呼ばれ,これは政策を明示的に更新する.
環境の状態を直接観測することが出来ないため,エージェントは環境の状態の真値が持つ不確実性の下で意思決定を行う必要がある. しかし,環境と相互作用し観測を受け取るため,エージェントは現在状態の確率分布を更新することで真の状態の信念を更新する. この属性による結果として,エージェントの持つ現在状態の推定値を更新するため,最適な振舞いはしばしば直接取得・集計した行動の情報を含み,それにより,未来のよりよい意思決定を可能にする.
上の定義とマルコフ決定過程の定義を比較することは有益である. エージェントは現在の環境の状態を知ることが出来るため,MDP は観測の集合を持たない. 一方MDP は,観測の集合を状態の集合,観測の確率を真の状態を決定的に選ぶよう設定することで,POMDP として定式化し直すことが出来る.