PaperlayerView exact revision on arXiv

Source-linked AI summary

Regret Minimization with Adaptive Opponents in Repeated Games

Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

arXiv:2606.06486v1cs.LGcs.AIcs.GT

TL;DR

Adaptive opponents make external regret inadequate for repeated games because responses depend on play histories. The paper introduces RP-Regret, derives conditions and algorithms for minimizing its non-convex objective, and connects regret minimization to equilibrium learning, including a cooperative Iterated Prisoner’s Dilemma outcome.

  • Problem

    External regret does not capture repeated-game opponents that respond to histories, while existing adaptive-regret notions can be inapplicable or computationally intractable.

  • Method

    The paper defines RP-Regret with adaptive opponents and dynamic comparators, derives variation and memory conditions, and proposes oracle, linearized-surrogate, and slow-opponent minimization algorithms.

  • Results

    In Iterated Prisoner’s Dilemma, tit-for-tat achieves utility 0.6 for each player with sublinear RP-Regret, compared with defect-defect at utility 0.2 under external-regret minimization.

  • Takeaways & Limitations

    When all players minimize RP-Regret or its linearized variant, certain subgame perfect equilibria of repeated games can be learned.

  • Takeaways & Limitations

    Sublinear RP-Regret requires additional memory restrictions; without them, regret is linear in the worst case, and state-passing can prevent sublinear regret even with m = 1.

Abstract

from arXiv · show

In this paper, we study regret minimization in repeated games with \emph{adaptive} opponents who can respond based on histories of play. The standard metric of \emph{external regret} in online learning is known to fail to capture such adaptivity. To account for players' counterfactual reasoning, we introduce {\tt Repeated Policy Regret (RP-Regret)}, a game-theoretic metric that measures the difference between the \emph{realized} and the \emph{best-in-hindsight} accumulated utility when all players can \emph{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. We first identify necessary conditions for obtaining {\tt RP-Regret} sublinear in time, on the variation of the player's comparator strategies in the regret definition and on the memories of both the comparator and opponents' strategies. We then study additional conditions and provable algorithms to minimize {\tt RP-Regret}, which is by definition \emph{non-convex} in the strategy space. To address this challenge, we propose three algorithms: (i) one based on an optimization oracle, as assumed in some prior work in online non-convex learning; (ii) one that minimizes a convex and \emph{linearized} surrogate of {\tt RP-Regret} at each iteration; (iii) one that directly minimizes {\tt RP-Regret} when opponents change strategies slowly. Furthermore, when all players can run algorithms to minimize the {\tt RP-Regret} (or its linearized variant), certain subgame perfect equilibria of the repeated game can be learned. We also provide experiments showing that minimizing our regret notions can lead to more cooperative solutions with higher utility in games such as Stag-Hunt.

1 Introduction

Repeated games can support higher-utility equilibria than one-shot games, but external regret fails when opponents respond to play histories. The paper introduces RP-Regret as a native repeated-game metric and develops methods to minimize it despite non-convexity.

  • Motivation: Iterated games can have equilibria with higher utility for both players than equilibria in corresponding one-shot games.The introduction contrasts Prisoner’s Dilemma with Iterated Prisoner’s Dilemma.
  • Motivation: External regret assumes losses depend only on time, so it cannot capture opponents whose actions respond to the history of play.This mismatch matters because a player’s action can affect opponents’ subsequent decisions.
  • Prior limitations: Policy Regret handles environments with memory, but bounded-memory assumptions can be too restrictive when early deviations alter play well beyond the memory window.Response Regret allows whole-history dependence but can be computationally intractable or otherwise difficult to apply in repeated games.
  • Contributions: RP-Regret compares realized accumulated utility with the best hindsight comparator while allowing adaptive opponents and time-varying comparator strategies.The paper positions this metric as natural to repeated games while retaining generality and computational tractability as design goals.
  • Contributions: The paper proposes three minimization approaches: non-convex optimization oracles, convex linearized surrogates, and direct minimization against slowly changing opponents.The linearized surrogate is called Local Repeated Policy Regret (LRP-Regret).
  • Illustrative result: In Iterated Prisoner’s Dilemma, tit-for-tat yields utility 0.6 for each player and sublinear RP-Regret, whereas external-regret minimization converges to defect-defect with utility 0.2 each.Tit-for-tat suffers linear external regret in this example, while RP-Regret captures the cooperation-promoting outcome.

2 Preliminaries

