部分観測マルコフ決定過程

部分観測マルコフ決定過程(ぶぶんかんそくマルコフけっていかてい、英: partially observable Markov decision process; POMDP)はマルコフ決定過程 (MDP) の一般化であり，状態を直接観測できないような意思決定過程におけるモデル化の枠組みを与える．

POMDP は実世界におけるあらゆる逐次的な意思決定過程をモデル化するのに十分であり，ロボットのナビゲーションや機械整備 (machine maintenance)，および不確実な状況下でのプランニングなどに応用されている． POMDP はオペレーションズリサーチを起源とし，のちに人工知能や自動計画のコミュニティに引き継がれた．

定義

形式的定義

POMDPは 組 $\langle {\mathcal {S}},{\mathcal {A}},T,R,\Omega ,O\rangle$ で定義される:

• ${\mathcal {S}}=\{s^{1},\ldots ,s^{N}\}$ : 状態 (state) の有限集合
• ${\mathcal {A}}=\{a^{1},\ldots ,a^{K}\}$ : 行動 (action) の有限集合
• $T:{\mathcal {S}}\times {\mathcal {A}}\times {\mathcal {S}}\to [0,1]$ : 条件付き状態遷移確率
• $R:{\mathcal {S}}\times {\mathcal {A}}\to \mathbb {R}$ : 報酬関数 (reward function)
• $\Omega$ : 観測の集合
• $O:{\mathcal {S}}\times {\mathcal {A}}\times \Omega \to [0,1]$ : 条件付き観測確率の集合

各時刻において，環境はある状態  $s\in S$  にあるエージェントは行動 $a\in A$ をとり，それに影響を受け環境は状態 $s'$ に確率 $T(s'\mid s,a)$ で遷移する． 同時刻において，エージェントは遷移後の状態に依存し確率分布 $O(o|s,a)$ に従う観測 $o\in \Omega$ を得る． 最後に，エージェントは環境から報酬 $R(s,a)$ を受け取る． 形式的には、POMDP は隠れマルコフモデル (HMM) に行動および行動を変更する動機を与える報酬を付与したものと解釈することができる。

問題設定

POMDP の基本的な問題設定における目標 (goal) は、各時刻においてエージェントが受け取る未来の割引された報酬の期待値 ${\textstyle E\left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right]}$の最大化である． ここで $r_{t}$ はエージェントが時刻 $t$ に受け取る即時報酬 (immediate reward) である。 また、$\gamma \in [0,1]$ は割引因子 (discount factor) であり、他の遠い報酬と比べて即時報酬をどの程度好むかを規定する． $\gamma =0$ のとき，エージェントは即時に得られる報酬の期待値の最大化のみを考慮し，$\gamma =1$ のとき未来の報酬の累積和の期待値の最大化を考慮する．

議論

環境の状態を直接観測することが出来ないため，エージェントは環境の状態の真値が持つ不確実性の下で意思決定を行う必要がある． しかし，環境と相互作用し観測を受け取るため，エージェントは現在状態の確率分布を更新することで真の状態の信念を更新する． この属性による結果として，エージェントの持つ現在状態の推定値を更新するため，最適な振舞いはしばしば直接取得・集計した行動の情報を含み，それにより，未来のよりよい意思決定を可能にする．

上の定義とマルコフ決定過程の定義を比較することは有益である． エージェントは現在の環境の状態を知ることが出来るため，MDP は観測の集合を持たない． 一方MDP は，観測の集合を状態の集合，観測の確率を真の状態を決定的に選ぶよう設定することで，POMDP として定式化し直すことが出来る．

信念の更新

環境の状態に関する情報を得るため、エージェントは行動 $a$ と 観測 $o$ に基づき自身のもつ状態の信念 (belief) を更新する必要がある． ここで信念 $b$ は状態空間 ${\mathcal {S}}$ 上の確率分布として与えられる。 $b(s)\in [0,1]$ は環境が状態 $s\in {\mathcal {S}}$ にいる確率を表す．

マルコフ性のおかげで，すべての状態にわたる信念は直前の状態の信念，取った行動，そして現在の観測のみから修正することが出来る． 現在ステップにおける信念 $b:{\mathcal {S}}\to [0,1]$ ，および行動 $a$ と 観測 $o$ が得られた後，信念は次のように更新される:

$$b'(s')=\eta \;O(o\mid s',a)\sum _{s\in {\mathcal {S}}}T(s'\mid s,a)b(s)\quad \forall s'\in {\mathcal {S}}$$

ここで $1/\Pr(o|b,a)$ は正規化定数であり，$\Pr(o|b,a)$ は次式で与えられる．

