REBA: A Revealed Belief Automaton Framework for Online Planning in Continuous POMDPs

Researchers introduce REBA (Revealed Belief Automaton), a new framework for online planning in continuous partially observable environments that dynamically certifies belief states rather than relying on predefined discrete abstractions. The method achieves 17-47% performance improvements over existing approaches in patrolling and navigation tasks by combining information-theoretic analysis with formal symbolic planning.

REBA addresses a fundamental challenge in autonomous systems: how to make reliable long-horizon decisions when operating in continuous environments with incomplete information. Traditional approaches either work entirely in continuous belief space without symbolic memory for logical constraints, or pre-discretize the environment before planning begins—both approaches limit adaptability and performance. This research bridges that gap through online revelation events, where the system dynamically discovers trustworthy anchor points in noisy belief distributions and builds a finite automaton incrementally. This represents a meaningful shift from static abstraction to adaptive certification.

The work builds on decades of POMDP research but introduces information-theoretic gating as a novel mechanism for validating when continuous beliefs have stabilized enough to represent reliable discrete states. By coupling this dynamic abstraction with ω-regular specifications (formal logic for infinite-horizon goals), REBA enables Monte Carlo Tree Search to extend beyond its typical local planning horizon using formally verified guidance. The error decomposition analysis provides a framework for assessing how well discrete guidance performs on the underlying continuous problem—a critical feature for safety-critical applications.

For the robotics and autonomous systems community, this work has immediate practical implications. The substantial performance gains (up to 47% improvement) suggest faster convergence and better goal satisfaction in real-world deployment scenarios. The approach scales computationally better than global discretization methods while maintaining formal correctness guarantees. Future impact depends on whether these methods prove robust to sensor noise and dynamic environments in physical systems rather than simulation.

• →REBA dynamically certifies belief states online instead of using predefined discrete abstractions, enabling adaptive symbolic planning.
• →Information-theoretic gates identify reliable anchor points in noisy continuous beliefs to construct finite automata incrementally.
• →Integration with ω-regular specifications allows formal policy synthesis that guides Monte Carlo Tree Search beyond local horizons.
• →Empirical results show 17-47% performance improvements over state-of-the-art baselines in navigation and patrolling tasks.
• →Error decomposition analysis assesses the reliability of discrete guidance for underlying continuous POMDP problems.