Probabilistic planning models – Markov Decision Processes (MDPs) and Partially Observable Markov Decision Processes (POMDPs) – have been extensively studied by Artififi- cial Intelligence communities for planning under uncertainty. The conventional criterion for these probabilistic planning models is to fifind policies that minimize the expected cumulative cost, which we call the Minimizing Expected Cost criterion (MEC-criterion). While such a policy is good in the expected case, there is a chance that it might result in an exorbitantly high cumulative cost. Therefore, it is not suitable in high-stake planning problems, where exorbitantly high cumulative costs should be avoided. With the above motivation in mind, Yu et al. [1998] introduced the Risk-Sensitive criterion (RS-criterion), where the objective is to fifind a policy that maximizes the probability that the cumulative cost of possible execution trajectories is less than an user-defifined initial cost threshold ✓0. Also, if we consider the initial cost threshold ✓0 as the cost budget that the system holds at the beginning, then the above objective probabilities