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 can react to play histories, making external regret inadequate for repeated-game counterfactual reasoning. The paper introduces Repeated Policy Regret, derives conditions and algorithms for minimizing it, and shows that it can support higher-utility cooperative outcomes and equilibrium learning.

  • Problem

    External regret does not capture counterfactual reasoning when opponents adapt to histories in repeated games.

    Source: §3.1 · p. 5

  • Method

    The paper introduces RP-Regret and studies necessary conditions, optimization methods, linearized surrogates, and slow-opponent algorithms for minimizing it.

    Source: §1 · p. 3, §3.1 · p. 5, §3.2 · p. 6

  • Results

    In Iterated Prisoner’s Dilemma, RP-Regret supports the higher-utility tit-for-tat outcome with utility 0.6 per player, compared with 0.2 under external-regret minimization.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Sublinear RP-Regret can yield approximate equilibria and can enable learning certain subgame perfect equilibria in repeated games.

    Source: §5.2 · p. 14, §6 · p. 15

    Sublinear RP-Regret requires restrictions on comparator variation and player memory, because unrestricted memory can produce linear worst-case regret.

    Source: §3.1 · p. 6, §3.2 · p. 7

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 Massachusetts Institute of Technology · 2 OpenAI · 1 Introduction

The introduction motivates Repeated Policy Regret (RP-Regret) as a repeated-game-native alternative to external regret that accounts for adaptive opponents and can support higher-utility equilibria. It summarizes necessary conditions, three minimization approaches, equilibrium implications, and cooperative empirical benefits.

1 Introduction

  • Repeated games can yield higher-utility equilibria than one-shot games, as illustrated by Iterated Prisoner’s Dilemma versus Prisoner’s Dilemma.In Prisoner’s Dilemma, defect-defect is the only Nash equilibrium and gives both players relatively low utility, whereas Iterated Prisoner’s Dilemma has a higher-utility equilibrium.Source: §1 · pp. 1–2
  • External regret is inadequate against responsive opponents because actions can alter future play, potentially producing suboptimal equilibria and making no-external-regret impossible.Classical external regret assumes losses depend only on the timestep, unlike game-theoretic environments where opponents respond to play histories.Source: §1 · p. 2
  • Existing adaptive-regret notions are either restrictive or computationally intractable: bounded memory, constant-action comparators, insensitive opponents, or exponentially large history-dependent strategy spaces.Policy Regret requires m-bounded memory; Response Regret uses exponentially large history-dependent strategies; and Arora et al. (2018) restricts comparators and opponent adaptability.Source: §1 · p. 2
  • RP-Regret measures realized utility against the best in-hindsight accumulated utility when opponents respond to history, while permitting adaptive opponents and dynamic comparator strategies.The notion is designed specifically for repeated games while retaining broad strategy spaces and computational tractability goals.Source: §1 · pp. 2–3
  • The paper derives necessary conditions for sublinear RP-Regret involving comparator variation and the memories of comparator and opponent strategies.These conditions characterize how strategy changes and memory constrain the possibility of sublinear regret.Source: §1 · p. 3
  • Because RP-Regret is non-convex, the paper proposes an optimization-oracle method, convex linearized LRP-Regret, and direct RP-Regret minimization when opponents change slowly.A further approach reformulates the repeated game as a Markov game and optimizes a convex occupancy-measure objective.Source: §1 · p. 3
  • The occupancy-measure approach controls discrepancies between extracted and actual opponent strategies, converts constraint violations into RP-Regret bounds, and redesigns non-convex behavioral-form constraints.The method uses time-varying online-learning constraints to prevent projection errors from accumulating.Source: §1 · p. 3
  • In Iterated Prisoner’s Dilemma, tit-for-tat achieves time-average utility 0.6 with sublinear RP-Regret, whereas external-regret learning converges to defect-defect with utility 0.2 and tit-for-tat has linear external regret.The example demonstrates that RP-Regret can capture a cooperation-promoting strategy missed by classical external regret.Source: §1 · p. 4

