マルコフ決定過程

マルコフ決定過程（MDP ）は、結果が不確実な場合に順次意思決定を行うための数学モデルである。^{[ 1 ]}これは確率的意思決定過程の一種であり^{[ 2 ]} 、確率的動的計画法の手法を用いて解かれることが多い。

1950年代のオペレーションズ・リサーチから生まれた^{[ 3 ] [ 4 ]} MDPは、それ以来、生態学、経済学、医療、通信、強化学習など、さまざまな分野で認知されてきました。^{[ 5 ]}強化学習では、MDPフレームワークを利用して学習エージェントとその環境との相互作用をモデル化します。このフレームワークでは、相互作用は状態、行動、報酬によって特徴付けられます。MDPフレームワークは、人工知能の課題の主要要素を簡略化した表現を提供するように設計されています。このモデリングフレームワークには、因果関係の理解、不確実性と非決定性の管理、明確な目標の追求が組み込まれています。^{[ 5 ]}

この名称は、ロシアの数学者アンドレイ・マルコフが提唱した概念であるマルコフ連鎖との関連性に由来しています。「マルコフ決定過程」の「マルコフ」は、マルコフ性に従った状態遷移の根底にある構造を指します。この過程が「決定過程」と呼ばれるのは、これらの状態遷移に影響を与える意思決定を伴うためであり、マルコフ連鎖の概念を不確実性下における意思決定の領域に拡張しています。

意味

3 つの状態 (緑の円)、2 つのアクション (オレンジ色の円)、2 つの報酬 (オレンジ色の矢印) を持つ単純な MDP の例

マルコフ決定プロセスは 4 つの要素 から成り、次のようになります。 ${\displaystyle (S,A,P_{a},R_{a})}$

• ${\displaystyle S}$は状態空間と呼ばれる状態の集合です。状態空間は、実数集合と同様に、離散的または連続的になります。
• ${\displaystyle A}$はアクション空間と呼ばれるアクションの集合です（あるいは、状態 から利用可能なアクションの集合です）。状態に関しては、この集合は離散的または連続的になります。 ${\displaystyle A_{s}}$ ${\displaystyle s}$
• ${\displaystyle P_{a}(s,s')}$は、直感的に言えば、時刻における動作が時刻 における状態 に至る確率です。一般に、この確率遷移は、あらゆる測定可能値に対してを満たすように定義されます。状態空間が離散的な場合、積分は計数測度に関して行われるため、後者は と簡略化されます 。 の場合、積分は通常、ルベーグ測度に関して行われます。 ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s'}$ ${\displaystyle t+1}$ ${\displaystyle \Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{S'}P_{a}(s,s')ds',}$ ${\displaystyle S'\subseteq S}$ ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ ${\displaystyle S\subseteq \mathbb {R} ^{d}}$
• ${\displaystyle R_{a}(s,s')}$状態から状態へ遷移するための行動が取られた後に受け取る即時報酬（または期待される即時報酬）です。報酬は一般に確率変数です。 ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle s'}$

ポリシー関数は、状態空間（ ）からアクション空間（）への（潜在的に確率的な）マッピングです。 ${\displaystyle \pi }$ ${\displaystyle S}$ ${\displaystyle A}$

最適化目標

マルコフ決定過程における目標は、意思決定者にとって適切な「ポリシー」を見つけることです。ポリシーとは、状態 において意思決定者が選択する行動を指定する関数です。このようにマルコフ決定過程とポリシーを組み合わせると、各状態における行動が固定され、結果として得られる組み合わせはマルコフ連鎖のように動作します（状態 において選択される行動はによって完全に決定されるため）。 ${\displaystyle \pi }$ ${\displaystyle \pi (s)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle \pi (s)}$

目的は、ランダム報酬の累積関数（通常は潜在的に無限の期間にわたる期待割引合計）を最大化する ポリシーを選択することです。 ${\displaystyle \pi }$

${\displaystyle E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]}$（ここで、私たちが選択する、つまり、ポリシーによって与えられたアクション）。そして、期待値は引き継がれる ${\displaystyle a_{t}=\pi (s_{t})}$ ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

ここで、 は を満たす割引係数であり、これは通常 に近い値となります（例えば、ある割引率 の場合）。割引係数が低いほど、意思決定者はより近視眼的になり、現在の方針に従うことで将来に生じる影響を比較的無視するようになります。 ${\displaystyle \ \gamma \ }$ ${\displaystyle 0\leq \ \gamma \ \leq \ 1}$ ${\displaystyle 1}$ ${\displaystyle \gamma =1/(1+r)}$ ${\displaystyle r}$

もう一つの可能​​な目的関数は、厳密に関連しているものの、一般的に用いられるステップリターンです。この場合、割引係数を使用する代わりに、エージェントはプロセスの最初のステップのみに関心を持ち、各報酬は同じ重みを持ちます。 ${\displaystyle H-}$ ${\displaystyle \ \gamma \ }$ ${\displaystyle H}$

${\displaystyle E\left[\sum _{t=0}^{H-1}{R_{a_{t}}(s_{t},s_{t+1})}\right]}$（ここで、私たちが選択する、つまり、ポリシーによって与えられたアクション）。そして、期待値は引き継がれる ${\displaystyle a_{t}=\pi (s_{t})}$ ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

時間軸はどこにあるか。前者の目的と比較して、後者の目的は学習理論でより多く用いられます。 ${\displaystyle \ H\ }$

上記の関数を最大化する方策は最適方策と呼ばれ、通常は と表記されます。特定のMDPには複数の異なる最適方策が存在する場合があります。マルコフ性により、上で仮定したように、最適方策は現在の状態の関数であることが示されます。 が決定論的である場合、同様に決定論的な 最適方策が常に存在します。 ${\displaystyle \pi ^{*}}$ ${\displaystyle R_{a}(s,s')}$ ${\displaystyle \pi ^{*}}$

[証拠]

が決定論的であると仮定する。つまり、定数に対しては値も一定である。なぜなら、値反復（ベルマン方程式）再帰を満たす 唯一の不動点が存在することが知られているからである。 ${\displaystyle R}$ ${\displaystyle a,s,s'}$ ${\displaystyle R_{a}(s,s')}$ ${\displaystyle \gamma <1}$ ${\displaystyle V^{*}}$

$${\displaystyle V^{*}(s)=\max _{a}E\left[R_{a}(s,s')+\gamma V^{*}(s')\right]}$$

検査により、この固定点が次のポリシーに関連付けられた価値関数であることがわかります。

$${\displaystyle \pi ^{*}(s):=\arg \max _{a}E\left[R_{a}(s,s')+\gamma V^{*}(s')\right]}$$

ベルマン再帰を展開することで、決定論的ポリシーのセットに対して が実際に最適である（すべての状態に対して同時に）ことを示すことができます。 ${\displaystyle V^{*}}$

$${\displaystyle {\begin{aligned}V^{*}(s_{0})&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma \max _{a_{1}}E\left[R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right]\right]\\&=\max _{a_{0},a_{1}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma \left(R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right)\right]\\&=\sup _{\{a_{t}\}_{t=0}^{\infty }}E\left[\sum _{t=0}^{\infty }\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})\right]\end{aligned}}}$$

が確率的、つまり実行されるアクションがランダム変数である場合を考えてみましょう。このような非決定論的なポリシーは、決定論的なポリシーによって支配されていることは、以下のように示せます。 ${\displaystyle \pi }$ ${\displaystyle a:=\pi (s)}$ ${\displaystyle \pi ^{*}}$

$${\displaystyle {\begin{aligned}V^{*}(s_{0})&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&\geq E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&=E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma \max _{a_{1}}E\left[R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right]\right]\\&\geq E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma \left(R_{\pi (s_{1})}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right)\right]\\&\geq E\left[\sum _{t=0}^{\infty }\gamma ^{t}R_{\pi (s_{t})}(s_{t},s_{t+1})\right]\end{aligned}}}$$

シミュレータモデル

多くの場合、遷移確率分布 を明示的に表現することは困難です。そのような場合、シミュレータを用いて遷移分布のサンプルを提供することで、MDPを暗黙的にモデル化することができます。暗黙的MDPモデルの一般的な形態の一つは、エピソード環境シミュレータです。これは、初期状態から開始し、行動入力を受け取るたびに次の状態と報酬を生成します。このようにして、状態、行動、報酬の軌跡（エピソードと呼ばれることが多い）を生成することができます。 ${\displaystyle P_{a}(s,s')}$

シミュレータの別の形式は生成モデルであり、任意の状態とアクションが与えられた場合に、次の状態と報酬のサンプルを生成できるシングルステップシミュレータです。^{[ 6 ]} （これは統計分類の文脈における生成モデルという用語とは異なる意味であることに注意してください。）擬似コードを使用して表現されるアルゴリズムでは、が生成モデルを表すためによく使用されます。たとえば、式は生成モデルからサンプリングするアクションを示します。ここで、とは現在の状態とアクション、との新しい状態と報酬です。エピソードシミュレータと比較して、生成モデルには、軌跡で遭遇した状態だけでなく、任意の状態からデータを生成できるという利点があります。 ${\displaystyle G}$ ${\displaystyle s',r\gets G(s,a)}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s'}$ ${\displaystyle r}$

これらのモデルクラスは情報内容の階層を形成します。明示的モデルは分布からのサンプリングを通じて生成モデルを自明に生成し、生成モデルを繰り返し適用することでエピソードシミュレータを生成します。逆方向には、回帰を通じてのみ近似モデルを学習することが可能です。特定のMDPで利用可能なモデルの種類は、どのソリューションアルゴリズムが適切かを決定する上で重要な役割を果たします。例えば、次のセクションで説明する動的計画法アルゴリズムは明示的モデルを必要とし、モンテカルロ木探索は生成モデル（または任意の状態でコピーできるエピソードシミュレータ）を必要としますが、ほとんどの強化学習アルゴリズムはエピソードシミュレータのみを必要とします。

例

ポールバランスの例（ Open AI ジムベンチマークからの環境のレンダリング）

MDP の例としては、古典的な制御理論に由来するポールバランス モデルがあります。

この例では、

• ${\displaystyle S}$ポールの角度、角速度、カートの位置、速度によって指定された順序付けられたタプルの集合です。 ${\displaystyle (\theta ,{\dot {\theta }},x,{\dot {x}})}$
• ${\displaystyle A}$は、カートの左側（右側）に力を加えることに対応します。 ${\displaystyle \{-1,1\}}$
• ${\displaystyle P_{a}(s,s')}$システムの遷移であり、この場合は決定論的であり、力学の法則によって駆動されます。
• ${\displaystyle R_{a}(s,s')}$遷移後にポールが上向きの場合は 、そうでない場合は 0です。したがって、この関数はこの特定のケースでのみ に依存します。 ${\displaystyle 1}$ ${\displaystyle s'}$

アルゴリズム

有限状態空間および行動空間を持つMDPの解は、動的計画法などの様々な手法で見つけることができます。本節のアルゴリズムは、有限状態空間および行動空間を持ち、遷移確率と報酬関数が明示的に与えられたMDPに適用されますが、基本概念は関数近似などを用いて他の問題クラスにも拡張できます。また、可算無限状態空間および行動空間を持つプロセスの中には、有限状態空間および行動空間を持つプロセスに正確に縮減できるものもあります。^{[ 7 ]}

有限状態およびアクションMDPの最適ポリシーを計算する標準的なアルゴリズム群では、状態をインデックスとする2つの配列（実数値を格納するvalue とアクションを格納するpolicy ）を格納するためのストレージが必要です。アルゴリズムの最後には、解が格納され、状態からその解に従うことで得られる（平均して）報酬の割引合計が格納されます。 ${\displaystyle V}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle V(s)}$ ${\displaystyle s}$

このアルゴリズムは、(1) 値の更新と (2) 方策の更新という2つのステップから成り、これらは、それ以上の変化がなくなるまで、すべての状態に対して一定の順序で繰り返されます。どちらのステップも、最適な方策と状態の値の以前の推定値を用いて、最適な方策と状態の値の新しい推定値を再帰的に更新します。

${\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}$

${\displaystyle \pi (s):=\operatorname {argmax} _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}}$

これらの順序はアルゴリズムのバリエーションによって異なります。すべての状態に対して一度に実行することも、状態ごとに実行することもできます。また、状態によっては実行頻度を高く設定することもできます。いずれのステップからも除外される状態が存在しない限り、アルゴリズムは最終的に正しい解に到達します。^{[ 8 ]}

注目すべき変種

価値の反復

値反復法（ベルマン 1957 ）は後方帰納法とも呼ばれ、関数は使用されません。代わりに、必要に応じての値が内で計算されます。 の計算結果を の計算値に代入すると、結合されたステップが得られます。 ${\displaystyle \pi }$ ${\displaystyle \pi (s)}$ ${\displaystyle V(s)}$ ${\displaystyle \pi (s)}$ ${\displaystyle V(s)}$

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}$

ここで、 は反復回数です。値反復は から始まり、値関数の推定値として計算されます。その後、すべての状態 を繰り返し計算し、が左辺と右辺に収束するまで反復されます（これはこの問題の「ベルマン方程式」です）。ロイド・シャプレーの1953年の確率ゲームに関する論文には、MDPに対する値反復法が特別なケースとして含まれていましたが^{[ 9 ]}、これが認識されたのは後になってからのことでした^{[ 10 ] 。} ${\displaystyle i}$ ${\displaystyle i=0}$ ${\displaystyle V_{0}}$ ${\displaystyle V_{i+1}}$ ${\displaystyle s}$ ${\displaystyle V}$

値反復は、バナッハの不動点定理により収束することが保証されています。 ${\displaystyle \gamma <1}$

[証拠]

バナッハの不動点定理は、与えられた縮約写像には唯一の不動点が存在することを述べています。さらに、縮約写像を反復適用することで、この不動点に漸近的に近づくことができます。したがって、値の反復が縮約写像であることを示すだけで十分であり、これは以下に示す について示されます。 ${\displaystyle \gamma <1}$

便宜上、 とを示します。 ${\displaystyle X_{a}^{V}(s):=\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)}$ ${\displaystyle ({\mathcal {B}}V)(s):=\max _{a}X_{a}^{V}(s)}$

$${\displaystyle {\begin{aligned}\|{\mathcal {B}}V-{\mathcal {B}}W\|_{\infty }&=\max _{s}\left|({\mathcal {B}}V)(s)-({\mathcal {B}}W)(s)\right|\\&=\max _{s}\left|\max _{a}X_{a}^{V}(s)-\max _{a}X_{a}^{W}(s)\right|\\&\leq \max _{s}\max _{a}\left|X_{a}^{V}(s)-X_{a}^{W}(s)\right|\\&=\max _{s}\max _{a}\gamma \left|\sum _{s'}P_{a}(s,s')\left(V_{i}(s')-W_{i}(s')\right)\right|\\&\leq \max _{s}\max _{a}\gamma \max _{s'}\left|V_{i}(s')-W_{i}(s')\right|\\&=\gamma \max _{s'}\left|V_{i}(s')-W_{i}(s')\right|\\&=\gamma \|V_{i}-W_{i}\|_{\infty }\end{aligned}}}$$

政策の反復

ポリシー反復^{[ 11 ]}では、まずステップ1で説明した線形システムからを解くことで価値決定を実行し、次にステップ2のように計算することでポリシー改善を実行し、ポリシーが収束するまで両方のステップを繰り返します。（ポリシー反復は、価値反復を使用して最適化していたシアーズのカタログ郵送を最適化するためにハワードによって発明されました。^{[ 12 ]}） ${\displaystyle V}$ ${\displaystyle \pi }$

ポリシー反復は線形逆問題と非線形演算を効果的にインターリーブするため、緩和法の一種として解釈できます。

この変種の利点は、明確な停止条件が存在することです。各ポリシーには一意の解が存在するため、ポリシー改善によって同じポリシーが2回連続して生成される と、アルゴリズムは完了します。 ${\displaystyle V}$ ${\displaystyle \pi }$

ポリシー反復が値の反復よりも高速になる場合があります (たとえば、アクション空間が状態空間よりも大幅に大きい場合など)。ただし、可能な状態の数が多い場合は通常、ポリシー反復は値の反復よりも遅くなります。

修正されたポリシー反復

修正された政策反復（van Nunen 1976 ; Puterman & Shin 1978）では、ステップ1が複数回繰り返され、次にステップ2が1回実行されます。^{[ 13 ] [ 14 ]}その後、ステップ1が再び複数回繰り返され、これが繰り返されます。

優先清掃

このバリアントでは、ステップは、アルゴリズムに基づいているか (最近、これらの状態またはその周辺で大きな変更があった)、使用に基づいているか (これらの状態は開始状態に近いか、またはアルゴリズムを使用する人またはプログラムにとって興味深い)、何らかの意味で重要な状態に優先的に適用されます。 ${\displaystyle V}$ ${\displaystyle \pi }$

計算の複雑さ

有限MDPに対しては、問題表現のサイズに対して時間計算量が多項式となる最適ポリシーを見つけるアルゴリズムが存在する。したがって、 MDPに基づく決定問題は計算量クラスPに属する。^{[ 15 ]}しかし、次元の呪いにより、問題表現のサイズは状態変数と行動変数の数に対して指数関数的になることが多く、正確な解法はコンパクトな表現を持つ問題に限定される。実際には、モンテカルロ木探索などのオンライン計画手法は、より大きな問題で有用な解を見つけることができ、理論的には、状態空間のサイズに計算量が依存しない、任意の最適に近いポリシーを見つけることができるオンライン計画アルゴリズムを構築することが可能である。^{[ 16 ]}

拡張と一般化

マルコフ決定プロセスは、プレイヤーが 1 人だけの確率ゲームです。

部分的な観測可能性

上記の解法は、行動を起こすべき時点の状態が既知であることを前提としています。そうでなければ、状態は計算できません。この前提が成り立たない場合、この問題は部分観測マルコフ決定過程（POMDP）と呼ばれます。 ${\displaystyle s}$ ${\displaystyle \pi (s)}$

制約付きマルコフ決定過程

制約付きマルコフ決定過程（CMDPS）はマルコフ決定過程（MDP）の拡張である。MDPとCMDPには3つの根本的な違いがある。^{[ 17 ]}

• アクションを 1 つではなく 1 つ適用すると、複数のコストが発生します。
• CMDP は線形計画法のみで解決され、動的計画法は機能しません。
• 最終的なポリシーは開始状態によって異なります。

ラグランジュ乗数法はCMDPに適用されます。ラグランジュ乗数法に基づくアルゴリズムは数多く開発されています。

• 自然方策勾配プライマル・デュアル法。^{[ 18 ]}

CMDPには多くの応用分野があり、最近ではロボット工学における動作計画のシナリオにも利用されています。 ^{[ 19 ]}

連続時間マルコフ決定過程

離散時間マルコフ決定プロセスでは、離散的な時間間隔で意思決定が行われます。一方、連続時間マルコフ決定プロセスでは、意思決定者が任意の時点で意思決定を行うことができます。離散時間マルコフ決定プロセスと比較して、連続時間マルコフ決定プロセスは、連続ダイナミクスを持つシステム、すなわち常微分方程式（ODE）によって定義されるシステムの意思決定プロセスをより適切にモデル化できます。このモデリングフレームワークは、待ち行列システム、疫病プロセス、人口プロセスなどの分野に適用できます。

離散時間マルコフ決定過程と同様に、連続時間マルコフ決定過程においても、エージェントは期待累積報酬を最大化する最適な方策を見つけることを目指します。標準的なケースとの主な違いは、時間変数の連続性により、総和が積分に置き換えられることです。

${\displaystyle \max \operatorname {E} _{\pi }\left[\left.\int _{0}^{\infty }\gamma ^{t}r(s(t),\pi (s(t)))\,dt\;\right|s_{0}\right]}$

どこ ${\displaystyle 0\leq \gamma <1.}$

離散空間：線形計画法の定式化

状態空間と行動空間が有限であれば、線形計画法を使って最適なポリシーを見つけることができ、これは最も初期に適用されたアプローチの1つでした。ここではエルゴードモデルのみを考慮します。つまり、連続時間MDPは定常ポリシーの下でエルゴード連続時間マルコフ連鎖になります。この仮定の下では、意思決定者は現在の状態でいつでも意思決定を行うことができますが、複数のアクションを実行する利点はありません。システムが現在の状態から別の状態に遷移しているときにのみアクションを実行する方が適切です。いくつかの条件下では、^{[ 20 ]}最適価値関数が状態に依存しない場合、次の不等式が成り立ちます。 ${\displaystyle V^{*}}$ ${\displaystyle i}$

${\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j\mid i,a)h(j)\quad \forall i\in S{\text{ and }}a\in A(i)}$

