Adaptively Perturbed Mirror Descent for Learning in Games
This addresses convergence challenges in game theory for noisy environments, representing an incremental improvement over existing perturbation methods.
The paper tackles the problem of learning in games with monotone payoff functions and potential noise by proposing Adaptively Perturbed Mirror Descent (APMD), which adjusts perturbation magnitude by updating a slingshot strategy at intervals, achieving guaranteed convergence rates to Nash equilibrium with significantly accelerated empirical convergence.
This paper proposes a payoff perturbation technique for the Mirror Descent (MD) algorithm in games where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. The optimistic family of learning algorithms, exemplified by optimistic MD, successfully achieves {\it last-iterate} convergence in scenarios devoid of noise, leading the dynamics to a Nash equilibrium. A recent re-emerging trend underscores the promise of the perturbation approach, where payoff functions are perturbed based on the distance from an anchoring, or {\it slingshot}, strategy. In response, we propose {\it Adaptively Perturbed MD} (APMD), which adjusts the magnitude of the perturbation by repeatedly updating the slingshot strategy at a predefined interval. This innovation empowers us to find a Nash equilibrium of the underlying game with guaranteed rates. Empirical demonstrations affirm that our algorithm exhibits significantly accelerated convergence.