Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability

Valentina Zaccaria; Philip Jordan; Tingting Ni; Gian Antonio Susto; Maryam Kamgarpour

cs.LGOct 15, 2026

Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability

Authors: Valentina Zaccaria, Philip Jordan, Tingting Ni, Gian Antonio Susto, Maryam Kamgarpour

Organizations: University of Padova · SYCAMORE, EPFL

Abstract

We study reinforcement learning in constrained partially observable Markov decision processes (CPOMDPs), where an agent maximizes reward subject to a cost constraint using only incomplete information about the underlying state. The lack of state observability may require optimal policies to depend on arbitrarily long observation-action histories, making planning and learning challenging. We leverage recent advances in finite-memory approximations of POMDPs and represent finite history windows as states of a constrained MDP. We then develop a primal--dual algorithm that provides the first non-asymptotic guarantees that jointly bound average reward suboptimality and constraint violation in the original CPOMDP. A key challenge is that this finite-window approximation affects both reward values and the set of feasible policies. Under a filter-stability assumption, we derive bounds relating optimality and feasibility in the finite-state model to those in the original CPOMDP, with approximation errors that decay geometrically with the window length. Experiments in partially observable gridworlds demonstrate the effectiveness of our approach.

Figures & tables

Panel of Figure 1 — Figure 1: Comparison between the CPOMDP $\mathcal{P}$ (top) and the superstate CMDP $\mathcal{M}^{g}$ (bottom). The truncation operator $\mathbb{G}_{l}$ maps the full history $h_{t}$ to the superstate $g_{t}$ by retaining the length- $l$ suffix, which is then treated as the observed state of $\mathcal{M}^{g}$ .

Figure 2: Gridworld: Green cell is the goal, orange cells are unsafe, and $\times$ is initial position. Arrows are an approximately optimal policy computed using SARSOP Kurniawati et al., (2008) , with lengths proportional to action probabilities.

Figure 3: Algorithm performance for different history lengths

l

. Solid curves show the mean, shaded regions show the evaluation uncertainty.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Performance of Algorithm 1 in the finite-history superstate model for different values of

K

and

l

Figure 5: Performance of using exact oracle vs TD(0) learning oracle in Algorithm 1 . Average optimality gap (left) and average constraint violation (right). The iterates are evaluated in the CPOMDP .

Panel of Figure 6 — Figure 6: Effect of superstate constraint tightening. Average optimality gap (left) and average constraint violation (right). The iterates are evaluated in the CPOMDP . History length $l=3$ .

Policy	Reward	Cost
Approx. constrained CPOMDP	$3.426\pm 0.013$	$0.684\pm 0.004$
Approx. unconstrained POMDP	$3.898\pm 0.020$	$1.302\pm 0.013$
Exact constrained CMDP	$4.162$	$0.692$

Appendix

Table 1: Model-based planning references. SARSOP-based values are reported with 95% confidence intervals. The constraint threshold is

d^{o}\simeq 0.692

Panel of Figure 7 — Figure 7: Approximate constrained CPOMDP policy obtained using SARSOP (left) and exact fully observable policy (right). Their respective expected cumulative reward values are $3.426$ and $4.162$ , while their cost values are $0.684$ and $0.692$ . Arrow lengths are proportional to action probabilities.

	Average reward		Constraint violation
$l$	Constr.	Unconstr.	Constr.	Unconstr.
0	1.599	0.685	0.682	1.158
1	1.885	1.889	0.541	0.695
2	2.750	2.901	0.331	0.840
3	3.175	2.958	0.299	1.504
4	3.329	3.534	0.237	0.922

Appendix

Table 2: Constrained and unconstrained policies evaluated in the original CPOMDP after

K=10^{4}

iterations. Reported values are averages over four random seeds. Constraint violations are computed relative to

d^{o}\simeq 0.692

Figure 8: Performance of Algorithm 1 under partial observability for different values of

K

and

l

, compared with its fully observable performance (black line).

Panel of Figure 9 — Figure 9: Performance of Algorithm 1 in the CPOMDP for different values of $K$ and $l$ using the stepsizes required by Theorem 1 . Left: $\frac{1}{K}\sum_{k=0}^{K-1}V_{r^{o}}^{\pi^{k}}(\rho^{o})$ . Right: $\left[\frac{1}{K}\sum_{k=0}^{K-1}V_{c^{o}}^{\pi^{k}}(\rho^{o})-d^{o}\right]_{+}$ .

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,661 papers

PriPG-RL: Privileged Planner-Guided Reinforcement Learning for Partially Observable Systems with Anytime-Feasible MPC
Apr 9, 2026Mohsen Amiri, Mohsen Amiri, Ali Beikmohammadi +2Partially Observable RL Learning Using Privileged Information
The authors are with the Department of Computer and System Science, Stockholm University, 11419 Stockholm, Sweden · The authors are with the School of Mechanical and Material Engineering, Washington State University, Pullman, WA 99164, USA
Near-Optimal Sample Complexity for Online Constrained MDPs
Feb 16, 2026Chang Liu, Yunfan Li, Lin F. YangConstrained RL Safe RL
University of California, Los Angeles
Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs
Apr 1, 2026Philip Jordan, Maryam KamgarpourPartially Observable Markov Decision Processes Policy Learning
SYCAMORE group, Institute of Mechanical Engineering, EPFL Switzerland.

Apr 9, 2026J/K move · Enter open · S save

PriPG-RL: Privileged Planner-Guided Reinforcement Learning for Partially Observable Systems with Anytime-Feasible MPC

Mohsen Amiri, Mohsen Amiri, Ali Beikmohammadi, Sindri Magnuśson+1

The authors are with the Department of Computer and System Science, Stockholm University, 11419 Stockholm, Sweden · The authors are with the School of Mechanical and Material Engineering, Washington State University, Pullman, WA 99164, USA

Partially Observable RL Learning Using Privileged Information Partially Observable Markov Decision Processes Model Predictive Control

Open paper AskPDF arXiv

This paper addresses the problem of training a reinforcement learning (RL) policy under partial observability by exploiting a privileged, anytime-feasible planner agent available exclusively during training. We formalize this as a Partially Observable Markov Decision Process (POMDP) in which a planner agent with access to an approximate dynamical model and privileged state information guides a learning agent that observes only a lossy projection of the true state. To realize this framework, we introduce an anytime-feasible Model Predictive Control (MPC) algorithm that serves as the planner agent. For the learning agent, we propose Planner-to-Policy Soft Actor-Critic (P2P-SAC), a method that distills the planner agent's privileged knowledge to mitigate partial observability and thereby improve both sample efficiency and final policy performance. We support this framework with rigorous theoretical analysis. Finally, we validate our approach in simulation using NVIDIA Isaac Lab and successfully deploy it on a real-world Unitree Go2 quadruped navigating complex, obstacle-rich environments.

Abstract

Reinforcement Learning

Explore similar work

PriPG-RL: Privileged Planner-Guided Reinforcement Learning for Partially Observable Systems with Anytime-Feasible MPC

Near-Optimal Sample Complexity for Online Constrained MDPs

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