論文の概要: Anytime Optimal PSRO for Two-Player Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2201.07700v1
• Date: Wed, 19 Jan 2022 16:34:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-20 15:24:31.130437
• Title: Anytime Optimal PSRO for Two-Player Zero-Sum Games
• Title（参考訳）: ツープレイヤーゼロサムゲームにおける任意のPSRO
• Authors: Stephen McAleer, Kevin Wang, Marc Lanctot, John Lanier, Pierre Baldi, Roy Fox
• Abstract要約: Policy Space Response Oracles (PSRO) は、継続的なアクションを扱うことができるゲームのための強化学習アルゴリズムである。 AODOは、ナッシュ均衡に収束する2プレイヤーゼロサムゲームのための二重オラクルアルゴリズムである。 提案手法は, DOやPSROよりもはるかに低いエクスプロイザビリティを実現し, エクスプロイザビリティを向上しないことを示す。
• 参考スコア（独自算出の注目度）: 17.821479538423155
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Policy Space Response Oracles (PSRO) is a multi-agent reinforcement learning algorithm for games that can handle continuous actions and has empirically found approximate Nash equilibria in large games. PSRO is based on the tabular Double Oracle (DO) method, an algorithm that is guaranteed to converge to a Nash equilibrium, but may increase exploitability from one iteration to the next. We propose Anytime Optimal Double Oracle (AODO), a tabular double oracle algorithm for 2-player zero-sum games that is guaranteed to converge to a Nash equilibrium while decreasing exploitability from iteration to iteration. Unlike DO, in which the meta-strategy is based on the restricted game formed by each player's strategy sets, AODO finds the meta-strategy for each player that minimizes its exploitability against any policy in the full, unrestricted game. We also propose a method of finding this meta-strategy via a no-regret algorithm updated against a continually-trained best response, called RM-BR DO. Finally, we propose Anytime Optimal PSRO, a version of AODO that calculates best responses via reinforcement learning. In experiments on Leduc poker and random normal form games, we show that our methods achieve far lower exploitability than DO and PSRO and never increase exploitability.
• Abstract（参考訳）: ポリシー空間応答オラクル(psro: policy space response oracles)は、連続したアクションを処理できるゲームのためのマルチエージェント強化学習アルゴリズムであり、大規模なゲームで経験的にナッシュ平衡が発見された。 PSROは、Nash平衡に収束することが保証されるが、あるイテレーションから次のイテレーションへのエクスプロイザビリティを高めることができる、表形式のDouble Oracle(DO)メソッドに基づいている。 我々は,繰り返しから繰り返しへの悪用性を低減しつつ,ナッシュ平衡に収束することを保証した2プレイヤゼロサムゲームのための表型二重オラクルアルゴリズムであるAnytime Optimal Double Oracle (AODO)を提案する。 メタストラテジーが各プレイヤーの戦略セットによって形成された制限されたゲームに基づいているdoとは異なり、aodoは、すべての制限のないゲームにおけるポリシーに対する利用性を最小化する各プレイヤーのメタストラテジーを見つける。 また, rm-br doと呼ばれる連続的に学習されるベスト応答に対して更新されるno-regretアルゴリズムを用いて, このメタストラテジーを求める手法を提案する。 最後に,強化学習によるベスト応答を計算するaodoのバージョンであるanytime optimal psroを提案する。 Leduc ポーカーとランダムな正規形式ゲームの実験では、我々の手法は DO や PSRO よりもはるかに低いエクスプロイラビリティを実現し、エクスプロイラビリティは向上しない。

関連論文リスト

• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• 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)
• Online Double Oracle [20.291016382324777]
  本論文では,純粋な戦略の数が巨大あるいは無限である2プレイヤーゼロサムゲームにおける新しい学習アルゴリズムを提案する。 私たちの方法は、$k$がゲームのサイズではない自己再生設定で$mathcalO(sqrtT k log(k))$の後悔の境界を達成します。
  論文  参考訳（メタデータ） (2021-03-13T19:48:27Z)
• 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)
• 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)
• Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games [11.866835246140647]
  ポリシー空間応答オラクル(英: Policy Space Response Oracles、PSRO)は、近似的なナッシュ均衡に収束することが保証される深い強化学習アルゴリズムである。 大規模ゲームにおける近似的なナッシュ平衡を求めるための,最初のスケーラブルな一般化手法であるPipeline PSROを紹介する。 また,ストラテゴの変種であるBarrage Strategoのオープンソース環境についても紹介する。
  論文  参考訳（メタデータ） (2020-06-15T17:17:17Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

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

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