Abstract: We consider the problem of tracking an adversarial state sequence in a linear dynamical system subject to adversarial disturbances and loss functions, generalizing earlier settings in the literature. To this end, we develop three techniques, each of independent interest. First, we propose a comparator-adaptive algorithm for online linear optimization with movement cost. Without tuning, it nearly matches the performance of the optimally tuned gradient descent in hindsight. Next, considering a related problem called online learning with memory, we construct a novel strongly adaptive algorithm that uses our first contribution as a building block. Finally, we present the first reduction from adversarial tracking control to strongly adaptive online learning with memory. Summarizing these individual techniques, we obtain an adversarial tracking controller with a strong performance guarantee even when the reference trajectory has a large range of movement.
Introduction
In classical control, tracking involves steering a system to follow a reference trajectory. While modern learning-based control has made strides in regulation—maintaining a system at a fixed origin despite noise—adversarial tracking remains a significant challenge. In this setting, the target trajectory is not pre-planned; it may change abruptly, follow no known model, or even react to the controller's own actions.
This paper bridges the gap between control theory and strongly adaptive online learning to develop a controller capable of tracking unpredictable targets with near-optimal performance across any time interval, even in the presence of adversarial disturbances and time-varying dynamics.
The Challenge of Adversarial Tracking
Tracking is inherently harder than regulation because real-world systems possess memory (past actions influence current states) and movement costs (rapidly changing actions are often physically impossible or energetically inefficient).
Existing algorithms often struggle with "strong adaptivity." While they might perform well on average over a long horizon, they can fail during short, critical windows when a target suddenly shifts. Furthermore, most controllers require prior knowledge of the target's range or optimal learning rates. The goal of this work is to create a "comparator-adaptive" system that automatically tunes itself to the target's movement speed without manual intervention.
The Three-Pillar Methodology
The authors' solution is built upon three hierarchical technical contributions:
- Comparator-Adaptive OLO with Movement Cost: The foundation is a new algorithm for Online Linear Optimization (OLO). By utilizing "coin-betting" duality, the authors created an algorithm that matches the performance of the best fixed action in hindsight while strictly limiting prediction movement between steps.
- Strongly Adaptive OCOM: This is extended to Online Convex Optimization with Memory (OCOM). Strong adaptivity is achieved by maintaining multiple subroutines, each responsible for different time scales.
- The Reduction: The final step is a mathematical reduction proving that tracking control can be treated as OCOM. In stable systems, the influence of past actions decays over time. By truncating this history, the control problem becomes a sequence of optimization steps.
Strong Adaptivity via Geometric Covering
To ensure the controller performs well on every sub-interval of time, the authors employ a Geometric-Covering (GC) interval structure. This structure allows the meta-algorithm to manage various subroutines that focus on different temporal resolutions.
By using this structure, the controller ensures it is always "pursuing the best fixed action" for any specific window of time, rather than just optimizing for the global average. This prevents the "slow start" or "overshoot" issues common in traditional adaptive methods when a target moves outside a pre-defined range.
Key Results and Empirical Validation
The framework provides a theoretical regret bound of $\tilde{O}(\sqrt{|I|})$ for any time interval $I$. This means the controller's error on any segment of time is proportional to the square root of that segment's length, regardless of prior or subsequent events.
In synthetic numerical simulations, the controller was tested against adversarial scenarios including step signals, square waves, and complex 2D sinusoidal trajectories. The results demonstrated that the controller successfully tracked circular trajectories even under changing system dynamics and adversarial noise, outperforming standard methods that lack movement-aware adaptivity.
Conclusion and Future Work
This work presents the first reduction from adversarial tracking control to strongly adaptive online learning with memory. While the current framework assumes an "open-loop stable" system, future research may extend these techniques to inherently unstable systems (e.g., rocketry) by integrating them with robust control methods. Additionally, while the computational overhead scales logarithmically with time, optimizing the meta-algorithm for extremely high-frequency applications remains an area for further exploration.
Summary updated