acceptodds
Under review as a conference paper at ICLR 2027

PolyStepOR: Learning to Decide Without Optimal Decisions

35 views

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.

Primary area:
optimization
Keywords:
decision-focused learning, optimal transport, optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_hXS6OpenReview ↗
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

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.

AblationMain result
Softmax versus greedy or best-single-candidate updatesSoftmax yields lower regret on shortest path and portfolio.
Other cost-aware rulesNo detected difference on knapsack; top-3 averaging also shows no significant difference from softmax on shortest path.
Probe geometryEffects depend on the task, and variants use different solver-call counts.

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).

AuthorsOpenReview ↗

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

Reviewer_hXS6OpenReview ↗

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.

Reviewer_bFf2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes PolyStepOR, a derivative-free decision-focused learning framework that learns directly from decision costs without requiring optimal decision labels or differentiable optimization solvers. Its key innovation is structured parameter perturbations combined with entropy-regularized, cost-weighted updates. Theoretical results characterize decision-boundary exploration and establish an stationarity rate for a smoothed objective. Experiments show competitive performance across several optimization tasks, although results vary by problem.

Critical strengths
  1. PolyStepOR eliminates the need for optimal decision labels and gradients through optimization solvers, making it applicable to non-differentiable decision-making problems.
  2. The paper provides convergence analysis and demonstrates competitive performance across diverse optimization tasks, including portfolio optimization and predicted-constraint problems.
Critical weaknesses
  1. The perturbation-based approach requires repeated optimization-solver evaluations, potentially limiting scalability on computationally expensive problems.
  2. Performance varies across problem settings, with weaker results on some tasks. The convergence analysis concerns a smoothed objective and does not guarantee finding globally optimal decisions.
Questions for authors
  1. How does PolyStepOR's computational cost, in terms of solver calls and wall-clock training time, compare with existing decision-focused learning baselines as problem size increases?

  2. How sensitive is PolyStepOR to the choice of perturbation radius, temperature, and learning rate? Can the authors provide a systematic sensitivity analysis across different problem classes?

  3. What explains the weaker performance on high-complexity shortest-path instances and predicted item-weight problems? Are there identifiable conditions under which PolyStepOR is expected to outperform existing methods?

2 comments

Thank you for the questions about computational cost, sensitivity, and convergence. We have made these limits explicit and revised the discussion around what the completed experiments support.

Computational cost and scaling

Each candidate predictor requires a forward pass and downstream solves. With block size and the number of radii fixed, the candidate count grows with the searched parameter dimension. Larger optimization instances can also increase the time per solve. The compute and scaling tables separate these effects, and the larger-instance measurements are timing benchmarks rather than complete training runs. Restricting the search dimension reduces calls but can substantially degrade decision quality. Alloy uses a small search subspace within a larger network, so it does not establish favorable scaling with network size.

Candidate evaluation, districting, and inexact solves

Our practical motivation is to train predictors directly from the realized scalar cost of candidate decisions, including repair costs or heuristic solver outputs, when optimal training targets or derivatives through the decision pipeline are unavailable. In districting, for example, the predictor defines a spanning-tree surrogate that returns a candidate partition whose routing cost is scored, avoiding optimal partitions as training targets. However, candidate evaluation being cheaper than finding an optimal target does not imply lower total training cost. Both districting methods use the same precomputed district costs, and DistrictNet remains cheaper at the measured training size, including reference generation (Table 14). Because PolyStepOR relies only on realized decision costs, training solves also do not need to reach exact optimality. Moderately relaxed training solves show no detected regret change on scheduling (Table 23), while our analysis explains why a solver's predicted-objective gap alone cannot bound its error in realized decision cost.

Equal-budget comparisons and sensitivity

On the main classical benchmarks, PolyStepOR achieves competitive regret on knapsack and scheduling and attains the lowest mean post-hoc regret on predicted capacity. To isolate optimizer efficiency, the budget study compares PolyStepOR with six other derivative-free optimizers using the same predictors, cost objective, and caps on training solver calls.

