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

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

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

定義

→「マルコフ決定過程 § 定義」も参照

POMDP は、マルコフ決定過程に観測を表現するための要素を追加することで定義される^[1]。 まず、マルコフ決定過程は次に挙げる 4 つの要素の組 ${\displaystyle ({\mathcal {S}},{\mathcal {A}},T,R)}$ として定義される。

• ${\displaystyle {\mathcal {S}}}$ は環境のもつ状態 (state) の有限集合であり、状態空間 (state space) とも呼ばれる。
• ${\displaystyle {\mathcal {A}}}$ は意思決定者の取ることが出来る行動 (action) の有限集合である。
• ${\displaystyle T\colon {\mathcal {S}}\times {\mathcal {A}}\times {\mathcal {S}}\to [0,1]}$ は状態遷移関数 (state transition function) と呼ばれ、ある行動のもとでの状態遷移確率 ${\displaystyle T(s_{t},a_{t},s_{t+1})=\Pr(s_{t+1}\mid s_{t},a_{t})}$ を定める。
• ${\displaystyle R\colon {\mathcal {S}}\times {\mathcal {A}}\to \mathbb {R} }$ は報酬関数 (reward function) と呼ばれ、即時報酬の期待値 (expected immediate reward) ${\displaystyle R(s_{t},a_{t})=\mathbb {E} [r_{t+1}\mid s_{t},a_{t}]}$ を定める。

POMDP は、上に加えて次の 2 つを加えた 6 要素の組 ${\displaystyle ({\mathcal {S}},{\mathcal {A}},T,R,\Omega ,O)}$ によって定義される。

• ${\displaystyle \Omega }$ は意思決定者が環境から受け取る可能性のある観測 (observation) の有限集合である。
• ${\displaystyle O\colon {\mathcal {S}}\times {\mathcal {A}}\times \Omega \to [0,1]}$ は観測の条件付き確率分布 ${\displaystyle O(s_{t+1},a_{t},o_{t+1})=\Pr(o_{t+1}\mid s_{t+1},a_{t})}$ を定める。

形式的には、POMDP は隠れマルコフモデルに行動、および（行動を変更する動機を与える）報酬を付与したものと解釈することができる。

Belief MDP

信念状態

MDP とは異なり、POMDP による問題設定では環境の状態を直接取得することが出来ない。 したがって、方策を定めるために意思決定者は自身が過去に取った行動および環境から受け取った観測の履歴をもとに状態を推定する必要がある。 この状態の推定値は一般に状態空間 ${\displaystyle {\mathcal {S}}}$ 上の（主観）確率分布で記述され、信念状態 (belief state) と呼ばれる。 具体的には、ある時刻 ${\displaystyle t}$ における信念状態 ${\displaystyle b_{t}}$ は、初期時点における信念の値 ${\displaystyle b_{0}}$ と過去の行動と観測の履歴 ${\displaystyle {\mathcal {H}}}$ が与えられたもとでの条件付き確率分布 ${\textstyle b_{t}(s)=\Pr(S_{t}=s\mid b_{0},{\mathcal {H}})}$ である。

信念の更新

モデルのマルコフ性により、信念状態は直前における値と、直近に取った行動と観測の値のみから修正することが出来る。 いま、ある時刻 ${\displaystyle t}$ における信念状態 ${\displaystyle b_{t}}$ に対し意思決定者が行動 ${\displaystyle a_{t}}$ を選択し、その結果として観測値 ${\displaystyle o_{t+1}}$ が得られたとする。 このとき、次ステップでの信念状態 ${\displaystyle b_{t+1}(s_{t+1})}$ の更新式は次のように記述される:

$${\displaystyle {\begin{aligned}b_{t+1}(s_{t+1})&={\frac {\Pr(o_{t+1}\mid b_{t},a_{t},s_{t+1})\times \Pr(s_{t+1}\mid b_{t},a_{t})}{\Pr(o_{t+1}\mid b_{t},a_{t})}}\\&=\eta \cdot O(s_{t+1},a_{t},o_{t+1})\sum _{s\in {\mathcal {S}}}T(s_{t},a_{t},s_{t+1})b_{t}(s_{t})\end{aligned}}}$$

(1)

