acceptodds
Under review as a conference paper at ICLR 2027

Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback

Abstract

Decision-focused learning (DFL) trains predictive models by optimizing downstream decision quality rather than standalone prediction accuracy. For contextual linear optimization, most existing DFL methods assume offline data and full observations of the objective cost vector. We develop an on-policy learning method for sequential contextual linear optimization under partial feedback, generalizing the standard bandit feedback setting. Our method learns a stochastic predict-then-optimize policy that samples a cost-vector prediction from a conditional distribution and solves the resulting downstream linear optimization problem. To update this distributional model, we introduce a two-component hybrid gradient estimator. The first component is a score function estimator, which provides an unbiased but potentially high-variance policy gradient estimate. The second is a decision-focused plug-in component that uses an auxiliary nuisance estimate of the latent cost vector to exploit the downstream optimization structure, becoming more informative as the estimate improves. We prove an bound on the average squared policy-gradient norm, matching the standard non-convex SGD rate. Experiments on top- selection, shortest path, combinatorial pricing, and a real-data energy-scheduling benchmark show that, under bandit feedback, the hybrid gradient approach achieves lower mean cumulative regret than the contextual-bandit baselines on all four benchmarks and than linear Thompson sampling on three, and that it also works with richer conditional generative cost models.

Primary area:
optimization
Keywords:
decision-focused learning, contextual linear optimization, on-policy learning, partial feedback, contextual bandits, predict-then-optimize, policy gradients

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_uJV3OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper studies online contextual linear optimization with decision-dependent partial feedback. DFHPG samples a cost vector from a conditional predictive distribution, chooses a feasible decision through a linear optimization oracle, and combines a score-function gradient with a plug-in gradient based on an auxiliary cost estimator. The framework also incorporates decision-focused surrogates and generative predictors. Under realizability, regularity, and uniform strong convexity of nuisance estimation, the authors establish O(1/T)O(1/\sqrt{T}) stationarity bounds. Experiments on top-kk selection, shortest path, combinatorial pricing, and electricity scheduling evaluate cumulative regret against contextual- and linear-bandit baselines, supplemented by component, surrogate, model, and feedback ablations.

Critical strengths
  1. Under its assumptions, the shared nuisance minimizer yields a clean conversion of online estimation regret into policy-gradient bias, providing a principled analysis of coupled updates.

  2. Four benchmarks, including real electricity data, and extensive ablations provide useful evidence about the method’s performance and the feedback regimes where its components help.

Critical weaknesses
  • The theoretical assumptions leave central identification and exploration difficulties unresolved. Assumption 6(iii) requires the nuisance population loss to be strongly convex in all nuisance parameters, uniformly over every policy. For shortest-path actions satisfying Aw=bAw=b (Appendix F.2), there are nonzero edge-cost perturbations that leave every feasible path’s total cost unchanged. Consequently, an unrestricted linear nuisance model already has unidentifiable directions under pure bandit feedback, regardless of exploration. An identifiable parameterization or an analysis of projected error is needed; neither is specified. Fixed positive Gaussian sampling variance also does not ensure a uniform information bound when unrestricted policy means can drive some action probabilities toward zero.

  • The experiments do not sufficiently isolate the benefit of the proposed hybrid update. Table 1 uses Gaussian-linear policy models, while DFHPG additionally uses a neural-network nuisance estimator (Section 2.4 and Appendix J.2). The main prediction-based and linear-bandit competitors use linear cost models. On the strongly nonlinear synthetic generators, this extra predictor could materially affect performance. Sharing contexts, feedback, and the optimization oracle therefore does not isolate the learning update as claimed in Section 3.2. A particularly informative missing control is a policy that acts directly on the same neural nuisance predictor, with comparable exploration and tuning.

Questions for authors
  1. Which pairwiseDiff gradient was implemented? Appendix G.3, p. 25, line 1316, gives a negative sign for pairwiseDiff. If aa denotes a solution-pair difference, differentiating the squared pairwise-gap error with respect to the predicted cost gives 2⟨c^−c,a⟩a2\langle\hat c-c,a\rangle a, up to averaging. The displayed expression has the opposite sign under the stated gradient-descent convention. This follows directly from the loss in Mandi et al. (2022), Equation (13). Is this a typesetting error or the implemented update? Since Table 2 selects this surrogate for the main top-kk and shortest-path experiments, please identify which update produced Table 1 and whether any results change.

  2. When does the key nuisance assumption hold? Can you provide a nontrivial policy/nuisance parameterization for the studied structured problems that satisfies Assumption 6(iii), accounting for the shortest-path feedback nullspace and maintaining a uniform exploration bound? The closest offline precursor, Hu et al. (2025), Sections 4.1 and 5.1, explicitly accommodates rank-deficient feedback matrices and controls projected nuisance error. Is a comparable restriction intended here? Please also identify whether any reported stationarity experiment uses the estimator, objective, and nuisance conditions covered by the corresponding theorem.

  3. Does the advantage survive a matched nuisance-based baseline? Please specify the nuisance architecture and compare DFHPG with directly optimizing predictions from the same nuisance model, trained from the same feedback with comparable exploration. What validation budgets and selected hyperparameters were used for the baselines, including the noise/prior scales of OFUL and LinTS? This would clarify whether the gains come from the policy update or the additional model capacity and tuning.

  4. How much does the score component add after independent tuning? Were DFHPG-0 and DFHPG-1 independently tuned with the same validation budget as DFHPG, including surrogate choice and learning rates? Can you report paired regret differences and uncertainty intervals against the independently tuned plug-in-only method? The existing fixed-weight and surrogate ablations are useful, but they leave this comparison unresolved.

