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

Abstract

Background: Risk-averse decision-making under partial observability involves evaluating a risk measure, such as the Conditional Value-at-Risk (CVaR), of the cumulative return, a computationally demanding task in POMDPs.

Objectives: This work introduces a framework for accelerating CVaR value function evaluation by replacing the original POMDP dynamics with a computationally tractable surrogate model while providing formal performance guarantees.

Methods: As the mathematical foundation, we derive bounds on the CVaR of a random variable X using an auxiliary random variable Y under assumptions relating their cumulative distribution functions. We introduce a truncation decomposition that separates CVaR estimation from n samples into a data-driven term -- bounded at rate O(1/√n) without support knowledge -- and a tail correction where the support bound enters only through an O(1/n) term, strictly improving existing concentration bounds. These bounds are further tightened via local CDF concentration parameters that exploit the quantile structure of CVaR. Building on this foundation, 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 sample-based estimators for computing these bounds during online policy evaluation with probabilistic performance guarantees. These bounds enable computational acceleration via action elimination: actions whose bounds indicate suboptimality under the simplified model are safely discarded while ensuring consistency with the original POMDP.

Results: Empirical evaluation across multiple POMDP domains confirms that the bounds reliably distinguish safe from dangerous policies while achieving 9-21× computational speedups on the evaluated benchmarks.

Conclusions: The proposed framework provides a principled and practical approach for accelerating risk-averse policy evaluation in POMDPs, with theoretical guarantees and significant computational gains demonstrated across multiple domains.