On Boundedness of Q-Learning Iterates for Stochastic Shortest Path Problems
On Boundedness of Q-Learning Iterates for Stochastic Shortest Path Problems
复制标题
随机最短路径问题的 Q-Learning 迭代有界性
DOI：
10.1287/moor.1120.0562
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
D. Bertsekas
中科院分区：
文献类型：
--
作者：
Huizhen Yu;D. Bertsekas
我们考虑一种完全异步的随机逼近算法Q-学习来求解有限空间随机最短路SSP问题，该问题是具有吸收和无代价状态的无折扣总代价马尔可夫决策过程。对于最常用的SSP模型，现有的收敛证明都假设q-学习迭代序列是概率1有界的，或者其他一些保证有界性的条件。我们证明了迭代序列以概率1自然有界，从而在Tsitsiklis[Tsitsikillis JN1994异步随机逼近和Q-学习]的收敛证明中提供了有界性条件。机器学习。16：185--202]，并完全建立了这些SSP模型的Q学习的收敛性质。
We consider a totally asynchronous stochastic approximation algorithm, Q-learning, for solving finite space stochastic shortest path SSP problems, which are undiscounted, total cost Markov decision processes with an absorbing and cost-free state. For the most commonly used SSP models, existing convergence proofs assume that the sequence of Q-learning iterates is bounded with probability one, or some other condition that guarantees boundedness. We prove that the sequence of iterates is naturally bounded with probability one, thus furnishing the boundedness condition in the convergence proof by Tsitsiklis [Tsitsiklis JN 1994 Asynchronous stochastic approximation and Q-learning. Machine Learn. 16:185--202] and establishing completely the convergence of Q-learning for these SSP models.