基底関数に同径分布関数を採用し、パラメータθとの線型結合で行動価値関数を近似パラメータ$\theta$の更新式を導出はじめにこれまでに、TD法を用いてテーブル状の価値関数を推定し、最適な行動を行動価値関数から選択することでエージェントを制御しました。SarsaとQ学習の違い今回の題材としてマウンテンカー(山登り問題)のデモを以下に示します。マウンテンカーとは、車を左右に加速させて、右端の山頂に登る切るタスクです。ポイントは、初期状態から右に加速させても山頂には登り切れないため、一度左側に山を登って、勢いを付けて坂を下らないといけないことです。(3種類の離散値)Sarsaを用いた学習結果を示しました。このデモでは行動価値関数をテーブルで表すために、状態空間をそれぞれ32分割しています。3072$のグリッドに区切った行動価値関数を計算しています。これをテーブル法と呼びましょう。ともに離散値でなければなりません。現実の問題では状態、時には行動も連続値になります。その場合、連続空間を離散値に無理やり区切らなければならないところにテーブル法の問題点があります。分割方法に任意性がある分割数が多いと、メモリの消費量、計算量が爆発的に増大する探索すべき空間が増大する特に3の問題は顕著です。テーブル法では、価値関数は実際にその状態を訪問しないと初期値から更新されません。価値関数の表現力を上げるには分割数を上げなければなりませんが、代わりに訪問しなければならない状態が増え、学習が終了しなくるジレンマに陥ります。マウンテンカー(2次元の状態空間)でしたらテーブル法でも十分いけますが、次元数が上がると手に負えなくなるのは明らかです。関数を用いた価値関数の近似テーブル法とは、言うならば区切られたマス目に対してブロックを積み上げて、価値関数を離散的に表現していく方法です。(下図左)価値関数は山型の分をしていることが推測されますが、分割が粗いため細かい分布はわかりません。逆に、真ん中の図のように分割数を上げると今度は各状態への訪問が足りず、近似が不十分になります。そこで、離散的な状態として取り扱うことをやめ、右の図のように連続な状態空間上で行動価値関数を近似してやることを考えます。分布を近似してやるために、どんな関数を用いましょう。近似に用いる関数を基底関数と呼びます。今回は基底関数に山型の分布である正規分布、より正確には同径分布関数(積分して1になる必要はないので)を用います。\cdots(1)$$となります。正規分布の定数項を取り去った関数ですね。後述しますが、基底関数の数は複数個とっても良いし、別の分布の基底関数を組み合わせても構いません。基底関数単体ではその関数自身の分布にしかなり得ないので、後述するように複数の基底関数を組み合わせて近似力を上げる必要があります。行動価値関数を近似しているため、基底関数の入力xは状態sおよび行動$a$を含みます。実際には、行動価値関数のデザインには2つのやり方があって、1)状態$s$と行動$a$を入力値$x$にして出力値は1つのパターン2)入力をsのみにして出力値を行動$a$の数にし、その後任意の行動を選択するパターンがあります。ニューラルネットワークを用いたDQNは後者のアプローチをとっています。本稿でも後者のスタイルを取ります。下図がわかりやすいです。Approximation]より引用(http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/FA.pdf)近似関数の学習パラメータ今回紹介する近似方法で重要な点は、配置した基底関数内のパラメータは固定とし、学習対象にしないことです。同径分布関数の場合、分布の位置($\mu$)と広がり($\sigma$)は固定します。基底関数そのものには手を付けません。正規分布の位置や山の広がりを調整するわけではないのですね。その代わり、基底関数を定数倍する係数$\theta$をパラメータとします。(2)$$負の方向を含め基底関数を$\theta$で伸縮させて分布を表現します。いっても、一つの基底関数の伸縮だけでは複雑な関数を表現(近似)できそうにないのは明らかでね。ここは数で対抗しましょう。基底関数を複数個(N個)使います。\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}\phi(s_t,a_t)$$は、時刻tにおける($\theta$で近似した)行動価値関数です。式(X)の導出について説明します。更新式の結果だけが知りたかった人は飛ばして、最後の結果を見てください。行動価値関数を真の値に近づけていくためには、真の価値関数との誤差を定量的に表し、その誤差を下げる方向にパラメータを更新します。誤差を下げる方法は誤差のパラメータに対する勾配(微分)を使います。これは、回帰やクラス分類で一般的に使われている確率的勾配降下法(SGD)という手法です。真の価値関数qが存在すると仮定して、近似価値関数との二乗和誤差を評価関数$E_{MSE}$として定義します。(6)$$評価関数をパラメータ$\theta$について微分し、勾配を計算します。(7)$$あとはパラメータをこの勾配を下る方向に更新させればOKです。定数項は学習率$\alpha$に吸収させました。近似関数の微分となります。今の場合、ターゲットとは真の価値関数です。近似関数の微分を求めれば、近似関数のパラメータを更新できることがわかりました。先に、近似関数の微分について考えます。(11)\end{align}となり、微分の結果は基底関数そのものになります。(12)$$を得ます。基底関数そのもの線形関数を使うことで、更新式がシンプルになりましたね。この明快さが線形関数のメリットです。Q(s,a)$を計算するだけです。考えてみると真の価値関数qはわかりっこないです。そもそも(真の)価値関数を知りたくてそれを近似的に表わそうとしていたのでした。もとから真の価値関数を知っているなら、そもそも近似する必要がありません。ここが教師あり機会学習と強化学習の違いで、教師データ(ターゲット)がもとから与えられているわけではなく、あくまで試行を通じて関数を近似する必要があります。いっても、勾配降下法を用いて教師あり学習の枠組みで解くためには、何かしらのターゲットを決める必要があります。いっても何かをターゲットにせねば求めたい真の価値関数qの代わりに、もっともらしい値を持ってきてqの代替とします。この場合もっともらしいとは、少なくとも今の近似関数よりは真の価値関数に近いとします。テーブル法の時の価値関数の更新を思い出します。時刻tで状態s,行動aをとったときの行動価値関数$Q(s,a)$は、その次の時刻t+1のときに状態s'、行動a'をとった行動価値関数$Q(s',a'$で表されるのでした。(13)$$ただし、等号は異なる行動によって分岐する状態s'についての期待値(平均)をとった時に成り立ちます。分岐の比率はわからないため、実際には平均をとらず、1ステップずつエピソードを進めるたびに訪問先の価値関数から訪問もとの価値関数を更新します。(15)$$ひとつ先の時刻の推定値を用いて、今の推定値を更新したのでした。・・・Q学習の場合この値qを近似価値関数$Q(s,a|\theta)$を更新するときのターゲットとします。この値を式(x)に代入することで、最終的なパラメータの更新式を得ます。ここではQ学習の更新式を示します。(16)$$疑似コード疑似コードを以下に示します。いずれにも該当するように抽象化して書いています。関数近似の結果マウンテンカーでの価値関数近似の結果を示します。学習初期の500ステップまでを動画化しました。左にテーブル法の価値関数推定、右に線形関数近似(同型分布関数使用)テーブル法の場合は実際に訪問したところだけしか価値関数が更新されないのに比べ、線形関数近似ではパラメータを学習するので訪問したところ以外も価値関数が更新されます。従ってテーブル法よりも関数の収束が早くなっています。(リピートの切れ目が見にくいですが200ステップあたりですでに形が作られています。)次に、収益の結果を示します。マウンテンカーでは山登りが成功しない限りはスコアは-200点です。テーブル法の場合300ステップを超えてようやく成功しています。その場合も最高点は-180点前後と低い値です。対して線形関数近似の場合は学習後すぐにスコアが上昇し、-100点とテーブル法よりや高いスコアを出しています。このように線形関数近似の法が学習の速さ、性能ともにテーブル法を上回りました。最後に線形関数による近似法はハマると強いですが、基底関数の種類や数などを人力で設計しなければならないところがデメリットです。そこで、近似関数としてニューラルネットワークを使えばいいのではないでしょうか。多層のニューラルネットワークを使えば表現力もありますし、微分操作も今はTensorFlowなどのフレームワークで自動的にやってくれます!二乗誤差も定義されてますし!しかし、近似関数を単純にニューラルネットワークにしただけでは以下のように学習がうまくいきません。失敗する理由はいくつかあるのですが、それらを解決し多層ニューラルネットワークで安定的に学習が進むようにしたのが、かの有名なDQNです。DQNを解説した良記事はたくさんあるので、次回は少し視点を変えて線形関数近似→NN近似(失敗)→DQNという流れで説明をしたいと思います。upLoginユーザーは見つかりませんでした。