# Pareto-Optimal Algorithms for Learning in Games

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2024.

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

- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Generalized Principal-Agent Problem with a Learning Agent](https://mlsanity.com/paper/2402.09721/) (2024)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (2024)
- [Learning to Play Against Unknown Opponents](https://mlsanity.com/paper/2412.18297/) (2024)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)
- [Computational Intractability of Strategizing against Online Learners](https://mlsanity.com/paper/2503.04202/) (2025)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Swap Regret Minimization Through Response-Based Approachability](https://mlsanity.com/paper/2602.06264/) (2026)
- [Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners](https://mlsanity.com/paper/2502.08597/) (2025)
- [Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent](https://mlsanity.com/paper/2510.22471/) (2025)
- [mathsfVISTA: Decentralized Machine Learning in Adversary Dominated Environments](https://mlsanity.com/paper/2605.07841/) (2026)
- [Is Online Linear Optimization Sufficient for Strategic Robustness?](https://mlsanity.com/paper/2602.12253/) (2026)

## Abstract (arXiv)

We study the problem of characterizing optimal learning algorithms for playing repeated games against an adversary with unknown payoffs. In this problem, the first player (called the learner) commits to a learning algorithm against a second player (called the optimizer), and the optimizer best-responds by choosing the optimal dynamic strategy for their (unknown but well-defined) payoff. Classic learning algorithms (such as no-regret algorithms) provide some counterfactual guarantees for the learner, but might perform much more poorly than other learning algorithms against particular optimizer payoffs. In this paper, we introduce the notion of asymptotically Pareto-optimal learning algorithms. Intuitively, if a learning algorithm is Pareto-optimal, then there is no other algorithm which performs asymptotically at least as well against all optimizers and performs strictly better (by at least Omega(T)) against some optimizer. We show that well-known no-regret algorithms such as Multiplicative Weights and Follow The Regularized Leader are Pareto-dominated. However, while no-regret is not enough to ensure Pareto-optimality, we show that a strictly stronger property, no-swap-regret, is a sufficient condition for Pareto-optimality. Proving these results requires us to address various technical challenges specific to repeated play, including the fact that there is no simple characterization of how optimizers who are rational in the long-term best-respond against a learning algorithm over multiple rounds of play. To address this, we introduce the idea of the asymptotic menu of a learning algorithm: the convex closure of all correlated distributions over strategy profiles that are asymptotically implementable by an adversary. We show that all no-swap-regret algorithms share the same asymptotic menu, implying that all no-swap-regret algorithms are ``strategically equivalent''.