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

Yaacov Pariente; Vadim Indelman

math.STFeb 26, 2026

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

Authors: Yaacov Pariente, Vadim Indelman

Organizations: Technion - Israel Institute of Technology, Israel

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1. Overview of the proposed framework. The original POMDP yields the original CVaR value function. The simplified POMDP $M_{s}$ admits a simplified value function, related to the original via Theorem 6.2 . In practice, the simplified value function and distributional discrepancy are estimated from sample trajectories, yielding probabilistic computable bounds on the original value function (Theorem 7.4 ).

Panel of Figure 2 — Figure 2. Conceptual overview. Direct evaluation of $Q^{\pi}_{M}$ under the original model $M$ is computationally expensive. Instead, the simplified model $M_{s}$ is used to compute bounds on $Q^{\pi}_{M}$ , where the bound quality is governed by the distributional discrepancy $\epsilon$ between their belief transition models.

Panel of Figure 3 — Figure 3. Problem formulation illustrations. (a) The CVaR value function focuses on the tail of the return distribution, unlike the expected value. (b) The simplified model $P_{s}$ yields a computable CDF $F_{Y}$ , while the original CDF $F_{X}$ is intractable. When $|F_{X}(r)-F_{Y}(r)|\leq\epsilon$ , bounds on $\CVaR_{\alpha}(X)$ can be derived from $Y$ .

Panel of Figure 4 — Figure 4. Illustrations of bounds on $F_{X}(x)$ . (a) Bounds from Theorem 5.1 . (b) Bounds from Theorem 5.3 , where $g$ depends on $x$ and yields a tighter result than $F_{Y}(x)+\epsilon$ .

Panel of Figure 5 — Figure 5. Accumulation of distributional discrepancy over the planning horizon. Each bar represents the expected one-step TV distance $\mathbb{E}^{s}[\Delta^{s}(b_{t},a_{t})\mid b_{k},a_{k}]$ at time $t$ . The cumulative sum $\epsilon=\sum_{t=k}^{T-1}\Delta^{s}_{t}$ (dashed) governs the bound quality: when $\epsilon<\alpha$ (below the dash-dotted line), the CVaR bounds from Theorem 6.2 remain informative; when $\epsilon\geq\alpha$ , the bounds reduce to trivial extrema.

Panel of Figure 6 — Figure 6. Offline–online decoupling for distributional discrepancy estimation. In the offline phase, states are sampled from a proposal distribution $Q_{0}$ and the TV distances $\Delta^{s}$ are computed using the original observation model $p_{z}$ . During online planning, the precomputed $\Delta^{s}$ values are reweighted via importance sampling using only the state-transition model, eliminating the need to evaluate $p_{z}$ in real time.

Panel of Figure 7 — Figure 7. Illustration of bound-based action selection when $\epsilon^{\prime}\geq\alpha$ . (a) The agent chooses between a safe path (cost $\approx 1\times 2=2$ ) and a dangerous path through an obstacle (cost $\approx 100\times 2=200$ ). (b) Although the CVaR bounds collapse to $[\hat{d}_{\min},\hat{d}_{\max}]$ , the return estimators remain well-separated, enabling the agent to distinguish between the two paths.

Panel of Figure 8 — Figure 8. Figure 8a shows the bounds established in Theorem 5.7 , demonstrating how a simple truncated Normal distribution can be employed to bound the CVaR of a truncated GMM. Figure 8b illustrates the sensitivity of the CVaR bounds to the distributional discrepancy $\epsilon$ , showing how the bound interval widens as $\epsilon$ increases, while the true CVaR remains contained within the bounds. When $\epsilon$ exceeds the risk level $\alpha$ , the bounds become trivial, spanning the entire support; this is expected, as a large distributional discrepancy implies that the surrogate random variable $Y$ provides negligible information about the target random variable $X$ . Figure 8c presents a comparison of the sampling times for each distribution, while Figure 8d reports the total computation time required to sample from the truncated GMM and estimate its CVaR, in contrast to sampling from the truncated Normal surrogate and computing the associated concentration bounds. Figures 8a , 8c , and 8d were configured with confidence level $\alpha=0.2$ and probability of error $\delta=0.05$ . Figure 8b uses $\alpha=0.5$ . Figures 8c and 8d display 95% confidence intervals around the empirical means.

