Risk-Averse Online POMDP Planning via CVaR of the Immediate Cost with Performance Guarantees

Yaacov Pariente; Vadim Indelman

cs.AISep 26, 2026

Risk-Averse Online POMDP Planning via CVaR of the Immediate Cost with Performance Guarantees

Authors: Yaacov Pariente, Vadim Indelman

Organizations: Faculty of Mathematics Technion – Israel Institute of Technology Haifa, Israel · Stephen B. Klein Faculty of Aerospace Engineering; Faculty of Data and Decision Sciences Technion – Israel Institute of Technology Haifa, Israel

Abstract

Online POMDP planners optimize the expected cumulative cost, which can mask dangerous states when the belief places significant mass on high-cost states. Existing risk-averse methods apply static or dynamic Conditional Value at Risk (CVaR) to the value function, capturing trajectory-level risk, but share two gaps: (i) by retaining the immediate cost as an expectation of a state-dependent cost over the belief, the risk within the belief is left unaddressed; and (ii) by modifying the value function, they require new tailored algorithms rather than reusing existing expectation-based planners. We instead apply CVaR to the immediate cost over the belief at each step, directly targeting per-step uncertainty about the current state. The standard expected cumulative return is retained as the objective, so the resulting problem has a standard MDP structure: any expectation-based POMDP planner can be made risk-sensitive by changing only the cost computation. We inherit finite-time guarantees for policy evaluation and sparse sampling---with estimation error independent of the risk level---and, as our central theoretical result, prove a finite-time bound on the gap between the particle belief MDP surrogate and the original POMDP, which together yield an end-to-end guarantee from the true POMDP value to the algorithmic estimate. In the risk-neutral limit, the formulation recovers standard expectation-based planning.

Figures & tables

Panel of Figure 1 — Figure 1: Structure of the CVaR cost return during navigation. Top : beliefs $\bar{b}_{k}$ evolve along the planning horizon. Middle : particle cost histograms—the worst- $\alpha$ fraction (right of the dashed threshold) determines the CVaR cost. At steps where all particles are safe (green boxes, e.g., $t{+}1$ and $T$ ), the tail is also safe; at steps with dangerous states (red boxes, e.g., $t$ and $t{+}2$ ), the tail captures high-cost particles. Bottom : corresponding navigation scenes—the robot maintains a particle belief (blue dots), with red dots marking particles in dangerous states. Safe steps show all-blue beliefs; dangerous steps show the outlier particles that drive the CVaR cost. The return $G_{t}^{\pi}(\alpha)$ sums these per-step CVaR costs $\rho_{\alpha}$ with discount $\gamma^{k-t}$ .

Environment	Planner	CVaR Cost Return	Danger Encounters	Goal Rate
LightDark	PFT-DPW	$777.7\pm 26.8$	$2.16\pm 0.09$	$100\%$
	ICVaR-PFT-DPW	$250.5\pm 24.1$	$0.97\pm 0.11$	$100\%$
	CVaRCost-PFT-DPW	$\mathbf{144.8\pm 11.1}$	$\mathbf{0.61\pm 0.07}$	$100\%$
	POMCPOW	$820.3\pm 26.7$	$2.28\pm 0.09$	$100\%$
	ICVaR-POMCPOW	$58.6\pm 6.6$	$0.31\pm 0.06$	$100\%$
	CVaRCost-POMCPOW	$\mathbf{87.9\pm 6.5}$	$\mathbf{0.45\pm 0.06}$	$100\%$

Table 1: CVaR cost return (mean

\pm

95% CI), dangerous encounters, and goal rate across 500 episodes. Lower CVaR cost return and fewer dangerous encounters indicate safer behavior. Dangerous encounters are: obstacle hits (LightDark), obstacle collisions (PushPOMDP), danger area steps (ContinuousLaserTag), and ghost collisions (PacMan). Goal rate is not applicable (—) for PacMan, which is an infinite-horizon pursuit-evasion task with no terminal goal state.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Environment	Planner	$\mathbb{E}[G]$	$\text{CVaR}_{0.1}[G]$	CVaR Cost Return	Danger	Goal
LightDark	PFT-DPW	$-96.1\pm 15.3$	$-463.4$	$777.7\pm 26.8$	$2.16\pm 0.09$	$100\%$
	ICVaR-PFT-DPW	$-49.1\pm 9.6$	$-290.5$	$250.5\pm 24.1$	$0.97\pm 0.11$	$100\%$
	CVaRCost-PFT-DPW	$\mathbf{-30.1\pm 6.5}$	$\mathbf{-186.1}$	$\mathbf{144.8\pm 11.1}$	$\mathbf{0.61\pm 0.07}$	$100\%$
	POMCPOW	$-104.1\pm 15.3$	$-451.9$	$820.3\pm 26.7$	$2.28\pm 0.09$	$100\%$
	ICVaR-POMCPOW	$-21.1\pm 3.5$	$-76.6$	$58.6\pm 6.6$	$0.31\pm 0.06$	$100\%$
	CVaRCost-POMCPOW	$\mathbf{-23.3\pm 3.6}$	$\mathbf{-86.2}$	$\mathbf{87.9\pm 6.5}$	$\mathbf{0.45\pm 0.06}$	$100\%$

