- 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 stationarity bounds. Experiments on top- 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
-
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.
-
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 (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
-
Which pairwiseDiff gradient was implemented? Appendix G.3, p. 25, line 1316, gives a negative sign for pairwiseDiff. If denotes a solution-pair difference, differentiating the squared pairwise-gap error with respect to the predicted cost gives , 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- and shortest-path experiments, please identify which update produced Table 1 and whether any results change.
-
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.
-
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.
-
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
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:
| T | 8,000 | 32,000 | 128,000 | 512,000 |
|---|---|---|---|---|
| Average of ‖∇_θ V^0‖² | 6.23 | 3.54 | 1.82 | 0.86 |
| √T × average of ‖∇_θ V^0‖² | 557 | 634 | 651 | 619 |
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.
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:
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).
α = 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.