Identify the Nash Equilibrium in Static Games with Random Payoffs
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:41604169, 2017.
Abstract
We study the problem on how to learn the pure Nash Equilibrium of a twoplayer zerosum static game with random payoffs under unknown distributions via efficient payoff queries. We introduce a multiarmed 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—LUCBG 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.
Related Material


