TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

Agent57: Outperforming the Atari Human Benchmarkを読む その2

背景:Never Give Up(NGU)

NGU上に構築する2つのアイディア

  • 私たちの研究は、2つのアイデアを組み合わせたNGUエージェントの上に構築される。
  • 1つは、好奇心主導型の探索、2つ目は、分散型の深層RLエージェント、特にR2D2である。

NGUの報酬

  • NGUは、探索を促進するために固有の報酬を計算する。
  • この報酬は、エピソードごとと長期にわたる新規性を組み合わせることによって定義される。
  • エピソードごとの新規性、r_t^{\text{episodic}}は、エピソードの過程で急速に消失し、観測をエピソードメモリの内容と比較することによって計算される。
  • 長期にわたる新規性\alpha_tは、訓練全体を通じてゆっくりと消失し、パラメトリックモデルを使用して計算される(NGUおよびこの研究では、この目的のためにRandom Network Distillationが使用される)。
  • これにより、固有の報酬r_t^iは次のように定義される。

\displaystyle
\begin{equation*}
r_t^{i} = r_t^{\text{episodic}}\cdot \min \left\{\max\left\{\alpha_t, 1\right\}, L\right\}
\label{eq:clipping}
\end{equation*}

  • ここで、L = 5は、選択された最大報酬スケーリングである。
  • これにより、\alpha_tによって提供される長期的な新規性を活用するが、r_t^{\text{episodic}}は、エージェントがエピソード内を探索することを奨励し続ける。
  • r_t^{\text{episodic}}および\alpha_tの計算の詳細については、(Puigdomènech Badia et al., 2020)を参照。
  • 時間tで、NGUは、環境によって提供された外部報酬r^e_tに、同じ固有報酬\beta_j r_t^i (\beta_j\in\mathbb{R}^+, j\in 0,\dots N-1)のN個の異なるスケールを追加して、N個の潜在的な合計報酬r_{j,t} = r^e_t + \beta_j r_t^iを形成する。
  • その結果、NGUは、各報酬関数r_{j,t}に関連付けられたN個の異なる関連する最適な状態行動価値関数Q^*_{r_j}を学習することを目的としている。
  • 探索率\beta_jは、探索度を制御するパラメータである。
  • 高い値は探索的方策を奨励し、小さい値は活用的方策を奨励する。
  • さらに、長期の信用割り当てを学習する目的で、それぞれに独自の割引係数\gamma_jがある(背景とマルコフ決定プロセス(MDP)の表記については、付録Aを参照)。
  • 固有の報酬は通常、外部の報酬よりもはるかに密なので、\{(\beta_j, \gamma_j)\}_{j=0}^{N-1}は、活用的方策(\beta_jの値が小さい)には長期的視野(\gamma_jの値が高い)を、探索的方策(\beta_jの値が高い)には短期的視野(\gamma_jの値が低い)を可能にするように選択される。

状態行動価値関数の学習

  • 状態行動価値関数Q^*_{r_j}を学習するために、NGUはリカレントニューラルネットワークQ(x, a, j; \theta)を訓練する。
  • ここで、jは、Nの暗黙のMDP(特に(\beta_j, \gamma_j))の1つにインデックスを付けるonehotベクトルである。
  • xは 現在の観測、aはアクション、\thetaはネットワークのパラメータ(再帰状態を含む)である。
  • 実際には、NGUは不安定で、単純な環境であっても、ファミリ内のすべての状態行動価値関数のQ^*_{r_j}の適切な近似を学習できない場合がある。
  • これは特に、r^e_tr^i_tのスケールとスパース性が両方とも異なる場合、または1つの報酬が他の報酬よりもノイジーな場合に当てはまる。
  • 報酬の性質が非常に異なる場合、報酬の組み合わせに対する一般的な状態と行動の価値関数を学習することは難しいと推測する。
  • したがって、3.1節では、この問題に取り組むためのアーキテクチャの変更を提案する。

