Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

技术摘要：基于非单调包含关系的非凸稀疏强化学习

问题陈述
强化学习（RL）在处理高维状态空间中的 Q 函数近似时，经常面临“维度之咒”。虽然线性函数近似是一种标准的补救措施，但它在近似精度与计算复杂度之间引入了权衡。通过稀疏建模进行特征选择是减轻这一问题的常用策略，然而，依赖 $\ell_1$ 范数正则化（例如 LARS-TD、带有 $\ell_1$ 的 LSTD）的传统方法存在估计偏差，即系统性地低估大振幅分量。此外，在数据固定且可能存在噪声的离线（batch）强化学习设置中，对无关特征和离群值的鲁棒性至关重要。虽然非凸惩罚项（如极小极大凹（Minimax Concave, MC）惩罚）已被提议用于稀疏回归以减少偏差，但由于其导致的优化问题非凸性，将其应用于强化学习的研究仍处于空白阶段，因为这种非凸性破坏了标准算子分裂方法所需的单调性假设。

方法论
本文提出了一种用于强化学习特征选择的新型离线算法，该算法将非凸投影极小极大凹（Projective Minimax Concave, PMC）惩罚集成到最小二乘时序差分（LSTD）公式中。

1. 问题重构： 作者将策略评估问题表述为寻找一个映射的固定点，该映射最小化由 PMC 惩罚正则化的最小二乘时序差分误差。与标准的 LSTD 不同，该目标函数是非凸的。
2. 算子分裂： 通过利用 PMC 惩罚的弱凸性，将该固定点问题重构为寻找两个算子之和的零点，其中一个为单调 Lipschitz 算子，另一个为假设单调（hypomonotone）算子。这使得该问题属于非单调包含问题（non-monotone inclusions）的范畴。
3. 算法求解： 作者采用前向-反射-后向分裂（Forward-Reflected-Backward Splitting, FRBS）法来求解此包含问题。一项关键的技术贡献是推导出了假设单调部分（涉及软阈值算子）的闭式表达式，这使得算法在无需辅助变量的情况下依然具有可操作性。
4. 超参数微调： 该方法引入了一个可调超参数 $q$，用于控制 PMC 惩罚效应所作用的子空间 $M$。这推广了原始 PMC 的定义，使得即使在输入 Gram 矩阵具有极小正特征值的情况下，也能优化惩罚项的性能。

核心贡献
本文主要有四项贡献：

• 强化学习算法： 引入了一种高效的离线强化学习特征选择方法，将非凸 PMC 惩罚整合进 LSTD 中。这解决了 $\ell_1$ 正则化方法固有的估计偏差问题。
• 理论扩展： 将 FRBS 方法的收敛性分析扩展到了更广泛的非单调包含问题类。具体而言，本文确立了：
  • 李雅普诺夫稳定性（Lyapunov Stability）： 在温和条件下，证明了迭代过程是拟 Fejér 单调的，从而确保了极限点的存在性和稳定性。
  • 精确收敛性： 在弱 Minty 变分不等式（MVI）假设下，证明了序列精确收敛于解。
• 广义 PMC 惩罚： 通过允许子空间 $M$ 由可调参数 $q$ 控制（而非固定为零空间的正交补），对 PMC 惩罚进行了泛化。这防止了在病态设置下的性能下降。
• 误差界限： 提供了由所提近似策略迭代（API）方案生成的策略的误差界限，将近似误差与 Q 函数估计误差联系起来。

实验结果
在三个基准强化学习任务（50 状态链行走、山路车和 Acrobot）上进行了数值测试。将所提方法与最先进的离线特征选择方法（包括 LSTD、LARS-TD 和基准追踪去噪法 BPDN）进行了对比。

• 性能： 所提方法显著优于竞争对手，特别是在存在大量噪声或无关特征的情景下。在山路车和 Acrobot 任务中，该方法实现了最高的成功率和最短的平均到达目标步数。
• 偏差缓解： 结果表明，该方法有效地缓解了与 $\ell_1$ 范数正则化相关的估计偏差，从而获得了更准确的 Q 函数估计。
• 超参数敏感性： 在 50 状态链行走实验中显示，超参数 $q$ 对性能有显著影响。适中的 $q$ 取值范围能产生最低的归一化均方误差（NMSE），而极端值会因无法充分去偏或迫使惩罚项趋近于有偏的 $\ell_1$ 范数而导致性能下降。

意义
本文声称为在强化学习中应用非凸惩罚项提供了严谨的理论基础，而此前由于收敛性担忧，此类方法在强化学习领域一直较少被采用。通过建立 FRBS 在非单调设置下的收敛保证，这项工作架起了非凸稀疏建模理论与实际强化学习应用之间的桥梁。作者断言，其方法提供了一种稳健的凸正则化替代方案，能够在不牺牲理论收敛保证的前提下，在高维、多噪声环境中实现卓越的特征选择和策略性能。本研究通过提供弱 MVI 假设下的完整收敛证明以及广泛的数值验证，对初步的会议版本进行了扩展。