Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities

In plain words

Many decisions, such as which route to drive, which items to pack or when to run a machine, start from a guess about some numbers: travel times, prices or values. The usual recipe trains a model to make its guesses as accurate as possible, then hands them to a solver that picks the best decision. The catch is that a guess can be far off in a place that does not change the decision, and slightly off in a place that flips it.

Decision-focused learning trains the model on the quality of the final decision instead. The model's guesses go through the solver, and the training signal says how much worse the resulting decision is than the best one that could have been made with the true numbers. The difficulty is that a solver's answer jumps when its inputs change slightly, so the usual gradient is zero almost everywhere. This survey explains the workarounds, compares eleven of them on seven problem sets, and releases code. The results are mixed: no method wins everywhere, some are steady, some are cheap, and some break on certain constraint types.

TL;DR

• A survey plus a benchmark. Decision-focused learning (DFL) trains a model to minimise the regret of the decision a solver returns, instead of the error of its predictions §2.2.
• The gradient problem is the central obstacle. Methods are grouped into gradient-based ones (analytical differentiation, analytical smoothing, random perturbation, surrogate losses) and gradient-free ones §3.
• Benchmark: 11 methods on 7 problem sets, with test regret over 10 seeds. Results are shown only as box plots; the text gives qualitative rankings §5.
• The text calls SPO consistently robust and says the cache-based losses are much cheaper to train §5.2.3.
• Several settings in the paper do not match its repository. Read the Paper vs code section before reproducing.

Problem

Decisions are modelled as a parametric combinatorial optimisation problem whose objective depends on a cost vector c. The constraints are assumed known. The cost vector is unknown and is predicted from features z by a model m_ω, which gives ĉ. The decision is x*(ĉ), and it is scored on the true c §2.1.

Prediction-focused learning (PFL) trains m_ω on a prediction loss such as MSE or BCE. Decision-focused learning trains it on a task loss, most often regret: the true objective of the chosen decision minus the true optimum §2.2. The paper's own argument is that small prediction errors can change the decision and large ones often do not, so the two losses need not agree §2.2.

Three obstacles follow §2.3:

• the map c → x*(c) has no closed form;
• for linear programs and integer programs the map is piecewise constant, so its derivative is zero almost everywhere and does not exist at the breakpoints;
• every training step must solve and differentiate the problem, which is costly for hard problems.

Regret needs the true costs c at training time. The surrogate losses in §3.1.4 therefore do not apply when only optimal decisions are observed §3.1.4. The paper's benchmark, however, includes one subset-selection task trained on decisions alone, and uses a task loss that does not need c §5.1.

Method

Training objective

PFL minimises the prediction error directly. It is a standard regression step, shown as alg. 1 in §2.3 §2.2.

DFL is written as a bilevel empirical risk problem: the outer level minimises the average regret over the training set, and the inner level is the solver applied to ĉ_i = m_ω(z_i) §2.2. Gradient descent needs the chain rule dL/dω = (dL/dx̂)(dx̂/dĉ)(dĉ/dω). Autodiff handles the last factor. The middle factor is the problem, and the methods below each supply a substitute for it alg. 2 §2.3.

# Gradient descent for DFL, regret as the task loss  [alg. 2]
# Input: data (z, c, x_star) with x_star = x*(c); learning rate lr
# Output: trained predictor weights w

def train_dfl(w, data, lr, epochs):
    # Repeat over the training set  [alg. 2]
    for epoch in range(epochs):
        for z, c, x_star in data:
            # Predict the cost vector from the features  [§2.2]
            c_hat = predict(w, z)
            # Solve the problem with the predicted costs  [§2.2]
            x_hat = solve(c_hat)
            # Regret of x_hat under the true costs (linear objective)  [§2.2]
            loss = dot(c, x_hat) - dot(c, x_star)
            # Substitute for dx_hat/dc_hat, which is zero almost everywhere
            # for LPs and ILPs  [§2.3] [§3.1]
            grad_c_hat = surrogate(c_hat, c, x_star, loss)
            # Chain rule through the predictor  [alg. 2]
            w = w - lr * backprop(grad_c_hat, w)
    return w

Taxonomy of gradient-based methods

The paper sorts gradient-based DFL into four classes §3.1. tab. 1 summarises which problem forms each technique supports, how it obtains a gradient, and whether it yields a differentiable optimisation layer that can sit anywhere in a network.

