2022/02/11 by Feicheng Wang, Lucas Janson, Wang, Feicheng +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (cs.LG) #Receptor Mechanisms and Signaling #Statistics Theory (math.ST) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2202.05799
openalex publication_date 2022/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The theory of reinforcement learning currently suffers from a mismatch between its empirical performance and the theoretical characterization of its performance, with consequences for, e.g., the understanding of sample efficiency, safety, and robustness. The linear quadratic regulator with unknown dynamics is a fundamental reinforcement learning setting with significant structure in its dynamics and cost function, yet even in this setting there is a gap between the best known regret lower-bound of Ωp(√(T)) and the best known upper-bound of Op(√(T) polylog(T)). The contribution of this paper is to close that gap by establishing a novel regret upper-bound of Op(√(T)). Our proof is constructive in that it analyzes the regret of a concrete algorithm, and simultaneously establishes an estimation error bound on the dynamics of Op(T-1/4) which is also the first to match the rate of a known lower-bound. The two keys to our improved proof technique are (1) a more precise upper- and lower-bound on the system Gram matrix and (2) a self-bounding argument for the expected estimation error of the optimal controller.