ComparisonMain resultPaper reference
Other derivative-free optimizersPolyStepOR's advantage is clearest on portfolio and shortest path.Tables 18 and 19
SPO+ and MSEBoth have lower mean regret than capped PolyStepOR on portfolio and shortest path.Tables 6 and 19
One-at-a-time sensitivityModerate changes to radius, temperature, and step length produce few detected differences on knapsack, shortest path, and predicted capacity. Portfolio is more sensitive.Table 22

The main PolyStepOR runs use larger budgets. Methods may stop below the cap, tuning and runtime differ, and PolyStepOR is tuned separately at each cap. These are comparisons of configurations rather than points on one learning curve, and the uncorrected pairwise tests are descriptive. The local sensitivity study does not establish general robustness. Most shortest-path runs at the highest misspecification level reach the step budget, but this does not show that more training would close the gap. Likewise, the predicted-weight results do not isolate the cause of weaker performance or establish that tuning resolves it.

Theoretical convergence and scope

The convergence result bounds the expected squared gradient of a smoothed loss at a random iterate, up to a bias residual. The appendix now gives a concrete sufficient OR setting consisting of finite data, finitely many returned decisions, and finite total costs including recourse. Compact decision sets with continuous total costs also give bounded losses. Smooth radius randomization supplies the required regularity, whereas fixed radii alone need not.

Additionally, the result also requires fixed search coordinates, temperature and probe law, conditionally unbiased batches, and the stated step-size rule. Bounded costs ensure finite constants, but the residual need not be small. No reported configuration is established to satisfy every assumption, and a stationary point may lie on a poor plateau. We therefore motivate PolyStepOR by the availability of candidate costs and the difficulty of obtaining targets or derivatives, without claiming that these conditions ensure better performance.

AuthorsOpenReview ↗

Follow-up discussion

Thank you for your time and thoughtful feedback on our work. As the discussion period is nearing its end, we wanted to follow up on the updates we made in response to your review.

We have addressed your comments as follows:

  • Provided more comprehensive results on computational costs and scaling, along with clearer explanations of the advantages of training without optimal solutions, specifically in the districting demonstration.
  • Added new experiments examining the solving budget and sensitivity analysis.
  • Strengthened the theoretical convergence analysis when applied to optimization problems.

We are happy to engage in further discussions if there are still further concerns about our work. Authors

Reviewer_S362OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes PolyStepOR, a decision-focused learning (DFL) method that aims to train predictive models without needing optimal reference decisions. The main idea is to directly train the predictor based on the costs of the decisions it produces. Instead of differentiating through the optimization problem (as most DFL approaches do), the authors perturb the parameters of the predictive model in different directions and evaluate how well the resulting predictors perform on minibatches of training instances. Based on the decision costs obtained from these evaluations, they use the PolyStep method from prior work to determine how to update the model parameters. This way, the method does not require gradients of either the predictor or the optimization problem. The paper also considers cases where the predictions appear in the constraints, where infeasible decisions are handled through repair costs or penalties.

Critical strengths

General applicability. The main idea of training directly from the realized decision costs is appealing, especially since the method does not require differentiating through the optimization solver, as many other DFL methods do.

Applicability to predicted constraints. I appreciate that the authors do not restrict themselves to the classical DFL setting where only the objective coefficients are predicted. They also consider predictions appearing in the constraints and incorporate feasibility corrections and recourse costs into the training objective.

Theoretical analysis and reproducibility. While I have some concerns about the practical relevance of the theoretical results, I appreciate the effort to characterize the behavior of the probing mechanism and provide formal guarantees. The appendices are also quite detailed, with additional experimental results, computational statistics, and hyperparameter configurations that help with reproducibility.

Critical weaknesses

