論文の概要: Barriers to Welfare Maximization with No-Regret Learning

• arxiv url: http://arxiv.org/abs/2411.01720v1
• Date: Mon, 04 Nov 2024 00:34:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 21:27:31.197501
• Title: Barriers to Welfare Maximization with No-Regret Learning
• Title（参考訳）: No-Regret Learning による福祉最大化への障壁
• Authors: Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm,
• Abstract要約: 我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
• 参考スコア（独自算出の注目度）: 68.66209476382213
• License:
• Abstract: A celebrated result in the interface of online learning and game theory guarantees that the repeated interaction of no-regret players leads to a coarse correlated equilibrium (CCE) -- a natural game-theoretic solution concept. Despite the rich history of this foundational problem and the tremendous interest it has received in recent years, a basic question still remains open: how many iterations are needed for no-regret players to approximate an equilibrium? In this paper, we establish the first computational lower bounds for that problem in two-player (general-sum) games under the constraint that the CCE reached approximates the optimal social welfare (or some other natural objective). From a technical standpoint, our approach revolves around proving lower bounds for computing a near-optimal $T$-sparse CCE -- a mixture of $T$ product distributions, thereby circumscribing the iteration complexity of no-regret learning even in the centralized model of computation. Our proof proceeds by extending a classical reduction of Gilboa and Zemel [1989] for optimal Nash to sparse (approximate) CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in polynomial time. Moreover, we strengthen our hardness results to apply in the low-precision regime as well via the planted clique conjecture.
• Abstract（参考訳）: オンライン学習とゲーム理論のインターフェースにおける有望な結果は、非相対的なプレイヤーの繰り返しの相互作用が、自然なゲーム理論のソリューション概念である粗い相関均衡(CCE)につながることを保証している。 この根本的問題の豊富な歴史と近年の大きな関心にもかかわらず、基本的な疑問はまだ未解決のままである。 本稿では,CCEが最適社会福祉(あるいはいくつかの自然目的)に到達した制約の下で,この問題に対する最初の計算下界を確立する。 技術的観点から、我々のアプローチは、ほぼ最適の$T$-sparse CCE -- 製品分布の混合である$T$-sparse CCE -- を計算するための低いバウンダリの証明を中心に展開している。 我々の証明は、最適ナッシュをスパース(近似) CCE に拡張するために、Gilboa と Zemel [1989] を古典的に還元する。 特に,最大傾きの不適応性は多項式時間における非自明なスパーシリティを達成できないことを示す。 さらに、我々は、植込みクリッド予想(英語版)を通して、低精度体制にも適用できるように、硬度結果を強化する。

関連論文リスト

• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
  論文  参考訳（メタデータ） (2024-11-04T00:39:52Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces [29.29647282754262]
  我々は、ある仮説クラスに対して外部回帰アルゴリズムが存在しない場合、同じクラスに対して非スワップ回帰アルゴリズムが存在することも示している。 我々の減少は、あるゲームで非回帰学習が可能であるならば、このゲームは近似された平衡を持つ必要があることを意味する。
  論文  参考訳（メタデータ） (2023-10-30T17:50:29Z)
• 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)
• 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)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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