PaperlayerView exact revision on arXiv

Source-linked AI summary

Preference-based Online Learning with Dueling Bandits: A Survey

Viktor Bengs, Robert Busa-Fekete, Adil El Mesaoudi-Paul, Eyke Hüllermeier

arXiv:1807.11398v2cs.LGstat.ML

TL;DR

Numerical rewards are unavailable in many online-learning applications, motivating preference-based bandits that learn from qualitative pairwise comparisons. This survey synthesizes stochastic PB-MAB problems and methods, organizing them by feedback assumptions and discussing their targets, algorithms, and limitations. It shows that the field encompasses diverse algorithms and extensions, while preference incoherence and the lack of transitivity can constrain identifiable targets and efficient learning.

  • Problem

    Many applications provide qualitative pairwise preferences instead of numerical rewards, creating a need to understand online learning with preference-based feedback.

  • Method

    The paper surveys stochastic preference-based bandit problems and methods, classifying them primarily by assumptions about pairwise comparisons and the data-generating process.

  • Results

    The survey covers diverse algorithmic approaches, including queue-based, tournament, axiomatic, multi-dueling, and other extensions of preference-based bandits.

  • Takeaways & Limitations

    Preference-based bandit learning requires matching targets and algorithms to the coherence, transitivity, and structure assumed for pairwise feedback.

  • Takeaways & Limitations

    The survey focuses on stochastic processes, while adversarial processes receive only brief treatment; multi-dueling settings also lack readily available transitivity properties.

Abstract

from arXiv · show

In machine learning, the notion of multi-armed bandits refers to a class of online learning problems, in which an agent is supposed to simultaneously explore and exploit a given set of choice alternatives in the course of a sequential decision process. In the standard setting, the agent learns from stochastic feedback in the form of real-valued rewards. In many applications, however, numerical reward signals are not readily available -- instead, only weaker information is provided, in particular relative preferences in the form of qualitative comparisons between pairs of alternatives. This observation has motivated the study of variants of the multi-armed bandit problem, in which more general representations are used both for the type of feedback to learn from and the target of prediction. The aim of this paper is to provide a survey of the state of the art in this field, referred to as preference-based multi-armed bandits or dueling bandits. To this end, we provide an overview of problems that have been considered in the literature as well as methods for tackling them. Our taxonomy is mainly based on the assumptions made by these methods about the data-generating process and, related to this, the properties of the preference-based feedback.

1. Introduction

Multi-armed bandits traditionally learn from noisy numerical rewards, but many applications provide only qualitative pairwise preferences. This survey examines preference-based bandits by organizing existing problems and methods according to assumptions about the stochastic feedback.

  • Standard multi-armed bandits require repeated online selection of alternatives while observing numerical, typically noisy, reward signals.The framework has been applied to medical treatment design, online advertising, and recommendation systems.
  • Numerical rewards can be difficult or impossible to obtain, motivating learning from qualitative pairwise comparisons or rankings.Such feedback appears in applications including online information retrieval and crowdsourcing, where comparisons may be noisy or partially incoherent.
  • Preference-based multi-armed bandits extend online bandit learning by allowing the learner to compare arms qualitatively rather than observe numerical rewards.
  • The survey reviews the stochastic PB-MAB setting and organizes methods mainly by assumptions about the data-generating process and pairwise comparisons.Adversarial processes are largely outside its scope, while multi-dueling and other extensions receive dedicated discussion.

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

In preference-based bandits, the learner compares arms and observes stochastic pairwise outcomes, then estimates preferences to identify an arm, ranking, or top-k set. These targets and regret or sample-complexity analyses are complicated by incoherent preferences, cycles, and adaptive sampling.

  • A learner repeatedly compares pairs of arms and observes stationary, independent Bernoulli outcomes governed by unknown reciprocal pairwise probabilities.Ties are conceptually possible but excluded from the survey’s main treatment.
  • Pairwise win frequencies provide estimates of preference probabilities, but adaptive comparison counts can make those estimates biased.Confidence intervals can be constructed using Hoeffding-type bounds.
  • Preference-based learning typically estimates the pairwise matrix Q, although the prediction target is often a best arm, full ranking, or top-k subset.The target may be undefined or non-unique when preferences contain cycles.
  • Top-k identification generally requires less information than top-k ranking because the ranking determines the top-k set, but not conversely.
  • Expected regret bounds depend on pairwise probabilities, the number of arms, and the iteration number, rather than directly on numerical reward means.The bound is technically analogous to expected regret bounds for value-based algorithms such as UCB.

