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

Q1: "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."

A1: The reviewer is right in their understanding of our setting. However, note that there is still no research on the instance-dependent analysis within the field of offline PbRL, regardless of whether the transition kernel is known or not and whether the number of states is finite or not. Our work is the first to provide instance-dependent (lower and upper) bounds for offline PbRL, and, we wish, it can inspire further research of instance-dependent analysis within the domain.

Q2: 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$

A2: Indeed, the improvement of the worst-case bound is by an albeit small factor of $\sqrt{\log n}$. Note that the improvement of the worst-case bound is not our focus in this paper -- it is merely a by-product of our analyses. Our focus is on deriving instance-dependent bounds and showing their tightness. Yes, it decays exponentially in $n$, i.e, $\mathrm{Reg}\le\exp(-\Omega(n))$. Most importantly, we formally nail down the hardness constant $H(v)$ in the exponent (i.e., $\mathrm{Reg}\le\exp(- cn/H(v))$) and show, via a matching lower bound, that it is tight.

Q3: Previous work [1] derived an instance-dependent sub-optimality upper bound $\frac{1}{\sqrt{n}} + \frac{1}{\epsilon n}$ 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.

A3: Thank you very much for providing the interesting related work. We have provided the worst-case version of our Theorem 5.3 in the newly added Appendix H.2 of the revised manuscript. In summary, we obtain that the worst-case regret under $(\epsilon,\delta)$-DP yields the form of $\frac{1}{\sqrt{n}} + \frac{1}{\epsilon n}$ for the dependency of $n$ and $\varepsilon$, which is exactly what the reviewer expects. That is, it indeed aligns with the bounds of [1] without preference feedback. We have added these comments and cited the paper of [1] in Section 5 of our revised version. Thanks again for raising this study.

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

Finally, we would like to express our heartfelt thanks again to the reviewer for recognizing our technical contributions, and we are welcome any further questions if the reviewer may have.

(edit: update the appendix letter for the latest revised paper)

Q1: On the computation complexity of finding a policy that maximizes $\pi$ that maximize $\arg \max_{\pi} \\mathbb{E}\_{k \sim d^\pi} [\\hat{r}\_{k,\pi(k),1}]$

A1: Thanks for the question. To calculate $\arg \max_{\pi} \\mathbb{E}\_{k \sim d^\pi} [\\hat{r}\_{k,\pi(k),1}]$, there are two steps.

First, we calculate the empirical reward of $\hat{r}_{k,i,1}$ for each $(k,i)\in \mathcal{S}\times \mathcal{A}$, which takes computational complexity of $\mathcal{O}(SAd + nd^2 + d^3)$.

Second, after we obtain the empirical reward of $\hat{r}\_{k,i,1}$, the next step is exactly the classical RL problem of finding the optimal MDP policy under the condition that the transition probabilities and rewards are known. This classical problem can be solved by using asynchronous dynamic programming [1], which typically takes $O(\kappa SA)$ time complexity, where $\kappa$ is a hyperparameter that represents the average number of iteration, which controls the solution precision. Hence, the overall computational complexity is $\mathcal{O}(SAd + nd^2 + d^3+\kappa SA)$; we have added more details in Appendix E.2.2 of our revised version to address this question. Thanks again for the precious question.

Q2: How is $d^\pi$ formally defined? Is it the stationary distribution under the policy?

A2: Yes, it bears high similarities with the stationary distribution to some extent. Generally, we adopt the notion of state distribution as is in Zhu et al [1], which is standardly defined in Sutton and Barto [2018, Section 9.2]. We have cited this in our revised version to avoid any ambiguity. Thank you very much for the question.

Here we quote the paragraph of Section 9.2 of Sutton and Barto in the following, where they call it "on-policy distributioin":

Let $h(s)$ denote the probability that an episode begins in each state $s$, and let $\eta(s)$ denote the number of time steps spent, on average, in state $s$ in a single episode. Time is spent in a state $s$ if episodes start in $s$, or if transitions are made into $s$ from a preceding state $\bar{s}$ in which time is spent:

