DREAM: Deep Regret minimization with Advantage baselines and Model-free learning

• URL: http://arxiv.org/abs/2006.10410v2
• Date: Sun, 29 Nov 2020 12:23:34 GMT
• Title: DREAM: Deep Regret minimization with Advantage baselines and Model-free learning
• Authors: Eric Steinberger, Adam Lerer, Noam Brown
• Abstract summary: We introduce DREAM, a deep reinforcement learning algorithm that finds optimal strategies in imperfect-information games with multiple agents. Our primary innovation is an effective algorithm that, in contrast to other regret-based deep learning algorithms, does not require access to a perfect simulator of the game to achieve good performance.
• Score: 24.273841968933475
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce DREAM, a deep reinforcement learning algorithm that finds optimal strategies in imperfect-information games with multiple agents. Formally, DREAM converges to a Nash Equilibrium in two-player zero-sum games and to an extensive-form coarse correlated equilibrium in all other games. Our primary innovation is an effective algorithm that, in contrast to other regret-based deep learning algorithms, does not require access to a perfect simulator of the game to achieve good performance. We show that DREAM empirically achieves state-of-the-art performance among model-free algorithms in popular benchmark games, and is even competitive with algorithms that do use a perfect simulator.

Related papers

• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• Online Learning and Solving Infinite Games with an ERM Oracle [20.1330044382824]
  We propose an algorithm for online binary classification setting that relies solely on ERM oracle calls. We show that it has finite regret in the realizable setting and sublinearly growing regret in the agnostic setting. Our algorithms apply to both binary-valued and real-valued games and can be viewed as providing justification for the wide use of double oracle and multiple oracle algorithms in the practice of solving large games.
  arXiv  Detail & Related papers  (2023-07-04T12:51:21Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
  arXiv  Detail & Related papers  (2022-10-30T22:58:22Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  Learning from repeated play in a fixed zero-sum game is a classic problem in game theory and online learning. We develop a single parameter-free algorithm that simultaneously enjoys favorable guarantees under three performance measures. Our algorithm is based on a two-layer structure with a meta-algorithm learning over a group of black-box base-learners satisfying a certain property.
  arXiv  Detail & Related papers  (2022-01-30T06:10:04Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  We study last-iterate convergence of optimistic algorithms in sequential games. We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
  arXiv  Detail & Related papers  (2021-06-27T22:02:26Z)
• Discovering Multi-Agent Auto-Curricula in Two-Player Zero-Sum Games [31.97631243571394]
  We introduce a framework, LMAC, that automates the discovery of the update rule without explicit human design. Surprisingly, even without human design, the discovered MARL algorithms achieve competitive or even better performance. We show that LMAC is able to generalise from small games to large games, for example training on Kuhn Poker and outperforming PSRO.
  arXiv  Detail & Related papers  (2021-06-04T22:30:25Z)
• Combining Deep Reinforcement Learning and Search for Imperfect-Information Games [30.520629802135574]
  We present ReBeL, a framework for self-play reinforcement learning and search provably converges to a Nash equilibrium in zero-sum games. We also show ReBeL achieves performance in heads-up no-limit Texas hold'em poker, while using far less domain knowledge than any prior poker AI.
  arXiv  Detail & Related papers  (2020-07-27T15:21:22Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)
• Model-Based Reinforcement Learning for Atari [89.3039240303797]
  We show how video prediction models can enable agents to solve Atari games with fewer interactions than model-free methods. Our experiments evaluate SimPLe on a range of Atari games in low data regime of 100k interactions between the agent and the environment.
  arXiv  Detail & Related papers  (2019-03-01T15:40:19Z)

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.