Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs

📄 arXiv: 2405.06363v1 📥 PDF

作者: Davide Maran, Alberto Maria Metelli, Matteo Papini, Marcello Restelli

分类: cs.LG, cs.AI

发布日期: 2024-05-10

💡 一句话要点

提出基于卷积投影的强化学习方法，实现连续状态空间MDPs中的最优样本复杂度

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

关键词: 强化学习 连续状态空间 马尔可夫决策过程 样本复杂度 值迭代 函数逼近 调和分析 卷积投影

📋 核心要点

  1. 现有连续状态空间强化学习方法在样本复杂度方面存在瓶颈，尤其是在高维和非光滑MDPs中。
  2. 论文提出一种基于卷积投影的新型强化学习算法，利用正交三角多项式进行函数逼近，并结合扰动最小二乘值迭代。
  3. 该方法在理论上实现了速率最优的样本复杂度，并在不同平滑度假设下，统一了离散化和低秩MDPs两种视角。

📝 摘要（中文）

本文研究了在具有平滑Bellman算子的一般连续状态空间马尔可夫决策过程（MDP）中学习ε-最优策略的问题。通过访问生成模型，并使用正交三角多项式作为特征，执行一个简单的、扰动最小二乘值迭代版本，实现了速率最优的样本复杂度。该解决方案的关键是一种基于调和分析思想的新型投影技术。样本复杂度为$\widetilde{\mathcal{O}}(ε^{-2-d/(ν+1)})$，其中$d$是状态-动作空间的维度，$ν$是平滑度。对于Lipschitz MDPs（$ν=0$）的特殊情况，该结果恢复了离散化方法的最新结果。同时，对于$ν\to\infty$，它恢复并极大地推广了低秩MDP的$\mathcal{O}(ε^{-2})$速率，这更适合回归方法。从这个意义上说，该结果弥合了关于连续空间MDPs的两种流行的但相互冲突的观点之间的差距。

🔬 方法详解

问题定义：论文旨在解决连续状态空间MDPs中强化学习的样本复杂度问题。现有方法，如离散化方法，在高维状态空间中面临维度灾难；而基于回归的方法，如低秩MDP假设，对MDP的结构有较强的限制，适用性有限。因此，如何在更一般的连续状态空间MDPs中实现样本复杂度最优的强化学习是一个挑战。

核心思路：论文的核心思路是利用平滑性假设，通过合适的函数逼近方法，降低学习的难度。具体而言，论文利用正交三角多项式作为基函数，并结合一种新颖的基于卷积的投影技术，将值函数投影到该函数空间中。这种投影方法能够有效地利用MDP的平滑性，从而降低样本复杂度。

技术框架：整体框架是基于值迭代的。首先，利用生成模型采样得到数据；然后，利用最小二乘法估计Bellman算子；接着，利用基于卷积的投影技术，将估计的Bellman算子投影到正交三角多项式空间中；最后，通过迭代更新值函数，直到收敛到最优值函数。算法的关键在于投影步骤，它利用了调和分析的思想，将值函数分解到不同的频率分量上，并根据频率分量的能量大小进行截断，从而实现降维和正则化。

关键创新：最重要的技术创新点是基于卷积的投影技术。与传统的投影方法不同，该方法利用卷积运算来计算投影系数，从而能够更有效地利用MDP的平滑性。此外，该方法还引入了扰动项，以保证算法的稳定性。这种投影方法能够自适应地选择合适的函数空间，从而在不同的平滑度假设下都能实现最优的样本复杂度。

关键设计：关键的设计包括：1) 选择正交三角多项式作为基函数，因为它们具有良好的逼近性质和易于计算的特点；2) 设计基于卷积的投影算子，该算子能够有效地利用MDP的平滑性；3) 引入扰动项，以保证算法的稳定性；4) 选择合适的学习率和迭代次数，以保证算法的收敛性。

📊 实验亮点

论文在理论上证明了所提出的算法具有速率最优的样本复杂度，即$\widetilde{\mathcal{O}}(ε^{-2-d/(ν+1)})$。该结果在Lipschitz MDPs（$ν=0$）的特殊情况下，恢复了离散化方法的最新结果。同时，对于$ν\to\infty$，它恢复并极大地推广了低秩MDP的$\mathcal{O}(ε^{-2})$速率。这意味着该算法在不同的平滑度假设下都能实现最优的性能。

🎯 应用场景

该研究成果可应用于各种连续状态空间下的强化学习任务，例如机器人控制、自动驾驶、资源管理等。通过降低样本复杂度，该方法能够加速强化学习算法的训练过程，并提高学习到的策略的性能。此外，该方法还可以用于分析和理解连续状态空间MDPs的结构，为设计更有效的强化学习算法提供理论指导。

📄 摘要（原文）

We consider the problem of learning an $\varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Given access to a generative model, we achieve rate-optimal sample complexity by performing a simple, \emph{perturbed} version of least-squares value iteration with orthogonal trigonometric polynomials as features. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our~$\widetilde{\mathcal{O}}(ε^{-2-d/(ν+1)})$ sample complexity, where $d$ is the dimension of the state-action space and $ν$ the order of smoothness, recovers the state-of-the-art result of discretization approaches for the special case of Lipschitz MDPs $(ν=0)$. At the same time, for $ν\to\infty$, it recovers and greatly generalizes the $\mathcal{O}(ε^{-2})$ rate of low-rank MDPs, which are more amenable to regression approaches. In this sense, our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.