A Bounded Regret Strategy for Linear Dynamics with Unknown Control

Abstract

We consider a simple linear control problem in which a single parameter $b$, describing the effect of the control variable, is unknown and must be learned. We work in the setting of agnostic control: we allow $b$ to be any real number and we do not assume that we have a prior belief about $b$. For any fixed time horizon, we produce a strategy whose expected cost is within a constant factor of the best possible.

minor revisions; 32 pages