Belief Embedding Tree Search

Christopher Solinas; Radovan Haluška; Martin Schmid; Michael Buro; Nathan R. Sturtevant; Michael Bowling

cs.AIOct 10, 2026

Belief Embedding Tree Search

Authors: Christopher Solinas, Radovan Haluška, Martin Schmid, Michael Buro, Nathan R. Sturtevant, Michael Bowling

Organizations: University of Alberta · Charles University, Prague · EquiLibre Technologies, Inc. · Alberta Machine Intelligence Institute (Amii)

Abstract

Beliefs in a Partially Observable Markov Decision Process (POMDP) are posterior distributions over the hidden state given the agent's history of actions and observations. They summarize everything the history says about the state, so planning in a POMDP is planning in a Markov decision process (MDP) over beliefs. Belief MDPs have continuous state spaces even for finite POMDPs, and exact planning in them is intractable in general. Planners must therefore approximate beliefs and estimate values. Monte Carlo planners do both inside a search tree, with an approximate belief at every node and a value estimate at every leaf. Approximations usually consist of sets of sampled states, with leaf values coming from rollouts, hand-designed bounds, or learned networks. Policies and values computed from these approximations are limited by their quality, and prior methods with learned networks rely on hand-chosen summaries of the sampled states. A belief representation should be computable from the parent node's representation through the POMDP's dynamics, let the search sample from it, and be learned so that it provides the information that policies and value functions need. We present Belief Embedding Tree Search (BETS), a Monte Carlo planner that meets these requirements by representing each node's belief with a generative distribution embedding (GDE) while updating it through the POMDP dynamics. BETS trains its belief model alongside its policy and value networks through experience, with the realized hidden state of the POMDP as the belief model's training target. We evaluate BETS on six configurations of RockSample, LightDark, and PocMan against BetaZero and three planners without learned components. BETS is competitive or leading on all six, while every baseline falls far behind on at least one. Where beliefs are highest-dimensional, it outperforms them by a large margin, even without search.

Figures & tables

Panel of Figure 1 — Figure 1: BETS. Each round starts every root action from the same sampled state and interior actions are selected via PUCT. Expansion costs one NBF update.

Panel of Figure 2 — Figure 2: The variable-coupling stream. Pooling over samples gives one summary per variable and a variable-by-variable co-occurrence matrix. Attention over the variable summaries, biased by the co-occurrence matrix, produces coupling summaries, which are concatenated with $\mu$ to form $\theta$ .

Domain	search	policy	BetaZero	AdaOPS	DESPOT	POMCPOW
	BETS
RockSample(15,15)	20.78 $\pm$ 0.09	20.65 $\pm$ 0.10	19.79 $\pm$ 0.18	21.45 $\pm$ 0.10	19.45 $\pm$ 0.10	11.45 $\pm$ 0.08
RockSample(20,20)	14.97 $\pm$ 0.13	13.91 $\pm$ 0.16	11.30 $\pm$ 0.15	10.77 $\pm$ 0.20 †	0.28 $\pm$ 0.02 †	4.33 $\pm$ 0.18 †
LightDark(5)	3.61 $\pm$ 0.10	3.77 $\pm$ 0.12	3.76 $\pm$ 0.15	3.08 $\pm$ 0.03 †	2.29 $\pm$ 0.09	2.82 $\pm$ 0.25
LightDark(10)	13.01 $\pm$ 0.41	13.88 $\pm$ 0.28	14.43 $\pm$ 0.33	3.18 $\pm$ 0.40 †	0.33 $\pm$ 0.05	0.98 $\pm$ 0.13
PocMan(M)	78.08 $\pm$ 0.54	72.42 $\pm$ 2.05	40.87 $\pm$ 3.26	–	54.20 $\pm$ 0.34	36.34 $\pm$ 1.93

Table 1: Mean discounted return with the SE across training seeds (BETS, BetaZero) or evaluation seeds (AdaOPS, DESPOT, POMCPOW). AdaOPS has no bounds implementation for PocMan.

Table 2: Variable coupling and value prediction on PocMan(M).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Search
	RockSample		LightDark		PocMan
	(15,15)	(20,20)	(5)	(10)	(M), (L)
Simulations per decision $K$	600	600	99	99	100
Particles per node $n$	256	256	256	256	512
Exploration constant $c$	20 to 3
Prior mix $m$	0 to 0.75

Appendix

Table 3: BETS settings per configuration. A range is annealed over the anneal window.

Policy iteration
	RockSample		LightDark		PocMan
	(15,15)	(20,20)	(5)	(10)	(M), (L)
Iterations $\times$ episodes	50 $\times$ 500	50 $\times$ 500	30 $\times$ 500	30 $\times$ 500	40 $\times$ 250
Epochs per iteration	10	10	50	50	10
Optimizer	RMSProp	RMSProp	Adam	Adam	RMSProp
Learning rate	$10^{-3}$	$10^{-3}$	$10^{-4}$	$10^{-4}$	$10^{-4}$

Appendix

Table 4: BetaZero settings per configuration. A cell with two values gives the value during policy iteration, then the value at evaluation.

AdaOPS ( Wu et al., 2021 )
	RockSample	LightDark	PocMan
Lower, upper bound	exit policy, QMDP †	$-r$ , $r$	–
$m_{\min}$ , $\delta$	100, 0.1	10, 1.0	–
Maximum depth	90	90	–
DESPOT ( Somani et al., 2013 )
Lower, upper bound	exit policy, QMDP †	random policy, $r$	preferred actions, fixed

Appendix

Table 5: AdaOPS, DESPOT, and POMCPOW settings per domain.

Panel of Figure 3 — Figure 3: Per-variable conditioning of the autoregressive generator. Token $j$ combines the coupling summary $\mathrm{VC}_{j}$ of variable $j$ with the pooled embedding $\mu$ shared by every token. The causal blocks attend to the preceding values $x_{<j}$ , and the output is the logits of the factor $p_{\psi}(x_{j}\mid x_{<j},\theta)$ .

Domain	$n$	$K=50$	$K=100$	$K=200$	policy
		search
RockSample(15,15)	256	140	229	460	2.8
	512	248	410	812	4.5
RockSample(20,20)	256	176	349	688	4.0
	512	323	641	1289	6.6
LightDark(5)	256	237	454	901	5.6

Appendix

Table 6: Milliseconds per decision of BETS on one NVIDIA GeForce RTX 5080.

Explore similar work

Apr 1, 2026

Leveraging the Value of Information in POMDP Planning

Partially observable Markov decision processes (POMDPs) offer a principled formalism for planning under state and transition uncertainty. Despite advances made towards solving large POMDPs, obtaining performant policies under limited planning time remains a major challenge due to the curse of dimensionality and the curse of history. For many POMDP problems, the value of information (VOI) - the expected performance gain from reasoning about observations - varies over the belief space. We introduce a dynamic programming framework that exploits this structure by conditionally processing observations based on the value of information at each belief. Building on this framework, we propose Value of Information Monte Carlo planning (VOIMCP), a Monte Carlo Tree Search algorithm that allocates computational effort more efficiently by selectively disregarding observation information when the VOI is low, avoiding unnecessary branching of observations. We provide theoretical guarantees on the near-optimality of our VOI reasoning framework and derive non-asymptotic convergence bounds for VOIMCP. Simulation evaluations demonstrate that VOIMCP outperforms baselines on several POMDP benchmarks.

Zakariya Laouar, Qi Heng Ho, Zachary Sunberg

Department of Aerospace Engineering Sciences, University of Colorado Boulder · Kevin T. Crofton Department of Aerospace and Ocean Engineering, Virginia Tech

Partially Observable Markov Decision Processes Belief-Space Planning Value of Information Monte Carlo Tree Search Dynamic Programming

Ask PDF

Jun 3, 2026

Think Fast and Far: Long-Horizon Online POMDP Planning via Rapid State Sampling

Partially Observable Markov Decision Processes (POMDPs) are a general and principled framework for motion planning under uncertainty. Despite tremendous improvement in the scalability of POMDP solvers, long-horizon POMDPs remain difficult to solve. To alleviate the difficulty, this paper proposes a new approximate online POMDP solver, called Reference-Based Online POMDP Planning via Rapid State Space Sampling (ROP-RAS3). ROP-RAS3 uses novel extremely fast sampling-based motion planning techniques to sample the state space and generate a diverse set of macro actions online, which are then used to bias belief-space sampling and infer high-quality policies without requiring exhaustive enumeration of the action space -- a fundamental constraint for modern online POMDP solvers. ROP-RAS3 converges to a near-optimal reference-based solution at a rate that depends on the number of sampled actions, rather than the size of the action space. ROP-RAS3 is evaluated on various long-horizon POMDPs with up to 3000 lookahead steps and 35-dimensional state spaces, where the state, action and observation spaces can be continuous, discrete, or a hybrid of discrete and continuous. Although the reference-based optimal solution may not be the same as the optimal POMDP solution, empirical results indicate that in all of these problems, in terms of success rate, ROP-RAS3 outperforms other state-of-the-art methods by up to multiple folds. We also demonstrate the capability of our approach on a physical robot demonstration. This work extends the theory and empirical results of our ISRR24 paper. Code can be found at https://github.com/RDLLab/ROPRAS3.

Yuanchu Liang, Edward Kim, J. Arden Knoll +4

Australian National University, Canberra ACT 2601, Australia. · Rice University, Houston TX 77005, USA.

Belief-Space Planning Partially Observable Markov Decision Processes

Ask PDF

Jun 20, 2026

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

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.

Xiangwei Chen, Lingling Fang, Andreas Holzinger +1

School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China · School of Computer Science and Artificial Intelligence, Liaoning Normal University, Dalian 116029, China · Human-Centered AI Lab, Department of Ecosystem Management, Climate and Biodiversity, BOKU University, Vienna, 1190, Austria +1

Belief-Space Planning Partially Observable Markov Decision Processes

Ask PDF