Deep Q-Network (DQN)について簡単に勉強してみた

機会があったので、少し気になってたDeep Q-Network (DQN)について数日で勉強してみた。
既にいろんなところでまとめられてN番煎じだけど、自分なりに整理するために強化学習やDQNについて簡単にまとめておく。

今回はDQNに関連する強化学習の基礎+DQNの手法説明、あたりを主にまとめてみた。簡単にまとめていて足りない部分がある気がするので、詳しく知りたい場合は以下を参照してもらいたい。

まず、DQNに関する論文は以下がある。DQNの全体を知りたい場合はこちらを参照。(本記事は[1]の内容を元に書いている)
[1] Mnih, Volodymyr, et al. "Playing atari with deep reinforcement learning." arXiv preprint arXiv:1312.5602 (2013).
[2] Mnih, Volodymyr, et al. "Human-level control through deep reinforcement learning." Nature 518.7540 (2015): 529-533.

また、QiitaにはDQNや強化学習に関する素晴らしい記事があるので、DQNや強化学習について詳しく知りたい方はこちらを参照するとよさそう。
qiita.comqiita.com

そして、強化学習についてよく分かってなかったので以下を読んだ。強化学習の基本から書かれていてうまく理解できたと思う。

強くなるロボティック・ゲームプレイヤーの作り方プレミアムブックス版 ~実践で学ぶ強化学習~

作者: 八谷大岳,杉山将
出版社/メーカー: マイナビ出版
発売日: 2016/06/30
メディア: 単行本
この商品を含むブログ (2件) を見る

概要

Deep Q-Network (DQN)はGoogleの子会社であるDeepMind社が開発した手法である。
この手法を使って、Atari 2600の複数のゲームをうまく学習させている。
(Youtubeで"Deep Q-Network"とかで調べると実際に学習させているものが出てくる)

DQNは深層学習と強化学習を利用し学習していくアルゴリズムである。
ゲームの画面を元に次の行動を決定しながら、スコアを元に最適な行動になるように改善していく。

深層学習

深層学習(Deep Learning)とは、人間の神経を模したニューラルネットワークを多層にしたものを利用し学習を行う方法である。
各ユニットの間に重みやバイアスが定義されており、データを元にそれらをうまく調整することによって学習を行っていく。

重みやバイアスを調整するための一般的な方法として、誤差逆伝搬法(Backpropagation)がある。

強化学習 - Q学習

強化学習(Reinforcement Learning)とは、ある環境にいるエージェントが環境から取得した状態 ${s}$ を元に行動 ${a}$ をし、その行動によって報酬 ${r}$ が得られる状況で、その報酬を最大化するように行動を最適化し、最適な方策 ${\pi^*}$ を求める手法である。

強化学習では、マルコフ決定過程(MDP: Markov Decision Process)でモデル化することで簡単に考えられるようになる。
このモデルでは対象の状態は現在の状態と行動のみに依存し、過去の状態や行動の状況には依存しない「マルコフ性」を仮定する。つまり、状態 ${s_t}$ において行動 ${a_t}$ をとった時に状態 ${s_{t+1}}$ に遷移する確率は ${s_i, a_i\ (\forall i < t)}$ に依存しないことである。
また、状態のみに依存する確率過程であるマルコフ過程とは異なり、MDPは方策関数 ${\pi}$ による学習者の行動決定を考慮している。

強化学習の手法としてTD学習 (Temporal Difference Learning)があり、勾配法のように現在の状況と理想の状況が近づくように反復計算を行い解く方法である。
そして、このTD学習の内の一つの手法にQ学習(Q-Learning)がある。この手法では、行動価値関数 ${Q}$ をうまく最適行動価値関数 ${Q^*}$ へと近づけながら求めていく。

この行動価値関数 ${Q}$ というのは、状態 ${s}$ と行動 ${a}$ を取り、その状態 ${s}$ において行動 ${a}$ を行う価値を返す関数である。また、最適行動価値関数 ${Q^*}$ が求められた時、状態 ${s}$ における最適方策 ${\pi^*_s}$ は ${\arg\max_aQ^*(s, a)}$ で求めることができる。

