論文の概要: No-regret learning and mixed Nash equilibria: They do not mix

• arxiv url: http://arxiv.org/abs/2010.09514v2
• Date: Tue, 20 Oct 2020 06:15:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 23:27:38.696146
• Title: No-regret learning and mixed Nash equilibria: They do not mix
• Title（参考訳）: no-regret learning と mix nash equilibria: 混合しない
• Authors: Lampros Flokas and Emmanouil-Vasileios Vlatakis-Gkaragkounis and Thanasis Lianeas and Panayotis Mertikopoulos and Georgios Piliouras
• Abstract要約: 我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。 厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。 この結果は,学習過程の結果を予測する上で重要な意味を持つ。
• 参考スコア（独自算出の注目度）: 64.37511607254115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding the behavior of no-regret dynamics in general $N$-player games is a fundamental question in online learning and game theory. A folk result in the field states that, in finite games, the empirical frequency of play under no-regret learning converges to the game's set of coarse correlated equilibria. By contrast, our understanding of how the day-to-day behavior of the dynamics correlates to the game's Nash equilibria is much more limited, and only partial results are known for certain classes of games (such as zero-sum or congestion games). In this paper, we study the dynamics of "follow-the-regularized-leader" (FTRL), arguably the most well-studied class of no-regret dynamics, and we establish a sweeping negative result showing that the notion of mixed Nash equilibrium is antithetical to no-regret learning. Specifically, we show that any Nash equilibrium which is not strict (in that every player has a unique best response) cannot be stable and attracting under the dynamics of FTRL. This result has significant implications for predicting the outcome of a learning process as it shows unequivocally that only strict (and hence, pure) Nash equilibria can emerge as stable limit points thereof.
• Abstract（参考訳）: 一般の$N$-playerゲームにおけるノンレグレットダイナミクスの振る舞いを理解することは、オンライン学習とゲーム理論における基本的な問題である。 フィールドにおける民間の結果は、有限ゲームにおいて、非回帰学習下のプレイの経験的頻度がゲームの粗い平衡の集合に収束することを示している。 対照的に、ダイナミクスの日々の振る舞いがゲームのナッシュ均衡とどのように相関しているかについての我々の理解はより限定的であり、特定のクラスのゲーム(ゼロサムゲームや混雑ゲームなど)で部分的な結果のみが知られている。 本稿では,no-regretダイナミクスの最もよく研究されているクラスである"after-the-regularized-leader"(ftrl)のダイナミクスについて検討し,混合nash平衡の概念がno-regret学習に対して反理論的であることを示す包括的な負の結果を確立した。 具体的には、厳密でない任意のナッシュ均衡(全てのプレイヤーが一意の最良の応答を持つ)は安定であり、FTRLの力学の下で引き寄せることができないことを示す。 この結果は学習プロセスの結果を予測する上で重要な意味を持ち、厳密な(従って純粋な)nash平衡のみがその安定な極限点として現れることは明白である。

関連論文リスト

• No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes [11.846329468283583]
  本稿では,ブラックボックスゲームにおける学習の課題について検討する。 我々はガウス過程を利用してそのようなゲームの平衡を同定する非回帰学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-05-14T04:58:23Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。 また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
  論文  参考訳（メタデータ） (2024-03-13T01:51:30Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  非定常マルチエージェントシステムにおける平衡の学習について検討する。 単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
  論文  参考訳（メタデータ） (2023-06-12T23:48:24Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。 この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。 これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
  論文  参考訳（メタデータ） (2023-01-22T16:54:06Z)
• Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Games [51.90475640044073]
  本研究では,2プレイヤゼロサムゲームにおける最適応答戦略の交互化として,対戦訓練について検討する。 一方、ゲームのユニークな純粋なナッシュ均衡が存在し、確実に堅牢である。
  論文  参考訳（メタデータ） (2022-10-23T03:21:01Z)
• Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics [28.815822236291392]
  ゲーム力学が$epsilon$-Nash平衡に収束できないことを示す。 また、$epsilon$-approximate Nash equilibriaに対してより強い結果を示す。
  論文  参考訳（メタデータ） (2022-03-26T18:27:40Z)
• No-Regret Learning in Games is Turing Complete [33.03065693224728]
  行列ゲーム上での複製子力学のチューリング完全性は、最も単純な設定の1つである。 この結果から,ゲームにおける学習アルゴリズムにおける到達可能性問題の非効率性が示唆され,特に平衡収束が決定される。
  論文  参考訳（メタデータ） (2022-02-24T02:37:50Z)
• Multiplayer Performative Prediction: Learning in Decision-Dependent Games [18.386569111954213]
  本稿では,マルチプレイヤー演奏予測のための新たなゲーム理論の枠組みを定式化する。 我々は、(i)パフォーマンス的に安定な平衡と(ii)ゲームのナッシュ平衡という、2つの異なる解の概念に焦点を当てる。 軽微な仮定の下では、様々なアルゴリズムにより、性能的に安定な平衡を効率的に見つけることができることを示す。
  論文  参考訳（メタデータ） (2022-01-10T15:31:10Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information [32.384868685390906]
  一般Nプレイヤーゲームにおける非回帰学習のナッシュ平衡収束特性について検討する。 ナッシュ平衡の安定性と支持との包括的な等価性を確立します。 ゲームにおける非学習の日々の行動を予測するための明確な洗練基準を提供する。
  論文  参考訳（メタデータ） (2021-01-12T18:55:11Z)

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

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