This system of equations can be solved for the expected number of visits $\eta(s)$. The on-policy distribution is then the fraction of time spent in each state normalized to sum to one:

This is the natural choice without discounting. If there is discounting $(\gamma<1)$ it should be treated as a form of termination, which can be done simply by including a factor of $\gamma$ in the second term of $\eta(s)$.

Q3: It seems like the consistency requirement is mainly .... in the final regret bound?

A3: Yes, the review is correct in noting that consistency ensures the dataset contains enough information to compare each pair of actions for a given state. This is formally supported by our Proposition 2.3, which shows that achieving vanishing regret is not possible for inconsistent instances. Therefore, our focus in this paper is on the investigation with consistent instances. We also appreciate the reviewer’s insightful idea regarding the idea of 'ignoring highly unlikely state-action tuples.' This is an interesting direction, and we leave it for future study.

[1] Zhu et al. (2023). Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. ICML 2023.

[2] Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.

Finally, we would like to extend our sincere gratitude to the reviewer for acknowledging our technical contributions, particularly on the design of Locally Optimal Weights

(edit: update the appendix letter for the latest revised paper)

Q1: "This work considers a linear reward setting, which is more stringent compared to the general reward function setting in the existing literature".

A1: We agree that considering general reward functions is indeed more flexible. However, prior studies have not considered the derivation of instance-dependent upper and lower bounds even for the linear reward setting. Given that the linear case has not been done, we need to tackle it before considering more general reward settings, which subsume the linear rewards as a special case. We aim for this contribution to serve as a foundational step, offering valuable insights that may guide future research on instance-dependent bounds in more general reward settings.

Q2: "The reward function is not trajectory-based defined but is just defined on the state-action pairs.

A2: Thank you for highlighting this point. Indeed, our reward function is defined based on state-action pairs. We would like to emphasize that both trajectory-based and state-action-based frameworks are valuable but complementary directions in PbRL. For example, in a recent technical report of Ahmadian et al. [1], which is adopted by the TRL library of Huggingface, the authors modelled the entire response as a single action (see in their Section 3.3) rather than use it as a trajectory, which exactly aligns with our Section 2.

Q3: "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."

A3: Thank you for your insightful comments. The reviewer is right that the setting described in Section 2 bears similarities with contextual bandit problems to some extent. However, we wish to draw the reviewer's attention to Section 6, in which the results are extended to include MDPs, thus bringing more realism to the PbRL problem.

Q4: "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.

A4: We are not sure if "the coverage of the offline data" mentioned by the reviewer is exactly the same as that Zhu et al. [2] under offline PbRL. We acknowledge that the coverage of offline data plays a significant role in the worst-case analysis presented by Zhu et al. However, we must admit that our instance-dependent analysis does not currently establish an explicit connection to the concept of "coverage of offline data."

We remain open to further exploration of this topic and would greatly appreciate any insights the reviewer might provide regarding how "coverage of offline data" could be integrated or related to our instance-dependent analysis.

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

A5: Our focus on the consistent instance is supported by Proposition 2.3, which states that it is not possible to get vanishing regret in inconsistent instances. Thus, the notion of consistency is required in our analyses, without which vanishing regret cannot be obtained by any algorithm. Thanks again for the observation.

Q6: "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."

A6: Thanks for the comment. We would like to clarify that our lower and upper bounds do not rely on the CLIP function defined in Equation (6). The CLIP function is utilized solely as a component within our proposed algorithm; this CLIP operation in RL-LOW is efficient and easy to implement.

Q7: 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.

A7: The overall computational complexity of our algorithm is $O(SAd + nd^2 + d^3)$, where the term "$SAd$" corresponds to basic requirement to scan through the feature vectors for all state-action pairs, and the term "$nd^2 + d^3$" corresponds to the complexity of calculating the inverse of a matrix.