Panel of Figure 9 — Figure 9. Figures 9a , 9b , and 9c illustrate pairs of agent trajectories, consisting of a safe (orange) and a dangerous (blue) path. In Figure 9a , the agent moves from the lower-left to the upper-right goal location; the dangerous trajectory incurs higher cost. Figure 9b depicts trajectories in the Laser Tag environment, where the dangerous path traverses a high-cost region indicated in red. Figure 9c shows a similar pair of trajectories, with the dangerous path entering a hazardous region that leads to a terminal state. Across all three environments, the theoretical bounds on the values of the corresponding action sequences successfully discriminate between the safe and dangerous trajectories. Bounds are computed with probability of error $\delta=0.05$ .

Panel of Figure 10 — Figure 10. Sensitivity analysis of the computational acceleration with respect to the planning horizon and number of return samples, for Light-Dark (left), Laser Tag (center), and Push (right), with $\alpha=0.5$ . Rows 1–2: computation time and acceleration ratio as a function of the planning horizon. Rows 3–4: computation time and acceleration ratio as a function of the number of return samples. Error bars indicate 95% confidence intervals.

Panel of Figure 11 — Figure 11. Sensitivity of the CVaR bounds for the Light-Dark (left), Laser Tag (center), and Push (right) environments, using the complete safe (blue) and dangerous (red) action sequences depicted in Figure 9 ; solid and dashed lines indicate the upper and lower bounds, respectively. Rows 1–2: bounds as a function of the planning horizon with $\alpha=0.5$ and $\alpha=0.1$ , respectively. Row 3: bounds as a function of the risk level $\alpha$ at a fixed horizon. As the horizon increases, the accumulated distributional discrepancy grows, causing the bounds to widen. As $\alpha$ decreases (more risk-averse), the bounds increase and the bound intervals widen, yet they remain well separated between the safe and dangerous paths across the full range of $\alpha$ . Bounds are computed with probability of error $\delta=0.05$ .

Panel of Figure 12 — Figure 12. Evaluation of the BetaZero neural network policy against the safe and dangerous action sequences in the Light-Dark POMDP ( $\alpha=0.1$ , $H=9$ ), with bounds computed under the simplified observation model. Figure 12a : CVaR bounds for the dangerous sequence (blue), safe sequence (orange), and BetaZero policy (green). The bound intervals of the policy and dangerous sequence do not overlap, demonstrating that the bounds correctly identify the policy as less risky. Bounds are computed with probability of error $\delta=0.05$ . Figure 12b : agent trajectories; the BetaZero policy (green) and safe sequence (orange) navigate through the illuminated safe zones, while the dangerous sequence (blue) traverses the high-cost region.

Panel of Figure 13 — Figure 13. Sensitivity of the CVaR bounds (computed under the simplified observation model) for the BetaZero policy, safe sequence, and dangerous sequence in the Light-Dark POMDP; solid and dashed lines denote upper and lower bounds, respectively. Figure 13a : bounds as a function of the risk level $\alpha$ at horizon $H=9$ . Figure 13b : bounds as a function of the planning horizon at $\alpha=0.1$ . The dangerous sequence remains clearly separated from the policy and safe sequence across all conditions. Bounds are computed with probability of error $\delta=0.05$ .

Panel of Figure 14 — Figure 14. Computational speedup from evaluating CVaR bounds under the simplified observation model relative to the original model for the BetaZero policy in the Light-Dark POMDP ( $\alpha=0.1$ ). Row 1: computation time and speedup ratio as a function of the planning horizon. Row 2: computation time and speedup ratio as a function of the number of return samples. The simplified model achieves a consistent ${\approx}5\times$ speedup across all conditions. Error bars indicate $95\%$ confidence intervals.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 15. Illustration of the upper and lower bounds $F_{Y}^{U}$ and $F_{Y}^{L}$ on the cumulative distribution function $F_{X}$ .

Figure 16. Comparison of concentration inequalities for $\CVaR_{\alpha}(X)$ established by Theorem 5.5 (this work) and by Thomas and Learned-Miller, 2019 , evaluated on $\operatorname{Beta}(2,2)$ , $\operatorname{Beta}(0.5,0.5)$ , $\operatorname{Beta}(2,5)$ , $\operatorname{Beta}(5,2)$ , $\operatorname{Beta}(10,2)$ , $\operatorname{Beta}(2,10)$ , and $\operatorname{Laplace}(0,1)$ distributions. The two sets of bounds coincide for all tested distributions.

Aspect	Original	Simplified
Observation noise	Gaussian Mixture Model (GMM)	Isotropic Gaussian
Reward noise	Stochastic (Push, Laser Tag)	Deterministic

Appendix

Table 1. Architectural differences between the original and simplified models across all domains.

Parameter	Value
Grid size	$7\times 7$
Start state	$(1,\;1)$
Goal state	$(6,\;6)$ ; radius $1.5$
State transition covariance	$0.06\cdot I_{2}$
Obs. noise (far from beacon)	$\mathcal{N}(0,\;0.06\cdot I_{2})$ / GMM( $K{=}2500$ )
Obs. noise (near beacon)	$\mathcal{N}(0,\;0.03\cdot I_{2})$ / GMM( $K{=}2500$ , scaled)

Appendix

Table 2. Configuration for the 2D Light-Dark POMDP.

Parameter	Value
Grid size	$6\times 6$
Initial state	$(0.5,\;0.5,\;1.0,\;0.5,\;5.0,\;5.0)$
Robot transition covariance	$\mathrm{diag}(0.005,\;0.005)$
Observation noise $\sigma$	$0.1$ (on object position)
Push threshold	$1.0$
Friction coefficient	$0.3$

Appendix

Table 3. Configuration for the Continuous Push POMDP.

Parameter	Value
Arena	$11\times 7$ continuous grid
Walls	8 axis-aligned wall cells
Initial state	$(2.0,\;1.0,\;8.0,\;5.0,\;0)$
Robot transition covariance	$0.0125\cdot I_{2}$
Opponent transition covariance	$0.00625\cdot I_{2}$
Opponent pursuit speed	$0.6$

Appendix

Table 4. Configuration for the Continuous Laser Tag POMDP.

Parameter	Value
CVaR level $\alpha$	$0.1$
Belief particles $N_{p}$	$10$
Return samples $N_{r}$	$600$
$\Delta$ -estimation states	$100$
Samples per state (for $\Delta$ )	$2000$
$k$ -NN neighbours	$10$

Appendix

Table 5. Planner parameters shared across all three environments.

Parameter	Value
Number of Episodes	300
Steps per Episode	30 (max)
Planning Depth	2
Return Samples ( $N_{b}$ )	600
CVaR $\alpha$	0.5
Number of Particles ( $N_{p}$ )	10

Appendix

Table 6. Planning configuration for the Continuous Laser Tag experiments.

Parameter	Value
Number of Episodes	300
Steps per Episode	30 (max)
Planning Depth	2
Return Samples ( $N_{b}$ )	600
CVaR $\alpha$	0.5
Number of Particles ( $N_{p}$ )	10

Appendix

Table 7. Planning configuration for the Light-Dark experiments.

Parameter	Value
Number of Episodes	300
Steps per Episode	30 (max)
Planning Depth	2
Return Samples ( $N_{b}$ )	600
CVaR $\alpha$	0.5
Number of Particles ( $N_{p}$ )	10

Appendix

Table 8. Planning configuration for the Continuous Push experiments.

Parameter	Value
State dimension	2
Belief feature dimension	4 (= $2\times$ state dim)
Particles per belief $N_{p}$	500

Appendix

Table 9. Belief representation parameters for BetaZero on Light-Dark.

Feature	Mean	Std
$\bar{\mu}_{x}$	3.56	1.91
$\bar{\mu}_{y}$	4.12	1.91
$\bar{\sigma}_{x}$	0.302	0.407
$\bar{\sigma}_{y}$	0.303	0.408
Value output	$-24.34$	36.64

Appendix

Table 10. Input normalisation statistics for the BetaZero network.

Layer	Size
Input	4
Hidden 1	128
Hidden 2	128
Value head output	1 (scalar)
Policy head output	4 (one logit per action)

Appendix

Table 11. BetaZero network architecture.

Parameter	Value
Search depth	10
Simulations per step (training)	100
Simulations per step (inference)	1000
Exploration constant $c$	219.13 (tuned)
Temperature $\tau$	0.319 (tuned)
Value weight $z_{q}$	1.0

Appendix

Table 12. MCTS parameters for BetaZero on Light-Dark.

Parameter	Value
Outer iterations	50
Episodes per iteration	50
Total training episodes	2500
Episode length	20 steps
Data collection	Full MCTS rollouts
Replay buffer	5 iterations

Appendix

