概要
| Double Oracle | |
| 英名 | DO |
| 別名 | ダブル・オラクル |
Double Oracleとは、ナッシュ均衡を求めるゲーム理論のアルゴリズムの一つ。
根本的なアルゴリズムの構造としては、列生成法に近い。プレイヤー1もプレイヤー2も両方がオラクルを利用して純粋戦略の候補を追加していくのがその名の由来である。
限られた純粋戦略候補の中から開始し、小さなゲームの解(混合戦略)を求める。
その得られた解に対して、オラクルは全ての戦略から最適応答を探す。そして、その最適応答の戦略を戦略候補の中に追加して、再び小さなゲームを解くということを繰り返す。
オラクルの見つける最適応答による利得が、現在の戦略の期待利得と十分近くなったときに終了し、その時点での混合戦略がナッシュ均衡戦略の近似となる。
深層学習や強化学習への拡張としては、PSROがある。
参考になる文献
- Double Oracleの原論文
- Planning in the Presence of Cost Functions Controlled by an Adversary
- 連続ゲームへの拡張
- Double Oracle Algorithm for Computing Equilibria in Continuous Games
