Logarithmic Regret for Adversarial Online Control

Abstract

We introduce a new algorithm for online linear-quadratic control in a known system subject to adversarial disturbances. Existing regret bounds for this setting scale as $\sqrt{T}$ unless strong stochastic assumptions are imposed on the disturbance process. We give the first algorithm with logarithmic regret for arbitrary adversarial disturbance sequences, provided the state and control costs are given by known quadratic functions. Our algorithm and analysis use a characterization for the optimal offline control law to reduce the online control problem to (delayed) online learning with approximate advantage functions. Compared to previous techniques, our approach does not need to control movement costs for the iterates, leading to logarithmic regret.

arXiv commentICML 2020

References in corpus (7)

• Continuous control with deep reinforcement learning
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• Improper Learning for Non-Stochastic Control
• Online Control with Adversarial Disturbances
• Logarithmic Regret for Online Control
• Online Convex Optimization in Adversarial Markov Decision Processes

Cited by in corpus (17)

• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Non-stationary Online Learning with Memory and Non-stochastic Control
• Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon
• Regret-optimal control in dynamic environments
• The Power of Predictions in Online Control
• Making Non-Stochastic Control (Almost) as Easy as Stochastic
• Regret-optimal measurement-feedback control
• Online Linear Quadratic Tracking with Regret Guarantees
• Online Optimal Control with Affine Constraints
• An Iterative Riccati Algorithm for Online Linear Quadratic Control
• Bandit Linear Control
• When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?
• Lazy OCO: Online Convex Optimization on a Switching Budget
• Exact Asymptotics for Linear Quadratic Adaptive Control
• Online Learning Robust Control of Nonlinear Dynamical Systems
• PAC-Bayesian bounds for learning LTI-ss systems with input from empirical loss
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory