Timezone: »

 
Poster
Gradient-free Online Learning in Continuous Games with Delayed Rewards
Amélie Héliou · Panayotis Mertikopoulos · Zhengyuan Zhou

Thu Jul 16 12:00 PM -- 12:45 PM & Fri Jul 17 12:00 AM -- 12:45 AM (PDT) @
in Poster Session 45 »

Motivated by applications to online advertising and recommender systems, we consider a game-theoretic model with delayed rewards and asynchronous, payoff-based feedback. In contrast to previous work on delayed multi-armed bandits, we focus on games with continuous action spaces, and we examine the long-run behavior of strategic agents that follow a no-regret learning policy (but are otherwise oblivious to the game being played, the objectives of their opponents, etc.). To account for the lack of a consistent stream of information (for instance, rewards can arrive out of order and with an a priori unbounded delay), we introduce a gradient-free learning policy where payoff information is placed in a priority queue as it arrives. Somewhat surprisingly, we find that under a standard diagonal concavity assumption, the induced sequence of play converges to Nash Equilibrium (NE) with probability 1, even if the delay between choosing an action and receiving the corresponding reward is unbounded.

Keywords: Game Theory and Mechanism Design · Learning Theory · Online Learning / Bandits

Author Information

Amélie Héliou (Criteo)
Panayotis Mertikopoulos (CNRS and Criteo AI Lab)
Zhengyuan Zhou (Stanford University)

More from the Same Authors