# Predicting the Price Movement of Cryptocurrencies Using Linear Law-based
Transformation

Marcell T. Kurbucz<EMAIL_ADDRESS>Péter Pósfay
<EMAIL_ADDRESS>Antal Jakovác<EMAIL_ADDRESS>Department of
Computational Sciences, Wigner Research Centre for Physics, 29-33 Konkoly-
Thege Miklós Street,
H-1121 Budapest, Hungary  Institute of Data Analytics and Information Systems,
Corvinus University of Budapest, 8 Fővám Square,
H-1093 Budapest, Hungary

###### Abstract

The aim of this paper is to investigate the effect of a novel method called
linear law-based feature space transformation (LLT) on the accuracy of
intraday price movement prediction of cryptocurrencies. To do this, the
1-minute interval price data of Bitcoin, Ethereum, Binance Coin, and Ripple
between 1 January 2019 and 22 October 2022 were collected from the Binance
cryptocurrency exchange. Then, $14$-hour nonoverlapping time windows were
applied to sample the price data. The classification was based on the first
$12$ hours, and the two classes were determined based on whether the closing
price rose or fell after the next $2$ hours. These price data were first
transformed with the LLT, then they were classified by traditional machine
learning algorithms with $10$-fold cross-validation. Based on the results, LLT
greatly increased the accuracy for all cryptocurrencies, which emphasizes the
potential of the LLT algorithm in predicting price movements.

###### keywords:

Time series classification, Linear law, Feature space transformation, Feature
engineering, Cryptocurrency, Artificial intelligence

††journal: arXiv

##  1 Introduction

The advent of cryptocurrencies has revolutionized the world of finance and
investment.111The concept of Bitcoin, i.e. the first blockchain application,
was made public in Nakamoto (2008). Cryptocurrencies, such as Bitcoin and
Ethereum, are decentralized digital assets that operate on blockchain
technology. Contrary to traditional financial systems, this technology ignores
financial intermediaries and provides a public ledger that records all
transactions. Predicting the price movement of these currencies creates a
number of challenges, especially due to the extremely high volatility of their
exchange prices (Mahayana et al., 2022). As reflected by current market
dynamics, the absence of government regulation and oversight creates obstacles
in mitigating the high volatility and consequential losses that may arise (Dag
et al., 2023). For this reason, traders and investors must use appropriate
price prediction methods that consider the extreme behavior of cryptocurrency
markets (Mba & Mwambi, 2020).

In recent years, several studies have been conducted on the classification of
intraday price movements of cryptocurrencies. For instance, El-Berawi et al.
(2021) proposed a deep learning model for forecasting and classifying the
price of various cryptocurrencies based on a multiple-input architecture. To
identify the relevant variables, they applied a two-stage adaptive feature
selection procedure. Mahayana et al. (2022) predicted the price movement of
Bitcoin’s exchange rate using a tree-based classification algorithm with the
gradient boosting framework. In Zhou et al. (2023), price movements were
predicted by a support vector machine algorithm based on historical trading
data, sentiment indicators, and daily Google Trends. Additionally, a data-
driven tree augmented naïve Bayes methodology was proposed by Dag et al.
(2023) that can be used for identifying the most important factors influencing
the price movements of Bitcoin. Other works focus on the predictive power of
the features obtained from the transaction network of various cryptocurrencies
(Abay et al., 2019; Akcora et al., 2018a, b; Dey et al., 2020; Kurbucz, 2019).

The recently published algorithm called linear law-based feature space
transformation (LLT) (Kurbucz et al., 2022) can be applied to facilitate uni-
and multivariate time series classification tasks. The aim of this paper is to
investigate the effect of LLT on the accuracy of intraday price movement
prediction of various cryptocurrencies. To do this, the 1-minute interval
price data of Bitcoin, Ethereum, Binance Coin, and Ripple between 1 January
2019 and 22 October 2022 were collected from the Binance cryptocurrency
exchange. Then, $14$-hour nonoverlapping time windows were applied to sample
the price data. The classification was based on the first $12$ hours, and the
two classes were determined based on whether the closing price rose or fell
after the next $2$ hours. These price data were first transformed with the
LLT, and then they were classified by traditional machine learning algorithms
with $10$-fold cross-validation and Bayesian hyperparameter optimization.

The rest of this paper is organized as follows. Section 2 introduces the
employed dataset, the classification task, the LLT algorithm, and the applied
software and its settings. Section 3 compares and discusses the classification
outcomes obtained with and without the LLT. Finally, conclusions and suggested
future research directions are provided in Section 3.

##  2 Data and methodology

###  2.1 Cryptocurrency dataset

This study is based on the 1-minute interval price data of Bitcoin (BTC),
Ethereum (ETH), Binance Coin (BNB), and Ripple (XRP) between 1 January 2019
and 22 October 2022. These data were collected from the Binance cryptocurrency
exchange by the CryptoDataDownload website
(https://www.cryptodatadownload.com/, retrieved: 19 April 2023). For each
cryptocurrency, the obtained dataset contains the opening, closing, high, and
low prices, as well as the transaction volume and the volume of Tether (USDT):
i.e., the volume of the stablecoin that prices were measured against.
Hereinafter, these variables are called the initial features of
cryptocurrencies.

###  2.2 Classification task

To define the classification task, we first generated instances by sampling
the price datasets based on $14$-hour, nonoverlapping time windows. The input
data ($\bm{X}$) of the classification task were the $720$ ($k$) consecutive
values of the $6$ ($m$) initial features, measured in the first $12$ hours.
The output variable contains two classes defined by whether the closing price
rose or fell after the next $2$ hours. After we balanced the number of
instances related to the two classes, this sampling procedure resulted in
approximately $1\,680$ ($n$) instances in each cryptocurrency: $840$ per
class. The applied sampling procedure is illustrated in Fig. 1.

Figure 1: Applied sampling procedure

Formally, input data are denoted by
$\bm{X}=\\{\bm{X}_{t}\;|\;t\in\\{1,2,\dots,k\\}\\}$, where $t$ represents the
observation times. The internal structure of the input data is
$\bm{X}_{t}=\\{\bm{x}_{t}^{i,j}\;|\;i\in\\{1,2,\dots,n\\},~{}j\in\\{1,2,\dots,m\\}\\}$,
where $i$ indicates the instances and $j$ identifies the different initial
features belonging to a given instance. The output is a vector
$\bm{y}\in\\{0,1\\}$ identifying the classes of instances
($\bm{y}=\\{y^{i}\in\mathbb{R}\;|\;i\in\\{1,2,\dots,n\\}\\}$). The goal of the
classification task is to predict the $\bm{y}$ values (classes) from the
$\bm{X}$ input data.

###  2.3 Price movement prediction

Price movement prediction is based on the combination of the LLT with
traditional machine learning algorithms.222The concept of linear laws is
detailed in Jakovác (2021) and Jakovác et al. (2022). The complete
mathematical formulation of LLT can be found in Kurbucz et al. (2022).

LLT first separates the ($tr\in\small\\{1,2,\dots,\tau\small\\}$) and tests
($te\in\small\\{\tau+1,\tau+2,\dots,n\small\\}$) the sets of
instances.333Instances are split in such a way that their classes are balanced
in the two sets. For transparency, we assume that the original arrangement of
the instances in the dataset satisfies this condition for the $tr$ and $te$
sets. Then, it identifies the governing patterns (linear laws) of each input
sequence in the training set. To this end, we perform the $l^{\text{th}}$
order ($l\in\mathbb{Z}^{+}$ and $l<k$) time-delay embedding (Takens, 1981) of
these series as follows:

$\bm{A}^{tr,j}=\left(\begin{matrix}\bm{x}^{tr,j}_{1}&\bm{x}^{tr,j}_{2}&\cdots&\bm{x}^{tr,j}_{l}\\\
\ \bm{x}^{tr,j}_{2}&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\vdots\\\
\bm{x}^{tr,j}_{k-l}&\cdots&\cdots&\bm{x}^{tr,j}_{k}\\\ \end{matrix}\right),$
(1)

for all $tr$ and $j$. Then, symmetric $l\times l$ matrices are generated as
$\bm{S}^{tr,j}={\bm{A}^{tr,j}}^{\intercal}\bm{A}^{tr,j}$. The coefficients
($\bm{v}^{tr,j}$) that satisfy $\bm{S}^{tr,j}\bm{v}^{tr,j}\approx\mathbf{0}$
are called the linear law of the input series $\bm{x}^{tr,j}_{t}$. These laws
are grouped by input series and classes as follows:
$\bm{V}^{j}=\\{\bm{V}^{j}_{0},\bm{V}^{j}_{1}\\}$, where $\bm{V}^{j}_{0}$ and
$\bm{V}^{j}_{1}$ denote the laws of the training set related to the initial
feature $j$ and the two classes.

The next step involves calculating $\bm{S}^{te,j}$ matrices from the test
instance’s initial features and left multiplying them by the $\bm{V}^{j}$
matrices obtained from the same initial features of the training instances
($\bm{S}^{\tau+1,1}\bm{V}^{1},\bm{S}^{\tau+1,2}\bm{V}^{2},\dots,\bm{S}^{n,m}\bm{V}^{m}$).
The product of these matrices gives an estimate of whether the test data
belong to the same class as the training instance based on the presence of
close-to-null vectors with a small variance in the resulting matrix. The final
step reduces the dimensions of the resulting matrices by selecting columns
with the smallest variance and/or absolute mean from the
$\bm{S}^{te,j}\bm{V}^{j}$ matrices for each class. As a result of this step,
the transformed feature space of the test set has $((n-\tau)l)\times(mc+1)$
dimensions combined with the output variable.

After the feature space transformation, test instances are classified by
decision tree (DT) (Li et al., 2019), k-nearest neighbor (KNN) (Mello et al.,
2019), support vector machine (SVM) (Al Tobi et al., 2019; Raghu et al.,
2019), and classifier ensemble (ENS) (Oza & Tumer, 2008) algorithms with
cross-validation and Bayesian hyperparameter optimization.

###  2.4 Applied software and settings

Datasets were transformed using the LLT R package (version: 0.1.0) (Kurbucz et
al., 2023a) with the following settings:444The LLT R package is publicly
available on GitHub (Kurbucz et al., 2023b).

  * •

test_ratio = 0.25: $25\%$ of the instances were included in the test set. The
training and test sets contained approximately $1284$ ($\tau$) and $428$
($n-\tau$) independent instances for each cryptocurrency: $642$ and $214$ from
both classes, respectively.

  * •

dim = 10: It defined the $l$ parameter ($l=10$).

  * •

lag = 11: The successive row lag of the $\bm{A}$ matrix is set to $11$. That
is, since $l=10$, $\bm{A}^{tr,j}_{1,10}=\bm{x}^{tr,j}_{10}$,
$\bm{A}^{tr,j}_{2,1}=\bm{x}^{tr,j}_{11}$,
$\bm{A}^{tr,j}_{2,2}=\bm{x}^{tr,j}_{12}$, and so on.

  * •

select = "var": As the last step of the LLT, the column vectors with the
smallest variance were selected from the $\bm{S}^{te,j}\bm{V}^{j}$ matrices
for each class.

  * •

seed = 12345: For the reproducibility of the results, the random number
generation was fixed.

The original and transformed classification tasks were solved in the
Classification Learner App of MATLAB.555More information can be found at
https://www.mathworks.com/help/stats/classificationlearner-app.html,
retrieved: 19 April 2023). For each classifier, $10$-fold cross-validation and
$300$-step Bayesian hyperparameter optimization were applied.

##  3 Results and discussion

The results of the original and transformed classification tasks are presented
in Table 1.666Related confusion matrices and the details of hyperparameter
optimization can be found in the Supplementary material.

Table 1: Classification accuracies (%)

(a) Original feature space

| BTC | ETH | BNB | XRP
---|---|---|---|---
Ensemble | 56.5 | 55.8 | 52.3 | 56.2
KNN | 57.0 | 55.8 | 57.5 | 57.3
DT | 57.0 | 54.2 | 50.8 | 52.4
SVM | 59.6 | 56.1 | 57.5 | 54.5

(b) Feature space transformed by LLT

| BTC | ETH | BNB | XRP
---|---|---|---|---
Ensemble | 75.2 | 80.8 | 70.4 | 79.5
KNN | 84.3 | 82.0 | 77.6 | 81.4
DT | 65.9 | 73.6 | 60.8 | 67.5
SVM | 65.9 | 64.3 | 58.8 | 62.0

As shown in Table 1, LLT greatly increased the accuracy for all classifiers
and cryptocurrencies. In the case of the original feature space, the SVM
algorithm achieved the best average performance with an accuracy of $56.9$%.
After the transformation, the KNN algorithm became the most accurate
classifier, with an average accuracy of $81.3$%. This result is consistent
with our previous work (Kurbucz et al., 2022), in which we tested the same
classifiers on human activity recognition data and found that the combination
of LLT and KNN achieved the highest accuracy and shortest computation time,
outperforming even state-of-the-art methods. Since LLT has a low calculation
requirement, it can effectively handle feature spaces with much higher
dimensions than previously used methods. Applying additional features, such as
sentiment indicators and daily Google Trends (Zhou et al., 2023), can result
in even higher classification accuracy.

##  4 Conclusions and future works

This paper investigated the effect of LLT on the accuracy of intraday price
movement prediction of cryptocurrencies. To do this, the 1-minute interval
price data of Bitcoin, Ethereum, Binance Coin, and Ripple between 1 January
2019 and 22 October 2022 were collected from the Binance cryptocurrency
exchange. Then, $14$-hour nonoverlapping time windows were applied to sample
the price data. The classification was based on the first $12$ hours, and the
two classes were determined based on whether the closing price rose or fell
after the next $2$ hours. These price data were first transformed with the LLT
and then classified by traditional machine learning algorithms with $10$-fold
cross-validation.

Based on the results, LLT greatly increased the accuracy regardless of the
type of cryptocurrency and classification algorithm. While the SVM algorithm
achieved the best results for the original feature space, after the
transformation, we achieved the highest average accuracy with the KNN
classifier. By using the LLT algorithm, we managed to increase the best
average accuracy from $56.9$% to $81.3$%. These results not only emphasize the
potential of the LLT algorithm in price movement prediction but also provide
further research directions. Future works could focus on the classification
performance of the LLT-KNN algorithm pair in high-dimensional feature spaces.
Other research could extend the LLT algorithm with the adaptive selection of
the laws used during the transformation. Finally, due to its low computational
cost, LLT could also be useful in the field of portfolio optimization, which
would require further investigation.

