論文の概要: The Complexity of Markov Equilibrium in Stochastic Games

• arxiv url: http://arxiv.org/abs/2204.03991v1
• Date: Fri, 8 Apr 2022 10:51:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-11 14:07:40.067716
• Title: The Complexity of Markov Equilibrium in Stochastic Games
• Title（参考訳）: 確率ゲームにおけるマルコフ平衡の複雑さ
• Authors: Constantinos Daskalakis and Noah Golowich and Kaiqing Zhang
• Abstract要約: 一般ゲームにおける確率的定常なマルコフ粗相関平衡(CCE)の計算は、計算的に難解であることを示す。 この結果は、正確なCCEを効率的に計算可能な正規形式ゲームとは対照的である。
• 参考スコア（独自算出の注目度）: 44.77547027158141
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that computing approximate stationary Markov coarse correlated equilibria (CCE) in general-sum stochastic games is computationally intractable, even when there are two players, the game is turn-based, the discount factor is an absolute constant, and the approximation is an absolute constant. Our intractability results stand in sharp contrast to normal-form games where exact CCEs are efficiently computable. A fortiori, our results imply that there are no efficient algorithms for learning stationary Markov CCE policies in multi-agent reinforcement learning (MARL), even when the interaction is two-player and turn-based, and both the discount factor and the desired approximation of the learned policies is an absolute constant. In turn, these results stand in sharp contrast to single-agent reinforcement learning (RL) where near-optimal stationary Markov policies can be efficiently learned. Complementing our intractability results for stationary Markov CCEs, we provide a decentralized algorithm (assuming shared randomness among players) for learning a nonstationary Markov CCE policy with polynomial time and sample complexity in all problem parameters. Previous work for learning Markov CCE policies all required exponential time and sample complexity in the number of players.
• Abstract（参考訳）: 一般確率ゲームにおける近似定常マルコフ粗相関平衡 (CCE) の計算は, 2人のプレイヤーが存在する場合でも, ゲームはターンベースであり, 割引係数は絶対定数であり, 近似は絶対定数であることを示す。 我々の難易度は、正確なCCEを効率的に計算できる通常のゲームとは対照的である。 その結果,マルチエージェント強化学習(MARL)におけるマルコフCCEポリシーの学習には,相互作用が2つのプレイヤーとターンベースであっても効率の良いアルゴリズムが存在しないこと,学習方針の割引係数と所望の近似が絶対定数であること,などが示唆された。 これらの結果は, ほぼ最適な定常マルコフ政策を効率的に学習できる単一エージェント強化学習(RL)とは対照的である。 定常マルコフCCEの難易度を補足し、非定常マルコフCCEポリシーを多項式時間で学習する分散アルゴリズム(プレイヤー間のランダム性を仮定する)を提供する。 マルコフのCCEポリシーを学習するためには、プレイヤー数の指数時間とサンプルの複雑さが必要だった。

関連論文リスト

• Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games [3.8779763612314633]
  一般的なマルコフゲームにおける学習アルゴリズムの特性について検討する。 特に,各エージェントがアクター批判学習を動的に採用する分散アルゴリズムに着目した。
  論文  参考訳（メタデータ） (2024-09-06T20:49:11Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  本研究は,情報指向サンプリング(IDS)の原理に基づくマルチエージェント強化学習(MARL)のための新しいアルゴリズムの設計と解析を行う。 エピソディックな2プレーヤゼロサムMGに対して、ナッシュ平衡を学習するための3つのサンプル効率アルゴリズムを提案する。 我々は、Reg-MAIDSをマルチプレイヤー汎用MGに拡張し、ナッシュ平衡または粗相関平衡をサンプル効率良く学習できることを証明する。
  論文  参考訳（メタデータ） (2024-04-30T06:48:56Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation [44.051717720483595]
  本稿では,マルチ緊急近似の呪いを確実に解決するMARLアルゴリズムの1行について述べる。 より弱いバージョンのCCEを学習する代わりに、このアルゴリズムは一般的な関数近似の下で幅広い問題に適用される。 我々のアルゴリズムは常にMarkov CCEを出力し、最適レートは$widetildemathcalO(epsilon-2)$で$epsilon$-optimal Solutionを見つける。
  論文  参考訳（メタデータ） (2023-02-13T18:59:25Z)
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation [56.715186432566576]
  そこで本稿では,大規模状態空間と多数のエージェントを用いた強化学習のための新しいモデルである独立線形マルコフゲームを提案する。 我々は,各エージェントの関数クラスの複雑性にのみ対応して,サンプル境界複雑性を持つ相関平衡 (CCE) とマルコフ相関平衡 (CE) を学習するための新しいアルゴリズムを設計する。 提案アルゴリズムは,1)複数のエージェントによる非定常性に対処するためのポリシーリプレイと,機能近似の利用,2)マルコフ均衡の学習とマルコフゲームにおける探索の分離という,2つの重要な技術革新に依存している。
  論文  参考訳（メタデータ） (2023-02-07T18:47:48Z)
• Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation [93.52573037053449]
  H-MARL (Hallucinated Multi-Agent Reinforcement Learning) は,環境と数回交流した後の平衡政策を学習する。 自律運転シミュレーションベンチマークにおいて,本手法を実験的に実証した。
  論文  参考訳（メタデータ） (2022-03-14T17:24:03Z)
• Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
  ゲームにおける学習は、多エージェント強化学習(MARL)における最も標準的で基本的な設定であることは間違いない。 汎用近似ゲーム(SG)の重要なクラスにおいて、完全分散Q-ラーニングアルゴリズムの有限サンプル複雑性を確立する。 我々は,各エージェントが報酬や他のエージェントの行動を観察できないような,完全に分散化されたMARLの実践的かつ挑戦的な設定に焦点をあてる。
  論文  参考訳（メタデータ） (2021-12-15T03:33:39Z)
• On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games [18.48133964089095]
  ゲーム(SG)は、マルチエージェント強化学習(MARL)とシーケンシャルエージェント相互作用の研究の基礎となった。 我々は,textbfPPAD-completeの指数的精度において,有限状態SGsゲームにおける近似完全平衡(MPE)を導出する。 その結果,textbfNP=textbfco-NP がなければ,SGs における MPE の発見は textbfNP-hard である可能性が極めて低いことが示唆された。
  論文  参考訳（メタデータ） (2021-09-04T05:47:59Z)

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

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