今回やったこと
- 連続状態空間でのQ学習
- 基底関数に同径分布関数を採用し、パラメータθとの線型結合で行動価値関数を近似
- パラメータ$\theta$の更新式を導出
はじめに
これまでに、TD法を用いてテーブル状の価値関数を推定し、最適な行動を行動価値関数から選択することでエージェントを制御しました。
今回の題材としてマウンテンカー（山登り問題）のデモを以下に示します。マウンテンカーとは、車を左右に加速させて、右端の山頂に登る切るタスクです。ポイントは、初期状態から右に加速させても山頂には登り切れないため、一度左側に山を登って、勢いを付けて坂を下らないといけないことです。
入力値（状態）
- 車の位置（連続空間）
- 車の速度（連続空間）
出力値（行動）
- {左に加速, 何もしない, 右に加速} （3種類の離散値）
Sarsaを用いた学習結果を示しました。山を登れていますね。このデモでは行動価値関数をテーブルで表すために、状態空間をそれぞれ32分割しています。すなわち$32\times 32 \times 3 = 3072$のグリッドに区切った行動価値関数を計算しています。これをテーブル法と呼びましょう。
テーブル法の問題点
テーブル法は状態空間、行動空間がともに離散値でなければなりません。しかし、現実の問題では状態、時には行動も連続値になります。その場合、連続空間を離散値に無理やり区切らなければならないところにテーブル法の問題点があります。
- 分割方法に任意性がある
- 分割数が多いと、メモリの消費量、計算量が爆発的に増大する
- 探索すべき空間が増大する
特に3の問題は顕著です。テーブル法では、価値関数は実際にその状態を訪問しないと初期値から更新されません。
価値関数の表現力を上げるには分割数を上げなければなりませんが、代わりに訪問しなければならない状態が増え、学習が終了しなくるジレンマに陥ります。
マウンテンカー（2次元の状態空間）でしたらテーブル法でも十分いけますが、次元数が上がると手に負えなくなるのは明らかです。
関数を用いた価値関数の近似
テーブル法とは、言うならば区切られたマス目に対してブロックを積み上げて、価値関数を離散的に表現していく方法です。(下図左)
価値関数は山型の分をしていることが推測されますが、分割が粗いため細かい分布はわかりません。逆に、真ん中の図のように分割数を上げると今度は各状態への訪問が足りず、近似が不十分になります。
そこで、離散的な状態として取り扱うことをやめ、右の図のように連続な状態空間上で行動価値関数を近似してやることを考えます。
そうすれば膨大な分割数を考慮する必要がなくなり、近似した関数のパラメータだけを学習すればよくなります。
基底関数
価値関数の分布を近似してやるために、どんな関数を用いましょう。近似に用いる関数を基底関数と呼びます。今回は基底関数に山型の分布である正規分布、より正確には同径分布関数（積分して1になる必要はないので）を用います。
同径分布関数(基底関数)を$\phi$で表すと
$$ \phi(x) = = \exp \Bigl( -\frac{(x - \mu)^2}{2 \sigma^2} \Bigr) \qquad \cdots(1)$$
となります。正規分布の定数項を取り去った関数ですね。
後述しますが、基底関数の数は複数個とっても良いし、別の分布の基底関数を組み合わせても構いません。むしろ、基底関数単体ではその関数自身の分布にしかなり得ないので、後述するように複数の基底関数を組み合わせて近似力を上げる必要があります。
基底関数の準備
近似関数の入力と出力
行動価値関数を近似しているため、基底関数の入力xは状態sおよび行動$a$を含みます。
実際には、行動価値関数のデザインには２つのやり方があって、
1）状態$s$と行動$a$を入力値$x$にして出力値は1つのパターン
2）入力をsのみにして出力値を行動$a$の数にし、その後任意の行動を選択するパターン
があります。ニューラルネットワークを用いたDQNは後者のアプローチをとっています。本稿でも後者のスタイルを取ります。下図がわかりやすいです。
[UCL Course on RL Lecture 6: Value Function Approximation]より引用(http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/FA.pdf)
近似関数の学習パラメータ
今回紹介する近似方法で重要な点は、配置した基底関数内のパラメータは固定とし、学習対象にしないことです。同径分布関数の場合、分布の位置($\mu$)と広がり($\sigma$)は固定します。
つまり、基底関数そのものには手を付けません。正規分布の位置や山の広がりを調整するわけではないのですね。
その代わり、基底関数を定数倍する係数$\theta$をパラメータとします。
$$Q(s,a|\theta)= \theta \times \phi(s,a) \qquad \cdots (2)$$
負の方向を含め基底関数を$\theta$で伸縮させて分布を表現します。
といっても、一つの基底関数の伸縮だけでは複雑な関数を表現（近似）できそうにないのは明らかでね。なのでここは数で対抗しましょう。基底関数を複数個(N個)使います。
\begin{align}
Q(s,a|\vec{\theta}) &= \theta_1 \phi_1(s,a) + \theta_2 \phi_2(s,a) + ... + \theta_N \phi_N(s,a)c \qquad \cdots (3)\\
&=\sum_{i}^{N}\theta_{i} \phi_{i}
\end{align}
ベクトルで表記すると
$$Q(s,a|\vec{\theta}) = \vec{\theta}^{T}\vec{\phi}\qquad \cdots (4)$$
ここで
$$\vec{\theta} = [\theta_1, \theta_2, \cdots, \theta_N]^T$$
および
$$\vec{\phi} = [\phi_1, \phi_2, \cdots, \phi_N]^T$$
です。今後は簡単のため、添字をつけない$\theta$、$\phi$はそれぞれベクトル$\vec{\theta}$および$\vec{\phi}$を表します。
このように、各基底関数とパラメータとの線形一次結合をとって関数を近似することを線形近似法と呼びます。
状態空間での基底関数の図示
マウンテンカーの状態空間で図示してみましょう。基底関数の下図を9として分布の中心を等間隔に配置しています。$\sigma$は0.1で固定です。
パラメータ$\theta_{i}$は全て1としています。鍾乳洞みたい。$\theta$を変えることで価値関数を近似表現します。試しに$\theta$をランダムに振ってみましょう。
なんか凸凹していますね。基底関数がオーバーラップしていないので、それぞれを伸び縮みさせてもなめらかな関数が表現できません。これを解決するには基底関数の数を増やすか、$\sigma$を大きくする（山を広げる）必要があります。
$\sigma$を0.3にしてみます。
先ほどより滑らかな分布を表現できています。$\sigma$は0.3でいく戦略としましょう。
このように、線形近似法は基底関数の種類、数、配置、形状などを自分で選択する必要があります。この選択を間違えると、いくら学習しても目的の関数を近似できなくなってしまいます。MountainCarの例は可視化できるから良いですが、状態空間が多次元になるとツラいですね。
これで、$\theta$でパラメタライズされた基底関数を用いて価値関数を近似する準備ができました。次は、学習ステップを進めてパラメータを更新していきます。
パラメータの更新
近似関数を用いる強化学習の場合も、テーブル法と同様に1ステップずつ実際に訪問を行います。
ただし、価値関数そのものを更新するのではなくパラメータ$\theta$を更新していきます。そのため、訪問された状態だけでなくその周辺の状態の価値も同時に更新されます。このような汎化性能をもっているのも関数近似法の利点です。
これからパラメータ$\theta$の更新方法を導出していきます。ただし、多少長くなるので先に結論を書いておきます。
パラメータの更新更新式は以下です。
$$\theta_{t+1} \leftarrow \theta_t + \alpha[r + max_{a} Q(s_{t+1}, a_{t+1}|\theta) - Q(s_{t}, a_{t}|\theta)] \phi \qquad \cdots (5)$$
ここで、
$$Q(s_t,a_t|\theta) = \theta^{T}\phi(s_t,a_t)$$
は、時刻tにおける($\theta$で近似した)行動価値関数です。
パラメータの更新式の導出
式(X)の導出について説明します。更新式の結果だけが知りたかった人は飛ばして、最後の結果を見てください。
行動価値関数を真の値に近づけていくためには、真の価値関数との誤差を定量的に表し、その誤差を下げる方向にパラメータを更新します。誤差を下げる方法は誤差のパラメータに対する勾配（微分）を使います。これは、回帰やクラス分類で一般的に使われている確率的勾配降下法(SGD)という手法です。
まず真の価値関数qが存在すると仮定して、近似価値関数との二乗和誤差を評価関数$E_{MSE}$として定義します。
$$E_{MSE} = (q_{t} - Q(s_{t}, a_{t};\theta))^2\qquad \cdots (6)$$
評価関数をパラメータ$\theta$について微分し、勾配を計算します。
$$\frac{\partial E_{MSE}}{\partial \theta} = 2(q_{t} - Q(s_{t}, a_{t}|\theta)) \frac{\partial{Q(s_{t},a_{t};\theta)}}{\partial{\theta}} \qquad \cdots (7)$$
あとはパラメータをこの勾配を下る方向に更新させればOKです。定数項は学習率$\alpha$に吸収させました。
\begin{align}
\theta_{t+1} \leftarrow \theta_t - \alpha (q_{t} - Q(s_{t}, a_{t}|\theta)) \frac{\partial Q(s_{t},a_{t}| \theta)}{\partial{\theta}} \qquad \cdots (8)
\end{align}
式（x）を日本語で表現すると
新しい推定量 = 現在の推定量 - 学習率 × ターゲットと近似関数との誤差 × 近似関数の微分
となります。今の場合、ターゲットとは真の価値関数です。
線形関数近似のメリット
式（x）により、
- 近似関数とターゲットとの誤差
- 近似関数の微分
を求めれば、近似関数のパラメータを更新できることがわかりました。先に、近似関数の微分について考えます。
近似関数Qの$\theta$に関する微分は
$$\frac{\partial Q}{\partial{\theta}} = [\frac{\partial Q}{\partial \theta_1},\frac{\partial Q}{\partial \theta_2}, \cdots, \frac{\partial Q}{\partial \theta_N}]\qquad \cdots (9)$$
微分される近似関数は
$$Q(s,a|\theta) = \theta_1 \phi_1(s,a) + \theta_2 \phi_2(s,a) + ... + \theta_N \phi_N(s,a)\qquad \cdots (10)$$
でしたので、結局添字が同じ項以外は微分して0になるため
\begin{align}
\frac{\partial Q}{\partial \theta} &= [\phi_1, \phi_2, \cdots, \phi_N]^T \\
&= \phi \qquad \cdots (11)
\end{align}
となり、微分の結果は基底関数そのものになります。
以上から、線形近似関数の場合のパラメータの更新式として
$$\theta_{t+1} \leftarrow \theta_t + \alpha (q_{t} - Q(s_{t}, a_{t}；\theta)) \phi \qquad \cdots (12)$$
を得ます。
新しい推定量 = 現在の推定量 + 学習率 × 近似関数とターゲットとの誤差 × 基底関数そのもの
線形関数を使うことで、更新式がシンプルになりましたね。この明快さが線形関数のメリットです。
何を教師信号とするか
あとは真の価値関数との誤差$q_t - Q(s,a)$を計算するだけです。しかし、よく考えてみると真の価値関数qはわかりっこないです。
そもそも（真の）価値関数を知りたくてそれを近似的に表わそうとしていたのでした。もとから真の価値関数を知っているなら、そもそも近似する必要がありません。
ここが教師あり機会学習と強化学習の違いで、教師データ（ターゲット）がもとから与えられているわけではなく、あくまで試行を通じて関数を近似する必要があります。
とはいっても、勾配降下法を用いて教師あり学習の枠組みで解くためには、何かしらのターゲットを決める必要があります。
とはいっても何かをターゲットにせねば
求めたい真の価値関数qの代わりに、もっともらしい値を持ってきてqの代替とします。この場合もっともらしいとは、少なくとも今の近似関数よりは真の価値関数に近いとします。
テーブル法の時の価値関数の更新を思い出します。
時刻tで状態s,行動aをとったときの行動価値関数$Q(s,a)$は、その次の時刻t+1のときに状態s'、行動a'をとった行動価値関数$Q(s',a'$で表されるのでした。
$$Q(s,a) = E_{s'}[r + \gamma Q(s',a')]\qquad \cdots (13)$$
ただし、等号は異なる行動によって分岐する状態s'についての期待値（平均）をとった時に成り立ちます。
分岐の比率はわからないため、実際には平均をとらず、1ステップずつエピソードを進めるたびに訪問先の価値関数から訪問もとの価値関数を更新します。更新方法には2通りあって、
Sarsa
- 探索的な行動（例えば$\epsilon$-greedy）に従って、価値関数をバックアップする
$$Q(s, a) ← Q(s, a) + \alpha[r' + \gamma Q(s', a') - Q(s, a)] (14)$$
Q学習
- 探索的に行動するが価値関数のバックアップは取りうる行動価値関数の最大値をとる方法
$$Q(s, a) ← Q(s, a) + \alpha[r' + \gamma \, max_{a'} Q(s', a') - Q(s, a)] (15)$$
ひとつ先の時刻の推定値を用いて、今の推定値を更新したのでした。つまり
- $q = r + Q(s_{t+1}, a_{t+1})$ ・・・sarsaの場合
- $q = r + max_A Q(s_{t+1}, A_{t+1})$ ・・・Q学習の場合
この値qを近似価値関数$Q(s,a|\theta)$を更新するときのターゲットとします。
この値を式(x)に代入することで、最終的なパラメータの更新式を得ます。ここではQ学習の更新式を示します。
$$\theta_{t+1} \leftarrow \theta_t + \alpha[r + max_a Q(s_{t+1}, a_{t+1}|\theta) - Q(s_{t}, a_{t}|\theta)] \phi \qquad \cdots (16)$$
疑似コード
疑似コードを以下に示します。このコードはテーブル法、線形関数近似法いずれにも該当するように抽象化して書いています。
初期化：
パラメータを初期化(agent.init)
各エピソードに対して繰り返し：
sを初期化
a ← sから$\epsilon$-greedyに従い得られる行動(agent.select_action)
エピソードの各ステップに対して繰り返し：
行動aをとり、報酬rと次状態s'を観測する(env.step)
a' ← s'から$\epsilon$-greedyに従い得られる行動(agent.select_action)
$\theta \leftarrow \theta_t + \alpha[r + max_a Q(s', a'|\theta) - Q(s_{t}, a_{t}|\theta)]\phi$ パラメータを更新(agent.train)
s ← s'
a ← a'
sが終端状態ならば繰り返しを終了
関数近似の結果
マウンテンカーでの価値関数近似の結果を示します。学習初期の500ステップまでを動画化しました。
左にテーブル法の価値関数推定、右に線形関数近似（同型分布関数使用）
テーブル法の場合は実際に訪問したところだけしか価値関数が更新されないのに比べ、線形関数近似ではパラメータを学習するので訪問したところ以外も価値関数が更新されます。
従ってテーブル法よりも関数の収束が早くなっています。（リピートの切れ目が見にくいですが200ステップあたりですでに形が作られています。）
次に、収益の結果を示します。
マウンテンカーでは山登りが成功しない限りはスコアは-200点です。テーブル法の場合300ステップを超えてようやく成功しています。その場合も最高点は-180点前後と低い値です。
対して線形関数近似の場合は学習後すぐにスコアが上昇し、-100点とテーブル法よりや高いスコアを出しています。
このように線形関数近似の法が学習の速さ、性能ともにテーブル法を上回りました。
最後に
線形関数による近似法はハマると強いですが、基底関数の種類や数などを人力で設計しなければならないところがデメリットです。そこで、近似関数としてニューラルネットワークを使えばいいのではないでしょうか。特に多層のニューラルネットワークを使えば表現力もありますし、微分操作も今はTensorFlowなどのフレームワークで自動的にやってくれます!二乗誤差も定義されてますし！
しかし、近似関数を単純にニューラルネットワークにしただけでは以下のように学習がうまくいきません。
失敗する理由はいくつかあるのですが、それらを解決し多層ニューラルネットワークで安定的に学習が進むようにしたのが、かの有名なDQNです。DQNを解説した良記事はたくさんあるので、次回は少し視点を変えて線形関数近似→NN近似（失敗）→DQNという流れで説明をしたいと思います。