## Data availability

The applied price data were collected from the Binance cryptocurrency exchange
by the CryptoDataDownload website (https://www.cryptodatadownload.com/,
retrieved: 19 April 2023).

## Supplementary material

The supplementary material contains the confusion matrices related to Table 1
and the results of hyperparameter optimization applied during the
calculations.

## Acknowledgements

Project no. PD142593 was implemented with the support provided by the Ministry
of Culture and Innovation of Hungary from the National Research, Development,
and Innovation Fund, financed under the PD_22 “OTKA” funding scheme. A.J.
received support from the Hungarian Scientific Research Fund (OTKA/NRDI
Office) under contract number K123815. The research was supported by the
Ministry of Innovation and Technology NRDI Office within the framework of the
MILAB Artificial Intelligence National Laboratory Program.

## References

  * Abay et al. (2019) Abay, N. C., Akcora, C. G., Gel, Y. R., Kantarcioglu, M., Islambekov, U. D., Tian, Y., & Thuraisingham, B. (2019).  Chainnet: Learning on blockchain graphs with topological features.  In 2019 IEEE international conference on data mining (ICDM) (pp. 946–951).  IEEE.
  * Akcora et al. (2018a) Akcora, C. G., Dey, A. K., Gel, Y. R., & Kantarcioglu, M. (2018a).  Forecasting bitcoin price with graph chainlets.  In Advances in Knowledge Discovery and Data Mining: 22nd Pacific-Asia Conference, PAKDD 2018, Melbourne, VIC, Australia, June 3-6, 2018, Proceedings, Part III 22 (pp. 765–776).  Springer.
  * Akcora et al. (2018b) Akcora, C. G., Dixon, M. F., Gel, Y. R., & Kantarcioglu, M. (2018b).  Bitcoin risk modeling with blockchain graphs.  Economics Letters, 173, 138–142.
  * Al Tobi et al. (2019) Al Tobi, M. A. S., Bevan, G., Wallace, P., Harrison, D., & Ramachandran, K. (2019).  Fault diagnosis of a centrifugal pump using MLP-GABP and SVM with CWT.  Engineering Science and Technology, an International Journal, 22, 854–861.
  * Dag et al. (2023) Dag, A., Dag, A. Z., Asilkalkan, A., Simsek, S., & Delen, D. (2023).  A Tree Augmented Naïve Bayes-based methodology for classifying cryptocurrency trends.  Journal of Business Research, 156, 113522.
  * Dey et al. (2020) Dey, A. K., Akcora, C. G., Gel, Y. R., & Kantarcioglu, M. (2020).  On the role of local blockchain network features in cryptocurrency price formation.  Canadian Journal of Statistics, 48, 561–581.
  * El-Berawi et al. (2021) El-Berawi, A. S., Belal, M. A. F., & Abd Ellatif, M. M. (2021).  Adaptive deep learning based cryptocurrency price fluctuation Classification.  International Journal of Advanced Computer Science and Applications, 12.
  * Jakovác (2021) Jakovác, A. (2021).  Time series analysis with dynamic law exploration.  URL: https://arxiv.org/abs/2104.10970. doi:10.48550/ARXIV.2104.10970.
  * Jakovác et al. (2022) Jakovác, A., Kurbucz, M. T., & Pósfay, P. (2022).  Reconstruction of observed mechanical motions with artificial intelligence tools.  New Journal of Physics, 24, 073021.
  * Kurbucz (2019) Kurbucz, M. T. (2019).  Predicting the price of Bitcoin by the most frequent edges of its transaction network.  Economics letters, 184, 108655.
  * Kurbucz et al. (2023a) Kurbucz, M. T., Pósfai, P., & Jakovác, A. (2023a).  LLT: An R package for Linear Law-based Feature Space Transformation (Under Review).  Scientific Reports, .
  * Kurbucz et al. (2023b) Kurbucz, M. T., Pósfai, P., & Jakovác, A. (2023b).  LLT R package.  GitHub, . URL: https://github.com/mtkurbucz/LLT.
  * Kurbucz et al. (2022) Kurbucz, M. T., Pósfay, P., & Jakovác, A. (2022).  Facilitating time series classification by linear law-based feature space transformation.  Scientific Reports, 12, 18026.
  * Li et al. (2019) Li, G., Yan, W., & Wu, Z. (2019).  Discovering shapelets with key points in time series classification.  Expert systems with applications, 132, 76–86.
  * Mahayana et al. (2022) Mahayana, D., Madyaratri, S. A., & Fadhl‘Abbas, M. (2022).  Predicting price movement of the BTCUSDT pair using LightGBM classification modeling for cryptocurrency trading.  In 2022 12th International Conference on System Engineering and Technology (ICSET) (pp. 01–06).  IEEE.
  * Mba & Mwambi (2020) Mba, J. C., & Mwambi, S. (2020).  A Markov-switching COGARCH approach to cryptocurrency portfolio selection and optimization.  Financial Markets and Portfolio Management, 34, 199–214.
  * Mello et al. (2019) Mello, C. E., Carvalho, A. S., Lyra, A., & Pedreira, C. E. (2019).  Time series classification via divergence measures between probability density functions.  Pattern Recognition Letters, 125, 42–48.
  * Nakamoto (2008) Nakamoto, S. (2008).  Bitcoin: A peer-to-peer electronic cash system.  Decentralized business review, (p. 21260).
  * Oza & Tumer (2008) Oza, N. C., & Tumer, K. (2008).  Classifier ensembles: Select real-world applications.  Information fusion, 9, 4–20.
  * Raghu et al. (2019) Raghu, S., Sriraam, N., Temel, Y., Rao, S. V., Hegde, A. S., & Kubben, P. L. (2019).  Performance evaluation of DWT based sigmoid entropy in time and frequency domains for automated detection of epileptic seizures using SVM classifier.  Computers in biology and medicine, 110, 127–143.
  * Takens (1981) Takens, F. (1981).  Dynamical systems and turbulence, eds. Rand, DA & Young, L.-S.  Lecture Notes in Mathematics, 898, 366.
  * Zhou et al. (2023) Zhou, Z., Song, Z., Xiao, H., & Ren, T. (2023).  Multi-source data driven cryptocurrency price movement prediction and portfolio optimization.  Expert Systems with Applications, (p. 119600).

See pages - of supplementary_material.pdf


# Provably Sample Efficient RLHF via Active Preference Optimization

Nirjhar Das  Souradip Chakraborty  Aldo Pacchiano  Sayak Ray Chowdhury

###### Abstract

Reinforcement Learning from Human Feedback (RLHF) is pivotal in aligning Large
Language Models (LLMs) with human preferences. While these aligned generative
models have demonstrated impressive capabilities across various tasks, the
dependence on high-quality human preference data poses a costly bottleneck in
practical implementation of RLHF. Hence better and adaptive strategies for
data collection is needed. To this end, we frame RLHF as a contextual
preference bandit problem with prompts as contexts and show that the naive way
of collecting preference data by choosing prompts uniformly at random leads to
a policy that suffers an $\Omega(1)$ suboptimality gap in rewards. Then we
propose _Active Preference Optimization_ (APO), an algorithm that actively
selects prompts to collect preference data. Under the Bradley-Terry-Luce (BTL)
preference model, APO achieves sample efficiency without compromising on
policy performance. We show that given a sample budget of $T$, the
suboptimality gap of a policy learned via APO scales as $O(1/\sqrt{T})$. Next,
we propose a compute-efficient batch version of APO with minor modification
and evaluate its performance in practice. Experimental evaluations on a human
preference dataset validate APO’s efficacy as a sample-efficient and practical
solution to data collection for RLHF, facilitating alignment of LLMs with
human preferences in a cost-effective and scalable manner.

Active Learning, Preference Bandit, Contextual Bandit

##  1 Introduction

Reinforcement Learning from Human Feedback (RLHF) has proven highly effective
in aligning Large Language Models (LLMs) with human preferences (Christiano et
al., 2017; Ouyang et al., 2022; Glaese et al., 2022). This approach involves
collecting extensive data, each comprising a prompt, a pair of generations,
and a preference indicating which generation is better. Then a reward model is
trained to classify preferred generations, and subsequently, a language model
policy using Proximal Policy Optimization (PPO) (Schulman et al., 2017) is
trained to generate high-reward actions while minimizing divergence from a
reference policy.

Given the practical success, recent theoretical advances have been made in
learning reward functions from pairwise comparisons, studied as contextual
dueling bandits (Saha, 2021; Saha & Krishnamurthy, 2022; Dudík et al., 2015)
and preference-based RL (Pacchiano et al., 2021; Chen et al., 2022; Zhu et
al., 2023). In these settings, the learner doesn’t control the contexts or
states and the aim is to minimize cumulative regret, with optimal rates
achieved in both settings.

However, in the case of aligning LLMs, the learner indeed has control over
both the contexts and actions, i.e., the prompts and generations for which
preference data is to be collected. Currently, most practical implementations
of RLHF picks contexts uniformly at random from a pool of contexts followed by
two actions for that context based on some policy, to collect preference data
on. The success of RLHF hinges on the balance between the quality and quantity
of human preference data (Stiennon et al., 2020; Ouyang et al., 2022).
Excessive low-quality data can degrade performance, while scarce high-quality
data may not enhance it. However, uniform prompt sampling as a simple approach
has proven effective for LLMs so far.

Restricting ourselves to the contextual preference bandit setting, one is then
bound to ask whether uniformly sampling contexts followed by observing the
preference between two chosen actions is a good enough strategy. Do we really
need sophisticated and potentially more involved methods to deliver better
model alignment? To this end, we design a contextual preference bandit
instance on which we show that a learner who only samples contexts uniformly
suffers a constant suboptimality gap (gap between the reward of the best
action and that of the policy) with high probability. To the best of our
knowledge, our work is the first to provide provable lower bounds for learners
that sample contexts uniformly at random to collect preference data.

This immediately necessitates algorithms that can make choices of contexts
(and two actions) adaptively during the reward learning phase. This scenario
falls under Active Learning, where the learner not only performs tasks but
also decides which tasks to perform during the course of training. The goal is
to optimize performance at test time when the learner has no control on the
tasks’ arrivals. In the contextual bandit setting, Char et al. (2019) actively
query contexts and actions for optimal policy learning. Li et al. (2022)
explore optimal policy identification in the RL setting when the agent can
choose the state and action to query via a simulator.

However, we deal with a contextual _preference_ bandit setting which cannot be
reduced to a contextual bandit by virtue of the fact that comparisons between
two actions are valid only if they come from the same context. Moreover, the
goal of the learner is now to actively select contexts as well as a pair of
actions for that context to collect preference data on this triplet. The
learner should be sample efficient so that with more data being collected, the
suboptimality gap of the policy learnt from the collected data should go down.

A recent work (Mehta et al., 2023) proposes to tackle this problem by
measuring performance of the learned policy against the _Borda_ winner policy,
an action that wins in expectation over a randomly chosen action. They resort
to sampling one action randomly, while adaptively sampling the other. Although
they guarantee an $O(1/\sqrt{T})$ suboptimality gap after $T$ rounds for the
trained policy, choosing a random action at every round can result in sample
inefficiency in practical scenarios. Furthermore, Mehta et al. (2023) assume
both the reward function and the _Borda_ score (average probability of an
action being a _Borda_ winner) are linear functions of a common feature map.
This doesn’t hold in general for the popular Bradley-Terry-Luce (BTL)
preference model (Bradley & Terry, 1952; Luce, 2012). Their guarantee also has
a linear dependence on the Lipschitz constant of rewards with respect to the
_Borda_ score, which could be exponential for the BTL model.

We now list the main contributions of our work:

1\. Lower Bound: We show that the naive way of collecting preference data by
choosing contexts uniformly at random can lead to wastage of samples as the
learned policy can suffer $\Omega(1)$ suboptimality gap with high probability.
To the best of our knowledge, this is the first provable negative result for
uniformly sampling prompts.

2\. Adaptive Algorithm: We propose _Active Preference Optimization_ (APO), an
active contextual preference bandit algorithm that adaptively selects a
context and two actions every time to collect preference data. Under the BTL
preference model, the suboptimality gap of APO scales as $O(1/\sqrt{T})$ where
$T$ is the given sample budget. Moreover, in contrast to Mehta et al. (2023),
APO chooses both the actions adaptively given a context, thus leading to more
meaningful comparisons in practical settings.

3\. Improved Guarantees: We improve the linear dependence of the suboptimality
guarantee of Mehta et al. (2023) on $\kappa$, to $\sqrt{\kappa}$ while
removing their restrictive assumptions. Here, $\kappa$ is a problem-dependent
non-linearity factor which can be exponential in problem parameters.
Additionally, we present an analogue of APO under general function
approximation that attains a similar guarantee while generalizing to
preference models other than BTL.

4\. Experiments: We propose a batch algorithm APO-RLHF with a slight
modification of the original algorithm so that it is also computationally more
efficient. We experiment with GPT-2 (Radford et al., 2019) on IMDB sentiment
dataset (Maas et al., 2011) and demonstrate significant improvement over
uniform sampling in both reward learning step and alignment step in the RLHF
pipeline. We believe that our work contributes towards a sample-efficient and
practical solution to preference data collection for RLHF.

##  2 Background and Problem Setup

We have a set of contexts $\mathcal{X}$ and a set of possible actions per
context $\mathcal{A}$. To learn using preference feedback, the agent selects a
tuple $(x,a,a^{\prime})$ to present to a human labeller who then reveals a
binary preference $y$ which takes value $1$ if $a$ wins over $a^{\prime}$ and
$0$ otherwise. We assume that $y$ is sampled from a Bernoulli distribution
conditioned on $(x,a,a^{\prime})$, i.e.,

$\displaystyle\mathbb{P}_{\theta^{*}}\\!\\!\left[y\\!=\\!1|x,a,a^{\prime}\\!\right]\\!=\\!\frac{\exp(r_{\theta^{*}}(x,a))}{\exp(r_{\theta^{*}}(x,a))\\!+\\!\exp(r_{\theta^{*}}(x,a^{\prime}))}.$

