# Optimal Design for Human Feedback

Subhojyoti Mukherjee  Anusha Lalitha  Kousha Kalantari  Aniket Deshmukh  Ge
Liu  Yifei Ma  Branislav Kveton

###### Abstract

Learning of preference models from human feedback has been central to recent
advances in artificial intelligence. Motivated by this progress, and the cost
of obtaining high-quality human annotations, we study the problem of data
collection for learning preference models. The key idea in our work is to
generalize optimal designs, a tool for computing efficient data logging
policies, to ranked lists. To show the generality of our ideas, we study both
absolute and relative feedback on items in the list. We design efficient
algorithms for both settings and analyze them. We prove that our preference
model estimators improve with more data and so does the ranking error under
the estimators. Finally, we experiment with several synthetic and real-world
datasets to show the statistical efficiency of our algorithms.

##  1 Introduction

_Reinforcement learning with human feedback (RLHF)_ has proved to be very
effective in training and fine-tuning _large language models (LLMs)_ (Casper
et al., 2023; Yang et al., 2023; Shen et al., 2023). The main difference from
classic _reinforcement learning (RL)_ (Sutton and Barto, 2018) is that the
agent learns from human feedback, which is expressed in the form of
preferences among different potential choices (Wu and Sun, 2023). The human
feedback allows LLMs to be adapted beyond the distribution of data that was
used for their pre-training and generate answers that are more preferred by
humans (Casper et al., 2023).

The key step in RLHF that allows adaptation to human feedback is the learning
of a preference model. When the relative feedback is between two choices, the
_Bradley-Terry-Luce model_ (Bradley and Terry, 1952) can be used. When the
relative feedback is among multiple choices, the _Plackett-Luce (PL) model_
(Plackett, 1975; Luce, 2012) can be used. Learning a good preference model can
be viewed as learning to rank answers to questions, which is a standard
setting of learning to rank. Many papers have been written on learning to
rank, both in offline (Burges, 2010) and online (Radlinski et al., 2008;
Kveton et al., 2015a; Szörényi et al., 2015; Sui et al., 2018; Lattimore et
al., 2018) settings.

In this work, we study the problem of data collection for learning a
preference model from human feedback. We formalize the problem as follows. We
have a collection of $L$ lists, each with $K$ items. The lists represent
questions, and the items are potential answers. The goal of the agent is to
learn to rank all items in all lists. The agent can query humans for feedback.
In each query, the human is shown all items in one list and provides feedback
on them. We study both the absolute and relative feedback settings. The
absolute feedback could be noisy ratings of all items in a list. The relative
feedback would be their order. The agent has a budget for the number of
queries. To learn efficiently within the budget, the agent needs to ask for
feedback on the most informative lists, which allows it to learn to rank all
other lists. Our main contribution is an efficient algorithm for computing the
distribution over most informative lists.

Our work touches on many classic topics and recent works. For instance, the
recent popularity of RLHF led to major theoretical developments, including
analyses of regret minimization in RLHF (Chen et al., 2022; Wang et al., 2023;
Wu and Sun, 2023; Xiong et al., 2023; Opoku-Agyemang, 2023; Saha et al.,
2023). These works propose and analyze adaptive algorithms that interact with
the environment to learn highly rewarding policies. In practice, though, such
policies are hard to deploy because they may over-explore initially, which
harms user experience, and may need to be recomputed frequently (Dudik et al.,
2014; Swaminathan and Joachims, 2015). Zhu et al. (2023b) study RLHF from
ranking feedback in the offline setting with a fixed dataset. We focus on
collecting a good dataset for offline learning to rank with both absolute and
ranking feedback. The data logging problem is framed as an optimal design. The
optimal design aims to find a distribution over the most informative choices
that minimize uncertainty over some metric (Pukelsheim, 2006; Fedorov, 2013).
This distribution generally solves an optimization problem and has some nice
properties, like sparsity. The main technical contribution of this work is a
matrix generalization of the Kiefer-Wolfowitz theorem (Kiefer and Wolfowitz,
1960), which allows us to formulate optimal designs over ranked lists and
explore them efficiently. Optimal designs have become a standard tool in
exploration (Katz-Samuels et al., 2020; Lattimore and Szepesvári, 2020; Katz-
Samuels et al., 2021; Mukherjee et al., 2022; Jamieson and Jain, 2022). We
contribute to these works by proposing the first pure exploration algorithm
for ranked lists based on optimal designs. More precisely, our setting can be
viewed as fixed-budget _best-arm identification (BAI)_ (Audibert et al., 2009;
Yang and Tan, 2021; Azizi et al., 2022; Lalitha et al., 2023), where the best
arm corresponds to all lists being correctly ranked. We also study how to
minimize the maximum prediction error. In this case, the goal is to minimize
the estimation error of the unknown model parameter for the purpose of ranking
items (Riquelme et al., 2017; Fontaine et al., 2021; Mukherjee et al., 2023).

We make the following contributions:

(1) We develop a novel approach for logging data for learning to rank from
human feedback. The key idea is to generalize the Kiefer-Wolfowitz theorem
(Kiefer and Wolfowitz, 1960) to matrices, which then allows us to compute
information-gathering policies for ranked lists.

(2) In the absolute feedback model, we propose an algorithm that uses an
optimal design to collect absolute human feedback and a least-squares
estimator for the mean rewards of items that learns from it. To our best
knowledge, this is the first combination of the two that results in an
efficient algorithm with statistical guarantees, for both the estimated mean
rewards of items and a ranking loss.

(3) In the ranking feedback model, we propose an algorithm that uses an
optimal design to collect ranking human feedback and a _maximum likelihood
estimator (MLE)_ (Zhu et al., 2023b) that learns from it. This is the first
combination of the two that yields a computationally and statistically
efficient algorithm that can be analyzed. These results mimic our absolute
feedback results and show the generality of our proposed framework.

(4) We compare our algorithms to multiple baselines on several synthetic and
real-world datasets. We observe that our algorithm achieves lower ranking loss
than other baselines.

##  2 Setting

Notation: Let $[K]$ denote $\\{1,2,\ldots,K\\}$. Let $\triangle^{L}$ be the
probability simplex over $[L]$. For any distribution $\pi\in\triangle^{L}$, we
have $\sum_{i=1}^{L}\pi(i)=1$. For any function $f$ and $k$, we have
$\widetilde{O}(f(n))=O(f(n)\log^{k}f(n))$, i.e., $\widetilde{O}(.)$ ignores
the log factor. Let $\Pi_{2}(K)=\\{(j,k):j<k;j,k\in[K]\\}$, i.e., it is the
set of all ordered pairs where the first coordinate is strictly less than the
second one. Let
$\|\mathbf{x}\|^{2}_{\mathbf{A}}=\mathbf{x}^{\top}\mathbf{A}\mathbf{x}$ for
any positive-definite $\mathbf{A}\in\mathbb{R}^{d\times d}$ and
$\mathbf{x}\in\mathbb{R}^{d}$.

Setup: We consider a problem of learning to rank $L$ lists consisting of $K$
items each. An item $k\in[K]$ in list $i\in[L]$ is represented by its feature
vector $\mathbf{x}_{i,k}\in\mathcal{X}$, where
$\mathcal{X}\subseteq\mathbb{R}^{d}$ is the set of all feature vectors. The
relevance of items is represented by their mean rewards. The mean reward of
item $k$ in list $i$ is $\mathbf{x}_{i,k}^{\top}\bm{\theta}_{*}$, where
$\bm{\theta}_{*}\in\mathbb{R}^{d}$ is an unknown parameter. Without loss of
generality, we assume that
$\mathbf{x}_{i,j}^{\top}\bm{\theta}_{*}>\mathbf{x}_{i,k}^{\top}\bm{\theta}_{*}$
for any $j<k$ and every list $i$. This means that the original order is
optimal. The learner does not know it. At every round $t$, the learner selects
a list $I_{t}$, and the human labeler provides noisy feedback on the rewards
of all items in it. The goal is to design a strategy for selecting lists such
that after $n$ rounds of interactions, the learner learns the optimal order of
$K$ items in each list. Our setup resembles the problem of _best arm
identification (BAI)_ (Bubeck et al., 2009; Audibert et al., 2009; Yang and
Tan, 2021; Azizi et al., 2022) under a fixed budget where the goal is to
identify the arm with the highest mean in a stochastic multi-armed bandit.

Feedback Model: In this paper, we consider two models of human feedback: (1)
absolute and (2) ranking.

(1) Under the absolute feedback model, for every round $t$, the human labeler
provides a reward for each item $k\in[K]$ in list $I_{t}$ selected by the
learner. Specifically, the learner observes noisy rewards for all $k\in[K]$ in
list $I_{t}$,

$\displaystyle y_{t,k}=\mathbf{x}_{I_{t},k}^{\top}\bm{\theta}_{*}+\eta_{t,k},$
(1)

where $\eta_{t,k}$ is zero-mean $1$-sub-Gaussian noise that is independent
across items and rounds. In other words, the reward provided by human labelers
is stochastic, with mean $\mathbf{x}_{I_{t},k}^{\top}\bm{\theta}_{*}$ and
additive independent noise. This is similar to the document-based click model
(Chuklin et al., 2022).

(2) Under the ranking feedback model, for every round $t$, the human labeler
provides a rank order over all $K$ items in list $I_{t}$ selected by the
learner. Specifically, the learner observes a permutation over the $K$ items
in list $I_{t}$ sampled from the _Plackett-Luce (PL)_ model (Plackett, 1975;
Luce, 2012). Such ranking feedback model has been studied in Zhu et al.
(2023b); Ji et al. (2023). Let $\sigma_{t}:[K]\rightarrow[K]$ denote the
permutation provided by the human labeler at round $t$, where $\sigma_{t}(k)$
denotes the item placed at $k$-th rank by the human labeler for list $I_{t}$
at round $t$. Then, the PL model states that the probability that permutation
$\sigma_{t}$ is generated at round $t$ is

$\displaystyle\mathbb{P}\left(\sigma_{t}\right)=\prod_{k=1}^{K}\frac{\exp\left(\mathbf{x}_{I_{t},\sigma_{t}(k)}^{\top}\bm{\theta}_{*}\right)}{\sum_{j=k}^{K}\exp\left(\mathbf{x}_{I_{t},\sigma_{t}(j)}^{\top}\bm{\theta}_{*}\right)}.$
(2)

The PL model provides a probabilistic ranking using the underlying mean
rewards with unknown parameter $\bm{\theta}_{*}$.

Objective: At the end of $n$ rounds, the learner outputs an estimated
permutation $\widehat{\sigma}_{n,i}$ for each list $i\in[L]$, where
$\widehat{\sigma}_{n,i}(k)$ denotes the item placed at $k$-th rank by the
learner for list $i$. We define the _ranking loss_ after $n$ rounds as
color=red!20,size=,inline,]B: Replace all occurrences of ”simple regret” with
”ranking loss”.

$\displaystyle\mathrm{R}_{n}=\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbb{I}\\{\widehat{\sigma}_{n,i}(j)>\widehat{\sigma}_{n,i}(k)\\}\,.$
(3)

color=red!20,size=,inline,]B: Replace all occurrences of $\mathrm{SR}_{n}$
with $\mathrm{R}_{n}$. This is a worst-case ranking loss. Roughly speaking, it
is zero when the hardest to sort list among $i\in[L]$ is sorted optimally.
While there are other possible losses, such as the _mean reciprocal rank
(MRR)_ and _normalized discounted cumulative gain (NDCG)_ , we choose the
ranking loss defined in (3) to simplify our presentation (Dadkhahi and
Negahban, 2018; Ermis et al., 2020; Gampa and Fujita, 2021). In the following
section, we introduce the idea of optimal design (Pukelsheim, 2006; Fedorov,
2013) that enables the learner to minimize the expected ranking loss within
the budget of $n$ rounds. We note that our algorithm designs and analyses can
be trivially extended to the setting where the maximization over $i\in[L]$ in
(3) is replaced by a sum.

##  3 Optimal Design and Matrix Kiefer-Wolfowitz

This section introduces a unified strategy for selecting lists $I_{t}$ at
rounds $t$ for both absolute and ranking feedback.

First, we note that to learn the optimal order of items in all lists, the
learner needs to estimate the unknown parameter $\bm{\theta}_{*}$ well. In
this work, the learner uses a _maximum-likelihood estimator (MLE)_
$\widehat{\bm{\theta}}_{n}$ to estimate $\bm{\theta}_{*}$. After that, it
orders the items in all lists $i\in[L]$ according to their estimated mean
rewards $\\{\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}\\}_{k=1}^{K}$ in
descending order to obtain the permutation $\widehat{\sigma}_{n,i}$. If the
learner learns an estimate $\widehat{\bm{\theta}}_{n}$ that minimizes the
prediction error
$\left(\mathbf{x}_{i,k}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\right)^{2}$
for all items $k\in[K]$ in list $i$, then it can output an estimated
permutation $\widehat{\sigma}_{n,i}$ that is closer to the optimal order.
Moreover, by minimizing the maximum prediction error over all lists, the
learner can learn the optimal order over all lists and minimize the ranking
loss in (3). Thus, we are concerned with optimizing the _maximum prediction
error_

$\displaystyle\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\left(\mathbf{a}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\right)^{2}$
$\displaystyle=\max_{i\in[L]}\mathbf{Tr}\left(\mathbf{A}_{i}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)^{\top}\mathbf{A}_{i}\right),$
(4)

where $\mathbf{A}_{i}$ is the matrix of feature vectors associated with list
$i$ and $\mathbf{a}\in\mathbf{A}_{i}$ represents a column in matrix
$\mathbf{A}_{i}$. Under absolute feedback, the columns of $\mathbf{A}_{i}$ are
the feature vectors of items in list $i$. Under ranking feedback, the columns
of $\mathbf{A}_{i}$ are the differences of feature vector. Therefore,
$\mathbf{A}_{i}$ is human-feedback specific.

We show in Sections 4 and 5 that the learner can minimize the prediction error
in (4) by sampling according to a fixed distribution
$\pi_{*}\in\triangle^{L}$. That is, the probability of selecting list $i$ at
round $t$ is $\mathbb{P}(I_{t}=i)=\pi_{*}(i)$. The distribution $\pi_{*}$ is a
minimizer of

$\displaystyle
g(\pi)=\max_{i\in[L]}\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\mathbf{A}_{i}),$
(5)

where $\mathbf{V}_{\pi}$ is a design matrix defined as

