# Evolutionary Dynamics and Phi-Regret Minimization in Games

arXiv: https://arxiv.org/abs/2106.14668 · HTML: https://mlsanity.com/paper/2106.14668/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 89 references that are in the map.
- First posted on arXiv 28 Jun 2021.

## Builds on (most cited first, 21 of 21)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Actor-Critic Policy Optimization in Partially Observable Multiagent Environments](https://mlsanity.com/paper/1810.09026/) (2018)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Hindsight and Sequential Rationality of Correlated Play](https://mlsanity.com/paper/2012.05874/) (2020)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2004.00603/) (2020)
- [Chaos, Extremism and Optimism: Volume Analysis of Learning in Games](https://mlsanity.com/paper/2005.13996/) (2020)
- [The route to chaos in routing games: When is Price of Anarchy too optimistic?](https://mlsanity.com/paper/1906.02486/) (2019)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021)
- [Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes](https://mlsanity.com/paper/1905.04532/) (2019)
- [A continuous-time approach to online optimization](https://mlsanity.com/paper/1401.6956/) (2014)
- [From Darwin to Poincar'e and von Neumann: Recurrence and Cycles in Evolutionary and Algorithmic Game Theory](https://mlsanity.com/paper/1910.01334/) (2019)
- [Evolutionary Game Theory Squared: Evolving Agents in Endogenously Evolving Zero-Sum Games](https://mlsanity.com/paper/2012.08382/) (2020)
- [Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincar'e Recurrence](https://mlsanity.com/paper/2106.04748/) (2021)

## Built on by (most cited first, 2 of 2)

- [Generalization in Cooperative Multi-Agent Systems](https://mlsanity.com/paper/2202.00104/) (2022)
- [Learning Correlated Equilibria in Mean-Field Games](https://mlsanity.com/paper/2208.10138/) (2022)

## Abstract (arXiv)

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 external, internal, and swap regret, and thus broadening the insights gained from regret-based analysis of learning algorithms. We prove here that the well-studied evolutionary learning algorithm of replicator dynamics (RD) seamlessly minimizes the strongest possible form of Phi-regret in generic 2 × 2 games, without any modification of the underlying algorithm itself. We subsequently conduct experiments validating our theoretical results in a suite of 144 2 × 2 games wherein RD exhibits a diverse set of behaviors. We conclude by providing empirical evidence of Phi-regret minimization by RD in some larger games, hinting at further opportunity for Phi-regret based study of such algorithms from both a theoretical and empirical perspective.