論文の概要: From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces

• arxiv url: http://arxiv.org/abs/2310.19786v4
• Date: Mon, 24 Feb 2025 02:58:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:48:56.750610
• Title: From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces
• Title（参考訳）: 外部からスワップレグレット2.0: 大規模アクションスペースの効率的な削減と曖昧な対応
• Authors: Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich,
• Abstract要約: 我々は、ある仮説クラスに対して外部回帰アルゴリズムが存在しない場合、同じクラスに対して非スワップ回帰アルゴリズムが存在することも示している。 我々の減少は、あるゲームで非回帰学習が可能であるならば、このゲームは近似された平衡を持つ必要があることを意味する。
• 参考スコア（独自算出の注目度）: 26.81775688975904
• License:
• Abstract: We provide a novel reduction from swap-regret minimization to external-regret minimization, which improves upon the classical reductions of Blum-Mansour [BM07] and Stolz-Lugosi [SL05] in that it does not require finiteness of the space of actions. We show that, whenever there exists a no-external-regret algorithm for some hypothesis class, there must also exist a no-swap-regret algorithm for that same class. For the problem of learning with expert advice, our result implies that it is possible to guarantee that the swap regret is bounded by {\epsilon} after $\log(N)^{O(1/\epsilon)}$ rounds and with $O(N)$ per iteration complexity, where $N$ is the number of experts, while the classical reductions of Blum-Mansour and Stolz-Lugosi require $O(N/\epsilon^2)$ rounds and at least $\Omega(N^2)$ per iteration complexity. Our result comes with an associated lower bound, which -- in contrast to that in [BM07] -- holds for oblivious and $\ell_1$-constrained adversaries and learners that can employ distributions over experts, showing that the number of rounds must be $\tilde\Omega(N/\epsilon^2)$ or exponential in $1/\epsilon$. Our reduction implies that, if no-regret learning is possible in some game, then this game must have approximate correlated equilibria, of arbitrarily good approximation. This strengthens the folklore implication of no-regret learning that approximate coarse correlated equilibria exist. Importantly, it provides a sufficient condition for the existence of correlated equilibrium which vastly extends the requirement that the action set is finite, thus answering a question left open by [DG22; Ass+23]. Moreover, it answers several outstanding questions about equilibrium computation and learning in games.
• Abstract（参考訳）: 我々は,スワップ・リグレットの最小化から外部リグレットの最小化への新たな削減を提案し,動作空間の有限性を必要としない点において,Blum-Mansour [BM07] と Stolz-Lugosi (SL05) の古典的縮小を改善する。 我々は、ある仮説クラスに対して外部回帰アルゴリズムが存在しない場合、同じクラスに対して非スワップ回帰アルゴリズムが存在することも示している。 専門家のアドバイスで学ぶことの問題は、スワップ後悔が$\log(N)^{O(1/\epsilon)} のラウンドと$O(N)$の反復複雑性の後に {\epsilon} で束縛されることを保証し、そこでは$N$は専門家の数であり、古典的な Blum-Mansour と Stolz-Lugosi の還元には$O(N/\epsilon^2) のラウンドと少なくとも$\Omega(N^2) のラウンドが必要である。 私たちの結果は、[BM07] のそれとは対照的に、関連する下限が伴うもので、暗黙的かつ$\ell_1$-制約された敵と学習者に対して成り立ち、専門家よりも分布を利用でき、ラウンドの数は$\tilde\Omega(N/\epsilon^2)$または $1/\epsilon$で指数関数でなければならないことを示す。 我々の減少は、あるゲームで非回帰学習が可能であるならば、このゲームは任意によい近似の近似平衡を持つ必要があることを意味する。 このことは、粗い相関平衡がほぼ存在するという非回帰学習の民俗的含意を強化する。 重要なことに、これは相関平衡の存在に対して十分条件を与え、これは作用集合が有限であるという要件を大きく拡張し、[DG22; Ass+23] で残された疑問に答える。 さらに、ゲームにおける平衡計算と学習に関するいくつかの卓越した疑問に答える。

関連論文リスト

• Alternating Regret for Online Convex Optimization [43.12477663757647]
  連続Hedgeアルゴリズムは,任意の逆数$次元OCO問題に対して,$tildemathcalO(dfrac23Tfrac13)$の繰り返し後悔を実現することを示す。 例えば、Regret Matching 変種に対する$Omega(sqrtT)$ lower boundなどである。
  論文  参考訳（メタデータ） (2025-02-18T04:32:52Z)
• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
  論文  参考訳（メタデータ） (2024-11-04T00:39:52Z)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
  Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。 一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
  論文  参考訳（メタデータ） (2024-06-10T23:23:52Z)
• Fast swap regret minimization and applications to approximate correlated equilibria [20.047624953965965]
  任意の定数$varepsilon>0$に対して、我々のアルゴリズムは$varepsilon T$-swap regretを$T = Mathsfpolylog(n)$ roundsで取得する。 我々のアルゴリズムは$varepsilon$に指数関数的依存を持つが、我々は一致する新しい下界を証明している。
  論文  参考訳（メタデータ） (2023-10-30T15:35:24Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• 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)
• No Discounted-Regret Learning in Adversarial Bandits with Delays [40.670563413892154]
  アルゴリズムが「割引なし」の場合、予想される遊びの割引エルゴジック分布が粗相関平衡(CCE)の集合に収束することを示した。 ゼロサムゲームでは、Nash平衡のセットに収束する割引エルゴディック平均のプレイには、ディスカウントレグレットが十分ではないことを示します。
  論文  参考訳（メタデータ） (2021-03-08T05:15:31Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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