論文の概要: Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games

• arxiv url: http://arxiv.org/abs/2308.08858v2
• Date: Wed, 5 Jun 2024 21:24:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-08 00:49:21.102608
• Title: Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games
• Title（参考訳）: ゼロサムマルコフゲームにおけるモデルフリーアルゴリズムのサンプル効率の改善
• Authors: Songtao Feng, Ming Yin, Yu-Xiang Wang, Jing Yang, Yingbin Liang,
• Abstract要約: モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。 本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
• 参考スコア（独自算出の注目度）: 66.2085181793014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of two-player zero-sum Markov games has recently attracted increasing interests in theoretical studies of multi-agent reinforcement learning (RL). In particular, for finite-horizon episodic Markov decision processes (MDPs), it has been shown that model-based algorithms can find an $\epsilon$-optimal Nash Equilibrium (NE) with the sample complexity of $O(H^3SAB/\epsilon^2)$, which is optimal in the dependence of the horizon $H$ and the number of states $S$ (where $A$ and $B$ denote the number of actions of the two players, respectively). However, none of the existing model-free algorithms can achieve such an optimality. In this work, we propose a model-free stage-based Q-learning algorithm and show that it achieves the same sample complexity as the best model-based algorithm, and hence for the first time demonstrate that model-free algorithms can enjoy the same optimality in the $H$ dependence as model-based algorithms. The main improvement of the dependency on $H$ arises by leveraging the popular variance reduction technique based on the reference-advantage decomposition previously used only for single-agent RL. However, such a technique relies on a critical monotonicity property of the value function, which does not hold in Markov games due to the update of the policy via the coarse correlated equilibrium (CCE) oracle. Thus, to extend such a technique to Markov games, our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions whose value difference is the smallest in the history in order to achieve the desired improvement in the sample efficiency.
• Abstract（参考訳）: 近年,マルチエージェント強化学習(RL)の理論研究において,ツープレイヤーゼロサムマルコフゲームの問題が注目されている。 特に有限ホライズン・エピソード・マルコフ決定過程(MDPs)では、モデルベースのアルゴリズムは、標本の複雑さが$O(H^3SAB/\epsilon^2)$で、地平線上の$H$と州数$S$(それぞれ$A$と$B$は2人のプレイヤーのアクションの数を表す)の依存性が最適である$O(H^3SAB/\epsilon^2)$を見つけることができる。 しかし、既存のモデルフリーアルゴリズムではそのような最適性を達成できない。 本研究では,モデルフリーのステージベースQ-ラーニングアルゴリズムを提案し,モデルフリーのアルゴリズムがモデルベースアルゴリズムと同一のサンプル複雑性を達成できることを示し,モデルフリーのアルゴリズムがモデルベースアルゴリズムと同一の最適性を享受できることを初めて示す。 H$への依存性の主な改善は、単一のエージェントRLでしか使われていなかった参照アドバンテージ分解に基づいて、一般的な分散還元技術を活用することで生じる。 しかし、そのような手法は値関数の臨界単調性に依存しており、これはマルコフのゲームでは粗相関平衡(CCE)オラクルによるポリシーの更新によって成り立たない。 そこで,この手法をマルコフゲームに拡張するために,提案アルゴリズムは,値差が史上最小となる楽観的かつ悲観的な値関数のペアとして参照値関数を更新し,標本効率の向上を期待する鍵となる設計を特徴としている。

関連論文リスト

• Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation [44.051717720483595]
  本稿では,マルチ緊急近似の呪いを確実に解決するMARLアルゴリズムの1行について述べる。 より弱いバージョンのCCEを学習する代わりに、このアルゴリズムは一般的な関数近似の下で幅広い問題に適用される。 我々のアルゴリズムは常にMarkov CCEを出力し、最適レートは$widetildemathcalO(epsilon-2)$で$epsilon$-optimal Solutionを見つける。
  論文  参考訳（メタデータ） (2023-02-13T18:59:25Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• 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)
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret [44.374427255708135]
  無限水平平均逆マルコフ決定過程(MDP)のモデルフリーアルゴリズムである探索強化Q-ラーニング(EE-QL)を提案する。 EE-QLは、最適平均報酬のオンライン集中近似が利用可能であると仮定する。 これは、エルゴード的な仮定なしに$O(sqrt T)$後悔を達成する最初のモデル自由学習アルゴリズムであり、対数的因子を除いて、下位境界の$T$と一致する。
  論文  参考訳（メタデータ） (2020-06-08T05:09:32Z)

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

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