在最弱假设下分析了时变策略Q-learning的收敛性,揭示了探索与利用的权衡。
A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies
- 基于泊松方程分解马尔可夫噪声,处理时变策略带来的分析难题
- 证明了最后迭代收敛速率,样本复杂度为 $\mathcal{O}(1/ξ^2)$
- 适用于研究在线策略强化学习的理论机制,如单尺度演员-评论家
本文首次在最小假设下对折扣马尔可夫决策过程中的时变学习策略(即在线策略采样)的Q-learning进行了有限时间分析,仅要求存在一个使状态空间上马尔可夫链不可约的策略。我们建立了 $\mathbb{E}[ |Q_k - Q^*|_\infty^2]$ 的最后迭代收敛速率,表明达到 $\mathbb{E}[ |Q_k - Q^*|_\infty]\le ξ$ 的样本复杂度为 $\mathcal{O}(1/ξ^2)$,与离线策略Q-learning一致,但探索相关参数依赖更差。同时推导出 $\mathbb{E}[ |Q^{π_k} - Q^*|_\infty^2]$ 的有限时间速率,凸显在线策略中探索与利用的权衡。尽管探索能力弱于离线方法,但随着学习策略趋近最优,其利用优势明显。数值结果支持理论。技术上,快速时变策略引发时非齐次马尔可夫噪声,带来显著分析挑战。为此,我们基于懒惰转移矩阵发展了一种泊松方程分解,将噪声拆分为鞅差项与残差项;残差通过泊松方程解对Q估计和学习策略的敏感性分析进行控制。这些方法可能推广至其他时变策略算法,如单尺度演员-评论家和博弈学习算法。
原文摘要 · Abstract (English)
In this work, we present the first finite-time analysis of Q-learning with time-varying learning policies (i.e., on-policy sampling) for discounted Markov decision processes under minimal assumptions, requiring only the existence of a policy that induces an irreducible Markov chain over the state space. We establish a last-iterate convergence rate for $\mathbb{E}[\|Q_k - Q^*\|_\infty^2]$, implying a sample complexity of order $\mathcal{O}(1/ξ^2)$ for achieving $\mathbb{E}[\|Q_k - Q^*\|_\infty]\le ξ$. This matches the rate of off-policy Q-learning, but with worse dependence on exploration-related parameters. We also derive a finite-time rate for $\mathbb{E}[\|Q^{π_k} - Q^*\|_\infty^2]$, where $π_k$ is the learning policy at iteration $k$, highlighting the exploration-exploitation trade-off in on-policy Q-learning. While exploration is weaker than in off-policy methods, on-policy learning enjoys an exploitation advantage as the learning policy converges to an optimal one. Numerical results support our theory. Technically, rapidly time-varying learning policies induce time-inhomogeneous Markovian noise, creating significant analytical challenges under minimal exploration. To address this, we develop a Poisson-equation-based decomposition of the Markovian noise under a lazy transition matrix, separating it into a martingale-difference term and residual terms. The residuals are controlled via sensitivity analysis of the Poisson equation solution with respect to both the Q-function estimate and the learning policy. These techniques may extend to other RL algorithms with time-varying policies, such as single-timescale actor-critic methods and learning-in-games algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。