PolyStepOR: Learning to Decide Without Optimal Decisions

Viet The Nguyen; Gunther Gust; An Thai Le

cs.LGSep 26, 2026

PolyStepOR: Learning to Decide Without Optimal Decisions

Authors: Viet The Nguyen, Gunther Gust, An Thai Le

Organizations: University of Würzburg, Germany · Center for Artificial Intelligence and Data Science (CAIDAS), Germany · Center for AI Research, VinUniversity, Vietnam · Intelligent Autonomous Systems, TU Darmstadt, Germany

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.

Figures & tables

Figure 1: Mean test regret on synthetic shortest-path and portfolio tasks as misspecification degree varies; lower is better. The portfolio panel uses a logarithmic axis and the displayed

\times 10^{3}

scale.

Figure 2: Mean test regret for knapsack capacities and scheduling loads on energy-price data ( Ifrim et al., 2012 ) , and matching instance types on citation networks ( Sen et al., 2008 ) ; lower is better.

Problem	$\rho$	MSE	CombOptNet	SFGE	PolyStepOR
KP (capacity)	5	0.5556 $\pm$ 0.3529	–	0.3577 $\pm$ 0.2152	0.2975 $\pm$ 0.1666
	10	1.2126 $\pm$ 0.7797	–	0.5081 $\pm$ 0.2784	0.3802 $\pm$ 0.1958
	20	2.5205 $\pm$ 1.6313	–	0.8216 $\pm$ 0.5031	0.4772 $\pm$ 0.2415
KP (weight)	5	0.1676 $\pm$ 0.0357	0.1901 $\pm$ 0.0289	0.1297 $\pm$ 0.0114	0.1501 $\pm$ 0.0210
	10	0.3190 $\pm$ 0.0814	0.4015 $\pm$ 0.0659	0.1760 $\pm$ 0.0221	0.2293 $\pm$ 0.0372
	20	0.6146 $\pm$ 0.1745	0.8233 $\pm$ 0.1401	0.2205 $\pm$ 0.0276	0.2884 $\pm$ 0.0558

Table 1: Mean relative post-hoc regret over 15 runs of 3 in-constraint prediction problems. Bold underlined marks the lowest mean in each row and bold the second lowest.

Method	Cost	Rel. (%)	$p$	Cost	Rel. (%)
	35 test problems			Ile-de-France
BD	594.1	9.46	$1\text{\times}{10}^{-8}$	2379.0	10.33
FIG	594.3	9.60	$1\text{\times}{10}^{-8}$	2388.8	10.78
PredGNN	603.0	10.95	$1\text{\times}{10}^{-10}$	2295.2	6.44
AvgTSP	583.3	3.86	$2\text{\times}{10}^{-5}$	2262.7	4.93
DistrictNet	557.7	-0.05	0.14	2205.7	2.29

Table 2: Districting costs on the 35 test problems (left), which consists of 7 real cities at 120 units, 5 target sizes and on the large instance Ile-de-France (right) with 2000 units.

Figure 3: Infeasibility ratio and regret of feasible solutions on test instances (adapted from Mandi et al., 2026 ). PolyStepOR is competitive with ODECE’s strongest baseline (MSE).

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	Scenario	Cases	Problem	Predictor	Parameters	Train / Val / Test
Shortest path	Degree	$\{1,2,4,6,8\}$	LP	Linear	240	1000 / 250 / 10000
Portfolio	Degree	$\{1,4,8,16\}$	QP	Linear	300	1000 / 250 / 10000
Knapsack	Capacity	$\{60,120,180\}$	0-1 ILP	Linear	9	550 / 100 / 139
Energy scheduling	Load	$\{1,2,3\}$	ILP	Linear	9	550 / 100 / 139
Matching	Instance type	$\{1,2,3\}$	ILP	MLP	573,601	22 / 5 / 5

Appendix

Table 3: Problems, solvers, predictors, and splits of the classical benchmarks of Mandi et al. (2024) .

Problem	$d$	$2Kd$	$B$	Solver calls per step	Mean stop / budget (steps)	Solver processes	Training (h)	Inference per instance (ms)
Shortest path	240	480	128	$61\,440$	139.5 / 150	8	$0.35\pm 0.05$	2.36
Portfolio	300	600	128	$76\,800$	92.5 / 100	1	$2.04\pm 1.03$	2.15
Knapsack	9	18	128	$2304$	98.0 / 100	1	$0.06\pm 0.01$	0.89
Energy	9	18	128	$2304$	93.8 / 100	32	$1.46\pm 0.46$	288.14
Matching	512	1024	17	$17\,408$	80.7 / 100	32	$1.25\pm 0.90$	143.25

Appendix

Table 4: Cost of one PolyStepOR run on the classical benchmarks, with training time as mean

\pm