2 Preliminaries

The paper models repeated games in which players choose history-dependent actions and incur bounded losses over joint action profiles. It formalizes histories, strategy profiles, and expected loss, emphasizing that repeated-game expected loss is generally non-convex in the strategy sequence.

Repeated (Matrix) Games

  • Repeated games involve N ≥ 2 players selecting actions from individual action sets, forming joint action profiles and incurring losses in [0,1] each timestep.The loss functions are called matrices for two-player games and tensors for games with more players.Source: §2 · p. 4

History and Strategy

  • A history is a sequence of prior joint actions, and each player uses a history-dependent strategy mapping histories to distributions over their actions.Unless explicitly correlated, joint strategies are represented as products of individual strategies, and histories may be full or truncated.Source: §2 · pp. 4–5

Expected Loss in Repeated Games

  • The expected loss over repeated play is defined by summing each action’s loss weighted by the probability of the corresponding history under a sequence of strategy profiles.The probability accounts for sequential action sampling conditioned on the initial history.Source: §2 · p. 5
  • Unlike one-shot normal-form games, repeated-game expected loss is non-convex in the strategy sequence, motivating optimization oracles, linearization, or lifted-variable methods.These alternatives are developed later as non-convex optimization, convexification through linearization, and dimension lifting.Source: §2 · p. 5

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

RP-Regret compares realized loss with the best history-responsive comparator when adaptive opponents can react to deviations. Sublinear minimization requires slowly varying comparators and memory restrictions that limit dependence on distant history.

3.1 RP-Regret Definition

  • The comparator class may be restricted to make optimization tractable, yielding a weaker comparator than the full strategy space.The paper notes that these restrictions can make the comparator space smaller than the unrestricted sequence space.Source: §3.1 · p. 6
  • RP-Regret compares realized accumulated loss with the best comparator strategy while opponents respond to the altered history induced by deviations.Unlike external regret, a deviation can affect losses at later rounds because adaptive opponents may change their strategies.Source: §3.1 · p. 6
  • With unrestricted memory, RP-Regret can be linear in the worst case, motivating additional restrictions on how players respond to histories.Under those restrictions, RP-Regret differs from adaptive regret as defined by Loftin and Oliehoek (2022), because strategies may change over time.Source: §3.1 · p. 6

3.2 When is Minimizing RP-Regret Possible?

  • Sublinear RP-Regret requires both sublinear comparator variation and imperfect recall for players and the comparator.These are identified as two basic necessary conditions for achieving sublinear regret in T.Source: §3.2 · pp. 6–7
  • The proposed exponential-decay memory condition makes distant history negligible after retaining only O(log(1/ϵ)) recent observations.It models imperfect recall through finite effective memory and is satisfied by several regularized mirror-descent-type updates.Source: §3.2 · p. 7
  • Simple bounded memory is insufficient because actions can encode earlier events, whereas exponential decay prevents this near-perfect state passing.This encoding phenomenon can preclude sublinear regret even when m = 1; the paper therefore adopts the stronger indistinguishability property of exponential decay.Source: §3.2 · p. 7, Table 1 · p. 8

4 RP-Regret Minimization

Section 4 addresses RP-Regret’s non-convexity with three approaches: a non-convex optimization oracle, locally convexified LRP-Regret, and a Markov-game reformulation for slowly changing opponents. The latter approaches use convex surrogates or occupancy measures to obtain computationally efficient algorithms and sublinear guarantees under memory, exploration, and variation conditions.

4 RP-Regret Minimization

  • The proposed approaches establish sublinear RP-Regret under sufficient comparator, opponent, memory, exploration, and variation conditions, including a non-convex-oracle route and an efficient Markov-game algorithm.The oracle approach requires Condition 1 for the comparator and Condition 3 for the comparator and opponents; the Markov-game algorithm also achieves sublinear accumulated constraint violation.Source: §4 · p. 8, §4.2.4 · p. 12

