論文の概要: Doubly Optimal No-Regret Learning in Monotone Games

• arxiv url: http://arxiv.org/abs/2301.13120v2
• Date: Mon, 4 Sep 2023 18:07:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 06:45:08.016429
• Title: Doubly Optimal No-Regret Learning in Monotone Games
• Title（参考訳）: 単調ゲームにおける2重最適no-regret学習
• Authors: Yang Cai, Weiqiang Zheng
• Abstract要約: 本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムを提案する。 このアルゴリズムは, 滑らかかつ凸な損失関数の下での対角的条件下での最適$O(sqrtT)$後悔と, (ii) 最適$O(frac1T)$最後の収束率をナッシュ平衡に達成する。
• 参考スコア（独自算出の注目度）: 10.760195409078591
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online learning in multi-player smooth monotone games. Existing algorithms have limitations such as (1) being only applicable to strongly monotone games; (2) lacking the no-regret guarantee; (3) having only asymptotic or slow $O(\frac{1}{\sqrt{T}})$ last-iterate convergence rate to a Nash equilibrium. While the $O(\frac{1}{\sqrt{T}})$ rate is tight for a large class of algorithms including the well-studied extragradient algorithm and optimistic gradient algorithm, it is not optimal for all gradient-based algorithms. We propose the accelerated optimistic gradient (AOG) algorithm, the first doubly optimal no-regret learning algorithm for smooth monotone games. Namely, our algorithm achieves both (i) the optimal $O(\sqrt{T})$ regret in the adversarial setting under smooth and convex loss functions and (ii) the optimal $O(\frac{1}{T})$ last-iterate convergence rate to a Nash equilibrium in multi-player smooth monotone games. As a byproduct of the accelerated last-iterate convergence rate, we further show that each player suffers only an $O(\log T)$ individual worst-case dynamic regret, providing an exponential improvement over the previous state-of-the-art $O(\sqrt{T})$ bound.
• Abstract（参考訳）: マルチプレイヤースムーズなモノトーンゲームにおけるオンライン学習について考察する。 既存のアルゴリズムには、(1)強単調ゲームにのみ適用できる、(2)非相対保証がない、(3)漸近的あるいは遅い$O(\frac{1}{\sqrt{T}})$最後の点収束速度をナッシュ平衡に限定するといった制限がある。 o(\frac{1}{\sqrt{t}})$レートは、よく研究された超勾配アルゴリズムや楽観的勾配アルゴリズムを含む多くのアルゴリズムには厳しいが、すべての勾配に基づくアルゴリズムには最適ではない。 本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムであるAOGアルゴリズムを提案する。 すなわち、我々のアルゴリズムは両方を達成する。 (i)滑らかかつ凸損失関数の下での敵対的設定における最適な$o(\sqrt{t})$ regret (ii) 最適$O(\frac{1}{T})$ストレート収束速度は、マルチプレイヤーの滑らかなモノトーンゲームにおいてナッシュ平衡となる。 加速された最終項目収束率の副産物として、各プレイヤーが1個$O(\log T)$個々の最悪の動的後悔に悩まされ、以前の最先端の$O(\sqrt{T})$境界よりも指数関数的に改善されることが示される。

関連論文リスト

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [72.43065138581589]
  RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。 本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。 そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)
• 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)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• 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)
• Tight last-iterate convergence rates for no-regret learning in multi-player games [31.604950465209335]
  定常的なステップサイズを持つ楽観的勾配(OG)アルゴリズムは,スムーズな単調ゲームにおいて最終定位レートが$O(1/sqrtT)であることを示す。 また、$O (1/sqrtT)$レートは、特別なケースとしてOGを含む全ての$p$-SCLIアルゴリズムに対して厳密であることを示す。
  論文  参考訳（メタデータ） (2020-10-26T17:06:19Z)

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

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