Non-Stochastic Control with Bandit Feedback

Abstract

We study the problem of controlling a linear dynamical system with adversarial perturbations where the only feedback available to the controller is the scalar loss, and the loss function itself is unknown. For this problem, with either a known or unknown system, we give an efficient sublinear regret algorithm. The main algorithmic difficulty is the dependence of the loss on past controls. To overcome this issue, we propose an efficient algorithm for the general setting of bandit convex optimization for loss functions with memory, which may be of independent interest.

References in corpus (12)

• Near optimal finite time identification of arbitrary linear dynamical systems
• Logarithmic Regret for Online Control
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Model-Free Linear Quadratic Control via Reduction to Expert Prediction
• Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
• Learning Linear Dynamical Systems with Semi-Parametric Least Squares
• Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret
• Online Linear Quadratic Control
• Online convex optimization in the bandit setting: gradient descent without a gradient
• The Nonstochastic Control Problem
• Regret Minimization in Partially Observable Linear Quadratic Control
• Online Convex Optimization Against Adversaries with Memory and Application to Statistical Arbitrage

Cited by in corpus (4)

• Non-stationary Online Learning with Memory and Non-stochastic Control
• Modes of Homogeneous Gradient Flows
• Generating Adversarial Disturbances for Controller Verification
• Geometric Exploration for Online Control