From POMDP Theory to Deep RL with Particle Filters

Kevin Tan; Ziping Xu

cs.LGOct 20, 2026

From POMDP Theory to Deep RL with Particle Filters

Authors: Kevin Tan, Ziping Xu

Organizations: Wharton Statistics and Data Science, University of Pennsylvania · School of Data and Information Sciences, University of North Carolina at Chapel Hill

Abstract

Model-based reinforcement learning in partially observable environments requires inferring hidden states, learning latent dynamics, and planning under the resulting belief. Practical algorithms often solve one aspect of the above pipeline while relying on approximations for the others that are often poorly understood, while existing POMDP theory typically analyzes computationally inefficient theoretical algorithms far from modern deep RL practice. To fill this gap, we propose a practical end-to-end algorithm that approximately solves the hidden state filtering problem via sequential Monte Carlo (SMC), updates a latent dynamics model online, and performs approximate online planning for $d$ steps before bootstrapping leaves with a state-value critic (a QMDP approximation). We analyze each approximation and prove an end-to-end regret bound decomposing the error into model estimation error, particle filter error, Monte Carlo rollout error, and a structural bias term induced by the QMDP approximation controllable by the planning depth that we further analyze in various special cases. The resulting guarantee makes explicit how statistical sample size, particle budget, rollout budget, and planning depth affect performance. We instantiate our algorithm in an MPC-based deep RL framework, demonstrating its practicality on a variety of environments. On a POMDP that satisfies our assumptions, each term of the bound decays at its predicted rate. Our results provide a practical and theoretically grounded route for bridging theory and practice within online decision-making in POMDPs.

Figures & tables

Figure 1: Particle beliefs for the unobserved velocity of a double integrator LQR over the last 1000 steps. Mean, 10th and 90th quantiles visualized. Beliefs track the state when the system is stable.

Figure 2: Cumulative reward above the baseline rollout in four HeartSteps scenarios varying the positive intervention effect and the delayed negative measurement effect or proxy $O_{t}$ informativeness. Mean and 2.5%/97.5% quantiles over five seeds.

Environment	Doeblin	$g_{\min}>0$	Finite ${\mathcal{A}}$	Bounded $r$	Role
Mixing Tiger (Sec. 5 )	✓	✓	✓	✓	theory-valid
Active sensing (App. F )	✓	$\sim$	✓	✓	structural diagnostic
Box search (App. F )	$\times$	$\times$	✓	✓	$g_{\min}=0$ by design
HeartSteps	$\sim$	$\sim$	✓	✓	not claimed
Double-integrator LQR	✓	$\times$	$\times$	$\times$	filtering diagnostic
MuJoCo	$\times$	$\times$	$\times$	$\times$	heuristic demonstration

Table 1: Which experiments satisfy the assumptions of Theorem 1 . ✓: holds;

\times

: fails;

\sim

: approx.

Term	Error at endpoints	Fitted	Predicted
Particle filtering, $J=8\to 512$	$0.144\to 0.012$	$J^{-0.59}$	$J^{-1/2}$
Monte Carlo, $N=4\to 512$	$0.171\to 0.015$ (RMSE)	$N^{-0.50}$	$N^{-1/2}$
Structural, $d=0\to 12$	$0.314\to 0.0216$	$0.80$ per level	$\gamma=0.80$
Estimation (online MLE), $\sum_{t\leq T}\varepsilon_{\mathrm{opt}}(t)$		$T^{0.57}$	$\sqrt{T}$

Table 2: Fitted vs. predicted rates on mixing Tiger; Theorem 1 gives slower

J^{-1/(2\kappa_{\mathrm{pf}})}

T^{3/4}

Figure 3: Partial-observation MuJoCo learning curves in the low-sample regime: smoothed means with 95% Student-

t

bands over five seeds (Ant: three seeds for corrected PF-MCTQ; the submitted configuration, dashed, shows its two seeds as thin lines). Ant PF-MCTQ shows the 10-episode rolling training return; others, per-episode returns. Dotted: the submitted 3k-step cutoff; none extrapolated.

Appendix figures & tables23 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Snapshot of belief state at select training checkpoints. State recovery improves over time.

Figure 5: Posterior panel over five seeds for the double integrator LQR, over the last 1000 steps. The 10th quantile and 90th quantile are visualized. In this setting, only the magnitude, but not the direction, latent state is identifiable from the current observations alone. With no access to memory, the particle belief state still exhibits the ability to tracking the belief state, as seen in seeds 2 and 4, but fails when the state rapidly diverges. This suggests that the particle belief can be used in tandem with memory for latent state recovery..

