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

Dimitar Ho

eess.SYAug 13, 2026

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

Authors: Dimitar Ho

Organizations: California Institute of Technology

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: The change of variables behind Corollary 1 and Proposition 3 . (a) In model space the update intersects the consistent set $A_{t}$ with a data window $W_{t}$ whose width $2/s_{t}$ shrinks as the state grows. (b) The affine map $\varphi_{t}$ sends the posited model $\theta_{t}$ to the origin and rescales by the regressor $x_{t}$ . The image $J_{t}$ of $A_{t}$ straddles $0$ with reaches $q_{\pm}$ , both equal to $g_{t}/2$ for the midpoint law, matching the radius $r$ of Lemma 1 , and at most $E_{t}s_{t}$ for a general implicit selector, where $E_{t}:=\sup_{\alpha\in A_{t}}\left\lvert\alpha-\theta_{t}\right\rvert$ is the selector’s worst-case error; the window becomes an interval of width exactly $2$ centered at the realized successor state $y=x_{t+1}$ ; and the posterior length is read off as $\mu=s_{t}L_{t+1}$ . The window lemma, the invariant, and the attack primitives of Appendix B are all statements about this one picture: how much of $J_{t}$ a width- $2$ window placed at $y$ can leave behind. (c) Once $y>1$ the window sits strictly on one side of $0$ , and if it is clipped by the far end of $J_{t}$ (the only way to realize a large $y$ ), the exchange is exact: magnitude realized now is subtracted, unit for unit, from the uncertainty left to exploit later.

		state	consistent set			controller		adversary		transition
$t$	move	$x_{t}$	$A_{t}$	$L_{t}$	$E_{t}$	$\theta_{t}$	$u_{t}$	$a$	$w_{t}$	window $W_{t}$
$0$	kick	$0$	$[-\Delta,\Delta]$	$2\Delta$	—	—	$0$	free	$-1$	$\mathbb{R}$
$1$	half-spike	$-1$	$[-\Delta,\Delta]$	$2\Delta$	$R$	$a^{\circ}$ (clamp)	$a^{\circ}$	$:=-\Delta$	$-1$	$[-\Delta,\;-\Delta{+}2]$
$2$	echo	$R{-}1$	$[-\Delta,\,-\Delta{+}2]$	$2$	$2$	$-\Delta{+}2$ (clamp)	$(\Delta{-}2)(R{-}1)$	$-\Delta$	$-1$	—
$3$	—	$-(2R{-}1)$	peak $=2R-1=2\Delta+2\left\lvert a^{\circ}\right\rvert-1$

Table 1: The anchored-optimism attack of Proposition 9 , mirrored so that

a^{\circ}\geq 0

;

R=\Delta+\left\lvert a^{\circ}\right\rvert

. Row

t

is the game state at step

t

A_{t}

is the consistent set entering the step,

L_{t}

its length,

E_{t}=\sup_{\alpha\in A_{t}}\left\lvert\alpha-\theta_{t}\right\rvert

the selector’s worst-case error, and

W_{t}

the data window induced by the transition out of the step (

A_{t+1}=A_{t}\cap W_{t}

). Unlike the endpoint attack of Proposition 7 , the selector is an interior clamp (

E_{1}=R<L_{1}

) and no deferral is needed: the adversary commits to

a=-\Delta

already at the spike, since the clamp’s later selections are determined. The half-spike parks the width-

2

window at the far corner; the clamp then sits at distance

2

from

a

, and the echo doubles the state.

Figure 2: Empirical verification. Left: the worst peak found by any attack family (markers) coincides with the theoretical value $\gamma^{\star}=1+\Delta$ (line) over more than three orders of magnitude of $\Delta$ . Right: the realized worst-case trajectory for $\Delta=5$ : the disturbance kicks the state to $1$ while revealing nothing about $a$ ; the aligned extreme parameter then produces the one-time identification spike $\left\lvert x_{2}\right\rvert=\Delta+1=6$ , which reveals $a$ exactly, after which deadbeat control holds $\left\lvert x_{t}\right\rvert\leq 1$ forever.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: The spike knob, in the regressor coordinate of Corollary 1 . Thick segment: the prior $A_{1}=[-\tfrac{G}{2},\tfrac{G}{2}]$ after the kick, with the selected endpoint $\theta_{1}$ at one end. Shaded: the surviving posterior $A_{2}$ , which always abuts the far corner $a$ . Raising the spike height $y$ slides the width- $2$ data window leftward off that corner. Left: at $y=G-1$ the window just fits inside the prior and the full length $\mu=2$ survives. Right: at $y>G-1$ the window overhangs and $\mu=G+1-y$ shrinks one-for-one — the tradeoff the adversary optimizes.

		state	consistent set		controller		adversary		transition
$t$	move	$x_{t}$	$A_{t}$	$L_{t}{=}E_{t}$	$\theta_{t}$	$u_{t}$	$a$	$w_{t}$	window $W_{t}$
$0$	kick	$0$	$[-\tfrac{G}{2},\tfrac{G}{2}]$	$G$	—	$0$	free	$+1$	$\mathbb{R}$
$1$	spike	$1$	$[-\tfrac{G}{2},\tfrac{G}{2}]$	$G$	$\tfrac{G}{2}$	$-\tfrac{G}{2}$	free	$\tfrac{G}{2}{-}y{-}a$	$[\tfrac{G}{2}{-}y{-}1,\;\tfrac{G}{2}{-}y{+}1]$
$2$	echo	$-y$	$[-\tfrac{G}{2},\;\tfrac{G}{2}{-}y{+}1]$	$\mu$	${\in}\;\partial A_{2}$	$\theta_{2}\,y$	opp. end of $A_{2}$	$\operatorname{sgn}\!\big((a{-}\theta_{2})x_{2}\big)$	—
$3$	—	$\pm(\mu y{+}1)$	peak $=\mu y+1$ , where $\mu=\min(2,\;G{+}1{-}y)$

Appendix

Table 2: The witness run of Lemma 2 at generic spike height

y

, on the prior

[-\tfrac{G}{2},\tfrac{G}{2}]

, mirrored so that

\theta_{1}=\tfrac{G}{2}

(far corner

c=-\tfrac{G}{2}

). Row

t

is the game state at step

t

A_{t}

is the consistent set entering the step,

W_{t}

the data window induced by the transition out of it (

A_{t+1}=A_{t}\cap W_{t}

), and

E_{t}=L_{t}

because the selector picks endpoints. The adversary defers committing to

a

until

\theta_{2}

is revealed: any

a\in A_{2}

certifies

\left\lvert w_{1}\right\rvert\leq 1

through the tabulated reconstruction

w_{1}=\tfrac{G}{2}-y-a

. For

G\leq 1

the optimum is the full-spike

y=G+1

, ending at

t=2

with no echo. Optimal tunings of

y

: Table 3 .

regime	spike height $y$	posterior $\mu$	trajectory $(x_{1},x_{2},x_{3})$	peak
$G\leq 1$	$G+1$ (full-spike)	— (no echo)	$(1,\;-(1+G))$	$1+G$
$1\leq G\leq 3$	$\tfrac{G+1}{2}$ (vertex)	$\tfrac{G+1}{2}$	$\big(1,\;-\tfrac{G+1}{2},\;\pm(1+h(G))\big)$	$1+\big(\tfrac{G+1}{2}\big)^{2}$
$G\geq 3$	$G-1$ (half-spike)	$2$	$\big(1,\;-(G-1),\;\pm(2G-1)\big)$	$2G-1$

Appendix

Table 3: The witnesses of Lemma 2 , on the prior

[-\tfrac{G}{2},\tfrac{G}{2}]

against the endpoint law. The sign of

x_{3}

is whichever the selector’s tie-break forces; the adversary commits to

a

only after seeing

\theta_{2}

. Both branch points of

h

are feasibility boundaries of the single spike knob:

G=3

is where the width-

2

window stops fitting inside the prior (

\mu\leq 2

starts to bind), and

G=1

is where the vertex height drops below

1

and the echo dies. Certified numerically for

G

across three orders of magnitude (

0.05

200

) and for both endpoint tie-breaks, each attack replayed through the closed loop from its reconstructed certificate.

$t$	bound on $\left\lvert x_{t}\right\rvert$	information state after the step	mistake?
First episode — entered from the plain law: $\left\lvert x_{t_{1}}\right\rvert\leq 1+\Delta$ , $L_{t_{1}}\leq 2\Delta$ .
$t_{1}$	$1+\Delta$	—	(in $C$ )
$t_{1}{+}1$	$p_{1}{+}1{+}\Delta$ (probe)	regressor ${\geq}\,p_{1}{-}1{-}\Delta$ : $L\leq\tfrac{2}{p_{1}-1-\Delta}\leq\tfrac{\varepsilon}{1+\Delta}$	yes
$t_{1}{+}2$	$\Delta(p_{1}{+}1{+}\Delta)+1$ (exposure)	plain-law step: ( 11 ) gives $g_{t_{1}+3}\leq L_{t_{1}+2}\leq L$	yes
$t_{1}{+}3$	$\tfrac{L}{2}\left\lvert x_{t_{1}+2}\right\rvert+1\leq\Delta(1{+}\varepsilon)+O(1)$ (echo)	—	$\leq 1$
$t_{1}{+}4$	$L/2+1\leq 1+\varepsilon/2$	—	no