4 comments

Thank you for the careful review. We answer Q2 (theory) in a separate comment.

Q1. pairwiseDiff sign. The implemented update has the correct sign; no result changes. In App. G.3, the "−" in 𝒫ₜ⁻ was a superscript for the pool without its best solution w_b. The term itself, (2/(|𝒫ₜ|−1)) Σ_{r≠b} Δ_br (w_b − w_r), has a positive sign and is the derivative of Eq. 13 in [1]. The revision drops the superscript and sums over r ≠ b.

W2/Q3. Matched baselines and tuning. In matched comparisons, the policy update helps on energy and pricing, and with a linear cost model DFHPG has lower regret than the contextual-bandit baselines. You are right that sharing contexts, feedback and the oracle does not isolate the learning update, so we removed that claim. DFHPG's nuisance is a two-layer, 256-unit ReLU network. Each comparison fixes the cost model: (i) your control: greedy and Gaussian-perturbed actions on DFHPG's nuisance; (ii) DFHPG with a linear nuisance against the linear baselines; (iii) DFHPG with a Gaussian neural network (NN) against the contextual-bandit baselines on the same 128-unit network.

Mean regret, 30 replications, bandit feedback:

MethodTop-kShortest pathPricingEnergy
DFHPG1.19e51.51e67.00e43.85e7
(i) Greedy, DFHPG's nuisance1.35e51.48e67.83e45.62e7
(i) Perturbed, DFHPG's nuisance1.40e51.61e67.89e45.54e7
(ii) DFHPG, linear nuisance1.36e51.84e67.69e43.40e7
(ii) Best tuned linear bandit1.70e5 (OFUL)1.44e6 (LinTS)7.00e4 (LinTS)5.50e7 (LinTS)
(iii) DFHPG, Gaussian NN1.32e51.59e67.71e47.73e7
(iii) Best baseline, same NN7.98e4 (TSCB)1.67e6 (TSCB)7.33e4 (TSCB)9.36e7 (GreedyCB)

At the controls' budget, DFHPG with score-function weight α = 0 has lower regret than both on energy, by 1.99e7 [7.79e6, 3.14e7] and 1.91e7 [7.35e6, 2.98e7] (95% confidence intervals, CIs), in 24 of 30 replications each. On pricing the selected DFHPG is lower in 29 and 28 of 30 (α = 0 alone, 18 of 30). On top-k and shortest path we detect no difference (p ≥ 0.30).

With matched capacity (Table 1), a linear nuisance keeps DFHPG below the linear contextual-bandit baselines except on pricing, and below OFUL and LinTS on top-k (20 and 21 of 30) and LinTS on energy (29 of 30); OFUL and LinTS are lower on shortest path, and LinTS on pricing. With the neural network, as [2, 3] predict for a nearly well-specified cost model, shortest path and energy show no significant difference, and GreedyCB and TSCB are lower on top-k (p < 10⁻³) and pricing (p ≈ 0.03).

Every baseline is now tuned on DFHPG's validation runs, over learning rates and noise and exploration scales (previously DFHPG's values, with exploration probability ε = 0.1): 256 configurations on 10 validation runs for top-k and shortest path, 32 on 5 for pricing and energy. DFHPG's search is larger because it has more hyperparameters, but its α = 0 search alone has the contextual-bandit baselines' budget. OFUL and LinTS tune their scale over {0.1, 0.3, 1, 3}; validation selects 0.1 except for OFUL on top-k and LinTS on energy (both 1).

Q4. Unclear benefit of the hybrid gradient. DFHPG is a family over the score-function weight α, from DFHPG-0 (α = 0) to DFHPG-1 (α = 1); its contributions hold at α = 0, and validation now selects α, including both end points (general comment, item 1). The end points previously reused DFHPG's configuration with α fixed; each now has its own search at the baselines' budget, including both learning rates and, for α = 0, the surrogate. At equal budget, adaptive α (decaying from α_max toward α_min as the nuisance improves) has lower final regret than tuned α = 0 on pricing, a lower mean on energy and no significant difference elsewhere; the score term helps most early in the run (general comment, item 2). The table gives adaptive α (same candidates) minus tuned α = 0: paired mean over 30 replications, 95% CI (replications where adaptive α is lower).

BenchmarkAdaptive α − α = 0
Top-k+1.16e4 [−1.32e4, 3.57e4] (12)
Shortest path+2.07e4 [−1.07e5, 1.52e5] (16)
Pricing−5.52e3 [−6.29e3, −4.69e3] (29)
Energy−1.18e7 [−2.25e7, −2.70e6] (13)

