Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options

AI summary

Overview

• Research area: Online preference-based reinforcement learning (PbRL) and reinforcement learning from human feedback (RLHF), specifically the theory of learning from ranking feedback over multiple options rather than only pairwise comparisons.
• Technical level: Advanced. The paper is a theoretical machine-learning paper built on the Plackett–Luce (PL) ranking model, online mirror descent, confidence-bound arguments, and matching upper/lower bound analysis.
• Scope: The paper introduces an algorithm called M-AUPO for online PbRL with PL ranking feedback over action subsets of size up to K, proves an upper bound on its suboptimality gap that improves as subset size grows, proves a near-matching lower bound, and reports synthetic and real-world experiments.

What This Paper Is About

Most theoretical work in preference-based reinforcement learning assumes the learner only ever sees pairwise comparisons (this option was preferred to that one). A few recent papers study richer ranking feedback over multiple options, but their guarantees do not improve — and can get worse — as the ranking gets longer, even though a ranking over K actions contains (K choose 2) pairwise comparisons and should be more informative. This paper asks whether an algorithm can provably do better under multiple-option feedback than under pairwise feedback in online PbRL, and answers yes by proposing M-AUPO and analyzing it under the Plackett–Luce model.

Key Contributions

1. Improved sample efficiency from larger subsets. The authors propose M-AUPO (Maximizing Average Uncertainty for Preference Optimization), which selects an action subset (assortment) of size up to K by greedily maximizing average uncertainty. Its suboptimality gap is ~O( (d/T) * sqrt( sum_{t=1}^{T} 1/|S_t| ) ), where T is the number of rounds, d is the feature dimension, and |S_t| is the size of the subset offered at round t. The bound strictly decreases as subset size grows, which the authors state is the first theoretical PbRL result with ranking feedback to explicitly show improved sample efficiency as a function of subset size.

2. Elimination of the exponential dependence on the parameter-norm bound. Prior PbRL and dueling-bandit guarantees commonly carry an O(e^B) factor, where B bounds the norm of the unknown parameter ||θ||_2 ≤ B. M-AUPO's leading term has no O(e^B) dependence, achieved without auxiliary techniques such as specialized sampling schemes or prior knowledge of κ. The authors argue this shows the O(e^B) dependence is an artifact of loose analysis rather than inherent, and that their proof technique (dividing rounds into warm-up and non-warm-up phases only in the analysis) can be plugged into existing PbRL or dueling-bandit analyses, including regret-minimization frameworks, without changing the algorithms.

3. Rank-breaking as a better computational and empirical alternative. The paper presents both a naive Plackett–Luce loss approach and a rank-breaking (RB) loss approach that decomposes a length-|S_t| ranking into its (|S_t| choose 2) pairwise comparisons. The RB formulation is reported to achieve superior computational efficiency and empirical performance relative to the PL counterpart.

4. A near-matching lower bound. The authors prove a lower bound of Ω( d / (K sqrt(T)) ) under the PL model with ranking feedback, where K is the maximum subset size, matching the upper bound up to a factor of K. They also report empirical evaluation on synthetic and real-world datasets showing improved performance for larger K and superiority over existing baselines.

Main Findings

• Larger assortments provably help. Under the PL model, M-AUPO's suboptimality gap depends on the sum of 1/|S_t| over rounds, so offering larger subsets directly lowers the bound. The full statement in Theorem 1 is SubOpt(T) = ~O( d/T * sqrt( sum_{t=1}^{T} 1/|S_t| ) + d²K⁴/(κT) ), with κ := e^{-6B}, holding with probability at least 1 − δ for T ≥ e^{K/d}. For sufficiently large T the second term is non-leading.

• The lower bound scales with subset size. The established lower bound is Ω( d / (K sqrt(T)) ). The authors state this shows that leveraging richer ranking information (larger K) provably improves sample efficiency, and that it matches the upper bound up to a K factor.

• No O(e^B) in the leading term, unlike prior ranking-feedback work. Table 1 in the paper compares settings and guarantees: Zhu et al. [93] (offline) have ~O( e^B K² sqrt(d/T) ); Mukherjee et al. [49] (online) have ~O( e^B K³ d / sqrt(T) ); Thekumparampil et al. [76] (online, no context) have ~O( e^B K³ d / sqrt(T) ). All three carry the e^B factor, while this work's leading term does not. The paper notes that very recent works [14, 20] also avoid e^B but rely on auxiliary techniques or prior knowledge of κ and are restricted to pairwise feedback.

