Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation

Abstract : We examine the problem of regret minimization when the learner is involved in a continuous game with other optimizing agents: in this case, if all players follow a no-regret algorithm, it is possible to achieve significantly lower regret relative to fully adversarial environments. We study this problem in the context of variationally stable games (a class of continuous games which includes all convex-concave and monotone games), and when the players only have access to noisy estimates of their individual payoff gradients. If the noise is additive, the game-theoretic and purely adversarial settings enjoy similar regret guarantees; however, if the noise is multiplicative, we show that the learners can, in fact, achieve constant regret. We achieve this faster rate via an optimistic gradient scheme with learning rate separation that is, the method's extrapolation and update steps are tuned to different schedules, depending on the noise profile. Subsequently, to eliminate the need for delicate hyperparameter tuning, we propose a fully adaptive method that smoothly interpolates between worst-and best-case regret guarantees.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03694134
Contributor : Yu-Guan HSIEH Connect in order to contact the contributor
Submitted on : Monday, June 13, 2022 - 1:57:26 PM
Last modification on : Friday, July 22, 2022 - 10:45:52 AM

File

Learning_in_games_with_noisy_f...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03694134, version 1

Citation

Yu-Guan Hsieh, Kimon Antonakopoulos, Volkan Cevher, Panayotis Mertikopoulos. No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation. 2022. ⟨hal-03694134⟩

Share

Metrics

Record views

23

Files downloads

2