PaperlayerView exact revision on arXiv

Source-linked AI summary

Reducing Dueling Bandits to Cardinal Bandits

Nir Ailon, Thorsten Joachims, Zohar Karnin

arXiv:1405.3396v1cs.LG

TL;DR

The paper addresses learning preferences when online interactions provide ordinal comparisons rather than reliable cardinal values. It reduces Utility-Based Dueling Bandits to conventional Multi-Armed Bandits through generic black-box reductions, obtaining regret guarantees and strong empirical performance for some reductions.

  • Problem

    Online choices provide ordinal preferences between alternatives but not reliable cardinal valuations, motivating methods for learning from preference feedback.

  • Method

    The paper uses conventional Multi-Armed Bandit strategies as black boxes within general reductions for the Utility-Based Dueling Bandits Problem.

  • Results

    MultiSBM achieves an O(log T) regret bound under suitable logarithmic-regret and moment assumptions, with regret asymptotically identical to UCB in second-order terms for sufficiently large T.

  • Takeaways & Limitations

    The reductions provide a general approach for transferring conventional Multi-Armed Bandit results to the dueling setting, while experiments report that MultiSBM outperforms competing non-heuristic algorithms across many scenarios.

  • Takeaways & Limitations

    Doubler may require Ω(T) memory to store the history of arms from the last epoch in settings without a suitable geometric representation.

Abstract

from arXiv · show

We present algorithms for reducing the Dueling Bandits problem to the conventional (stochastic) Multi-Armed Bandits problem. The Dueling Bandits problem is an online model of learning with ordinal feedback of the form "A is preferred to B" (as opposed to cardinal feedback like "A has value 2.5"), giving it wide applicability in learning from implicit user feedback and revealed and stated preferences. In contrast to existing algorithms for the Dueling Bandits problem, our reductions -- named $\Doubler$, $\MultiSbm$ and $\DoubleSbm$ -- provide a generic schema for translating the extensive body of known results about conventional Multi-Armed Bandit algorithms to the Dueling Bandits setting. For $\Doubler$ and $\MultiSbm$ we prove regret upper bounds in both finite and infinite settings, and conjecture about the performance of $\DoubleSbm$ which empirically outperforms the other two as well as previous algorithms in our experiments. In addition, we provide the first almost optimal regret bound in terms of second order terms, such as the differences between the values of the arms.

1 Introduction

The paper studies learning from ordinal preference feedback, where users reveal which alternative they prefer but not reliable cardinal values. It introduces general reductions from Dueling Bandits to conventional Multi-Armed Bandits and establishes regret guarantees across finite and structured settings.

  • Motivation: Implicit feedback from clicks or choices usually expresses ordinal preference rather than reliable cardinal valuation.The paper frames this distinction as central to applications such as search ranking and recommendations.
  • Problem setting: UBDB presents two actions per round, rewards their average latent utility, and observes only the user’s binary choice.The utilities are unobserved, while the choice depends on both utilities through a link function.
  • Reduction approach: The paper reduces UBDB to stochastic cardinal MAB by using MAB strategies as black boxes, covering finite and infinite action spaces.The conventional MAB setting directly observes cardinal rewards, unlike UBDB.
  • Results: Doubler adds an extra O(log T) factor for polylogarithmic MAB regret, while MultiSBM achieves O(log T) regret under logarithmic-regret and moment assumptions.MultiSBM is asymptotically identical to UCB in horizon and second-order terms under the stated conditions.
  • Scope: The extended abstract’s proved results assume a linear link function, with preliminary results for other link functions deferred to an appendix.This assumption bounds the stated scope of the main results.
  • Relation to prior work: The reductions provide a general alternative to case-specific dueling algorithms and improve on prior infinite-setting regret in a more restricted setting.The paper also reports a linear rather than quadratic dependence on the number of arms relative to a partial-monitoring-based bound.

2 Definitions

