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

arXiv: https://arxiv.org/abs/2606.21971 · HTML: https://mlsanity.com/paper/2606.21971/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 20 Jun 2026.

## Builds on (most cited first, 17 of 17)

- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [The Safety Filter: A Unified View of Safety-Critical Control in Autonomous Systems](https://mlsanity.com/paper/2309.05837/) (2023)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Online algorithms for POMDPs with continuous state, action, and observation spaces](https://mlsanity.com/paper/1709.06196/) (2017)
- [Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/1801.08099/) (2018)
- [An On-Line POMDP Solver for Continuous Observation Spaces](https://mlsanity.com/paper/2011.02076/) (2020)
- [What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives](https://mlsanity.com/paper/1309.2802/) (2013)
- [BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximations](https://mlsanity.com/paper/2306.00249/) (2023)
- [Probabilistic Shielding for Safe Reinforcement Learning](https://mlsanity.com/paper/2503.07671/) (2025)
- [Safe POMDP Online Planning via Shielding](https://mlsanity.com/paper/2309.10216/) (2023)
- [Guiding Multi-agent Multi-task Reinforcement Learning by a Hierarchical Framework with Logical Reward Shaping](https://mlsanity.com/paper/2411.01184/) (2024)
- [Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practice](https://mlsanity.com/paper/2311.07745/) (2023)
- [Previous Knowledge Utilization In Online Anytime Belief Space Planning](https://mlsanity.com/paper/2412.13128/) (2024)
- [Occlusion-Aware Contingency Safety-Critical Planning for Autonomous Driving](https://mlsanity.com/paper/2502.06359/) (2025)
- [Observation Adaptation via Annealed Importance Resampling for Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2503.19302/) (2025)
- [Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives](https://mlsanity.com/paper/2511.13134/) (2025)
- [Addressing Myopic Constrained POMDP Planning with Recursive Dual Ascent](https://mlsanity.com/paper/2403.17358/) (2024)

## Abstract (arXiv)

Online planning in continuous partially observable Markov decision processes (POMDPs) using ω-regular specifications requires handling continuous belief dynamics within the finite symbolic memory in order to track temporal progress. Existing methods based on either direct search in belief space or predefined discrete abstractions suffer from drawbacks, e.g., lack of symbolic memory for long-horizon logical progress or difficult to certify from noisy online beliefs. As such, obtaining reliable symbolic states online from continuous observations remains a challenge. To address this issue, we introduce the Revealed Belief Automaton (REBA), an event-driven framework that advances the research from global belief-space discretization to a fundamental new way of thinking, namely online certification of revelation events. Specifically, we propose an online revelation method that, through information-theoretic gates, can dynamically analyse and establish belief abstraction from the continuous belief space by discovering reliable anchors among noisy beliefs. We then develop an incremental topology adaptation mechanism over the certified anchors to realise the online finite Belief Automaton. By combining with the ω-regular specification, REBA is able to support formal parity policy synthesis without a predefined discrete abstraction, which in turn can guide the Monte Carlo Tree Search process to perform online search beyond its local horizon. In addition, we design an error decomposition analysis which can assess the effectiveness and reliability of this discrete guidance for the underlying continuous POMDP. Empirical evaluations in patrolling and navigation scenarios show that REBA matches or exceeds all evaluated baselines, with primary metric gains of +17.0% to +47.4% over state-of-the-art approaches.