4.1 Minimizing a Surrogate: Local Repeated Policy Regret

  • LRP-Regret replaces global deviations with one-step deviations, yielding a locally convex surrogate whose expected loss is linear in the comparator strategy and amenable to projected gradient descent.The weaker regret notion retains the necessary conditions for RP-Regret minimization, while one-step deviation is motivated by the SPNE principle.Source: §4.1 · pp. 8–9
  • With an appropriate learning rate and slowly varying comparator, LRP-Regret is sublinear when opponents satisfy Condition 3, with complexity depending on memory, action-space size, and comparator variation.The bound hides factors polynomial in m and logarithmic in T, while maintaining an exponential dependence on |A|^(m+1) from tracking histories.Source: §4.1 · p. 9

4.2 Minimizing RP-Regret with Slowly-Changing Opponents

  • When opponents change strategies slowly, RP-Regret can be minimized directly by reformulating the repeated game as an infinite-horizon average-loss Markov game with bounded memory.Condition 1 must additionally hold for opponents; bounded-memory conversion under Condition 3 controls the approximation error while avoiding exponentially growing full-history state spaces.Source: §4.2 · p. 9, §4.2.1 · p. 10

4.2.1 Reformulating Repeated Games with Bounded Memory as Markov Games

  • The induced Markov game uses length-M histories as states, original actions as actions, history-shift transitions, and stage losses inherited from the repeated matrix game.Its expected time-average loss equals the repeated game’s expected average loss when the same joint Markov strategy is used at every timestep.Source: §4.2.1 · p. 10

4.2.2 Occupancy-Measure-based Regret Minimization in the Markov Game

  • Occupancy measures convexify the Markov-game problem because expected loss is linear in them, while adaptive opponents impose time-varying linear consistency constraints.The proposed constraint avoids the non-differentiability caused by absolute-value constraints and recovers player 1’s strategy from the occupancy measure.Source: §4.2.2 · pp. 10–11

4.2.3 Convexifying Condition 3 and the Overall Algorithm

  • Condition 4 replaces non-convex forgetfulness with a convex exploration constraint requiring bounded memory and a history-independent minimum probability on an exploration strategy.Under Condition 4, the induced Markov game’s average loss exists, and finite-horizon loss approaches infinite-horizon loss with exponentially decreasing error, independently of the initial distribution.Source: §4.2.3 · pp. 11–12

4.2.4 Theoretical Guarantees

  • Algorithm 2 guarantees sublinear RP-Regret and accumulated constraint violation when players and the comparator satisfy Condition 4 and total opponent-plus-comparator variation is sufficiently sublinear.Condition 4 is linear in the occupancy measure, so the algorithm can enforce it efficiently by projection.Source: §4.2.4 · p. 12

5 Equilibrium Computation via RP-Regret Minimization

The section connects RP-Regret minimization to equilibrium computation in infinitely repeated general-sum games, defining bounded-deviation equilibrium notions and proving that sublinear regret can yield approximate subgame-perfect equilibria. It also gives an algorithm for computing an approximate SPCCE with O(T)-bounded deviation.

5.1 Equilibria in Repeated Games

  • Bounded-deviation SPCCE permits correlated strategies, while the corresponding robust SPNE restricts strategies to products; setting PT = Θ(T) recovers the classical equilibrium notions.The deviation bound restricts the comparator strategies allowed in the equilibrium definition.Source: §5.1 · p. 13

5.2 Relationship between RP-Regret and Equilibria

  • When all players achieve sublinear RP-Regret against comparators with cumulative variation bounded by PT0, their limiting strategies form an approximate SPNE with O(PT)-bounded deviation.The result holds under the stated comparator and player conditions, and applies at any fixed timestep as T approaches infinity.Source: §5.2 · pp. 13–14
  • Sublinear LRP-Regret similarly implies an approximate SPNE with O(T)-bounded deviation, but this relationship does not itself provide an algorithm and requires an unrestricted Θ(T) comparator-variation budget.The paper notes that directly applying the LRP-Regret algorithm may fail because it requires comparator variation sublinear in T0.Source: §5.2 · p. 14

5.3 Computing the Equilibria

  • Algorithm 3 computes an approximate SPCCE with O(T)-bounded deviation for infinitely repeated matrix games under Condition 4 and uniform strategy distributions.Its guarantee is obtained by modeling the repeated game as a Markov game and applying existing CCE results for Markov games.Source: §5.3 · p. 14

6 Conclusion

The paper introduces RP-Regret for repeated games with adaptive opponents, establishes conditions and algorithms for sublinear minimization, and connects this minimization to computing certain subgame-perfect equilibria.

Conclusion

  • RP-Regret provides a repeated-game-native metric for adaptive opponents, with necessary conditions identified for achieving sublinear regret over time.The paper also develops additional conditions and provable algorithms to minimize RP-Regret.Source: §6 · p. 15
  • RP-Regret minimization is connected to computing certain known subgame-perfect equilibria in repeated games.Future work includes weaker equilibrium notions induced by RP-Regret and provable equilibrium selection in games with particular payoff structures.Source: §6 · p. 15

Supplementary Materials for “Regret Minimization with Adaptive Opponents in Repeated Games” … B Detailed Related Work

The supplementary materials show that LRP-Regret can guide players toward higher-utility equilibria, while related work highlights computational limits and the distinct challenges of adaptive repeated-game regret. They position the approach against equilibrium computation, cooperation, opponent shaping, and online-learning frameworks.

F Bounding Rm

  • Section F.2 addresses bounding the difference between Jm and the quantity used to bound Rm.The supplied supplementary passage identifies this as part of the analysis of bounding Rm.Source: F Bounding Rm · p. 21

A Motivating Example Details

  • Figure 1 reports average utility over 10,000 Stag-Hunt runs for 100,000 iterations, with memory lengths M = 1,2,3 and learning rate η = 0.01.Both players minimize LRP-Regret from uniformly random initial strategies.Source: Figure 1 · p. 22
  • Minimizing LRP-Regret can more often reach the higher-utility Stag-Stag equilibrium, with utility 1.0 for both players, rather than Hare-Hare.The example attributes this to the larger set of equilibria potentially induced by the new regret notions.Source: A Motivating Example Details · p. 22

B Detailed Related Work

  • Repeated-game equilibrium work uses no-regret dynamics, folk-theorem trigger strategies, and polynomial-time two-player algorithms, but multi-player extensions face NP-hard minimax computation.No-external-regret learning converges to one-shot coarse correlated equilibrium, whereas history-dependent strategies can yield different repeated-game equilibria.Source: B Detailed Related Work · p. 22
  • Directly minimizing RP-Regret may be computationally intractable: sublinear RP-Regret would imply convergence to a subgame perfect equilibrium, while computing repeated-game equilibria is hard.The cited impossibility results establish PPAD-hardness for three-player infinitely repeated games with discount factors and motivate the paper’s CCE result instead of an NE result.Source: B Detailed Related Work · p. 23
  • Unlike finite-state cooperation results, the paper shows that RP-Regret cannot be minimized when players have unlimited memory.Prior work modeled repeated-game strategies as finite-state automata and found equilibria with payoffs near cooperation.Source: B Detailed Related Work · p. 23
  • Opponent-shaping methods target adaptive opponents but generally lack convergence or performance guarantees, whereas this regret-based approach covers opponents satisfying provably necessary conditions.Stable Opponent Shaping converges only for naive learners and has no guarantee against general unknown opponents.Source: B Detailed Related Work · p. 23
  • Existing online-learning analyses typically assume convex losses or bounded memory, but repeated-game losses can be non-convex and depend on the entire history.The paper distinguishes its setting from bounded-memory games that restart the game every k + 1 rounds and from dynamic regret with sublinear comparator variation.Source: B Detailed Related Work · pp. 23–24

C Proof for Example 1.1 · D Full Statements of Hardness Results

The IPD example shows that external regret drives play toward the dominant defection action, whereas RP-Regret accounts for adaptive retaliation and remains constant under mutual tit-for-tat. The proof also explains why tit-for-tat is an equilibrium in the infinitely repeated setting.

C Proof for Example 1.1

  • Mutual tit-for-tat sustains cooperation in IPD, yielding time-average utility 0.6, above the one-shot Nash equilibrium.Source: C Proof for Example 1.1 · p. 24
  • Mutual tit-for-tat incurs linear external regret because always playing D obtains regret (1.0 −0.6)T.Source: C Proof for Example 1.1 · p. 24
  • Any IPD strategy with sublinear external regret must converge in time average to D, the strictly dominant action.Source: C Proof for Example 1.1 · p. 24
  • For RP-Regret against tit-for-tat, an optimal comparator can be taken deterministic and, along the induced deterministic history, oblivious at each deviation timestep.Source: C Proof for Example 1.1 · p. 24
  • At any timestep before the last, the comparator maximizes its two-step expected utility by choosing C, because the current deviation changes the opponent’s next action under tit-for-tat.The two-step analysis gives 1.2 −0.2w′ + w(0.4 −0.2w′), whose coefficient on w is positive for w′ ≤1.Source: C Proof for Example 1.1 · pp. 24–25
  • Thus, the best RP-Regret deviation can occur only at T, increasing utility by at most 0.4 and producing constant, hence sublinear, RP-Regret.Source: C Proof for Example 1.1 · p. 25
  • The distinction is that RP-Regret accounts for deviations’ effects on future play through opponent adaptivity, unlike external regret’s non-adaptive comparison.Source: C Proof for Example 1.1 · p. 25
  • In infinitely repeated IPD, the terminal deviation opportunity disappears, so tit-for-tat has no incentive to deviate and is an NE.Source: C Proof for Example 1.1 · p. 25

D.1 Hardness Results in Table 1 … H Minimization of Local RP-Regret

The paper establishes that sublinear RP-Regret requires bounded comparator variation and imperfect recall, then develops memory truncation and oracle-based methods to make minimization computationally tractable. These results yield exponentially accurate approximations and regret bounds under the stated conditions.

D.1 Hardness Results in Table 1

  • Sublinear RP-Regret requires sublinear comparator variation and excludes perfect recall for both comparator and opponent strategies.Violating any of these conditions causes Ω(T) RP-Regret in the worst case, even when stronger regularity conditions hold.Source: §D.1 · p. 25

H Minimization of Local RP-Regret

  • The framework therefore supports accurate RP-Regret minimization only after enforcing the memory and variation conditions identified by the hardness results.The supplied passages establish this scope through the approximation, unary-loss, and oracle analyses; no separate result for local RP-Regret is provided in the excerpt.Source: §D.1 · pp. 25–26, E Approximation of RP-Regret · p. 27, T T0.8 + CLipsm2PT · p. 32

D.1.1 Proofs of Results in Table 1

  • The hardness proofs use coin-flipping and augmented Prisoner’s Dilemma games to construct adversaries that maintain a constant comparator-versus-player gap.The opponent can retain only bounded recent memory in the Prisoner’s Dilemma construction, so finite-memory perfect recall does not avoid linear regret.Source: §D.1.1 · pp. 26–27

E Approximation of RP-Regret

  • Truncating histories to the latest m steps makes RP-Regret optimization tractable while introducing an approximation error that decays exponentially with m.Under Condition 3 for every player and γ ≤ 1/(2(N+2)), the approximation error |R^m_T−R_T| decays exponentially in m.Source: E Approximation of RP-Regret · pp. 27–28

F.1 Mitigating the Dependence on Past Strategies

  • A unary-loss formulation removes dependence on full past strategy sequences, and its regret is sublinear when the comparator and regret minimizer satisfy Condition 1.This reformulation permits standard online-learning algorithms to control the truncated regret while accounting for comparator variation.Source: §F.1 · pp. 28–29

F.2 Bounding the difference between Jm T and ¯Jm

  • Lipschitz continuity of the truncated loss bounds the difference between cumulative truncated objectives and their unary counterparts using strategy variation.The analysis combines Lipschitz continuity with a general variation inequality to control the resulting regret difference.Source: §F.2 · p. 29

G Minimization of Repeated Policy Regret with an Oracle

  • An optimization-oracle algorithm minimizes the resulting non-convex objective by restarting a non-convex online-learning procedure across episodes.The strategy space is restricted to policies satisfying Condition 3, while the analysis combines truncation, Lipschitz, and variation bounds.Source: G Minimization of Repeated Policy… · pp. 30–31

T T0.8 + CLipsm2PT

  • The oracle analysis provides a regret bound combining non-convex optimization, memory-truncation, comparator variation, and oracle-accuracy terms.The displayed bounds include terms involving m, K, T, action-set size, Lipschitz constants, and cumulative variation.Source: G Minimization of Repeated Policy… · p. 31

H.1 Hardness Results … I.1 Important Lemmas

The section establishes linear lower bounds for Local RP-Regret under insufficient memory conditions, then develops proof machinery and occupancy-measure optimization supported by performance-difference and continuity lemmas.

H.1 Hardness Results

  • Local RP-Regret is Ω(T) when both comparator and opponent satisfy only Condition 2, even though neither needs memory.A coin-flipping game yields regret at least 0.5T against an adversarial opponent, while a fixed comparator guesses correctly throughout.Source: §H.1 · p. 32
  • Local RP-Regret remains Ω(T) when only the opponent satisfies Condition 2, because an unrestricted comparator can adapt its fixed strategy to history lengths.In the coin-flipping construction, the comparator deterministically chooses different guesses across timesteps while the opponent remains adversarial.Source: §H.1 · pp. 32–33
  • Local RP-Regret is Ω(T) even when only the comparator satisfies Conditions 1 and 2, via an augmented Prisoner’s Dilemma where a single deviation changes future opponent behavior.The comparator is time-invariant and history-independent, yet the opponent’s response produces a linear regret gap.Source: §H.1 · p. 33

H.2 Proof of Theorem 4.1

  • Theorem 4.1’s proof decomposes the regret analysis into terms involving mT, m^2, C_Lips, and opponent variation P_T.The derivation invokes auxiliary lemmas and imposes γ ≤ 1/(2(N+2)) for one required bound.Source: §H.2 · pp. 34–35

I Proof of Theorem 4.4

  • Theorem 4.4’s proof implements an occupancy-measure optimizer using a constrained convex set, policy-gradient updates, and received constraints g_t.The algorithm initializes a uniform strategy and updates q_t through the specified constrained policy-gradient rules.Source: I Proof of Theorem 4.4 · p. 36

I.1 Important Lemmas

  • Under the aperiodic-unichain assumption, the performance-difference lemma relates average rewards across strategy profiles and makes the stationary distribution independent of the initial state.The analysis controls player 1 and uses the induced Markov game’s fixed stationary distribution.Source: §I.1 · pp. 36–37
  • The supporting lemmas bound Q^π, establish Lipschitz continuity of ρ^π, and lower-bound q^π when every action probability is at least γ/|A_i|.These properties provide quantitative control of average-reward changes and induced transition behavior.Source: §I.1 · pp. 37–38

I.2 Formal Version and Proof of Theorem 4.4 · T + (CQ + 2CLipsK2) |A|M+1 · J Regret and Subgame Perfect Equilibrium

