State reduction in a Markov decision process
Theodore J. Sheskin · International Journal of Mathematical Education in Science and Technology · 1999
We present a new state reduction algorithm for solving the value determination equations of policy iteration for a Markov decision process. The state reduction algorithm has three parts: (1) augmentation; (2) stochastic complementation; and (3) a backward pass. We show that stochastic complementation is equivalent to reducing the size of a system of linear equations by the method of substitution. When we execute policy iteration for a discounted Markov decision process, we defer all subtractions until we have obtained an optimal policy in order to reduce round-off error. For a Markov decision process using the average reward criterion, stochastic complementation has an interesting probabilistic interpretation. Our state reduction algorithm has about the same number of arithmetic operations as Gaussian elimination. We apply policy iteration with state reduction to solve a small example problem involving the nesting behaviour of a female hawk.