Order-Optimal Instance-Dependent Bounds for Offline Reinforcement Learning with Preference Feedback

## Abstract

Abstract We consider offline reinforcement learning (RL) with preference feedback in which the implicit reward is a linear function of an unknown parameter. Given an offline dataset, our objective consists in ascertaining the optimal action for each state, with the ultimate goal of minimizing the simple regret . We propose an algorithm, RL with L ocally O ptimal W eights or RL-LOW , which yields a simple regret of exp ⁡ ( − Ω ⁢ ( n / H ) ) Ω 𝑛 𝐻 \exp(-\Omega(n/H)) roman_exp ( - roman_Ω ( italic_n / italic_H ) ) where n 𝑛 n italic_n is the number of data samples and H 𝐻 H italic_H denotes an instance-dependent hardness quantity that depends explicitly on the suboptimality gap of each action. Furthermore, we derive a first-of-its-kind instance-dependent lower bound in offline RL with preference feedback. Interestingly, we observe that the lower and upper bounds on the simple regret match order-wise in the exponent, demonstrating order-wise optimality of RL-LOW . In view of privacy considerations in practical applications, we also extend RL-LOW to the setting of ( ε , δ ) 𝜀 𝛿 (\varepsilon,\delta) ( italic_ε , italic_δ ) -differential privacy and show, somewhat surprisingly, that the hardness parameter H 𝐻 H italic_H is unchanged in the asymptotic regime as n 𝑛 n italic_n tends to infinity; this underscores the inherent efficiency of RL-LOW in terms of preserving the privacy of the observed rewards. Given our focus on establishing instance-dependent bounds, our work stands in stark contrast to previous works that focus on establishing worst-case regrets for offline RL with preference feedback.

## 1 Introduction

Reinforcement Learning (RL) (Sutton and Barto,, ) has been widely recognized for its capacity to facilitate agents in learning a sequence of optimal actions through iterative interactions with their environments. However, RL encounters significant hurdles in environments that are characterized by uncertainty or lacking explicit reward signals. To address these shortcomings, the concept of RL with human feedback (or RLHF) has emerged as a prominent paradigm. Preference-based RL (PbRL) (Christiano et al.,, ; Chen et al.,, ; Ibarz et al.,, ; Palan et al.,, ) has stood out as one of the most widely used frameworks for RLHF. In this regard, preference-based RL has achieved remarkable performances in practical applications, with particular importance lying in its ability to align large language models (LLMs) with human intent, thereby mitigating the output of toxic and dishonest information (Ouyang et al.,, ; Ziegler et al.,, ; Glaese et al.,, ; Bai et al.,, ; Liu et al.,, ), and improving the quality of applying to the specific tasks (Stiennon et al.,, ; Wu et al.,, ; Nakano et al.,, ).

In this work, we tackle the problem of offline RL with preference feedback, wherein the learning mechanism operates solely on pre-existing (or offline) data without dynamically engaging with the environment. Given the high cost associated with human interaction, offline RL has assumed particular importance in the context of incorporating human feedback. The significance of this offline framework has been justified by many previous prominent works (Shin et al.,, ; Ouyang et al.,, ; Zhu et al.,, ; Kim et al.,, ). For instance, within the learning process of InstructGPT (Ouyang et al.,, ), a pivotal procedure involves the training of a reward model utilizing pre-trained LLM feature vectors, coupled with the utilization of pre-collected human preference feedback as the training dataset. Conceptually, this procedure can be construed as treating the current prompt context as a state within a certain Markov Decision Process (MDP), while the responses generated by the LLM serve as actions within this process. Empirical findings presented by Ouyang et al., () demonstrate the efficacy of this offline framework in effectively aligning human intent with the outputs of LLMs.

However, the literature concerning theoretical analyses within the domain of offline PbRL remains rather scant. Previous theoretical analyses (Zhu et al.,, ; Zhan et al.,, ) of offline PbRL predominantly focused on the worst-case (or minimax) regret, often resulting in the derivation of regret upper bounds for their algorithms of the form $\tilde{O}(n^{-1/2})$, where $n$ is the size of the offline dataset. In this work, we adopt a different approach that is centered on instance-dependent guarantees. In other words, we wish to derive performance guarantees that are functions of the specific problem instance, thus elucidating the role of fundamental hardness parameters. This yields complementary insights to the existing worst-case analyses. To this end, we design and analyze RL-LOW, a preference-based RL algorithm. Our analysis of the performance RL-LOW unveils an instance-dependent simple regret bound of $\exp(-\Omega(n/H))$, where $H$ is a hardness parameter. This reveals that the simple regret decays exponentially fast in the size of the dataset $n$ and the exponential rate of convergence has also been identified. Complementarily, by proving an instance-dependent lower bound, we show that any algorithm will suffer from a simple regret of at least $\exp(-O(n/H))$. Thus, the dependence of the problem on $H$ is fundamental and cannot be improved upon, thereby demonstrating the efficacy of RL-LOW and the tightness of our analyses.

### 1.1 Related works

Preference-based RL:
From the empirical viewpoint, Christiano et al., () initially demonstrated that RL systems can effectively address complex tasks like Atari games and simulated robot locomotion by learning from human preferences between trajectory segments. Later, numerous researchers started to employ human preference feedback to enhance the performance of LLMs, e.g., aligning the LLMs’ behavior with human intent (Ouyang et al.,, ; Ziegler et al.,, ; Glaese et al.,, ; Bai et al.,, ; Liu et al.,, ), and enhancing the efficacy of application to specific tasks (Stiennon et al.,, ; Wu et al.,, ; Nakano et al.,, ).

From the theoretical perspective, the existing literature remains sparse in offline RL with preference feedback. Zhu et al., () elucidated the failure of the maximum likelihood estimation (MLE) procedure in some scenarios. Motivated by this, they theoretically prove the (near) minimax optimality of the Pessimistic MLE approach with a high probability guarantee. In addition,  Zhan et al., () introduced a novel paradigm for general reward functions, and they introduce $\varepsilon$-bracket approximations for reward models, accompanied by a rigorous theoretical analysis delineating sample complexity in terms of approximation error $\varepsilon$ and the high-probability parameter $\delta$.

We observe that the above theoretical investigations, while invaluable, are not instance-dependent. Typically, the above minimax or worst-case guarantees yield upper bounds in the form of $\tilde{O}(n^{-1/2})$ and do not depend on any problem-specific factors (such as suboptimality gaps). Our research stands out as a pioneering attempt in offering an instance-dependent examination for offline RL with preference feedback, thereby bridging a critical gap in the existing literature.

Label-Differential Privacy: In our study, we also consider the notion of label privacy, acknowledging that the labels in our offline dataset originate from users, thus highlighting the imperative to protect user privacy.
Chaudhuri and Hsu, () were among the pioneers in exploring the concept of label privacy within the context of supervised learning for binary classification. Their foundational work posits that the sensitive information primarily resides in the labels, while considering the unlabeled attributes as non-sensitive. Later, the concept of label privacy has been investigated across various machine learning paradigms, including but not limited to PAC learning (Beimel et al.,, ) and deep learning frameworks (Ghazi et al.,, ). This broadened examination underscores the significance and relevance of label privacy considerations across diverse areas of machine learning research and applications.

More recently, Chowdhury et al., () investigated the use of label differential privacy to protect the privacy of human labelers in the process of estimating rewards from preference-based feedback. Chowdhury et al., () derive an upper bound for their proposed algorithm on the estimation error. They show that it also decays as $O(n^{-1/2})$ and the implied constant here depends on $(\varepsilon,\delta)$, the parameters that define differential privacy. This bound only applies in the scenario of estimating the reward value and is not applicable if we want to understand how it depends on the simple regret of a specific instance. In our work, we consider the effect of $(\varepsilon,\delta)$-DP on the simple regret.

### 1.2 Our contributions

We summarize our main contributions as follows:

- 1.
We establish the first-of-its-kind instance-dependent lower bound characterized by suboptimality gaps for a given problem instance. Our analysis reveals that this lower bound takes the form $\exp(-O({n}/{H}))$, where $H$ is a hardness parameter that is an explicit function of the suboptimality gaps. This finding furnishes a novel, and possibly generalizable, analytical approach for assessing algorithmic performance within the realm of preference-based RL.
- 2.
We design a simple algorithm RL-LOW based on the novel concept of locally optimal weights. Our analysis demonstrates that its expected simple regret matches the aforementioned instance-dependent lower bound (in the exponential decay rate of the simple regret), thus revealing our algorithm’s achievement of instance-dependent optimality.
- 3.
We adapt RL-LOW to the $(\varepsilon,\delta)$-differential privacy paradigm by combining the Gaussian mechanism with the aforementioned locally optimal weights. Our analysis demonstrates that, for large datasets, this combination enables our algorithm to achieve differential privacy without weakening the bound on the simple regret, underscoring the superiority of the design and analysis of RL-LOW.
- 4.
As a by-product of our analyses, we show that RL-LOW achieves a worst-case bound of the form $O(n^{-1/2})$. If we translate the high-probability upper bound in Zhu et al. Zhu et al., () to the same worst-case setting, we obtain a bound of the form $O(\sqrt{n^{-1}\log n})$. Thus, our work provides a noticeable (albeit small) improvement over the state-of-the-art theoretical result in Zhu et al., ().

## 2 Preliminaries and Problem Setup

Let $\mathcal{S}=\{1,\ldots,S\}$ denote the state space, and $\mathcal{A}=\{1,\ldots,A\}$ denote the action set. We assume that there is an unknown non-degenerate distribution $\rho=(\rho_{1},\ldots,\rho_{S})$ over the states, i.e., $\rho_{k}>0$ for all $k\in\mathcal{S}$. The $i$-th action of state $k$ is associated with the feature vector $\phi(k,i)\in\mathbb{R}^{d}$, and its associated (unknown) reward is

$$ $r_{k,i}=\langle\phi(k,i),\theta\rangle,$ (1) $$

where $\theta\in\mathbb{R}^{d}$ is an unknown parameter vector. The collection of all feature vectors is denoted as $\phi=\{\phi(k,i)\}_{k\in\mathcal{S},i\in\mathcal{A}}$. For all $k\in\mathcal{S}$, we denote the suboptimaliy gap of action $i\in\mathcal{A}$ as $\Delta_{k,i}=\max_{j\in\mathcal{A}}r_{k,j}-r_{k,i}$. Let $(a^{(0)},a^{(1)})\in\mathcal{A}^{2}$ be a pair of comparisons and let $s\in\mathcal{S}$ be a state. Then, we define a stochastic label $\sigma$, following the Bradley–Terry–Luce (BTL) model as

$$ $\mathbb{P}\big{(}\sigma=1\mid a^{(0)},a^{(1)},s\big{)}=\frac{\exp\big{(}r_{s,a ^{(1)}}\big{)}}{\exp\big{(}r_{s,a^{(0)}}\big{)}+\exp\big{(}r_{s,a^{(1)}}\big{) }}.$ (2) $$

Given this model, we assume throughout that we have access to an offline dataset, which we denote as
$\mathcal{D}=\{({s}_{i},{a}^{(0)}_{i},{a}^{(1)}_{i},\sigma_{i})\}_{i=1}^{n}$. Note that this dataset consists of $n$ tupies of states, pairs of actions for comparison, and stochastic labels. Without loss of generality, we assume that the comparisons are arranged such that $a^{(0)}_{i}<a^{(1)}_{i}$ for all $i=1,\ldots,n$, and $a^{(0)}_{i}<a^{(0)}_{j}$ (or $a^{(1)}_{i}\leq a^{(1)}_{j}$ if $a^{(0)}_{i}=a^{(0)}_{j}$) for all $i<j$.
For simplicity, we assume that the feature vectors satisfy $\phi(k,i)\neq\phi(k,j)$ for all states $k\in\mathcal{S}$ and all actions $i\neq j$. In addition, we assume that for each state $k$, the best action $i_{k}^{*}=\arg\max_{j\in\mathcal{A}}r_{k,j}$ is unique.
Broadly speaking, our objective is to use the offline dataset $\mathcal{D}$ to estimate the best action $i_{k}^{*}$ for each state $k\in\mathcal{S}$. Following  Zhu et al., (), we aim to design a (possibly randomised) policy $\pi$ that uses the dataset $\mathcal{D}$ to output a set of actions $\{\hat{i}_{k}\}_{k\in\mathcal{S}}$ that minimizes the simple regret(^1^11The term “simple regret” is referred to as “performance gap” in some existing works (e.g., Zhu et al., ()).) (averaged over all $S$ states), defined as

$$ $R_{n}=\sum_{k\in\mathcal{S}}\rho_{k}\big{(}r_{k,i^{*}_{k}}-r_{k,\hat{i}_{k}} \big{)}.$ (3) $$

Let $N\in\mathbb{R}^{S\times A\times A}$ be a tensor that collects the proportions of each comparison in the dataset $\mathcal{D}$. In particular, $N_{k,i,j}\coloneqq\frac{1}{n}\sum_{\iota=1}^{n}\mathbbm{1}\{s_{\iota}=k,a_{
\iota}^{(1)}=i,a_{\iota}^{(2)}=j\}$ is the proportion of the number of times actions $i$ and $j$ have been compared under state $k$. A problem instance, denoted as $v$, is completely characterised by the tuple $(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$.
In the following, we index instance-specific parameters with the instance $v$ to indicate their dependence on $v$; this will be omitted when the instance is clear from the context. In addition, we write $\mathbb{P}_{v}^{\pi}$ (resp. $\mathbb{E}_{v}^{\pi}$) to denote the probability measure (reps. the expectation) induced under policy $\pi$ and under the instance $v$. Other assumptions are as follows.

###### Assumption 2.1 .

(Bounded reward)
There exists a finite and known constant $L$ such that for any $k\in\mathcal{S}$ and $i\in\mathcal{A}$, it holds that $\lvert\langle\phi(k,i),\theta\rangle\rvert\leq L$.

In previous works (Zhu et al.,, ), the authors assume that the norms of the feature vectors $\phi(k,i)$ and parameter vector $\theta$ are separately bounded. This clearly implies that Assumption 2.1 is satisfied, but Assumption 2.1 is weaker as it is a bound on the rewards.

###### Definition 2.2 .

(Consistent instance)
A problem instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$ is consistent if for all $(k,i,j)\in\mathcal{S}\times\mathcal{A}^{2}$, it holds that
$\phi(k,i)-\phi(k,j)\in{\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},
j^{\prime}):(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^
{2}\text{ and }N_{k^{\prime},i^{\prime},j^{\prime}}>0\}.$

We say an instance $v$ is inconsistent if it is not consistent. In the following, we will be only concerned with those instances that are consistent as the following result shows that
it is impossible to design a policy that achieves vanishing simple regret for inconsistent instances.

###### Proposition 2.3 .

(Impossibility result)
For any inconsistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$, there exists an instance $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})$ such that for all policies $\pi$

$$ $\liminf_{n\rightarrow\infty}\big{\{}\mathbb{E}^{\pi}_{v}[R_{n}]+\mathbb{E}^{ \pi}_{v^{\prime}}[R_{n}]\big{\}}>0.$ (4) $$

###### Assumption 2.1 .

###### Definition 2.2 .

###### Proposition 2.3 .

## 3 The Proposed Algorithm: RL-LOW

In this section, we describe our computationally and statistically efficient algorithm for offline RL with preference feedback based on the novel idea of locally optimal weights for estimating the relative reward of each pair of actions. This algorithm, called RL-LOW, is simple and is presented formally in Algorithm 1. Before we describe its components, we introduce some notations.

First, we denote $B_{k,i,j}$ as the empirical success rate with the comparison of actions $i$ and $j$, i.e., for $k\in\mathcal{S}$ and $i,j\in\mathcal{A}$ with $N_{k,i,j}>0$

$$ $B_{k,i,j}\coloneqq\frac{1}{nN_{k,i,j}}\sum_{\iota=1}^{n}\sigma_{\iota}\mathbbm {1}\{s_{\iota}=k,a_{\iota}^{(1)}=i,a_{\iota}^{(2)}=j\},$ (5) $$

and $B_{k,j,i}\coloneqq 1-B_{k,i,j}$. If $N_{k,i,j}=N_{k,j,i}=0$, we define $B_{k,i,j}=B_{k,j,i}=0$.
Subsequently, certain empirical success rates may exhibit magnitudes that are either excessively large or small. We clip them by means of the following operation:

$$ ${B}_{k,i,j}^{\rm CLP}=\mathrm{CLIP}_{L}({B}_{k,i,j})\quad\mbox{where}\quad \mathrm{CLIP}_{L}(a)=\left\{\begin{array}[]{cc}\frac{\exp(2L)}{1+\exp(2L)}&a> \frac{\exp(2L)}{1+\exp(2L)}\\ \frac{1}{1+\exp(2L)}&a<\frac{1}{1+\exp(2L)}\\ a&\text{otherwise}\end{array}\right..$ (6) $$

In accordance with Assumption 2.1, the implicit rewards are bounded by $L$. Consequently, within our BTL model framework, the success rate of each comparison necessarily falls within the interval $\big{[}\frac{1}{1+\exp(2L)},\frac{\exp(2L)}{1+\exp(2L)}\big{]}$. We exploit this in (6) to ensure that the implementation of our clip operation is consistent with the model’s dynamics. We are now ready to introduce the notion of locally optimal weights, which plays a central role in the estimation of the rewards.

Figure: Algorithm 1 Reinforcement Learning with Locally Optimal Weights (RL-LOW)

###### Definition 3.1 .

(Locally Optimal Weight)
For an consistent instance $v$, let $\mathcal{U}_{k,i,j}=\{u\in\mathbb{R}^{S\times A\times A}:\phi(k,i)-\phi(k,j)=
\sum_{k^{\prime}\in\mathcal{S},i^{\prime},j^{\prime}\in\mathcal{A}}u_{k^{
\prime},i^{\prime},j^{\prime}}(\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{
\prime}))\;\mbox{and}\;u_{k^{\prime},i^{\prime},j^{\prime}}=0\;\mbox{if}\;N_{k
^{\prime},i^{\prime},j^{\prime}}=0\}$. We say that $w^{(k,i,j)}=(w_{k^{\prime},i^{\prime},j^{\prime}}^{(k,i,j)})_{k^{\prime}\in
\mathcal{S},i^{\prime},j^{\prime}\in\mathcal{A}}$ is a set of locally optimal weights for $(k,i,j)\in\mathcal{S}\times\mathcal{A}^{2}$ with $i\neq j$ if