$\displaystyle\mathbf{V}_{\pi}=\sum_{i=1}^{L}\pi(i)\mathbf{A}_{i}\mathbf{A}_{i}^{\top}.$
(6)

The optimal design aims to find the distribution $\pi_{*}$. If the learner
samples lists according to $\pi_{*}$ for $n$ rounds, it can minimize the
maximum prediction error in (4) and also the ranking loss in (3).

The problem of finding a design $\pi_{*}$ minimizing $g$ is called the
G-optimal design. The Kiefer-Wolfowitz theorem characterizes the minimum of
$g$ and the support of $\pi_{*}$ (Lattimore and Szepesvári, 2020). The
original Kiefer-Wolfowitz theorem is for least-squares estimation, where
$\mathbf{A}_{i}$ are feature vectors. We generalize it to estimate the mean
rewards of items in a list from absolute and ranking feedback, where
$\mathbf{A}_{i}$ are matrices of feature vectors representing list $i$. Now we
present our first result, where we generalize the Kiefer-Wolfowitz theorem
(Kiefer and Wolfowitz, 1960) to matrices $\mathbf{A}_{i}$. This generalization
allows us to go from a design over feature vectors to a design over sets of
items, which are represented by matrices.

######  Theorem 3.1.

(Matrix Kiefer-Wolfowitz) Consider a set of $L$ matrices
$\mathbf{A}_{i}\in\mathbb{R}^{d\times M}$ for $i\in[L]$. Suppose the column
space of all the matrices together spans $\mathbb{R}^{d}$. Let
$\mathbf{V}_{\pi}$ be the design matrix in (6). Then the following are
equivalent:

  1. (a)

$\pi_{*}$ is a minimizer of $g(\pi)$ defined in (5).

  2. (b)

$\pi_{*}$ is a maximizer of
$f(\pi)=\log\operatorname{det}\left(\mathbf{V}_{\pi}\right)$.

  3. (c)

$g\left(\pi_{*}\right)=d$.

Furthermore, there exists a minimizer $\pi_{*}$ of $g(\pi)$ such that
$\left|\operatorname{Supp}\left(\pi_{*}\right)\right|\leq d(d+1)/2$.

###### Proof.

Our technique generalizes the proof of the Kiefer-Wolfowitz theorem in
Lattimore and Szepesvári (2020). The key observation is that even in our
generalization, where $\mathbf{A}_{i}$ is a matrix instead of a vector, the
design matrix $\mathbf{V}_{\pi}$ is positive definite. Using this, we
establish the following two key facts used in the original proof. First, we
show that $f$ is concave in $\pi$ and that the gradient of $f(\pi)$ with
respect to $\pi(i)$ is given by

$\displaystyle\nabla
f(\pi)_{\pi(i)}=\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\mathbf{A}_{i}).$

Next we show that
$\sum_{i\in[L]}\pi(i)\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\mathbf{A}_{i})=d.$
The complete proof is given in Appendix B. ∎

From the equivalence in Theorem 3.1, it follows that the learner should solve
the optimal design

$\displaystyle\pi_{*}=\max_{\pi\in\triangle^{L}}f(\pi)=\max_{\pi\in\triangle^{L}}\log\det(\mathbf{V}_{\pi}),$
(7)

and sample according to $\pi_{*}$ to minimize the maximum prediction error in
(4). Note that the optimization problem in (7) is convex and hence is easy to
solve. In the following sections, we use Theorem 3.1 to bound the maximum
prediction error and ranking loss for both absolute feedback and ranking
feedback.

##  4 Learning with Absolute Feedback

This section is organized as follows. First, we present the algorithm that
logs absolute feedback and the MLE estimator that learns from it. Then, we
show that the optimal design $\pi_{*}$ and Theorem 3.1 lead to a low maximum
prediction error with a high probability. Finally, we bound the expected
ranking loss incurred by our algorithm.

###  4.1 Algorithm Dope

Now we present our algorithm for absolute feedback called D-optimal design
(Dope). The algorithm has three parts. First, we solve the optimal design in
(7), where the matrix for list $i$ is
$\mathbf{A}_{i}=[\mathbf{x}_{i,1},\mathbf{x}_{i,2},\ldots,\mathbf{x}_{i,K}]\in\mathbb{R}^{d\times
K}$ and $\mathbf{x}_{i,k}$ is the feature vector of item $k$ in list $i$. The
solution to (7) is a data logging policy $\pi_{*}$. Second, the policy
$\pi_{*}$ is used to collect human feedback for $n$ rounds. Specifically, in
round $t\in[n]$, the learner samples $I_{t}\sim\pi_{*}$ and observes $y_{t,k}$
for $k\in[K]$, as defined in (1). Since the sampling distribution $\pi_{*}$ is
fixed, we have a fixed-design algorithm. Finally, we estimate the unknown
model parameter as

$\displaystyle\widehat{\bm{\theta}}_{n}=\overline{\mathbf{\Sigma}}_{n}^{-1}\sum_{t=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{I_{t},k}y_{t,k},$
(8)

where we define the covariance matrix
$\overline{\mathbf{\Sigma}}_{n}=n\mathbf{\Sigma}_{n}$ where

$\displaystyle\mathbf{\Sigma}_{n}=\frac{1}{n}\sum_{t=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{I_{t},k}\mathbf{x}_{I_{t},k}^{\top}.$
(9)

Finally, the learner orders the items in every list $i\in[L]$ according to
their estimated mean rewards
$\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}$ in descending order to
obtain the permutation $\widehat{\sigma}_{n,i}$.

When the noise is sub-Gaussian, our MLE estimate is the same as an _ordinary
least-squares (OLS)_ estimate. In other words, the optimal design under
absolute feedback logs data for a least-squares problem by minimizing the
covariance matrix of the OLS estimator (Lattimore and Szepesvári, 2020;
Jamieson and Jain, 2022). We present the full pseudo-code in Algorithm 1 in
Appendix F.

###  4.2 Maximum Prediction Error Under Absolute Feedback

In this section, we analyze the prediction error of our fixed design algorithm
that logs absolute feedback according to $\pi_{*}$. First, we prove a lemma
that uses the optimal design $\pi_{*}$ to bound
$\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}_{n}^{-1}}$
where we define the unnormalized covariance matrix

$\displaystyle\overline{\mathbf{\Sigma}}_{n}=n\mathbf{\Sigma}_{n}=\sum_{t=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{I_{t},k}\mathbf{x}_{I_{t},k}^{\top}.$
(10)

We now bound the prediction error. To this effect, we first prove the
following lemma.

######  Lemma 4.1.

Fix design $\pi_{*}$ and budget $n$. Let the number of times that any list
$i\in[L]$ is seen, $n\pi_{*}(i)$, be an integer. Then we have

$\displaystyle\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}_{n}^{-1}}=\tfrac{d}{n}.$

###### Proof.

We start by noting that for all $i\in[L]$,

$\displaystyle\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}_{n}^{-1}}=\mathbf{Tr}(\mathbf{A}_{i}^{\top}\overline{\mathbf{\Sigma}}_{n}^{-1}\mathbf{A}_{i}).$

Since we assume that $n\pi_{*}(i)$ is an integer, the covariance matrix
$\mathbf{\Sigma}_{n}$ is invertible. This is because the optimal design
$\pi_{*}$ outputs a set of lists that spans $\mathbb{R}^{d}$ and avoids
degenerate solutions. Then, we can rewrite the above as

$\displaystyle\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}^{-1}_{n}}=\mathbf{Tr}(\mathbf{A}_{i}^{\top}\overline{\mathbf{\Sigma}}_{n}^{-1}\mathbf{A}_{i})$
$\displaystyle=\mathbf{Tr}\left(\mathbf{A}_{i}^{\top}\left(\sum_{t=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{I_{t},k}\mathbf{x}_{I_{t},k}^{\top}\right)^{-1}\mathbf{A}_{i}\right)$
$\displaystyle\overset{(a)}{=}\frac{1}{n}\mathbf{Tr}\left(\mathbf{A}_{i}^{\top}\left(\sum_{i=1}^{L}\pi_{*}(i)\sum_{k=1}^{K}\mathbf{x}_{i,k}\mathbf{x}_{i,k}^{\top}\right)^{-1}\mathbf{A}_{i}\right)$
$\displaystyle=\frac{1}{n}\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}^{-1}_{\pi_{*}}\mathbf{A}_{i}),$

where $(a)$ follows from the fact that given a fixed design $\pi_{*}$ and
budget $n$, list $i$ is seen exactly $n\pi_{*}(i)$ times. Now we apply Theorem
3.1, use our definition of $g(\pi_{*})$, and get that $g(\pi_{*})=d$. Thus

$\displaystyle\max_{i\in[L]}\mathbf{Tr}(\mathbf{A}_{i}^{\top}\overline{\mathbf{\Sigma}}^{-1}_{n}\mathbf{A}_{i})=\frac{d}{n}.$

The claim of the lemma follows. ∎

Now that we have a bound on the maximum sum of the squared error of the mean
reward estimates, we can proceed to get a bound on the maximum prediction
error. This is shown in the following theorem.

######  Theorem 4.2.

(Maximum Prediction Error) Fix $\delta\in[0,1)$. Then, with probability
$1-\delta$, the maximum prediction error after $n$ rounds is bounded as

$\displaystyle\max_{i\in[L]}\ $
$\displaystyle\mathbf{Tr}\left(\mathbf{A}_{i}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)^{\top}\mathbf{A}_{i}\right)$
$\displaystyle\leq\widetilde{O}\left(\dfrac{d^{2}\log(1/\delta)}{n}\right).$

###### Proof.

We start with

$\displaystyle\max_{i\in[L]}\mathbf{Tr}\left(\mathbf{A}_{i}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)^{\top}\mathbf{A}_{i}\right)$
$\displaystyle=\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\left(\mathbf{a}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\right)^{2}$
$\displaystyle=\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\left(\mathbf{a}^{\top}\overline{\mathbf{\Sigma}}_{n}^{-1/2}\overline{\mathbf{\Sigma}}_{n}^{1/2}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\right)^{2}$
$\displaystyle\overset{(a)}{\leq}\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}_{n}^{-1}}\|\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\|^{2}_{\overline{\mathbf{\Sigma}}_{n}}$
$\displaystyle\overset{(b)}{=}\underbrace{\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}_{n}^{-1}}}_{\textbf{Part
I}}\underbrace{n\|\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\|^{2}_{\mathbf{\Sigma}_{n}}}_{\textbf{Part
II}},$ (11)

where $(a)$ follows from the Cauchy-Schwarz inequality and $(b)$ follows from
the definition of $\overline{\mathbf{\Sigma}}_{n}$.

Part I captures the efficiency of the data collection process and depends on
the optimal design. The quantity represents the maximum sum of squared
standard errors of the mean reward estimates of all items in any list under
the empirical covariance matrix $\mathbf{\Sigma}_{n}$. By Lemma 4.1, it is

$\displaystyle\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}^{-1}_{n}}=\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi_{*}}^{-1}\mathbf{A}_{i})=\frac{d}{n}.$

Part II measures the quality of the MLE $\widehat{\bm{\theta}}_{n}$, and
depends on the squared distance of $\widehat{\bm{\theta}}_{n}$ from the true
parameter $\bm{\theta}_{*}$, under the empirical covariance matrix
$\mathbf{\Sigma}_{n}$. For Part II, we use Lemma C.1 in Section C.1 and get

$\displaystyle\left\|\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\right\|^{2}_{\mathbf{\Sigma}_{n}}\leq
4\left(\frac{2d\log(6)+\log(1/\delta)}{n}\right)$

The main claim follows from combining the upper bounds on Parts I and II in
(11). ∎

Theorem 4.2 shows that maximum prediction error under absolute feedback
decreases inversely with the number of rounds $n$, when the learner selects
lists using the optimal design $\pi_{*}$. In Lemma 4.1 and Theorem 4.2, we
assume that the number of times that each list is chosen is an integer. If the
allocations are not integers, rounding errors arise. To handle such scenarios,
efficient rounding procedures have been established (Pukelsheim, 2006; Fiez et
al., 2019; Katz-Samuels et al., 2020). This would only introduce a constant
multiplicative factor $(1+\beta)$ in our bounds (Lattimore and Szepesvári,
2020) (see notes in Chapter 21) for some $\beta>0$. For simplicity, we omit
this factor in our derivation. Finally, because of assuming integer
allocations, we do not need to initialize the covariance matrix by
$\lambda\mathbf{I}_{d}$, for some $\lambda>0$. This ensures its invertibility
in Zhu et al. (2023b).

###  4.3 ranking loss Under Absolute Feedback

In this section, we bound the expected ranking loss under absolute feedback.
Recall from Section 2 that we assume that the original order of items in each
list is optimal. With this in mind, we define the _gap_ between the mean
rewards of items $j$ and $k$ in list $i$ as
$\Delta_{i,j,k}=(\mathbf{x}_{i,j}-\mathbf{x}_{i,k})^{\top}\bm{\theta}_{*}$,
for any $i\in[L]$ and $(j,k)\in\Pi_{2}(K)$.

######  Theorem 4.3.

(Expected ranking loss) The expected ranking loss under absolute feedback, can
be bounded as

$\displaystyle\mathbb{E}\left[\mathrm{R}_{n}\right]\leq\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}2\exp\left(-\dfrac{n\Delta^{2}_{i,j,k}}{2d}\right)$

###### Proof.

From the definition of ranking loss, we have

$\displaystyle\mathbb{E}\left[\mathrm{R}_{n}\right]=$
$\displaystyle\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbb{E}\left[\mathbb{I}\\{\widehat{\sigma}_{n,i}(j)>\widehat{\sigma}_{n,i}(k)\\}\right]$
$\displaystyle=$
$\displaystyle\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbb{P}\left(\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}>\mathbf{x}_{i,j}^{\top}\widehat{\bm{\theta}}_{n}\right).$

At the end of round $n$, the probability of predicting a sub-optimal item $k$
above item $j$ is
$\mathbb{P}\left(\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}>\mathbf{x}_{i,j}^{\top}\widehat{\bm{\theta}}_{n}\right)$.
Then we show that this probability is bounded from above by the sum of
probabilities
$\mathbb{P}\left(\mathbf{x}_{i,j}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})<-\Delta_{i,j,k}\right)$
and
$\mathbb{P}\left(\mathbf{x}_{i,k}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})>\Delta_{i,j,k}\right)$.
Finally, we bound each of these from above by
$\exp\left(-\frac{n\Delta^{2}_{i,j,k}}{2d}\right)$ using a concentration
inequality for sub-Gaussian random variables derived in Lemma 4.1. The full
proof is in Section C.2. ∎

