Tail-Influence Sampling for CVaR Policy Evaluation

Pauline Bourigault; Xiaotong Ji; Matthieu Zimmer; Rasul Tutunov; Haitham Bou-Ammar

cs.LGSep 29, 2026

Tail-Influence Sampling for CVaR Policy Evaluation

Authors: Pauline Bourigault, Xiaotong Ji, Matthieu Zimmer, Rasul Tutunov, Haitham Bou-Ammar

Organizations: Imperial College London · Huawei Noah’s Ark Lab · UCL Centre for AI

Abstract

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 $\times$ lower MSE than rollouts on six-call FinQA reviews.

Figures & tables

Figure 1: Equal visitation and reward variability can conceal different information about CVaR. The same kernel can be reused across many stages (Use 1,

\ldots

, Use

H

). A and B are visited equally and have identical reward means and variances, but only A’s returns can fall below the CVaR cutoff

q_{\alpha}

. TIS sums each pilot draw’s first-order CVaR effects across all uses, then measures their spread

\widehat{\sigma}_{g}

across draws; orange rings track one draw. With 20% uniform exploration, the illustrated scores give nominal fresh-query shares of 90%/10% for A/B, versus 50%/50% for visitation or mean influence (before minimum counts and rounding).

	$t=0$ (equal)		$t=\frac{1}{2}$		$t=1$ (one active)
Method	100	400	100	400	100	400
Uniform	1.00	1.00	1.00	1.00	1.00	1.00
Occupancy + pilot	1.60	1.31	1.67	1.39	1.69	1.31
Learned mean	1.63	1.28	1.71	1.39	1.87	1.34
Complete rollout	1.01	0.95	0.99	1.07	1.11	1.18
TIS	5.42	4.30	3.62	3.15	0.22	0.16

Table 1: TIS gains under concentrated tail influence; elsewhere its pilot does not repay. MSE/uniform MSE (

G=10,\alpha=.1

); columns: queries/kernel incl. pilots. Uniform=known occupancy; occupancy+pilot isolates pilot cost; Oracle+floor=population scores. Bold: sample-only column minima (point estimates). Table 3 : absolute errors/SEs.

Figure 2: At largest budgets, TIS MSE is lower than learned occupancy, learned mean, and rollouts. CVaR MSE vs. charged queries/kernel in (a) CliffWalking and /block in (b) inventory. Conditional-query methods have direct kernel access; rollouts use trajectories at same charged transition budget. Oracle+floor=population scores; bars=

1.96

Monte Carlo SEs.

Domain	vs. occupancy $+$ uniform	vs. occupancy $+$ mean
Inventory disruption family	18/18 (0)	17/18 (0)
FinQA review (held-out)	16/16 (0)	0/16 (15)
MMLU-Pro, Brier utility (6 generators $\times$ 3 budgets)	18/18 (0)	11/18 (0)
MMLU-Pro high-stakes panel (3 generators $\times$ 3 budgets)	9/9 (0)	5/9 (2)
MMLU-Pro, confident-error utility (6 generators)	24/24 (0)	23/24 (0)
FinQA with calculator faults (ordinary review)	15/18 (0)	0/18 (12)

Table 2: Anchor vs. equally regularized blends: never resolved worse than uniform; mean-blend gains depend on domain. Counts of resolved (

|z|\geq 2

) lower (higher) anchor MSE vs. each blend. Inventory: 18 cases at

1{,}200

queries/block; FinQA: 2 generators

\times

2 workflows

\times

4 budgets.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Controlled

H=5

MRP (21 untied blocks): CVaR MSE versus total queries for learned methods and population references; bars are

1.96

Monte Carlo SEs.

	$t=0$		$t=\frac{1}{2}$		$t=1$
