Miyamoto
1 はじめに
部分観測マルコフ決定過程（partially observable Markov decision process）とは、その名の通り、状態の一部しか観測できない状況でのMDPです。
さらに、裏にある「真の状態」はマルコフ性\(^{\ast1}\)を持つのですが、表に見える「観測できる状態」は必ずしもマルコフ性が成り立たないという厄介な性質を持っています。
これは実態のモデル化と、理論的解析の可能性を両立\(^{\ast2}\)できており、非常に技巧的な定式化であるといえます。
本記事では、このPOMDPを測度論と関数解析学の言葉を用いて、数学的解析に向いた形で定義しなおします。独自の定義であり、これまでの記事とは比較にならないくらい数学の難易度が高いです。
しかし、本記事を理解することができれば、現段階で有名な強化学習の全概念をこの応用で理解することができるでしょう。
そんな統一的な定義を目指す一環として、本記事を書きました。
\(^{\ast1}\)簡単に言うと、これからの状態遷移の確率法則は、今の状態のみで決まる、という確率論の概念です。
\(^{\ast2}\)一般には、実態をより詳細に表せるモデルであるほど、複雑になりすぎて理論解析が困難になります。逆に理論解析しやすいモデルは、実態を表現しきれないことが多いです。トレードオフの要素が強いのですが、このPOMDP は強化学習の実応用を考えるにあたって、最適な折り合いポイントにかなり近いモデルではないかと考えております
2 モデルについて
2.1遷移カーネル
二つの可測空間\((S,\mathcal{S}),(T,\mathcal{T}) \)があるとします。
遷移カーネル\(k: S \times \mathcal{T} \rightarrow \mathbb{R}_{+}\)を次の二条件が満たされるように定義します。
(1)
任意の\(B \in \mathcal{T} \)に対して、\(S\)上の実数値関数\(k(\cdot, B)\)は可能
(2)
任意の\(s \in S \)に対して、\(k(s,\cdot)\)は\(T\)上の確立測度
これは、\(s\)が確定すると\(T\)上の分布が確定するような状況に対して用いられます。
強化学習を数学的にきちんと考える状況では必要不可欠な概念です。
2.2 部分観測マルコフ決定過程の定義
通常の強化学習におけるマルコフ決定過程と比較します。
ここでの定義は、種々の書籍とは異なります。
例えば[1] の定義は、\(\mathcal{S},\mathcal{A}\)が有限集合である場合は問題ありませんが、無限集合(例えばDQN を意識した連続濃度) への拡張ができません。
定義1 通常のマルコフ決定過程
- \((\Omega,\mathcal{F}, P)\) : 確率空間
- \(S\) : 状態集合。有限集合か\(\mathbb{R} ^d\)上の単連結コンパクト集合\(^{\ast3}\)
- \(A\) : 行動の集合
- \((S,\mathcal{F}_S)\) : 可測空間。\(S\)が有限集合の時は\(\mathcal{F}_S := 2^S\) で、無限集合の場合はボレル集合族を用いて\(\mathcal{B}(S)\)とします。
- \(p_0\) : 初期状態の確率。\(S\)上の確率測度
- \(p\left(r, s^{\prime} | s, a\right)\) : 遷移カーネル。\(s \in \mathcal{S},a \in \mathcal{A}\)に対して定まる\(\mathbb{R} × \mathcal{S}\)上の確率測度
- \(R(s, a)\) : 報酬の確率変数。\(\mathbb{R}\)上のボレル集合\(K\)に対して、\(R^{-1}(K):=p(K, \cdot | s, a)\)となるような\(s \in S,a \in \mathcal{A}\)に対して定まる\(\mathbb{R}× \mathcal{S}\)上の確率測度\(^{\ast4}\)
この \( \left\{\mathcal{S}, \mathcal{A}, p_{0}, p\right\} \) の組を、マルコフ決定過程と呼びます。
履歴という概念を導入します。これは過去の状況の記録であり、\(\mathcal{F}_t \subset \mathcal{F}\)となる増大情報系です。
(3)
\[ \mathcal{F}_{t}=\sigma\left\{s_{0}, a_{0} . r_{0}, s_{1}, \dots . ., r_{t-1}, s_{t}\right\} \]
各種計算は\(\mathcal{F}-\)適合である必要があります。
\(^{\ast3}\)理論解析の際は、立方体\([0, 1]^d\)と考えてもかまいません。任意の単連結コンパクト集合はこの立方体と同相です。
\(^{\ast4}\)厳密には、確率空間上で定義された\(\mathbb{R} \otimes S\)に値をとる確率変数族\(\{X^{s,a} (\omega) \}_{s,a}\)がまず先に存在し、その逆象として\(p\)が定義されます。非常にややこしいので\(p\)ありきで捉えてもかまいません。\(X\)の射影が\(R\)です。ちなみにPOMDPでのみ登場する\(p^{sa}_o,p^{ba}_z\)も同様に、実際にはまず確率変数族ありきでそれと対応する測度として定義されます。
定義2 部分観測マルコフ決定過程
マルコフ決定過程の定義に加えて
- \(\mathcal{O}\) : 観測集合
- \(p^{sa}_o(\cdot|s,a) \) : 観測確率を表す遷移カーネル。 \(s,a \)に対して定まる\(\mathcal{O} \)上の確率測度。
- \(\mathcal{B}: \mathcal{S} \)上の確率測度の集合。 \(\mathcal{S} \)が無限集合の場合はルベーグ測度と絶対連続なもののみの集合。ノルムは \(L^1 \)で定義する。 \(^{\ast5} \)
- \(z \) : 報酬と観測をまとめた値。つまり \(z \in \mathcal{O} × \mathbb{R} \)
- \(p^{ba}_z(z|b,a) \):遷移カーネル。後述する信念状態 \(b \in \mathcal{B} \)と行動 \(a \in A \)から定まる \(\mathcal{O}×\mathbb{R} \)上の測度
- \(\alpha (s) \) : 状態価値関数。通常のMDPで言うところの \(V \)です。
- \(B(\omega) \) : ボレル集合族を \(\sigma \)加法族とした可測空間 \(\mathcal{B} \)に値をとる確率変数。POMDPの数理的再定義の際に出てきてしまった抽象概念。定義は後述。 \(^{\ast6} \)
- \(V^\pi \) : 信念価値関数 \(\mathcal{B} \to \mathbb{R}_\circ \)定義は後述。
- \(\pi \) : 方策。 \(A \)上の確率測度の集合を\(\mathcal{A} \)として、 \(\pi:\mathcal{B} \to \mathcal{A} \)として定義される、確率測度を受け取って確率測度を返す関数です。
- \(\Phi \) : 信念状態の遷移を表す測度。 \(\mathcal{B} × A × \mathcal{O}×\mathbb{R}\to\mathcal{B} \)
ただし \(\mathcal{O} \)は有限集合もしくは \(\mathbb{R}^d \)上の単連結なコンパクト集合であるとします。
\(^{\ast5}\)実はここの距離の定義は今後の課題です。絶対連続な測度の集合で定義するだけなら確率収束位相でいいのでつまり\(L1\)でいけますが、これだとS が有限集合の場合とスムースにつながりません。
\(^{\ast6}\)「確率測度の集合に値をとる確率変数」というクレイジーな概念。確率変数の実現値\(B (\omega)\)が測度という狂気。例えば\(B (\omega)(s) = 0.1\)といった数値を持ちます。本記事の中でぶっちぎりで難しい。ただ、このやたら難しい考え方を導入すると分布型強化学習（DRL）なども含んて統一的に扱えるという大きな利点があり、MDP、POMDP、DRL すべてに通用する大定理も作っていけそう。ちなみにマリアヴァン解析やホワイトノイズ解析になると、「超関数空間に値を取る確率変数」というもうワンランクえげつないものが出てきます。
こちらでも履歴という概念を導入します。
(4)
さらにこの部分 \(\sigma \)-加法族を定めます。
(5)
各種計算は\(\mathcal{G}\)-適合である必要があります。
ここで注意したいのが、\(s\)は\(p, p_o \)両方に対して現在の値を参照するのに対して、参照される\(a \) は\(p\)では現在の値であるものの、 \(p_o \)では過去の値であるということです。
すなわち、\(s\)の遷移にはマルコフ性がありますが、\(o \)の遷移にはマルコフ性があるとは限りません。
\(s_t = o_t, \mathcal{S} = \mathcal{O}\)とすることで、マルコフ決定過程を部分観測マルコフ決定過程の一部と見做すことができます。\(^{\ast7}\)
裏に確率過程があり、それは観測できない状況、というとHMM(隠れマルコフモデル) が浮かぶ方もいらっしゃるかもしれません。
実際、非常に状況はよく似ており、この関係性はマルコフ過程と通常のマルコフ決定過程の関係と同じであると言えます。
すなわち、制御の要素が入らないものがマルコフ過程や隠れマルコフモデルで、それらに対する制御を行うのが、マルコフ決定過程や部分観測マルコフ決定過程です。
\(^{\ast7}\)どちらも定義２を定義としたうえで、\(\mathcal{F}_t = \mathcal{G}_t\)をマルコフ決定過程、\(\mathcal{F}_t \supsetneq \mathcal{G}_t\)を部分観測マルコフ決定過程の定義とするのもアリです。可測性の条件とも釣り合います。
2.3 信念状態
これまでの履歴から作られる、実際の状態に対する予測分布です。
まず、\(B\)を「\(S\)上の確率測度の集合 :\(\mathcal{P}(S)\)」と定義します。
そして、信念状態\(b_t \in \mathcal{B}\)を、\(S\)上の\(\mathcal{F}_t\)条件付き分布とします。
\(S\)はマルコフ性があるので、前の行動、前の信念状態、今の観測だけで決定することができます。
POMDP特有の難しさは、この信念状態の改良であると言えます。\(^{\ast 8}\)
信念状態の更新測は、単純に考えて次のようになると考えられます。
(6)
\[d b_{t+1}\left(s^{\prime}\right)=p_{o}\left(o_{t+1} | s^{\prime}, a_{t}\right) \int_{\mathcal{S}} p\left(s^{\prime} | s, a_{t}\right) d b_{t}(s)\]
信念状態はこれで正しい測度に収束してくれるらしいのですが、実際には報酬と状態が独立でないことが多いため、著しく効率が悪いです。\(^{\ast 9}\)
\(^{\ast 8}\)マルコフ方策の妥当性という定理が[1] の定理7.1 として書かれていますが、実際には信念状態が\(\mathcal{F}_t\)条件付き分布として初めて定義される概念であるため、マルコフなようで大いに履歴に依存しています。そのため同値性は帰納法だとか使わなくても自明です。
\(^{\ast 9}\) [1] では方策がなかなか良くならないのは信念状態の不確実性が大きくなるため、とありますが、実際にはそうではなく、信念状態の更新において、行動の質をフラットに見るため、通常のDQN のように良いところを強く見るといったことをしなくなります。それによって良い報酬に対する適合が進まないというのが、本当の理由であると考えられます。ちなみにこの事実の実証的な結果は[2]
2.4 方策の決定
POMDPにおける方策とは、信念状態に対して行動の確率分布を定める写像です。
すなわち、\(\pi : \mathcal{P} (S) \to \mathcal{P} (A) \)です。
ここで、マルコフ決定過程と同じく、状態行動価値関数を導入します。
(7)
\[Q^{\pi}(s, a):=E\left[\sum_{t=0}^{\infty} \gamma^{t} R_{t}\left(S_{t}, A_{t}\right) | A_{\tilde{t}} \pi\left(b_{t}\right), S_{0}=s, A_{0}=a\right]\]
ただし、先述の通り、\(s\)は直に観測できません。そこで、\(V^\pi : \mathcal{B} \to \mathbb{R} \) から価値を見積もる信念価値関数を導入します。
(8)
これは、通常のMDP における、状態価値関数に該当します。これの上での最適化がすなわち、POMDP とは、現在の状態\(S\) から行動を決定するのではなく、現在の信念である\(S\)上の確率測度という。無限集合を状態と置いて意思決定するモデルです。\(^{\ast 10}\)
ここで\(\tilde{R}(b, a):=R(s, a) | \tilde{s} b(s)\)と置くことで、信念に対して報酬を考えることができます。\(^{\ast 11}\)
\(^{\ast 10}\) 確率測度の距離を\(L^1\)で置けば、\(S\)が\(d\)次元ならこれは\([0, 1]^d\)上の最適化問題になります。
\(^{\ast 11}\) [1] でいろいろややこしいことが書かれてるのは、報酬を決定論的に甘えてるかを飲み込んでしまえばここでややこしいことを考える必要がなくなります。
次に、非常に重要な定理を書きます。
定理1
可測な方策の集合を\(\prod^{M}\)と書く。さらに、決定論的で可測な方策\(\prod^{d} : \mathcal{B} \to A\)を置く。
任意の\(b \in \mathcal{B}\)に対して
(9)
ここで、\(b\)の遷移にマルコフ性を仮定します。すなわち、対応する\(S\)上の確率変数\(B_t\)はマルコフ過程とします。
(10)
ただし、\(b^′\) は信念状態\(b\)に対して行動\(a\)をとったときの信念状態を表す、\(B\)上の確率変数です。\(^{\ast 12}\)
また、遷移カーネル\(p^{ba}_z (r, o | b, a)\)を、\(\mathcal{B} ×A \to \mathcal{O} × R\)という確率測度にします。
ここで重要なのは、\(b_t, a_t\) から\(b_{t+1}\)は確率的にしか定まりませんが、\(b_t, a_t, r_t, o_{t+1} \)からは決定論的に定まることに注意。
そこで\(\Omega\)で\(B×A×\mathcal{O}× \mathbb{R} \to B\)の写像を表すとして、ベルマン最適方程式は
(11)
と書き直せます。これであの測度の集合に値をとる確率変数を消して考えることができました。
ベルマン作用素\(\mathcal{T}_b\)を次のように定義します。
信念状態関数\(V : B \to B\)のうち、有界なものの集合\(\mathcal{V}\)上の作用素です。\(\mathcal{V}\)上の距離は最大値ノルムで定義します。\(^{*13}\)
(12)
\(^{\ast 12}\)測度の集合に値をとる確率変数という、極めて難解で抽象的な概念ですが、なんとか頑張ってついてきてください。こうでないと定式化できません。もはや完全に数学科の確率論専攻かつ大学院レベルの概念です。ちなみに、マリアヴァン解析とかホワイトノイズ解析になると、汎関数空間に値をとる確率変数とかいう、もっと難解なのが出てきます。
\(^{\ast 13}\)「測度を受け取り測度を返す写像のうち、連続写像がなす空間の距離」というおぞましすぎるものが出てきてますが、頑張りましょう。
2.5 信念価値関数とアルファベクトル
ここで、一般の機械学習でもよくある状態価値関数を導入します。これはPOMDP界隈ではアルファベクトルと呼ばれるため、それに倣って\(\alpha(s)\)と表記します。
これを用いて、信念価値関数\(V ^\pi\)を開きます
(13)
要するに、状態価値関数の、測度\(b\)に対する期待値\(^{\ast 14}\)です。
\(^{\ast 14}\)普通の機械学習と違い、二つの確率空間が出てきており、期待値もそれぞれの確率空間によって変わります。場合によっては期待値そのものが確率測度になることもあり得ます。非常にややこしいですが諦めないでください。
最後に
今回は、POMDP について、独自の再定義を行いました。尋常じゃない難易度に、正直疲れ果てました。
ですがもう一段階ステップアップして、これとDRL を組み合わせた定義をすれば、DRL,POMDP,RLなどはすべてこの統一定義の特別な場合と考えることができ、定理もその統一定義の下で考えればすべてに通用するものができると考えられます。
ランダム測度に関してもっと知りたい方は、ぜひとも「離散マリアヴァン解析」「ジャンプ過程」などのキーワードで調べてみてください。
株式会社ダイナミックプライシングテクノロジーでは、このPOMDPの理論やそれを用いたアルゴリズム、その社会実装についても研究中です。
参考文献
[1] 森村哲郎, 強化学習機械学習プロフェッショナルシリーズ(2019)
[2] M.T.Izadi and D.Precup.Using rewards for belief state updates in partially observable Markov decisionprocess.In European Conference on Machine Learning,pages 593-600,2005