論文の概要: Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games
- arxiv url: http://arxiv.org/abs/2303.12287v1
- Date: Wed, 22 Mar 2023 03:28:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-23 15:29:02.467047
- Title: Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games
- Title（参考訳）: マルコフゲームにおける独立学習のハードネスとスパース均衡計算
- Authors: Dylan J. Foster, Noah Golowich, Sham M. Kakade
- Abstract要約: マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
- 参考スコア（独自算出の注目度）: 70.19141208203227
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of decentralized multi-agent reinforcement learning
in Markov games. A fundamental question is whether there exist algorithms that,
when adopted by all agents and run independently in a decentralized fashion,
lead to no-regret for each player, analogous to celebrated convergence results
in normal-form games. While recent work has shown that such algorithms exist
for restricted settings (notably, when regret is defined with respect to
deviations to Markovian policies), the question of whether independent
no-regret learning can be achieved in the standard Markov game framework was
open. We provide a decisive negative resolution this problem, both from a
computational and statistical perspective. We show that:
- Under the widely-believed assumption that PPAD-hard problems cannot be
solved in polynomial time, there is no polynomial-time algorithm that attains
no-regret in general-sum Markov games when executed independently by all
players, even when the game is known to the algorithm designer and the number
of players is a small constant.
- When the game is unknown, no algorithm, regardless of computational
efficiency, can achieve no-regret without observing a number of episodes that
is exponential in the number of players.
Perhaps surprisingly, our lower bounds hold even for seemingly easier setting
in which all agents are controlled by a a centralized algorithm. They are
proven via lower bounds for a simpler problem we refer to as SparseCCE, in
which the goal is to compute a coarse correlated equilibrium that is sparse in
the sense that it can be represented as a mixture of a small number of product
policies. The crux of our approach is a novel application of aggregation
techniques from online learning, whereby we show that any algorithm for the
SparseCCE problem can be used to compute approximate Nash equilibria for
non-zero sum normal-form games.
- Abstract（参考訳）: マルコフゲームにおける分散マルチエージェント強化学習の問題を考える。
基本的な問題は、すべてのエージェントによって採用され、分散された方法で独立して実行されるアルゴリズムが存在する場合、各プレイヤーがノーレグレットに繋がるアルゴリズムが存在するかどうかである。
近年の研究では、制限された設定のためにそのようなアルゴリズムが存在することが示されている(特にマルコフのポリシーへの偏見に関して後悔が定義される)が、標準マルコフゲームフレームワークで独立した非回帰学習が達成できるかどうかという疑問が開かれた。
計算と統計の両方の観点から、この問題を決定的に否定的に解決する。
PPAD-ハード問題は多項式時間では解けないという広く信じられている仮定の下では、全てのプレイヤーが独立に実行した場合に一般のマルコフゲームにおいて、ゲームがアルゴリズムデザイナーに知られ、プレイヤー数が少なくても、多項式時間アルゴリズムは存在しない。
-ゲームが未知の場合には、計算効率に関係なく、プレイヤー数に指数関数的なエピソードを数回観察することなく、いかなるアルゴリズムもノンリグレットを達成できない。
おそらく意外なことに、我々の下限は、すべてのエージェントが中央集権的なアルゴリズムで制御されるような、一見簡単な設定であっても保持される。
それらは、我々がスパーセッセ(sparsecce)と呼ぶより単純な問題に対する下限を通じて証明され、それは、少量の製品ポリシーの混合として表現できるという意味で、粗い相関均衡を計算することを目的としている。
本手法の要点は,オンライン学習における集約手法の新たな応用であり,SparseCCE問題に対する任意のアルゴリズムを用いて,非ゼロ和正規形式ゲームに対する近似ナッシュ平衡を計算することができることを示す。
関連論文リスト
- Independent Learning in Constrained Markov Potential Games [19.083595175045073]
制約付きマルコフゲームは、マルチエージェント強化学習問題をモデル化するための正式なフレームワークを提供する。
近似的制約付きナッシュ平衡を学習するための独立ポリシー勾配アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-27T20:57:35Z) - Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。
本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
論文 参考訳（メタデータ） (2024-01-10T12:56:24Z) - 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) - Learning in Multi-Player Stochastic Games [1.0878040851638]
有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。
ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。
我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
論文 参考訳（メタデータ） (2022-10-25T19:02:03Z) - Regret Minimization and Convergence to Equilibria in General-sum Markov
Games [57.568118148036376]
汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。
我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
論文 参考訳（メタデータ） (2022-07-28T16:27:59Z) - Learning in Congestion Games with Bandit Feedback [45.4542525044623]
我々は、良質な理論構造と広い実世界の応用を持つゲームのクラスである混雑ゲームについて検討する。
まず,渋滞ゲームにおける不確実性原理に直面する楽観性に基づく集中型アルゴリズムを提案する。
次に,Frank-Wolfe法とG-Optimal設計を組み合わせた分散アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-04T02:32:26Z) - Independent Policy Gradient for Large-Scale Markov Potential Games:
Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。
我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。
我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
論文 参考訳（メタデータ） (2022-02-08T20:09:47Z) - Model-Free Online Learning in Unknown Sequential Decision Making
Problems and Games [114.90723492840499]
大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。
私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。
エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
論文 参考訳（メタデータ） (2021-03-08T04:03:24Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。