Making RL with Preference-based Feedback Efficient via Randomization
Authors: Runzhe Wu
Wen Sun
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning
preference-based feedback
theory
active learning
posterior sampling
Primary area: reinforcement learning

Abstract: Reinforcement Learning algorithms that learn from human feedback (RLHF) need to be efficient in terms of *statistical complexity, computational complexity, and query complexity*. In this work, we consider the RLHF setting where the feedback is given in the format of preferences over pairs of trajectories. In the linear MDP model, using randomization in algorithm design, we present an algorithm that is sample efficient (i.e., has near-optimal worst-case regret bounds) and has polynomial running time (i.e., computational complexity is polynomial with respect to relevant parameters). Our algorithm further minimizes the query complexity through a novel randomized active learning procedure. In particular, our algorithm demonstrates a near-optimal tradeoff between the regret bound and the query complexity. To extend the results to more general nonlinear function approximation, we design a model-based randomized algorithm inspired by the idea of Thompson sampling. Our algorithm minimizes Bayesian regret bound and query complexity, again achieving a near-optimal tradeoff between these two quantities. Computation-wise, similar to the prior Thompson sampling algorithms under the regular RL setting, the main computation primitives of our algorithm are Bayesian supervised learning oracles which have been heavily investigated on the empirical side when applying Thompson sampling algorithms to RL benchmark problems.

Published as a conference paper at ICLR 2024
MAKING RL WITH PREFERENCE-BASED FEEDBACK EFFICIENT VIA RANDOMIZATION
Runzhe Wu
Wen Sun
Department of Computer Science Comell University r4 60 corne edu
Department of Computer Science Comell University ws4550coz 1 edu
ABSTRACT
Reinforcement Learning algorithms that learn from human feedback (RLHF) need be efficient terms of statistical complexity, computational complexity, and query complexity. In this work, we consider the RLHF setting where the feedback is given in the format of preferences over pairs of trajectories. model, using randomization in algorithm design, present an algorithm that is sample efficient (i.e., has near-optimal worst-case regret bounds) and has poly- nomial rumning time (i.e., computational complexity is polynomial with respect to relevant parameters). Our algorithm further minimizes the query complexity through a novel randomized active learning procedure. In particular, our algo- rithm demonstrates a near-optimal tradeoff between the regret bound and the query complexity. To extend the results more general nonlinear function approxi- mation, we design a model-based randomized algorithm inspired by the idea of Thompson sampling. Our algorithm minimizes Bayesian regret bound and query complexity, again achieving near-optin optimal tradeoff between these two quantities. Computation- wise, similar the prior Thompson sampling algorithms under the regular RL setting, the main computation primitives of our algorithm are Bayesian supervised learning oracles which have been heavily investigated on the empirical side when applying Thompson sampling algorithms to RL benchmark problems.
the linear MDP
INTRODUCTION
Reinforcement learning from human feedback (RLHF) has been widely used across various do- mains, including robotics (Jain et al., 2013; 2015) and natural language processing (Stiennon et al., 2020; Ouyang et al., 2022). Unlike standard RL, RLHF requires the agent to learn from feedback in the format of preferences between pairs of trajectories instead of per-step reward since assigning a dense reward function for each state is challenging in many tasks. For instance, in natural language generation, rating each generated token individually is challenging. Hence, it is more realistic to ask humans compare two pieces of text and indicate their preference. Recent works have shown that, by integrating preference-ber based feedback into the training process, we can align models with human intention and enable high-quality numan-machin interaction.
Despite the existing empirical applications of RLHE, its theoretical foundation remains far from satisfactory. Empirically, researchers first learn reward models from preference-based feedback and then optimize the reward models via policy gradient- based algorithms such as PPO (Schulman et al., 2017). Questions such whether or not the learned reward model is accurate, whether PPO suf- ficient for deep exploration, and how to strategically collect more feedback on the fly are often ignored. Theoretically, prior works study the regret bound for RL with preference-basee feedback (Saha et al.. 2023; Chen et al., 2022). Despite achieving sublinear worst-case regret, these algo- rithms are computationally intractable even for simplified models such as tabular Markov Decision Processes (MDPs). This means that cannot easily leverage the algorithmic ideas in prior work to guide or improve how we perform RLHF in practice.
In addition maximizing reward, another important metric in RLHF is the query complexity since human feedback expensive to collect. To illustrate, we note that InstructGPT's training data com- prises mere 30K instances of human feedback (Ouyang al., 2022), which is significantly fewer

---

