ゲーム理論では、一般化された戦略が専門化された戦略に勝る場合がある

ポーカーを単一の対戦相手と行う場合でも、別の見込み購入者と住宅購入の入札競争に巻き込まれる場合でも、あなたは不完全情報という条件下で行動しています。ポーカーゲームでは自分が持っているカードが何であるかを知っており、また家の提示価格よりいくら上なら支払えるかも知っていますが、カードゲームでの相手の手札や、もう一人の住宅購入者がどこまで出せるかは知りません。 MIT の研究者らが共著した論文は、リオデジャネイロで開催された 4 月の国際学習表現会議で発表されましたが、これらの状況で具体的に何をすべきかを教えるものではありません。しかし、この論文は、2 つの競技者が「ゼロサム」競争で対峙し、一方のプレイヤーの利益が他方のプレイヤーの損失を意味する、いわゆる不完全情報ゲームに関する新たな洞察を提供しています。 MIT の研究プロジェクトには、電気工学・コンピュータサイエンス学部（EECS）および情報意思決定システム研究所（LIDS）の博士課程学生である Sobhan Mohammadpour 氏と、EECS の准教授であり LIDS の主要研究者である Gabriele Farina 氏が参加しています。その他の共著者には、テキサス大学オースティン校（UT）の Max Rudolph 氏、カリフォルニア大学バークレー校（UCB）の Nathan Lichtlé 氏および Alexandre Bayen 氏、カーネギーメロン大学（CMU）の J. Zico Kolter 氏、UT の Amy X. Zhang 氏（'11, MNG '12）、ニューヨーク大学の Eugene Vinitsky 氏、そして CMU の Samuel Sokota 氏が含まれています。 新しい研究の焦点は、不完全情報ゲームに参加するようにニューラルネットワークを訓練するために使用できるアルゴリズムにあります。この分野では長年信じられてきた仮説として、ゲーム理論の原理に基づいたアルゴリズムが、1990 年代に意思決定のために導入された汎用型のアルゴリズムであるポリシー勾配法（policy gradient methods）を、この設定において明確に凌駕すると考えられていました。この文脈における「ポリシー」とは基本的に戦略を意味し、「勾配」は最も大きな変化の方向、例えば丘の頂上（または底）へと至る経路を指します。ポリシー勾配法は、ニューラルネットワークを訓練して特定の目標（比喩的に言えば山頂に到達することなど）に向かって小さな連続的なステップで意思決定を行わせるために使用されており、エージェントが意図した目的地により近づくように、その過程で継続的な調整とコース修正が行われます。 ポリシー勾配法が考案された 1990 年代初期には戦略ゲームは当初の議題に含まれていませんでしたが、新しい論文の著者たちは、この種のアルゴリズムが二人用ゲームにおいてどのように機能するかについて疑問を抱きました。ファリーナ氏によると、これらの手法はマルチエージェント設定では分析がより複雑になります。「改善できる方向はまだ存在しますが、他のプレイヤーの行動によって、その方向はゲームの進行中に絶えず変化します。そして、その変化は急速に起こり得るのです。」 「この設定においては、ゲーム理論に特化したアルゴリズムが適切なアプローチであることはほぼ当然視されていた」とソコタは語る。「私たちの研究では、ポリシー勾配法がこれらの特化型アルゴリズムよりも効果的に機能し得ることが示され、また特化型アルゴリズムは人々が考えていたほどにはうまく機能しない可能性も示されました。これはなぜこれが長期間見過ごされてきたのかという興味深い社会学的な問いを提起するものです。その答えの一部は、この分野がアルゴリズムを厳密に評価するために必要なエンジニアリング作業を行っていなかったため、何が機能し何が機能しないかを判断することが難しかったことにあるのです」 したがって、本研究の主要な貢献の一つは、エージェント（つまりニューラルネットワーク）が不完全情報ゲームで競争する方法を教えるための異なるアルゴリズムを公平に評価する手法を提供したことです。「私たちは異なるアプローチを採用しています」とルドルフは指摘します。「この分野で発表された多くの論文とは異なり、私たちは他のアルゴリズムに勝つ新しいアルゴリズムを提案しているわけではありません。私たちはこれらのアルゴリズムを評価できるベンチマーク（基準）を提案しているのです」 簡単に言えば、ベンチマークとはアルゴリズムのパフォーマンスを評価するために設計されたソフトウェアです。「私たちが提供するのは、人々が自らのアルゴリズムを持ち込み、特定のタスクのために訓練し、その成果がどの程度かを検証できるテスト場、あるいは競技場です」とファリーナは述べています グループは、プレイヤーのパフォーマンスを「エクスプロイタビリティ」と呼ばれる概念に基づいて計算します。これは、プレイヤーが「最悪の敵」に対してどの程度うまく機能するかを測定するもので、ソコタ氏は説明しています。「ポーカーのようなゲームでは、この相手は私の手札の内容を知りませんが、与えられた手札に対して私がどのように振る舞うかは知っています。」この尺度でゼロを達成することは完璧なプレイを意味し、一方、高いエクスプロイタビリティスコアは最適化されていないプレイを示します。 チームが行った実験では5つのゲームがプレイされました。プレイヤーが相手の行動を確認できない「ファントム・ナイン（Phantom Tic-Tac-Toe）」の2バージョン、そして「Hex」と呼ばれるボードゲームの不確実情報バリアント2種類、さらに嘘つきサイコロ（Liar's Dice）と呼ばれる別の欺瞞ゲームです。 研究者たちが直面した最大の課題は、この規模のゲームでエクスプロイタビリティ測定を機能させることでした。これには最大300億の状態が含まれる可能性があります。この場合における「状態」とは、単にあり得るすべての盤面配置だけでなく、その過程でのあらゆるステップやミステップを含むゲーム全体の履歴も包含します。 「見えない物体で満たされた暗闇の部屋を覗き込むようなものです」とモハマドプール氏は言います。「どうにかして、これらの物体がどこにあるか、そしてどのようにそこに到達したかを特定する必要があります。」モハマドプール氏によると、過去の研究者たちは通常、彼らの研究で分析されたゲームよりも10万倍小さいゲームに対してエクスプロイタビリティを使用してきました。 これら5つのゲームで行われた実験において、ポリシー勾配アルゴリズムで訓練されたニューラルネットワークは、ゲーム理論ベースのアルゴリズムで訓練されたネットワークよりも優れた（より低い）搾取可能性スコアを示しました。翌ラウンドで行われた直接対決では、ポリシー勾配で訓練されたネットワークが再びゲーム理論派の相手チームを破りました。「これらの結果は安心できるものです」とルドルフ氏は述べています。「なぜなら、これによりベンチマーキング手法に対する自信がさらに深まるからです。」 研究チームは、ベンチマーキング用ソフトウェアを無料で自由に利用できるようにしました。モハマドプール氏は「スーパーコンピュータは必要ありません。通常のラップトップで実行できます。必要なことは、一般的に使用されているベンチマーキングソフトウェアのコレクション『OpenSpiel』にコードを1行追加するだけです」と述べています。 実験にはややマニアックなゲームも含まれていましたが、ファリーナ氏はこの研究をより広い文脈で位置づけたいと考えています。「『ゲーム』という用語は、実際には任意のマルチエージェント戦略的相互作用に適用されることを忘れないでください」と彼は言います。「したがって、本研究から得られる教訓が娯楽ゲームに限定されるものではありません。」 ヴィニツキー氏も同意します。「隠された情報は世界の非常に重要な性質です」と彼は述べています。「これは軍事作戦、取引シナリオ、交渉など、多くの事象に浸透しており、これらすべては隠された情報の条件下で実施されます。これらのゲームを改善できるという考え方は、他の状況でもより良い成果が得られる可能性を示唆しています。」 この研究には関与していない Google DeepMind のコンピュータサイエンティストでありゲーム理論の専門家であるイアン・ゲンプは、これらの結果を歓迎しています。「この研究は、古典的なツール [例えば方策勾配法] を近代化することが、複雑な戦略的問題を解決するための非常に生産的な道であることを示す説得力のある reminder となっています」と彼は述べています。

ゲーム理論では、一般化された戦略が専門化された戦略に勝る場合がある

背景や根拠まで確認しますか？

調べる

選ぶ

サイト