強化学習基礎（メモ書き） - DeepLearningを勉強する人

強化学習基礎

MDP→TD→Q-Learning→DQN手前まで、強化学習の基本的なことをかいつまんだまとめ
（自分用の自己満メモ）

素晴らしい講義
David Silver氏による強化学習講義
これにほぼ対応した素晴らしい演習問題+α
GitHub - dennybritz/reinforcement-learning: Implementation of Reinforcement Learning Algorithms. Python, OpenAI Gym, Tensorflow. Exercises and Solutions to accompany Sutton's Book and David Silver's course.

Malkov Decision Process (MDP)

完全に観測可能(fully observable)な環境を表す過程

MP (Malkov Process, Malkov Chain)

Malkov Property

${ \displaystyle \mathbb{P} \lbrack S_{t+1} | S_{t} \rbrack = \mathbb{P} \lbrack S_{t+1} | S_{1}, ..., S_{t} \rbrack }$
これの意味するところは、未来が現在のみに依存し、過去とは独立しているということ.

MPは ${ \langle \mathcal{S}, \mathcal{P} \rangle }$ の組で定義され、 ${\mathcal{S}}$ は有限の状態集合、 ${\mathcal{P}}$ は状態遷移確率行列で、
${\displaystyle \mathcal{P}_{ss'} = \mathbb{P} \lbrack S_{t+1} = s' | S_{t} = s \rbrack }$
である.

MRP (Malkov Reward Process)

MPにスカラー値が加わったもので、 ${ \langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \rangle }$ の四つ組で定義される.
${\mathcal{R}}$ はreward function(報酬関数)で、 ${\mathcal{R}_s = \mathbb{E} \lbrack R_{t+1} | S_t = s \rbrack}$
${\gamma}$ はdiscount factor(割引率)で、 ${\gamma \in \lbrack 0, 1 \rbrack}$ である.

Return

ここでreturnという量を定義する.
return ${G_t}$ とは、時刻 ${t}$ からの割り引かれた報酬の合計値.
つまり、
${ \displaystyle G_t = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} }$

なぜ割引？

discount factorの直感的なイメージは、将来の報酬の、現在の値とみることができる.

returnの発散を回避する
将来への不確実性
即時的な報酬の方が重要な場合など
動物は基本的に即時的な報酬の方を重要視する
など

Value Function

returnの期待値としてvalue function(価値関数)を定義する.
${\displaystyle v(s) = \mathbb{E} \lbrack G_t | S_t = s \rbrack }$

Bellman Equation

このvalue functionは二つの量に分解することができる.
${\displaystyle \begin {equation} \begin {split} v(s) &= \mathbb{E} \lbrack G_t | S_t = s \rbrack \\ &= \mathbb{E} \lbrack R_{t+1} + \gamma G_{t+1} | S_t = s \rbrack \\ &= \mathbb{E} \lbrack R_{t+1} + \gamma v_(S_{t+1}) | S_t = s \rbrack \end {split} \end{equation} }$
(returnの定義からすぐ分かる)
つまり、即時的な報酬 ${R_{t+1}}$ と次の状態の割り引かれた価値 ${\gamma v_(S_{t+1})}$ に分解できた.

MDP (Malkov Decision Process)

