マルコフ決定過程

マルコフ決定過程（マルコフけっていかてい、（英: Markov Decision Process, MDP）は、状態遷移が確率的に生じる動的システムの確率モデルであり、状態遷移がマルコフ性を満たすものをいう^[1]。

MDP は不確実性を伴う意思決定のモデリングにおける数学的枠組みとして、強化学習など動的計画法が適用される幅広い最適化問題の研究に活用されている^[1]。 MDP は少なくとも1950年代には知られていた^[2]が、研究の中核は1960年に出版された Ronald A. Howard の "Dynamic Programming and Markov Processes" に起因する^[3]。 MDP はロボット工学や自動制御、経済学、製造業を含む幅広い分野で用いられている。

概要

マルコフ決定過程は離散時間における確率制御過程 (stochastic control process) である。各時刻において過程 (process) はある状態 (state) を取り、意思決定者 (decision maker) はその状態において利用可能な行動 (action) を任意に選択する。その後過程はランダムに新しい状態へと遷移し、その際に意思決定者は状態遷移に対応した報酬 (reward) を受けとる。

遷移後の状態 $s'$ 、および得られる報酬の値 $r$ は現在の状態 $s$ と行動 $a$ のみに依存し、 $s$ と $a$ が与えられたもとでそれより過去の状態および行動と条件付き独立となる。言い換えると、マルコフ決定過程の状態遷移はマルコフ性を満たす。

マルコフ決定過程はマルコフ過程に（選択可能な）行動、および（行動を計画する動機を与える）報酬を追加し拡張したものであると解釈できる。逆に言えば、各ステップにとる行動がそのステップにおける状態のみ依存するとき、マルコフ決定過程は等価なマルコフ過程に置き換えることが出来る。

定義

マルコフ決定過程は四つ組 ${\textstyle (S,A,T,R)}$ で定義される。すなわち、以下の4要素でルールが表現される：

状態空間 S
行動空間 A
遷移関数 T
報酬関数 R

状態空間 S

状態空間（じょうたいくうかん、（英: state space）は空でない集合である^{[注 1]}。 $\textstyle S$ で表記され^[5]^[6]、状態集合（じょうたいしゅうごう）とも^[6]。

$\textstyle S$ の元 $\textstyle s$ は状態（じょうたい、（英: state）と呼ばれる^[5]^[6]。

典型的には、状態空間はシステム・環境が取りうる状態の全体と解釈される^[5]^[6]。意思決定によって状態は遷移していく^[7]。状態空間は「確率過程の状態空間」に相当する。

行動空間 A

行動空間（こうどうくうかん、（英: action space）は空でない集合である^{[注 1]}。 $\textstyle A$ で表記され^[8]、行動集合（こうどうしゅうごう）^[8]、決定空間（けっていくうかん）^[9]とも。

$\textstyle A$ の元 $\textstyle a$ は行動（こうどう、（英: action）^[8]^[10] あるいは決定（けってい）^[10]と呼ばれる。 $\textstyle s\in S$ で取れる行動の集合は $\textstyle A_{s}\subset A$ で表記される^[要出典]。

典型的には、行動空間は取りうる行動の全体と解釈される。意思決定者は行動空間からただ1つの行動を取り、それを反映して状態が遷移する^[7]。

遷移関数 T

遷移関数（せんいかんすう、（英: transition function）は関数 $\textstyle T\colon (S,A,S)\rightarrow [0,1]$ のうち、総和による制約を満たすものである^[要出典]。

典型的には、遷移関数はマルコフ性をもった状態遷移の表現と解釈される。例えば状態空間が有限な場合の $\textstyle T(s_{t},a_{t},s_{t+1})=0.1$ は「状態 $\textstyle s_{t}$ な意思決定者が行動 $\textstyle a_{t}$ を取った場合、状態 $\textstyle s_{t+1}$ へ遷移する確率は $\textstyle 10\%$ である」というルールと解釈される。引数の数がマルコフ性を反映していると解釈される。また $\textstyle T$ の終域が $\textstyle \{0,1\}$ の場合は決定論的な遷移をするルールだと解釈される^[11]。

