Controlling unknown linear dynamics with almost optimal regret

Here and in a companion paper, we consider a simple control problem in which the underlying dynamics depend on a parameter a that is unknown and must be learned. In this paper, we assume that a can be any real number and we do not assume that we have a prior belief about a . We seek a control strategy that minimizes a quantity called the regret. Given any \varepsilon>0 , we produce a strategy that minimizes the regret to within a multiplicative factor of (1+\varepsilon) .