深層分散RLエージェント

  • 私たちのエージェントは、R2D2とNGUの系譜にある、深層分散RLエージェントである。
  • したがって、多くのアクターが中央の優先順位付けされたリプレイバッファにデータを供給することで、データ収集と学習プロセスを分離する。
  • 図2に示すように、ラーナーはこのバッファーから訓練データをサンプリングできる(実装の詳細とハイパーパラメータについては、付録Eを参照)。
  • より正確には、リプレイバッファには、FIFO方式で定期的に削除される遷移のシーケンスが含まれている。
  • これらのシーケンスは、環境の独立したコピーと相互作用するアクタープロセスから取得され、TD誤差に基づいて優先順位が付けられる。
  • 優先度はアクターによって初期化され、ラーナーによって更新された状態行動価値関数Q(x, a, j; \theta)で更新される。
  • これらの優先順位に従って、ラーナーはリプレイバッファから遷移のシーケンスをサンプリングして、RL損失を構築する。
  • 次に、RL損失を最小化して最適な状態行動価値関数を近似することにより、ニューラルネットワークQ(x, a, j; \theta)のパラメータを更新する。
  • 最後に、各アクターはラーナーと同じネットワークアーキテクチャを共有するが、重みは異なる。
  • l番目のアクターのパラメータを\theta_lとする。
  • ラーナーの重み\thetaをアクターに頻繁に送信することで、アクターは自身の重み\theta_lを更新できる。
  • 各アクターは異なる値\epsilon_lを使用する。これは、状態行動価値関数Q(x, a, j; \theta_l)の現在の推定に基づいて、\epsilon_l-greedy方策に従うために使用される。
  • 特に、各エピソードの最初と各アクターでは、NGUはペア(\beta_j, \gamma_j)を一律に選択する。
  • このプロセスは最適ではないと仮定し、データ収集プロセスを適応させる各アクターにメタコントローラを導入することにより、3.2節でこれを改善することを提案する。

f:id:TadaoYamaoka:20200401230355p:plain
図2.分散深層RLエージェントの略図

感想

Atari57はNGUR2D2を改善したアルゴリズムのようです。
NGUは探索と活用のトレードオフを制御するために、通常の報酬の他に、長期での新規性とエピソード内での探索を促す内部報酬を与えるようにしたアルゴリズムのようです。
NGUもつい最近(2020年)の論文です。
内部報酬には、探索と活用のトレードオフを制御するパラメータと、長期の信用割り当てを制御する割引係数があり、それらが異なる複数の状態行動価値関数を学習しているようです。

(続く)

Agent57: Outperforming the Atari Human Benchmarkを読む

DeepMindが発表したAgent57: Outperforming the Atari Human Benchmark論文を読んでいきます。

Atari57のすべてのゲームで人間のパフォーマンスを上回ったようです。
モンテズマリベンジのような長期的な目標を必要とするゲームは強化学習アルゴリズムが苦手としていましたが、長期的な信用割り当てをコントロールすることで克服できたようです。

概要

  • Atariゲームは、過去10年間、強化学習(RL)コミュニティで長年のベンチマークとなっている。
  • このベンチマークは、RLアルゴリズムの一般的な能力をテストするために提案された。
  • 以前の研究は、ゲームのセットの多くで非常によく機能することにより、優れた平均パフォーマンスを達成したが、最も挑戦的なゲームのいくつかでは非常に貧弱だった。
  • 57のすべてのAtariゲームで標準の人間のベンチマークよりも優れた最初の深層RLエージェントであるAgent57を提案する。
  • この結果を達成するために、非常に探索的なものから純粋に活用的なものまでの一連の方策をパラメーター化するニューラルネットワークを訓練する。
  • 訓練プロセス全体で優先するポリシーを選択するための適応メカニズムを提案します。 さらに、アーキテクチャの新しいパラメータ化を利用して、より一貫した安定した学習を可能にします。

導入

アーケード学習環境(ALE)

  • アーケード学習環境(ALE)は、幅広いゲームで一般的な能力を発揮するように設計されたエージェントを経験的に評価するためのプラットフォームとして提案された。
  • ALEは、人間のプレイヤーにとって魅力的でやりがいのあるように設計された多様なAtari 2600ゲーム環境へのインターフェースを提供する。
  • Bellemareらが述べたように、Atari 2600ゲームは、3つの主な理由でAIエージェントの一般的な能力を評価するのに非常に適している。

(i)一般性を主張するのに十分な多様性
(ii)それぞれが実際に直面する可能性のある設定を代表するのに十分興味深い
(iii)実験者の偏見のないように独立した者によってそれぞれ作成された

一般的なRLアルゴリズムの課題

  • エージェントは、ゲーム固有の情報を使用せずに、手元のドメインについて最小限の仮定をしながら、できるだけ多くのゲームでうまく機能することが期待されている。
  • Deep Q-Networksは、多数のAtari 2600ゲームで人間レベルの制御を実現する最初のアルゴリズムであり、人間の正規化スコア(HNS)で測定された。
  • その後、HNSを使用してAtariゲームのパフォーマンスを評価することは、人間のベースラインスコアが人間のパフォーマンスを潜在的に過小評価しているにもかかわらず、深層強化学習(RL)で最も広く使用されているベンチマークの1つになった。
  • それにもかかわらず、人間のベンチマークパフォーマンスは、57のアタリゲーム全体で「合理的なパフォーマンス」のオラクル(神託)のままである。
  • あらゆる努力にもかかわらず、単一のRLアルゴリズムでは、1組のハイパーパラメーターで57のすべてのAtariゲームで100%を超えるHNSを達成できなかった。
  • 実際、モデルベースのRLであるMuZero、およびモデルフリーRLにおける最新のアルゴリズムであるR2D2では、100%HNSを上回るのはそれぞれ51、52ゲームである。
  • これらのアルゴリズムは、ゲームの大部分で人間レベルの平均をはるかに超えるパフォーマンスを達成するが(たとえば、HNSが1000%を超えるなど)、達成できないゲームでは、完全に学習できないことがよくある。
  • これらのゲームは、一般的なRLアルゴリズムで対処できるはずの特に重要な問題を示している。
  • 第一は、長期的な信用割り当て:その後のポジティブな(またはネガティブな)結果に対して、どの決定が最も信用に値するか?
  • この問題は、報酬が遅れて、スキーやソラリスのゲームなど、一連の長い行動で信用を割り当てる必要がある場合に特に困難である。
  • スキーのゲームは、その独特の報酬構造により、標準的な例である。
  • ゲームの目標は、すべてのゲートをできるだけ速く下り坂で走ることである。逃したゲートごとに5秒のペナルティが与えられる。最後にのみ与えられる報酬は、経過時間に比例する。
  • したがって、ゲームの早い段階で行われた行動(ゲートを逃すなど)が獲得した報酬にマイナスの影響を与える理由を理解するには、長期的な信用割り当てが必要である。
  • 第二に、探索:RLで効果的に学習するには、効率的な探索が不可欠である。
  • Private Eye, Montezuma’s Revenge, Pitfall!またはVentureなどのゲームは、最初のポジティブな報酬が表示される前に何百もの行動が必要になる可能性があるため、困難な探索ゲームとして広く考えられている。
  • 成功するためには、エージェントはポジティブな報酬を見つけることは明らかに不可能であるにもかかわらず、環境を探索し続ける必要がある。
  • これらの問題は、関数の近似が必要な大規模な高次元状態空間で特に困難である。

NGUの改善の提案

  • 深層RLの探索アルゴリズムは、一般に3つのカテゴリに分類される。
  • ランダム化された価値関数、教師なしの方策学習、内因性動機付けである。
  • その他の研究では、手作りの特徴量、ドメイン固有の知識、または恵まれた事前トレーニングを組み合わせて、探索問題を回避し、場合によってはいくつかのAtariゲームでのみ評価される。
  • 有望な結果にもかかわらず、人間のデモンストレーションに依存することなく、残りのゲームのパフォーマンスを低下させることなく、挑戦的なゲームのパフォーマンスを大幅に改善できるアルゴリズムはない。
  • 特に、このすべての研究の中で、内因性動機付け、特にNever Give Up(NGU)は、困難な探索ゲームのパフォーマンスを向上させる上で重要な最近の明るい見通しを示している。
  • NGUは、2つのレベル(エピソード内の短期的な新規性およびエピソード全体の長期的な新規性)で新規性に敏感な内部で生成された固有の報酬で報酬信号を増強することにより、これを実現する。
  • 次に、探索と活用(同じパラメーターを共有)のための一連の方策を学習する。
  • 最終的な目標は、活用方策の下で最高のスコアを取得することである。
  • ただし、NGUは最も一般的なエージェントではない。
  • R2D2やMuZeroはほとんどすべてのゲームで強力に実行できるが、NGUはMuZeroやR2D2などのエージェントとは異なり、小さなゲームセットしか強力に機能しないという欠点がある (R2D2に基づいているにもかかわらず)。
  • たとえば、Surroundゲームでは、R2D2が最適なスコアを達成し、NGUはランダムポリシーと同程度にしか機能しない。
  • NGUの欠点の1つは、学習の進歩への貢献に関係なく、各方策に従って同じ量の経験を収集することである。
  • 一部のゲームでは、他と大きく異なる量の探索が必要である。
  • 直感的には、最終的なパフォーマンスが最大化されるように、共有リソース(ネットワーク容量とデータ収集の両方)を割り当てることができる。
  • NGUがエージェントの存続期間中に探索戦略を適応できるようにして、学習している特定のゲームに特化できるようにすることを提案する。
  • これは、NGUをより一般的なエージェントにするためにNGUに行った最初の重要な改善である。

