Organizations: School of Architecture, Building and Civil Engineering, Loughborough University, UK · Department of Computer Science, KU Leuven, Leuven, Belgium · Institute of Engineering Sciences, Universidad de O’Higgins, Rancagua, Chile · Department of Statistics and Operations Research, Universidad de Murcia, Murcia, Spain
Many combinatorial optimization (CO) problems involve parameters that are uncertain when the problem must be solved. In such settings, the parameters have to be predicted from correlated contextual information before a solution can be computed. Decision-focused learning (DFL) addresses this by training the predictive model to produce predictions that optimize downstream decision quality. Most existing DFL methods are risk-neutral and minimize the expected regret. In high-stakes applications this can lead to undesirable outcomes, because decision-makers must also account for the tail risk of decision quality. Prior risk-sensitive approaches typically model uncertainty explicitly and solve a stochastic or robust optimization problem at inference time, which increases computational complexity. We instead propose a DFL framework that achieves risk-sensitive behavior while retaining point predictions and deterministic optimization at inference time. Starting from the dual representation of the Conditional Value-at-Risk (CVaR) and adding entropy regularization, we derive a smooth surrogate for the CVaR of regret. Its gradient induces an instance-dependent reweighting within each minibatch that emphasizes high-risk outcomes, so the approach can turn existing surrogate-loss DFL methods, including the SPO+ loss, into risk-sensitive variants. When instantiated with SPO+, the resulting objective admits a generalization bound on the CVaR of the true regret. Experiments on knapsack, portfolio, shortest-path, and energy-aware scheduling problems show substantial reductions in tail regret when the uncertain parameters exhibit heterogeneous tail behavior.
Figures & tables
Case 1
Case 2
A
B
A
B ′
Travel time, normal scenario ( p=0.9 )
30
20
30
40
Travel time, rare scenario ( p=0.1 )
30
60
30
5
Regret, normal scenario
10
0
0
10
Regret, rare scenario
0
30
25
0
\CVaR0.9 of travel time
30
60
30
40
Table 1: Travel times and regrets (in minutes) in the illustrative example. Bold entries mark the route preferred by each CVaR objective.
Problem
Data
Method
Batch size
β
Learning rate
Portfolio (50 assets)
Heterogeneous
MSE
32
–
0.005
Heterogeneous
SPO+
128
–
0.005
Heterogeneous
RESTROSPO+ (exact η )
128
50
0.005
Heterogeneous
RESTROSPO+ (quantile η )
128
10
0.005
Homogeneous
MSE
128
–
0.005
Homogeneous
SPO+
64
–
0.005
Table 2: Selected Hyperparameters for Each Problem, Dataset, and Method.
Problem
MSE
SPO+
RESTROSPO+ (exact η )
RESTROSPO+ (quantile η )
Portfolio
0.00±0.00
0.00±0.00
0.00±0.00
0.00±0.00
Shortest path
0.53±0.11
0.38±0.07
0.38±0.06
0.39±0.07
Knapsack
2.30±0.30
1.61±0.07
1.61±0.11
1.62±0.09
Table 3: CVaR0.9 of Regret on the PyEPO Datasets with Homogeneous Cost Vectors.
Problem
MSE
SPO+
RESTROSPO+ (exact η )
RESTROSPO+ (quantile η )
Portfolio
0.43±0.01
0.42±0.01
0.39±0.01
0.39±0.01
Shortest path
5.36±0.83
11.04±0.96
4.99±0.63
5.07±0.55
Knapsack
10.73±1.50
20.54±5.11
8.18±0.84
8.07±0.90
Table 4: CVaR0.9 of Regret on the Datasets with Heterogeneous Long-Tail Cost Vectors.
Heterogeneous
Homogeneous
Problem
Method
CVaR0.9
Time (s)
CVaR0.9
Time (s)
Shortest path
MSE
5.36±0.83
2.11±0.04
0.53±0.11
2.28±0.07
SPO+
11.04±0.96
10.09±0.33
0.38±0.07
10.54±0.31
RESTROSPO+ (exact η )
4.99±0.63
11.41±0.85
0.38±0.06
11.67±0.85
RESTROSPO+ (quantile η )
5.07±0.55
10.37±0.17
0.39±0.07
10.11±0.20
Knapsack
MSE
10.73±1.50
7.38±0.78
2.30±0.30
7.67±0.53
Table 5: Exact Threshold ηβ⋆ Versus Quantile Approximation ηα : CVaR0.9 of Regret and Training Time (s).
Heterogeneous
Homogeneous
Problem
η
Normalized
CVaR0.9
Time (s)
CVaR0.9
Time (s)
Shortest path
Exact
No
4.99±0.63
11.41±0.85
0.38±0.06
11.67±0.85
Exact
Yes
5.02±0.56
10.67±0.05
0.39±0.07
10.27±0.06
Quantile
No
4.99±0.42
10.08±0.09
0.39±0.07
10.12±0.07
Quantile
Yes
5.07±0.55
10.37±0.17
0.39±0.07
10.11±0.20
Knapsack
Exact
No
8.18±0.84
29.38±4.16
1.61±0.11
38.22±3.58
Table 6: Effect of Normalizing the Losses by the Threshold: CVaR0.9 of Regret and Training Time (s) of RESTROSPO+ .
Data
Method
CVaR0.9
Time (s)
Original
MSE
166,331.07
35.90
SPO+ (cached)
159,213.45
98.10
SPO+ (non-cached)
159,032.17
1,102.86
RESTROSPO+ (exact η )
157,237.15
106.83
RESTROSPO+ (quantile η )
157,176.50
97.88
Heterogeneous
MSE
242,105.05
35.41
Table 7: Energy-Aware Scheduling with 10 Tasks: CVaR0.9 of Regret and Training Time (s).