Preference is More Than Comparisons: Rethinking Dueling Bandits with Augmented Human Feedback

AI summary

Overview

Research area: Machine learning / online decision-making — specifically dueling bandits (DB) and interactive preference elicitation (IPE), with applications to recommendation, multi-objective optimization, and large language model (LLM) response optimization.

Technical level: Intermediate for the conceptual framing; Advanced for the theoretical sections (concentration bounds and regret analysis).

Scope: The paper proposes a model-free dueling bandit framework, IPEA-HF, that augments sparse pairwise human feedback with related observations weighted by contextual similarity, and analyzes the resulting trade-offs in sample complexity and regret (arXiv:2511.09047v1, 12 Nov 2025).

What This Paper Is About

Interactive preference elicitation tries to learn what a user wants while asking as few questions as possible, and dueling bandit algorithms are a standard tool for that because they only require pairwise comparisons ("is A better than B?"). These algorithms become inefficient when feedback is sparse, and the common fix — assuming a parametric reward model such as Bradley–Terry — is vulnerable to model misspecification and non-transitive preferences. The paper's goal is to improve the DB framework instead by augmenting the feedback itself: a single comparison is treated as also carrying information about related candidates, and that extra information is folded into the confidence bounds used to pick the next comparison.

Key Contributions

1. A model-free DB framework with a generalized concentration property. Augmented human feedback is integrated into the DB loop without predefined parametric assumptions, and its influence is quantified by linking feedback to the calibration of confidence bounds — a mechanism the authors show is shared with a broad class of DB approaches.

2. Sample complexity and cumulative regret analysis. The paper derives bounds that expose an explicit trade-off between the amount of augmented human feedback and the strength of contextual dependencies, and shows that partition-based approaches (Huang et al. 2024) fall out as a special case.

3. Prototype computational designs. A similarity-based graph structure plus an auxiliary annotation process capture contextual dependencies; the resulting algorithms are IPEA-RUCB and IPEA-DTS, instantiating the framework on top of RUCB and DTS respectively.

4. Empirical validation across three IPE benchmark families. Recommendation (Sushi, Car Preference), multi-objective optimization (DTLZ2, DTLZ7), and LLM response optimization (Anthropic Helpfulness and Harmlessness), where the proposed algorithms are reported as competitive against context-free and parametric baselines.

Main Findings

• Augmented confidence bounds concentrate. Theorem 3.1 states that under $X^k_{i,j} \sim \mathrm{Bernoulli}(w^k_{i,j} p_{i,j})$ and with $C(\delta) = \left(\frac{(4\alpha-1)K^2}{(2\alpha-1)\delta}\right)^{\frac{1}{2\alpha-1}}$, for any $\alpha > 0.5$ and $\delta \in (0,1)$, the true preference probability $p_{i,j}$ lies in the augmented interval with probability greater than $1-\delta$ for all $t > C(\delta)$.

• Related observations act as uncertainty calibration. With a dependency weight $w^r_{i,j} = 1$, a related observation shrinks the confidence bound exactly like a direct observation; with $w^r_{i,j} = 0$, the bound becomes strictly larger than the original one. The paper quantifies this with an interval-width ratio in equation (5) and a threshold condition in equation (6): $w^r_{i,j} > \eta, n_{i,j}(t)\left(\sqrt{1 + \frac{1}{n_{i,j}(t)}} - 1\right)$.

• The benefit of augmentation is conditional, not automatic. Theorem 3.2 gives $D^w_{i,j} = \frac{4\alpha}{\min_r w^{r,2}{i,j}\min{\Delta_i^2, \Delta_j^2}}$. When dependencies are strong, one pair's direct observations count toward other pairs' totals and sample efficiency can improve; when $\min_r w^r{i,j} \to 0$, $D^w_{i,j}$ grows sharply and augmentation can hurt. The recommendation is to augment selectively.

• Regret scales with dependency strength and cluster structure. Theorem 3.3 gives a cumulative regret bound of $\mathcal{O}\left(\frac{1}{\min_{i,j,r} w^r_{i,j}} \hat{K}^2 \log T\right)$ where $\hat{K} = \max{C, K_1, \dots, K_C}$ under bidirectional dependency. This subsumes the cluster-based bound $\mathcal{O}(C^2 \log T)$ from Huang et al. (2024), which assumes $w^r_{i,j} \equiv 1$.

• Model-free beats parametric in the recommendation benchmarks. Over 2,000 simulated interaction rounds on Sushi and Car Preference, context-free DB algorithms consistently outperform parametric baselines under a moderate number of candidate items, an outcome attributed to model misspecification in mixed-type feature spaces; VACDB shows a steadily increasing regret curve, indicating failed exploration.

• Deterministic selection is more robust under sparse feedback. On multi-objective optimization with 200 interaction rounds and a large candidate set ($100^2$ pairs), IPEA-RUCB outperforms IPEA-DTS. COLSTIM and VACDB are observed to repeatedly select a small subset of pairs, reflecting strong exploitation and insufficient exploration.

• Stochastic selection wins in the LLM setting. In response optimization, most algorithms are inefficient except DTS and IPEA-DTS, consistent with the empirical findings of Dwaracherla et al. (2024). Parametric methods require substantially more computational resource because of the 768-dimensional MPNet embeddings.