長期的な信用割り当てに関する最近の研究

  • 長期的な信用割り当てに関する最近の研究は、大きく2つのタイプに分類できる。
  • 勾配が正しく信用を割り当てることを確認することと、価値または目標を使用して正しい信用が割り当てられるようにすることである。
  • NGUは、100%HNSに到達できないスキーやSolarisなどのような長期的な信用割り当ての問題にも対処できない。
  • モデルを通る勾配の流れが学習を指示する一方で、価値と報酬が損失を形成するため、RLでの信用割り当ての進展には、多くの場合、両方のアプローチが混在している。

提案手法

  • この研究では、全体的な訓練の安定性を改善し、割引率を動的に調整し、backprop through time windowを増やすことにより、長期的な信用割り当て問題に取り組むことを提案する。
  • これらは、以前の研究で提案されたアプローチと比較して比較的単純な変更ですが、効果的であることがわかる。
  • 最近の多くの研究で、深層RLエージェントのハイパーパラメータを動的に調整する方法、たとえば、進化、勾配、多腕バンディットに基づくアプローチなど、この問題が調査されている。
  • Schaulらに触発されて、単純な非定常多腕バンディットを使用して、探索率と割引率を直接制御し、エピソードの収益を最大化して、この情報をエージェントの価値ネットワークに入力として提供することを提案する。
  • Schaulらとは異なり、1)探査率と割引係数を制御し(長期的な信用割り当てを支援)、2)バンディットは、固定された関数形式で共通の価値関数を直線的に傾けるのではなく、探索とより長い割引の効果をバックアップする一連の状態行動価値関数を制御する。

要約

  • 要約すると、私たちの貢献は次のとおり。
  1. 内因性の報酬と外部の報酬の寄与を分解する状態行動価値関数の新しいパラメーター化。 結果として、内因性の報酬スケールの広い範囲で訓練の安定性が大幅に向上する。
  2. メタコントローラー:訓練プロセス全体で優先順位を付ける方策(探索率と割引係数でパラメーター化)を選択する適応メカニズム。 これにより、エージェントは、より多くのリソースをどちらか一方に割り当てることで、探索/活用のトレードオフを制御できる。
  3. 最後に、すべてのAtari 57ゲームで初めて人間のベースラインを超えるパフォーマンスを示す。 これらの実験の一部として、R2D2より以前に公開されたウィンドウの2倍になるようにbackprop through time windowを再調整するだけで、残りのゲームの全体的なパフォーマンスを維持または改善しながら、(Solarisなどで)優れた長期の信用割り当てにつながることもわかった。
  • NGUに対するこれらの改善により、NGUは合計で最も汎用的なAtari57エージェントに変換され、すべてのAtari 57ゲームにわたって人間のベースラインを均一に上回ることができた。
  • したがって、このエージェントをAgent57と呼ぶ。

f:id:TadaoYamaoka:20200401084325p:plain
図1. Agent57と最先端のベースラインの訓練を通して、アルゴリズムが人間のベンチマークを上回った57のアタリゲームのゲーム数。

(続く)

wxWidgetsをVisual Studio 2019でビルドする

マルチプラットフォームGUIツールキットであるwxWidgetsVisual Studio 2019でビルドする方法についてです。
ほぼ自分用のメモです。

ダウンロード

公式ページから最新のソースをダウンロードする。
ダウンロードしたソースを適当なフォルダに解凍する。

ビルド

build\msw\wx_vc16.slnをVisual Studio 2019で開く。
ビルドの構成を「DLL Debug」※「x64」にして、ソリューションのビルドを実行する。
デバッグランタイムを使用する場合

サンプルプログラムのビルド

公式のProgramming Guidesの「Hello World Example」をビルドする。

プロジェクト作成

Visual Studioの新規プロジェクト作成でWindowsデスクトップウィザードを選択し、アプリケーションの種類を「デスクトップアプリケーション (.exe)」にして、空のプロジェクトを作成する。

プロジェクトの設定
  • ビルド構成

ビルド構成を「Debug」「x64」に設定する。