The preliminaries define repeated matrix games, histories, history-dependent strategies, expected loss, and the resulting optimization challenge. Expected loss over repeated-game strategy sequences is non-convex, motivating oracle, linearization, or variable-lifting approaches.

  • Repeated matrix games: A repeated matrix game has N ≥ 2 players, individual action sets, joint action profiles, and losses Li(at) ∈ [0,1] at each timestep.For two players, the loss objects are matrices; for more players, they are tensors.
  • History and strategy: A history is a sequence of past joint actions, with L(h) denoting its length and concatenation written as (h,a) or (h,h′).Hm denotes histories of length m, while H collects histories across lengths.
  • History and strategy: A player’s strategy maps histories to action distributions, and joint product strategies multiply players’ conditional action probabilities.Strategies may condition on the full history or a truncated portion of it.
  • Expected loss: The probability of a history is defined by multiplying the conditional probabilities of its successive action profiles under the strategy sequence.This history probability supports the expected-loss definition for play beginning from an initial history.
  • Expected loss: Expected loss sums each terminal action’s loss weighted by the probability of the corresponding history under the strategy sequence.The strategy input has m + 1 steps when the relevant history has length m.
  • Optimization challenge: Repeated-game expected loss is non-convex in the strategy sequence, so optimization requires a non-convex oracle, linearization, or lifting the variable dimension.The paper later uses occupancy measures for the Markov-game lifting approach.

3 A New Metric: Repeated Policy Regret (RP-Regret)

RP-Regret compares realized loss with the best hindsight comparator while allowing adaptive opponents and history-dependent responses. Sublinear minimization requires restrictions on comparator variation and player memory, motivating several tractability-preserving approaches.

  • RP-Regret definition: RP-Regret compares the realized accumulated loss with the best-response expected loss of a comparator strategy.The comparator may be constrained to a smaller strategy class to improve tractability.
  • RP-Regret definition: Unlike external regret, a comparator deviation changes losses at later timesteps because adaptive opponents respond to the altered history.The changed action distribution modifies future histories and opponents’ corresponding strategies.
  • RP-Regret definition: Unrestricted strategy memory can make RP-Regret linear in the worst case, so the paper imposes memory restrictions on players and comparators.The paper distinguishes this setting from adaptive regret when strategies may change over time.
  • Necessary conditions: Sublinear RP-Regret requires sublinear comparator variation and imperfect recall, with exponential-decay memory providing a quantitative surrogate.These conditions constrain how quickly comparators change and how strongly strategies depend on distant history.
  • Necessary conditions: Bounded memory alone can permit action-based state passing, whereas exponential decay makes policies with the same recent suffix nearly indistinguishable.The indistinguishability improves exponentially with suffix length, and retaining L = O(log(1/ϵ)) recent steps can make earlier history negligible.
  • Minimization approaches: The paper studies direct non-convex optimization, convex linearized surrogates, and a Markov-game reformulation for minimizing RP-Regret.The necessary-condition summary supports sublinear RP-Regret with a non-convex optimization oracle when Condition 3 replaces Condition 2.

4 RP-Regret Minimization

The paper develops several ways to minimize the non-convex RP-Regret, including local deviations, linearized surrogates, occupancy-measure reformulations, and direct minimization under slowly changing opponents.

  • RP-Regret is difficult to minimize directly because expected loss is non-convex in strategies due to products across consecutive timesteps.The paper addresses this challenge with three approaches: non-convex optimization oracles, linearization, and a Markov-game reformulation.
  • 4.1 Minimizing a Surrogate: Local Repeated Policy Regret: Local Repeated Policy Regret restricts deviations to one action at one timestep, following the one-step deviation principle for subgame-perfect equilibrium.The weaker regret notion still inherits the necessary conditions identified for RP-Regret minimization.
  • 4.1 Minimizing a Surrogate: Local Repeated Policy Regret: The local-regret expected loss is linear in the deviating strategy, enabling projected gradient descent updates.The update uses learning rate η > 0; Theorem 4.1 provides a sublinear local-regret guarantee under opponent and comparator conditions.
  • 4.2 RP-Regret Minimization: A direct RP-Regret algorithm is also proposed when opponents change their strategies slowly.This approach requires the opponents to satisfy the same slow-variation condition used for the comparator strategies.
  • 4.2.2 Occupancy-Measure-based Regret Minimization in the Markov Game: The induced Markov game uses M-step histories as states, with transitions shifting the history and appending the current joint action.M-bounded memory avoids the exponentially growing state space of using the whole history, and unbounded memory can be approximated under Condition 3.
  • 4.2.2 Occupancy-Measure-based Regret Minimization in the Markov Game: Occupancy measures convexify the learning problem because infinite-horizon expected loss is linear in occupancy measures, while strategies can be recovered from them.The algorithm updates the occupancy measure at each timestep and handles time-varying linear constraints determined after each proposed update.
  • 4.2.2 Occupancy-Measure-based Regret Minimization in the Markov Game: Under the Markov-game conditions, expected finite-horizon loss approaches infinite-horizon loss with exponentially decreasing error and becomes independent of the initial distribution.Algorithm 2 achieves sublinear RP-Regret and sublinear accumulated constraint violation under the stated variation and memory conditions.

