マルコフ決定過程

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

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

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

意味

マルコフ決定過程は4タプルである $(S,A,P_{a},R_{a})$ 、どこ：

$S$ は、状態空間と呼ばれる状態の集合です。状態空間は、離散的である場合もあれば、実数の集合のように連続的である場合もあります。
$A$ は、アクション空間と呼ばれる一連のアクションです（または、 $A_{s}$ 状態から利用可能なアクションのセット $s$ 状態に関しては、この集合は離散的または連続的である可能性があります。
$P_{a}(s,s')$ 行動の確率は $a$ 州内 $s$ その時 $t$ 州 $s'$ その時 $t+1$ 一般に、この確率遷移は以下を満たすように定義される。 $\Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{S'}P_{a}(s,s')ds',$ すべての $S'\subseteq S$ 測定可能。状態空間が離散的である場合、積分は計数尺度に関して行われるため、後者は次のように簡略化される。 $P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$ ; 万一に備えて $S\subseteq \mathbb {R} ^{d}$ 積分は通常、ルベーグ測度に関して行われる。
$R_{a}(s,s')$ 行動後に受け取る即時報酬（または期待される即時報酬） $a$ 状態から移行するために $s$ 述べる $s'$ 報酬は一般的に確率変数である。

政策機能 $\pi$ 状態空間からの（潜在的に確率的な）マッピング（ $S$ ）アクションスペースへ（ $A$ )

最適化目標

マルコフ決定過程の目標は、意思決定者にとって良い「方策」、つまり関数を見つけることである。 $\pi$ アクションを指定する $\pi (s)$ 意思決定者が州内で選択する $s$ このようにマルコフ決定過程と方策が組み合わされると、各状態における行動が固定され、結果として得られる組み合わせはマルコフ連鎖のように振る舞います（状態における行動の選択が固定されるため）。 $s$ 完全に決定されます $\pi (s)$ )

目的は政策を選択することです $\pi$ これは、ランダムな報酬の累積関数、典型的には潜在的に無限の期間にわたる期待割引合計を最大化するものである。

E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]

（私たちが選ぶ場所）

a_{t}=\pi (s_{t})

（つまり、ポリシーによって与えられた行動）。そして期待は

s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})

どこ $\ \gamma \$ 割引係数は満足できるものですか $0\leq \ \gamma \ \leq \ 1$ 通常は $1$ （例えば、 $\gamma =1/(1+r)$ 割引率 $r$ 割引率が低いほど、意思決定者は近視眼的になり、現在の政策に従うことが将来に及ぼす影響を比較的に無視するようになる。

もう一つ考えられるが、厳密に関連している一般的な目的は、 $H-$ ステップリターン。今回は割引係数を使用する代わりに $\ \gamma \$ エージェントは最初のものだけに興味がある $H$ プロセスの各段階において、それぞれの報酬は同じ重みを持つ。

E\left[\sum _{t=0}^{H-1}{R_{a_{t}}(s_{t},s_{t+1})}\right]

（私たちが選ぶ場所）

a_{t}=\pi (s_{t})

（つまり、ポリシーによって与えられた行動）。そして期待は

s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})

どこ $\ H\$ は時間軸です。前の目的と比較すると、後者は学習理論でより多く使用されます。

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

[証拠]

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

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

調査の結果、この固定点が以下のポリシーに関連付けられた値関数であることがわかります。

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

ベルマン再帰を展開することで、次のことが示せる。 $V^{*}$ これは、決定論的な政策の集合の中で、（すべての状態に対して同時に）確かに最適である。

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

次のような場合を考えてみましょう。 $\pi$ 確率的であるということは、取られた行動が $a:=\pi (s)$ は確率変数である。このような非決定論的な政策は決定論的な政策に支配されることを示すことができる。 $\pi ^{*}$ 次のように。

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

シミュレーターモデル

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

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

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

例

MDPの一例として、古典制御理論に由来する極平衡モデルが挙げられる。

この例では、

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

アルゴリズム

有限状態空間および有限行動空間を持つ MDP の解は、動的計画法などのさまざまな方法で見つけることができます。このセクションのアルゴリズムは、有限状態空間および有限行動空間を持ち、遷移確率と報酬関数が明示的に与えられた MDP に適用されますが、基本的な概念は、たとえば関数近似を使用して、他の問題クラスを扱うように拡張できます。また、可算無限状態空間および有限行動空間を持つプロセスの一部は、有限状態空間および有限行動空間を持つプロセスに正確に還元できます。^{[ 7 ]}

