論文の概要: Logarithmic Regret for Alternating Mirror Descent

• arxiv url: http://arxiv.org/abs/2611.05243v1
• Date: Tue, 03 Nov 2026 17:26:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-07 13:28:37.470261
• Title: Logarithmic Regret for Alternating Mirror Descent
• Title（参考訳）: 交互鏡用対数レグレット
• Abstract要約: AltOMD(AltOMD)は、ゼロサムゲームのための単純な学習ルールである。 2つのプレイヤーのゼロサム双線形ゲームに対するプレイヤーの外部後悔の和に縛られた$O(log(T))$後悔を示す。
• 参考スコア（独自算出の注目度）: 32.99582462172077
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained $O(T^{1/3})$ and $O(T^{1/5})$ regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether AltOMD achieves near-constant regret has remained an open question. In this paper we resolve the question of whether AltOMD achieves near-constant regret in the affirmative. In particular, we show an $O(log(T))$ regret bound on the sum of the players' external regrets for any two-player zero-sum bilinear game with compact convex strategy sets, under mild regularity assumptions on the regularizers. We verify that our assumptions hold for the negative entropy regularizer, thereby obtaining logarithmic regret for the alternating multiplicative weights updates algorithm. The regret bound also yields an $O(log(T)/T)$ duality gap bound for the averaged strategies.
• Abstract（参考訳）: 代替オンラインミラー降下(AltOMD)はゼロサムゲームのための単純な学習ルールであり、数値的および理論的に同時OMDを改善する。 以前の研究は、修正エネルギー関数に基づく解析を利用して、AltOMDに対して$O(T^{1/3})$と$O(T^{1/5})$後悔境界を得た。 しかし、AltOMDがほぼ確実な後悔を成し遂げたかどうかについては、未解決の問題が残っている。 本稿では,AltOMDが肯定的にほぼ一貫した後悔を達成できるかどうかを問う。 特に、コンパクト凸戦略セットを持つ任意の2プレーヤゼロサム双線型ゲームに対するプレイヤーの外部後悔の和に縛られた$O(log(T))$後悔を示す。 我々は, 負のエントロピー正則化器に対する仮定が成り立つことを検証し, 交互乗法重み更新アルゴリズムの対数的後悔を得る。 後悔境界はまた、平均化された戦略に対して$O(log(T)/T)$双対性ギャップを与える。

関連論文リスト

• A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games [0.7106986689736826]
  ステップサイズが一定であれば、一般ゲームにおいてO_n,d(1)$の個別後悔が得られることを示す。 我々の証明はフリッシュ (1967) の非構成的ネーター性論証に基づいているので、$(n,d)$-依存は暗黙的に残る。
  論文  参考訳（メタデータ） (2026-09-19T07:15:57Z)
• Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization [12.597979977402543]
  スワップ後悔は、非結合学習力学がマルチプレイヤー一般サムゲームにおける平衡に収束する速度を支配している。 我々は、すべてのプレイヤーが$O(nm2sqrtlog mlog T/T)$スワップ後悔を発生させるアンカップリング力学を構築する。
  論文  参考訳（メタデータ） (2026-08-04T18:58:51Z)
• 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)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)

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

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