$$ $w^{(k,i,j)}\in\operatorname*{argmin}_{u\in\mathcal{U}_{k,i,j}}\bigg{\{}\sum_{k ^{\prime}\in\mathcal{S},i^{\prime},j^{\prime}\in\mathcal{A}:N_{k^{\prime},i^{ \prime},j^{\prime}}>0}\frac{(u_{k^{\prime},i^{\prime},j^{\prime}})^{2}}{N_{k^{ \prime},i^{\prime},j^{\prime}}}\bigg{\}}.$ (7) $$

The weights in Eqn. (7) are described as “locally optimal” because they are customized to each $(k,i,j)$ tuple. Hence, $w^{(k,i,j)}$ is local to $(k,i,j)$. This is a novelty in the design of our algorithm.

By the definition of the consistency of an instance (cf. Definition 2.2), there exists a subset $\beta\subset\mathcal{S}\times\mathcal{A}^{2}$ such that $\phi(k,i)-\phi(k,j)\in{\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},
j^{\prime}):(k^{\prime},i^{\prime},j^{\prime})\in\beta\}.$ Hence, there exists a locally optimal weight for every pair of actions given a consistent instance. In addition, $w^{(k,i,j)}$ can be calculated efficiently by its analytic form (see details in Appendix C).

Equipped with the definition of locally-optimal weights, we now provide an estimate of the relative reward for state $k\in\mathcal{S}$ and pair of action $(i,j)\in\mathcal{A}^{2}$ with $i\neq j$ as follows:

$$ $\hat{r}_{k,i,j}=\sum_{k^{\prime}\in\mathcal{S},i^{\prime}\in\mathcal{A},j^{ \prime}\in\mathcal{A}}w^{(k,i,j)}_{k^{\prime},i^{\prime},j^{\prime}}\,\log\Big {(}\frac{B^{\rm CLP}_{k^{\prime},i^{\prime},j^{\prime}}}{1-B^{\rm CLP}_{k^{ \prime},i^{\prime},j^{\prime}}}\Big{)}.$ (8) $$

The term $\frac{(u_{k^{\prime},i^{\prime},j^{\prime}})^{2}}{N_{k^{\prime},i^{\prime},j^{
\prime}}}$ in Eqn. (7) is a proxy for the variance introduced by the pair of actions $(i^{\prime},j^{\prime})$ in state $k^{\prime}$ when associated with the coefficient $u_{k^{\prime},i^{\prime},j^{\prime}}$ in the linear combination of the definition of $\mathcal{U}_{k,i,j}$. Our objective is to minimize the cumulative variance proxy for $(k,i,j)$, thus enhancing the precision of the estimate of the relative reward for $(k,i,j)$ for the purposes of establishing the tightest possible concentration result for subGaussian random variables (see Appendix E).

Finally, for any $k\in\mathcal{S}$, let $\hat{i}_{k}\in\hat{\mathcal{I}}_{k}:=\{i\in\mathcal{A}:\hat{r}_{k,i,j}\geq 0,
\forall\,j\neq i\}$ be any estimate of the best action under state $k$. It is natural to wonder whether $\hat{i}_{k}$ exists, i.e., whether the set $\hat{\mathcal{I}}_{k}$ is empty. The following proposition answers this in the affirmative.

###### Proposition 3.2 .

For any consistent instance $v$ and using estimate of the best action under each state $k$ as prescribed by RL-LOW, we have $\lvert\hat{\mathcal{I}}_{k}\rvert\geq 1$, i.e., $\hat{i}_{k}$ exists.

###### Definition 3.1 .

###### Proposition 3.2 .

### 3.1 Upper Bound of RL-LOW

In this section, we provide an instance-dependent upper bound of the simple regret for Rl-LOW. In addition, we also provide a worst-case upper bound as a by-product. First, we define an instance-dependent hardness parameter $H(v)$.
Let

$$ $H(v)\coloneqq\max_{k\in\mathcal{S},i\in\mathcal{A}:i\neq i^{*}_{k}}\ \frac{ \gamma_{k,i}}{\Delta_{k,i}^{2}}\quad\mbox{where}\quad\gamma_{k,i}\coloneqq\sum _{k^{\prime}\in\mathcal{S},i^{\prime},j^{\prime}\in\mathcal{A}:N_{k^{\prime},i ^{\prime},j^{\prime}}>0}\frac{(w^{(k,i,i_{k}^{*})}_{k^{\prime},i^{\prime},j^{ \prime}})^{2}}{N_{k^{\prime},i^{\prime},j^{\prime}}}.$ (9) $$

The parameter $\gamma_{k,i}$ exhibits a positive correlation with the variance proxy of the relative empirical reward $\hat{r}_{k,i,i_{k}^{*}}$. Consequently, the ratio $\frac{\gamma_{k,i}}{\Delta_{k,i}^{2}}$ in the definition of $H(v)$ serves as a quantitative measure of the difficulty that the empirical reward of a suboptimal action $i$ surpasses that of $i^{*}_{k}$ in state $k$.

###### Theorem 3.3 .

(Instance-Dependent Upper Bound)
For any consistent instance $v$, under RL-LOW, we have for all sufficiently large $n$,

$$ $\mathbb{E}^{\rm RL\mbox{-}LOW}_{v}\left[R_{n}\right]\leq\exp\bigg{(}-\frac{n}{ C_{\rm up}\cdot H(v)}\bigg{)},$ (10) $$

where $C_{\rm up}$ is a universal constant.(^2^22In this paper, our universal constants depend on $L$, which is known and fixed throughout.)

From Theorem 3.3, it is evident that the upper bound decays exponentially fast and the exponent is a function of an instance-dependent hardness term $H(v)$. This is the first instance-dependent analysis in offline reinforcement learning with preference feedback.

It is natural to wonder why we do not devise an instance-dependent analysis of or modification to Pessimistic MLE which was developed by Zhu et al., (). Note that Pessimistic MLE is designed to perform well with high probability and not necessarily in expectation. In particular, the regret bound of Pessimistic MLE holds with probability at least $1-\delta$. Hence, to ensure the regret is less than $\exp(-\Omega(n/H(v)))$, one should set the failure probability $\delta$ to be $\exp(-\Theta(n/H(v)))$, which is not possible as $H(v)$ is unknown to the algorithm (since $\theta$ is also unknown).

We further provide a worst-case upper bound for RL-LOW as follows.

###### Proposition 3.4 .

(Worst-Case Upper Bound)
For any consistent instance $v$ and for all $n\geq 1$,

$$ $\!\mathbb{E}^{\rm RL\mbox{-}LOW}_{v}\left[R_{n}\right]\!\leq\!\frac{\sum \limits_{\begin{subarray}{c}k,i:i\neq i^{*}_{k}\end{subarray}}\rho_{k}(\sqrt{ \gamma_{k,i}}\!+\!\tilde{\gamma}_{k,i})}{C_{\rm wup}\sqrt{n}}\;\,\mbox{where} \;\,\tilde{\gamma}_{k,i}\!=\!\sum_{\begin{subarray}{c}k^{\prime},i^{\prime},j^ {\prime}:N_{k^{\prime},i^{\prime},j^{\prime}}>0\end{subarray}}\frac{\lvert w^{ (k,i,i_{k}^{*})}_{k^{\prime},i^{\prime},j^{\prime}}\rvert}{\sqrt{N_{k^{\prime} ,i^{\prime},j^{\prime}}}}$ (11) $$

and $C_{\rm wup}>0$ is a universal constant.

We note that in Zhu et al., (), the high probability upper bound is of the form $O\big{(}\sqrt{n^{-1}\log(1/\delta)}\big{)}$. Hence, if we desire a bound in expectation, we obtain, through the law of total probability, a bound of the form $\mathbb{E}[R_{n}]=O\big{(}\sqrt{n^{-1}\log(1/\delta)}+\delta\big{)}$. Minimizing this bound over $\delta$ yields $\mathbb{E}[R_{n}]=O\big{(}\sqrt{n^{-1}\log n}\big{)}$, which is slightly inferior to our upper bound $O(n^{-1/2})$.

###### Theorem 3.3 .

###### Proposition 3.4 .

## 4 Instance-Dependent Lower Bound

In this section, we derive the first-of-its-kind instance-dependent lower bound on offline RL with preference feedback.
Before we present our bound, we present some auxiliary lemmas that are potentially instrumental in deriving lower bounds on other preference-based RL problems.

Given any instance $v$, we let $P_{v}^{(n)}$ denote the joint distribution of the associated labels $\{\sigma_{i}\}_{i=1}^{n}$. The following lemma provides an estimate of the Kullback–Leibler (KL) divergence between instances $v$ and $v^{\prime}$ that share the same parameters except for the latent vector $\theta$ that defines the reward in (1).

###### Lemma 4.1 .

For any instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$ and $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})$, it holds that

$$ $\displaystyle 2n\exp(-4R_{\max})\leq\frac{D_{\rm KL}(P_{v}^{(n)}\|P_{v^{\prime }}^{(n)})}{\tilde{D}(v,v^{\prime})}\leq 2n\exp(2R_{\max})$ (12) $$

where

$$ $\displaystyle\tilde{D}(v,v^{\prime})=\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N _{k,i,j}(\langle\phi(k,i)-\phi(k,j),\theta-\theta^{\prime}\rangle)^{2},$ (13) $$

and where $R_{\max}=\max_{k\in\mathcal{S},i\in\mathcal{A}}\max\{\lvert\langle\phi(k,i),
\theta\rangle\rvert,\lvert\langle\phi(k,i),\theta^{\prime}\rangle\rvert\}$ is the maximum absolute reward in these two instances.

This lemma demonstrates that when the rewards are bounded, the weighted sum of squared differences of the relative rewards can be used to approximate the KL divergence between the distributions of two instances. The approximation is precisely $\tilde{D}(v,v^{\prime})$ defined in (13).
Furthermore, for any $\mathbb{z}\in\mathbb{R}^{d}$, $\eta\in\mathbb{R}$ and consistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$, we let ${\rm Alt}(v,\mathbb{z},\eta)$ be the set of instances that share the same instance parameters except for $\theta$ and satisfies
$\langle\mathbb{z},\theta^{\prime}-\theta\rangle=\eta$
for all $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})\in{\rm Alt}(v
,\mathbb{z},\eta)$.
The following lemma states a useful property that relates the ${\rm Alt}$ set to the “approximate KL divergence” $\tilde{D}$.

###### Lemma 4.2 .

Let $\mathcal{G}$ be an arbitrary orthonormal basis of ${\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime}):(k^{\prime
},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}\text{ and }N_{k^{
\prime},i^{\prime},j^{\prime}}>0\}$. Also let $[\mathbf{w}]_{\mathcal{G}}$ denote the column vector that represents $\mathbf{w}$ under basis $\mathcal{G}$ (Meyer,, , Chapter 4). Define the matrix

$$ $V\coloneqq\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N_{k,i,j}[\phi(k,i)-\phi(k,j )]_{\mathcal{G}}[\phi(k,i)-\phi(k,j)]_{\mathcal{G}}^{\top}.$ (14) $$

Then for any consistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$, $\eta\in\mathbb{R}$, and $\mathbb{z}\in{\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime
}):(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}\text{
and }N_{k^{\prime},i^{\prime},j^{\prime}}>0\}$,

$$ $\min_{v^{\prime}\in{\rm Alt}(v,\mathbb{z},\eta)}\tilde{D}(v,v^{\prime})=\frac{ \eta^{2}}{\lVert[\mathbb{z}]_{\mathcal{G}}\rVert^{2}_{V^{-1}}}.$ (15) $$

Lemma 4.2 provides an estimate of the KL divergence between instance $v$ and $v^{\prime}\in{\rm Alt}(v,\mathbb{z},\eta)$. This, in turn, provides a convenient means to apply the ubiquitous change of measure technique to derive the lower bound.

In addition, let $(\bar{i}$, $\bar{k})$ be the state-action pair that attains maximum in the definition of hardness in Eqn. (9). Define the subset of instances

$$ $\mathcal{Q}=\bigg{\{}v\mbox{ consistent}:\frac{\gamma_{\bar{k},\bar{i}}}{ \Delta_{\bar{k},\bar{i}}^{2}}\geq 4\frac{\gamma_{k,i}}{\Delta_{k,i}^{2}}\;\; \forall\,(k,i)\neq(\bar{k},\bar{i})\;\mbox{and}\;i\neq i^{*}_{k}\bigg{\}}.$ (16) $$

We are now ready to state our lower bound.

###### Theorem 4.3 .

(Instance-Dependent Lower Bound)
For any instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)\in\mathcal{{\mathcal{Q}}}$, there exists another instance $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})$ with $H(v)\leq H(v^{\prime})\leq 8H(v)$ such that for all sufficiently large $n$,

$$ $\inf_{\pi}\big{\{}\mathbb{E}_{v}^{\pi}[R_{n}]+\mathbb{E}_{v^{\prime}}^{\pi}[R_ {n}]\big{\}}\geq\exp\bigg{(}-\frac{n}{C_{\mathrm{lo}}\cdot H(v)}\bigg{)},$ $$

where $C_{\mathrm{lo}}>0$ is a universal constant.

The alternative instance $v^{\prime}$ that appears in Theorem 4.3 is judiciously chosen to be $v^{\prime}\in{\rm Alt}(v,\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{k}(v),i^{*}_{
\bar{k}}(v)),2\Delta_{\bar{k}(v),\bar{i}(v)}(v))$. In particular, it is designed so that the optimal action $i^{*}_{\bar{k}}$ under state $k$ of instance $v$ will become suboptimal under instance $v^{\prime}$, and its suboptimality gap is at least $\Delta_{\bar{k}(v),\bar{i}(v)}(v)$ under $v^{\prime}$.

Theorem 4.3 is an instance-dependent lower bound for all instances in the set $\mathcal{Q}$. The condition that defines $\mathcal{Q}$ in Eqn. (16) ensures that the hardness quantities $H(v)$ and $H(v^{\prime})$ have the same order.
Since instances in $\mathcal{Q}$ cover all possible hardness values $H(v)$ (i.e., for every hardness values $h>0$, there exists an instance in $\mathcal{Q}$ of hardness $h$), we conclude that for any consistent instance $v$ and (small) $\epsilon\in(0,1)$,
there does not exist any policy $\pi$ that achieves

$$ $\mathbb{E}_{v}^{\pi}[R_{n}]=\exp\bigg{(}-\Omega\Big{(}\frac{n}{H(v)^{1- \epsilon}}\Big{)}\bigg{)}.$ (17) $$

In this sense, the exponential decay rate of the simple regret of RL-LOW presented in Theorem 3.3 is asymptotically tight (or optimal) and the exponential dependence on the hardness parameter $H(v)$ is necessary, fundamental, and cannot be improved upon.

###### Lemma 4.1 .

###### Lemma 4.2 .

###### Theorem 4.3 .

## 5 Extension to ( ε , δ ) 𝜀 𝛿 (\varepsilon,\delta) ( italic_ε , italic_δ ) -Differential Privacy (DP)

In this section, we extend our algorithm RL-LOW to be amenable to $(\varepsilon,\delta)$-differential privacy.
To formalize our results, we provide the definition of $(\varepsilon,\delta)$-DP, following Dwork et al., ().
We say that two sets of preference labels, $\sigma:=\{\sigma_{i}\}_{i=1}^{n}$ and $\sigma^{\prime}:=\{\sigma^{\prime}_{i}\}_{i=1}^{n}$ are neighboring if there exists $s\in[n]$ such that $\sigma_{s}\neq\sigma^{\prime}_{s}$ and $\sigma_{j}=\sigma^{\prime}_{j}$ for all $j\neq s$.

###### Definition 5.1 .

(Differential Privacy)
Fix any label-free dataset $\{(s_{i},a^{(1)}_{i},a^{(2)}_{i})\}_{i=1}^{n}$. A (randomized) policy $\mathcal{M}:\{0,1\}^{n}\rightarrow\mathcal{A}^{S}$ (that takes as inputs a set of labels and outputs a set of actions, one for each state) satisfies $(\varepsilon,\delta)$-DP if for all neighboring labels $\sigma:=\{\sigma_{i}\}_{i=1}^{n}$ and $\sigma^{\prime}:=\{\sigma^{\prime}_{i}\}_{i=1}^{n}$,

$$ $\mathbb{P}(\mathcal{M}(\sigma)\in\mathcal{Z})\leq e^{\varepsilon}\,\mathbb{P}( \mathcal{M}(\sigma^{\prime})\in\mathcal{Z})+\delta\qquad\forall\,\mathcal{Z} \subset\mathcal{A}^{S}.$ (18) $$

Note that Definition 5.1 primarily concerns protecting the privacy of users’ labels. In particular, the DP mechanism guarantees that any alteration in a user’s label must not substantially affect the output of our algorithm. Otherwise, there exists a risk that a user’s label might be inferred through the algorithm’s output. Our definition of differential privacy (DP) aligns with that of Chowdhury et al., ().

We now adapt our RL-LOW to $(\varepsilon,\delta)$-DP by using the Gaussian mechanism  (Dwork et al.,, ). Firstly, we introduce the private version of the empirical success rate (analogous to $B_{k,i,j}$ in (5)) which we denote as

$$ $\tilde{B}_{k,i,j}\coloneqq\frac{1}{nN_{k,i,j}}\sum_{\iota=1}^{n}\sigma_{\iota} \mathbbm{1}\{s_{\iota}=k,a_{\iota}^{(1)}=i,a_{\iota}^{(2)}=j\}+\tilde{\xi}_{k, i,j}\ \ \forall\,k\in\mathcal{S},(i,j)\in\mathcal{A}^{2}\text{ with }{N_{k,i,j }>0},$ $$

