Provable Reward-Agnostic Preference-Based Reinforcement Learning

Thank you for the positive feedback! Here are our responses.

• Presentation

Thanks for the suggestions! We will move some key points in the Appendix to the main paper.

• Relation to $\widehat{P}$

We use $\widehat{\phi}$ and $\widehat{\Sigma}$ to denote the quantities evaluated under $\widehat{P}$ to simplify the writing. We will further remark this in the paper.

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 for the valuable feedback! Here are our responses.

• Worst-case Sample Complexity (in Weaknesses)

We admit that $\kappa$ will scale with $\exp(H)$ in the worst case. This quantity occurs in all the existing theoretical works on PbRL [1-3] and seems inevitable for MLE estimators. That said, in the sparse-reward setting which is very common in practice, $r _ {max}$ is typically $O(1)$ and thus $\kappa$ will also be negligible. In addition, to circumvent the scaling of $\kappa$, we also consider action-based setting in the paper where we only scale with $\exp(B _ {adv})$, which is guaranteed to be not greater than $r _ {max}$ and often much smaller in practice [4].

• General comments (in Weaknesses)

We agree that [1] focuses on regret minimization while our goal is to improve sample complexities in terms of PAC-learnability. We will make it more clear in our final version.

• Why Markovian Policies Are Sufficient

This is an excellent point; but, this is not due to linear reward parametrization. Instead, it is because while human feedback relies on the whole trajectories, rewards in actual MDPs are per-step rewards, i.e., the reward function is a mapping from $\mathcal{S}\times\mathcal{A}\times [H]$ to $[0,1]$. Hence, in this MDP, there exists an optimal policy which is Markovian [5]. Therefore, in Step 4 we only need to search within Markovian policies too. Note that the objective of Step 1 is to ensure the dataset can cover the optimal policy and arbitrary output policies such that the estimated reward is accurate under these policies. Now that the optimal policy and output policy are both Markovian, we only need to consider Markovian policies in lines 4-7 in Algorithm 1.

On the other hand, If we consider more general trajectory-wise reward, i.e., the reward function maps directly from a trajectory to $[0, r _ {max}]$ as in other PbML work [2], the optimal policy might not be Markovian and then we will also need to consider non-Markovian policies in line 4-7 in Algorithm 1.

• Requirement of Linear Reward Parametrization

We agree that “it is necessary to make structural assumptions about the reward” is a bit informal. We were not trying to make a formal statement here. We will change the wording into a “we make structural assumptions as in other works [1,3]”.

In a nutshell, here originally, we just wanted to convey that we need some structural assumptions for generalization, and we chose linear models as these structural assumptions. For example, in the literature on standard supervised learning, the former statement (necessary to assume structure) is often formalized as VC dimension needs to be finite to ensure learnability. Yeah, but to say formally in our context, we need to establish certain lower bounds as you mention. Hence, we will just remove it.

• Direct Maximization

This is a good point. Direct maximization of human preference is possible and has been studied theoretically as the well-known dueling bandits problem [8-10]. However, in practice, in PbRL, people usually first train a reward model and then use the reward model for downstream learning [11-15]. We think this is because after learning a reward model, people can use the reward model to score an arbitrary number of trajectories or even reuse the model in other related tasks, thus reducing a large amount of human cost. Therefore, due to the wide application of such a framework, we also assume an underlying reward model in this paper.

• Relation to Inverse RL

While there are some similarities as you mention, we think PbRL is still very different from inverse RL. Most importantly, in inverse RL, the actions are sampled from an expert policy directly and thus we only need to learn a reward function that matches such expert behaviors. However, in PbRL, the pair of actions is not sampled from an expert and can possibly be undesirable.

• Technical Novelty

The novelty of our techniques mainly lies in the design and analysis of the reward-agnostic trajectory collection procedure (line 4-7 in Algorithm 1). We will try to emphasize more in the final version. More specifically, our analysis deals with the following challenges that are not solved in the literature:

1. First, almost all the reward-free exploration literature is focused on learning the transition dynamics of the MDPs. Our problem is completely different because our main task is to learn the reward function from human preferences. Consequently, our iterative collection procedure (line 4-7 in Algorithm 1) also differs from the reward-free exploration literature. For example, [17] is the closest work to ours and studies the reward-free exploration in linear MDPs. They utilize a variant of UCB-LSVI, which is quite different from our collection procedure. Correspondingly, we can not directly use the existing analysis either and need to come up with new proofs.

2. Second, our framework is also different from the existing online PbRL [6-7]. In their algorithms, the reward-learning process and exploration phase are not decoupled and the analysis heavily relies on the utilization of optimism. In contrast, our algorithm does not use optimism, and thus their analysis techniques also do not apply here.

3. Third, our analysis of REGIME-lin differs from the one in the literature on linear MDPs. This is because while the style of our algorithm is akin to multi-policy evaluation in linear MDPs, the current literature of linear MDPs mainly focuses on Q-learning-style algorithms for policy optimization [16-17].

More specifically, in REGIME-lin, we want to evaluate all the policies in a policy class under a certain reward function. This brings a new challenge that does not occur in [16-17]: our learning difficulty will scale with the size of the policy class $\Pi$. This forces us to find and analyze an appropriate policy class that is able to approximate the optimal policy while retaining a relatively small size. In addition, a key component of our analysis is the new concentration inequality in Lemma 13, which also differs from the existing concentration lemma in [16-17] and may be of independent interest.

[1] Saha, Aadirupa, Aldo Pacchiano, and Jonathan Lee. "Dueling RL: Reinforcement Learning with Trajectory Preferences." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[2] Chen, Xiaoyu, et al. "Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation." International Conference on Machine Learning. PMLR, 2022.

[3] Zhu, Banghua, Jiantao Jiao, and Michael I. Jordan. "Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons." arXiv preprint arXiv:2301.11270 (2023).

[4] Ross, Stéphane, Geoffrey Gordon, and Drew Bagnell. "A reduction of imitation learning and structured prediction to no-regret online learning." Proceedings of the fourteenth international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, 2011.

[5] Bertsekas, Dimitri. Dynamic programming and optimal control: Volume I. Vol. 4. Athena scientific, 2012.

[6] Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. "Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms." Advances in neural information processing systems 34 (2021): 13406-13418.

[7] Huang, Baihe, et al. "Towards general function approximation in zero-sum markov games." arXiv preprint arXiv:2107.14702 (2021).

[8] Yue, Yisong, et al. "The k-armed dueling bandits problem." Journal of Computer and System Sciences 78.5 (2012): 1538-1556.

[9] Zoghi, Masrour, et al. "Relative confidence sampling for efficient on-line ranker evaluation." Proceedings of the 7th ACM international conference on Web search and data mining. 2014.

[10] Dudík, Miroslav, et al. "Contextual dueling bandits." Conference on Learning Theory. PMLR, 2015.

[11] Ouyang, Long, et al. "Training language models to follow instructions with human feedback." Advances in Neural Information Processing Systems 35 (2022): 27730-27744.

[12] Glaese, Amelia, et al. "Improving alignment of dialogue agents via targeted human judgements." arXiv preprint arXiv:2209.14375 (2022).

[13] Ramamurthy, Rajkumar, et al. "Is reinforcement learning (not) for natural language processing?: Benchmarks, baselines, and building blocks for natural language policy optimization." arXiv preprint arXiv:2210.01241 (2022).

[14] Xue, Wanqi, et al. "PrefRec: Preference-based Recommender Systems for Reinforcing Long-term User Engagement." arXiv preprint arXiv:2212.02779 (2022).

[15] Shin, Daniel, Anca D. Dragan, and Daniel S. Brown. "Benchmarks and algorithms for offline preference-based reward learning." arXiv preprint arXiv:2301.01392 (2023).

[16] Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." Conference on Learning Theory. PMLR, 2020.

[17] Wang, Ruosong, et al. "On reward-free reinforcement learning with linear function approximation." Advances in neural information processing systems 33 (2020): 17816-17826.

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

• Presentation

Thanks for the suggestions! We will add more margins around equations in the final version. In addition, as far as we know, the existing theoretical online PbRL works [1-2] focus on regret minimization and only an offline PbRL paper [3] studies PAC algorithm. The PAC sample complexity of [1-2] is derived from the corresponding regret bound. We will try to add the table in the final version.

