論文の概要: Provably Efficient Reinforcement Learning in Decentralized General-Sum
Markov Games
- arxiv url: http://arxiv.org/abs/2110.05682v1
- Date: Tue, 12 Oct 2021 02:01:22 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-13 13:05:09.264176
- Title: Provably Efficient Reinforcement Learning in Decentralized General-Sum
Markov Games
- Title（参考訳）: 分散一般サムマルコフゲームにおける効果的な強化学習
- Authors: Weichao Mao, Tamer Ba\c{s}ar
- Abstract要約: 本稿では,一般のマルコフゲームにおいて平衡を効率的に学習する問題に対処する。
本稿では,各エージェントが独立して楽観的なV-ラーニングを実行し,未知の環境を効率的に探索するアルゴリズムを提案する。
エージェントは少なくとも$widetildeO(H6S A /epsilon2)$ episodesで$epsilon$-approximate CCEを見つけることができる。
- 参考スコア（独自算出の注目度）: 5.205867750232226
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper addresses the problem of learning an equilibrium efficiently in
general-sum Markov games through decentralized multi-agent reinforcement
learning. Given the fundamental difficulty of calculating a Nash equilibrium
(NE), we instead aim at finding a coarse correlated equilibrium (CCE), a
solution concept that generalizes NE by allowing possible correlations among
the agents' strategies. We propose an algorithm in which each agent
independently runs optimistic V-learning (a variant of Q-learning) to
efficiently explore the unknown environment, while using a stabilized online
mirror descent (OMD) subroutine for policy updates. We show that the agents can
find an $\epsilon$-approximate CCE in at most $\widetilde{O}( H^6S A
/\epsilon^2)$ episodes, where $S$ is the number of states, $A$ is the size of
the largest individual action space, and $H$ is the length of an episode. This
appears to be the first sample complexity result for learning in generic
general-sum Markov games. Our results rely on a novel investigation of an
anytime high-probability regret bound for OMD with a dynamic learning rate and
weighted regret, which would be of independent interest. One key feature of our
algorithm is that it is fully \emph{decentralized}, in the sense that each
agent has access to only its local information, and is completely oblivious to
the presence of others. This way, our algorithm can readily scale up to an
arbitrary number of agents, without suffering from the exponential dependence
on the number of agents.
- Abstract（参考訳）: 本稿では,分散マルチエージェント強化学習による一般サムマルコフゲームにおける平衡学習の効率化について述べる。
ナッシュ均衡(NE)を計算することの根本的な困難さを考えると、我々はエージェントの戦略間の相関を許容することによってNEを一般化するソリューション概念である粗相関平衡(CCE)を見つけることを目指している。
本稿では,各エージェントが楽観的v-learning(q-learningの変種)を独立に実行して未知環境を効率的に探索するアルゴリズムを提案する。
エージェントは$\epsilon$-approximate CCEを最大$\widetilde{O}(H^6S A /\epsilon^2)$のエピソードで見つけることができる。
これは一般的な一般のマルコフゲームで学ぶための最初のサンプル複雑性の結果である。
本研究は, 動的学習率と重み付き後悔を伴うOMDに対して, 常に高い確率の後悔が伴うことを新たな研究に頼っている。
アルゴリズムの重要な特徴の1つは、各エージェントがローカル情報のみにアクセスでき、他のエージェントの存在を全く無視できるという意味で、完全に\emph{decentralized} であることである。
このようにして、我々のアルゴリズムは任意の数のエージェントに容易にスケールアップできるが、エージェント数への指数的な依存に悩まされることはない。
関連論文リスト
- A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
非定常マルチエージェントシステムにおける平衡の学習について検討する。
単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
論文 参考訳（メタデータ） (2023-06-12T23:48:24Z) - Stochastic Principal-Agent Problems: Efficient Computation and Learning [25.637633553882985]
プリンシパルとエージェントは環境の中で相互作用し、それぞれが互いに利用できない状態に関する観察を行う。
このモデルは、特殊ケースワイドフォームゲーム(EFG)を包含し、マルコフ決定プロセス(POMDP)のゲームにアプローチする。
遷移確率が未知のエピソード強化学習環境において,効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-06T16:20:44Z) - 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) - Decentralized model-free reinforcement learning in stochastic games with
average-reward objective [1.9852463786440127]
本アルゴリズムは,次数$T3/4$のサブ線形高確率後悔と次数$T2/3$のサブ線形高確率後悔を実現する。
本アルゴリズムは,従来の手法に比べて計算量が少なく,メモリスペースも少ない。
論文 参考訳（メタデータ） (2023-01-13T15:59:53Z) - Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。
遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
論文 参考訳（メタデータ） (2022-10-30T22:58:22Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret
Learning in Markov Games [95.10091348976779]
我々はマルコフゲームにおいて、非定常的でおそらく敵対的な相手と遊べる単一のエージェントを制御する分散ポリシー学習について研究する。
我々は、新しいアルゴリズム、アンダーラインデ集中型アンダーラインハイプラインRpolicy munderlineIrror deunderlineScent (DORIS)を提案する。
DORISは、一般的な関数近似の文脈で$sqrtK$-regretを達成する。
論文 参考訳（メタデータ） (2022-06-03T14:18:05Z) - V-Learning -- A Simple, Efficient, Decentralized Algorithm for
Multiagent RL [35.304241088947116]
V-ラーニング(V-learning)は、任意の反逆バンディットアルゴリズムをRLアルゴリズムに変換する、単エージェントRLアルゴリズムの新しいクラスである。
Q-ラーニングとは異なり、Q-値の代わりにV-値の推定だけを保持する。
論文 参考訳（メタデータ） (2021-10-27T16:25:55Z) - Decentralized Cooperative Multi-Agent Reinforcement Learning with
Exploration [35.75029940279768]
マルコフチーム(Markov team)において、最も基本的な協調環境でマルチエージェント強化学習を研究する。
本稿では,各エージェントが独立してステージベースのVラーニングスタイルのアルゴリズムを実行するアルゴリズムを提案する。
エージェントは、少なくとも$proptowidetildeO (1/epsilon4)$ episodesにおいて、$epsilon$-approximate Nash平衡ポリシーを学ぶことができる。
論文 参考訳（メタデータ） (2021-10-12T02:45:12Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。