PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Strategizing Against No-Regret Learners: Pure When It Is Easy, Hard Even When Mixed

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis

arXiv:2610.36261v1cs.GT

TL;DR

The paper asks whether near-optimal steering of a known learner in a finite-horizon game can be computed efficiently. It proves hardness for general-sum games even when the optimizer may output mixed strategies, while in zero-sum games pure strategies retain guarantees against mixed play.

  • Problem

    A no-regret guarantee compares the learner with a fixed action in hindsight but does not settle whether an optimizer can efficiently choose a high-reward sequence that steers the learner.

    Source: §1 · p. 3, §3.3 · p. 8

  • Method

    The paper studies trajectory optimization against known deterministic learning rules, using a reduction for general-sum hardness and pure-sequence constructions for zero-sum guarantees.

    Source: §1.1 · p. 4, §2.2 · p. 6, §3.3 · p. 8

  • Results

    Unless P = NP, no polynomial-time optimizer can guarantee an o(T) loss from the pure-sequence benchmark for the stated general-sum game family, even with explicitly encoded mixed trajectories; in zero-sum games, pure play stays within the learner’s regret bound of the optimal mixed trajectory.

    Source: §1.1 · p. 4, §3.1 · p. 7

  • Takeaways & Limitations

    Mixed outputs do not remove the stated general-sum hardness, while pure play suffices for the zero-sum approximation guarantee.

    Source: §1.1 · p. 4, §3.1 · p. 7

    The hardness result is scoped to fixed deterministic learners satisfying the quantitative mean-based condition at the theorem’s required rate.

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

Abstract

from arXiv · show

We study the computational complexity of clairvoyant strategy optimization against a known online learner in finite-horizon repeated games. In general-sum games with bounded payoffs, unless $\mathsf{P}=\mathsf{NP}$, no polynomial-time optimizer can achieve a reward within $cT$ of the reward of the optimal pure-action sequence for an absolute constant $c>0$, even when allowed to output explicitly represented mixed strategies at every round. Our hardness result strengthens prior work along two complementary axes: it extends to a broader class of learning dynamics, including widely used mean-based algorithms, answering an open question of Assos, Dagan, and Rajaraman (2025) for learners beyond multiplicative weights; and it permits mixed outputs while retaining the weaker pure-sequence benchmark. Thus, neither mixed strategies nor algorithmic specificity removes the computational obstruction in general-sum games. In sharp contrast, zero-sum games exhibit the reverse phenomenon: deterministic pure actions suffice for efficiently recovering the leading surplus guarantees previously obtained through mixed play against Follow-the-Regularized-Leader (FTRL) opponents. Thus, the two regimes form a striking mirror image: mixed play cannot overcome general-sum hardness even against a pure benchmark, whereas pure play retains the full surplus guarantees of mixed strategies in zero-sum games.

1 Introduction

The paper asks whether an optimizer can efficiently steer a known learner over repeated rounds, where actions shape future responses. It shows that mixed actions do not remove general-sum hardness, while pure actions suffice for zero-sum guarantees.

1.2 Related work

  • The paper frames the contrast as mixed play failing to overcome general-sum hardness while pure play retains zero-sum guarantees.Table 1 compares the guarantees with prior work; its highlighted entries mark broader learner classes and stronger pure/mixed guarantees.Source: §1 · p. 3, §1.2 · p. 4

