winner-only group feedback hides the pairwise comparisons an ordinary dueling algorithm expects. stable preferences can also stop being stable. in our paper, duplication handles the first problem; monitoring handles the second.

the problem

we study multi-dueling bandits: in each round, the learner chooses several arms and sees only the winner. think of comparing search rankers: several produce results, one is preferred, and every other pairwise comparison stays hidden.

Winner-only feedback in one multi-dueling round Four arms A, B, C, and D are selected. C is returned as the winner, while all other relations remain unobserved. learner plays Aₜ A B C D winner-only feedback learner sees Aₜ(Iₜ) = C everything else is hidden
four candidates go in; one winner comes back.

with stable preferences, the learner can settle on a strong option. if those preferences change adversarially, that early confidence becomes costly. the learner does not know which regime it is in. the best-of-both-worlds objective is to use stability when it exists without depending on it.

from a group comparison back to a duel

for Condorcet, duplication lets an ordinary dueling algorithm use the multi-way interface. if the algorithm asks to compare \(x\) and \(y\), while the interface expects four items, we submit \(\{x,x,y,y\}\). we report “\(x\) won” whenever either copy of \(x\) is selected.

this duplication weakens the preference signal, but does not reverse it. a true \(70\)-\(30\) preference becomes roughly \(63\)-\(37\). with a group of \(m\) items, every margin is multiplied by the same positive factor:

\[ \widetilde P_t(x,y)-\tfrac12 =\beta_m\!\left(P_t(x,y)-\tfrac12\right) \]

the factor \(\beta_m\) lies between \(1/2\) and \(1\), so every head-to-head winner is preserved. that is enough to place a standard dueling algorithm inside the multi-way interface. we call the resulting wrapper MetaDueling.

Condorcet and Borda behave differently

this trick is enough for Condorcet: a Condorcet winner beats every other option directly, so the direction of each pairwise comparison is what matters. a Borda winner has the best average performance against all opponents. that score depends on information spread across the entire preference matrix, which duplication alone does not recover.

learn quickly, but keep checking

for Borda, SA-MiDEX first samples broadly enough to build a baseline, then eliminates arms that are clearly worse. a monitoring process keeps checking whether the observations still agree with that baseline.

The two modes of SA-MiDEX SA-MiDEX builds a baseline, alternates elimination with monitoring in stochastic mode, and switches permanently to an adversarial strategy if drift is detected. stochastic mode build a baseline sample every pair successive elimination remove weak arms background monitoring does the baseline still fit? no detectable drift drift detected adversarial mode MiDEX adversarial mode EXP3 + importance weighting
exploit stability while continuously testing whether it still exists.

as long as the observations agree with the baseline, SA-MiDEX gets the efficiency of the stochastic setting. if the monitor finds sustained drift, it switches to MiDEX, which keeps exploring and can handle adversarially changing preferences.

random noise is the annoying part: it can look like drift for a while, so the switching threshold has to be conservative. a persistent change eventually grows beyond ordinary fluctuation, and that is when the algorithm gives up the stochastic assumption.

what each piece solves

duplication changes the feedback interface without reversing the preferred winner. monitoring lets the algorithm use a stable baseline without trusting it indefinitely.

the poster below puts the setup, both algorithms, and the guarantees in one place. thanks to Pratik for somehow fitting the whole result onto one page.

our poster for RLC 2026
RLC 2026 poster for Best-of-Both-Worlds Multi-Dueling Bandits, summarizing MetaDueling and SA-MiDEX