Deep Reinforcement Learning with Double Q-learningを読んだ

Hado van Hasselt, Arthur Guez, David Silver
AAAI 2016
[arXiv](https://arxiv.org/abs/1509.06461), [pdf](https://arxiv.org/pdf/1509.06461.pdf)

# どんなもの？
DQNとDouble Q-learningを組み合わせたDouble DQNを提案．
学習時の過大評価(overestimations)を低減し，DQNを上回るパフォーマンスを実現．
推定誤差が与える影響について，例を交えて丁寧に議論をしている印象．

# 先行研究との差分
DQNとDouble Q-learningを組み合わせることで学習時の過大評価(overestimations)を低減．
Atari 2600 gamesのスコアでDQNを上回ることを明らかにした（過大評価の低減がゲームのスコアの上昇に繋がる）．

# Q-learningの問題点とその解決策
学習時に推定したaction valuesに対してmax演算を行うため，action valuesを過大評価してしまうことがある．これは以下の２つの影響による．

- 十分に柔軟でない関数による近似（Thrun and Schwartz, 1993）
- ノイズ（van Hasselt, 2010）

この問題を解決するためにDoule Q-learningが提案された．
Q-learningでは行動の選択と評価に同じ関数( $\theta_t$ )を用いており，これが過大評価に繋がると考えた．
そこでDouble Q-learningでは二つの関数( $\theta_t$と$\theta_t^{\prime}$ )をそれぞれの役割（選択と評価）を交互に変えながら更新する．

>For each update, one set of weights is used to determine the greedy policy and the other to determine its value.

Q-learning, Double Q learningの更新式のtarget$Y_t^{Q}, Y_t^{DoubleQ}$は以下になるみたい（ $\theta^{\prime}$ の更新式中のargmaxは $\theta$ に対して行う？）．

```math
Y_t^{Q} = R_{t+1} + \gamma Q(S_{t+1}, arg\max_{a} Q(S_{t+1}, a; \theta_t); \theta_t)
```

```math
Y_t^{DoubleQ} = R_{t+1} + \gamma Q(S_{t+1}, arg\max_{a} Q(S_{t+1}, a; \theta_t); \theta_t^{\prime})
```

# 推定誤差について
過大評価の上界と下界は証明されている（上界についてはaction valuesが一様な誤差を含む場合に限り？）．
一般に行動数が増えるにつれて推定誤差は大きくなる．
以下は行動数に対する推定誤差．Double Q-learningは行動数が増えても誤差が小さい．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/b11c46dd-f1fc-2b05-0b9d-2609bc957488.png)

# 関数の近似について

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/7e4f2628-a061-06ef-4b5c-586ca6baab59.png)

３つの関数の近似結果を比較していた（設定はよく分からなかった）．
stateの関数と見立てて，action valueの推定をしているようだった．行動数は10．
図の各行はそれぞれ異なる関数の近似結果を表している．

- 左の列
紫色のプロットが真値，緑色のプロットが，ある１つのactionについての推定結果．

- 真ん中の列
緑色のプロットが真値，薄い緑色の線が全action（10コ）についての推定結果，黒色破線が推定結果のmax．

- 右の列
真値との推定誤差．橙色がQ-learning，青色がDouble Q-learning．
Double Q-learningの方が全体的に誤差が小さい．

# 技術や手法のキモ
Q-learningのように行動の選択と評価を切り離す．
更新式のtarget$Y_t^{DoubleDQN}$は，

```math
Y_t^{DoubleDQN} = R_{t+1} + \gamma Q(S_{t+1}, arg\max_{a} Q(S_{t+1}, a; \theta_t); \theta_t^{-})
```

$\theta_t^{-}$はDQNのtarget network．
これ以外にDQNからの変更点は無し．

# どうやって有効性を検証したか
Atari gamesに対してテストを行い，そのスコアを比較．
以下は４種類のゲーム（Alien, Space Invaders, Time Pilot, Zaxxon）に対するaction valuesの推定結果．橙色がDQN，青色がDouble DQNで直線はそれぞれの真値（学習後に獲得）．DQNと比べ，Double DQNはより真値に近い推定が行えている．
また，どのゲームでもDouble DQNの真値がDQNを上回っている．これはより良い方策が得られていることを示している．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/8663faf0-3be9-5d24-e0f5-fd1e04e80c4c.png)

以下は２種類のゲーム（Wizard of Wor, Asterix）に対するaction valuesの推定結果とそのスコア．DQNが大きなoverestimationを起こしており，これがスコアの悪化に繋がっていることが分かる．一方でDouble DQNは安定している．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/5250c33c-2955-9894-2617-5014c1f69853.png)

最後に57種類のAtari gamesに対するスコア（人間のスコアを100%）．多くのゲームでDQNを上回っていることが分かる．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/259451/5784fdba-6f1f-8189-8cd2-1a56f684b580.png)


# 議論はあるか
Q-learningにおける過大評価の原因を考察．
Double Q-learningを提案し，過大評価の低減と安定した学習を実現．
Atari gamesによるテストでDQNを上回る性能．

# 次に読むべき論文
[Dueling Network Architectures for Deep Reinforcement Learning](https://arxiv.org/abs/1511.06581)