Source: tab. 1. Section numbers are the paper's; the table itself lists the technique and its gradient in a compact form.

Two ideas recur. First, smoothing: LPs are made differentiable by a quadratic term §3.1.2, a log-barrier §3.1.2, or random perturbations of the costs §3.1.3. Second, surrogate losses that never call the solver in the backward pass §3.1.4.

The eleven benchmarked methods

The benchmark uses these names §5.2. Pseudocode follows the paper's equations; the code differences are in Paper vs code.

• PF: the prediction-focused baseline, trained with MSE (BCE for matching) §5.2.
• SPO §3.1.4: the SPO+ subgradient, which uses two solver calls.
• DBB §3.1.3: a finite difference of the solver at a costs vector nudged by the loss gradient.
• I-MLE §3.1.3: a finite difference with noise added to the costs.
• FY §3.1.3: the gradient of the perturbed Fenchel-Young loss.
• HSD (Intopt) §3.1.2: an LP with a log-barrier term, differentiated through its self-dual embedding.
• QPTL §3.1.2: an LP with a quadratic term, differentiated as a QP; the quadratic term is removed at test time.
• Listwise, Pairwise, Pairwise (diff) and MAP §3.1.4: losses over a cache of feasible solutions. The cache starts from the training optima and grows by solving on a fraction p_solve of steps (5% in the benchmark) §5.2.

The paper's four solution-cache losses are shown below. The cache S holds feasible solutions, including the true optimum x*(c).

# Listwise loss over the solution cache  [§3.1.4]
# cache: (|S|, n) feasible solutions, including the true optimum
# tau: temperature

def listwise_loss(c_hat, c, cache, tau):
    # Cost of every cached solution under true and predicted costs  [§3.1.4]
    costs_true = cache @ c
    costs_hat = cache @ c_hat
    # Tempered-softmax probabilities over the cache  [§3.1.4] [tab. 1]
    p_true = softmax(-costs_true / tau)
    log_p_hat = log_softmax(-costs_hat / tau)
    # Cross-entropy averaged over the cache entries  [§3.1.4]
    return -mean(p_true * log_p_hat)

# Pairwise losses: the true optimum against each cached rival  [§3.1.4]
# x_star: index of the true optimum in the cache; margin: Theta

def pairwise_loss(c_hat, c, cache, x_star, margin):
    # Gap in predicted cost between the optimum and each rival  [§3.1.4]
    gap_hat = dot(cache[x_star] - cache, c_hat)
    # Hinge: zero once the optimum wins by at least the margin  [§3.1.4]
    return sum(max(0, margin + gap_hat))

def pairwise_diff_loss(c_hat, c, cache, x_star):
    # Predicted and true gaps for each rival  [§3.1.4]
    gap_hat = dot(cache[x_star] - cache, c_hat)
    gap_true = dot(cache[x_star] - cache, c)
    # Penalise the difference between the two gaps  [§3.1.4]
    return sum((gap_hat - gap_true) ** 2)

# MAP contrastive loss with (c_hat - c) as the cost  [§3.1.4] [§5.1]
# The benchmark uses this linear-objective form, not the solver form

def map_loss(c_hat, c, cache, x_star):
    # Gap to each rival, weighted by the cost error (c_hat - c)  [§3.1.4]
    gaps = dot(cache[x_star] - cache, c_hat - c)
    # Keep the hardest rival in the cache  [§3.1.4]
    return max(gaps)

SPO, DBB, I-MLE and FY work with the solver directly, and their estimators are short enough to state in full.

# SPO subgradient with respect to the predicted costs  [§3.1.4]
# solve(c) returns an optimal decision for costs c

def spo_gradient(c_hat, c):
    # Optimal decision under the true costs  [§3.1.4]
    x_star = solve(c)
    # Decision under the perturbed costs 2 * c_hat - c  [§3.1.4]
    x_perturbed = solve(2 * c_hat - c)
    # Subgradient of the SPO+ surrogate  [§3.1.4]
    return x_star - x_perturbed

# Blackbox differentiation (DBB)  [§3.1.3]
# dL_dx: gradient of the task loss at x_hat; delta: step size

def dbb_gradient(c_hat, dL_dx, delta):
    # Decision with the costs nudged against the loss gradient  [§3.1.3]
    x_nudged = solve(c_hat + delta * dL_dx)
    # Decision with the unchanged predicted costs  [§3.1.3]
    x_hat = solve(c_hat)
    # Finite difference as written in the paper; the code also divides
    # by delta (see Paper vs code)  [§3.1.3]
    return x_nudged - x_hat

# I-MLE: finite difference with noise  [§3.1.3]
# eta: one noise sample; delta: step size; eps: noise scale

def imle_gradient(c_hat, dL_dx, delta, eps, eta):
    # Decision with the nudged and noisy costs  [§3.1.3]
    x_nudged = solve(c_hat + delta * dL_dx + eps * eta)
    # Decision with the noisy costs  [§3.1.3]
    x_noisy = solve(c_hat + eps * eta)
    return x_nudged - x_noisy

# Fenchel-Young gradient from perturbed optimisers  [§3.1.3]
# eps: noise scale; samples: number of noise draws M

def fenchel_young_gradient(c_hat, c, eps, samples):
    # Average the decisions over randomly perturbed predicted costs  [§3.1.3]
    x_bar = 0
    for m in range(samples):
        # Draw one perturbation from the noise density  [§3.1.3]
        eta = draw_noise()
        x_bar = x_bar + solve(c_hat + eps * eta) / samples
    # True decision minus the perturbed average  [§3.1.3]
    return solve(c) - x_bar

Solution cache

The cache is the cheap route to a solver-free loss. The benchmark seeds it with the optima of the training set test_sp.py and grows it with probability p_solve on each step §3.1.4 §5.2. The paper describes the coin as tossed per instance. The code tosses it once per mini-batch and then solves the whole batch; see Paper vs code.

Hyperparameters

Shared across the benchmark, as stated in the paper §5.2:

• Optimiser: Adam with ReduceLROnPlateau. The learning rate is tuned per method and per setting.
• Grid search on validation regret. The setting with the lowest average validation regret wins. Each setting is run for seeds 0 to 9 §5.2.
• Grid tab. 3:

Source: tab. 3. Values above are as printed in the paper. Several chosen values in the repository fall outside these ranges (see Paper vs code).

Optimal values per setting are not in the compiled paper. The appendix says they are in the repository app. C, and the LaTeX source contains tables that are wrapped in \iffalse, so they are not in the published PDF. The tables below use the repository's config.json files, which match those unpublished tables except where Paper vs code says otherwise.

Key mapping. The paper's symbols and the code keys differ:

• lr is the learning rate.
• lambda_val (DBB) is the step size. The paper's text calls it δ, and its table calls it λ PO_modelsSP.py.
• beta (I-MLE) is passed as the beta of the target distribution, which the paper's table calls λ PO_modelsSP.py.
• temperature (I-MLE) is the noise scale ε.
• k (I-MLE) is the sum-of-gamma shape κ. The paper never defines κ; the code uses k in SumOfGammaNoiseDistribution noise.py.
• sigma (FY) is the noise scale ε of Gumbel perturbations PO_modelsSP.py.
• thr and damping (IntOpt, the HSD method): thr is μ, the log-barrier parameter; damping is the damping term. The mapping is inferred from the values, which match the paper's HSD column.
• mu (DCOL, the QPTL method) is μ.
• tau in Listwise is τ, the temperature. In Pairwise the code passes tau as the margin Θ, not as a temperature PO_modelsSP.py.
• noise is the noise half-width ϑ, and deg is the degree of misspecification. Both come from the data generator described in §5.1.

Other settings, from the code and not the paper (defaults or per-file flags):

• Batch size 128, the default in the shortest-path driver test_sp.py and Warcraft TestWarcraft.py. The paper does not state it.
• Maximum epochs: 30 for shortest path test_sp.py, 70 for Warcraft TestWarcraft.py, 35 for knapsack testknapsack.py. The paper does not state them.
• Minimum epochs: 5 for shortest path test_sp.py, 1 for knapsack and Warcraft.
• L1 penalty weight 1e-5 added to every loss test_sp.py. The paper does not mention it.
• p_solve (growth) 0.05 test_sp.py.
• Scheduler is off unless --scheduler True is passed. The readmes pass it for every problem except Warcraft test_sp.py readme.md readme.md.

Per-setting values, from the repository. Empty cells mean the method is not in that config file.

Shortest path 5×5 grid, ShortestPath/config.json, N = 1000, noise 0.5. Columns are Deg 1, 2, 4, 6, 8 config.json:

The file has no entries for PF, SPO, DBB, I-MLE, FY or MAP on this problem, although the paper reports all of them §5.2.1. See Paper vs code.