Figure 6: Belief mean panel over five seeds for LQR. The MLP backbone diverges, while the GRU backbone converges.

Figure 7: Cumulative reward above the baseline rollout across the twelve HeartSteps scenarios. Panels vary the positive intervention effect (rows: minimal, small, medium) and the delayed negative measurement effect or proxy informativeness (columns: zero negative effect, minimal negative effect, small negative effect, and uninformative passive proxy $O_{t}$ ). Solid lines show the mean across runs and shaded bands show 2.5% and 97.5% quantiles. The never-measure RLSVI-SMC benchmark performs best in most scenarios because it is specifically matched to the linear-Gaussian HeartSteps structure and is given access to hand-specified linear features. PF-MCTQ also never measures, but must learn its model, actor, and critic from data using neural approximators, so it typically improves over baseline while trailing the tailored linear benchmark. Dyna-ATMQ often underperforms when measurement has delayed negative effects, especially when the positive intervention effect is weak, because it measures frequently and therefore gains latent-state information at the cost of worsening future engagement. Its relative performance improves when the positive effect is larger or when passive proxy information is unavailable and so direct measurements become more valuable.

Figure 8: Belief over the latent reward at three training checkpoints in HeartSteps. Rows show PF-MCTQ, the never-measure RLSVI-SMC benchmark, and Dyna-ATMQ; columns show days 27, 135, and 243. Each panel displays posterior particles, a kernel density estimate, the posterior interquartile range, and the posterior mean. The red vertical line marks the true latent reward. We see that Dyna-ATMQ having access to measurements of the environment gives it an informational advantage over the other two algorithms. On the other hand, the correct linear specification that RLSVI-SMC enjoys allows it to create a posterior that is close to Gaussian. PF-MCTQ, which has to estimate a dynamics model, actor, and critic, parameterized by neural networks, from the observed data, consequently has a much more expressive and multimodal posterior.

Figure 9: Latent-reward belief trajectories for HeartSteps scenario (a), shown separately by random seed. Columns compare PF-MCTQ, the never-measure RLSVI-SMC benchmark, and Dyna-ATMQ; rows show five independent seeds. Each panel plots the posterior median, interquartile range, and 10–90% interval for the latent reward, with the dashed red curve showing the true latent reward. All three methods track the latent reward at the level needed for control, but they express uncertainty differently. Never-measure produces comparatively narrow posteriors because it is tailored to the linear-Gaussian HeartSteps model and uses a conjugate SMC/RLSVI update. PF-MCTQ has wider and more variable posteriors because it must learn the transition model and value functions from data while never directly measuring the latent reward. Dyna-ATMQ also shows broad posterior support, but its belief remains centered near the true trajectory because it actively measures the latent reward on many days, partially collapsing uncertainty despite the coarser tabular approximation.

Hyperparameter	Value
Environment	LQR double integrator
Observed indices	$[0]$
Warmup steps	$256$
Initial model / policy updates	$100$ / $100$
Epochs / steps per epoch	$40$ / $256$
Model updates per epoch	$10$

Appendix

Table 3: Key hyperparameters for LQR.

Hyperparameter	Value
Environment	HeartSteps
User id / horizon	$0$ / $270$
Noise mode / observation noise	sequential / $0.0$
Warmup steps	$1024$
Initial model / policy updates	$10$ / $30$
Epochs / steps per epoch	$27$ / $10$

Appendix

Table 4: Key hyperparameters for HeartSteps.

Hyperparameter	Value
Environment	Ant
Observation variants	no position, no velocity
Observation noise / discount	$0.1$ / $0.99$
Warmup steps	$1000$
Initial model / policy updates	$2000$ / $10$
Epochs / steps per epoch	$164$ / $300$ (submitted: $10$ / $300$ )

Appendix

Table 5: Key hyperparameters for MuJoCo Ant, using the corrected configuration of Figure 3 . Values from the submitted version are given in parentheses where they differ.

Hyperparameter	Value
Environment	HalfCheetah
Observation variants	no position, no velocity
Observation noise / discount	$0.1$ / $0.99$
Warmup steps	$1000$
Initial model / policy updates	$1000$ / $10$
Epochs / steps per epoch	$50$ / $1000$

Appendix

Table 6: Key hyperparameters for MuJoCo HalfCheetah.

Hyperparameter	Value
Environment	Hopper
Observation variants	no position, no velocity
Observation noise / discount	$0.1$ / $0.99$
Warmup steps	$1000$
Initial model / policy updates	$1000$ / $10$
Epochs / steps per epoch	$50$ / $1000$