standard deviation over the settings and ten seeds. Inference is one forward pass plus one solve, measured on load 2 for energy.

Method	Shortest path	Portfolio ( $\times 10^{3}$ )	Knapsack	Energy	Matching
MSE	0.1470 $\pm$ 0.0029	1.0738 $\pm$ 0.0008	0.0870 $\pm$ 0.0089	0.0224 $\pm$ 0.0021	0.9352 $\pm$ 0.0060
SPO+	0.1303 $\pm$ 0.0002	0.2617 $\pm$ 0.0315	0.0829 $\pm$ 0.0183	0.0151 $\pm$ 0.0014	0.9177 $\pm$ 0.0130
DBB	0.1228 $\pm$ 0.0033	141.5336 $\pm$ 0.0659	0.0616 $\pm$ 0.0016	0.0150 $\pm$ 0.0015	0.9171 $\pm$ 0.0098
I-MLE	0.1073 $\pm$ 0.0007	131.6175 $\pm$ 1.2281	0.0620 $\pm$ 0.0024	0.0149 $\pm$ 0.0015	0.9165 $\pm$ 0.0174
FY	0.1034 $\pm$ 0.0007	107.8452 $\pm$ 1.0827	0.1467 $\pm$ 0.0152	0.0151 $\pm$ 0.0016	0.9304 $\pm$ 0.0139
Listwise	0.1128 $\pm$ 0.0006	9.2482 $\pm$ 7.2742	0.1493 $\pm$ 0.0274	0.0277 $\pm$ 0.0037	0.9005 $\pm$ 0.0148

Appendix

Table 5: Test regret on the classical benchmarks averaged on all settings of each problem over ten seeds. Bold underlined marks the lowest mean in each column and bold the second lowest.

Method	Shortest path, degree $\mathrm{deg}$
Method	$\mathrm{deg}=1$	$\mathrm{deg}=2$	$\mathrm{deg}=4$	$\mathrm{deg}=6$	$\mathrm{deg}=8$
MSE	0.153 $\pm$ 0.000	0.101 $\pm$ 0.000	0.085 $\pm$ 0.001	0.131 $\pm$ 0.002	0.266 $\pm$ 0.013
SPO+	0.154 $\pm$ 0.000	0.101 $\pm$ 0.000	0.076 $\pm$ 0.000	0.099 $\pm$ 0.001	0.222 $\pm$ 0.000
DBB	0.164 $\pm$ 0.003	0.126 $\pm$ 0.009	0.083 $\pm$ 0.002	0.092 $\pm$ 0.005	0.148 $\pm$ 0.006
I-MLE	0.159 $\pm$ 0.002	0.104 $\pm$ 0.002	0.071 $\pm$ 0.000	0.087 $\pm$ 0.001	0.116 $\pm$ 0.002
FY	0.157 $\pm$ 0.001	0.102 $\pm$ 0.000	0.071 $\pm$ 0.001	0.081 $\pm$ 0.001	0.106 $\pm$ 0.002

Appendix

Table 6: Test regret per setting on the synthetic classical benchmarks over ten seeds (portfolio in absolute regret

\times 10^{3}

). Bold underlined marks the lowest mean in each column and bold the second lowest.

Method	Knapsack, capacity $C$
Method	$C=60$	$C=120$	$C=180$
MSE	0.149 $\pm$ 0.023	0.077 $\pm$ 0.005	0.035 $\pm$ 0.004
SPO+	0.142 $\pm$ 0.030	0.068 $\pm$ 0.030	0.038 $\pm$ 0.035
DBB	0.110 $\pm$ 0.006	0.052 $\pm$ 0.003	0.023 $\pm$ 0.002
I-MLE	0.108 $\pm$ 0.005	0.053 $\pm$ 0.004	0.025 $\pm$ 0.002
FY	0.289 $\pm$ 0.033	0.109 $\pm$ 0.016	0.043 $\pm$ 0.004

Appendix

Table 7: Test regret per setting on the classical benchmarks with real data over ten seeds. Bold underlined marks the lowest mean in each column and bold the second lowest.

Problem	Setting	Lowest-mean baseline	Lower mean	$p$ Wilcoxon	$p$ sign-flip
Shortest path	$\mathrm{deg}=1$	MSE	MSE	0.002	0.002
	$\mathrm{deg}=2$	SPO+	SPO+	0.002	0.002
	$\mathrm{deg}=4$	FY	FY	0.002	0.002
	$\mathrm{deg}=6$	FY	FY	0.002	0.002
	$\mathrm{deg}=8$	FY	FY	0.002	0.002
	pooled	FY	FY	0.002	0.002

Appendix

Table 8: Paired two-sided tests of PolyStepOR against the lowest-mean baseline of the main-text figures, over the ten paired seeds of each setting. “Lower mean” indicates the method with the lower mean of the pair.