This section formalizes cardinal MAB and UBDB, then introduces Singleton Bandit Machines as black-box interfaces for reductions. It also reviews classic MAB guarantees and gives the Doubler procedure for finite or structured action spaces.

  • MAB definitions: In stochastic MAB, each arm has an unknown expected utility, and the algorithm observes the sampled utility after choosing an arm.Regret compares accumulated utility with repeatedly selecting an optimal arm.
  • Black-box interface: A Singleton Bandit Machine exposes reset, advance, and feedback operations, allowing an MAB algorithm to operate as a black-box component.The reduction supplies simulated feedback values in [0, 1].
  • UBDB definitions: In UBDB, the algorithm selects an action pair, receives unobserved independent utilities, and observes only a binary comparison generated by a known link function.The linear link function is the principal case studied in the paper.
  • Utility and regret: The primary UBDB reward is average utility, U_av = (u_t + v_t)/2, rather than the utility of whichever action the user chooses.Choice-based utility is discussed separately and then excluded from subsequent analysis.
  • Classic MAB results: UCB has expected regret bounded by 2(α + 2)H ln(T) + Kα + 2α, which is O(αH ln T).Here H sums inverse gaps over suboptimal arms.
  • Doubler: Doubler repeatedly compares MAB-selected right arms with uniformly sampled arms from the previous epoch and feeds binary choices back to the SBM.Each epoch doubles the number of comparisons and replaces the candidate multiset with the arms selected by the SBM.

3 UBDB Strategy for Large or Structured X

Doubler reduces UBDB over large or structured action spaces to a black-box MAB strategy, using exponentially growing epochs. Its regret depends on the black-box guarantee, with explicit bounds for confidence-ball and UCB-based instantiations.

  • Doubler: Doubler treats UBDB play as a competition between left and right players, with the right player controlled adaptively by an MAB strategy.The left-arm distribution in each epoch is chosen to mimic the right arm's actions in the previous epoch.
  • Doubler: Doubler adds an O(log T) factor when the MAB strategy has regret c log^α T, yielding at most 2cα/(α+1) log^(α+1) T expected regret.If the MAB regret is instead f(T) = Ω(T^α), Doubler incurs O(f(T)) regret.
  • Doubler: ConfidenceBall2 or ConfidenceBall1 instantiations provide explicit regret bounds for compact convex action spaces and Δ-gap settings.The supplied corollary gives bounds involving d, T, H, α, and the gaps Δ_x.
  • Doubler: With UCB on a finite action set, Doubler has expected regret at most O(H log^2(T)), where H is defined from the arm gaps.This is obtained by setting the MAB strategy in Doubler to UCB.
  • Limitation: Doubler may require Ω(T) memory to store the previous epoch's right-arm history, although linear structure or a Δ-gap condition can reduce storage.For linearly embedded action spaces, storing an average arm suffices; under a Δ-gap condition, the required space becomes polylogarithmic in T as T grows.

4 UBDB Strategy for Unstructured X

MultiSBM targets finite, unstructured action spaces by running one MAB strategy per arm and linking successive duels. Under a robustness condition, its regret is asymptotically competitive with a single MAB strategy rather than K times larger.

  • MultiSBM: MultiSBM uses K MAB strategies in parallel, with each instance indexed by a left arm and selecting the right arm for that duel.The next round's left arm is set to the previous round's right arm.
  • Regret analysis: MultiSBM's regret is dominated by the strategy corresponding to the maximum-utility arm rather than incurring the naive K-fold single-strategy bound.The analysis assumes a robustness property controlling the tail of each strategy's regret distribution.
  • Assumptions: The required robustness is α = max(3, ln(K)/ln ln(T)), and UCB can ensure it with a suitable parameter choice.Achieving α = 3 requires a slight modification of UCB's confidence-interval parameter.
  • Results: For sufficiently large horizons satisfying ln ln T > (ln K)/3, MultiSBM's total regret is comparable to UCB's regret in the standard MAB game.This comparison follows under the stated robustness setting.
  • Regret analysis: The proof identifies a positive feedback loop: lower right-arm regret increases future play of the optimal arm, which further lowers right-arm regret.Conversely, frequent left-arm play of a fixed arm, including the optimal arm, rapidly decreases the right arm's expected regret.

