Pareto-Optimal Algorithms for Learning in Games
Open Access
- 8 July 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 490-510
Abstract
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 Ω(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. Interestingly, we show that all no-swap-regret algorithms share the same asymptotic menu, implying that all no-swap-regret algorithms are "strategically equivalent".Keywords
All Related Versions
Funding Information
- NSF (National Science Foundation) (CCF-2045128)
- Amazon Web Services (ASSET Grant)
This publication has 15 references indexed in Scilit:
- Learning in Stackelberg Games with Non-myopic Agents2022
- Auctions between Regret-Minimizing Agents2022
- Learning Optimal Strategies to Commit ToProceedings of the AAAI Conference on Artificial Intelligence, 2019
- Selling to a No-Regret Buyer2018
- Commitment Without Regrets2015
- Computing the optimal strategy to commit to2006
- Strategic Learning and its Limits2004
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000
- Calibrated Learning and Correlated EquilibriumGames and Economic Behavior, 1997
- An analog of the minimax theorem for vector payoffsPacific Journal of Mathematics, 1956