首次为近最优强化学习算法提供依赖奖励差距的性能保证。
Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation
- 提出新分析方法，适用于近最优的线性函数逼近强化学习算法。
- 改进了对特征维度d和时域长度H的依赖关系，提升理论性能。
- 适用于多智能体并行探索，实现线性加速，适合分布式强化学习场景。
我们研究在线性函数逼近下的强化学习中，近最小最大最优算法的间隙依赖性能保证。尽管已有工作建立了该设置下的间隙依赖后悔界，但现有分析不适用于达到近最小最大最优最坏情况后悔界 $ ilde{O}(d oot{3}{H^3K})$（其中 $d$ 为特征维度，$H$ 为时域长度，$K$ 为训练轮数）的算法。本文填补这一空白，首次为近最优算法 LSVI-UCB++（He et al., 2023）提供了间隙依赖的后悔界。分析结果在 $d$ 和 $H$ 的依赖关系上优于先前的间隙依赖结果。此外，利用 LSVI-UCB++ 的低策略切换特性，我们引入一种并发变体，实现多个智能体的高效并行探索，并首次建立在线多智能体强化学习中线性函数逼近的间隙依赖样本复杂度上界，实现了与智能体数量成线性速度提升。
原文摘要 · Abstract (English)
We study gap-dependent performance guarantees for nearly minimax-optimal algorithms in reinforcement learning with linear function approximation. While prior works have established gap-dependent regret bounds in this setting, existing analyses do not apply to algorithms that achieve the nearly minimax-optimal worst-case regret bound $\tilde{O}(d\sqrt{H^3K})$, where $d$ is the feature dimension, $H$ is the horizon length, and $K$ is the number of episodes. We bridge this gap by providing the first gap-dependent regret bound for the nearly minimax-optimal algorithm LSVI-UCB++ (He et al., 2023). Our analysis yields improved dependencies on both $d$ and $H$ compared to previous gap-dependent results. Moreover, leveraging the low policy-switching property of LSVI-UCB++, we introduce a concurrent variant that enables efficient parallel exploration across multiple agents and establish the first gap-dependent sample complexity upper bound for online multi-agent RL with linear function approximation, achieving linear speedup with respect to the number of agents.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。