論文の概要: Tractable Local Equilibria in Non-Concave Games

• arxiv url: http://arxiv.org/abs/2403.08171v1
• Date: Wed, 13 Mar 2024 01:51:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-14 15:49:49.044930
• Title: Tractable Local Equilibria in Non-Concave Games
• Title（参考訳）: 非コンケーブゲームにおけるトラクタブルな局所平衡
• Authors: Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng
• Abstract要約: オンライングラディエントDescentとノンレグレット学習は,非コンケーブゲームにおける粗相関平衡に効率よく収束することを示した。 非凹面ゲームにおいて局所的なナッシュ均衡を一般化する、$(varepsilon, Phi(delta))$-local equilibriumと呼ばれる新しい解の概念を提案する。
• 参考スコア（独自算出の注目度）: 57.088421626355455
• 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 coarse correlated equilibrium in games where each agent's utility is concave in their own strategy, this is not the case when the utilities are non-concave, a situation that is common in machine learning applications where the agents' strategies are parameterized by deep neural networks, or the agents' utilities are computed by a neural network, or both. Indeed, non-concave games present a host of game-theoretic and optimization challenges: (i) Nash equilibria may fail to exist; (ii) local Nash equilibria exist but are intractable; and (iii) mixed Nash, correlated, and coarse correlated equilibria have infinite support in general, and are intractable. To sidestep these challenges we propose a new solution concept, termed $(\varepsilon, \Phi(\delta))$-local equilibrium, which generalizes local Nash equilibrium in non-concave games, as well as (coarse) correlated equilibrium in concave games. Importantly, we show that two instantiations of this solution concept capture the convergence guarantees of Online Gradient Descent and no-regret learning, which we show efficiently converge to this type of equilibrium in non-concave games with smooth utilities.
• Abstract（参考訳）: オンライングラディエントDescentやその他の非回帰学習手順は、各エージェントのユーティリティが自身の戦略で凹むゲームにおいて、粗い相関均衡に効率よく収束することが知られているが、ユーティリティが非凹地である場合、エージェントの戦略がディープニューラルネットワークによってパラメータ化される機械学習アプリケーションで一般的な状況、またはエージェントのユーティリティがニューラルネットワークによって計算される場合、またはその両方においてそうではない。 実際、非コンケーブゲームには、ゲーム理論と最適化の課題が数多く存在する。 一 ナッシュ均衡が存在しないこと。 (ii)局所的なナッシュ均衡は存在するが、難解である。 三 混合ナッシュ、相関、粗相関平衡は一般に無限に支持され、難解である。 これらの課題を克服するために、我々は$(\varepsilon, \Phi(\delta))$-local equilibriumと呼ばれる新しい解の概念を提案し、これは非凹面ゲームにおいて局所的なナッシュ均衡を一般化し、また、凹面ゲームにおいて(粗い)相関平衡を一般化する。 重要なことは、このソリューションの概念の2つのインスタンス化が、オンライングラディエント・ディクエンスと非レグレット学習の収束保証を捉えており、スムーズなユーティリティを持つ非コンケーブゲームにおいて、このタイプの平衡に効率的に収束していることである。

関連論文リスト

• 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)

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

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