論文の概要: Representation Learning for General-sum Low-rank Markov Games
- arxiv url: http://arxiv.org/abs/2210.16976v1
- Date: Sun, 30 Oct 2022 22:58:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 15:58:02.936116
- Title: Representation Learning for General-sum Low-rank Markov Games
- Title（参考訳）: 汎用低ランクマルコフゲームにおける表現学習
- Authors: Chengzhuo Ni, Yuda Song, Xuezhou Zhang, Chi Jin, Mengdi Wang
- Abstract要約: 非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。
遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
- 参考スコア（独自算出の注目度）: 63.119870889883224
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study multi-agent general-sum Markov games with nonlinear function
approximation. We focus on low-rank Markov games whose transition matrix admits
a hidden low-rank structure on top of an unknown non-linear representation. The
goal is to design an algorithm that (1) finds an $\varepsilon$-equilibrium
policy sample efficiently without prior knowledge of the environment or the
representation, and (2) permits a deep-learning friendly implementation. We
leverage representation learning and present a model-based and a model-free
approach to construct an effective representation from the collected data. For
both approaches, the algorithm achieves a sample complexity of
poly$(H,d,A,1/\varepsilon)$, where $H$ is the game horizon, $d$ is the
dimension of the feature vector, $A$ is the size of the joint action space and
$\varepsilon$ is the optimality gap. When the number of players is large, the
above sample complexity can scale exponentially with the number of players in
the worst case. To address this challenge, we consider Markov games with a
factorized transition structure and present an algorithm that escapes such
exponential scaling. To our best knowledge, this is the first sample-efficient
algorithm for multi-agent general-sum Markov games that incorporates
(non-linear) function approximation. We accompany our theoretical result with a
neural network-based implementation of our algorithm and evaluate it against
the widely used deep RL baseline, DQN with fictitious play.
- Abstract（参考訳）: 非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。
遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
目的は,(1)環境や表現の事前知識を必要とせず,効率よく$\varepsilon$-equilibrium Policyサンプルを見つけるアルゴリズムを設計することであり,(2)ディープラーニングに親しみやすい実装を可能にする。
表現学習を活用し、収集したデータから効果的な表現を構築するためのモデルベースおよびモデルフリーなアプローチを提案する。
どちらのアプローチに対しても、このアルゴリズムはpoly$(H,d,A,1/\varepsilon)$のサンプル複雑性を達成し、$H$はゲーム水平線、$d$は特徴ベクトルの次元、$A$は関節アクション空間のサイズ、$\varepsilon$は最適性ギャップである。
プレイヤー数が大きくなると、上記のサンプル複雑性は最悪の場合プレイヤー数で指数関数的に拡大する。
この課題に対処するために、マルコフゲームは分解された遷移構造を持ち、そのような指数的スケーリングから逃れるアルゴリズムを提案する。
我々の知る限り、これは(非線形)関数近似を組み込んだマルチエージェント汎用マルコフゲームのための最初のサンプル効率アルゴリズムである。
ニューラルネットワークによるアルゴリズムの実装による理論的結果に付随し、広く使われている深部RLベースラインであるDQNに対して、架空のプレイで評価する。
関連論文リスト
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。
本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
論文 参考訳（メタデータ） (2023-08-17T08:34:58Z) - 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) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。