From Dueling Bandits to Episodic MDPs: Learning with Adversarial Preference Feedback

Taira Tsuchiya; Shinji Ito; Haipeng Luo

cs.LGJul 15, 2025

From Dueling Bandits to Episodic MDPs: Learning with Adversarial Preference Feedback

Authors: Taira Tsuchiya, Shinji Ito, Haipeng Luo

Organizations: The University of Tokyo and RIKEN · University of Southern California

Abstract

In dueling bandits, the learner compares two arms in each round and observes only which one is preferred. This paper asks what changes when the compared pair also affects the next state, as in a recommendation interface where the pair shown to a user affects the user's next context. We formulate this problem as a state-wise preference-based MDP, an episodic tabular MDP in which the learner selects a pair of arms at each visited state, observes only a noisy comparison between them, and moves to a next state that may depend on the pair. The preferences may change adversarially across episodes, and the loss of a pair is defined through Borda scores. We show that the minimax regret of this problem under known transitions is $\tildeΘ(\min\{HT,(H^3SK)^{1/3}T^{2/3}\})$ , where $H$ , $S$ , $K$ , and $T$ are the numbers of steps per episode, states, arms, and episodes, and that this rate is achieved by an algorithm based on online linear optimization over the set of occupancy measures. If the pair did not affect the next state, each state would be a separate dueling bandit, and the $T^{2/3}$ term of the minimax regret would be smaller by a factor of $H^{1/3}$ , demonstrating the cost of having action-dependent state transitions. We also give a policy optimization algorithm with closed-form updates, whose regret is $\tilde{O}((H^4SK^3)^{1/3}T^{2/3})$ up to lower-order terms, and we extend both algorithms to unknown transitions.

Figures & tables

Setting	Result	Regret	Algorithm
Lower bound	Theorem 3	$\Omega\big((H^{3}SK)^{1/3}T^{2/3}\big)$	–
Known transitions	Theorem 1	$\widetilde{O}\big((H^{3}SK)^{1/3}T^{2/3}\big)$	OLO over polytope
Known transitions	Theorem 2	$\widetilde{O}\big((H^{4}SK^{3})^{1/3}T^{2/3}\big)^{\dagger}$	policy optimization
Unknown transitions	Theorem 8	$\widetilde{O}\big((H^{3}SK)^{1/3}T^{2/3}+HSK\sqrt{T}\big)^{\dagger}$	OLO over polytope
Unknown transitions	Theorem 17	$\widetilde{O}\big((H^{4}SK^{3})^{1/3}T^{2/3}+H^{2}SK\sqrt{T}\big)^{\dagger}$	policy optimization

Table 1: Regret bounds established in this paper for state-wise PbMDPs with Borda scores. The notation

\widetilde{O}

hides logarithmic factors. Each bound is of the form

\min\{HT,\cdot\}

, and the trivial term

HT

is omitted. OLO stands for online linear optimization. † Up to additive lower-order terms.

\widetilde{q}_{t}\in\argmin_{q\in\Omega_{\rho}}\left\{\left\langle q,\sum_{\tau=1}^{t-1}\widehat{\ell}_{\tau}\right\rangle-\frac{1}{\eta}\operatorname{H}(q)\right\},\hskip 9.24994pt\operatorname{H}(q)=\sum_{s,a}q(s,a)\log\left(\frac{1}{q(s,a)}\right).

(2)

Algorithm 1 Global optimization under known transitions

\pi_{t}(a\mid s)=(1-\gamma)\widetilde{\pi}_{t}(a\mid s)+\gamma/A,\hskip 18.49988ptq_{t}=q^{\pi_{t}}.

(7)

Algorithm 2 Policy optimization under known transitions

Panel of Figure 1 — Figure 1: Lower-bound instance used to prove Theorem 3 . Each chain is selected with probability $1/M$ . At $x_{c,h}$ with $h\leq L$ , a pair in $\mathcal{A}_{b}=\mathcal{A}\setminus(\mathcal{K}_{g}\times\mathcal{K}_{g})$ , where $\mathcal{K}_{g}=[\lfloor K/2\rfloor]$ , leads to the penalty state $z_{c,h+1}$ , and any other pair leads to $x_{c,h+1}$ . All other transitions do not depend on the pair.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

	Trajectory-comparison formulation	State-wise PbMDPs (this paper)
Feedback	Preference over two trajectories	Preference over two arms per state
Decision unit	One arm per state (per policy)	One ordered pair of arms per state
Transition kernel	Depends on the chosen arm	May depend on the compared pair

Appendix

Table 2: Comparison of state-wise PbMDPs with the trajectory-comparison formulation.

Panel of Figure 2 — Figure 2: Pair-independent instance with $S^{\prime}=\lfloor(S-2)/(H-1)\rfloor$ reachable states per intermediate layer. Transitions to the next intermediate layer are uniform for every pair, and all states in layer $H-1$ lead to $s_{H}$ .

Figure 3: Cumulative regret and regret per episode versus the number of episodes

T

(

H=3

S=6

, and

K=6

). Error bars show one standard error of the weighted mean over ten runs and are smaller than the markers. Open squares and dashed segments show the additional runs of policy optimization with

T\in\{10^{7},3\times 10^{7}\}

. The gray curve is the lower bound

B_{\varepsilon_{T}}(T)

Figure 4: Regret per step for

T=20{,}000

S

H

, and

K

vary. Error bars show one standard error over ten runs and are smaller than the markers.

Figure 5: Running time for

20{,}000

episodes, excluding the evaluation of the regret, for five configurations

(H,S,K)

. Points show medians. Error bars show interquartile ranges over five paired repetitions and are smaller than the markers.

Preference-Based RL

Preference-based reinforcement learning learns policies from comparisons or rankings of behaviors instead of requiring hand-designed numerical rewards.

See all 127 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
Replicable Dueling Bandits
Oct 14, 2026Rohan Deb, Aadirupa Saha, Udaya Ghai +2Dueling Bandits Multi-Armed Bandits
University of Illinois, Urbana Champaign · University of Illinois, Chicago · Amazon +1
A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback
Oct 22, 2026Haolin Liu, Chen-Yu Wei, Hanbin ZhouLinear Markov Decision Processes
University of Virginia · Hong Kong University of Science and Technology

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

Preference-Based RL

Explore similar work

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

Replicable Dueling Bandits

A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback