Making Non-Stochastic Control (Almost) as Easy as Stochastic

Abstract

Recent literature has made much progress in understanding \emph{online LQR}: a modern learning-theoretic take on the classical control problem in which a learner attempts to optimally control an unknown linear dynamical system with fully observed state, perturbed by i.i.d. Gaussian noise. It is now understood that the optimal regret on time horizon $T$ against the optimal control law scales as $\tilde{\Theta }(\sqrt{T})$. In this paper, we show that the same regret rate (against a suitable benchmark) is attainable even in the considerably more general non-stochastic control model, where the system is driven by \emph{arbitrary adversarial} noise (Agarwal et al. 2019). In other words, \emph{stochasticity confers little benefit in online LQR}. We attain the optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret when the dynamics are unknown to the learner, and $\mathrm{poly}(\log T)$ regret when known, provided that the cost functions are strongly convex (as in LQR). Our algorithm is based on a novel variant of online Newton step (Hazan et al. 2007), which adapts to the geometry induced by possibly adversarial disturbances, and our analysis hinges on generic "policy regret" bounds for certain structured losses in the OCO-with-memory framework (Anava et al. 2015). Moreover, our results accomodate the full generality of the non-stochastic control setting: adversarially chosen (possibly non-quadratic) costs, partial state observation, and fully adversarial process and observation noise.

References in corpus (11)

• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis
• Online Control with Adversarial Disturbances
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Logarithmic Regret for Online Control
• Naive Exploration is Optimal for Online LQR
• Logarithmic Regret for Adversarial Online Control
• Learning Linear Dynamical Systems with Semi-Parametric Least Squares
• Regret Minimization in Partially Observable Linear Quadratic Control
• Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
• Online learning over a finite action set with limited switching

Cited by in corpus (7)

• Adaptive Regret for Control of Time-Varying Dynamics
• Non-stationary Online Learning with Memory and Non-stochastic Control
• A Regret Minimization Approach to Iterative Learning Control
• When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?
• Learning from Censored and Dependent Data: The case of Linear Dynamics
• Geometric Exploration for Online Control
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory