- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper presents PolyStepOR, which applies the existing PolyStep optimizer to decision-focused learning (DFL). The method trains predictors directly from realized decision costs, without requiring optimal reference solutions or gradients through the predict-then-optimize pipeline. It perturbs predictor parameters, evaluates the resulting decisions, and uses cost-weighted directions to update the model. The approach also handles problems with predicted constraints through repair costs or infeasibility penalties.
The paper studies decision-preserving perturbations, boundary detection and crossing, and stationarity of a smoothed objective. Experiments cover standard DFL benchmarks, problems with predicted constraints, and practical applications such as network districting and brass alloy production. While PolyStepOR achieves competitive results in some settings, the improvements are not consistent, especially given its computational cost. Overall, the paper shows that PolyStep can be applied to DFL, but it remains unclear what this adds to the original method or why it should be preferred over existing approaches.
Critical strengths
S1. Flexible training without optimal reference solutions.
PolyStepOR trains predictors using realized decision costs without requiring optimal training labels or gradients through the prediction–optimization pipeline. This can be useful when obtaining optimal solutions is expensive or when the downstream solver is difficult to differentiate. The method also handles problems with predicted constraints through recourse costs.
S2.Broad evaluation and analysis.
The paper evaluates the method on a variety of DFL problems, including standard benchmarks and practical applications. The theoretical analysis also helps explain how perturbations behave around decision boundaries. The appendix provides detailed experimental settings and computational costs.
Critical weaknesses
W1. Insufficient motivation for using PolyStep in DFL.
The paper does not clearly explain why PolyStep is a particularly good choice for DFL, given the many existing approaches to learning from decision losses.
The authors motivate their method by noting that decision losses are often piecewise constant, and that finite perturbations can provide useful learning signals when gradients vanish. While this connection makes sense, it is also a fairly general argument for using derivative-free optimization. Existing DFL methods already address this problem in various ways, including perturbation-based gradient estimation and learned surrogate losses.
What I find missing is a clearer explanation of why PolyStep is well suited to this setting. What limitations of existing approaches does it aim to overcome, and what properties of DFL make PolyStep's update rule a good fit? The paper shows how the two can be combined, but the motivation for this particular choice remains weak.
W2. Limited novelty beyond the original PolyStep method.
Most of the optimization procedure is inherited from the original PolyStep method (Le, 2026). As described in Section 4 and Algorithm 1, the structured perturbations, rotated search directions, softmax-based cost weighting, and parameter updates are already part of PolyStep.
Training directly on realized decision costs is also a relatively straightforward extension. In the standard setting with a fixed feasible set, the optimal reference cost is independent of the predictor. Removing it therefore leaves the minimizers of unnormalized regret unchanged. Similarly, Proposition 1 follows from the shift invariance of the softmax weights.
The paper adds some analysis of decision boundaries, particularly in Propositions 2 and 3. However, these results mainly characterize how the existing probing procedure behaves around decision boundaries. They are not used to change the search strategy or improve the updates. The stationarity results also build on the smoothing analysis of PolyStep and concern a smoothed objective with a residual bias. Moreover, the experiments do not examine whether the decision margins and boundary detection and crossing conditions in Propositions 2 and 3 help explain the observed performance. This leaves the practical significance of the theoretical analysis unclear.
As a result, I find the contribution beyond the original PolyStep rather limited. The paper provides an application of the optimizer to DFL and some additional analysis, but it is difficult to identify a substantial new methodological insight.
W3. Unconvincing performance–efficiency trade-off.
The experimental results do not provide a clear reason to prefer PolyStepOR over existing DFL methods, especially considering its computational cost.
PolyStepOR performs competitively on several benchmarks, but the improvements are not consistent. For example, Section 6.1 highlights the portfolio results against SPO+, while Appendix Table 5 shows that MAP and Pairwise achieve lower average regret than PolyStepOR (0.0955 and 0.1109 versus 0.1602, respectively, in the reported scale). Existing methods also perform better on shortest path and matching. In the predicted-constraint experiments, PolyStepOR performs better than SFGE on knapsack capacity prediction but worse on knapsack weight prediction, while the WSMC results are largely comparable.
The computational cost is also substantial. PolyStepOR evaluates many perturbed predictors at every training step, requiring repeated solver calls. In the districting experiment, the tuned configuration takes around 13.5–14.5 hours on 128 CPU cores, while retraining DistrictNet takes about 32.5 minutes on 2 cores. Despite this difference, PolyStepOR does not achieve a statistically significant improvement on the 35 test problems (p = 0.14). The untuned configuration performs significantly worse. I recognize that DistrictNet requires optimal training labels, which can be expensive to obtain. Still, the paper does not provide a complete comparison that accounts for these costs.
More importantly, the experiments do not establish whether PolyStep itself offers an advantage over simpler derivative-free optimization methods. A comparison under the same solver-call or wall-clock budget would be particularly useful here. The evaluation also gives limited insight into how PolyStepOR compares with more recent approaches that aim to reduce the cost of learning from decision losses.
Overall, the results show that PolyStep can be applied to DFL, but they do not establish a convincing practical advantage over existing methods. Given the limited novelty, I find this particularly concerning.
Questions for authors
Q1. Motivation and novelty.
What is the main motivation for choosing PolyStep over other approaches to learning from decision costs? Beyond applying the existing optimizer to DFL, what do the authors consider the main new contribution? In particular, how does the decision-boundary analysis contribute to the proposed method beyond explaining the behavior of the original optimizer?
Q2. Computational cost and comparisons.
How does PolyStepOR compare with standard derivative-free optimizers such as ES or SPSA under the same solver-call or wall-clock budget? It would also be helpful to compare total training costs, including the generation of optimal reference solutions where needed. More generally, in which settings would PolyStepOR offer a practical advantage over existing DFL methods?
Q3. Evidence for the proposed mechanism.
The paper analyzes when perturbations can detect better decision regions and when updates can cross decision boundaries. Is there empirical evidence that these events occur frequently during training? In particular, how often do probes find lower-cost decisions, and how often do the resulting updates actually reduce the decision loss? This would help clarify whether the observed performance comes from PolyStep's update rule or simply from evaluating many candidates.
4 comments
Follow-up discussion
Thank you for your review and feedback. As the discussion period is ending soon, could you let us know if our response and revision address your concerns? We have provided 4 updates to address the concerns:
- Highlighted the specific complications of bridging PolyStep to decision-focused learning, while narrowing our claims to separate the inherited optimizer from our DFL contribution. Unlike standard neural network training in PolyStep, each forward pass here requires running external solvers multiple times across instances and turning the realized OR decision cost itself into a guided loss without optimal labels or solver gradients.
- Clarified our theoretical scope by mapping prediction gaps to decision-preserving distances, distinguishing boundary detection from crossing via a worked example, and detailing limits such as batch cancellation and evaluation errors.
- Reported performance and runtime trade-offs directly across all benchmarks, showing that PolyStepOR scales with returned candidate solutions rather than the full feasible space required to compute exact labels.
- Added extensive experiments for matched solver-budget comparisons against ES, SPSA, and four other derivative-free methods, along with a replay study of minibatch versus validation behavior as suggested.
We are very happy to provide further information, should there be further concerns about our work. Authors
Response to the Authors
Thank you for the detailed response. I appreciate the explanations, particularly the clarification of the experimental limitations and the scope of the theoretical analysis. I still have some concerns about the results and the novelty of the work.
First, I could not find Tables 18–21 in the revised PDF available to me. The appendix ends at Table 17. I can see the results summarized in your response, but I cannot check the full comparisons with ES, SPSA, and the other methods, or the additional ablations. Could you let me know where I can find these tables?
The results reported in your response suggest that PolyStepOR performs better than several derivative-free methods. However, the comparisons use the same solver-call budget without matching training time or tuning costs. More importantly, other DFL methods still achieve lower regret on several benchmarks, as you acknowledge. In the districting experiment, PolyStepOR takes much longer to train than DistrictNet, without showing a statistically significant improvement. Avoiding optimal reference solutions can be useful, but the paper does not show when this benefit outweighs the additional training cost.
I still have concerns about the novelty of the work. As you acknowledge, the main parts of the method already come from PolyStep. The decision-boundary analysis does not change the update rule, and as you note in your response, the additional experiments do not directly verify the decision-boundary analysis. I therefore still see the paper mainly as an application of an existing optimizer to DFL.
I do not see a clear reason to choose PolyStepOR over existing DFL methods. Its performance is not consistently better, its training cost is high, and the contribution beyond PolyStep is limited. For these reasons, I will keep my original rating.
Thank you for the insightful feedback. We have uploaded the revised manuscripts with all of the additional experiments highlighted. We apologize for the confusion.
the comparisons use the same solver-call budget without matching training time or tuning costs.
We agree that equal solver-call caps do not equalize runtime or tuning effort, as noted in Appendix B.5.1. However, because all baselines are tuned per their original papers and share the same predictor, solver, and minibatch objective, solver calls represent their primary shared cost. Notably, PolyStepOR achieves lower regret in most comparisons even at the smallest cap, which matches the training calls of SPO+ (Table 18).
More importantly, other DFL methods still achieve lower regret on several benchmarks, as you acknowledge.
Section 6.1 openly reports these results, though we view them as reflecting a difference in supervision regimes rather than settling the central question of the paper. The methods achieving lower regret rely on stronger training signals, such as optimal reference decisions for every instance (FY, MAP, Pairwise) or true cost vectors used as gradients with respect to the decision (I-MLE). In contrast, PolyStepOR targets settings where only realized decision costs are accessible, such as predicted constraints with recourse or heuristic solvers. Within that cost-only regime, the appropriate baselines are methods operating under the same restriction, namely SFGE (Table 1) and the derivative-free optimizers (Tables 18 and 19).
In the districting experiment, PolyStepOR takes much longer to train than DistrictNet, without showing a statistically significant improvement. Avoiding optimal reference solutions can be useful, but the paper does not show when this benefit outweighs the additional training cost.
Section 6.2 explicitly notes both points. At the 30-unit training scale, DistrictNet requires less total compute even when including label generation (Table 14), and the cost difference across the 35 test instances is not statistically significant. While our study does not pinpoint the exact instance size where avoiding optimal labels outweighs the added training cost, a predictor trained solely on the costs of its own partitions still matches the decision quality of one trained on optimal partitions.
I still have concerns about the novelty of the work. As you acknowledge, the main parts of the method already come from PolyStep. The decision-boundary analysis does not change the update rule, and as you note in your response, the additional experiments do not directly verify the decision-boundary analysis. I therefore still see the paper mainly as an application of an existing optimizer to DFL.
While the underlying update rule builds on PolyStep, our contribution extends beyond a straightforward application. Without reference decisions, label-based methods such as SPO+, Fenchel-Young, caching losses, and DistrictNet lose their training signal entirely because they rely on optimal solutions to construct it. In contrast, PolyStepOR synthesizes a learning signal purely from the realized costs of candidate predictors. Our ablations further confirm that how these costs are aggregated is critical for decision losses. Under identical candidates and solver-call budgets, replacing the update with greedy or best-candidate rules increases regret on shortest path, portfolio, and predicted item weights, whereas all cost-aware rules perform similarly on the nine-parameter knapsack predictor (Table 20).
I do not see a clear reason to choose PolyStepOR over existing DFL methods. Its performance is not consistently better, its training cost is high, and the contribution beyond PolyStep is limited. For these reasons, I will keep my original rating.
PolyStepOR is intended for settings where optimal decisions and solver derivatives are unavailable. Within this regime, it achieves lower regret than other derivative-free optimizers on larger predictors (Table 18), while outperforming SFGE on predicted capacity and trailing it on predicted item weights (Table 1). Conversely, when optimal decisions are inexpensive to compute, label-based methods remain the preferable choice.
Overall, PolyStepOR trains predictors solely from decision costs without optimal decisions or solver derivatives, achieving lower regret than other derivative-free optimizers in most comparisons and matching SFGE competitively, with full training costs transparently reported. Thank you again for your thoughtful review. We hope these updates address your concerns and are happy to continue the discussion to further improve the paper.
Thank you for the detailed assessment of novelty and the trade-off between performance and cost. We agree that the original draft did not clearly separate the inherited optimizer from the DFL contribution. We have narrowed the claims and clarified the comparisons.
Motivation and novelty
Decision losses are piecewise constant in predictor parameters, so gradients vanish almost everywhere. Unlike label-based DFL methods (SPO+, Fenchel-Young, ranking losses, DistrictNet) that rely on reference decisions for supervision, PolyStepOR requires only candidate decision costs. Finite probes detect decision changes across plateaus, and PolyStep combines directions into a bounded update with a separate step length, avoiding exploding steps at small radii. Table 20 assesses these components.
The evidence does not establish that every component is necessary. Rotated polytope probes, softmax weights, and the parameter update come from PolyStep. Our contribution is their use through a DFL cost oracle, together with analysis of prediction margins, batch aggregation, and the relation between probed and updated decisions. Reference-cost invariance is now a remark because it follows from softmax shift invariance. We also credit PolyStep for the jump and smoothing analyses on which our results build.
Scope of the theoretical analysis
The theory maps prediction gaps to a search distance that preserves a decision and distinguishes detecting a cheaper region from reaching it. The worked example makes this distinction concrete. The appendix shows how batch preferences can cancel, why simultaneous block updates can fail to improve the loss, and why predicted solver gaps do not directly control realized-cost errors. These results explain the limits of the cost signal. They neither alter the search rule nor guarantee improvement at each step, and the stationarity bound also retains a bias residual.
Decision quality, compute cost, and practical scope
We now state the gaps in decision quality and total compute directly. MAP and Pairwise achieve lower pooled portfolio regret, and other DFL methods perform better on shortest path and predicted item weights. On matching, several methods have lower mean regret, but paired tests detect no difference. DistrictNet remains cheaper at the measured training size, including shared preprocessing (Table 14). Tuned PolyStepOR has no detected cost advantage on the benchmark cities, and the untuned configuration is worse. The large-city comparison is descriptive because DistrictNet has only one published value. However, label cost scales with all feasible districts (400 CPU-core days for one 60-unit label in DistrictNet), whereas one PolyStepOR evaluation scales only with returned candidate districts. PolyStepOR offers a practical advantage when decisions can be scored without exact labels or differentiable paths, including predicted constraints with recourse, inexact solvers, and large combinatorial instances.
Derivative-free comparisons and training behavior
The requested comparison with ES, SPSA, and four other derivative-free methods uses equal training solver-call caps (Tables 18 and 19). PolyStepOR achieves lower test regret in 199 of 270 paired comparisons and higher regret in 3, winning 79 of 90 comparisons against OpenAI-ES and SPSA with zero losses. Its clearest advantage within this group is on portfolio and shortest path, while its capped results on both tasks remain worse than SPO+ and MSE. Runtime and tuning effort are not matched. Solution-caching losses (Listwise, Pairwise, MAP) in Appendix B.1 reuse optimal reference decisions, making them complementary to our reference-free setting. Related work also covers LANCER and solver-free DFL for linear optimization, though neither is evaluated here.
Finally, the replay study separates minibatch improvement from validation improvement (Table 21). Updates often reduce minibatch cost, but this does not consistently transfer to validation. Probe statistics come from separate ablation reruns and cannot be combined with replay counts into a detection-to-crossing rate. We present these measurements as observations of training behavior rather than verification of the isolated-boundary theorem, while random-vertex ablations confirm that candidate count alone does not explain performance (Table 20).