Deep Reinforcement Learning with Double Q-learning (Double DQN)

Deep Reinforcement Learning with Double Q-learning
[1509.06461] Deep Reinforcement Learning with Double Q-learning

論文まとめ

Q-learningは、maxを取っている関係上、action-valueを過大評価(overestimate)する傾向があることが知られている.

これまでに挙げられていた過大評価の原因

  • 柔軟性が不十分な関数近似による誤差 Thrun and Schwartz (1993)
  • 環境のノイズ van Hasselt (2010)

この論文ではより一般的に、任意の推定誤差によって過大評価は引き起こされることが示されている.
学習過程では必ず不正確な推定値になってしまうのでこれは重要な問題.

Double Q-learning (van Hasselt, 2010)

そもそも、Q-learningのTD-targetは以下の形であった.
{
\newcommand{\argmax}{\mathop{\rm argmax}\limits}
\displaystyle
R_{t+1} + \gamma \max_aQ(S_{t+1}, a; \theta_t) \\
\displaystyle = R_{t+1} + \gamma Q(S_{t+1}, \argmax_a Q(S_{t+1}, a; \theta_t); \theta_t) 
}
つまり、greedy policyに基づく行動の選択と、その価値の推定は同じQ関数に基づいている.
これは過大評価に繋がりやすく、楽観的(optimistic)な価値の評価になりやすい.

そこで選択と推定を分離することを考える.
つまり、パラメータは\theta\theta'があり、一つはgreedy policyの行動選択に、もう一つは価値の推定に使われる.
するとTD-targetは以下のようになる.
{ \newcommand{\argmax}{\mathop{\rm argmax}\limits}
\displaystyle
R_{t+1} + \gamma Q(S_{t+1}, \argmax_a Q(S_{t+1}, a; \theta_t); \theta_t') 
}

二つの価値関数をランダムに選んだ別個の経験(experience)からそれぞれを更新する.
\theta\theta'の役割を交互に変えることで更新する.
(よくわかってない)

推定誤差によるOveroptimism

過大評価の上界(Thrun and Schwartz (1993))

action-valueが[-\epsilon,\epsilon]の一様分布に従う誤差を含んでいる場合、
過大評価の上界は{\displaystyle \gamma \epsilon \frac{m-1}{m+1}  } (mは行動数)

過大評価の下界

価値の推定が平均的に正しい、{\displaystyle \sum_a(Q_t(s, a)-V_{*}(s))=0 }
が、どこかで何かしらの誤差が生じている{\displaystyle \frac{1}{m} \sum_a (Q_t(s,a)-V_{*}(s))^2 = C } (C>0)
ような時、{\displaystyle \max_a Q_t(s,a) \geq V_{*}(s) + \sqrt{\frac{C}{m-1}}}
となることが証明されている. つまり真値より高く推定(過大評価)してしまう.
また、同じ条件でDouble Q-learningの場合、絶対値誤差の下界が0になることも証明されている.

この式から、下界としては行動数mが増えると小さくなるが、これはあくまで下界の話で、
一般的には行動数が増えると真値との誤差も大きくなる.
またDouble Q-learningの場合は行動数が増えても誤差が小さいことも実験的に示されている.

価値関数と近似関数の柔軟性

真の価値関数をサンプリングして多項式近似した結果として、
価値関数に関わらず、また近似関数の柔軟性に関わらず過大評価は発生することが示されている.

現実的には真値ではなく、bootstrappingするのでより一層悪化する可能性がある(よってpolicyにも影響がでる).

DQNはDNNよって柔軟な関数近似を行えるが、その場合でも過大評価してしまうことがある.

(※ explorationの手法としてのoptimismとは別の話なので混同してはいけない.)

Double DQN

上述のようにDouble Q-learningは選択と評価を分離することで過大評価を回避する.
完全な分離ではないが、DQNのtarget networkが使える(別のネットワークが必要ない).

よってtarget networkのパラメータを\theta_t^{-}とすると、TD-targetは、
{ \newcommand{\argmax}{\mathop{\rm argmax}\limits} 
\displaystyle
R_{t+1} + \gamma Q(S_{t+1}, \argmax_a Q(S_{t+1}, a; \theta_t); \theta_t^{-}) 
}
となる. TD-targetが変わる以外はDQNと同じ.

DQN vs Double DQN

以下のグラフの通り、Double DQNではDQNよりも過大評価がかなり抑えられていることが確認できる.
f:id:wanwannodao:20170305134519p:plain
(論文より引用)

以下のグラフは、価値の推定値とゲームのスコアのグラフだが、過大評価が生じ始めるとスコアが下がることが見てわかる.
つまりこれは、過大評価がpolicyに悪影響を与えるということを意味している.
f:id:wanwannodao:20170305134523p:plain
(論文より引用)
DQNのこの性能悪化は、Off-Policy+関数近似の本質的な不安定性に起因したものではなく、Q-learningの過大評価に起因したものということを意味している.
(現にDouble DQNは安定している)

過大評価は必ずしも悪影響に繋がるわけではないが、減らすことで学習の安定化が図れるという事が言える.
また、Double DQNはより汎用的なpolicyを学習できる(ロバスト性が高い)ということも示されている.

※必ずしも悪影響に繋がらないとは、例えば全てのaction-valueが一様に過大評価されていれば、相対的な振る舞いは同じなので悪くはならない

Double DQN用のチューニング

DQNからDouble DQN用にハイパーパラメータ等を調整することでより高い性能が得られる.

Target Networkの更新間隔

10,000から30,000フレーム間隔に
更新した直後は通常のQ-learningに戻ってしまうので、間隔を広げる

\epsilon-greedy

\epsilon(の最終値)を学習時は0.1から0.01に、評価時は0.001に

shared bias

出力の行動価値に対するbias(最後のfc層のbiasか?)を共有する.

下二つの根拠はわからなかった.

実装

github.com

TD-target

a_max = tf.expand_dims(tf.argmax(Q(self.s_, reuse=True), axis=1), axis=1)
a_max = tf.to_int32(a_max)
target_q_val = tf.expand_dims(
       tf.gather_nd(target_Q(self.s_),
                     tf.concat(values=[first, a_max], concat_dim=1))
       , axis=1)
self.y = self.r + gamma*(1.0 - self.done)*target_q_val

shared bias

 # shared bias
with tf.variable_scope("shared", reuse=s_bias):
    b = tf.get_variable("shared_b", [self.a], dtype=tf.float32,
    initializer=tf.constant_initializer(0.0))

結果

OpenAI gymのMsPacman-v0
500000ステップで\epsilonが0.01に到達する設定なので、あまり学習が進んでいないかもしれない.
f:id:wanwannodao:20170313182321p:plain