Portfolio optimisation, Portfolio/config.json, N = 1000, noise 1. Columns are Deg 1, 4, 8, 16. There is no HSD, which the paper excludes because of quadratic constraints §5.2.1 config.json:

Warcraft shortest path, warcraft/config.json. Columns are image sizes 12, 18, 24 and 30. There is no HSD or QPTL, which the paper could not run §5.2.1 config.json:

Energy-cost aware scheduling, Energy/config.json. Columns are instances 1, 2 and 3, which the paper describes as having 10, 15 and 20 tasks §5.2.1. The config includes HSD here, although the scheduling problem is an ILP and HSD is run on its LP relaxation §5.2.1 config.json:

Knapsack, Knapsack/config.json. Columns are capacities 60, 120 and 180 config.json:

Bipartite matching, Matching/config.json. Columns are instances 1, 2 and 3. The paper lists the diversity settings (ρ1, ρ2) as (10%, 10%), (25%, 25%) and (50%, 50%) §5.2.1. The config does not link the instance index to these settings; this card assumes the same order config.json:

The subset-selection experiment has no folder in the repository, so its settings cannot be checked against code §5.2.1 README.md.

Results

All numbers are author-reported. Test regret is relative (regret divided by the true objective of the optimum), averaged over 10 seeds, and drawn as box plots §5.2. For the portfolio problem, where relative regret is undefined for some instances, absolute regret is used instead §5.2.1. The text gives qualitative rankings and no regret values. Read the figures for the numbers.

Training time per epoch on energy scheduling §5.2.2 fig. 12:

• PF has the lowest training time because it never solves the problem during training.
• SPO, DBB, I-MLE and FY take about 100 times as long as PF.
• Listwise, Pairwise, Pairwise (diff) and MAP, run with p_solve = 5%, are much faster than the other DFL methods.
• Gurobi solves one knapsack instance in about 0.001 s and the hardest scheduling instance in about 0.1 s §5.2.2.

Summary claims from the discussion §5.2.3:

• SPO is described as consistently robust across problems, though not the best in every experiment.
• I-MLE, FY, DBB and QPTL do worse than PF on the portfolio problem, which has a quadratic constraint.
• QPTL does well when its LP relaxation is close to the ILP (matching, knapsack) and poorly when it is not (scheduling).
• MAP is consistent across most problems. The paper suggests it for large problems, because it is cheap and its regret is close to SPO's.
• Listwise and Pairwise have high variance. Pairwise (diff) has lower variance.

Paper vs code

The code is MIT-licensed and pinned to commit 1a8e048c5aa640f73a05e29878b8e1e8f6f73610. It covers six problem folders. The subset-selection experiment has no folder. The shortest-path and portfolio data are downloaded from a DOI, and their generators are not in the repository readme.md readme.md.

