Learning to Play Against Adaptive Opponents: Beyond External Regret in Repeated Games

Paper: 2606.06486 Authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang Categories: cs.LG, cs.AI, cs.GT

The Gap

Standard multi-agent learning measures performance using external regret — comparing against fixed alternative strategies. This fails catastrophically when opponents adapt based on your behavior history. Existing adaptive regret notions (swap regret, Φ-regret, internal regret) either restrict opponent behavior too severely or use comparators that ignore counterfactual reasoning: “what if I had played differently from the start?”

Prior work assumed opponents follow stationary distributions or move slowly. Real strategic agents remember, respond, and exploit patterns. The gap: no regret metric that (1) handles unrestricted adaptive opponents, (2) uses comparators that reason about alternate entire histories, and (3) still admits learnable algorithms.

Problem: External regret blind to adaptation
    |
    v
Assumption: Opponents can respond to full history
    |
    v
Method: RP-Regret compares realized vs best-hindsight policy sequences
    |
    +---> Challenge: Non-convex in strategy space
    |
    v
Evidence: Three algorithms (oracle, linearized, slow-opponent)
    |
    v
Conclusion: Sublinear regret achievable under memory/variation bounds
             All-player minimization -> cooperative equilibria

The Increment

One sentence: Before, learning agents ignored that opponents adapt to their history; now, a learnable regret metric captures this adaptation and provably converges to better equilibria when both sides use it.

Core Mechanism

RP-Regret asks: “If I could rewind time and commit to a different sequence of policies from the start, knowing opponents would respond accordingly, how much better could I do?” The comparator isn’t a single fixed strategy but a sequence of policies {\pi_t^*}, and the opponent’s response at each step depends on this alternate history.

The definition is inherently non-convex — you’re optimizing over policy sequences where each choice affects future opponent behavior. The paper tackles this three ways: (1) assume a black-box optimization oracle for the non-convex problem, (2) linearize the regret at each iteration into a convex surrogate (like FTL in online learning), (3) exploit slow opponent variation to make gradient-based minimization tractable.

All three algorithms require bounds: comparator policies can’t vary wildly between time steps (Lipschitz-like constraints), and opponent memory can’t be infinite (bounded recall). These aren’t artifacts of the proofs — they’re fundamental. Without variation bounds, the best-hindsight sequence could oscillate chaotically; without memory bounds, opponents could implement uncomputable strategies.

At each round t:
    Player observes history h_{t-1}
           |
           v
    Chooses policy pi_t
           |
           v
    Opponent responds with sigma_t (may depend on h_{t-1})
           |
           v
    Actions sampled -> utilities realized
           |
           v
    RP-Regret = max over alternate {pi'_1...pi'_T}
                [ sum_t u(pi'_t, sigma'_t) - sum_t u(pi_t, sigma_t) ]
                where sigma'_t = opponent's response to alternate history

Think of it like chess preparation. External regret asks: “Should I have played the Sicilian every game?” RP-Regret asks: “If I had committed to a different opening repertoire from move one, and my opponent adjusted their prep accordingly, would that path have scored better?” The key structural element: your counterfactual choices propagate forward, changing the opponent’s future responses. The linearized algorithm approximates this by assuming locally, the opponent’s response doesn’t change much — you can treat it as fixed for one step, solve a convex problem, then update. The oracle algorithm solves the full non-convex problem each time. The slow-opponent algorithm directly descends the non-convex objective when opponent strategies drift slowly enough that gradient noise doesn’t dominate.

Key Concepts

• Repeated Policy Regret: Classical regret compares your average loss to a single best fixed action. RP-Regret compares your accumulated utility across T rounds to the best sequence of T policies you could have committed to, where “best” accounts for how opponents would have responded differently had you played that sequence. It’s regret over entire trajectories, not single decisions. Concretely: you earned U across history H; the comparator asks “if I’d played policies {π₁**, π₂*, …, π_T*} and opponents responded to that alternate history, would I have earned more?” If yes, the gap is your regret.

• Memory and Variation Bounds: For RP-Regret to be learnable, two constraints appear necessary. Memory bound: opponent strategies at time t depend only on the last M steps of history, not all T steps. Variation bound: consecutive policies in your comparator sequence can’t differ too wildly (measured by some distance metric on policy space). Without memory bounds, opponents could encode uncomputable functions of infinite history. Without variation bounds, the best-hindsight sequence could be adversarially chosen to exploit the non-convexity — like a spline that interpolates through T arbitrary points. These bounds make the problem “approximately Markovian” and “locally smooth.”

• Linearized Surrogate: To avoid the non-convex RP-Regret objective, Algorithm 2 linearizes it each round. At iteration t, treat opponent responses as fixed (first-order approximation), solve a convex regret minimization problem, then step forward and relinearize. This is analogous to Follow-the-Leader in online convex optimization, but here the “loss function” changes because opponent behavior drifts. The linearization trades global optimality for computational tractability — you get a convex problem at each step but may not find the true best-hindsight sequence. The paper proves this still achieves sublinear regret under slow opponent variation.

