Paper deep dive

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

Yaacov Pariente, Vadim Indelman

Year: 2026Venue: arXiv preprintArea: math.STType: PreprintEmbeddings: 189

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%

Last extracted: 7/20/2026, 9:24:17 AM

Summary

This paper introduces a theoretical framework for accelerating online risk-averse policy evaluation in Partially Observable Markov Decision Processes (POMDPs) using Conditional Value-at-Risk (CVaR). The authors derive novel bounds on the CVaR of a random variable using an auxiliary random variable with known distributional discrepancies. These bounds are applied to simplified belief-MDP models to establish computable upper and lower bounds on the original POMDP's value function. The framework enables safe action elimination during online planning, providing probabilistic performance guarantees and significant computational speedups while maintaining consistency with the original POMDP dynamics.

Entities (8)

CVaR · metric · 99%Vadim Indelman · person · 99%Yaacov Pariente · person · 99%POMDP · model · 98%Technion · organization · 97%Action Elimination · technique · 94%Belief-MDP · model · 92%Particle-Belief MDP · model · 90%

Relation Signals (6)

Yaacov Pariente → affiliatedwith → Technion

confidence 99% · Yaacov Pariente Technion - Israel Institute of Technology

Vadim Indelman → affiliatedwith → Technion

confidence 99% · Vadim Indelman Technion - Israel Institute of Technology

CVaR → isusedin → POMDP

confidence 95% · risk sensitivity is introduced through a risk measure applied to the value function, with Conditional Value-at-Risk (CVaR) being a particularly significant criterion.

Action Elimination → uses → CVaR Bounds

confidence 94% · employ them for acceleration via action elimination: actions whose bounds indicate suboptimality... are safely discarded

Simplified Belief-MDP → providesboundsfor → Original POMDP

confidence 93% · establish upper and lower bounds on the CVaR value function computable from a simplified belief-MDP

Particle-Belief MDP → supports → Estimators

confidence 90% · We develop estimators for these bounds within a particle-belief MDP framework

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

187,594 characters extracted from source content.

Expand or collapse full text

Accelerated Online Risk-Averse Policy Evaluation in POMDPs with Theoretical Guarantees and Novel CVaR Bounds Yaacov Pariente Technion - Israel Institute of TechnologyHaifaIsrael and Vadim Indelman Technion - Israel Institute of TechnologyHaifaIsrael Abstract. Risk-averse decision-making under uncertainty in partially observable domains represents a central challenge in artificial intelligence and is essential for developing reliable autonomous agents. The formal framework for such problems is typically the partially observable Markov decision process (POMDP), where risk sensitivity is introduced through a risk measure applied to the value function. Among these, the Conditional Value-at-Risk (CVaR) has emerged as a particularly significant criterion. However, solving POMDPs is computationally intractable in general, and approximate solution methods rely on computationally expensive simulations of possible future agent trajectories. This work introduces a theoretical framework for accelerating the evaluation of CVaR value functions in POMDPs while providing formal performance guarantees. As the mathematical foundation, we derive new bounds on the CVaR of a random variable X using an auxiliary random variable Y, under assumptions relating their respective cumulative distribution and density functions; these bounds yield interpretable concentration inequalities and converge as the distributional discrepancy vanishes. 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—including reduced-complexity observation and transition models. We develop estimators for computing these bounds during online policy evaluation within a particle-belief MDP framework and provide probabilistic performance guarantees. These bounds are employed for computational 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. †copyright: none 1. Introduction Autonomous agents have emerged as a cornerstone of modern intelligent systems, with applications spanning healthcare, disaster response, education, industrial automation, and decentralized systems. From autonomous aerial vehicles coordinating firefighting efforts to multi-agent systems executing complex financial transactions, these agents are designed to perceive, reason, and act without continuous human oversight. However, ensuring that such systems behave safely and reliably in uncertain and partially observable environments remains a central challenge. In these settings, risk-aware decision-making frameworks, particularly those grounded in partially observable Markov decision processes (POMDPs), provide a principled foundation for modeling uncertainty and enforcing safety through explicit risk-sensitive optimization (Marecki and Varakantham, 2010; Hou et al., 2016; Ahmadi et al., 2023). Exact solution methods for POMDPs become computationally intractable when the state, observation, and action spaces are large (Papadimitriou and Tsitsiklis, 1987a). To address this fundamental limitation, approximate planning algorithms utilize forward search trees constructed via simulation of future agent trajectories (Silver and Veness, 2010; Sunberg and Kochenderfer, 2018). The sampling procedure is guided by the underlying reward function, which provides evaluative feedback for action selection. This approach enables practical online planning in partially observable domains by trading off solution optimality for computational tractability. Risk-averse decision-making frameworks in the literature encompass three primary approaches: distributionally robust optimization, which hedges against distributional uncertainty (Xu and Mannor, 2010); chance-constrained programming, which enforces probabilistic feasibility constraints (Rodrigues Quemel e Assis Santana et al., 2016; Moss et al., 2024b); and risk metric integration, wherein a risk measure—such as Conditional Value-at-Risk (CVaR)—is incorporated directly into the value function (Chow et al., 2015). Risk metric integration is particularly appealing when the risk measure is coherent, as coherent risk measures satisfy fundamental axioms—monotonicity, translation invariance, positive homogeneity, and subadditivity—that ensure rational and consistent behavior under aggregation and scaling of uncertain returns. These properties are especially important in sequential decision-making, where returns accumulate over time and diversification across stochastic outcomes should not be penalized. Moreover, coherence guarantees convexity of the resulting objective, enabling tractable optimization and facilitating theoretical analysis. Among coherent risk measures, CVaR has emerged as a widely adopted choice due to its explicit focus on tail risk and its compatibility with robust and distributional formulations. In the latter framework, CVaR is computed over the cumulative return, defined as the sum of stage-wise costs across the planning horizon. Chance-constrained and CVaR-based formulations reflect different perspectives on risk in sequential decision problems. Chance constraints enforce probabilistic restrictions on state visitation, thereby preventing the agent from entering undesirable regions of the state space. Conversely, CVaR optimization targets the tail risk of the cumulative return, prioritizing mitigation of poor reward realizations. These objectives are complementary rather than interchangeable. Consider, for instance, an online algorithmic trading problem wherein the environment reward is defined as the percentage portfolio gain relative to the preceding portfolio value, and the state is characterized by current asset prices. In this setting, CVaR optimization of returns directly addresses the trader’s primary objective—managing downside risk in cumulative gains—whereas formulating the problem as a chance constraint on state space would be less natural and potentially misaligned with the risk management goal. Another example arises in sequential decision-making problems with multiple objectives, such as a navigating robot that must account for fuel availability, obstacles, and related operational constraints. In such settings, optimizing the cumulative reward provides a principled means of jointly accommodating all constraints. Current state-of-the-art POMDP planning algorithms remain computationally demanding, as they rely on extensive sampling from the original POMDP dynamics. To mitigate this issue, the simplification approach replaces the true POMDP dynamics with a computationally tractable surrogate model, which is then employed during planning while still admitting performance guarantees relative to the original dynamics. Simplification techniques for expectation-based value functions are already available (Lev-Yehudi et al., 2024; Barenboim and Indelman, 2023; Zhitnikov et al., 2025) and have been shown to accelerate POMDP planning. However, risk-averse simplification has remained largely unexamined; the only existing contribution in this direction employs a non-coherent risk measure (Zhitnikov and Indelman, 2022), which offers weaker justification for risk-averse decision making (Majumdar and Pavone, 2020). We begin by establishing the mathematical foundations of this work, deriving several CVaR bounds for a random variable X using an auxiliary random variable Y, under assumptions relating their respective CDFs and PDFs. Although not all of these theoretical results are employed in our practical applications, they form a foundational framework that we expect will support future research on simplification. Building on these foundations, we analyze the relationship between the original value function—defined as the CVaR of the return—and its simplified belief transition-model counterpart. In particular, we establish lower and upper bounds on the original value function in terms of the simplified value function and provide corresponding performance guarantees. We then develop estimators for computing these bounds during online planning and derive performance guarantees for these estimators as well. The primary contributions of this work are as follows: • Derivation of bounds on the CVaR of a random variable X given another random variable Y. These bounds enable the approximation of CVaRα⁡(X)CVaR_α(X) when direct access to X is limited. They also yield interpretable concentration inequalities that characterize the CVaR of X through the CVaR of Y under an adjusted confidence level, and we establish convergence of these bounds as the distributional discrepancy vanishes. • Derivation of lower and upper bounds on the theoretical value function in risk-averse POMDPs expressed through the action-value function from a simplified belief-MDP transition model, with corresponding bounds for simplified observation models. • Estimators for evaluating the simplified bounds during online planning, with probabilistic performance guarantees on the deviation between the theoretical action-value function and its estimated bounds computed using simplified belief-MDP and observation models within a particle-belief MDP framework. • Application of the derived bounds to computational acceleration via action elimination, in which actions whose bounds indicate suboptimality are safely discarded, and empirical demonstration of substantial speedups with negligible degradation in policy performance across multiple POMDP domains. ModelsTheory (Sec. 5–6)Estimation (Sec. 7)Original POMDPMMCVaR value function(original)Simplified POMDPMsM_sCVaR value function(simplified)Sample-basedestimatesProbabilisticcomputable bounds Bounds (Thm. 6.2) sampleThm. 7.4 Figure 1. Overview of the proposed framework. The original POMDP yields the original CVaR value function. The simplified POMDP MsM_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). An overview of the proposed framework is depicted in Figure 1. The remainder of this paper is organized as follows. Section 2 reviews related work. Section 3 introduces the necessary preliminaries on POMDPs, particle belief MDPs, and CVaR estimation. Section 4 formulates the problem of bounding the risk-averse value function under a simplified belief-transition model. Section 5 derives the foundational CVaR bounds using auxiliary random variables. Section 6 establishes value function bounds for the static CVaR value function under general and observation-model simplifications. Section 7 develops online estimators for computing these bounds during planning and provides corresponding performance guarantees. Section 8 discusses the limitations of the framework. Section 9 presents the experimental evaluation across multiple POMDP domains. Section 10 concludes the paper. Proofs and additional experimental details are provided in the appendix. 2. Related Work Conditional Value at Risk (CVaR) (Rockafellar et al., 2000) is a principled and extensively studied risk measure with broad applicability across domains involving uncertainty. A central property of CVaR is its dual representation (Artzner et al., 1999), which allows it to be interpreted as the expected loss in the worst-case tail of a cost distribution (Chow et al., 2015). Unlike Value at Risk (VaR), which identifies only the quantile threshold of extreme losses at a chosen confidence level, CVaR quantifies both the probability and the magnitude of such losses, yielding a more comprehensive assessment of risk. This property makes CVaR especially relevant in safety-critical decision-making contexts, where both the occurrence and severity of adverse outcomes are significant. Moreover, CVaR satisfies the axioms of coherent risk measures—such as subadditivity and positive homogeneity—ensuring consistent and rational aggregation of risk across time and decision stages (Artzner et al., 1999). Practical estimators of CVaR are supported by concentration inequalities and deviation guarantees from the true risk value (Brown, 2007; Thomas and Learned-Miller, 2019), further reinforcing its reliability in applied decision-making problems. Risk can be incorporated into planning under uncertainty through multiple paradigms, including chance constraints (Ono et al., 2015), exponential utility functions (Koenig and Simmons, 1994), distributionally robust optimization (Xu and Mannor, 2010; Osogami, 2015; Cubuktepe et al., 2021), and quantile regression methods (Dabney et al., 2018). Among these, distributionally robust formulations are particularly aligned with CVaR optimization, as both emphasize resilience to rare but high-impact events (Chow et al., 2015). Risk measures map random cost variables to real-valued evaluations and are expected to satisfy fundamental axioms to ensure interpretability and consistency (Majumdar and Pavone, 2020). Coherent risk measures, by satisfying these axioms, provide a principled foundation for incorporating CVaR into sequential decision-making. General coherent risk formulations have been employed as optimization objectives in POMDPs, constrained MDPs, and shortest-path problems (Ahmadi et al., 2021b, 2020, a; Dixit et al., 2023), where CVaR arises as a key special case. Specifically, (Chow et al., 2015) introduced the CVaR-MDP framework, defining the value function as the CVaR of the return and deriving a value-iteration-based solution with formal error guarantees. Simplification techniques for POMDPs aim to reduce computational complexity while retaining performance guarantees, thereby facilitating real-time deployment of POMDP-based policies in practical systems (Papadimitriou and Tsitsiklis, 1987b). Simplification refers to replacing one or more POMDP components with computationally tractable approximations while providing formal performance guarantees that ensure decision quality with respect to the original model. For instance, (Lev-Yehudi et al., 2024) examined simplification of the observation model by introducing a less expensive surrogate while establishing finite-sample convergence bounds. Similarly, (Barenboim and Indelman, 2026) studied simplification of the state and observation spaces, providing deterministic performance guarantees and integrating them into state-of-the-art solvers. Furthermore, (Zhitnikov and Indelman, 2022) examined the simplification of belief-dependent rewards and provided deterministic guarantees under the Value at Risk (VaR) criterion. However, VaR is not a coherent risk measure and therefore lacks several essential properties for principled risk-averse decision making. More broadly, the simplification of risk-averse planning remains largely unexplored, with (Zhitnikov and Indelman, 2022) being the only prior work in this direction. To the best of our knowledge, no prior work has addressed the problem of bounding the CVaR of a random variable using an auxiliary random variable with a known distributional discrepancy, which constitutes a key contribution of this work. 3. Preliminaries 3.1. Partially Observable Markov Decision Process A finite-horizon Partially Observable Markov Decision Process (POMDP) is formally defined as the tuple (X,A,Z,T,O,c,b0)(X,A,Z,T,O,c,b_0), where X, A, and Z denote the state, action, and observation spaces, respectively. The transition model T(xt+1∣xt,at)≜P(xt+1∣xt,at)T(x_t+1 x_t,a_t) P(x_t+1 x_t,a_t) specifies the conditional probability of transitioning from state xtx_t to xt+1x_t+1 given action ata_t, while the observation model O(zt∣xt)≜P(zt∣xt)O(z_t x_t) P(z_t x_t) defines the likelihood of observing ztz_t when the system is in state xtx_t. The belief space B is the set of all probability distributions over X, and the stage-wise cost function is given by c:B×A→ℝc:B× A . At each time step t, the agent maintains a belief bt∈Bb_t∈ B, representing the posterior distribution over the latent state conditioned on the history of observations and actions. The history is denoted by Ht=z1:t,a0:t−1,b0H_t=\z_1:t,a_0:t-1,b_0\, and the belief update is defined as bt(xt)≜P(xt∣Ht)b_t(x_t) P(x_t H_t) for each xt∈Xx_t∈ X. A policy πt:B→A _t:B→ A is a measurable mapping that prescribes the action at=πt(bt)a_t= _t(b_t) based on the current belief state. The immediate expected cost under belief btb_t and action ata_t is (1) c(bt,at)≜x∼bt[cx(x,at)],c(b_t,a_t) _x b_t[c_x(x,a_t)], where cx(x,at)c_x(x,a_t) denotes the state-dependent cost, bounded as Rmin≤cx(x,at)≤RmaxR_ ≤ c_x(x,a_t)≤ R_ . The cumulative cost, or return, over a finite horizon T∈ℕT is given by (2) Rt:T≜∑τ=tTc(bτ,aτ),R_t:T _τ=t^Tc(b_τ,a_τ), which serves as the performance criterion starting at time t. The value function associated with policy π and initial belief bkb_k is (3) Vπ(bk)≜[Rk:T∣bk,π]=∑t=kT[c(bt,at)∣bk,π],V^π(b_k) [R_k:T b_k,π]= _t=k^TE[c(b_t,a_t) b_k,π], and the corresponding action-value function is (4) Qπ(bk,ak)≜zk+1[c(bk,ak)+Vπ(bk+1)∣bk,ak].Q^π(b_k,a_k) _z_k+1\! [c(b_k,a_k)+V^π(b_k+1) b_k,a_k ]. A POMDP can equivalently be formulated as a fully observable belief-MDP (BMDP), in which the belief btb_t serves as the state variable and is a sufficient statistic for the interaction history. In this formulation, the dynamics are governed by a belief transition kernel induced by the latent state-transition and observation models. Formally, the belief-MDP associated with a POMDP M is defined as (5) MB≜(ℬ,A,τ,ρ,γ),M_B (B,A,τ,ρ,γ), where ℬ≜Δ(X)B (X) denotes the space of probability distributions over the latent state space X, A is the action space, τ denotes the belief-transition kernel, ρ is the expected cost, and γ is the discount factor. Given the state-transition and observation models, the belief-transition model of the belief-MDP is given by (6) P(bt+1|bt,at)=∫xt∈X∫xt+1∈X∫zt+1∈ZP(xt+1|xt,at)P(zt+1|xt+1)bt(xt)xtxt+1zt+1.P(b_t+1|b_t,a_t)= _x_t∈ X _x_t+1∈ X _z_t+1∈ ZP(x_t+1|x_t,a_t)P(z_t+1|x_t+1)b_t(x_t)dx_tdx_t+1dz_t+1. This BMDP formulation is exact but generally intractable, since the belief space ℬB is infinite-dimensional, motivating approximate representations such as particle belief MDPs. 3.2. Particle Belief MDP In order to estimate the theoretical action-value function, we consider a particle belief MDP (PB-MDP) setting. Formally, denote by MP≜(Σ,A,τ,ρ,γ)M_P ( ,A,τ,ρ,γ) the PB-MDP that is defined with respect to the POMDP M (Lim et al., 2023) and Np∈ℕN_p , where • Σ≜b¯:b¯=(xi,wi)i=1Np,xi∈X,∀i,wi≥0,∃i such that wi>0 \ b: b=\(x_i,w_i)\_i=1^N_p,x_i∈ X,∀ i,w_i≥ 0,∃ i such that w_i>0\ is the state space over the particle beliefs. • A is the action space as defined in the POMDP M. • τ(b¯t+1|b¯t,a)τ( b_t+1| b_t,a) is the belief transition probability, for a∈A,b¯∈Σa∈ A, b∈ . • ρ(b¯,a)≜∑j=1Npwjc(xj,a)∑j=1Npwjρ( b,a) _j=1^N_pw_jc(x_j,a) _j=1^N_pw_j is the belief-dependent cost. • γ as defined in the POMDP M. This belief estimator maintains a finite set of state particles that serve as an approximation to the theoretical belief, which, in principle, may involve an infinite number of states. 3.3. Conditional Value-at-Risk Let X be a random variable defined on a probability space (Ω,ℱ,P)( ,F,P), where ℱF is the σ-algebra, and P:ℱ→[0,1]P:F→[0,1] is a probability measure. Assume further that [|X|]<∞E[|X|]<∞. We denote the cumulative distribution function (CDF) of the random variable X by FX(x)=P(X≤x)F_X(x)=P(X≤ x). The value at risk at confidence level α∈(0,1)α∈(0,1) is the 1−α1-α quantile of X, i.e., (7) VaRα⁡(X)≜infx∈ℝ:FX(x)>1−αVaR_α(X) \x :F_X(x)>1-α\ For simplicity we denote qαX=VaRα⁡(X)q_α^X=VaR_α(X) or qαF=VaRα⁡(X)q_α^F=VaR_α(X). The conditional value at risk (CVaR) at confidence level α is defined as (Rockafellar et al., 2000) (8) CVaRα⁡(X)≜infw∈ℝw+1α[(X−w)+]|w∈ℝ,CVaR_α(X) _w \w+ 1αE[(X-w)^+]|w \, where (x)+=max⁡(x,0)(x)^+= (x,0). For a smooth F, it holds that (Pflug, 2000) (9) CVaRα⁡(X)=[X|X>VaRα⁡(X)]=1α∫1−α1F−1(v)v.CVaR_α(X)=E[X|X>VaR_α(X)]= 1α _1-α^1F^-1(v)dv. Let Xi∼iidFX_i iid F for i∈1,…,ni∈\1,…,n\. Denote by (10) C^α(X)≜C^α(Xii=1n)≜infx∈ℝx+1nα∑i=1n(Xi−x)+ C_α(X) C_α(\X_i\^n_i=1) _x \x+ 1nα _i=1^n(X_i-x)^+ \ the estimate of CVaRα⁡(X)CVaR_α(X) (Brown, 2007). Theorem 3.1, that bounds the deviation of the estimated CVaR and the true CVaR, was proved in (Brown, 2007). Theorem 3.1. If supp(X)⊆[a,b]supp(X) [a,b] and X has a continuous distribution function, then for any δ∈(0,1]δ∈(0,1], (11) P(CVaRα⁡(X)−C^α(X)>(b−a)5ln⁡(3/δ)αn)≤δ,P (CVaR_α(X)- C_α(X)>(b-a) 5 (3/δ)α n )≤δ, (12) P(CVaRα⁡(X)−C^α(X)<−(b−a)αln⁡(1/δ)2n)≤δ.P (CVaR_α(X)- C_α(X)<- (b-a)α (1/δ)2n )≤δ. The estimator in (10) can be expressed as (13) C^α(X)=X(n)−1α∑i=1n−1(X(i)−X(i−1))(in−(1−α))+, C_α(X)=X^(n)- 1α _i=1^n-1(X^(i)-X^(i-1)) ( in-(1-α) )^+, where X(i)X^(i) is the iith order statistic of X1,…,XnX_1,…,X_n in ascending order (Thomas and Learned-Miller, 2019). The results presented in Theorems 3.2 and 3.3, following the work of (Thomas and Learned-Miller, 2019), yield tighter bounds on the CVaR compared to those established by (Brown, 2007). Theorem 3.2. If X1,…,XnX_1,…,X_n are independent and identically distributed random variables and Pr⁡(X1≤b)=1 (X_1≤ b)=1 for some finite b, then for any δ∈(0,0.5]δ∈(0,0.5], (14) Pr⁡(CVaRα⁡(X1)≤Zn+1−1α∑i=1n(Zi+1−Zi)(in−ln⁡(1/δ)2n−(1−α))+)≥1−δ, (CVaR_α(X_1)≤ Z_n+1- 1α _i=1^n(Z_i+1-Z_i) ( in- (1/δ)2n-(1-α) )^+ )≥ 1-δ, where Z1,…,ZnZ_1,…,Z_n are the order statistics (i.e., X1,…,XnX_1,…,X_n sorted in ascending order), Zn+1=bZ_n+1=b, and x+≜max⁡0,xx^+ \0,x\ for all x∈ℝx . Theorem 3.3. If X1,…,XnX_1,…,X_n are independent and identically distributed random variables and Pr⁡(X1≥a)=1 (X_1≥ a)=1 for some finite a, then for any δ∈(0,0.5]δ∈(0,0.5], (15) Pr⁡(CVaRα⁡(X1)≥Zn−1α∑i=0n−1(Zi+1−Zi)(min⁡1,in+ln⁡(1/δ)2n−(1−α))+)≥1−δ, (CVaR_α(X_1)≥ Z_n- 1α _i=0^n-1(Z_i+1-Z_i) ( \1,\, in+ (1/δ)2n \-(1-α) )^+ )≥ 1-δ, where Z1,…,ZnZ_1,…,Z_n are the order statistics (i.e., X1,…,XnX_1,…,X_n sorted in ascending order), Z0=aZ_0=a, and x+≜max⁡0,xx^+ \0,x\ for all x∈ℝx . Notably, Theorems 3.2 and 3.3 require only one-sided boundedness of the support and do not assume continuity of the distribution function, in contrast to Theorem 3.1, which requires both two-sided boundedness and a continuous distribution. The restriction to δ∈(0,0.5]δ∈(0,0.5] is mild in practice, as it corresponds to confidence levels of at least 50%50\%. 4. Problem Formulation In this work, we adopt a risk-averse formulation in which, instead of optimizing the expected return as in (3) and (4), the value function is defined as the CVaR of the return. Let α∈(0,1)α∈(0,1), and denote the original POMDP by M. The value and action-value functions at time k are defined by (16) VMπ(bk,α)≜CVaRαP⁡[∑t=kTc(bt,π(bt))|bk,π], V^π_M(b_k,α)\! \!CVaR_α^P[ _t=k^T\!c(b_t,π(b_t))|b_k,π], (17) QMπ(bk,ak,α)≜CVaRαP⁡[c(bk,ak)+∑t=k+1Tc(bt,π(bt))|bk,π]. Q^π_M(b_k,a_k,α) _α^P[c(b_k,a_k)+ _t=k+1^Tc(b_t,π(b_t))|b_k,π]. Figure 3a illustrates the difference between the standard expected value function and the CVaR value function. We consider cases in which the belief-MDP transition model is simplified for computational tractability. Let ΩB _B be the sample space of the belief random variable and let Ω≜ΩBT−k+1 _B^T-k+1 denote the corresponding product space, endowed with a σ-algebra ℱF. We define two probability measures P,Ps:ℱ→[0,1]P,P_s:F→[0,1] on the measurable space (Ω,ℱ)( ,F), corresponding to the original and simplified belief models, respectively. The CDF of Rk:TR_k:T under the original model is (18) P(Rk:T≤l|bk,π)=∫bk+1:T∈BT−kP(Rk:T≤l|bk:T,π)∏i=k+1TP(bi|bi−1,π)dbk+1:T,P(R_k:T≤ l|b_k,π)= _b_k+1:T∈ B^T-k\!\!P(R_k:T≤ l|b_k:T,π) _i=k+1^TP(b_i|b_i-1,π)db_k+1:T, and the simplified CDF of Rk:TR_k:T is defined using only the simplified belief transition model: (19) Ps(Rk:T≤l|bk,π)=∫bk+1:T∈BT−kP(Rk:T≤l|bk:T,π)∏i=k+1TPs(bi|bi−1,π)dbk+1:T.P_s(R_k:T≤ l|b_k,π)= _b_k+1:T∈ B^T-k\!\!P(R_k:T≤ l|b_k:T,π) _i=k+1^TP_s(b_i|b_i-1,π)db_k+1:T. The belief-MDP transition model is defined using the state transition and observation models. Hence, simplification of the belief-MDP transition model is general enough to include simplifications of state and observation models simultaneously. Denote the simplified POMDP by MsM_s. The value and action-value functions corresponding to MsM_s are denoted by VMsπ(bk,α)V^π_M_s(b_k,α) and QMsπ(bk,ak,α)Q^π_M_s(b_k,a_k,α), respectively. These definitions are identical to those in (16) and (17), except that the return distribution is defined with respect to the simplified belief transition model PsP_s. While the simplified model PsP_s is computationally tractable, directly using QMsπ(bk,ak,α)Q^π_M_s(b_k,a_k,α) as a surrogate for QMπ(bk,ak,α)Q^π_M(b_k,a_k,α) may lead to incorrect risk assessments, since the return distributions under P and PsP_s differ. Our objective is to establish lower and upper bounds, denoted by LsL_s and UsU_s, such that Ls≤QMπ(bk,ak,α)≤UsL_s≤ Q_M^π(b_k,a_k,α)≤ U_s, depending solely on quantities computable from the simplified model (19); this conceptual approach is summarized in Figure 2. These bounds provide formal guarantees on the true value function, enabling reliable action selection during online planning. As illustrated in Figure 3, the key quantity governing these bounds is ϵε, an upper bound on the discrepancy between the CDFs of the return under P and PsP_s. Bounding this CDF discrepancy allows us to bound the difference in CVaR, as established in subsequent sections. Original POMDP MMQMπ(bk,ak,α)Q^π_M(b_k,a_k,α)Simplified POMDP MsM_sComputable boundsLs≤QMπ≤UsL_s≤ Q^π_M≤ U_sdiscrepancyϵε Figure 2. Conceptual overview. Direct evaluation of QMπQ^π_M under the original model M is computationally expensive. Instead, the simplified model MsM_s is used to compute bounds on QMπQ^π_M, where the bound quality is governed by the distributional discrepancy ϵε between their belief transition models. ReturnProbability Density Upper α tail VMπ(bk)V^π_M(b_k) VMπ(bk,α)V^π_M(b_k,α) (a) Comparison of expected value VMπ(bk)V^π_M(b_k) and CVaR value VMπ(bk,α)V^π_M(b_k,α). The shaded region represents the worst α fraction of outcomes. ReturnCumulative Probability011ϵε FYF_Y (simplified) FXF_X (original) ϵε-band (b) CDF discrepancy between original (FXF_X) and simplified (FYF_Y) models. The ϵε-band bounds the discrepancy, enabling CVaR bounds. 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 PsP_s yields a computable CDF FYF_Y, while the original CDF FXF_X is intractable. When |FX(r)−FY(r)|≤ϵ|F_X(r)-F_Y(r)|≤ε, bounds on CVaRα⁡(X)CVaR_α(X) can be derived from Y. 5. CVaR Bounds In the previous section, we introduced a simplified belief-transition model with distribution PsP_s as a computationally tractable approximation of the original belief-transition model P. This approximation induces two corresponding random variables: X, representing the return under the original model P, and Y, representing the return under the simplified model PsP_s. While direct evaluation of risk-sensitive criteria for X is often computationally infeasible, sampling and analysis of Y can be carried out efficiently. The goal of this section is to characterize how CVaRα⁡(X)CVaR_α(X) can be bounded and estimated using information derived from Y. To this end, we first establish distributional bounds that relate X and Y, and then derive finite-sample guarantees that allow these bounds to be estimated from data. Together, these results provide a principled framework for bounding the CVaR of the true return using samples generated from the simplified model. 5.1. Theoretical CVaR Bounds In this section, we establish bounds for the CVaR of the random variable X by leveraging an auxiliary random variable Y. Two forms of distributional relationships between their respective CDFs are considered: a uniform bound and a non-uniform bound, as illustrated in Figure 4a and Figure 4b. These results provide the theoretical basis for subsequent sections, in which the derived bounds are applied to estimate the CVaR of random variables that are either computationally intractable or prohibitively expensive to sample directly. Theorem 5.1 bounds CVaRα⁡(X)CVaR_α(X) in terms of CVaRα⁡(Y)CVaR_α(Y) under the sole condition that the cumulative distribution functions of X and Y differ by at most a known uniform bound. This representation enhances the interpretability of the bound and constitutes a novel aspect of the result, made possible by framing the bounding problem in terms of distributional discrepancies. In the next section, we demonstrate that the bounds established in (Thomas and Learned-Miller, 2019) (theorems 3.2 and 3.3) arise as a special case of Theorem 5.1, thereby providing an interpretation for existing CVaR bounds that are otherwise difficult to interpret. Theorem 5.1. Let X and Y be random variables and ϵ∈[0,1]ε∈[0,1]. (1) Upper Bound: assume that P(X≤bX)=1,P(Y≤bY)=1P(X≤ b_X)=1,P(Y≤ b_Y)=1 and ∀z∈ℝ,FY(z)−FX(z)≤ϵ∀ z ,F_Y(z)-F_X(z)≤ε, then (a) If α>ϵα>ε, (20) CVaRα⁡(X)≤ϵαmax⁡(bX,bY)+(1−ϵα)CVaRα−ϵ⁡(Y).CVaR_α(X)≤ εα (b_X,b_Y)+(1- εα)CVaR_α-ε(Y). (b) If α≤ϵα≤ε, then CVaRα⁡(X)≤max⁡(bX,bY)CVaR_α(X)≤ (b_X,b_Y). (2) Lower Bound: If P(X≥aX)=1,P(Y≥aY)=1P(X≥ a_X)=1,P(Y≥ a_Y)=1 and ∀z∈ℝ,FX(z)−FY(z)≤ϵ∀ z ,F_X(z)-F_Y(z)≤ε, then (a) If α+ϵ≤1α+ε≤ 1, (21) CVaRα⁡(X)≥(1+ϵα)CVaRα+ϵ⁡(Y)−ϵαCVaRϵ⁡(Y)CVaR_α(X)≥(1+ εα)CVaR_α+ε(Y)- εαCVaR_ε(Y) (b) If α+ϵ>1α+ε>1 and amin=min⁡(aX,aY)a_min= (a_X,a_Y), (22) CVaRα⁡(X)≥1α([Y]−ϵCVaRϵ⁡(Y)+(α+ϵ−1)amin)CVaR_α(X)≥ 1α (E[Y]- _ε(Y)+(α+ε-1)a_min ) Proof. The proof is available in Appendix A.1. ∎ The parameter ϵε quantifies the discrepancy between the random variables X and Y, and is defined as a uniform bound on the difference between their cumulative distribution functions. By construction, ϵε takes values in the interval [0,1][0,1]. In the limiting case where ϵ=1ε=1, Y provides no information about X. In this setting, the bounds provided by Theorem 5.1 reduce to trivial bounds on CVaRα⁡(X)CVaR_α(X) involving the essential supremum of both X and Y, rendering them ineffective for practical use. When ϵ=0ε=0, the cumulative distribution functions of X and Y are identical, and thus the bound becomes exact, yielding CVaRα⁡(X)=CVaRα⁡(Y)CVaR_α(X)=CVaR_α(Y). Theorem 5.2. Under the definitions of X, Y, ϵε, and α specified in Theorem 5.1, the lower and upper bounds established therein converge to CVaRα⁡(X)CVaR_α(X) as ϵ→0ε→ 0. Proof. The proof is available in Appendix A.2. ∎ For both the upper and lower bounds to be informative, Theorem 5.1 shows that α>ϵα>ε and α+ϵ≤1α+ε≤ 1 must hold, thereby specifying the required relation between the distributional discrepancy ϵε and the CVaR confidence level α. Under these conditions, the bounding problem reduces to (20) and (21). For α>ϵα>ε, the upper bound on CVaRα⁡(X)CVaR_α(X) is a weighted average of the CVaRCVaR of Y at a confidence level shifted by the distributional discrepancy ϵε and the maximum of the supports of X and Y, where the weights are proportional to the amount of distributional discrepancy. For α+ϵ≤1α+ε≤ 1, the bound in (21) satisfies (23) CVaRα⁡(X) _α(X) ≥CVaRα+ϵ⁡(Y)+ϵα(CVaRα+ϵ⁡(Y)−CVaRϵ⁡(Y)). _α+ε(Y)+ εα(CVaR_α+ε(Y)-CVaR_ε(Y)). The lower bound corresponds to the CVaRCVaR of Y evaluated at a confidence level adjusted by the distributional discrepancy ϵε, augmented by a correction term that is proportional to the distributional discrepancy. Theorem 5.1 assumes that the parameter ϵε provides an upper bound on the pointwise difference between the cumulative distribution functions FXF_X and FYF_Y. As illustrated in Figure 4a, this bound is particularly conservative in the vicinity of x=−1x=-1, where the actual discrepancy between FXF_X and FYF_Y is significantly smaller than the global bound ϵε. Ideally, a tighter bound on FX(x)F_X(x) would allow for variation with respect to x, rather than relying on a uniform constant. Specifically, one seeks a pointwise bound of the form FX(x)≤FY(x)+g(x)F_X(x)≤ F_Y(x)+g(x) for some non-negative function g, as illustrated in Figure 4b. In this paper, we defer the study of specific choices of the function g to future work, and instead provide general assumptions under which a feasible tighter bound can be established using such a function. (a) (b) Figure 4. Illustrations of bounds on FX(x)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 FY(x)+ϵF_Y(x)+ε. Theorem 5.3. (Tighter CVaR Lower Bound) Let α∈(0,1)α∈(0,1), X and Y be random variables. Define the random variable YLY^L such that FYL(y)≜min⁡(1,FY(y)+g(y))F_Y^L(y) (1,F_Y(y)+g(y)) for g:ℝ→[0,∞)g:R→[0,∞). Assume limx→−∞g(x)=0 _x→-∞g(x)=0, g is continuous from the right and monotonic increasing. If ∀x∈ℝ,FX(x)≤FY(x)+g(x)∀ x ,F_X(x)≤ F_Y(x)+g(x), then FYLF_Y^L is a CDF and CVaRα⁡(YL)≤CVaRα⁡(X).CVaR_α(Y^L) _α(X). Proof. The proof is available in Appendix A.4. ∎ Theorem 5.3 defines a random variable YLY^L, constructed from Y and the function g, such that the distributional discrepancy between YLY^L and X is determined explicitly by g rather than being uniformly bounded as in Theorem 5.1. In addition, it offers a criterion for determining whether a given function g can be used to derive a lower bound on the CVaR. This bound extends the lower bound established in Theorem 5.1, which is obtained when g(x)g(x) is constant and equal to ϵε for all x∈ℝx . Intuitively, FYLF_Y^L is the largest valid CDF that remains within the pointwise discrepancy band [FY(y),FY(y)+g(y)][F_Y(y),\,F_Y(y)+g(y)]; since FX≤FYLF_X≤ F_Y^L by construction, monotonicity of CVaR yields the lower bound. Figure 4(c) illustrates this tighter construction. Note that in Theorem 5.3, the function g is assumed to be non-decreasing and right-continuous. If one assumes only that |FX(x)−FY(x)|≤g(x)|F_X(x)-F_Y(x)|≤ g(x) for some function g:ℝ→[0,∞)g:R→[0,∞), which is not necessarily monotonic or continuous, then the most general form of the CVaR bounds is given by (24) CVaRα⁡(X)=1α∫1−α1infz∈ℝ:FX(z)≥τdτ≥1α∫1−α1infz∈ℝ:FY(z)+g(z)≥τdτ, _α(X)= 1α _1-α^1 \z :F_X(z)≥τ\dτ≥ 1α _1-α^1 \z :F_Y(z)+g(z)≥τ\dτ, (25) CVaRα⁡(X)=1α∫1−α1infz∈ℝ:FX(z)≥τdτ≤1α∫1−α1infz∈ℝ:FY(z)−g(z)≥τdτ. _α(X)= 1α _1-α^1 \z :F_X(z)≥τ\dτ≤ 1α _1-α^1 \z :F_Y(z)-g(z)≥τ\dτ. Another option is to specify the distributional discrepancy through the density functions underlying the cumulative distribution functions. Let fxf_x and fyf_y be the probability density functions of X and Y, respectively, and let h:ℝ→[0,∞)h:R→[0,∞) describe the pointwise discrepancy between them. Theorem 5.4 specifies conditions on the function h under which a lower bound for the CVaR of X can be obtained. A key advantage is that this bound takes the form of the CVaR of a random variable, enabling its estimation with performance guarantees via CVaR concentration bounds given in Theorems 3.1, 3.3, 3.2 and Theorem 5.5. Theorem 5.4. Let α∈(0,1)α∈(0,1), X and Y be random variables. Define h:ℝ→[0,∞)h:R→[0,∞) to be a continuous function, g(z)≜∫−∞zh(x)xg(z) _-∞^zh(x)dx and YLY^L to be a random variable such that FYL(y)≜min⁡(1,FY(y)+g(y))F_Y^L(y) (1,F_Y(y)+g(y)). If limz→−∞g(z)=0 _z→-∞g(z)=0 and ∀x∈ℝ,fx(x)≤fy(x)+h(x)∀ x ,f_x(x)≤ f_y(x)+h(x), then FYLF_Y^L is a CDF and CVaRα⁡(YL)≤CVaRα⁡(X)CVaR_α(Y^L) _α(X). Proof. The proof is available in Appendix A.5. ∎ Theorem 5.4 is obtained as a corollary of Theorem 5.3 by defining a function g, as illustrated in Figure 4b, in terms of the function h. This construction demonstrates that the function g in Theorem 5.3 can be generated from a broad class of density discrepancy functions. 5.2. Concentration Inequalities In this section, we derive concentration inequalities for CVaRα⁡(X)CVaR_α(X) based on samples drawn from an auxiliary random variable Y. A notable special case of these inequalities arises when Y is taken to follow the empirical cumulative distribution function (ECDF) of X. Let X1,…,Xn∼i.i.d.FXX_1,…,X_n i.i.d. F_X, where FXF_X is the CDF of a random variable X. The ECDF based on these samples is defined by F^X(x)=1n∑i=1n1Xi≤x F_X(x)= 1n _i=1^n1_X_i≤ x, for x∈ℝx . Let EF^X[X]E_ F_X[X] denote the expectation with respect to F^X F_X, and let CαF^XC_α F_X denote the CVaR computed under the empirical distribution F^X F_X. Theorem 5.5. Let X be a random variable, α∈(0,1],δ∈(0,0.5),ϵ=ln⁡(1/δ)/(2n)α∈(0,1],δ∈(0,0.5),ε= (1/δ)/(2n). Let X1,…,Xn∼iidFXX_1,…,X_n iid F_X be random variables that define the ECDF F^X F_X. (1) Upper Bound: If P(X≤b)=1P(X≤ b)=1, then (a) If α>ϵα>ε then P(CVaRα⁡(X)≤(1−ϵα)Cα−ϵF^X+ϵαb)>1−δP(CVaR_α(X)≤(1- εα)C_α-ε F_X+ εαb)>1-δ. (b) If α≤ϵα≤ε then CVaRα⁡(X)≤bCVaR_α(X)≤ b (2) Lower Bound: If P(X≥a)=1P(X≥ a)=1, then (a) If α+ϵ<1α+ε<1, then P(CVaRα⁡(X)≥(1+ϵα)Cα+ϵF^X−ϵαCϵF^X)>1−δP(CVaR_α(X)≥(1+ εα)C_α+ε F_X- εαC_ε F_X)>1-δ. (b) If α+ϵ≥1α+ε≥ 1, then P(CVaRα⁡(X)≥1α[(α+ϵ−1)a+EF^X[X]−ϵCϵF^X])>1−δP(CVaR_α(X)≥ 1α[(α+ε-1)a+E_ F_X[X]-ε C_ε F_X])>1-δ. Proof. The proof is available in Appendix A.3. ∎ Theorem 5.5 provides concentration inequalities for CVaRα⁡(X)CVaR_α(X) in a form that enables the user to specify a desired bound consistency level δ, which determines the probability that the bound holds. This result follows as a corollary of Theorem 5.1, in which the auxiliary random variable Y is instantiated as the ECDF of X, whereas X denotes the underlying true random variable, which is inaccessible in practice. The distributional discrepancy required by Theorem 5.1, denoted by ϵε, is controlled in Theorem 5.5 via the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality (Dvoretzky et al., 1956). The DKW inequality ensures that the supremum distance between the true CDF and the ECDF converges to zero at a rate of order 1/n1/ n as the number of samples n increases. Corollary 5.6 establishes the asymptotic convergence of the bounds given in Theorem 5.5 as the sample size tends to infinity. Corollary 5.6. Let X be a random variable, α∈(0,1],δ∈(0,0.5),ϵ=ln⁡(1/δ)/(2n),a∈ℝ,b∈ℝα∈(0,1],δ∈(0,0.5),ε= (1/δ)/(2n),a ,b . Let X1,…,Xn∼iidFXX_1,…,X_n iid F_X be random variables that define the ECDF F^X F_X. Denote by U(n)U(n) and L(n)L(n) the upper and lower bounds respectively from Theorem 5.5, where n is the number of samples, then (1) If P(X≤b)=1P(X≤ b)=1, then limn→∞U(n)=a.s.CVaRα⁡(X) _n→∞U(n) a.s.=CVaR_α(X). (2) If P(X≥a)=1P(X≥ a)=1, then limn→∞L(n)=a.s.CVaRα⁡(X) _n→∞L(n) a.s.=CVaR_α(X). where a.s. denotes almost sure convergence. Proof. The proof is available in Appendix A.6. ∎ The concentration bounds established by (Thomas and Learned-Miller, 2019) coincide with those given in Theorem 5.5, rendering the results of (Thomas and Learned-Miller, 2019) a special case of Theorem 5.5. This equivalence arises because both Theorem 5.5 and (Thomas and Learned-Miller, 2019) derive concentration bounds for CVaRα⁡(X)CVaR_α(X) by constructing an alternative CDF that stochastically dominates the true distribution FXF_X, employing the DKW inequality to control the discrepancy. The principal distinction between the two results lies in the formulation of the CVaRCVaR bound: (Thomas and Learned-Miller, 2019) express the bound through a sum of reweighted order statistics (theorems 3.2 and 3.3), resulting in a more intricate form, whereas Theorem 5.5 presents a more interpretable bound in terms of CVaRCVaR. The interpretability of these bounds constitutes a contribution of this paper. Theorem 5.7 provides concentration inequalities for the theoretical CVaRα⁡(X)CVaR_α(X) based on samples drawn from an auxiliary random variable Y, assuming only a bound on the distributional discrepancy between X and Y. Theorem 5.7. Let X and Y be random variables, ϵ∈[0,1],δ∈(0,0.5)ε∈[0,1],δ∈(0,0.5), and η=ln⁡(1/δ)/(2n),ϵ′=min⁡(ϵ+η,1)η= (1/δ)/(2n),ε = (ε+η,1). Let Y1,…,YnY_1,…,Y_n be independent and identically distributed samples from FYF_Y, and denote by F^Y F_Y the associated empirical cumulative distribution function. (1) Upper Bound: If ∀z∈ℝ,FY(z)−FX(z)≤ϵ∀ z ,F_Y(z)-F_X(z)≤ε and P(X≤bX)=1,P(Y≤bY)=1P(X≤ b_X)=1,P(Y≤ b_Y)=1, then (a) If α>ϵ′α>ε then P(CVaRα⁡(X)≤ϵ′αmax⁡(bX,bY)+(1−ϵ′α)CVaRα−ϵ′F^Y)>1−δP (CVaR_α(X)≤ ε α (b_X,b_Y)+(1- ε α)CVaR_α-ε F_Y )>1-δ. (b) If α≤ϵ′α≤ε , then CVaRα⁡(X)≤max⁡(bX,bY)CVaR_α(X)≤ (b_X,b_Y) (2) Lower Bound: If ∀z∈ℝ,FX(z)−FY(z)≤ϵ∀ z ,F_X(z)-F_Y(z)≤ε and P(X≥aX)=1,P(Y≥aY)=1P(X≥ a_X)=1,P(Y≥ a_Y)=1, then (a) If α+ϵ′≤1α+ε ≤ 1, then (26) P(CVaRα(X) P (CVaR_α(X) ≥(1+ϵ′α)CVaRα+ϵ′F^Y−ϵ′αCVaRϵ′F^Y)>1−δ. ≥(1+ ε α)CVaR_α+ε F_Y- ε αCVaR_ε F_Y )>1-δ. (b) If α+ϵ′>1α+ε >1, then (27) P(CVaRα(X) P (CVaR_α(X) ≥1α(F^Y[Y]−ϵ′CVaRϵ′F^Y+(α+ϵ′−1)amin))>1−δ. ≥ 1α (E_ F_Y[Y]-ε CVaR_ε F_Y+(α+ε -1)a_min ) )>1-δ. Proof. The proof is available in Appendix A.7. ∎ The parameter ϵε in Theorem 5.7 captures the distributional discrepancy between X and Y, consistent with its role in Theorem 5.1. Additionally, the theorem introduces ϵ′ε to represent the discrepancy between FXF_X and F^Y F_Y, where F^Y F_Y denotes the empirical CDF of Y constructed from the sample Yii=1n\Y_i\_i=1^n. The parameter η accounts for the additional distributional discrepancy beyond ϵε, and captures the estimation error in approximating FYF_Y using the empirical sample Yii=1n\Y_i\_i=1^n. By combining Theorem 5.1 with the DKW inequality (Dvoretzky et al., 1956), we obtain probabilistic guarantees for the estimated bounds. 6. Value Function Bounds for Static CVaR Value Function In this section, we leverage the CVaR bounds from the previous section to establish bounds between the simplified and original value functions as defined in (16), where the simplification is considered in a general form with respect to the belief transition model. We then derive bounds for the specific case in which the simplification applies to the observation model. The implications of these bounds for policy evaluation and open-loop POMDP planning will be examined in the Experiments section. 6.1. Bounds for a General Belief Transition Model Simplification In this section, we establish bounds on the difference between the CDFs of the returns, computed with respect to the simplified and original belief transition models. These bounds are then used to bound the original value function in terms of the simplified value function. Theorem 6.1 demonstrates that the difference between the CDFs of the returns, computed with respect to the simplified and original belief transition models, can be characterized in terms of the difference between the simplified and original belief transition models. Theorem 6.1. Let P and PsP_s denote the probability measures induced by the original and simplified belief-transition models, respectively. Denote by sE^s the expectation taken with respect to the simplified belief-transition model. Then, the following holds: (28) supl∈ℝ|P(Rk:T≤l|bk,ak,π)−Ps(Rk:T≤l|bk,ak,π)|≤∑t=kT−1s[Δs(bt,at)|bk,ak], _l |P(R_k:T≤ l|b_k,a_k,π)\!-\!P_s(R_k:T≤ l|b_k,a_k,π)|\!≤\!\!\! _t=k^T-1E^s[ ^s(b_t,a_t)|b_k,a_k], where Δs ^s is the TV distance that is defined by (29) Δs(bt−1,at−1)≜∫bt∈B|P(bt|bt−1,at−1)−Ps(bt|bt−1,at−1)|dbt. ^s(b_t-1,a_t-1) _b_t∈ B|P(b_t|b_t-1,a_t-1)-P_s(b_t|b_t-1,a_t-1)|db_t. Proof. The proof is available in Appendix C.1. ∎ The expression s[Δs(bt,at)∣bk,ak]E^s[ ^s(b_t,a_t) b_k,a_k] quantifies the expected one-step distributional discrepancy at time t between the transition dynamics of the simplified and original belief-MDPs, conditioned on the planning process being initiated at time k. Summing this quantity over the horizon accumulates the total distributional discrepancy, leading to the bound in (28), which in turn bounds the cumulative distribution function of the return across the horizon. This accumulation mechanism is illustrated in Figure 5. Time step ttDistributional discrepancykkk+1k\!+\!1k+2k\!+\!2k+3k\!+\!3k+4k\!+\!4⋯·sT−1T\!-\!1Δks ^s_kΔk+1s ^s_k+1Δk+3s ^s_k+3ϵ=∑tΔtsε= _t ^s_tα tight bounds s[Δs(bt,at)|bk,ak]E^s[ ^s(b_t,a_t)|b_k,a_k] Cumulative ϵε CVaR level α Figure 5. Accumulation of distributional discrepancy over the planning horizon. Each bar represents the expected one-step TV distance s[Δs(bt,at)∣bk,ak]E^s[ ^s(b_t,a_t) b_k,a_k] at time t. The cumulative sum ϵ=∑t=kT−1Δtsε= _t=k^T-1 ^s_t (dashed) governs the bound quality: when ϵ<αε<α (below the dash-dotted line), the CVaR bounds from Theorem 6.2 remain informative; when ϵ≥αε≥α, the bounds reduce to trivial extrema. By leveraging Theorem 5.1 and combining it with the supremum norm bounds for the simplified and original return CDFs in (28), we derive the following bounds on the value functions. Theorem 6.2. Let δdmin∈[0,1],δdmax∈[0,1] _d_min∈[0,1], _d_max∈[0,1] and denote (30) ϵ≜ϵ(bk,ak)≜min⁡(∑i=kT−1s[Δs(bi,ai)|bk,ak,π],1),ε ε(b_k,a_k) ( _i=k^T-1E^s[ ^s(b_i,a_i)|b_k,a_k,π],1), (1) Upper Bound: assume that P(Rk:T≤dmax)>1−δdmaxP(R_k:T≤ d_max)>1- _d_max and Ps(Rk:T≤dmax)>1−δdmaxP_s(R_k:T≤ d_max)>1- _d_max, then (a) If ϵ<αε<α, then Us≜(1−ϵα)QMsπ(bk,ak,α−ϵ)+ϵαdmaxU_s (1- εα)Q^π_M_s(b_k,a_k,α-ε)+ εαd_max (b) If ϵ≥αε≥α then Us≜dmaxU_s d_max (2) Lower Bound: assume that P(Rk:T≥dmin)>1−δdminP(R_k:T≥ d_min)>1- _d_min and Ps(Rk:T≥dmin)>1−δdminP_s(R_k:T≥ d_min)>1- _d_min, then (a) If ϵ+α<1ε+α<1 then Ls≜(1+ϵα)QMsπ(bk,ak,α+ϵ)−ϵαQMsπ(bk,ak,ϵ)L_s (1+ εα)Q^π_M_s(b_k,a_k,α+ε)- εαQ^π_M_s(b_k,a_k,ε) (b) If ϵ+α≥1ε+α≥ 1 then Ls≜1α[−(α+ϵ−1)dmin+QMsπ(bk,ak)−ϵQMsπ(bk,ak,ϵ)]L_s 1α[-(α+ε-1)d_min+Q^π_M_s(b_k,a_k)-ε Q^π_M_s(b_k,a_k,ε)] Then P(Ls≤QMπ(bk,ak,α))>1−δdminP(L_s≤ Q_M^π(b_k,a_k,α))>1- _d_min and P(QMπ(bk,ak,α)≤Us)>1−δdmaxP(Q_M^π(b_k,a_k,α)≤ U_s)>1- _d_max. Proof. The proof is available in Appendix C.3. ∎ The bounds established in Theorem 6.2 provide upper and lower bounds on the original value function in terms of the simplified value function, evaluated at an adjusted confidence level that accounts for the distributional discrepancy ϵε between the simplified and original belief transition models. 6.2. Bounds for Observation Model Simplification Simplification of the observation model is a special case of simplification of the belief transition model. Despite that, computation of the belief transition model is still an open question in the field, and therefore the bounds from Theorem 6.2 should be adjusted for this specific simplification setting. Let qzq_z denote the simplified observation model associated with the POMDP MsM_s, and let pzp_z denote the original observation model associated with the POMDP M. The bounds for observation model simplification are exhibited in Theorem 6.3. Theorem 6.3. In the case where the simplified and original observation models are denoted by qzq_z and pzp_z respectively, it holds that (31) supl∈ℝ|P(Rk:T≤l|bk,ak,π)−Ps(Rk:T≤l|bk,ak,π)|≤∑t=kT−1s[Δs(xt+1)|bk,ak], _l |P(R_k:T≤ l|b_k,a_k,π)\!-\!P_s(R_k:T≤ l|b_k,a_k,π)|\!≤\!\!\! _t=k^T-1E^s[ ^s(x_t+1)|b_k,a_k], where Δs ^s is the TV distance that is defined by (32) Δs(xt)≜∫zt∈Z|pz(zt|xt)−qz(zt|xt)|dzt. ^s(x_t) _z_t∈ Z|p_z(z_t|x_t)-q_z(z_t|x_t)|dz_t. Proof. The proof is available in Appendix C.2. ∎ Theorem 6.3 establishes a state-dependent upper bound on the sup-norm difference between the CDFs of the return. This bound is amenable to practical computation. The state xt+1x_t+1 appearing in (31) can be sampled from the distribution P(⋅∣xt,πt)∏i=k+1t−1P(xi+1∣xi,πi)P(xk∣bk)P(· x_t, _t) _i=k+1^t-1P(x_i+1 x_i, _i)P(x_k b_k), where πi _i denotes the action selected by policy π at time i. By leveraging Theorem 6.2 with Theorem 6.3, we obtain Corollary 6.4, which provides computable CVaR bounds based on state-dependent total variation distance. Corollary 6.4. The bound from Theorem 6.2 holds for ϵ(bk,ak)=∑t=kT−1s[Δs(xt+1)|bk,ak]ε(b_k,a_k)= _t=k^T-1E^s[ ^s(x_t+1)|b_k,a_k]. Proof. The proof is available in Appendix C.4. ∎ 7. Online Bound Estimation In this section, we derive practical estimators corresponding to the theoretical bounds presented in Section 6, and describe how these bounds can be efficiently computed within the context of online policy evaluation and open-loop planning. All estimators are constructed from samples generated by particle-based belief estimators drawn under the simplified belief-transition distribution. Specifically, we develop estimators for the action–value function, the distributional discrepancy ϵε appearing in Corollary 6.4, and the minimum and maximum values of the return, thereby enabling computation of the complete bound stated in Corollary 6.4. Moreover, we provide performance guarantees for these estimators, establishing their reliability when computed from a finite number of samples. 7.1. Action-Value Function Estimator The action-value function is defined as the CVaR of the return Rk:T≜∑t=kTc(bt,at)R_k:T _t=k^Tc(b_t,a_t), and can be estimated in a straightforward manner by generating sample trajectories of the return and computing the empirical CVaR from these samples. To generate return samples, it is necessary to simulate belief trajectories from time k to time T. This is achieved using a particle-based belief estimator, where the belief is represented by a weighted set of Np∈ℕN_p particles. Given a particle belief b¯k b_k, provided by the user to represent the agent’s belief at time k, the agent generates NbN_b simulated particle-belief trajectories b¯ti\ b_t^i\, where i∈1,…,Nbi∈\1,…,N_b\ indexes the trajectory and t∈k,…,Tt∈\k,…,T\ denotes the time step. For each simulated trajectory, a return sample is computed as R¯k:Ti=∑t=kTc(b¯ti,π(b¯ti)) R^i_k:T= _t=k^Tc( b_t^i,π( b_t^i)), resulting in a collection of return samples R¯k:Tii=1Nb\ R_k:T^i\_i=1^N_b. Let b¯ti≜(xti,j,wti,j)j=1Np b_t^i \(x_t^i,j,w_t^i,j)\_j=1^N_p denote the i-th simulated particle belief at time t, where j indexes the particles. Define the normalized weights by w~ti,j≜wti,j∑j=1Npwti,j w_t^i,j w_t^i,j _j=1^N_pw_t^i,j. Assuming the cost function is state-dependent, the cost associated with belief b¯ti b_t^i and action a is given by c(b¯ti,a)=∑j=1Npw~ti,jc(xti,j,a).c( b_t^i,a)= _j=1^N_p w_t^i,j\,c(x_t^i,j,a). By estimating CVaR according to (13), we get the action-value function estimator (33) Q^MPπ(b¯k,a,α)≜C^(Rii=1Nb) Q_M_P^π( b_k,a,α) C(\R^i\_i=1^N_b) =R(Nb)−1α∑i=1Nb(R(i)−R(i−1))(iNb−(1−α))+. =R^(N_b)- 1α _i=1^N_b(R^(i)-R^(i-1)) ( iN_b-(1-α) )^+. Detailed pseudo-code for the estimation of the action–value function is presented in Algorithm 1. Algorithm 1 CVaR Value Function Estimation for Policy π Global Parameters: Np,Nb,T,πN_p,N_b,T,π Input: Particle belief b¯ b, planning horizon T, policy π, action a, risk level α, number of belief trajectories NbN_b and number of belief particles NpN_p. Output: Estimated value V^π(b¯) V^π( b) or Q^π(b¯,a) Q^π( b,a) 1:procedure GENPF(b¯,a b,a) 2: Sample x0x_0 from b¯ b with prob. wi/∑iwiw_i/ _iw_i 3: z←G(x0,a)z← G(x_0,a) 4: for i=1i=1 to NpN_p do 5: (xi′,ri)←G(xi,a)(x _i,r_i)← G(x_i,a) 6: wi′←wi⋅Z(z∣a,xi′)w _i← w_i· Z(z a,x _i) 7: end for 8: b′¯←(xi′,wi′)i=1Np b ←\(x _i,w _i)\_i=1^N_p 9: ρ←∑iwiri∑iwiρ← _iw_ir_i _iw_i 10: return b′¯,ρ b ,ρ 11:end procedure 12:procedure SampleNextBeliefs(beliefs, π) 13: NextBeliefs←list()NextBeliefs← list() 14: for j=1j=1 to NbN_b do 15: NextBelief←GENPF(beliefs[j],NextBelief (beliefs[j], π(beliefs[j]))π(beliefs[j])) 16: append NextBelief to NextBeliefs 17: end for 18: return NextBeliefs 19:end procedure 20:procedure GenBeliefTrajectories(b¯,π,T b,π,T) 21: trajectories←list()trajectories← list() 22: for i=1i=1 to NbN_b do 23: append b¯ b to trajectories 24: end for 25: for t=0t=0 to T−1T-1 do 26: NextBeliefs←NextBeliefs← SampleNextBeliefs(trajectories[t], π) 27: append NextBeliefs to trajectories 28: end for 29: return trajectories 30:end procedure 1:procedure GenerateReturnSample(b¯,a,π b,a,π) 2: trajectories ← GenBeliefTrajectories(b¯,π,T b,π,T) 3: ReturnSample ← list() 4: for i=1i=1 to NbN_b do 5: Return ← c(trajectories[0][i], a) 6: for t=1t=1 to T do 7: Return += c(trajectories[t][i], π(trajectories[t][i])) 8: end for 9: append Return to ReturnSample 10: end for 11: return ReturnSample 12:end procedure 13:procedure CVaREstimate(samp, α) 14: Sort samp in ascending order as z1,…,znz_1,…,z_n with z0=0z_0=0 15: return zn−1α∑i=0n−1(zi+1−zi)(in−(1−α))+z_n- 1α _i=0^n-1(z_i+1-z_i) ( in-(1-α) )^+ 16:end procedure 17:procedure EstimateVπV^π(b¯,α b,α) 18: return EstimateQ(b¯,π(b¯),α b,π( b),α) 19:end procedure 20:procedure EstimateQ(b¯,a,α b,a,α) 21: samp ← GenerateReturnSample(b¯,a,π b,a,π) 22: return CVaREstimate(samp,α) 23:end procedure 7.2. Online CDF Bound Estimation The bound on the difference between return simplified and original CDFs, established in Theorem 6.3 and denoted by ϵε in Corollary 6.4, plays a central role in bounding the discrepancy between the simplified and original action-value functions. Notably, it is the only term in the bound that explicitly captures the impact of the difference between the simplified and original observation models. A challenge arises from the fact that the quantity ϵε cannot be directly estimated during planning, as its computation requires access to the full observation model pzp_z, which is typically too expensive to evaluate online. For the purpose of online computation of the bound, we adopt the methodology proposed in (Lev-Yehudi et al., 2024), which enables evaluation without real-time access to the original observation model. This is achieved by decoupling the offline sampling phase—conducted using the original observation model—from the online sampling phase, which relies solely on the simplified observation model. Specifically, the offline–online decoupling strategy and the state-level importance-sampling estimator in (34) were introduced by (Lev-Yehudi et al., 2024); the belief-level aggregation, horizon-level accumulation, and the probabilistic guarantees developed in the remainder of this section are novel contributions of the present work. This offline–online decoupling procedure is illustrated in Figure 6. Let Q0Q_0 be a distribution over the state space, and denote the TV-distance expectation given the previous state and action by m. (34) shows how the one-step distributional discrepancy bound m can be computed using importance sampling. (34) m(xt,a) m(x_t,a) ≜xt+1∼P(⋅|xt,a)[Δs(xt+1)|xt,a] _x_t+1 P(·|x_t,a)[ ^s(x_t+1)|x_t,a] =xt+1∼Q0[P(xt+1|xt,a)Q0(xt+1)Δs(xt+1)|xt,a]. =E_x_t+1 Q_0[ P(x_t+1|x_t,a)Q_0(x_t+1) ^s(x_t+1)|x_t,a]. Define the belief-dependent one-step distributional discrepancy m, and the belief-dependent total distributional discrepancy bound of the CDFs difference at time t by ϵt _t. (35) m(bt,a)≜[m(xt,a)|bt,a],m(b_t,a) [m(x_t,a)|b_t,a], (36) ϵt(bt,a)≜∑τ=tT−1[Δs(xτ+1)|bt,a]=∑τ=tT−1[m(bτ,a)|bt,a]. _t(b_t,a) _τ=t^T-1E[ ^s(x_τ+1)|b_t,a]= _τ=t^T-1E[m(b_τ,a)|b_t,a]. In practice, a set of states xnΔn=1NΔ∼i.i.d.Q0\x_n \_n=1^N i.i.d. Q_0 is drawn from a user-specified distribution Q0Q_0, and the TV-distance corresponding to each sampled state is computed offline. During online planning, the precomputed TV distance estimates are reweighted via importance sampling, thereby adapting the offline-computed distributional discrepancy to reflect the actual distributional discrepancy encountered by the agent during execution, as described in (37). By utilizing xnΔ\x_n \, (34) and (35) can be estimated as follows (37) m^(xt,a)=1NΔ∑n=1NΔP(xnΔ|xt,a)Q0(xnΔ)Δs(xnΔ), m(x_t,a)= 1N _n=1^N P(x_n |x_t,a)Q_0(x_n ) ^s(x_n ), (38) m^(b¯t,a)=∑i=1Npm^(xti,a)w~ti, m( b_t,a)= _i=1^N_p m(x_t^i,a) w_t^i, for b¯t≜(xti,wti) b_t \(x_t^i,w_t^i)\ where w~ti w_t^i are the normalized weights. Using the particle-belief trajectories b¯τii=1Nb\ b_τ^i\_i=1^N_b introduced in Section 7.1, the TV-distance at time τ+1τ+1 is estimated by using b¯τii=1Nb\ b_τ^i\_i=1^N_b as samples from the conditional distribution of b¯τ b_τ given b¯t b_t, as described below. (39) ^[m(bτ,a)|b¯t,a]=1Nb∑i=1Nbm^(b¯τi,π(b¯τi)). E[m(b_τ,a)| b_t,a]= 1N_b _i=1^N_b m( b_τ^i,π( b_τ^i)). The estimate of ϵε is then computed directly by (40) ϵ^(b¯t,a)=∑τ=tT−1^[m(b¯τ,πτ)|b¯t,a]. ε( b_t,a)= _τ=t^T-1 E[m( b_τ, _τ)| b_t,a]. Offline (original pzp_z)Sample xnΔn=1NΔ∼Q0\x_n \_n=1^N Q_0Compute Δs(xnΔ) ^s(x_n ) using pz,qzp_z,q_zStore (xnΔ,Δs(xnΔ))\(x_n ,\; ^s(x_n ))\Online (simplified qzq_z only)Given state xtx_t, action a Reweight via IS: P(xnΔ|xt,a)Q0(xnΔ)Δs(xnΔ) P(x_n |x_t,a)Q_0(x_n ) ^s(x_n ) Aggregate: m^(b¯t,a) m( b_t,a)Accumulate: ϵ^(b¯t,a) ε( b_t,a)precomputed Δs ^s Figure 6. Offline–online decoupling for distributional discrepancy estimation. In the offline phase, states are sampled from a proposal distribution Q0Q_0 and the TV distances Δs ^s are computed using the original observation model pzp_z. During online planning, the precomputed Δs ^s values are reweighted via importance sampling using only the state-transition model, eliminating the need to evaluate pzp_z in real time. Theorem 7.1 establishes performance guarantees for the distributional discrepancy estimator defined in (40), and demonstrates that it converges exponentially fast to the true distributional discrepancy as the number of sampled beliefs NbN_b increases. Theorem 7.1. Let η>0,δ∈(0,1)η>0,δ∈(0,1). If Δ is unbiased, then (41) P(|ϵ^t(b¯t,a)−ϵt(b¯t,a)|≥η) P(| ε_t( b_t,a)- _t( b_t,a)|≥η) ≤2exp⁡(−2η2NbD2(T−k)2(Rmax−Rmin)2) ≤ 2 (- 2η^2N_bD^2(T-k)^2(R_ -R_ )^2 ) for D=maxi∈k+1,…,T−1⁡DiD= _i∈\k+1,…,T-1\D_i where Di=supxi+1P(xi+1|xi,ai)/Q0(xi+1)D_i= _x_i+1P(x_i+1|x_i,a_i)/Q_0(x_i+1). Proof. The proof is available in Appendix C.5. ∎ 7.3. Online Return Bound Estimation The bound in Theorem 6.2 requires knowledge of the upper and lower bounds on the return under both the original and simplified distributions. Formally, we need estimators d^min d_ and d^max d_ for dmind_ and dmaxd_ in Theorem 6.2. A simple choice is (42) d^min=(T−k+1)Rmin,d^max=(T−k+1)Rmax, d_ =(T-k+1)R_ , d_ =(T-k+1)R_ , which, however, ignores the dependence of the return on the agent’s belief bkb_k and policy π. For example, if the belief indicates that the agent is far from any obstacle and the planning horizon is too short for a collision to occur, taking the maximal possible return obscures this contextual information and results in a looser bound than necessary. To obtain tighter estimates, we define (43) d^maxπ(bk)=maxi∈1,…,Nb⁡Ri,d^minπ(bk)=mini∈1,…,Nb⁡Ri, d_ ^π(b_k)= _i∈\1,…,N_b\R^i, d_ ^π(b_k)= _i∈\1,…,N_b\R^i, where Rii=1Nb∼Ps(⋅|bk,π)\R^i\_i=1^N_b P_s(·|b_k,π) are the return samples used to estimate the action–value function. Theorem 7.2 provides performance guarantees for these estimators. Theorem 7.2. For the estimators d^maxπ(bk)=maxi⁡Ri d_ ^π(b_k)= _iR^i and d^minπ(bk)=mini⁡Ri d_ ^π(b_k)= _iR^i, where i∈1,…,Nbi∈\1,…,N_b\, R1,…,RNb∼PsR^1,…,R^N_b P_s, and for ϵε as defined in (30), the following bounds hold. (44) Ps(Rk:T≥d^minπ(bk)|bk,π)≥NbNb+1,Ps(Rk:T≤d^max|bk,π)≥NbNb+1P_s(R_k:T≥ d_min^π(b_k)|b_k,π)≥ N_bN_b+1, P_s(R_k:T≤ d_max|b_k,π)≥ N_bN_b+1 (45) P(Rk:T≥d^minπ(bk)|bk,π)≥NbNb+1−ϵ,P(Rk:T≤d^maxπ(bk)|bk,π)≥NbNb+1−ϵ.P\! (R_k:T≥ d_min^π(b_k) |b_k,π )≥ N_bN_b+1-ε, P\! (R_k:T≤ d_max^π(b_k) |b_k,π )≥ N_bN_b+1-ε. Proof. The proof is available in Appendix C.6. ∎ The bounds for both the simplified and the original returns are computed using return samples generated from the simplified belief-transition model. The uncertainty in the upper bound on the original return, induced by using samples drawn from the simplified return distribution, is quantified by ϵε, which represents the distributional discrepancy between the original and simplified returns. 7.4. Performance Guarantees In this section we provide performance guarantees for the bounds exhibited in previous sections, making them reliable in practice. 7.4.1. Guarantees with Known Return Bounds Theorem 7.3 establishes performance guarantees for the original action–value function in terms of the simplified action–value function, under the assumption that the simplification is applied to the belief–transition model. These bounds hold for a general ρ-POMDP, where the cost is belief-dependent. Theorem 7.3. Let δ,δdmin,δdmax∈[0,1]δ, _d_ , _d_ ∈[0,1], and let bkb_k denote the initial belief. Consider samples R1,…,RNb∼Ps(⋅∣bk,π)R^1,…,R^N_b P_s(· b_k,π) generated using the simplified belief-transition model. Define (46) ϵ≜ϵ(bk,ak)≜min⁡(∑i=kT−1s[Δs(bi,ai)|bk,ak,π],1),ε ε(b_k,a_k) ( _i=k^T-1E^s[ ^s(b_i,a_i)|b_k,a_k,π],1), (47) η=ln⁡(1/δ)/(2Nb),ϵ′=ϵ+η.η= (1/δ)/(2N_b), ε =ε+η. (1) Upper Bound: assume that P(Rk:T≤dmax)>1−δdmaxP(R_k:T≤ d_max)>1- _d_max and Ps(Rk:T≤dmax)>1−δdmaxP_s(R_k:T≤ d_max)>1- _d_max, then (a) If ϵ′<αε <α, then Us≜(1−ϵ′α)Q^Msπ(bk,ak,α−ϵ′)+ϵ′αdmaxU_s (1- ε α) Q^π_M_s(b_k,a_k,α-ε )+ ε αd_max (b) If ϵ′≥αε ≥α then Us≜dmaxU_s d_max (2) Lower Bound: assume that P(Rk:T≥dmin)>1−δdminP(R_k:T≥ d_min)>1- _d_min and Ps(Rk:T≥dmin)>1−δdminP_s(R_k:T≥ d_min)>1- _d_min, then (a) If ϵ′+α<1ε +α<1 then Ls≜(1+ϵ′α)Q^Msπ(bk,ak,α+ϵ′)−ϵ′αQ^Msπ(bk,ak,ϵ′)L_s (1+ ε α) Q^π_M_s(b_k,a_k,α+ε )- ε α Q^π_M_s(b_k,a_k,ε ) (b) If ϵ′+α≥1ε +α≥ 1 then Ls≜1α[−(α+ϵ′−1)dmin+Q^Msπ(bk,ak)−ϵ′Q^Msπ(bk,ak,ϵ′)]L_s 1α[-(α+ε -1)d_min+ Q^π_M_s(b_k,a_k)-ε Q^π_M_s(b_k,a_k,ε )] Then P(Ls≤QMπ(bk,ak,α))>(1−δ)(1−δdmin)P(L_s≤ Q_M^π(b_k,a_k,α))>(1-δ)(1- _d_min) and P(QMπ(bk,ak,α)≤Us)>(1−δ)(1−δdmax)P(Q_M^π(b_k,a_k,α)≤ U_s)>(1-δ)(1- _d_max). Proof. The proof is available in Appendix C.7. ∎ Estimation of the belief-transition model remains an open problem in the literature; consequently, the distributional discrepancy ϵε in Theorem 7.3, when defined in terms of the belief-transition model, is currently intractable to estimate. In the special case where only the observation model is simplified, the one-step distributional discrepancy Δs ^s is defined with respect to the observation model rather than the belief-transition model (see Section 6.2). In this case, Theorem 7.3 holds when Δs ^s is defined using the original and simplified observation models, as characterized in Theorem 6.4, thereby rendering the estimation of ϵε tractable. To attain standard bounds, one can set trivial bounds to the return dmin=(T−k+1)Rmind_min=(T-k+1)R_ and dmax=(T−k+1)Rmaxd_max=(T-k+1)R_ . These bounds would produce δdmin=δdmax=0 _d_min= _d_max=0 and guarantees of 1−δ1-δ for the bounds in Theorem 7.3. 7.4.2. Guarantees with Estimated Return Bounds In practice, it is preferable to estimate the return bounds dmind_ and dmaxd_ with respect to the current belief and policy in order to obtain tighter bounds (see Section 7.3). Theorem 7.4 establishes guarantees for the resulting simplified bounds, in which dmind_ and dmaxd_ are replaced by their estimators. Theorem 7.4. Let bkb_k be an initial belief and let R1,…,RNb∼Ps(⋅|bk,π)R^1,…,R^N_b P_s(·|b_k,π) be a sample that utilizes the simplified belief-transition model. Denote (48) ϵ≜ϵ(bk,ak)≜min⁡(∑i=kT−1s[Δs(bi,ai)|bk,ak,π],1)ε ε(b_k,a_k) ( _i=k^T-1E^s[ ^s(b_i,a_i)|b_k,a_k,π],1) (49) η=ln⁡(1/δ)/(2Nb),ϵ′=ϵ+η= (1/δ)/(2N_b), ε =ε+η (50) d^maxπ(bk)=maxi∈1,…,Nb⁡Ri,d^minπ(bk)=mini∈1,…,Nb⁡Ri, d_ ^π(b_k)= _i∈\1,…,N_b\R^i, d_ ^π(b_k)= _i∈\1,…,N_b\R^i, (1) Upper Bound: Under the following conditions, it holds that P(QMπ(b¯k,ak,α)≤Us|bk,π)≥(1−δ)(NbNb+1−ϵ)P(Q^π_M( b_k,a_k,α)≤ U_s|b_k,π)≥(1-δ) ( N_bN_b+1-ε ) (a) If ϵ′<αε <α, then Us≜(1−ϵ′α)Q^Msπ(bk,ak,α−ϵ′)+ϵ′αd^maxπ(bk)U_s (1- ε α) Q^π_M_s(b_k,a_k,α-ε )+ ε α d_max^π(b_k) (b) If ϵ′≥αε ≥α then Us≜d^maxπ(bk)U_s d_max^π(b_k) (2) Lower Bound: Under the following conditions, it holds that P(QMπ(b¯k,ak,α)≥Ls|bk,π)≥(1−δ)(NbNb+1−ϵ)P(Q^π_M( b_k,a_k,α)≥ L_s|b_k,π)≥(1-δ) ( N_bN_b+1-ε ) (a) If ϵ′+α<1ε +α<1 then Ls≜(1+ϵ′α)Q^Msπ(bk,ak,α+ϵ′)−ϵ′αQ^Msπ(bk,ak,ϵ′)L_s (1+ ε α) Q^π_M_s(b_k,a_k,α+ε )- ε α Q^π_M_s(b_k,a_k,ε ) (b) If ϵ′+α≥1ε +α≥ 1 then Ls≜1α[−(α+ϵ′−1)d^minπ(bk)+Q^Msπ(bk,ak)−ϵ′Q^Msπ(bk,ak,ϵ′)]L_s 1α[-(α+ε -1) d_min^π(b_k)+ Q^π_M_s(b_k,a_k)-ε Q^π_M_s(b_k,a_k,ε )] Proof. The proof is available in Appendix C.8. ∎ Recall that the theoretical bounds derived in Section 6 impose constraints on the relationship between the distributional discrepancy ϵε and the CVaR confidence level α. When these conditions are violated, the resulting bounds on the action-value function become trivial. Employing estimators for the minimum and maximum return enables the agent to act according to the guarantees in Theorem 7.4, even when these constraints are not satisfied. As an example (illustrated in Figure 7), consider ϵ=α=0.1ε=α=0.1, Nb=1000N_b=1000, and δ=0.01δ=0.01, with planning horizon T=2T=2. The agent must choose between a dangerous path that passes through an obstacle and a safe path that avoids it. The agent incurs a cost of 11 for remaining in place and a cost of 100100 upon colliding with an obstacle. In this setting, even under partial observability, the probability of encountering an obstacle along the safe path, as well as the probability of not encountering an obstacle along the dangerous path, may be small. Consequently, the estimators satisfy d^maxπ(b0)=d^minπ(b0)≈1×2 d^π_ (b_0)= d^π_ (b_0)≈ 1× 2 for the safe path and d^maxπ(b0)=d^minπ(b0)≈100×2 d^π_ (b_0)= d^π_ (b_0)≈ 100× 2 for the dangerous path. This allows the agent to distinguish between the two paths, in the sense that the CVaR of the dangerous path is strictly larger than that of the safe path. obstacleSSGGsafedangerouscstep=1c_step=1ccollision=100c_collision=100 (a) An agent at position S must choose between a safe path (blue, cost 11 per step) and a dangerous path (red, passing through an obstacle with collision cost 100100). The goal’s position is G. Cost22200200d^min≈d^max≈2 d_ ≈ d_ ≈ 2Safed^min≈d^max≈200 d_ ≈ d_ ≈ 200Dangerousclearly separable (b) When ϵ′≥αε ≥α, the CVaR bounds collapse to [d^min,d^max][ d_ , d_ ]. The return estimators for the safe path (≈2≈ 2) and dangerous path (≈200≈ 200) remain well-separated. Figure 7. Illustration of bound-based action selection when ϵ′≥αε ≥α. (a) The agent chooses between a safe path (cost ≈1×2=2≈ 1× 2=2) and a dangerous path through an obstacle (cost ≈100×2=200≈ 100× 2=200). (b) Although the CVaR bounds collapse to [d^min,d^max][ d_ , d_ ], the return estimators remain well-separated, enabling the agent to distinguish between the two paths. When the constraint ϵ′<αε <α required for the original bounds is violated—as in this example where ϵ=α=0.1ε=α=0.1 and hence ϵ′≥ϵ≥αε ≥ε≥α—the bounds in Theorem 7.4 reduce to d^max d_ and d^min d_ , causing the upper and lower bounds to coincide. Nevertheless, decision making remains possible: the estimators for the safe and dangerous paths differ substantially (≈2≈ 2 versus ≈200≈ 200), enabling the agent to distinguish between them. By Corollary 6.4, the guarantees stated in Theorem 7.4 and Theorem 7.3 also apply to the specific setting in which the observation model is simplified, with the distributional discrepancy ϵε between the original and simplified observation models defined as in Corollary 6.4. As shown in Section 7, this setting can be resolved within the framework of online planning. 8. Limitations The bounds in Theorem 6.2 depend on the accumulation of one-step distributional discrepancies over the planning horizon, which may limit their effectiveness for long-horizon problems. Importantly, this accumulation does not necessarily grow linearly with the horizon and is highly problem dependent. For example, in a Light–Dark environment, the agent receives observations only in light regions and relies exclusively on the state-transition model in dark regions. As a result, no distributional discrepancy is accumulated in dark regions, since the observation model is not invoked. Consequently, the effective distributional discrepancy can grow sublinearly with the horizon. This behavior is examined empirically in the experiments section, where we also consider a more challenging variant of the Light–Dark environment in which distributional discrepancy accumulates even in dark regions. Moreover, even when the distributional discrepancy becomes large relative to α, the agent can still act. In this case, the value function bounds collapse to their extrema; specifically, the upper value function bound reduces to d^max d_ (Theorem 7.4), which is expected to be low in safe regions and high in dangerous ones. Analogous considerations hold for the lower bound. Consequently, decision making relies on minimum and maximum return samples conditioned on the path and policy, while the simplified observation model continues to provide computational acceleration, as it remains necessary for sampling return realizations. Finally, the proposed simplification framework yields computational gains only when sampling from the state-transition model is cheaper than sampling from the observation model. The bounds in Theorem 6.2 require samples from both the simplified observation model and the state-transition model to compensate for the absence of the original observation model. Consequently, if the state-transition model is computationally more expensive than the original observation model, the simplification approach would increase rather than decrease planning time. This limitation is shared by other observation model simplification frameworks (Lev-Yehudi et al., 2024). 9. Experiments In this section, we evaluate our derived bounds across several standard benchmark environments. We demonstrate the efficacy of our bounds by examining their performance on selected action sequences, illustrating their capacity to distinguish between safe and unsafe trajectories while achieving computational acceleration relative to the baseline model. We subsequently demonstrate the integration of these bounds into open-loop planning frameworks. All simulations were conducted using the POMDPPlanners package (Pariente and Indelman, 2026). Detailed simulation configurations are provided in Appendix E, and hardware specifications in Appendix G. 9.1. Theoretical CVaR Bounds (a) (b) (c) (d) 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 ϵε, showing how the bound interval widens as ϵε increases, while the true CVaR remains contained within the bounds. When ϵε exceeds the risk level α, 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 α=0.2α=0.2 and probability of error δ=0.05δ=0.05. Figure 8b uses α=0.5α=0.5. Figures 8c and 8d display 95% confidence intervals around the empirical means. Specifically, we compare a truncated Gaussian Mixture Model (GMM) and its corresponding truncated Normal approximation for CVaR estimation under bounded support. Such a setting arises, for example, in POMDP planning, where a computationally expensive model used by the agent during online planning is replaced with a more tractable surrogate model, thereby improving the agent’s decision-making speed (Lev-Yehudi et al., 2024). In these settings, the agent’s decisions may rely on bounds for the original value function that are derived from the tractable surrogate model (Barenboim and Indelman, 2022). The GMM consists of five components with means μ1=0.2 _1=0.2, μ2=−0.2 _2=-0.2, μ3=−0.5 _3=-0.5, μ4=0.5 _4=0.5, μ5=0.0 _5=0.0, variances σ12=0.5 _1^2=0.5, σ22=0.2 _2^2=0.2, σ32=0.1 _3^2=0.1, σ42=0.1 _4^2=0.1, σ52=0.3 _5^2=0.3, and weights w1=0.3w_1=0.3, w2=0.2w_2=0.2, w3=0.05w_3=0.05, w4=0.05w_4=0.05, w5=0.4w_5=0.4. The Normal approximation matches the GMM’s mean and variance but cannot reproduce its multi-modal structure or outlier effects. All samples are truncated to the interval [−1,1][-1,1], which reshapes the tails and slightly distorts boundary components. We compute CVaR at the 20% quantile for sample sizes ranging from 100 to 10,000, with 100 independent repetitions per setting to ensure statistical reliability. The distributional discrepancy (ϵε in Theorem 5.7) between the truncated GMM and the truncated Normal distribution is assessed via simulation, by estimating their respective cumulative distribution functions over a common set of bins and computing the maximum difference across all bins. This setup enables a direct assessment of the trade-off between computational efficiency and statistical accuracy when approximating a complex truncated mixture by a single truncated Normal distribution. Figure 8c presents the sampling time comparison between the truncated GMM and the truncated Normal distribution, with an observed average time ratio of approximately 3.7 in favor of the Normal distribution. Figure 8d reports a total computational speedup of approximately 3.1 when comparing the process of sampling from the truncated GMM and estimating its CVaR to that of sampling from the truncated Normal and computing both upper and lower bounds as given in Theorem 5.7. Figure 8a illustrates the convergence behavior of the CVaR bounds as a function of the number of samples, comparing estimates obtained from the truncated GMM with bounds derived from the truncated Normal surrogate. It is important to note that these bounds are obtained without requiring full knowledge of the underlying GMM distribution. Instead, they rely solely on the discrepancy between the corresponding CDFs. Figure 8b depicts the sensitivity of the CVaR bounds to the distributional discrepancy ϵε. In this experiment, the base distribution F is a truncated Normal on [−1,1][-1,1] with mean 0 and standard deviation 11. For each value of ϵ∈[0,0.5]ε∈[0,0.5], a perturbed distribution G is constructed such that its CDF satisfies G(x)=min⁡(F(x)+ϵ,1)G(x)= (F(x)+ε,1), yielding a Kolmogorov–Smirnov distance of exactly ϵε between F and G by construction. Samples from G are obtained via inverse transform sampling. The resulting bounds grow monotonically with ϵε while consistently enclosing the true CVaR of F. When ϵε exceeds the risk level α, the bounds become trivial, spanning the full support; this is expected, since a large distributional discrepancy implies that Y provides negligible information about X. We evaluated the concentration bounds established by (Thomas and Learned-Miller, 2019) alongside our proposed bounds from Theorem 5.5 on a set of probability distributions: Beta⁡(2,2)Beta(2,2), Beta⁡(0.5,0.5)Beta(0.5,0.5), Beta⁡(2,5)Beta(2,5), Beta⁡(5,2)Beta(5,2), Beta⁡(10,2)Beta(10,2), Beta⁡(2,10)Beta(2,10), and the Laplace(0,1)(0,1) distribution. These distributions were selected to match those used in the original study by (Thomas and Learned-Miller, 2019), enabling a direct comparison under identical conditions. For each distribution, our bounds precisely coincide with those reported by (Thomas and Learned-Miller, 2019), resulting in complete overlap between the two sets of bounds. The graphs exhibiting these results are available in Appendix B (Figure 16). 9.2. POMDP Environments We evaluate our approach on three POMDP domains: 2D Light-Dark Navigation, Laser Tag, and Push. Each environment contains dangerous areas where the likelihood of incurring high penalties is elevated, requiring the agent to balance risk-aware decision-making with task completion. In the 2D Light-Dark POMDP, an agent must navigate from a start position to a goal region while avoiding these dangerous areas. The observation noise is position-dependent, with lower uncertainty near designated beacon locations, requiring the agent to balance information gathering with goal-directed movement. In Laser Tag POMDP, the agent must locate and tag an opponent in a partially observable environment using noisy range-bearing measurements from multiple sensors, resulting in an 8-dimensional observation space, while navigating around dangerous regions. The Push POMDP involves manipulating an object to a target location while managing partial observability about the object’s position through noisy 2-dimensional observations and avoiding dangerous areas. For each domain, we construct two environment variants: an original environment with a complex observation model represented by Gaussian Mixture Models (GMMs) capturing multi-modal observation distributions, and a simplified environment where this complex distribution is approximated using a single Gaussian distribution. This approximation introduces a controlled model mismatch, allowing us to evaluate the robustness of planning algorithms when the true observation dynamics differ from the assumed model. The GMM-based observation models enable realistic representation of sensor fusion, occlusions, and multi-hypothesis tracking, while the Gaussian approximation provides computational tractability at the cost of distributional fidelity. Full environment specifications are provided in Appendix D. 9.3. Online Distributional Discrepancy Estimation To compute the distributional discrepancy ϵε appearing in Corollary 6.4, we define Q0Q_0 as the uniform distribution over the axis-aligned square whose lower-left corner is xstartx_start and upper-right corner is xgoalx_goal. Samples xnΔx_n are drawn from the mixture distribution (pZ+qZ)/2(p_Z+q_Z)/2; that is, with probability 0.50.5, a sample is drawn from the original GMM observation model, and with probability 0.50.5, from the simplified observation model. The estimator Δ^s(xnΔ) ^s(x_n ) is then defined as (51) Δ^s(xnΔ)=∑j=1Nz2⋅|pz(zjn∣xnΔ)−qz(zjn∣xnΔ)|pz(zjn∣xnΔ)+qz(zjn∣xnΔ), ^s(x_n )= _j=1^N_z2· |p_z(z_j^n x_n )-q_z(z_j^n x_n ) |p_z(z_j^n x_n )+q_z(z_j^n x_n ), and is evaluated over NΔ=100N =100 presampled states. Here, Nz=2000N_z=2000 denotes the number of sampled observations used in the estimation procedure. Given equation (51), the belief-dependent one-step distributional discrepancy m^(b¯t,a) m( b_t,a) can be estimated accordingly. Since the state-transition model in (37) assigns exponentially small probability to states that are far from the current state, we employ a K-Nearest Neighbors (KNN) approach with K=10K=10 to select a subset of the samples xnΔ\x_n \ that lie in the vicinity of a given state x. The estimation is then performed over this localized subset, rather than the entire collection xnΔ\x_n \. 9.4. Empirical Static CVaR Bound Evaluation: Open-Loop Policies To evaluate the bounds we define for each environment two action-sequences - one that dictates a safe path and the other that dictates a dangerous path. Figure 9 shows that bounds based on the simplified observation models distinguish between the two action sequences and would eliminate the dangerous path under action elimination. The estimated distributional discrepancies are ϵ=0.38ε=0.38 and ϵ=0.36ε=0.36 for the dangerous and safe paths in Light-Dark, ϵ=0.52ε=0.52 and ϵ=0.53ε=0.53 in Laser Tag, and ϵ=0.24ε=0.24 and ϵ=0.20ε=0.20 in Push. Despite high distributional discrepancies across paths within each environment, the bounds successfully discriminate between the two action sequences. Notably, in the Laser Tag environment, the estimated ϵε exceeds 0.50.5, which is the value of the risk level α; nevertheless, the bounds remain sufficiently tight to separate the safe and dangerous action sequences. Comparing the bounds computation time using the original observation models using the bounds of (Thomas and Learned-Miller, 2019) to our bounds that use the simplified observation models, we gain approximately 20.89×20.89× acceleration in Light-Dark POMDP, 8.87×8.87× in Laser Tag POMDP, and 7.62×7.62× in Push POMDP. Figure 10 illustrates how the acceleration remains solid when the number of return samples and horizon changes. Figure 11 presents the evolution of the CVaR bounds as a function of the planning horizon for the same safe and dangerous action sequences depicted in Figure 9, where each action sequence is decomposed into sub-sequences of increasing horizon length. In the Light-Dark environment, the bounds are separated from the earliest horizon, since the agent’s start state is close to the dangerous area and the dangerous path immediately traverses the high-cost region. In Laser Tag and Push, the bounds of both paths are similar at early horizons, before the dangerous path enters the hazardous region, confirming that the bound separation is driven by the actual risk difference rather than by an artifact of the bounding mechanism. In Laser Tag, the separation is most pronounced: both paths have comparable bounds up to horizon 44, after which the dangerous path’s bounds increase sharply as it enters the dangerous area, while the safe path remains at low values throughout. In Push, the two paths overlap closely up to horizon 44, and the bounds diverge around horizon 66 when the dangerous path approaches the hazardous region. These patterns are consistent across both α=0.5α=0.5 and α=0.1α=0.1, indicating that the bounds remain discriminative under a more risk-averse setting. The bottom row of Figure 11 further examines the sensitivity of the bounds to the risk level α at a fixed horizon. As α decreases, the CVaR focuses on worse-case outcomes, causing both the bound values and the bound intervals to increase; nevertheless, the bounds maintain a clear separation between the safe and dangerous paths across the full range of α. (a) (b) (c) (d) (e) (f) 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 δ=0.05δ=0.05. (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) 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 α=0.5α=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. (a) (b) (c) (d) (e) (f) (g) (h) (i) 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 α=0.5α=0.5 and α=0.1α=0.1, respectively. Row 3: bounds as a function of the risk level α at a fixed horizon. As the horizon increases, the accumulated distributional discrepancy grows, causing the bounds to widen. As α 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 α. Bounds are computed with probability of error δ=0.05δ=0.05. 9.5. Empirical Static CVaR Bound Evaluation: Closed-Loop Policy The preceding evaluation assessed bounds on fixed open-loop action sequences. We now demonstrate that the framework extends to closed-loop planners, using the Light-Dark POMDP as a test case. Specifically, we use the neural network trained by BetaZero (Moss et al., 2024a) as a deterministic policy: BetaZero learns offline approximations of the optimal policy and value function for POMDPs and combines them with online Monte Carlo tree search at test time. Here, we extract a deterministic closed-loop policy from the trained network by selecting at each belief state the action with minimum predicted cost. The BetaZero configuration used in our experiments is detailed in Appendix F. We evaluate two objectives. First, we test whether the bounds computed under the simplified observation model successfully distinguish between policies of differing risk levels. We compare the BetaZero policy against the same safe and dangerous action sequences from the preceding subsection. As shown in Figures 12 and 13, the bounds clearly separate the dangerous sequence from both the safe sequence and the BetaZero policy, with non-overlapping bound intervals. The trajectory plot confirms this ordering: the dangerous sequence traverses the high-cost region, while the BetaZero policy navigates through the illuminated safe zones. This separation persists across the full range of risk levels α and planning horizons. Second, we show that evaluating the bounds under the simplified observation model is substantially faster than under the original model. Figure 14 shows a consistent ≈5×≈5× speedup, stable across planning horizons from 44 to 1212 and return sample counts from 100100 to 10001000. (a) (b) Figure 12. Evaluation of the BetaZero neural network policy against the safe and dangerous action sequences in the Light-Dark POMDP (α=0.1α=0.1, H=9H=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 δ=0.05δ=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. (a) (b) 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 α at horizon H=9H=9. Figure 13b: bounds as a function of the planning horizon at α=0.1α=0.1. The dangerous sequence remains clearly separated from the policy and safe sequence across all conditions. Bounds are computed with probability of error δ=0.05δ=0.05. (a) (b) (c) (d) 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 (α=0.1α=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 ≈5×≈5× speedup across all conditions. Error bars indicate 95%95\% confidence intervals. 10. Conclusions In this work we introduced a belief-simplification framework for risk-averse policy evaluation in POMDPs under a static CVaR objective, with guaranteed bounds on the resulting action-value function estimators, enabling accelerated online policy evaluation. Our approach establishes bounds on the true action-value function by leveraging an approximate action-value function computed under a simplified belief-transition model. We further derived specialized bounds for the case of a simplified observation model and showed how these bounds can be employed to accelerate online planning. To support these results, we developed the requisite mathematical foundations for bounding the CVaR of a random variable X through an auxiliary random variable Y, under assumptions relating their respective cumulative and density functions. These theoretical results are independent of the POMDP-planning setting and provide a general analytical framework that can facilitate future research on risk-sensitive decision making. Our empirical evaluation, focused on observation model simplification, demonstrates the practical utility of the framework in both open-loop and closed-loop settings. In the open-loop case, the bounds correctly distinguish action sequences of differing risk levels across multiple environments and risk parameters. In the closed-loop case, using a BetaZero neural-network policy, the bounds successfully rank policies by risk level with non-overlapping bound intervals, while achieving a consistent ≈5×≈5× computational speedup over evaluation under the original model. The theoretical framework accommodates general belief-transition model simplifications, including state-transition models, whose empirical investigation we leave for future work. References C. Acerbi and D. Tasche (2002) On the coherence of expected shortfall. Journal of banking & finance 26 (7), p. 1487–1503. Cited by: Appendix A, Appendix A. M. Ahmadi, A. Dixit, J. W. Burdick, and A. D. Ames (2021a) Risk-averse stochastic shortest path planning. In 2021 60th IEEE Conference on Decision and Control (CDC), p. 5199–5204. Cited by: §2. M. Ahmadi, M. Ono, M. D. Ingham, R. M. Murray, and A. D. Ames (2020) Risk-averse planning under uncertainty. In 2020 American Control Conference (ACC), p. 3305–3312. Cited by: §2. M. Ahmadi, U. Rosolia, M. D. Ingham, R. M. Murray, and A. D. Ames (2021b) Constrained risk-averse markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, p. 11718–11725. Cited by: §2. M. Ahmadi, U. Rosolia, M. D. Ingham, R. M. Murray, and A. D. Ames (2023) Risk-averse decision making under uncertainty. IEEE Transactions on Automatic Control 69 (1), p. 55–68. Cited by: §1. P. Artzner, F. Delbaen, J. Eber, and D. Heath (1999) Coherent measures of risk. Mathematical finance 9 (3), p. 203–228. Cited by: §2. M. Barenboim and V. Indelman (2022) Adaptive information belief space planning. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, L. D. Raedt (Ed.), p. 4588–4596. Note: Main Track External Links: Document, Link Cited by: §9.1. M. Barenboim and V. Indelman (2023) Online pomdp planning with anytime deterministic guarantees. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36, p. 79886–79902. External Links: Link Cited by: §1. M. Barenboim and V. Indelman (2026) Online pomdp planning with anytime deterministic optimality guarantees. Artificial Intelligence 350, p. 104442. External Links: ISSN 0004-3702, Document, Link Cited by: §2. D. B. Brown (2007) Large deviations bounds for estimating conditional value-at-risk. Operations Research Letters 35 (6), p. 722–730. Cited by: §2, §3.3, §3.3. Y. Chow, A. Tamar, S. Mannor, and M. Pavone (2015) Risk-sensitive and robust decision-making: a cvar optimization approach. Advances in neural information processing systems 28. Cited by: §1, §2, §2. M. Cubuktepe, N. Jansen, S. Junges, A. Marandi, M. Suilen, and U. Topcu (2021) Robust finite-state controllers for uncertain pomdps. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, p. 11792–11800. Cited by: §2. W. Dabney, M. Rowland, M. Bellemare, and R. Munos (2018) Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI conference on artificial intelligence, Vol. 32. Cited by: §2. A. Dixit, M. Ahmadi, and J. W. Burdick (2023) Risk-averse receding horizon motion planning for obstacle avoidance using coherent risk measures. Artificial Intelligence 325, p. 104018. Cited by: §2. A. Dvoretzky, J. Kiefer, and J. Wolfowitz (1956) Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator. The Annals of Mathematical Statistics 27 (3), p. 642 – 669. External Links: Document, Link Cited by: Appendix A, §5.2, §5.2. P. Hou, W. Yeoh, and P. Varakantham (2016) Solving risk-sensitive pomdps with and without cost observations. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 30. Cited by: §1. S. Koenig and R. G. Simmons (1994) Risk-sensitive planning with probabilistic decision graphs. In Principles of Knowledge Representation and Reasoning, p. 363–373. Cited by: §2. I. Lev-Yehudi, M. Barenboim, and V. Indelman (2024) Simplifying complex observation models in continuous pomdp planning with probabilistic guarantees and practice. Vol. 38, p. 20176–20184. External Links: Link, Document Cited by: §1, §2, §7.2, §8, §9.1. M. H. Lim, T. J. Becker, M. J. Kochenderfer, C. J. Tomlin, and Z. N. Sunberg (2023) Optimality guarantees for particle belief approximation of pomdps. Journal of Artificial Intelligence Research 77, p. 1591–1636. Cited by: §3.2. A. Majumdar and M. Pavone (2020) How should a robot assess risk? towards an axiomatic theory of risk in robotics. In Robotics Research: The 18th International Symposium ISRR, p. 75–84. Cited by: §1, §2. J. Marecki and P. Varakantham (2010) Risk-sensitive planning in partially observable environments. In AAMAS, p. 1357–1368. Cited by: §1. R. J. Moss, A. Corso, J. Caers, and M. J. Kochenderfer (2024a) BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximations. In Reinforcement Learning Conference (RLC), Cited by: Appendix F, §9.5. R. J. Moss, A. Jamgochian, J. Fischer, A. Corso, and M. J. Kochenderfer (2024b) ConstrainedZero: Chance-Constrained POMDP Planning Using Learned Probabilistic Failure Surrogates and Adaptive Safety Constraints. In International Joint Conference on Artificial Intelligence (IJCAI), Cited by: §1. M. Ono, M. Pavone, Y. Kuwata, and J. Balaram (2015) Chance-constrained dynamic programming with application to risk-aware robotic space exploration. Autonomous Robots 39, p. 555–571. Cited by: §2. T. Osogami (2015) Robust partially observable markov decision process. In International Conference on Machine Learning, p. 106–115. Cited by: §2. C. H. Papadimitriou and J. N. Tsitsiklis (1987a) The complexity of markov decision processes. Math. Oper. Res. 12 (3), p. 441–450. External Links: ISSN 0364-765X Cited by: §1. C. H. Papadimitriou and J. N. Tsitsiklis (1987b) The complexity of markov decision processes. Math. Oper. Res. 12, p. 441–450. External Links: Link Cited by: §2. Y. Pariente and V. Indelman (2026) POMDPPlanners: open-source package for pomdp planning. External Links: 2602.20810, Link Cited by: §9. G. C. Pflug (2000) Some remarks on the value-at-risk and the conditional value-at-risk. Probabilistic constrained optimization: Methodology and applications, p. 272–281. Cited by: §3.3. R. T. Rockafellar, S. Uryasev, et al. (2000) Optimization of conditional value-at-risk. Journal of risk 2, p. 21–42. Cited by: §2, §3.3. P. Rodrigues Quemel e Assis Santana, S. Thiébaux, and B. Williams (2016) RAO*: an algorithm for chance-constrained pomdp’s. Proceedings of the AAAI Conference on Artificial Intelligence 30 (1). External Links: Link, Document Cited by: §1. D. Silver and J. Veness (2010) Monte-carlo planning in large pomdps. Advances in neural information processing systems 23. Cited by: §1. Z. Sunberg and M. Kochenderfer (2018) Online algorithms for pomdps with continuous state, action, and observation spaces. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 28, p. 259–263. Cited by: §1. P. Thomas and E. Learned-Miller (2019) Concentration inequalities for conditional value at risk. In Proceedings of the 36th International Conference on Machine Learning, K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, p. 6225–6233. External Links: Link Cited by: Appendix A, Appendix A, Appendix B, Figure 16, §2, §3.3, §5.1, §5.2, §9.1, §9.4. H. Xu and S. Mannor (2010) Distributionally robust markov decision processes. Advances in Neural Information Processing Systems 23. Cited by: §1, §2. A. Zhitnikov and V. Indelman (2022) Simplified risk aware decision making with belief dependent rewards in partially observable domains. Artificial Intelligence, Special Issue on “Risk-Aware Autonomous Systems: Theory and Practice”. Cited by: §1, §2. A. Zhitnikov, O. Sztyglic, and V. Indelman (2025) No compromise in solution quality: speeding up belief-dependent continuous partially observable markov decision processes via adaptive multilevel simplification. The International Journal of Robotics Research 44 (2), p. 157–195. External Links: Document, Link, https://doi.org/10.1177/02783649241261398 Cited by: §1. Appendix A CVaR Bounds Proofs Theorem A.1. Let X and Y be random variables and ϵ∈[0,1]ε∈[0,1]. (1) Upper Bound: assume that P(X≤bX)=1,P(Y≤bY)=1P(X≤ b_X)=1,P(Y≤ b_Y)=1 and ∀z∈ℝ,FY(z)−FX(z)≤ϵ∀ z ,F_Y(z)-F_X(z)≤ε, then (a) If α>ϵα>ε, (52) CVaRα⁡(X)≤ϵαmax⁡(bX,bY)+(1−ϵα)CVaRα−ϵ⁡(Y).CVaR_α(X)≤ εα (b_X,b_Y)+(1- εα)CVaR_α-ε(Y). (b) If α≤ϵα≤ε, then CVaRα⁡(X)≤max⁡(bX,bY)CVaR_α(X)≤ (b_X,b_Y). (2) Lower Bound: If P(X≥aX)=1,P(Y≥aY)=1P(X≥ a_X)=1,P(Y≥ a_Y)=1 and ∀z∈ℝ,FX(z)−FY(z)≤ϵ∀ z ,F_X(z)-F_Y(z)≤ε, then (a) If α+ϵ≤1α+ε≤ 1, (53) CVaRα⁡(X)≥(1+ϵα)CVaRα+ϵ⁡(Y)−ϵαCVaRϵ⁡(Y)CVaR_α(X)≥(1+ εα)CVaR_α+ε(Y)- εαCVaR_ε(Y) (b) If α+ϵ>1α+ε>1 and amin=min⁡(aX,aY)a_min= (a_X,a_Y), (54) CVaRα⁡(X)≥1α([Y]−ϵCVaRϵ⁡(Y)+(α+ϵ−1)amin)CVaR_α(X)≥ 1α (E[Y]- _ε(Y)+(α+ε-1)a_min ) Proof. The strategy of the proof is to construct two distributions derived from FYF_Y, denoted FYLF_Y^L and FYUF_Y^U, such that FXF_X is stochastically bounded between them; that is, FYL≤FX≤FYUF_Y^L≤ F_X≤ F_Y^U. Consequently, since CVaR is a coherent risk measure, it follows that (55) CVaRαFYL≤CVaRαFX≤CVaRαFYU,CVaR_α^F_Y^L _α^F_X _α^F_Y^U, where CVaRαFYLCVaR_α^F_Y^L, CVaRαFXCVaR_α^F_X, and CVaRαFYUCVaR_α^F_Y^U denote the CVaR at level α corresponding to the distributions FYLF_Y^L, FXF_X, and FYUF_Y^U, respectively. Let amin=min⁡(aX,aY)a_ = (a_X,a_Y) and bmin=min⁡(bX,bY)b_ = (b_X,b_Y). Define the interval [bmin,bX)[b_ ,b_X) to be ∅ if bmin=bXb_ =b_X, and equal to [bY,bX)[b_Y,b_X) otherwise. Analogously, define [amin,aX)[a_ ,a_X) in the same manner. We then define upper and lower bounds for FYF_Y as follows (see Figure 15): (56) FYU(y)=0y<max⁡(aX,q1−ϵY)min⁡(FY(y)−ϵ,1−ϵ)y∈[max⁡(aX,q1−ϵY),bmin)1−ϵy∈[bmin,bX)1y≥max⁡(bX,bY),F_Y^U(y)= cases0&y< (a_X,q_1-ε^Y)\\ (F_Y(y)-ε,1-ε)&y∈[ (a_X,q_1-ε^Y),b_min)\\ 1-ε&y∈[b_min,b_X)\\ 1&y≥ (b_X,b_Y), cases (57) FYL(y)=0y<aminϵy∈[amin,aY)min⁡(FY(y)+ϵ,1)y∈[aY,min⁡(qϵY,bX))1y≥min⁡(qϵY,bX).F_Y^L(y)= cases0&y<a_min\\ ε&y∈[a_min,a_Y)\\ (F_Y(y)+ε,1)&y∈[a_Y, (q_ε^Y,b_X))\\ 1&y≥ (q_ε^Y,b_X). cases Figure 15. Illustration of the upper and lower bounds FYUF_Y^U and FYLF_Y^L on the cumulative distribution function FXF_X. As a first step, we verify that FYLF_Y^L and FYUF_Y^U are valid CDFs and that they satisfy FYL≤FX≤FYUF_Y^L≤ F_X≤ F_Y^U. To establish that F is a CDF, it suffices to verify the following properties: (1) F is non-decreasing; (2) F:ℝ→[0,1]F:R→[0,1] with limx→∞F(x)=1 _x→∞F(x)=1 and limx→−∞F(x)=0 _x→-∞F(x)=0; (3) F is right-continuous. Proof that FYLF_Y^L is a CDF: (1) On the interval [aY,min⁡(q1−ϵY,bX))[a_Y, (q_1-ε^Y,b_X)), the function FYLF_Y^L is monotone increasing, since FYF_Y is monotone increasing by virtue of being a CDF. Outside this interval, FYLF_Y^L is constant and consequently preserves monotonicity. (2) By definition, limy→∞FYL(y)=1 _y→∞F_Y^L(y)=1 and limy→−∞FYL(y)=0 _y→-∞F_Y^L(y)=0. We need to show that FYLF_Y^L is bounded between 0 and 1. By its definition, FYLF_Y^L is bounded between 0 and 1. (3) Within the interval [aY,min⁡(qϵY,bX))[a_Y, (q_ε^Y,b_X)), FYLF_Y^L is right-continuous since FYF_Y is right-continuous as a CDF. Outside this interval, FYLF_Y^L is constant and hence also right-continuous. Proof that FYUF_Y^U is a CDF: (1) On the interval [max⁡(aX,q1−ϵY),bmin)[ (a_X,q_1-ε^Y),b_min), the function FYUF_Y^U is monotone increasing, since FYF_Y is monotonically increasing by virtue of being a CDF. Outside this interval, FYUF_Y^U is constant and consequently preserves monotonicity. (2) By definition, limy→∞FYU(y)=1 _y→∞F_Y^U(y)=1 and limy→−∞FYU(y)=0 _y→-∞F_Y^U(y)=0. By its definition, FYUF_Y^U is bounded between 0 and 1. (3) Within the interval [max⁡(aX,q1−ϵY),bmin)[ (a_X,q_1-ε^Y),b_min), FYUF_Y^U is right-continuous since FYF_Y is right-continuous as a CDF. Outside this interval, FYUF_Y^U is constant and hence also right-continuous. Proof that FYL≤FX≤FYUF_Y^L≤ F_X≤ F_Y^U: To establish that FYL≤FX≤FYUF_Y^L≤ F_X≤ F_Y^U, we need to show that for all z∈ℝz , FYL(z)≥FX(z)≥FYU(z)F_Y^L(z)≥ F_X(z)≥ F_Y^U(z). Let z∈ℝz . • If z<aminz<a_min then FYL(z)=0=FX(z)F_Y^L(z)=0=F_X(z). • If z∈[amin,aY)z∈[a_min,a_Y) then FX(y)=FX(y)−FY(y)+FY(y)≤|FX(y)−FY(y)|+FY(y)≤ϵ+FY(y)=ϵ=FYL(y)F_X(y)=F_X(y)-F_Y(y)+F_Y(y)≤|F_X(y)-F_Y(y)|+F_Y(y)≤ε+F_Y(y)=ε=F_Y^L(y). • If z∈[aY,min⁡(qϵY,bX))z∈[a_Y, (q_ε^Y,b_X)) we assume that FY(z)+ϵ≤1F_Y(z)+ε≤ 1 because otherwise FYL(z)=1F_Y^L(z)=1 and the inequality holds. FYL(z)=FY(z)+ϵ=FY(z)−FX(z)+FX(z)+ϵ≥FX(z)−|FY(z)−FX(z)|+ϵ≥FX(z)F_Y^L(z)=F_Y(z)+ε=F_Y(z)-F_X(z)+F_X(z)+ε≥ F_X(z)-|F_Y(z)-F_X(z)|+ε≥ F_X(z). • If z≥min⁡(qϵY,bX)z≥ (q_ε^Y,b_X) then FYL(z)=1≥FX(z)F_Y^L(z)=1≥ F_X(z). and therefore FYL≤FXF_Y^L≤ F_X. Note that the last proof holds when bX=∞b_X=∞, making FYLF_Y^L a valid CDF when the support of X is not bounded from above. • If z<max⁡(aX,q1−ϵY)z< (a_X,q_1-ε^Y) then FYU(z)=0≤FX(z)F_Y^U(z)=0≤ F_X(z). • If z∈[max⁡(aX,q1−ϵY),bmin)z∈[ (a_X,q_1-ε^Y),b_min) then FYU(z)≤FY(z)−ϵ=FY(z)−FX(z)+FX(z)−ϵ≤|FY(z)−FX(z)|+FX(z)−ϵ≤ϵ+FX(z)−ϵ=FX(z)F_Y^U(z)≤ F_Y(z)-ε=F_Y(z)-F_X(z)+F_X(z)-ε≤|F_Y(z)-F_X(z)|+F_X(z)-ε≤ε+F_X(z)-ε=F_X(z). • If z∈[bmin,bX)z∈[b_min,b_X) then FYU(z)=1−ϵ=FY(z)−ϵ=FY(z)−ϵ+FX(z)−FX(z)≤FX(z)−ϵ+|FY(z)−FX(z)|≤FX(z)F_Y^U(z)=1-ε=F_Y(z)-ε=F_Y(z)-ε+F_X(z)-F_X(z)≤ F_X(z)-ε+|F_Y(z)-F_X(z)|≤ F_X(z) and therefore FX≤FYUF_X≤ F_Y^U. Note that the last proof holds when aX=−∞a_X=-∞, making FYUF_Y^U a valid CDF when the support of X is not bounded from below. Next, we derive bounds for the CVaR associated with FYUF_Y^U and FYLF_Y^L. Upper bound for CVaRαFYUCVaR_α^F_Y^U: From (Acerbi and Tasche, 2002), CVaR is equal to an integral of the VaR (58) CVaRαFYU=1α∫1−α1infy∈ℝ:FYU(y)≥τdτ=1α∫1−α+ϵ1+ϵinfy∈ℝ:FYU(y)≥τ−ϵdτ _α^F_Y^U= 1α _1-α^1 \y :F_Y^U(y)≥τ\dτ= 1α _1-α+ε^1+ε \y :F_Y^U(y)≥τ-ε\dτ If α≤ϵα≤ε, then 1−α+ϵ≥11-α+ε≥ 1, rendering the bound in the preceding equation trivial, as it attains the maximum value of the support of both X and Y. (59) 1α∫1−α+ϵ1+ϵinfy∈ℝ:FYU(y)≥τ−ϵ≤1α∫1−α+ϵ1+ϵmax⁡(bX,bY)τ=max⁡(bX,bY). 1α _1-α+ε^1+ε \y :F_Y^U(y)≥τ-ε\≤ 1α _1-α+ε^1+ε (b_X,b_Y)dτ= (b_X,b_Y). That is, CVaRα⁡(X)≤max⁡(bX,bY)CVaR_α(X)≤ (b_X,b_Y). If α>ϵα>ε, then 1−α+ϵ<11-α+ε<1, and the integral may be decomposed into one term that is trivially bounded by the maximum of the support and another term that can be computed explicitly (60) CVaRαFYU _α^F_Y^U =1α∫1−α+ϵ1+ϵinfy∈ℝ:FYU(y)≥τ−ϵdτ=1α[∫11+ϵinfy∈ℝ:FYU(y)≥τ−ϵdτ⏟≜A1 = 1α _1-α+ε^1+ε \y :F_Y^U(y)≥τ-ε\dτ= 1α[ _1^1+ε \y :F_Y^U(y)≥τ-ε\dτ_ A_1 +∫1−α+ϵ1infy∈ℝ:FYU(y)≥τ−ϵdτ⏟≜A2] + _1-α+ε^1 \y :F_Y^U(y)≥τ-ε\dτ_ A_2] The term A1A_1 is bounded, in a manner analogous to (59), by ϵmax⁡(bX,bY)ε (b_X,b_Y), which is essentially the tightest bound attainable given the definition of FYUF_Y^U. The term A2A_2 can be expressed in terms of the CVaR of Y, evaluated at a shifted confidence level. Specifically, the variable τ−ϵτ-ε in A2A_2 lies within the interval [1−α,1−ϵ][1-α,1-ε]. Over this range, for all y∈[max⁡(aX,q1−ϵY),bmin]y∈[ (a_X,q_1-ε^Y),b_ ], the inequality FYU(y)≤FY(y)−ϵF_Y^U(y)≤ F_Y(y)-ε holds. This follows because if q1−ϵY≥aXq_1-ε^Y≥ a_X, then by definition FYU(y)=min⁡(FY(y)−ϵ,1−ϵ)F_Y^U(y)= (F_Y(y)-ε,1-ε), and if aX>q1−ϵYa_X>q_1-ε^Y, then FYU(y)=0≤FY(y)−ϵF_Y^U(y)=0≤ F_Y(y)-ε for y∈[q1−ϵY,aX]y∈[q_1-ε^Y,a_X] and again FYU(y)=min⁡(FY(y)−ϵ,1−ϵ)F_Y^U(y)= (F_Y(y)-ε,1-ε) for y∈[aX,bmin]y∈[a_X,b_min]. (61) A2≤∫1−α+ϵ1infy∈ℝ:FY(y)−ϵ≥τ−ϵdτ=∫1−(α−ϵ)1infy∈ℝ:FY(y)≥τdτ=(α−ϵ)CVaRα−ϵ⁡(Y). A_2≤ _1-α+ε^1 \y :F_Y(y)-ε≥τ-ε\dτ= _1-(α-ε)^1 \y :F_Y(y)≥τ\dτ=(α-ε)CVaR_α-ε(Y). Note that the confidence level is valid, as α,ϵ∈(0,1)α,ε∈(0,1) and α>ϵα>ε imply α−ϵ∈(0,1)α-ε∈(0,1). By combining the previous two expressions, we obtain a single bound: (62) CVaRαFYU≤ϵmax⁡(bX,bY)α+(1−ϵα)CVaRα−ϵ⁡(Y).CVaR_α^F_Y^U≤ε (b_X,b_Y)α+(1- εα)CVaR_α-ε(Y). In the case where aX=−∞a_X=-∞, we have max⁡(aX,q1−ϵY)=q1−ϵY (a_X,q_1-ε^Y)=q_1-ε^Y, and the definition of FYUF_Y^U no longer involves aXa_X. Therefore, the inequality remains valid in the case of aX=−∞a_X=-∞. Lower bound for CVaRαFYLCVaR_α^F_Y^L: From (Acerbi and Tasche, 2002), CVaR is equal to an integral of the VaR (63) CVaRαFYL=1α∫1−α1infy∈ℝ:FYL(y)≥τdτ=1α∫1−(ϵ+α)1−ϵinfy∈ℝ:FYL(y)≥τ+ϵdτ. _α^F_Y^L= 1α _1-α^1 \y :F_Y^L(y)≥τ\dτ= 1α _1-(ε+α)^1-ε \y :F_Y^L(y)≥τ+ε\dτ. It holds that FYL(y)≤FY(y)+ϵF_Y^L(y)≤ F_Y(y)+ε and therefore (64) CVaRαFYL≥1α∫1−(ϵ+α)1−ϵinfy∈ℝ:FY(y)+ϵ≥τ+ϵdτ=1α∫1−(ϵ+α)1−ϵinfy∈ℝ:FY(y)≥τdτ _α^F_Y^L≥ 1α _1-(ε+α)^1-ε \y :F_Y(y)+ε≥τ+ε\dτ= 1α _1-(ε+α)^1-ε \y :F_Y(y)≥τ\dτ =1α[∫1−(ϵ+α)1infy∈ℝ:FY(y)≥τdτ−∫1−ϵ1infy∈ℝ:FY(y)≥τdτ] = 1α[ _1-(ε+α)^1 \y :F_Y(y)≥τ\dτ- _1-ε^1 \y :F_Y(y)≥τ\dτ] =1α[(α+ϵ)CVaRα+ϵ⁡(Y)−ϵCVaRϵ⁡(Y)]. = 1α[(α+ε)CVaR_α+ε(Y)- _ε(Y)]. In the case where ϵ+α>1ε+α>1, (65) CVaRαFYL _α^F_Y^L =1α∫1−(ϵ+α)1−ϵinfy∈ℝ:FYL(y)≥τ+ϵdτ = 1α _1-(ε+α)^1-ε \y :F_Y^L(y)≥τ+ε\dτ =1α[∫01−ϵinfy∈ℝ:FYL(y)≥τ+ϵdτ⏟≜A3+∫1−(ϵ+α)0infy∈ℝ:FYL(y)≥τ+ϵdτ⏟≜A4]. = 1α[ _0^1-ε \y :F_Y^L(y)≥τ+ε\dτ_ A_3+ _1-(ε+α)^0 \y :F_Y^L(y)≥τ+ε\dτ_ A_4]. (66) A3 A_3 ≥∫01−ϵinfy∈ℝ:FY(y)≥τdτ=∫01infy∈ℝ:FY(y)≥τdτ−∫1−ϵ1infy∈ℝ:FY(y)≥τdτ ≥ _0^1-ε \y :F_Y(y)≥τ\dτ= _0^1 \y :F_Y(y)≥τ\dτ- _1-ε^1 \y :F_Y(y)≥τ\dτ =[Y]−ϵCVaRϵ⁡(Y) =E[Y]- _ε(Y) In the case of A4A_4, after the change of variable, τ ranges from 1−α1-α to ϵε, and therefore (67) A4=∫1−αϵinfy∈ℝ:FYL(y)≥τdτ≥(α+ϵ−1)amin A_4= _1-α^ε \y :F_Y^L(y)≥τ\dτ≥(α+ε-1)a_min By combining the last equations to one bound we get (68) CVaRα⁡(X) _α(X) ≥CVaRαFYL≥1α([Y]−ϵCVaRϵ⁡(Y)+(α+ϵ−1)amin). _α^F_Y^L≥ 1α (E[Y]- _ε(Y)+(α+ε-1)a_min ). ∎ Theorem A.2. Given the definition of X,Y,ϵX,Y,ε and α as in Theorem 5.1, the lower and upper bounds of Theorem 5.1 converge to CVaRα⁡(X)CVaR_α(X) as ϵ→0ε→ 0. Proof. Let f and g be continuous functions such that f(0)f(0) and g(0)g(0) are finite. Then limx→0f(x)g(x)=(limx→0f(x))(limx→0g(x)) _x→ 0f(x)g(x)= ( _x→ 0f(x) ) ( _x→ 0g(x) ). This property will be used throughout the proof. Assume that FY(z)−FX(z)≤ϵF_Y(z)-F_X(z)≤ε for all z∈ℝz . Since we consider the limit as ϵ→0ε→ 0, we further assume that α>ϵα>ε when computing the bound. Noting that CVaR is continuous with respect to the confidence level, it follows that limϵ→0CVaRα−ϵ⁡(Y)=CVaRα⁡(Y) _ε→ 0CVaR_α-ε(Y)=CVaR_α(Y). (69) limϵ→0ϵαmax⁡(bX,bY)+(1−ϵα)CVaRα−ϵ⁡(Y)=limϵ→0(1−ϵα)CVaRα−ϵ⁡(Y)=limϵ→01−ϵαlimϵ→0CVaRα−ϵ⁡(Y)=CVaRα⁡(Y) _ε→ 0 εα (b_X,b_Y)+(1- εα)CVaR_α-ε(Y)= _ε→ 0(1- εα)CVaR_α-ε(Y)= _ε→ 01- εα _ε→ 0CVaR_α-ε(Y)=CVaR_α(Y) If FX(z)−FY(z)≤ϵF_X(z)-F_Y(z)≤ε for all z∈ℝz , then, since we consider the limit as ϵ→0ε→ 0, we assume in the derivation of the bound that α+ϵ≤1α+ε≤ 1. (70) limϵ→0(1+ϵα)CVaRα+ϵ⁡(Y)−ϵαCVaRϵ⁡(Y)=limϵ→01+ϵαlimϵ→0CVaRα+ϵ⁡(Y)−limϵ→0ϵαlimϵ→0CVaRϵ⁡(Y)=CVaRα⁡(Y). _ε→ 0(1+ εα)CVaR_α+ε(Y)- εαCVaR_ε(Y)= _ε→ 01+ εα _ε→ 0CVaR_α+ε(Y)- _ε→ 0 εα _ε→ 0CVaR_ε(Y)=CVaR_α(Y). ∎ Theorem A.3. Let X be a random variable, α∈(0,1],δ∈(0,0.5),ϵ=ln⁡(1/δ)/(2n)α∈(0,1],δ∈(0,0.5),ε= (1/δ)/(2n). Let X1,…,Xn∼iidFXX_1,…,X_n iid F_X be random variables that define the ECDF F^X F_X. (1) Upper Bound: If P(X≤b)=1P(X≤ b)=1, then (a) If α>ϵα>ε then P(CVaRα⁡(X)≤(1−ϵα)Cα−ϵF^X+ϵαb)>1−δP(CVaR_α(X)≤(1- εα)C_α-ε F_X+ εαb)>1-δ. (b) If α≤ϵα≤ε then CVaRα⁡(X)≤bCVaR_α(X)≤ b (2) Lower Bound: If P(X≥a)=1P(X≥ a)=1, then (a) If α+ϵ<1α+ε<1, then P(CVaRα⁡(X)≥(1+ϵα)Cα+ϵF^X−ϵαCϵF^X)>1−δP(CVaR_α(X)≥(1+ εα)C_α+ε F_X- εαC_ε F_X)>1-δ. (b) If α+ϵ≥1α+ε≥ 1, then P(CVaRα⁡(X)≥1α[(α+ϵ−1)a+EF^X[X]−ϵCϵF^X])>1−δP(CVaR_α(X)≥ 1α[(α+ε-1)a+E_ F_X[X]-ε C_ε F_X])>1-δ. Proof. From DKW inequality the following inequalities can be derived (Thomas and Learned-Miller, 2019) (71) Pr⁡(supx∈ℝ(F^(x)−F(x))≤ln⁡(1/δ)2n)≥1−δ,Pr⁡(supx∈ℝ(F^(x)−F(x))≥ln⁡(1/δ)2n)≥1−δ. ( _x ( F(x)-F(x) )≤ (1/δ)2n )≥ 1-δ, ( _x ( F(x)-F(x) )≥ (1/δ)2n )≥ 1-δ. Let ϵ=ln⁡(1/δ)2nε= (1/δ)2n. By using Theorem 5.1 we get the following. If α>ϵα>ε then (72) P(CVaRα⁡(X)≤α−ϵαCα−ϵF^X+ϵαb) P(CVaR_α(X)≤ α-εαC_α-ε F_X+ εαb) =P(Cα(X)≤α−ϵαCα−ϵF^X+ϵαb|supz∈ℝ(F^X−FX)≤ϵ)⏟=1P(supz∈ℝ(F^X−FX)≤ϵ)⏟>1−δ = P(C_α(X)≤ α-εαC_α-ε F_X+ εαb | _z ( F_X-F_X)≤ε)_=1 P( _z ( F_X-F_X)≤ε)_>1-δ +P(Cα(X)≤α−ϵαCα−ϵF^X+ϵαb|supz∈ℝ(F^X−FX)>ϵ)⏟≥0P(supz∈ℝ(F^X−FX)>ϵ)⏟≥0 + P(C_α(X)≤ α-εαC_α-ε F_X+ εαb | _z ( F_X-F_X)>ε)_≥ 0 P( _z ( F_X-F_X)>ε)_≥ 0 >1−δ. >1-δ. Observe that, conditional on the event supz∈ℝ(F^X(z)−FX(z))≤ϵ, _z ( F_X(z)-F_X(z) )≤ε, the bound in Theorem 5.1 holds deterministically. Consequently, the probability that Cα(X)≤α−ϵαCα−ϵF^X+ϵαbC_α(X)≤ α-εαC_α-ε F_X+ εαb holds, given supz∈ℝ(F^X(z)−FX(z))≤ϵ, _z ( F_X(z)-F_X(z) )≤ε, is equal to one. The same observation is necessary through the rest of the proof in a similar manner. If α+ϵ<1α+ε<1, then (73) P(Cα(X)≥(1+ϵα)Cα+ϵF^X−ϵαCϵF^X) P(C_α(X)≥(1+ εα)C_α+ε F_X- εαC_ε F_X) =P(Cα(X)≥(1+ϵα)Cα+ϵF^X−ϵαCϵF^X|supz∈ℝ(FX−F^X)≤ϵ)⏟=1P(supz∈ℝ(FX−F^X)≤ϵ)⏟>1−δ = P(C_α(X)≥(1+ εα)C_α+ε F_X- εαC_ε F_X | _z (F_X- F_X)≤ε)_=1 P( _z (F_X- F_X)≤ε)_>1-δ +P(Cα(X)≥(1+ϵα)Cα+ϵF^X−ϵαCϵF^X|supz∈ℝ(FX−F^X)>ϵ)⏟≥0P(supz∈ℝ(FX−F^X)>ϵ)⏟≥0 + P(C_α(X)≥(1+ εα)C_α+ε F_X- εαC_ε F_X | _z (F_X- F_X)>ε)_≥ 0 P( _z (F_X- F_X)>ε)_≥ 0 >1−δ >1-δ If α+ϵ≥1α+ε≥ 1, then (74) P(Cα(X)≥1α[(α+ϵ−1)a+EF^X[X]−ϵCϵF^X]) P(C_α(X)≥ 1α[(α+ε-1)a+E_ F_X[X]-ε C_ε F_X]) =P(Cα(X)≥1α[(α+ϵ−1)a+EF^X[X]−ϵCϵF^X]|supz∈ℝ(FX−F^X)≤ϵ)⏟=1P(supz∈ℝ(FX−F^X)≤ϵ)⏟>1−δ = P(C_α(X)≥ 1α[(α+ε-1)a+E_ F_X[X]-ε C_ε F_X] | _z (F_X- F_X)≤ε)_=1 P( _z (F_X- F_X)≤ε)_>1-δ +P(Cα(X)≥1α[(α+ϵ−1)a+EF^X[X]−ϵCϵF^X]|supz∈ℝ(FX−F^X)>ϵ)⏟≥0P(supz∈ℝ(FX−F^X)>ϵ)⏟≥0 + P(C_α(X)≥ 1α[(α+ε-1)a+E_ F_X[X]-ε C_ε F_X] | _z (F_X- F_X)>ε)_≥ 0 P( _z (F_X- F_X)>ε)_≥ 0 >1−δ >1-δ ∎ Theorem A.4. (Tighter CVaR Lower Bound) Let α∈(0,1)α∈(0,1), X and Y be random variables. Define a random variable YLY^L such that FYL(y)≜min⁡(1,FY(y)+g(y))F_Y^L(y) (1,F_Y(y)+g(y)) for g:ℝ→[0,∞)g:R→[0,∞). Assume limx→−∞g(x)=0 _x→-∞g(x)=0, g is continuous from the right and monotonic increasing. If ∀x∈ℝ,FX(x)≤FY(x)+g(x)∀ x ,F_X(x)≤ F_Y(x)+g(x), then FYLF_Y^L is a CDF and CVaRα⁡(YL)≤CVaRα⁡(X).CVaR_α(Y^L) _α(X). Proof. In order to prove that FYLF_Y^L is a CDF we need to prove that FYLF_Y^L is: (1) Monotonic increasing (2) F:ℝ→[0,1]F:R→[0,1], limx→∞FYL(x)=1 _x→∞F_Y^L(x)=1, limx→−∞FYL(x)=0 _x→-∞F_Y^L(x)=0 (3) Continuous from the right Monotonic increasing: Note that for every fi:ℝ→ℝ,i=1,2f_i:R ,i=1,2 that are monotonic increasing, f1(f2(x)))f_1(f_2(x))) is also monotonic increasing in x. Denote f(x):=min⁡(x,1)f(x):= (x,1) and f2(x):=FY(x)+g(x)f_2(x):=F_Y(x)+g(x). FY(x)F_Y(x) is a CDF and therefore monotonic increasing, so f2(x)f_2(x) is monotonic increasing as a sum of monotonic increasing functions. f1f_1 is also monotonic increasing, and FYL(x)=f1(f2(x))F_Y^L(x)=f_1(f_2(x)). Therefore FYL(x)F_Y^L(x) is monotonic increasing. Limits: (75) 1 1 ≥limx→∞FYL(x)=limx→∞min⁡(1,FY(x)+g(x))≥limx→∞min⁡(1,FY(x))=limx→∞FY(x)=1 ≥ _x→∞F_Y^L(x)= _x→∞ (1,F_Y(x)+g(x))≥ _x→∞ (1,F_Y(x))= _x→∞F_Y(x)=1 and therefore limx→∞FYL(x)=1 _x→∞F_Y^L(x)=1. 0 0 ≤limx→−∞FYL(x)=limx→−∞min⁡(1,FY(x)+g(x))≤limx→−∞FY(x)+g(x)=limx→−∞FY(x)+limx→−∞g(x)=0 ≤ _x→-∞F_Y^L(x)= _x→-∞ (1,F_Y(x)+g(x))≤ _x→-∞F_Y(x)+g(x)= _x→-∞F_Y(x)+ _x→-∞g(x)=0 and therefore limx→−∞FYL(x)=0 _x→-∞F_Y^L(x)=0. By definition ∀x∈ℝ,FYL(x)≤1∀ x ,F_Y^L(x)≤ 1, and ∀x∈ℝ,FYL(x)≥0∀ x ,F_Y^L(x)≥ 0 because both g and FYLF_Y^L are non negative functions. Continuity from the right: FYF_Y is continuous from the right because it is a CDF, and g is continuous from the right by assumption. Their sum FY+gF_Y+g is therefore continuous from the right, and since the constant function 11 is continuous, FYL=min⁡(1,FY+g)F_Y^L= (1,F_Y+g) is continuous from the right as the minimum of two right-continuous functions. Thus, FYLF_Y^L is a CDF. Bound proof: If YL≤XY^L≤ X, then CVaRα⁡(YL)≤CVaRα⁡(X)CVaR_α(Y^L) _α(X) because CVaR is a coherent risk measure. Note that if FY(x)+g(x)<1F_Y(x)+g(x)<1 then FX(x)≤FY(x)+g(x)=FYL(x),F_X(x)≤ F_Y(x)+g(x)=F_Y^L(x), and if FY(x)+g(x)≥1F_Y(x)+g(x)≥ 1, 1=FYL(x)≥FX(x)1=F_Y^L(x)≥ F_X(x). Therefore YL≤XY^L≤ X. ∎ Theorem A.5. Let α∈(0,1)α∈(0,1), X and Y be random variables. Define h:ℝ→[0,∞)h:R→[0,∞) to be a continuous function, g(z):=∫−∞zh(x)xg(z):= _-∞^zh(x)dx and YLY^L to be a random variable such that FYL(y):=min⁡(1,FY(y)+g(y))F_Y^L(y):= (1,F_Y(y)+g(y)). If limz→−∞g(z)=0 _z→-∞g(z)=0 and ∀x∈ℝ,fx(x)≤fy(x)+h(x)∀ x ,f_x(x)≤ f_y(x)+h(x), then FYLF_Y^L is a CDF and CVaRα⁡(YL)≤CVaRα⁡(X)CVaR_α(Y^L) _α(X). Proof. We will show the g satisfies the properties of Theorem 5.3, and therefore this theorem holds. We need to prove that (1) limz→−∞g(z)=0 _z→-∞g(z)=0 (2) g is continuous from the right. (3) g is monotonic increasing. (4) FX(y)≤FY(y)+g(y)F_X(y)≤ F_Y(y)+g(y) It is given in the theorem’s assumptions that limz→−∞g(z)=0 _z→-∞g(z)=0, so (1) holds. h is non negative and therefore g is monotonic increasing, so (3) holds. g is continuous if its derivative exists for all z∈ℝz . Let z∈ℝz and a<za<z. (76) dzg(z) ddzg(z) =dz∫−∞zh(x)x=dz[∫−∞ah(x)x+∫azh(x)x]=dz∫azh(x)x=h(z) = ddz _-∞^zh(x)dx= ddz[ _-∞^ah(x)dx+ _a^zh(x)dx]= ddz _a^zh(x)dx=h(z) where the third equality holds because ∫−∞ah(x)x=g(a) _-∞^ah(x)dx=g(a) is a constant that does not depend on z. The last equality holds from the fundamental theorem of calculus because h is continuous. Finally, (4) holds because (77) FX(y) F_X(y) ≜∫−∞yfx(x)x≤∫−∞yfy(x)+h(x)dx≜FY(y)+g(y). _-∞^yf_x(x)dx≤ _-∞^yf_y(x)+h(x)dx F_Y(y)+g(y). ∎ Corollary A.6. Let X be a random variable, α∈(0,1],δ∈(0,1),ϵ=ln⁡(1/δ)/(2n),a∈ℝ,b∈ℝα∈(0,1],δ∈(0,1),ε= (1/δ)/(2n),a ,b . Let X1,…,Xn∼iidFXX_1,…,X_n iid F_X be random variables that define the ECDF F^X F_X. Denote by U(n)U(n) and L(n)L(n) the upper and lower bounds respectively from Theorem 5.5, where n is the number of samples, then (1) If P(X≤b)=1P(X≤ b)=1, then limn→∞U(n)=a.s.CVaRα⁡(X) _n→∞U(n) a.s.=CVaR_α(X). (2) If P(X≥a)=1P(X≥ a)=1, then limn→∞L(n)=a.s.CVaRα⁡(X) _n→∞L(n) a.s.=CVaR_α(X). where a.s. denotes almost sure convergence. Proof. (78) limn→∞U(n)=a.slimn→∞(1−ϵα)Cα−ϵF^X+ϵαb=a.slimn→∞Cα−ϵF^X=limn→∞CαF^X=CαFX _n→∞U(n) a.s= _n→∞(1- εα)C_α-ε F_X+ εαb a.s= _n→∞C_α-ε F_X= _n→∞C_α F_X=C_α^F_X where the first and second equalities follow from the fact that ϵ→0ε→ 0 as n→∞n→∞; the third equality holds by the continuity of CVaR with respect to α; and the fourth equality holds by the almost sure convergence of the empirical CVaR of i.i.d. samples to the true CVaR. For the same reason, (79) limn→∞L(n)=a.slimn→∞(1+ϵα)Cα+ϵF^X−ϵαCϵF^X=a.slimn→∞Cα+ϵF^X=a.slimn→∞CαF^X=a.slimn→∞CαFX. _n→∞L(n) a.s= _n→∞(1+ εα)C_α+ε F_X- εαC_ε F_X a.s= _n→∞C_α+ε F_X a.s= _n→∞C_α F_X a.s= _n→∞C_α^F_X. ∎ Theorem A.7. Let X and Y be random variables, ϵ∈[0,1]ε∈[0,1], and η=ln⁡(1/δ)/(2n),ϵ′=min⁡(ϵ+η,1)η= (1/δ)/(2n),ε = (ε+η,1). Let Y1,…,YnY_1,…,Y_n be independent and identically distributed samples from FYF_Y, and denote by F^Y F_Y the associated empirical cumulative distribution function. (1) Upper Bound: If ∀z∈ℝ,FY(z)−FX(z)≤ϵ∀ z ,F_Y(z)-F_X(z)≤ε and P(X≤bX)=1,P(Y≤bY)=1P(X≤ b_X)=1,P(Y≤ b_Y)=1, then (a) If α>ϵ′α>ε then (80) P(CVaRα(X) P (CVaR_α(X) ≤ϵ′αmax(bX,bY)+(1−ϵ′α)CVaRα−ϵ′F^Y)>1−δ. ≤ ε α (b_X,b_Y)+(1- ε α)CVaR_α-ε F_Y )>1-δ. (b) If α≤ϵ′α≤ε , then CVaRα⁡(X)≤max⁡(bX,bY)CVaR_α(X)≤ (b_X,b_Y) (2) Lower Bound: If ∀z∈ℝ,FX(z)−FY(z)≤ϵ∀ z ,F_X(z)-F_Y(z)≤ε and P(X≥aX)=1,P(Y≥aY)=1P(X≥ a_X)=1,P(Y≥ a_Y)=1, then (a) If α+ϵ′≤1α+ε ≤ 1, then (81) P(CVaRα(X) P (CVaR_α(X) ≥(1+ϵ′α)CVaRα+ϵ′F^Y−ϵ′αCVaRϵ′F^Y)>1−δ. ≥(1+ ε α)CVaR_α+ε F_Y- ε αCVaR_ε F_Y )>1-δ. (b) If α+ϵ′>1α+ε >1, then (82) P(CVaRα(X) P (CVaR_α(X) ≥1α(F^Y[Y]−ϵ′CVaRϵ′F^Y+(α+ϵ′−1)amin))>1−δ. ≥ 1α (E_ F_Y[Y]-ε CVaR_ε F_Y+(α+ε -1)a_min ) )>1-δ. Proof. We begin by establishing that ϵ′ε bounds the distributional discrepancy between F^Y F_Y and FXF_X, under the assumption that supx(F^Y(x)−FY(x))≤η _x ( F_Y(x)-F_Y(x) )≤η. Let x∈ℝx , (83) F^Y(x)−FX(x)=F^Y(x)−FY(x)+FY(x)−FX(x) F_Y(x)-F_X(x)= F_Y(x)-F_Y(x)+F_Y(x)-F_X(x) ≤|F^Y(x)−FY(x)|+|FY(x)−FX(x)|≤η+ϵ=ϵ′. ≤| F_Y(x)-F_Y(x)|+|F_Y(x)-F_X(x)|≤η+ε=ε . Assume that α>ϵ′α>ε . Note that, conditional on the event supz∈ℝ(F^Y(z)−FX(z))≤ϵ′ _z ( F_Y(z)-F_X(z) )≤ε , the upper bound in Theorem 5.1 holds deterministically. Consequently, the probability that (84) CVaRα⁡(X)≤ϵ′αmax⁡(bX,bY)+(1−ϵ′α)CVaRα−ϵ′F^YCVaR_α(X)≤ ε α (b_X,b_Y)+(1- ε α)CVaR_α-ε F_Y holds is equal to one. From the law of total probability, (85) P(CVaRα⁡(X)≤ϵ′αmax⁡(bX,bY)+(1−ϵ′α)CVaRα−ϵ′F^Y) P (CVaR_α(X)≤ ε α (b_X,b_Y)+(1- ε α)CVaR_α-ε F_Y ) =P(CVaRα⁡(X)≤ϵ′αmax⁡(bX,bY)+(1−ϵ′α)CVaRα−ϵ′F^Y|supz∈ℝ(F^Y(z)−FX(z))≤ϵ′)P(supz∈ℝ(F^Y(z)−FX(z))≤ϵ′) =P (CVaR_α(X)≤ ε α (b_X,b_Y)+(1- ε α)CVaR_α-ε F_Y | _z ( F_Y(z)-F_X(z) )≤ε )P( _z ( F_Y(z)-F_X(z) )≤ε ) +P(CVaRα⁡(X)≤ϵ′αmax⁡(bX,bY)+(1−ϵ′α)CVaRα−ϵ′F^Y|supz∈ℝ(F^Y(z)−FX(z))>ϵ′)P(supz∈ℝ(F^Y(z)−FX(z))>ϵ′) +P (CVaR_α(X)≤ ε α (b_X,b_Y)+(1- ε α)CVaR_α-ε F_Y | _z ( F_Y(z)-F_X(z) )>ε )P( _z ( F_Y(z)-F_X(z) )>ε ) =P(supz∈ℝ(F^Y(z)−FX(z))≤ϵ′) =P( _z ( F_Y(z)-F_X(z) )≤ε ) +P(CVaRα⁡(X)≤ϵ′αmax⁡(bX,bY)+(1−ϵ′α)CVaRα−ϵ′F^Y|supz∈ℝ(F^Y(z)−FX(z))>ϵ′)P(supz∈ℝ(F^Y(z)−FX(z))>ϵ′) +P (CVaR_α(X)≤ ε α (b_X,b_Y)+(1- ε α)CVaR_α-ε F_Y | _z ( F_Y(z)-F_X(z) )>ε )P( _z ( F_Y(z)-F_X(z) )>ε ) ≥P(supz∈ℝ(F^Y(z)−FX(z))≤ϵ′) ≥ P( _z ( F_Y(z)-F_X(z) )≤ε ) From DKW (Dvoretzky et al., 1956) inequality the following inequalities can be derived (Thomas and Learned-Miller, 2019) (86) Pr⁡(supx∈ℝ(F^(x)−F(x))≤ln⁡(1/δ)2n)≥1−δ,Pr⁡(supx∈ℝ(F^(x)−F(x))≥ln⁡(1/δ)2n)≥1−δ. ( _x ( F(x)-F(x) )≤ (1/δ)2n )≥ 1-δ, ( _x ( F(x)-F(x) )≥ (1/δ)2n )≥ 1-δ. (87) P(supz∈ℝ(F^Y(z)−FX(z))≤ϵ′) P( _z ( F_Y(z)-F_X(z) )≤ε ) ≥P(supz∈ℝ(F^Y(z)−FY(z))+supz∈ℝ(FY(z)−FX(z))≤ϵ′) ≥ P( _z ( F_Y(z)-F_Y(z) )+ _z (F_Y(z)-F_X(z) )≤ε ) ≥P(supz∈ℝ(F^Y(z)−FY(z))+ϵ≤ϵ+η) ≥ P( _z ( F_Y(z)-F_Y(z) )+ε≤ε+η) =P(supz∈ℝ(F^Y(z)−FY(z))≤η)>1−δ. =P( _z ( F_Y(z)-F_Y(z) )≤η)>1-δ. The first inequality follows from the triangle inequality; the second holds since ϵε bounds the distributional discrepancy between X and Y; and the third follows from (86). As with the preceding equations, all bounds in Theorem 5.1 hold deterministically for a given distributional discrepancy, where the discrepancy between F^Y F_Y and FXF_X is ϵ′ε . Consequently, the remaining probabilistic guarantees hold with probability at least 1−δ1-δ. ∎ Appendix B Comparison with the Concentration Bounds of Thomas et al. (Thomas and Learned-Miller, 2019) Figure 16. Comparison of concentration inequalities for CVaRα⁡(X)CVaR_α(X) established by Theorem 5.5 (this work) and by (Thomas and Learned-Miller, 2019), evaluated on Beta⁡(2,2)Beta(2,2), Beta⁡(0.5,0.5)Beta(0.5,0.5), Beta⁡(2,5)Beta(2,5), Beta⁡(5,2)Beta(5,2), Beta⁡(10,2)Beta(10,2), Beta⁡(2,10)Beta(2,10), and Laplace⁡(0,1)Laplace(0,1) distributions. The two sets of bounds coincide for all tested distributions. See Figure 16. Appendix C Static CVaR Simplification Proofs Theorem C.1. (88) supl∈ℝ|P(Rk:T≤l|bk,ak,π)−Ps(Rk:T≤l|bk,ak,π)|≤∑t=kT−1s[Δs(bt,at)|bk,ak], _l |P(R_k:T≤ l|b_k,a_k,π)\!-\!P_s(R_k:T≤ l|b_k,a_k,π)|\!≤\!\!\! _t=k^T-1E^s[ ^s(b_t,a_t)|b_k,a_k], where Δs ^s is the TV distance that is defined by (89) Δs(bt−1,at−1)≜∫bt∈B|P(bt|bt−1,at−1)−Ps(bt|bt−1,at−1)|dbt. ^s(b_t-1,a_t-1) _b_t∈ B|P(b_t|b_t-1,a_t-1)-P_s(b_t|b_t-1,a_t-1)|db_t. Proof. By expanding the belief path from time k+1k+1 to time T we get (90) P(∑t=kTc(bt,at)≤l|bk,π) P( _t=k^Tc(b_t,a_t)≤ l|b_k,π) =∫bk+1:T∈BT−kP(Rk:T≤l|bk:T,π)∏i=k+1TP(bi|bi−1,π,ai)dbk+1:T = _b_k+1:T∈ B^T-kP(R_k:T≤ l|b_k:T,π) _i=k+1^TP(b_i|b_i-1,π,a_i)db_k+1:T =∫bk+1:T∈BT−k1Rk:T≤l∏i=k+1TP(bi|bi−1,π,ai)dbk+1:T, = _b_k+1:T∈ B^T-k1_R_k:T≤ l _i=k+1^TP(b_i|b_i-1,π,a_i)db_k+1:T, where the second equality holds because Rk:TR_k:T is constant given π and bk:Tb_k:T. Hence, the subtraction between the simplified and original return CDFs can be exhibited using the difference between the multiplication of the belief transition models. (91) P(Rk:T≤l|bk,π)−Ps(Rk:T≤l|bk,π)=∫bk+1:T∈BT−k1Rk:T≤l[∏i=k+1TP(bi|bi−1,π,ai)−∏i=k+1TPs(bi|bi−1,π,ai)]bk+1:T P(R_k:T≤ l|b_k,π)-P_s(R_k:T≤ l|b_k,π)= _b_k+1:T∈ B^T-k1_R_k:T≤ l[ _i=k+1^TP(b_i|b_i-1,π,a_i)- _i=k+1^TP_s(b_i|b_i-1,π,a_i)]db_k+1:T By applying the triangle inequality we get the following bound (92) |P(Rk:T≤l|bk,π)−Ps(Rk:T≤l|bk,π)|≤∫bk+1:T∈BT−k1Rk:T≤l|∏i=k+1TP(bi|bi−1,π,ai)−∏i=k+1TPs(bi|bi−1,π,ai)|dbk+1:T |P(R_k:T≤ l|b_k,π)-P_s(R_k:T≤ l|b_k,π)|≤ _b_k+1:T∈ B^T-k1_R_k:T≤ l| _i=k+1^TP(b_i|b_i-1,π,a_i)- _i=k+1^TP_s(b_i|b_i-1,π,a_i)|db_k+1:T ≤∫bk+1:T∈BT−k|∏i=k+1TP(bi|bi−1,π,ai)−∏i=k+1TPs(bi|bi−1,π,ai)|dbk+1:T=g(T), ≤ _b_k+1:T∈ B^T-k| _i=k+1^TP(b_i|b_i-1,π,a_i)- _i=k+1^TP_s(b_i|b_i-1,π,a_i)|db_k+1:T=g(T), where (93) g(t) g(t) ≜∫bk+1:t∈Bt−k+1|∏i=k+1tP(bi|bi−1,π,ai)−∏i=k+1tPs(bi|bi−1,π,ai)|dbk+1:t. _b_k+1:t∈ B^t-k+1| _i=k+1^tP(b_i|b_i-1,π,a_i)- _i=k+1^tP_s(b_i|b_i-1,π,a_i)|db_k+1:t. We will prove that (94) g(t+1)≤g(t)+s[Δs(bt,at)|bk,ak]=ϵtg(t+1)≤ g(t)+E^s[ ^s(b_t,a_t)|b_k,a_k]= _t for t∈k+1,…,Tt∈\k+1,…,T\, where ϵk=0 _k=0, and therefore (95) |P(Rk:t≤l|bk,π)−Ps(Rk:t≤l|bk,π)|≤ϵt.|P(R_k:t≤ l|b_k,π)-P_s(R_k:t≤ l|b_k,π)|≤ _t. For the case where t=kt=k, btb_t is constant, and therefore the c(bt,at)c(b_t,a_t) does not depend on the belief transition model. Hence, Ps(c(bt,at)≤l|bt,at)=P(c(bt,at)≤l|bt,at)P_s(c(b_t,a_t)≤ l|b_t,a_t)=P(c(b_t,a_t)≤ l|b_t,a_t). Therefore we get (96) P(c(bk,ak)≤l|bk,ak)−Ps(c(bk,ak)≤l|bk,ak)|=0=ϵk.P(c(b_k,a_k)≤ l|b_k,a_k)-P_s(c(b_k,a_k)≤ l|b_k,a_k)|=0= _k. The rest of the proof will use induction over t∈k+1,…,Tt∈\k+1,…,T\. Base case, t=k+1t=k+1: (97) g(k+1)=∫bk+1∈B|∏i=k+1k+1P(bi|bi−1,π,ai)−∏i=k+1k+1Ps(bi|bi−1,π,ai)|dbk+1:k+1 g(k+1)= _b_k+1∈ B| _i=k+1^k+1P(b_i|b_i-1,π,a_i)- _i=k+1^k+1P_s(b_i|b_i-1,π,a_i)|db_k+1:k+1 =∫bk+1∈B|P(bk+1|bk,π,ak)−Ps(bk+1|bk,π,ak)|dbk+1=Δs(bk,ak)=s[Δs(bk,ak)|bk,ak] = _b_k+1∈ B|P(b_k+1|b_k,π,a_k)-P_s(b_k+1|b_k,π,a_k)|db_k+1= ^s(b_k,a_k)=E^s[ ^s(b_k,a_k)|b_k,a_k] =ϵk+1 = _k+1 Induction step: Assume that the claim is true for t∈k+1,…,T−1t∈\k+1,…,T-1\ and prove for t+1t+1. Our proof’s strategy is to express g(t+1)g(t+1) recursively, using g(t)g(t), and separate the bound at time t+1t+1 into 2 components - one at time t and one at time t+1t+1. We then bound the term at time t+1t+1, and use the induction step to bound the recursive part of g at time t. For all xi,yi∈ℝx_i,y_i , (98) ∏i=k+1t+1xi−∏i=k+1t+1yi=∏i=k+1t+1xi−xt+1∏i=k+1tyi+xt+1∏i=k+1tyi−∏i=k+1t+1yi=xt+1(∏i=k+1txi−∏i=k+1tyi)+(xt+1−yt+1)∏i=k+1tyi. _i=k+1^t+1x_i- _i=k+1^t+1y_i= _i=k+1^t+1x_i-x_t+1 _i=k+1^ty_i+x_t+1 _i=k+1^ty_i- _i=k+1^t+1y_i=x_t+1( _i=k+1^tx_i- _i=k+1^ty_i)+(x_t+1-y_t+1) _i=k+1^ty_i. By denoting xi=P(bi|bi−1,ai−1)x_i=P(b_i|b_i-1,a_i-1) and yi=Ps(bi|bi−1,ai−1)y_i=P_s(b_i|b_i-1,a_i-1) we get (99) ∏i=k+1t+1P(bi|bi−1,π,ai)−∏i=k+1t+1Ps(bi|bi−1,π,ai) _i=k+1^t+1P(b_i|b_i-1,π,a_i)- _i=k+1^t+1P_s(b_i|b_i-1,π,a_i) =[P(bt+1|bt,at)−Ps(bt+1|bt,at)]∏i=k+1tPs(bi|bi−1,ai−1)+P(bt+1|bt,at)[∏i=k+1tP(bi|bi−1,π,ai)−∏i=k+1tPs(bi|bi−1,π,ai)]. =[P(b_t+1|b_t,a_t)-P_s(b_t+1|b_t,a_t)] _i=k+1^tP_s(b_i|b_i-1,a_i-1)+P(b_t+1|b_t,a_t)[ _i=k+1^tP(b_i|b_i-1,π,a_i)- _i=k+1^tP_s(b_i|b_i-1,π,a_i)]. By combining the equation above with the triangle inequality, we get (100) g(t+1)≤A1+A2g(t+1)≤ A_1+A_2 for (101) A1 A_1 ≜∫bk+1:t+1∈Bt−k|P(bt+1|bt,at)−Ps(bt+1|bt,at)|∏i=k+1tPs(bi|bi−1,ai−1)bk+1:t, _b_k+1:t+1∈ B^t-k|P(b_t+1|b_t,a_t)-P_s(b_t+1|b_t,a_t)| _i=k+1^tP_s(b_i|b_i-1,a_i-1)b_k+1:t, (102) A2 A_2 ≜∫bk+1:t+1∈Bt−kP(bt+1|bt,at)|∏i=k+1tP(bi|bi−1,π,ai)−∏i=k+1tPs(bi|bi−1,π,ai)|dbk+1:t _b_k+1:t+1∈ B^t-kP(b_t+1|b_t,a_t)| _i=k+1^tP(b_i|b_i-1,π,a_i)- _i=k+1^tP_s(b_i|b_i-1,π,a_i)|db_k+1:t A1A_1 is the expectation over the TV-distance of the belief at time t. (103) A1=s[Δs(bt,at)|bk,ak]. A_1=E^s[ ^s(b_t,a_t)|b_k,a_k]. As we see below, A2A_2 does not depend on the belief integration at time t+1t+1, and therefore equals to g(t)g(t). From the induction assumption, we get that g(t)≤ϵtg(t)≤ _t. (104) A2=∫bk+1:t∈Bt−kP(bt+1|bt,at)|∏i=k+1tP(bi|bi−1,π,ai)−∏i=k+1tPs(bi|bi−1,π,ai)|dbk:t+1 A_2= _b_k+1:t∈ B^t-kP(b_t+1|b_t,a_t)| _i=k+1^tP(b_i|b_i-1,π,a_i)- _i=k+1^tP_s(b_i|b_i-1,π,a_i)|db_k:t+1 =∫bk+1:t∈Bt−k|∏i=k+1tP(bi|bi−1,π,ai)−∏i=k+1tPs(bi|bi−1,π,ai)|∫bt+1P(bt+1|bt,at)bt+1⏟=1dbk+1:t = _b_k+1:t∈ B^t-k| _i=k+1^tP(b_i|b_i-1,π,a_i)- _i=k+1^tP_s(b_i|b_i-1,π,a_i)| _b_t+1P(b_t+1|b_t,a_t)db_t+1_=1db_k+1:t =g(t)≤ϵt =g(t)≤ _t By combining the computations of A1A_1 and A2A_2, (105) g(t+1) g(t+1) ≤A1+A2=g(t)+s[Δs(bt,at)|bk,ak]. ≤ A_1+A_2=g(t)+E^s[ ^s(b_t,a_t)|b_k,a_k]. The last equation completes the induction proof. Utilizing the recursive relation of ϵt _t, we get the bound we want to prove. (106) |P(Rk:T≤l|bk,π)−Ps(Rk:T≤l|bk,π)|≤g(T)≤g(T−1)+s[Δs(bT−1,aT−1)|bk,ak]≤∑t=kT−1s[Δs(bt,at)|bk,ak]. |P(R_k:T≤ l|b_k,π)-P_s(R_k:T≤ l|b_k,π)|≤ g(T)≤ g(T-1)+E^s[ ^s(b_T-1,a_T-1)|b_k,a_k]≤ _t=k^T-1E^s[ ^s(b_t,a_t)|b_k,a_k]. ∎ Theorem C.2. In the case where the simplified and original observation models are denoted by qzq_z and pzp_z respectively, it holds that (107) supl∈ℝ|P(Rk:T≤l|bk,π)−Ps(Rk:T≤l|bk,π)|≤∑t=kT−1s[Δs(xt+1)|bk,ak], _l |P(R_k:T≤ l|b_k,π)\!-\!P_s(R_k:T≤ l|b_k,π)|\!≤\!\!\! _t=k^T-1E^s[ ^s(x_t+1)|b_k,a_k], where Δs ^s is the TV distance that is defined by (108) Δs(xt)≜∫zt∈Z|p(zt|xt)−q(zt|xt)|dzt. ^s(x_t) _z_t∈ Z|p(z_t|x_t)-q(z_t|x_t)|dz_t. Proof. We show that for each t∈k,…,T−1t∈\k,…,T-1\, (109) s[Δs(bt,at)|bk,ak]≤s[Δs(xt+1)|bk,ak],E^s[ ^s(b_t,a_t)|b_k,a_k] ^s[ ^s(x_t+1)|b_k,a_k], and therefore (110) supl∈ℝ|P(Rk:T≤l|bk,π)−Ps(Rk:T≤l|bk,π)|≤∑t=kT−1s[Δs(bt,at)|bk,ak]≤∑t=kT−1s[Δs(xt+1)|bk,ak]. _l |P(R_k:T≤ l|b_k,π)\!-\!P_s(R_k:T≤ l|b_k,π)|\!≤\!\!\! _t=k^T-1E^s[ ^s(b_t,a_t)|b_k,a_k]≤ _t=k^T-1E^s[ ^s(x_t+1)|b_k,a_k]. We start by expressing the belief transition model using the observation and state-transition models. Here we assume that btb_t is known. That is, bt=(xi,wi)i=1nb_t=\(x_i,w_i)\_i=1^n, where xix_i and wiw_i are constants. (111) P(bt+1|bt,at)=∫xt∈X,xt+1∈X,zt+1∈ZP(bt+1|bt,at,zt+1,xt,xt+1)P(zt+1,xt,xt+1|bt,at)zt+1xt+1xt P(b_t+1|b_t,a_t)= _x_t∈ X,x_t+1∈ X,z_t+1∈ ZP(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1)P(z_t+1,x_t,x_t+1|b_t,a_t)dz_t+1dx_t+1dx_t =∫xt∈X,xt+1∈X,zt+1∈ZP(bt+1|bt,at,zt+1,xt,xt+1)p(zt+1|xt+1)×P(xt+1|xt,at)b(xt)zt+1xt+1xt. = _x_t∈ X,x_t+1∈ X,z_t+1∈ ZP(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1)p(z_t+1|x_t+1)× P(x_t+1|x_t,a_t)b(x_t)dz_t+1dx_t+1dx_t. Similarly, (112) Ps(bt+1|bt,at)=∫xt∈X,xt+1∈X,zt+1∈ZPs(bt+1|bt,at,zt+1,xt,xt+1)q(zt+1|xt+1)P(xt+1|xt,at)b(xt)zt+1xt+1xt. P_s(b_t+1|b_t,a_t)= _x_t∈ X,x_t+1∈ X,z_t+1∈ ZP_s(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1)q(z_t+1|x_t+1)P(x_t+1|x_t,a_t)b(x_t)dz_t+1dx_t+1dx_t. Note that P(bt+1|bt,at,zt+1,xt,xt+1)=Ps(bt+1|bt,at,zt+1,xt,xt+1)P(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1)=P_s(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1), as both terms do not depend on the observation model. By subtracting the simplified and original belief transition models, we can separate the simplified and original observation models. (113) |P(bt+1|bt,at)−Ps(bt+1|bt,at)| |P(b_t+1|b_t,a_t)-P_s(b_t+1|b_t,a_t)| =|∫xt∈X,xt+1∈X,zt+1∈ZPs(bt+1|bt,at,zt+1,xt,xt+1)P(xt+1|xt,at)b(xt)(p(zt+1|xt+1)−q(zt+1|xt+1))dzt+1dxt+1dxt| =| _x_t∈ X,x_t+1∈ X,z_t+1∈ ZP_s(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1)P(x_t+1|x_t,a_t)b(x_t)(p(z_t+1|x_t+1)-q(z_t+1|x_t+1))dz_t+1dx_t+1dx_t| ≤∫xt∈X,xt+1∈X,zt+1∈ZPs(bt+1|bt,at,zt+1,xt,xt+1)P(xt+1|xt,at)b(xt)|p(zt+1|xt+1)−q(zt+1|xt+1)|dzt+1dxt+1dxt. ≤ _x_t∈ X,x_t+1∈ X,z_t+1∈ ZP_s(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1)P(x_t+1|x_t,a_t)b(x_t)|p(z_t+1|x_t+1)-q(z_t+1|x_t+1)|dz_t+1dx_t+1dx_t. where the inequality holds from the triangle inequality. It holds that (114) Δs(bt,at)=∫bt+1∈B|P(bt+1|bt,at)−Ps(bt+1|bt,at)|dbt+1 ^s(b_t,a_t)= _b_t+1∈ B|P(b_t+1|b_t,a_t)-P_s(b_t+1|b_t,a_t)|db_t+1 ≤∫bt+1∈B∫xt∈X,xt+1∈X,zt+1∈ZPs(bt+1|bt,at,zt+1,xt,xt+1)P(xt+1|xt,at)b(xt)|p(zt+1|xt+1)−q(zt+1|xt+1)|dzt+1dxt+1dxtdbt+1 ≤ _b_t+1∈ B _x_t∈ X,x_t+1∈ X,z_t+1∈ ZP_s(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1)P(x_t+1|x_t,a_t)b(x_t)|p(z_t+1|x_t+1)-q(z_t+1|x_t+1)|dz_t+1dx_t+1dx_tdb_t+1 =∫xt∈X,xt+1∈XP(xt+1|xt,at)b(xt)∫zt+1∈Z|p(zt+1|xt+1)−q(zt+1|xt+1)|∫bt+1∈BPs(bt+1|bt,at,zt+1,xt,xt+1)bt+1⏟=1dzt+1dxt+1dxt = _x_t∈ X,x_t+1∈ XP(x_t+1|x_t,a_t)b(x_t) _z_t+1∈ Z|p(z_t+1|x_t+1)-q(z_t+1|x_t+1)| _b_t+1∈ BP_s(b_t+1|b_t,a_t,z_t+1,x_t,x_t+1)db_t+1_=1dz_t+1dx_t+1dx_t =∫bt+1∈B∫xt∈X,xt+1∈XP(xt+1|xt,at)b(xt)Δs(xt+1)xt+1xt = _b_t+1∈ B _x_t∈ X,x_t+1∈ XP(x_t+1|x_t,a_t)b(x_t) ^s(x_t+1)dx_t+1dx_t =s[Δs(xt+1)|bt,at] =E^s[ ^s(x_t+1)|b_t,a_t] where the first inequality holds from (113). From the last equation and expectation monotonicity, we get that s[Δ(bt,at)]≤s[Δs(xt+1)|bt,at]E^s[ (b_t,a_t)] ^s[ ^s(x_t+1)|b_t,a_t], and therefore the claim holds for each t. Summing over t and applying the tower property yields the result. (115) s[Δs(bt,at)|bk,ak] ^s[ ^s(b_t,a_t)|b_k,a_k] =s[s[Δs(bt,at)|bt,at]|bk,ak]≤s[s[Δs(xt+1)|bt,at]|bk,ak]=s[Δs(xt+1)|bk,ak]. =E^s[E^s[ ^s(b_t,a_t)|b_t,a_t]|b_k,a_k] ^s[E^s[ ^s(x_t+1)|b_t,a_t]|b_k,a_k]=E^s[ ^s(x_t+1)|b_k,a_k]. ∎ Theorem C.3. Let δdmin∈[0,1],δdmax∈[0,1] _d_min∈[0,1], _d_max∈[0,1] and denote (116) ϵ≜ϵ(bk,ak)≜min⁡(∑i=kT−1s[Δs(bi,ai)|bk,ak,π],1),ε ε(b_k,a_k) ( _i=k^T-1E^s[ ^s(b_i,a_i)|b_k,a_k,π],1), (1) Upper Bound: assume that P(Rk:T≤dmax)>1−δdmaxP(R_k:T≤ d_max)>1- _d_max and Ps(Rk:T≤dmax)>1−δdmaxP_s(R_k:T≤ d_max)>1- _d_max, then (a) If ϵ<αε<α, then Us≜(1−ϵα)QMsπ(bk,ak,α−ϵ)+ϵαdmaxU_s (1- εα)Q^π_M_s(b_k,a_k,α-ε)+ εαd_max (b) If ϵ≥αε≥α then Us≜dmaxU_s d_max (2) Lower Bound: assume that P(Rk:T≥dmin)>1−δdminP(R_k:T≥ d_min)>1- _d_min and Ps(Rk:T≥dmin)>1−δdminP_s(R_k:T≥ d_min)>1- _d_min, then (a) If ϵ+α<1ε+α<1 then Ls≜(1+ϵα)QMsπ(bk,ak,α+ϵ)−ϵαQMsπ(bk,ak,ϵ)L_s (1+ εα)Q^π_M_s(b_k,a_k,α+ε)- εαQ^π_M_s(b_k,a_k,ε) (b) If ϵ+α≥1ε+α≥ 1 then Ls≜1α[−(α+ϵ−1)dmin+QMsπ(bk,ak)−ϵQMsπ(bk,ak,ϵ)]L_s 1α[-(α+ε-1)d_min+Q^π_M_s(b_k,a_k)-ε Q^π_M_s(b_k,a_k,ε)] Then P(Ls≤QMπ(bk,ak,α))>1−δdminP(L_s≤ Q_M^π(b_k,a_k,α))>1- _d_min and P(QMπ(bk,ak,α)≤Us)>1−δdmaxP(Q_M^π(b_k,a_k,α)≤ U_s)>1- _d_max. Proof. From the law of total probability, (117) P(QMπ(bk,ak,α)≤Us) P(Q_M^π(b_k,a_k,α)≤ U_s) =P(QMπ(bk,ak,α)≤Us|Rk:T≤dmax)P(Rk:T≤dmax) =P(Q_M^π(b_k,a_k,α)≤ U_s|R_k:T≤ d_max)P(R_k:T≤ d_max) +P(QMπ(bk,ak,α)≤Us|Rk:T>dmax)P(Rk:T>dmax) +P(Q_M^π(b_k,a_k,α)≤ U_s|R_k:T>d_max)P(R_k:T>d_max) ≥P(QMπ(bk,ak,α)≤Us|Rk:T≤dmax)P(Rk:T≤dmax) ≥ P(Q_M^π(b_k,a_k,α)≤ U_s|R_k:T≤ d_max)P(R_k:T≤ d_max) >P(QMπ(bk,ak,α)≤Us|Rk:T≤dmax)(1−δdmax). >P(Q_M^π(b_k,a_k,α)≤ U_s|R_k:T≤ d_max)(1- _d_max). Similarly, (118) P(QMπ(bk,ak,α)≥Ls)>P(QMπ(bk,ak,α)≥Ls|Rk:T≥dmin)(1−δdmin).P(Q_M^π(b_k,a_k,α)≥ L_s)>P(Q_M^π(b_k,a_k,α)≥ L_s|R_k:T≥ d_min)(1- _d_min). From Theorem C.1, for all l∈ℝl (119) |P(Rk:T≤l|bk,π)−Ps(Rk:T≤l|bk,π)|≤∑i=k+1T−1bk+1:i[Δs(bi,ai)|bk,π]=ϵ, |P(R_k:T≤ l|b_k,π)-P_s(R_k:T≤ l|b_k,π)|≤ _i=k+1^T-1E_b_k+1:i[ ^s(b_i,a_i)|b_k,π]=ε, The action-value function is defined as the CVaR of the return. Let X and Y be random variables distributed according to the original and simplified models P and PsP_s, respectively. Theorem 5.1 establishes bounds on CVaRα⁡(X)CVaR_α(X) in terms of CVaRCVaR of Y, under a known discrepancy between the cumulative distribution functions of X and Y. In our setting, this distributional discrepancy is bounded by ϵε, and thus the result applies directly. ∎ Corollary C.4. The bound from Theorem 6.2 holds for ϵ(bk,ak)=∑t=kT−1s[Δs(xt+1)|bk,ak]ε(b_k,a_k)= _t=k^T-1E^s[ ^s(x_t+1)|b_k,a_k]. Proof. Theorem 6.2 establishes bounds on the value and action-value functions under a quantified distributional discrepancy ϵε between the original and simplified return distributions. As long as this discrepancy between their CDFs remains bounded by ϵε, the result remains valid. Consequently, by bounding the belief-based discrepancy ϵε in Theorem 6.2 via the state-based discrepancy bound established in Theorem C.2, we recover the same form of the bound for the newly defined ϵε. ∎ Theorem C.5. Let η>0,δ∈(0,1)η>0,δ∈(0,1). If Δ is unbiased, then (120) P(|ϵ^t(b¯t,a)−ϵt(b¯t,a)|≥η)≤2exp⁡(−2η2NbD2(T−k)2(Rmax−Rmin)2) P(| ε_t( b_t,a)- _t( b_t,a)|≥η)≤ 2 (- 2η^2N_bD^2(T-k)^2(R_ -R_ )^2 ) for D=maxi∈k+1,…,T−1⁡DiD= _i∈\k+1,…,T-1\D_i where Di=supxi+1P(xi+1|xi,ai)/Q0(xi+1)D_i= _x_i+1P(x_i+1|x_i,a_i)/Q_0(x_i+1). Proof. We start by proving that m^(b¯t,a) m( b_t,a) is an unbiased estimator for m(b¯t,a)m( b_t,a). (121) [m^(b¯t,a)]=∑i=1Np[m^(xti,a)]w~ti=∑i=1Np[P(xnΔ|xti,a)Q0(xnΔ)Δ(xnΔ)]w~ti=∑i=1Npm(xti,a)w~ti [ m( b_t,a)]= _i=1^N_pE[ m(x_t^i,a)] w^i_t= _i=1^N_pE[ P(x_n |x_t^i,a)Q_0(x_n ) (x_n )] w^i_t= _i=1^N_pm(x_t^i,a) w^i_t =m(b¯t,a). =m( b_t,a). It follows that the estimator ϵ^(b¯t,a) ε( b_t,a) of the total distributional discrepancy is an unbiased estimator of ϵ(b¯t,a)ε( b_t,a). (122) [ϵ^(b¯t,a)] [ ε( b_t,a)] =∑τ=tT−1[^[m(b¯τ,πτ)|b¯t,a]|b¯t,a]=∑τ=tT−1[m^(b¯τ1,π(b¯τ1))|b¯t,a]=∑τ=tT−1[[m^(b¯τ1,π(b¯τ1))|b¯τ1]|b¯t,a] = _τ=t^T-1E[ E[m( b_τ, _τ)| b_t,a]| b_t,a]= _τ=t^T-1E[ m( b_τ^1,π( b_τ^1))| b_t,a]= _τ=t^T-1E[E[ m( b_τ^1,π( b_τ^1))| b_τ^1]| b_t,a] =∑τ=tT−1[m(b¯τ1,π(b¯τ1))|b¯t,a]=ϵ(b¯t,a) = _τ=t^T-1E[m( b_τ^1,π( b_τ^1))| b_t,a]=ε( b_t,a) Define (123) Xi≜1Nb∑τ=tT−1m^(b¯τi,π(b¯τi)),X_i 1N_b _τ=t^T-1 m( b_τ^i,π( b_τ^i)), and note that (124) ∑i=1NbXi=ϵ^t(b¯t,a). _i=1^N_bX_i= ε_t( b_t,a). Since the total variation distance is bounded by 2, each XiX_i satisfies the bound (125) 2D(T−t)RminNb≤Xi≤2D(T−t)RmaxNb. 2D(T-t)R_ N_b≤ X_i≤ 2D(T-t)R_ N_b. Moreover, the XiX_i are independent and identically distributed, and thus Hoeffding’s inequality applies. (126) P(|ϵ^t(b¯t,a)−ϵt(b¯t,a)|≥η)=P(|∑i=1NbXi−ϵt(b¯t,a)|≥η) P(| ε_t( b_t,a)- _t( b_t,a)|≥η)=P(| _i=1^N_bX_i- _t( b_t,a)|≥η) ≤2exp⁡(−2η2D2(T−k)2(Rmax−Rmin)2/Nb2×Nb) ≤ 2 (- 2η^2D^2(T-k)^2(R_ -R_ )^2/N_b^2× N_b) ≤2exp⁡(−2η2NbD2(T−k)2(Rmax−Rmin)2). ≤ 2 (- 2η^2N_bD^2(T-k)^2(R_ -R_ )^2). ∎ Theorem C.6. For the estimators d^maxπ(bk)=maxi∈1,…,Nb⁡Ri d_ ^π(b_k)= _i∈\1,…,N_b\R^i and d^minπ(bk)=mini∈1,…,Nb⁡Ri d_ ^π(b_k)= _i∈\1,…,N_b\R^i, where R1,…,RNb∼Ps(⋅|bk,π)R^1,…,R^N_b P_s(·|b_k,π), and for ϵε as defined in (30), the following bounds hold. (127) Ps(Rk:T≥d^minπ(bk))≥NbNb+1,Ps(Rk:T≤d^maxπ(bk))≥NbNb+1P_s(R_k:T≥ d_min^π(b_k))≥ N_bN_b+1, P_s(R_k:T≤ d_max^π(b_k))≥ N_bN_b+1 (128) P(Rk:T≥d^minπ(bk)|bk,π)≥NbNb+1−ϵ,P(Rk:T≤d^maxπ(bk)|bk,π)≥NbNb+1−ϵ.P\! (R_k:T≥ d_min^π(b_k) |b_k,π )≥ N_bN_b+1-ε, P\! (R_k:T≤ d_max^π(b_k) |b_k,π )≥ N_bN_b+1-ε. Proof. Note that Rii=1Nb∼Ps(⋅|bk,π)\R^i\_i=1^N_b P_s(·|b_k,π) are sampled from the simplified distribution. Observe that Rk:T,R1,…,RNbR_k:T,R^1,…,R^N_b constitute an i.i.d. sample of size Nb+1N_b+1 from the simplified distribution. For each j∈0,1,…,Nbj∈\0,1,…,N_b\, define the event Aj=Xj is strictly the largest among all Nb+1 samplesA_j=\X_j is strictly the largest among all N_b+1 samples\, where X0=Rk:TX_0=R_k:T and Xi=RiX_i=R^i for i≥1i≥ 1. These events are mutually exclusive, and by the i.i.d. assumption Ps(Aj)P_s(A_j) is the same for all j. Since ∑j=0NbPs(Aj)≤1 _j=0^N_bP_s(A_j)≤ 1, it follows that (129) Ps(Rk:T>maxi∈1,…,Nb⁡Ri|bk,π)=Ps(A0)≤1Nb+1.P_s\! (R_k:T> _i∈\1,…,N_b\R^i |b_k,π )=P_s(A_0)≤ 1N_b+1. Similarly, Ps(Rk:T<mini∈1,…,Nb⁡Ri|bk,π)≤1Nb+1P_s(R_k:T< _i∈\1,…,N_b\R^i|b_k,π)≤ 1N_b+1. Therefore, (130) Ps(Rk:T≤maxi∈1,…,Nb⁡Ri|bk,π)≥NbNb+1,Ps(Rk:T≥mini∈1,…,Nb⁡Ri|bk,π)≥NbNb+1.P_s(R_k:T≤ _i∈\1,…,N_b\R^i|b_k,π)≥ N_bN_b+1, P_s(R_k:T≥ _i∈\1,…,N_b\R^i|b_k,π)≥ N_bN_b+1. When bounding P(Rk:T≤maxi∈1,…,Nb⁡Ri)P (R_k:T≤ _i∈1,…,N_bR^i ), observe that Rk:TR_k:T is drawn from the original distribution P, whereas the samples Rii=1Nb\R^i\_i=1^N_b are drawn from the simplified distribution PsP_s. Consequently, the symmetry argument used in the previous bound does not apply. To address this mismatch, we employ the bound from Theorem 6.1 to bound the CDF of the return computed with the original model, using the CDF computed using the simplified belief-transition model. (131) P(Rk:T≤maxi∈1,…,Nb⁡Ri|bk,π)=∫R1,…,RNbP(Rk:T≤maxi∈1,…,Nb⁡Ri|R1,…,RNb,bk,π)Ps(R1,…,RNb|bk,π)R1…RNb P\! (R_k:T≤ _i∈\1,…,N_b\R^i |b_k,π )= _R^1,…,R^N_bP\! (R_k:T≤ _i∈\1,…,N_b\R^i |R^1,…,R^N_b,b_k,π )P_s(R^1,…,R^N_b|b_k,π)dR^1… dR^N_b ≥∫R1,…,RNb(Ps(Rk:T≤maxi∈1,…,Nb⁡Ri|R1,…,RNb,bk,π)−ϵ)Ps(R1,…,RNb|bk,π)R1,…,dRNb ≥ _R^1,…,R^N_b (P_s\! (R_k:T≤ _i∈\1,…,N_b\R^i |R^1,…,R^N_b,b_k,π )-ε )P_s(R^1,…,R^N_b|b_k,π)dR^1,…,dR^N_b =s[Ps(Rk:T≤maxi∈1,…,Nb⁡Ri|R1,…,RNb)−ϵ|bk,π] =E_s [P_s\! (R_k:T≤ _i∈\1,…,N_b\R^i |R^1,…,R^N_b )-ε |b_k,π ] =Ps(Rk:T≤maxi∈1,…,Nb⁡Ri)−ϵ =P_s\! (R_k:T≤ _i∈\1,…,N_b\R^i )-ε ≥NbNb+1−ϵ. ≥ N_bN_b+1-ε. The first inequality follows directly from Theorem 6.1, and the last inequality holds from the symmetry argument used above. Similarly, (132) P(Rk:T≤mini∈1,…,Nb⁡Ri|bk,π)≥NbNb+1−ϵ.P\! (R_k:T≤ _i∈\1,…,N_b\R^i |b_k,π )≥ N_bN_b+1-ε. ∎ Theorem C.7. Let δ,δdmin,δdmax∈[0,1]δ, _d_ , _d_ ∈[0,1], and let bkb_k denote the initial belief. Consider samples R1,…,RNb∼Ps(⋅∣bk,π)R^1,…,R^N_b P_s(· b_k,π) generated using the simplified belief-transition model. Define (133) ϵ≜ϵ(bk,ak)≜min⁡(∑i=kT−1s[Δs(bi,ai)|bk,ak,π],1),ε ε(b_k,a_k) ( _i=k^T-1E^s[ ^s(b_i,a_i)|b_k,a_k,π],1), (134) η=ln⁡(1/δ)/(2Nb),ϵ′=ϵ+η.η= (1/δ)/(2N_b), ε =ε+η. (1) Upper Bound: assume that P(Rk:T≤dmax)>1−δdmaxP(R_k:T≤ d_max)>1- _d_max and Ps(Rk:T≤dmax)>1−δdmaxP_s(R_k:T≤ d_max)>1- _d_max, then (a) If ϵ′<αε <α, then Us≜(1−ϵ′α)Q^Msπ(bk,ak,α−ϵ′)+ϵ′αdmaxU_s (1- ε α) Q^π_M_s(b_k,a_k,α-ε )+ ε αd_max (b) If ϵ′≥αε ≥α then Us≜dmaxU_s d_max (2) Lower Bound: assume that P(Rk:T≥dmin)>1−δdminP(R_k:T≥ d_min)>1- _d_min and Ps(Rk:T≥dmin)>1−δdminP_s(R_k:T≥ d_min)>1- _d_min, then (a) If ϵ′+α<1ε +α<1 then Ls≜(1+ϵ′α)Q^Msπ(bk,ak,α+ϵ′)−ϵ′αQ^Msπ(bk,ak,ϵ′)L_s (1+ ε α) Q^π_M_s(b_k,a_k,α+ε )- ε α Q^π_M_s(b_k,a_k,ε ) (b) If ϵ′+α≥1ε +α≥ 1 then Ls≜1α[−(α+ϵ′−1)dmin+Q^Msπ(bk,ak)−ϵ′Q^Msπ(bk,ak,ϵ′)]L_s 1α[-(α+ε -1)d_min+ Q^π_M_s(b_k,a_k)-ε Q^π_M_s(b_k,a_k,ε )] Then P(Ls≤QMπ(bk,ak,α))>(1−δ)(1−δdmin)P(L_s≤ Q_M^π(b_k,a_k,α))>(1-δ)(1- _d_min) and P(QMπ(bk,ak,α)≤Us)>(1−δ)(1−δdmax)P(Q_M^π(b_k,a_k,α)≤ U_s)>(1-δ)(1- _d_max). Proof. From the law of total probability, (135) P(QMπ(bk,ak,α)≤Us) P(Q_M^π(b_k,a_k,α)≤ U_s) =P(QMπ(bk,ak,α)≤Us|Rk:T≤dmax)P(Rk:T≤dmax) =P(Q_M^π(b_k,a_k,α)≤ U_s|R_k:T≤ d_max)P(R_k:T≤ d_max) +P(QMπ(bk,ak,α)≤Us|Rk:T>dmax)P(Rk:T>dmax) +P(Q_M^π(b_k,a_k,α)≤ U_s|R_k:T>d_max)P(R_k:T>d_max) ≥P(QMπ(bk,ak,α)≤Us|Rk:T≤dmax)P(Rk:T≤dmax) ≥ P(Q_M^π(b_k,a_k,α)≤ U_s|R_k:T≤ d_max)P(R_k:T≤ d_max) >P(QMπ(bk,ak,α)≤Us|Rk:T≤dmax)(1−δdmax). >P(Q_M^π(b_k,a_k,α)≤ U_s|R_k:T≤ d_max)(1- _d_max). Similarly, (136) P(QMπ(bk,ak,α)≥Ls)>P(QMπ(bk,ak,α)≥Ls|Rk:T≥dmin)(1−δdmin).P(Q_M^π(b_k,a_k,α)≥ L_s)>P(Q_M^π(b_k,a_k,α)≥ L_s|R_k:T≥ d_min)(1- _d_min). From Theorem C.1, for all l∈ℝl (137) |P(Rk:T≤l|bk,π)−Ps(Rk:T≤l|bk,π)|≤∑i=k+1T−1bk+1:i[Δs(bi,ai)|bk,π]=ϵ, |P(R_k:T≤ l|b_k,π)-P_s(R_k:T≤ l|b_k,π)|≤ _i=k+1^T-1E_b_k+1:i[ ^s(b_i,a_i)|b_k,π]=ε, The action-value function is defined as the CVaR of the return. Let X and Y be random variables distributed according to the original and simplified models P and PsP_s, respectively. Theorem 5.7 establishes bounds on CVaRα⁡(X)CVaR_α(X) in terms of CVaRCVaR of a sample of Y, under a known discrepancy between the cumulative distribution functions of X and Y. In our setting, this distributional discrepancy is bounded by ϵε, and thus the result applies directly. ∎ Theorem C.8. (Bound Guarantees) Let δ∈(0,0.5)δ∈(0,0.5), and let bkb_k denote the initial belief. Consider samples R1,…,RNb∼Ps(⋅∣bk,π)R^1,…,R^N_b P_s(· b_k,π) generated using the simplified belief-transition model. Define (138) ϵ≜ϵ(bk,ak)≜min⁡(∑i=kT−1s[Δs(bi,ai)|bk,ak,π],1),ε ε(b_k,a_k) ( _i=k^T-1E^s[ ^s(b_i,a_i)|b_k,a_k,π],1), (139) η=ln⁡(1/δ)/(2Nb),ϵ′=ϵ+η,η= (1/δ)/(2N_b), ε =ε+η, (140) d^maxπ(bk)=maxi∈1,…,Nb⁡Ri,d^minπ(bk)=mini∈1,…,Nb⁡Ri. d_ ^π(b_k)= _i∈\1,…,N_b\R^i, d_ ^π(b_k)= _i∈\1,…,N_b\R^i. (1) Upper Bound: (a) If ϵ′<αε <α, then Us≜(1−ϵ′α)Q^Msπ(bk,ak,α−ϵ′)+ϵ′αd^maxπ(bk)U_s (1- ε α) Q^π_M_s(b_k,a_k,α-ε )+ ε α d_ ^π(b_k) (b) If ϵ′≥αε ≥α then Us≜d^maxπ(bk)U_s d_ ^π(b_k) (2) Lower Bound: (a) If ϵ′+α<1ε +α<1 then Ls≜(1+ϵ′α)Q^Msπ(bk,ak,α+ϵ′)−ϵ′αQ^Msπ(bk,ak,ϵ′)L_s (1+ ε α) Q^π_M_s(b_k,a_k,α+ε )- ε α Q^π_M_s(b_k,a_k,ε ) (b) If ϵ′+α≥1ε +α≥ 1 then Ls≜1α[−(α+ϵ′−1)d^minπ(bk)+Q^Msπ(bk,ak)−ϵ′Q^Msπ(bk,ak,ϵ′)]L_s 1α[-(α+ε -1) d_ ^π(b_k)+ Q^π_M_s(b_k,a_k)-ε Q^π_M_s(b_k,a_k,ε )] Then P(Ls≤QMπ(bk,ak,α))>(1−δ)(NbNb+1−ϵ)P(L_s≤ Q_M^π(b_k,a_k,α))>(1-δ) ( N_bN_b+1-ε ) and P(QMπ(bk,ak,α)≤Us)>(1−δ)(NbNb+1−ϵ)P(Q_M^π(b_k,a_k,α)≤ U_s)>(1-δ) ( N_bN_b+1-ε ). Proof. We prove the upper bound; the lower bound follows by an analogous argument applied to d^minπ(bk) d_ ^π(b_k). By Theorem 7.2, (141) Ps(Rk:T≤d^maxπ(bk)∣bk,π)≥NbNb+1,P(Rk:T≤d^maxπ(bk)∣bk,π)≥NbNb+1−ϵ.P_s(R_k:T≤ d_ ^π(b_k) b_k,π)≥ N_bN_b+1, P(R_k:T≤ d_ ^π(b_k) b_k,π)≥ N_bN_b+1-ε. Setting dmax=d^maxπ(bk)d_ = d_ ^π(b_k) and δdmax=1Nb+1+ϵ _d_ = 1N_b+1+ε in Theorem 7.3, both of its conditions are satisfied, and we obtain (142) P(QMπ(bk,ak,α)≤Us)>(1−δ)(1−δdmax)=(1−δ)(NbNb+1−ϵ).P(Q^π_M(b_k,a_k,α)≤ U_s)>(1-δ)(1- _d_ )=(1-δ) ( N_bN_b+1-ε ). An analogous argument with dmin=d^minπ(bk)d_ = d_ ^π(b_k) and δdmin=1Nb+1+ϵ _d_ = 1N_b+1+ε yields the lower bound guarantee. ∎ Appendix D Environment Configurations The following subsections describe the three POMDP environments used throughout the experiments, including the action elimination experiments of Figure 9. Each domain provides an original environment (used for sampling rollouts) and a simplified surrogate (used for belief updates and CVaR bound computation). The two models differ only in their observation and reward models, as summarised in Table 1. Aspect Original Simplified Observation noise Gaussian Mixture Model (GMM) Isotropic Gaussian Reward noise Stochastic (Push, Laser Tag) Deterministic Table 1. Architectural differences between the original and simplified models across all domains. D.1. Light-Dark State space: =(x,y)∈ℝ2s=(x,y) ^2 (2D continuous position). Action space: Discrete — up,down,left,right\up,down,left,right\, mapped to unit vectors in ℝ2R^2. Observation space: ∈ℝ2o ^2 — noisy 2D position. Parameter Value Grid size 7×77× 7 Start state (1, 1)(1,\;1) Goal state (6, 6)(6,\;6); radius 1.51.5 State transition covariance 0.06⋅I20.06· I_2 Obs. noise (far from beacon) (0, 0.06⋅I2)N(0,\;0.06· I_2) / GMM(K=2500K=2500) Obs. noise (near beacon) (0, 0.03⋅I2)N(0,\;0.03· I_2) / GMM(K=2500K=2500, scaled) Beacons (1,1),(1,6),(6,1),(6,6)(1,1),\;(1,6),\;(6,1),\;(6,6); radius 1.01.0 Obstacle (5,2)(5,2); radius 3.03.0; hit prob 1.01.0 Goal reward +10+10 Obstacle penalty −10-10 Step cost (fuel) −2-2 Discount factor γ 0.950.95 Planning horizon H 99 steps Table 2. Configuration for the 2D Light-Dark POMDP. Original: Two independent 1D GMMs (one per axis), K=2500K=2500 components, approximating the target Normal distribution. Simplified: Standard Gaussian (0,σ2I2)N(0,\;σ^2I_2) with the same σ. D.2. Continuous Push State space: =(rx,ry,ox,oy,tx,ty)∈ℝ6s=(r_x,r_y,o_x,o_y,t_x,t_y) ^6 — robot, object, and target positions. Action space: Discrete — up,down,left,right\up,down,left,right\, mapped to unit vectors. Observation space: ∈ℝ6o ^6 — robot and target positions observed exactly; object position is noisy: o^=o+ϵ,ϵ∼(0,σ2I2) o=o+ε,\;ε (0,σ^2I_2). Parameter Value Grid size 6×66× 6 Initial state (0.5, 0.5, 1.0, 0.5, 5.0, 5.0)(0.5,\;0.5,\;1.0,\;0.5,\;5.0,\;5.0) Robot transition covariance diag(0.005, 0.005)diag(0.005,\;0.005) Observation noise σ 0.10.1 (on object position) Push threshold 1.01.0 Friction coefficient 0.30.3 Max push force 2.02.0 Robot radius 0.30.3 Dangerous area (5.0, 2.0)(5.0,\;2.0); radius 1.01.0; penalty −20-20 Discount factor γ 0.950.95 Planning horizon H 99 steps Table 3. Configuration for the Continuous Push POMDP. Original: One 1D GMM (K=7000K=7000 components) applied independently to each object-position axis; additionally adds stochastic reward noise (0, 25)N(0,\;25). Simplified: Gaussian noise (0, 0.01⋅I2)N(0,\;0.01· I_2) on object position; deterministic reward. D.3. Continuous Laser Tag State space: =(rx,ry,ox,oy,term)∈ℝ4×0,1s=(r_x,r_y,o_x,o_y,term) ^4×\0,1\ — robot and opponent positions plus terminal flag. Action space: Discrete — up,down,left,right,tag\up,down,left,right,tag\. Observation space: ∈ℝ8o ^8 — 8-directional laser range measurements with additive noise; terminal states return =−o=-1. Parameter Value Arena 11×711× 7 continuous grid Walls 8 axis-aligned wall cells Initial state (2.0, 1.0, 8.0, 5.0, 0)(2.0,\;1.0,\;8.0,\;5.0,\;0) Robot transition covariance 0.0125⋅I20.0125· I_2 Opponent transition covariance 0.00625⋅I20.00625· I_2 Opponent pursuit speed 0.60.6 Laser noise σ 1.01.0 (per measurement) Robot / opponent radius 0.30.3 Tag radius 0.50.5 Tag reward +10+10 Failed-tag penalty −10-10 Step cost −1-1 Dangerous areas (5.0, 3.0),(7.0, 1.0)(5.0,\;3.0),\;(7.0,\;1.0); radius 1.01.0; penalty −300-300 Discount factor γ 0.950.95 Planning horizon H 88 steps (7 moves + tag) Table 4. Configuration for the Continuous Laser Tag POMDP. Original: One 1D GMM with K=290K=290 components (σcomp=0.097 _comp=0.097), applied independently to all 8 laser measurements; additionally adds stochastic reward noise (0, 0.25)N(0,\;0.25). Simplified: Gaussian noise (0, 1.0)N(0,\;1.0) per laser measurement; deterministic reward. D.4. Shared Planner Parameters Parameter Value CVaR level α 0.10.1 Belief particles NpN_p 1010 Return samples NrN_r 600600 Δ -estimation states 100100 Samples per state (for Δ ) 20002000 k-N neighbours 1010 Discount factor γ 0.950.95 Confidence parameter δ 0.050.05 Random seed 4242 Table 5. Planner parameters shared across all three environments. These parameters are used in the open-loop bound evaluation experiments (Figures 9, 10, and 11) and in the closed-loop policy evaluation experiments (Figures 12, 13, and 14). Appendix E Simulations The planning configurations below correspond to the open-loop experiments in Figures 9, 10, and 11. Figure 9 presents the estimated bounds and CVaR values for pairs of action sequences across all three environments, computed using 600 sampled belief trajectories and a confidence parameter of δ=0.05δ=0.05. The simplified planner samples NΔ=100N =100 states offline from the square region defined by the corners (0,0)(0,0) and (7,7)(7,7). For each sampled state, the distributional discrepancy Δ between the simplified and original observation models is estimated using Nz=2000N_z=2000 samples. CVaR is computed at confidence level α=0.5α=0.5, and the probabilistic bounds are constructed with confidence level δ=0.05δ=0.05. We set the number of sampled belief trajectories to Nb=600N_b=600. E.0.1. Continuous Laser Tag – Planning Configuration Parameter Value Number of Episodes 300 Steps per Episode 30 (max) Planning Depth 2 Return Samples (NbN_b) 600 CVaR α 0.5 Number of Particles (NpN_p) 10 Discount Factor (γ) 0.95 GMM Components 290 Table 6. Planning configuration for the Continuous Laser Tag experiments. E.0.2. Light-Dark – Planning Configuration Parameter Value Number of Episodes 300 Steps per Episode 30 (max) Planning Depth 2 Return Samples (NbN_b) 600 CVaR α 0.5 Number of Particles (NpN_p) 10 Discount Factor (γ) 0.95 GMM Components 7000 Table 7. Planning configuration for the Light-Dark experiments. E.0.3. Continuous Push – Planning Configuration The planning parameters used for Continuous Push experiments are summarized in Table 8; see Figure 9c for representative agent trajectories. Parameter Value Number of Episodes 300 Steps per Episode 30 (max) Planning Depth 2 Return Samples (NbN_b) 600 CVaR α 0.5 Number of Particles (NpN_p) 10 Discount Factor (γ) 0.95 GMM Components 7000 Table 8. Planning configuration for the Continuous Push experiments. Appendix F BetaZero Policy Configuration (Light-Dark) The closed-loop policy evaluation uses BetaZero (Moss et al., 2024a), an AlphaZero-style algorithm for POMDPs. A neural network maps a belief summary vector ϕ(b)φ(b) to a scalar value estimate V(b)V(b) and a policy prior π(a∣b)π(a b), which guide MCTS over particle beliefs. F.1. Belief Representation Particles are summarised into a fixed-size feature vector using the mean-and-standard-deviation representation: (143) ϕ(b)=[μ¯x,μ¯y,σ¯x,σ¯y]∈ℝ4,φ(b)= [ μ_x,\ μ_y,\ σ_x,\ σ_y ] ^4, where μ¯ μ and σ¯ σ are the weighted mean and standard deviation of the particle set. Parameter Value State dimension 2 Belief feature dimension 4 (= 2×2× state dim) Particles per belief NpN_p 500 Table 9. Belief representation parameters for BetaZero on Light-Dark. Input normalisation is applied using online statistics collected during training: Feature Mean Std μ¯x μ_x 3.56 1.91 μ¯y μ_y 4.12 1.91 σ¯x σ_x 0.302 0.407 σ¯y σ_y 0.303 0.408 Value output −24.34-24.34 36.64 Table 10. Input normalisation statistics for the BetaZero network. F.2. Network Architecture Two-headed MLP with a shared trunk and separate value and policy heads: Layer Size Input 4 Hidden 1 128 Hidden 2 128 Value head output 1 (scalar) Policy head output 4 (one logit per action) Table 11. BetaZero network architecture. F.3. MCTS Parameters Parameter Value Search depth 10 Simulations per step (training) 100 Simulations per step (inference) 1000 Exploration constant c 219.13 (tuned) Temperature τ 0.319 (tuned) Value weight zqz_q 1.0 Visit count weight znz_n 1.0 DPW action widening kak_a, αa _a 1.0, 0.5 DPW observation widening kok_o, αo _o 1.0, 0.5 Discount factor γ 0.95 Table 12. MCTS parameters for BetaZero on Light-Dark. F.4. Training Loop 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 Table 13. BetaZero training loop parameters. At each episode, a fresh initial belief is sampled: mean ∼([−1,8]2) ([-1,8]^2), std ∼(0.01, 2.0) (0.01,\;2.0), then Np=500N_p=500 particles are drawn from (mean,std2I)N(mean,\;std^2I). This diversity prevents the training distribution from collapsing to a uniform loop. F.5. Optimizer and Loss Parameter Value Optimizer Adam Learning rate 10−410^-4 Batch size 1024 Training epochs per iteration 50 Weight decay 10−510^-5 Loss Cross-entropy (policy) + MSE (value) Table 14. Optimizer and loss configuration for BetaZero training. F.6. Hyperparameter Search The exploration constant c and temperature τ were selected via Optuna (TPE sampler, 20 trials) with nsim=100n_sim=100 during search: Hyperparameter Search range Best value c (exploration constant) [1.0, 10×Δr]≈[1, 220][1.0,\;10× r]≈[1,\;220] 219.13 τ (temperature) [0.05, 0.5][0.05,\;0.5] 0.319 zqz_q, znz_n fixed 1.0, 1.0 Table 15. Hyperparameter search results for BetaZero on Light-Dark. Search used a MedianPruner (3 startup trials, 5 warmup steps) and a TPE sampler with seed 42. The objective minimised the final policy loss (cross-entropy vs. MCTS visit counts); the baseline uniform policy corresponds to ln⁡4≈1.386 4≈ 1.386. The best trial was retrained at nsim=1000n_sim=1000 for the final model used in all experiments. Appendix G Hardware Specifications All simulations were conducted on a machine equipped with an 11th Gen Intel® CoreTM i9-11900K CPU running at 3.50 GHz and 64 GB of RAM.

Instant research discovery