Score Function Gradient Estimation to Widen the Applicability ofDecision-focused Learning

Mattia Silvestri 1 Senne Berden 2 Jayanta Mandi 2 Ali İrfan Mahmutoğulları 2 Maxime Mulamba 2
Allegra De Filippo 1 Tias Guns 2 Michele Lombardi 1

Abstractof uncertain traffic conditions. These kinds of problems canbe framed as predict-then-optimize problems. As indicatedby their name, predict-then-optimize problems consist of
two stages – a prediction stage and an optimization stage.
In the prediction stage, a machine learning (ML) model isused to predict the unknown quantities. In the optimization
stage, the predicted quantities occur as parameters in an
optimization problem, which is solved by optimizing some
objective function while satisfying a set of domain-specificconstraints. Effective solving of predict-then-optimize problems hinges on the quality of the ML model used, and thus
the way this model is trained is highly important. Twoparadigms for doing so can be distinguished: predictionfocused and decision-focused learning.

Many real-world optimization problems contain
unknown parameters that must be predicted prior
to solving. To train the predictive machine learning (ML) models involved, the commonly adopted
approach focuses on maximizing predictive accuracy. However, this approach does not always
lead to the minimization of the downstream task
loss. Decision-focused learning (DFL) is a recently proposed paradigm whose goal is to train
the ML model by directly minimizing the task
loss. However, state-of-the-art DFL methods arelimited by the assumptions they make about thestructure of the optimization problem (e.g., thatthe problem is linear) and by the fact that can only
predict parameters that appear in the objectivefunction. In this work, we address these limitations by instead predicting distributions overparameters and adopting score function gradientestimation (SFGE) to compute decision-focused
updates to the predictive model, thereby widening
the applicability of DFL. Our experiments showthat by using SFGE we can: (1) deal with predictions that occur both in the objective function
and in the constraints; and (2) effectively tackle
two-stage stochastic optimization problems.

In prediction-focused learning (PFL) (also called two-stage
learning in (Wilder et al., 2019)), the predictive model istrained without considering the downstream optimization
problem. In other words, it is trained to maximize the accuracy of the predicted parameters, using traditional ML
losses like the mean squared error (MSE). While this may
appear entirely sensible at first – after all, higher predictive
accuracy generally leads to better decisions – it does nottake into account the complex ways in which prediction
errors affect the downstream decision-making.
To account for this, decision-focused learning (DFL) trains
the predictive model to directly minimize the task loss athand, i.e., some metric that depends on the outcome of the
optimization problem instantiated by the predicted parameters. This involves a deeper integration of the prediction andoptimization phases, as training the predictive model now requires backpropagation through the optimization procedure.
While this can be done exactly for convex optimization
problems through implicit differentiation (Agrawal et al.,2019; Amos & Kolter, 2017), it is more tricky when the
optimization problem is combinatorial. This is because,
when the parameters of a combinatorial optimization problem change, the solution either does not change at all, orchanges discontinuously. In other words, the partial derivatives of the solution with respect to the parameters are zeroalmost everywhere, and do not exist at the points where thesolution changes suddenly. This makes the straightforward

1. Introduction
Many real-world decision-making problems contain parameters that are uncertain at solving time. Consider, for example, a manufacturing company that needs to schedule its
production in function of uncertain customer demands, or adelivery company that needs to route its vehicles in function*
Equal contribution 1 Dipartimento di Informatica Scienza e
Ingegneria, University of Bologna, Bologna, Italy 2 Departmentof Computer Science, KU Leuven, Belgium. Correspondence to:
Mattia Silvestri <mattia.silvestri4@unibo.it>.

Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1SFGE to Widen the Applicability of DFL

application of gradient descent unhelpful in training.