プロジェクトのプロパティで、構成プロパティ→VC++ ディレクトリを選択し、
インクルードディレクトリに「..\wxWidgets\include;..\wxWidgets\lib\vc_x64_dll\mswud;」※を追加する。
wxWidgetsを作成したプロジェクトと同じ階層に、wxWidgetsというフォルダ名で解凍した場合
※別のフォルダに解凍した場合はそのフォルダを指定する
ライブラリディレクトリに「..\wxWidgets\lib\vc_x64_dll;」を追加する。

構成プロパティ→C/C++プリプロセッサを選択し、
プリプロセッサの定義に「__WXMSW__;WXUSINGDLL;」を追加する。

  • リンクライブラリ追加

構成プロパティ→リンカー→入力を選択し、
追加の依存ファイルに「wxbase31ud.lib;wxmsw31ud_core.lib;」を追加する。

ソース作成

適当な名前でソースを追加し、Hello World Exampleの内容を記述する。

ビルド

ソリューションのビルドを実行する。

実行

そのまま実行すると、wxWidgetsのDLLが見つからないためエラーになる。
環境変数PATHに「C:\src\wxWidgets\lib\vc_x64_dll」※を追加する。
※ソースを「C:\src\wxWidgets」に展開した場合

成功すればウィンドウが表示される。
f:id:TadaoYamaoka:20200314151615p:plain

リバーシ(オセロ)で深層強化学習 その7(Prioritized Experience Replay)

リバーシ(オセロ)で深層強化学習を試すシリーズ、前回からしばらく空いたが、今回はPrioritized Experience Replayを試す。

Prioritized Experience Replay

強化学習では、サンプルの時間依存の相関を弱めるために、サンプルを乱択する経験再生(experience peplay)をいうヒューリスティックが用いられる。
DQNでは、さらにリプレイメモリを用いて、過去の経験からもサンプリングすることで、過去の経験を一定期間忘れないようにする。
リプレイメモリは、基本的には方策オフ型の強化学習で使用される。

DQNでは、リプレイメモリから均一にサンプリングされるが、Prioritized Experience Replay(優先順位付き経験再生)では、重要なサンプルをより頻繁に再生し、より効率的に学習できるようにする。

優先順位

TD誤差を優先順位の尺度とする。
現在のネットワークの予測結果と、1ステップ後の\max _{a} Q\left(s^{\prime}, a\right)の差が大きいほど優先的に再生する。
すでに予測の誤差が少ない遷移については、学ぶ必要が少ないため、再生する頻度を減らす。

遷移iをサンプリングする確率は、以下の式で決定する。
\displaystyle
P(i) = \frac{p_i^{\alpha}}{\sum_k p_k^{\alpha}}
p_iは、遷移iの優先度を表し、指数\alphaは優先度がどれだけ使用されるかを決定する。
\alpha=1の場合、一様にサンプルされる。

論文では、p_iの決め方は、proportionalとrank-basedの2種類が提案されている。

1つ目のproportionalでは、以下の式で優先度を決める。
\displaystyle
p_i = |\delta_i| + \epsilon
ここで、|\delta_i|はTD誤差の絶対値、\epsilonは正の小さな定数で誤差が0の場合にまったく再生されなくなることを防ぐ。

2つ目のrank-basedでは、以下の式で優先度を決める。
\displaystyle
p_i = \frac{1}{\operatorname{rank}(i)}
ここで、rank(i)は、リプレイメモリが|\delta_i|に従ってソートされたときの遷移iのランクである。

イテレーションで、各サンプルのp_iを計算するのは、O(N)の計算が必要でリプレイメモリのサイズが大きい場合重たい処理である。
proportionalは、sum-treeを使うことで効率的に実装することができる。
sum-treeを使うことで計算量は、O(log N)になる。

sum-treeについては、以前に記事にしたので参考にしてほしい。

論文に記載されているproportionalとrank-basedのAtariのスコアを、以下に示す。どちらかが一方的に良いというわけではないようだ。
f:id:TadaoYamaoka:20200126174201p:plain

優先度の初期値

優先度に使用するTD誤差は、DQNではリプレイメモリからサンプリングしてネットワークを更新するタイミングでバッチで計算を行う。
一方、リプレイメモリに遷移を格納するタイミングは、エピソードを作成するタイミングになる。
このタイミングでTD誤差を計算するのは効率が悪い。
そこで、これまでの優先度の最大値で初期化して、サンプリングされたタイミングで実際のTD誤差に更新を行う。

重要度サンプリング

確率的勾配法は、サンプルの分布に依存した更新が行われる。
優先度の高い遷移が頻繁に再生されると分布に偏りが起きるため、バイアスがかかる。