$$\Pr(o\mid b,a)=\sum _{s'\in {\mathcal {S}}}O(o\mid s',a)\sum _{s\in {\mathcal {S}}}T(s'\mid s,a)b(s)$$

.

Belief MDP

すべての状態に関する信念の値を状態とみなすことで、POMDP はマルコフ決定過程として計算することができる。 このようにして得られた MDP を信念空間における MDP (belief MDP) と呼ぶ。 POMDP に無限個の信念が存在することから、belief MDP は連続状態空間上に定義される。

belief MDP は組 $\langle B,A,\tau ,r\rangle$ で定義される．ここで

• ${\textstyle {\mathcal {B}}=\{(b(s))_{s\in {\mathcal {S}}}\in [0,1]^{N}\mid \sum _{s}b(s)=1\}}$ : 信念状態の集合
• ${\textstyle {\mathcal {A}}}$ : 元のPDMDP と同じ行動の集合
• $\tau :{\mathcal {B}}\times {\mathcal {A}}\times {\mathcal {B}}\to [0,1]$ : 信念状態空間における状態遷移確率
• $r:{\mathcal {B}}\times A\to \mathbb {R}$ : 信念状態空間における報酬関数

このうち， $\tau$ と $r$ は元のPOMDPからそれぞれ次のように導出される:

$${\begin{aligned}\tau (b,a,b')&=\sum _{o\in \Omega }\Pr(b'|b,a,o)\Pr(o|a,b)\\r(b,a)&=\sum _{s\in S}b(s)R(s,a)\end{aligned}}$$

ここで $\Pr(o|a,b)$ は前節で導出した値であり，$\Pr(b'|b,a,o)$ は次のように与えられる．

$\Pr(b'|b,a,o)={\begin{cases}1&{\text{if the belief update with arguments }}b,a,o{\text{ returns }}b'\\0&{\text{otherwise }}\end{cases}}.$

エージェントにとって自身の信念（または belief MDP における状態の値）は既知であるため、信念 MDP はもはや部分観測でないことに注意されたい。

たいていの場合、（元のモデルにおける）各状態への信念はある程度の値をもっているため、 "元の" MDP である行動が特定の状態からしか利用できないような状況であっても、対応する belief MDP ではその行動をすべての状態で取ることができる。

政策関数・価値関数

任意の信念 $b$ に対する特定の行動 $a=\pi (b)$ を$\pi$ と表す。 ここで目的関数は無限ホライズンの期待割引報酬和 (expected total discounted reward) と仮定する．$R$ がコストとして定義される場合，目的関数は期待コストの最小化となる．

信念の初期値を $b_{0}$ としたときの政策 $\pi$ に対する期待報酬 (expected reward) は次のように定義される:

$$V^{\pi }(b_{0})=\sum _{t=0}^{\infty }\gamma ^{t}r(b_{t},a_{t})=\sum _{t=0}^{\infty }\gamma ^{t}E{\Bigl [}R(s_{t},a_{t})\mid b_{0},\pi {\Bigr ]}$$

ここで $\gamma <1$ は割引因子である． 最適な政策 $\pi ^{*}$は長期的な報酬の最適化により次のように得られる:

$$\pi ^{*}={\underset {\pi }{\mbox{argmax}}}\ V^{\pi }(b_{0})$$

ここで $b_{0}$ は初期信念である．

最適政策 (optimal policy) は $\pi ^{*}$ で表され，任意の信念状態において期待報酬の最大値（最適価値関数 (optimal value function) $V^{*}$ で表す）を与える． 価値関数はベルマンの最適性方程式の解である:

$$V^{*}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }O(o\mid b,a)V^{*}(\tau (b,a,o)){\Bigr ]}$$

有限ホライズンの POMDP では，最適な価値関数は凸な区分線形関数となる ． これは有限個のベクトルの集合で表現することが出来る． 無限ホライズンでは，有限次元ベクトルを用いることで凸性を維持するよう任意に綿密に $V^{*}$ を近似することができる．

価値反復法は動的計画法を用いて，区分線形性と収束性は区分線形性と凸性を維持しながら，収束するまで価値関数の値を更新する． 価値関数の値を更新することで，政策は改善される． もう一つの動的計画法に基づくテクニックは政策反復法と呼ばれ，これは政策を明示的に更新する．

POMDP の近似解法

