Preference-based Online Learning with Dueling Bandits: A Survey

Motivation

• Standard multi-armed bandits require balancing exploration and exploitation while learning from noisy numerical rewards to minimize error or cumulative regret.The learner repeatedly selects arms, observes rewards, and seeks performance relative to the best arm; this setting supports applications including medical treatment design, online advertising, and recommendation systems.Source: §1 · pp. 1–2
• Preference-based feedback replaces difficult-to-quantify rewards with potentially noisy pairwise comparisons or rankings, supporting applications such as information retrieval, crowdsourcing, and Xbox gamer ranking.The goal can be to approximate an underlying target ranking from comparisons that may be noisy or partially non-coherent (Chen et al., 2013; Hofmann, 2013; Radlinski et al., 2008; Guo et al., 2012).Source: §1 · p. 2

Survey scope

• The survey updates and substantially extends Busa-Fekete and H¨ullermeier (2014) by reviewing preference-based multi-armed bandit methods and organizing them by assumptions about the data-generating process and pairwise comparisons.Its scope is the stochastic setting, where feedback comes from an unknown but stationary probabilistic process.Source: §1 · p. 2
• The survey excludes adversarial data-generating processes except for brief discussion in Section 5, while covering other extensions, multi-dueling, practical applications, and open issues.Sections 2–4 recall the basic problem and methods, Section 6 addresses multi-dueling, Section 7 discusses applications, and Section 8 concludes with open issues; adversarial work includes Ailon et al. (2014a), Dud´ık et al. (2015), Gajane and Urvoy (2015), and Zimmert and Seldin (2019).Source: §1 · pp. 2–3

2. The Basic Preference-based Multi-Armed Bandit Problem

• A learner compares pairs among K fixed arms over finite or infinite horizons, observing stationary independent Bernoulli outcomes with reciprocal probabilities q_i,j; ties may be excluded or reduced to coin-flip decisions.Arm a_i beats a_j when q_i,j > 1/2, and comparisons become harder as q_i,j approaches 1/2.Source: §2 · p. 3, §2.1 · p. 4

2.1 Learning Protocol

• Pairwise probabilities are estimated from observed wins and comparisons, but adaptive sampling makes comparison counts random and can bias the estimates; Hoeffding-based confidence intervals support high-probability decisions.The protocol updates empirical winning proportions using the comparisons selected through time t.Source: §2.1 · p. 4

2.2 Learning Tasks

• Preference-based learning targets include a Condorcet winner, full rankings, top-k identification or ranking, preference-relation or ranking-distribution estimation, and epsilon-optimal approximations, but cycles can prevent exact winners or rankings.Top-k identification generally requires less information than top-k ranking, while epsilon-preferability permits approximation when exact targets are difficult to define.Source: §2.2 · pp. 4–5, §2.2.1 · p. 5, §2.2.2 · p. 5

2.3.1 Regret Bounds

• Average regret accounts for the quality of both compared arms, with strong and weak variants forming a hierarchy; expected or high-probability bounds may be gap-dependent or gap-independent, and no-regret bounds grow sublinearly in T.The average regret is zero when the learner compares the target arm with itself, enabling final commitment after sufficient confidence.Source: §2.3.1 · pp. 6–7

2.3.2 PAC Setting

• PAC learning limits the number of pairwise comparisons while returning an epsilon-optimal target with probability at least 1−delta, whereas exact sample complexity requires the correct target and reflects intrinsic preference-gap hardness.PAC comparison costs do not depend on the suboptimality of the selected arms, unlike regret minimization.Source: §2.3.2 · p. 8, §2.3.3 · p. 8

2.4 Algorithm Classes

• Algorithm classes include MAB reductions or generalizations, online optimization, noisy sorting, tournaments, and challenges, using concepts such as confidence-based exploration, sorting, successive elimination, and champion–challenger comparisons.These classes are not mutually exclusive, and their applicability depends on assumptions about the preference process, arm set, and target.Source: §2.4 · p. 9, §2.4.1 · p. 9, §2.4.2 · p. 9

Learning from Coherent Pairwise Comparisons

• The learner estimates pairwise preference probabilities qi,j, yet its prediction target is the best arm or a ranking ≻ over all arms.Information about Q is useful only insofar as it supports identifying the target, which may not be well-defined for arbitrary preference relations.Source: §3 · pp. 10–11
• Pairwise probabilities must be sufficiently coherent for the learner to approximate and eventually identify the intended target as the sample size grows.Without such coherence, estimating Q may not provide information about the best arm or ranking.Source: §3 · p. 11
• Different consistency and regularity assumptions on Q substantially influence how preference-based multi-armed bandit problems are tackled algorithmically.The survey categorizes approaches according to these assumptions across this and the following two sections.Source: §3 · p. 11

3.1 Axiomatic Approaches

• Axiomatic approaches exploit preference structure to enable efficient algorithms, covering low noise, total ordering, transitivity, identifiability, no ties, and Condorcet-winner assumptions.The survey also distinguishes γ-relaxed, moderate, and weak stochastic transitivity, plus the stochastic triangle inequality.Source: §3.1 · pp. 11–12
• WST is necessary and sufficient for a complete ranking consistent with all pairwise preferences, whereas low noise does not imply triplet conditions such as SST or STI.The relationship overview represents implications among assumptions, while the low-noise counterexample shows that no such triplet structure follows automatically.Source: §3.1 · p. 13
• WST does not imply either a total order or general identifiability, as the all-0.5 preference relation satisfies WST while satisfying neither condition.Other counterexamples show that a total order need not imply SST, and no ties need not imply a Condorcet winner.Source: §3.1 · p. 14
• MST and γ-RST do not imply one another: constructions satisfy MST but violate γ-RST, or satisfy γ-RST but violate MST, for suitable parameter choices.The examples retain a total arm order while separating the two transitivity conditions.Source: §3.1 · p. 14
• STI is incomparable with stronger-than-WST transitivity assumptions: examples separately satisfy SST but violate STI, and satisfy STI but violate MST or γ-RST.The survey concludes by reviewing methods under these axioms, their goals, guarantees, novelties, and tabulated coverage of regret minimization and PAC or exact sample-complexity tasks.Source: §3.1 · pp. 14–15