where $\tilde{\xi}_{k,i,j}$ is an independent (across $k$, $i$, and $j$) Gaussian noise with zero mean and variance $\frac{2\log(1.25/\delta)}{(\varepsilon nN_{k,i,j})^{2}}$, and we let $\tilde{B}_{k,j,i}\coloneqq 1-\tilde{B}_{k,i,j}$. If $N_{k,i,j}=N_{k,j,i}=0$, we define $\tilde{B}_{k,i,j}=\tilde{B}_{k,j,i}=0$. Again, analogously to the operation in (6), we clip $\tilde{B}_{k,i,j}$ to form

$$ $\tilde{B}_{k,i,j}^{\rm CLP}=\mathrm{CLIP}_{L}(\tilde{B}_{k,i,j})$ (19) $$

Similarly to Eqn. (8), the perturbed estimated relative rewards are given as follows

$$ $\tilde{r}_{k,i,j}=\sum_{k^{\prime}\in\mathcal{S},(i^{\prime},j^{\prime})\in \mathcal{A}^{2}}w^{(k,i,j)}_{k^{\prime},i^{\prime},j^{\prime}}\,\log\Big{(} \frac{\tilde{B}^{\rm CLP}_{k^{\prime},i^{\prime},j^{\prime}}}{1-\tilde{B}^{\rm CLP }_{k^{\prime},i^{\prime},j^{\prime}}}\Big{)},$ (20) $$

where $w^{(k,i,j)}$ is defined in Definition 3.1. Finally, the empirical best action is $\hat{i}_{k}\in\tilde{\mathcal{I}}_{k}:=\{i\in\mathcal{A}:\tilde{r}_{k,i,j}\geq
0
,\forall\,j\neq i\}$. A similar argument as Proposition 3.2 shows that $\hat{i}_{k}$ exists; see details in Appendix C for the details. The algorithm described above is a differentialy private version of the RL-LOW policy and hence, it is named DP-RL-LOW.

DP-RL-LOW with the carefully chosen variance of $\xi_{k,i,j}$ fulfils the requirement of $(\varepsilon,\delta)$-DP.

###### Proposition 5.2 .

Given privacy parameters $\varepsilon,\delta>0$, DP-RL-LOW satisfies $(\varepsilon,\delta)$-DP.

The proof of Proposition 5.2 follows exactly along the lines of the proof of Dwork et al., (, Theorem A.1) and is omitted.
We next upper bound the expected simple regret of DP-RL-LOW.

###### Theorem 5.3 .

(Instance-Dependent Upper Bound for DP-RL-LOW)
Given any consistent instance $v$, for all sufficiently large $n$,

$$ $\mathbb{E}^{\rm DP\mbox{-}RL\mbox{-}LOW}_{v}\left[R_{n}\right]\leq\exp\bigg{(} -C_{\rm DP}\cdot\Big{(}\frac{n}{H(v)}\land\Big{(}\frac{n}{H_{\rm DP}^{( \varepsilon,\delta)}(v)}\Big{)}^{2}\Big{)}\bigg{)},$ (21) $$

where $C_{\rm DP}>0$ is a universal constant, and

$$ $\!\!H_{\rm DP}^{(\varepsilon,\delta)}(v)\!=\!\max_{k\in\mathcal{S},i\in \mathcal{A}:i\neq i^{*}_{k}}\frac{\sqrt{\log(\frac{1.25}{\delta})\gamma^{\rm DP }_{k,i}}}{\sqrt{\varepsilon}\Delta_{k,i}}\;\;\text{and}\;\;\gamma_{k,i}^{\rm DP }\!=\!{\sum_{k^{\prime},i^{\prime},j^{\prime}\in\mathcal{A}:N_{k^{\prime},i^{ \prime},j^{\prime}}>0}\left(\frac{w^{(k,i,i^{*}_{k})}_{k^{\prime},i^{\prime},j ^{\prime}}}{N_{k^{\prime},i^{\prime},j^{\prime}}}\right)^{2}}.$ (22) $$

Consequently,

$$ $\limsup_{n\rightarrow\infty}\frac{1}{n}\log\mathbb{E}^{\rm DP\mbox{-}RL\mbox{- }LOW}_{v}\left[R_{n}\right]\leq-\frac{C_{\mathrm{DP}}}{H(v)}.$ (23) $$

The limiting statement in (23) implies that DP-RL-LOW has the same order of the exponential decay rate as its non-differentially privacy counterpart RL-LOW when $n$ is sufficiently large; in particular, $n>{(H_{\rm DP}^{(\varepsilon,\delta)}(v))^{2}}/H(v)$ suffices to nullify the effect of the privacy requirement. In other words, in the sense of the exponent, privacy comes “for free” for sufficiently large offline datasets.

###### Definition 5.1 .

###### Proposition 5.2 .

###### Theorem 5.3 .

## 6 Numerical Simulations

Figure: Figure 1: Comparison of RL-LOW and DP-RL-LOW to Pessimistic MLE (Zhu et al.,, ) on average simple regret and standard deviation (shaded area). In the left figure, we set $\delta=0.2$ and $\varepsilon=2.0$ for DP-RL-LOW. In the right figure, we set $n=300$ for all policies, and $\varepsilon$ does not apply to RL-LOW.
Refer to caption: x1.png

In this section, we present some numerical simulations of our algorithm RL-LOW and and its differentially private counterpart DP-RL-LOW. We compare them to the state-of-the-art (non-private algorithm) Pessimistic MLE developed by Zhu et al., (). We conduct the experiments on a synthetic dataset. Specifically, we set the number of states $S=2$, the number of actions $A=10$, the dimensionality of the data $d=5$, the unknown parameter vector $\theta=[1,1,1,1,1]^{\top}$, and the state distribution $\rho=[0.4,0.6]$. The feature vector of each action is generated as follows: For the $i$-th action of state $k\in\{1,2\}$, we first uniformly generate a $d$-dimentional vector $\phi^{\prime}(k,i)$ with all non-negative elements and $\lVert\phi^{\prime}(k,i)\rVert_{1}=1$. Then, for each state $k\in\{1,2\}$, we set the feature vector of $i$-th action as $\phi(k,i)=\phi^{\prime}(k,i)-0.01(i-1)\theta$. That is, in both state $1$ and $2$, the best action is the first action, and the suboptimality gap of the $i$-th action is $0.05i$. In addition, for both states $k\in\{1,2\}$ and $i<j$, we set $N_{k,i,j}=\frac{1}{A(A-1)}$, i.e., the proportions of comparisons for this instance are uniform. In the simulation, we use $\lceil N_{k,i,j}n\rceil$ as the number of samples involved in the comparison between actions $i$ and $j$ under state $k$.

As for the hyperparameters of Pessimistic MLE, we follow the default setting of Zhu et al., (, Section 3). In addition, Pessimistic MLE only works under the assumption that $\langle 1,\theta\rangle=0$ (Zhu et al.,, , Assumption 2.1). Therefore, when running the experiments of Pessimistic MLE, we further set $d=6$, $\theta=[1,1,1,1,1,-5]$ and the $6$-th element of each feature vector is set to 0 0. Then, this new instance is mathematically equivalent to the original instance and additionally satisfies (Zhu et al.,, , Assumption 2.1) which is needed for Pessimistic MLE.

The simulation results are shown in Figure 1. We run each experiment $200$ times, and report the average and standard deviation. From Figure 1 (left), we observe that RL-LOW is inferior to Pessimistic MLE for small $n$. However, since RL-LOW is instance-dependent optimal in the exponential decay rate and in its dependence on the hardness parameter $H(v)$, the experimental findings depicted in Figure 1 (left) corroborate the empirical superiority of our proposed RL-LOW algorithm over Pessimistic MLE for $n$ sufficiently large ($n>150$ suffices). This observation underscores the efficacy of our novel algorithmic design based on locally optimal weights. Furthermore, from Figure 1 (left), we also observe that as the sample size $n$ increases, the performance of DP-RL-LOW converges to that of RL-LOW, consistent with our theoretical findings in Theorem 5.3.

Lastly, as shown in Figure 1 (right), it is evident that achieving comparable performance between RL-LOW and DP-RL-LOW may necessitate substantially larger sample sizes $n$ when considering small privacy parameters of $\varepsilon$ and $\delta$. This observation is again consistent with our theoretical findings in Theorem 5.3.

## 7 Concluding Remarks

This paper addresses the problem of offline RL with preference feedback, aiming to determine the optimal action for each state to minimize the simple regret. We introduced a novel algorithm, RL-LOW, which achieves a simple regret of $\exp(-\Omega(n/H(v))$, where $n$ represents the number of data samples and $H(v)$ characterizes an instance-dependent hardness parameter related to the suboptimality gaps of each action.
Additionally, we established a first-of-its-kind instance-dependent lower bound for offline RL with preference feedback, demonstrating the order-wise optimality of RL-LOW (in the exponential decay rate) through the matching of lower and upper bounds on the simple regret. To address privacy concerns, we extended RL-LOW to be amenable to $(\varepsilon,\delta)$-differential privacy, revealing that the hardness parameter $H(v)$ remains unchanged in the asymptotic regime as $n$ tends to infinity. This underscores RL-LOW’s effectiveness and robustness in preserving the privacy of observed rewards. Our focus on establishing instance-dependent bounds sets this work apart from previous research that focuses primarily on worst-case regret analyses in offline RL with preference feedback.

Some interesting directions for future research include extending our work to incorporate general reward functions (Zhan et al.,, ). In particular, a natural question concerns whether or not there exist an algorithm that is instance-dependent and order-optimal for general reward functions?

## Appendix A Useful facts

In this section, we collate some useful facts that will be used in the subsequent proofs.

###### Definition A.1 (SubGaussian norm) .

A random variable $X$ is subGassian if it has a finite subGaussian norm denoted as $\|X\|_{\psi_{2}}$ and defined as

$$ $\|X\|_{\psi_{2}}=\inf\left\{c>0:\mathbb{E}\left[\exp\left(\frac{X^{2}}{c^{2}} \right)\right]\leq 2\right\}<+\infty.$ $$

###### Definition A.2 (Variance proxy) .

The variance proxy of a subGaussian random variable $X$ is denoted as $\|X\|_{\rm vp}^{2}$ and defined as

$$ $\|X\|_{\rm vp}^{2}\coloneqq\inf\left\{s^{2}>0:\mathbb{E}\left[\exp({(X-\mathbb {E}[X])t})\right]\leq e^{\frac{s^{2}t^{2}}{2}},\;\;\forall\,t>0\right\}.$ $$

###### Lemma A.3 (Linear combination of subGaussian random variables) .

Let $X_{1},\ldots,X_{n}$ be independent subGaussian random variables, where the variance proxy of $X_{i}$ is $\sigma_{i}^{2}$ . Then, for any $a_{1},\dots,a_{n}\in\mathbb{R}$, the random variable $\sum_{i=1}^{n}a_{i}X_{i}$ is a subGaussian random variable with variance proxy $\sigma^{2}=\sum_{i=1}^{n}a_{i}^{2}\sigma_{i}^{2}$.

###### Lemma A.4 .

(Tail bound of subGassian random variables)
Suppose $X$ is subGaussian with variance proxy $\sigma^{2}$. Then, for any $\epsilon>0$, we have

$$ $\operatorname{Pr}(X-\mathbb{E}[X]\geq\epsilon)\leq\exp\left(-\epsilon^{2}/ \left(2\sigma^{2}\right)\right),$ $$

and

$$ $\operatorname{Pr}(X-\mathbb{E}[X]\leq-\epsilon)\leq\exp\left(-\epsilon^{2}/ \left(2\sigma^{2}\right)\right),$ $$

###### Lemma A.5 .

(Adapted from (Vershynin,, , Proposition 2.5.2))
For any subGaussian random variable $X$,

$$ $\|X\|_{\rm vp}\leq C\|X\|_{\psi_{2}},$ $$

where $C\leq 6\sqrt{2e}\cdot(3\sqrt{\log 2}+1)$.
If $\mathbb{E}[X]=0$, then we have

$$ $\|X\|_{\psi_{2}}\leq\sqrt{6}\|X\|_{\rm vp}.$ $$

###### Definition A.1 (SubGaussian norm) .

###### Definition A.2 (Variance proxy) .

###### Lemma A.3 (Linear combination of subGaussian random variables) .

###### Lemma A.4 .

###### Lemma A.5 .

## Appendix B Proof of Proposition 2.3

###### Lemma B.1 .

For any inconsistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$, there exists $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $i\neq i^{*}_{k}$ such that

$$ $\phi(k,i)-\phi(k,i^{*}_{k})\notin{\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi( k^{\prime},j^{\prime})\>|\>N_{k^{\prime},i^{\prime},j^{\prime}}>0,(k^{\prime}, i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}\}.$ $$

###### Proof.

We prove this result by contradiction. Fix any inconsistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$. Assume that for all $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $i\neq i^{*}_{k}$, it holds

$$ $\phi(k,i)-\phi(k,i^{*}_{k})\in{\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{ \prime},j^{\prime})\>|\>N_{k,i,j}>0,(k^{\prime},i^{\prime},j^{\prime})\in \mathcal{S}\times\mathcal{A}^{2}\}.$ (24) $$

By the fact that $\phi(k,i)-\phi(k,j)=(\phi(k,i)-\phi(k,i^{*}_{k}))-(\phi(k,j)-\phi(k,i^{*}_{k})))$, Eqn. (24) implies that for any $(k,i,j)\in\mathcal{S}\times\mathcal{A}\times{A}$ with $i\neq j$, it holds

$$ $\phi(k,i)-\phi(k,j)\in{\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime}, j^{\prime})\>|\>N_{k,i,j}>0,(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S} \times\mathcal{A}^{2}\},$ (25) $$

which is a contradiction to that $v$ is inconsistent. This completes the proof of Lemma B.1.
∎

###### Proof of Proposition 2.3 .

Fix any inconsistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$. By Lemma B.1, there exists $(\underline{k},\underline{i})\in\mathcal{S}\times\mathcal{A}$ with $\underline{i}\neq i^{*}_{\underline{k}}$ such that

$$ $\phi(\underline{k},\underline{i})-\phi(\underline{k},i^{*}_{\underline{k}}) \notin{\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime})\>|\> N_{k^{\prime},i^{\prime},j^{\prime}}>0,(k^{\prime},i^{\prime},j^{\prime})\in \mathcal{S}\times\mathcal{A}^{2}\}.$ $$

That is, there exists a vector $\mathbb{z}\in\mathbb{R}^{d}$ such that

$$ $\langle\mathbb{z},\phi(\underline{k},\underline{i})-\phi(\underline{k},i^{*}_{ \underline{k}})\rangle=-2\langle\theta,\phi(\underline{k},\underline{i})-\phi( \underline{k},i^{*}_{\underline{k}})\rangle$ $$

and for all $(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}$ with $N_{k^{\prime},i^{\prime},j^{\prime}}>0$,

$$ $\langle\mathbb{z},\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime}) \rangle=0.$ $$

Finally, we let $\theta^{\prime}=\theta+\mathbb{z}$, and instance $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})$.
By the fact that
$\langle\theta,\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime})\rangle=
\langle\theta^{\prime},\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime})\rangle$ for all $(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}$ with $N_{k^{\prime},i^{\prime},j^{\prime}}>0$ we get that for all $n\geq 1$

$$ $D_{\rm KL}(P_{v}^{(n)},P_{v^{\prime}}^{(n)})=0.$ $$

Therefore, we get that $P_{v}^{(n)}$ is equal to $P_{v^{\prime}}^{(n)}$.
In addition, by definition of $R_{n}$, we get that

$$ $\displaystyle\mathbb{E}^{\pi}_{v}[R_{n}]+\mathbb{E}^{\pi}_{v^{\prime}}[R_{n}]$ $\displaystyle=\mathbb{E}_{v}^{\pi}\left[\sum_{k\in\mathcal{S}}\rho_{k}\left( \max_{j\in\mathcal{A}}\langle\phi(k,j)-\phi(k,\hat{i}_{k}),\theta\rangle\right )\right]+\mathbb{E}_{v^{\prime}}^{\pi}\left[\sum_{k\in\mathcal{S}}\rho_{k} \left(\max_{j\in\mathcal{A}}\langle\phi(k,j)-\phi(k,\hat{i}_{k}),\theta^{ \prime}\rangle\right)\right]$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}_{v}^{\pi}\left[\sum_{ k\in\mathcal{S}}\rho_{k}\left(\max_{j\in\mathcal{A}}\langle\phi(k,j)-\phi(k, \hat{i}_{k}),\theta\rangle+\max_{j\in\mathcal{A}}\langle\phi(k,j)-\phi(k,\hat{ i}_{k}),\theta^{\prime}\rangle\right)\right]$ (26) $\displaystyle\geq\rho_{\underline{k}}\min_{i\in\mathcal{A}}\left[\max_{j\in \mathcal{A}}\langle\phi(\underline{k},j)-\phi(\underline{k},i),\theta\rangle+ \max_{j\in\mathcal{A}}\langle\phi(\underline{k},j)-\phi(\underline{k},i), \theta^{\prime}\rangle\right],$ $$

where (a) follows from the fact that $P_{v}^{(n)}$ is equivalent with $P_{v^{\prime}}^{(n)}$.

Further, by the definition of $v$ and $v^{\prime}$, we get that

$$ $\min_{i\in\mathcal{A}}\left[\max_{j\in\mathcal{A}}\langle\phi(\underline{k},j) -\phi(\underline{k},i),\theta\rangle+\max_{j\in\mathcal{A}}\langle\phi( \underline{k},j)-\phi(\underline{k},i),\theta^{\prime}\rangle\right]>0,$ $$

and recall that $\rho_{\underline{k}}>0$. This completes the proof of Proposition 2.3

∎

###### Lemma B.1 .

###### Proof.

###### Proof of Proposition 2.3 .

## Appendix C The existence of i ^ k subscript ^ 𝑖 𝑘 \hat{i}_{k} over^ start_ARG italic_i end_ARG start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT in RL-LOW and DP-RL-LOW

We first provide analytical solutions of $w^{(k,i,j)}$ and $\gamma_{k,i,i^{*}_{k}}$.

###### Lemma C.1 .

Fix any consistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$. Recall the definitions of $w^{(k,i,j)}$ and $\gamma_{k,i,i^{*}_{k}}$ in Eqn. (7) and Eqn. (9), respectively. Then, for any $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $i\neq i^{*}_{k}$,

$$ $\gamma_{k,i,i^{*}_{k}}=\lVert[\phi(k,i^{*}_{k}-\phi(k,i)]_{\mathcal{G}}\rVert^ {2}_{V^{-1}}$ (27) $$

and for any $(k,i,j)\in\mathcal{S}\times\mathcal{A}^{2}$ with $i\neq j$,

$$ $w^{(k,i,j)}_{k^{\prime},i^{\prime},j^{\prime}}=N_{{k^{\prime}},{i^{\prime}},{j ^{\prime}}}[\phi({k^{\prime}},{i^{\prime}})-\phi({k^{\prime}},{j^{\prime}})]_{ \mathcal{G}}^{\top}V^{-1}[\phi(k,i)-\phi(k,j)]_{\mathcal{G}}$ (28) $$

where $V$ and $\mathcal{G}$ are as defined in Lemma 4.2.

###### Proof of Lemma C.1 .

Fix any $(k,i,j)\in\mathcal{S}\times\mathcal{A}^{2}$ with $i\neq j$.
By definition, the optimization problem of Eqn. (7) is equivalent to

$$ $\min_{u\in\mathbb{R}^{S\times A\times A}}\sum_{k^{\prime}\in\mathcal{S},i^{ \prime},j^{\prime}\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{\prime}}>0}\frac{ (u_{k^{\prime},i^{\prime},j^{\prime}})^{2}}{N_{k^{\prime},i^{\prime},j^{\prime }}}$ (29) $$

subject to

$$ $[\phi(k,i)-\phi(k,j)]_{\mathcal{G}}=\sum_{k^{\prime}\in\mathcal{S},i^{\prime}, j^{\prime}\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{\prime}}>0}u_{k^{\prime}, i^{\prime},j^{\prime}}[\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime}) ]_{\mathcal{G}}.$ $$

The Lagrangian of the above constrained optimization problem is

$$ $\displaystyle L(u,\lambda)=\sum_{k^{\prime}\in\mathcal{S},i^{\prime},j^{\prime }\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{\prime}}>0}\frac{(u_{k^{\prime},i^ {\prime},j^{\prime}})^{2}}{N_{k^{\prime},i^{\prime},j^{\prime}}}+\lambda^{\top }\bigg{(}[\phi(k,i)-\phi(k,j)]_{\mathcal{G}}$ $\displaystyle\hskip 85.35826pt-\sum_{k^{\prime}\in\mathcal{S},i^{\prime},j^{ \prime}\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{\prime}}>0}u_{k^{\prime},i^{ \prime},j^{\prime}}[\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime})]_{ \mathcal{G}}\bigg{)},$ $$

for $u\in\mathbb{R}^{S\times A\times A}$ and $\lambda\in\mathbb{R}^{\lvert\mathcal{G}\rvert}$.
Then, by solving $\frac{\mathrm{d}L}{\mathrm{d}\lambda}=0$ and $\frac{\mathrm{d}L}{\mathrm{d}u_{k^{\prime},i^{\prime},j^{\prime}}}=0$ for all $(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}$ with $N_{k^{\prime},i^{\prime},j^{\prime}}>0$, we obtain that the minimum of (29) is

$$ $\lambda=-2V^{-1}[\phi(k,i)-\phi(k,j)]_{\mathcal{G}}\\$ $$

and

$$ $u_{k^{\prime},i^{\prime},j^{\prime}}=N_{{k^{\prime}},{i^{\prime}},{j^{\prime}} }[\phi({k^{\prime}},{i^{\prime}})-\phi({k^{\prime}},{j^{\prime}})]_{\mathcal{G }}^{\top}V^{-1}[\phi(k,i)-\phi(k,j)]_{\mathcal{G}}$ (30) $$

for all $(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}$ with $N_{k^{\prime},i^{\prime},j^{\prime}}>0$.
That is, for any $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $i\neq i^{*}_{k}$,

$$ $\gamma_{k,i,i^{*}_{k}}=\lVert[\phi(k,i^{*}_{k})-\phi(k,i)]_{\mathcal{G}}\rVert ^{2}_{V^{-1}}$ (31) $$

This completes the desired proof.
∎

Then, we are ready to prove Proposition 3.2

###### Proof of Propostion 3.2 .

By Lemma C.1, we get that under RL-LOW, for any $(k,i,j,j_{2})\in\mathcal{S}\times\mathcal{A}^{3}$,

$$ $\displaystyle\hat{r}_{k,i,j}+\hat{r}_{k,j,j_{2}}$ $\displaystyle=\sum_{(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times \mathcal{A}^{2}}N_{{k^{\prime}},{i^{\prime}},{j^{\prime}}}[\phi({k^{\prime}},{ i^{\prime}})-\phi({k^{\prime}},{j^{\prime}})]_{\mathcal{G}}^{\top}V^{-1}[\phi( k,i)-\phi(k,j)]_{\mathcal{G}}\log\Big{(}\frac{B^{\rm CLP}_{k^{\prime},i^{ \prime},j^{\prime}}}{1-B^{\rm CLP}_{k^{\prime},i^{\prime},j^{\prime}}}\Big{)}$ $\displaystyle\hskip 28.45274pt+\sum_{(k^{\prime},i^{\prime},j^{\prime})\in \mathcal{S}\times\mathcal{A}^{2}}N_{{k^{\prime}},{i^{\prime}},{j^{\prime}}}[ \phi({k^{\prime}},{i^{\prime}})-\phi({k^{\prime}},{j^{\prime}})]_{\mathcal{G}} ^{\top}V^{-1}[\phi(k,j)-\phi(k,j_{2})]_{\mathcal{G}}\log\Big{(}\frac{B^{\rm CLP }_{k^{\prime},i^{\prime},j^{\prime}}}{1-B^{\rm CLP}_{k^{\prime},i^{\prime},j^{ \prime}}}\Big{)}$ $\displaystyle=\sum_{(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times \mathcal{A}^{2}}N_{{k^{\prime}},{i^{\prime}},{j^{\prime}}}[\phi({k^{\prime}},{ i^{\prime}})-\phi({k^{\prime}},{j^{\prime}})]_{\mathcal{G}}^{\top}V^{-1}[\phi( k,i)-\phi(k,j_{2})]_{\mathcal{G}}\log\Big{(}\frac{B^{\rm CLP}_{k^{\prime},i^{ \prime},j^{\prime}}}{1-B^{\rm CLP}_{k^{\prime},i^{\prime},j^{\prime}}}\Big{)}$ $\displaystyle=\hat{r}_{k,i,j_{2}},$ (32) $$

which implies that $\lvert\hat{\mathcal{I}}_{k}\rvert\geq 1$ under RL-LOW.
This completes the proof of Proposition 3.2.
∎

Following the same lines as the proof of Propostion 3.2, we get the corollary below.

###### Corollary C.2 .

For any consistent instance $v$ and using the estimate of the best action under each state $k$ as prescribed by RL-LOW-DP, we have $\hat{i}_{k}$ exists.

###### Lemma C.1 .

###### Proof of Lemma C.1 .

###### Proof of Propostion 3.2 .

###### Corollary C.2 .

## Appendix D Proof of Lower Bound

Before we prove the lower bound, we first give a useful corollary.
The following corollary is a direct result of Pinsker’s inequality.

###### Corollary D.1 .

Fix any $C\in(0,\frac{1}{2})$. For any $p,q\in(0,1)$ with $\min(p,1-p)\geq C$ and $\min(q,1-q)\geq C$, we have

$$ $2(p-q)^{2}\leq d_{\rm KL}(p,q)\leq\frac{2}{C}(p-q)^{2}$ $$

where $d_{\rm KL}(p,q)$ denotes the KL divergence between the Bernoulli distributions with parameters of $p$ and $q$.

Then, we prove Lemma 4.1 that reveals the KL divergence between instances. Recall that given any instance $v$, we let $P_{v}^{(n)}$ denote the distribution of $(\sigma_{i})_{i=1}^{n}$. The following lemma gives an estimation of the KL divergence between instance $v$ and $v^{\prime}$ that share the same parameters but $\theta$.

###### Lemma 4.1 .

For any instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$ and $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})$, it holds that

$$ $\displaystyle 2n\exp(-4R_{\max})\leq\frac{D_{\rm KL}(P_{v}^{(n)}\|P_{v^{\prime }}^{(n)})}{\tilde{D}(v,v^{\prime})}\leq 2n\exp(2R_{\max})$ (33) $$

where

$$ $\displaystyle\tilde{D}(v,v^{\prime})=\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N _{k,i,j}(\langle\phi(k,i)-\phi(k,j),\theta-\theta^{\prime}\rangle)^{2},$ (34) $$

and where $R_{\max}=\max_{k\in\mathcal{S},i\in\mathcal{A}}\max\{\lvert\langle\phi(k,i),
\theta\rangle\rvert,\lvert\langle\phi(k,i),\theta^{\prime}\rangle\rvert\}$ is the maximum absolute reward in these two instances.

###### Proof.

Fix any consistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$. By the chain rule of the KL divergence, we have

$$ $\displaystyle D_{\rm KL}(P_{v}^{(n)}\|P_{v^{\prime}}^{(n)})$ $\displaystyle=n\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N_{k,i,j}d_{\rm KL} \bigg{(}\frac{\exp(\langle\phi(k,i),\theta\rangle)}{\exp(\langle\phi(k,i), \theta\rangle)+\exp(\langle\phi(k,j),\theta\rangle)},$ $\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\frac{\exp( \langle\phi(k,i),\theta^{\prime}\rangle)}{\exp(\langle\phi(k,i,\theta^{\prime} \rangle)+\exp(\langle\phi(k,j),\theta^{\prime}\rangle)}\bigg{)}$ $\displaystyle=n\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N_{k,i,j}d_{\rm KL}({ \rm Sig}(\langle\phi(k,i)-\phi(k,j),\theta\rangle),{\rm Sig}(\langle\phi(k,i)- \phi(k,j),\theta^{\prime}\rangle))$ (35) $$

where ${\rm Sig}(\cdot)$ represents the Sigmoid function.
By the fact that $-2R_{\rm max}\leq\langle\phi(k,i)-\phi(k,j),\theta\rangle\leq 2R_{\rm max}$ and $-2R_{\rm max}\leq\langle\phi(k,i)-\phi(k,j),\theta^{\prime}\rangle\leq 2R_{\rm
max}$ and that $\frac{\mathrm{d}{\rm Sig}(x)}{\mathrm{d}x}=\frac{\exp(-x)}{(\exp(-x)+1)^{2}}$, we further get that

$$ $\displaystyle\lvert{\rm Sig}(\langle\phi(k,i)-\phi(k,j),\theta\rangle)-{\rm Sig }(\langle\phi(k,i)-\phi(k,j),\theta^{\prime}\rangle)\rvert$ $\displaystyle\qquad\leq\lvert\langle\phi(k,i)-\phi(k,j),\theta-\theta^{\prime}\rangle\rvert$ (36) $$

and

$$ $\displaystyle\lvert{\rm Sig}(\langle\phi(k,i)-\phi(k,j),\theta\rangle)-{\rm Sig }(\langle\phi(k,i)-\phi(k,j),\theta^{\prime}\rangle)\rvert$ $\displaystyle\qquad\geq\exp(-2R_{\rm max})\lvert\langle\phi(k,i)-\phi(k,j), \theta-\theta^{\prime}\rangle\rvert.$ (37) $$

Then, by Corollary D.1, we get that Eqn. (36) and Eqn. (37) imply that

$$ $\displaystyle d_{\rm KL}({\rm Sig}(\langle\phi(k,i)-\phi(k,j),\theta\rangle),{ \rm Sig}(\langle\phi(k,i)-\phi(k,j),\theta^{\prime}\rangle))$ $\displaystyle\qquad\leq 2\exp(2R_{\rm max})\lvert\langle\phi(k,i)-\phi(k,j), \theta-\theta^{\prime}\rangle\rvert^{2}$ (38) $$

and

$$ $\displaystyle d_{\rm KL}({\rm Sig}(\langle\phi(k,i)-\phi(k,j),\theta\rangle),{ \rm Sig}(\langle\phi(k,i)-\phi(k,j),\theta^{\prime}\rangle))$ $\displaystyle\qquad\geq 2\exp(-4R_{\rm max})\lvert\langle\phi(k,i)-\phi(k,j), \theta-\theta^{\prime}\rangle\rvert^{2}.$ (39) $$

Finally, combining Eqn. (35), Eqn. (38) and Eqn. (39), we complete the proof of Lemma 4.1.
∎

Then, recall that we denote $\tilde{D}(\cdot,\cdot)$ as the approximation of KL divergence between instance $v$ and $v^{\prime}$ that share the same parameter except $\theta$, i.e., for any $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$ and $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})$,

$$ $\tilde{D}(v,v^{\prime})\coloneqq\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N_{k,i ,j}(\langle\phi(k,i)-\phi(k,j),\theta-\theta^{\prime}\rangle)^{2}.$ $$

In addition, recall that for any $\mathbb{z}\in\mathbb{R}^{d}$, $\eta\in\mathbb{R}$ and consistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$, we denote ${\rm Alt}(v,\mathbb{z},\eta)$ as the set of instances that share the same parameter except $\theta$ and satisfy

$$ $\langle\mathbb{z},\theta^{\prime}-\theta\rangle=\eta$ $$

for all $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})\in{\rm Alt}(v
,\mathbb{z},\eta)$.

We are ready to prove Lemma 4.2 that reveals a useful property for ${\rm Alt}(\cdot)$ and $\tilde{D}(\cdot)$

###### Lemma 4.2 .

Let $\mathcal{G}$ be an arbitrary orthonormal basis of ${\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime}):(k^{\prime
},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}\text{ and }N_{k^{
\prime},i^{\prime},j^{\prime}}>0\}$. Also let $[\mathbf{w}]_{\mathcal{G}}$ denote the column vector that represents $\mathbf{w}$ under basis $\mathcal{G}$ (Meyer,, , Chapter 4). Define the matrix

$$ $V\coloneqq\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N_{k,i,j}[\phi(k,i)-\phi(k,j )]_{\mathcal{G}}[\phi(k,i)-\phi(k,j)]_{\mathcal{G}}^{\top}.$ $$

Then for any consistent instance $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)$, $\eta\in\mathbb{R}$, and $\mathbb{z}\in{\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime
}):(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}\text{
and }N_{k^{\prime},i^{\prime},j^{\prime}}>0\}$,

$$ $\min_{v^{\prime}\in{\rm Alt}(v,\mathbb{z},\eta)}\tilde{D}(v,v^{\prime})=\frac{ \eta^{2}}{\lVert[\mathbb{z}]_{\mathcal{G}}\rVert^{2}_{V^{-1}}}.$ (40) $$

and the minimum of (40) is attained in $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})$ with

$$ $\theta^{\prime}=\theta-\frac{\eta}{\lVert\mathbb{[z]_{\mathcal{G}}}\rVert^{2}_ {V^{-1}}}V^{-1}\mathbb{z}.$ $$

###### Proof.

By definition, we equivalently write down the optimization problem of Eqn. (40) as follows.

$$ $\min_{\mathbb{x}\in\mathbb{R}^{d}}\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N_{k ,i,j}(\langle[\phi(k,i)-\phi(k,j)]_{\mathcal{G}},[\mathbb{x}]_{\mathcal{G}} \rangle)^{2}$ (41) $$

subject to

$$ $\langle\mathbb{x},\mathbb{z}\rangle=\eta.$ $$

The Lagrangian of the above constrained optimization problem is,

$$ $L(\mathbb{x},\lambda)=\sum_{k\in\mathcal{S},i,j\in\mathcal{A}}N_{k,i,j}( \langle[\phi(k,i)-\phi(k,j)]_{\mathcal{G}},[\mathbb{x}]_{\mathcal{G}}\rangle)^ {2}+\lambda(\langle\mathbb{x},\mathbb{z}\rangle-\eta).$ $$

By solving $\frac{\mathrm{d}L}{\mathrm{d}\lambda}=0$ and $\frac{\mathrm{d}L}{\mathrm{d}\mathbb{x}_{i}}=0$ for all $i\in[d]$, we attain the minimum of Eqn. (41) at

$$ $\begin{cases}\lambda=\frac{2\eta}{\lVert\mathbb{[z]_{\mathcal{G}}}\rVert^{2}_{ V^{-1}}}\\ \mathbb{x}=-\frac{\eta}{\lVert[\mathbb{z}]_{\mathcal{G}}\rVert^{2}_{V^{-1}}}V^ {-1}\mathbb{z}+\mathbb{g},\\ \end{cases}$ $$

where $\mathbb{g}$ is any vector that is orthogonal with vector space ${\rm Span}\{\phi(k^{\prime},i^{\prime})-\phi(k^{\prime},j^{\prime}):(k^{\prime
},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}\text{ and }N_{k^{
\prime},i^{\prime},j^{\prime}}>0\}$,
which implies

$$ $L(\mathbb{z},\lambda)=\frac{\eta^{2}}{\lVert[\mathbb{z}]_{\mathcal{G}}\rVert^{ 2}_{V^{-1}}}.$ $$

This completes the desired proof.
∎

###### Lemma D.2 .

Fix any $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)\in\mathcal{Q}$. Let

$$ $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})\in \operatorname*{argmin}_{u\in{\rm Alt}(v,\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{ k}(v),i^{*}_{\bar{k}(v)}),2\Delta_{\bar{k}(v),\bar{i}(v)}(v))}\tilde{D}(v,u).$ $$

Then, it holds

