論文の概要: Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

• arxiv url: http://arxiv.org/abs/2605.09363v1
• Date: Sun, 10 May 2026 06:23:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.214294
• Title: Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
• Title（参考訳）: 帯域フィードバックと応答動作を持つゼロサムゲームにおける準最適最終イテレート収束
• Authors: Soumita Hait, Ping Li, Haipeng Luo, Mengxiao Zhang,
• Abstract要約: ゲームにおける学習力学の最後の項目収束は、近年大きな注目を集めている。 我々は, t(-1/2) の終点収束は, バンディットフィードバックを持つゲームにおいて高い確率で達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 43.45624707071202
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t^(-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t^(-1/3) in expectation or t^(-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t^(-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.
• Abstract（参考訳）: ゲームにおける学習力学の最後の項目収束は、近年大きな注目を集めている。 Fiegel et al (2025) は、選択されたアクション対の損失のみが観測される2つのプレイヤーゼロサムゲームにおいて、二元性ギャップにおける平均点収束と最終点収束の分離を示す: t ラウンド後の最適 t^(-1/2) レートは標準のno-regret アルゴリズムによって前者に対して達成可能であるが、後者は期待されるときに t^(-1/3) よりも速く収束することができない。 しかし、嗜好学習など多くの実践的な環境では、プレイヤーは損失だけでなく、相手の行動も観察する。 このような追加情報は、最終段階の収束を早めることができるだろうか? この問題に対して, t^(-1/2) の終点収束が高い確率で達成可能であることを示す上で, 対数バリア正規化ゲームを用いて, その戦略を頻繁に更新するアルゴリズムを提案する。 シングルプレイヤーのケースであるマルチアームバンディットの標準解析がゲームへの一般化を阻害する基本的障害を特定し、それらを克服するための新しい分析を開発する。 実験により,本アルゴリズムは,本アルゴリズムの初歩的なベースラインや,反作用フィードバックを生かさない先行手法よりも早く収束することが確認された。 最後に、スキュー対称なゲーム行列を持つ特殊なケースであるデュエルバンディットについても改善した点に留意する。

関連論文リスト

• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback [46.50566806285207]
  ゼロサム行列ゲームにおいて繰り返しプレイやバンディットフィードバックで学習する問題について検討する。 プレイヤー間の通信なしに、最終項目のナッシュ均衡への収束を保証するアンカップリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-17T14:17:09Z)
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  大規模なゲームでは、非結合学習ダイナミクスの平均的な繰り返しを新しい非結合学習ダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示す。 我々の削減は、各プレイヤーの効用が自身の戦略と全ての対戦者の共同戦略の両方において線形であるゲームに適用される。
  論文  参考訳（メタデータ） (2025-06-04T00:24:14Z)
• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  ゲームにおける学習力学の非エルゴード収束は、理論と実践の両方において重要であるため、広く研究されている。 近年の研究では、最適乗算重み更新を含む学習力学の幅広いクラスが、任意に遅い最終項目収束を示すことが示されている。 OMWUは、同じクラスのゲームにおいて、その遅い最終点収束とは対照的に、$O(T-1/6)$est-iterate convergence rateを達成することを示す。
  論文  参考訳（メタデータ） (2025-03-04T17:49:24Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)
• Adaptively Perturbed Mirror Descent for Learning in Games [10.868347525353293]
  本稿では,ペイオフ関数の勾配が単調なゲームにおいて,ミラーDescent(MD)アルゴリズムに対するペイオフ摂動手法を提案する。 その結果,アルゴリズムの収束が著しく加速していることが判明した。
  論文  参考訳（メタデータ） (2023-05-26T04:02:54Z)
• No-regret learning for repeated non-cooperative games with lossy bandits [5.437709019435926]
  本研究では,長期的後悔の損失を最小限に抑えるために,プレイヤーの非同期オンライン学習戦略について検討する。 この論文は、損失帯域付きオンライングラディエントDescent(OGD-lb)と呼ばれる、新しい非回帰学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-14T05:02:56Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)

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

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