The regret, however, is not appropriate when the predictedparameters also occur in the constraints. To this end, (Huet al., 2022) introduced the notion of post-hoc regret, which
is based on the use of a correction and a penalty function.
The correction function turns a solution z ⋆ (ŷ) that is infea⋆
sible with respect to y into a feasible one zcorr(ŷ, y), while⋆⋆
the penalty function P en(z (ŷ), zcorr (ŷ, y)) expresses thecost for doing so. Note that feasible solutions are mapped
onto themselves by the correction function, and that the associated penalty for this is 0. The post-hoc regret P Regret
captures the suboptimality of the corrected decisions, plus
the associated penalty:

To address this challenge, previous works (Elmachtoub &Grigas, 2022; Elmachtoub et al., 2020; Mandi & Guns, 2020;
Mandi et al., 2022; Mulamba et al., 2021; Shah et al., 2022;
Wilder et al., 2019) have proposed different techniques tostill obtain useful gradients. However, most works consider optimization problems where the predicted parameters
appear only in the objective function. This is a major limitation, as in many real-world problems, both the objective andconstraint functions contain uncertain parameters. Moreover, most methods are restricted to problems in which theobjective function is linear. These limitations in the stateof the art motivated us to develop a more widely applicable
methodology for DFL. More concretely, this paper investigates the use of score function gradient estimation (i.e.,the REINFORCE algorithm (Williams, 1992)) to learn topredict any parameters of an optimization problem (in theobjective, in the constraints, or both), regardless of whether
the objective function is linear or not. We also show how,
thanks to its generality, the method can effectively tackle
stochastic optimization problems, with consistent improvement over PFL approaches.

⋆
P Regret(ŷ, y) =f (zcorr(ŷ, y), y) − f (z ⋆ (y), y)⋆+ P en(z ⋆ (ŷ), zcorr(ŷ, y))Note that while we consider the post-hoc regret as task loss
in the experiments, our method does not depend on it andwill be formalized in function of an arbitrary task loss.

3. Score Function Gradient Estimation
The central problem in decision-focused learning is thatwhen the loss L depends on the outcome z ⋆ of a combinatorial optimization procedure, it has zero-valued gradientswith respect to the predictive model’s parameters almost
everywhere. This can be seen when applying the chain rule:

2. Problem setting
We consider a parametric optimization problem:z ⋆ (y) = arg min f (z, y)(1a)∂L(z ⋆ (ŷ), y) ∂z ⋆ (ŷ) ∂ ŷ∂L(z ⋆ (ŷ), y)=∂ω∂z ⋆ (ŷ)∂ ŷ ∂ωzs.t. g(z, y) ≤ 0(1b)h(z, y) = 0

(1c)

(4)

⋆

The second factor, ∂z∂ ŷ(ŷ) , measures the change in z ⋆ (ŷ)
when ŷ changes infinitesimally. However, since the problem
is combinatorial, this change is zero almost everywhere.
⋆
This in turn causes the entire gradient ∂L(z∂ω(ŷ),y) to be zeroalmost everywhere, and thus to be unhelpful in gradientbased learning.

The goal of the optimization problem is to find a solutionz ⋆ (y), a minimizer of the objective function f , that satisfies
a set of inequality and equality constraints defined by g andh, respectively. Parameter vector y is unknown, but can be
estimated as a function of some correlated known features
x. Given is a set of examples D = {(xi , yi )}N
i=1 . Thisis used to train a machine learning model mω that makes
predictions ŷ = mω (x).

To tackle this, we shift from training a model that makes
point predictions ŷ, to a model that predicts a vector θ that
instantiates a distribution pθ (y). In other words, instead ofpredicting parameter vectors, the model predicts distributions over parameter vectors. For instance, we consider y tobe sampled from a multivariate Gaussian distribution parameterized by its means µ and standard deviations σ, which
the predictive model is trained to predict, i.e., θ = (µ, σ).
The loss then becomes an expectation:

In the predict-then-optimize setting, the goal in training
the predictive model is not to maximize the accuracy ofŷ with respect to y. Rather, the goal is to learn to makepredictions ŷ that lead to good decisions z ⋆ (ŷ), with respect
to some task loss L. A common task loss is the regret(also called the SPO loss in (Elmachtoub & Grigas, 2022)),
which expresses the suboptimality of the decisions made on
the basis of the predicted parameters, with respect to theground-truth parameters:
Regret(ŷ, y) = f (z ⋆ (ŷ), y) − f (z ⋆ (y), y)(3)