Appendix

Table 4: Per-step bookkeeping of the probe episodes of Appendix C (i), valid for every admissible

(a,w)

; a mistake is

\left\lvert x_{t}\right\rvert>1+\varepsilon

. The probe’s own transition re-identifies

a

whatever the adversary plays — the disturbance shifts the window’s center, never its width — so each episode contributes at most

3

mistakes before the loop re-enters the mistake-free regime of Figure 4 (a).

Panel of Figure 4 — Figure 4: Appendix C (i) and (iii): a law whose regret is small under every accounting and whose worst-case peak is infinite. (a) The optimal law with isolated probes $p_{k}\uparrow\infty$ superimposed at a sparse schedule. Between episodes the invariant ( 11 ) holds the state below $1+\varepsilon$ , so no mistakes accrue there. The regret is carried entirely by the episodes, and there are only $\#\{k:t_{k}\leq T\}$ of them. (b) Inside an episode the bookkeeping is short because the probe is self-correcting: the probe state is enormous, so the transition out of it measures $a$ through a huge regressor and confines the parameter to a window of width $\leq 2/(p_{k}-2)$ , whatever the adversary does, since the disturbance can shift that window’s center but not its width. Two large states (probe and echo), then the loop is back under $1+\varepsilon$ . (c) The consequence, and the reason Proposition 10 is stated in both directions. Columns are fixed per law; the check marks the better law on each scoreboard. The peak and mistake criteria prefer the optimal law; on the third scoreboard the check jumps columns — the integrated criterion prefers the law with the infinite peak . Nothing about the trajectories changed between the rows — only how they are added up.

$\Delta\geq 1$ : $a=1$ , $\bar{x}:=\tfrac{1}{\Delta+1}$ .
$t$	$x_{t}$	$w_{t}$	window $W_{t}$	$A_{t+1}$	excess $\left\lvert x_{t}\right\rvert-\left\lvert x^{*}_{t}\right\rvert$
$0$	$0$	$\bar{x}$	$\mathbb{R}$ (zero regressor)	$[-\Delta,\Delta]$	$0$
$1$	$\bar{x}$	$0$	$[-\Delta,\;\Delta+2]$	$[-\Delta,\Delta]$	$0$
$t\geq 2$	$\bar{x}$	$0$	$[-\Delta,\;\Delta+2]$	$[-\Delta,\Delta]$	$\bar{x}$
$\Delta<1$ : $a=\Delta$ , $\bar{x}:=\tfrac{1}{\Delta+1}$ .
$0$	$0$	$\bar{x}$	$\mathbb{R}$ (zero regressor)	$[-\Delta,\Delta]$	$0$

Appendix

Table 5: The stealth pairs of Appendix C (ii) against the optimal law. Throughout,

\hat{a}_{t}\equiv 0

and

u_{t}\equiv 0

: every induced window

W_{t}

contains the full prior, so

A_{t+1}=A_{t}=[-\Delta,\Delta]

and the loop reproduces itself — zero information leaks at any time, and each row for

t\geq 1

repeats forever. Excess is measured against the clairvoyant

x^{*}_{t+1}=w_{t}

(deadbeat at the true

a

); summing the last column gives the stated linear regret.

Panel of Figure 5 — Figure 5: The stealth attack of Appendix C (ii), at $\Delta=5$ : $a=1$ , $w_{0}=\bar{x}:=\tfrac{1}{\Delta+1}$ , $w_{t}=0$ thereafter. (a) The adversary parks the state at $\bar{x}$ and leaves it there. Because the regressor is $\bar{x}$ , the induced data window has width $2/\bar{x}=2(\Delta+1)$ and is centered at the true $a=1$ , so it contains the entire prior, with its lower edge falling exactly on $-\Delta$ . The intersection removes nothing, the consistent set never shrinks, the midpoint stays at $0$ , the input stays at $0$ , and the loop reproduces itself forever: an attack that leaks no information at any time. This is the exact complement of the spike of Remark 8 : there, magnitude is bought at the price of information; here, no magnitude is taken and no information is given. (b) The optimal law therefore holds $\bar{x}$ forever while the clairvoyant, knowing $a$ , pays only the one-time disturbance. Under the cumulative state cost the minimax-optimal policy accrues regret $\tfrac{T-1}{\Delta+1}$ , linear in $T$ — the price of refusing to gamble on dynamics the data have not pinned down.

Explore similar work

