論文の概要: Swap Regret Minimization Through Response-Based Approachability

• arxiv url: http://arxiv.org/abs/2602.06264v1
• Date: Thu, 05 Feb 2026 23:43:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.158614
• Title: Swap Regret Minimization Through Response-Based Approachability
• Title（参考訳）: 応答に基づくアプローチ性によるスワップレグレスト最小化
• Authors: Ioannis Anagnostides, Gabriele Farina, Maxwell Fishelson, Haipeng Luo, Jon Schneider,
• Abstract要約: オンライン最適化において,スワップ後悔という異なる概念を最小化することの問題点を考察する。 我々は、一般凸集合に対して$O(d3/2 sqrtT)$リニアスワップ後悔を保証し、集合が中央対称であるときに$O(d sqrtT)$を保証し、より単純で効率的なアルゴリズムを開発する。
• 参考スコア（独自算出の注目度）: 66.39400409563976
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of minimizing different notions of swap regret in online optimization. These forms of regret are tightly connected to correlated equilibrium concepts in games, and have been more recently shown to guarantee non-manipulability against strategic adversaries. The only computationally efficient algorithm for minimizing linear swap regret over a general convex set in $\mathbb{R}^d$ was developed recently by Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '25). However, it incurs a highly suboptimal regret bound of $Ω(d^4 \sqrt{T})$ and also relies on computationally intensive calls to the ellipsoid algorithm at each iteration. In this paper, we develop a significantly simpler, computationally efficient algorithm that guarantees $O(d^{3/2} \sqrt{T})$ linear swap regret for a general convex set and $O(d \sqrt{T})$ when the set is centrally symmetric. Our approach leverages the powerful response-based approachability framework of Bernstein and Shimkin (JMLR '15) -- previously overlooked in the line of work on swap regret minimization -- combined with geometric preconditioning via the John ellipsoid. Our algorithm simultaneously minimizes profile swap regret, which was recently shown to guarantee non-manipulability. Moreover, we establish a matching information-theoretic lower bound: any learner must incur in expectation $Ω(d \sqrt{T})$ linear swap regret for large enough $T$, even when the set is centrally symmetric. This also shows that the classic algorithm of Gordon, Greenwald, and Marks (ICML '08) is existentially optimal for minimizing linear swap regret, although it is computationally inefficient. Finally, we extend our approach to minimize regret with respect to the set of swap deviations with polynomial dimension, unifying and strengthening recent results in equilibrium computation and online learning.
• Abstract（参考訳）: オンライン最適化において,スワップ後悔という異なる概念を最小化することの問題点を考察する。 これらの後悔の形態はゲームにおける相関平衡概念と密接に結びついており、より最近では戦略的敵に対する非マニピュラビリティを保証することが示されている。 $\mathbb{R}^d$ の一般凸集合に対する線形スワップ後悔を最小化する唯一の計算効率のアルゴリズムは、最近ダスカラキス、ファリーナ、フィッシュソン、ピピス、シュナイダーによって開発された(STOC '25)。 しかし、これは$Ω(d^4 \sqrt{T})$の超最適後悔境界を生じさせ、また各反復における楕円体アルゴリズムへの計算集約的な呼び出しにも依存する。 本稿では,一般凸集合に対して$O(d^{3/2} \sqrt{T})$リニアスワップ後悔と,集合が中央対称である場合に$O(d \sqrt{T})$を保証し,より単純で効率的なアルゴリズムを開発する。 我々のアプローチは、バーンスタインとシムキンの強力な応答に基づくアプローチ可能性フレームワーク(JMLR '15)を利用します。 我々のアルゴリズムは、最近非マニピュラビリティを保証することが示されているプロファイルスワップ後悔を同時に最小化する。 さらに、一致した情報理論の下界を確立する:任意の学習者は、集合が中心対称である場合でも、十分大きな$T$に対して$Ω(d \sqrt{T})$リニアスワップ後悔を引き起こす必要がある。 これはまた、Gordon, Greenwald, Marks (ICML '08) の古典的アルゴリズムが、計算的に非効率であるにもかかわらず、線形スワップ後悔を最小限に抑えるのに、実在的に最適であることを示している。 最後に、多項式次元のスワップ偏差の集合に対する後悔を最小限に抑え、平衡計算とオンライン学習の最近の結果を統一し、強化するアプローチを拡張した。

関連論文リスト

• Full Swap Regret and Discretized Calibration [18.944031222413294]
  構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。 我々は、Emphfullスワップリ後悔の最小化という新しいオンライン学習問題を導入する また、これらのツールをオンライン予測問題に適用し、校正誤差を補正する。
  論文  参考訳（メタデータ） (2025-02-13T13:49:52Z)
• Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
  Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。 一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
  論文  参考訳（メタデータ） (2024-06-10T23:23:52Z)
• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

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

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