3. Learning from Coherent Pairwise Comparisons

Because pairwise preferences may not define a coherent target, PB-MAB methods impose consistency or regularity assumptions. The survey categorizes approaches by these assumptions and their effect on learning algorithms.

  • Figure 1 presents a taxonomy of stochastic PB-MAB algorithms.
  • Learning in PB-MAB essentially estimates pairwise probabilities, but the desired arm or ranking may not be well-defined without sufficiently coherent preferences.
  • Different consistency assumptions on Q substantially influence how PB-MAB problems are formulated and solved.The survey organizes these approaches according to their assumptions about pairwise preferences.

3.1 Axiomatic Approaches

Axiomatic approaches make PB-MAB learnable by imposing structure on pairwise preferences, ranging from total orders and weak transitivity to stronger stochastic transitivity and identifiability conditions. The survey compares these assumptions through implication relationships and counterexamples.

  • Axiomatic Approaches: No ties do not guarantee a Condorcet winner, because each arm can be beaten by another arm in a cyclic preference relation.
  • Axiomatic Approaches: Weak stochastic transitivity supports a ranking consistent with pairwise preferences, while stronger conditions constrain calibrated preference gaps across arm triplets.The survey defines relaxed stochastic transitivity, moderate stochastic transitivity, and the stochastic triangle inequality through inequalities on these gaps.
  • Axiomatic Approaches: A total order over arms does not imply strong stochastic transitivity: one example has ∆1,3 = 0.1 < 0.5 = max{∆1,2, ∆2,3}.
  • Axiomatic Approaches: WST does not imply either a total order or general identifiability, as shown by a preference relation with all entries equal to 0.5.
  • Axiomatic Approaches: The survey reviews methods under axiomatic assumptions, covering their conditions, learning goals, theoretical guarantees, and algorithmic innovations.

3.1.1 Interleaved Filtering

Interleaved Filtering (IF) identifies the best arm through sequential one-versus-all comparisons under strong stochastic transitivity and the stochastic triangle inequality. For a known finite horizon, its expected regret matches the lower bound.

  • 3.1.1 Interleaved Filtering: IF sequentially eliminates arms by repeatedly comparing a selected arm against the other active arms in a one-versus-all manner.The algorithm identifies the best arm with probability at least 1 −δ under its stated assumptions.
  • 3.1.1 Interleaved Filtering: IF achieves expected regret of order O(...), and this rate is also shown to be a lower bound for the finite-horizon setting.

3.1.2 Beat the Mean

Beat-The-Mean (BTM) relaxes the transitivity assumptions used by IF by comparing sparsely sampled active arms and eliminating arms with statistically inferior empirical scores. Its high-probability regret guarantee strengthens IF’s expected-regret result and matches it when γ = 1.

  • 3.1.2 Beat the Mean: BTM requires only relaxed stochastic transitivity and imposes the relaxed properties relative to the best arm rather than across all arm triplets.
  • 3.1.2 Beat the Mean: The survey organizes related regret-minimization and PAC algorithms in separate tables, including RUCB, MergeRUCB, MergeDTS, and RCS.
  • 3.1.2 Beat the Mean: BTM selects an under-compared active arm, pairs it with a uniformly sampled active arm, and eliminates it when another arm has a significantly higher empirical winning score.The score estimates an arm’s probability of winning against a randomly selected active arm, with confidence intervals guiding elimination.
  • 3.1.2 Beat the Mean: BTM has a high-probability finite-horizon regret bound of order O(...), unlike IF’s expected-regret guarantee.
  • 3.1.2 Beat the Mean: BTM is an (ε, δ)-PAC preference-based learner with an author-reported sample complexity of O(...).

3.1.7 Relative Minimum Empirical Divergence

Relative Minimum Empirical Divergence (RMED) adapts minimum empirical divergence ideas to dueling bandits with a Condorcet winner, using empirical divergences to identify plausible best arms and choose comparisons. The supplied discussion also contrasts these guarantees with Winner Stays results under different regret notions.

  • 3.1.7 Relative Minimum Empirical Divergence: RMED algorithms use empirical divergences to identify an empirical best arm and maintain a set of potentially good arms for comparison.After exploration, variants compare a selected potentially good arm with the empirical best arm or a variant-specific second arm.
  • 3.1.7 Relative Minimum Empirical Divergence: The survey reports an asymptotic lower bound for consistent dueling-bandit algorithms and identifies a constant-factor gap between RMED1’s upper bound and that lower bound.
  • 3.1.7 Relative Minimum Empirical Divergence: RMED2 is designed to match the asymptotic lower-bound constant factor, while RMED2FH provides a simpler fixed-horizon variant because RMED2’s analysis is cumbersome.
  • 3.1.8 Winner Stays: Winner Stays is analyzed separately for weak and strong regret, with WS-W attaining constant-in-time expected cumulative weak regret when there are no ties.
  • 3.1.8 Winner Stays: The WS-W guarantee is optimal in time-horizon dependence but not in dependence on calibrated preference probabilities.

3.1.9 Beat the Winner

This section surveys dueling-bandit algorithms for best-arm and ranking tasks, emphasizing tournament, challenge, and sequential-elimination strategies under progressively weaker preference assumptions.

  • Knockout Tournaments: Knockout uses random pairings in successive elimination rounds and improves BTM’s sample complexity, matching the lower bound when γ = 1.The result assumes a total order, γ-relaxed stochastic transitivity, and stochastic triangle inequality.
  • Sequential Elimination: Seq-Eliminate has order-optimal high-confidence sample complexity when δ ≤ 1/K, whereas its modified version addresses the regime δ > 1/K.The modification first finds a good champion and then restricts further comparisons to a smaller candidate subset.
  • Complexity Comparison: Top-k ranking has a logarithmic-factor higher leading sample-complexity term than finding a nearly best arm, reflecting sorting versus maximum-finding complexity.The comparison concerns the PAC setting under the corresponding preference assumptions.
  • Lower Bounds: Lower bounds scale quadratically with K for best-ranking identification under strong stochastic transitivity and also under moderate stochastic transitivity with the stochastic triangle inequality.The latter condition is reported to facilitate the learning problem despite the quadratic lower bound.

3.1.14 Top-k identification via Quick Select

This section presents QuickSelect-inspired methods for identifying the top-k arms and contrasts their optimal PAC complexity with related ranking and structured-query approaches.

  • Epsilon-Quick-Select: Epsilon-Quick-Select randomly chooses a pivot and partitions arms into surely preferred, unsure, and surely non-preferred subsets before recursively selecting the required arms.Uncertain arms can be sampled to complete a k-sized candidate set when the surely preferred subset is too small.
  • Tournament-k-Selection: T-k-S is an (ε, δ)-PAC algorithm for top-k identification whose sample complexity is optimal under a total order, strong stochastic transitivity, and stochastic triangle inequality.The method partitions arms into subsets of size at most 2k and applies Epsilon-Quick-Select iteratively until k arms remain.
  • Approx-Prob: Approx-Prob exploits strong stochastic transitivity and the stochastic triangle inequality to reduce pairwise comparisons when estimating all preference probabilities from a pre-sorted list.Its estimates use grid rounding and equality constraints among triplets of arms.
  • Structured Query Selection: Structured query selection relates ranking under embedded noisy preferences to determining labels of points via active linear separators.Robust Query Selection repeats ambiguous pairwise duels and uses the majority winner under noisy outcomes.

3.1.17 Verification-based Solution

This section describes verification-based and low-round algorithms that identify best or kth-best arms by combining candidate generation, confidence-based verification, and structured partitioning.

  • Verification-Based Solution: Karnin’s verification framework alternates FindBestArm and VerifyBestArm subroutines, using verification to confirm or reject proposed optimal arms with high confidence.The framework applies across structured bandit settings, including classical, linear, and combinatorial bandits.
  • Verification-Based Solution: Under the Condorcet assumption, the proposed method improves RMED-derived sample complexity by a multiplicative factor Kε when δ is sufficiently large.The procedure maintains confidence estimates for active pairs and verifies each alleged non-Condorcet winner against its toughest competitor.
  • Parallel Selection and Partition: Parallel selection and partition algorithms solve kth-best-arm and best-k partition tasks with low round complexity and sample complexity matching the provided lower bound.The algorithms use random subsets and anchor-based filtering before combining two major procedures to recover the true partition.
  • Parallel Selection and Partition: The deterministic partition procedure repeatedly selects random anchors, compares them with the active subset, and retains arms in an interquartile range of duel wins.The probabilistic setting is obtained by repeating duels between each pair a prescribed number of times.
  • Top-k Selection: The Top algorithm extends Select from best-arm identification to top-k ranking and identification by combining subgroup winners with heap-based extraction.Its leading sample-complexity factor differs from Select’s by a logarithmic factor.