有限状態および有限行動MDPの最適ポリシーを計算するための標準的なアルゴリズム群は、状態と値によってインデックス付けされた2つの配列を格納する必要がある。 $V$ 実際の価値と政策を含む $\pi$ アクションが含まれています。アルゴリズムの最後に、 $\pi$ 解決策と $V(s)$ には、その状態からその解に従うことによって（平均して）得られる報酬の割引合計が含まれます。 $s$ 。

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

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

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

それらの順序はアルゴリズムのバリアントによって異なります。すべての状態に対して一度に実行することも、状態ごとに実行することもでき、また、一部の状態に対して他の状態よりも頻繁に実行することもできます。いずれのステップからも恒久的に除外される状態がない限り、アルゴリズムは最終的に正しい解に到達します。^{[ 8 ]}

注目すべき変種

価値反復

値反復法（ベルマン 1957 ）は、後方帰納法とも呼ばれ、 $\pi$ 関数は使用されません。代わりに、 $\pi (s)$ 計算範囲は $V(s)$ 必要なときにいつでも。 $\pi (s)$ 計算に $V(s)$ 結合されたステップを示します。

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

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

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

[証拠]

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

表記する $X_{a}^{V}(s):=\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)$ そして $({\mathcal {B}}V)(s):=\max _{a}X_{a}^{V}(s)$ 利便性のために。

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

方策反復法は、線形逆問題と非線形演算を効果的に交互に行うため、一種の緩和法と解釈できる。

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

政策反復が価値反復よりも高速になる場合もあるが（例えば、行動空間が状態空間よりも著しく大きい場合など）、通常、可能な状態の数が多い場合は、政策反復は価値反復よりも遅くなる。

修正されたポリシー反復

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

優先的に清掃を行う

このバリアントでは、アルゴリズムに基づいているかどうかにかかわらず、何らかの形で重要な状態にステップが優先的に適用されます（大きな変更がありました $V$ または $\pi$ （最近それらの州の周辺にいる）または使用状況に基づいて（それらの州は開始州に近いか、アルゴリズムを使用する個人またはプログラムにとって関心のある州である）。

計算複雑性

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

拡張と一般化

マルコフ決定過程は、プレイヤーが1人だけの確率ゲームである。

部分観測可能性

上記の解決策は、状態が $s$ 行動を起こす必要があるときにわかっている。そうでなければ $\pi (s)$ 計算できない。この仮定が成り立たない場合、その問題は部分観測マルコフ決定過程（POMDP）と呼ばれる。

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

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

一つの対策ではなく、複数の対策を講じることで、複数のコストが発生する。
CMDPは線形計画法でのみ解くことができ、動的計画法は適用できません。
最終的な政策は、開始時の状態によって決まる。

ラグランジュ乗数法はCMDP（条件付き動的計画法）に適用可能である。ラグランジュ乗数法に基づくアルゴリズムは数多く開発されている。

自然方策勾配主双対法。^{[ 18 ]}

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

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

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

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

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

どこ $0\leq \gamma <1.$

離散空間：線形計画法による定式化

状態空間と行動空間が有限であれば、線形計画法を用いて最適方策を見つけることができます。これは、最も初期に適用されたアプローチの1つです。ここではエルゴードモデルのみを考慮します。つまり、連続時間MDPは定常方策の下でエルゴード連続時間マルコフ連鎖になります。この仮定の下では、意思決定者は現在の状態であればいつでも意思決定を行うことができますが、複数の行動を取るメリットはありません。システムが現在の状態から別の状態に遷移しているときにのみ行動を取る方が良いでしょう。いくつかの条件下では、^[²⁰^]最適値関数が $V^{*}$ 国家から独立している $i$ すると、次の不等式が得られます。

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)

関数が存在する場合 $h$ 、それから ${\bar {V}}^{*}$ 最小になる $g$ 上記の式を満たす。 ${\bar {V}}^{*}$ 次のような線形計画モデルを用いることができる。

主線形計画法（P-LP）

{\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）

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

$y(i,a)$ D-LP の実行可能な解は、 $y(i,a)$ 非ネイティブであり、D-LP問題の制約を満たしている。実行可能な解 $y^{*}(i,a)$ D-LP に対して最適解であるとは、

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

すべての実行可能な解について $y(i,a)$ D-LPへ。最適な解が見つかったら $y^{*}(i,a)$ それを利用して最適な政策を確立することができる。

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

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

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

$D(\cdot )$ は終端報酬関数であり、 $s(t)$ はシステム状態ベクトルであり、 $a(t)$ これは、我々が探そうとしているシステム制御ベクトルです。 $f(\cdot )$ これは、状態ベクトルが時間とともにどのように変化するかを示しています。ハミルトン・ヤコビ・ベルマン方程式は次のとおりです。

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

方程式を解いて最適値関数を求めることができます $V^{*}$ これにより、任意の時点で最適な制御が得られる。 $t$ 、 $a(t)$ を通して $a(t)={\underset {a}{\text{argmax}}}(r(t,s,a)+{\frac {\partial V^{*}(t,s)}{\partial s}}f(t,s,a)).$

強化学習

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

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

離散型マルコフ決定過程のための強化学習

このセクションの目的のために、アクションを実行することに対応する別の関数を定義することが有用です。 $a$ そして、最適な方法（または現在採用している方針に従って）で継続する：

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

この機能も不明ですが、学習中の経験は $(s,a)$ ペア（結果とともに） $s'$ つまり、「私は国にいた」 $s$ そして私は試してみた $a$ そして $s'$ 発生した」。したがって、配列が得られます。 $Q$ そして、経験を利用してそれを直接更新します。これはQ学習として知られています。

その他の範囲

学習オートマトン

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

学習オートマトン理論において、確率オートマトンは以下の要素から構成される。

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

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

圏論的解釈

報酬以外にも、マルコフ決定過程 $(S,A,P)$ は圏論の観点から理解できる。すなわち、 ${\mathcal {A}}$ 生成集合Aを持つ自由モノイドを表す。DistをGiry モナドのKleisli 圏とする。すると、ファンクターは ${\mathcal {A}}\to \mathbf {Dist}$ 状態の集合Sと確率関数P の両方をエンコードします。

このようにして、マルコフ決定過程はモノイド（1つの対象を持つ圏）から任意の圏に一般化できる。この結果を次のように呼ぶことができる。 $({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )$ 文脈依存のマルコフ決定過程、なぜならあるオブジェクトから別のオブジェクトへ移動するから ${\mathcal {C}}$ 利用可能なアクションのセットと可能な状態のセットを変更します。

別表記法

MDP（マルコフ決定過程）の用語と表記法は完全には確立されていません。大きく分けて2つの流れがあり、1つは経済学などの分野における最大化問題に焦点を当て、行動、報酬、価値といった用語を用い、割引率を $β$ または $γ$ と呼びます。もう1つは工学や航海などの分野における最小化問題に焦点を当て、制御、コスト、所要コストといった用語を用い、割引率を $α$ と呼びます。さらに、遷移確率の表記法も様々です。

さらに、遷移確率は次のように表記されることもあります。 $\Pr(s,a,s')$ 、 $\Pr(s'\mid s,a)$ または、まれに、 $p_{s's}(a).$

参考文献

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

情報源

ベルマン、R. (1957)、動的計画法、プリンストン大学出版局、ISBN 978-0-486-42809-3{{citation}}ISBN/日付の不一致（ヘルプ）。ドーバー社ペーパーバック版（2003年）

さらに読む

Bellman, 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。
Meyn, SP (2007).複雑ネットワークの制御技術. Cambridge University Press. ISBN 978-0-521-88441-92010年6月19日にオリジナルからアーカイブされました。付録には「Meyn & Tweedie」の要約版が掲載されています。 2012年12月18日にオリジナルからアーカイブされました。
Puterman., ML (1994). Markov Decision Processes . Wiley.
Ross, SM (1983).確率的動的計画法入門(PDF) . Academic press. 2022年3月4日にオリジナル(PDF)からアーカイブ済み。 2019年1月19日取得。
Sutton, RS; Barto, AG (2017).強化学習入門. Cambridge, MA: The MIT Press.
Tijms., HC (2003).確率モデル入門. Wiley. ISBN 9780470864289。

[1] Puterman, Martin L. (1994). Markov decision processes: discrete stochastic dynamic programming . Wiley series in probability and mathematical statistics. Applied probability and statistics section. New York: Wiley. ISBN 978-0-471-61977-2。

[2] 尹博 (2021).低遅延高密度無線ネットワークにおけるエアタイム管理(博士論文). 日本: 京都大学.

[3] Schneider, S.; Wagner, DH (1957-02-26). "冗長システムにおけるエラー検出" . 1957年2月26日～28日開催の西部合同コンピュータ会議「信頼性のための技術 - IRE-AIEE-ACM '57 (Western)」で発表された論文集。ニューヨーク州ニューヨーク、米国：Association for Computing Machinery。pp. 115–121。doi : 10.1145 /1455567.1455587。ISBN 978-1-4503-7861-1。{{cite book}}ISBN /日付の不一致（ヘルプ）

[4] Bellman, Richard (1958-09-01). "動的計画法と確率的制御プロセス" . Information and Control . 1 (3): 228– 239. Bibcode : 1958InfCo...1..228B . doi : 10.1016/S0019-9958(58)80003-0 . ISSN 0019-9958 .

[:0-5] 1 2 Sutton, Richard S.; Barto, Andrew G. (2018).強化学習入門. 適応計算と機械学習シリーズ（第2版）. マサチューセッツ州ケンブリッジ：MIT Press. ISBN 978-0-262-03924-6。

[Kearns_Sparse-6] Kearns, Michael; Mansour, Yishay; Ng, Andrew (2002). "大規模マルコフ決定過程におけるほぼ最適な計画のためのスパースサンプリングアルゴリズム" . Machine Learning . 49 ( 193–208 ): 193–208 . doi : 10.1023/A:1017932429737 .

[Wrobel_1984-7] ローベル、A. (1984)。「有限の骨格を持つマルコフの意思決定モデルについて」。オペレーションズリサーチの時代。28 (1): 17–27 .土井: 10.1007/bf01919083。S2CID 2545336。

[8] 強化学習：理論とPython実装。北京：中国機械出版社。2019年。44ページ。ISBN 9787111631774。

[9] シャプレー、ロイド( 1953)。「確率ゲーム」。米国科学アカデミー紀要。39 ( 10 ) : 1095–1100。Bibcode : 1953PNAS ... 39.1095S。doi : 10.1073 / pnas.39.10.1095。PMC 1063912。PMID 16589380。

[10] カレンバーグ、ロデウィック（2002）。「有限状態および有限行動MDP」。ファインバーグ、ユージン A.、シュワルツ、アダム（編）。マルコフ決定過程ハンドブック：方法と応用。シュプリンガー。ISBN 978-0-7923-7459-6。

[11] ハワード、ロナルド A. (1960).動的計画法とマルコフ過程(PDF) . MIT Press.

[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] Papadimitriou, Christos ; Tsitsiklis, John (1987). "The Complexity of Markov Decision Processes" . Mathematics of Operations Research . 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). Constrained Markov decision processes . Vol. 7. CRC Press.

[18] Ding, Dongsheng; Zhang, Kaiqing; Jovanovic, Mihailo; Basar, Tamer (2020).制約付きマルコフ決定過程に対する自然方策勾配主双対法. ニューラル情報処理システムの進歩.

[19] Feyzabadi, S.; Carpin, S. (2014年8月18日～22日). 「階層的制約付きマルコフ決定過程を用いたリスク認識型経路計画」 . IEEE国際会議オートメーション科学および工学（CASE） . 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). "Learning Automata – A Survey". IEEE Transactions on Systems, Man, and Cybernetics . SMC-4 (4): 323– 334. Bibcode : 1974ITSMC...4..323N . CiteSeerX 10.1.1.295.2280 . doi : 10.1109/TSMC.1974.5408453 . ISSN 0018-9472 .

[NarendraEtAl1989-23] 1 2ナレンドラ、クンパティ S. ;タタチャー、アラバマ州マンダヤム (1989)。学習オートマトン: 概要。プレンティス・ホール。ISBN 9780134855585。

[FOOTNOTENarendraThathachar1974p.325_left-24] Narendra & Thathachar 1974、p.325 左。

[

[

[ 3 ]

[ 4 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]