α = 1 has higher regret on every benchmark. The selected DFHPG is lower than α = 0 on pricing because of its configuration: setting α = 0 in it changes regret by +1.8e2 [−5.4e2, 8.9e2] (p = 0.64; Table 13).

In the revised PDF: Q1 in App. G.3; Q3 in Table 1, Fig. 1(a), App. I, J.6 and K (Table 14); Q4 in Sec. 3.4 (Table 3) and App. K (Table 11).

References

[1] Mandi, Bucarey, Mulamba, Guns. Decision-focused learning: through the lens of learning to rank. ICML 2022.

[2] Elmachtoub, Lam, Zhang, Zhao. Estimate-then-optimize versus integrated-estimation-optimization versus sample average approximation. arXiv:2304.06833, 2023.

[3] Hu, Kallus, Mao. Fast rates for contextual linear optimization. Management Science, 2022.

W1/Q2. Assumption 6(iii), identifiability, and exploration.

Under bandit feedback, a linear nuisance restricted to the span of the feasible decisions, with a bounded-mean Gaussian policy, satisfies Assumption 6(iii) on the paper's binary decision sets (revised Remark C.1), and a new shortest-path run that meets Theorem 2.3's conditions is consistent with the O(T^{-1/2}) rate. Thank you for this careful analysis. The shortest-path null space you point out changes no decision cost, so it affects neither the policy gradient nor the regret. Restricting the nuisance to the span removes the redundant parameters; this is the online counterpart of the projected-error control in [1].

The null space does not affect the feedback, the regret or the gradient. Let 𝒲 be the set of feasible decisions and P the orthogonal projection onto their span. On the 5 × 5 grid this span has dimension 17 of 40; the other 23 directions are the edge-cost perturbations you describe. Every feasible decision w satisfies wᵀc = wᵀPc, so the bandit feedback, the regret and the expected decision cost V^cost depend on the cost only through Pc. The plug-in gradient likewise depends on the nuisance f_φ only through P f_φ: with p_θ the policy density and w*_θ(x) the expected decision under it, E[∇_θ log p_θ] = 0, so the columns of ∇_θ w*_θ(x) lie in span(𝒲 − 𝒲). The bandit problem with cost c is therefore the same as the one with cost Pc, whose conditional mean is P f*, with f*(x) = E[c | x].

A linear nuisance on the span satisfies the assumption. Take a nuisance that is linear in its parameters, with its output restricted to the span: f_φ(x) = UΓψ(x), where U is an orthonormal basis of span(𝒲), ψ is bounded with E[ψψᵀ] ⪰ λ_ψ I and λ_ψ > 0, and Γ lies in a compact convex set that contains a realizer of P f*. Suppose the policy explores the whole span:

(∗) E_{w∼π_θ(·|x)}[wwᵀ] ⪰ λ_w P for all x and θ.

Then the expected nuisance loss is strongly convex in Γ with constant 2λ_w λ_ψ, uniformly over policies. This is Assumption 6(iii), so Theorem 2.2 applies to the equivalent problem with cost Pc, under its other assumptions and the projected SGD update of Algorithm 1. Theorem 2.3 also applies to the listwise ranking loss (listwiseLTR) on a fixed pool with positive temperature, because this surrogate depends on the cost only through the decision costs sᵀc. The linear nuisance of Table 1 uses ψ(x) = (1, xᵀ)ᵀ without the span restriction and is trained with Adam.

The O(T^{-1/2}) rate of Theorem 2.2(i) also extends to an unrestricted linear nuisance. Under (∗), the gradient of the plug-in objective's bias B(φ, θ) is bounded by the excess nuisance loss: ‖∇_θ B(φ, θ)‖² ≤ (L²/λ_w) × (excess loss), where L bounds ‖∇_θ w*_θ‖. This bound replaces the strong-convexity step in Proposition D.2(i), and the proof of Proposition 2.1(i) needs only convexity, which holds for any nuisance linear in its parameters.

A bounded-mean Gaussian policy explores the whole span. With a fixed sampling variance, (∗) holds once the policy mean is bounded. Take ĉ ∼ N(μ̄_θ(x), σ_G²I) with fixed σ_G > 0, bounded contexts and μ̄_θ(x) = b·tanh(Θx), so the mean stays in [−b, b]^d, with d the cost dimension. Each binary decision is a vertex of conv(𝒲), so the oracle returns it for every cost vector in a cone with nonempty interior. With fixed variance and bounded mean, each cone has Gaussian probability at least some p_min > 0 for every x and θ. Hence E[wwᵀ | x] ⪰ p_min Σ_{s∈𝒲} ssᵀ ⪰ p_min λ₊ P, where λ₊ is the smallest positive eigenvalue of Σ_s ssᵀ. Θ is unconstrained, so the SGD analysis is unchanged, and bounded contexts give Assumptions 3 and 4.

