Pointwise or Pairwise: When Do Pairwise Losses Help Reward Learning, Provably?
Abstract
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.
Related
- Provably Efficient Q-learning for Robust Reinforcement Learning
- Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
- Provably Efficient Risk-Sensitive Offline Reinforcement Learning via Optimized Certainty Equivalents
- Non-asymptotic Convergence of Average-reward Q-learning with Options
- Learning Stabilizing Latent Feedback Controllers via Multi-Step Backward Losses
BibTeX
@misc{lee2026pointwise,
title = {{Pointwise or Pairwise: When Do Pairwise Losses Help Reward Learning, Provably?}},
author = {Junghyun Lee and Minsoo Ha and Sanghwa Kim and Yeongjong Kim and Eunjee Lee and Seiyun Shin and Kwang-Sung Jun},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37209},
eprint = {2609.37209},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37209},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Pointwise or Pairwise: When Do Pairwise Losses Help Reward Learning, Provably?
AU - Junghyun Lee
AU - Minsoo Ha
AU - Sanghwa Kim
AU - Yeongjong Kim
AU - Eunjee Lee
AU - Seiyun Shin
AU - Kwang-Sung Jun
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37209
UR - https://arxiv.org/abs/2609.37209
AB - 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.
ER -