1.1 Our contributions

  • Unless P = NP, no polynomial-time optimizer can achieve a fixed per-round loss from the best pure sequence in general-sum games, even with mixed outputs.With bounded payoffs, the gap grows linearly with the horizon.Source: §1.1 · p. 3
  • Hardness extends beyond Hedge/MWU to fixed deterministic learners satisfying a quantitative mean-based condition, including Euclidean, Tsallis, and log-barrier regularization under specified learning rates.This addresses Assos, Dagan, and Rajaraman [ADR25]’s question about learners beyond multiplicative weights.Source: §1.1 · p. 3
  • In zero-sum games, a pure best response each round stays within the learner’s regret bound of the optimal mixed trajectory, and can be computed efficiently when learner responses are efficient.Against any no-regret learner, the average shortfall vanishes.Source: §1.1 · pp. 3–4
  • For separable FTRL learners, deterministic pure sequences recover passive and active surplus rates previously obtained through mixed play, up to rounding losses and under the respective theorem assumptions.Passive surplus scales as 1/η_T and active surplus as η_T T for a fixed game and regularizer.Source: §1.1 · p. 4
  • The hardness reduction extracts an independent set from cumulative optimizer action counts, including fractional counts, by grouping rounds into intervals of comparable setup counts.Alarm actions limit rewards from incompatible activations, converting the source gap into a linear reward gap.Source: §1.1 · p. 4

2 Preliminaries

The paper models offline planning over full action sequences against a known deterministic learner, distinguishing pure and mixed trajectory benchmarks from the learner’s fixed-action regret comparator. It considers general deterministic learners for hardness and separable FTRL for finer zero-sum surplus analysis.

2.1 Repeated-game model and benchmarks

  • The optimizer plans over a full finite-horizon trajectory against the learner’s induced responses; pure trajectories are included among mixed trajectories.The mixed supremum need not be attained for a general response rule, though it is a maximum for continuous response rules such as FTRL.Source: §2.1 · p. 5
  • A no-regret bound compares the learner with its best fixed action on the same payoff sequence, and does not generally control the optimizer’s trajectory benchmarks in general-sum games.In zero-sum games, the game value lets regret bound both trajectory benchmarks.Source: §2.1 · pp. 5–6

2.2 Learner models

  • For hardness, the learner need only be a fixed deterministic rule satisfying the quantitative mean-based condition at the theorem’s rate; no other structural restriction or regret assumption is imposed.The condition limits probability on an action whose cumulative score trails another sufficiently far.Source: §2.2 · p. 6
  • The basic zero-sum approximation uses only a regret guarantee, whereas recovering finer surplus gains requires analysis specialized to separable FTRL.The learner’s response balances cumulative payoff with regularization; the class includes Hedge/MWU, Euclidean, and Tsallis examples.Source: §2.2 · p. 6

3 General-sum hardness: mixed control does not help

The section proves that mixed optimizer actions do not remove general-sum hardness, using a gap Independent Set reduction and extraction from mixed trajectories. The reduction applies to fixed mean-based learner families under the stated rate condition.

3.1 Main result

  • Unless P = NP, no polynomial-time optimizer returning rational mixed trajectories achieves the theorem’s additive guarantee against the pure-sequence benchmark for the stated fixed mean-based learners.The learner family must satisfy γ_T T = o(T^(1−ζ)); the guarantee holds on every game in the constructed family at sufficiently large reduction horizons.Source: §3.1 · p. 7

3.3 The game: activate a vertex, then harvest it

  • Each graph vertex becomes an activation-and-harvesting choice; learner alarms constrain local and adjacent activations, while the optimizer earns reward only by harvesting.The construction has a rewarding learner action and local and edge alarms; setup and activation do not directly earn reward.Source: §3.3 · pp. 8–9

3.2 Source problem: Independent Set on co-partite graphs

  • Gap Independent Set on co-partite graphs supplies a constant separation: YES instances permit one compatible choice per clique, while NO instances permit choices from only a small fraction [DS05, Section 9].The reduction transfers this gap to rewards separated by Ω(T), despite constant losses and o(T) errors.Source: §3.3 · p. 8, §3.2 · p. 8

3.4 Completeness: harvesting an independent set

  • A pure trajectory processes independent-set vertices one at a time: activation makes b_v lead, then harvesting earns about k/2 per vertex, repeatable because no previously chosen vertex is adjacent.Independence keeps edge alarms below the current rewarding action during harvesting.Source: §3.4 · p. 9

