DQNの進化史 ①DeepMindのDQN - どこから見てもメンダコ

DeepMindのDQNからR2D2くらいまでの深層強化学習（Q学習）の発展の歴史を、簡単な解説とtensorflow2での実装例と共に紹介していきます。

まずは深層強化学習の新たな時代を切り開いたDeepMindのDQN（2013）です。論文からはわかりにくいatari環境向けの実装上のテクニックとDQNを構成する各要素が後継手法でどのように改良されていったかのレビューに焦点を置いてBreakout（ブロック崩し）向けにtensorflow2での実装例を紹介します。

DQNシリーズ
DQNの進化史 ①DeepMindのDQN - どこから見てもメンダコ
 DQNの進化史 ②Double-DQN, Dueling-network, Noisy-network - どこから見てもメンダコ
 DQNの進化史 ③優先度付き経験再生, Multi-step learning, C51 - どこから見てもメンダコ
 DQNの進化史 ④Rainbowの実装 - どこから見てもメンダコ

はじめに
トレーニングループの実装
Experience Replay
- replay bufferの実装
- 経験再生の改良
Qネットワークの実装
ネットワークの更新
訓練の実行
次： Double DQN, Dueling Network

はじめに

[1312.5602] Playing Atari with Deep Reinforcement Learning

Human-level control through deep reinforcement learning | Nature

Human-level control through deep reinforcement learning (pdf)

DeepMind社によって発表された Deep-Q-Network (arxiv 2013, nature 2015) は、"強化学習に深層CNNを導入することでレトロゲームを人間レベルでプレイできるようになる！" という結果でもって世界に衝撃を与え、深層強化学習の新時代を切り開いたまさにエポックメイキングと言うべき手法です。発表は2013年ながら最新の強化学習手法でもDQNをベースにしたものは多く、深層強化学習の初学者は必ず学ぶことになる手法です。

しかしDQNは初学者が必ず学ぶことになる手法であるにも関わらず再現実装難易度がそこそこ高いです。これはDQNのパフォーマンスがハイパーパラメータに非常にsensitiveである上に、論文を読むだけでは分かりづらい実装上の細かいテクニックが多く存在するためです。

そこで、本記事ではatari環境を攻略するための実装上のテクニック、およびDQNの各構成要素がその後の後継手法でどう発展していったかに焦点を置いてtensorflow2での実装例を紹介していきます。

※注意： DQNそのものの説明はすでに良記事がたくさんありますので基本的なアルゴリズム解説は最低限です。

トレーニングループの実装

ネットワーク更新以外のエージェントの実装は以下のようになります。

それではトレーニングループの各要素を確認していきましょう。

BreakoutDeterministic-v4

Breakoutはいわゆるブロック崩し環境です。gymには似た名前の環境(Breakout-v0, Breakout-v4とか)が多数実装されていますが、基本的には BreakoutDeterministic-v4を使ってください。このブロック崩し環境では必ず指示した通りの行動が実行され、高すぎるフレームレートを間引くため毎回4フレームスキップします。これ以外の環境だと指示した通りに動かなかったりフレームスキップ数がランダム化されたりと環境の遷移が確率的になり~~（クソゲーでは？）~~、攻略難易度が劇的上昇します。

Difference between Breakout-v0, Breakout-v4 and BreakoutDeterministic-v4? · Issue #1280 · openai/gym · GitHub

POMDPへの対応

Q学習はMDP（マルコフ決定過程）を前提としています。MDPとは乱暴に言うなら適切なアクション判断に必要な情報はすべて現在の状態の観測に含まれている、という仮定が成立するような系です。Breakout環境では現在の状態の観測とは現在の画面(frame)にあたります。しかし1フレームだけではアクション決定には情報がまったく不十分です。

f:id:horomary:20210125000147p:plain:w400 — ボールは上と下のどちらに進んでいるでしょうか？

適切なアクション選択のためには、もっと過去の情報を加味してアクションを決定する必要があります。このような系をPOMDP（部分観測マルコフ決定過程）と言います。そこでDQNでは直近4フレームを現在の状態と定義することで、本来POMDPであるatari環境をMDPっぽい系にすることに成功しQ学習の適用を可能にしました。

直近４フレームを現在の状態として疑似MDPとするDQNのアプローチはBreakoutのような反射神経要素の強いゲームでは十分に成功しましたが、一部のゲームでは直近4フレームでもなお情報が不十分であることが明らかでした。このようなPOMDP環境に対応するアプローチの一つがRNNの導入です。このアプローチは当初（[1507.06527] Deep Recurrent Q-Learning for Partially Observable MDPs）は思っていたほどうまくいかなかったのですが、2018年発表のR2D2（Recurrent Experience Replay in Distributed Reinforcement Learning (ICLR 2019) ）でついに大きな成功を収めました。

直近4フレームの保持

さて、DQNの疑似MDPアプローチのためには直近4フレームを保持しつづける必要があります。ここで便利なのがPython標準ライブラリcollections.dequeです。dequeは listと同様に使えますが、指定された最大要素数（maxlen）を超える要素が追加された場合は"First in First out"でもっとも古い要素を削除するので直近Nフレームを保持する処理をスッキリ書くことができます。
ちなみに、ゲーム開始直後は当然4フレームに満たないので初期フレーム×4を直近4フレームとすることに注意です。