A run under the conditions of Theorem 2.3 is consistent with the rate. The earlier runs in App. J.2 show stationarity on top-k and shortest path but do not meet the conditions of either theorem: they use a neural-network nuisance trained with Adam and pairwiseDiff with a growing pool, and they plot ‖∇_θ V^cost‖², whereas Theorem 2.3 controls ‖∇_θ V^α‖², where α is the mixing weight on the score-function gradient. We therefore ran the construction above on shortest path with polynomial degree 1 and bounded contexts at α = 0. The run uses a linear nuisance on the span updated by projected SGD, the bounded Gaussian policy, and listwiseLTR over all 70 paths, with both step sizes of order T^{-1/2} as in the constant-step version of Theorem 2.3. Over 30 replications, the average of ‖∇_θ V^0‖² over the iterates, estimated at 40 random iterates per run, roughly halves each time T grows fourfold:

T8,00032,000128,000512,000
Average of ‖∇_θ V^0‖²6.233.541.820.86
√T × average of ‖∇_θ V^0‖²557634651619

The log-log slope is −0.48 (95% confidence interval [−0.49, −0.46]), consistent with the O(T^{-1/2}) bound (App. J.2).

References

[1] Hu, Kallus, Mao, Wu. Contextual linear optimization with bandit feedback. NeurIPS, 2024.

Thank you for the detailed response and revisions, which addresses my theoretical concern. The matched-nuisance controls and independently tuned comparisons also address my experimental concern. The score term’s benefit remains limited and configuration-dependent, but the revised claims appropriately reflect this. Overall, my main concerns have been substantially addressed.

Thank you for taking another look at our responses and revised manuscript. We're glad that the additional theoretical clarifications and experimental comparisons addressed your main concerns. We really appreciate your careful feedback, which has helped us improve the paper.

Reviewer_Fkz5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies online contextual linear optimization under partial feedback. A known observation matrix covers bandit, semi-bandit, and full-information feedback. The policy samples a predicted cost vector and selects a decision through a linear optimization oracle. Its update combines a REINFORCE gradient with a decision-focused plug-in or surrogate gradient, using a nuisance model trained on the observed feedback.

The authors bound nuisance estimation error and establish an O(T−1/2)O(T^{-1/2}) bound on the average squared gradient norm. Experiments cover top-k selection, shortest path, combinatorial pricing, and real-data energy scheduling.

Critical strengths

S1. Generality w.r.t. feedback type.

The framework preserves the downstream optimization structure while accommodating several partial-feedback regimes. It uses a linear optimization oracle and supports richer conditional cost models, including neural, flow, and diffusion models.

S2. Extensive experiments and useful ablations.

The evaluation covers four benchmarks, including real-data energy scheduling, and examines both gradient components, alternative surrogates, distributional models, and feedback regimes. The authors also report settings where the hybrid loses to existing baselines or the plug-in-only variant, which helps assess its practical limitations.

Critical weaknesses

W1. Unclear benefit of the hybrid update.

The additional benefit of combining the score-function and plug-in gradients is not consistently established. In Figure 5, the plug-in-only variant achieves a lower best reported mean regret than the hybrid on top-k and energy. This suggests that the advantage of mixing depends on the surrogate choice.

Comparing the hybrid, score-only, and plug-in-only variants with each independently tuned on validation data under comparable budgets would better isolate the contribution of combining the two in the hybrid mode. These experiments would clarify whether mixing provides a consistent benefit beyond a well-tuned plug-in update.

W2. Missing dedicated semi-bandit baselines.

Under semi-bandit feedback, the evaluation includes adaptations of contextual-bandit baselines, but no dedicated contextual combinatorial semi-bandit algorithms. Comparisons with methods such as contextual CombLinUCB or CombLinTS would strengthen the evaluation and clarify whether the proposed approach is competitive with methods designed to exploit coordinate-level feedback.

Questions for authors

Q1. Were DFHPG, DFHPG-0 (plug-in-only), and DFHPG-1 (score-only) tuned independently with comparable validation budgets?

Q2. How does DFHPG compare with dedicated contextual combinatorial semi-bandit methods, such as contextual CombLinUCB or CombLinTS, under semi-bandit feedback?

4 comments

Thank you for the careful review. We ran both comparisons you suggested; they improved the paper and changed how it presents the method (general comment, items 1, 2 and 5).

Q1/W1. Unclear benefit of the hybrid gradient. DFHPG is a family of policy gradients that weight a plug-in gradient against a score-function gradient by α ∈ [0, 1], with end points DFHPG-0 (α = 0) and DFHPG-1 (α = 1), and the revision presents it this way: validation now selects α, including both end points, and every contribution holds at α = 0. Tuned separately, α = 1 has higher regret than α = 0 on every benchmark, and at equal budget adaptive α has lower regret than α = 0 on pricing, a lower mean on energy and no significant difference on top-k and shortest path. In the submission, DFHPG-0 and DFHPG-1 reused DFHPG's configuration with α set to 0 or 1. Now each has its own random search over DFHPG's other hyperparameters (for α = 0, including both learning rates and the surrogate loss), with the submitted budget (smaller on energy). To test mixing at equal budget, adaptive α uses the same candidates as α = 0, adding only the adaptive mixing weight, which decays α from α_max toward α_min as the nuisance becomes reliable. The table reports each variant's regret minus that of α = 0, paired over 30 replications (95% confidence interval (CI) in brackets; negative favors the variant):

BenchmarkAdaptive α (same candidates)α = 1
Top-k+1.16e4 [−1.32e4, 3.57e4]+2.73e5 [2.09e5, 3.45e5]
Shortest path+2.07e4 [−1.07e5, 1.52e5]+3.02e5 [1.65e5, 4.40e5]
Pricing−5.52e3 [−6.29e3, −4.69e3]+8.46e3 [7.53e3, 9.45e3]
Energy−1.18e7 [−2.25e7, −2.70e6]+5.74e7 [3.53e7, 8.06e7]

Adaptive α has lower regret on pricing in 29 of 30 replications. The selected DFHPG is also lower than α = 0 on pricing because of its configuration: removing its score term makes no detectable difference (+1.8e2 [−5.4e2, 8.9e2], p = 0.64; Table 13).

The score term can still help early. In the submitted top-k configuration, α = 0.25 lowers cumulative expected cost by 10.6% at t = 200, though not significantly at T = 2000 (general comment, item 2). At α = 0, DFHPG keeps the online coupled update of the policy and its nuisance, the theory, and the distributional cost models.

Validation selects α = 0 on top-k and shortest path and the submitted configuration on pricing and energy, never α = 1. We removed the sentences that ranked the hybrid above α = 0. The main DFHPG row in Table 1, which uses a multilayer perceptron (MLP) nuisance, is the configuration with the lowest validation regret over the union of the α = 0, α = 1, constant-α and adaptive-α searches, which includes the submitted configuration. Your reading of Fig. 5 is also correct: with some surrogates α = 0 does better, and the α = 0 search now tunes the surrogate.

Q2/W2. Dedicated semi-bandit baselines. We added CombLinUCB and CombLinTS; DFHPG has lower regret than both on top-k, shortest path and energy (29 or 30 of 30), and both have lower regret on pricing. Both use DFHPG's contexts, feedback and linear oracle with ridge models on the observed coordinates, and their exploration scale is tuned on the same validation runs as DFHPG; App. I.1 states both budgets. The table reports baseline minus DFHPG regret over 30 replications and the number of replications in which DFHPG is lower:

BenchmarkDFHPG regret, tuned (submitted configuration)CombLinUCB − DFHPG (95% CI)CombLinTS − DFHPG (95% CI)
Top-k2.24e4 (7.10e4)+3.08e4 [2.15e4, 4.19e4], 29/30+2.33e4 [1.70e4, 3.15e4], 30/30
Shortest path5.10e5 (6.83e5)+2.52e5 [2.03e5, 3.04e5], 30/30+2.26e5 [1.87e5, 2.64e5], 29/30
Pricing5.11e4 (5.19e4)−4.68e3 [−5.01e3, −4.33e3], 0/30−4.95e3 [−5.21e3, −4.69e3], 0/30
Energy2.09e7 (2.35e7)+1.72e7 [1.68e7, 1.75e7], 30/30+1.69e7 [1.65e7, 1.73e7], 30/30

With an MLP nuisance, DFHPG's regret is 51%, 31% and 45% below that of CombLinTS on top-k, shortest path and energy. With a linear nuisance, which matches the capacity of the baselines' ridge models, DFHPG has lower regret than both only on energy (25 of 30).

In the revised PDF, Q1 is in Sec. 3.4 (Table 3) and App. K (Table 11), with the selection of α in Sec. 3.2 and Table 1 and the surrogate search in App. I; Q2 is in Table 2, Fig. 1(b, c) and App. H.

We would be glad to clarify anything further.

Dear Reviewer Fkz5,

Thank you again for your thoughtful feedback and helpful suggestions. We just wanted to follow up as the discussion period is coming to a close today.

We've added both comparisons you suggested: independently tuned gradient variants and dedicated semi-bandit baselines. We hope these additions help address your concerns, and we'd really appreciate hearing your thoughts. We're happy to clarify anything that remains unclear. Thank you again for your time and consideration!

Reviewer_Fkz5OpenReview ↗

Thank you for your answer!

Many thanks to the authors for the detailed response and additional experiments. W2 is fully addressed, and I appreciate the transparent reporting of both positive and negative results. However, the additional experiments reinforce my earlier skepticism regarding the benefit of the hybrid component. This weakens the case for algorithmic novelty, and thus I will therefore maintain my score.

Thank you for following up and for confirming that W2 has been fully addressed. We appreciate your careful consideration of our additional experiments.

We respectfully disagree that the limited additional benefit of the hybrid component substantially weakens the paper's algorithmic novelty. Our main contribution is a new on-policy decision-focused learning method for contextual linear optimization under partial feedback, not just the mixing of two gradient estimators.

In response to your concerns, we have revised how we position and evaluate the method, without changing the underlying algorithm or its main theoretical results. Specifically, we revised the abstract and contributions to emphasize on-policy DFL, with the score-function term presented as optional. Table 1 now reports DFHPG with α selected through validation, including both endpoints α = 0 and α = 1, rather than treating the hybrid and its two endpoints as separate headline methods. We moved the independently tuned DFHPG-0 and DFHPG-1 comparisons to Section 3.4 (Table 3), where we explicitly examine when mixing helps and when the plug-in-only update is preferable. We also strengthened the evaluation with tuned baselines and dedicated semi-bandit comparisons. These changes provide a more accurate assessment of the method while preserving its original contributions.

