PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yaacov Pariente, Vadim Indelman

arXiv:2609.35874v1cs.AI

TL;DR

Expected-cost POMDP planning can mask dangerous states within a belief, while existing risk-averse methods focus on trajectory-level risk and require tailored algorithms. The paper applies CVaR to immediate cost while retaining expected cumulative return and standard planning structure. It reports risk-level-independent estimation guarantees, particle-surrogate and end-to-end bounds, and improved outcomes over expected-cost planners in the reported environments.

  • Problem

    Expected-cost POMDP planning can mask high-cost states within a belief, and existing value-function CVaR methods do not directly address that current-state uncertainty.

    Source: §1 · p. 1, §3.1 · p. 5

  • Method

    The method replaces expected immediate cost with CVaR over the current belief’s state distribution while retaining the standard expected cumulative return.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Across four environments, CVaR cost planners outperform expected-cost counterparts on both metrics; in ContinuousLaserTag, CVaRCost-POMCPOW reduces CVaR cost return by 97% (5.4 vs. 188.0).

    Source: §6 · p. 8

  • Takeaways & Limitations

    Changing only cost computation makes existing expectation-based POMDP planners risk-sensitive, with estimation bounds independent of α and an end-to-end guarantee from the true POMDP value to algorithmic estimates.

    Source: §1 · p. 2, §7 · p. 9

    Per-step CVaR does not directly control cumulative-return tails and may underestimate trajectory-level risk when costs have strong temporal correlations.

    Source: §7 · p. 9

Abstract