Theorem 4.3 says that $\mathbb{E}\left[\mathrm{SR}_{n}\right]$ decays
exponentially with budget $n$. The exponent is proportional to the squared
gaps between mean rewards of all pairs of items $(j,k)\in\Pi_{2}(K)$ in the
list and inversely proportional to $d$. Although we do not derive a matching
lower bound for $\mathbb{E}\left[\mathrm{SR}_{n}\right]$, its exponential
decrease with budget $n$ and squared gaps is similar to the previously
observed dependencies in the fixed-budget BAI literature (Audibert et al.,
2009; Bubeck et al., 2009; Jamieson and Nowak, 2014; Yang and Tan, 2021; Azizi
et al., 2022; Lalitha et al., 2023).

##  5 Learning with Ranking Feedback

This section is organized similarly to Section 4. First, we present the
algorithm that logs ranking feedback and the MLE estimator that learns from
it. Then, we show that the optimal design $\pi_{*}$ and Theorem 3.1 lead to a
low maximum prediction error with a high probability. Finally, we bound the
expected ranking loss incurred by our algorithm.

###  5.1 Algorithm Dope

Now we present Dope for ranking feedback. The algorithm is similar to the
absolute feedback algorithm in Section 4 and has three parts. First, we solve
the optimal design in (7), where the matrix for list $i$ is
$\mathbf{A}_{i}=[\mathbf{z}_{i,j,k}]_{(j,k)\in\Pi_{2}(K)}\in\mathbb{R}^{d\times
K(K-1)/2}$ and $\mathbf{z}_{i,j,k}=\mathbf{x}_{i,j}-\mathbf{z}_{i,k}$ denotes
the difference between feature vectors of items $j$ and $k$ in list $i$. The
solution to (7) is a data logging policy $\pi_{*}$. Second, the policy
$\pi_{*}$ is used to collect human feedback for $n$ rounds. Specifically, in
round $t\in[n]$, the learner samples a list $I_{t}\sim\pi_{*}$ and observes
$\sigma_{t}$ drawn from the PL model in (2). Since $\pi_{*}$ is fixed, we have
a fixed-design algorithm under ranking feedback as well. Finally, we compute
the MLE $\widehat{\bm{\theta}}_{n}$ of the unknown model parameter
$\bm{\theta}_{*}$ as

$\displaystyle\widehat{\bm{\theta}}_{n}$
$\displaystyle\in\underset{\bm{\theta}}{\mathop{\rm arg\,min}}\
\ell_{n}(\bm{\theta}),\text{ where }$ (12)
$\displaystyle\ell_{n}(\bm{\theta})$
$\displaystyle=-\frac{1}{n}\sum_{t=1}^{n}\sum_{k=1}^{K}\log\left(\frac{\exp\left(\mathbf{x}_{I_{t},\sigma_{t}(k)}^{\top}\bm{\theta}\right)}{\sum_{j=k}^{K-1}\exp\left(\mathbf{x}_{I_{t},\sigma_{t}(j)}^{\top}\bm{\theta}\right)}\right).$

Finally, the learner orders the items in every list $i\in[L]$ according to
their estimated mean rewards
$\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}$ in descending order to
obtain the permutation $\widehat{\sigma}_{n,i}$.

Note that under ranking feedback, we are interested in pair-wise differences
$\mathbf{z}_{i,j,k}$ between feature vectors because unlike under absolute
feedback, the human labeler only ranks the items.

color=red!20,size=,inline,]B: This sentence does not belong here. What do we
talk about? We present the full pseudo-code in Algorithm 2 in Appendix F.

###  5.2 Maximum Prediction Error Under Ranking Feedback

In this section, we analyze the prediction error of our fixed design algorithm
that logs ranking feedback according to $\pi_{*}$. Before we proceed, we make
the following assumption, which we borrow from Zhu et al. (2023b).

######  Assumption 5.1 (Identifiability of $\bm{\theta}_{*}$).

We assume that the true parameter satisfies
$\bm{\theta}_{*}\in\mathbf{\Theta}$, where

$\displaystyle\mathbf{\Theta}=\\{\bm{\theta}\in\mathbb{R}^{d}:\bm{\theta}^{\top}\mathbf{1}_{d}=0,\|\bm{\theta}\|_{2}\leq
1\\}.$ (13)

We also assume that $\max_{i\in[L],k\in[K]}\|\mathbf{x}_{i,k}\|\leq 1$.

This assumption is common in the linear bandit literature (Abbasi-Yadkori et
al., 2011; Lattimore and Szepesvári, 2020) and has been recently used in the
context of $K$-wise ranking feedback in Zhu et al. (2023b).

######  Assumption 5.2 (Lower bound of gradient).

We assume that $\kappa=\inf_{\left\\{\mathbf{x}:\|\mathbf{x}\|\leq
1,\bm{\theta}:\left\|\bm{\theta}-\bm{\theta}_{*}\right\|\leq
1\right\\}}\nabla{\exp}\left(\mathbf{x}^{\top}\bm{\theta}\right)>0$.

This is needed to bound the uncertainty of
$|\mathbf{x}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})|$ and has been
used frequently in the analyses of generalized linear bandit algorithms (Li et
al., 2017).

As before, and similarly to Theorem 4.2, we first bound the maximum prediction
error by decomposing it into two parts, where one part captures the efficiency
of the optimal design and the other part captures the uncertainty in the MLE
$\widehat{\bm{\theta}}_{n}$. To measure the uncertainty of the MLE in our
analysis, we define the covariance matrix

$\displaystyle\mathbf{\Sigma}_{n}=\frac{2}{K(K-1)n}\sum_{t=1}^{n}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbf{z}_{I_{t},j,k}\mathbf{z}_{I_{t},j,k}^{\top}.$
(14)

The unnormalized covariance matrix is

$\displaystyle\overline{\mathbf{\Sigma}}_{n}\\!=\\!\dfrac{K(K-1)n}{2}\mathbf{\Sigma}_{n}\\!=\\!\sum_{t=1}^{n}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbf{z}_{I_{t},j,k}\mathbf{z}_{I_{t},j,k}^{\top}.$
(15)

We bound on the maximum prediction error next.

######  Theorem 5.3.

(Maximum Prediction Error) Fix $\delta\in[0,1)$. Then with probability
$1-\delta$, the maximum prediction error after $n$ rounds is bounded

$\displaystyle\max_{i\in[L]}$
$\displaystyle\mathbf{Tr}\left(\mathbf{A}_{i}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)^{\top}\mathbf{A}_{i}\right)$
$\displaystyle\leq\widetilde{O}\left(\dfrac{K^{6}d^{2}\log(1/\delta)}{n}\right).$

###### Proof.

Since $\overline{\mathbf{\Sigma}}_{n}$ is invertible, following similar steps
to Theorem 4.2 yields

$\displaystyle\max_{i\in[L]}\mathbf{Tr}\left(\mathbf{A}_{i}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)^{\top}\mathbf{A}_{i}\right)$
$\displaystyle\leq\underbrace{\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}_{n}^{-1}}}_{\textbf{Part
I}}\underbrace{\tfrac{K(K-1)n}{2}\|\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\|^{2}_{\mathbf{\Sigma}_{n}}}_{\textbf{Part
II}}.$ (16)

Part I captures the efficiency of the optimal design and Part II captures the
uncertainty in the MLE $\widehat{\bm{\theta}}_{n}$.

Now we bound the individual quantities in Parts I and II. First, we use Lemma
4.1 to bound Part I. Then we bound Part II using Lemma D.1 in Section D.1. We
use the proof technique of Theorem 4.1 in Zhu et al. (2023b) to prove Lemma
D.1. Finally, the proof follows by combining Lemma 4.1 and Lemma D.1. At the
end, we get

$\displaystyle\max_{i\in[L]}$
$\displaystyle\sum_{\mathbf{a}\in\mathbf{A}_{i}}\left(\mathbf{a}^{\top}\left(\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\right)\right)^{2}$
$\displaystyle\overset{}{\leq}\tfrac{K(K-1)n}{2}\underbrace{\max_{i\in[L]}\sum_{\mathbf{a}\in\mathbf{A}_{i}}\|\mathbf{a}\|^{2}_{\overline{\mathbf{\Sigma}}_{n}^{-1}}}_{\textbf{Part
I}}\underbrace{\|\bm{\theta}_{*}-\widehat{\bm{\theta}}_{n}\|^{2}_{\mathbf{\Sigma}_{n}}}_{\textbf{Part
II}}$
$\displaystyle\leq\left(\frac{K(K-1)n}{2}\right)\frac{d}{n}C\left(\frac{K^{4}(d+\log(1/\delta))}{n}\right)$
$\displaystyle=\widetilde{O}\left(\dfrac{K^{6}d^{2}\log(1/\delta)}{n}\right),$

for some constant $C>0$. This concludes the proof. ∎

Again, we remind the reader that the sampling allocation to each list may not
be an integer. This requires a separate rounding procedure (Pukelsheim, 2006),
which introduces an additional factor of $(1+\beta)$ for some $\beta>0$ in our
bound. For simplicity, we omit this factor.

###  5.3 ranking loss Under Ranking Feedback

In this section, we bound the expected ranking loss under ranking feedback.
Similarly to Section 4.3, we define the _gap_ between the mean rewards of
items $j$ and $k$ in list $i$ as
$\Delta_{i,j,k}=(\mathbf{x}_{i,j}-\mathbf{x}_{i,k})^{\top}\bm{\theta}_{*}$.

######  Theorem 5.4.

(Expected ranking loss) The expected ranking loss, i.e., the ranking loss
under ranking feedback, can be bounded as

$\displaystyle\mathbb{E}\left[\mathrm{R}_{n}\right]$
$\displaystyle\leq\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}2\exp\left(-\dfrac{n\kappa^{2}\Delta^{2}_{i,j,k}}{2d}\right).$

###### Proof.

The proof is similar to Theorem 4.3. At the end of round $n$, we bound the
probability that a sub-optimal item $k$ is ranked above item $j$. This bound
has two parts. First, for any $(j,k)\in\Pi_{2}(K)$, we show that

$\displaystyle\mathbb{P}\left(\mathbf{x}_{i,j}^{\top}\widehat{\bm{\theta}}_{n}<\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}\right)=\mathbb{P}\left(\mathbf{z}_{i,j,k}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})<-\Delta_{i,j,k}\right),$

where we introduce feature vector differences $\mathbf{z}_{i,j,k}$. Then we
bound the above quantity by
$2\exp\left(-\frac{n\kappa^{2}\Delta^{2}_{i,j,k}}{2d}\right)$, using Lemma D.2
in Section D.2 and Lemma 4.1. The full proof is in Section D.2. ∎

Theorem 5.4 says that $\mathbb{E}\left[R_{n}\right]$ decays exponentially with
budget $n$. The main difference from Theorem 4.3 is the additional factor
$\kappa^{2}$ in the exponent. This is due to using a different concentration
bound (Lemma D.2 in Section D.2) to bound
$\mathbb{P}\left(\mathbf{z}_{i,j,k}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})<-\Delta_{i,j,k}\right)$,
which applies to generalized least squares. In comparison, Lemma C.2 in
Section C.2 only applies to ordinary least squares with independent sub-
Gaussian noise.

##  6 Experiments

Our experiments show that optimal designs minimize the ranking loss in (3).
All compared algorithms estimate $\widehat{\bm{\theta}}_{t}$ using (8) and
(12), depending on the feedback. Then they rank items in the lists based on
their estimated mean scores $\mathbf{x}_{i,k}\widehat{\bm{\theta}}_{t}$. The
algorithms differ in how they collect feedback. We consider two pure
exploration algorithms:

(1) Dope (D-optimal design: This is our proposed approach. We solve the
optimal design problem in (7), and then the sample lists $I_{t}$ according to
$\pi_{*}$.

(2) Unif (uniform sampling): This approach chooses lists $I_{t}$ uniformly at
random from $[L]$. It is known to be competitive in real-world problems where
feature vectors cover the feature space close to uniformly (Ash et al., 2019;
Yuan et al., 2020; Ash et al., 2021; Ren et al., 2021).

We introduce a few more baselines. There are many bandit algorithms for online
learning to rank (Radlinski et al., 2008; Kveton et al., 2015a). While
cumulative regret minimization algorithms are known to be suboptimal for pure
exploration (Bubeck et al., 2009; Audibert et al., 2010), they are easy to
implement. Therefore, we also experiment with:

(3) LinUCB (linear upper confidence bound): This algorithm chooses list
$I_{t}$ at round $t$ that maximizes the _upper confidence bound (UCB)_. The
UCB of list $i$ at round $t$ is the sum of the UCBs of all items in it,
$U_{t,i}=\sum_{k=1}^{K}U_{t,i,k}$. The UCB of item $k$ in list $i$ at round
$t$ is

$\displaystyle
U_{t,i,k}=\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{t-1}+\alpha\|\mathbf{x}_{i,k}\|_{\overline{\mathbf{\Sigma}}_{t-1}^{-1}}\,,$

where $\widehat{\bm{\theta}}_{t-1}$ and $\overline{\mathbf{\Sigma}}_{t-1}$ and
the MLE and corresponding covariance matrix, respectively, from feedback up to
round $t$; and $\alpha=2$ is a constant. This algorithm design is motivated by
existing algorithms for online learning to rank with a linear reward function
(Zong et al., 2016).

(4) $\epsilon$-greedy: This algorithm explores with probability $\epsilon$ and
exploits with probability $1-\epsilon$. When exploring, the list $I_{t}$ at
round $t$ is chosen uniformly at random from $[L]$. When exploiting, the list
with the highest estimated mean reward,
$\sum_{k=1}^{K}\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{t-1}$, is chosen.

Error metric: We report the ranking loss in (3). We average it over $10$
independent runs.

|
---|---
|

(a) Absolute Feedback

(b) Ranking Feedback

(c) Nectar Dataset

(d) Anthropic Dataset

Figure 1: Cumulative Ranking error of all compared algorithms as a function of
the number of rounds. The confidence bars represent one standard error of the
estimate.

Synthetic experiment 1 (absolute feedback): We choose $L=500$ questions and
represent them by random vectors $\mathbf{q}_{i}\in[10,20]^{5}$. Each question
has $K=4$ answers. For each question, we generate $4$ random answers
$\mathbf{a}_{k}\in\mathbb{R}^{5}$: $2$ answers are random vectors in
$[100,200]^{5}$ and $2$ answers are random vectors in $[700,1000]^{5}$. We
divide the answers into two groups to guarantee that their representations are
sufficiently different. Finally, for each question-answer pair $(i,k)$, the
feature vector is
$\mathbf{x}_{i,k}=\mathrm{vec}(\mathbf{q}_{i}\mathbf{a}_{k}^{\top})$. Its
length is $d=25$. We choose a random $\bm{\theta}_{*}\in\mathbb{R}^{d}$. The
absolute feedback is generated as in (1) for each $k\in[K]$. Our results are
reported in Figure 1(a). We observe that the ranking loss of Dope decreases
the fastest among all methods.

Synthetic experiment 2 (ranking feedback): This experiment is almost the same
as the first experiment, except the feedback is generated by the PL model in
(2). Our results are reported in Figure 1(b) and we observe again that the
ranking loss of Dope decreases the fastest.

Real-world experiment 3 (Nectar dataset): We choose $L=100$ questions from the
Nectar dataset (Zhu et al., 2023a). Each question has $K=5$ answers generated
by gpt-4, gpt-4-0613, gpt-3.5-turbo, gpt-3.5-turbo-instruct, and anthropic. We
first obtain $768$-dimensional Instructor embeddings (Su et al., 2022) of both
questions and answers. Then we randomly project them to $\mathbb{R}^{10}$. All
questions are projected using a single projection matrix
$\mathbf{P}_{q}\in\mathbb{R}^{768\times 10}$. Each of the $K$ answers is
projected using its own projection matrix
$\mathbf{P}_{k}\in\mathbb{R}^{768\times 10}$, for $k\in[K]$. This guarantees
the diversity of answer representations. Let $\mathbf{q}_{i}$ and
$\mathbf{a}_{k}$ be the projected embeddings of question $i$ and answer $k$ to
it. Then for each question-answer pair $(i,k)$, the feature vector is
$\mathbf{x}_{i,k}=\mathrm{vec}(\mathbf{q}_{i}\mathbf{a}_{k}^{\top})$. Its
length is $d=100$. We estimate $\bm{\theta}_{*}\in\mathbb{R}^{d}$ from the
original ranking feedback in the dataset using the MLE in (12). During
simulation, the ranking feedback is generated by the PL model in (2). Our
results are reported in Figure 1(c). We observe that the ranking loss of Dope
is consistently the lowest. Observe that the ranking loss of Dope is lower
than uniform.

Real-world experiment 4 (Anthropic dataset): We take $L=200$ questions, each
with $K=2$ answers, from the Anthropic dataset (Bai et al., 2022). In this
dataset, each question $\mathbf{q}_{i}$ is concatenated with its answer
$\mathbf{a}_{k}$. We first obtain a $768$-dimensional Instructor embedding of
this concatenated representation. After that, we use two projection matrices
$\mathbf{P}_{1},\mathbf{P}_{2}\in\mathbb{R}^{768\times 30}$, one per answer
$k\in[K]$, to project the representations to $d=30$ dimensions. We estimate
$\bm{\theta}_{*}\in\mathbb{R}^{d}$ from the original ranking feedback in the
dataset using the MLE in (12). During simulation, the ranking feedback is
generated by the PL model in (2). Our results are reported in Figure 1(d), and
we observe again that the ranking loss of Dope is the lowest. Note that till
the sample size of $1000$ we observe that Dope achieves a ranking loss lower
than uniform.

##  7 Conclusions

In this paper, we studied the optimal design for $K$-way human feedback where
the underlying human feedback model is the Plackett-Luce model (Plackett,
1975). We study both minimizing prediction error and fixed-budget pure
exploration when the $K$-way human feedback is either an absolute score of the
items or a relative ranking of the items. We first provided a unified
framework for optimal design for absolute and ranking feedback by generalizing
the Kiefer-Wolfowitz theorem (Kiefer and Wolfowitz, 1960; Lattimore and
Szepesvári, 2020) from generating a distribution over individual items to a
distribution over lists of items using matrix algebra. Then using the optimal
design solution from the matrix Kiefer-Wolfowitz theorem we propose the Dope
algorithm for both absolute and ranking feedback that minimizes prediction
error at the end of round $n$. We also bound the prediction error of Dope
under these two feedback methods. Similarly, the optimal design solution of
Dope is used to minimize the ranking loss for the fixed budget pure
exploration setting. Moreover, we also bound the ranking loss bound for Dope
under both absolute and ranking feedback. Finally, we experiment on several
synthetic and real-world datasets to show the efficacy of our algorithm Dope
for the RLHF setting. In the future we want to extend the Dope algorithm for
the MDP setting and for the setting with changing contexts and actions. We
also want to extend the optimal design of Dope to fixed confidence setting for
both absolute and ranking feedback.

## References

  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Abbeel and Ng [2004] Pieter Abbeel and Andrew Y Ng.  Apprenticeship learning via inverse reinforcement learning.  In _Proceedings of the twenty-first international conference on Machine learning_ , page 1, 2004.
  * Ash et al. [2021] Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade.  Gone fishing: Neural active learning with fisher embeddings.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Ash et al. [2019] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal.  Deep batch active learning by diverse, uncertain gradient lower bounds.  _arXiv preprint arXiv:1906.03671_ , 2019.
  * Audibert et al. [2009] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári.  Exploration–exploitation tradeoff using variance estimates in multi-armed bandits.  _Theoretical Computer Science_ , 410(19):1876–1902, 2009.
  * Audibert et al. [2010] Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos.  Best arm identification in multi-armed bandits.  In _COLT_ , pages 41–53, 2010.
  * Azizi et al. [2022] Mohammad Javad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh.  Fixed-budget best-arm identification in structured bandits.  In _Proceedings of the 31st International Joint Conference on Artificial Intelligence_ , 2022.
  * Bai et al. [2022] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_ , 2022.
  * Bengs et al. [2021] Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier.  Preference-based online learning with dueling bandits: A survey.  _The Journal of Machine Learning Research_ , 22(1):278–385, 2021.
  * Bradley and Terry [1952] Ralph Allan Bradley and Milton E Terry.  Rank analysis of incomplete block designs: I. the method of paired comparisons.  _Biometrika_ , 39(3/4):324–345, 1952.
  * Brown et al. [2019] Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum.  Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations.  In _International conference on machine learning_ , pages 783–792. PMLR, 2019.
  * Bubeck et al. [2009] Sebastien Bubeck, Remi Munos, and Gilles Stoltz.  Pure exploration in multi-armed bandits problems.  In _Proceedings of the 20th International Conference on Algorithmic Learning Theory_ , pages 23–37, 2009.
  * Burges [2010] Christopher Burges.  From RankNet to LambdaRank to LambdaMART: An overview.  Technical Report MSR-TR-2010-82, Microsoft Research, 2010.
  * Busa-Fekete et al. [2014] Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, Weiwei Cheng, and Eyke Hüllermeier.  Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm.  _Machine learning_ , 97:327–351, 2014.
  * Casper et al. [2023] Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al.  Open problems and fundamental limitations of reinforcement learning from human feedback.  _arXiv preprint arXiv:2307.15217_ , 2023.
  * Chen et al. [2022] Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang.  Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation.  In _International Conference on Machine Learning_ , pages 3773–3793. PMLR, 2022.
  * Christiano et al. [2017] 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.
  * Chuklin et al. [2022] Aleksandr Chuklin, Ilya Markov, and Maarten De Rijke.  _Click models for web search_.  Springer Nature, 2022.
  * Dadkhahi and Negahban [2018] Hamid Dadkhahi and Sahand Negahban.  Alternating linear bandits for online matrix-factorization recommendation.  _arXiv preprint arXiv:1810.09401_ , 2018.
  * Dudik et al. [2014] Miroslav Dudik, Dumitru Erhan, John Langford, and Lihong Li.  Doubly robust policy evaluation and optimization.  _Statistical Science_ , 29(4):485–511, 2014.
  * Ermis et al. [2020] Beyza Ermis, Patrick Ernst, Yannik Stein, and Giovanni Zappella.  Learning to rank in the position based model with bandit feedback.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pages 2405–2412, 2020.
  * Fedorov [2013] Valerii Vadimovich Fedorov.  _Theory of optimal experiments_.  Elsevier, 2013.
  * Fiez et al. [2019] Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff.  Sequential experimental design for transductive linear bandits.  _Advances in neural information processing systems_ , 32, 2019.
  * Florence et al. [2022] Pete Florence, Corey Lynch, Andy Zeng, Oscar A Ramirez, Ayzaan Wahid, Laura Downs, Adrian Wong, Johnny Lee, Igor Mordatch, and Jonathan Tompson.  Implicit behavioral cloning.  In _Conference on Robot Learning_ , pages 158–168. PMLR, 2022.
  * Fontaine et al. [2021] Xavier Fontaine, Pierre Perrault, Michal Valko, and Vianney Perchet.  Online a-optimal design and active linear regression.  In _International Conference on Machine Learning_ , pages 3374–3383. PMLR, 2021.
  * Fürnkranz and Hüllermeier [2003] Johannes Fürnkranz and Eyke Hüllermeier.  Pairwise preference learning and ranking.  In _European conference on machine learning_ , pages 145–156. Springer, 2003.
  * Gampa and Fujita [2021] Phanideep Gampa and Sumio Fujita.  Banditrank: Learning to rank using contextual bandits.  In _Pacific-Asia conference on knowledge discovery and data mining_ , pages 259–271. Springer, 2021.
  * Glass [2006] Alyssa Glass.  Explaining preference learning, 2006.
  * Hejna and Sadigh [2023] Joey Hejna and Dorsa Sadigh.  Inverse preference learning: Preference-based rl without a reward function.  _arXiv preprint arXiv:2305.15363_ , 2023.
  * Ho and Ermon [2016] Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  _Advances in neural information processing systems_ , 29, 2016.
  * Houlsby et al. [2011] Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel.  Bayesian active learning for classification and preference learning.  _arXiv preprint arXiv:1112.5745_ , 2011.
  * Hussein et al. [2017] Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne.  Imitation learning: A survey of learning methods.  _ACM Computing Surveys (CSUR)_ , 50(2):1–35, 2017.
  * Jamieson and Jain [2022] Kevin Jamieson and Lalit Jain.  Interactive machine learning.  2022\.
  * Jamieson and Nowak [2014] Kevin Jamieson and Robert Nowak.  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In _2014 48th Annual Conference on Information Sciences and Systems (CISS)_ , pages 1–6. IEEE, 2014.
  * Ji et al. [2023] Xiang Ji, Huazheng Wang, Minshuo Chen, Tuo Zhao, and Mengdi Wang.  Provable benefits of policy learning from human preferences in contextual bandit problems.  _arXiv preprint arXiv:2307.12975_ , 2023.
  * Jin et al. [2021] Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is pessimism provably efficient for offline rl?  In _International Conference on Machine Learning_ , pages 5084–5096. PMLR, 2021.
  * Katz-Samuels et al. [2020] Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al.  An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits.  _Advances in Neural Information Processing Systems_ , 33:10371–10382, 2020.
  * Katz-Samuels et al. [2021] Julian Katz-Samuels, Jifan Zhang, Lalit Jain, and Kevin Jamieson.  Improved algorithms for agnostic pool-based active classification.  In _International Conference on Machine Learning_ , pages 5334–5344. PMLR, 2021.
  * Kiefer and Wolfowitz [1960] Jack Kiefer and Jacob Wolfowitz.  The equivalence of two extremum problems.  _Canadian Journal of Mathematics_ , 12:363–366, 1960.
  * Kveton et al. [2015a] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan.  Cascading bandits: Learning to rank in the cascade model.  In _Proceedings of the 32nd International Conference on Machine Learning_ , 2015a.
  * Kveton et al. [2015b] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan.  Cascading bandits: Learning to rank in the cascade model.  In _International conference on machine learning_ , pages 767–776. PMLR, 2015b.
  * Lagrée et al. [2016] Paul Lagrée, Claire Vernade, and Olivier Cappe.  Multiple-play bandits in the position-based model.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Lalitha et al. [2023] Anusha Lalitha Lalitha, Kousha Kalantari, Yifei Ma, Anoop Deoras, and Branislav Kveton.  Fixed-budget best-arm identification with heterogeneous reward variances.  In _Uncertainty in Artificial Intelligence_ , pages 1164–1173. PMLR, 2023.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Lattimore et al. [2018] Tor Lattimore, Branislav Kveton, Shuai Li, and Csaba Szepesvari.  TopRank: A practical algorithm for online stochastic ranking.  In _Advances in Neural Information Processing Systems 31_ , pages 3949–3958, 2018.
  * Lee et al. [2021] Kimin Lee, Laura Smith, Anca Dragan, and Pieter Abbeel.  B-pref: Benchmarking preference-based reinforcement learning.  _arXiv preprint arXiv:2111.03026_ , 2021.
  * Lekang and Lamperski [2019] Tyler Lekang and Andrew Lamperski.  Simple algorithms for dueling bandits.  _arXiv preprint arXiv:1906.07611_ , 2019.
  * Li et al. [2022] Gene Li, Cong Ma, and Nati Srebro.  Pessimism for offline linear contextual bandits using $\\\ backslash\\\ ell\\\ _{p}$ confidence sets.  _Advances in Neural Information Processing Systems_ , 35:20974–20987, 2022.
  * Li et al. [2017] Lihong Li, Yu Lu, and Dengyong Zhou.  Provably optimal algorithms for generalized linear contextual bandits.  In _International Conference on Machine Learning_ , pages 2071–2080. PMLR, 2017.
  * Liu et al. [2009] Tie-Yan Liu et al.  Learning to rank for information retrieval.  _Foundations and Trends® in Information Retrieval_ , 3(3):225–331, 2009.
  * Luce [2012] R Duncan Luce.  _Individual choice behavior: A theoretical analysis_.  Courier Corporation, 2012.
  * Mukherjee et al. [2022] Subhojyoti Mukherjee, Ardhendu S Tripathy, and Robert Nowak.  Chernoff sampling for active testing and extension to active regression.  In _International Conference on Artificial Intelligence and Statistics_ , pages 7384–7432. PMLR, 2022.
  * Mukherjee et al. [2023] Subhojyoti Mukherjee, Qiaomin Xie, Josiah Hanna, and Robert Nowak.  Speed: Experimental design for policy evaluation in linear heteroscedastic bandits.  _arXiv preprint arXiv:2301.12357_ , 2023.
  * Neu and Szepesvári [2009] Gergely Neu and Csaba Szepesvári.  Training parsers by inverse reinforcement learning.  _Machine learning_ , 77:303–337, 2009.
  * Ng et al. [2000] Andrew Y Ng, Stuart Russell, et al.  Algorithms for inverse reinforcement learning.  In _Icml_ , volume 1, page 2, 2000.
  * Novoseller et al. [2020] 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.
  * Opoku-Agyemang [2023] Kweku A Opoku-Agyemang.  Randomized controlled trials via reinforcement learning from human feedback.  2023\.
  * Ouyang et al. [2022] 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.
  * Plackett [1975] Robin L Plackett.  The analysis of permutations.  _Journal of the Royal Statistical Society Series C: Applied Statistics_ , 24(2):193–202, 1975.
  * Pukelsheim [2006] Friedrich Pukelsheim.  _Optimal design of experiments_.  SIAM, 2006.
  * Radlinski et al. [2008] 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.
  * Ramachandran and Amir [2007] Deepak Ramachandran and Eyal Amir.  Bayesian inverse reinforcement learning.  In _IJCAI_ , volume 7, pages 2586–2591, 2007.
  * Rashidinejad et al. [2021] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell.  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  _Advances in Neural Information Processing Systems_ , 34:11702–11716, 2021.
  * Ren et al. [2021] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang.  A survey of deep active learning.  _ACM Computing Surveys (CSUR)_ , 54(9):1–40, 2021.
  * Riquelme et al. [2017] Carlos Riquelme, Mohammad Ghavamzadeh, and Alessandro Lazaric.  Active learning for accurate estimation of linear models.  In _International Conference on Machine Learning_ , pages 2931–2939. PMLR, 2017.
  * Saha and Gaillard [2022] Aadirupa Saha and Pierre Gaillard.  Versatile dueling bandits: Best-of-both-world analyses for online learning from preferences.  _arXiv preprint arXiv:2202.06694_ , 2022.
  * Saha et al. [2023] Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee.  Dueling rl: Reinforcement learning with trajectory preferences.  In _International Conference on Artificial Intelligence and Statistics_ , pages 6263–6289. PMLR, 2023.
  * Shen et al. [2023] Tianhao Shen, Renren Jin, Yufei Huang, Chuang Liu, Weilong Dong, Zishan Guo, Xinwei Wu, Yan Liu, and Deyi Xiong.  Large language model alignment: A survey.  _arXiv preprint arXiv:2309.15025_ , 2023.
  * Shin et al. [2023] Daniel Shin, Anca D Dragan, and Daniel S Brown.  Benchmarks and algorithms for offline preference-based reward learning.  _arXiv preprint arXiv:2301.01392_ , 2023.
  * Su et al. [2022] Hongjin Su, Weijia Shi, Jungo Kasai, Yizhong Wang, Yushi Hu, Mari Ostendorf, Wen-tau Yih, Noah A. Smith, Luke Zettlemoyer, and Tao Yu.  One embedder, any task: Instruction-finetuned text embeddings.  2022\.  URL https://arxiv.org/abs/2212.09741.
  * Sui et al. [2018] Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yue.  Advancements in dueling bandits.  In _IJCAI_ , pages 5502–5510, 2018.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Swaminathan and Joachims [2015] Adith Swaminathan and Thorsten Joachims.  Counterfactual risk minimization: Learning from logged bandit feedback.  In _Proceedings of the 32nd International Conference on Machine Learning_ , pages 814–823, 2015.
  * Szörényi et al. [2015] Balázs Szörényi, Róbert Busa-Fekete, Adil Paul, and Eyke Hüllermeier.  Online rank elicitation for plackett-luce: A dueling bandits approach.  _Advances in neural information processing systems_ , 28, 2015.
  * Wang et al. [2023] Yuanhao Wang, Qinghua Liu, and Chi Jin.  Is rlhf more difficult than standard rl? a theoretical perspective.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Wirth et al. [2017] Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, et al.  A survey of preference-based reinforcement learning methods.  _Journal of Machine Learning Research_ , 18(136):1–46, 2017.
  * Wu and Sun [2023] Runzhe Wu and Wen Sun.  Making rl with preference-based feedback efficient via randomization.  _arXiv preprint arXiv:2310.14554_ , 2023.
  * Xia et al. [2008] Fen Xia, Tie-Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li.  Listwise approach to learning to rank: theory and algorithm.  In _Proceedings of the 25th international conference on Machine learning_ , pages 1192–1199, 2008.
  * Xie et al. [2021a] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  _Advances in neural information processing systems_ , 34:6683–6694, 2021a.
  * Xie et al. [2021b] Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai.  Policy finetuning: Bridging sample-efficient offline and online reinforcement learning.  _Advances in neural information processing systems_ , 34:27395–27407, 2021b.
  * Xiong et al. [2023] Wei Xiong, Hanze Dong, Chenlu Ye, Han Zhong, Nan Jiang, and Tong Zhang.  Gibbs sampling from human feedback: A provable kl-constrained framework for rlhf.  _arXiv preprint arXiv:2312.11456_ , 2023.
  * Xu et al. [2022] Tengyu Xu, Yue Wang, Shaofeng Zou, and Yingbin Liang.  Provably efficient offline reinforcement learning with trajectory-wise reward.  _arXiv preprint arXiv:2206.06426_ , 2022.
  * Xu et al. [2020] 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.
  * Yang and Tan [2021] Junwen Yang and Vincent YF Tan.  Minimax optimal fixed-budget best arm identification in linear bandits.  _arXiv preprint arXiv:2105.13017_ , 2021.
  * Yang et al. [2023] Kevin Yang, Dan Klein, Asli Celikyilmaz, Nanyun Peng, and Yuandong Tian.  Rlcd: Reinforcement learning from contrast distillation for language model alignment.  _arXiv preprint arXiv:2307.12950_ , 2023.
  * Yuan et al. [2020] Michelle Yuan, Hsuan-Tien Lin, and Jordan Boyd-Graber.  Cold-start active learning through self-supervised language modeling.  _arXiv preprint arXiv:2010.09535_ , 2020.
  * Yue et al. [2012] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims.  The k-armed dueling bandits problem.  _Journal of Computer and System Sciences_ , 78(5):1538–1556, 2012.
  * Zanette [2023] Andrea Zanette.  When is realizability sufficient for off-policy reinforcement learning?  In _International Conference on Machine Learning_ , pages 40637–40668. PMLR, 2023.
  * Zanette et al. [2021] Andrea Zanette, Martin J Wainwright, and Emma Brunskill.  Provable benefits of actor-critic methods for offline reinforcement learning.  _Advances in neural information processing systems_ , 34:13626–13640, 2021.
  * Zhong et al. [2021] Zixin Zhong, Wang Chi Chueng, and Vincent YF Tan.  Thompson sampling algorithms for cascading bandits.  _The Journal of Machine Learning Research_ , 22(1):9915–9980, 2021.
  * Zhou et al. [2023] Tianchen Zhou, Jia Liu, Yang Jiao, Chaosheng Dong, Yetian Chen, Yan Gao, and Yi Sun.  Bandit learning to rank with position-based click models: Personalized and equal treatments.  _arXiv preprint arXiv:2311.04528_ , 2023.
  * Zhu et al. [2023a] Banghua Zhu, Evan Frick, Tianhao Wu, Hanlin Zhu, and Jiantao Jiao.  Starling-7b: Improving llm helpfulness & harmlessness with rlaif, November 2023a.
  * Zhu et al. [2023b] Banghua Zhu, Jiantao Jiao, and Michael I Jordan.  Principled reinforcement learning with human feedback from pairwise or $k$-wise comparisons.  _arXiv preprint arXiv:2301.11270_ , 2023b.
  * Ziebart et al. [2008] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al.  Maximum entropy inverse reinforcement learning.  In _Aaai_ , volume 8, pages 1433–1438. Chicago, IL, USA, 2008.
  * Zoghi et al. [2017] Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari, and Zheng Wen.  Online learning to rank in stochastic click models.  In _International conference on machine learning_ , pages 4199–4208. PMLR, 2017.
  * Zong et al. [2016] Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton.  Cascading bandits for large-scale recommendation problems.  _arXiv preprint arXiv:1603.05359_ , 2016.

##  Appendix A Related Works

In this section, we discuss related works.

Our setting is similar to the preference learning framework. In preference
learning framework the goal is to learn the preferences of one or more agents
from the observations [Fürnkranz and Hüllermeier, 2003, Glass, 2006, Houlsby
et al., 2011]. The preference learning literature mainly consists of two types
of feedback: pairwise preferences and ranking feedback. In pairwise
preference, the observed data is a preference between pairs of objects while
in ranking feedback the learner observes the absolute ranking of the items.
Both of these have been studied in the online and bandit communities [Kveton
et al., 2015b, Zoghi et al., 2017, Ermis et al., 2020, Bengs et al., 2021].
The preference based bandits have several similarities with the dueling bandit
settings [Yue et al., 2012, Lekang and Lamperski, 2019, Saha and Gaillard,
2022, Saha et al., 2023]. In dueling bandits at every round $t$ the learner
selects a pair of items and observes an instantaneous comparison over them
where the outcome does not depend on the items previously selected. So in
dueling bandits the goal of the learner is to select the item winning with the
highest probability. In contrast in our setting, the learner observes the
absolute feedback for $K$ items or a ranking over these $K$ items.

In the ranking setting the learner observed a ranking over the items and the
goal of the learner is to find the $K$ items with the highest reward [Zhu et
al., 2023b]. These rankings can be generated from an underlying human
preference model like Placket-Luce (PL) [Plackett, 1975, Luce, 2012] or BTL
model [Bradley and Terry, 1952]. However, in this work, we focus on the fixed
budget pure exploration setting whereas all the previous works focus on simple
regret setting under the ranking feedback [Kveton et al., 2015b, Zoghi et al.,
2017]. Previous works in online learning to rank have focused on several types
of click feedback models, like position based model [Lagrée et al., 2016,
Ermis et al., 2020, Zhou et al., 2023] or cascading model [Kveton et al.,
2015a, Zong et al., 2016, Zhong et al., 2021]. In contrast in our setting, we
do not assume any such underlying click model, but assume that there is an
underlying human ranking model (PL or BTL).

Similar preference based learning has been studied in Reinforcement Learning
(RL) as well [Wirth et al., 2017, Novoseller et al., 2020, Xu et al., 2020,
Hejna and Sadigh, 2023]. This is termed Preference Based Reinforcement
Learning (PBRL). The key difference between RL and PBRL settings is that in
PBRL the learner has to learn the underlying human preference through the
rewards observed which can be non-numerical [Christiano et al., 2017, Lee et
al., 2021, Chen et al., 2022]. All of these works focus on regret minimization
or finding the optimal policy in RL setting. However, in our setting, we only
consider the stateless bandit framework, and we focus pure exploration
setting. The PBRL setting has also been studied under general function
approximation when the reward is parameterized by a neural network [Xia et
al., 2008, Liu et al., 2009, Busa-Fekete et al., 2014, Brown et al., 2019,
Ouyang et al., 2022, Shin et al., 2023].

Our work is also closely related to Inverse Reinforcement Learning (IRL) and
Offline Reinforcement Learning. These frameworks also allow the agent to take
into account human preferences into it decision-making process. In IRL and
imitation learning the agent only observes the expert’s interaction history
and aims to predict the expert’s preference [Ng et al., 2000, Abbeel and Ng,
2004, Ramachandran and Amir, 2007, Ziebart et al., 2008, Neu and Szepesvári,
2009, Ho and Ermon, 2016, Hussein et al., 2017, Florence et al., 2022]. In the
offline RL setting the agent directly observes the past history of
interactions. Note that these actions can be sub-optimal and there can be
issues of data coverage and distribution shifts. Therefore in recent years
pessimism under offline RL has gained traction [Jin et al., 2021, Rashidinejad
et al., 2021, Xie et al., 2021b, Zanette et al., 2021, Xie et al., 2021a, Li
et al., 2022, Xu et al., 2022, Zanette, 2023] In contrast to these works, we
study offline K-wise preference ranking under PL and BTL models for pure
exploration setting. We do not use any pessimism but use optimal design
[Pukelsheim, 2006, Fedorov, 2013] to ensure diversity among the data
collected.

##  Appendix B Proof of Matrix Kiefer-Wolfowitz

We follow the proof technique of Lattimore and Szepesvári [2020]. Observe that
$\mathbf{V}_{\pi}\in\mathbb{R}^{d\times d}$ is a square matrix. Using Jacobi
formula we have

$\displaystyle\nabla f(\pi)_{\pi(i)}$
$\displaystyle{=}\frac{\mathbf{Tr}\left(\operatorname{adj}(\mathbf{V}_{\pi})\mathbf{A}_{i}\mathbf{A}_{i}^{\top}\right)}{\operatorname{det}(\mathbf{V}_{\pi})}$
(17)
$\displaystyle=\frac{\mathbf{Tr}(\mathbf{A}_{i}^{\top}\operatorname{adj}(\mathbf{V}_{\pi})\mathbf{A}_{i})}{\operatorname{det}(\mathbf{V}_{\pi})}$
(18)
$\displaystyle\overset{(a)}{=}\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\mathbf{A}_{i}),$
(19)

