On the speed of convergence of value iteration on stochastic shortest-path problems

• 成果类型: Article
• 署名作者: Bonet, Blai
• 署名单位: Simon Bolivar University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1060.0238
• 发表日期: 2007
• 页码: 365-373
• 关键词: search

摘要

We establish a bound on the convergence time of the value iteration algorithm on stochastic shortest-path problems. The bound. which applies for admissible initial vectors as, for example, J 0, implies a polynomial-time convergence of value iteration for all problems with polynormally bounded ||J*||/g. This result gives a partial answer to the open problem of bounding the convergence time of value iteration on arbitrary initial vectors. The proof is obtained by analyzing a stochastic process associated with the shortest-path problem.