Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory

Zhiyu Zhang, Ashok Cutkosky, Ioannis Ch. 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.

TL;DR

This research bridges the gap between online learning and control theory by introducing a "strongly adaptive" controller capable of tracking unpredictable, adversarial targets. By developing a new online learning algorithm that accounts for "movement costs" (the physical penalty of changing control actions), the authors provide a controller that guarantees high performance over any time interval, even when the target trajectory is complex or reactive.

Problem Statement: Tracking in Adversarial Environments

In classical control theory, "tracking" usually involves following a reference trajectory that is either known in advance or generated by a predictable linear system. However, real-world scenarios—like a drone chasing an evasive target or a robot navigating a changing environment—often involve "adversarial" targets that are unpredictable and may even react to the controller's actions.

While recent advances have applied Online Learning (OL) to control, most focus on regulation (keeping the system at a fixed state, like zero) rather than tracking. Existing tracking methods often struggle with two conflicting requirements:

  1. Adaptivity: The controller must move quickly to respond to new information.
  2. Movement Cost: In physical systems, changing control actions rapidly is "expensive" or even damaging.

Standard adaptive algorithms often exhibit "wild" movements that are impractical for control. This paper seeks a way to achieve "strong adaptivity"—meaning the controller performs well over every sub-interval of time—while respecting these movement constraints.

Methodology

The authors build their solution through a three-tiered hierarchical approach, reducing the complex control problem into manageable online learning sub-problems.

The hierarchical reduction from adversarial tracking control to strongly adaptive online learning.

1. OLO with Movement Cost

They first create a "comparator-adaptive" algorithm for Online Linear Optimization (OLO). Using a technique called coin-betting, they design a "parameter-free" algorithm. Unlike standard Gradient Descent, which requires tuning a learning rate based on the unknown target, this algorithm automatically matches the performance of the best-tuned strategy in hindsight.

2. Strongly Adaptive OCOM

They extend this to Online Convex Optimization with Memory (OCOM). To achieve "strong adaptivity," the algorithm maintains a hierarchy of subroutines running on different time scales.

Geometric-Covering (GC) intervals used to achieve strong adaptivity across different time scales.

These Geometric-Covering (GC) intervals allow the system to "forget" old, irrelevant data and quickly pivot when the target changes behavior. By running instances of the OLO algorithm on these overlapping intervals, the meta-algorithm ensures low regret on any arbitrary time window.

3. The Reduction

Finally, they provide a mathematical reduction that transforms the adversarial tracking control problem into the OCOM framework. They use a "history truncation" trick: since linear systems are stable, old actions have a diminishing effect on the current state. This allows them to treat the control problem as a sequence of local optimization steps.

Key Insights

  • The "Tracking" Duality: The authors exploit a symmetry: the concept of "tracking" in online learning (comparing yourself to a sequence of changing experts) is the perfect mathematical tool for "tracking" in control (following a moving physical target).
  • Parameter-Free is Key: In adversarial settings, you don't know how fast or far the target will move. By using a "comparator-adaptive" approach, the controller doesn't need to be pre-tuned to the target's specific "speed"; it learns the scale of the movement on the fly.
  • Memory Matters: Because physical states depend on previous actions, the "memory" component of their OCOM algorithm is essential. It ensures that the controller accounts for the "momentum" of the system.

Results and Evaluation

The authors prove a regret bound of $\tilde{O}(\sqrt{|I|})$ for any time interval $I$. This means that on any slice of time, the controller’s performance is nearly as good as the best possible fixed action for that specific slice.

In numerical simulations of 1D and 2D linear dynamical systems:

  • Robustness: Unlike previous adaptive OLO algorithms that could have exponentially large per-step movements, this new algorithm keeps movements bounded and predictable.
  • Adaptivity: The controller successfully tracked complex composite signals (combinations of sine waves and square waves). Even when the target made sudden, sharp jumps, the strongly adaptive nature of the algorithm allowed it to recover and resume tracking much faster than non-adaptive methods.

Limitations

  • Known Dynamics: The current framework assumes the system matrices ($A_t, B_t$) are known.
  • Stability Assumptions: The reduction relies on the system being "open-loop stable" (or having an oracle-provided stabilizing controller).
  • Computational Overhead: Running multiple subroutines across GC intervals increases the computational cost per step, which might be a constraint for high-frequency real-time robotics.

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 Ch. 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},
}

Loading related content...

Figure