論文の概要: Computational Lower Bounds for Regret Minimization in Normal-Form Games

• arxiv url: http://arxiv.org/abs/2411.01721v1
• Date: Mon, 04 Nov 2024 00:39:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 21:27:30.481076
• Title: Computational Lower Bounds for Regret Minimization in Normal-Form Games
• Title（参考訳）: 正規形式ゲームにおけるレギュレット最小化のための計算下界
• Authors: Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm,
• Abstract要約: 乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
• 参考スコア（独自算出の注目度）: 68.66209476382213
• License:
• Abstract: A celebrated connection in the interface of online learning and game theory establishes that players minimizing swap regret converge to correlated equilibria (CE) -- a seminal game-theoretic solution concept. Despite the long history of this problem and the renewed interest it has received in recent years, a basic question remains open: how many iterations are needed to approximate an equilibrium under the usual normal-form representation? In this paper, we provide evidence that existing learning algorithms, such as multiplicative weights update, are close to optimal. In particular, we prove lower bounds for the problem of computing a CE that can be expressed as a uniform mixture of $T$ product distributions -- namely, a uniform $T$-sparse CE; such lower bounds immediately circumscribe (computationally bounded) regret minimization algorithms in games. Our results are obtained in the algorithmic framework put forward by Kothari and Mehta (STOC 2018) in the context of computing Nash equilibria, which consists of the sum-of-squares (SoS) relaxation in conjunction with oracle access to a verification oracle; the goal in that framework is to lower bound either the degree of the SoS relaxation or the number of queries to the verification oracle. Here, we obtain two such hardness results, precluding computing i) uniform $\text{log }n$-sparse CE when $\epsilon =\text{poly}(1/\text{log }n)$ and ii) uniform $n^{1 - o(1)}$-sparse CE when $\epsilon = \text{poly}(1/n)$.
• Abstract（参考訳）: オンライン学習とゲーム理論のインターフェースにおける有望なつながりは、スワップ後悔を最小限に抑えるプレイヤーが相関平衡(CE)に収束することを証明している。 この問題の長い歴史と近年の新たな関心にもかかわらず、基本的な疑問は未解決のままである:通常の正規形式表現の下で平衡を近似するために、どれくらいのイテレーションが必要か? 本稿では,乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 特に、CE の計算問題に対する下界を$T$-sparse CE の均一な混合として表すことができ、そのような下界はゲームにおいて即時(計算的に有界な)後悔の最小化アルゴリズムを包含する。 我々は,コサリとメフタ (STOC 2018) が計算の文脈で行ったアルゴリズムの枠組みにおいて,検証オラクルへのオラクルアクセスと合わせて2乗の和(SoS)緩和からなる Nash equilibria が得られた。 ここでは、計算に先立って、そのような硬さの2つの結果を得る。 i) uniform $\text{log }n$-sparse CE when $\epsilon =\text{poly}(1/\text{log }n)$ and i) uniform $n^{1 - o(1)}$-sparse CE when $\epsilon = \text{poly}(1/n)$

関連論文リスト

• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces [29.29647282754262]
  我々は、ある仮説クラスに対して外部回帰アルゴリズムが存在しない場合、同じクラスに対して非スワップ回帰アルゴリズムが存在することも示している。 我々の減少は、あるゲームで非回帰学習が可能であるならば、このゲームは近似された平衡を持つ必要があることを意味する。
  論文  参考訳（メタデータ） (2023-10-30T17:50:29Z)
• 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)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Solving optimization problems with Blackwell approachability [31.29341288414507]
  Conic Blackwell Algorithm$+$ (CBA$+$) regret minimalr。 CBA$+$はBlackwellのアプローチ性に基づいており、$O(sqrtT)$ regretに達する。 CBA$+$に基づいて、凸凹サドル問題を解くための新しいパラメータフリーアルゴリズムSP-CBA$+$を導入する。
  論文  参考訳（メタデータ） (2022-02-24T18:19:21Z)
• 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)

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

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