Research map / Bandits and online learning / RL theory and MDPs

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

NeurIPS 2025 · Bandits and online learning › RL theory and MDPs · approach: Linear function approximation in RL · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MAUPO, an online PbRL algorithm that selects multi-action subsets maximizing average uncertainty and receives Plackett-Luce ranking feedback, proving suboptimality decreasing with subset size and removing the exponential e^B dependence in the leading term.

Problem

Online preference-based RL with ranking feedback over action subsets: existing theory for multiple comparisons shows no improvement (and often degradation) with longer feedback, and most bounds carry an exp(B) dependence on the parameter norm.

Approach

Select assortments greedily to maximize the average mean-centered uncertainty under the PL model, update parameters with online mirror descent on PL or rank-breaking losses, and use a warm-up/non-warm-up round split in the analysis to remove the e^B factor from the leading term.

Key results

• Theory: suboptimality O~((d/T) sqrt(sum 1/|S_t|)) with no exp(B) in the leading term, and a lower bound Omega(d/(K sqrt T)).
• Synthetic experiments (d=5, N=100): performance improves as maximum assortment size K increases under both PL and RB losses, and MAUPO outperforms DopeWolfe, Uniform, and Best&Ref at K=5.
• On TREC-DL and NECTAR with gemma-2b features and Mistral-7B reward, MAUPO (RB) improves with K and outperforms baselines by a large margin at K=3.

Measured effects reported in the paper

Surprising findings

• Rank-breaking (pairwise decomposition) of ranking feedback is both cheaper and empirically better than the exact PL loss.
• The exponential e^B dependence widely assumed in PbRL and dueling bandit analyses is argued to be an artifact of loose analysis rather than inherent.

Limitations

• Theorem for RB loss requires K^2 <= (2 sqrt6 + 12 sqrt3 B) d, a small-K regime assumption.
• Lower bound matches upper bound only up to a K factor and only when |S_t|=K.
• Non-leading term d^2 K^4/(kappa T) with kappa = e^{-6B} still carries exponential dependence on B.

Experimental setup

Datasets: TREC-DL NECTAR

Benchmarks: synthetic linear PbRL TREC-DL NECTAR

Metrics: suboptimality gap

Baselines: DopeWolfe Uniform assortment Best&Ref

Builds on: MNL bandit online confidence bound (Lee and Oh 2024 style analysis) dueling bandits XPO DopeWolfe

Closest papers by meaning

• Provable Reward-Agnostic Preference-Based Reinforcement Learning (ICLR 2024 · similarity 0.91)
• Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF (ICLR 2025 · similarity 0.90)
• Listwise Reward Estimation for Offline Preference-based Reinforcement Learning (ICML 2024 · similarity 0.90)
• Query-Policy Misalignment in Preference-Based Reinforcement Learning (ICLR 2024 · similarity 0.90)
• Greedy Sampling Is Provably Efficient For RLHF (NeurIPS 2025 · similarity 0.90)
• Avoiding exp(R) scaling in RLHF through Preference-based Exploration (NeurIPS 2025 · similarity 0.89)