論文の概要: Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games
- arxiv url: http://arxiv.org/abs/2208.09747v2
- Date: Wed, 31 May 2023 01:02:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 04:18:53.388901
- Title: Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games
- Title（参考訳）: 総合型ゲームにおける準最適$\Phi$-regret学習
- Authors: Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm
- Abstract要約: 我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。
これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
- 参考スコア（独自算出の注目度）: 95.91027522413265
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we establish efficient and uncoupled learning dynamics so
that, when employed by all players in multiplayer perfect-recall
imperfect-information extensive-form games, the trigger regret of each player
grows as $O(\log T)$ after $T$ repetitions of play. This improves exponentially
over the prior best known trigger-regret bound of $O(T^{1/4})$, and settles a
recent open question by Bai et al. (2022). As an immediate consequence, we
guarantee convergence to the set of extensive-form correlated equilibria and
coarse correlated equilibria at a near-optimal rate of $\frac{\log T}{T}$.
Building on prior work, at the heart of our construction lies a more general
result regarding fixed points deriving from rational functions with polynomial
degree, a property that we establish for the fixed points of (coarse) trigger
deviation functions. Moreover, our construction leverages a refined regret
circuit for the convex hull, which -- unlike prior guarantees -- preserves the
RVU property introduced by Syrgkanis et al. (NIPS, 2015); this observation has
an independent interest in establishing near-optimal regret under learning
dynamics based on a CFR-type decomposition of the regret.
- Abstract（参考訳）: 本稿では,マルチプレイヤーの完全リコール不完全情報多形式ゲームにおいて,全プレイヤーが使用した場合,各プレイヤーのトリガ後悔がt$の繰り返し後に$o(\log t)$となるように,効率的かつ非結合的な学習ダイナミクスを確立する。
これは、以前のよく知られた$O(T^{1/4})$よりも指数関数的に改善され、Bai et al. (2022) による最近の開問題に着目する。
即ち、大域的な相関平衡と粗相関平衡の組への収束を、ほぼ最適のレートである $\frac{\log t}{t}$ で保証する。
我々の構成の核心にある先行研究は、多項式次数を持つ有理関数から導出される不動点に関するより一般的な結果である。
さらに,従来の保証とは異なり,sirgkanis et al. (nips, 2015) が導入した rvu 特性を保存し,cfr 型の後悔の分解に基づく学習ダイナミクス下での最適に近い後悔を確立することに関心を持っている。
関連論文リスト
- $\widetilde{O}(T^{-1})$ Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games [8.215874655947335]
楽観的フォロー・ザ・レギュラライズド・リーダー・アルゴリズムは,フル情報汎用マルコフゲームにおいて,$widetildeO(T-1)$-approximate iterationsを$T$内で見つけることができることを示す。
論文 参考訳（メタデータ） (2024-02-02T20:40:27Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - Near-Optimal No-Regret Learning for Correlated Equilibria in
Multi-Player General-Sum Games [104.74734408204749]
マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。
外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
論文 参考訳（メタデータ） (2021-11-11T01:19:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。