Hybrid RL: Using both offline and online data can make RL efficient
Authors: Yuda Song
Yifei Zhou
Ayush Sekhari
Drew Bagnell
Akshay Krishnamurthy
Wen Sun
Venue: ICLR 2023 poster (2023)
Keywords: reinforcement learning theory
hybrid reinforcement learning
online reinforcement learning
offline reinforcement learning

Abstract: We consider a hybrid reinforcement learning setting (Hybrid RL), in which an agent has access to an offline dataset and the ability to collect experience via real-world online interaction. The framework mitigates the challenges that arise in both pure offline and online RL settings, allowing for the design of simple and highly effective algorithms, in both theory and practice. We demonstrate these advantages by adapting the classical Q learning/iteration algorithm to the hybrid setting, which we call Hybrid Q-Learning or Hy-Q. In our theoretical results, we prove that the algorithm is both computationally and statistically efficient whenever the offline dataset supports a high-quality policy and the environment has bounded bilinear rank. Notably, we require no assumptions on the coverage provided by the initial distribution, in contrast with guarantees for policy gradient/iteration methods. In our experimental results, we show that Hy-Q with neural network function approximation outperforms state-of-the-art online, offline, and hybrid RL baselines on challenging benchmarks, including Montezuma’s Revenge.

Published as a conference paper at ICLR 2023
HYBRID RL: USING BOTH OFFLINE AND ONLINE DATA CAN MAKE RL EFFICIENT
Yuda Song' Carnegie Mellon University
Yifei Zhou"
Ayush Sekhari MIT
Cornell University
J. Andrew Bagnell Carnegie Mellon University
Akshay Krishnamurthy
Wen Sun Cornell University
Microsoft Research
ABSTRACT
We consider a hybrid reinforcement learning setting (Hybrid RL), in which an agent has access to offline dataset and the ability to collect experience via real-world online interaction. The framework mitigates the challenges that arise in both pure offline and online RL settings, allowing for the design of simple and highly effective algorithms, in both theory and practice. We demonstrate these advantages by adapting the classical leamiing/teration algorithm the hybrid setting, which we call Hybrid Q-Learning or Hy-Q. In our theoretical results, we prove that the algorithm is both computationally and statistically efficient whenever the offline dataset supports high-quality policy and the environment has bounded bilinear rank. Notably, we require no assumptions on the coverage provided by the initial distribution, in contrast with guarantees for policy gradien//iteratoo methods. In our experimental results, we show that Hy-Q with neural network function approximation outperforms state-of-the-art online, offline, and hybrid RL baselines on challenging benchmarks, including Montezuma's 's Revenge.
INTRODUCTION
Learning by interacting with an environment, in the standard online reinforcement learning (RL) protocol, has led to impressive results across number of domains. State-of-the- art RL algorithms are quite general, employing function approximation to scale to complex environments with minimal domain expertise and inductive bias. However, online RL agents are also notoriously sample inefficient, often requiring billions of environment interactions to achieve suitable performance. This issue particularly salient when the environment requires sophisticated exploration and a high quality reset distribution is unavailable to help overcome the exploration challenge. As consequence, the practical success of online RL and related policy gradient/mmproeemen methods has been largely restricted to settings where high quality simulator is available.
To overcome the issue of sample inefficiency, attention has turned to the offline RL setting (Levine et al., 2020), where, rather than interacting with the environment, the agent trains on large dataset of experience collected in some other manner (e.g.. by a system running in production or an expert). While these methods still require a large dataset, they mitigate the sample complexity concerns of online RL, since the dataset can be collected without compromising system performance. However, offline RL methods can suffer from distribution shift, where the state distribution induced by the learned policy differs significantly from the offline distribution (Wang et al., 2021). Existing prov- able approaches for addressing distribution shift are computationally intractable, while empirical approaches rely on heuristics that can be sensitive to the domain and offline dataset (as we will see).
In this paper, focus a hybrid reinforcement learning setting, which call Hybrid RL, that draws on the favorable properties of both offline and online settings. In Hybrid RI., the agent has both an offline dataset and the ability interact with the environment, as in the traditional online RL setting. The offline dataset helps address the exploration challenge, allowing us to greatly reduce
"Equal contribution
Author contact info: yudas@andrew, cmu. edu, v26390cornes mel1 1dddu sekhari @mi edu, dbagnel1 @aurera. tech, akshaykr@m crosoft. com, w84 550ccoee eddu

---

Published as a conference paper at ICLR 2023
the number of interactions required. Simultancously, we can identify and correct distribution shift issues via online interaction. Variants of the setting have been studied in a number of empirical works (Rajeswaran et al., 2017; Hester et al., 2018; Nair et al., 2018; 2020; Vecerik et al., 2017) which mainly focus on using expert demonstrations as offline data. Our algorithmic development is closely related to these works, although our focus is formalizing the hybrid setring and establishing theoretical guarantees against more general offline datasets.
Hybrid RL is closely related the reset setting, where the agent can interact with the environment starting from a "nice" distribution. A number of simple and effective algorithms, including CPI (Kakade& & Langford, 2002). PSDP (Bagnell et al., 2003), and policy gradient methods (Kakade, 2001; Agarwal et al., (9200)-whiih have further inspired deep RL methods such as TRPO (Schulman et al., 2015) and PPO (Schulman al., 2017>are are provably efficient in the reset setting. Yet, nice reset distribution is strong requirement (often tantamount to having access to a detailed simulation) and unlikely to be available in real world applications. Hybrid RI. differs from the reset setting in that (a) we have offline dataset, but (b) our online interactions start from the initial distribution of the environment, which is not assumed to have any nice properties. Both features (offline data and a nice reset distribution) facilitate algorithm design by de-emphasizing the exploration challenge. However, Hybrid RL is much more practical since an offline dataset is much easier to obtain in practice.
We showcase the Hybrid RL setting with new algorithm, Hybrid Q learning Hy-Q (pronounced: Haiku). The algorithm is a simple adaptation of the classical fitted Q-iteration algorithm (FQI) and accommodates value-based function approximation.' ! For our theoretical results, we prove that Hy-Q is both statistically and computationally efficient assuming that: (1) the offline distribution covers some high quality policy, (2) the MDP has low bilinear rank, (3) the function approximator is Bellman complete, and (4) we have a least squares regression oracle. The first three assumptions are standard statistical assumptions in the RL literature while the fourth is widely used computational abstraction for supervised learning. No computationally efficient algorithms are known under these assumptions in pure offline or pure online settings, which highlights the advantages of the hybrid setting.
We also implement Hy-Q and evaluate it on two challenging RL benchmarks: rich observation combination lock (Misra et al., 2020) and Montezuma's Revenge from the Arcade Learning Environ- ment (Bellemare et al., 2013). Starting with an offline dataset that contains some transitions from high quality policy, our approach outperforms: an online RL baseline with theoretical guarantees, an online deep RL baseline tuned for Montezuma's 's Revenge, pure offline RL baselines, imitation learning baselines, and existing hybrid methods. Compared to the online methods, Hy-Q requires only small fraction of the online experience, demonstrating its sample efficiency. Compared the offline and hybrid methods, Hy-Q performs most favorably when the offline dataset also contains many interactions from low quality policies, demonstrating its robustness. These results reveal the significant benefits that can be realized by combining offline and online data.
2 RELATED WORKS
We discuss related works from four categories: pure online RL, online RL with access reset distribution, offline RI., and prior work in hybrid settings. We note that pure online RI refers to the setting where one can only reset the system to initial state distribution of the environment, which is not assumed to provide any form of coverage.
Pure online RL Beyond tabular settings, many existing statistically efficient RL algorithms are not computationally tractable, due to the difficulty of implementing optimism. This is true in the linear MDP (Jin et al., 2020) with large action spaces, the linear Bellman complete model (Zanette et al., 2020; Agarwal et al., 2019), and in the general function approximation setting (Jiang et al., 2017; Sun et al., 2019; Du et al., 2021; Jin et al., 2021a). These computational challenges have inspired results on intractability of aspects of online RL (Dann et al., 2018; Kane al., 2022).
There are several online RL algorithms that aim to tackle the computational issue via stronger structural assumptions and supervised learning-style computational oracles (Misra et al., 2020; Zhang et al., 2022c; Agarwal et al., 2020a; Uehara et al., 2021; Modi et al., 2021; Zhang et al., 2022a; Qiu et al., 2022). Compared to these oracle-based methods, our approach operates in the more general
'We use Q-learning and Q-iteration interchangeably. although they are not strictly speaking the same algorithm. Our theoretical results analyze Q-iteration, but we algorithm with online/mini-batch flavor that is closer to Q-learnin for our experiments.
2

---

Published as a conference paper at ICLR 2023
"bilinear rank" setting and relies standard supervised learning primitive: least squares regression. Notably, our oracle admits efficient implementation with linear function approximation, so we obtain an end-to-end computational guarantee; this is not true for prior oracle-basee methods.
There are many deep RL methods for the online setting (c.g., Schulman et al. (2015; 2017); Lillicrap al. (2016); Haarnoja et al. (2018); Schrittwieser et al. (2020)). Apart from few exceptions (e.g.. Burda et al. (2018); Badia et al. (2020); Guo et al. (2022)), most rely on random exploration and are not capable of strategic exploration. In our experiments, we test our approach on Montezuma's 's Revenge, and we pick RND (Burda et al., 2018) as a deep RL exploration baseline due to its effectiveness.
Online RL with reset distributions When exploratory reset distribution is available, a number of statistically and computationally efficient algorithms are known. The classic algorithms are CPI (Kakade & Langford, 2002), PSDP (Bagnell et al., 2003), Natural Policy Gradient (Kakade, 2001; Agarwal ct al., 2020b), and POLYTEX (Abbasi-Yadkori et al., 2019). Uchendu et al. (2022) recently demonstrated that algorithms like PSDP work well when equipped with modern neural network function approximators. However, these algorithms (and their analyses) heavily rely on the reset distribution to mitigate the exploration challenge, but such a reset distribution is typically unavailable in practice, unless one also has a simulator. In contrast, we assume the offline data covers some high quality policy, which helps with exploration, but we do not require an exploratory reset distribution. This makes the hybrid setting much more practically appealing.
Offline RL Offline RL methods learn policies solely from a given offline dataset, with no interaction whatsoever. When the dataset has global coverage, algorithms such as FQI (Munos & Szepesvári, 2008; Chen & Jiang, 2019) find near-optimal policies in an oracle-efficient manner, via least squares or model-fitting oracles. However, with only partial coverage, existing methods either (a) are not computationally efficient due to the difficulty of implementing pessimism both in linear settings with large action spaces (Jin et al., 2021b; Zhang et al., 2022b; Chang et al., 2021) and general function approximation settings (Uehara & Sun, 2021; Xie et al., 2021a; Jiang & Huang, 2020: Chen & Jiang, 2022; Zhan et al., 2022). or (b) require strong representation conditions such as policy-based Bellman completeness (Xie et al., 2021a; Zanette et al., 2021). In contrast, in the hybrid setting, we obtain an efficient algorithm under the more natural condition of completeness w.r.t., the Bellman optimality operator only.
-equvvlleeeeevveeeeeee model learning (Ross & Bagnell, 2012), can
Among the many empirical offline RL methods (e.g., Kumar et al. (2020); Yu et al. (2021); Kostrikov et al. (2021); Fujimoto & Gu (2021)), we use CQL (Kumar et al., 2020) as a baseline our experiments, since it has been shown to work in image-based control settings such as Atari games.
Online RL with offline datasets Ross & Bagnell (2012) developed a model-based algorithm for similar hybrid setting. In comparison, our approach is model-free and consequently more suitable for satb-dimensional state spaces (e.g., raw-pixel images). Xie et al. (2021b) studied hybrid RL and show that offline data does not yield statistical improvements in tabular MDPs. Our work instead focuses on the function approximation setting and demonstrates computational benefits of hybrid RL.
On the empirical side, several works consider combining offline expert demonstrations with online interaction (Rajeswaran et al., 2017: Hester al., 2018; Nair et al., 2018; 2020; Vecerik et al., 2017). A common challenge in offline RL is the robustness against low-quality offline dataset. Previous works mostly focus on expert demonstrations and have no rigorous guarantees for such robustness. In fact, Nair et al. (2020) showed that such degradation in performance indeed happens in practice with low-quality offline data. In our experiments, we observe that DQID (Hester et al., 2018) also wwweeeieeeemmm has similar degradation. On the other hand, our algorithm is robust to the quality of the offline data. Note that the core idea of our algorithm is similar to that of Vecerik et al. (201)), who adapt DDPG to the setting of combining RL with expert demonstrations for continuous control. Although Vecerik et al. (2017) does not provide any theoretical results, it may be possible to combine our theoretical insights with existing analyses for policy gradient methods to establish some guarantees of the algorithm from Vecerik et al. (2017) for the hybrid RL setting. We also include detailed comparison with previous empirical work in Appendix D.
3 PRELIMINARIES
We consider finite horizon Markov Decision Process M(S. ASS.A,HHRR P.dd), where S is the state space, A is the action space, H denotes the horizon, stochastic rewards R(s, a) E A(0, 1]) and a(),a) A(8) are the reward and transition distributions at (s,a), and do E A(S) is the initial
3

