Author(s)

Edilson F. Arruda, Fabrício Ourique

Federal University of Rio de Janeiro, Alberto Luiz Coimbra Institute—Graduate School and Research in Engineering, Rio de Janeiro, Brazil.
Federal University of Santa Catarina (Campus Araranguá), Araranguá, Brazil.

This paper proposes a technique to accelerate the convergence of the value iteration algorithm applied to discrete average cost Markov decision processes. An adaptive partial information value iteration algorithm is proposed that updates an increasingly accurate approximate version of the original problem with a view to saving computations at the early iterations, when one is typically far from the optimal solution. The proposed algorithm is compared to classical value iteration for a broad set of adaptive parameters and the results suggest that significant computational savings can be obtained, while also ensuring a robust performance with respect to the parameters.

Average Cost; Markov Decision Processes; Value Iteration; Computational Effort; Gradient

E. Arruda and F. Ourique, "Adaptive Strategies for Accelerating the Convergence of Average Cost Markov Decision Processes Using a Moving Average Digital Filter," American Journal of Operations Research, Vol. 3 No. 6, 2013, pp. 514-520. doi: 10.4236/ajor.2013.36050.