Table 13. BetaZero training loop parameters.

Parameter	Value
Optimizer	Adam
Learning rate	$10^{-4}$
Batch size	1024
Training epochs per iteration	50
Weight decay	$10^{-5}$
Loss	Cross-entropy (policy) + MSE (value)

Appendix

Table 14. Optimizer and loss configuration for BetaZero training.

Hyperparameter	Search range	Best value
$c$ (exploration constant)	$[1.0,\;10\times\Delta r]\approx[1,\;220]$	219.13
$\tau$ (temperature)	$[0.05,\;0.5]$	0.319
$z_{q}$ , $z_{n}$	fixed	1.0, 1.0

Appendix

Table 15. Hyperparameter search results for BetaZero on Light-Dark.

Partially Observable Markov Decision Processes

Partially Observable Markov Decision Processes study sequential decisions when agents must act from incomplete, noisy observations of hidden states.

See all 88 papers

Sep 26, 2026

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

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.

Yaacov Pariente, Vadim Indelman

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

Risk-Sensitive Planning Partially Observable Markov Decision Processes Belief-Space Planning Conditional Value-at-Risk

Ask PDF

Feb 3, 2026

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

Tail-end risk measures such as static conditional value-at-risk (CVaR) are used in safety-critical applications to prevent rare, yet catastrophic events. Unlike risk-neutral objectives, the static CVaR of the return depends on entire trajectories without admitting a recursive Bellman decomposition in the underlying Markov decision process. A classical resolution relies on state augmentation with a continuous variable. However, unless restricted to a specialized class of admissible value functions, this formulation induces sparse rewards and degenerate fixed points. In this work, we propose a novel formulation of the static CVaR objective based on augmentation. Our alternative approach leads to a Bellman operator with: (1) dense per-step rewards; (2) contracting properties on the full space of bounded value functions. Building on this theoretical foundation, we develop risk-averse value iteration and model-free Q-learning algorithms that rely on discretized augmented states. We further provide convergence guarantees and approximation error bounds due to discretization. Empirical results demonstrate that our algorithms successfully learn CVaR-sensitive policies and achieve effective performance-safety trade-offs.

Aneri Muni, Vincent Taboga, Esther Derman +2

Universit´e de Montr´eal, Quebec, Canada · Mila - Quebec AI Institute, Quebec, Canada · GERAD & Department of Decision Sciences, HEC Montr´eal, Quebec, Canada

Markov Decision Processes Q-Learning Risk-Sensitive RL Conditional Value-at-Risk

Ask PDF

Oct 19, 2026

Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games

Robust partially observable Markov decision processes model agents that act under partial observability while adversarial environment resolves uncertainty in the transition probabilities. Reward objectives such as discounted-sum, long-run average and cumulative reward under finite and infinite horizons allow quantifying the utility of an agent. We consider the problem of solving RPOMDPs under all four reward objectives, where the goal is to decide whether the value of a risk measure with respect to a reward objective exceeds a given threshold. We consider different risk measures, such as (1)~expected value, (2)~mean-variance (MV), (3)~conditional value-at-risk (CVaR), and (4)~entropic risk (ERisk). Our results can be summarized as follows. First, we formalize the class of law-invariant risk measures, that subsume all four risk measures above. Second, we propose a unified framework for solving RPOMDPs with discounted-sum, long-run average and cumulative reward objectives under any law-invariant risk measure, by reducing the problem to solving partially observable stochastic games (POSGs). Our unified framework applies to (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, which we show to be {\em equivalent} to POSGs, for each of the four reward objectives and any law-invariant risk measure. We prove equivalence by designing logspace reductions between the RPOMDP and POSG models, that map strategies to strategies and preserve the distribution of the reward objective, up to a constant rescaling factor. Third, as a corollary, we derive new computational complexity results for R(PO)MDPs and POSGs. In particular, we show that solving (s,a)-rectangular RMDPs is as hard as solving simple stochastic games.

Durgam Latha, Dion Reji, Dorde Zikelic +1

Indian Institute of Technology Bombay Mumbai, India · Nanyang Technological University Singapore, Singapore

Partially Observable Stochastic Games Robust Partially Observable Markov Decision Processes Robust Markov Decision Processes Partially Observable Markov Decision Processes Risk-Sensitive Planning Risk-Sensitive RL

Ask PDF

Abstract

Partially Observable Markov Decision Processes

Explore similar work

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

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

Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games