Fast computation of Nash Equilibria in Imperfect Information Games
We introduce and analyze a class of algorithms, called Mirror Ascent against an Improved Opponent (MAIO), for computing Nash equilibria in two-player zero-sum games, both in normal form and in sequential imperfect information form. These algorithms update the policy of each player with a mirror-descent step to minimize the loss of playing against an improved opponent. We establish a convergence result to the set of Nash equilibria where the speed of convergence depends on the amount of improvement of the opponent policies. In addition, if the improved opponent is a best response, then an exponential convergence rate is achieved.
Code (0)
등록된 구현이 없습니다.
Tasks
FormSimilar Papers 제목 키워드 기반
Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games
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 g…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Abstracting Imperfect Information Away from Two-Player Zero-Sum Games
In their seminal work, Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This insight underpins sound …
Vocal Bursts Valence PredictionDeep Reinforcement Learning from Self-Play in Imperfect-Information Games
Many real-world applications can be described as large-scale games of imperfect information. To deal with these challenging domains, prior work has focused on computing Nash equilibria in a handcrafted abstraction of the…
Card GamesDeep Reinforcement LearningGame of Pokerreinforcement-learning+2Computing Nash Equilibria in Multiplayer DAG-Structured Stochastic Games with Persistent Imperfect Information
Many important real-world settings contain multiple players interacting over an unknown duration with probabilistic state transitions, and are naturally modeled as stochastic games. Prior research on algorithms for stoch…
Smooth Nash Equilibria: Algorithms and Complexity
A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, inspired by the ideas of smoothed analysis…