Framework Shift

Before (external regret):           After (RP-Regret):

    You play: a_1, a_2, ..., a_T        You play: pi_1, pi_2, ..., pi_T
         |                                       |
         v                                       v
    Compare to fixed a*                  Opp responds: sigma_1(h_1), sigma_2(h_2),...
         |                                       |
         v                                       v
    Regret = max_a* [U(a*) - U(a)]       Compare to alternate {pi'_1,...,pi'_T}
                                                  |
    Opponent is "nature"                          v
    (oblivious or slow-varying)          Opp WOULD respond: sigma'_1(h'_1),...
                                                  |
                                                  v
                                         Regret = max_{pi'} [U(pi',sigma') - U(pi,sigma)]

                                         Opponent is strategic
                                         (responds to counterfactuals)

From passive baselines to counterfactual trajectories: the core shift is treating the opponent’s strategy as a function of your policy history, not an external sequence.

Expert Assessment

Problem choice: This is a real gap. Existing multi-agent RL theory either assumes non-adaptive opponents (stochastic bandits), slow adaptation (adversarial bandits), or uses regret notions that ignore counterfactual reasoning (external regret, swap regret on fixed distributions). Strategic opponents in real settings — poker bots, market makers, negotiating agents — absolutely exploit patterns. The motivation is sound.

Method maturity: The paper leans heavily on oracles and strong smoothness assumptions. Algorithm 1 punts the hard part to a black-box optimizer. Algorithm 2 (linearized) is more practical but requires Lipschitz-smooth opponent response mappings — a modeling assumption, not a guarantee. Algorithm 3 (slow opponents) is the most honest: it admits the problem is non-convex and says “if opponents move slowly, descent works.” The variation and memory bounds feel like the right conditions, but proving tightness of these bounds (are they minimal?) is left open. I’d like to see impossibility results: can you construct opponents that make RP-Regret unlearnable without these assumptions?

Experimental integrity: The Stag-Hunt experiment (Figure 1) is illustrative, not dispositive. It shows RP-Regret algorithms can converge to cooperative payoffs where external regret gets stuck at Nash. But the setting is toy (2x2 game, 1000 iterations), and there’s no ablation on memory length M or variation parameter L. The paper doesn’t test whether the theoretical rates (Õ(√T)) hold empirically, nor does it compare to recent adaptive regret algorithms like online mirror descent with expert tracking. The experiment serves as proof-of-concept, not validation. For a theory paper, that’s acceptable, but practitioners should be cautious extrapolating.

Writing quality: The definitions are dense. Section 3.1 introduces RP-Regret across two pages with heavy notation before giving intuition. Swapping order — motivate with Stag-Hunt first, then formalize — would help. The memory and variation bounds (Section 3.2) are scattered; consolidating them into a single “Learnability Conditions” section would clarify their role. Algorithm 2’s linearization step is buried in the proof sketch (Appendix C); promoting it to the main text as a diagram would make the method more accessible. The related work section is thorough but reads like a literature dump; framing it as “prior work solves X but not Y, we solve Y” would sharpen the contribution.

Verdict: Weak accept — Introduces a well-motivated regret notion and proves it learnable under reasonable conditions, but the algorithms rely on strong smoothness assumptions and the experiments are preliminary. The contribution is more conceptual (defining RP-Regret) than algorithmic (practical minimizers). A strong revision would tighten necessity results, add harder experimental domains, and surface the core ideas earlier.

Takeaways

For practitioners: If you’re training agents against adaptive opponents (trading bots, game AI, negotiation systems), measuring external regret is misleading. RP-Regret suggests you should track not just “did I beat a fixed baseline” but “if I’d committed to a different trajectory, accounting for opponent responses, would I be better off?” Concretely: log opponent behavior conditioned on your past actions, estimate their response model, then periodically solve for your best-hindsight sequence. Even if you can’t minimize RP-Regret exactly, the framework clarifies what “adaptation-aware” learning should optimize.

For researchers: The linearization trick (Algorithm 2) generalizes. Anytime you face a non-convex sequential objective where future costs depend on current actions, linearize around the current point, solve a convex surrogate for one step, then relinearize. This is essentially model-predictive control but for regret minimization. The memory bound M is the key knob: small M makes the problem tractable but limits opponent expressiveness; large M captures richer strategies but blows up computational cost. If you’re working on multi-agent learning, consider whether your regret definition respects counterfactual opponent behavior — if not, you’re ignoring strategic adaptation.

Transferable technique: The paper’s proof structure (Lemma 3.3) shows that bounding RP-Regret requires controlling *both the variation of your comparator sequence and the Lipschitz constant of opponent response functions. This “joint smoothness” requirement likely applies to any learning problem where the loss function is generated by an adaptive adversary. If you’re analyzing online learning with non-oblivious opponents, check whether your regret bound assumes one-sided smoothness (your actions vary slowly) or two-sided smoothness (opponent responses also vary smoothly). The latter is often necessary but rarely stated explicitly.