An Exact Algorithm for Solving MDPs under Risk-Sensitive Objective with One-Switch Utility Functions

One-switch utility functions are an important class of nonlinear utility functions that can model human beings whose decisions change with their wealth level. We study how to maximize the expected utility for Markov decision problems with given one-switch utility functions. We first utilize the fact that one-switch utility functions are weighted sums of linear and exponential utility functions to prove that there exists an optimal policy that is both stationary and deterministic as the wealth level approaches negative infinity. We then develop a solution method, the backward-induction method, that starts with this policy and augments it for higher and higher wealth levels. Our backward-induction method determines maximal expected utilities in finite time, different from the previous functional value iteration method, that typically determines only approximately maximal expected utilities.

Authors

• Yaxin Liu Institute of Information Engineering, Chinese Academy of Sciences School of Cyber Security, University of Chinese Academy of Sciences
• Sven Koenig University of California, Irvine

Keywords

• Decision Making
• Functional Value Iteration
• Markov Decision Problem
• One-Switch Utility Function
• Planning
• Utility Theory