50 items, $\rho=5$
Method	Rel. post-hoc regret	MSE	Infeas. ratio
MSE	0.5556 $\pm$ 0.3529	10.81	0.667 $\pm$ 0.257
SFGE	0.3577 $\pm$ 0.2152	16.63	0.749 $\pm$ 0.295
PolyStepOR	0.2975 $\pm$ 0.1666	21.87	0.752 $\pm$ 0.289
50 items, $\rho=10$
MSE	1.2126 $\pm$ 0.7797	10.81	0.667 $\pm$ 0.257

Appendix

Table 9: Knapsack with stochastic capacity (KP capacity), Table 8 of Silvestri et al. (2026) over 15 runs. Bold underlined marks the lowest value in each block and column, and bold the second lowest.

50 items, $\rho=5$
Method	Rel. post-hoc regret	MSE	Infeas. ratio
MSE	0.1676 $\pm$ 0.0357	$7.88\times 10^{4}$	0.929 $\pm$ 0.031
CombOptNet	0.1901 $\pm$ 0.0289	$5.09\times 10^{7}$	0.907 $\pm$ 0.032
SFGE	0.1297 $\pm$ 0.0114	$3.48\times 10^{5}$	0.987 $\pm$ 0.017
PolyStepOR	0.1501 $\pm$ 0.0210	$1.58\times 10^{6}$	0.964 $\pm$ 0.021
50 items, $\rho=10$

Appendix

Table 10: Knapsack with stochastic weights (KP weight), Table 2 of Silvestri et al. (2026) over 15 runs. Bold underlined marks the lowest value in each block and column, and bold the second lowest.

$10\times 50$ , $\rho=1$
Method	Rel. post-hoc regret	MSE	Infeas. ratio
MSE	1.2960 $\pm$ 0.5676	$1.04\times 10^{5}$	0.912 $\pm$ 0.048
CombOptNet	5.2044 $\pm$ 2.1887	$1.89\times 10^{7}$	1.000 $\pm$ 0.000
SFGE	1.1373 $\pm$ 0.4368	$3.33\times 10^{5}$	0.809 $\pm$ 0.125
PolyStepOR	1.1205 $\pm$ 0.5002	$4.87\times 10^{5}$	0.839 $\pm$ 0.091
$10\times 50$ , $\rho=5$

Appendix

Table 11: Weighted set multi-cover

10\times 50

, Table 3 of Silvestri et al. (2026) over 15 runs. Bold underlined marks the lowest value in each block and column, and bold the second lowest.

$5\times 25$ , $\rho=1$
Method	Rel. post-hoc regret	MSE	Infeas. ratio
MSE	1.6856 $\pm$ 1.1119	$8.07\times 10^{4}$	0.728 $\pm$ 0.163
CombOptNet	6.0568 $\pm$ 4.1781	$8.66\times 10^{6}$	1.000 $\pm$ 0.000
SFGE	1.2319 $\pm$ 0.5118	$2.98\times 10^{5}$	0.533 $\pm$ 0.280
PolyStepOR	1.0940 $\pm$ 0.3827	$7.20\times 10^{5}$	0.568 $\pm$ 0.248
$5\times 25$ , $\rho=5$

Appendix

Table 12: Weighted set multi-cover

5\times 25

, Table 9 of Silvestri et al. (2026) over 15 runs. Bold underlined marks the lowest value in each block and column, and bold the second lowest.

Problem	$\rho$	Lower mean	$p$ Wilcoxon	$p$ sign-flip	Runs	Lower mean	$p$ Wilcoxon
		Against SFGE				Against MSE
KP (capacity)	5	PolyStepOR	0.002	$<0.001$	12/15	PolyStepOR	0.002
	10	PolyStepOR	$<0.001$	$<0.001$	14/15	PolyStepOR	$<0.001$
	20	PolyStepOR	$<0.001$	$<0.001$	15/15	PolyStepOR	$<0.001$
KP (weight)	5	SFGE	0.004	0.005	2/15	PolyStepOR	0.022
	10	SFGE	$<0.001$	$<0.001$	0/15	PolyStepOR	$<0.001$

Appendix

Table 13: Paired two-sided tests over the 15 paired runs of each cell (5 datasets

\times

3 splits) on the relative post-hoc regret. “Lower mean” names the method with the lower mean of the pair, and “Runs” counts the runs in which PolyStepOR has the lower regret.

	35 problems					Ile-de-France
Seed	PolyStepOR	DistrictNet	Rel. (%)	$p$	PolyStepOR cheaper	PolyStepOR
3	551.7	551.4	-0.71	0.53	15/35	2156.3
5	552.2	562.0	+0.79	$6\times 10^{-3}$	22/35	2268.3
7	555.6	557.8	-0.16	0.64	19/35	2190.7
11	554.5	556.0	-0.97	0.40	13/35	2219.5
13	554.4	557.2	+0.54	0.08	25/35	2183.0

