Fugu-MT 論文翻訳(概要): A Sharp Analysis of Model-based Reinforcement Learning with Self-Play

論文の概要: A Sharp Analysis of Model-based Reinforcement Learning with Self-Play

arxiv url: http://arxiv.org/abs/2010.01604v2
Date: Sun, 7 Feb 2021 03:38:01 GMT
ステータス: 処理完了
システム内更新日: 2022-10-11 02:56:48.418355
Title: A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
Title（参考訳）: セルフプレイによるモデルベース強化学習のシャープ解析
Authors: Qinghua Liu, Tiancheng Yu, Yu Bai, Chi Jin
Abstract要約: マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
参考スコア（独自算出の注目度）: 49.88233710867315
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Model-based algorithms -- algorithms that explore the environment through building and utilizing an estimated model -- are widely used in reinforcement learning practice and theoretically shown to achieve optimal sample efficiency for single-agent reinforcement learning in Markov Decision Processes (MDPs). However, for multi-agent reinforcement learning in Markov games, the current best known sample complexity for model-based algorithms is rather suboptimal and compares unfavorably against recent model-free approaches. In this paper, we present a sharp analysis of model-based self-play algorithms for multi-agent Markov games. We design an algorithm -- Optimistic Nash Value Iteration (Nash-VI) for two-player zero-sum Markov games that is able to output an $\epsilon$-approximate Nash policy in $\tilde{\mathcal{O}}(H^3SAB/\epsilon^2)$ episodes of game playing, where $S$ is the number of states, $A,B$ are the number of actions for the two players respectively, and $H$ is the horizon length. This significantly improves over the best known model-based guarantee of $\tilde{\mathcal{O}}(H^4S^2AB/\epsilon^2)$, and is the first that matches the information-theoretic lower bound $\Omega(H^3S(A+B)/\epsilon^2)$ except for a $\min\{A,B\}$ factor. In addition, our guarantee compares favorably against the best known model-free algorithm if $\min \{A,B\}=o(H^3)$, and outputs a single Markov policy while existing sample-efficient model-free algorithms output a nested mixture of Markov policies that is in general non-Markov and rather inconvenient to store and execute. We further adapt our analysis to designing a provably efficient task-agnostic algorithm for zero-sum Markov games, and designing the first line of provably sample-efficient algorithms for multi-player general-sum Markov games.
Abstract（参考訳）: モデルベースアルゴリズム -- 推定モデルの構築と活用を通じて環境を探索するアルゴリズム -- は強化学習実践で広く使われており、理論的にはマルコフ決定過程(mdps)における単一エージェント強化学習の最適なサンプル効率を達成することが示されている。しかしながら、マルコフゲームにおけるマルチエージェント強化学習では、モデルベースアルゴリズムの現在の最もよく知られたサンプル複雑性は、比較的最適であり、最近のモデルフリーアプローチと好ましくない比較である。本稿では,マルチエージェント型マルコフゲームのためのモデルベースセルフプレイアルゴリズムの急激な解析を行う。私たちは、ゲームプレイのエピソードである$\tilde{\mathcal{o}}(h^3sab/\epsilon^2)$で$\epsilon$-approximate nashポリシーを出力できる2人のプレイヤーのゼロサムマルコフゲームのための楽観的なnash値反復(nash-vi)を設計します。これは、$\tilde{\mathcal{O}}(H^4S^2AB/\epsilon^2)$の最もよく知られたモデルベースの保証よりも大幅に改善され、$\min\{A,B\}$ factorを除いて、情報理論的下界$\Omega(H^3S(A+B)/\epsilon^2)$と一致する最初のものである。さらに,既存のサンプル効率のよいモデルフリーアルゴリズムは,一般にはマルコフでないが保存や実行に不便なマルコフポリシーのネスト混合を出力するのに対して,$\min \{A,B\}=o(H^3)$の場合,この保証は最もよく知られたモデルフリーアルゴリズムと比較できる。我々はさらに,ゼロサムマルコフゲームにおけるタスク非依存な実現可能なアルゴリズムの設計と,マルチプレーヤ一般サムマルコフゲームのための実証可能なサンプル効率アルゴリズムの最初のラインの設計に,解析を適用した。

論文の概要: A Sharp Analysis of Model-based Reinforcement Learning with Self-Play

関連論文リスト