2016

Deep Reinforcement Learning from Self-Play in Imperfect-Information Games

Heinrich, Johannes, Silver, David

Understand

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.

Built on

Iterative solution of games by fictitious play
Brown, G. W. (1951) · 1951
Earlier work this paper cites.
An iterative method of solving a game
Robinson, J. (1951) · 1951
Earlier work this paper cites.
Some studies in machine learning using the game of checkers
Samuel, A. L. (1959) · 1959
Earlier work this paper cites.
Random sampling with a reservoir
Vitter, J. S. (1985) · 1985
Earlier work this paper cites.
Bounded rationality
Selten, R. (1990) · 1990
Earlier work this paper cites.
Game Theory: Analysis of Conflict
Myerson, R. B. (1991) · 1991
Earlier work this paper cites.
Self-improving reactive agents based on reinforcement learning, planning and teaching
Lin, L.-J. (1992) · 1992
Earlier work this paper cites.
Q-learning
Watkins, C. J. and Dayan, P. (1992) · 1992
Earlier work this paper cites.
Temporal difference learning and td-gammon
Tesauro, G. (1995) · 1995
Earlier work this paper cites.
Fictitious play property for games with identical interests
Monderer, D. and Shapley, L. S. (1996) · 1996
Earlier work this paper cites.
Efficient computation of behavior strategies
Von Stengel, B. (1996) · 1996
Earlier work this paper cites.
The theory of learning in games
Fudenberg, D. (1998) · 1998
Earlier work this paper cites.
Reinforcement learning: An introduction
Sutton, R. S. and Barto, A. G. (1998) · 1998
Earlier work this paper cites.

Similar

Rational and convergent learning in stochastic games
Bowling, M. and Veloso, M. (2001) · 2001
Cited alongside, same era.
Deep blue
Campbell, M., Hoane, A. J., and Hsu, F.-h. (2002) · 2002
Cited alongside, same era.
Tree-based batch mode reinforcement learning
Ernst, D., Geurts, P., and Wehenkel, L. (2005) · 2005
Cited alongside, same era.
A fictitious play approach to large-scale optimization
Lambert III, T. J., Epelman, M. A., and Smith, R. L. (2005) · 2005
Cited alongside, same era.
Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method
Riedmiller, M. (2005) · 2005
Cited alongside, same era.
Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria
Shamma, J. S. and Arslan, G. (2005) · 2005
Cited alongside, same era.
Generalised weakened fictitious play
Leslie, D. S. and Collins, E. J. (2006) · 2006
Cited alongside, same era.
Reinforcement learning for optimized trade execution
Nevmyvaka, Y., Feng, Y., and Kearns, M. (2006) · 2006
Cited alongside, same era.
Gradient-based algorithms for finding Nash equilibria in extensive form games
Gilpin, A., Hoda, S., Pena, J., and Sandholm, T. (2007) · 2007
Cited alongside, same era.
Regret minimization in games with incomplete information
Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. (2007) · 2007
Cited alongside, same era.
Opportunities for multiagent systems and multiagent reinforcement learning in traffic control
Bazzan, A. L. (2009) · 2009
Cited alongside, same era.
Security and game theory: algorithms, deployed systems, lessons learned
Tambe, M. (2011) · 2011
Cited alongside, same era.

Then

Evaluating state-space abstractions in extensive-form games
Johanson, M., Burch, N., Valenzano, R., and Bowling, M. (2013) · 2013
Later among the works it cites.
Further Limit Hold ’em: Exploring the Model Poker Game
Newall, P. (2013) · 2013
Later among the works it cites.
Exponential reservoir sampling for streaming language models
Osborne, M., Lall, A., and Van Durme, B. (2014) · 2014
Later among the works it cites.
Tactex’13: a champion adaptive power trading agent
Urieli, D. and Stone, P. (2014) · 2014
Later among the works it cites.
Heads-up limit hold’em poker is solved
Bowling, M., Burch, N., Johanson, M., and Tammelin, O. (2015) · 2015
Later among the works it cites.
Training deep convolutional neural networks to play go
Clark, C. and Storkey, A. (2015) · 2015
Later among the works it cites.
Fictitious self-play in extensive-form games
Heinrich, J., Lanctot, M., and Silver, D. (2015) · 2015
Later among the works it cites.
Smooth UCT search in computer poker
Heinrich, J. and Silver, D. (2015) · 2015
Later among the works it cites.
Continuous control with deep reinforcement learning
Original
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2015) · 2015
Later among the works it cites.
Move evaluation in go using deep convolutional neural networks
Maddison, C. J., Huang, A., Sutskever, I., and Silver, D. (2015) · 2015
Later among the works it cites.
Human-level control through deep reinforcement learning
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015) · 2015
Later among the works it cites.
Solving games with functional regret estimation
Waugh, K., Morrill, D., Bagnell, J. A., and Bowling, M. (2015) · 2015
Later among the works it cites.
Poker-cnn: A pattern learning strategy for making draws and bets in poker games using convolutional networks
Yakovenko, N., Cao, L., Raffel, C., and Fan, J. (2016) · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…