Harnessing Density Ratios for Online Reinforcement Learning
Authors: Philip Amortila
Dylan J Foster
Nan Jiang
Ayush Sekhari
Tengyang Xie
Venue: ICLR 2024 spotlight (2024)
Keywords: reinforcement learning theory
online RL
offline RL
hybrid RL
density ratio
marginalized importance weight
weight function
general function approximation
Primary area: learning theory
TL;DR: The notion of density ratio modeling, an emerging topic in offline RL, has been largely absent from online RL. We show a perhaps surprising result, that density ratio-based algorithms have online counterparts.

Abstract: The theories of offline and online reinforcement learning, despite having evolved in parallel, have begun to show signs of the possibility for a unification, with algorithms and analysis techniques for one setting often having natural counterparts in the other. However, the notion of *density ratio modeling*, an emerging paradigm in offline RL, has been largely absent from online RL, perhaps for good reason: the very existence and boundedness of density ratios relies on access to an exploratory dataset with good coverage, but the core challenge in online RL is to collect such a dataset without having one to start.

In this work we show---perhaps surprisingly---that density ratio-based algorithms have online counterparts.  Assuming only the existence of an exploratory distribution with good coverage, a structural condition known as *coverability* (Xie et al., 2023), we give a new algorithm (GLOW) that uses density ratio realizability and value function realizability to perform sample-efficient online exploration. GLOW addresses unbounded density ratios via careful use of truncation, and combines this with optimism to guide exploration. GLOW is computationally inefficient; we complement it with a more efficient counterpart, HyGLOW, for the Hybrid RL setting (Song et al., 2023) wherein online RL is augmented with additional offline data. HyGLOW is derived as a special case of a more general meta-algorithm that provides a provable black-box reduction from hybrid RL to offline RL, which may be of independent interest.

Published as a conference paper at ICLR 2024
HARNESSING DENSITY RATIOS FOR ONLINE REINFOR LEARNING
Philip Amortila'
Dylan J. Foster
Nan Jiang UICC
Ayush Sekhari MIT
Tengyang Xie Microsoft Research
UIUC
Microsoft Research
ABSTRACT
The theories of offline and online reinforcement learning, despite having evolved in parallel, have begun to show signs of the possibility for a unification, with algorithms and analysis techniques for one setting often having natural counterparts in the other. However, the notion of density rafio modeling, an emerging paradigm in offline RI. has been largely absent from online RI., perhaps for good reason: the very existence and boundedness of density ratios relies on access an exploratory dataset with good coverage, but the core challenge in online RL to collect such a dataset without having one to start.
In this work we show-perhaps surprisingly-thane density ratio-based algorithms have online counterparts. Assuming only the existence of an exploratory distribu- tion with good coverage, a structural condition known as coverability (Xie et al., 2023), we give a new algorithm (GLOW) that uses density ratio realizability and value function realizability to perform sample-efficient online exploration. GL.ow addresses unbounded density ratios via careful use of truncation, and combines this with optimism to guide exploration. GLOW is computationally inefficient; we complement it with more efficient counterpart, HYGLOW, for the Hybrid RL setting (Song et al., 2023) wherein online RL is augmented with additional offline data. HyGLOw is derived as a special case a more general meta-al meea--lgorithm that provides provable black-box reduction from hybrid RL to offline RL., which may be of independent interest.
INTRODUCTION
fundamental problem in reinforcement learning (RL) is to understand what modeling assumptions and algorithmic principles lead to sample-efficient learning guarantees. Investigation into algorithms for sample-efficient reinforcement learning has primarily focused on two separate formulations: Offline reinforcement learning, where learner must optimize a policy from logged transitions and rewards, and online reinforcement learning, where the learner can gather new data by interacting with the environment; both formulations share the common goal of learning a near-optimal policy. For the most part, the bodies of research on offline and online reinforcement have evolved in parallel, but they exhibit a number of curious similarities. Algorithmically, many design principles for offline RL (e.g., pessimism) have online counterparts (e.g., optimism). and statistically efficient algorithms for both frameworks typically require similar representution conditions (e.g.. ability to model state- action value functions). Yet, the frameworks have notable differences: online RL algorithms require exploration conditions to address the issue of distribution shift (Russo and Van Roy, 2013; Jiang et al., 2017; Sun et al., 2019; Wang et al., 2020c; Du et al., 2021; Jin et al., 2021a; la; Foster et al., 2021). while offline RI. algorithms require conceptually distinct coverage conditions to ensure the data logging distribution sufficienlly covers the state space (Munos, 2003; Antos et al., 2008; Chen and Jiang, 2019; Xie and Jiang, 2020, 2021; Jin et al., 2021b; Rashidinejad et al., 2021; Foster et al., 2022; Zhan al., 2022).
Recently, Xie et al. (2023) exposed deeper connection between online and offline RL by showing that coverability-
is, existence of a data distribution with good coverage for offline RI.-is itself sufficient condition that enables sample-efficient exploration in online RI., even when the learner has no prior knowledge of said distribution. This suggests the possibility of a theoretical unification of online and offline RL, but the picture remains incomplete, and there are many gaps
Authorrs listed in alphahetical order. Full version appears LrXXv:2400.00968

---

