The Power of Linear Controllers in LQR Control

Abstract

We consider optimal control in linear dynamical systems from the perspective of regret minimization. We compute the policy regret between three distinct control policies: i) the optimal online policy, whose linear structure is given by the Riccati equations; ii) the optimal offline linear state-feedback policy, which is the best linear state-feedback policy selected in hindsight given the noise sequence; and iii) the optimal offline policy, which selects the globally optimal control actions given the noise sequence. We derive a state-space model for the optimal offline policy and show that it has a recursive form in terms of the optimal online policy and future disturbances. We also show that the cost of the best linear state-feedback policy selected in hindsight converges to the cost of the optimal online policy as the time horizon grows large, and consequently any linear state-feedback policy incurs linear regret relative to the optimal offline policy. We also prove a novel concentration bound on the cost incurred by any linear state-feedback controller; this result may be of independent interest.