TITLE:
Adaptive Strategies for Accelerating the Convergence of Average Cost Markov Decision Processes Using a Moving Average Digital Filter
AUTHORS:
Edilson F. Arruda, Fabrício Ourique
KEYWORDS:
Average Cost; Markov Decision Processes; Value Iteration; Computational Effort; Gradient
JOURNAL NAME:
American Journal of Operations Research,
Vol.3 No.6,
October
31,
2013
ABSTRACT:
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.