$$ $\begin{cases}\langle\phi(k,i^{*}_{k}(v))-\phi(k,i),\theta-\theta^{\prime} \rangle=2\Delta_{k,i}(v)\qquad\mbox{for}\ (k,i)=(\bar{k}(v),\bar{i}(v))\\ \lvert\langle\phi(k,i^{*}_{k}(v))-\phi(k,i),\theta-\theta^{\prime}\rangle \rvert\leq\frac{1}{2}\Delta_{k,i}(v)\qquad\forall i\neq i^{*}_{k}(v)\mbox{ and }(k,i)\neq(\bar{k}(v),\bar{i}(v))\\ \end{cases}$ (42) $$

Consequently,

$$ $\begin{cases}i^{*}_{k}(v)=i^{*}_{k}(v^{\prime})\quad\forall k\neq\bar{k}(v)\\ \bar{k}(v)=\bar{k}(v^{\prime})\\ i^{*}_{\bar{k}(v^{\prime})}(v^{\prime})=\bar{i}(v)\\ \end{cases}$ (43) $$

###### Proof.

Fix any $v$ and $v^{\prime}$ as in Lemma D.2.
By the definition of $v^{\prime}$, we can immediately obtain the first inequality of Eqn. (42), i.e.,

$$ $\langle\phi(k,i^{*}_{k}(v))-\phi(k,i),\theta-\theta^{\prime}\rangle=2\Delta_{k ,i}(v)\ \text{for}\ (k,i)=(\bar{k}(v),\bar{i}(v)).$ (44) $$

Then, we will use proof by contradiction to prove the second inequality of Eqn. (42).

Assume that there exists $(\tilde{k},\tilde{i})\in\mathcal{S}\times\mathcal{A}$ with for all $\tilde{i}\neq i^{*}_{\tilde{k}}\text{ and }(\tilde{k},\tilde{i})\neq(\bar{k}(v
),\bar{i}(v))$ such that

$$ $\lvert\langle\phi(\tilde{k},i^{*}_{\tilde{k}})-\phi(\tilde{k},\tilde{i}), \theta-\theta^{\prime}\rangle\rvert>\frac{\Delta_{\tilde{k},\tilde{i}}(v)}{2}$ (45) $$

Then, we let $v^{\prime\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime\prime})$, where

$$ $\theta^{\prime\prime}=\theta+\frac{(\theta-\theta^{\prime})2\Delta_{\tilde{k}, \tilde{i}}(v)}{\langle\phi(\tilde{k},{i}^{*}_{\tilde{k}})-\phi(\tilde{k}, \tilde{i}),\theta-\theta^{\prime}\rangle},$ $$

which implies that $v^{\prime\prime}\in{\rm Alt}(v,\phi(\tilde{k},\tilde{i})-\phi(\tilde{k},\tilde
{i}^{*}_{k}),2\Delta_{\tilde{k},\tilde{i}}(v))$.
Note that from Lemma 4.2, we have

$$ $\tilde{D}(v,v^{\prime})=\frac{4\Delta_{\bar{k}(v),\bar{i}(v)}(v)^{2}}{\lVert[ \phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{k}(v),i^{*}_{\bar{k}(v)})]_{\mathcal{G}} \rVert^{2}_{V^{-1}}},$ (46) $$

where $V$ and $\mathcal{G}$ are as defined in Lemma 4.2.
In addition, by definition, we also can get that

$$ $\displaystyle\tilde{D}(v,v^{\prime\prime})$ $\displaystyle=\left(\frac{2\Delta_{\tilde{k},\tilde{i}}(v)}{\langle\phi(\tilde {k},{i}^{*}_{\tilde{k}})-\phi(\tilde{k},\tilde{i}),\theta-\theta^{\prime} \rangle}\right)^{2}\cdot\tilde{D}(v,v^{\prime})$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{<}}16\tilde{D}(v,v^{\prime})$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{<}}\frac{16\Delta_{\bar{k}(v),\bar{ i}(v)}(v)^{2}}{\lVert[\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{k}(v),i^{*}_{\bar{ k}(v)})]_{\mathcal{G}}\rVert^{2}_{V^{-1}}}$ $\displaystyle\stackrel{{\scriptstyle(c)}}{{<}}\frac{64}{\gamma_{\bar{k}(v), \bar{i}(v)}(v)}$ (47) $$

where (a) follows from Eqn. (45) and (b) follows from Eqn. (46), and (c) follows from Lemma C.1.

Similarly, from Lemma 4.2, we get that

$$ $\displaystyle\min_{u\in{\rm Alt}(v,\phi(\tilde{k},\tilde{i})-\phi(\tilde{k},i^ {*}_{\tilde{k}}),2\Delta_{\tilde{k},\tilde{i}}(v))}\tilde{D}(v,u)$ $\displaystyle=\frac{4\Delta_{\tilde{k},\tilde{i}}(v)^{2}}{\lVert[\phi(\tilde{k },\tilde{i})-\phi(\tilde{k},i^{*}_{\tilde{k}})]_{\mathcal{G}}\rVert^{2}_{V^{-1 }}}$ $\displaystyle=\frac{4}{\gamma_{\tilde{k},\tilde{i}}(v)}$ (48) $$

By the fact that $v^{\prime\prime}\in{\rm Alt}(v,\phi(\tilde{k},\tilde{i})-\phi(\tilde{k},i^{*}_
{\tilde{k}}))$ as well as Eqn. (24) and Eqn. (25), we further get that

$$ $\frac{4}{\gamma_{\tilde{k},\tilde{i}}(v)}<\frac{64}{\gamma_{\bar{k}(v),\bar{i} (v)}(v)}.$ $$

That is, $16{\gamma_{\tilde{k},\tilde{i}}}(v)>\gamma_{\bar{k}(v),\bar{i}(v)}(v)$, which contradicts the fact that $v\in\mathcal{Q}$.

Hence, for all $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $\forall\tilde{i}\neq i^{*}_{\tilde{k}}\text{ and }({k},{i})\neq(\bar{k}(v),
\bar{i}(v))$, we have

$$ $\lvert\langle\phi(k,i^{*}_{k}(v))-\phi(\bar{k}(v),\bar{i}(v)),\theta-\theta^{ \prime}\rangle\rvert\geq 2\Delta_{k,i}(v)$ $$

Consequently, we have

$$ $\begin{cases}i^{*}_{k}(v)=i^{*}_{k}(v^{\prime})\quad\forall k\neq\bar{k}(v)\\ \bar{k}(v)=\bar{k}(v^{\prime})\\ i^{*}_{\bar{k}(v^{\prime})}(v^{\prime})=\bar{i}(v)\\ \end{cases}$ $$

This completes the proof of Lemma D.2.
∎

###### Lemma D.3 .

Fix any $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)\in\mathcal{Q}$. Let

$$ $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})\in \operatorname*{argmin}_{u\in{\rm Alt}(v,\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{ k}(v),i^{*}_{\bar{k}(v)}),2\Delta_{\bar{k}(v),\bar{i}(v)}(v))}\tilde{D}(v,u).$ $$

Then, it holds

$$ $H(v)\leq H(v^{\prime})\leq 8H(v).$ $$

###### Proof.

Fix any $v$ and $v^{\prime}$ as in Lemma D.2.
Note that from Lemma D.2, we get that instance $v$ and instance $v^{\prime}$ share the same optimal action for the state $k\neq\bar{k}$ and the optimal action of state $\bar{k}(v)$ is $\bar{i}(v)$ under the instance $v^{\prime}$, i.e., $i^{*}_{\bar{k}(v^{\prime})}(v^{\prime})=\bar{i}(v)$ and $i^{*}_{k}(v)=i^{*}_{k}(v^{\prime})$ for all $k\neq\bar{k}(v)$. Then, by definition, the hardness of instance $v^{\prime}$ is

$$ $\displaystyle H(v^{\prime})$ $\displaystyle=\max_{k\in\mathcal{S},i\in\mathcal{A}:i\neq i^{*}_{k}(v^{\prime} )}\ \frac{\gamma_{k,i}(v^{\prime})}{\Delta_{k,i}^{2}(v^{\prime})}$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\max\left\{\max_{k\in\mathcal{S} ,i\in\mathcal{A}:i\neq i^{*}_{k}(v^{\prime}),k\neq\bar{k}(v)}\ \frac{\gamma_{k ,i}(v)}{\Delta_{k,i}^{2}(v^{\prime})},\max_{i\in\mathcal{A}:i\neq\bar{i}(v),k= \bar{k}(v)}\frac{\gamma_{k,i}(v^{\prime})}{\Delta_{k,i}^{2}(v^{\prime})}\right\}$ $$

where (a) follows the fact that $i^{*}_{k}(v)=i^{*}_{k}(v^{\prime})$ for all $k\neq\bar{k}(v)$ and both instances $v$ and $v^{\prime}$ share the same parameters of $\phi$ and $N$, which implies $\gamma_{k,i}(v)=\gamma_{k,i}(v^{\prime})$ for all $k\neq\bar{k}(v)$.

Then, by the fact that $\lvert\langle\phi(k,i^{*}_{k}(v))-\phi(k,i),\theta-\theta^{\prime}\rangle
\rvert\leq\frac{1}{2}\Delta_{k,i}(v)$ for all $i\neq i^{*}_{k}(v)\text{ and }(k,i)\neq(\bar{k}(v),\bar{i}(v))$ from Lemma D.2, we get that

$$ $\displaystyle\max_{k\in\mathcal{S},i\in\mathcal{A}:i\neq i^{*}_{k}(v^{\prime}) ,k\neq\bar{k}(v)}\ \frac{\gamma_{k,i}(v)}{\Delta_{k,i}^{2}(v^{\prime})}$ $\displaystyle\leq\max_{k\in\mathcal{S},i\in\mathcal{A}:i\neq i^{*}_{k}(v^{ \prime}),k\neq\bar{k}(v)}\ \frac{4\gamma_{k,i}(v)}{\Delta_{k,i}^{2}(v)}$ $\displaystyle\leq 4H(v)$ (49) $$

Further, by the fact that $\langle\phi(k,i^{*}_{k}(v))-\phi(k,i),\theta-\theta^{\prime}\rangle=2\Delta_{k
,i}(v)$ for $(k,i)=(\bar{k}(v),\bar{i}(v))$ Lemma D.2, we get that

$$ $\displaystyle\max_{i\in\mathcal{A}:i\neq\bar{i}(v),k=\bar{k}(v)}\frac{\gamma_{ k,i}(v^{\prime})}{\Delta_{k,i}^{2}(v^{\prime})}$ $\displaystyle=\max\left\{\frac{\gamma_{\bar{k}(v),\bar{i}(v)}(v)}{\Delta_{\bar {k}(v),\bar{i}(v)}^{2}(v)},\max_{i\in\mathcal{A}:i\neq\bar{i}(v),i\neq i^{*}_{ \bar{k}(v)}(v)}\frac{\gamma_{\bar{k}(v),i}(v^{\prime})}{\Delta_{\bar{k}(v),i}^ {2}(v^{\prime})}\right\}$ $\displaystyle=\max\left\{H(v),\max_{i\in\mathcal{A}:i\neq\bar{i}(v),i\neq i^{* }_{\bar{k}(v)}(v)}\frac{\gamma_{\bar{k}(v),i}(v^{\prime})}{\Delta_{\bar{k}(v), i}^{2}(v^{\prime})}\right\}$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\max\left\{H(v),\max_{i\in \mathcal{A}:i\neq\bar{i}(v),i\neq i^{*}_{\bar{k}(v)}(v)}\frac{\lVert[\phi(\bar {k}(v),\bar{i}(v))-\phi(\bar{k}(v),i)]_{\mathcal{G}}\rVert^{2}_{V^{-1}}}{ \Delta_{\bar{k}(v),i}^{2}(v^{\prime})}\right\}$ (50) $$

where (a) follows from Lemma C.1, $V$ and $\mathcal{G}$ are as defined in Lemma 4.2.
Similarly, by the fact that $\lvert\langle\phi(k,i^{*}_{k}(v))-\phi(k,i),\theta-\theta^{\prime}\rangle
\rvert\leq\frac{1}{2}\Delta_{k,i}(v)\ \ \forall i\neq i^{*}_{k}(v)\text{ and }
(k,i)\neq(\bar{k}(v),\bar{i}(v))$, we obtain for $i\in\mathcal{A}$ with $i\neq\bar{i}(v),i\neq i^{*}_{\bar{k}(v)}(v)$

$$ $\displaystyle\frac{\lVert[\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{k}(v),i)]_{ \mathcal{G}}\rVert^{2}_{V^{-1}}}{\Delta_{\bar{k}(v),i}^{2}(v^{\prime})}\leq \frac{4\lVert[\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{k}(v),i)]_{\mathcal{G}} \rVert^{2}_{V^{-1}}}{(\Delta_{\bar{k}(v),i}(v)\lor\Delta_{\bar{k}(v),\bar{i}}( v))^{2}}$ $\displaystyle=\frac{4\lVert[\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{k}(v),i^{*}_ {\bar{k}(v)}(v))+\phi(\bar{k}(v),i^{*}_{\bar{k}(v)}(v))-\phi(\bar{k}(v),i)]_{ \mathcal{G}}\rVert^{2}_{V^{-1}}}{(\Delta_{\bar{k}(v),i}(v)\lor\Delta_{\bar{k}( v),\bar{i}}(v))^{2}}$ $\displaystyle\leq\frac{4(\lVert[\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{k}(v),i^ {*}_{\bar{k}(v)}(v))]_{\mathcal{G}}\rVert^{2}_{V^{-1}}+\lVert[\phi(\bar{k}(v), i^{*}_{\bar{k}(v)}(v))-\phi(\bar{k}(v),i)]_{\mathcal{G}}\rVert^{2}_{V^{-1}}}{( \Delta_{\bar{k}(v),i}(v)\lor\Delta_{\bar{k}(v),\bar{i}}(v))^{2}}$ $\displaystyle\leq 8H(v).$ (51) $$

Finally, combining Eqn. (D), Eqn. (50) and Eqn. (51), we complete the proof of Lemma D.3.
∎

With the ingredients of the above lemmas, we are ready to prove Theorem 4.3.

###### Proof of Theorem 4.3 .

Fix any $v=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta)\in\mathcal{Q}$ and

$$ $v^{\prime}=(\rho,\mathcal{S},\mathcal{A},\phi,N,\theta^{\prime})\in \operatorname*{argmin}_{u\in{\rm Alt}(v,\phi(\bar{k}(v),\bar{i}(v))-\phi(\bar{ k}(v),i^{*}_{\bar{k}(v)}),2\Delta_{\bar{k}(v),\bar{i}(v)}(v))}\tilde{D}(v,u).$ $$

By Lemma D.3, we get that $H(v^{\prime})\leq H(v)\leq 8H(v^{\prime})$.
By Lemma 4.2, we get that

$$ $\displaystyle\tilde{D}(v,v^{\prime})$ $\displaystyle=\frac{\lVert[\phi(\bar{k}(v),i^{*}_{\bar{k}}(v))-\phi(\bar{k}(v) ,\bar{i}(v))]_{\mathcal{G}}\rVert^{2}_{V^{-1}}}{4\Delta_{\bar{k}(v),\bar{i}(v) }^{2}(v)}$ $\displaystyle=\frac{1}{4H(v)},$ $$

where $\mathcal{G}$ and $V$ are as defined in Lemma 4.2.
Further, by Lemma 4.1 and Lemma D.2, we get that for any $n>0$

$$ $\displaystyle D_{\rm KL}(P_{v}^{(n)}\|P_{v^{\prime}}^{(n)})$ $\displaystyle\leq{2\exp(2L)}\cdot n\tilde{D}(v,v^{\prime})$ $\displaystyle=\frac{n}{2\exp(-2L)H(v)}.$ (52) $$

Then, we let $\bar{\Delta}$ be the minimum suboptimality of state $\bar{k}(v)$ in both instances $v$ and $v^{\prime}$, i.e.,

$$ $\bar{\Delta}=\min_{i\in\mathcal{A}}\left[\max_{j\in\mathcal{A}}\langle\phi( \bar{k}(v),j)-\phi(\bar{k}(v),i),\theta\rangle+\max_{j\in\mathcal{A}}\langle \phi(\bar{k}(v),j)-\phi(\bar{k}(v),i),\theta^{\prime}\rangle\right]$ $$

By the definitions of $v$ and $v^{\prime}$, we can obtain that $\bar{\Delta}>0$.
Then, we get that for any policy $\pi$

$$ $\displaystyle\mathbb{E}^{\pi}_{v}[R_{n}]+\mathbb{E}^{\pi}_{v^{\prime}}[R_{n}]$ $\displaystyle\geq\rho_{\bar{k}(v)}\bar{\Delta}(1-D_{\rm TV}(P_{v}^{(n)},P_{v^{ \prime}}^{(n)}))$ (53) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\frac{1}{2}\rho_{\bar{k}(v)} \bar{\Delta}\exp(-D_{\rm KL}(P_{v}^{(n)}\|P_{v^{\prime}}^{(n)}))$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\frac{1}{2}\rho_{\bar{k}(v)} \bar{\Delta}\exp\left(-\frac{n}{2\exp(-2L)H(v)}\right),$ $$

where $D_{\rm TV}(\cdot,\cdot)$ denotes the total variance distance, and (a) follows from Bretagnolle–Huber inequality (Tsybakov,, , Lemma 2.6) and (c) follows from Eqn. (52).
Finally, for all sufficiently large $n$, we have

$$ $\mathbb{E}^{\pi}_{v}[R_{n}]+\mathbb{E}^{\pi}_{v^{\prime}}[R_{n}]\geq\exp\left( -\frac{n}{C_{\rm lo}\cdot H(v)}\right),$ $$

which completes the proof of Theorem 4.3.

∎

###### Corollary D.1 .

###### Lemma 4.1 .

###### Proof.

###### Lemma 4.2 .

###### Proof.

###### Lemma D.2 .

###### Proof.

###### Lemma D.3 .

###### Proof.

###### Proof of Theorem 4.3 .

## Appendix E Proof of Upper bound

###### Lemma E.1 .

Let $Y_{n}$ be a random variable sampled from the Binomial distribution with $n$ trials and probability of success $p\in[1-\beta,\beta]$ for $\beta\in(\frac{1}{2},1)$. Then,

$$ $\lvert\mathbb{E}(f(X_{n}))-f(\mathbb{E}(X_{n}))\rvert\leq\frac{3}{(1-\beta)^{4 }\sqrt{n}}$ $$

where $X_{n}=\frac{Y_{n}}{n}$ and

$$ $f(x)=\begin{cases}\log(\frac{x}{1-x})\quad\text{ if }x\in(1-\beta,\beta)\\ \log(\frac{\beta}{1-\beta})\quad\text{ if }x\geq\beta\\ \log(\frac{1-\beta}{\beta})\quad\text{ if }x\leq 1-\beta.\end{cases}$ (54) $$

###### Proof of Lemma E.1 .

For simplicity of notation, we let $x_{0}\coloneqq\mathbb{E}(X_{n})$, which implies $x_{0}=p\in[1-\beta,\beta]$.
Then, by the smoothness of $f(\cdot)$ on $[1-\beta,\beta]$, we obtain the equivalent expression of $f(\cdot)$ from the Taylor expansion of $f(\cdot)$ on $[1-\beta,\beta]$,

$$ $f(x)=\begin{cases}f(x_{0})+f^{\prime}(x_{0})\cdot(x-x_{0})+\frac{1}{2}f^{ \prime\prime}(\xi_{x})\cdot(x-x_{0})^{2}\quad\text{ if }x\in[1-\beta,\beta]\\ f(x_{0})+f^{\prime}(x_{0})\cdot(\beta-x_{0})+\frac{1}{2}f^{\prime\prime}(\xi_{ \beta})\cdot(\beta-x_{0})^{2}\quad\text{ if }x>\beta\\ f(x_{0})+f^{\prime}(x_{0})\cdot(1-\beta-x_{0})+\frac{1}{2}f^{\prime\prime}(\xi _{\beta})\cdot(1-\beta-x_{0})^{2}\quad\text{ if }x<1-\beta,\\ \end{cases}$ (55) $$

where $\xi_{x}\in(\min(x,x_{0}),\max(x,x_{0}))$ only depends on $x$ and $x_{0}$ in the Talor expansion.

By using the fact that $f^{\prime}(x_{0})\cdot(\beta-x_{0})=f^{\prime}(x_{0})\cdot(\beta-x)+f^{\prime}
(x_{0})\cdot(x-x_{0})$ and $f^{\prime}(x_{0})\cdot(1-\beta-x_{0})=f^{\prime}(x_{0})\cdot(1-\beta-x)+f^{
\prime}(x_{0})\cdot(x-x_{0})$, we obtain from Eqn. (55) that

$$ $\displaystyle\lvert\mathbb{E}(f(X_{n}))-f(\mathbb{E}(X_{n}))\rvert$ $\displaystyle\leq\sup_{x\in(1-\beta,\beta)}\lvert f^{\prime\prime}(x)\rvert \cdot{\rm Var}(X_{n})+\lvert f^{\prime}(x_{0})\rvert\cdot\mathbb{E}([X_{n}- \beta]_{+})+\lvert f^{\prime}(x_{0})\rvert\cdot\mathbb{E}([1-\beta-X_{n}]_{+})$ (56) $$

where ${\rm Var}(\cdot)$ represents the variance of the random variable $\cdot$ and $[x]_{+}=\max\{x,0\}$.

In addition, we note that

$$ $\displaystyle\mathbb{E}([X_{n}-\beta]_{+})$ $\displaystyle\leq\int_{\beta}^{1}(x-\beta)\mathbb{P}(X_{n}\geq x)\,\mathrm{d}x$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\int_{\beta}^{1}(x-\beta)\exp (-2n(x-x_{0})^{2})\,\mathrm{d}x$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\int_{\beta}^{1}(x-\beta)\exp (-n(x-\beta)^{2})\,\mathrm{d}x$ $\displaystyle\leq\int_{\beta}^{1}\frac{1}{\sqrt{n}}\,\mathrm{d}x$ $\displaystyle=\frac{1-\beta}{\sqrt{n}},$ (57) $$

where (a) follows from the fact $X_{n}$ is a subGaussian random variable with variance proxy $\frac{1}{4n}$, and (b) follows from the fact that $(x-\beta)\exp(-n(x-\beta)^{2})\leq\frac{1}{\sqrt{n}}$.
Similarly, we also can get that

$$ $\mathbb{E}([1-\beta-X_{n}]_{+})\leq\frac{1-\beta}{\sqrt{n}}.$ (58) $$

Finally,

$$ $\displaystyle\lvert\mathbb{E}(f(X_{n}))-f(\mathbb{E}(X_{n}))\rvert$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sup_{x\in(1-\beta,\beta)} \lvert f^{\prime\prime}(x)\rvert\cdot{\rm Var}(X_{n})+\lvert f^{\prime}(x_{0}) \rvert\cdot\mathbb{E}([X_{n}-\beta]_{+})+\lvert f^{\prime}(x_{0})\rvert\cdot \mathbb{E}([1-\beta-X_{n}]_{+})$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{(1-\beta)^{4}}\cdot{ \rm Var}(X_{n})+f^{\prime}(x_{0})\cdot\mathbb{E}([X_{n}-\beta]_{+})+f^{\prime} (x_{0})\cdot\mathbb{E}([1-\beta-X_{n}]_{+})$ $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{1}{(1-\beta)^{4}}\cdot \frac{1}{n}+f^{\prime}(x_{0})\cdot\mathbb{E}([X_{n}-\beta]_{+})+f^{\prime}(x_{ 0})\cdot\mathbb{E}([1-\beta-X_{n}]_{+})$ $\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{1}{(1-\beta)^{4}}\cdot \frac{1}{n}+\frac{1}{(1-\beta)^{2}}\cdot\mathbb{E}([X_{n}-\beta]_{+})+\frac{1} {(1-\beta)^{2}}\cdot\mathbb{E}([1-\beta-X_{n}]_{+})$ $\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\frac{1}{(1-\beta)^{4}}\cdot \frac{1}{n}+\frac{1}{(1-\beta)^{2}}\cdot\frac{2}{\sqrt{n}}$ $\displaystyle\leq\frac{3}{(1-\beta)^{4}\sqrt{n}},$ (59) $$

where (a) follows from Eqn. (56), (b) follows from ${\rm Var}(X_{n})\leq\frac{1}{n}$, (c) follows from $f^{\prime\prime}(x)=\frac{2x-1}{(x-1)^{2}x^{2}}$ for $x\in(\beta,1-\beta)$, (d) follows from $f^{\prime}(x)=\frac{1}{x-x^{2}}$ for $x\in(\beta,1-\beta)$, and (e) follows from Eqn. (57) and Eqn. (58).
∎

###### Lemma E.2 .

Let $Y_{n}$ be a random variable sampled from the binomial distribution with parameters $n>0$ and $p\in[1-\beta,\beta]$ for $\beta\in(\frac{1}{2},1)$. Let $X_{n}=\frac{Y_{n}}{n}$. Then,
$f(X_{n})$ is subGaussian with

$$ $\|f(X_{n})\|^{2}_{\rm vp}\leq\frac{C}{n},$ $$

where $C\leq(6\sqrt{2e}\cdot(3\sqrt{\log 2}+1))^{2}\cdot\frac{3}{2(1-\beta)^{4}}$ and $f(\cdot)$ is defined in Eqn. (54).

###### Proof.

By the definition of $X_{n}$, we get that

$$ $\|X_{n}-p\|_{\rm vp}^{2}\leq\frac{1}{4n}.$ $$

Then, by Lemma A.5, we get that

$$ $\|X_{n}-p\|_{\rm\phi_{2}}^{2}\leq\frac{3}{2n}.$ $$

By the fact that $\lvert f^{\prime}(x)\rvert\leq\frac{1}{(1-\beta)^{2}}$ for $x\in(1-\beta,\beta)$ and $f^{\prime}(x)=0$ for $x\in(0,1-\beta)\bigcup(\beta,1)$ , we get that

$$ $\|f(X_{n})-f(p)\|_{\rm\phi_{2}}^{2}\leq\frac{3}{2n(1-\beta)^{4}}.$ (60) $$

Similarly, from Lemma A.5, we further get that

$$ $\|f(X_{n})-f(p)\|_{\rm vp}^{2}\leq(6\sqrt{2e}\cdot(3\sqrt{\log 2}+1))^{2}\cdot \frac{3}{2n(1-\beta)^{4}}.$ (61) $$

Note that by definition, we have $\|f(X_{n})-f(p)\|_{\rm vp}^{2}=\|f(X_{n})\|_{\rm vp}^{2}$, which completes the proof of Lemma E.2.
∎

With the ingredients of the above lemmas, we are ready to prove the upper bound of our algorithms

###### Proof of Theorem 3.3 .

Fix any consistent instance $v$ and dataset size $n$ under RL-LOW.
By Lemma E.2 and Lemma A.3, we get that $\hat{r}_{k,i^{*}_{k},i}$ is subGaussian with variance proxy as

$$ $\|\hat{r}_{k,i^{*}_{k},i}\|_{\rm vp}^{2}\leq\frac{C\gamma_{k,i}}{n},$ (62) $$

where $C\leq(6\sqrt{2e}\cdot(3\sqrt{\log 2}+1))^{2}\cdot\frac{3}{2(1-\beta)^{4}}$ and $\beta=\frac{\exp(2L)}{1+\exp(2L)}$.

In addition, by Lemma E.1, we get that for any $(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}\times
\mathcal{A}$ with $N_{k^{\prime},i^{\prime},j^{\prime}}>0$,

$$ $\lvert\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left[f(B_{k^{\prime},i^{\prime},j^{ \prime}})\right]-f(\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left[B_{k^{\prime},i^{ \prime},j^{\prime}}\right])\rvert\leq\frac{3}{(1-\beta)^{4}\sqrt{n\cdot N_{k^{ \prime},i^{\prime},j^{\prime}}}},$ $$

which implies for any $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $i\neq i^{*}_{k}$,

$$ $\displaystyle\left\lvert\sum_{k^{\prime}\in\mathcal{S},i^{\prime}\in\mathcal{A },j^{\prime}\in\mathcal{A}}w^{(k,i^{*}_{k},i)}_{k^{\prime},i^{\prime},j^{ \prime}}\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left[f(B_{k^{\prime},i^{\prime},j^{ \prime}})\right]-f(\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left[\hat{r}_{k,i^{*}_{k },i}\right])\right\rvert$ $\displaystyle\leq\sum_{k^{\prime}\in\mathcal{S},i^{\prime}\in\mathcal{A},j^{ \prime}\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{\prime}}>0}\frac{3\lvert w^{ (k,i^{*}_{k},i)}_{k^{\prime},i^{\prime},j^{\prime}}\rvert}{(1-\beta)^{4}\sqrt{ n\cdot N_{k^{\prime},i^{\prime},j^{\prime}}}}.$ (63) $$

That is,

$$ $\displaystyle\left\lvert\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left[\hat{r}_{k,i^{ *}_{k},i}\right]-r_{k,i^{*}_{k},i}\right\rvert$ $\displaystyle\leq\sum_{k^{\prime}\in\mathcal{S},i^{\prime}\in\mathcal{A},j^{ \prime}\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{\prime}}>0}\frac{3\lvert w^{ (k,i^{*}_{k},i)}_{k^{\prime},i^{\prime},j^{\prime}}\rvert}{(1-\beta)^{4}\sqrt{ n\cdot N_{k^{\prime},i^{\prime},j^{\prime}}}}$ (64) $\displaystyle=\frac{3\tilde{\gamma}_{k,i}}{(1-\beta)^{4}\sqrt{n}},$ (65) $$

where we denote $r_{k,i,j}\coloneqq r_{k,i}-r_{k,j}$.

Note that by the definition of $R_{n}$ we have

$$ $\displaystyle R_{n}$ $\displaystyle\leq\sum_{(k,i)\in\mathcal{S}\times\mathcal{A}:i\neq i^{*}_{k}} \mathbbm{1}_{\{\hat{r}_{k,i^{*}_{k},i}\leq 0\}}\cdot\rho_{k}\Delta_{k,i}$ (66) $\displaystyle\leq\sum_{(k,i)\in\mathcal{S}\times\mathcal{A}:i\neq i^{*}_{k}} \bigg{[}\bigg{(}\mathbbm{1}_{\{\hat{r}_{k,i^{*}_{k},i}\leq\mathbb{E}_{v}^{\rm RL \mbox{-}LOW}\left[\hat{r}_{k,i,i^{*}_{k}}\right]-\Delta_{k,i}/2\}}$ $\displaystyle\hskip 85.35826pt\lor\mathbbm{1}_{\{\lvert\mathbb{E}_{v}^{\rm RL \mbox{-}LOW}\left[\hat{r}_{k,i^{*}_{k},i}\right]-\Delta_{k,i}\rvert\geq\Delta_ {k,i}/2\}}\bigg{)}\cdot\rho_{k}\Delta_{k,i}\bigg{]}$ (67) $$

By Lemma A.4 and Eqn. (62), we get that for any $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $i\neq i^{*}_{k}$,

$$ $\mathbb{P}_{v}^{\rm RL-LOW}\left(\hat{r}_{k,i^{*}_{k},i}\leq\mathbb{E}_{v}^{ \rm RL\mbox{-}LOW}\left[\hat{r}_{k,i^{*}_{k},i}\right]-\Delta_{k,i}/2\right) \leq\exp\left(-\frac{2n\Delta_{k,i}^{2}}{C\gamma_{k,i}}\right),$ (68) $$

and by Eqn. (65) we get that

$$ $\lvert\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left[\hat{r}_{k,i^{*}_{k},i}\right]-r _{k,i^{*}_{k},i}\rvert\leq\Delta_{k,i}/2$ $$

for all $n>\frac{18\tilde{\gamma}_{k,i}^{2}}{(1-\beta)^{8}\Delta_{k,i}}$.
That is, for all sufficiently large $n$, we have

$$ $\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left[R_{n}\right]\leq\sum_{k\in\mathcal{S}, i\in\mathcal{A}:i\neq i^{*}_{k}}\rho_{k}\Delta_{k,i}\exp\left(-\frac{2n\Delta_ {k,i}^{2}}{C\gamma_{k,i}}\right),$ $$

which further implies that for all sufficiently large $n$, we have

$$ $\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left[R_{n}\right]\leq\exp\left(-\frac{n}{C_ {\rm up}\cdot H(v)}\right).$ $$

This completes the proof of Theorem 3.3.
∎

In addition, we present the proof of Proposition 3.4 as follows.

###### Proof of Proposition 3.4 .

Note that by the definition of $R_{n}$ we have

$$ $\displaystyle R_{n}$ $\displaystyle\leq\sum_{(k,i)\in\mathcal{S}\times\mathcal{A}:i\neq i^{*}_{k}} \mathbbm{1}_{\{\hat{r}_{k,i^{*}_{k},i}\leq 0\}}\cdot\rho_{k}\Delta_{k,i}$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{(k,i)\in\mathcal{S} \times\mathcal{A}:i\neq i^{*}_{k}}\rho_{k}\bigg{[}\mathbbm{1}_{\{\Delta_{k,i}< \frac{6\tilde{\gamma}_{k,i}}{(1-\beta)^{4}\sqrt{n}}\}}\cdot\frac{6\tilde{ \gamma}_{k,i}}{(1-\beta)^{4}\sqrt{n}}$ $\displaystyle\hskip 85.35826pt+\mathbbm{1}_{\{\lvert\mathbb{E}_{v}^{\rm RL \mbox{-}LOW}\left[\hat{r}_{k,i,i^{*}_{k}}\right]-r_{k,i,i^{*}_{k}}\rvert\leq \Delta_{k,i}/2\}}\cdot\Delta_{k,i}\bigg{]}$ $$

where $\beta=\frac{\exp(2L)}{1+\exp(2L)}$, and (a) follows from Eqn. (65).

Hence, by Eqn. (68), we have

$$ $\displaystyle\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}[R_{n}]$ $\displaystyle{\leq}\sum_{(k,i)\in\mathcal{S}\times\mathcal{A}:i\neq i^{*}_{k}} \rho_{k}\left[\frac{6\tilde{\gamma}_{k,i}}{(1-\beta)^{4}\sqrt{n}}+\exp\left(- \frac{2n\Delta_{k,i}^{2}}{C\gamma_{k,i}}\right)\Delta_{k,i}\right]$ (69) $\displaystyle\leq\sum_{(k,i)\in\mathcal{S}\times\mathcal{A}:i\neq i^{*}_{k}} \rho_{k}\left[\frac{6\tilde{\gamma}_{k,i}}{(1-\beta)^{4}\sqrt{n}}+\sqrt{\frac{ C\gamma_{k,i}}{2n}}\right]$ (70) $\displaystyle=\frac{1}{\sqrt{n}}\sum_{(k,i)\in\mathcal{S}\times\mathcal{A}:i \neq i^{*}_{k}}\rho_{k}\left[\frac{6\tilde{\gamma}_{k,i}}{(1-\beta)^{4}}+\sqrt {\frac{C\gamma_{k,i}}{2}}\right]$ (71) $$

where $C\leq(6\sqrt{2e}\cdot(3\sqrt{\log 2}+1))^{2}\cdot\frac{3}{2(1-\beta)^{4}}$.

This completes the desired proof.
∎

###### Lemma E.1 .

###### Proof of Lemma E.1 .

###### Lemma E.2 .

###### Proof.

###### Proof of Theorem 3.3 .

###### Proof of Proposition 3.4 .

## Appendix F Theoretical analysis of DP-RL-Low

###### Lemma F.1 .

Fix any $\varepsilon>0$ and $\delta>0$. Let $Y_{n}$ be a random variable sampled from the binomial distribution with number of trials $n\in\mathbb{N}$ and probability of success $p\in[1-\beta,\beta]$ for $\beta\in(\frac{1}{2},1)$. Then,

$$ $\lvert\mathbb{E}(f(\tilde{X}_{n}))-f(\mathbb{E}(\tilde{X}_{n}))\rvert\leq\frac {3}{(1-\beta)^{4}\sqrt{2n}}+\frac{4\sqrt{{{\log(1.25/\delta)}}}}{(1-\beta)^{4} {{(\varepsilon n)}}},$ $$