where the last equality follows from the fact that for a square matrix
$\mathbf{V}_{\pi}$, its adjoint matrix $\operatorname{adj}(\mathbf{V}_{\pi})$
is the transpose of its cofactor matrix and hence, the inverse is
$\mathbf{V}^{-1}_{\pi}=\frac{1}{\operatorname{det}(\mathbf{V}_{\pi})}\operatorname{adj}(V_{\pi})^{\top}$.
Then, we have

$\displaystyle\sum_{i\in[L]}\pi(i)\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\mathbf{A}_{i})$
$\displaystyle=\mathbf{Tr}\left(\sum_{i\in[L]}\pi(i)\mathbf{A}_{i}\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\right)$
(20)
$\displaystyle=\mathbf{Tr}\left(\sum_{i\in[L]}\pi(i)\mathbf{A}_{i}\mathbf{A}_{i}^{\top}\left(\sum_{i\in[L]}\pi(i)\mathbf{A}_{i}\mathbf{A}_{i}^{\top}\right)^{-1}\right)$
(21) $\displaystyle=\mathbf{Tr}\left(\mathbf{I}_{d}\right)=d.$ (22)

The above equation implies $g(\pi)\geq d$ for all $\pi$.
$(b)\Rightarrow(a)$: Suppose that $\pi_{*}$ is a maximizer of $f(\pi)$. By the
first-order optimality criterion, for any $\pi$ distribution,

