論文の概要: 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つのインスタンス化が、オンライングラディエント・ディクエンスと非レグレット学習の収束保証を捉えており、スムーズなユーティリティを持つ非コンケーブゲームにおいて、このタイプの平衡に効率的に収束していることである。
関連論文リスト
- Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale
Algorithm Under Weak Reachability [13.932957324139672]
我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。
従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。
我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
論文 参考訳(メタデータ) (2023-12-13T09:31:30Z) - Bayes correlated equilibria and no-regret dynamics [9.89901717499058]
本稿では,不完全情報を持つゲームの基本モデルであるベイズゲームに対する平衡概念について検討する。
我々は,各プレイヤーのプライベート情報を収集し,関連するレコメンデーションをプレイヤーに送信する仲介者によって実現可能なコミュニケーション均衡に焦点を当てる。
本稿では,非直交スワップ後悔を線形上界で最小化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-11T06:22:51Z) - Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。
この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。
これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
論文 参考訳(メタデータ) (2023-01-22T16:54:06Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳(メタデータ) (2022-11-29T05:16:41Z) - How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in
Urban Driving Games [64.71476526716668]
我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。
我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。
提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
論文 参考訳(メタデータ) (2022-10-24T09:32:40Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳(メタデータ) (2022-08-22T08:31:46Z) - Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。
この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。
我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
論文 参考訳(メタデータ) (2022-08-03T16:41:01Z) - 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) - Survival of the strictest: Stable and unstable equilibria under
regularized learning with partial information [32.384868685390906]
一般Nプレイヤーゲームにおける非回帰学習のナッシュ平衡収束特性について検討する。
ナッシュ平衡の安定性と支持との包括的な等価性を確立します。
ゲームにおける非学習の日々の行動を予測するための明確な洗練基準を提供する。
論文 参考訳(メタデータ) (2021-01-12T18:55:11Z) - On Information Asymmetry in Competitive Multi-Agent Reinforcement
Learning: Convergence and Optimality [78.76529463321374]
協調的でない2つのQ-ラーニングエージェントの相互作用システムについて検討する。
この情報非対称性は、集団学習の安定した結果をもたらす可能性があることを示す。
論文 参考訳(メタデータ) (2020-10-21T11:19:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。