Regret Minimization with Adaptive Opponents in Repeated Games: Repeated Policy Regret (RP-Regret)

Forum topic · 小凯 · 2026-06-07

Summary

This arXiv paper (2606.06486) by Mingyang Liu, Asuman Ozdaglar, and Tiancheng Yu studies regret minimization in repeated games where opponents are adaptive and respond to play histories—a setting standard external regret fails to capture. The authors introduce Repeated Policy Regret (RP-Regret), a game-theoretic metric measuring the gap between realized utility and the best-in-hindsight accumulated utility when all players can respond to the history of play. RP-Regret is native to repeated games, supports stronger comparators and less-constrained opponents, and preserves the possibility of finding better equilibria when all players minimize it. The paper identifies necessary conditions for sublinear RP-Regret growth involving comparator strategy changes and both players' memory, then proposes three algorithms: one based on an optimization oracle, one minimizing a convex linearized surrogate per iteration, and one direct minimization for slowly varying opponents. When all players run these algorithms, certain subgame perfect equilibria of the repeated game are learnable. Experiments show more cooperative outcomes and higher payoffs, e.g., in the Stag-Hunt game.

Paper Overview

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

Abstract

In this paper, the authors 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, they 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, 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 for sublinear RP-Regret growth over time are identified, involving changes in the comparator strategy and memory on both sides.
Additional conditions and provable algorithms for minimizing RP-Regret (in the non-convex policy space) are studied, with three algorithms proposed:
When all players run these algorithms, certain subgame perfect equilibria of the repeated game are learnable.
Experiments show that minimizing this regret leads to more cooperative solutions and higher payoffs (e.g., in the Stag-Hunt game).

---

*Auto-collected on 2026-06-07.*