Black-Box Control for Linear Dynamical Systems

Abstract

We consider the problem of controlling an unknown linear time-invariant dynamical system from a single chain of black-box interactions, with no access to resets or offline simulation. Under the assumption that the system is controllable, we give the first efficient algorithm that is capable of attaining sublinear regret in a single trajectory under the setting of online nonstochastic control. This resolves an open problem on the stochastic LQR problem, and in a more challenging setting that allows for adversarial perturbations and adversarially chosen and changing convex loss functions. We give finite-time regret bounds for our algorithm on the order of $2^{\tilde{O}(\mathcal{L})}+\tilde{O}(\text{poly}(\mathcal{L})T^{2/3})$ for general nonstochastic control, and $2^{\tilde{O}(\mathcal{L})}+\tilde{O}(\text{poly}(\mathcal{L})\sqrt{T})$ for black-box LQR, where $\mathcal{L}$ is the system size which is an upper bound on the dimension. The crucial step is a new system identification method that is robust to adversarial noise, but incurs exponential cost. To complete the picture, we investigate the complexity of the online black-box control problem, and give a matching lower bound of $2^{\Omega (\mathcal{L})}$ on the regret, showing that the additional exponential cost is inevitable. This lower bound holds even in the noiseless setting, and applies to any, randomized or deterministic, black-box control method.

References in corpus (7)

• Near optimal finite time identification of arbitrary linear dynamical systems
• Improper Learning for Non-Stochastic Control
• Online Control with Adversarial Disturbances
• Logarithmic Regret for Online Control
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Naive Exploration is Optimal for Online LQR
• Regret Minimization in Partially Observable Linear Quadratic Control

Cited by in corpus (7)

• Deluca -- A Differentiable Control Library: Environments, Methods, and Benchmarking
• Online Robust Control of Nonlinear Systems with Large Uncertainty
• Streaming Linear System Identification with Reverse Experience Replay
• Improper Reinforcement Learning with Gradient-based Policy Optimization
• Generating Adversarial Disturbances for Controller Verification
• Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with $\sqrt{T}$ Regret
• Geometric Exploration for Online Control