Offline Data Enhanced On-Policy Policy Gradient with Provable Guarantees
Authors: Yifei Zhou
Ayush Sekhari
Yuda Song
Wen Sun
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning theory
hybrid reinforcement learning
actor critic method
online reinforcement learning
offline reinforcement learning
Primary area: reinforcement learning

Abstract: Hybrid RL is the setting where an RL agent has access to both offline data and online data by interacting with the real-world environment. In this work, we propose a new hybrid RL algorithm that combines an on-policy actor-critic method with offline data. On-policy methods such as policy gradient and natural policy gradient (NPG) have shown to be more robust to model misspecification, though sometimes it may not be as sample efficient as methods that rely on off-policy learning. On the other hand, offline methods that depend on off-policy training often require strong assumptions in theory and are less stable to train in practice. Our new approach integrates a procedure of off-policy training on the offline data into an on-policy NPG framework. We show that our approach, in theory, can obtain a *best-of-both-worlds* type of result --- it achieves the state-of-art theoretical guarantees of offline RL when offline RL-specific assumptions hold, while at the same time maintaining the theoretical guarantees of on-policy NPG regardless of the offline RL assumptions' validity. Experimentally, in challenging rich-observation environments, we show that our approach outperforms a state-of-the-art hybrid RL baseline which only relies on off-policy policy optimization, demonstrating the empirical benefit of combining on-policy and off-policy learning.

Published conference paper at ICLR 2024
OFFLINE DATA ENHANCED ON-POLICY POLICY GRA-
DIENT
WITH PROVABLE GUARANTEES
Yifei Zhou
Ayush Sekhari MIT sekhar 1@mit. edu
Yuda Song
University of California, Berkeley (yifei_zhhie ltteeei_hhoo@beeeleeyyoo
Carnegie Mellon University yudas
dos os. cmu edu
Wen Sun
Cornell University
ws4558cornell.edh
ABSTRACT
Hybrid RL is the setting where RL agent has access to both offline data and online data by interacting with the real-world environment. In this work, we propose hybrid RL algorithm that combines on-policy actor-critic method with offline data. On-policy methods such as policy gradient and natural policy gradient (NPG) have shown be more robust to model misspecification, though sometimes it may not be as sample efficient as methods that rely on off-policy learning. On the other hand, offline methods that depend on off-policy training often require strong assumptions in theory and are less stable to train in practice. Our new approach integrates procedure of off off-policy training on the offline data into an on-policy NPG framework. We show that our approach, in theory, can obtain pest-of-both-worllee type of result - it achieves the state-of-art theoretical guarantees of offline RL when offline RL-specific assumptions hold, while at the same time maintaining the theoretical guarantees of on-policy NPG regardless of the offline RL assumptions' validity. Experimentally, in challenging tich-observation environments, we show that our approach outperforms a state-of-the art hy hybrid RL baseline which only relies off- off-policy policy optimization, demonstrating the empirical benefit of combining on-policy and off-policy learning. Our code is publicly available at https://ggihubb.co YifeiZhouQ2/HNPG.
INTRODUCTION
On-policy RL methods, such as direct policy gradient (PG) methods (Williams, 1992; Sutton et al., 1999; Konda & Tsitsiklis, 1999; Kakade, 2001), are a class of successful RL algorithms due to their compatibility with rich function approximation (Schulman et al., 2015), their ability to directly optimize the cost functions of interests, and their robustness model-misspecificationn (Agarwal et al., 2020). While there are many impressive applications of on-policy PG methods in high-dimensional dexterous manipulation (Akkaya et al., 2019), achieving human-level performance in large-scale games (Vinyals et al., 2019), and finetuning large language model with human feedback (Ouyang al., 2022), the usage of on-policy PG methods often limited the setting where huge amount of training data. This is majorly due to the fact that on-policy PG methods do not reuse old data (i.e., historical data that are not collected with the current policy to optimize evaluate).
afford
On the other hand, offline RL asks the question of how to reuse existing data. There are many real- world applications where we have pre-collected offline data (Fan al., 2022; Grauman et al., 2022), and the goal of offline RL is to learn a high-quality policy purely from offline data. Since offline data typically generated from sub-optimal policies, offline RI methods rely on off-policy learning (e.g.. Bellman-backup-basee
learning such as Q-learning and Fitted Q Iteration (FQI) (Munos & Szepesvári, 2008)). While the vision of offline RL is promising, making offline RL work in both theory and practice is often challenging. In theory, offline RL methods rely strong assumptions on the function
First authors contribute equally.

---

Published as a conference paper at ICLR 2024
approximation (e.g,, classic off offlpo Temporal Difference (TD) Learning algorithms can diverge without strong assumptions such as Bellman completeness (Tsitsiklis & Van Roy, 1996)). In practice, unlike on-policy PG method which directly performs gradient ascent on the objective of interests, training dellman-backuu based value learning procedure in an off-policy fashion can be unstable (Kumar et al., 2019) and less robust to model misspecification (Agarwal et al., 2020). In this work, we ask the following question: Can we design an RL algorithm that can achieve the strengths of both on-policy and offline RL methods? We study this question and provide an affirmative answer under the setting of hybrid RL (Ross & Bagnell, 2012; Song et al., 2023), which considers the situation where in addition to some offline data, the learner can also perform online interactions with the underlying environment to collect fresh data. Prior hybrid RL works focus on the simple approach of mixing both offline data and online data followed by iteratively running off-policy learning algorithms such as FQI (Song et al., 2023) or Soft Actor-Crité Critic (SAC) (Nakamoto al., 2023; Ball et al., 2023) both of which are off-policy methods that rely on Bellman backup or TD to learn value functions from off- policy data. We take an alternative approach here by augmenting on- on-policy PG methods with an off-policy learning procedure on the given offline data. Different from prior work, our new approach combines on-policy learning and off-policy learning, thus achieving the best of both worlds guarantee. More specifically, on the algorithmic side, we integrate the Fitted Policy Evaluation procedure (Antos et al., 2007) (an off-policy algorithm) into the Natural Policy Gradient (NPG) (Kakade, 2001) algorithm (an on-policy framework). On the theoretical side, we show that when standard assumptions related to offline RL hold, our approach indeed achieves similar theoretical guarantees that can be obtained by state-of-art theoretical offline RL methods which rely on pessimism conservatives (Xie et al., 2021), I), while at the same time, our approach always maintains the theoretical guarantee of the on-policy NPG algorithm, regardless of the validity of the offline RL specific assumptions. Thus, our approach can still recover the on-policy result while the offline component fails.
On the practical side, we verify our approach on the challenging oich-observation combination lock problem (Misra et al., 2020) where the agent has to always take the only correct action at each state to get the final optimal reward (see Section for more details). This RL environment has been extensively used in prior works to evaluate an RI. algorithm's 's ability to do representation learning and exploration simultaneously (Zhang et al., 2022b; Song et al., 2023; Agarwal et al., 2023). Besides the standard rich-observation combination lock example, we propose more challenging variant where the observation is made of real-world images from the Cifar100 dataset (Krizhevsky, 2009). In the Cifar 100 augmented combination lock setting, the RL agent can only access images from the training set during training and will be tested using images from the test set. Unlike standard Mujoco environments where the transition is deterministic and initial state distribution is narrow, our new setup here stresses testing the generalization ability of an RI. algorithm when facing real-world images states. Empirically, both benchmarks, our approach significantly outperforms baselines such as pure on-policy method PPO and a hybrid RL approach RLPD (Ball et al., 2023) which relies on only off-policy learning.
2 RELATED WORKS
On-policy RL. On-policy RL defines the algorithms that perform policy improvement or evaluation using the current policy's 's actions or trajectories. The most notable on-policy methods are the family of direct policy gradient methods, such as REINFORCE (Williams, 1992). Natural Policy Gradient (NPG) (Kakade, 2001), and more recent ones equipped with neural network function approximation such as Trust Region Policy Optimization (TRPO) (Schulman al., 2015) and Proximal Policy Optimization (PPO) (Schulman et al., 2017). In general, on-policy methods have some obvious advantages: they directly optimize the objective of interest and they are nicely compatible with general function approximation, which contributes to their success on larger-scale applications ( (Vinyals et al., 2019; Berner al., 2019). In addition, (Agarwal et al., 2020) demonstrates the provable robustness to the "Delusional Bias" (Lu et al., 2018 8) while only part of the model is well-specified.
Off-policy/ offline RL. Off-policy learning uses data from behavior policy that not necessarily the current policy that we are estimating or optimizing. Since off-policy methods rely on the idea of bootstrapping (either from the current or the target function), in theory, stronger assumptions are required for successful learning. Foster et al. (2021) showed that realizability alone does not guarantee sample efficient offline RL (in fact, the lower bound could be arbitrarily large depending on the state space size). Stronger conditions such as Bellman completeness that in policy setting, when equipped with function approximation, classic TD algorithms indeed do not guarantee to converge (Tsitsiklis & Van Roy, 1996), and even converged, the fixed point
required. It is also well-known
2

---

Published a conference paper at ICLR 2024
solution of TD can be arbitrarily bad (Scherrer, 2010). In addition. (Agarwal et al., 2020) provided counter-examples for TD/Q-learning style algorithms' failures on partially misspecified models. These negative results all indicate the challenges of learning with offline or off-policy data. On the other hand, positive results are present when stronger assumptions such Bellman completeness (Munos & Szepesvári, 2008). While these assumptions are off- policy/offline learning specific and can be strong, the fact that TD can succeed in practice implies such conditions can hold in practice (or at least hold approximately).
Hybrid RL. Hybrid RL (Song et al., 2023) deñines the setting where the learning agent has access to both offline dataset and online interaction with the environment. Previous hybrid RL methods (Song et al., 2023; Ross Bagnell, 2012; Ball et al., 2023; Nakamoto et al., 2023) perform off-policy learning (or model-based learning) on the dataset mixed with online and offline data. In particular, HyQ (Song et al., 2023) provides theoretical justification for the off-policy approach, and the guarantees presented by HyQ still require standard offline RL conditions to hold (due to the bootstrap requirement). However, our new approach is fundamentally different in algorithm design: although our offline component is still inevitably off-policy with the ideas of bootstrap, we perform on-policy learning with the data collected during online interaction without bootstrap, which gives us a doubly robust result when the offline learning specific assumptions (e.g.. Bellman completeness) do not hold. Additionally, we would like to mention that some other works (Gu et al., 201 7b;a; Xiao et al., 2023; Zhao et al., 2023; Lee et al., 2021), also explored the possibility of achieving the best of both worlds of on on-policy and off- off-policy learning. Despite achieving empirical success, their theoretical guarantees still require a strong coverage condition on the reset distribution, while this work presents a doubly-robust guarantee when either the offline or the on-policy condition holds.
PRELIMINARIES
We consider discounted infinite horizon MDP M = AS,A,,,,, P) where S A are state-action spaces, E (0, 1) is the discount factor, r(s,a) a) E [0, 1] is the reward, μo E ASS x A) is the initial reset distribution over states and actions (i.e., we reset based on a state and action sampled from po), and P E S x A + ASS) is the transition kernel. Note that assuming the reset distribution over the joint space S A. contrary to just resetting over S, a standard assumption used policy optimization literature such as CPI and NPG (Kakade & Langford, 2002; Agarwal et al., 2021).
As usual, given a policy π E + (AA), we denote Q (s((s a) as the Q function of π, and V*(s) (s) as the value function of We denote dt E AS x A) as the average state-action occupancy measure of policy т. We denote V = Eng=po V*(s0) as the expected total discounted reward of n. We denote 7 as the Bellman operator associated with π, i.e., given function ʃ E S x A + I. we have [())]
((, = r(s, a) +
In the hybrid RL setting, we assume that the learner has access to offline data distribution from which it can draw i.i.d. samples 8, a ~ v, = r(s, a), 8' ~ P(s, a) to be used for learning (in addition to on-policy online interactions). The assumption that the learner has direct access to can be easily relaxed by instead giving the learner a dataset D of samples drawn i.i.d. from v. For a given policy æ, we denote d' the average state-action occupancy measure, starting from Poo
In our algorithm, given a policy π. we will draw state-action pairs from the distribution dt defined such that d= (s, a) = (1 ())(((1) a1) E Pr" (sx 8,0, = a)), which can be done by sampling h with probability proportional to y execute π to h starting from (81, a1) ) Mo, and return (sn, a.). Given (x, a), π, to draw an unbiased estimate of the reward-to-go (8 a), we can execute starting from (80, on) := (s; a),, every time step ht, we terminate with probability 7 (otherwise move to h + 1); once terminated at h, return the sum of the undiscounted rewards Σ/= Tr. This is an unbiased estimate of (= a). Such kind of procedure is commonly used in on-policy PG methods, such as PG (Williams, 1992), NPG (Kakade, 2001; Agarwal et al., 2020), and CPI (Kakade & Langford, 2002). We refer readers to Algorithm 1 in Agarwal et al. (2021) for details.
4 HYBRID ACTOR-CRITIC
In this section, we present our main algorithm called Hybrid Actor-Critic (HAC), given in Algorithm 1. HAC takes as input the number of rounds 7,, a value function class J, an offline data distribution v (or equivalently an offline dataset sampled from 2), and a weight parameter X, among other parameters, and returns policy स. HAC runs for T rounds, where it performs few very simple steps at each round t E T. At the beginning of every round, given a policy x' computed in the previous rounds, it first invokes the subroutine Hybrid Fitted Policy Evaluate (HPR), given in Algorithm 2,
3

---

Published conference paper at ICLR 2024
Algorithm Hybrid Actor-Crite (HAC)
Require: Function class F, offline data v, # of PG iteration T,, HPE of iterations K1, K2. weight
parameter À
Initialize f F, set #1 (a)s) & (x,()
2: Set 1j = (1 -
Setn)=(1-)yvo((4)) ylg(())))
3: for = 1, I'....To do
4: Let ft f- HPE((T, F1,,, K2, v, A).
5: (a|ssa))) n' (als) exp(nf" a)), Vs
6: end for
7: Return policy मे Uniform
Algorithm 2 Hybrid Fitted Policy Evaluation (HPE)
Require: Policy и, function class F, offline distribution v, number of iterations K1, K2, weight
1: Initialize fo E F.
2: Sample Don = {s, a, (s, a))} of mon many on-policy samples using π.
3: Sample Duff= = {s, 8 srr)} of mof many offline samples from v.
4: for k === 1..... KI...., K2 do
5: Solve the square loss regression problem to compute:
f& argmin ED. (f(s, 7 (s')))) + fEF
= (1)
6: Sample fresh datasets Don and Dou in lines and above.
7: end for
8: Return
- K2-K, Ek= Lk=Ki+1 Sa. and optionally Doi and Don-
to compute an approximation f of the value function Q" corresponding to n². Then, using the function fr. HAC computes the policy x'+1 for the next round using the softmax policy update: (a+ 8) ix r'(a s) exp((ns((( (s. a)) for 8 E S, where is the step size. This step ensures that the new policy does not change too much compared the old policy.
We next describe the subroutine HPE, our key tool in the HAC algorithm. HPE algorithm takes as input policy n, value funetion class F, offline distribution v, and weight parameter X, among other parameters, and outputs a value function f that approximates Q" of the input policy æ. HPE performs K₂ many iterations, where on the k-th iteration, it computes function fa based on the function fA-1 from the previous rounds. At the k-th iteration. in order to compute fu. HPE first collects dataset Don of mon many on-policy online samples from the input policy n. each of which consists of triplet (s, a. y) where (s,a) ~ dd and is stochastic estimate for Q" (s, a) iee, satisfies Ely] = Q (x, a) (e.g., y can be obtained from a Monte-Carlo rollout). Then, HPE collects a dataset Doi of moff many offline samples (s, a, s', from v, where s' P(- s, a) and r r(s, a). Finally, HPE computes the estimate fs by solving the optimization problem in (I), The first term in (1) corresponds to minimizing TD error with respect to fk-1 under the offline data Don, and the second term corresponds to minimizing estimation error of (s a) under the online dataset Don Note that the second term does not rely the bootstrapping procedure. The relative weights of the terms is decided by the parameter X, given as an input to the algorithm and chosen via hyperparameter tuning in our experiments. Typically, À T]. Finally, after repeating this for K₂ times, HPE outputs f which is computed by taking the average of fa produced in the last K2 K1 iterations' where we ignore the first K₁ iterations to remove the bias due to the initial estimate fo-
The key step in HPE is Eq. which consists of an off-policy TD loss and an on-policy least square regression loss. When the standard offline RL condition
Bellman completeness, holds (i.e., the Bayes optimal T f E F), HPE can return a function f that has the following two properties: (1) is an accurate estimate of Q² a) under d thanks to the on-policy least square loss, (2) f has small Bellman residual under the y² the offline distribution. On the other hand, without the Bellman completeness condition, due to the existence of the on on-policy regression loss, we can still ensure
Averaagig only needed for our thcoretical guarantees. Our experiments in Section do not perform averaging and use the last iterate. i.c (f a) r(s,a) a) -B -. P(),)))) F(s' a²))²
4

---

Published conference paper at ICLR 2024
is a good estimator of Q? under d", This property ensures that we always retain the theoretical guarantees of on-policy NPG. We illustrate these points in more detail in the analysis section.
Parameterized policies. Note that HAC uses softmax policy parameterization, which may be intractable when A is large (since we need to compute a partition function in order to sample from r'). In order to circumvent this issue, we also consider a Hybrid Natural Policy Gradient (HNPG) algorithm (Algorithm 3), that directly works with a parameterized policy class II = { 8 E θ). where is the parameter (e.g., Ty can be a differentiable neural network based policy). The algorithm is very similar to HAC and runs for T rounds, where at each round S T, it first computes Se, an approximation for Q by invoking the HPE procedure. However, it relies on compatible function approximation update the current policy Tgr. For working with parameterized policies, HNPG relies on HPE to also supply an offline dataset Doff of Maff many tuples (s, a) ~ V, and an on on-policy online dataset Don of mon many tuples (s,a) ~ d'', which it uses to fit the linear critic (w²) T V In mg (a|s) (2). We then update the current policy parameter via 0*+1 = 0 + "pw", similar to the classic NPG update for parameterized policy (Kakade, 2001; Agarwal et al., 2021) except that we fit the linear critic under both online and offline data. Another way to interpret this update rule is to investigate the form of w'. Taking the gradient of the objective in (2) with respect to w, setting it to zero, and solving for w. we get that the stationary point should be in the
form of E (d' (s, a))T){ Ea,a d's, (s, Using the fact that ('(ss a) is defined is exactly the fisher information matrix
to be V In T&. (als), we see that (o, computed using both online and offtine data. Thus approach extends the parameterized NPG (Kakade, 2001) to the hybrid RL setting in a principled manner.
Algorithm 3 Hybrid NPG with Parameterized Policies (HNPG)
Require: Function class F, PG iteration T, PE iterations (K1, K2), offline data v, Params X, n. 1: Initialize f E F, and 0² such that TTa = Uniform(A).
2: for .,, T do
3: ft, ",Don D + HIEETT,F,,K,, K2,KIKKK,,... A).
4: Let ø' (s, a) = V log Toe (als) and (s) f' a) - E. Raw (o)
5: Solve the square loss regression problem to compute:
w¹ E argmin [(w o' (s) (s) + AED., (w To'(s,a) (((s)))-((s.a)))) (ss (2)
u
6: Update gt+1 +- 0r + mw'.
7:
end for
8: Return policy के Uniform ( (1. .......,,....................... Tgr++)))
5 THEORETICAL ANALYSIS
In this section, we first present our main theoretical guarantees for our Hybrid Actor-Critic algorithm (HAC), and then proceed to its variant HNPG that works for parameterized policy classes. We start by stating the main assumptions and definitions for function approximation, the underlying MDP, the offline data distribution v,, and their relation to the prior works. We remark that all our assumptions and definitions are standard, and are frequently used in the RL theory literature (Agarwal et al., 2019).
Assumption (Realizability). For any म, there exists a f E F s.I. E (U a) Q" a)) = 0.
We consider the following notion inherent Bellman Error, that will appear in our bounds.
Definition (Point-wise Inherent Bellman Error). We say that F has a point-wise inherent Bellman error Ebe- if for all f E F and policy æ. there exists f E J such that I| -T ff I Ebe-
Note that when be = 0, the above definition implics that for any f E F, its Bellman backup f is in the class F, i.c. F is Bellman complete. While, Bellman completeness is a commonly used assumption in both online (Jin et al., 2021; Xie et al., 2022) and offline RL (Munos & Szepesvári, 2008), our results do not require be = O. In fact, our algorithm enjoys meaningful guarantees, as presented below, even when Bellman completeness does not hold, i.e., Ebe could be arbitrarily large.
We next define the coverage for the comparator policy x", which is common tool in the analysis of policy gradient methods (Kakade & Langford, 2002; Agarwal et al., 2021).
5

---

Published conference paper at ICLR 2024
Definition 2 (NPG Coverage), Given some comparator policy T²,, we say that has coverage Cupg.a over ve for any policy x. we have
S Cupg.x.. where d= is the occupancy measure of x².
Note that Cupg. < OC if the reset distribution μi satisfies /polloo < cc, which is standard assumption used in policy optimization literature such as CPI and NPG (Kakade & Langford, 2002; Agarwal et al., 2021) )). This condition intuitively says that the reset distribution has good coverage over d² making it possible to transfer the square error under d' of any policy π to d= (since we always have that |////d" < 1/1-7 for all æ. by definition of (o)., Finally, introduce the Bellman error transfer coefficient, which allows us to control the expected Belmman under a policy π in terms of the squared Bellman error under the offline distribution v.
Definition 3 (Bellman error transfer coefficient). Given the offline distribution v, for any policy x², we define the Bellman error transfer coefficient as
aaan (T f(x.a) [s,
Coff
max O,
max HIXX SET
V Ea (()) f(8,
where the max; is taken over the set of all stationary policies.
The Bellman error transfer coefficient above was introduced in Song et al. (2023), and is known to be weaker than other related notions considered in prior works, including density ratio (Kakade & Langford, 2002; Munos& & Szepesvári, 2008; Chen & Jiang, 2019; Uehara & Sun, 2021), all-policy concentrability coefficient (Munos & Szepesvári, 2008; Chen Jiang, 2019), square Bellman error based concentrability coefficient (Xie et al., 2021). relative condition number for linear MDP (Uchara et al., 2021: Zhang et al., 2022a), etc. (see Song et al. (2023) for a detailed comparison). Our definition of Bellman error transfer coefficient involves two policies x and π, where πº denotes the comparator policy that we wish to compete with (and is thus fixed), and π is used to define the Bellman transfer from the offline distribution to the occupancy measure induced by n². We take a max w.r.t. all possible π for the underlying MDP as our analysis proceeds by transferring (from under v to d" ") the Bellman error terms corresponding to the policies that are generated by our algorithm, which could be arbitrary.
backups (i.e. the terms 7 fn+1 (s, a) (s, a.) that
Theorem (Cumulative suboptimality). Fix any 8 (0.1), and let be an offline data distribution. Suppose the function class F satisfies Assumption 1. Additionally, suppose that the subroutime HPE is run with parameters K₁ with probability at least 1 6, HAC satisfies the following bounds on cunulative subpotimality w.r.t. any comparator policy n=:
(flog(1/>)), K₂ K₁ + T, and moft Mon 2T (11(2111/88) Then, (1-7)²
Under approximate Bellman Complete (when bb S 1/T):
T
V V so (1-7)²
1
Log(A)T
min Capg. Poft (r
TT
(1 (1-7)) 7)²
Without Bellman Completeness (when Ebe 1/T):
Σv - Va' < o ( (1 (og((A)T +
1 (1 7)2 Cupg.
where n" denotes the policy at round t.
The above shows that T increases, the average cumulative suboptimality EET, V*" -V')/ 1==1 converges to 0 at rate at least O0/vT). Thus, our algorithm will eventually learn to compete with any comparator policy T" that has bounded Capg. (or bounded Coff. . with be S 1/r). Furthermore, our algorithm exhibits a best-of-bond both-worlds behavior in the sense that it can operate both with or without approximate Bellman Completeness and enjoys a meaningful guarantee both cases.
In scenarios when approximate Bellman Completeness holds (i.e. 6b S 1/T), the above theorem shows that our algorithm can benefit from access to offline data, and can compete with any comparator policy re that has small Bellman enror transfer coefficient. This style of bound is typically obtained in pure offline RL by using pessimism, which is typically computationally inefficient (Uchara & algorithm only relies simple primitives like
Sun, 2021; Xie et al., 2021). In comparison, square-loss regression, which can be made computationally efficient under mild assumptions on F (see discussion below); On the practical side, least square regression is much easier to implement

---

Published a conference paper at ICLR 2024
and is even compatible with modern neural networks. Finally, note that, under approximate Bellman Completeness and when C - S Cnpg.r", while our guarantees are similar to that of HyQ algorithm from Song et al. (2023), the performance guarantee for HyQ only holds under the conditions that Bellman completeness (when Eb is small) and the problem has small bilinear rank (Du et al., 2021). In comparison, our algorithm enjoys an on-policy NPG style convergence guarantee even when Sbe or bilinear-rank is large.
When there is no control on the inherent Bellman error, the second bound above holds. Such a bound is typical for policy gradient style algorithms, which do not require any control on Eb Again our result is doubly robust in the sense that we still obtain meaningful guarantees when the offline condition does not hold, while previous hybrid RL results like Song et al. (2023) do not have any guarantee when the offline assumptions (that Cof is small for some reasonable xe or Eb is small) are not met.
Setting nh to be n* (the optimal policy for the MDP), and using a standard online-to-batch conversion, the above bound implies a sample complexity guarantee for Algorithm 1 for finding an e-suboptimal policy w.r.t n². Details are deferred to Section C.1.5.
On the computation side, there are two key steps that need careful consideration: (a) First, the sampling step in line 5 in HAC. Note that for any given s, we have that r'(a | s) o exp(1)
a)), so for an efficient implementation, we need the ability to efficiently sample from this distribution. When |A] is small, this can be trivially done via enumeration. However, when |A| is large, we may need to resort to parameterized policies in HNPG to avoid computing the partition function. (b) Second, the minimization of (1) in HPE to compute f& given fa-1- Note that (1) is square loss regression problem in f, which can be implemented efficiently in practice. In fact, for various function classes F, explicit guarantees for subpotimality/regrel for minimizing the square loss in (1) are well known (Rakhlin & Sridharan, 2014). The above demonstrates the benefit of hybrid RL over online RL and offline RL: by leveraging both offline and online data, we can avoid explicit exploration or conservativeness, making algorithms much more computationally tractable.
Hybrid NPG with Parameterized Policies. We can provide a similar bound as in Theorem 1 for the HNPG algorithm, given in Algorithm 3, that works wth parameterized policy class II (To 0 E {.. In particular, we show that HNPG exhibits a best-of-hest-worldd behavior in the sense that it can operate with/without approximate Bellman Completeness, and in both cases enjoy a meaningful cumulative suboptimality bound. For the theoretical analysis of HNPG, we make additional assumptions that the policy class is well-parameterized, log Te (a s) is smooth w.r.t. the parameter 0, and that W realizes the appropriate linear critics for all π E II; All of these assumptions are standard in the literature on theoretical analysis of NPG algorithms. We defer the exact details of the assumptions, and the cumulative suboptimality bound for HNPG, to Appendix D.
6 EXPERIMENTS
In this section, describe empirical comparison of HNPG with other state-ofthee ooftthe-art hybrid RL methods on two challenging rich-observation exploration benchmarks with continuous action space. Our experiments are designed answer the following questions: (1) Is HNPG able to leverage offline data to solve hard exploration problems which cannot be easily solved by pure online on-policy PG methods? (2) For setting where Bellman Completeness condition does not necessarily hold, is HNPG able to outperform other hybrid RL baselines which only rely on off-policy learning?
Implementation. The implementation of HNPG largely follows from Algorithm 3 and the practical implementation recommendations from TRPO (Schulman et al., 2015). We use a two-layer multi-layer perceptron for Q-functions and policies, plus an additional feature extractor for imaged- environment. Generalized Advantage Estimation (GAE) (Schulman et al., 2018) is used while calculating online advantages. For NPG-based policy updates, we conjugate gradient algorithm followed by a line search to find the policy update direction. Following standard combination lock algorithms (Song et al., 2023; Zhang al., 2022b), instead of a discounted setting policy evaluation, we adapt to the finite horizon setting and train separate Q-functions and policies for each timestep. The pseudocode and hyperparameters are provided in Appendix E.
Baselines. We compare HNPG with both pure on-policy and hybrid off- off-policy actor-crite meth- ods. For pure on-pol method, we use TRPO (Schulman et al., 2015) as the baseline. For hybrid off-policy method, we consider RLPD (Ball et al., 2023), a state-of-the algorithm in Mujoco bench- marks, and tuned the hyperparameters specifically for this environment (see Appendix E). We tried
7

---

Published as a conference paper at ICLR 2024
Continuous Combiook
image-Raeed Reedd Continuous Combrock
hwO
h-1
h=2
P-
hwd
h=0
hw
h=2
hw h-
Figure 1: Illustration for continuous combination lock and maage-based continuous combination lock.
training separate actors and critics for each time step and also training a single large actor and critic shared for all time steps, for both TRPO and RLPD, and report the best variant. We found that using a single actor and critic for RLPD resulted in better performance while the opposite holds for TRPO. Note that imitation learning such Behavior Cloning (Bc) (Bain & Sammut, 1995) and pure offline learning such as Conservative Q-Learning (CQL) (Kumar et al., 2020) have previously been shown to fail on this benchmark (Song et al., 2023). Hybrid Q-learning methods (Hester et al., 2018; Song et al., 2023) or provable online learning methods for block MDP (Du et al., 2019; Misra et al., 2020; Zhang et al., 2022b; Mhammedi et al., 2023) do not apply here due to the continuous action space.
Offline distribution. Following Song al. (2023), erated by an E-greedy policy with - E probability of taking the good action and & probability of taking& a random action. & is taken to be 1/H so that this offline distribution has bounded density ratio for the optimal policy. The size of the offline dataset is set to 50000, and around 32%-36% of the trajectories get optimal rewards, for H ranging from 5 to 50.
suboptimal offline distribution gen-
6.1 CONTINUOUS COMBLOCK
The left part of Figure provides an illustration of a rich observation continuous Comblock of horizon H (Misra et al., 2020; Zhang et al., 2022b). For each latent state, there is only one good latent action (out of 10 latent actions) that can lead the agent to the good states (green) in the next time step, while taking any of the other 9 actions will lead the agent to a dead state (orange) from which the agent will never be able to move back to good states; The reward is available at the good states in the last time step. Every timestep, the agent does not have direct access to the latent state, instead, it has access to a high-dimensional observation omitted from the latent state. More details can be found in Appendix 1. This environment is extremely challenging due to the exploration difficulty and also the need to decode latent states from observations, and many popular deep RL baselines are known to fail (Misra et al., 2020). Built on this environment, we further make the action space continuous. We consider a 10-dimensional action space where a E IR At each timestep, when the agent chooses a 10- 10-dimensional action a, the action is passed through a softmax layer, i.e., p i exp(a) where the distribution p encodes the probability of choosing the 10 latent actions. A latent action is then sampled based on p and the agent transits to the next time step. This continuous Comblock preserves the exploration difficulty where a uniform exploration strategy only has exp(-H) probability of getting the optimal reward. The continuous action space makes this environment even harder and rules out many baselines that are based on Q-learning scheme (e.g.. HyQ from Song et al. (2023))
The sample complexity of our algorithm vs. the baselines are shown in Figure 2; are deferred to Appendix E.2. To begin with, we observe that HNPG can reliably solve continuous Comblock up to horizon 50 with mild sample complexity (50k sub-optimal offline samples and around 30m online samples) despite the challenges of continuous action space. In comparison, TRPO is not able to solve even horizon 5 due to the exploration difficulty in the environment. Although RLPD has the benefit of improved sample complexity (detailed in Appendix E) by reusing past online interactions, it can only solve up to horizon 15. To investigate why off-policy methods cannot solve continuous Comblock as reliably as HNPG, we examine the critic loss of HNPG and RLPD for both online and offline samples. Notably, although both methods maintain a relatively stable critic loss on the offline samples, the online critic loss is more volatile for RLPD since it optimizes the TD error (which requires bootstrap from target network) while HNPG optimizes the policy evaluation error (which is pure supervised learning problem) for online samples. We believe this unstable online critic loss is why off-policy methods fail to learn reliably in this environment.
The loss curves
6.2 IMAGE BASED CONTINUOUS COMBLOCKS
To examine the robustness of HNPG when bellman completeness does not necessarily hold, we carry out experiments on a real-word world- waaldd-imee-bua based continuous Comblock, as depicted in the right part of Figure 1. The only difference between image-based continuous Comblock and continuous
8

---

Published as a conference paper at ICLR 2024
Eet
(Dved
Continouus Comblock
1.0
Imag d Based Condinuous Comblock
3.6
0.0
50
Horizon
Figure 2: Comparison of sample complexity of different algorithms in Continuous Comblock and Image-Based Based Continuous Comblock benchmarks. The number of online samples is averaged over 5 random seeds and the standard deviation is shaded.
Comblock lies in their observation spaces. Specifically, for image-based continuous Comblock, each latent state is represented by a class in cifar (Krizhevsky, 2009) and an observation is generated by randomly sampling training image from that class. After sampling an image, we get the observation by using the "ViT-B/32" CLIP (Radford et al., 2021) image encoder to calculate a pre-trained feature. In addition, in the training environment, the image observations are sampled from the training set of cifar100 00 while in the test environment the image observations are drawn from the val set of c00 Unlike mujoco-basee benchmarks where transition is often deterministic and initial state distribution is narrow, our setting, which uses real-world supervised learning datasets with a clear training and testing data split, challenges the algorithms to generalize to unseen test examples.
To get a sense of the inherent bellman error in Definition 1 for this setting, we conduct supervised learning experiments on c0far100 with the same functions as used for actors and critics (on top of the CLIP feature). The resulting top-1 classification accuracy is 77.7% on the training set and 72. % on the test set, showing that the latent states are not 100% decodable from the pre-trained features using our function class. The fact that our function classes are not rich enough to exactly decode the latent states introduces model misspecification such that Bellman completeness may not hold.
The sample complexity results are shown in Figure 2 (right) and the loss curve results of horizon 5 are shown in Figure 3. First, TRPO fails to solve horizon 5 again due to its inefficient exploration. In this more realistic image- based setting, we observe that RLPD struggles even in horizon 5 and completely fails for horizon 10. In contrast, HNPG not only has a reduced sample complexity for horizon 5 but also reliably solves up horizon 30 with around 10m online samples. To investigate this contrast, we examine the critic loss of HNPG and RLPD for horizon 5. While the offline critic TD loss stays stable for both HNPG and RLPD. the online critic TD loss is exploding for RLPD. This is not surprising since for environments where the Bellman completeness condition does not hold, Bellman backup based methods can diverge and become unstable to train. On the other hand, the on-policy training loss for HNPG is small since the on-policy training is based on supervised learning style least square regression instead of TD-style bootstrapping.
Finally, the train and test learning curves are also reported in Figure 3. It is observed that both the training curve and the test curve of HNPG have smaller variances, indicating that it more stable to train, while those of RLPD have a larger variance, indicating that it is less stable. More importantly, even though two methods reach a similar train set reward in the best random seed, HNPG achieves a larger margin over RLPD in the test environment (around 0.8 compared to 0.6), showing that HNPG is better at generalization since RLPD uses the off-policy algorithm SAC which typically has a much higher updates-to-Ol to-a (gradient updates per (s, a, r, 8') collection) ratio from 1:1 to 10:1, making it possible to overfit to the training data in the replay buffer.
7 CONCLUSION
We propose a new actor-critic style algorithm for the hybrid RL setting. Unlike previous model-free hybrid RL methods that only rely on off-policy learning, our proposed algorithms HAC and (the parametrized version) HNPG perform on on-policy learning over the online data together with an off- policy learning procedure using the offline data. Thus, our algorithms are able to achieve guarantees that are the guarantees of offline RL. when offline RL-specifii assumptions (e.g., Bellman completeness and offline distribution coverage) hold, while at the same time enjoy the theoretical guarantees of on- policy policy gradient methods regardless of the offline RL assumptions' validity. Our experiment results show that HNPG can indeed outperform the pure on- on-policy method, and stay robust to the lack of Bellman completeness condition in practice; In the latter scenario, other off- off-policy hybrid RL algorithms fail. Future research directions include sharpening the rates in our theoretical bounds and trying our algorithmic ideas for large-scale applications.
In particular, our algorithms achieve the sfate-of-art theoretical

---

Published conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We thank Akshay Krishnamurthy and Drew Bagnell for useful discussions. AS acknowledges support from the Simons Foundation and NSF through award DMS-2031883, as well from the DOE through award DE- SC0022199.
REFERENCES
Alckh Agarwal, Nan Jiang, and Sham M Kakade. Reinforcement learning: Theory and algorithms. 2019.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. PC-PG: Policy cover directed explo- ration for provable policy gradient learning. Advances in Neural Information Processing Systems, 2020.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Reseurch, 22(1):441144006 2021.
Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, and Xuezhou Zhang. Provable benefits of representational transfer in reinforcement learning. In Gergely Neu and Lorenzo Rosasco (eds.). Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 2114-2187. PMLR, 12-15 Jul 2023.
Iige Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's cube with robot hand. arXiv preprint arXiv:1910.0713: 2019.
András Antos, Csaba Szepesvári. and Rémi Munos. Fitted q-iteration continuous action-space mdps. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
Michael Bain and Claude Sammut. framework for behavioural cloning. In Machine Intelligence 15, 1995.
Philip J Ball, Laura Smith, Ilya Kostrikov, and Sergey Levine. Efficient online reinforcement learning with offline data. arXiv preprint 2xXxi22302.02488 2023.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint 19X1v:1912.06660, 2019.
Jinglin Chen and Nan Jiang. Information-thhorett considerations in batch reinforcement learning. In International Conference on Machine Learning, 2019.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dud'ik, and John Langford. Provably efficient RI. with rich observations via latent state decoding. In International Conference on Machine Learning, 2019.
Simon Du Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pp. 1826-28366 PMLR, 2021.
Linxi Fan, Guanzhi Wang. Yunfan Jiang, Ajay Mandlekar, Yuncong Yang, Haoyi Zhu, Andrew Tang, De-An Huang, Yuke Zhu, and Anima Anandkumar. Minedojo: Building open-ended embodied agents with internet-scale knowledge. arXiv preprini 2:Xiv:2206.08853 2022.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. In Conference on Learning Theory, 2021.
10

---

Published conference paper at ICLR 2024
Kristen Grauman, Andrew Westbury, Eugene Byrne, Zachary Chavis, Antonino Furnari, Rohit Girdhar, Jackson Hamburger, Hao Jiang, Miao Liu, Xingyu Liu, et al. Ego4d: Around the world in 3,000 hours of egocentric video. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 18995-19012, 2022.
Shixiang Gu, Timothy Lillicrap, Zoubin Ghahramani, Richard E. Turner, and Sergey Levine. Q-prop: Sample-efficient policy gradient with an off- off-policy critic. In International Conference on Learning Representations, 2017a.
Shixiang Gu, Timothy P. Lillicrap. Zoubin Ghahramani, Richard E. Turner, Bernhard Schölkopf, and Sergey Levine. Interpolated policy gradient: Merging on-policy and off-policy gradient estimation for deep reinforcement learning. CoRR, abs/1 abs/1706.000m 706.00387. 2017b.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Picter Abbecl, and Sergey Levine. Soft actor-critic algorithms and applications. arXiv:1812.05500 2018.
Todd Hester, Matej Vecerik, Olivier Pietquin, Mare Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, John Agapiou, Joel 7. Leibo, and Audrunas Gruslys. Deep Q-learning from demonstrations. AAA/ Conference on Artificial Intelligence, 2018.
Chi Jin, 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:13406-13418, 2021.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274, 2002.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Alex Krizhevsky, Learning multiple layers of features from tiny images. 2009.
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buu Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for offline reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
Seunghyun Lee, Younggyo Seo, Kimin Lee, Pieter Abbeel, and Jinwoo Shin. Offline-to-online reinforcement learning via balanced replay and pessimistic q-ensemble, 2021.
Tyler Lu, Dale Schuurmans, and Craig Boutilier. Non-delusional q-learning and value-iteration. Advances in neural information processing systems, 31, 2018.
Zakaria Mhammedi, Dylan J. Foster, and Alexander Rakhlin. Representation learning with multi-step inverse kinematics: An efficient and optimal approach to rich-observation rl, 2023.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. International conference machine learning, 2020.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008.
Mitsuhiko Nakamoto, Yuexiang Zhai, Anikait Singh, Max Sobol Mark, Yi Ma. Chelsea Finn, Aviral Kumar, and Sergey Levine. Cal-ql: Calibrated offline rl pre- pre-training for efficient online fine-tuning, arXiv preprint SXXv:23033005477 2023.
11

---

Published conference paper at ICLR 2024
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances Neural Information Processing Systems, 35: 27730-27744, 2022.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8748-87666 PMLR, 18-24 Jul 2021.
Alexander Rakhlin and Karthik Sridharan. Online non-parametric regression. In Conference Learning Theory, pp. 1262-1264. PMLR, 2014.
Stephane Ross and J Andrew Bagnell. Agnostic system identification for model-based reinforcement learning, arXiv: 1007, 2012.
Bruno Scherrer. Should one compute the temporal difference fix point minimize the bellman residual? the unified oblique projection view. arXiv preprint 10Xiv:001..4360 2010.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. arXiv: 2017.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation, 2018.
Yuda Song, Yifei Zhou, Ayush Sekhari, Drew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid RL: Using both offline and online data can make RL efficient. In The Eleventh International Conference on Learning Representations, 2023.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinoorcceett learning with function approximation. Advances in neural information processing systems, 12, 1999.
John Tsitsiklis and Benjamin Van Roy. Analysis of -ifffereece learning with function approximation. Advances in neural information processing systems, 9, 1996.
Masatoshi Uchara and Wen Sun. Pessimistic model-bbsed offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06626. 2021.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. arXiv:2110.04633 2021.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamneki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)350-3355 2019.
Ronald J Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning. Reinforcement learning, pp. 5-32, 1992.
Chenjun Xiao, Han Wang, Yangchen Pan, Adam White, and Martha White. The in-sample softmax for offline reinforcement learning, 2023.
Tengyang Xie. Ching- An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-comee consistent pessimism for offline reinforcement learning. Advances in Neural Information Processing Systems, 2021.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. arXiv preprint w.Xiv:22/0.04157 2022.
12

---

Published conference paper at ICLR 2024
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption-robuse offline reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 5757-5773. PMLR, 2022a.
Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning block MDPs; A model-free representation learning approach. In International Conference on Machine Learning, 2022b.
Kai Zhao, Yi Ma, Jianye Hao, Jinyi Liu, Yan Zheng, and Zhaopeng Meng. Improving offline-to-online reinforcement learning with q-ensembles, 2023.
13

---

Published conference paper at ICLR 2024
CONTENTS OF APPENDIX
A Preliminaries
15
Hybrid Fitted Policy Evaluation Analysis
17
Missing Proofs from Section
20
C.I Proof of Theorem
20
C.I.1
Supporting Technical Results
20
C.1.2 Hybrid Analysis Under Approximate Bellman Completeness
21
C.1.3
Natural Policy Gradient Analysis (Without Bellman Completeness)
C.1.4 Final Bound on Cumulative Suboptimality
22
C.1.5 Sample Complexity Bound
23
D Hybrid Policy Gradient with Parameterized Policy Classes
25
Update Rule
26
D.2
Proof of Theorem 2
27
D.2.1
Supporting Technical Results
27
D.2.2
Hybrid Analysis Under Approximate Bellman Completeness
29
D.2.3
Natural Policy Gradient Analysis
29
D.2.4
Final Bound on Cumulative Suboptimality
30
D.2.5 Sample Complexity Bound
31
E Experiment Details of Comblock
34
E.1 Details of Combination Lock
E.2 Loss Curves for Comblock Experiments
34
E,3 Implementation Pseudocode
34
E,4 Hyperparameters
35
14

---

Published conference paper at ICLR 2024
Additional notation. Given a dataset D {z}. we denote [p]](=) as its empirical average, i.e. [f(f(=) = [D] ExeD]f())] For any function f, and data distribution μ., we define || = Exgarp ((ssa))] Unless explicitly specified, all log are natural logarithms.
A PRELIMINARIES
The following the well-known Performance Difference Lemma.
Lemma (Performance difference lemma; Kakade & Langford (2002)). For any two policies n, n²,
Va V 1- E Es,and [A (A (s.
where 4 aas 1Q" (8, a)). and A (8,a) = Q" (8, a) V" (s).
Lemma' 2. For any policy and negatiit function g a), we have:
(a) E E (s, a)) S - Baard [g(s, a)].
(b) Es Ptpaa a)] s L and (s(s,a)):
where denotes the initial reset distribution (which is the same for all policies π
Proof. We prove the two parts separately:
(a) The proof follows trivially from the definition of
d (s, a) = (1 (1->) Ho(s, (20(HH00))) a)
Exd((s,0))
(b) Recall that lim, 7dh = O. We start by noting that:
d= (s, a) = (1 - (uo
(d] + ax)
(3)
2 711 - 7)
Σ
(sls + [((.s))(66BS0))))))).
8,0
7(1 7) Σ
(Mo(3, (3. )...)
(8,
8.0
d" (3, ((s3))(s
(4)
3,0
=Bg [P(s|3, ())]s))
where (4) follows by plugging in relation (3) for 8, a. The above implies that for any
function g 2 0,
Σ d' d'
Σ
which implies that
Ex Bar
Eaaad (g(s.
The next lemma bounds the gap between value of the policy T" and policy x (given a value function f) in terms of the expected bellman error of and the gap between ʃ(s, r())) and f(s, +T) 3
'In order keep the notation simple, for stochastic policies n, define f(x, (T)) TE ( [f a)).
15

---

Published conference paper at ICLR 2024
Lemma 3. For any policy n, value function f. and comparator policy x².
V V E aor [ π (so)) (su,
1 R Bs ((T [88, a) - (8, + 1-9 Br ([(8.a) - [8, (s))),
1
+ 1 where for any policy v we define V Bx.and (Q
Proof. We start by noting that v
E aom (0 (so, av)
E ao (r T- (8o))] + E Eao Poo. | (s)) (81)
Es (800 an) + +nEs,, P(.lo,,))))))) [= (== (81)]
+T* - T [80, an) + +T [850 an)]
= =BB rdd [V= ( ((611,T($))) [(51)) + I Boo [T (80, no)l;
where the last line follows from the definition of T f, and the fact that 8o, an no followed by
81 ~ P(- 8o: ao) is equivalent to 81 ~ dō by definition. Using the fact that pi = dō and the
definition of df", we get
E Exx ~po [Q"h (so, ao) [(80 (880))
E so [Qth (80, no) - S(00 x (80))
=yE,, .a mdp Q (s), - ((1, [T f(u, ao) f( an)l + R B aomaay
+ E Boo
[ an) - ((o)))
Repeating the above expansion for the first term in the above, and then recursively for all future terms, along with the fact that lim, 7/h O, get that
V=a Eagmmo [f क7 (s0)))
Σ n E Baa
(()
h=0
00
M ( (0(s, [(s,
h=0
The above implies that
V y=a - Eso-po (S T (su))]] + E.o. Eso. (d(o, ((su)) (80. an)
< Eso wl (50, (so)) ("0 an)ll
A R saand [T (s, ((),a))
0=0
E s.andy [f(s,a) - f(s, ((s)]]
4=0
The following is well-known generalization bound that holds for least squares regression. We recall the version given in Song et al. (2023), and skip the proof for conciseness.
Lemma (Least squares generalization bound, (Song et al., 2023, Lemma 3)). Let R > 0, ó (0. 1), and consider a sequential function estimation setting with an instance space X and target space Let D = ((11.1)).... (IT,, (IT, yr)} be
y. Let H. X + [-R, R) be a class of real folued,functinn dataset of points where Ia Pt := (1 11:t-1), and yt sampled via the conditional probability pe(x.) (which could be adversarially chosen). Additionally, suppose that max, yyl - R and max; max, [x()]] S R. Then, the least square solution h <- argmin TT (h=(((xx)) yr
16

---

Published conference paper at ICLR 2024
satisfies
Ex-pes
(M(()) w)²
inf NER.
Ex-pey-ri [(h(z) y) + 256 1og(21H1/0))
with probability at least 1 - 5.
B HYBRID FITTED POLICY EVALUATION ANALYSIS
In this section, we provide our main technical result for the HPE subroutine Algorithm 2. In particular, show that for any input policy HPE succeeds in finding a value function f that closely approximates Q" on the state action distribution d", and at the same time has small Bellman error (w.r.. backups T*) on the offline data distribution The former guarantee is used for on-policy online analysis, and the latter part is used for the Hybrid analysis.
Lemma Suppose that HPE procedure, given in Algorithm is executed for policy with parameters K1 = + log,( ( t }}
K2 = K1 20 and moft Mon
X²
27 16) Then, with probability at least the output value function satisfies (1-2)*
(a) Es (f(ss - (st a)) a1- minf x. Ebet + 125mat Don.
A(1-7)
Arws (b) E R ( (1~>] I-7
+ Estat)
Dotf,
where Estat 128(1+A)/T.
Proof of Lemma 5. We first define additional notation. For the k-th iteration in Algorithm 2, let - - a')) AE D; =)
[x(f) =
and,
T&x := (e
sa [(f(s, y)
Thus, an application Lemma 4 implies that the optimization procedure (1) satisfies, with probability least 1 5, the guarantee
L(Ja) S min L(F) + Estats
(6)
JEF
where
1 A
(n(2//105
1+
Extat I 256
S 256
(1 7)2
min (Mon: Moft
2T
since the terms in the least squares optimization problem given by the objective (5) satisfies the bound R² < (1 + X) sup,, (s, a)I² (1+)//1>2)).
Now, fix any e [K1 + K2], and define a function Fs E such that
1ife T fk-1 S Ebe:
(8)
which is guaranteed exist from Definition Plugging in fr instead of the corresponding minimizer in the RHS of (6), we get that
Es wu.a (1e [[f (s, - 7f--ffssss/
AE A (fa a) y)
[f <E su ((F - - a²))²1 + XE A ((fe(s. a) - + Estat Due to the linearity of expectation, and adding appropriate terms on both the sides to handle the variance, get that
E, D - T" (5,1(3, AL ()) -
(s,
AEs ((fa(s,)) (=, Estat
(9)
<eb + AB (= Q² a)) Extat
17

---

Published conference paper at ICLR 2024
B8 + aad (sf (s,
Estatt
I-7
where the second last line follows from (8) and the last line uses the fact that be S 2/(11 - 77) since max(s,a))ffl ((s 1-y
for any f and f' E F. The above implies that
B8be
E, a~ ((fa(1, T TT fn-1(s; a)) S dr (r Q" (x, (s,a)) + 1-7 + Estass (10)
and
AEg ((fe(s,a) - Q" -(s. z aa
((f((s,)) - Q" a))
+ Estat (11)
1-7
We next focus our attention on bounding the first term in the RHS above. Note that E as [[ee(s, a) (*, a))
Be -
(T (T -
T -s,,,a)))))s
be
+ 2. [TT - ((
1-9
+ Be [T fA ( (s,
(ii) 48 Es [(7 fx- (s, =])
(s,
(12)
1-
where (i) follows from (8). and simple manipulation of the second term, and (ii) again uses (8) and the fact that sup,,a max [I cc. || fl S 1/(1 7). For the second term above, we have
Exa-a [T a) Q a}} = -"²Eg,a-dt _"-P(((ss)))a==xx(()) ("(
('()
I ~ [ffa- - (s a))
where the second inequality is due to Lemma Plugging this bound back in (12), we get that
45he
Eg (s, a) - Q (s, a)) 1-y + BBe [(k-- - Q (s, (13)
We now complete the bounds on (10) and (11), using the bound in (13).
Bound on (11): Using the relation (13) (11), we get
Es [[/a(s, - Q" (8, a)) < EEs,a
1 1- (1
Q*,,
+
65
+
Estat
where simplified the RHS since y < 1. Recursing the above relation from i: to get that
Ex ((",,,) s S M Exannt (()i(s, (=
1
6êbe
Extat
x-1
6Ebe
Estat A
+ 1- 1 1-7 +
(1 71
where the last line uses the fact that sup supp,alf(s. (f a)l S 2/1-7. Since, the above inequality holds
for all & < Ki + K2, setting Ki = log,( (denotagan(--))
)|
+ we get that
12 Ebe
Estat )
Vk E [K,, Kg] : Es ((fa(s, - (s(sa))))1
(14)
(1 7
1-
x
Bound on (10): Using the bound (14) in (13), we get that
Vk E [2 + 1, K2]
Exaadd [[fe a) (= (1 71-))
16 Ebe
Ysstat
1-7
A
Using the above relation in (10), we get that for all K₁ +
+1 k K2-
20
Adbe
Exaav ((f((8a) - (e
< (1 1-2)
+ Estat
(15)
1-
18

---

Published conference paper at ICLR 2024
where again we used the fact that y E (0, 1).
An alternate bound on (11), We now provide an alternate bound on (11) through an independent analysis. Let f& = Q*, which is guaranteed to be the class F due to Assumption 1. Thus, repeating the same steps till (9) but with this choice of fk, we get that
E B B (ff((s a) T fx-1(8', a²)) 2 + aa [[fa(s, Q"
LBs (Q" (Q*(s. a) T fx-1(s, + Estat.
Ignoring positive terms in the LHS, the above implies that
1 Es (()((s as)
X Es Fs.aaol("10 (8, a) - T Sh- (s,
(Q"
Estat
Estat
(16)
X(1 -))2 X
Combining the above results, we note that for all K + S k S K2,
12
12 12
Bg ((fa(s,a) Q (s))a)) v
min
Ebe +
(17)
(1 7)3
X(1 7)
and,
20
(
XB
(3aa))(/a(s,00)) - (T- 71
1
+ Estat
(18)
We are now ready to complete the proof. Equipped with the bounds in (17) and (18), we note that
K2-Ki Σx=k fk satisfies
Eg (()(s,)) (f(ssa=((((sa) (=,
Ex ((fa(s, Q"
- (s)
K2 Ki
Ki+1
12
12
min
Sb
+
(19)
7
X(1 7)²
where the first line follows from Jensen's 's inequality, and the second line is due (17). Similarly, we have that
Eg,arv ((f(s)) a(s,
Ka
Bea
(IKHHi(s,0)TT//Ma [K, +
Σ
aa(s, -T" -T--1(6,)))
K2 - K1
K2
Kg
< K₂ Ki Bearv
(JKI+I(S,a) - -Ts (Kajs(6ss)-TT/(((ss1))))) +
(Ja(s,a) T Tn)
k Ki+2
K₂
<
K₂ Ki Esaav
+
Σ
( - (T ST-
y)-
7)2
k=Ki+2
20
Xêbe
+ Estat
(20)
(K₂ - K1)(1 2
(1-7)
1-
where the first inequality is an application Jensen's inequality, second inequality simply plus in the fact that max [lffllo. T| S 1/(1 - 77), and the last line simply plugs in (18). Setting
1
K₂ = K1 + 20 (1 - 7)
completes the proof.
19

---

Published conference paper at ICLR 2024
C MISSING PROOFS FROM SECTION 4
C.I PROOF OF THEOREM 1
C.I.1 SUPPORTING TECHNICAL RESULTS
We first provide a useful technical result. In the analysis, (') ( will represent an approximation for the advantage function A (s, a). The following bounds the expected advantage when 8, a are sampled from the occupancy π²
Lemma 6. Supppose f" and nt denote the value function and the policies round t in Algorithm 1. Then, for any 1J S (2-7)/2 and policy H², we have
Σ Es Bs ((. 1-7 v log(A)T.
2
Proof. For the ease of notation, let (((s = (s) - fs, Xt (s)). Recall that the policy m++1, after round f, is defined as
a' 5) exp(nf
la 5) Ea a' 8) exp(nf'(s.
Let Z, = Eo a'(a' s)
be the normalization constant, and note that for any s,
(swr((s) [log (a s) log x (+1 (a s)] = Ea-r-(s) (s) [nff + log( Zt)
(21)
We first bound the term comprising of log( Z.). Note that since 17 S (1-7)/2 and || I 1/(1 - 7)
we have that n/ (8, a) < 1.Thus, using the fact that exp(x) < $1+ x² for any S 1, we have
log( Z = log
Σ
x (a' | exp((F((s
< log
Σ
+ n (1'' |s)(1 + " (()
17² 7)²
n²
< log
1 +
7)2
where in the second last inequality we use the fact that E. raa fs a) by the definition
of ft, and that bb < 1/(1 (1) The last inequality simply uses the fact that log(1 + æ) S x for any x 2 O. Plugging in the above bound (21), and rearranging the terms, we get that
Easr" [f((s) < Bawnr))) [log n - (a 8) log r' (a $)] + (1 (1-
7
"1
Telescoping the above for from to T, and using the fact that log(T(a) 8)) S 0 since T(a 8) S 1. we get that
log ' s)] + T/
Σ (f
s (awar(s) [log n T+1 (a s) - log
"
(1 7)2
1 (s) [log (a s)] + (1 - (1-
T/
<
77
Using the fact that n (s) Uniform(( (A), we get that
Ba- (s) (f) log(A)
n/T
+ (1 - 71
n
Setting 7 = (1 (og)))/////////// (A)/T.
T
2
Σ
Es (F)
Ilg(AA).
I
The final bound follows by taking expectation on both the sides w.r.t. d=
20

---

Published conference paper at ICLR 2024
C.1.2 HYBRID ANALYSIS UNDER APPROXIMATE BELLMAN COMPLETENESS
Let f be the output of Algorithm 2, on policy xf at round t of Algorithm 1. An application of Lemma 3 for each (Tt, S() implies that
T
v
V=
E Bo.
(10 ao)) Q (sv. (sp.aw))
T
(T" -(s,a) a))
+
E s.aada
1
T
T sa -(s
1
We bound each of the terms on the RHS above separately below:
Term 1: We start by noting that
T (s,
E Ba (s, (s)) Q (s,
Σ
f
-Q²
||1
T
||
Q
112
t=1
T
Q
2,
t=1
where the first inequality is due Jensen's 's inequality, and the second inequality is from Lemma 2. Using Lemma 5, we get
Don
Σ Eampo (s) V [ T
1-7
Term Using offline coverage in Definition 3, we get that
Σ E Beandee
[TT ('s (s) Co
D E)s' T fe
< noff. T Aotfi
where the last line follows from the bound in Lemma 5.
Term 3: Lemma implies that
T
Σ
E Banag
2 s 1- Vlog(A)T.
[=1
Combining the above bound, we get that
T
Aon
CoHl.TT V Dott + (1-7)² v (lg(AAT.
E Bawwo y (8)
(s)
v (8)
(22)
C.1.3 NATURAL POLICY GRADIENT ANALYSIS (WITHOUT BELLMAN COMPLETENESS)
Let r" and ft be the corresponding policies and value functions at round t, and recall the definition (ss (s) ('s (s)). Using Lemma 1, get that
E Ex-yo [V (8) - ya' (s)]
E Eraandr [AT (s)
1
21

---

Published conference paper at ICLR 2024
E sand [s)
A 1 1-7 V E B. [(f((s, (( - (s, - a)) as),
s.andr (8, a)]
Ar V BE (( (()(()))) (s,,))))
(23)
where the second-las. line above follows from Jensen's 's inequality, and the last line is by invoking Definition 2. We next bound the second term in the right hand side. Using Lemma 2-(a), we get that
Bx ((f(s,,) A (s, a))
= E Be [("(s,, a) - (s, 7 (()) (= + Q (s, (s)) (2(f(ss, Q (s. + (s) x n' (s)))
(8,
a00
s. (2( Qr (s,a))²= (s) Q (s)
< 4E (s, Q" (s)
<4Amn.
where the second last line follows from Jensen's inequality, and the last line uses the bound from Lemma 5, Plugging the above in (23), we get that
1
2 E Baa (8) + (1-?) v An
Rewuo [ V" (s) S 1
Summing the above expression for all E [T), we get
T Σve ya
T
Σ
E Br [s,
(1 7) Cnpg.ee Aon.
1
Plugging the bound from Lemma 6 in the above, get that
T
2
2T
V
<
(A) + (1 7)
VCngg Don
(24)
(1 (1-7) 7)²
t=1
C.1.4 FINAL BOUND ON CUMULATIVE SUBOPTIMALITY
Combining the bounds from (22) and (24), we get that
T
2
2T
V
Va
min
(A)T +
(1 (1-7) x) VCupg. Aons
(1 1-1- 7)
(a)
A on
(1 (1- 7) v Vlog (og(A)T+ + Coff.ne T
2
T
(1-?) Duff
(25)
where, from Lemma 5, recall that
12
12
Aon
min X Ebe +
(1 - 72
X(1 7)
40
Asbe + Estat
Aoff
(26)
(1 7)
1-7
Plugging in the bounds on Aon and Doff (25), we get that
2
87
8T
Cupg. Estat
(a) < (1 - 7
(AT
Copg min
(
(1 (1->)p
(1 33/2
and,
47
1
4T VEstat
+ T
(1 (1-7)² V /eeb + 7I xe
(b) < (1 3/2
min
Ebe
(1-7)2 v log (og(A)T
Eattat-
X(1 - 7)
(1-7)31²
22

---

Published conference paper at ICLR 2024
Note that À is free parameter the above, which is chosen by the algorithm. We provide an upper bound on the cumulative suboptimality under two separate cases (we set different value of X, and get a different bound on Estat in the two cases):
Case 1: Ebc & 1/r: In this case, we set X = 1. Thus, from the bound in (7), we get that
Estat S 128//T which implies that
2
8T
27
(a) - (1 7)2
[ATT +
(1 (1- 7)2 C Ebe + (1 (1- V Cupg.
2
30
$ (1 7)2 log( (A)T +
(1 - 7)² Cnpg.arTT
where the last line follows from the fact that bbe 1/T and Estat S 128/T. Additionally, we also have that
4T
4T /Estat
2
log( (A) + TTCoff
(1- Vēhe + TT
(b) 5 (1 7)3/2
Ebe +
+
Estat
(1 7)
(1 11 72
(1 33/2
52VT
2
91
(1 -1-78 7)2 Vlog(A)T
C2 nff,
(1 7)3/2
(1 (1-7)* 7)2
60
100
< (1 (1-7)2 Vlog( [A]T + (1-
Con
where the second-last line uses the fact that Ebe S 1/T, and the last line holds since 1/(1 7)) 2 1 and log(A) A) 2 1.
Plugging the above bounds in (25), we get
ΣVT - V= < (1
60
log( (A)T + (1 7)2 V min Capg. Caft JT.
100
Case 2: Ebe 3/T: In this case, we set X T/2 1. Thus, from the bound in (7), we get that Estat = 64, which implies that
(a) 2
72 (1 7)2 V Cupg.
/log(A)) Mog(A)]++
7)2
Plugging the above bounds in (25), we get
Vx
(1 (1- Vlo((A)T+
2
+ (1- 7) v /Cupg.
72
C.1.5 SAMPLE COMPLEXITY BOUND
Let Ron and nof denote the total number of on-policy online sample, and offline samples, collected by Algorithm 2. In the following, we give bound on non and noft for finding e-suboptimal policy. Corollary Consider the setting of Theorem 1. Then, in order to guarantee that the returned policy स is e-suboptimal w.r.t. to the optimal policy x² (for the underlying MDP), the number of sampled offline and online samples required by HAC in Algorithm is given by:
Under approximate Bellman Complete (when Eb S 1/T)::
(log(A) + min Cainn(Cng, Caft. 3)3
log log(2
non = -oof =
c5(1 74
Without Bellman Completeness (when Ehe 1/T):
Roon O (log(A) + Cnpg,
log 1og(2[F1/6))
Poff
<5(1 7)
We next provide a sample complexity bound. Let T' 2 4log(1/7) Then, the total number of online samples collected in T rounds of interaction is given by
T (2g(2)F1//))
T K2 Mon S
(27)
y1-
23

---

Published conference paper at ICLR 2024
Similarly, the total number of offline samples from is given by
7 (0g((
T K2 Moff X
(28)
(1 7)²
Let = Uniform(((*)) ) J. and suppose nt denote the optimal policy for the underlying MDP. In the following, we provide a bound total number of samples queried to ensure that स is e-suboptimal. We consider the two cases:
Under approximate Bellman Complete (when S 1/T):
E
V*
V
V=
T tm
min Cupg.re, Coff.
60
log(A)
100
(1
7)2
T
71
T
Thus, to ensure that E[v=* - V
I E, we set
200
T < - 7) (36 log A) + 100 min CCnpgrr,, offt })-
This implies total number of online samples,
(log(A) (A) + min C off })3
log (2g(
c0 - 7)4
Total number of offline samples used is the same above.
Without Bellman Completeness (when Ebe > 1/r):
B B[ya*
V*
1
Vaa
<
T
1=1
log( (A)
72
Cnpra
<
(1 7)2
T
7/2
T
Thus, to ensure that V= V 5 E, we set
log(A)
+ Cnpr.s
(1 7) ))
T= _² (1 7)
This implies total number of online samples,
log(2)FF1/4)
(log(A) + Cupg. )a)
E 74
Total number of offline samples used is the same above.
24

---

Published conference paper at ICLR 2024
D HYBRID POLICY GRADIENT WITH PARAMETERIZED POLICY CLASSES
The previous section uses the softmax policy updates, which may be difficult to handle in applications where action space is continuous. In this section, we present the analysis for HNPG (Algorithm 3) that work with any differentiably parameterized policy class, including neural network- policies. Particularly, we consider a parameterized policy class II [Tg E θ), where is the parameter, which satisfies the following assumption.
Assumption 2 (Smoothness). For any parameter 8, state and action a, the function In To is 3-smooth with respect to 0, i.e., Vinno((als) - V In Tg S 0|10 8' 122
This smoothness assumption is commonly used in the analysis of NPG style algorithms (Kakade, 2001; Agarwal et al., 2021). Note that vanilla on-policy NPG can be understood critic algorithm with compatible function approximation. .More formally, on-policy NPG can be understood as first fitting critic with linear function w TV In (a(ss) i.e. computing v
actor-
argmin E, (u,aa((--ddre) (w V In (=(a)s) (s a))² followed up a parameter update 0' 0 + 176. Our hybrid approach is inspired by this actor-critic interpretation of NPG. As shown in Algorithm 3, every iteration, given f which is leamed via HPE to approximate QTat, we fit the linear critic (w") V In Tp. (als) under both offline and online data from v and a respectively. After computing w², we simply update 6 = 0f + nw'.
We now illustrate that a similar best-of-both-- worlds type of performance guarantee can also be achieved for learning with parameterized policies. We first introduce an assumption which is basically saying that the linear critic (w") V In (a)s) can approximate f(, a) Ea f a) which
itself is used for approximating the advantage A" (s, a) (recall f is used to approximate Q*).
Assumption 3 (Realizability of w). We assume realizability of the implicit value function in the set W = (w E Rd ||w|| S W), i.e. for every π E II and f E F. there exists a w E W such that sup |w Vo (a) s) - f(s, a) (s, = O. 8,8
We can relax the above assumption to only hold approximately, but we skip this extension for the sake of conciseness. The next assumption is on the parameterized policy. Assumption 4 (Well-parameterizeed policy class). For any E II, we have Eawno Ve In (als)] = 0 for any E S.
This assumption is quite standard and holds for most of the parameterization. For instance, long as ne (a 8) x (s, a) for some parameterized function fs. this condition will hold. Special cases include Gaussian policy (-(ss) N' (Ho(s), I²)), and flow-based policy parameterization where a = fs E) and ~ NO, I). Note that Gaussian policy and flow-based policy are commonly used policy parameterizations in practice (examples include TRPO Schulman al. (2015), PPO Schulman et al. (2017), SAC Haarnoja et al. (2018), etc.).
Finally, for the sake of simplicity, our bounds in this section depend on the concentrability coefficient, which we define below.
Definition 4 (Concentrability coefficient). Given the offline distribution v, for any policy n², we define the concentrability coefficient as
Cofl.T= == sup d= (8,a)
v(s. a)
s.0.
Clearly, bounded concentrability coefficient implies bounded Bellman error transfer coefficient (Definition 3). but the converse does not hold, Our main result in this section the following bound for HNPG algorithm (given in Algorithm 3) that holds for parameterized policy classes.
Theorem 2 (Cumulative suboptimality). Fix any 8 E (0, 1), and let be an offline data distribution. and hold for the function class F, policy class II and the critic class W. Additionally, suppose that the subroutime HPE is run with parameters K₃ = 4[Dog(1 (17)]/
Suppose Assumption
2o max (1) Then, with probability at least HNPG satisfies the following bounds on cumulative subpotimality w.r.t. any comparator policy n":
K₂ = K1 + T. and mott = Mon =
(1-7)²
25

---

Published conference paper at ICLR 2024
Under approximate Bellman Complete (when bbe S 1/r);
T
V 50 ( 1 /W2
log (A)T (1
(1-7)2 V min (Cupg, Coft. }
T -T)
Without Bellman Completeness (when Eb > 1/T):
T
V V S 50
Σ
BW2 log( + (1 (1- VCngg.r.T
where Tee denotes the policy at round
Thus, HNPG exhibits a sitt--ff-besttwotfe behavior in the sense that it can operate with/without approximate Bellman Completeness, and in both cases enjoys a meaningful cumulative sub-optimality bound.
D.1 UPDATE RULE
We first recall the update rule. In Algorithm 3, we run Algorithm get an estimate f corresponding to the value function for x². With fitted f", we then estimate linear critic to approximate the advantage on both the offline and online data. In particular, we fit w' on top of the feature of (s. a) = V log (a(a)))lo=e) such that
w' = argmin B(n.a)Dar (w To - (s) + E. (o a'))
+ (a
[w To - (s, + Ene (slf
(29)
Once we have compute w', our policy update procedure defined as follows:
gi-1 = 0¹ + mpu
We next provide a generalization bound for the above. Let
['(w) Ep.. Tw (', a) + E Eo'nny (on",,))
+ ADD...
(w (w (w)sas) (f(s,a)-f(ssa)) En (f
and its population counterpart
L' (w)= E( (w (s) + tn
+ AR ( (w [' a) + Ba'na (0) (" a "
where ds(s. a) = Vlog {o(ass))o=0 Next, without any loss of generality, assume that ww" (= a)l < 1/1-7 for all and s, (This condition can be easily relaxed since ||l||| I W.
and for any 2 1, Assumption implies that ||V log na [a (a]s)]e===|| < ||V log mo (a (0)
ET=2100 - 0| < V log (e(a)s))o=ol + ntW). Thus, an application of Lemma 4 implies that the least squares solution w satisties
256(1 (56(1+A) A) log(2)W/1/8) I inf ['(w) 256(1 A) log (2
('(w") I inf L'(w)
(1 71- min(man Moff)
(1 7) min ( Mon- Moff
(30)
where the second line follows from straightforward covering argument of the set W = fw E RRd ||l||| < W} at scale J/T. Using Assumption in the above bound, we get that
L L'(w') < Aw:
which implies that
Egaav (s) (s, a) + E. - (o)) $ SAn.
(31)
26

---

Published conference paper at ICLR 2024
and
A E saadddo (( - (s, a) + Ba (s) a'I))
(32)
A
Next, in order to simply the notation in the following proof, we increase the value of Estat to
1 1+
In(2 (xx
1
1+1 X
Estat = 256
I 256
(33)
(1 7)-
min Moff }
2T
which ensures that Aw S Estat-
D.2 PROOF OF THEOREM 2
D.2.1 SUPPORTING TECHNICAL RESULTS
Fix any S T, and let mae be the policy round and S be the corresponding value function that is computed using Algorithm at round t. We note that an application of Lemma implies that
12
12
sa on (8, QT (8. (s.a))²}
(1 - 7)
min
A
Ebe
+
A(1 7)
Aun
(34)
and that,
40
AEbe
E Eg ((f Tfot f' (1 7)
ff a)),
1-7 + Estat
Dofl.
(35)
Furthermore, from (31) and (32) recall that
Ex Exaavo ((w')) (s(ssa) ((w')To'ss,
f'(s, + E (s) s A..
(36)
and that
E Bo ((wo)) (((o))T((ss,)))) - f'(s, a) + Burnn (s) (D))
A
(37)
and that Aw S Estat Additionally, define the function g2 such that for all s, a:
g'(ss a) Ex' (>) a')] + (w²) (s, (
(38)
Before we move to the bound on total suboptimality, we first prove two technical results for g that will be useful for the rest of the analysis.
First, note that l1gl To 12,
Egave (g'(s, r(s)) Be
(1) Ex,onv (Bo'N (w") - - E -erp---eeeeeeoooooeeeeeee
(18)
E. 1 2E, s (lw') (s(s,a) - (a (o
+ 2
aa (f) - rs, - By B. (+9))))))))))))))))
< .. + 2 o 1113
(18t)
- 2A, + 2Doff
where (i) uses the fact that Ear (er) (e)) (8' 16',,.. a²)] for all s' E S the second term. The inequality (ii) holds from splitting the squares. Finally, (Mi) follows from (35). Thus,
l - Tf gf 112,. S 2A + 24
(39)
Next, note that since E. (0' = - for any 8, we have E (1 a)]
=
(awn (s, a)] Thus,
Beg (so, ao) T0 (so, [o)]
E Eg [f oo) Q (sp,ao))
< | T 11,10
27

---

Published conference paper at ICLR 2024
S 11
12,10
S
11f
oon
(40)
1-7'
where the third last line is from Jensen's inequality, the second last line is from Lemma 2 and the last line is due to (34).
Lemma Consider the update rule Algorithm 3, and let the function g defined such that g'(s, a) Ea (9) (8), + (wo)T (s, a). Then, setting rj = v BW2T we get that
(ogg(A
Be [0' - E (s)l a)]] S 12332log(A1)
Proof of Lemma 7. For policy optimization part, will start by leveraging the smoothness of the log of the policy. For any 8, a, f-smmoohhnes implies that
Tgc (a|s) log
3 | 00
Va a log noe (als) (0C+1 - -0)
a (a|s)
V log Tor (a|s) w² 173 1100
(41)
Taking expectation on both the sides w.r.t. a n (s), we have that:
(s))((s (s)) - (s)
Ex-x [oog(T loog( (als) log ne. (als))]
Blart (s) Vo Tor To. (als) w'| 2
|w 11
2
7
2 Blant (s) V log Tor (als) w'|
W
2
12 W - Vo log oor (als) w"] Ba (s) Vo log mor (als) w²)]
2
where the second line above follows from (41), and the last line follows from the fact that ( VV log To. (a|s)] for any s. Rearranging the terms, and taking expectation w.r.t.
d=t we get that: Eg (s) V log ne (als) w²)- [Fan Ve log ne (als) w''l
[| (s)) KL (s)] (s)) + n W². Bandre [KL (5)
"
Next, recall that definition g'(s, a) Va log Tai (als). Using this in the above, get that
(s) (wt) T (s. where (s
Exnder [Ea- (s, a)] - (o [s)
E. Ea [KL(TT [[or (s)) [ + n8
W2
2
Summing the above for t from to T, we get that:
T
E Ex-de (o) B (s,
(s)) - (L(T (s)))( + n7
E Banden
22T
2
(s)) n/ 2
$ E Exwdrr
28

---

Published conference paper at ICLR 2024
Using the fact that Tga (s) Uniform(A) (A), we get that
KL( (s) (s)) I (a) (s)l-log(TT) (s)) = (A),
which implies that
o (8) 96 Fo: (s))] log(A)
+ n
endd [g (8,
W
7 2
Setting 17 = / log( @W2T
concludes the proof.
D.2.2 HYBRID ANALYSIS UNDER APPROXIMATE BELLMAN COMPLETENESS
For any L S [T], invoking Lemma 3 with π = Tge and f = g", we get that
V= V < E Eeg, [9' (su, ao) - Q (su. ao)]
+ Eg [T g' (s, 96 [s)
I- E, anatoo (8, - gs mg (s))).
Using Jensen's 's inequality and Definition 4, we get that
V= - V < Ess, [g' ("(ss, au) - T (Su. an)
1 Coff. 1f g' a) 9 as,
1 E, aadd (g'(s, g'((s, (s))
Adding the above bounds for from T, we get
Σ V
Σ
Egg sp ag woo [g' an) TTo (so; on)]
Coft.ee T| go - (s
Σ
E Brand (g'( a) - gs(s,, no (s))]
1
We bound each of the terms on the RHS above separately below:
Term 1: Using (40), we get that
T
Aon (1-7))
B
eq ao (g' ao) Q (so. (so.ao)] ST
[=1
Term 2: Using (39), we get that
Con - - T= S 2CoHt. / + +Aw.
Term 3: Using Lemma 7, we get that
T
(s))] s Σ E.a-dr (s,(s, (x
228W2log(A))
Combining the above bounds, we get that
Aon 20olI T TV Aut Aw + 1- / 2/W2 log( (42)
1
V Vo STy (1 x1 1-2
D.2.3 NATURAL POLICY GRADIENT ANALYSIS
The following bound follows by repeating similar analysis in Appendix C.I.3. Fix any [T]. let Tp. and f be the corresponding policies and value functions at round t. Further, recall that
go (8, E Eg'en (ol' as)) (w') o (s, and define (s gs(s,a) g¹ (s, mo (s)).
29

---

Published conference paper at ICLR 2024
Using Lemma 1, we get that
Bo-wol [V* (s) V at (s)]
B aa [A [8)
7
1
1
<
B ar Ig' (s, +
E Be ((g a) A (s, a)))
1 1-y
B, ar
lg (8,a))
+
Capg.r Baandrs (80 - AFO (8, a)}²},
(43)
where the second-last line above follows from Jensen's 's inequality, and the last line is by invoking Definition We next bound the second term in the right hand side. Using the fact that ne age, we
get that
Bs ((g' (x, a) A 2)
Rand
Ko a) - g (8, mo (s)) Q= (s, + (s)
B saad ae ((g'(s Q= (s, 2( (T( - g'(s, Tet (8))) (s, QT* + 2( ( ( lg (s, QT (s. a d))
E Ba
<4B add""" ((g a) (***(s
where the first inequality uses (a + b)2 < 2a² + 21² for any a, b, and the second inequality follows from Jensen's 's inequality. Adding and subtracting (x) (s, a'))) inside the expectation, further decomposing the above, and again applying Jensen's inequality, we get that
E Bs (('' a) at (s, =] I SE so ((g' (s, a)
Eg (s)
+ SE aa (( a) - Q (s, a))
Aw + Don:
where the last line uses the bound from (37) and Lemma 5. Plugging the above in (43), we get that
1
4
Capg.r= A w
Egsup V (s) o (s)] S 1-7 Ba (s, a)]
Capg, : Don-
(1-7)
(1 (1-))
Summing the above expression for all E [T] implies that
4T
Capg Aw
4T
V=- Vaaa <
E Ea (g'( a))
(1 (1-7){
X
+ (1-7)
Copg. Bon
Using the bound for the first term from Lemma in the above, we get that
4T
4T
v - aa < 1 1-7 /28w2 log( (A)T + (1-))
+ (1 (1-7)
VCnpg. Don.
A
(44)
D.2.4 FINAL BOUND ON CUMULATIVE SUBOPTIMALITY
Combining the bounds from (42) and (44), we get that
1
2T
Capg. Au
47'
V= V < min
43W2 log( A)T +
Vnpa, Aon.
(1-7)
(a)
Aon
+ 2Cott,reTT V /
T
+
An
v 2//22
(A)T
()
1-
1
(b)
(45)
30

---

Published conference paper at ICLR 2024
where recall that
12
minf 1
+ 12Estat
A
1 [be)
(1-7)²
X(1 ?)
40
( AEbe + Estat
off
(1 7)- 1 --
A Estat:
2T' 2T
Moff
= Mon
(1 -7)
1+
max FF (WI1/6)
1 +
Estat I 256
S 256
(1 - (1
min Mon: Moff }
27
due to Lemma 5, and (33) and (30). Plugging in the bounds Don and Don in (45), get that
(a) v 1 v 23W2 loy(
16T
en Estat
167
71-7
A
(1 (1-
Cupg. min
x
Ebe
and,
4T
X Ebe }
1
4T
Estat
14T /debe
(b) v (1 7/322
min
+
(1->) +
(1 7)2
14T'Coff,
Vestat
v 2BW2 log (A)T.
73/2
Note that À is free parameter the above, which is chosen by the algorithm. We provide an upper bound on the cumulative suboptimality under two separate cases (we set different value of X, and get a different bound on Estat in the two cases):
Case I: Under approximate Bellman Complete (when bbe S 1/T): In this case, we set À = 1. Thus, from the bound in (7), we get that Estat S 256/T, which implies that
16T
16T
(a) S 23W2 log( (A)T
CCpg, Estat +
(1 7)2 V Cnpp,
(1 3/3/2
300
S 1-7 233 (A)T
(1 71- VC
where the last line follows from the fact that Ebe I 1/T. Additionally, we also have that
350
1
(b) (1 7)2
C2 Aut.nTTT T 1-7
2/2 log(A)T,
where the last line uses the fact that bb I 1/T, and that Cofl.. 2 Plugging the above bounds in (25), we get
350
Σ V - V
/ 23W2 log( (A)T 1-7
min Capg.rs,
Caiisrr,,ottte CaRt T.
(1 7)2
Case 2: Without Bellman Completeness (when She 1/T) In this case, we set À T - Thus, from the bound in (7), we get that Extat 128, which implies that
56
(a)
<
332 (og( + (1 y)- v C.
Plugging the above bounds in (25), we get
Σ Vo - V23W3 log(A)T
56
(1 (1-7)2 V Cnng.re
D.2.5 SAMPLE COMPLEXITY BOUND
Corollary 2 (Sample complexity). Consider the setting of Theorem 2. Then, in order to guarantee that the returned policy â is E-suboptimal w.r.t to the optimal policy x² (for the underlying MDP), the number of sampled offline and online samples required by HNPG in Algorithmm 3 is given by:
31

---

Published conference paper at ICLR 2024
Under approximate Bellman Complete (when Ebe 1/r)):
Hon 1ooff o (BW3log(A) + min (Cope Cot 1/(1-)))))))) mog(2))x((W//T))
60 7)8
Without Bellman Completeness (when Ebe > 1/T):
Ton Rofff = (BW2 log(A) 21pp,=*/11100))) log(2 (WxT(
(1-1)8
In particular, HNPG draws the same number of offline samples, and on-policy online samples.
We next provide a sample complexity bound. Let 7 4 1og(1/7) Then, the total number of online samples collected in I rounds of interaction is given by
Tst (log(2 max max (W/T),,
T K2 Mon
(46)
(1 71-
Similarly, the total number of offline samples from is given by
T (log(2 max ( (FI/0))
T K2 Moff
(47)
71-
Let Uniform )T= J. and suppose n* denote the optimal policy for the underlying MDP. In the following, provide a bound total number of samples queried to ensure that म is e-suboptimal. We consider the two cases:
Case 1: Under approximate Bellman Complete (when Ebe S 1/T))
T
E Vm
-
V&
<
V
T
A=1
(1 7)2 ming HainfCnpesss Capg, Offt,
350
v 2,3W2 2 log( (A)T
7
Thus, to ensure that E[V=* - V S E, we
1
3 log
71 min Cupg,as Co Cart 1)).
T T= 22
(1 - (1-
This implies a total number of online samples,
(2 m (W/T)4, (F1)/0)
(oW"log(A (1- min Connn O2 oorr.x))
e²(1 - 7)
Total number of offline samples used is the same above.
Case 2: Without Bellman Completeness (when Ebe >> 1/T):
T
E ElvT*
E
V - V
3W2 log(A) (A)
Cppg.
(1 7] V
1
T
T
Thus, to ensure that V V$] S E, we set
T= 3W2 lA)
Caps.x*
(1 7)
(1 7)
This implies total number of online samples, log(2 max
[@W2log(A) log(A) +
(1 (1-22) Capa.
60 7)
32

---

Published conference paper at ICLR 2024
Total number of offline samples used is same as above.
33

---

Published conference paper at ICLR 2024
Train
Orttic
Offine
1.0
2.8
0.2
0.4
0.-
0.4
42- 0.2
02
6.
Figure 3: Comparison of the moving average learning and loss curves between HNPG and RLPD on an image-based Comblock with horizon 5. For train/test reward curves, median over 5 random seeds reported and 20/80th quantile shaded. For loss curves, one random run is chosen and reported. Online critic loss for HNPG refers to online MC regression square loss and offline critic loss for HNPG refers to offline TD loss. Both online and offline critic losses for RLPD are TD losses.
Train Set Reward
Online Critic Loss
Offi inc Critic Loss
0.8
0.8
0.8
0.4
0.4
0.4
0.2
0.0
0.0
60x
120k
280k
240k
300c
120k
180k
200c
300L
50k
120k
100k
2004
300k
Number Online Samples
Number of Online Samples
Number of Online Samples
RLPD
HNPG
Figure 4: Comparison of the loss curves between HNPG and RLPD on continuous Comblock with
horizon 15.
E
EXPERIMENT DETAILS OF COMBLOCK
E.I DETAILS OF COMBINATION LOCK
In Comblock environment, each timestep has three latent states with the first two being good states and the last being absorbing state. Each latent state has 10 underlying actions. In good states, only one underlying action will lead to one of two good states of the next timestep with equal probability while the of the underlying actions will lead the absorbing state of the next timestep. Once the agent gets to an absorbing state, any underlying action will lead to the absorbing state of the next timestep. Once the agent reaches one of the good states the last timestep, will receive an optimal reward of 1. When the agent goes from a good state to an absorbing state, it also has 0.5 probability of receiving an anti-shaped reward 0.1. Rewards for any other transitions are To get the observation for each latent state, we concatenate one-hot representations of the latent state and horizon, add random noise (0, 0.1) to each dimension, and finally multiply it with a Hadmard matrix.
E.2 Loss CURVES FOR COMBLOCK EXPERIMENTS
In Figure 4, we present the loss curve comparison for HNPG and RLPD on a continuous Comblock with horizon 5, Although RLPD enjoys smaller sample complexity compared HNPG, its learning curve is less stable. Similar to Figure 3, the online critic loss is more bumpy for RLPD since it optimizes TD loss and its bellman bootstrapping can be unstable.
E.3 IMPLEMENTATION PSEUDOCODE
Following prior combination lock algorithms (Song et al., 2023; Zhang et al., 2022b), instead of a discounted setting policy evaluation, we adapt to the finite horizon setting and train separate Q- functions and policies for each timestep. We also incorporated some empirical recommendations from (Schulman et al., 2015) and the resulting practical algorithm is presented in Algorithm 4 and Algorithm 5.
34

---

Published conference paper at ICLR 2024
Algorithm 4 Practical Finite-Horizon HNPG
Require: Function class
{Fr PG iteration T, offline data Params X, KL constraint maxxı. E and ...... ;
1: Initialize -o...., J
2: for [ 1,... T,, do
3: fo.... f6.
JH-1 E F, Dof, Don + FHPP (H : T ) A).
4: for h = O.......................... H -1-10 do
5: Let (s. V log Tog (als) and [s a) ()) Bannoy (0) (1)))()s)))
6: Use Conjugate Gradient to solve:
w/ E argmin Epg, I(w of ((l,,)))(((s.a))))) ΛEps 1( (wTTh () (+,a))))
(48)
7: Get rf' = argiaxx, (Is(1, maxxl) according to (50) using line search.
8: Update 0/+11 0% n n/
9:
end for
end for
11:
Return policy ......... T
Algorithm 5 Finite-Horizon Hybrid Fitted Policy Evaluation (FHPE)
Require: Policy To..... -1, function class {Fi) offline distribution weight X
1: Initialize fo..... fH-1 E FH = O.
2: Sample Don = [((8), 04 = Q7 -)) of Mon many on-policy samples using
....... -H-1-
Sample Doff {[(s;, Ce s/ 3)) H-1 of mof many offline samples from v.
4: for h = H - 1...... 0 do
5: Solve the square loss regression problem to compute:
fn + argmin Eps, (f(s, a) - - fn+ils', Th+1(s)))) + ΛEDa (f(s,a) y)² (49)
fEF
6: end for
7:
Return fo...., fH-1, and optionally Doft and D
In Algorithm 4, we define the line search objective ft (11 maXKL), which take the following form:
(n, maxkı.) Log (6% + mww)) - X' (KL, 6% + +ww)) S maxkı.).
(50)
where L(-) is the policy gradient objective. and x } = 0 if the statement is true and co otherwise. In practice, this objective is solved using line search. For more details we refer the reader to the original paper (Schulman et al., 2015).
E.4 HYPERPARAMETERS
We provide the hyperparameters of HNPG for both continuous Comblock and image-based continu- Comblock in Table 1. In addition, we provide the hyperparameters tried for RLPD baseline for both Comblock settings in Table 2.
Table 1: Hyperparameters for HNPG in (image-based) continuous Comblock
Value Considered
Final Value
GAE L-2 regularization rate
(0.97, 0.9)
0.97
[0, 1e-3, 1e-2]
0
Maximum KL difference
[le-1, le-2, le-3)
le-2
Damping
(1e-1]
le-1
Optimizer
(Adam, SGD)
Adam
Batch size
(500, 1000)
1000
Reweighting factor
(0.1, 1, 10)
35

---

Published conference paper at ICLR 2024
Table 2: Hyperparameters for RLPD in (image-based) continuous Comblock
Value Considered
Final Value
Discount 7
(0.99)
0.99
Actor minimum standard deviation
(-10)
-10
Actor maximum standard deviation
(2)
2
Initial temperature
(0.1)
0.1
Alpha Beta
(0.5}
0.5
Alpha Learning Rate
(le-4)
le-4
Actor learning rate
(le-2, 1e-3)
1e-3
Critic learning rate
(1e-2, 1e-3)
1e-3
Critic soft update
0000,,0022,, 0.1)
0.01
Critic soft update frequency Optimizer
[1.2]
2
[Adam]
Adam
Number of updates per sample Batch size
[0]
1
[64, 128)
128
Buffer size
(le5, le6)
le6
36


Reviews:
[{"review_id": "GWLFVWkjds", "reviewer": "Reviewer_M4D3", "summary": "This paper focuses on hybrid RL, where the agent has offline data and is able to interact with the environment simultaneously. The novel algorithms introduced in this paper integrate the TD error from offline data and the estimation error coming from online datasets into the policy evaluation loss. These approaches distinguish itself from the prior works that directly merge offline and online data, followed by applying an off-policy method. The theoretical result shows that the optimality gap of the proposed method can be upper bounded without Bellman Completeness or with Bellman Completeness and offline data coverage guarantee. The experiments are conducted in a continuous Comblock environment, which necessitates accurate multi-step actions to attain the final optimal reward. The results reveal that this method outperforms TRPO, a purely on-policy method, as well as RLPD, a hybrid off-policy actor-critic method.", "questions": "Some detailed questions:\n- The concept and the terminology of “NPG coverage” in Definition 2 could be further elaborated on. Specifically, Definition 2 is defined w.r.t. some comparator policy, which is not necessarily related to NPG.\n- To calculate the loss in Eq. (1), one would need to obtain an unbiased estimate $y$, which could be obtained via Monte Carlo sampling. On the other hand, it would probably be better to get $y$ with the help of bootstrapping. Would this still preserve a similar sub-optimality guarantee as in Theorem 1?\n- Regarding Definition 2, how to ensure a finite $C_npg$ without the assumption on the positivity of the reset distribution?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The proposed algorithms in the hybrid RL setting are interesting and novel.\n- The theoretical guarantee established for the two distinct cases of Bellman Completeness offers significant insights. To my knowledge, this paper is the first that provides an algorithm with best-of-both-worlds type guarantees for hybrid RL (so that the assumption about Bellman Completeness can be relaxed).\n- The proposed algorithms empirically outperform other hybrid RL baseline like RLPD in hard exploration problems (continuous and image-based Comblock).\n- The paper is very well-written and easy to follow.", "weaknesses": "I did not spot any particular major weakness in this paper. That said, there are a few places that could be further improved:\n- In Algorithm 3, HNPG solves the squared loss regression with a linear critic. The requirement of a linear critic is probably mainly for theoretical analysis and could be relaxed to more general function classes (e.g., neural function approximation). A further discussion (possibly with some experiments) could make the proposed algorithm more impactful. \n- Regarding Definition 3, it is a bit difficult to get a sense of how large the transfer coefficient could be (as it is the maximum taken over all stationary policies and the whole function class) and under what condition of $\\nu$ would $C_{off}$ be bounded or small.\n- As the proposed HNPG focuses on the hybrid RL problems, readers would probably expect at least a bit of experimental comparison on those more mainstream RL benchmarks like D4RL (as done in several recent hybrid RL papers, e.g., RLPD and Cal-QL) or hard exploration problems in Atari, e.g., Montezuma's Revenge as in (Song et al., 2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CjHAcYlh9y", "reviewer": "Reviewer_HGgg", "summary": "This paper proposes a new hybrid reinforcement learning (RL) algorithm called Hybrid Actor-Critic (HAC) that combines on-policy and off-policy learning. The proposed algorithm uses compatible function approximation and a hybrid loss using both online and offline data to achieve better theoretical guarantees. The authors present a theoretical analysis to show that it has both offline and on-policy performance guarantees with a small Bellman error and still has the on-policy performance gurantee when the Bellman error is large. In practice, the algorithm is tested on rich-observation and exploration-challenging environments and is shown to outperform hybrid RL baselines like RLPD.", "questions": "1. What is the technical challenge in combining natural actor critic and hybrid RL?\n\n2. When the offline guarantee does not hold, how can we still retain the on-policy guarantee?\n\n3. Can you provide more insights on the superior performance of the proposed method on the comblock environment?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Theoretical analysis: The paper provides a thorough theoretical analysis of the proposed algorithm, demonstrating that it achieves nice theoretical guarantees when offline RL-specific assumptions hold, while maintaining the guarantees of on-policy natural policy gradient (NPG) regardless of the validity of the offline RL assumptions.\n2. Empirical results: The authors demonstrate the effectiveness of their approach on challenging rich-observation environments, outperforming state-of-the-art hybrid RL baselines. This showcases the practical benefits of combining on-policy and off-policy learning.", "weaknesses": "1. The novelty of the proposed method is limited. The algorithm is a combination of natural actor-critic and hybrid-RL [1], and it needs to be clarified what is the technical challenge in combining them.\n\n2. I am also concerned with the claim that the proposed method achieves the best of both worlds. While it is nice to have guarantees without the Bellman completeness assumption, other strong assumptions are still required. The realizability for any $Q^\\pi$ is a strong assumption, and the value-based method usually only requires the realizability of $Q^*$. More importantly, the assumption on NPG coverage is also strong since it is an all-policy coverage assumption. Offline RL only needs single-policy coverage assumption as in Definition 3, and it can be proved that $C_{off,\\pi^e}^2 \\leq C_{npg,\\pi^e}$ [1,2]. This invalidates the claim that the proposed method achieves the best of both worlds since when the offline assumption does not hold, the online guarantee is lost, too. I expect an exploration mechanism so that we can still achieve low regret when the offline data has insufficient coverage.\n\n[1] Song, Yuda, et al. \"Hybrid rl: Using both offline and online data can make rl efficient.\" arXiv preprint arXiv:2210.06718 (2022).\n\n[2] Xie, Tengyang, et al. \"Bellman-consistent pessimism for offline reinforcement learning.\" Advances in neural information processing systems 34 (2021): 6683-6694.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iD4R3KnBC2", "reviewer": "Reviewer_mti6", "summary": "This paper proposed a hybrid RL method based on NPG that uses both on-policy data and offline data. The algorithm enjoys theoretical guarantees for the best of both the offline RL setting and on-policy RL setting. Empirical performance also shows that the proposed hybrid RL algorithm outperforms the existing algorithms in challenging scenarios.", "questions": "See above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Clarify: the paper is well written. The motivation is justified clearly. The algorithm design and theoretical guarantees are also explained clearly. \n\nSignificance and quality: the results are quite significant since it is able to achieve the best of the both world theoretical guarantees, with empirical performance improvements in challenging scenarios too.", "weaknesses": "I don't see major weaknesses. Just one question about Figure 2: it is hard to differentiate the curves generated by different approaches, thus difficult to see the message from this figure. I suggest the authors improve the presentation of Figure 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bLwQF0aiix", "reviewer": "Reviewer_CW8P", "summary": "The paper studied the hybrid RL setting where the agent has access to both online and offline dataset. A natural policy gradient based algorithm is proposed with provable guarantee on the sample complexity. The sample complexity bound showed that the approach, in theory, can achieve the best of both worlds. The paper further provides simulation studies on combinatory lock environment, where the proposed algorithm showed advantage over baseline methods.", "questions": "The authors proposed a parameterized policy class. What is a sufficient condition on the policy class to ensure the same sample complexity bound in Theorem 1?\n\nAs indicated by the Theorem 1, the algorithm should benefits more from the offline dataset when Bellman completeness is not satisfied. Has this been observed in the simulation studies? It seems that the HNPG always has the dominate performance regardless of the Bellman completeness? Do the authors have any comments on this point? I believe this is critical regarding how the theoretical results help us understand the real-world performance.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The hybrid RL setting has a quickly growing literature and this paper by considering a natural policy gradient algorithm is a significant contribution to the literature. The algorithm has sound theoretical guarantee.", "weaknesses": "In general, the discussions on the theoretical results have to be more comprehensive and more coherent. \n \nThe paper mentioned in the abstract that the sample complexity bound is best-of-both-worlds. However, I did not see any discussion on the existing bound for pure online and pure offline bound. Many results in the offline literature, when a pessimism algorithm is applied, has a sample-complexity bound depending on the single-policy concentrability instead of the all-policy. it is clearly not the best in the world of pure-offline learning.\n\nThe NPG coverage condition and the Bellman error transfer coefficient do not seem to match. Could NPG coverage condition be weakened such that it reflects the dependence on the value function class? In the current form, if $\\nu$ is generated by some policy on the environment, then $C_{off, \\pi^e} \\leq C_{jpg, \\pi^e}$. \n\nCould the authors comment on the technical contribution? By quickly going through the appendix, I don't see significant technical contributions except following the analysis in Song et al. (2022) and the previous natural policy gradient literature.\n\nOne can image that the algorithm performance should heavily depend on the coverability of the offline dataset. I suggest the authors test the effects of offline distribution $\\nu$. Does the a better coverage provide better performance?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)