Speedy Q-Learning
Speedy Q-Learning
复制标题
DOI：
--
复制
发表时间：
2011-12
期刊：
影响因子：
--
通讯作者：
M. G. Azar;R. Munos;M. Ghavamzadeh;H. Kappen
中科院分区：
文献类型：
--
作者：
M. G. Azar;R. Munos;M. Ghavamzadeh;H. Kappen
我们引入了 Q-learning 的一种新的收敛变体，称为快速 Q-learning (SQL)，以解决 Q-learning 算法标准形式收敛速度慢的问题。我们证明了 SQL 性能的 PAC 界限，这表明对于具有 n 个状态-动作对和折扣因子 γ 的 MDP，SQL 算法仅需要 T = O(log(n)/(e2(1 – γ)4)) 步骤即可以高概率收敛到 ? 最优动作值函数。该界限更好地依赖于 1/e 和 1/(1 2– γ)，因此比 Q 学习的最佳可用结果更严格。我们的界限也优于批量 Q 值迭代的无模型和基于模型实例的现有结果，这些实例被认为比 Q 学习等增量方法更有效。
We introduce a new convergent variant of Q-learning, called speedy Q-learning (SQL), to address the problem of slow convergence in the standard form of the Q-learning algorithm. We prove a PAC bound on the performance of SQL, which shows that for an MDP with n state-action pairs and the discount factor γ only T = O(log(n)/(e2(1 – γ)4)) steps are required for the SQL algorithm to converge to an ?-optimal action-value function with high probability. This bound has a better dependency on 1/e and 1/(1 2– γ), and thus, is tighter than the best available result for Q-learning. Our bound is also superior to the existing results for both model-free and model-based instances of batch Q-value iteration that are considered to be more efficient than the incremental methods like Q-learning.