論文の概要: Efficient Policy Space Response Oracles

• arxiv url: http://arxiv.org/abs/2202.00633v1
• Date: Fri, 28 Jan 2022 17:54:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-02 15:38:17.819149
• Title: Efficient Policy Space Response Oracles
• Title（参考訳）: 効率的なポリシー空間対応 oracle
• Authors: Ming Zhou, Jingxiao Chen, Ying Wen, Weinan Zhang, Yaodong Yang, Yong Yu
• Abstract要約: ポリシー空間応答 Oracle 法 (PSRO) は、2プレイヤーゼロサムゲームにおけるナッシュ均衡の一般解を提供する。 我々の開発の中心は、制限なし(URR)ゲームにおけるミニマックス最適化の導入である。 壁面時間, 10倍のデータ効率, および既存のPSRO法と同様のエクスプロイザビリティを, Kuhn と Leduc Poker のゲームで50倍高速化したことを報告した。
• 参考スコア（独自算出の注目度）: 61.71849698253696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Policy Space Response Oracle method (PSRO) provides a general solution to Nash equilibrium in two-player zero-sum games but suffers from two problems: (1) the computation inefficiency due to consistently evaluating current populations by simulations; and (2) the exploration inefficiency due to learning best responses against a fixed meta-strategy at each iteration. In this work, we propose Efficient PSRO (EPSRO) that largely improves the efficiency of the above two steps. Central to our development is the newly-introduced subroutine of minimax optimization on unrestricted-restricted (URR) games. By solving URR at each step, one can evaluate the current game and compute the best response in one forward pass with no need for game simulations. Theoretically, we prove that the solution procedures of EPSRO offer a monotonic improvement on exploitability. Moreover, a desirable property of EPSRO is that it is parallelizable, this allows for efficient exploration in the policy space that induces behavioral diversity. We test EPSRO on three classes of games and report a 50x speedup in wall-time, 10x data efficiency, and similar exploitability as existing PSRO methods on Kuhn and Leduc Poker games.
• Abstract（参考訳）: ポリシー空間応答 oracle method (psro)は、2人プレイのゼロサムゲームにおけるnash均衡に対する一般的な解決策を提供するが、(1)シミュレーションによって現在の人口を一貫して評価することによる計算効率の非効率、(2)各イテレーションにおける固定されたメタストラテジーに対する最善の反応を学ぶことによる探索効率の非効率の2つの問題に苦しむ。 本稿では,上記の2つのステップの効率を大幅に向上させるEPSRO(Efficient PSRO)を提案する。 我々の開発の中心は、制限なし(URR)ゲームにおけるミニマックス最適化の導入されたサブルーチンである。 各ステップでURRを解くことで、現在のゲームを評価し、ゲームシミュレーションを必要とせずに、1回のフォワードパスでベストレスポンスを計算することができる。 理論的には、ESPROの解法が、攻撃性に対する単調な改善をもたらすことを証明している。 さらに、ESPROの望ましい性質は、並列化可能であり、行動多様性を誘導する政策空間の効率的な探索を可能にすることである。 我々は,EPSROを3種類のゲームでテストし,壁面時間における50倍の高速化,10倍のデータ効率,および既存のKuhnおよびLeduc PokerゲームにおけるPSRO手法と同様のエクスプロイザビリティを報告した。

関連論文リスト

• Self-adaptive PSRO: Towards an Automatic Population-based Game Solver [34.326819257554874]
  一般のアルゴリズムフレームワークとしてのポリシー空間対応オラクル(PSRO)は、2つのプレイヤーゼロサムゲームの平衡ポリシーの学習において最先端のパフォーマンスを達成した。 我々はPSROフレームワークにおける最適パラメータ値を自己適応的に決定する可能性について検討する。 様々な2プレイヤーゼロサムゲームの実験は、異なるベースラインに対するSPSROの優位性を示している。
  論文  参考訳（メタデータ） (2024-04-17T07:40:57Z)
• 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)
• 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)
• DORO: Distributional and Outlier Robust Optimization [98.44757325531631]
  本稿では,分散ロバスト最適化のためのDOROのフレームワークを提案する。 このアプローチのコアとなるのは、DROがオーバーフィットして潜在的な外れ値に収まらないような、洗練されたリスク関数である。 提案手法の有効性を理論的に証明し, DOROがDROの性能と安定性を向上することを示す。
  論文  参考訳（メタデータ） (2021-06-11T02:59:54Z)
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning [8.819672165548477]
  本稿では,マルチプルオプティマス(POMO)を用いたポリシー最適化について紹介する。 POMOは、幅広いCO問題に適用可能であり、CO溶液の表現における対称性を利用するように設計されている。 我々は,旅行セールスマン(TSP),キャパシタンドカールーティング(CVRP),0-1knapsack(KP)の3つの一般的なNPハード問題を解くことで,POMOの有効性を実証した。
  論文  参考訳（メタデータ） (2020-10-30T00:57:50Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。 本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-17T20:19:25Z)
• 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)

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

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