Identify the Nash Equilibrium in Static Games with Random Payoffs

@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.}
}