Source-linked AI summary
Pointwise or Pairwise: When Do Pairwise Losses Help Reward Learning, Provably?
Junghyun Lee, Minsoo Ha, Sanghwa Kim, Yeongjong Kim, Eunjee Lee, Seiyun Shin, Kwang-Sung Jun
TL;DR
Pairwise losses are used for reward learning even when pointwise rewards are available, but their empirical benefits are mixed. This paper compares pointwise and pairwise regression in grouped offline contextual bandits with action-independent contextual nuisance. It finds that finite-class guarantees favor VDR in specified terms, while linear-class comparisons depend on feature geometry and neither method uniformly dominates.
Problem
Empirical comparisons of pairwise and pointwise reward learning are mixed, leaving open when pairwise losses improve downstream decisions.
Source: §1 · p. 2Method
The paper analyzes Value Regression on observed rewards and Value Difference Regression on within-context reward differences under a semiparametric nuisance model.
Source: §1 · p. 2, §1.1 · p. 3, §5 · p. 10Results
For finite classes VDR removes the VR approximation-error term and improves a reward-scale term, while for linear classes neither method uniformly dominates and their comparison depends on feature geometry.
Source: §5 · p. 10Takeaways & Limitations
The relative benefit of differencing depends on the function class: it removes nuisance-induced bias, but in linear classes may increase estimation variance when misspecification is sufficiently low.
Source: §5 · p. 10The paper leaves assessing weak realizability in LLM and other applications, and finding weaker assumptions for meaningful guarantees, as future work.
Source: §5 · p. 10
Abstract
from arXiv · showhide
Pairwise losses are increasingly used for reward learning even when pointwise rewards are observed, with mixed empirical results. When and why do pairwise losses outperform pointwise losses? We study this question in a grouped offline contextual-bandit setting allowing multiple actions per context, capturing many reward learning scenarios. We compare Value Regression (VR), which regresses observed rewards pointwise, with Value Difference Regression (VDR), which regresses reward differences between a pair of actions sampled under the same context. We consider a semiparametric model where the mean reward is the sum of a learnable action-dependent component and an arbitrary context-dependent yet action-independent nuisance, capturing context-specific disturbances. Using a unified localized analysis, we prove finite-sample regression guarantees for finite and linear function classes and translate them into offline-regret bounds. For finite classes, VDR eliminates the misspecification term in the VR bound and improves a reward-scale-dependent error term by averaging over actions within each context, a benefit absent from the corresponding VR term. For linear classes, neither method uniformly dominates: within-context differencing removes nuisance-induced bias but may increase estimation variance relative to using absolute rewards when the misspecification is sufficiently low. This yields a feature geometry-dependent bias-variance tradeoff, which we corroborate with numerical experiments.
1 INTRODUCTION
Although pairwise losses are used even when numerical rewards are available, their empirical benefits are mixed; this paper asks when they improve downstream decisions. It studies pointwise and pairwise regression with grouped offline data and action-independent contextual nuisance, deriving guarantees for finite and linear classes.
1 INTRODUCTION
- Mixed empirical findings motivate asking when pairwise losses improve downstream decisions over pointwise losses.Some studies report gains, while others find no consistent improvement or results that depend on the kernel.Source: §1 · p. 2
1.1 THEORETICAL SETUP: GROUPED OFFLINE REWARD LEARNING
- The setting allows multiple actions and rewards per context in passively collected grouped offline data.Contexts are sampled independently; conditional on each context, actions are sampled independently from the behavior policy.Source: §1.1 · p. 2
- Weak realizability models reward as a learnable action-dependent function plus an arbitrary action-independent context term.The assumption requires realizability only for the action-dependent component.Source: §1.1 · p. 3
- Value Regression fits observed rewards, whereas Value Difference Regression fits reward differences between actions sampled under the same context.The paper studies squared difference loss as a representative pairwise objective.Source: §1.1 · p. 3
1.2 OUR CONTRIBUTIONS
- For finite classes, VDR removes the VR approximation-error term and improves a reward-scale term from context-scale to full-sample scaling.The latter gain comes from repeated action observations within contexts.Source: §1.2 · p. 4
- For linear classes, neither method uniformly dominates: VDR removes misspecification terms, but its variance depends on the geometry of feature differences.The relative performance depends on feature geometry, yielding a bias–variance tradeoff illustrated in numerical experiments.Source: §1.2 · p. 4
2 A LOCALIZED ANALYSIS FOR GROUPED REGRESSION
The analysis develops a common localized approach for grouped regression that preserves the distinction between variation across contexts and variation within a context. It applies this recipe to both pointwise and pairwise losses.
2 A LOCALIZED ANALYSIS FOR GROUPED REGRESSION
- The localized block-offset modulus provides the shared empirical-complexity quantity used in the fixed-point recipe.It is defined around a comparator and used to bound excess loss.Source: §2 · p. 4
- A common blockwise localized analysis yields fixed-point bounds for the population excess loss under two stated conditions.The estimator’s loss geometry supplies one condition, while problem-specific concentration bounds establish the other.Source: §2 · p. 5
- The analysis separates contributions governed by 1/Nx from those governed by 1/N, preserving the two sampling scales.The grouped-sampling concentration argument makes the context and within-context contributions explicit.Source: §2 · p. 5
3 FINITE CLASS: NUISANCE CANCELLATION AND GAINS FROM Na ≥2
For finite classes, the bounds favor VDR on approximation error and a reward-scale term, while an instance demonstrates a separation in offline regret. Additional action samples reduce within-context fluctuations but cannot replace information from unseen contexts.
3 FINITE CLASS: NUISANCE CANCELLATION AND GAINS FROM Na ≥2
- VDR removes the approximation-error term in the finite-class VR bound and improves the FRmax term from scale 1/Nx to 1/N.The additional action observations reduce within-context fluctuations, but do not provide information about unseen contexts without further structure on F.Source: §3 · p. 6
- The finite-class VR bound is a non-exact oracle inequality, with approximation-error coefficient two rather than one.The text notes that ERM over an arbitrary finite class cannot attain an exact oracle inequality with the optimal stated rate.Source: §3 · p. 6
- On one finite-class instance, VR regret is Ω(Rmax), while VDR regret is zero with probability tending exponentially fast to one in Nx.The separation holds for sufficiently large Nx; the VDR result requires Na ≥2.Source: §3 · p. 6
4 LINEAR CLASSES: A GEOMETRIC BIAS–VARIANCE TRADEOFF
For linear classes, VR and VDR trade off nuisance-induced bias against feature-geometry-dependent estimation variance rather than one uniformly dominating. VDR cancels action-independent nuisance, while VR can benefit from absolute rewards when informative within-context comparisons are rare.
4.1 VR FOR LINEAR CLASS
- Repeated actions reduce within-context Gram variability, but not context covariance; when conditional feature covariance varies across contexts, enough distinct contexts remain necessary for lower isometry.The block Gram variance enters the sample-size condition for lower isometry, not the error bound itself.Source: §4.1 · p. 7
4.2 VDR FOR LINEAR CLASS
- VDR's identifiable feature subspace is generated by within-context action variation; action-invariant directions lie in ker(ΣC), so it identifies θ⋆ only modulo that kernel.This suffices to identify action gaps on the support of πref.Source: §4.2 · p. 8
4.3 COMPARING VR AND VDR: FEATURE GEOMETRY PERSPECTIVE
- At Na = 512, VDR reduced mean regret by 9.7% for Llama, 13.0% for Qwen3, and 24.0% for ArmoRM; it was significantly lower for all three at Na ≥64.The real-data comparison varies labeled responses per training prompt; Figure 1 plots regret against that number.Source: Figure 1 · p. 9, §4.3 · p. 10
- At β = 0, VR had lower regret for every tested δ > 0; at δ = 0.02, RegVR − RegVDR changed from negative to positive as β increased.This illustrates VR's advantage when informative comparisons are rare and VDR's advantage as nuisance-induced bias grows.Source: Figure 1 · p. 9, §4.3 · p. 9
- With misspecification, nuisance cancellation removes VR's misspecification terms; when well specified, VDR's displayed leading variance is no larger, but lower-order terms do not uniformly order the bounds.The sharper VR bound can have a leading term σ²d_eff/N with d_eff ≤ d_C.Source: §4.3 · p. 9
5 CONCLUSION AND FUTURE WORK
The paper compares pointwise and within-context difference regression under grouped offline data, finding no uniformly preferred method: finite-class and linear-class guarantees exhibit different tradeoffs. It closes by identifying assumptions and extensions for future study.
5 CONCLUSION AND FUTURE WORK
- For finite classes, VDR removes the misspecification term in the VR bound and improves a reward-scale term through repeated action observations; for linear classes, neither method uniformly dominates.In the linear case, differencing removes nuisance-induced bias, while fitting absolute rewards can reduce estimation variance under correct specification.Source: §5 · p. 10
- Future work includes testing weak realizability in LLMs and other domains, studying Bradley–Terry logistic losses and pair selection, and extending beyond pairwise comparisons.Source: §5 · p. 10
AI DISCLOSURE STATEMENT
- The authors report using generative AI across modeling, proofs, experiments, writing, and other tasks, with generated proofs, cited literature, and code checked by authors.Source: AI DISCLOSURE STATEMENT · p. 10
A RELATED WORK
- Related work spans reward objectives, semiparametric estimation, misspecified regression, grouped-observation guarantees, and offline contextual bandits.Source: A RELATED WORK · pp. 20–21
B ESTIMATION ERROR TO OFFLINE REGRET
This appendix translates estimation error into offline-regret guarantees for GREEDY and PESSIMISM policies using coverage coefficients. The bounds and their usefulness depend on coverage and, for PESSIMISM, implementation inputs.
B.1 COVERAGE COEFFICIENTS AND REGRET GUARANTEES
- The all-policy coverage coefficient has no general ordering with optimal-policy coverage, although instances can have C⋆ ≪ C∞F.Source: §B.1 · p. 22
- The appendix presents offline-regret upper bounds for GREEDY and PESSIMISM policies under coverage assumptions.Source: §B.1 · p. 22
- PESSIMISM requires computing an expectation under ρ and knowing γN and C(π); its implementation may also require a useful a priori bound on εaprx.Source: §B.1 · p. 22
B.2 PROOF OF PROPOSITION B.1: OFFLINE REGRET OF GREEDY AND PESSIMISM
- The proof uses that centering preserves action gaps, so reward and action-dependent components share the optimal policy; bounds become vacuous when the relevant coverage coefficient is infinite.Source: §B.2 · pp. 22–23
C AUXILIARY RESULTS FOR GROUPED REGRESSION
The auxiliary results connect VDR's population loss to centered prediction error and give a fixed-point route for converting localized excess-loss control into an estimator bound.
C AUXILIARY RESULTS FOR GROUPED REGRESSION
- The appendix defines population and empirical excess loss relative to a comparator and a perturbation of that comparator.Source: C AUXILIARY RESULTS FOR GROUPED… · p. 25
C.1 VDR POPULATION LOSS AND CENTERED PREDICTION ERROR
- VDR's population-loss identity links its loss to centered prediction error; under weak realizability, the action-independent nuisance cancels, giving Cf⋆ = Cr⋆.Source: §C.1 · p. 25
C.2 PROOF OF PROPOSITION 2.1: LOCALIZED FIXED-POINT INEQUALITY
- The fixed-point argument bounds an estimator's population excess loss by the largest nonnegative r satisfying r ≤ ψ(r), once the localized modulus conditions hold.Source: §C.2 · p. 25
D.1.1 PROOF OF LEMMA 3.1: LOCALIZED MODULUS FOR VR IN FINITE CLASS
The proofs use blockwise localization to exploit repeated actions, while VDR's centering removes shared nuisance variation. The STAR discussion gives a distinct finite-class guarantee and a condition under which the VR bound is smaller.
D.1.1 PROOF OF LEMMA 3.1: LOCALIZED MODULUS FOR VR IN FINITE CLASS
- The VR modulus proof retains repeated-action benefits by separating within-context variation from context-level fluctuations before blockwise concentration.Source: §D.1.1 · pp. 26–27
D.2.1 PROOF OF THE VDR BOUND IN THEOREM 3.1
- The VDR proof combines empirical risk minimization with localized-modulus control, then converts the excess-loss bound into centered prediction error.Source: §D.2.1 · p. 27
C ˆf VDR
- The VDR theorem proof records a bound on twice the estimator's population loss, then compares it with the stated finite-class rate.Source: C ˆf VDR · p. 28
D.2.2 PROOF OF LEMMA D.1: LOCALIZED MODULUS FOR VDR IN FINITE CLASS
- VDR's pairwise-centering identity yields a transformed squared error, and the action-independent nuisance cancels from within-context differences.Source: §D.2.2 · p. 28
E.1 STAR ESTIMATOR AND ITS GUARANTEE
- The STAR estimator is reported to have an exact oracle inequality in this setting, unlike usual ERM's non-exact inequality.Source: §E.1 · p. 30
C ˆf STAR
- STAR reduces the εaprx coefficient from two to one, at the price of Rmax² instead of FRmax in the Nx^-1 term.Source: C ˆf STAR · p. 30
- When Rmax ≫ F and Rmax²/Nx ≫ εaprx, σ²/N, up to logarithmic factors, the VR bound is smaller than the STAR bound.Source: C ˆf STAR · p. 30
E.2 PROOF OF THEOREM E.1: STAR ESTIMATOR BOUND FOR FINITE CLASS
The finite-class STAR-estimator proof establishes the conditions needed for a localized bound, then uses that analysis alongside the linear-VR proof techniques to derive regression guarantees.
E.2 PROOF OF THEOREM E.1: STAR ESTIMATOR BOUND FOR FINITE CLASS
- The STAR-estimator proof uses a localized block-offset modulus over Hstar and establishes the two conditions required by Proposition 2.1.The proof notes that condition (i) holds deterministically with λ = 1/18; Lemma E.1 verifies condition (ii).Source: §E.2 · p. 31
E.3 PROOF OF LEMMA E.1: LOCALIZED MODULUS FOR THE STAR ESTIMATOR IN FINITE CLASS
- For the STAR estimator, a finite net, Bernstein bounds, and a union bound yield a uniform high-probability bound on the localized modulus.The net is extended to the full class using its approximation property.Source: §E.3 · pp. 31, 33
F.1.1 PROOF OF THEOREM 4.1: VR BOUND FOR LINEAR Flin
- For linear VR, Lemma F.1 supplies a high-probability localized-modulus bound used in the proof of Theorem 4.1.The proof combines its bounds to establish the theorem.Source: §F.1.1 · pp. 34–35
F.1.2 PROOF OF LEMMA F.1: LOCALIZED MODULUS FOR LINEAR VR
- The linear-VR localized-modulus proof controls the process through a lower-isometry event and concentration of two score vectors.The score vectors are the misspecification and reward-noise scores.Source: §F.1.2 · p. 35
F.1.3 ALTERNATE ERROR BOUND FOR LINEAR VR
The alternate linear-VR bound can improve on the original bound, but its comparison with VDR depends on approximation error and feature geometry.
F.1.3 ALTERNATE ERROR BOUND FOR LINEAR VR
- In the well-specified case, the alternate VR bound is tighter than the original bound, and the gap can be arbitrarily large for some feature geometries.A Rademacher-feature example improves both terms of the original bound by a factor of τ.Source: §F.1.3 · p. 37
- The alternate bound’s leading N^-1 term is no larger than VDR’s, but its lower-order terms have no uniform ordering because α0 and αC are not generally comparable.Source: §F.1.3 · pp. 37–38
- In an example with action-independent misspecification, the alternate bound avoids the original bound’s constant εaprx term.The example has εaprx = 1 and εVR,C = 0.Source: §F.1.3 · p. 38
- When εVR,C < εaprx, neither alternate nor original VR bound uniformly dominates, because the smaller centered approximation error must be weighed against a slower square-root remainder.When εVR,C is a positive constant, that interaction may yield a slower estimation remainder.Source: §F.1.3 · p. 38
G LOWER BOUNDS
- The lower-bound section gives an estimator-specific separation between VR and VDR, then states an agnostic minimax lower bound for arbitrary learners.Source: G LOWER BOUNDS · p. 42
G.1 PROOF OF THEOREM 3.2: FAILURE MODE OF VR
The appendix constructs a grouped-data instance where VR selects a suboptimal action, while VDR succeeds on that same instance; it also presents a separate agnostic minimax lower bound.
G.1 PROOF OF THEOREM 3.2: FAILURE MODE OF VR
- The construction makes VR fail through a context-varying baseline, action-context correlation in the behavior policy, and a class unable to represent the baseline.The baseline can then be absorbed into fitted action values and reverse their ordering.Source: §G.1 · p. 42
- When (1 − 2p)B > ∆, the population VR solution prefers a2 at every context although a1 is optimal at every context.Source: §G.1 · p. 43
- On the event, g is the unique empirical VR minimizer, and greedy selection chooses a2 at both contexts; it has probability at least 1 − exp(−25Nx/288), uniformly over Na ≥ 1.Source: §G.1 · p. 44
- For Na ≥ 2, within-context differences cancel the baseline, and VDR followed by GREEDY has zero regret with probability at least 1 − (5/8)^Nx.A block containing both actions distinguishes f⋆ from g using reward differences.Source: §G.1 · p. 44
G.2 AGNOSTIC MINIMAX LOWER BOUND
- The agnostic minimax lower bound is presented as showing that, without Assumption 1, approximation and statistical terms cannot be improved in a worst-case sense.The passage describes the result over a coverage-budget class.Source: §G.2 · pp. 44–45
G.3 PROOF OF THEOREM G.1: AGNOSTIC MINIMAX LOWER BOUND
The proof establishes an agnostic minimax lower bound by encoding action choices as signs and applying weighted Assouad testing. Its construction separates statistical and misspecification contributions.
G.3 PROOF OF THEOREM G.1: AGNOSTIC MINIMAX LOWER BOUND
- Every learner has expected regret at least S/4 for some constructed reward, and regret at least S/8 with probability at least 1/8.The reduction applies to arbitrary learners, not only predictors in F or policies induced by them.Source: §G.3 · pp. 46, 48
- Weighted Assouad testing turns sign errors into regret: neighboring reward hypotheses have total variation at most 1/2, and each wrong sign incurs its context’s weighted action gap.The sign-testing reduction covers arbitrary possibly randomized policies.Source: §G.3 · pp. 46–48
- The construction assigns d signs to contexts represented in F and m signs to contexts whose action differences are absent from the model, separating statistical and misspecification contributions.The misspecification gap is spread across enough contexts to keep each sign difficult to identify; when ε = 0, that block contributes no regret.Source: §G.3 · p. 46
- Although context blocks are not generally independent, conditional independence of rewards makes the KL divergence scale with the total N = NxNa observations.The context–action design has the same law under every hypothesis, allowing the conditional reward law to be handled as a product.Source: §G.3 · p. 48
- The theorem’s lower bound is worst-case over the class C⋆≤C; it does not establish a hard instance with prescribed C⋆=C≪C∞_F.The passage notes that the constructed example with all signs negative need not attain the minimax lower bound.Source: §G.3 · p. 50
H DEFERRED EXPERIMENTAL DETAILS
- The deferred experimental details cover a controlled synthetic experiment, LLM response selection, and downstream MCTS mathematical reasoning.The MCTS experiment uses a binary-preference VDR variant; the first two use the squared-loss VR and VDR objectives.Source: H DEFERRED EXPERIMENTAL DETAILS · p. 51
H.1 CONTROLLED SYNTHETIC LINEAR-BANDIT EXPERIMENT
The controlled experiments vary cross-face sampling, nuisance magnitude, and reward alignment to test when VR or VDR has lower regret. Results show a crossover as nuisance grows, while VR has lower regret when the true value aligns with a weakly sampled action direction.
Contexts, actions, and features
- The experiment uses five-dimensional spherical contexts, eight cube actions, and the bilinear feature map ϕ(x, a) = vec(xa⊤).It fixes (Nx, Na) = (200, 8) and σ = 0.5; eight problem instances are evaluated with 20 data sets each.Source: §H.1 · pp. 51–53
Role of δ: design constants
- Although total within-context variation stays at least 2/3, small δ leaves little variation in the first action coordinate that separates the faces.The first-coordinate eigenvalue of centered covariance is proportional to 4δ(1 −δ).Source: §H.1 · p. 52
Crossover results
- At δ = 0.02, the regret difference shifts from −0.0040±0.0005 at β = 0 to +0.0188 ± 0.0050 at β = 0.5, favoring VR then VDR.For each tested δ in {0.02, 0.05, 0.1, 0.2}, the sign flips as β grows.Source: §H.1 · pp. 53–54, Table 2 · p. 54, Figure 2 · p. 55
- When β = 0, VR has lower regret in all eight instances for every tested δ > 0; its advantage shrinks as δ grows.At δ = 0.5, VR bias vanishes and the regret-difference row is nearly flat.Source: §H.1 · pp. 53–54, Table 2 · p. 54
- Increasing β grows VR’s population bias proportionally, while the VDR objective is unaffected by the action-independent nuisance.The bias values at β = 0, 0.25, 0.5, 1, and 2 are 0, 0.129, 0.259, 0.518, and 1.036.Source: §H.1 · pp. 52, 54
- At δ = 0 and ρ = 1, VDR cannot identify the cross-face gaps needed by the greedy policy because observed within-context differences are zero.When β = 0, VR can still identify the true value coefficients because Σ ≻ 0.Source: §H.1 · p. 54
Data-driven selection results
- For δ > 0, DIFFERENCE-CV selects α similarly to ORACLE and achieves regret close to the better endpoint across the tested grid.At δ = 0, its regret falls behind the better endpoint, increasingly so for larger β.Source: §H.1 · p. 54, Figure 2 · p. 55
Alignment sweep results
- For every ρ > 0, VR has lower mean regret than VDR; as ρ rises from 0 to 1, κdiff falls from 1 to 0.0784.At ρ = 0, both methods have mean regret 0.0003; κmean rises from 0 to 0.9216 over the sweep.Source: §H.1 · p. 54, Figure 3 · p. 55
H.2 LLM RESPONSE-SELECTION EXPERIMENT
The experiment compares VR and VDR across reward models and response budgets using fixed prompts, responses, and representations. For Na ≥64, paired regret differences favor VDR under all three reward models.
H.2 LLM RESPONSE-SELECTION EXPERIMENT
- The study uses 1,000 prompts and 1,000 cached Llama-3.2-3B-Instruct responses per prompt, represented by 3,072-dimensional mean-pooled final-layer hidden states.The same prompts, responses, and representations are evaluated with three reward models.Source: §H.2 · p. 55
- For every Na ≥64, paired regret-difference intervals fall below zero across all three reward models, favoring VDR.Figure 4 reports the mean paired difference RegVDR − RegVR with pointwise 95% Student-t intervals over five seeds.Source: Figure 4 · p. 56, §H.2 · p. 56
- Across five seeds, VR and VDR share sampled responses at nine Na budgets; VDR uses all pairs through Na=32, then samples 16Na pairs, with separate validation tuning.Each seed uses 800 training prompts and 200 held-out evaluation prompts; the models are refit on all 800 training prompts after validation.Source: §H.2 · p. 56
- Offline regret averages the reward gap between the best cached response and the response selected by each fitted scorer over 200 evaluation prompts.Each scorer ranks all 1,000 cached responses for each evaluation prompt.Source: §H.2 · p. 56
H.3 MCTS-BASED MATHEMATICAL REASONING EXPERIMENT
The MCTS experiment tests whether preferences derived from numerical Q-values guide reasoning search, comparing VR with binary-preference VDR. VDR has higher observed final-answer accuracy with both linear and MLP heads.
H.3 MCTS-BASED MATHEMATICAL REASONING EXPERIMENT
- The experiment tests whether preferences derived from numerical feedback guide MCTS toward correct final answers, evaluating all 100 problems with Qwen2.5-Coder-7B-Instruct under fixed search limits.The setup uses one MCTS tree, two iterations, four children per expansion, maximum depth 16, and fixed token limits.Source: §H.3 · pp. 56–57
- Contexts comprise a problem and its reasoning prefix; candidate next steps receive Q-value labels from an eight-rollout snapshot, with final-outcome rewards backed up through the search tree.The Q-value estimates eventual success under the generating policy and budget.Source: §H.3 · p. 57
- A frozen Qwen backbone supplies 3,584-dimensional candidate-step features for trainable linear or one-hidden-layer GELU heads; VR regresses Q-values, while VDR learns pairwise orderings.For VDR, the encoder and head form the process preference model; MLP hyperparameters are selected by validation loss and averaged across three training seeds.Source: §H.3 · p. 57
- VDR records higher observed accuracy than VR for linear heads (16% versus 15%) and MLPs (13% versus 10%).Table 3 reports final-answer accuracy on 100 test problems under a common MCTS budget.Source: §H.3 · p. 57, Table 3 · p. 58