Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games

• URL: http://arxiv.org/abs/2207.06541v1
• Date: Wed, 13 Jul 2022 22:55:51 GMT
• Title: Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games
• Authors: Stephen McAleer, JB Lanier, Kevin Wang, Pierre Baldi, Roy Fox, Tuomas Sandholm
• Abstract summary: We introduce emphSelf-Play PSRO (SP-PSRO), a method that adds an approximately optimal policy to the population in each iteration. SP-PSRO empirically tends to converge much faster than APSRO and in many games converge in just a few iterations.
• Score: 69.5064797859053
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: In competitive two-agent environments, deep reinforcement learning (RL) methods based on the \emph{Double Oracle (DO)} algorithm, such as \emph{Policy Space Response Oracles (PSRO)} and \emph{Anytime PSRO (APSRO)}, iteratively add RL best response policies to a population. Eventually, an optimal mixture of these population policies will approximate a Nash equilibrium. However, these methods might need to add all deterministic policies before converging. In this work, we introduce \emph{Self-Play PSRO (SP-PSRO)}, a method that adds an approximately optimal stochastic policy to the population in each iteration. Instead of adding only deterministic best responses to the opponent's least exploitable population mixture, SP-PSRO also learns an approximately optimal stochastic policy and adds it to the population as well. As a result, SP-PSRO empirically tends to converge much faster than APSRO and in many games converges in just a few iterations.

Related papers

• Fictitious Cross-Play: Learning Global Nash Equilibrium in Mixed Cooperative-Competitive Games [14.979239870856535]
  Self-play (SP) is a popular reinforcement learning framework for solving competitive games. In this work, we develop a novel algorithm, Fictitious Cross-Play (FXP), which inherits the benefits from both frameworks.
  arXiv  Detail & Related papers  (2023-10-05T07:19:33Z)
• Population-size-Aware Policy Optimization for Mean-Field Games [34.80183622480149]
  We study how the optimal policies of agents evolve with the number of agents (population size) in mean-field games. We propose Population-size-Aware Policy Optimization (PAPO), which unifies two natural options (augmentation and hypernetwork) and significantly better performance. PAPO consists of three components: i) the population-size encoding which transforms the original value of population size to an equivalent encoding to avoid training collapse, ii) a hypernetwork to generate a distinct policy for each game conditioned on the population size, andiii) the population size as an additional input to the generated policy.
  arXiv  Detail & Related papers  (2023-02-07T10:16:00Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  We study the problem of finding an approximate Nash equilibrium of games with continuous action sets. We propose two new methods that minimize an approximation of exploitability with respect to the strategy profile.
  arXiv  Detail & Related papers  (2023-01-20T23:55:30Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  We show that the state-wise average policy of this algorithm converges to an approximate Nash equilibrium (NE) of the game. We extend this algorithm to multi-player general Markov Games and show a $mathcalwidetildeO(T-1/2)$ convergence rate to Correlated Equilibria (CCE)
  arXiv  Detail & Related papers  (2022-06-06T14:23:13Z)
• Efficient Policy Space Response Oracles [61.71849698253696]
  Policy Space Response Oracle method (PSRO) provides a general solution to Nash equilibrium in two-player zero-sum games. Central to our development is the newly-introduced of minimax optimization on unrestricted-restricted (URR) games. We report a 50x speedup in wall-time, 10x data efficiency, and similar exploitability as existing PSRO methods on Kuhn and Leduc Poker games.
  arXiv  Detail & Related papers  (2022-01-28T17:54:45Z)
• Anytime Optimal PSRO for Two-Player Zero-Sum Games [17.821479538423155]
  Policy Space Response Oracles (PSRO) is a reinforcement learning algorithm for games that can handle continuous actions. AODO is a double oracle algorithm for 2-player zero-sum games that converges to a Nash equilibrium. We show that our methods achieve far lower exploitability than DO and PSRO and never increase exploitability.
  arXiv  Detail & Related papers  (2022-01-19T16:34:11Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)
• Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games [11.866835246140647]
  Policy Space Response Oracles (PSRO) is a deep reinforcement learning algorithm guaranteed to converge to an approximate Nash equilibrium. We introduce Pipeline PSRO, the first scalable general method for finding approximate Nash equilibria in large games. We also introduce an open-source environment for Barrage Stratego, a variant of Stratego with an approximate game complexity tree of $1050$.
  arXiv  Detail & Related papers  (2020-06-15T17:17:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.