2022/06/18 by Kenshi Abe, Mitsuki Sakamoto, Abe, Kenshi +3 · 4 citations
Computer Science · Decision Sciences · Social Sciences · #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2206.09254
openalex publication_date 2022/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this study, we consider a variant of the Follow the Regularized Leader (FTRL) dynamics in two-player zero-sum games. FTRL is guaranteed to converge to a Nash equilibrium when time-averaging the strategies, while a lot of variants suffer from the issue of limit cycling behavior, i.e., lack the last-iterate convergence guarantee. To this end, we propose mutant FTRL (M-FTRL), an algorithm that introduces mutation for the perturbation of action probabilities. We then investigate the continuous-time dynamics of M-FTRL and provide the strong convergence guarantees toward stationary points that approximate Nash equilibria under full-information feedback. Furthermore, our simulation demonstrates that M-FTRL can enjoy faster convergence rates than FTRL and optimistic FTRL under full-information feedback and surprisingly exhibits clear convergence under bandit feedback.