Abstract
We consider the problem of online control of systems with time-varying linear dynamics. This is a general formulation that is motivated by the use of local linearization in control of nonlinear dynamical systems. To state meaningful guarantees over changing environments, we introduce the metric of adaptive regret to the field of control. This metric, originally studied in online learning, measures performance in terms of regret against the best policy in hindsight on any interval in time, and thus captures the adaptation of the controller to changing dynamics. Our main contribution is a novel efficient meta-algorithm: it converts a controller with sublinear regret bounds into one with sublinear adaptive regret bounds in the setting of time-varying linear dynamical systems. The main technical innovation is the first adaptive regret bound for the more general framework of online convex optimization with memory. Furthermore, we give a lower bound showing that our attained adaptive regret bound is nearly tight for this general framework.
Introduction
In classical control theory, systems are often modeled as Linear Time-Invariant (LTI). This assumes the physical laws governing a system—such as the aerodynamics of a drone or the mechanics of a robotic arm—remain constant over time. However, real-world environments are rarely static. A drone’s flight dynamics shift as it consumes battery power or encounters unpredictable wind gusts.
Recent research in nonstochastic control has utilized regret as a performance metric. Standard regret measures how an algorithm performs compared to the single best fixed policy chosen in hindsight. While useful, this is a relatively low bar for changing environments; a policy that is optimal for the first half of an experiment might be disastrous for the second. To address this, we introduce adaptive regret to the control domain, requiring a controller to compete with the best possible policy on any given time interval.
The Challenge of Time-Varying Dynamics
We focus on Linear Time-Varying (LTV) systems, which serve as a powerful proxy for complex nonlinear systems through iterative local linearization. The primary difficulty in controlling these systems lies in the presence of "memory." Unlike standard Online Convex Optimization (OCO), where an action only affects the immediate loss, actions in a dynamical system change the state, influencing all future costs.
This creates a fundamental tension between stability and agility. To manage the long-term effects of actions (memory), a controller must be stable and change its decisions gradually. Conversely, to minimize adaptive regret in a shifting environment, the controller must be agile enough to pivot quickly when dynamics change.
The MARC Meta-Algorithm
Our primary contribution is the Meta Adaptive Regret Controller (MARC). MARC is designed as a meta-algorithm that can wrap around various "base" controllers (such as GPC or DRC-ONS) to grant them adaptive properties.
1. Expert Ensemble
MARC maintains multiple "expert" copies of a base controller. Each expert is initialized at a different point in time. By maintaining a weighted ensemble of these experts based on their recent performance, MARC can effectively "switch" its strategy if the system dynamics undergo a sudden shift.
2. OCO with Memory
We frame the control problem as OCO with memory. We provide the first adaptive regret bound for this general framework, proving that MARC achieves an adaptive regret of $\tilde{O}(\sqrt{OPT})$, where $OPT$ is the cost of the best policy. This is a "first-order" bound, meaning the algorithm performs even better when the environment is benign and the optimal cost is low.
3. Computational Efficiency
While a naive implementation of MARC might require $T$ controllers (one for each timestep), we utilize an efficient implementation that requires only $O(\log T)$ active controllers. This makes the algorithm computationally feasible for real-time control applications.
Empirical Evaluation
We evaluated MARC using the Inverted Pendulum environment from OpenAI Gym, comparing a standard noiseless version against a version featuring Sinusoidal Shocks. In the latter, an adversarial perturbation is introduced midway through the run to simulate a sudden change in dynamics.
Our results demonstrated that standard planning methods like iLQR, which are environment-agnostic, failed completely when the sinusoidal shock was introduced. MARC, however, successfully adapted to the noise. By leveraging its ensemble of experts, the meta-algorithm identified the shift in dynamics and maintained stability where fixed-policy approaches could not.
Conclusion and Future Work
MARC provides a robust framework for teaching controllers to pivot in changing worlds. By achieving a nearly tight adaptive regret bound of $\Omega(\sqrt{T})$, we show that this approach is near-optimal for OCO with memory.
Future research directions include extending these results to strongly adaptive regret, where bounds depend on the optimal cost specifically within each sub-interval rather than the total horizon. Additionally, moving from expected bounds to high-probability bounds remains an open challenge for first-order adaptive regret in control systems.
Summary updated