We would like to reemphasize two central contributions:

  1. Methodologically, we introduce an on-policy DFL algorithm that directly trains a conditional distribution over cost vectors for downstream decision quality. The distribution induces a stochastic decision policy through the optimization oracle, while an auxiliary nuisance model learns from the policy's own partial feedback and supplies decision-focused gradients. This enables joint online learning of the distributional policy and nuisance estimator, rather than simply optimizing decisions using fitted cost predictions. The framework supports a broad range of DFL surrogates and distributional predictors, including Gaussian linear and neural models, conditional normalizing flows, and diffusion models.

  2. Theoretically, we analyze the two-way dependence between the policy and nuisance estimator. By exploiting a common minimizer of the policy-dependent nuisance losses, we convert online nuisance-estimation regret into a bound on policy-gradient bias, establishing O(T−1/2)O(T^{-1/2}) stationarity under the stated assumptions, including at α = 0.

These contributions were already present in the original submission, including the α = 0 update in Algorithm 1 and its theoretical guarantees. Our revision makes their central role clearer and provides stronger experimental evidence, without changing the core methodology.

Thank you again for your constructive feedback. We hope you will reconsider your assessment of algorithmic novelty in light of these contributions and the revised evidence.

Reviewer_RvSdOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Decision-focused learning optimizes downstream decisions by predicting costs, focusing on decision quality rather than prediction accuracy, but existing methods mostly assume offline data with full observations of the cost vector. This paper extends it to an online setting with partial feedback, where only the feedback of the implemented decision is observed. The paper introduces a technique that predicts the cost and at the same time optimizes the policy based on it. In this process, two gradient estimators for the policy are used: one is an unbiased policy gradient estimate with high variance, and the other is a gradient computed with a learned prediction model of the cost vector, which may be biased but has small variance. By using these in a hybrid manner, it simultaneously learns the cost model and optimizes the policy, eventually giving a distribution over cost predictions that, through the solver, induces a decision policy that reduces the actual cost, with a guarantee of first-order stationarity at rate O(T−1/2)O(T^{-1/2}).

Critical strengths

A practically relevant and novel setting: Existing decision-focused learning (DFL) methods mostly assume offline data with full observations of the cost vector. This paper addresses the online setting with partial feedback, where the learner must predict costs from the context and optimize its policy based on these predictions while observing only the feedback of its own decisions, and it provides a solution for this setting.

Hybrid gradient to compensate for nuisance bias: Without full observations, the cost must be estimated with a nuisance model, and the resulting plug-in gradient can be substantially biased, especially early in learning. To compensate, the paper mixes in the unbiased score function (REINFORCE) gradient that uses the observed cost, which reduces the bias of the overall policy gradient. This makes it possible to use DFL surrogates under partial feedback, and the paper establishes an O(T−1/2)O(T^{-1/2}) stationarity guarantee for this hybrid update.

Critical weaknesses

Unclear benefit of the hybrid gradient: The performance varies considerably with α\alpha across environments. Under bandit feedback, the score function term helps on top-k and shortest path, but DFHPG and the plug-in-only DFHPG-0 perform alike on energy, and under semi-bandit feedback DFHPG-0 achieves lower regret on every benchmark (Table 1). The hybrid DFHPG therefore does not consistently outperform both extremes, so the advantage of combining the two gradients is not clearly demonstrated.

Although Figure 1 suggests that the score function term helps early in training, DFHPG-0 already performs well overall, which weakens the justification for using the score function term to reduce the bias of the plug-in gradient. If the plug-in-only variant suffices, the contribution reduces largely to extending the nuisance-based plug-in approach from offline to online data, which partially reduces the novelty.

Questions for authors

Q1. In Table 1 on pricing, DFHPG appears to achieve the best performance when the two gradients are combined, but its difference from DFHPG-0 is negligible (7.00×1047.00\times10^4 vs. 7.02×1047.02\times10^4 in Table 1). In which situations or problems does using the score function term, as in DFHPG or DFHPG-1, yield significantly better performance, and does this actually hold empirically? An analysis of when and why the score function term helps would strengthen the contribution of the paper.

Q2. The mixing-weight schedule of DFHPG depends on several hyperparameters in Appendix G.2, which are tuned separately for each benchmark (Tables 2 and 3). Could the authors clarify whether the benefit of the schedule justifies this additional tuning burden?

3 comments

Thank you for the thoughtful review and for finding the setting relevant and novel. Your main question led to the first item of our general comment.

W1/Q1. Unclear benefit of the hybrid gradient. DFHPG is a family of policy gradients that weight a plug-in gradient against a score-function gradient by α ∈ [0, 1], from pure plug-in (α = 0) to pure score function (α = 1). The revision presents it this way: validation now selects α, including both end points, Table 1 reports tuned DFHPG for each cost model, and the contributions hold at α = 0 (see below and general comment, item 1). Within this family, the score term helps early, while the nuisance has seen little data, and the gain fades by the horizon T = 2000. On top-k, we took the submitted DFHPG configuration, changed only α from 0 to 0.25, and ran 1,000 new replications. The table reports cumulative expected cost at α = 0.25 minus that at α = 0; the last column counts the replications in which this difference is negative. The tests at t = 200 and T = 2000 were fixed before the run.

