首次给出经典Q-learning的后悔界，无需乐观或奖励项。
Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
- 用退温玻尔兹曼探索分析在线Q-learning的后悔行为。
- 提出平滑ε_n-贪心策略，实现近似$ ilde{O}(N^{9/10})$的鲁棒后悔界。
- 适用于关注强化学习理论与高概率收敛性的研究者。
我们首次为无限时域折扣马尔可夫决策过程中的经典在线Q-learning提供了后悔界，且不依赖于乐观性或奖励项。首先分析了退温玻尔兹曼Q-learning，发现其后悔表现高度依赖于MDP的次优性差距：当差距足够大时，后悔为次线性；当差距较小时，后悔恶化并可能接近线性增长。为克服此局限，研究了一种结合ε_n-贪心与玻尔兹曼探索的平滑ε_n-贪心探索策略，证明其具有近似$ ilde{O}(N^{9/10})$的间隙鲁棒后悔界。同时获得样本复杂度保证，且在高概率下成立。为分析这些算法，我们建立了针对迭代与时间相关转移动态的收缩型马尔可夫随机逼近的高概率集中不等式，其中收缩因子可渐近趋近于1，该工具本身可能具独立价值。
原文摘要 · Abstract (English)
We present the first regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes (MDPs), without relying on optimism or bonus terms. We first analyze Boltzmann Q-learning with decaying temperature and show that its regret depends critically on the suboptimality gap of the MDP: for sufficiently large gaps, the regret is sublinear, while for small gaps it deteriorates and can approach linear growth. To address this limitation, we study a Smoothed $ε_n$-Greedy exploration scheme that combines $ε_n$-greedy and Boltzmann exploration, for which we prove a gap-robust regret bound of near-$\tilde{O}(N^{9/10})$. We also obtain sample complexity guarantees, with both regret and sample complexity bounds holding with high probability. To analyze these algorithms, we develop a high-probability concentration bound for contractive Markovian stochastic approximation with iterate- and time-dependent transition dynamics. This bound may be of independent interest as the contraction factor in our framework is allowed to converge to one asymptotically.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。