• Feedback augmentation can cross prompt boundaries. In response optimization, the algorithms use related observations from the same prompt as well as inter-prompt observations with high contextual similarity and dependency, which the authors present as a demonstration of augmentation beyond pairwise comparisons.

Methodology in Plain English

Rather than replacing the dueling bandit with a parametric model, the authors keep the model-free structure and change what counts as evidence. Each arm comparison produces a direct observation as usual, but it can also produce related observations about other pairs whose candidates are contextually similar. These related observations are weighted by a dependency weight $w$ between 0 and 1, and both direct and weighted related counts enter the total observation count $n_{i,j}(t)$. That total feeds into the upper and lower confidence bounds, with an extra factor $\eta$ that controls how much a related observation is trusted relative to a direct one. The algorithm (IPEA-HF) then loops: compute augmented confidence bounds, select a pair using a standard DB rule (RUCB or DTS), record the winner, extract dependencies, and augment the feedback graph for the next round.

Dependencies are obtained in two steps. First, a similarity graph over candidates is built in the context space and filtered by graph partitioning or soft clustering to focus on meaningful dependencies. Second, additional annotations — from users or LLMs — label conditional dependencies over local pairwise relations, and observations with high dependency scores are folded in. If two candidates belong to the same group, no augmentation is done for that pair. The authors argue the design is robust to annotation noise because a related observation's influence is strictly weaker than a direct one's and shrinks as direct observations accumulate, so noisy dependencies are refined or discarded over time.

The theory is developed in the standard dueling bandit language: a $K$-arm problem with a preference matrix, the Condorcet winner, per-round regret $r_t = \frac{\Delta_i + \Delta_j}{2}$ and cumulative regret $R(T) = \sum_{t=1}^{T} r_t$.

Why This Matters

The work pushes back on the assumption that the way to make preference learning sample-efficient is to impose a stronger reward model. It shows that the information content of each comparison can be expanded instead, and it does so with concentration and regret guarantees rather than heuristics. The authors also note that their result covers partition-based methods as a special case, giving the framework a unifying role across existing DB families, and that it points toward generalizing the DB framework beyond pairwise comparisons to feature-level comparisons, expert demonstrations, and explanations of human choice. The regret analysis operates at the candidate level rather than the cluster level, which the authors present as a broader guarantee than the cluster-based bound it generalizes.

Real-world applications (as identified in the paper):

• Item recommendation in personalization systems, tested on the Sushi and Car Preference datasets.
• Multi-objective optimization, in the a posteriori preference-based evolutionary multi-objective optimization (PBEMO) setting.
• Response optimization for large language models, via active exploration over a pool of responses sampled from the Anthropic Helpfulness and Harmlessness dataset.
• Interactive preference elicitation more generally, where user effort must be minimized while preferences are acquired.

Industry relevance: The paper targets personalization systems that must acquire user preferences at low human cost, including recommendation (Austin et al. 2024), multi-objective optimization (Huang et al. 2024), and LLMs (Rafailov et al. 2023). The observation that parametric DB methods are computationally expensive at 768-dimensional embedding sizes — and that some fail to explore — is a practical argument for the lighter model-free route. Code is released at https://github.com/COLA-Laboratory/IPEA-HF.

Future Directions

• Systematic handling of noisy or biased annotations. The paper argues robustness comes from the fact that related observations weigh less than direct ones and are refined or discarded over time, but it leaves open how much annotation error the framework tolerates in practice.

• Probabilistic graphical models for dependency structure. The authors suggest that as more dependency data becomes available, graphical models could capture joint distributions and conditional structures to further denoise sparse human feedback and estimate missing relationships.

• Richer feedback modalities. Extending the framework to feature-level comparisons, expert demonstrations, human explanations and rationales is framed as a key opportunity; the current empirical work demonstrates contextual similarity, LLM-powered dependency annotations, and inter-prompt observations.

• Where augmentation should be refused. The theory shows that weak dependencies raise $D^w_{i,j}$ and can degrade performance; the paper does not report a validated procedure for deciding in practice which observations to admit, which remains an open design question.

• Robustness verification. The related work notes that extensions to adversarial preferences (Saha and Gaillard 2022) and delayed feedback (Yi et al. 2024) could offer robustness verification of this approach.

Target Audience

Researchers and graduate students working on dueling bandits, interactive preference elicitation, contextual bandits, and reinforcement learning from human feedback, who want theoretical sample-complexity and regret guarantees alongside practical algorithm designs. It is also relevant to practitioners building recommendation, multi-objective optimization, or LLM response-optimization systems who need sample-efficient preference learning without committing to a Bradley–Terry-style parametric assumption.

Authors’ abstract

Interactive preference elicitation (IPE) aims to substantially reduce human effort while acquiring human preferences in wide personalization systems. Dueling bandit (DB) algorithms enable optimal decision-making in IPE building on pairwise comparisons. However, they remain inefficient when human feedback is sparse. Existing methods address sparsity by heavily relying on parametric reward models, whose rigid assumptions are vulnerable to misspecification. In contrast, we explore an alternative perspective based on feedback augmentation, and introduce critical improvements to the model-free DB framework. Specifically, we introduce augmented confidence bounds to integrate augmented human feedback under generalized concentration properties, and analyze the multi-factored performance trade-off via regret analysis. Our prototype algorithm achieves competitive performance across several IPE benchmarks, including recommendation, multi-objective optimization, and response optimization for large language models, demonstrating the potential of our approach for provably efficient IPE in broader applications.