このバイアスを修正するために、重要度サンプリングを使い、以下の式で更新を重み付けする。
\displaystyle
w_i = \left(\frac{1}{N} \cdot \frac{1}{P(i)}\right)^{\beta}
ここで、\betaはどれだけ補正を行うかを制御する。\beta=1の場合、サンプルの偏りを完全に補正する。
安定性の理由から、w_i1/\max_i w_iで正規化する。

proportionalの場合、実装上\max_i w_iを効率的に計算するために、min P(i)をmin-treeを使って探索する。

実装

効率的な実装が可能なため、優先度にはproportionalを使用して実装を行う。

前回までのDQNの実装と変更になるのは、リプレイメモリの実装のみである。

sum-treeとmin-treeの実装は、少々複雑である。
以下のPyTorchによるチュートリアルの実装を参考にさせてもらった。
GitHub - qfettes/DeepRL-Tutorials: Contains high quality implementations of Deep Reinforcement Learning algorithms written in PyTorch

ソース

creversi_gym/dqn_per.py at master · TadaoYamaoka/creversi_gym · GitHub
※リプレイメモリの実装は、class PrioritizedReplayMemoryの部分

sum-treeとmin-treeの実装(上記チュートリアルから流用)
creversi_gym/data_structures.py at master · TadaoYamaoka/creversi_gym · GitHub

結果

バニラDQNとDDQN、DDQN+Dueling Networkの3パターンをPrioritized Experience Replayありで学習した。
1万イテレーション学習した結果は以下のようになった。

損失

f:id:TadaoYamaoka:20200126181810p:plain

比較のために、Prioritized Experience Replayなしの結果も記載する。
前回の結果は今回とリプレイメモリのサイズが異なるため再測定した(Prioritized Experience Replayはsum-treeの実装上、2の累乗にする必要がある)。
f:id:TadaoYamaoka:20200127211747p:plain

損失が、重要度により重みづけされている影響で、損失がPrioritized Experience Replayありの方は、なしの場合と比べて一桁小さくなっている。
Prioritized Experience Replayありの方が、より早く安定して損失が減少し始めているように見える。

強さ

Prioritized Experience Replayありで学習したモデルのランダムに対して1000局対局した結果は以下の通り。

結果 勝率 信頼区間95%
DQN 906勝78敗16分 92.07% 90.22%-93.6%
DDQN 880勝107敗13分 89.16% 87.07%-90.95%
DDQN+Dueling 909勝72敗19分 92.66% 90.86%-94.13%

Prioritized Experience Replayなしの結果は以下の通り。

結果 勝率 信頼区間95%
DQN 867勝111敗22分 88.65% 86.51%-90.49%
DDQN 861勝116敗23分 88.13% 85.95%-90.01%
DDQN+Dueling 901勝80敗19分 91.85% 89.96%-93.4%

Prioritized Experience Replayありで強化学習することで、DQN、DDQN、Duelingすべての場合で勝率が上がっている。
DDQN+DuelingをPrioritized Experience Replayあり学習した場合が、一番勝率が高くなった(しかし、統計量zは-0.67558>-1.96 のため有意差があるとは言えない)。

Prioritized Experience Replayありなしによらず、DDQNよりDQNの方が勝率が高いのは、以前の結果と同じである。

まとめ

Prioritized Experience Replayありで学習することで、勝率が高くなることが確認できた。
Duelingと組み合わせた場合が、一番勝率が高くなる。


次は、Distributional DQNを試したいが、次の技術書典向けの本を書くのでしばらくお休みします。
技術書典のネタは、このリバーシ(オセロ)で深層強化学習を試した内容を丁寧に解説したものにしようと思っています。

将棋AIの進捗 その39(リーグ戦)

年末にCPUを3970Xに変えてから、USIエンジンをリーグに加えた強化学習を行っている。
USIエンジンを各探索スレッドにつき2つ、GPUにつき探索スレッドを3つ、3GPUで探索を行っているので、合計18プロセス起動している。
メモリの制約が厳しくこれ以上は起動できなかった。

リーグの構成は、1/8はUSIエンジンと対局して、残りは自己対局を行っている。
1手500msだと局面生成速度は、リーグなしと比べて7割くらいになる。
USIエンジンには、elmo(WCSC28)を使用した。

タスクマネージャの様子
f:id:TadaoYamaoka:20200119000643p:plain
GPU使用率にCUDAの使用率は反映されていない。

リーグ戦の効果測定

