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 126 papers

Mar 19, 2026

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

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.

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

Ask PDF

Oct 14, 2026

Replicable Dueling Bandits

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.

Rohan Deb, Aadirupa Saha, Udaya Ghai +2

University of Illinois, Urbana Champaign · University of Illinois, Chicago · Amazon +1

Dueling Bandits Multi-Armed Bandits Pairwise Preference Learning

Ask PDF

Oct 22, 2026

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

We study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback. The state-of-the-art result for this setting (Liu et al., 2024) either achieves

\sqrt{K}

regret with a computationally inefficient algorithm or achieves suboptimal

K^{3/4}

regret, where

K

is the number of episodes. Our work gives the first

\sqrt{K}

regret with a polynomial-time algorithm. Our method reduces adversarial linear MDPs to adversarial linear bandits whose action set consists of policies' expected feature vectors. The central challenge is that this action set is unknown and can be estimated only through exploration. We address this challenge by constructing an approximate separation oracle for the action set that either generates executable policies from queried features, or refines an outer approximation of the action set. This approach draws inspiration from the reduction of van Erven et al. (2025) for linear contextual bandits and the oracle-efficient linear bandit algorithm of Ito et al. (2019), but additionally deals with the imprecision of the oracle. The resulting algorithm requires only aggregate loss feedback, and to our knowledge. This is the first polynomial-time algorithm for adversarial MDPs with aggregate feedback beyond the tabular case.

Haolin Liu, Chen-Yu Wei, Hanbin Zhou

University of Virginia · Hong Kong University of Science and Technology

Linear Markov Decision Processes

Ask PDF

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