フレームの前処理

CNNに入力するために各フレームは適切な前処理が必要です。具体的には余分な部分（スコア表記など）をトリミングし、二値化し、正方形にリサイズし、正規化します。ごく基本的な画像処理なのでPILでもtensorflow.imageでも自分の好きなライブラリで書きましょう。ただしopencvはなんか処理が重いので使わない方がいいです。

ε-Greedy方策によるアクション決定

局所最適解に陥らないために探索と活用（Exploration vs. Exploitation）のバランスをうまくとることは強化学習において重要な課題の一つです。しかし、もっともシンプルなQ学習では常にQ関数を最大化するアクションを採用する決定論的方策である”貪欲方策 (Greedy policy)”を使用するので、探索力の弱さという問題を抱えることとなります。

貪欲方策
$\displaystyle{ a = \underset{a} {\text{argmax }} Q(s, a) }$

貪欲方策では学習初期にたまたま価値の高くなった行動をとり続けてしまいます。そこで、DQNではこのQ学習の探索力の弱さを補うためにε-Greedy法を採用します。この方法はごく単純で、行動の決定時にεの確率で完全にランダムなアクションを採用し、1-ε の確率で貪欲方策でアクション決定を行うことで探索力を高めようというものです。

ε-Greedy方策
(1-ε) の確率で：貪欲方策 $\displaystyle{ a = \underset{a} {\text{argmax }} Q(s, a) }$
εの確率で：ランダムなアクション $\displaystyle{ a}$ を選択

ε-Greedy法の問題は探索率εの適切な設定が難しいことです。学習の序盤では探索率εを高めにとる必要がありますし、ゲームに習熟してきたらεを低めにする必要があります*1。そこで、DQNでは最初の100万ステップで探索率εを1.0から0.1まで線形に減少させ、それ以降はε=0.1で固定するというアニーリング方式を採用しています（下図）。

epsilon_scheduler = (lambda steps: max(1.0 - 0.9 * steps / 1000000, 0.1))

f:id:horomary:20210125134709p:plain:w400 — 探索率εのアニーリング

このようにε-Greedy法では探索率εのアニーリングのスケジューリング関数がエージェントのパフォーマンスを大きく左右する重要なハイパーパラメータとなってしまうので大変扱いづらいという問題があります。この問題にアプローチした後継手法のひとつが Noisy network（[1706.10295] Noisy Networks for Exploration, ICLR2018）です。Noisy networkではε-Greedy法のようにアクション選択に直接確率的ノイズを乗せるのではなく、Q-netwrok自体がノイズを発生することによって探索を促進します。

別アプローチとして分散強化学習手法 Ape-X（ [1803.00933] Distributed Prioritized Experience Replay, ICLR2018）ではε-Greedy法を採用しながらも分散強化学習の強みを生かして並列化されたagentそれぞれに異なるεの値を割り当てるという、いい意味での力押しにより多様な探索を可能にしました。

Life losses as episode ends

Breakoutにおける１エピソードとは５つの残機をすべて失いGam eoverとなるまでです。当然、DQN論文に表記されているスコアもGame overになるまでに獲得したトータルスコアです。しかし、それでは残機を失うことが悪いことだとエージェントが学習しにくくなってしまうので、DQNでは残機が減ったら遷移情報（transition）ではエピソードが終了した扱いにするというトリックが使用されています。

最近の手法（R2D2）では、このトリックを使わないことによりatari環境の一部のゲーム(seaquest)で大幅に性能改善が見られることが報告されていますが、Breakoutについてはこのトリックを使用した方が学習の進みが良いです。

Experience Replay

強化学習はオンラインで遷移情報（経験）を収集するため、サンプル間の強烈な自己相関が発生し学習が不安定になるという問題があります。そこで、収集した経験をすぐに学習に使わずいったんバッファ(replay buffer)に蓄積し、学習時はバッファからランダムに経験を選択してミニバッチを作成する、という方法により自己相関を低減するのがExperience Replay *2 です。

Experience Replay はDQNの性能にもっとも大きく貢献している要素であることが論文のablation studyから分かります。

f:id:horomary:20210125230721p:plain:w700 — Human-level control through deep reinforcement learning | Nature より

replay bufferの実装

遷移情報（経験）を蓄積するreplay bufferの実装自体は簡単です。もっともシンプルには遷移情報のタプル (state, action, reward, next_state, done) をリストに追加していくだけでもOKですが、ミニバッチ作成機能を持たせたいのでクラスで実装します。

このreplay bufferの実装は見通しがよいのですが、わかりやすさのためにメモリ効率を犠牲にしています。もしコードのわかりやすさを気にしなければメモリ消費は8分の1くらいで実装できるはずですが、強化学習においてデバッグのしやすさは本当に重要なので見通しを悪くしたくありません。

そこで、この実装では exp = zlib.compress(pickle.dumps(exp)) において遷移情報をpickle化したうえで圧縮することによりわかりやすさを保ったままメモリ消費を抑えています。DQNではreplay bufferには100万ステップ分の遷移情報を格納しますが、圧縮処理なしでこれをやるとRAMを60GBくらい消費する一方、圧縮すると処理が少し遅くなるかわりにメモリ消費は6GBくらいで済みます。

経験再生の改良

DQNでは100万ステップ分の遷移情報が蓄積されたリプレイバッファから毎更新ごとに32の遷移情報をランダムに選択してミニバッチを作成します。これではレアで高報酬な遷移を学習する効率が悪いことは明らかです。そこで後に『優先つき経験再生』（ICLR2016, [1511.05952] Prioritized Experience Replay）という手法が提案されました。この手法では遷移情報のTD誤差の大きさ（驚きの大きさ、あるいは意外性の高さ）に応じてリプレイバッファから選択される確率を高めることで、レアイベントを効率よく学習することを可能にします。

Qネットワークの実装

DQNスタイルのQ-networkは状態sを入力としてアクション次元数のユニットを出力するようにします。ネットワーク構造自体はごく普通のCNNですが、初期のQ値が偏らないように重みの初期化スキームを適切に選択する必要があることに注意してください。 ここではhe_normalを採用しました。重みの初期化方法の選択はQ学習だけではなく方策勾配法でも同様に重要です。*3

画像認識分野では2012年のAlexNetから数年でResNetのような超大規模化が進んだのと対照的に、Qネットワーク自体の工夫や大規模化はあまり行われていません。パラメータ数が増えるとそれだけ必要なサンプル数が増えるからでしょうか？

Qネットワークの改良で明らかな成功を収めたのは、ネットワークの出力に近い部分をちょこっと変えた[1511.06581] Dueling Network Architectures for Deep Reinforcement Learning や RNNを導入したRecurrent Experience Replay in Distributed Reinforcement Learning (ICLR 2019) くらいじゃないでしょうか*4。他にはQ-networkの出力をスカラ値でなく確率分布に変更した C51（[1707.06887] A Distributional Perspective on Reinforcement Learning）もQネットワークの改良と言えるかもしれません。

ネットワークの更新

reward clipping

DQNでは報酬を-1~+1の範囲にクリッピングし、報酬のスケールを揃えることで学習を円滑化します。ただし、Breakoutについてはもともと報酬のスケールがいい感じなのでreward clippingしなくてもあまりパフォーマンスに影響しません。

ベルマンエラーの計算

Qネットワーク更新のためのベルマンエラーを計算します。シンプルにはベルマンエラーのMSE（平均二乗誤差）がQ-network更新のためのロス関数となります。が、実際にはMSEではなくhuber loss関数というものを使用します（後述）。

ベルマンエラー $\displaystyle{ = \mathcal{T}Q(s_t, a_t) - Q(s_t, a_t) }$

ここで、 $\displaystyle{ \mathcal{T}Q(s_t, a_t) = r_t + \gamma \max_{a'} Q_{target}(s_{t+1}, a') }$

教師あり学習で言えばTQが教師ラベルでQが予測値なので、推測で推測を更新するという一見奇妙なことをしています。実際これをそのままニューラルネットワークでやると学習がものすごく不安定になります。そこで、DQNでは教師ラベルとなるTQは重みを凍結した過去のQ関数（target-Q-network）で算出することで学習の不安定化を低減しています。target-networkは定期的（DQNでは1万ステップごと）にメインのQ関数と重みを同期します。この同期頻度は頻繁にしすぎると学習が不安定化し、長くとりすぎると学習が進みにくくなるので重要なハイパーパラメータの一つとなっています。

実装について、TQ(s, a)の計算では $\displaystyle{ Q(s_{t+1}, \cdot) }$ の値を最大化するようなアクションa' (next_actions)を算出して、 $\displaystyle{ Q(s_{t+1}, a') }$ を抽出する処理がありますが、tensorflowの仕様上onehot化したうえでreduce_sumをとるという少々ややこしいコードになっています。これがもしnumpyなら以下のようにすっきり書けるのですが、tensorflowではこのようなindexingはいまのところエラーになります。

n = next_qvalues.shape[0]  #: n==batch_size
max_next_qvalues = next_qvalues[np.arange(n), next_actions]

また、TQは教師ラベルなので勾配計算をしない＝tf.GradientTapeの外で定義しておく必要があることに注意しましょう。tensorflow2で使えるtf.GradientTapeは普通の教師あり学習だとあまり有難みを感じませんが強化学習だとなかなか便利な記法です。

ロスと勾配計算

ロス関数について、前述した通りMSE(TQ - Q) でも学習はできますがDQNではMSEよりも外れ値に鈍感なhuber-loss関数を使用することで極端な勾配更新を防ぎます。huber-lossはtensorflow.keras.losses.Huber()として用意されているので自力実装しなくても大丈夫です。

ja.wikipedia.org

勾配計算について、DQN論文ではRMSpropを使用していますが、ここでは学習率0.00025のAdamを使用しました。