論文の概要: Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents

• arxiv url: http://arxiv.org/abs/2611.07773v1
• Date: Thu, 05 Nov 2026 10:11:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 21:50:50.653235
• Title: Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents
• Title（参考訳）: 任意遅延のあるゲームにおける最適学習--自己プレーと対戦相手のためのベスト・オブ・ボトム・ワールド
• Abstract要約: 我々は,スムーズなゲーム上でのセルフプレイにおいて,最適な高速レートを得るための単一アルゴリズムであるマルチアンカー最適オンラインミラー Descent (MAO-OMD) を導入する。 これらの最適レートは、非遅延設定に対する標準ブラックボックス還元を用いて同時に取得できないことを示す。
• 参考スコア（独自算出の注目度）: 53.61453128371497
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study learning in zero-sum games with delayed feedback. We introduce Multi-Anchor Optimistic Online Mirror Descent (MAO-OMD), a single algorithm which obtains optimal fast rates in self-play on smooth games, while simultaneously maintaining minimax optimal guarantees against arbitrary opponents. In particular, in smooth zero-sum games with arbitrary and unknown feedback delays, MAO-OMD obtains $O(σ_{\max}+1)$ social and individual regrets when used by both players, where $σ_{\max}$ denotes the maximum number of outstanding gradients, while also guaranteeing minimax optimal $O(\sqrt{T+d_{\mathrm{tot}}})$ individual regret against arbitrary opponents, where $d_{\mathrm{tot}}$ is the total delay. Moreover, we show that these optimal rates cannot be obtained simultaneously using the standard black-box reduction to the undelayed setting. We also extend our results to multi-player games, and to games with player-dependent delay sequences.
• Abstract（参考訳）: ゼロサムゲームにおける学習を遅延フィードバックを用いて研究する。 我々は,スムーズなゲーム上での自己プレイにおける最適な高速レートを同時に獲得する単一アルゴリズムであるMulti-Anchor Optimistic Online Mirror Descent (MAO-OMD)を紹介する。 特に、任意のフィードバック遅延と未知のフィードバック遅延を持つ滑らかなゼロサムゲームにおいて、MAO-OMDは、両方のプレイヤーが使用するときの社会的および個人的後悔を$O(σ_{\max}+1)$で取得し、$σ_{\max}$は卓越した勾配の最大数を表す一方で、minimaxOptiimal $O(\sqrt{T+d_{\mathrm{tot}}})$ 反対相手に対する個人的後悔を$d_{\mathrm{tot}}$で保証する。 さらに,これらの最適レートは,非遅延設定に対する標準ブラックボックス削減を用いて同時に取得できないことを示す。 また、マルチプレイヤーゲームや、プレイヤー依存遅延シーケンスを持つゲームにも結果を拡張します。

関連論文リスト

• Minimax Last-Iterate Convergence in Matrix Games with Observed Actions [14.692647465985916]
  各ラウンドで高い確率で$widetildemathcalO(sqrtd/t)$の双対性ギャップを達成するアルゴリズムを開発する。 レートは標準帯域幅の下限と一致し、アクションの数とラウンド数の両方において最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2026-09-28T08:59:34Z)
• Multiplicative Optimism for Constant Regret in Games [29.477078788138154]
  乗法的最適回帰マッチング(英: multiplicatively Optimistic Regret Matching)は、有限一般ゲームにおける非結合学習規則である。 学習率の保護は、敵のユーティリティに直面して、$O(sqrtTlog d)$ regretを与える。
  論文  参考訳（メタデータ） (2026-09-18T16:38:29Z)
• Constant regret in general games via higher-order optimism [21.642749388029525]
  任意の$N$-playerの正規フォームゲームのすべてのプレイヤーが採用するアンカップリング学習アルゴリズムを導入し、このアルゴリズムは個々の後悔に対して$O(N3log2 K)を保証します。 提案アルゴリズムは、割引された$(N+1)$-th次予測器とエントロピー正規化を組み合わせた楽観的追従正規化リーダ(FTRL)の変種である。
  論文  参考訳（メタデータ） (2026-09-03T17:16:13Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。 我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
  論文  参考訳（メタデータ） (2025-10-20T00:45:47Z)
• Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games [60.871651115241406]
  ゼロサムゲームにおける理論と実践の間、何十年にもわたってかなりのシャズムが一階法によって浸食されてきた。 我々は、IREG-PRM$+$と呼ぶPRM$+$の新しいスケール不変かつパラメータフリーな変種を提案する。 ベンチマークゲームでは, PRM$+$と同等でありながら, 最適収束保証を$T-1/2$, $T-1$とする。
  論文  参考訳（メタデータ） (2025-10-06T00:33:20Z)
• Optimism Without Regularization: Constant Regret in Zero-Sum Games [33.767080029410764]
  同様の最適なレートが、正規化なしで達成可能であることを初めて示します。 我々は、オプティスティック・フィクティトゥス・プレイ(タイブレッシング・ルールを使用)が絶え間ない後悔しか得られない2つのストラテジー・ゲームについて証明する。
  論文  参考訳（メタデータ） (2025-06-20T04:10:51Z)
• Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer Games [121.50979258049135]
  我々は、すべてのプレイヤーが、時空不変の学習速度で我々のダイナミクスに従うとき、時間$T$までの時空二階パス長は、$O(log T)$で有界であることを示す。 提案する学習力学は, 直観的正規化学習と, 自己一致障壁を併用した新しい学習手法である。
  論文  参考訳（メタデータ） (2022-04-25T03:20:16Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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