Skip to yearly menu bar Skip to main content


Poster

Identify the Nash Equilibrium in Static Games with Random Payoffs

Yichi Zhou · Jialian Li · Jun Zhu

Gallery #54

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.

Live content is unavailable. Log in and register to view live content