L(θ, y) = Eŷ∼pθ (y) [L(ŷ, y)](5)

The motivation for this is that it removes the zero-gradientproblem: by predicting distributions, the gradient of the loss
with respect to the output of the predictive model is not zero
anymore. Despite overcoming differentiability via stochastic smoothing is not novel (Niepert et al., 2021), (Petersen,(2)

The regret is commonly used because most DFL work islimited to predicting parameters of the objective function.
2

SFGE to Widen the Applicability of DFL2022), (Berthet et al., 2020), (Abernethy et al., 2016), tothe best our knowledge, this is the first time it is applied in
the context of DFL. However, computing the gradient of
the loss is not trivial. To do so, we take inspiration fromthe field of reinforcement learning, where score function
gradient estimation (i.e., the REINFORCE algorithm) isused. Consider the following derivation:∇θ L(θ, y) = ∇θ Eŷ∼pθ (y) [L(ŷ, y)]Z= ∇θ pθ (y)L(ŷ, y)dŷZ= L(ŷ, y)∇θ pθ (ŷ)dŷZ= L(ŷ, y)pθ (ŷ)∇θ log pθ (ŷ)dŷ

We consider the knapsack problem (KP) wherein the item
weights are unknown. Since the predicted weights may leadto a solution that exceeds the capacity when considering
the ground-truth weights, a correction action is required torecover feasibility. In the case of the KP, this function discards a subset of the chosen items, for which an additional
cost is payed, whose value depends on a penalty coefficientρ. More precisely, for the i-th item, the cost for discarding
it is ρ · vi , where vi is the item value.

(6a)
(6b)

Table 1. PFL and SFGE results on the KP with uncertain weights
of size 50 for different penalty coefficient values.

(6c)

Method(6d)Rel. PRegret
ρ=1

PFL
SFGE

0.119 ± 0.014
0.103 ± 0.019

The validity of bringing the gradient inward in line 6c isdiscussed in (Mohamed et al., 2020). In line 6d, the log
derivative trick is used.

PFL
SFGE

0.259 ± 0.046
0.187 ± 0.069

To get an estimation of this gradient that can effectively be
used in training, the final result in line 6e can be estimatedusing a Monte Carlo method, giving

PFL
SFGE

0.435 ± 0.091
0.235 ± 0.078= Eŷ∼pθ (y) [L(ŷ, y)∇θ log pθ (ŷ)]

1X
L(ŷ (i) , y)∇θ log pθ (ŷ (i) )
S i=1

(6e)

0.33 ± 0.05
0.23 ± 0.06

ρ=50.33 ± 0.05
0.05 ± 0.03

ρ = 10S∇θ L(θ, y) ≈Infeas. ratio

0.33 ± 0.05
0.03 ± 0.03

We compare SFGE with a PFL approach that trains a ML
model to minimize the MSE. For each of the methods, wereport the relative post-hoc regret (Rel. PRegret) and theratio of infeasible solutions (Infeas. ratio), which expresses
how frequently the recourse action is used. We run experiments on three different KPs, all with 50 items , but withdiffering penalty coefficients ρ, namely ρ = {1, 5, 10}. We
generated synthetic data by introducing a mapping between
input features and targets in the same way as described in
the shortest path experimental evaluation of (Elmachtoub& Grigas, 2022), with a degree of model misspecification
deg = 5 and number, p = 5, of input features, and a noise
half-width ϵ̄ = 0.5. The results are shown in Table 1: SFGE
outperforms PFL in all the cases and it provides both better
relative regret and infeasibility ratio.

(7)with ŷ (i) ∼ pθ (y)with S as the total number of samples.
Note that the method is not specific to any loss function L.
For example, this can be the Hamming distance between
solutions z ⋆ (ŷ) and z ⋆ (y), the regret, or the post-hoc regret.
In our experiments, the latter is used.

