Statistical Efficiency of Distributional Temporal Difference Learning and Freedman's Inequality in Hilbert Spaces

📄 arXiv: 2403.05811v4 📥 PDF

作者: Yang Peng, Liangyu Zhang, Zhihua Zhang

分类: stat.ML, cs.LG

发布日期: 2024-03-09 (更新: 2025-01-16)

💡 一句话要点

提出非参数分布式时序差分学习以优化策略评估

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

关键词: 分布式强化学习 时序差分学习 统计效率 马尔可夫决策过程 希尔伯特空间 策略评估 样本复杂度 弗里德曼不等式

📋 核心要点

  1. 分布式强化学习中的策略评估面临高样本复杂度和估计误差的问题，现有方法难以满足高效性要求。
  2. 提出非参数分布式时序差分学习（NTD），通过引入新的统计分析框架，降低样本复杂度并提高估计精度。
  3. 研究结果表明，NTD和CTD在马尔可夫环境下的样本复杂度达到了最新的统计结果，具有显著的理论和实践价值。

📝 摘要（中文）

分布式强化学习（DRL）在多个领域取得了实证成功。本文聚焦于分布式策略评估的非渐近统计速率，提出了非参数分布式时序差分学习（NTD）。我们证明，对于折扣因子为γ的无限期表格马尔可夫决策过程，NTD在高概率下需要$ ilde{O}( ilde{ heta}^{-2}μ_{ ext{min}}^{-1}(1-γ)^{-3})$次与环境的交互才能达到$ ilde{ heta}$-最优估计。此外，我们还重新审视了分类分布式时序差分学习（CTD），并展示了在1-瓦瑟斯坦距离下相同的非渐近收敛界限。我们扩展了分析到更一般的马尔可夫数据生成过程，并提出了NTD和CTD的方差减少变体，证明它们在1-瓦瑟斯坦距离下的样本复杂度界限与经典策略评估的最新统计结果相匹配。为实现精确的统计速率，我们建立了在希尔伯特空间中的新弗里德曼不等式。

🔬 方法详解

问题定义：本文旨在解决分布式强化学习中策略评估的样本复杂度高和估计误差大的问题。现有的分布式时序差分学习方法在统计效率上存在不足，难以在有限的样本下实现高精度的策略评估。

核心思路：论文提出非参数分布式时序差分学习（NTD），通过引入新的统计框架和不等式，优化样本复杂度和估计精度。设计上，NTD利用生成模型来有效地估计策略的返回分布。

技术框架：整体架构包括数据生成过程的建模、NTD算法的设计和统计分析。主要模块包括环境交互、样本收集、估计更新和收敛性分析。

关键创新：最重要的技术创新在于提出了新的弗里德曼不等式，适用于希尔伯特空间，为无限维在线学习问题的统计分析提供了新的工具。这一创新使得NTD和CTD在样本复杂度上达到了最优界限。

关键设计：在设计中，NTD和CTD的样本复杂度界限为$ ilde{O}( ilde{ heta}^{-2} μ_{ ext{min}}^{-1}(1-γ)^{-3})$，并在马尔可夫环境下引入了方差减少的变体，确保了在1-瓦瑟斯坦距离下的收敛性和效率。

📊 实验亮点

实验结果表明，NTD和CTD在马尔可夫环境下的样本复杂度达到了$ ilde{O}( ilde{ heta}^{-2} μ_{ ext{min}}^{-1}(1-γ)^{-3})$，与经典策略评估的最新统计结果相匹配，展示了显著的性能提升。这一结果为分布式强化学习提供了新的理论基础和实践指导。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、金融决策等需要高效策略评估的场景。通过优化样本复杂度和提高估计精度，NTD和CTD可以在实际应用中显著提升决策质量和效率，推动智能系统的进一步发展。

📄 摘要（原文）

Distributional reinforcement learning (DRL) has achieved empirical success in various domains. One core task in DRL is distributional policy evaluation, which involves estimating the return distribution $η^π$ for a given policy $π$. Distributional temporal difference learning has been accordingly proposed, which extends the classic temporal difference learning (TD) in RL. In this paper, we focus on the non-asymptotic statistical rates of distributional TD. To facilitate theoretical analysis, we propose non-parametric distributional TD (NTD). For a $γ$-discounted infinite-horizon tabular Markov decision process, we show that for NTD with a generative model, we need $\tilde{O}(\varepsilon^{-2}μ_{\min}^{-1}(1-γ)^{-3})$ interactions with the environment to achieve an $\varepsilon$-optimal estimator with high probability, when the estimation error is measured by the $1$-Wasserstein. This sample complexity bound is minimax optimal up to logarithmic factors. In addition, we revisit categorical distributional TD (CTD), showing that the same non-asymptotic convergence bounds hold for CTD in the case of the $1$-Wasserstein distance. We also extend our analysis to the more general setting where the data generating process is Markovian. In the Markovian setting, we propose variance-reduced variants of NTD and CTD, and show that both can achieve a $\tilde{O}(\varepsilon^{-2} μ_{π,\min}^{-1}(1-γ)^{-3}+t_{mix}μ_{π,\min}^{-1}(1-γ)^{-1})$ sample complexity bounds in the case of the $1$-Wasserstein distance, which matches the state-of-the-art statistical results for classic policy evaluation. To achieve the sharp statistical rates, we establish a novel Freedman's inequality in Hilbert spaces. This new Freedman's inequality would be of independent interest for statistical analysis of various infinite-dimensional online learning problems.