Published as a conference paper at ICLR 2024
than the internet-scale dataset for training the GPT-3 base model. This underscores the challenge of scaling up the size of human feedback datasets. Ross et al. (2013); Laskey et al. (2016) also pointed out that extensively querying for feedback puts too much burden human experts. Empir- ically, Lightman et al. (2023) observes that active learning reduces query complexity and improves the learned reward model. In theory, query complexity is mostly studied in the settings of active learning, online learning, and bandits (Cesa-Bianchi et al., 2005; Dekel et al., 2012; Agarwal, 2013; Hanneke & Yang, 2021; Zhu & Nowak, 2022; Sckhari al., 2023a;b), but overlooked in RL.
In this work, we aim to design new RL algorithms that can learn from preference-based feedback feedbba and can be efficient in statistical complexity (i.e., regret), computational complexity and query complexity. In particular, we strike optrmoppimal balance between regret minimization and query complexity minimization. To achieve this goal, our key idea is to use randomization in algorithm design. We summarize our new algorithmic ideas and key contributions as follows.
1. For MDPs with linear structure (i.e., linear MDP (Jin et al., 2020)), propose the first RL algorithm that achieves sublinear worst-case regret and computational efficiency simultaneously with preference- achieve a no-regret guarantee and computational efficiency. Moreover, it has an active learning procedure and attains a near-optimal tradeoff between the regret and the query complexity. Our algorithm adds random Gaussian noises to the learned state-action- wise reward model and the least-squares value iteration (LSVI) procedure. Using random noise instead of the UCB-style technique (Azar et al., 2017) preserves the Markovian property in the reward model and allows one to use dynamic programming to achieve computation efficiency.
feedback. Even when reduced tabular MDPs, it is still the first to
2. For function approximation beyond linear, we present a model-based Thompson-sampal algorithm that forms posterior distributions over the transitions and reward models. Assuming the transition and the reward model class both have small E (-normm eluder dimension - a structural condition introduced in Liu et al. (2022a) that is more general than the common 4--nrr eluder dimension (Russo & Van Roy, 2013), we show that our algorithm again achieves near-optimal tradeoff between the Bayesian regret and the Bayesian query complexity. Computation wise, similar to previous TS algorithms for regular RL (c.g.. Osband et al. (2013)), the primary com- putation primitives Bayesian supervised learning oracles for transition and reward learning.
(TS)
3.
Our query conditions for both algorithms are based on variance-style uncertainty quantification of the preference induced by the randomness of the reward model. We query for preference feed- back only when the uncertainty of the preference computing the uncertainty can be easily done using i.i.d. random reward models drawn from the reward model distribution, which makes the active query procedure computationally tractable.
pair of trajectories is large. Approximately
Overall, while our main contribution is on the theoretical side, our theoretical investigation provides several new practical insights. For instance, for regret minimization, our algorithms propose to draw a pair of trajectories with one from the latest policy and the other from an older policy instead of drawing two trajectories from the same policy (e.g., Christiano et al. (2017)), avoiding the situation of drawing two similar trajectories when the policy becomes more and more deterministic. Our theory shows that drawing two trajectories from combination of new and older policies balances exploration and exploitation better. Another practical insight is the variance-style uncertainty measure for designing the query condition. Compared to more standard active learning procedure that relies on constructing version space and confidence intervals (Dekel et al., 2012; Puchkin & Zhivotovskiy, 2021; Zhu & Nowak, 2022; Sekhari al., 2023a:b), our new approach comes with strong theoretical guarantees and is more computationally tractable. It is also amenable to existing implementations of Thompson sampling RL algorithms (c.g.. using bootstrapping to approximate the posterior sampling (Osband et al., 201 6a; 2023)).
2 COMPARISON TO PRIOR WORK
RL with preference-basee feedback. Many recent works have obtained statistically efficient algo- rithms but are computationally inefficient even for tabular MDPs due to intractable policy search and version space construction (Chen et al., 2022; Zhan al., 2023a;b; Saha al., 2023). For example, Zhan et al. (2023b); Saha et al. (2023) use the idea from optimal design and rely on the computation [s ((8, B. (.,aa) a)ll with some positive definite matrix A.
oracle: arg max, ar eeel
2

---

Published as a conference paper at ICLR 2024
Here || == == Azx and Φ is some state-action feature.' It is unclear how to implement this ora- cle since standard planning approaches based on dynamic programming cannot be applied here. In addition, these methods also actively maintain a policy space by eliminating potentially sub-optimal policies. The policy class can be exponentially large even in tabular settings, so how to maintain it computationally efficiently is unclear. We provide more detailed discussion on the challenges in achieving computational efficiency in RLHF in Appendix A.
While the work mentioned above is intractable even for tabular MDPs, there are some other works that could be computationally efficient but have weaker statistical results. For instance, very recently, Wang et al. (2023) proposed a reduction framework that can be computationally efficient (depending on the base algorithm used in the reduction). However, their algorithms have PAC bounds while we focus on regret minimization. Moreover, we achieve a near-optimal balance between regret and query complexity. Novoseller et al. (2020) proposed a posterior sampling algorithm for tabular MDP but their analysis asymptotic (i.e., they do not address exploration, exploitation, and query complexity tradeoff). Xu et al. (2020) proposed efficient algorithms that do reward-free exploration. However, it is limited to tabular MDPs and PAC bounds.
In contrast to the above works, our algorithms aim to achieve efficiency in statistical, computa- tional, and query complexities simultancously. Our algorithms leverage randomization to balance exploration, exploitation, and feedback query. Randomization allows to avoid non-standard computational oracles and only use standard Dynamic Programming (DP) based oracles (e.g.. value iteration), which makes our algorithm computationally more tractable. Prior works that simultaneously achieve efficiency in all three aspects are often restricted in the bandit and imitation learning settings where the exploration problem is much easier (Sekhari et al., 2023a).
RL via randomization. There are two lines of work that study RL via randomization. The first injects random noise into the learning object to encourage exploration. A typical example is the randomized least-squares value iteration (RLSVI) (Osband et al., 2016b), which adds Gaussian noise into the least-squares estimation and achieves near-optimal worst-case regret (Zanette et al., 2020; Agrawal et al., 2021) for linear MDPs. The other line of work is Bayesian RI and uses Thompson sampling (TS) (Osband et al., 2013; Osband & Van Roy, 2014b;a; Gopalan & Mannor, 2015; Agrawal & Jia, 2017; Efroni et al., 2021; Zhong al., 2022; Agarwal & Zhang, 2022). They achieve provable Bayesian regret upper bound by maintaining posterior distributions over models.
Active learning. Numerous studies have studied active learning across various settings (Cesa- Bianchi et al., 2005; Dekel et al., 2012; Agarwal, 2013; Hanneke & Yang. 2015: 2021; Zhu & Nowak, 2022; Sckhari et al., 2023b;a). However, most of them focus the bandits and online learning settings, and their active learning procedures are usually computationally intractable due to computing version spaces upper and lower confidence bounds. In contrast, design a variance- style uncertainty quantification for our query condition, which can be easily estimated by random samples of reward model. This makes our active learning procedure more computationally tractable.
PRELIMINARY
Notations. For two real numbers and b, we denote (a, b] {a S x < b). For integer N. we denote [N] :=
N). For a set S, we denote A(S) as the set of distributions over S. Let (--(..) denote the total variation distance.
We consider a finite-horizon Markov decision process (MDP), which is a tuple AA,,,,r", H) where is the state space, AA is the action space, p* S x A + (SS) is the transition kernel, r* S x AA + [0, 1] is the reward function, and H is the length of the episode. The interaction proceeds for T rounds. At each round E [T]. we need to select two policies क, and प. and execute them separately, which generates two trajectories 7. and 7/ where 7/ (sf, of. s at,r) for i E {0, 1}. For the case of notation, we assume a fixed initial state s1. Then, we need to decide whether to make a query for the preference between Ti and 7/. If making a query, we obtain a preference feedback 0, E {0, that is sampled from the Bernoulli distribution:
Pr(o: 1/ o r*) ) Pr(z is preferred 7f r*) (((r(())) - (+())
'These works typically assume trajectory-wise feature é(r) for trajectory т. However, even when speci- fied state-action-wii features, these algorithms are still computationally intractable, even in tabular MDPs.
3

---

Published as a conference paper at ICLR 2024
where r" (rt) Σm= r" (5/,1) ai,)) for i {0, 1) is the trajectory reward, and + : + [0. is monotonically increasing link function. We note that, by symmetry, we have (rr((=() (r)))
(()" (r))) = 1. If not making query, we receive no feedback.
This feedback model is weaker than the standard RL where the per-step reward signal is revealed. We impose the following assumption on the link function b. which has appeared in many existing works of RLHF (Saha et al., 2023; Zhu et al., 2023; Zhan et al., 2023a).
Assumption 3.1. We assume & is differentiable and there exists constants Ri R > 0 such that ri" < 4 (')x) S K for any x E [- H. H.
The constants x and F. characterize the non-linearity of o and determine the difficulty of estimating the reward from preference feedback. noteworthy that, in the theoretical results of our algo- rithms, the bounds depend polynomially on k but logarithmically on R. Some typical examples of the link functions are provided below.
Example 3.2 (Link functions). is common to have o ((x) - (xx(=xx)p((x))) which recovers the HoulleyTTerry-Leee (BTL) model (Bradley & Terry, 1952), and we have K = = exx(epp)))+xxx and R = 4. Additionally, if the trajectory-wise reward is scaled within the interval of [0, 11, then the difference in reward will be within the range of [-,1,, 1). In this case, another common choice of the link function is ((x) = =z + 1)/2. which results in K = R 2
The goal is to minimize the worst-case regret and the query complexity simultaneously:
Regrety Σ -s* (s))). - Queries Σ Zr.
Here (T( = E- E= (" an)] denotes the vtaue function of policy n. and we define (s1) = Va (81) where xt is the optimal policy that maximizes the state-value function. The variable Z, E 1] indicates whether a query is made at round f. Note that the regret looks at the sum of the performance gaps between two pairs of policies: (x*, and (T* T.).. This is standard in dueling bandits (Yue & Joachims, 2011; I; Yue et al., 2012; Dudík et al., 2015; Bengs et al., 2022;
Wu et al., 2023b) and RL with preference- based feedback (Saha et al., 2023; Chen et al., 2022).
Bayesian RL. We also consider Bayesian RL in this work when learning with general function approximation. In the Bayesian setting, Ps and r* are sampled from some known prior distributions @r and pr. The goal is to minimize the Bayesian regret and the Bayesian query complexity:
vri (+)) { BayesQueriess = E
T
T
Reyest == E Σ
- (x1) (2
Σ
7
Here the expectation is taken with respect to the prior distribution over p* and r- We will use Bayesian supervised learning oracles to compute posteriors over the transition and reward model.
4 A MODEL-FREE RANDOMIZED ALGORITHM FOR LINEAR MDPs
In this section, we present model-free algorithm for linear MDPs which is defined as follows. Assumption 4.1 (Linear MDP (Jin et al., 2020)). We assume known feature map & S A + Rd, an wnknown (signed) measure (s) E S x A, we have (*('' s, a) o (s, (.,aa))a .u(s") and r" rs(ss a) = o_ (s.a) 67. We assume (lo(s, 2) < 1 for all (s, a) E Sx A, Is [lı(s)]l2 ds S vd, and [10; ||2 S B for some B > 0. For a trajectory
S + IRd, and an unknown vector 02 such that for any
($1, .1.............................. SH aH), we define (0T) DH Ø(sn, an) and assume [| 1.
Linear MDPs can capture tabular MDPs by setting d = |S|||A| and Φ(s, a) to be the one-ho hot encoding of (s, a). In this case, we have [[](T)]|2 < H. However, we can scale it down to get [|o(T) < at the expense of scaling B up by H. We define O = {0 E Idd : |0]|2 S B), which contains 0z.
4.1 ALGORITHM
The algorithm, called PR-LSVI, is presented in Algorithm 1. At the beginning of episode k, it first computes the maximum likelihood estimate θ.,, (Line 3). Computation-wise, while the likelihood
4

---

Published as a conference paper at ICLR 2024
objective is not guaranteed to be concave due to the generality of t. efficient algorithms exist in certain common scenarios. For example, if f(x) = 1/(1 + exp(-2)). it recovers the BTL model (Example 3.2). In this case, the MLE objective is concave in 0 and thus can be solved in polynomial running time. Moreover, we emphasize that the reward is learned under wajectory-wwise features, which is different from the standard RL setting where it is learned under state-action features.
Given the MLE fr it next samples ,.,, from Gaussian distribution centered at θr,c (Line 4). Note that the covariance matrix Σ,- uses trajectory-wiss features (Line 16) which allows the random- ized Gaussian vector to capture trajectory- wise uncertainty of the learned reward. The noise aims to encourage exploration. Then, it computes the least-squares estimate of the state-action value function 0p.c. for each h E [H] and samples 0p... from a Gaussian distribution centered at 0p.,. (Lines 7-8). Similar to the reward model, the noise is added to the state-value function encourage exploration. We then define the value function Q2, and Ve, as
(s, a) == 0(s, a) Dr, + (s,ass)),,
Vi,(s) == max Q (s,0
(1)
and the function wi SSX R is defined as
Φ(s,a) T
if lf a) ())اs, Sa.
(s,n(s = p(s. a) (0((),))) ()) Tr...h) +11 -11-PP (H)-))))))(H h) af ||0(s, a) x7 S av
11-h
if f1 > au
where p(s,a) (av (lo(s, [|((s,))l,,, 1,, )/(av a1) interpolates between the two regimes to en- sure continuity. This truncation trick is from Zanette et al. (2020) and is crucial. It controls the abnormally high value estimates. Specifically, when [ø(s, (aosaaallss 0>>>>,1,, is large, the uncertainty in the
direction of o(s, a) is large, which makes the estimate dis, T Op.c. abnormally large. In this case, we have to truncate it to H/ h. Moreover, we note that the usual "value clipping" trick (i.e., simply constraining the value function within the range of [0, - h + 1] by clipping) cannot easily work here since it introduces bias to the random walk analysis, also pointed out by Zanette et al. (2020).
Then, the algorithm computes the greedy policy 5द with respect to Qtn.- The comparator policy कं is simply set to the greedy policy from the previous episode, Tp-1 In other words, we are comparing the two most recent greedy policies. This is different from previous work, which compares the current greedy policy with fixed comparator (Wang et al., 2023). Analytically, for our algorithm, the cumulative regret incurred by a for all E [T') equivalent that incurred by x for all f [T]. Hence, it suffices to compute the regret for one of them and multiply it by two to get the total regret.
Given the trajectories 7, and oř. generated by # and n/. we compute the expected absolute reward difference between the trajectories under the same noisy distribution of the reward parameter:
[[(0(T] (()))
01)]]
E
0,.0, (0r,
This represents the uncertainty of the preference between the two trajectories, and we make a query only when it is larger than a threshold e (Line 13). Intuitively, we only make a query on two trajectories when we are uncertain about the preference (e.g., the expected disagreement between two randomly sampled reward models is large). Computationally, we can estimate this expectation by drawing polynomially many reward models from the distribution A (0, - and computing the empirical average. The deviation of the empirical average the true mean can be easily bounded by standard concentration inequalities. We simply use expectation here for analytical simplicity. If the query condition triggered, we make a query for feedback on 7h, T/ and update the trajectory-wiset feature covariance matrix accordingly.
4.2 ANALYSIS
The theoretical results of Algorithm are stated in Theorem 4.2. The detailed assignment of hyper- parameters can be found in Table 1, and the proof is provided in Appendix B.
Theorem 4.2. Define 7 Vx + B2, which characterizes the difficulty of estimating the reward model. Set a, = @(rvd), or @(H))2 ox (d5/2 (16/2/3/222-11 or ov/2,, and X 1.
5

---

Published as a conference paper at ICLR 2024
Algorithm Preference- based and Randomized Least-Square Value Iteration (PR-LSVI)
Require: STD rr, dp, threshold c, value cutoff parameters ot, at, and regularization parameter X.
1: Let zo be arbitrary policy, Σo XI, Lo,n + X (vh [M]).
2: for = I,..., T'..., do
3: 0,, < arg max 0-
==1 Z,
4: 0r,
5: 8P.I + 0, Bp,,, + 0
6: for
1...., do
7:
Pp.c. + 2,1 0 0 i, V 1 (s
8:
Dr.ch ~ (f
9: Define Qi, and Ven as in (1).
10: end for
11: Set oi + {
T. (s) arg max, Qu (s, Vs e S, [H] and mे t -.-1-
Sample Tf oH and T, ~ t.
13:
Ze < (B ( ()((((( ((T)) -00-0)))0>>>
14:
if Z =1 then
15:
Query preference feedback or on {-..
16:
Σ, + Em-1 + ( o() ((((T)) - ((T)))
else
18:
Σ, x- Σx-1
end if'
20:
Dr. + 1 h + ol N (s) oln) (Ah E [H]).
21:
end for
Then, PR-LSVI (Algorithm 1) guarantees the following with probability at least 1-6: 6:
Regret, = Ō (eTaa/2 VT 15122 / 111122221)22 QueriesT = Ō (d"m2/62)
To further study the balance between the regret and the query complexity, we let c T for some B < 1/2. Then, the upper bounds in Theorem 4.2 can be rewritten as
Regret,- = Ō Queries = (
where we only focus on the dependence T' and omit any other factors for simplicity. We see that there is tradeoff in T between the regret and the query complexity - the smaller regret we want, the more queries query complexity is Ó(1), meaning that will incur linear regret if we don't make any query. If we increase 3 to 1 1/2. the regret decreases to Ö(VT) while the query complexity increases to Ö(T), meaning that the regret bound is optimal in T but make queries every episode.
need make. For example, when 3 0, the regret is Ö(T), and the
emphasize that this tradeoff in T' is optimal, as evidenced by a lower bound result established by Sekhari al. (2023a). Their lower bound was originally proposed for contextual dueling bandits, which is a special case of our setting. Their results are stated below.
Theorem 4.3. (Sekhari et al., 2023a, Theorem 5) The following two claims hold: (1) For any algo- rithm, there exists an instance that leads to Regret,- ((VT); expected regret upper bound in the form of E, [[Regeety] = O B) for some 3 > 0, there exists an instance that results E. [[Queriesy] 23)
; (2) For any algorithm achieving an
However, the dependence other parameters (c.g., d and H) can be loose, and further improvement may be possible. We leave further investigation of these factors as future work.
Although injecting random noise is inspired by RLSVI (Zanette et al., 2020), we highlight five key differences between ours and theirs: (1) Since the feedback is ruajectory-wise we need to design ran- dom noise that preserves the saate-ctioo-wiin wise format (so that it can be used in DP) but captures the trajectory-vue uncertainty. We do this by maintaining E, which uses trajectory-wist feature differ- ences; (2) Since the preference feedback is generated from some probabilistic model, learn the

---

Published as a conference paper at ICLR 2024
reward model via MLE and use MLE generalization bound (Geer, 2000) to capture the uncertainty in learning. This allows us to use a more general link function D; (3) We design a new regret decompo- sition technique to accommodate preference-basee feedback. Particularly, we decompose regret to characterizes the reward difference between mo and mp.: Regrety & Ei= (V, Vi) -V V where V. is an estimate of V=², and V. == Er-x? |E Φ(5), an) 'r,,] is an estimate of V under the real transition and the learned reward model. This is different from standard RL (Zanette et al., 2020), and is necessary since we cannot guarantee the learned reward model will be accurate in a state-action-wiss manner under the preference-base randomized active learning procedure for reducing the number of queries, and our analysis achieves a near-optimal tradeoff between regret and query complexity: (5) In every round t, we propose to draw a pair of trajectories where one is from the current greedy policy Ti and the other is from the greedy policy of the previous round, Tp-1- This ensures of is conditionally independent of the Gaussian noises at round f, which is the key to optimism (with constant probability).
feedback. (4) Our algorithms have new
Running time. To assess the time complexity of Algorithm 1, assuming finite number of actions?, all steps can be computed in polynomial running time (i.e., polynomial in d, H, A) except the MLE of the reward model (Line 3), which depends on the link function 4. For the popular BTL model where (xx = 1/(1 + exp(-z)), the MLE objective is concave with respect to 8 and belongs to convex set θg. In this case, procedure (e.g., projected gradient ascent).
use any convex programming algorithms for the MLE
5 A MODEL-BASED THOMPSON SAMPLING ALGORITHM
In this section, we aim to extend to nonlinear function approximation. We do so in based framework with Thompson sampling (TS). The motivation that TS is often considered a compu- tationally more tractable alternative to UCB-style algorithms.
5.1 ALGORITIIM
The algorithm, called PbTS, is presented in Algorithm 2. At the beginning of episode is, it computes the reward model posterior fr, and the transition model posterior pr. (Line 3). Then, samples P. and re from the posteriors and computes the optimal policy x. assuming the true reward function is r. and the true model is P, (Line 5). Here we denote V..p as the state-value function of π under reward function r and model P. Note that this oracle a standard planning oracle. The comparator policy nf is simply set to be the policy from the previous episode, TP_1, as we did in Algorithm 1. The two policies then generate respective trajectories 78 and 77- To decide whether we should make a query, we compute the uncertainty quantity under the posterior distribution of the reward: (r'(T?) r (T!'))))] which is analogous to (2) in Algorithm 1. We make a query only when is larger than a threshold e. Similar to Algorithm 1, we can approximate this expectation by sampling polynomial many pairs of and r' and then compute the empirical average.
Erpr'>p,. (I")))) ((T))))))r))))))))))))))))))))))
5.2 ANALYSIS
The theoretical results of Algorithm 2 should rely on the complexity of the reward and the transition model. In our analysis, we employ two complexity measures - eluder dimension and bracketing number. We start by introducing generic notion of elleee dimension (Russo & Van Roy, 2013).
Definition 5.1 (p--norm e-dependence). Let p O. Let X and y be two sets and d(-,-) be distance function on V. Let C X + y) be a function class. We say an element x E X is Le dedeendentt on {I1, (21,W2,... .2,...., Fnl C X' with respect to F and d if any pair of functions f. F satisfying > dd (f:)), f'x,)) S e also satisfies d(f(x,, (x)) S Otherwise, we say x is ly fn-norm e-independent of (n,
Definition 5.2 (lp- (e--norm eluder dimension). The normr c-eluder dimension of function class F C X' + Y, denoted by dim,, e, d,, is the length of the longest sequence of elements in X satisfying that there exists è 2 é such that every element in the sequence is Ep-norm e' é'-independet of its predecessors.
"Tiis is ensure that arg max, ()) can be computed efficiently.
7

---

Published as a conference paper at ICLR 2024
Algorithm 2 Preference-base based Thompson Sampling (PbTS)
Require: priors pp and Pr. threshold
1: Let xy be arbitrary policy.
2: fort=1,.... T do
3: Compute posteriors:
t-1 H P(s
Pr, (P
II
18, (g
==1k=
+ (01111 (((0))-r(r))))))) -r(r))) 2.
1-1
Pra(r) x (r)
4: Sample P: ~ Pp, and rt ~ Pr,--
5:
Compute m2 f- arg max, V (81) and कं t -p-1-
6:
Sample 7/ of and T. ~ Tz.
7:
Z4 <- "Er."",,..l(rr
r(7))
- r
8:
if 71 1 then
9:
Query preference feedback or on ( T.
10: end if
11:
end for
The eluder dimension is non-decreasing in i.e., dim,(F, e. d) S dim,(F, e, d) for any p S q. In the analysis, we will focus on é and f2-norm eluder dimension, which have been used in nonlinear bandits and RL extensively (Wen & Van Roy, 2013; Osband & Van Roy, 2014a; Jain et al., 2015; Wang et al., 2020; Ayoub et al., 2020; Foster et al., 2021; Ishfaq et al., 2021; Chen et al., 2022; Liu et al., 2022a; Sckhari et al., 2023a;b). Examples where eluder dimension is small include linear functions, generalized linear models, and functions in Reproducing Kernel Hilbert Space (RKHS).
The other complexity measure use is the bracketing number (Van de Geer, 2000).
Definition 5.3 (Bracketing number). Consider a function class F C X + R. Given two functions 1.u. a. X IR, the bracket [1, is defined as the set of functions f E F with 1(x) S f(x) I u(x:) for all x E X. is called an w-bracket if [[- -ull S w. The bracketing number of F w.t.. the metric || |]. denoted by N1 II), is the minimum number of w-brackets needed cover F.
The logarithm of the bracketing number is small in many common scenarios, which has been ex- tensively examined by previous studies (e.g., Van de Geer (2000)) for deriving MLE generalization bound (Agarwal et al., 2020; Uehara & Sun, 2021; Liu et al., 2022b; 2023). For example, when F is finite, the bracketing number is bounded by its size. When F d-dimensional linear function class, the logarithm of the bracketing number is upper bounded by d up to logarithmic factors.
not similarly It is worth noting that while we will employ both measures the model class P, apply them to the reward class R. Instead, we have to rely on the complexity of the following function class, which comprises functions mapping pairs of trajectories to reward differences:
R R= f F(T -(7)))))= (+) at), V = {sh, J e (0.1), ( ER] (3)
We have to use R instead R. because we only receive preference feedback, and thus we cannot guarantee that the learned reward model is accurate state-action- wise. Now we ready state our main results. The proofs are provided in Appendix C.
Theorem 5.4. PbTS (Algorithm
2) guarantees that
BayesRegret, = δ Te + H² dim, (P.1/T) VT. up + K- ddmm (R,1/T) /T 1x))
BayesQueries, δ min INTT iR dim, ( E2,) 152 x2.1R dimg R2, (2,)
where we denote up log(No ((TT))))))))))) P, )loo)) and UR (127) R, -lxx))
8

---

Published as a conference paper at ICLR 2024
Similar to the analysis of Algorithm 1, study the balance between the Bayesian regret and the query complexity by setting é = T for some 3 S 1/2. Then, we can simplify the bounds into BayesRegrety = = and
BayesQueriesy = Ō min 1 dimi (2, 2/2 128 dimg R e/2) 2
(it)
where have hidden factors except T and the eluder dimension for brevity. We see that there is again a tradcoff in between the Bayesian regret and the query complexity, similar to the one in Theorem 4.2. Term (ii) demonstrates that the tradeoff in T is again optimal, evidenced by the lower bound (Theorem 4.3). Moreover, term (i) further improves the dependence on the eluder dimension (recalling that -noom version is smaller than the 2--norm version). However, the T T-dependence is worse. It is desired to derive a query complexity upper bound that scales as Ó dim, (R, c/2)), attaining the favorable dependence on both 7 and the eluder dimension. We leave it as future work.
We emphasize that the Bayesian regret analysis Theorem 5.4 not simple extension of pre- vious TS works. We highlight four main differences: (1) The feedback is preference- based, which necessitates a new Bayesian regret decomposition:
BayesRegrely
ΣE
V
Σ
R
Viri
Tmodel
Teeward
Here Fmodel and Treward are the respective regret incurred due to model and reward misspecification. We highlight that Trwwar characterizes the misspecification in terms of the reward difference be- tween मे and n/. which different from the standard Bayesian RL. (2) Unlike prior works (Russo & Van Roy, 2014), we do not rely on upper confidence bounds (UCB) or optimism. Instead, we construct version spaces by classic MLE generalization bound. Taking the reward learning as an example, given the preference data {T,, ,t,
we construct the version space round as
1-1
V1 TET R
Eie (Pr(- T... Pr(-1 (... SB
1=1
where F; arg max, log Ei 7. -f.r) is the MLE from the preference data and / is tuned appropriately to ensure r* E V/ with high probability. We then show the posterior probability of and r* not belonging V; small. (3) Our analysis uses the tighter -noom eluder dimension, which is strictly better than the f2-nomm eluder dimension used in prior work. (4) We also equipped it with randomized active learning procedure for query complexity minimization.
Computation. The computational bottleneck of Algorithm 2 lies in the computation of the posterior distribution (Line 3). Prior TS works have used Bootstrapping to approximate posterior sampling (Osband et al., 2016a; 2023) and achieved competitive performance in common RL benchmarks.
Non-Markovian reward. Algorithm 2 can also be applied to non-Markovian reward (i.e., reward model is trajectory-wise) without any change. Here we consider Markovian reward for the consis- tency with Algorithm and for the purpose of using a standard planning oracle for computing an optimal policy from reward and transition model. While non-Markovian reward is more general, it unclear how to solve the planning problem efficiently even tabular MDPs. This computational intractability makes non-Markovian rewards not casily applicable in practice.
Extension to SEC. In Appendix C.4, we extend the eluder dimension Theorem 5.4 to the Se- quential Extrapolation Coefficient (SEC) (Xie et al., 2022), which is more general.
6 CONCLUSION
We use randomization to design algorithms for RL with preference-based feedback. Randomization allows us to minimize regret and query complexity while at the same time maintaining computation efficiency. For linear models, our algorithms achieve a near-optimal balance between the worst-case reward regret and query complexity with computational efficiency. For models beyond linear, using eluder dimension, we present TS-inspired algorithm that balances Bayesian regret and Bayesian query complexity nearly optimally.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
Both RW and WS acknowledge support from NSF IIS-2154711, J, NSF CAREER 2339395, and Cor- nell Infosys Collaboration.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pp. 176-184. PMLR, 2017.
Alekh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. Interna- tional Conference on Machine Learning, pp. 1220-1228. PMLR, 2013.
Alekh Agarwal and Tong Zhang. Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. Advances in Neural Information Processing Systems, 35: 35284 35297, 2022.
Alckh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural com- plexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20107, 2020.
Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for randomized least-squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6566-6573, 2021.
case regret bounds. Advances in Neural Information Processing Systems, 30, 2017. Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference Machine Learning, pp. 263-272. PMLR, 2017.
Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In International Conference on Machine Learning, pp. 1764- 1786. PMLR, 2022.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-345 1952.
Nicolo Basa-Bianchi, Gábor Lugosi, and Gilles Stoltz. Minimizing regret with label efficient pre- diction. IEEF Transactions Information Theory, 516)):1122221116 2005.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory reinforce- ment learning with per-epee-e feedback. Advances in Neural Information Processing Sys- tems, 34:3401-3412, 2021.
Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Hlmman-i--hhe-lopy in-the-looo: Provably efficient preference- reinforcement learning with general function approximation. In International Conference on Machine Learning, pp. 3773-3793, PMLR, 2022.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforeement learning from human preferences. Advances in neural information processing sys- tems, 30, 2017.
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple experts. The Journal Machine Learning Research, 13(1):2655-269) 2012.
10

---

Published as a conference paper at ICLR 2024
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in In International Conference Machine Learning, pp. 2826-2836 PMLR, 2021.
Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Con- textual dueling bandits. In Conference on Learning Theory, pp. 563-587. PMLR, 2015.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7288-7295, 2021.
Dylan Foster, Alexander Rakhlin, David Simehi-Levi, and Yunzong Xu. ristance-depende com- plexity of contextual bandits and reinforcement learning: A disagreement- based perspective. In Conference on Learning Theory, pp. 2059-2059 PMLR, 2021.
Sara A Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
Aditya Gopalan and Shie Mannor. Thompson sampling for learning parameterized markov decision processes. In Conference Learning Theory, pp. 861-898. PMLR, 2015.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1): 3487-3602, 2015.
Steve Hanneke and Liu Yang. Toward a general theory of online selective sampling: Trading off mistakes and queries. In International Conference Artificial Intelligence and Statistics, pp. 3997-4005. PMLR, 2021.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pp. 4607-4616. PMLR, 2021.
Ashesh Jain, Brian Wojeik, Thorsten Joachims, and Ashutosh Saxena. Learning trajectory pref- erences for manipulators via iterative improvement. Advances in neural information processing systems, 26, 2013.
Ashesh Jain, Shikhar Sharma, Thorsten Joachims, and Ashutosh Saxena. Learning preferences for manipulation tasks from online coactive feedback. The International Journal of Robotics Research,
2015.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-13418, 2021.
Michael Laskey, Sam Staszak, Wesley Yu-Shu Hsieh, Jeffrey Mahler, Florian T Pokomn, Anca D Dragan, and Ken Goldberg. Shiv: Reducing supervisor burden in dagger using support vectors for efficient learning from demonstrations in high dimensional state spaces. In 2016 IEEE Inter- national Conference on Robotics and Automation (ICRA), pp. 469. IEFF, 2016.
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2023.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforce- ment learning not scary? In Conference on Learning Theory, pp. 5175-5220. PMLR, 2022a.
Qinghua Liu, Csaba Szepesvári, and Chi Jin. Sample-efficient reinforcement renteeeeeeeennnnieeeeeeeeee learning of partially ob- servable markov games. Advances in Neural Information Processing Systems, 35:18296-11 18988-88888, 2022b.
Qinghua Liu, Pranceth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle: A generic model- based algorithm for partially observable sequential decision making. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pp. 363-376, 2023.

---

Published as a conference paper at ICLR 2024
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sam- pling for preference- beaeee reinforcement learning. In Conference on Uncertainty Artificial Intelligence, pp. 1029-1038, PMLR, 2020.
lan Osband and Benjamin Van Roy. Model- reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014a.
lan Osband and Benjamin Van Roy. Near-optimal reinforeement learning in factored mdps. Ad- vances in Neural Information Processing Systems, 27, 2014b.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
lan Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems. 29, 2016a.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via random- ized value functions. In International Conference on Machine Learning, pp. 2377-2386. PMLR,
2016b.
Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy. Approximate thompson sampling via epistemic neural networks. In Uncertainty in Artificial Intelligence, pp. 1586-1595. PMLR, 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
David Pollard. Empirical processes: theory and applications. Ims, 1990.
Nikita puchkin and Nikita Zhivotovskiy. Exponential savings in agnostic active learning through abstention. In Conference Learning Theeory pp. 3806-3832 PMLR, 2021.
Stéphane Ross, Narck Beiik-Barkkuudrrv,, Kumar Shaurya Shankar, Andreas Wendel, Debadeepta Dey, J Andrew Bagnell, and Martial Hebert. Learning monocular reactive uav control in cluttered natural environments. In 2013 IEEE international conference robotics and automation, pp- 1765-1772. IEEE, 2013.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-124) 2014.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Ducling rl: Reinforcement learning with trajec- tory preferences. In International Conference Artificial Intelligence and Statistics, pp. 6263- 6289. PMLR, 2023.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.00377777 2017.
Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Contextual bandits and imitation learning with preference-baae based active queries. Advances Neural Information Processing Sys- fems, 36, 2023a.
Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Selective sampling and imitation learning via online regression. Advances in Neural Information Processing Systems, 36, 2023b.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference Learning Representations, 2021.
12

