論文の概要: Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

• arxiv url: http://arxiv.org/abs/2609.34656v1
• Date: Mon, 28 Sep 2026 08:59:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 11:32:42.922344
• Title: Minimax Last-Iterate Convergence in Matrix Games with Observed Actions
• Title（参考訳）: 観測行動を伴うマトリックスゲームにおける極小Iterate Convergence
• Abstract要約: 各ラウンドで高い確率で$widetildemathcalO(sqrtd/t)$の双対性ギャップを達成するアルゴリズムを開発する。 レートは標準帯域幅の下限と一致し、アクションの数とラウンド数の両方において最小限の最適性を確立する。
• 参考スコア（独自算出の注目度）: 14.692647465985916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t$. This improves the dimension dependence of the best previously known guarantee by a factor of $d^{3/2}$. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only $\mathcal{O}(d)$ time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.
• Abstract（参考訳）: 未知の2プレーヤゼロサム行列ゲームにおいて,バンド利得フィードバックを伴い,対戦動作を観測し,最終項目収束について検討した。 プレイヤー当たり$d$アクションを持つゲームに対しては、高い確率で$\widetilde{\mathcal{O}}(\sqrt{d/t})$の双対性ギャップを達成するアルゴリズムを各ラウンド$t$で同時に開発する。 これにより、最も既知の保証の次元依存性を$d^{3/2}$の係数で改善する。 速度は標準帯域幅の下限と一致し、作用数とラウンド数の両方において最小限の最適性を確立する。 このアルゴリズムは計算効率が良く、ラウンド当たりの時間とメモリは$\mathcal{O}(d)$である。 我々の技術的貢献は、アダプティブ平均化と補正指数重みの合同設計であり、推定分散を吸収し、位相長を束縛する潜在的な議論である。

関連論文リスト

• Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions [43.45624707071202]
  ゲームにおける学習力学の最後の項目収束は、近年大きな注目を集めている。 我々は, t(-1/2) の終点収束は, バンディットフィードバックを持つゲームにおいて高い確率で達成可能であることを示す。
  論文  参考訳（メタデータ） (2026-05-10T06:23:19Z)
• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback [46.50566806285207]
  ゼロサム行列ゲームにおいて繰り返しプレイやバンディットフィードバックで学習する問題について検討する。 プレイヤー間の通信なしに、最終項目のナッシュ均衡への収束を保証するアンカップリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-17T14:17:09Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。 我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
  論文  参考訳（メタデータ） (2025-10-20T00:45:47Z)
• Two-Player Zero-Sum Games with Bandit Feedback [6.66618805642802]
  本研究では,行プレーヤが敵列プレーヤに対する報酬を最大化することを目的とした2プレイヤーゼロサムゲームについて検討する。 本研究では,Explore-Then-Commitフレームワークに基づく3つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-17T13:46:32Z)
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  大規模なゲームでは、非結合学習ダイナミクスの平均的な繰り返しを新しい非結合学習ダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示す。 我々の削減は、各プレイヤーの効用が自身の戦略と全ての対戦者の共同戦略の両方において線形であるゲームに適用される。
  論文  参考訳（メタデータ） (2025-06-04T00:24:14Z)
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• 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)

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

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