Offline Data Enhanced On-Policy Policy Gradient with Provable Guarantees

Thanks for your review! We would like to address the following concerns that have been raised.

Our results depend on an all-policy concentration while recent offline rl literature only depends on single-policy concentrability.

We would like to point out that our definition of $C_{off}$ is, in fact, single-policy concentration, instead of all-policy concentration. In particular, it is consistent with the form of concentration used by pessimism-based offline RL literature [1], where in their practical algorithm they also need the concentricity to hold for all $\mathcal{T}^\pi,\pi \in \{ \pi_1,..,\pi_T\}$ generated by the policy gradient algorithm. In principle, we could also write our assumptions in the same way, but since $\pi_1,...,\pi_T$ are all algorithm-dependent quantities, we simply replace it with $\max_\pi$. Furthermore, it can be shown that $C_{off}$ is weaker than the single-policy density ratio.

[1] Xie, Tengyang, et al. "Bellman-consistent pessimism for offline reinforcement learning." Advances in neural information processing systems 34 (2021): 6683-6694.

Could we weaken the assumption of $C_{NPG, \pi^e}$ to be dependent on some functional forms?

Yes, we can replace the density ratio at least by a fraction of square error under the two distributions in the form of $\max_\pi \max_{f \in \mathcal{F}}\frac{E_{s,a \sim d^{\pi^e}}(f(s,a) - Q^\pi(s,a))^2}{E_{s,a \sim d^{\pi}}(f(s,a) - Q^\pi(s,a))^2}$. Indeed, Equation 22 in the appendix is the only place where we used the definition of $C_{npg}$ and we can relax the assumption to the minimum needed for that inequality to hold. We will add a discussion on this in the final version of the paper.

What is the technical contribution of the paper?

The main technical challenge of this paper is to achieve best-of-both-world type guarantees where we can still achieve meaningful results where either offline or online assumptions fail. This can be particularly meaningful in real-world problems where it is hard to verify the assumptions. To do this, we propose a novel HPE subroutine in Algorithm 2, where we optimize simultaneously for TD error and monte carlo regression loss and we need to carefully balance the statistical error term from the TD error and monte carlo regression such that the error of the other term does not blow up when the realizability of one term is not met. In fact, the TD error and the MC regression error interleave with each other and our analysis uses one to supervise the other (e.g., MC regression error is used to bound the Bellman residual under the offline distribution). The entirety of Appendix B is dedicated to this proof.

Does a better coverage of the offline distribution provide a better performance?

In our experiments, we follow a similar setup to [1] where the offline distribution is generated by an epsilon greedy policy (on top of the optimal policy) to ensure both sufficient coverage and the average performance of the offline data is around 3% of the optimal policy. The choice of offline distribution is carefully chosen such that $C_{off,\pi_e}$ is bounded while naive methods such as behavior cloning is only as good as the epsilon-greedy policy.

[1] Song, Yuda, et al. "Hybrid rl: Using both offline and online data can make rl efficient." arXiv preprint arXiv:2210.06718 (2022).

What is a sufficient condition on the policy class to ensure the same sample complexity bound in Theorem 1?

The full assumptions, update rules, and discussions on parameterized policy class are presented in Appendix D. We will move it to the main body for the final version of the paper.

How does the simulation reflect the benefit of HNPG when Bellman completeness is not satisfied? It seems that the HNPG always has the dominant performance regardless of the Bellman completeness?

Although it is hard to tell from Figure 2, a comparison between the learning curves and loss curves in Figure 3 and Figure 4 in the appendix shows that HNPG is actually more at an advantage in the case of image-based comblock without Bellman completeness. In Figure 4, we can see that with Bellman completeness, in the short horizon case, RLPD can actually learn faster if tuned properly. However, by examining the loss curve we can find that the online TD error has a much larger fluctuation compared to the online Monte Carlo regression loss, potentially due to the instability of optimization in practice caused by bootstrapping in TD-style algorithms. This could explain why even with Bellman completeness, HNPG dominates the performance in the long horizon case.