4. Experimental Results
We conducted a preliminary analysis by focusing on two
main research questions: 1) Does SFGE outperform PFL
when predicting parameters that appear in the constraints?;
2) Does SFGE outperform PFL when predicting parametersof stochastic optimization problems?

Stochastic Optimization To assess the performance of
SFGE on stochastic optimization problems, we run experiments on the weighted set multi-cover problem (WSMC)
with stochastic coverage requirements(Hua et al., 2009). A
recourse action is employed whenever the demands are notsatisfied at the price of paying an additional cost whose
value depends on a penalty coefficient. More specifically,
the additional cost for each unit of not satisfied demandof the i-th product is computed as the maximum set costamong the ones that cover it, multiplied by the coefficientρ. We conducted the experimental analysis on synthetic
data that were generated following a set of guidelines thatallows us to obtain realistic instances. For the availability

Prediction of parameters in the constraints To the bestof our knowledge, the only work that tackles the problem
of predicting parameters in the constraints in a decisionfocused manner is (Hu et al., 2022) but it is limited to linear
packing and covering problems, and thus is not applicableto general integer linear programs. A wider applicable approach is proposed in (Paulus et al., 2021); however, themachine learning model is trained end-to-end to provide amore accurate solution rather than making decision-focused
prediction.
3

SFGE to Widen the Applicability of DFL

Despite that, PFL approaches can still be applied. While inprinciple one could train an ML model by minimizing theMSE, we devised a PFL approach that is more suitable ina stochastic optimization setup: we trained a probabilistic
model by maximum likelihood estimation. The probabilistic
model is a multivariate Gaussian distribution whose meansµ ∈ Rd are parameterized by a linear regression model,
and whose standard deviations σ ∈ Rd are a set of trainable but non-contextual parameters, where d is the numberof products. In Table 2, we report results for the WSMC
with 5 products and 25 items with different penalty values,ρ = {1, 5, 10}. Similarly to the previous problem, SFGE
achieved lower relative post-hoc regret and infeasibility ratio and the gap with PFL becomes larger when the problem
has a larger penalty coefficient.
For a more comprehensive comparison, we employed thesame probabilistic model in conjunction with the Sample
Average Approximation (SAA) algorithm (Kleywegt et al.,2002): we rely on the model to gather a set of instancespecific samples, which are subsequently used as scenariosin the SAA algorithm. This approach enables us to obtain a more robust solution. We refer to this pipeline as
PFL+SAA. In Figure 1, we show the relative post-hoc
regret and the normalized runtime at inference time in function of the number of sampled scenarios, for the WSMC
previously described and ρ = 10. The normalized runtime
expresses the relative slowdown in runtime at inference timewith respect to SFGE. As can be seen, when increasing
the number of scenarios, PFL+SAA improves in relative
regret, but at the price of a higher computational cost. As areference value, we also reported the relative post-hoc regretof SFGE, which does not involve sampling scenarios. Even
when 100 scenarios are employed, PFL+SAA does not outperform SFGE and, at the same time, has a computation
time at inference time that is at least one order of magnitudelarger.

Figure 1. The relative post-hoc regret and normalized runtime atinference time of SFGE and PFL+SAA on the WSMC

matrix, we follow the procedure described in (Grossman& Wool, 1997): every column covers at least one row andevery row is covered by at least two columns. The set costs
are randomly generated in the range [1, 100] with a uniform
probability distribution. Finally, we assume that the demands follow a Poisson distribution whose rate λ depends
on a set of correlated features. The ground-truth mapping
between features and rate is the same as the one previously
described for the KP, and was taken from (Elmachtoub &Grigas, 2022).
Table 2. PFL and SFGE results on the WSMC with 5 items and
25 sets for different penalty coefficient values.
MethodRel. PRegret

PFL
SFGE

1.18 ± 0.62
0.850 ± 0.264

