PaperlayerView exact revision on arXiv

Source-linked AI summary

Consistent Model Chasing Is Minimax Optimal: The Exact Value of Scalar Adversarial Adaptive Control under Large Parametric Uncertainty

Dimitar Ho

arXiv:2608.13651v1eess.SYcs.LGmath.OC

TL;DR

The paper studies worst-case peak regulation for a scalar system with an unknown constant pole and adversarial disturbances. It proves that midpoint consistent model chasing with certainty-equivalent deadbeat control is minimax optimal, achieving the exact value γ⋆(Δ) = 1 + Δ.

  • Problem

    The paper asks for the exact worst-case peak guarantee in scalar adaptive control with interval parametric uncertainty and adversarial disturbances.

  • Method

    It composes a deadbeat robust oracle with midpoint selection on the set-membership consistent interval, yielding passive consistent model chasing.

  • Results

    γ⋆(Δ) = 1 + Δ for every Δ>0, with the disturbance and unavoidable identification spike priced exactly.

  • Takeaways & Limitations

    For the peak objective, consistent model chasing is exactly minimax optimal, and the optimal law learns passively without exploration.

  • Takeaways & Limitations

    These results apply specifically to peak cost with full actuation, no input penalty, and an initially resting state.

Abstract

from arXiv · show

We solve exactly a fundamental problem of adaptive control against adversarial disturbances: regulate the scalar system $x_{t+1} = ax_t + u_t + w_t$, $x_0=0$, $\|w\|_\infty \le 1$, where the constant pole $a \in [-Δ, Δ]$ is unknown in sign and magnitude and $Δ$ is arbitrarily large. Elementary as the system looks, the least worst-case peak $\|x\|_\infty$ that a causal controller can guarantee against an adversarial pair $(a, w)$ (the value of this game) has, to our knowledge, never been determined for any adaptive control problem with parametric uncertainty of arbitrary size under this criterion; existing theory supplies stability certificates, gain bounds, and regret rates, not the value. That value is $γ^\star(Δ) = 1 + Δ$ for every $Δ>0$. The summand $1$ is the irreducible price of the disturbance, and $Δ$ the exact price of a single, unavoidable identification spike. The optimal policy is certainty-equivalent deadbeat control at the midpoint of the set-membership consistent interval, an instance of the robust oracle $\times$ consistent model chasing architecture. The architecture is forced, not merely sufficient: writing $θ_t := -u_t/x_t$ exhibits every causal controller as an oracle-selector composition, and optimality pins the selector to the midpoint at the critical histories. The standard tools, classical and modern, each fail quantifiably: probing is punished before it pays, commitment is fatal at sub-disturbance excitation once adaptation is necessary, optimism degenerates to tie-breaking or pays asymptotically at least twice the optimum, and regret certificates are blind to the worst-case peak in both directions. The optimal law contains no exploration mechanism, its learning purely passive. These results give the first exact optimality certificate for consistent model chasing as a design principle for adversarial adaptive control.

1 Introduction

The paper exactly solves the scalar adversarial adaptive-control game with arbitrarily large interval uncertainty, establishing minimax value γ*(Δ) = 1 + Δ. It shows that midpoint consistent-model chasing is not merely sufficient but forced and optimal, without exploration.

  • Problem setting: For Δ ≥ 1, no static linear controller has finite worst-case peak, making closed-loop adaptation necessary for boundedness.Information about the unknown pole is generated only when the state leaves the origin, coupling learning directly to exposure.
  • Main result: γ*(Δ) = 1 + Δ for every Δ > 0, decomposing the worst-case peak into disturbance cost 1 and one unavoidable identification spike costing Δ.The infimum and suprema are attained, yielding an exact minimax value rather than an order-of-growth or regret rate.
  • Optimal architecture: The optimal controller maintains the set-membership consistent interval and applies certainty-equivalent deadbeat control using its midpoint.This is an oracle–selector composition and instantiates the PixSel robust-control framework.
  • Structural optimality: The oracle–selector decomposition is a normal form for every causal controller, and minimax optimality forces its selector to choose the midpoint at critical histories.Writing θ_t := −u_t/x_t exposes every causal law as an oracle–selector composition, possibly with an inconsistent selector.
  • Why standard tools fail: The optimal policy uses no probing, persistency of excitation, optimism, or explicit identification phase; learning is entirely passive through consistency.Probing is amplified by the full uncertainty Δ before its information can be used, while irrevocable finite-time commitment pays at least double the optimal excess for Δ ≥ 1.