---

Published as a conference paper at ICLR 2024
Sara Van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
Ruosong Wang. Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6133 2020.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard ri? arXiv preprint urXiv:2306.14111 2023.
Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in de- terministic systems. Advances in Neural Information Processing Systems, 26, 2013.
Runzhe Wu, Masatoshi Uehara, and Wen Sun. Distributional offine policy evaluation with pre-
dictive error guarantees. In International Conference on Machine Learning, pp. 37685-37712. PMLR, 2023a.
Yue Wu, Jin, Hao Lou, Farzad Farnoud, and Quanquan Gu. Borda regret minimization for generalized linear dueling bandits. arXiv preprint
2023b.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. The Eleventh International Conference on Learning Represen- tations, 2022.
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-based inforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 11118884-17944 2020.
Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proceedings of the 28th international conference on machine learning (ICML-1I), pp. 241-248. Citeseer, 2011.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5)11538-1566 2012.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Confer- ence on Artificial Intelligence and Statistics, pp. 1954-1964. PMLR, 2020.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. arXiv preprint arXiv:2305. 14816, 2023a.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason Lee. How to query human feedback efficiently in rl? arXiv preprint arXiv: 18505, 2023b.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. CoRR, 2022.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feed- back from pairwise k-wise comparisons. In International Conference on Machine Learning, pp. 43037-43067. PMLR, 2023.
Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. Advances in Neural Information Processing Systems, 01335377-353999 2022.
13

---

Published as a conference paper at ICLR 2024
A COMPUTATIONAL CHALLENGES IN RL WITH PREFERENCE BBSSDD FEEDBACK
For RL with preference-based feedback, there currently no algorithm that achieves sublinear worst-case regret and computational efficiency simultaneously, even for tabular MDPs. In this sec- tion, we discuss the challenges that hindered previous works from being computationally efficient. Specifically, the reasons are twofold:
(1) Trajectory-wise information. The feedback is trajectory-wise, meaning that we only receive formation about cumulative rewards instead of per-step rewards. In this case, there is no longer ground truth per-step reward signal. To see this, consider an MDP with two steps and a trajectory with cumulative reward of 1. Then, steps - could be that the first step has reward and the second has reward O, or both have reward 0.5. The meference-based feedback is strictly harder than trajectory- -wise reward feedback, and thus the same issue persists. This invalidates all algorithms relying on per-step reward information (e.g.. UCBVI (Azar al., 2017)) and necessitates leveraging feedback signal trajectory level. However, trajectory-lever approaches typically entail maintaining a version space via trajectory con- straints (Saha et al.. 2023; Chen al., 2022; Zhan et al., 2023a), and the computational complexity of searching within this version space is at least exponential in the length of the episode. Some works circumvent this computational obstacle by additional assumptions (e.g., explorability (Chat- terji et al., 2021)), which are restrictive and do not generally hold even in tabular MDPs.
cannot decide the respective per-step reward for the two
(2) Preference-bee based information. The feedback relies on a pair of policies. Standard algorithms based on a single policy become computationally intractable when adapting to this setting since optimizing over pair of policies simultaneously is qualitatively different. For example, Zhan et al. (2023b); Saha et al. (2023) use the idea from optimal design and need the computation or- acle: arg max,, [|E,,avn Φ(s, a) - EE..rr'''ss a) for some positive definite matrix A. Here || := x Ar, and Φ is some state-action wise feature. It is unclear how to implement this oracle since standard planning approaches relying on dynamic programming cannot be applied here. Addi- tionally, these methods also require actively maintaining a policy space II by eliminating potentially sub-optimal policies. The policy class can be exponentially large even tabular settings, so unclear how to maintain a valid policy space in computationally tractable manner.
These challenges motivate us to devise a novel algorithm using technique distinct from previous approaches. Our solution centers around the concept of randomization, which allows us to balance exploration and exploitation and thus enable standard efficient computation oracles (e.g., DP-style planning oracle like value iteration).
B PROOF OF THEOREM 4.2
B.1 NOTATIONS
We define some symbols and their values in Table 1. We have categorized them into four classes for the ease of reference.
The concept of covering number is defined below, which will be used to bound the statistical error of our algorithm.
Definition B.1 (Covering number). Consider a function class F. C X + R. The w-cover of function Í FF is defined the set of functions f F for which I|S 1 S w. The covering number of F w.r.t the metric || denoted by Nu,,F,1 II) is the mininum number of w-covers needed to cover F.
'These prior work typically assume trajectory wise feature Φ(7) for state-action wise trajectory 7. However, even when specializing state-action-wise features, these algorithms are still not computationally tractable in tabular MDPs.
14

---

Published as a conference paper at ICLR 2024
Table Symbols and their respective values.
Symbol
Value
(1) Error components
0, 0r.t
pp.c. 0p
AΣ 1 Ser (s'V 1 (s') ds'
Tra
0,, - 02
1 (Et-l (8 (, (V e, Es,,, (en+t((snttt)) su.raae)))
1211 [V,h- ds'
(2) Statistical upper bounds
6,
orv 2d log(dT///))
80ndlog 224TT (T5) + 168 4A
6
Vana
H(2 (er,g + Cr.n) er.n)// \/A)
ex
VImax Axd
OP / log (2HTT/8)
EP
log 12H A)V
B
2Vaax Vdlt VA
(defined in Lemma B.3)
+ 16dV max / - log ((au a1 (6A)
ép,"
( + 16dV / Le log (o1)
6P,"
(3) Value cutoff
(sn(s)
(ll(ss Te, (s))(ss))s,)11 $ sal)
(1o(s, Te, (
an
Lmax
2dH log
(+11)
af (4) Hyperparameters
or
G. (EP.n E (EP, EP.n + Ex) -1 (EP,E + EP., + Ex) -1/2
Op
au
15

---

Published as a conference paper at ICLR 2024
B.2 SUPPORTING LEMMAS
Lemma B.2 (Covering number of Euclidean balls). (Pollard, 1990) Let On == 10 E Rd |01 S B}. Then have
Nww, θB, II l12) & (3B/w)".
Lemma B.3. There exists X = (( + CP, + ex)) such that 6p, I Cp (recalling that x in the definition of cp.))
Proof of Lemma B.3. By definition, we have
+ 16dV Vic log ((av - (1.)62)
VX
16dV max Vie log(dA) log(au -OL)
VX
+ 16dV Vee log((A)) + log 2(EP,E + tp. + Ex)
VX
< + 16dV V log(dA)
-P..
Here the third equality is by the definition of a and au. The inequality holds by setting x Ologg(Er + CP + cx)) to be large enough.
Lemma B.4. It holds that a de,t = Gr p any E [T] and h [H].
Proof of Lemma B.4. By definition, we have
1P., + X4,b
Σ Φ(sinh ain)) (1 (1eA))))LA)))) E (V 8i, ai.h)
= ET
Sh11
+ - 1-1,1
(ettss) ds'
S. (i(ss)) (V [Venti(s)]] ds'
0p,,. ET1nh
(Siin anndolss, ann) + A1
= -1o mh(s') [v,+)(ss)) ds'
=Op,t.b Op
The following lemma is adapted from Zanette et al. (2020, Lemma 1) to our setting.
Lemma B.5 (One-step decomposition). For any t E [T), h E [H]. E S, A. and policy we have
(0r. a)
+ (p...)) (s)
= a(s (Er, + Ep,c, + Th,t TP.. Ae,t)) + V v.)+ (s+) s. a]
Proof. We have
((8,a) a) (0r, + Op,,,)) -T(s)
= o(s, (0., + Fp...)) - v(s, a) 0r ElVitt ss
=((,, a) (0.t - Br.)) + ((8 a) (Oreen- - Gras) ((s, (0.. 07)
+ o(s, a) T 0p,,. - EIV a).
16

---

Published as a conference paper at ICLR 2024
For the last but one term, note that o(s, a) 0p,
=0s,, a) 1 O(SLA, air VenVea
(eati((LNt1) scmman))) + a(s,a)) mern
=(s,a) T "Ii_IM
((8LA, (ih)) E
snt1
=(s,,)) T "E d(sLA) aw) [ phiis) (antio") ds') + a(s,a) mpn
a() / (1((8') VV ds' Ao(s,a) E I (illl') do' + ((s,a) m
= [vn+1((5) s, s,a] o(s,a) (e,, den a( ne,c..
Plugging this back, we get
((s.a) (Br, + BP.N.) - a))
= a)) (Or,
( - 0r,)) + ((8 a) (Op,t. - @pan) + a) ((o,a))(Or,. 07)
+ [VAN+i(S' (8) 8, o(s,a) de, + (18 a) 1/,t,h
= a) T + EPAA The + 17 Ae,)) E (i,++(''') V/= (s'
This completes the proof.
Lemma B.6. For any t E [T]. if Ze 0, then we have
( - - ((t')lls,, S (2v))(20,).
Proof. By the definition of Ze, we have
go 0 NO ((p(T=)) - (): -1)
E
((o(T() - p(T:)) o, (10 - un)
1/2
(( - -((T)) T -2,,5=11 1-11221
R
=0,5
E
u M (d(T)) (
-
(D.L)
= =,
F (D.La
|||||
We then apply Lemma D.9 and obtain
2tr 2 -x)
c 2 2.0.
π
(6(T)) - ((++)) (()))))))0)))))
20,
20r
[| -(+)))
Vir
Hence, complete the proof.
17

---

