Deep Reinforcement Learning from Self-Play in Imperfect-Information Games
By Johannes Heinrich, David Silver. 2016
468 citations recorded by the source corpus.
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 domain. In this paper we introduce the first scalable end-to-end approach to learning approximate Nash equilibria without prior domain knowledge. Our method combines fictitious self-play with deep reinforcement learning. When applied to Leduc poker, Neural Fictitious Self-Play (NFSP) approached a Nash equilibrium, whereas common reinforcement learning methods diverged. In Limit Texas Holdem, a poker game of real-world scale, NFSP learnt a strategy that approached the performance of state-of-the-art, superhuman algorithms based on significant domain expertise.
Subfields: Artificial Intelligence, Reinforcement Learning, Game & Decision Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Pieter Abbeel
- Yoshua Bengio
- Ruslan Salakhutdinov
- Yuxi Li
- Mohit Bansal
- Shimon Whiteson
- Quoc V. Le
In Reinforcement Learning
- Sergey Levine
- Pieter Abbeel
- Shimon Whiteson
- Yuxi Li
- Jakob N. Foerster
- Chelsea Finn
- David Silver
- Timothy P. Lillicrap
In Game & Decision Theory
Citations in the corpus
- DeepStack: Expert-level artificial intelligence in heads-up no-limit poker (2017, background): “Previous applications of deep learning, though, either are not known to be theoretically sound (47) or have only been applied in small games (48).”
- Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning (2020, background): “While some multi-agent testbeds have emerged, such as Poker (Heinrich and Silver, 2016), Pong (Tampuu et al., 2017), Keepaway Soccer (Stone et al., 2005), or simple gridworld-like environments (Lowe et al., 2017; Leibo et al., 2017; Yang et al., 2018; Zheng et al., 2017), there are currently no…”
- Policy Consolidation for Continual Reinforcement Learning (2019, background): “In practice, however, it has been reported that only training an agent against the most recent version(s) of itself can lead to instabilities during training (Heinrich & Silver, 2016).”
- Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, background): “…a general solution concept and serves as a goal for policy learning and has attracted increasingly significant interests from AI researchers (Heinrich & Silver, 2016; Lanctot et al., 2017; Foerster et al., 2018; Kamra et al., 2019; Han & Hu, 2019; Bai & Jin, 2020; Perolat et al., 2020):…”
- The StarCraft Multi-Agent Challenge (2019, neutral): “Some testbeds have emerged for other multi-agent regimes, such as Poker (Heinrich & Silver, 2016), Pong (Tampuu et al., 2015), Keepaway Soccer (Stone et al., 2005), or simple gridworld-like environments (Lowe et al., 2017; Leibo et al., 2017; Yang et al., 2018; Zheng et al., 2017).”
- Learning with Opponent-Learning Awareness (2017, background): “[21] generalise the ideas of game-theoretic best-response-style algorithms, such as NFSP [17].”
- A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, background): “The input is represented as in [40], which includes one-hot encodings of the private card, public card, and history of actions.”
- Emergent Complexity via Multi-Agent Competition (2017, methodology): “Reinforcement Learning (RL) is exciting because good reinforcement learning algorithms exist [Mnih et al., 2015, Silver et al., 2016, Schulman et al., 2015a, Mnih et al., 2016, Schulman et al., 2015b, Lillicrap et al., 2015, Schulman et al., 2017], allowing us to train agents that accomplish a…”
- A Brief Survey of Deep Reinforcement Learning (2017, neutral): “Other DRL works of note in MARL investigate the effects of learning and sequential decision making in game theory [38, 60].”
- Human-level performance in 3D multiplayer games with population-based reinforcement learning (2018, neutral): “While self-play variants can prove effective in some multi-agent games ( 4, 9, 24, 37, 47, 57, 58 ), these methods can be unstable and in their basic form do not support concurrent training which is crucial for scalability.”
- A survey and critique of multiagent deep reinforcement learning (2018, background): “omains is an open avenue of research. On the role of self-play. Self-play is a cornerstone in MAL with impressive results [147, 127, 145, 346, 143]. While notable results had also been shown in MDRL [173, 193], recent works have also shown that plain self-play does not yield the best results. Howeve”
- Open-Ended Learning Leads to Generally Capable Agents (2021, methodology): “However, we can take ideas from multi-agent training algorithms that eventually converge to a Nash equilibrium (Heinrich and Silver, 2016; Marris et al., 2021; McMahan et al., 2003).”
- Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “Recent years have witnessed sensational advances of reinforcement learning (RL) in many prominent sequential decision-making problems, such as playing the game of Go [1, 2], playing real-time strategy games [3, 4], robotic control [5, 6], playing card games [7, 8], and autonomous driving [9], especi”
- Deep Fictitious Play for Games with Continuous Action Spaces (2019, methodology): “Existing methods which employ stochastic policies do it in domains with discrete action sets since explicit distributions can be maintained over them [4, 8, 9, 17].”
- Neural Replicator Dynamics (2019, methodology): “These include approaches relying on self-play [23], regret minimization [9, 10, 12, 34, 43, 69], and a large body of works that assume a standard centralized learning, decentralized execution paradigm [18, 35, 44, 51].”
- Deep Reinforcement Learning: An Overview (2017, background): “Tesauro (1994) Heinrich and Silver (2016) proposed Neural Fictitious Self-Play (NFSP) to combine fictitious self-play with deep RL to learn approximate Nash equilibria for games of imperfect information in a scalable end-to-end approach without prior domain knowledge.”
- Robust Deep Reinforcement Learning for Security and Safety in Autonomous Vehicle Systems (2018, methodology): “To derive the maximizer action at each time step for each player, we use the following update rule for the Q function [21]:”