概要

強化学習理論の基礎2の続きです。
3の範囲は、Function Approximationです。
4はこちら。

2ではModel-Freeのアルゴリズムについて学習しましたが、価値関数を要素とするテーブルを使ったものでした。
そのため、状態やアクションが無限に近く、複雑な問題に対しては適用が難しいという欠点がありました。
その欠点を解消するために利用するため、今回はFunction Approximationを学習します。

Function Approximationとは

Q-Learningまでは、全ての状態に対応する価値関数($V(s)$)や全ての状態/アクションに対応する価値関数($Q(s,a)$)を、それぞれを1つの要素とする表として利用し学習していた。
しかし、現実の問題を考えると、状態はほぼ無限に存在するため、メモリや学習速度といった理由から上記のようなテーブル探索による学習は実践的なではない。

その問題を解決するために、Function Approximationを導入する。

Value Function Approximation

Value Function Approximationは、各価値関数を求めるのではなく、おおよその価値関数を使って、各状態の本当の価値関数を推定しながら学習を進める。(価値関数の一般化)
Value Function Approximationの背景には、ある環境における1つ1つの状態は全く違うということはなく、ある程度似通っているという考えがある。

\hat{v}(s, w) \approx v_ \pi (s) \\
\hat{q}(s, a, w) \approx q_ \pi (s,a)

状態価値関数と行動価値関数のFunction Approximationは以上のようになる。
ここで$w$は重みとなるパラメーターであり、ニューラルネットワークなどによって表現され、これを使って価値関数の一般化を行う。
価値関数を一般化することはメモリの節約だけでなく、学習データには含まれなかった状態、または、状態/アクションのペアについても推測が可能になるという利点がある。
$w$の更新は、MCやTDを使って行う。

Value Function Approximationは3つの種類がある。
1つ目は、状態$s$を入力として、その状態の価値(その先の最大報酬合計)である$\hat{v}(s, w)$が出力される。
2つ目は、状態$s$とアクション$a$のペアを入力として、その状態におけるそのアクションの価値である$\hat{q}(s, a, w)$が出力される。
3つ目は、状態$s$を入力として、その状態においてとり得るアクション全ての価値$\hat{q}(s, a_1, w) \cdots \hat{q}(s, a_m, w)$が出力される。

上記を踏まえた上で重要になるのは、どのFunction Approximatorを使えば良いのかということである。
ここでは、微分可能な線型結合とニューラルネットワークに絞って考慮することにする。
その理由は、すでに$w$の変化がどのように出力に影響を及ぼすか(勾配)ということが明らかだからである。
また、強化学習の性質上、非定常で独立同分布ではない(マルコフ性のため)データに対して適したFunction Approximatorを選ばなければならないという理由もある。

Incremental Methods

勾配降下

Incremental Methodsに入る前に勾配降下について確認する。(機械学習でも必ず使うので知っていたら飛ばしてください)
例として、$J(w)$をwによって微分可能な関数と仮定する。($w$はparameter vector)
$J(w)$の勾配(行列)を定義すると以下のようになる。

\nabla _w J(w) = 
\begin{pmatrix}
\frac{\partial J(w)}{\partial w_1} \\
\vdots \\
\frac{\partial J(w)}{\partial w_n}
\end{pmatrix}

ここで、$J(w)$の最小値を探すため、$w$を勾配の傾きの方向に調節する。

\Delta w = - \frac{1}{2} \alpha \nabla _w J(w)

$ \alpha $はステップサイズ(学習率)である。
マイナスを掛けているのは、簡単に言うと$J(w)$が大きかったら$w$を減らし、$J(w)$が小さかったら$w$を増やすように調節するためである。
また、$\frac{1}{2}$を掛けているのは、誤差関数に二乗誤差を使う際に微分しやすくするためである。(二乗したものを微分して前に出た2を打ち消す)
勾配降下法は、局所最小値を求めることが可能である。

そして、強化学習に勾配降下法の考えを取り入れる。
ゴールは、本当の価値関数($v_ \pi (s)$)と近似した価値関数($\hat {v} (s, w)$)の平均二乗誤差(mean squared error)を最小にするような$w$を見つけることである。
ここでは$v_ \pi (s)$が与えられると仮定し、勾配を以下のように定義する。

J(w) = E_ \pi [(v_ \pi (S) - \hat {v} (S, w))^2 ]

勾配降下を使うと以下のように$w$の更新を行うことができる。

\Delta w = \alpha E_ \pi [(v_ \pi (S) - \hat {v} (S, w)) \nabla _w \hat {v} (S, w)]

$v_ \pi (S) - \hat{v} (S, w)$の部分が誤差、∇$\hat{v} (S, w) $の部分が勾配を表す。
これにより誤差を勾配の方向に従って減少させるよう$w$を更新しているのがわかる。
勾配に$v_ \pi (S) - \hat{v} (S, w)$ではなく、$ \hat{v} (S, w)$のみを用いているのは、$v_ \pi (S)$はパラメータによらず不変なので、勾配は$\hat {v} (S, w)$のみで十分なためである。

次に確率的勾配降下法(Stochastic Gradient Descent)を使って、Onlineで$w$を更新する。

\Delta w = \alpha (v_ \pi (S) - \hat {v} (S, w)) \nabla _w \hat {v} (S, w)

Feature Vector

$v_ \pi (s)$が与えられると仮定しない場合に進む前に、feature vectorについて確認する。
feature vectorとは、各状態の特徴(feature)を表す変数の行列(ベクトル)であり、どのような物でも良い。
例えば、ある場所から現在の状態(位置)の距離や株価のトレンドなどである。
feature vectorは学習の効率をよくするために用いられる。

