論文の概要: Optimal Alternating Regret for Online Learning and Games
- arxiv url: http://arxiv.org/abs/2608.24731v1
- Date: Tue, 25 Aug 2026 15:41:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-26 14:09:35.082153
- Title: Optimal Alternating Regret for Online Learning and Games
- Title（参考訳）: オンライン学習とゲームのための最適代替レグレット
- Abstract要約: 我々は,オンライン線形最適化 (OLO) とオンライン凸最適化 (OCO) の両面において,ゲームにおける学習力学の交互化を動機とした,ミニマックス-最適交互後悔(minimax-optimal alternating regret)を解決した。
確率単純度 $_d$ 上の OLO に対して、任意の時間的地平線$T$ と一致する下界に対して定数である $O(log d)$ の繰り返し後悔を持つアルゴリズムを与える。
一般の$d$次元コンパクト凸集合上のOCOに対して、$O(dlog (1+T/d)$交互後悔を伴うアルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 13.57157968084561
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex $Δ_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a constant for any time horizon $T$, and a matching lower bound. Our constant regret bound significantly improves previous results with $O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with $O(\log d /T)$ convergence to Nash equilibria in two-player zero-sum games and $O(\log d /T)$ convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with $O(1/T)$ convergence to CCE in two-player general-sum games, while all prior works suffer additional $\log T$ factors. For general OCO over a $d$-dimensional compact convex set, we give an algorithm with $O(d\log (1+T/d))$ alternating regret, improving the previous best of $\widetilde{O}(d^{2/3}T^{1/3})$. We also prove a matching lower bound of $Ω(d\log (1+T/d))$, showing that the $Ω(\log T)$ factor is unavoidable.
- Abstract（参考訳）: 我々は,オンライン線形最適化 (OLO) とオンライン凸最適化 (OCO) の両面において,ゲームにおける学習力学の交互化を動機とした,ミニマックス-最適交互後悔(minimax-Optimating regret)を解決した。
確率単純度$Δ_d$ 上の OLO に対して、任意の時間的地平線$T$ と一致する下界に対して定数である$O(\log d)$交互後悔のアルゴリズムを与える。
O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]
その結果、2プレイヤゼロサムゲームにおけるナッシュ平衡への$O(\log d /T)$収束と、2プレイヤ一般サムゲームにおける粗相関平衡への$O(\log d /T)$収束との交互学習ダイナミクスが得られる。
これは、O(1/T)$CCEを2プレイヤーの一般サムゲームで収束させた最初の未結合の学習力学であり、全ての先行研究は追加の$\log T$因子を被る。
一般の$d$次元コンパクト凸集合上のOCOに対して、$O(d\log (1+T/d))$の交互後悔を伴うアルゴリズムを与え、以前の$\widetilde{O}(d^{2/3}T^{1/3})$の最高値を改善する。
また、$Ω(d\log (1+T/d))$の一致する下界を証明し、$Ω(\log T)$因子が避けられないことを示す。
関連論文リスト
- Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Scale-Invariant Fast Convergence in Games [67.02769061793619]
我々は,スケールフリーでもスケール不変でも,高速収束を実現する学習力学を開発した。
2プレーヤゼロサムゲームに対しては、$tildeO(A_mathrmdiff)$で有界な外部後悔を伴うスケールフリーかつスケール不変のダイナミクスが得られる。
マルチプレイヤーの汎用ゲームでは、過去の観測に基づいて観察された勾配をクリップする2倍のクリッピングと呼ばれる手法によって、スケールフリーの学習も可能となる。
論文 参考訳（メタデータ） (2026-02-12T11:57:20Z) - Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。
我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
論文 参考訳（メタデータ） (2025-10-20T00:45:47Z) - Faster Rates for No-Regret Learning in General Games via Cautious Optimism [46.462843198107144]
我々は,マルチプレイヤーの汎用ゲームにおいて,O(n, d log T)$per-playerの後悔を実現する最初の未結合学習アルゴリズムを確立する。
この結果は,Log-Regularized Lifted Optimistic FTRLで達成可能な$O(n, d log T)$ regretと比較して,$d$への依存を指数関数的に改善する。
論文 参考訳（メタデータ） (2025-03-31T17:25:33Z) - Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。
また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
論文 参考訳（メタデータ） (2025-02-24T20:20:06Z) - Alternating Regret for Online Convex Optimization [43.12477663757647]
連続Hedgeアルゴリズムは,任意の逆数$次元OCO問題に対して,$tildemathcalO(dfrac23Tfrac13)$の繰り返し後悔を実現することを示す。
例えば、Regret Matching 変種に対する$Omega(sqrtT)$ lower boundなどである。
論文 参考訳（メタデータ） (2025-02-18T04:32:52Z) - Corrupted Learning Dynamics in Games [62.73758165845971]
すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。
本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
論文 参考訳（メタデータ） (2024-12-10T02:23:44Z) - Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - Doubly Optimal No-Regret Learning in Monotone Games [10.760195409078591]
本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムを提案する。
このアルゴリズムは, 滑らかかつ凸な損失関数の下での対角的条件下での最適$O(sqrtT)$後悔と, (ii) 最適$O(frac1T)$最後の収束率をナッシュ平衡に達成する。
論文 参考訳（メタデータ） (2023-01-30T17:55:53Z) - Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer
Games [121.50979258049135]
我々は、すべてのプレイヤーが、時空不変の学習速度で我々のダイナミクスに従うとき、時間$T$までの時空二階パス長は、$O(log T)$で有界であることを示す。
提案する学習力学は, 直観的正規化学習と, 自己一致障壁を併用した新しい学習手法である。
論文 参考訳（メタデータ） (2022-04-25T03:20:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。