論文の概要: On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games

• arxiv url: http://arxiv.org/abs/2109.01795v1
• Date: Sat, 4 Sep 2021 05:47:59 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-07 17:23:44.285872
• Title: On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games
• Title（参考訳）: 汎用確率ゲームにおけるマルコフ完全平衡計算の複雑さについて
• Authors: Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, Yaodong Yang
• Abstract要約: ゲーム(SG)は、マルチエージェント強化学習(MARL)とシーケンシャルエージェント相互作用の研究の基礎となった。 我々は,textbfPPAD-completeの指数的精度において,有限状態SGsゲームにおける近似完全平衡(MPE)を導出する。 その結果,textbfNP=textbfco-NP がなければ,SGs における MPE の発見は textbfNP-hard である可能性が極めて低いことが示唆された。
• 参考スコア（独自算出の注目度）: 18.48133964089095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Similar to the role of Markov decision processes in reinforcement learning, Stochastic Games (SGs) lay the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions. In this paper, we derive that computing an approximate Markov Perfect Equilibrium (MPE) in a finite-state discounted Stochastic Game within the exponential precision is \textbf{PPAD}-complete. We adopt a function with a polynomially bounded description in the strategy space to convert the MPE computation to a fixed-point problem, even though the stochastic game may demand an exponential number of pure strategies, in the number of states, for each agent. The completeness result follows the reduction of the fixed-point problem to {\sc End of the Line}. Our results indicate that finding an MPE in SGs is highly unlikely to be \textbf{NP}-hard unless \textbf{NP}=\textbf{co-NP}. Our work offers confidence for MARL research to study MPE computation on general-sum SGs and to develop fruitful algorithms as currently on zero-sum SGs.
• Abstract（参考訳）: 強化学習におけるマルコフ決定プロセスの役割と同様に、確率ゲーム(SG)はマルチエージェント強化学習(MARL)とシーケンシャルエージェント相互作用の研究の基礎を築いた。 本稿では,指数的精度における有限状態割引確率ゲームにおける近似マルコフ完全平衡 (MPE) の計算が \textbf{PPAD}-完全であることを示す。 我々は,MPE計算を定点問題に変換するために,戦略空間に多項式的に有界な記述を持つ関数を採用する。 完全性の結果は、固定点問題をラインの {\sc 終点へ還元するのに続く。 以上の結果から, SGs における MPE の発見は \textbf{NP}=\textbf{co-NP} がなければ, 極めて困難である可能性が示唆された。 我々の研究は、汎用SG上でのMPE計算の研究と、現在ゼロサムSG上での実りあるアルゴリズムの開発に、MARL研究の信頼性を提供する。

関連論文リスト

• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究 まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。 次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
  論文  参考訳（メタデータ） (2023-06-21T16:04:03Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• 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)
• The Complexity of Markov Equilibrium in Stochastic Games [44.77547027158141]
  一般ゲームにおける確率的定常なマルコフ粗相関平衡(CCE)の計算は、計算的に難解であることを示す。 この結果は、正確なCCEを効率的に計算可能な正規形式ゲームとは対照的である。
  論文  参考訳（メタデータ） (2022-04-08T10:51:01Z)
• Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
  ゲームにおける学習は、多エージェント強化学習(MARL)における最も標準的で基本的な設定であることは間違いない。 汎用近似ゲーム(SG)の重要なクラスにおいて、完全分散Q-ラーニングアルゴリズムの有限サンプル複雑性を確立する。 我々は,各エージェントが報酬や他のエージェントの行動を観察できないような,完全に分散化されたMARLの実践的かつ挑戦的な設定に焦点をあてる。
  論文  参考訳（メタデータ） (2021-12-15T03:33:39Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Gradient play in stochastic games: stationary points, convergence, and sample complexity [6.97785632069611]
  ゲーム用グラデーションプレイアルゴリズム(SG)の性能について検討する。 この設定では、ナッシュ均衡(NE)と1次定常ポリシーが等価であることを示す。 マルコフポテンシャルゲームと呼ばれるSGのサブクラスに対して、サンプルベース強化学習アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-01T03:03:45Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)

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

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