Learning Linear-Quadratic Regulators Efficiently with only T𝑇\sqrt{T} Regret
Alon Cohen Technion—Israel Inst. of Technology and Google Tel Aviv; Tomer Koren Google Brain, Mountain View; Yishay Mansour Tel-Aviv University and Google Tel Aviv;
Abstract
We present the first computationally-efficient algorithm with $\smash{\widetilde{O}}(\sqrt{T})$ regret for learning in Linear Quadratic Control systems with unknown dynamics. By that, we resolve an open question of Abbasi-Yadkori and Szepesvári (2011) and Dean, Mania, Matni, Recht, and Tu (2018).
中文速览
在动态系统控制领域，有一个经典难题：当控制器完全不知道系统的动力学参数（即线性二次调节器 Linear Quadratic Regulator, LQR 中的矩阵 A★ 和 B★）时，如何在边学习边控制的过程中把"后悔值"（regret，即与最优策略的代价差距）压到尽可能低？此前的算法要么能达到理论上最优的 √T 后悔界但计算上极其低效（每步需解一个非凸优化），要么计算高效但后悔界只有 T^(2/3)，这一矛盾在十年间悬而未决。本文通过将 LQR 规划问题重新表述为一个凸半定规划（semidefinite program, SDP），设计出首个在计算上高效且后悔界达到 Õ(√T) 的自适应控制算法——算法在每轮只需求解一系列 SDP 松弛，用"乐观面对不确定性"的策略同时平衡探索与利用，随着样本积累松弛逐步收紧、策略逐步逼近最优。这一结果同时解决了 Abbasi-Yadkori & Szepesvári（2011）和 Dean 等人（2018）明确提出的公开问题，为自适应控制与在线学习的交叉领域树立了新的理论基准。
原文 arXiv:1902.06223;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1902.06223v2