PFL
SFGE

7.27 ± 4.20
2.53 ± 0.53

Infeas. ratio

ρ=1

5. Conclusions
0.63 ± 0.11
0.55 ± 0.27

This work aims to widen the applicability of decisionfocused learning to tackle predict-then-optimize problems
by proposing a method that does not suffer from the limitations of the state of the art. Concretely, we predict distributions over problem parameters, which circumvents thezero-gradient problem that occurs when the optimization
problem is combinatorial. To estimate the resulting non-zero
gradients, we employ SFGE. We showcased the effectiveness of the method on two problems of practical relevanceon which no other DFL approach can be applied, namely the
KP with unknown weights and the WSMC with unknown
stochastic coverage requirements. In a set of preliminary
experiments, SFGE demonstrated superior performance to
PFL in terms of both post-hoc regret and infeasibility ratio.

ρ=50.63 ± 0.11
0.23 ± 0.11

ρ = 10PFL
SFGE

17.8 ± 13.3
3.47 ± 1.73

0.63 ± 0.11
0.12 ± 0.06

To the best of our knowledge, the only work that proposesa method to tackle stochastic optimization problems in a
DFL fashion is (Donti et al., 2017); however it assumes the
problem is convex. This assumption restricts the applicability of the method, as numerous real-world problems are
non-convex, such as integer linear programs like the WSMC.
4

SFGE to Widen the Applicability of DFL

References

Mandi, J. and Guns, T. Interior point solving for lp-based
prediction+optimisation. In Larochelle, H., Ranzato, M.,
Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in
Neural Information Processing Systems, volume 33, pp.
7272–7282. Curran Associates, Inc., 2020.

Abernethy, J., Lee, C., and Tewari, A. Perturbation techniques in online learning and optimization. Perturbations,
Optimization, and Statistics, 233, 2016.
Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S.,
and Kolter, J. Z. Differentiable convex optimization layers. Advances in neural information processing systems,
32, 2019.

Mandi, J., Bucarey, V., Mulamba, M., and Guns, T.
Decision-focused learning: Through the lens of learning
to rank. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research,
pp. 14935–14947. PMLR, 17–23 Jul 2022.

Amos, B. and Kolter, J. Z. Optnet: Differentiable optimization as a layer in neural networks. In International
Conference on Machine Learning, pp. 136–145. PMLR,
2017.

Mohamed, S., Rosca, M., Figurnov, M., and Mnih, A.
Monte carlo gradient estimation in machine learning. J.
Mach. Learn. Res., 21(132):1–62, 2020.

Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.P., and Bach, F. Learning with differentiable pertubed
optimizers. Advances in neural information processing
systems, 33:9508–9519, 2020.

Mulamba, M., Mandi, J., Diligenti, M., Lombardi, M.,
Lopez, V. B., and Guns, T. Contrastive losses and solution caching for predict-and-optimize. In 30th International Joint Conference on Artificial Intelligence (IJCAI21): IJCAI-21, pp. 2833–2840. International Joint Conferences on Artificial Intelligence, 2021.

Donti, P., Amos, B., and Kolter, J. Z. Task-based end-to-end
model learning in stochastic optimization. Advances inneural information processing systems, 30, 2017.
Elmachtoub, A. N. and Grigas, P. Smart “predict, then
optimize”. Management Science, 68(1):9–26, 2022.

Niepert, M., Minervini, P., and Franceschi, L. Implicit
mle: backpropagating through discrete exponential family
distributions. Advances in Neural Information Processing
Systems, 34:14567–14579, 2021.

Elmachtoub, A. N., Liang, J. C. N., and Mcnellis, R. Decision trees for decision-making under the predict-thenoptimize framework. In III, H. D. and Singh, A. (eds.),
Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine
Learning Research, pp. 2858–2867. PMLR, 13–18 Jul
2020.

Paulus, A., Rolı́nek, M., Musil, V., Amos, B., and Martius,
G. Comboptnet: Fit the right np-hard problem by learning
integer programming constraints. In International Conference on Machine Learning, pp. 8443–8453. PMLR,
2021.