Queries/kernel	100	400	100	400	100	400
Uniform	$\mathbf{11.07}\,(0.48)$	$2.98\,(0.13)$	$11.44\,(0.50)$	$\mathbf{2.69}\,(0.12)$	$9.79\,(0.44)$	$2.46\,(0.12)$
Occupancy + pilot	$17.68\,(0.79)$	$3.89\,(0.17)$	$19.12\,(0.86)$	$3.73\,(0.17)$	$16.51\,(0.76)$	$3.22\,(0.16)$
Learned mean	$18.05\,(0.79)$	$3.82\,(0.16)$	$19.53\,(0.92)$	$3.74\,(0.16)$	$18.32\,(1.07)$	$3.30\,(0.17)$
Complete rollout	$11.16\,(0.56)$	$\mathbf{2.84}\,(0.12)$	$\mathbf{11.27}\,(0.50)$	$2.87\,(0.12)$	$10.84\,(0.46)$	$2.90\,(0.13)$
TIS	$59.96\,(3.19)$	$12.82\,(0.66)$	$41.45\,(2.68)$	$8.47\,(0.44)$	$\mathbf{2.17}\,(0.11)$	$\mathbf{0.40}\,(0.02)$

Appendix

Table 3: Absolute MSE

\times 10^{5}

(Monte Carlo SE) for the six main controlled-separation settings;

1{,}000

replications per entry.

Method	150	300	600	1,200
Uniform	1.232	0.583	0.303	0.176
Reachability only	1.091	0.659	0.297	0.177
Local scale only	1.908	1.049	0.531	0.285
Oracle + floor	0.731	0.329	0.150	0.100
Learned occupancy	1.517	0.634	0.311	0.161
Learned mean	1.361	0.571	0.302	0.152

Appendix

Table 4: Inventory MSE

\times 10^{3}

over 300 replications versus charged queries per retained block.

Pilot fraction	$\lambda=N^{-1/6}$	$N^{-1/4}$	$N^{-1/3}$
$3.7\%$	1.124 (1.184)	1.111 (1.184)	1.123 (1.212)
$7.2\%$	1.082 (1.108)	1.057 (1.087)	1.054 (1.088)
$14.2\%$	1.064 (1.073)	1.034 (1.043)	1.028 (1.038)
$28.3\%$	1.055 (1.060)	1.023 (1.028)	1.015 (1.020)

Appendix

Table 5: Inventory pilot sensitivity: median (90th percentile)

V(\widehat{w})/V^{*}

over 300 pilots.

Method	50	100	200	400
Uniform	1683.126	818.420	363.617	216.877
Occupancy (population)	26.269	12.474	5.727	2.741
Mean influence (population)	19.182	9.731	4.371	2.164
Learned mean	27.413	11.367	5.349	2.307
Learned occupancy	35.792	15.924	6.450	3.189
Complete rollout	65.883	32.221	16.257	7.954

Appendix

Table 6: CliffWalking MSE

\times 10^{3}

over 500 replications versus charged queries per reachable kernel.

Generator	TIS	occup.	rollout	anchored	oracle +floor
Qwen3-4B	1.38	.090	.074	.057	.058
Phi-4-mini	.49	.113	.072	.066	.025
Granite-4.2-8B	.15	.126	.107	.070	.034
Mistral-24B	.21	.138	.127	.093	.055
Qwen3-32B	.41	.079	.055	.056	.028
GLM-4-32B	1.77	.087	.069	.065	.034

Appendix

Table 7: MMLU-Pro: anchoring mitigates plain TIS’s observed failures. Panel MSE/uniform MSE at

H=6

\alpha=.1

, 400 queries/kernel.

Component	MMLU-Pro	FinQA
State after a call	Answer $j$ and confidence $c$ ( $10\times 9$ possibilities)	Candidate $i$ and confidence $c$ ( $8\times 9$ possibilities)
Initial action	solve	select
Number of calls	$H=2,4,6$ , including the initial solve	$H=3$ : selection and two reviews
Stage index	$h=H-t$ calls remaining; stop at $h=0$	$h=3,2,1,0$ ; stop at $h=0$
Query groups	$1+90=91$ per question	$1+72=73$ per question and workflow
Reward on $s\to s^{\prime}$	$r_{q}(s^{\prime})$ : normalized Brier utility	$[u(s^{\prime})-u(s)+1]/2$ : shifted utility change