Published as a conference paper at ICLR 2024
in understanding. Notably, a promising emerging paradigm in offline RL makes use of the ability to model density ratios (also referred to as marginalized importance weights or simply weighr functions) for the underlying MDP. Density ratio modeling offers an altermative to classical value function approximation (or, approximate dynamic programming) methods (Munos, 2007; Munos and Szepesvári, 2008; Chen and Jiang. 2019), it avoids instability and typically succeeds under weaker representation conditions (requiring only realizability conditions as opposed to Bellman completeness-type assumptions). Yet despite extensive investigation into density ratio methods for offline RL-both in theory (Liu et al., 2018: Uehara et al., 2020; Yang et al., 2020; Uehara et al., 2021; Jiang and Huang, 2020: Xie and Jiang. 2020; Zhan al., 2022; Chen and Jiang. 2022; Rashidinejad et al., 2023; Ozdaglar et al., 2023) and practice (Nachum et al., 2019; Kostrikov et al., 2019; Nachum and Dai, 2020; Zhang et al., 2020; Lee et al., density ratio modeling has been conspicuously absent in the online reinforcement learning. This leads us to ask:
Can online reinforcement learning from the ability to model density ratios?
Adapting density ratio-based methods to the online setting with provable guarantees presents number of conceptual and technical challenges. First, since the data distribution in online RL is constantly changing, it is unclear what densities one should even attempt to model. Second, most offline reinforcement learning algorithms require relatively stringent notions of coverage for the data distribution. In online RI,, it is unreasonable expect data gathered early in the learning process to have good coverage, and naive algorithms may cycle or fail to explore as a result. As such, it may not be reasonable to expect density ratio modeling to benefit online RL in the same fashion as offline.
Our contributions. We show that in spite of these challenges, density ratio modeling enables guarantees for online reinforcement learning that were previously out of reach.
Density ratios for online RL. We show (Section 3) that for any MDP with low coverability, density ratio realizability and realizability of the optimal state-action value function are sufficient for sample-efficient online RL. This result is obtained through new algorithm, GI.Ow, which ad- dresses the issue of distribution shift via careful use of truncated density ratios, which it combines with optimism to drive exploration. This complements Xie et al. (2023), who gave guarantees for coverable MDPs under a stronger Bellman completeness assumption for the value function class.
Density ratios for hybrid RL. Our algorithm for online RL is computationally inefficient. We complement it (Section 4) with a more efficient counterpart, HYGLOW, for the hybrid RI. framework (Song et al., 2023), where the learner has access to additional offiine data that covers a high-quality policy.
Hybrid-to-offline reductions. To achieve the result above, we investigate a broader question: when can offline RL algorithms be adapted as-is to online settings? We provide a new meta-algorithm, H2O, which reduces hybrid RL to offline RL by repeatedly calling a given offline RL algorithm as a black box. We show that H₂O enjoys low regret whenever the black-bor -bx offline algorithm satisfies certain conditions, and demonstrate that these conditions are satisfied by a range of existing offline algorithms, thus lifting them to the hybrid RL setting.
While our results are theoretical in nature, we are optimistic that they will lead to further investigation into the power of density ratio modeling in online RL and inspire practical algorithms.
1.1 PRELIMINARIES
Markov Decision Processes. We consider an episodic reinforcement learning setting. A Markov De- cision Process (MDP) is a tuple M = (X, A. P. R, H, dj), where X' is the (large/potentially infinite) state space, A is the action space, /l E N is the horizon, R {Rr is the reward function (where Rg : X x A - ([0,, 1))) P = [Pr and d1 is the initial state distribution. A randomized policy is sequence of functions π {Ti | When a policy is executed, it generates a trajectory (I1, d1.r1),......................... (Z aH rh) via the process (4 ~ T (xx),, Th (N,,,, ap) ), rh41 Pr (x az), initialized at x1 di (we use + to denote a deterministic terminal state with zero reward). We write [' and [*[.] to denote the law and corresponding expectation for the trajectory under this process.
is the transition distribution (where PA : X x A - A(Y)),
X + ((A)) -
For policy म, the expected reward for is given by J(m) = E [i ra]. , and the value functions
given by V) == E" |' TM x = =r), and (T a) = E [> = Th Ih = x,, ax a] We write x² {mt] k to denote an optimal deterministic policy, which maximizes 4 at all
2

---

Published as a conference paper at ICLR 2024
states. We let Ta denote the Bellman (optimality) operator for layer h, defined via [Tnf]xx, [rr + max,' (1 a') T4 x. an = a] for f x A I.
Online RL. In the online reinforcement learning framework, the learner repeatedly interacts with an unknown MDP by executing policy and observing the resulting trajectory. The goal is to maximize total reward. Formally, the protocol proceeds N rounds, where at each round & E [N], the learner selects policy T {TT Jh=1 in the (unknown) underlying MDP M* and observes the trajectory {[a]" 0% : .h
Our results most naturally stated in terms of PAC guarantees. Here, after the N rounds of interaction conclude, the learner can use all of the data collected to produce a final policy म, with the goal of minimizing
/= )))))
Risk == [
(1)
where p E (II) denotes a distribution that the algorithm can use to randomize the final policy.
Additional definitions and assumptions. We assume that rewards are normalized such that Dh=1 Th [0, 1] almost surely for all trajectories (Jiang and Agarwal, 2018; Wang et al., 2020a; Zhang et al., 2021; Jin et al.. a). To simplify presentation, we assume that X' and A are countable; we expect that our results extend to handle continuous variables with an appropriate measure-theoretic treatment. We define the occupancy measure for policy π via dz (z, a) = P [IA = I, ag = a].
2 PROBLEM SETUP: DENSITY RATIO MODELING AND COVERABILITY
To investigate the power of density ratio modeling in online RL, we make use of function approx- imation, and aim to provide sample complexity guarantees with explicit dependence on the size of the state space. We begin by appealing to value function approximation, standard ap- proach in online and offline reinforcement learning, and assume access to value-function class F C (X x A x [H] - [0, 1J) that can realize the optimal value function Q*
Assumption 2.1 (Value function realizability). We have Q' E F.
For F, we define the greedy policy Ty via ( = arg max, fn (z. a), with ties broken in an arbitrary consistent fashion. For the remainder of the paper, we define II {Λf f F} as the policy class induced by F, unless otherwise specified.
Density ratio modeling. While value function approximation is a natural modeling approach, prior works in both online (Du et al., 2020; Weisz et al., 2021; Wang et al., 2021) 1) and offline RI. (Wang et al., 2020b; Zanette, 2021; Foster et al., 2022) have shown that value function realizability alone is not sufficient for statistically tractable learning in many settings. As such, value function approximation methods in online (Zanette et al., 2020; Jin et al., 2021a; Xic et al., 2023) and offline RL (Antos et al., 2008; Chen and Jiang, 2019) typically require additional representation conditions that may not be satisfied in practice, such as the stringent Bellman completeness assumption (i.e., Tr.F++1 S Fi))
In offline RL, promising emerging paradigm that goes beyond pure value function approximation is to model density ratios (or, marginalized important weights), which typically take the form di (2..0)//a. for policy æ, where j4, denotes the offline data distribution." A recent line of work (Xie and Jiang, 2020; Jiang and Huang. 2020; Zhan et al., 2022) shows, that given access to a realizable value function class and weight function class W that can realize the ratio di/uz (typically either for all policies π, or for the optimal policy T²), one can learn a near-optimal policy offline in sample-efficien efficiien fashion; such results sidestep the need for stringent value function representation conditions like Bellman completeness. To explore whether density ratio modeling has similar benefits in online RL, we make the following assumption.
Assumption 2.2 (Density ratio realizability). The learner has access to weight function class W C (X A [H] - R24) such that for any policy pair n, x' E II, and h E [H). we have w/p म.म (z, a) = d[ (f.,))/ay (s.a) E Wn.
Assumption 2.2 does not assume that the density ratios under consideration are finite. That is, we do not assume boundedness of the weights, and our results do not pay for their range; our algorithm will only access certain clipped versions of the weight functions (Remark B.
Formally, offiine reinforcement learning the learner does not interact with M but is given a dataset of tuples (Ih, ab, Th 1 collected i.i.d. according to (z)) ~ pha Th ~ R2 (2h, ok), Th+1 ~ Pa (2 ax). We adopt the convention that s/o- +oo when > 0 and %/- 1.
3

---

Published as a conference paper at ICLR 2024
Compared to density ratio approaches in the offline setting, which typically require either realizabilitty of 4i/pn for all II or realizability of dī /pn. where μu is the offline data distribution, require realizability of 62/45 for all pairs of policies n. E IT. This assumption is natural because facilitates transfer between historical data (which is algorihnn-depeneen and future policies. We refer the reader to Appendix B for a detailed comparison to alternative assumptions.
Coverability. In addition to realizability assumptions, online RL methods require exploration conditions (Russo and Van Roy, 2013; Jiang et al., 2017; Sun et al., 2019; Wang et al., 2020c; Du ct al., 2021; Jin et al., 202 la; Foster et al., 2021) that allow deliberately designed algorithms to control distribution shift or extrapolate unseen states. Towards lifting density ratio modeling from offline to online RL,, we make use of coverability (Xie et al., 2023), an exploration condition inspired by the notion of coverage in the offline setting.
Definition 2.1 (Coverability coefficient (Xie et al., 2023)). The coverability coefficient Ccov > for a policy class 1I given by Coov == inf (A(Xxx.)) suPren.he(tt) 110%/uxll We refer to the distribution μú that attains the minimum for ht as the coverability distribution.
Coverability is a structural property of the underlying MDP, and can be interpreted as the best value one can achieve for the concentrability coefficient (c) == supren,ee|sr |/4 1/ lloo (a standard coverage parameter in offline RI. (Munos, 2007; Munos and Szepesvári, 2008; Chen and Jiang, 2019)) by optimally designing the offline data distribution μ.. However, in our setting the agent has no prior knowledge of μ² and no way to explicitly search for it. Examples that admit low coverability include tabular MDPs and Block MDPs (Xie et al., 2023), linear/low-rank MDPs (Huang et al., 2023), and analytically sparse low-rank MDPs (Golowich et al., 2023); see Appendix C for further examples.
Concretely, we aim for sample complexity guarantees scaling as poly (H, Ceov, Fl, log W|, where is the desired bound on the risk in Eq. (1).² Such guarantee complements Xie et al. (2023), who achieved similar sample complexity under the Bellman completeness assumption, and parallels the fashion in which density ratio modeling allows one to remove completeness in offline RL.
Additional notation. For n E N, we write [nx] = (1,...,,n) n). For a countable set Z, we write A(2) Z. We adopt standard big-oh notation, and use Ö(-) and Ω?(-) to suppress factors polylogarithmic in H, T, E logg Fl. log W), and other problem parameters. For each h E [H], we define Fr, {fr f E F} and Wn {wn, W}.
for the set of probability distributions
3 ONLINE RL WITH DENSITY RATIO REALIZABILITY
This section presents our main results for the online RL setting. We first introduce our main algorithm, GLOW (Algorithm 1), and explain the intuition behind its design (Section 3.1). We then show (Section 3.2) that GL.WW obtains polynomial sample complexity guarantees (Theorems 3.1 and 3.2) under density ratio realizability and coverability, and conclude with a proof sketch.
3.1 ALGORITHM AND KEY IDEAS
Our algorithm, GLOW (Algorithm 1). is based on the principle of optimism in the face of uncertainty. For each iteration < E N. the algorithm uses the density ratio class W to construct confidence set (or, version space) Fr C F with the property that Q* E FRO, It then chooses a policy (( = fto based on the value function f E F with the most optimistic estimate E[f1 (æ1, T (x:))) for the initial value. Then, uses the policy l(*) to gather K E N trajectories, which are used to update the confidence set for subsequent iterations.
Within the scheme above, the main novelty to our approach lies in the confidence set construction. GLOW appeals global optimism (Jiang et al., 2017: Zanette et al., 2020; Du al., 2021; Jin et al., 2021a; Xie et al., 2023), and constructs the confidence set F by searching for value functions f F that satisfy certain Bellman residual constraints for all layers h E [H] simultaneously. For MDPs with low coverability, previous such approaches (Jin et al., 2021a; Xie et al., 2023) make use of constraints based on squared Bellman error, which requires Bellman completeness. The confidence set construction in GL.OW (Eq. (3)) departs from this approach, and aims to find f E F such that the
'To simplify presentation as much as possible, we assume finiteness of F and W. but our results extend to infinite classes via standard uniform convergence arguments. Likewise, we do not require exact realizability, and an extension to misspecified classes given in Appendix E.
4

---

Published as a conference paper at ICLR 2024
average Bellman error is small for all weight functions. At the population level, this (informally) corresponds to requiring that for all h E [H] and w E W.
(2) where // - Eies dh is the historical data distribution and at and ( are algorithm parameters; this is motivated by the fact that the optimal value function satisfies ET (w (Q7 (Ih, mn) [T (Ih, ax))] = for all functions w and policies л. Our analysis uses that Eq. (2) holds for the weight function wo := -;,") / which allows to transfer bounds on the off-policy Bellman error for the historical distribution d(t) to the on-policy Bellman error for T(
E [wn (T an (n) (In, ap)) (Tnfn+il(aa an))] - a Ego [[w (3n, an)) g
Remark 3.1. Among density ratio-based algorithms for offline reinforcement learning (Jiang and Huang, 2020; Xie and Jiang, 2020; Zhan et al., 2022; Chen and Jiang, 2022; Rashidinejad et al., 2023), the constraint (2) is most directly inspired by the Minimax Average Bellman Optimization (MABO) algorithm (Xie and Jiang, 2020), which uses similar minimax approximation to the average Bellman error.
Partial coverage and clipping. Compared to the offiine setting, much extra work is required to handle the issue of partial coverage. Early in the learning process, the ratio w := dz." "a may be unbounded, which prevents the naive empirical approximation to Eq. (2) from concentrating. To address this issue, GLOW carefully truncates the weight functions under consideration.
Definition 3.1 (Clipping operator). For any w X A - I U (00) and y R, we define the clipped weight function (at scale -y) via clip,,[uo(<r a) = min(w((, 7}
We replace the weight functions in Eq. (2) with clipped counterparts clip.,ro [w] a). where y(()) := 7 t for a parameter " E [o, 1]. For a given iteration f, clipping in this fashion may render Eq. (2) a poor approximation to the on-policy Bellman error. The crux of our analysis is to show-via via coverability- on average across all iterations, the approximation error small.
An important difference relative to MABO is that the weighted Bellman eπror in Eq. (2) incorporates quadratic penalty " IEgo [(wr an))²) for the weight function. This is not essential to derive polynomial sample complexity guarantees, but is critical to attain the 1/c2-type rates we achieve under our strongest realizability assumption. Briefly, regularization is beneficial because it allows us appeal to variance-depender Bernstein-style concentration; our analysis shows that while the variance of the weight functions under consideration may not be small on per-iteration basis, it small on average across all iterations (again, via coverability). Interestingly, similar quadratic penalties have been used within empirical offline RL algorithms based on density ratio modeling (Yang et al., 2020; Lee et al., 2021), as well as recent theoretical results (Zhan et al., 2022), but for considerations seemingly unrelated to concentration.
3.2 MAIN RESULT: SAMPLE COMPLEXITY BOUND FOR GLOW
We now present the main sample complexity guarantees for GLOW. The first result we present, which gives the tightest sample complexity bound, is stated under form of density ratio realizability that strengthens Assumption 2.2. Concretely, we assume that the class W can realize density ratios for certain mixtures of policies. For E N, we write ((i:t) as a shorthand for a sequence (IT(1) .r(",,.". , (.), where (() E II, and let (1 := + E dr(0
Assumption 2.2' (Density ratio realizability, mixture version). Let T be the parameter GLOW (Algorithm 1), For all h E [H], π E 11, 1 < T, and (")) ,(..,,(1)) E II, we have
प: (1:4) (x,a)== wh
(2, E.
d. (1))) (x.
This assumption directly facilitates transfer from the algorithm's historical distribution di = Under Assumption 2.2', GLOW obtains 1/eaPAAC sample
E Eier dz to on-policy error.
complexity and VT-regret.
'Aeraage Bellman error without weight functions is used in algorithms such at OLIVE (Jiang et al., 2017) and BIC Du et al. (2021). Without weighting, this approach is insufficient to derive guarantees based on coverability; see discussion in Xie et al. (2023).
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 GLOW: Global Optimism via Weight Function Realizability
input: Value function class F, Weight function class W, Parameters T, K.KEN, [0, 1/.
3.1, T 6((HHP A) log( (e)))) K = 1, and 7= /Coou/ (WV1))) 2: For Thm. 3.2, set T= S(o// K G(T log(l? (w1))) and == foun/T.
1: For
3: Set Se0 =y t, a = =8/-(0) and gth) (30x /K(-1)) log( 1og(s)7/IW(T///))
4: Initialize 1/ = Ø for all h < H.
5: for 1. ....., T do
6: Define confidence set based on (regularized) minimax average Bellman emror:
F { SEFIVE: WEW,,
Eago [(S, (n(2,)) - ( s 800)
( (2)
sup
(3)
where w := ces [w]] and [a, a, r. r/) (n(2,,) maxa' (n+1(2',0) ,1))
7:
Compute optimistic value function and policy:
f = arg max SAND (1((,, and x= = y(() )EF()
(4)
8: Initialize ((++1) + Dha for h E [H].
9: for k: = 1,...,K K do
Online data collection.
10: Collect a trajectory (I1, 01 ri),... (HH, on, rH) by executing 7
Update ( + Di U ((Eb: 0b, Ths #b+1)} for each h [M].
12:
output: policy गे = Uni (..))
// For PAC guarantee only.
Theorem 3.1 (Risk bound for GL.WW under strong density ratio realizability). Let > 0 be given, and
suppose that Assumptions 2. and 2.2' hold. Then, GLOW, with hyperparameters T = ( (I(c)))))) log((F/1w1//)). K 1, and 7 (Com/(T log(1z1119/4) returns an E-suboptimal policy â with probability at least 8 after collecting
Ml log((1)1)1/))
N Ō (
(5)
trajectories. Additionally, for any T E N. with the same choice for K and yy above, GLOW enjoys the regret bound Reg = Ei= -(()- Ö(H /CouT (ogoTTolll//iii
Next, we provide our main result, which gives a sample complexity guarantee under density ratio realizability for pure policies (Assumption 2.2). To obtain the result, we begin with class W that satisfies Assumption 2.2, then expand it to obtain an augmented class W that satisfies mixture realizability (Assumption 2.2'). This reduction increases Wo by a factor, which we offset by increasing the batch size ; this leads to polynomial increase in sample complexity."
Theorem 3.2 (Risk bound for GLOW under weak density ratio realizability). Let E > 0 be given, and suppose that Assumptions 2. I and 2.2 hold for the classes F. and W. Then, GL.Ow, when executed with modified class W defined in Eq. (30) in Appendix E, with hyperparameters T = ((1(Cm=/ K (I log( ())()))))))) and y / Ccm//,, returns an e-suboptimal policy â with probability at least 1 - 8 after collecting N trajectories, for
Ō
cov log(( e
(6)
Theorems 3.1 and 3.2 show for the first time that value function realizability and density ratio realizability alone are sufficient for sample-efficient online RL under coverability. In particular, the sample complexity and regret bound in Theorem 3.1 match the coverability- based guarantees obtained in Xie et al. (2023, Theorem 1) under the complementary Bellman completeness assumption, with the only difference being that they scale with log(IFF[[)) instead of log Fl; as discussed in
'This reduction also prevents us from obtaining a regret bound directly under Assumption 2.2, though a (slower-than-ye /T) regret bound he attained using an explore-then-commi strategy.

---

Published as a conference paper at ICLR 2024
Xie et al. (2023), this rate is tight for the special case of contextual bandits (H 1). Interesting open questions include (i) whether the sample complexity for learning with density ratio realizability for pure policies can be improved to 1/2², and (ii) whether value realizability and coverability alone are sufficient for sample-efficient RI.. Extensions to Theorems 3.1 and 3.2 under misspecification are given in Appendix E; see also Remark B.1 We further refer to Appendix C for examples instantiating these results, Appendix E. for proof sketch, and Remark B.3 for a connection of our algorithm to the GOLF algorithm (Jin et al., 202 Xie et al., 2023).
EFFICIENT HYBRID RL WITH DENSITY RATIO REALIZABILITY
Toward overcoming the challenges of intractable computation in online exploration, a number of recent works show that including additional offline data in online RL can lead to computational benefits in theory (e.g.. Xie et al., 2021b; Wagenmaker and Pacchiano, 2023; Song et al., 2023; Zhou et al., 2023) and in practice (e.g., Cabi et al., 2020; Nair et al., 2020; Ball et al., 2023; Song et al., 2023; Zhou et al., 2023). Notably, combining offline and online data can enable algorithms that provably explore without having appeal optimism or pessimism, both of which are difficult to implement efficiently under general function approximation.
Song et al. (2023) formalize a version of this setting in which online RL is augmented with offline data-as hybrid reinforcement learning. Formally, in hybrid RL, the learner interacts with the MDP online (as in Section 1.1) but is additionally given an offline dataset Doff collected from a data distribution V. The data distribution v is typically assumed to provide coverage for the optimal policy x² (formalized in Definition 4.3), but not on all policies, and thus additional online exploration is required (see Appendix F.2 for further discussion).
4.1 O₂O: A PROVABLE BLACK- Box HYBRID- TO----------E-- OF-OFELINE REDUCTION
Interestingly, many of the above approaches for the hybrid setting simply apply offline algorithms (with relatively little modification) on a mixture of online and offline data (e.g.. Cabi al., 2020; Nair et al., 2020; Ball et al., 2023). This raises the question: when can we given offline algorithm as a black box to solve the problem of hybrid RL (or, more generully, of online RL?). To answer this, algortthmm,, H2O, which provides a provable black-box reduction to solve the hybrid RL problem by repeatedly invoking a given offline RL algorithm on a mixture of offline data and freshly gathered online trajectories. To present the result, we first describe the class of offline RL algorithms with which it will be applied.
give general
Offline RL and partial coverage. We refer to collection of distributions f = (14 1H where μ4, A(X x A), data distribution, and say that dataset D (Dr M=1 has H samples from data distributions v!") ....,, ,...,, ((() if Dr = {(x,)) a rh , hh+11 )) where (z/ a p.))) Th
R2 (x .0 (12) ), 3/111 Px(x)) h aaa)). We denote the mixture distribution via μ ((()=)) {u) where 1h
(1m) Th=1'
(1m)) = E 1h An offline RL algorithu Alg takes as input a dataset = (Dx )
of H n samples from nd) ""...,,'"") and outputs policy π = (Fx m An offline algorithm is
measured by its risk, as in Equation (1); we write Riskoff when we are in the offline interaction protocol.
An immediate problem with directly invoking offline RL algorithms in the hybrid model is that typical algorithms particularll,, those that do not make use of pessimism (e.g., Xie and Jiang, require relatively uniform notions of coverage (e.g., coverage for all policies as opposed to just coverage for x*) to provide guarantees, leading one to worry that their behaviour might be completely uncontrolled when applied with non-exploratory datasets. Fortunately, we will show that for large class algorithms whose risk scales with a measure of coverage refer to clipped concentrabilliy, this phenomenon cannot occur.
Definition 4.1 (Clipped concentrability coefficient). The clipped concentrability coefficient (at scale y E for क E II relative to a data distribution μ = {Hn)E where μr, E A(X A.), is defined as
CC,(T..)))) = clip,,
1.45
'When parameters are needed, Algat should instead be thought of as the algorithm for fixed choice of parameter. Likewise, treat function approximators (F, W. etc.) as part of the algorithm. We consider adantively chosen () hecause, in the reduction, Algar will he invoked history-dependent datasets.
7

---

Published as a conference paper at ICLR 2024
This coefficient should be thought of as generalization of the standard (squared) L2(p) concentrabil- ity coefficient 22 (T, p)) := | 2.19: offline RL algorithms (e.g., Farahmand et al., 2010), but incorporates clipping to better handle partial coverage. We consider offline RL algorithms with the property that for any offline distribution μu, the algorithm's risk can be bounded by the clipped concentrability coefficients for (i) the output policy n. and (ii) the optimal policy n². For the following definition, we recall the notation (()) == T n.
1 ||4///ml]] 041////l..d;: 1..7 a fundamental object in the analysis of
Definition 4.2 (CC-bounded offline RL algorithm), An offline algorithm Algoft is CC-bounded at scale y E R+ under an assumption (ssumption(-) if there exists scalars a,, by such that for all N and data distributions p²), ..... p( Algoff outputs p E A(II) satisfying
Riskol = ER - J[F)]
(T") (m0) (/0) + Ba-pICC (CCa u mn ,(")))) - by
with probability least 8, when given H samples from p( ,..., p(n) such that Assumption( (mm)) M*) ) is satisfied.
This definition does not automatically imply that the offline algorithm has low offline risk, but simply that the risk can be bounded in terms of clipped coverage (which may be large if the dataset has poor coverage). In the sequel, we will show that many natural offline RL algorithms have this property (Appendix F.1).7
The H. O algorithm. Our reduction, H2O, is given in Algorithm 2. For any dataset D, will write D 1ic for the subset consisting of its first elements. The algorithm is initialized with an offline dataset Doa (Doit /- and at each iteration E [I'] invokes the black-box offline RL algorithm Algoff with dataset Dhybrid (Phybrid,A Jh= that mixes the first elements of Doft. with all of the online data gathered so far. This produces a policy T(1,, which is executed to gather trajectories that are then added to the online dataset and used the next iteration. HzO is inspired by empirical methods for the hybrid setting (e.g.. Cabi et al., 2020; Nair et al., 2020; Ball et al., 2023), and in particular the meta-algorithm is efficient whenever Algoft is.
Algorithm 2 HyO: Syybrid-to-Offinng Reduction
input: Parameter T E N, offline algorithm Alg offline datasets Don (Doff hh each of size T.
1: Initialize D ph.h = D hybrid,A Ø for all h [H].
2: for /= 1, 1,..., T do
3: Get policy z( from Algoft on dataset Phybria = (Ditt
h k J
4: Collect (z), 01, ri),..... (IH, An, TH) using T() Diett) = Det) U (( an The Zn+ 1n+1]].
5: Aggregate offline and online data: hybrid,h Dost,h Dic+t) on
for all h E [H].
6: output: policy मे Unif(T "..,"""....""""".......
Main risk bound for H.O. We now present the main result for this section: a risk bound for the H2O reduction. Our bound depends the coverability parameter for the underlying MDP, well as the quality of the offline data distribution v, quantified by single-policy concentrability.
Definition 4.3 (Single-policy concentrability). A data distribution v = Hr satisfies C.-single- policy concentrability if max, |1 //r/l < C..
Theorem 4.1 (Risk bound for H2O). Let T E N be given, let Dan consist of H HT samples from data distribution v, and suppose that satisfies C.-single-policy concentrability. Let Algont be CC- bounded at scale E (0, 1) under Assumption(-), with parameters a., and b,, Suppose that V E [T] and 70) ..... T(1) E II. Assumption MM*) holds for μ == {1/2(1, + +// d% (8) Then, with probubility at least 1 8T, the risk of H₂O (Algorithm 2) with T, Algoft and Dott is
Examples of assumptions for Assumption include value function completeness (e.g., for For (Chen and Jiang, 2019)) and realizability of value functions and density ratios (e.g., for MARO (Xie and Jiang, 2020)).
8

---

Published as a conference paper at ICLR 2024
bounded as
(y(C++ Ccou) + byy ).
Risk < H
(8)
T
For the algorithms we consider, one can take a, x %/7 and by x by for scalar- valued problem parameters a, 0, that choosing Y optimally gives Risk v O(H /CC.,CCo.aa////// This is special case of more general result, Theorem F6, which handles the general case where v need not satisfy single-policy concentrability.
4.2 APPLYING THE REDUCTION: HYGLOW
We now apply H2O to give hybrid counterpart to GLOW (Algorithm 1), using variant of MABO (Xie and Jiang, 2020) as the black box offline RL algorithm Algoff in H2O. Further examples, which apply Fitted Q-Iteration (FQI) and Model-Based Maximum Likelihood Estimation the black box, are deferred to Appendix F.I.
More specifically, the offline RL algorithm we consider is variant of MABO that incorporates clipping and regularization in the same fashion as GLOW, which we call MABO.CR. CR. Our algorithm takes as input dataset D {D,} with H n samples, has parameters consisting of value function class F, a weight function class W, and a clipping scale y, and computes the following estimator:
fEE E arg min max JEF NEW
Σ EDD ü. (2h, an) (aaf oho Thi (44)))))))))) af ED,
[w (2t an)], (9)
where (n)) : (/m) and Wy clm [wn]. By instantiating H₂O with this algorithm, obtain density vatio-based algorithm for the hybrid RL setting (HYGLOW; Algorithm 3) that is statistically and computationally efficient.
Theorem 4.2 (Risk bound for HyGLOW). Let = >
be given, let Dott consist of H T samples from data distribution v. and suppose that v satisfies C, C.-single-polic concentrabil- ity. Suppose that Q E F and that for all E [T]. x E II, and h E [H], we have d7/p1) E W. where 1h =1/(vn + Ei= dr")). Then, HYGLOW (Algorithm 3) with imputs T (((t///)))))))))) log(1=11w1/8)) F. augmented W defined Eq. (34), ς = CCC,+Coo)THH log(17111118)) and Doft returns an e-suboptimal policy with probability at least 8T after collecting Ö (Cog log((>(1111/))) trajectories.
①
This result is obtained from Theorem 4.1 by showing that MABO.CR is CC-bounded under Q"-realizability and density ratio rcalizability assumption (cf. Theorem F.1). While the sample complexity and realizability assumptions parallel those of GLOW, the computational efficiency is improved because we remove the need for global optimism. More specifically, note that when clipping and the absolute value signs are removed from Eq. (9), the optimization problem is concave-convex in the function class F and weight function class W, a desirable property shared by standard density- ratio based offline algorithms (Xie and Jiang, 2020; Zhan et al., 2022). To accommodate clipping and the absolute value signs efficiently, we note that Eq. (9) can be written as convex-concave {=clip,,, [w,] wy E Wh) ) and
program in which the player optimizes over the set WA. the result continues to hold if the max player optimizes over any expanded weight function class W, S W such that || < ym for all w E W"; we defer the details to Appendix F.1.2.
5
CONCLUSION
Our work shows for the first time that density ratio modeling has provable benefits for online rein- forcement learning, and serves step in broader research program that aims to clarify connections between online and offline reinforcement learning. On the theoretical side, promising directions for future research include (i) resolving whether sample efficiency is possible under only coverability and value function realizability, and (ii) generic reductions from offline to online RL (see Appendix F3 for a brief discussion). In addition, we are excited to explore the possibility of developing practical and computationally efficient online reinforcement learning algorithms based on density ratio modeling.
'e define risk for the hybrid setting as in Eq. (1). Our result is stated a bound on the risk the optimal policy x² but extends to give hound on the risk of any comparator with C. replaced by coverage for

---

Published as a conference paper at ICLR 2024
REFERENCES
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646, 2014.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20181 2020.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008.
Philip J Ball, Laura Smith, Ilya Kostrikov, and Sergey Levine. Efficient online reinforcement learning with offline data. In International Conference on Machine Learning, pages 1577-1594. PMLR, 2023.
Serkan Cabi, Sergio Gómez Colmenarejo. Alexander Novikov, Ksenia Konyushkova, Scott E. Reed, Rae Jeong, Konrad Zolna, Yusuf Aytar, David Budden, Mel Vecerík, Oleg Sushkov, David Barker, Jonathan Scholz, Misha Denil, Nando de Freitas, and Ziyu Wang. Scaling data-driven robotics with reward sketching and batch reinforcement learning. In Robotics: Science and Systems XVI, Virtual Event / Corvalis, Oregon, USA, July 12-16, 2020, 2020.
Jinglin Chen and Nan Jiang. Information-theoretie considerations in batch reinforcement learning. In International Conference on Machine Learning, 2019.
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizability: the power of gaps. In Uncertainty Artificial Intelligence, pages 378-388, PMLR, 2022.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674 PMLR, 2019.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020.
Simon S Du, Sham M Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. International Conference on Machine Learning, 2021.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. Advances Neural Information Processing Systems, 23, 2010.
Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the bellman equation. Advances in Neural Information Processing Systems, 32, 2019.
Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint 12. 2021.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. In Conference Learning Theory, pages 3489-3489. PMLR, 2022.
Noah Golowich, Dhruv Rohatgi, and Ankur Moitra. Exploring and learning in sparse linear mdps without computationally intractable oracles. arXiv preprint trXiv:2309.09457 2023.
Audrey Huang, Jinglin Chen, and Nan Jiang, Reinforcement learning in low-rank mdps with density features. arXiv preprint arXiv:230..02252.22 2023.
Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds planning horizon. In Conference On Learning Theory, pages 3395-3398. PMLR, 2018.
10

---

Published as a conference paper at ICLR 2024
Nan Jiang and Jiawei Huang. Minimax value interval for off off-policy evaluation and policy optimization. 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-learnable. International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Neural Information Processing Systems, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021b.
Ilya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribution matching. In International Conference on Learning Representations, 2019.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning. pages 6120-6133 PMLR, 2021.
Gen Li, Wenhao Zhan, Jason Lee, Yuejie Chi, and Yuxin Chen. Reward-agnostic fine-tuning: Provable statistical benefits hybrid reinforcement learning. arXiv preprint arXiv:2305. 10282, 2023.
Fanghui Liu, Luca Viano, and Volkan Cevher. Provable benefits of general coverage conditions in efficient online rl with function approximation. International Conference on Machine Learning. 2023.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou, Breaking the curse of horizon: Infinite- horizon off-policy estimation. Advances in neural information processing systems, 31, 2018.
Zakaria Mhammedi, Dylan J Foster, and Alexander Rakhlin. Representation learning with multi- step inverse kinematics: An efficient and optimal approach to rich-observation rl. International Conference on Machine Learning (ICML), 2023.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. arXiv preprint arXiv:1911.058/5 2019.
Rémi Munos. Error bounds for approximate policy iteration. In International Conference on Machine Learning, 2003.
Rémi Munos. Performance bounds in f--norm for approximate value iteration. SIAM Journal Control and Optimization, 2007.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008.
Ofir Nachum and Bo Dai. Reinforcement learning via fenchel-rockafellar duality. arXiv preprint arXiv:2001.01 2020.
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02090 2019.
Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. Awac: Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.09359, 2020.
11

---

Published as a conference paper at ICLR 2024
Gergely Neu and Nneka Okolo. Efficient global planning in large mdps via stochastic primal- optimization. In International Conference on Algorithmic Learning Theory, pages 1101-1123. PMLR. 2023.
Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33:1392-1403, 2020.
Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. Revisiting the linear- programming framework for offline rl with general function approximation. In International Conference on Machine Learning, pages (6769-26791, PMLR, 2023.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1702-11716, 2021.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao. Optimal conserva- tive offline rl with general function approximation via augmented lagrangian. In The Eleventh International Conference Learning Representations, 2023.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pages 2256-2264, 2013.
Yuda Song, Yifei Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid RL: Using both offline and online data can make RL efficient. International Conference on Learning Representations, 2023.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933. PMLR, 2019.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang, Minimax weight and Q-function learning for off-policy evaluation. In International Conference on Machine Learning. 2020.
Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. w:Xiv:2102.02990 2021.
Andrew Wagenmaker and Aldo Pacchiano. Leveraging offline data in online reinforcement learning. In International Conference on Machine Learning, pages 35300-35338, PMLR, 2023.
Ruosong Wang, Simon S Du, Lin Yang, and Sham Kakade. Is long horizon rl more difficult than short horizon rI? Advances in Neural Information Processing Systems, 33:9075-9085, 2020a.
Ruosong Wang, Dean Foster, and Sham M Kakade. What are the statistical limits of offline RL with linear function approximation? In International Conference on Learning Representations, 2020b.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020c.
Yuanhao Wang. Ruosong Wang. and Sham M Kakade. An exponential lower bound for linearly- realizable MDPs with constant suboptimality gap. Neural Information Processing Systems (NeurIPS), 2021.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in MDPs with rinelaly-reliizable optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR, 2021.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforeement learning: A theoretical comparison. In Conference on Uncertainty Artificial Intelligence. 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference Machine Learning, pages 11404-1144 11004-11411 11413, PMLR, 2021.
12

---

Published as a conference paper at ICLR 2024
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistee consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning, Advances in neural information processing systems, 14:27395-27443 2021b.
Tengyang Xie, Dylan Foster, Yu Bai, Nan Jiang, and Sham M Kakade, The role of coverage in online reinforcement learning, International Conference on Learning Representations, 2023.
Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-polic, evaluation via the regularized lagrangian. Advances in Neural Information Processing Systems, 33:6551-6561, 2020.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch RL can be exponentially harder than online RL. In International Conference on Machine Learning, 2021.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill, Learning near optimal policies with low inherent bellman error. International Conference on Machine Learning, pages
PMLR, 2020.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages 2730-2775. PMLR, 2022.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. arXiv preprint arXiv:2002. 09072. 2020.
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 Machine Learning, pages 26517-26547. PMLR, 2022.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528-4531. PMLR, 2021.
Yifei Zhou, Ayush Sekhari, Yuda Song, and Wen Sun. Offline data enhanced on-policy policy gradient with provable guarantees, arXiv preprint wtXiv:23111.8882 2023.
13

---

Contents of Appendix
A Additional Related Work
14
Comparing Weight Function Realizability to Alternative Realizability Assumptions
15
Examples for GLOW
16
Technical Tools
18
D.I Reinforcement Learning Preliminaries
18
Proofs from Section 3 (Online RL)
19
E.1
Overview Proof Techniques
19
E.2 Supporting Technical Results
20
E.3 Main Technical Result: Bound on Cumulative Suboptimality for GLOW
E,4 Proof of Theorem 3.1
27
E.5
Proof of Theorem
28
F
Proofs and Additional Results from Section (Hybrid RL)
31
F.1
Examples for H₂O
F.2
Comparison Offline RL
F33
Generic Reductions from Online to Offiine RL.?
34
E.4
Proofs for H2O (Theorem 4.1)
F.5
Proofs for H₂O Examples (Appendix F.1)
39
A ADDITIONAL RELATED WORK
Online reinforcement learning. Xie (2023) introduce the notion of coverability and provide regret bounds for online reinforcement learning under the assumption of access to value function class satisfying Bellman completeness. Liu al. (2023) extend their result more general coverage conditions under the same Bellman completeness assumption. Our work complements these results by providing guarantees based on coverability that do not require Bellman completeness.
To the best of our knowledge, our work is the first to provide provable sample complexity guarantees for online reinforcement learning that take advantage of the ability to model density ratios, but a number of closely related works bear mentioning. Recent work of Huang al. (2023) considers the low-rank MDP model and provides an algorithms which takes advantage of a form of occupancy realizability. Occupancy realizability, while related density ratio realizability, is stronger assump- tion in general: For example, the Block MDP model (Krishnamurthy et al., 2016; Du et al., 2019; Misra et al., 2019: Zhang et al., 2022; Mhammedi al., 2023) admits a density ratio class low complexity, but does not admit a small occupancy class. Overall, however, their results are somewhat complementary, they do not require any form of value function realizability. number of other recent works in online reinforcement learning also make use of occupancy measures, but restrict to linear function approximation (Neu and Pike-Burke, 2020; Neu and Okolo, 2023). Lastly, a number of works apply density ratio modeling in online settings with empirical focus (Feng al., 2019; Nachum et al., 2019), but do not address the exploration problem.
Offline reinforcement learning. Within the literature on offline reinforcement learning theory, density ratio modeling has been widely used as a means to avoid strong Bellman completeness requirements, with theoretical guarantees for policy evaluation (Liu et al., 2018; Uehara et al., 2020; Yang et al., 2020; Uehara et al., 2021) and policy optimization (Jiang and Huang, 2020; Xie and Jiang, 2020; Zhan et al., 2022; Chen and Jiang, 2022; Rashidinejad al., 2023; Ozdaglar et al., 2023). A number of additional works investigate density ratio modeling with empirical focus, and do not provide finie-ssmple guarantees (Nachum et al., 2019; Kostrikov et al., 2019; Nachum and Dai, 2020; Zhang et al., 2020; Lee al., 2021).
Hybrid reinforcement learning. Song et al. (2023) were the first to show, theoretically, that the hybrid reinforcement learning model can lead to computational benefits over online and offline RL individually, Our reduction, H2O, can be viewed generalization of their Hybrid Q-Learning algorithm, with their result corresponding to the special case in which FQi is applied as a the base algorithm. Our guarantees under coverability complement their guarantees based on bilinear rank.
14

---

Published as a conference paper at ICLR 2024
Other recent works on hybrid reinforcement learning in specialized settings (e.g., tabular MDPs or linear MDPs) include Wagenmaker and Pacchiano (2023); Li et al. (2023); Zhou et al. (2023).
B COMPARING WEIGHT FUNCTION REALIZABILITY TO ALTERNATIVE REALIZABILITY ASSUMPTIONS
In this section, we compare the density ratio realizability assumption in Assumption 2.2 to a number of alternative realizability assumptions.
Comparison to Bellman completeness. A traditional assumption in the analysis of value function approximation methods is to assume that FF satisfies a representation condition called Bellman completeness, which asserts that F++1 C Fr; this assumption is significantly stronger than just assuming realizability of Q" (Assumption 2. and has been used throughout offline RL (Antos et al., 2008; Chen and Jiang, 2019), and online RL (Zanette et al., 2020; Jin et al., 2021a; Xie et al., 2023).
Bellman completeness is incomparable to our density ratio realizability assumption. For example, the low-rank MDP model (Jin et al., 2020) in which Pa (x' a) (ón (z, a), 4 (x²)) satisfies Bellman completeness when the feature map & is known to the learner even if sb is unknown (but may not satisfy it otherwise), and satisfies weight function realizability when the feature map vó is known even if Φ is unknown (but may not satisfy it otherwise). Examples C.1 and C.2 in Appendix give further examples that satisfy weight function realizability but are not known to satisfy Bellman completeness.
Comparison to model-based realizability. Weight function realizability is strictly weaker than model-based realizability (e.g.. Foster et al., 2021), in which one assumes access to model class M of MDPs that contains the true MDP. Since each MDP induces an occupancy for every policy, it is straightforward to see that given such class, we construct weight function class W that satisfies Assumption 2.2 with
log|W|
W| S O(log] M| + log]
as well as a realizable value function class with 1o < (log)MM).. On the other hand, weight function realizability does not imply model-based realizability; a canonical example that witnesses this is the Block MDP.
Example B.1 (Block MDP). In the well-studied Block MDP model (Krishnamurthy et al., 2016; Jiang al., 2017; Du al., 2019; Misra al., 2019; Zhang et al., 2022; Mhammedi al., 2023), there exists realizable value function class F and weight function class W with log W| S poly([&),, |A], log//(). where S is the latent state space and & is a class of decoder functions. However, there does not exist a realizable model class with bounded statistical complexity (see discussion in, e.g., Mhammedi et al. (2023)).
Alternative forms of density ratio realizability.
Remark B.1 (Clipped density ratio realizability). Since GLOW only accesses the weight function class W through the clipped weight functions, we can replace Assumption 2.2 with the assumption that for all π, n' E II, t S T, we have clip,, [==="]] E -W, where T E N and ry E [0, 1] are chosen as in Theorem 3.2. Likewise, we can replace Assumption 2.2' with the assumption that for all a E II, and for all < T, and TT E ITT, we have clip,y [u J.W, for T E M and E [0, 1] chosen as in Theorem 3.1.
Remark B.2 (Density ratio realizability relative fixed reference distribution). Assumption 2.2 is weaker than assuming access to a class W that can realize the ratio diffr (or alternatively va(d%)
for all IL. where Vn is an arbitrary fixed distribution (natural choices might include 1/h, 1
or U/ = dj. ). Indeed, given access to such a class, the expanded class W := (w/w/ | [w w E W} satisfies Assumption 2.2 and has logl < 2 Wo.
Remark B.3 (Connection to GOLF). Prior work (Xie et al., 2023) analyzed the GOLF algorithm of Jin et al. and established positive results under coverability and Bellman completeness. We remark that
Up to H factors, this is equivalent to assuming access to class of transition distributions that can realize the true transition distribution, and class of reward distributions that can realize the reward distribution.
15

---

Published as a conference paper at ICLR 2024
by allowing for weight functions that take negative values. 10 GLOW can be viewed as generalization of GOLF, and can be configured to obtain comparable results. Indeed, given a value function class FF that satisfies Bellman completeness, the weight function class W := {f f' f. F} leads to a confidence set construction at least as tight as that of GOLF. To see this, observe that if we set 7 2 so that no clipping occurs, our construction for F (Eq. (3)) implies (after standard concentration arguments) that Q E F and that in in-sample squared Bellman errors are small with high probability. These ingredients are all that is required repeat the analysis of GOLF from Xie et al. (2023).
C EXAMPLES FOR GLOW
In this section, give two new examples in which main results for GLOW, Theorems 3.1 and 3.2, can be applied: MDPs with low-rank density features and general value functions, and a class of MDPs refer to Generalized Block MDPs.
Example C.1 (Realizable Q" with low-rank density features). Consider a setting in which (i) Q" E F, and (ii), there a known feature map thh x A -> Rdd with 1/ (2, a) ll2 S such that for all E II, di (1x a) (1, a), ) for an unknown parameter 8 Rd with ||0* S This assumption is sometimes referred to as low occupancy complexity (Du et al., 2021), and has been studied with and without known features. In this case, we have Ceau S c, and one can construct a weight function class W that satisfies Assumption 2.2' with log W| S (dH)) (Huang et al., 2023). !! As result, Theorem 3.1 gives sample complexity Ö Fog)F)/E²). Note that while this setup requires that the occupancies themselves have low-rank structure, the class F can consist of arbitrary, potentially nonlinear functions (c.g., neural networks). We remark that when the feature map e is not known, but instead belongs to a known class V, the result continues hold, at the cost of expanding W to have size log) W| S Öddf + log/v/). V/)
This example is similar to but complementary to Huang al. (2023), who give guarantees for reward-frie free exploration under low-rank occupancies. Their results do not require any form of value realizability, but require a low-rank MDP assumption (which, in partieular, implies Bellman completeness).
Our next example concerns a generalization of the well-studied Block MDP framework (Krish- namurthy et al., 2016; Jiang et al.. 2017: Du et al.. 2019; Misra et al., 2019; Zhang et al., 2022; Mhammedi et al., 2023) that we refer as the Generalized Block MDP.
Definition C.1 (Generalized Block MDP). A Generalized Block MDP M (X, S, A, Patent: Riatent, q; H, d1) is comprised of an observation space X. latent state space S, action space A, latent space transition kernel Patent :S x A ASS), and emission distribution q: S + A(X). The latent state space evolves based on the agent's 'ss action On A via the process
Th Riatent (sh, an); 8h+t1
Piatent(
8h, (h),
(10)
with $1 ~ dy: we refer to Sh as the latent state. The latent state is not observed directly, and instead observe observations E X generated by the emission process
Ib. q(- sn).
(11)
We assume that the emission process satisfies the decodability property:
supp q(: |s) n Ssupp | =0, Ø, As #
(12)
Decodability implies that there exists a (unknown to the agent) decoder o.: X S such that &. (2x) = Sh a.s. for all h [H), meaning that latent states can be uniquely decoded from observa- tions. Prior work on the Block MDP framework KKishhamurthhy et al., 2016; Jiang et al., 2017; Du et al., 2019; Misra al., 2019; Zhang et al., 2022; Mhammedi et al., 2023) assumes that the latent
+
In this context, W can be thought of more generally as class of test functions.. "To be precise, W is infinite, and this result requires covering number bound. We omit formal treatment, and refer Huang et al. (2023) for details.
Thee low-rank MDP assumption is incomparable to the assumption we consider here, as it implies that (x) = (1)(2)) ) but does not necessarily imply that the state-action occupancies (i.c. di (z. a)) are low-rank.
16

---

Published as a conference paper at ICLR 2024
space S and action space A are finite, but allow the observation space X' be large potentially infinite. They provide sample complexity guarantees that scale as poly( |A], H. log| | (.).).)),
where & is known class of decoders that contains o.. We use the term Generalized Block MDP to refer to Block MDPs in which the latent space not tabular, and can be arbitrarily large.
GLOW to give sample complexity guarantees for Generalized Block MDPs in which the latent space is large, but has low coverability. Let Ihatent = (S [H] - ((A) denote the set of all randomized policy that operate on the latent space. Assume that the following conditions hold:
Example C.2 (Generalized Block MDPs with coverable latent states). We
We have value function class Fiatent such that Vistent F, where Viatent is the optimal Q-function for the latent space.
We have access class of latent space density ratios Watent such that for all h E [4]] and all n, T'' E 1lttentt
K,n' W intent,, (8,a) == Istent, (s, a) E Watents
Istent, hs (s,a)
where datent,, 1pth (8h- = 8, a) is the latent occupancy measure.
The latent coverability coefficient is bounded:
latent,h
inf Coov,latent Mionod EA(SXA) hE
sup
14h
We claim that whenever these conditions hold, analogous conditions hold in observation space (viewing the Generalized BMDP large MDP), allowing GLOW and Theorem 3.2 be applied. Namely, we have:
There exists class F satisfying Assumption 2.1 in observation space such that log [F S (log) Fiatent| + 1
There exists weight function class W satisfying Assumption 2.2 in observation space such that log WI < Wlacee/aacat!
Wacent + log +|).
We have Ccov S Caov.latent
As a result, GLOW attains sample complexity poly This generalizes existing results for Block MDPs with tabular latent state spaces, which have Fistnt) log) Watent Caov,latent poly([S), |A], H).
H, liateti log] Wiatent I. log | e e
17

---

Published as a conference paper at ICLR 2024
D
TECHNICAL TOOLS
Lemma D.1 (ezuma-Hoeffding)) Let M E NN and (Ym)m<M be sequence of random variables
adapted to a filtration (mm) If S R almost surely, then with probability at least 1
M
Σ m3
Ym
Em [mm] <R SR.V8M log(2-)11
Lemma D.2 (Freedman's 's inequality (e.g., Agarwal et al., 2014)). Ler M E and (Ym)mMM be real-valued martingale difference sequence adapted to a filtration (Fmmms. (Y|m R almost surely, then for any E (0, 1/R), with probability at least 1 5,
M
M
Bm 1 {? + log(20-1)
Σ
Ym
I m=1
1
m=1
The following lemma is standard consequence of Lemma D.2 (e.g., Foster et al., 2021).
Lemma D.3. Let M N and (mm)msM be sequence of random variables adapted filtration
(Fm) M. 1f0 & Yu < R almost surely, then with probability at least 1 - 8,
3 Σ
Σ
Y
Em [Ym] 4Rlog(20-1),
and
M
M
R [Ym)
S2
Σ m=1
Yn + 8Rlog(26
D.I REINFORCEMENT LEARNING PRELIMINARIES
Lemma D.4 (Jiang et al. (2017, Lemma 1)). For any value function f = (JI,...,SH)
Eny [ nn (#1)) J(
Σ #=1
E
[Tnfnt1((Hn, an)
Lemma D.5 (Per-state-action elliptic potential lemma; Xie et al. (2023, Lemma 4)), Let ...., d be an arbitrary sequence of distributions over a set Z. and let E A(Z) be distribution such that att (s)/ S for all z E Z and E [T]. Then, for all E 2, we have
T
d (2)
< 2 + T))
Eier dlm (2)
18

---

Published as a conference paper at ICLR 2024
E PROOFS FROM SECTION 3 (ONLINE RL)
This section of the appendix is organized as follows:
Appendix E.I gives a high-level sketch of the proof of Theorems 3.1 and 3.2, highlighting
the role of clipped density ratios and coverability.
Appendix E.2 provides supporting technical results for GLOW, including concentration guarantees.
Appendix E.3 presents main technical result for GLOW, Lemma E.4, which bounds the cumulative suboptimality of the iterates ,..., (7)) produced by the algorithm for general choices of the parameters T, K, and y 0.
Finally, in Appendices E.4 and E.5, we invoke with specific parameter choices to prove Theorems 3.1 and 3.2, well as more general results (Theorems 3.1' and 3.2') that allow for misspecification error.
E. OVERVIEW OF PROOF TECHNIQUES
In this section we give a proof sketch for Theorem 3.1, highlighting the role of truncated weight functions in addressing partial coverage. We focus on the regret bound; the sample complexity bound in Eq. (5) an immediate consequence.
By design, the constraint in Eq. (3) ensures that Q' E F for all t < T with high probability. Thus, by a standard regret decomposition for optimistic algorithms (Lemma D.4), we have
T Reg- Σ J(Z")
N
[1h (Ch, an) - [TS ( an)
(13)
d
On-policy Bellman error for f(() under (1)
up to lower-order terms, where we abbreviate d = d=(0 Defining (() == A (I, a) [Thsht [zx (z,0), a), remains to bound the on-policy expected bellman error
E E f ax)]. To do so, natural approach is to relate this quantity to the weighted off-
policy Bellman error under d == + Eier a=(0)
by introducing the weight function //0/20) W:
d/ (x 0n) 2 (2h, an))
E Bg [A (' an) = Ezy0 [nf an)
Unfortunately, this equality is not true as-is because the ratio / can be unbounded. We address this by replacing d's by d(t+1) throughout the analysis (at the cost of small approximation error), and work with the weight function w == 44¹² /ap+)) W. which is always bounded in magnitude I. However, while boundedness is desirable property, the range / is still too large to obtain non-vacuous concentration guarantees. This motivates us to introduce clipped/truncated weight functions via the following decomposition.
[[ [
un) B [ (1)(,, an) clip,,o [wo].) (Ir, an)] + Bage [T[ (f (Ih, an) 2 20
On policy Bellman error
(A₂): Clipped off policy Bellinn emoor
(B²): Loss due to clipping
Recall that wb(h) = clipy.co (w))) (In, an). As with) E W. follows from the constraint in Eq. (3) and Freedman ttyp concentration that the clipped Bellman error in term (A,) has order
(t)) E8 18 [( + 3,0)) that DTr Ar I Σt at Eg [1 + g Since clip to 70 = yt, we have Σt= g S+ T (og((FF)M))// bounding the sum of weight functions requires more involved argument that we defer for a moment.
We now focus on bounding the terms (B.). Each term (B:) captures the extent to which the weighted off-policy Bellman error at iteration fails approximate the true Bellman error due to clipping. This occurs when d(t-1) has poor coverage relative to d which happens when 7()) visits portion of the state space not previously covered. We begin by applying Markov's inequality (Ifu 2 20 S w/o for u, v 2 0) to bound
d (wh, an) (et1)
1
8 (Ih, an)
E Egg0 (w), (Ih, an)) = 7000 Egd B, < 7((1)
(14)
(Ih,
an)
7
d
7012)
(1), a1)
19

---

Published as a conference paper at ICLR 2024
where the equality uses that 7:0 := y and d := d t. Our most important insight is that even though each term in Eq. (14) might be large on a given iteration (if previously unexplored portion of the state space is visited), coverability implies that average across all iterations the error incurred by clipping must be small. In particular, using a variant of a coverability- potential argument from Xie et al. (2023) (Lemma D.5), show that
T
de (Wh, an) an) ((e41) (Ihs an)
Σ
E
< O(Covv log(T)),
d%
1=1
so that Et= B. I O(Ceau/7). To conclude the proof, we use analogous potential argu- ment show the sum of weight functions in our bound on Σ A also satisfies Σ a Ege+1; [(0))) < O(Ccov/)). The intuition is similar: the squared weight functions (corre- sponding to variance of the weighted Bellman error) may be large in a given round, but cannot be large for all rounds under coverability. Altogether, combining the bounds on A and B, gives Reg = (H Caze + + (I[[T8T888) The final result follows by choosing 7 > 0 to balance the terms.
We find it interesting that the way in which this proof makes use of coverability--to handle the cumulative loss incurred by clipping-is quite different from the analysis in Xie al. (2023), where it more directly facilitates change-of-measure argument.
E.2 SUPPORTING TECHNICAL RESULTS
For x. x' E EX E. (0, 1), and E [M], recall the notation
[ fn max fa(e',
[An] = (, (Tn,n++(((( (n( clip,
[wn] (lip,,to/wa/(3.
Lemma E.1 (Basic concentration for GLOW). Let 700 > 0 for E [T.. With probability at least 1 8, all of the following inequalities hold for all J E F, w E W. E (T] and (H):
(a)
E (
[Z an. The xh wy (In, an)
- Bage IAn an) in (In, an)] S 3,.05
10
Eg0 (n))))),)))))) g0
(b)
700 Bay
[ (Th; an)]
2 B 7007
D(o [wg] ( an)] + ~g
(c) 700 E Pep (2 an)]
3
Eaz
[wn (zn; an)] g(()
2
(d) J(T)) E Ed lfa (21, T (x1))]
<
È
E [max, Qi(z1,01 (y
8 log (0
K(t-1)
36 (2)
where Wn. = cls [wn] and 3
(og((/=)]//T///))
K(-
Proof of Lemma E.1. Fix any h E [H] and t [T]. Let M K(t and recall that the dataset D
consists of M tuples of the form {<r oa rh =x++1)) ) JmsM where x P(- a 0% (m))
and 0) (m) = (m)(()/)))) where T rmm) = [m/x], Fix any f E F and w E W.
Proof of (a). For each m [M]. define the random variable
Y.-- (a ah rim (m()) wn (1
aa (m))) E -Egrtty [[A_ an) wh (2h, an)]
Clearly, Emm- = and thus (Ym IMs M is martingale difference sequence with
Y < 3 sup wu (Z), aa)l ()
20

---

Published as a conference paper at ICLR 2024
since
| ((/// a , S 2 and [[ ax)l S 1. Furthermore,
M Σ
Σ Y
wh441)) tn (n a (m))
(m)
Σ
E (m)) [Anf] an) -in(Tn an)
m=
K(t 1)
[fn (2 Cb. rbi +1) in (Th, an)
K
E (rr [An an) th (Zh.
K(t 1) (0
(Tn) ar, rhi x1 wn (In, an)
K(tt 1) E x
[ an) unn (2n, an))
Additionally, we also have that
Em [Xmm)] 2
[IAnff(a/ a ah mii -mai1 (a) .a a/mr))))
(
| A an) .n (Fn, an)) )
2 Em-1
Em -1
Swm (1)
)
+ 2 d
(-()))
([An.f(ET,, an) th (zn, az))²
Em-1
8r0 (2/ aa )
+ 22
of (m)))
(1x, am))
10 E. of
(m))))
(10 (Jin, a=))
where the second line follows since [ (m) (m) (m) , ) s 2 and by using Jensen's inequality, and the third line uses [A, an) 1
-hh
Thus, using Lemma D.2 with 77 1/3y(t), get that with probability at least - 8',
M
Ym
= K(t
1)
E
[anf( an Thi Th. 2//41) wn (2n, an)
B Bg [[n ax) ii (an, an)
m=1
10K
E /
[(wnn(n (n) + 3 log(2/8')
37(())
10K
1)
E B (In, an)) [x)] ") log(2/5").
3-
The above bound implies that
E p
[ an, The 2h41)) (nn, an)
Ex [[n1[Aff(2 an) wn
an)l (n))l
10
37
[(vn an)))
1) log(2/8").
37yc
Plugging in the value of 309 gives the desired bound. The final result follows by setting 8' = 5/3//" IWITH, and taking another union bound over the choice of f, w. and h.
Proof of (b) and (c). For each m E [M]. define the random variable
Y (wxx<x (ar )² (
Clearly, the sequence {Ym ImsM is adapted to an increasing filtration, with Y, 2 0 and |Y] ) S (2)) Furthermore,
((w), (x) , a (m))
E 1 Ymml K
Σ
E A (2h. K(t 1) Ez0 ((0n( an)))
and,
Ym
Σ
(un( K(t - 1)Ep!0) (win((n, an)))
m=
(
21

---

Published as a conference paper at ICLR 2024
Thus, by Lemma D.3, we have that with probability at least - 8'
E B30 (1)))))))))) - 2 p (Tn, an)) 8(111)22 1og(2/0') K(t 1)
and
(
Epgo (In an)) S ga [(in (2n, as)) +
K(L 1)
The final result follows by setting 8' // and taking another union bound over the choice of f, w. I and h.
Proof of (d). For each m E [M]. define the random variable
Ym max (1(""") .a) f1(=1")
Clearly, [m I 1. Thus, using Lemma D.1, we get that with probability at least 1 - 8
M
Σ Em [mm]
Σ max (1 ,a) (1 T (x("))) + log(///)
Setting M = [(t - 1) and noting that Bm-1(Ym) = J(x²) Enyod [f2 (21, nn (+1)) since x!T) di for any m [M]. we get that
8 8log(2/8))
J(x²) (f TH (x1) E
E anD
+
K(t -
The final result follows by setting 8' //3 and taking another union bound over choice of ʃ, w. and h.
Lemma E.2 (Properties of GLOW confidence set), Let (0) 2 0f t E [T]. With probability least
1 8, all of the following events hold:
(a) For all t 1, Q" E F()
(b) For all t 2 2, h E [H), f E F(O,, and w E W, we have
20
7
E B [l an) (n (x)))aa))) S yee)
[w, ( +
18
Furthermore,
40
7360)
+ 700
E go [Anf](Z an) (I an))
E
Bx--1 [(.n(In.
y00
160
(c) For all 1 2 2, we have
Bzy max (1) (21, 1 (x1)) S
K(t 1)
where Wy clip,.co [wn] and g0 3t
K(t-1) log /8
Proof of Lemma E.2. Using Lemma E.1, we have that with probability at least 8. for all F. w E W, E [T] and h E [M].
E [[nS](TA, an, Thi 2442) tha (æn, an)] gg [[ an) th (2 (xn, an>l
10
g
<
E [(in (x ax))) +
(15)
3
12
22

---

Published as a conference paper at ICLR 2024
yts E Boo (10 an)) 2
2
E Aạp0 [ (Th, [])] =
(16)
y(v)
1
3
,80
E B (tx (2 an))a v
E (iy (2 an))²]
(17)
y(0)
2y(0))
dh
9
and,
[ - (Ei, B max ()) - S1 T ((1))
llog (log(6/F/I[IHH/
+
(18)
K(1- ((1-1)
For the rest of the proof, we condition on the event in which (15-18) hold. Proof of (a). Consider any t [T]. and observe that the optimal state-action value function Q* satisfies for any wn E W.
E M (Q% an) - rh - max a'
d')) ven (an, and 0,
where رi == clipy, [wx]. Using the above relation with (15), we get that
E B [0T("); ap) Th max 2h+ (2 (1/h1;;')) a²)) wn (5 an)
10
E
an)) + 12
,80
3y00
di
[10 (2n, an. an)) + (30)
E A
y(1
12
I 200
Epg [(ū (Z an)) + 8800
where the second-last inequality follows from (16).
Plugging in the values of a and (00,, rearranging the terms, we get that
E Di" (1n, an) - Th max Qi+ (1%441;))) th an) - a aL" an) s g
a'
Since the above inequality holds for all w E W, we have that Q* E F(t))
Proof of (b). Fix any I, and note that by the definition of F(t), any ʃ F(() satisfies for any w E W, the bound
Ezgo (fa(zn on) TA max fu+t (f) (T an) 5 7(0
10
Ep(())
E
(2h,, (11) + 8
Using the above bound with (15), get that
10
10
13
E Rg [[An,[(rr, an) in (In, ax) S
Ezg (wnn(z an) a=))
+
7:1) D [1n, (xh, +
R
go.
3
12"
Plugging the bound from (17) for the second term above, we get that
20 E By
ax)) 7,30)
a Eg
[IAn. an) un (F an) S
18
Finally, noting that d (c-1)xC+a") we can further upper bound as:
E Egt+ f((n,, an) ib (22, an)
t
20
7,800
+
E dh [lAsa an) dhn (zn,
6
7(1))
20
[Win(Ins an)) + 7,8
2
E
Ege
[n (w0,, an)l]
7(0
40
7
40
(0)
E
g
(1 an) [n)) +
E
[w,,
(2h,
anh)
700
160
40
0000
E
(w an) (n
(())
9
160
where the second-to-lass line follows from application of AM-GM inequality.
23

---

Published as a conference paper at ICLR 2024
Proof of (c). Plugging in f(() in (18) and noting that max, Qi(21, = Qx x (x))) for any I E X. we get that
8 F
((x)) - Berndh (111 (21)) - B sn (0( (1,,
(I1, gon +
K(t 1))
However, note that by definition, N E arg max Bisi (21, TA (z) )] and using part-(a), Q" E FFW.
Thus, E. Bppo0 ((())) 1 (I1, ((o
which implies that
8 6log(6FFIW((H/0)) K(t-1 1)
J(TT) - Eornds (11 go
Lemma E.3 (Coverability potential bound). Let d be an arbitrary sequence of distribu- tions over x A. such that there exists a distribution μ E A x A) that satisfies || /M| S C for all (I, a) X A and I [T]. Then,
(x,
Σ (2.a)aa
S <5Clog(T),
ditt
where recall that d = Emm d for all [T].
Proof of Lemma E.3. Let minfl ) 2 Cu(ar,a) With this definition, can bound
d (z,
(z,
E g(0))
Σ E g())
1ft r(z,a)}
(1, a))
(2
(x,
+
Bytt)
Ilft 2 r(2,
(x, a)
T
d'C(r,
$
Egio [Ift < Txx a)}
Σ Ego
I[t 2 ((x,
do
(1) barn-in plasse
(II) stable phase
where the second line uses that de0 (1. S 1.
For the burn-in phase, note that
Σ Egc [L[t < ((2, a(x,
Σ Σ d'(,, = - (2, S Exl(r, C2
(<r(z.))
where the last inequality uses that by definition, d' (',,, a) S Cu(a, a) for all L S TT(x
For the stable phase, whenever 2 Tx a), by definition, we have d(t1) a) 2 Cp(z, a) which implies that d (z, a) 2 (d (z, a) Cp(z,a)). Thus.
(II)
Ex(0)
(19)
(I, + C)(z,a)
(x,) a) ddh (x,
d(t) (2, a) + CH(I,a) a)
F.a
d (x,
Σ max d''')z, (zz a) max
Σ
2.0
d: (z, a) + Cu(r,,
24

---

Published as a conference paper at ICLR 2024
Using the per-state elliptical potential lemma (Lemma D.5) in the above inequality, we get that (II) S (T + 1)
Σ
max dd (z, a) S 4C log + e'e(T]
Σ
ulx, a) - 4C log (1 + T), (20)
2,a
where the second inequality follows from the fact that equality uses that Ex,a p1x, a) = 1. Combining the above bound, get that
C' (by definition), and the last
T
d (x, a) d (x,, a)
E
S 5C log(T))
E.3 MAIN TECHNICAL RESULT: BOUND ON CUMULATIVE SUBOPTIMALITY FOR GLOW
In this section we prove key technical lemma, Lemma E,4, which gives a bound on the cumulative suboptimality of the sequence of policies generated by GLOW. Both the proofs of Theorem 3,2 and Theorem 3.1 build on this result. To facilitate more general sample complexity bounds that allow for misspecification error in W. In particular, for each t [T], we define as the misspecification error of the clipped density ratio df") // in class Wh. defined as
& == sup inf sup (0 he(H] WEWA well
clip, co) [wn]
(21)
7641
1.d5
where recall that for any function : X' ||u[[ı,d == B(o.a)-allu(z, a)l. Note that under Assumption 2.2 or 2.2', & 0 for all t (T].
R and distribution d E A(X A), the norm
Lemma E.4 (Bound on cumulative suboptimality). Let ,......,. (!!) be the sequence of policies generated by GL.WW, when executed on classes F and W with parameters T, K and 7, Then the cumulative suboptimality of the sequence of policies {T") hee(Ty bounded as
T
= o( H Coov log(1 + +T)
T
E E ))
Σ J(オ)) ((a)) 1=1
K
Proof of Lemma E.4. Fix any t 2 2. We begin by establishing optimism follows:
J(x²) (() = Bx max Qi (211 a)] ((T'0)
E dd
max Qi 11 (x1, "0 (xi)) En [$1 (x11 x (x:)) J(T
(0x()))/IIW(HH//) Eayedd [5 (11, T (x:)) (TT())
K(t
where the last line follows from Lemma F.2-(c). Using Lemma D.4 for the second term, we get that
- S
8 K(I-1)
Σ EE (as (as )naf (10 an)},
where recall that ( an) = 1 (1n, - (T (T an). Thus,
T
Σ J( - (() < -(7))- - () + Σ J(TT) ((
T
8 8log (log((///IW/TH//
11
E
(sn ( an)),
K(t-1)
(22)
where the second inequality uses that J(m*) < 1 and J( 2 0.
25

---

Published as a conference paper at ICLR 2024
We next bound the expected Bellman enror terms that appear in the right- hight-hand-sin hand-side above. Consider any 2 2 and h E [H] and note that via a straightforward change measure.
d (3A, "h (xn, an) an)
E d
|| ( an)]
E a
| ( ap)
Since S mi, f) + uilf 2 t) for any u, v, we further decompose as
[A an) min { (zn, an)
B B 1e fr (T an)l s B x+n
(In, an) .7163
(%
I (I
(A): Expected clipped Bellman ervor
[{
d (In, an) (x (1))
}
+ E. dg
(B): clipping violation
where in the second term we have changed the measure back to d/, and used that f ax)l 1. We bound the terms (A) and (B) separately below.
Bound on expected clipped Bellman error. satisfies
Let w/y (In, an) E W denote weight function which
sup
clip
clip,.o) [wn
S Se.
(23)
1,47
which is guaranteed to exist by the definition of &.. Then, we have
de (Ir, an)
(A) = %n
A an) clip,..)
( an))
dh
< (
| f0 (2 an) clip, (20 (#h, an)) ) + clip,,
clip, [w
d
((++1
1,
E z
[| ff I an) clip, [wy (on, ]n]]] + Ee.,
where the second line uses that ||A, ff (TT an) 1, and the last line plugs in (23). Next, using Lemma E.2-(b) in the above inequality, we get that
40 (e
7,80)
7(1))
(A) S
E
Exe+1)
(clip,,.o) [u (on,, an)))
+ Ec.
(24)
9
160
Further splitting the first term, and using that (a + 6)² < 2n² + 262
we have that
E get+1)
(clip,,co) [o0 (zh, [=
dh ((++1) (xn, (wh,an)) 1)
di (I an)
(tt)
2 [mo[0]]
< 2
(((+)) dh
clip,.00
+ clip,,c0
h
clip,co)
+ dy
2.
dh (I an)
an)) 1)
|ctp,
d T++1)
< 2E (++))
clip,.c))
di [(+1) (xn, (m...a))
+ +2700 clipy00
clip,.00
1,
1l (Ihs and) ( an)
< 2 ((+3)
clip,.co
+ 27
where the second line holds since ||wll2d S ||/l|oo////l l/lll and clip,. [w]] S (0)) for any w. and the last line is due to (23). Using the above bound in (24), we get that
80
(ming
(#n, an) dh (In, (I) an)
()
700
(A)
E
E
7000
+4 10300
7000
80
80 <
d (Inh an)
((0)
E,(0))
+ 45. + 10,300
+
700
d
(Ih, (x an)
80r2
26

---

Published as a conference paper at ICLR 2024
80
(Ih an) (Th ah)
E d
+ 4G: + 10,3 +
dh
80t
where the second line simply follows from a change of measure, and the last line holds since 7(1) = 76, and 1 td
Bound on clipping violation.
Since Ifu 2 2) S for any v 2 0, we get that
d (1h, an) 7(0) di d (x))))))
1
d (x an)
(B)
E
?
d (Ih, an))
where the last line holds since y = yt.
Combining the bounds on the terms (A) and (B) above, and summing over the rounds t 2,...,
we get
Σ EIAnf an)] S
81
Σ
E
de (z and
10
Σ
Σ
Ex
(25)
7 t=
dx (I an)
80
t=2
For the first term, using Lemma E.3, along with the bound || 11000 S Coov get that
(In, an)
Σ
E
20
< 55Crav log(1 + T)
dett an)
For the second term, we have
T
T
36yl log (6) (6
72-T log (07
gio
<
K(t- 1)
K
Combining these bounds, we get that
E 0 (' an]]= =0 -
Coov log(1 [Tl HT5-1)
T
Σ
& 7 log(T)
7
(26)
Plugging this bound to (22) for each h E [H]] gives the desired result.
E.4 PROOF OF THEOREM 3.1
In this section, we prove generalization of Theorem 3.1 that accounts for misspecification error when the class W can only approximately realize the density ratios of mixed policies. Formally, we make the following assumption on the class W:
Assumption 2.2 (Density ratio realizability, mixture version, with misspecification error). Let T be the parameter GLOW (Algorithm 1). For all E [M]. E I1, 1 E [T], and ((::)) (1it) (x, a) E Wh. such that
(T711) ..... 00) II, there exists weight function w
d
(1i)
(1i))
sup #ell
w
S Eapx
(1:t)
d
1.d
Note that setting Eaps above recovers Assumption 2.2' given in the main body.
Theorem 3.1'. Let > O be given, and suppose that Assumption 2.1 holds. Further, suppose that
Assumption 2.21 (above) holds with Eapx 5/1181. Then, GLOW, when executed classes F and W
27

---

Published as a conference paper at ICLR 2024
with hyperparameters T (((1CC))/2))) log((=(()//s), K = and (1gg// returns an e-suboptimal policy with probability at least 1 after collecting
H
=
log( log((=(111//)
(27)
E²
irajectories. addition, for any M,, with the same choice for and ry as above, the algorithm enjoys regret bound of the form
T
Reg == -( Õ( Coeu (l + Hapa
(28)
1=1
Clearly, setting the misspecification enror Eupx O above recovers Theorem 3.1.
Proof of Theorem 3.1'. First note that by combining Assumption 2.2t with the fact that clip,,[2] is 1-Lipschitz for any y > 0, we have that for any E [H] and t E [T'. there exists weight function w/ Wh. such that
10
sup
co
clip,,)) [w]]]]
S
Expx.
(29)
11
1,4g
Using this misspecification bound, and setting K = 1 in Lemma E.4, we get that with probability at least 1 8,
Reg- = Σ J(T') - - (H + T)
T
log(1
+ # + HT
1=1
Further setting 7 /Con/ (To(F)/))T implies that
Reg < 20 (og() (10 + HT''sp
(T)
For the sample complexity bound, note that the returned policy is chosen via 7 Unif([ ""..,, (²))),, and thus
(((=*))-(AA)) = ((T)) J( so H
T
Ceon 1og(7))oo( + H
T
Hence, when Eupx S Oz/H)), setting T T= 3 H² log (01(6)) implies that the returned policy î satisfies
B[J(T") J(m) S
The total number of trajectories collected to return an E e-suboptimal policy given by
T.K K 5 H2
(0g(61111(18)))))
E.5 PROOF THEOREM 3.2
In this section, we prove generalization of Theorem 3.2 in Theorem 3.2' (below) which accounts for misspecification error when the class W can only approximately realize the density ratios of pure policies. Formally, we make the following assumption on the class W.
Assumption 2.2 (Density ratio realizability, with misspecification error). For any policy pair (2)) E Wh, such that
n2 II and h E [H), there exists some weight function wh
g
sup
w
(2)
< Eax
dp
1.d7
28

---

Published as a conference paper at ICLR 2024
Setting Fapx above recovers Assumption 2.2 given in the main body.
Note that Assumption 2.2F only states that density ratios of pure policies are approximately realized by Wh. On the other hand, the proof of Lemma E.4, our key tool in sample complexity analysis, requires (approximate) realizability for the ratio /' /2tt+) in Wh, which involves mixture of occupancies. We fix this problem by running GLOW larger class W that is constructed using W and has small misspecification error for d (a(++) for all < T. Before delving into the proof of Theorem 3.2', we first describe the class W.
Construction of the class W. Define operator Mixture that takes in sequence of weight functions {woh) ..... w(") } and a parameter s T, and outputs function [Mixture(w ,..., ;t)) : such that for any I, a X' A.
MMxturee (w w ()) == Ennuni((()) [,, (v.a)] a)]
Using the operator Mixture, define W via
W [Mixture w(t) ...., ;t)
t) :0) "e.,,,,,,""""
w E W}.
and then define
W = U
(30)
As result of this construction, we have that
| S (DWI+ 1)" S (2/W1)".
(31)
In addition, we define Wn fun w WJ. The following lemma shows that W has small misspecificatioon eπror for density ratios of mixture policies.
Lemma E.5. Let t 2 0 be given, and suppose Assumption 2.2$ holds. For any sequence of policies n x(1) E 11, and h E [M], there exists a weight function wū E WWo such that for any >> 0,
sup clip,
clip, [WN)]
< >
1,47
where recall that dz
Di= di
The following theorem, which is our main sample complexity bound under misspecification error, is obtained by running GLOW on the weight function class W.
Theorem 3.2'. Let > 0 be given, and suppose that Assumption 2.1 holds. Further, suppose that Assumption 2.2% holds with capx S fc2 H²). Then, GLOW, when executed on classes F and W (defined in Eq. (30)) with hyperparameters T = (HH-w//))) K = (T log((F(lW1/s), and / /OunfT returns e-suboptimal policy से with probability at least - 8 after collecting
H C2
N = Ō
coy
log((F11w1/s)
trajectories.
Setting the misspecification error Eapx 0 above recovers Theorem 3.2 in the main body.
Proof of Theorem 3.2'. Using the misspecification bound from Lemma E.5 in Lemma E.4 implies that with probability at least 1 8,
J(m)) J(x(0) =
HCoov log(1 + T)) +
HT log F HT8-1)
+ 2T273 Caps + + +HHlog(T) log(T)
K
1=1
Using the relation in Eq. (31), get that [W] < (2(W))T and thus
Σ J(m*) [(x o HCoovv log(1 + 7)
HT log(6) HT8-1)
277 + +7Hlog(T)
? +
29

---

Published as a conference paper at ICLR 2024
Setting K = 27 (og(6/ and VCp in the above bound, we get
T
Σ - J(F <0(( =0
+ T' (O /ConT
Finally, observing that the returned policy मे
,..,,,,.")) we get
[( -(x())) 50
Ceov
H
log(T) + HC Eaps
T
1=1
Thus, when Epp S 0c29/22 n1), setting T O Cav e²
log (gz))) )) in the above bound implies that - S.
The total number of trajectories collected return e-suboptimal policy is given by:
H CoN
T K O0
log (FIWWITT--)))
Proof Lemma E.5, Fix any h E [H] and E [T]. Using Assumption 2.24, we have that for any I t, there exists a function / k/11)) E W, such that
d
sup xlll
wh
(..1)
S
Eapx:
(32)
1.47
Let Wp [Miture x, E X' x A, define
t (.)) (,,0),)s,, 0),, E WR, ho and recall that d(++2) (n-(ui(((()) [d% For any
((x, a) =
min
.7 { min
(x,a)) E (nnUnif((t) twonn (x, a)l .7
(ni((()(()))
de (aaas//ff)) (a.aa)
Using that the function g(>) = min f 2
max(= is 22 --pisschitz we get that
(x,, a)
C(r, a) 522 (n-Uni(((e))
Ee-unir(()) (woh (x, a)]
di (z,a)
de (x,
I 2n² (n-
wh w
(x, a))
(x, ()).a)
where the last inequality follows from the linearity of expectation, and by using Jensen's inequality. Thus,
d (2h, an) (In, an) ,,7
) min ün (In, an).
sup Esg an TEll
min
d
sup Exn [C(2n an)l #ell
((a)
< 72 sup E Unif(((( tell
w
(9.))
1,17
(
< 7 E Ex- (1t) sup sell
(a.t)
h
1.47
< 7 Expx:
where the second-to- -tst line is due to Jensen's 's inequality, and the last line follows from the bound in (32).
30

---

Published as a conference paper at ICLR 2024
F PROOFS AND ADDITIONAL RESULTS FROM SECTION 4 (HYBRID RL)
This section is organized follows:
Appendix F.I gives additional details and further examples of offline algorithms with which we can apply H2O, including an example that uses FQI as the base algorithm.
Appendix F.2 includes a detailed comparison between HYGLOW and purely offline algo- rithms based on single-policy concentrability.
Appendix F.3 includes a discussion on generic reductions from offline to online RL using a class of algorithms we call optimistic offline RL algorithms.
Appendix F.4 contains the proof of the main result for H2O, Theorem 4.1.
Appendix F5 contains supporting proofs for the offline RL algorithms (Appendix F.I) we use within H2O.
F.1 EXAMPLES FOR H₂O
This section contains additional examples of base algorithms that can be applied within the HzO reduction.
F.1.1 HYGLOW ALGORITHM
For completeness, we state full pseudocode for the HYGLOW algorithm described in Section 4.2 as Algorithm 3. As described in the main body, this algorithm simply invokes H2 with a clipped and regularized variant of the MABO algorithm (MABO.CR, Eq. (9)) as the base algorithm.
We will invoke MABO.CR with a certain augmented weight function class W, which we now define. For any W, let w(th E (X' x A [H] IR U { (+x0)) be defined by
WA (z. a)
h = V if + h
(k) h''
(I, a) = {0
(33)
and let Woo) (w(h) w E W). Define the set
W = (W URE(H] (Wa)) U (-WWo)))
(34)
Note that the size satisfies W is [ S 2 + 1)|WI S 4H|W).
We recall that the MABO.CR algorithm with dataset D and parameters 7, FF, W is defined via
f arg min max NEW
EDA
ün an) (n) an The #h+1 a' [ (2n, ax)]. (35)
where (1)) : (0) and Wn == (mi [v0))
In Appendix F.5.2 we will prove the following result.
Theorem F.1 (MABO.CR is CC-bounded). Let D (D consist of H samples from t ...., m) For any 7 E R4,, the MABO.CR algorithm (Eq. (9)) with parameters F, augmented class W defined in Eq. (34) in Appendix F.I.1, and 7 CC-bounded at scale y under the Assumption that Q* E F and that for all π E II and h [H). d7/v/ E W.
The risk bound for HYGLOW will follow by Theorem 4.1. Namely, we have the following.
Theorem 4.2 (Risk bound for HYGLOw). Let > be given, let Dat consist of H T samples from data distribution v, and suppose that u satisfies C--single-policy concentrabil- ity. Suppose that Q F and that for all
TT], E II, and h E [H), we have G7/111 E W, where ph = 1/2(1h + 1/2 Et dr. Then, HYGLOW (Algorithm 3) with inputs T ((( 1og((Fl111/)), F. augmented W defined in Eq. (34), 7 and Doi returns an e-suboptimal policy with probability at least 1 8T after collecting N = Ō HP 1og(1=11W1/8) trajectories.
θ
(C.+CColl/TT (og(1=
31

---

Published as a conference paper at ICLR 2024
Algorithm 3 HYGLOW: H₂O MABO.CR
input: Parameter 7 E N, value function class F, weight function class W,, parameter y [0, 1].
offline datasets Doff {Doff, a hn each of size T.
1: Set -700) = =y i, a 4/-'0) and go = (127/K) k)- log(0)F1I)))H/))
2: Initialize D on. D hybrid,, Ø for all h [H]
3: for t = i..... I do
4: Compute value function fro) such that
( arg min max SET
Σ
E 20u hybrid,
(xn an) an))) (ne (h -a Eayy
[ [nl]
"ybriid
(36)
where e == clip,, [w] and an fn(x, - max, (2',
5: Compute policy T( + f(t).
6: Collect (x1, 01, (1,,, (HH, 0H, TH) using π. D((+1) = D(t) on, U (( an Th, #n+1))
7: Aggregate offline and online data: hybrid, == Dott, U Dutth for all h E [H].
8: output: 7 Unif(TT (T.,,
F.1.2 COMPUTATIONALLY EFFICIENT IMPLEMENTATION FOR HYGLOW
In the following, we expand on the discussion after Theorem F.1 regarding computationally efficient implementation of the optimization problem in Eq. (9) and Eq. (36) via reparameterization. Let y and n. > 0 be given to the learner, and suppose that in addition to the class W, the leamer has access function class W(..)) that satisfies the following assumption.
A Assumption F.1. The function class W())) satisfies
(a) For all Wir:: and h E [4]. |w S yn.
(b) For all h E [H], (=clip,, E W] S WKx
(c) For all h E [A]. (t w E W] C WKr"), where with is defined as in Eq. (33).
Note that W also satisfies the density ratio realizability required by MABO.CR (ef. Theorem F.1). We claim that optimizing directly over the class Wy(.)), which does not involve explicitly clipping, leads to the same guarantee as solving Eq. (9). In more detail, consider the following offline RL algorithm, which given offline datasets (Du)nigt returns
H ED,
ie arg min max JEF WEW(
(n an) An an, The xh+1) ED, I (an,
(37)
Using the next lemma, we show that the function obtained by solving Eq. (37) leads to the same offline RL guarantee as MABO.CR when [log(W(.)))
(logg()V) poly (H)). In particular, substituting the bound from Lemma F.1 in place of the corresponding bound from Lemma F.6 in the proof of Theorem F.1, while keeping rest of the analysis same, shows that the above described computationally efficient implementation of MABO. BBO.RR is also CC-bounded. Using this fact with Theorem 4.1 implies the desired performance guarantee for HYGLOW (similar to Theorem 4.2).
Lemma F.1. Suppose F and W satisfy Assumption 2. and Assumption F.4. Additionally, let E (0, 1) and n > be given constants, and for h HH), let Dr. be datasets of size sampled from the offline distribution ph (n Furthermore, let War.) be reparumeterized function class that satisfies Assumption F.I w.r.. W. Then, the function f returned by Eq. (37), when executed with datasets (Dn weight function class Wir.), and parameters (n 5n satisfies with probability least -8, 8,
Σ
[ an) wo (Ih, an)
50
Σ
E (1)))
(wo ana)²] 112 (rm)
ph
7m
for all w E W, where Bin = =0(200 -- log(24[F]|W))H
32

---

Published as a conference paper at ICLR 2024
Proof of Lemma F.1. Repeating the same arguments in the proof of Lemma E.2 with K = 1 (we avoid repeating the arguments for conciseness), along with the fact that |lwn lloo I yn for all h E [H] and w' E (y get that the returned function f satisfies for all w' e Myt
E ( (In) an) (2h; an) s SOL
Σ
1 m
E
Hm
log log(IFI]Wt {1)0)
However, as in the proof of Lemma F.6, since for any w E W we have that both cl [w E W%
and -n [1 E Wh for every h E [H], the above inequality immediately implies that for
every W.
H
H Σ
Ham log log(FFl|M (H/0))
[An]( an) in (xn, an)) =
E (10))
E yn
nt n-1
where we used that the RHS is independent of the sign. The final statement follows by plugging in that (log(W)))) Ollog (W)) + poly(H)).
F.1.3 FITTED Q O-TTRRATION
In this section, we apply HzO with the Fitted Q-Iteration (FQI) algorithm (Munos, 2007; Munos and Szepesvári, 2008; Chen and Jiang, 2019) as the base algorithm. For an offline dataset D and value function class F, the FQr algorithm is defined as follows:
Algorithm F.2 (Fitted Q-Iteration (FQr).
1. Set TH (1,, a) for all (a, a)
2. For h 1:
Ih E arg min Eo,, [Ja(Ia, - -hh- - max fuEFn
a²
3. Output के z
We analyze FQr under the following standard Bellman completeness assumption. Assumption F.2 (Bellman completeness). For all {H), we have that Tr,Fr+1 S Fb.
Theorem F.3. The FQr algorithm is CC-bounded under Assumption F22 with scaling functions ay 9 and by = 1024 (2g F.r all y > 0 simultaneously. As a consequence, when invoked within H,O, we have Risk S Õ(H HCH./C.+Car (C.+Com) (og((F(6-)1//) with probability at least 1 1- 8T.
The proof can be found in Appendix F.5.3.
The full pseudocode for H₂O with FQr is essentially identical to the Hy-Q algorithm of Song et al. (2023), except for slightly different data aggregattion strategy in Line 7. Thus, Hy-Q can be interpreted as a special case of the H₂O algorithm when instantiated with FQI as a base algorithm. The risk bounds in Song al. (2023) are proven under structural condition known as bilinear rank (Du et al., 2021), which is complementary to coverability. Our result recovers a special case of a risk bound for Hy-Q given in the follow-up work of Liu al. (2023), which analyzes Hy-Q under coverability instead of bilinear rank.
F.1.4 MODEL-BASED MIE
In this section we apply H2O with Model-Based Maximum Likelihood Estimation (MLE) algorithm the base algorithm. The algorithm is parameterized by model class M (Ma) where Mn [M, X' x A A x X)). Each model M (Mr | E M has the same state space, action space, initial distribution, and horizon, and each M,, E Mr is a conditional distribution over rewards and next states for layer h. For dataset D, the algorithm proceeds follows.
1
Algorithm F.4 (Model-Based MLE).
For h E [M]
33

---

Published as a conference paper at ICLR 2024
Compute the maximum likelihood estimator for layer h
MR arg max M,E.Mi.
Σ
log(Ma((Th. Ihe kn)an))
(38)
(2t (0 o (2t7%h
Output "3r the optimal policy for M (Mr
We analyze Model-Based MLE under standard realizability assumption.
Assumption F.3 (Model realizability). We have that M E M.
Theorem E.5. The model-base MLE algorithm is CC-bounded under Assumption F.3 for all 0 simultaneousty, with scaling functions a, and by = H As a consequence, when invoked within H2O, we have Risk -
1/T) with probability at least
1 17.
The proof can be found in Appendix F.5.4.
F.2 COMPARISON TO OFFLINE RL
In this section, we compare the performance of HyGLOW to existing results in purely offline RL which assume access data distribution with single-policy concentrability (Definition 4.3)
Let μ be the offiine data distribution. Let write w == d//n w² == d= and V for the optimal value function The most relevant work the PRO-RL algorithm of Zhan et Their algorithm is computationally efficient and establishes polynomial sample complexity bound under the realizability of certain regularized versions of w" and V*. By contrast, our result requires Q"-realizability and the density ratio realizability of w* for all II, but for the unregularized problem. These assumptions are not comparable, as either may hold without the other. Their sample
complexity result is also slightly larger, scaling roughly as Ō ""CCOP ((PP(C.+Coo)/e) However,
where C.,e the single-
5
policy concentrability for the regularized problem, as opposed our approach requires additional online access while their algorithm does not.
To the best of our knowledge, all other algorithms for the purely offline setting that only require single-policy concentrability either need stronger representation conditions (such as value-function completeness Xie et al. (2021a)), are not known to be computationally efficient in the general function approximation setting due to the need for implementing pessimism (e.g., Chen and Jiang (2022)).
F.3 GENERIC REDUCTIONS FROM ONLINE TO OFFLINE RL?
Our hybrid-to-offline reduction O₂O and the CC-boundedness definition also shed light the question when offline RL methods can be lifted to the purely online setting. Indeed, observe that any offline algorithm which satisfies CC- CC-boundedness (Definition 4.2) with only R-coverage term, namely which satisfies an offline risk bound of the form
Riskoff S
>>x
Egpp [ER (F n² (10), yn)] + by?
(39)
can be repeatedly invoked within OzO (with Doit Ø) to achieve small / /Con/T-type risk bound for the purely online setting, with no hybrid data. This can be seen immediately by inspecting our proof for the hybrid setting (Theorem F66 and Theorem 4.1).
We can think of algorithms satisfying Eq. (39) as optimistic offline RI. algorithms, since their risk only scales with term depending on their own output policy; this typically achieved using optimism. easy to see, that GLOW and GOLF (Jin et al., 2021a; Xie et al., 2023) can be
In particular, interpreted as repeatedly invoking such an optimistic offline RL algorithm within the H₂O reduction. This class of algorithms has not been considered in the offline RL literature since they inherit both the computational drawbacks of pessimistic algorithms and the statistical drawbacks of "neutral" (i.e. non-pessimisttc) algorithms (at least, when viewed only in the context of offline RL).
In more detail, as with pessimism, optimism is often not computationally efficient, although furthermore requires all-policy concentrability (as opposed to single-policy concentrability) to
34

---

Published as a conference paper at ICLR 2024
obtain low offline risk. On the other hand, neutral -on--eesimmistic) algorithms such FQI (Chen and Jiang, 2019) and MABO (Xie and Jiang. 2020) also require all-policy concentrability, but more computationally efficient. However, reduction shows that these algorithms might merit further investigation. In particular, it uncovers that they can automatically solve the online setting (without hybrid data) under coverability and when repeatedly invoked datasets generated from their previous policies. We find that this reduction advances the fundamental understanding of sample-efficient algorithms both the online and offline settings, and are optimistic that this understanding can be used for future algorithm design.
F.4 PROOFS FOR H₂O (THEOREM 4.1)
The following theorem is slight generalization of Theorem 4.1. In the sequel, we prove Theorem 4.1 as consequence of this result.
Theorem F.6. Let T E N be given, let Doff consist of H T samples from data distribution v. Let Algont be CC-bounded at scale 7 E [0, under Assumption()), with parameters a- and by. Suppose that V E [T] and "",,...,,""" T II, Assumption(11)) M*) holds for n²) :=
(1/((n) + +1/ d% >>kr-- Then, with probabiliyy at least 1 8T, the risk of H2O (Algorithm 2)
with T, Algan. and Dof is bounded as
2a
H
+0((
00 H
(Cooray b,,
Risk
(=
(40)
=leffafi
Proof of Theorem F.6. Recall the definitions d/ = di d
E.= dh and = 1 Z
=
Furthermore, let dz = d% for all h < H. Note that the data distribution for Dio Dhybrid is n (p h= where /4, (vn + + where V/ is the offline distribution. As a result of Definition 4.2,
the offline algorithm lggo invoked on the dataset D hybrid outputs a distribution pt. ~ A(II that satisfies the bound:
E (0 [1(TT) - [ S
(CCa(TT, ,," ,,,,t) + E E,t (CCA(TT)) " ,t),)t)) + by,
A=1
(41)
with probability at least 1 - 6, where a, and b. are the scaling functions for which Algof is CC- bounded at scale 7. By taking a union bound over T, the number of iterations, we have that the event in Eq. (41) occurs for all < T with probability greater than 1 8T.
Plugging in the definition for the clipped concentrability coefficient above and summing over t from 1. T, get that
Reg Σ J(xt) - (T
E
H
T'
(+)
clip,t
a
E,
clip
+
HTb,
yt
mpt
h=1
1.dg
1,
(II)
For each h [H], bound the two terms I and II separately below. Term (I). Note that u (x, a) 2 un (I, a)/2 for any x, Thus,
d
11 S 20
clipat
2a,
CC ,4,
Vh.
1,dg"
1=1
We define risk for the hybrid setting as in Eq. (1). Our result is stated a bound on the risk the optimal policy x², but extends to give hound on the risk of any comparator with C. replaced by coverage for
35

---

Published as a conference paper at ICLR 2024
Term (II).
We bound this term uniformly for any x/ ~ pr. So, fix x00) and note that
T
dh (c, a) Hi (x, a) 7
(II) = d
E
min
(=1
cd (I, a)
d d a)
d (z, a) d
71 m1))
d,
(c)
Ph (z,
I
2% (x, 5T1
E (
71.
H (z, a)
(1I.A)
(LI.B)
where the second line holds since min min(u, = all(u lu I o) + vI (u < <u) for all u. U.E.R.R R.R
In order to bound the two terms appearing above, we use certain properties of coverability, similar to the analysis of GLOW (Appendix E). For parameter À (0, 1), let us define burn-in time
Th T (x,a) a) = min (z) > Ceov 17, a)
(42)
and observe that
T
Σ
E L
<
(2)
Σ
E
(x, S
2C
(43)
x
1=1
2,0 1<TT) (CTT (2.a)
which holds for any x (0, 1). This bound can be derived by noting that
Σ Σ
(x, = Σ / (Ir
J.0. (
Σ
do (e.0)) 12 (1, a) + Σ
(oWM (I, a)
F.a
3,
Ceon
$ Σ
14 (2,,a)
Σ
Coouth (2,
A
F.a
I,a
1
2Ccov
< Coov
+1
We also recall the follow bound, which is a corollary of the elliptical potential lemma (Lemma D.5):
T
l a) (1, llt > To (x) S
T
( Lo (z, 1lt > Th a)) S 5 5log(T))cov (x, a)
Σ Σ d
(I,
de
[=1 2.0
1=1
3,
(44)
The inequality (i) can be seen derived by noting that, under the event in the indicator, we have 7 (a, a) 2 Coow (x, a) and thus d
(z. a) N (Ccov) a) ( a)). This gives
T
d0 (z, He th (c. ))) < 2
T
(x,)))
do (x, a) dio a) + (r,
(0())))
2.0
t=1
25.
from which we can repeat the steps from Eq. (19) to Eq. (20).
Term (ILA)..
To bound this term, we introduce split according to the burn-in time (x, a), i.e.
(IL.A)
Σ
T
1
1
E
10
(1, a) 1x
de (x, a) 11 (I,
S srt (u(t S Th (x, + llt Th (
t=1
The first term is bounded via
T
d (z. a) 1A
/ d (I,
s sTefitt= s th (x, <> Σ Bgo [u[t S (x,
E (
(I,a) a)
14 (x,a)
2yCca
36

---

Published as a conference paper at ICLR 2024
by Eq. (43) with À 1. The second term is bounded via:
(
dd (z. P (x, a) 1/ (I, a)
(x, a)
I nt stf (x)
2
1
EE
(0)
(1r a) d (x.a)
1[t Th (z, a)}
T
de (2 11
x (x,
(x,0)
1=1
< 10 10 Ccov:
by using that p (x,a) 2 2. (r.a) and Equation (44).
Adding these two terms together gives us the upper bound (II.A) S 27ycou + 10 100log(T)Cco-
Term (IIB). We have
T
de (I, a) P/ (x, a)
N
[z,
}
yell
(I.a)
Coow (2, a)
1
200)
(I. (xx,) 0)
h
(i)
E di
[I{t S Th
(1/2) (1 [x,a)}]
(=1
4Ccov 4Ccov
7
where the inequality (i) follows from applying the upper bounds d (x, S Coou (2x, a) and (a,, 2 Tit (z, a), and the inequality (ii) follows from the definition of the burn-in time (Eq. (42)) with x 7/22
Combining all the bounds above, get that
(II) < 2a, C2n + 10
+ 2Ccov)
4a, (y + 10 log T) + 1).
Adding together the terms far, conclude the regret bound:
Reg S 2a,
ΣΣ CC,( "1ll"",,,,, (t) + H(4s (4a, Ceov (y + 10log(T) + 1) + Tb,).
follows that the policy
= Unif( ,...,, (T) satisfies the risk bound
2a.
H
T
CC,(TT" + H (4 4 4 Coon
Risk <
(7 10log(T) + 1) by
T
T
:eerr
2a
H
T
CC,( + 0 +0
T (((Co + by, ).
Ccovay
T
with probability at least
8T, where in the last line we have used that y E [0, 1].
We now prove Theorem 4.1 as a consequence of Theorem F.6.
Theorem 4.1 (Risk bound for H2O). Let T e N be given, let Don consist of H T samples data distribution v. and suppose that satisfies C, C.-single-policy concentrability. Let Algoft be CC- bounded at scale 7 E (0, 1) under Assumption(.), with parameters a. and b,, Suppose that V tt E [T] and n (1) 2.... (0 E IT, "), M*) holds for p (1/2(1n + 1/2 Ei=1 di D
37

---

Published as a conference paper at ICLR 2024
Then, with probability least 1 8T, the risk of H2O (Algorithm 2) with T, Algoff and Dof is bounded as
Risk < zō(1) ar (C. + Ccou) + by b..))
(8)
T
Proof of Theorem 4.1.
Under the assumptions in the theorem statement, Theorem F66 implies that
Risk I
2a,
Σ
H
T
CC,
(4,7)) H
(
Ccov (7 + (0 +1 by.
T
h=1
Since max; maX
di (a.a) (araa
S C.. we have (T*
, ,t,tt E C., so we can simplify the first
term above
2a
H
T
2a C.
T
6a, Hlgg(T),
(C
(1)t)
H
T
T
T
1=1
(T). Combining with the remainder of using the bound on the harmonic number Σ 1/1 < 3 (T) the risk bound in Theorem F.6 gives us
Risk < T (6C. log(T) + (T + (T) 1))++ =ō =0(1) (ay(C, + Ccov). + by) ).))
Hay
T
where we have used the fact that y E [0, 1].
Corollary F.1. Let T N and Das consist of H ' samples from data distribution Suppose
that for all t E [T] and T(), 7(1) E II, Assumption( _M)) holds for μ == {2/2(V%
1/2 Ei di (1) H h=1-- Let Alg be CC-bounded scale 7 E [0, 1] under Assumption(-) and with parameters a, = and by = by. Consider the H2O algorithm with inputs T, Algon and Don-
Then,
If Algof is CC-bounded at scale 7 = (VoCur/oO) and T such that y E [0, 1), we have
ab ΣΣ CC, +0 H
Ccovab
Risk <21 TC h=1t=1
T
with probability greater than 1-
If satisfies C.-single-policy concentrability and Algon is CC-bounded at scale @ @VValc++Co))o) and T is such that E [0, 1), then
Risk S (H(W/iC.CCwwaaap
with probability greater than 1 8T.
Proof of Corollary F.1. We start with the first case. We recall the definition of errai appearing in
Theorem F.6:
erroff H ( + 8log() +1 +b,,) 6.) =ō(m) (H(CConl,
CCov T
+ b,, ))
and the risk bound from Theorem F.6.
H
T
2a. T
Risk <
CCA (C',,,,,,,0)) (,) + erroff
(45)
1=1t1
"We define risk for the hybrid setting as in Eq. (1). Our result is stated bound on the risk the optimal policy x², but extends to give hound the risk of any comparator with C. replaced by coverage for
38

---

Published as a conference paper at ICLR 2024
Plugging in ay 7t and b, by into erroff gives
erf H 4 7T Coon (7+8log(T) + 1) + by))
The above is optimized by picking = =2 Sip (8 (8)oo(())))))) + 1). Plugging this in gives us
effoff = H (VV abC log(T) + +1
aCcov T
ab abCcov
=ō
+
T
as desired. For the second result, recall from Theorem 4.1 that the risk bound when v satisfied C. co-eetieyy
Ha, (6C, log(T) + 4Ccov( (y + log(() + 1)) + Hb..
Risk & T
Plugging in ay and b, by gives us
Ha
Risk <
T7 T (6C, log(T) + 4C (7 & + 1)) + Hbb.
This expression is optimized by a(6C, log gives us the risk bound
4C2d(7+ (7g
which when substituted
Tb
ab (6C, log(T") + 4Ccov (7 8log(T)+ +1) 0(1 ((11()
(1(VCC
/C, + (CCoo)oa aab
Risk < 2H
T
T
as desired.
F.5 PROOFS FOR H2O EXAMPLES (APPENDIX F.1)
F.5.1 SUPPORTING TECHNICAL RESULTT
Lemma F.2 (Telescoping Performance Difference (Xie and Jiang (2020, Theorem 2); Jin al. (2021b,
Lemma 3.1))). For any F, have that
H1
J(x*) J(T)) <
Σ A=1
E Bag [TaJ4+1( ax) - (1n, an)] + BBay' [Jn( an) - TTJaei an)).
This bound follows from a straightforward adaptation of the proof of Xie and Jiang (2020, Theorem 2) to the finite horizon setting.
Lemma F.3. For all policy и value function E F, timestep E [H), data distribution
(un) ) h- where μr A(X x A), and 7 E 1R,,, we have
di an.) Jun (1h,, an.)
d (Zh; an) 14h (Th, an)
Esg Anf](E ax)] S En,,
[Anf(an, an) clip,,
+ 21p=
7)
Similarly,
dd ( an)
di (2 ab) Pr (In, an)
Eag Bagl-(Ans(anh... an) < Eyn (=xAn]((x),ah)) an)) clip,
+ 2
> >7
M4 (1n. on)
where recall that [Anf == fn(a, a) [Tnf4+1((,,0)
Proof of Lemma F.3. In the following, we prove the first incquality. The second inequality follows similarly. Using that f( a)) < for any x, X A. we have
Exg A1 an) < Es; [[An.] fl an) 11pp an) * 0J + Eay [l ax) = 0}}.
For the second term, for any 0,
d (Kn, an)
} 7
dh an) H4n (2p, an)
Eag (T4s (2n,, an) = 03} s Egg [
= =
>
(a an)
39

---

Published as a conference paper at ICLR 2024
For the first term, using that u I min(u, 2) ullfu 2 2) for all u, O, and that [[Anff S for any 2, a E X x A, we get that
Eag [[Axf an) (In and # 0}}
4 (Th. and pun (Tn aph)
Mulann and # #0} 03)
Bpn
[nf]( an)
< Epn
[an] an)
clip,
di (Ens anh
Iu [un((nnaa)) and + 03}
Mh (In, a1p
di (2h and I
d (2hh, an)
>y Huu and 0} }
+ Bus
(n and
ue (2h,
(on, an) Mh (1n,
d (2 an) Mbh (Tin an)) > >
Epn [Anf(ern, an) clip,
[un( and + #0} + Eaz II
Furthermore, also note that
di (2h, and pm (In, an)
Eun
[Anf(CEn an) clip,,
[un an) 03}
d7 ( an) μhh (Ti, an))
Σ
un (xn an) [In an) -cli,
0.
(#).0n) s.t. pa (1)
The final bound follows by combining the above three terms.
Lemma F.4. For any policy n,, data distribution μ {un 1 where pn A x A), scale y R+ and horizon h E [H], we have
di (Eh,aa))
2 clip,
dg
p
14h (Th, atts)
14h
1,47
Proof of Lemma F.4. Note that
(Th,, an)
d (zh: and
p
>
Edg
I
14h (2h, ahh)
Nh (Ih, an
d (1 and
7
Edy
11
(n, a) + 7 -dl (Jh, (bh)
2
2
di (Nh, an))
7
Mn (In, ah) + 7
d% (Ih, ah)
2
d (Th: an) pnn (In, an)
dh
1847
clip,,
clip,
7
1.
where the first inequality follows from
> -1 (I. a) > ph (x, = 7 dx > +
and the second inequality follows by Markov's 's inequality.
Lemma F.S. For any policy n, data distribution ?' R,,, and horizon [H], have
{un) where pa E A(X x A), scale
2
clip,
2
clip,
pb
2,H
1.45
Proof of Lemma F.5. Beginning with the left-hand side, we have,
d (Zh, an) Mn (M((nnaa))
(i)
(
[ (Z an.)
di dT an) Men (wn, an) 57)
E,,, min
< 2 E,,,
I
[In, un)
40

---

Published as a conference paper at ICLR 2024
d (2 an)
d (z an)
+ 2 wn
7
7/
Ma (T an)
( anl)
(ii)
di (kh. an)
of di (In. and
di (I an) Men (T anh)
- 2 Bag
5 Men (e anh)
+ 2 Bug
27]
Pu [IN, an)
(ii1)
min di (2h, and)
2 Ez
ph (T ah
In (i), we have used that for all E RT min u, oj S uu < < + /uollf < u} and that (u+v)² S 2(u² +(u²+u²), thus that min (u, o}² I 2(u21fu + u}). In (ii), we have done
a change of measure from μu to d% In (ii)), we have used that min(u, v) = wll(u S {0) +ulu < u).
F.5.2 PROOFS FOR MABO. (PROOF OF THEOREM F.1)
Suppose the dataset = {Di JN is sampled from the offline distribution p( In this section, we analyze our regularized and clipped variant of MABO (Eq. (9)). We analyze MABO.CE under the following density ratio assumption. Recall for any sequence of data distributions ,(") p1 we
denote the mixture distribution by p {o (11))) H h- defined by ph (1=m) := E Uh
Assumption F.4. For given sequence of data distributions nt) .... p!) we have that for all πT E II, for all h [H],
E W.
We first note the following bound for the hypothesis if returned by MABO.CR.
Lemma F... Let D | be dataset consisting of H samples from pet) ...... "...,,"))),. Suppose that F satisfies Assumption 2.1 and that W satisfies Assumption F.4 with respect to p Let I be the function returned by MABO.CC given in Eq. (9), when executed on (Du) with parameters y, and the augmented weight function class W defined in Eq. (34). Then, with probability least
1 1-8, 8, we have
H
Σ A=1
B gand
[ an) wn ( an)
Σ
20 7(u))
E (.))
(Wn(Is,
an)) 7 33 (46)
Mn
h=
for all w E W. where 8(0) == 36y
log (2g(24)7
Proof of Lemma F.6. Repeating the argument of Lemma E.2 (a), we can establish that Q* satisfies the following bound for all h [H], E W:
ED, (1 Q an, rh, (hr4)) wn (vn, an)] s ED, (a (win(an,
(2 an)) "|] + g(,) (47)
with probability at least 1 - 6, where (n) = 8/y(0) and (3t0 = 30-/"//n log(G) (G H/8) ( S
367"'//--1 [og24
Going forward, we condition on the event that this holds. Now,
since the right-hand side of Eq. (47) is independent of the sign of uh, we can apply this to - E W conclude that
ED.. (AA,Q") an, Th, xh41)) wh (xA, an) < ÆD, (a . (wh (wn, (IN, an)) + 800
Summing over h E [H] and taking the max over E W, we can conclude that:
H
Σ ED, ((A, on, Fhy x)) (xn, an) -Eo
Ez. (a (ann))n)))) $ H
max
WEW
By Assumption 2.1 and the definition of the hypothesis f returned by MABO.CR, we have:
H Ep, (IAn) an, The 2h+ iby, (xn, an) - ED, [o (In) $ =
Σ
H3
max
WEW
41

---

Published as a conference paper at ICLR 2024
and in particular the bound that for all W
ED, (IAn] an, Th, ph41) th (2 an))
Σ
ED,
a
(#n an)) Hm
h=1
Repeating the argument for Lemma E.2 (b), we can conclude that for all to E W
H
E (1:)) Ak
[An an) uu (Tn, (In, am)]
S
H
20 7/m)
E Mb
(1:)
(1on ax))² +
7H
18
h=1
h=1
Applying this to wht) W and to -w E W, and again noting that the right-hand side is
independent of the sign of úú we can conclude that for each h E (H), W:
E (1)) AA
[ an) in am)
20 $ ymn)
E ( [(0n(x an)))
7H
18
Summing over h E [H] gives the desired bound.
Theorem F11 (MABO.CR is CC-bounded). Let = D= (Di)a= consist of H n samples from p .....y pd0) For any y RR,, the MABO.CR algorithm (Eq. (9)) with parameters F, augmented class W defined in Eq. (34) in Appendix F.I.I, and is CC-bounded at scale under the Assumption that Q' E F and that for all π E II and E [H), 42/14/ E W.
Proof of Theorem F.1. Let R nz. Using the performance difference lemma (Lemma F.2), note that
H
H
S
B
E
an) + Σ
E [IAn] an)..
(48)
h=1
However, note that due to Lemma F33 and Lemma F44, we have that
di (Eh: an)
11
4
d
ER [[Anf( an))] s E (m)) (IAnf( on clipp
clip
(1m)
(Ih, and
ym
(1:)
1.45
(49)
and,
Edg [(-1A an))) E am))
(-IAn an)))
dh (In,
+ mm
4
clipyn
d
14
(1m) (I an)
(
(50)
We bound the terms (I) and (II) separately below. Before we delve into these bounds, note that using Lemma F.6, we have with probability least 1 --d. ó,
H
Σ
(
in (IAn (x))
20 p(m) ( (m)) (1
(Ih, an)) < H2 3m (51)
max WEW Am1
(1m) (
18
where ((0)
36mm I-1
log 12 Moving forward, we condition the event under which
Eq. (51) holds.
Bound on Term (I). Define w via W0p
Timn and شي = clipyn
di Lim
and note that due to
Assumption F.4, we have that w W. Thus, using (51). we get that
a00 [[- (-IA )i) (E an) <
no [(-AAn) a. )ix (xh, an)
h=1
42

---

Published as a conference paper at ICLR 2024
1f
20
7
E
(1)))
[ (2 an))²] +
gmn)
Ph
18
1=1
20
7
clip Hiiimm[wnlli
2:04 (1:0 + 12 g(m)
7(0)
18
h=1
40 clip pm
[wi]]
H²² 3
18
where the last step follows by Lemma F.5 and the definition of whe
Bound on Term (II) Define w = [ha) and मं clip and again note that due to
Assumption F,4, we have that W/ Wh. Thus, using (51), and repeating the same arguments as above, we get that
40 7(m)
7 -/1 3m
(II)
clip...
wu +
18
h=1
Plugging the two bounds above in (53) and (54), and then further in (52), and using the definitions for wh. and wi. we get that with probability at least 1 - 6,
40
5
14
-(x*) - ((F)
clipyyn
clip
clip.n.
g(
7
14
Ldg
^=1
yn
n
H
1,d
18
11
ddip
+
/lip
d
+
14
g(n)
7(m)
1/ (1)
18
1,45"
1.48
40
(IC,(TT', ( (mm) CC2,
(#, ( (mmm),
(mm) 28H22
n 7
10g(24/71
y(m)
40
(CCa (nT ( s mm) + p 100777711
yn
40 and which establishes that the algorithm is CC-bounded for scale y, with scaling functions a, 7 b, = 56077>
Theorem 4.2 (Risk bound for HYGLOW). Let > be given, let Dost consist of H T samples from data distribution v, and suppose that v satisfies C.-single-policy concentrabil- ity. Suppose that Q F and that for all TT, E II, and h E [H], we have 0 E W. where 1h = 1/2(1n + Et dz Then, HYGLOW (Algorithm 3) with imputs T @((HA(ContO))))) 1og((F)))1/)),, F. augmented W defined in Eq. (34), 7 θ CC.+Cool/THH (0((1=11011))) and DoH returns an e-suboptimal policy with probability at least
1 8T after collecting N Ō HHA(C.t (F 10g(1=1111/6)) trajectories.
Proof of Theorem 4.2. This follows by combining Theorem F.1 with Corollary F.I.
F,5.3 PROOFS FOR FITTED Q-ITERATION (FOT)
In this section we prove Theorem F.3.
We quote the following generalization bound for least squares regression in the adaptive setting.
43

---

Published as a conference paper at ICLR 2024
Lemma F.7 (Least squares generalization bound; Song et al. (2023, Lemma 3)), Let R > 0, E (0, 1).
and H + [-R, R] a class of real-valued functions. Let D = { y1) (TT, Vr } be a dataset Tf points where z₁ 1e 1::2-1))111))) and yt h- (z+) E for some realizable ht H and Et conditionally mean-zero, i.e. Elye xe] = ht (24)). Suppose max, [yv| I and max lh (x)) S R. Then the least squares solution arg millnen at least d,
y1) satisfies that with probability
T
Σ
E Euup (((x)))((x))) & 256R 12g(2171/6).
Using the above theorem, we can show the following concentration result for FQL.
Lemma F.8 (Concentration bound for FQI). With probability at least 1 - 6, we have that for all h [H].
a
(Fa(or) (Th,))))))TT+ (T 21
(1m) (IA,)
E ao mn
log F1H/6)
1024
Proof of Lemma F8. Fix h + 1. Consider the regression problem induced by the dataset D₁. {(=/), ) where =/h (z) ,a(²) ~ 1/ and y/²² r( max,' fh+1 (o)tt,aa)) This problem is realizable via the regression function Ely 2% h (2 = T fatz (x)))))) E F, and
satisfies that lo).' I 2, [h* (xfx)1 < 2. In this regression problem, the least squares solution from Lemma F.7 is precisely the FQI solution, so by Lemma F.7 we have
E "a (1m0 (Fa(an, un)
1
E (Zn
(Ta(Hn, as) (TThr))(nn)))
i=1
log (2
1024
with high probability. Taking union bound over E [H] gives the desired result.
Theorem F.3. The FQr algorithm is CC-bounded under Assumption F.2 with scaling functions ay @ and by 1024 (on f. for all y > 0 simultaneously. As a consequence, when invoked within H,O. we have Risk < Ö H (C.+Con) log(1 ()/r) with probability least 1-8T
Proof of Theorem F.3. Let i nz. Using the performance difference lemma (given in Lemma F.2),
note that
H Egg [I.
-
<
E g
an) + Σ
IIAn an).
(52)
1=1
h=1
However, note that due to Lemma F.3 and Lemma F.4, we have that
(Tn: an)
1]
4
di
Ex [1AAA an))) < E Kh (m))
([Anf clip
clip
14
(1))
(I an)
yn
14/
(3m)
1.4
(
(53)
and,
d (Ih, and
di
Egg= ((-1Ar,,<E,, an))l (m
[=IAn)(2E,, an )clip,
+ mm
clip,y
11 (Nny 0nh
(1:n)
(1)
(54)
44

---

Published as a conference paper at ICLR 2024
Bound on Term (I)
Note that
(IAnA(0n, an))
di (Tnn an) Mn m (In, (n))
11
-
E (g
2 [(An)) and)
B (12..)))
clipyn
d (1hh ab)
1) 27
1/ (/h (2 an.)
log (2g(2(F]H)
dh
2048
clip
n
(1:m) Ph
2,4
where the second line follows from Cauchy-Schward and the last line follows by Lemma F88. AM-GM inequality implies that
2048 log(2)F11 H))
di
clip,.
clip
+ 2048 (2
7
(Tom3
2,04
(1:m)
2
m/
ym
(Tin)
2, (1:))
1
d
<
2
ym
clipyy
pm
LPh
(3rm
1.
+ 2048 20488og(2|
where the last line is due Lemma F.5.
Bound on Term (II). Repeating the same argument above for x", we get that
2 clip
dh
(II)
S
+
(2
(1:m)
7
1,45
Combining the above bounds implies that
H
2
[|ctip...
dh
-(x*)- -
+
clip ym
h
+ 2048 (1)
(1mn
[1m)
7m
ym
1,dg"
[1
1.
H
2
(CCA(TT, u ,2) CCn (F, ((()), ()) 2048 1og(2)F1/H)
y
which shows that For CC-bounded at scale 7 under Assumption E2, with scaling functions a., 2
and by = 2048 [)
It remains to show the stated risk bound when For is applied within H2O. This follows by applying Corollary F.I.
F.5.4 PROOFS FOR MODEL-BASED MLE
In this section we prove Theorem F.5. We quote the following generalization bound for maximum likelihood estimation (MLE) in the adaptive setting.
Agarwal et al. (2020, Theorem 18)). Consider sequential conditional probability estimation setting with an instance space Z and a target space y and conditional density ply 2). We are given F (Z x y) + R. We are given a dataset D {(2,, WO] where 2t ~ Di = De(21a11. V1:1-1) and yt ~ p(- 21). Fix E 1), assume [F] < 00 and there exists f* F such that f^ 2) p(u 2). Then, with probability at least 1 8,
Lemma F9 (MLE generalization bound;
Σ
E Exppr
1f-1 (((12))ff( ( 12) s 2 log((F))))
where
f E arg max JEF
log f(y 21)
Recall the notation that each model M E -M defines a conditional probability distribution of the form M(r of a). We apply the above generalization bound our setting obtain the following.
45

---

Published as a conference paper at ICLR 2024
Corollary F.2. Under Assumption F.3, we have that the model-base maximun likelihood estimator of Equation (38) satisfies
E (1:m) | wh, an) - ( Wh, an))
1:2 tv
S log([
vh E :
Note that we have taken an extra union bound over H so that the MLE succeeds each layer. This is easily seen to imply an error bound between the associated Bellman operators.
Corollary F.3. Let [7 f](2, = ((ra))) + max f(x', d')l denote the Bellman optimal-
ity operator of M, and T denote the Bellman optimality operator of M Then we have that for all E [H] and for all f :. A A- 1}.
(Thif( and - [Thf (TT)))))a))) ) $ log(IMMHH/8)
E
(1.0) Ph
Proof Corollary F.3. Notice that
[Trff(x, a) (T, a) E (( (r.a")=((((a))) r+ mmx max f(x',a') .4)]
max f(z', a')
a
< 2 Ma a) - M, x, a)
Theorem F.S. The model-based MLE algorithm is CC-bounded under Assumption F,3 for all y >> O simultaneously, with scaling functions ay and b, invoked within H2O, we have Risk S Ö(H, /C., Com Ing( 1//T) with probability at least 1- 8T.
As consequence, when
Proof of Theorem F., We note that Corollary F.2 implies a squared Bellman error bound for VTT the optimal value function for M, since
Yz (Th - (TQ M ( (z, 1Th ((,
by the optimality equation for 177 Thus we have
(Qiz (Th, an) (TQ M7 1 an) ) 27 log({MMHH/))
vh E H E (
(55)
This is enough to repeat the proof of CC-boundedness for FQr (Theorem F.3), with Q taking the place of the FQi solution f. Indeed, the only algorithmic property that we used for FQi was Lemma F.8, which also holds for M by Equation (55). Tracking the slightly different constants
resulting gives us the desired values for a., and by.
46


Reviews:
[{"review_id": "qcGe8kRbSi", "reviewer": "Reviewer_4ukw", "summary": "The convergence of offline and online reinforcement learning theories has led to the emergence of density ratio modeling in offline RL. However, this concept has been absent in online RL due to the challenge of collecting a comprehensive exploratory dataset. This paper introduces GLOW, an online RL algorithm that can explore and learn efficiently when there is an exploratory distribution with good coverage (coverability condition), even in the presence of value functions and density ratios. GLOW handles unbounded density ratios through truncation and employs optimism for exploration, but it is computationally inefficient. To address this, a more efficient variant called HYGLOW is introduced for Hybrid RL, combining online RL with offline data. HYGLOW is derived from a meta-algorithm called $H_2O$, which offers a provable reduction from hybrid RL to offline RL.", "questions": "The idea of using density ratios in online RL is new. However, I am still curious about the specific benefits for online RL. Does it enlarge range of MDPs which can be solved by online RL algorithms (it may be computationally inefficient)? What is the advantage of using density ratios for guiding exploration in online RL compared to other classical methods like Upper Confidence Bound ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is fairly well organized and the problem is well motivated (to analyze the notion of density ratio in online RL). \n\n2. The theoretical guarantee is solid and the explanation of concepts is also very comprehensive.", "weaknesses": "While the paper primarily delves into theoretical aspects and introduces the GLOW algorithm with statistical guarantees, it's worth noting that GLOW is computationally inefficient. Therefore, there is a need to develop more computationally efficient variants to showcase the algorithm's practical effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ge3Jnx1IQ1", "reviewer": "Reviewer_reZc", "summary": "This paper endeavors to establish a bridge between offline and online reinforcement learning. More specifically, it introduces a novel algorithm named GLOW, which excels at conducting sample-efficient online exploration while assuming the presence of value-function and density-ratio realizability. Furthermore, the authors extend these findings to encompass the hybrid reinforcement learning setting.", "questions": "see the Weakness part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well-crafted, presenting its content in a clear and easily understandable manner. The majority of the results are extensively scrutinized and discussed, adding to the paper's overall quality. The introduction of a new density-based online algorithm effectively bridges the gap between offline and online RL. Furthermore, the paper's concerted effort to tackle the enduring and vital issue of removing the completeness assumption is a critical contribution to the field. This problem has long been a pressing concern in online reinforcement learning and is integral to the significance of this work.", "weaknesses": "- Bypassing the need for strong completeness-type assumptions by introducing an additional density ratio realizability assumption is not a novel approach, particularly in the context of offline reinforcement learning (see [Zhan et al., 2021] and a missing related work [1]). So the results in this work are not very surprising.\n\n- Dentity-based algorithms may not be as suitable for online reinforcement learning, given the perceived strength of Assumption 2.2. While the authors have included two examples in Appendix D.1, these examples are already familiar to us and do not pose a significant challenge. If the authors could provide additional examples, such as those involving low (Bellman) eluder dimension or bilinear class, it would make the results more remarkable. \n\n[1] Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning. Hanlin Zhu, Paria Rashidinejad, Jiantao Jiao", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sWbRA7uCgs", "reviewer": "Reviewer_xDdp", "summary": "This paper provides theoretical results adapting the idea of density ratio modeling from offline RL to the setting of online RL and provides sample complexity guarantees for the proposed algorithms. The main contribution of the paper is the algorithm called GLOW which provides polynomial sample complexity bounds in the online RL setting by minimizing the weighted average Bellman error using clipped density ratios along with realizability assumptions in function approximation. To further improve the sample efficiency, authors propose a meta-algorithm H2O that can reuse any offline algorithm to output an online exploration policy in the Hybrid RL setting (i.e. online RL with some available offline data). \n\n\n\n*I would also like to note here that I am perhaps not the target audience of this work and though I am aware of some of the related works on this topic, I may not be the best judge of this paper's contributions.*", "questions": "1. Why did the authors not consider empirical verification of their proposed framework in Sec 4? Is there any understanding of the validity of the assumptions made in the paper when applied to RL algorithms in practice?\n\n2. In the first line on page 4, \"that $\\frac{d^\\pi_h}{d^{\\pi'}_h}$ for all ...\", is there some missing text after $\\frac{d^\\pi_h}{d^{\\pi'}_h}$?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper exhaustively compares to the relevant prior work in the field and positions the contributions of this work with the literature in offline and Hybrid RL. In several parts of the paper, authors intuitively explain some of the challenges faced in adapting the density ratio modeling to online RL and the need for certain regularization formulations to achieve desired approximation error bounds. These add to the readability of the paper. \n\n2. This paper claims to be the first to provide theoretical guarantees showing that value function realizability and density ratio realizability alone are sufficient for sample-efficient RL under coverability. It is a step towards unifying some of the advances made in offline RL with the requirements of sample-efficient online RL algorithms.", "weaknesses": "While the paper focuses on providing theoretical bounds regarding sample efficiency of the proposed algorithms, it lacks any attempts at empirical verification of the same. Comparing to Song et al. which the authors highlight for introducing the Hybrid RL setting, I would expect similar experiments (eg. Song et al. present experimental results in Montezuma's revenge) in this paper to demonstrate the performance of the theoretically motivated framework in practice. Perhaps it would also help to include a discussion of the practicality of the assumptions made in the theoretical proofs and what, if any, are the challenges of implementing the proposed algorithms in standard RL benchmarks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)