Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation

📄 arXiv: 2410.23434v2 📥 PDF

作者: Stefan Stojanovic, Yassir Jedra, Alexandre Proutiere

分类: cs.LG

发布日期: 2024-10-30 (更新: 2024-11-10)

备注: Accepted for presentation at the Conference on Neural Information Processing Systems (NeurIPS) 2024

💡 一句话要点

提出LoRa-PI算法以解决低秩强化学习问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 低秩强化学习 无模型学习 策略迭代 样本复杂度 动态系统

📋 核心要点

  1. 现有方法在学习低秩动态系统中的最优策略时，样本复杂度较高且依赖于矩阵的相干性，限制了其应用。
  2. 论文提出的LoRa-PI算法通过杠杆条目矩阵估计，优化了策略评估过程，降低了样本复杂度。
  3. 实验结果表明，LoRa-PI在样本效率上优于现有方法，能够在更宽松的条件下学习到$ ext{ε}$-最优策略。

📝 摘要（中文）

本文考虑在具有低秩潜在结构的受控动态系统中学习$ ext{ε}$-最优策略的问题。我们提出了LoRa-PI（低秩策略迭代），这是一种无模型学习算法，交替进行策略改进和策略评估。在策略评估阶段，算法通过两阶段程序估计当前策略的（状态，动作）值函数对应的低秩矩阵。首先随机均匀采样矩阵的条目，通过谱方法估计其行和列的杠杆分数。然后利用这些分数提取少量重要的行和列，进一步采样其条目。该算法利用这些新样本通过CUR-like方法完成矩阵估计。我们为这一杠杆矩阵估计程序建立了逐项保证，显著地，这些保证不依赖于矩阵的相干性，而仅依赖于其尖锐性。我们的算法在比以前提出的方法更温和的条件下，实现了$ ext{ε}$-最优策略的学习，样本复杂度为$ ilde{O}( rac{S+A}{ ext{poly}(1-γ)ε^2})$。

🔬 方法详解

问题定义：本文旨在解决在具有低秩潜在结构的受控动态系统中学习$ ext{ε}$-最优策略的问题。现有方法通常需要大量样本，并且对矩阵的相干性有较高的依赖性，限制了其在实际应用中的有效性。

核心思路：论文提出的LoRa-PI算法通过引入杠杆条目矩阵估计，优化了策略评估过程。该方法通过随机采样和谱方法有效地识别重要的行和列，从而减少了所需的样本数量。

技术框架：LoRa-PI算法的整体流程包括两个主要阶段：策略改进和策略评估。在策略评估阶段，首先随机采样矩阵条目，然后利用谱方法计算杠杆分数，最后根据这些分数提取重要行列并进行进一步采样，最终完成低秩矩阵的估计。

关键创新：最重要的技术创新在于引入了杠杆条目矩阵估计方法，该方法的逐项保证不依赖于矩阵的相干性，而是基于其尖锐性。这一创新使得LoRa-PI在样本复杂度上优于现有方法。

关键设计：算法中的关键设计包括随机均匀采样、谱方法的应用以及CUR-like矩阵估计技术。通过这些设计，LoRa-PI能够在更宽松的条件下实现$ ext{ε}$-最优策略的学习。

📊 实验亮点

实验结果显示，LoRa-PI算法在样本复杂度上达到了$ ilde{O}( rac{S+A}{ ext{poly}(1-γ)ε^2})$，显著优于传统方法。该算法在更宽松的条件下成功学习到$ ext{ε}$-最优策略，展示了其在低秩强化学习中的有效性。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、智能制造等需要高效决策的动态系统。LoRa-PI算法的样本效率和适应性使其在实际应用中具有重要价值，能够降低学习成本并提高系统性能。

📄 摘要（原文）

We consider the problem of learning an $\varepsilon$-optimal policy in controlled dynamical systems with low-rank latent structure. For this problem, we present LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. In the latter, the algorithm estimates the low-rank matrix corresponding to the (state, action) value function of the current policy using the following two-phase procedure. The entries of the matrix are first sampled uniformly at random to estimate, via a spectral method, the leverage scores of its rows and columns. These scores are then used to extract a few important rows and columns whose entries are further sampled. The algorithm exploits these new samples to complete the matrix estimation using a CUR-like method. For this leveraged matrix estimation procedure, we establish entry-wise guarantees that remarkably, do not depend on the coherence of the matrix but only on its spikiness. These guarantees imply that LoRa-PI learns an $\varepsilon$-optimal policy using $\widetilde{O}({S+A\over \mathrm{poly}(1-γ)\varepsilon^2})$ samples where $S$ (resp. $A$) denotes the number of states (resp. actions) and $γ$ the discount factor. Our algorithm achieves this order-optimal (in $S$, $A$ and $\varepsilon$) sample complexity under milder conditions than those assumed in previously proposed approaches.