Accelerating the convergence of value iteration by using partial transition functions

作者：Arruda Edilson F^*; Ourique Fabricio O; LaCombe Jason; Almudevar Anthony

来源：European Journal of Operational Research, 2013, 229(1): 190-198.

DOI：10.1016/j.ejor.2013.02.029

• Dynamic programming
• Markov processes
• Optimization

This work proposes an algorithm that makes use of partial information to improve the convergence properties of the value iteration algorithm in terms of the overall computational complexity. The algorithm iterates on a series of increasingly refined approximate models that converges to the true model according to an optimal linear rate, which coincides with the convergence rate of the original value iteration algorithm. The paper investigates the properties of the proposed algorithm and features a series of switchover queue examples which illustrates the efficacy of the method.

• 出版日期2013-8-16