ゲーム理論において、ジェネラリストがスペシャリストに勝る場合がある
研究者らは、ある種のゲームにおいて、見過ごされてきたアルゴリズムのクラスが予想よりもはるかに優れた性能を発揮することを示した。
ポーカーを一人の相手とプレイする場合でも、住宅購入の入札合戦に別の購入希望者と参加する場合でも、不完全情報の条件下で行動しています。ポーカーでは自分の手札を知り、住宅の希望価格以上の予算も把握していますが、相手の手札や他の購入希望者がいくらまで支払う意思があるかはわかりません。
MITの研究者らが共同執筆し、4月にリオデジャネイロで開催された国際会議ICLRで発表された論文は、これらの状況で具体的に何をすべきかを教えるものではありません。しかし、2人の対戦者が「ゼロサム」競争（一方の利益が他方の損失となる）で対決する不完全情報ゲームに関する新たな洞察を提供します。
プロジェクトに参加したMIT研究者には、電気電子工学・コンピュータサイエンス学科（EECS）および情報・意思決定システム研究室（LIDS）の博士課程学生Sobhan Mohammadpour氏、EECS助教授でLIDS主席研究員のGabriele Farina氏が含まれます。他の共著者は、テキサス大学オースティン校（UT）のMax Rudolph氏、カリフォルニア大学バークレー校（UCB）のNathan Lichtlé氏とAlexandre Bayen氏、カーネギーメロン大学（CMU）のJ. Zico Kolter氏、Amy X. Zhang ’11, MNG ’12氏、ニューヨーク大学のEugene Vinitsky氏、CMUのSamuel Sokota氏です。
この研究の焦点は、不完全情報ゲームに参加するニューラルネットワークを訓練するために使用できるアルゴリズムにあります。長年にわたってこの分野で広く信じられていた仮定は、ゲーム理論の原理に基づくアルゴリズムが、1990年代に意思決定に使われ始めた汎用アルゴリズム群であるポリシーグラディエント法を明らかに凌駕するというものでした。「ポリシー」は基本的に戦略を意味し、「グラディエント」は最大の変化をもたらす方向（例えば丘の頂上や底）への経路を指します。ポリシーグラディエント法は、ニューラルネットワークが小さな逐次的なステップで特定の目標に向かって意思決定を行い、その過程で継続的に調整と修正を加えてエージェントを目的の目的地に近づけるために使用されています。
戦略的ゲームは1990年代初頭にポリシーグラディエント法が考案された当初の目的ではありませんでしたが、新しい論文の著者らは、このアルゴリズムクラスが2人用ゲームでどのように機能するかを疑問視しました。Farina氏によれば、これらの手法はマルチエージェント環境では分析が複雑になります。「自分の状況を改善するために動ける方向はまだありますが、相手の行動により、その方向はゲームの進行中に絶えず変化し、その変化は急速になり得ます。」
「専門的なゲーム理論アルゴリズムがこの設定に適しているというのはほぼ当然のことと考えられていました」とSokota氏は述べます。「私たちの研究は、ポリシーグラディエント法がこれらの専門アルゴリズムよりも優れた性能を発揮できること、そして専門アルゴリズムは人々が考えていたほど効果的ではない可能性があることを示しました。これは、なぜこれまで見過ごされてきたのかという興味深い社会学的疑問を提起します。その答えの一部は、この分野がアルゴリズムを厳密に評価するために必要な工学的作業を行っていなかったため、何が機能し何が機能しないかを判断するのが難しかったことにあります。」
その結果、この研究の主要な貢献は、不完全情報ゲームで競争するエージェント（ニューラルネットワーク）を教えるさまざまなアルゴリズムを公平に評価する方法を提供したことです。「私たちは異なるアプローチを取っています」とRudolph氏は述べます。「この分野で発表される多くの論文とは異なり、他のアルゴリズムを打ち負かす新しいアルゴリズムを提案しているわけではありません。私たちはアルゴリズムを評価するためのベンチマークを提案しているのです。」
簡単に言えば、ベンチマークはアルゴリズムの性能を評価するために設計されたソフトウェアから構成されます。「私たちが提供しているのはテスト場、あるいは競技場であり、人々は自分のアルゴリズムを持ち込み、特定のタスクで訓練し、どれだけうまく機能するかを確認できます」とFarina氏は述べます。
グループは「搾取可能性」と呼ばれる概念を用いてプレイヤーの性能を計算します。これはプレイヤーが「最悪の敵」に対してどれだけうまく対処できるかを測定します。Sokota氏は説明します。「ポーカーのようなゲームでは、この相手は私の手札を知りませんが、私がどの手札でどのように振る舞うかを知っています。」この尺度でゼロを達成することは完璧なプレイを意味し、高い搾取可能性スコアは最適からほど遠いプレイを示します。
チームが実施した実験では、5つのゲームがプレイされました：相手の行動が見えない2つの幻の三目並べ、ボードゲームHexの2つの不完全情報バリアント、および欺瞞ゲームの嘘つきのサイコロです。
研究者らが直面した最大の課題は、最大300億の状態を含む可能性のあるこの規模のゲームに搾取可能性尺度を適用することでした。この場合の「状態」は可能なボードの位置すべてだけでなく、ゲームの全履歴、途中のすべてのステップと失敗を含みます。
「それは見えない物体で満たされた暗い部屋を見つめるようなものです」とMohammadpour氏は述べます。「何とかしてそれらの物体がどこにあり、どのようにしてそこに至ったかを把握する必要があります。」Mohammadpour氏は、以前の研究者は通常、自分たちが分析したゲームよりも10万倍小さいゲームに搾取可能性を使用していたと付け加えます。
これら5つのゲームで行われた実験では、ポリシーグラディエントアルゴリズムで訓練されたニューラルネットワークは、ゲーム理論に基づくアルゴリズムで訓練されたネットワークよりも良い（低い）搾取可能性スコアを獲得しました。次のラウンドで行われた直接対決では、ポリシーグラディエントで訓練されたネットワークが再びゲーム理論で訓練された相手を打ち負かしました。「これらの結果は安心できるものでした」とRudolph氏は述べます。「なぜなら、ベンチマークアプローチへの信頼が高まるからです。」
チームはベンチマークソフトウェアを自由に利用可能にし、使いやすくしました。「スーパーコンピュータは必要ありません」とMohammadpour氏は述べます。「通常のラップトップで実行できます。そして、一般的に使用されるベンチマークソフトウェアコレクションOpenSpielに1行のコードを追加するだけで済みます。」
実験ではかなりニッチなゲームが使われましたが、Farina氏はこの研究をより広い文脈に位置づけたいと考えています。「『ゲーム』という用語は実際にはあらゆるマルチエージェントの戦略的相互作用に適用されることを覚えておいてください」と彼は述べます。「したがって、この研究から得られる教訓は決して娯楽ゲームに限定されるものではありません。」
Vinitsky氏も同意します。「隠された情報は世界の非常に重要な特性です」と彼は述べます。「それは軍事作戦、取引シナリオ、交渉など、さまざまなものに浸透しており、それらすべては隠された情報の条件下で行われます。これらのゲームを改善できるという考えは、他の設定でもより良い結果を達成できる可能性を示唆しています。」
この研究に関与していないGoogle DeepMindのコンピュータ科学者兼ゲーム理論専門家Ian Gemp氏は、これらの結果を励みになるものと評価しています。「この研究は、古典的なツール（ポリシーグラディエント法など）を現代化することが、複雑な戦略的問題を解決するための非常に生産的な道であり続けることを示す説得力のあるリマインダーです。」