1. DBB gradient scale. The paper's finite difference has no division by δ §3.1.3. The code returns the difference divided by the step size diff_layer.py. Verify which one you implement.
2. Pairwise sums. The paper sums the pairwise hinge and the squared difference over every x′ in S §3.1.4. The code takes one representative per distinct true cost, found with np.unique, and compares only those CacheLosses.py CacheLosses.py. This changes the loss value and its scale.
3. Cache growth. The paper tosses a coin per instance §3.1.4. The code tosses once per mini-batch, and when the coin succeeds it solves the whole batch PO_modelsSP.py utils.py.
4. Loss scale. The ranking losses already divide by the batch size CacheLosses.py CacheLosses.py CacheLosses.py, and the cached training step divides again by the batch size before adding the L1 term PO_modelsSP.py. The paper does not mention this. Adam largely cancels a uniform gradient scale, but the L1 term is not divided, so its weight relative to the data term is larger than a single division would give, by a factor equal to the batch size.
5. L1 penalty. Every model adds an L1 penalty with weight 1e-5 by default test_sp.py PO_modelsSP.py. The paper does not mention it.
6. Checkpoint selection. The checkpoint callback's monitor is commented out test_sp.py. The Lightning documentation says that without a monitor only the last epoch is saved. The repository pins Lightning 1.6.4 requirements.txt. The shortest-path driver may therefore evaluate the final-epoch model rather than the best-validation one. Verify this for 1.6.4 before relying on it.
7. Scheduler. The paper says ReduceLROnPlateau is used. The scheduler is off by default and is enabled with the --scheduler flag test_sp.py PO_modelsSP.py. The readmes pass --scheduler True.
8. Shortest-path config coverage. ShortestPath/config.json has entries only for HSD and the three ranking losses. The paper reports results for all eleven methods on this problem §5.2.1.
9. Values outside the paper's grid. Several chosen values fall outside tab. 3. Listwise τ takes 0.01 and 0.005 in portfolio, 0.001 and 0.0001 in knapsack and 50 in matching. Θ takes 0.5 and 5. HSD μ (thr) takes 0.001 and 1e-06 in shortest path and energy. FY ε takes 0.005 and 0.01 in several problems. QPTL μ takes 100 in matching. These contradict the stated ranges config.json config.json config.json config.json config.json.
10. Unpublished table versus config. The LaTeX source contains an appendix table, inside \iffalse, that the published PDF does not show. For most entries it matches config.json. Two entries do not. Matching DBB at instance 3 is λ = 1.0 in the table and 0.1 in the config. Matching Listwise at instance 3 is τ = 5.0 in the table and 50.0 in the config config.json. The table also gives DBB on portfolio as (lr, λ) = (1.0, 0.1), while the config has lr 0.1 and λ 1.0 config.json. This card uses the config values.
11. Positivity in Warcraft. The paper says a ReLU keeps predicted costs positive §5.1. The network has no output activation. Its output is the channel mean of the first residual stage, whose last operation is a ReLU, so the output is non-negative computervisionmodels.py. The effect is the same, but the stated mechanism differs.
12. Knapsack features. The paper says each item has eight features and does not mention standardisation §5.1. The code drops the first feature column, standardises, and splits 550 training, 100 validation and the rest as test data_utils.py.
13. Portfolio formulas. The covariance uses ζ where the noise magnitude ϑ is defined, and the factor matrix L is written as n×4, probably meaning d×4 §5.1. The generator is not in the repository, so these cannot be checked.
14. I-MLE parameter κ. The paper never defines it §5.2. The code uses it as the sum-of-gamma shape parameter noise.py.

Pitfalls

• Zero gradients. Plain autodiff through a solver gives zero gradients almost everywhere for LPs and ILPs §2.3. Every method here replaces the true derivative with a surrogate, so the choice of surrogate is the choice of method.
• Surrogates need true costs. The regret-based surrogates need c, not just x*(c). Decision-only data needs a different loss §3.1.4.
• Ties. With predicted costs at zero, every feasible solution is optimal. The benchmark assumes the solver breaks ties in a fixed way §5.2. Check your solver's tie-breaking before comparing numbers.
• Relative regret is undefined when the true optimum has zero objective, which happens in portfolio when every return is negative §5.2.1. Use absolute regret there.
• Relaxations can fail. QPTL and HSD solve an LP relaxation of an ILP. That works for knapsack and matching and fails for energy scheduling, because the relaxed solution can differ a lot from the integer one §5.2.3.
• Quadratic constraints. HSD cannot take quadratic constraints. Several gradient methods, including I-MLE, FY, DBB and QPTL, do worse than PF on portfolio §5.2.3.
• Solver cost dominates. In the energy benchmark, SPO, DBB, I-MLE and FY take about 100 times as long per epoch as PF. The cached losses sit between PF and these methods §5.2.2.
• Hyperparameter sensitivity. The grid spans several orders of magnitude for learning rate, damping and μ, and the optimum changes by setting tab. 3 config.json. Re-tune when you change the problem size or the solver.
• Warcraft text contradicts itself. The text says Listwise is best for sizes 12, 18 and 30, and also that SPO is best for 30 §5.2.1. Check the figure before citing a winner.
• Runtime numbers are subject to system overhead, as the paper itself warns §5.2.2. Only the ratios are meaningful.
• Gradient-free methods are surveyed §3.2 but not benchmarked. The benchmark covers gradient-based methods only §5.2.
• DBB step. The paper and the code differ by a division by the step size (see Paper vs code, item 1). Pick one and state it.

Lineage

• Builds on: the earlier methods the paper reviews in §3, among them SPO, DBB, I-MLE, Fenchel-Young and DPO, OptNet, cvxpylayers, Intopt and QPTL. Each is cited there by name only. No arXiv ids are given because none were checked.
• Compared against: the eleven methods above, benchmarked on seven problem sets §5.2.
• Superseded by: not known from this card's sources.