論文の概要: Pipeline PSRO: A Scalable Approach for Finding Approximate Nash
Equilibria in Large Games
- arxiv url: http://arxiv.org/abs/2006.08555v2
- Date: Thu, 18 Feb 2021 19:26:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 03:42:13.570928
- Title: Pipeline PSRO: A Scalable Approach for Finding Approximate Nash
Equilibria in Large Games
- Title（参考訳）: Pipeline PSRO: 大規模ゲームにおける近似ナッシュ平衡を見つけるためのスケーラブルなアプローチ
- Authors: Stephen McAleer, John Lanier, Roy Fox, Pierre Baldi
- Abstract要約: ポリシー空間応答オラクル(英: Policy Space Response Oracles、PSRO)は、近似的なナッシュ均衡に収束することが保証される深い強化学習アルゴリズムである。
大規模ゲームにおける近似的なナッシュ平衡を求めるための,最初のスケーラブルな一般化手法であるPipeline PSROを紹介する。
また,ストラテゴの変種であるBarrage Strategoのオープンソース環境についても紹介する。
- 参考スコア（独自算出の注目度）: 11.866835246140647
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding approximate Nash equilibria in zero-sum imperfect-information games
is challenging when the number of information states is large. Policy Space
Response Oracles (PSRO) is a deep reinforcement learning algorithm grounded in
game theory that is guaranteed to converge to an approximate Nash equilibrium.
However, PSRO requires training a reinforcement learning policy at each
iteration, making it too slow for large games. We show through counterexamples
and experiments that DCH and Rectified PSRO, two existing approaches to scaling
up PSRO, fail to converge even in small games. We introduce Pipeline PSRO
(P2SRO), the first scalable general method for finding approximate Nash
equilibria in large zero-sum imperfect-information games. P2SRO is able to
parallelize PSRO with convergence guarantees by maintaining a hierarchical
pipeline of reinforcement learning workers, each training against the policies
generated by lower levels in the hierarchy. We show that unlike existing
methods, P2SRO converges to an approximate Nash equilibrium, and does so faster
as the number of parallel workers increases, across a variety of imperfect
information games. We also introduce an open-source environment for Barrage
Stratego, a variant of Stratego with an approximate game tree complexity of
$10^{50}$. P2SRO is able to achieve state-of-the-art performance on Barrage
Stratego and beats all existing bots. Experiment code is available
athttps://github.com/JBLanier/pipeline-psro.
- Abstract（参考訳）: 情報状態の数が多ければゼロサム不完全情報ゲームにおいて近似ナッシュ平衡を求めることは困難である。
ポリシー空間応答オラクル (psro) はゲーム理論に基づく深い強化学習アルゴリズムであり、近似ナッシュ平衡に収束することが保証されている。
しかしPSROは、各イテレーションで強化学習ポリシーをトレーニングする必要があるため、大きなゲームでは遅すぎる。
既存の2つのPSROスケールアップ手法であるDCHとRectified PSROは,小型ゲームにおいても収束しないことを示す。
大規模ゼロサム不完全情報ゲームにおける近似ナッシュ平衡を求める最初のスケーラブルな汎用手法であるパイプラインpsro (p2sro) を提案する。
P2SROは、強化学習者の階層的なパイプラインを維持することにより、PSROを収束保証で並列化することができる。
既存の手法とは異なり、p2sroはナッシュ平衡に収束し、様々な不完全な情報ゲームを通じて並列作業者の数が増えるほど高速である。
また,ストラテゴの変種であるBarrage Strategoのオープンソース環境についても紹介する。
P2SROは、Barrage Strategoで最先端のパフォーマンスを達成でき、既存のボットをすべて破る。
実験コードはhttps://github.com/jblanier/pipeline-psroで利用可能である。
関連論文リスト
- Policy Abstraction and Nash Refinement in Tree-Exploiting PSRO [10.137357924571262]
Policy Space Response Oracles (PSRO) は、従来の分析手法では複雑すぎるゲームを解決するために、実験的なゲーム理論解析を深層強化学習 (DRL) とインターリーブする。
ツリー露光PSRO (TE-PSRO) は、広義に粗い経験ゲームモデルを反復的に構築するこのアプローチの変種である。
TE-PSROには2つの方法論的進歩があり、不完全情報の複雑なゲームへの適用性を高めている。
論文 参考訳（メタデータ） (2025-02-05T05:48:16Z) - On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
論文 参考訳（メタデータ） (2024-03-13T01:51:30Z) - Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。
本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
論文 参考訳（メタデータ） (2024-01-10T12:56:24Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games [69.5064797859053]
本稿では,各イテレーションの個体群に対して,ほぼ最適なポリシーを付加する手法であるemphSelf-Play PSRO(SP-PSRO)を紹介する。
SP-PSRO は経験的に APSRO よりもはるかに早く収束する傾向があり、多くのゲームではほんの数イテレーションで収束する。
論文 参考訳（メタデータ） (2022-07-13T22:55:51Z) - Efficient Policy Space Response Oracles [61.71849698253696]
ポリシー空間応答 Oracle 法 (PSRO) は、2プレイヤーゼロサムゲームにおけるナッシュ均衡の一般解を提供する。
我々の開発の中心は、制限なし(URR)ゲームにおけるミニマックス最適化の導入である。
壁面時間, 10倍のデータ効率, および既存のPSRO法と同様のエクスプロイザビリティを, Kuhn と Leduc Poker のゲームで50倍高速化したことを報告した。
論文 参考訳（メタデータ） (2022-01-28T17:54:45Z) - Anytime Optimal PSRO for Two-Player Zero-Sum Games [17.821479538423155]
Policy Space Response Oracles (PSRO) は、継続的なアクションを扱うことができるゲームのための強化学習アルゴリズムである。
AODOは、ナッシュ均衡に収束する2プレイヤーゼロサムゲームのための二重オラクルアルゴリズムである。
提案手法は, DOやPSROよりもはるかに低いエクスプロイザビリティを実現し, エクスプロイザビリティを向上しないことを示す。
論文 参考訳（メタデータ） (2022-01-19T16:34:11Z) - XDO: A Double Oracle Algorithm for Extensive-Form Games [14.823154995416997]
我々は,インフォステート数を線形に近似ナッシュ平衡に収束する拡張型二重オラクルアルゴリズムを提案する。
ゲームの根元で最高のレスポンスをミックスするPSROとは異なり、XDOはすべてのインフォステートで最高のレスポンスをミックスします。
改良されたLeducポーカーゲームの実験では、XDOはCFRよりも11倍、PSROやXFPより82倍低いエクスプロイラビリティを実現している。
論文 参考訳（メタデータ） (2021-03-11T03:05:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。