Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options
Authors: Joongkyu Lee
Seouh-won Yi
Min-hwan Oh
Venue: NeurIPS 2025 poster ()
Keywords: Preference-based Reinforcement Learning
Ranking Feedback
Plackett–Luce Model
Reinforcement Learning from Human Feedback
Dueling Bandit
Primary area: theory
TL;DR: We present the first theoretical analysis of PbRL with ranking feedback, showing that longer ranking feedback can provably improve sample efficiency.

Abstract: We study online preference-based reinforcement learning (PbRL) with the goal of improving sample efficiency. While a growing body of theoretical work has emerged—motivated by PbRL’s recent empirical success, particularly in aligning large language models (LLMs)—most existing studies focus only on pairwise comparisons. A few recent works  (Zhu et al., 2023, Mukherjee et al., 2024, Thekumparampil et al., 2024)  have explored using multiple comparisons and ranking feedback, but their performance guarantees fail to improve—and can even deteriorate—as the feedback length increases, despite the richer information available. To address this gap, we adopt the Plackett–Luce (PL) model for ranking feedback over action subsets and propose **M-AUPO**, an algorithm that selects multiple actions by maximizing the average uncertainty within the offered subset. We prove that **M-AUPO** achieves a suboptimality gap of $\tilde{\mathcal{O}}\left( \frac{d}{T} \sqrt{ \sum_{t=1}^T \frac{1}{|S_t|}} \right)$, where $T$ is the total number of rounds, $d$ is the feature dimension, and $|S_t|$ is the size of the subset at round $t$. This result shows that larger subsets directly lead to improved performance and, notably, the bound avoids the exponential dependence on the unknown parameter’s norm, which was a fundamental limitation in most previous works. Moreover, we establish a near-matching lower bound of $\Omega \left( \frac{d}{K \sqrt{T}} \right)$, where $K$ is the maximum subset size. To the best of our knowledge, this is the first theoretical result in PbRL with ranking feedback that explicitly shows improved sample efficiency as a function of the subset size.

Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options
Joongkyu Lee Seoul National University jklee07170smu ac.kr
Seouh-won Seoul National University uniqueseouh@enu. ac
Min-hwan Oh Seoul National University minoh@snu. ac. krr
Abstract
We study online preference-basee reinforcement learning (PbRL) with the goal of improving sample efficiency. While a growing body of theoretical work has mmtived-motivated by PbRL's recent empirical success, particularly in align- ing large language models (LLMs) most existing studies focus only pairwise comparisons. A few recent works 193 49 76 have explored using multiple compar- isons and ranking feedback, but their performance guarantees fail to improve and can even deteriorate-aa as the feedback length increases, despite the richer informa- tion available. To address this gap, we adopt the Plackett- (PL.) model for ranking feedback over action subsets and propose M-AUPO, an algorithm that selects multiple actions by maximizing the average uncertainty within the offered subset.
We prove that M- AUPO achieves a suboptimality gap of Ō (4V) 21-1 [8.T] where
T is the total number of rounds, d is the feature dimension, and [Sa]| is the size of the subset round This result shows that larger subsets directly lead to improved performance and, notably, the bound avoids the exponential dependence on the unknown parameter's norm, which was a fundamental limitation most previous where is the maximum subset size. To the best of our knowledge, this is the first theoretical result in PbRL with ranking feedback that explicitly shows improved sample efficiency as a function of the subset size.
works. Moreover, establish a near-matching lower bound of Ω d
KVT
Introduction
The framework of Preference-basee Reinforcement Learning (PbRL) 12
80 8
70
was introduced
address the difficulty of designing effective reward functions, which often demands substantial and complex engineering effort 779 81). PbRL has been successfully applied in diverse domains, including robot training, stock prediction, recommender systems, and clinical trials 30
65
18
Notably, PbRL also serves as a foundational framework for Reinforcement Learning from Human Feedback (RLHF) when feedback provided in the form of preferences rather than explicit scalar rewards. This preference-basee approach has proven highly effective in aligning Large Language
Models (LLMs) with human values and preferences [8] 57 62).
Given its practical success, the field has also seen significant theoretical advances 16
70
93
86
4 38). However, despite this progress, most existing models remain limited to handling only pairwise comparison feedback. A few works [93 76] explore the more general setting of multiple comparisons, offering strict extension beyond the pairwise case. Zhu et al. [93] study the offline setting, where a dataset of questions (or contexts) along with corresponding ranking feedback over K answers (or actions), labeled by human annotators. is available. Mukherjee et al. 449 investigate the online learning-to-rant problem [61], where dataset of questions with K candidate answers provided, but no feedback is initially available.
91
90
g 72
49 74
76
85
49
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparisons of settings and theoretical guarantees in related works on PbRL with ranking feedback. Here, T denotes the number of rounds (or the number of data points in the offline setting), K' is the (maximum) size of the offered action set (i.e., axsortment), and is the feature dimension. p represents the unknown context distribution. Here, O hides logarithmic factors and polynomial dependencies on B. "Pred. Error" refers to the prediction error.
Setting
Context
Assortment
Measure
Result
Zhu et al.
Offiine
Accessible
Given
Suboptimality
Mukherjee
Online
Accessible
Given
Pred. Error
0 0
Thekumparampil al. 76
Online
No context
Select K
Pred. Error
This work (Theorem
Online
Sampled x ~ p
Select & K
Suboptimalityy
Ei- (377]
This work (Theorem 3
Lower Bound
Sampled x
Select & K
Suboptimality
d KVT
Thekumparampil al. [76] consider a context-free setting (i.e., singleton context), and the goal is to learn the ranking of N K answers based on ranking feedback obtained from subsets of size K. However, all of their theoretical performance guarantees fail show that using multiple comparisons provides any advantage over the pairwise setting (see Table This is counterintuitive, as ranking feedback is inherently more informative than pairwise feedback. Specifically, since a ranking over K actions provides (t) pairwise comparisons, it should, in principle, enable faster learning and lead to stronger performance guarantees. Thus, the following fundamental question remains open:
Can we design an algorithu that achieves a strictly better theoretical guarantee under multiple-option feedback compared to the pairwise comparisons in the online PbRL setting?
In this paper, we assume that the ranking feedback follows the Plackett-Lacc Luce (PI.) model [60] 45), where, in each round, the learner receives ranking feedback over a subset of up K actions (with K & N) selected from a universe of N actions. This problem setup is closely related to that of Thekumparampil et al. [76); however, unlike their work, which focuses solely on context-free setting (or equivalently, a fixed singleton context), we study a more general setting where contexts are diverse and drawn from an unknown distribution.
Under this problem setup, we provide an affirmative answer to the above question by introducing novel algorithm, Maximizing Average Uncertainty for Preference Optimization (M-AUPO), which explicitly exploits the richer information available from ranking feedback under the Plackett-Luce (PI.) model. M-AUPO selects action subsets by maximizing average uncertainty and achieves suboptimality gap that strictly improves upon what is attainable with pairwise comparisons. In particular, we show that its suboptimality gap decreases with longer ranking feedback.
Furthermore, our suboptimality gap eliminates the exponential dependence on the parameter norm bound, Oce"), in the leading term. This improvement stems from analytically dividing the total rounds into warm-up up and non-warm-up phases (see the proof sketch in Section [5.I). This repre- sents significant improvement over most prior works, where performance guarantees depend on OeeB) [66] 70 93 86
76 38). Very recently, a few works [1, 20 have successfully avoided the O B) dependency by relying on auxiliary techniques additional information- such as specialized sampling schemes [4] or prior knowledge of ι: [20] however, are often imprac- tical. Moreover, their methods are limited pairwise comparison settings. In contrast, our approach climinates the (ce dependency without using any auxiliary techniques and considers more general ranking feedback beyond pairwise comparisons. Our main contributions are summarized as follows:
91
19
85
Improved sample efficiency via larger subsets: We propose M-AUPO, novel algorithm for online PbRL. (or RLHF) with PL. ranking feedback, which achieves a suboptimality gap
where |SS|] is the size of the action subset offered at round This result provides the first rigorous theoretical guarantee that larger subsets directly improve sample efficiency. To the best of our knowledge, this is the first theoretical work in PbRL. that explicitly demonstrates performance improvements as function of the subset size |..]..
Ō V |Sc

---

