- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies when learning from numerical reward differences is preferable to regressing absolute rewards. It considers grouped offline contextual-bandit data consisting of independent context draws and action–reward observations per context. Under the weak realizability assumption , where belongs to the hypothesis class and is an arbitrary action-independent nuisance, the authors compare pointwise Value Regression (VR) with squared-loss Value Difference Regression (VDR).
The paper derives finite-sample prediction guarantees for finite and linear function classes, distinguishing fluctuations governed by from those reduced by all observations. It translates centered prediction error into coverage-dependent offline regret and gives a finite-class instance in which VR incurs persistent regret while VDR succeeds. The linear analysis incorporates raw and centered feature geometry. Controlled synthetic experiments illustrate a nuisance–variance tradeoff, and additional experiments compare regularized reward models for LLM response selection and preference models for mathematical-reasoning search.
Critical strengths
1. The grouped finite-sample analysis provides a useful distinction between two sources of statistical uncertainty.
The paper explicitly accounts for dependence among observations sharing a context and among pairs formed from the same observations. Its analysis separates fluctuations governed by the number of contexts from those reduced by repeated action observations. The linear results additionally account for the identifiable centered-feature subspace and explain how repeated actions affect empirical-covariance concentration.
These distinctions are consequential because grouped data collection is common in the motivating reward-learning settings. The results clarify why collecting more observations for existing contexts need not have the same statistical effect as observing additional contexts. The treatment of both finite and linear classes, together with the refined centered VR bound, makes this a coherent theoretical contribution.
2. The finite-class separation establishes an actual downstream difference between the estimators.
Theorem 3.2 constructs an instance satisfying weak realizability on which empirical VR followed by greedy selection incurs constant regret with high probability, whereas VDR succeeds on the same instance. This result is stronger than a comparison between upper bounds: it demonstrates that fitting an action-independent nuisance through a restricted model class can distort action rankings.
The controlled synthetic experiments provide complementary evidence. They vary nuisance magnitude and the informativeness of within-context comparisons separately, exhibit both VR-favored and VDR-favored regimes, and report uncertainty across independently generated problem instances. The positive-coverage results support the proposed mechanism without relying solely on the degenerate zero-coverage setting.
Critical weaknesses
1. The central comparative interpretation needs a sharper distinction between intrinsic estimator differences and differences in analytical tightness.
For linear classes, Section 4.3 primarily establishes that separately derived upper bounds are not uniformly ordered. The text acknowledges this with the qualification “upper bound-wise,” but the examples making , or its inverse, large do not by themselves establish corresponding advantages in actual prediction error or regret.
Appendix F.1.3 makes this distinction particularly important. The sharper VR bound has a leading noise term involving , and its decision-relevant population bias is , which can vanish even when the absolute approximation error is positive. These quantities should be central to the comparison. In the correctly specified, unregularized, conditionally homoscedastic case, when the relevant centered functionals are estimable, Gauss–Markov gives OLS no larger conditional expected centered squared error than VDR. This special case should be distinguished from the broader heteroscedastic setting allowed by the paper.
A related issue arises in the finite-class reward-scale comparison. Under ordinary realizability, , separately concentrating the empirical quadratic term over context blocks and the reward-noise multiplier conditional on the full design yields a VR bound of order
\frac{F^2}{N_x} + \frac{\sigma^2+FR_{\max}}{N} \right] \log\frac{2|\mathcal F|}{\delta}.$$ Thus, the $FR_{\max}/N$ dependence is also available to VR in this special case using the decomposition already employed for VDR. The published VR bound remains valid, and the nuisance-induced separation remains meaningful, but the displayed reward-scale improvement is not established as an independent advantage of pairing. The authors should clarify which differences remain intrinsic under weak realizability and which reflect the sharpness of the analyses. These issues limit the strength of the paper’s answer to its central comparative question, although they do not invalidate the grouped guarantees or Theorem 3.2. **2. The application experiment changes the estimator and does not isolate the mechanism emphasized by the theory.** The response-selection experiment in Appendix H.2 uses ridge-regularized estimators in a 3,072-dimensional feature space, whereas the linear theorems analyze unregularized estimators under lower-isometry conditions. Moreover, VDR uses all pairs only for $N_a\le32$ and switches to $16N_a$ sampled pairs for larger budgets. The consistent advantage across all three reward models is then highlighted from $N_a=64$ onward. An exact centered-ridge implementation would provide a more direct comparison. The paper already gives the identity allowing the all-pairs squared objective to be evaluated through within-context centering, so this check does not require enumerating all pairs. Regularization and effective rank also matter at the smaller budgets. The centered feature matrix has rank at most $N_x(N_a-1)$, which equals 800 and 2,400 for $N_a=2$ and $N_a=4$, respectively. Unless the relevant population rank is correspondingly smaller, these regimes cannot satisfy the unregularized analysis’s invertibility conditions. Reporting effective-rank diagnostics, the regularization search grid, selected penalties, and sensitivity to exact versus sampled pairs would help explain the crossover. The matched samples, prompt-level holdout, separate regularization selection, and paired confidence intervals are positive features of the experiment. However, it does not establish weak realizability or show that nuisance cancellation explains the observed gains. The supplementary MCTS experiment provides limited additional evidence: it uses a binary logistic preference objective and reports gains of one and three solved problems on 100 tests with one search seed. These results should remain explicitly exploratory.Questions for authors
1. Clarification of the linear comparative claim.
Beyond the finite-class separation in Theorem 3.2, which result establishes an ordering or separation of actual linear-estimator risks, rather than non-ordering of upper bounds? Please explain how Section 4.3 should be interpreted when and from Appendix F.1.3 are used throughout. A direct comparison in an appropriate special case would help distinguish the well-specified homoscedastic setting from the more general noise assumptions.
2. Clarification of the finite-class reward-scale dependence.
In the realizable case, let and . Block concentration controls the population quadratic error through and an term, while conditional concentration controls through and terms. Empirical optimality then gives the refined VR rate stated above.
How does this refinement change the interpretation of the second finite-class advantage? Under weak realizability, can the remaining context-scale range contribution be expressed through the approximation-residual envelope, thereby separating misspecification effects from observation-noise averaging?
3. Validation of the reported response-selection comparison.
Do the conclusions persist when VDR uses the exact all-pairs centered objective at every budget, with consistent loss normalization and separately selected regularization strengths? Please clarify the regularization grids, the candidate and label budget used for validation regret, and any available effective-rank or regularization-sensitivity diagnostics.
These requests concern the interpretation and validation of the existing results rather than extensions to new applications.
3 comments
The proof improvement is to separate the noiseless excess loss from the reward-noise multiplier before applying concentration. We concentrate the former over the context blocks and the latter over the observations conditional on the sampled contexts and actions. Empirical optimality and localization then yield the bounds above; revised Appendix D.1 gives the full proof.
We have updated the finite-class statement and discussion in §2 accordingly. These are comparisons of upper bounds; the actual greedy-regret separation is established separately in Theorem 2.2.
W2 and Q3. Exact pairs, ridge, and interpretation
Exact all-pairs objective. We agree that exact within-context centering provides a cleaner comparison. We additionally evaluated exact VDR at every response budget by centering features and rewards within each prompt, avoiding pair subsampling without explicitly enumerating all pairs. The larger-budget conclusion persists: exact VDR achieves lower mean held-out regret than VR for all three reward models at , consistent with our original findings. Figure 1 now shows the exact fit alongside the original VDR results.
To clarify normalization, Appendix H.2 uses summed squared losses, with ridge penalties defined on that scale. Writing for a prediction residual and , the exact all-pairs ridge objective satisfies This gives the identical regularized objective without enumerating pairs. Equivalently, using the centered sum without the factor requires the penalty . The grid reported below refers to the summed-loss convention; relative to an averaged loss, the corresponding penalties are for VR and for VDR, where is the total number of pairs used.
Regularization and rank. We agree that the smallest response budgets can prevent direct application of our unregularized analysis. The centered covariance estimated from the full response pool has numerical rank 3,072, whereas the empirical VDR Gram matrices on 800 training prompts have rank at most 800 and 2,400 for and , respectively. This matters since Theorem 3.2 requires lower isometry on the identifiable population subspace.
To examine this limitation, we computed (i) eigenvalue decay, (ii) cumulative spectral energy, and (iii) ridge effective dimension. Despite the full numerical rank, 1,468 and 1,974 directions explain 90% and 95% of the spectral energy, respectively. Both are below 2,400, so at , the rank restriction alone does not rule out capturing most of the feature variation in the final refit. However, these diagnostics do not establish lower isometry or show that the sampled designs actually capture those directions. The rank restriction remains more severe at .
On the same splits and samples, the zero-penalty controls reproduce the tuned original fits’ test regrets and confidence intervals at all four budgets from 64 to 512. At , however, tuning improves VR substantially and can change the ordering. Thus, regularization affects the comparison at the smallest budgets, while the advantage of the original VDR fits at larger budgets persists without a positive ridge penalty. As noted in Appendix H.2, some smaller-budget runs select the largest tested penalty, so sensitivity to a wider grid remains unresolved.
We have updated Appendix H.2 to report the regularization search grid, the validation-based selection procedure, and the main patterns in the selected penalties. Penalties are selected independently for each reward model, response budget, method—including exact VDR—and random seed, from . We use 640 prompts for fitting in the inner split, 160 for validation regret, 800 for the refit, and 200 for held-out testing. Validation regret uses all 1,000 labeled candidate responses per validation prompt at every budget. Thus, specifies the responses used per prompt for fitting, while validation uses the fixed full candidate pool.
We also believe that our theoretical framework can be naturally extended to ridge regularization by accounting for regularization bias and the corresponding spectral quantities, along the lines of Hsu et al. (2014). Ridge regularization addresses empirical singularity, while the effective dimension curve shows how it reduces the contribution of directions with smaller eigenvalues. Hence, although our current theorems do not directly cover these regularized experiments, we believe that they remain closely connected to the setting we analyze.
Scope of the empirical evidence. The response-selection study compares regularized linear fits on frozen features, while the synthetic study directly examines the role of the additive baseline and comparison geometry. We do not claim that the response-selection results alone establish weak realizability or identify baseline cancellation as the source of the gains. In §3.4, we now describe the MCTS study in Appendix H.3 as exploratory. Specifically, it uses a binary logistic objective and one search seed, with one and three additional solved problems out of 100 for the linear and MLP heads, respectively.
We sincerely thank the reviewer for their exceptionally careful review, for recognizing the value of our grouped finite-sample analysis, and for highlighting the regret separation between VR and VDR. We address their points below.
W1 and Q1. Where the linear bounds lose information
Thank you for emphasizing this distinction. We agree that the original geometric examples compare upper bounds and do not establish an ordering of actual risks. The revised §3.3 explicitly separates these comparisons, and Appendix F.3 provides direct risk comparisons for the unregularized linear estimators.
We have also incorporated sharper quantities into the main VR theorem and its interpretation. Bounding centered error through uncentered error loses information about both the population approximation error and the feature geometry. The revised proof works directly in the centered prediction norm, yielding the centered population error εVR,C and leading noise dependence σ2deff/N, with deff≤dC. In particular, εVR,C can vanish even when εaprx>0. Appendix F.1.2 gives the corresponding proof. The examples involving α0 and αC now explicitly compare the N−2 correction terms.
For actual risks, the revised discussion distinguishes three cases:
Ordinary realizability and homoskedastic. Conditional on the logged design, suppose the reward noises are independent with common variance and the centered test features are estimable from the within-context differences. Both centered prediction rules are linear in the observed rewards and unbiased. Gauss–Markov therefore gives VR no larger variance, and hence no larger centered risk, than VDR. VR retains information in the block means that VDR discards.
Weak realizability. Under the same design and noise conditions, VDR remains unbiased for centered predictions, while VR can incur bias from fitting the baselines. VDR has lower conditional risk exactly when VR’s squared conditional bias exceeds its variance savings. We illustrate this with X uniform on {−1,1}, A=X with probability 3/4, ϕ(X,A)=A, and r⋆(X,A)=θ⋆A−BX, where B≥0. Consider two context blocks with two observations each: one contains both actions, and the other contains A=X twice. The exact conditional centered risks are
\qquad \frac{3}{8}\sigma^2\quad\text{for VDR}.$$ Thus, VR has lower risk for $B<\sigma$, and VDR for $B>\sigma$. Appendix F.3.2 also establishes a crossover after averaging over the logged design. For the same population, as $N_x$ grows with $N_a=2$, the limiting greedy regrets are $2\theta^\star$ and zero, respectively, whenever $B/2>\theta^\star>0$.Ordinary realizability and heteroskedastic. The variance ordering can reverse even under ordinary realizability. The example in §3.3 and Appendix F.3.3 gives exact conditional centered risks 9σ2/25 for VR and σ2/4 for VDR, so VDR has strictly lower risk.
W1 and Q2. The finite-class proof and reward-scale term
Thank you very much for this observation. Through a tighter proof, we have indeed separated misspecification effects from observation-noise averaging and corrected the interpretation of the finite-class comparison.
Let f∘ be a population VR minimizer, F=supf∈F∥f∥∞, and
=\left(\frac{F^2}{N_x}+\frac{\sigma^2+FR_{\max}}{N}\right) \log\frac{|\mathcal F|}{\delta}.$$ Under weak realizability and $N_a\ge2$, the revised Theorem 2.1 gives, with probability at least $1-\delta$, for any $\eta>0$, $$\mathbb E[(\mathcal C\hat f_N^{\rm VR}-\mathcal C r^\star)^2] \le (1+\eta)\varepsilon_{\rm aprx} +\mathcal{O}\left( (1+\eta^{-1})\mathcal E_\delta +\frac{F\|f^\circ-r^\star\|_\infty}{N_x} \log\frac{|\mathcal F|}{\delta} \right), \quad \mathbb E[(\mathcal C\hat f_N^{\rm VDR}-\mathcal C r^\star)^2] \lesssim \mathcal E_\delta.$$ Thus, **we no longer claim an independent advantage in the observation-noise dependence on $R_{\max}$**: both bounds contain $FR_{\max}/N$. Under ordinary realizability, $\varepsilon_{\rm aprx}$ and $\|f^\circ-r^\star\|_\infty$ vanish, and the bounds have the same order. Under weak realizability, these additional misspecification terms can remain for VR, whereas VDR avoids them by canceling the shared baseline.