いまさらだけどTensorFlowでDQN(不完全版)を実装する

# DQNって何？
もはやこの手の記事は至るところにあるので、あえて説明しなくてもいいような気がしますが、強化学習の一つの方法であるQ-LearningのQ関数部分を、DeepLearningを使って近似し、それまで難しかった画像から直接Q値を推定することを可能にした学習手法です。
[Google DeepMind](https://deepmind.com/)によって2014に発表され、Atariの数あるゲーム(インベーダーゲームとか、ブロック崩し)で、事前知識なしにコンピュータが高得点が取れるようになることが示されて、注目されました
ちなみに、DQNはDeepQNetworkの略です。

# じゃあTensorFlowって何？
[TensorFlow](https://www.tensorflow.org/)はGoogleが出している数値計算ライブラリです(雑)。
DeepLearning専用のライブラリではなく、様々な機能があります。
もちろん、DeepLearningを実装するのに必要なモジュールも充実しています。

# DQN(不完全版)？？？
Nature論文のDQNはOptimizerとしてA.Gravesが[この論文](http://arxiv.org/abs/1308.0850)で導入した、通常とは異なるRMSProp(以下、RMSPropGraves)を使っています。
標準のTensorFlowには、RMSPropGravesは実装されていないので、標準のTensorFlowにもある通常版RMSPropを使ったDQNが、この記事で言うDQN(不完全版)です。
Natureの論文を見るとRMSPropとして書いてあり、紛らわしいのですが、いろいろなところに転がっているサンプルソースも通常のRMSPropを使って、これがDQNだ！的な感じになってるので、他の人が書いているものを参考にする場合は、このあたり注意が必要です。
具体的なRMSPropとRMSPropGravesの違いは以下の通りです。
###RMSProp

```math
{\begin{align}
  n &\leftarrow \rho n + (1-\rho)g_r^2 \\
  m &\leftarrow \beta m - \frac \alpha {(n + \gamma)}g_r
\end{align}}
```

###RMSPropGraves

```math
{\begin{align}
  n &\leftarrow \rho n + (1-\rho)g_r^2 \\
  g &\leftarrow \rho g + (1-\rho)g_r \\
  m &\leftarrow \beta m - \frac \alpha {(n - g^2 + \gamma)}g_r
\end{align}}
```

イメージ的には、RMSPropが平均的な傾きの大きさを見て、値の更新幅を変えるのに対して、RMSPropGravesは傾きの分散に応じて、更新幅を変える感じでしょうか。
あとここで実装したDQNが、もう一点オリジナルと違うのは、通常のRMSPropを使う関係で、論文にあるLoss Clippingも行いません。
理由は、Clippingしたら、まともに学習が進まなかったからです・・・

# DQN(不完全版)を実装するには
## 必要なライブラリ等

- [TensorFlow](https://www.tensorflow.org/)
- [Arcade Learning Environment](http://www.arcadelearningenvironment.org/)
- 学習させたいゲームのRom

の3つが最低でも必要です(python関係のライブラリはTensorFlowのインストールで入ります)
Romは検索すればそこら中に転がっていてすぐ見つかると思います。(Atari 2600 romとかで検索してみてください)
RL-glueを使ってる方もいますが、Arcade Learning Environmentは標準でPythonのAPIも用意されているので、必須ではないです。
ここでは上の3つが準備出来ているものとして進めます。
[GitHubにコード](https://github.com/yuishihara/DQN-tensorflow/tree/dqn_incomplete_ver)は載せているので、以下はTensorFlowで実装する際の要点を書いておきます。

## 実装
### TensorFlowでDQNのネットワークを書く
DQNのネットワークは下記のようになっています。入力画像を入れて、ゲームをするのに可能な各動き(上下左右など)に対するQ値を出力するような構成です。

- 入力: 84*84のゲーム画面
- 第1層: Filter数 32, Filter size 8*8, stride 4, paddingなしのconvolution layer
- 第2層: Filter数 64, Filter size 4*4, stride 2, paddingなしの convolution layer
- 第3層: Filter数 64, Filter size 3*3, stride 1, paddingなしのconvolution layer
- 第4層: (input 3136), output 512のFully connected layer
- 第5層: (input 512), output ゲームで使えるキー操作数(ブロックくずしなら4)のFully connected layer
- 活性化関数: Reluを使う

TensorFlowでは、パラメータである重みと、実際の演算部分は分かれているので、実装は次のような感じになります(パラメータに関しては、第1層部分と、第4層部分の抜粋)。

```py
  # Parameter部分
  def __init__(self, image_width, image_height, num_channels, num_actions):
    # conv1
    self.conv1_filter_size = 8
    self.conv1_filter_num = 32
    self.conv1_stride = 4
    self.conv1_output_size = (image_width - self.conv1_filter_size) / self.conv1_stride + 1  # 20 with 84 * 84 image and no padding
    self.conv1_weights, self.conv1_biases = \
      self.create_conv_net([self.conv1_filter_size, self.conv1_filter_size, num_channels, self.conv1_filter_num], name='conv1')

    # inner product 1
    self.inner1_inputs = self.conv3_output_size * self.conv3_output_size * self.conv3_filter_num  # should be 3136 for default
    self.inner1_outputs = 512
    self.inner1_weights, self.inner1_biases = self.create_inner_net([self.inner1_inputs, self.inner1_outputs], name='inner1')

  def create_conv_net(self, shape, name):
    weights = tf.Variable(tf.truncated_normal(shape=shape, stddev=0.01), name=name + 'weights')
    biases = tf.Variable(tf.constant(0.01, shape=[shape[3]]), name=name + 'biases')
    return weights, biases

  def create_inner_net(self, shape, name):
    weights = tf.Variable(tf.truncated_normal(shape=shape, stddev=0.01), name=name + 'weights')
    biases = tf.Variable(tf.constant(0.01, shape=[shape[1]]), name=name + 'biases')
    return weights, biases

  # 実際のNetworkの演算部分
  def forward(self, data):
    conv1 = tf.nn.conv2d(data, self.conv1_weights, [1, self.conv1_stride, self.conv1_stride, 1], padding='VALID')
    conv1 = tf.nn.relu(conv1 + self.conv1_biases)
    conv2 = tf.nn.conv2d(conv1, self.conv2_weights, [1, self.conv2_stride, self.conv2_stride, 1], padding='VALID')
    conv2 = tf.nn.relu(conv2 + self.conv2_biases)
    conv3 = tf.nn.conv2d(conv2, self.conv3_weights, [1, self.conv3_stride, self.conv3_stride, 1], padding='VALID')
    conv3 = tf.nn.relu(conv3 + self.conv3_biases)
    shape = conv3.get_shape().as_list()
    reshape = tf.reshape(conv3, [shape[0], shape[1] * shape[2] * shape[3]])
    inner1 = tf.nn.relu(tf.matmul(reshape, self.inner1_weights) + self.inner1_biases)
    inner2 = tf.matmul(inner1, self.inner2_weights) + self.inner2_biases
    return inner2
```

### Replay MemoryとTarget Network
DQNは非常に学習が不安定で、得られた報酬からすぐにフィードバックをかけて学習させると、うまく学習が進みません。また、Q学習の下記更新式の$Q(s_{t+1},a)$部分は、ネットワークの出力値を利用する必要があるのですが、重みの更新が頻繁に走っているネットワークの出力は不安定でそのままではうまく行きません。

```math
{\begin{align}
  Q(s_t,a_t) &\leftarrow Q(s_t,a_t) + \alpha(r + \gamma \max_a Q(s_{t+1},a) - Q(s_t, a_t))
\end{align}}
```

そこで、DQNでは、報酬をすぐネットワークにフィードバックするのではなく、状態$s_t$で行動$a_t$をしたところ、状態$s_{t+1}$に変化し、いくつ報酬$r$を得たかを覚えておいて、この記憶した状態からランダムにサンプリングして、学習用のデータとして利用します。この記憶をReplayMemoryと呼びます。
また、$Q(s_{t+1},a)$は、重みの更新が走っているネットワークのコピーを持っておき、そこから算出します。このコピーをTarget Networkと呼びます。もちろんネットワークを毎Iteration起きにコピーするのでは意味がないので、一定の間隔(10000 Iterationおき)で、コピーを走らせます。

TensorFlowでネットワークのコピーは下記のような感じで実装できます。

```py
  def weights_and_biases(self):
    return [self.conv1_weights, self.conv1_biases,
            self.conv2_weights, self.conv2_biases,
            self.conv3_weights, self.conv3_biases,
            self.inner1_weights, self.inner1_biases,
            self.inner2_weights, self.inner2_biases]

  def copy_network_to(self, target, session):
    copy_operations = [target.assign(origin)
                       for origin, target in zip(self.weights_and_biases(), target.weights_and_biases())]
    session.run(copy_operations)
```

### Optimizer
上でも書きましたが、RMSPropを使って学習する場合、オリジナルの論文にある学習率0.00025では、全く学習がすすみません。そこで、0.000025とひと桁小さくして、さらにクリッピングはやめて学習させます。(他にも学習がうまく行く設定があるかもしれませんが、調べてません)

```py
optimizer = tf.train.RMSPropOptimizer(learning_rate=0.000025).minimize(loss)
```

# 結果
最後に、上記の実装で得られた結果を載せておきます。

遊ぶゲーム:Breakout(ブロック崩し)
ReplayMemory数:50000(持っているマシンのメモリ制約による。オリジナルはこれの20倍)
それ以外は、Nature論文のパラメータのまま

これを動かすと、だいたい30万Iterationくらいで、学習の効果が見てわかるようになってきて、ブロック崩しの場合だと、10点から20点くらい取れるようになります。
さらに学習を続ける(200万Iterationくらい)と、40点位はとれるようになります。(オリジナルの論文の性能には届いていません)

こんな感じ(40万Iteration付近の動画)：

<blockquote class="twitter-video" data-lang="ja"><p lang="en" dir="ltr">DQN with tensorflow <a href="https://t.co/nAOEXuEWqV">pic.twitter.com/nAOEXuEWqV</a></p>&mdash; EpsilonCode (@epsilon_code) <a href="https://twitter.com/epsilon_code/status/757185059233214464">2016年7月24日</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

# DQN(完全版)は？
別記事で後日載せる予定です→[載せました](http://qiita.com/yuishihara/items/73e8f8c4a30b8148d9fc)

# 参考文献
[DQNのNature論文](https://storage.googleapis.com/deepmind-data/assets/papers/DeepMindNature14236Paper.pdf)
[Chainerでの実装](http://qiita.com/Ugo-Nama/items/08c6a5f6a571335972d5)