Online POMDP Planning with Anytime Deterministic Optimality Guarantees
This work addresses the challenge of providing deterministic guarantees for approximate POMDP solvers, which is incremental but improves certification and decision-making in autonomous systems.
The paper tackles the problem of decision-making under uncertainty in POMDPs by deriving deterministic bounds that relate approximated solutions to optimal ones, enabling algorithms with anytime deterministic optimality guarantees and showing superior performance in some cases.
Decision-making under uncertainty is a critical aspect of many practical autonomous systems due to incomplete information. Partially Observable Markov Decision Processes (POMDPs) offer a mathematically principled framework for formulating decision-making problems under such conditions. However, finding an optimal solution for a POMDP is generally intractable. In recent years, there has been a significant progress of scaling approximate solvers from small to moderately sized problems, using online tree search solvers. Often, such approximate solvers are limited to probabilistic or asymptotic guarantees towards the optimal solution. In this paper, we derive a deterministic relationship for discrete POMDPs between an approximated and the optimal solution. We show that at any time, we can derive bounds that relate between the existing solution and the optimal one. We show that our derivations provide an avenue for a new set of algorithms and can be attached to existing algorithms that have a certain structure to provide them with deterministic guarantees with marginal computational overhead. In return, not only do we certify the solution quality, but we demonstrate that making a decision based on the deterministic guarantee may result in superior performance compared to the original algorithm without the deterministic certification.