PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Control via Counterfactual Tracking

Yunzong Xu

arXiv:2607.13029v2math.OCcs.LGcs.SYeess.SYstat.ML

TL;DR

Online control guarantees have relied on structural assumptions about benchmark policies and stabilizability, leaving unclear which assumptions are necessary. Counterfactual tracking separates reference selection from correction, reducing control to switching-cost learning; under additional assumptions, the converse makes the reduction minimax-tight up to a system-dependent factor.

  • Problem

    Existing guarantees rely on shared policy parameterizations, common disturbance-decay rates, or stabilizability, leaving unclear which assumptions are necessary for online control.

    Source: §1.1 · p. 2

  • Method

    Counterfactual tracking has a learner select or average benchmark counterfactual trajectories as references and a corrective law steer the system toward them, pricing changes by recovery cost.

    Source: §1.2 · p. 2, §3.3 · p. 11

  • Results

    Under additional assumptions, online control and its induced switching problem have the same minimax regret up to a system-dependent factor.

    Source: §1.2 · p. 2, §8 · p. 25

  • Takeaways & Limitations

    The difficulty of online control is determined by benchmark counterfactual trajectories and the cost of correcting changes between them.

    Source: §1.2 · p. 2

    The minimax converse covers convex globally Lipschitz costs and benchmarks that ignore previously revealed cost functions; its recovery factor may also be loose.

    Source: §8 · p. 25

Abstract

from arXiv · show

We study online control of a known linear dynamical system with adversarial costs and bounded disturbances, measuring regret against a general class of benchmark policies. We introduce counterfactual tracking, which separates the challenge of learning from the challenge of controlling the system. An online learner builds a reference trajectory by selecting or averaging the trajectories that the benchmark policies would have generated under the realized costs and disturbances, and a corrective law steers the system toward that reference. Charging each change in the reference its recovery cost (the cost of steering the system onto the new reference) reduces the problem to online learning with switching costs. Conversely, under additional natural assumptions, we show that this reduction is tight: the two problems have the same minimax regret up to a system-dependent factor, uniformly over horizons and policy classes. The reduction gives sharp regret guarantees for policy classes beyond standard finite-memory parameterizations. For a class of $N$ possibly nonlinear or history-dependent policies, it achieves $O(\sqrt{T\log N})$ regret over $T$ rounds, provided their trajectories remain within a bounded distance of one another and recovery costs are bounded. For the full $\ell_1$ ball of disturbance-response controllers, it achieves $O(\sqrt{T\log T})$ regret, which is minimax optimal in $T$, without assuming a common decay rate for disturbance effects. The framework also improves the best known regret bounds for linear state-feedback policies.

1 Introduction

The paper asks what makes online control learnable across general policy classes and known linear systems, then separates reference selection from physical control through counterfactual tracking. It establishes a minimax connection to switching-cost learning and derives guarantees for finite policy classes, disturbance-response balls, and linear state-feedback policies.

1.1 Motivation and research question

  • Existing guarantees impose shared linear parameterizations, common disturbance-decay rates, or stabilizability, while the paper seeks a characterization for given systems and policy classes.Conserved state components in load-balancing models illustrate why stabilizability can be unnecessary for low regret.Source: §1.1 · p. 2

1.2.2 Minimax tightness of the reduction

  • The converse makes online-control learnability equivalent to learnability in the induced switching problem, up to a system-dependent factor.It assumes convex globally Lipschitz costs, unconstrained inputs, and benchmark policies that do not use previously revealed costs.Source: §1.2 · p. 2, §1.2.2 · p. 3

1.2.1 Counterfactual tracking: the algorithmic reduction

  • Counterfactual tracking lets a base learner select or average benchmark trajectories while a corrective law steers the physical state toward the changing reference.Reference changes are priced by the recovery cost of correcting their trajectory gaps.Source: §1.2 · p. 2, §1.2.1 · pp. 2–3

1.2.3 Application I: learning general policy classes

  • For N possibly nonlinear or history-dependent policies with bounded trajectory gaps and recovery costs, regret is O(√T log N), worst-case optimal in T and N.Under strong convexity, regret improves to O(log N), independent of the horizon.Source: §1.2.3 · pp. 3–4

1.2.4 Application II: learning bounded disturbance responses

  • For a fixed-radius full ℓ1 ball of disturbance responses, regret is O(√T log T), minimax optimal in T without a common decay-rate assumption.The logarithmic factor reflects learning responses across disturbance ages; the learner stores O(T) coefficients and solves a convex program each round.Source: §1.2.4 · p. 4

1.2.5 Further consequences for linear state-feedback policies

  • For linear state-feedback policies with a common decay margin γ, convex-cost regret is O(γ^-1√dxT), with sharp dependence on T and γ.Under strong convexity, a finite cover of feedback gains gives O(dxdu log T) regret, though this algorithm need not be computationally efficient.Source: §1.2.5 · p. 4

1.3 Relation to prior work

  • The minimax equivalence provides a necessary-and-sufficient learnability characterization for general policy classes under the paper’s assumptions.The response-ball guarantee also differs from earlier long-memory bounds by requiring no decay information and allowing any feasible baseline.Source: §1.3 · pp. 6–7

2 Problem setup

The setup studies online control of a known linear system, where decisions affect both current costs and future states, against policies evaluated on the same realized costs and disturbances. The benchmark class is unrestricted in parameterization and stability, while quantitative cost guarantees rely on stated trajectory-region conditions.

2.2 Benchmark policies and regret

  • Regret compares the algorithm’s cumulative cost with the lowest cumulative cost of a benchmark policy on its counterfactual trajectory.The benchmark needs no parametric or stability restriction; algorithms need only simulate the policies’ counterfactual trajectories.Source: §2 · p. 7, §2.2 · p. 8

2 Problem setup

  • The algorithm chooses inputs before observing each round’s cost or disturbance, then incurs the cost and observes the full cost and next state.Environments may react to past inputs, but not to the current round’s random choice; the upper bounds cover adaptive environments and lower bounds use oblivious ones.Source: §2 · pp. 7–8

2.1 State–input geometry and cost classes

  • Lipschitz costs bound extra cost by state–input deviation, while strong-convexity results assume both conditions only on regions visited by relevant trajectories.The two conditions cannot both hold globally on all Euclidean space.Source: §2.1 · p. 8

3 Counterfactual tracking: the algorithmic reduction

Counterfactual tracking converts online control into online learning with switching costs by having a learner choose references and a corrective law track them. The reduction prices reference changes by their recovery cost, allowing the learner’s regret guarantee to transfer to control.

3.1 The algorithm

  • The base learner selects or averages counterfactual policies’ trajectories as a reference, and the control algorithm adds a correction based on tracking error.A distribution over policies is allowed, including distributions that put weight outside the benchmark class.Source: §3.1 · p. 9

3.2 Why switches matter: the tracking-error identity

  • The tracking error follows the system dynamics, driven by changes in the learner’s decision rather than by the common disturbance.A single corrective feedback law can remove discrepancies after switches; if there are no switches, the error remains zero and control regret equals base-learner regret.Source: §3.2 · p. 10

3.3 Pricing a switch: recovery norms

  • A switch discrepancy is priced by the total state–input deviation it causes under the corrective law when no later switch occurs.The prices add across switches in the physical run because the recovery norm satisfies a one-step recovery inequality and the triangle inequality.Source: §3.3 · p. 11

3.4 The reduction theorem

  • The reduction theorem transfers base-learner regret to control regret by charging recovery-weighted movement between decisions.The theorem also permits general loss choices, including an averaged loss with a Jensen gain.Source: §3.4 · p. 12
  • The reduction accepts different base learners for finite classes, the ℓ1 response ball, and approximating parameter sets for truncated disturbance–action control or spectral filters.Approximation error is charged when the available decision set only approximates the benchmark class.Source: §3.4 · p. 13

4 The minimax converse

The converse shows that, under additional assumptions, online control and switching have minimax regrets equivalent up to a system-dependent factor. It prices switches by their least recovery cost over the remaining horizon and defines a horizon-independent recovery norm on the reachable subspace.

4.1 Remaining-horizon recovery

  • A switch discrepancy’s least separate price is the minimum recovery cost over the rounds remaining after the switch, with no terminal constraint.Any causal correction scheme with additive switch prices must charge at least this amount for a single discrepancy.Source: §4.1 · pp. 13–14

4.2 Minimax equivalence

  • Under the theorem’s assumptions, minimax regret for control and switching differs by at most a factor depending only on the system and norm, uniformly over horizons and policy classes.The assumptions include unconstrained inputs, globally Lipschitz convex costs, and a nonempty loss-independent policy class.Source: §4 · p. 13, §4.2 · p. 15

4.3 Infinite-horizon recovery

  • The infinite-horizon recovery norm is minimal among time-independent recovery prices and is finite on the reachable subspace even when the full system is not stabilizable.Extended to the full state space, it is finite if and only if the system is stabilizable; the paper gives a non-stabilizable example with sublinear regret.Source: §4.3 · p. 16

5 Application I: learning general policy classes

Counterfactual tracking extends learning to policy classes whose members need not share a parameterization by using weighted averages of their counterfactual trajectories. The section establishes worst-case-optimal finite-class regret, a horizon-independent bound under strong convexity, and prior-based bounds for infinite classes.

5.1 Finite-class aggregation

  • O(min{T, √T log N}) regret is worst-case optimal in T and N for finite policy classes.The lower bound holds for a class of N open-loop policies on a fixed scalar system.Source: §5 · p. 17, §5.1 · p. 18

5 Application I: learning general policy classes

  • Weighted averages of counterfactual trajectories let the learner combine policies designed by different methods without a shared parameterization.The finite-class analysis assumes convex, L-Lipschitz costs on the counterfactual hull and on segments from actual points to references.Source: §5 · p. 17

5.2 Strong convexity pays for learning and recovery

  • O(log N) regret follows under strong convexity and bounded recovery distortion, without requiring a diameter bound.The Jensen gain from averaging cancels the learning and switching terms; strong convexity and Lipschitzness also bound the policy-point diameter.Source: §5 · p. 17, §5.2 · pp. 18–19

5.3 Infinite policy classes

  • For infinite policy classes, a prior replaces log N with KL(ρ∥ν) when comparing against a distribution ρ.With a nonatomic prior, a single policy has infinite relative entropy, so comparison uses a distribution concentrated near that policy, adding an approximation term.Source: §5.3 · p. 19

6 Application II: learning bounded disturbance responses

The section treats bounded disturbance responses as a learnable benchmark class without requiring a shared decay rate or bounded policy memory. Counterfactual tracking and a mirror-descent learner yield a dimension- and decay-rate-independent bound for the full response ball, while lower bounds show the logarithmic price of unrestricted disturbance ages is unavoidable.

6 Application II: learning bounded disturbance responses

  • A bound on total response magnitude defines a learnable class without prescribing disturbance-effect decay or limiting internal policy memory.The class is formed around any fixed feasible baseline, and the system need not be stabilizable.Source: §6 · p. 19, §6.2 · p. 20

6.1 Disturbance responses as decisions

  • A disturbance-response sequence specifies each disturbance’s later state and input effects, and SLS feasibility constraints make its reference trajectory obey the system dynamics.The first coefficient and the recurrence across later coefficients encode feasibility; contributions from separate disturbances add.Source: §6.1 · pp. 19–20, Figure 2 · p. 20

6.2 The full ℓ1 response ball and its learner

  • The full-response-ball bound depends on the system through M_V and on the class through R, with no explicit dependence on state or input dimension or a decay rate.The learner stores O(T) coefficient blocks and solves a convex problem whose size grows with T.Source: §6.2 · p. 21

Both bounds hold already against the policies

6.3 The statistical price of unrestricted disturbance ages

  • A one-step-recovering scalar system already incurs a minimax-optimal logarithmic price for learning responses over unrestricted disturbance ages.The lower bound persists for strongly convex costs; the logarithm is attributed to the response class, not slow recovery.Source: §6.3 · pp. 21–22, Both bounds hold already against the… · p. 22

7 Further consequences for linear state-feedback policies

For linear state-feedback benchmarks, the paper derives regret guarantees from their shared response decay and finite-dimensional gain structure, then describes cheaper implementations with additional assumptions.

7 Further consequences for linear state-feedback policies

  • Common disturbance-response decay removes the √log T factor for convex costs, while the finite-dimensional gain class yields logarithmic regret under strong convexity.Truncated DAC and spectral filters reduce computation in the stated settings.Source: §7 · p. 22

7.1 Regret for convex costs through age-weighted responses

  • The weighted ball Cκ,γ,H contains the length-H prefix of every response from Kκ; mirror descent over it gives a regret bound for convex, globally L-Lipschitz costs with a fixed recovery pair.For quadratic costs, a gradient bound on the visited region adds a factor γ^-1; that region has radius of order W√dx/γ, explaining Table 2’s γ^-2.Source: §7.1 · p. 23

7.2 Regret for strongly convex costs through a finite cover

  • A finite cover of the gains supports logarithmic regret for strongly convex costs, with the decay margin entering through the cost Lipschitz constant.The cover approximates full-horizon trajectories; its size is bounded using the finite-dimensional gain class, but efficient algorithms without an additional decay factor remain open.Source: §7.2 · pp. 23–24

7.3 Cheaper implementations: DAC and spectral filters

  • The response learner stores a coefficient for every disturbance age, and the finite gain cover can be large; DAC and spectral filters reduce computation under additional assumptions.The comparison assumes a trajectory-ball gradient bound and fixed κ and dimensions; prior rows retain their published normalizations.Source: §7.3 · p. 24, Table 2 · p. 24