5 Equilibrium Computation via RP-Regret Minimization

The paper connects RP-Regret minimization to approximate equilibria in infinitely repeated games, with deviation bounds determined by comparator variation. It also gives an algorithm for approximate SPCCE with O(T)-bounded deviation, while leaving a corresponding no-LRP-Regret algorithm open.

  • Relationship between RP-Regret and equilibria: Sublinear RP-Regret with comparator variation bounded by PT yields an approximate SPNE with O(PT)-bounded deviation.The comparator variation bound is the accumulated variation over the relevant horizon.
  • Relationship between RP-Regret and equilibria: Sublinear LRP-Regret yields an approximate SPNE with O(T)-bounded deviation when regret is measured against comparators without a variation budget.This connection assumes the players and comparators satisfy the stated condition.
  • Limitations: The direct LRP-Regret algorithms do not currently provide this equilibrium guarantee because they require sublinear comparator variation.The paper identifies development of no-LRP-Regret algorithms for this setting as future work.
  • Finite repeated games: For finitely repeated games, sublinear RP-Regret or LRP-Regret produces an approximate equilibrium or coarse correlated equilibrium rather than a subgame perfect equilibrium.The corresponding equilibrium is for the finite repeated game.
  • Algorithmic guarantee: Algorithm 3 computes an approximate SPCCE with O(T)-bounded deviation in infinitely repeated matrix games under Condition 4.Its proof models the repeated game as a Markov game and applies existing results for CCE in Markov games.

6 Conclusion

The paper introduces RP-Regret for adaptive-opponent repeated games, establishes conditions and algorithms for sublinear regret, and connects regret minimization to selected subgame perfect equilibria. It also identifies weaker equilibrium notions and payoff-structure-specific equilibrium selection as future directions.

  • Main contributions: RP-Regret measures regret in repeated games while allowing opponents to respond to play histories.The paper presents it as a metric native to repeated-game settings with adaptive opponents.
  • Main contributions: The paper identifies necessary conditions, develops provable RP-Regret minimization algorithms, and connects minimization to certain subgame perfect equilibria.These are presented as the paper’s main theoretical developments.
  • Future directions: Future work includes weaker equilibrium notions induced by RP-Regret minimization and provable equilibrium-selection results for games with particular payoff structures.The paper notes that weaker assumptions may be sufficient for computing some weaker equilibrium notions.

Supplementary Materials for “Regret Minimization with Adaptive Opponents in Repeated Games”

The supplementary material situates RP-Regret among equilibrium computation, impossibility results, rationalizing cooperation, opponent shaping, and online learning with memory. It also reports a Stag-Hunt example where LRP-Regret minimization can favor a higher-utility equilibrium.

  • Motivating example: The figure averages utilities over 10,000 runs and 100,000 iterations while varying memory lengths M = 1,2,3.Initial strategies are sampled uniformly and the learning rate is η = 0.01.
  • Motivating example: In Stag-Hunt, minimizing LRP-Regret can converge more often to Stag-Stag, which gives both players utility 1.0.The example attributes this possibility to the larger set of equilibria induced by the new regret notions.
  • Equilibrium computation: Classical no-external-regret learning converges in time average to coarse correlated equilibria of the one-shot matrix game.The supplementary discussion presents this as a standard result in repeated normal-form games.
  • Impossibility results: Computing equilibria in infinitely repeated games can be hard, and directly minimizing RP-Regret may not be computationally tractable without further assumptions.The cited hardness discussion contrasts the paper’s CCE computation with Nash equilibrium computation.
  • Related work: Prior work studies cooperative equilibria under bounded strategy complexity, empirical opponent shaping without general theoretical guarantees, and policy regret for environments with memory.These strands motivate the paper’s repeated-game-specific regret formulation.

C Proof for Example 1.1

