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

部分的に観測可能なマルコフ決定プロセス( POMDP ) は、マルコフ決定プロセス(MDP)の一般化です。POMDP は、システム ダイナミクスが MDP によって決定されるが、エージェントが基礎状態を直接観測できないと想定されるエージェント決定プロセスをモデル化します。代わりに、センサー モデル (基礎状態を与えられたさまざまな観測の確率分布) と基礎 MDP を維持する必要があります。基礎状態をアクションにマッピングする MDP のポリシー関数とは異なり、POMDP のポリシーは、観測 (または信念状態) の履歴からアクションへのマッピングです。

POMDP フレームワークは、さまざまな現実世界の順次決定プロセスをモデル化できるほど汎用的です。アプリケーションには、ロボットのナビゲーション問題、機械のメンテナンス、一般的な不確実性下での計画などがあります。不完全情報によるマルコフ決定プロセスの一般的なフレームワークは、1965 年にカール・ヨハン・オーストロムによって離散状態空間の場合に説明され^{[1] 、}オペレーションズ リサーチコミュニティでさらに研究され、POMDP という頭字語が作られました。その後、レスリー・P・ケルブリングとマイケル・L・リットマンによって人工知能と自動計画の問題に適応されました^[2]。

POMDP の正確な解は、世界の状態における各可能な信念に対する最適なアクションを生み出します。最適なアクションは、おそらく無限の期間にわたってエージェントの期待報酬を最大化 (またはコストを最小化) します。最適なアクションのシーケンスは、エージェントが環境と対話するための最適なポリシーとして知られています。

離散時間POMDPはエージェントとその環境の関係をモデル化する。正式には、POMDPは7組の組であり、 ${\displaystyle (S,A,T,R,\Omega ,O,\gamma )}$

• ${\displaystyle S}$状態の集合であり、
• ${\displaystyle A}$一連の行動である。
• ${\displaystyle T}$状態間の条件付き遷移確率の集合である。
• ${\displaystyle R:S\times A\to \mathbb {R} }$報酬関数です。
• ${\displaystyle \オメガ}$観察の集合であり、
• ${\displaystyle O}$は条件付き観測確率の集合であり、
• ${\displaystyle \gamma \in [0,1)}$割引率です。