3.1.20 Sequential-Elimination-Exact-Selection

This section surveys exact and approximate sequential-elimination methods for best-arm, top-k, and ranking tasks, including tree-based insertion when preference gaps lack a known lower bound.

  • SEEBS: SEEBS repeatedly obtains a nearly best champion with T-k-S, partitions arms around it, and eliminates challengers to identify the exact best arm.The method assumes strong stochastic transitivity and the stochastic triangle inequality.
  • SEEKS: SEEKS uses two T-k-S variants per round to build a candidate pool for the top-k set and identify a nearly worst arm for subsequent elimination.The nearly worst designation is defined by rank in the underlying total order.
  • Iterative-Insertion-Ranking: IIR addresses unknown lower bounds on calibrated preference gaps through binary insertion in a preference interval tree.Each insertion traverses the tree and duels the new arm against non-artificial node arms to determine its position.
  • Iterative-Insertion-Ranking: IIR builds a preference interval tree by inserting arms through confidence-based duels, and its sample complexity is nearly optimal when strong stochastic transitivity holds.The guarantee is that the final tree represents the true ranking with probability at least 1 − δ.
  • Iterative-Insertion-Ranking: The adjacent-arm gap used by IIR differs generally from the minimum gap against all other arms, but the two coincide under strong stochastic transitivity.This distinction determines which preference gaps characterize IIR’s complexity.

3.2 Regularity Through Latent Utility Functions

Latent utility models represent qualitative comparisons through utilities and a link function, enabling preference-based learning under finite or infinite arm spaces. The surveyed methods use these structures for optimization, regret minimization, elimination, and ranking tasks.

  • Utility-based models: A latent utility u maps each arm to a real value, while a link function σ converts utility differences into pairwise comparison probabilities.The link function is strictly monotone and satisfies σ(0)=1/2; logistic and linear links are common examples.
  • Utility-based models: Injective utilities imply low noise and a total order, whereas non-injective utilities may lose the order but still satisfy strong stochastic transitivity.This makes the utility assumption stronger than regularity properties such as stochastic transitivity when utilities are injective.
  • Dueling Bandits Gradient Descent: E[RT] ≤ 2T^3/4√(10RdL) for a d-dimensional ball of radius R, with L the product of the link and utility Lipschitz constants.The bound is reported for an appropriate choice of δ and γ.
  • Dueling Bandits Temporary Elimination Algorithm: DBTEA maintains arms with non-positive lower confidence bounds, pairs active arms in randomized phases, and uses an anytime concentration inequality.Its expected regret is bounded by O(K)+O(Σ Δ̃_i), and experiments find it superior in some large-arm, moderate-horizon instances.
  • Round-efficient dueling bandits: Round-efficient elimination returns the highest-utility arm with probability at least 1−δ while targeting low comparison complexity.The surveyed result reports a round-complexity bound, though the supplied passage does not expose its full expression.

3.3 Regularity Through Statistical Models

Statistical ranking models provide structured assumptions for learning optimal arms or full rankings from pairwise-comparison marginals. The survey covers Mallows and Plackett–Luce models, along with algorithms for PAC identification and ranking.

  • Statistical ranking models: Preference-based ranking can be modeled by a distribution over permutations, with pairwise probabilities obtained as marginals of that distribution.Learning then amounts to inferring the ranking distribution from pairwise-comparison samples.
  • Statistical ranking models: Mallows and Plackett–Luce impose stronger structure than utility-based dueling bandits because their pairwise probabilities admit utility-link representations.Both models are reviewed as statistical approaches to optimal-arm and ranking identification.
  • Mallows model: In the Mallows model, the center ranking is the mode and defines a total order whose pairwise probabilities can be computed from the spread and ranking parameters.The model also yields a relatively wide margin around 1/2 and structured differences among nearby ranks.
  • Mallows model: MallowsMPI identifies the most preferred arm with high probability, while MallowsMerge finds the most probable ranking with sample complexity differing by a logarithmic factor.The latter ranking is the center ranking of the Mallows model.
  • Mallows model: Estimating the full Mallows distribution under small KL divergence can require extremely high sample complexity, and a polynomial algorithm was left open.The difficulty remains even for small numbers of arms.
  • Plackett–Luce model: Under Plackett–Luce, rankings are generated stagewise with selection probabilities proportional to arm weights, so the modal ranking sorts weights decreasingly.The model’s pairwise probabilities coincide with the Bradley–Terry form after setting utilities to log(θ_i).
  • Plackett–Luce model: PLPAC targets an ε-optimal arm, while PLPAC-AMPR targets an ε-optimal ranking within the (ε,δ)-PAC framework.The survey reports separate sample-complexity bounds for the two objectives.

4. Learning from Non-coherent Pairwise Comparisons

For non-coherent pairwise comparisons, the survey organizes learning around alternative target concepts and algorithms for regret minimization, ranking, and PAC identification. These methods use confidence bounds, tournament solutions, and task-dependent complexity measures to handle preference relations that may not induce consistent total orders.

  • 4.1 Alternative Target Concepts: Alternative target concepts can disagree: Borda and random-walk rankings may reverse a total order, whereas Copeland coincides with it under the stated coherence condition.Under strong stochastic transitivity and low noise, the survey gives sufficient conditions for Borda and random-walk rankings to match the total order.
  • 4.1 Alternative Target Concepts: For arm selection, Borda and random-walk winners may differ from a Condorcet winner, while both coincide with it under low noise; the von Neumann winner also coincides when a Condorcet winner exists.Without a Condorcet winner, the von Neumann winner can generally differ from Copeland, Borda, and random-walk winners.
  • 4.2.1 Copeland Confidence Bound: When a Condorcet winner exists, Copeland regret guarantees transfer to cumulative regret up to a multiplicative constant, making Copeland algorithms applicable to that task.The survey notes that Copeland is a more general problem formulation than the corresponding Condorcet-winner setting.
  • 4.2.1 Copeland Confidence Bound: Copeland-based methods target non-coherent preferences, with CCB using optimistic and pessimistic confidence estimates to identify winners, eliminate arms, and select informative opponents.SCB extends the approach for larger arm sets through an explore-then-exploit design based on KL-UCB ideas.
  • 4.2.5 General Tournament Solutions: General tournament-solution algorithms use upper confidence bounds and solution-specific selection rules, yielding regret bounds governed by a tournament-specific complexity term.The worst-case bounds are described as comparable to those for RUCB under a Condorcet-winner assumption.
  • 4.2.6 PAC Rank Elicitation: PAC rank elicitation analyzes γ-sensitive Copeland and γ-insensitive sum-of-expectations rankings, but sample complexity for the NDP distance remains open because small preference changes can strongly alter rankings.The γ parameter controls relation strictness and therefore the difficulty of rank elicitation.

5. Further Extensions

The survey extends preference-based bandits to adversarial, contextual, partially ordered, graphical, and partial-monitoring settings, as well as specialized matching and structured problems.

  • Adversarial Utility-Based Dueling Bandits: O(√(KT ln K)) regret bounds are obtained for adversarial utility-based dueling bandits, matching the order of EXP3 for adversarial MABs.REX3 achieves this order, while SPARRING reductions preserve the corresponding EXP3 bound.
  • Contextual Dueling Bandits: Contextual dueling algorithms address online learning and approximate von Neumann-winner computation, but dependence on |Π| creates computational issues when the policy space is large.The reported method requires time and space linear in |Π|.
  • Dueling Bandits on Posets: Poset dueling bandits target Pareto-set identification when arms may be incomparable, but exact recovery can be impossible without additional information.Decoys enable recovery of the exact Pareto set with extra decoy-related regret and a stated sample-complexity bound.
  • Partial Monitoring Games: Partial-monitoring analyses classify dueling bandits as easy problems because adjacent-action loss differences are locally observable, yielding sublinear regret guarantees.The survey also reports O(KT) bounds for a related algorithmic result and logarithmic regret for Thompson Condorcet sampling under a Condorcet winner.
  • Other Extensions: Specialized extensions provide PAC guarantees for Borda matching winners and near-optimal sample complexity on a subclass of learning scenarios.The reported results include correctness probability at least 1 − δ and almost-optimal sample complexity for the specified subclass.

6. Multi-Dueling Bandits

Multi-dueling bandits generalize preference-based bandits by allowing comparisons among more than two arms, with methods covering regret minimization and PAC learning. The survey finds that richer feedback can improve guarantees in some settings, but most-preferred-arm feedback does not always improve theoretical performance.

  • 6.1 Learning Protocol: The action spaces of generalized multi-dueling settings are substantially more complex than the basic dueling-bandit action space.The survey notes that basic dueling corresponds to A+≤2, while larger action spaces include more subsets and possibly singleton commitments.
  • 6.3.1 Best Arm and Ranking of Arms: Generalized winner notions may fail to exist or be unique, and generalized Borda and Condorcet winners can differ even when a Condorcet winner exists.These drawbacks preserve important ambiguities in defining the target arm for multi-dueling learning.
  • 6.5 Multi-dueling algorithms: More informative feedback from the l′ most preferred arms improves theoretical guarantees as l′ increases, unlike feedback reporting only the most preferred arm.The survey attributes this improvement to the greater information content of top-l′ feedback.
  • 6.5.1 Multileaving: Empirical information-retrieval studies report that several approaches outperform DBGD on NDCG, although corresponding theoretical analyses are unavailable.MDB is also reported to perform well empirically, but without theoretical guarantees.
  • 6.5 Multi-dueling algorithms: For some pairwise-subset choice models, comparing more than two arms provides no advantage when feedback is only the most preferred arm.The same limitation appears in sample-complexity results, where multi-dueling can retain the dueling-bandit lower bound.
  • 6.5 Multi-dueling algorithms: Multi-dueling algorithms can match or nearly match lower bounds for regret minimization and PAC identification under several preference models.The cited results include order-optimal or nearly optimal guarantees for WBA, PAC-Wrapper, and related procedures.

7. Applications

Dueling-bandit methods have been applied to preference-driven tasks including human–robot interaction, gesture generation, information retrieval, clinical stimulation, optimization, translation, and peer assessment.

  • Information retrieval: Applications extend to online learning-to-rank, where DBGD with probabilistic interleaving uses historical interaction data and discounted cumulative reward for evaluation.
  • Clinical applications: CorrDuel exploits correlations among spinal-stimulation configurations and performs as well as specialized physicians in a live clinical trial.In synthetic experiments, it also outperforms algorithms that do not exploit correlation information.
  • Human judgments: Dueling bandits model human judgments for learning exercise preferences, gesture naturalness, and translation quality when absolute numerical assessments are difficult or noisy.The applications use pairwise preference feedback to guide learning.
  • Search: Preference-Based Monte Carlo Tree Search replaces single-successor observations with paired roll-outs, producing binary-tree feedback and potentially exponentially many explored paths.A tree policy uses RUCB to guide successor choice.
  • Optimization and structured tasks: Preference-based methods also support algorithm-configuration recommendation, safe Bayesian optimization, and peer-assignment ranking under contextual, safety, or partial-ranking constraints.These settings include CPPL, StageOpt, and sequential noisy ranking aggregation formulations.

8. Summary and Perspectives

The survey organizes the developing PB-MAB field while identifying unresolved theoretical, methodological, and practical questions. It emphasizes that assumptions about preference relations shape difficulty, yet coherent comparisons and validated real-world use remain incomplete.

  • State of the field: PB-MAB remains less mature than standard bandits because preference cycles, ambiguous regret definitions, and differing assumptions complicate the field.
  • Open theoretical issues: Different theoretical results are difficult to compare because the literature lacks agreement on assumptions, targets, and performance measures.A complete and coherent theoretical framework has yet to be developed.
  • Open theoretical issues: Lower bounds remain unknown for some settings, including general tournament solutions and weak regret minimization, making algorithmic optimality difficult to assess.
  • Preference assumptions: More restrictive assumptions on the preference relation make learning easier; strong stochastic transitivity and the stochastic triangle inequality can yield sub-quadratic PAC sample complexity.The survey notes that analogous substitutes are not readily available for multi-dueling bandits.
  • Methodological gaps: The field needs statistical tests for its modeling assumptions and clearer evidence about whether adaptive sampling improves preference-based online learning.Existing assumption-testing work is described as limited, including restriction to weak stochastic transitivity in offline settings.
  • Practical perspectives: Practical progress is constrained by the lack of a repository collecting established methods and by limited testing in real applications such as crowdsourcing platforms.
Loading 1807.11398v2…