状況設定

大前提として、マルコフモデル を仮定する：将来の状態（State） $s_{t+1}$ は現在の状態 $s_t$ だけに依存して決まり、それより過去の状態 $s_{t-1},s_{t-2},\cdots$ には寄らない。

ある時点の状態 $s$ において、次の行動（Action） $a$ をあるルールに基づいて決定し、実行する。
行動 $a$ の結果、状態 $s$ は新たな状態 $s’$ に遷移（Transition） し、このとき 即時報酬（Reward） $R(s,s’)$ を受け取る。

一般に、遷移先の状態 $s’$ は確定しておらず確率的に決まる。以後、状態 $s$ において行動 $a$ を取ったときに状態 $s’$ に遷移する条件付き確率を $T(s’\vert s,a)$ で表す。

強化学習の目的

$s_t \to s_{t+1} \to s_{t+2} \to \cdots$ と状態の遷移を繰り返す中で、報酬 $R$ の総和 $G$ を最大化すること。

時刻 $t$ 以降、終了時刻 $T$ まで状態遷移を繰り返したときの報酬の総和を $G_t$ とすると、

\[G_t = R(s_t,s_{t+1}) + R(s_{t+1},s_{t+2}) + R(s_{t+2},s_{t+3}) + \cdots + R(s_{T-1},s_T)\]

これを直接最大化できれば一番嬉しいが、前述の通り、状態 $s$ で行動 $a$ を取った結果遷移する状態 $s’$ は確率的に決まるため、$s_{t+1},s_{t+2},\cdots,s_{T}$ は不確定。
→ 未来の報酬は推測して見積もるしかない

推測の精度は未来になるほど不確かになるので、不確かさを表す 割引率 $\gamma\ (0 \lt \gamma \lt 1)$ を導入して、

\[G_t = R(s_t,s_{t+1}) + \gamma\ R(s_{t+1},s_{t+2}) + \gamma^2\ R(s_{t+2},s_{t+3}) + \cdots + \gamma^{T-t-1}\ R(s_{T-1},s_T)\]

の最大化を目指す。この式は時刻 $t+1$ 以降の報酬の総和 $G_{t+1}$ を用いて漸化式形式に変形できる：

\[\begin{eqnarray} G_t &=& R(s_t,s_{t+1}) + \gamma\ \left\{R(s_{t+1},s_{t+2}) + \gamma\ R(s_{t+2},s_{t+3}) + \cdots + \gamma^{T-(t+1)-1}\ R(s_{T-1},s_T) \right\} \\ &=& R(s_t,s_{t+1}) + \gamma\ G_{t+1} \tag{1} \end{eqnarray}\]

この「ある状態以降に得られる報酬の総和」を見積もった値を、価値（Value） と呼ぶ。

方策と Bellman 方程式

強化学習が想定する状況では、状態 $s$ に対して、得られる価値が大きくなるよう、あるルールに基づいて次の行動 $a$ を決定する。この行動選択のルールを方策（Policy） $\pi$ と呼ぶ。
一般には、状態 $s$ に対してただ1つの行動を決定するのではなく、確率的に次の行動を選択することが多い。
すなわち、方策 $\pi$ の実体は、状態 $s$ のときに行動 $a$ を選択する条件付き確率 $\pi(a \vert s)$。

前節で価値 $G_t$ を定義したのと同様に、状態 $s$ から方策 $\pi$ に基づいて行動を決定したときの価値を $V_\pi(s)$ とすると、

\[V_\pi(s) = E \left[ R(s,s') + \gamma\ V_\pi(s') \right] \tag{2}\]

$E[\cdots]$ は期待値を表す。遷移先の状態 $s’$ が確率的に決まる不確定なパラメータであるため、期待値を取ることでその状態の価値としている。
$(2)$ 式の解釈：ある状態の価値 = そこからの遷移で得られる即時報酬と、遷移先状態の価値を併せたもの（の期待値）

期待値を計算するには、元の状態 $s$ から遷移する可能性がある全ての遷移先状態 $s’$ について、その遷移確率 $P(s,s’)$ による重み付けをして和を取れば良い：

\[V_\pi(s) = \sum_{s'} P(s,s') \left\{ R(s,s') + \gamma\ V_\pi(s') \right\}\]

