证明线性Q学习在L²意义下收敛到有界集，无需修改算法或强假设。
Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set
- 基于马尔可夫噪声与快速变化转移函数的随机逼近理论分析
- 首次给出线性Q学习迭代序列在L²下的收敛速率
- 适用于ε-softmax行为策略，无需贝尔曼完备性或近最优假设
Q-learning是强化学习中最基础的算法之一。长期以来，人们认为带有线性函数近似的Q-learning（即线性Q-learning）存在发散风险。直到近期Meyn（2024）的工作才首次证明了线性Q-learning迭代序列几乎必然有界。本文在此基础上，进一步建立了线性Q-learning迭代序列在L²意义下收敛到有界集的首个收敛速率。与Meyn（2024）类似，本工作不修改原始算法，不假设贝尔曼完备性，也不要求行为策略具有近最优性。我们仅需一个ε-softmax行为策略并采用自适应温度。分析的关键在于马尔可夫噪声下具有快速变化转移函数的随机逼近的一般结果。作为副产品，我们也利用该一般结果，为ε-softmax行为策略下的表格型Q-learning建立了L²收敛速率，其关键在于加权贝尔曼最优算子的新伪压缩性质。
原文摘要 · Abstract (English)
$Q$-learning is one of the most fundamental reinforcement learning algorithms. It is widely believed that $Q$-learning with linear function approximation (i.e., linear $Q$-learning) suffers from possible divergence until the recent work Meyn (2024) which establishes the ultimate almost sure boundedness of the iterates of linear $Q$-learning. Building on this success, this paper further establishes the first $L^2$ convergence rate of linear $Q$-learning iterates (to a bounded set). Similar to Meyn (2024), we do not make any modification to the original linear $Q$-learning algorithm, do not make any Bellman completeness assumption, and do not make any near-optimality assumption on the behavior policy. All we need is an $ε$-softmax behavior policy with an adaptive temperature. The key to our analysis is the general result of stochastic approximations under Markovian noise with fast-changing transition functions. As a side product, we also use this general result to establish the $L^2$ convergence rate of tabular $Q$-learning with an $ε$-softmax behavior policy, for which we rely on a novel pseudo-contraction property of the weighted Bellman optimality operator.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。