Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory
arXiv:2102.01623
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.
AISTATS 2022
References in corpus (16)
- Slow Learners are Fast
- Online Learning: A Modern Introduction Using Convex Optimization
- Improper Learning for Non-Stochastic Control
- Logarithmic Regret for Online Control
- Logarithmic Regret for Adversarial Online Control
- Online Optimization with Memory and Competitive Control
- An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays
- Adaptive Regret of Convex and Smooth Functions
- Adaptive Regret for Control of Time-Varying Dynamics
- Lipschitz and Comparator-Norm Adaptivity in Online Learning
- Non-stationary Online Learning with Memory and Non-stochastic Control
- Minimizing Dynamic Regret and Adaptive Regret Simultaneously
- Strongly Adaptive Online Learning
- The Power of Predictions in Online Control
- Making Non-Stochastic Control (Almost) as Easy as Stochastic
- Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications