Probabilistic planning with risk-sensitive criterion

Probabilistic planning models and, in particular, Markov Decision Processes (MDPs), Partially Observable Markov Decision Processes (POMDPs) and Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) have been extensively used by AI and Decision Theoretic communities for planning under uncertainty. Typically, the solvers for probabilistic planning models find policies that minimize the expected cumulative cost (or, equivalently, maximize the expected cumulative reward). While such a policy is good in the expected case, there is a small chance that it might result in an exorbitantly high cost. Therefore, it is not suitable in high-stake planning problems, where exorbitantly high costs should be avoided. With this motivation in mind, Yu, Lin, and Yan (1998) introduced the Risk-Sensitive criterion (RS-criterion) for MDPs, where the objective is to find a policy π that maximizes the probability Pr(cT (s0) ≤ θ0), where cT (s0) is the cumulative cost of the policy and θ0 is the cost threshold. They combine MDPs with the RS-criterion to formalize Risk-Sensitive MDPs (RS-MDPs) and introduced a Value Iteration (VI) like algorithm to solve a typical type of RSMDPs. Liu and Koenig (2006) generalized RS-MDPs by mapping the MDP rewards to risk-sensitive utility functions and sought to find policies that maximize the expected utility—an RS-MDP is a specific case, where the utility function is a step function. They introduced Functional Value Iteration (FVI), which finds optimal policies for general utility functions by approximating it as piecewise linear (PWL) functions. Unfortunately, algorithms like VI and FVI cannot scale to large problems as they need to perform Bellman updates for all states and all break points of their utility function in each iteration. As such, more efficient algorithms can be developed to take advantage of structure in RS-MDPs. In my work, I introduced various algorithms for RSMDPs with different assumptions (e.g., MDPs with dead ends and MDPs with zero or negative cost cycles). In addition to RS-MDPs, POMDPs and Dec-POMDP can also be combined with RS-criterion to formalize Risk-Sensitive POMDPs (RS-POMDPs) and Risk-Sensitive Dec-POMDPs