In addition, we wish to clarify that the computational complexity's dependency "$SAd$" is inevitable, as we require to output $\hat{i}_k$ for all $k \in \mathcal{S}$ in the setting of our manuscript. Nonetheless, if we remove this output's requirement, the term "$SAd$" indeed be removed in our algorithm, and the overall computational complexity beccomes $O(nd^2+d^3)$. We have added more details in Appendix E.2 of our revised version to address this issue. Thanks again for the comment of computational complexity.

(edit: update the appendix letter for the latest revised paper)

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

A8: We are thankful to the reviewer for providing an insightful observation. In our setting, we wish to highlight that the consistency is required for us to obtain non-vacuous instance-dependent bounds as shown in Proposition 2.3.

Q9: "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.

A9: We thank the reviewer for providing a thoughtful opinion. The dimension is indeed not explicitly in our instance-dependent bound.

For example, let's say $S=1, A=2$, and $d$ is sufficiently large. In addition $\phi(1,1)=[0,1,0,0,\cdots]$, $\phi(1,2)=[1,0,0,0,\cdots]$, and $\theta=[0,1,0,0,\cdots]$. Then, we have $r_{1,1}=0$ and $r_{1,2}=1$. Given the offline dataset with size $n$ (i.e., these are the $n$ historical records for "action $1$ wins action $2$" or "action $2$ wins action $1$" ) under our setting, if the learner picks the action with the most winning records (as it does in our RL-LOW), then by Hoeffding's inequality it will suffer an expected regret of $\exp(-\Omega(n))$ which does not depend on the dimension $d$, and it explains why our upper bound does not explicitly depend on $d$.

In addition, we would like to draw the reviewers' attention that our upper bound yields an exponential decay while Nguyen et al. [3] does not, due to different settings that necessitate different proof techniques.

Thanks again for the careful observation, which enforces the novelty of our upper bound and shows that the setting and techniques differ significantly from Nguyen et al.

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

A10: Our motivation aligns closely with that of Chowdhury et al. [4]. For example, in certain labelling procedures for question-answering (QA) systems, users provide preference labels between two responses for a given question rather than directly submitting their own responses to the question. Consequently, our work prioritizes safeguarding the privacy of these preference labels rather than the privacy of the questions or responses themselves.

Q11, Q12: The issues in empirical study.

A11,A12: We sincerely appreciate the reviewer's thorough and comprehensive evaluation of the empirical studies. While we fully acknowledge and respect these observations, we would like to kindly note that the primary focus of our paper is theoretical, i.e., the establishment of the instance-dependent upper and lower bounds that are {\em tight} in the hardness parameter. In light of this, we hope the reviewer might consider adopting an optimistic perspective on this aspect. Thanks again for the detailed and thoughtful comment.

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

A13: We attach great importance to simplified and clear notations in article writing. We would be very grateful if the reviewer could provide more details on this point.

[1] Ahmadian, et al. (2024). Back to basics: Revisiting reinforce style optimization for learning from human feedback in llms. arXiv preprint arXiv:2402.14740

[2] Zhu et al. (2023). Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. ICML 2023.

[3] Nguyen-Tang, Thanh, et al. "On instance-dependent bounds for offline reinforcement learning with linear function approximation." AAAI.

[4] Chowdhury et al. (2024). Differentially private reward estimation with preference feedback. In International Conference on Artificial Intelligence and Statistics (pp. 4843-4851). PMLR.

Finally, we would like to extend our sincere gratitude to the reviewer for providing the detailed review. We hope that the above replies to the esteemed reviewer are satisfactory. We remain open and happy to answer any follow-up questions the reviewer may have.

Q1: "Limited Practical Relevance of Instance-Dependent Bounds."

A1: Thanks for the comment. We wish to highlight that the significance of instance-dependent bounds is to comprehensively justify that the regret is in the rate of $\exp(-\Omega(n))$ when it is dependent on the sub-optimality gap instead of $\frac{1}{\sqrt{n}}$ (which is only applicable in the worst case). In the study of multi-armed bandits, both worst-case and instance-dependent bounds are useful as they provide complementary insights into the difficulty of the problem. We hope our conclusions provide some insights for real-world applications, as is in many other theoretical papers.

Q2: "Some parts Hard to Understand"

A2: There are essentially two types of regret bounds in the literature -- worst-case and instance-dependent bounds. As the name suggests, the former involves deriving regret over worst-case instances over a certain class of instances. The latter, however, involves deriving regret for a fixed instance. Our derived hardness parameter in both the upper and lower bounds is also rather intuitive. It depends on various suboptimality gaps in an inverse manner. Essentially, the smaller the suboptimality gap, the larger of the hardness, which implies the instance is harder to learn. Furthermore, the introduction of a notion of consistency in Definition 2.2 is inspired by our Proposition 2.3, i.e., it is necessary for deriving non-vacuous regret bounds. Thanks again for the question.

Q3: Experiments Lack Validity:

A3: We are thankful for the comment in terms of the empirical studies. We do not disagree with this point. However, given that the main focus of our paper is theoretical, we hope that the reviewer might consider the issue of the empirical study with an optimistic perspective. Thanks again for the valuable feedback.

Q4: Unclear Motivation for Differential Privacy.it is also unclear whether the bound under different privacy (in Theorem 5.3) is tight or not in terms of $\delta$ and $\varepsilon$.

A4: Our motivation aligns closely with that of Chowdhury et al. [2]. For example, in certain labelling procedures for question-answering (QA) systems, users provide preference labels between two responses for a given question, rather than directly submitting their own responses to the question. Consequently, our work prioritizes safeguarding the privacy of these preference labels rather than the privacy of the questions or responses themselves.

Furthermore, the tightness of the Theorem 5.3 is guaranteed when $n$ is larger than ${(H_{\rm DP}^{(\varepsilon,\delta)}(v))^2}/H(v)$ as explained at the end of Section 5. Thank you very much for submitting this point.

Q5: On the BTL Model Assumptions

A5: Note that the BTL model is very popular/prevalent for modeling human preference feedback. The reviewer is right that the real-world application may not exactly meet the BTL model, we leave this for future research, e.g., considering corruption, mis-specification in the BTL model or the presence of adversaries.

We would like to extend our sincere gratitude for the review's follow-up comments and helpful suggestions.

Q9: I recommend adding a concise yet impactful explanation of what $H$ represents when it is first introduced. For example, you could include an intuitive description or a small example to clarify its meaning.

A9: We are greatly thankful for the advice. We agree that it would be good to present an additional intuitive explanation for $H$. In light of this point, we have provided a newly added Appendix B in our revised version, and we also provide a link to this appendix in Section 3 of the main text. For the convenience of the reviewer's reading, we quote the text in our newly added Appendix B in the following:

The hardness parameter $H(v)$ is inversely proportional to the square of the suboptimality gaps across various states and actions. Specifically, a smaller suboptimality gap implies an increased hardness parameter, indicating that the instance is more challenging to learn. This relationship underscores the significance of the suboptimality gap as a critical measure in evaluating the complexity and learning difficulty of each instance.

For example, let's suppose $S=1, A=2$, $r_{1,1}=0$ and $r_{1,2}=1$. Given offline data with of size $n$ (i.e., these are $n$ history records for "action $1$ wins action $2$" or "action $2$ wins action $1$"), if the learner picks the action with the most winning records (as it does in our algorithm RL-LOW), then by Hoeffding's inequality, it will suffer an upper bound of expected simple regret of $\exp(-C \cdot \frac{n}{ {(r_{1,2}-r_{1,1})^{-2}}})$ for a constant $C$ that does not depend on $r_{1,2}-r_{1,1}$ (in fact this upper bound is also tight in the hardness parameter according to our lower bound). Notice the exponent is $-\Theta(\frac{n}{ {(r_{1,2}-r_{1,1})^{-2}}})$, and the hardness parameter $H(v)$ is exactly $(r_{1,2}-r_{1,1})^{-2}$ under this instance.

