Online Control via Counterfactual Tracking

arXiv:2607.13029v2 Announce Type: cross Abstract: 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{Tlog 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{Tlog 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.

Related

• A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
• Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory
• Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise

Source: arXiv cs.LG | 2026-10-06