Poster
Mon Aug 07 01:30 AM -- 05:00 AM (PDT) @ Gallery #54
Identify the Nash Equilibrium in Static Games with Random Payoffs
In
Posters Mon
[
PDF]
[
Summary/Notes]
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.