Q10: On the motivation of Label-DP

A10: Thanks a lot for the advice. We agree that it is important to present more details for the motivation of why we consider Label-DP. We have provided a newly added Appendix A.2 to present more details on the motivation of label-DP to address this issue. For the convenience of the reviewer, we quote our newly added Appendix A.2 in the following:

In the development of question-answering (QA) systems, a common approach for improving response quality involves engaging users in a labeling process where they are asked to provide preference labels. Specifically, users evaluate pairs of system-generated responses to a given question and indicate which response they prefer. This method, often referred to as pairwise preference labeling, is integral to training RLHF algorithms that aim to optimize the relevance and utility of answers provided by QA systems.

Given our understanding of the nature of this process, our research emphasizes the importance of protecting the confidentiality of user-submitted preference labels. Without any concerted attempt to protect privacy, these labels, which directly reflect individual opinions or biases toward specific types of responses, can potentially reveal sensitive information, e.g., their preferences for some specific political parties. Therefore, we augment our RL-LOW with a label-DP protection mechanism to mitigate the risk of privacy breaches from the labels.

Q1: " The target state distribution $\rho$ is fixed rather than controlled by the chosen policy. A generalization is given in Section 6 but still requires the transition dynamics to be known."

A1: The reviewer is right. Our RL setting indeed requires the transition dynamics to be known in both Sections 2 and 6. Notably, these assumptions align with those made by Zhu et al. [1] in their Sections 1 and 5. More importantly, we wish to highlight that whether or not the transition dynamics are known, prior to our work, there were no instance-dependent bounds in the offline PbRL setting. Our paper thus provides a first step to derive the instance-dependent bounds in the offline PbRL setting for bridging this research gap in the literature.

Q2: 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$. Typical settings in RL with function approximation require dependence on $log S$ to be considered efficient."

A2: Yes, the state/action spaces are assumed to be finite in our current manuscript. However, we wish to highlight that Zhu et al.'s bound not only depends polynomially in $d$, but also depends on a term $\mathbb{E}_{s \sim \rho} (\cdot )$ that is related to state distribution. Hence, their upper bound implicitly depends on the number of states; see Theorem 3.2 in Zhu et al [1].

In addition, it is worth noting that the proposed algorithm of Zhu et al. also requires the computational complexity depending on $S$ rather than $\log(S)$, as they need to calculate a term "$\mathbb{E}_{s \sim q} (\cdot )$" in their algorithm.

Most importantly, we wish to clarify that the computational complexity's dependency $S$ is inevitable, as we require to output $\hat{i}_k$ for all $k \in \mathcal{S}$ in the current setting. Nonetheless, if we remove this output's requirement, the dependency "$S$" is indeed avoidable in our algorithm, and the overall computational complexity becomes $O(nd^2+d^3)$, aligning with the reviewer. We have added more details in our modified Appendix E.2 of our revised version to address this issue. Thank you very much for the precious comment. We hope this reply could adequately address this comment.

(edit: update the appendix letter for the latest revised paper)

We are deeply grateful for the prompt follow-up feedback.

Q7: "Why would $E_{s \sim \rho}[ . ]$ necessarily depend on the number of states?"

A7: The reviewer is right in their special example. Hence, we did not claim $E_{s \sim \rho}[ . ]$ of Theorem 3.2 in Zhu et al. explicitly depend on $S$ but in an implicit way, which is similar to our worst-case bound of Prop 3.4.

The reviewer is correct in noting that we can reduce computation by calculating $\mathbb{E}_{s \sim q}()$ approximately rather than exactly in Zhu et al.'s algorithm; however, it is unclear (for us) how the performance would be affected by doing so for Zhu et al.'s algorithm. Hence, we claim the computation of their algorithm depends on $S$ at least for their original version in A2.

