論文の概要: Online Double Oracle
- arxiv url: http://arxiv.org/abs/2103.07780v2
- Date: Tue, 16 Mar 2021 14:34:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-17 11:15:24.901514
- Title: Online Double Oracle
- Title（参考訳）: オンラインDouble Oracle
- Authors: Le Cong Dinh, Yaodong Yang, Zheng Tian, Nicolas Perez Nieves, Oliver
Slumbers, David Henry Mguni, Haitham Bou Ammar, Jun Wang
- Abstract要約: 本論文では,純粋な戦略の数が巨大あるいは無限である2プレイヤーゼロサムゲームにおける新しい学習アルゴリズムを提案する。
私たちの方法は、$k$がゲームのサイズではない自己再生設定で$mathcalO(sqrtT k log(k))$の後悔の境界を達成します。
- 参考スコア（独自算出の注目度）: 20.291016382324777
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving strategic games whose action space is prohibitively large is a
critical yet under-explored topic in economics, computer science and artificial
intelligence. This paper proposes new learning algorithms in two-player
zero-sum games where the number of pure strategies is huge or even infinite.
Specifically, we combine no-regret analysis from online learning with double
oracle methods from game theory. Our method -- \emph{Online Double Oracle
(ODO)} -- achieves the regret bound of $\mathcal{O}(\sqrt{T k \log(k)})$ in
self-play setting where $k$ is NOT the size of the game, but rather the size of
\emph{effective strategy set} that is linearly dependent on the support size of
the Nash equilibrium. On tens of different real-world games, including Leduc
Poker that contains $3^{936}$ pure strategies, our methods outperform no-regret
algorithms and double oracle methods by a large margin, both in convergence
rate to Nash equilibrium and average payoff against strategic adversary.
- Abstract（参考訳）: アクションスペースが制限的に大きい戦略的ゲームを解くことは、経済学、コンピュータサイエンス、人工知能において、未解決のトピックである。
本稿では,2プレイヤーゼロサムゲームにおいて,純粋戦略の数が巨大あるいは無限であるような新たな学習アルゴリズムを提案する。
具体的には,オンライン学習のノンレグレット分析とゲーム理論のダブルオラクル手法を組み合わせる。
我々の方法 -- \emph{Online Double Oracle (ODO)} -- は、ゲームのサイズではなく、ナッシュ平衡の支持サイズに線形に依存する \emph{ Effective Strategy set} のサイズであるセルフプレイ設定において、$\mathcal{O}(\sqrt{T k \log(k)})$の後悔境界を達成する。
純粋戦略が3.936$のLeduc Pokerを含む数種類の現実世界ゲームにおいて、我々の手法は、Nash平衡への収束率と戦略的敵に対する平均ペイオフの両方において、非regretアルゴリズムと二重オラクル手法を大きなマージンで上回ります。
関連論文リスト
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - Is Learning in Games Good for the Learners? [14.781100349601587]
2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。
このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。
また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
論文 参考訳（メタデータ） (2023-05-31T02:10:27Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - 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) - 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 Markov Decision Processes with Non-oblivious Strategic Adversary [35.25621843666453]
オンラインマルコフ決定過程 (OMDP) において, 損失関数は非公開の戦略的敵によって選択される。
MDP-Expertは、暗黙の敵とうまく連携する既存のアルゴリズムで、$mathcalO(sqrtTlog(L)+tau2sqrt T log(|A|))$のポリシー後悔の限界を達成でき、$L$は敵の純粋な戦略セットのサイズであり、$|A|$はサイズを表す。
論文 参考訳（メタデータ） (2021-10-07T16:32:37Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Efficient exploration of zero-sum stochastic games [83.28949556413717]
ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。
限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。
私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
論文 参考訳（メタデータ） (2020-02-24T20:30:38Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。