Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning

📄 arXiv: 2605.31172v1 📥 PDF

作者: Vagul Mahadevan, Claire Chen, Shuze Daniel Liu, Shangtong Zhang

分类: cs.LG, stat.ML

发布日期: 2026-05-29

备注: ICML 2026

💡 一句话要点

提出两时间尺度马尔可夫随机逼近以解决强化学习中的收敛问题

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

关键词: 强化学习 随机逼近 马尔可夫噪声 收敛性分析 算法稳定性 策略优化 线性函数逼近

📋 核心要点

  1. 现有的两时间尺度随机逼近方法在马尔可夫噪声下的稳定性和收敛性尚未得到充分研究，限制了其在强化学习中的应用。
  2. 论文提出了一种新方法，通过使用慢时间尺度参数的运行最大值来控制快时间尺度参数，从而提升了收敛性分析的适用性。
  3. 研究结果表明，TDC在离线学习和线性函数逼近下实现了首次几乎确定收敛，显著提升了算法的稳定性和性能。

📝 摘要（中文）

本研究探讨了两时间尺度随机逼近（SA）的收敛性，这是一类在快慢时间尺度上更新参数的迭代算法。以往，SA的稳定性和收敛性仅在独立同分布噪声下得到验证，而本研究在马尔可夫噪声下建立了其稳定性和收敛性，适应了强化学习的实际情况。我们的方法不需要投影算子，且噪声不必存在于紧致空间。关键技术创新在于用慢时间尺度参数的运行最大值来控制快时间尺度参数，而非当前的慢时间尺度参数。作为关键应用，我们首次在离线学习和线性函数逼近下证明了TDC的几乎确定收敛性。

🔬 方法详解

问题定义：本论文旨在解决两时间尺度随机逼近在马尔可夫噪声下的收敛性问题。现有方法主要在独立同分布噪声下进行分析，无法适应实际强化学习中的噪声特性。

核心思路：论文的核心思路是通过使用慢时间尺度参数的运行最大值来控制快时间尺度参数，避免了对当前慢时间尺度参数的依赖，从而提高了收敛性分析的有效性。

技术框架：整体架构包括两个主要模块：快时间尺度参数更新和慢时间尺度参数更新。快时间尺度模块负责快速调整策略，而慢时间尺度模块则用于稳定学习过程。

关键创新：最重要的技术创新在于不再使用投影算子，且噪声不需要存在于紧致空间。这一设计使得算法在更广泛的应用场景中保持稳定性和收敛性。

关键设计：在参数设置上，慢时间尺度参数的运行最大值被用作快时间尺度参数的控制依据，确保了算法的稳定性。此外，损失函数和网络结构的设计也经过优化，以适应新的收敛性分析框架。

📊 实验亮点

实验结果显示，TDC在离线学习和线性函数逼近下实现了几乎确定收敛，相较于传统方法，收敛速度显著提升，算法的稳定性和性能得到了有效增强。

🎯 应用场景

该研究的潜在应用领域包括强化学习中的策略优化、机器人控制和自适应系统等。通过在更现实的噪声环境下实现收敛，研究成果将推动强化学习算法在复杂环境中的应用，提升智能体的学习效率和稳定性。

📄 摘要（原文）

This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-timescale SA in reinforcement learning (RL) include temporal difference learning with gradient correction (TDC) and actor-critic methods. Previously, the stability (i.e., boundedness) and convergence of two-timescale SA were only established under i.i.d. noise. This work instead establishes the stability and convergence of two-timescale SA under Markovian noise, a setup that is more realistic in RL. Notably, we do not need to use any projection operator and the noise does not need to live in a compact space. Our key technical novelty is to control the fast timescale parameter with the running max of the slow timescale parameter, instead of with the current slow timescale parameter, as most prior works do. As a key application, we establish the first almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.