Here $r_{\theta^{*}}$ is a latent reward model parameterized by an unknown
parameter $\theta^{*}$. This reward model is often called Bradley-Terry-Luce
(BTL) model (Bradley & Terry, 1952; Luce, 2012). The goal of the agent is to
first learn the reward model $r_{\theta^{*}}$ over $T$ rounds of sequential
interaction with the labeller and then employ this reward model to learn a
policy $\pi:\mathcal{X}\to\mathcal{A}$ (i.e. a rule for selecting an action
$a$ given a context $x$), which will eventually fetch high latent rewards
$r^{*}(x,a)$. The agent collects a preference dataset
$\mathcal{D}=(x_{s},a_{s},a^{\prime}_{s},y_{s})_{s=1}^{T}$ of $T$ samples in
the process.

In this work, we consider a linear reward model
$r_{\theta^{*}}(x,a)=\phi(x,a)^{\top}\theta^{*}$, where
$\phi:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{d}$ is some known and fixed
feature map. (In section 6 we generalize this set-up to general function
approximation removing the need for such explicit reward models.) For
instance, such a $\phi$ can be constructed by removing the last layer of a
pre-trained language model, and in that case, $\theta^{*}$ correspond to the
weights of the last layer. With this model, one can equivalently write the
probability of sampling $y_{s}=1$ given $(x_{s},a_{s},a^{\prime}_{s})$ as

$\displaystyle\\!\mathbb{P}_{\theta^{*}}\\!\\!\left[y_{s}\\!=\\!1|x_{s},a_{s},a^{\prime}_{s}\right]\\!=\\!\mu\big{(}\phi(x_{s},a_{s})^{\top}\theta^{*}\\!-\\!\phi(x_{s},a^{\prime}_{s})^{\top}\theta^{*}\\!\big{)},$

where $\mu(w)\\!=\\!\frac{1}{1+e^{-w}}$ is the sigmoid function. We let
$z_{s}=\phi(x_{s},a_{s})\\!-\\!\phi(x_{s},a^{\prime}_{s})$ denote the
differential feature of actions $a_{s}$ and $a^{\prime}_{s}$ at state $x_{s}$.
This lets us denote, for any $\theta\in\mathbb{R}^{d}$, the predicted
probabilities of a label $y_{s}=1$ given $(x_{s},a_{s},a^{\prime}_{s})$ as (we
omit dependence on $\theta$ for brevity)

$\displaystyle\mathbb{P}_{\theta}\left[y_{s}\\!=\\!1|x_{s},a_{s},a^{\prime}_{s}\right]\\!=\\!\mu(z_{s}^{\top}\theta)~{}.$

Note that this problem cannot be reduced to a logistic bandit instance
(Abeille et al., 2021; Faury et al., 2022) as comparisons only between actions
of the same contexts are valid, i.e., actions $a$ and $a^{\prime}$ can only be
compared via $\phi(x,a)$ and $\phi(x,a^{\prime})$ for the same $x$.

We make the following assumption which is standard in preference-based
learning literature (Shah et al., 2015; Zhu et al., 2023).

######  Assumption 2.1 (Boundedness).

(a) $\theta^{*}$ lies in the set
$\Theta=\\{\theta\in\mathbb{R}^{d}|\left\langle\mathbf{1},\theta\right\rangle=0,||\theta||\leq
S\\}$. The condition $\left\langle\mathbf{1},\theta\right\rangle=0$ ensures
identifiability of $\theta^{*}$. (b) Features are bounded, i.e.,
$||\phi(x,a)||\leq 1$, $\forall\ (x,a)\in\mathcal{X}\times\mathcal{A}$.

Now, we define a quantity that captures the learning complexity under the
logistic (BTL) preference model:

$\displaystyle\kappa=\max_{x\in\mathcal{X},a,a^{\prime}\in\mathcal{A}}\max_{\theta\in\Theta}\frac{1}{\dot{\mu}(\phi(x,a)^{\top}\theta\\!-\\!\phi(x,a^{\prime})^{\top}\theta)}~{}.$

$\kappa$ is a problem-specific constant and it specifies difficulty in
learning via the worst-case non-linearity in preference feedback. It can be
exponential in the parameter norm $S$, and much of logistic bandit literature
(Abeille et al., 2021; Faury et al., 2022; Lee et al., 2023) deals with
removing the linear dependence of regret on $\kappa$.

Now, we present the process of parameter estimation in the BTL model via
maximum likelihood estimation. Maximum Likelihood Estimation. At time $t$,
given the preference dataset
$\\{(x_{s},a_{s},a^{\prime}_{s},y_{s})\\}_{s=1}^{t-1}$, the maximum likelihood
estimate (MLE) of $\theta^{*}$ constrained to the set $\Theta$ is

$\displaystyle\hat{\theta}_{t}=\mathop{\mathrm{argmin}}\nolimits_{\theta\in\Theta}\mathcal{L}_{t}(\theta)~{}.$
(1)

Here the log-loss $\mathcal{L}_{t}(\theta)$ is computed using observed
preferences $y_{s}$ and predicted probabilities $\mu(z_{s}^{\top}\theta)$ as

$\displaystyle\\!\\!\\!\mathcal{L}_{t}(\theta)\\!=\\!-\\!\\!\sum_{s=1}^{t-1}\\!y_{s}\log(\mu(z_{s}^{\top}\\!\theta)\\!)\\!+\\!(1\\!-\\!y_{s})\\!\log(1\\!-\\!\mu(z_{s}^{\top}\\!\theta)\\!).$
(2)

The above optimization involves both convex objective and constraint, hence
can be solved using standard algorithms (Hazan et al., 2016; Bubeck et al.,
2015).

Performance measure. Our goal is to learn a policy over the collected data
$\mathcal{D}$, which has high rewards or, equivalently, low suboptimality.
Formally, the suboptimality gap of a learned policy $\pi_{T}$ after collecting
$T$ samples by an algorithm of choice is defined as follows:

$\\!\\!R(T)\\!=\\!\max\nolimits_{x\in\mathcal{X}}\max\nolimits_{a\in\mathcal{A}}r^{*}(x,a)-r^{*}(x,\pi_{T}(x))~{}.$
(3)

Here, our policy competes with the _Condorcet_ winner of a context—an action
that is better than all other actions. The suboptimality gap is the worst
possible difference in latent rewards over the set of contexts. Mehta et al.
(2023) uses a similar measure of performance but they compete against the
_Borda_ winner, which is weaker than ours111Indeed, a _Condorcet_ winner is
also the _Borda_ winner but not conversely..

Notations. Throughout the paper, we will denote universal constants with $C$
and express our guarantees in terms of $C$. Further, for a vector $a$ and a
matrix $M$, we will use $\lVert a\rVert_{M}$ to denote $\sqrt{a^{\top}Ma}$.
For two matrices $A$ and $B$, $B\preccurlyeq A$ or $A\succcurlyeq B$ will
denote that $A-B$ is a positive semi-definite matrix. Lastly, we will use
$\tilde{O}(\cdot)$ to denote order notation but hiding log factors.

##  3 Is Uniform Sampling Good Enough?

In this section we illustrate the pitfall of a learner who samples contexts
uniformly for learning. We first characterize such a learner in the contextual
preference bandit setting.

######  Definition 3.1 (Uniform Learner).

Suppose an algorithm Alg first samples contexts uniformly at random from a
given set of contexts $\mathcal{X}$ and then picks two actions of its choice
from the action set $\mathcal{A}$. The algorithm then queries the true
preference model parameterized by $\theta^{*}$ to observe the stochastic
binary preference outcome. After $T$ rounds, the algorithm solves an MLE over
the collected data. With the ML estimate, the algorithm then learns a greedy
policy. We call such an algorithm Alg a Uniform Learner.

Now we state the following theorem that shows that a _Uniform Learner_ can
suffer constant suboptimality gap that does not go down with the number of
samples.

######  Theorem 3.2.

There exists a contextual preference bandit instance
$(\mathcal{X},\mathcal{A},\theta^{*})$ and a choice of $T$ for which the
policy learnt by a Uniform Learner Alg suffers $\Omega(1)$ suboptimality gap
with high probability.

###### Proof.

Let $\lvert\mathcal{X}\rvert=N$ and assume $T\ll N$. Indeed, this is the
interesting case because otherwise, if budget of samples $T>N$, then one can
just collect data for every context.

We divide $\mathcal{X}$ into two disjoint subsets: a _good_ set
$\mathcal{X}_{g}$ and a _bad_ set $\mathcal{X}_{b}$, where w.l.o.g. we assume
$\lvert\mathcal{X}_{b}\rvert=1$. Hereon, we will denote the _bad_ context by
$b$. Let $\mathcal{A}=\\{a,a^{\prime}\\}$ for all contexts, and let $a$ be the
action with higher reward. Let
$\phi:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}^{2}$ be a feature map
and $z_{x}=\phi(x,a)-\phi(x,a^{\prime})$ be the the feature difference vector
for the context $x$. We now specify a problem instance:

$\displaystyle\forall\ x\in\mathcal{X}_{g}:\ $ $\displaystyle
z_{x}=\begin{bmatrix}1&0\end{bmatrix}^{\top};\,\,z_{b}=\begin{bmatrix}-\frac{1}{2}&\frac{\sqrt{3}}{2}\end{bmatrix}^{\top}~{},$
$\displaystyle\theta^{*}$
$\displaystyle=\alpha\begin{bmatrix}\frac{1}{2}&\frac{\sqrt{3}}{2}\end{bmatrix}^{\top},\
\alpha>0~{}.$

We will specify $\alpha$ later, but note that
$\lVert\theta^{*}\rVert_{2}=\alpha$. From this construction (see fig. 1), it
is clear that both for _good_ and _bad_ sets,
$z_{x}^{\top}\theta^{*}=\alpha/2>0$, which implies that indeed action $a$ has
higher reward than $a^{\prime}$.

Let $\mathcal{E}_{1}$ be the event that the collection of $T$ contexts
constructed by sampling uniformly at random from $\mathcal{X}$ contains
contexts only from $\mathcal{X}_{g}$. Let $\mathcal{E}_{2}$ be the event that
all observed comparison feedbacks $y_{1},\ldots y_{T}$ are equal to $1$. Under
uniform sampling, for a random context $X$,
$\mathbb{P}[X\in\mathcal{X}_{g}]=1-1/N$. Since the sequence
$\\{x_{i}\\}_{i=1}^{T}$ contains i.i.d samples, and similarly for
$\\{y_{i}\\}_{i=1}^{T}$, it can be easily calculated that

$\displaystyle\mathbb{P}[\mathcal{E}_{1}]=\left(1-\frac{1}{N}\right)^{T}\\!\\!,$
$\displaystyle\ \
\mathbb{P}[\mathcal{E}_{2}|\mathcal{E}_{1}]=\prod_{i=1}^{T}\mu\left(\frac{\alpha}{2}\right)=\mu\left(\frac{\alpha}{2}\right)^{T}$

Under the event $\mathcal{E}_{1}\cap\mathcal{E}_{2}$, the maximum likelihood
estimate $\hat{\theta}$ constrained to the same norm as $\theta^{*}$ is given
by

$\displaystyle\hat{\theta}=\mathop{\mathrm{argmin}}_{\theta\in\mathbb{R}^{2}:\lVert\theta\rVert_{2}\leq\alpha}\sum\nolimits_{i=1}^{T}\log\left(1+e^{-\alpha\theta_{1}}\right)$
($\theta\equiv\begin{bmatrix}\theta_{1}\\\ \theta_{2}\end{bmatrix}$)

It is easy to verify that
$\hat{\theta}=\begin{bmatrix}\alpha&0\end{bmatrix}^{\top}$. For
$x\in\mathcal{X}_{g}$, the predicted reward difference between actions $a$ and
$a^{\prime}$ is $z_{x}^{\top}\hat{\theta}=\alpha>0$. Thus, $\hat{\theta}$
predicts correctly for $x\in\mathcal{X}_{g}$. However, for context $b$, the
reward difference is $z_{b}^{\top}{\hat{\theta}}=-\frac{\alpha}{2}<0$. Thus
$\hat{\theta}$ wrongly predicts $a^{\prime}$ as the better action for the bad
context $b$ incurring a constant sub-optimality gap:

$\displaystyle
R(T,b)=(\phi(b,a)-\phi(b,a^{\prime}))^{\top}\theta^{*}=\alpha/2=\Omega(1).$

Finally, it remains to show that the event
$\mathcal{E}_{1}\cap\mathcal{E}_{2}$ happens with high probability. We choose
$\alpha=2\log(N-1)$ which yields $\mu(\alpha/2)=1-(1/N)$. Hence, we get

$\displaystyle\mathbb{P}[\mathcal{E}_{1}\cap\mathcal{E}_{2}]=\mathbb{P}[\mathcal{E}_{2}|\mathcal{E}_{1}]\mathbb{P}[\mathcal{E}_{1}]=\left(1-\frac{1}{N}\right)^{2T}\geq
1-\frac{2T}{N}~{}$

The last step uses $T\ll N$, which completes the proof. ∎

Our lower bound highlights the need for algorithms that can make better use of
the sample budget $T$. In the next section, we propose an algorithm which
actively selects contexts to ensure that suboptimality gap goes down as
${1}/{\sqrt{T}}$.

$z_{b}$$\theta^{*}$$X$$\hat{\theta}$$z_{g}$$Y$$X^{\prime}$

Figure 1: A pictorial representation of the lower bound instance. $z_{g}$
represents the feature difference vectors for the _good_ contexts and $z_{b}$
represents the feature difference vector for the _bad_ context. $\theta^{*}$
and $\hat{\theta}$ are the true and the learnt parameters respectively.

##  4 Our Approach

First we will define two matrices that characterize the confidence ellipsoid
around the unknown reward parameter after $t-1$ steps of data collection.
Recall the feature difference
$z_{s}=\phi(x_{s},a_{s})-\phi(x_{s},a^{\prime}_{s})$ where
$(x_{s},a_{s},a^{\prime}_{s})$ is the triplet queried at time $s$. With this,
we define:

$\begin{split}V_{t}&=\sum\nolimits_{s=1}^{t-1}z_{s}z_{s}^{\top}+\kappa\lambda\mathbf{I}_{d}~{},\\\
H_{t}(\theta)&\\!=\\!\nabla^{2}\\!\mathcal{L}_{t}(\theta)\\!+\\!\lambda\mathbf{I}_{d}\\!=\\!\\!\sum\nolimits_{s=1}^{t-1}\\!\dot{\mu}(z_{s}^{\top}\theta)z_{s}z_{s}^{\top}\\!+\\!\lambda\mathbf{I}_{d}~{}.\end{split}$
(4)

Here $V_{t}$ is a regularized sample covariance matrix of feature differences,
while $H_{t}(\theta)$ scales each rank-one component inside the sum by its
variance given that the parameter is $\theta$. A key relation between these
two matrices is that $H_{t}(\theta)\succcurlyeq V_{t}/\kappa$. We set
$\lambda=1/4S^{2}(2+2S)^{2}$ for providing guarantees but can be treated as a
tuning parameter. Now we are ready to present the algorithm for active context
selection in the BTL preference model.

###  4.1 Algorithm: Active Preference Optimization

At each round $t$, our algorithm proceeds by computing the MLE estimate
$\hat{\theta}_{t}$ based on the data obtained in the past $t-1$ steps (see (1)
and (2)). Based on $\hat{\theta}_{t}$, our goal is to maximize exploration. To
do this, for a context $x\in\mathcal{X}$, we compute the uncertainty for each
$(a,a^{\prime})$ available for that context and choose the one which maximizes
this:

$\begin{split}(a_{t}(x),a^{\prime}_{t}(x))&=\mathop{\mathrm{argmax}}_{(a,a^{\prime})\in\mathcal{A}\times\mathcal{A}}b_{t}(x,a,a^{\prime}),\,\,\text{where}\\\
b_{t}(x,a,a^{\prime})&=\lVert\phi(x,a)-\phi(x,a^{\prime})\rVert_{H_{t}^{-1}(\hat{\theta}_{t})}~{}.\end{split}$
(5)

Intuitively, $H_{t}(\hat{\theta})$ describes a confidence ellipsoid around
$\theta^{*}$ which keeps shrinking along whichever direction (in
$\mathbb{R}^{d}$) we decide to explore. Thus, for a given context $x$, playing
$(x,a_{t}(x),a^{\prime}_{t}(x))$ described above maximally reduces the
uncertainty among all other possible action duels.

However, our algorithm picks not only the action pair that minimizes
uncertainty, but also the context that decreases it the most. Thus, we define

$\displaystyle
x_{t}=\mathop{\mathrm{argmax}}\nolimits_{x\in\mathcal{X}}b_{t}(x,a_{t}(x),a^{\prime}_{t}(x))$
(6)

This is the crucial step in our algorithm that ensures that the reward
uncertainty over all contexts decreases at a fast rate which in turn ensures
low suboptimality gap of our policy.

After running this procedure for $T$ time steps, we define
$\theta_{T}=\frac{1}{T}\sum_{s=1}^{T}\hat{\theta}_{t}$ as the average of all
the past parameter estimates. Our final policy $\pi_{T}$ for any context
$x\in\mathcal{X}$ is to play the action that maximizes the reward
parameterized by $\theta_{T}$. In other words, for any $x\in\mathcal{X}$, we
choose the policy

$\displaystyle\pi_{T}(x)=\mathop{\mathrm{argmax}}\nolimits_{a\in\mathcal{A}}\,\phi(x,a)^{\top}\theta_{T}~{}.$
(7)

The pseudocode is given in algorithm 1.

Algorithm 1 APO: Active Preference Optimization

0: Context set $\mathcal{X}$, action set $\mathcal{A}=[K]$, feature map
$\phi:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$, regularization
$\lambda=1/4S^{2}(2+2S)^{2}$, and failure level $\delta\in(0,1)$

1: Initialize $\hat{\theta}_{1}=0$

2: for $t=1,\dots,T$ do

3: Choose the triplet $(x_{t},a_{t},a^{\prime}_{t})$ using (5) and (6).

4: Observe preference feedback
$y_{t}\\!\sim\\!\texttt{Ber}\big{(}\mu(z_{t}^{\top}\theta^{*})\big{)}$, where
$z_{t}=\phi(x_{t},a_{t})-\phi(x_{t},a^{\prime}_{t})$.

5: Compute reward estimate $\hat{\theta}_{t+1}$ using (1) that minimizes the
constrained log-loss (2).

6: Compute the (scaled) design matrix $H_{t+1}(\hat{\theta}_{t+1})$ using (4).

7: end for

8: Compute final policy $\pi_{T}(x)$ using (7)

###  4.2 Theoretical Guarantee

First, we present a key lemma that quantifies the error in estimating the
parameter $\theta^{*}$. This lemma is obtained by extending results from (Lee
et al., 2023) and using a novel inequality derived from the self-concordance
property of the sigmoid function ($\lvert\ddot{\mu}\rvert\leq\dot{\mu}$).
Detailed version of the lemma and its proof is deferred to appendix A.

######  Lemma 4.1 (Confidence Set).

Let $\delta\in(0,1]$. Then, under Assumption 2.1, with probability at least
$1-\delta$, we have

$\displaystyle\lVert\theta^{*}\\!-\\!\hat{\theta}_{t}\rVert_{H_{t}(\hat{\theta}_{t})}\\!\leq\\!CS^{\nicefrac{{1}}{{2}}}\gamma_{t}(\delta)~{},$

where
$\gamma_{t}(\delta)=CS\sqrt{\left(d\log\frac{St}{d}+\log\frac{t}{\delta}\right)}$
for some $C>0$.

Now, we present the guarantee that our algorithm enjoys.

######  Theorem 4.2 (Sub-optimality gap).

Let $\delta\in(0,1)$. Under Assumption 2.1, the suboptimality gap $R(T)$ of
our policy $\pi_{T}$ after running APO (Algorithm 1) for $T$ steps is upper
bounded with probability at least $1-\delta$ as

$\displaystyle R(T)\leq
C\gamma_{T}(\delta)\sqrt{S\log\Big{(}1+\frac{T}{\lambda\kappa
d}\Big{)}\frac{\kappa d}{T}}~{}.$

Comparison with Prior work. Plugging in the value of $\gamma_{T}(\delta)$ in
the above bound, we get a sub-optimility gap of
$\widetilde{O}(d\sqrt{\kappa/T})$ with high probability. We compare this with
the $\widetilde{O}(d\kappa\sqrt{T})$ cumulative regret bound of Saha (2021) in
dueling bandit setting. We get $\sqrt{\kappa}$ factor improvement thanks to a
tighter confidence set (Lemma 4.1), which we obtain by crucially using self-
concordance of sigmoid functions.

One might note from the logistic bandit literature (Abeille et al., 2021;
Faury et al., 2022; Lee et al., 2023) that state-of-the-art regret guarantee
is $\kappa$-independent (dependence is only in lower order term). We believe
that our analysis is tight in $\kappa$ because our sub-optimality gap
guarantee is over real-valued rewards ($\phi(x,a)^{\top}\theta^{*}$) instead
of their sigmoid rewards $\mu(\phi(x,a)^{\top}\theta^{*})$ (mean of the
Bernoulli preferences $y$), making the $\sqrt{\kappa}$ dependence unavoidable
for our case.

Proof Sketch. The proof proceeds by first upper bounding the suboptimality gap
of every context with the estimation error of the sub-optimality gap for that
context. Then we use Lemma 4.1 to bound the error in gap estimation with the
error in the parameter estimation times an arm-dependent quantity.
Specifically, for context $x\in\mathcal{X}$, let
$z_{T}=\phi(x,a^{*}(x))-\phi(x,\pi_{T}(x))$, where $a^{*}(x)$ is the optimal
action for context $x$. Then, from (3), the sub-optimality gap at context $x$
is

$\displaystyle R(T,x)\\!=\\!z_{T}^{\top}\theta^{*}$
$\displaystyle\\!\leq\\!z_{T}^{\top}\theta^{*}\\!-\\!z_{T}^{\top}\theta_{T}\\!=\\!\frac{1}{T}\\!\sum\nolimits_{t=1}^{T}\\!z_{T}^{\top}\left(\theta^{*}\\!-\\!\hat{\theta}_{t}\right)\
$ $\displaystyle\leq\frac{1}{T}\\!\sum\nolimits_{t=1}^{T}\\!\lVert
z_{T}\rVert_{H_{t}(\hat{\theta}_{t})^{-1}}\lVert\theta^{*}\\!-\\!\hat{\theta}_{t}\rVert_{H_{t}(\hat{\theta}_{t})}~{}.$

Here, the first inequality is due to the fact that
$\phi(x,\pi_{T}(x))^{\top}\theta_{T}\geq\phi(x,a^{*}(x))^{\top}\theta_{T}$,
which follows from definition of $\pi_{T}$, and so $z_{T}^{\top}\theta_{T}\leq
0$. The last inequality is by Cauchy-Schwarz. Now, we can apply Lemma 4.1 to
upper bound
$\lVert\theta^{*}-\hat{\theta}_{t}\rVert_{H_{t}(\hat{\theta}_{t})}$ by
$CS^{1/2}\gamma_{t}(\delta)$. Next, note that by the design of our algorithm,
$\lVert z_{T}\rVert_{H_{t}(\hat{\theta}_{t})^{-1}}\leq\lVert
z_{t}\rVert_{H_{t}(\hat{\theta}_{t})^{-1}}$ which we again upper bound by
$\sqrt{\kappa}\lVert z_{t}\rVert_{V_{t}^{-1}}$ using the fact that
$H_{t}(\hat{\theta})\succcurlyeq(\nicefrac{{1}}{{\kappa}})V_{t}$. Finally,
applying the Elliptic Potential Lemma (Lemma C.2) finishes the proof. The
proof is presented in details in appendix A.

####  4.2.1 Comparison with Mehta et al. (2023)

We revisit assumptions and results in Mehta et al. (2023) to highlight major
differences. First, they consider the Borda scores
$g^{*}(x,a)=\mathbb{E}_{a^{\prime}\sim\texttt{Unif}(\mathcal{A}(x))}[\mu(r^{*}(x,a)-r^{*}(x,a^{\prime}))]$,
which is the probability of action $a$ winning at context $x$ over any other
random action. They assume both reward and Borda functions lie in the same
Hilbert Space $\mathcal{H}$, i.e.
$\exists\,\theta^{*},\beta^{*}\in\mathcal{H}$ and a feature map
$\phi:\mathcal{X}\times\mathcal{A}\to\mathcal{H}$ such that
$r^{*}(x,a)=\left\langle\theta^{*},\phi(x,a)\right\rangle_{\mathcal{H}}$ and
$g^{*}(x,a)=\left\langle\beta^{*},\phi(x,a)\right\rangle_{\mathcal{H}}$. Since
$g^{*}$ is a non-linear function of $\phi(x,a)$, this assumption doesn’t hold
for BTL preference model in general.

The assumption holds trivially when each $\phi(x,a)$ is the one-hot vector
$\mathbf{e}_{x,a}$. However, it requires $\mathcal{H}$ to be
$\lvert\mathcal{X}\rvert\cdot\lvert\mathcal{A}\rvert$ dimensional Euclidean
space. This would then significantly weaken their suboptimality guarantee
which scales linearly with dimension. We remove this assumption but provide
the same guarantee in terms of $d$. We achieve this by exploiting the problem
structure, especially the properties of the sigmoid function.

Next, Mehta et al. (2023) assumes that the optimal action
$a^{*}_{x}\\!=\\!\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\phi(x,a)^{\top}\theta^{*}$
satisfies for some $L\\!>\\!0$:

$\displaystyle\langle{\phi(x,a^{*}_{x})\\!-\\!\phi(x,a)},{\theta^{*}}\rangle\\!\leq\\!L\left(g^{*}(x,a^{*}_{x})\\!-\\!g^{*}(x,a)\right)$
(8)

From definition, $g^{*}$ is in the same non-linear function space as $\mu$.
Denote by $\nu$ the Logit function: $\nu(z)=\log(z/(1-z))$. We know that
$\nu(\mu(y))=y$. With this, the assumption stated in (8) roughly translates to
$\lvert\nu(z)-\nu(z^{\prime})\rvert\leq L\lvert z-z^{\prime}\rvert$.

Thus, $L$ is a global upper bound on $\dot{\nu}(z)$ for all $z$. A minor
calculation will show that $\dot{\nu}(z)=1/\dot{\mu}(y)$ where $z=\mu(y)$.
Hence $L$ is of the order of $\kappa$. The suboptimality gap of Mehta et al.
(2023) (Theorem 1) scales linearly with $L$ (or $\kappa$). Our guarantee is
therefore asymptotically tighter as it only scales as $\sqrt{\kappa}$. Note
that the constant $\kappa$ can be exponential in problem parameter $S$.

Finally, one major difference with Mehta et al. (2023) is that we choose both
actions by maximizing the exploration bonus, while they choose the second
action randomly. This approach might be wasteful in terms of samples as the
choice of second action is equally crucial in preference models e.g., if the
second answer is generated randomly for a given prompt, then always the first
answer will be preferred, although such a data does not reveal much.

Figure 2: Left: the evaluation accuracy of the reward model comparing our
algorithm (APO) with random sampling baseline by varying the amount of data
used (in percentage) for the reward model training. It is evident that eval
accuracy of APO even with 5% active samples is higher than that achieved by
random baseline with 40% samples illustration the sub-optimality gap as shown
in Theorem 3.2. Middle: sentiment score distribution of the PPO policy trained
on the reward model learned with APO (using only 10% samples) and random
baseline’s highest accuracy reward model (40% sample). Generations by APO-
trained reward is more shifted towards positive showing successful reward
learning. Right: APO outperforms random baseline by 60-40 winrate
demonstrating the efficiency of our active preference optimization procedure.

##  5 Experiments

In this Section, we first give a batch version of the online algorithm and the
details of the performed experiments. The batch version strongly follows the
framework of APO (algorithm 1) with slight changes adapted for computationally
efficient implementation for large scale experiments.

###  5.1 APO-RLHF

Algorithm 2 APO-RLHF: Active Preference Optimization for RLHF

0: Dataset $\mathcal{D}=\\{(x_{i},a_{i},a^{\prime}_{i})\\}_{i=1}^{N}$,
$\lambda>0$, sample budget $T$, encoder $\phi$, batch size $B$, SFT policy
$\pi_{\text{SFT}}$

1: Initialize $V=\lambda I$

2: for $t=1\ldots\lfloor T/B\rfloor$ do