The formal theorem analyzes Algorithm 2 when all players and the comparator satisfy Condition 4 with uniform strategies, establishing the stated regret bound through occupancy-measure and Lipschitz arguments. The proof also connects comparator variation and feasibility of induced product-form strategies to the bound.

I.2 Formal Version and Proof of Theorem 4.4

  • Under Condition 4 with ν(i) uniform over each player’s simplex, Algorithm 2 satisfies the formal version of Theorem 4.4.The theorem explicitly assumes that player 1 runs Algorithm 2 and that all players, including the comparator, satisfy the condition.Source: §I.2 · p. 38
  • Lipschitz continuity and Corollary M.7 are used to bound intermediate terms involving the common state distribution induced by earlier play.The proof applies these tools for t ≥ K + 1 and identifies a shared state distribution μ.Source: §I.2 · p. 39
  • The proof converts each qt into its normalized joint strategy using qt(h,a) divided by the total action mass at h.This construction is used to define the joint strategy induced by qt.Source: §I.2 · p. 40
  • A positivity condition on action mass yields a distance bound for two strategy profiles, supporting the proof’s occupancy-measure comparisons.Lemma I.6 assumes every history’s total action mass is at least c > 0.Source: §I.2 · p. 40
  • The cited expression includes the additive term (CQ + 2CLipsK2) |A|M+1.Source: §I.2 · p. 42
  • For comparator sequences, Algorithm 5 convergence and Lemma I.7 transfer variation in q to variation in π within the theorem’s bound.The proof defines a comparator joint strategy and invokes both convergence and variation control.Source: §I.2 · p. 42
  • When the comparator sequence lies in X, it corresponds to a product-form strategy profile and satisfies the feasibility requirement of Lemma L.7.For such comparator points, Dt(h,a, q̂t) = 0 for all h,a, so gt(q̂t) = 0 ≤ 0.Source: §I.2 · p. 43

T + (CQ + 2CLipsK2) |A|M+1

  • Lemma I.7 bounds the distance between occupancy measures induced by two strategy profiles, with its proof using a point-mass loss at a selected history.The proof sets L(h,a) = 1(h = h0) and identifies ρπ with dπ(h0).Source: T + (CQ + 2CLipsK2) |A|M+1 · p. 43

J.1 LRP-Regret and Subgame Perfect Equilibrium · J.2 RP-Regret and SPNE · K Finding Subgame Perfect Coarse Correlated Equilibrium in Repeated Games

The section establishes that sublinear local regret can imply approximate subgame-perfect equilibrium, while extending the analysis to RP-Regret and SPNE under conditions ensuring the required comparator structure. It also relates finite repeated-game equilibria to equilibria in infinitely repeated games through bounded-memory and variation conditions.

J.1 LRP-Regret and Subgame Perfect Equilibrium

  • Sublinear local regret for all players implies an approximate subgame-perfect equilibrium.Source: §J.1 · p. 44
  • For finite horizons, the analysis assumes each action has probability at least γ|A_i| under the players’ strategies.Source: §J.1 · p. 44
  • The argument extends player-specific local-regret bounds to every player and uses them to establish subgame perfection.Source: §J.1 · p. 44
  • Approximate equilibria across K epochs transfer to the infinitely repeated game when the matrix game satisfies the stated condition and has bounded memory M.Source: §J.1 · pp. 44–45
  • The transfer analysis is limited by strategy variation: the algorithm guarantees sublinear regret when P_T=o(T), while the game-setting case P_T=O(T) remains unresolved.Source: §J.1 · p. 44

J.2 RP-Regret and SPNE

  • For RP-Regret, sublinearity implies the existence of parameters p and q with p+q=1 and p<1, enabling the SPNE argument through Lemma 5.4.Source: §J.2 · p. 47

K.1 Computation of SPCCE … M.3 Contraction property with bounded memory of length M