このfeature vectorを利用して、$v_ \pi (s)$を利用しないアルゴリズムを確認する。
最もシンプルなのは、近似した関数を重み(weight vector)とfeature vectorの加重和として表す方法である。(Linear Value Function Approximation)

\hat{v}(S, w) = x(S)^T w = \sum ^n _{j=1}x_j(S)w_j

$x$はfeature vectorを表す。
すうると、目的関数(二乗誤差)は以下のように定義できる。

J(w) = E_ \pi [(v_ \pi (S) - x(S)^T w)^2]

この時、確率的勾配降下法による最適化は、局所的な最適解ではなく、大域的な最適解に導かれる。
上記の目的関数は$w$についての2次式と考えられるので、以下のように重みは更新される。

\nabla _w \hat{v}(S, w) = x(S) \\
\Delta w = \alpha (v_ \pi (S) - \hat {v} (S, w))x(S)

$\hat{v}(S, w)$は$x(S)^T w$なので、勾配はfeature vectorの$x(S)$となり、学習率、予測誤差と共にそれを用いて重みの更新を行う。
$x(S)$で誤差への影響力が強い箇所と掛け合わされる$w$が更新されることになる。

ここまでくると、Linear Function Approximationの特殊なケースが、基礎2までで見てきたテーブル探索であると説明できる。
$x(S)$は各状態ごとに存在するので、現在の状態($s_t$)の時、$x(s_t)$のみが1となり、その他の$x(S)$は全て0になるような場合、重み$w_t$以外の$w$は更新されない。
そのため$w$が状態ごとの価値を表すテーブルとなり、テーブルの更新と同じことになる。

Incremental Prediction Algorithms

feature vectorを学習したことで、$v_ \pi (s)$(=教師データ)なしのアルゴリズムの準備が整った。
強化学習は、教師データは与えられず、報酬のみが手がかりとなる。
そのため、今までズルをして使用してきた$v_ \pi (s)$の代わりに、$v_ \pi (s)$の見積もりであるターゲットをアルゴリズムごとに指定する。
MCは報酬合計である$G_t$、TD(0)はTD-target($R_{t+1} + \gamma \hat {v} (S_{t+1}, w)$)、TD(λ)はλ-return($G^ \lambda _t$)となる。
それぞれの更新は以下のように行う。

\Delta w = \alpha (G_t - \hat {v} (S_t, w)) \nabla _w \hat {v} (S_t, w) \\
\Delta w = \alpha ((R_{t+1} + \gamma \hat {v} (S_{t+1}, w)) - \hat {v} (S_t, w)) \nabla _w \hat {v} (S_t, w) \\
\Delta w = \alpha (G^ \lambda _t - \hat {v} (S_t, w)) \nabla _w \hat {v} (S_t, w)

各ターゲットが$v_ \pi (s)$の代わりとなるので、それらを教師データとして誤差を減らす。

MCから順に確認していく。
$G_t$は、$v_ \pi (S_t)$からサンプリングした実際のデータであるため、バイアスはないがノイズが含まれる。
そのため、これらのデータは教師あり学習の訓練データとして利用することができる。($〈S_1, G_1〉, 〈S_2, G_2〉 \cdots 〈S_T, G_T〉$のデータセット)
1番シンプルなLinear Monte-Carlo policy evaluationは、このような重みの更新を行う。

\begin{align}
\Delta w &= \alpha (G_t - \hat {v} (S_t, w)) \nabla _w \hat {v} (S_t, w) \\
&= \alpha (G_t - \hat {v} (S_t, w)) x(S_t)
\end{align}

Linear MCは、局所解に収束する。(線形なら大域解)

次はTD(0)である。
TD-target($R_{t+1} + \gamma \hat {v} (S_{t+1}, w)$)は、バイアス付きの$v_ \pi (S_t)$のサンプルデータである。(TDの項でも確認したが、推測値のため)
しかし、このTD-targetも訓練データとして使用可能である。($〈S_1, R_2 + \gamma \hat {v} (S_2, w)〉, 〈S_2, R_3 + \gamma \hat {v} (S_3, w)〉 \cdots 〈S_{T-1}, R_T + \gamma \hat {v} (S_T, w)〉$のデータセット)
TD(0)で最もシンプルなLinear TD(0)の重みの更新は以下のようになる。

