論文の概要: On Reinforcement Learning for Turn-based Zero-sum Markov Games
- arxiv url: http://arxiv.org/abs/2002.10620v1
- Date: Tue, 25 Feb 2020 01:40:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-28 20:43:57.770799
- Title: On Reinforcement Learning for Turn-based Zero-sum Markov Games
- Title（参考訳）: ターンベースゼロサムマルコフゲームにおける強化学習について
- Authors: Devavrat Shah, Varun Somani, Qiaomin Xie, Zhi Xu
- Abstract要約: 2人のプレイヤーのターンベースゼロサムゲームに対するナッシュ均衡を求める問題を考察する。
そこで我々は,AlphaGo Zero (AGZ) アルゴリズムにヒントを得て,強化学習に基づくアプローチを開発した。
- 参考スコア（独自算出の注目度）: 24.071036229246644
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding Nash equilibrium for two-player turn-based
zero-sum games. Inspired by the AlphaGo Zero (AGZ) algorithm, we develop a
Reinforcement Learning based approach. Specifically, we propose
Explore-Improve-Supervise (EIS) method that combines "exploration", "policy
improvement"' and "supervised learning" to find the value function and policy
associated with Nash equilibrium. We identify sufficient conditions for
convergence and correctness for such an approach. For a concrete instance of
EIS where random policy is used for "exploration", Monte-Carlo Tree Search is
used for "policy improvement" and Nearest Neighbors is used for "supervised
learning", we establish that this method finds an $\varepsilon$-approximate
value function of Nash equilibrium in $\widetilde{O}(\varepsilon^{-(d+4)})$
steps when the underlying state-space of the game is continuous and
$d$-dimensional. This is nearly optimal as we establish a lower bound of
$\widetilde{\Omega}(\varepsilon^{-(d+2)})$ for any policy.
- Abstract（参考訳）: 2人のプレイヤーのターンベースゼロサムゲームに対するナッシュ均衡を求める問題を考察する。
AlphaGo Zero (AGZ) アルゴリズムにヒントを得て,強化学習に基づくアプローチを開発した。
具体的には,「探索」「政治改善」「教師付き学習」を組み合わせて,ナッシュ均衡に伴う価値関数と政策を探索する探索・Improve-Supervise(EIS)手法を提案する。
このようなアプローチの収束と正しさの十分な条件を同定する。
ランダムなポリシーが「探索」に使われ、モンテカルロ・ツリー・サーチが「政治改善」に使われ、Nearest Neighborsが「教師付き学習」に使われているEISの具体的な例に対して、この手法は、ゲームの基本状態空間が連続かつ$d$次元であるときに、$\widetilde{O}(\varepsilon^{-(d+4)})のナッシュ平衡の$\varepsilon$-approximate値関数を見つけることを証明している。
これは、任意のポリシーに対して$\widetilde{\omega}(\varepsilon^{-(d+2)})$の下限を確立するときにほぼ最適である。
関連論文リスト
- Policy Mirror Ascent for Efficient and Independent Learning in Mean
Field Games [35.86199604587823]
平均場ゲームは対称および匿名の$N$-playerゲームに対して近似的なナッシュ均衡を得るための理論的ツールとして使われてきた。
ポリシーミラーを実行する$N$エージェントは、$widetildemathcalO(varepsilon-2)$サンプル内で正規化ゲームのナッシュ平衡に収束することを示す。
論文 参考訳（メタデータ） (2022-12-29T20:25:18Z) - 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) - Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games [18.832436856339587]
本稿では,オフラインデータから2プレイヤーゼロサムマルコフゲームにおけるナッシュ均衡の学習に向けて前進する。
ベルンシュタイン型低信頼境界を持つ悲観的モデルベースアルゴリズム(VI-LCB-Game)を提案する。
論文 参考訳（メタデータ） (2022-06-08T17:58:06Z) - Independent Policy Gradient for Large-Scale Markov Potential Games:
Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。
我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。
我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
論文 参考訳（メタデータ） (2022-02-08T20:09:47Z) - 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) - Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic
Games with Independent Chains [2.132096006921048]
我々は、プレイヤーがペイオフ機能を介して結合されている間、内部の状態/行動空間を持つ、$n$プレイヤゲームのクラスを考える。
このクラスのゲームに対して、報奨関数を仮定せずに定常ナッシュ(NE)ポリシーを見つけることは、対話可能であることを示す。
我々は,2重平均化と2重ミラー降下に基づくアルゴリズムを開発し,これを$epsilon$-NEポリシーの集合に収束させる。
論文 参考訳（メタデータ） (2022-01-28T16:27:21Z) - 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) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Provable Fictitious Play for General Mean-Field Games [111.44976345867005]
静止平均場ゲームのための強化学習アルゴリズムを提案する。
目標は、ナッシュ均衡を構成する平均場状態と定常政策のペアを学ぶことである。
論文 参考訳（メタデータ） (2020-10-08T18:46:48Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。