Thanks for your review! We would definitely improve the presentation of Figure 2 to make it clearer to tell the difference between two approaches.

Thanks for your review! We would like to address the following concerns that have been raised.

What is the technical challenge in combining Hybrid RL with natural actor critic?

The main technical challenge of this paper is to achieve best-of-both-world type guarantees where we can still achieve meaningful results where either offline or online assumptions fail. This can be particularly meaningful in real-world problems where it is hard to verify the assumptions. To do this, we propose a novel HPE subroutine in Algorithm 2, where we optimize simultaneously for TD error and monte carlo regression loss and we need to carefully balance the statistical error term from the TD error and monte carlo regression such that the error of the other term does not blow up when the realizability of one term is not met. In fact, the TD error and the MC regression error interleave with each other and our analysis uses one to supervise the other (e.g., MC regression error is used to bound the Bellman residual under the offline distribution). The entirety of Appendix B is dedicated to this proof.

We emphasize that, to the best of our knowledge, and despite being simple, our hybrid PE algorithm 2 is new. Prior work either just focuses on pure on-policy algorithms or pure offline TD-style algorithms. There is no provable work that attempts to combine them together. By combining these two components together into a single objective in a principled manner, we managed to get the best of both worlds style results.

The assumption for online RL such as realizability of Q^{\pi} and the definition of $C_{NPG}$ is too strong and invalidates the claim of best of both worlds.

We would like to first note that $Q^{\pi}$ realizability is a very standard assumption in the Policy Gradient literature. For example, prior works (including [1,2,3]) all use this Q^\pi realizable assumption (indeed, assumptions in [1,3] are stronger than Q^\pi being realizable).

Furthermore, our definition of $C_{NPG}$ is only single-policy concentration with respect to a single comparator policy $\pi_e$ and it can be shown that our definition of $C_{NPG}$ is weaker than the single-policy density ratio $\|\frac{d^{\pi^e}}{\nu}\|_{\infty}$ where $\nu$ is the reset distribution. The notion of a good reset distribution is also a standard assumption in PG literature [4,5]. In particular, Page 124 Figure 0.1 of [5] shows that without a good reset distribution, PG methods can easily get stuck in a local optimum.

There are indeed two cases where online guarantees hold while offline guarantees fail. Firstly, when the offline distribution is not admissible (generated by some policy) we can no longer show $C_{off, \pi_e}^2 < C_{npg, \pi_e}$, and it is possible that $C_{off, \pi_e}^2$ is unbounded while $C_{npg, \pi_e}$ is bounded. Secondly, and more importantly as shown in our simulation experiments in Section 6, when the offline distribution is admissible but the Bellman completeness assumption does not hold, the online guarantee of our algorithm is still meaningful.

[1] Xie, Tengyang, et al. "Bellman-consistent pessimism for offline reinforcement learning." Advances in neural information processing systems 34 (2021): 6683-6694.

[2] Weisz, Gellert, et al. Online RL in Linearly $q\textasciicircum\pi$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore, In Advances in Neural Information Processing Systems. MIT

[3] Qinghua Liu, Gellért Weisz, András György, Chi Jin, & Csaba Szepesvári. (2023). Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RL.

[4] Kakade, S. (2001). A Natural Policy Gradient. In Advances in Neural Information Processing Systems. MIT Press.

[5] Agarwal, A, Jiang N, Kakade, S, Sun, W. (2022). Reinforcement Learning, Theory and Algorithms.

Intuition of the superior performance of HNPG in the comblock environment.

Compared with pure online RL such as TRPO, HNPG is better in the use of offline data to help explorations in hard exploration environments such as comblock. Comparing state-of-the-art hybrid RL approaches such as RLPD, they rely heavily on Bellman completeness by doing bootstrapping for both online and offline data. In HNPG, the dependence on Bellman completeness is relaxed by doing Monte Carlo regression for online data thus working better for the real image observations where Bellman completeness does not necessarily hold.