リーグ戦を開始してから、途中でdropoutを削除する変更と、未探索ノードの初期値の変更を行ったため、リーグ戦のみの効果は測定できていないが、リーグ戦導入後の損失、floodgateの棋譜に対する正解率、USIエンジンに対する勝率は以下のようになった。

訓練損失

f:id:TadaoYamaoka:20200119001457p:plain

テスト損失

f:id:TadaoYamaoka:20200119001510p:plain

テスト正解率

f:id:TadaoYamaoka:20200119001533p:plain

USIエンジンに対する勝率

f:id:TadaoYamaoka:20200119001948p:plain

考察

リーグ戦を開始したモデルは、既に200サイクル学習したモデルで、テスト損失はほぼ横ばいになっていた。
リーグ戦で学習するとテスト損失は上昇傾向がある。
210epochで急に上昇しているのは、dropoutを削除したためである。
それ以外の区間ではやや上昇している。

方策の正解率は、0.3%程上昇している。
価値の正解率は、ほぼ横ばいである。

テスト損失が上がって、正解率が上がるという結果からは良くなっているのか悪くなっているのか判断がつかない。

USIエンジンとの勝率は、218epochで未探索ノードの初期化方法を変えたことで大幅に上昇した。
それ以外の区間でも少しずつ上昇している。

技巧2との対局

技巧2と1手3秒で100対局した結果は以下の通りである。

結果 勝率 信頼区間
76勝20敗4分 79% 70.0%-86.09%

未探索ノードの初期化方法を修正した同じ対局プログラムして、213epoch時点のモデルを使用すると、

結果 勝率 信頼区間
67勝27敗6分 71% 61.4~79.4%

だったので、強くなっていそうである。

Apery(WCSC28)との対局

技巧2に8割近く勝てるようになったので、Apery(WCSC28)とも対局させてみた。

結果 勝率 信頼区間
55勝41敗4分 57% 47.3%-66.72%

※CPUはCore i7 4コア、GPUは2080Ti 1枚

Apery(4コア(8スレッド))と互角の強さになっていた。
f:id:TadaoYamaoka:20200119091724p:plain

まとめ

USIエンジンをリーグに加えて強化学習を行った効果かは追加で検証しないとわからないが、他の変更の効果も合わせて、Apery(WCSC28)と互角レベルの強さにすることができた。
MCTSは終盤が弱いという課題も克服できつつあると思う。

2019/1/19 追記

やねうら王のEvalShareオプションをtrueにすると、メモリ使用量を減らせることに気付いた。
設定すると、コミット済みが119GBだったが、84GBまで減った。
メモリに余裕ができたので、USIのプロセスを探索スレッドあたり3に増やした。
局面生成速度は、数%速くなった。

将棋AIの進捗 その38(SWA)

dlshogiの学習にSWA(Stochastic Weight Averaging)を実装して、測定した。

SWA

SWA(Stochastic Weight Averaging)は、一定間隔での重みを平均化することで、ニューラルネットワークのテスト精度を改善するテクニックである。
一般的なアンサンブルの手法では予測の結果を平均化するが、SWAでは重みを平均化することで実現する。

SWAの実装

SWAの実装は、PyTorchの実装を参考にした。
この実装では、学習開始時点からの平均を計算するようになっているが、強化学習に適用する場合は、古いステップの重みは忘れていった方が良い。
そこで、平均の代わりに、指数移動平均を使用するように変更した。
DeepLearningShogi/swa.py at master · TadaoYamaoka/DeepLearningShogi · GitHub

Leela Chess Zeroや、KataGoでも、指数移動平均を使用している。

重みを平均化する間隔はKataGoの設定を参考にして250バッチ(バッチサイズ1024)間隔、区間は適当に10とした。

効果測定

dlshogiの強化学習で生成した12サイクル分(1サイクル250万局面、1回の学習で過去10サイクル分を使用)のデータを学習して、188サイクル学習したモデルから追加で学習して効果を測定した。
SWAとdropoutは、どちらもアンサンブルの効果を狙ったもので、目的が重複しているためdropoutなしの場合も比較した。
テストデータには、floodgateの棋譜を使用した。

グラフ凡例
SWA ドロップアウト
master なし あり
nodropout なし あり
swa あり なし
swadropout あり あり
方策のテスト損失

f:id:TadaoYamaoka:20200118134510p:plain

価値のテスト損失

f:id:TadaoYamaoka:20200118134555p:plain

Q値(評価値)のテスト損失

