Risk-Sensitive Markov Decision Process with Limited Budget
Daniel Augusto Moreira, Karina Valdivia Delgado, Leliane Nunes de Barros · 2017
Markov Decision Process (MDP) commonly have the objective of finding a policy that minimizes the expected cumulative cost. Although this optimization criterion is useful, some policy executions may result in a too high cost, which for some applications is unacceptable (e.g. policies for military operations). A better optimization problem for those applications is based on probability maximization of cumulative costs within a threshold, called Risk-Sensitive MDP (RS-MDP). In the frame of RS-MDP, we propose a new challenging problem of finding the minimum budget for which the probability maximization of cumulative costs converges to a maximum. To solve this problem we propose a modified algorithm based on TVI-DP (a previous solution for RS-MDPs) and demonstrate its correctness. We also propose two major efficient improvements for memory saving and early termination. Finally, the empirical results show the proposed algorithm can solve large instances of RS-MDPs.