🤖 AI

Regret Minimization with Adaptive Opponents in Repeated Games

This paper introduces Repeated Policy Regret (RP-Regret), a novel game-theoretic metric designed to handle adaptive opponents in repeated games, and proposes algorithms to minimize this non-convex regret measure, thereby enabling the learning of subgame perfect equilibria and more cooperative outcomes.

Original authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

Published 2026-06-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a long game of chess, poker, or even a simple game of "Rock, Paper, Scissors" with a friend. In a standard game, you make a move, they make a move, and the score is tallied. But in the real world (and in the "repeated games" studied in this paper), your friend isn't a robot. They are watching you. If you play aggressively, they might get defensive. If you play nicely, they might cooperate. They are adaptive: they change their strategy based on your history.

The problem is that the standard way computer scientists measure "how well you played" (called External Regret) assumes your opponent is a static wall that doesn't care what you do. It asks: "If I had just picked the single best move for every turn, regardless of what you did, would I have won more?"

This paper argues that this standard measurement is broken for games with smart, adaptive opponents. It often forces players to play poorly (like always "defecting" in a Prisoner's Dilemma) because it fails to account for the fact that your actions change your opponent's future behavior.

Here is a breakdown of the paper's solution, using simple analogies.

1. The New Metric: "Repeated Policy Regret" (RP-Regret)

The authors introduce a new way to measure success called RP-Regret.

The Old Way (External Regret): Imagine you are driving a car. The old metric asks: "If you had just driven the exact same route every single day, ignoring traffic lights and other cars, how much time would you have saved?" This is useless if the traffic lights change based on your driving.
The New Way (RP-Regret): This metric asks: "If you had chosen a different entire plan (a policy) for the whole trip, knowing that the traffic lights and other drivers would react to that specific plan, how much better off would you be?"

The Key Difference: In the new metric, you aren't just comparing your current moves to a single "best move." You are comparing your entire strategy to a hypothetical "better strategy" that you could have used, assuming your opponent would have adapted to that better strategy too.

2. The "Memory" Problem

The paper discovers a major hurdle: if players have perfect, infinite memories and can react to every tiny detail of the past, it becomes mathematically impossible to minimize this new regret. It's like trying to solve a puzzle where every piece you move changes the shape of every other piece instantly.

To fix this, the authors propose two "rules of the road" (conditions) that make the problem solvable:

Slow Changes: Your opponent (and your own "what-if" strategy) shouldn't change their mind too wildly from one second to the next.
Forgetting: Players shouldn't remember everything perfectly. They should have a "fading memory." If something happened 100 turns ago, it should barely matter now. The paper calls this Exponential Decay Memory. It's like how you remember a conversation better if it happened recently, but the details of a conversation from a year ago fade away.

3. Three Ways to Play Better (The Algorithms)

Since calculating the perfect "RP-Regret" strategy is hard (like trying to solve a maze that keeps changing shape), the authors propose three different tools to get close to the best result:

Tool 1: The Magic Oracle. Imagine you have a super-computer that can instantly solve any complex, non-linear puzzle. If you have this "oracle," you can find the perfect strategy. The paper proves this works, but admits that in real life, we don't have such a magic computer.
Tool 2: The "Local" Shortcut. Instead of trying to change your entire plan for the whole game, this tool asks: "What if I only changed one move right now, and kept everything else the same?" It simplifies the problem by looking at small, local changes. This makes the math much easier (turning a jagged, bumpy hill into a smooth slope) and allows for a fast, practical algorithm.
Tool 3: The Slow-Motion Game. If your opponent changes their strategy very slowly, the authors show you can treat the game like a "Markov Game" (a game where the future only depends on the current state, not the whole history). They convert the game into a format where standard optimization tools work well, effectively "lifting" the problem into a higher dimension to make it solvable.

4. The Result: Cooperation Wins

The most exciting part of the paper is what happens when everyone uses these new tools.

In the famous Prisoner's Dilemma (a game where two people often end up betraying each other because they are afraid), the old methods usually lead to a "Defect-Defect" outcome where both lose. However, the paper shows that if players minimize RP-Regret, they naturally learn to cooperate.

The Analogy: Think of two neighbors. If they only look at today's interaction, they might steal each other's mail. But if they realize that "If I steal today, my neighbor will steal tomorrow, and we'll both lose," they learn to be nice. The new metric captures this long-term thinking.
The Experiment: The authors tested this on a game called Stag-Hunt (where you can either hunt a hare alone for a small reward or hunt a stag together for a big reward). When players used the new "Local RP-Regret" algorithm, they successfully learned to cooperate and hunt the stag, achieving much higher scores than before.

Summary

This paper says: "Stop measuring players by how they would do against a robot. Start measuring them by how they would do against a smart, reacting human." By introducing a new metric that accounts for adaptation and memory limits, and by providing algorithms to calculate it, the authors show that players can learn to cooperate and achieve better outcomes in repeated games than ever before.

Technical Summary: Regret Minimization with Adaptive Opponents in Repeated Games

Problem Statement

The paper addresses the challenge of regret minimization in repeated games where opponents are adaptive, meaning they can adjust their strategies based on the history of play. The authors argue that the standard metric of external regret in online learning is insufficient for this setting. External regret assumes that loss sequences are functions of time steps only, implicitly treating opponents as non-adaptive. In game-theoretic settings, however, an opponent's response to a player's action can alter future losses. Consequently, minimizing external regret in repeated games often leads to sub-optimal equilibria (e.g., the "defect-defect" outcome in Iterated Prisoner's Dilemma) and fails to capture effective cooperative strategies like "tit-for-tat," which may suffer linear external regret despite yielding higher utilities.

Existing alternatives, such as Policy Regret (which accounts for memory in loss functions) or Response Regret (which considers history-dependent mixed strategies), face significant limitations. Policy Regret often relies on restrictive $m$ -bounded memory assumptions that do not hold in repeated games where early deviations can have long-term effects. Response Regret, while theoretically sound, requires an exponentially large strategy space, rendering it computationally intractable.

Methodology

1. Repeated Policy Regret (RP-Regret)

The authors introduce Repeated Policy Regret (RP-Regret), a new performance metric native to repeated games.

Definition: RP-Regret measures the difference between the realized accumulated utility and the best-in-hindsight accumulated utility, assuming all players (including the opponent) respond adaptively to the history of play.
Key Distinction: Unlike external regret, a deviation to a comparator strategy at time $t$ affects not only the loss at $t$ but also all subsequent losses, as the adaptive opponents change their strategies in response to the new history.
Necessary Conditions: The paper establishes that achieving sublinear RP-Regret is impossible without specific constraints. Two necessary conditions are identified:
1. Sublinear Variation: The comparator strategy must not change too rapidly over time.
2. Imperfect Recall: Players (and the comparator) cannot have perfect recall of the entire history. Specifically, the paper proposes Exponential Decay Memory (EDM), where the influence of past history on current strategy decays exponentially. This prevents "state passing" via actions and ensures the effective memory length grows only logarithmically with accuracy requirements.

2. Minimization Algorithms

Since the objective function for RP-Regret is non-convex due to the product of strategies over time, the paper proposes three approaches to minimize it:

Oracle-Based Approach: Assuming access to a non-convex optimization oracle (as in prior online non-convex learning work), the authors show that sublinear RP-Regret is achievable under the necessary conditions (Sublinear Variation and EDM). This serves as a theoretical baseline.
Local Repeated Policy Regret (LRP-Regret): To ensure computational tractability, the authors propose a surrogate metric, LRP-Regret. This metric restricts deviations to a single timestep (local deviation) rather than a global strategy change.
- Convexification: The expected loss at a specific timestep, when viewed as a function of a single-step deviation, becomes linear (and thus convex) with respect to the strategy at that step.
- Algorithm: The authors propose a Projected Gradient Descent (PGD) algorithm to minimize LRP-Regret. Theoretical guarantees show that if opponents satisfy the EDM condition, the algorithm achieves sublinear LRP-Regret.
Markov Game Reformulation: For the case where opponents also change strategies slowly (satisfying Sublinear Variation), the authors reformulate the repeated game with bounded memory as an infinite-horizon Markov Game.
- Occupancy Measures: Instead of optimizing the strategy directly, the algorithm optimizes the occupancy measure (state-action visitation frequencies). This transforms the non-convex problem into a convex one in the occupancy measure space.
- Constraints: The algorithm handles time-varying constraints to ensure the occupancy measure corresponds to a valid product strategy profile against the adaptive opponents.
- Result: This approach directly minimizes the original RP-Regret (not just the surrogate) and achieves sublinear regret.

Key Results

Hardness Results: The paper proves that without the conditions of sublinear variation and imperfect recall (specifically EDM), minimizing RP-Regret is impossible (resulting in linear regret).
Algorithmic Guarantees:
- The LRP-Regret minimization algorithm achieves a regret bound of $\tilde{O}(|A|^{m+1}\sqrt{P_T/T})$ , where $P_T$ is the variation of the comparator and $m$ is the memory length.
- The Markov Game-based algorithm achieves sublinear RP-Regret when opponents change strategies slowly.
Equilibrium Computation: The authors establish a theoretical link between minimizing these regret notions and computing equilibria.
- If all players minimize RP-Regret (or LRP-Regret), the time-average strategies converge to an Approximate Subgame Perfect Nash Equilibrium (SPNE) or Subgame Perfect Coarse Correlated Equilibrium (SPCCE) with bounded deviation.
- Specifically, for infinitely repeated games, the trajectory converges to an equilibrium that is robust to deviations within a certain variation budget.
Experimental Validation: Experiments on the Stag-Hunt game demonstrate that minimizing LRP-Regret allows players to converge to the cooperative equilibrium (Stag-Stag) with higher utility more frequently than methods minimizing external regret, which often get stuck in the risk-dominant but lower-utility equilibrium (Hare-Hare).

Significance and Claims

The paper claims to provide a native and natural regret metric for repeated games that accounts for opponent adaptivity without imposing the restrictive bounded-memory assumptions of prior Policy Regret work or the computational intractability of Response Regret.

Theoretical Contribution: It identifies the fundamental limits (necessary conditions) for learning in adaptive environments and provides the first provable algorithms for minimizing a game-theoretic regret metric that allows for dynamic comparators and adaptive opponents.
Practical Implication: By minimizing RP-Regret (or its convex surrogate LRP-Regret), players can learn to cooperate in games like the Iterated Prisoner's Dilemma and Stag-Hunt, achieving higher utilities than those dictated by standard Nash Equilibria in one-shot games.
Equilibrium Selection: The work suggests that regret minimization in repeated games can serve as a mechanism for selecting better equilibria (e.g., cooperative ones) that are not necessarily the unique Nash Equilibrium of the underlying one-shot game.

The authors remain modest regarding the computational complexity, acknowledging that the non-convex nature of the problem generally requires oracles or specific structural assumptions (like slow-changing opponents) to be tractable. They frame their work as opening new directions for research into weaker equilibrium notions and equilibrium selection via regret minimization.