Improvement on O(e") dependency: Our result eliminates the exponential dependence on the parameter norm bound, O(e"), in the leading term without relying on any auxiliary techniques-through a fully refined analysis. This shows that the (e)B) dependence widely observed in PhRL. (or RLHF) and dueling bandit analyses not inherent but rather an artifact of loose analysis. Moreover, our key technique for removing the (Ee dependence- by dividing the rounds into warm-up and non-warm-up phases only in the analysis be seamlessly incorporated into existing PbRL or dueling bandit analyses, including regret- minimization frameworks without altering the underlying algorithms (see Appendix [G.T) To the best of our knowledge, this is the first PbRL work with ranking feedback beyond pairwise comparisons that avoids the O )) dependence.
Efficiency of Tran-bbrekking (RB): We present both naive PL loss loss-based and rank-breaking (RB) coss-based learning approaches, and show that the RB formulation achieves superior computational efficiency and empirical performance compared to the PL counterparr.
Lower bound:
We establish a near-matching lower bound of Z
under the PL
KVT
model with ranking feedback, matching our upper bound up to a K factor. This shows that leveraging richer ranking information (larger K) provably improves sample efficiency.
Experiment: We empirically evaluate M-AUPO on both synthetic and real-world datasets, showing its improved performance for larger K and its superiority over existing baselines.
2
Related Works
Fueled by the remarkable success of LLMs 18 57 62). the theoretical study of PbRL has rapidly emerged as a central focus within the research community. Early work in this area traces back to the ducling bandits literature [88] 95 68 [8].
Dueling bandits. The dueling bandit framework, introduced by Yue et al. 88 departs from the classical multi-armed bandit setting by requiring the learner to select two arms and observe only their pairwise preference. For general preferences, a single best arm that globally dominant may not exist. To address this, various alternative winners have been proposed, including the Condorcet
winner [94 35
Copeland winner (95] 82 36), Borda winner [31 25 28 69 84], and von Neumann each with its own corresponding performance metric.
winner 63 24
To address scalability and contextual information, Saha [66] proposed a structured contextual dueling bandit setting in which preferences are modeled using Bradley-Tery-- (BTL) model (I] based on the unknown intrinsic rewards of each arm. In similar setting, Bengs et al. ( studied a contextual linear stochastic transitivity model, and Di et al. (2I) proposed a layered algorithm that achieves variance-aware regret bounds. However, most prior dueling bandit works suffer from an O(e") dependence. Only few recent studies 20 [4 have succeeded in removing this O(e term, either by introducing additional complex subroutines or by relying on prior knowledge of K 20
Preference-based reinforcement learning (PHRL). Building upon this line of work, subsequent research has extended the dueling bandit framework to the RL. considering both online [87 52 16
70 83 and offline settings [93 91 44). More recently, under the active learning framework where the full set of contexts X' is accessible-maan mani studies aim to improve sample efficiency by selecting prompts either based on the differences in estimated rewards for their responses (50) or through D-optimal design methods 47 71 19
76 38 However, most of these works focus exclusively on pairwise preference feedback and cannot be extended to more general ranking feedback cases. Mukherjee al. (49 study the online learning- tooiing-t-rratt to-k problem when prompts are given along with K candidate answers, while Thekumparampil et al. (76) investigate learning to rank N > K answers from partial rankings over K answers, but under a context-free setting. In this paper, we consider a stochastic contextual setting (more general than Thekumparampil et al. (76)), where contexts are sampled from an unknown but fixed distribution, and aim to minimize the suboptimality gap using ranking feedback of up to length K. For further related work, see Appendix
49
3 Problem Setting and Preliminaries
Notations. Given a set X, we use | to denote its cardinality. For a positive integer n, we denote [n] := (1,2,... ... n2). For a real-valued matrix A, we let ||Al| = sup=:|=]a=1 ||Ar|| which is the
3

---

maximum singular value of A. We write A = if 1- - -A' is positive semidefinite. For a univariate function f. we denote as its derivative.
We have set of contexts (or prompts), denoted by X, and of possible actions (or answers), denoted by A := {a aN) } We consider preference feedback in the form of partial rankings over subsets of A, and model this feedback using the Plackett-Luce (PL) distribution:
Definition (PL. model), Let S =- (S = 2 & |S| & K) be the collection of all action subsets whose sizes range from 2 to K. For any Se S, let a denote the labeler's ranking feedback-that is, a permutation of the elements in S. We write o for the j-th most preferred action under a. We model the distribution of such rankings using the Plackett- Luce (PL) model [60 45y, defined as:
1s|
exp (rg. (z,
(;0),, -
where (I, S) x
(1)
ش exp exp (ro- ow))
Here, rg- represents a reward model parameterized by the unknown parameter 0*
When = 2, this reduces to the pairwise comparison framework considered in the Bradley-Terry Luce (BTL) model [TT]. The probability that a is preferred a' given be expressed as:
exp (re- (Ir, a))
Pa(a > a' alI::; 0*)
exp (r, exp (ro-(z,a')) / (ro- (I, a) ro- az),
(2)
where u(w) 14e-w is the sigmoid function. In this work, assume linear reward model:
Rd be known feature map satisfying maxz,a lØ(zz, a)llz & and let 0* Rd denote the true but unknown parameter. The reward is assumed to follow a linear structure given by re- (I, = Φ(x T
Assumption Let Φ X x
0". We further assume realizability, i.e., 0" E θ == (0 Rd 0 & B). Without loss of generality, we assume z 1.
At each round e [T]. context I; X' is drawn from a fixed but unknown distribution p. Given the context Tt, the learning agent selects a subset of actions S, S-referred as an assortment throughout the paper and receives a ranking over St as feedback, generated according to the PL model. Let x (a) argmax, (2, a) be the optimal policy under the true reward rer. After T rounds of interaction with the labeler, the goal is to output policy कि. X - A that minimizes the suboptimality gap, defined as:
SubOpt(T) = Ee- [re. (z,)" re- (I,
3.1 Loss Functions and Rank-Breaking
In this paper, we consider different losses for estimating the parameter: one directly induced by the PL model, and the other obtained by splitting the ranking feedback into pairwise comparisons.
Plackett-Luce (PL) loss. The PL loss function for round is defined follows:
SSc
exp (ó(z), ot))
(0)
where =- -0) log
Sc kーjj exp (ól Ft, otx) TO))
Here, (0) denotes the negative log-likelihood loss under the Multinomial Logit (MNL) model [46] conditioned on the assortment being the remaining actions in S, after removing the previously selected actions O....... O(j-1) ,
that is, over the set S, ,., ((j-))))
Rank-Breaking (RB) loss. In addition to this standard approach, can replace the full |S,|-action ranking with its (Siil pairwise comparisons. This technique, referred as rank-breaking (RB), decomposes (partial) ranking data into individual pairwise comparisons, treating each comparison as Thus, the RB loss is defined as:
independent
32
|S.1-1 - S,
exp (0(#1, oej)) 0)
(0) = Σ
Σ
(..) (0),
where of ((ik)
= (0)=
log
(4)
Eme exp (o(I,, Jtm
1= Aーjー1
This approach is applied in the current RLHF for LLM (e.g., Ouyang et al. [7) and is also studied in the theoretical RLHF paper 933
under the offline setting.
For simplicity, we assume stationary action space A. though it may depend on the context X.

---

Procedure OMD-PL, OMD for PI Loss
Procedure 2 OMD-RB, OMD for RB Loss
Input: 000, St, H+, for j 1 to [St] do Update f 0 via 5
Input: 0(1.2) St. He
for each k) such that j < k < |
do
Update H((AA), 0(2k+1) via end for return 0(155|-1.S.:--
end for return 0 (((++111)
3.2 Online Parameter Estimation
Motivated by recent advances in Multinomial Logit (MNL) bandits 992 39 41 we adopt an online mirror descent (OMD) algorithm to estimate the underlying parameter 0" instead of relying on maximum likelihood estimation (MLE). This enables constant per-round computational cost, in contrast to the MI.E-based approach, whose cost grows linearly with the number rounds t.
OMD update for PL loss. For the the PL loss
3
estimate the true parameter 0 as follows:
0(++1) argmin < (5) (0()) ),0) 0) + 27
10
Po j= 1 St,
where we write 0(1 = 0 (1)
t+1 and is the siep-size parameter to be specified later. The matrix
AT()) is given by A7(0 = H, Σ =
( (0("))
where
11 Σ
Σ
v (0) ( ALe, ^>
(6)
The optimization problem 5 can be solved using a single projected gradient step (55). which enjoys computational cost of only (iddd))-ideeeendent of [48), unlike MLE-an and requires only ((d))
storage, thanks to the incremental updates of H()) and He-
OMD update for RB loss. Similarly, for the RB loss
4 we estimate the underlying parameter as:
@ g(+++t) argmin <vel (((.k))
0
0 A.
1 1 j < k |St).
(7)
27
where we set 0f 00.15:1+11_ = 0: (1+++++2) for all < [Sp| 1 and for the final pair, let 0 -11.11111)1111
@(.2). The matrix (((i))) is defined as (r(i.k) = H, + (G v2el k)) (0 (6,
M) where
1.1-111
SS
H, - E
Σ Σ
V
(()))) + ALa A>0. 0.
(8)
k-j+1
Remark (Computational cost of OMD). The per-round computational cost of the PL parameter update is d(K²d') since the parameter is updated |S, & K times per round. Similarly, the cost for the RB parameter update is O(33d {),, the parameter is updated (15:ll times per round.
M-AUPO: Maximizing Average Uncertainty
In this section, we propose a new algorithm, M-AUPO, which selects an assortment that maximizes the average uncertainty of S., thereby exploiting the potential benefits of larger K. For clarity of presentation, we first define the MNL probability (46) for a given assortment S at round as follows:
exp (Ó(12, a) TT
S: Enes exp (Ø(I), a') TTO 0)
Va E S.
We write (.,K) & (j, indicate lexicographic order. i.e., j j j' and k' & k.
5

---

Algorithm 3 M-AUPP: Maximizing Average Uncertainty for Preference Optimization
1: Inputs: maximum assortment size K, regularization parameter X, step size
2: Initialize: H1 AIg 01 E
3: for round = to T do
4: Observe Iı P and select St via
5: Observe ranking feedback 0z for S.
6: Oc+1 - OMD-PL(O:; St, H.) (Proc.
t- or OMD-RB( 0., St, H.) (Proc. 2 if RB loss
7: Update He+1 H, D 4 (0++))
via (6)
via (8) if RB loss
8: end for
9: Return: (x) - argmax (1 a) 0r+1
Given an assortment S and ranking feedback o, let S = {ar...... Tss) denote the remaining actions in S after removing the first j - actions. Let IPr [S: = P( 0), for simplicity. Then, the PL model in Equation ( can be expressed as follows:
Pi(o|S;0) 0) = P((ai(S;0) P(oy|SMa11)00 ... P(o
I Pi(o, ==1
Greedy assortment selection for PI. loss. Given H2 and Q., we define the function fc(S) as follows:
f((S) = Σ
1
[S]
E (1s.0.)
|o a) - E w.w.s1PP
a' 2') H
1
(10)
Intuitively, finding S that exactly maximizes fi(S) amounts maximizing the average (mean- centered) uncertainty- that is, the Mahalanobis dispersion of the feature vectors evaluated under H However, computing the exact maximizer of Equation (10) generally NP-hard. our setting, it is sufficient to add actions sequentially in a greedy manner. This is because our analysis centers on the suboptimality gap between two actions- one optimal and one chosen by the policy. As result, the suboptimality gap is (approximately) upper bounded by term involving (S) for pairwise action sets (i.e., |S| 2). Therefore, greedily adding actions that increase fe(S) is sufficient.
We initialize 5 with a pair of actions ([S) =
2) that maximizes the average information gain, as defined in Equation (0)). Then, iteratively add one action a time by
a' E argmax (a S), where (a S) = fS u (at) f((S), AES
(11)
and accept at if (a(a) S) > O. until [S| = K no non-negative gain remains. This selection rule central to our algorithm, as it facilitates a rapid decrease in the reward estimation error by favoring assortments that provide more informative feedback, especially when the assortment size |S, is large. Notably, the greedy variant of the selection rule can be implemented efficiently with a computational cost of O(N d3 LNK22 K df I. where L denotes the (approximate) expectation cost over the ranking
a. This implementation avoids enumerating all (x) possible subsets.
Greedy assortment selection for RB loss. Analogous to Equation [0). we define the following function to select an assortment that maximizes the average uncertainty:
fe(S) = S
1
Σ a,a'ES
E a- P(Claa.a));
|o a) - E (0 (o(re, xل]
2
H,
1
Σ
á (()(z;;)) - o(z,, a')),,')) TO)
| a) paz,, a d')l
(12)
S|S
G.0'ES
We then perform greedy assortment selection according to Equation III Note that, unlike in the PL loss case, assortment selection under the RB loss does not require taking expectations over rankings, as all pairs within S are directly compared. Therefore, the RB-based assortment selection both exact and computationally efficient, without any additional expectation-approximati cost L, and incurs a total computational cost O (N 8 + &
*O(N2& to choose the first pair, followed by at most additions, each which requires (LNN 'O(22 ( to choose the first pair, followed up K additional steps, each costing O(NK3)

---

Once the assortment S; is selected, the algorithm receives the ranking feedback from the labeler (Line 5) and updates the parameter using Procedure [ for the PL loss or Procedure 2 for the RB loss (Line 6). After 7 rounds, the algorithm returns the final policy कr, which selects actions by maximizing the estimated reward under the final parameter estimate 0r+1 (Line 7
Main Results
5.1
Suboptimality Gap of M-AUPO
begin by presenting the online confidence bound for the PL loss, derived by extending the results of Lee and Oh 41,, who analyzed the MNL model [46]. Since the PL model constructs ranking probabilities as a product MNL probabilities, their confidence bound can be directly applied to our
setting by replacing the round with the cumulative number of updates Σ [Sa]-
Corollary (Online confidence bound for PL loss). Let ó (0, We set 1 = (1 + 3/B2BB222 and max 12m, 144nd, 2). Then, under Assumption
with probability at least 6, we have
10
0' H & B,(5) - O B
(log(((///)) B
BVA),
V 1,j < Sal
where H(") = Hi + + 22 2 (0. (1) AL4-
This confidence bound is free of any polynomial dependency on K, which is primarily made possible by the improved seff-concordantllkk properties proposed by Lee and Oh [1]. Moreover, for the RB loss, we can derive confidence bound of the same order (see Proposition D.I.. Based on this confidence bound, we derive the suboptimality gap for M-AUPO, with the proof deferred to Appendix C
Theorem (Suboptimality gap for PL loss). Let ò E (0, Set X = lgd KT/0) + n + d))
and 1 [1 3/2B). Define e-BB If Assumptioo ① holds, then for any T > eKid, with probability at least - 5, M-AUPO (Algorithm
3 achieves the following suboptimality gap:
d T
1 S
dK* RT
SubOpt(7) -
Discussion of Theorem For sufficiently large T, the second (non-leading) term becomes negligible, and Theorem I shows that the suboptimality gap of M-AUPO decreases as the assortment size |S,]] increases. This establishes a strict advantage of receiving ranking feedback over larger assortments. Moreover, result does not involve any (ee dependency in the leading term, harmful depen- dency that commonly appears in prior works [66 70 93
19 76 38. Although very recent studies 20 14] also achieve D(cB)-free performance in the leading term, they rely auxiliary techniques and are restricted to pairwise preference feedback. To the best of our knowledge, this the first theoretical study that simultaneously establishes (i) the performance benefits of utilizing richer ranking feedback over larger assortments, and (ii) the elimination of the (ee)) dependence in the leading term of the PbRL framework when accommodating multiple (i.e., more than two) options.
86 91
Proof sketch of Theorem I We provide a proof sketch for Theorem I For simplicity, we define at,,,a' o( a) o(z,, d'). We begin by defining the set of warm-up rounds, denoted by T which consists of rounds with large (non-centered) uncertainty:
w
E [T]
max I|Vr. a,a'EA
H > 1/ (3 (3(3
1) Regret decomposition and assortment selection. The proof begins by decomposing the subopti- mality gap into two components: the realized regrets and martingale difference sequence (MDS). Since the MDS term can be readily bounded using the Azuma Hoea-HHogiiiigg inequality, the analysis focuses bounding the realized regrets.
7

---

SubOpt(T))
(a.) (((()))))))))))))
0
MDS,
T
realized regret of fr at round
=O(1VVT)
de
(a). 14
10 00' -rtaall +0
VT
KT
-0.(0))
In the inequality, we first use the fact that -VV (ma)), '0r+1 > 0, which follows from definition of Pr.. We then apply Hölder's s inequality together with the inequality Hr+1 H.- Moreover, we invoke Lemma C.4) which states that the regret incurred during the warm-up rounds
T is a non-leading term. Finally, by applying Corollary we bound |0- - 0r+lllrr by O(vd).
2) Avoiding OeeB) for non-warm-up rounds. For & T we have
3,(0)
(E,.) (x:)) 0* & (a) 10 1 Hr 3/2KBr+11
$ 1,
which implies that 1/A0 ( (1 t, (as),
0*)
< (1 (1+ Thus, we obtain
1 Σ (arra)) 1
(1 + e)²
(((1) "*)
T
T
NT"
e( 11 + e)²
Σ
T
where the last inequality follows from Lemma
E.2
together with the fact that for any a, A and
t $ T a 0(+1)l < | H
0 0 Hr & 3r+6)/3r+1(0) = 1. Then, by the
inequality, and ignoring constants, we have
1
Σ T
18cl ((( Oc+1) (o,,) (e, H.
T
S
TT
T
T
1
Seel fe((=*(x)), (x
1
Σ
S f(())
T
Seel
Sel
(S₁ selection)
T
Si1 Σ
(0(z,, a) - E p1(-)57",, ,, 16( M.
p(( P((1 0.)
(Lemma
S
18T
where M, -ESeet- Σ/=,1 E. ( (o,) + AI is the expected version of H..
Finally, applying the elliptical potential lemma (Lemma C.3 we concludes the proof.
Remark (Generality of our technique for avoiding ( D). Our approach of dividing the total rounds into warm-up and non-warm-up phases improve the Oee dependency is broadly appli- cable. In particular, this technique can be readily incorporated into most existing PbRL and dueling bandit algorithms without modifying their original algorithms. See Appendix G. for more details.
Furthermore, under the rank-breaking (RB) parameter update 7 and assortment selection rule (22 we establish a comparable suboptimality gap for the RB loss. The proof is provided in Appendix
Theorem 2 (Online confidence bound for RB loss). Under the same setting as Theorem the parameter is updated and the assortment is selected according to the RB-loss setting and K² & (2v6 + 12/3B)d, then for any T 2 ek2/d, with probability at least 1 - 5, M-AUPO
(Algorithm 3 satisfies SubOpt(T) = δ
T
d²
T
S2
KT
8

---

Discussion of Theorem 2 For sufficiently large T, the suboptimality gap in Theorem matches the leading-order term of Theorem [T] while its second (non-leading) term is tighter by factor of O O(K'). In addition, the assortment selection cost for RB (12) is lower, since it avoids the expensive expectation over rankings required in the PI.-loss case (Equation (10).. This yields an important insight: under ranking feedback, breaking the ranking and updating pairs independently can be more computationally efficient-and even more stable- than learning directly from the PL loss. Although the bound is stated for the small-K regime, the assumption appears mild in practice, since in LLM applications the dimension d is typically much larger than K. Moreover, this result provides theoretical explanation for the empirical success of RLHF in LLMs (e.g., Ouyang et al. (57)) where ranking feedback commonly decomposed into pairwise comparisons for parameter estimation.
5.2 Lower Bound
Theorem 3 (Lower bound). Suppose 3 d)((K2). Define the feature space as $ :- Sa-1, the unit sphere in R&, and let the parameter space be θ = {-p, 1,," where μt /d/(SKTT). Then, for any final policy रo Le returned after collecting T samples (using any sampling policy), the expected suboptimality gap is lower bounded as:
d
SubOpt(T) - KVT
Discussion of Theorem 3. The proof is deferred to Appendix Theorem 3 provides theoretical support for our upper bounds, especially in their dependence on K; in particular, it matches the upper bound in Theorem 2 when |S.| K. To the best of our knowledge, this is the first lower bound on the suboptimality gap that incorporates PL ranking feedback in PbRL and formally shows that the suboptimality gap can diminish as K grows, highlighting the ad advantage of utilizing ranking feedback over simple pairwise comparisons.
6 Numerical Experiments
We conduct two sets of experiments to empirically validate our theoretical findings: (i) one using synthetic data (Subsection 6.1). and (ii) another using two real- woll-world datasets (Subsection 6.22) We compare our proposed algorithm, M-AUPO, against three baselines: (i) DopeWolfe (76), which selects K actions in non-contextual setting; (ii) Uniform, which uniformly samples assortments of size K at random; and (iii) Best&Ref constructs an action pair ([S, 2) by combining the action that maximizes the current reward estimate with another sampled from reference policy (e.g., uniform random or SFT), following the setup in Online GSHF [86] and XPO [85]. In our experiments, the reference policy for Best&Ref is set the uniform random policy.
6.1 Synthetic Data
In the synthetic data experiment, for each instance, we sample the underlying parameter 0* (0 Ia) and normalize it to ensure that | 2 & 1. At every round f, a context x E X' is drawn uniformly at random, and its feature vector Φxx,)) lies within the unit ball. We set 5, |A] N = 100, and |X| = 100. We measure the suboptimality gap every 25 rounds and report the mean over 20 independent runs, together with one standard error.
The first two plots in Figure show the suboptimality gap of M-AUPO under both the PL loss 3 and RB loss 4 the maximum assortment size K varies. The results clearly show that performance improves as K increases, supporting our theoretical findings. In the third plot of Figure D we compare the performance of M-AUPO with three bascline methods at the final round for showing that our algorithm significantly outperforms all baselines. While DopeWolfe e also considers the selection of К actions from N actions, it treats each context independently and is specifically designed for the context-free setting (i.e., a singleton context). As a result, DopeWolfe cannot leverage information sharing across varying contexts and performs poorly in our setting. Furthermore, M-AUPO outperforms naive assortment selection strategies such as Uniform and Best&Ref, as it explicitly chooses assortments that maximize the average uncertainty, thereby achieving more efficient exploration. Finally, the results also show that the RB version of M-AUPO empirically outperforms the Pl.-based approach, since RB does not incur approximation errors when computing expectations. See Appendix H.T for additional experimental results.

---

PL Loss, varying
RB Loss, varying K
vs Other Methods, K=5
0.20
0.20
WAUFO 10-21
N-AUPO 18=21
SibbOpt, (t=20))
Subbpt Gap
3.155
HAUPO (K-51
HAUPO (K-31
08011 0.15
N-AUPO 18
NIAUPO 1i
AUro poust
MAURO (K-71
MiAURO (8-
6.5
124
6.15
0.10-
MaliR 18)
0.10
NiAURO (60101
0.1
0.02
Loss
Figure 1: Synthetic data experiment: suboptimality gap of M- AUPO under varying K, evaluated with PL loss (left) and RB loss (middle), along with comparison against other baselines (right).
TREC- DL, varying
NECTAR, varying K
PL Loss vs Baselines, K-3
MAURO
(o-2
SubOpt, (t-200)
undimm
KAUPO Rod)
SubOpt C50
SubOat Coo
(6-21
0.3
0.3
0.20
6.22
62-
0:
3000
10000
15000
20000
52000
10050
15002
20003
Round (L)
Round (t)
TREC-DL
NECTAR
Figure 2: Real-world dataset experiment: suboptimality gap of M-AUPO under varying K the TREC-DL. dataset (left) and the NECTAR dataset (middle), along with comparison against other baselines (right). The results are rescaled align the performances between the two datasets.
6.2 Real-World World Dataset
We also conduct experiments using real-world datasets from TREC Deep Learning (TREC-DL) and NECTAR The TREC-DL dataset provides 100 candidate answers for each question, while the NECTAR dataset offers candidate answers per question. We sample | = 5000 prompts from each dataset, with the corresponding set of actions (100 or actions, respectively).
We use the gemma-22 2 (75 LLM to construct the feature Φ(x, a). Specifically, o(x, a) is obtained by extracting the embedding of the concatenated prompt and response from the last hidden layer of the LLM, with size = 2048. Additionally, we use the Mistral-7B B3] reward mode as the true reward model re- generate ranking feedback and compute the suboptimality gap accordingly. We measure the suboptimality gap every 2,500 rounds and report the average over 10 independent runs, along with the standard error. In these experiments, report results only for the RB version of M- AU-P,, as it is computationally more efficient and empirically performs better, as shown in Figure [
The first two plots in Figure show that the performance improves as K increases on two real-world datasets In the third plot of Figure we compare the performance of M-AUPO with other baselines with K = 3 at the final round, showing that M- AUPO outperforms baselines by large margin. See
Appendix H.2 for additional experimental details and results.
7
Conclusion
To the best of our knowledge, this work provides the first theoretical result in online PbRL showing that the suboptimality gap decreases more options are revealed to the labeler for ranking feedback. Our analysis also removes the O) dependency the leading term without modifying the algorithm, implying that existing PbRL and dueling bandit methods can similarly avoid this dependence through our refined analysis. Together, these results advance the theoretical understanding of PbRL, revealing both the value of richer feedback and the opportunity for more refined and efficient analysis.
"httss//hugginggface www.aeeeeeeeeeeeeeeeeeeeeeeeeeee
"httss//hugginngfcce http:///hugggggaaecccoooogggggge 'hats://hugginnffcce cot.coo////////aaae www.:wwrrddoooe--idd-dddd 7B-insi -n-itrrtt-Uniffeed Feeebbcck
10

---

Acknowledgements
This work was supported by the National Research Foundation Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NRO7IES 1853, RS-2023-00222665 and RS RS-2025-255 2025-254208499 by the Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2025-02263755 and AI-Bio Research Grant through Seoul National University, and by the 2025 Global Google PhD Fellowship funded with support from Google.org.
by the
References
[1] Yasin Abbasi- Yadiii, Dávid Pál. and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 14:2312-2320, 2011.
[2] Mare Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages (691-3699, PMLR, 2021.
[3] Priyank Agrawal, Theja Tulabandhula, and Vashist Avadhanula. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 310(2):737-750, 2023.
[4] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. In Conference on learning theory, pages 76-78. PMLR, 2017.
[5] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach assortment selection. Operations Research, 67(5):1453-1485 2019.
[6] Hossein Azari Soufiani, William Chen, David C Parkes, and Lirong Xia. Generalized method- of-moments for rank aggregation. Advances Neural Information Processing Systems, 26, 2013.
[7] Akshay Balsubramani. Zohar Karnin, Robert E Schapire, and Masrour Zoghi. Instance- dependent regret bounds for ducling bandits. Conference on Learning Theory, pages 336-360. PMLR, 2016.
[8] Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier. Preference- based online learning with dueling bandits: A survey, Journal of Machine Learning Research, 22(7):1-108, 2021.
[9] Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In International Conference on Machine Learning. pages 1764-1786. PMLR, 2022.
[10] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
[11] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
[12] Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, Weiwei Cheng, and Eyke Hüllermeier. Preference-basee reinforcement learning: evolutionary direct policy search using preference- based racing algorithm. Machine learning, 97:327-351, 2014.
[13] Shicong Cen, Jincheng Mei, Katayoon Goshvadi, Hanjun Dai, Tong Yang, Sherry Yang, Dale Schuurmans, Yuejie Chi, and Bo Dai. Value-incentivized preference optimization: A unified approach to online and offline RLHF. In The Thirteenth International Conference on Learning Representations, 2025. URL attpss//oppenrviiie http://rer.en.e.eeeeooooooooraaa

---

[14] Mingyu Chen, Yiding Chen, Wen Sun, and Xuezhou Zhang, Avoiding exp (r) scaling in rlhf through peference-based exploration. In The Thirty- Annual Conference on Neural Information Processing Systems, 2025.
[15] Xi Chen, Yining Wang, and Yuan Zhou, Dynamic assortment optimization with changing contextual information. The Journal of Machine Learning Research, 21(1):89188866 2020.
[16] Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-in -nt-o--oooho Provably efficient preference- based reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 2022.
[17] Wooseong Cho, Taehyun Hwang, Joongkyu Lee, and Min-hwan Oh. Randomized exploration for reinforcement learning with multinomial logistic function approximation. Advances in Neural Information Processing Systems, 37:766433 2024.
[18] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
[19] Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Active preference optimization for sample efficient rlhf. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 96-112. Springer, 2025.
[20] Qiwei Di, Jiafan He, and Quanquan Gu. Nearly optimal algorithms for contextual dueling bandits from adversarial feedback. In Forty-second International Conference on Machine Learning, 2024.
[21] Qiwei Di, Tao Jin, Yue Wu, Heyang Zhao, Farzad Farnoud, and Quanquan Gu. Variance- aware regret bounds for stochastic contextual dueling bandits. In The Twelfth International Conference on Learning Representations, 2024.
[22] Hanze Dong, Wei Xiong, Bo Pang. Haoxiang Wang. Han Zhao, Yingbo Zhou, Nan Jiang. Doyen Sahoo, Caiming Xiong, and Tong Zhang. Rlhf workflow: From reward modeling to online rlhf. Transactions on Machine Learning Research, 2024.
[23] Shi Dong, Tengyu Ma, and Benjamin Van Roy. On the performance of thompson sampling on logistic bandits. In Conference on Learning Theory, pages 1158-1160, PMLR, 2019.
[24] Miroslav Dudik, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference on Learning Theory, pages 563-587. PMIR, 2015.
[25] Moein Falahatgar, Yi Hao, Alon Orlitsky, Venkatadheerai Pichapati, and Vaishakh Ravindraku- mar. Maxing and ranking with few assumptions. Advances in Neural Information Processing Systems, 30, 2017.
[26] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference Machine Learning, pages 0052-3060. PMLR, 2020.
[27] Louis Faury, Mare Abeille, Kwang-Sung Jun, and Clément Calauzènes. Jointly efficient and optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 546-580. PMLR, 2022.
[28] Reinhard Heckel, Max Simchowitz, Kannan Ramchandran, and Martin Wainwright. Approxi- mate ranking from pairwise comparisons. International Conference on Artificial Intelligence and Statistics, pages 1057-1066. PMLR, 2018.
[29] Tachyun Hwang and Min-hwan Oh. Model-based reinforcement learning with multinomial logistic function approximation. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 7971-7979, 2023.
[30] Ashesh Jain, Brian Wojcik, Thorsten Joachims, and Ashutosh Saxena. Learning trajectory preferences for manipulators via iterative improvement. Advances neural information processing systems, 26, 2013.
12

---

[31] Kevin Jamieson, Sumeet Katariya, Atul Deshpande. and Robert Nowak. Sparse dueling bandits. In Artificial Intelligence and Statistics, pages 416-424, PMLR, 2015.
[32] Minje Jang, Sunghyun Kim, Changho Suh, and Sewoong Oh. Optimal sample complexity of m-wise data for top-k ranking. Advances in Neural Information Processing Systems, 30, 2017.
[33] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023. URL http://aaaxiiv.oaabaa/////as
[34] Ashish Khetan and Sewoong Oh. Data-driven rank breaking for efficient rank aggregation. Journal of Machine Learning Research, 17(193):1544 1-44 2016.
[35] Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory, pages
1 1141-1154. PMLR, 2015.
[36] Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Copeland dueling bandit problem: Regret lower bound, optimal algorithm, and computationally efficient algorithm. In International Conference Machine Learning, pages 1244-1244. PMLR, 2016.
[37] Andras Kupesik, David Hsu, and Wee Sun Lee. Learning dynamic robot-to-human object handover from human feedback. In Robotics Research: Volume 1, pages 161-176. Springer, 2017.
[38] Branislav Kveton, Xintong Li, Julian McAuley, Ryan Rossi, Jingbo Shang, Junda Wu, and Tong Yu. Active learning for direct preference optimization. arXiv preprint arXiv:2503.01070 2025.
[39] Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. In The eiihth- Annual Conference on Neural Information Processing Systems, 2024.
[40] Joongkyu Lee and Min-hwan Oh. Combinatorial reinforcement learning with preference feedback. In Forty-second International Conference on Machine Learning, 2025.
[41] Joongkyu Lee and Min-hwan Oh. Improved online confidence bounds for multinomial logistic bandits. In Forty-second International Conference on Machine Learning. 2025.
[42] Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. Improved regret bounds of (multinomial) logistic bandits via segrettt--coffddenceeee conversion. In International Conference on Artificial Intelligence and Statistics, pages 1474-4482. PMLR, 2024.
[43] Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. A unified confidence sequence for generalized linear models, with applications bandits. Advances in Neural Information Processing Systems, 37:124640-124685, 2024.
[44] Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang. Jose Blanchet, and Zhaoran Wang. Provably mitigating overoptimization RLHF: Your SFT loss is implicitly an adversarial regularizer. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URR. httprrewwwwwwwwweeeeeeeeeeeeeeee www//ferum//eeee sett/foruum?id-2ccaPPPieee
[45] R Duncan Luce et al. Individual choice behavior, volume 4. Wiley New York, 1959.
[46] Daniel McFadden. Modelling the choice of residential location. 1977.
[47] Viraj Mehta, Vikramjeet Das. Ojash Neopane, Yijia Dai, Ilija Bogunovic, Jeff Schneider, and Willie Neiswanger. Sample efficient reinforcement learning from human feedback via active exploration. arXiv preprint arXiv:2312. 00267, 2023.
[48] Zakaria Mhammedi, Wouter M Koolen, and Tim Van Erven. Lipschitz adaptivity with multiple learning rates online learning. In Conference on Learning Theory, pages 2490-2511. PML.R 2019.
13

---

[49] Subhojyoti Mukherjee, Anusha Lalitha, Kousha Kalantari, Aniket Anand Deshmukh, Ge Liu, Yifei Ma, and Branislav Kveton. Optimal design for human preference elicitation. Advances in 2024.
Neural Information Processing Systems, 37:90132-9000
[50]
William Muldrew, Peter Hayes, Mingtian Zhang, and David Barber. Active preference learning for large language models. In Forty-first International Conference on Machine Learning, 2024.
[51] Rémi Mumos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Cóme Fiegel, et al. Nash learning from human feedback. Forty-first International Conference on Machine Learning, 2023.
[52] Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 1029-1038, PMLR, 2020.
[53] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. Advances Neural Information Processing Systems, 32, 2019.
[54) Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9205-9215 2021.
[55] Francesco Orabona. modern introduction to online learning. arXiv preprint arXiv:1912.132211 2019.
[56] Mingdong Ou, Nan Li, Shenghuo Zhu, and Rong Jin. Multinomial logit bandit with linear utility functions. In Proceedings of the Teentt-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 2602-2608. International Joint Conferences on Artificial Intelligence Organization, 2018.
[57] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744, 2022.
[58] Jachyun Park, Junyeop Kwon, and Dabeen Lee. Infinite-horioon reinforcement learning with multinomial logit function approximation. In International Conference on Artificial Intelligence and Statistics, pages 361-369. PMLR, 2025.
[59] Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under contextual mnl demand. Advances in Neural Information Processing Systems, 35:3461-3474, 2022.
[60] Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series
C: Applied Statistics, 24(2):193-25) 1975.
[61] Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi-armed bandits In Proceedings of the 25th international conference on Machine learning. pages 784-791, 2008
[62] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neurul Information Processing Systems, (6:53728-53741 2023.
[63] Siddartha Y Ramamohan, Arun Rajkumar, and Shivani Agarwal. Dueling bandits: Beyond condorcet winners to general tournament solutions. Advances in Neural Information Processing Systems, 29, 2016.
[64] Sayak Ray Chowdhury, Anush Kini, and Nagarajan Natarajan. Provably robust DPO: Aligning language models with noisy feedback. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages PMLR, 21-27 Jul 2024.
14

---

[65] Dorsa Sadigh, Anca Dragan, Shankar Sastry, and Sanjit Seshia. Active preference-based learning of reward functions. 2017.
[66] Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits, Advances in Neural Information Processing Systems, 34:30050-30062 2021.
[67] Aadirupa Saha and Pierre Gaillard. Finally rank-breaking conquers mnl bandits: Optimal and efficient algorithms for mnl assortment. In The Thirteenth International Conference Learning Representations, 2025.
[68] Aadirupa Saha and Aditya Gopalan. Battle of bandits. In UAI, pages 805-814 0558114,7 2018. 2018.
[69] Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversarial dueling bandits. In International Conference on Machine Learning, pages 9235-9244. PMLR, 2021.
[70] Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International conference on artificial intelligence and statistics, pages 6263 6263-6289. PMLR, 2023.
[71] Antoine Scheid, Etienne Boursier, Alain Durmus, Michael Jordan, Pierre Ménard, Eric Moulines, and Michal Valko. Optimal design for reward modeling in rlhf. arXiv preprint arXiv:2410.17033 17055, 2024.
[72] Ayush Sckhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Contextual bandits and imitation learning with preference-bait based active queries. Advances in Neural Information Processing Systems, 36:1 1261-11295, 2023.
[73] Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. In Conference on learning theory, pages 3-24. PMLR, 2013.
[74] Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alckh Agarwal. A minimaximalist approach to reinforcement learning from human feedback. In Proceedings of the 41 International Conference Machine Learning, pages 47345-47377, 2024.
[75] Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXiv preprint 3xXi:2443.08295, 2024.
[76] Kiran Koshy Thekumparampil, Gaurush Hiranandani. Kousha Kalantari, Shoham Sabach, and Branislav Kveton. Comparing few to rank many: Active human preference learning using randomized frank-wolfe method. In Forty-second International Conference on Machine Learning, 2024.
[77] Jean Ville. Étude critique de la notion de collectif, volume 3. Gauthier-Villars Paris, 1939.
[78] Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward-free rl is no harder than reward-aware rl in linear markov decision processes. In International Conference Machine Learning, pages 22430-22456. PMLR, 2022.
[79] Christian Wirth and Johannes Fürnkranz. Preference- reinforcement learning: prelim- inary survey. In Proceedings of the FCMI/PKKD-115 Workshop on Reinforcement Learning from Generalized Feedback: Beyond Numeric Rewards, 2013.
[80] Christian Wirth, Johannes Fürnkranz, and Gerhard Neumann. Model-free preference-based reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence. volume 30, 2016.
[81] Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18 (136):1-46, 2017.
[82] Huasen Wu and Xin Liu. Double thompson sampling for dueling bandits. Advances in neural information processing systems, 29, 2016.
15

---

[83] Runzhe Wu and Wen Sun. Making rl with preference- based feedback efficient via randomization. In The Twelfth International Conference on Learning Representations, 2023.
[84] Yue Wu, Tao Jin, Qiwei Di, Hao Lou, Farzad Farnoud, and Quanquan Gu. Borda regret minimization for generalized linear dueling bandits. In International Conference on Machine Learning, pages 53571 13396.. PMLR, 2024.
[85]
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Hassan Awadal- lah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit q-- approximation for sample-efficient RLHF. In The Thirteenth International Conference on Learning Representations, 2025. URL
[86] Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. Forty-first International Conference on Machine Learning, 2024.
[87] Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference- based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18794, 2020.
[88] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed ducling bandits problem. Journal of Computer and System Sciences, 78(5):1538- 2012.
[89] Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimiza- tion and exploration with linear function approximation. In Conference on Learning Theory, pages 4473-4525 PMLR, 2021.
[90] Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline preference-based reinforcement learning. In The Twelfth International Conference Learning Representations, 2024.
[91] Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. Provable reward-agnostic preference-basee reinforcement learning. In The Twelfth International Conference Learning Representations, 2024.
[92] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. Advances Neural Information Processing Systems, 36, 2024.
[93] Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons, In International Conference on Machine Learning, pages 43037-4308 -3037-43067. PMLR, 2023.
[94] Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In International conference on machine learning. pages 10-18. PMLR, 2014.
[95] Masrour Zoghi, Zohar S Karnin, Shimon Whiteson, and Maarten De Rijke. Copeland dueling bandits. Advances in neural information processing systems, 28, 2015.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Abstract and Section 1
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
Assumption 1 and Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Secion 6 Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [No]
Justification: We have included the code in the supplementary material. After our paper is accepted, we will provide open access to the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https http://ooooSuuiisssodeee
//nips. //nips.cc/ppl wwcppblic/guticcccccccceee.oo.pe
wtt.SSbbbiiiiooooiiiii.oooi for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 6 and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Figure and
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
19

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:: httppp////aarro..ccco//////////a
Answer: [Yes]
Justification:
We comply with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: impacts.
This paper focuses on theoretical results and therefore does not discuss societal
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We will release the full code with documentation support reproducibility. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The study does not involve human participants sensitive data.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
22

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: We used LLMs only for writing and editing.
Guidelines: The study does not utilize LLMs in the core methodology or experimental pipeline.
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy http:///eerrrppp.cco/oeeeeeeeeee for what should or should be described.
23

---

Appendix
Table of Contents
A Further Related Work
24
B Notation
25
Proof of Theorem 1
26
Main Prool of Theorem
26
Proofs of Lemmas for Theorem
31
Proof Theorem 2
36
D. Main Proof 2
36
................................
D.2 Proofs Propositions and Lemmas for Theorem
................................
38
E Technical Lemmas
42
F Proof of Theorem 3
44
FI Main Proof of Theorem
44
F2 Proof of Lemmas for Theorem 3
47
G Additional Discussions)
48
Avoiding e Scaling in Regret Minimization
48
G.2 Extension to Active Learning Setting
50
Experimental Details and Additional Results
51
Synthetic Data
51
World Datasel
54
Limitations
56
A Further Related Work
In this section, we provide additional related work that complements Section
Logistic and MNL bandits. Our work is also closely related to logistic bandits and multinomial logit a special case of the MNL bandit model in which the agent offers only single item (i.e., K = at each round and receives binary feedback indicating whether the item was selected (1) or (0). Faury et (6 examined how the regret in logistic bandits depends on the non-linearity parameter of the logistic link function and proposed the first algorithm whose regret bound eliminates explicit dependence on 1/xc = ()
(MNL) bandits. The logistic bandit problem 23 26
42
Abeille et al. (2) further improved the theoretical dependency on 1/k and established a matching, lower bound. Building on this, Faury et al. [27] developed computationally efficient algorithm whose regret still matches the lower bound established by Abeille al. (2).
Multinomial logit (MNL) bandits tackle more sophisticated problem than logistic bandits. In- stead of offering a single item and observing binary feedback, the learner chooses subset of items- underscoring the combinatorial nature of the task and receives non-uniform rewards driven A recent breakthrough by Lee and (39 closed long-standing gap by providing computationally efficient algorithm that attains the minimax-optimal regret for this setting. Building on this result, Lee and Oh [11 further re- duced the regret bound by a factor polynomial in and logarithmic in K, and established the first variance-dependent regret bounds for MNL bandits.
by an MNL choice model [ 4 56 15
53
54 59
3 39

---

Our work extends the online confidence bound analysis of Lee and Oh [4 to the Plackett- (PL) model. This extension natural because the PL probability distribution decomposes into sequence of MNI. probabilities over successive choices. Crucially, we leverage their key insight- that the MNL loss exhibits an fe-seeff-concordant property eliminate the harmful O(eB) dependence. This is one of the main contributions of our work (see Lemma
RL with MNL models. Recent work has extended the Multinomial Logit (MNL) framework beyond bandit formulations to reinforcement learning. Lee and Oh 20 introduced combinatorial RL with preference feedback, framework in which an agent learns select subsets of items so as to maximize long-term cumulative rewards.
Another line of research incorporates MNL models directly into the transition dynamics. Hwang and Oh (29 proposed MNI--MDPs, a class of Markov decision processes whose transition probabilities follow an MNL parameterization. Building upon this formulation, Cho et al. [17 improved the regret bounds by improving the exponential dependence on B, and Park et al. [58 extended the analysis to the infinite-horizon setting.
B Notation
Let T denote the total number of rounds, with t [7'] representing the current round. We use N for the total number of items, K for the maximum assortment size, for the feature vector dimension. and B as an upper bound on the norm of the unknown parameter. For notational convenience, we provide Table B.1
For clarity, we derive the first- and second-order derivatives (i.e., gradients and Hessians) of the loss (
()) if i j. and Y 0 for functions. For the PL loss at round for the j j'th ranking, let ytu otherwise. Then, we have
exp (0(2,, ots) (1x01,01))
St yes
exp (Ø(xe, Tzi) TO)
(0) log
log
[ exp o() TT))
Sa kーj
exp (Øl ve, oexe TB))
=: ((())
15c
Σ
Bii log p(ù) (on),
()
[5cl Σ
1.0 (an) - (3) p(oe,
|8
|8g S11
(2)(0
Σ
Σ Σ
p(t) (on) (G)))(( p! (er)))((a o.))
ドー
1 |.l s.
Σ
Σ
plt (on) (1d Ma oth) (d(s), ((F1,
(j,)
For the RB loss round for the pairwise comparison between dtj and dek, let Vei (.k) = 0 for otherwise (i.e., when = k). Then, we have
if
and Vea
exp (0(z,, 0 log (6(2,, T + exp (0( T
(lA (
log / (0(1), - (1)) 1 0)) where n(w) 1 w-
1
veliiN( (0) (u((((1):))) p(z,, o()) 0) -1) (Ø(z), ((2x,
22 (0) = i ((o(ee) O(z, -(0) ow)) 0) (o(ve, (()) (0((),)1)) - (x)
25

---

Table B.1: Symbols
2,A,S
context (prompt) space, action (answer) space, assortment space
6(2,a) R"
feature representation of context-action pair (z,a)
:= ob sty) 0(zz, Ttk), feature difference between Stj and under context 27 assortment chosen by algorithm at round /
S:
(0)
log
exp(s(s..ae)"
PL. loss round for j'th ranking
Ft (xp(d(n
(0)
= log
exp()(x,,0))'0
RB loss at round t for comparison Ot
Limciia) explo(=s.
(0)
E | (xp((0lzn.oo)))00z..
2 exp(ols)..)))) 0))
V2cliR (0)
(=T) F where ((w) I+e-e is sigmoid function
online parameter estimate using Pl. loss round after j' update
0,5
online parameter estimate using RB loss at round t, after (j. k'tth comparison update
= =1 3V2)), step-size parameter
+O(dloog(K' (KT/8) (B + d)) regularization parameter
E. 1 v2 (1++))) Ala (or E. E Sk= V 2 (0.1at1)) ( + Ala)
H,
He + + E 22 (0 (for PL loss)
He 1 NE V (0(' (for RB loss)
B((8)
O (BBdloow (log(( (K/0) /0] BV confidence radius for 0, at round
{e e [2] max 16(2, a) a')ll,))lln 3 3vIK3r.1655
T
warm-up rounds
= E T8T 1 (I- 22( (0.) + Ala
M+
C Proof of Theorem 1
In this section, we present the proof of Theorem
C.1 Main Proof of Theorem
PL loss and OMD. We begin by recalling the loss function and the parameter update rule. Specifically. we use the PL loss defined in Equation
33) and update the parameter according to Equation (5).
exp (Ø(z,, Gea) T
(0)
log
(
(0),
1S k-j exp (Ø(I), own) TOO)
==1
(
and
o(1+1) argmin < (0 (0. 0)
0
0
j=
1=....,,1Sp |Scl
dc
21
where 0[1)+++1] ((1 and = [1 3/2B 2B) the step-size parameter. The matrix H.)) is given
by H1,0) = H, + n Σ 2
p2((5) (0(5)) where
S
He
2 20) (0++)) ALa
>>
Online confidence bound for PL loss. Now, we present the confidence bound for online parameter estimation in MNL models, as recently proposed by Lee and Oh 41
Lemma C.1 (Online confidence bound, Theorem 4.2 of Lee and Oh 41). Let 8 (0, We set 7 (1 + 3/2BB/2 and X max/12v221) 144nd, 2}. Then, under Assumption 1 with probability
26

---

at least - 8, we have
8--0% 0H. & (,( o 0 ( (Bydlog(t/o) + BBA)). vt 1.
We now extend this result to our setting. Since the total number of updates up to round t is Σ |Sa], the corresponding confidence bound can be expressed as follows:
Corollary C.1 (Restatement of Corollary Online confidence bound for PL loss). Let 8 E (0. 1].
We set = (1 + 3v2B)/2 and X max 12v 2Bn, 144nd, 2}. Then, under Assumption |
with
probability least 6, we have
10 0* mn Bx(8) O (Vllogtt//0) + BVĀ). Vt > 1,j < Sta
where HD)) = H. v 0 +1)) AI and 0.") θ:-
Useful definitions. For clarity, we write o (0) to make explicit that the loss function is random with respect the ranking a. When the ranking is realized as de, we simply denote by (0). We define the set of warm-up up rounds, denoted by T which consists of rounds with large uncertainty, as:
T t [T] max | o(ze, o(=z,,''ll a.) a,e'A
(C.1)
3/2K (1+
where (1) denotes the confidence radius as defined in Corollary C.I
Furthermore, we define the expected version of the Hessian matrix (taken with respect to the randomness of the ranking feedback) as follows:
M₁
Σ
Σ
E (.ss.
V2 (0.) Ald
(C.2)
sE[t-1]
Note that (
) is random matrix conditional the assortment Sg, where the randomness arises from the ranking feedback a..
Key lemmas. We now present key lemmas needed to prove Theorem I The following lemma, one of our main contributions, is crucial for avoiding the 1/k- O(e dependency in the leading term. Lemma C.2 to-exeecte Hessian lower bound). Let M, be defined in Equation (C.2) Ser A = (od (T)))). Then, for all E [T], with probability at least - 5, we have
He Z
3e Mr.
The proof is deferred to Appendix C.2.I
The following lemma is the elliptical potential lemma adapted to our setting. Lemma C.3 (Elliptical potential for expected mean-centered uncertainty). Let M, be defined as in Equation C.2 Let Pa(a s(5), O) denote the MNL probability for the subset of remaining actions in St after removing the first j actions according the ranking a. Then, for any X > O, we have
Σ min 7
1, j-1
Σ
E --1((-)) a P-(1s (11)))))00))
(olan,a) a~ P.(55 a. (. Mr
KT
2dg
dx
The proof is deferred Appendix C.2.2
The size of the set T is bounded as described in the following lemma.
Lemma C.4. Let T T { [T] max,,o'eA 10(# a) Ō(21, ) 1
3/2K (6)) Define
-6B Set À > Then, the size of the set T is bounded as follows:
T & 288K4
11 2KT
(7)
dA
27

---

The proof is deferred to Appendix C.2.3
We now ready provide the proof of Theorem
Proof of Theorem 4 To begin, we define a martingale difference sequence (MDS) Ça as follows: (x+, x (x+)) - & (r,, fr 0
G ::=Eu-up
(6 (I,, x" (x)) & (z, +r())) 0-
which satisfies
[Gr 2B. Then, by the definition of the suboptimality gap, we have
SubOpt(T) = Ex-p (0 (x, x (x)) o (z, a)()))
(1r, o (2,, mr (24 0- + T t=1
Σ
(Def. of (t)
T
1 T
T (0 (x))) - ( (2,, (0- 0r+1) ) +
Σ
S
T
(ar(2)) argmax p(I,, a) 0r+1)
(x)) - (2,, (z(())
(0- 0r-1) 0
1
(C.3)
VT
where the last inequality follows from the Azuma Huena--oe inequality. Specifically, for any T > with probability at least 1 8, we have
1 GE T -V88BT
1 (
log(1/)) Ô
To complete the proof, it remains bound the first term in Equation (C.3
T
(o (T T' (xt)
o (x).)r())))) (or -01+1)
T
Σ
(0t, (f (or - -ōTt1)
T
T
+
(1)))
(0* (0--0r+1)
T
4B
Σ
(6 (1 (x;) - (x,, (x,, ax())) (0- (0--0)+1)
(Assumption) !
T
BK
T
BT + 2
1+
(Lemma
KT
dA
Σ (ø Tt' (αx)) (xx)) - @ (2,, oo (xx))) (0--0)+1)
(C.4)
T
1F7"
To further bound the last term of Equation C..4. we get
1
(0 ((t,,"((2)))) (zx)) o (Nc, (r()))) T (or (0--0r+)
T
0-- 0--rr+1 Hr+1 (o ( (x n
(Hölder's ineq.)
Σ (2,,,, (z,)) o (r. (it
0" 0r+1 Hr+1
(Hr+1 H,)
(TT
BT+i (8)
Σ ( - o (x., (x))))))
T
#
(Corollary C.I with prob. 1 - 5)
28

---

Define the sigmoid function s(() 1 14e w. Then, we have
Σ b (It, x (x+)) - (zz, (r(x)))
Σ i (() (2, 0+)
177 is ((000larrrta))))tte(t
11 (2t, (1,, =<xx)) @ (rx, कr (x:))ll
-le, 0+)
(1 + e)² Σ i ((0( - (
(l xr(x,)) ) (2,, (x+)) - o (Ie, (n,
where the last equality holds due to the fact that
i (0), T (xx)) ① (01, Rr (211)) )' o+)
+ (4 0¹)
(
[1 + (o0l 00)²
(())) o (x(x)) 0 0)
(olen (4.) (0 -r1.)) (fT(z;) argmax o(or, a) θr+1)
1000000-000 1000000010100 br-1 2 (a))
(Hölder's ineq, and Hr+1 2 H,)
1 2
322K07+1(6)
(1 E T and Corollary C.1
(1 e/K3 (1 + c)
Recall that 56²) = (a Tss denotes the subset of remaining actions in S after removing the first j - 1 actions, given S and a. We denote the Multinomial Logit (MNL) model round / by Pi(a | 5:0) 0) (see Equation (9). Then, by our assortment selection rule in Equation (TT), we obtain
i (10 (2), (' - o (x,, Ar()))) 00)) (| (ar, ",,, =a(x)) - & (x,, 9r (r(())))
< i 7 (z)) ( (r (z),)))))) 0.) I (a)) (0. (0.-0*)
- (2,, ,, < e i ((0( o (z,, (x()) To.) (1 ar n
(Lemma E.2
(Eqn. C.5
[a-- H: [ _a
E
2
(a(2) =[= (d2)) and let S (z
c
(x (aaaa))--aaassss Ba ",,,0,,,,,,,,,,0,,,,,,, a')l
P. 0.)
H
(5 = 2)
29

---

where the second inequality holds since, for any t # T and a' E A, the following property holds:
(d(Ie))) a) d()), (0,-0-) 0²)
< 10 a) - o a')l 111 .10, 0' 1'
(Hölder's inequality)
0. 1'
T
W/2K3T+11
3e(5)
(Corollary C.1
(()+)16)
(C.5)
K
Combining the above results, we get
Σ #=
1 (Ites (x:)) Φ (Ze, (r())))
< <e(1 + 2
E (.()))))))
(olonna) -E 01 a' H.
(C.6)
14 T0
T
S
2 [ - E Plccss @. L, a')]
<e(1+e)
E
S1
S
11.1
(Cauchy-Schwartz incq., and T
1
[ a) E (1(( 0,) (T) a 11
<)(1+
E (.(...)))
|..1
7
Pa 0.)
(Assortment selection rule, Equation
11
T -
<
Σ
E .. 0.)
P.(-));00))
[((z).)) E p 0,)l a')
S1
#
(Eqn.
(C.7
S.
1
[o(or P (1 [d(s,, a']]
2
(1+
E r,((S,00) P ..)
S
Mr
(Lemma C.2 with prob. 1 - 6)
where the second-to -o-lstt inequality holds because, for any & T e S, and E S, we have
exp ()(Iz.))T))
P:(alS; 0.)
En's exp ((x,, a²) TO))
exp ()( o(xx, a)) 0,,
(any ā S)
1+ (e exp (66()), a') o( a)) 0.)
exp (()(2)))) 0(21, a)) 0 + +1/K)
(Eqn. CC.
E exp ((o(z), - o(5,, a)) 0- -1/K)
2 2/K P:(a)S:0'),
30

---

which implies that, for the ranking = (s))
|
Pr(a,15h & e² 1s|
(,(S:;;,
I (St, 0,) 2
P.lo,1sp):07 0*)
5=1 = =c(
j=1
(C.7)
Moreover, by setting X dlog I and T io eKid, for any t, we have
18c
[ -B Brsss o.) lo( d')
2K
Σ E ex((s.:0)) P.(- (.)
< 2.
(C.8)
MT!
Hence, by the elliptical potential for expected mean-centered uncertainty (Lemma C
obtain
Σ
(
(x+)) o (2 (x)) (0 -r
(8)
Σ
( x (xx)) @ (2e, Rr 2r (2:)))))
T
0
1r+1(8)
1
Σ
S+
E8 (.((s0)0)) (..)
((x),, -Ep p a)]l M.!
a
T
Sc
(r)
1
KT di
0
log
1+
(Lemma C.3 with Eqn.
(C.8
T
St
(r)
1
O
dloo (KT)
(C.9)
T
S
By combining Equations
and C..9 and setting Br+1(0) (BB/alog(KT) +
B)), we derive that, with probability at least 1 38 (omitting logarithmic terms and polynomial dependencies on B for brevity).
1
PK*
SubOpt(T)
St
KT
Substituting 5. we conclude the proof of Theorem
C.2 Proofs Lemmas for Theorem 1
C.2.1 Proof of Lemma
Proof of Lemma
C.2
Recall the definition of Hç-
IS
H,
(()+))) ALa Z
Σ Σ
(0++)) Ala
J=1
Here, we can equivalently express the MNL loss step j and round s, denoted by v2660 (( as follows:
exp (o(Ie, -0.itt1
exp (aوو)
(0++1)) - log
-log
118.1 k=j
exp (0 aosh T T6.5
|S kmj
exp (a.x)
=: (a()).
(C.10)
31

---

where asj 2( TT) 11 a
(aot) 18,1 E RIS.--i11,
Define the matrix
(zj)
$ ( ((18,))
E ER (R(SS.-++1)x
where each row corresponds the feature vector of an action ranked from position j to [S, in the
ranking a. Moreover, we define ãzح (xx;, 2 T 0, and a!!) (#ax) RIS.11++11
Then, using the -nom self-concordant property of the MNL loss 41. for any s E 17, we obtain
V Ve = -(5)))) V2 (2 $!!)
(Eqn. (C.10
3 3v (1) 8 (0!)) ((())
z e
(Lemma E.1
= 2
1
( 24 1
(aa (1) ab)
2 11:0 &
3/2
1 = ( 0.)
(Eqn. (C.10)
where the last inequality holds because, for any - T and j < [Sa), the following holds:
(a() 2 100 &
[bx ax) (0(k+1) (0((+))-@00)
0.)) -6)))
max k -=J....[s.l
oz) (1/ottt2)
0- 11,
+ 0. 0"
max h [S,
H.
(Hölder's inequality)
(oeutt)) 0-
+ 1 00 (s $ Tw, H, H (++
max
3v 3.25T++ k=j....S.l
H.
28r+1(0)
(Corollary C.1 (((8) is non-decreasing)
3v2Br+1(0)
2
3
Therefore, get
SS
SS 22 (2))) + Ala.
H, > Σ
Σ
2
2
1)
+
AI
>
Σ
se(t-
-e[t-I]TT3--
se(t
-ett-|| T
]-1
Recall the definition of the MNL choice probability D
exp (o(TT,, a) TT)
(a(aS::)) Evtss exp a')
Va E S.
Given S. (ax1..... } and the ranking feedback as we define s(3) (a.j...., 0.1.1)) the subset of remaining actions in S, after removing the first j 1 actions. For simplicity, let
32

---

p!0) P.(..5.. - 0.). Then, can express the Hessian of the loss follows:
()
1
|s.
|s.
exp (a( + (( 0.) Sul
ViL (0.) - Σ
Pakk Sahe
EE kk=
exp (((2))0())
osx) TT.)
|S
s..
(a (S (s) 2aha Zakk'
|8.1 18
1S.1
Σ
E
p2) xP0) (a
(0((x)))) -ale:aa))-la....
(l22, - -0(2, o(z). I
S.1
E ppo [
(6x),) BB [por =0,
(C.11)
where 2ske' o(z,, 0.k) 0(2,, x22). Therefore, E (2. is a random PSD ma- trix conditional on the assortment S., where the randomness arises from the realized ranking Ts. Note that the true PL distribution Pa(-|S,;00 0*) is measurable with respect to the filtration
F.-1
o [11, S1, Fz. Ss). Moreover, the maximum eigenvalue of the Hessian satisfies
Xmaa
(2)-11 2 (Q.))
K. Then, by the PSD matrices concentration lemma (Lemma E.3
with probability 1 - 8, we have
1S.1
H 2
Σ
Σ
(2
+ ALa
K
S.1
Σ
Σ
v2g (0.) + ALa
2²
K
SE(t 1
T
1 1Sal
K
Σ
E E.
Σ
2 22
(0.)
ALd
3c
K
(Lemma
E.3 with prob. 1 - 6)
S.
3c
Σ
Σ
E
(.S..00)
(p((i)(0.)
3.0
+ AI
3
1
Mr.
NE[t-1][T
1|
This concludes the proof of Lemma
C
C.2.2 Proof of Lemma
Proof of Lemma C
By the definition of Mf
C.2 and Equation C.I for $ T", we have
det (M++1) det
Mr
(-1S,.
(2
[8c1
det
Mr
Σ
E
a-
(1)
Pt (()(() (a)
(Eqn. (C.II
j=1
(11522)))))))
|s.
det (Mi)
1+
Σ
E o~ P.(.
(, (a)) No
pn (.1
1S.
| (a)l (ollaa- =11)
> det (AIa)
π
1 + min
1,
Σ
E a (-
"E(t]TT
j-1
a~ P. (-
33

---

where, for simplicity, denote (a) o(1x, a) E B 0.) 0.)l0(r,,)))
For T is clear that det (M++1) = det (M,)
Hence, using the fact that & 21og(1 + a) for any [0, 11, get
Σ min
1, Σ
E (')
[a)
j-1
a P((((11/220111
1sc1
< 2 Σ log
+ min
1, Σ I8 (-1,(-)),00))
|
#+
j-1
dett [det((Mrg (MT+1)
< 2 log
det (AIa)
4KT
$ 2dlog
dd
where the last inequality holds because
A1 +...... Ad
det (Mr+1)
(A,, dd eigenvalues of MT+1, AM-GM ineq.)
d
(race(Mr+1))
d
d
Ad D
(a)
<(x+
KT
1=1
x
(B 1
d
This concludes the proof of Lemma
C.2.3 Proof of Lemma C.4
Proof of Lemma C.4 Let
(āt, āe) = argmax e ((o(z),)) 0(2,, (( 6.) [Ø(21, o(Ie, a a')ll
a,a'tA
where x(w) Ite denote the sigmoid function. Note that, by our assortment selection rule in
III the two actions a, a' E A that maximize j (lō(22.)) - )(x),a)) 6.) | a)
Equation
6(2,, a I| H, are always included in S. It is because
" (((())))) o(x,, a') d')) 0.)) (o(0,, o(0,, d()
= 2E
((x)) - -E -B a')l
H,
| - -B -B P 10 e
2_.oPi(( 1.0) a>Pr(- (a,
2E
= 2f(((a, a')), H
which directly implics that ā, 0 S..
34

---

For simplicity, we denote 2okae 6(2s, - ((Ix: Then, by the definition of H,, we have
1-1 S.
H 0 AI
exp (0(x Tsk) + 0 )ow)) 0l:+2))
S. 19 s
Zakk Zshk' + Ald
S. k=j exp )ww)
2
1-1
Z + XL
2K
4B
(0(zz) k.) 6x (0(x), ā.) o(xe; ax)) + Ald
(ā,, E Sa)
2K
eAB
Σ (((((os,) - M(.. a.) 0O.) (0(x.) ū.) - 61 (.)) - 6( aa))
2K²
NET
+ AId
(C.12)
where the last inequality holds since j (()(zz, a) (((...')) a '0.) < J. In addition, we denote THe T Wi,, (t....,TT T3 in the last inequality. To better presentation, we define
A.
Σ (((5(t,,))) ((x,, k.)) T.) (0(x,, ā.) - o(x. a.)) (ā(r,,, ax))
SET,"
Ald-
On the other hand, by setting À > 1, for any i, we can ensure that
i (ll(z), a.) o(x,, a.)) 0.) 1Ø(2,, āx) - o(z,, a(x),,0)?
(Ap)
(AP)
- $
4 X
1 2
(i()) < D
1.
(C.13)
Then, we can derive that
Σ max ET
10( a) o00,, l'
(0(12), a) - M(x, a')) 0..)
te a.E j ((((2)) o( a()) 0, [6(x,,)) a) o(zr, d')
Σ max
< 2B
Σ
max ju a.eed
o(. - (..) 10(0r, a) p(1r, "
tET
(Assumption) I
2B Σ i (0(x)) M(x,, a.)) 0.) jo āz) - M(x,, de)l 2.
T
8 # (((()) o(ze. ac)) 0.) |1( ā.) o(xx az) (AP)
m
(Eqn. C.12
882268 68
Σ min 1 (0(2)), 6(2,, 06.) [10(21, ā.) 6(21, 12)
(Ar)
t
(Eqn. C.13
27
& 16K2 2 dl 1
(Lemma E.6
dA
35

---

On the other hand, for tt T we know that
Σ max 16(z1, a) 0(2x, H, 1r
T a.a'
By combining the two results above, and setting n. = c- we obtain
288K* (r+1(0)dloog 1+ 2KT
IT
dd
which concludes the proof.
D Proof of Theorem 2
D.1 Main Proof of Theorem
In this section, we present the proof of Theorem which is obtained by using the RB loss (4) instead of the PL loss (3). Note that this approach is based on the concept of rani-breaking (RB), which decomposes (partial) ranking data into individual pairwise comparisons, treats each comparison as independent, and has been extensively studied in previous works 6 34
32 67]. Moreover, this
RB approach is applied in the current RLHF for LLM (e.g., Ouyang et al. 57 and is also studied
theoretically Zhu et al. (93 under the offline setting.
RB loss and OMD. We begin by recalling the loss function and the parameter update rule. Specifically, we use the PL loss defined in Equation (4) and update the parameter according Equation 77)
| 1
exp (Ø(2), oty) T
|S.1-1
SS Σ
(((0) = Σ
Σ
log exp (δ(0), ott) 0) + exp (0(æ,, Oth) 0)
= j-1 k=j+1
Σ
(1)00(0)
j-1
(0)
and
@lik+1) = argmin (vel) ((().))) 0) + 27
0
0
p2
1Ej k < Sii
where if l-
[Se). we set 0(1++11)
0(++1.+22 and for the final pair, let 0(1.11-1151++)
(.))
Also, the matrix A((5.) is defined as A((m) =- H. + n ((yAEE)) x2pli'>0 (((''
where
1. IS
H =
Σ
Σ
+ AL
k-
1-1 -S [S.]
= Σ
Σ
Σ
i ((0(x))))) - p(0,, ok),, T Tobiet1))
()) Max, ov)) ( (2,, σz)) Max, (()), + ALa-
Online confidence bound for RB loss. Now, we introduce the online confidence bound for RB loss.
Since the total number of updates up to round is >xt (ls.)).. modification of Lemma C. yields the following result:
Proposition D.1 (Online confidence bound for RB loss). Let 5 e (0, 17. We set 1 = (1 + 3 3 2/2 and X = 2.2 144nd, 2}. If K2 & (2v6 + 12v3B)d, then under Assumption 1 with probability least 8, we have
10(1.) ( < B(() O (BVllog(k/0)++++ BVA). Vt 1, < < k < 18,)
where H(..A) H. + Σg villi x) ( ((1) + lL and 0(1.2) θ..
We write (F,K)) & (j,k) indicate lexicographic order. i.e. j j j' j and k' S k.
36

---

The proof is deferred to Appendix D.2.1 Useful definitions. We define the set of warm-up rounds T in similar manner the analysis of Theorem
1
T le [T] max 16(5), a) -0(,,,)) a,''
(warm-up rounds)
(T+(
Moreover, we define the matrix
A, Σ Σ is [[1-1]]7=a..0'S5. + AI
0.) (d(x), ((1). o(z,,
(D.1)
Key lemmas. The relationship between H, and A, is as follows:
Lemma D.1. Let Ne be defined as in Equation D.I. Then, for all t E [T], we have
H1 2 Ac.
2
The proof is deferred to Appendix D.2.2
The size of the set T is bounded described in the following lemma:
Lemma D.2. Let T {t [T]
a [,, a) o(I,, a') ll,
8r120)) Define
= 6B Set X / 1. Then, the size of the set T is bounded as follows:
32
2T dA
T
3r (8)
1+
The proof is deferred to Appendix D.2.3 Note that the bound on the cardinality of T is tighter than the loss case (Lemma C.4 by up a factor K" (and up logarithmic factors in K).
We are now ready to provide the proof of Theorem
We start from Equation (C.4), but apply Lemma D.2 instead of Lemma C.4 Then, with probability at least 1 8, we have
Proof of Theorem 2 The overall proof structure is similar to that of Theorem [
SubOpt(T) = Exup (00 (I, x- (x)) - (x, 0.]
(r-) (8) (1+ dx
B
7)
② + +0
(Lemma D.2
KT
Σ (0(n - o (z,, )r())))) (0r -Or-1).
+ 7
(D.2)
**
37

---

To further bound the last term of Equation (D2). by following the similar reasoning from Equa- tion (C4 to Equation (C.6), with probability least 1 6, we obtain
Σ 7
1 (2t, (2x)) (ar, (o,,TT((x)))) H.
el1 + e)²
Σ
Σ a,a's8;
ilbii(a, a') O.)) l,ri d')l
1T
(S; = { (xxe, (x()) and let v4(a, a') o(zr, o(x,,
<e + +)
T
Se
Σ
(V)a(a,a') (1a aa))l,
(ET
a,
(Cauchy-Schwand ineq., and T = [T]
T
< <e1+c)
Σ
(( II in
S
EET
a,o'ES,
(1+
Σ
Σ
a(vi((aa'' | (Lemma D.I
S
NT a,a'ES.
Moreover, by setting X dloog I and T' > kd for any we have
2K
Σ (( 0.) 1) A 2
(D.3)
a,e'ES,
Hence, by the elliptical potential lemma (Lemma E.6p. we derive that
Σ (0(2), a (1. fx(())) (0 (0-
(r) T
Σ
( x (xx)) - o (or, (fr())))
#T
V dog (KT)
(D.4)
T
St
By plugging Equation (D4 into Equation (D.2) and setting 8T (0) dllgdlog(T)))+++ BV
then, with probability at least
26, we derive that
d
SubOpt(T) δ T
S2
RT
Substituting - 2. we conclude the proof of Theorem
2
D.2 Proofs of Propositions and Lemmas for Theorem
D.2.1 Proof of Proposition D.I
Proof of Proposition D.I Since the rank-breaking pairs generated from the same set S, are not mutually independent, Lemma C. cannot be applied directly. Therefore, instead of Lemma C.2 of Lee and Oh [1I,, we use the following lemma.
Lemma D.3. Let 8 (0. We define pseudo-inverse function of pt (..)()) as u liik).+
R where lut (1.)):+(()))) (q)]: = log (1-1||ll))) for any q {p E [0,1] ||ppi <
1}. Let vela,a') a( ((I,,a)), and the intermediary parameter denote z(i.k)
38

---

Mt (.. (Bo ( (We(o,,ou) T0)) where p(1.)) N (olitt, .cHi , is a multivari-
normal distribution with mean 8, we have
k and covariance cH, (c> > 0). Then, for any e [T], with
probability at least
Σ
Σ
C (1)) - -2., K(K - 1)
log 8
2
jzk S.al
where E((z) = -log [+exp(=)
exp(x)
The proof of Lemma D.3 mostly follows the analysis of Lemma C.2 in Lee and Oh [41]. However, unlike their setting, the rank- breekbbe pairs generated from the same assortment St are generally dependent. Therefore, instead of applying Ville's inequality (77] to individual pairs, we apply it at the block level, where each block corresponds to one round t, by aggregating pairwise likelihood ratios through mixture construction. This preserves the supermartingale property and allows us to obtain the desired bound.
Proof of Lemma D.3
For simplicity, we write
Pt (i.)) == == (1.M)
ow) ow) and p( ; E Eon [4 (u( (u
(x) TO)
We define
plank) (x((2)))
M Σ
(5il) exp ((())(0)) plick) (2(1
1
Σ
(15.)) Dt p(ob)) (y(ia)))
(ia))
j<ke|se1
Jske|sel
(1.8) (y,( = (p.
pf ((an)) 1- x
where pt:
Then, we have
ki. (y(5
B[Me| F,
E
Fr
(v)
ps p(iik (x)())))
Se1
j- S. (e
Let A, == _ M, and Ao := 1. Then, it follows that (At)sa is a nonnegative supermartingale with respect to the filtration F (22 S1, ... ((,
Hence, following the analysis of Lemma C.2 in Lee and Oh 41 and applying Ville's inequality, we obtain that
1
P
sup A, Sup
< E[AoJo 8,
(Ville's inequality)
c
which is equivalent to
1 log Mo > log 8)
IP 3t: Σ
<d.
s-1
Therefore, with probability at least 8, we have
Σ Σ (00)))(0)) - -Z() (=(.)))
K(K- 1)
1
Σ
(())))(0))) (2.
2
(Aal)
jick
K(K- 1)
log M2
(Jensen's inquality)
2
K K(K 1)
1
log 5"
2
This concludes the proof of Lemma D.3
Now we follow the proof of Theorem 4.2 in Lee and Oh [4], with substituting Lemma C.2 of theirs with our Lemma D.3 then, we obtain that
1 3/2B
1+3v2B
1-
1pfii &
K(K 1) log - + 4v6
dlog(tK2 + +2) 4B22 (Let K2 < (2 12
2
= (B&d (lg((((8)) + B²
This completes the proof of Proposition D.I
39

---

D.2.2 Proof of Lemma D.1
Proof of Lemmn D.7 Recall that, under the Bradley-Tery-LLue (BTL) model defined in Equa- tion 2) the probability that action is preferred over action a' is given by:
exp (o( a) '0
P (a > m2; 0)
exp (o a) 0) + exp (6(z), d') 1 ((0(2)))) o(ze, TO).
Then, derive lower bound on the matrix H2 follows:
H
( + ALa
k-j+1
|S
Σ
<2glin) (1()++)) + Ala
:E|1
T
k=j+1
|s,1-1 |S
Σ
Σ
Σ
A O(iAAt)))))
Fak T ZngNZ
+ Ald
SE -
TT j=1 Kーj+1
|8.1-1 SS
i 0.) e (o znjke + Ala
Σ
Σ
Σ
(Lemma E.2
EE
- j=1 K-j+1
| |
2
Σ
Σ Σ (23)k0.)
ZnjkZzjk + AL
sE[t-1] 1|
k-j+1
2
At
2
where the second-to-last inequality holds because, for any Tw, the following property is satisfied:
=zju (0(.*+1) -0.) (0(x.) )ny) p( sx)) (0(+++1) -0())+1)-6.) 0.)
< |0(xs onj) - @l Ron) HJ (10(ihtt11
00 + 11 - -0-1 101
H.
(Hölder's inequality)
0- -0 (1lleeee + 110 - 0"
(0)
H.
(s * T H2 3 H().tt1)
283+1(0)
(Proposition D.I and 3:(6) is non-decreasing)
(r)
2.
This concludes the proof of Lemma D.I
D.2.3 Proof of Lemma D.2
Proof of Lemma D.2 The proof follows the same structure as the analysis of Lemma C.4 with the main difference that we use the Hessian corresponding to the RB loss. Let
(ā,, ae) = jrgmax ((o(x),)) o( d')) 0.)) [ a) M(x,, a' a')ll,,,""
a.a'EA
By the assortment selection rule in (TT, the two actions ãe, are always included in S,. is because, for any pair (a, a²} we have
j ((((z)) ol2,, d')) 0.) [| a) o(),, =ff((aa a')),
which directly implics that ā, a S..
40

---

For simplicity, we denote Sskk" 0(ts ((t)) Recall that by the definition of H,.
1
H
V
V +
ala
k=j+1
48
-1
Σ
Σ
2zjk2 + Ald
k=j+1
4B [-1
(0(z,, ū.) (x a.)) ( (0(0s, ū.) o(F.. u.)) + Ala
(ū,, E Sa)
4B
Σ İ ((b(os, o(E,, 0.) (0(z.: ā.) 6(12, (o)os,, o(Ex: (()):
T
+ AId
(D.5)
where in the last inequality, we use the fact that ií(-) < 1 and let 7," = T (t.,, Define
Al
Σ ù (((6(I.)))) o(x a.)) 0.) (o(x), ā.) ((T.) (d) (d( ((xx,,a))
SET?
ALd.
Furthermore, by setting À b 1, for any t, the following holds
ju ((0(z), a.) ((x),a)) 0.) 10(21, ā.) - o(x,, a.)1
1 2
(a(1) < 2
(Ap)
(Ar)
4 X
1.
(D.6)
Then, we obtain
Σ 17
max (Ø(x):)) 10(0,)(,00) a')l A
i (((or)) M( a')) T0.)
Σ max t a,e'E
i (o( o0 d')) 0.) |1( a) - a'));
& 2B
max ((0(0),)) a) - (()), 6.) (l0(r);0) - pl al) )1
1e a,t'A
(Assumption) I
2B Σ j (1) o(0, az)) 6.) | o(xx a()1,))))?
6B Σ i (o(z), Mx az)) 0.) (o(o) ār) o(rr, a av))(1>)
(A7)-
(Eqn. D.5)
T
Σ min { 1: (((())) -((, 0.) |1o ā.) ol ae)
16.
(AP)
-1 (D.6)
T
(Eqn.
2T
< 32c doog
1 +
(Lemma E.6
dx
On the other hand, for T we know that
7
Σ max [ a) ((2x,,001 H.
a.''A
(8)1
10
By combining the two results above, and setting K = 6- we derive that
32 IT & B (7+(
1+ dx
2T
K
which concludes the proof.
41

---

E
Technical Lemmas
Lemma E.1 (Proposition B.5 of Lee and Oh 41). The Hessian of the multinomial logistic loss
L:R. - R satisfies that, for any a1, E RRM, we have:
3v2/ai oo v (2(((a) 3 (((( = 3 aal (()(
Lemma E.2 (Lemma Abeille et al. 2). Let f be a strictly increasing function such that l.f] & f. and let Z be any bounded interval of I.. Then, for all Z1, E 2, we have
f(22) exp (-1 21) & f(2)) & f(22) exp (|22 21))
We also provide a concentration lemma for positive semi-definite (PSD) random matrices.
Lemma E.3 (Concentration of PSD matrices). Let p4 denote the conditional distribution of positive semiidefinite M R. dxd conditioned the filtration Fi-1. Assume Amax (M) & 1. Define M 1 M. If X = lo((n)()))) then with probability at least 6, for any n ž 1,
(nM + Aao) z Σ M4 + ALA
(n. + +Aa)
Proof of Lemma E.3 The overall structure of the proof closely follows that of Lemma 39 in Zanette et al. 189). For completeness, we provide the full proof below.
Fix E Rd such that | = 1. Let M, = EM M and M = - M, Then, we have
EM-H x Mæ = x. T EM Mx = x. M5æ.
Since M is positive semi-demmeeeeeeeeeeee definite matrix, the random variable x Mæ is non-negative, and it satisfies Mr Amax x112 1. Thus, the conditional variance is at most xf M,r because
Varm~n (x Mx) & EM-nA (x Mx)² & EM- Mæ = x M,T.
Applying Lemma E.4 with the filtration Fs, we obtain that, with probability at least 6, there exists universal constant such that
n
1xx 2oTMMe Ma
log(2/8)
x M.. LJ Max)
Mxx T Mæ Ec
log(2/8) +
r
m2
n
3n
Now, we will show that A alog (1/ 1/8)), we can derive
2x Mæ
log(2/0)
1
A 2
log(2/8) +
x
Mx
(E.1)
n
3n
2
12
Case 1. T Mxx & A In this case, is sufficient to satisfy for some constants c',""
2log(2/6)
2(log(118)) & X
7
n
log(2/8)
d"
2(log(1/8) & A.
3n
Case 2. x. Mæ A In this case, it is sufficient to satisfy for some constants " "
2x Mx
A
log(2/8) & "
((log(1/8)) & X
7
log(2/8)
A
& ""
(((og((188) & X.
3n
71
42

---

Therefore, Equation EEI1 is satisfied. Since | < 1, this implies
12 Σ n
x
M,
M
x $ 2"²
M
n l
(E.2)
We denote the boundary of the unit ball by 2B = <||0r| 1). Then, for any x E 2B, we know there exists x' in the e-covering such that [ by the covering number of Fuclidean ball lemma (Lemma R..5 p. we get
22|12 -r>x'll
Let N. be the e-ooeernng number of AB. Then,
3
N₂
(E.3)
Taking a union bound over x' and the number of samples n, with probability least 1 nNod, we obtain
M M
x 8
(2))
M
M
x
+ (x
(x==x))
M₁ M x
71
1 n1
(z))
12 Σ
Mj M
(x x¹)
(x/)
Σ
M4 M
+ 4e.
71
(x- 2'112 & and Mj || & 1)
1
> Ii
(2))
M
+
x² 4c
(Eqn. E..2)
2
n2
9
2
M
n
Ia
x.
2
(xx x-1= E e and | E 1)
2
M x.
(set c (
3
n
where Ω (log
2nAV.
)). By substituting 8 8/(nNV + 1) and combining this with Equa-
tion E.3 we obtain:
5 M M+ n Am
M
La
Mc +
Ia s
3
n
n
n 3
which concludes the proof.
Lemma E.4 (Bernstein for martingales, Theorem I of Beygelzimer al. [0]and Lemma 45 of Zanette et al. 19). Consider the stochastic process {X,} adapted to the filtration {F,,). Assume E.X,, 0
and eX2, & 1 for every n; then for every constant 2 + holds that
N
1 2
Pr
Σ
Xx
Σ
1
E
Fr)
log 3
1=11
1=1
By optimizing the bound as a function of we also have
N
N Σ
1
Pr
Σ
X
B(X2
Fn)) log J + log x
2 1.
Lemma E.5 (Covering number of Euclidean ball). For any > 0, the e-covering number of the Euclidean ball in Rd with radius R > 0 upper bounded by (1 + 2R/e)²
Lemma E.6 (Elliptical potential lemma Abbasi-Yaun Yadkori et al. I.. Let {21]12 be bounded sequence
in Id satisfying max || & X. For any t 2 1, we define A, == E 2027 ALg with À > O. Then, we have
T
X2T
min 11 1 A,1 & 2d 1
d)
43

---

Proof of Theorem 3
E.1 Main Proof of Theorem
Throughout the proof, we consider the setting where the context space is a singleton. i.c., A' = {2)]- As result, the problem reduces context-free setting, and focus solely the action space A. Note that this is equivalent to assuming that is Dirac distribution.
We first present the following theorem, which serves as the foundation for our analysis.
Theorem F.1 (Lower bound on adaptive PL model parameter estimation), Let $ 8 1 be the unit sphere in Rd, and let θ = (-p, μ1 for some μ E (0, 1/vdj. We consider a query model where, at each round t = ,,..., T, the learner selects a subset S. S & of feature vectors, with cardinality satisfying 2 < [Sp] & K, and then receives ranking feedback os drawn from the Plackett Placket-Luuce (PL) model defined as:
S.
exp
P(o 0)
exp Fo 0)
j=1
where or (ou..... (ss..)
is a permutation of the actions Se, da denotes the feature vector associated with action a A in the selected subset at round f, and O E O. Then, we have
[10 0 0
du²
(1 (1-1 2K?TH²
inf max Egg 0. AEG
where the infamum is all measurable estimators ô and measurable (but possibly adaptive) query rules n, and E.[.) denotes the expectation over the randomness in the observations and decision rules if 0 is the true instance. In particular, if 8K2, by choosing μ /dd/=///KKT)) obtain
d²
d2
inf max Eeg 0,7 OEE
||e 0
З2КºT
Proof of Thhorem F.7 The analysis of this result closely follows the proof of Theorem 3 in Shamir 73.. The key distinction lies in the input structure: our setting involves a set of feature vectors, while theirs restricted to a single feature vector.
To begin with, since the worst-case expected regret with respect to 0 can be lower bounded by the average regret under the uniform prior over θ we have:
max Egg 0c0
|0
0
En-
|10
0 0
0 0)
Σ 110.0 0.0 < <0)
> 1 Eg Eo-
(F.I)
As in Shamir [73), we assume that the query strategy deterministic conditioned on the past: that is, S, is a deterministic function of the previous queries and observations. i.c., 51,01.-. ......... St-1, This assumption made without loss of generality, since any randomized querying strategy can be viewed distribution over deterministic strategies. Therefore, a lower bound that holds uniformly for all deterministic strategies also applies to any randomized strategy. Then, we use the following lemma.
d--1-
Lemma E.1 (Lemma of Shamir 73). Let be a random vector, none of whose coordinates is .... .r be sequence of queries obtained by deterministic strategy
supported on O, and let y1, .2..... returning point 0 (that is, tbe deterministic function of 1b,, 1,,00 ...... 11 1t-1, and O is deterministic funtttooo of "1,..., WT). Then, we have
Σ 1 10,0000 < of
d
Eg Un)f(O) Eo
1-
ΣΣΣ1
Ue
i=1t_
44

---

where
Un = sup DeL (P(())0;> 0, 0, (v6)==1) P(u P(u
< 0, <m. (v))=1))
0,
In our setting, we interpret y/ Tt. and tb. = Maafaes, S Φ. Then, we can write Us as follows:
Uni
sup 0zJti
DxL (IP (o, S 0; > 0, (0)))tm))) (o, 02 < 0,10))ims))
For simplicity, let (o( = P (a 0). Then, we can upper bound Un, using the following lemma.
Lemma F.2. For any 0, 0 e R let Po S) denote the PL distribution over rankings induced by the action set S and parameter vector 0. Then, we have
DRL (P
< 2
K
Σ (0) (())
asS
The proof is deferred to Appendix F2.1 By applying Lemma
we have
K
UB
(2 [boli)²
2K
Σ (laol)
nES
2 1SA1
(0. E Sd-1)
2K²
(S11 & K)
Hence, by Lemma F.1 get
En-Unif(() Eg
Σ
d
I
0,0, <
<0}
3
1
Σ
d
Σ
T
Un
2
d
2K2T
(F22
d
Combining Equation F1 and F2 we prove the first inequality of Theorem
F1
The second
inequality directly follows by choosing (d/(8))T).
We now ready present the proof of Theorem 3
Proof of Theorem 3 The structure of our proof is similar to that of Theorem 2 in Wagenmaker et al. 78 However, while they consider the linear bandit setting, we focus the Plackett Luce (PL) bandit setting.
We adopt the same instance construction as in Theorem F1 where + Sd-1 and Q {-1, 14)d Define ø² (0) argmax o 0. Then, since s²(O + and 0 e 4, it is clear that
(A) 0/[|0||2 = 0/(v 8/(vdp), and o" (0) vdu.
(F.3
Fix the suboptimality gap > 0. By definition, policy π E A& is said to be e-optimal if satisfies
E
O T
E (0] ) To (0) T 0 = vdu
(F.4)
Moreover, by Jensen's inequality, we have
| 13 < ESnT [11011]] = 1.
45

---

Let A 0x (0). Then, we get
1> Ox (0) +A12
| (0)
(0) $ - | -111111
dp
0'
|
(Eqn. 113
Hence, if a policy æ is e-optimal for a parameter 0, then the following bound holds:
Vdu
|
(Eqn. (F.4)
2c
|
where O = Vdpl0> A).
vdp
We now assume that given c-optimal policy f. Define c: = Φn and the following estimator
0- 0'
if 30' E θ with 0' ddul A') for some A E R 1A'1 &
2x
Vap
any 0' e
otherwise.
If f is indeed e-optimal for some 0 O, then the first condition is satisfied, and have:
0 10-012 -V A - vdu(ō A)1l2 2vdu
2c
V8vdue.
(F.5)
vdp
We denote & as the event that â is e-optimal for A E O Then, we get
Eg 00 0 | = Ee |10 01 118) + 0 118)
8V ddue Eo [ -0- I(E*)
(Eqn. F55)
& 8vduee 2d,² Po[89.
(max @ 101 < du²)
On the other hand, by Theorem F.1 there exists a parameter 0 θ such that, if we collect T samples and set μ (d)38T then the following lower bound holds:
d²
Eo 1
0
З2K²T
To satisfy both inequalities, we require:
2de
d²
d² 32K2T
Po[E")
VK²T
4K2T
4 4.2KVT
PolEq
8
d
It follows that if
4 4/2K > 0.1
0.025 de
K2 T.
8
d
32
then have that [8[89] 0.1. In words, this means that with constant probability, any algorithm must either collect more than c k²22 samples, or output a policy that is not c-optimal. This implies
that Q d² x²22) samples are necessary to guarantee an c-optimal policy. Equivalently, after T rounds, the suboptimality gap c is lower bounded as
d
SubOpt(T) Ω
KVT
This concludes the proof of Theorem
46

---

F.2
Proof of Lemmas for Theorem 3
F.2.1
Proof of Lemma
F2
Proof of Lemma F22
By the definition of KL divergence, we have
Is
|S| 8 0
Kーj %
DEL (Fo( = (-
t (0 0) - -log
(F.6)
C 0¹
kーj
Fix a stage j and ranking a. We define
exp
Por 0
Pk (0) ==
where k' E ;
Σ
exp (oT, 0)
which corresponds the Multinomial Logit (MNL) probability of selecting action dy position given the parameter and the choice set S. Moreover, we define
18
((0) log
ook
Then, by applying the mean value form of Taylor's theorem, there exists 0 (1 - c)0 + c0' for
some c (0, 1) such that
e )
log
O f(0)) f(0)
|s|
1
Voi(O)T (0' -0)
0 0) Val(O) (0' 0)
(Taylor's theorem)
2
S
Vof(O) (0' - 0) 2
(0) (Ø), (0' 0))²
Pk
19 (0)0 (0' - 0) + 2 oES
Σ
(o_ (0' - 0))²
(F.7)
where the first inequality holds because
T
[s]
18]
[8|
Vor(0) pk 0 10
Σ
Σ
Pk 0 Do
Σ
Pk 0 Doz
Pk
0 do TT.
Plugging Equation
F7 into Equation F.6
we get
DKL. (Po(
IS
$ E. Ea-Po(-1s)
④ 0 0 0¹
Σ
pk
( (0 - 8¹) Σ (0 - 0))*)
Eo--P((1s))
P0 0 0¹
(0) (0 00) 0 01...., 0ー-1
(Tower rule)
[S|
Σ (8T 0))²
2
S
<
K
6 (0' 0))
(S) < K)
2
aE
which concludes the proof.
47

---

G Additional Discussions
This section provides further discussion of approach. In Subsection G.1 we show how it extends to the regret-mininization setting and improves the existing O(e²) dependence. In Subsection G.2 we describe how the approach also applies the active-learning setting considered in [9]
G.1 Avoiding R Scaling in Regret Minimization
In this subsection, we show that our technique for eliminating the OeeB) dependence in the leading term-prinn term-primarily by dividing the total rounds into warm-up and non-warm-up phases can also be applied in the pegrettminimization setting (e.g., Bengs et al. 9).
First, we formally define the cumulative regret as:
T Regr = Σ (ro- (Iz, 1T' (x+)) max max (2), a));
aeS;
where the contexts 24 can be given arbitrarily (in contrast to the main paper, where they are drawn from fixed distribution). We assume the linear rewards (Assumption T as in the main paper. Moreover, we use the RB update rule (Procedure ( in this subsection.
Next, we define
gc(S)
Σ (1é(z),)) (z2, (()) (0(()) 6(1, S
1
where à argmax A 6(x,, a) 0.. The quantity measures the average uncertainty between the feature vectors of actions in S and that of the current best action â,-
T
We then select the assortment S, in greedy manner, following the procedure in Equation (T... We initialize (āz), and subsequently add actions one by one. Specifically, at each step, we select
a" E argmax A.(a S), where (a S) (S S {at) (S), AEA
(G.1)
and include a" in S if (a a non-negative gain. Since ge ((ā,)) 0, this rule guarantees that the selected set satisfies |S|| 2.
8) 3 0. The process continues until either | = K or no action yields
Theorem G.1 (Regret upper bound). In the same setting as Theorem 2 suppose T 3 Kid, Then, with probability least 1 - 6, the assortment selection rule in Equation (..)) combined with the RB loss update strategy (Procedure 2}, guarantees
d
Reg
d
Σ
Proof of Theorem
G.1
By the definition of the cumulative regret, we have
T 0.
Regr
(x t5 (xx)) max (xI),))) oES,
(0(2,, " xxx)) 6(11; 0"
(a. S.)
(0(2), (zx)) 6(11, ( 00)
(ā, (= argmax o(zr, T T.)
48

---

Recall the definition of the set of wa rounds, i.e., T = {t E [T] max (1((z). 6(2,, a' dH 1/Br Then, we get
Regr $ 4B
+ Σ
(f (xx)) 2(22, ao)) (0' ( 00))
B 31+1(0) (6) doog 1+ di
00
Σ
1 ''''''''"))) (x1)) o(z a+)l H, 0 O He
(Lemma D.2 and Cauchy-Schward ineq.)
00
B (1)
h Br+
1+ dd
)) (r(
T)
Σ
| x (xx)) 6(2,, A.
(Proposition D.I
For simplify the presentation, let (s, = o( a) a'),, Then, for t $ T we have
[1 (otr)_a)) 2
1
A (We (1))) Tz)TTa 0r)
we (o.) 00
(v)()")))) > 0)
(1 (0- -0))
( (ā: == argmax o(I2, T..)
1 + (1((("(ww))e)) ( 10-:10--011 -0
2 < 1 e 3r.
& (1 (1+
(1 T and Proposition D.I
Therefore, the same line of reasoning used in the proof of Theorem applies here well.
Σ pa क > (2x))
T
< e( e)
Σ
Σ
i (v)((a (()((a,
(S² = (x+)
S
TT
neSt
<e(1+e)2
Σ (v)((a,a)) (v, iz,
(a))),))))
S
St
T
RES;
(Cauchy-Schward) ineq.. and T S (T))
< <e(1+e)
1
Σ DES,
ú(vr(a, T.) [1)c(a,a.)))..
Sc1
LET T
T
& V2e2(1 + c)²
Σ 1FT aeS.
Σ (()l(a (,((a,))))
(Lemma D.I
Se
1 S
Vllog (KT)
(Lemma E.6
where, in the last inequality, we introduce E, = =E EoEs, i (v) vela @e)a( T ALa, and use the relation H, A, 1 (A, is defined in Equation (.. In the final equality, we apply the fact that if dlog and T 2 kid then, for any t,
2K
(.) l a.) a.)
A $ 2.
49

---

Therefore, using Br(6) OBB dlog (KT) + BVX), we obtain, with probability at least 1 - 6,
I
d²
Reg7 = δ
d
Σ
+
St
K
This completes the proof of Theorem G.
G.2 Extension to Active Learning Setting
In this subsection, we consider different the learner has access to the entire context set X' and the objective is to minimize the following worst-case suboptimality gap, defined as:
referred as the active learning setting-whers -here
WorstSubOpt(T)- max [re- (I,, (x))x(()) ro- (2r, {x))]]
This setting has received increasing attention in recent work [0 most existing approaches focus exclusively on pairwise preference feedback. Mukherjee et al. [49 study an online learning-to-rank problem where, for each context, fixed set of K actions is provided. and the goal is to recover the true ranking based on feedback over these K actions. In contrast, we consider more general setting in which, for each context, set of N actions is available. The learner selects at most K actions from this set and receives ranking feedback over the selected subset. Thekumparampil al. (76 investigate the problem of ranking N > items using partial rankings over K candidates, but under context-free setting. In contrast, we study stochastic contextual setting, where contexts are drawn from an unknown (and fixed) distribution.
49 76 38 However,
In the active learning setting, the algorithm jointly selects the context z,-which is no longer given but actively chosen-ann and the assortment S, by maximizing the average uncertainty objective. For each candidate context it first constructs the assortment S,(x) by solving Equation (TT). It then selects 22 argmax (x))) and sets S, Sxx)).. The rest of the algorithm proceeds in the same manner as Algorithm
For simplicity, we focus on the RB loss and its corresponding update rule (Procedure D Then, can obtain the following bound on the worst-case suboptimality gap.
Theorem G.2. Under the same setting Theorem rule for (It,S) described above achieves:
2
with probability at least 1 ö, the selection
WorstSubOp((T)= = T
Sp
RT
Proof of Theurem G.2
By the definition of the worst-case suboptimality gap, we have
WorstSubOpt(T)
max xe (o (x,x"(())))))))) o (z, 0
n (5 (00 0r+
max sEi
(f)(x) = argmax aF a Ø(I, a) T0r+1)
1 T
Σ max (0 (x) 6( ()(()) (Ø* (0--0r+1)
T wedt
We adopt the same definitions for T = {t E [T] max / - p(0,, ((or, > 1/8r+1(8)) Thus, get
1
( (2, ( (x)) o (z. (t(()))) (0--
max NEN
T
80+1 (0)2 (1+ (1+dx) dx )
0
(Lemma D.2
KT
+ T
Σ
max TE
(0 - o (z, f((()) (0--0++))
(G.2)
50

---

Instance 1, PL Loss, K=2
Instance 1, PL Loss, K=
Instance 1, PL Loss, K=5
088
Subbpt. Gap
0.6
0.6
DosclWeli Unifomn
4-4
0.44
Instance RB Loss, K=2
Instance RB Loss, K=3
Instance 1. RB Loss, K=5
0.8
9.00et. C50
DepetWette Unitemm BeetSBef
SubDpt.
M.ALPO
0.2
0.0
75
100
125
150
175
200
0.0
25
75
100
125
150
175
250
0.0
25
50
100
325
150
135
200
Round (1)
Round (U)
Round (1)
Figure G.I: Performance comparisons for Instance (Stochastic contexts) with K 2, and evaluated under the PL loss (first row) and RB loss (second row).
To further bound the last term of Equation (..2. we get
max
(
(1,
o ((, (or (0- -r0rt))
Σ
max ssd
HJ 100000000 -0+1
(Hölder's ineq.)
Hrl1
#T
BrI1 (0)
max
|0 o (I, tr (
T
(HT+1 2 H, and Corollary C.I with prob.
5)
H, It therefore suffices to bound E, | (xrz, n² (z:) (zf Rr(+))) n- From here, the argument as in the proof of Theorem) applies, with the only modification that the procedure now selects both x; and S.. This completes proof of Theorem G.2
For simplicity, let x = argmax, 1 (z, n"
H Experimental Details and Additional Results
H.1 Synthetic Data
Setup. the synthetic data experiment, we sample the true but unknown parameter O* Rd from d-dimensional standard normal distribution, i.c., 0* ~ (O, and then normalize it to ensure We consider four different types of context sets X':
| 22 &
Instance (Stochastic contexts): For each x X, the feature vectors Φ(x,) :) are sampled from a standard normal distribution and then normalized to satisfy || x. 1)12 & 1. Here,
|x| = 100.
2. Instance 2 (Non-contextual); A single shared context is used for all rounds, i.e., = {a ) and | = 1. The corresponding feature vectors ((x1, :) are sampled from standard normal distribution and then normalized to satisfy (0(21, )||2 & 1.
3. Instance 3 (Hard-to-learn contexts): For each X. the feature vectors ((x,,) are constructed such that most of them are approximately orthogonal the true parameter 0* Here, X 100.
51

---

4. Instance 4 (Skewed stochastic contexts): For each x E X, the feature vectors o(x, -) are sampled in skewed or biased manner and then normalized to satisfy (o(z, -)l2 & Here, | 100. This is our main experimental setup in Section 6.1
Additionally, we set the feature dimension to and the number of available actions to |AA| N 100. The suboptimality gap is measured every 25 rounds. All results are averaged over 20 independent runs with different random seeds, and standard errors are reported to indicate variability. The experiments are on a Xeon(R) Gold 6226R CPU @ 2.90GHz (16 cores).
Baselines. We evaluate our proposed algorithm, MUAUPO, against three baselines: (i) DopeWolfe 76 a method designed for con-contextual K -usubet selection; (ii) Uniform, which selects assortments of size K uniformly random; and (iii) Best&Ref, which forms a pair of actions ().S.) = 2) by combining one action from the current policy with another from reference policy (e.g., uniform random or SFT), following the setup Online GSHF [66 and XPO
85
When using the PI. loss-based update in our algorithm, M-AUPO, the exact expectation over rankings computationally expensive. To mitigate this, we approximate the expectation via Monte Carlo sampling with 5 samples. Consequently, the computational cost of the PL-based approach is higher than that of the RB-based approach (see Table H.
Thekumparampil et al. 766 propose D-optimal design approach for the PlackettLLuce objective to efficiently select informative subsets of items for comparison. Recognizing the computational complexity inherent in this method, they introduce a randomized Frank- Wolfe algorithm, named DopeWolfe, which approximates the optimal design by solving linear maximization sub-problems on randomly chosen variables. This approach reduces computational overhead while maintaining effective learning performance. However, their approach is specifically tailored the single-context setting (e.g., Instance 2) and may not generalize well to the multiple-conten scenarios (e.g., Instances 3, and 4). While their original implementation updates the model parameters using maximum likelihood estimation (MLE) procedure, we instead adopt an online update strategy (as described in Procedures I and to ensure a fair comparison across all methods. For sampling size parameter Rt we set R min { (x) 100, 000).
The uniform random selection strategy. Uniform, selects K actions uniformly at random from the available action set A at each round, without utilizing any uncertainty reward-basce information.
Best&Ref constructs an action pair ([S:l 2) by combining two distinet sources of actions. The first action is chosen to maximize the current reward estimate, while the second is sampled from reference policy-such as a uniform random policy or a supervised fine-tuned (SFT) model. This pairing mechanism follows the framework introduced in Online GSHF [86] and XPO (85, In our experiments, we use the uniform random policy as the reference.
Performance measure. Since computing the exact suboptimality gap is challenging under general distribution p. we instead evaluate the realized regret, which serves as a slightly relaxed proxy for the suboptimality gap.
ò (
SubOpt(T)
$ T (o (TI, o (2, (o(,)r)()))) +
by MDS
(g (I,, TT (z,, mz()))) +0
T
(T))
-crealized regret
where we define (x(x) := argmax, δ(z, a) 0,, and let कि denote the best policy among (Te) possibly selected using validation set.
Results. We present performance comparisons in Figures G.1 through H. corresponding to Instances 1 through 4, respectively. Overall, our algorithm. AUPU consistently outperforms other baseline methods. The only exception is in Instance (Figure H.. a special case of the non-contextual setting, where M-AUPO performs slightly worse than DopeWolfe. This is an expected outcome, as DopeWolfe leverages a D-optimal design strategy, which is known be highly effective in the single-context setting, However, it is important to note that DopeWolfe completely fails in more
52

---

Instance 2, PL Loss, K=2
Instance 2, PL Loss, K=
Instance 2, PL Loss, K=5
088
DoscWoll
Subbpt. Gap
0.6
BestSkef M.ALPO bound
Unifum
0.6.
4-4
Instance RB Loss, K=2
Instance RB Loss, K=3
Instance 2, RB Loss, K=5
0.8
9.00et. C50
SubDpt
0.4
0.2
0.0
75
100
125
150
375
200
0.0
25
75
100
125
150
175
250
0.0
25
50
100
325
150
175
200
Round (1)
Round (U)
Round
Figure H.1: Performance comparisons for Instance (Non-contextual) with K 2, 3, and evaluated under the PL loss (first row) and RB loss (second row).
Instance 3, PL Lass, K=2
Instance 3, PL Loss, K=3
Instance 3, PL Loss, K=5
Sib0pt. Eac
0.6
0.4
Subopt
0.4
SabOpt.
0.4-
DipoMottc
0.2
75
150
375
100
175
100
125
200
Round (1)
Round
Instance RB Loss, K=2
Instance RB
Instance
0.8
0.8
0.8
SahOpt, CaD
DopeWbbtle Untermm
BeatSta!
MAAUFO (ous)
75
150
150
375
0.0
100
175
200
0.0
100
125
200
Round (t)
Round
Round
Figure H.2: Performance comparisons for Instance (Hard- lealearn contexts) with K 2, 3, and evaluated under the PI. loss (first row) and RB loss (second row).
general contextual scenarios (Figures G.1 higher than that of our approach (see Table
H.2 and H.3)
and its computational cost is significantly
K
DopeWolfe
Uniform
Best&Ref
M-AUPO (PL)
M-AUPO (RB)
2
7.28
0.10
0.10s
1.09
1.04
99.6 s
0.18 s
0.10s
2.35
1.06 s
5
150.5 s
0.35
0.10s
2.71
1.10 s
218.8
0.58 s
0.10s
4.10
1.13 s
10
331.1
0.99
0.10s
6.89
1.31
Table H.1: Runtime comparison over 200 rounds (seconds)
The uniform random assortment selection strategy, Uniform, shows reasonable performance though consistently inferior to M- AUPO-ip in Instances 1, 2, and 4, as presented in Figures G.I
H.I and H.3
53

---

Instance 4, PL Loss, K=2
Instance 4, Loss, K=3
Instance 4, PL Loss, K=5
0.25
023
0.25
Subppt Cap
0.20
022
0.20
0.15
0.35
0.15
SubOp,
Sabbpt
0.10
0.0
175
200
Instance 4, RB Loss, K=2
Instance 4, Loss, K=3
Instance 4, RB Loss, K=5
0.25
025
0.25
9.00m, C50
S.h0ppt
0.10-
Do Detiateee
0.10
knittm
0.05
BestSRer
0.05
0.05
MAUPO suun)
0.00
50
125 Round (0
150
150
175
200
0.00
25
75
120
125
150
175
250
0.00
25
75
100
125
150
175
200
Round (0)
Round (1)
Figure H.3: Performance comparisons for Instance 4 (skewed stochastic contexts) with K 2, and 5, evaluated under the PL loss (first row) and RB loss (second row).
respectively. In contrast, for Instance 3 (Figure H.2) where most features are uninformative (being nearly orthogonal to the true parameter) and thus careful action selection becomes crucial, Uniform performs substantially worse than M-AUPO.
The Best&Ref algorithm performs consistently worse than our algorithm and does not benefit from larger K, since always selects only a pair of actions.
Moreover, the suboptimality gap consistently decreases with larger K across the three algo- rithms-M-AUPO, Uniform, and DopeWolfe--werrea Best&Ref shows such improvement, as it always selects only two actions regardless of K. For M- AUPUPO this trend is consistent with our theoretical results (Theorems and 2). In contrast, the improvement observed for DopeWolfe suggests that its current theoretical guarantees may be loose, as their bound actually deteriorates with increasing K (recall that their theoretical guarantee worsens for larger K). This suggests that tighter bounds could be obtained by incorporating techniques similar to those introduced in our work.
Table H.2 presents the average assortment size |S,] of M-AUPO for various values of the maximum assortment size K. In most cases, the algorithm selects the full K actions, i.e., [S|]] = K. An exception occurs when K is large (e.g., 30 or more), which may be impractical in real-world applications due to the increased annotation burden on human labelers.
K
2
5
10
30
50
PL loss,
[S
2.00
3.00
5.00
7.00
10.00
16.21
18.78
RB loss, [
2.00
3.00
5.00
7.00
10.00
19.87
22.37
Table H.2: Assortment size |S,] of M-AUPO with varying K the synthetic experiment
H.2
Real-Worle Dataset
Setup. In our real-world dataset experiments, we evaluate performance on two widely used benchmark datasets: TREC Deep Learning (TREC-DL) and NECTAR. The TREC-DL dataset provides 100 candidate answers for each query, offering rich and diverse set of responses suitable for learning from listwise feedback. In contrast, the NECTAR dataset presents more concise setup, with only 7 candidate answers per question. From each dataset, we randomly sample | = 5000 prompts, each paired with its corresponding set of candidate actions-1000 for TREC-DL and 7 for NECTAR.
We use the Gemma-29 language model 75 to construct the feature representation ,(x, a). To obtain 6(2 a), we first concatenate the input prompt and the candidate response into single sequence,
54

---

TREC-DL, K=2
TREC-DL, K=3
TREC-DL, K=5
Dasakibll Uniomm
Srmpple Regret
Simple Regret
Simple Regres
3000
10500
13200
20000
5000
10000
25000
20000
5000
10000
13000
20020
Round (t)
Round (1)
Round (1)
Nectar, K=2
Nectar, K=3
Nectar, K=5
7.00
Dope
Simple Regret
1.75
Unitorm
Simple Regret
2.75
Simple Regret
1.75
1.25
1.23
1.2
1.40
5000
10503
15000
20000
5000
10000
15000
20000
5000
10000
15000
20000
Round (1)
Round
Round (5)
Figure H.4: Performance comparisons on the TREC-DL dataset (top row) and the NECTAR dataset (bottom row) for varying values of K = 2, 3, and 5.
which is then fed into Gemma-2B. The resulting feature vector is extracted from the last hidden layer of the model and has a dimensionality of d 2048. We then apply l normalization to enhance numerical stability and ensure consistent scaling. For each round i, we sample the context index from an exponential distribution with rate À = 0.1, which assigns higher probability to smaller indices and thus biases the selection toward earlier contexts. To generate ranking feedback and evaluate the suboptimality gap, we use the Mistral- 7B reward model [33] the ground-truth reward function.
We measure the suboptimality gap every 2,500 rounds throughout the training process and report the average performance over 10 independent runs, each with a different random seed. Along with the average, we also include the standard error to indicate variability across runs. these experiments, we report results under the RB loss only, due to its superior performance, as demonstrated in the synthetic data experiments. The experiments are conducted on Xeon(R) Gold 6226R CPU @ 2.90GHz (16 cores) and a single Geforce RTX 3090 GPU,
Baselines. We use the same set of baselines as in the synthetic data experiments. For DopeWolfe 76 we set the sampling size parameter R as R min( (x), 1000). Although a small value of R < 1000 may introduce significant approximation error- since the theoretically minimal-error choice is R = ((())) adopt this smaller value in our experiment to reduce computational overhead.
Performance measure. We measure the realized regret as in the synthetic experiment.
Results. We present performance comparisons in Figure H.4 Our algorithm, AUPO, consistently outperforms all baselines by a significant margin. As in the synthetic data experiments, the subop- timality gap for all methods decreases as K increases. Notably, DopeWolfe performs particularly poorly on the TREC-DL dataset. This may be attributed to the use of small sampling size R. which is insufficient compared to the full subset space of size (N) = =(N*) >> 1000 > R. This result highlights an important practical limitation of DopeWolfe: despite its use of approximate optimization to reduce runtime, the method still depends on combinatorial sampling to perform well, which becomes computationally infcasible in large-scale settings. In contrast, our algorithm, M-AUPO, achieves consistently strong performance while incurring only polynomial computational cost, demonstrating superior scalability and practicality for real-world deployment.
Table H.3 reports the actual assortment size [St] selected by M- AUPD on both datasets. In the TREC- DL experiment, [S,] nearly equal K for all values of K, as the number of available actions large (N = 100). In contrast, in the NECTAR experiment, where the number of available actions is much smaller (N- = 7), the actual assortment size [S is often smaller than K, especially when = N. This reduction occurs because the limited action space constrains the potential informativeness of larger assortments
example, becomes difficult to achieve high average uncertainty when there too few actions to choose from.
55

---

K
2
5
TREC-DL dataset, NECTAR dataset,
S S
2.00
3,00
5.00
6.98
2.00
2.99
4.45
4.76
Table H.3: Assortment size |St] of M-AUPO with varying in the real-world dataset experiment
I Limitations
In this paper, we primarily focus on the online PbRL setting, where contexts are drawn stochastically from fixed distribution. However, we do not explore the offline setting [93], which may involve a different set of challenges. As result, it remains an open question whether similar improve- ments such better performance with larger can be achieved in the offline setting. We view this as a promising direction for future research and leave it as an open problem.
56


Reviews:
[{"review_id": "I3vXEue4eH", "reviewer": "Reviewer_bMth", "summary": "This paper proposes selecting multiple actions in preference-based learning to improve sampling efficiency. The authors provide theoretical guarantees for the proposed algorithm, showing that the suboptimality gap is $O(\\frac{d}{T}\\sqrt{\\sum_{t=1}^T\\frac{1}{|S_t|}})$, where $|S_t|$ is the size of the action subset offered at round $t$.  This result eliminates the exponential dependence on parameter norm bound  $e^B$. The authors also establish a theoretical lower bound that matches the upper bound.", "questions": "1. In the field of contextual dueling bandits, theoretical guarantees are also often provided in terms of regret. The authors use the weaker notion of suboptimality gap. Is there an inherent difficulty in this work to provide a regret analysis?\n2. Saha, A. (2021) also provides a regret lower bound (matching the upper bound) of $O(\\sqrt{dT})$. In contrast, this paper gives a suboptimality gap lower bound of $O(\\frac{d}{\\sqrt{T}})$. How can this difference be explained?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths: \n 1. This work is the first  theoretical guarantee that larger subsets directly improve sample efficiency in PbRL.   \n 2.  This result eliminates the exponential dependence on parameter norm bound  $e^B$. And previous related works (eliminates $e^B$) only considered two options.  \n   \n\n### Weakness\n1. The parameter $B$ is the upper bound on the norm of $\\theta$ in the linear reward model, i.e., $\\Theta:= \\{ \\theta:\\mid \\|\\theta\\|_2 \\leq B\\}$. Generally, it is a small constant. Therefore, the theoretical improvement does not appear to be particularly significant.\n2. Each iteration requires solving the optimization problem (9), and the authors report a time complexity of $N^2K$. When the number of arms is large, the algorithm incurs a high computational cost.\n3. The paper assumes a finite number of arms ($N$). Under the same setting (linear rewards with a finite number of arms), previous works [1] and [2] have provided regret upper bounds of $O(\\sqrt{dT})$ (which correspond to a suboptimality gap of $O(\\sqrt{\\frac{d}{T}})$), which are better than the $O(\\frac{d}{\\sqrt{T}})$ bound presented in this paper.\n\n[1] Saha, A. (2021). Optimal algorithms for stochastic contextual preference bandits. Advances in\nNeural Information Processing Systems 34 30050–30062.\n\n[2] Bengs, V., Saha, A. and H¨ullermeier, E. (2022). Stochastic contextual dueling bandits under\nlinear stochastic transitivity models. In International Conference on Machine Learning. PMLR.", "was_revised": true, "final_justification": "The authors have addressed my concerns during the rebuttal phases. Overall, my evaluation is positive.", "rebuttal": "Thank you very much for your positive review! Below, we provide our responses to your comments and concerns.\n\n---\n- ### **The Parameter Boundedness $B$ Is Typically Large in Practice**\nWe respectfully **disagree** with the claim that $B$ is generally a small constant. In many real-world scenarios, $B$ can in fact be quite large. For example, in our real-world experiments, the reward function derived from Mistral-7B spans a range of approximately –20 to 20. Given that we assume $\\\\|\\phi(x,a)\\\\|_2 \\leq 1$, this implies that the norm bound on $\\theta$, i.e., $B$, must also scale with 20. Therefore, we strongly believe that **eliminating exponential dependence on $B$ (e.g., $e^B$) represents a substantial and meaningful improvement**.\n\nIn many prior works on logistic bandits (Faury et al., 2020; 2022; Abeille et al., 2021), GLM bandits (Lee et al., 2024; Sawarni et al., 2024 [1]), and MNL bandits (Zhang and Sugiyama, 2024; Lee and Oh, 2024), eliminating or reducing the $e^B$ dependence has been recognized as a central research goal. In contrast, PbRL and dueling bandit literature (e.g., Saha, 2021; Saha et al., 2023; Zhu et al., 2023; Xiong et al., 2023; Zhan et al., 2023) has largely overlooked this issue, and whether $e^B$ dependence can be avoided has remained a **long-standing open question**. \n\nIn this paper, we show that it is **indeed possible to eliminate the $e^B$ dependence without relying on auxiliary techniques**, such as specialized sampling schemes [2] or prior knowledge of $\\kappa$ [3], which are often impractical. Our improvement is enabled by rethinking the Hessian as a conditional expectation of the covariance matrix and applying matrix concentration inequalities repeatedly (see Lemmas D.2 and E.1).\n\nThis proof technique is **not only theoretically elegant but also broadly applicable**: it can be **directly applied to any existing PbRL or dueling bandit analysis**, including regret-minimization settings, as long as elliptical potential lemmas are used—**without modifying the original algorithm!** This reveals that the exponential dependence on $B$ was **not fundamentally necessary**, but rather a byproduct of loose analysis.\n\nWe strongly believe this new perspective deepens the theoretical understanding of PbRL and dueling bandits, and could inspire new research directions in the field.\n\n> [1] Sawarni, Ayush, et al. \"Generalized linear bandits with limited adaptivity.\" Advances in Neural Information Processing Systems 37 (2024): 8329-8369.\n\\\n[2] Chen, Mingyu, et al. \"Avoiding exp (rmax) scaling in rlhf through preference-based exploration.\" arXiv (2025).\n\\\n[3] Di, Qiwei, Jiafan He, and Quanquan Gu. \"Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback.\" ICML 2025.\n\n\n---\n- ### **Efficient $\\mathcal{O}(NK)$ Assortment Selection Provided in Appendix**\n\nIn Appendix H.1, we introduce a **more efficient** assortment selection strategy. Instead of selecting the reference action $\\bar{a}_t$ that maximizes the average uncertainty, we simply choose $\\bar{a}_t \\in \\mathcal{A}$ arbitrarily. We show that this simplification still yields the same theoretical guarantees while reducing the computational cost to $\\mathcal{O}(NK)$. We believe this is a significant improvement, as prior works in the dueling bandit literature typically incur $\\mathcal{O}(N^2)$ computational costs (e.g., Saha, 2021; Bengs et al., 2022), which is worse than ours since $K \\ll N$ in general.\n\n---\n- ### **Saha (2021) and Bengs et al. (2022) Assume Stronger Context Conditions**\n\nWe would like to clarify that both Saha, 2021 and Bengs et al., 2022 make **stronger assumptions** on the context (feature) vectors. Specifically:\n1. Saha (2021) assumes that the feature vectors at each round $t$ are **drawn i.i.d.** from a fixed distribution.\n2. Bengs et al. (2022) imposes a more stringent condition (Assumption A1), requiring that the offered **feature vectors contain a set of basis vectors satisfying**\n    $\\rho \\mathbf{I}\\_d \\leq \\sum\\_{j=1}^d b_j b_j^\\top,$\nfor some constant $\\rho>0$.\n\nIn contrast, we **do not require any structural assumptions on the feature vectors** $\\phi(x,a)$; they can be specified **arbitrarily**. Even though we assume a fixed context distribution and a stationary action space in our main presentation *for simplicity*, our analysis readily extends to settings where both **the context distribution and the action space vary over time** (and can be given arbitrarily). We will make this point more explicit in the revised version, in addition to the brief note already provided in Footnote 1.\n\nTherefore, we strongly believe that **comparisons to their algorithms and results are not meaningful**, as they rely on significantly stronger assumptions. In particular, without these contextual assumptions, their algorithms and analyses break down entirely and cannot achieve the regret bound of $\\mathcal{O}(\\sqrt{dT \\log N} )$ in more general setting we consider.\n\n---\n- #### **Q1. Is there an inherent difficulty in this work to provide a regret analysis?**\nNo, there is **no inherent difficulty**. In fact, our method readily admits a regret analysis. Specifically, define the greedy policy at round $t$ as\n$\\hat{\\pi}\\_t(x) = \\arg\\max\\_{a \\in \\mathcal{A}} \\phi(x, a)^\\top \\hat{\\theta}\\_t$.\nThen, following the similar analysis as in the proof of Theorem 1 (and ignoring non-leading terms for simple presentation), we obtain:\n$$\n    \\text{Reg}_T \n    := \\sum\\_{t=1}^T \n    \\left(\\phi(x_t, \\pi^\\star(x_t)) - \\phi(x_t, \\hat{\\pi}\\_t(x_t))\\right)^\\top \\theta^\\star\n    \\lesssim \\sum\\_{t=1}^T \n    \\left(\\phi(x_t, \\pi^\\star(x_t)) - \\phi(x_t, \\hat{\\pi}\\_t(x_t))\\right)^\\top    \\left(\\theta^\\star - \\hat{\\theta}\\_t\\right)\n    \\leq \\sum\\_{t=1}^T \\\\| \\phi(x_t, \\pi^\\star(x_t)) - \\phi(x_t, \\hat{\\pi}\\_t(x_t)) \\\\|\\_{H_t^{-1}}\n    \\\\| \\theta^\\star - \\hat{\\theta}\\_t \\\\|\\_{H_t}\n    \\leq 2 \\beta_T(\\delta) \\sum\\_{t=1}^T \n    \\frac{1}{|S_t|} \\sum\\_{a \\in S_t} \n     \\\\| \\phi(x_t, a) - \\phi(x_t, \\bar{a}\\_t) \\\\|\\_{H_t^{-1}}\n    \\leq  2 \\beta_T(\\delta) \n    \\sqrt{\\sum\\_{t=1}^T \\frac{1}{|S_t|}}\n    \\sqrt{\\sum\\_{t=1}^T  \\sum\\_{a \\in S_t} \\\\| \\phi(x_t, a) - \\phi(x_t, \\bar{a}\\_t) \\\\|\\_{H_t^{-1}}^2}\n    = \\tilde{\\mathcal{O}}\n    \\left( d \\sqrt{\\sum\\_{t=1}^T \\frac{1}{|S_t|}} \\right).\n$$\nThis result also shows that the regret improves with larger comparison sets $S_t$, clearly demonstrating the benefit of multiple-option feedback. We appreciate the constructive question.\n\n\n---\n- #### **Q2. Comparison to the lower bound of Saha (2021). How can the difference be explained?**\nFirst, we would like to emphasize that there are **fundamental differences in the problem setting.** Saha (2021) considers *one-click feedback* among the $|S_t|$ items, whereas our setting assumes access to the *full ranking feedback* over $|S_t|$ items. Hence, our setup reflects a richer information setting, which naturally allows for improved statistical efficiency—especially in terms of dependence on $K$.\n\nMoreover, the definitions of regret differ. In Saha (2021), the regret is defined as an average reward gap:\n$$\n    \\text{Reg}\\_t = (x_t^\\star)^\\top \\theta^\\star -\\frac{1}{|S_t|} \\sum\\_{x \\in S_t} x^\\top \\theta^\\star,\n$$\nwhereas in our case, the suboptimality gap is defined as the gap between the optimal and the current best item (for simplicity, let $x \\leftarrow \\phi(\\cdot, \\cdot)$):\n$$\n    \\text{SubOpt}\\_t = (x_t^\\star)^\\top \\theta^\\star - \\hat{x}_t^\\top \\theta^\\star, \\quad \\text{where } \\hat{x}_t:= \\arg\\max\\_{x \\in \\mathcal{X}_t} x^\\top \\hat{\\theta}_t.\n$$\nDue to these key differences in feedback type and regret formulation, a direct **comparison to the lower bound in Saha (2021) is not appropriate**. That said, if one were to hypothetically align the performance measures and consider the special case of $K = 2$, then our lower bound of $\\Omega\\left(\\frac{d}{\\sqrt{T}}\\right)$ is **strictly tighter** than theirs, which is $\\Omega\\left(\\sqrt{\\frac{d}{T}}\\right)$. (We also note that their bound does not include any dependence on $\\log N$.)\n\nTo directly address your question on **why the bounds differ**, we cautiously suggest that the looser bound in Saha (2021) arises from the **choice of instance construction**. A similar phenomenon can be observed in Theorem 3.1 of Bengs et al. (2022), where the authors derive an $\\Omega(d \\sqrt{T})$ lower bound under the assumption that $\\theta^\\star \\in \\mathcal{B}_1(2)$ and $\\mathcal{X} \\subseteq \\mathcal{B}_1(\\infty)$, but only an $\\Omega(\\sqrt{dT})$ bound when $\\mathcal{X} \\subseteq \\mathcal{B}_1(2)$.\n\nWe speculate that a comparable $\\Omega\\left(\\sqrt{\\frac{d}{T}}\\right)$ suboptimality gap could also be derived in our setting by constructing a different (weaker) instance. However, since this would yield a looser bound than our current result, we do not explore this direction further in the this rebuttal.\n\n---\n Please feel free to reach out if you have any further questions!"}, {"review_id": "gvKMx6mw08", "reviewer": "Reviewer_LFMk", "summary": "The paper aims to design an algorithm for learning from multiple-option feedback in an online PbRL setting with stronger theoretical guarantees. The paper proposes M-AUPO which uses online mirror descent on the comparison loss and selects an assortment of actions by maximizing the feature uncertainty relative to a reference. The paper provides a sub optimality gap and performs experiments on synthetic data and real-world data with fixed features.", "questions": "- Can you provide synthetic experiments with varying B and also provide more details such as what the norms of the features look like in the real-world setting?\n- Can you clarify why the provided bound is an improvement? It seems the second term alone for larger $B$ is weaker than existing bounds. \n- Can you provide comparison to other methods beyond DopeWolfe? In particular, it would be good to see comparisons of sub-optimality gap to the methods presented in Table 1. \n- Would it be possible to extend the experiments/method beyond a linear model?\n- Can you provide the proofs for all results?\n\nHaving the full proofs and clarifications about the provided bound in particular would increase the score.", "limitations": "No, limitations around the method and analysis being restricted to linear models could be more explicitly presented and limitations of the bound under different conditions (larger B, smaller T) should be addressed.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper considers a novel setting of multi-option PbRL where contexts are drawn from an unknown distribution and the assortment is selected. \n- Background on PbRL and the algorithm are clearly presented.\n- The paper proposes a new algorithm based on selecting a diverse set of actions and using an online mirror descent algorithm with theoretical guarantees. \n- The paper performs numerical experiments following the theoretical setting and with real-world data. \n\nWeaknesses:\n- Full proofs are not provided. \n- It seems it could be difficult to generalize M-AUPO to more practical settings beyond a linear model. \n- The full bound consists of the term consider the leading term and an additional term with an $e^B$ dependency but decays faster with $T$. The second term is considered negligible for large enough $T$, but if $T$ large enough for this term to be neglected is being considered, under the same setting, the bounds from existing work with $e^B$ dependency would actually be better than the bound presented especially since the provided bound has a factor $e^{4B}$. Based on this, the claims can be misleading and it is unclear whether the sub optimality of M-AUPO is better in practice. \n- Experiments only compare to DopeWolfe. \n- The synthetic experiments work with $B=1$ and the decrease in sub-optimality seems relatively small with $K$ and based on the bound, the effect of $K$ could be smaller with larger $B$. It would be useful to see how this generalizes with varying $B$. \n- The real world setting uses fixed features which differs from most practical settings which often train a full model or train at least multiple layers of a model. As a result it seems difficult to be able to make claims about the effect of multi-option feedback for tasks such as training a language model based on the analysis.", "was_revised": true, "final_justification": "Authors provided clarifications around results showing their results are novel and can be verified. Additional discussion on implications has been provided, but significant revision would be required.", "rebuttal": "We appreciate the time you took to review our paper and your valuable feedback.\n\nBefore addressing the reviewer’s concerns, we would like to re-emphasize the significance of our theoretical contributions. Our primary contributions and interesting insights are:\n1) the **first theoretical result showing improved sample efficiency with multiple-option feedback** (to our best knowledge), \n2) the **elimination of the exponential $e^B$ dependence** common in prior PbRL and dueling bandit literature—achieved **without relying on any complex or auxiliary techniques**, such as self-sampling updates [1] or the use of $\\kappa$-dependent weighted covariance matrix [2] ($\\kappa$ is generally unknown in practice), and\n3) The sample efficiency of **RB loss and PL loss is equivalent** in terms of the leading-order term. This result provides **theoretical justification** for the common empirical practice of decomposing ranking feedback into pairwise comparisons, as done in works such as Ouyang et al. (2022).\n4) the **first $K$-improving lower bound** in PbRL.\n\nFrom a theoretical perspective, the **key lemmas used to eliminate the exponential \\$e^B\\$ dependence** (Lemmas D.2 and E.1) are **particularly significant**, as they can be **readily applied to many existing PbRL analyses**—*provided elliptical potential lemmas are used*—**without any modification to the underlying algorithms**. This demonstrates that the widely observed $e^B$ dependence was **not a fundamental limitation**, but rather an artifact of overly loose analysis—an insight we find both surprising and highly impactful.\n\nWe believe these contributions mark a significant step forward in the theory of PbRL and are sufficient to merit acceptance. We also address all of the reviewer’s concerns below and hope the reviewer will reconsider our paper in light of these points.\n\n>[1] Chen, Mingyu, et al. \"Avoiding exp (rmax) scaling in rlhf through preference-based exploration.\" arXiv (2025).\n\\\n>[2] Di, Qiwei, Jiafan He, and Quanquan Gu. \"Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback.\" ICML 2025.\n\n---\n- ### **Full Proofs Are Provided in the Appendix** \nWe clarify that all theoretical proofs have already been provided in the appendix, which was submitted as part of the supplementary material in accordance with NeurIPS 2025 guidelines.\n\n---\n- ### **Linear Model Is a Foundational Starting Point**\nAssuming linear rewards (with fixed features) is a **widely adopted approach** for analyzing the statistical efficiency of PbRL, including dueling bandits. This modeling choice has been used in numerous prior works—such as Saha (2021), Wu and Sun (2023), Saha et al. (2023), Zhu et al. (2023), Di et al. (2024), Thekumparampil et al. (2024), among others—as a foundational tool for theoretical analysis. \n\nTherefore, we strongly believe that **this assumption should not be regarded as a unique weakness of our work, nor as a reason for rejection.** The linear assumption serves as a fundamental starting point for understanding how the learning mechanism operates in PbRL. If certain phenomena fail to hold in this foundational setting, it is difficult to expect them to hold in more complex scenarios. Hence, we believe that the contributions outlined above are both **meaningful and valuable to the community**. \n\n---\n- ### **Extension to General Function Approximation**\nTo further **address the reviewer’s concern about the linearity and fixed feature assumptions**, we show that  **MAU (Maximizing Average Uncertainty) method can be extended to general function classes**, following a similar approach to Theorem 4 of Das et al. (2024). Specifically, given a function class $\\mathcal{F}$, we define a confidence set $\\mathcal{C}\\_t(\\mathcal{F}, \\delta)$ and an exploration bonus: \n$$\nb_t(x, a, a'):= \\max_\\{f_1, f_2 \\in \\mathcal{C}\\_t (\\mathcal{F}, \\delta)}|f_1(x,a,a') - f_2(x,a,a')|.\n$$\nWe then select the reference action-assortment pair $(\\bar{a}\\_t, S_t)$ according to:\n$$(\\bar{a}\\_t, S_t) := \\arg\\max\\_{\\bar{a}, S \\,s.t.\\, \\bar{a} \\in S} \\frac{1}{|S|} \\sum\\_{a \\in S} b_t(x, a, \\bar{a}).$$\nThen, we can bound the suboptimality as:\n$$\n\\text{SubOpt}(T) \\leq \\frac{2}{T} \\sum\\_{t=1}^T b_t(x_t, \\hat{\\pi}\\_t(x_t), \\pi^\\star(x_t))\n\\leq \\frac{2}{T} \\sum\\_{t=1}^T \\frac{1}{|S_t|} \\sum\\_{a\\in S_t} b_t(x, a, \\bar{a}\\_t)\n\\leq \\frac{2}{T} \n\\sqrt{\\sum_{t=1}^T \\frac{1}{|S_t|}}\n\\sqrt{\\sum_{t=1}^T\\sum\\_{a\\in S_t} b_t(x, a, \\bar{a}\\_t)^2}\n\\leq \\frac{2}{T} \n\\sqrt{\\sum\\_{t=1}^T \\frac{1}{|S_t|}}\n\\sqrt{\\frac{1}{TK} + d_{\\mathcal{E},\\mathcal{F}} + 4 d_{\\mathcal{E},\\mathcal{F}} \\beta_T \\log (TK)}\n= \\tilde{\\mathcal{O}}\\left( \\frac{1}{T} \\sqrt{\\sum_{t=1}^T \\frac{1}{|S_t|}\\cdot d_{\\mathcal{E}} \\log\\mathcal{N_\\mathcal{F}}}\\right),\n$$\nwhere $d_{\\mathcal{E},\\mathcal{F}}$ and $\\mathcal{N_\\mathcal{F}}$ are  the covering number and Eluder dimension of $\\mathcal{F}$, respectively. The final inequality follows from Lemma 2 of [1], with minor modifications. Therefore, this result suggests that **multiple-option feedback can lead to improved sample complexity for general function classes** as well.\n\nWe hope that this additional result can addresses the reviewer’s concern regarding the linear reward assumption and the fixed feature assumption.\n\n>[1] Russo, Daniel, and Benjamin Van Roy. \"Eluder dimension and the sample complexity of optimistic exploration.\" NeurIPS 2013.\n---\n- ### **Our Bound Is a Clear Improvement**\n\nIt seems there is a possibility that readers may **misunderstand the prior bounds** presented in Table 1. To clarify, we highlight two key points:\n1. **Prior works also incur $e^{4B}$ dependence**: For example, Zhu et al. (2023), Mukherjee et al. (2024), and Thekumparampil et al. (2024) all include $\\gamma = e^{-4B}$ (or $e^{-4}$ when $B = 1$), implying an $e^{4B}$ dependence. Thus, the second term in our bound is NOT weaker than theirs.\n2. **The Sq. Pred. Error measure used in Mukherjee et al. (2024) and Thekumparampil et al. (2024), roughly speaking, corresponds to the square of our suboptimality.**: Taking square roots, their bounds become $\\tilde{\\mathcal{O}}\\left(\\frac{d K^3}{\\kappa \\sqrt{T}}\\right)$—which is worse than ours $\\tilde{\\mathcal{O}}\\left(\\frac{d}{T} \\sqrt{\\sum_{t=1}^T \\frac{1}{|S_t|}} + \\frac{d^2}{\\kappa T}\\right)$ in terms of both $K$ and $\\kappa$.\n\nTherefore, our bound is a **strict improvement**, and even the **second term alone is NOT weaker than existing results** for large $B$. We will make this clarification more explicit in the revised version. Thank you for pointing this out.\n\n---\n- ### **Additional Experiments**\n\n**1. vs. Other Baselines**\n\n**In Appendix I**, we have **already included** an additional comparison with a \"Uniform\", which selects actions uniformly at random (to be moved to the main paper in the revision). To provide a more comprehensive evaluation, we now also include:\n- \"Uniform\", which selects actions uniformly at random (already included in Appendix I), and\n- \"Best&Ref\", which selects an action pair ($K=2$) using the current policy and a reference policy (e.g., uniform random or SFT),  respectively—following a selection mechanism similar to those in Online GSHF [1] and XPO [2]. \n\nThe results demonstrate that our method either **significantly outperforms** all other baselines or is second-best with a minimal gap. (*PL loss only, due to limited space.*)\n\n**i) Synthetic experiment ($T=200$)**\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|0.1629|0.1671|0.1575|**0.0396**|\n|3|0.1587|0.1654|0.1482|**0.0331**|\n|5|0.1539|0.0797|0.1534|**0.0244**|\n|7|0.1547|0.0561|0.1551|**0.0204**|\n\n**ii) Realworld experiment ($T=20,000$)**\n\n**ii-1)** TREC-DL dataset\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|6.115|3.579|3.465|**3.204**|\n|3|5.999|2.964|3.458|**2.381**|\n|5|5.971|2.548|3.430|**2.052**|\n\n**ii-2**) Nectar dataset\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|1.418|**1.279**|1.291|1.285|\n|3|1.246|1.243|1.275|**1.019**|\n|5|1.232|1.116|1.257|**0.997**|\n\nThe reviewer also suggested comparing sub-optimality gaps with the methods in Table 1. However, Zhu et al. (2023) and Mukherjee et al. (2024) assume **fixed (given) assortments**, a different and simpler setting that does not account for interactive decision-making—crucial in real-world tasks like web search, where only the top-ranked results can be labeled. Therefore, a **direct comparison with these methods is either infeasible or inappropriate**.\n\n> [1] Xiong, Wei, et al. \"Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint.\" ICML 2024\n\\\n[2] Xie, Tengyang, et al. \"Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF.\" ICLR 2025\n\n**2. Robustness to Varying B**\n\nIn response to the reviewer’s request, we report suboptimality across varying values of $B$ in our synthetic experiments. As shown below, our algorithm is quite **robust** to the scale of $B$ in practice, e.g., $(K=2, B=1) \\approx (K=5, B=10)$. \n\ni) $K=2$\n|B|DopeWolfe|Uniform|Best&Ref|TopK|M-AUPO (ours)|\n|-|-|-|-|-|-|\n|1.0|0.1629|0.1671|0.1575|0.1260|**0.0396**|\n|3.0|0.1829|0.1673|0.1598|0.1349|**0.0425**|\n|5.0|0.1859|0.1664|0.1587|0.1431|**0.0482**|\n|10.0|0.1821|0.1686|0.1624|0.1476|**0.0543**|\n\nii) $K=5$\n|B|DopeWolfe|Uniform|Best&Ref|TopK|M-AUPO(ours)|\n|-|-|-|-|-|-|\n|1.0|0.1539|0.0797|0.1534|0.1026|**0.0244**|\n|3.0|0.1623|0.0760|0.1550|0.0936|**0.0269**|\n|5.0|0.1698|0.0785|0.1576|0.1043|**0.0286**|\n|10.0|0.1766|0.0812|0.1618|0.1081|**0.0395**|\n\n#### **Q. What the norms of the features look like in the real-world setting?**\n\nIn our real-world experiments, we use the reward from Mistral-7B as the true reward signal, which ranges from approximately –20 to 20. Since we assume $\\\\|\\phi(x,a)\\\\|_2 \\leq 1$, this implies that the norm bound on $\\theta$ (i.e., $B$) is approximately on the order of 20.\n\n---\nWe welcome any additional questions!"}, {"review_id": "y3qbiewLkq", "reviewer": "Reviewer_fSmY", "summary": "This paper propose M-AUPO, an algorithm that selects action subsets by maximizing average uncertainty, to enhance sample efficiency for online PbRL. The authors theoretically prove a suboptimality gap and lower bound for M-AUPO, avoiding the exponential dependence on parameter norms. Experiments on synthetic and real-world datasets validate its effectiveness.", "questions": "1. See weaknesses.\n2. The denominator of Eq. (1) should be $\\sigma_k$ and not $\\sigma_j$, right?", "limitations": "Suggest adding a limitation paragraph about the effect of inherent limitations of PL or BT assumptions on RLHF.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The theoretical derivation is sufficient.\n2. The paper is well organized and easy to follow.\n\nWeaknesses:\n1. In RLHF, it's no surprise that increasing the number of options for the same context leads to performance improvements. For example, for RB methods, this approach means more amount of data, so the reward model will be more accurate. What I think more interesting is the discussion of whether to increase the number of questions or the number of options per question for a fixed amount of total data. For example, the first set of experiments have N questions with M options per question; the second set of experiments had N/2 questions with 2M options per question; which one is better?\n2. The experimental part is too simple. 1. Missing important baselines, e.g., other algorithms that can handle pairwise comparisons in the RB setting, such as DPO; 2. Missing dopewolfe vs. m-aupo comparisons with **varying K** (the last subfigure in Figure 1 and 2).\n3. Lack of hyperparametric analysis. The paper does not show the values of regularization parameter $\\lambda$ and step size $\\eta$ hyperparameters in the experiments and lacks tuning or ablation studies on hyperparameters.", "was_revised": true, "final_justification": "The authors respond to my question about which of the longer or short options are better using Theorem 3, clarifying the choice of baseline and providing additional explanations about hyperparameters. The authors address all of my concerns.", "rebuttal": "We appreciate your time and thoughtful feedback in reviewing our paper.\n\nBefore addressing the reviewer's specific concerns, we would like to emphasize the importance of our theoretical contributions, which we believe are substantial but may have been somewhat underappreciated in your initial evaluation. Our key contributions and insights are as follows:\n\n1) the **first theoretical result showing improved sample efficiency with multiple-option feedback** (to our best knowledge), \n2) the **elimination of the exponential $e^B$ dependence** common in prior PbRL and dueling bandit literature—achieved **without relying on any complex or auxiliary techniques**, such as self-sampling updates [1] or the use of $\\kappa$-dependent weighted covariance matrix [2] ($\\kappa$ is generally unknown in practice), and\n3) The sample efficiency of **RB loss and PL loss is equivalent** in terms of the leading-order term. This result provides **theoretical justification** for the common empirical practice of decomposing ranking feedback into pairwise comparisons, as done in works such as Ouyang et al. (2022).\n4) the **first $K$-improving lower bound** in PbRL.\n\n\nEspecially, from a theoretical perspective, the **key lemmas used to eliminate the exponential $e^B$ dependence** (Lemmas D.2 and E.1) are **particularly significant**, as they can be **readily applied to many existing PbRL analyses**—*provided elliptical potential lemmas are used*—**without any modification to the underlying algorithms**. This demonstrates that the widely observed $e^B$ dependence was **not a fundamental limitation**, but rather an artifact of overly loose analysis. We believe this insight is both surprising and broadly useful.\n\nGiven the novelty, generality, and potential impact of our theoretical contributions, we kindly ask the reviewer to reconsider their evaluation and support our paper for acceptance.\n\n>[1] Chen, Mingyu, et al. \"Avoiding exp (rmax) scaling in rlhf through preference-based exploration.\" arXiv (2025).\n\\\n[2] Di, Qiwei, Jiafan He, and Quanquan Gu. \"Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback.\" ICML 2025.\n\n---\n- ### **First Rigorous Theoretical Justification of the Insight!**\n\nWhile it may appear intuitive that offering more options per round should improve performance (though it is unclear whether this is a widely recognized insight), **no prior work has formally established this**. In fact, most existing theoretical results worsen as $K$ increases, contradicting the intuition. Our result therefore **closes a long-standing gap between intuition and theory**, representing a meaningful step forward for the PbRL literature. We believe this contribution should be viewed as a **strength**—providing a complete theoretical justification of the intuition—rather than as a weakness.\n\nFurthermore, we would like to clarify that—even though ranking feedback can *potentially* provide more data—it is not obvious whether this feedback contains sufficient information to yield meaningful information gain. For example, under the RB loss, if many item pairs are very similar in preference, the gain from such feedback is not guaranteed. Our paper explicitly addresses this issue by studying how to *maximize the average uncertainty* in the offered options, a challenge that we believe has not been adequately explored in prior work.\n\n\n---\n- ### **Longer Options Are No Worse Than Shorter Options**\n\nWe address your question comparing the following two settings:\n\n- Option 1: $N$ questions with $M$ options each\n- Option 2: $N/2$ questions with $2M$ options each\n\nOur upper and lower bounds yield the following suboptimality ranges:\n\nOption 1: $\\Omega\\left(\\frac{d}{M\\sqrt{N}}\\right) \\sim \\tilde{\\mathcal{O}}\\left(\\frac{d}{\\sqrt{MN}}\\right)$\n\nOption 2: $\\Omega\\left(\\frac{d}{2M\\sqrt{N/2}}\\right) \\sim \\tilde{\\mathcal{O}}\\left(\\frac{d}{\\sqrt{MN}}\\right)$\n\nThese bounds suggest that the **longer-option case (Option 2) is not worse than the shorter-option case (Option 1)** in terms of sample efficiency. However, due to the remaining gap between the upper and lower bounds by a factor of $\\sqrt{K}$ (i.e., the optimal rate is not yet identified), we cannot definitively say which option is always better. It is possible that Option 2 may be better, as its lower bound is strictly smaller. Alternatively, the two settings may be equivalent if the current upper bound is tight. \n\nWe believe that rigorously closing this gap is an interesting and important direction for future work, and we thank the reviewer for raising this constructive point. That said, even with the current bounds, we find the result valuable, as it suggests that either setting can be used depending on practical convenience, with comparable (or similar) statistical efficiency.\n\n\n---\n- ### **Additional Experiments**\n\nIn our experiments, we made every effort to include all relevant baselines and to cover a wide range of scenarios. We hope the reviewer finds our experimental evaluation sufficiently thorough.\n\n**1. vs. Other baselines**\n\\\nIn **Appendix I**, we have **already included** an additional comparison with a \"Uniform\", which selects actions uniformly at random (to be moved to the main paper in the revision). To provide a more comprehensive evaluation, we now also include: \n- \"Uniform\", which selects actions uniformly at random (already included in Appendix I, and will be moved to the main paper in the revision), and\n- \"Best&Ref\", which selects an action pair ($K=2$) using the current policy and a reference policy (e.g., uniform random or SFT),  respectively—following a selection mechanism similar to those in Online GSHF [1] and XPO [2]. \n\nWe believe that \"Best&Ref\" is the most relevant baseline for online RLHF, as it reflects how many online RLHF algorithms select actions in practice. Note that a direct comparison with DPO is not appropriate, since DPO is best understood as an optimization algorithm for the offline setting, rather than an action (or assortment) selection strategy for the online setting.\n\nThe results demonstrate that our method either **significantly outperforms** all other baselines or is second-best with a minimal gap. (*PL loss only, due to limited space.*)\n\n**i) Synthetic experiment ($T=200$)**\n\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|0.1629|0.1671|0.1575|**0.0396**|\n|3|0.1587|0.1654|0.1482|**0.0331**|\n|5|0.1539|0.0797|0.1534|**0.0244**|\n|7|0.1547|0.0561|0.1551|**0.0204**|\n\n**ii) Realworld experiment ($T=20,000$)**\n\n**ii-1)** TREC-DL dataset\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|6.115|3.579|3.465|**3.204**|\n|3|5.999|2.964|3.458|**2.381**|\n|5|5.971|2.548|3.430|**2.052**|\n\n**ii-2**) Nectar dataset\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|1.418|**1.279**|1.291|1.285|\n|3|1.246|1.243|1.275|**1.019**|\n|5|1.232|1.116|1.257|**0.997**|\n\n> [1] Xiong, Wei, et al. \"Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint.\" ICML 2024\n\\\n[2] Xie, Tengyang, et al. \"Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF.\" ICLR 2025\n\n**2. Varying values of $K$ is already included in Appendix I**\n\\\nA comparison between DopeWolfe and M-AUPO across **varying values of $K$ is already included in Appendix I.** Moreover, in the synthetic experiments, we evaluate our algorithm under diverse context structures. The results demonstrate the **superior performance** of our method across various settings. We also include runtime tables—covering both synthetic and real-world experiments—which highlight the **computational efficiency of our algorithm**. Please refer to Appendix I for further details.\n\n\n---\n- ### **We Use Exact Theoretical Parameter Values in All Experiments**\nIn all of our experiments, we used the **exact same parameter values** (e.g., $\\lambda$, $\\eta$, etc.) as defined in the theoretical results. For reference, please see the notation summary in Table C.1. Therefore, **ablation studies on these parameters are unnecessary**. \n\nOne key advantage of using theoretically grounded algorithms is that the **prescribed parameter values can be directly applied in practice**, without the need for exhaustive hyperparameter tuning. We will clarify this point more explicitly in the final version of the paper.\n\n---\n- **(minor)**: As you pointed out, the denominator in Eq. (1) should indeed be $\\sigma_k$. In fact, we had already made the correction in the supplementary appendix, but we still appreciate your attention to detail—thank you for pointing it out.\n\n---\nPlease feel free to reach out if you have any further questions or require clarificationon any point!"}, {"review_id": "2uQAXkyxtP", "reviewer": "Reviewer_h2r7", "summary": "The paper proposes M-AUPO, a novel algorithm for preference-based reinforcement learning (PbRL) that leverages ranking feedback over multiple actions (beyond pairwise comparisons) under the Plackett-Luce (PL) model.", "questions": "1. The RB loss has tighter bounds but higher computational cost. In practice, how do you decide between PL and RB losses?\n2. Given the prominence of pairwise preference-based RLHF (e.g., PPO + BT model in [35] or DPO [38]), did you consider comparing M-AUPO against such methods?\n3. See the weaknesses.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. First work to rigorously show that larger ranking feedback subsets improve sample efficiency in PbRL, with matching lower bounds.\n2. Addresses limitations of pairwise comparisons in RLHF and provides a principled way to exploit richer feedback.\n3. Validates theory on both synthetic and real-world data, outperforming baselines like DopeWolfe.\n\nWeaknesses:\n\n1. The per-round cost scales with $K^3d^3$ for rank-breaking (RB) loss, which may limit scalability for very large $K$.\n2. Relies on linear reward models and the PL model for rankings; robustness to misspecification is unclear.", "was_revised": true, "final_justification": "Key Resolved Issues:\n* Concerns about the baseline problem were addressed through additional experiments in the rebuttal.\n* Concerns about \"Robustness to Model Misspecification in Experiments\" were addressed through extension to General Function Approximation in the rebuttal.\n\n\nThe paper’s strengths outweigh its weaknesses, justifying a score of Borderline accept.", "rebuttal": "Thank you for your feedback and for engaging with our work.\n\nThe reviewer’s main concerns are (i) computational efficiency for large $K$ and (ii) the linear reward assumption. However, **$K$ is typically small** in practice (e.g., $K \\leq 10$ in Ouyang et al., 2022), and the l**inear assumption is a standard and foundational** choice in bandit and RL theory. Thus, these should not be viewed as weaknesses. We elaborate below.\n\nBeyond the main concerns, we would like to reiterate the significance of our theoretical results:\n\n1) the **first theoretical result showing improved sample efficiency with multiple-option feedback** (to our best knowledge), \n2) the **elimination of the exponential $e^B$ dependence** common in prior PbRL—achieved **without relying on any auxiliary techniques**, such as self-sampling updates [1] or the use of $\\kappa$-dependent weighted covariance matrix [2] ($\\kappa$ is generally unknown in practice), and\n3) The sample efficiency of **RB loss and PL loss is equivalent** in terms of the leading-order term. This result provides **theoretical justification** for the common empirical practice of decomposing ranking feedback into pairwise comparisons (Ouyang et al., 2022).\n4) the **first $K$-improving lower bound** in PbRL.\n\nFor our first contribution, although it may seem intuitive that more options improve performance, **no prior work has formally proven this**—and most existing results actually degrade with larger $K$. Our result thus **closes a long-standing gap between practical intuition and theory, marking a significant step forward for PbRL**.\n\nFor our second contribution, removing the $e^B$ dependence is especially impactful, as many prior works failed to do so (e.g., Saha, 2021; Saha et al., 2023; Zhu et al., 2023; Xiong et al., 2023; Zhan et al., 2023). More importantly, the **key lemmas used to eliminate the exponential $e^B$ dependence** (Lemmas D.2 and E.1) are **particularly significant**, as they can be **readily applied to many existing PbRL analyses without any modification to the underlying algorithms**. This shows that the commonly observed $e^B$ dependence is **not fundamental**, but rather an artifact of loose analysis—an insight we find both surprising and broadly useful.\n\nAs we believe that all of your concerns have been thoroughly addressed and that our theoretical contributions are substantial, we respectfully ask the reviewer to reconsider the evaluation and recommend our paper for acceptance.\n\n>[1] Chen, Mingyu, et al. \"Avoiding exp (rmax) scaling in rlhf through preference-based exploration.\" arXiv 2025.\n\\\n[2] Di, Qiwei, Jiafan He, and Quanquan Gu. \"Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback.\" ICML 2025.\n\n---\n- ### **We Typically Consider Small $K$ Settings**\nThe reviewer raised a concern about the large-$K$ scenario (i.e., when the maximum size of the assortment is large). However, in practice, **small $K$ is typically used**. For example, Ouyang et al. (2022) utilize ranking feedback of length 4 to 9.\n\nLarge-$K$ settings are generally unrealistic, as it is difficult to obtain accurate long rankings from human annotators. Therefore, we believe **this concern should not be considered a weakness of our paper.**\n\n\n---\n- ### **Linear Model Is a Foundational Starting Point**\nAssuming linear rewards is a **widely adopted approach** for analyzing the statistical efficiency of PbRL, including dueling bandits. This modeling choice has been used in numerous prior works—such as Saha (2021), Wu and Sun (2023), Saha et al. (2023), Zhu et al. (2023), Di et al. (2024), Thekumparampil et al. (2024), among others—as a foundational tool for theoretical analysis. \n\nTherefore, we strongly believe that **this assumption should not be regarded as a unique weakness of our work, nor as a reason for rejection.** The linear assumption serves as a fundamental starting point for understanding how the learning mechanism operates in PbRL. If certain phenomena fail to hold in this foundational setting, it is difficult to expect them to hold in more complex scenarios. Hence, we believe that the contributions outlined above are both **meaningful and valuable to the community**. \n\n---\n- ### **Robustness to Model Misspecification in Experiments**\nMoreover, **in our real-world experiment, there is indeed model misspecification**: the features $\\phi(x, a)$ and the true rewards come from different models. Specifically, the features $\\phi(x, a)$ are extracted from the last hidden layer of Gemma-2B, while the true reward model is based on Mistral-7B. Despite this mismatch, our method still performs well, demonstrating a notable degree of **robustness to model misspecification**.\n\n---\n- ### **Extension to General Function Approximation**\nTo further **address the reviewer’s concern about the linearity and PL model assumptions**, we show that  **MAU (Maximizing Average Uncertainty) method can be extended to general function classes** (i.e., general preference models), following a similar approach to Theorem 4 of Das et al. (2024). Specifically, given a function class $\\mathcal{F}$, we define a confidence set \n$$\nb_t(x, a, a'):= \\max_\\{f_1, f_2 \\in \\mathcal{C}\\_t (\\mathcal{F}, \\delta)}|f_1(x,a,a') - f_2(x,a,a')|.\n$$\nWe then select the reference action-assortment pair $(\\bar{a}\\_t, S_t)$ according to:\n$$\n    (\\bar{a}\\_t, S_t) := \\arg\\max\\_{\\bar{a}, S \\,s.t.\\, \\bar{a} \\in S} \\frac{1}{|S|} \\sum\\_{a \\in S} b_t(x, a, \\bar{a}).\n$$\nThen, we can bound the suboptimality as:\n$$\n    \\text{SubOpt}(T) \\leq \\frac{2}{T} \\sum\\_{t=1}^T b_t(x_t, \\hat{\\pi}\\_t(x_t), \\pi^\\star(x_t))\n    \\leq  \\frac{2}{T} \\sum\\_{t=1}^T \\frac{1}{|S_t|} \\sum\\_{a\\in S_t} b_t(x, a, \\bar{a}\\_t)\n\\leq  \\frac{2}{T} \n\\sqrt{\\sum_{t=1}^T \\frac{1}{|S_t|}}\n\\sqrt{\\sum_{t=1}^T\\sum\\_{a\\in S_t} b_t(x, a, \\bar{a}\\_t)^2}\n\\leq \\frac{2}{T} \n\\sqrt{\\sum\\_{t=1}^T \\frac{1}{|S_t|}}\n\\sqrt{\\frac{1}{TK} + d_{\\mathcal{E},\\mathcal{F}} + 4 d_{\\mathcal{E},\\mathcal{F}} \\beta_T \\log (TK)\n}\n= \\tilde{\\mathcal{O}}\\left( \n\\frac{1}{T} \n\\sqrt{\\sum_{t=1}^T \\frac{1}{|S_t|}\n\\cdot d_{\\mathcal{E}} \\log\\mathcal{N_\\mathcal{F}}\n}\n\\right),\n$$\nwhere $d_{\\mathcal{E},\\mathcal{F}}$ and $\\mathcal{N_\\mathcal{F}}$ are  the covering number and Eluder dimension of $\\mathcal{F}$, respectively. The final inequality follows from Lemma 2 of [1], with minor modifications. Therefore, this result suggests that **multiple-option feedback can lead to improved sample complexity for general function classes** (including LLMs) as well.\n\nWe hope that this additional result can addresses the reviewer’s concern regarding the linear reward assumption and PL model assumption.\n\n>[1] Russo, Daniel, and Benjamin Van Roy. \"Eluder dimension and the sample complexity of optimistic exploration.\" NeurIPS 2013.\n\n---\n- #### **Q1. How do you decide between PL and RB losses?**\n\nOur theoretical results show that the suboptimality gaps of the PL and RB losses are comparable, especially as $T$ becomes large. While the RB loss may offer a slightly tighter non-leading term, this difference is negligible for large $T$. Therefore,  **both losses are statistically equivalent in the asymptotic regime**.\n\nHowever, the **RB loss incurs higher computational cost** due to the rank-breaking procedure. Therefore, we **recommend using the PL loss** when handling ranking feedback (just for its computational efficiency, not due to any statistical advantage).\n\n---\n- #### **Q2. Did you consider comparing M-AUPO against such methods (e.g., PPO + BT model in [35] or DPO [38])?**\n\nThe methods proposed in Ouyang et al. (2022) and Rafailov et al. (2023) operate purely in the *offline setting*—they optimize over a fixed dataset and do not make decisions about which actions to collect next. In contrast, M-AUPO is designed for the *online setting*, where the learner must actively select actions (or assortments) at each round. Therefore, a **direct comparison would be methodologically inappropriate**.\n\nInstead, we compare against two baselines more relevant to the online RLHF setting:\n\n- \"Uniform\", which selects actions uniformly at random (already included in Appendix I, and will be moved to the main paper in the revision), and\n- \"Best&Ref\", which selects an action pair ($K=2$) using the current policy and a reference policy (e.g., uniform random or SFT), respectively—following a selection mechanism similar to those in Online GSHF [1] and XPO [2]..\n\nWe believe \"Best&Ref\" is the most appropriate baseline for online RLHF, as it closely mirrors how actions are selected in many existing online RLHF algorithms. Note again that DPO is best understood as an optimization algorithm for the offline setting, and thus not directly comparable in terms of online action selection or assortment design.\n\nThe results demonstrate that our method either **consistantly and significantly outperforms** all other baselines or is second-best with a minimal gap. (*PL loss only, due to limited space.*)\n\n**i) Synthetic experiment ($T=200$)**\n\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|0.1629|0.1671|0.1575|**0.0396**|\n|3|0.1587|0.1654|0.1482|**0.0331**|\n|5|0.1539|0.0797|0.1534|**0.0244**|\n|7|0.1547|0.0561|0.1551|**0.0204**|\n\n**ii) Realworld experiment ($T=20,000$)**\n\n**ii-1)** TREC-DL dataset\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|6.115|3.579|3.465|**3.204**|\n|3|5.999|2.964|3.458|**2.381**|\n|5|5.971|2.548|3.430|**2.052**|\n\n**ii-2**) Nectar dataset\n|K|DopeWolfe|Uniform|Best&Ref|M-AUPO (ours)|\n|-|-|-|-|-|\n|2|1.418|**1.279**|1.291|1.285|\n|3|1.246|1.243|1.275|**1.019**|\n|5|1.232|1.116|1.257|**0.997**|\n\n> [1] Xiong, Wei, et al. \"Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint.\" ICML 2024\n\\\n[2] Xie, Tengyang, et al. \"Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF.\" ICLR 2025\n---\n Please don’t hesitate to reach out if you have any further questions!"}]

Author rebuttal:

Meta-review: The paper improves preference-based reinforcement learning by providing the theoretical analysis with sub-group ranking feedback.

As shown in early dueling bandits research, if multiple options are ranked simultaneously, the algorithms could be more efficient than traditional pairwise comparisons (e.g. Multi-dueling Bandits with Dependent Arms, UAI 2017).

Generating the results to full RL settings is important to apply PbRL to large-scale real world problems.

The authors further confirmed that increasing the maximum selection size K improves performance, aligning with the reference and the paper's own theoretical predictions. These efforts highlight the advantage of utilizing ranking feedback to achieve more data-efficient and scalable PbRL.
Decision: Accept (poster)