3.5 Soundness: extracting an independent set from mixed play

  • For arbitrary mixed trajectories, near-leading rewards impose activation-count constraints; geometric setup intervals produce independent candidate sets, and extraction returns the largest one.The extraction rule uses cumulative optimizer counts, not learner behavior, and Proposition 2 gives its reward bound.Source: §3.5 · pp. 9–10

B. Incompatible bounds t′ ≥t

Geometric setup intervals keep extracted candidate sets independent despite changing cumulative counts. The reduction’s horizon and error bounds then transfer the Independent Set gap to a linear reward gap.

B. Incompatible bounds t′ ≥t

  • Within each geometric setup interval, a vertex’s persistent activation lower bound conflicts with the upper bound required for a later neighbor, so the extracted candidates are independent.The interval ratio is 3/2; the appendix identifies it as the largest ratio that keeps the bounds apart.Source: B. Incompatible bounds t′ ≥t · p. 11, Figure 1 · p. 11

3.6 Horizon choice and hardness transfer

  • The horizon and encoding are polynomial and the proposition error terms are o(T), transferring the Independent Set gap to a hardness constant c = 1/(24r).The reward bounds compare the pure benchmark with the extracted independent set and the mixed trajectory with its size.Source: §3.6 · p. 11

4 Zero-sum games: pure play keeps the full surplus

In zero-sum games, pure actions can match the leading guarantees of mixed play: a myopic best response is near-optimal under sublinear regret, and structured pure schedules recover passive and active surplus against separable FTRL. Terminal or prefix balancing lets those schedules approximate a target mixture while preserving the relevant surplus.

4 Zero-sum games: pure play keeps the full surplus

  • A pure myopic best response earns at least T Val(A) and at most RegretL(T) below any mixed trajectory’s reward.With sublinear external regret and efficient learner simulation, this approximates the optimal mixed trajectory within sublinear additive error.Source: §4 · pp. 11–12

4.1 The potential decomposition

  • The FTRL reward decomposition separates a terminal potential difference from nonnegative Bregman terms, while fixed max-min play earns passive surplus as the learner retains mass on suboptimal responses.The paper uses the discrete-update terms to obtain active surplus in addition to this passive component.Source: §4.1 · p. 12

4.2 Passive surplus survives terminal rounding

  • Terminally balanced deterministic pure play preserves the continuous-time passive surplus up to a rounding loss.The construction rounds target max-min action counts to integers summing to the horizon, then plays each action its assigned number of times; the surplus applies when suboptimal learner responses exist.Source: §4.2 · p. 13

4.3 Active surplus survives prefix balancing

  • Under the non-identification and FTRL conditions, a deterministic prefix-balanced pure trajectory combines an active update bonus with the terminal contribution.Prefix quotas keep learner scores near those under the target max-min strategy; distinct payoff differences between selected best responses provide the bonus.Source: §4.3 · pp. 13–15

5 Discussion

The discussion explains the general-sum and zero-sum contrast through cumulative action counts, then delineates the conditions on both results. It also identifies unresolved questions about proximal-regret learners and robustness to payoff perturbations.

5 Discussion

  • Cumulative counts let the general-sum reduction extract a combinatorial choice even from fractional play, while zero-sum pure schedules approximate target-mixture counts within one per action.In zero-sum games, the value and regret bound place both trajectory benchmarks within RegretL(T) of T Val(A).Source: §5 · p. 15
  • The hardness result is worst-case, with n,m≤T^β and γ_T T=o(T^(1−ζ)); positive guarantees require additional learner-simulation, regularizer, or active-surplus conditions.Active surplus specifically requires the regularity, step-size, and non-identification conditions of Theorem 3.Source: §5 · p. 15
  • Open questions include whether recursive Euclidean projected gradient descent permits efficient planning and how much payoff noise preserves the Ω(T) hardness gap.The smoothed-complexity discussion considers independent uniform perturbations and asks whether larger perturbations permit efficient approximation.Source: §5 · pp. 15–16

AI Disclosure

The authors report the development of the mathematical results and disclose generative-AI assistance with manuscript preparation.

