CS Paper Radar

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

Dimitar Ho

eess.SY cs.LGmath.OC ·submitted 2026-08-13 18:00 UTC · v1

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.

Comment
37 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG math.OC ·2026-09-27 ·Chen Jia
theory similarity 0.63
Abstract

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$.

0.27

Online Constrained Control of Storage Systems via Simplex Disturbance-Action Policies

eess.SY ·2026-09-07 ·Kamiar Asgari, Michael J. Neely
theory similarity 0.62
Abstract

We study online control of a scalar storage system with nonnegative adversarial resource arrivals and state-dependent action constraints. The adversarial, time-varying cost depends on both state and action. At each time, the controller selects a feasible action before the current resource arrival and cost are revealed. To handle the coupling between feasibility and online learning, we introduce Simplex Disturbance-Action Control (SDAC), whose policies have $H$ nonnegative parameters summing to at most one. Every fixed SDAC policy is feasible by construction. Our online SDAC controller updates these parameters using entropic online mirror descent while preserving feasibility along the time-varying trajectory. We prove a regret bound of $O\!\left(\sqrt{T\log(H+1)}\right)$ relative to the best fixed SDAC policy and a minimax lower bound showing that the dependence on $T$ is tight. We also introduce infinite-memory SDAC policies, which include every feasible fixed-fraction policy. SDAC policies approximate this class with an error that decreases geometrically with $H$. For a suitable choice $H=Θ(\log T)$, the resulting regret against infinite-memory SDAC policies is $O\!\left(\sqrt{T\log\log T}\right)$. The framework applies to energy-harvesting batteries and other storage-constrained resource systems.

0.48

Online Causal Configuration for Networked Systems via Doubly Robust Steady-State Learning

cs.LG stat.ML ·2026-11-06 ·Yuli Liu, Zhiheng Zhang
top venuebenchmarktheory similarity 0.62
Abstract · Accepted at NeurIPS 2026

Measurement exploration reveals how interacting local controllers behave but can alter the steady-state regime a network operator seeks to optimize. Exploratory rewards may therefore fail to identify a configuration's no-exploration value: under full exploration, identical logged distributions can conceal different target values. Identification requires accounting for both action-law mismatch and shifts in the steady-state context distribution. We introduce CAUSAL-UCB, which selects configurations using optimistic bounds on target causal values. Its interference-aware clipped doubly robust evaluator produces predecision certificates separating statistical variation from calibrated identification, transport, and temporal-dependence errors. For any finite horizon and predetermined schedule of measurement-exploration rates $\{η_t\}$, we prove lower bounds of $Ω((1+\sum_tη_t)^{-1/2})$ on minimax inference error and $Ω(\sum_tη_t)$ on measurement-induced deployment loss in a stationary, potentially slow-mixing family. We bound regret under valid certificates and selected-information growth, and establish an anytime finite-sample certificate with a shared radius for estimation, selection, and reporting in a restricted known-local-interference model. In a high-mismatch benchmark with 24 paired seeds and 200 rounds, CAUSAL-UCB attains target regret of $1.732$ versus $6.326$ for certified IPS-UCB, with deployment gaps of $30.607$ and $23.217$, respectively. Independent-audit coverage tests and trace-driven semi-synthetic studies further assess certificate coverage and deployment trade-offs.

0.43

Safe and Scalable Minimax Adaptive Control of Positive Systems

eess.SY math.OC ·2026-11-10 ·Fethi Bencherki, David Ohlin, Tomas Meijer
similarity 0.61
Abstract · 20 pages, 1 figure (6 panels), 1 table

This paper studies minimax adaptive control of positive linear systems with fixed unknown dynamics and nonnegative disturbances. We reformulate the problem by compressing the historical data into a vector and a positivity-induced consistency set containing the models compatible with the observations. Together with the physical state, these quantities form a sufficient information state and yield an exact reformulation as a standard minimax dynamic game. We allow the admissible input set to adapt to the current consistency set, ensuring positivity for every remaining feasible model. As inconsistent models are eliminated, the input set can expand, allowing less cautious control actions. For finite model sets, we derive an explicit solution to the Bellman inequality and construct a safe and stabilizing certainty-equivalence controller with robustness guarantees. The framework also accommodates structured classes of continuum model uncertainty whose consistency sets admit fixed, finite-dimensional representations, enabling scalable information-state updates.

0.17

When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

cs.LG eess.SYmath.OCstat.ML ·2026-11-02 ·Ridham Patel
publishedtheory similarity 0.61
Abstract · Accepted at NeurIPS 2026 FMTS Workshop

