Hado van Hasselt, Arthur Guez, David Silver
AAAI 2016
arXiv, 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$ に対して行う？）．

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

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は行動数が増えても誤差が小さい．

関数の近似について

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

左の列
紫色のプロットが真値，緑色のプロットが，ある１つのactionについての推定結果．
真ん中の列
緑色のプロットが真値，薄い緑色の線が全action（10コ）についての推定結果，黒色破線が推定結果のmax．
右の列
真値との推定誤差．橙色がQ-learning，青色がDouble Q-learning．
Double Q-learningの方が全体的に誤差が小さい．

技術や手法のキモ

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

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を上回っている．これはより良い方策が得られていることを示している．

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

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

議論はあるか

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

次に読むべき論文

Dueling Network Architectures for Deep Reinforcement Learning