Computing Equilibria with Two-Player Zero-Sum Continuous Stochastic Games with Switching Controller
Abstract
Equilibrium computation with continuous games is currently a challenging open task in artificial intelligence. In this paper, we design an iterative algorithm that finds an ε-approximate Markov perfect equilibrium with two-player zero-sum continuous stochastic games with switching controller. When the game is polynomial (i.e., utility and state transitions are polynomial functions), our algorithm converges to ε = 0 by exploiting semidefinite programming. When the game is not polynomial, the algorithm exploits polynomial approximations and converges to an ε value whose upper bound is a function of the maximum approximation error with infinity norm. To our knowledge, this is the first algorithm for equilibrium approximation with arbitrary utility and transition functions providing theoretical guarantees. The algorithm is also empirically evaluated.
Cite
Text
Bonomi et al. "Computing Equilibria with Two-Player Zero-Sum Continuous Stochastic Games with Switching Controller." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8238Markdown
[Bonomi et al. "Computing Equilibria with Two-Player Zero-Sum Continuous Stochastic Games with Switching Controller." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/bonomi2012aaai-computing/) doi:10.1609/AAAI.V26I1.8238BibTeX
@inproceedings{bonomi2012aaai-computing,
title = {{Computing Equilibria with Two-Player Zero-Sum Continuous Stochastic Games with Switching Controller}},
author = {Bonomi, Guido and Gatti, Nicola and Panozzo, Fabio and Restelli, Marcello},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {1270-1277},
doi = {10.1609/AAAI.V26I1.8238},
url = {https://mlanthology.org/aaai/2012/bonomi2012aaai-computing/}
}