Grossman, T. and Wool, A. Computational experience withapproximation algorithms for the set covering problem.
European journal of operational research, 101(1):81–92,
1997.

Petersen, F. Learning with differentiable algorithms. arXiv
preprint arXiv:2209.00616, 2022.
Shah, S., Wang, K., Wilder, B., Perrault, A., and Tambe,
M. Decision-focused learning without decision-making:Learning locally optimized decision losses. In NeurIPS,
2022.

Hu, X., Lee, J. C. H., and Lee, J. H. M. Predict+optimize
for packing and covering lps with unknown parametersin constraints. CoRR, abs/2209.03668, 2022. doi: 10.
48550/arXiv.2209.03668. URL https://doi.org/
10.48550/arXiv.2209.03668.

Wilder, B., Dilkina, B., and Tambe, M. Melding the datadecisions pipeline: Decision-focused learning for combinatorial optimization. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, pp. 1658–
1665. AAAI Press, 2019.

Hua, Q.-S., Yu, D., Lau, F. C., and Wang, Y. Exact algorithms for set multicover and multiset multicover problems. In Algorithms and Computation: 20th International
Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings 20, pp. 34–44. Springer,
2009.

Williams, R. J. Simple statistical gradient-following
algorithms for connectionist reinforcement learning.
Mach. Learn., 8:229–256, 1992.
doi: 10.1007/
BF00992696. URL https://doi.org/10.1007/
BF00992696.

Kleywegt, A. J., Shapiro, A., and Homem-de Mello, T.
The sample average approximation method for stochastic
discrete optimization. SIAM Journal on Optimization, 12(2):479–502, 2002.
5

SFGE to Widen the Applicability of DFL

A. Additional results
For a more comprehensive analysis, we provide additional results for larger sizes of the KP with uncertain weights andthe WSMC. When compared to the sole PFL, we can draw similar conclusions as for the smaller size problems: SFGE
always outperforms PFL in terms of both the relative post-hoc regret and infeasibility ratio; moreover, the gap becomes
more evident with the increasing of the penalty coefficient value.
Table 3. PFL and SFGE results on the KP with uncertain weights of size 75 for different penalty coefficient values.
MethodRel. PRegret

PFL
SFGE

0.115 ± 0.017
0.114 ± 0.014

PFL
SFGE

0.247 ± 0.048
0.214 ± 0.058

PFL
SFGE

0.440 ± 0.091
0.251 ± 0.064

Infeas. ratio

ρ=10.31 ± 0.05
0.20 ± 0.04

ρ=50.31 ± 0.05
0.04 ± 0.02

ρ = 100.31 ± 0.05
0.03 ± 0.02.
Table 4. PFL and SFGE results on the WSMC with 10 items and 50 sets for different penalty coefficient values.
MethodRel. PRegret

Infeas. ratio

ρ=1
PFL
SFGE

2.35 ± 0.85
1.94 ± 0.50

0.98 ± 0.01
0.94 ± 0.05

ρ=5
PFL
SFGE

12.17 ± 4.73
4.87 ± 1.15

0.98 ± 0.01
0.64 ± 0.08

ρ = 10PFL
SFGE

22.41 ± 7.90
7.08 ± 1.29

6

0.98 ± 0.01
0.54 ± 0.14

SFGE to Widen the Applicability of DFL

When compared to PFL+SAA, SFGE probes its efficiency in terms of computational cost at inference time. PFL+SAA
provides better relative post-hoc regret but it requires sampling a non-negligible number of scenarios. This is especiallyvisible when ρ = 10: even if the post-hoc regret is slightly improved, 100 scenarios are sampled at the price of more than 50
times the computational time of SFGE.

Figure 2. Comparison between SFGE and PFL+SAA on the WSMC of size 5 × 25.

Figure 3. Comparison between SFGE and PFL+SAA on the WSMC of size 10 × 50.

7