• The paper's setting is more general than the closest prior online ranking work. Thekumparampil et al. [76] study a context-free (singleton context) setting; this paper studies a stochastic contextual setting where contexts x_t are drawn from a fixed but unknown distribution ρ, and the learner selects assortments of size at most K.

• Warm-up analysis drives the improvement. The proof separates rounds into a warm-up set T^w (rounds with large non-centered uncertainty) and non-warm-up rounds. In non-warm-up rounds, the quantity 1/μ̇((ψ_{t,π*(x_t),π̂_T(x_t)})^T θ*) is bounded by (1+e)², which is what allows the leading term to avoid the exponential parameter dependence. Warm-up rounds contribute only a non-leading term.

• Assortment selection is greedy and tractable. Exactly maximizing the average-uncertainty objective is generally NP-hard, so the paper uses a greedy rule: start from a pair maximizing Equation (10), then repeatedly add the action a* maximizing Δ_t(a|S) = f_t(S ∪ {a}) − f_t(S), accepting it if Δ_t(a|S) ≥ 0, until |S| = K or no non-negative gain remains. Greedy selection for the PL loss costs O(N²d³ + LNK²d²), where L is the (approximate) expectation cost over the ranking σ; for the RB loss it costs O(N²d³ + NK³d²) and is exact, requiring no ranking-expectation approximation. This avoids enumerating all (N choose K) subsets.

• Online estimation is constant-cost per round. Instead of maximum likelihood estimation (whose cost grows linearly with the number of rounds t), the paper uses online mirror descent (OMD) updates. Storage is O(d²) thanks to incremental updates of the Hessian-like matrices. Per-round computational cost is O(K²d³) for the PL parameter update and O(K³d³) for the RB parameter update. Each OMD step is solvable by a single projected gradient step.

• Empirical results are reported but specific numbers are not in the provided text. The paper states that M-AUPO was evaluated on both synthetic and real-world datasets, showing improved performance for larger K and superiority over existing baselines. The truncated content does not include the experiment tables, baselines, or numeric results, so no specific experiment figures are reported here.

Methodology in Plain English

The learner repeatedly faces a context (a prompt or situation), picks a small set of candidate actions, and receives back a full ranking of those actions from a labeler. Rather than always asking for a two-way comparison, it can ask for a ranking over up to K options. The paper assumes the labeler's rankings follow the Plackett–Luce model, a standard probabilistic model for rankings in which higher-reward actions are more likely to appear earlier in the list. The reward is assumed to be a linear function of a known feature map of context-action pairs, with an unknown parameter vector θ*, and θ* is assumed to lie in a ball of radius B.

The core algorithmic idea is to choose the offered set so that it maximizes average uncertainty: the selected actions should be ones whose feature vectors, measured under the current uncertainty matrix H_t^{-1}, are spread out and hard to predict. Because exactly maximizing this objective is NP-hard, the algorithm starts with the most informative pair of actions and then adds actions one at a time as long as doing so increases the objective by a non-negative amount. This is the "maximizing average uncertainty" idea in the algorithm's name. The intuition is that more spread-out, uncertain subsets produce more informative ranking feedback, so a longer ranking can shrink the reward estimation error faster.

Learning proceeds round by round. After receiving the ranking, the algorithm updates its estimate of θ* using online mirror descent, which keeps per-round computation independent of how many rounds have passed. The paper gives two variants of this update: one that uses the full Plackett–Luce negative log-likelihood (which requires taking expectations over the ranking distribution), and one based on rank-breaking that decomposes the ranking into all its pairs and treats them as independent comparisons. At the end, the algorithm outputs a policy that picks the action with the highest estimated reward for each context.

For the theory, the authors prove a confidence bound on the parameter estimate (extending prior work on the multinomial logit model), then decompose the suboptimality gap into realized regrets plus a martingale difference term bounded by Azuma–Hoeffding. The key analytic device is splitting rounds into warm-up and non-warm-up phases. On non-warm-up rounds the per-round quantity behaves well, which is precisely what removes the exponential dependence on B from the leading term — the trick is purely in the analysis and does not change the algorithm itself.

Why This Matters

This work is a step toward explaining why asking humans (or labelers) for rankings instead of yes/no comparisons should pay off. It gives the first theoretical result in PbRL with ranking feedback showing that performance improves as a function of subset size, and it argues that the widely observed O(e^B) factor in PbRL and dueling-bandit theory is a limitation of loose analysis rather than a fundamental barrier. Because the warm-up/non-warm-up argument is described as transferable to existing regret-minimization analyses, it may improve older bounds retroactively without altering their algorithms.

Real-world applications noted in the paper:

• Aligning large language models with human values and preferences (RLHF). PbRL is the foundational framework for RLHF when feedback comes as preferences instead of scalar rewards, and this paper's setting directly models ranking feedback over multiple candidate responses.
• Robot training, where hand-designing reward functions demands substantial engineering effort.
• Recommender systems, where rankings over candidate items are a natural form of user feedback.
• Stock prediction and clinical trials, both listed among the domains where PbRL has been successfully applied.

Industry relevance: Collecting human preference labels is expensive, so getting more signal per label matters. A ranking over K items carries (K choose 2) pairwise comparisons from a single annotation. If a system can use longer rankings and provably learn faster, that translates into fewer annotation rounds and lower labeling cost for model alignment and ranking systems. The paper's rank-breaking variant is especially relevant here: it is exact and avoids extra expectation cost, and RLHF pipelines such as the one of Ouyang et al. [57] already use rank-breaking-style pairwise decomposition.

Future Directions

• Close the gap between the upper and lower bounds. The upper bound matches the lower bound only up to a factor of K. Tightening the analysis to remove this factor is the obvious next theoretical target.
• Relax the linear reward assumption. The current guarantees rest on a linear reward model with a known feature map and a bounded parameter ball. Extending the analysis to nonlinear or neural reward models — the practical setting for LLM alignment — is unaddressed.
• Transfer the warm-up phase analysis more broadly. The paper states in Appendix G.1 that the technique for removing O(e^B) can be incorporated into existing PbRL and dueling-bandit analyses. Verifying and quantifying those gains across specific prior algorithms would be a concrete follow-up.
• Understand the practical limits of large K. M-AUPO's per-round cost rises quickly with subset size — O(K²d³) for the PL update and O(K³d³) for the RB update, plus assortment-selection costs of O(N²d³ + LNK²d²) or O(N²d³ + NK³d²). How well this scales to the very large action spaces used in real ranking and alignment systems is an open practical question that the paper's experiments (synthetic and real-world only, with no numeric details in the provided text) do not settle.

Target Audience

This paper is aimed at theoretical machine-learning researchers working on preference-based reinforcement learning, RLHF theory, dueling bandits, and learning-to-rank. It is also relevant to researchers who want to understand when and why multi-option ranking feedback beats pairwise feedback, and to practitioners in LLM alignment or recommender systems who need a principled argument for collecting longer rankings rather than binary comparisons. A reader needs comfort with convex optimization, confidence bounds, and bandit-style regret analysis to follow the proofs; the high-level message about subset size improving sample efficiency is accessible to a broader machine-learning audience.

Authors’ abstract

We study online preference-based reinforcement learning (PbRL) with the goal of improving sample efficiency. While a growing body of theoretical work has emerged-motivated by PbRL's recent empirical success, particularly in aligning large language models (LLMs)-most existing studies focus only on pairwise comparisons. A few recent works (Zhu et al., 2023, Mukherjee et al., 2024, Thekumparampil et al., 2024) have explored using multiple comparisons and ranking feedback, but their performance guarantees fail to improve-and can even deteriorate-as the feedback length increases, despite the richer information available. To address this gap, we adopt the Plackett-Luce (PL) model for ranking feedback over action subsets and propose M-AUPO, an algorithm that selects multiple actions by maximizing the average uncertainty within the offered subset. We prove that M-AUPO achieves a suboptimality gap of $\tilde{\mathcal{O}}\left( \frac{d}{T} \sqrt{ \sum_{t=1}^T \frac{1}{|S_t|}} \right)$, where $T$ is the total number of rounds, $d$ is the feature dimension, and $|S_t|$ is the size of the subset at round $t$. This result shows that larger subsets directly lead to improved performance and, notably, the bound avoids the exponential dependence on the unknown parameter's norm, which was a fundamental limitation in most previous works. Moreover, we establish a near-matching lower bound of $\Omega \left( \frac{d}{K \sqrt{T}} \right)$, where $K$ is the maximum subset size. To the best of our knowledge, this is the first theoretical result in PbRL with ranking feedback that explicitly shows improved sample efficiency as a function of the subset size.