We consider minimising a spectral risk objective, the expected cost plus a weighted conditional value-at-risk, when the distribution of the uncertain parameters depends on the decision and can only be sampled through a stochastic simulator under a fixed budget of draws. We propose adaptive conditional residual sampling (ACRS). It takes one simulator draw at each point of a space-filling design, fits a heteroscedastic regression model of the decision-dependent distribution and reuses the standardised residual vectors as scenarios to construct a deterministic surrogate. ACRS searches this surrogate for several local optima, adds draws around the most promising ones, ranks the candidates on the simulator with common random numbers and finishes with sample-path local refinement using tail importance sampling. We show that the optimality gap of the surrogate minimiser is bounded by the Wasserstein error of the scenario distribution and that the refinement estimator is consistent. In the experiments, all methods share the budget accounting, the design sampler and the local refinement routine, and solutions are scored by normalised regret against reference optima. On 60 random instances of an analytic family with a closed-form objective, ACRS attains a mean regret of 11.8% against 22.3-42.3% for Bayesian optimisation, cross-entropy, kernel-density, stochastic-gradient and refinement-only baselines; its lead is largest at small budgets and, relative to the kernel-density method, tends to grow with the dimension. ACRS also has the lowest mean regret on two six-dimensional benchmarks and three development problems, and performs comparably to pure local refinement on three held-out problems frozen before testing.
Figures & tables
Figure 1: Schematic of ACRS. Phases 1–4 form the global phase; phase 5 is the local refinement routine, which all methods in the experiments use whenever enough budget remains. Budget shares refer to the total budget B of simulator draws; the reranking budget is spent only if the surrogate has more than one distinct candidate. Every simulator draw is debited from one counter with hard cap B ; on exhaustion the incumbent is returned
Family
d
m
Units
B (k)
Reps
Final evaluation
Analytic family
2–8
3
60 instances
2, 5 or 10
4
exact
DGP1, DGP2 a
6
5
18 settings
5, 10, 30
30
20,000 draws
E1–E3 (development)
3–5
2–5
9 settings
2, 5, 10
20
100,000 draws
E4–E6 (held-out)
3–5
3–5
9 settings
2, 5, 10
20
100,000 draws
Table 1: Benchmark families. d : decision dimension; m : dimension of W ; B : simulation budget. Each analytic instance has one budget, drawn at random. Final evaluation is exact or uses a large sample of common random numbers shared by all methods within a replication a a footnotetext: Each with λ∈{0.5,0.7,0.9} .
Adam with common-random-number central differences
≈ 85%
best checkpoint overall and of each chain
Refine-only
none
0%
3 random feasible points
Table 2: Methods compared. All methods use the same design sampler and, whenever enough budget remains, the same local refinement (Section 4.5 ), which receives the listed starting points and uses the remaining budget
Opponent
Mean regret
ACRS better / tie / worse
p
Analytic family, 60 instances; ACRS mean regret 11.8
GP-BO
29.4
48
7
5
< 0.001
CEM
22.3
40
14
6
< 0.001
KDE-SO
26.1
38
17
5
< 0.001
SGD-CVaR
42.3
56
2
2
< 0.001
Refine-only
22.9
39
12
9
< 0.001
Table 3: Head-to-head comparison of ACRS with each competitor, by family. Units are instances (analytic family) or settings (other families), summarised by their mean normalised regret. Better/tie/worse count units on which ACRS has lower, equal (within 0.5) or higher mean regret; p is a two-sided paired Wilcoxon signed-rank test on unit means, Holm-adjusted over the five competitors within each family (unadjusted for the best competitor per unit) a a footnotetext: For each unit, the competitor with the lowest mean regret on that unit, chosen after the fact.
Figure 2: Analytic family: mean normalised regret by (a) budget (thousands of simulator draws) and (b) decision dimension, with 95% bootstrap intervals over instances (60 instances, 4 replications each). Methods are distinguished by marker shape and line type
n
ACRS
GP-BO
CEM
KDE-SO
SGD-CVaR
Refine-only
B=2000
25
24.5
43.5
43.3
48.6
61.2
40.6
B=5000
16
5.3
29.5
10.7
13.6
48.3
15.3
B=10000
19
0.7
10.8
4.5
6.9
12.5
6.1
d=2
16
4.2
20.0
15.9
4.7
17.3
21.1
d=4
16
5.1
20.5
11.8
17.9
35.1
17.7
d=6
11
10.3
26.4
23.3
36.1
45.8
14.3
Table 4: Analytic family: mean normalised regret by budget, dimension and jump regime ( n = number of instances). The lowest value in each row is in bold
Figure 3: External problems: mean normalised regret by budget (thousands of simulator draws) with 95% bootstrap intervals over 20 replications; (a)–(c) development set E1–E3, (d)–(f) held-out set E4–E6. Methods are distinguished by marker shape and line type. The vertical scales differ between panels
Problem
B (k)
ACRS
GP-BO
CEM
KDE-SO
SGD-CVaR
Refine-only
Development set
E1
2
3.8
26.7 +
21.3 +
29.3 +
74.4 +
39.3 +
E1
5
0.4
16.2 +
10.1 +
9.6 +
18.0 +
10.1 +
E1
10
0.3
5.0 +
2.5 +
0.5 +
9.8 +
3.4 +
E2
2
20.1
103.5 +
100.3 +
59.5 +
68.5 +
35.7
E2
5
16.8
31.3 +
38.5 +
36.3 +
64.5 +
39.1 +
Table 5: External problems: median normalised regret over 20 replications. Bold: lowest median in the row. + / - : the competitor is significantly worse/better than ACRS (paired Wilcoxon test over replications, Holm-adjusted over five comparisons, level 0.05)
Figure 4: Analytic family: exact normalised regret of ACRS after the surrogate search, after oracle reranking and after the local refinement, by budget (240 runs; boxes show quartiles, whiskers 1.5 interquartile ranges; values below 0.01 are shown at 0.01)
Variant
Mean regret
Median regret
p
ACRS (full)
11.8
0.5
–
without focused augmentation
16.3
1.0
0.005
without oracle reranking
17.0
2.2
0.004
without tail importance sampling
12.3
0.7
0.333
quadratic location model only
20.2
4.5
< 0.001
kernel weights instead of residual model
15.1
1.0
0.112
Table 6: Ablation of ACRS on the 60 analytic instances (4 replications each). p : two-sided paired Wilcoxon test against the full method on instance means, Holm-adjusted over the six variants
Figure 5: Ablation of ACRS on the 60 analytic instances: mean normalised regret with 95% bootstrap intervals over instances. The dashed line marks the full method
DGP1
DGP2
Conditional model
N=1000
N=5000
N=1000
N=5000
Time (s)
Residual, quadratic location
18.5
6.1
44.6
27.0
1.7
Residual with forest weights
20.7
14.8
44.6
35.1
78.0
Kernel weights
31.5
38.2
74.8
54.2
2.2
Generalised random forest
48.1
29.4
72.4
63.6
85.0
Distributional random forest
52.2
33.6
69.9
66.0
41.3
Table 7: Choice of conditional model (preliminary experiment): median relative gap (%) between the objective at the surrogate minimiser and at the reference optimum, without any simulator draws after the N design draws (15 replications per cell), and median fitting and search time
Table 2: Decision-dependent parameters of DGP2 (Gaussian copula with log-normal marginals); σj is floored at 0.05
Setting
B=2000
B=5000
B=10000
B=30000
ACRS: design n0
200
500
1000
3000
ACRS: augmentation na
100
250
500
1500
ACRS: reranking (at most)
320
320
500
1500
Refinement: sample-path size nℓ
80
80
80
102
Refinement: selection/pilot size ns
150
150
150
170
GP-BO: draws per evaluation
50
50
50
115
Appendix
Table 1: Budget-dependent settings. EI: expected improvement. CEM population: analytic and external problems; on DGP1/DGP2 the population is 30 at every budget
DGP
λ
B (k)
ACRS
GP-BO
CEM
KDE-SO
SGD-CVaR
Refine-only
DGP1
0.5
5
0.5
3.9 +
7.0 +
0.7 +
68.2 +
5.5 +
DGP1
0.5
10
0.2
1.3 +
0.2
0.2
3.7 +
0.2
DGP1
0.5
30
0.1
0.5
0.1
0.1
0.5
0.1
DGP1
0.7
5
1.1
5.5 +
6.5 +
0.7
63.1 +
5.8 +
DGP1
0.7
10
0.1
1.9 +
0.3
0.6 +
3.5 +
0.0
DGP1
0.7
30
0.3
0.2
0.1
0.1
0.8
0.1
Appendix
Table 1: DGP1 and DGP2: median normalised regret over 30 replications. Bold: lowest median in the row. + / - : the competitor is significantly worse/better than ACRS (paired Wilcoxon test over replications, Holm-adjusted, level 0.05)
We study Bayesian optimization of the Conditional Value-at-Risk (CVaR) of an expensive black-box function that depends on a decision and an environmental variable. Existing no-regret algorithms assume that the correct Gaussian process (GP) kernel and its hyperparameters are known. In practice, however, they must be estimated from limited data, often yielding a misspecified surrogate. This is especially damaging for CVaR because misspecification can distort the estimated tail-risk and thus lead to catastrophic decisions. We propose HE-CV-UCB, the first no-regret algorithm for CVaR Bayesian optimization with unknown GP hyperparameters. Given a finite candidate set containing a well-specified model, HE-CV-UCB adaptively eliminates those inconsistent with the observed data, actively queries where the survivors disagree, and returns a design that is robust across the surviving candidates. We prove that it attains cumulative regret matching the oracle rate of CV-UCB up to a factor depending only on the candidate set's size. Across synthetic benchmarks and three real-world applications, HE-CV-UCB achieves competitive performance and frequently outperforms existing CVaR Bayesian optimization methods.
Valentin Margraf, Jonas Hanselle, Viktor Bengs +3
LMU Munich · Munich Center for Machine Learning (MCML) · German Research Center for Artificial Intelligence (DFKI) +3
Conditional Value-at-Risk (CVaR) is a widely used risk-sensitive objective for learning under rare but high-impact losses, yet its statistical behavior under heavy-tailed data remains poorly understood. Unlike expectation-based risk, CVaR depends on an endogenous, data-dependent quantile, which couples tail averaging with threshold estimation and fundamentally alters both generalization and robustness properties. In this work, we develop a learning-theoretic analysis of CVaR-based empirical risk minimization under heavy-tailed and contaminated data. We establish sharp, high-probability generalization and excess risk bounds under minimal moment assumptions, covering fixed hypotheses, finite and infinite classes, and extending to β-mixing dependent data; we further show that these rates are minimax optimal. To capture the intrinsic quantile sensitivity of CVaR, we derive a uniform Bahadur-Kiefer type expansion that isolates a threshold-driven error term absent in mean-risk ERM and essential in heavy-tailed regimes. We complement these results with robustness guarantees by proposing a truncated median-of-means CVaR estimator that achieves optimal rates under adversarial contamination. Finally, we show that CVaR decisions themselves can be intrinsically unstable under heavy tails, establishing a fundamental limitation on decision robustness even when the population optimum is well separated. Together, our results provide a principled characterization of when CVaR learning generalizes and is robust, and when instability is unavoidable due to tail scarcity.
Dept. of Mathematics, IISER, Pune. · Dept. of Computer Science and Automation, Indian Institute of Sciecne, Bangalore. · The Alan Turing Institute, Greater London, England, UK.
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