Identify the Nash Equilibrium in Static Games with Random Payoffs
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
Text
Zhou et al. "Identify the Nash Equilibrium in Static Games with Random Payoffs." International Conference on Machine Learning, 2017.Markdown
[Zhou et al. "Identify the Nash Equilibrium in Static Games with Random Payoffs." International Conference on Machine Learning, 2017.](https://mlanthology.org/icml/2017/zhou2017icml-identify/)BibTeX
@inproceedings{zhou2017icml-identify,
title = {{Identify the Nash Equilibrium in Static Games with Random Payoffs}},
author = {Zhou, Yichi and Li, Jialian and Zhu, Jun},
booktitle = {International Conference on Machine Learning},
year = {2017},
pages = {4160-4169},
volume = {70},
url = {https://mlanthology.org/icml/2017/zhou2017icml-identify/}
}