An exact algorithm for solving MDPs under risk-sensitive planning objectives with one-switch utility functions

ABSTRACT

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.

REFERENCES

• 1: David E. Bell, One-switch utility functions and a measure of risk, Management Science, v.34 n.12, p.1416-1424, Dec. 1988 [doi>10.1287/mnsc.34.12.1416]
• 2: David E. Bell , Peter C. Fishburn, Strong One-Switch Utility, Management Science, v.47 n.4, p.601-604, April 2001 [doi>10.1287/mnsc.47.4.601.9825]
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, An analysis of stochastic shortest path problems, Mathematics of Operations Research, v.16 n.3, p.580-595, Aug. 1991 [doi>10.1287/moor.16.3.580]
• 4: J. L. Corner and P. D. Corner. Characteristics of decisions in decision analysis practice. The Journal of Operational Research Society, 46:304--314, 1995.
• 5: Gregory M. Gelles , Douglas W. Mitchell, Broadly Decreasing Risk Aversion, Management Science, v.45 n.10, p.1432-1439, October 1999 [doi>10.1287/mnsc.45.10.1432]
• 6: S. Koenig and R. G. Simmons. Risk-sensitive planning with probabilistic decision graphs. In Proceedings of the Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR-94), pages 2301--2308, 1994.
• 7: Yaxin Liu , Sven Koenig, Decision-theoretic planning under risk-sensitive planning objectives, Georgia Institute of Technology, Atlanta, GA, 2005
• 8: Y. Liu and S. Koenig. Existence and finiteness conditions for risk-sensitive planning: Results and conjectures. In Proceedings of the Twentieth Annual Conference on Uncertainty in Artificial Intelligence (UAI-05), 2005.
• 9: Y. Liu and S. Koenig. Risk-sensitive planning with one-switch utility functions: Value iteration. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), pages 993--999, 2005.
• 10: C. McMillen and M. Veloso. Thresholded rewards: Acting optimally in timed, zero-sum games. In Proceedings of The Twenty-Second Conference on Artificial Intelligence (AAAI-07), 2007.
• 11: Y. Nakamura. Sumex utility functions. Mathematical Social Sciences, 31:39--47, 1996.
• 12: E. Nikolova, M. Brand, and D. R. Karger. Optimal route planning under uncertainty. In Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS-06), 2006.
• 13: S. D. Patek. On terminating Markov decision processes with a risk averse objective function. Automatica, 37(9):1379--1386, 2001.
• 14: P. Perny, O. Spanjaard, and L.-X. Storme. State space search for risk-averse agents. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), pages 2353--2358, 2007.
• 15: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 16: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1st edition, 1944.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms

Keywords:
Markov decision problem, decision making, functional value iteration, one-switch utility function, planning, utility theory