Interleaved Filtering

• Under a total arm order, strong stochastic transitivity, and the stochastic triangle inequality, IF identifies the best arm with probability at least 1 −δ.It sequentially compares a selected active arm against the others and eliminates it when another arm defeats it.Source: §3.1.1 · p. 15
• A pruning rule eliminates any arm confidently shown unable to be best, after which exploitation repeatedly compares the arm selected by IF against itself.Source: §3.1.1 · p. 15
• For known finite horizon T, Interleaved Filtering achieves an expected regret order that is also shown to be the lower bound in this setting.Source: §3.1.1 · p. 15

3.1.2 Beat the Mean

• Beat-The-Mean (BTM) uses random active-arm pairings and confidence intervals on aggregate winning scores to eliminate significantly inferior arms.Its relaxed stochastic-transitivity assumptions are required only relative to the best arm.Source: §3.1.2 · pp. 15, 17
• BTM has a finite-horizon high-probability regret bound that is stronger than IF’s expected-regret guarantee and matches it when γ = 1.BTM is also analyzed as an (ε, δ)-PAC learner for identifying an ε-optimal arm.Source: §3.1.2 · pp. 17, 19

3.1.3 Relative Upper Confidence Bound

• RUCB requires only a Condorcet winner and selects comparisons using optimistic upper confidence bounds under the optimism-in-the-face-of-uncertainty principle.It selects a potential Condorcet winner and compares it with the competitor most likely to challenge that status.Source: §3.1.3 · p. 19
• RUCB provides both expected and high-probability horizonless regret bounds valid at every time step, unlike the finite-horizon explore-and-exploit analyses of IF and BTM.Its bounds are not directly comparable with IF and BTM because their constants have different forms.Source: §3.1.3 · p. 19

3.1.4 MergeRUCB

• MergeRUCB scales RUCB to many arms by processing batches locally, repeatedly eliminating arms with insufficient upper confidence bounds, and merging batches as they shrink.Under assumptions limiting uninformative pairs, it yields a high-probability regret bound that eliminates RUCB’s additive K^2 term because comparisons remain local.Source: §3.1.4 · p. 20

3.1.5 MergeDTS

• MergeDTS combines MergeRUCB’s batching assumptions with Double Thompson Sampling, matching MergeRUCB’s high-probability regret order but requiring the horizon in advance.Experiments report MergeDTS as superior to MergeRUCB and other state-of-the-art dueling-bandit algorithms.Source: §3.1.5 · p. 20

3.1.6 Relative Confidence Sampling

• Relative Confidence Sampling (RCS) combines RUCB-style upper confidence bounds with Beta posteriors to propose duel candidates, then challenges the first arm with its toughest competitor.Experiments on learning-to-rank data show satisfactory cumulative-regret performance, but RCS has no theoretical cumulative-regret upper bound.Source: §3.1.6 · pp. 20–21

3.1.7 Relative Minimum Empirical Divergence

• RMED assumes a Condorcet winner and selects empirically promising arms using relative minimum empirical divergence based on Bernoulli KL divergence.The empirical best arm minimizes divergence, while a potentially good set contains arms whose divergence is sufficiently close to the minimum.Source: §3.1.7 · p. 21
• RMED1 achieves an expected regret upper bound of order O(K^2+ε), but its constant factor leaves a gap relative to the asymptotic lower bound.The lower bound applies to consistent algorithms for preference relations with a Condorcet winner or total order of arms.Source: §3.1.7 · pp. 21–22
• RMED2 adapts RMED1’s second-arm selection to estimate the gap to the lower-bound constant, while RMED2FH uses a known horizon T to obtain an asymptotically optimal bound.RMED2FH replaces the difficult analysis of RMED2 with a non-exploring gap estimate derived using the known time horizon.Source: §3.1.7 · p. 22

3.1.8 Winner Stays

• Winner Stays for weak regret (WS-W) repeatedly duels a current champion against a worthy challenger until one is displaced, then proceeds round by round through the available arms.The champion is the arm with the most overall duel wins, while the challenger has the second-most among arms not yet considered in the round.Source: §3.1.8 · p. 22
• WS-S separates exploration from exploitation by running one WS-W round per epoch and then self-dueling the resulting champion for an exponentially increasing exploitation phase.The self-duels implement full commitment to keep cumulative strong regret low.Source: §3.1.8 · p. 22
• WS-W has expected cumulative weak regret constant in time when preferences have no ties, with guarantees also stated for Condorcet-winner and total-order settings.The bounds are optimal in their dependence on T, though not in their dependence on calibrated preference probabilities.Source: §3.1.8 · pp. 22–23
• WS-S obtains expected cumulative strong-regret bounds in Condorcet-winner and total-order settings, with optimal dependence on T but non-optimal dependence on calibrated preference probabilities.The WS-S analysis uses the exploration and exploitation structure described above.Source: §3.1.8 · p. 23
• Peköz et al. (2020) revise the WS-W analysis and obtain an expected regret upper bound under a Condorcet-winner assumption without requiring tie-free preferences.The analysis uniquely uses the Gambler’s ruin problem to bound suboptimal-arm pulls rather than relying on Chernoff bounds.Source: §3.1.8 · p. 23

3.1.9 Beat the Winner

• BTW uses queue-based champion–challenger rounds for weak-regret minimization, moving the defeated arm to the queue’s end and the winner to its front.MBTW adds win-history scores and random score-weighted challengers, showing satisfactory empirical performance against BTW and WS-W without theoretical analysis.Source: §3.1.9 · p. 23

3.1.10 Knockout Tournaments

• Knockout is an (ε, δ)-PAC best-arm algorithm under total order, γ-relaxed stochastic transitivity, and stochastic triangle inequality, improving BTM and matching the γ = 1 lower bound.It repeatedly pairs surviving arms, eliminates one from each pair, and geometrically schedules round-wise confidence and approximation levels.Source: §3.1.10 · p. 24

3.1.11 Sequential Elimination

• Seq-Eliminate uses adaptive confidence levels to eliminate defeated arms and is order-optimal in the high-confidence regime δ ≤ 1/K, while a modified version handles δ > 1/K.The modification first finds a good champion on a subset, constructs a surviving candidate subset, and then reruns the elimination procedure when necessary.Source: §3.1.11 · pp. 24–25

3.1.12 Opt-Max

• Opt-Max extends best-arm identification to moderate stochastic transitivity through Soft-Seq-Elim, whose speed and accuracy improve when the initial champion requires few changes.Opt-Max uses three confidence-level-specific variants and is order-optimal in its stated regime; under only weak stochastic transitivity, worst-case PAC identification requires K^2 comparisons.Source: §3.1.12 · p. 25

3.1.13 Binary-Search-Ranking

• Binary-Search-Ranking provides an (ε, δ)-PAC ranking method under strong stochastic transitivity and the stochastic triangle inequality, while later improvements remove superfluous logarithmic factors.The method ranks anchors, assigns arms to bins through binary-tree random walks, and applies repeated checking to reduce comparison complexity.Source: §3.1.13 · pp. 25–26
• Binary-Search-Ranking’s lower bounds show that PAC ranking requires quadratic comparisons under strong stochastic transitivity, with the same lower bound also holding under moderate transitivity plus stochastic triangle inequality.The results indicate that the stochastic triangle inequality facilitates learning, while nearly best-arm identification differs from nearly best ranking by a logarithmic factor.Source: §3.1.13 · p. 26

3.1.14 Top-k identification via Quick Select

• T-k-S repeatedly partitions selectable arms into groups of at most 2k, applies Epsilon-Quick-Select, and stops when k arms remain.EQS eliminates arms confidently excluded from a subset’s nearly top-k set, while recursively handling preferred, uncertain, and nonpreferred arms around a random pivot.Source: §3.1.14 · pp. 26–27
• T-k-S is an (ε, δ)-PAC top-k algorithm whose sample complexity matches the authors’ lower bound under its stated assumptions.The result assumes a total preference order, strong stochastic transitivity, the stochastic triangle inequality, and k ≤ K/2.Source: §3.1.14 · pp. 26–27

3.1.15 Approx-Prob

• Approx-Prob estimates every pairwise probability within ε with optimal sample complexity O(·) for δ ≥ 1/K, given an ε/8-ranking.The supplied passage states the asymptotic form but does not provide its expression.Source: §3.1.15 · p. 27
• Approx-Prob reduces comparisons by exploiting strong stochastic transitivity and the stochastic triangle inequality to constrain, correct, or skip pairwise estimates.It rounds estimates to ε-grid points and compares arms in nested index order to maximize the use of triplet constraints.Source: §3.1.15 · p. 27

3.1.16 Robust Query Selection

• Query Selection identifies the exact ranking by randomly testing previously unconsidered pairs and dueling only those whose preference cannot be inferred from past comparisons.The method uses a geometric embedding with an unknown reference point and relates ambiguity to active linear-separator labeling in d+1 dimensions.Source: §3.1.16 · pp. 27–28
• Robust Query Selection handles noisy duels by repeating each ambiguous comparison and selecting its majority winner.With per-pair repetitions log(2K log(K)/δ)/2h^2 and min_{1≤i<j≤K}|Δ_i,j| ≥ h, it returns the true ranking with sample complexity O(·).Source: §3.1.16 · p. 28

3.1.17 Verification-based Solution

• Karnin’s verification framework alternates best-arm search with confidence-based verification, continuing only when the candidate is rejected and stopping when optimality is confirmed.The framework uses FindBestArm and VerifyBestArm with geometrically decreasing verification confidence and constant search error probability.Source: §3.1.17 · p. 28
• For Condorcet dueling bandits, the framework identifies a candidate using confidence intervals, then verifies each alleged loser against its toughest competitor.The first subroutine eliminates ordered pairs under three confidence-estimate conditions, while the second checks the resulting candidate and competitors.Source: §3.1.17 · pp. 28–29
• Karnin’s method improves on RMED’s sample complexity by a multiplicative factor K_ε when δ is sufficiently large.The stated bound hides logarithmic factors, and the improvement follows by transforming RMED’s expected-regret bound into a sample-complexity bound.Source: §3.1.17 · p. 29

3.1.18 Parallel Selection and Partition

• Under a total arm order, Braverman et al. (2016) provide high-probability algorithms for kth-best identification and top-k partitioning with low round complexity and optimal sample complexity.They study adaptivity through round complexity, ranging from non-adaptive schedules to fully adaptive duel selection.Source: §3.1.18 · p. 29
• Their procedure repeatedly samples arms, filters them using random anchors and interquartile win ranges, and combines two runs to recover the true partition and kth-best arm.A reduced subset supplies a pivot whose comparisons partition all arms into the best-k set and its complement.Source: §3.1.18 · pp. 29–30

3.1.19 Single Elimination Tournament

• Mohajer et al. (2017) construct Select as a layered single-elimination tournament that identifies the best arm with probability at least 1 −δ.Pairs are randomly formed at each layer, one arm is retained after comparison, and the process continues until one arm remains.Source: §3.1.19 · p. 30
• They generalize Select to Top by finding subgroup winners, organizing them in a heap, and successively extracting top-k arms, although the δ-dependent sample complexity is not established.The survey conjectures a top-k identification order involving the adjacent-rank gap ∆_(k),(k+1), while reporting the authors’ stated complexity in Table 3.Source: §3.1.19 · p. 30
• Top’s leading sample-complexity factor differs from Select’s by a logarithmic factor in the (ε, δ)-PAC setting.The comparison concerns the leading factor of the two tournament-based procedures.Source: §3.1.19 · p. 30

3.1.20 Sequential-Elimination-Exact-Selection

• SEEBS and SEEKS impose strong stochastic transitivity and the stochastic triangle inequality on Q, extending the same best- or top-k-selection goal considered by Mohajer et al. (2017).SEEBS targets one best arm, whereas SEEKS targets the top-k arms.Source: §3.1.20 · p. 31
• SEEBS finds the best arm by repeatedly selecting a near-best champion, partitioning arms into three preference classes, and eliminating challengers that are surely worse.Round-wise confidence adaptation preserves the overall confidence level δ until one arm remains.Source: §3.1.20 · p. 31
• SEEKS identifies the top-k arms by alternating near-best and near-worst selection to build a candidate pool while eliminating arms classified as surely not preferred.It stops when the candidate pool has at least k arms or when candidates plus selectable arms contain at most k arms, then completes the set as specified by the termination case.Source: §3.1.20 · p. 31

3.1.21 Iterative-Insertion-Ranking

• IIR addresses unknown lower bounds on calibrated pairwise preference gaps by adapting BinarySearch’s idea through binary insertion sort over a preference interval tree, as proposed by Ren et al. (2019).The tree’s leaf order represents the underlying total order of the arms.Source: §3.1.21 · p. 32
• IIR ranks all arms by repeatedly inserting each arm into a preference interval tree using pairwise duels and confidence-controlled traversal.The insertion restarts with an updated gap guess when the arm cannot be placed with sufficient certainty.Source: §3.1.21 · p. 32
• IIR guarantees recovery of the true ranking with probability at least 1−δ and has nearly optimal sample complexity when strong stochastic transitivity holds.The comparison uses a lower bound for any learner required to return the true ranking with confidence level δ.Source: §3.1.21 · p. 32
• The IIR gap estimate minj̸=i ∆i,j generally differs from the smaller gap to an arm’s two ranking neighbors, but they coincide under strong stochastic transitivity.This distinction determines how the insertion confidence conditions relate to the ranking structure.Source: §3.1.21 · p. 32

3.2 Regularity Through Latent Utility Functions

• Utility-based dueling assumes u:A→R and comparison probabilities σ(u(ai)−u(aj)); strict monotonicity and σ(0)=1/2 preserve utility ordering and equal-utility symmetry.Common admissible links include logistic and linear link functions.Source: §3.2 · p. 33
• With an injective utility function, the link assumptions imply the low-noise model, whereas non-injective utilities need not provide a total order but still satisfy SST.The same conclusions extend to infinitely many arms under a suitable link function, while latent utilities provide a surrogate for quantitative rewards.Source: §3.2 · pp. 33–34

3.2.1 Dueling Bandits Gradient Descent

• DBGD estimates an unbiased gradient approximation through random comparisons and, on a d-dimensional ball of radius R, has a bounded expected regret under Lipschitz utility and link assumptions.The method projects exploratory points into the arm space and updates toward the winner when the exploratory point loses.Source: §3.2.1 · p. 36

3.2.2 Noisy Comparison-based Stochastic Mirror Descent

• NC-SMD reduces utility-based regret minimization to locally-convex optimization and achieves a regret bound that is optimal up to a logarithmic factor under suitably tuned learning rates.The analysis assumes a compact convex arm set with non-empty interior and establishes a matching lower bound in order.Source: §3.2.2 · p. 36

3.2.3 Reduction to Value-based MAB

• Ailon et al. (2014b) reduce utility-based preference learning to value-based MAB algorithms, obtaining asymptotically identical preference regret for finite arms and an extra log T factor for infinite arms.Their finite-arm Doubler assigns value-based bandit instances to arms, while the infinite-arm MultiSBM uses an epoch-based two-player reduction.Source: §3.2.3 · p. 37

3.2.5 Dueling Bandits Temporary Elimination Algorithm

• DBTEA maintains active arms with non-positive lower confidence bounds on suboptimality gaps, duels each active arm twice per phase, and achieves an expected-regret upper bound of O(K)+O(∑ ˜∆i).Its analysis uses a novel anytime concentration inequality for sums of sub-Gaussian random variables, and experiments show superiority in some large-arm, moderate-horizon instances.Source: §3.2.5 · p. 38

3.2.6 Round-Efficient Dueling Bands

• Round-efficient dueling identifies the highest-utility arm with probability at least 1 −δ by estimating active-arm utilities and eliminating arms below the empirically best arm’s confidence threshold.A modified stopping criterion also yields an (ε, δ)-PAC learner, with stated round and pairwise sample complexities in the source.Source: §3.2.6 · p. 39

3.2.7 Multisort

• With high probability, Multisort uses O(log^5 K) QuickSort calls, each requiring O(K log K) pairwise comparisons, and achieves o(K) Spearman footrule distance from the underlying arm ranking.Source: §3.2.7 · pp. 39–40

3.3 Regularity Through Statistical Models

• Rank-data models represent the generative process as a distribution P over all arm rankings, with pairwise preferences obtained as marginals and targets defined as the best arm or modal ranking.Learning therefore consists of inferring P from pairwise comparisons; the optimal arm has the highest probability of occupying rank 1, while the target ranking is the distribution’s mode.Source: §3.3 · pp. 40–41

3.3.1 Mallows

• The Mallows model makes the center ranking the unique mode and imposes a total order with analytically determined pairwise probabilities, making rank decisions easier than some preferred-arm comparisons.MallowsMPI finds the most preferred arm, MallowsMerge finds the modal ranking, and estimating the full distribution in KL divergence can require extremely high sample complexity even for small K.Source: §3.3.1 · pp. 41–42

3.3.2 Plackett-Luce

• The Plackett-Luce model assigns each arm a positive strength, generates rankings stagewise with selection probability proportional to strength, and has a mode obtained by sorting strengths decreasingly.PLPAC and PLPAC-AMPR provide (ε, δ)-PAC procedures for an ε-optimal arm and ranking, respectively, using budgeted QuickSort with O(K log K) complexity while preserving pairwise stability.Source: §3.3.2 · p. 43

4. Learning from Non-coherent Pairwise Comparisons

• Non-coherent preferences can contain cycles and transitivity violations, so learning targets must be derived from pairwise probabilities rather than an assumed ground-truth ranking.The section considers preference relations Q as primary and surveys alternative targets for settings where Condorcet winners or total rankings may not exist.Source: §4 · p. 44, §4.2 · p. 46

4.1 Alternative Target Concepts

• Copeland, Borda, and random-walk procedures define rankings for every preference relation, but only Copeland is guaranteed to match an existing total order.In the illustrated three-arm relation, Borda and random-walk rank a2 above a1 despite the total order a1 ≻ a2 ≻ a3; under stated stochastic-transitivity or low-noise conditions, Borda and random walk can coincide with the total order.Source: §4.1 · p. 45
• Alternative winner concepts include Copeland, Borda, random-walk, and von Neumann winners, with von Neumann selecting a randomized strategy that guarantees a higher winning probability against every fixed arm.When a Condorcet winner exists, Copeland and von Neumann coincide with it, while Borda and random walk require low noise; without one, von Neumann generally differs from the other concepts.Source: §4.1 · pp. 45–46

4.2.1 Copeland Confidence Bound

• For Copeland regret minimization, CCB uses optimistic and pessimistic confidence scores to identify candidates, eliminate likely losers, and select informative competitors, while SCB scales through KL-UCB-style simulated rewards.CCB targets small-arm problems; SCB uses horizonless doubling periods and its induced best-arm distributions correspond to Copeland winners.Source: §4.2.1 · pp. 48–49

4.2.2 Copeland Winners Relative Minimum Empirical Divergence

• CW-RMED derives exploration from a Copeland regret lower bound, while ECW-RMED replaces a costly complexity computation with a surrogate and can eliminate the Copeland-winner multiplicity factor.The two methods have asymptotically matching complexity terms when |CP(Q)| ≥2, and ECW-RMED improves CCB’s multiplicative constants.Source: §4.2.2 · p. 50

4.2.3 Double Thompson Sampling

• D-TS samples preference relations from Beta posteriors, combines optimistic Copeland selection with sampled informative opponents, and D-TS+ resolves ties using estimated cumulative regret.Both algorithms have expected Copeland-regret guarantees without preference ties; D-TS also has a refined bound under an additional assumption, and the refined bounds apply to D-TS+.Source: §4.2.3 · pp. 50–51

4.2.4 Sparse Sparring

• Sparse Sparring adopts the game-theoretic objective of approaching the von Neumann winner’s performance, using regret defined through the zero-sum game matrix.Its regret is measured against the maximum average game payoff over arms up to time T.Source: §4.2.4 · p. 51
• SPAR2 exploits sparsity in a unique von Neumann winner by using two Exp3 copies and confidence regions to eliminate arms outside the winner’s support.Its support-monitoring procedure can be computationally inefficient, motivating conservative stability-based conditions; the resulting regret bound improves over straightforward Exp3 sparring.Source: §4.2.4 · pp. 51–52

4.2.5 General Tournament Solutions

• UCB-TS generalizes dueling-bandit learning to tournament solutions such as the top cycle, uncovered set, and Banks set by selecting candidates and challenging their validity with upper confidence bounds.The resulting high-probability regret bounds depend on a tournament-solution complexity term, have a worst-case order, and leave matching lower bounds open; when a Condorcet winner exists, the alternative solutions coincide with it.Source: §4.2.5 · p. 52

4.2.6 PAC Rank Elicitation

• PAC rank elicitation uses NDP and MRD distances, while γ-insensitive Copeland and sum-of-expectations relations reduce instability by controlling order strictness and task difficulty.Greedy algorithms compare arms expected to reduce surrogate-ranking confidence bounds; sample complexity is analyzed for MRD, whereas NDP complexity remains open because small preference changes can strongly alter rankings.Source: §4.2.6 · pp. 53–54

4.2.7 Borda-Ranking

• Borda reduction converts duels against random arms into Bernoulli observations with expected rewards equal to Borda scores, enabling PAC identification of an ǫ-Borda arm and ranking.The ranking algorithm estimates each score within ǫ/2 using Hoeffding’s inequality and sorts the estimates, achieving an ǫ-Borda-optimal ranking with confidence at least 1 −δ.Source: §4.2.7 · pp. 54–55

4.2.8 Round-Efficient Dueling Bandits

• A round-efficient modification keeps all arms active to obtain unbiased Borda-score estimates from random-opponent duels and returns an ǫ-Borda-optimal arm with probability at least 1 −δ.Its round complexity follows the prescribed horizon, while pairwise sampling complexity is K times that order; the analysis suggests the log(ǫ−1) term may be removable relative to prior results.Source: §4.2.8 · p. 55

4.2.9 Hamming-LUCB

• Hamming-LUCB identifies a top-k Borda partition by comparing confidence-bound candidates until the current (k −ǫ)th-best lower bound exceeds the current (n −k −ǫ)th-worst upper bound.Assuming distinct Borda scores, it returns a partition (2ǫ)-close in Hamming distance; up to logarithmic factors, its sample complexity is optimal, and Bradley-Terry assumptions do not yield qualitatively stricter lower bounds.Source: §4.2.9 · pp. 55–56

4.2.10 Preference-based Racing

• Preference-based racing uses successive selection and rejection to identify top-k arms under Copeland, Borda, or random-walk rankings, but without structural assumptions it must estimate the full preference relation.This lack of exploitable regularities produces sample-complexity bounds that are not as tight in the number of arms as bounds for structured settings.Source: §4.2.10 · p. 56

4.2.11 Voting Bandits

