Deep Reinforcement Learning from Self-Play in Imperfect-Information Games (2016-03-03T00:00:00.000000Z)

TL;DR

This paper introduces the first scalable end-to-end approach to learning approximate Nash equilibria without prior domain knowledge, and combines fictitious self-play with deep reinforcement learning.

Abstract

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.

Authors

David Silver

21 papers

Johannes Heinrich

1 papers

TL;DR

Abstract

Authors

References118 items

Dynamic Programming

The Predictron: End-To-End Learning and Planning

Mastering the game of Go with deep neural networks and tree search

Poker-CNN: A Pattern Learning Strategy for Making Draws and Bets in Poker Games Using Convolutional Networks

Continuous control with deep reinforcement learning

Smooth UCT Search in Computer Poker

Optimal Network Security Hardening Using Attack Graph Games

Fictitious Self-Play in Extensive-Form Games

Training Deep Convolutional Neural Networks to Play Go

Endgame Solving in Large Imperfect-Information Games

Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit Texas Hold'em Agent

Online Monte Carlo Counterfactual Regret Minimization for Search in Imperfect Information Games

Human-level control through deep reinforcement learning

Monte Carlo Planning Method Estimates Planning Horizons during Interactive Social Exchange

Heads-up limit hold’em poker is solved

Move Evaluation in Go Using Deep Convolutional Neural Networks

Solving Games with Functional Regret Estimation

An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information

Exponential Reservoir Sampling for Streaming Language Models

Extensive-form game abstraction with bounds

TacTex'13: A Champion Adaptive Power Trading Agent

Deep learning in neural networks: An overview

Convergence of Monte Carlo Tree Search in Simultaneous Move Games

Evaluating state-space abstractions in extensive-form games

A parameterized family of equilibrium profiles for three-player kuhn poker

Solving Imperfect Information Games Using Decomposition

Finding Optimal Abstract Strategies in Extensive-Form Games

Lossy stochastic game abstraction with bounds

The grand challenge of computer Go

A Survey of Monte Carlo Tree Search Methods

Security and Game Theory - Algorithms, Deployed Systems, Lessons Learned

Automatic Construction of Temporally Extended Actions for MDPs Using Bisimulation Metrics

Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling

Computer poker: A review

Multiple Tree for Partially Observable Monte-Carlo Tree Search

Constructing Skill Trees for Reinforcement Learning Agents from Demonstration Trajectories

Monte-Carlo Planning in Large POMDPs

The State of Solving Large Incomplete-Information Games, and Application to Poker

Using counterfactual regret minimization to create competitive multiplayer poker agents

Smoothing Techniques for Computing Nash Equilibria of Sequential Games

Bootstrapping from Game Tree Search

Monte Carlo Sampling for Regret Minimization in Extensive Games

A Practical Use of Imperfect Recall

Computing Equilibria in Multiplayer Stochastic Games of Imperfect Information

Reinforcement learning for robot soccer

Opportunities for multiagent systems and multiagent reinforcement learning in traffic control

Abstraction pathologies in extensive games

Game Theory of Mind

Gradient-Based Algorithms for Finding Nash Equilibria in Extensive Form Games

Regret Minimization in Games with Incomplete Information

A Fast Bundle-based Anytime Algorithm for Poker and other Convex Games

Bandit Based Monte-Carlo Planning

Generalised weakened fictitious play

A Competitive Texas Hold'em Poker Player via Automated Abstraction and Real-Time Equilibrium Computation

Reinforcement learning for optimized trade execution

Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search

Tree-Based Batch Mode Reinforcement Learning

Neural Fitted Q Iteration - First Experiences with a Data Efficient Neural Reinforcement Learning Method

Bayes' Bluff: Opponent Modelling in Poker

Stochastic Approximations and Differential Inclusions

A Fictitious Play Approach to Large-Scale Optimization

Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria

Dynamic abstraction in reinforcement learning via clustering

Approximating game-theoretic optimal strategies for full-scale poker

The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics

Finite-time Analysis of the Multiarmed Bandit Problem

Deep Blue

The challenge of poker

Rational and Convergent Learning in Stochastic Games

Automatic Discovery of Subgoals in Reinforcement Learning using Diverse Density

Policy Gradient Methods for Reinforcement Learning with Function Approximation

Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning

Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition

Planning and Acting in Partially Observable Stochastic Domains

Search in Games with Incomplete Information: A Case Study Using Bridge Card Play

Fictitious Play in Extensive Form Games