Source-linked AI summary
Deep Reinforcement Learning from Self-Play in Imperfect-Information Games
Johannes Heinrich, David Silver
TL;DR
Imperfect-information games are difficult because prior approaches relied on handcrafted abstractions, while standard reinforcement learning can fail to converge. The paper introduces NFSP, which combines fictitious self-play with deep reinforcement learning to learn approximate Nash equilibria without prior domain knowledge. NFSP approached equilibrium in Leduc poker and approached superhuman, abstraction-based performance in real-world-scale Limit Texas Hold’em.
Problem
Real-world-scale imperfect-information games require approximate Nash equilibria, but prior approaches relied on handcrafted abstractions and common reinforcement learning methods failed to converge.
Method
NFSP combines fictitious self-play with deep reinforcement learning to learn approximate Nash equilibria directly from self-play experience without prior domain knowledge.
Results
NFSP approached a Nash equilibrium in Leduc poker and approached the performance of state-of-the-art, superhuman methods in Limit Texas Hold’em.
Takeaways & Limitations
NFSP can learn approximate equilibria and competitive strategies in imperfect-information poker from scratch without explicit prior knowledge.
Takeaways & Limitations
The work focuses on imperfect-information two-player zero-sum games, though the authors suggest NFSP may extend to cooperative, potential, and continuous-action games.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets imperfect-information games where standard reinforcement learning may fail to converge and game-theoretic methods lack scalable pattern learning. NFSP combines fictitious self-play with deep reinforcement learning to learn approximate Nash equilibria without prior domain knowledge.
- Imperfect-information games create high-dimensional decision problems relevant to real-world domains such as security, trading, and traffic control.
- Many machine learning methods near optimality in perfect-information games fail to converge in imperfect-information games.
- NFSP combines fictitious self-play with neural network function approximation to learn approximate Nash equilibria.Its agents use reinforcement learning for approximate best responses and supervised learning to model average historical strategies.
- NFSP learns directly from self-play experience without engineering game abstractions or using prior domain knowledge.
- In Leduc poker NFSP approached a Nash equilibrium, while in Limit Texas Hold’em it approached the performance of superhuman methods using handcrafted abstractions.
2 Background
The background defines reinforcement learning and imperfect-information extensive-form games, then introduces fictitious play and its machine-learning approximation. FSP replaces exact best-response and average-strategy computations with reinforcement and supervised learning.
- Reinforcement Learning: Reinforcement-learning agents improve policies through interaction with an environment to maximize expected future rewards.Agents may learn from transition tuples containing states, actions, rewards, and successor states.
- Extensive-Form Games: In imperfect-information extensive-form games, players observe only their information states and choose behavioural strategies mapping those states to action distributions.Perfect recall means a current information state implies the sequence of that player’s prior information states and actions.
- Extensive-Form Games: A Nash equilibrium is a strategy profile in which each player uses a best response to the other players and cannot gain by deviating.An approximate Nash equilibrium allows approximate best responses.
- Fictitious Self-Play: Fictitious play has players choose best responses to opponents’ average behaviour, with convergence guarantees in classes including two-player zero-sum games.
- Fictitious Self-Play: FSP approximates extensive-form fictitious play by replacing best-response computation with reinforcement learning and average-strategy updates with supervised learning.Agents store transition experience separately from their own behavioural experience to support the two learning processes.
3 Neural Fictitious Self-Play
NFSP combines fictitious self-play with neural networks, using separate memories and policies to learn approximate best responses and average historical behaviour during self-play.
- NFSP combines fictitious self-play with neural network function approximation for learning in extensive-form imperfect-information games.Each agent uses separate action-value and average-policy networks trained from distinct experience memories.
- Agents store game transitions in MRL and best-response behaviour in MSL, treating them as reinforcement-learning and supervised-classification datasets.MRL is a circular buffer, while MSL uses reservoir sampling for historical best responses.
- The average-policy network learns to match historical behaviour, while the agent acts from a mixture of its average strategy and best-response strategy.The best response is represented by an epsilon-greedy policy derived from the action-value network.
- The anticipatory mixture resolves the conflict between learning off-policy best responses and collecting the best-response behaviour needed to train the average policy.Without this mechanism, playing only the average policy would not generate the required best-response experience.
- NFSP uses anticipatory dynamics so agents respond to opponents’ anticipated average strategies while sampling their own best responses.The mixture policy is σ ≡ (1 −η)ˆπ + η ˆβ, enabling best-response learning and average-policy training from the same self-play process.
4 Experiments
The experiments evaluate NFSP in Leduc Hold’em and Limit Texas Hold’em, measuring equilibrium proximity, component stability, and performance against established poker agents. NFSP approached equilibrium in Leduc and achieved competitive performance in Limit Texas Hold’em, while DQN failed to converge to a Nash equilibrium.
- Evaluation setup: Exploitability measures the expected average payoff of a best-response profile against a strategy profile; exploitability 2δ implies at least a δ-Nash equilibrium.The experiments primarily measure exploitability in two-player zero-sum games.
- Evaluation setup: NFSP agents learn directly from poker interaction without engineered higher-level features or handcrafted game abstractions.Poker information states were encoded in a domain-independent way using k-of-n representations for cards.
- 4.1 Leduc Hold’em: NFSP achieved an exploitability of 0.06 in Leduc Hold’em and approached Nash equilibria across network architectures.This level was typically reached by full-width XFP after around 1000 full-width iterations.
- 4.1 Leduc Hold’em: Removing or altering NFSP components degraded performance: sliding-window experience storage caused divergence, while high anticipatory parameters produced a plateau.Exponentially averaged reservoir sampling produced noisy performance in the component study.
- 4.2 Comparison to DQN: DQN’s deterministic strategy was highly exploitable, and its average behaviour did not approach a Nash equilibrium.NFSP generated a smoother data distribution through slowly changing anticipated average policies, whereas DQN’s experience was narrow and highly correlated.
- 4.3 Limit Texas Hold’em: NFSP’s average and greedy-average strategies improved stably in Limit Texas Hold’em, reaching approximately -50 and -20 mbb/h against SmooCT.The greedy-average strategy achieved win rates similar to the top half of ACPC 2014 computer agents and was competitive with superhuman programs.
5 Related work
Prior game-playing systems often relied on human expertise or exhaustive full-width reasoning, while NFSP targets scalable, sample-based learning in imperfect-information games without prior domain knowledge.
- Human expert knowledge has supported strong game-playing systems but can be expensive, biased, and limiting when suboptimal.
- Full-width algorithms can be prohibitively expensive because they implicitly reason over all information states at each iteration.
- NFSP instead learns from sampled interactions without requiring exhaustive state enumeration or a model of game dynamics.
- Temporal-difference methods that work in perfect-information games do not generally converge in imperfect-information games, and DQN failed to approach Nash equilibrium in adaptive Leduc Hold’em.
- The paper focuses on imperfect-information two-player zero-sum games, while fictitious play also has guarantees in cooperative and potential games.
6 Conclusion
The paper introduces NFSP as an end-to-end deep reinforcement learning approach for approximate Nash equilibria from self-play. It reports reliable convergence in small poker and competitive performance in a real-world-scale imperfect-information game without explicit prior knowledge.
- NFSP is presented as the first end-to-end deep reinforcement learning approach to learning approximate Nash equilibria of imperfect-information games from self-play.
- NFSP is scalable without prior domain knowledge and is reported as the first deep reinforcement learning method known to converge to approximate Nash equilibria in self-play.
- NFSP converged reliably to approximate Nash equilibria in a small poker game, whereas DQN’s greedy and average strategies did not.
- NFSP learned from scratch a strategy competitive with superhuman programs in a real-world-scale imperfect-information game without explicit prior knowledge.
A Robustness of XFP
The experiments test how incremental averaging, approximation error, and noisy best-response computation affect full-width XFP. Smaller stepsizes improve asymptotic performance but reduce initial performance, while added noise lowers performance without preventing continued improvement.
- XFP experiments replace perfect averaging with incremental strategy updates and exact table lookup with epsilon-error approximation.
- Figure 3 compares XFP performance under default, 1/T, and constant stepsizes for strategy updates.
- Smaller stepsizes produce improved asymptotic performance but lower initial performance, while constant stepsizes appear to plateau rather than diverge.
- Exponentially averaged reservoir sampling may be viable because exponential averaging approximately corresponds to using a constant stepsize.
- XFP with stepsize 1 is equivalent to full-width iterated best response, which the results suggest does not generally converge in imperfect-information games.
- With noise added to dynamic-programming best responses, performance decreases monotonically but remains stable and continues improving at all tested noise levels.