Evolutionary Dynamics And \(\phi\)-regret Minimization In Games

Abstract

Regret has been established as a foundational concept in online learning, and likewise has important applications in the analysis of learning dynamics in games. Regret quantifies the difference between a learner's performance against a baseline in hindsight. It is well-known that regret-minimizing algorithms converge to certain classes of equilibria in games; however, traditional forms of regret used in game theory predominantly consider baselines that permit deviations to deterministic actions or strategies. In this paper, we revisit our understanding of regret from the perspective of deviations over partitions of the full *mixed* strategy space (i.e., probability distributions over pure strategies), under the lens of the previously-established \(\Phi\)-regret framework, which provides a continuum of stronger regret measures. Importantly, \(\Phi\)-regret enables learning agents to consider deviations from and to mixed strategies, generalizing several existing notions of regret such as

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keypiliouras2021evolutionary

Related papers

• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• Model-free Online Learning In Unknown Sequential Decision Making Problems And Games (2021)5.24
• Regret Minimization In Population Network Games: Vanishing Heterogeneity And Convergence To Equilibria (2025)3.58
• Online Learning In Unknown Markov Games (2020)0.00
• On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games (2023)0.00
• Implications Of Regret On Stability Of Linear Dynamical Systems (2022)6.34
• Generalized Bandit Regret Minimizer Framework In Imperfect Information Extensive-form Game (2022)0.00
• Learning In Markov Games With Adaptive Adversaries: Policy Regret, Fundamental Barriers, And Efficient Algorithms (2024)0.00