3: To every triplet $(x,a,a^{\prime})\in\mathcal{D}$, assign
$\texttt{score}(x,a,a^{\prime})=\lVert\phi(x,a)-\phi(x,a^{\prime})\rVert_{V^{-1}}$

4: $\mathcal{E}=$ Top $B$ items from $\mathcal{D}$ by score.

5: for $(x,a,a^{\prime})\in\mathcal{E}$ do

6: Observe feedback $y$. Let $z=\phi(x,a)-\phi(x,a^{\prime})$

7: Update $V\leftarrow V+zz^{\intercal}$

8: end for

9: Update $\hat{\theta}\leftarrow\texttt{GRADIENT-
STEP}(\hat{\theta},\mathcal{E},\\{y_{i}\\}_{i=1}^{B})$

10: end for

11: Policy $\pi_{T}\leftarrow\texttt{PPO}(\pi_{\text{SFT}},\hat{\theta})$

The batch version of the algorithm called APO-RLHF at each round computes the
score of each triplet $(x,a,a^{\prime})$.222The feature difference data can
pre-computed and stored in memory to avoid multiple LLM inferences of the same
sentences. The computation (Step 3) is very similar to Step 3 of Algorithm 1
except that here we compute the norm w.r.t $V^{-1}$ instead of
$H(\hat{\theta})^{-1}$. A close look at the proof of Theorem 4.2 (see Appendix
A) will reveal that changing the matrix does not alter the theoretical
guarantees. We do this here because it is computationally more efficient to
update $V$ compared to $H(\theta)$. Moreover, data is now collected in batches
and those triplets are queried in a batch that have the highest score to
maximize exploration. At the end of every batch, we update the parameter
$\hat{\theta}$ via GRADIENT-STEP which is a blackbox gradient based
optimization algorithm that performs gradient steps of $\hat{\theta}$ by
minimizing the log-loss (2) over the dataset specified by $\mathcal{E}$ and
$\\{y_{i}\\}_{i=1}^{B}$. Finally, the aligned policy $\pi_{T}$ is learned via
PPO which inputs the SFT policy $\pi_{\text{SFT}}$ and the learnt reward model
$\hat{\theta}$ and aligns $\pi_{\text{SFT}}$ via PPO (Schulman et al., 2017).

###  5.2 Controlled Sentiment Generation

Experiment Design & Evaluation: In our experiment on controlled sentiment
generation, we consider a user group that prefers positive sentiment
completions for a prompt. Using the IMDb dataset as a basis for our inputs
(Maas et al., 2011), the goal for the optimal policy is to produce responses
$y$ that exhibit positive sentiment, catering to the user group’s preferences
for a given prompt $x$. For a controlled evaluation, we generated a set of
preference pairs utilizing a pre-trained sentiment classifier where
$p(\text{positive}\mid x,y_{w})>p(\text{positive}\mid x,y_{l})$ for the
evaluation. We implement the 3 phases of RLHF pipeline ((Christiano et al.,
2017; Ouyang et al., 2022)) - 1. Supervised Fine-tuning 2. Reward Modelling
Phase 3. RL Fine-tuning with PPO. For the SFT policy, we fine-tune GPT-2
(Radford et al., 2019) until convergence on reviews from the train split of
the IMDb dataset and use this GPT-2 backbone for both the reward model and PPO
(Schulman et al., 2017) training. The generations are evaluated against the
ground truth reward $r^{*}$ for positive sentiment, provided by the pre-
trained sentiment classifier (similar to (Rafailov et al., 2023)). To
demonstrate the performance of APO-RLHF (algorithm 2) against random selection
baselines, we use the feature representation $\phi(x,y)$ given a prompt $x$
and response $y$ using the GPT-2 SFT backbone. We estimate the score
$b_{t}(x,y_{\texttt{chosen}},y_{\texttt{rejected}})$ for each
$(x,y_{\texttt{chosen}},y_{\texttt{rejected}})$ in our dataset $\mathcal{D}$
using score defined in step 3 and select the top-$B$ samples (step 4) to
update the reward model. We repeat this process $K$ times and compare the same
against random baseline (where we select the $B$ samples randomly) for
different values of $BK$. Note that our total sample budget is now $T=BK$.
Finally, we train PPO (Schulman et al., 2017) with the learned reward model
and evaluate the responses against the ground truth reward $r^{*}$ for
positive sentiment. Figure 2 shows the results of the experiment. It is clear
that evaluation accuracy of the reward model learned by APO-RLHF is much
higher than the one learned via random selection baseline even when APO-RLHF’s
sample budget is only $5\%$ of the data and random baseline’s $40\%$
illustrating the suboptimality gap as shown in Theorem 3.2. Next, we compare
the performance of the aligned models trained via PPO using the respective
reward models. For APO-RLHF, we use the reward model trained on a sample
budget of $10\%$ while for random baseline it is the highest accuracy reward
model (corresponding to $40\%$ sample). From figure 2 it is evident that APO-
RLHF outperforms the random baseline by a 60-40 win rate demonstrating the
efficiency of our Active Preference Optimization procedure.

##  6 Generalization to Function Approximation

In this section, we remove the assumption of BTL preference model
characterized by a linear parameter $\theta$. Instead, we assume that we have
access to a function class

$\mathcal{F}\\!=\\!\\{f:\mathcal{X}\\!\times\\!\mathcal{A}\\!\times\\!\mathcal{A}\rightarrow[0,1]:f(x,a,a^{\prime})\\!+\\!f(x,a^{\prime},a)\\!=\\!1\\},$

where $f(x,a,a^{\prime})$ denotes the probability that the arm $a$ wins over
arm $a^{\prime}$ given context $x$ when the preference function is $f$, i.e.,
$f(x,a,a^{\prime})=\mathbb{P}[a\succcurlyeq a^{\prime}|x,f]$ where
$a\succcurlyeq a^{\prime}$ denotes the event that $a$ wins over $a^{\prime}$.
Now, we assume that there is a true $f^{*}\in\mathcal{F}$ from which the data
is generated. Further, we assume a Condorcet winner at each context:

######  Assumption 6.1.

For all context $x\\!\in\\!\mathcal{X}$, there is an action
$a^{*}(x)\\!\in\\!\mathcal{A}(x)$ such that
$f^{*}(x,a^{*}(x),a_{0})\\!\geq\\!\nicefrac{{1}}{{2}}\,\forall
a_{0}\\!\in\\!\mathcal{A}(x)$.

Note that in this case, there is no direct reward model and is therefore a
generalization of the BTL model. The absence of a reward model makes the
problem more nuanced. Accordingly, the simple regret is now defined as:

$\displaystyle
R(T)\\!=\\!\max\nolimits_{x\in\mathcal{X}}\max\nolimits_{a\in\mathcal{A}(x)}f^{*}(x,a,\pi_{T}(x))\\!-\\!\nicefrac{{1}}{{2}}~{}.$

Note that $f^{*}(x,a^{*}(x),\pi_{T}(x))\geq\nicefrac{{1}}{{2}}$ by assumption
6.1, thus $R(T)$ is always non-negative.

###  6.1 Algorithm

Our algorithm takes a function class $\mathcal{F}$ and a confidence level
$\delta\in(0,1]$ as its inputs. First, a regularized least square estimate of
$f^{*}$ is computed by minimizing the cumulative squared prediction error:

$\displaystyle\widehat{f}_{t}\in\mathop{\mathrm{argmin}}\nolimits_{f\in\mathcal{F}}\sum\nolimits_{s=1}^{t-1}\left(y_{s}-f(x_{s},a_{s},a^{\prime}_{s})\right)^{2}~{}.$
(9)

The confidence set $\mathcal{C}_{t}(\mathcal{F},\delta)$ is then defined as
the set of all functions $f\in\mathcal{F}$ satisfying

$\displaystyle\sum\nolimits_{s=1}^{t-1}\\!\\!\big{(}f(x_{s},a_{s},a^{\prime}_{s})\\!-\\!\hat{f}_{t}(x_{s},a_{s},a^{\prime}_{s})\big{)}^{2}\\!\leq\\!\beta_{t}(\mathcal{F},\delta)\;,$
(10)

where $\beta_{t}(\mathcal{F},\delta)$ is an appropriately chosen confidence
parameter. Since $y_{t}\sim\texttt{Ber}(f^{*}(x_{t},a_{t},a^{\prime}_{t}))$
given $(x_{t},a_{t},a^{\prime}_{t})$, We have $\operatorname*{{\rm
Var}}[y_{t}]\leq 1/4$. Thus, following (Ayoub et al., 2020), we set the
confidence parameter

$\displaystyle\beta_{t}(\mathcal{F},\delta)\\!=\\!2\log\frac{2\mathcal{N}\\!\left(\\!\mathcal{F}\right)}{\delta}\\!+\\!2\sqrt{\log\frac{4t(t\\!+\\!1)}{\delta}}\\!+\\!4~{},$

where $\mathcal{N}(\mathcal{F})$ denotes the
$(1/t,||\cdot||_{\infty})$-covering number333For any $\alpha>0$, we call
$\mathcal{F}^{\alpha}$ an $(\alpha,||\cdot||_{\infty})$ cover of the function
class $\mathcal{F}$ if for any $f\in\mathcal{F}$ there exists an $f^{\prime}$
in $\mathcal{F}^{\alpha}$ such that
$||f^{\prime}-f||_{\infty}:=\sup_{x\in\mathcal{X}}|f^{\prime}(x)-f(x)|\leq\alpha$.
of $\mathcal{F}$. This choice of confidence width ensures that $f^{*}$ lies in
the confidence set $\mathcal{C}_{t}(\mathcal{F},\delta)$ at all time instant
$t\geq 1$ with probability at least $1-\delta$ (Lemma B.1).

Next, for each triplet $(x,a,a^{\prime})$, we define the exploration bonus
$b_{t}(x,a,a^{\prime})$ at round $t$ as

$\displaystyle\\!\\!b_{t}(x,a,a^{\prime})\\!=\\!\max_{f_{1},f_{2}\in\mathcal{C}_{t}(\mathcal{F},\delta)}\lvert
f_{1}(x,a,a^{\prime})\\!-\\!f_{2}(x,a,a^{\prime})\rvert,$ (11)

which measures the uncertainty of a pair of actions $a,a^{\prime}$ given a
context $x$ with respect to the confidence set
$\mathcal{C}_{t}(\mathcal{F},\delta)$. The near-optimal action set
$\mathcal{A}_{t}(x)$ at round $t$ is defined as the set of all actions in the
previous set $\mathcal{A}_{t-1}(x)$ satisfying

$\displaystyle\hat{f}_{t}(x,a,a_{0})+b_{t}(x,a,a_{0})\geq\nicefrac{{1}}{{2}}\,\forall
a_{0}\in\mathcal{A}_{t-1}(x)~{}.$ (12)

Intuitively speaking, we retain only those actions from the previous near-
optimal set which are not significantly outperformed by other actions
according to the estimates of the current round. Since
$f^{*}\in\mathcal{C}_{t}(\mathcal{F},\delta)$, the optimal action $a^{*}(x)$
lies in $\mathcal{A}_{t}(x)$ for each context $x$ for all $t$ with high
probability (Lemma B.2). By pruning out suboptimal actions every round, we
make better use of samples. When the set $\mathcal{A}_{t}(x)$ becomes a
singleton (i.e., $a^{*}(x)$ has been identified w.h.p), we remove this context
from the pool of contexts considered in future rounds.

To encourage exploration, we choose actions $(a_{t}(x),a^{\prime}_{t}(x))$
which has the highest uncertainty in $\mathcal{A}_{t}(x)$, i.e., we choose

$\displaystyle(a_{t}(x),a^{\prime}_{t}(x))\\!=\\!\mathop{\mathrm{argmax}}\nolimits_{a,a^{\prime}\in\mathcal{A}_{t}(x)}b_{t}(x,a,a^{\prime})~{}.$
(13)

Next, we choose the context $x_{t}$ that provides the maximum information
about the unknown preference function $f^{*}$, i.e.,

$x_{t}\in\mathop{\mathrm{argmax}}\nolimits_{x\in\mathcal{X}}b_{t}(x,a_{t}(x),a^{\prime}_{t}(x))~{}.$
(14)

We play the actions $a_{t}=a_{t}(x_{t})$ and
$a^{\prime}_{t}=a^{\prime}_{t}(x_{t})$ in round $t$ and observe the preference
feedback $y_{t}$. We repeat this until we have exhausted the budget $T$. Our
final policy $\pi_{T}$ samples an action uniformly at random from the set
$\mathcal{A}_{T}(x)$ for every context $x\in\mathcal{X}$. Pseudocode is given
in App. B.

###  6.2 Analysis

We characterize the complexity of the function class $\mathcal{F}$ by its
_eluder dimension_ (Russo & Van Roy, 2013).

######  Definition 6.2 (Eluder dimension).

The $\varepsilon$-eluder dimension
$\dim_{\mathcal{E}}(\mathcal{F},\varepsilon)$ of a function class
$\mathcal{F}$ defined on a domain $\mathcal{X}$ is the length of the longest
sequence $\\{x_{i}\\}_{i=1}^{n}\\!\subseteq\\!\mathcal{X}$ of input points
such that for some $\varepsilon^{\prime}\\!\geq\\!\varepsilon$ and for each
$i\in\\{2,\ldots,n\\}$,

$\displaystyle\sup_{f_{1},f_{2}\in\mathcal{F}}\\!\bigg{\\{}\\!(f_{1}\\!-\\!f_{2})(x_{i})\\!\;\Big{|}\;\\!\\!\sqrt{\sum\nolimits_{j=1}^{i-1}(f_{1}\\!-\\!f_{2})^{2}(x_{i})}\\!\leq\\!\varepsilon^{\prime}\\!\bigg{\\}}\\!>\\!\varepsilon^{\prime}~{}.$

We denote by
$d_{\mathcal{E}}(\mathcal{F})=\dim_{\mathcal{E}}\left(\mathcal{F},1/T\right)$,
the $(1/T)$-Eluder dimension of the function class $\mathcal{F}$. Now, we
state sub-optimality guarantee of the final policy using eluder dimension and
metric entropy of the function class $\mathcal{F}$.

######  Theorem 6.3 (Suboptimality Gap).