各期間において、環境はある状態 にあります。エージェントはアクション を実行し、これにより、環境は確率 で状態 に遷移します。同時に、エージェントは、環境の新しい状態と、実行したばかりのアクション に依存する確率(またはセンサー モデルに依存する確率) で観測値を受け取ります。最後に、エージェントはに等しい報酬を受け取ります。その後、このプロセスが繰り返されます。目標は、エージェントが各タイム ステップで、期待される将来の割引報酬 を最大化するアクションを選択することです。ここで、 は時刻 で獲得した報酬です。割引係数は、より遠い報酬よりも即時の報酬がどの程度優先されるかを決定します。エージェントが、どのアクションが最大の期待即時報酬をもたらすかだけを気にする場合、エージェントが将来の報酬の期待合計を最大化することに関心がある場合。 ${\displaystyle s\in S}$${\displaystyle a\in A}$${\displaystyle s'}$${\displaystyle T(s'\mid s,a)}$${\displaystyle o\in \Omega }$${\displaystyle s'}$${\displaystyle a}$${\displaystyle O(o\mid s',a)}$${\displaystyle O(o\mid s')}$${\displaystyle r}$${\displaystyle R(s,a)}$${\displaystyle E\left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right]}$${\displaystyle r_{t}}$${\displaystyle t}$${\displaystyle \gamma}$${\displaystyle \gamma =0}$${\displaystyle \gamma \rightarrow 1}$

エージェントは環境の状態を直接観察しないため、環境の真の状態が不確実な状況で決定を下す必要があります。ただし、環境と対話して観察結果を受け取ることで、エージェントは現在の状態の確率分布を更新し、真の状態に対する確信を更新できます。この特性の結果、最適な動作には、エージェントの現在の状態に対する推定値を向上させるためだけに実行される (情報収集) アクションが含まれることが多く、それによってエージェントは将来的により良い決定を下すことができます。

上記の定義をマルコフ決定過程の定義と比較すると有益です。エージェントは常に環境の現在の状態を確実に知っているため、MDP には観測セットは含まれません。あるいは、観測セットを状態セットと等しくなるように設定し、観測条件付き確率を定義して真の状態に対応する観測を決定論的に選択することで、MDP を POMDP として再定式化できます。

アクションを実行してを観察した後、エージェントは環境がどのような状態であるか（またはそうでないか）についての信念を更新する必要があります。状態はマルコフ的であるため（仮定により）、状態に対する信念を維持するには、以前の信念状態、実行されたアクション、および現在の観察についての知識のみが必要です。この操作は で示されます。以下では、この信念の更新がどのように計算されるかを説明します。 ${\displaystyle a}$${\displaystyle o}$${\displaystyle b'=\tau (b,a,o)}$

に到達した後、エージェントは確率 で を観察します。を状態空間上の確率分布とします。は環境が状態 にある確率を表します。 が与えられた場合、アクションを起こしてを観察した後、 ${\displaystyle s'}$${\displaystyle o\in \Omega }$${\displaystyle O(o\mid s',a)}$${\displaystyle b}$${\displaystyle S}$${\displaystyle b(s)}$${\displaystyle s}$${\displaystyle b(s)}$${\displaystyle a}$${\displaystyle o}$

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

ここでは の正規化定数です。 ${\displaystyle \eta =1/\Pr(o\mid b,a)}$${\displaystyle \Pr(o\mid b,a)=\sum _{s'\in S}O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)}$

マルコフの信念状態により、POMDP は、すべての信念が状態であるマルコフ決定プロセスとして定式化できます。したがって、結果として得られる信念 MDP は、連続状態空間で定義されます (「元の」POMDP の状態の数が有限であっても、状態 () 上の確率分布の数は無限であるため、信念状態 () は無限にあります)。^[2]${\displaystyle B}$${\displaystyle S}$

正式には、信念MDPは、次の組として定義される。 ${\displaystyle (B,A,\tau,r,\gamma)}$

• ${\displaystyle B}$はPOMDP状態上の信念状態の集合であり、
• ${\displaystyle A}$は、元のPOMDPと同じ有限のアクションセットです。
• ${\displaystyle \tau}$は信念状態遷移関数であり、
• ${\displaystyle r:B\times A\to \mathbb {R} }$信念状態に対する報酬関数である。
• ${\displaystyle \gamma}$は、元の POMDPの割引係数に等しいです。${\displaystyle \gamma}$

これらは、元のPOMDPから派生する必要があります。 ${\displaystyle \tau}$${\displaystyle r}$${\displaystyle \tau}$

${\displaystyle \tau (b,a,b')=\sum _{o\in \Omega }\Pr(b'|b,a,o)\Pr(o|a,b),}$

ここで、前のセクションで導出された値であり、 ${\displaystyle \Pr(o|a,b)}$

${\displaystyle Pr(b'|b,a,o)={\begin{cases}1&{\text{引数 }}b,a,o{\text{ による信念更新が }}b' を返す場合\\0&{\text{それ以外の場合 }}\end{cases}}.}$

信念MDP報酬関数（）は、信念状態分布上のPOMDP報酬関数からの期待報酬である。 ${\displaystyle r}$

${\displaystyle r(b,a)=\sum _{s\in S}b(s)R(s,a)}$。

エージェントはいつでも自分の信念を知っており、さらには信念 MDP の状態も知っているため、信念 MDP は部分的にしか観測できません。

「元の」POMDP（各アクションは 1 つの状態からのみ使用可能）とは異なり、対応する Belief MDP では、（ほぼ）常に、任意の（元の）状態にあると信じる可能性があるので、すべての信念状態ですべてのアクションが許可されます。そのため、は任意の信念に対するアクションを指定します。 ${\displaystyle \pi}$${\displaystyle a=\pi (b)}$${\displaystyle b}$

ここでの目的は、無限の期間にわたって期待される合計割引報酬を最大化することであると想定されています。 がコストを定義する場合、目的は期待コストの最小化になります。 ${\displaystyle R}$

信念から始まる政策の期待報酬は次のように定義される。 ${\displaystyle \pi}$${\displaystyle b_{0}}$

${\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}}$

で表される最適ポリシーは、各信念状態に対して最高の期待報酬値を生み出し、最適値関数 によって簡潔に表されます。この値関数は、ベルマン最適性方程式の解です。 ${\displaystyle \pi^{*}}$${\displaystyle V^{*}}$

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

有限時間POMDPの場合、最適値関数は区分線形かつ凸である。^[3]これは有限ベクトル集合として表すことができる。無限時間定式化では、有限ベクトル集合は任意に近い近似値を持つことができ、その形状は凸形状のままである。値反復は動的計画法更新を適用して、最適値関数に収束するまで値を徐々に改善し、区分線形性と凸性を維持する。^[4]値を改善することで、ポリシーは暗黙的に改善される。ポリシー反復と呼ばれる別の動的計画法は、代わりにポリシーを明示的に表現して改善する。^{[5] [6]}${\displaystyle V^{*}}$${\displaystyle \epsilon }$

実際には、POMDP を正確に解くのは計算上困難であることが多い。この困難さは、次元の呪いまたは履歴の呪い (最適なポリシーがアクションと観察の履歴全体に依存する可能性があるという事実) によることが多い。これらの問題に対処するために、コンピューター科学者は POMDP のソリューションを近似する方法を開発してきた。これらのソリューションは通常、限られた数のパラメーターで問題またはソリューションを近似しようとしたり、^[7]オンラインで信念空間の小さな部分のみを計画したり、アクションと観察の履歴をコンパクトに要約したりします。

グリッドベースのアルゴリズム^[8]は、近似解法の 1 つの手法です。このアプローチでは、価値関数は信念空間内のポイント セットに対して計算され、補間を使用して、グリッド ポイント セットに含まれない他の信念状態が発生した場合に最適なアクションを決定します。最近の研究では、サンプリング手法、一般化手法、問題構造の活用が活用され、POMDP 解決が数百万の状態を持つ大規模な領域に拡張されています。^{[9] [10]}たとえば、適応グリッドとポイントベースの方法では、ランダムに到達可能な信念ポイントをサンプリングして、計画を信念空間内の関連領域に制限します。^{[11] [12]} PCA を 使用した次元削減も検討されています。^[13]

オンライン計画アルゴリズムは、新しい観測が受信されるたびに現在の信念に対する新しいポリシーを構築することで、大規模な POMDP に近づきます。このようなポリシーでは、現在の信念から到達可能な将来の信念のみを考慮する必要がありますが、これは完全な信念空間のごく一部にすぎません。このファミリーには、モンテカルロ木探索^[14]とヒューリスティック探索^[15]のバリエーションが含まれます。MDPと同様に、任意の最適に近いポリシーを見つけ、状態と観測空間のサイズに直接的な計算量依存を持たないオンラインアルゴリズムを構築できます。^[16]

POMDPを解くための別の近似解法は、現在のタイムステップまでの過去の観測、行動、報酬の履歴（のサブセット）を疑似状態として使用することに依存しています。これらの疑似状態に基づいてMDPを解くための通常の手法を使用できます（例：Q学習）。理想的には、疑似状態には、（バイアスを減らすために）履歴全体から最も重要な情報を含め、（過剰適合を減らすために）可能な限り圧縮する必要があります。^[17]

POMDP における計画は一般に決定不可能である。しかし、いくつかの設定は決定可能であることが確認されている (以下に転載した^[18]の表 2 を参照)。さまざまな目的が検討されている。Büchi 目的は、Büchi オートマトンによって定義される。到達可能性は、Büchi 条件の例である (たとえば、すべてのロボットがホーム状態にある良好な状態に到達する)。coBüchi 目的は、特定の Büchi 条件を満たさないトレースに対応する (たとえば、一部のロボットが死亡する悪い状態に到達しない)。パリティ目的は、パリティ ゲームによって定義される。これにより、10 タイムステップごとに良好な状態に到達するなどの複雑な目的を定義できる。目的は次のように満たすことができる:

• ほぼ確実に、つまり目的を満たす確率は 1 です。
• 正、つまり目的を達成する確率は 0 より確実に大きい。
• 定量的、つまり目的を満たす確率が所定のしきい値よりも大きい。

また、エージェントが有限状態マシンである有限メモリのケースと、エージェントが無限メモリを持つ一般的なケースも検討します。

POMDPは、さまざまな現実世界の問題をモデル化するために使用できます。注目すべき応用例としては、虚血性心疾患患者の管理におけるPOMDPの使用、^[19]、認知症患者のための支援技術^{[9] [10]、}絶滅の危機に瀕しており発見が難しいスマトラトラの保護^[20]、航空機の衝突回避^{[21]などがあります。}

一つの応用例は、教育事例である泣いている赤ちゃんの問題である。これは、赤ちゃんが泣いているかどうかの観察に基づいて、親が赤ちゃんに食事を与えるかどうかを順番に決定する必要があるが、これは実際の赤ちゃんの空腹状態を不完全に表している。^{[22] [23]}

• APPL、高速ポイントベースPOMDPソルバー
• 分岐制限法を用いた有限状態コントローラ 制限されたサイズのポリシーに対する正確な POMDP ソルバー
• pomdp: 部分的に観測可能なマルコフ決定プロセスのインフラストラクチャ (POMDP)。Tony Cassandra の pomdp-solve プログラムへのインターフェイスを含む R パッケージ。
• POMDPs.jl は、さまざまなソルバーを使用してJuliaおよび Pythonで MDP と POMDP を定義および解決するためのインターフェースです。
• pyPOMDP、Oliver Stollmann と Bastian Migge による Python 用の (PO)MDP ツールボックス (シミュレーター、ソルバー、学習器、ファイル リーダー)
• zmdp、Trey Smith による POMDP ソルバー