首次给出带马尔可夫噪声的双时间尺度算法的有限时间误差界。
Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise
- 用广义Moreau包络处理任意范数压缩映射。
- 一般情况下均方误差以$O(1/n^{2/3})$速率下降。
- 适用于强化学习中的Q-Learning与博弈均衡求解。
双时间尺度随机逼近（Two-time-scale Stochastic Approximation, SA）在强化学习与优化中有广泛应用。此前的有限时间分析主要针对欧几里得范数下的固定点迭代。本文首次为具有任意范数压缩映射和马尔可夫噪声的非线性双时间尺度SA给出了均方误差上界。在一般情况下，均方误差以$O(1/n^{2/3})$的速率衰减；在慢时间尺度无噪声的特殊情形下，收敛速率达到$O(1/n)$。分析中采用广义Moreau包络处理任意范数收缩，并利用泊松方程解处理马尔可夫噪声。通过分析SSP Q-Learning算法，首次获得平均奖励准则下异步控制MDPs算法的$O(1/n)$收敛界。此外，还得到了带Polyak平均的Q-Learning的$O(1/n)$速率，并提出一种强单调博弈中广义纳什均衡的$O(1/n^{2/3})$收敛算法。
原文摘要 · Abstract (English)
Two-time-scale Stochastic Approximation (SA) is an iterative algorithm with applications in reinforcement learning and optimization. Prior finite time analysis of such algorithms has focused on fixed point iterations with mappings contractive under Euclidean norm. Motivated by applications in reinforcement learning, we give the first mean square bound on non linear two-time-scale SA where the iterations have arbitrary norm contractive mappings and Markovian noise. We show that the mean square error decays at a rate of $O(1/n^{2/3})$ in the general case, and at a rate of $O(1/n)$ in a special case where the slower timescale is noiseless. Our analysis uses the generalized Moreau envelope to handle the arbitrary norm contractions and solutions of Poisson equation to deal with the Markovian noise. By analyzing the SSP Q-Learning algorithm, we give the first $O(1/n)$ bound for an algorithm for asynchronous control of MDPs under the average reward criterion. We also obtain a rate of $O(1/n)$ for Q-Learning with Polyak-averaging and provide an algorithm for learning Generalized Nash Equilibrium (GNE) for strongly monotone games which converges at a rate of $O(1/n^{2/3})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。