MRPに決定が加わったもので、 ${ \langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle }$ の五つ組で定義される.
${ \mathcal{A} }$ は、有限な行動の集合
状態遷移確率と報酬も行動に依存するようになるので、
${\displaystyle \mathcal{P}_{ss'}^a = \mathbb{P} \lbrack S_{t+1} = s' | S_{t} = s, A_{t} = a \rbrack }$
${\mathcal{R}_s^a = \mathbb{E} \lbrack R_{t+1} | S_t = s, A_t = a \rbrack}$
これが環境に対応する.

Policy

行動が加わったのでpolicyというものを定義する
${\displaystyle \pi(a|s) = \mathbb{P} \lbrack A_t = a | S_t = s \rbrack }$
これは、ある状態での取り得る行動の確率分布を表し、エージェントの振る舞いを決定する.

state-value & action-value function

MDPにおけるstate-value function(状態価値関数)とは
${\displaystyle v_{\pi}(s) = \mathbb{E}_{\pi} \lbrack G_t | S_t = s \rbrack }$
これはpolicy ${\pi}$ に従った場合の、状態 ${s}$ からの将来のreturnの期待値で、その状態の価値を表す.
MDPにおけるaction-value function(行動価値関数)とは
${\displaystyle q_{\pi}(s, a) = \mathbb{E}_{\pi} \lbrack G_t | S_t = s, A_t = a \rbrack }$
これはpolicy ${\pi}$ に従い、状態 ${s}$ にいる時に行動 ${a}$ を取る時の将来のreturnの期待値で、その行動の価値を表す.

Bellman Expectation Equation

さて、MRPの場合と同様にこれらは、即時的な報酬と、割引された未来の報酬に分割することができる
${\displaystyle v_{\pi}(s) = \mathbb{E}_{\pi} \lbrack R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s \rbrack }$
${\displaystyle q_{\pi}(s, a) = \mathbb{E}_{\pi} \lbrack R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a \rbrack }$
${\pi}$ を定義したので、状態遷移確率と併せて期待値の部分を展開してみる.
${\displaystyle \begin{equation} \begin{split} v_{\pi}(s) &= \sum_{a \in \mathcal{A} } \pi(a|s)q_{\pi}(s, a) \\ &= \sum_{a \in \mathcal{A}} \pi(a|s) \biggl( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{\pi}(s') \biggr) \end{split} \end{equation} }$
${\displaystyle \begin{equation} \begin{split} q_{\pi}(s, a) &= \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{\pi}(s') \\ &= \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a \sum_{a' \in \mathcal{A} } \pi(a'|s')q_{\pi}(s', a') \end{split} \end{equation} }$

Optimal value function

最適なstate-value functionとaction-value functionを次のように定義する.
${ \displaystyle v_{*}(s) = \max_{\pi} v_{\pi}(s) \\ \displaystyle q_{*}(s, a) = \max_{\pi} q_{\pi}(s, a) }$

Optimal Policy

policyに関して次の半順序を定義する
${\displaystyle \pi \geq \pi^{'} if v_{\pi} \geq v_{\pi^{'}}, \forall s }$
この時、最適なpolicyとは
${\displaystyle \pi_{*} \geq \pi, \forall \pi }$
であり、このようなpolicyが存在し、 ${\pi_{*}}$ は ${v_{*}(s)}$ と ${q_{*}(s, a)}$ を達成するという定理がある.
また、最適なpolicyは以下のように得ることができ、決定的なpolicyである.
${\displaystyle \begin{eqnarray} \pi_{*}(a|s) = \left\{ \begin{array} {} 1 & if \; a = \displaystyle \arg \max_{a \in \mathcal{A}} q_{*}(s, a) \\ 0 & otherwise \end{array} \right. \end{eqnarray} }$

Bellman Optimality Equation

最適なpolicyを仮定した時のBellman Equation. Bellman Expectation Equationと区別しておくことがとても重要
${ \displaystyle \begin{equation} \begin{split} v_{*}(s) &= \max_{a} q_{*}(s, a) \\ &= \max_{a} \biggl( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{*}(s') \biggr) \end{split} \end{equation} }$
${ \begin{equation} \begin{split} \displaystyle q_{*}(s, a) &= \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{*}(s') \\ &= \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a \max_{a'} q_{*}(s', a') \end{split} \end{equation} }$

Policy/Value Iteration（簡単に）

強化学習において、Dynamic Programming (Full backup)によるアプローチには、大きく次の２種類のアプローチが存在する.

Policy Iteration

Policy EvaluationとPolicy Improvementを繰り返してpolicyを最適化する.
Policy Evaluation: 現在のpolicyを評価することのみを行う.
これはBellman Expectation Equationに基づいて行われる.
Policy Improvement: 評価に基づいてpolicyの更新を行う.

Value Iteration

明示的にpolicyは持たない.
value functionをBellman Optimality Equationに基づいて更新することで、最適なvalue functionに近づけていく.

Model-free Prediction (Policy EvaluationのSample backup版)

Model-freeというのは、環境のダイナミクスを利用しない（知らなくて良い）という意味.
Dynamic ProgrammingでのPlanningと比較すると分かりやすいが、例えばDPは状態遷移確率行列が必要になる.

Predictionでは、value functionを予測することを目的とする. （最適化することは後述のControlの領分）

基本的にMonte-Carlo(MC)とTemporal-Difference(TD)というアプローチが存在する.
どちらの手法もイテレーティブに価値関数を更新して評価するのだが、以下の形で表現できる.
${\displaystyle V(S_t) \leftarrow V(S_t) + \alpha ( return - V(S_t)) }$
真のreturnの方向に修正していく. が、真returnは未知なのでこれを何かしらに置き換える.
MCの場合はreturnとして実際に観測した ${G_t}$ を利用するのに対して、TD(0)の場合はreturnの予測値 ${R_{t+1} + \gamma V(S_{t+1}) }$ を使う.
したがって、MCでは ${G_t}$ を得るために"episodic"でないといけないし、offlineであり、完全なepisodeを必要とする.
TD(0)の場合は、bootstrappingするのでonlineで、しかも不完全なepisodeから学習することが可能である.

MCには深く立ち入らないでTDに焦点を当てていく.
改めてTD(0)の更新式は、
${\displaystyle V(S_t) \leftarrow V(S_t) + \alpha ( R_{t+1} + \gamma V(S_{t+1}) - V(S_t)) }$
で、 ${R_{t+1} + \gamma V(S_{t+1}) }$ をTD Target、 ${\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) }$ をTD Errorと呼ぶ
TD( ${\lambda)}$ に拡張できるのだが、とりあえずここではTD(0)にとどめる.

Model-free Control (Policy Improvementの Sample backup版)

value functionを最適化することを考える.
今まで、 ${V(S)}$ 、つまりstate-valueについて考えていたが、ここでgreedy policy(最大値を与える行動を常に取るpolicy)を想定してみると、
${\displaystyle \pi(s) = \arg \max_{a \in \mathcal{A}} \mathcal{R}_s^a + \mathcal{P}_{ss'}^a V(S') }$
である.
状態遷移確率 ${\mathcal{P}_{ss'}}$ 、つまり環境のモデルが必要になってきてしまう.
一方で、action-valueの場合は、
${\displaystyle \pi(s) = \arg \max_{a \in \mathcal{A}} Q(s, a) }$
これはmodel-free.
したがって、action-valueに基づいて更新を行うことにする.

${\epsilon }$ -greedy exploration

ここで ${\epsilon }$ -greedyという考え方を定義する.
確率 ${1-\epsilon }$ でgreedyな行動を、確率 ${\epsilon }$ でランダムな行動を取るというもの.

${ \displaystyle \begin{eqnarray} \pi(a|s) = \left\{ \begin{array} {} \frac{\epsilon} {m} + 1 - \epsilon & if \; a^{*} = \displaystyle \arg \max_{a \in \mathcal{A}} Q(s, a) \\ \frac{\epsilon} {m} & otherwise \end{array} \right. \end{eqnarray} }$
${m}$ は行動数
これによってPolicy Improvementを行えば ${v_{\pi'}(s) \geq v_{\pi}(s)}$ となるという定理がある.

GLIE (Greedy in the Limit with Infinite Exploration)

全てのstate-actionペアが無限回探索される時、policyがgreedy policyに収束するような探索方法.

例えば、 ${\epsilon}$ -greedyで ${\epsilon}$ が0に収束するようなものならば、GLIEである.

On-Policy TD Control (Policy IterationのSample backup版)

Sarsa(0)

Policy Evaluationは以下の更新式に基づく、
${\displaystyle Q(s, a) \leftarrow Q(s, a) + \alpha (R + \gamma Q(s', a') - Q(s, a)) }$
Policy Improvementは ${\epsilon}$ -greedy policy に基づいて更新する
returnの予測値は現在の状態 ${s}$ において行動 ${a}$ を取った時の次の状態 ${s'}$ において、policy ${\pi}$ に従って行動 ${a'}$ を選んだ場合の予測値になっている.
ここで、(サンプルした)Bellman Expectation Equationに基づいていることを再確認したい.
GLIEかつステップサイズ ${\alpha}$ がRobbins-Monro(略)になっていれば最適なaction-value functionに収束する定理が存在する.

Off-Policy Control (Value IterationのSample backup版)

Off-Policyでは、target policy ${\pi(a|s)}$ を評価するのだが、行動自体はbehavior policy ${\mu(a|s)}$ に従って行う.
なぜそんなことをするのか？？

ひとつのpolicyに従いながら、複数のpolicyについて学習できる
探索的なpolicyに従いながら、最適なpolicyについて学習できる
例えば、他の人がどう動いているのだろうということを学ぶイメージ

Importance Sampling

さて、確率分布 ${\pi(a|s)}$ に関する期待値を確率分布 ${\mu(a|s)}$ で取る場合、Importance Samplingという操作を行う.
${\displaystyle \mathbb{E}_{x \sim \pi} \lbrack f(x) \rbrack = \sum \pi(x) f(x) = \sum \mu(x) \frac {\pi(x)} {\mu(x)} f(x) = \mathbb{E}_{x \sim \mu} \lbrack \frac {\pi(x)} {\mu(x)} f(x) \rbrack }$

例えば、TD(0)のPolicy Evaluationはインクリメンタルな更新なので、以下のようになる
${\displaystyle V(S_t) \leftarrow V(S_t) + \alpha \biggl( \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}(R_{t+1} + \gamma V(S_{t+1})) - V(S_t) \biggr) }$

だがしかし、こんなことは必要ない、そうQ-Learningならね.

Q-Learning

${\displaystyle Q(S_t,A_t) \leftarrow Q(S_t, A_t) + \alpha (R + \gamma Q(S_{t+1}, A') - Q(S_t, A_t)) }$
returnの予測値は、状態 ${S_t}$ において ${\mu}$ に従って行動 ${A_t}$ を取った時の次の状態 ${S_{t+1}}$ において、 ${\pi}$ に従って行動 ${A'}$ を取る時の予測値となっている.

${\pi}$ と ${\mu}$ を具体的に定義する.

${\pi}$ はgreedy policy、 $\pi(S_{t+1}) = \arg \max_{a'} Q(S_{t+1}, a')$
${\mu}$ は ${\epsilon}$ -greedy policy

従って、
${\displaystyle R_{t+1} + \gamma Q(S_{t+1}, A') = R_{t+1} + \gamma Q(S_{t+1}, \arg \max_{a'} Q(S_{t+1}, a') ) = R_{t+1} + \max_{a'} \gamma Q(S_{t+1}, a') }$
ここで、(サンプルした)Bellman Optimality Equationに基づいていることを再確認しておきたい.
Q-Learningは最適なaction-value functionに収束するという定理がある.

関数近似

今までの話をスケールアップさせる上では、value functionを近似することが必要不可欠となる.
ちなみに、今までの収束の話は関数近似した場合、必ずしも成立しなくなる.

確率的勾配降下法(SGD)

今、 ${\mathbf{w}}$ でパラメータ化されたvalue functionを ${\hat{v}(S, \mathbf{w}) }$ 、真のvalue functionを ${v_{\pi}(S)}$ とした時、以下の最小化問題を解きたい.
${\displaystyle \min_{\mathbf{w}} J(\mathbf{w}) = \min_{\mathbf{w}} \mathbb{E}_{\pi} \lbrack ( v_{\pi}(S) - \hat{v}(S, \mathbf{w}) )^2\rbrack }$

${\mathbf{w}}$ に関する勾配は、
${\displaystyle \nabla_{\mathbf{w}} J(\mathbf{w}) = 2 \mathbb{E}_{\pi} \lbrack (v_{\pi}(S) - \hat{v}(S, \mathbf{w})) \nabla_{\mathbf{w}} \hat{v}(S, \mathbf{w}) \rbrack }$
よって、SDGの各ステップは以下の更新を行う
${\displaystyle \mathbf{w} \leftarrow \mathbf{w} - \frac {1}{2} \alpha \nabla_{\mathbf{w}} J(\mathbf{w}) = \mathbf{w} - \alpha (v_{\pi}(S) - \hat{v}(S, \mathbf{w})) \nabla_{\mathbf{w}} \hat{v}(S, \mathbf{w}) }$
期待値でないのは"確率的"勾配降下であるから(勾配をサンプリグする).
インクリメンタルな平均値の更新をイメージすれば、これが期待値になっていくことが直感的にわかる.

ここにおいても、 ${v_{\pi}(S)}$ を何かしらに置き換えるわけだが、TD(0)の場合(Policy Evaluation)は、TD Targetで置き換えて、
${\displaystyle \mathbf{w} \leftarrow \mathbf{w} - \alpha \biggl(R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}) - \hat{v}(S_t, \mathbf{w}) \biggr) \nabla_{\mathbf{w}} \hat{v}(S_t, \mathbf{w}) }$
これは、action-valueについても同様で、
${\displaystyle \mathbf{w} \leftarrow \mathbf{w} - \alpha \biggl(R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1}, \mathbf{w}) - \hat{q}(S_t, A_t, \mathbf{w}) \biggr) \nabla_{\mathbf{w}} \hat{q}(S_t, A_t, \mathbf{w}) }$

ではQ-Learningにおいては...? → DQN