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.
1. Introduction
Classical control theory and recent "nonstochastic" control approaches have largely focused on Linear Time-Invariant (LTI) systems, where the underlying physical laws governing the system remain constant. However, real-world applications—ranging from robotics to autonomous flight—frequently encounter environments that change over time. A drone's flight dynamics shift in a rainstorm, and mechanical components wear down, altering a robot's response to torque.
While recent advances in regret minimization allow controllers to handle adversarial noise, they typically rely on "standard regret." This metric compares a controller's performance to the single best fixed policy in hindsight. In a dynamic or changing environment, a single fixed policy is often a mediocre compromise that fails to capture the optimal behavior for any specific sub-interval. To address this, we introduce the concept of Adaptive Regret to the control domain, requiring a controller to perform well against the best local policy for every possible time interval.
2. The Challenge of Time-Varying Dynamics
Linear Time-Varying (LTV) systems serve as a critical bridge between simple LTI models and complex nonlinear systems. By using local first-order approximations (iterative linearization), many nonlinear problems can be treated as LTV systems. However, controlling LTV systems is inherently difficult due to the "memory" effect: an action taken at time $t$ influences the state and the resulting costs for many subsequent steps.
This creates a fundamental Agility-Stability Trade-off. To minimize adaptive regret, an algorithm must be "agile" enough to track environmental shifts. Conversely, because past actions have lingering effects, the algorithm must remain "stable" to avoid the accumulated costs of rapid policy shifts. This paper formalizes this conflict within the framework of Online Convex Optimization (OCO) with memory.
3. The Meta Adaptive Regret Controller (MARC)
Our primary contribution is the Meta Adaptive Regret Controller (MARC). MARC is a meta-algorithm designed to convert standard controllers with sublinear regret into adaptive controllers.
3.1 Mechanism
MARC maintains a set of "base" controllers (experts), each initialized at different points in time. The meta-algorithm aggregates the suggestions of these experts using a weighted switching scheme to determine the final control action. While a naive implementation would require $T$ controllers (one for every timestep), we utilize a construction that only requires $O(\log T)$ active controllers at any given time, ensuring the algorithm is computationally efficient and practical for real-time applications.
3.2 OCO with Memory
Control is modeled as OCO with memory, where the loss function depends on a sequence of past actions. We provide the first adaptive regret bounds for this framework. We prove that any algorithm in this setting must suffer at least $\Omega(\sqrt{T})$ adaptive regret. MARC achieves a bound of $\tilde{O}(\sqrt{OPT})$, where $OPT$ is the cost of the best policy. This "first-order" bound is particularly powerful because it implies that if the environment is easy to control (low $OPT$), the regret is significantly smaller than the worst-case scenario.
4. Experimental Evaluation
We evaluated MARC using a simulated Inverted Pendulum, a standard benchmark in control theory. The goal is to maintain a pole in an upright position by applying torque to the base.
To test adaptability, we introduced a Sinusoidal Shock Scenario. Midway through the simulation, the pendulum is subjected to an unanticipated adversarial force (a sinusoidal wave). Standard planning methods, such as iLQR, are environment-agnostic and failed to adapt to these midway shocks, leading to system failure. In contrast, MARC successfully adapted to the new dynamics. By leveraging its internal ensemble of controllers, MARC identified the shift in dynamics and adjusted its policy to maintain stability where other methods crashed.
5. Conclusion
MARC provides a robust theoretical and practical framework for control in non-stationary environments. By achieving nearly tight adaptive regret bounds for OCO with memory, we provide a foundation for applying iterative linearization methods to nonlinear robotics problems with greater reliability.
Future work will explore "strongly adaptive regret," where bounds depend specifically on the length of the interval, and the extension of these guarantees to high-probability bounds. Additionally, further research is needed to characterize the specific properties of nonlinear dynamics that most effectively map to the LTV approximations used by MARC.
Summary updated