\begin{align}
\Delta w &= \alpha (R + \gamma \hat {v} (S', w) - \hat {v} (S, w)) \nabla _w \hat {v} (S, w) \\
&= \alpha \delta x(S)
\end{align}

Linear TD(0)は大域解に(ほぼ)収束する。

最後にTD(λ)について見てみる。
λ-return($G^ \lambda _t$)もTD(0)と同様に、バイアス付きのサンプルデータである。
また同様に、訓練データとして使用可能である。

Forward-view TD(λ)は、同様に以下のようになる。

\begin{align}
\Delta w &= \alpha (G^ \lambda _t - \hat {v} (S_t, w)) \nabla _w \hat {v} (S_t, w) \\
&= \alpha (G^ \lambda _t - \hat {v} (S_t, w)) x(S_t)
\end{align}

Backward-view TD(λ)では、Eligibility tracesの更新にfeature vector($x(S_t)$)を使う。
$x(S_t)$は今まで見てきた全てのfeatureの情報が含まれる。(状態の出現頻度と時間の情報)
そのため、より多く訪れたり最近訪れた状態の情報をEligibility tracesが持つことになる。
その結果、feature valueが高い部分の重みがより大きく更新されることになる。

\delta _t = R_{t+1} + \hat {v} (S_{t+1}, w) - \hat {v} (S_t, w) \\
E_t = \gamma \lambda E_{t-1} + x(S_t) \\
\Delta w = \alpha \delta _t E_t

Forward-view TD(λ)とBackward-view TD(λ)の重みは最終的に同じになる。

Incremental Control Algorithms

ここまでは、State Value Function Approximationをみてきた。
次に、Action Value Function Approximationを確認する。
基本的には、$\hat{v}(S, w)$が$\hat{q}(S, A, w)$になることだけしか変わらない。
二乗誤差を小さくすること、局所解を見つけるために確率的勾配降下法を利用することも同じである。

\hat{q}(S, A, w) \approx q_ \pi (S, A) \\
J(w) = E_ \pi [(q_ \pi (S, A) - \hat{q}(S, A, w))^2] \\
- \frac{1}{2} \nabla _w J(w) = (q_ \pi (S, A) - \hat{q}(S, A, w))\nabla _w \hat{q}(S, A, w) \\
\Delta w = \alpha (q_ \pi (S, A) - \hat{q}(S, A, w))\nabla _w \hat{q}(S, A, w)

まず、線形のFunction Approximationを確認する。
feature Vector($x(S, A)$)は、状態だけでなく、アクションの特徴の情報も保持するようになる。
状態価値関数の際と同じように、Function Approximatorは重み$w$とfeature vector($x(S, A)$)の加重和となる。

\hat{q}(S, A, w) = x(S, A)^T w = \sum ^n _{j=1} x_j (S, A) w_j

そのため、勾配及び勾配降下は以下のように行う。

\nabla _w \hat{q}(S, A, w) = x(S,A) \\
\Delta w = \alpha (q_ \pi (S, A) - \hat{q}(S, A, w))x(S, A)

MC、TD(0)、Forward-view TD(λ)、Backward-view TD(λ)の重み更新は、Predictionと同様に以下のように行う。(Incremental Control)
MC

\Delta w = \alpha (G_t - \hat{q}(S_t, A_t, w)) \nabla _w \hat{q}(S_t, A_t, w) \\

TD(0)

\Delta w = \alpha (R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1}, w) - \hat{q}(S_t, A_t, w)) \nabla _w \hat{q}(S_t, A_t, w)

Forward-view TD(λ)

\Delta w = \alpha (q^ \lambda _t - \hat{q}(S_t, A_t, w)) \nabla _w \hat{q}(S_t, A_t, w)

Backward-view TD(λ)

\delta _t = R_{t+1} + \hat{q}(S_{t+1}, A_{t+1}, w) - \hat{q}(S_t, A_t, w) \\
E_t = \gamma \lambda E_{t-1} + \nabla _w \hat{q}(S_t, A_t, w) \\
\Delta w = \alpha \delta _t E_t

収束

Incremental Methodsのアルゴリズムは以上だが、注意しなければいけない点がある。
まず、MCは学習に時間がかかりすぎる、分散が大きすぎるといった点により、実践的には使えない。
しかし、TDもアルゴリズムによっては最適解(またはそれに近い値)に収束しない場合がある。
Predictionを行う時の解の収束について示したのが、以下の表である。

On/Off Policy	アルゴリズム	テーブル探索	線形	非線形
On Policy	MC	○	○	○
	TD(0)	○	○	×
	TD(λ)	○	○	×
Off Policy	MC	○	○	○
	TD(0)	○	×	×
	TD(λ)	○	×	×

○は収束することが保証されていることを表し、×は保証されないことを示している。(理論上は)
TDが収束しなくなるのは、Bootstrapによって分散が大きくなるためである。
これを解決するのが、Gradient TDと呼ばれるアルゴリズムである。(詳しくは調べてください。。)
TDはいかなる目的関数の勾配にも追従しないが、Gradient TDは本当のBellman Errorの勾配に従って重みの更新を行う(らしい)。
そのため、非線形であろうと線形であろうと最終的に最適解に収束する(らしい)。

次にControlを確認する。
まず問題として、ControlのアルゴリズムにFunction Approximationを利用した場合、更新後の方策が本当によりよい方策となっているか保証することはできない。そのため、最適な価値関数に近づいたとしても、方策の更新によって遠のくといったことが起きる。それを以下の図では(○)で表す。(講義ではChatters around near- optimal value functionと言っていた)

アルゴリズム	テーブル探索	線形	非線形
MC Control	○	(○)	×
Sarsa	○	(○)	×
Q-Learning	○	×	×
Gradient Q-Learning	○	○	×

Batch Methods

Incremental Methodsでは、1ステップごとに重みの更新をしていたため、それまでの経験を全て捨て去ってしまうことになる。(=サンプルを効率的に利用しているとは言えない)
Batch Methodsではエージェントの経験のセット(Batch、訓練データ)を最大限利用し、最適な価値関数を見つける。

Least Squares Prediction

Value Function Approximatorの定義はIncremental Methodsと同じである。

\hat{v}(s, w) \approx v_ \pi (s)

ここでもまずは最適化された価値関数($v_\pi$)が与えられていると仮定する。
すると、エージェントの経験$D$は、以下のような状態と価値のペアのセットと考えることができる。

D = {〈s_1, v^\pi _1〉, 〈s_2, v^\pi _2〉, \cdots , 〈s_T, v^\pi _T〉}

