Identify the Nash Equilibrium in Static Games with Random Payoffs

Yichi Zhou, Jialian Li, Jun Zhu
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:4160-4169, 2017.

Abstract

We study the problem on how to learn the pure Nash Equilibrium of a two-player zero-sum static game with random payoffs under unknown distributions via efficient payoff queries. We introduce a multi-armed bandit model to this problem due to its ability to find the best arm efficiently among random arms and propose two algorithms for this problem—LUCB-G based on the confidence bounds and a racing algorithm based on successive action elimination. We provide an analysis on the sample complexity lower bound when the Nash Equilibrium exists.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-zhou17b, title = {Identify the {N}ash Equilibrium in Static Games with Random Payoffs}, author = {Yichi Zhou and Jialian Li and Jun Zhu}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {4160--4169}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/zhou17b/zhou17b.pdf}, url = {https://proceedings.mlr.press/v70/zhou17b.html}, abstract = {We study the problem on how to learn the pure Nash Equilibrium of a two-player zero-sum static game with random payoffs under unknown distributions via efficient payoff queries. We introduce a multi-armed bandit model to this problem due to its ability to find the best arm efficiently among random arms and propose two algorithms for this problem—LUCB-G based on the confidence bounds and a racing algorithm based on successive action elimination. We provide an analysis on the sample complexity lower bound when the Nash Equilibrium exists.} }
Endnote
%0 Conference Paper %T Identify the Nash Equilibrium in Static Games with Random Payoffs %A Yichi Zhou %A Jialian Li %A Jun Zhu %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-zhou17b %I PMLR %P 4160--4169 %U https://proceedings.mlr.press/v70/zhou17b.html %V 70 %X We study the problem on how to learn the pure Nash Equilibrium of a two-player zero-sum static game with random payoffs under unknown distributions via efficient payoff queries. We introduce a multi-armed bandit model to this problem due to its ability to find the best arm efficiently among random arms and propose two algorithms for this problem—LUCB-G based on the confidence bounds and a racing algorithm based on successive action elimination. We provide an analysis on the sample complexity lower bound when the Nash Equilibrium exists.
APA
Zhou, Y., Li, J. & Zhu, J.. (2017). Identify the Nash Equilibrium in Static Games with Random Payoffs. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:4160-4169 Available from https://proceedings.mlr.press/v70/zhou17b.html.

Related Material