Ordinal Credit Assignment: Multi-Step Reinforcement Learning from Comparisons Alone
Abstract
Policy-gradient methods need a scalar reward, yet for many tasks no formula captures what we want, while judging which of two outcomes is better is easy. We study reinforcement learning that receives only such comparisons - no reward function, no reward model - in multi-step tasks. Groups of trajectories start from a shared state, and each action is credited by how its reward-to-go compares with those of other trajectories at the same time step. We show the expected update is policy gradient with reward-to-go replaced by its win rate against the population still running at that time, weighted by the chance an opponent is still running; in deterministic environments the update ranks actions by true value and the optimal policy is stable, whereas under stochastic outcomes it prefers actions that win more often rather than those with higher mean. Label noise near ties or from position bias leaves the expected update unchanged; only noise that also flips clear comparisons halves the signal. A critic trained from the same comparisons removes the state confound without changing the expected update. In a pre-registered study over six environments with ten seeds per claim, comparisons cost no detectable performance relative to scalar returns at the same granularity, learning a reward model from the same comparisons is not better, and ten percent of comparisons suffice when spent on a few time points with all pairs. With real LLM judges, comparisons are 7-10 points more accurate than pointwise scores, and the gap grows with the stronger judge. Trained end-to-end with an LLM judge on a requirement the hand-written reward omits, policies satisfy it in all five seeds but land far less often than with oracle comparisons, because the judge is near chance on the near-tied failures dominating early training. Comparisons do not close the gap to PPO with scalar rewards on HalfCheetah.
Related
- BRIDGE: Bilevel Retrieval-Credit-Aware Agentic Reinforcement Learning
- Orthogonal Policy Learning with Ordinal Outcomes
- BCFL-DAI-PUB: Blockchain-integrated federated learning with dynamic adaptive incentives for privacy-utility balanced credit risk modelling
- Reinforcement Learning Under Runtime Confounding: Policy Learning and Off-Policy Evaluation
- Deep Reinforcement Learning for Blind Passive Beamforming in RIS-Assisted MIMO Systems
BibTeX
@misc{yu2026ordinal,
title = {{Ordinal Credit Assignment: Multi-Step Reinforcement Learning from Comparisons Alone}},
author = {Hao Yu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.06375},
eprint = {2605.06375},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.06375},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Ordinal Credit Assignment: Multi-Step Reinforcement Learning from Comparisons Alone
AU - Hao Yu
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2605.06375
UR - https://arxiv.org/abs/2605.06375
AB - Policy-gradient methods need a scalar reward, yet for many tasks no formula captures what we want, while judging which of two outcomes is better is easy. We study reinforcement learning that receives only such comparisons - no reward function, no reward model - in multi-step tasks. Groups of trajectories start from a shared state, and each action is credited by how its reward-to-go compares with those of other trajectories at the same time step. We show the expected update is policy gradient with reward-to-go replaced by its win rate against the population still running at that time, weighted by the chance an opponent is still running; in deterministic environments the update ranks actions by true value and the optimal policy is stable, whereas under stochastic outcomes it prefers actions that win more often rather than those with higher mean. Label noise near ties or from position bias leaves the expected update unchanged; only noise that also flips clear comparisons halves the signal. A critic trained from the same comparisons removes the state confound without changing the expected update. In a pre-registered study over six environments with ten seeds per claim, comparisons cost no detectable performance relative to scalar returns at the same granularity, learning a reward model from the same comparisons is not better, and ten percent of comparisons suffice when spent on a few time points with all pairs. With real LLM judges, comparisons are 7-10 points more accurate than pointwise scores, and the gap grows with the stronger judge. Trained end-to-end with an LLM judge on a requirement the hand-written reward omits, policies satisfy it in all five seeds but land far less often than with oracle comparisons, because the judge is near chance on the near-tied failures dominating early training. Comparisons do not close the gap to PPO with scalar rewards on HalfCheetah.
ER -