Timezone: »

Identify the Nash Equilibrium in Static Games with Random Payoffs
Yichi Zhou · Jialian Li · Jun Zhu

Sun Aug 06 08:48 PM -- 09:06 PM (PDT) @ C4.1

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.

Author Information

Yichi Zhou (Tsinghua University)
Jialian Li (Tsinghua University)
Jun Zhu (Tsinghua University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors