Actor-Critic Fictitious Play in Simultaneous Move Multistage Games

Julien Perolat, Bilal Piot, Olivier Pietquin
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:919-928, 2018.

Abstract

Fictitious play is a game theoretic iterative procedure meant to learn an equilibrium in normal form games. However, this algorithm requires that each player has full knowledge of other players’ strategies. Using an architecture inspired by actor-critic algorithms, we build a stochastic approximation of the fictitious play process. This procedure is on-line, decentralized (an agent has no information of others’ strategies and rewards) and applies to multistage games (a generalization of normal form games). In addition, we prove convergence of our method towards a Nash equilibrium in both the cases of zero-sum two-player multistage games and cooperative multistage games. We also provide empirical evidence of the soundness of our approach on the game of Alesia with and without function approximation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-perolat18a, title = {Actor-Critic Fictitious Play in Simultaneous Move Multistage Games}, author = {Perolat, Julien and Piot, Bilal and Pietquin, Olivier}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {919--928}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/perolat18a/perolat18a.pdf}, url = {https://proceedings.mlr.press/v84/perolat18a.html}, abstract = {Fictitious play is a game theoretic iterative procedure meant to learn an equilibrium in normal form games. However, this algorithm requires that each player has full knowledge of other players’ strategies. Using an architecture inspired by actor-critic algorithms, we build a stochastic approximation of the fictitious play process. This procedure is on-line, decentralized (an agent has no information of others’ strategies and rewards) and applies to multistage games (a generalization of normal form games). In addition, we prove convergence of our method towards a Nash equilibrium in both the cases of zero-sum two-player multistage games and cooperative multistage games. We also provide empirical evidence of the soundness of our approach on the game of Alesia with and without function approximation.} }
Endnote
%0 Conference Paper %T Actor-Critic Fictitious Play in Simultaneous Move Multistage Games %A Julien Perolat %A Bilal Piot %A Olivier Pietquin %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-perolat18a %I PMLR %P 919--928 %U https://proceedings.mlr.press/v84/perolat18a.html %V 84 %X Fictitious play is a game theoretic iterative procedure meant to learn an equilibrium in normal form games. However, this algorithm requires that each player has full knowledge of other players’ strategies. Using an architecture inspired by actor-critic algorithms, we build a stochastic approximation of the fictitious play process. This procedure is on-line, decentralized (an agent has no information of others’ strategies and rewards) and applies to multistage games (a generalization of normal form games). In addition, we prove convergence of our method towards a Nash equilibrium in both the cases of zero-sum two-player multistage games and cooperative multistage games. We also provide empirical evidence of the soundness of our approach on the game of Alesia with and without function approximation.
APA
Perolat, J., Piot, B. & Pietquin, O.. (2018). Actor-Critic Fictitious Play in Simultaneous Move Multistage Games. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:919-928 Available from https://proceedings.mlr.press/v84/perolat18a.html.

Related Material