Replacement process decomposition for discounted Markov renewal programming

An iterative decomposition method is presented for computing the values in an infinite-horizon discounted Markov renewal program (DMRP). The states are partitioned into M groups, with each iteration involving disaggregation of one group at a time, with the other M-1 groups being collapsed into M-1 singletons using the replacement process method. Each disaggregation also looks like a DMRP and can be performed by policy-iteration, value-iteration or linear programming. Anticipated benefits from the method include reduced computer time and memory requirements, scale-invarance and greater robustness to the starting point.