Provable Offline Preference-Based Reinforcement Learning

Thank you for the valuable feedback! Here are our responses:

• Comparison against Practical Work

We mainly discuss theoretical works in the related works because our paper also focuses on the theory of offline RLHF. That said, our algorithm is still quite different from the practical algorithms presented in [1]. Although they also use MLE to estimate the reward model, they typically run RL algorithms with respect to the learned MLE rewards (i.e., $\hat{r}$ in Algorithm 1) without any pessimism. The lower bound in [Theorem 3.9, 2] has shown that this kind of algorithm can fail in the worst cases.

In contrast, we use pessimism to circumvent such failure. More specifically, we construct a confidence set of the reward model and then evaluate each policy with the most pessimistic reward model inside the confidence set. This is the key difference between our algorithm and existing commonly used algorithms in [1], and this modification is crucial to overcome their limit.

• Reward vs Return

Thanks for pointing it out! We will revise this in the final version.

• Appendix

Thanks for pointing it out! We will move the key points in Appendix to the main paper in the final version.

• Remark 3

We will clarify it as follows. In line 4 of Algorithm 1, we need to compute $\mathbb{E} _ {\tau \sim \mu _ {ref}}[r (\tau)]$, which might be computationally inefficient since the space of all trajectories is large. In this case, we can sample $N_0$ trajectories $(\tau ^ i) _ {i = 1} ^ {N _ 0}$ from $\mu _ {ref}$ and then simply use $\frac{1}{N _ 0}\sum _ {i=1} ^ {N _ 0} r(\tau ^ i)$ as a surrogate of $\mathbb{E} _ {\tau \sim \mu _ {ref}}[r (\tau)]$. From Azuma-Hoeffding inequality, this will only incur an error scaling with $\frac{1}{N _ 0}$. Therefore as long as we choose $N _ 0 = O(1 / \epsilon ^2)$, this error can be neglected while line 4 becomes more computationally efficient.

• Cannot Relaxed to Per-step Concentrability

Theorem 2 shows that there exists a set of MDPs whose rewards are defined per step (i.e., $r(\tau) = \sum _ {h=1} ^ H r _ h (s _ h, a _ h)$) and an offline dataset which satisfies the per-step concentrability such that no offline algorithm is able to learn a near-optimal policy. This implies that with only per-step concentrability, we are not able to find a high-quality policy, even if we assume the rewards of the MDPs are defined per step. In contrast, with our trajectory-wise concentrability coefficient in Definition 2, we are able to learn a near-optimal policy for any MDPs, no matter whether the reward is defined over trajectories or defined per step. We will add this explanation in the final version.

• Missing Reference

We are sorry about the missing references. We list the references here and will add them in the main paper: Per-step concentrability coefficient: [3-7], Optimal policy: [8]

• Definition of $g(\cdot|\tau _ 1,\tau _ 2)$

We are sorry about the unclearness of the definition of $g$. $g$ is a function mapping from $(\mathcal{T} \times \mathcal{T})$ (recall that $\mathcal{T} = (\mathcal{S} \times \mathcal{A}) ^ H$ is the set of all possible trajectories) to $\mathbb{R}^2$ and thus $g(\cdot|\tau _ 1, \tau _ 2)$ is a two-dimensional vector. It doesn’t need to be a distribution, i.e., $g(\cdot|\tau _ 1, \tau _ 2)$ is not necessarily positive and $\Vert g(\cdot|\tau _ 1, \tau _ 2) \Vert _1$ doesn’t need to be 1. Similar functions are elaborated in the definitions in Appendix E. We will revise this in the final version.

• Wrong Symbol and Typo

Thanks for pointing them out! We will correct them in the final version.

[1] Wirth, C., Akrour, R., Neumann, G., Fürnkranz, J., et al. (2017). A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1–46.

[2] Zhu, B., Jiao, J., and Jordan, M. I. (2023). Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. arXiv:2301.11270.

[3] Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. arXiv:2106.06926

[4] Uehara, M. and Sun, W. (2021). Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage. In arXiv:2107.06226.

[5] Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J. (2022a). Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages 2730–2775. PMLR.

[6] Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022). Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv:2202.13890.

[7] Li, G., Shi, L., Chen, Y., Chi, Y., andWei, Y. (2022b). Settling the sample complexity of model-based offline reinforcement learning. arXiv:2204.05275.

[8] Bertsekas, D. P. (2017). Dynamic programming and optimal control. Athena Scientific.

• from $C_r(\mathcal{G} _ r, \pi _ {tar}, \mu _ {ref})$ to $C _ {tr}$ in Questions

Note that in this reduction we take $\mu _ {ref}$ to be $\mu _ 1$. From Cauchy-Schwartz inequality, we have $\sqrt{ \mathbb{E} _ {\tau ^ 0 \sim \pi _ {tar}, \tau ^ 1 \sim \mu _ 1}\big[|r ^ *(\tau ^ 0) - r ^ *(\tau ^ 1) - r(\tau ^ 0) + r(\tau ^ 1)| ^ 2 \big] } \geq \mathbb{E} _ {\tau ^ 0 \sim \pi _ {tar}, \tau ^ 1 \sim \mu _ 1}\big[|r ^ *(\tau ^ 0) - r ^ *(\tau ^ 1) - r(\tau ^ 0) + r(\tau ^ 1)|\big].$

This implies that $C^2_r(\mathcal{G} _ r, \pi _ {tar}, \mu _ 1) \leq \sup _ {r} \frac{ \mathbb{E} _ {\tau ^ 0 \sim \pi _ {tar}, \tau ^ 1 \sim \mu _ 1}\big[|r ^ *(\tau ^ 0) - r ^ *(\tau ^ 1) - r(\tau ^ 0) + r(\tau ^ 1)| ^ 2\big]}{ \mathbb{E} _ {\tau ^ 0 \sim \mu _ 0,\tau ^ 1 \sim \mu _ 1}\big[|r ^ *(\tau ^ 0) - r ^ *(\tau ^ 1) - r(\tau ^ 0) + r(\tau ^ 1)| ^ 2\big]}$

Since $\tau _ 0$ and $\tau _ 1$ are independent, we have $C ^ 2 _ r(\mathcal{G} _ r, \pi _ {tar}, \mu _ 1) \leq \sup _ {r} \max _ {\tau _ 0, \tau _ 1 }\frac{ d ^ {\pi _ {tar}}(\tau _ 0) \mu _ 1(\tau _ 1)}{ \mu _ 0(\tau _ 0) \mu _ 1(\tau _ 1)} =\max _ {\tau} \frac{d ^ {\pi _ {tar}}(\tau)}{ \mu _ 0(\tau)}.$

• $\pi, \mu$ and $d$ in Questions

We are sorry for the unclearness. For $\pi$, we use $\tau \sim \pi$ to denote the distribution of $\tau$ when executing $\pi$ in the MDP. When $\tau$ follows a more general distribution $\mu$, i.e., when the distribution may not be induced by a policy $\pi$, we use $\tau \sim \mu$. For $d$, we only use $d ^ {\pi} (\tau)$ to denote the probability of $\tau$ under policy $\pi$. We will further clarify these in the final version.

[1] Rigter, M., Lacerda, B., and Hawes, N. (2022). Rambo-rl: Robust adversarial model-based offline reinforcement learning. Neurips 2022.

[2] Xie, T., Cheng, C. A., Jiang, N., Mineiro, P., & Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34, 6683-6694.

[3] Cheng, C. A., Xie, T., Jiang, N., & Agarwal, A. (2022, June). Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning (pp. 3852-3878). PMLR.

[4] Uehara, M. and Sun, W. (2021). Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage. ICLR 22

[5] Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint (Vol. 48). Cambridge university press.

[6] Agarwal, A., Jiang, N., Kakade, S. M., & Sun, W. (2019). Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32

Thank you for the valuable feedback. Here are our responses:

• Implementation Details and Empirical Experiments in Weaknesses

We would like to clarify that this is mainly a theoretical work that strives to find sample efficient offline RLHF algorithms with provable guarantees. That said, we would like to point out that we indeed have discussions about the practical implementation of our algorithm in Remark 1 in the main text and Appendix B. In summary, we use the Lagrangian multiplier to convert our algorithm into a maximin optimization problem and demonstrate how to compute the gradient of the objective function so that we can use gradient ascent-descent to solve it. Given this type of gradient descent-ascent has shown superior performance in standard offline RL problems [1], we believe that the above approach can also work well in practice in our preference-based RL setting. We will emphasize this part more in the final version.

• Response to the claim: There are no experiments either. So there is no way to check how this method empirically scales.

We would like to mention that there are many practical and impactful works about offline RL in top machine learning conferences without any experiments. First, for example, in the literature on offline model-free RL, [2] proposed the first provably efficient algorithm with general function approximation. While this paper does not have any experiments, it is later implemented in another follow-up paper [3]. It is reported that the proposed algorithm achieves SOTA and beats many offline RL baselines, such as CQL, COMBO ICL, and TD3+BC.

Similarly, in the literature on model-based RL, [4] proposed the first probably efficient algorithm with general function approximation. While this paper does not have any experiments again, later, it is implemented in another follow-up paper [1], and it is reported that it achieves SOTA and beats many baselines, such as again MOReL, CQL, IQL, and TD3+BC. In this way, even with no experiments, theoretically backed algorithms have been empirically impactful.

• Definition of $g(\cdot|\tau _ 1,\tau _ 2)$ in Weaknesses

We are sorry about the unclearness of the definition of $g$. $g$ is a function mapping from $(\mathcal{T} \times \mathcal{T})$ (recall that $\mathcal{T} = (\mathcal{S} \times \mathcal{A}) ^ H$ is the set of all possible trajectories) to $\mathbb{R}^2$ and thus $g(\cdot|\tau _ 1, \tau _ 2)$ is a two-dimensional vector. It doesn’t need to be a distribution, i.e., $g(\cdot|\tau _ 1, \tau _ 2)$ is not necessarily positive and $\Vert g(\cdot|\tau _ 1, \tau _ 2) \Vert _1$ doesn’t need to be 1. Similar functions are elaborated in the definitions in Appendix E. We will revise this in the final version.

• Proposition 1 in Weaknesses

We would like to state that our bounds are not weak compared to standard RL literature. First, as you notice, the log bracket number increases logarithmically as the accuracy $\epsilon$ decreases. However, as we will later see in Theorem 1, we just set $\epsilon=1/N$, which results in an additional $\log(N)$ term. This term is negligible compared to the leading term $1/N$. Second, the log dependence on $B$ and $R$ is very standard in the literature on statistical machine learning in general, as seen in Section 4,5 in [5] and Definition 8.1 in a standard RL textbook [6].

• Sample Bounds in Weaknesses

We are sorry for the misleading expression. Here, we take $N$ so that the right-hand side of (2) in Theorem 1 is less than $\epsilon$. So, this expression means if $N$ satisfies (2), we can get an $\epsilon$-optimal policy. To remove $N$ from the right-hand side, with some algebra, we can state that as long as $N=O(\log(1/\epsilon)/\epsilon^2)$ (when we just focus on the dependence on $\epsilon$), we can get an $\epsilon$-optimal policy. We will clarify it in the final version.

• $r$ and $r ^ *$ in Questions

No, $r$ and $r ^ *$ are reward functions. They map a trajectory $\tau$ to a scalar. Thus, here $r$ ($r^*$) can be viewed as a vector whose $\tau$-th entry corresponds to the value of $r(\tau)$ ($r^*(\tau)$) for each $\tau \in \mathcal{T}$.

• $C _ {tr}$ in Questions

No, it doesn’t depend on $\mu _ 1$ because when we reduce $C _ r$ to $C _ {tr}$, we take $\mu _ {ref} = \mu _ 1$ in $C _ r(\mathcal{G} _ r, \pi _ {tar}, \mu _ {ref})$ and then $\mu _ 1$ is canceled out by $\mu _ {ref}$.

Dear reviewer,

There are only three days left for the discussion period. Do you have any other questions that we can help with?

Thank you very much for increasing the score! We appreciate your feedback and will try adding some experiments in the future.

Thank you very much for the positive feedback! Here are our responses:

• Empirical Results

We are currently considering adding an empirical case study in future work. That said, we indeed have some discussions about the practical implementation of our algorithm in Appendix B. In summary, we use the Lagrangian multiplier to convert our algorithm into a maximin optimization problem and demonstrate how to compute the gradient of the objective function so that we can use gradient ascent-descent to solve it. Given that gradient descent-ascent has shown superior performance in standard offline RL problems [1], we believe that the above approach can also work well in practice.

• Link Function

Yes, we assume the link function is known. When the link function is unknown, we may consider a link function class $\mathcal{F}$. Then we can generalize our analysis by implementing MLE over the joint function class $(\mathcal{F}, \mathcal{G} _ r)$, i.e., $(\hat {r}, \hat{\Phi}) = \arg\max _ {r \in \mathcal{G} _ r, \Phi\in\mathcal{F}} \sum _ {n=1}^N \log P _ {r,\Phi}(o=o^{n}\mid\tau^{n,1},\tau^{n,0})$ where $P_{r,\Phi}(o= 1\mid\tau^1, \tau ^ 0) := \Phi( r(\tau ^ 1) - r (\tau ^ 0))$. We leave its formal analysis to our future work.

• Unknown Transition Kernel

Yes, the analysis still holds. We reuse the dataset in order to reduce sample complexity, but you can definitely collect a different dataset for transition learning as long as the dataset has a bounded single-policy concentrability coefficient (Definition 3).

[1] Rigter, M., Lacerda, B., and Hawes, N. (2022). Rambo-rl: Robust adversarial model-based offline reinforcement learning. Neurips 22.

Thank you very much for your positive feedback! We are currently considering adding an empirical case study in future work. That said, we indeed have some discussions about the practical implementation of our algorithm in Appendix B. In summary, we use the Lagrangian multiplier to convert our algorithm into a maximin optimization problem and demonstrate how to compute the gradient of the objective function so that we can use gradient ascent-descent to solve it. Given that gradient descent-ascent has shown superior performance in standard offline RL problems [1], we believe that the above approach can also work well in practice.

[1] Rigter, M., Lacerda, B., and Hawes, N. (2022). Rambo-rl: Robust adversarial model-based offline reinforcement learning. arXiv preprint arXiv:2204.12581.