2 Problem formulation

The problem studies causal deterministic regulation of a scalar system with unknown a in [−Δ, Δ] and adversarial disturbances bounded by 1, evaluated by worst-case peak state. For Δ≥1, adaptation is necessary because no static linear gain can guarantee a finite peak, while the peak objective makes learning transients unforgiving.

  • Problem setup: The system has exactly measured state, scalar input, disturbance ||w||∞≤1, and unknown constant parameter a∈[−Δ, Δ], with Δ>0 known.Controllers are causal deterministic feedback laws, and the game value is γ⋆(Δ).
  • Problem setup: Disturbance-bound rescaling and input recentering are without loss, so the symmetric prior [−Δ, Δ] is a convention rather than an assumption.Rescaling by W reduces ||w||∞≤W to 1 and scales the value by W; ut becomes ut+cxt under recentering.
  • Adaptation requirement: For Δ≥1, no static linear law achieves a finite worst-case peak; controllers must use history to infer a.A single static gain works for every a∈[−Δ, Δ] only when Δ<1.
  • Implicit learning: Whenever xt≠0, each transition localizes a through observations, making information generation proportional to distance from the origin.The resulting data window has width 2/|xt|, coupling exploration and regulation.
  • Peak objective: The ℓ∞-peak criterion is designed for worst-case safety but is unforgiving to learning transients because a single bad step is never amortized.This criterion is the regime where average-cost and regret intuitions fail.

3 Main result: the exact value and the optimal architecture

The minimax peak is exactly 1 + Δ, attained by set-membership certainty-equivalent deadbeat control at the midpoint of the consistent parameter interval. Every causal controller has an oracle-selector form, and optimality forces a consistent midpoint selector at critical histories.

  • Exact value: 1 + Δ is the exact minimax peak, with 1 the unavoidable disturbance cost and Δ the cost of one unavoidable identification spike.The disturbance can move the state from 0 to ±1 without revealing a, after which one exposure of magnitude Δ cannot be prevented.
  • Optimal architecture: The optimal controller is certainty-equivalent deadbeat control using the midpoint of the set-membership interval as the parameter estimate.The controller maintains the closed interval of parameters consistent with observed data and cancels the estimated a x_t term.
  • Optimal architecture: The architecture attains the exact minimax peak, upgrading general polynomial-in-Δ boundedness and mistake guarantees to an exact value.The broader framework’s scalar example gives an O(Δ^2) mistake guarantee, whereas this result certifies the composition’s exact worst-case peak.
  • Selector normal form: Every causal controller factors through the deadbeat oracle and an implicit selector, so the design problem reduces to choosing that selector.For nonzero states, any causal action defines θ_t = −u_t/x_t, without requiring θ_t to be consistent with the parameter set.
  • Forced optimality: u_0 = 0 and u_1 = 0 are necessary for optimality, while the midpoint is uniquely optimal at maximal-exposure histories.A nonzero first action raises the lower bound; after w_0 = ±1, the prior remains intact and any deviation d costs exactly d in worst-case peak.

4 Lower bound: no causal controller beats 1 + ∆

Every causal controller suffers a worst-case peak of at least 1 + Δ. The lower bound arises from an information-free initial kick followed by an extreme parameter and aligned disturbance that reinforce the next control action.

  • Lower bound: 1 + Δ is unavoidable: every causal controller admits an admissible parameter and disturbance producing ||x||∞ ≥ 1 + Δ.Thus γ⋆(Δ) ≥ 1 + Δ.
  • Information-free kick: The initial state-independent input can be opposed by the disturbance, creating |x1| = |u0| + 1 ≥ 1 before any parameter information is available.Because x0 = 0, every a ∈ [−Δ, Δ] remains consistent with the observed data.
  • Aligned extreme parameter: Choosing the extreme parameter aligned with the fixed next input yields |a⋆x1 + u1| = Δ|x1| + |u1| ≥ Δ.The next move u1 is fixed once x1 is observed, while the parameter remains unrestricted after the first transition.
  • Final peak: A second disturbance aligned with the resulting drift forces |x2| = Δ|x1| + |u1| + 1 ≥ 1 + Δ.The construction then sets all later disturbances to zero.
  • Randomization: The lower bound uses only ±Δ and two disturbance moves, extends to randomized controllers, and remains valid in expectation against an oblivious disturbance sequence.The proof exploits moving the state off the origin before any information about a exists.

