論文の概要: The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2604.16087v1
• Date: Fri, 17 Apr 2026 14:17:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-20 22:00:19.950219
• Title: The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
• Title（参考訳）: バンドフィードバックを持つゼロサムゲームにおける非結合学習のための最後の繰り返し収束
• Authors: Côme Fiegel, Pierre Ménard, Tadashi Kozuno, Michal Valko, Vianney Perchet,
• Abstract要約: ゼロサム行列ゲームにおいて繰り返しプレイやバンディットフィードバックで学習する問題について検討する。 プレイヤー間の通信なしに、最終項目のナッシュ均衡への収束を保証するアンカップリングアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 46.50566806285207
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of $\mathcal{O}(T^{-1/8})$ on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being $Ω(T^{-1/4})$ in contrast to the usual $Ω(T^{-1/2})$ rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.
• Abstract（参考訳）: 本研究では,ゼロサム行列ゲームにおいて繰り返しプレイとバンディットフィードバックで学習する問題について検討する。 具体的には,プレイヤー間のコミュニケーションがなければ,最終項目のナッシュ均衡への収束を保証する未結合アルゴリズムの開発に焦点をあてる。 非バンディットのケースは広く研究されているが、この設定は、エクスプロイザビリティギャップに$\mathcal{O}(T^{-1/8})$の制限を課すことによって、最近のみ検討されている。 アンカップリングアルゴリズムでは、平均的なイテレートの収束に対する$Ω(T^{-1/4})$に対して、最も達成可能な速度が$Ω(T^{-1/4})$であるのに対し、ポリシプロファイルのナッシュ均衡への収束を保証することが性能に有害であることを示す。 次に、この最適率を定数および対数因子まで達成する2つのアルゴリズムを提案する。 第1のアルゴリズムは、探索と搾取の間の直接的なトレードオフを利用し、第2のアルゴリズムは、2段階のミラー降下アプローチに基づく正規化手法を採用する。

関連論文リスト

• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  大規模なゲームでは、非結合学習ダイナミクスの平均的な繰り返しを新しい非結合学習ダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示す。 我々の削減は、各プレイヤーの効用が自身の戦略と全ての対戦者の共同戦略の両方において線形であるゲームに適用される。
  論文  参考訳（メタデータ） (2025-06-04T00:24:14Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
  論文  参考訳（メタデータ） (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)

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

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