改めて問題を確認すると、経験$D$(全訓練データ)に対して最も誤差の少ない$\hat{v}(s, w)$に導くパラメーター$w$とを見つけることである。
最もシンプルな考えは、各タイムステップごとに$v_\pi$と$\hat{v}(s, w)$の誤差(二乗誤差)を合計したものを小さくしていくというものであり、これはLeast Squares Algorithms(最小二乗法)と呼ばれる考え方である。

\begin{align}
LS(w) &= \sum ^T _{t=1} (v^\pi _t - \hat{v}(s_t, w))^2 \\
&= E_D [(v^\pi - \hat{v}(s, w))^2] 
\end{align}

$E_D$は、経験$D$から得られる$v_\pi$に対する$\hat{v}(s, w)$の誤差の予測を表す。

次に、訓練データを効率的に利用するための手段として、Experience Replayについて確認する。
Experience Replayでは、訓練データのセット$D$を保持し、その中からランダムにデータ($〈s, v^\pi〉$)を取り出して学習する。
この場合、訓練データ=教師データとなり、教師データとの誤差を最小にするように学習していくため、教師あり学習と同じことをしていると言える。
Experience Replayを利用した確率的勾配降下法による重みの更新は以下のように行われ、$LS(w)$が最小になるように収束する。

\Delta w = \alpha (v^\pi - \hat{v}(s, w)) \nabla _w \hat{v}(s, w)

Experience Replayと固定したQ-targetsを使ったアルゴリズムとして、Deep Q-Network(DQN)がある。
DQNは以下の手順で更新される。

ε-greedy policyに従って、アクションを実施する
その際、現在の状態、実行したアクション、即時報酬、遷移先の状態のセット($s_t,a_t,r_{t+1},s_{t+1}$)を replay memory($D$)に格納する
1と2を繰り返しサンプルの取得を終えたら、$D$からいくつかのサンプルを取得する(mini-batch)
更新前の重み$w^-$を利用してQ-targetsを計算する(mini-batchを学習し終えるまで$w^-$は固定化されている)
4で得たQ-targetsとQ-Networkの二乗誤差を最適化する(確率的勾配降下法を使う)
3から5を繰り返す

L_i (w_i) = E_{s,a,r,s' \sim D_i} [(r + \gamma \: max_{a'} Q(s', a', w^- _i) - Q(s, a, w_i))^2]

DQNが他のFunction Approximationより実践的なのは、それらより分散が大きくならないためである。
分散が小さくなる要因は、Experience Replayと固定したQ-targetsにある。
Experience Replayは、始めから終わりまでのパスにそって学習するのではなく、ランダムに選択しながら学習するので、各状態ごとの相関を少なくできる。
またQ-targetsを固定する(=$w^-$を固定=Q-Networkを2つ持つ)ことで、ステップごとに更新した後の重みに対してbootstrapを行わないため、学習が安定する。
TDでは誤差を求める際の両方の項を同時に更新していたため、学習するたびにターゲットも更新されることになっていた。そのためにTDでは、非線形のモデルの学習が不可能であった。Q-targetsを古い重みで固定するのはそれを防ぐためである。

Linear Least Squares Prediction

Experience Replayは最適解に到達できるが、膨大な数のイテレーションが必要になる。
その解決策として、Linear Value Function Approximation($\hat{v}(s, w) = x(s)^T w $)を使う方法がある。
$LS(w)$が最小の値をとる=0を考え、その式を展開していく。

\begin{align}
E_D [\Delta w]  &= 0 \\
\alpha \sum ^T _{t=1} x(s_t)(v^\pi _t - x(s_t)^T w) &= 0 \\
\sum ^T _{t=1} x(s_t) v^\pi _t &= \sum ^T _{t=1} x(s_t) x(s_t)^T w \\
w &= (\sum ^T _{t=1} x(s_t) x(s_t)^T w)^{-1} \sum ^T _{t=1} x(s_t) v^\pi _t
\end{align}

以上より、feature vectorのテーブルさえあれば、feature vectorから直接重みの更新が可能になり、二乗誤差を使った学習よりも効率的な学習が可能になる。
Linear Value Function Approximationはテーブルを使った学習だが、テーブルの大きさはfeature vectorの数に比例するので、feature vectorが大きくなければ大きなコストにならない。($O(N^3)$、Sherman-Morrisonの公式を使った場合$O(N^2)$)

上記では最適化された価値関数が与えられた場合を想定したが、これを利用したMCやTDに適用することができる(LSMC, LSTD, LSTD(λ))が、詳しい数式は省略する。

Linear Value Function Approximationは非線形なモデルには適用できないが(Linear=線形)、LSMC、LSTD、LSTD(λ)は全てOff Policyでも最適解に収束する。

On/Off Policy	アルゴリズム	テーブル探索	線形	非線形
On Policy	MC	○	○	○
	LSMC	○	○	-
	TD	○	○	×
	LSTD	○	○	-
Off Policy	MC	○	○	○
	LSMC	○	○	-
	TD	○	×	×
	LSTD	○	○	-

Least Squares Control

最小二乗法を使ったControlは、ほぼPredictionの状態価値関数を行動価値関数に置き換えるだけである。

ある方策($\pi $)によって取得したサンプルを利用して最適な行動価値関数($q_\pi (s,a)$)を近似するとき、Function Approximatorは$\hat{q} _\pi (s,a,w)$と表す。
Linear Value Function Approximationを利用する場合は、以下のように表せる。

\hat{q} _\pi (s,a,w) = x(s,a)^T w \approx q_\pi (s,a)

経験$D$(訓練データセット)は、このようになる。