$\displaystyle 0$ $\displaystyle\geq\left\langle\nabla
f\left(\pi_{*}\right),\pi-\pi_{*}\right\rangle$
$\displaystyle\geq\left(\sum_{i\in[L]}\pi(i)\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi_{*}}^{-1}\mathbf{A}_{i})-\sum_{i\in[L]}\pi_{*}(i)\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi_{*}}^{-1}\mathbf{A}_{i})\right)$
$\displaystyle\geq\left(\sum_{i\in[L]}\pi(i)\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi_{*}}^{-1}\mathbf{A}_{i})-d\right).$

For an arbitrary $\pi$, choosing $\pi$ to be the Dirac at $i$ proves that
$\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi_{*}}^{-1}\mathbf{A}_{i})\leq
d$ for all $i\in[L]$. Since $g(\pi)\geq d$ for all $\pi$ by (22), it follows
that $\pi_{*}$ is a minimizer of $g$ and that $g(\pi_{*})=d$.

$(c)\Longrightarrow(b)$: Suppose that $g\left(\pi_{*}\right)=d$. Then, for any
$\pi$,

$\displaystyle\left\langle\nabla
f\left(\pi_{*}\right),\pi-\pi_{*}\right\rangle=\sum_{i\in[L]]}\pi(i)\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi_{*}}^{-1}\mathbf{A}_{i})-d\leq
0.$ (23)

And it follows that $\pi_{*}$ is a maximizer of $f(\pi)$ by the first-order
optimality conditions and the concavity of $f(\pi)$.

$(a)\Longrightarrow(c)$: Follows from the previous two steps as we proved that
$\pi_{*}$ is a minimizer of $g(\pi)$ and $\pi_{*}$ is also a maximizer of
$f(\pi)$.

To prove the second part of the theorem, let $\pi_{*}$ be a minimizer of $g$,
which by the previous part is a maximizer of $f$. Let
$\mathcal{M}=\operatorname{Supp}\left(\pi_{*}\right)$, and suppose that
$|\mathcal{M}|>d(d+1)/2$. Since the dimension of the subspace of $d\times d$
symmetric matrices is $d(d+1)/2$, there must be a non-zero function
$v:\mathcal{S}\rightarrow\mathbb{R}^{L}$ with
$\operatorname{Supp}(v)\subseteq\mathcal{M}$ such that

$\displaystyle\sum_{i\in\mathcal{M}}v(i)\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\mathbf{A}_{i})=0.$
(24)

where, $v(i)$ is the probability assigned to the $\mathbf{a}$ under the
function (distribution) $v$. Notice that for any $j\in\mathcal{M}$, the first-
order optimality conditions ensure that
$\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\mathbf{A}_{i})=d$.
Hence we can show that

$\displaystyle
d\sum_{i\in\mathcal{M}}v(i)=\sum_{i\in\mathcal{M}}v(i)\mathbf{Tr}(\mathbf{A}_{i}^{\top}\mathbf{V}_{\pi}^{-1}\mathbf{A}_{i})=0,$

where the last equality follows from (24). Let $\pi(t)=\pi_{*}+tv$ and let
$\tau=\max\left\\{t>0:\pi(t)\in\Delta^{|\mathcal{S}|}\right\\}$, which exists
since $v\neq 0$ and $\sum_{i\in\mathcal{M}}v(i)=\mathbf{0}$ and
$\operatorname{Supp}(v)\subseteq\mathcal{M}$. By (24),
$\mathbf{V}_{\pi(t)}=\mathbf{V}_{\pi_{*}}$, and hence
$f(\pi(\tau))=f\left(\pi_{*}\right)$, which means that $\pi(\tau)$ also
maximises $f$. The claim follows by checking that
$|\operatorname{Supp}(\pi(t))|<\left|\operatorname{Supp}\left(\pi_{*}\right)\right|$
and then using induction. The claim of the theorem follows.

##  Appendix C Learning with Absolute Feedback

###  C.1 Maximum Absolute Prediction Error

######  Lemma C.1.

Under the absolute feedback model, for any $\lambda>0$, with probability at
least $1-\delta$,

$\displaystyle\left\|\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\right\|^{2}_{\mathbf{\Sigma}_{n}}\leq
4\left(\frac{2d\log 6+\log(1/\delta)}{n}\right).$

Here
$\mathbf{\Sigma}_{n}=\frac{1}{n}\sum_{i=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{i,k}\mathbf{x}_{i,k}^{\top}$.

###### Proof.

First we define some additional notation. Recall that each $\mathbf{x}_{i,k}$
is column vector in $\mathbb{R}^{d}$. We define the feature vector associated
with $I_{t}$ as $\mathbf{X}_{t}\in\mathbb{R}^{K\times d}$ as
$[\mathbf{x}_{I_{t},1},\mathbf{x}_{I_{t},2},\ldots,\mathbf{x}_{I_{t},K}]^{\top}$
and define the feature matrix after $n$ observations
$\mathbf{X}\in\mathbb{R}^{Kn\times d}$ as
$[\mathbf{X}^{\top}_{1},\mathbf{X}^{\top}_{2},\ldots,\mathbf{X}^{\top}_{n}]^{\top}$.
Similarly, we define the observation vector $\mathbf{Y}_{t}\in\mathbb{R}^{K}$
at round $t$ as $[y_{t,1},y_{t,2},\ldots,y_{t,K}]^{\top}$ and define the
observation vector after $n$ observations $\mathbf{Y}\in\mathbb{R}^{Kn}$ as
$[\mathbf{Y}_{1}^{\top},\mathbf{Y}_{2}^{\top},\ldots,\mathbf{Y}_{t}^{\top}]^{\top}$.

Under the sub-Gaussian noise we can show that the MLE estimate is same as the
Ordinary Least Square (OLS) estimate such that
$\widehat{\bm{\theta}}_{n}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{Y}$.
Then we can show that

$\displaystyle\widehat{\bm{\theta}}_{n}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{Y}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}(\mathbf{X}\bm{\theta}_{*}+\eta_{n})=\bm{\theta}_{*}+(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\eta_{n}$
$\displaystyle\implies$
$\displaystyle\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\eta_{n}.$

Since, the noise is independent sub-Gaussian noise, it follows then for any
$\mathbf{a}\in\mathbb{R}^{d}$

$\displaystyle\mathbf{a}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})$
$\displaystyle\sim\mathcal{SG}(0,\mathbf{a}^{\top}(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\eta_{n}\eta_{n}^{\top}\mathbf{X}(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{a})$
$\displaystyle\sim\mathcal{SG}(0,\mathbf{a}^{\top}(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{a})$
$\displaystyle\sim\mathcal{SG}(0,\|\mathbf{a}\|^{2}_{(\mathbf{X}^{\top}\mathbf{X})^{-1}})$

Therefore we have that using sub-Gaussian concentration inequality that

$\displaystyle\mathbb{P}\left(\mathbf{a}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})\geq\sqrt{2(\|\mathbf{a}\|^{2}_{(\mathbf{X}^{\top}\mathbf{X})^{-1}})\log(1/\delta)}\right)\leq\delta.$
(25)

Also, note that $(\mathbf{X}^{\top}\mathbf{X})=n\mathbf{\Sigma}_{n}$. Follows
Chapter 20 of Lattimore and Szepesvári [2020] We now use a covering argument.
Let there exists a set $\mathcal{C}_{\epsilon}\subset\mathbb{R}^{d}$ with
$\left|\mathcal{C}_{\epsilon}\right|\leq(3/\varepsilon)^{d}$ such that for all
$\mathbf{x}\in S^{d-1}$ there exists a
$\mathbf{y}\in\mathcal{C}_{\varepsilon}$ with
$\|\mathbf{x}-\mathbf{y}\|_{2}\leq\epsilon$. Now define event

$\xi=\left\\{\operatorname{exists}x\in\mathcal{C}_{\varepsilon}:\langle\mathbf{\Sigma}_{n}^{1/2}\mathbf{x},\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\rangle\geq\sqrt{\frac{2}{n}\log\left(\frac{\left|\mathcal{C}_{\epsilon}\right|}{\delta}\right)}\right\\}$

We now want to show that $\mathbb{P}(\xi)\leq\delta$. We can show this as
follows:

$\displaystyle\|\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\|_{\mathbf{\Sigma}_{n}}$
$\displaystyle=\frac{1}{\sqrt{n}}\max_{\mathbf{x}\in
S^{d-1}}\langle\mathbf{\Sigma}_{n}^{1/2}\mathbf{x},\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\rangle$
$\displaystyle=\frac{1}{\sqrt{n}}\max_{\mathbf{x}\in
S^{d-1}}\min_{\mathbf{y}\in\mathcal{C}_{\epsilon}}\left[\langle\mathbf{\Sigma}_{n}^{1/2}\mathbf{x}-\mathbf{y},\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\rangle+\langle\mathbf{\Sigma}_{n}^{1/2}\mathbf{y},\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\rangle\right]$
$\displaystyle<\frac{1}{\sqrt{n}}\max_{\mathbf{x}\in
S^{d-1}}\min_{\mathbf{y}\in\mathcal{C}_{\epsilon}}\left[\|\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\|_{\mathbf{\Sigma}_{n}}\|\mathbf{x}-\mathbf{y}\|^{2}_{2}+\sqrt{2\log\frac{|\mathcal{C}_{\epsilon}|}{\delta}}\right]$
$\displaystyle\leq\frac{\epsilon}{\sqrt{n}}\|\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\|_{\mathbf{\Sigma}_{n}}+\frac{1}{\sqrt{n}}\sqrt{2\log\frac{|\mathcal{C}_{\epsilon}|}{\delta}}$

Rearranging the above yields

$\displaystyle\|\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\|_{\mathbf{\Sigma}_{n}}\leq\frac{1}{\sqrt{n}}\cdot\frac{1}{1-\epsilon}\sqrt{2\log\frac{|\mathcal{C}_{\epsilon}|}{\delta}}$

Setting $\epsilon=\tfrac{1}{2}$ we get that

$\displaystyle\mathbb{P}\left(\|\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\|_{\mathbf{\Sigma}_{n}}\geq
2\sqrt{\frac{2d}{n}\log(6)+\frac{1}{n}\log\frac{1}{\delta}}\right)\leq\delta.$

The claim of the lemma follows. ∎

###  C.2 Proof of Proposition 4.4

From the definition of simple regret we have

$\displaystyle\mathbb{E}\left[\mathrm{R}_{n}\right]=\sum_{i=1}^{L}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbb{E}\left[\mathbb{I}\\{\widehat{\sigma}_{n,i}(j)>\widehat{\sigma}_{n,i}(k)\\}\right]=\sum_{i=1}^{L}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbb{P}\left(\mathbf{x}_{i,j}^{\top}\widehat{\bm{\theta}}_{n}<\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}\right).$

Hence, our first step is to bound the prediction error where item $k$ is
predicted above item $j$ under absolute feedback
$\mathbb{P}\left(\mathbf{x}_{i,j}^{\top}\widehat{\bm{\theta}}_{n}<\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}\right)$
for all list $i\in[L]$ and $(j,k)\in\Pi_{2}(K)$. Our proof closely follows the
proof technique of Lemma 2 in Yang and Tan [2021]. Recall
$\Delta_{i,j,k}=(\mathbf{x}_{i,j}-\mathbf{x}_{i,k})^{\top}\bm{\theta}_{*}$. At
the end of round $n$, we bound the prediction error as follows

$\displaystyle\mathbb{P}\left(\mathbf{x}_{i,j}^{\top}\widehat{\bm{\theta}}_{n}<\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}\right)$
$\displaystyle=\mathbb{P}\left(\mathbf{x}_{i,j}^{\top}\widehat{\bm{\theta}}_{n}-\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}-\Delta_{i,j,k}<-\Delta_{i,j,k}\right)$
$\displaystyle=\mathbb{P}\left((\mathbf{x}_{i,j}-\mathbf{x}_{i,k})^{\top}\widehat{\bm{\theta}}_{n}-(\mathbf{x}_{i,j}-\mathbf{x}_{i,k})^{\top}\bm{\theta}_{*}<-\Delta_{i,j,k}\right)$
$\displaystyle=\mathbb{P}\left((\mathbf{x}_{i,j}-\mathbf{x}_{i,k})^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})<-\Delta_{i,j,k}\right)$
$\displaystyle\leq\mathbb{P}\left(\mathbf{x}_{i,j}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})<-\Delta_{i,j,k}\right)+\mathbb{P}\left(\mathbf{x}_{i,k}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})>\Delta_{i,j,k}\right)$
$\displaystyle\overset{(a)}{\leq}\exp\left(-\dfrac{\Delta^{2}_{i,j,k}}{2\|\mathbf{x}_{i,j}\|^{2}_{\overline{\mathbf{\Sigma}}^{-1}_{n}}}\right)+\exp\left(-\dfrac{\Delta^{2}_{i,j,k}}{2\|\mathbf{x}_{i,k}\|^{2}_{\overline{\mathbf{\Sigma}}^{-1}_{n}}}\right)$
$\displaystyle\overset{(b)}{\leq}\exp\left(-\dfrac{n\Delta^{2}_{i,j,k}}{2d}\right)+\exp\left(-\dfrac{n\Delta^{2}_{i,j,k}}{2d}\right)$
$\displaystyle=2\exp\left(-\dfrac{n\Delta^{2}_{i,j,k}}{2d}\right),$

where, $(a)$ follows from Lemma C.2, and $(b)$ follows from Lemma 4.1.
Finally, the total probability of error for the fixed budget setting under
absolute feedback is given by

$\displaystyle\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbb{P}\left(\mathbf{x}_{i,j}^{\top}\widehat{\bm{\theta}}_{n}<\mathbf{x}_{i,k}^{\top}\widehat{\bm{\theta}}_{n}\right)$
$\displaystyle\leq\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}2\exp\left(-\dfrac{n\Delta^{2}_{i,j,k}}{2d}\right).$

The claim of the proposition follows.

######  Lemma C.2.

For an arbitrary constant $\Delta$ and $\mathbf{x}\in\mathbb{R}^{d}$ we can
show that