Appendix

Table 8: MMLU-Pro and FinQA workflow models; both use the confidence-band review policy.

Generator	$H$	plain TIS	anchored TIS	learned mean	learned occup.	rollout	TIS no cov.	untied	MC-UCB	oracle +floor
Qwen3-4B	2	.719	.030	.307	.036	.028	.719	.724	1.04	.192
	4	1.02	.059	.707	.069	.057	1.02	4.28	1.08	.058
	6	1.38	.057	1.00	.090	.074	1.35	7.67	1.06	.058
Phi-4-mini	2	.181	.027	.106	.032	.023	.181	.183	1.03	.015
	4	.326	.047	.264	.074	.048	.327	1.33	1.11	.020
	6	.487	.066	.425	.113	.072	.493	3.00	1.48	.025

Appendix

Table 9: MMLU-Pro,

\alpha=.1

, 400 queries/shared kernel: MSE/uniform MSE.

\dagger

marks follow-up generators; Table 10 gives absolute TIS MSE.

Generator	$H=2$	$H=4$	$H=6$
Qwen3-4B	2.2e-04 (1e-05)	9.7e-04 (6e-05)	2.7e-03 (2e-04)
Phi-4-mini	2.8e-04 (1e-05)	1.7e-03 (1e-04)	5.1e-03 (5e-04)
Granite-4.2-8B	9.8e-05 (5e-06)	1.3e-04 (1e-05)	2.4e-04 (1e-05)
Mistral-24B †	1.2e-04 (2e-05)	3.5e-04 (3e-05)	9.6e-04 (1e-04)
Qwen3-32B †	5.7e-04 (4e-05)	2.9e-03 (3e-04)	7.5e-03 (8e-04)
GLM-4-32B †	4.1e-04 (3e-05)	4.2e-03 (2e-04)	1.9e-02 (9e-04)

Appendix

Table 10: Absolute TIS panel MSE (Monte Carlo SE),

\alpha=.1

, 400 queries/kernel; 300 replications.

	shared TIS				untied TIS
Generator	50	100	200	400	50	100	200	400
Qwen3-4B	.819	.851	1.22	1.38	8.59	4.53	5.44	7.67
Phi-4-mini	.448	.499	.469	.487	4.29	2.02	2.55	3.00
Granite-4.2-8B	.469	.386	.248	.154	5.49	1.64	2.06	1.56
Mistral-24B †	.497	.462	.391	.214	5.81	1.58	2.08	1.90
Qwen3-32B †	.681	.606	.497	.411	5.45	2.71	2.91	3.71

Appendix

Table 11: Budget sensitivity at

H=6

\alpha=.1

: shared/untied TIS MSE relative to uniform at equal total budget.

Generator	$H=2$	$H=4$	$H=6$
Qwen3-4B	.195 (18.8)	.290 (14.4)	.613 (6.2)
Phi-4-mini	.115 (37.4)	.219 (25.0)	.521 (8.0)
Granite-4.2-8B	.120 (43.8)	.084 (42.6)	.088 (37.1)
Mistral-24B †	.068 (49.5)	.175 (31.5)	.289 (16.9)
Qwen3-32B †	.170 (33.5)	.232 (27.5)	.368 (16.2)
GLM-4-32B †	.345 (20.6)	.929 (1.1)	1.52 (-6.2)

Appendix

Table 12: Risk sensitivity at

\alpha=.2

, 400 queries/kernel: TIS MSE/uniform MSE with uniform-minus- TIS

z

(positive favors TIS ); GLM

H=4

is unresolved.

