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