The proof contrasts external regret with RP-Regret in iterated Prisoner’s Dilemma using tit-for-tat. Because RP-Regret accounts for adaptive responses, tit-for-tat has only constant regret, unlike its linear external regret.

  • Tit-for-tat and external regret: Mutual tit-for-tat yields time-average utility 0.6, exceeding the one-shot Nash equilibrium outcome.The players start with C and continue cooperating under tit-for-tat.
  • Tit-for-tat and external regret: Mutual tit-for-tat incurs external regret (1.0 − 0.6)T against always defecting, so sublinear external regret forces convergence toward D.Defect is the strictly dominant action in the one-shot Prisoner’s Dilemma.
  • RP-Regret analysis: Before the final round, the best comparator does not deviate from C; any beneficial deviation can occur only at t = T.The proof uses deterministic deviations and induction over the history generated by tit-for-tat.
  • RP-Regret analysis: The resulting RP-Regret is at most 0.4, which is constant and therefore sublinear in T.The final-round utility increase is 1.0 − 0.6 = 0.4.
  • RP-Regret analysis: RP-Regret evaluates deviations through their effects on future rounds because the opponent adapts to the player’s history.This is the key distinction from external regret, which treats opponents as non-adaptive.
  • Infinite horizon: In the infinitely repeated game, the nonexistent final round removes the remaining incentive to deviate from tit-for-tat.The proof therefore aligns with tit-for-tat being a Nash equilibrium in infinitely repeated Prisoner’s Dilemma.

D.1 Hardness Results in Table 1

The hardness results identify comparator variation and memory restrictions as necessary for sublinear RP-Regret. They also show that truncating history can approximate the full objective under a sufficiently small responsiveness parameter.

  • Necessary conditions: Without sublinear comparator variation, RP-Regret is Ω(T) in the worst case, even when comparator and opponent satisfy stronger memory conditions.The result is established in Lemma D.1.
  • Necessary conditions: Allowing the comparator perfect recall causes Ω(T) RP-Regret, even when comparator variation and opponent memory satisfy the required conditions.The comparator can exploit history length to behave differently across timesteps.
  • Necessary conditions: Allowing the opponent perfect recall causes Ω(T) RP-Regret, even when the comparator satisfies the variation and memory conditions.This lower bound remains valid under a constant bounded-memory constraint on the opponent.
  • Hardness constructions: An adaptive opponent can create a constant loss gap between the comparator and the learner, yielding linear RP-Regret in an augmented Prisoner’s Dilemma.The opponent’s later actions depend on its initial choice and the learner’s play.
  • Truncated-history approximation: When Condition 3 holds for all players and γ ≤ 1/[2(N+2)], truncating history to m steps yields approximation error that decays exponentially with m.The truncated loss depends only on strategies from timestep t−m through t, reducing optimization complexity.
  • Truncated-history approximation: The unary-loss formulation permits online-learning minimization when the comparator and learner satisfy the required variation condition, producing sublinear truncated regret.The supplied passages state that the relevant right-hand side is sublinear in T under Condition 1.

H.1 Hardness Results

The local RP-Regret hardness results show that each of the main regularity conditions is necessary: dropping comparator variation, comparator memory limits, or opponent memory limits can force linear regret.

  • Necessary conditions: Without comparator variation control, Local RP-Regret is Ω(T) even when both comparator and opponent have bounded memory.The coin-flipping construction gives a per-timestep regret gap of at least 0.5.
  • Necessary conditions: With comparator variation controlled but comparator perfect recall allowed, Local RP-Regret remains Ω(T), even when the opponent has bounded memory.The comparator uses history length to implement different timestep-dependent guesses.
  • Necessary conditions: When only the comparator satisfies both variation and memory restrictions, allowing an opponent perfect recall still yields Ω(T) Local RP-Regret.The augmented Prisoner’s Dilemma construction supplies the adaptive opponent strategy.
  • Hardness constructions: The local hardness proofs use coin-flipping and augmented Prisoner’s Dilemma games to separate the learner’s realized loss from a responsive comparator deviation.The constructions are analyzed through history-dependent opponent responses and local deviations.

I.2 Formal Version and Proof of Theorem 4.4

