On Double Descent in Reinforcement Learning with LSTD and Random Features

📄 arXiv: 2310.05518v4 📥 PDF

作者: David Brellmann, Eloïse Berthier, David Filliat, Goran Frehse

分类: cs.LG, cs.AI, stat.ML

发布日期: 2023-10-09 (更新: 2024-02-18)

💡 一句话要点

提出双重下降现象以分析强化学习中的LSTD算法性能

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

关键词: 强化学习 时间差分算法 过参数化 双重下降 LSTD算法 随机特征 正则化

📋 核心要点

  1. 现有强化学习方法对神经网络规模的影响尚不明确，尤其是在过参数化情况下的表现不佳。
  2. 本文提出通过分析参数与状态比率来理解LSTD算法的性能，并定义过参数化的条件。
  3. 实验结果表明，理论推导与实际数据高度一致，验证了双重下降现象的存在及其影响因素。

📝 摘要（中文）

时间差分（TD）算法在深度强化学习（RL）中被广泛应用，其性能受到神经网络规模的显著影响。尽管在监督学习中，过参数化的机制及其优势已被充分理解，但在RL中的情况仍不明确。本文通过理论分析网络规模与$l_2$正则化对性能的影响，识别出参数数量与访问状态数量的比率作为关键因素，并定义当该比率大于1时为过参数化。此外，观察到双重下降现象，即在参数/状态比率为1附近性能突然下降。利用随机特征和懒惰训练机制，研究了正则化最小二乘时间差分（LSTD）算法的渐近行为，推导出包含修正项的经验和真实均方贝尔曼误差（MSBE）的确定性极限，这些修正项与双重下降现象相关。数值实验与理论预测高度一致。

🔬 方法详解

问题定义：本文旨在解决强化学习中LSTD算法性能受网络规模影响的不确定性，特别是在过参数化情况下的表现问题。现有方法未能充分解释这一现象。

核心思路：通过理论分析参数数量与访问状态数量的比率，识别出该比率对算法性能的关键影响，并定义过参数化的条件。同时，观察到双重下降现象，提供了新的视角来理解RL中的学习动态。

技术框架：研究采用随机特征和懒惰训练机制，分析正则化LSTD算法的渐近行为，推导出均方贝尔曼误差的确定性极限，包含修正项。整体框架包括理论推导、实验验证和参数分析三个主要阶段。

关键创新：最重要的创新在于识别并定义了参数与状态比率的双重下降现象，揭示了在强化学习中网络规模对性能的复杂影响，这与传统监督学习中的理解有本质区别。

关键设计：论文中设置了$l_2$正则化参数，并分析了未访问状态数量对修正项的影响，确保在理论推导和实验中保持一致性。

🖼️ 关键图片

img_0

📊 实验亮点

实验结果显示，在不同的参数/状态比率下，算法性能的变化与理论预测高度一致，尤其在比率接近1时，性能出现显著下降。通过调整$l_2$正则化，修正项的影响得以消除，验证了理论分析的有效性。

🎯 应用场景

该研究为强化学习算法的设计提供了新的理论基础，尤其是在神经网络规模和正则化策略的选择上。其结果可应用于机器人控制、游戏智能体和其他需要高效学习的领域，推动智能系统的性能提升。

📄 摘要（原文）

Temporal Difference (TD) algorithms are widely used in Deep Reinforcement Learning (RL). Their performance is heavily influenced by the size of the neural network. While in supervised learning, the regime of over-parameterization and its benefits are well understood, the situation in RL is much less clear. In this paper, we present a theoretical analysis of the influence of network size and $l_2$-regularization on performance. We identify the ratio between the number of parameters and the number of visited states as a crucial factor and define over-parameterization as the regime when it is larger than one. Furthermore, we observe a double descent phenomenon, i.e., a sudden drop in performance around the parameter/state ratio of one. Leveraging random features and the lazy training regime, we study the regularized Least-Square Temporal Difference (LSTD) algorithm in an asymptotic regime, as both the number of parameters and states go to infinity, maintaining a constant ratio. We derive deterministic limits of both the empirical and the true Mean-Squared Bellman Error (MSBE) that feature correction terms responsible for the double descent. Correction terms vanish when the $l_2$-regularization is increased or the number of unvisited states goes to zero. Numerical experiments with synthetic and small real-world environments closely match the theoretical predictions.