Appendix

Table 7: Key hyperparameters for MuJoCo Hopper.

Hyperparameter	Value
Environment	Walker2d
Observation variants	no position, no velocity
Observation noise / discount	$0.1$ / $0.99$
Warmup steps	$1000$
Initial model / policy updates	$1000$ / $10$
Epochs / steps per epoch	$50$ / $1000$

Appendix

Table 8: Key hyperparameters for MuJoCo Walker2d.

Figure 10: The three computational terms on the mixing Tiger. (a) Filtering error versus particles

J

(fitted slope

-0.59

). (b) Root-

Q

RMSE of the frozen-leaf estimator versus returns

N

(fitted slope

-0.50

). (c) Exact structural error versus belief lookahead depth

d

. The error contracts by a factor

0.80=\gamma

per level and stays below

\gamma^{d+1}\Xi_{\theta}/(1-\gamma)

. Means over

2000

replications in (a, b).

Figure 11: Estimation and structural terms. (a)

\varepsilon_{\mathrm{opt}}

and the model’s total-variation error versus model-estimation samples

n_{t}

, with an

n^{-1/2}

reference (fitted slopes

-0.59

and

-0.55

). (b) Cumulative estimation term

\sum_{t}\varepsilon_{\mathrm{opt}}(t)

versus rounds

T

, with a

T^{1/2}

reference (fitted slope

0.57

). (c) Structural error

\|\bar{V}_{d}-V^{\star}\|_{\infty}

32

instances versus belief lookahead depth

d

, below the envelope

\gamma^{d+1}\Xi/(1-\gamma)

