  Continuous POMDPs with general belief-dependent rewards are notoriously
difficult to solve online. In this paper, we present a complete provable theory
of adaptive multilevel simplification for the setting of a given externally
constructed belief tree and MCTS that constructs the belief tree on the fly
using an exploration technique. Our theory allows to accelerate POMDP planning
with belief-dependent rewards without any sacrifice in the quality of the
obtained solution. We rigorously prove each theoretical claim in the proposed
unified theory. Using the general theoretical results, we present three
algorithms to accelerate continuous POMDP online planning with belief-dependent
rewards. Our two algorithms, SITH-BSP and LAZY-SITH-BSP, can be utilized on top
of any method that constructs a belief tree externally. The third algorithm,
SITH-PFT, is an anytime MCTS method that permits to plug-in any exploration
technique. All our methods are guaranteed to return exactly the same optimal
action as their unsimplified equivalents. We replace the costly computation of
information-theoretic rewards with novel adaptive upper and lower bounds which
we derive in this paper, and are of independent interest. We show that they are
easy to calculate and can be tightened by the demand of our algorithms. Our
approach is general; namely, any bounds that monotonically converge to the
reward can be easily plugged-in to achieve significant speedup without any loss
in performance. Our theory and algorithms support the challenging setting of
continuous states, actions, and observations. The beliefs can be parametric or
general and represented by weighted particles. We demonstrate in simulation a
significant speedup in planning compared to baseline approaches with guaranteed
identical performance.