AI Disclosure

  • The authors obtained the mathematical results in July 2026.An initial approximately 50-page proof used a (1, 2)-Max TSP reduction and an additional learner assumption; exploring alternative strong NP-hardness sources led to gap Independent Set.Source: AI Disclosure · p. 16
  • The current reduction uses gap Independent Set after the authors explored whether the earlier learner restriction came from the learning model or the source problem.The initial reduction from (1, 2)-Max TSP required an additional assumption on the mean-based learner.Source: AI Disclosure · p. 16
  • Claude and Codex assisted with language editing, organization, LaTeX typesetting, and notation, reference, and consistency checks.The authors take responsibility for the correctness, proofs, originality, and attribution.Source: AI Disclosure · p. 16

Proof roadmap

The proof roadmap links the gap Independent Set problem to a constructed game and two reward-bound arguments, then uses a polynomial horizon to complete the hardness reduction. It also outlines the zero-sum proofs and supplementary hardness results.

Proof roadmap

  • Completeness turns an independent set into a valuable pure schedule, while soundness extracts a large independent set from any valuable mixed trajectory despite fractional interleavings.Geometric setup intervals enforce independence, and the mean-based condition bounds reward by the extracted set size.Source: Proof roadmap · p. 20

A.1 Other output–benchmark combinations

  • The other pure/mixed output–benchmark combinations follow from Theorem 1 and the fact that every pure trajectory is also mixed.The corollary rules out the listed guarantees under Theorem 1’s assumptions unless P = NP.Source: §A.1 · p. 21

A.2 The source gap: specialization of Dinur and Safra

  • The source gap specializes Dinur and Safra’s gap-h-Clique-Independent-Set problem to h=2 and ε=1/128, yielding the usual gap Independent Set problem.The construction fixes r as a constant satisfying r≥256c.Source: §A.2 · p. 21

A.3 Proof of Proposition 1

  • The completeness schedule uses setup, vertex activation, and harvesting blocks; its setup suppresses rewarding actions, and harvesting collects reward from each selected vertex.The construction pads with the neutral action if needed, while the soundness argument uses local and edge alarms to constrain incompatible activations.Source: §A.3 · pp. 22–23

A.4 Proofs of Lemma 1 and Proposition 2

The proof extracts independent sets from cumulative optimizer counts and uses their size to bound harvesting reward, then transfers the bound through a polynomial-horizon reduction. The appendix extends the hardness argument to setwise mean-based learners, including separable FTRL under regularizer-specific conditions.

A.4 Proofs of Lemma 1 and Proposition 2

  • Reward is bounded by separating non-near-leading leakage, small-setup harvesting, and large-setup harvesting controlled by the largest extracted independent set.Non-near-leading vertices receive probability at most γ_T per round; small setup levels contribute at most 6N(γ_TT + 1).Source: §A.4 · pp. 24–26
  • At each sufficiently large setup level, near-leading vertices are captured in candidate sets whose union within a geometric interval is an independent set.The extraction returns the largest such set across intervals, using only the optimizer trajectory.Source: §A.4 · pp. 24–25

A.5 Horizon choice, error bounds, and proof of the main theorem

  • The polynomial-horizon reduction makes the reward-error terms sublinear, so a constant-factor optimizer guarantee would decide the NP-hard gap Independent Set promise problem.The proof chooses c = 1/(24r), where r depends only on the source gap.Source: §A.5 · pp. 26–27

B Setwise mean-based learners

  • Setwise mean-basedness bounds total probability on an inferior action set, and the reduction retains hardness when its score-gap and probability-error conditions hold.The setwise extension replaces the coordinatewise probability error in the reward bounds with ρ_T.Source: B Setwise mean-based learners · p. 27

B.1 What the reduction needs: setwise mean-based learners

The reduction needs a bound on the total probability assigned to inferior actions, not on how that probability is distributed among them. Separable FTRL supplies such a bound through regularizer derivative gaps, yielding learner-specific conditions under which the hardness transfer applies.

B.1 What the reduction needs: setwise mean-based learners

  • A (γ_T, ρ_T)-setwise mean-based learner assigns at most ρ_T total probability to an inferior set when an outside action exceeds every set member by the required score gap.The definition places no other restriction on dependence on ordered payoff history or fixed internal memory.Source: §B.1 · p. 27
  • Theorem 1’s hardness transfers to fixed deterministic setwise mean-based learner families when the score-gap and probability-error requirements hold.The same game family and absolute hardness constant apply; coordinatewise mean-basedness also yields a setwise guarantee by summing probability bounds.Source: §B.1 · p. 28

B.2 Setwise guarantees for separable FTRL

  • For separable FTRL, a sufficiently large regularizer-derivative gap forces the total mass on an inferior set below ρ.The proof transfers mass from a set coordinate to a higher-scoring action; a score gain exceeding the regularization cost contradicts optimality.Source: §B.2 · pp. 28–29
  • Negative entropy and Euclidean FTRL satisfy the derived rate condition when ζ < α, while negative Tsallis entropy has a condition depending on q and the action-count bound.Using the constructed family’s actual action count improves the Tsallis sufficient condition to (2 − q)ζ < α.Source: §B.2 · pp. 29–30
  • Log-barrier regularization also yields the setwise guarantee, but its sufficient learning-rate condition is more restrictive than those for negative entropy or Euclidean regularization.For the actual action count, the stated sufficient condition is 2ζ < α.Source: §B.2 · pp. 30–31

C.1 Proof of Proposition 5 and the offline construction

A pure myopic best response against the learner secures the game value each round. The learner’s regret then bounds every optimizer trajectory, yielding an efficient route to approximating the optimal mixed and pure trajectories.

C.1 Proof of Proposition 5 and the offline construction

  • The pure myopic best-response trajectory earns at least T Val(A), the game-value baseline, by choosing a best row against the learner’s response each round.The proposition defines the choice with ties broken by a fixed action order.Source: §C.1 · p. 31
  • The learner’s regret bounds the reward of every mixed optimizer trajectory, so the pure best-response guarantee yields the stated approximation to the mixed benchmark and hence to the pure benchmark.The proof compares both trajectories through the game value.Source: §C.1 · pp. 31–32
  • If learner responses can be simulated efficiently, the optimizer can construct the pure trajectory offline; approximate responses add at most the stated cumulative approximation loss.With entries of A in [−1, 1], choosing ε_t = 1/T gives total approximation loss at most one and polynomial-time simulation.Source: §C.1 · p. 32

C.2 Proofs for passive extraction

Terminally balanced rounding converts a target max-min strategy into a pure sequence while controlling its terminal score error. Because the passive guarantee depends only on that terminal score, every ordering of the rounded actions preserves it, with only a fixed support-size loss.

C.2 Proofs for passive extraction

  • For any target strategy and horizon, integer action counts can be chosen to sum to T while each count lies between the floor and ceiling of its target.The counts, and thus a sequence with those counts, can be computed in polynomial time.Source: §C.2 · p. 33
  • Every ordering of the rounded counts preserves the passive guarantee because only the terminal score enters the potential comparison.Rounding changes the terminal score by at most the support size; the potential is Lipschitz and the Bregman terms are nonnegative.Source: §C.2 · pp. 33–35
  • Terminal rounding transfers the previously established passive-surplus bounds to pure play with only a fixed support-size loss, and the resulting trajectory is polynomial-time constructible.Under the stated asymptotic conditions, the support-size loss can be absorbed into the inverse-rate surplus term.Source: §C.2 · p. 35

C.3 Proofs for active extraction

This section frames strategizing against learners by the optimizer’s knowledge, the fixed learner, and the reward benchmark, and addresses computational and control questions across game settings and time horizons. It proves pure-surplus guarantees from prefix-balanced trajectories against FTRL learners and describes implementation conditions and random-game estimates for applying the theorem.

