Timezone: »

 
Poster
Learning with Bandit Feedback in Potential Games
Amélie Héliou · Johanne Cohen · Panayotis Mertikopoulos

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #221
in Posters Wed »

This paper examines the equilibrium convergence properties of no-regret learning with exponential weights in potential games. To establish convergence with minimal information requirements on the players' side, we focus on two frameworks: the semi-bandit case (where players have access to a noisy estimate of their payoff vectors, including strategies they did not play), and the bandit case (where players are only able to observe their in-game, realized payoffs). In the semi-bandit case, we show that the induced sequence of play converges almost surely to a Nash equilibrium at a quasi-exponential rate. In the bandit case, the same result holds for approximate Nash equilibria if we introduce a constant exploration factor that guarantees that action choice probabilities never become arbitrarily small. In particular, if the algorithm is run with a suitably decreasing exploration factor, the sequence of play converges to a bona fide Nash equilibrium with probability 1.

Keywords: Learning Theory · Online Learning · Theory · Multi-Agent RL · Game Theory and Computational Economics
[ Paper]  [ Poster] 

Author Information

Amélie Héliou (Criteo)
Johanne Cohen (LRI-CNRS)
Panayotis Mertikopoulos (CNRS (French National Center for Scientific Research))

More from the Same Authors