• Sample Complexity in [1]

We are sorry that a $\log(1/\delta)$ term is missed in the complexity. We will correct this in the final version. In addition, [1] only studies the regret bound so we derive the PAC sample complexity directly from the regret bound, i.e., $K$ such that $reg (K ) / K \leq \epsilon$. As far as we know, the existing theoretical online PbRL works [1-2] focus on regret minimization and do not have a specific PAC learning bound.

• Computational Efficiency and Practical Implementation

The main computational obstacle lies in line 5 of Algorithm 1. To implement the algorithm in practice, gradient ascent can be applied here to solve the optimization problem. More specifically, assume that $\pi ^ 0$ and $\pi ^ 1$ are parameterized by $\nu ^ 0$ and $\nu ^ 1$ (for example, they might be parametrized by a neural network). Then the gradient of the objective $f(\nu ^ 0,\nu ^ 1) := \Vert \widehat{\phi}(\pi ^ 0) - \widehat{\phi}(\pi ^ 1) \Vert _ {{\widehat{\Sigma}} ^ {-1} _ n}$ with respect to $\nu ^ 0$ (gradient of $\nu ^ 1$ can be similarly computed) can be computed as:

$\frac{\partial f(\nu ^ 0 , \nu ^ 1)}{\partial \nu ^ 0} = 2 \frac{\partial \widehat{\phi}(\pi ^ 0)}{\partial \nu ^ 0} \cdot {\widehat{\Sigma}} ^ {-1} _ n \cdot (\widehat{\phi}(\pi ^ 0) - \widehat{\phi}(\pi ^ 1)).$

Here $\widehat{\phi} (\pi ^ 0)$ and $\widehat{\phi}(\pi ^ 1)$ can be estimated efficiently by simulating $\pi ^0$ and $\pi ^ 1$ in $\widehat{P}$. For $\frac{\partial \widehat{\phi}(\pi ^ 0)}{\partial \nu ^ 0}$, we show in Section 4 that each coordinate of $\widehat{\phi}(\pi^0)$ is indeed a value function with respect to a certain reward function under $\widehat{P}$. Therefore we can apply the techniques in policy gradient literature such as REINFORCE to estimate $\frac{\partial \widehat{\phi}(\pi ^ 0)}{\partial \nu ^ 0}$ efficiently. We will incorporate this explanation in our paper.

• Intuition about Reward Free vs Reward Dependent Collection

We agree the phenomenon you mentioned has indeed been shown in the literature of standard reward-free exploration RL [3-4], where the sample complexity of the reward-free algorithms is only slightly worse than reward-aware algorithms [5-6]. However, in PbML, we won’t necessarily see this phenomenon.

1. First, reward learning in PbRL is much more difficult than reward learning in standard RL in the sense that rewards in standard RL could be just learned from regression over $r$ onto a pair of $(s,a)$ at single-time point; but, rewards in PbRL need to be learned from exploratory data over the whole trajectories (not a pair of $(s,a)$). Due to the difficulty of reward learning, it is unclear whether a reward-aware adaptive data collection process leads to better sample complexity in PbRL because learned awards could be very inaccurate before exploring the whole trajectory very well. That’s why our algorithm has a better sample complexity than [1], even in terms of not only the sample complexity of human feedback $N_{hum}$ but also the sample complexity of transitions $N_{tra}$, as we mention at the end of Section 3.

2. Second, compared to standard RL, we need to make a distinction between sample complexity in terms of human feedback $N_{hum}$ and the sample complexity of trajectories $N_{tra}$. If we implement adaptive experimental designs depending on learned rewards, this means we need to query human feedback (to accurately learn rewards) while we explore over trajectories. This results in larger sample complexity in terms of $N_{hum}$ while we might be able to successfully decrease $N_{tra}$, which may be undesirable because in practice human feedback is often more expensive than trajectories.

• Insights for Regret Minimization

We think this generalization is possible. For example, we can collect trajectories for reward learning and dynamics learning separately in different frequencies. When the dynamics is more complicated, we can query human feedback and update the reward model less often to wait for the learning of the dynamics. This can potentially reduce the human feedback complexity.