The formal proof analyzes occupancy-measure optimization for the bounded-memory repeated game and connects constrained policy-gradient updates to the regret bound in Theorem 4.4.

  • I.2 Formal Version and Proof of Theorem 4.4: Algorithm 2 represents bounded-memory repeated-game strategies with occupancy measures and converts them back into joint strategies by normalizing q_t(h,a).The occupancy-measure constraints enforce nonnegativity, normalization, and history-flow consistency.
  • I.2 Formal Version and Proof of Theorem 4.4: The theorem’s bound combines optimization error, Lipschitz constants, action-space size, memory length, and comparator variation terms.The proof repeatedly invokes occupancy-measure continuity and the convergence guarantee of Algorithm 5.
  • I.2 Formal Version and Proof of Theorem 4.4: The occupancy-measure distance is controlled by policy distance, completing the link between strategy variation and the theorem’s regret analysis.The proof derives this relation by choosing a loss that identifies a particular history state.
  • I.2 Formal Version and Proof of Theorem 4.4: Uniform lower bounds on action probabilities imply lower bounds on occupancy measures, supporting the continuity and regret estimates.The proof applies these bounds through the feasible occupancy-measure set and the induced player-1 marginal.
  • I.2 Formal Version and Proof of Theorem 4.4: The constrained update uses a sign-based feasibility condition evaluated at each timestep to maintain the comparator’s admissibility.For product-form comparator profiles, the corresponding constraint quantity is zero, so feasibility holds.

J.1 LRP-Regret and Subgame Perfect Equilibrium

The paper connects sublinear LRP-Regret to approximate subgame-perfect equilibrium in infinitely repeated games, while noting that the available regret algorithm does not yet achieve the required no-LRP-Regret guarantee.

  • J.1 LRP-Regret and Subgame Perfect Equilibrium: The analysis studies infinitely repeated matrix games by dividing T timesteps into K epochs of length T0.This epoch decomposition supports transferring finite-game equilibrium guarantees to the infinite horizon.
  • J.1 LRP-Regret and Subgame Perfect Equilibrium: Under the stated positivity condition, the resulting equilibrium is an approximate SPNE.The proof uses fixed history distributions and the performance-difference argument to establish subgame perfection.
  • J.1 LRP-Regret and Subgame Perfect Equilibrium: A local deviation at a history is compared with a proxy strategy that matches the deviating action at that history and otherwise follows the original strategy.This proxy construction lets local regret control deviation gains.
  • J.1 LRP-Regret and Subgame Perfect Equilibrium: An approximate equilibrium for a K-repeated matrix game satisfying bounded-memory conditions is also an approximate equilibrium for the infinitely repeated game.Lemma J.2 provides the finite-to-infinite transfer used in the equilibrium argument.
  • J.1 LRP-Regret and Subgame Perfect Equilibrium: The subgame-perfectness conclusion extends from player 1 to every player by symmetry, with each player’s local regret appearing in the corresponding bound.The argument assumes action probabilities are uniformly bounded below.
  • J.1 LRP-Regret and Subgame Perfect Equilibrium: The theorem relating approximate robust SPNE to LRP-Regret requires sublinear regret against a comparator with PT = Θ(T).This condition permits comparator variation linear in T in the construction.

K.1 Computation of SPCCE

This section develops Algorithm 3 and supporting lemmas for computing an approximate O(T)-robust SPCCE. The analysis combines regret bounds, finite-memory approximation, and repeated-game connectivity results.

  • Regret analysis: Lemma K.1 extends the analysis to a regret upper bound for every player, replacing |A1| with |Ai| and taking the maximum across players.The bound applies to comparators satisfying Condition 4 with the uniform strategy as ν(i).
  • Equilibrium computation: When all players achieve sublinear RP-Regret against comparators with bounded accumulated variation, the analysis constructs an approximate SPNE with bounded deviation and then an approximate robust SPCCE.Algorithm 3 samples a strategy uniformly from T0 iterations before applying it across horizons.
  • Algorithm 3: Algorithm 3 is presented as a full-information method for computing SPCCE-related strategies.The algorithm uses a Euclidean regularizer over the action simplex and initializes player 1 uniformly.
  • Regret analysis: Lemma K.2 provides a timestep-wise upper bound on Algorithm 3's value relative to any comparator strategy.Its proof proceeds by backward induction from the terminal horizon.
  • Finite-memory approximation: Under the forgetful condition, finite-memory approximations control how much past histories affect current action distributions.Lemma L.2 assumes γ ≤ 1/(2(N+2)) and establishes finite-memory approximation errors.
  • Markov-game dynamics: Condition 3 yields an induced Markov game whose expected time-average loss exists and is independent of the initial distribution.With full-support policies, the induced Markov chain is irreducible, which supports this conclusion.
  • Fast mixing: Lemma M.4 establishes a vertex from which every other vertex is reachable within log2 |HM| + 1 steps.This short-connectivity property is used in the fast-mixing analysis.
Loading 2606.06486v1…