Tighter Value-Function Approximations for POMDPs

Solving partially observable Markov decision processes (POMDPs) typically requires reasoning about the values of exponentially many state beliefs. Towards practical performance, state-of-the-art solvers use value bounds to guide this reasoning. However, sound upper value bounds are often computationally expensive to compute, and there is a tradeoff between the tightness of such bounds and their computational cost. This paper introduces new and provably tighter upper value bounds than the commonly used fast informed bound. Our empirical evaluation shows that, despite their additional computational overhead, the new upper bounds accelerate state-ofthe-art POMDP solvers on a wide range of benchmarks.

Authors

• Merlijn Krale Radboud University, Nijmegen
• Wietze Koops Lund University, Lund, Sweden University of Copenhagen, Copenhagen, Denmark
• Sebastian Junges Radboud University Nijmegen, The Netherlands
• Thiago D. Simão Eindhoven University of Technology, The Netherlands
• Nils Jansen Radboud University Nijmegen, The Netherlands Ruhr-University Bochum, Germany

Keywords

• POMDPs
• Heuristic Search
• Value Bounds
• Planning