D = {〈(s_1, a_1), v^\pi _1〉, 〈(s_2, a_2), v^\pi _2〉, \cdots , 〈(s_T, a_T), v^\pi _T〉}

ここまでで準備ができたので、Least Squares Policy Iteration(LSPI)について考える。
Policy Iterationは、Policy evaluationとPolicy improvementの2ステップを繰り返して学習した。
LSPIでは、Policy evaluationにLeast Squares Q-Learningを利用する。(Policy improvementはGreedy policy improvement)

Policy evaluationでは経験を効率的に活用したいが、方策の改善(Policy improvement)も行う必要がある。
これは、別の方策によって取得した経験を利用して新しい方策の学習を行うということであり、Off Policyの学習ということになる。
そこで、Q-Learningと同様の方法を導入する。
まず、ある方策($\pi _{old}$)でサンプルを取得する。($S_t, A_t, R_{t+1}, S_{t+1} \sim \pi _{old}$)
次に、次のアクションを新しい方策($\pi _{new}$)に従って選択する。($A' = \pi _{new}(S_{t+1})$)
そして、サンプルの即時報酬$R_{t+1}$と次のアクション$A'$を使って行動価値関数を更新する。($R_{t+1} + \gamma \hat{q} (S_{t+1},A',w) - \hat{q}(S_t,A_t,w)$)

以上より、Linear Least Square Q-Learningによる重み$w$の更新は次のようになる。

\delta = R_{t+1} + \gamma \hat{q} (S_{t+1}, \pi (S_{t+1}),w) - \hat{q}(S_t,A_t,w) \\
\Delta w = \alpha \delta x(S_t, A_t)

Linear Least Squares Predictionで登場したLSTDに、Linear Least Square Q-Learningを適用したアルゴリズムはLSTDQと呼ばれ、以下のようにfeature vector($x(s,a)$)から直接最適な重みを導くことができる。

0 = \sum ^T _{t=1} \alpha (R_{t+1} + \gamma \hat{q} (S_{t+1}, \pi (S_{t+1}),w) - \hat{q}(S_t,A_t,w))x(S_t, A_t)\\
w = (\sum ^T _{t=1} x(S_t, A_t) (x(S_t, A_t) - \gamma x(S_{t+1}, \pi (S_{t+1})))^T)^{-1} \sum ^T _{t=1} x(S_t, A_t) R_{t+1}

最後に、LSPIの収束を以下に表す。

アルゴリズム	テーブル探索	線形	非線形
MC Control	○	(○)	×
Sarsa	○	(○)	×
Q-Learning	○	×	×
LSPI	○	(○)	-

Policy Gradient(Policy Function Approximation)

今まで価値関数に着目してきたが、経験から直接方策を改善する手法について確認する。
Value Function Approximationでは、重み$w$やニューラルネットを使って価値関数を近似したが、方策についてはさほど重要ではなかった。その理由は、方策が常にGreedyまたはε-greedyであり、価値関数から生成されたためである。

Policy-basedな強化学習がValue-basedより有利である点は以下の3つである。

よりシンプルでより少ない情報のみで学習が可能になる(価値関数は、アクションが複雑であったり連続する場合、価値が最大となるアクションを計算して探さなければいけないので、コストが高くなる)
Value-basedよりも分散が大きくならず、収束しやすい
確率的な方策も学習することができる(決定論的な方策よりも確率的な方策が最適な場合がある(繰り返し雑音がある場合など))

反対に欠点はこれらである。

大域解ではなく、局所解に収束しやすい
単純な学習手段の場合、Value-basedよりも少しづつ学習が進むため非効率となり、また逆に分散が大きくなってしまうことがある

Policy Gradient Methods(方策勾配法)は、方策を経験から直接パラメーター化する手法である。

\pi _\theta (s,a) = P(a|s,\theta )

方策は、状態と$\theta $を条件とする、アクションの確率分布となる。
$\theta $は方策を左右するパラメータであり、これを調整することで方策の改善を行うことになる。
方策勾配法は、より多くの報酬をもらえる$\theta$についての勾配を見つけ、それに沿って学習する。

また、ここではModel-Freeの環境を想定する。

最適な方策を見つけるためには方策を比較しなければならない(正確には$\theta $)が、比較する方法は大きく分けて3つある。(2つ目と3つ目の$d^{\pi _\theta }$は、方策$\pi _\theta $に対して定常分布のマルコフ連鎖であると仮定する)

1つ目が、初期状態を使う方法である。
イテレーションが始まる状態がある状態$s_1$と決定している場合、$s_1$からイテレーションの終わりまでに得られる報酬が最も大きい方策がより優れた方策と言える。

J_1(\theta) = V^{\pi _\theta } (s_1) = E_{\pi _\theta } [v_1]

2つ目が、状態ごとの価値を平均する方法である。
最終状態がない場合、初期状態は使えないため、遷移確率と各状態の価値を掛け合わせて平均をとる。

J_{avV}(\theta) = \sum _s d^{\pi _\theta }(s) \; V^{\pi _\theta }(s)

3つ目は、ステップごとの報酬の平均を比較する方法である。

J_{avR}(\theta) = \sum _s d^{\pi _\theta }(s) \sum _a \pi _\theta (s,a) R^a _s

以上の3つが方策勾配法を利用する際の目的関数(Policy Objective Functions)となり、これらを最大にする$\theta $を見つけることで最適な方策を見つける。

Finite Difference Policy Gradient

方策勾配法では、勾配降下法で確認したのと同様に勾配を利用して$\theta $を更新する。
しかし、今回はエラーを最小化するのではなく、上記で定義した目的関数を最大にしたい。
そのため、Gradient Ascent(勾配上昇法)を使う。

