論文の概要: Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games

• arxiv url: http://arxiv.org/abs/2511.01852v2
• Date: Wed, 05 Nov 2025 18:50:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-06 13:56:26.178509
• Title: Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
• Title（参考訳）: 近位回帰と近位関連平衡--オンライン学習・ゲームのための新しいトラクタブル・ソリューション
• Authors: Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng,
• Abstract要約: 近位演算子に基づく新たな後悔の概念である近位後悔を導入し、外部とスワップ後悔の間に厳密に関係する。 古典的オンライングラディエントDescentアルゴリズムは,近位後悔に縛られた最適な$O(sqrtT)を達成している。 これは、オンライン学習とゲームにおける勾配降下の実験的に優れたパフォーマンスについて、新しい説明を提供する。
• 参考スコア（独自算出の注目度）: 60.981847057352695
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning and computation of equilibria are central problems in game theory, theory of computation, and artificial intelligence. In this work, we introduce proximal regret, a new notion of regret based on proximal operators that lies strictly between external and swap regret. When every player employs a no-proximal-regret algorithm in a general convex game, the empirical distribution of play converges to proximal correlated equilibria (PCE), a refinement of coarse correlated equilibria. Our framework unifies several emerging notions in online learning and game theory-such as gradient equilibrium and semicoarse correlated equilibrium-and introduces new ones. Our main result shows that the classic Online Gradient Descent (GD) algorithm achieves an optimal $O(\sqrt{T})$ bound on proximal regret, revealing that GD, without modification, minimizes a stronger regret notion than external regret. This provides a new explanation for the empirically superior performance of gradient descent in online learning and games. We further extend our analysis to Mirror Descent in the Bregman setting and to Optimistic Gradient Descent, which yields faster convergence in smooth convex games.
• Abstract（参考訳）: 平衡の学習と計算はゲーム理論、計算理論、人工知能において中心的な問題である。 本稿では, 近位演算子に基づく新たな後悔の概念である近位後悔(proximal regret)を導入する。 一般凸ゲームにおいて、全てのプレイヤーが非近位回帰アルゴリズムを用いる場合、プレイの実証的な分布は、粗い相関平衡の洗練である近位平衡(PCE)に収束する。 オンライン学習とゲーム理論における新たな概念 - 勾配平衡や半粗相関平衡など - を統一し, 新たな概念を導入する。 本研究の主な成果は,従来のオンライングラディエント・Descent (GD) アルゴリズムが最良な$O(\sqrt{T})$を近位後悔に縛り付けることを示し,GDが修正することなく,外部後悔よりも強い後悔の概念を最小化することを示した。 これは、オンライン学習とゲームにおける勾配降下の実験的に優れたパフォーマンスについて、新しい説明を提供する。 さらに、ブレグマン設定におけるミラー・ディクセントや、滑らかな凸ゲームにおいてより高速な収束をもたらす最適勾配・ディクセントまで分析を拡大する。

関連論文リスト

• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [61.6869963435955]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• 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)
• Online Multiobjective Minimax Optimization and Applications [14.699969822572308]
  本稿では,適応的な対戦相手が新しいゲームを導入する,シンプルだが汎用的なオンライン学習フレームワークを提案する。 学習者のゴールは、累積ベクトル値損失の最大座標を最小化することである。 対戦相手がまず行動を発表しなければならない設定と競合する簡単なアルゴリズムを提供する。 最適なアルゴリズムと境界を回復して、外部の後悔、内部の後悔、適応的な後悔、多集団の後悔、その後の後悔、睡眠専門家の設定における後悔の概念を最小化できます。
  論文  参考訳（メタデータ） (2021-08-09T06:52:08Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)

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

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