Appendix

Table 2: Extended results across 500 episodes with

\alpha=0.1

\gamma=0.95

\mathbb{E}[G]

: expected cumulative return (mean

\pm

95% CI).

\text{CVaR}_{0.1}[G]

: static CVaR of the cumulative return distribution (point estimate; confidence intervals omitted due to high variance of this tail statistic). CVaR Cost Return, Danger Encounters, and Goal Rate are as in Table 1 .

Figure 2: CVaR cost return vs. risk level $\alpha$ for PFT-DPW (risk-neutral) and CVaRCost-PFT-DPW on LightDark (left) and ContinuousLaserTag (right). Error bars show 95% confidence intervals over 300 episodes. At $\alpha=1$ , both planners converge to the same performance, confirming that CVaR cost recovers standard expectation-based planning.

Figure 3: CVaR cost return vs. particle count $N_{p}$ for PFT-DPW (risk-neutral) and CVaRCost-PFT-DPW on LightDark (left) and ContinuousLaserTag (right). Error bars show 95% confidence intervals over 300 episodes. Fixed $\alpha=0.1$ .

Environment	Planner	Depth	Expl. Const.	$k_{a}$	$\alpha_{a}$	$k_{o}$	$\alpha_{o}$
LightDark	PFT-DPW	2	9534.9	1	0.28	6	0.49
	CVaRCost-PFT-DPW	2	650.3	10	0.50	10	0.22
	ICVaR-PFT-DPW	2	9657.0	6	0.01	1	0.19
	POMCPOW	15	8000.9	6	0.35	6	0.36
	CVaRCost-POMCPOW	2	11595.5	4	0.48	7	0.46
	ICVaR-POMCPOW	3	5659.7	10	0.39	1	0.19

Appendix

Table 3: Tuned hyperparameters per (environment, planner) pair. All planners use

\gamma=0.95

\alpha=0.1

N_{p}=200

particles, and 4-second planning timeout.

Risk-Sensitive Planning

See all 24 papers

Accelerated Online Risk-Averse Policy Evaluation in POMDPs with Theoretical Guarantees and Novel CVaR Bounds
Feb 26, 2026Yaacov Pariente, Vadim IndelmanPartially Observable Markov Decision Processes Policy Evaluation
Technion - Israel Institute of Technology, Israel
POMDPPlanners: Open-Source Package for POMDP Planning
Feb 24, 2026Yaacov Pariente, Vadim IndelmanPartially Observable Markov Decision Processes Decision-Making under Uncertainty
Faculty of Mathematics, Technion - Israel Institute of Technology, Haifa 3200003, Israel · Stephen B. Klein Faculty of Aerospace Engineering, Faculty of Data and Decision Sciences, Technion - Israel Institute of Technology, Haifa 3200003, Israel
Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity
Feb 3, 2026Aneri Muni, Vincent Taboga, Esther Derman +2Markov Decision Processes Q-Learning
Universit´e de Montr´eal, Quebec, Canada · Mila - Quebec AI Institute, Quebec, Canada · GERAD & Department of Decision Sciences, HEC Montr´eal, Quebec, Canada

Feb 26, 2026J/K move · Enter open · S save

Accelerated Online Risk-Averse Policy Evaluation in POMDPs with Theoretical Guarantees and Novel CVaR Bounds

Yaacov Pariente, Vadim Indelman

Technion - Israel Institute of Technology, Israel

Partially Observable Markov Decision Processes Policy Evaluation Risk-Sensitive RL Conditional Value-at-Risk

Open paper AskPDF arXiv

Risk-averse decision-making under uncertainty in partially observable domains is a central challenge in artificial intelligence and is essential for developing reliable autonomous agents. The formal framework for such problems is the partially observable Markov decision process (POMDP), where risk sensitivity is introduced through a risk measure applied to the value function, with Conditional Value-at-Risk (CVaR) being a particularly significant criterion. However, solving POMDPs is computationally intractable in general, and approximate methods rely on computationally expensive simulations of future agent trajectories. This work introduces a theoretical framework for accelerating CVaR value function evaluation in POMDPs with formal performance guarantees. We derive new bounds on the CVaR of a random variable X using an auxiliary random variable Y, under assumptions relating their cumulative distribution and density functions; these bounds yield interpretable concentration inequalities and converge as the distributional discrepancy vanishes. Building on this, we establish upper and lower bounds on the CVaR value function computable from a simplified belief-MDP, accommodating general simplifications of the transition dynamics. We develop estimators for these bounds within a particle-belief MDP framework with probabilistic guarantees, and employ them for acceleration via action elimination: actions whose bounds indicate suboptimality under the simplified model are safely discarded while ensuring consistency with the original POMDP. Empirical evaluation across multiple POMDP domains confirms that the bounds reliably separate safe from dangerous policies while achieving substantial computational speedups under the simplified model.

Abstract

Risk-Sensitive Planning

Explore similar work

Accelerated Online Risk-Averse Policy Evaluation in POMDPs with Theoretical Guarantees and Novel CVaR Bounds

POMDPPlanners: Open-Source Package for POMDP Planning

Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity