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

部分観測マルコフ決定過程(ぶぶんかんそくマルコフけっていかてい、)はマルコフ決定過程 (MDP) の一般化であり，状態を直接観測できないような意思決定過程におけるモデル化の枠組みを与える．
POMDP は実世界におけるあらゆる逐次的な意思決定過程をモデル化するのに十分であり，ロボットのナビゲーションや機械整備 (machine maintenance)，および不確実な状況下でのプランニングなどに応用されている．
POMDP はオペレーションズリサーチを起源とし，のちに人工知能や自動計画のコミュニティに引き継がれた．
定義.
形式的定義.
POMDPは 組 formula_1 で定義される:
各時刻において，環境はある状態  formula_8  にあるエージェントは行動 formula_9 をとり，それに影響を受け環境は状態 formula_10 に確率 formula_11 で遷移する．
同時刻において，エージェントは遷移後の状態に依存し確率分布 formula_12 に従う観測 formula_13 を得る．
最後に，エージェントは環境から報酬 formula_14 を受け取る．
形式的には、POMDP は隠れマルコフモデル (HMM) に行動および行動を変更する動機を与える報酬を付与したものと解釈することができる。
問題設定.
POMDP の基本的な問題設定における目標 (goal) は、各時刻においてエージェントが受け取る未来の割引された報酬の期待値 formula_15の最大化である．
ここで formula_16 はエージェントが時刻 formula_17 に受け取る即時報酬 (immediate reward) である。
また、formula_18 は割引因子 (discount factor) であり、他の遠い報酬と比べて即時報酬をどの程度好むかを規定する．
formula_19 のとき，エージェントは即時に得られる報酬の期待値の最大化のみを考慮し，formula_20 のとき未来の報酬の累積和の期待値の最大化を考慮する．
議論.
環境の状態を直接観測することが出来ないため，エージェントは環境の状態の真値が持つ不確実性の下で意思決定を行う必要がある．
しかし，環境と相互作用し観測を受け取るため，エージェントは現在状態の確率分布を更新することで真の状態の信念を更新する．
この属性による結果として，エージェントの持つ現在状態の推定値を更新するため，最適な振舞いはしばしば直接取得・集計した行動の情報を含み，それにより，未来のよりよい意思決定を可能にする．
上の定義とマルコフ決定過程の定義を比較することは有益である．
エージェントは現在の環境の状態を知ることが出来るため，MDP は観測の集合を持たない．
一方MDP は，観測の集合を状態の集合，観測の確率を真の状態を決定的に選ぶよう設定することで，POMDP として定式化し直すことが出来る．
信念の更新.
環境の状態に関する情報を得るため、エージェントは行動 formula_21 と 観測 formula_22 に基づき自身のもつ状態の信念 (belief) を更新する必要がある．
ここで信念 formula_23 は状態空間 formula_24 上の確率分布として与えられる。
formula_25 は環境が状態 formula_26 にいる確率を表す．
マルコフ性のおかげで，すべての状態にわたる信念は直前の状態の信念，取った行動，そして現在の観測のみから修正することが出来る．
現在ステップにおける信念 formula_27 ，および行動 formula_21 と 観測 formula_22 が得られた後，信念は次のように更新される:
formula_30
ここで formula_31 は正規化定数であり，formula_32 は次式で与えられる．
formula_33.
Belief MDP.
すべての状態に関する信念の値を状態とみなすことで、POMDP はマルコフ決定過程として計算することができる。
このようにして得られた MDP を信念空間における MDP (belief MDP) と呼ぶ。
POMDP に無限個の信念が存在することから、belief MDP は連続状態空間上に定義される。
belief MDP は組 formula_34 で定義される．ここで
このうち， formula_39 と formula_40 は元のPOMDPからそれぞれ次のように導出される:
formula_41
ここで formula_42 は前節で導出した値であり，formula_43 は次のように与えられる．
formula_44
エージェントにとって自身の信念（または belief MDP における状態の値）は既知であるため、信念 MDP はもはや部分観測でないことに注意されたい。
たいていの場合、（元のモデルにおける）各状態への信念はある程度の値をもっているため、
"元の" MDP である行動が特定の状態からしか利用できないような状況であっても、対応する belief MDP ではその行動をすべての状態で取ることができる。
政策関数・価値関数.
任意の信念 formula_23 に対する特定の行動 formula_46 をformula_47 と表す。
ここで目的関数は無限ホライズンの期待割引報酬和 (expected total discounted reward) と仮定する．formula_48 がコストとして定義される場合，目的関数は期待コストの最小化となる．
信念の初期値を formula_49 としたときの政策 formula_47 に対する期待報酬 (expected reward) は次のように定義される:
formula_51
ここで formula_52 は割引因子である．
最適な政策 formula_53は長期的な報酬の最適化により次のように得られる:
formula_54
ここで formula_49 は初期信念である．
最適政策 (optimal policy) は formula_53 で表され，任意の信念状態において期待報酬の最大値（最適価値関数 (optimal value function) formula_57 で表す）を与える．
価値関数はベルマンの最適性方程式の解である:
formula_58
有限ホライズンの POMDP では，最適な価値関数は凸な区分線形関数となる ．
これは有限個のベクトルの集合で表現することが出来る．
無限ホライズンでは，有限次元ベクトルを用いることで凸性を維持するよう任意に綿密に formula_57 を近似することができる．
価値反復法は動的計画法を用いて，区分線形性と収束性は区分線形性と凸性を維持しながら，収束するまで価値関数の値を更新する．
価値関数の値を更新することで，政策は改善される．
もう一つの動的計画法に基づくテクニックは政策反復法と呼ばれ，これは政策を明示的に更新する．
POMDP の近似解法.
組み合わせ爆発の問題をはらむため，POMDP の厳密解を求めることは実用上困難であることが多い．
そのため，POMDP の解を近似する手法が複数提案されている．
グリッドベースのアルゴリズムでは価値関数を信念空間内の点集合として計算し，最適行動を決定するための計算など，グリッドの点集合に含まれない信念状態の値が必要な場合は補完する．
より最近の研究では，サンプリングや一般化 (genelization technique)，および問題の構造を利用する手法などが用いられ，膨大な状態を伴うより大きい領域を扱うよう POMDP を拡張する．
例えば，点ベースの手法では，信念空間において関連する領域への計画を拘束するため，到達可能な信念をランダムにサンプルする．
主成分分析を用いた次元削減も調べられている．
POMDP の応用.
POMDP は実世界の多くの種類の問題に用いることが出来る．
注目すべき応用には，虚血性心疾患の患者の特別療法に対する POMDP の活用，痴呆患者の支援技術，
絶滅の危機に瀕し発見の難しいスマトラトラの保護，および航空機の衝突回避が含まれる．