$\displaystyle\mathbb{P}\left(\mathbf{x}^{\top}\left(\widehat{\bm{\theta}}-\bm{\theta}_{*}\right)>\Delta\right)\leq\exp\left(-\frac{\Delta^{2}}{2\|\mathbf{x}\|^{2}_{\overline{\mathbf{\Sigma}}^{-1}_{n}}}\right)$

where,
$\overline{\mathbf{\Sigma}}_{n}=\sum_{i=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{i,k}\mathbf{x}_{i,k}^{\top}$.

###### Proof.

The proof of the lemma is from Section 2.2 in Jamieson and Jain [2022]. Under
the sub-Gaussian noise assumption, we can show that for any vector
$\mathbf{x}\in\mathbb{R}^{d}$ the following holds

$\displaystyle\mathbf{x}^{\top}\left(\widehat{\bm{\theta}}-\bm{\theta}_{*}\right)=\underbrace{\mathbf{x}^{\top}\left(\mathbf{X}^{\top}\mathbf{X}\right)^{-1}\mathbf{X}^{\top}}_{\mathbf{w}}\eta=\mathbf{w}^{\top}\eta.$

Then for an arbitrary constant $\Delta$ and $\mathbf{x}\in\mathbb{R}^{d}$, we
can show that

$\displaystyle\mathbb{P}\left(\mathbf{x}^{\top}\left(\widehat{\bm{\theta}}-\bm{\theta}_{*}\right)>\Delta\right)$
$\displaystyle=\mathbb{P}\left(\mathbf{w}^{\top}\eta>\Delta\right)$
$\displaystyle\overset{(a)}{\leq}\exp(-\lambda\Delta)\mathbb{E}\left[\exp\left(\lambda\mathbf{w}^{\top}\eta\right)\right],\quad\text{
let }\lambda>0$
$\displaystyle=\exp(-\lambda\Delta)\mathbb{E}\left[\exp\left(\lambda\sum_{s=1}^{t}\mathbf{w}_{s}\eta_{s}\right)\right]$
$\displaystyle\overset{(b)}{=}\exp(-\lambda\Delta)\prod_{s=1}^{t}\mathbb{E}\left[\exp\left(\lambda\mathbf{w}_{s}\eta_{s}\right)\right]$
$\displaystyle\overset{(c)}{\leq}\exp(-\lambda\Delta)\prod_{s=1}^{t}\exp\left(\lambda^{2}\mathbf{w}_{s}^{2}/2\right)$
$\displaystyle=\exp(-\lambda\Delta)\exp\left(\frac{\lambda^{2}}{2}\|\mathbf{w}\|_{2}^{2}\right)$
$\displaystyle\overset{(d)}{\leq}\exp\left(-\frac{\Delta^{2}}{2\|\mathbf{w}\|_{2}^{2}}\right)$
$\displaystyle\overset{(e)}{=}\exp\left(-\frac{\Delta^{2}}{2\mathbf{x}^{\top}\left(\mathbf{X}^{\top}\mathbf{X}\right)^{-1}\mathbf{x}}\right)=\exp\left(-\frac{\Delta^{2}}{2\|\mathbf{x}\|^{2}_{\overline{\mathbf{\Sigma}}^{-1}_{n}}}\right)$

where, $(a)$ follows from Chernoff Bound, $(b)$ follows from independence of
$\mathbf{w}_{s}\eta_{s}$, $(c)$ follows sub-Gaussian assumption, $(d)$ follows
by setting $\lambda=\frac{\Delta}{\|\mathbf{w}\|^{2}_{2}}$, and $(e)$ follows
from the equality

$\|\mathbf{w}\|_{2}^{2}=\mathbf{x}^{\top}\left(\mathbf{X}^{\top}\mathbf{X}\right)^{-1}\mathbf{X}^{\top}\mathbf{X}\left(\mathbf{X}^{\top}\mathbf{X}\right)^{-1}\mathbf{x}=\mathbf{x}^{\top}\left(\mathbf{X}^{\top}\mathbf{X}\right)^{-1}\mathbf{x}.$

The claim of the lemma follows. ∎

##  Appendix D Learning with Ranking Feedback

###  D.1 Semi norm bound for ranking feedback

######  Lemma D.1.

Fix $\delta\in(0,1)$. Under the ranking feedback model, for any $\lambda>0$
and a constant $C>0$, with probability at least $1-\delta$,

$\displaystyle\left\|\widehat{\bm{\theta}}_{n}-\bm{\theta}^{*}\right\|^{2}_{\mathbf{\Sigma}_{n}}\leq
C\cdot\left(\frac{K^{4}(d+\log(1/\delta))}{n}\right).$

###### Proof.

Step 1 (Strong Convexity of loss): We first prove the strong convexity of the
loss $\ell_{\mathcal{D}_{n}}(\bm{\theta})$ with respect to the semi-norm
$\|\cdot\|_{\mathbf{\Sigma}_{n}}$ at $\bm{\theta}_{*}$ meaning that there is
some constant $\gamma>0$ such that

$\displaystyle\ell_{n}\left(\bm{\theta}_{*}+\Delta\right)-\ell_{n}\left(\bm{\theta}_{*}\right)-\left\langle\nabla\ell_{n}\left(\bm{\theta}_{*}\right),\Delta\right\rangle\geq\gamma\|\Delta\|_{\mathbf{\Sigma}_{n}}^{2}$

for all pertubations of $\Delta$ such that
$\bm{\theta}_{*}+\Delta\in\mathbf{\Theta}$. First, the Hessian of the negative
log-likelihood can be written as

$\displaystyle\nabla^{2}\ell_{n}(\bm{\theta})$
$\displaystyle=\frac{1}{n}\sum_{t=1}^{n}\sum_{j=1}^{K}\sum_{k=j}^{K}\sum_{k^{\prime}=j}^{K}\frac{\exp\left(\bm{\theta}^{\top}\mathbf{x}_{I_{t},\sigma_{t}(k)}+\bm{\theta}^{\top}\mathbf{x}_{I_{t},\sigma_{t}\left(k^{\prime}\right)}\right)}{2\left(\sum_{k^{\prime}=j}^{K-1}\exp\left(\bm{\theta}^{\top}\mathbf{x}_{I_{t},\sigma_{t}\left(k^{\prime}\right)}\right)\right)^{2}}\cdot\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}^{\top}.$

Since $\exp(\bm{\theta}^{\top}\mathbf{x})\in[\mathrm{e}^{-1},\mathrm{e}]$ for
any $\mathbf{x}$, we know that the coefficients satisfy

$\displaystyle\frac{\exp\left(\bm{\theta}^{\top}\mathbf{x}_{I_{t},\sigma_{t}(k)}+\bm{\theta}^{\top}\mathbf{x}_{I_{t},\sigma_{t}\left(k^{\prime}\right)}\right)}{\left(\sum_{k^{\prime}=j}^{K-1}\exp\left(\bm{\theta}^{\top}\mathbf{x}_{I_{t},\sigma_{t}\left(k^{\prime}\right)}\right)\right)^{2}}\geq\frac{\mathrm{e}^{-4}}{2(K-j)^{2}}.$
(26)

This implies that for any arbitrary vector $\mathbf{v}\in\mathbb{R}^{d}$ we
have that

$\displaystyle\mathbf{v}^{\top}\nabla^{2}\ell_{n}(\bm{\theta})\mathbf{v}$
$\displaystyle\geq\frac{1}{n}\mathbf{v}^{\top}\left(\sum_{t=1}^{n}\sum_{j=1}^{K}\frac{1}{(K-j)^{2}}\sum_{k=j}^{K}\sum_{k^{\prime}=j}^{K}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}^{\top}\right)\mathbf{v}$
$\displaystyle=\mathbf{v}^{\top}\left(\mathbf{\Sigma}_{n}+\sum_{t=1}^{n}\sum_{j=0}^{K}\frac{1}{n(K-j)^{2}}\sum_{k=j}^{K}\sum_{k^{\prime}=j}^{K}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}^{\top}-\mathbf{\Sigma}_{n}\right)\mathbf{v}$
$\displaystyle\overset{(a)}{\geq}\mathbf{v}^{\top}\mathbf{\Sigma}_{n}\mathbf{v}$
$\displaystyle=\|\mathbf{v}\|_{\mathbf{\Sigma}_{n}}^{2},$

where $(a)$ follows by noting

$\displaystyle\sum_{t=1}^{n}\sum_{j=1}^{K}\frac{1}{n(K-j)^{2}}\sum_{k=j}^{K}\sum_{k^{\prime}=j}^{K-1}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}^{\top}-\mathbf{\Sigma}_{n}$
(27)
$\displaystyle=\sum_{t=1}^{n}\sum_{j=1}^{K}\frac{1}{n(K-j)^{2}}\sum_{k=j}^{K}\sum_{k^{\prime}=j}^{K}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}^{\top}-\frac{2}{K(K-1)n}\sum_{t=1}^{n}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbf{z}_{I_{t},j,k}\mathbf{z}_{I_{t},j,k}^{\top}$
(28)
$\displaystyle=\sum_{t=1}^{n}\frac{1}{n}\left(\sum_{j=1}^{K}\frac{1}{(K-j)^{2}}\sum_{k=j}^{K}\sum_{k^{\prime}=j}^{K}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}\mathbf{z}_{I_{t},\sigma_{t}(k),\sigma_{t}(k^{\prime})}^{\top}-\frac{2}{K(K-1)}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbf{z}_{I_{t},j,k}\mathbf{z}_{I_{t},j,k}^{\top}\right),$
(29)

is positive semi-definite matrix.

Hence, we have that $\ell_{n}(\bm{\theta})$ is strongly convex at
$\bm{\theta}_{*}$ with respect to the norm $\|\cdot\|_{\mathbf{\Sigma}_{n}}$.
Therefore, we have

$\displaystyle\gamma\|\Delta\|_{\mathbf{\Sigma}_{n}}^{2}$
$\displaystyle\leq\ell_{n}\left(\bm{\theta}_{*}+\Delta\right)-\ell_{n}\left(\bm{\theta}_{*}\right)-\left\langle\nabla\ell_{n}\left(\bm{\theta}_{*}\right),\Delta\right\rangle$
$\displaystyle\overset{(a)}{\leq}-\left\langle\nabla\ell_{n}\left(\bm{\theta}_{*}\right),\Delta\right\rangle$
$\displaystyle\leq\left\|\nabla\ell_{n}\left(\bm{\theta}_{*}\right)\right\|_{\mathbf{\Sigma}_{n}^{-1}}\|\Delta\|_{\mathbf{\Sigma}_{n}}$

where, $(a)$ follows as
$\ell_{n}\left(\widehat{\bm{\theta}}_{n}\right)\leq\ell_{n}\left(\bm{\theta}_{*}\right)$,
and the last inequality follows from
$|\left\langle\nabla\ell_{n}\left(\bm{\theta}_{*}\right),\Delta\right\rangle|\leq\left\|\nabla\ell_{n}\left(\bm{\theta}_{*}\right)\right\|_{\mathbf{\Sigma}_{n}^{-1}}\|\Delta\|_{\mathbf{\Sigma}_{n}}$.

Step 2 (Upper bound the gradient of loss $\ell_{n}(\bm{\theta}_{*})$): First
recall that the gradient of loss is as follows

$\displaystyle\nabla\ell_{n}\left(\bm{\theta}_{*}\right)$
$\displaystyle=-\frac{1}{n}\sum_{t=1}^{n}\sum_{j=1}^{K}\sum_{k=j}^{K}\frac{\exp\left(\bm{\theta}_{*}^{\top}\mathbf{x}_{I_{t},\sigma_{t}(k)}^{i}\right)}{\sum_{k^{\prime}=j}^{K}\exp\left(\bm{\theta}_{*},\mathbf{x}_{I_{t},\sigma_{t}\left(k^{\prime}\right)}^{i}\right)}\mathbf{z}_{I_{t},\sigma_{t}(j),\sigma_{t}(k)}$
$\displaystyle\overset{(a)}{=}\frac{1}{n}\sum_{t=1}^{n}\sum_{j=1}^{K}\sum_{k=j}^{K}V_{I_{t},j,k}\mathbf{z}_{I_{t},j,k}$
$\displaystyle=\frac{1}{n}\mathbf{X}^{T}\mathbf{V},$

where, in $(a)$ we have define

$\displaystyle
V_{I_{t},j,k}=\begin{cases}\frac{\exp\left(\bm{\theta}_{*}^{\top}\mathbf{x}_{I_{t},k}\right)}{\sum_{k^{\prime}=\sigma_{t}^{-1}(j)}^{K-1}\exp\left(\bm{\theta}_{*}^{\top}\mathbf{x}_{I_{t},\sigma_{t}\left(k^{\prime}\right)}\right)},&\text{
if }\sigma_{t}^{-1}(j)<\sigma_{t}^{-1}(k)\\\
-\frac{\exp\left(\bm{\theta}_{*}^{\top}\mathbf{x}_{I_{t},j}\right)}{\sum_{k^{\prime}=\sigma_{t}^{-1}(k)}^{K-1}\exp\left(\bm{\theta}_{*}^{\top},\mathbf{x}_{I_{t},\sigma_{t}\left(k^{\prime}\right)}\right)},&\text{
otherwise. }\end{cases}$

In $(b)$ we define matrix $\mathbf{X}\in\mathbb{R}^{(nK(K-1)/2)\times d}$ has
the differencing vector $\mathbf{z}_{I_{t},jk}$ as its $(tK(K-$ 1)
$\left./2+k+\sum_{l=K-j+1}^{K}l\right)^{th}$ row and
$\mathbf{V}\in\mathbb{R}^{nK(K-1)/2}$ is the concatenated vector of
$\\{\left\\{V_{I_{t},j,k}\right\\}_{0\leq j<k\leq K-1}\\}_{t=1}^{n}$. With
this notation, we have

$\displaystyle\left\|\nabla\ell_{n}\left(\bm{\theta}_{*}\right)\right\|^{2}_{\mathbf{\Sigma}^{-1}_{n}}$
$\displaystyle\overset{}{=}\frac{1}{n^{2}}\mathbf{V}^{\top}\mathbf{X}\mathbf{\Sigma}_{n}^{-1}\mathbf{X}^{\top}\mathbf{V}$
$\displaystyle\overset{(a)}{\leq}\frac{K^{2}}{n}\|\mathbf{V}\|_{2}^{2}$
$\displaystyle\overset{(b)}{\leq}CK^{4}\cdot(d+\log(1/\delta)),$

