MDPによる強化学習：環境モデル、動的計画法、状態遷移確率、利得、ポリシー、価値関数

　時刻tでの決定がそれ以降の状況に影響を与える意思決定プロセスであるマルコフ決定プロセス（MDP)を基に、強化学習を数式化する。
　開始状態を$${S_0}$$とおく。エージェントは、時刻$${t}$$の状態
$${S_t}$$から動作$${A_t}$$を決定し、環境はその動作を受けてエージェントに報酬$${R_{t+1}}$$を返す。これを終了時間$${T}$$まで続け、それを一連のエピソードと呼ぶ。
　$${S_t, A_t, R_{t+1}}$$は確率変数で、マルコフ決定プロセスを採用していることから、$${S_t, R_{t+1}}$$はその一つ前の時間の$${S_{t-1}}$$とエージェントの行動$${A_t}$$の条件付き確率として記述される。これを持って、環境モデルが定義される。
$${Pr(s',r|s,a)\stackrel{\text{def}}{=}Pr(S_{t+1}=s', R_{t+1}=r| S_t=s, A_t=a)}$$
　現実的に言えば、この環境モデルを持っている学習モデルは少なく、環境モデルを要求する強化学習、環境モデルを学習する強化学習法は、Model-Base、環境モデルを必要としない強化学習をモデルフリーと呼ぶ。
　環境モデルが与えられている場合、動的計画法で強化学習を行うことができる。動的計画法とは、複雑な問題をより小さい部分に分割して解く再帰問題に帰結される。ただし、動的計画法が部分問題の結果を保存し、同じ問題に対した時に以前に保存した結果を使うことで、計算時間の短縮を行なっている。
　特定の状態において、ある行動が実行されるか否かの2択である場合、環境モデルは$${Pr(s',r|s,a)=0 {\text{or} 1}}$$となり、決定論的に振る舞う。それ以外の場合では、環境は確率論的な振る舞いをし、報酬を足し上げることで、状態遷移確率が記述される。
$${Pr(s'|s,a)=\sum_{r\in R}Pr(s',r|s,a)}$$
決定論であるとき、$${Pr(s'|s,a)=\sum_{r\in R}Pr(s',r|s,a)=0+1=1}$$で状態遷移確率は１である。

利得

　ある時刻$${t}$$における利得$${G_t}$$は、その時刻以降に受け取る報酬に割引率$${\gamma, 0\le\gamma\le 1}$$をかけた総和で与えられる。
$${G_t=R_{t+1}+\gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}\gamma^{k}G_{t+k+1}}$$
　利得は再帰的にも表現でき、
$${G_t=R_{t+1}+ \gamma(R_{t+2}+ \gamma R_{t+3}) + \dots=r +\gamma G_{t+1}}$$
ここで、即時報酬$${R_{t+1}=r}$$としている。

ポリシー

エージェントは状態から次に取る行動を、ポリシー$${\pi(a|s)}$$に従って決める。
$${\pi(a|s)\stackrel{\text{def}}{=}Pr(A_t=a|S_t=s)}$$

価値関数

状態価値関数$${\mu_{pi}(s)}$$は、ポリシー$${\pi}$$に従った時の利得$${G_t}$$の期待値で与えられる。
$${\nu_{\pi}(s)\stackrel{\text{def}}{=}E_{\pi}[G_t|S_t=s]= E_{\pi}[\sum_{k=0}\gamma^k R_{t+k+1}|S_t=s]}$$
状態と行動をペアにした価値関数は行動価値関数$${q_{\pi}(s,a)}$$と呼ばれ、状態$${S_t=s}$$、行動$${A_t=a}$$においての利得の期待値で与えられる。
$${q_{\pi}(s,a)\stackrel{\text{def}}{=}E_{\pi}[G_t|S_t=s,A_t=a]= E_{\pi}[\sum_{k=0}\gamma^k R_{t+k+1}|S_t=s,A_t=a]}$$
　上記の式から直感的に、行動価値関数をポリシーをかけて$${a}$$で足し上げれば、状態価値関数となることがわかる。
$${\nu_{\pi}(s)=\sum_{a\in A}\pi(a|s)q_{\pi}(s,a)}$$