任意の可測集合 $S'\subset S$ に対して状態遷移確率は $\Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{s'\in S'}T(s,a,s')\,ds'$ によって記述される。

報酬関数 R

報酬関数（ほうしゅうかんすう、（英: reward function）は $\textstyle R\colon (S,A)\rightarrow \mathbb {R}$ を満たす関数である^[12]。即時報酬（そくじほうしゅう、（英: immediate reward）^[要出典]、期待利得（きたいりとく、（英: expected reward）とも^[12]。

報酬関数に従う実現値 $\textstyle r$ は報酬（ほうしゅう、（英: reward）と呼ばれる^[13]。

典型的には、報酬関数は遷移に伴う報酬の期待値と解釈される^[12]^[14]。例えば $\textstyle R(s_{t},a_{t})=100$ は「状態 $\textstyle s_{t}$ において意思決定者が行動 $\textstyle a_{t}$ を取ると期待利得 $\textstyle 100$ が与えられる」というルールと解釈される。状態の遷移先が確率的に定まることを考慮して「期待」利得と理解される。報酬関数を $\textstyle R\colon (S,A,S)\rightarrow \mathbb {R}$ として遷移先ごとの利得を定義する流儀もある^[14]。

意思決定

マルコフ決定過程には行動空間 A の形で意思決定が組み込まれている。ある時点において意思決定者は $\textstyle A$ からただ 1 つの行動 $\textstyle a$ を取る。これによりどのような意思決定（の連続）がどのような状態遷移（の連続）を起こすか解析できる。

この意思決定を精緻化するうえで、しばしば方策 π が採用される。

方策 π

方策（ほうさく、（英: policy）は現在の状態に基づいて次に取る行動の割合を定める関数である^[15]。 $\textstyle \pi$ で表記され^[15]^[16]、政策（せいさく）とも^[15]。

$\textstyle \pi$ は $\pi \colon (S,A)\rightarrow \mathbb {R}$ であり、行動空間 $\textstyle A$ が高々可算集合であれば確率質量関数 $\pi \colon (S,A)\rightarrow [0,1]$ 、不可算集合であれば確率密度関数である。例えば $\textstyle A=\{a_{\mathrm {I} },a_{\mathrm {II} }\}$ として $\textstyle s_{t}=s$ のときの $\textstyle \pi$ を次で定義した場合、

\pi (s,a_{t})={\begin{cases}0.9,&{\text{if }}a_{t}=a_{\mathrm {I} }\\0.1,&{\text{if }}a_{t}=a_{\mathrm {II} }\\\end{cases}}

この $\textstyle \pi$ は「現在の状態が $\textstyle s$ なら、意思決定者は $\textstyle 90\%$ の確率で行動 $\textstyle a_{\mathrm {I} }$ を、 $\textstyle 10\%$ の確率で行動 $\textstyle a_{\mathrm {II} }$ を（確率的に）選ぶ」という意思決定を意味する（参考: ゲーム理論における混合戦略）。

$\textstyle \pi$ の終域が $\textstyle \{0,1\}$ の場合、意思決定者は決定論的な意思決定をする（例: $\textstyle s_{\mathrm {II} }$ には $\textstyle a_{\mathrm {II} }$ と決め打ちする）と解釈される。このタイプの方策は決定論的方策（けっていろんてきほうさく、（英: deterministic policy）と呼ばれる。この対比として確率的な意思決定を含みうる方策は確率的方策（かくりつてきほうさく、（英: stochastic policy）と呼ばれる。

利得

マルコフ決定過程には報酬関数 R の形で利得（りとく、（英: return）が組み込まれている。各時点での意思決定によって状態が遷移するとそのたびに報酬が発生する。これによりどのような意思決定（の連続）がどのような利得をもたらすか解析できる。