7.3.1 Truncated disturbance–action control

  • Truncated DAC learns a response prefix of length H and lets a stabilizing baseline handle older disturbances, retaining the decay dependence while taking O(H) operations per round.The response itself is not truncated: older disturbances continue to act through the baseline state feedback.Source: §7.3.1 · p. 25

7.3.2 Spectral filters

  • Spectral filters replace age-specific coefficients with a low-dimensional temporal-pattern representation, taking O(h log^2(eT)) amortized operations per round for h = polylog(T/γ) filters.This implementation assumes real nonnegative closed-loop eigenvalues and well-conditioned eigenvectors.Source: §7.3.2 · p. 25

8 Conclusion and open directions

The conclusion characterizes counterfactual tracking as a reduction to online learning with switching costs and identifies limits to its minimax equivalence, model scope, and computational efficiency.

Conclusion

  • Counterfactual tracking reduces online control to online learning with switching costs, and under convex globally Lipschitz costs its minimax converse loses at most a system-dependent factor.The reduction itself needs Lipschitzness only on visited regions, allowing quadratic and strongly convex costs in the fast-rate results.Source: §8 · p. 25

Conclusion and open directions

  • The minimax equivalence is established only for convex globally Lipschitz costs and benchmarks that ignore past costs; extending it to other costs remains open.Its recovery factor may be loose because it charges switches separately and uses a worst-direction recovery constant.Source: §8 · p. 25
  • The reduction relies on known dynamics, linearity for feasible averaged trajectories, and unconstrained inputs for correcting errors in the reachable subspace.Unknown or nonlinear dynamics, partial observation, and hard constraints each require a replacement for one of these steps.Source: §8 · pp. 25–26
  • Efficient compression of the full response learner and efficient strongly convex guarantees without an extra decay factor remain open; cheaper implementations require additional assumptions.Approximate evaluation and projection also need analysis together with tracking error.Source: §8 · p. 26

Statement on AI use

The author reports that ChatGPT and Claude assisted with proof details, extensions, theoretical analysis, and writing, while the author remained responsible for the results and presentation.

Statement on AI use

  • ChatGPT helped complete proof details, identify extensions, and sharpen the analysis; the author wrote the paper with assistance from ChatGPT and Claude and takes sole responsibility for its results and presentation.The author says they conceived the main ideas, posed most research questions, and guided proofs.Source: Statement on AI use · p. 26

Guide to the appendices

The appendices establish reachability and tracking-error bounds, then give mirror descent as a base learner whose movement contributes to switching cost.

A.1 Reachable differences and the telescoping bound

  • The tracking-error recursion yields a telescoping bound by summing recovery costs and discrepancy terms, then discarding the nonnegative terminal recovery term.The appendix relates the trajectory norm to recovery and uses the recovery-pair condition.Source: §A.1 · p. 29
  • Differences between feasible trajectories lie in reachable directions because disturbances cancel in their next-state difference; this also holds for averages of references.The actual trajectory's difference from a feasible reference is likewise in the reachable subspace.Source: §A.1 · p. 29

A.2 Mirror descent as a base learner

  • Mirror descent can serve as the base learner when the reference set and losses are convex; its guarantee combines the usual mirror-descent terms with switching cost and Jensen gain.The update's movement controls both the learner's regret and its switching cost.Source: §A.2 · p. 30

A.3 Representation error and initial tracking error

This appendix extends tracking guarantees to imperfect references and initial offsets, then develops recovery prices used in the reduction and its converse.

A.3 Representation error and initial tracking error

  • Approximate policy representations and references starting away from x_ini are allowed, with representation discrepancy and initial tracking error included in the tracking comparison.The proof adds V(e1) to the tracking bound before comparing with the target policy.Source: §A.3 · pp. 31–32

B Proofs for the minimax converse and recovery norms

B.1 Controllability on the reachable subspace

  • Controllability on the reachable subspace makes recovery values finite, with V⋆ bounded above and below by multiples of the Euclidean norm on R.Source: §B.1 · p. 32

B.2 Remaining-horizon recovery

  • Remaining-horizon recovery values are finite continuous norms on R, and minimizing corrective laws exist for them.Source: §B.2 · p. 33
  • Any causal correction scheme satisfying the stated uniform bound must charge each discrepancy at least its remaining-horizon recovery value.Source: §B.2 · p. 33
  • The minimizing remaining-horizon corrective law yields a tracking bound by telescoping the remaining-horizon values.Source: §B.2 · pp. 33–34

B.3 Minimax equivalence

The appendix proves the minimax comparison and develops recovery prices and constructions, including for conserved and unreachable state components.

B.3 Minimax equivalence

  • The minimax comparison couples control and switching plays pathwise; shared next states make switching discrepancies zero, reducing that case to ordinary online learning.The comparison is stated for a fixed norm, and changing state/input weights can change recovery costs and the comparison factor.Source: §B.3 · pp. 34–36

