論文の概要: Near-Optimal Reinforcement Learning with Self-Play
- arxiv url: http://arxiv.org/abs/2006.12007v2
- Date: Tue, 14 Jul 2020 04:21:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 04:17:38.728765
- Title: Near-Optimal Reinforcement Learning with Self-Play
- Title（参考訳）: セルフプレイによる近最適強化学習
- Authors: Yu Bai, Chi Jin, Tiancheng Yu
- Abstract要約: 我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 50.29853537456737
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the problem of designing optimal algorithms for
reinforcement learning in two-player zero-sum games. We focus on self-play
algorithms which learn the optimal policy by playing against itself without any
direct supervision. In a tabular episodic Markov game with $S$ states, $A$
max-player actions and $B$ min-player actions, the best existing algorithm for
finding an approximate Nash equilibrium requires $\tilde{\mathcal{O}}(S^2AB)$
steps of game playing, when only highlighting the dependency on $(S,A,B)$. In
contrast, the best existing lower bound scales as $\Omega(S(A+B))$ and has a
significant gap from the upper bound. This paper closes this gap for the first
time: we propose an optimistic variant of the \emph{Nash Q-learning} algorithm
with sample complexity $\tilde{\mathcal{O}}(SAB)$, and a new \emph{Nash
V-learning} algorithm with sample complexity $\tilde{\mathcal{O}}(S(A+B))$. The
latter result matches the information-theoretic lower bound in all
problem-dependent parameters except for a polynomial factor of the length of
each episode. In addition, we present a computational hardness result for
learning the best responses against a fixed opponent in Markov games---a
learning objective different from finding the Nash equilibrium.
- Abstract（参考訳）: 本稿では,2プレイヤーゼロサムゲームにおける強化学習のための最適アルゴリズムの設計問題について考察する。
我々は,直接の監督なしに自己対決で最適な政策を学ぶセルフプレイアルゴリズムに焦点を当てる。
s$状態、$a$ max-playerアクション、$b$ min-playerアクションを持つ表型エピソディックマルコフゲームでは、近似ナッシュ均衡を見つけるための最良の既存のアルゴリズムは、$(s,a,b)$にのみ依存を強調するとき、ゲームプレイのステップである$\tilde{\mathcal{o}}(s^2ab)$を必要とする。
対照的に、最も高い既存の下界スケールは$\Omega(S(A+B))$で、上界と大きな差がある。
本稿では, サンプル複雑性を$\tilde{\mathcal{O}}(SAB)$, サンプル複雑性を$\tilde{\mathcal{O}}(S(A+B)$とする新しい \emph{Nash V-learning} アルゴリズムの楽観的な変種を提案する。
後者の結果は、各エピソードの長さの多項式係数を除く全ての問題依存パラメータにおける情報理論の下限と一致する。
さらに,マルコフゲームにおける固定対戦相手に対する最善の応答を学習する計算の難易度を,nash平衡を求めることとは異なる学習目標として提示する。
関連論文リスト
- Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games [18.832436856339587]
本稿では,オフラインデータから2プレイヤーゼロサムマルコフゲームにおけるナッシュ均衡の学習に向けて前進する。
ベルンシュタイン型低信頼境界を持つ悲観的モデルベースアルゴリズム(VI-LCB-Game)を提案する。
論文 参考訳（メタデータ） (2022-06-08T17:58:06Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。
我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。
そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
論文 参考訳（メタデータ） (2021-12-06T08:27:54Z) - When Can We Learn General-Sum Markov Games with a Large Number of
Players Sample-Efficiently? [10.397170312149067]
本稿では,m$-player General-sum Markovゲームの設定において,学習目標がより優れたサンプル複雑性を許容するものについて検討する。
まず,$epsilon$-Coarse Correlated Equilibrium (CCE)を$widetildemathcalO(H5Smax_ile m A_i / epsilon2)$ episodesで学習するアルゴリズムを設計する。
第二に、マルコフポテンシャルゲームの重要な特別な場合を考え、$widet内で$epsilon$-approximate Nash平衡を学ぶアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-10-08T15:06:22Z) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - Almost Optimal Algorithms for Two-player Markov Games with Linear
Function Approximation [92.99933928528797]
同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。
我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。
我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
論文 参考訳（メタデータ） (2021-02-15T09:09:16Z) - A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。
我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。
我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
論文 参考訳（メタデータ） (2020-10-04T15:27:39Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。