NUMERICAL ENCLOSURE FOR THE OPTIMAL THRESHOLD PROBABILITY IN DISCOUNTED MARKOV DECISION PROCESSES

There are various procedures to compute the optimal threshold probability in discounted Markov decision processes. In the actual numerical computation of an approximate optimal solution, the estimation of the discrepancy between the approximate solution and the exact solution is important. White(1993 b) derived such an error estimation for the value iteration method, however, this estimation is not actually in the computable form. In this paper, we present a numerical enclosure method to compute the optimal threshold probability, that guarantees a rigorous a posteriori error bound.