Introduction: The Pitfalls of Empirical Regret
Decision-Focused Learning (DFL), often referred to as "predict-then-optimize," integrates machine learning predictions directly into optimization frameworks. The standard training objective is to minimize empirical regret: the difference in objective value between a decision based on predicted parameters and the optimal decision based on ground-truth parameters.
However, empirical regret is often a poor surrogate for the true objective of minimizing expected regret. Because optimization landscapes are frequently non-smooth or discrete, small prediction errors can trigger drastic shifts in the optimal decision. This leads to two primary challenges:
- Epistemic Uncertainty: Poor generalization when training data is sparse.
- Aleatoric Uncertainty: A "biased learning" trap where the model overfits to high-variance, noisy parameters rather than learning the underlying mean.
Proposed Robust Loss Functions
To mitigate these issues, the authors introduce three robust loss functions that stabilize the training signal by modifying the "target" decision used in the regret calculation.
1. Robust Optimization (RO) Loss
The RO loss replaces the standard optimal decision with a robust optimal decision. This decision is designed to remain effective across a range of possible parameter values within a defined uncertainty set. By comparing predictions against a decision that accounts for worst-case scenarios, the model becomes less sensitive to individual noisy realizations.
2. Top-k Loss
Instead of penalizing the model based on a single "perfect" decision, the Top-k loss averages regret across the top $k$ best decisions for a given scenario. This approach smooths the loss landscape, providing a more consistent gradient for neural network optimizers and preventing the model from converging to narrow, unstable local optima.
3. k-Nearest Neighbor (k-NN) Loss
The k-NN loss leverages local structure in the feature space. It identifies the $k$ closest historical neighbors to the current input and averages their objective realizations. This effectively "denoises" the target signal, allowing the model to focus on the conditional mean of the parameters rather than being distracted by outliers.
A significant advantage of these methods is that the robust targets can be precomputed. Consequently, they provide improved decision quality with zero additional computational overhead during the training epochs.
Experimental Evaluation
The researchers benchmarked these losses against state-of-the-art DFL methods across three domains: synthetic shortest path problems, the Traveling Salesperson Problem (TSP), and a real-world energy-cost aware scheduling task.
Key Results
- Improved Generalization: In low-data regimes, robust losses outperformed standard empirical regret in approximately 67% of experimental comparisons.
- Consistency of k-NN: The k-NN loss proved to be the most robust across various noise levels, effectively filtering out aleatoric uncertainty by looking at similar historical contexts.
- Combinatorial Complexity: For the TSP, the Top-k loss was particularly effective, suggesting that exploring a neighborhood of high-quality solutions is superior to targeting a single, potentially noisy optimum in complex discrete spaces.
Conclusion
This work demonstrates that "chasing" the empirical optimum in DFL is often counterproductive. By incorporating robustness—either through uncertainty sets, neighborhood averaging, or local feature smoothing—models can achieve significantly better decision performance in uncertain environments. These robust losses serve as a practical, drop-in replacement for existing DFL pipelines, offering superior performance without increasing training time.
Summary updated