Fictitious Self-Play in Extensive-Form Games

Johannes Heinrich, Marc Lanctot, David Silver
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:805-813, 2015.

Abstract

Fictitious play is a popular game-theoretic model of learning in games. However, it has received little attention in practical applications to large problems. This paper introduces two variants of fictitious play that are implemented in behavioural strategies of an extensive-form game. The first variant is a full-width process that is realization equivalent to its normal-form counterpart and therefore inherits its convergence guarantees. However, its computational requirements are linear in time and space rather than exponential. The second variant, Fictitious Self-Play, is a machine learning framework that implements fictitious play in a sample-based fashion. Experiments in imperfect-information poker games compare our approaches and demonstrate their convergence to approximate Nash equilibria.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-heinrich15, title = {Fictitious Self-Play in Extensive-Form Games}, author = {Heinrich, Johannes and Lanctot, Marc and Silver, David}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {805--813}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/heinrich15.pdf}, url = {https://proceedings.mlr.press/v37/heinrich15.html}, abstract = {Fictitious play is a popular game-theoretic model of learning in games. However, it has received little attention in practical applications to large problems. This paper introduces two variants of fictitious play that are implemented in behavioural strategies of an extensive-form game. The first variant is a full-width process that is realization equivalent to its normal-form counterpart and therefore inherits its convergence guarantees. However, its computational requirements are linear in time and space rather than exponential. The second variant, Fictitious Self-Play, is a machine learning framework that implements fictitious play in a sample-based fashion. Experiments in imperfect-information poker games compare our approaches and demonstrate their convergence to approximate Nash equilibria.} }
Endnote
%0 Conference Paper %T Fictitious Self-Play in Extensive-Form Games %A Johannes Heinrich %A Marc Lanctot %A David Silver %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-heinrich15 %I PMLR %P 805--813 %U https://proceedings.mlr.press/v37/heinrich15.html %V 37 %X Fictitious play is a popular game-theoretic model of learning in games. However, it has received little attention in practical applications to large problems. This paper introduces two variants of fictitious play that are implemented in behavioural strategies of an extensive-form game. The first variant is a full-width process that is realization equivalent to its normal-form counterpart and therefore inherits its convergence guarantees. However, its computational requirements are linear in time and space rather than exponential. The second variant, Fictitious Self-Play, is a machine learning framework that implements fictitious play in a sample-based fashion. Experiments in imperfect-information poker games compare our approaches and demonstrate their convergence to approximate Nash equilibria.
RIS
TY - CPAPER TI - Fictitious Self-Play in Extensive-Form Games AU - Johannes Heinrich AU - Marc Lanctot AU - David Silver BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-heinrich15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 805 EP - 813 L1 - http://proceedings.mlr.press/v37/heinrich15.pdf UR - https://proceedings.mlr.press/v37/heinrich15.html AB - Fictitious play is a popular game-theoretic model of learning in games. However, it has received little attention in practical applications to large problems. This paper introduces two variants of fictitious play that are implemented in behavioural strategies of an extensive-form game. The first variant is a full-width process that is realization equivalent to its normal-form counterpart and therefore inherits its convergence guarantees. However, its computational requirements are linear in time and space rather than exponential. The second variant, Fictitious Self-Play, is a machine learning framework that implements fictitious play in a sample-based fashion. Experiments in imperfect-information poker games compare our approaches and demonstrate their convergence to approximate Nash equilibria. ER -
APA
Heinrich, J., Lanctot, M. & Silver, D.. (2015). Fictitious Self-Play in Extensive-Form Games. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:805-813 Available from https://proceedings.mlr.press/v37/heinrich15.html.

Related Material