mlsanityData to 7 Oct 2026

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

arXiv 2606.21971 ↗First posted 20 Jun 2026cs.AIcited by 0

Not on the map. Why?

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.

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

Builds on

17 of 41 references.

References · 17

  1. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 183
  2. 2017Online algorithms for POMDPs with continuous state, action, and observation spacescited by 82
  3. 2022Partially Observable Markov Decision Processes in Robotics: A Surveycited by 81
  4. 2023The Safety Filter: A Unified View of Safety-Critical Control in Autonomous Systemscited by 77
  5. 2018Logically-Constrained Reinforcement Learningcited by 50
  6. 2020An On-Line POMDP Solver for Continuous Observation Spacescited by 15
  7. 2013What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectivescited by 14
  8. 2023BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximationscited by 13
  9. 2025Probabilistic Shielding for Safe Reinforcement Learningcited by 12
  10. 2023Safe POMDP Online Planning via Shieldingcited by 8
  11. 2024Guiding Multi-agent Multi-task Reinforcement Learning by a Hierarchical Framework with Logical Reward Shapingcited by 4
  12. 2023Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practicecited by 2
5 more
  1. 2024Previous Knowledge Utilization In Online Anytime Belief Space Planningcited by 2
  2. 2025Occlusion-Aware Contingency Safety-Critical Planning for Autonomous Drivingcited by 2
  3. 2025Observation Adaptation via Annealed Importance Resampling for Partially Observable Markov Decision Processescited by 2
  4. 2024Addressing Myopic Constrained POMDP Planning with Recursive Dual Ascentcited by 1
  5. 2025Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectivescited by 1

Built on by

Not cited yet.