where $\tilde{X}_{n}=\frac{Y_{n}}{n}+\tilde{\xi}_{n}$, and $\tilde{\xi}_{n}$ is an independent Gaussian noise with zero mean and variance of $\frac{2\log(1.25/\delta)}{(\varepsilon n)^{2}}$, and $f(\cdot)$ is defined in (54).

###### Proof of Lemma F.1 .

For simplicity of notation, we let $x_{0}\coloneqq\mathbb{E}(\tilde{X}_{n})$, which implies $x_{0}=p\in[1-\beta,\beta]$.
Again, by the smoothness of $f(\cdot)$ on $[1-\beta,\beta]$, we get the Taylor expansion of $f(\cdot)$ on $[1-\beta,\beta]$,

$$ $f(x)=\begin{cases}f(x_{0})+f^{\prime}(x_{0})\cdot(x-x_{0})+\frac{1}{2}f^{ \prime\prime}(\xi_{x})\cdot(x-x_{0})^{2}\quad\text{ if }x\in[1-\beta,\beta]\\ f(x_{0})+f^{\prime}(x_{0})\cdot(\beta-x_{0})+\frac{1}{2}f^{\prime\prime}(\xi_{ \beta})\cdot(\beta-x_{0})^{2}\quad\text{ if }x>\beta\\ f(x_{0})+f^{\prime}(x_{0})\cdot(1-\beta-x_{0})+\frac{1}{2}f^{\prime\prime}(\xi _{\beta})\cdot(1-\beta-x_{0})^{2}\quad\text{ if }x<1-\beta,\\ \end{cases}$ (72) $$

where $\xi_{x}\in(\min(x,x_{0}),\max(x,x_{0}))$ that only depends on $x$ and $x_{0}$ in the Talor expansion.

Similarly, by the fact that $f^{\prime}(x_{0})\cdot(\beta-x_{0})=f^{\prime}(x_{0})\cdot(\beta-x)+f^{\prime}
(x_{0})\cdot(x-x_{0})$ and $f^{\prime}(x_{0})\cdot(1-\beta-x_{0})=f^{\prime}(x_{0})\cdot(1-\beta-x)+f^{
\prime}(x_{0})\cdot(x-x_{0})$, we can get from (72),

$$ $\displaystyle\lvert\mathbb{E}(f(\tilde{X}_{n}))-f(\mathbb{E}(\tilde{X}_{n}))\rvert$ $\displaystyle\leq\sup_{x\in(1-\beta,\beta)}\lvert f^{\prime\prime}(x)\rvert{ \rm Var}(\tilde{X}_{n})+\lvert f^{\prime}(x_{0})\rvert\cdot\mathbb{E}([\tilde{ X}_{n}-\beta]_{+})+\lvert f^{\prime}(x_{0})\rvert\cdot\mathbb{E}([1-\beta- \tilde{X}_{n}]_{+})$ (73) $$

where ${\rm Var}(\cdot)$ represents the variance and $[x]_{+}=\max\{x,0\}$.

In addition, we note that

$$ $\displaystyle\mathbb{E}([\tilde{X}_{n}-\beta]_{+})$ $\displaystyle\leq\int_{\beta}^{1}(x-\beta)\mathbb{P}(\tilde{X}_{n}\geq x)\, \mathrm{d}x$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\int_{\beta}^{1}(x-\beta)\exp (-\frac{(x-x_{0})^{2}}{2(\frac{1}{4n}+\frac{2\log(1.25/\delta)}{(\varepsilon n )^{2}})})\,\mathrm{d}x$ $\displaystyle\leq\int_{\beta}^{1}(x-\beta)\exp\left(-\left({2n(x-x_{0})^{2}} \land\frac{(x-x_{0})^{2}(\varepsilon n)^{2}}{{4\log(1.25/\delta)}}\right) \right)\,\mathrm{d}x$ $\displaystyle=\int_{\beta}^{1}(x-\beta)\exp\left(-{(x-x_{0})^{2}}\left(2n\land \frac{(\varepsilon n)^{2}}{{4\log(1.25/\delta)}}\right)\right)\,\mathrm{d}x$ $\displaystyle\leq\int_{\beta}^{1}(x-\beta)\exp\left(-{(x-\beta)^{2}}\left(2n \land\frac{(\varepsilon n)^{2}}{{4\log(1.25/\delta)}}\right)\right)\,\mathrm{d}x$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\int_{\beta}^{1}\sqrt{\frac{1 }{{2n\land\frac{(\varepsilon n)^{2}}{{4\log(1.25/\delta)}}}}}\,\mathrm{d}x$ $\displaystyle=\frac{1-\beta}{\sqrt{2n\land\frac{(\varepsilon n)^{2}}{{4\log(1. 25/\delta)}}}},$ (74) $$

where (a) follows from the fact that $\tilde{X}_{n}$ is subGaussian with variance proxy $\frac{1}{4n}+\frac{2\log(1.25/\delta)}{(\varepsilon n)^{2}}$, and (b) follows from the fact that $x\exp(-x^{2}y)<\sqrt{\frac{1}{y}}$ for any $y>0$.
Similarly, we also can get that

$$ $\mathbb{E}([1-\beta-X_{n}]_{+})\leq\frac{1-\beta}{\sqrt{2n\land\frac{( \varepsilon n)^{2}}{{4\log(1.25/\delta)}}}}.$ (75) $$

Finally,

$$ $\displaystyle\lvert\mathbb{E}(f(\tilde{X}_{n}))-f(\mathbb{E}(\tilde{X}_{n}))\rvert$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sup_{x\in(1-\beta,\beta)} \lvert f^{\prime\prime}(x)\rvert{\rm Var}(\tilde{X}_{n})+\lvert f^{\prime}(x_{ 0})\rvert\cdot\mathbb{E}([\tilde{X}_{n}-\beta]_{+})+\lvert f^{\prime}(x_{0}) \rvert\cdot\mathbb{E}([1-\beta-\tilde{X}_{n}]_{+})$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{(1-\beta)^{4}}\cdot \left(\frac{1}{n}+\frac{2\log(1.25/\delta)}{(\varepsilon n)^{2}}\right)+f^{ \prime}(x_{0})\cdot\mathbb{E}([X_{n}-\beta]_{+})+f^{\prime}(x_{0})\cdot\mathbb {E}([1-\beta-X_{n}]_{+})$ $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{1}{(1-\beta)^{4}}\cdot \left(\frac{1}{n}+\frac{2\log(1.25/\delta)}{(\varepsilon n)^{2}}\right)+f^{ \prime}(x_{0})\cdot\frac{2}{\sqrt{2n\land\frac{(\varepsilon n)^{2}}{{4\log(1.2 5/\delta)}}}}$ $\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{1}{(1-\beta)^{4}}\cdot \left(\frac{1}{n}+\frac{2\log(1.25/\delta)}{(\varepsilon n)^{2}}\right)+\frac{ 1}{(1-\beta)^{2}}\cdot\frac{2}{\sqrt{2n\land\frac{(\varepsilon n)^{2}}{{4\log( 1.25/\delta)}}}}$ $\displaystyle\leq\frac{3}{(1-\beta)^{4}\sqrt{2n}}+\frac{4\sqrt{{{\log(1.25/ \delta)}}}}{(1-\beta)^{2}{{(\varepsilon n)}}}+\frac{2{{{\log(1.25/\delta)}}}}{ (1-\beta)^{4}{{(\varepsilon n)^{2}}}}$ (76) $\displaystyle\leq\frac{3}{(1-\beta)^{4}\sqrt{2n}}+\frac{4}{(1-\beta)^{4}}\cdot \left(\frac{\sqrt{{{\log(1.25/\delta)}}}}{{{(\varepsilon n)}}}\lor\frac{{{{ \log(1.25/\delta)}}}}{{{(\varepsilon n)^{2}}}}\right)$ $\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\frac{3}{(1-\beta)^{4}\sqrt{2 n}}+\frac{4\sqrt{{{\log(1.25/\delta)}}}}{(1-\beta)^{4}{{(\varepsilon n)}}}$ $$

where (a) follows from Eqn. (73), (b) follows from the fact that ${\rm Var}(\tilde{X}_{n})\leq\frac{1}{n}+\frac{2\log(1.25/\delta)}{(\varepsilon
n
)^{2}}$ and that $f^{\prime\prime}(x)=\frac{2x-1}{(x-1)^{2}x^{2}}$, (c) follows from Eqn. (74) and Eqn. (75), (d) follows from the fact that $f^{\prime}(x)=\frac{1}{x-x^{2}}$, and (e) follows the fact that $\lvert\mathbb{E}(f(\tilde{X}_{n}))-f(\mathbb{E}(\tilde{X}_{n}))\rvert\leq\frac
{4}{(1-\beta)^{4}}$ and that $\sqrt{x}\geq x$ for any $x\in(0,1]$
∎

###### Lemma F.2 .

Fix any $\varepsilon>0$ and $\delta>0$. Let $Y_{n}$ be a random variable sampled from the binomial distribution with number of trials $\in\mathbb{N}$ and probability of success $p\in[1-\beta,\beta]$ for $\beta\in(\frac{1}{2},1)$. Let $\tilde{X}_{n}=\frac{Y_{n}}{n}+\tilde{\xi}_{n}$, and $\tilde{\xi}_{n}$ is an independent Gaussian noise with zero mean and variance of $\frac{2\log(1.25/\delta)}{(\varepsilon n)^{2}}$. Then,
$f(\tilde{X}_{n})$ is subGaussian with

$$ $\|f(\tilde{X}_{n})\|^{2}_{\rm vp}\leq C\cdot\left(\frac{1}{n}+\frac{8\log(1.25 /\delta)}{(\varepsilon n)^{2}}\right),$ $$

where $C\leq(6\sqrt{2e}\cdot(3\sqrt{\log 2}+1))^{2}\cdot\frac{3}{2(1-\beta)^{4}}$ and $f(\cdot)$ is defined in (54).

###### Proof.

By the definition of $X_{n}$, we get that

$$ $\|\tilde{X}_{n}-p\|_{\rm vp}^{2}\leq\frac{1}{4n}+\frac{2\log(1.25/\delta)}{( \varepsilon n)^{2}}.$ $$

Then, by Lemma A.5, we get that

$$ $\|\tilde{X}_{n}-p\|_{\rm\phi_{2}}^{2}\leq\frac{3}{2n}+\frac{12\log(1.25/\delta )}{(\varepsilon n)^{2}}.$ $$

By the fact that $\lvert f^{\prime}(x)\rvert\leq\frac{1}{(1-\beta)^{2}}$, we get that

$$ $\|f(\tilde{X}_{n})-f(p)\|_{\rm\phi_{2}}^{2}\leq\left(\frac{3}{2n}+\frac{12\log (1.25/\delta)}{(\varepsilon n)^{2}}\right)\cdot\frac{1}{(1-\beta)^{4}}.$ (77) $$

Similarly, from Lemma A.5, we further get that

$$ $\|f(\tilde{X}_{n})-f(p)\|_{\rm vp}^{2}\leq(6\sqrt{2e}\cdot(3\sqrt{\log 2}+1))^ {2}\cdot\frac{3}{2(1-\beta)^{4}}\left(\frac{1}{n}+\frac{8\log(1.25/\delta)}{( \varepsilon n)^{2}}\right).$ (78) $$

Note that by definition, we have $\|f(\tilde{X}_{n})-f(p)\|_{\rm vp}^{2}=\|f(\tilde{X}_{n})\|_{\rm vp}^{2}$, which completes the proof of Lemma E.2.
∎

###### Proof of Theorem 5.3 .

Fix any consistent instance $v$ and $n>0$ under DP-RL-LOW.
By lemma E.2 and lemma A.3, we get that $\tilde{r}_{k,i^{*}_{k},i}$ is subGaussian with variance proxy to be,

$$ $\|\tilde{r}_{k,i^{*}_{k},i}\|_{\rm vp}^{2}\leq C\cdot\left(\frac{\gamma_{k,i}} {n}+\frac{8\gamma_{k,i}^{\rm DP}\log(1.25/\delta)}{(\varepsilon n)^{2}}\right),$ (79) $$

where $C\leq(6\sqrt{2e}\cdot(3\sqrt{\log 2}+1))^{2}\cdot\frac{3}{2(1-\beta)^{4}}$ and $\beta=\frac{\exp(2L)}{1+\exp(2L)}$.

In addition, by Lemma F.1, we get that for any $(k^{\prime},i^{\prime},j^{\prime})\in\mathcal{S}\times\mathcal{A}^{2}$ with $N_{k^{\prime},i^{\prime},j^{\prime}}>0$,

$$ $\displaystyle\left\lvert\mathbb{E}_{v}^{\rm DP\mbox{-}RL\mbox{-}LOW}\left[f( \tilde{B}_{k^{\prime},i^{\prime},j^{\prime}})\right]-f\left(\mathbb{E}_{v}^{ \rm DP\mbox{-}RL\mbox{-}LOW}\left[\tilde{B}_{k^{\prime},i^{\prime},j^{\prime}} \right]\right)\right\rvert$ $\displaystyle\leq\frac{3}{(1-\beta)^{4}\sqrt{2nN_{k^{\prime},i^{\prime},j^{ \prime}}}}+\frac{4\sqrt{{{\log(1.25/\delta)}}}}{(1-\beta)^{4}{{(\varepsilon nN _{k^{\prime},i^{\prime},j^{\prime}})}}},$ (80) $$

which implies for any $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $i\neq i^{*}_{k}$,

$$ $\displaystyle\left\lvert\sum_{k^{\prime}\in\mathcal{S},i^{\prime}\in\mathcal{A },j^{\prime}\in\mathcal{A}}w^{(k,i^{*}_{k},i)}_{k^{\prime},i^{\prime},j^{ \prime}}\mathbb{E}_{v}^{\rm DP\mbox{-}RL\mbox{-}LOW}\left[f(B_{k^{\prime},i^{ \prime},j^{\prime}})\right]-f(\mathbb{E}_{v}^{\rm DP\mbox{-}RL\mbox{-}LOW} \left[B_{k^{\prime},i^{\prime},j^{\prime}}\right])\right\rvert$ $\displaystyle\leq\sum_{k^{\prime}\in\mathcal{S},i^{\prime}\in\mathcal{A},j^{ \prime}\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{\prime}}\neq 0}\lvert w^{(k, i^{*}_{k},i)}_{k^{\prime},i^{\prime},j^{\prime}}\rvert\left(\frac{3}{(1-\beta) ^{4}\sqrt{2nN_{k^{\prime},i^{\prime},j^{\prime}}}}+\frac{4\sqrt{{{\log(1.25/ \delta)}}}}{(1-\beta)^{4}{{(\varepsilon nN_{k^{\prime},i^{\prime},j^{\prime}}) }}}\right).$ (81) $$

Recall that we denote $r_{k,i^{*}k,i}=r_{k,i^{*}_{k}}-r_{k,i}$. Then, from Eqn. (81), we get

$$ $\displaystyle\left\lvert\mathbb{E}_{v}^{\rm DP\mbox{-}RL\mbox{-}LOW}\left[ \tilde{r}_{k,i^{*}_{k},i}\right]-r_{k,i^{*}_{k},i}\right\rvert$ $\displaystyle\leq\sum_{k^{\prime}\in\mathcal{S},i^{\prime}\in\mathcal{A},j^{ \prime}\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{\prime}}\neq 0}\lvert w^{(k, i,j)}_{k^{\prime},i^{\prime},j^{\prime}}\rvert\left(\frac{3}{(1-\beta)^{4} \sqrt{2nN_{k^{\prime},i^{\prime},j^{\prime}}}}+\frac{4\sqrt{{{\log(1.25/\delta )}}}}{(1-\beta)^{4}{{(\varepsilon nN_{k^{\prime},i^{\prime},j^{\prime}})}}}\right)$ (82) $\displaystyle\leq\frac{3\tilde{\gamma}_{k,i}}{(1-\beta)^{4}\sqrt{n}}+\frac{4 \tilde{\gamma}^{DP}_{k,i}\sqrt{{{\log(1.25/\delta)}}}}{(1-\beta)^{4}{{( \varepsilon n)}}},$ (83) $$

where $\tilde{\gamma}^{\mathrm{DP}}_{k,i}\coloneqq\sum_{k^{\prime}\in\mathcal{S},i^{
\prime}\in\mathcal{A},j^{\prime}\in\mathcal{A}:N_{k^{\prime},i^{\prime},j^{
\prime}}\neq 0}\frac{\lvert w^{(k,i^{*}_{k},i)}_{k^{\prime},i^{\prime},j^{
\prime}}\rvert}{{N_{k^{\prime},i^{\prime},j^{\prime}}}}$

Note that by the definition of $R_{n}$, under DP-RL-LOW we have

$$ $\displaystyle R_{n}$ $\displaystyle\leq\sum_{(k,i)\in\mathcal{S}\times\mathcal{A}:i\neq i^{*}_{k}} \mathbbm{1}_{\{\tilde{r}_{k,i^{*}_{k},i}<0\}}\cdot\rho_{k}\Delta_{k,i}$ (84) $\displaystyle\leq\sum_{(k,i)\in\mathcal{S}\times\mathcal{A}:i\neq i^{*}_{k}} \bigg{[}\big{(}\mathbbm{1}_{\{\tilde{r}_{k,i^{*}_{k},i}\leq\mathbb{E}_{v}^{\rm DP \mbox{-}RL\mbox{-}LOW}\left[\tilde{r}_{k,i^{*}_{k},i}\right]-\Delta_{k,i}/2\}}$ $\displaystyle\hskip 85.35826pt\lor\mathbbm{1}_{\{\lvert\mathbb{E}_{v}^{\rm DP \mbox{-}RL\mbox{-}LOW}\left[\tilde{r}_{k,i^{*}_{k},i}\right]-r_{k,i^{*}_{k},i} \rvert\leq\Delta_{k,i}/2\}}\big{)}\cdot\rho_{k}\Delta_{k,i}\bigg{]}$ (85) $$

By Lemma A.4 and  (79), we get that for any $(k,i)\in\mathcal{S}\times\mathcal{A}$ with $i\neq i^{*}_{k}$,

$$ $\displaystyle\mathbb{P}_{v}^{\rm DP-RL-LOW}\left(\tilde{r}_{k,i^{*}_{k}i,}\leq \mathbb{E}_{v}^{\rm DP\mbox{-}RL\mbox{-}LOW}\left[\tilde{r}_{k,i^{*}_{k},i} \right]-\Delta_{k,i}/2\right)$ $\displaystyle\leq\exp\left(-\frac{2\Delta_{k,i}^{2}}{C\cdot(\gamma_{k,i}/n+{8 \gamma_{k,i}^{\rm DP}\log(1.25/\delta)}/{(\varepsilon n)^{2}})}\right),$ (86) $$

and by (83) we get that

$$ $\lvert\mathbb{E}_{v}^{\rm DP\mbox{-}RL\mbox{-}LOW}\left[\tilde{r}_{k,i^{*}_{k} ,i}\right]-r_{k,i^{*}_{k},i}\rvert\leq\Delta_{k,i}/2$ $$

for all $n>\frac{12\tilde{\gamma}_{k,i}^{2}}{(1-\beta)^{8}\Delta_{k,i}^{2}}+\frac{8
\tilde{\gamma}^{DP}_{k,i}\sqrt{{{\log(1.25/\delta)}}}}{(1-\beta)^{4}{{(
\varepsilon\Delta_{k,i})}}}$.
That is, for all sufficiently large $n$, we have

$$ $\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left(R_{n}\right)\leq\sum_{k\in\mathcal{S}, i\in\mathcal{A}:i\neq i^{*}_{k}}\rho_{k}\Delta_{k,i}\exp\left(-\frac{2\Delta_{ k,i}^{2}}{C(\gamma_{k,i}/n+{8\gamma_{k,i}^{\rm DP}\log(1.25/\delta)}/{( \varepsilon n)^{2}})}\right),$ $$

which further implies that for all sufficiently large $n$, there exists a global constant $C_{\rm DP}$, we have

$$ $\mathbb{E}_{v}^{\rm RL\mbox{-}LOW}\left(R_{n}\right)\leq\exp\left(-C_{\rm DP} \cdot\left(\frac{n}{H(v)}\land\left(\frac{n}{H_{\rm DP}^{(\varepsilon,\delta)) }(v)}\right)^{2}\right)\right).$ $$

This completes the proof of Theorem 5.3
∎

###### Lemma F.1 .

###### Proof of Lemma F.1 .

###### Lemma F.2 .

###### Proof.

###### Proof of Theorem 5.3 .

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: *These are not quite questions, but comments that I think may help the authors.*

-	I would suggest that the authors not just focus on the dependence on n, but more thoroughly inspect the “coverage”, i.e., how the discrepancy between N and \rho affects the learning bounds.  This is well-studied in offline RL (non-preference feedback), e.g., https://proceedings.mlr.press/v97/chen19e.html  https://arxiv.org/abs/2106.04895  https://arxiv.org/abs/2203.05804  


-	Since the setting is label-DP, e.g., in the “Our Contributions” setting, it should be appropriately referred to “label-DP”.  This is in contrast to existing studies on differentially private reinforcement learning that considered individual trajectories to be the contribution of a user (to be protected).  I agree that label-DP seems natural in the RLHF setting. 

-	More discussion on the following body of work will help the paper to situation its novel contribution in a broader context:

1.	Gap-dependent analysis for Dueling Bandits, e.g.,  https://proceedings.mlr.press/v130/yang21a/yang21a.pdf 

2.	Contextual Dueling Bandits (and many follow-up work, e.g., https://proceedings.neurips.cc/paper/2021/file/fc3cf452d3da8402bebb765225ce8c0e-Paper.pdf who talked about large-gap as an open problem) https://proceedings.mlr.press/v40/Dudik15.html 

3.	Gap-dependent bound for offline RL is well-studied but not cited (a).	Tabular setting:  https://arxiv.org/abs/2206.00177  (b).	Linear function approximation https://arxiv.org/abs/2211.13208 

Note that in those cases even if the rewards are known, a 1/n rate is required in the lower bound. The main difference is that the current paper assumes away any planning and does not measure the regret in terms of the value function.
soundness: 4
strengths: Strengths

-	The results appear to be new. 
-	The presentation of the technical results is clear.
-	The logarithm of the upper and lower bounds of the suboptimality match up to a universal constant. The weak notion of optimality (on the exponent) may appear to be esoteric, but it is appropriate in cases when the error bound is exponentially small.
-	In a specialized setting, the result knocks out a log n factor in the worst-case expected “simple regret” of Zhu et al. (2023).
summary: The paper studies offline reinforcement learning with preference feedback under the Bradley-Terry-Luce Model. There is a known feature function \phi that maps state-action pairs to a vector embedding such that the preference of two actions is determined by a linear function of their feature through a sigmoid transform.

The offline dataset have fixed s,a1, a2, but the label is random (from the BTL model). The target state distribution is \rho.  The offline dataset appears to be fixed for s, a1,a2 but have random Boolean label (preference).

The main claims are: (1) An algorithm that enjoys a gap-dependent bound that decays exponentially in the number of samples n. (2)  A lower bound showing that the rate of decay (on the exponent) is optimal up to a constant. (3) A label-differentially private algorithm with appropriate privacy and utility bound.
weaknesses: Weaknesses:

-	The model of offline RL being considered in the paper is crudely simplified. The target state distribution \rho is fixed rather than controlled by the chosen policy.  The policy only controls the actions.  This setting should be called “Offline Contextual Bandits under distribution-shift” rather than offline RL.  A generalization is given in Section 6 but still requires the transition dynamics to be known (still quite far from a typical offline RL setting).

-	The whole point of assuming a linear feature model in BTL model is that the learning bound does not depend explicitly on the cardinality of the state space and that the model can learn without seeing all states, i.e., the learner can generalize to unseen states.  The setting in this paper assumes linear features, but also requires state/action spaces to be finite and that the distribution samples each state with non-zero probability.  For example,  Zhu et al's bound depends polynomially in d.  When S = {0,1}^d,  this is log S. I personally think that it is more natural if the authors just focus on the tabular case (with \phi being the trivial one-hot feature).

-	Related to the above, the claim on computational efficiency is only valid when S and A are finite and small.  Typical settings in RL with function approximation require dependence on log S to be considered efficient. 

-	The fourth strength above (Proposition 3.4 compared to Theorem 1.1 of Zhu et al 2023) is not a fair comparison.  In the setting of Zhu et al, there is no dependence on the cardinality of the state space.  The “coverage” is described by the properties of the feature covariance matrix.  The results of this paper require all states (in the support of target distribution \rho) to have many observations to be non-vacuous.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. **BTL Model Assumptions**: 

The Bradley–Terry–Luce (BTL) model used for preference feedback is quite limited in terms of modeling real human preferences. To what extent could the assumptions of this model be relaxed, and what impact would this have on the results?

2. **Algorithmic Novelty vs. Analytical Refinement**: 

Is the prior theoretical guarantee of RL-LOW due to its algorithmic design or a more refined analysis? A comparison of RL-LOW’s performance with that of PESSIMISTIC MLE under the same conditions would help clarify this point.

3. **Clarification on Assumptions**: 

Definition 2.2 needs further explanation, which appears somewhat confusing. This definition relies on the collected data $N_{k,i,j}$, which is random, while the concept of a consistent instance seems to be a property of the feature $\phi(k, i)$. This suggests that for a given feature $\phi(k, i)$, it may sometimes be consistent and other times not, depending on the data. Could the authors clarify why this assumption is necessary and provide more insight into its implications? Additionally, it would be helpful to understand how consistency is determined in practice.

4. **Clarification on "Instance-Dependent" Bound**: 

The so-called instance-dependent bound appears more like a "gap-dependent" bound, as it heavily relies on the suboptimality gaps between actions. This raises the question of how the results would change if these gaps did not exist or were negligible. In such cases, would the proposed algorithm still achieve meaningful bounds, or would its performance degrade? Could the authors explain how the proposed method would handle instances where the suboptimality gaps are small or non-existent?
soundness: 3
strengths: 1. **Instance-Dependent Bounds**: 

The algorithm’s ability to achieve instance-dependent error bounds is a major strength. This focus provides finer theoretical guarantees compared to minimax bounds.

2. **Theoretical Contributions**: 

The paper does a thorough job of proving both upper and lower bounds for the regret, providing order-optimality guarantees in terms of the hardness parameter $H$.
summary: This paper introduces RL-LOW, an algorithm aimed at minimizing simple regret in offline reinforcement learning (RL) with preference feedback. 

The paper claims that RL-LOW achieves tight instance-dependent bounds, offering theoretical guarantees beyond existing minimax approaches. 

Additionally, the algorithm is extended to a differential privacy setting, maintaining its instance-dependent guarantees.
weaknesses: 1. **Limited Practical Relevance of Instance-Dependent Bounds**: 

While the instance-dependent bounds are novel, I feel they are disconnected from practical applications. In many real-world scenarios, problem instances aren’t clearly characterized in terms of hardness, which limits the utility of these bounds. It is also unclear how people could use these refined bounds to benefit practice.

2. **Some parts Hard to Understand**: 

The paper suffers from clarity issues throughout. Key concepts, such as the distinction between the instance-dependent and worst-case bounds, are not well-explained. For instance, the introduction of the hardness parameter $H$ is not intuitive, and sections like Definition 2.2 on consistent instances are particularly difficult to digest. More explanation or discussions would benefit understanding.

3. **Experiments Lack Validity**: 

The experimental validation is weak. The simulations are based on a synthetic dataset, and while this is standard for theoretical work, the lack of real-world testing makes the results less convincing. Furthermore, the comparisons with PESSIMISTIC MLE are only on narrow setups, leaving questions about the general applicability of RL-LOW.

4. **Unclear Motivation for Differential Privacy**: 

The introduction of differential privacy seems tacked on and not well-motivated. There’s little discussion on why privacy is critical for this particular problem setting, and the paper introduces the concept late in the related work section rather than making it part of the core problem setup. This reduces the relevance of the extension. Furthermore, it is also unclear whether the bound under different privacy (in Theorem 5.3) is tight or not in terms of $\epsilon$ and $\delta$.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 1
questions: See weakness.
soundness: 2
strengths: 1.  The preference-based problem is important in the offline RL community. 
2.  Some theoretical guarantees are established for the proposed algorithm.
summary: The paper studies an offline preference-based policy learning problem. This work utilizes the locally optimal weights to construct an instance-dependent algorithm. In theory, the instance-dependent upper bound and lower bound are derived. Further, an extension to the data-privacy setting is studied.
weaknesses: 1. This work considers a linear reward setting, which is more stringent compared to the general reward function setting in the existing literature: a. Chen, Xiaoyu, et al. "Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation." ICML b. Zhan, Wenhao, et al. "Provable offline preference-based reinforcement learning." ICLR. On the other hand, the reward functions are complex and usually require non-linear function approximation. 

2. The reward function is not trajectory-based defined but is just defined on the state-action pairs. The state-action pair setting is inconsistent with the practical applications, particularly natural language processing. See Ramamurthy, Rajkumar, et al. "Is reinforcement learning (not) for natural language processing: Benchmarks, baselines, and building blocks for natural language policy optimization." ICLR. 

3. This paper mentions the underlying problem is a PbRL. However, following careful reading of the setting in Section 2, the problem considered in the paper is essentially a contextual bandit problem. This greatly limits the contribution of the work.

3. The instance-dependent setup is not well explained in the preference-based settings. Particularly, the coverage of the offline data is not discussed in the work. 

4. Definition 2.2: The condition on the consistent instance is strong, which is usually not true in general offline settings. 

5. Equation (6): The clip on the implicit reward is difficult. That is, the bound in the implicit reward is not easy to measure in practice. 

6. The estimation of the locally optimal weight seems very sensitive over the low-coverage samples. Also, the computational complexity is high for estimating the local optimal weight. 

7. Equation (7): the condition of the consistent instance essentially implies good coverage following the definition of the locally optimal weight. 

8. The instance-dependent upper bound seems superficial as compared to the setting in the general offline RL. For example, the dimension of the feature mapping is not in the bound. See Nguyen-Tang, Thanh, et al. "On instance-dependent bounds for offline reinforcement learning with linear function approximation." AAAI.  Some further explanation and discussion on this point are required. 

9. The extension to a privacy-preserve setting is trivial, but the motivation for ensuring privacy in the PbRL problem is not well discussed. 

10. There is a lack of comprehensive empirical studies on the algorithm. The evaluation of the offline PbRL benchmark is necessary. This can better position the paper in the existing literature.  

11. The ablation studies on the instance-dependent upper bound and lower bound in terms of the key parameters are needed. 

12. The presentation of the paper is not clear. There are many notations and some of them are not necessary.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. How is $d^{\pi}$ formally defined? Is it the stationary distribution under the policy $\pi$?
2. It seems like the consistency requirement is mainly to ensure that the dataset at least contains enough information to compare each pair of actions $i,j$ on a state $k$. Is there a setting where such assumption is relaxed and one instead assumes that there is a joint distribution over state and action tuples so that one can ignore the highly unlikely state-action tuples in the final regret bound?
soundness: 4
strengths: The main novelty of the algorithm is the design of Locally Optimal Weights. At a high level, the weights are used to weight to what extend one should take into account the information about a datapoint about state $k’$, action $i’$, and action $j’$ while comparing the rewards of action $i$ and action $j$ on state $k$. Moreover, the weights are constructed to minimize a variance proxy for the comparison result so as to enhance the estimation precision. The technique is sophisticated, and shown in experiment to have non-trivially improved the average simple regret bound.
summary: The work studies simple regret bounds of offline reinforcement learning with preference feedback. Formally, we are given a dataset generated as follows:
1. A state $k$ is drawn from some fixed distribution $\rho$.
2. Two actions $a_0, a_1$ are picked. 
3. A Bernoulli variable $\sigma$ is generated based on the soft-max of the rewards associated with $(k, a_0), (k, a_1)$.

We want to assign each state $k$ a candidate action $a(k)$ so as to minimize the simple regret defined as $  \mathbf E_{ k \sim \rho } [  \text{reward}(k, a^*(k)) - \text{reward} (k, a(k))  ) ] $, where $a^*(k)$ is the action that maximizes the reward of state $k$.

The main contribution is an algorithm that achieves a simple regret bound of $\exp(- O(n/H))$, where $H$ is some complexity parameter that depends on the instance, and a lower bound construction showing that $\exp(- \Omega(n/H) )$ is necessary.
weaknesses: The extension to the MDP setting, where one tries to find optimal policies, rather than just actions that maximize per-state rewards, is rather superficial. First, the authors assume that the transition probabilities are known a priori (though this is the case in prior work as well), which significantly weakens the algorithm’s applicability. Besides, there is likely no mention of the computation complexity of their algorithm in this setting. It seems like the algorithm is just doing brute-force to find a policy $\pi$ that maximizes $\mathbf E_{k \sim d^{\pi}}[ \hat r_{k, \pi(k),1} ]$, which is prohibitively expensive.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Please refer to the weaknesses above.
soundness: 3
strengths: 1. The problem of deriving an instance dependent sub-optimality bound for offline RLHF is well-motivated and interesting.

2. The paper presents the first instance dependent bounds for the setting, while the upper bound matches the lower bound in the order. The paper is solid and the proof looks correct to me.

3. The authors also extend the result to DP-RL setting and the MDP setting, which makes this paper a comprehensive work.

4. The simulation supporting the theoretical findings is convincing.

5. The paper is well-written in general.
summary: In this paper, the authors consider offline reinforcement learning (RL) with preference feedback in which the implicit reward is a linear function of an unknown parameter. They propose an algorithm, RL with Locally Optimal Weights (RL-LOW), which yields a simple regret which decays exponentially as n goes large. Furthermore, they derive a matching instance-dependent lower bound in offline RL with preference feedback. Moreover, they also extend RL-LOW to the setting of differentially private RL and show that the hardness parameter 
 is unchanged in the asymptotic regime as n tends to infinity.
weaknesses: 1. The setting is kind of simple. For the bandit setting, although the reward is linear, the setting is actually tabular (finite states & actions). For the MDP setting, the transition kernel is known. While I understand to derive a gap-dependent analysis as in the paper, the setting is required to be tabular, it seems that the locally optimal weights heavily depend on the tabular nature of the problem.

2. The improvement on the worst-case bound is limited. Meanwhile, the instance-dependent upper bound seems to be well-expected, since given the minimum gap, the failure probability of identifying the optimal arm will decay exponentially as n converges to $\infty$.

3. Previous work [1] derived an instance-dependent sub-optimality upper bound $O(\frac{1}{\sqrt{n}}+\frac{1}{n\epsilon})$ for standard offline RL (explicit reward) with DP. The two terms in [1] seem to match the order of the two terms in (22) of Theorem 5.3. It will be interesting if the author could provide a worst-case version of Theorem 5.3 and compare with the result in [1] to further showcase the cost of privacy.

[1] Offline Reinforcement Learning with Differential Privacy, Dan Qiao and Yu-Xiang Wang.

Overall, I think the instance-dependent sub-optimality bound for offline RLHF is meaningful and the strengths outperform the weaknesses. Therefore, I lean towards acceptance. I will be happy to raise my score if my comments are solved.

Meta-review: The reviewers are unfortunately not excited about the results in the paper, both before and after the rebuttal discussion. While some of the issues raised are superficial (for instance, I do not see any problem in this paper's notation in the first place), the paper is below the bar from a technical merit standpoint. The main issue is that the paper is only studying the much simpler problem of contextual bandits, rather than RL, as the title suggests (as also pointed out by the reviewer). Bandits are much simpler, and there are many more instance-dependent bounds investigated in the bandits literature than in RL. There's a lack of comparison to bandits literature (studied not just in ML/CS, but in operations research and statistics). As such, I view this paper as a warm-up to the ultimate worthwhile pursuit for RL. I would suggest work out the full RL version and submit to ICML.

Decision: Reject