Task	Budget	Uniform	Occ.	Mean	TIS	Anch.	Mean blend	Rollout
CliffWalking	400	110	122	394	394	396	390	32
Inventory	1,200	5.0	6.5	10.7	10.9	10.8	11.2	5.2
FinQA panel (50 q.)	200	658	823	2,031	2,015	2,039	2,040	298

Appendix

Table 13: CPU milliseconds per replication for the full sampling-and-estimation pipeline at fixed query budgets; FinQA is the 50-question Phi ordinary-review panel. These are frozen-law replay times, not live-call costs.

Figure 4: FinQA: the anchor beats occupancy and rollouts on Phi at 400/800 queries; Qwen favors the baselines. (a,b) Mean panel-MSE/uniform-MSE ratio across workflows; (c) Phi wrong-selection rate. Table 14 gives per-workflow results.

Gen.	Workflow	Budget	Unif. MSE	Anch./unif.	Anch./occ.	Anch./roll.	$z$
qwen	ordinary	25	$6.2\,e{-5}$	0.152	1.84	3.52	+5.3
qwen	ordinary	50	$2.8\,e{-5}$	0.127	2.10	2.81	+6.5
qwen	ordinary	100	$1.6\,e{-5}$	0.089	1.47	2.07	+8.1
qwen	ordinary	200	$6.7\,e{-6}$	0.097	1.77	2.30	+9.9
qwen	ordinary	400	$3.3\,e{-6}$	0.075	1.41	1.62	+10.0
qwen	ordinary	800	$2.0\,e{-6}$	0.077	1.66	2.11	+10.2

Appendix

Table 14: FinQA frozen-metric estimation: uniform panel MSE, anchor-to-baseline MSE ratios, and paired uniform-minus-anchor

z

over 300 replications.

Gen.	Budget	$C_{\mathrm{ord}}$	$C_{\mathrm{unit}}$	Gap	Unif.	TIS	Occ.	Roll.	Anch.	Oracle +floor
qwen	25	1.87304	1.87262	+0.00041	0.0	2.0	0.0	0.0	0.7	0.0
qwen	50	1.87304	1.87262	+0.00041	0.0	0.3	0.0	0.0	0.0	0.0
qwen	100	1.87304	1.87262	+0.00041	0.0	0.3	0.0	0.0	0.0	0.0
qwen	200	1.87304	1.87262	+0.00041	0.0	1.0	0.0	0.0	0.0	0.0
phi	25	1.76764	1.76697	+0.00067	45.3	50.0	36.3	38.3	42.3	36.3
phi	50	1.76764	1.76697	+0.00067	45.3	47.3	34.0	27.0	33.3	24.3

Appendix

Table 15: FinQA frozen-metric workflow selection at 25–200 queries/kernel: exact panel CVaRs, their gap, and wrong-selection percentages under shared workflow streams. Zero means no errors in 300 replications.

Method	occupancy	learned mean	occ. $+$ uniform	occ. $+$ mean	rollouts
TIS	18	17	18	18	18
anchored TIS	18	17	18	17	18

Appendix

Table 16: Inventory family: resolved lower-MSE cases (of 18) at 1,200 queries/block, using paired

|z|\geq 2

; none resolve in the comparator’s favor.

	FinQA $H=3$			FinQA $H=6$
