Deep Q Network (DQN)

http://www.nature.com/nature/journal/v518/n7540/full/nature14236.html
[1312.5602] Playing Atari with Deep Reinforcement Learning

Q-Learningにおいて、action-value functionをDNNで関数近似したもので、Deep RLの皮切りとなった.

Q-Learningとはなんだったか?

自分用の強化学習メモからの復習的ななにか.

Model-free、Off-Policy、Value-basedなControl

{\displaystyle
Q(S_t,A_t) \leftarrow Q(S_t, A_t) + \alpha \biggl(R_{t+1} + \max_{a'} \gamma Q(S_{t+1}, a') - Q(S_t, A_t) \biggr)
}
target policy {\pi} : greedy
behavior policy {\mu} : {\epsilon}-greedy
(TD-TargetにはサンプリングしたBellman Optimality Equation)

パラメータ{\mathbf{w}}関数近似した場合、
{\displaystyle
\mathbf{w} \leftarrow  \mathbf{w} - \alpha \biggl(r_{t+1} + \max_{a'} \gamma \hat{q}(s_{t+1}, a'; \mathbf{w})  - \hat{q}(s_t, a_t ; \mathbf{w}) \biggr) \nabla_{\mathbf{w}} \hat{q}(s_t, a_t ; \mathbf{w}) 
}

論文まとめ

そもそも、action-value(以下Q)関数を非線形関数で近似すると、RLは不安定あるいは発散することが知られている.
理由は例えば以下のようなことが挙げられる.

  • 観測間に依存関係が存在する.
  • Qを多少更新したただけでも、政策関数が大きく変わる可能性があるので、観測データの分布も依存関係も大きく変わってしまう可能性がある.

この不安定性を打破するために以下の2つを行う.

Experience Replay

生物学的なメカニズム(海馬まわり?)からの発想.
過去の観測データをランダムサンプリングして、観測間に生じる依存関係を除去することで、観測データ分布の変化を滑らかにする.
具体的には、経験e_t=(s, a, r, s')を各時刻tにおいて、バッファD_t= \lbrack e_1, ..., e_t \rbrackにプールする. Q関数を更新する時は、このバッファからランダムサンプリングしたミニバッチ(s, a, r, s') \sim U(D)で行う.

Target Network

一定間隔で更新するQ関数をTD-targetに利用する. これも依存関係を除外することに貢献している.
Q-LearningにおけるTD-Target、r + \gamma \max_{a'} Q(s', a'; \theta_i)を、Cステップ毎に更新されるパラメータ\displaystyle \theta_i^{-}で置き換える. (\theta_ii iterでのパラメータ)

DQN

以上をまとめると、DQNは以下の最小化問題を解くことになる.
{ \displaystyle
\min_{\theta_i} L_i(\theta_i)= \min_{\theta_i} \mathbb{E}_{(s,a,r,s') \sim U(D)} 
\lbrack (r + \gamma \max_{a'} Q(s', a'; \theta_i^{-}) - Q(s, a; \theta_i))^2 \rbrack
}

その他

上記の2点が中心ではあるが、その他にも学習を進める上でいくつかのことを行っている.

Error Clipping

これを行うことで更に安定性を上げている.
つまり、TD-Error r + \gamma \max_{a'} Q(s', a'; \theta_i^{-}) - Q(s, a; \theta_i)が、
(-1,1)の外側の場合は絶対値誤差を、内側の場合は二乗誤差利用する.
これは、Hurber Lossに対応する.

前処理、flickeringの除去

あるオブジェクトは偶数フレームにしか現れないなどの現象(flickering)を回避するために、前フレームと現フレームの最大値を1フレームとする.
更にこれを、グレースケール化して、84x84にリサイズする.
直近の4フレームにこの前処理を施したものを1ステートとする.

他frame skipping, reward scaling

実装

github.com

前処理

# gray-scaling 
gray = cv2.cvtColor(obs, cv2.COLOR_RGB2GRAY)
# resizing
gray = cv2.resize(gray, (84, 84))
# squashing
return (gray - 127.5) / 127.5
pre = self._preprocess(obs)
self.state = np.concatenate( (self.state[:, :, 1:], pre[:,:,np.newaxis]), axis=2 )

OpenAI gymではframe skippingなどは内部的に行われているようで、特に何かする必要はなさそう.

サンプリング

samples = random.sample(self.D, self.batch_size)

パラメータのコピー(target networkの更新)

def copy_params(src, dst):
    src_params = [v for v in tf.trainable_variables() if v.name.startswith(src.scope)]
    dst_params = [v for v in tf.trainable_variables() if v.name.startswith(dst.scope)]
    op = [d.assign(s) for s, d in zip(src_params, dst_params)]
    return op

Hurber Loss

def Hurber_loss(x, y, delta=1.0):
    error = tf.abs(y - x)
    cond = tf.less(error, delta)
    return tf.where(cond,
                    0.5*tf.square(error),
                    delta*error - 0.5*tf.square(delta))

r + \gamma \max_{a'} Q(s', a'; \theta_i^{-})

# r: reward
# s_: next state
# done: 1 (terminated), 0 (otherwise)
self.y = self.r + gamma*(1.0 - self.done)*tf.reduce_max(target_Q(self.s_), axis=1, keep_dims=True)

Q(s, a; \theta_i)

self.probs = Q(self.s)
first = tf.expand_dims(tf.range(self.batch_size), axis=1)
indices = tf.concat(values=[first, self.a], concat_dim=1)
# gather corresiponding q_vals
self.q_val = tf.expand_dims(tf.gather_nd(self.probs, indices), axis=1)

\epsilon-greedy

if np.random.rand() < epsilon:
    a = env.action_space.sample()
else:
    a = dqn.greedy(s, sess)

\epsilon-decay

epsilon = 1.0 if global_step < FLAGS.replay_start_size else \
    max(FLAGS.min_epsilon, np.interp(
        global_step, [0, FLAGS.decay], [1.0, FLAGS.min_epsilon]))

結果

OpenAI gymのMsPacman-v0
あんまり回してないので、微妙な結果.
メモリが少ないのでReplay Bufferのサイズも50000程度.
機会があったらもっと長い時間学習させたい.
f:id:wanwannodao:20170312185804p:plain