Preference to Reward Reductions for Dueling Bandits

15 concepts9 papers1 proposal

When designing systems that learn from human input—such as search engines ranking results or large language models aligning with human values—collecting feedback is a notorious bottleneck. Humans are notoriously bad at providing absolute, numerical scores. If you ask a user to rate a response on a scale from 1 to 10, the feedback is highly subjective, noisy, and inconsistent. However, humans are excellent at providing relative feedback: if you present two options, they can easily tell you which one they prefer.

This framework is known as the dueling bandit problem. While it matches human psychology perfectly, it introduces a major algorithmic headache. Standard multi-armed bandit (MAB) algorithms operate on cardinal feedback (absolute rewards), allowing them to maintain a simple independent estimate of each arm's value. Dueling bandits operate on ordinal feedback (pairwise comparisons), which traditionally requires tracking a $K \times K$ matrix of how every single item compares to every other item. This matrix scales quadratically ($O(K^2)$), making it computationally intractable for large option spaces and requiring restrictive assumptions about transitivity (e.g., if A beats B and B beats C, then A must beat C).

The core insight of this research direction is that we do not need to throw away decades of optimized, reward-based bandit algorithms to solve preference-based problems. Instead, we can mathematically reduce dueling bandits to cardinal bandits. By transforming pairwise comparisons into synthetic, single-stream reward signals, we can use standard reward-based algorithms as modular black boxes to solve complex preference tasks efficiently.

The Borda Reduction: Turning Win Rates into Rewards

The most intuitive way to bridge the gap between relative preferences and absolute rewards is through the concept of a Borda score. Imagine a tournament where every item plays against every other item. The quality of an item can be naturally quantified by its average probability of winning against a competitor chosen at random.

This insight allows us to treat an item's win rate as a direct proxy for a cardinal reward. As shown by Falahatgar et al. (2017), treating the average probability of an item winning against a random opponent as its expected reward allows optimal, standard bandit algorithms to solve ranking and selection tasks. Because this reduction relies purely on empirical win rates, it requires no assumptions about transitivity or specific parametric noise models.

Why does this work so well in practice? Consider how an algorithm like Upper Confidence Bound (UCB) selects arms. In a standard bandit setting, UCB chooses an arm based on its estimated reward plus an uncertainty bonus. In the reduced dueling setting, we can simulate a "pull" of Arm $A$ by pairing it against a randomly sampled opponent from our pool. If Arm $A$ wins, we feed a reward of $1$ to the underlying cardinal bandit algorithm; if it loses, we feed a reward of $0$.

As highlighted by Jain et al. (2018) and Singla et al. (2016), this transformation converts subjective, noisy human comparisons into stable numerical utility scores. Instead of maintaining a massive matrix of pairwise relationships, the algorithm only needs to track a single scalar value (and its uncertainty) for each arm. This breaks the quadratic complexity bottleneck, reducing the problem to a standard linear space.

[Dueling Environment] ---> Pairwise Outcome (A beats B) 
                                   |
                                   v
                      [Borda Reduction Wrapper] 
                                   |
                                   v
[Cardinal Bandit Algorithm] <--- Synthetic Reward (e.g., 1 or 0)

Modular Black-Box Wrappers

By framing this transformation as a clean algorithmic interface, researchers can decouple the feedback mechanism from the optimization logic. Ailon et al. (2014) formalized this by introducing black-box wrappers that sit between the dueling environment and a standard cardinal bandit algorithm. This modularity means that whenever a breakthrough is made in standard reward-based bandits, it can instantly be inherited by preference-based systems without modifying the underlying optimization logic.

In a comprehensive survey of the field, Bengs et al. (2021) detailed how these reductions can be achieved either by constructing synthetic "meta-arms" or by leveraging game-theoretic formulations. This abstraction is particularly powerful in large-scale industrial applications. For instance, Zoghi et al. (2015) demonstrated that mapping the estimated number of pairwise wins to a noisy reward signal allows preference learning to scale efficiently to high-dimensional option spaces where exhaustive pairwise comparisons are completely impossible.

The Two-Player Game Formulation

An alternative, highly elegant reduction bypasses the need to sample random opponents by framing the dueling bandit problem as a two-player zero-sum game. If finding the best arm is equivalent to finding the Nash equilibrium of a preference game, why not let two independent reward-based bandit algorithms play against each other?

Saha et al. (2022) designed a mechanism where the dueling bandit problem is decomposed into two separate multi-armed bandit instances, each acting as a player.

  1. Player 1 selects Arm $A$.
  2. Player 2 selects Arm $B$.
  3. The two arms face off in a duel.
  4. The outcome of the duel is returned as a loss or reward signal to both players simultaneously.

This setup works because it forces both algorithms to co-evolve. If Player 1 discovers a strong arm, Player 2 is penalized for choosing weaker arms and is forced to find an arm that can beat it. This competitive dynamic drives both players toward the optimal arm. By reducing the problem to two independent standard MAB instances, the system automatically inherits optimal theoretical guarantees—such as tight regret bounds—across both stable (stochastic) and chaotic (adversarial) environments.

Scaling to RLHF and Contextual Decisions

The modern frontier of this research direction lies in contextual settings, most notably Reinforcement Learning from Human Feedback (RLHF) for aligning Large Language Models. Here, the choice is not just between static arms, but between different text responses given a specific prompt (the context).

To make this sample-efficient, Neopane et al. (2023) extended the Borda reduction to the offline contextual setting. By mapping dueling feedback to a cardinal value function that represents the probability of an action winning against a fixed reference distribution, they showed that standard value-based optimization and active exploration techniques can be applied directly to preference data.

Similarly, Belakaria et al. (2023) utilized this reduction to derive formal performance bounds for complex alignment tasks. By reducing pairwise comparisons to a single-stream value function, the authors proved that the suboptimality gap in learning user preferences shrinks at a predictable, optimal rate. This mathematical bridge ensures that models can strategically select the most informative prompts for human labeling, drastically reducing the cost of alignment while maintaining the rigorous guarantees of classical reward-based learning.

Key Foundational Work

Reducing Dueling Bandits to Cardinal Bandits (2014) — contributed 2 concept elements to this direction.
Copeland Dueling Bandits (2015) — contributed 2 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_dueling_to_cardinal_reduction_f2dd0591,
  title = {dueling-to-cardinal reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dueling-to-cardinal-reduction/rdr_f2dd059184214f9fba4c5648c64fc182},
  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_dueling_to_cardinal_reduction_f2dd0591_v1,
  title = {dueling-to-cardinal reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dueling-to-cardinal-reduction/rdr_f2dd059184214f9fba4c5648c64fc182/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