2023/05/26 by Kenshi Abe, Kaito Ariu, Abe, Kenshi +5 · 4 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2305.16610
openalex publication_date 2023/05/26 · openalex created_date 2023/05/30 · openalex updated_date 2026/07/28
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.