TadaoYamaokaの日記

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

AlphaStarの論文を読む その2

昨日の続きです。

人間のデータの重要性

  • StarCraftの主な課題の1つは、新しい戦略を発見すること
  • 一度、地上ユニットの局所戦略を学んだ後、航空ユニットを単純に使用するとパフォーマンスが低下する
  • 航空ユニットがその局所戦略を効果的に利用する、数千ステップを超える一連の命令を実行する可能性は非常に低い
  • この問題に対処するため、人間のデータを利用する
  • 各エージェントは教師ありで学習したパラメータで初期化される
  • 強化学習中にも、エージェントを人間の統計に条件付ける
  • エージェントは統計に従う報酬を受け取るか、もしくは、条件なしで独自の戦略を自由に選択して訓練する
  • また、エージェントは行動の確率が教師方策と異なる場合、ペナルティを受け取る
  • この人間の探索の導入により、訓練中、多様なプレイが引き続き調査される
  • 図3Eに人間のデータの重要性を示す

f:id:TadaoYamaoka:20191101085707p:plain

感想

単体では効果のない行動を他の行動と関連させた場合に効果を発揮し、それにステップ数を要する場合、強化学習で学習させることが困難であることが示されています。
将棋に例えると大駒を捨ててでも相手の囲いを崩すといった、局所的には駒損でも数手先で有利になるといったケースでしょうか。
AlphaZeroがうまくいっているのは、囲碁や将棋では行動空間が比較的少ないためMCTSのような探索と組み合わせることで先読みが可能になるので、強化学習のみで学習できたのだと思います。
StarCraftのように行動空間が広すぎるため探索が使えない状況では、強化学習でステップ数のかかる戦略を発見するのは困難ということだと思います。

リーグトレーニン

  • マルチエージェント強化学習アルゴリズムであるリーグトレーニングを導入する
  • 不完全情報ゲームの場合、戦略にサイクルの関係が生まれる
  • AlphaGoと同様の自己対局では、急速に学習するが、サイクルに嵌ることがある
  • 不完全情報ゲームではFictitious self-play(FSP)という自己対局アルゴリズムで、以前のすべての方策の一様な混合に対する最良の応答を計算することでサイクルを回避できる
  • 2人ゼロサムゲームではナッシュ均衡に収束する
  • このアプローチを拡張して不均一な方策の混合に対する最良の応答を計算する
  • リーグには、多様なエージェントと現在と過去のイテレーションの方策が含まれる
  • イテレーションで、そのエージェントに固有の方策が対戦相手としてサンプリングされる
  • エージェントのパラメータはアクタークリティックによってゲームの結果から更新される
感想

不完全情報の理論は詳しくないので、FSPというのがどういうものか分かっていません。
不完全情報ゲームでは、ナッシュ均衡が最善の方策となるので、リーグを構成することでそれを発見しようという試みでしょうか。
ポーカーAIのPluribusでは、リグレット(後悔)を最小にする学習をすることで、ナッシュ均衡に収束させていました。
AlphaStarでは報酬はAlphaZeroと同じようにゲームの結果ですが、リーグ戦とすることでナッシュ均衡になるようにしているようです。

リーグ構成

  • リーグは3つの異なるタイプのエージェントで構成される
  • 主に対戦相手を選択するアルゴリズムが異なる

メインエージェント

  • メインエージェントは、各対戦相手の勝率に比例して確率的に選択する(優先順位付きfictitious self-play(PFSP)メカニズム)
  • これにより、最も問題のある相手を克服する機会がエージェントに与えられる
  • 固定確率でメインエージェントが対戦相手に選ばれる
  • これにより、自己対局による迅速な学習が回復する

メインエクスプロイトエージェント(main exploiter agent)
※適当な訳が思いつかなかったが、exploitは悪用可能といった意味。つまり、相手の弱点を突くエージェント。

  • 最新のメインエージェントのみと対戦する
  • 目的はメインエージェントの潜在的な弱点を識別すること
  • メインエージェントが弱点に対処するように促す

リーグエクスプロイトエージェント

  • メインエージェントと同様のPFSPメカニズムを使用するが、対象はメインエージェントではない
  • 目的はリーグ全体の組織的な弱点を見つけること
  • メインエクスプロイトエージェントとリーグエクスプロイトエージェントは、定期的に再初期化される
  • それにより多様性を促進し、必ずしも堅牢性の必要のない特殊な戦略を発見できる可能性がある

リーグの構成比
f:id:TadaoYamaoka:20191101223625p:plain

感想

それぞれ異なる弱点を発見する目的で異なるタイプのエージェントでリーグが構成されています。
囲碁AIのGLOBIS-AQZでもマルチエージェント学習が行われているようですが、AlphaStarのようにエージェントを目的別を分けて構成するやり方は、囲碁や将棋の学習でも応用ができそうです。
例えば終盤に特化したエージェントを作るとか。
定期的に初期化して、特殊な戦略を見つけるというやり方も効果があるかもしれません。