組み合わせ爆発の問題をはらむため，POMDP の厳密解を求めることは実用上困難であることが多い． そのため，POMDP の解を近似する手法が複数提案されている． グリッドベースのアルゴリズムでは価値関数を信念空間内の点集合として計算し，最適行動を決定するための計算など，グリッドの点集合に含まれない信念状態の値が必要な場合は補完する． より最近の研究では，サンプリングや一般化 (genelization technique)，および問題の構造を利用する手法などが用いられ，膨大な状態を伴うより大きい領域を扱うよう POMDP を拡張する． 例えば，点ベースの手法では，信念空間において関連する領域への計画を拘束するため，到達可能な信念をランダムにサンプルする． 主成分分析を用いた次元削減も調べられている．

POMDP の応用

POMDP は実世界の多くの種類の問題に用いることが出来る． 注目すべき応用には，虚血性心疾患の患者の特別療法に対する POMDP の活用，痴呆患者の支援技術， 絶滅の危機に瀕し発見の難しいスマトラトラの保護，および航空機の衝突回避が含まれる．

参考文献

• Kaelbling, L.P.; Littman, M.L.; Cassandra, A.R. (1998). “Planning and acting in partially observable stochastic domains”. Artificial Intelligence Journal 101: 99–134. doi:10.1016/S0004-3702(98)00023-X. 

• Sondik, E.J. (1971). The optimal control of partially observable Markov processes (PhD thesis). Stanford University.

• Smallwood, R.D.; Sondik, E.J. (1973). “The optimal control of partially observable Markov decision processes over a finite horizon”. Operations Research 21 (5): 1071–88. doi:10.1287/opre.21.5.1071. 

• Sondik, E.J. (1978). “The optimal control of partially observable Markov processes over the infinite horizon: discounted cost”. Operations Research 26 (2): 282–304. doi:10.1287/opre.26.2.282. 

• Hansen, E. (1998). "Solving POMDPs by searching in policy space". Proceedings of the Fourteenth International Conference on Uncertainty In Artificial Intelligence (UAI-98).

• Hauskrecht, M. (2000a). “Value function approximations for partially observable Markov decision processes”. Journal of Artificial Intelligence Research 13: 33–94. doi:10.1613/jair.678. 

• Lovejoy, W. (1991). “Computationally feasible bounds for partially observed Markov decision processes”. Operations Research 39: 162–175. doi:10.1287/opre.39.1.162. 

• Jesse Hoey; Axel von Bertoldi; Pascal Poupart; Alex Mihailidis (2007). "Assisting Persons with Dementia during Handwashing Using a Partially Observable Markov Decision Process". Proc. International Conference on Computer Vision Systems (ICVS). doi:10.2390/biecoll-icvs2007-89。

• Jesse Hoey; Pascal Poupart; Axel von Bertoldi; Tammy Craig; Craig Boutilier; Alex Mihailidis. (2010). “Automated Handwashing Assistance For Persons With Dementia Using Video and a Partially Observable Markov Decision Process”. Computer Vision and Image Understanding (CVIU) 114 (5). doi:10.1016/j.cviu.2009.06.008. 

• Pineau, J., Gordon, G., Thrun, S. (August 2003). "Point-based value iteration: An anytime algorithm for POMDPs". International Joint Conference on Artificial Intelligence (IJCAI). Acapulco, Mexico. pp. 1025–32.

• Roy, Nicholas; Gordon, Geoffrey (2003). “Exponential Family PCA for Belief Compression in POMDPs”. Advances in Neural Information Processing Systems 

• Hauskrecht, M. , Fraser, H. (2000b). “Planning treatment of ischemic heart disease with partially observable Markov decision processes”. Artificial Intelligence in Medicine 18 (3): 221–244. doi:10.1016/S0933-3657(99)00042-1. 

• Chadès, I., McDonald-Madden, E., McCarthy, M.A., Wintle, B., Linkie, M., Possingham, H.P. (16 September 2008). “When to stop managing or surveying cryptic threatened species”. Proc. Natl. Acad. Sci. U.S.A. 105 (37): 13936–40. Bibcode: 2008PNAS..10513936C. doi:10.1073/pnas.0805265105. PMC 2544557. PMID 18779594. http://www.pnas.org/content/105/37/13936.abstract. 

• Kochenderfer, Mykel J. (2015). “Optimized Airborne Collision Avoidance”. Decision Making Under Uncertainty. The MIT Press 

外部リンク

• Tony Cassandra's POMDP pages with a tutorial, examples of problems modeled as POMDPs, and software for solving them.
• zmdp, a POMDP solver by Trey Smith
• APPL, a fast point-based POMDP solver
• SPUDD, a factored structured (PO)MDP solver that uses algebraic decision diagrams (ADDs).
• pyPOMDP, a (PO)MDP toolbox (simulator, solver, learner, file reader) for Python by Oliver Stollmann and Bastian Migge
• Finite-state Controllers using Branch-and-Bound An Exact POMDP Solver for Policies of a Bounded Size