5 Upper bound: one identification spike is all the adversary gets

The midpoint controller keeps the adversarial peak at 1 + Δ by trading state exposure for information through a window invariant. The same exposure cap is necessary for every optimal controller, forcing midpoint selection at maximal exposure and yielding the exact value γ⋆(Δ) = 1 + Δ.

  • Upper bound: The window lemma gives |y| + μ ≤ r + 1 and μ|y| ≤ 2r, bounding exposure as state growth supplies information.Under the affine change of variables, interval length becomes μ_t+1 = s_t L_t+1, while r = g_t/2; this is the information–exposure tradeoff.
  • Upper bound: 1 + Δ is the guaranteed peak bound for every a ∈ [−Δ, Δ] and ||w||∞ ≤ 1, so γ⋆(Δ) ≤ 1 + Δ.The upper bound, combined with the lower bound, proves the exact game value.
  • Exactness: For every Δ > 0, the identification price is exactly linear: γ⋆(Δ) − γ⋆(0) = Δ.For an asymmetric prior of diameter D, the corresponding value is γ⋆ = 1 + D/2.
  • Necessary structure: The exposure cap g_t ≤ 2Δ is necessary for every optimal controller, not merely a property of the midpoint law.The converse follows from a deferred-commitment attack, making the cap a law of the problem.
  • Necessary structure: At maximal exposure g_t = 2Δ, the selector must equal mid(A_t); deviating by d incurs γ(K) ≥ 1 + Δ + d s_t.Equivalently, the action is u_t = −mid(A_t) x_t at those histories.

6 Why probing, commitment, and optimism are suboptimal

Under peak cost with full actuation and no input penalty, probing, explore-then-commit, and biased model selection are structurally suboptimal. The optimal strategy is passive at zero histories and selects the midpoint, while optimism either cannot rank models or incurs excessive cost.

  • Probing: Probing forfeits optimality by at least η∆ because the adversary amplifies the probe before its information becomes available.The bound is tight when the probe is superimposed on the optimal law.
  • Probing: Every optimal controller is passive at all-zero histories, since sub-disturbance probes can be canceled while the consistent set remains uncertain.This extends the initial-time penalty to later histories reachable with zero state and no information leakage.
  • Commitment: For ∆≥1, explore-then-commit is strictly suboptimal, and its worst-case peak is infinite when it never exceeds magnitude 1 at a zero state.The adversary can either starve identification through cancellation or monetize excitation after commitment.
  • Selection bias: The midpoint uniquely minimizes the one-step selection penalty, achieving the optimal 1 + ∆.Every causal controller has an implicit selector θ_t, so the result prices deviations from the midpoint directly.
  • Optimism: Endpoint selection creates an echo vulnerability whose cost is asymptotically at least four times the optimal 1+∆.The adversary can repeatedly reposition the surviving uncertainty against the selector’s standing bias.

7 Regret cannot certify safety

