  Performance of adaptive control policies is assessed through the regret with
respect to the optimal regulator, which reflects the increase in the operating
cost due to uncertainty about the dynamics parameters. However, available
results in the literature do not provide a quantitative characterization of the
effect of the unknown parameters on the regret. Further, there are problems
regarding the efficient implementation of some of the existing adaptive
policies. Finally, results regarding the accuracy with which the system's
parameters are identified are scarce and rather incomplete.
  This study aims to comprehensively address these three issues. First, by
introducing a novel decomposition of adaptive policies, we establish a sharp
expression for the regret of an arbitrary policy in terms of the deviations
from the optimal regulator. Second, we show that adaptive policies based on
slight modifications of the Certainty Equivalence scheme are efficient.
Specifically, we establish a regret of (nearly) square-root rate for two
families of randomized adaptive policies. The presented regret bounds are
obtained by using anti-concentration results on the random matrices employed
for randomizing the estimates of the unknown parameters. Moreover, we study the
minimal additional information on dynamics matrices that using them the regret
will become of logarithmic order. Finally, the rates at which the unknown
parameters of the system are being identified are presented.
