Markov decision processes associated with two threshold probability criteria

This paper deals with Markov decision processes with a target set for nonpositive rewards.Two types of threshold probability criteria are discussed.The frst criterion is a probability that a total reward is not greater than a given initial threshold value,and the second is a probability that the total reward is less than it.Our frst(resp.second)optimizing problem is to minimize the frst(resp.second)threshold probability.These problems suggest that the threshold value is a permissible level of the total reward to reach a goal(the target set),that is,we would reach this set over the level,if possible.For the both problems,we show that 1)the optimal threshold probability is a unique solution to an optimality equation,2)there exists an optimal deterministic stationary policy,and 3)a value iteration and a policy space iteration are given.In addition,we prove that the frst(resp.second)optimal threshold probability is a monotone increasing and right(resp.left)continuous function of the initial threshold value and propose a method to obtain an optimal policy and the optimal threshold probability in the frst problem by using them in the second problem.