[1] Saha, Aadirupa, Aldo Pacchiano, and Jonathan Lee. "Dueling RL: Reinforcement Learning with Trajectory Preferences." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[2] Chen, Xiaoyu, et al. "Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation." International Conference on Machine Learning. PMLR, 2022.

[3] Jin, Chi, et al. "Reward-free exploration for reinforcement learning." International Conference on Machine Learning. PMLR, 2020.

[4] Wang, Ruosong, et al. "On reward-free reinforcement learning with linear function approximation." Advances in neural information processing systems 33 (2020): 17816-17826.

[5] Azar, Mohammad Gheshlaghi, Ian Osband, and Rémi Munos. "Minimax regret bounds for reinforcement learning." International Conference on Machine Learning. PMLR, 2017.

[6] Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." Conference on Learning Theory. PMLR, 2020.

• Technical Contributions

Most importantly, the novelty of our algorithm mainly lies in the reward-agnostic trajectory collection procedure (line 4-7 in Algorithm 1). For the other steps in the framework, we follow the common practice in empirical works and thus they are the same as the practical work. Our reward-agnostic trajectory collection procedure takes inspiration from the existing works in reward-free exploration RL and online PbRL. However, it is not a simple combination of the existing algorithms. More specifically, our analysis has the following challenges that are not solved in the literature. We will incorporate this explanation in the final version.

1. First, almost all the reward-free exploration literature is focused on learning the transition dynamics of the MDPs. Our problem is completely different because our main task is to learn the reward function from human preferences. Consequently, our iterative collection procedure (line 4-7 in Algorithm 1) also differs from the reward-free exploration literature. For example, [2] is the closest work to ours and studies the reward-free exploration in linear MDPs. They utilize a variant of UCB-LSVI, which is quite different from our collection procedure. Correspondingly, we can not directly use the existing analysis either and need to come up with new proofs.

2. Second, our framework is also different from the existing online PbRL [6-7]. In their algorithms, the reward-learning process and exploration phase are not decoupled and the analysis heavily relies on the utilization of optimism. In contrast, our algorithm does not use optimism and thus their analysis techniques also do not apply here.

3. Third, our analysis of REGIME-lin differs from the one in the literature on linear MDPs. This is because while the style of our algorithm is akin to multi-policy evaluation in linear MDPs, the current literature of linear MDPs mainly focuses on Q-learning-style algorithms for policy optimization [1,2].

More specifically, in REGIME-lin, we want to evaluate all the policies in a policy class under a certain reward function. This brings a new challenge that does not occur in [1,2]: our learning difficulty will scale with the size of the policy class $\Pi$. This forces us to find and analyze an appropriate policy class that is able to approximate the optimal policy while retaining a relatively small size. In addition, a key component of our analysis is the new concentration inequality in Lemma 13, which also differs from the existing concentration lemma in [1,2] and may be of independent interest.

• Reasons of the Sample Complexity Improvement

As pointed out in the paper, we believe this is because [6] couples the reward learning process with dynamics learning. Consequently, part of the human feedback is also utilized to learn the dynamics and thus wasted. In contrast, our algorithm decouples these two learning processes and human feedback is only utilized to learn the reward, leading to more efficient human feedback complexity.

[1] Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." Conference on Learning Theory. PMLR, 2020.

[2] Wang, Ruosong, et al. "On reward-free reinforcement learning with linear function approximation." Advances in neural information processing systems 33 (2020): 17816-17826.

[3] Jin, C., Liu, Q., and Miryoosefi, S. (2021a). Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms.

[4] Zanette, A., Lazaric, A., Kochenderfer, M., & Brunskill, E. (2020, November). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning (pp. 10978-10989). PMLR.

[5] Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning (pp. 2826-2836). PMLR.

[6] Saha, Aadirupa, Aldo Pacchiano, and Jonathan Lee. "Dueling RL: Reinforcement Learning with Trajectory Preferences." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[7] Chen, Xiaoyu, et al. "Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation." International Conference on Machine Learning. PMLR, 2022.

[8] Zhu, Banghua, Jiantao Jiao, and Michael I. Jordan. "Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons." arXiv preprint arXiv:2301.11270 (2023).