• SAVAGE models Copeland, Borda, and Condorcet identification as generic bandit optimization, maintaining confidence regions and eliminating distributions that cannot affect the optimal decision.It queries relevant distributions round-robin and uses task-specific pessimistic-versus-optimistic tests; winner-identification sample complexity is characterized, while explore-then-exploit regret bounds are generally not strict for Condorcet or Copeland targets.Source: §4.2.11 · p. 57

4.2.12 Successive Elimination

• SECS exploits preference sparsity through partial Borda gaps, improving over straightforward successive elimination with Borda reduction under a unique Borda winner.It initially uses standard elimination, then activates an additional criterion based on potential top candidates; the cited analysis also provides a matching lower-bound regime for moderately balanced pairwise probabilities.Source: §4.2.12 · pp. 58–59

4.2.13 Bayesian Sequential Sampling

• POCBA and PKG target top-k Borda selection using Bayesian sampling criteria, and both are asymptotically optimal as the sampling budget becomes infinite.POCBA maximizes expected AEPCS improvement, whereas PKG selects duels by approximated information gain about changes to the current top-k set; both stop when AEPCS exceeds a threshold.Source: §4.2.13 · p. 59

4.2.14 Active Ranking

• Active Ranking identifies the correct Borda-based coarse ranking with probability at least 1−δ and is nearly optimal under pairwise preferences bounded below by 3/8.It maintains active arms and assigns them to clusters using confidence bounds; the lower bound applies when qi,j ≥ 3/8 for distinct arms, and parametric assumptions do not yield qualitatively stricter lower bounds.Source: §4.2.14 · p. 60

5.1 Adversarial Dueling Bandits

• In adversarial utility-based dueling bandits, REX3 has regret of the same order as EXP3, while feeding SPARRING with TSALLIS-INF preserves EXP3’s upper-bound order.In the stochastically constrained adversarial setting, TSALLIS-INF yields an expected regret upper bound of the same order for SPARRING.Source: §5.1 · p. 61

5.2 Contextual Dueling Bandits

• Contextual dueling algorithms seek von Neumann winners: Sparring Exp4.P has O(√(KT ln(|Π|/δ))) regret, whereas oracle-based methods trade weaker regret for logarithmic dependence on |Π|.SparringFPL and ProjectedGD use a classification oracle and attain O((KT)^(2/3) ln^(1/3)(|Π|/δ)) regret with time and space logarithmic in |Π|.Source: §5.2 · p. 62

5.3 Dueling Bandits on Posets

• Poset dueling addresses incomparable arms and indistinguishability, with UnchainedBandits approximating the Pareto front and decoys enabling exact recovery under bounded sample complexity.Audiffren and Ralaivola (2017) use peeling to control comparisons of indistinguishable arms; decoys add a term to regret and yield O(K width(S) log(NK^2/δ)/Δ^2) sample complexity.Source: §5.3 · p. 63

5.4 Graphical Dueling Bandits

• Graphical dueling restricts comparisons to graph edges and studies PAC identification, with topology-specific procedures for lines, trees, general networks, and contextual graphs.The NNE algorithm handles general connected graphs, while its contextual version has sample complexity O(B log^2 B), with B = K D^d2.Source: §5.4 · pp. 63–64

5.5 Dueling Bandits with Dependent Arms

• With feature-dependent utilities, CTB exploits arm dependencies and achieves expected weak-regret bounds scaling generally with K^d′ and as O(K^2d′) in special cases.The model uses known arm features and an unknown weight parameter; CTB maintains cells for pairwise preference sequences and selects arms from highest-scoring cells.Source: §5.5 · p. 64

5.6 Partial Monitoring Games

• In the partial-monitoring formulation, utility-based dueling bandits are easy instances with locally observable adjacent loss differences and regret of order ˜O(√T), matching IDS’s ˜O(√(KT)) result.The encoding uses arm pairs as actions, ternary feedback, and utility vectors as outcomes; Kirschner et al. (2020) obtain the same order as REX3.Source: §5.6 · p. 65

5.7 Dueling Bandits for Qualitative Feedback

• For qualitative ordinal feedback, Thompson Condorcet and Borda methods target respective winners, while Thompson Condorcet and Borda-UCB achieve O(K log(T)) regret under their stated winner conditions.Thompson Borda sampling instead has polynomial regret in T, whereas Borda-UCB matches the theoretical lower bound.Source: §5.7 · pp. 65–66

5.8 Combinatorial Pure Exploration for Dueling Bandits

• Combinatorial pure exploration defines Condorcet and Borda winners over maximum matchings, then uses approximately uniform sampling in CLUCB-Borda-PAC and CLUCB-Borda-Exact to avoid exponential costs.CLUCB-Borda-PAC is an (ε,δ)-PAC algorithm for identifying the Borda matching winner, with sample complexity governed by graph structure and gap terms.Source: §5.8 · p. 67
• A lower bound on a specific subclass of instances shows that both algorithms are almost optimal in sample complexity for those instances.Source: §5.8 · p. 68
• CAR-Cond and CAR-Parallel identify a Condorcet matching winner, with CAR-Parallel running parallel CAR-Cond variants at selected confidence levels.CAR-Cond formulates the winner as an optimization problem, relaxes it to convex optimization, and iteratively evaluates undecided edges using confidence bounds and an approximate-solution oracle.Source: §5.8 · p. 68
• Both algorithms have polynomial running time and derived sample-complexity bounds; CAR-Parallel’s bound replaces arm-level quantities with graph-level duel counts and edge-gap terms.The bounds use K_G, the number of possible duels in G, and gap terms Δ_e,e′, with summations analogous to the corresponding expression for CAR-Cond.Source: §5.8 · p. 68

6.1 Learning Protocol

• Multi-dueling bandits let the learner compare admissible subsets of arms, whose action spaces are generally much more complex than the pairwise dueling-bandit space.The action space may contain fixed-size subsets, subsets up to a maximum size, and singleton commitments; the basic dueling setting corresponds to subsets of size at most two plus singletons.Source: §6.1 · p. 69

6.2 Feedback Mechanisms

• Feedback may reveal all pairwise preferences, only the most preferred arm, an ordered list of the l′ most preferred arms, or arbitrary combinations of partial preferences.Most-preferred-arm feedback can be modeled through discrete choice models or random utility models, while l′-arm feedback is more informative than winner-only feedback when l′ > 1; its relation to all-pairwise feedback is generally unresolved because rank-breaking may introduce bias.Source: §6.2.1 · p. 70, §6.2.2 · pp. 70–71, §6.2.3 · p. 72

6.3 Learning Tasks

• The learning tasks extend standard best-arm and ranking objectives to finding the best subset, but the appropriate target depends on the feedback mechanism and its underlying preference model.Preference-relational feedback can support Condorcet-style targets, whereas discrete-choice or probabilistic-ranking models motivate targets based on choice probabilities, latent utilities, or distribution modes.Source: §6.3 · p. 73, §6.3.1 · pp. 73–74, §6.3.2 · p. 75

6.3.1 Best Arm and Ranking of Arms

• Generalized Condorcet, Copeland, and Borda notions may be computationally difficult, fail to exist or be unique, and need not agree even when a generalized Condorcet winner exists.If a generalized Condorcet winner exists, it is the unique generalized Copeland winner, but the generalized Borda winner can differ or remain non-unique.Source: §6.3.1 · p. 74

6.3.2 Best Subset of Arms

• Under a random utility model, the best subset can maximize expected action utility rather than simply contain the arms with the highest individual utilities.For fixed-size action spaces, the top-l arms under a chosen ranking provide one natural definition, while expected-utility maximization yields another.Source: §6.3.2 · p. 75

6.4 Performance Measures

• Performance is evaluated through PAC sample complexity or cumulative regret, with regret defined by averaged preferences, preference-probability shortfall, or expected utility.The appropriate regret notion depends on what the feedback permits the learner to infer; generalized averaged regret is zero only for singleton commitment to the target arm.Source: §6.4 · pp. 75–76
• Most-preferred-arm feedback can have the same total-order sample-complexity lower bound as dueling feedback, whereas guarantees improve with the number l′ of preferred arms.Ren et al. (2019) establish the unchanged lower bound when A = A_l; increasing l′ improves theoretical guarantees.Source: §6.4 · p. 76

6.5.1 Multileaving

• Multileaving methods extend interleaving to multiple rankers, with MGD, DP-DBGD, and MP-DGD using multiple directions to improve practical ranking performance over DBGD.Experiments on information-retrieval datasets show superior NDCG performance over DBGD, but these approaches lack DBGD-style theoretical analyses.Source: §6.5.1 · p. 79

6.5.2 Multi-Dueling / 6.5.3 SelfSparring

• MDB uses conservative and non-conservative confidence estimates to explore optimistic Condorcet winners, while SelfSparring controls up to l selected arms with independent or Gaussian-process Thompson sampling.MDB performs well empirically for generalized averaged regret but has no theoretical guarantees; IndSelfSparring achieves asymptotically optimal no-regret rate O(K ln(T)/∆) under approximate linearity.Source: §6.5.2 · p. 80, §6.5.3 · pp. 80–81

6.5.4 Battling Bandits

• Battling-Duel inherits a black-box dueling algorithm’s regret order, and its lower bound does not improve with subset size, while Battling-Doubler and Battling-MultiSBM incur a leading factor l.These results hold under a Condorcet winner and generalized average regret; the latter algorithms’ bounds assume a linear link function.Source: §6.5.4 · pp. 81–82

6.5.5 MaxMin-UCB

• Under the PL model, MaxMin-UCB targets generalized average regret, while Rec-MaxMin-UCB is asymptotically optimal for generalized top-l′ regret in l′, K, and T.The analyzed generalized average regret is equivalent up to constants to preference-probability shortfall under compact PL parameters.Source: §6.5.5 · pp. 82–83

6.5.6 Preselection Bandits

• In PL preselection bandits, optimal subsets may combine top and worst arms, while TRCB and CBR achieve near-optimal expected-utility regret despite combinatorial action spaces.For A = A_l, the regret bounds are independent of l; for A = A_full, CBR has an O(√(KT)) bound and an asymptotic Ω(K log(T)) lower bound.Source: §6.5.6 · pp. 83–84

6.5.7 Choice Bandits

• WBA identifies a generalized Condorcet winner through champion–challenger rounds and is order optimal for the MNL model under shortfall-of-preference-probabilities regret.Its analysis uses concentration of conditional preference estimates even when direct pairwise estimates may be biased.Source: §6.5.7 · pp. 84–85

6.5.8 Nearly Best Arm of Plackett-Luce Model

• For PL nearly-best-arm identification, Trace-the-best uses challenge rounds whereas Divide-and-Battle uses tournaments, with Divide-and-Battle improving the logarithmic sample-complexity term.Both algorithms return an ε-best arm with probability at least 1 − δ.Source: §6.5.8 · pp. 85–86
• Under Plackett-Luce feedback, observing only the most preferred arm does not improve sample complexity over dueling bandits, whereas richer top-l′ feedback can facilitate learning.The lower bound for most-preferred-arm feedback matches the dueling-bandit lower bound up to logarithmic factors; Trace-the-best and Divide-and-Battle are extended to top-l′ feedback using rank-breaking.Source: §6.5.8 · p. 86
• PAC-Wrapper is an (ǫ, δ)-PAC learner with sample complexity of the stated order; when ǫ=0, it returns the arm with largest latent utility with probability at least 1−δ and has nearly optimal sample complexity.Source: §6.5.8 · p. 87

6.5.9 Nearly Best Arm of RUMs

• For IID-RUMs, Sequential-Pairwise-Battle is optimal up to logarithmic terms when every pair’s minimum advantage ratio exceeds the stated noise-dependent threshold.The algorithm adapts Divide-and-Battle’s round-wise approximation qualities using CRUM and remains valid with top-l′ feedback under the Min-AR condition.Source: §6.5.9 · p. 88

6.5.10 Nearly Best Ranking of Plackett-Luce Model

• For nearly best rankings under the Plackett-Luce model, Beat-the-Pivot and Score-and-Rank achieve sample complexity that is optimal up to logarithmic factors, with no improvement over dueling bandits for most-preferred-arm feedback.Both methods first find an anchor with Find-the-Pivot; Beat-the-Pivot ranks via pairwise preferences, whereas Score-and-Rank uses relative utility estimates.Source: §6.5.10 · p. 88

6.5.11 Exact Top-k Arms of Plackett-Luce Model

• For exact top-k identification, AlgPairwise and AlgMulti-wise return the top-k set with high probability and are nearly optimal across logarithmic and superlogarithmic action-size regimes.AlgPairwise exploits transitivity among sampled pairwise comparisons, while the superlogarithmic-regime algorithm matches the same order and has a lower bound of that order up to polylogarithmic terms.Source: §6.5.11 · p. 89

6.6.1 Stochastic Click Bandits

• Stochastic click bandits model ordered-list interaction and possible non-clicks, so they differ fundamentally from multi-dueling bandits in how arm order matters and neither framework is a special case of the other.Click models represent stochastic choice over ordered sets, whereas multi-dueling bandits do not model the user’s top-to-bottom scanning behavior.Source: §6.6.1 · p. 90

6.6.2 Dynamic assortment optimization

• Dynamic assortment optimization assumes known product revenues and permits customers to refuse purchase, unlike multi-dueling bandits, where revenues are absent and a dummy arm could represent no choice.This modeling difference can change the optimal action subset and would require rethinking learning tasks and performance measures if incorporated into multi-dueling bandits.Source: §6.6.2 · p. 90

6.6.3 Best-of-k bandits

• Best-of-k bandits typically provide numerical feedback, although marked-bandit feedback is qualitative and may potentially be represented in multi-dueling bandits using a dummy arm.Marked-bandit feedback reports the highest-reward arm when it is in the chosen subset and otherwise reports void information.Source: §6.6.3 · pp. 90–91

Human judgments and information retrieval

• DBGD-based methods improve gesture naturalness from pairwise human judgments and enhance online learning-to-rank performance using historical interaction data.Pairwise gesture comparisons are easier and less noisy than absolute judgments, while the retrieval approach uses Probabilistic Interleave and discounted cumulative reward.Source: §7 · p. 91

Clinical stimulation

• CorrDuel exploits correlations among stimulation configurations, outperforming non-correlated methods synthetically and matching specialized physicians in a live spinal-cord-stimulation trial.It updates active arm sets rather than only pairs, addressing the huge action space that slows convergence.Source: §7 · p. 91

Safe clinical optimization

• StageOpt safely optimizes preference-based spinal-cord stimulation by expanding a known safe region before Bayesian optimization, with suggested therapies outperforming experienced physicians.It models safety and utility with Gaussian processes and uses KernelSelfSparring for preference feedback.Source: §7 · pp. 91–92

Structured prediction and human-robot interaction

• Structured Dueling Bandits enables direct SMT optimization from partial translation-quality feedback, while DTS learns satisfactory exercise preference rankings and significantly reduces ranking errors against random selection.The SMT method updates model parameters from response-based assessments; the human-robot interaction study presents exercise pairs for user comparison.Source: §7 · p. 92

Ranking aggregation and algorithm configuration

• TrustAwareRankingBasedMAB aggregates students’ partial peer-assignment rankings under a Mallows model, whereas CPPL adaptively selects solver configurations and outperforms state-of-the-art methods.CPPL maintains and replenishes candidate parametrizations using utility-function confidence bounds, genetic crossover, and racing across mixed-integer-programming and satisfiability datasets.Source: §7 · pp. 92–93

Preference-based tree search

• PB-MCTS applies RUCB-guided qualitative successor selection to binary-rollout tree search, inducing exponentially more explored paths and being evaluated on 8-puzzle solving.Unlike classical policies that choose one successor and observe one path, PB-MCTS triggers two roll-outs at each node.Source: §7 · pp. 92–93

• PB-MAB extends standard bandits from real-valued rewards to pairwise preferences and other qualitative feedback, including partial rankings, while surveying problems, algorithms, evaluation criteria, and applications.Source: §8 · p. 93
• The field remains less mature than standard bandits because preference cycles, ambiguous regret definitions, differing assumptions, and incompatible targets and performance measures hinder a unified framework.Open theoretical and algorithmic gaps remain even in the standard preference-based setting.Source: §8 · pp. 93–94
• Future work should develop practically motivated extensions, evaluate algorithms in real applications such as crowdsourcing, and improve software availability through resources such as the duelpy Python package.The survey explicitly frames these directions as part of its non-exhaustive open-problem agenda.Source: §8 · pp. 94, 96
• Lower bounds remain unknown for general tournament solutions and weak regret minimization, limiting conclusions about algorithmic optimality; distribution-learning bounds are also needed for models such as Mallows and Plackett-Luce.For Mallows distribution estimation, Busa-Fekete et al. (2014b) use KL divergence, but the reported sample complexity scales poorly with the number of arms.Source: §8 · p. 94
• Learning becomes easier under stronger preference assumptions, but multi-dueling lacks comparable transitivity properties; online tests are needed to verify assumptions such as Mallows, Plackett-Luce, stochastic transitivity, and Condorcet structure.Existing testing work is limited, while the benefits of adaptive sampling and sample-optimal learning for ranking distributions remain largely unresolved; Busa-Fekete et al. (2019) characterize optimal learning for Mallows.Source: §8 · pp. 94–95
• Open algorithmic directions include learning Kemeny or MFAS rankings from partial preference information and combining preference duels with real-valued pulls to reduce the resources needed for target identification.The hybrid setting was studied by Xu et al. (2020), while MFAS ranking is NP-hard when Q is known and admits a PTAS.Source: §8 · pp. 95–96