Thanks for your review! We would like to address the following concerns that have been raised.

The requirement of a linear critic in Algorithm 3.

We would like to clarify that the linear critic in Algorithm 3 is practical for the following two reasons: 1) the feature used in Algorithm 3 is $\nabla \ln \pi(a|s)$ which is equal to $\nabla \pi(a|s)/\pi(a|s)$ where $\nabla \pi(a|s)$ is the neural tangent kernel, i.e., define $\phi(s,a) := \nabla \pi(a|s)$, the kernel $k(z,z’) = \phi(z)^T \phi(z’)$ is called a neural tangent kernel ([1] and Lemma 8.1.1 of [2]). Therefore, the linear regression in Algorithm 3 is actually neural tangent kernel linear regression, and the neural tangent kernel has been shown to be expressive. 2) Practical implementations of NPG like TRPO uses fisher information matrix to precondition the gradient and it can shown that it is equivalent to first do regression with $\nabla \ln \pi(a|s)$ feature.

How big is $C_{off}$ in Definition 3?

We would like to note that $C_{off}$ is only a single-policy concentrability instead of an all-policy concentrability, and it is the same as many practical algorithms in the offline RL literature that uses NPG analysis for offline RL. In particular, it is consistent with the form of concentration used by pessimism-based offline rl literature [3], where in their practical algorithm they also need the concentrability to hold for all $\mathcal{T}^\pi,\pi \in \{ \pi_1,..,\pi_T\}$ generated by the policy gradient algorithm. In principle, we could also write our assumption in the same way, but since $\pi_1,...,\pi_T$ are all algorithm-dependent quantities, we simply replace it by $\max_\pi$. Furthermore, it can be shown that it is smaller than the single-policy density ratio $\|\frac{d^{\pi^*}}{\nu}\|_{\infty}$ where $\nu$ is the reset distribution.

The definition of NPG with respect to some comparator policy?

Our definition of NPG only requires coverage of a single policy instead of requiring coverage of all policies (as commonly used in the NPG literature such as [4,5]). It can be shown that our definition of $C_{NPG}=\max_\pi |\frac{d^{\pi^*}}{d^\pi}|_{\infty}$

is weaker than the single-policy density ratio of the reset distribution $\|\frac{d^{\pi^*}}{\nu}\|_{\infty}$ except a factor of $\frac{1}{1-\gamma}$.

We also note that positivity of reset distribution, while being sufficient is not necessary for bounded $C_{NPG}$. In cases where we do not have positivity of the reset distribution, $C_{NPG}$ could be bounded when the MDP dynamics is favorable. As an example, a typical case where $C_{NPG}$ holds is Ergodic MDP (for example, see Assumption 2 from [6]) which implies that the probability of any policy to visit any reachable state is strictly positive.

In equation (1), can we obtain y with bootstrapping?

Using bootstrapping to get y typically requires the assumption of Bellman completeness (e.g., algorithms like TD which use bootstrapping often require very specific assumptions to guarantee to succeed), which is not needed in standard NPG analysis. In order to achieve online RL guarantees when the assumption of Bellman completeness does not hold, we choose to use Monte Carlo estimation for y.

[1] Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems. Curran Associates, Inc..

[2] Raman, A., et al. “The Theory of Deep Learning”

[3] Xie, Tengyang, et al. "Bellman-consistent pessimism for offline reinforcement learning." Advances in neural information processing systems 34 (2021): 6683-6694.

[4] Kakade, S. (2001). A Natural Policy Gradient. In Advances in Neural Information Processing Systems. MIT Press.

[5] Agarwal, A, et al. (2022). Reinforcement Learning, Theory and Algorithms.

[6] Fabien Pesquerel, & Odalric-Ambrym Maillard (2022). IMED-RL: Regret optimal learning of ergodic Markov decision processes. In Advances in Neural Information Processing Systems.

Thanks for the detailed response. All of my questions have been addressed.