In traditional machine learning, we assume the world provides us with a clear yardstick. We ask a model to predict a value, and the environment returns a precise scalar reward—a "7.4 out of 10" or a "$50.00 profit." However, in complex human-centric domains like search engine ranking, robotic gait optimization, or fine-tuning large language models, these absolute numbers are often a fiction.
Humans are notoriously poor at providing consistent absolute scores for subjective experiences. As noted by Armin Stahl and Thomas Gabel in Optimizing Similarity Assessment in Case-Based Reasoning, users struggle to quantify utility but can easily state that one case is more useful than another. This shift from absolute rewards to relative preferences is the core of a growing research direction that seeks to build robust AI systems using only pairwise comparisons.
The Dueling Bandit Problem
The fundamental abstraction for this research is the "dueling bandit." Unlike a standard multi-armed bandit where you pull one arm and see a reward, a dueling bandit requires you to choose two arms and observe which one "wins" the duel.
The challenge is that a single win provides very little information. If Arm A beats Arm B, we don't know if A is a masterpiece and B is trash, or if they are both mediocre and A just happened to be slightly better. To overcome this, algorithms like RUCB (Relative Upper Confidence Bound), developed by Masrour Zoghi, Maarten de Rijke, and colleagues in Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem, maintain a set of "potentially optimal" arms. By strategically dueling these candidates, the system can narrow down the best option without ever needing to know its true numerical value.
Bridging Preferences and Reinforcement Learning
This "comparison-only" philosophy extends beyond simple choices into the realm of sequential actions, known as Preference-based Reinforcement Learning (PbRL). This is the engine behind Reinforcement Learning from Human Feedback (RLHF).
A major hurdle in PbRL is that standard RL algorithms (like Q-learning) are built to maximize a sum of scalar rewards. How do we bridge the gap? Yinglun Xu and David C. Zhu propose a surprisingly simple solution in Optimal Reward Labeling: Bridging Offline Preference and Reward-Based Reinforcement Learning: Binary Reward Labeling (BRL). By labeling steps in a "chosen" trajectory as $+1$ and "rejected" steps as $-1$, researchers can treat preference data as a standard RL problem, often matching the performance of agents trained on ground-truth rewards.
Theoretical Efficiency: Why Relative Feedback Works
One might assume that because relative feedback is "weaker" than absolute feedback, it would be significantly slower to learn. However, recent theoretical work suggests the opposite.
In Logarithmic Regret for Online KL-Regularized Reinforcement Learning, Heyang Zhao, Quanquan Gu, and Tong Zhang demonstrate that the mathematical landscape created by preference-based regularizers (like the KL-penalty used in ChatGPT) is actually quite "benign." This allows agents to achieve logarithmic regret, meaning they stop making significant mistakes much faster than traditional theory would predict.
Furthermore, Aadirupa Saha has pioneered algorithms like MinMaxDB in Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability. These methods reduce the complex task of learning from preferences to a simple square-loss regression problem, proving that we can be both computationally efficient and statistically optimal using only relative signals.
Beyond Optimization: Learning Constraints and Logic
The utility of relative feedback isn't limited to finding the "best" item; it can also be used to learn the underlying rules of a system.
- Learning Constraints: In Interactively Learning Preference Constraints in Linear Bandits, David Lindner and Andreas Krause show that by asking users to compare the feasibility of different options, a system can learn complex safety boundaries without needing explicit "violation" scores.
- Learning Logic: Eric Hsiung, Joydeep Biswas, and Swarat Chaudhuri developed REMAP in Automata Learning from Preference and Equivalence Queries, which reconstructs the logical state machines governing a task simply by asking a teacher to compare two sequences of actions.
The Intuition: Comparisons as Constraints
Why does this work? The intuition is to treat every pairwise comparison as a linear inequality. If a user prefers $A$ over $B$, they are telling the system that $Utility(A) > Utility(B)$. As the system collects more comparisons, it builds a massive system of inequalities that carves out the shape of the true utility function.
Whether it's personalizing a robotic exoskeleton (Maegan Tucker et al., Preference-Based Learning for Exoskeleton Gait Optimization) or tuning hearing aids (Tanya Ignatenko et al., On Sequential Bayesian Optimization with Pairwise Comparison), the core insight remains: we don't need to know how much a user likes something; we only need to know what they like better.