ここで ${\displaystyle \eta =1/\Pr(o_{t+1}\mid a_{t},b_{t})}$ は正規化定数である。確率 ${\displaystyle \Pr(o_{t+1}\mid a_{t},b_{t})}$ は次式で与えられる。 $${\displaystyle \Pr(o_{t+1}\mid b_{t}a_{t})=\sum _{s'\in {\mathcal {S}}}O(s_{t+1},a_{t},o_{t+1})\sum _{s\in {\mathcal {S}}}T(s,a,s)b_{t}(s)}$$

Belief MDP の定式化

式 (1) は現在取る行動 ${\displaystyle a_{t}}$ と得られる観測 ${\displaystyle o_{t+1}}$ が既知の場合における信念状態 ${\displaystyle b_{t}}$ から ${\displaystyle b_{t+1}}$ への（決定論的な）遷移関係と解釈することが出来る。 すなわち、信念状態を介することで POMDP を（部分観測でない）マルコフ決定過程として扱うことが出来る。 このようにして構成される MDP のことを belief MDP と呼ぶ。 形式的には、belief MDP は次の要素からなる組 ${\displaystyle ({\mathcal {B}},{\mathcal {A}},\tau ,r)}$ として定義される:

• ${\textstyle {\mathcal {B}}=\{b\colon S\to [0,1]\mid \sum _{s\in {\mathcal {S}}}b(s)=1\}}$ : 信念状態が取り得る値の集合
• ${\displaystyle {\mathcal {A}}}$ : belief MDP における行動集合（元々の POMDP と共通）
• ${\displaystyle \tau \colon {\mathcal {B}}\times {\mathcal {A}}\times {\mathcal {B}}\to [0,1]}$ : 信念状態空間における状態遷移確率
• ${\displaystyle r\colon {\mathcal {B}}\times {\mathcal {A}}\to \mathbb {R} }$ : 信念状態空間における報酬関数

ここで ${\displaystyle \tau }$ および ${\displaystyle r}$ はそれぞれ次のように求められる。 $${\displaystyle {\begin{aligned}\tau (b_{t},a_{t},b_{t+1})&=\sum _{o_{t+1}\in \Omega }\Pr(b_{t+1}\mid b_{t},a_{t},o_{t+1})\Pr(o_{t+1}\mid b_{t},a_{t})\\r(b_{t},a_{t})&=\sum _{s_{t}\in {\mathcal {S}}}b_{t}(s_{t})R(s_{t},a_{t})\\\end{aligned}}}$$ ただし、${\displaystyle \Pr(b_{t+1}\mid b_{t},a_{t},o_{t+1})}$ は ${\displaystyle b_{t+1}}$ が ${\displaystyle b_{t},a_{t},o_{t+1}}$ をもとに式 (1) によって得られる値の場合 1 を、それ以外のとき 0 を取るように定められる。

方策関数・価値関数

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

信念の初期値を ${\displaystyle b_{0}}$ としたときの方策 ${\displaystyle \pi }$ に対する期待報酬 (expected reward) は次のように定義される: $${\displaystyle 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 ]}}$$ ここで ${\displaystyle \gamma <1}$ は割引因子である。 最適な方策 ${\displaystyle \pi ^{*}}$は長期的な報酬の最適化により次のように得られる:

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

ここで ${\displaystyle b_{0}}$ は初期信念である。

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

$${\displaystyle 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 では、最適な価値関数は凸な区分線形関数となる^[2] 。 これは有限個のベクトルの集合で表現することが出来る。 無限ホライズンでは、有限次元ベクトルを用いることで凸性を維持するよう任意に綿密に ${\displaystyle V^{*}}$ を近似することができる^[3]。

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

POMDP の近似解法

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

POMDP の応用

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

参考文献

1. Kaelbling 1998.
2. Sondik 1971.
3. Sondik 1973.
4. Sondik 1978.
5. Hansen 1998.
6. Hauskrecht 2000a.
7. Lovejoy 1991.
8. Hoey 2007.
9. ^ Hoey 2010.
10. Pineau 2003.
11. Roy 2003.
12. Hauskrecht 2000b.
13. Chadès 2008.
14. Kochenderfer 2015.

• 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