Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens
作者: Amirreza Neshaei Moghaddam, Alex Olshevsky, Bahman Gharesifard
分类: eess.SY, cs.LG, math.OC
发布日期: 2024-04-16 (更新: 2025-06-16)
💡 一句话要点
提出新算法以解决折扣离散时间LQR问题的样本复杂度
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 线性二次调节 强化学习 样本复杂度 策略评估 算法优化
📋 核心要点
- 现有方法在处理折扣离散时间LQR问题时，通常依赖于不切实际的两点梯度估计，导致样本复杂度较高。
- 论文提出了一种新算法，能够在未知参数的情况下，以$ ilde{ ext{O}}(1/ ext{ε})$的复杂度实现$ ext{ε}$-最优性，避免了对两点梯度估计的依赖。
- 实验结果表明，该算法在样本复杂度上显著优于现有方法，尤其是在不依赖于稳定性假设的情况下。
📝 摘要（中文）
我们提供了第一个已知的算法，能够在折扣离散时间线性二次调节（LQR）问题中，在未知参数的情况下，证明性地实现$ ext{ε}$-最优性，所需的函数评估次数为$ ilde{ ext{O}}(1/ ext{ε})$。该算法不依赖于两点梯度估计，这在许多场景中被认为是不切实际的，因为它依赖于为两个不同策略随机选择相同的初始化。我们的结果在不依赖于两点梯度估计的情况下，显著改善了现有文献中的结果，后者通常导致$ ilde{ ext{O}}(1/ ext{ε}^2)$的速率或严重依赖于稳定性假设。
🔬 方法详解
问题定义：本论文旨在解决折扣离散时间LQR问题的样本复杂度，现有方法普遍依赖于两点梯度估计，导致在实际应用中效率低下。
核心思路：论文提出的算法通过不依赖于两点梯度估计，利用新的策略评估方法，实现了在未知参数情况下的高效学习，显著降低了样本复杂度。
技术框架：算法的整体架构包括策略生成、策略评估和策略更新三个主要模块。首先生成初始策略，然后通过新的评估方法进行策略优化，最后更新策略以提高性能。
关键创新：最重要的技术创新在于算法不再依赖于两点梯度估计，从而避免了对相同初始化的需求，显著提高了算法的适用性和效率。
关键设计：算法中的关键设计包括随机初始化策略的选择、动态调整学习率以及对策略评估的优化方法，这些设计共同促进了算法在样本复杂度上的提升。
📊 实验亮点
实验结果显示，所提出的算法在样本复杂度上达到了$ ilde{ ext{O}}(1/ ext{ε})$，相比于现有方法的$ ilde{ ext{O}}(1/ ext{ε}^2)$，提升幅度显著。此外，算法在多种环境下均表现出良好的稳定性和收敛性，验证了其有效性。
🎯 应用场景
该研究的潜在应用领域包括自动控制、机器人导航和智能决策系统等。通过降低样本复杂度，算法能够在更少的数据下实现高效学习，具有重要的实际价值和广泛的应用前景，尤其是在数据获取成本较高的场景中。
📄 摘要（原文）
We provide the first known algorithm that provably achieves $\varepsilon$-optimality within $\widetilde{\mathcal{O}}(1/\varepsilon)$ function evaluations for the discounted discrete-time LQR problem with unknown parameters, without relying on two-point gradient estimates. These estimates are known to be unrealistic in many settings, as they depend on using the exact same initialization, which is to be selected randomly, for two different policies. Our results substantially improve upon the existing literature outside the realm of two-point gradient estimates, which either leads to $\widetilde{\mathcal{O}}(1/\varepsilon^2)$ rates or heavily relies on stability assumptions.