論文の概要: Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2208.09747v1
• Date: Sat, 20 Aug 2022 20:48:58 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-23 14:29:03.374356
• 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 \emph{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 \emph{extensive-form correlated equilibria} and \emph{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 \emph{polynomial degree}, a property that we establish for the fixed points of \emph{(coarse) trigger deviation functions}. Moreover, our construction leverages a refined \textit{regret circuit} for the convex hull, which -- unlike prior guarantees -- preserves the \emph{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（参考訳）: 本稿では,マルチプレイヤーの完全リコール不完全情報広義ゲームにおいて,各プレイヤーの「emph{trigger regret}」が,プレイの繰り返し後に$O(\log T)$として成長するように,効率的で非結合な学習ダイナミクスを確立する。 これは、以前のよく知られた$O(T^{1/4})$よりも指数関数的に改善し、Bai et al. (2022) による最近の開問題に解決する。 即ち、ほぼ最適に近いレートで \emph{extensive-form correlationd equilibria} と \emph{coarse correlationd equilibria} の組への収束を、$\frac{\log t}{t}$ で保証する。 先行研究に基づいて、我々の構成の核心にあるより一般的な結果として、不動点に関するより一般的な結果が、 \emph{polynomial degree} を持つ有理関数から導かれる、すなわち、 \emph{(coarse) トリガー偏差関数の不動点に対して確立される性質である。 さらに, 先行保証とは異なり, syrgkanis らによって導入された \emph{rvu property} (nips, 2015) を保存した凸包の洗練された \textit{regret circuit} を活用する。

関連論文リスト

• $\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)

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

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