関数 が存在する場合、 は上記の式を満たす最小のものになります。 を求めるには、次の線形計画モデルを使用できます。 ${\displaystyle h}$ ${\displaystyle {\bar {V}}^{*}}$ ${\displaystyle g}$ ${\displaystyle {\bar {V}}^{*}}$

• 主線形計画法(P-LP)

${\displaystyle {\begin{aligned}{\text{Minimize}}\quad &g\\{\text{s.t}}\quad &g-\sum _{j\in S}q(j\mid i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}$

• 双対線形計画法（D-LP）

${\displaystyle {\begin{aligned}{\text{Maximize}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.t.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j\mid i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i){\text{ and }}\forall i\in S\end{aligned}}}$

${\displaystyle y(i,a)}$が非ネイティブであり、D-LP問題における制約を満たす場合、D-LPの実行可能解である。D -LPの実行可能解は、次の場合に最適解であると言われる。 ${\displaystyle y(i,a)}$ ${\displaystyle y^{*}(i,a)}$

${\displaystyle {\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}}$

D-LP のすべての実行可能な解について。最適解が見つかったら、それを用いて最適なポリシーを確立できます。 ${\displaystyle y(i,a)}$ ${\displaystyle y^{*}(i,a)}$

連続空間：ハミルトン・ヤコビ・ベルマン方程式

連続時間MDPにおいて、状態空間と行動空間が連続であれば、ハミルトン・ヤコビ・ベルマン（HJB）偏微分方程式を解くことで最適な基準を求めることができる。HJB方程式を議論するためには、問題を再定式化する必要がある。

${\displaystyle {\begin{aligned}V(s(0),0)={}&\max _{a(t)=\pi (s(t))}\int _{0}^{T}r(s(t),a(t))\,dt+D[s(T)]\\{\text{s.t.}}\quad &{\frac {ds(t)}{dt}}=f[t,s(t),a(t)]\end{aligned}}}$

${\displaystyle D(\cdot )}$は終端報酬関数、はシステム状態ベクトル、は私たちが求めようとしているシステム制御ベクトルです。は状態ベクトルが時間とともにどのように変化するかを示しています。ハミルトン・ヤコビ・ベルマン方程式は以下のとおりです。 ${\displaystyle s(t)}$ ${\displaystyle a(t)}$ ${\displaystyle f(\cdot )}$

${\displaystyle 0=\max _{a}(r(t,s,a)+{\frac {\partial V(t,s)}{\partial s}}f(t,s,a))}$

この方程式を解くことで最適値関数 を見つけることができ、これにより任意の 時点での最適制御が得られる。 ${\displaystyle V^{*}}$ ${\displaystyle t}$ ${\displaystyle a(t)}$ ${\displaystyle a(t)={\underset {a}{\text{argmax}}}(r(t,s,a)+{\frac {\partial V^{*}(t,s)}{\partial s}}f(t,s,a)).}$

強化学習

強化学習は機械学習と最適制御の学際的な分野であり、遷移確率と報酬が未知のMDPに対して近似的に最適なポリシーを見つけることを主な目的としています。^{[ 21 ]}

強化学習は、方策反復に必要な遷移確率を明示的に指定することなく、マルコフ決定過程を解くことができます。この設定では、遷移確率と報酬は経験から学習する必要があります。つまり、エージェントにMDPと所定のステップ数だけ相互作用させることによって学習します。理論的にも実践的にも、サンプル効率の最大化、つまり最適な方策に近いパフォーマンスを持つ方策を学習するために必要なサンプル数を最小化することに注力します（プロセスの確率的性質により、有限個のサンプルで最適な方策を学習することは一般的に不可能です）。 ${\displaystyle \varepsilon -}$

離散MDPのための強化学習

このセクションの目的のために、アクションを実行してから最適に（または現在のポリシーに従って）続行することに対応する追加の関数を定義すると便利です。 ${\displaystyle a}$

${\displaystyle \ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }$

この関数も未知ですが、学習中の経験はペア（結果とペア、つまり「私は状態にあり、行動しようとして、そして何が起こったか」）に基づいています。つまり、配列を持ち、経験を用いてそれを直接更新するのです。これはQ学習として知られています。 ${\displaystyle (s,a)}$ ${\displaystyle s'}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s'}$ ${\displaystyle Q}$

その他のスコープ

学習オートマトン

機械学習理論におけるMDPプロセスのもう一つの応用は、学習オートマトンと呼ばれる。これは、環境が確率的である場合の強化学習の一種でもある。学習オートマトンに関する最初の詳細な論文は、 NarendraとThathachar（1974）によって概説されており、これはもともと有限状態オートマトンとして明示的に記述されていた。^{[ 22 ]}強化学習と同様に、学習オートマトンアルゴリズムにも、確率や報酬が未知の場合に問題を解決できるという利点がある。学習オートマトンとQ学習の違いは、前者の手法ではQ値の記憶を省略し、行動確率を直接更新して学習結果を求める点である。学習オートマトンは、収束の厳密な証明を備えた学習方式である。^{[ 23 ]}

学習オートマトン理論では、確率オートマトンは次の要素から構成されます。

• 可能な入力の集合x 、
• 可能な内部状態のセット Φ = { Φ ₁ , ..., Φ _{s }、}
• 可能な出力またはアクションの集合 α = { α ₁ , ..., α _r } （ r ≤ s）
• 初期状態確率ベクトルp (0) = ≪ p ₁ (0), ..., p _s (0) ≫、
• 計算可能な関数 Aは、各時間ステップtの後にp ( t )、現在の入力、および現在の状態からp ( t +1)を生成し、
• 各タイムステップで出力を生成する関数G : Φ → α。

このようなオートマトンの状態は、「離散状態離散パラメータマルコフ過程」の状態に対応する。^{[ 24 ]}各時間ステップt = 0,1,2,3,...において、オートマトンはその環境から入力を読み取り、AによってP( t )をP( t +1)に更新し、確率P( t +1)に従って後続状態をランダムに選択し、対応するアクションを出力する。オートマトン環境は、次にそのアクションを読み取り、次の入力をオートマトンに送信する。^{[ 23 ]}

カテゴリー理論的解釈

報酬を除けば、マルコフ決定過程は圏論の観点から理解できる。すなわち、生成集合Aを持つ自由モノイドを と表す。Distをジリーモナドのクライスリ圏とすると、関数は状態の集合Sと確率関数Pの両方を符号化する。 ${\displaystyle (S,A,P)}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}\to \mathbf {Dist} }$

