Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu University of California, Berkeley
Abstract
We consider adaptive control of the Linear Quadratic Regulator (LQR), where an unknown linear system is controlled subject to quadratic costs. Leveraging recent developments in the estimation of linear systems and in robust controller synthesis, we present the first provably polynomial time algorithm that provides high probability guarantees of sub-linear regret on this problem. We further study the interplay between regret minimization and parameter estimation by proving a lower bound on the expected regret in terms of the exploration schedule used by any algorithm. Finally, we conduct a numerical study comparing our robust adaptive algorithm to other methods from the adaptive LQR literature, and demonstrate the flexibility of our proposed method by extending it to a demand forecasting problem subject to state constraints.
中文速览
线性二次型调节器（LQR）在系统参数未知时如何边学边控、同时把性能损失压到最低，这是自适应控制领域长期悬而未决的难题。已有方法要么依赖无法验证的假设，要么核心步骤需要求解非凸优化而在计算上不可行。这篇论文结合线性系统估计、鲁棒控制综合和"系统层级综合"（System Level Synthesis，SLS）框架，提出了第一个在多项式时间内可运行、且以高概率保证次线性遗憾（regret）的自适应LQR算法——核心每步只需求解规模随时间对数增长的半正定规划，遗憾界达到 $\widetilde{\mathcal{O}}(T^{2/3})$，并通过配套下界证明该分析在对数因子意义下是紧的。这项工作填补了自适应LQR领域"既有理论保证又计算可行"的空白，同时揭示了遗憾最小化与系统参数估计速率之间的基本权衡关系，具有重要的理论价值和实际参考意义。
原文 arXiv:1805.09388;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1805.09388v1