\Delta \theta = \alpha \nabla _\theta J(\theta )

この時、$\nabla _\theta J(\theta )$をPolicy Gradient(方策勾配)と呼び、以下のように表される。

\nabla _\theta J(\theta ) = 
\begin{pmatrix}
\frac{\partial J(\theta )}{\partial \theta _1} \\
\vdots \\
\frac{\partial J(\theta )}{\partial \theta _n}
\end{pmatrix}

Finite Difference Policy Gradientで、方策$\pi _\theta (s,a)$の勾配を評価する。
そのために、各次元$k \in [1,n]$の偏微分を計算し、得られた結果全てから全体の方策勾配を求める。(= 1回勾配を求めるため、$n$回の計算が必要になる)
具体的には、$\theta $の各次元に対して、目的関数の偏微分の近似値を摂動によって得る。

\frac{\partial J(\theta )}{\partial \theta _k} \approx \frac{J(\theta + \epsilon u_k) - J(\theta )}{\epsilon }

$\epsilon $は摂動のための小さな値、$u_k$は$k$番目の要素が1でそれ以外が0の単位ベクトルである。
この方法は、ノイズが入り、効率的でもないが、効果的である。
また、方策が微分可能でなくても適用可能である。

Monte-Carlo Policy Gradient

Likelihood ratios and Score Function

次に方策勾配を分析的に計算する方法に移る。
まず、方策$\pi _\theta $のアクションを選択する部分は微分可能であるとし、勾配$\nabla _\theta \pi _\theta (s,a)$をすでに得ていることを前提とする。

まず、Likelihood ratios(尤度比 = $\nabla _\theta \pi _\theta (s,a)$)からScore Function(スコア関数)を定義する。

\begin{align}
\nabla _\theta \pi _\theta (s,a) &= \pi _\theta (s,a) \frac{\nabla _\theta \pi _\theta (s,a)}{\pi _\theta (s,a)} \\
&= \pi _\theta (s,a) \nabla _\theta \log \pi _\theta (s,a)
\end{align}

対数尤度関数を最大にする$\theta $を求めるため、対数尤度関数を$\theta $で偏微分した(= スコア関数)$\nabla _\theta \log \pi _\theta (s,a)$を使う。
尤度比を上げる為には、スコア関数の勾配に従うことになり、この勾配にしたがって方策の更新を行うことにより報酬を最大化していく。
なぜスコア関数を求めるかというと、方策から方策勾配が予測できるからである。

スコア関数の例としてまずSoftmax Policyを使う。
Softmax Policyでは、どのくらいの確率で独立したアクションのセットから各アクションを選択するかということをパラメータ化する。
ここでは、feature vector($\phi (s,a)^T $)と$\theta $の線型結合を、そのアクションを選択する確率を示す値として利用する。(= Linear Softmax Policy)
この時、ある状態$s$においてアクション$a$が選択される可能性は、指数関数$e^{\phi (s,a)^T \theta }$に比例する。

\pi _\theta (s,a) \propto e^{\phi (s,a)^T \theta }

これは方策をパラメータ化するシンプルな方法の１つである。
スコア関数は、注目しているアクション$a$の確率から他のアクションのfeatureの値の平均を引いたものとなる。

\nabla _\theta \log \pi _\theta (s,a) = \phi (s,a) - E_{\pi _\theta} (\phi (s,・))

もしアクション$a$を予想より多く選択し、またアクション$a$を選ぶことでより多くの報酬がもらえるのであれば、この$\phi (s,a)$の値を大きくする。

2つ目の例は、Gaussian Policyである。
これは、最終状態を持たないモデルで最も一般的な方策である。
ここで平均$\mu (s)$は、状態のfeature vectorと$\theta $を線型結合したものである。($\mu (s) = \phi (s)^T \theta$)
$a$は1次元のガウス分布(正規分布)に従うので、$a \sim N(\mu (s), \sigma ^2)$と表せる。
そして、スコア関数は以下のようになる。

\nabla _\theta \log \pi _\theta (s,a) = \frac{(a - \mu (s)) \phi (s)}{\sigma ^2}

ここでもスコア関数はアクション$a$を予想よりどの程度頻繁に選択しているかを表している。

次に実際のMDP(1ステップのみ)を使って、目的関数と方策勾配を定義する。
このMDPは、ある分布によって初期状態$s$が決定され($s \sim d(s)$)、1ステップのみで最終状態となるため、即時報酬は全報酬と同じになる($r = R_{s,a} $)。
これを踏まえて目的関数を定義するとこのようになる。

\begin{align}
J(\theta ) &= E_{\pi _\theta } [r] \\
&= \sum _{s \in S} d(s) \sum _{a \in A} \pi _\theta (s,a) R_{s,a}
\end{align}

次に方策勾配を定義する。

\begin{align}
\nabla _\theta J(\theta ) &= \sum _{s \in S} d(s) \sum _{a \in A} \pi _\theta (s,a) \nabla _\theta \log \pi _\theta (s,a) R_{s,a} \\
&= E_{\pi _\theta } [\nabla _\theta \log \pi _\theta (s,a) r]
\end{align}

Policy Gradient Theorem

1ステップではないMDPの場合、即時報酬$r$の代わりに行動価値関数($Q^{\pi _\theta} (s,a) $)を利用する。

\nabla _\theta J(\theta ) = E_{\pi _\theta } [\nabla _\theta \log \pi _\theta (s,a) Q^{\pi _\theta} (s,a)]

スコア関数(予想よりどのくらい多くor少なくそのアクションを選ぶか)に行動価値関数の値(どのくらいの報酬が得られるかという予測値)を掛けることで、より多くの報酬が得られる方向に方策を更新することになる。
これをPolicy Gradient Theoremと呼び、$\pi $が微分可能である限り、上記で述べた3種類のどの方策目的関数にも適用可能である。

例としてMonte-Carlo Policy Gradient(REINFORCE)の手法について見てみる。
Monte-Carlo Policy Gradientでは、確率的勾配上昇法とPolicy Gradient Theorem(方策勾配定理)を使う。
また、$Q^{\pi _\theta} (s_t,a_t)$のバイアスなしのサンプルとして、その状態から獲得できる報酬の合計$v_t$を使う。
サンプルを取得した後、全エピソードの全タイムステップ$t \in T$において、以下のように$\theta $を更新する。

\Delta \theta _t = \alpha \nabla _\theta \log \pi _\theta (s_t,a_t) v_t

Monte-Carlo Policy Gradientは、方策の学習はできるが、非効率であり、分散も大きくなる。
それを解決するためにActor-Critic Policy Gradientを利用する。

Actor-Critic Policy Gradient

Actor-Critic

まず、分散を小さくすることを考える。
バイアス無しのサンプル($Q^{\pi _\theta } (s,a)$)を使って行動価値関数を推測すると、分散は大きくなる。
そこで、Critic(Value Function Approximator)を使って行動価値関数を推測する。($Q_w (s,a) \approx Q^{\pi _\theta } (s,a) $)
これはValue Function ApproximationとPolicy Gradientの手法を合わせたものであると考えられる。

Actor-criticは、2つのパラメータで表現される。
Actor：実際にアクションを決定する。
　　　　Criticの示す方向(勾配)に従って$\theta $を更新することで方策の更新を行う。
Critic：実際にアクションは実施せず、Actorの実施したアクションが良いか悪いかを観察/評価する。
　　　　行動価値関数を$w$を更新することで更新する。

以上より、Actor-Criticでは、Approximate policy gradient(近似した方策勾配)に従うことになる。

\nabla _\theta J(\theta ) = E_{\pi _\theta } [\nabla _\theta \log \pi _\theta (s,a) Q_w (s,a)] \\
\Delta \theta = \alpha \nabla _\theta \log \pi _\theta (s,a) Q_w (s,a)

上の式は、方策勾配定理のサンプルの部分を近似した行動価値関数に置き換えただけである。
Criticは近似した行動価値関数を更新することで、Actorに方策の更新方向を示していることがわかる。

Criticは方策の評価を行うが、その手法は今まで見てきたアルゴリズムである、MCやTD、TD(λ)などで行う。
それらの手法で、今の方策($\pi _\theta $)によってどのくらいの報酬が得られたかを評価する = $\theta $を評価する。

例として、Linear Value Function approximator($Q_w (s,a) = \phi (s,a)^T w$)によって本当の$Q_\pi (s,a)$を近似し、Criticはlinear TD(0)を使って重み$w$を更新、Actorはpolicy gradientを使って$\theta $を更新するActor-Criticのアルゴリズム(Q Actor-Critic)を考えてみる。

初期状態$s$とパラメータ$\theta $を初期化する
方策$\pi _\theta $に従ってアクションを実行する($a \sim \pi _\theta $)
即時報酬$r$に$R^a_s$を代入し、遷移先状態$s'$を取得する($s' \sim P^a_s$)
次のアクション$a'$を方策$\pi _\theta $に従って選択する($a' \sim \pi _\theta (s', a')$)
今のFunction Approximatorとサンプル報酬を使って予測したFunction ApproximatorのTD Error($\delta $)を計算する($\delta = r + \gamma Q_w(s',a') - Q_w(s,a)$)
Actorが$\theta $をpolicy gradient theoremとFunction Approximatorを使って更新する($\theta = \theta + \alpha \nabla _\theta \log \pi _\theta (s,a) Q_w (s,a)$)
CriticがLinear TD(0)を使って、重み$w$を更新する($w = w + \beta \delta \phi (s,a) $)
$a$に$a'$、$s$に$s'$を代入する
エピソードが終了していなければ、3に戻る

ここで大事なことは、各ステップで$\theta $を更新しているので、1ステップごとにより良い方策に更新されていることである。
$\alpha $と$\beta $は、ステップサイズ(学習率)を表すが、これはどれくらいgreedyかを表す指標となる。例えば、$\alpha $を1とすると、ただのgreedy policyと同じである。より多くの報酬がもらえると予測されたアクションを選択する確率が高くなる方向(少ない報酬のアクションを取る確率を下げる方向でもある)に沿って、学習率の分だけ$\theta $を更新する。

Advantage Function Critic

ここまででアルゴリズムとしての基礎は終わりにし、次に分散をいかに少なくするかという点について考える。
ここではベースライン(baseline function)$B(s)$を取り入れ、方策勾配からベースラインを引くことで分散を抑える。
ここで方策勾配定理にベースラインを適用しても、勾配に影響を与えないことを確認する。

\begin{align}
E_{\pi _\theta } [\nabla _\theta \log \pi _\theta (s,a) B(s)] &= \sum _{s \in S} d^{\pi _\theta }(s) \sum _a \nabla _\theta \pi _\theta (s,a) B(s) \\
&= \sum _{s \in S} d^{\pi _\theta }(s) \: B(s) \: \nabla _\theta \sum _{a \in A} \pi _\theta (s,a) \\
&= 0
\end{align}