Let $\delta\in(0,1)$. Under assumption 6.1, the suboptimality gap $R(T)$ of
our policy $\pi_{T}$ after running APO-Gen (algorithm 3) for $T$ steps is
upper bounded with probability at least $1-\delta$ as

$\displaystyle
R(T)\leq\tilde{O}\bigg{(}\sqrt{\frac{\log(\mathcal{N}(\mathcal{F})T/\delta)d_{\mathcal{E}}(\mathcal{F})}{T}}\bigg{)}.$

Proof is deferred to Appendix B due to space constraint but essentially
follows ideas similar to Theorem 4.2 with difference that we crucially
leverage action elimination (Step 8).

BTL model. For the BTL preference model
$f(x,a,a^{\prime})=\mu(\phi(x,a)^{\top}\theta\\!-\\!\phi(x,a^{\prime})^{\top}\theta)$.
Define $r=\overline{h}/\underline{h}$, where

$\displaystyle\overline{h}$
$\displaystyle=\sup\nolimits_{x,a,a^{\prime},\theta}\,\dot{\mu}(\phi(x,a)^{\top}\theta\\!-\\!\phi(x,a^{\prime})^{\top}\theta)~{},$
$\displaystyle\underline{h}$
$\displaystyle=\inf\nolimits_{x,a,a^{\prime},\theta}\,\dot{\mu}(\phi(x,a)^{\top}\theta\\!-\\!\phi(x,a^{\prime})^{\top}\theta)~{}.$

Then the $\log\mathcal{N}(\mathcal{F})$ and Eluder dimension of $\mathcal{F}$
are at most $O(d\log(\overline{h}T))$ and
$O(dr^{2}\overline{h}\log(rS\overline{h}T))$, respectively. Note that
$\underline{h}=1/\kappa$ and $\overline{h}\leq 1/4$. This yields
$\log\mathcal{N}(\mathcal{F})=O(d\log T)$ and
$d_{\mathcal{E}}(\mathcal{F})=O(\kappa^{2}d\log T)$. Substituting this in
Theorem 6.3, we get the sub-optimality gap $O(\kappa d/\sqrt{T})$, which is
$\sqrt{\kappa}$ factor loose than Theorem 4.2. This is because we crucially
use self-concordance of the sigmoid function in Theorem 4.2 to shave this
extra $\sqrt{\kappa}$ factor. Nevertheless, Theorem 6.3 is general enough to
subsume other preference models (e.g. probit/Thurstone) beyond the BTL model.

Conclusion. In this work we aimed to answer the question whether the simple
approach of sampling prompts uniformly from a dataset to solicit feedback is
sample efficient. We showed that this method can suffer constant suboptimality
gap when used for model alignment. Then we proposed APO which actively samples
contexts (prompts) to achieve $O(1/\sqrt{T})$ suboptimality scaling with
number of samples $T$. We believe that our algorithm recipe is general enough
to be extended to other alignment methods like Direct Preference Optimization
(Rafailov et al., 2023). This is a promising future direction of our work
towards building sample-efficient algorithms for LLM alignment.

## Broader Impact

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

## References

  * Abeille et al. (2021) Abeille, M., Faury, L., and Calauzènes, C.  Instance-wise minimax-optimal algorithms for logistic bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 3691–3699. PMLR, 2021.
  * Ayoub et al. (2020) Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L.  Model-based reinforcement learning with value-targeted regression.  In _International Conference on Machine Learning_ , pp. 463–474. PMLR, 2020.
  * Bradley & Terry (1952) Bradley, R. A. and Terry, M. E.  Rank analysis of incomplete block designs: I. the method of paired comparisons.  _Biometrika_ , 39(3/4):324–345, 1952.
  * Bubeck et al. (2015) Bubeck, S. et al.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.
  * Char et al. (2019) Char, I., Chung, Y., Neiswanger, W., Kandasamy, K., Nelson, A. O., Boyer, M., Kolemen, E., and Schneider, J.  Offline contextual bayesian optimization.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Chen et al. (2022) Chen, X., Zhong, H., Yang, Z., Wang, Z., and Wang, L.  Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation.  In _International Conference on Machine Learning_ , pp. 3773–3793. PMLR, 2022.
  * Christiano et al. (2017) Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30, 2017.
  * Dudík et al. (2015) Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A., and Zoghi, M.  Contextual dueling bandits.  In _Conference on Learning Theory_ , pp. 563–587. PMLR, 2015.
  * Faury et al. (2022) Faury, L., Abeille, M., Jun, K.-S., and Calauzènes, C.  Jointly efficient and optimal algorithms for logistic bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 546–580. PMLR, 2022.
  * Glaese et al. (2022) Glaese, A., McAleese, N., Trebacz, M., Aslanides, J., Firoiu, V., Ewalds, T., Rauh, M., Weidinger, L., Chadwick, M., Thacker, P., et al.  Improving alignment of dialogue agents via targeted human judgements.  _arXiv preprint arXiv:2209.14375_ , 2022.
  * Hazan et al. (2016) Hazan, E. et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Lee et al. (2023) Lee, J., Yun, S.-Y., and Jun, K.-S.  Improved regret bounds of (multinomial) logistic bandits via regret-to-confidence-set conversion, 2023.
  * Li et al. (2022) Li, X., Mehta, V., Kirschner, J., Char, I., Neiswanger, W., Schneider, J., Krause, A., and Bogunovic, I.  Near-optimal policy identification in active reinforcement learning.  _arXiv preprint arXiv:2212.09510_ , 2022.
  * Luce (2012) Luce, R. D.  _Individual choice behavior: A theoretical analysis_.  Courier Corporation, 2012.
  * Maas et al. (2011) Maas, A. L., Daly, R. E., Pham, P. T., Huang, D., Ng, A. Y., and Potts, C.  Learning word vectors for sentiment analysis.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pp. 142–150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/P11-1015.
  * Mehta et al. (2023) Mehta, V., Das, V., Neopane, O., Dai, Y., Bogunovic, I., Schneider, J., and Neiswanger, W.  Sample efficient reinforcement learning from human feedback via active exploration.  _arXiv preprint arXiv:2312.00267_ , 2023.
  * Ouyang et al. (2022) Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Pacchiano et al. (2021) Pacchiano, A., Saha, A., and Lee, J.  Dueling rl: reinforcement learning with trajectory preferences.  _arXiv preprint arXiv:2111.04850_ , 2021.
  * Radford et al. (2019) Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I.  Language models are unsupervised multitask learners.  2019\.
  * Rafailov et al. (2023) Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, C. D., and Finn, C.  Direct preference optimization: Your language model is secretly a reward model, 2023.
  * Russo & Van Roy (2013) Russo, D. and Van Roy, B.  Eluder dimension and the sample complexity of optimistic exploration.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Saha (2021) Saha, A.  Optimal algorithms for stochastic contextual preference bandits.  _Advances in Neural Information Processing Systems_ , 34:30050–30062, 2021.
  * Saha & Krishnamurthy (2022) Saha, A. and Krishnamurthy, A.  Efficient and optimal algorithms for contextual dueling bandits under realizability.  In _International Conference on Algorithmic Learning Theory_ , pp. 968–994. PMLR, 2022.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Shah et al. (2015) Shah, N., Balakrishnan, S., Bradley, J., Parekh, A., Ramchandran, K., and Wainwright, M.  Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence.  In _Artificial intelligence and statistics_ , pp. 856–865. PMLR, 2015.
  * Stiennon et al. (2020) Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021, 2020.
  * Zhu et al. (2023) Zhu, B., Jiao, J., and Jordan, M. I.  Principled reinforcement learning with human feedback from pairwise or $k$-wise comparisons.  _arXiv preprint arXiv:2301.11270_ , 2023.

##  Appendix A Missing Proofs from Section 4

First we state the result from logistic bandit literature that characterizes
the confidence set for the constrained maximum likelihood estimator. Here we
give one version of the confidence set from (Lee et al., 2023) but note that
similar guarantees are also derived in (Abeille et al., 2021).

######  Lemma A.1 (Confidence Set for MLE (Theorem 1 of (Lee et al., 2023)).

Let $\hat{\theta}_{t}$ be the constrained maximum likelihood estimator after
$t-1$ time steps defined as follows:

$\displaystyle\hat{\theta}_{t}=\mathop{\mathrm{argmin}}_{\theta\in\Theta}-\sum_{s=1}^{t-1}$
$\displaystyle
y_{s}\log(\mu(z_{s}^{\intercal}\theta))+(1-y_{s})\log(1-\mu(z_{s}^{\intercal}\theta))$

Now define the set

$\mathcal{C}_{t}(\delta)=\\{\theta\in\Theta:\mathcal{L}_{t}(\theta)-\mathcal{L}_{(}\hat{\theta})\leq\beta_{t}(\delta)^{2}\\}$

where
$\beta_{t}(\delta)=\sqrt{10d\log\left(\frac{St}{4d}+e\right)+2(e-2+S)\log\left(\frac{1}{\delta}\right)}$.
Then we have $P(\forall t\geq 1,\theta^{*}\in\mathcal{C}_{t}(\delta))\geq
1-\delta$.

The details of the proof can be found in section 3.1 of (Lee et al., 2023).
Next we present another lemma that quantifies the parameter estimation error.
Using this lemma and a novel self-concordance property, we will prove A.3.

######  Lemma A.2 (Lemma 6 of (Lee et al., 2023)).

Let $\hat{\theta}_{t}$ be defined above. Further, let $\theta^{*}\in
C_{t}(\delta)$. Then,

$\lVert\hat{\theta}_{t}-\theta^{*}\rVert_{H_{t}(\theta^{*})}^{2}\leq\gamma_{t}(\delta)^{2}\coloneqq
2(2+2S)f(d,S,t,\delta)$

where

$f(d,S,t,\delta)\coloneqq
2(e-2)(2+2S)d\log(\frac{5St}{d})+2(e-2)(2+2S)\log(\frac{t}{\delta})+\frac{5d}{4}+\frac{d^{2}}{16St}$

Simplifying,
$\gamma_{t}(\delta)^{2}=CS^{2}\left(d\log\frac{St}{d}+\log\frac{t}{\delta}\right)$
for some $C>0$.

The proof of the lemma can be found in appendix C.4.4 of (Lee et al., 2023).
Now we are ready to present the proof of lemma A.3.

######  Lemma A.3.

Suppose $\theta^{*}\in\mathcal{C}_{t}(\delta)$. Then,
$\lVert\theta^{*}-\hat{\theta}\rVert_{H_{t}(\hat{\theta}_{t})}\leq
CS^{\nicefrac{{1}}{{2}}}\gamma_{t}(\delta)$.

###### Proof.

By Taylor’s theorem, we have,

$\displaystyle\mathcal{L}_{t}(\hat{\theta}_{t})-\mathcal{L}_{t}(\theta^{*})$
$\displaystyle=\nabla\mathcal{L}_{t}(\theta^{*})^{\intercal}(\hat{\theta}_{t}-\theta^{*})+\int_{v=0}^{1}(1-v)(\hat{\theta}-\theta^{*})^{\intercal}\nabla^{2}\mathcal{L}_{t}(\theta^{*})(\hat{\theta}-\theta^{*})dv$
$\displaystyle=\nabla\mathcal{L}_{t}(\theta^{*})^{\intercal}(\hat{\theta}_{t}-\theta^{*})+\sum_{s=1}^{t-1}\left[\int_{v=0}^{1}(1-v)\dot{\mu}(z_{s}^{\intercal}\theta^{*}+v(z_{s}^{\intercal}\hat{\theta}_{t}-z_{s}^{\intercal}\theta^{*}))dv\right](z_{s}^{\intercal}(\hat{\theta}_{t}-\theta^{*}))^{2}$
$\displaystyle=\nabla\mathcal{L}_{t}(\theta^{*})^{\intercal}(\hat{\theta}_{t}-\theta^{*})+\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}_{\tilde{G}_{t}(\theta^{*},\hat{\theta}_{t})}-\lambda\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}$

where we define
$\tilde{G}_{t}(\theta^{*},\hat{\theta}_{t})=\lambda\mathbf{I}_{d}+\sum_{s=1}^{t-1}\left[\int_{v=0}^{1}(1-v)\dot{\mu}(z_{s}^{\intercal}\theta^{*}+v(z_{s}^{\intercal}\hat{\theta}_{t}-z_{s}^{\intercal}\theta^{*}))dv\right]z_{s}z_{s}^{\intercal}$.
Thus, we obtain,

$\displaystyle\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}_{\tilde{G}_{t}(\theta^{*},\hat{\theta}_{t})}$
$\displaystyle=\mathcal{L}_{t}(\theta^{*})-\mathcal{L}_{t}(\hat{\theta}_{t})+\nabla\mathcal{L}_{t}(\theta^{*})^{\intercal}(\hat{\theta}_{t}-\theta^{*})+\lambda\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}$

Now, from a novel self-concordant analysis (see lemma C.1),
$H_{t}(\hat{\theta}_{t})\preccurlyeq
C(2+2S)^{2}\tilde{G}_{t}(\theta^{*},\hat{\theta}_{t})$ for some $C>1.01$.
Thus,

$\displaystyle\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}_{H_{t}(\hat{\theta}_{t})}$
$\displaystyle\leq
C(2+2S)^{2}\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}_{\tilde{G}_{t}(\theta^{*},\hat{\theta}_{t})}$
$\displaystyle=C(2+2S)^{2}\left[\mathcal{L}_{t}(\theta^{*})-\mathcal{L}_{t}(\hat{\theta}_{t})+\nabla\mathcal{L}_{t}(\theta^{*})^{\intercal}(\hat{\theta}_{t}-\theta^{*})+\lambda\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}\right]$
$\displaystyle\leq C(2+2S)^{2}\left[4\lambda
S^{2}+\beta_{t}(\delta)^{2}+\nabla\mathcal{L}_{t}(\theta^{*})^{\intercal}(\hat{\theta}_{t}-\theta^{*})\right]$
(15)

where the last inequality is because (a)
$\hat{\theta}_{t},\theta^{*}\in\Theta$ which implies that
$\lVert\theta^{*}-\hat{\theta}_{t}\rVert\leq\text{diam}(\Theta)=2S$ and (b) by
lemma A.1,
$\mathcal{L}_{t}(\theta^{*})-\mathcal{L}_{t}(\hat{\theta}_{t})\leq\beta_{t}(\delta)^{2}$
since $\theta^{*}\in\mathcal{C}_{t}(\delta)$ by assumption.

Thereafter, from the proof of Lemma 6 of (Lee et al., 2023) it can be
extracted that
$\lvert\nabla\mathcal{L}_{t}(\theta^{*})^{\intercal}(\hat{\theta}_{t}-\theta^{*})\rvert\leq\frac{\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}_{H_{t}(\theta^{*})}}{2(2+2S)}+f(d,S,t,\delta)~{}.$
Then using lemma A.2, the R.H.S of 15 can be bounded by $2f(d,S,t,\delta)$.
Thus, we now obtain,

$\displaystyle\lVert\hat{\theta}_{t}-\theta^{*}\rVert^{2}_{H_{t}(\hat{\theta}_{t})}$
$\displaystyle\leq C(2+2S)^{2}\left[4\lambda
S^{2}+\beta_{t}(\delta)^{2}+2f(d,S,t,\delta)\right]$ $\displaystyle\leq
C(2+2S)^{2}\left[\frac{1}{(2+2S)^{2}}+\beta_{t}(\delta)^{2}+\frac{\gamma_{t}(\delta)^{2}}{2(2+2S)}\right]$
(Setting $\lambda=\frac{1}{4S^{2}(2+2S)^{2}}$) $\displaystyle\leq
C(2+2S)^{2}\left[\frac{1}{(2+2S)}+\beta_{t}(\delta)+\frac{\gamma_{t}(\delta)}{\sqrt{2(2+2S)}}\right]^{2}$
$\displaystyle\implies\lVert\hat{\theta}_{t}-\theta^{*}\rVert_{H_{t}(\hat{\theta}_{t})}$
$\displaystyle\leq
C(2+2S)\left[\frac{1}{(2+2S)}+\beta_{t}(\delta)+\frac{\gamma_{t}(\delta)}{\sqrt{2(2+2S)}}\right]$
$\displaystyle=C(1+(2+2S)\beta_{t}(\delta)+\sqrt{2+2S}\gamma_{t}(\delta))=CS^{3/2}\sqrt{\left(d\log(\frac{St}{d})+\log(\frac{t}{\delta})\right)}$

∎

######  Theorem A.4 (Suboptimality Upper Bound).

Let $\delta\in(0,1)$. The suboptimality of the policy $\pi_{T}$ specified at
the end of APO (algorithm 1) after running the algorithm for $T$ rounds is
upper bounded with probability at least $1-\delta$ as follows:

$\displaystyle R(T)\leq
CS^{3/2}\sqrt{\left(d\log(\frac{ST}{d})+\log(\frac{T}{\delta})\right)\log\left(1+\frac{T}{\lambda\kappa
d}\right)\frac{\kappa d}{T}}$

###### Proof.

Let the suboptimality gap for a context $x\in\mathcal{X}$ be denoted as
$R(T,x)$. Thus,

$\displaystyle R(T,x)$
$\displaystyle=\left(\phi(x,a^{*}(x))-\phi(x,\pi_{T}(x))\right)^{\intercal}\theta^{*}$
$\displaystyle\overset{(1)}{\leq}\left(\phi(x,a^{*}(x))-\phi(x,\pi_{T}(x))\right)^{\intercal}\theta^{*}+\left(\phi(x,\pi_{T}(x))-\phi(x,a^{*}(x))\right)^{\intercal}\left(\frac{1}{T}\sum_{t=1}^{T}\hat{\theta}_{t}\right)$
$\displaystyle=\left(\phi(x,a^{*}(x))-\phi(x,\pi_{T}(x))\right)^{\intercal}(\theta^{*}-\frac{1}{T}\sum_{t=1}^{T}\hat{\theta}_{t})$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\left(\phi(x,a^{*}(x))-\phi(x,\pi_{T}(x))\right)^{\intercal}(\theta^{*}-\hat{\theta}_{t})$
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\lVert\phi(x,a^{*}(x))-\phi(x,\pi_{T}(x))\rVert_{H_{t}^{-1}(\hat{\theta}_{t})}\lVert\theta^{*}-\hat{\theta}_{t}\rVert_{H_{t}(\hat{\theta}_{t})}$
(Cauchy-Schwarz)

Here inequality (1) is due the definition of policy
$\pi_{T}(x)\coloneqq\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\phi(x,a)^{\intercal}\left(\frac{1}{T}\sum_{i=1}^{T}\hat{\theta}_{t}\right)$.
Now we use lemma A.3 to upper bound
$\lVert\theta^{*}-\hat{\theta}_{t}\rVert_{H_{t}(\hat{\theta}_{t})}$ with
$CS^{\nicefrac{{1}}{{2}}}\gamma_{t}(\delta)$ which we further upper bound by
$CS^{1/2}\gamma_{T}(\delta)$ after noting that
$\gamma_{t}(\delta)\leq\gamma_{t+1}(\delta)$ for all $t\in[T]$. Thus, we now
have,

$\displaystyle R(T,x)$
$\displaystyle\leq\frac{CS^{\nicefrac{{1}}{{2}}}\gamma_{T}(\delta)}{T}\sum_{t=1}^{T}\lVert\phi(x,a^{*}(x))-\phi(x,\pi_{T}(x))\rVert_{H_{t}^{-1}(\hat{\theta}_{t})}$
$\displaystyle\leq\frac{CS^{\nicefrac{{1}}{{2}}}\gamma_{T}(\delta)}{T}\sum_{t=1}^{T}\lVert\phi(x_{t},a_{t})-\phi(x_{t},a^{\prime}_{t})\rVert_{H_{t}^{-1}(\hat{\theta}_{t})}$

To get the above inequality, we use the fact that algorithm’s choice of the
triplet is
$(x_{t},a_{t},a^{\prime}_{t})\coloneqq\mathop{\mathrm{argmax}}_{x\in\mathcal{X},a,a^{\prime}\in\mathcal{A}}\lVert\phi(x,a)-\phi(x,a^{\prime})\rVert_{H_{t}^{-1}(\hat{\theta}_{t})}$.
Now, we are left with terms that can be bounded using Elliptic Potential Lemma
(lemma C.2) after using the fact that
$\lVert\phi(x_{t},a_{t})-\phi(x_{t},a^{\prime}_{t})\rVert_{H_{t}^{-1}(\hat{\theta}_{t})}\leq\sqrt{\kappa}\lVert\phi(x_{t},a_{t})-\phi(x_{t},a^{\prime}_{t})\rVert_{V_{t}^{-1}}$
due to the fact that $V_{t}\preccurlyeq\kappa H_{t}(\hat{\theta}_{t})$. Thus,

$\displaystyle R(T,x)$ $\displaystyle\leq\frac{C\sqrt{\kappa
S}\gamma_{T}(\delta)}{T}\sum_{t=1}^{T}\lVert\phi(x_{t},a_{t})-\phi(x_{t},a^{\prime}_{t})\rVert_{V_{t}^{-1}}$
$\displaystyle\leq\frac{C\sqrt{\kappa
S}\gamma_{T}(\delta)}{T}\sqrt{T\sum_{t=1}^{T}\lVert\phi(x_{t},a_{t})-\phi(x_{t},a^{\prime}_{t})\rVert^{2}_{V_{t}^{-1}}}$
(Cauchy-Schwarz) $\displaystyle\leq\frac{C\sqrt{\kappa
S}\gamma_{T}(\delta)}{T}\sqrt{2dT\log\left(1+\frac{T}{\lambda\kappa
d}\right)}$ (Lemma C.2)
$\displaystyle=CS^{3/2}\sqrt{\left(d\log(\frac{ST}{d})+\log(\frac{T}{\delta})\right)\log\left(1+\frac{T}{\lambda\kappa
d}\right)\frac{\kappa d}{T}}$ (Def. of $\gamma_{T}(\delta)$)

∎

##  Appendix B Missing Proofs from Section 6

Algorithm 3 APO-Gen: Active Preference Optimization with General Function
Approximation

0: Context set $\mathcal{X}$, action set $\mathcal{A}=[K]$, function class
$\mathcal{F}$, failure level $\delta\in(0,1)$

1: Set $\mathcal{X}_{0}=\mathcal{X}$ and
$\mathcal{A}_{0}(x)=\mathcal{A}\,\forall x\in\mathcal{X}$,

2: for $t=1,2,\dots T$ do

3: Compute function estimate $\hat{f}_{t}$ usning (9).

4: Construct confidence set $\mathcal{C}_{t}(\mathcal{F},\delta)$ using (10).

5: Intialize the $\mathcal{X}_{t}=\mathcal{X}_{t-1}$

6: for each context $x\in\mathcal{X}_{t-1}$ do

7: For each pair of actions $a,a^{\prime}\in\mathcal{A}_{t-1}(x)$, compute the
bonus $b_{t}(x,a,a^{\prime})$ using (11).

8: Find the near-optimal action set $\mathcal{A}_{t}(x)$ using (12)

9: if $\lvert\mathcal{A}_{t}(x)\rvert=1$ then

10: Set $\mathcal{A}_{T}(x)=\mathcal{A}_{t}(x)$

11: $\mathcal{X}_{t}\leftarrow\mathcal{X}_{t}\setminus\\{x\\}$

12: end if

13: end for

14: Choose context and pair of actions
$(x_{t},a_{t},a_{t}^{\prime})=\mathop{\mathrm{argmax}}_{x\in\mathcal{X}_{t},a,a^{\prime}\in\mathcal{A}_{t}(x)}b_{t}(x,a,a^{\prime})$

15: Observe preference
$y_{t}\sim\texttt{Ber}(f^{*}(x_{t},a_{t},a^{\prime}_{t}))$

16: end for

17: Output final policy $\pi_{T}(x)=a$ for some $a\in\mathcal{A}_{T}(x)$.

First let us recall the notations. At any time $t$ in the algorithm, we have a
dataset
$\mathcal{D}_{t}=\\{(x_{s},a_{s},a^{\prime}_{s},y_{s})\\}_{s=1}^{t-1}$. Let
the loss function be the squared error defined as
$\mathcal{L}_{t}(f)\coloneqq\sum_{s=1}^{t-1}(y_{s}-f(x_{s},a_{s},a^{\prime}_{s}))^{2}$.
Further let $\hat{f}_{t}$ be the least squares estimate:

$\hat{f}_{t}\in\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\mathcal{L}_{t}(f)$

and let
$\beta_{t}(\mathcal{F},\delta)=2\log\left(2\mathcal{N}\left(\mathcal{F},1/t,||\cdot||_{\infty}\right)/\delta\right)+4\left(1+\sqrt{(1/4)\log\left(4t(t+1)/\delta\right)}\right)$.
With these, we present the result that characterizes the confidence set around
$\hat{f}_{t}$.

######  Lemma B.1 (Confidence Set for Function Approximation (Lemma A.1 of
(Chen et al., 2022)).

Let $\delta\in(0,1)$. Define the confidence set

