Linear Quadratic Regulators (LQR) achieve enormous successful real-world
applications. Very recently, people have been focusing on efficient learning
algorithms for LQRs when their dynamics are unknown. Existing results
effectively learn to control the unknown system using number of episodes
depending polynomially on the system parameters, including the ambient
dimension of the states. These traditional approaches, however, become
inefficient in common scenarios, e.g., when the states are high-resolution
images. In this paper, we propose an algorithm that utilizes the intrinsic
system low-rank structure for efficient learning. For problems of rank-$m$, our
algorithm achieves a $K$-episode regret bound of order $\widetilde{O}(m^{3/2}
K^{1/2})$. Consequently, the sample complexity of our algorithm only depends on
the rank, $m$, rather than the ambient dimension, $d$, which can be
orders-of-magnitude larger.

本篇论文提出一种基于系统内在低秩结构进行高效学习的算法，使样本复杂度只依赖于秩而非环境维度，同时获得了关于 K 的次线性复杂度，在 LQR 问题的应用中取得了较好效果。