論文の概要: XDO: A Double Oracle Algorithm for Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2103.06426v1
• Date: Thu, 11 Mar 2021 03:05:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-13 10:27:42.351531
• Title: XDO: A Double Oracle Algorithm for Extensive-Form Games
• Title（参考訳）: XDO: 拡張型ゲームのためのダブルOracleアルゴリズム
• Authors: Stephen McAleer, John Lanier, Pierre Baldi, Roy Fox
• Abstract要約: 我々は,インフォステート数を線形に近似ナッシュ平衡に収束する拡張型二重オラクルアルゴリズムを提案する。 ゲームの根元で最高のレスポンスをミックスするPSROとは異なり、XDOはすべてのインフォステートで最高のレスポンスをミックスします。 改良されたLeducポーカーゲームの実験では、XDOはCFRよりも11倍、PSROやXFPより82倍低いエクスプロイラビリティを実現している。
• 参考スコア（独自算出の注目度）: 14.823154995416997
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Policy Space Response Oracles (PSRO) is a deep reinforcement learning algorithm for two-player zero-sum games that has empirically found approximate Nash equilibria in large games. Although PSRO is guaranteed to converge to a Nash equilibrium, it may take an exponential number of iterations as the number of infostates grows. We propose Extensive-Form Double Oracle (XDO), an extensive-form double oracle algorithm that is guaranteed to converge to an approximate Nash equilibrium linearly in the number of infostates. Unlike PSRO, which mixes best responses at the root of the game, XDO mixes best responses at every infostate. We also introduce Neural XDO (NXDO), where the best response is learned through deep RL. In tabular experiments on Leduc poker, we find that XDO achieves an approximate Nash equilibrium in a number of iterations 1-2 orders of magnitude smaller than PSRO. In experiments on a modified Leduc poker game, we show that tabular XDO achieves over 11x lower exploitability than CFR and over 82x lower exploitability than PSRO and XFP in the same amount of time. We also show that NXDO beats PSRO and is competitive with NFSP on a large no-limit poker game.
• Abstract（参考訳）: Policy Space Response Oracles(PSRO)は、大規模ゲームにおけるNash平衡の近似を実証的に発見した2プレイヤーゼロサムゲームのための深層強化学習アルゴリズムである。 PSROはナッシュ平衡に収束することが保証されているが、インフォステートの数が増えるにつれて指数関数的に反復する。 インフォステート数に近似的なナッシュ平衡に収束することが保証される拡張形式二重オラクルアルゴリズムであるExtensive-Form Double Oracle (XDO)を提案する。 ゲームの根元で最高のレスポンスをミックスするPSROとは異なり、XDOはすべてのインフォステートで最高のレスポンスをミックスします。 またニューラルXDO (NXDO) も導入し, より深いRLを用いて最良の応答を学習する。 Leduc ポーカーの表計算実験では、XDO はPSRO よりも 1-2 桁小さい反復数で近似的な Nash 平衡を達成する。 改良型leducポーカーゲームにおける実験では,表型xdoがcfrよりも11倍以上,psroやxfpよりも82倍以上のエクスプロイト性を実現していることが示された。 また,NXDOがPSROに勝って,NFSPと競合していることを示す。

関連論文リスト

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games [69.5064797859053]
  本稿では,各イテレーションの個体群に対して,ほぼ最適なポリシーを付加する手法であるemphSelf-Play PSRO(SP-PSRO)を紹介する。 SP-PSRO は経験的に APSRO よりもはるかに早く収束する傾向があり、多くのゲームではほんの数イテレーションで収束する。
  論文  参考訳（メタデータ） (2022-07-13T22:55:51Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Efficient Policy Space Response Oracles [61.71849698253696]
  ポリシー空間応答 Oracle 法 (PSRO) は、2プレイヤーゼロサムゲームにおけるナッシュ均衡の一般解を提供する。 我々の開発の中心は、制限なし(URR)ゲームにおけるミニマックス最適化の導入である。 壁面時間, 10倍のデータ効率, および既存のPSRO法と同様のエクスプロイザビリティを, Kuhn と Leduc Poker のゲームで50倍高速化したことを報告した。
  論文  参考訳（メタデータ） (2022-01-28T17:54:45Z)
• Anytime Optimal PSRO for Two-Player Zero-Sum Games [17.821479538423155]
  Policy Space Response Oracles (PSRO) は、継続的なアクションを扱うことができるゲームのための強化学習アルゴリズムである。 AODOは、ナッシュ均衡に収束する2プレイヤーゼロサムゲームのための二重オラクルアルゴリズムである。 提案手法は, DOやPSROよりもはるかに低いエクスプロイザビリティを実現し, エクスプロイザビリティを向上しないことを示す。
  論文  参考訳（メタデータ） (2022-01-19T16:34:11Z)
• Online Double Oracle [20.291016382324777]
  本論文では,純粋な戦略の数が巨大あるいは無限である2プレイヤーゼロサムゲームにおける新しい学習アルゴリズムを提案する。 私たちの方法は、$k$がゲームのサイズではない自己再生設定で$mathcalO(sqrtT k log(k))$の後悔の境界を達成します。
  論文  参考訳（メタデータ） (2021-03-13T19:48:27Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Combining Deep Reinforcement Learning and Search for Imperfect-Information Games [30.520629802135574]
  本稿では,自己再生強化学習と探索のためのフレームワークであるReBeLを,ゼロサムゲームにおけるナッシュ均衡に確実に収束させる。 また、ReBeLは、従来のポーカーAIよりもはるかに少ないドメイン知識を使用しながら、制限なしのテキサスホールド'emポーカーのパフォーマンスを達成することを示す。
  論文  参考訳（メタデータ） (2020-07-27T15:21:22Z)
• Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games [11.866835246140647]
  ポリシー空間応答オラクル(英: Policy Space Response Oracles、PSRO)は、近似的なナッシュ均衡に収束することが保証される深い強化学習アルゴリズムである。 大規模ゲームにおける近似的なナッシュ平衡を求めるための,最初のスケーラブルな一般化手法であるPipeline PSROを紹介する。 また,ストラテゴの変種であるBarrage Strategoのオープンソース環境についても紹介する。
  論文  参考訳（メタデータ） (2020-06-15T17:17:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。