dqn.md

Playing Atari with Deep Reinforcement Learning

論文のポイントを抑えていったものです。（途中どうみてもポイントを抑えるに留まっていない部分がありますが）

Introduction

• Reinforcement Learning(RL)は高次元の感覚的入力を学習するのに良いが、そのようなシステムの性能は特徴表現に強く依存する。
• Deep Learningはコンピュータビジョンの分野(Imagenetとか)で大きな成果をあげたり、音声認識で大きな成果をあげた
• 当然Deep LearningはRLにも応用が期待されるが、Deep Learningの成功は人間によって作られた大量の訓練データに大きく依存し、RLの報酬は、うまく適合しない。というのも、行動と報酬は教師あり学習のように与えられるものでなく、時間的差異がある。
• また、教師あり学習では、学習データは独立しているが、強化学習においては、似通った状態に連続して遭遇することになる。
• さらにDeep Learningでは、背後にある確率分布は一定であると仮定されているが、RLでは行動方針の変化とともに、確率分布が変動する。
• この論文では、たたみ込みニューラルネットによって、これらの困難を高いし、環境から生の映像データを用いることによって、良い方針を学習することを示す。
• Q Learningと確率勾配降下を用いてネットワークは学習
• 関連性のつよい状態の連続による弊害を解決するために、Experience Replayという手法を用いる。これは過去の遷移をランダムに収集して、過去の行動を踏まえてなめらかな分布の学習を可能とする。
• Atariのゲームを題材に、一つのAIで、複数のゲームを学習できるようにする。この時、ゲームの詳細情報を一切与えず、入力はゲーム映像の入力のみとする。

背景

RLやQ Learningについては先週の資料を参照

最適行動価値関数は、Bellman方程式という重要な恒等式に従っている。もし状態sにおいて次のタイムステップにおける可能なすべての行動について $Q(s',a')$ が既知であるとすると、最適化戦略は、報酬$r$と割引率 $\gamma$を用いて、$r + \gamma Q(s',a')$ の期待値を最大化する$a'$を選べばよく、 $$ \begin{eqnarray} Q^(s,a) = E_{s'\sim \epsilon}[r + \gamma max Q^ (s',a')|s, a] \end{eqnarray} $$ を得られる。これがBellmanの方程式である。 $$ \begin{eqnarray} Q_{i+1}(s,a) = E[r + \gamma max Q_i(s',a')|s, a] \end{eqnarray} $$ という更新式は、$i \rightarrow \infty$で、行動価値関数と一致することが示されている。

この方針は、実際には実践的でなく、多くの場合関数近似$Q(s,a; \theta) \approx Q(s,a)$ が用いられる。多くの場合これは、線形近似であるが、ニューラルネットのような非線形近似関数が用いられることもある。重みパラメータとしてθ を持つニューラルネットによる近似関数をQ-networkと呼ぶ。Q-networkは、ロス関数$L_i(\theta )$ を用いることで学習され、ロス関数は

$$ \begin{eqnarray} L_i(\theta ) = E_{s,a\sim \rho(\cdot)}[(y_i - Q(s,a;\theta _i ))^2] \end{eqnarray} $$

目標関数は、