5 A Heuristic Approach

Sparring is a heuristic reduction that uses two SBMs to select the left and right arms, achieving very strong empirical performance despite lacking a proven stochastic regret guarantee.

  • 5 A Heuristic Approach: Sparring uses two SBMs, one for each side, whose selected arms form each duel and whose feedback is based on the observed preference.The chosen arm's SBM receives feedback 1, while the other receives 0.
  • 5 A Heuristic Approach: The heuristic achieves extremely good performance in the experiments, but no proven bound currently explains that performance.The authors conjecture that its regret may be close to the combined regret of the two underlying SBM algorithms, possibly with a small overhead.
  • 5 A Heuristic Approach: Proving the conjecture is particularly relevant for infinite action spaces, where tournament elimination does not apply and Doubler may be suboptimal because of its extra logarithmic factor.The analysis is difficult because each SBM receives feedback influenced by the other SBM's non-stochastic choices.

6 Notes

The paper relates dueling-bandit regret to conventional MAB regret in both stochastic and adversarial settings, including matching lower-bound implications and adversarial reductions.

  • Lower Bound: A lower-bound reduction from UBDB to MAB shows that classic MAB lower bounds also apply to the dueling-bandit problem, up to logarithmic terms.The reverse reduction simulates an SBM using a UBDB solver with regret at most twice the dueling-bandit regret.
  • Sparring: Sparring is described as a reduction to two SBMs, with separate left and right strategies receiving feedback from each duel.The algorithm initializes two SBMs, advances both to select a pair, observes the binary choice, and feeds each side the corresponding outcome.
  • Adversarial Setting: In the adversarial setting, the utilities may change arbitrarily each round, while a lower bound matching the MAB problem and Sparring's corresponding SBM regret bounds remain available.These adversarial results are stated without a full development because of space constraints.

7 Experiments

The experiments compare the proposed reductions with established baselines across many utility, link-function, and preference-matrix settings. Sparring performs best throughout, while MultiSBM is generally the strongest non-heuristic method.

  • Experimental design: The study compares IF, BTMB, MultiSBM, Doubler, and Sparring across scenarios including nonlinear link functions and the broader setting analyzed by Yue and Joachims.The experiments therefore include cases beyond those covered by the paper's theoretical bounds.
  • Experimental design: The main experiments use 6 arms, 5 expected-value functions, and 3 link functions, with all 5 algorithms run for each of 15 combinations.The time horizon extends to 32000, and the expected utility vector is randomly permuted to avoid initialization bias.
  • Experimental design: The YJ evaluation uses an unknown fixed pairwise-choice matrix satisfying mild constraints, allowing the proposed algorithms to be compared with BTMB without modification.This setting is more general than the latent-utility/link-function model used elsewhere in the experiments.
  • Experiment Results and Analysis: Sparring is superior to all other algorithms in every tested setting, while IF and MultiSBM are the top two among the remaining methods and MultiSBM wins in many scenarios.Figure 1 reports expected regret against log2 time, averaged over 400 executions with one-standard-deviation confidence bars.

8 Future work

The paper identifies scope limits around pairwise choices and asymmetric reductions, and highlights proving Sparring's conjectured regret behavior as future work.

  • Scope: The analysis considers choices from sets of size 2 and primarily studies the linear choice function, with extensions to other link functions deferred to Appendix D.Larger choice sets are not analyzed in the main treatment.
  • Scope: Doubler and MultiSBM treat the left and right positions asymmetrically, preventing analysis with distinct expected valuation functions for those positions.The limitation matters in settings where lower-ranked displayed items may receive lower perceived valuations.
  • Experiments: Figure 1 plots expected regret against log2 time for 16 scenarios and 5 algorithms, averaging 400 runs per scenario with one-standard-deviation confidence bars.These plots summarize the empirical comparisons used to motivate further analysis of Sparring.
  • Future work: Proving or refuting Sparring's regret conjecture remains an open problem because the two SBMs create a positive feedback loop as each side's play changes the other's environment.More frequent optimal play by one side makes the other side's environment closer to a standard MAB setting.

A Robustness of the UCB algorithm

The proof establishes robustness for UCB by combining Chernoff concentration with a case analysis of when a suboptimal arm can be selected. It then bounds suboptimal-arm pulls and expected regret.

  • Chernoff’s inequality supplies tail bounds for empirical estimates of rewards supported in [0, 1].
  • The analysis assumes K arms, designates arm 1 as optimal, and defines Δ_i as the reward gap between arm 1 and arm i.
  • A suboptimal arm can be selected only if one of several confidence-related events occurs, including an overestimate of its empirical mean.
  • The probability that the relevant events occur is bounded by 2t^(1−β), with the analogous bound applying to the other event.
  • The resulting high-probability pull bounds are converted into an expected-regret bound by summing the contributions of suboptimal-arm selections.

B Proof of Theorem 3.1

The proof analyzes one phase of the reduction by viewing its internal SBM as a standard binary-reward MAB. Phase-wise regret is then bounded by the MAB policy’s regret function and aggregated across phases.

  • Within phase i, the phase length is T_i = 2^i and the left bandit is sampled from a fixed distribution.
  • The SBM plays a standard MAB over X with binary rewards generated by the dueling process.
  • Because the highest-reward arm is x*, the SBM’s traditional MAB regret during phase i is at most B(T_i) = B(2^i).
  • The right arm contributes at most B(2^i) expected regret in phase i, while the left-arm contribution is handled using its previous-phase sampling distribution.
  • Aggregating the phase contributions yields the expression 1/2 + 3B(2) + 3B(4) + ··· + 3B(2^k) + B(Z), from which the theorem follows.

C Proof of Theorem 4.2

The proof bounds MultiSBM regret by decomposing it across internal machines and arm pairs. Its key step is that suboptimal machines are advanced only logarithmically often, after which robustness bounds their internal regret.

  • MultiSBM advances exactly one SBM per algorithm step, so each machine’s internal counter can lag behind the algorithm’s iteration counter.
  • When S_x is advanced, it observes binary rewards whose expected reward for arm y is (μ(y) − μ(x) + 1)/2, giving suboptimality Δ_y/2.
  • The regret contribution R_xy(T′) equals the number of x-versus-y interactions up to internal time T′ multiplied by Δ_y/2.
  • The total regret can be bounded by summing E[R_xy(ρ_x(T))] over nonoptimal x and all y.
  • For each nonoptimal x, the analysis exploits that ρ_x(T) is typically of order ln T rather than using the trivial upper bound T.
  • With α = max{3, 2 + (ln K)/ln ln T}, the derived expression converges to O(R_8α), and the total expected regret is bounded by the sum of these pairwise terms.

D Extension to more General Models

The extension replaces utility differences with general duel-probability gaps satisfying a relaxed extended stochastic triangle inequality. Under this condition, MultiSBM retains an asymptotic regret guarantee whose logarithmic term is independent of γ for large T.

  • The generalized setting allows duel outcomes to be determined by pairwise parameters Δ(x, y), rather than only by deterministic utility differences.
  • The model assumes relaxed stochastic transitivity and a relaxed stochastic triangle inequality for ordered triples x* ≻ x ≻ y.
  • MultiSBM’s analysis extends to arbitrary Δ under the relaxed extended stochastic triangle inequality with parameter γ.
  • The condition includes utility-ratio gaps Δ(x, y) = μ(x)/(μ(x) + μ(y)) when all utilities lie in [1/γ, 1].
  • Theorem D.1 gives an asymptotic expected-regret expression for MultiSBM under the generalized condition, assuming an α-robust MAB policy with α = max(3, ln(K)/ln ln(T)).
  • For large T, γ does not enter the ln(T) summand, so the regret is unaffected by γ in that asymptotic term.
Loading 1405.3396v1…