Published as a conference paper at ICLR 2024
B.3 STATISTICAL UPPER BOUNDS
Lemma B.7 (Gaussian noise). Each of the following holds with probability at least 6:
foralllt 1. | 6rg for all E [T],
2. [|P,,alllaa-a S for all E [T] and h E [M].
Proof of Lemma B.7. It simply follows from Lemma D.3 and the union bound.
Lemma B.S. Fixt E T.. It holds with probability at least 8 that
(d(T)) v(T))) (0: - -0:=)
- T (0: -r:) 1688"
)(
E
Here the expectation is taken over the randomness of sumpling T. and T from my and ny, respec- lively.
Proof of Lemma B.8. Let Gg denote an w-covering of Og with respect to || ll2 for some w > 0. By Lemma B.2, we have |OBl (3B/w)". Moreover, for any s E 1]. by Cauchy-Schward inequality, it holds that
((T?) T (0+ 1) | - 10 0 s 16B
Then, by Lemma D.4 and union bound over θg. it holds that
(o(7.) - -(T))) _ (0z - =
( ((+))) (0: (0) do
(4)
for all Ø E θB with probability at least 1 Now we consider an arbitrary E OB and let Ø E θg be the closest to f. Then, by triangle inequality and Cauchy-Schwarz inequality, we have the following two ineuqalities:
(0(7g) o(?:)) (0) - 0))²
<2( -(T))) T (0: (0:00
+ +2)(0(T?) - o(T))11110 - -013
s 22 (0(T)) d(7))) (0=-0)
2
+ sww
and
(0(79) o(T!)) T (0: - (
<2(()( o(T!)) _ (0: - 0) + 2l( - 0
< (0(T.) o(T!))) (0) - 8) &w2
18

---

Published as a conference paper at ICLR 2024
Applying these inequalities and (4), we get
(6(T)) - o(T))) T (0 - -o)
(d(T)) o(+:)) T (o: - 0) + 8w+t
E (d(T)) a(!))) T -0)= (123B")og((BB(40)) - -8W2
(Ó(Tg) o(T!)) T (0) 00)² 128B""log(3BB)(ub) + 40w2t
(0(T)) ((!))) (0) 0) +168B"d
where the last step holds by setting w = 1/t.
Lemma B.9 (Reward estimation error). It holds with probability at least 1- 8 that Il S Cr.n for all t E [T).
Proof of Lemma B.9. Since de. is the MLE, by Lemma D.10, we have
Σ E 12
d (r(1122 8,, Pr (-172: (2..)) < 10log (ND((2T) RR (1bo)/
(5)
with probability at least 5, where R denotes the set of probability distributions of preference feedback and Pr(-) denotes the preference feedback generating probability. Now we upper bound the covering number of R by the covering number of O We notice the following:
Pr (o - (0,.)))))..
sup ,,
Pr
( T 00) & ((((79) - -((r1))T0r
sup ,
S 1
sup ,1,
(0(79) - o()+)) T (0; 8..)] -
SR
sup []x(T0) o(+))))) )121100 - 0.ell2 +,r!
<2R 11000 0r.el12
where the equality holds since the feedback o is binary, the first inequality is Lemma D.1, and the last inequality is by the condition that [|x()) - for any trajectory т. This means that an w-covering of the space of parameter 0 implies a 2wm -covering of the space of the probability distribution of the preference feedbacks. Hence, (5) can be further upper bounded by
E dr (Pr (-1 (Pr(-11,,7,) -. T
Pr (-1 7, -2 0(.)))))
< 10 (2T) RR RI 11)
< 10 (N(R/(1T), 0B, 112)
< 10d
(6)
19

---

Published as a conference paper at ICLR 2024
where the last inequality is Lemma B.2. For the left side, note that
E dv
(Pr (-
T 03) Pr (.1 7 T. 7.17, 0r:))
((())) 8:) 1b ((d(7)) - -((:)) (....) )
+
(d(T=)) -29)-6(110 p(T!)) (0:-0..) |
(ő(+)) - (T!))) 0 (00-0ss) 21xx Bld="1B'
4
with probability at least where the first inequality is by Lemma D.I and the last inequality is by Lemma B.8. Furthermore, we have
(0(T)) - a(+2)) (o: - 0net) ) 1
-rss)
(0 0..1) Σ ( (((T)) - o(T!)) (0: - -B..))
(0; 8,,3) I (0+ - 0,,)) - (0;-0.z) T a 00 - -r,)) 2 | -AB²
(8)
Putting (6), (7), and (8) together, we get
[. I 80kd log (12BT(R6)) 1o8BBBdoo((3TB/0) - 4XB2
with probability at least 28. Adjusting å to 6/2 and taking the union bound over & [T] yields the desired result.
Lemma B.10 (One-step transition estimation error). Assume the events defined in Lemma B.7 hold. Then, the following claim holds for all t E [T') and h E [M] with probability at least 1 - 6: if max, V (s)4 < Vuaao it holds that [ E. 1.A S EP..
Proof of Lemma B.10. By definition, we have
[лp,,, 1.4
Σ ((8.nn ai (Venn1(BAAH))
- E $1.111
[Ven+ (8t Si,hs an,1]]
Towards an upper bound of the above, we will conduct some covering arguments. To that end, we first derive the upper bounds of norms of Br,, and &.....
Bounding the no-no of 0r, and Ppt For Or... applying triangle inequality, we have 10, = Ils,, + 10,, I Ilsr, + B. For ||Er, we have
& ll / (TT 2 S//ee s VIG.AIlE.- //L.:alla.-/llcolll.... S Ver.e IlEr.ola/VV
where in the last step applied Lemma B.7 and the fact that [|E+, I || s 1l5r.ll2/vA. This implies that ||&r.el2 I er.e/ / VĀ, and thus, ||0,.lla S G..g/ ev.//V+ B.
For &r,ch, we have l|@r,aull2 S IlEr.,,ll2 + |l0r..al2.. For IlEr,,,ll2. following a similar argument as above, we have
A S In S Vep.e IIe..alll
20

---

Published as a conference paper at ICLR 2024
which implies that 1E,,,,0ll22 I <p.5/ V, For |10p,enll we have
0
E, 1/2 1 21 111
1/2
(88ih ant (8
2
1/2 | 1,b
l12
1 1.
WVX-I. Vt.
SVX-1. VL. Vmax
11 (i,)),
Vinax Vdt
where the second inequality is by the Jensen's inequality, the third inequality is by the condition that max, (e)( I Vmax, and the last inequality is by Lemma D.7. Putting these together, we get 00, S cr.e/vA /oe//VV Vmax vdllVA.
Covering construction. struction. First define
With these bounds in hand, we can now proceed with covering con-
(0,00.2(5,,)
[ a)lls S an p(s, a) ((s,a)TTp + +1 ( h) or < l|o(s, a)ll= S au -
(ssaa)Tos
= (() 0, +
if ||o(s, a)ll av
Vo. s(5) = max Q0, ((,
where p(8,a) == av-1a( This definition aims to mimic the behavior of Algorithm Then, we define the space of parameters as follows
u = (0. 0). E) |10.112 s B + G.g/ /.../VA, X, |10p|2 I (Vmax dit + cp.s\vA,
|E S vd/A, E= ΣT. E z 0, xp.x S Vmax
Clearly, Dr,e and Bp.c. satisfy the constraints of 0, and 0p. Moreover, |E S Vdl Ez S vd/A X, and thus ) satisfies the constraint of L. Hence, we have (O,,,, pp 2x-1) u.
By Lemma B.2, the size of an w-covering of l/ by treating as subset 2R2ddd can be bounded by
2d+d
3 (B+Ce//VA)) (Vnax Vit + cr.e//AA++ va/A) +V3l/
21 s
w
We denote the covering set by U. We will write N = N (w, || (12) for simplicity when there is no ambiguity. We note that it is possible that not points in 27 belong to U. However, we can project all points to 14 so it becomes 2w-covering of U. We will omit this subtlety.
Covering argument. For any (0,, Op. Σ) E U. we define
Fi,0 E. == Vo..pp.( EVVe,... 8i,h a.
21

---

Published as a conference paper at ICLR 2024
By construction, have 00..0.0p. xl 2V it is max -ubgauusuaa conditioning (8i,,, di,h). Hence, for all (0,, 0p, Σ) E U, we have
Σ ((si aiA B1.
32V max
(dlog 1 (1+ + log(N/6)
(10)
with probability at least 1 - 8 by Lemma D.5 and the union bound over Ü. Now consider an arbitrary tuple (0r, 0p, Σ) l and the nearest point (0,, 0r, Σ) U. Then, we have
MM 1 WM
(5 0i,h 02.0)
1 1
1.b
(8ihh, 0i.h 0 0,,
D(si,h ai (..0 2,,,00.5 -.0.
11-1,
(( 0i.h (...
| a.wh))x) max 10,00 It 3p,
Ey 1.
t. max 01,00 - 2, 20000pp.511
1.1
where the last step is by the fact that [ a. a,n))l,, I VA-T. Observing the derived upper
bound above, the first term is already bounded by (10) since (θr, Gr, Σ) E U. To bound the second term, we note that, by the definiton of 01,0,,0, and Er
max 11,,0,00 0r.
Vo Vr (s) Vo,0n.5(s)
8
=2 2 max
max Q0, a) max Qi E(
2 max Q0. 26,6p.5(8,a))
We assume w < (or - a1.)² (and this will be satisfied later when we specify the value of w). Recall that we have three cases in the definition of Q0.00p. (s, a) (see (9)), and will refer to them as Case L, Case M, and Case U. There are in total 6 possible combinations of cases for the pair Qe (s, a), Q8 (ss, a). and we will discuss them one by one below. For the ease of notation, we denote (ss, a) and ((s, a) as shorthand for Q0.,rr. a) and (s..a).
(1) Case + Case U. This is impossible, because, in this case, we have ||[/|| - ||llls >
at - al, but we also have || - || = Iv Ed VoT & V (Σ ΣjSl 5
/ Vloll2/2 [ Elle|lelle & y < au ap
(2) Both Case L. Then immediately have
[Q(s. ((s,a)]==((s... (0, (0, + 0p Ô, -0pp (1ob(s,)) (10. 0.112 + 110p -02l2) 2w.
(3) Both are Case U. Then we immediately have
1Q(8, a) ((s, a)l = -/0(s,0) a) T() - 0.) s (o(3,))]l2 110, - - < w.
22

---

Published as a conference paper at ICLR 2024
(4) Case L + Case M. in Case L. Then we have
Without loss of generality, assume Q(s, a) is in Case M and @(s, a) is
[Q(s.a) ((ss Sp(s, ((s, a) T (0. + 0p 1p--0-
0. - -6p)
+ (1 a)) ((8, a) T (0. + 0p) - (H h)
<p(s,a) 2w + (1 - p(s, a)) max
Recall that a(s,a) au _ll))e(s,a)]ls so
p(s, a) = | an Futhermore, au-aL
au-al ||0(s, a)] OL
|0(s, - | a a)}ss + ((((s,))l on
1 - p(s.a)=
aU aL
aU aL
|lo(s, a)({= - ( VØl V Φ TEΦ
ar 01
av az.
10T (2 حهوع
V E112110112
0U ap
au 00
du an
where the first inequality is by the condition that Q is in Case L. Inserting this back, we get (Q(s. V
(s,,a)) S 2w +
au-oL
(5) Case M + Case U. Without loss of generality, we assume Q(s, is in Case M and @(s, a) is
in Case U. Then we have
(Q(s.) a) as) Sp(s, a) (0(s, a) ( (0. 0r -H) + (1 p(s, - h) (H h)l =p(s, a) (o(s,a) a) T (0,
2V w0
Op (H h-)] pls,a) 2V 5 av en.
where the last inequality is from
p(s,a) = au - ||((s, au [1 ax ||0 a)}s= + 110(5,
au oz
ov - on.
| - a1((,,)) VØTEO- Io Σσ
au - -QL
au a2
Φ ( -1
-1 E121110122
VW
S au al
aU aL where the first inequality is by the condition that @ is in Case U.
QU aL
(6) Both are Case M. have
Denote p(s,a) = au [0(x,))ll and p(8, a) aI
ou (asaall au aan
Then, we
(o(saa)-pss a)l 116(,, a)ls - 11(8,
a>1b> 11((,,))1x>)
v VIliIlalEE E|1
V/w
au aL which also implics 1(1 (11-p(s)) p(s,a)) - - (1-7(s, a)) 5 ag-a Hence, we have
QU aL
au aIL
vi
(Q(s,a) -s(,,a) - p(s.a))(s a) T T(, + 0r) p(s
0r)
+ +1(1 - p(s, a)) o) h)) - (1 ((s. +p. (0,, a(s,a)o(s, a) T(0 +
< p(s,a)((s, (0,
+ |(s,,a)((s a) (0. + 0p) (l. a) (0. + 0r)
+ (1- (1-ppss a)) - h) - (1- ((s. h))
<2w Vmnx Vw H H
au - al au ap
23

---

Published as a conference paper at ICLR 2024
Putting Everything Together.
Taking the maximum of the six cases, conclude that
2V max Vw
[Q a) ((s,a)) S 2w +
ov - 01
We set
01 -a1. 2: 2m
and obtain
[Q(s, a) ((s,a)) 2 CUU 0L
3
+ i b
S
21V
where we leverage the condition that on,, oU S 1. Thus, we have
00.0 2r. max a(s - ((,
-
The covering argument is now complete, and we can use it to derive an upper bound for | I| To that end, note that, for 1/,,,, there must exists (0,, 0p. Σ) E U and its closest element (0r, 0p, Σ) E 22 such that
Final Bound.
M 1x 1.
(sLh, (VeAtI(OLAAI))
11 sin, (LAg
86,612
(8 as d1,1)
( 0.,1)
p(s,n, ais.,..nn(( x.0.00..)
where the second term is bounded by
(in.,,ain)( - -
( (.n.,, -1000 E-
A- t. max 10.0000.0 T.
<6/VX,
and, applying (10), the first term is bounded by
((sih di,h 0.
1.
32V
dlog 1+ x
+ log((//))
+ tr.///\V) + (Vmax Vot te..))//+++ +
dlog (1+4) + dZ)
321/2m
w6
12V2 "2V2x*""
12 (B+
(Vmax v + + va/A) (av 21
-V max 32d (1+1)= 33(2dd + do)
24

---

Published as a conference paper at ICLR 2024
where the second inequality is by inserting the upper bound of the covering number N, and the equality is by inserting the value of w. The last line looks complicated and we can further simplify it and get
(8i,br 0z.b (. 1.
111
m2V (1 (
en./vv) + (VmaxVdl (VAA///V///A)))))))))() (av a1)dA
<16dV max
log
Plugging these upper bounds back, we obtain A.P.AAAEE--1.
12V 2)
c..//\) (B+ (av a1)5A
+ (Vmax Vet cp.g\vA+ vaja)
16dV max
log
Applying union bound over all [T] and h E [H), the upper bound exactly becomes P.,.- Further invoking Lemma B.3 finishes the proof.
Lemma B.11 (Boundness of value functions and transition estimation Error). Assume the events define in Lemmas B.7 and B.9 hold. Then, the following holds with probability least 1 - 8:
1. max,,a (8, a)l S Vmax for all E [T] and h E [M].
2. 1 E I for all E [T] and E [M].
3. MANllE for all & [T] and h E [M).
The first statement implies max, V (s,( & for all t E [2] and h E [H].
Proof. We prove the three statements together by induction.
For the first statement, define Vimax,h (Hl - h + 1)(1 + (er.g + e,,r A)), and we will actually
show that maxs,a (1, a) Qi (s, a)l < V Vmax, in the induction, which immediately leads to max,,a Q2, (s, < V Viaanhh + (H + 1)= V Vmax.
Base. For H,
directly apply Lemma B.10 without the transition argument, which also
leads to the desired upper bound of [[ |Ix._,,.. Moreover, the upper bound of trivially holds. For upper bound on the value function, immediately have
Qu, a) - Qu (s, a) = lo(s, a)T (O., 0:) z (lo(s, a>لاs, ,, 1l0., - -0010111 01
by Cauchy-Schward inequality. We note that [, 0))1,, S V and 110,, - 0,11x,-1 S I1r,e
nh.ell.... ||,r,llE,_, + |lneells.. S 6r, Cn.. Hence, have Qu.n(s. a) (s. s (6.,5 + fnn)/VX V.ax.H-
Inductive Steps. Now consider h H. By induction hypothesis, have max,, IV (s)+ s Vmnx- Thus, we can apply Lemma 1.10 and get || lIs, 1.6 S ep,n- For the upper bound of by definition, we have
=11 / (((5 (.') ds'
| M
SVĀ //
do'
VVmux Vd =
25

---

Published as a conference paper at ICLR 2024
where the second inequality is by ||2-11,612 S Vλ, and the last inequality is by Assumption 4.1.
For the upper bound on the value function, consider the following three cases.
Case 1: |,(s,, ب)لxI; 01. We apply Lemma B.5 and get
(0n, a)
+ +p...) (2))saa
((s,,a) (Er, EPAA + Nee + metch (c,)) + IE [V (4+)((8)) - v s.a]
s $10(s, a) (aaaa)"()) (Er, + m+ti + a)) (Ep,,A + upan deni + E [ 1 - 1 8.a]
6²
S(Erg + +r.n) V |1
EPmn (EPLe ep.m + Ex) + (1H (H-1)) + (er,e + fr.n/vA)
S(G,, + G,n)//A+1++ (H hh((1 (Ee, + Gnn)/VA)
-(H - h+ 1)(1+ (fr. + G.n\/AA)
-Vmmx,h
where the second inequality is by Cauchy-Schward inequality, Lemmas B.7 and B.9, and the induc- tion hypothesis. The third inequality by the condition that [ a) 0)||,,,,,, S or, and the definition
of aL.
Case 2: 16(5, (08,,,))==,,,, > au.
We have
Qe,(s, (aals,a)-Q.,, ()) a)
S10(8, a) 0r, + H h - (x,
=|p(,, a) (Sr. + mme) H - - ((s,a) Q%(s,))
((r,, + (rn)/VA + (H 1h+
Vmmax,h
where we used the fact that 0 - a) < 1 and 0 s (7,sa)) S H - h + 1, which leads to 0, - (% 1.
-(H - 1) S (() TO;
Case 3: an < 1|0(s, (f(ss,a)l a)1|=)) s av. Denoting p = p==(s, a) for simplicity, we have
(c)(s, - (Tssaa)
a)) (Or,t + -p.,,) (,(s a) + (1 p) o] a) 0,,1 + - -
Sp(H - h h 1) 1+ [1+ (cr,g + G
+(1 p(s a) (E., + n1,)) + H + o(s,a) (iss,a)
Sp(H - - 1) 1 1 (er,g + vv/) + +(1 -1- p) ( + tn.) + (H - -h+1))
SVmaxx,
where we have used the similar arguments from Case I and 2. Taking the maximum over the three cases, we conclude that
(s, (s, a)l S Vmax,h
which implies max,,a 1Q,, (8, a)l Vmax-
Lemma B.12 (High probability bounds Sounds-summnn summary). All the following events hold simultaneously with probability at least 1 8:
1. ||Er,ellz,_n for all E [T]
2. [KEr,AN||E in S Sor all 1 (T) and h E [M].
26

---

Published as a conference paper at ICLR 2024
3. |Ma,ll Er,y for [T].
4. |I 1 I CP,y for all E [T] and [H].
5. DAGAlEELLA & for all & E (T) and h E [H).
6. Q a)l & Vmax and [V (s) & Vmax all (s,0) ES A [T], and [M]]
Proof of Lemma B. The first and second statements by Lemma B.7. The third is by
Lemma B.9. The last three are by Lemma B.11. Then we take a union bound over all of them. 0
B.4 BOUNDING REGRET
We define
H
V = E Twem
Σ
(sn, an) T Orst
Lemma B.13. Assume all events listed in Lemma B.12 hold. Fix t [T]. Then, have (V* vi) (V-V S normal distribution (i.e., (0, 1))-
with probability at least (-11) where denotes the CDF of a standard
Proof. Define the indicators
(s) =1 |0(s, x ((S))l sai). (8) =1 for < |100, x (1)) in S sau).
(s) =1 ||*s, क (s)) avy
We note that they are independent of the random noises at episode and only depends on the infor- mation up episode / Then, we can decompose V V
V V.
EE (s1 [si(s [Qi Qu,(s1. (s)))
E [Qi(s), - -()())))))))
E (Q1()) Q1))))
+ E (51 (Q1 T (s1) (s, xt (s:)))
+ E (s) (Qi x" (s1))
(s:)))
Tr. + TM, +Tp-
Now we establish upper bounds for each term. For Tu, we have
(si) (Qi ""
7" )
=E (s1) ((((s))='sss)) p(s -5 (s1)) Br,, - (H 1))]
= (si) (Q1 6(8,, (s1)) 0; o(si, (81)) (mre + Exe)) - (H - 1))]
<E ( (11 (nh +
where the inequality holds since
7 (81)) (s1)) - (Hf -
= (0: EE(V3 (52) sn, x (s1)] x (s1)) (H 1) s
27

---

Published as a conference paper at ICLR 2024
For TL, we have
E (si)) (Qi(s), (,, x (s:)))
= E (si)s) (Qf(,, 0(5 T- ((1)) (O.. + pp.,,,))]
=E (01) (-0(s), (T (s1)) (E., + fp... + The nP..1 )x11) + E [22 Vez(s) 81, ग (s)))
where the last equality is by Lemma B.5. For TM, have
E M2 (81) (0((01==*(x)) - (()
=B (11( 1 ( (()1) Q1()) (H1 (s)n (0,, + (P...))
+ (1--p(s, (s1))) (()))) - (( x (81)) 02,1 (H - 11))
SE E Mi (1))) (1 (s1)) - (s1)) (Er, + fP..1 + 7e + 7,,,1 - 21,1)
+ E Vi - Ve2(s') s1, 51, (si)) + (1- = (s)))) (- (nr + Enx)
where the inequality is by similar arguments as in the case of Tu and TL. So putting TL, Tm, Tu together, we have
V V
Ui + (s))( p(81, - ((11))) (-i)) (-0(s),="<s))) (nr + Srx))
< E
((1))
+ (s)) + (s) (- (s1 n (s1)) (G., + EPA.1 + The + m..1 - d1.1)
E (52) Ve2(6') 81, 11, (s1i))
Keeping expanding the last term, we arrive at
H
h-1
II LMM.(()) ( (-M(h) (Er, (n) + T2,)))
V. S
E
(Mi
1=1
h
II (MS))())
(-o(s).aa) an) (Er. + Eppen + The + Mp - sen)))
h=1
h-1
h
II (M) + +II LMM,(())) (-o(sn) an) (Er, + +,,)))
UMi (SK)
7N0
i=1
1=1
h
LM (8))
(-o(s), an) (Er.e. + Meae - denu))
+
1=1
H
=I(-d)) (Er. + +m.) +
( " (EP.ch + mp.. de,1))
h=1
28

---

Published as a conference paper at ICLR 2024
where in the last step defined of and @P., as
H
h-1
h
II (M, + II (80) 0(sn, and
E
UM (sh)
1=1
2=1
II
LMM
P
E Trust
i==1
Now we also decompose Vg V and get
V
V
olsk: anh
(0., - 8;)
E
Σ
(ss and
(Er, + ne,e)
Tm
1=11
(0,)
(Er, 7e,e)
Combining the decomposition together, we obtain
(V* (V) Vol)
meah )an) + TT (Er, Th.))
(-d;) (Erse (Er,c + Th,1) +
v1 (EP,,, T
h=1
H
(3, )t) (Er, + nc,e) +
xp)N) (EreAn + was - Aca))
h=1
<11o: o'1ls, 1 -llirlll + (ō: - TT,t
10p a (Ilpaall,, in + |enale, In)
Σ
h=1
S110:
o" 0'11ss 1 F.m - (ō: T +
Σ
E.l. V H(Ep., + tx22
Σ
op.n
T
h=1
1=1
= 10 0² 001|,1-1 Cr.
(5r - -0-)d")a Er,1
(a)
H
H Σ
+
min
1, 1 12
H(rr +2)2
s Epp. h=1
h=1
(b)
where the second inequality is by Cauchy- Schowrr inequality, the third inequality is Lemma B.12 and Mauchy-Schwarz inequality again, and the last step is by the fact that | 1| $ 1/1 $ 1.
For (a), we note that (ō. - TT, ~ NNO, of 0= So by setting o, 2 cr.m we have (a) < 0 with probability at least F--1).
For (b), similarly, note that Σtt of T SPAAA N10 1 1 So by set-
ting op / H((p,, + Ex)=, we have (b) < 0 with probability at least F(-1).
Conclusion. Finally, we note that (a) and (b) are independent, so the probability that both (a) and (b) hold is at least F2 (-1).
29

---

Published as a conference paper at ICLR 2024
Lemma B.14. It holds that
H
i (Bc,)) S Tmmax-
A=1
Proof. Denote 01, (8(,).)). Then, we have
(s(()))
ΣΣ
1
10 (L at.
=
[10(8,, (eNs,, --a.h
Oz
h=1
T
min 11o(s,,n, S 11
1=1
T
2d
Limax
a
where the second inequality uses the fact that on < 1, and the last inequality is by Lemma D.6.
Lemma B.15. Assume all events listed in Lemma B. 12 hold. Then, the following holds
Σ (V,- V -0-- (V. --rii) -ō (VmmxxLmax Vmax HTT
+ (4ng + (a) (VaT + Lmmxx + VHT + CTVT
20,
+ (EP,s Epn +Ex) (HVdT + Lmax + HHT)
Proof. By definition, have
(V.- vol) (Ve (V--V') -vmi)
Σ
az) oif (s1,
Σ
Σ
o(st, an) (Br,t 07)
h=1 smaapmti
By triangle inequality, we have
H
E (s,,))
(S)) (s1,
((sh,an) an) (Er,e + ne.))
t=1
$1.a1
1=1
9h,0g mn
+ 2V
E
Le (s1.))
t=1
For the first term, conditioning Lt,1 (8t,1), we have
(s,1)) a1) (Or.t + 0p,,,)) - Q ($1, (s1,
E
T
T
E
a(sn)an) (Er.e Thi))
+ 2V
E
LC (st.1)
Aml 1=1 c
[im St SEaa
30

---

Published as a conference paper at ICLR 2024
Applying triangle inequality again, get
T 07 (01,aa))
I
(T + 0p.,1) ((a))--2ff
ΣΣ
@(sn, an) (5r, + nr,))
Sh.0a
T
+ 2V mmax
E
Le (s1.1)
LE
(91())))) (o(s)))(((s),)) (0(s), (0,, + 0p.1.) Q (s,,
Applying Lemma B.5 and the triangle inequality, we get
T
T
H
E
V(2(82)
122h 1 (82)
E
d(sh, and (Sr,t + Nr,))
h=2
m
E
o
(EE, EP.111 &p..1 The + 7P.,11 Ae,1)
E
ai),, + m..))
#1,01
2V
((.()11))
max
$1,01
(1) (Or, + (p..1) Q7 (s1,
$1.01 1
Keep expanding the first term, we get
Σ (V. Vzl)
(Ve vz*)
H
T
<
2V
E
I. (se.a))
LC (L.n(se)) (0(s), an) (0,, Dp,..)) Q (sn, ]n)
E
(n) (3) (Er, + mar))
o J(sh an) (Ep.. (n) + TP.. dea)
E
Sh
=: Ti + +
bound each term separately.
Bounding T By Hoeffding's 's inequality and Lemma B.14, we have
Ti 5 2V max
LE [..n(s + 2V
2V max V log(1/8)
HT
HT V.
$ 2mmax
Tomax +
2 1og(1/8)
with probability at least 8.
31

---

Published as a conference paper at ICLR 2024
Bounding T2.
By definition and Lemma B.4, we have
T
Σ
LEn(oLnD (oss, an) (Er, The + 0 + EP,c + mea + de, + (r,,1))
T2
h=1
[=1
The (sn; an))]
T
Il (Ln(( an) (0; + + 0% (sh, an)
(sh, + T (8h, (n) mes) + ( an) + mpsh + Se.h))
H
T
Σ
(la(oen)) b(sn, an) (0; + Op.en)) (p 2h (on, an)
E
1=1
+ |lo(s an M|ss (Ils,,ell + lMnelllnn))
+ +lo0(sn an),,,n)ll,,,,.. (IEEp,aNlEENin + (lleaaa I + [1AeillZ (A)ilBern))
We note that (Ø(sn, Tn (0T + (f S Vmax and 12 (sh, and S Vmax- Moreover, we have (ld un)llx, 1/VA and (lo( an) an)llxz?, S 11/V.. Apply triangle inequality and inserting these upper bounds back, obtain
T Σ
EEhloen (o(sn (0; + +p Q (sh, on))
T2
h=
[=1
LE Dfalse)))ldsss (n)l(((s,,))))) an)ls (1 + lerelll .)
E
1=1
8h.0p m
(r,n),))ll((ss an)))ss,,)))))))) an)ll,,,, (AAl,,,.l + AMpeall + Me
E
h= I
t=1
Sh m
< 2V max
ΣΣ
E
h= t=1
H
T
(suNNee + e.n + Ep,s t + Ex)
1=1 shaan
H
(2Vinxx + eng + fr. + EP,E + EP.n +
E
V
1=1 1=
We notice that (+) can be bounded by Hoeffding's inequality and Lemma B.14, as we did similarly for Tı:
HT
(+) < Lmax + V
2 log(1/8)
Hence, we have
< [Imax + v HT
2V + G. Grn + CP + CP + C
T2
(8)(1
VA
with probability at least 8.
32

---

Published as a conference paper at ICLR 2024
Bounding Tg.
By definition, we have
E (d(T)
- (Cr. + ne,e)
T3
E
By Cauchy-Schwar inequality, we have
T
E
E
((()) - o(+) o(t)
15- (IEnellla + lImallEe.))
5(En,5 + c2.71
(d()) )()) E Tout
E
E
FiuT!
1=1
Since (|p(T) - ((F)
S 2/ V/VA A, by Hoeffding's inequality, we have
27 2Tlog (1g(1/6)
s (er Ex,
Σ [((T) - o(F)
+
1
=(crst + Cxm)
Σ 4e ((T)) ((F)
+
Σ
(1 Z,)
O(T) o(F)
+
27 2T log(1/))
1
a
1=1
i
(i))
To bound (i), we have
T (i)
Ze min 2//2, | - ,())
x
1=1
T
4/1, [T() 0(7)
T
Zi min
t=1
1, ||(()) - o(F) 12
2
T
Z min
1
1=1
A 4T
52
T. 2d 2d
X
where the last inequality is Lemma D.6. To bound (ii), we have
T
(ii) =
Σ (1
20) ((F))
t=1
< Σ (1 Zi) (200)
t=1
SeT (2())
where the first inequality is by Lemma B.6. Putting the two upper bounds together, we have
47
2T (og(8/)
To I 6.g + ct,))
2 T 2d
+ (TTT/((20) +
A
Bounding Tı.
By Cauchy- inequality, we have
T
[oo(k, an))l, (IEPAAAlEEE + IMP.aalll + 11 ( Emn.))
T4 <
E
Sh.0n xxp
< <(EP.S EP,n tEx
E o
[0(sh,an)lls) an) an)ls,
A=1 tmm
33

---

Published as a conference paper at ICLR 2024
Since ||o(s), an)lls,h I 1/vi, by Hoeffding's inequality, we have
H
TH log(1/6)
$ EP + EP ta)
|10(3) an)ll +
21
=(ePs + Pn ta)
H
T
min 1/V2, |l0(s an an)ll
+
TH log(1/6)
2
1=1
T
TH (1/)
<(Ep Ep,n toa)
min 1/2, (lo(sn, an)ll
+
2A
Since 2 1, we have
TH log(1/6)
$ EP + EP,n +Ex
T min 1, [lo(s,, an)ll an 2,-1,n
2A
TH log(11)8)
+cx)
H T 2d
+
A
2A
where the last inequality is Lemma D.6.
Conclusion. Combining the above bounds, we have
(V. - -VG) - (V, (V.-v -+tt
HT log(1/0)
max
Limx +
2
HT Immax +
En. +,, + EP,E + EP, +
1og(1/0)
2V +
VÁ
(G. + GeM)
22/T
T 2d
a A
+
VVV
27 1/8)
20,
+ (PP.e + (pp
H T 2dlog T-2log
A + T
+
TH log( 1/6)
A
2A
HT
4Vmax
Limax + V
log(1/6)
2
(erg +
T 2dlog
4
A
+
CTVT
+
Lmax + 2 TH log (1/0//2
20,
VA
(CP.s + CP CPm
+a)
H TT--200 2dlog T-2log
(A+T)
Imnax 2 2TTH log 1/8)/2
A
V
=ō VinxxTmax Vinax / HT
+ +(n,g + exm)) (ViTT + T.max + / /TT
eT Vi
20.
+ (eP,s + He +Ex) (HVET + Lmax + HT
34

---

Published as a conference paper at ICLR 2024
Lemma B.16 (Regret decomposition). Assume all events listed in Lemma B.12 hold. Then, we have
T
Σ
(V*
Vi) + (V. -
T C(V (V, (V=)
- -(V - -V+) + -V.) - -(V - -v:)
F2 t=1
2am + F2(-1)
(TTlos(1/0) 2 + 48
with probability at least 1 5.
Proof. We note that, at any round & E [Z]. conditioning on all information collected up to round t 1, the randomness of V. and V. only comes from the randomness of Gaussian noise vari- In other words, the values of V. and V, determined once given these Gaussian noise variables. In light of this, we write out the dependence on the Gaussian noise variables explicitly: we treat V, and V. as functions of Er,,, , and define Velsr, fp..... [P.r.H] and Vels., ..... .pp.. the values of V. and V2 obtained at round with the Gaussian noise variables E Ep.,, E.... H. Then, we define notion of "worst- case" Gaussian noise variables as follows:
ables 1..............PPPPP..
E,,, SP,
SPA.
arg min
Ve Sp,,ul Volse,e Sp.,, Sp.um
s.t. [|,,, S and vh E [M] I1S an Sep.--
And we denote V. and V as the value functions specified by 5P,, .
Veler,e F &...Hl V VIlE, ST, .F.,.nl
In other words, V. and Vi- counterparts of V, and V, that attain the smallest difference, V. V. while the noise variables still satisfy the high probability bounds. By Lemma 1. we immediately have
Pr Pr(Eiow) == Pr V. V. S V. v. 1 8/T.
(11)
We note that here we have 8/T instead of 5 because we considering fixed and the results of Lemma B.12 are derived by the union bound over all E [T] - thus, the probability of the event &lo is at least 5/T for single t.
Then, we denote Eopt as the event that V.-V, V V Thus, by Lemma B.1,, we have Pr(Eopt) 2 (=2(- Moreover, we denote Palg as the randomness of the algorithm. Then, we define the joint distribution Popt of V, and V by restricting Palg to the event Eopt Specifically, is defined as
Pala (V,, Vs)/ Pr(Eopt) if Eopt otherwise
Pope (v,, V.)
Let == V. V. Then, we have
(V* - V.) + (V. - -va) SV 1 V. + V. - V
V* V. - Vi- - Vog
E. pryp
2 Vi + Vi
E prppopt
(Eppe) Palg(2)
- (2- 1 Vi + Vi-) dz
Pr(Eopt)
[Eapt) (z-V, + +v;)) /Pr(Eopt)
E
gropoig
35

---

Published as a conference paper at ICLR 2024
where the second inequality is by the definition of Popt. which rules out the case that Eopt does not hold. Considering the event Elow, we have
(V* - V.) + (V. - V
E zrePats
[Eppp) 11 {Etow]
(z-V, + +v:)] + E
[ 1 ( } (= (= V. + v1)) /P((Eop))
E sorpalg
[ ]
(2-Ve- + Vi }]
E prrpalg
[1Eope 1 14Vanal) /Pr(Eops)
V= + V.) + maxx B/T) PPr(Eopt)
E anrPals
[| [ 1 [8tow]
where the last inequality is by (11). For the first term, we have
[Eopt
j { (z VT + +V/)]
E PrrPalx
[(Elow] (z V2 + }
s
E Pala
[2=vv; V. + +v=)]
[1 (z-V; + v
zmppll
srupalg
(z-V, V, + +v:)] 5/
E
pnepagg
E
V. Vi V.V
-V + +V, + 4mmax8/T
= E (V. - vol) - (Ve- - - + +E (VaL -V, - (V - -V,-] + Vmmax
where the first inequality holds since inequality is by (11) again.
-V V. 0 conditioning on Elows and the second
Recall that Pr(Eopt)= 2 (-1). Inserting all of these back, we obtain
Σ V - V.)+ (V,+ 1=1
E (V. Vol) (V-- - vai] +E Vi) -(va) 1s--vi -(vai-Vii)) v)))))
<F-2(-1)
8Vmax& +
8Vmax + SF (-1)
Σ
(VV, v=l)- - -(v -Vi- - - + (V - -V,) - -(v=) - -v-))
(1o8(1/8)
+ 2Vmax
2
where the last inequality is the Hoeffding's 's inequality.
Given all these lemmas, we are ready to establish an upper bound of regret. We first note that, since π. xh-1 for all f, the regret incurred by o. for all t equivalent to that incurred by of for all Hence, it suffices to compute the regret incurred by xf for t E [T] and multiply it by two to get the total regret.
We start with the following regret decomposition:
Regret
Σ V'
(v=
Σ
V* V,
+ V.
-Vxl
+
Σ 1=
T
V. - Vol
+ +
- v.).
(*)
36

---

Published as a conference paper at ICLR 2024
By Lemma 1., further decompose (+) and obtain
v V. Ve Ve + (1 F2(-1)
Regret, F2
Σ
V.
-
V
Vi
(
(
mmx +
T 1og(1
46
F2(-1)
2
We note that both (i) and (ii) can be bounded by Lemma B.15:
(i), (ii) $
V Lmax + Vmxx v HT
+ (Eng + +.,)) (VaT + Lmax + v HT + cT
20,
+ (ep,e + EP (P,+teN) (HVdT + Lmax + VHT)
Inserting this back, we obtain
Regrety Ō Vinax-man + Vinxx VHT
+ (Cos + (an) ( (VaT + Lmmax + VHT + ET cVVT
20,
+ (er,s + fr,n + (a) (HVaT + Timax + VHT
+ Vmax VT
To compute this quantity, we note the following asymptotic rate:
f.g + Er,y = Ō (dvk+B*
CP.E + CP.m + + (2/220/ <
Lmax ( B2))
Hence, we have
Regrety =
R =
VT kt 2 11/2 122 (k+ B2)312) (B+g333)))
B.5 BOUNDING NUMBER OF QUERIES
Recall that the number of queries are computed via
T
T
Queriesy = Z,
->
2,1
0o.01~NNi C -((())))(++))) - B|) >
E
1=1
1=1
Notice that Cauchy-Schwaan inequality implies
E 8
- ((7))) - 0z) s [|o(7?) - -(T
E
100 01112,-1
0
2 110
2 207d
(Q(7") -
E 110 0111.,-1 5
0 1|
0,.0,
VX 00.01
VA
where the second inequality is by |ااا|ع2 = 1/A, and the last step is by the fact that 0o - 0, follows
(O 2,),))))1)) and Lemma D.3. We denote Ç 20 Btrr/2d/// 2d/A for the ease of notation. Then,
37

---

Published as a conference paper at ICLR 2024
have
T
Ze min {s,
((:)) (00 -00-0 -.i1]} > >E}
Queries
E
00.0:
T
min {i,
[[((TT) -()))) -000-111) -01l)>
Σ
Zr
E 00.0,
t=1
Applying
inequality, we have
T Z,1
((0) -11) 2112
Queriesy -
min
1, E 90.01
1=1
Let uo, i1 denotes two independent standard Gaussian variables with zero mean and identity covari- ance matrix. Then, On- - 02 has the same joint distribution as or -. 1/2 ("o - u1). Hence, we can rewrite the expectation in the indicator
-1))]
[(((6))) o,E,-12 (wo mn)) ]
TE 80,81
20.
Furthermore, we have
- (10(7))
(1067))
((([)) T 0,207-1 1/2 (no - u1) w1))
E
M0,001
E
[d(T)) - -o(Tt))
o,Eس 1/2 (uo - un) (wo u1) o, (
- - o(T!)) 0f 1 E. (uo - un) (uo u1) 7 o, o, 1/2 (d(T)) - d(:)))
u0.01
For the expectation in the middle, have
E (wo uz) (uo u1) | Elugu]1 + E[unu 21
where we have used the fact that E[ugu,]] by independence. Therefore, we have
(10(79) - ((++)) -(((7)))<(T))) (0. - -a)))²
E
0..01
= ( o(tt)) T 22211/221)0 (0(7))
(|[((( ((rr)
Inserting this back, we obtain
Queries,
2,1
min - > 2
T
²²
<
Z,1
min (1.1|((7?) o(7)) o(T))) >
2c f
1=1
0
T
Zi min [1, - ,T. |
2
t=1
2
+ 47
2d 2d
2
A
where the last step is Lemma D.6. Plugging the value of ( and all other variables, we obtain
+ 4T
=ō d + B2)2
Queriesy <
log
Xe²
2
38

---

Published as a conference paper at ICLR 2024
C PROOF OF THEOREM 5.4
We first present some supporting results Appendix C.I. Then, we prove the upper bound of Bayesian regret in Appendix C.2 and the number of queries in Appendix C.3.
C.1 SUPPORTING LEMMAS
In Appendix C.I.I, we establish some supporting results for a probability estimation problem in the frequentist setting. In Appendix C.1.2, we adapt these results to the Bayesian setting. The Bayesian results will be heavily used later in the proof of Theorem 5.4 in Appendices C.2 and C.3.
C.1.1 SUPPORTING RESULTS FROM FREQUENTIST SETTING
Consider a conditional probability estimation problem. Let A' and y be the instance space and the target space, respectively. Let J. (X' )) R be function class. We given dataset D = {(z, y)} where generation process, we assume the data distribution D; is history-dependent, i.e., 24 can depend on the previous samples: 21, conditional probability f" using the dataset D.
Dj and ~ (z, -). We assume f E F. Regarding the data
1, ,1i.:..,.i........... for any [n]. Our goal is to estimate the true
At a high level, this problem is designed to capture both the reward learning and the model learning problems the RL setting. Specifically, in the reward learning problem, we will instantiate X' S x A and y = {0, 1). where we recall that S and A are the state space and the action space, respectively, and the preference feedback is binary. In the model learning problem, we can instantiate X' = S x A and y S. We abstract these two problems into this conditional probability estimation problem to make the analysis more concise. However, one caveat is that all we derived in this section frequentist results, while applicable. In Appendix C.1.2, we will adapt these frequentist results to the Bayesian setting so that they can be applied.
considering Bayesian RL. Thus, the results are not directly
Now we establish some important results for this problem. First, we have the following lemma, which is consequence of Lemma D.10.
Lemma C.1 (MLE generalization bound). Fix E (0, 1). Follow the setting stated above. Let J be the maximum likelihood estimator:
arg max fer
log f(r, V.).
Define the version space:
w - f SEF:
n dTy (for))) (r(m))
where 3x(n) = 98 log((N) (m) 18)) Then, the following holds
(i) ft E v with probability at least 1 - 8.
(ii) for any f. E EV, it holds that
Edt (I(w)) S 43z(n).
Proof of Lemma C.I. We first construct an auxiliary version space V as follows
n
D
JEF
Σ
E DnD.
dey (f(,,)), S log (ND( 11xz)) )
By Lemma 1010, f E 5e with probability at least 1- 6. To prove (i), will show that whenever f E D., have f V as well with high probability. Let Fi denote (n-bai)--b of F
39

---

Published as a conference paper at ICLR 2024
with respect to || bl Then for all E Fi. the following holds with probability at least 1 by Lemma D.4 and the union bound on Fi}
Σ Ty (
E dry (f)(x,),, + 4log (No (m11)))))) FF, 11mo) BnDi
2
(12)
Now for any f E F, there must exist fn E Fij such that ll. - filllo S (n/V1)-1, which impies the following
"
11 - fille -
Σ
1/n,
(13)
i=1
n
Σ E di (((,,)) D.D.
1/ Snll3 Σ
1/n
(14)
Hence, for all / FF we have
Σ di (f(zs,)),
2
Σ di (fi(a.)) (z);, +2 >
dry (H(
i=1
2
dr (Ji(z f (x4) 2/n
4
Σ
diy (fi(z,)) log NN (nn())))) FF,1l 11o0) 16) 2/n
[=1 DrD
<87
Σ RND.
dry (f(z, (x,, 8lgg ND (n( F, 16) + 10/n.
with probability at least 8. Here the second inequality uses (13), the third uses (12), and the last uses (14). Therefore, for any possible value of the estimator f. conditioning on f V* we have
Σ diy ((...))
<8 Σ E dtv (fle,)) 8log (n((()))))) ",,, 1lx)) 10/n D-D;
<88 log (No (M(()))))) llec 16) 110n
598 NN (mDD))))
11x /8)
with probability at least 1 - 5. Here the second inequality is by the definition of V.. The last inequality holds since it reasonable to assume that the bracketing number least some constant so that (x)))) ,F. (0)) > 1/n.
The above means whenever f* Dr we have f E yF as well with probability at least 1 - 6. Since f* E fi with probability at least 1 - 6, we have f E oF with probability at least 28. Adjusting 8 completes the proof of (i).
40

---

Published as a conference paper at ICLR 2024
For (ii), we have
Σ div ((x,)))
n
> dTV (fo.))) drv (f(.:))
"
2d1 (f(x,)), + Σ 2dby ((x,)),
<487(n)
where the second inequality is by the fact that (a + 6)² S 2a² + 262 for any and 6, and the third inequality is by the definition of y=.
Next, we further assume that the function class F is parameterized by a function class via link function Φ. The reason for this assumption is that we want to capture the structure of the reward learning problem, where the feedback generating distribution is parameterized by the reward function via a link function 4.
Assumption C.2 (Binary label and function parameterization.). Assume Y {0, 1} is binary, and there is a function class G [ X' + [0, G] that parameterizes FF via link function t. Specifically, we assume
= F= [f 0) (g(x))) =1 Q(g(x)) : g
where we further assume & satisfies Assumption 3.1. For any f E F, let gs denote the function that parameterizes f. We define g 97 and g" = 91"
As preliminary note, the function class g will actually correspond to the function class R (3) later in the proof.
We should emphasize again that, although the function class G aims to capture the structure of the reward learning problem, the function class F will be used to capture both the reward learning and the model learning problems. When it is applied to the model learning problem, we can simply ignore the function class G and any results that are related to G. On the other hand, when is applied to the reward learning problem, such function class G will be helpful to derive some results in the reward function itself.
Before diving into the analysis of the function class G. we first introduce the following lemma which shows that the bracketing numbers of F and G are bounded by each other.
Lemma C.3. Under Assumption C.2, for any w > O, we have and
No [, l1x)) S ND [Rw, 9, llx))
Ng (Kw,, 9, (1xo) S ND [W lboo).
Proof. For any f E F, we assume they are parameterized by g = Ij and g' == 9p, respectively. Then, have
sup (f fl, (e) = sup ((((z)) - (g' (z)xx))) < sup [g(x) g (=) x.9
where the inequality is Lemma D.1. Hence, if we have a bracktt of G in the infinite norm, then we have w-bracket of JF in the infinite norm. This proves the first claim. For the second claim, by Lemma D.I, we have
sup [g(x) g (x)) & ssup (g(x)) (0g((x)) = kuu [f v) - f'(x,, v)1-
2,2)
This proves the second claim.
Then, Lemma C. leads to similar results with version space constructed on G. Corollary C.4. Under Assumption C.2, define
V
g geg:
- -(at))) S Bl((m)
i=1
where Bg(n) 98 18g2log(22 (((r)))) 9. 1//) and we denote 9 == 97 as the function that parameterizes the maximum likelihood estimator J. Then, the following holds
41

---

Published as a conference paper at ICLR 2024
(1) g" E V with probability at least 1 - 6
(2) for any g.g E V we have
Σ (g(z)) s 448((n).
Proof of Corollary C.4. To prove (i), we claim that for any f E V (defined in Lemma C.I), we have 9 v as well. To see this, we note that
E 2ND:
(0(x) -1()))
I R
E
((ī(z))
#(or(x)))
DrDD
E DwD;
f(z,,)) 0) f(z,
k
E
d+v (f(z,),
where the inequality is Lemma D.I, and the last equality holds since we assume y {0. 1) is binary. Hence, for any f E V.,, it holds that
(ī(z) -g(()))
Sx E E di (fI..))
E DND:
aNDD
SK² (5(
=x² (12)) 1x))
By Lemma C.3, we have
log log(2N FI 110) -
9. 1l0))
Hence, we have
Σ DND,
()(z) -(()))9((1)) -g(()))) S 3o(n)
E
which implies gs V Therefore, whenever ft E VJ, we have gy. E V as well. Since f e v with probability at least - ō, we have gy. ve with probability at least 6. This completes the proof of (i).
Now we prove (2). For any g.g E Vo, we have
9 (<(x)) < ==1
Σ (B(a)) g(2z)) + Σ [(x;) - (((x))) s 48g(n)
((
i=1
where the first inequality is by the fact that (a + b)2 < 2a + 2b for any and b.
C.1.2 ADAPTING RESULTS INTO BAYESIAN SETTING
Now we change the setting defined in Appendix C.I.1 into Bayesian online setting. The reason for this adaptation to make these results applicable to the Bayesian RL setting. We formally define the Bayesian online conditional probability estimation problem below.
Let X' and Y be the instance space and the target space, respectively. Let (X' }) + RR be function class. The interaction proceeds for T' rounds. At each round t [T'.. observe an instance Tu E X and need to outputs a function f. F as our prediction. Then, the label y/ E y is revealed. We assume that x; D; for some distribution D, and yi ~ f (z. We assume the true conditional distribution fr is sampled from some known prior distribution E A(F) at the beginning. Regarding the data generation process, we assume the data distribution D; is history- dependent, i.c., T; can depend on the previous samples: I1, W1,..... Fi- M for any E [n).
Denote H4 the history up round I, i.e., H4 (x1, f1, 91, x2, f2, y2, ... rz, St. ya). Define the maximum likelihood estimator of f on the dataset ((1., ys) v.) 1 as Fr. i.e.
F. arg max
log ff (x).
fEF
8=1
42

---

Published as a conference paper at ICLR 2024
Similar to the previous section, we will also consider the presence of a function class g (Assump- tion C.2) in the analysis presented in this section. It's worth noting that although Assumption C.2 is initially introduced in the frequentist setting, when mention that Assumption C.2 holds in this section, we are actually considering the Bayesian setting.
Lemma C.5. It holds that
T Σ E
B 1.5
(dt)) H [
drv
s 6 6/T3)(T) dim (F,1/T) log(T)
(15)
and
E f.f'
(f(s))
M--]] 4T) +
(16)
where 8/x(t) = 98 12g 1F, and f' are sampled from the posterior of f* from conditioning on H4-1 in the inner conditional expectation. Moreover, if F is parameterized by G (i.e., if Assumption C.2 holds), we have
Σ Hi
E [o(x)) g g'(x)) Me-1] s ( dim (9.1/T) log(GT) 9.0
(17)
and
Σ
E
E
- ( Me [
< 4,G(T) +
(18)
19.9'
where Bl(() = I8x2 log(2GTN (x(U))))),, 1.11- (lxo) and g: o are sampled from the posterior of g" conditioning on H4-1 in the inner conditional expectation.
Proof of Lemma C.5. We will only prove (15) and (16) since the proof of (17) and (18) is almost identical.
Proof of (15), We define the version space round for t [T] follows
DF = {1EF ddev (f(lr)))) s 35(t 1)
where the maximum likelihood estimator on the dataset (x. yz) 1= This construction aims to mimic the version space Di defined Lemma C.I, which enable us to apply Lemma C.I.
We first split the left side of (15) into two cases based on whether and I' belong to Vi::
E
E
(dv(((()),
He-
Lif
1 Vi and fl E (fdd))((())) H
Ms-1
fif'
+ 1 ve or ff a (dv H4-
ff
=: T2.
43

---

Published as a conference paper at ICLR 2024
To bound T2, since the total variation distance is upper bounded by 1, we have
T2
E
[I
V
f v M6-1
S.f"
E [.f
1 v or f & v H6-1
He-1
2R [[ $ v.3} Ho 1]
E
He-1
E
[f $ v
[1
(( [+]
2
Hi-1
$278
where the second inequality holds by the union bound and the condition that f and f' have the same posterior distributions as f conditioning on H4-1- The last two equalities holds by the law of probability. The last inequality is Lemma C.I.
Now let's bound Tj. We first notice that can replace the expectation with the supremum:
sup drv (fv()))).
He-1
Applying Lemma D.12, we have
Ti S TVF dim (F,1/T) loo T
Combining the upper bounds of T, and T2 and setting 5 = 1/T, we complete the proof of (15).
Proof of (16). We split the left side of (16) into two cases based on whether f and f' belong to Vi=:
T
Σ
E
E
(f()),
[6-1]
S.
T
1 E of and S' E e ((v))) [e-1]]
E
E
H
E
1 $ Vi or f & VV (fvss) Ho-1
He-1
T3 + T4.
Following a similar argument as the proof of (15) above, we have T4 S 275. For T3, by the definition VL" we directly have T3 s 43) Setting 1/T, we complete the proof of (16).
Proof of (17) and (18). An identical argument can be applied to prove (17) and (18) leveraging Corollary C.4.
Lemma C.6. Under Assumption C.2, it holds that
He-1 > g
E [ g'(x))
H4-1
5.9"
9 TTbTT
(T)
min
dim (g,e/2).
dimz e/2)
22
where (t)() = 98x2 log (x(()))) -1,9, 11 In the inner expectation, 9, g' are sampled from the posterior of g" conditioning H--1-
44

---

Published as a conference paper at ICLR 2024
Proof of Lemma C.6. We define the version space at round for t [T] as follows
E(a(es) (
? - Bo(t (oatt-1)
yp- g geg:
where recall that 9t is defined as the function that parameterizes the maximum likelihood estimator on the dataset ((Tr. Ms) k= (i.e., Ft- 97. ). This construction aims to mimic the version space 1/ defined in Corollary C.4, which enable us to apply Corollary C.4.
We first split the left side into two cases based on whether both 9 and g' belong to V/:
T
(xx))) Ho-1 >e }}]
E
E
M4-1
9-9
[ E us and g' E (o(t)( g (axi) Hom]
E
1
E
H6-1
9.9"
[=1
[1 E vg or of $ H 5 (xxi)) [aal||Hi]]] > of]
E
9.9¹
[19e vs and (o()) - (zx) Heme| > 0/2/
1
E
Ht-1
9.9'
[1 vg or o' E (o)()))))- - s'(x:) Nn-1| > c12 9.9
+
E He-1
1
E
+T
Here the inequality is due to the fact that Il [a +b > c) < [aa> 1(b c/2} for any a, c. To bound T2, recalling that g()) E [0, G). then we have
1 G [|-1 > c12}
T2
E
1
E
[
or
1=1
H4
9.9
T
2G
1 1 vg or E v8n [a_1
E
E
6
He-1
19:0'
2C T
[fg E v3 He He-1] ]
E
2
He-1
1=1
4G T
Σ
E
[1 $ 1
9", He-1
tm1
4G
Σ
E Hi-1
[1000
& vg) [r]
6
t=1
9"
4GT6
where the second inequality is by the fact that 1 1a > b} < a/b for any a 2 0 and b > 0, the third inequality holds since g and g' are identically distributed as g" conditioning on He-1, the two equalities holds by the law of probability, and the last inequality is Corollary C.4.
Now let us bound Tj. We first notice that we can replace the expectation with the supremum:
Ti
1 sup
19(2.) g'(xx)) e/2
H
Recall that, for any g DS we have
(g(x.) 0(x=))² < Bg - 1).
45

---

Published as a conference paper at ICLR 2024
Hence, applying Lemma D.11, we get
T1 Smin
2 RVT5al1-11 -
+1) dim (9,c/2),
(180(1-1)
22/4 +1 dimz(G,e/2)
c/2
<min
Ty/BBtt-11
dimı (9.c/2).
(7
(9,
22
Combining the upper bounds of and T2, obtain
T
(lo(2s) - g((x))) Me-1 s
E
E
9-9"
4GT
(5 T5/TB((t1)) dimi (G.e/2). (t
dimg(G, e/23
min
Setting 5 = (/GT),, the parameter (t 1) becomes 3/ 1), which is upper bounded by 5 (T). Then, we finish the proof.
C.2 BOUNDING BAYESIAN REGRET
Now we are ready to prove Theorem 5.4. We will prove the upper bound on the Bayesian regret in this section and prove the upper bound on the number of queries in the next section.
For the ease of notation, we will omit the dependence of the state-value function on the initial state 8i and simply write V == (si) for any state-value function V throughout the proof.
We start by simplifying the Bayesian regret. Since के
T we have
Σ 2V Vol -
BayesRegrety r-
22V* Vo -V-L.)
T
V - -v+)
V+ voi)
E
+ E
< E y
Σ
(v* -
Hence, we only need to consider the regret incurred by m.. We defined V.P as the state-value function of policy with reward function and model P. Given that, we can express the Bayesian regret as
T
Bayestegret, $2
E r'
We reformulate the expectation by first taking the expectation of the historical data up to round t - 1 and then taking the conditional expectation of p* and r*. Coneretely, we denote H = {7f. (o1), Tf (ot-1)} as the history up to round t 1, and then we have
BayesRegret,
2
E
V pt
V.m.p. H
Hi 1
t=0
V
Pr.P. pm
H1-1
Hi
p,
t=0
46

---

Published as a conference paper at ICLR 2024
For the equality above, note that (ri, Pt) and (r*, P*) identically distributed given He-1 and oद and n² are the respective optimal policies of (re, Pt) and (r", P*). Hence, V and V .. are identically distributed given Hz-1, which is the reason that we can do the replacement in the conditional expectation. Next, we proceed by decomposing the regret:
BayesRegrely
E
E
V
Pr
V
h.
V m. + -
V
H4
Hi-1
T
2
E
E
Vay
11.
V
re, +
ri.pa - V
+ ri,p - V
He-1
He-1
1=0
2
E
V
P.
V a
+ Velae
re, + Veu.po
1=0
v
V
n reppr
V
+ V mi V.
P..
=:Toddel
-Trwwardd
(19)
Here added and substracted -e-p- and V in the first equality. For the second equality, note that n.- = - is measurable with respect to H4-1 (i.e., E(T) [4-1] = m/).* Hence, V
and P. are identically distributed conditioning He-1-
Next, we will show that the two terms, Toodel and Treward, arise from the estimation errors in the model and reward, respectively.
Bounding Tmodel.
By simulation lemma (Lemma D.2) and the tower rule, we have
T
H
drv (Pc(on an), (sh dn))
model SHE
E
1= 1=1 )a)
H
drv ak)( Pr (shn
=H E
1=0 A=1
H
ddv (Pi(sh. an), P* P* an)) He-1
=H E
PLP
11
T
H
E
Σ
E P.P
drv (r,(s,, an), P* (sh, an)) [e-_1]
1=1
0
H2 dimi (P.1/T) log(T):
(Hog((N -1-1=))))
where the last step is Lemma C.5.
Bounding Trwward. By the definition of state-value function, we have
T
Treward
E
r((T.))
re( + +++) -
1=0
T
E
(1
- Zi)
r((TT)) - r ((( +r (T-)) - r (T.)
1=0
T
Zi re( - - ((()))))))))(())(((())))))))
E
t=
Strietlyy speaking, m) is measurable with respect to the a-algehra generated by H4-
47

---

Published as a conference paper at ICLR 2024
For the first term, by the query condition, it holds that
T
E
(((+))))((+)))-----))))))))))))) (1-
(1 - Z+)
1=0
T
- (1
E
t=
1 [ - ( sc}
H
(T((7)) - rx() ((+))))))) Hi H
( -+))))((((()(()))))))))))) sc
1.7
()))))())))(+))))))))))))))))))) (())))))())+))))))((-) (77) He-1 +t]
(
Te.
Here the first equality is by definition. The second equality is by the law of probability. The third equality holds since the indicator is measurable with respect to H T. and T/.. The last inequality by the indicator and the fact that r; and y* have the same posterior conditioning on He-1- Plugging this upper bound back, have
T
Treward ST'
+
Σ
E
2e
re(Te) - + r" (7:)
1=0
| - - (r,) r [5,)| (
=Te +
Σ
E
2, E Per
He-1
1=0
In the inner expectation of the second term above, we notice that both r and r* are sampled from the posterior of r* conditioning on H4-1- Thus, we can invoke the second statement in Lemma C.5 where the function g corresponds to rt and the function g' corresponds to r* This gives
Treward 50 5
TE <o(Te
V TT2 log (HTNN(M(2T)-)) R2
-1=0)) 1- dim, (R, 1/. log(HrT)
Conclusion. Given the upper bounds Tmodel and Treward, ignoring logarithmic factors T and H, we conclude that
BayesRegret,, = δ H² dimi (P.1/T) ((TIS)) (lo)))
+ Te + k dim (R,1/T) / Tlog (1((R(2T))1 R,
-,, -lxo))
48