from arXiv · show

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 \emph{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.

1 Introduction

Expected-cost POMDP planners can overlook high-cost states within a belief, while existing risk-averse approaches target trajectory-level risk and require tailored algorithms. The paper applies CVaR to immediate cost, retaining standard MDP structure and deriving risk-level-independent estimation guarantees and end-to-end bounds.

1 Introduction

  • Expected-cost POMDP planners can mask dangerous belief states, selecting actions that are safe in expectation but catastrophic for part of the belief.This matters in safety-critical settings including robotics, autonomous driving, and medical decision-making.Source: §1 · p. 1
  • Prior risk-averse methods modify the value function to target trajectory-level risk, requiring tailored algorithms that cannot benefit from advances in expectation-based planners.The cited approaches include static CVaR, CVaR constraints, and Iterated CVaR (ICVaR) [2010].Source: §1 · p. 1
  • Retaining expected cumulative return preserves standard MDP structure, so existing POMDP planners can become risk-sensitive by changing only cost computation.The CVaR cost is deterministic given the particle belief, leaving standard Monte Carlo sampling error and Hoeffding bounds independent of α.Source: §1 · p. 2
  • CVaR applied to immediate cost targets the worst-α fraction of states under the current belief, addressing state uncertainty directly.Unlike chance constraints, it operates on the cost function and captures both frequency and severity of tail risk.Source: §1 · p. 2
  • The paper establishes finite-time guarantees for policy evaluation and sparse sampling, with estimation accuracy independent of α, plus particle-approximation and end-to-end guarantees.The particle approximation bounds place the 1/α factor as a multiplier rather than compounding it.Source: §1 · p. 2

2 Preliminaries

The preliminaries define CVaR, the belief-based POMDP cost, and the particle belief MDP used to approximate the belief space. They establish the concepts and particle representation used in the formulation.

2.1 Conditional Value-at-Risk

  • For confidence level α, VaR is the 1−α quantile, and CVaR for a continuous distribution is the conditional expectation above that threshold.The text also introduces CVaR estimation from i.i.d. and weighted samples.Source: §2.1 · p. 2

2.2 Partially Observable Markov Decision Process

  • A POMDP specifies states, actions, observations, transition and observation models, costs, discount, horizon, and initial belief; the agent updates its belief using Bayes’ rule.The conventional immediate cost is the state-action cost averaged over the current belief.Source: §2.2 · p. 3

2.3 Particle Belief MDP

  • The particle belief MDP approximates the infinite-dimensional belief space with particle beliefs and a transition model based on weighted particles sampled from prior predictive distributions.Its expected cost is computed as a normalized weighted sum of particle costs.Source: §2.3 · p. 3

3 Problem Formulation

The formulation replaces expected immediate cost with CVaR over states in the current belief, targeting per-step risk from hidden dangerous states. It contrasts this with return-level and future-belief CVaR formulations and retains compatibility with standard planning structure.

3 Problem Formulation

  • CVaR cost replaces expected cost under the true and particle beliefs with a measure of the worst-α fraction of states in each current belief.This is the proposed cost formulation for both the POMDP and its particle belief surrogate.Source: §3 · p. 3
  • In a POMDP, expected cost can mask dangerous states in the current belief, whereas CVaR pessimistically evaluates actions against its worst-α fraction.In a fully observable MDP, the immediate state-action cost is known exactly.Source: §3 · p. 3
  • Figure 1 depicts beliefs across the planning horizon and particle-cost histograms, with the worst-α tail selecting per-step CVaR cost.Safe steps have safe tails; at dangerous steps, high-cost particles enter the tail.Source: Figure 1 · p. 4
  • The stated goals are online policy evaluation and sparse-sampling algorithms with finite-time guarantees, and bounds on particle-approximation error propagation.The formulation also compares its target risk with existing CVaR approaches.Source: §3 · p. 4

3.1 Comparison with Prior CVaR Formulations

  • Static CVaR targets a bad total return but does not specifically address per-step danger from hidden states, and its Bellman equation requires tracking the return distribution.The text characterizes that tracking as making dynamic programming intractable.Source: §3.1 · p. 4
  • Dynamic CVaR targets transitions to bad future beliefs, while its immediate cost still averages over the current belief and its 1/α Lipschitz factor compounds across recursion levels.The cited bound scales as O((1/α)^(T−t) ) [2026b].Source: §3.1 · p. 5
  • CVaR cost applies the operator to the current belief’s state distribution, preserving standard MDP structure and preventing the 1/α factor from compounding through the horizon.Among the compared formulations, it directly addresses per-step danger from partial observability while remaining compatible with existing planners.Source: §3.1 · p. 5

4 CVaR Cost Planning Algorithms

The CVaR-cost formulation preserves standard MDP structure, so existing planners need only change their cost computation. Policy evaluation and sparse sampling inherit finite-time estimation guarantees that do not worsen with greater risk aversion.

4 CVaR Cost Planning Algorithms

  • Replacing expected immediate cost with CVaR cost lets existing MDP planning algorithms and their guarantees apply with only a cost-computation change.The CVaR cost is bounded and deterministic given the particle belief, so it cancels in the error decomposition; only Monte Carlo error from sampling successor beliefs remains.Source: §4 · p. 5, §4.1 · p. 5

4.1 Inherited Guarantees

  • Neither policy-evaluation nor sparse-sampling estimation bounds depends on α, so estimation accuracy does not degrade as the planner becomes more risk-averse.The estimation error scales as O(D^2); the O(γ^D) scaling applies to approximation bounds, not these estimation bounds.Source: §4.1 · pp. 5–6
  • Unlike the inherited guarantees here, ICVaR-based methods introduce a 1/α factor at each level, giving estimation error that scales as O((1/α)^(T−t)).The cited comparison says this can become vacuous for small α or long horizons.Source: §4.1 · p. 6

5 Particle Belief Approximation Guarantees

The paper bounds the gap between the true POMDP and its particle-belief surrogate by controlling per-step CVaR-cost discrepancies through cost-distribution error. Combining this approximation guarantee with a planner’s estimation guarantee yields an end-to-end POMDP guarantee.

5 Particle Belief Approximation Guarantees

  • Particle count controls weighted empirical CDF accuracy, while propagation depth contributes additional particle-belief error.The abstract bound assumes the distributional discrepancy remains below α at every depth on an event of probability at least 1−δ0.Source: §5 · p. 6
  • The particle-belief approximation bound controls the true POMDP–PB-MDP Q-gap through per-step CVaR-cost discrepancies, under the stated conditions and a bounded Rényi-divergence assumption.The theorem considers particles sampled from the prior predictive distribution and gives a probability guarantee; the supplied passage does not include the complete bound.Source: §5 · p. 7
  • At each depth, CVaR-cost error is controlled by the cost-CDF discrepancy, amplified by Δρ/α through CVaR’s 1/α-Lipschitz property.The discrepancy is the sup-norm difference between the true-belief cost CDF and the weighted empirical particle-belief CDF.Source: §5 · pp. 6–7
  • The CVaR sensitivity factor enters once as a multiplier rather than compounding across depths, whose discounted accumulation is captured by G_D+1.The bound also includes the d_max importance-weighting factor and a uniform-convergence term ε_approx from weighted DKW.Source: §5 · p. 7
  • Combining the surrogate-approximation guarantee with any PB-MDP planner’s estimation guarantee yields an end-to-end POMDP guarantee.Both estimation bounds are independent of α; the approximation term is the only source of α-dependence in the end-to-end guarantee.Source: §5 · p. 7

6 Experiments

Across four environments, CVaR-cost planners outperform expected-cost planners on both reported metrics and beat ICVaR baselines in most planner-environment pairs. Results also reveal a safety–task-completion trade-off in PushPOMDP, while performance is strong with fewer particles than the theorem’s sufficient condition requires.

Experimental setup

  • The comparison covers four dangerous-region POMDP environments, six planner variants, and 500 episodes per configuration.The six variants are expected-cost, CVaR-cost, and ICVaR versions of PFT-DPW and POMCPOW.Source: §6 · p. 8

Results

  • CVaRCost-POMCPOW reduces ContinuousLaserTag CVaR cost return by 97% (5.4 vs. 188.0) and danger-area entries to 0.04 vs. 4.03.Expected reward is zero in danger zones, which are therefore invisible to expected-cost planners.Source: §6 · p. 8, Table 1 · p. 9
  • In PushPOMDP, CVaR-cost variants reduce obstacle collisions to 1.78 and 1.66 vs. 2.79–2.83 for baselines, but goal rates fall to 27–33% vs. 59–71%.At α = 0.1, the planner may detour or abort because progress requires routing the pushed object near the obstacle.Source: §6 · p. 8
  • Across all four environments, CVaR-cost planners outperform expected-cost counterparts on both metrics and beat ICVaR baselines in most cells; the exceptions are ICVaR-POMCPOW on LightDark and ContinuousLaserTag.The reported metrics are CVaR cost return and dangerous encounters.Source: §6 · pp. 8–9, Table 1 · p. 9
  • The CVaR-cost modification works with both PFT-DPW and POMCPOW, while tuned ICVaR planners achieve competitive returns in some settings but require environment-specific tuning.ICVaR-POMCPOW scores 58.6 in LightDark and 8.1 in ContinuousLaserTag.Source: §6 · pp. 8–9

Extended results and ablations

  • At α = 1, CVaR-cost planning recovers risk-neutral performance; its advantage is robust across particle counts from 50 to 500 and also yields the best static CVaR across environments.The reported evaluation uses 200 particles and a four-second planning timeout per step; the sufficient condition in Theorem 5.2 is more demanding at α = 0.1, though experiments perform strongly below it.Source: §6 · pp. 8–9

7 Conclusion

The paper presents a modular risk-sensitive POMDP approach with estimation bounds independent of α and particle-belief approximation bounds with an additive 1/α factor. It notes that per-step CVaR may underestimate trajectory-level risk under strong temporal cost correlations.

Conclusion

  • Applying CVaR to immediate cost while retaining expected cumulative return makes existing POMDP planners risk-sensitive through a cost-definition change alone.The paper reports estimation bounds independent of α and particle-belief approximation bounds where the 1/α factor enters additively.Source: §7 · p. 9

Limitations and future work

  • Per-step CVaR does not directly control cumulative-return tails and may underestimate trajectory-level risk when costs have strong temporal correlations.The paper identifies adaptive α selection and analysis for MCTS with adaptive sampling as future directions.Source: §7 · p. 9

Broader Impact

  • The authors state that the work aims to make autonomous systems safer by accounting for tail risks in safety-critical domains.They foresee no negative societal impacts.Source: §7 · p. 10

A Proof of Theorem 4.1

The proof bounds estimation error by separating Monte Carlo sampling error from propagated estimation error. The immediate CVaR cost cancels because it is deterministic given the particle belief, leaving standard sampling error for concentration bounds.

Final Bound

  • The proof proceeds by induction, unrolls the recursive error bounds, and sets ηt = δ to obtain a finite-time bound with confidence 1 − δ.The initial error decomposition and recursive bounds are combined before unrolling.Source: A Proof of Theorem 4.1 · pp. 12–13

Error Decomposition

  • The proof decomposes estimation error into Monte Carlo sampling error and propagated estimation error; the deterministic CVaR cost cancels between theoretical and estimated Q-functions.The remaining sampling error is bounded using Hoeffding’s inequality.Source: A Proof of Theorem 4.1 · p. 12

Inductive Proof

  • At the terminal horizon, the error is zero because both the terminal value and its estimate are zero.The proof uses this as the base case for induction over the horizon.Source: A Proof of Theorem 4.1 · p. 12
  • At each induction step, the propagated value has range at most (T − t)∆ρ, since it sums at most T − t CVaR costs, each with range bounded by ∆ρ.The proof combines this range bound with Hoeffding concentration and a union bound over sampled successor beliefs.Source: A Proof of Theorem 4.1 · pp. 12–13

B Proof of Theorem 4.2

The appendix proof handles action-wise estimation with union bounds, establishes a CVaR Lipschitz bound and a weighted DKW bound, then couples true and particle beliefs along shared state trajectories to bound value error.

B Proof of Theorem 4.2

  • For Theorem 4.2, the induction must hold simultaneously over actions, so union bounds add |A| factors to failure probabilities while leaving the error recursion unchanged.The factors arise from bounds over actions and over |A|·Nb successor beliefs.Source: B Proof of Theorem 4.2 · p. 14

C CVaR Lipschitz Property

  • The CVaR Lipschitz lemma relates CVaR differences to CDF discrepancy for variables supported on [cmin, cmax], using the Wasserstein-1 distance and range ∆ρ.The cited property gives CVaRα a 1/α Lipschitz factor with respect to W1.Source: C CVaR Lipschitz Property · p. 14

D Weighted DKW Bound

  • The weighted DKW bound concerns a belief and its importance-weighted particle approximation, with weights wi = b(xi)/q(xi) and bounded density ratio d∞.The proof controls the self-normalized empirical CDF by bounding its unnormalized average and weight normalization.Source: D Weighted DKW Bound · pp. 15–16

E.1 State Trajectory Coupling

  • The state-trajectory coupling treats the true belief and particle belief at each depth as deterministic functions of the same trajectory ω.The proof uses this shared trajectory to compare the corresponding Q-functions.Source: §E.1 · p. 16

E.2 Proof of Theorem 5.1

  • When the CDF discrepancy at each step is below α, the CVaR Lipschitz bound controls per-step cost differences, yielding a bound that holds for every trajectory in the specified good event.Because the resulting right-hand side does not depend on ω, taking expectations preserves the bound.Source: §E.2 · pp. 16–17

E.3 Completing the Proof of Theorem 5.2

The proof establishes a particle-belief approximation bound using trajectory coupling and, alternatively, backward induction. The alternative bound separates CVaR-cost discrepancy from observation-distribution mismatch.

E.3 Completing the Proof of Theorem 5.2

  • The coupling proof applies a union bound over D + 1 time steps to obtain a particle-count condition for the approximation bound.For a fixed policy and query action, the CDF discrepancy need only hold for one action at each step.Source: §E.3 · p. 17

F Alternative Approximation Bound via Induction

  • The two-source bound controls the approximation error from CVaR-cost discrepancy and observation-distribution mismatch, with probability at least 1 − 2(T − t + 1)δ0.It applies under the stated assumptions, including εC < α.Source: F Alternative Approximation Bound via… · pp. 17–18
  • Backward induction propagates the error as βℓ = λα + µ + γβℓ+1, with terminal value βT = λα.The two terms represent the CVaR-cost and observation-shift contributions, alongside the discounted recursive discrepancy.Source: F Alternative Approximation Bound via… · p. 18
  • The induction proof bounds immediate CVaR-cost discrepancy at the terminal step before extending the error bound recursively to earlier steps.The terminal bound is βT = λα.Source: F Alternative Approximation Bound via… · p. 18

G Extended Results

The extended results report strong static tail-risk performance for CVaR-cost planners, while expected-return effects vary by environment. Ablations examine risk-level and particle-count sensitivity, and the experiments use independently tuned planner parameters.

G Extended Results

  • Across environments, CVaR-cost planners achieve the best static CVaR of cumulative return, while their expected-return effects vary by environment.Table 2 reports 500-episode results; its expected-return metric uses standard immediate cost, while static CVaR is computed over episode returns.Source: G Extended Results · pp. 18–19, Table 2 · p. 19

H.1 Sensitivity to Risk Level α

  • At α = 1, CVaRCost-PFT-DPW and PFT-DPW match within overlapping confidence intervals in LightDark (109.9 vs. 107.3) and ContinuousLaserTag (13.6 vs. 14.6).In ContinuousLaserTag, at α = 0.01, CVaRCost-PFT-DPW has CVaR cost return ≈20 or lower across α ≤ 0.5, while PFT-DPW reaches 167.1.Source: §H.1 · pp. 19–20, Figure 2 · p. 20

H.2 Sensitivity to Particle Count Np

  • At Np = 100 in LightDark, CVaRCost-PFT-DPW has CVaR cost return 498.0 versus 912.6 for PFT-DPW; its advantage persists across tested particle counts.In ContinuousLaserTag, both planners’ CVaR cost return increases at Np = 500, which the authors attribute likely to reduced effective search depth under the fixed timeout.Source: §H.2 · p. 20, Figure 3 · p. 20

I Hyperparameter Tuning

  • Planners were tuned independently for each environment with 50 Optuna trials, and the better of tuned and default parameters was selected.Table 3 reports the final hyperparameters used in the experiments.Source: I Hyperparameter Tuning · p. 21, Table 3 · p. 21

J Bounding V π

Because realized state trajectories do not reconstruct the observation-conditioned beliefs, direct evaluation of the per-step CVaR value from those trajectories alone is unavailable. The section derives population bounds and finite-sample certificates from rollout costs.

J Bounding V π

  • Realized state trajectories alone cannot directly evaluate Vπ because they do not reconstruct the posterior beliefs needed for per-step CVaR costs.The posterior depends on observation history and belief-defining importance reweighting.Source: J Bounding V π · p. 21
  • The law of total CVaR gives a population upper bound on Vπ, while conditional CVaR being at least the conditional mean supplies a companion lower bound.The bounds are expressed using marginal step-cost distributions under the policy.Source: J Bounding V π · pp. 21–23
  • Independent realized rollouts yield finite-sample certificates: DKW and CVaR’s 1/α-Lipschitz property bound the upper arm, while Hoeffding’s inequality bounds the lower arm.The certificate width scales as O(GT ∆ρ/(α√Nep)) on the lower arm; the asymmetric 1/α factor appears only in the upper bound.Source: J Bounding V π · pp. 23–24
  • As Nep → ∞, the gap between the data-driven bounds contracts to a population sandwich that is zero precisely when conditional step-cost distributions given beliefs are almost surely point masses.This corresponds to fully informative beliefs.Source: J Bounding V π · p. 24
Loading 2609.35874v1…