# Policy Regret in Repeated Games

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2018.

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

- [Rethinking the Foundations for Continual Reinforcement Learning](https://mlsanity.com/paper/2504.08161/) (2025)
- [Complete Policy Regret Bounds for Tallying Bandits](https://mlsanity.com/paper/2204.11174/) (2022)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality](https://mlsanity.com/paper/2305.02955/) (2023)
- [Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback](https://mlsanity.com/paper/2204.12764/) (2022)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [Minimax-Optimal Policy Regret in Partially Observable Markov Games](https://mlsanity.com/paper/2606.02363/) (2026)

## Abstract (arXiv)

The notion of policy regret in online learning is a well defined? performance measure for the common scenario of adaptive adversaries, which more traditional quantities such as external regret do not take into account. We revisit the notion of policy regret and first show that there are online learning settings in which policy regret and external regret are incompatible: any sequence of play that achieves a favorable regret with respect to one definition must do poorly with respect to the other. We then focus on the game-theoretic setting where the adversary is a self-interested agent. In that setting, we show that external regret and policy regret are not in conflict and, in fact, that a wide class of algorithms can ensure a favorable regret with respect to both definitions, so long as the adversary is also using such an algorithm. We also show that the sequence of play of no-policy regret algorithms converges to a policy equilibrium, a new notion of equilibrium that we introduce. Relating this back to external regret, we show that coarse correlated equilibria, which no-external regret players converge to, are a strict subset of policy equilibria. Thus, in game-theoretic settings, every sequence of play with no external regret also admits no policy regret, but the converse does not hold.