[9] Qiu, Shuang, et al. "Contrastive ucb: Provably efficient contrastive self-supervised learning in online reinforcement learning." International Conference on Machine Learning. PMLR, 2022.

[10] Zhang, Tianjun, et al. "Making linear mdps practical via contrastive representation learning." International Conference on Machine Learning. PMLR, 2022.

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

• Practical Insights and Computational Efficiency

1. We first want to clarify that this work mainly focuses on the statistical complexity of PbRL and attempts to explain the advantages of the current practical PbRL framework from the perspective of sample complexity. For practical insights, we agree that empirical experiments can further verify our claims. However, we do not think theoretical analysis cannot provide insights to explain the advantages of current PbRL in practice. Instead, we believe that by studying the theoretical properties of some simplified cases (such as the linear reward parametrization setting in this paper), we are able to dig out the mathematical explanation behind the phenomenon in practice, and make actual algorithms more sample efficient. As a matter of fact, from the sample complexity comparison against existing works, our paper provides the following insights into practical algorithm design: 1) decoupling the interaction with the environment and the collection of human feedback could lead to reduced sample complexity in theory 2) if we want to use fewer human feedback, we need to make the query dataset as diverse as possible such that it can cover the feature space.

We do not have empirical evidence, but we would like to point out that a lot of important theoretical works also focus on theoretical analysis and lack empirical evaluation, from standard RL [1-5] to PbRL [6-8]. Among them, the algorithms in [3-8] are not computationally efficient either. In particular, as far as we know, [6-7] are the only existing online PbRL algorithms with provable guarantees, and their algorithms are even harder to implement than ours in practice because the optimization problems in their algorithms have more constraints and are much more complicated.

2. Second, for computational efficiency, the majority of computational cost lies in line 5 in Algorithm 1. To implement the algorithm in practice, gradient ascent can be applied here to solve the optimization problem. More specifically, assume that $\pi ^ 0$ and $\pi ^ 1$ are parameterized by $\nu ^ 0$ and $\nu ^ 1$ (for example, they might be parametrized by a neural network). Then the gradient of the objective $f(\nu ^ 0,\nu ^ 1) := \Vert \widehat{\phi}(\pi ^ 0) - \widehat{\phi}(\pi ^ 1) \Vert _ {{\widehat{\Sigma}} ^ {-1} _ n}$ with respect to $\nu ^ 0$ (gradient of $\nu ^ 1$ can be similarly computed) can be computed as:

$

\frac{\partial f(\nu ^ 0 , \nu ^ 1)}{\partial \nu ^ 0} = 2 \frac{\partial \widehat{\phi}(\pi ^ 0)}{\partial \nu ^ 0} \cdot {\widehat{\Sigma}} ^ {-1} _ n \cdot (\widehat{\phi}(\pi ^ 0) - \widehat{\phi}(\pi ^ 1))

$

Here $\widehat{\phi} (\pi ^ 0)$ and $\widehat{\phi}(\pi ^ 1)$ can be estimated efficiently by simulating $\pi ^0$ and $\pi ^ 1$ in $\widehat{P}$. For $\frac{\partial \widehat{\phi}(\pi ^ 0)}{\partial \nu ^ 0}$, we show in Section 4 that each coordinate of $\widehat{\phi}(\pi^0)$ is indeed a value function with respect to a certain reward function under $\widehat{P}$. Therefore we can apply the techniques in policy gradient literature such as REINFORCE to estimate $\frac{\partial \widehat{\phi}(\pi ^ 0)}{\partial \nu ^ 0}$ efficiently. We will incorporate this explanation in our paper.

3. Third, although our analysis posits linear models, we can potentially extend our algorithms to the one with deep neural networks. This is roughly done after learning representations with deep neural networks and treating it as a feature $\phi$. This type of extension is commonly used in the literature of standard RL [9,10]. Since the focus in our paper is to establish theoretically provably efficient algorithms without any heuristics, we explain this possible extension in the section of future works.

Dear reviewer,

There are only three days left for the discussion period. Are you satisfied with our response, or do you have any other questions that we can help with?

Dear reviewer,

This is the last day of the discussion period. Are you satisfied with our response? If so, would you consider raising the score?