C.3 Proofs for active extraction

  • For fixed game data and δ, Lemma 5’s control holds eventually whenever ηT→0; Proposition 6 assumes two distinct learner actions’ probabilities remain in [δ, 1−δ] throughout the update.Source: §C.3 · pp. 36, 39
  • The proof combines terminal-potential corrections and per-round active bonuses into linear terminal-count costs, yielding the theorem’s lower bound for randomized and deterministic pure sequences.The randomized construction uses mean-zero terminal discrepancies; cost-guided derandomization preserves prefix quotas while choosing a nondecreasing linear objective.Source: §C.3 · pp. 41–42
  • Under non-identification on the max-min support, pure active surplus is Ω_A,h(η_T T) for a fixed game and regularizer geometry when the stated horizon condition holds.The horizon condition ensures the rounding loss is at most half the active term.Source: §C.3 · p. 43

C.4 Polynomial-time construction and identification

  • For rational inputs, the pure sequence is computable in polynomial time by approximating the linear costs, with lower-bound loss at most |supp(x★)|ε.This guarantee is subject to polynomial-time evaluation of Q_h to the required precision.Source: §C.4 · p. 43

C.5 Random games

  • For random games, cited estimates provide non-identification and a payoff gap of at least 2/(n^2m^3) for every row-entry gap with probability at least 1−1/(nm), enabling application of the deterministic theorem on their intersection.The passage does not include the resulting random-game guarantee.Source: §C.5 · p. 44
  • For random games with independent uniform entries on [-1, 1], Corollary 5 gives a pure trajectory whose reward exceeds TVal(A) by an active-surplus term.The proof combines bounds on the active term and rounding loss; its stated horizon condition also yields a second reward bound.Source: §C.5 · p. 44

Static commitment and dynamic control

  • Repeated play adds a state-dependent trajectory objective: mean-based learners can permit linear improvement over Stackelberg, while no-swap-regret learners cap reward at that benchmark up to sublinear error [DSS19].The control formulation exposes the planning problem but does not provide a general efficient optimizer for the trajectory objective.Source: Static commitment and dynamic control · p. 45

Known dynamics and computational hardness

  • Prior hardness against fictitious play did not settle total-reward approximation for standard no-regret dynamics [ADD24]; Hedge/MWU hardness followed [ADR25], and Theorem 1 extends the barrier to mean-based learners and mixed outputs against a pure-trajectory benchmark.The extension requires handling fractional interleavings rather than schedules that choose one action each round.Source: Known dynamics and computational… · pp. 45–46

Unknown payoffs and local Stackelberg targets

  • Unknown-payoff interaction is distinct from known-game optimization: learning a Stackelberg strategy can require exponentially many rounds against mean-based learners, while local Stackelberg approximation relies on geometric assumptions and smoothed analysis [ADY25].The local-target results and interaction lower bounds concern different objectives from hardness of optimizing a trajectory with full knowledge.Source: Unknown payoffs and local Stackelberg… · p. 46

Regret guarantees and learner design

  • Efficient regret guarantees for a fixed learner do not settle whether an optimizer can efficiently plan against it: the entropy-based Bregman formulation includes MWU, whose optimizer still faces the approximation barrier [CDLW+26].The text leaves the sharper question of recursive Euclidean projected gradient descent to Appendix E.Source: Regret guarantees and learner design · p. 47

Zero-sum surplus and long-run objectives

  • In zero-sum games, terminal rounding preserves passive surplus and prefix balancing retains active surplus under stated conditions, complementing general-sum hardness [ADD24] [SV26].Finite-horizon approximation hardness does not automatically imply an infinite-horizon average-reward gap; that requires a fixed learning rule and a persistent gap.Source: Zero-sum surplus and long-run objectives · p. 47

E Open questions and future work

  • Open questions include local optimization of full trajectories and efficient steering against proximal-regret learners, including whether Euclidean projected gradient descent permits near-optimal steering or linear excess.Other directions ask whether hardness persists beyond a prescribed horizon and which payoff perturbations preserve the extraction argument or permit efficient approximation.Source: E Open questions and future work · pp. 47–48
Loading 2610.36261v1…