Nonetheless, we would like to highlight that our RL-LOW's computational complexity indeed does not depend on $S$ if we remove an output's requirement, as detailed in our revised Appendix E.2 as well as A2. We hope this could satisfactorily align with the reviewer's expectation for the computational complexity.

Thank you very much for the question, which gives us the chance for further clarification.

Q8: "Though I was pointing out that ....You still cannot get logarithmic sample complexity of learning.".

A8: We wish to highlight that we indeed get a logarithmic sample complexity of learning in our setting.

Specifically, in our settings (in both Sections 2 and 6), the upper bounds of the expected regret are of the form $\exp(-\Omega(n/H(v)))$ in terms of the dependency on $n$. That is to say, to obtain the regret of $\varepsilon$, one needs to take no more than $n =O(\log(1/\varepsilon))$ samples when taking $H(v)$ as a contant, which is indeed a logarithmic function of in $1/\varepsilon$.

More importantly, we wish to emphasize that our upper bound matches our lower bound in Theorem 4.3, elucidating the important role of the hardness parameter $H(v)$. That is, our algorithm is order-optimal and cannot be improved in general in terms of instance-dependent analysis, which is beyond whether it can yield a logarithmic sample complexity.

Admittedly, our result is not applicable to other settings (e.g., those settings that the reviewer considers), and we wish to emphasize the significance of our setting in the following "A9".

Q9: On the significance of the setting.

A9: We agree that it is interesting to consider other various settings, e.g., when the rewards are known and the transitions are unknown.

However, given that our particular setting (i.e., the rewards are unknown, but the transitions are known), which was proposed by Zhu et al. has hitherto not been studied well, we feel it is meaningful to provide a complementary instance-dependent analysis to Zhu et al., elucidating the dependence of the regret on the instance. This setting is also pertinent in LLMs, because the states are represented by prompts and the actions are represented by the next response (or next token). For example, let's say the current state $s=$"the capital of America is". If we take action $a$="Washington", then next state $s'$ is deterministic and known to be $s'$="the capital of America is Washington". That is, the rewards are unknown, but the transitions are indeed known in this application.

We hope that the esteemed reviewer appreciates our contributions to this practically-relevant setting in which we have established the first instance-dependent theoretical results. We kindly wish that the reviewer could adopt optimistic views to the various settings. Thank you so much again for the very detailed follow-up comment.

Update: We simplify "A7" for the ease and efficiency of communication in the rebuttal stage.

Thanks a lot again for the engagement. We apologize for the use of "implicitly" that is ambiguous in A2.

Q10: Their result appears to work even if most (nearly all) states are not visited in the data.

A10: Thanks for pointing it out in Zhu et al.'s results. We would like to highlight that our results also work if most states are not visited in the data.

Note that in our setting, we do not assume any relation between the offline data's proportions $N_{k,i,j}$ and the distribution of states $\rho_k$. For example, let $S=10000$, $d=2$,$A=3$, $N_{1,1,2}=0.5$, and $N_{1,2,3}=0.5$ (i.e., $N_{1,1,3}=N_{k,i,j}=0$ for $k>1$ and $i \neq j$). In addition, let $\rho_k = \frac{1}{10000}$ for all $k \in \mathcal{S}$. In state $1$, let $\phi(1,1)=[0,1]^\top$,$\phi(1,2)=[1,0]^\top$ and $\phi(1,3)=[1,1]^\top$. Furthermore, for any state $k$, suppose $i^*_k$ is unique and $\phi(k,i)\neq \phi(k,j)$ for $i \neq j$.

That is, in the above instance, we only have data in state $1$ and no data for other states, and the $\rho$ is uniform in $\mathcal{S}$. Note that the above instance is a consistent instance from our Def 2.2. Hence, the upper bounds of Theorem 3.3 and Prop 3.4 are valid under this instance.

Q11: "the "full-fledged" RL with preference feedback setting is exponentially harder than the setting" (of Zhu et al. and ours)

A11: We agree. In view of the fact that the present setting is not studied well in the literature, we hope our results can provide some insights for future study of much harder settings in the community.