$$ \begin{eqnarray} y_i = E_{s'\sim \epsilon}[r + \gamma max Q^* (s',a';\theta_{i-1})|s, a] \end{eqnarray} $$ であり、$\rho(s,a)$ をs,aのシーケンスについての確率分布として、行動分布と呼ぶ。$\theta_{i-1}$ のパラメータは$L_i({\theta_i})$ がロス関数を最適かしている間は固定される。また、目標関数はネットワークの重みにも依存することに注意する。

重みに関して、微分すると勾配は $$ \begin{eqnarray} \nabla L_i({\theta_i}) = E_{s,a\sim \rho(\cdot);s'\sim \epsilon}[(r + \gamma max Q^* (s',a';\theta_{i-1}) - Q(s,a;\theta_i))\nabla_{\theta_i}Q(s,a;\theta_i)] \end{eqnarray} $$ が得られる。計算理論的に、確率勾配降下を用いてロス関数を最適化する方が、すべての勾配の期待値を計算するよりも好都合で、もし、重みが毎回のタイムステップ後に更新され、期待値は、行動分布 $\rho$ と環境 $\epsilon$各々から一つを取り出すことによって置き換えられるなら、Q-learningになる。

また、これは"model freeである。すなわち、環境 $\epsilon$を直接推論することなく、サンプルを用いることで、RLタスクをとく。また"off-policy"である。すなわち、行動分布が状態空間における適切な探索を確かにする間に、愚直な最もよいQ値をとる行動をするという方法を学習する。これは、実践的には $\epsilon$ greedyなどが用いられる。

Related Work

TD-gammon

自分同士で対戦して学習する。Backgammonにはうまくいくが、�GoやChessではうまくいかない

Q-learning

状態が発散する。つらい。収束しない。線形関数近似は収束が保証しやすくて良い。

Deep Learning

制限ボルツマンマシン(RBM)を価値関数推測に使ったりする。"Gradient temporal-difference"という方法によってQ学習で発散する問題が解決したりする。こいつらは、非線形近似関数でも固定された方針であれば、収束することが示されている。

Neural Fitted Q-learning(NFQ)

NFQは、Q-netのパラメタ更新にRPROPアルゴリズムを用いて、上のロス関数のシーケンスを最適化する。ただバッチ学習をするので、計算コストがでかい。今回のSGDの方が低い。 NFQは画像データを入力として、制御タスクにも成功している。最初にタスクの低次元の表現を得るために深層自己符号化器を使って、学習して、この表現をNFQに突っ込むことで実現した。

Deep Reinforcement Learning

RLとDeep neural Networkを組み合わせて、RGBの画像から効率的に学習することを目標とする。

TD-Gammonでは、環境とのインタラクションで得た値である $s_t , a_t, r_t, s_{t+1}, a_{t+1}$ から、価値関数を近似するネットワークの重みを更新する。この方針をDeep Neural Netを用いるようにすることが、この論文の基本となる方針である。

この論文では、"Experience Replay"を利用する。"Experience Replay"とは、各タイムステップにおけるエージェントの経験を保持する、すなわち $e_t = (s_t,a_t,r_t,s_{t+1})$ をReplay Memory $D = e_1, e_2, ..., e_N$としていくつかのエピソードの間保持する。そして、アルゴリズムの内部で、Q-learningの更新をランダムに保持されたMemoryから取り出したExperienceを適用する。これをしたのち、エージェントは $\epsilon$ -greedyにしたがって、行動を決定する。任意の長さの入力に対応するニューラルネットを構成するのは難しいので、固定長表現を生成する関数 $\phi$ を導入する。これら全体のアルゴリズムをDeep Q-Learningと呼ぶ。

この方法の通常のQ-learningに対する利点として、まず多くの重み更新に各ステップの経験が潜在的に使われるということがあり、より良いデータ効率を可能とする。二つ目に、RLにおいて、連続するサンプルから学習することは、それらの間にあるつよい関係性のために非効率であり、これらの関係性を壊してランダムに学習することで、更新の分散を削減することができる。三つ目に、on-policyな学習をする際、パラメータが次のデータのサンプルに強く影響し発散につながるが、Experience Replayを用いることで、発振や発散を抑えることができる（ただし、当然off-policyしか使えなくなるが）

実際上は、有限の個数 $N$ のみ保持し、そこから一様乱数によってサンプリングをする。

Preprocessing and Model Structure

通常のAtariのゲームは210 x 160ピクセルのRGB画面だが、これを畳み込みそうに合わせて2Dのgray scaleな84 x 84にする前処理をしたりする。 また、過去の４つのフレームをまとめて、入力するように加工する。

ニューラルネットには状態のみを入力し出力として、それぞれの行動のQ値を返すようなものを今回はニューラルネットに利用した。

実際のネットワーク構成については省略

Experiments

Atariのゲームで実験。基本的に一つのネットワーク（超パラメタとか構成が同じ）を用いて、複数のゲームを学習させた。 また、ポイントがゲームによってまちまちなので、報酬を1と-1と0に変換した。こうすることで、誤差の勾配のスケールが制限されるし、同じ学習率を複数のゲームに使用できる。

RMSPropを使って、ε-greedyにはアニーリングを線形1->0.1に行った。

experience Replayには直近100万のフレームから行った。

また、毎フレームの実行は大変なので、基本的に4フレームに一回をタイムステップとした。ただ、Space Invadersに関しては、レーザーが避けられなくなるので、3フレームにした。

Training and Stability

Rewardの合計はまちまちで揺れちゃうので、最大のQ関数の値の平均を使ったほうがいいよという話。

また、発散を経験したことがないから、収束する証明はないけど、多分安定だよ。という話。

Main Evaluation

既存のSarsaやContigency、さらには場合によって人間よりもすごいよという話。 そもそもSarsaやContigencyは人間が加工した特徴をあげるが、DQNはゲーム画面だけなので、とてもすごい。