$\mathcal{C}_{t}(\mathcal{F},\delta)=\\{f\in\mathcal{F}|\sum_{s=1}^{t-1}(f(x_{s},a_{s},a^{\prime}_{s})-\hat{f}_{t}(x_{s},a_{s},a^{\prime}_{s}))^{2}\leq\beta_{t}(\mathcal{F},\delta)$

Let $\mathcal{E}_{t}(\delta)$ be the event that
$f^{*}\in\mathcal{C}_{t}(\mathcal{F},\delta)$. Then,
$\mathbb{P}[\mathcal{E}_{t}(\delta)]\geq 1-\delta$. Further,
$\mathbb{P}\left[\cap_{t=1}^{T}\mathcal{E}_{t}(\delta/T)\right]\geq 1-\delta$.

###### Proof.

The proof is a direct extension of lemma C.3 by observing that in our case the
subgaussianity parameter $\sigma=\nicefrac{{1}}{{4}}$ since our rewards are
Bernoulli and by setting $\alpha=\nicefrac{{1}}{{t}}$. Moreover, $C=1$ in our
case. Finally, since $\mathcal{E}_{t}(\delta/t)$ holds with probability at
least $1-\delta/t$, by union bound we can show that
$\mathbb{P}\left[\cap_{t=1}^{T}\mathcal{E}_{t}(\delta/T)\right]=1-\mathbb{P}\left[\cup_{t=1}^{T}\overline{\mathcal{E}}_{t}(\delta/T)\right]\geq
1-\sum_{t=1}^{T}\mathbb{P}[\overline{\mathcal{E}}_{t}(\delta/T)]\geq
1-\delta$. ∎

Hereon, we assume that for all $t\in[T]$, $\mathcal{E}_{t}(\delta/T)$ holds.
All subsequent guarantees are under this event.

Now for a given tuple
$(x,a,a^{\prime})\in\mathcal{X}\times\mathcal{A}\times\mathcal{A}$, for a
given $\delta\in(0,1)$, define
$b_{t}(x,a,a^{\prime})=\max_{f,f^{\prime}\in\mathcal{F}_{t}(\delta)}\lvert
f(x,a,a^{\prime})-f^{\prime}(x,a,a^{\prime})\rvert$. We have the following
lemma.

######  Lemma B.2.

For a given context $x\in\mathcal{X}$, let
$\\{\mathcal{A}_{s}(x)\\}_{s=0}^{t}$ be defined as follows: (a)
$\mathcal{A}_{0}(x)=\mathcal{A}$ and (b)
$\mathcal{A}_{s}(x)=\\{a\in\mathcal{A}_{s-1}(x)|\hat{f}_{s}(x,a,a^{\prime})+b_{s}(x,a,a^{\prime})\geq\frac{1}{2}\
\forall a^{\prime}\in\mathcal{A}_{s-1}(x)\\}$. Then, we have,
$a^{*}(x)\in\mathcal{A}_{s}(x)$.

###### Proof.

The proof is by induction. First note that by definition of $a^{*}(x)$,
$f^{*}(x,a^{*}(x),a^{\prime})\geq 1/2$ for every $a^{\prime}\in\mathcal{A}$,
and $a^{*}(x)\in\mathcal{A}_{0}(x)=\mathcal{A}$. Suppose, for some $s>0$,
$a^{*}(x)\in\mathcal{A}_{s-1}(x)$. Now, we know that under event
$\mathcal{E}_{s}(\delta/T)$, $f^{*}\in\mathcal{C}_{s}(\mathcal{F},\delta/T)$
and thus from definition of $b_{s}(x,a,a^{\prime})$,
$f^{*}(x,a,a^{\prime})-\hat{f}_{s}(x,a,a^{\prime})\leq b_{s}(x,a,a^{\prime})$.
Thus, for any $a^{\prime}\in\mathcal{A}_{s-1}(x)$,

$\displaystyle\frac{1}{2}\leq
f^{*}(x,a^{*}(x),a^{\prime})\leq\hat{f}_{s}(x,a^{*}(x),a^{\prime})+b_{s}(x,a^{*}(x),a^{\prime})$

Hence $a^{*}(x)\in\mathcal{A}_{s}(x)$. Thus by induction,
$a^{*}(x)\in\mathcal{A}_{s}(x)$ for all $s\in[t]$. ∎

######  Theorem B.3 (Suboptimality Upper Bound for Function Approximation).

The suboptimality of algorithm 3 is upper bounded with probability at least
$1-\delta$, as

$R(T)\leq\tilde{O}\left(\sqrt{\frac{\log(\mathcal{N}(\mathcal{F})T/\delta)d_{\mathcal{E}}(\mathcal{F})}{T}}\right)$

###### Proof.

The idea is to show that our arm elimination technique throws away arms with
large suboptimality gap in every round for every context. Thus the set
$\mathcal{A}_{t}(x)$ maintains a candidate set of good arms at every time
instant. In the end, playing any action from $\mathcal{A}_{T}(x)$ ensures that
we only play actions from a set of actions that are only $1/\sqrt{T}$
suboptimal. Formally, for any context $x\in\mathcal{X}$, the suboptimality
$R(T,x)$ is upper bounded as follows:

$\displaystyle R(T,x)$
$\displaystyle=f^{*}(x,a^{*}(x),\pi_{T}(x))-\frac{1}{2}$
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\left[\hat{f}_{t}(x,a^{*}(x),\pi_{T}(x))+b_{t}(x,a^{*}(x),\pi_{T}(x))-\frac{1}{2}\right]$
($a^{*}(x),\pi_{T}(x)\in\mathcal{A}_{t}(x)\ \forall\ t\in[T]$)
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\left[\frac{1}{2}-\hat{f}_{t}(x,\pi_{T}(x),a^{*}(x))+b_{t}(x,a^{*}(x),\pi_{T}(x))\right]$
($f(x,a,a^{\prime})+f(x,a^{\prime},a)=1\ \forall\ f\in\mathcal{F}$)
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\left[\frac{1}{2}-\hat{f}_{t}(x,\pi_{T}(x),a^{*}(x))+b_{t}(x,\pi_{T}(x),a^{*}(x))\right]$
($b_{t}(x,a,a^{\prime})=b_{t}(x,a^{\prime},a)$)
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\left[b_{t}(x,\pi_{T}(x),a^{*}(x))+b_{t}(x,\pi_{T}(x),a^{*}(x))\right]$
(Since $\pi_{T}(x),a^{*}(x)\in\mathcal{A}_{t}(x)$, line 7 Algorithm 3)
$\displaystyle=\frac{2}{T}\sum_{t=1}^{T}b_{t}(x,\pi_{T}(x),a^{*}(x))$
$\displaystyle\leq\frac{2}{T}\sum_{t=1}^{T}b_{t}(x_{t},a_{t},a^{\prime}_{t})$
(Line 9 of Algorithm 3)

Now we invoke lemma C.4 to bound the RHS.

$\displaystyle
R(T,x)\leq\frac{2}{T}\sum_{t=1}^{T}b_{t}(x_{t},a_{t},a^{\prime}_{t})\leq\frac{2}{T}\left[\frac{1}{T}+\min\\{d_{\mathcal{E}}(\mathcal{F}),T\\}+2\beta_{T}(\mathcal{F},\delta/T)\sqrt{d_{\mathcal{E}}(\mathcal{F})T}\right]$

Simplifying constants and using the fact that $\min\\{a,b\\}\leq\sqrt{ab}$ for
$a,b>0$, $R(T,x)\leq
C\beta_{T}(\mathcal{F},\delta/T)\sqrt{\frac{d_{\mathcal{E}}(\mathcal{F})}{T}}$.
Using order notation, we have for all $x\in\mathcal{X}$ with probability at
least $1-\delta$,

$R(T,x)\leq\tilde{O}\left(\sqrt{\frac{\log(\mathcal{N}(\mathcal{F})T/\delta)d_{\mathcal{E}}(\mathcal{F})}{T}}\right)$

∎

##  Appendix C Some Useful Results

######  Lemma C.1.

Let $z,z^{\prime}\in\mathbb{R}$ and
$\tilde{\alpha}(z,z^{\prime})\coloneqq\int_{0}^{1}(1-v)\dot{\mu}(z+v(z^{\prime}-z))dv$.
Then, for some $C>1$ ($1.01$ suffices),

$\tilde{\alpha}(z,z^{\prime})\geq\frac{\dot{\mu}(z^{\prime})}{C(2+\lvert
z-z^{\prime}\rvert)^{2}}$

###### Proof.

Firstly, note that by property of definite integrals
$\int_{a}^{b}f(x)dx=\int_{a}^{b}f(a+b-x)dx$, we have

$\int_{0}^{1}(1-v)\dot{\mu}(z+v(z^{\prime}-z))dv=\int_{0}^{1}v\dot{\mu}(z^{\prime}+v(z-z^{\prime}))dv$

Now, we use the fact that $\dot{\mu}(x)\geq\dot{\mu}(y)\exp(-\lvert
x-y\rvert)$ (see appendix A of (Faury et al., 2022)). Let $a=\lvert
z-z^{\prime}\rvert$. Thus,

$\displaystyle\int_{0}^{1}v\dot{\mu}(z^{\prime}+v(z-z^{\prime}))dv$
$\displaystyle\geq\int_{0}^{1}v\dot{\mu}(z^{\prime})\exp(-va)dv$
$\displaystyle=\dot{\mu}(z^{\prime})\int_{0}^{1}v\exp(-va)dv$
$\displaystyle=\dot{\mu}(z^{\prime})\left(\frac{1-(1+a)e^{-a}}{a^{2}}\right)$
$\displaystyle\geq\dot{\mu}(z^{\prime})\left(\frac{1-1/a}{a^{2}}\right)$
($(1+a)e^{-a}<\frac{1}{a}\ \forall a>0$)
$\displaystyle=\dot{\mu}(z^{\prime})\left(\frac{a-1}{a^{3}}\right)$

Again, from appendix A of (Faury et al., 2022), we have that
$\tilde{\alpha}(z,z^{\prime})\geq\dot{\mu}(z)/(2+a)$ which can again be lower
bounded with $\dot{\mu}(z^{\prime})e^{-a}/(2+a)$. Combining this lower bound
with above, we get,

$\displaystyle\tilde{\alpha}(z,z^{\prime})\geq\max\left\\{\frac{e^{-a}}{2+a},\frac{a-1}{a^{2}}\right\\}\dot{\mu}(z^{\prime})$

Finally, we can lower bound the RHS with
$\frac{\dot{\mu}(z^{\prime})}{C(2+a)^{2}}$ for some $C>1.01$. To do this, let
$f(x)=(2+x)e^{-x}$. Thus, $f^{\prime}(x)=-(1+x)e^{-x}$ which implies that
$f(x)$ is decreasing for $x>0$. Thus, $f(x)=\frac{1}{C}$ is satisfied for only
one value of $x$ since $f(0)=2>1/C$. For $C=1.01$, this value is
$x_{0}=1.1608$. Then, for $0\leq x\leq x_{0}$, $e^{-x}/(2+x)\geq
1/C(2+x)^{2}$. Again, let $g(x)=(x-1)(x+2)^{2}/x^{3}$. Simplifying, we have,
$g(x)=1+\frac{3}{x}-\frac{4}{x^{3}}$. It is easy to see that for $x\geq
2/\sqrt{3}$, $\frac{3}{x}\geq\frac{4}{x^{3}}$ which implies that $g(x)\geq 1$
for all $x\geq x_{1}=2/\sqrt{3}=1.1547$. So, for $x\geq 1.1547$, $g(x)\geq
1/C$ (since $C>1$) which is equivalent to
$\frac{(x-1)}{x^{3}}\geq\frac{1}{C(x+2)^{2}}$. The numeric solution to
$g(x)=1/C$ for $C=1.01$ is $x_{2}=1.1525$. It can be checked via first
derivative test that $g(x)$ is increasing in $x_{2}\leq x\leq x_{1}$. Thus,
indeed, $g(x)\geq 1/C$ for all $x\geq x_{2}$. Jence, we have established so
far that for $C=1.01$,

$\displaystyle\frac{x-1}{x^{3}}$
$\displaystyle\geq\frac{1}{C(x+2)^{2}}\quad\quad\forall\ x\geq x_{2}=1.1525$
$\displaystyle\frac{e^{-x}}{2+x}$
$\displaystyle\geq\frac{1}{C(x+2)^{2}}\quad\quad\forall\ x\leq x_{0}=1.1608$

Since, $x_{2}\leq x_{0}$, we have the required result that
$\max\left\\{\frac{e^{-a}}{2+a},\frac{a-1}{a^{2}}\right\\}\dot{\mu}(z^{\prime})\geq\frac{\dot{\mu}(z^{\prime})}{C(2+a)^{2}}$
for all $a\geq 0$ which completes the proof. ∎

######  Lemma C.2 (Elliptic Potential Lemma).

Let $\\{z_{s}\\}_{s=1}^{t}$ be a sequence of vectors in $\mathbb{R}^{d}$ such
that $\lVert z_{s}\rVert\leq L$ for any $s\in[t]$. Let
$V_{t}=\sum_{s=1}^{t-1}z_{s}z_{s}^{\intercal}+\lambda I$. Then,

$\sum_{s=1}^{t}\lVert z_{s}\rVert^{2}_{V^{-1}_{s}}\leq
2d\log\left(1+\frac{tL^{2}}{\lambda d}\right)$

.

Now we present the confidence set properties of function approximation. We use
the same notations as (Ayoub et al., 2020)

Let $(X_{p},Y_{p})_{p\geq 1}$ be a sequence of random elements,
$X_{p}\in\mathcal{X}$ for some measurable set $\mathcal{X}$ and
$Y_{p}\in\mathbb{R}$. Let $\mathcal{F}$ be a subset of the set of real-valued
measurable functions with domain $\mathcal{X}$. Let
$\mathbb{F}=(\mathbb{F}_{p})_{p\geq 0}$ be a filtration such that for all
$p\geq 1,(X_{1},Y_{1},\dots,X_{p-1},Y_{p-1},X_{p})$ is $\mathbb{F}_{p-1}$
measurable and such that there exists some function $f^{*}\in\mathcal{F}$ such
that $\mathbb{E}[Y_{p}\mid\mathbb{F}_{p-1}]=f^{*}(X_{p})$ holds for all $p\geq
1$. The (nonlinear) least-squares predictor given
$(X_{1},Y_{1},\ldots,X_{t},Y_{t})$ is
$\hat{f}_{t}=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\sum^{t}_{p=1}(f(X_{p})-Y_{p})^{2}$.
We say that $Z$ is conditionally $\rho$-subgaussian given the $\sigma$-algebra
$\mathbb{F}$ if for all $\lambda\in\mathbb{R},\ \log\mathbb{E}[\exp(\lambda
Z)\mid\mathbb{F}]\geq\frac{1}{2}\lambda^{2}\rho^{2}$. For $\alpha>0$, let
$N_{\alpha}$ be the $\lVert\cdot\rVert_{\infty}$-covering number of
$\mathcal{F}$ at scale $\alpha$. That is, $N_{\alpha}$ is the smallest integer
for which there exist $\mathcal{G}\subset\mathcal{F}$ with $N_{\alpha}$
elements such that for any $f\in\mathcal{F}$, $\min_{g\in\mathcal{G}}\lVert
f-g\rVert_{\infty}\leq\alpha$. For $\beta>0$, define
$\mathcal{F}_{t}(\beta)=\\{f\in\mathcal{F}:\sum_{s=1}^{t}(f(X_{s})-\hat{f}_{t}(X_{p}))^{2}\leq\beta\\}$.

######  Lemma C.3 (Theorem 5 of (Ayoub et al., 2020)).

Let $\mathbb{F}$ be the filtration defined above and assume that the functions
in $\mathcal{F}$ are bounded by the positive constant $C>0$. Assume that for
each $s\geq 1$, $(Y_{p}-f^{*}(X_{p}))_{p}$ is conditionally
$\sigma$-subgaussian given $\mathbb{F}_{p-1}$. Then, for any $\alpha>0$, with
probability $1-\delta$, for all $t\geq
1,f^{*}\in\mathcal{F}_{t}(\beta_{t}(\delta,\alpha))$, where

$\beta_{t}(\delta,\alpha)=8\sigma^{2}\log(2N_{\alpha}/\delta)+4t\alpha\left(C+\sqrt{\sigma^{2}\log(4t(t+1)/\delta)}\right)~{}.$

######  Lemma C.4 (Lemma 2 of (Russo & Van Roy, 2013)).

Let $\mathcal{F}\in B_{\infty}(\mathcal{X},C)$ be a set of functions bounded
by $C>0$, $(\mathcal{F}_{t})_{t\geq 1}$ and $(x_{t})_{t\geq 1}$ be sequences
such that $\mathcal{F}_{t}\subset\mathcal{F}$ and $x_{t}\in\mathcal{X}$ hold
for $t\geq 1$. Let
$\mathcal{F}\mid_{x_{1:t}}=\\{(f(x_{1}),\dots,f(x_{t})):f\in\mathcal{F}\\}(\subset\mathbb{R}^{t})$
and for $S\subset R^{t}$, let $diam(S)=\sup_{u,v\in S}\lVert u-v\rVert_{2}$ be
the diameter of $S$. Then, for any $T\geq 1$ and $\alpha>0$ it holds that

$\sum^{T}_{t=1}diam(\mathcal{F}_{t}\mid_{x_{t}})\leq\alpha+C(d\wedge
T)+2\delta T\sqrt{dT}$

where $\delta_{T}=\max_{1\leq t\leq T}diam(\mathcal{F}_{t}\mid_{x_{t}})$ and
$d=dim_{\mathcal{E}}(\mathcal{F},\alpha)$ is the Eluder Dimension of
$\mathcal{F}$.