利得を精緻化するうえで、複数の指標が用いられる。

総期待利得

総期待利得（そうきたいりとく、（英: expected total reward）は期待利得の総和による指標である^[17]。 $\mathbb {E} _{\pi }{\bigg [}\sum _{\tau =1}^{H}r_{t+\tau }\mid s_{t}=s{\bigg ]}$ $\textstyle H$ は期間長である。 $\mathbb {E} _{\pi }[\cdot \mid s_{t}=s]$ は方策 $\pi$ のもとでの（条件付き）期待値である。また、期末で状態に応じた特別報酬を発生させる定式化もある^[18]。

$\textstyle H$ は有限期間とする場合が多い。無限期間の場合、特殊な条件を満たさないと意味をなさなくなる。

無限期間総割引期待利得

無限期間総割引期待利得（むげんきかんそうわりびききたいりとく、（英: expected discounted total reward over an infinite horizon）は無限期間における割引期待利得の総和による指標である^[19]。

「時刻 $\textstyle t$ における、将来にわたる割引報酬の合計 $\textstyle V_{t}$ 」を考える。 $\textstyle t$ を時刻、 $\textstyle r_{t}$ を $\textstyle t$ での報酬（確率変数）、 $H$ を評価区間、 $\textstyle \gamma \ (0<\gamma <1)$ を割引率（わりびきりつ、（英: discount rate）とする^[20]。 $\textstyle V_{t}$ は次で定義される^[20]：

V_{t}=r_{t}+\gamma r_{t+1}+\gamma ^{2}r_{t+2}\dots =\sum _{\tau =0}^{\infty }\gamma ^{\tau }r_{t+\tau }

確率変数の和である $\textstyle V_{t}$ もまた確率変数になる。その実現値は MDP によって規定される状態遷移確率や方策に基づいて確率的に変動する。

平均利得

平均利得（へいきんりとく、（英: long-run time average reward）は無限期間の総報酬を無限期間長で割った指標である^[21]。

問題設定

MDP における基本的な問題設定は、現在の状態が与えられたときに最良の方策 π を求めることである。 $\pi$ は、目的関数 (objective function) を最大化するようなものが選ばれる。目的関数には期待利得が用いられる。

有限の時間区間における利得を評価する問題設定は有限時間区間 (finite horizon) と呼ばれる。無限の時間区間の場合は無限時間区間 (infinite horizon) と呼ばれる。

価値関数