---

Published as a conference paper at ICLR 2023
Algorithm Hybrid Q-learning using both offline and online data (Hy-Q)
Require: Value class: F, #iterations: T, offline dataset Dj of size most T for h E [H 1].
1: Initialize f (8, a) 0.
2: for ==r
do
3: Let r' be the greedy policy w.r.t. i.e., = = argmax, (s)
4: For each h, collect mou online tuples Dj di // Online collection
// FQI using both online and offline data
5:
Set fH (s,a) 0.
ct+
6:
for h
1,..., do
7:
Estimate f++ using least squares regression on the aggregated data D/ = Dj + Σ D
I + argginn [Eyy (J(s, r- max S ( ( JEFn
(1)
a'
8: end for
9: end for
distribution. We assume the agent can only reset from do (at the beginning of each episode). Since the optimal policy is non-stationary in this setting, we define a policy æ == {mo..... HH where Th S + (AA). Given т,, dz A(S x A) denotes the state-action occupancy induced by æ at step h.
Given TT, we define the state and state-action value functions in the usual manner: (s) B "1- T IT, 8h sj and (7, a) = E TT, 84 as a]. Q* and V* denote the optimal value functions. We define the Bellman operator T such that for any f A+
Tf = E[R(s, a)] + Ex-- max f(s',(')
Vs,a,
We assume that for each h we have an offline dataset of moft samples (s, a, a,r,s') s') drawn iid via (s, a) Uh, r & R(s, a), 8' P(x, a). Here v (up,..., VH-1) denote the corresponding offline data distributions. For a dataset D, we use Epl-1] to denote a sample average over this dataset. For our theoretical results, will assume that v covers some high-quality policy.
We consider the value-based function approximation setting, where we are given a function class F = Fo x... Fir-1 with Fr, S x A + [0, Vmax] that use to approximate the value functions for the underlying MDP, For ease of notation, we define f = "oo...,,J--J 1 and define x! to be the greedy policy w.r.t., f, which chooses actions as n/ (s) = argmax, fn (s,
4 HYBRID Q-LEARNING
In this section, we present our algorithm Hybrid Q Learning Hy-Q in Algorithm 1. Hy-Q takes an offline dataset D that contains (s, a, 8') tuples and a Q function class F C A + [0, H| as inputs, and outputs policy that optimizes the given reward function. The algorithm is conceptually simple: it iteratively executes the Fitted Q Iteration procedure (line 6) using the offline dataset and on-policy samples generated by the learned policies.
Specifically, at iteration t, we have an estimate f' of the Q* function and we set π' to be the greedy policy for ft. We execute x' to collect dataset Dj, of online samples in line 4. Then run FQI, dynamic programming style algorithm on both the offline dataset D and all previously collected online samples {D The FQI update works backward from time step H to 0 and computes p++1 via least squares regression with input (s, a) and regression target max.' fit (8', (s',,')²
Let us make several remarks. Intuitively, the FQI updates in Hy-Q try to ensure that the estimate f has small Bellman error under both the offline distribution and the online distributions d= The standard offline version of FQI ensures the former, but this alone is insufficient when the offline dataset has poor coverage. Indeed FQI may have poor performance in such cases (see examples in Zhan et al., 2022: Chen & Jiang, 2022). The key insight in Hy-Q is to use online interaction to ensure that also have small Bellman error on d= As will see, the moment find an f that has small Bellman error on the offline distribution and its own greedy policy's 's distribution dt FQI
Note that FQI and Hy-Q extend the infinite horizon discounted setting (Munos Szepesvári, 2008).
4

---

Published as a conference paper at ICLR 2023
guarantees that r' will be at least as good as any policy covered by This observation results in an sxplore-or-terminate phenomenon: either f has small Bellman error on its distribution and we are done, or d' must be significantly different from distributions we have seen previously and we make progress. Crucially, no explicit exploration is required for this argument, which is precisely how we avoid the computational difficulties with implementing optimism.
Another important point pertains catastrophic forgetring. We will see that the size of the offline dataset moft should be comparable to the total amount of online data (DT)=-1, so that the two terms in Eq. 1 have similar weight and we ensure low Bellman error on v throughout the learning process. In practice, we implement this by having all model updates use a fixed proportion of offline samples even as we collect more online data, so that we do not "forget" the distribution v. This is quite different from warm-starting with D and then switching to online RL, which may result in catastrophic forgetting due to a vanishing proportion of offline samples being used for model training as we collect more online samples. We note that this balancing scheme is analogous and inspired by the one used by Ross & Bagnell (2012) in the context of model-based RL with a reset distribution. Previously, similar techniques have also been explored for various applications (for example, see Appendix F.3 of Kalashnikov et al. (2018)). As in Ross & Bagnell (2012), a key practical insight from our analysis is that the offline data should be used throughout training to avoid catastrophic forgetting.
THEORETICAL ANALYSIS: Low BILINEAR RANK MODELS
In this section we present the main theoretical guarantees for Hy-Q. We start by stating the main assumptions and definitions for the function approximator, the offlin data distribution, and the MDP. We state the key definitions and then provide some discussion.
Assumption 1 (Realizability and Bellman completeness). For any h, we have Q7 E F Additionally, for any fa+1 E FR+1, we have Th++1 E Fu-
Definition (Bellman error transfer coefficient). For any policy n, define the transfer coefficient as
1h= B, a [T (8, f1((,
C+ = max O, max JEF
-H- Esgaarn (T a) ftn a))
Definition 2 (Bilinear model (Du et al., 2021)). We say that the MDP together with the function class F a bilinear model of rank d for any h E [H- 1), there exist two (unknown) mappings Xn, Wh F + Rd with max, [|xx(f))22 S Bx and max, [[W,(f)la l S Bw such that:
Vf.g FF: s.add (9, a) Thh+1 (s, a)l| (xx,(), Wx(.)
All concepts defined above are frequently used in the statistical analysis of RL methods with function approximation. Realizability is the most basic function approximation assumption, but is known to be insufficient for offline RL (Foster et al., 2021) unless other strong assumptions hold (Xie & Jiang, 2021; Zhan et al., 2022: Chen & Jiang, 2022). Completeness is the most standard strengthening of realizability that is used routinely in both online (Jin et al., 202 and offline RL (Munos & Szepesvári, 2008; Chen & Jiang, 2019) and is known to hold in several settings including the linear MDP and the linear quadratic regulator. These assumptions ensure that the dynamic programming updates of FQI are stable in the presence of function approximation.
The transfer coefficient definition above is somewhat non-standard, but is actually weaker than related notions used in prior offline RL results. First, the average Bellman error appearing in the numerator is weaker than the squared Bellman error notion of (Xie et al., 2021a); a simple calculation shows that Cº is upper bounded by their coefficient. Second, by using Bellman errors, both of these are bounded by notions involving density ratios (Kakade & Langford, 2002; Munos & Szepesvári, 2008; Chen & Jiang, 2019). Finally, many works, particularly those that do not employ pessimism (Munos & Szepesvári, 2008; Chen & Jiang, 2019), require "all-policy" analogs, which places a much stronger requirement on the offline data distribution v. In contrast, we will only ask that C₂ is small for some high-quality policy that we hope compete with (see Appendix A.5 for more details).
Lastly, the bilinear model was developed in a series of works (Jiang et al., 2017: Jin et al., 2021a; Du al., 2021) on sample efficient online RL. The setting is known to capture a wide class of models
Jin et al. (2021a) consider the Bellman Fluder dimension, which is related but distinct from the Bilinear model. However, our proofs can he easily translated this setting; see Appendix C for more details.
5

---

Published as a conference paper at ICLR 2023
including linear MDPs, linear Bellman complete models, low-rank MDPs, reactive POMDPs, and more. As a technical note, the main paper focuses on the "Q-type" version the bilinear model, but the algorithm and proofs easily extend to the "V-type" version. See Appendix C for details.
Theorem (Cumulative suboptimality). Fix 8 E (0, 1), Moff = and Mon = 1, suppose that the function class F satisfies Assumption 1, and together with the underlying MDP admits Bilinear rank d. Then with probability at least 1 - 6, Algoritim obtains the following bound on cumulative subpotimality w.r.t. any comparator policy x²,
T Σv V = - =m(max(Ca 1, v /dH2T- log (F10)) -V-
where x² = TT' is the greedy policy w.E.. f round t.
& Ben-David, 2014) immediately gives the following sample complexity guarantee for Algorithm for finding e-suboptimal policy w.r.t. the optimal policy π for the underlying MDP.
standard online-to-bater conversion
Corollary 1 (Sample complexity). Under the assumptions of Theorem I if oo then Algorithm I can find an e-suboplimal policy मे for which V - -V S with total sample complexity:
n = Ō max C2. H (llg((())/))
The results formalize the statistical properties of Hy-Q. In terms of sample complexity, a somewhat unique feature of the hybrid setting that both transfer coefficient and bilinear rank parameters are relevant, whereas these (or related) parameters typically appear in isolation in offline and online RL respectively. In terms of coverage, Theorem highlights an "oracle property" Hy-Qu Q: competes with any policy that is sufficiently covered by the offline dataset.
We also highlight the computational efficiency of Hy-Q: only requires solving least squares problems over the function class F. To our knowledge, no purely online or purely offline methods are known to efficient in this sense, except under much stronger "uniform" coverage conditions.
5.1 THE LINEAR BELLMAN COMPLETENESS MODEL.
We next showcase example of low bilinear rank models: the popular linear Bellman complete model which captures the linear MDP model (Yang & Wang, 2019; Jin et al., 2020), and instantiate the sample complexity bound in Corollary 1.
Definition 3. Given a feature function Φ S x A - Ba(()), a model admits linear Bellman completeness for any w BB(BB)), there exists w' (B((B)) such that
Vs (w' (w',6(s,0) a)) [[ a)] + Eg(P((s.)) max(w, a(8', a,)))
Note that the above condition implies that (7 a) (w o(s, a)) with | ll2 S Bw. Thus, we can define function class Fr, = [(wn, ((5,a) )) wh E Rd || lla Bw) which by inspection satisfies Assumption Additionally, this model is also known to have bilinear rank at most d (Du al., 2021). Thus, using Corollary we immediately get the following guarantee:
Lemma 1. Let 8 E (0, 1), suppose the MDP is linear Bellman complete, C.+ < 80, and consider Fn defined above. Then, with probubility 8, Algorithm finds an e-suboptimal policy with total sample complexity:
n CH
Remark 1 (Computational efficiency). For linear Bellman complete models, we note that Algorithm I can be implemented efficiently under mild assumptions. For the class in Lemma the regression problem in (1) reduces to a least squares linear regression with norm constraint on the weight vector. This regression problem can be solved efficiently by convex programming with computational efficiency scaling polynomially in the number of parameters (Bubeck et al., 2015) (d here), whenever max, fN+1(s, a) (or argmax, f1411s, a)) can be computed efficiently.
Remark 2. (Linear MDPs) Since linear Bellman complete models generalize linear MDPs (Yang Wang, 2019; 9 Jin et al., 2020), as we discuss above, Algorithm 1 can be implemented efficiently whenever max, J&+ 1 (8, a) be computed efficiently. The latter is tractable when:

---

Published as a conference paper at ICLR 2023
(s, a) for any and thus When |A] is smallifinite, one can just enumerate compute max, fh+11 (1) can be implemented efficiently. The computational efficiently of Algorithm I in this case is comparable the prior works, e.g. Jin al. (2020).
When the set {ø(s, a) I a E A} is convex and compact, one can simply use a linear optimization oracle to compute max, fn+1(s, a) max Wh41 ( a). This linear optimization problem is itself solvable with computational efficiency scaling polynomially with here).
Note that even under access to a linear optimization oracle, prior works e.g. Jin et al. (2020) rely B on bonuses in the form of argmax, 6(s, a) w + - (,,ss, a) Eé(s, a), where E is some positive definite matrix (e.g., the regularized featurre feature covariance matrix). Computing such bonuses could be NP-hard (in the feature dimension d) without additional assumptions (Dani et al., 2008).
Remark 3. (Relative condition number) A common coverage metric in these linear MDP models is the relative condition number. In Appendix A.5, we show that our coefficient C is upper bounded by the relative condition number of with respect to Ed || 2,,, where En Be,a a) (s, a).
Concretely, we have CT S
maxx Eay 110
5.2 WHY DON'T OFFLINE RL METHODS WORK?
One may wonder why do pure offline RL methods fail to learn when the transfer coefficient is bounded, and why does online access help? We illustrate with the MDP construction developed by Zhan et al. (2022); Chen & Jiang (2022), visualized in Figure 1.
Consider two MDPs (M, with H 2, three states {A, C), two actions {L. R} and the fixed start state A. The two MDPs have the same dynamics but different rewards. In both, actions from state B yield reward 1. In M,. (C, R) yields reward 1 while (C, L) yields reward 1 in M2. All other rewards are In both M1 and M2, an optimal policy T (A) = L and x (B) x (C') = Uniform ((L, R}). With F = (QI, Q5} where Q7 is the optimal Q function for M,. then one can easily verify that F satisfies Bellman completeness, for both MDPs. Finally with offline distribution supported on states and B only (with no coverage on state C), we have sufficient coverage over d= However, samples from y/ are unable to distinguish between fi and f2 or (M, and M2), since state C is not supported by v. Unfortunately, adversarial tie-breaking may result the greedy policies of S1 and /2 visiting state C, where we have no information about the correct action.
B
+0
+1
+1
+0
Figure A hard in- stance for offline RL (Zhan et al., 2022, reproduced with per- mission)
This issue has been documented before, and order to address with pure
offline RL, existing approaches require additional structural assumptions. For instance, Chen & Jiang (2022) assume that Q* has a gap, which usually does not hold when action space is large or continuous. Xie et al. (2021a) assumes policy-dependem Bellman completeness for every possible policy π E II (which is much stronger than our assumption), and Zhan et al. (2022) assumes a somewhat non-interpretable realizability assumption on some "value" function that does not obey the standard Bellman equation. In contrast, by combining offline data and online data, our approach focuses functions that have small Bellman residual under both the offline distribution and the on-policy distributions, which together with the offline data coverage assumption, ensures near optimality, It is easy to see that the hybrid approach will succeed Figure 1.
6 EXPERIMENTS
In this section we discuss empirical results comparing Hy-Q to several representative RL methods on two challenging benchmarks. Our experiments focus on answering the following questions:
1. Can Hy-Q efficiently solve problems that SOTA offline RL methods simply cannot?
Can Hy-Q, via the use of offline data, significantly improve the sample efficiency of online RL?
Does Hy-Q scale to challenging RL benchmarks?
Our empirical results provide positive answers to all of these questions. To study the first two, we consider the diabolical combination lock environment (Misra et al., 2020; Zhang et al., 2022c), synthetic environment designed to be particularly challenging for online exploration. The synthetic nature allows to carefully control the offline data distribution modulate the difficulty of the
7

---

Published as a conference paper at ICLR 2023
Per- Per-episode reward
Optimal Occupancy
Optimal Trajectory
1.0
00::5m
c60m
c0..2m
0.5-
0.0
COL.4cm
BC440m
0
100m
200m
300m
400m
100m
200m
300m
400m
Number of online samples
Number online samples
CQL
BC
Hy Q:1m
H500k
Hy Hy50k
DRIEE
Figure 2: The learning curve for combination lock with H/ 100. The plots show the median and 80th/20th quantile for 5 replicates. Pure offline and IL methods are visualized as dashed horizontal lines (in the left plot, CQL overlaps with BC). Note that we report the number of samples while Zhang et al. (2022c) report the number of episodes.
setup and also compare with a provably efficient baseline (Zhang et al., 2022c). To study the third question, we consider the Montezuma's 's Revenge benchmark from the Arcade Learning environment, which is one of the most challenging empirical benchmarks with nigh-dimensional image inputs, largely due to the difficulties of exploration. Additional details are deferred to Appendix E.
Hy-Q implementation. We largely follow Algorithm in our implementation for the combination lock experiment. Particularly, we use a similar function approximation to Zhang et al. (2022c), and a minibatch Adam update Eq. (1) with the same sampling proportions as in the pseudocode. For Montezuma'ss 's Revenge, in addition to minibatch optimization, since the horizon of the environment is not fixed, we deploy a discounted version of Hy-Q. Concretely, the target value in the Bellman error is calculated from the output of a target network, which is periodically updated, times a discount factor. We refer the readers Appendix E for more details.
Baselines. We include representative algorithms from four categories: (1) for imitation learning we use Behavior Cloning (BC) (Bain & Sammut, 1995), (2) for offline RL we use Conservative Q-Learning (CQL) (Kumar et al., 2020). (3) for online RL we use BRIEE (Zhang et al., 2022c) for combination lock' and Random Network Distillation (RND) (Burda et al., 2018) for Montezuma's 's Re- venge, and (4) as a Hybrid-RL. baseline we use Deep Q-learning from Demonstrations (DQFD) (Hester et al., 2018). We note that DQFD and prior hybrid RL methods combine expert demonstrations with online interactions, but are not necessarily designed to work with general offline datasets.
6.1 COMBINATION LOCK
The combination lock benchmark is depicted in Figure 3 and consists of horizon Hl = 100, three latent states for each time step and 10 actions in each state. Each state has a single "good" action that advances down a chain of favorable states from which optimal reward can be obtained. A single incorrect action transitions to an absorbing chain with suboptimal value. The agent operates on high dimensional observations and must use function approximation succeed. This is an extremely challenging problem for which many Deep RL methods are known to fail (Misra et al., 2020), in part because (uniform) random exploration only has 10 probability of obtaining the optimal reward.
On the other hand, the model has low bilinear rank, so we do have online RL algorithms that are provably sample-efficient BRIEE currently obtains state of the art sample complexity. However, its sample complexity is still quite large, and we hope that Hybrid RL can address this shorteoming. We are not aware of any experiments with offline RL methods on this benchmark.
We construct two offline datasets for the experiments, both of which are derived from the optimal policy л². In the optimal trajectory dataset we collect full trajectories by following x² with e-greedy exploration with 1/ the optimal occupancy dataset we collect transition tuples from the state-occupancy measure of x* with random actions. Both datasets have bounded concentrability coefficients (and hence transfer coefficients) with respect to 'τ" but the second dataset is much more challenging since the actions do not directly provide information about π², as they do in the former.
Figure 3: The combina- tion lock (Zhang et al., 2022c), reproduced with permission.
*We note that BRIEE is currently the state-of-the-art method for the combination lock environment. In particular, Misra et al. (2020) show that many Deep RL baselines fail this enviroment. Formally, we sample Unif([A]], di. Unif( r R(s,a), s' P(s,a).
8

---

Published as a conference paper at ICLR 2023
per-eplsode reward
Easy
Medium
Hard
5k
4k
2k
0
5m
10m
15m
5m
10m
15m
5m
10m
15m
Number of frames
Number of frames
Number of frames
Expert
Offline
Hy-Q
Figure 4: The learning curve for Montezuma's Revenge. The plots show the median and 80th/20th quantile for 5 replicates. Pure offline, IL methods and dataset qualities are visualized as dashed horizontal lines. "Expert" denotes y* and "Offline" denotes the average trajectory reward in the offline dataset. The y-axis denotes the (moving) average of 100 episodes for the methods involving online interactions. Note that COL. and Bc overlap on the last plot.
The results are presented in Figure First, we observe that Hy-Q can reliably solve the task under both offline distributions with relatively low sample complexity (500k offline samples and I 25m online samples). In comparison, Bc fails completely since both datasets contain random actions. CQL solve the task using the trajectory-based dataset with sample complexity that is comparable to the combined sample size of Hy-Q. However, CQL fails on the occupancy- not informative. Indeed the pessinism-inducing regularizer of CQL is constant on this dataset and so the algorithm reduces to FQI. Finally, Hy-Q can solve the task with a factor of 5-10 reduction in (online and offine) samples when compared with BRIEE, This demonstrates the robustness and sample efficiency provided by hybrid RL.
dataset since the
actions themselves
6.2 MONTEZUMA'S REVENGE
To answer the third question, we turn to Montezuma's ' Revenge, an extremely challenging image- based benchmark environment with sparse rewards. We follow the setup from Burda et al. (2018) and introduce stochasticity to the original dynamics: with probability 0.25 the environment exe- cutes the previous action instead of the current one. For offline datasets, we first train "expert policy" лe via RND to achieve V* Rs 6400. We create three datasets by mixing samples from xe with those from random policy: the easy dataset contains only samples from x², the medium dataset mixes in a 80/20 proportion (80 from x"), and the hard dataset mixes in a 50/50 pro- portion. Here we record full trajectories from both policies in the offline dataset, but measure the proportion using the number of transition tuples instead of trajectories. We provide 0.1 million offline samples for the hybrid methods, and I million samples for the offline and IL methods.
Results are displayed in Figure 4. CQL fails completely on all datasets. DQFD performs well on the easy dataset due to the large margin loss (Piot et al., 2014) that imitates the policies in the offline dataset. However, DQFD's 's performance drops the quality of the offline dataset degrades (medium), and fails when the offline dataset is low quality (hard). We also observe that Bc is competitive bascline in the first two settings, and thus we view these problems relatively easy to solve. Hy-Q is the only method that performs well on the hard dataset. Note that here, BC's performance quite poor. We also include the comparison with RND in Figure 5: with only 100k offline samples from any of the three datasets, Hy-Q is over 10x more efficient in terms of online sample complexity.
7k
Montezuma's Revenge
5k-
per-egiodde
4k
3k
Expt
(edd..)
0
Hy- dhrdi
50m 100m 150m 200m
Number frames
Figure 5: Learning curves of Hy-Q and RND. Metric fol- lows Figure
CONCLUSION
We demonstrate the potential hybrid RL with Hy-Q, simple, theoretically principled, and empiri- cally effective algorithm. Our theoretical results showcase how Hy-Q circumvents the computational issues of pure offline or online RL, while our empirical results highlight its robustness and sample efficiency. Yet, Hy-Q is perhaps the most natural hybrid algorithm, and we optimistic that there is much more potential to unlock from the hybrid setting. We look forward to studying this in the future.

---

Published as a conference paper at ICLR 2023
Reproducibility Statement. For theory results, provide detailed proof in the Appendices. For experiments, we submit anonymous code in the supplemental materials. Our (offline) dataset can be reproduced with the attached instructions, and our results could be reproduced with the given random seeds. For more details, we include implementation, environment and computation hardware details in the Appendices, along with hyperparameters for both our method and the baselines. We also open source our code at https: / github. com/ hann//yddaonng / HyQ.
ACKNOWLEDGEMENT
AS thanks Karthik Sridharan for useful discussions. WS acknowledges funding support from NSF IIS 2154111 We thank Simon Zhao for their careful reading of the manuscript and improvement on the technical correctness of our paper. We also thank Uri Sherman for their discussion on the computational efficiency the original draft.
REFERENCES
Yasin Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, 2019.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. 2019. URL, httpps:: : /r1 htt/rrlthhhoroooo gi thub. io/.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank MDPs. In Advances in Neural Information Processing Systems, 2020a.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, 2020b.
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the Atari human benchmark. In International Conference on Machine Learning. 2020.
James Bagnell, Sham M Kakade, Jeff Schneider, and Andrew Ng. Policy search by dynamic programming. Advances in Neural Information Processing Systems, 2003.
Michael Bain and Claude Sammut. framework for behavioural cloning. In Machine Intelligence 15, 1995.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning envi- ronment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 2013.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In International Conference Artificial Intelligence and Statistics, 2011.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 2015.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2018.
Jonathan Chang, Masatoshi Uchara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems, 2021.
Jinglin Chen and Nan Jiang. Information- considerations in batch reinforcement learning. In International Conference Machine Learning, 2019.
10

---

Published as a conference paper at ICLR 2023
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-rate ratio realizability: the power of gaps. arXiv:2203.13935, 2022.
Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. 2008.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient PAC RL, with rich observations. In Advances Neural Information Processing Systems, 2018.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: structural framework for provable generalization RL. International Conference on Machine Learning, 2021.
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.
Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning, In Advances in Neural Information Processing Systems, 2021.
Zhaohan Daniel Guo, Shantanu Thakoor, Miruna Pislar, Bernardo Avila Pires, Florent Altché, Corentin Tallec, Alaa Saade, Daniele Calandriello, Jean-Bastien Grill, Yunhao Tang, Michal Valko, R'emi Munos, Mohammad Gheshlaghi Azar, and Bilal Piot. BYOL-explore: Exploration by bootstrapped prediction. arXiv:2206. 08332, 2022.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Soft actor-critic algorithms and applications. arXiv: /8/2.05905 2018.
Todd Hester, Matej Vecerik, Olivier Pietquin, Marc Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, John Agapiou, Joel Z. Leibo, and Audrunas Gruslys. Deep Q-learning from demonstrations. In AAAI Conference on Artificial Intelligence, 2018.
Zhiwei Jia, Xuanlin Li, Zhan Ling, Shuang Liu, Yiran Wu, and Hao Su. Improving policy optimization with pnneraalistspeciallii learning. In International Conference Machine Learning, pp. 10104 10119. PMLR, 2022.
Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low Bellman rank are PAC-leamable. In International Conference on Machine Learning, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, 2020.
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, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning. 2021b.
Sham M Kakade. A natural policy gradient. Advances in Neural Information Processing Systems, 2001.
Sham M Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, 2002.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang. Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Qt-opt: Scalable deep reinforcement learning for vision-based robotic manipulation. arXiv preprint 188.11180..10293, 2018.
11

---

Published as a conference paper at ICLR 2023
Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computational-sttinn stattsssica gaps in reinforcement learning. In Conference on Learning Theory, 2022.
Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit Q-learnig. w 2021.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for offline reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Seunghyun Lee, Younggyo Seo, Kimin Lee, Pieter Abbeel, and Jinwoo Shin. Offline-to-online reinforcement learning via balanced replay and pessimistic q-ensemble. In Conference Robot Learning, pp. 1702-1712. PMLR, 2022.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv:2005.01643, 2020.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In International Conference Learning Representations, 2016.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank MDPs. arXiv:2102.0703: 07035, 2021.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008.
Ashvin Nair, Bob McGrew, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Overcom- ing exploration in reinforcement learning with demonstrations. IEEE International Conference on Robotics and Automation, 2018.
Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online reinforcement learning with offline datasets. urXiv:2006.09333 2020.
Haoyi Niu, Shubham Sharma, Yiwen Qiu, Ming Li, Guyue Zhou, Jianming Hu, and Xianyuan Zhan. When to trust your simulator: Dynamics-aware hybrid fifline-and-onlie reinforcement learning. arXiv preprint arXiv:2206. 13444, 2022.
Bilal Piot, Matthieu Geist, and Olivier Pietquin. Boosted bellman residual minimization handling expert demonstrations. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, 2014.
Shuang Qiu, Lingxiao Wang, Chenjia Bai, Zhuoran Yang, and Zhaoran Wang. Contrastive UCB: Prov- ably efficient contrastive self-supervised learning in online reinforcement learning. In International Conference on Machine Learning, 2022.
Aravind Rajeswaran, Vikash Kumar, Abhishek Gupta, Giulia Vezzani, John Schulman, Emanuel Todorov, and Sergey Levine. Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. 1709, 10087, 2017.
Stephane Ross and Andrew Bagnell. Agnostic system identification for model-based reinforcement learning. arXiv: /203. 1007, 2012.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv:1511.05952, 2015.
Julian Schritwieserr, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering Atari, Go, chess and Shogi by planning with learned model. Nature, 2020.
12

---

Published as a conference paper at ICLR 2023
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:1707.06344 2017.
Ayush Sekhari, Christoph Dann, Mchryar Mohri, Yishay Mansour, and Karthik Sridharan. Agnostic reinforcement learning with low-rank MDPs and rich observations. Advances in Neural Information Processing Systems, 2021.
Shai Shalev-Shwariz and Shai Ben-Davie Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
Wen Sun, Nan Jiang, Akshay Krishnamurthh, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. Conference on learning theory, 2019.
Ikechukwu Uchendu, Ted Xiao, Yao Lu, Banghua Zhu, Mengyuan Yan, Joséphine Simon, Matthew Bennice, Chuyuan Fu, Cong Ma, Jiantao Jiao, Sergey Levine, and Karol Hausman. Jump-start reinforcement learning. Sedi:22004003722, 2022.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference Learning Representations, 2021.
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. arXiv:2110.04652, 2021.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. In AAAI Conference Artificial Intelligence, 2016.
Mel Vecerik, Todd Hester, Jonathan Scholz, Fumin Wang, Olivier Pietquin, Bilal Piot, Nicolas Heess, Thomas Rothörl, Thomas Lampe, and Martin Riedmiller. Leveraging demonstrations for deep reinforcement learning robotics problems with sparse rewards. / 2017.
Ruosong Wang. Yifan Wu, Ruslan Salakhutdinov, and Sham Kakade. Instabilities of offline rl with pre-trained neural representation. In International Conference on Machine Learning, 2021.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International Conference Machine Learning, 2016.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference Machine Learning, 2021.
Tengyang Xie. Ching-Ar An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. pessimism for offline reinforcement learning. Advances in Neural Information Processing Systems, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in Neural Information Processing Systems, 2021b.
Lin Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, 2019.
Tianhe Yu, Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. Combo: Conservative offline model-base policy optimization. In Advances in Neural Information Processing Systems, 2021.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, 2020.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in Neural Information Processing Systems, 2021.
13

---

Published as a conference paper at ICLR 2023
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single- segle-policy concentrability. In Conference on Learning Theory, pp. 2730-2775. PMLR, 2022.
Tianjun Zhang, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear MDPs practical via contrastive representation learning. In International Conference on Machine Learning. 2022a.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption robust offline reinforcement learning. In International Conference Artificial Intelligence and Statistics, 2022b.
Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block MDPs: A model-free representation learning approach. In International Conference on Machine Learning, 2022c.
14

---

Published as a conference paper at ICLR 2023
A
PROOFS FOR SECTION 5
Additional notation.
Throughout the appendix, we define the feature covariance matrix Σigh as
Eigh = (((())( + AL
(3)
Furthermore, given distribution A(S x A) and function f A R, we denote its weighted lg norm as [ == 8 (2
A.1 SUPPORTING LEMMAS FOR THEOREM 1
Before proving Theorem 1, first present few useful lemma. We start with standard result least square generalization bound, which is be used by recalling that Algorithm 1 performs least squares on the empirical bellman error. We defer the proof of Lemma
Appendix B.
Lemma 2. (Least squares generalization bound) Let R O, å E (0, 1), consider sequential function estimation setting, with an instance space and target space y. Let H. x I-R, R] be class of real valued functions. Let D {(I1, y1)...., (2.r. yr }} be a dataset of T points where It ~ Ps == Pe(praa--- (1:1-1). and yt is sampled via the conditional probability p(. x1):
Yt p(. (xa)) == h (xxa) Exs
where the function ht satisfies approximate realizability i.e.
T E t=1
inf bEA
Eamp. (h²(z)) (h^(z)- h(x))² S s:
and (6)]= are independent random variables such that Elye xrl = (xx)). Addition- ally, suppose that max, lyel R and (xx S R. Then the least square solution
To 4 arg Eiz1(haa (h((re) ) - 3² satisfies with probubility at least 1 8,
T
Σ Exros [M(x)) 10 (x)))) & 3YT + 256R 10/(2)7(/88)
The above lemma is basically an extension of the standard least square regression agnostic gener- alization bound from i.i.d. setting to the non-i.i.d. case with the sequence of training data forms sequence of Martingales. We state the result when the realizability only holds approximately upto the approximation However, for all our proofs, we invoke this result by setting 7 = O.
In the next two lemmas, we prove two lemmas where we can bound each part of the regret decompo- sition using the Bellman error of the value function f.
Lemma 3 (Performance difference lemma). For any function f = (oo...,SH-1)) where Jn
S A + R and h [H 1), have
Egndy [max fo(s, a) vol (6)
Σ
E
((n( (/an////nnnn
T TThn (s,
where define [n(s, a) for all 8, a.
Proof. We start the proof by noting that T/ (s) = argmax, fo(s, ((ss, a), then we have:
Egwdo max fo(s,a) x (s)] Egydd [ and an Fols, a) V.5((() (s)
Egndd a fo a) -T---fiie (s, E Egddo (an Th( 1/- (s)
E
= E awdd [o((,, () -aia)--fi(s Ts,
E, Sy E
aang(()) [R(s, a) + (BgeP((sn) max fi(s', - R(ss,)) + EEr ViL (s')l
o
15

---

Published as a conference paper at ICLR 2023
E
sga -) - (s) + saddt/ [max (i VT'
(8)
(4)
Then by recursively applying the same procedure on the second term in (4), we have
H-1
Ba max fo(s, a) V= (s)
= Σ E saway
(f)(s,a) -T Tf,+ E sway/ mmxx fH(s, a) - VHH (s)].
h=0
Finally for h H, we recall that we set fa(s,a) 0 and V 0 for notation simplicity, Thus have:
IE Eg [max fo(s, v= (s))
(s)
E (f((s,a)
s
H --1
E s.and? (fh(s,
[s,
Now we proceed how to bound the other half in the regret decomposition:
Lemma Let xe (Tō.... ..... TH Th--1) be a comparator policy, and consider any value function .fo..... FH-1) where fn 8 x + R. Then,
H-1
Egndd
Voah (8) - max max So(8, a) S Σ
Bs.and (TSe11 -((s,a)),
i=0
where defined fH(8 a) 0 for all
Proof. The proof similar to the proof of Lemma 3, and we start with the fact that max, f(, a) 2 f(s, d'), Va', including actions sampled from π":
Exwdo 10" (s) max fo(s, a)]
< E B.
Q (s, - fols,a)
E aaand
2 20 (s,a) - Tfi(s, +Tf((8,,) - fo(s. a)]
Eggandge
EerNP(s,)) Vi (8') max fi (1'ss''')) a') + Eg.andg (Tii(s;a) - fo(s,
BB
VTT (s) max -s) fi a) + E Egardy (T) fo(s,a)
(5)
Again by recursively applying the same procedure the first term in (5), we have
H-1
Exddo Vot (s) - max a0) < Es-die VH (s) - max fn (s, a)
+
Σ
E
Egandfo I [Tuua - (s,
h=0
and recall that (s a) = 0 and VØL = O, we have
#-1
E Exndo V00 (s)- max fo(s, a)
Σ
E
aa (T(++((8,)) fn(s,a))
The following result is useful in the bilinear models when want bound the potential functions. The result directly follows from the elliptical potential lemma (Lattimore & Szepesvári, 2020. Lemma 19.4).
16

---

Published as a conference paper at ICLR 2023
Lemma 5. Let xx.(")....,xXX Xn(ff) Rd be sequence of vectors with [|x(ff))| Bx < <000 for all t & T. Then,
TB$
Σ [ $
$V V200 log 1+
Ad
where the matrix Eich = E Xn( AI [T] and X 2 B3 and the matrix norm [xx(( (Xx(((")TTE 11-1xx000
Proof. Since À 2 Bx,, we have that
[ S ( 1
Thus, using elliptical potential lemma (Lattimore Szepesvári, 2020, Lemma 19.4), we get that
T
TB
Σ
|X*(())
E2 S 2d
1+
Ad
The desired bound follows from Jensen's 's inequality which implies that
T
T
TB3 Ad
Xx((*)
b 11th
S
T
s
2r
1+
1=1
A.2 PROOF OF THEOREM 1
Before delving into the proof, first state that following generalization bound for FQI.
Lemma 6 (Bellman error bound for FQI). Let å E (0, 1) and let for h E [/ - 1] and t E [T], fr. be the estimated value function for time step h computed via least square regression using samples in the dataset (D). D h: .D,)) in (1) in the iteration t of Algorithm 1. Then, with probability at least
1 - 8, for any h E H 1] and 1 E [T].
|| T 2 S
1
256V2 max (2g =: Aof..
h+1
Moff
and
256V2 1og(2HT( Don.
2.14
Mon
where denotes the offline data distribution at time h, and the distribution J.d, E A(s, a) is defined such that 8, di
Proof. Fix t T h E [I 1] and pt+1 E Fa+1 and consider the regression problem ((1) in the iteration of Algorithm I):
sh+1 <- argmin Rpg (f()) max p+t ( ,d))) JEF,
where dataset D), DV + Σ Dj consisting of Maff + t. mon samples ((i1,)))is where
I, = (s/, a
and
y = + max ftt a))
In particular, define D such that the first mar samples ((r,, yi) vi) (i)ismon Dí the next Mon
samples (x1, 3:) ) Jemortt = D), and on where the samples {(x;, W/) i= (T- 1)m DJ. Note that: (a) for any sample (rr = (sh, an), y (r + max, fft (sh+1, a))) in D, we have that
more +rmon
Byy x]
Eg Egs Pm [r max f (8)42.a)
17

---

Published as a conference paper at ICLR 2023
=Tshii (sh: an) - ((sh,an);
where the last line holds since the Bellman completeness assumption implies existence of such function (b) for any sample, ly/ S Viax and f(, I Vmax for all s, a. (c) our construction of DD implies that for each iteration I, the sample (dte Mt) are generated the following procedure: Te is sampled from the data generation scheme DD (11:t-11 11:t-)),,,,, and is sampled from some conditional probability distribution p(- xx) as defined in Lemma finally (d) the samples in Dj are drawn from the offline distribution Mh, and the samples in 27 are drawn such that di and an T." (sn).Thus, using Lemma 2, we get that the least square regression solution f4+1 satisfies
Σ
at)) D. S 256V -
max 1og(2
Using the property- (d) in the above, we get that
Moft 115h T Mon
- T 2,14, S 256V max 1og(2)F1/6).
where the distribution J A(s, a) is defined by sampling s ~ d% and a ~ x (s). Taking a union bound over [H 1] and E (7), and bounding each term separately, gives the desired statement.
We next note change in distribution lemma which allows us bound expected bellman error under the (s, a) distribution generated by f in terms of the expected square bellman error w.r.t. the previous policies data distribution, which further controlled using regression.
Lemma 7. For any t 2 0 and h E [H 1). have
(TAl")),,,("))) & |xx(0))|l,
Σ
E s.
[ (Jh+T + AB
where E defined in (3) and use the notation df, to denote az.""
Proof. Using Cauchy-Schwand inequality, get that (WWLF))xx 1xx())) [[ 1.6
=IXx(('))1E V (WA(P)) Ee-WW
= -1X,,00 M
Σ XXUM)X,1O + Whrrr (WA(19)
=IXx(09|1 2
< |X,(%) 3m
(WAA))) +AB
(6)
E srana! [1r - -TTh+i))) AD
where the inequality in the second last line holds by plugging in the bound on ||Vx( and the last line holds by using Definition 2 which implies that
(W)()') Xx(P))²
aa [5h -Thh+il) s s.a [1hh -Th-Thhii))
where the last inequality is due Jensen's inequality.
18

---

Published as a conference paper at ICLR 2023
We now have all the tools prove Theorem 1. We first restate the bound with the exact problem dependent parameters, assumign that Bw and Bx are constants which are hidden in the order notation below.
Theorem (Theorem restated). Let Matf = T and mon = 1. Then, with probability at least 1 - ô, the cumulative suboptimality of Algorithm is bounded as
v -Va =0 max
dH log 1+ T
HT
F
log
Proof of Theorem I. Let n" be any comparator policy with bounded transfer coefficient
Σ H-1 E, Braan (f)(s, - T Th++2(s,a)
C. = max O, max SEF
<00.
V Em== Esganee (ff(s,a) - T fs++)
We start by noting that
T
T
m
Eg
Vo= (s) - VoT" (s)
t=1
t=1
E Eando
Vor (8) max (8(8,a) a))
+ B max Sols, a) - Vo (s)
t=1
(8)
For the first term in the right hand side of (8), note that using Lemma 4 for each fo for 1 S t T, get
H
E Egndo
Vo-(() (8)
max fa(s
E
aa
[T sh(s,aa]
t=1
h=0
T
H-1
Cre
Eg Eg,anvs (f)(s,a) - (
1=1
A=
Doff where the second inequality follows from plugging in the definition of C.,, in (7). The last line follows from Lemma
=
TC
VH
For the second term in (8), using Lemma 3 for each f. for ST we get
max Eanda
fals a) vor"" (s) s a
(f - (s, "
(10)
H
(X,(())
(x
V + XB
1=1 K=
where the second line follows from Definition 2, the third line follows from Lemma and by plugging in the bound in Lemma 6. Using the bound in Lemma 5 in the above, we get that
E Ba max fe(s. a) - vor" (s) s
2dH² log 1+
TB Xd
-Aam + +B T
T) 1+ d
2dH2 2dH2log log
(Aon +B)BBy). T, (11)
19

---

Published as a conference paper at ICLR 2023
where the second line follows by plugging in À B Combining the bound (9) and (11), we get that
Dott + 2d112 log [+ Σ EV- - v= T VH H
rr ) ( (Aon + Bzx
Plugging in the values of oon and Doft in the above, and using subadditivity of square-root, we get that
V V=l
H
2HT
2dH2T
+ T
22T
< 16V 116Vmax T
log
16V 1666mxx
log
log
Moff
5
Mon
21+2)
1+ +
+ BW
2dT
Setting Moff
T and Mon
= 1 in the above gives the cumulative suboptimality bound
T va
Va = =0 ( 1C max dHST log
HT 8
1 à log
(12)
Proof of Corollary 1. We next convert the above cumulative suboptimality bound into sample com- plexity bound via a standard online-to-batch conversion. Setting x² x² in (12) and defining the policy के = Uniform (TT) , }), we get that
E
V
V
Vxl
T
1=1
dHH
7 log 1+ d
HT
maxx(Cr. 13V Vmaxx
log
T
Thus, we get that for 7' δ m Mose
d 2H2 HTT(
we get that
E 2 V
SE
In these 7' iterations, the total number of offline samples used is
Mof = =T max{(; V2 max dH² log HTT
2
and the total number of online samples used is
max maxfC²., C2., 1
12 max
dH log (HT
Mon H Ö
where the additional H factor appears because we collect samples for every h E [H] in the algorithm.
A.3 V-TYPE BILINEAR RANK
Our previous result focus on the Q-type bilinear model. Here provide the V-type Bilinear rank definition. This V-type Bilinear rank definition is basically the same as the low Bellman rank model proposed by Jiang et al. (2017).
20

---

Published as a conference paper at ICLR 2023
Algorithm 2 V-type Hy-Q
Require: Value function class: F, #iterations: T, Offline dataset D of size mott for h [H 1]. 1: Initialize (x)
2: for 1arl=1....
do
3: [et n² be the greedy policy w.r.t. S i.e., (8) argmax, (8,
// Online collection
4: For each hi, collect mon online tuples Dj ~ dx Uniform(AA)
// FQI using both online and offline data
5: Set fH (s, a.) 0.
6: for h H 1,.... do
7:
Estimate f using least squares regression on the aggregated data:
5 + argmin
Bog (f(,,)) - - max (s Boy (f(s, - max Sati a'))²
SETA
(13)
8: end for
9: end for
Definition 4 (V-type Bilinear model). Consider any pair of functions (f.g) with f.g F. Denote the greedy policy of f as nH {Thh == argmax, fia(s,a), a), Wh]. We say that the MDP together with the function F admits bilinear structure of rank d if for any h E H 11. there exist and Wn. :F + Rd with max, (f)x(f)ll2 I Bx and
two (unknown) mappings Xn, F + Idd max, [[Wx(f)l2 Bw, such that:
Vf.geF:
| Baaay ama
(,) (s,
Tgh+ (s) (X(,,)))
Note that different from the Q-type definition, here the action is taken from the greedy policy with respect to g. This way max, g(s, a) can serve as an approximation of V* thus the name of V-type.
To make Hy-Q work for the V-type Bilinear model, we only need to make slight change on the data collection process, i.e,, when collect online batch Dr, we sample di P(-[s, a). Namely the action is taken uniformly randomly here. We provide the pseudocode in Algorithm 2. We refer the reader Du al. (2021); Jin al. (2021a) for detailed discussion.
Uniform(A) (A), s' ~
A.3.1 COMPLEXITY BOUND FOR V-TYPE BILINEAR MODELS
In this section, give performance analysis of Algorithm 2 for V-type Bilinear models. The contents this section extend the results developed for Q-type Bilinear models in Section A.2 to V-type Bilinear models.
We first note the following bound for FQI estimates in Algorithm 2.
Lemma 8. Let E (0, 1) and let for h E [H 1] and E [T], ft+ be the estimated value function for time step h computed via least square regression using samples in the dataset (Di, , D) ... .Di)) in (13) in the iteration of Algorithm 2. Then, with probability least for any E [1 and E [T].
1 256V log F2HT Aoi. moff
| T
and
1 T 2+11 < Tihtill
256V max 10g(2HT( A.n.
2.1g
Mon
where yn, denotes the offline data distribution time h, and the distribution 14j, Ass, a) is defined such that di. and Uniform(A).
21

---

Published as a conference paper at ICLR 2023
The following change in distribution lemma is the version of Lemma under V-type Bellman rank assumption.
Lemma Suppose the underlying model is a V-rype bilinear model. Then, for any t z and
h E [H -1,, we huve
(WW(F)) & 1x,(f))
|
E snudy
[ -TT+1))+)) AB
a>Uniform(A)
where 2 defined in (3).
Proof. The proof is identical to the proof of Lemma 7. Repeating the analysis till (6), we get that
(WW(F)) & (f
(WF(F) +BB
=I
E smat" (s) 15) -hital) + +BB
|
E swape (nUnformm(A)
[1h (
+B
where the second line above follows from the definition of V-type bilinear model in Definition 4, and the last line holds because:
E (Badgg" (w) (x) 1h - -Thhi]]
$ E switt .anxt' (0) (Fh - (hh+1)
[A
[ -Th+
soud (a-Uniforr((A)
where the first inequality above is due to Jensen's 's inequality and the last inequality follows form straightforward upper bound since each term inside the expectation is non-negative.
We are finally ready to state and prove our main result in this section.
Theorem 2 (Cumulative suboptimality bound for V-type bilinear rank models). Let mon |A] and Moff = T. Then, with probability at least 1 - 8, the cumulative suboptimality of Algorithm is bounded
V Vo -0( mmax(Crr 1.r,,11VWaa dH2T log
T
T' log
HT 8
Proof. The proof follows closely the proof Theorem 1. Repeating the analysis till (8) and (9), we get that:
Σ V* vxx STC, VH Aoll + E Egndo max f6(s, v.r" (s)
(14)
For the second term in the above, using Lemma 3 for each for St5 get
Ba-do max fo(s, varl (5)
E slandy!!
(f((s,a) (s,
T
(xx(0))
0=
22

---

Published as a conference paper at ICLR 2023
T H-
|x,("))
VIAl Aon + AB
where the second line follows from Definition and the last line follows from Lemma and by plugging in the bound in Lemma 8. Using the elliptical potential Lemma as in the proof of Theorem I, we get that
Σ v v=l STCge VH Dont + 2d112 log 1+ 2 (IA) Don + BB, T
Plugging in the values of on and Dor from Lemma in the above, and using subadditivity of square-root, we get that
Σ V= v= S 166V 16V C C
2
2dH
LA
T
2HT
log
16V max
log
1 + d
log
Moff
5
Mon
8
(1+7) d
+ HBx Bw B
2dT log
1 1+
Setting Mon
AA and moff T, we get the following cumulative suboptimality bound:
Σ v" yat =0( maax(Crr 130m d log
T d
HT 8
1
log
(15)
Corollary 2 (Sample complexity). Under the assumptions Theorem 2 if Cg-- o0 then Algorithm can find an c-suboptimal policy सt for which Va" -V* with total sample complexity of:
max f 1)
max V2 dl log
log (TT)3100
Proof. The following follows from standard online-to-batch conversion. Setting n" 7²" in (15) and defining the policy म Uniform { (,!....,,"" we get that
B[VT v*]
val =0(mxx v
(0maxx(Cr (Tre, 1JVaax
dH2
T 1
HT
log
log
d
Thus, the policy returned after T maxx (C?
V2 aH2 log ( man 27
satisfies
B[VT' va] In these iterations, the total number offline samples used
Moff T =T= maxx(C2. 12,,13VV
V2 max dHI log(HT])1/0)
and the total number of online samples collected is
Mon H. T = max Maxx(C..11VV y
log HT H F1/8) max d 12
where the additional H factor appears because we collect mon samples for every E [H] in the algorithm.
23

---

Published as a conference paper at ICLR 2023
A.4 LOW-RANK MDP
In this section, we briefly introduce the low-rank MDP model (Du et al., 2021), which is captured by the V-type Bilinear model discussed in Appendix A.3. Unlike the linear MDP model discussed in Section 5.1, low-rank MDP does not assume the feature & is known a priori.
Definition 5 (Low-ram rank MDP). A MDP is called low-rank MDP if there exists μ¹¹ : :S : R o² x A - Rd, such that the transition dynamics P(s'(s, a) (s') T dt (s,a) a) for all s,a, We (s,
additionally assume that we are given a realizable representation class such that o' E D and that sups,a s.a 11 (s, a)ll2 S 1, and Ilf 1= 1= I for any f : U:S+ 1
Consider the function class Fr. fWTTo(ss ((s,a) ( E w Ba(Bw)), and through the bilinear decomposition we have that Bw S d. By inspection, we know that this function class satisfies Assumption 1. Furthermore, it is well known that the low rank MDP model has V-type bilinear rank of at most d (Du al., 2021). Invoking the sample complexity bound given in Corollary 2 for V-type Bilinear models, we get the following result.
Lemma 10. Let 8 E 10. MDP w.r.t. some o" 4, C < co, and consider Fn defined above. Then, with probability 1 Algorithm 2 finds an e-suboptimal policy with total sample complexity (offline + online):
1) and 4 be a given representation class. Suppose that the MDP is rank d
max Ca. max{Ca.. 13 (HA))))((TTT))))))))))
2
Proof sketch of Lemma 10. The proof follows by invoking the result in Corollary for a discretization of the class F, denoted by F. Fu, ... x FH-1ee- F. is defined such that Fr, {w" p(s, a) E 4, w E (B.c(Bw)) where Ba, (Bw) ) is an e-net of the Ba (w) under foo -dittance and contains O((Bw(e)) /e)d) many elements. Thus, we get that log((FF)) = O Hd log( (+1))/))
For low-rank MDP, the transfer coefficient C₂ is upper bounded by relative condition number style quantity defined using the unknown ground truth feature o" (see Lemma 13). On the computational side, Algorithm (with the modification of (niform(AA) in the online data collection step) requires to solve least squares regression problem at every round. The objective of this regression problem convex functional of the hypothesis / over the constraint set F. While this is not fully efficiently implementable due to the potential non-convex constraint set F (e.g., & could be complicated), our regression problem still much simpler than the oracle models considered in the prior works for this model (Agarwal et al., 2020a; Sckhari et al., 2021; Uchara et al., 2021; Modi et al., 2021).
A.5 BOUNDS ON TRANSFER CORFFICIENT
Note that C₂ takes both the distribution shift and the function class into consideration, and is smaller than the existing density ratio based concentrability coefficient (Kakade & Langford, 2002; Munos Szepesvári, 2008; Chen & Jiang, 2019) and also existing Bellman error based concentrability coefficient Xie et al. (2021a). We formalize this in the following lemma.
Lemma 11. For any π and offline distribution V,
I1 T Th++ 11a5
(s,a)
O S
max f.h
I sup
Iff T Ts+t1 Pe h,s 14 (s(sa))
Proof. Using Jensen's inequality, we get that
-- 11-1llln T fn+ 113g
C₂ S
max f
Σ カー1 11.n T f 112
1l TT 113
max fh
1 - T Tf++1l12
24

---

Published as a conference paper at ICLR 2023
sup ( V
h.s. (s)
(s.0)
sup a, V/ (8, (),
where the second line follows from the Mediant incquality and the last line holds whenever ( s.aa (3,0 1.
Next show that in the linear Bellman complete setting, C2 is bounded by the relative condition number using the linear features.
Lemma 12. Consider the linear Bellman complete setting (Definition 3) with known feature
6. Suppose that the feature covariance matrix induced by offline distribution vs Ev..
E. B.ga-rn 10 (s, ())0())())))))))))))))))) (8,a) is invertible. Then for any policy nT, we have
Cr S
V max E Ea (1, |
Proof. Repeating the argument in Lemma 11, we have
1 T Ts++1 11a5
C+ S
max fhh
11 T f 11 11:h
|| Φ w/, $1
max w.h
||1), Ø- w², $11?
I1(wn w )1 Eay 1012 Eny
< max w,
[1(wn w//) T E11
max E. Es, (|0 s, a)l Dnm!
Recall that in linear Bellman complete setting, write f as u ds and for any that defines f. there exists w such that Tf = w Φ.
Now we proceed to low-rank MDPs where feature is unknown. We show that for low-rank MDPs, Oz is bounded by the partial feature coverage using the unknown ground truth feature.
Lemma 13. Consider the low-rank MDP setting (Definition 5) where the transition dynamics P is
given by P(s') 8, a, (ye* (s'), di (s, a)) for some p d² E Rdd. Suppose that the offline distribution is such that max, max,,a Ih (alals)
v = -Vo...., is induced via trajectories i.e. mo(s) do(s) and (s) = P a) for any h > 1, and that the feature covariance matrix Ev,, 1.d0 Eg 10 (s, (8, a) T] is invertible." Then for any policy n, we have
(a]s) S a: for any s, a. Furthermore, suppose that
H
(100 a) a)
C S
Esaandy_
+ Vo.
Proof. We first upper bound the numerator separately. First note that for h 0,
Exgandz (s,)( - fo(s,a)) <
(Bndonawz7(1)) -T(ss)))))(((saa))
di (s,a) (s(s,a) a)
Egaav (
max
-
TThis is for notation simplicity, and emphasize that do not assume eigenvalues are lower bounded. In other words, eigenvalue of this feature covariance matrix could approach (1*
25

---

Published as a conference paper at ICLR 2023
S Va Braws (T) Jo(s so(s,
(16)
where the last inequality follows from our assumption since maX,,0
dp (s.a] max,,a [a(a] S a. vo(a.a)
sofa
Next, for any h 2 1, we note that backing up one step and looking at the pair a that lead to the state 8, we get that
Ea [T [T - as)
poo [T - [n
(0"(,,)) 1 (s)) Σ x(als) fu,, ds
(3{,aa)" / (((())m(ass)TTT (anaaa)))(saa)) an(s,a)]
= -Eggändh-
// M fa(s, ds
< Eggardg__
(10 (3(5a))l>>
(17)
where the last line follows from application of Cauchy-Schwarzz inequality. For the term inside the expectation in the right hand side above, we note that,
2
/ ur (o(o))rdo)) -((
[
1 Exarees-
(/ - fa(s, a))ds
(T fa((s
Bgaau L.
(T (Tf++1(s,a) as)
(80) EsTN (T (
a Eg (Tf [
(18)
where (i) follows by expanding the norm (ii) follows an application of Jensen's inequality, (iii)
is due to our assumption that the offline dataset is generated using trajectories such that (s)
Eg -1 [P(s a)]. Finally, (iv) follows from the definition of a. Plugging (18) in (17), we get
that for h 2 1,
Eg
[T (h - -
< Eggand
100 as) n Esgaan (TTnt fn(s,
(19)
We are now ready bound the transfer coefficient. First note that using (16), for any f.
a Es,anus
-
F Es [T so(s,a)
Σ H 11 E, Beaan, (T [TTh [(((s
H-1 Er Egganrn ソ=w
- fn a)))
h==
Va.
26

---

Published as a conference paper at ICLR 2023
Furthermore, for any using (19), get that
H-1 Σ h= E an [Tfn+1 fn(s,a)]
2 hh B Barawyn (T (Tfn+i (n(s,
Bs (T ff fn
Eg Ex
110"
1h-1
H-1 E Bsaave
(T (Tsh+i(s, a))
Rg Bg
(5, a)
val
A=1
where the last line holds for an appropriate choice of X (e.g. X 0). Combining the above two bounds in the definition of C² we get that
C
Es,a aad (10 x -0-
+ Vv.
Note that in the above result, the transfer coefficient is upper bounded by the relative coverage under [a(a]s)
unknown feature o* and term a related to the action coverage, i.e., max,, m&x,,a (als) < a. This matches to the coverage condition used in prior offline RI. works for low-rank MDPs (Uehara & Sun, 2021).
B AUXILIARY LEMMAS
In this section, we provide few results and their proofs that we used in the previous sections. We first with the following form of Freedman's 's inequality that is a modification of a similar incquality in (Beygelzimer et al., 2011).
Lemma 14 (Freedman's 's Inequality). Let {X1,..., XT} be sequence of non-negative random variables where each x, is sampled from some process that depends on all previous instances, i.e, It Pt = ( 1). Further, suppose that [Xa] < R almost surely for all S T. Then, for any > 0 and E [0, 1/ 1/2 with probability at least 8.
T
log(2/5)
Σ X, - X pe]
Σ
| pd] + E[X? pb))
À
Proof. Define the random variable Z, = X. -[ pr]. Clearly, (2.)2- is martingale difference
sequence. Furthermore, we have that for any [Z.| S 2R and that
E 2 p.] = E[X, px)))² pt 2R p.] + [ pc]
(20)
where the last inequality holds because |Xe| < R.
Using the form of Freedman's 's inequality in Beygelzimer et al. (2011, Theorem 1), we get that for any [0, 1/2R).
log (2/5)
Σ
Ze
Σ 1=1
E E[Z
pc]
Plugging in the form of Z, and using (20), we get the desired statement.
Next give formal proof of Lemma 2, which gives generalization bound for least squares regression when the samples are adapted to an increasing filtration (and are not necessarily i.i.d.). The proof follows similarly to Agarwal et al. (2019, Lemma A.11).
27

---

Published as a conference paper at ICLR 2023
Lemma 15 (Lemma 2 restated: Least squares generalization bound). Let R > 0, 8 (0, 1). consider a sequential function estimation setting. with an instance space X and target space y. Let H. X + [-R, R) be class of real valued functions. Let D {(z1, y1 (i)..... (2r, yr) } be a dataset of T points where Tt ~ Pe(TTtt-1, 11 and yt is sampled via the conditional probability pl- [x)):
Y1 ~ p(- x.) == h" (x+) + Et,
where the function It" satisfies approximate realizability i.e.
T Σ Eamp, (1) -)(x)) 57
inf NER
and {ei]i=1 are independent random variables such that Elye xel = (xt). Addition- ally, suppose that max, Wal R and maxx/h" (z) S R. Then the least square solution h t- nr Σt= 2h<x()(z)- - y satisfies with probability least 1 8.
Σ Brups
(=)))) 3 256 12g(2)71/6).
Proof. Consider any fixed function h H. and define the random variable Z (h(z;) y1)² (h" (xx) =v)) Define the notation E[- Pe] denote Exp [t], and note that
B[Z pc] (x. h²" (x=))) + h" (xx)) 2y:)] Encppi ((((z))~~((<))))) (2x))))
(21)
where the last line holds because Elye xi] = 11 (3x). Furthermore, we also have that
[[(Z))² pt] Eggeppe (h(az)) - - hx (()))))) + (xx) 2y.)²
< 16R Exp (1(
- 1: hx:))))
(22)
Now we can note that the sequence of random variables [Zi..... z}} satisfies the condition in Lemma 14 with | < 4R². Thus we get that for any À E [0, 1/8R] and O, with probability at
least 1 8,
T
T
( ( + log(2/8)
Σ - - pc]
<
SR² E
pt]
+
1=1
T
Exrxp, (1((1)) 11" (xx)))))] + log(2/0)
< 32XR
E
t=1
where the last inequality uses (21) and (22). Setting A == 1/64 in the above, and taking a union bound over h, we get that for any h E H and 8 O, with probability least 1- 5,
p:]
I 2
Exrroe
- h²" [(h(xz))(
(xx)))) + 64R2 1og(2)7(/6))
Rearranging the terms and using (21) the above implies that,
3
Σ z
Σ Exirp (1((x)) 10" (xx)) 64/2 1617elog(2211111
1=1
and
T
T
Σ
- 11 E Eniop (1 (xx))) < Σ z + 128 log(2)7(/8)).
(23)
t=1
t=1
28

---

Published as a conference paper at ICLR 2023
For the rest of the proof, condition the event that (23) holds for all h H.
Define the function h NEH Et Brirpp [(h(zz) h² (xx)))] Using (23), we get that
T
T
Σ
F Papppi (M(zz)) - - (xx))
+ 64 log(2
2
1=1
$ TT + 64R 10g(2/H1/0).
where the last inequality follows from the approximate realizability assumption. Let h denote the least squares solution on dataset {( 31) he)r By definition, we have that
T
T
Σ - = -((z,) - y²)² (xx) vi)² (h(xx)) - v1)) - (1h()x)) - y10) Σ
Combining the above two relations, we get that
z
3 2 TT + 64R 12)(2/)1/6).
(24)
Finally, using (23) for the function h, we get that
Σ E Exempe (((x)))((=0))))
$ > z 128R log (2
t=1
I 3 256 1og(2)7(/8))
where the last inequality the relation (24).
C Low BELLMAN ELUDER DIMENSION PROBLEMS
In this section, consider problems with low Bellman Eluder dimensions Jin et al. (2021a). This complexity measure a distributional version of the Eluder dimension applied to the class of Bellman residuals w.r.t. F. We show that our algorithm Hy-Q gives similar performance guarantee for problems with small Bellman Eluder dimensions. This demonstrates that Hy-Q applies to any general model-free RL frameworks known in the RL literature far.
We first introduce the key definitions:
Definition (e-independence between distributions (Jin al., 2021a)). G a class of functions defined on space X, and u, Mi,..., be probability measures over X. We say is e-independent
of {M1, ,,,.,.,,,,.. with respect to G if there exists E G such that VEi, 1 S -ut IE, [g]l >E
Definition (Distributional Eluder (DE) dimension). Let & be a function class defined on X and P be a family of probability measures over X' The distributional Eluder dimension dimpe(F. P,E) the length of the longest sequence {PI,.... C P such that there exists g' Z where p: e' -iindependent of ( Pi-1) for all E [n].
Definition 8 (Bellman Eluder (BE) dimension (Jin et al., 2021a)). Given a value function class F, let Frs fh+t1 E Fr+1) be the set of Bellman residuals induced by F at step h. and P = {Px) k= be collection of H probability measure families over X x A. The e-Bellman Eluder dimension of F with respect to defined as
Gn. (fn from H
dimpg F,P,)
max dimpe Paoe). ke(H]
We also note the following lemma that controls the rate at which Bellman error accumulates.
Lemma 16 (Lemma 41, (Jin et al., 2021a)). Given a function class G defined on a space with supyeg.zext (x())) C, and of probability measures P over X. Suppose that the sequence
29

---

Published as a conference paper at ICLR 2023
K {gk [gklk=] C and {uu] K E [K] and y > O,
C satisfy that Ei=l (Bn 19xl) s 3 for all & [K]. Then, for all
m peelll & 50 diimee(S (g. + min(k, dimpE(9,P,,)CT + kr))
We next state our main theorem whose proof is similar to that of Theorem 1.
Theorem 3 (Cumulative suboptimality). Fix E (0, 1), Moft = HT/d and Man = H2, and suppose that the underlying MDP admits Bellman eluder dimention d, and the function class F satisfies Assumption 1. Then with probability at least 1 - ó, Algorithm obtains the following bound on cumulative subpotimality w.r.. any comparator policy n²,
T V -V- WV--ve' -
=Ö(Vmax ( V dT log 1og(H1F1/8))
where x² = T is the greedy policy w.r.t. f at round t and d = dimBe Ps, 1//1//T). Here Py is the class of occupancy measures that can be be induced by greedy policies w.n. value functions F.
Proof. Repeating the analysis till (10) in the proof of Theorem
get that
T H
Σ V Vaa TC H Aot
ΣΣ
(f)(s,)) (s
Using the bound in Lemma 6 and Lemma 16 in the above, we get that
H
v* - yat STC, H A. +
dimpe(9h,)) Pr:ho (1:m:7)4m Amn
h=0
+ mi, dimpe PF )]]} Thy.
where On = = ---1i E Fh+s1+ fh+1 E F(+1) denotes the set of Bellman residuals induced by F at step h, and P (PFM)E is the collection of occupancy measures at step h induced by greedy policies max; dimpe (Gr, PF.h.)) 7). Ignoring the lower order terms, we get that
value functions in F. We set ? 1/vT and define d = dimBe
V= S TC. VH A. + H d
log (11 + HV max dT log(HT(F1/0)
TC Viax
H
Maff
Mon
where < hides lower order terms, multiplying constants and log factors. Setting moff HT and Mon H2, we get that
Σ V" -V* = =ō(c-, Vmux (oT
D COMPARISON WITH PREVIOUS WORKS
As mentioned in the main text, many previous empirical works consider combining offline expert demonstrations with online interaction (Rajeswaran et al., 2017; Hester et al., 2018; Nair et al., 2018; 2020; Vecerik al., 2017; Lee et al., 2022; Jia et al., 2022; Niu et al., 2022). Thus the idea of performing RL algorithm on both offline data (expert demonstrations) and online data is also explored in some of the previous works, for example, Vecerik et al. (2017) runs DDPG on both the online
30

---

Published as a conference paper at ICLR 2023
and expert data, and Hester et al. (2018) uses DQN on both data but with an additional supervised loss. Since we already compared with Hester et al. (2018) in the experiment, here we focus on our discussion with Vecerik et al. (2017).
We first emphasize that Vecerik et al. (2017) only focuses on expert demonstrations and their experiments entirely rely on using expert demonstrations, while we focus more general offline dataset that is not necessarily coming from experts. Said though, the DDPG-based algorithm from Vecerik al. (2017) potentially can be used when offline data is not from experts. Although the algorithm from Vecerik et al. (2017) and Hy-Q share the same high-level intuition that one should perform RL on both the datasets, there are still a few differences (1) Hy-Q uses Q-learning instead of deterministic policy gradients; note that deterministic policy gradient methods cannot be directly applied to discrete action setting; (2) Hy-Q does not require n-step TD style update, since in off- off-policy case, without proper importance weighting, n-step TD could incur strong bias. While proper tuning on n could balance bias and variance, one does not need to tune such n-step at all Hy-Q: (3) The idea of keeping non-zero ratio to sample offline dataset is also proposed in Vecerik et al. (2017). Our buffer ratio is derived from our theory analysis but meanwhile proves the advantage of the similar heuristic applied in Vecerik et al. (2017). (4) In their experiment, Vecerik et al. (2017) only considers expert demonstrations. In our experiment, we considered offline datasets with different amounts of transitions from very low-quality policies and showed Hy-Q is robust low-quality transitions in offline data. Note that some of the differences may seem minor on the implementation level, but they may be important to the theory.
Regarding the experiments, our experimental evaluation adds the following insights over those in Vecerik et al. (2017): (i) hybrid methods can succeed without expert data, (ii) hybrid methods can succeed in hard exploration discrete-action tasks, (iii) the core algorithm (Q-learning vs DDPG) is not essential although some details may matter. Due to the similarity between the two methods, we believe some of these insights may also translate to Vecerik et al. (2017) and we expect that the choice between Hy-Q and Hy-DDPG will be environment specific, as is with the purely online versions of these methods. In some situations, Q-learning works does not immediately imply Deterministic policy gradient methods work, nor vice versa. Nevertheless, it is beyond the scope of this paper to rigorously verify this claim and we deem the study of Actor-critic algorithms in Hybrid RL setting an interesting future direction.
E EXPERIMENT DETAILS
E.1 COMBINATION LOCK
In this section we provide a detailed description of combination lock experiment. The combination lock environment has horizon H and 10 actions each state. There three latent states Zi,,i E {0, 1,2] } for each timestep h, where 24,1, i E {0, 1} are good states and 22,4 is the bad state. For each good state, we randomly pick a good action di,h, such that in latent state 2,,,, E (0, 1}. taking the good action 0ghh will result in 0.5 probability of transiting to 20,4+1 and 0.5 probability of transiting to 21,++1 while taking all other actions will result in a probability of transiting to 22, At 22, all actions will result in a deterministic transition to 22, For the reward, we give an optimal reward of for landing zi i {0, 1). We also give an anti-shaped reward of 0.1 for all transitions from good state to a bad state. All other transitions have a reward of 0. The initial distribution is a uniform distribution over 20,0 and 21,0. The observation space has dimension 2 ())), created by concatenating one-hot representation of the latent state and one-hot representation of the horizon (appending 0 if necessary). Random noise from (/ 0.1) is added to each dimension, and finally the observation is multiplied by a Hadamard matrix. Note that this environment, the agent needs to perform optimally for all H timesteps to hit the final good state for an optimal reward of 1. Once the agent chooses a bad action, it will stay in the bad state until the end with at most 0.1 possible reward for the trajectory received while transitting from a good state to bad state.
E.2 IMPLEMENTATION DETAILS OF COMBINATION LOCK EXPERIMENT
We train H separate Qufuntiooss for all H timesteps. Our function class consists of an encoder and a decoder. For the encoder, we feed the observation into one linear layer with 3 outputs, followed by
31

---

Published as a conference paper at ICLR 2023
softmax layer to get reteeseeprtsnnniinnn. This design of encoder is intended learn one-hot representation of the latent state. We take Kronecker Product of the staterrepresentttion and the action, and feed the result to linear layer with only output, which will be our Q value. In order to stabilize the training, we warm-start the Q-function of timestep h - with the encoder from Q-function of the current iteration and the decoder from the h Q-function of the last iteration, for each iteration of training.
One remark is that since combination lock belongs Block MDPs, we require V-type algorithm instead of the Q-type algorithm as shown in the main text. The only difference lies in the online sampling process: instead of sampling from d% for each h, we sample from dz o Uniform(A), i.e., we first rollin with respect to n' to timestep h - 1, then take a random action, observe the transition and collect that tuple. We provide Algorithm 2 for completeness. Note that the only difference is in line 4.
For CQL, we implemented the variant of CQL-DQN and picked the peak in the learning curve to report in the main paper (so it should represent an upper bound of the performance of CQL).
E.3 IMPLEMENTATION DETAILS OF MONTEZUMA'S REVENGE EXPERIMENT
In this section we provide the detailed algorithm for the discounted setting. The overall algorithm is described in Algorithm 3. For the function approximation, networks (parameterized by class +) as promoted by the original DQN paper. We include several standard empirical design choices that have been practically proven to stabilize the training: we use Prioritize Experience Replay (Schaul et al., 2015) for our buffer. We also add Double DQN (Van Hasselt et al., 2016) and Dueling DON (Wang et al., 2016) during our Q-update. We also observe that a decaying schedule on the offline sample ratio 3 and the exploration rate also helps provide better performance. Note that an annealing /3 does not contradict to our comment in Section on catastrophic forgetting because In addition, we also perform per step update instead of per episode update since this has been the popular design choice and leads to better efficiency in practice.
a class of convolutional neural
set 3 to small after our online trajectory distribution covers d"
E.4 BASELINE IMPLEMENTATION
E.4.1 COMBINATION LOCK
We use the open-sourced implementation ttttps:/ggttie wtt.B///////////teeeeeteeeee COL-DQN for CQL. For BRIBE, we use the official code released by the authors: https: github. com/ rrddasong/brien where we rely on the code there for the combination lock environment.
E.4.2 MONTEZUMA'S REVENGE
We use the open-sourced implementation bttps://qithis ctt. jewle// lotiooopootto for RND. For CQL., /d3 for their implementation of CQL. for atari. We use https://githut. con/ felix-kerkhof//Doe hyperparameters used in these public repositories. For CQL and DQFD, we provide the offline datasets as described in the main text instead of using the offline dataset provided in the public repositories.' All baselines are tested in the same stochastic environment setup as in Burda et al. (2018).
https:
for DQFD, For all basclines, we keep the
F.5 HARDWARE INFRASTRECTURE
We run our experiments on a cluster of computes with Nvidia RTX 3090 GPUs and various CPUs which do not incur any randomness to the results.
We note that CoL. also fails completely with the original offlie dataset (with 1 million samples) provided in the public repository.
32

---

Published as a conference paper at ICLR 2023
Algorithm 3 Discounted Hy-Q
Require:
Value function class: F (induced by O), #iterations: T, Offline dataset D of size ooffs discounted factor 7, target update frequency Vtargetss learning rate a, offline sample ratio B, exploration rate e, action space A.
1: Randomly initialize value function fa) fo.
2: Initialize target value function
3: Initialize online buffer D (1.
4: Sample initial state s ~ du
5: for / ..... do
6: Let π be the e-greedy policy w.r.t. f i.e. (8)) = argmax, (s, with probability 1 -
and iT(s) ((AA with probability
// Online collection
7:
Interact with the environment for step:
(T). = P(s.a), R(x,a).
8:
Update online buffer: D (s,
// Discounted minibatch FQI using both online and offline data
9:
if mod Ylyalue then With probability 1 - 3: Sample a minibatch D with size Mminibatch from online buffer D. Otherwise: Sample minibatch D with size Aminibathh from offline buffer D
10:
11:
Perform one-step gradient descent on D:
0 = --o (f - - max f(s',
a
12:
end if
// Delayed update of target function every Yitarg updates
13:
it' mod Tlarget = then
14: Set target function to the current value function: f= f".
end if
16: Update 8 6-8'. 8'.
end for
E.6 HYPERPARAMETERS
E. COMBINATION LOCK
We provide the hyperparameters of Hy-Q Table. In addition, we provide the hyperparameters we tried for CQL baseline in Table. 2.
Table I: Hyperparameters for Hy-Q in combination lock
Value Considered
Final Value
Learning rate
(1e-2, 2e-2, le-3)
2e-2
Buffer size Optimizer
{1e8}
le8
(Adam, SGD)
Adam
Number of updates per iteration Batch size
(30, 300, 500) [512)
500
512
E.6.2 MONTEZUMA'S REVENGE
We provide the hyperparameter of Hy-Q in Table. 3. We reuse many hyperparameter choices from DQFD. Note that (a, b) denotes decreasing/increasing schedule from a
33

---

Published as a conference paper at ICLR 2023
Table 2: Hyperparameters for CQL(DQN) in combination lock
Value Considered
Final Value
Learning rate
{le-3}
le-3
Optimizer
[Adam]
Adam
Buffer size
{1e8}
1e8
Batch size
{512]
512
Discount Factor
{0.99)
0.99
Moving Average Factor
{0.01, 0.1,
0.01
Weight on CQL loss a
(0, 0.01)
0.1
Table 3: Hyperparameter of Discounted Hy-Q in Montezuma's 's Revenge.
Value Considered
Final Value
Learning rate Offline Schedule 3 Exploration rate
(6,25e-5, (0.5.0.2.(0.2.00011))
[1e-4,
[0.2.0.01]
[10.25,00001]]
[0.25,0.001]
Minibatch size mmminibaich
{32}
32
Weight decay (regularization) coefficient Gradient Clipping
{le-5]
le-5
(10,20)
10
Discount factor
{0.99)
0.99
Value function update frequency Taapdate
{4)
4
Target function update frequency Tharget
(1000.2000,5000,1000
10000
Buffer size
{220)
220
PER Importance Sampling ratio
{[0.6.
[0.6.1]
Online PER
{0.001}
0.001
Offline PER
{0.0001}
0.0001
Online PER Priority Coefficient
{0.4)
0.4
Offline PER Priority Coefficient
(1)
34


Reviews:
[{"review_id": "yEFH8y2QN", "reviewer": "Reviewer_SJM5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a simple hybrid offline-online RL algorithm, and provides an extensive theoretical analysis to showcase its properties. The proposes algorithm is compared with baseline algorithms that fall into the categories of online, offline and hybrid RL, as well as \"learning by imitation\", in the \"combination lock\" and \"Montezuma's revenge\" problems.", "summary_of_the_review": "The paper proposes a simple hybrid offline-online RL algorithm, it provides an extensive  analysis to showcase its properties and a comparison with other RL algorithms in two problems. I suggest to improve the experimental part and to provide more extensive experiments in more challenging problems, as well as a deeper analysis of the obtained results.", "strength_and_weaknesses": "Strengths\n- The paper is well-written and the references appropriate.\n- The proposed hybrid offline-online RL algorithm is simple and effective, and an extensive theoretical analysis of its properties is provided.\n\nWeaknesses\n- The comparison with other algorithms is weak. Just two simple problems are used, and the experiments could better analyze the reason of the different performance of the compared algorithms.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QOIUyA3zUr", "reviewer": "Reviewer_bRLc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new method to run fitted Q learning on both online and offline data. Theoretical analysis is provided under several assumptions and empirical improvements over certain baselines are observed on certain tasks.", "summary_of_the_review": "See above\n\n==========================================\nThe revision cleared my major concern in credit assignment so I raised score accordingly.", "strength_and_weaknesses": "Strength: the theoretical analysis seems novel and the paper is easy to follow\n\nWeaknesses: \n1. The authors failed to properly place the algorithmic contribution in the literature. For Algorithm 1, I feel the idea is basically to fix the demonstration / offline data in experience replay and run some RL algorithm (e.g., FQI). This feeling is especially true when it is actually implemented with a discounted factor using a target network. This idea is not new, see, e.g., [x][y]. The authors failed to explicitly acknowledge the similarity between Algorithm 1 and existing works. The way to control catastrophic forgetting mentioned in Section 4 is also already done by [y] and the authors failed to acknowledge.\n2.  As a result of (1), the main contribution is the theoretical analysis. So I must hold a higher standard when evaluating the contribution of the theoretical analysis. I, however, believe that Assumption 1 is way too strong. Can the author actually give a concrete meaningful example beyond the tabular setting where this assumption holds?\n3. The selection of baselines is improper. The only baseline that is designed for both online and offline data is DQFD (Hester et al., 2018). However, it looks DQFD does imitation learning instead of RL for offline data. I believe using baselines methods that do RL for both online and offline data is more proper and more informative. In particular, the authors should compare with [x] and [y]. And **what is the fundamental difference between the algorithm that the authors actually implemented and [y]? The authors are using DQN and [y] uses DDPG. Other than this, I cannot see any major difference.** I feel the paper is quite far from making the following claim [z]\n4. The domains for comparison can be much improved. For now the two domains are quite similar and requires guided exploration. I agree this is an important area of RL but considering only such areas is not enough to support the claim [z]. I think the authors should also compare in the settings where the reward is not so sparse. The authors should also consider offline dataset of different quality. D4RL seems to be a good complementary benchmarks. Otherwise the authors should consider tone down their claims.\n\n[x] Lee, Seunghyun, et al. \"Offline-to-online reinforcement learning via balanced replay and pessimistic q-ensemble.\" Conference on Robot Learning. PMLR, 2022.  \n[y] Vecerik, Mel, et al. \"Leveraging demonstrations for deep reinforcement learning on robotics problems with sparse rewards.\" arXiv preprint arXiv:1707.08817 (2017).  \n[z] On the empirical side, several works consider combining offline expert demonstrations with online interaction (Rajeswaran et al., 2017; Hester et al., 2018; Nair et al., 2018; 2020; Vecerik et al., 2017). In our experiments, we find that these methods perform poorly when the offline dataset also contains experience from low-quality policies, while our method is robust to the quality of the offline data.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8Iu4HGlTC9d", "reviewer": "Reviewer_WaHo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper presents Hybrid Q-Learning (Hy-Q), an algorithm for a hybrid RL setting, where the agent has both offline datasets and can interact with the environment in an online manner. Hy-Q learns a value function by fitted-Q iteration on both the offline dataset and the online experiences, where the online samples are collected by the greedy policy w.r.t. the learned value function. Theoretical analysis for the sample complexity of Hy-Q is provided. In addition, in the case of the linear Bellman completeness model, it can be shown that Hy-Q is a computationally efficient algorithm, which is in contrast to the existing methods that require solving NP-hard problems. In the experiments, Hy-Q outperforms both pure online and pure offline RL algorithms in Combination Lock and Montezuma's Revenge.\n", "summary_of_the_review": "The paper presents a simple yet provably efficient algorithm for hybrid RL with theoretical guarantees, which I think is a novel and nice contribution. Still, in the experiments, comparisons with baseline algorithms that use both offline and online experiences are missing.\nLastly, one thing unclear to me was that Hy-Q uses a greedy policy for online data collection, but it can always learn a near-optimal policy without falling into some local optima, which is counterintuitive. I would like to raise my score if those concerns are addressed.\n== post-rebuttal\nThanks for your clarifications, which addressed most of my concerns. I raise my score accordingly.", "strength_and_weaknesses": "[Strengths]\n1. The paper presents a principled hybrid RL algorithm, which is supported by theoretical guarantees.\n2. The algorithm is simple to implement and computationally efficient.\n3. Experimental results show that the proposed Hy-Q outperforms online/offline baseline algorithms.\n\n\n[Weaknesses]\n1. It would be great to compare with more baseline algorithms that deal with both offline datasets and online experiences in the experiments, e.g. [1,2,3]\n2. Page 4: There exists a gap between theory and practical implementation, i.e. using a fixed proportion of offline samples rather than forgetting them gradually, but I think this is minor.\n3. Some notations are used without explicit definitions/explanations. What is $m_{off}$ and $m_{on}$ in Theorem 1? Also, they do not appear in the statement.\n\n\n[Questions]\n1. In the case of using flexible function approximators such as neural networks, is $C_\\pi$ bounded?\n2. Can Hy-Q be extended to continuous action spaces?\n3. In Algorithm 1, the proportion of the offline dataset would decrease as the number of online samples increases. I am curious about the performance of this forgetting algorithm, rather than using a fixed proportion of offline samples.\n4. I was wondering if the combination of Hy-Q and exploration strategy (e.g. RND) can improve or degrade the performance in the experiments.\n5. The theoretical result was somewhat counter-intuitive to me. Hy-Q collects online samples via a 'greedy' policy w.r.t the learned value function; thus there is no exploration mechanism in the algorithm. Suppose an offline dataset was collected by a poor agent. Then, intuitively, exploitation alone w.r.t. the learned value function may be prone to get stuck in local optima and thus unable to learn a near-optimal policy. However, Corollary 1 is saying that Hy-Q can always learn a (near-)optimal policy with a sufficiently large number of samples. It would be great to provide some intuitive explanation about how 'greedy' data collection can always yield a near-optimal policy.\n\n\n[1] Nair et al., AWAC: Accelerating Online Reinforcement Learning with Offline Datasets, 2020\n\n[2] Lee et al., Offline-to-Online Reinforcement Learning via Balanced Replay and Pessimistic Q-Ensemble, 2021\n\n[3] Xie et al., Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning, 2022\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3OhWr6rV5PY", "reviewer": "Reviewer_mmKF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper considers hybrid reinforcement learning, which is a setting where both offline data and online data are available. The paper proposes a corresponding algorithm to be computation-efficient and sample-efficient under such a setting. The theoretical sample complexity upper bound shows both the characteristics of offline and online RL. The paper also provides experiments result to show the strength of the proposed algorithm.", "summary_of_the_review": "The paper provides solid analysis of a novel RL algorithm in a less studied setting, in both theories and experiments. However, the contribution of the result seems not very clear, and thus I believe the paper is a little below the acceptance threshold. If the authors can well settle the concerns stated above, I may raise my score.", "strength_and_weaknesses": "Strength: The paper considers a less studied setting and provides complete theoretical analysis of the proposed algorithm. The theoretical bound seems to have the optimal rate.\n\nWeakness: The motivation of the hybrid RL setting is not very clear to me. In particular, the introduction part says that, to overcome the issue of sample inefficiency (of online RL), attention has turned to the offline RL setting. However, the information of each data point in online RL is surely much more than that of offline RL. Given the same sample size, we should always choose online RL over offline RL. The only setting that I can imagine that hybrid RL is useful is that there is already an offline dataset and we do not want to waste the data.\n\nAs for the theory part, similar confusion remains: the result in Theorem 1 seems similar to the convergence of offline RL, as it still requires the offline data set to have a good coverage condition number $C_{\\pi}$. it is also not clear how the result is better than online RL (e.g., Du et al 2021). I am also wonder if using pessimism or optimism (from usual offline and online RL algorithms) in the hybrid RL algorithm is helpful to improve the sample efficiency. Or if the algorithm deliberately choose not to use them to reduce the computation cost.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster