Regret Minimization with Adaptive Opponents in Repeated Games

Accounting for the Counterfactual in Strategic Play

In multi-agent learning, a central goal is to design algorithms for improving performance through repeated interaction. Standard approaches rely on "regret minimization." This is a process where a player minimizes the difference between their actual loss and the loss they would have incurred using the best fixed strategy in hindsight. While this works in static environments, it fails in repeated games where opponents are adaptive (capable of responding to your history of play). If an opponent changes behavior based on your past moves, your "best" strategy is no longer a fixed sequence. It becomes a reactive one.

Current mathematical frameworks struggle to bridge this gap. Existing metrics assume the environment is indifferent to the player's actions. Alternatively, they impose heavy restrictions on opponent memory. This leaves a critical question: how can we define regret to account for the fact that every move we make reshapes the game?

The Failure of External Regret in Responsive Environments

The status quo in online learning is dominated by "external regret." This metric compares a player's performance against a stationary comparator (a fixed reference strategy). It asks, "Would I have been better off if I had just picked one single action and stuck to it?" This makes sense when playing against a fixed distribution. However, it fails in repeated games like the Iterated Prisoner's Dilemma.

The authors demonstrate that if players minimize external regret, they converge toward a "defect-defect" outcome. This is the Nash equilibrium of a one-shot game, but it yields low utility for both. Even effective cooperative strategies, such as "tit-for-tat," suffer from linear external regret. Tit-for-tat involves starting with cooperation and then mimicking the opponent's previous move. A single deviation triggers retaliatory responses from an adaptive opponent. This makes the "fixed strategy" look terrible in hindsight. The classical metric cannot distinguish between a bad strategy and a good strategy that was punished by a responsive adversary.

Defining Repeated Policy Regret

To fix this, the authors introduce a new metric: Repeated Policy Regret (RP-Regret). Unlike external regret, RP-Regret is native to the game-theoretic setting. It measures the difference between realized utility and the utility of the best adaptive strategy in hindsight. This comparator strategy is itself capable of responding to the history of play.

Because RP-Regret accounts for how a deviation today alters behavior tomorrow, the optimization problem is harder. The authors identify three pillars that make minimizing this regret possible:

1. Sublinear Variation: The comparator strategy cannot change erratically. It must evolve with controlled, slow variation over time.
2. Imperfect Recall: Players cannot possess "infinite" memory. The authors propose Exponential Decay Memory (EDM). In EDM, a player's sensitivity to the distant past decays exponentially. This prevents players from using actions as complex information carriers to manipulate the game history.
3. Non-convex Optimization: The loss function depends on the product of strategies across consecutive timesteps. This makes the objective non-convex (meaning it may have multiple local minima rather than one global optimum).

The paper proposes three algorithmic paths. One uses an optimization oracle to handle non-convexity directly. A second minimizes a "Local RP-Regret" (LRP-Regret). This is a convex, linearized surrogate that looks only at one-step deviations. A third reformulates the game as a Markov game. This shifts optimization from the strategy space to the "occupancy measure" space (the long-term distribution of states and actions).

Convergence Toward Cooperation

The RP-Regret framework can recover higher-utility equilibria. In the Stag Hunt game, players must choose between a high-reward "Stag" and a low-reward "Hare." Standard learning often traps players in the inefficient "Hare-Hare" equilibrium.

The authors report that minimizing the LRP-Regret surrogate helps players converge to the superior "Stag-Stag" equilibrium. As shown in, average utility in the Stag Hunt game increases as the memory length $M$ increases.

The experiments show that with sufficient memory, LRP-Regret minimization encourages coordination. This reaches a utility of 1.0 for both players. This shows that accounting for opponent response can shape interactions toward cooperation.

Complexity and Computational Limits

This framework is not a universal panacea. The authors identify several fundamental hurdles. First, the "imperfect recall" condition is essential. If players have perfect, infinite memory, achieving sublinear RP-Regret is mathematically impossible ($\Omega(T)$). In that regime, an opponent can exploit any pattern a player establishes.

Second, there is a trade-off between metric sophistication and computational tractability. Direct minimization of RP-Regret is non-convex and potentially intractable without a specialized oracle. While the LRP-Regret surrogate offers a convex path, it is an approximation. Practitioners must balance "true" policy regret against the difficulty of calculating the influence of a single deviation on an infinite future. Finally, the convergence rates—such as the $T^{0.8}$ upper bound for the oracle-based algorithm—suggest that settling into stable equilibria may require significant time scales.

The Verdict: A Necessary Shift for Multi-Agent AI

Moving from external regret to RP-Regret shifts the view of agents. They are no longer learners in a vacuum. Instead, they are participants in a living ecosystem. For engineers building multi-agent reinforcement learning (MARL) systems, the takeaway is vital. If agents interact with intelligent, adaptive entities, optimizing for standard external regret leads to suboptimal, "defensive" behavior.

The research supports adopting these concepts for high-stakes coordination. However, it carries a caveat. The reliance on bounded memory and specific variation constraints means these algorithms are currently optimized for structured environments. They are not yet ready for the chaotic, unbounded interactions of the real world. Future work must relax these memory requirements or find ways to approximate the occupancy measure in higher-dimensional spaces.

Figures from the paper