遷移確率 $P(s,s’)$ は、状態 $s$ において取りうるあらゆる行動 $a$ について、その行動が取られ、かつその結果遷移先が $s’$ となる確率の和を取ったものだから、

\[P(s,s') = \sum_a \pi(a \vert s) T(s' \vert s,a)\]

以上により、

\[\begin{eqnarray} V_\pi(s) &=& \sum_{s'} \sum_a \pi(a \vert s) T(s' \vert s,a) \left\{ R(s,s') + \gamma\ V_\pi(s') \right\} \\ &=& \sum_a \pi(a \vert s) \sum_{s'} T(s' \vert s,a) \left\{ R(s,s') + \gamma\ V_\pi(s') \right\} \tag{3} \end{eqnarray}\]

この式を Bellman 方程式 と呼ぶ。

状態価値と行動価値

Bellman 方程式 $(3)$ において、遷移先状態 $s’$ についての和の部分を

\[Q_\pi(s,a) := \sum_{s'} T(s' \vert s,a) \left\{ R(s,s') + \gamma\ V_\pi(s') \right\} \tag{4}\]

とおくと、$Q_\pi(s,a)$ は状態 $s$ において行動 $a$ を取ったときに得られる報酬の期待値となる。
これは言い換えれば「状態 $s$ において行動 $a$ が持つ価値」と考えることもできるので、これを 行動価値 と呼ぶ。
また、行動価値との対比で、状態 $s$ のみで決まる価値 $V_\pi(s)$ を 状態価値 と呼ぶ。

$(4)$ を Bellman 方程式 $(3)$ に代入すれば、

\[V_\pi(s) = \sum_a \pi(a \vert s) Q_\pi(s,a) \tag{5}\]

$(4),(5)$ は状態価値と行動価値を変換する式になっている。

$(5)$ の $s$ を $s’$ に置き換えて $(4)$ 右辺に代入すれば

\[Q_\pi(s,a) = \sum_{s'} T(s' \vert s,a) \left\{ R(s,s') + \gamma\ \sum_{a'} \pi(a' \vert s') Q_\pi(s',a') \right\} \tag{6}\]

となり、行動価値で見た漸化式が得られる。

Policy ベースと Value ベース

Value ベースの強化学習：行動選択の方策 $\pi$ として、「常に価値の期待値が最大となる行動を取る」というものを採用し、行動の評価方法のみを学習する
- 価値反復法など
Policy ベースの強化学習：行動の評価方法だけでなく、行動選択の方策 $\pi$ 自体も学習により更新していく手法
- 方策反復法など

Value ベースの手法の場合、常に価値を最大化する方策となるので、$(3)$ 式は以下の Bellman 最適方程式 に書き換えられる：

\[\begin{eqnarray} V(s) &=& \max_a \left\{ \sum_{s'} T(s' \vert s,a) \left\{ R(s,s') + \gamma\ V_\pi(s') \right\} \right\} \\ &=& \max_a \left\{ Q_\pi(s,a) \right\} \end{eqnarray} \tag{7}\]

ここで $\displaystyle \max_a { f(a) }$ は、変数 $a$（ここでは行動）に関する $f(a)$ の最大値を意味する。
すなわち、行動価値 $Q_\pi$ を最大にするような行動 $a$ を代入する。

モデルベースとモデルフリー

モデルベースの強化学習：状態遷移確率 $T(s’\vert s,a)$ と即時報酬 $R(s,s’)$ が分かっている事が前提
モデルフリーの強化学習：状態遷移確率 $T(s’\vert s,a)$ と即時報酬 $R(s,s’)$ が未知であることが前提（やってみないと分からない）。実際の経験（試行）から学習を行う

現実世界の問題では、実際の環境を正確にモデル化することが困難なケースが多いため、モデルフリーの手法が用いられることが多い。

モデルフリー：経験から学習する

観点1：探索と活用のバランス

遷移確率や報酬が不明なため、ランダムに行動して経験を蓄積する 探索（Exploration） と、得た経験から効率的に報酬を得る 活用（Exploitation） をバランス良く行いながら報酬の最大化を目指す。

探索と活用のトレードオフを調整する手法として、ε-greedy アルゴリズムがある。