B.4 Infinite-horizon recovery

  • Remaining-horizon values increase pointwise to V⋆, a finite continuous norm on R whose minimizing corrective law forms a recovery pair.Source: §B.4 · p. 37

B.5 Minimality of the infinite-horizon price

  • V⋆ is the pointwise smallest time-independent, horizon-uniform separable switch charge among the stated causal correction schemes.Source: §B.5 · p. 37

B.6 Stable linear corrective laws

  • A stable linear corrective law on R induces a recovery norm and recovery pair; finite-horizon MPC also provides computable recovery norms converging to V⋆ from above.The MPC construction trades computational effort against tightness of the recovery norm.Source: §B.6 · p. 38, §B.8 · p. 39

B.7 Recovery outside the reachable subspace

  • Extending recovery cost beyond R is finite exactly when the uncontrollable quotient dynamics are stable; otherwise some initial quotient state has infinite recovery cost.Source: §B.7 · p. 39

B.8 Recovery norms from model predictive control

  • MPC recovery values are norms and recovery pairs, and decrease to V⋆ from above; polyhedral formulations are linear programs and Euclidean or ellipsoidal ones are second-order cone programs.Source: §B.8 · pp. 39–40

B.9 The conserved network

  • In the connected conserved network, inputs preserve total load but can drive deviations in 1⊥ to zero, separating redistributable error from the conserved component.Source: §B.9 · p. 40

C Proofs for general policy classes

C.1 Finite-class aggregation

This section develops counterfactual tracking and aggregation for finite and measurable policy classes, including conditions for tracking policy averages and controlling regret through switching-cost bounds and, under strong convexity, Jensen gains. It also treats finite covers for stable state-feedback gains, weighted disturbance-response classes, and settings where localized distributions, known trajectory regions, or zero-scale conventions matter.

C.1 Finite-class aggregation

  • O(L√TDDV log N) regret to the best policy follows for finite classes when known diameter bounds satisfy the stated aggregation conditions.The time-varying-diameter theorem tunes exponential weights using a deterministic bound known before play; a full-support prior also permits comparison with any distribution under an entropy budget.Source: §C.1 · pp. 41–42

C.2 The variance form of exponential weights

  • With ηrt ≤ 1/2, the variance form bounds exponential-weights movement by a covariance and learning regret by a variance for every comparison distribution.The lemma applies to counterfactual tracking initialized from a full-support prior.Source: §C.2 · p. 43

C.3 Absorption by the Jensen gain

  • Under strong convexity, the Jensen gain can absorb positive variance terms at a sufficiently small learning rate, and the optimal recovery cost gives the smallest trajectory norm and distortion.The class-independent learning-rate choice is justified by bounding pairwise distances by 4L/µ and the loss range by 4L²/µ.Source: §C.3 · p. 44

C.4 Infinite policy classes

  • For measurable policy classes, exponential weights compares against any ρ ≪ ν of finite relative entropy, with relative entropy replacing log N; under strong convexity it also gives horizon-independent aggregation.The strongly convex guarantee uses η = c0µ/(L²α) for a sufficiently small universal c0 and an almost-everywhere pairwise distortion bound.Source: §C.4 · pp. 44–46
  • For a nonatomic prior, comparison with a single policy requires a localized distribution and an approximation-error bound; exact implementation also requires Gibbs normalizers and trajectory integrals.Sampling or variational approximations require separate error analysis.Source: §C.4 · p. 45

C.5 A trajectory region known before play

  • A known linear corrective gain can make the trajectory region for the run-dependent Lipschitz segments known before play.The passage poses this question and begins the corresponding setup.Source: §C.5 · p. 47
  • If counterfactual paths start at the actual initial state and stay within Dref, tracking policy averages keeps all actual-reference segments inside a known ball of radius Dtr.A gradient bound on that ball supplies the Lipschitz condition, while strong convexity is needed only on the counterfactual hull; the sufficient ball may exceed the region actually visited.Source: §C.5 · p. 47

C.6 A finite cover of stable state-feedback gains

  • A finite operator-norm cover of stable state-feedback gains yields a regret bound whose implied constant is independent of state and input dimensions, horizon, and decay margin at fixed scales.The result assumes strong convexity on the counterfactual hull, Lipschitz costs on that hull and the actual-reference segments, and a known distortion bound; its finite-horizon logarithmic factor is O(log T) at fixed scales.Source: §C.6 · pp. 48–49

