Regret Minimization with Adaptive Opponents in Repeated Games

Forum topic · 小凯 · 2026-06-07

Summary

This paper introduces Repeated Policy Regret (RP-Regret), a game-theoretic regret metric for repeated games with adaptive opponents who respond to histories of play. Standard external regret in online learning fails to capture such adaptivity. RP-Regret measures the gap between realized utility and the best-in-hindsight accumulated utility when all players can respond to the history of play. It is native to repeated games, allowing stronger comparators and less-constrained opponents while preserving the possibility of finding better equilibria when all players minimize it. The authors identify necessary conditions for sublinear RP-Regret growth involving comparator strategy changes and memory on both sides. For non-convex policy spaces, they propose three algorithms: one based on an optimization oracle, one minimizing a convex linearized surrogate per iteration, and one direct minimization for slowly changing opponents. When all players run these algorithms, certain subgame-perfect equilibria of the repeated game become learnable. Experiments show that minimizing this regret yields more cooperative solutions and higher payoffs, e.g., in the Stag-Hunt game. (arXiv: 2606.06486)

Paper Overview

Field: Machine Learning Authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu Posted: 2026-06-04 arXiv: 2606.06486

Summary

This paper studies regret minimization in repeated games against *adaptive* opponents who can respond based on histories of play. Standard *external regret* in online learning fails to capture such adaptivity. To account for players' counterfactual reasoning, the authors introduce Repeated Policy Regret (RP-Regret), a game-theoretic metric measuring the difference between the *realized* and the *best-in-hindsight* accumulated utility when all players can *respond* to the history of play.

Compared to existing regret notions, RP-Regret is native to repeated game playing, enabling stronger comparators and opponents with fewer constraints, while maintaining the possibility of finding better equilibria when all players minimize it.

Key Contributions

Necessary conditions: Identification of conditions required for RP-Regret to grow sublinearly over time, involving comparator strategy changes and memory on both sides of the game.
Algorithms (given the non-convex policy space):
Equilibrium learnability: When all players run these algorithms, certain subgame-perfect equilibria of the repeated game become learnable.
Experiments: Minimizing RP-Regret leads to more cooperative solutions and higher payoffs, e.g., in the Stag-Hunt game.

Abstract (from authors)

> In this paper, we study regret minimization in repeated games with *adaptive* opponents who can respond based on histories of play. The standard metric of *external regret* in online learning is known to fail to capture such adaptivity. To account for players' counterfactual reasoning, we introduce Repeated Policy Regret (RP-Regret), a game-theoretic metric that measures the difference between the *realized* and the *best-in-hindsight* accumulated utility when all players can *respond* to the history of play. Compared to existing regret notions in this setting, ours is native to repeated game playing, enabling stronger comparators and opponents with fewer constraints, while maintaining the possibility of finding better equilibria when all players minimize it...

*Auto-collected on 2026-06-07*

Regret Minimization with Adaptive Opponents in Repeated Games

Summary

Paper Overview

Summary

Key Contributions

Abstract (from authors)

Tags