論文の概要: V-Learning -- A Simple, Efficient, Decentralized Algorithm for
Multiagent RL
- arxiv url: http://arxiv.org/abs/2110.14555v1
- Date: Wed, 27 Oct 2021 16:25:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 12:54:31.170774
- Title: V-Learning -- A Simple, Efficient, Decentralized Algorithm for
Multiagent RL
- Title（参考訳）: V-Learning -- マルチエージェントRLのためのシンプルで効率的な分散アルゴリズム
- Authors: Chi Jin, Qinghua Liu, Yuanhao Wang, Tiancheng Yu
- Abstract要約: V-ラーニング(V-learning)は、任意の反逆バンディットアルゴリズムをRLアルゴリズムに変換する、単エージェントRLアルゴリズムの新しいクラスである。
Q-ラーニングとは異なり、Q-値の代わりにV-値の推定だけを保持する。
- 参考スコア（独自算出の注目度）: 35.304241088947116
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A major challenge of multiagent reinforcement learning (MARL) is the curse of
multiagents, where the size of the joint action space scales exponentially with
the number of agents. This remains to be a bottleneck for designing efficient
MARL algorithms even in a basic scenario with finitely many states and actions.
This paper resolves this challenge for the model of episodic Markov games. We
design a new class of fully decentralized algorithms -- V-learning, which
provably learns Nash equilibria (in the two-player zero-sum setting),
correlated equilibria and coarse correlated equilibria (in the multiplayer
general-sum setting) in a number of samples that only scales with
$\max_{i\in[m]} A_i$, where $A_i$ is the number of actions for the $i^{\rm th}$
player. This is in sharp contrast to the size of the joint action space which
is $\prod_{i=1}^m A_i$. V-learning (in its basic form) is a new class of
single-agent RL algorithms that convert any adversarial bandit algorithm with
suitable regret guarantees into a RL algorithm. Similar to the classical
Q-learning algorithm, it performs incremental updates to the value functions.
Different from Q-learning, it only maintains the estimates of V-values instead
of Q-values. This key difference allows V-learning to achieve the claimed
guarantees in the MARL setting by simply letting all agents run V-learning
independently.
- Abstract（参考訳）: マルチエージェント強化学習(marl:multiagent reinforcement learning)の最大の課題はマルチエージェントの呪いである。
これは、有限個の状態と動作を持つ基本的なシナリオであっても、効率的なMARLアルゴリズムを設計する上でボトルネックとなる。
本稿では,この課題をマルコフゲームのモデルとして解決する。
v-learningは、$\max_{i\in[m]} a_i$でしかスケールしないサンプル数において、nash平衡(2人のプレイヤーがゼロサム設定で)、相関平衡、粗相関平衡(マルチプレイヤーの一般サム設定で)を確実に学習し、ここで$a_i$は$i^{\rm th}$プレイヤーのアクション数である。
これは、$\prod_{i=1}^m A_i$である関節アクション空間のサイズと鋭く対照的である。
v-learning(基本形)は、任意の逆バンディットアルゴリズムを適切な後悔の保証でrlアルゴリズムに変換する、単一エージェントのrlアルゴリズムの新しいクラスである。
古典的なq学習アルゴリズムと同様に、値関数を漸進的に更新する。
q-learningとは異なり、q-valueではなくv-valueの見積しか保持しない。
この重要な違いにより、v-learningは、すべてのエージェントがv-learningを独立して実行することによって、marl設定で主張された保証を達成することができる。
関連論文リスト
- 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) - 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 Cooperative Multi-Agent Reinforcement Learning with
Exploration [35.75029940279768]
マルコフチーム(Markov team)において、最も基本的な協調環境でマルチエージェント強化学習を研究する。
本稿では,各エージェントが独立してステージベースのVラーニングスタイルのアルゴリズムを実行するアルゴリズムを提案する。
エージェントは、少なくとも$proptowidetildeO (1/epsilon4)$ episodesにおいて、$epsilon$-approximate Nash平衡ポリシーを学ぶことができる。
論文 参考訳（メタデータ） (2021-10-12T02:45:12Z) - Provably Efficient Reinforcement Learning in Decentralized General-Sum
Markov Games [5.205867750232226]
本稿では,一般のマルコフゲームにおいて平衡を効率的に学習する問題に対処する。
本稿では,各エージェントが独立して楽観的なV-ラーニングを実行し,未知の環境を効率的に探索するアルゴリズムを提案する。
エージェントは少なくとも$widetildeO(H6S A /epsilon2)$ episodesで$epsilon$-approximate CCEを見つけることができる。
論文 参考訳（メタデータ） (2021-10-12T02:01:22Z) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - QVMix and QVMix-Max: Extending the Deep Quality-Value Family of
Algorithms to Cooperative Multi-Agent Reinforcement Learning [10.334745043233974]
本稿では,マルチエージェント強化学習問題に取り組むための4つのアルゴリズムを提案する。
すべてのアルゴリズムは、Deep Quality-Valueアルゴリズムファミリに基づいている。
QVMix と QVMix-Max をよく知られた MARL 技術と比較した場合の競合結果を示す。
論文 参考訳（メタデータ） (2020-12-22T14:53:42Z) - A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。
我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。
我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
論文 参考訳（メタデータ） (2020-10-04T15:27:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。