Lack of clarity. There is a serious lack of clarity in the methodology. Particularly the central Section 4.2 is unnecessarily obscure and difficult to follow. The three main components of the algorithm (search coordinates, probes, and updates) are introduced primarily through mathematical definitions, with very little intuition or motivation given. For example, in the very beginning of this section, the authors introduce θ(y)=θ0+Ay\theta(y)=\theta_0+Ay without adequately explaining the role of its components. A clearer exposition would first explain that θ0\theta_0 represents the initial predictor parameters, that the columns of AA define the directions in parameter space along which the model can be modified (potentially restricting the search to a lower-dimensional subspace), and that yy contains the variables that are actually being optimized. This would help readers understand why the reparameterization is introduced and how it relates to the subsequent probing and updating procedure. Similar explanations are needed for essentially all other components of this section. Given that this is the central methodological contribution, I consider the lack of intuitive explanation a significant weakness.

Unclear motivation for avoiding optimal decisions. Another fundamental concern I have is whether the central motivation of the paper, namely learning without optimal reference decisions, provides a meaningful practical advantage. In the introduction, the authors state that “Another challenge is obtaining optimal reference decisions for training, which can be expensive for large instances.” However, the proposed method requires solving a large number of downstream optimization problems at every training iteration to evaluate perturbed predictors. This raises the question of why computing optimal reference decisions once per training instance would be less attractive, particularly when these optimization problems have comparable complexity. Given that avoiding optimal decisions is the central premise of the paper, I believe the authors need to provide a stronger justification of when and why this is advantageous, rather than presenting the absence of optimal reference decisions as an advantage in itself.

Limited contribution of the momentum extension. Section 4.2 introduces an optional momentum-based update, which essentially applies a standard optimization technique to the proposed update directions. While this is a reasonable design choice, it is not particularly novel, and in my view should be removed from the paper. The space this frees could be used for more intuitive explanations of the core methodology. This is especially warranted since Table 17 in the appendix shows that momentum is disabled in almost all experimental configurations, raising questions about its practical importance to the method.

Unclear relevance of the theoretical results. While Section 5 provides several theoretical results concerning decision margins and boundary detection, it is not immediately clear to me what insights these results offer beyond formalizing some intuitive properties of the proposed mechanism. For instance, the observation that probes need to reach a decision boundary to detect a change, or that an update must cross this boundary to improve the decision, seems rather straightforward. I would encourage the authors to better explain the significance of these results, particularly what they tell us about the behavioir of the algorithm and whether they can inform practical choices such as probe radius, step size, or temperature, for example.

Limited empirical improvements. While the method performs reasonably well across several benchmarks, it does not consistently improve on existing state-of-the-art methods. Together with my earlier concern about whether avoiding optimal reference decisions is actually that useful in practice, this makes the overall contribution less convincing to me. Given the substantial computational effort required by PolyStepOR, I would have liked to see either clearer improvements in decision quality or a more convincing demonstration of its practical advantages over existing methods.

Lack of ablation studies. The experimental evaluation lacks ablations that would help understand the contribution of the different components of the method, such as the orthoplex probes, Haar rotations, block-wise search, and softmax weighting. It is therefore unclear which design choices are actually important for the observed performance. The tuned versus untuned comparison in Appendix B.3 is useful, but changes several components at once. More targeted ablations would help justify the proposed algorithmic design.

Questions for authors

/

4 comments
AuthorsOpenReview ↗

Improving method clarify, and connecting theory better to the experimenmts

Thank you for the careful and thoughtful review. Your comments helped us see where the method and its practical motivation needed clearer explanations. We have simplified the method section and connected the theory to the questions examined in the experiments.

Methodology

Section 4.2 now defines which predictor parameters can change before introducing the formulas. Each probe changes one block, and all probes use the same minibatch. Softmax weights favor cheaper directions; a separate step length controls the update. Algorithm 1 presents this core procedure, with momentum moved to the appendix. A worked example shows why finding a cheaper decision with a probe does not ensure that the update reaches it.

Clarification of motivation