Sep 27, 2026

Sharp Critical Minimax Laws and No-Learning Thresholds in Continuous-Time Adaptive Control

We study episodic continuous-time control with an unknown vector control gain, scalar state, quadratic action cost, and smooth convex terminal cost. In the scalar Gaussian experiment, let

Δ(H)

denote the minimax improvement over zero control and set

δ=\sqrt2H^2-1

. We prove the critical law

Δ(H)\asymp δ^4\sqrt{\log(1/δ)} \qquad (δ\downarrow0),

with a matching lower and upper bound. The lower bound follows from a uniform deficit--energy inequality valid for fully adaptive controls with unbounded amplitudes, while a moving soft-threshold feedback attains the rate. For local parameters

θ=N^{-1/4}h

|h|\le H

, we show that the normalized minimax regret over

N

episodes is within

O(N^{-1/2})

of a fixed-horizon Gaussian sequential control problem, without an additional dimension factor. The terminal task enters the limit only through

c_g=\operatorname{Var}(g(Z))

. The Gaussian problem exhibits an exact no-learning phase transition:

C_d^T(H)=TH^2/2 \iff H^4T\le d^2/2,

yielding the asymptotic task boundary

c_gH^4=d^2/2

Chen Jia

Adaptive Control Stochastic Optimal Control Minimax Regret Phase Transitions

Ask PDF

Jul 29, 2026

Self-Adaptive Learning and Model Predictive Control for Tracking Unknown Dynamics with No Regret

We propose a self-adaptive online learning for control method for tracking unknown target dynamics. The target dynamics can exhibit switching behavior, particularly, a mixture of structured, random, and/or adversarial motion. Such challenging target tracking scenarios arise in applications of dynamic mapping, traffic control, and pursuit evasion, where robots need to track, pursue, or avoid collision with moving landmarks, objects, humans, etc., whose dynamics are unknown. Our method simultaneously learns multiple predictors from scratch, via self-supervised, one-shot, and computationally efficient learning, and adaptively selects the best one to match the observed target behavior. The method enjoys finite-time near-optimality guarantees in expectation, characterized as a function of the learning error of the target dynamics and the frequency that the target dynamics switch. In the absence of both error and switching, the method asymptotically matches the optimal non-causal control policy that knows a priori the target dynamics, i.e., the method enjoys no regret in expectation. In the presence of learning errors and switching, the method degrades gracefully, \eg when there are errors and no switching, the average regret is proportional to the average learning error and switching times. To prove these guarantees, a novel technical approach is required compared to the existing works that employ RFF-based online learning. We validate our method in Crazyflie simulations and hardware experiments, across target trajectories that vary from structured to random to adversarial, in comparison to non-stochastic, kernel-based, and neural-network-based methods for online learning.

Atharva Navsalkar, Hongyu Zhou, Vasileios Tzoumas

Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

Dynamical Systems Regime-Switching Dynamical Systems Model Predictive Control Regret Minimization Adaptive Learning Online Learning

Ask PDF

Jul 18, 2026

When Can Safe Controllers Adapt? Information before Commitment

Safe adaptive control is online adaptation under a safety guarantee on the learning trajectory itself. The controller may use any causal, history-dependent rule and act differently across environments as data arrive. Only its safety guarantee is uniform: the same rule must satisfy it under every initially plausible model. Performance is measured against a safe oracle that knows the realized model. Many finite-time analyses assume persistent excitation of the uniformly safe closed loop, so the data distinguish every pair of models requiring different control decisions. Under that assumption, feasibility is already settled; only the rate remains. We ask instead: Do the safety constraints permit such an informative experiment at all? While an alternative remains plausible, the controller must preserve a safe continuation under it. We call the first action that forecloses such a continuation commitment. Chance safety allows commitment only on an event rare under the alternative, and the evidence must arrive beforehand: the observation generated by the committing action is too late. We define precommitment information as the KL divergence between learner-visible laws stopped before commitment. Our main result is a causal reduction. The commitment rule determines (1) the probability that safety permits commitment under the alternative, (2) the target-side cost of remaining noncommittal, (3) and the information available when the decision is made. Bounded precommitment information therefore leaves a fixed fraction of the oracle gap unavoidable. If the gap is Ω(T), every uniformly safe policy has linear regret. We establish the obstruction in a constrained linear system with quadratic regulation cost. We also prove recovery in special cases and derive semidefinite upper certificates for deterministic linear-Gaussian systems.

Venkatesh Saligrama

Department of Electrical and Computer Engineering, Boston University, MA 02215

RL Exploration Optimal Control Adaptive Control Information-Theoretic Lower Bounds

Ask PDF