2019-11-30

リバーシ(オセロ)で深層強化学習

先日作成した高速なリバーシライブラリを使って、深層強化学習のアルゴリズムをいろいろ試してみたいと思っている。

DQNの実装

将棋でDQNによる強化学習を試したときはまったく学習しなかったので、まずは教師ありでDQNのネットワークが学習できるか試すことにした。
DQNのネットワークは、状態(局面)が入力となり、行動(着手)ごとに行動価値を出力する。
AlphaGoのバリューネットワークのような状態価値ではなく、行動ごとの行動価値を出力するため、価値の学習の方法がAlphaGoとは少し異なる。
f:id:TadaoYamaoka:20191130150316p:plain

エピソードには、状態で取りうるどれか一つの行動しか記録されていないため、損失を計算する行動価値はどれか一つになる。
Pytorchのチュートリアルでは、gatherを使って出力をどれか一つのノードにして損失を計算している。これと同じ方法で実装することにする。

リバーシの場合、行動価値は盤の座標対応する64ノードに対応させる（中央の4マスは実際には着手できないが64とした方が処理の都合がよい）。

入力は、黒と白に対応する2値画像2枚で表す。

ネットワーク構成

3×3フィルタ128の5層のCNNとした。
AlphaGoと同様にパディングを行い、各層で画像サイズが変わらないようにする。
出力層はAlphaGoの方策ネットワークと同様に1×1の畳み込みに位置ごとに異なるバイアスとした。
（ソースはこちら）

教師あり学習

DQNは強化学習でエピソードを作成するが、ここでは強化学習を行わず棋譜データをエピソードとして学習できるか確認を行った。
DQNではQ学習を使用するが、ここではQ学習は行わず、エピソードの終端の報酬を使用して学習を行う。

リバーシの棋譜

GGSから大量の棋譜がダウンロードできる。
棋譜を処理するため、creversiにGGSの棋譜を読み込む機能を実装した。

GGSからダウンロードした棋譜をレーティング2000以上、手数45以上でフィルタリングして、9,831,855局面の学習データを作成した。
（処理に使用したコードはこちら）

学習結果

学習データをすべてリプレイバッファに格納し、ミニバッチ256をランダムにサンプリングして、10万イテレーションの学習を行った。
サンプリング時に1/2の確率で局面を180度回転する処理も行っている。
f:id:TadaoYamaoka:20191130154808p:plain

20,000イテレーション(グラフのx軸200)あたりからlossが横ばいで、学習しているように見えない。
しかし、将棋AIでも価値の学習は、lossが横ばいになる傾向があるので、学習できているかもしれない。

ランダムプレイヤーと対局

lossだけでは学習できているか分からないので、ランダムプレイヤーと対局させてみた。
ランダムプレイヤーは、合法手から一様ランダムに手を選択して、着手する。

学習したモデルを使用するプレイヤーは、局面から行動価値を予測し、最大の行動価値の行動を選択する（グリーディー戦略）。
モデルの出力には、盤の座標に対応する64のノードがあるため、合法手に絞る必要がある。
そのため、gatherを使用して、合法手に対応するインデックスのみ出力するようにした。

ランダムプレイヤーと1000局対局した結果、680勝280敗40分となった。
信頼区間95%の勝率は73.6%～67.9%で、有意にランダムプレイヤーに勝ち越している。

ランダムに対する勝率としては低いように思うが、リバーシでもDQNのネットワークが学習できることが確かめられた。
これで、DQNを強化学習した場合にネットワーク構成が原因で学習できないということはないだろう。

なお、ソフトマックス戦略にした場合、温度0.1でも532勝424敗44分となり、勝率がかなり落ちた。

学習時間

10万イテレーションの学習には、GeForce2080Tiを使用して12時間かかった。

ネットワークサイズを変えて実験

リバーシでは、着手による駒の反転は盤の端から端まで影響するので、直感的には層数が多い方がよさそうなので、層数を10層、フィルタを192にして、1万イテレーション学習してみた。
（ソースはこちら）

ランダムプレイヤーとの1000局対局した結果、766勝196敗38分となった。
少ないイテレーションで、5層CNNよりも良い結果になった。
リバーシを学習するには、ある程度のネットワークサイズが必要そうだ。

次は、教師ありでTD学習(Q学習)を試してみたい。

続き

リバーシ(オセロ)で深層強化学習その２（教師ありQ学習） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その３（DQN） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その４（並列実行） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その５（DDQN） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その６（Dueling Network） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その７（Prioritized Experience Replay） - TadaoYamaokaの開発日記

2019-11-30

AlphaStarの論文を読むその１２（評価）

AlphaStar 強化学習

評価

AlphaStar Battle.netの評価

AlphaStarエージェントは、StarCraft IIバランスパッチ4.9.3で、MMRレーティングに基づくBlizzardのオンラインマッチメイキングシステムBattle.netで人間に対して評価された。
AlphaStar Finalは、グランドマスターレベル（過去数か月でヨーロッパのサーバ（約90,000人のプレイヤー）のリーグで十分アクティブだった人間プレイヤーの99.8％を超える）と格付けされた。

対戦相手、匿名アカウント、ハードウェア、評価時点

