Train decision models without known optimal decisions or derivatives
PolyStepOR: Learning to Decide Without Optimal Decisions
Machine Learning
Summary
Sometimes computers need to make decisions, but it is hard or expensive to find the very best choice to learn from. The authors created PolyStepOR, a new way to train decision-making models by using feedback from the decisions actually made, rather than needing the perfect solution first. PolyStepOR tweaks the model slightly and checks how the decision changes, learning which direction improves the outcome without needing complex calculations. Their method works well on standard test problems and some real-world tasks, even when the usual best answers aren't available.
What this means in practice
- •For supply chain planners: Optimize supply decisions when exact best solutions are unavailable or costly to compute.
- •For energy grid operators: Improve real-time management by learning from actual operational costs without pre-computed optimal setups.
Authors
Viet The Nguyen, Gunther Gust, An Thai Le
Abstract
Decision-focused learning (DFL) trains predictors for downstream decision quality, but often relies on optimal reference decisions that are expensive to obtain. We present PolyStepOR, which trains directly from realized decision costs without pre-computed optima and extends to in-constraint predictions through repair or infeasibility penalties. To handle piecewise-constant losses, PolyStepOR perturbs predictor parameters, evaluates the resulting decisions, and uses optimal transport to favor lower-cost directions, requiring no derivatives. Without task-specific tuning, PolyStepOR performs strongly on classical optimization benchmarks and competitively on predicted-constraint and real-world problems. Theoretically, we characterize decision-preserving perturbations and boundary detection, bound sensitivity to cost errors, and establish stationarity guarantees for a smoothed objective. PolyStepOR thus replaces optimal reference decisions and derivatives with forward evaluations.