Generator, workflow	100	200	400	100	200	400
Phi-4-mini, ordinary	$1.10$ ( $+1.9$ )	$.84$ ( $-4.4$ )	$.77$ ( $-5.2$ )	$.36$ ( $-22.1$ )	$.30$ ( $-22.5$ )	$.29$ ( $-22.4$ )
Phi-4-mini, unit check	$1.50$ ( $+10.0$ )	$1.07$ ( $+1.8$ )	$.88$ ( $-3.1$ )	$.64$ ( $-10.4$ )	$.47$ ( $-17.3$ )	$.41$ ( $-19.7$ )
Qwen3-4B, ordinary	$2.07$ ( $+6.1$ )	$2.30$ ( $+5.9$ )	$1.62$ ( $+3.4$ )	$2.64$ ( $+6.5$ )	$2.03$ ( $+5.1$ )	$2.02$ ( $+5.3$ )
Qwen3-4B, unit check	$2.28$ ( $+9.5$ )	$2.26$ ( $+8.6$ )	$1.74$ ( $+5.4$ )	$2.73$ ( $+8.8$ )	$2.09$ ( $+7.2$ )	$2.13$ ( $+7.3$ )
MMLU-Pro, 400 queries	$H=6$		$H=8$		$H=10$

Appendix

Table 17: Longer review loops favor the anchor over rollouts. Anchored- TIS /rollout MSE ratio (paired

z

; negative favors the anchor), 300 replications. The Phi

H=6

, 400-query ratios

.29/.41

give the

3.4\times/2.4\times

reductions in the abstract.

Figure 5: Anchoring reduces the variance penalty from poor pilots. (a) Realized/oracle leading variance; (b) occupancy versus tail-influence shares; (c) observed MSE versus the no-fit prediction

V(w)/n

. Rollouts are excluded.

Established starting point	Additional result here
Return-law and functional inference under specified sampling ( Zhang et al., 2025 ) ; quantile-based efficiency ( Cheng et al., 2026 ) .	An explicit categorical-CVaR influence for each conditional kernel, including its joint reuse across stages. Theorems 1 and 2 give the variance as a function of query shares and its fixed-design efficiency interpretation.
Neyman allocation and learning unknown stratum variances ( Neyman, 1934 ; Étoré and Jourdain, 2010 ; Carpentier et al., 2015 ) .	The influence function depends on the unknown model and quantile. Theorem 3 controls learning those quantities, quantile errors, and Bellman remainders to obtain oracle variance and normalized MSE, including pilot cost and individual zero-influence groups.
Trajectory collection for mean policy evaluation ( Mukherjee et al., 2022 ; Mukherjee et al., 2024 ) .	Independent conditional queries for a fixed policy’s tail functional. Proposition 1 shows why visitation and mean-optimal allocation can miss the relevant signal. Comparisons with complete rollouts are empirical; the product-model efficiency theorem does not cover their different sampling experiment.

Appendix

Table 18: Established foundations and the additional results for the conditional-query CVaR problem. The allocation rule is Neyman allocation; the work here identifies and learns the Bellman influence scales it needs.

Policy Evaluation

Policy evaluation estimates the outcomes, value, risks, and fairness of decision rules before or after deployment.

See all 55 papers

Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search
Oct 16, 2026Quynh Trinh, Trung Nguyen, Nam Nguyen +1Risk-Sensitive Planning Monte Carlo Tree Search
Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam
Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity
Feb 3, 2026Aneri Muni, Vincent Taboga, Esther Derman +2Markov Decision Processes Q-Learning
Universit´e de Montr´eal, Quebec, Canada · Mila - Quebec AI Institute, Quebec, Canada · GERAD & Department of Decision Sciences, HEC Montr´eal, Quebec, Canada
Risk-Averse Inference-Time Diffusion Model Alignment with Finite-Sample Guarantees
Oct 13, 2026Yuchen Liang, Xian YuDiffusion Model Alignment Stochastic Optimization
Indiana University Indianapolis · The Ohio State University

Oct 16, 2026J/K move · Enter open · S save

Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search

Quynh Trinh, Trung Nguyen, Nam Nguyen, Tuan Dam

Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam

Risk-Sensitive Planning Monte Carlo Tree Search Decision-Making under Uncertainty Conditional Value-at-Risk Thompson Sampling

Open paper AskPDF arXiv

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.

Abstract

Policy Evaluation

Explore similar work

Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search

Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

Risk-Averse Inference-Time Diffusion Model Alignment with Finite-Sample Guarantees