Tighter Value-Function Approximations for POMDPs
This work addresses computational bottlenecks in POMDP planning for robotics and AI applications, though it is incremental as it improves upon existing bound methods.
The paper tackled the problem of expensive and loose upper value bounds in POMDP solvers by introducing new, provably tighter bounds, which accelerated state-of-the-art solvers on various benchmarks.
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-of-the-art POMDP solvers on a wide range of benchmarks.