モデルのマルコフ性により、ある時刻における目的関数の値は方策 $\pi$ を固定した下で状態 $s_{t}\in S$ の関数とみなすことが出来る。このような考えのもと、ある方策 $\pi \colon S\times A\to [0,1]$ に対して定義される $V^{\pi }(s)=\mathbb {E} _{\pi }{\bigg [}\sum _{\tau =0}^{\infty }\gamma ^{\tau }r_{t+\tau +1}\mid s_{t}=s{\bigg ]}$ を 状態価値関数 (state-value function) と呼ぶ。状態価値関数は、現在の状態 $s$ からはじまり方策 $\pi$ によって行動を決定することで得られる（割引された）累積報酬の値であると解釈できる。この状態価値関数 $V^{\pi }(s)$ は、次の整合性条件を満たす。 $V^{\pi }(s)=\sum _{a\in A}\pi (s,a)\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V^{\pi }(s'){\Big )}$

任意の $\pi '$ および $s\in S$ に対し $V^{\pi ^{*}}(s)\geq V^{\pi '}(s)$ を満たす方策 $\pi ^{*}$ を最適方策 (optimal policy) と呼ぶ。また、最適方策のもとでの状態価値関数 $V^{*}(s)=V^{\pi ^{*}}(s)$ は特に最適状態価値関数 (optimal state-value function)と呼ばれる。最適状態価値関数は、次のベルマン方程式を満たす^[22]。 $V^{*}(s)=\max _{a\in A}\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V^{*}(s'){\Big )}$

アルゴリズム

MDP は線形計画法または動的計画法で解くことができる。ここでは後者によるアプローチを示す．

価値反復法

価値反復法 (value iteration)^[2]は後ろ向き帰納法 (backward induction) とも呼ばれ、ベルマン方程式を満たす価値関数を繰り返し計算により求める。ロイド・シャープレーが1953年に発表した確率ゲーム（英語版）に関する論文^[23]には価値反復法の特殊な場合が含まれるが、このことが認知されたのは後になってからである^[24]．

ステップ $i$ における価値関数の計算結果を $V_{i}(s)$ と表記すると、価値反復法における更新式はつぎのように記述される: $V_{i+1}(s)\leftarrow \max _{a\in A_{s}}\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V_{i}(s'){\Big )}\quad \forall s\in S$

上式をすべての状態において値が収束するまで繰り返したときの値を $V^{\infty }(s)$ とし、最適方策 $\pi ^{*}$ を次式で求める。

$\pi ^{*}(s)\leftarrow \arg \max _{a\in A_{s}}\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V^{\infty }(s'){\Big )}\quad \forall s\in S$

方策反復法

方策反復法 (policy iteration)^[3]では、方策固定の下で行われる価値関数の更新 (policy evaluation) と、価値関数固定のもとで行われる方策の更新 (policy improvement) を交互に行うことで最適方策を求める。

次の線形方程式を解き、価値関数を更新する
$V^{\pi }(s)=\sum _{a\in A}\pi (s,a)\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V^{\pi }(s'){\Big )}$
方策を次式で更新する
$\pi (s)\leftarrow \arg \max _{a\in A_{s}}\sum _{s'\in S}T(s,a,s'){\Big (}R(s,a,s')+\gamma V^{\pi }(s'){\Big )}\quad \forall s\in S$

これらの操作を $\pi$ がすべての状態に対し変化しなくなるまで繰り返すことで、最適方策を得る。方策反復法は離散値を取る方策の値が変化しなくなるという明確な終了条件を持つため有限時間でアルゴリズムが終了するという利点を持つ。

分類

有限マルコフ決定過程

状態空間 $S$ および行動空間 $A$ がともに有限集合であるような MDP は有限マルコフ決定過程 (finite Markov decision process; finite MDP) と呼ばれる。

状態空間が有限である場合においては、時刻 $t$ における状態遷移確率は遷移関数によって $\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)=T(s,a,s')$ と記述することが出来る。

拡張と一般化

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

→「部分観測マルコフ決定過程」も参照

MDP では方策 $\pi (s)$ を計算する際に現在の状態 $s$ が既知であることを仮定している。実際には状態観測に不確実性が伴う場合などこの仮定が成り立たない場合が多く、このような場合の一般化として部分観測マルコフ決定過程 (Partially Observable Markov Decision Process; POMDP) が用いられる。

強化学習

→「強化学習」および「Q学習」も参照

状態遷移確率 $T(s,a,s')$ や報酬関数 $R(s,a,s')$ が未知の場合，環境との相互作用を通じてこれらの情報を得ながら行動を決定する必要がしばしば生じる．このような問題は強化学習の枠組みで議論される^[25]．

強化学習における代表的な学習アルゴリズムはQ学習と呼ばれるものである。 Q学習では、行動価値関数 (action-value function) と呼ばれる関数 $Q^{\pi }(s,a)$ に着目する。ここで $Q^{\pi }(s,a)$ は次のように定義される: $Q^{\pi }(s,a)=\mathbb {E} _{\pi }[\sum _{t=0}^{\infty }\gamma ^{t}r_{t+1}|s_{0}=s,a_{0}=a]$

いま，最適方策のもとでの行動価値関数 $Q^{*}(s,a)=\max _{\pi }Q^{\pi }(s,a)$ は $V^{*}(s)=\max _{a}Q^{*}(s,a)$ を満たす。すなわち、 $Q^{*}$ を学習することができれば（モデルのパラメータを直接求めることなく）最適方策を獲得することができる。 Q学習では、各試行における遷移前後の状態と入力、および試行で得られる即時報酬の実現値をもとに $Q(s,a)$ の値を逐次更新する。実際の学習プロセスでは、すべての状態を十分サンプリングするため確率的なゆらぎを含むよう学習時の行動が選択される。

強化学習では最適化に必要なパラメータの学習を状態遷移確率・報酬関数を介することなくおこなうことが出来る（価値反復法や方策反復法ではそれらの明示的な仕様（各状態間の遷移可能性，報酬関数の関数形など）を与える必要がある）。状態数（および行動の選択肢）が膨大な場合、強化学習はしばしばニューラルネットワークなどの関数近似と組み合わせられる。

学習オートマトン

機械学習理論における MDP のもう一つの応用は学習オートマトン (Learning Automata) と呼ばれる。これは環境が確率的な挙動を示す場合における強化学習の一つでもある。学習オートマトンに関する最初の詳細な論文は 1974 年に Narendra と Thathachar によりまとめられた^[26]（そこでは有限状態オートマトンと明示的に記載されている）。強化学習と同様，学習オートマトンのアルゴリズムも確率や報酬が未知の場合の問題を解くことができる。 Q学習の違いは，価値関数ではく学習の結果を探すために行動の確率を直接求めることである。学習オートマトンは収束性が解析学の要領で厳密に証明されている^[27]．

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

制約付きマルコフ決定過程 (Constrained Markov Decision Process; CMDP) はマルコフ決定過程の拡張である。 MDP と CMDP には3つの基本的な違いがある^[28]:

ある行動をほかのものの代わりに適用した後で（複数の）コストが発生する
CMDP は線形計画法のみで解くことが出来る（動的計画法を用いることはできない）
終端時刻における方策が初期状態に依存する

CMDP の応用例は数多く存在し、最近ではロボット工学におけるモーションプランニングに用いられている^[29]。

脚注

[脚注の使い方]

注釈

1 2 濃度に関する制約は無い^[4]。

出典

1 2 強化学習では，環境のダイナミクスをマルコフ決定過程（Markov Decision Process：MDP）によってモデル化し，アルゴリズムを解析するのが一般的である(木村 2016, p. 12)
1 2 Bellman 1957.
1 2 Howard 1960.
↑ 状態空間については，以下の種類に分類できる。... 有限状態空間 ... 可算無限状態空間 ... 非可算無限状態空間 ... また，決定空間についても同様の区分ができる。(中出 2019, p. 8)
1 2 3 各時刻 $t$ で状態（state） $s_{t}$ を観測し ... 状態空間（state space） $S$ ：対象としているシステムの状態の集合である。(中出 2019, p. 8)
1 2 3 4 環境のとりうる ... 状態集合を $\textstyle {\mathsf {S}}=\{s_{1},s_{2},\dots ,s_{n}\}$ ... 環境中の状態 $\textstyle s\in {\mathsf {S}}$ (木村 2016, p. 12)
1 2 環境中の状態 $\textstyle s\in {\mathsf {S}}$ において，エージェントが行動 $\textstyle a$ を実行すると，環境は確率的に状態 $\textstyle s'\in {\mathsf {S}}$ へ遷移する．(木村 2016, p. 12)
1 2 3 エージェントがとる有限な行動集合を $\textstyle {\mathsf {A}}=\{a_{1},a_{2},\dots ,a_{l}\}$ と表す．... エージェントが行動 $\textstyle a$ を実行する(木村 2016, p. 12)
↑ 決定空間（action space） $A(s)$ ：状態 $s\in S$ を観測したとき可能な決定の集合である。(中出 2019, p. 8)
1 2 各時刻 $t$ で ... 決定（action，行動と呼ぶこともある） $a_{t}$ を行う。(中出 2019, p. 8)
↑ マルコフ決定過程 ... 離散的な時間ステップ $\textstyle t$ ごとに ... エージェントは現在の状態 $\textstyle s_{t}$ を観測し、とるべき行動 $\textstyle a_{t}$ を選択する ... 次の状態 $\textstyle s_{t+1}=\delta (s_{t},a_{t})$ となる ... 関数 $\textstyle \delta$ ... は non-deterministic であってよいし, エージェントにとって未知でよいp.4 より引用。櫻井, 彰人 (2015), 強化学習, 慶應義塾大学講義『情報意味論』, 慶應義塾大学
1 2 3 単位時間当り期待利得（expected reward） $r(s,a)$ ：状態 $s\in S$ を観測して決定 $a\in A(s)$ をとったとき，つぎの時刻までに受け取る利得の期待値である。(中出 2019, p. 8)
↑ 環境は確率的に ... 遷移する．... このとき環境からエージェントへ報酬 $r$ が確率的に与えられる(木村 2016, p. 12)
1 2 報酬 $r$ ... その期待値を条件付期待値 $R(s,a,s')$ により表す．(木村 2016, p. 12)
1 2 3 政策（policy）とは，与えられた履歴に対し各決定を行う確率を定めることを示しており ... 政策は履歴から決定に関する確率空間への写像となる。... 政策 $\pi$ (中出 2019, p. 9)
↑ エージェントにおける状態集合から行動集合への写像関数を政策と呼び $\pi$ と表す．(木村 2016, p. 12)
↑ 有限期間総期待利得（expected total reward over a finite horizon） $E^{\pi }\left[\sum _{t=0}^{T-1}r(s_{t},a_{t})+K(s_{T})\right]$ (中出 2019, p. 9)
↑ 時刻 $T$ において決定はとらず，状態 $s_{T}$ に対する利得 $K(s_{T})$ を受け取り確率過程は停止する。(中出 2019, p. 9)
↑ 無限期間総割引期待利得（expected discounted total reward over an infinite horizon） $E^{\pi }\left[\sum _{t=0}^{\infty }\gamma ^{t}r(s_{t},a_{t})\right]$ ... $\gamma$ は $0<\gamma <1$ を満たす実数であり，割引率と呼ぶ。
1 2 割引報酬合計による評価を利得とする場合が多い．ある時刻 $t$ の状態，あるいはそのとき実行した行動の利得 $V_{t}$ を以下で定義する． $\textstyle V_{t}=r_{t}+\gamma r_{t+1}+\gamma ^{2}r_{t+2}\dots =\sum _{\tau =0}^{\infty }\gamma ^{\tau }r_{t+\tau }$ ただし， $r_{t}$ は時刻 $t$ の報酬， $\gamma$ は割引率 $\textstyle \gamma \ (0\leq \gamma <1)$ である．(木村 2016, p. 12)
↑ （無限期間）平均利得（long-run time average reward） $\lim _{T\rightarrow \infty }{\frac {1}{T}}E^{\pi }\left[\sum _{t=0}^{T-1}r(s_{t},a_{t})\right]$ (中出 2019, p. 9)
↑ Suton 1998.
↑ Shapley 1953.
↑ Kallenberg 2002.
↑ Sutton & Barto 1998.
↑ Narendra & Thathachar 1974.
↑ Narendra & Thathachar 1989.
↑ Altman 1999.
↑ Feyzabadi & Carpin 2014.

参考文献

木村, 元 (2016), “3-3-2 強化学習”, 知識の森 (電子情報通信学会)
中出, 康一 (2019-04-05). マルコフ決定過程 - 理論とアルゴリズム -. 情報科学における確率モデル. 4. コロナ社. ISBN 978-4-339-02834-8

Bellman, R. (1957). “A Markovian Decision Process”. Journal of Mathematics and Mechanics 6.
Howard, Ronald. A. (1960). Dynamic Programming and Markov Processes. The M.I.T. Press
Shapley, Lloyd. (1953). “Stochastic Games”. Proceedings of National Academy of Science 39: 1095–1100.
Kallenberg, Lodewijk. (2002). “Finite state and action MDPs”. Handbook of Markov decision processes: methods and applications. Springer. ISBN 0-7923-7459-2
Sutton, R. S.; Barto, A. G. (1998). Reinforcement Learning: An Introduction. Cambridge, MA: The MIT Press
Narendra, K. S.; Thathachar, M. A. L. (1974). “Learning Automata - A Survey”. IEEE Transactions on Systems, Man, and Cybernetics SMC-4 (4): 323–334. doi:10.1109/TSMC.1974.5408453. ISSN 0018-9472.
Narendra, Kumpati S.; Thathachar, Mandayam A. L. (1989). Learning automata: An introduction. Prentice Hall. ISBN 9780134855585
Altman, Eitan (1999). Constrained Markov decision processes. 7. CRC Press
Feyzabadi, S.; Carpin, S. (2014). “Risk-aware path planning using hierarchical constrained Markov Decision Processes”. Automation Science and Engineering (CASE). IEEE International Conference. pp. 297, 303. doi:10.1109/CoASE.2014.6899341.
木村, 元 (2013). “《第1回》強化学習の基礎”. 計測と制御 (計測自動制御学会) 52 (1): 72-77. NAID 10031140795. https://doi.org/10.11499/sicejl.52.72.

外部リンク

Reinforcement Learning An Introduction by Richard S. Sutton and Andrew G. Barto
Learning to Solve Markovian Decision Processes by Satinder P. Singh
Optimal Adaptive Policies for Markov Decision Processes by Burnetas and Katehakis (1997)
ソフトウェアパッケージ
- MDP Toolbox for MATLAB, GNU Octave, Scilab and R The Markov Decision Processes (MDP) Toolbox.
- MDP Toolbox for Matlab - An excellent tutorial and Matlab toolbox for working with MDPs.
- MDP Toolbox for Python A package for solving MDPs
- SPUDD A structured MDP solver for download by Jesse Hoey

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

[card-5] 1 2 濃度に関する制約は無い^[4]。

[:0-1] 1 2 強化学習では，環境のダイナミクスをマルコフ決定過程（Markov Decision Process：MDP）によってモデル化し，アルゴリズムを解析するのが一般的である(木村 2016, p. 12)

[FOOTNOTEBellman1957-2] 1 2 Bellman 1957.

[FOOTNOTEHoward1960-3] 1 2 Howard 1960.

[4] 状態空間については，以下の種類に分類できる。... 有限状態空間 ... 可算無限状態空間 ... 非可算無限状態空間 ... また，決定空間についても同様の区分ができる。(中出 2019, p. 8)

[:5-6] 1 2 3 各時刻 $t$ で状態（state） $s_{t}$ を観測し ... 状態空間（state space） $S$ ：対象としているシステムの状態の集合である。(中出 2019, p. 8)

[:1-7] 1 2 3 4 環境のとりうる ... 状態集合を $\textstyle {\mathsf {S}}=\{s_{1},s_{2},\dots ,s_{n}\}$ ... 環境中の状態 $\textstyle s\in {\mathsf {S}}$ (木村 2016, p. 12)

[:3-8] 1 2 環境中の状態 $\textstyle s\in {\mathsf {S}}$ において，エージェントが行動 $\textstyle a$ を実行すると，環境は確率的に状態 $\textstyle s'\in {\mathsf {S}}$ へ遷移する．(木村 2016, p. 12)

[:2-9] 1 2 3 エージェントがとる有限な行動集合を $\textstyle {\mathsf {A}}=\{a_{1},a_{2},\dots ,a_{l}\}$ と表す．... エージェントが行動 $\textstyle a$ を実行する(木村 2016, p. 12)

[10] 決定空間（action space） $A(s)$ ：状態 $s\in S$ を観測したとき可能な決定の集合である。(中出 2019, p. 8)

[:6-11] 1 2 各時刻 $t$ で ... 決定（action，行動と呼ぶこともある） $a_{t}$ を行う。(中出 2019, p. 8)

[12] マルコフ決定過程 ... 離散的な時間ステップ $\textstyle t$ ごとに ... エージェントは現在の状態 $\textstyle s_{t}$ を観測し、とるべき行動 $\textstyle a_{t}$ を選択する ... 次の状態 $\textstyle s_{t+1}=\delta (s_{t},a_{t})$ となる ... 関数 $\textstyle \delta$ ... は non-deterministic であってよいし, エージェントにとって未知でよいp.4 より引用。櫻井, 彰人 (2015), 強化学習, 慶應義塾大学講義『情報意味論』, 慶應義塾大学

[:7-13] 1 2 3 単位時間当り期待利得（expected reward） $r(s,a)$ ：状態 $s\in S$ を観測して決定 $a\in A(s)$ をとったとき，つぎの時刻までに受け取る利得の期待値である。(中出 2019, p. 8)

[14] 環境は確率的に ... 遷移する．... このとき環境からエージェントへ報酬 $r$ が確率的に与えられる(木村 2016, p. 12)

[:8-15] 1 2 報酬 $r$ ... その期待値を条件付期待値 $R(s,a,s')$ により表す．(木村 2016, p. 12)

[:9-16] 1 2 3 政策（policy）とは，与えられた履歴に対し各決定を行う確率を定めることを示しており ... 政策は履歴から決定に関する確率空間への写像となる。... 政策 $\pi$ (中出 2019, p. 9)

[17] エージェントにおける状態集合から行動集合への写像関数を政策と呼び $\pi$ と表す．(木村 2016, p. 12)

[18] 有限期間総期待利得（expected total reward over a finite horizon） $E^{\pi }\left[\sum _{t=0}^{T-1}r(s_{t},a_{t})+K(s_{T})\right]$ (中出 2019, p. 9)

[19] 時刻 $T$ において決定はとらず，状態 $s_{T}$ に対する利得 $K(s_{T})$ を受け取り確率過程は停止する。(中出 2019, p. 9)

[20] 無限期間総割引期待利得（expected discounted total reward over an infinite horizon） $E^{\pi }\left[\sum _{t=0}^{\infty }\gamma ^{t}r(s_{t},a_{t})\right]$ ... $\gamma$ は $0<\gamma <1$ を満たす実数であり，割引率と呼ぶ。

[:4-21] 1 2 割引報酬合計による評価を利得とする場合が多い．ある時刻 $t$ の状態，あるいはそのとき実行した行動の利得 $V_{t}$ を以下で定義する． $\textstyle V_{t}=r_{t}+\gamma r_{t+1}+\gamma ^{2}r_{t+2}\dots =\sum _{\tau =0}^{\infty }\gamma ^{\tau }r_{t+\tau }$ ただし， $r_{t}$ は時刻 $t$ の報酬， $\gamma$ は割引率 $\textstyle \gamma \ (0\leq \gamma <1)$ である．(木村 2016, p. 12)

[22] （無限期間）平均利得（long-run time average reward） $\lim _{T\rightarrow \infty }{\frac {1}{T}}E^{\pi }\left[\sum _{t=0}^{T-1}r(s_{t},a_{t})\right]$ (中出 2019, p. 9)

[FOOTNOTESuton1998-23] Suton 1998.

[FOOTNOTEShapley1953-24] Shapley 1953.

[FOOTNOTEKallenberg2002-25] Kallenberg 2002.

[FOOTNOTESuttonBarto1998-26] Sutton & Barto 1998.

[FOOTNOTENarendraThathachar1974-27] Narendra & Thathachar 1974.

[FOOTNOTENarendraThathachar1989-28] Narendra & Thathachar 1989.

[FOOTNOTEAltman1999-29] Altman 1999.

[FOOTNOTEFeyzabadiCarpin2014-30] Feyzabadi & Carpin 2014.

[1]

[2]

[3]

[注 1]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[4]

概要

定義