Pith. sign in

REVIEW 1 major objections 12 references

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

T0 review · 1 major / 0 minor · reviewed 2026-06-28 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A hybrid gradient estimator enables on-policy training of stochastic predict-then-optimize policies for contextual linear optimization under partial feedback.

desk verdict New hybrid on-policy estimator for distributional DFL under partial feedback, but the convergence analysis leaves the nuisance bias control implicit. read the letter →

arxiv 2606.01081 v1 pith:2HU35VW4 submitted 2026-05-31 cs.LG

Wyame Benslimane , Tinghan Ye , Pascal Van Hentenryck , Paul Grigas This is my paper · ORCID
classification cs.LG
keywords decision-focusedlearningon-policypartialfeedbackcontextualoptimizationhybridgradientestimatorpredict-then-optimizestochasticpolicylinear
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces an on-policy learning method for training predictive models in sequential contextual linear optimization problems where only partial feedback on costs is observed. Instead of predicting costs accurately in isolation, it optimizes directly for downstream decision quality by sampling predictions from a conditional distribution and solving the linear program. The update uses a hybrid gradient that mixes an unbiased score-function term with a plug-in term based on an improving auxiliary cost estimate, which becomes more useful as learning progresses. This yields a convergence rate of O(T^{-1/2}) on the squared policy gradient norm and empirically lower regret than standard contextual bandit methods on benchmarks including top-k selection, shortest paths, pricing, and energy scheduling.

What carries the argument

The two-component hybrid gradient estimator consisting of a score function estimator for unbiasedness and a decision-focused plug-in component that exploits the downstream optimization structure using an auxiliary nuisance estimate of the latent cost vector.

What would settle it

A trial in which the auxiliary cost estimator fails to improve, resulting in the hybrid estimator performing no better than the pure score function estimator on regret metrics, would falsify the claimed advantage of the hybrid approach.

Watch

Extended reading notes

Core claim

The paper claims that the hybrid gradient estimator enables on-policy learning of stochastic predict-then-optimize policies for contextual linear optimization under partial feedback, achieving an O(T^{-1/2}) bound on the average squared policy-gradient norm and lower cumulative regret than contextual-bandit baselines across multiple benchmarks.

Load-bearing premise

The method assumes that an auxiliary nuisance estimator of the latent cost vector can be maintained and that its quality improves sufficiently over time to make the plug-in component informative.

Editorial extensions

If this is right

  • The approach generalizes the standard bandit feedback setting to contextual linear optimization.
  • It achieves an O(T^{-1/2}) bound on the average squared policy-gradient norm, matching standard non-convex SGD rates.
  • The hybrid method achieves lower cumulative regret than contextual-bandit-style baselines on top-k selection, shortest path, combinatorial pricing, and energy-scheduling benchmarks.
  • The method works with both Gaussian and richer conditional generative models for sampling cost-vector predictions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The on-policy nature could allow the policy to adapt in real-time to changing contexts without requiring offline data collection.
  • Extending the hybrid estimator to other decision-focused settings might improve learning efficiency when full cost observations are costly.
  • The improvement of the plug-in component over time suggests a natural curriculum where early updates rely more on the score function and later ones on the structure.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 0 minor

Summary. The paper develops an on-policy method for learning stochastic predict-then-optimize policies in contextual linear optimization under partial (bandit) feedback. It introduces a hybrid gradient estimator combining a score-function term with a decision-focused plug-in term that uses an auxiliary nuisance estimator of the latent cost vector. The central theoretical result is an O(T^{-1/2}) bound on the average squared policy-gradient norm; experiments on top-k selection, shortest path, combinatorial pricing, and energy scheduling report lower cumulative regret than contextual-bandit baselines, with code released.

Significance. If the hybrid estimator analysis can be completed with explicit controls, the work would usefully extend decision-focused learning to realistic online partial-feedback regimes while recovering the standard non-convex SGD rate. The multi-benchmark evaluation and public code are concrete strengths that would support adoption if the theoretical gap is closed.

major comments (1)
  1. [Convergence analysis] Convergence analysis (proof of the O(T^{-1/2}) bound on average squared policy-gradient norm): the hybrid estimator is defined precisely so that the plug-in term 'becomes more informative as the estimate improves,' yet the derivation does not state or control the required convergence rate of the auxiliary nuisance estimator of the full latent cost vector. Under the partial-feedback observation model, consistent recovery of the entire cost vector is not automatic; if the nuisance error decays slower than the step-size schedule, the bias term can dominate and the stationary-point guarantee fails to hold.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a gap in the convergence analysis. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: Convergence analysis (proof of the O(T^{-1/2}) bound on average squared policy-gradient norm): the hybrid estimator is defined precisely so that the plug-in term 'becomes more informative as the estimate improves,' yet the derivation does not state or control the required convergence rate of the auxiliary nuisance estimator of the full latent cost vector. Under the partial-feedback observation model, consistent recovery of the entire cost vector is not automatic; if the nuisance error decays slower than the step-size schedule, the bias term can dominate and the stationary-point guarantee fails to hold.

    Authors: We agree this is a substantive gap: the current proof does not explicitly bound the nuisance estimation error under the partial-feedback model. In the revision we will (i) state an explicit assumption on the nuisance estimator's convergence rate (e.g., that its error is o(η_t) where η_t is the policy step-size schedule), (ii) show that this rate is achievable when the context distribution satisfies standard identifiability conditions for linear costs, and (iii) verify that the resulting bias term remains dominated by the O(T^{-1/2}) stationary-point guarantee. If the assumption proves too strong for some regimes, we will also add a remark clarifying the limitation. These changes will be incorporated into the theorem statement, proof, and discussion sections. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation applies standard non-convex rate to hybrid estimator