具体的には、行動価値関数 ${Q}$ を以下の関係式で最適行動価値関数 ${Q^*}$ に近づけていく
${Q_{i+1}(s, a) \leftarrow Q_i(s, a) + \alpha (r + \gamma \max_{\alpha'}Q_i(s', a') - Q_i(s, a))}$
この時、状態 ${s}$ で行動 ${a}$ をした時の報酬が ${r}$ であり、その後の状態が ${s'}$ であるとする。
また、 ${\alpha}$ は学習率(関数Qの更新幅)であり、 ${\gamma}$ は割引率(将来をどの程度割り引いて考えるかの率)である。

おまけに、このQ学習は方策オフ型(off-policy)と呼ばれている。一方でSARSA法などの方策オン型(on-policy)も存在する。方策オン型では、行動を方策 ${\pi}$ から決定し、その結果から方策評価(価値関数 ${Q^\pi}$ の計算)と方策改善(方策 ${\pi}$ を価値関数 ${Q^\pi}$ から改善)を繰り返し行って方策 ${\pi}$ を改善していくのに対し、方策オフ型では、行動は方策 ${\pi}$ に依存させずに( ${Q}$ 関数などから)決定し、その結果からは方策評価を行わず、そのまま ${Q}$ 関数などを改善していく方法である。

Deep Q-Network

${Q(s, a)}$ を状態 ${s}$ と行動 ${a}$ でテーブルにして求める方法があるが、この場合(状態全通り)×(行動全通り)の空間量がかかり、膨大になってしまう。これを回避するためには関数 ${Q(s, a)}$ の関数近似を行う。そして、DQNではニューラルネットワークによって近似を行う。

また、学習についてはExperience Replayという方法をとり、過去の経験 ${(s, a, r, s')}$ をdataset Dに保存しておき、そこからランダムにサンプリングしたミニバッチ(= 少数のサンプル集合)から学習する。このようにランダムにサンプリングして学習させるのは、時系列データの間で相関を持ち、ニューラルネットワークの更新が非効率にならないようにするためらしい。

Deep Q-Networkの手法の流れ

DQNは以下の流れで行う

はじめにdataset Dの容量をNとし、 ${Q}$ 関数をランダムな重みで初期化しておく。

初期の状態として、 ${s_1 = \{x_1\}}$ , 前処理済みのシーケンス ${\phi_1=\phi(s_1)}$ とする。
行動 ${a}$ を決定
行動結果の報酬 ${r}$ と次の状態 ${s'}$ を計算
過去の行動から学習

この2~4のstepを1つのepisode内 (つまり、一回のゲーム中)で繰り返し行う。

そして、この1~4をM回のepisodeで繰り返す。

ここで出てくる関数 ${\phi}$ はニューラルネットワークに入力として与えられるように、時系列データを固定長のデータにする関数である。論文中では直前4フレーム分のゲームの画像データを抜き出す関数となっている。
また、 ${x_t}$ は時間 ${t}$ におけるゲームの画面データ (画面のpixelデータ)を表している。

以下で各手順(2~4)の説明をする。

2. 行動 ${a}$ を決定

この行動の決定にはε-greedy法を用いる。
この方法では、εの確率で全行動からランダムに行動 ${a_t}$ を決定し、(1-ε)の確率で ${Q(\phi(s_t), a; \theta)}$ が最大となるような行動 ${a}$ を ${a_t}$ として決定する。

3. 行動結果の報酬 ${r}$ と次の状態 ${s'}$ を計算

1で決定した行動 ${a_t}$ を行い、その結果の報酬 ${r_t}$ を計算する。
また、この時 ${x_t}$ も取得し、次の状態を ${s_{t+1} = s_t, a_t, x_t}$ とする。
そして、 ${\phi_{t+1} = \phi(s_{t+1})}$ を得る。

論文中では、報酬 ${r}$ を正規化し、正のスコアを1、負のスコアを-1、無報酬を0としている。この正規化により、誤差の微分のスケールを制限でき、複数のゲームに対して同じ学習率を適用しやすくなるらしい。

4. 過去の行動から学習

2で得た情報を含めた ${(\phi_t, a_t, r_t, \phi_{t+1})}$ をdataset Dに保存する。そして、このdataset Dからランダムに ${(\phi_j, a_j, r_j, \phi_{j+1})}$ のミニバッチをサンプリングしてきて、そこから ${y_j}$ を計算する。
${y_j}$ は以下のように計算する。
${ \begin{eqnarray} y_j =\left\{ \begin{array}{ll} r_j & (\phi_{j+1}\text{で終端の場合}) \\ r_j + \gamma\max_{a'}Q(\phi_{j+1}, a'; \theta) & (\phi_{j+1}\text{で終端でない場合}) \\ \end{array} \right. \end{eqnarray} }$

そして ${(y_j - Q(\phi_j, a_j; \theta))^2}$ の値が0に近づくように勾配を計算し、関数Qのパラメタθを調整する。(この時、関数QはNNなのでユニット間の重みとバイアスを調整していく)

論文では、勾配の計算にRMSPropという手法を用いている。(ミニバッチサイズは32)

ニューラルネットワークの構築

DQNにおけるQ関数は、前処理済みの状態 ${\phi_j}$ を入力とし、各行動の価値を出力するNNとして構築する。
このNNは畳み込みニューラルネットワーク(CNN)で構築している。CNNは画像認識に応用されるNNで、ある部分の領域の複数ユニットの情報を圧縮してうまく特徴量を抽出することができる。

実装話に続く...?

とりあえずTensorflowを使ってみたいと思ってたので、DQNを実際にTensorflowで実装してみた。しかし、実装が怪しい気がするので時間があれば実装しなおして書くかもしれない。~~(数日でTensorflowを使いこなすのは難しかった...)~~

日々ｄｒｄｒする人のメモ

今日も明日もｄｒｄｒ