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

We examine the problem of regret minimization when the learner is involved in\na continuous game with other optimizing agents: in this case, if all players\nfollow a no-regret algorithm, it is possible to achieve significantly lower\nregret relative to fully adversarial environments. We study this problem in the\ncontext of variationally stable games (a class of continuous games which\nincludes all convex-concave and monotone games), and when the players only have\naccess to noisy estimates of their individual payoff gradients. If the noise is\nadditive, the game-theoretic and purely adversarial settings enjoy similar\nregret guarantees; however, if the noise is multiplicative, we show that the\nlearners can, in fact, achieve constant regret. We achieve this faster rate via\nan optimistic gradient scheme with learning rate separation -- that is, the\nmethod's extrapolation and update steps are tuned to different schedules,\ndepending on the noise profile. Subsequently, to eliminate the need for\ndelicate hyperparameter tuning, we propose a fully adaptive method that attains\nnearly the same guarantees as its non-adapted counterpart, while operating\nwithout knowledge of either the game or of the noise profile.\n