D Proofs for disturbance responses and linear state feedback

  • When the loss, disturbance, response, or local-region scale vanishes, holding a feasible reference fixed gives zero regret; a zero spectral coefficient radius uses the representation baseline.Source: D Proofs for disturbance responses and… · p. 50

D.1 Response learning: feasibility and regret

  • Weighted projected subgradient descent with counterfactual tracking bounds regret against every response in a full-horizon class under convex globally Lipschitz costs and a fixed recovery pair.The bound combines learner regret with recovery costs of updates; a tuned step size is also provided, and if sensitivity is zero for every allowed sequence, fixing any feasible response gives zero regret.Source: §D.1 · pp. 51–52

D.2 The full ℓ1 response ball

This section studies learning the full ℓ1 ball of disturbance responses around a baseline, with regret guaranteed via near-ℓ1 mirror descent and a recovery pair. It characterizes the ball’s breadth and limits: no common finite-memory cutoff, but bounded total response constrains its scope.

D.2 The full ℓ1 response ball

  • Every zero-initialized finite-dimensional internally stabilizing linear policy has an absolutely summable feasible response, and rational feasible responses admit finite-dimensional internally stabilizing SLS realizations.With an absolutely summable baseline, such policies lie in a response ball of some finite radius.Source: §D.2 · p. 53
  • Nonrational responses need no realization, and the regret theorem requires neither internal stability nor a finite-memory approximation.The theorem uses causal convolution and affine feasibility relations.Source: §D.2 · p. 53
  • Peak-gain-bounded benchmark responses fit within a response ball of radius mb, yielding the full-ball regret bound without equating the two norms.This comparison constrains benchmark classes, not the online-control algorithm’s peak gain.Source: §D.2 · p. 54
  • No fixed memory cutoff approximates the full ball uniformly: on a scalar system, response mass can lie entirely beyond any cutoff.The example uses a finite-memory policy whose closed loop is nilpotent.Source: §D.2 · p. 54
  • The ball bounds total response, not decay speed: bounded-mass responses can have arbitrarily slow tails, while stable state-feedback examples leave every fixed-radius ball.Individual stability alone therefore does not ensure the theorem’s bound applies to a class.Source: §D.2 · p. 54
  • A mixed norm with exponent just above one stays within a constant factor of the ℓ1 coefficient sum while making the regularizer strongly convex.The section uses this near-ℓ1 regularizer for response mirror descent.Source: §D.2 · p. 55
  • Theorem D.6 gives a regret guarantee for the full response ball using near-ℓ1 mirror descent under convex, globally L-Lipschitz costs and a recovery pair.The theorem fixes H = T − 1 and a baseline Φ0 in S∞.Source: §D.2 · p. 55

D.3 Quadratic regularizers lose a factor

This section examines limitations and guarantees for counterfactual tracking across response and feedback classes, including quadratic regularization on the full response ball, infinite-memory and truncated DAC, and spectral-filter responses. It also covers stable feedback, weighted-response computation, locally bounded gradients, and regret guarantees for spectral filters and infinite-memory DAC.

D.3 Quadratic regularizers lose a factor

  • Quadratic regularizers pay a factor of √H versus √log H for near-ℓ1 geometry on delayed policies, even on a one-step system.The proposition lower-bounds the standard Hilbert radius–dual-radius bound for every quadratic norm; it is not a regret lower bound for infinite-memory DAC, and does not cover general nonquadratic mirror descent.Source: §D.3 · pp. 56–57

D.4 Stable linear state feedback with convex costs

  • Stable-feedback analysis separates benchmark-policy decay from physical recovery; the optimal recovery norm has existence bound Oκ(LW√dxT/γ^3/2).The recovery norm is minimized by an optimal corrective law, whose computation may require an optimization oracle.Source: §D.4 · pp. 57–58

D.5 Computation for weighted responses

  • For basic weighted response balls, projected updates take O(H) arithmetic operations and one cost-gradient evaluation per round, after O(H) preprocessing at fixed dimensions.The count includes reference evaluation, weighted projection, and physical action under a known linear corrective gain; added constraints require separate projection analysis.Source: §D.5 · pp. 59–60

D.6 Response learning with locally bounded gradients

  • Under the stated local-gradient and reference-radius conditions, the learner keeps the realized trajectory within the 2D0 ball, with D0=Oκ(W√dx/γ) for the stable-feedback response class.The construction uses a stable corrective gain and projected descent for long horizons, and holds a feasible response fixed when T<Pcor.Source: §D.6 · pp. 60–61

D.7 Comparison with infinite-memory DAC

  • In the published calculation, the memory term contributes only the final γ^-1/2 factor, while the full κ^17 power is already in the static scale; this compares stated bounds, not a general online-convex-optimization lower bound.Source: §D.7 · p. 62
  • Counterfactual tracking exposes the switching cost and corrective law as separate objects, unlike infinite-memory analysis, which absorbs correction into global Lipschitz and effective-memory quantities.Source: §D.7 · p. 62

D.8 Truncated DAC

  • Truncated DAC learns the first H disturbance ages, completes the response with a stabilizing gain, and adds a terminal term to the weighted norm to control the unlearned continuation.The completion is an affine family of feasible responses, and the corrective input uses the same gain; Theorem D.11 applies counterfactual tracking with mirror descent.Source: §D.8 · p. 63
  • For stable state-feedback comparators, the truncated-DAC horizon can be H=min{T−1,Hε}, with Hε=eOκ(γ−1) chosen to make the cumulative approximation error at most ε.At fixed dimensions, reference evaluation, weighted projection, and the physical action take O(H) arithmetic operations per round after O(H) preprocessing.Source: §D.8 · p. 66
  • With locally bounded gradients, the truncated-DAC construction keeps the realized trajectory within radius 2D0, using a horizon Hloc=eOκ(γ−1).It assumes a nonempty stable state-feedback comparator class and costs with bounded gradients on the specified ball; the construction requires a known gain stabilizing the full state.Source: §D.8 · p. 67

D.9 Spectral filters: construction and statements

  • Spectral filters compress long disturbance responses for stable state-feedback comparators with real nonnegative closed-loop spectra, using a stable baseline gain to construct feasible references.The shared Hankel basis requires uniformly conditioned eigenbases, restricting the comparator class; the corrective law need not use the baseline gain.Source: §D.9 · p. 68
  • The spectral-filter learner applies counterfactual tracking with mirror descent and any recovery pair, separating the baseline that defines compressed references from the pair that corrects switches.Source: §D.9 · pp. 70–71
  • γ_cor^-1/2 is the linear corrective law’s corrective-margin factor, up to factors polynomial in κ0, κcor, and 1 + ∥B∥op.Allowing the corrective and filtering gains to differ preserves the same filtering complexity; the linear gain is a computable alternative to an oracle bound using V⋆ and ψ⋆.Source: §D.9 · p. 71
  • Fast online convolution reduces spectral-feature evaluation from O(hm) to O(h log^2(eT)) amortized arithmetic operations at fixed dimensions.The per-round count excludes a one-time eigendecomposition of the m × m Hankel matrix.Source: §D.9 · p. 72
  • Constraining filter references to the radius-D/2 ball leaves at most the other half for tracking error, keeping the actual trajectory within radius D.This provides a spectral-filter construction for costs whose gradients are bounded only on a radius-D ball, under the stated dimension and projection-oracle conditions.Source: §D.9 · pp. 72–73
  • m = eO(γ^-1) and h = polylog(T/γ) learned coefficient matrices suffice for a spectral-filter regret guarantee under convex globally L-Lipschitz costs.The result assumes a nonempty spectral policy class, T ≥ 10, and 0 < γ ≤ 2/3; Corollary D.16 gives more detailed logarithmic factors.Source: §D.9 · pp. 71, 73

D.10 Spectral filters: proofs

These sections prove regret guarantees for spectral filters and develop lower-bound tools for finite policy classes and disturbance-response controllers. They also establish lower bounds for the full disturbance-response ball under convex and strongly convex costs.

D.10 Spectral filters: proofs

  • The spectral-filter proofs add comparator representation error LCspTεm,h to the learner’s regret bound and verify that tracking keeps physical trajectories within radius D.For long horizons, the threshold makes tracking error at most D/2; for short horizons, holding Q1 fixed keeps the physical trajectory equal to its feasible reference.Source: §D.10 · pp. 73, 75

D.11 Spectral filters: computation

  • At fixed dimensions, spectral-filter tracking takes O(h log^2(eT)) amortized arithmetic operations per round, plus one cost-gradient evaluation and one coefficient projection.The bound excludes worst-round latency and memory; the convolution routine may use O(hT) additional storage, and filter and gain construction are offline.Source: §D.11 · pp. 75–76

E Proofs of the lower bounds

  • The lower-bound proofs handle randomized algorithms by averaging seedwise regret over finite-support environments, yielding a deterministic sequence attaining the bound in expectation.For quadratic constructions, they average whole regrets rather than separating potentially nonintegrable linear and quadratic terms.Source: E Proofs of the lower bounds · p. 76

E.1 The one-step system

  • For the one-step system with A = 0, the optimal recovery cost for initial discrepancy z is V⋆(z) = |z|.Applying zero input removes the discrepancy in one step at that cost, and every correction sequence pays at least |z| in its first stage.Source: §E.1 · p. 76

E.2 Finite classes

  • For every T, N, and L in the stated ranges, a fixed scalar system and class of N loss-independent policies admit an oblivious convex, globally L-Lipschitz cost sequence giving randomized causal algorithms a lower bound.The construction uses block-constant sign policies and fresh Rademacher cost signs; the displayed bound’s magnitude is not present in the supplied passages.Source: §E.2 · pp. 76–78

E.3 Shifted Rademacher sums

  • Shifted-sign packing combines separated Rademacher vectors with a bounded convolution norm to control correlation gains and comparator energy.The supplied lemma passages state these properties for shifted sign vectors and provide a vector θ measurable from the sign sequences, but omit the displayed quantitative bounds.Source: §E.3 · pp. 78–80
  • The shifted Rademacher argument selects one maximizing age per group to construct a measurable sparse comparator and prove the grouped lower-bound inequalities.The selection is set to zero off the event, while the event probability and logarithmic comparisons support averaging the bound.Source: §E.3 · pp. 80–81

E.4 The full response ball with convex costs

  • For convex costs, a delayed policy in a finite sign experiment supplies a comparator in the full response ball and a deterministic disturbance–cost sequence lower bound.The comparator has finite support and summed state and input response-coefficient deviations at most R.Source: §E.4 · p. 81

E.5 The full response ball with strongly convex costs

  • Every cost is globally µ-strongly convex; under G ≥ 4µ and W ≤ D/4, the comparator has expected cost at most −cGDWR, and finite-support averaging yields each randomized algorithm a deterministic sequence with the same lower bound.Source: §E.5 · p. 82

E.6 Stable linear state feedback with convex costs

The lower bounds show that stable state-feedback policies can remain difficult comparators under convex costs, while the strongly convex construction matches the tracking upper bound on its fixed quadratic system. The appendix also calculates an exact recovery cost and verifies the strongly convex rate on that instance.

E.6 Stable linear state feedback with convex costs

  • The two stable policies stay order W/γ apart for most of the horizon, and random linear costs let the better comparator gain order W/γ√T.The construction uses costs chosen from an oblivious distribution; the lower-bound conclusions also hold for a deterministic cost sequence in its support.Source: §E.6 · p. 83

E.7 Stable linear state feedback with strongly convex costs

  • The strongly convex lower-bound construction uses comparators with a common state trajectory, reducing regret to estimating their one-dimensional input-allocation parameter from sign observations.The parameterized policies differ only in how input is split between two interchangeable actuators.Source: This system has the explicit optimal… · pp. 84–85

This system has the explicit optimal recovery cost

  • For the two-input system, the minimum cost to correct state error e is 3/2 |e|, achieved in one step by splitting the input equally.The proof also establishes that no finite-cost correction sequence is cheaper.Source: This system has the explicit optimal… · p. 85

E.8 Matching the strongly convex state-feedback bounds

  • O(µW^2γ^-2 log T) tracking regret matches the strongly convex lower bound in T, W, and γ on the constructed quadratic system.The verification uses the explicit quadratic costs and gradients bounded on an enlarged ball; a gradient bound only on the comparator region would not suffice for a general cost class.Source: §E.8 · p. 88

F.1 The sequential-complexity bound

The comparison identifies where two general online-learning frameworks can be loose for control: sequential-complexity bounds can incur a large stability term, while Hilbert-space memory bounds have geometry and memory costs. Counterfactual tracking gives a minimax √T rate for two policies in the example and avoids the stated response-ball assumptions of the unbounded-memory control specialization.

F.1 The sequential-complexity bound

  • The sequential-complexity guarantee combines the complexity of counterfactual losses with a stability-gap term; finiteness of the former does not control the latter.For N policies with losses in [−C, C], sequential complexity is at most C√(2T log N).Source: §F.1 · p. 88
  • O(√T) counterfactual-tracking regret is minimax for two policies, while the sequential-complexity bound can be linear because its stability term is linear.On the example, the RERM changes policies every round; mini-batching still gives order b^1/3T^2/3 for fixed b > 0.Source: §F.1 · pp. 88–89

F.2 The unbounded-memory bound

  • Hilbert geometry cannot recover the entropy rate for finite classes: the memoryless simplex bound is at least order C√(NT), rather than the O(C√(T log N)) entropy rate.The passage states that no other choice of Hilbert norm improves this memoryless bound.Source: §F.2 · p. 89
  • The unbounded-memory framework’s bound grows with effective memory, which is infinite when the history retains every past decision at full weight.Its online-control specialization keeps effective memory finite by assuming a known strongly stable baseline and geometrically decaying DAC coefficients; the response-ball guarantee needs neither assumption.Source: §F.2 · p. 90
Loading 2607.13029v2…