Replicable Dueling Bandits

Rohan Deb; Aadirupa Saha; Udaya Ghai; Karan Singh; Arindam Banerjee

cs.LGOct 14, 2026

Replicable Dueling Bandits

Authors: Rohan Deb, Aadirupa Saha, Udaya Ghai, Karan Singh, Arindam Banerjee

Organizations: University of Illinois, Urbana Champaign · University of Illinois, Chicago · Amazon · Carnegie Melon University

Abstract

Dueling bandits choose each comparison based on earlier noisy outcomes, so two runs on the same preferences can compare different pairs. We study replicable dueling bandits, where two executions with shared internal randomness and independent comparison outcomes must select the same ordered pair in every round with probability at least $1-ρ$ . Building on Beat-the-Mean, whose scores change as arms are eliminated and need not rank the best arm highest, we design the first such algorithms with sublinear regret. Under relaxed stochastic transitivity with parameter $γ\ge 1$ and the stochastic triangle inequality, we design an algorithm that achieves expected regret $\widetilde{O}(γ^8 K^4 H_{\mathrm{p}}/ρ^2)$ , where $H_{\mathrm{p}}=\sum_{i=2}^{K}(P_{1i}-1/2)^{-1}$ . Under strong stochastic transitivity, we design an algorithm based on simultaneous elimination that improves the dependence on $K$ and achieves $\widetilde{O}(K^2 H_{\mathrm{p}}/ρ^2)$ regret. For linear dueling bandits, we design an algorithm that achieves regret $\widetilde{O}(d^3\sqrt{T}/(c_μρ))$ . Experiments on synthetic and language-model preferences show replicability, with sublinear regret.

Figures & tables

Work	Setting	Approach	Regret
Esfandiari et al. [2023a]	$K$ -armed rewards	Batched elimination	$\displaystyle\mathcal{O}\!\left(\frac{K^{2}H_{\mathrm{r}}\log T}{\rho^{2}}\right)$
Komiyama et al. [2026]	$K$ -armed rewards	Batched elimination	$\displaystyle\widetilde{\mathcal{O}}\!\left(H_{\mathrm{r}}\Big(\log T+\frac{K^{2}}{\rho^{2}}\Big)\right)$
Deb et al. [2026]	$K$ -armed rewards	Batched optimism	$\displaystyle\widetilde{\mathcal{O}}\!\left(\frac{K^{2}H_{\mathrm{r}}\log T}{\rho^{2}}\right)$
Ours	$K$ -armed dueling, $\gamma\geq 1$	Single-arm elimination	$\displaystyle\widetilde{\mathcal{O}}\!\left(\frac{\gamma^{8}K^{4}H_{\mathrm{p}}}{\rho^{2}}\right)$
Ours	$K$ -armed dueling, $\gamma=1$	Simultaneous elimination	$\displaystyle\widetilde{\mathcal{O}}\!\left(\frac{K^{2}H_{\mathrm{p}}}{\rho^{2}}\right)$
Deb et al. [2026]	Linear rewards	Batched optimism	$\displaystyle\widetilde{\mathcal{O}}\!\left(\frac{d^{3}}{\rho}\sqrt{T}\right)$

Table 1: Representative regret guarantees for

\rho

-replicable stochastic bandits. For reward bandits,

H_{\mathrm{r}}=\sum_{i:\mu_{i}<\mu_{\star}}(\mu_{\star}-\mu_{i})^{-1}

; for finite dueling bandits,

H_{\mathrm{p}}=\sum_{i=2}^{K}(P_{1i}-1/2)^{-1}

. Finite dueling rows assume a strict preference order and the stochastic triangle inequality. Bounds are in expectation; the linear dueling row uses utility regret.

\widetilde{\mathcal{O}}

suppresses polylogarithmic factors, and

c_{\mu}

is a positive lower bound on the link derivative.

Figure 1: Left: cumulative regret at

\rho=0.2

over the first

6\times 10^{6}

rounds; the curves stay flat up to

T

. Middle: fraction

F(t)

of paired executions with identical trajectories up to round

t

, with the requirement

1-\rho

dashed. Right: final regret against

\rho

. Bands and bars are

95\%

intervals across

30

test instances.

Figure 2: Left: cumulative regret at

\rho=0.25

over

T=3\times 10^{4}

rounds. Middle: fraction

F(t)

of paired executions with identical trajectories up to round

t

, with the requirement

1-\rho

dashed. Right: final regret at

T=3\times 10^{5}

against

\rho

; labels give

F(T)

where it is below

1-\rho

. Bands are

95\%

intervals across paired runs.

Dueling Bandits

See all 14 papers

Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives
Mar 19, 2026S Akash, Pratik Gajane, Jawar SinghDueling Bandits Multi-Armed Bandits
Indian Institute of Technology Patna, India · University of Orléans, France
Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare
May 3, 2026Maheed H. Ahmed, Mahsa GhasemiPairwise Preference Learning Multi-Armed Bandits
Electrical and Computer Engineering Purdue University
Replicability is Asymptotically Free in Multi-armed Bandits
Feb 12, 2024Junpei Komiyama, Shinji Ito, Yuichi Yoshida +1Multi-Armed Bandits ML Reproducibility
New York University · Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · RIKEN AIP +2

Mar 19, 2026J/K move · Enter open · S save

Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives

S Akash, Pratik Gajane, Jawar Singh

Indian Institute of Technology Patna, India · University of Orléans, France

Dueling Bandits Multi-Armed Bandits Adversarial Bandits Pairwise Preference Learning

Open paper AskPDF arXiv

Multi-dueling bandits, where a learner selects

m \geq 2

arms per round and observes only the winner, arise naturally in many applications including ranking and recommendation systems, yet a fundamental question has remained open: can a single algorithm perform optimally in both stochastic and adversarial environments, without knowing which regime it faces? We answer this affirmatively, providing the first best-of-both-worlds algorithms for multi-dueling bandits under both Condorcet and Borda objectives. For the Condorcet setting, we propose

\texttt{MetaDueling}

, a black-box reduction that converts any dueling bandit algorithm into a multi-dueling bandit algorithm by transforming multi-way winner feedback into an unbiased pairwise signal. Instantiating our reduction with

\texttt{Versatile-DB}

yields the first best-of-both-worlds algorithm for multi-dueling bandits: it achieves

O(\sqrt{KT})

pseudo-regret against adversarial preferences and the instance-optimal

O\left(\sum_{i \neq a^\star} \frac{\log T}{Δ_i}\right)

pseudo-regret under stochastic preferences, both simultaneously and without prior knowledge of the regime. For the Borda setting, we propose

\texttt{SA-MiDEX}

, a stochastic-and-adversarial algorithm that achieves

O\left(K^2 \log KT + K \log^2 T + \sum_{i: Δ_i^{\mathrm{B}} > 0} \frac{K\log KT}{(Δ_i^{\mathrm{B}})^2}\right)

regret in stochastic environments and

O\left(K \sqrt{T \log KT} + K^{1/3} T^{2/3} (\log K)^{1/3}\right)

regret against adversaries, again without prior knowledge of the regime. We complement our upper bounds with matching lower bounds for the Condorcet setting. For the Borda setting, our upper bounds are near-optimal with respect to the lower bounds (within a factor of

K

) and match the best-known results in the literature.

Abstract

Dueling Bandits

Explore similar work

Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives

Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare

Replicability is Asymptotically Free in Multi-armed Bandits