Combining Deep Reinforcement Learning and Search for Imperfect-Information Games

Abstract

The combination of deep reinforcement learning and search at both training and test time is a powerful paradigm that has led to a number of successes in single-agent settings and perfect-information games, best exemplified by AlphaZero. However, prior algorithms of this form cannot cope with imperfect-information games. This paper presents ReBeL, a general framework for self-play reinforcement learning and search that provably converges to a Nash equilibrium in any two-player zero-sum game. In the simpler setting of perfect-information games, ReBeL reduces to an algorithm similar to AlphaZero. Results in two different imperfect-information games show ReBeL converges to an approximate Nash equilibrium. We also show ReBeL achieves superhuman performance in heads-up no-limit Texas hold'em poker, while using far less domain knowledge than any prior poker AI.

References in corpus (12)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Gaussian Error Linear Units (GELUs)
• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• Thinking Fast and Slow with Deep Learning and Tree Search
• Online Learning with Predictable Sequences
• Fast Convergence of Regularized Learning in Games
• Safe and Nested Subgame Solving for Imperfect-Information Games
• Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning
• Finding Friend and Foe in Multi-Agent Games
• Solving Large Sequential Games with the Excessive Gap Technique
• AIVAT: A New Variance Reduction Technique for Agent Evaluation in Imperfect Information Games
• Problems with the EFG formalism: a solution attempt using observations

Cited by in corpus (9)

• AI in Human-computer Gaming: Techniques, Challenges and Opportunities
• Human-Level Performance in No-Press Diplomacy via Equilibrium Search
• Joint Policy Search for Multi-agent Collaboration with Imperfect Information
• Scalable Online Planning via Reinforcement Learning Fine-Tuning
• Sound Algorithms in Imperfect Information Games
• Explainable Biomedical Recommendations via Reinforcement Learning Reasoning on Knowledge Graphs
• Evolutionary Dynamics and $\Phi$-Regret Minimization in Games
• No-Press Diplomacy from Scratch
• Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess