Demonstration-Regularized RL

This paper studies two new hybrid setting which are novel/uncommon in the literature: (i) demonstration regularized RL and (ii) Demonstration Regularized RLHF.

In (i) both expert demonstrations from an $\epsilon$-optimal policy and online access to an MDP with reward function are possible. In (ii) the reward function is not available but it can be inferred thanks to a Preference Based Model introduced in Assumption 4.

This paper studies demonstration-regularized RL where an agent is supposed to find a near optimal policy given an offline dataset that is collected from an expert policy. The paper theoretically shows that given $N^E$ expert samples, the sample complexity of finding a $\epsilon$-optimal policy reduces by a factor of $1/N^E$ in both tabular and linear MDPs. Moreover, the paper extends the proposed method to RLHF and theoretically justify the efficiency of it.

The paper studied demonstration-regularized reinforcement learning (RL), where the learner first performs behavioral cloning on expert-generated demonstrations using maximum likelihood estimation. Then during the online interaction with the underlying environment, the learner penalizes deviation of the learned policy from the one learned in the behavioral cloning phase. The paper provided a theoretical analysis of these two phases. For behavioral cloning, the authors show that the KL divergence between the learned policy and the expert policy decreases linearly as the number of demonstrations grows. This holds for both tabular MDPs and linear MDPs under certain assumptions. Then based on this result, the authors further studied the regularized online learning scenario and the RLHF setting. In both cases, the authors are able to prove a fast convergence rate for the proposed algorithms.

The authors propose KL-regularized online RL algorithms and provide an upper bound on the sample complexity of this algorithm in tabular MDP and linear MDP settings.

In this general comment we would like to make a general clarifications regarding BPI in regularized MDPs. First of all, we would like to acknowledge that each time we refer to UCBVI-Ent algorithm we refer to its version for general regularized MDPs, as it is mentioned in Appendix D.2 of Tiapkin et al. (2023).

Next, we would like to emphasize the differences between UCBVI-Ent and UCBVI-Ent+ allowing the latter algorithm to achieve sample complexity of order $\mathcal{O}(\varepsilon^{-1})$ which improves upon $\mathcal{O}(\varepsilon^{-2})$.

The UCBVI-Ent+ algorithm operates by sampling trajectories based on an exploratory version of the regularized-greedy policy. This exploratory policy corresponds to an optimistic solution of the regularized MDP, distinguishing it from the UCBVI and UCBVI-Ent algorithms, which employ the regularized-greedy policy without additional exploration. The unique aspect of the UCBVI-Ent+ algorithm involves a novel randomization over the horizon, denoted as $H$. Specifically, at a randomly chosen time step, the policy acts greedily concerning a gap between upper and lower bounds on the optimal Q-value. The formal definition of this exploration policy, denoted as $\pi^{t,(h')}$, can be found in Appendix D.2 after equation (9). The compressed form of the played policy is referred to as $\pi^{\mathrm{mix}, t}$.

Importantly, this additional randomization introduces control over a gap value $G^t$, as defined in equation (10). Notably, $G^t$ scales quadratically with the width of a confidence interval on the optimal Q-value. This quadratic scaling is crucial for achieving fast rates, specifically $\mathcal{O}(\varepsilon^{-1})$. This efficiency is akin to the reward-free algorithm RL-Explore-Ent by Tiapkin et al. (2023), but with an improved dependence on $H$ and $S$. It's worth highlighting that the use of the standard greedy policy would not enable us to control the expected width of the corresponding confidence intervals. This control is essential for exploiting the strong smoothness of our regularized MDP, ultimately leading to the achievement of fast rates.

LSVI-Ent algorithm also actively uses an explorative version of regularized-greedy policy, that allows us to control the quadratic quantity that appears in Lemma 19. As a result, the final rate for a linear case also scales with $\mathcal{O}(\varepsilon^{-1})$ instead of $\mathcal{O}(\varepsilon^{-2})$ in non-regularized setup.

We would like to emphasize a particular proof and algorithmic techniques used in our results and explain why we do not include some of the results in the main text. Unfortunately, due to space constraints we cannot include all these discussions in full length in the main body of the paper. In a new rebuttal revision of the paper we have added a brief discussion on Bernstein conditions for behavior cloning, discussion on assumption for behavior cloning in the linear setting, and an important algorithm difference between UCBVI-Ent and UCBVI-Ent+ that allows to improve the convergence guarantees. It is highlighted by a red color.

• In Section B, we showed $O(1/N)$ convergence rates for behavior cloning. To achieve them, we first switched to smoothed version of the KL-divergence (see e.g. Hazan et al. (2019) for a similar idea) and then verified the so-called Bernstein condition (see e.g. Bartlett & Mendelson, 2006): we showed that the variance of the smoothed version of the policy log-likelihood ratio is controllable by just KL-divergence itself up to some logarithmic multiplicative factors and second-order additive factors. However, since the focus of our paper is mainly on reinforcement learning with demonstrations and preferences, we decided to not include the proof in the main text.

• In Section C, we introduced the setting of RL with demonstrations and state the results on its convergence relying on the analysis of UCBVI-Ent+ and LSVI-Ent algorithms. We decided to focus on a novel demonstration-regularized setting instead of introducing the regularized BPI algorithms since the effect of fast rates is already studied in Tiapkin et al. (2023). This focus allowed us to clearly demonstrate the usefulness of regularization in RL in more practical scenarios from a theoretical viewpoint. Nethertheless, we included a novel algorithmic idea of UCBVI-Ent+ into the main text of the revised version.

• In Section D, we introduced RLHF with demonstrations and proposed a simple algorithm that shares similarity with real-world algorithms that have already been applied to fine-tuning of large language models (see Remark 6). To show the theoretical properties of these demonstration-regularized algorithms, we have to 1) show the theoretical properties of MLE estimate of the underlying reward function and 2) upper bound the policy error by applying Bernstein-type inequality introduced by Talebi & Maillard, (2018) and by verifying the Bernstein condition.

  • Theoretical properties of MLE estimate of reward function were already studied in the literature, see Lemma 2 by Zhan et al. (2023a) and we decided to not include them in the main text. However, we did not find the proof of the statement we exactly need in references and provided the proof for completeness in Appendix F.

  • Regarding the bounding the policy error, we did not include the proof since it is very technical and heavily relies on the existing Bernstein-type inequalities in terms of KL-divergence by Talebi & Maillard, (2018).

However, if the reviewers have a different viewpoint and might suggest a better organization of the achieved results, we would be happy to implement it.

Hazan, E., Kakade, S., Singh, K., & Van Soest, A. (2019, May). Provably efficient maximum entropy exploration. In International Conference on Machine Learning (pp. 2681-2691). PMLR.

Bartlett, P. L., & Mendelson, S. (2006). Empirical minimization. Probability theory and related fields, 135(3), 311-334.

Overall Assessment:

The paper presents a significant theoretical contribution to the field of Reinforcement Learning (RL), particularly in the domain of demonstration-regularized reinforcement learning and reinforcement learning with human feedback (RLHF). The authors have theoretically quantified how expert demonstrations can improve the sample efficiency of RL, offering new insights into the utility of expert demonstrations in RL and RLHF settings.

Strengths:

• Theoretical Depth: The paper offers a rigorous theoretical analysis, including proofs and convergence guarantees for behavior cloning procedures under general assumptions.
• Novelty: The demonstration-regularized reinforcement learning framework and its application in RLHF are novel contributions, offering fresh perspectives on leveraging expert demonstrations in RL.
• Practical Relevance: The approach aligns with practical applications, particularly in settings where expert demonstrations are available, making the findings relevant for real-world RL applications.

Weaknesses:

• Presentation and Clarity: Multiple reviewers pointed out issues with the presentation, particularly the heavy reliance on appendices and lack of clarity in explaining proof techniques and algorithmic contributions in the main text.
• Assumptions and Limitations: The assumption of near-optimal expert demonstrations and the lack of empirical validation were noted as limitations, although these are somewhat mitigated by the theoretical nature of the work.

Reviewer Consensus:

While there were initial concerns regarding the presentation and the assumptions made in the paper, the authors addressed most of these through revisions and clarifications. The reviewers appreciated the theoretical contributions and the clarity improvements made in response to feedback. The consensus leans towards acceptance, recognizing the paper’s contribution to the theoretical understanding of RL with expert demonstrations.

Accept (poster)