tDifference [95% confidence interval (CI)]ChangeLower in
100−2.4e3 [−4.1e3, −0.8e3]−7.4%567/1,000
200−6.1e3 [−8.4e3, −3.7e3]−10.6%601/1,000
500−8.0e3 [−1.21e4, −3.9e3]−8.0%585/1,000
1000−6.9e3 [−1.22e4, −1.4e3]−5.1%571/1,000
2000−4.1e3 [−1.07e4, 2.6e3]−2.4%564/1,000

The gap is significant at t = 200 (p < 10⁻⁶) but not at T = 2000 (p = 0.23). For final regret, validation now selects α = 0 on top-k and shortest path (general comment, item 1). Tuned separately, α = 1 has higher regret than α = 0 on every benchmark.

Theorem 2.2 explains why: its bound, valid for every fixed α, has a nuisance-bias term scaled by (1−α)² and a variance term σ_α², so a positive α helps when the nuisance bias outweighs the extra variance of the score term. Under semi-bandit feedback, where the nuisance receives richer feedback, α = 0 has lower mean regret on every benchmark in the submitted configurations, as you note.

Thank you for noticing the pricing gap (7.00e4 vs 7.02e4); it is within noise: removing the score term from the submitted configuration changes regret by +1.8e2 [−5.4e2, 8.9e2] (p = 0.64). The larger gap in Sec. 3.4 (7.00e4 vs 7.65e4, Table 3) is between DFHPG and the separately tuned α = 0, whose own search selects a different configuration; the paper now says so.

Novelty if plug-in alone suffices. First, we develop on-policy decision-focused learning for online contextual linear optimization under partial feedback: the policy update is a decision-focused plug-in gradient from a nuisance cost model learned online from the policy's own feedback. It admits decision-focused surrogates such as Smart Predict-then-Optimize (SPO+). Unlike the offline, logged-data setting of [1], the nuisance trains on data the current policy generates, so its data change with every policy update. Second, our analysis handles this coupling: the true conditional mean f* minimizes the nuisance loss for every policy parameter θ, so the nuisance update is online convex optimization against a fixed comparator, and we convert its regret into a bias bound on the policy gradient, giving O(T^{-1/2}) stationarity for every α, including α = 0. Third, the distributional policy supports richer cost models than the baselines: it is a conditional distribution over cost vectors that induces decisions through linear optimization and needs only a gradient estimator, so one update trains neural, conditional normalizing flow (CNF) and diffusion cost models from bandit feedback, whereas OFUL and LinTS are limited to linear cost models. With a CNF, DFHPG has the lowest pricing regret in Table 1 (6.60e4, below LinTS in 28 of 30 replications).

Q2. Is the adaptive mixing weight worth its tuning? Validation now decides this per benchmark: it keeps the adaptive weight, which decays α from α_max toward α_min as the nuisance becomes reliable, on pricing and energy, and uses α = 0 on top-k and shortest path. The adaptive weight adds two tuned values per benchmark, α_max and α_min, plus a decay time on energy and in the pricing CNF configuration; its smoothing and moving-average constants are fixed across benchmarks. We also tried one setting common to all benchmarks (α_max = 0.5, α_min = 0.05). It equals the submitted setting on shortest path and pricing, does not differ significantly from it on top-k (p = 0.39), and has higher regret on energy (22 of 30 replications; the mean CI includes zero).

In the revised PDF, Sec. 3.2 states that α is chosen on validation, and the text no longer ranks the hybrid above its end points. The early top-k test is in Sec. 3.4 (Fig. 2) and App. K (Table 12), the pricing gap in Table 13, and the common setting in App. K.

We would be glad to clarify anything further.

References

[1] Hu, Kallus, Mao, Wu. Contextual linear optimization with bandit feedback. NeurIPS, 2024.

Thank you for the detailed response and the general comment. The top-k experiment clarifies when the score-function term helps. Selecting $ \alpha$ on validation raised a question about the fairness of the comparison, but the general comment resolves it by tuning every baseline on the same validation runs.

My main concern is now the extent of the revision. The hybrid gradient, which the submitted version presents as central, is now optional; validation selects α = 0 on two of the four benchmarks; and Table 1 has been restructured, with the headline configurations changed after the reviews. The revised contributions, namely on-policy decision-focused learning with an online nuisance model, its O(T−1/2)O(T^{-1/2}) analysis, and support for richer cost models, are reasonable, but they differ substantially from those of the submitted version, and after tuning the advantage over OFUL and LinTS is significant only on some benchmarks. I am concerned that a change of this scope is difficult to evaluate fully within the discussion period. I will keep my score.

Thank you for taking the time to review our responses and revised manuscript. We appreciate your thoughtful feedback and understand your concern about the extent of the revision. We just wanted to clarify that the core method and theoretical results remain unchanged. In particular, α = 0 was already part of Algorithm 1 and covered by the original analysis. In response to the reviews, we clarified the role of the two gradient components, tuned the variants and baselines more carefully, and updated the presentation of the results. While some selected configurations have changed, the underlying approach remains the same. Thank you again for your feedback. It has been very helpful in improving the paper.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of replies and revisions

We thank the reviewers for finding online decision-focused learning (DFL) under partial feedback relevant and novel (RvSd), the framework general (Fkz5), the conversion of nuisance regret into gradient bias principled (uJV3) and the experiments extensive (Fkz5, uJV3). Below we summarize our replies and revisions to the paper.

  1. Unclear benefit of the hybrid gradient (all reviewers). DFHPG's novelty does not rest on the hybrid, and the revision repositions the method. DFHPG is a family of policy gradients that weight a plug-in gradient against a score-function gradient by α ∈ [0, 1]: pure plug-in (α = 0, DFHPG-0), pure score function (α = 1, DFHPG-1) and hybrids in between. The abstract and contributions now present the score term as optional. Validation now also searches both end points and keeps a hybrid only where it has lower validation regret (item 2). With the multilayer perceptron (MLP) nuisance, it selects α = 0 on top-k and shortest path, so there DFHPG coincides with DFHPG-0. Table 1 now shows the framework's flexibility: it is grouped by cost model (Gaussian linear, neural, generative), with tuned DFHPG in each. The DFHPG-0 and DFHPG-1 rows moved to the Sec. 3.4 ablation, where each now has its own search (Table 3; Fkz5, uJV3). Each contribution below remains novel with the plug-in gradient alone (α = 0):

    • Setting. We develop on-policy DFL for online contextual linear optimization under bandit, semi-bandit or full-information feedback; most DFL methods assume batch data with fully observed costs.
    • Method. The policy is a conditional distribution over cost vectors that induces decisions through linear optimization. Its update is a decision-focused plug-in gradient from a nuisance cost model learned online from the policy's own partial feedback, and it admits a broad class of DFL surrogates. Needing only a policy gradient estimator, the update trains Gaussian linear, neural, conditional normalizing flow (CNF) and diffusion cost models; four of the eight generative configurations use α = 0, and with a CNF, DFHPG has the lowest pricing regret in Table 1.
    • Analysis. Unlike in the offline setting of [3], the policy generates the nuisance's data and the nuisance supplies the policy's gradient; the analysis handles this two-way dependence. The true conditional mean minimizes the nuisance loss under every policy, so the nuisance update is online convex optimization against a fixed comparator. Theorems 2.2 and 2.3 convert its regret into a bias bound on the policy gradient, giving O(T^{-1/2}) stationarity for every fixed α, including α = 0.
  2. When does the score term help? (RvSd, uJV3) Besides α = 0 and α = 1, the search covers constant α and an adaptive weight that decays from α_max to α_min as the nuisance improves. On pricing and energy it selects the adaptive weight. The score term helps most while the nuisance has seen little data: on top-k, α = 0.25 instead of 0 lowers cumulative expected cost by 10.6% at t = 200 (1,000 replications, p < 10⁻⁶) and by 2.4% (not significant) at T = 2000.

  3. Baselines and cost model (uJV3). Every baseline is now tuned on DFHPG's validation runs. With the Gaussian linear cost model and MLP nuisance, DFHPG has lower regret than ε-GreedyCB, GreedyCB and TSCB on all four benchmarks, than OFUL and LinTS on top-k, and than LinTS on energy (27 of 30); on shortest path (OFUL, LinTS) and pricing (LinTS) the differences are not significant. With the Gaussian neural cost model, DFHPG shows no advantage over baselines on the same network, as expected when the cost model is close to well specified [1, 2].

  4. Theory assumptions (uJV3). Assumption 6(iii) can be met under bandit feedback: on the paper's binary decision sets, a linear nuisance on the span of the decisions with a bounded-mean Gaussian policy satisfies it (Remark C.1). Theorem 2.2 then applies, as does Theorem 2.3 for the listwise loss on a fixed pool. This loses nothing: the feedback and regret depend on the cost only through its projection onto that span. A shortest-path run under these conditions matches the O(T^{-1/2}) rate (App. J.2).

  5. Semi-bandit baselines (Fkz5). We added CombLinUCB and CombLinTS. DFHPG with the MLP nuisance has lower regret than both on top-k, shortest path and energy (29 or 30 of 30; 51%, 31% and 45% below CombLinTS), and higher on pricing.

New experiments: validation-selected DFHPG and tuned baselines (Table 1, App. I), separately tuned variants (Table 3), early score-term benefit (Fig. 2), policy update vs its nuisance (App. K), semi-bandit baselines (Table 2, App. H). Revised text is in blue.

References

[1] Elmachtoub et al. Estimate-then-optimize versus integrated-estimation-optimization versus sample average approximation. arXiv:2304.06833, 2023.

[2] Hu et al. Fast rates for contextual linear optimization. Management Science, 2022.

[3] Hu et al. Contextual linear optimization with bandit feedback. NeurIPS, 2024.

Dear Reviewers,

Thank you again for your thoughtful feedback. We have submitted our detailed responses and a revised manuscript addressing your main concerns.

As the discussion period is approaching its end, we would greatly appreciate your feedback on whether our responses have addressed your concerns. We would be happy to clarify any remaining questions.

Thank you for your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.