Title: Input Perturbations for Adaptive Regulation and Learning,
Abstract: Design of adaptive algorithms for simultaneous regulation and estimation of
MIMO linear dynamical systems is a canonical reinforcement learning problem.
Efficient policies whose regret (i.e. increase in the cost due to uncertainty)
scales at a square-root rate of time have been studied extensively in the
recent literature. Nevertheless, existing strategies are computationally
intractable and require a priori knowledge of key system parameters. The only
exception is a randomized Greedy regulator, for which asymptotic regret bounds
have been recently established. However, randomized Greedy leads to probable
fluctuations in the trajectory of the system, which renders its finite time
regret suboptimal.
This work addresses the above issues by designing policies that utilize input
signals perturbations. We show that perturbed Greedy guarantees non-asymptotic
regret bounds of (nearly) square-root magnitude w.r.t. time. More generally, we
establish high probability bounds on both the regret and the learning accuracy
under arbitrary input perturbations. The settings where Greedy attains the
information theoretic lower bound of logarithmic regret are also discussed. To
obtain the results, state-of-the-art tools from martingale theory together with
the recently introduced method of policy decomposition are leveraged. Beside
adaptive regulators, analysis of input perturbations captures key applications
including remote sensing and distributed control.