Regret-style guarantees and worst-case peak safety are incomparable: slowly growing regret can coexist with an infinite peak, while the peak-optimal law can incur linear regret. The reversal persists across cost accounting, showing that regret cannot certify adversarial safety.

  • Proposition 10: Regret and peak safety are incomparable in both directions.The section contrasts regret against a clairvoyant benchmark with the worst-case peak criterion.
  • Proposition 10: O(log T) or O(log log T) regret can coexist with an infinite worst-case peak under sparse probing.The probing schedules t_k = 2^k and t_k = 2^(2^k) yield the respective regret rates, while sup_{a,w} ||x||_∞ = ∞.
  • Proposition 10: Linear regret occurs for the peak-optimal law under the stealth attack a = 1, w = 0, which holds x_t = 1/(Δ+1) forever.The data windows contain the entire prior, so the law never adapts, while the clairvoyant pays only the one-time disturbance.
  • Robustness across costs: Under c_t = |x_t|, geometric probing has O(√T) regret while its worst-case peak remains infinite.The same incomparability persists under integrated state costs, rather than depending on the threshold-cost accounting.
  • Safety interpretation: Regret rankings reverse under re-accounting, whereas the peak criterion ranks the same policies unambiguously.Under mistake cost the comparison is O(1) versus Θ(#probes), while under state cost it is Θ(T); the peak criterion remains fixed.

8 Numerical verification

Numerical stress tests and exact reachability computations confirm γ⋆(Δ)=1+Δ with zero slack across broad parameter ranges. The experiments also verify the one-time identification spike and the exact linear penalty for deviating from the midpoint.

  • Numerical verification: No attack exceeded 1 + Δ; the theoretical worst case attained this value to machine precision for every tested Δ from 0.25 to 500.Tests included theoretical, aligned, randomized, random-restart, and lazy set-membership adversaries.
  • Numerical verification: γ⋆ = 1 + Δ matched the worst peak found by every attack family across more than three orders of magnitude of Δ.For Δ = 5, the trajectory reaches |x_2| = Δ + 1 = 6, then deadbeat control maintains |x_t| ≤ 1 forever.
  • Numerical verification: Exact reachability analysis confirmed the value with zero slack for Δ ranging from 0.125 to 5 · 10^4.The analysis tracked the scalar information state (s_t, L_t).
  • Numerical verification: A deviation d at the post-kick history produced worst-case peak 1 + Δ + d to 10^-9, confirming the exact linear midpoint penalty.This numerically matches the penalty stated in Remark 4 and the forced-midpoint result of Proposition 3(iii).

9 Discussion and outlook

The discussion identifies uncertainty diameter and pole constancy as the sources of the scalar game’s cost, while positioning robust oracle × consistent model chasing as a broader adversarial-control principle. It also outlines extensions to nonzero initial conditions and multivariate systems, plus implementation and selector-design lessons.

  • What the exact solution teaches: Uncertainty diameter, rather than nominal instability, governs the value; constancy makes the uncertainty identifiable and the optimal price payable.A known unstable pole is free, whereas a time-varying pole with the same uncertainty set has infinite value for ∆≥1.
  • Implementation caveat: Floating-point implementations should treat |xt| below a threshold as zero, because near-zero states can amplify rounding noise and create apparent bound violations.The stated artifacts disappear under exact rational arithmetic.
  • The multivariate frontier: In dimension n, preliminary analysis conjectures roughly one identification spike per direction, yielding minimax peak growth as ∆n up to n-dependent constants.The proposed generalization uses per-coordinate functional centering on consistent row sets.
  • Nonzero initial conditions: The nonzero-initial-state value is max(|x0|, 1 + ∆|x0|), attained by the midpoint law.Corollary 2 settles every initial condition at or above the disturbance level; outside the degenerate case, the midpoint is forced at the start.
  • The selector is the load-bearing component: The exact optimum 1+∆ is restored when the selector retains the entire consistent set, including all data windows and the prior, and centers on it.The passage identifies the selector as the load-bearing component and contrasts this with estimates that pay order 2∆ under masking.
  • Toward a model-chasing theory of adaptive control: Robust oracle × consistent model chasing is proposed as the organizing principle for adversarial adaptive control, with optimality certificates replacing asymptotic ones.The scalar problem is presented as having a complete certificate, with exact extension left open.

A The framework interface conditions: statements and proofs

The appendix formalizes the oracle–selector interface and proves that deadbeat control is a robust oracle while midpoint selection is a 1-competitive consistent model chaser. Their composition therefore inherits worst-case boundedness and mistake guarantees for arbitrarily large parameter sets.

  • Composition guarantee: The oracle–selector composition inherits worst-case boundedness and mistake bounds for arbitrarily large parameter sets.This is the consequence supplied by the general theorems once the two interface conditions are verified.
  • Interface conditions: The framework composes a robust oracle with a consistent model chaser through u_t = π[SEL(data_t)](x_t).The oracle tolerates parameter sequences within distance ρ of the truth, while the chaser selects parameters consistent with all observed data and controls cumulative movement relative to consistent-set changes.
  • Robust oracle: For every ρ ∈ (0, 1), deadbeat control satisfies |x_{t+1}| ≤ ρ|x_t| + 1 and yields a geometric peak envelope.This follows by rewriting the closed loop as x_{t+1} = (a − θ_t)x_t + w_t under |θ_t − a| ≤ ρ.
  • Robust oracle: The deadbeat oracle has finite mistake bounds for thresholds b > 1/(1−ρ), with M^π_ρ(γ) bounded logarithmically in the initial-state radius γ.The threshold is sharp: for b ≤ 1/(1−ρ), an adversary can sustain mistakes indefinitely from any γ > 1/(1−ρ).
  • Consistent model chaser: 1-competitive midpoint selection is a consistent model chaser for every nested sequence of closed intervals.Its total movement is bounded by half the initial interval length, and midpoint movement over any time window is at most the Hausdorff distance between the endpoint consistent sets.
  • Consistent model chaser: The midpoint selector is the one-dimensional Steiner point, linking the construction to the Steiner-point chasing algorithm used in the general framework.For nested intervals, endpoint-gap decomposition bounds each midpoint change by half the interval-length decrease and yields the competitive guarantee by telescoping.

B Attack primitives and lower-bound witnesses

Three adversarial primitives—kick, spike, and echo—construct lower-bound witnesses for consistent certainty-equivalent deadbeat controllers. Tuned across error caps, they yield the exact witness value 1 + h(G) for G ≥ 1 and 1 + G for G ≤ 1.

  • Attack primitives: Kick forces s_1 = 1 while providing zero information, leaving the posterior unchanged at A_1 = A_0.Because x_0 = 0 forces u_0 = 0, w_0 = ±1 realizes the unit state spike.
  • Attack primitives: A spike of height y is feasible exactly when y ∈ [E_t − 1, E_t + 1], and its data window survives at the far corner of A_t.For y ≥ 1, increasing y moves the width-2 window off the corner and shortens the surviving posterior one-for-one.
  • Attack primitives: Echo defers choosing a until θ_{t+1} is revealed, then selects the opposite posterior endpoint and produces s_{t+2} = E_{t+1}y + 1.The deferred parameter remains admissible because it belongs to the consistent posterior and has reconstructed disturbances bounded by 1.
  • Optimal tuning: The echo payoff is μy = y min(2, E_t + 1 − y), whose two optimal tunings are the half-spike and vertex-spike regimes.These tunings are branches of the same one-variable maximization, while the full-spike is the aligned kick requiring no echo.
  • Witness family: 1 + h(G) is attained for G ≥ 1, while 1 + G is attained for G ≤ 1, against any endpoint-selecting certainty-equivalent deadbeat law.The witness construction maintains E_t = L_t ≤ G at every step on the prior A_0 = [−G/2, G/2].

C Proof details for Proposition 10

The proof separates regret from peak performance in both directions: sparse probing can achieve sublinear regret while producing an infinite peak, whereas the optimal peak law can suffer linear regret through a stealth attack that prevents identification. These constructions also show that the probe’s self-correction limits mistakes per episode, while refusing to excite the system leaves the consistent set unchanged.

  • Small regret, infinite peak: C(Δ, ε) = O(log(Δ^2/ε)) mistakes occur before the surviving consistent interval becomes sufficiently narrow.Each mistake more than halves the surviving interval length.
  • Small regret, infinite peak: At most 3 mistakes occur per probe episode, since the probe transition re-identifies a while later dynamics re-enter the mistake-free regime.The first episode contributes O(1) mistakes, and subsequent episodes contribute at most 3 uniformly in k.
  • Small regret, infinite peak: O(log T) regret with t_k = 2^k still accompanies an infinite worst-case peak, because x_{t_k+1} = p_k → ∞ under (a, w) = (0, 0).With t_k = 2^{2^k}, regret becomes O(log log T).
  • Both directions under c_t = |x_t|: Under cost c_t = |x_t|, probing and nonprobing laws rank oppositely across criteria: probing has bounded regret but unbounded peak, while the plain optimal law has at most 3 mistakes.The threshold-cost comparison reports bounded mistake-regret for the plain law versus Θ(#probes) for the probing law.
Loading 2608.13651v1…