論文の概要: On Tractable $Φ$-Equilibria in Non-Concave Games

• arxiv url: http://arxiv.org/abs/2403.08171v2
• Date: Wed, 3 Jul 2024 00:26:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-04 19:54:15.955622
• Title: On Tractable $Φ$-Equilibria in Non-Concave Games
• Title（参考訳）: 非凹凸ゲームにおけるトラクタブル$$-平衡について
• Authors: Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng,
• Abstract要約: 非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。 また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
• 参考スコア（独自算出の注目度）: 53.212133025684224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While Online Gradient Descent and other no-regret learning procedures are known to efficiently converge to a coarse correlated equilibrium in games where each agent's utility is concave in their own strategy, this is not the case when utilities are non-concave -- a common scenario in machine learning applications involving strategies parameterized by deep neural networks, or when agents' utilities are computed by neural networks, or both. Non-concave games introduce significant game-theoretic and optimization challenges: (i) Nash equilibria may not exist; (ii) local Nash equilibria, though existing, are intractable; and (iii) mixed Nash, correlated, and coarse correlated equilibria generally have infinite support and are intractable. To sidestep these challenges, we revisit the classical solution concept of $\Phi$-equilibria introduced by Greenwald and Jafari [2003], which is guaranteed to exist for an arbitrary set of strategy modifications $\Phi$ even in non-concave games [Stoltz and Lugosi, 2007]. However, the tractability of $\Phi$-equilibria in such games remains elusive. In this paper, we initiate the study of tractable $\Phi$-equilibria in non-concave games and examine several natural families of strategy modifications. We show that when $\Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $\Phi$-equilibria. Additionally, we explore cases where $\Phi$ is infinite but consists of local modifications, showing that Online Gradient Descent can efficiently approximate $\Phi$-equilibria in non-trivial regimes.
• Abstract（参考訳）: Online Gradient Descentや他の非回帰学習手順は、各エージェントのユーティリティが自身の戦略で凹凸であるゲームにおいて、粗い相関均衡に効率的に収束することが知られているが、ユーティリティが非凹凸である場合(これは、ディープニューラルネットワークによってパラメータ化された戦略を含む機械学習アプリケーションで一般的なシナリオである)、エージェントのユーティリティがニューラルネットワークによって計算された場合、あるいはその両方で、そうではない。 非凹面ゲームは、重要なゲーム理論と最適化の課題をもたらす。 一 ナッシュ均衡が存在しないこと。 (ii)局所的なナッシュ均衡は存在するが、難解である。 3) 混合ナッシュ, 相関, 粗相関平衡は一般に無限に支持され, 難解である。 これらの課題を克服するために、Greenwald と Jafari [2003] が導入した $\Phi$-equilibria という古典的な解の概念を再考する。 しかし、そのようなゲームにおける$\Phi$-equilibriaのトラクタビリティは、いまだ解明されていない。 本稿では,非コンケーブゲームにおける抽出可能な$\Phi$-equilibriaの研究を開始し,戦略修正の自然ファミリーについて検討する。 我々は、$\Phi$が有限であるとき、対応する$\Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示した。 さらに、$\Phi$が無限だが局所的な修正から構成される場合についても検討し、非自明なレジームにおいてオンライングラディエント Descent が$\Phi$-equilibria を効率的に近似できることを示した。

関連論文リスト

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  非定常マルチエージェントシステムにおける平衡の学習について検討する。 単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
  論文  参考訳（メタデータ） (2023-06-12T23:48:24Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic Pricing [0.0]
  競技マルコフゲーム(MG)環境におけるナッシュ均衡学習について検討する。 我々は、近似的なナッシュ平衡を求めるための新しいモデルフリー手法を開発した。 我々は、特に動的価格領域において、近似的なナッシュ均衡を学習できることを実証する。
  論文  参考訳（メタデータ） (2022-07-13T19:27:07Z)
• Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
  状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。 我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。 我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
  論文  参考訳（メタデータ） (2022-02-08T20:09:47Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Convergence of Deep Fictitious Play for Stochastic Differential Games [6.875312133832078]
  最近提案された機械学習アルゴリズム、Deep fictitious Playは、大きな$N$非対称微分ゲームにおけるマルコフ的ナッシュ均衡を見つけるための、新しい効率的なツールを提供する。 架空のプレイの概念を取り入れることで、アルゴリズムはゲームを$N$のサブ最適化問題に分解する。 DFPに基づく戦略が$eps$-Nash均衡を形成することを示す。
  論文  参考訳（メタデータ） (2020-08-12T18:27:13Z)

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

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