AlphaStarは、実験への参加を選択した対戦相手（大半のプレイヤーが参加した）*1のみと対戦し、匿名のアカウント名を使用し、サイバーフォレスト、カイロスジャンクション、キングスコーブ、ニューリピュニャンの4つのマップで対戦した。
また、人間は少なくとも4つのマップを選択し、匿名のアカウント名で頻繁にプレイする必要がある。
各エージェントは、単一のハイエンドコンシューマGPUで実行された。
訓練中に、教師あり、中間点、最終の3つのポイントで評価した。

教師ありおよび中間点の評価の開始ランク

教師ありおよび中間点の評価のために、各エージェントは新しいランク付けされていないアカウントで開始した。

MMR

それらのMMRは、人間と同様にBattle.netで更新された。
教師ありおよび中間点の評価では、それぞれ30ゲームと60ゲームをプレイした。
まだ増加していたが、50ゲーム後に匿名性の制約が損なわれたため、中間点の評価は中止された。

複数のアカウントでのMMRの推定

Battle.netの最終評価では、複数のアカウントを使用してゲームを並列化し、識別を回避した。
私たちのアカウントのMMRは、結合して推定された中間点MMRの分布からランダムにシードされた。
その結果、Battle.netで提供される反復MMR推定を使用しなくなった。代わりにブリザードが提供する基本的な確率モデルを使用した：不確実性uの評価rと不確実性 $u_i \in[0.1,1.0$ ]の対戦相手の評価 $r_i$ が与えられたとき、結果 $o_i \in[-1,1$ の確率は、

$\displaystyle \mathbb{P}[o_{i}=1 | r, u, r_{i}, u_{i}] \\ =1-\mathbb{P}[o_{i}=-1 | r, u, r_{i}, u_{i}]=\Phi\left(\frac{r-r_{i}}{400 \sqrt{2+u^{2}+u_{i}^{2}}}\right) \approx \Phi\left(\frac{r-r_{i}}{568}\right)$

ここで、 $\Phi$ は標準のガウス分布のCDFであり、Battle.netの最小不確実性を使用した場所 $u = u_i = 0.1$ である。
対戦結果のi.i.d.およびMMRの均一な事前分布の仮定で、評価を

$\displaystyle \operatorname{argmax}_{\mathrm{r} \in \mathbb{N}} \mathbb{P}[\mathrm{r} | \text { results }] \\ =\operatorname{argmax}_{\mathrm{r} \in \mathbb{N}} \mathbb{P}[\mathrm{results} | \mathrm{r}] \mathrm{U}(\mathrm{r})=\operatorname{argmax}_{\mathrm{r} \in \mathbb{N}} \prod_{i=1}^{N} \mathbb{P}[\mathrm{o}_{\mathrm{i}} | \mathrm{r}, \mathrm{r}_{\mathrm{i}}]$

として計算できる。

MMR推定値

Battle.netが報告した平均MMRは6336でしたが、プロのStarCraft IIプレイヤーであるDario “TLO” Wünschの最新の200試合でMMR計算を検証したところ、MMR推定値は6334でした。

StarCraftデモンストレーションでの評価

2018年12月、私たちはStarCraft IIプロプレイヤーGrzegorz “MaNa” KominczとDario “TLO” Wünschに対して5つのゲームシリーズを2回プレイしましたが、TLOは彼がプロとしてプレイするのと同じStarCraft II種族でプレイしなかった。
これらのゲームは、AlphaStarの別の予備バージョンで行われた*2。
特に、エージェントはカメラが制限されておらず、また行動の頻度が制限されておらず、1つのマップに1つのStarCraft II種族で対戦していた。
AlphaStarは両方の5ゲームシリーズで10ゲームすべてに勝利したが、初期のカメラプロトタイプはMaNaに対するフォローアップゲームを失った。

感想

最終的な結果は、グランドマスターレベル(人間の上位99.8%)に達しています。

人間と同じ条件で強さを測定するための測定条件の詳細が述べられています。
人間にはAlphaStarだとわからないように匿名アカウントでプレイされています。
中間点の評価では途中で特定されてしまったようです。

人間との対戦では、ハイエンドコンシューマGPU1枚で実行されています。
探索を行っていないので、それほどGPU性能は必要なさそうです。

(続く)

*1:DeepMind Research on Ladder — StarCraft II — Blizzard News

*2:AlphaStar: Mastering the real-time strategy game StarCraft II | DeepMind

2019-11-30

AlphaStarの論文を読むその１１（インフラ）

AlphaStar 強化学習

インフラ

リーグを訓練するために、多数のStarCraft II対戦を並行して実行し、それらのゲームのデータに基づいてエージェントのパラメータを更新する。
これを管理するために、さまざまなタイプの分散ワーカーで非常にスケーラブルな訓練セットアップを開発した。

ハードウェア

リーグのすべてのトレーニングエージェントに対して、16,000のStarCraft IIの並列対戦と16のアクタータスク（それぞれ8つのTPUコア*1を備えたTPU v3デバイスを使用）を実行して、推論を実行する。
ゲームインスタンスはプリエンプティブCPU（それぞれ28の物理コアを備えた150のプロセッサとほぼ同等）上で非同期に進行するが、エージェントステップの要求はTPUを効率的に使用するために動的にバッチにまとめられる。
バッチ推論にTPUを使用すると、以前の研究*2 *3よりも大幅に効率が向上する。

訓練パイプライン

アクターは、ネットワークを介して中央の128コアTPUラーナーワーカーに観測、アクション、および報酬のシーケンスを送信し、トレーニングエージェントのパラメーターを更新する。
受信したデータはメモリにバッファリングされ、2回再生される。
ラーナーワーカーは、大きなバッチで同期更新を実行する。
各TPUコアは、4つのシーケンスのミニバッチを処理し、合計バッチサイズは512である。
ラーナーは、毎秒約50,000エージェントステップを処理する。
アクターは、ラーナーからのパラメーターのコピーを10秒ごとに更新する。

コーディネーター

このアクターとラーナーのセットアップの12の個別のコピーをインスタンス化する：各StarCraft種族に対して、1つのメインエージェント、1つのメインエクスプロイト、2つのリーグエクスプロイトエージェント
ある中央コーディネーターは、利得行列(payoff matrix)の推定値を維持し、要求に応じて新しい対戦をサンプリングし、メインおよびリーグのエクスプロイトをリセットする。
追加の評価ワーカー（CPUで実行）を使用して、利得(payoff)の見積もりを補完する。
訓練セットアップの概要については、拡張データの図6を参照。

拡張データ図6|トレーニングインフラストラクチャ|リーグ全体のトレーニング設定

f:id:TadaoYamaoka:20191125083339p:plain

感想

アクターは並列実行を行い、軌跡をラーナーに送信して、ラーナーは同期でパラメータの更新を行うという仕組みになっています。
A2Cの並列処理に近い構成だと思います。

アクターの推論は、1つのサーバ内の並列実行している対戦のステップをまとめてバッチで処理を行っています。
私が作成しているdlshogiの自己対局でも似たような処理を行っています。

リプレイバッファを使用していますが、再生回数は2回と少なめです。
50万ステップ分ごとにパラメータの更新を行っており、AlphaZeroに比べるとパラメータの更新頻度は高いようです。

(続く)

*1:[1704.04760] In-Datacenter Performance Analysis of a Tensor Processing Unit

*2:[1802.01561] IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures

*3:[1807.01281] Human-level performance in first-person multiplayer games with population-based deep reinforcement learning

2019-11-30

AlphaStarの論文を読むその１０（リーグ構成）

AlphaStar 強化学習

リーグ構成(Populating the League)

訓練中、新しいプレイヤーを作成するためにスナップショットが作成されたときの訓練対象の対戦相手の分布と、教師ありパラメーターにリセットされる確率のみが異なる3つのエージェントタイプを使用した。

メインエージェント

メインエージェントは、35％SP、50％PFSPの割合でリーグの過去のすべてのプレイヤーに対して訓練され、さらに15％のPFSPマッチは、エージェントがもはやメインエクスプロイトを打ち負かすことができなくなったメインプレイヤー(forgotten players)と対戦する。
forgotten playersや強力なエクスプロイターが存在しない場合、代わりに15％がセルフプレイに使用される。
$2 \cdot 10^9$ ステップごとに、エージェントのコピーが新しいプレイヤーとしてリーグに追加される。
メインエージェントはリセットされない。

リーグエクスプロイター

リーグエクスプロイターはPFSPを使用して訓練され、凍結されたコピーは、ゲームの70％以上で、または $2 \cdot 10^9$ ステップのタイムアウト後に、リーグ内のすべてのプレイヤーを倒したときにリーグに追加される。
この時点で、エージェントが教師ありパラメーターにリセットされる確率は25％である。
直観的には、リーグエクスプロイトがリーグ内のグローバルな盲点を識別しているということである（リーグ内のプレイヤーは誰も負けることはできないが、それ自体は必ずしも堅牢ではない）。

メインエクスプロイター

メインエクスプロイターはメインエージェントと対戦する。
半分の時間で、現在の勝率が20％未満の場合、エクスプロイターは、メインエージェントによって作成されたプレイヤーに対して $𝑓_{\text {var }}$ の重み付けでPFSPを使用する。
これは、学習を促進するカリキュラムを形成する。
それ以外の場合、十分な学習シグナルがあり、現在のメインエージェントと対戦する。
このエージェントは、ゲームの70％以上で3つのメインエージェントが全員敗北したとき、または $4 \cdot 10^9$ ステップのタイムアウト後にリーグに追加される。
その後、教師ありパラメーターにリセットされる。
メインエクスプロイターはメインエージェントの弱点を特定し、その結果、それらをより強固にする。

詳細については、補足資料の擬似コードを参照。

感想

3種類のエージェントが存在し、それぞれに役割が設定されています。

メインエージェントはあらゆる弱点に対処できるエージェントで、エクスプロイターは弱点を突くことに特化したエージェントです。
エクスプロイターには2種類あり、リーグ全体の弱点を見つけるリーグエクスプロイターと、メインエージェントの弱点を見つけるメインエクスプロイターです。

それぞれ条件に達するとスナップショットが作成されて、リーグに追加されていきます。
エクスプロイターは、その際パラメータが初期化される場合があります。
そうすることで、特定の戦略を見つけたエージェントがその戦略を忘れずに残り続け、また新たな戦略を見つけられるエージェントが継続して生まれることになるので、メインエージェントがより堅牢になるという仕組みのようです。

リーグのエージェントが増え続けることになりますが、優先順位付きFictitious Self-Playを使用しているので、無駄な対戦相手が選ばれないようになっています。

(続く)

2019-11-28

AlphaStarの論文を読むその９（マルチエージェント学習）

AlphaStar 強化学習

マルチエージェント学習

リーグトレーニングはマルチエージェント強化学習アルゴリズムであり、セルフプレイトレーニング中によく発生するサイクルに対処し、多様な戦略を統合するために設計されている。
訓練中に、エージェント（RLアルゴリズムによって訓練されている）からのパラメータを新しいプレイヤー（固定された固定パラメーターを持つ）として定期的に保存することにより、リーグにデータを取り込む。
また、リーグ内のすべてのプレイヤーに対するパフォーマンスに関する最新情報をエージェントに提供するために、内部利得(payoff)の推定値を継続的に再評価する（拡張データ図6のEvaluatorsを参照）。

拡張データ図6|トレーニングインフラストラクチャ|リーグ全体のトレーニング設定

f:id:TadaoYamaoka:20191125083339p:plain

優先順位付きFictitious Self-Play

セルフプレイ（SP）アルゴリズムは、3つのすべての種族で最新のエージェント間でゲームをプレイする。
このアプローチは、戦略空間でサイクルを追跡する可能性があり、単独ではうまく機能しない（図3D）。

f:id:TadaoYamaoka:20191125084818p:plain

Fictitious Self-Play（FSP）は、リーグ内の以前のすべてのプレイヤーと対戦することでサイクルを回避する。
ただし、多くのゲームは、ほぼ100％のゲームで敗北したプレイヤーに対して無駄になる。
そのため、優先順位付きFictitious Self-Play（PFSP）を導入する。
リーグで均一に対戦相手をサンプリングする代わりに、マッチメイキングメカニズムを使用して、良い学習の信号を提供する。
学習エージェント𝐴が与えられた場合、以下の確率で候補セット𝒞から凍結した相手𝐵をサンプリングする。

$\displaystyle \frac{f(\mathbb{P}[A \text { beats } B])}{\sum_{C \in \mathcal{C}} f(\mathbb{P}[A \text { beats } C])}$

ここで、𝑓: [0,1] → [0, ∞)は重み関数である。

対戦相手の強さの制御

$f_{\text {hard }}(x)=(1-x)^{p}$ で選択すると、PFSPは最も難しいプレイヤーに焦点を合わせる。ここで、 $p \in \mathbb{R}_{+}$ は、結果の分布のエントロピーを制御する。
$f_{\text {hard }}(1)=0$ であるため、エージェントが既に負かした対戦相手とのゲームは行われない。
最も難しいプレイヤーに焦点を当てることにより、エージェントは平均パフォーマンスを最大化するのではなく、リーグの全員を倒す必要がある。これは、平均勝率の追求が悪用されやすい方策につながる可能性があるStarCraftのような非常に非推移的なゲームではより重要です。
このスキームは、PFSPのデフォルトの重み付けとして使用される。
その結果、理論的には、FSPが課すmax-avgとは対照的に、 $f_{\text {hard }}$ はmax-min最適化の滑らかな近似の形式として見ることができる。
特に、これはエクスプロイトからの情報を統合するのに役立つ。それらは強力ではあるが頻度の少ないカウンター戦略であり、均一な混合ではそれらを無視することができるためである（拡張データ図5）。

拡張データ図5 | 図3 CおよびDのマルチエージェントアブレーションのより詳細な分析

f:id:TadaoYamaoka:20191127084422p:plain

PFSPベースの訓練は、考慮されたすべての測定値でFSPよりも優れている。相対的な人口パフォーマンスで測定される人口がより強く、悪用されにくいソリューションを提供し、対応するリーグに対してより良い最終エージェントパフォーマンスを持つ。

対戦相手選択の代替ソリューション

最も難しい相手と対戦するだけでは、はるかに強い相手とのゲームを無駄にする可能性があるため、PFSPは代替のカリキュラム、 $f_{\text {var }}(x)=x(1-x)$ も使用する。
このカリキュラムは、メインエクスプロイトと低迷しているメインエージェントに使用する。

感想

サイクル（じゃんけんのような関係）を追跡する問題に対処するため、AlphaStarではFictitious Self-Playというアルゴリズムでマルチエージェント学習が行われています。
Fictitious Self-Playは、以前のプレイヤーと対戦することでサイクルを回避できますが、無駄な対戦が多くなるとという問題があるようです。
そこで、対戦相手の選択に優先順位を付けて、勝率が低い相手を優先的に選択し、すでに100%勝つ相手とは対戦しないように制御しています。
平均勝率を最大化を目標にすると、特定の相手に対してだけ有効な戦略で勝率を稼ぐといった戦略を覚えてしまい弱点が残ったままになるため、最も苦手な相手に焦点を当てててリーグ全体に勝つことを目標にしています。
ただし、リーグ内で低迷しているエージェントは、最も強い相手とばかり対戦して負けてばかりでは成長しなくなるため、そのようなエージェントとメインエクスプロイトエージェントには中間の相手を選択する方法も取られています。

(続く)

2019-11-24

MuZeroの論文を読むその２（MuZeroアルゴリズム）

MuZero 強化学習

続きです。

MuZeroアルゴリズム

MuZeroアルゴリズムについて詳しく説明する。
予測は、各タイムステップtで、 $k=1 \ldots K$ ステップのそれぞれについて、過去の観測 $O_{1}, \ldots, O_{t}$ および将来の行動 $a_{t+1}, \dots, a_{t+k}$ を条件とするパラメーター $\theta$ を使用したモデル $\mu \theta$ によって行われる。
モデルは、3つの将来の量を予測する：

方策 $\mathbf{p}_{t}^{k} \approx \pi\left(a_{t+k+1} | o_{1}, \ldots, o_{t}, a_{t+1}, \ldots, a_{t+k}\right)$
価値関数 $v_{t}^{k} \approx \mathbb{E}[u_{t+k+1}+\gamma u_{t+k+2}+\ldots | o_{1}, \ldots, o_{t}, a_{t+1}, \ldots, a_{t+k}]$
即時報酬 $r_{t}^{k} \approx u_{t+k}$

ここで、 $u$ は真の観測報酬、 $\pi$ は実際の行動の選択に使用される方策、 $\gamma$ は環境の割引関数である。

モデルの目的

内部的には、各タイムステップtで、モデルは表現関数、ダイナミクス関数、および予測関数の組み合わせによって表される。
ダイナミクス関数 $r^{k}, s^{k}=g_{\theta}\left(s^{k-1}, a^{k}\right)$ は、各仮想ステップkで即時報酬 $r_k$ および内部状態 $s_k$ を計算する再帰プロセスである。
これは、特定の状態と行動に対して予想される報酬と状態遷移を計算するMDPモデルの構造を反映している*1。
ただし、モデルベースRLへの従来のアプローチとは異なり、この内部状態 $s_k$ には環境状態のセマンティクスが関連付けられていない。
これは単にモデル全体の隠れ状態であり、その唯一の目的は関連する将来の量（方策、価値、および報酬）を正確に予測することである。
この論文では、ダイナミクス関数は決定論的に表される。確率的遷移への拡張は将来の作業のために残されている。
方策と価値の関数は、AlphaZeroの方策と価値の結合ネットワークと同様に、予測関数 $\mathbf{p}^{k}, v^{k}=f_{\theta}\left(s^{k}\right)$ によって内部状態 $s_k$ から計算される。
「ルート」状態 $s^0$ は、過去の観測値 $s^{0}=h_{\theta}\left(o_{1}, \dots, o_{t}\right)$ をエンコードする表現関数を使用して初期化される。
繰り返すが、これには将来の予測の支援を超える特別なセマンティクスはない。

モデルを使用したプランニング

このようなモデルが与えられると、過去の観測 $o_{1}, \dots, o_{t}$ が与えられた場合に、仮想の将来の軌跡 $a^{1}, \ldots, a^{k}$ を探索できる。
たとえば、単純な探索では、価値関数を最大化するkステップ行動シーケンスを単純に選択できる。
より一般的には、ダイナミクス関数によって引き起こされる内部報酬と状態空間に、MDPプランニングアルゴリズムを適用できる。
具体的には、私たちはAlphaZeroの探索に似たMCTS アルゴリズムを使用する。これは、単一エージェントドメインと中間報酬を許可するように一般化されている（Methodsを参照）。
各内部ノードで、現在のモデルパラメーター $\theta$ によって生成された方策、価値、および報酬の推定値を利用する。
MCTS アルゴリズムは、推奨方策 $\pi_t$ および推定価値 $v_t$ を出力する。
それから、行動 $a_{t+1} \sim \pi_{t}$ が選択される。

モデルの訓練

モデルのすべてのパラメータは、各仮想ステップkの方策、価値、および報酬を、kの実際のタイムステップが経過した後に観測された対応するターゲット値に正確に一致するように一緒に訓練される。
AlphaZeroと同様に、改善された方策ターゲットはMCTS探索によって生成される。
最初の目標は、予測方策 $\mathbf{p}_{t}^{k}$ と探索方策 $\pi_{t+k}$ の間の誤差を最小化することである。
また、AlphaZeroと同様に、ゲームまたはMDPをプレイすることにより、改善された価値目標が生成される。
ただし、AlphaZeroとは異なり、探索価値 $z_{t}=u_{t+1}+\gamma u_{t+2}+\ldots+\gamma^{n-1} u_{t+n}+\gamma^{n} \nu_{t+n}$ から未来へのnステップをブートストラップすることにより、割引と中間報酬を伴う長いエピソードを許可する。
ボードゲームの最終結果{負け，引き分け，勝ち}は、エピソードの最終ステップで発生する $u_{t} \in\{-1,0,+1\}$ の報酬として扱われる。
具体的には、2番目の目標は、予測価値 $v_{t}^{k}$ と目標価値 $z_{t+k}$ の間の誤差を最小化することである。
報酬目標は、単に観測された報酬である。
したがって、3番目の目標は、予測された報酬 $r_{t}^{k}$ と観測された報酬 $u_{t+k}$ の間の誤差を最小化することである。
最後に、L2正則化項も追加され、全体的な損失になる。

$\displaystyle l_{t}(\theta)=\sum_{k=0}^{K} l^{r}\left(u_{t+k}, r_{t}^{k}\right)+l^{v}\left(z_{t+k}, v_{t}^{k}\right)+l^{p}\left(\pi_{t+k}, \mathbf{p}_{t}^{k}\right)+c\|\theta\|^{2} \tag{1}$

ここで、 $l^r$ 、 $l^v$ 、および $l^p$ は、それぞれ報酬、価値、および方策の損失関数である。
補足図S2は、MuZeroアルゴリズムがどのように計画、行動、学習するかを制御する式をまとめたものである。

補足図S2

$\displaystyle {\text { Model }} \\ \left.\begin{array}{c} {s^{0}=h_{\theta}\left(o_{1}, \ldots, o_{t}\right)} \\ {r^{k}, s^{k}=g_{\theta}\left(s^{k-1}, a^{k}\right)} \\ {\mathbf{p}^{k}, v^{k}=f_{\theta}\left(s^{k}\right)}\end{array}\right\} \mathbf{p}^{k}, v^{k}, r^{k}=\mu_{\theta}\left(o_{1}, \ldots, o_{t}, a^{1}, \ldots, a^{k}\right)$