ベースラインはアクションに依存しないため、$\sum $から取り出す。
次に勾配は掛けているだけのため$\sum $から取り出すと、$\sum $以降は方策のみが残り、1になる(ここで方策はアクションの確率分布のため)。
そして勾配が1 = 0となり、ベースラインが勾配に与える影響はないと言える。
これにより、方策勾配定理の$Q^{\pi _\theta }(s,a)$からどのような値を引いても良く、それを利用して分散を抑えることができる。

経験的にベースライン$B(s)$には状態価値関数($V^{\pi _\theta }(s)$)が利用される。
行動価値関数($Q^{\pi _\theta }(s,a)$)からベースライン$B(s) = V^{\pi _\theta }(s)$ を引くことで、アクション$a$を取ることがいつもよりどのくらい多く報酬の報酬につながるかを示す、Advantage Function($A^{\pi _\theta }(s,a)$)を得ることができる。

A^{\pi _\theta }(s,a) = Q^{\pi _\theta }(s,a) - V^{\pi _\theta }(s) \\
\nabla_\theta J(\theta ) = E_{\pi _\theta } [\nabla _\theta \log \pi _\theta (s,a) A^{\pi _\theta }(s,a)]

上記のようにAdvantage Functionとスコア関数を掛けることで方策勾配定理を書き直せる。
もし、Advantage Functionが負の値となるのであれば、アクション$a$を選択する方策から遠ざかるように$\theta $を更新する。

ベースラインを利用したActor-Criticは分散を大いに減らすことができる。
しかし、Advantage Functionを推測ために2つの価値関数($Q^{\pi _\theta }(s,a)$とV^{\pi _\theta }(s))を推定する必要がある。
ここでもValue Function Approximatorが登場する。

V_v (s) \approx V^{\pi _\theta }(s))\\
Q_w (s,a) \approx Q^{\pi _\theta }(s,a) \\
A(s,a) = Q_w (s,a) - V_v (s)

$w$と$w$はそれぞれ価値関数を推測するためのパラメータベクトルを表す。
2つのパラメータベクトルを使って、2つのFunctionを近似/更新するのは効率が悪い。
そこで、TD errorを使った手法が実践でよく利用される。
TD error($\delta ^{\pi _\theta }$)は、真の状態価値関数($V^{\pi _\theta }(s)$)と即時報酬$r$のみで求めることができる。($\delta ^{\pi _\theta } = r + \gamma V^{\pi _\theta }(s') - V^{\pi _\theta }(s) $)
そして$\delta ^{\pi _\theta }$は、バイアスなしのAdvantage Functionの予測と考えることができる。

\begin{align}
E_{\pi _\theta } [\delta ^{\pi _\theta }|(s,a)] &= E_{\pi _\theta } [r + \gamma V^{\pi _\theta }(s')|(s,a)] - V^{\pi _\theta }(s) \\
&= Q^{\pi _\theta }(s,a) - V^{\pi _\theta }(s) \\
&= A^{\pi _\theta } (s,a)
\end{align}

TD errorを使って方策勾配定理を書き換えるとこのようになる。

\nabla_\theta J(\theta ) = E_{\pi _\theta } [\nabla _\theta \log \pi _\theta (s,a) \delta ^{\pi _\theta }]

実際には、推測値の$V_v$を使うため、$\delta _v = r + \gamma V_v (s') - V_v(s)$を使う。
そのため、必要となるパラメータベクトルは$v$のみとなる。
これは、MCやTD(0)TD(λ)などを組み合わせることも可能である。
上記の例ではTD errorを使ったが、MCなら報酬合計$v_t$を使えば実現できる。
また、eligibility tracesも適用でき、その場合$e_{t+1}$はスコア関数を訪れた各状態と実行したアクションのセットで記憶する。

\delta = r_{t+1} + \gamma V_v(s_{t+1}) - V_v(s_t)
e_{t+1} = \lambda e_t + \nabla _\theta \log \pi _\theta (s,a)
\Delta \theta = \alpha \delta e_t

さらにAdvantage Functionは、Actorの更新にも適用できる。(詳しくは講義資料を参照)

Natural Policy Gradient

今までの確率論的な方策勾配定理では、ある方策で取得したサンプルを利用して方策勾配を推定し、方策の更新を行なった。
しかし、サンプルを取得することに用いた方策にはノイズが含まれるため、そのノイズを含んだ勾配によって更新することになり、とても効率を悪くする。

Criticは、どのアクションを選択するとより多くの報酬を得られるか(Qの勾配)を学習し、それを選択するようにActorに方向付ける。
Actorは、Criticによって示されたアクションをより多く取るためにパラメータを更新するための方向(方策勾配)に沿って学習する。
以上より、Criticは方策の更新に必要な情報は全て持っているということになる。
そこでシンプルに、より多くの報酬が得られる行動価値関数を選択するように方策を更新する(= 決定論的)ことによって、最終状態のない環境や複雑な環境において確率的な方策勾配定理を用いた場合よりも効率が上がる。

最後に

社会人になって再学習したとはいえ、数学を高校2年でやめた、強化学習独学の文系人が書いているので、間違っているところも多いと思います。
間違いを見つけた際には、私自身の学びのためにも、ご指摘いただけると大変ありがたいです。

参考資料

An Introduction to Reinforcement Learning(訳本は出版されてますが、有料です)
http://incompleteideas.net/book/bookdraft2017nov5.pdf

Algorithms for Reinforcement Learning
https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf

強化学習理論の基礎3

概要