where $(a)$ follows as
$\frac{K^{2}}{n}I\succeq\frac{1}{n^{2}}\mathbf{X}\mathbf{\Sigma}_{n}^{-1}\mathbf{X}^{\top}$
and the $(b)$ follows with probability $1-\delta$ as the vector $\mathbf{V}$
is sub-Gaussian with parameter $K$ (follows from Zhu et al. [2023b]) and
Bernstein’s inequality for sub-Gaussian random variables in quadratic form.

Step 3 (Combining everything): Combining everything we have

$\displaystyle\gamma\|\Delta\|_{\mathbf{\Sigma}_{n}}^{2}$
$\displaystyle\leq\left\|\nabla\ell_{n}\left(\bm{\theta}_{*}\right)\right\|_{\mathbf{\Sigma}_{n}^{-1}}\|\Delta\|_{\mathbf{\Sigma}_{n}}$
$\displaystyle\leq\sqrt{C\cdot\frac{K^{4}(d+\log(1/\delta))}{n}}\|\Delta\|_{\mathbf{\Sigma}_{n}},$

for some finite constant $C>0$. It follows then that

$\displaystyle\left\|\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\right\|^{2}_{\mathbf{\Sigma}_{n}}\leq
C\cdot\left(\frac{K^{4}(d+\log(1/\delta))}{n}\right).$

The claim of the lemma follows. ∎

###  D.2 Proof of Proposition 5.4

Following the same steps as that of Proposition 4.4, at the end of round $n$,
we bound the prediction error for $(j,k)\in\Pi_{2}(K)$ for list $i\in[L]$
under ranking feedback as follows

$\displaystyle\mathbb{P}\left(\mathbf{x}_{i,\sigma^{*}_{i}(j)}^{\top}\widehat{\bm{\theta}}_{n}<\mathbf{x}_{i,\sigma^{*}_{i}(k)}^{\top}\widehat{\bm{\theta}}_{n}\right)$
$\displaystyle=\mathbb{P}\left(\mathbf{x}_{i,\sigma^{*}_{i}(j)}^{\top}\widehat{\bm{\theta}}_{n}-\mathbf{x}_{i,\sigma^{*}_{i}(k)}^{\top}\widehat{\bm{\theta}}_{n}-\Delta_{i,j,k}<-\Delta_{i,j,k}\right)$
$\displaystyle=\mathbb{P}\left((\mathbf{x}_{i,\sigma^{*}_{i}(j)}-\mathbf{x}_{i,\sigma^{*}_{i}(k)})^{\top}\widehat{\bm{\theta}}_{n}-(\mathbf{x}_{i,\sigma^{*}_{i}(j)}-\mathbf{x}_{i,\sigma^{*}_{i}(k)})^{\top}\bm{\theta}_{*}<-\Delta_{i,j,k}\right)$
$\displaystyle=\mathbb{P}\left((\mathbf{x}_{i,\sigma^{*}_{i}(j)}-\mathbf{x}_{i,\sigma^{*}_{i}(k)})^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})<-\Delta_{i,j,k}\right)$
$\displaystyle=\mathbb{P}\left(\mathbf{z}_{i,\sigma^{*}_{i}(j),\sigma^{*}_{i}(k)}^{\top}(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*})<-\Delta_{i,j,k}\right)$
$\displaystyle\overset{(a)}{\leq}\exp\left(-\dfrac{\kappa^{2}\Delta^{2}_{i,j,k}}{2\|\mathbf{z}_{i,\sigma^{*}_{i}(j),\sigma^{*}_{i}(k)}\|^{2}_{\overline{\mathbf{\Sigma}}^{-1}_{n}}}\right)$
$\displaystyle\overset{(b)}{\leq}\exp\left(-\dfrac{n\kappa^{2}\Delta^{2}_{i,j,k}}{2d}\right)$

where, $(a)$ follows from Lemma D.2, and $(b)$ follows from Lemma 4.1.
Finally, the total probability of error for the fixed budget setting under
absolute feedback is given by

$\displaystyle\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbb{P}\left(\mathbf{x}_{i,\sigma^{*}_{i}(k)}^{\top}\widehat{\bm{\theta}}_{n}>\mathbf{x}_{i,\sigma^{*}_{i}(j)}^{\top}\widehat{\bm{\theta}}_{n}\right)$
$\displaystyle\leq\max_{i\in[L]}\sum_{j=1}^{K}\sum_{k=j+1}^{K}2\exp\left(-\dfrac{n\kappa^{2}\Delta^{2}_{i,j,k}}{2d}\right).$

The claim of the proposition follows.

######  Lemma D.2.

(Restatement of Theorem 1 from Li et al. [2017]) Let $\delta>0$ be given
Furthermore, assume that

$\displaystyle\lambda_{\min}\left(\overline{\mathbf{\Sigma}}_{n}\right)\geq\frac{512\gamma^{2}}{\kappa^{4}}\left(d^{2}+\log\frac{1}{\delta}\right).$

where,$\kappa:=\inf_{\left\\{\|\mathbf{x}\|\leq
1,\left\|\bm{\theta}-\bm{\theta}_{*}\right\|\leq
1\right\\}}\nabla{\exp}\left(\mathbf{x}^{\top}\bm{\theta}\right)>0$ from 5.2.
Then, with probability at least $1-3\delta$, the maximum likelihood estimator
for a generalized least square model satisfies, for any
$\mathbf{x}\in\mathbb{R}^{d}$, that

$\displaystyle\left|\mathbf{x}^{\top}\left(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\right)\right|\leq\frac{3}{\kappa}\sqrt{\log(1/\delta)}\|\mathbf{x}\|_{\overline{\mathbf{\Sigma}}_{n}^{-1}}.$

Setting,
$\delta=\exp\left(-\dfrac{9\kappa^{2}\Delta^{2}}{\|\mathbf{x}\|_{\overline{\mathbf{\Sigma}}_{n}^{-1}}}\right)$
for some arbitrary constant $\Delta>0$ we get that

$\displaystyle\mathbb{P}\left(\mathbf{x}^{\top}\left(\widehat{\bm{\theta}}_{n}-\bm{\theta}_{*}\right)\geq\Delta\right)\leq\exp\left(-\dfrac{9\kappa^{2}\Delta^{2}}{\|\mathbf{x}\|_{\overline{\mathbf{\Sigma}}_{n}^{-1}}}\right).$

for
$\lambda_{\min}\left(\overline{\mathbf{\Sigma}}_{n}\right)\geq\frac{512}{\kappa^{4}}\left(d^{2}+\frac{\|\mathbf{x}\|_{\overline{\mathbf{\Sigma}}_{n}^{-1}}}{9\kappa^{2}\Delta^{2}}\right)$.

##  Appendix E Table of Notations

Notations |  Definition
---|---
$K$ |  Total number of items in a list
$d$ |  Dimension of the feature
$L$ |  Total number of list
$\triangle^{L}$ |  Probability simplex over $L$ items
$\pi_{*}$ |  Optimal design over $L$ lists
$\sigma_{t}:[K]\rightarrow[K]$ |  permutation provided by the human labeler at round $t$
$\mathbf{x}_{i,k}$ |  Feature of the $k$-th item in the list $i$
$\bm{\theta}_{*}$ |  Hidden parameter for the feedback model
$\mathbb{P}\left(\sigma_{t}\right)=\prod_{k=1}^{K}\frac{\exp\left(\mathbf{x}_{I_{t},\sigma_{t}(k)}^{\top}\bm{\theta}_{*}\right)}{\sum_{i=k}^{K}\exp\left(\mathbf{x}_{I_{t},\sigma_{t}(i)}^{\top}\bm{\theta}_{*}\right)}$ |  Plackett-Luce model
$y_{t,k}=\mathbf{x}_{I_{t},k}^{\top}\bm{\theta}_{*}+\eta_{t,k},$ |  Absolute feedback model
$n$ |  Total horizon
$\Pi_{2}(K)=\\{(j,k):j<k;j,k\in[K]\\}$ |  set of all ordered pairs where the first coordinate is strictly less than the second one.
$\kappa:=\inf_{\left\\{\|\mathbf{x}\|\leq 1,\left\|\bm{\theta}-\bm{\theta}_{*}\right\|\leq 1\right\\}}\nabla{\exp}\left(\mathbf{x}^{\top}\bm{\theta}\right)$ |  Lower bound of gradient
$\mathbf{V}_{\pi}=\sum_{i=1}^{L}\pi(i)\mathbf{A}_{i}\mathbf{A}_{i}^{\top}$ |  Design matrix
$\mathbf{\Sigma}_{n}=\frac{1}{n}\sum_{t=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{I_{t},k}\mathbf{x}_{I_{t},k}^{\top}$ |  Covariance matrix for absolute feedback
$\mathbf{\Sigma}_{n}=\frac{2}{K(K-1)n}\sum_{t=1}^{n}\sum_{j=1}^{K}\sum_{k=j+1}^{K}\mathbf{z}_{I_{t},j,k}\mathbf{z}_{I_{t},j,k}^{\top}$ |  Covariance matrix for ranking feedback
$\overline{\mathbf{\Sigma}}_{n}\\!=\\!\dfrac{K(K-1)n}{2}\mathbf{\Sigma}_{n}$ |  Un-normalized covariance matrix for ranking feedback
$\Delta_{i,j,k}=(\mathbf{x}_{i,j}-\mathbf{x}_{i,k})^{\top}\bm{\theta}_{*}$ |  Gap between the mean rewards of items $j$ and $k$ such that $(j,k)\in\Pi_{2}(K)$ in list $i$
Table 1: Table of Notations

##  Appendix F Dope Algorithms

In this section we present the full pseudo-code of our algorithm Dope both for
the absolute and ranking feedback. First in Algorithm 1 we present the Dope
for the absolute feedback setting. The algorithmic details are given in
Section 4.1. Then in Algorithm 2 we present the Dope for the ranking feedback
setting under the PL model. The algorithmic details are given in Section 5.1.

Algorithm 1 Dope under absolute feedback

1: Input: Feature vectors $\mathbf{x}_{i,k}$ for all items $k\in[K]$ and for
all lists $i\in[L]$, budget $n$

2: for $i=1,\ldots,L$ do

3:
$\mathbf{A}_{i}\leftarrow[\mathbf{x}_{i,1},\mathbf{x}_{i,2},\ldots,\mathbf{x}_{i,1K}]$

4: end for

5:
$\mathbf{V}_{\pi}\leftarrow\sum_{i=1}^{L}\pi(i)\mathbf{A}_{i}\mathbf{A}_{i}^{\top}$

6: $\pi_{*}\leftarrow\max_{\pi\in\triangle^{L}}\log\det(\mathbf{V}_{\pi})$

7: for $t=1,\dots,n$ do

8: $I_{t}\sim\pi_{*}$

9: Observe $y_{I_{t},k}$ for all $k\in[K]$

10: end for

11:
$\mathbf{\Sigma}_{n}\leftarrow\frac{1}{n}\sum_{t=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{I_{t},k}\mathbf{x}_{I_{t},k}^{\top}$
(Covariance matrix)

12:
$\widehat{\bm{\theta}}_{n}\leftarrow\overline{\mathbf{\Sigma}}_{n}^{-1}\sum_{t=1}^{n}\sum_{k=1}^{K}\mathbf{x}_{I_{t},k}y_{t,k}$
(MLE under absolute feedback)

13: for $i=1,\dots,L$ do

14:
$R_{i}\leftarrow[\mathbf{x}_{i,1}^{\top}\widehat{\bm{\theta}}_{n},\mathbf{x}_{i,2}^{\top}\widehat{\bm{\theta}}_{n},\ldots,\mathbf{x}_{i,K}^{\top}\widehat{\bm{\theta}}_{n}]$
(estimated mean rewards)

15: Sort $R_{i}$ in descending order

16: for $k=1,\ldots,K$ do

17: $\sigma_{n,i}(k)\leftarrow$ item in $k$-th position in $R_{i}$

18: end for

19: end for

20: Output: Permutation $\sigma_{n,i}(k)$ for all $i\in[L]$

Algorithm 2 Dope under ranking feedback

1: Input: Feature vectors $\mathbf{x}_{i,k}$ for all items $k\in[K]$ and for
all lists $i\in[L]$, budget $n$

2: for $i=1,\dots,L$ do

3: for $j=1\dots,K$ do

4: for $k=j+1\dots,K$ do

5: $\mathbf{z}_{i,j,k}\leftarrow\mathbf{x}_{i,j}-\mathbf{x}_{i,k}$

6: end for

7: end for

8: $\mathbf{A}_{i}\leftarrow[\mathbf{z}_{i,j,k}]_{(j,k)\in\Pi_{2}(K)}$

9: end for

10:
$\mathbf{V}_{\pi}\leftarrow\sum_{i=1}^{L}\pi(i)\mathbf{A}_{i}\mathbf{A}_{i}^{\top}$

11: $\pi_{*}\leftarrow\max_{\pi\in\triangle^{L}}\log\det(\mathbf{V}_{\pi})$

12: for $t=1,\dots,n$ do

13: $I_{t}\sim\pi_{*}$

14: Observe $\sigma_{I_{t}}$

15: end for

16: $\widehat{\bm{\theta}}_{n}\leftarrow\mathop{\rm
arg\,min}_{\bm{\theta}}-\frac{1}{n}\sum_{t=1}^{n}\sum_{k=1}^{K}\log\left(\frac{\exp\left(\mathbf{x}_{I_{t},\sigma_{t}(k)}^{\top}\bm{\theta}\right)}{\sum_{k^{\prime}=k}^{K-1}\exp\left(\mathbf{x}_{I_{t},\sigma_{t}(k^{\prime})}^{\top}\bm{\theta}\right)}\right)$
(MLE under ranking feedback)

17: for $i=1,\dots,L$ do

18:
$R_{i}\leftarrow[\mathbf{x}_{i,1}^{\top}\widehat{\bm{\theta}}_{n},\mathbf{x}_{i,2}^{\top}\widehat{\bm{\theta}}_{n},\ldots,\mathbf{x}_{i,K}^{\top}\widehat{\bm{\theta}}_{n}]$
(estimated mean rewards)

19: Sort $R_{i}$ in descending order

20: for $k=1,\ldots,K$ do

21: $\sigma_{n,i}(k)\leftarrow$ item in $k$-th position in $R_{i}$

22: end for

23: end for

24: Output: Permutation $\sigma_{n,i}$ for all $i\in[L]$