Risk-aware planning must identify rare, costly outcomes using only a limited number of model evaluations. Monte Carlo rollouts spend this budget on noisy tail estimates, while planning from the mean can miss the tail entirely. We introduce quantile propagation planning (QPP), which propagates a small, fixed set of disturbance quantiles through the dynamics and integrates the resulting cost curve to evaluate both mean and tail risk. The method is exact at the propagated levels, converges as the quantile grid is refined, and admits a one-sided conservatism guarantee under stated structural conditions. In controlled overload and inventory tasks, QPP reduces realized tail cost and constraint violations relative to mean-rollout planning. On overload, it remains competitive with sampled evaluators that use substantially more trajectories. These results position QPP as a transparent, budget-controlled approach to tail-risk evaluation.
Figures & tables
Figure 1: QPP in the closed-loop planning pipeline. Fixed disturbance levels generate coupled trajectories and an analytic mean–tail score; CEM ranks candidate plans, executes the first action, observes the next state, and replans.
Figure 2: Planning holds one rank through the horizon (left; colored endpoint labels give the five fixed quantile levels), whereas execution draws a fresh rank at each step (right; colors only distinguish sample paths). Equal one-step marginals need not imply equal temporal dependence or tail behavior.
Figure 3: Controlled-environment results on overload. (a) QPP moves along a mean–tail frontier rather than dominating every metric. (b) Increasing trajectory count improves sampled evaluation, but the low-budget QPP points remain competitive; bars show bootstrap intervals. The appendix reports the full statistical comparisons and inventory counterexample.
CVaR0.1
Mean cost
Environment
QPP
Mean
Δ
QPP
Mean
Overload
-4.858
-0.032
-4.826
-5.209
-7.170
Inventory
163.139
270.013
-106.874
141.384
63.146
Table 1: Point estimates against mean rollout; lower is better and Δ is QPP minus mean rollout. Full results are in Appendix Tables 5 and 6 .
Environment
n
QPP K=5
MC S=5
MC S=20
MC S=50
Overload
200
-4.823
-1.989
-4.058
-4.735
Inventory
400
163.558
208.987
130.009
113.208
Table 2: Realized CVaR0.1 in the trajectory-count sweeps; lower is better. Inventory reports the corrected n=400 audit; full statistical results and extended sweeps are in the appendix.
Figure 4: Sitewise one-sided 95% bounds for the fitted microgrid. Dashed lines mark the gates: B1 passes at three sites, while V1 improves at all four. Bounds are frozen and unadjusted; the multiplicity audit is in the appendix.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Site-specific quantities fitted without pooling the four held-out evaluation sites. Labels give the exact scale, innovation scale sr , and capacity threshold pcap used by each site’s simulator. The separate axes preserve the three quantities’ natural units rather than normalizing them to a common visual scale.
Gate
Over.
Inv.
Micro.
Other
1a/b/c propagation versus coupled MC
Sat.
D1 reserve discrimination ≥0.15
Sat.
Not sat. 2/2
GE2 calibration (skill, PIT, support)
Sat.
B1 tail below mean rollout
Sat.
Sat.
Sat. 3/4
V1 headroom-loss rate below mean rollout
Sat. 4/4
H1 tail gap versus both noise-blind baselines ≥2
Sat.
Appendix
Table 3: Primary, calibration and application criteria. “Sat.” means satisfied, “Not sat.” means not satisfied, “Inc.” means inconclusive, “Negative” denotes a discharged negative result, and “N/A” denotes a criterion that was not evaluated. † Satisfied by action-bound saturation and not claimed (Section 7 ). Microgrid planning gates are read per site; GE2 and GE3 are pooled cross-client source gates. A fraction reports the number of site- or row-specific outcomes with the displayed status.
Gate or diagnostic
Over.
Inv.
Micro.
Other
C1 tail below MC under each sampler (4)
Not sat. 4/4
Not sat. 4/4
C2 tail below mean rollout under each sampler (4)
Sat. 4/4
Sat. 4/4
C3 tail gap within Gaussian-row margin (4)
Sat. 2/4; Inc. 2/4
Not sat. 2/4; Inc. 2/4
C4 candidate-stream variance halved (8)
Sat. 3/8
Not sat. 8/8
Diagnostics without a prospectively specified bar
B2 ′ both-stream decision variance versus MC
Not sat.
Appendix
Table 4: Composition gates and ungated diagnostics, using the status labels defined in Table 3 . C1–C4 were prospectively specified; the bottom block was not.
Figure 6: Overload B3 trajectory-count follow-up. The curves show sampler-minus-QPP tail-cost gaps. IID intervals join the paired one-sided 95% lower and upper bounds used by the B3 branches; clipped-coupled intervals are two-sided 95% intervals for the separate equivalence diagnostic. The shaded region is the ±0.2411 cost-unit comparison band.
Figure 7: One-step cost quantiles under standardized lognormal noise. The deployed five-level QPP approximation is shown together with a dense-grid reference; both retain positive skew and upper-tail curvature, whereas Gaussian moment matching is symmetric by construction. This diagnostic concerns distributional shape, not calibration or planning performance.
Site
Gain
95% lower
98.75% lower
p0.10
Holm p
242
0.188
0.136
0.118
0.0004
0.0013
253
0.153
0.102
0.085
0.0217
0.0435
255
0.121
0.068
0.052
0.2097
0.2097
279
0.185
0.141
0.125
0.0000
0.0001
Appendix
Table 23: Post-hoc cross-site audit of the B1 relative CVaR0.1 gain. The 95% column reproduces the sitewise gate scale; the 98.75% column and Holm p values address the four-site family in two complementary ways.
Figure 8: Microgrid trajectory-count sweeps at all four held-out sites. Each panel compares IID Monte Carlo and the clipped coupled sampler with K=5 QPP as S increases. Error bars are bootstrap 95% intervals; the narrow blue region is the 5% sampler-denominated comparison band above QPP. The CEM population, elite count and iteration count are fixed, so this is not a best-allocation total-budget frontier. n=200 per point.
Site
IID gap with 95% lower bound
B3
Clipped gap with 95% CI
Equivalence
242
11.1%−4.7%+∞
Satisfied
5.4%−4.3%+4.7%
Not satisfied
253
15.1%−5.4%+∞
Satisfied
6.6%−3.3%+3.4%
Not satisfied
255
12.0%−5.0%+∞
Satisfied
5.1%−3.5%+3.5%
Not satisfied
279
9.3%−4.1%+∞
Satisfied
7.8%−4.5%+4.9%
Not satisfied
Appendix
Table 30: Cross-site decision summary at S=200 . Positive gaps mean that the sampler has higher realized CVaR0.1 than QPP. IID entries pair the point estimate with the one-sided 95% lower bound used by B3; clipped-coupled entries use the two-sided interval required by the equivalence diagnostic. All four B3 criteria are satisfied by the lower-bound branch, while none of the four equivalence criteria is satisfied.
Monte-Carlo Tree Search (MCTS) typically stores only scalar mean estimates, which makes it poorly suited for tail-risk objectives such as conditional value-at-risk (CVaR). We introduce Categorical Thompson Sampling with Optimism (CATSO) and Particle Thompson Sampling with Optimism (PATSO), two distributional MCTS algorithms that maintain finite-support empirical backup laws at Q-edges. CATSO represents Q-edge laws with categorical atoms and Dirichlet Thompson sampling, while PATSO represents them with adaptive particles. Both algorithms select actions using the CVaR of a Thompson-sampled Q-edge law plus a polynomial optimism bonus, and propagate scalar continuation values through visit-weighted averages of child Q-edge CVaR scores. For the finite-depth nested CVaR planning target, we prove an O(n−1/2) bound on the root value error after n rollouts, which upper-bounds the risk-sensitive simple regret. CATSO adds a fixed-grid discretization bias, while capped PATSO adds a tunable Wasserstein compression bias. Experiments on stochastic planning benchmarks show that distributional Q-edges improve lower-tail return and reduce catastrophic outcomes when mean-optimal and risk-sensitive behavior differ.
Quynh Trinh, Trung Nguyen, Nam Nguyen +1
Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam
Policies with similar mean returns can differ sharply in rare failures, yet estimating lower-tail conditional value-at-risk (CVaR) accurately can require many costly rollouts. When different conditional components of a stochastic workflow can be queried separately, we ask how to allocate a fixed evaluation budget to estimate a fixed policy's CVaR most accurately. We derive a tail influence for each queryable conditional law that aggregates how its uncertainty affects CVaR across every Bellman reuse. Its variance yields the fixed-design efficiency bound and the oracle Neyman allocation. Tail-Influence Sampling (TIS) estimates these influence scales from a pilot model and reallocates fresh queries toward kernels that matter most for the tail; a visitation-anchored variant protects against pilot underallocation. Under fixed dimension and a positive quantile margin, TIS attains oracle asymptotic variance and first-order MSE including pilot cost, while the anchored variant is within a factor two of the oracle. We also characterize an exact-grid regime in which tail- and mean-optimal allocations coincide. On CliffWalking, TIS reduces MSE by 41% versus learned occupancy and 76% versus complete rollouts at the same charged transition budget. In frozen language-model review workflows, anchored TIS beats an equally regularized mean-influence blend in 23 of 24 MMLU-Pro settings and reaches 2.4-3.4× lower MSE than rollouts on six-call FinQA reviews.
Pauline Bourigault, Xiaotong Ji, Matthieu Zimmer +2
Imperial College London · Huawei Noah’s Ark Lab · UCL Centre for AI
Safe reinforcement learning seeks policies that maximize return while satisfying constraints on cumulative cost. Most methods impose these constraints on expected episodic cost. Consequently, standard evaluations report mean episodic cost without characterizing how cost is distributed across episodes. A policy that satisfies the mean-cost criterion may therefore remain unsafe in its worst episodes. Mean-cost reporting neither identifies this tail violation nor shows whether it can be brought within budget while preserving return. In this work, we measure the episodic-cost tail using CVaR0.1, the average cost of the worst 10% of episodes. We classify a policy as tail-safe when CVaR0.1 is within the safety budget. This allows us first to identify policies that are safe on average but unsafe in the tail and then to study whether their tail violations can be controlled while preserving return. To identify tail-unsafe policies, we evaluate five standard algorithms on three Safety-Gymnasium navigation tasks. We then examine four constraint families on dense-hazard navigation and assess tail control across four navigation and four locomotion tasks.