Relative Ranking in Reinforcement Learning

30 concepts16 papers1 proposal

In reinforcement learning (RL), we traditionally task algorithms with predicting exact, absolute numbers. We train critics to estimate the precise expected cumulative reward of a state ($V(s)$) or an action ($Q(s,a)$), and we design off-policy evaluation (OPE) methods to compute the exact dollar value or success rate of a candidate policy.

This insistence on absolute precision is a regression trap. Mapping high-dimensional state spaces to exact scalar rewards requires complex environment modeling, introduces extreme variance, and places an unnecessarily difficult constraint on our function approximators.

In reality, downstream decision-making rarely requires absolute accuracy. To choose the best action in a state, or to select the best policy to deploy on a physical robot, you do not need to know the exact value of each option. You only need to know their relative ranking. Shifting the objective from absolute value regression to ordinal ranking simplifies the learning target, reduces sample complexity, and stabilizes evaluation.

The Action-Level Insight: Why Search and Control Only Need Order

The realization that absolute values are an unnecessary burden dates back to early foundational work. Utgoff et al. demonstrated that maintaining the correct relative ordering of states is entirely sufficient for optimal performance, arguing that learning an absolute evaluation function forces representations to solve a much harder problem than the task dictates. Dietterich et al. operationalized this by framing value function approximation as a support vector linear program, showing that optimizing for the relative ranking of actions yields highly robust control policies without needing to minimize numerical prediction errors.

This principle explains why online search algorithms work so well in practice. Consider Monte Carlo Tree Search (MCTS), which relies on highly simplified, often random rollouts to evaluate deep branches of a game tree. Why do these inaccurate simulations lead to grandmaster-level moves?

James et al. revealed that MCTS functions fundamentally as an optimizer rather than a value estimator. The search converges to the optimal decision as long as the rollout policy acts as a positive affine transformation of the true value function.

$$\text{If } Q_{\text{rollout}}(s, a_1) > Q_{\text{rollout}}(s, a_2) \iff Q^*_{(s, a_1)} > Q^*_{(s, a_2)}$$

The numerical values can be wildly incorrect, but as long as the simulation preserves the relative ranking of actions, the search process prioritizes the correct branches.

Absolute Value Regression (Hard)       Relative Action Ranking (Easy)
         s ───> Q(s,a) = 10.53                  s ───> Action A > Action B
         s ───> Q(s,b) = 10.12

This same intuition applies to deep reinforcement learning. In actor-critic setups, Flet-Berliac et al. demonstrated that a critic only needs to accurately rank states and actions to drive rapid policy improvement; trying to perfectly fit absolute returns introduces residual variance that slows down the actor. Taking this to its logical conclusion, Cheng et al. bypassed value functions entirely by training a label ranking model to sort all available actions from most to least promising, providing a denser, more stable training signal than standard policy gradients.

The Policy-Level Insight: Stable Off-Policy Selection

The absolute value trap becomes even more dangerous when evaluating entire policies offline. In high-stakes domains like healthcare (Tang et al.) or industrial robotics, we often train dozens of candidate policies in simulation. Before deploying one to the real world, we must evaluate its performance using only historical data collected by an older behavior policy.

Traditional Off-Policy Evaluation (OPE) tries to predict the exact expected return of a target policy, typically using importance sampling. Because importance weights compound multiplicatively over long horizons, this approach suffers from catastrophic variance.

However, the practical goal of the engineer is not to know the exact decimal return of all 100 candidate models; the goal is simply to deploy the single best model. By reframing OPE from an unsupervised regression problem into a ranking problem, we can bypass the variance of importance sampling entirely.

Irpan et al. pioneered this shift by framing OPE as an off-policy classification task, showing that neural networks find it much easier to predict which of two policies will outperform the other than to predict their exact rewards. Gao et al. confirmed this by showing that model-based OPE using robust latent representations achieves exceptionally high rank correlation across diverse tasks, making it a highly reliable tool for model selection even when absolute value predictions drift.

Traditional OPE (High Variance)        Supervised Policy Ranking (Stable)
  Policy 1 Return: 84.2 ± 30             Rank 1: Policy 2
  Policy 2 Return: 89.1 ± 35  ───────>   Rank 2: Policy 1
  Policy 3 Return: 61.0 ± 25             Rank 3: Policy 3

To formalize this, Jin et al. and Gu et al. introduced frameworks that explicitly treat policy selection as a supervised learning-to-rank problem. By training meta-models on historical performance data to predict the relative order of candidate strategies, these approaches avoid complex environment modeling. To ensure mathematical consistency when sorting these candidates, Kalyanakrishnan et al. showed how the standard partial ordering of Markov Decision Process policies can be converted into a clean, linear total ranking by aggregating state values with strict tie-breaking rules.

Why It Works: Covariance and Noise Cancellation

The mathematical power of relative evaluation stems from a simple statistical property: positive covariance cancels out shared noise.

When evaluating a new candidate policy against an existing production baseline, both policies typically traverse similar state trajectories and encounter the same underlying environmental dynamics. If the environment is noisy or has high-variance rewards, an absolute estimator must absorb all of that noise for each policy independently.

Olivier Jeunen introduced $\Delta$-OPE to exploit this phenomenon. Instead of estimating the absolute performance of a target policy $\pi$, $\Delta$-OPE directly estimates the performance difference between $\pi$ and the baseline production policy $\pi_b$. Because the trajectories of $\pi$ and $\pi_b$ are highly correlated, subtracting the baseline isolates the incremental value added by the new model, causing shared environmental noise to drop out of the equation:

$$\text{Var}(\hat{J}(\pi) - \hat{J}(\pi_b)) = \text{Var}(\hat{J}(\pi)) + \text{Var}(\hat{J}(\pi_b)) - 2\text{Cov}(\hat{J}(\pi), \hat{J}(\pi_b))$$

When covariance is strongly positive, the variance of the relative difference is significantly smaller than the variance of the absolute estimates.

This focus on marginal differences drastically reduces sample complexity. Narang et al. proved theoretically that estimating policy differences relative to a well-understood reference policy requires far fewer samples to identify the optimal strategy than learning the absolute value of every candidate from scratch.

In offline settings, Krishnamurthy et al. leveraged this by focusing strictly on the "treatment effect"—the incremental value gained by deviating from the behavior policy at a single specific time step—allowing for tighter confidence intervals. Finally, Kiyohara et al. applied this to risk management, demonstrating that subtracting the behavior policy's performance as a risk-free baseline isolates the true net improvement, protecting production systems from catastrophic deployment failures.

By recognizing that decision-making is fundamentally an ordinal task, these methods stop wasting capacity on fitting absolute scales, focusing instead on the relative boundaries that actually dictate optimal behavior.

Key Foundational Work

Batch Value Function Approximation via Support Vectors (2001) — contributed 1 concept elements to this direction.
Two Kinds of Training Information For Evaluation Function Learning (1991) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_relative_policy_evaluation_b2a6e628,
  title = {relative policy evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relative-policy-evaluation/rdr_b2a6e6289c4748938fcfec94064fd5b5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_relative_policy_evaluation_b2a6e628_v1,
  title = {relative policy evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relative-policy-evaluation/rdr_b2a6e6289c4748938fcfec94064fd5b5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake