Online Control via Counterfactual Tracking

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