This section develops guarantees and auxiliary lemmas for SPCCE computation, finite-memory approximation, Markov-game averaging, and projected-gradient updates. It establishes regret bounds, history-forgetting and mixing properties, and contraction-related control under bounded memory and time-varying constraints.

K.1 Computation of SPCCE

  • Algorithm 3 provides a regret upper bound for comparators satisfying Condition 4 and yields an approximate O(T)-robust SPCCE when all players use the algorithm.The construction samples a strategy uniformly from the first T0 iterations and repeats it periodically across the horizon.Source: §K.1 · pp. 47–48
  • Algorithm 3 guarantees V_t(h^k) ≤ V_t^{ˆπ(1),¯π^(−1)}(h^k) for any ˆπ(1) at any timestep; the same argument applies to each player i, replacing |A_1| with |A_i|.Source: §K.1 · pp. 48, 50

L Auxiliary Lemmas

  • Under Condition 3 for all agents and γ ≤ 1/(2(N+2)), finite histories have controlled approximation errors because agents progressively forget the past.The auxiliary bounds control conditional-probability changes across histories and decay with the memory length m.Source: L Auxiliary Lemmas · pp. 52, 53, 55

L.2 Lemma for Markov Game

  • With Condition 3 for every player, the induced Markov game has an expected time-average loss that exists and is independent of the initial distribution.Full-support policies make every available joint action occur with positive probability, rendering the induced Markov chain irreducible.Source: §L.2 · p. 59
  • The bounded-memory Markov-game lemma relates strategy-profile performance to finite-memory averages under γ ≤ 1/(2(N+2)), with history comparisons controlled by ratios involving γ^(M+1).The comparison uses histories sharing their most recent suffix of length M.Source: §L.2 · pp. 59–60

L.4 Projected Gradient Descent (PGD)

  • The appendix also records a projected-gradient-descent regret bound for arbitrary comparator sequences in a convex domain.The update projects onto the convex feasible set using the L2 norm.Source: §L.4 · p. 60

L.5 Projected Gradient Descent with Time-varying Constraints

  • A time-varying-constraint variant of projected gradient descent has a corresponding guarantee when every comparator satisfies the time-indexed constraints and the learning rate is appropriately selected.This result is stated for Algorithm 5 under constraints g_t(ˆx_t) ⪯ 0.Source: §L.5 · p. 62
  • Projected gradient descent bounds each iterate’s movement by ηG(k + 1) + ηG∥λ_t−1∥_2 under time-varying constraints.The proof additionally bounds the cumulative movement term C∑_{t=2}^T ∥x_t − x_t−1∥_∞.Source: §L.5 · pp. 62–63

M Auxiliary Lemmas for the Induced Markov Game

  • The auxiliary analysis assumes all agents have bounded memory M and studies the induced Markov game under that memory restriction.These assumptions support the subsequent mixing and contraction results.Source: M Auxiliary Lemmas for the Induced… · p. 64

M.1 Milder Constraint

  • Condition 5 with parameter 1 − γ follows from Condition 3 with parameter γ; when all players satisfy Condition 5, infinite-horizon Markov-game expected average loss approximates repeated-game expected loss at each timestep.Source: §M.1 · pp. 64–65

M.2 Fast Mixing

  • Every memory state can reach a common state h0 within log_2 |H_M| + 1 steps, yielding fast mixing for the induced Markov chain.The construction merges rooted trees while increasing maximum depth by at most one per episode, and the resulting chain bound applies for sufficiently large K.Source: §M.2 · pp. 66–67

M.3 Contraction property with bounded memory of length M

  • The induced Markov dynamics contract across initial distributions, so sufficiently long-run average state distributions converge and become independent of initialization.This contraction supports replacing later strategies in an infinitely repeated game with a periodic strategy sequence after a sufficiently large K.Source: §M.3 · pp. 68, 70
Loading 2606.06486v1…