full rationale

The paper states an O(T^{-1/2}) bound on average squared policy-gradient norm for the hybrid estimator (score-function plus decision-focused plug-in), explicitly matching the standard non-convex SGD rate. No equations reduce the bound or regret claims to a quantity defined in terms of itself, nor does the analysis rename a fitted input as a prediction. The nuisance estimator improvement is invoked as an assumption enabling the plug-in term but is not derived from the policy update or shown to be self-referential. Experiments compare against external baselines rather than self-generated quantities, and no load-bearing self-citations or uniqueness theorems from prior author work are referenced in the claims. The derivation chain is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The central claim rests on the existence of a well-behaved auxiliary nuisance estimator whose quality improves with data, the validity of the score-function gradient for the chosen conditional distribution family, and standard assumptions on the linear optimization problems being solved at each step. No new entities are postulated.

assumptions (2)
  • domain assumption An auxiliary nuisance estimator of the latent cost vector exists and improves over time, making the plug-in component increasingly informative.
    Invoked in the description of the hybrid gradient estimator.
  • domain assumption The policy is a stochastic predict-then-optimize mapping from a conditional distribution over cost vectors to an action obtained by solving the downstream linear program.
    Core modeling choice stated in the method description.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback." pith.science (2026). https://pith.science/paper/2HU35VW4

@misc{pith2026260601081,
  author       = {Pith},
  title        = {Pith review of: Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2HU35VW4}},
  note         = {Machine review of arXiv:2606.01081}
}
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 $\mathcal{O}(T^{-1/2})$ bound on the average squared policy-gradient norm, matching the standard non-convex SGD rate. Experiments on top-$k$ selection, shortest path, combinatorial pricing, and a real-data energy-scheduling benchmark show that the hybrid gradient approach achieves lower cumulative regret than contextual-bandit-style baselines across all benchmarks, using both Gaussian and richer conditional generative models. Code is available at https://github.com/Joeyetinghan/on-policy-bandit-dfl.

Figures

Figures reproduced from arXiv: 2606.01081 by the authors.

Figure 1
Figure 1. Zoomed convergence plot for top-k selection (first 600 iterations). Each curve re￾ports average regret per iteration, with shaded ±1 standard-error bands across replications. 0 2000 4000 6000 8000 10000 12000 14000 Iteration 10 20 30 40 50 60 70 80 Avg. regret per iter. Gaussian Linear Gaussian NN CNF Diffusion [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 3
Figure 3. Convergence plots for shortest path, pricing, and energy scheduling. Synthetic benchmarks [PITH_FULL_IMAGE:figures/full_fig_p026_3.png] view at source ↗
Figure 4
Figure 4. Comparison of distributional cost models on top- [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗
Figures from the paper (4 more)
Figure 5
Figure 5. Figure 5: Surrogate-loss comparison across the four benchmark problems. Each heatmap reports [PITH_FULL_IMAGE:figures/full_fig_p029_5.png]
Figure 6
Figure 6. Figure 6: Mixing-weight ablation comparing the adaptive [PITH_FULL_IMAGE:figures/full_fig_p030_6.png]
Figure 7
Figure 7. Figure 7: Sensitivity across problem difficulty under moderate noise for pricing, shortest path, [PITH_FULL_IMAGE:figures/full_fig_p031_7.png]
Figure 8
Figure 8. Figure 8: Feedback mode comparison across the four benchmarks. Each plot compares final [PITH_FULL_IMAGE:figures/full_fig_p032_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 1 canonical work pages

  1. [1]

    Abbasi-Yadkori, Y ., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits.Advances in neural information processing systems,

    2011

  2. [2]

    predict, then optimize

    Abernethy, J., Hazan, E., and Rakhlin, A. (2008). Competing in the dark: An efficient algorithm for bandit linear optimization. InProceedings of the 21st Annual Conference on Learning Theory, pages 263–273. Bennouna, O., Bennouna, A., Amin, S., and Ozdaglar, A. (2025). What data enables optimal decisions? an exact characterization for linear optimization....

    work page arXiv 2008

  3. [3]

    Konda, V . R. and Tsitsiklis, J. N. (2000). Actor-critic algorithms. InAdvances in Neural Information Processing Systems. Kreutzer, J., Sokolov, A., and Riezler, S. (2017). Bandit structured prediction for neural sequence-to- sequence learning. InProceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 1503–1513. Kris...

    2000

  4. [4]

    Applying the triangle inequality,∥w ⋆(ˆc)∥ ≤BS, and (12) yields ∥∇θw⋆ θ(x)− ∇ θw⋆ θ′(x)∥ ≤B S Z ∥∇θpθ(ˆc|x)− ∇ θpθ′(ˆc|x)∥dˆc≤B S M∇ ∥θ−θ ′∥

    and (11), ∥∇θw⋆ θ(x)∥ ≤ Z ∥w⋆(ˆc)∥ ∥∇θpθ(ˆc|x)∥dˆc≤B S Z ∥∇θpθ(ˆc|x)∥dˆc≤B S M, Lipschitz continuity.Subtracting the integral representations atθandθ ′, ∇θw⋆ θ(x)− ∇ θw⋆ θ′(x) = Z w⋆(ˆc) ∇θpθ(ˆc|x)− ∇ θpθ′(ˆc|x) ⊤ dˆc. Applying the triangle inequality,∥w ⋆(ˆc)∥ ≤BS, and (12) yields ∥∇θw⋆ θ(x)− ∇ θw⋆ θ′(x)∥ ≤B S Z ∥∇θpθ(ˆc|x)− ∇ θpθ′(ˆc|x)∥dˆc≤B S M∇ ∥θ−θ ...

    2019

  5. [5]

    At the beginning of period t, the context is drawn as xt ∼ N(0, I p), with default p= 25

    At environment initialization, each product i is assigned a fixed latent direction bi ∈R p, sampled once and row- normalized. At the beginning of period t, the context is drawn as xt ∼ N(0, I p), with default p= 25 . Let kc and kp control the context and price nonlinearities, with kc =k p = deg in the paper experiments. For each product–price pair (i, ℓ),...

    2024

  6. [6]

    Algorithm 2:Greedy contextual bandit (GREEDYCB) Input:Initial parametersθ 1 ∈R dθ; stepsizeη t >0 fort= 1,2,

    GreedyCB exploits a point prediction, ϵ-GreedyCB replaces that point prediction by a standard- normal random cost vector on exploration iterations (default ε= 0.1 ), and TSCB samples from the learned conditional cost distribution. Algorithm 2:Greedy contextual bandit (GREEDYCB) Input:Initial parametersθ 1 ∈R dθ; stepsizeη t >0 fort= 1,2, . . . , Tdo Obser...

    2020

  7. [7]

    Figure 4 reports the same comparison on the three remaining benchmarks: top-k selection, shortest path, and energy scheduling

    compares distributional cost models – Gaussian linear, CNF, and diffusion – on pricing at the extended horizon T= 15,000 . Figure 4 reports the same comparison on the three remaining benchmarks: top-k selection, shortest path, and energy scheduling. The synthetic benchmarks useT= 15,000; the energy benchmark uses its native test-window length. On top-k se...

    2024

  8. [8]

    IMLE with adaptiveλ ptb =α∥ˆc∥/∥c∥,αupdated by EMA on grad sparsity NID (Sahoo et al., 2023)−c(negative-identity straight-through) PFYL (Berthet et al., 2020)¯w ⋆ ptb(ˆc)−w⋆(c) DPO (Berthet et al.,

    2023

Show all 12 references
  1. [9]

    w⋆(ˆc−σc)−w⋆(ˆc) /σ Pool-based surrogates.Let Pt denote the cumulative pool of feasible solutions at iterationt, grown online by appending w⋆(ˆct) and w⋆(ct) at each step. Let wb := arg minw∈Pt c⊤w denote the pool’s best solution under the target cost and Rt :=P t \ {wb} the r...

    2000

  2. [10]

    The negative signs on the softmax arguments convert cost minimization to score maximization for the listwise ranking step

    Same subgradient as NCE; cached/centered pool variant MAP_c (MAP-C) (Mulamba et al., 2021)w ⋆(c)−arg min w∈Pt(ˆc−c)⊤w(cached MAP variant) SPOCaching (Mulamba et al., 2021)arg min w∈Pt(2ˆc−c)⊤w−w ⋆(c) Here σsoft denotes softmax and ˆc⊤Pt ∈R |Pt| stacks the predicted-cost utilit...

    2021

  3. [11]

    27 K.4 Alternative surrogate choices The surrogate loss for the decision-focused plug-in component is treated as a tunable hyperparameter rather than fixed to a default. This appendix reports the per-benchmark sweep over standard surrogate choices, implemented following the Py...

    2024

  4. [12]

    On top- k the gap is more modest at low degrees (around 2× at deg = 2 ) and widens to roughly 4–5× at deg≥4

    and narrows at high degrees, where the Gaussian linear cost model can no longer capture the cost map well. On top- k the gap is more modest at low degrees (around 2× at deg = 2 ) and widens to roughly 4–5× at deg≥4 . Shortest path shows small gaps throughout. The score-only DF...

    2000

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.