$\displaystyle {\text { Search }} \\ \begin{array}{c}{\nu_{t}, \pi_{t}=M C T S\left(s_{t}^{0}, \mu_{\theta}\right)} \\ {a_{t} \sim \pi_{t}}\end{array}$

$\displaystyle {\text { Learning Rule }} \\ \begin{array}{c}{\mathbf{p}_{t}^{k}, v_{t}^{k}, r_{t}^{k}=\mu_{\theta}\left(o_{1}, \ldots, o_{t}, a_{t+1}, \ldots, a_{t+k}\right)}\end{array} \\ z_{t}=\left\{\begin{array}{ll}{u_{T}} & {\text { for games }} \\ {u_{t+1}+\gamma u_{t+2}+\ldots+\gamma^{n-1} u_{t+n}+\gamma^{n} \nu_{t+n}} & {\text { for general MDPs }}\end{array}\right. \\ l_{t}(\theta)=\sum_{k=0}^{K} l^{r}\left(u_{t+k}, r_{t}^{k}\right)+l^{v}\left(z_{t+k}, v_{t}^{k}\right)+l^{p}\left(\pi_{t+k}, p_{t}^{k}\right)+c\|\theta\|^{2}$

$\displaystyle {\text { Losses }} \\ l^{r}(u, r)=\left\{\begin{array}{ll}{0} & {\text { for games }} \\ {\phi(u)^{T} \log \mathbf{r}} & {\text { for general MDPs }}\end{array}\right. \\ l^{v}(z, q)=\left\{\begin{array}{ll}{(z-q)^{2}} & {\text { for games }} \\ {\phi(z)^{T} \log \mathbf{q}} & {\text { for general MDPs }}\end{array}\right. \\ l^{p}(\pi, p)=\pi^{T} \log \mathbf{p}$

図1：学習モデルを使用したプランニング、行動、および訓練

f:id:TadaoYamaoka:20191121214604p:plain

（A）MuZeroがモデルを使用してプランニングする方法

モデルは、表現、ダイナミクス、および予測のための3つの接続されたコンポーネントで構成されている。
前の隠れ状態 $s^{k-1}$ と候補行動 $a^k$ が与えられると、ダイナミクス関数 $g$ は即時報酬 $r^k$ と新しい隠れ状態 $s^k$ を生成する。
方策 $p^k$ および価値関数 $v^k$ は、予測関数 $f$ によって隠れ状態 $s^k$ から計算される。
初期隠れ状態 $s^0$ は、過去の観測（囲碁の盤面やAtariの画面など）を表現関数 $h$ に渡すことで取得される。

（B）MuZeroが環境でどのように動作するか

Aで説明したように、モンテカルロ木探索は各タイムステップtで実行される。
行動 $a_{t+1}$ は、ルートノードからの各アクションの訪問回数に比例する探索方策 $\pi_t$ からサンプリングされる。
環境は行動を受け取り、新しい観測値 $o_{t+1}$ と報酬 $u_{t+1}$ を生成する。
エピソードの終わりに、軌跡データはリプレイバッファに保存される。

（C）MuZeroがモデルを訓練する方法

軌跡は、リプレイバッファからサンプリングされる。
最初のステップでは、表現関数 $h$ は、選択された軌跡から過去の観測 $o_{1}, \dots, o_{t}$ を入力として受け取る。
その後、Kステップのモデルが再帰的に展開される。
各ステップkで、ダイナミクス関数 $g$ は入力として前のステップからの隠れ状態 $s^{k-1}$ と実際の行動[tex:a_{t+k}を受け取る。
表現、ダイナミクス、および予測関数のパラメーターは、3つの量を予測するために、backpropagation-through-timeによりエンドツーエンドで一緒に訓練される。
3つの量：方策 $\mathbf{p}^{k} \approx \pi_{t+k}$ 、価値関数 $v^{k} \approx z_{t+k}$ 、および報酬 $r_{t+k} \approx u_{t+k}$
ここで、 $z_{t+k}$ はサンプルの収益（最終報酬（ボードゲーム）またはnステップ収益（Atari））である。

感想

MuZeroのアルゴリズムは図1を見るとわかりやすいです。

図1(A)を見ると、表現関数 $h$ 、ダイナミクス関数 $g$ 、予測関数 $f$ を使用してMCTSでシミュレーションを行っています。
UCBの式は付録で解説があるので、別途読んでいきます。
AlphaZeroでは手を指した後の局面は、実際にゲームの盤面に手を適用して進めていますが、MuZeroでは、ダイナミクス関数 $g$ を使用して次の局面の隠れ状態を取得する点が異なっています。

図1(B)の行動の選択は、AlphaZeroと同じく訪問回数に応じて選択されています。

図1(C)の学習は、リプレイバッファから取得した軌跡について、開始状態から予測関数 $f$ とダイナミクス関数 $g$ に従いKステップ分展開した系列と、実際にMCTSに従い選択した軌跡が一致するように学習されています。再帰的な関数になるため、リカレントニューラルネットワークで使用されるbackpropagation-through-time(BPTT)を使用してエンドツーエンドで学習されています。実装する場合は、この部分が難しそうです。

(続く)

*1:https://dl.acm.org/citation.cfm?id=528623

2019-11-23

AlphaStarの論文を読むその８（教師あり学習、強化学習）

AlphaStar 強化学習

今回はMethodsの教師あり学習と強化学習についてです。

教師あり学習

各エージェントは、人間の行動を模倣するために、リプレイから教師付き学習を通じて最初に訓練される。
教師あり学習は、エージェントの初期化と多様な探索の維持の両方に使用される。
このため、主な目標は、StarCraftの複雑さを捉えた多様なポリシーを作成することにある。

データセット、観測と行動、アーキテクチャ

StarCraft IIバージョン4.8.2から4.8.6で、MMR（Eloに似たブリザードの指標）が3500を超える、つまり上位22％のプレイヤーによってプレイされた971,000リプレイのデータセットを使用する。
観測とアクションは、ゲームの生のインターフェイス（拡張データテーブル1および2で説明）によって返される。
強化学習で使用したものと同じアーキテクチャで、各種族に1つの方策を訓練する。

統計z

各リプレイから、各プレーヤーのビルド順序（最初の20の建設された建物とユニットとして定義）、累積統計（ユニット、建物、効果として定義）、およびゲーム中に出現したアップグレードをエンコードする統計zを抽出する。
教師あり学習と強化学習の両方でzで方策を調整し、教師あり学習ではzを時間の10％でゼロに設定する。

訓練方法

方策を訓練するために、各ステップで現在の観測値を入力し、各アクション引数の確率分布を出力する（拡張データ表2）。
これらの引数について、人間の行動と方策の出力との間のKLダイバージェンスを計算し、Adam最適化を使用して更新する。
また、L2正則化を適用する。
教師あり訓練アルゴリズムの擬似コードは、補足データの擬似コードにある。

ファインチューニング、多様性

MMRが6200（16,000ゲーム）を超える勝利したリプレイのみを使用して、方策をさらにファインチューニングする。
ファインチューニングにより、組み込みのエリートボットに対する勝率がプロトス対プロトスで87％から96％に改善された。
ファインチューニングされた教師ありエージェントは、テラン、プロトス、およびザーグでそれぞれ3947、3607、3544 MMRと評価された。
ゲーム内のすべてのユニットを構築することができ、ゲームごとに質の多様性がある（拡張データ図4）。

拡張データ図4 | ゲームに組み込まれたユニットの分布

f:id:TadaoYamaoka:20191122082335p:plain
Protoss AlphaStar Supervised（左）とAlphaStar Final（右）が複数のセルフプレイゲームで構築したユニット。AlphaStarSupervisedはすべてのユニットを構築できる。

強化学習

エージェント対エージェントのゲームに基づいてAlphaStarのパフォーマンスを改善するために強化学習を適用する。
対戦結果（負けで-1、引き分けで0、勝ちで+1）を終端の報酬 $r_{T}$ として使用し、ゲームに勝つという真の目標を正確に反映するために割引なしで使用する。
アクタークリティックのパラダイムに従い、価値関数 $V_{\theta}\left(s_{t}, z\right)$ は $r_{T}$ を予測するために訓練され、方策 $\pi_{\theta}\left(a_{t} | s_{t}, z\right)$ を更新するために使用される。

強化学習におけるStarCraftの課題

StarCraftは、強化学習の問題と見なされると、いくつかの課題を提起する。
ドメインの複雑さと報酬の希薄性のため、探索が困難である。
方策は、訓練を通じてさまざまな戦略を実行できる必要がある。そして、長い期間と複雑な行動空間のために、オフポリシーの学習が困難である。

探索と多様性

私たちは人間のデータを使用して、探索を支援し、訓練を通じて戦略的多様性を維持する。
最初に、教師あり方策で方策パラメータを初期化し、教師あり方策と現在の方策の間のKLダイバージェンスを継続的に最小化する。
次に、人間のデータからランダムにサンプリングした戦略統計zに従うように、擬似報酬でメインエージェントを訓練する。
これらの疑似報酬は、サンプリングされたビルド順序と実行されたビルド順序間の編集距離(レーベンシュタイン距離)、およびサンプリングされた累積統計と実行された累積統計間のハミング距離を測定する（補足データ詳細アーキテクチャを参照）。
疑似報酬の各タイプは、25%の確率でアクティブ（ゼロ以外）であり、各疑似報酬に対して個別の価値関数と損失が計算される。
強化学習で優れたパフォーマンスを達成するには、人間のデータの使用が重要であることがわかった（図3E）。

f:id:TadaoYamaoka:20191101085707p:plain

価値と方策の更新

新しい軌跡はアクターによって生成される。
非同期に、軌跡を格納する再生バッファーを使用して、モデルパラメーターはラーナー(learner)によって更新される。
このため、AlphaStarはオフポリシーのデータの影響を受けるため、オフポリシーの補正が必要になる可能性がある。
V-trace*1などのオフポリシーの補正方法は、StarCraftに使用したような大規模で構造化された行動空間では非効率的であることがわかった。
ハイブリッドアプローチを使用してこれに対処する。
方策はV-traceを使用して更新され、価値の推定値はTD(𝜆)*2を使用して更新される。
TD(𝜆)はオフポリシーの補正を適用しない（図3Iのアブレーション）。

f:id:TadaoYamaoka:20191122085204p:plain

価値の推定値の分散を減らすために、相手の観測値を価値関数への入力として使用する（図3Kのアブレーション）。

f:id:TadaoYamaoka:20191122085307p:plain

評価中に価値関数は不要なため、これらは訓練中にのみ使用されることに注意する。

V-trace

方策 $\pi_{\theta}\left(a_{t} | s_{t}, z\right)$ では、V-traceのオフポリシー補正を使用すると、学習の安定性が向上した。
大きな行動空間による早期のトレースカットを緩和するために、アクションタイプ、遅延、および他のすべての引数間の独立性を想定し、それらを個別に更新する。

UPGO

V-trace方策更新に加えて、以下の方向に方策パラメーターを更新するupgoing policy update（UPGO）を導入する。

$\displaystyle \rho_{t}\left(G_{t}^{\mathrm{U}}-V_{\theta}\left(s_{t}, z\right)\right) \nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}, z\right)$

ここで

$\displaystyle G_{t}^{\mathrm{U}}=\left\{\begin{array}{ll}{r_{t}+G_{t+1}^{\mathrm{U}}} & {\text { if } Q\left(s_{t+1}, a_{t+1}, z\right) \geq V_{\theta}\left(s_{t+1}, z\right)} \\ {r_{t}+V_{\theta}\left(s_{t+1}, z\right)} & {\text { otherwise }}\end{array}\right.$

は上昇リターン、 $Q\left(s_{t}, a_{t}, z\right)$ は行動価値の推定値、 $\rho_{t}=\min \left(\frac{\pi_{\theta}\left(a_{t} | s_{t}, z\right)}{\pi_{\theta^{\prime}}\left(a_{t} | s_{t}, z\right)}, 1\right)$ はクリップされた重要度比、 $\pi_{\theta^{\prime}}$ はアクターの軌跡を生成した方策である。

自己模倣学習と同様に、この考え方は、行動方策が平均よりも悪い行動をとる場合にブートストラップすることにより、予想よりも良いリターンを伴う部分軌跡から方策を更新することである（図3Iのアブレーション）。

f:id:TadaoYamaoka:20191122085204p:plain

StarCraftの大きな行動空間で $Q\left(s_{t}, a_{t}, z\right)$ を近似することは難しいため、1ステップターゲット $Q\left(s_{t}, a_{t}, z\right)=r_{t}+V_{\theta}\left(s_{t+1}, z\right)$ で行動価値を推定する。

全体の損失

全体の損失は、前述の方策と価値関数の損失の加重合計であり、勝敗報酬 $r_t$ に対応するだけでなく、人間のデータに基づく擬似報酬、教師あり方策に関するKLダイバージェンス損失、および標準エントロピー正則化損失*3にも対応する。
Adamで全体の損失を最適化する。
強化学習アルゴリズムの擬似コードは、補足データの擬似コードに記載されている。

感想

ある程度上位の人間のリプレイで教師あり学習した後に、最上位のプレイヤーでファインチューニングを行う方法は、泥臭い手法のように思いますが、機械学習ではやはりこういった手法が有効なようです。

強化学習において行動の多様性を確保するには、人間のリプレイの統計が重要であることが示されています。
多様性の確保にはAtariの最難関 Montezuma’s Revengeを攻略したRandom Network Distillationといった人間の統計を使用しない方法もあるようですが、人間のリプレイが大量に手に入る場合は、人間の統計を使う方が効率がよさそうです。

価値関数の更新にはオフポリシー補正なしのTD(λ)、方策の更新には、オフポリシー補正にV-trace、1ステップ収益の代わりに部分的にブートストラップするUPGOという手法が用いられていて、最新の強化学習の手法がいくつも盛り込まれています。

(続く)

*1:[1802.01561] IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures

*2:Sutton & Barto Book: Reinforcement Learning: An Introduction

*3:[1602.01783] Asynchronous Methods for Deep Reinforcement Learning