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

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.

Authors

Publication Details

Journal
Journal of Artificial Intelligence Research
Published
2026-11-13
DOI
https://doi.org/10.1613/jair.1.22332
Primary Topic
Reinforcement Learning in Robotics
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

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

Vadim Indelman, Yaacov Pariente
Journal of Artificial Intelligence Research
Reinforcement Learning in Robotics
article

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

Vadim Indelman, Yaacov Pariente
article en

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.

Journal of Artificial Intelligence ResearchVol. 87
Reinforcement Learning in Robotics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon