Block-scaling of value-iteration for discounted Markov renewal programming

The functional equations of infinite horizon discounted Markov renewal programming are where T is a monotone contractor operator. This paper shows how to accelerate convergence of the value-iteration scheme ^by a block-scaling step whereby all states in a given group have their scaled by a common scale factor. A similar method exists when the relative values are computed iteratively. In both cases, the block scaling factors are solution to a set of functional equations which has similar structure to a discounted Markov renewal program, and can itself be solved by successive approximation, policy iteration, or linear programming.