(per-level contraction

0.798

–

0.800

Sensing accuracy $q$	QMDP ( $d=0$ )	$d=1$	$d=2$	$d=3$	Optimum
0.55	0.500	0.500	0.500	0.500	0.500
0.65	0.500	0.500	0.500	0.500	0.565
0.75	0.500	0.500	0.500	0.641	0.643
0.85	0.500	0.500	0.717	0.717	0.722
0.95	0.500	0.500	0.793	0.794	0.798

Appendix

Table 9: Active sensing: normalized return of the depth-

d

policy (exact computation).

$J$	8	16	32	64	128
Empirical collapse rate	.773	.602	.360	.128	.017
Analytic $(1-1/K)^{J}$	.776	.602	.362	.131	.017
Mean ESS $/J$	.032	.031	.031	.032	.031

Appendix

Table 10: Item search with

K=32

and

g_{\min}=0

: weight collapse versus particles

J

Figure 12: Stress tests illustrating the two mechanisms. (a) In active sensing, depths

0

–

1

never sense, while depths

2

–

3

approach the belief-optimal return when sensing is informative. (b) With exact observations over

K

boxes, the one-step filtering error grows when the particle set is too small to cover the observed box. (c) At

g_{\min}=0

, weight collapse matches

(1-1/K)^{J}

(

K=32

), which is also the decision-failure probability. Means over

10{,}000

replications in (b, c).

Planner	$d$	Calls per decision	Return
MCTQ, uniform	0	0	$5.04\pm 0.11$
MCTQ, uniform ( $=$ UCB1)	1	768	$5.06\pm 0.13$
POMCP	–	768 / 3072	$5.47$ / $5.52$
MCTQ, uniform	2	1536	$6.37\pm 0.27$
MCTQ, UCB1	2	1536	$6.96\pm 0.11$
Sparse-PFT, $J=64$	2	2688	$7.18\pm 0.08$

Appendix

Table 11: Active sensing (

\gamma=0.9

): return, mean

\pm

s.e. over three seeds of

40

episodes. The belief optimum scores

7.45\pm 0.20

and the exact QMDP policy

5.54\pm 0.32

Variant	Online model	Decay	UTD	$15$ k– $20$ k mean	At $20.1$ k
Submitted	No	$0.1$	$1$	$-279$	$-563$
Online model only	Yes	$0.1$	$1$	$-378$	$-834$
Online model + corrected decay	Yes	$10^{-4}$	$1$	$-259$	$-505$
Corrected + UTD $1/4$	Yes	$10^{-4}$	$1/4$	$902$	$881$
Corrected + UTD $1/10$	Yes	$10^{-4}$	$1/10$	$980$	$975$

Appendix

Table 12: Correction screen on position-hidden Ant (seed

0

): mean

10

-episode rolling return over

15

k–

20

k steps and at

20.1

k steps.

Figure 13: Correction screen on position-hidden Ant (seed

0

). “Corrected” denotes online model updates with weight decay

10^{-4}

; UTD

1/k

means one policy update per

k

environment steps. The shaded region is the

15

k–

20

k selection window, and the dotted line marks the original

3

k cutoff.

Hidden variable	Method	Seeds	Late return	Final evaluation
Position	PF-MCTQ, corrected	3	$893\pm 177$	$862\pm 178$
Position	PF-MCTQ, submitted	2	$-396$ ( $-506$ , $-287$ )	$-751$ ( $-1055$ , $-448$ )
Position	Recurrent SAC	5	$-123\pm 47$	not recorded
Position	GRU-PPO	5	$599\pm 147$	not recorded
Velocity	PF-MCTQ, corrected	3	$822\pm 268$	$767\pm 323$
Velocity	PF-MCTQ, submitted	2	$-518$ ( $-513$ , $-522$ )	$-625$ ( $-511$ , $-739$ )

Appendix

Table 13: Ant return over the prespecified

40

k–

49.2

k window. Values with

\pm

are means and 95% Student-

t

intervals. For the submitted configuration’s two complete seeds, parentheses show both seed values. Recurrent baselines have five seeds.

	Corrected (3 seeds)		Submitted (2 seeds)
Env. steps	Pos. hidden	Vel. hidden	Pos. hidden	Vel. hidden
3k	$825\pm 146$	$882\pm 60$	$908$ ( $945$ , $871$ )	$897$ ( $925$ , $870$ )
10.2k	$931\pm 61$	$934\pm 11$	$600$ ( $659$ , $541$ )	$435$ ( $606$ , $264$ )
20.1k	$959\pm 36$	$962\pm 15$	$-911$ ( $-563$ , $-1260$ )	$-620$ ( $-697$ , $-542$ )
49.2k	$868\pm 249$	$816\pm 241$	$-448$ ( $-678$ , $-217$ )	$-648$ ( $-708$ , $-589$ )
40k–49.2k mean	$893\pm 177$	$822\pm 268$	$-396$ ( $-506$ , $-287$ )	$-518$ ( $-513$ , $-522$ )

Appendix

Table 14: Ant checkpoints. Corrected: mean and 95% Student-

t

half-width over three seeds (

t_{2,0.975}=4.30

). Submitted: mean of the two complete seeds, with both seed values in parentheses. The last two rows are the mean over the prespecified

40

k–

49.2

k window and a final

10

-episode evaluation.

Method	Initialization (s)	Training s / 1k steps	Steps / s
PF-MCTQ (corrected)	86.3	15.8	63.4
PF-MCTQ (submitted cfg.)	92.9	41.7	24.0
Recurrent SAC	21.0	53.6	18.6
GRU-PPO	2.8	5.5	181.8

Appendix

Table 15: Wall-clock cost on Ant with the released code (position hidden, one RTX 3090).

Partially Observable RL

Partially observable reinforcement learning studies how agents act when observations hide the true state and decisions must use memory or beliefs.

See all 118 papers

Apr 1, 2026

Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs

We study model-based learning of finite-window policies in tabular partially observable Markov decision processes (POMDPs). A common approach to learning under partial observability is to approximate unbounded history dependencies using finite action-observation windows. This induces a finite-state Markov decision process (MDP) over histories, referred to as the superstate MDP. Once a model of this superstate MDP is available, standard MDP algorithms can be used to compute optimal policies, motivating the need for sample-efficient model estimation. Estimating the superstate MDP model is challenging because trajectories are generated by interaction with the original POMDP, creating a mismatch between the sampling process and target model. We propose a model estimation procedure for tabular POMDPs and analyze its sample complexity. Our analysis exploits a connection between filter stability and concentration inequalities for weakly dependent random variables. As a result, we obtain tight sample complexity guarantees for estimating the superstate MDP model from a single trajectory. Combined with value iteration, this yields approximately optimal finite-window policies for the POMDP.

Philip Jordan, Maryam Kamgarpour

SYCAMORE group, Institute of Mechanical Engineering, EPFL Switzerland.

Partially Observable Markov Decision Processes Policy Learning Model-Based RL Sample-Efficient RL

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

Oct 10, 2026

Belief Embedding Tree Search

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.

Christopher Solinas, Radovan Haluška, Martin Schmid +3

University of Alberta · Charles University, Prague · EquiLibre Technologies, Inc. +1

Partially Observable RL Belief-Space Planning Partially Observable Markov Decision Processes Monte Carlo Tree Search

Ask PDF

Abstract

Partially Observable RL

Explore similar work

Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs

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

Belief Embedding Tree Search