Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory

Zhiyu Zhang, Ashok Cutkosky, Ioannis Paschalidis

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 theory, research typically focuses on regulation—maintaining a system state near a fixed point despite disturbances. However, tracking, where a system must follow a dynamic reference trajectory, presents a significantly higher degree of difficulty.

Existing tracking controllers often rely on restrictive assumptions, such as prior knowledge of the target's path or the assumption that the target follows a predictable linear model. In reality, targets—such as an evasive drone or a robot in a dynamic environment—are often unpredictable or "adversarial." This work addresses the challenge of designing a controller that tracks a fully adversarial target with strong adaptivity, ensuring performance guarantees hold over any sub-interval of time rather than just on average.

Methodology: A Hierarchical Approach

The proposed solution utilizes a three-tiered hierarchical framework that bridges online learning and control theory.

1. OLO with Movement Cost

The foundation is a "comparator-adaptive" algorithm for Online Linear Optimization (OLO). Unlike standard OLO, this version incorporates a movement cost, penalizing abrupt changes in control actions. By employing "coin-betting" duality, the authors created a parameter-free algorithm that matches the performance of an optimally tuned system without requiring prior knowledge of optimal settings.

2. Strongly Adaptive OCOM

Building on the OLO foundation, the authors developed an algorithm for Online Convex Optimization with Memory (OCOM). To achieve strong adaptivity, the system maintains a hierarchy of subroutines operating over different Geometric-Covering (GC) intervals. This structure allows the algorithm to effectively "forget" stale data and rapidly adapt to new target trajectories.

The hierarchical structure of Geometric-Covering (GC) intervals used to achieve strong adaptivity.

3. Reduction to Control

The final step is a formal reduction that transforms the adversarial tracking control problem into the OCOM framework. By truncating the system's history—recognizing that distant past actions have diminishing effects on the current state—the OCOM algorithm can be directly applied to generate real-time control actions.

An overview of the OCOM strategy, showing how 1D movement-aware OLO and OLO on a ball are combined via polar decomposition into the meta-algorithm.

Experimental Evaluation

The algorithms were evaluated using synthetic setups designed to simulate diverse adversarial scenarios:

  • 1D and 2D Tracking: Testing against step signals, square waves, sinusoidal waves, and circular reference trajectories.
  • Adversarial Disturbances: Incorporating time-varying system dynamics and adversarial noise (e.g., $w_t = 0.05 \cdot \sin(\pi t / 4000)$) to verify robustness.

Key Insights

  • Adaptivity as Tracking: A central insight of this work is that strong adaptivity in online learning is mathematically equivalent to tracking non-stationary targets in control.
  • Surrogate Losses for Movement: Handling movement costs in adaptive learning is difficult; the authors solved this by introducing a "surrogate loss" mechanism that incentivizes bounded internal "wealth," naturally limiting excessive movement.
  • Parameter-Free Control: Leveraging coin-betting allows the controller to adapt to the scale of target movement without manual tuning of learning rates, increasing its utility for real-world deployment.

Results and Limitations

The authors proved a regret bound of $\tilde{O}(\sqrt{|I|})$ for any time interval $I$, ensuring the controller remains effective even during short, volatile periods. Qualitatively, the controller successfully tracked complex composite signals and demonstrated robustness by converging toward a small error norm when targets stopped moving.

One identified limitation is the "Restart Problem": the hierarchical GC structure can cause periodic performance dips when new intervals activate. While empirical "smoothing" techniques (using the last known good prediction) showed promise in experiments, a full theoretical analysis of these transitions remains a subject for future research. Additionally, while the current analysis assumes open-loop stability, extending this to unstable systems via stabilizing oracles is a planned next step.

Summary updated

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.
BibTeX
@misc{zhang2021adversarial,
  author = {Zhiyu Zhang and Ashok Cutkosky and Ioannis Paschalidis},
  title = {{Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory}},
  year = {2021},
  eprint = {2102.01623},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.01623},
}
Figure