論文の概要: No-Regret Learning in Games is Turing Complete

• arxiv url: http://arxiv.org/abs/2202.11871v1
• Date: Thu, 24 Feb 2022 02:37:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-25 18:06:11.339745
• Title: No-Regret Learning in Games is Turing Complete
• Title（参考訳）: ゲームにおける非回帰学習はチューリング完了
• Authors: Gabriel P. Andrade, Rafael Frongillo, Georgios Piliouras
• Abstract要約: 行列ゲーム上での複製子力学のチューリング完全性は、最も単純な設定の1つである。 この結果から,ゲームにおける学習アルゴリズムにおける到達可能性問題の非効率性が示唆され,特に平衡収束が決定される。
• 参考スコア（独自算出の注目度）: 33.03065693224728
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Games are natural models for multi-agent machine learning settings, such as generative adversarial networks (GANs). The desirable outcomes from algorithmic interactions in these games are encoded as game theoretic equilibrium concepts, e.g. Nash and coarse correlated equilibria. As directly computing an equilibrium is typically impractical, one often aims to design learning algorithms that iteratively converge to equilibria. A growing body of negative results casts doubt on this goal, from non-convergence to chaotic and even arbitrary behaviour. In this paper we add a strong negative result to this list: learning in games is Turing complete. Specifically, we prove Turing completeness of the replicator dynamic on matrix games, one of the simplest possible settings. Our results imply the undecicability of reachability problems for learning algorithms in games, a special case of which is determining equilibrium convergence.
• Abstract（参考訳）: ゲームは、gans(generative adversarial networks)のようなマルチエージェント機械学習の設定のための自然なモデルである。 これらのゲームにおけるアルゴリズム的相互作用の望ましい結果は、例えばナッシュや粗い相関平衡といったゲーム理論平衡の概念として符号化される。 平衡を直接計算することは一般的に非現実的であるので、反復的に平衡に収束する学習アルゴリズムを設計することを目指すことが多い。 ネガティブな結果の増大は、非収束性からカオス的、さらには任意の行動に至るまで、この目標に疑問を呈する。 本稿では,このリストに対して強い否定的な結果を与える。ゲームにおける学習はチューリング完全である。 具体的には、最も単純な設定の1つであるマトリックスゲームにおけるレプリケータの動的チューリング完全性を証明する。 この結果から,ゲームにおける学習アルゴリズムにおける到達可能性問題の非効率性が示唆され,特に平衡収束が決定される。

関連論文リスト

• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。 本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
  論文  参考訳（メタデータ） (2024-01-10T12:56:24Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Multiplayer Performative Prediction: Learning in Decision-Dependent Games [18.386569111954213]
  本稿では,マルチプレイヤー演奏予測のための新たなゲーム理論の枠組みを定式化する。 我々は、(i)パフォーマンス的に安定な平衡と(ii)ゲームのナッシュ平衡という、2つの異なる解の概念に焦点を当てる。 軽微な仮定の下では、様々なアルゴリズムにより、性能的に安定な平衡を効率的に見つけることができることを示す。
  論文  参考訳（メタデータ） (2022-01-10T15:31:10Z)
• 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)
• Learning in Matrix Games can be Arbitrarily Complex [24.6667169480096]
  本稿では,任意の動的系を近似できるレプリケータダイナミクスが十分に豊富であることを示した。 本研究では,lonrenz dynamicsの有名なストレンジアトラクタをレプリケータダイナミクスが効果的に再現できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T00:41:35Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。 厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。 この結果は,学習過程の結果を予測する上で重要な意味を持つ。
  論文  参考訳（メタデータ） (2020-10-19T13:49:06Z)

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

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