このようにして、マルコフ決定過程はモノイド（一つの対象を持つカテゴリ）から任意のカテゴリへと一般化できる。この結果は文脈依存マルコフ決定過程と呼ぶことができる。なぜなら、ある対象から別の対象へ移動することで、可能な行動の集合と可能な状態の集合が変化するからである。 ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )}$ ${\displaystyle {\mathcal {C}}}$

代替表記

MDPの用語と表記法は完全には確立されていません。2つの主要な流れがあります。1つは経済学などの文脈における最大化問題に焦点を当てており、行動、報酬、価値といった用語を使用し、割引率をβまたはγと呼びます。もう1つは工学や航行学における最小化問題に焦点を当てており、制御、コスト、コスト・トゥ・ゴーといった用語を使用し、割引率をαと呼びます。さらに、遷移確率の表記法も様々です。

この記事で	代替	コメント
アクションa	コントロールu
報酬R	コストg	gはRの負数である
値V	持ち帰り費用J	JはVの負数である
ポリシーπ	ポリシーμ
割引係数γ	割引係数α
遷移確率 ${\displaystyle P_{a}(s,s')}$	遷移確率 ${\displaystyle p_{ss'}(a)}$

さらに、遷移確率は と書かれることもあるが、まれに、 ${\displaystyle \Pr(s,a,s')}$ ${\displaystyle \Pr(s'\mid s,a)}$ ${\displaystyle p_{s's}(a).}$

参照

• 確率オートマトン
• オッズアルゴリズム
• 量子有限オートマトン
• 部分観測マルコフ決定過程
• 動的計画法
• 経済学への応用のためのベルマン方程式。
• ハミルトン・ヤコビ・ベルマン方程式
• 最適な制御
• 再帰的経済学
• マビノギオンの羊問題
• 確率ゲーム
• Q学習
• マルコフ連鎖

参考文献

1. Puterman, Martin L. (1994).マルコフ決定過程：離散確率動的計画法. Wileyシリーズ 確率・数理統計. 応用確率・統計セクション. ニューヨーク: Wiley. ISBN 978-0-471-61977-2。
2. Yin, Bo (2021).低遅延高密度無線ネットワークにおけるエアタイム管理（博士論文）. 日本：京都大学.
3. Schneider, S.; Wagner, DH (1957-02-26). 「冗長システムにおけるエラー検出」 . 1957年2月26日～28日開催の西部合同コンピュータ会議「冗長システムにおける信頼性技術 - IRE-AIEE-ACM '57 (西部)」で発表された論文. 米国ニューヨーク州: Association for Computing Machinery. pp.  115– 121. doi : 10.1145/1455567.1455587 . ISBN 978-1-4503-7861-1。{{cite book}}: ISBN / Date incompatibility (help)
4. ベルマン, リチャード (1958-09-01). 「動的計画法と確率的制御プロセス」 .情報制御. 1 (3): 228– 239. Bibcode : 1958InfCo...1..228B . doi : 10.1016/S0019-9958(58)80003-0 . ISSN 0019-9958 . 
5. Sutton, Richard S.; Barto, Andrew G. (2018).強化学習：入門. 適応計算と機械学習シリーズ（第2版）. マサチューセッツ州ケンブリッジ：MIT出版. ISBN 978-0-262-03924-6。
6. Kearns, Michael; Mansour, Yishay; Ng, Andrew (2002). 「大規模マルコフ決定過程における準最適計画のためのスパースサンプリングアルゴリズム」 .機械学習. 49 ( 193–208 ): 193–208 . doi : 10.1023/A:1017932429737 .
7. ローベル、A. (1984)。 「有限の骨格を持つマルコフの意思決定モデルについて」。オペレーションズリサーチの時代。28 (1): 17–27 .土井: 10.1007/bf01919083。S2CID 2545336。 
8. 強化学習：理論とPython実装北京：中国機械出版社 2019年 44頁ISBN 9787111631774。
9. Shapley, Lloyd (1953). 「確率的ゲーム」 .米国科学アカデミー紀要. 39 (10): 1095–1100 . Bibcode : 1953PNAS...39.1095S . doi : 10.1073 / pnas.39.10.1095 . PMC 1063912. PMID 16589380 .  
10. Kallenberg, Lodewijk (2002). 「有限状態および行動MDP」Feinberg, Eugene A. ; Shwartz, Adam (編). 『マルコフ決定過程ハンドブック：方法と応用』 Springer. ISBN 978-0-7923-7459-6。
11. ハワード、ロナルド・A. (1960).動的計画法とマルコフ過程. MIT出版.
12. ハワード 2002、「マルコフ決定過程の起源と応用に関するコメント」
13. Puterman, ML; Shin, MC (1978). 「割引マルコフ決定問題のための修正ポリシー反復アルゴリズム」. Management Science . 24 (11): 1127– 1137. doi : 10.1287/mnsc.24.11.1127 .
14. ヴァン・ヌーネン、JAE E (1976)。 「割引マルコフ決定問題に対する逐次近似法のセット」。オペレーションズリサーチの時代。20 (5): 203–208 .土井: 10.1007/bf01920264。S2CID 5167748。 
15. パパディミトリウ, クリストス;ツィツィクリス, ジョン(1987). 「マルコフ決定過程の複雑性」 .オペレーションズ・リサーチ数学. 12 (3): 441– 450. doi : 10.1287/moor.12.3.441 . hdl : 1721.1/2893 . 2023年11月2日閲覧。
16. Kearns, Michael; Mansour, Yishay; Ng, Andrew (2002年11月). 「大規模マルコフ決定過程における準最適計画のためのスパースサンプリングアルゴリズム」 .機械学習. 49 (2/3): 193– 208. doi : 10.1023/A:1017932429737 .
17. Altman, Eitan (1999).制約付きマルコフ決定過程. 第7巻. CRC Press.
18. Ding, Dongsheng; Zhang, Kaiqing; Jovanovic, Mihailo; Basar, Tamer (2020).制約付きマルコフ決定過程のための自然方策勾配プライマル・デュアル法. ニューラル情報処理システムの進歩.
19. Feyzabadi, S.; Carpin, S. (2014年8月18日～22日). 「階層的制約付きマルコフ決定プロセスを用いたリスクを考慮した経路計画」 .オートメーション科学と工学 (CASE) . IEEE国際会議. pp. 297, 303.
20. 連続時間マルコフ決定過程. 確率モデルと応用確率論. 第62巻. 2009年. doi : 10.1007/978-3-642-02547-1 . ISBN 978-3-642-02546-4。
21. Shoham, Y.; Powers, R.; Grenager, T. (2003). 「マルチエージェント強化学習：批判的概説」(PDF) .スタンフォード大学技術報告書: 1– 13. 2018年12月12日閲覧。
22. Narendra, KS ; Thathachar, MAL (1974). 「学習オートマトン – 概要」. IEEE Transactions on Systems, Man, and Cyber​​netics . SMC-4 (4): 323– 334. Bibcode : 1974ITSMC...4..323N . CiteSeerX 10.1.1.295.2280 . doi : 10.1109/TSMC.1974.5408453 . ISSN 0018-9472 .  
23. ナレンドラ、クンパティ S. ;タタチャー、アラバマ州マンダヤム (1989)。学習オートマトン: 概要。プレンティス・ホール。ISBN 9780134855585。
24. Narendra & Thathachar 1974、p.325 左。

出典

• ベルマン、R.（1957）、ダイナミックプログラミング、プリンストン大学出版局、ISBN 978-0-486-42809-3{{citation}}: ISBN / Date incompatibility (help)ドーバー・ペーパーバック版（2003年）

さらに読む

• ベルマン, RE (2003) [1957].ダイナミック・プログラミング(ドーバー・ペーパーバック版). プリンストン, ニュージャージー: プリンストン大学出版局. ISBN 978-0-486-42809-3。
• Bertsekas, D. (1995).動的計画法と最適制御. 第2巻. MA: Athena.
• ダーマン、C. (1970).有限状態マルコフ決定過程. アカデミック・プレス.
• Feinberg, EA; Shwartz, A. 編 (2002). 『マルコフ決定過程ハンドブック』 ボストン, マサチューセッツ州: Kluwer. ISBN 9781461508052。
• Guo, X.; Hernández-Lerma, O. (2009).連続時間マルコフ決定過程. 確率モデルと応用確率論. Springer. ISBN 9783642025464。
• メイン, SP (2007).複雑ネットワークの制御技術. ケンブリッジ大学出版局. ISBN 978-0-521-88441-9. 2010年6月19日時点のオリジナルよりアーカイブ。付録には「Meyn & Tweedie」の要約が含まれています。 2012年12月18日時点のオリジナルよりアーカイブ。
• Puterman, ML (1994).マルコフ決定過程. Wiley.
• Ross, SM (1983).確率動的計画法入門(PDF) . 学術出版. 2022年3月4日時点のオリジナル(PDF)からのアーカイブ. 2019年1月19日閲覧.
• Sutton, RS; Barto, AG (2017). 『強化学習：入門』ケンブリッジ, マサチューセッツ州: The MIT Press.
• Tijms., HC (2003).確率モデル入門. Wiley. ISBN 9780470864289。

「 https://en.wikipedia.org/w/index.php?title=Markov_decision_process&oldid=1335326764#Policy_iteration」から取得