Problem

Evaluating risk-averse policies in Partially Observable Markov Decision Processes (POMDPs) is a critical challenge for developing reliable autonomous agents, yet it suffers from computational intractability. Exact solutions for POMDPs are infeasible in large state, observation, and action spaces, leading approximate methods to rely on computationally expensive simulations of future trajectories. While simplification techniques exist for expectation-based value functions, there has been limited exploration of risk-averse simplification, especially concerning coherent risk measures like Conditional Value-at-Risk (CVaR). A direct substitution of a complex POMDP model with a simplified one for CVaR evaluation can lead to inaccurate risk assessments, as the return distributions under the original and simplified models often differ significantly.

Method

This work introduces a theoretical framework designed to accelerate the evaluation of CVaR value functions in POMDPs, providing robust formal performance guarantees. The approach starts by deriving new mathematical bounds on the Conditional Value-at-Risk (CVaR) of a random variable (representing the true return) by utilizing an auxiliary random variable (representing the return from a simplified model). These bounds are based on assumptions about the relationship between their respective cumulative distribution and density functions. Building on this foundation, the paper establishes upper and lower bounds on the original CVaR value function, which can be computed from a simplified belief-MDP transition model. This simplified model is versatile enough to accommodate general simplifications of the transition dynamics, including reduced-complexity observation and state transition models. For practical application, estimators are developed to compute these bounds during online policy evaluation within a particle-belief MDP framework, along with probabilistic performance guarantees. A key application of these bounds is computational acceleration through action elimination: actions whose bounds indicate suboptimality under the simplified model can be safely discarded, ensuring consistency with the original POMDP. The methodology includes an offline-online decoupling strategy for estimating the distributional discrepancy, enabling online bound computation without real-time access to the full, complex original observation model.

Results

The empirical evaluation demonstrated the effectiveness of the proposed bounds across several standard POMDP domains, including 2D Light-Dark Navigation, Laser Tag, and Push environments. The results showed that the bounds derived from simplified observation models reliably distinguish between safe and dangerous policies, consistently enabling the elimination of suboptimal actions. Significant computational speedups were observed—approximately 20.89x in Light-Dark, 8.87x in Laser Tag, and 7.62x in Push—compared to methods using original observation models or prior CVaR bounds. These speedups remained consistent even when varying the number of return samples and planning horizons. The study also illustrated that the separation between bounds for safe and dangerous paths, and between a safe BetaZero policy and dangerous paths, was robust across different risk levels and planning horizons, confirming that the bound separation is driven by actual risk differences. Even in scenarios where the estimated distributional discrepancy exceeded the risk level, the bounds maintained sufficient tightness to effectively differentiate between action sequences.

Implications

This work provides a principled framework for accelerated risk-averse policy evaluation in POMDPs, significantly enhancing the feasibility of developing reliable autonomous agents in uncertain and partially observable environments. The derived mathematical foundations for bounding CVaR using an auxiliary random variable have broad analytical utility beyond the specific POMDP planning context. The demonstrated substantial computational speedups with minimal impact on policy performance can facilitate the real-time deployment of risk-aware policies in various practical and safety-critical applications. While the framework accommodates general belief-transition model simplifications, the empirical investigation of state-transition model simplifications is noted as a direction for future research. Acknowledged limitations include the potential for reduced effectiveness in very long-horizon problems due to accumulated distributional discrepancies, although some environments may exhibit sublinear growth of discrepancy. Additionally, the computational gains are contingent on the state-transition model being less expensive to sample from than the original observation model.