Source-linked AI summary
Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
Masrour Zoghi, Shimon Whiteson, Remi Munos, Maarten de Rijke
TL;DR
The K-armed dueling bandit learns from pairwise preferences rather than individual-arm rewards. RUCB uses optimistic pairwise estimates to choose a potential champion and runs UCB relative to it. The paper reports O(log t) regret bounds for all time steps and strong real-data performance against existing methods.
Problem
Method
RUCB uses optimistic estimates of pairwise probabilities to select a potential champion, then runs regular UCB with that champion as the benchmark.
Source: §1 · p. 2Results
Takeaways & Limitations
RUCB works without a specified exploration horizon, and its bounds hold for all time steps rather than only through a fixed T.
Source: §1 · p. 2, §7 · p. 9The theoretical comparisons are constrained by prior-method assumptions: IF and BTM require pairwise-probability conditions that can be difficult to verify and often violated in practice.
Source: §3 · p. 3
Abstract
from arXiv · showhide
This paper proposes a new method for the K-armed dueling bandit problem, a variation on the regular K-armed bandit problem that offers only relative feedback about pairs of arms. Our approach extends the Upper Confidence Bound algorithm to the relative setting by using estimates of the pairwise probabilities to select a promising arm and applying Upper Confidence Bound with the winner as a benchmark. We prove a finite-time regret bound of order O(log t). In addition, our empirical results using real data from an information retrieval application show that it greatly outperforms the state of the art.
1. Introduction
RUCB extends UCB to pairwise-preference feedback by selecting a potential champion and using it as the benchmark for regular UCB. The paper presents all-time regret guarantees and reports strong performance on real information-retrieval data.
1. Introduction
- Pairwise-preference feedback supports preference learning when judgments are naturally qualitative or real-valued feedback would be arbitrary or inefficient.Source: §1 · p. 1
- Unlike IF, BTM, and SAVAGE, RUCB needs no exploration-horizon input and outperforms them on finite-horizon accuracy and regret metrics.A suitable horizon can be difficult to guess in practice.Source: §1 · p. 1
- RUCB uses optimistic pairwise-probability estimates to select a potential champion, then runs regular UCB relative to that champion.Source: §1 · pp. 1–2
- O(log t) cumulative-regret bounds hold at every time step, unlike prior bounds tied to a specified horizon T.The paper describes these as the first explicitly non-asymptotic results for the K-armed dueling bandit problem.Source: §1 · p. 2
- RUCB greatly outperforms BTM and SAVAGE in real-data information-retrieval experiments.The experiments assess RUCB in a ranker-evaluation application.Source: §1 · pp. 1–2
- The paper claims RUCB is more broadly applicable and gives theoretical results with less restrictive assumptions than IF and BTM and better multiplicative constants than SAVAGE.Source: §1 · p. 2
2. Problem Setting
The problem compares arms through pairwise preferences and seeks a Condorcet winner, which beats every other arm head-to-head. The paper distinguishes finite-horizon evaluation from the horizonless goal of controlling cumulative regret over time.
2. Problem Setting
- Each comparison selects two arms and returns which one is preferred, with fixed pairwise probabilities recorded in preference matrix P.Source: §2 · p. 2
- A Condorcet winner beats every other arm head-to-head, unlike a Borda winner, which has the highest average win probability across opponents.The paper focuses on the Condorcet winner because users prefer it in direct comparisons; a standard bandit algorithm can target the Borda winner.Source: §2 · p. 2
- In the finite-horizon setting, the algorithm receives T in advance and is evaluated by accuracy or regret accumulated during exploration.Source: §2 · pp. 2–3
- The horizonless setting requires minimizing cumulative regret across all horizons, especially by reducing comparisons involving suboptimal arms.Source: §2 · p. 3
- Because choosing T is difficult and a poor choice can over-explore or stop before the best arm is known, RUCB works without a specified horizon or doubling trick.The paper says it can also be adapted to finite-horizon use by stopping at the horizon.Source: §2 · p. 3
3. Related Work
RUCB’s theoretical guarantees cover all time steps and apply under less restrictive assumptions than earlier methods. The section contrasts those guarantees with the finite-horizon bounds and assumptions of IF, BTM, and SAVAGE.
3. Related Work
- IF eliminates arms against a reference arm, whereas BTM eliminates arms based on estimated performance against the mean arm.Both methods require the comparison-probability conditions described above.Source: §3 · p. 3
- RUCB requires only a Condorcet winner, while IF and BTM rely on probability conditions that can be difficult to verify and often fail in practice.RUCB’s explicit bounds also do not depend on BTM’s relaxation parameter γ.Source: §3 · pp. 3–4
- RUCB substantially outperforms Condorcet SAVAGE, which samples pairs uniformly and removes a loser after a sufficiently wide win.The reported comparison is for ranker evaluation.Source: §3 · p. 4
- RUCB’s expected-regret bound is tighter on difficult small-gap problems, and its analysis gives an explicit additive constant absent from the IF, BTM, and SAVAGE analyses.The tighter bound follows from a Δ_j term in the numerator of its second summand.Source: §3 · p. 4
- RUCB’s regret bounds hold for all time steps, unlike IF, BTM, and SAVAGE bounds limited to a predetermined horizon.The prior methods bound regret accumulated in the first T steps; RUCB’s bounds do not require that horizon.Source: §3 · p. 4
4. Method
RUCB uses optimistic pairwise estimates to identify potential champions, then applies UCB with a selected champion as the benchmark. It compares the resulting pair and updates its win counts.
4. Method
- RUCB selects an arm whose upper bounds against every other arm are at least 1/2 as champion, choosing randomly among remaining potential champions when none qualifies.The algorithm’s return value is the arm with the largest count of pairwise wins.Source: §4 · p. 4
- RUCB computes pairwise upper bounds from estimated win probabilities and optimism bonuses, removing an arm when its bound against another falls below 1/2.The bonus increases with time and decreases as the number of comparisons grows.Source: §4 · pp. 4–5
- Using the champion as benchmark, RUCB selects the arm with the largest UCB estimate of beating that champion.For the champion’s self-comparison, the method sets the estimate to 1/2.Source: §4 · p. 5
- RUCB compares the champion with the selected arm and updates the corresponding win count.The algorithm can run to a finite horizon T or indefinitely when T is infinite.Source: §4 · pp. 4–5
- Champion selection is optimistic, while benchmark selection is pessimistic, discouraging uninformative self-comparisons until the champion is sufficiently certain.As estimates concentrate on the Condorcet winner, both selections increasingly choose it and regret declines.Source: §4 · p. 5
5. Theoretical Results
The section establishes finite-time high-probability and expected regret bounds for RUCB. Confidence-interval control limits how often distinct arm pairs are compared.
5. Theoretical Results
- With probability 1−δ, the time when confidence intervals include p_ij is at most C(δ).The interval grows toward p_ij when the pair is not compared, while repeated comparisons bring the estimated mean toward p_ij.Source: §5 · p. 5
- With probability 1−δ, each distinct pair’s comparisons cannot exceed both C(δ) and D_ij ln t, yielding the high-probability regret bound.The regret bound follows by accounting for the initial C(δ) steps and the comparisons bounded by D_ij ln t.Source: §5 · p. 6
- Theorem 3 derives the expected regret bound by integrating the high-probability regret bound over δ.The proof relates the regret distribution to its quantiles before carrying out the integration.Source: §5 · pp. 6–7
- Replacing UCB with KL-UCB does not improve the leading constant in the logarithmic regret term by more than a numerical factor of 2.Source: §5 · p. 7
6. Experiments
In real information-retrieval ranker evaluation, RUCB is compared with Condorcet SAVAGE and BTM. RUCB accumulates substantially less regret and reaches higher accuracy sooner than Condorcet SAVAGE, without knowing the horizon.
6. Experiments
- The task models ranker evaluation as dueling among 64 LETOR NP2004 feature rankers, using probabilistic interleave and simulated user clicks for comparisons.Source: §6 · p. 7
- The full preference matrix was estimated using 4,000 interleaved comparisons for each pair of feature rankers before simulating comparisons.Source: §6 · p. 7
- Across randomly chosen subsets with K=16, 32, or 64, each algorithm had 100 runs of up to 4.5 million iterations; RUCB used α=0.51.Source: §6 · p. 8
- BTM and Condorcet SAVAGE were run at horizons from 1,000 to 4.5 million, while RUCB ran horizonlessly for 4.5 million iterations.Source: §6 · p. 8
- RUCB asymptotically accumulates 5 to 10 times less regret than Condorcet SAVAGE and reaches higher accuracy in roughly 20% of its time, without knowing horizon T.Source: §6 · p. 8, Figure 4 · p. 8
7. Conclusions
RUCB extends UCB to pairwise-preference feedback by choosing a potential champion and using it as the comparison benchmark. The paper reports O(log t) regret bounds and strong empirical performance, and identifies continuous dueling bandits and sampling-based extensions as future work.
7. Conclusions
- RUCB uses optimistic pairwise-probability estimates to choose a potential champion, then applies UCB relative to that champion.Source: §7 · p. 8
- RUCB has finite-time high-probability and expected regret bounds of order O(log t), and its bounds hold at all time steps rather than only to a preset horizon.The bounds also rely on less restrictive assumptions or have better multiplicative constants than existing methods.Source: §7 · pp. 8–9
- In an information retrieval application, RUCB greatly outperformed state-of-the-art methods.Source: §7 · p. 9
- Future work will investigate continuous dueling bandits without a convexity assumption and sampling-based extensions of RUCB.The paper notes that both directions involve challenges from the two-stage nature of RUCB as well as those present in regular bandits.Source: §7 · p. 9
8. Appendix
The appendix examines the Condorcet assumption in feature-ranker subsets and proves a confidence-interval lemma used in the regret analysis. It reports that the Condorcet assumption holds more often than total ordering in the tested setting.
8.1. The Condorcet Assumption
- The Condorcet assumption is less restrictive than the total-ordering assumption required by IF and BTM, and every tested dueling-bandit problem required γ > 1.BTM requires γ as an input; underestimation can mislead it toward the Borda winner, while overestimation increases exploration and regret.Source: §8.1 · p. 11
- The Condorcet assumption held with probability greater than 0.97 for every tested subset size, while the probability of total ordering decreased rapidly as subset size grew.The authors attribute the decline to cycles among rankers; a cycle need not violate the Condorcet assumption if it excludes the Condorcet winner.Source: §8.1 · p. 11, Figure 5 · p. 11
8.2. Proof of Lemma 1
- Lemma 1 bounds the time until pairwise confidence intervals include p_ij: with probability 1 − δ, this time is at most C(δ).The proof uses Chernoff-Hoeffding bounds to control the probability that an interval fails to contain p_ij.Source: §8.1 · p. 12, §8.2 · pp. 12–13