---

Published as a conference paper at ICLR 2024
C.3 BOUNDING NUMBER OF QUERIES
It holds that
T
BaycsQueries, E
Σ
Zz
1=0
T
> }]
Σ 2=
E He-1
2
E r.pt
(())))
We notice that, in the inner expectaion, and r' are sampled from the posterior of r* conditioning on H4-1 (recalling the definition of Pr,)). Thus, we can invoke Lemma C.6 where the function corresponds to and the function g' corresponds to r'. This gives
{
1VTBBR dimu (R,e 21 diny (R, e/2)/ }
Bayes S min
6
where the inequality is Lemma C.6 and 3R == 98k log ( R, -1=)))
C.4 GENERALIZING THEOREM 5.4 THROUGH SEC
In this section, show that the dependence the eluder dimension in Theorem 5.4 can be gener- alized to the Sequential Extrapolation Coefficient (SEC) (Xie et al., 2022). It have been shown by Xie al. (2022) that the SEC can be upper bounded by the eluder dimenion, the Bellman-eluder dimension (Jin et al., 2021), and the bilinear rank (Du et al., 2021). Thus, SEC is more general measure of complexity.
We start by introducing the Bayesian Sequential Extrapolation Coefficient (Bayesian SEC) in the preference-based feedback, which is variant of the original SEC to accommodate the Bayesian and preference-base based learning setting. We define the Bayesian SEC for a model class P as
Sin Brand (drv (P((- (2(-1ssa); P 1 EE E Baandsy (db (P.(. 8. P*(, s.a))
BayesSECp (P)
E pr
sup P PpPP PTCP De (1
and the Bayesian SEC for reward function class R as
E.g Ef (m((7)) - (T(TT) + (Tt) - (+))) 1 IVVLL Byfnay (ra(7?" (T+) ( (T))
BayesSECA (R) == E PT
sup ER
We note that the Bayesian SEC can be easily reduced to the frequentist SEC by specifying the prior on r* and p* to be the Dirac delta function. We note that our definition of the reward function SEC involves squaring within the expectation in the numerator rather than externally, potentially making it larger.
Now, we are ready to state the generalization Theorem 5.4.
Theorem C.7. PbTS (Algorithm 2) guarantees that
BayesRegrety: δ Te H. BayesSEGa(P)) -H up (Ry) T k² 1R
BayesQueriesy ō x² BayesSECR(R)
where we denote up ( lloo)) and UR. == log (og (lxo))
The proofs are provided in the following sections (Appendices C.4.1 and C.4.2).
C.4.1 BOUNDING BAYESIAN REGRET VIA SEC
We first prove the upper bound on the Bayesian regret. Following (19), it suffices to separately bound T Tmadel and T Treward via SEC. We start with Tmodde-
49

---

Published as a conference paper at ICLR 2024
Bounding mmodel-
By simulation lemma (Lemma D.2), we have
T
drv (r((s) an), P (shn
T model S H
E
t=0 h=1 (a
where dz (s, a) denotes the probability of reaching (s, a) at time step h. By multiplying and dividing by the same term, we obtain the following.
H
drv (Pi(on, an); P* (onn (on,an))
E (9k (n
model SHE
1=
E
(onassmad
of diyy Peess, an), Pa (shn an)
x
IV
E
drv an),
1=0 h=1
Σ
H E
drv (Pr(sh an). (* an))) (r(snaah))
h= and
<H
E
1=0
Eizo
Σm=
EE
(n dry (r((s,, an), P (*n.
T
1-1
dev Cev an) (sh (sh.as)ddd
on), an))
E
1v
E
l=0
1=0
Here note that b == max(a, b) < a + b for a, 2 O. The last step above is the Cauchy- Schwarz inequality. We observe that term (i) exactly bounded by the Bayesian SEC of models. For term (ii), can invoke (16) in Lemma C.5 since Pt has identical posterior distribution P* given the historical data up to round t 1. This gives (ii) S Ö(VTH -1)). Plugging these back, we obtain
model zŌ zŌ(H BayesSECp(P)) TH up
Bounding Treward- The reward part can be bounded similarly, except that we need to additionally consider the query conditions. To begin with, by the definition of value function, we have
T Treward
Σ E
(r))
(((TT) -
r((T()
1=0
T
E
(1 Zr)
(())
E t=
Ze
r((TT)
(
1=0
(ii
Following the same argument as in the proof of Appendix C.2, we can bound (i) as (i) S Te. Now proceed to bound (ii), which is the regret incurred when making queries. By multiplying and
50

---

Published as a conference paper at ICLR 2024
dividing by the same term, obtain the following.
E Ze
Tp. m.. T2. Zz]
(ii
E FE
t=0
1 D
Tp. . Ze
1 Σ
Zo - - +r(())))r(++++)))rr+)))++)
Tp. op re Ze
P
? IZ (Te(T() - ((()))))()))+(+)))))-))))))-) op. T.. rr. Zi) )²
T
1 Σ =
Ze (r)6)))--6))
T&. m Te, Ze
1=
(ii)
Ze (((()))) - (((((t))-n(()))))
(x(( +(())))))))
IV
(iv)
where the last inequality is Cauchy-Schward inequality. We observe that term (iii) is exactly bounded by the Bayesian SEC reward functions via Jensen's 's incquality. For term (iv), we invoke (18) in Lemma C.5 and get (iv) z Ö(VR2T UR). Now plugging these upper bounds back, we get
reward S Te TT+ (CC+O(VEr (ayyesSEGRR()) RTT 1R
Conclusion. Given the upper bounds on Tmodel and T Treward, we conclude that
BayesRegrety ②ō H BayyysSSECC(P) TH up + Te + / /BayeSSECR(R) RTT 1R
C.4.2 BOUNDING NUMBER OF QUERIES VIA SEC
By the definition of Ze, we have
BayesQueries,
Z
E
Σ
z
7,1
(11(7()-((77))) ((t)
ppplpptd
- - -(())) > 2
E
7,1
E.
T
[[(((T2) - (
((((7))) -100))-))))1
E
Z
2
1=0
E
Zg
-
ro(T:t) - - [
2
r,p'
1=0
51

---

Published as a conference paper at ICLR 2024
Here the last step is by the definition of Pr.t- Now swap the order of expectation and get BayesQueriest
E
T
E E
(<((((1)) -
mc mp Tt: Ze
E
2
1-1
B- (((()((9)) (((
T m rM re, Ze
1=
=0
(rm)))))))) " nes Zo - - -((()))))n((t))))))))))))))))))) -
T
T
E E
nl. Tt; Ze
E
E ((((re()))) ((()))
T m3 rM Ti, Zz
(R)
where in the last step we applied Jensen's 's inequality to the first multiplicative term and applied (18) Lemma C.5 to the second term. We observe that the first term can be bounded by SEC, and thus we obtain
BayesQueries, 2ō k2 BayesSECR (R) LRR
22
D TECHNICAL LEMMAS
Lemma D.1. Under Assumption 3.1, we have (((((a) - +(b)) I a b k(σ(a) - +(b)) for any a, E [0, H).
Proof of Lemma D.I. We note that ((a) x(b) = J-" 4 4'(x) dx and
1 (a b) S (a (a-bb b) inf ('xx) < / ('xx) dx S (a - b)
sup xe(a,
('(x) S R R b).
2E(a,
Lemma D.2 (Simulation lemma). For any models P, P and any policy n, we have
H
(s1) - V (s1)
E
E V (s'+
E
V
s/ p(nnaaa
Amml
<H
drv (P(: (P(.1sp. sn, an), P(: sny an)
(sh Jod P.A.
where dp,, (8, a) is the probability of x reaching (s, a) at time step h given model P.
Lemma D.3 (Gaussian concentration), Let e ~ (0,,EE11) for e E R- and E positive definite matrix. Then, for any > O, we have
1. Pr (Iclls> 22ddlo((2d/)) 56
2. E [||e [ S Ved.
Proof of Lemma D.3. The proof of the first inequality is provided in Abeille & Lazaric (2017, Ap- pendix A). We provide a proof here for completeness. Let y No(0, Ia) where Ia denotes the d-dimensional identity matrix. Fix an arbitrary a. We have
Pr (Illla avd) Pr 3i maa a s dr (Imll > a) <d 2c d- 0022/2
52

---

Published as a conference paper at ICLR 2024
where the second inequality is the union bound, and the last inequality is the standard concentration inequality for one-dimensional Gaussian random variable. We choose logog(2)/0) and get
Pr [1lll2 log(2/)))) S Ó.
Let B denote the square root of 2, i.e., BB Σ. Then, we have
|| - Ve V(vBB-In) T BB (VeB-In)= = =velnll
(20)
Hence, it holds that
Pr (Idll > v log((/))) (11rll v log s 6.
This proves the first inequality. To prove the second inequality, note that, by (20),
E [||]||>] = VoE IIlalla] & voy E [n Vod.
The following inequalities are well- and we use the version in Zhu & Nowak (2022).
Lemma D.4. (Zhu Nowak, 2022) Ler (Xi)ez be a sequence of positive valued random variables adapted to a filtration Bt, and let [, = E[- B2-1l. Xf I B almost surely, then with probability at least 5, the following holds:
3 T
Σ
X1 Σ
Ex[X,] + 4B logg(1))))
2 1=1
T
Σ
E. [x,]
< 2 X. + 8B logg(100)
Σ
1=1
Lemma D.5 (Self-normalized process). (Abbasi-Yadkori et al., 2011) Let {xi]e=] be a real valued stochastic process sequence over the filtration {Fi) Let I; be conditionally B-subgaussian given F,-1- Let
{ 00 Define Σg AI i= with Φ, E Fi-1 be stochastic process in Rd with each l|øv|l & Lo- T.0T. Then for any > 0 and all > O, with probability at least 8
det (E.) 1/2 det(Al)-1/2
KL A
2B log
<
2B²
dlog
+ log((16)
Lemma D.6 (Elliptical potential lemma). (Abbasi- Yadkori al., 2011) Following the setting of Lemma D.5, we huve
A + +T2
Σ min {1, 11,.1112,1
2d
A
Lemma D.7 (Sum of features), (Jin et al., 2020) Following the setting of Lemma D.5, we have
Σ | &
The following lemma converts the TV distance between Gaussian distributions into the distance between their means.
Lemma D.8. Assume p1 = NN1,, 121) and p2 = Nu2, o²1) are two Gaussian distributions over Rdd Assume I|иl 122 S m. Then, we have
1
|| u2ll2 min
< drv(pi,p2) S Imm -2ll2
2ena" 2m
2
Co
53

---

Published as a conference paper at ICLR 2024
Proof. Without loss of generality, N0 I² and P2 = Na 61, I where a = l1 - -22ll2 and e1 = [1. [1.0..... ........ 0] E Rd. is clear that the total variation distance is preserved. Then, by definition,
rotate and translate the R space and assume that P1
(xx (x) P2(x)) dæ [
drv(p1.P2) P2) = 2 ZER
Ip
J2ee/aa/2
(1 (2 dz
where the last step holds since pl (z) - (2 2 0 and only x ei S a/2. Note that the above formulation is independent of any dimension except for first dimension, so we can marginize other dimensions and reduce into mee-iimesioonl problem:
[ asaa/2 Nxx ((110,,0)) -N -Naol dx
drv(p1,P2)
(F(a)(20)) - F(-o/(200))
(a/(20)
(ax 0, dr
-a/(22)
where we denote as the CDF of standard Gaussian ((, 1) in the middle step. Below we show that the above integral is upper bounded by C2a and lower bounded by Cja.
Upper bound.
For an upper bound, we note that for any v > 0, we have
2 n f N(x 00, dr S 2v N( 0, < VV
Inserting a2(2),, we obtain the desired upper bound.
Lower bound.
For a lower bound, we note that for any 0 < S mm if < 1, we have
e/2
| 0, 1) dx 2 2v max NN 00,1) 2 2cA 0, 1) = 20 xE|-v,u]
v
V2T
When v 2 1, we have
N(x 00 dx 2 [ N(x dr 0.6827
m
Combining the two together, have
[ N(= 0. dr 2 a. min
2 e m
Inserting a/(20), we obtain the desired lower bound.
Lemma D.9. Let x ~ NO, Ia) and A be positive semi-definite matrix. Then, we have
(tt((A)
E
1 2
Proof. Let P denote the orthogonal matrix diagonalizing A. i.e. A PAPT where diag(A),.... Ad)- Then, we have Ex ||ж| = E. Vx Ax = Ey / Ay where y = PT x
(O, La). Now consider the following optimization problem:
min S(M) = = Vvy My where M = {M > 0 M is diagonal and tr(M) = tr(A))) MEM
Then, we have A E M and Ez | Thus, the solution to the above optimization problem lower bound of E. ||= Since f(M) is concave in M, it must attain the minimum the bounary of M. By symmetry of entries in the diagonal, we know that the minimizer must have tr(A) one entry and 0 all other entries. Hence, the minimum value is
2 (r()) x
E VI(AA)) / Vr(AA) H.AJ)/un
We finish the proof by noticing that tr(A) tr(A).
54

---

Published as a conference paper at ICLR 2024
The following lemma was originally established by Agarwal et al. (2020) and later adapted by Wu et al. (2023a) to accommodate infinitely large function classes.
Lemma D.10 (Maximum likelihood estimation). (Wu et al., 2023a, Lemma C.3) Consider a se- quential conditional probability estimation problem. Let X and y be the instance space and the target space, respectively. Let F (X x } + IR denote the function class. We are given a dataset D = {(a,, y:) where 24 Di and y ~ (x. We assume f F. For the data generating process, we assume the data distribution D; is history-dependent, i.e., Ij can depend on the previ- samples: (h. Vi-1 likelihood estimator,
for any i [n]. We fix ô E (0,1). Let I denote the maximum
f = arg max fEr
Σ log (Irayy)).
Then, we have
Σ LE D,D,
div (fa,))) - 10 (Nn (n1))) 16xo)/6
(21)
with probability at least 1 5. Here [ denotes the total measure of space y, ie, |J] fy dy.
D.1 ELUDER DIMENSION
The following lemmas are adapted from Russo & Van Roy (2013) and Liu et al. (2022a).
Lemma D.11. Following the notation of Definition 5.2, define
Fi F= =={TEE
(-1 Eo(G..) SB
where Pe E F is an arbitrary function. Then, we have
(2VTB
sup
d(f(a)).(()))2
2w
+1 dim (F,W),
(22)
f.''F,
w
Σ
T
sup [((()),
4B <
We +1 dimz(F,w))
(23)
1=1
for any constant w > 0.
Proof of Lemma D.1I. We first prove (22) and then (23).
Proof of (22). We begin by showing that if
sup d (f(x)) 2 F.EF
for some / [T]. then &e is w-dependent sors. To see this, we note that, if x, is w-dependent on a subsequence (æi, Digs Fi,) of its predecessors, must have
23/Ww disjoint subsequence of its predeces-
Σ [df(()))) f(x.))) w.
Hence, x4 is w-dependent on disjoint subsequences, we have
Σ d(f(xs), > lw.
(24)
55

---

Published as a conference paper at ICLR 2024
For the left-hand side, also have
Σ (((( s E (((T.)) + + (((l)))))()))
SVT ((((as))(((ss)) + VT
Σ 8 ((((s)
<2/TB
(25)
where the first inequality is the triangle inequality, and the second inequality holds by the definition of Ft. Combining (24) and (25), we get that S 2/TB/w.
Next, we show that for any sequence (rf,.... ........... ). there is at least one element that is w-dependent on at least 7/d 1 disjoint subsequence of its predecessors, where d := (Jimm(F,uu) w). To show this, let m be the integer satisfying md + 1 < T S md + d. We will construct m disjoint subsequences, Bi...., Bmn At the beginning, let B; (x²)) for E [m]. If s'm is w-dependent subsequence B,,..., Bm, then we are done. Otherwise, we select a subsequence B; which a a w-independent of and append x'm+1 Bü. We repeat this process for all elements with indices j > m + until either æ/ is w-dependent on each subsequence or j т. For the latter, we have Σ [B 2 md, and since each element of subsequence B; is w-independent of its predecesors, we must have [B = for all Then, Ir must w-dependent on each subsequence by the definition of eluder dimension.
each
Finally, let's set the sequence (41....<4) .4) be the subsequence of (T) consisting of ele- ments F₁ for which d f(z)) > As we have established, have
1. each a/ is f--orm w-dependent on at most 2/T3/w disjoint subsequences, and 2. some 24 is -noom w-dependent on at least T/d - disjoint subsequences.
Therefore, we must have
implying that + S (2VT3/w + 1)d.
Proof of (23). The proof quite similar the proof of (22). For fn-norm, following the same argument, we can show the following:
1. each a/ is f2-norm w-dependent on at most 43/w² disjoint subsequences, and
2. some 2 l -o-morm w-dependent on least 7/d - disjoint subsequences.
Therefore, must have 7 7/d- A implying that (48/w2 1)d.
Lemma D.12. Following the setting of Lemma D.11, assume d(...) is upper bounded by < 8 Then, have
T Σ sup d(f(z). 4/T3B (imm(F,1/ log( t F.FEF.
Proof of Lemma D.12. For notational simplicity, we denote
d((())
04 = sup free
56

---

Published as a conference paper at ICLR 2024
Now fix constant A
O, and then we have
T
W/
1 (wr 2 53 dō
t=1
t=1
D
1 (w: 2 03 d8
D
SAT +
Σ
1l 2 63 dõ
22TB
SAT +
+1
dimi (F,6) d8
8
3
SAT +
dim, (F, d8
8
<T + 33/TB dim, (F, A) (og(D/A)
where the second incquality is Lemma D.11, and the last inequality uses the fact that dim, (F,8) is non-increasing in 5. We can conclude the proof by setting A 1/T.
57


Reviews:
[{"review_id": "Fm9VfKdXID", "reviewer": "Reviewer_ynpG", "summary": "This paper introduces a novel RLHF algorithm capable of learning from preference-based feedback while maintaining efficiency across statistical complexity, computational complexity, and query complexity. The algorithm is demonstrated to strike a near-optimal balance between regret bound and query complexity. Additionally, the authors extend these results to encompass more general nonlinear function approximation through the development of a model-based Thompson sampling method, accompanied by a Bayesian regret analysis.", "questions": "1. Sekhari et al. (2023a) have previously explored contextual bandits and imitation learning via preference-based active queries, demonstrating efficiency in statistical, computational, and query complexity. While this current paper addresses RL with linear MDP and nonlinear MDP, it would be beneficial to elucidate the specific technical differentiators that set it apart from Sekhari et al. (2023a).\n\n2. The paper proposes a new RLHF algorithm that relies on various input parameters such as $\\sigma_r, \\sigma_P, \\epsilon, \\alpha_L, \\alpha_U$. The authors provide rates for these parameters in the main theorem, some of which depend on unknown true parameters. To establish practical utility, it is crucial to use numerical simulations to justify the newly proposed algorithm.\n\n3. It is essential to support the theoretical findings with numerical evidence that demonstrates the superiority of the proposed approach over existing benchmark RLHF methods. Numerical comparisons would enhance the practical relevance and acceptance of this paper.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper makes good theoretical contributions. Despite prior works achieving sublinear worst-case regret for RL with preference-based feedback, these existing algorithms are often computationally infeasible, even in simplified models like tabular MDP. In the context of linear MDP, this paper marks the first RL algorithm that simultaneously achieves sublinear worst-case regret and computational efficiency when handling preference-based feedback.\n\n2. While the primary contribution is theoretical, the research provides valuable practical insights. Notably, the proposed algorithms suggest drawing one trajectory from the latest policy and another from an older policy, rather than two from the same policy, for regret minimization. This innovation departs from conventional practices and enhances the practicality of RLHF.\n\n3. Despite its theoretical nature, the paper is exceptionally well-written and easily comprehensible.", "weaknesses": "see Questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5ZcZqxXN73", "reviewer": "Reviewer_8PN9", "summary": "This paper studied RL with preference feedback and provided regret guarantee for linear MDP. Some extensions to nonlinear case using eluder dimension is also studied.", "questions": "See above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "An interesting problem and solid theory.", "weaknesses": "I have some major concerns:\n\n1. The theoretical contributions are incremental. The proposed algorithm is fairly standard (RLSVI) and almost identical as previous work. The proof technique is very routine and it is hard for me to see novelty here. There are a large body of theoretical works based on linear MDP and using model-free algorithms. The author didn't have a concrete comparison with them. Extension to nonlinear function approximation using eluder dimension is fairly well-known as well. People know for a while the only known function class for smaller eluder dimension is linear and generalized linear. There are many more general complexity measures for RL: Bellman-Eluder, Decision-Estimation Coefficient, bilinear class. The appendix is very long. I feel it might not be good to prove everything from scratch. There are so many prior works and I might suggest the authors to query existing lemma as much as possible to respect prior works.\n\n2. This work is far away from the practical RLHF use case. There is no experiment at all and the algorithm seems to be practically feasible. For example, it is unclear how to implement LLM fine-tuning through RLHF using algorithm 2. It is also unclear why we care about cumulative regret in the context of RLHF for LLM alignment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pF0vUB9gbd", "reviewer": "Reviewer_eu8c", "summary": "This paper considers learning linear MDP (Assp 4.1) with preferential feedback. The unobservability of rewards makes learning significantly harder than standard RL. The author proposes PR-LSVI (Alg 1). PR-LSVI combines the MLE and Gaussian exploration to balance the exploration versus exploitation tradeoff. The algorithm only queries the feedback when the two trajectories can have a large gap (2). Theorem 4.2 bounds regret and query complexity. The paper also introduced a posterior sampling algorithm (Alg 2) and derived its Bayesian regret and query complexity. The paper is somewhat more detailed than it should be but readable in general. I could not follow the details of the paper but found no issues. \n\nMinor comments:\n* Alg 1 Line 15: Quey -> Query", "questions": "* Could you elaborate with the connection of the paper by Wang et al. (2023)?\n\n* Could you elaborate on $\\omega$ after (1)? To my understanding, this controls the rewards in subsequent rounds. Essentially, the exploration and exploitation tradeoff is resolved by demonstrating that the exploration is enough (and decaying at the same rate as uncertainty), and describing the mechanism would help the reader.\n\n* One of the closest papers to this is Zanette et al 2019 which combines randomized exploration with least squares. Obviously, this paper is new in the sense that it deals with preferential noise. Other than that, are there technical novelty that should be highlighted in this paper?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Learning of linear MDP under limited feedback with optimal regret in terms of $T$ ($\\tilde{O}(\\sqrt{T})$)\n* Conceptually simple algorithm (Alg 1 and 2), which is computationally tractable and amount of query is controllable.", "weaknesses": "* Large volume: 53 pages is a bit large for conference proceedings. Not to mention, the shorter, the better s.t. the same results.\n* Suboptimal dependence on parameters except for $T$, such as $H$, which makes the exploration larger than what is required (Alg 1).\n* No experimental/simulation results.\n* Disjointness of two results: Two algorithms are not connected together, and they have different objectives (frequentist or Bayesian).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GBvvcsfSCA", "reviewer": "Reviewer_V7cf", "summary": "This paper considers Reinforcement Learning with preference-based feedback. Two algorithms are proposed with corresponding bounds on the (Bayesian) regret and (Bayesian) query complexity. The novelty lies at the application of randomization into the algorithm design in the preference-based feedback setup, making the algorithm more computationally efficient. It shows that there is a trade-off between the regret and the query times, i.e., more queries lead to less regret. The relationship is quantitatively characterized in the main results in terms of the parameter $\\beta$.", "questions": "- In terms of the regret bound for algorithm 1 (Theorem 4.2), can the authors comment on the dependence on $d$? Compared to the work by Zanette et al. (2020), it seems the power has increased a lot.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- For MDPs with linear structure, it proposes an algorithm that utilizes randomizations to facilitate the learning process under the context of preference feedback.\n- When the MDPs are not linear, it introduces a Thompson sampling based algorithm with accompanying Bayesian regret bound and query complexity bound.\n- For the proposed algorithms, regret bounds and query complexities are derived, which quantitatively characterizes the tradeoff between them. This provides insights on how to tune the threshold $\\epsilon$ in the algorithm in order to achieve certain performance, which I  appreciate a lot.\n- By injecting randomness to the algorithm, it improves the computation efficiency of the RL algorithm for the preference-based feedback problem.", "weaknesses": "- It would be great if the authors can illustrate the empirical performances of the proposed algorithms. Algorithm 2 seems to be computationally intensive. Additionally, it would be convincing if we can observe the tradeoff between the regret and query times in the experiments.\n\nMinors:\n- While most notations are well explained, some notations are used without being properly defined, e.g., $\\hat{\\theta}_{P,t,h}$. This may hinder the readers in other relevant field from reading this paper. Hope the authors can further improve the paper presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)