Dynamic regret measures an online learner against a moving comparator, and standard analyses assume the learner may move freely at every round. We study what happens when it may not: the learner is given a hard budget $S$ on its total movement $\sum_t \|x_t - x_{t-1}\|$. Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter $D$ with $G$-Lipschitz convex losses, for every comparator path length $P_T \in [D, DT]$ we exhibit a deterministic adversary that forces $R_d = Ω(GDT)$ on every budget-feasible algorithm whenever $S \le c P_T$ for a universal constant $c>0$. This barrier is caused by the budget rather than by a volatile environment: for fixed $D$, it applies when $P_T = o(T)$, where the unconstrained minimax rate $Θ(G\sqrt{D(D+P_T)T})$ is sublinear, so the same instances are learnable with an unbounded budget and unlearnable without one. Conversely, projected online gradient descent with a budget-aware step size is budget-feasible and attains $o(GDT)$ once $S = ω(D + P_T)$. Thus the critical movement scale is $D+P_T$: linear regret is unavoidable below a sufficiently small constant multiple of $P_T$, while sublinear regret is achievable when $S/(D+P_T)\to\infty$ in the learnable regime. The construction rests on a distinction we make explicit: what makes a comparator expensive to track under a movement budget is the distance it forces the learner to travel, not its path length. Above the threshold we give a budget-dependent upper bound and identify the tight minimax rate in this region as an open problem rather than claiming a product law. Experiments support the predicted transition location and the $1/S$ decay.

0.32

Optimal Regret for Online Storage Control via Cumulative Policies

eess.SY math.OC ·2026-09-18 ·Kamiar Asgari, Michael J. Neely
theory similarity 0.60
Abstract

We study online control of a scalar storage system with adversarial nonnegative arrivals, known retention coefficient, and convex costs depending on both state and action. Each action must respect current resource availability and is chosen before the current arrival and cost function are revealed. For the existing simplex disturbance-action policy class, we give an exact reparameterization by cumulative allocation fractions and a decay-weighted projected subgradient update. The resulting regret bound is independent of policy memory length. For fixed retention coefficient and cost constants, the controller achieves $O(\sqrt T)$ regret against the best fixed infinite-memory policy in this class, using $O(\log T)$ memory and arithmetic operations per round and one cost-subgradient query. A storage-specific block construction gives a matching lower bound against every causal feasible controller, including randomized controllers. Writing $τ=(1-α)^{-1}$, the minimax expected regret is $Θ(\sqrt T\min\{T,τ\}^{3/2})$ for every finite-memory simplex policy class and its infinite-memory extension, when $α\in[1/2,1)$, $T\ge4$, and the positive cost constants are fixed. This identifies the joint horizon and retention-time dependence for these policy benchmarks.

0.10

First-Order Optimization as Minimum-Time Control

eess.SY math.OC ·2026-08-14 ·Liraz Mudrik, Isaac Kaminer, Pramod P. Khargonekar
benchmark similarity 0.60
Abstract · 13 pages, 4 figures

We formulate first-order optimization as a minimum-time control problem. The iterate is the state, the update, a combination of the gradients observed so far, is the control, and the points with gradient norm at most a prescribed tolerance form the target set. For a fixed objective and start, the minimum number of oracle queries needed to reach the target is a value function: it measures the complexity of the instance, not the worst case over a class. On a strongly convex quadratic, the conjugate gradient iterates emerge from the discrete Pontryagin conditions, and the value is a controllability index. Beyond the quadratic, a Hessian-generated reachable span replaces the controllability matrix, and feasibility becomes a reachability question: whether a critical point can be reached at all, and in how many steps, is read from the span. Curvature is a resource: a checkable condition certifies that an instance needs fewer steps than the controllability index of its quadratic model at the minimizer, and the gap can grow without bound with the dimension. The value is thus a benchmark for the intrinsic difficulty of each instance, against which any first-order method can be measured.

0.10

Logarithmic Regret via Passive Change Detection in Piecewise-Stationary Self-Tuning Regulation

cs.LG cs.AI ·2026-10-07 ·A. Ch. Madhusudanarao, Rahul Singh
theory similarity 0.58
Abstract

We study minimum-variance control of an unknown autoregressive system with exogenous inputs and coefficients that change at unknown times. Under bounded independent disturbances, fixed detection gaps, stability and feasibility conditions, and sufficient time between changes, we prove \(O((C+1)\log((T+1)/δ))\) regret with probability at least \(1-δ\), where \(T\) is the horizon and \(C\) the number of changes. Unlike switching bandits, where unselected arms can change unobserved, admissible plant changes provide information during exploitation: the correct feasible controller leaves only the disturbance in the output, whereas a detectable change raises output energy under the old controller. PIECE-CD explores initially and after alarms, then uses gated recursive least squares for control. Its energy test compares windowed output power with a threshold above the noise floor; the extension to unstable controller mismatches also monitors the reference controller's input proposal. We control false alarms across the horizon and prove logarithmic detection delay. Inputs are clipped to prescribed bounds. Logarithmic regret also holds under an explicit condition ensuring that clipping becomes inactive after a finite burn-in. Under the stated feasibility conditions, the extended detector covers destabilizing changes with detectable excess energy over a fixed window.

0.26