Our practical motivation is to train predictors when we can evaluate the cost of a proposed decision but cannot readily obtain an optimal decision to use as a training target. For example, measuring the routing cost of a proposed geographical partition is much easier than finding the partition with the lowest routing cost. PolyStepOR learns by comparing the costs of the partitions its predictor produces, without needing the best partition as a target. This distinction explains when and why avoiding optimal targets is crucial (solving the exact problem to generate labels vs. solving the surrogate problem for training and testing). It enables learning from decision costs in settings where constructing those targets is the bottleneck. PolyStepOR can use the decisions returned by an exact or heuristic solver and train directly on their costs, including repair costs, without requiring derivatives through the prediction and decision process.

Districting experiments

Avoiding optimal targets is useful when a candidate decision can be scored at reasonable cost but finding the best decision is expensive. In districting, a predictor defines a spanning-tree surrogate that returns a partition, whose routing cost can then be evaluated. Finding an optimal training partition is a harder task. Our experiments nevertheless use the full precomputed district-cost table for both methods. DistrictNet costs less at the measured training size, including reference generation (Table 14). Transfer to larger test cities does not establish cheaper training on large cities.

Theoretical clarity

The theory explains how prediction margins restrict decision changes, then separates detecting a cheaper region from entering it. The crossing result applies to an update of one block near an isolated boundary where the loss takes two values. Batch preferences can cancel, and simultaneous block updates can interact. The cost-error bound also explains why sharper weights are more sensitive to inaccurate evaluations. These results support interpretation of the algorithm, but do not supply an automatic tuning rule. The stationarity result concerns a smoothed loss and retains a bias residual that need not be small.

Empirical contributions on classical OR benchmarks

We summarize the results on the classical OR benchmarks below:

ProblemMain resultPaper reference
Knapsack and schedulingCompetitive regret, with paired tests detecting no difference from the lowest-mean baseline in each setting.Figure 2; Table 8
Predicted constraintsLowest mean post-hoc regret on predicted capacity. Here, SFGE performs better on predicted item weights.Table 1
Portfolio and shortest pathMAP and Pairwise have lower pooled portfolio regret. Other DFL methods perform better on shortest path.Figure 1; Table 5
MatchingSeveral baselines have lower mean regret, but paired tests detect no difference from the lowest-mean baseline in the main comparison.Figure 2; Table 8

We also show that under equal training solver-call caps, PolyStepOR's advantage over other derivative-free methods is clearest on portfolio and shortest path (Table 18). At those caps, its mean regret on both tasks still exceeds the SPO+ and MSE results. The full results are shown in Appendix B.5.1, Table 18 and Table 19. The main PolyStepOR experiments use larger budgets, where runtime and tuning effort are not matched.

Momentum term

Thank you for pointing this out. The ablation studies in Table 20 show task-dependent benefits from cost weighting and probe geometry. While softmax weighting outperforms several cost-aware controls on portfolio and shortest path, it does not improve upon every control across all tasks, and the geometry variants differ in their solver-call counts. Additionally, our sensitivity study finds that momentum provides no significant benefit and can occasionally degrade performance. Accordingly, we have moved the momentum-based update to Appendix A.5. and present it as an optional component of the method.

AuthorsOpenReview ↗

Follow-up discussion

Dear reviewer,

Thank you for your time and great efforts in reviewing our paper. As the discussion period is coming to an end, could you let us know if our responses and updated manuscript have resolved your concerns? We have made three main updates in our revision:

  • Updated the methodology section to provide clearer intuition.
  • Better connected the theoretical framework to reflect the algorithm's behavior.
  • Provided stronger justifications for our empirical experiments and the overall motivation of the paper.

We are very happy to provide any additional information or clarification if needed. Authors

Thank you for the detailed response and the revisions to the manuscript.

Regarding the motivation, I now better understand the intended problem setting, where solving a surrogate problem is considerably cheaper than obtaining an optimal solution to the original problem. However, this distinction is barely discussed outside Section 6.3, and most experiments do not consider such a setting. For the classical DFL benchmarks, I still struggle to see the advantage of the proposed method, given its substantially higher computational cost compared to SPO+ and the limited improvements in decision quality.

I encourage the authors to focus the paper much more explicitly on problems for which a cheaper surrogate exists, as this is where I see the potential added value of the method. However, even in the districting application, PolyStepOR remains considerably more expensive than DistrictNet.

I remain unconvinced of the merit of the proposed method. I believe that addressing this requires a more fundamental revision of the paper's motivation, problem formulation, and experimental evaluation. I therefore cannot recommend acceptance in its current form, and maintain my original score.

Thank you for helping us sharpen the practical focus of the paper. We share your interest in settings where optimal references are difficult to obtain, and we view our fully gradient-free results as a concrete step toward addressing them. While we agree that expensive-reference regimes deserve greater emphasis, we want to highlight 3 core findings from our work:

Learning from decision costs alone

We show that PolyStepOR trains neural predictors to competitive decision quality using strictly scalar decision costs, requiring neither optimal targets nor derivatives of the predictor, solver, or task loss. This extends directly to predicted constraints through decision repair costs, establishing empirically that strong decision quality is achievable without optimal labels or backpropagation.

Classical OR benchmarks

We use these benchmarks to test gradient-free learning under controlled, standard formulations. Under matched solver-call budgets against 6 derivative-free baselines (Tables 18 and 19), our clear gains on portfolio and shortest path validate choosing PolyStep within this class. Furthermore, our ablations confirm that cost-weighted updates can beat simpler rules at the same per-step solver budget (Table 20), which essentially demonstrates the effectiveness of the search strategy.

Districting comparison establishment

Because both implementations use the full precomputed district-cost table at this scale, the experiment does not test the savings of evaluating only queried districts. Instead, we show that we can learn competitive districtings without optimal partition targets. While directly benchmarking regimes where reference generation is prohibitive would further strengthen the practical case, our current results already establish effective learning from decision costs alone.

Overall, your perspective has been greatly helpful for us to connect the findings to the applications where they matter most. Thank you again for the constructive discussion, and please let us know if you have any further thoughts.

Comments on the paper

3 comments

Thank you to the reviewers for the time and constructive feedback devoted to our paper. We provide this summary of our revision for the Area Chair and reviewers, outlining how we clarified our contribution, streamlined the presentation, and stated the limits of our evidence.

PolyStepOR applies the existing PolyStep optimizer to decision-focused learning through realized decision costs without optimal training targets or derivatives. In the revised manuscript, we clearly separate the inherited optimizer from our DFL cost-oracle formulation and analysis of prediction margins, batch aggregation, and decision changes. Section 4.2 now introduces the search coordinates before the update, reference-cost invariance is presented as a remark, and the optional momentum update has been moved to Appendix A.5.

Our experiments demonstrate useful, problem-dependent decision quality across classical benchmarks, predicted constraints, and real-world case studies. To address reviewer questions, we added equal solver-call comparisons against six derivative-free optimizers, component ablations, hyperparameter sensitivity and inexact-solve studies, and a complete districting compute comparison that includes reference generation. The revision makes solver-call costs and performance gaps relative to established DFL methods explicit. Finally, our theory gives local decision-boundary conditions and a conditional stationarity bound with a bias residual, without guaranteeing optimal decisions or convergence of the practical configurations.

We have uploaded the revised manuscript again with all the revised content. We apologize for the confusion.

Area_Chair_zDnLOpenReview ↗

Reminder: Reviewer–Author Discussion

Thank you to the reviewer who have already engaged in the discussion and provided valuable feedback. As the discussion deadline is approaching, I would kindly encourage the remaining reviewers to review the authors' responses and share their follow-up comments, particularly on whether their concerns have been adequately addressed.

Authors are also encouraged to respond promptly to any further questions.

Thank you all for your time and contributions to a constructive discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.