Skip to main content
Back

MIT Fixes Online Learning's Blind Spot Against Adaptive Opponents With RP-Regret

A new regret metric called RP-Regret enables agents to reason about adaptive opponents in repeated games, unlocking cooperative equilibria that standard external regret cannot reach

Paper, Full Access
  • Introduces Repeated Policy Regret (RP-Regret), a new regret metric for repeated games where all players can respond to the full history of play, accepted at COLT 2026.
  • Proves that standard external regret fails in adaptive-opponent settings — e.g., tit-for-tat in Iterated Prisoner's Dilemma has linear external regret despite being a Nash equilibrium.
  • Identifies necessary conditions for sublinear RP-Regret: the comparator must have sublinear variation, and both comparator and opponents must satisfy an exponential decay memory condition.
  • Proposes three algorithms: an oracle-based method, a convex surrogate (LRP-Regret) via local linearization, and an occupancy-measure approach via Markov game reformulation for slowly-changing opponents.
  • Shows that when all players minimize RP-Regret, play converges to Subgame Perfect Equilibria — enabling cooperative outcomes like mutual cooperation in IPD that external regret cannot reach.
  • Experiments on Stag-Hunt demonstrate that LRP-Regret minimization steers play toward the higher-utility Stag-Stag equilibrium more reliably than baseline approaches. No code is currently released.

Standard online learning assumes your opponent is oblivious , that their future moves are independent of what you do. But in real strategic interactions, opponents watch you and adapt. A new paper from MIT and the University of Maryland, accepted at COLT 2026, confronts this gap head-on by introducing Repeated Policy Regret (RP-Regret) , a regret metric purpose-built for repeated games where every player can respond to the history of play.

The problem with external regret in games

External regret , the workhorse of online learning , measures how much worse you did compared to the best fixed action in hindsight. It works well when your environment is static or oblivious. But in a repeated game, your opponent is a strategic agent who reacts to what you do. External regret is meaningful when the adversary is oblivious, but it does not admit any natural interpretation when the adversary is adaptive. The problem stems from the fact that in the definition of external regret, the benchmark is a function of the player's actions.

The classic example is the Iterated Prisoner's Dilemma (IPD). The famous tit-for-tat strategy , cooperate first, then mirror your opponent , is a Nash equilibrium of the infinitely repeated game and yields a time-average utility of 0.6 for both players. But any player running a no-external-regret algorithm will converge to always defecting, earning only 0.2. The standard metric of external regret in online learning is known to fail to capture such adaptivity. Tit-for-tat suffers linear external regret compared to always defecting , even though it's the better strategy when your opponent is adaptive.

Introducing RP-Regret

The paper introduces Repeated Policy Regret (RP-Regret), which measures the difference between your realized accumulated loss and the best-in-hindsight accumulated loss when all players can respond to the history of play. The key distinction from prior work: the comparator strategy is also allowed to be dynamic and history-dependent, and the opponents are allowed to be fully adaptive , not just memory-bounded in a restricted sense.