Appendix

Table 14: Districting results per training seed for tuned PolyStepOR and DistrictNet retrained with the authors’ code at the same seed. Results are reported over the 35 benchmark problems together with the PolyStepOR cost on Ile-de-France. Relative cost is measured for DistrictNet with respect to PolyStepOR, so negative values indicate lower DistrictNet cost. The

p

-value is from a paired two-sided Wilcoxon test over the 35 problems.

Configuration	Seeds	PolyStepOR	Rel. DistrictNet (%)	$p$	PolyStepOR cheaper	Mean	Best
		35 problems				Ile-de-France
Tuned	10	554.0	-0.05	0.14	18/35	2197.0	2156.3
Untuned	10	565.3	-1.97	$2\times 10^{-10}$	1/35	2220.5	2186.6

Appendix

Table 15: Performance of tuned and untuned PolyStepOR configurations. Results on the 35 benchmark problems are compared with DistrictNet retrained at the same seeds. Ile-de-France reports the mean and best PolyStepOR cost across seeds.

Figure 4: Districtings produced by PolyStepOR and DistrictNet at seed 1234 on the examples visualized by Ahmed et al. (2024) : London and Manchester at $t=6$ and $t=20$ . The cost is shown below each map, and the row label reports the relative cost of DistrictNet with respect to PolyStepOR.

Method	Infeasibility	Conditional regret
MSE	0.532	0.169
CombOptNet	0.896	0.181
SFL	0.991	0.019
2sPtO	0.400	8.539
ODECE ( $\alpha=0.2$ )	0.790	0.081
ODECE ( $\alpha=0.3$ )	0.729	0.123

Appendix

Table 16: Brass alloy production, with infeasibility before repair and regret over each method’s feasible test purchases; lower is better. The baselines except SFGE are the values reported by Mandi et al. (2026) , and PolyStepOR is mean

\pm

standard deviation over five seeds.

Problem	Schedule	$\varepsilon$		$s$		$r$		$d$	$q$	$K$	Momentum	$B$	Budget (steps)
Problem	Schedule	start	end	start	end	start	end	$d$	$q$	$K$	Momentum	$B$	Budget (steps)
Classical OR
Shortest path	cosine	10	0.1	5	1	10	2	240	8	1	0	128	150
Portfolio	cosine	5	0.3	32	8	2	0.5	300	8	1	0	128	100
Knapsack	cosine	10	0.1	5	1	10	2	9	8	1	0	128	100
Energy scheduling	cosine	10	0.1	5	1	10	2	9	8	1	0	128	100

Appendix

Table 17: PolyStepOR settings behind every reported number.

Explore similar work

A Solver-Free Training Method for Predict-then-Optimize
Jun 17, 2026Beichen Wan, Mo LiuPredict-Then-Optimize Learning to Optimize
Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, NC, USA.
Decision-Focused Learning: When and Why Traditional Prediction Models Fail
Jun 19, 2026Mo LiuPredict-Then-Optimize Decision-Focused Learning
Department of Statistics and Operations Research, University of North Carolina at Chapel Hill
Decision-Focused Learning via Tangent-Space Projection of Prediction Error
May 2, 2026Junhyeong Lee, Sangjin Jin, Yongjae LeeDecision-Focused Learning Differentiable Optimization
Department of Industrial Engineering, Ulsan National Institute of Science and Technology, Ulsan, South Korea.

Jun 17, 2026J/K move · Enter open · S save

A Solver-Free Training Method for Predict-then-Optimize

Beichen Wan, Mo Liu

Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, NC, USA.

Predict-Then-Optimize Learning to Optimize Decision-Focused Learning

Open paper AskPDF arXiv

We propose a scalable method for training prediction (machine learning) models in the predict-then-optimize paradigm, where model outputs serve as coefficients for a subsequent linear optimization task. Directly minimizing the empirical decision regret is intractable for linear programming and combinatorial optimization since the decision mapping is piecewise constant, and the gradients are zero almost everywhere. While existing methods address this by smoothing the differentiation process, they suffer from scalability issues, since a computationally expensive solver call is required for every gradient evaluation. To address this, we propose a decision-focused learning pipeline based on a measure transformation principle, which yields a new surrogate loss that is completely optimization-solver-free during training. We establish theoretical guarantees, including Fisher consistency and excess risk bounds. Empirically, our method achieves decision quality competitive with state-of-the-art methods while reducing training time by orders of magnitude.

Abstract

Explore similar work

A Solver-Free Training Method for Predict-then-Optimize

Decision-Focused Learning: When and Why Traditional Prediction Models Fail

Decision-Focused Learning via Tangent-Space Projection of Prediction Error