f:id:TadaoYamaoka:20200118134624p:plain

テスト損失の合計

f:id:TadaoYamaoka:20200118135607p:plain

方策の正解率

f:id:TadaoYamaoka:20200118134640p:plain

価値の正解率

f:id:TadaoYamaoka:20200118134658p:plain

考察

方策のテスト損失を見ると、ドロップアウトありなしで、損失の値に開きがあるがこれは、学習時にドロップアウトにより素子が無効化されている影響である。
ドロップアウトの有無の条件が同じもの同士では、SWAを使った方が値が安定しており、最終的にわずかに損失が小さくなっている。

価値のテスト損失も同じ傾向である。
Q値のテスト損失は、ドロップアウトなしの場合SWAなしが最終的な損失が小さくなっているが、損失の合計ではSWAありの方が良い。


方策の正解率は、ドロップアウトなしの方が良く、ドロップアウトの有無が同じ条件では、SWAありの方が良い。
価値の正解率は、ドロップアウトなしの方が良く、ドロップアウトなしの場合SWAなしの方が最終的にわずかに高くなっているが各サイクルで逆転が起きている。


全体的に、SWAがある方が学習が安定して、テスト精度はわずかに高くなることが分かった。
また、ドロップアウトがない方が、テスト正解率が高くなる。

学習時間

SWAを使用した場合の学習時間を比較した。
各サイクルの学習時間平均は以下の通りとなった。

master 2:18
nodropout 2:19
swa 3:02
swadropout 3:03

SWAを使用すると学習時間が、1.3倍になる。
SWAは、学習終了時に重みを平均化したモデルでBatchNormalizationの統計を計算しなおす必要があるため、訓練データを使って順伝播を計算し直す必要がある。
そのため、学習時間が長くなっている。

まとめ

SWAを使用することで、floodgateの棋譜に対するテスト精度が少しだけ上がることが確認できた。
学習時間が長くなるが、学習中も強化学習で局面を生成しているので、それほど問題にはならないのでSWAを採用することにする。

将棋AIの進捗 その37(FPU reduction)

昨日MCTSで未訪問のノードの価値を、動的に親ノードの価値で初期化する方法を試した。
その結果、技巧2(4コア)に対する勝率が、60%から69%(R+68.6)になった。

昨日の結果の考察

今までは0.5(引き分け)で初期化していたため、劣勢の局面で未探索のノードがすべて1回は探索されることになるので、終盤の合法手の多い局面では探索が広すぎる条件になっていた。
十分な数の探索が行われれば問題ないが、探索の深いノードでは十分な数の探索が行われないので、すべてのノードが探索対象となると、ひどい手がバックアップされることになる。
そう考えると、0.5(引き分け)で初期化するのは明らかに良くないと思われる。

0.5(引き分け)にしていたのは、AlphaGoの論文にQ(s,a)=0で初期化するという記述があり、AlphaGoは価値ネットワークの出力を-1(負け)、1(勝ち)としていたためである。
その後、AlphaZeroの中の人の投稿で、探索時は0を負けとしていることが明らかになった。
この時点で、0で初期化することを試したが、dlshogiではかえって弱くなったので、0.5のままとしたという経緯がある。

FPU reduction

Leela ZeroのPRで、FPUを訪問済みのノードの方策の確率に応じて低減することが提案され、有意に差があることが確認されている。
modify fpu reduction depending on visited policy by Eddh · Pull Request #827 · leela-zero/leela-zero · GitHub
※FPU(First Play Urgency)は、未訪問のノードを探索する緊急度を表す用語で、未訪問のノードの初期値のこと

これをdlshogiでも試してみた。

下記式の低減係数C_{FPU}は、ルートで0、中間ノードで0.2とした。
\displaystyle
V(s) - C_{FPU} \sqrt{ \sum_{a'}{ I(N(a')>0) P(a') } }

技巧2との対局結果

技巧2(4コア)と1手3秒で100対局した結果は以下の通り。

条件 結果 勝率 信頼区間
FPU reductionなし 65勝28敗7分 69% 59.9~78.3%
FPU reductionあり 67勝27敗6分 71% 61.4~79.4%

100対局では、有意差は測定できなかった。
対局数を増やして確認してみたい。

FPU低減の係数はチューニングパラメータなので、チューニングでさらに良くなる可能性がある。
また、未訪問のノードの初期値を変えたことで、PUCTの係数も再チューニングを行う予定である。

自己対局のプログラムでも0.5は良くないので、変更する予定である。