On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling and Beyond
Authors: Thanh Nguyen-Tang
Raman Arora
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning
offline reinforcement learning
TL;DR: A new notion of data diversity for sample-efficient offline RL and a new result showing that algorithms based on version spaces, regularized optimization and posterior sampling achieve comparable sub-optimality bounds.

Abstract: We seek to understand what facilitates sample-efficient learning from historical datasets for sequential decision-making, a problem that is popularly known as offline reinforcement learning (RL). Further, we are interested in algorithms that enjoy sample efficiency while leveraging (value) function approximation. In this paper, we address these fundamental questions by (i) proposing a notion of data diversity that subsumes the previous notions of coverage measures in offline RL and (ii) using this notion to \emph{unify} three distinct classes of offline RL algorithms based on version spaces (VS), regularized optimization (RO), and posterior sampling (PS). We establish that VS-based, RO-based, and PS-based algorithms, under standard assumptions, achieve \emph{comparable} sample efficiency, which recovers the state-of-the-art sub-optimality bounds for finite and linear model classes with the standard assumptions. This result is surprising, given that the prior work suggested an unfavorable sample complexity of the RO-based algorithm compared to the VS-based algorithm, whereas posterior sampling is rarely considered in offline RL due to its explorative nature. Notably, our proposed model-free PS-based algorithm for offline RL is \emph{novel}, with sub-optimality bounds that are \emph{frequentist} (i.e., worst-case) in nature.

On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
Thanh Nguyen-Tang Johns Hopkins University Baltimore, MD 21218 nguyent@cs, juu edu
Raman Arora Johns Hopkins University Baltimore, MD 21218 arora0cs. juu. edu edu
Abstract
We seek to understand what facilitates sample-efficient learning from historical datasets for sequential decision- becision-making, a problem that is popularly known as offline reinforcement learning (RL). Further, enjoy sample efficiency while leveraging (value) function approximation. In this paper, we address these fundamental questions by (i) proposing a notion of data diversity that subsumes the previous notions of coverage measures in offline RI. and (ii) using this notion unify three distinct classes of offline RI algorithms based on version spaces (VS), regularized optimization (RO), and posterior sampling (PS). We establish that VS-based, RO-based, and PS-based algorithms, under standard assumptions, achieve comparable sample efficiency, which recovers the state-of-the-art sub-optimality bounds for finite and linear model classes with the standard assumptions. This result is surprising, given that the prior work suggested an unfavorable sample complexity of the RO-based algorithm compared the VS-based algorithm, whereas posterior sampling is rarely considered in offline RI due explorative nature. Notably, our proposed model-free PS-based algorithm for offline RI. is novel, with sub-optimality bounds that are frequentist (i.e., worst-case) nature.
interested in algorithms that
Introduction
Learning from previously collected experiences a vital capability for reinforcement learning (RL) agents, offering broader scope of applications compared to online RL. This is particularly significant in domains where interacting with the environment poses risks or high costs. However, effectively extracting valuable policies from historical datasets remains considerable challenge, especially in high-dimensional spaces where the ability to generalize across various scenarios crucial. this paper, our objective is to comprehensively examine the efficiency of offline RI. in the context of (value) function approximation. We aim to analyze this within the broader framework of general data collection settings.
The problem of learning from historical datasets for sequential drcision-making commonly known as offline RL or batch RL, originated in the early 2000s [Ernst et al., 2005, Antos et al., 2006, Lange et al., 2012] and has recently regained significant attention [Levine al., 2020, Uehara et al., 2022a]. In offline RL, where direct interaction with environments is not possible, our goal is to learn an effective policy by leveraging pre-collected dltasett,, typically obtained from different policies known as behavior policies. The sample efficiency of an offline RL algorithm is measured by the sub-optimality of the policies it executes compared to a "good" comparator policy, which may or may not be an optimal policy. Due to the lack of exploration inherent in offline RL, designing algorithm with low sub-optimality requires employing the fundamental principle of pessimistic extrapolation. This means that the agent extrapolates from the offline data while considering the worst-case scenarios
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

that are consistent with that data. Essentially, the diversity present in the offline data determines the agent's is ability to construct meaningful extrapolations. Hence, a suitable notion of data diversity plays a crucial role in offline RI..
To address the issue of data diversity, several prior methods have made the assumption that the offline data is uniformly diverse- - this implies that the data should cover the entire trajectory space with some probability that is bounded from below [Munos and Szepesvári, 2008, Chen and Jiang, 2019, Nguyen-Tang et al., 2022b]. This assumption is often too strong and not feasible in many practical scenarios. In more recent approaches [Jin et al., 2021b, Xie al., 2021, Uehara and Sun, 2022, Chen and Jiang, 2022, Rashidinejad et al., 2023], the stringent assumption of uniform diversity has been relaxed to only require partial diversity in the offline data. Various measures have been proposed to capture this partial diversity, such as single-policy concentrability coefficients [Liu et al., 2019, Rashidinejad et al., 2021, Yin and Wang, 2021], relative condition numbers [Agarwal et al., 2021, Uehara and Sun, 2022], and Bellman residual ratios [Xie et al., 2021]. These measures aim to quantify the extent to which the data captures diverse states and behaviors. However, it should be noted that in some practical scenarios, these measures may become excessive or may not hold at all.
In terms of algorithmic approaches, existing sample-efficient offline RL algorithms explicitly construct pessimistic estimates of models or value functions to effectively learn from datasets with partial diversity. This typically achieved through the construction of lower confidence bounds (LCBs) [Jin et al., 2021b. Rashidinejad et al., 2021] or version spaces (VS) [Xie et al., 2021, Zanette et al., 2021]. LCB-based algorithms incorporate a bonus term subtracted from the value estimates to enforce pessimism across all state-action pairs and stages. However, it has been observed that LCB-based algorithms tend impose unnecessarily aggressive pessimism, leading to sub-optimal bounds [Zanette et al., 2021]. On the other hand, VS-based algorithms search through the space of consistent hypotheses to identify the one with the smallest value in the initial states. These algorithms have demonstrated state-of-the-art bounds [Zanette et al., 2021, Xie et al., 2021].
In contrast LCB-based and VS-based algorithms, regularized (minimax) optimization (RO) and posterior sampling (PS) are more amenable to tractable implementations but are relatively new in the offline RL literature. The RO-based algorithm initially introduced by [Xie et al., 2021, Algorithm 1] incorporates pessimism implicitly through regularization term that promotes pessimism in the initial state. This approach eliminates the need for an intractable search over the version space. However, Xie et al. [2021] demonstrate that the RO-based algorithm exhibits significantly slower sub-optimality rate than standard VS-based algorithms. Specifically, the RO-based algorithm achieves a sub-optimality rate of K --15 1/3, whereas VS-based algorithms achieve a faster rate of K 4-11 1/2, where K represents the number of episodes in the offline data.
On the other hand, posterior sampling (PS) [Thompson, 1933, Russo and Van Roy, 2014], a popular and successful method in online RI., is rarely explored in the context of offline RI. PS involves sampling from a constructed posterior distribution over the model or value function and acting accordingly. However, PS is less commonly considered in offline RL due to its explorative nature, which stems from the randomness of the posterior distribution. This randomness well-suited for addressing the exploration challenge in online RL tasks [Zhang, 2022, Dann et al., 2021, Zhong et al., 2022. Agarwal and Zhang, 2022]. The only work that considers PS for offline RL is Uehara and Sun [2022], where they maintain a posterior distribution over Markov decision process (MDP) models. However, this model-based PS approach is limited to small-scale problems where computing the optimal policy from an MDP model is computationally feasible. In addition, this work only provides a weak form of guarantees via Bayesian bounds.
In the context of (value) function approximation, achieving sample-efficient offline RL relies on certain conditions that facilitate effective learning. The identification of the minimum condition required for sample efficiency, as well as the algorithms that can exploit such conditions, is an important research question that we aim to address here. We advance our understanding by making the following contributions: (I) We introduce a new notion of data diversity that subsumes and expands all the prior distribution shift measures in offline RL, and (II) We show that all VS-based, RO-baser and PS-based algorithms are in fact (surprisingly) competitive to each other, i.e., under standard assumptions, they achieve the same sub- optimality bounds (up to constant and log factors). We summarize our key results in comparison with related work in Table 1. Our results further expand the class of sample-efficied efficient offline RL problems (Figure 1) and provide more choices of offline RI. algorithms with competitive guarantees and tractable approximations for practitioners to choose from.
2

---

Algorithms
Sub-optimality Bound
Data
VS in [Xie et al., 2021]
Bby (lb/))( (a(())-l(([])))))) [TT))] K
1
RO in [Xic ct al., 2021]
[byCC(s]- v/in(1F (T)) --10))---1/----0 Hb/vT
I
MBPS in [Uehara and Sun, 2022]
Hby Cleees In M K-1/2 (Bayesian)
1
VS in Algorithm
Hby //a:1//R) [n( [[))) Hb/ VT
A
RO in Algorithm
Hb Clm [ (-))) k-1/2 Hb/
A
MFPS in Algorithm
Cl1; (n( (I))) K-// Hb/ /T (frequentist)
A
Table I: Comparison of our bounds with SOTA bounds for offline RL under partial coverage and function approximation, where gray cells mark our contributions. Algorithms: VS = version space, RO regularized optimization, MBPS = model- posterior sampling, and MFPS model-free posterior sampling. Sub-optimality bound: = #number of episodes, π an arbi- mary comparator policy, H horizon, 6 boundedness, T = the number of algorithmic updates, In [F11, In [IT==fe(T) In [T J, In [M]: complexity measures of some value function class F, "in- duced" policy class 11 (T)) the class of all comparator policies 11s8t and model class M, where typically (T) c I| VT. Data: I = independent episodes, A adaptively collected data. Here C(R;;1 /K) and (2(
measures of extrapolation from the offline data to target policy æ.
For establishing (II), we need to construct concrete VS-based, RO-based and PS-based algorithms. While the key components of the VS- us-based and RO-based algorithms appear in the literature [Xie et al., 2021], we propose novel, a first-of-its -f--i--kind, model-ffre The algorithm contains two new ingredients: pessimistic prior that encourages pessimistic value functions when being sampled from the posterior distribution and integration of posterior sampling with the actor-critic framework that incrementally updates the learned policy.
posterior sampling algorithm for offline RL.
Overview of Techniques. Our analysis method presents a "decoupling" argument tailored for the batch setting, drawing inspiration from recent decoupling arguments in the online RL setting [Foster et al., 2021, Jin et al., 2021a, aa Zhang, 2022, Dann et al., 2021, Zhong et al., 2022, Agarwal and Zhang, 2022]. The core idea behind our decoupling argument is establish a relationship between the Bellman error under any comparator policy π and the squared Bellman error under the behavior policy. This relationship is mediated through our novel concept of data diversity, denoted C(T;; Ee). which is defined in detail in Definition 3. This allows to separate the sub-optimality of a learned policy into two main sources of errors: the extrapolation error, which captures the of-distrinution (OOD) generalization from the behavior policy to target policy, and the in-distribution error, which focuses on generalization within the same behavior distribution. The OOD error effectively managed by controlling the data diversity C(T; ec), while the in-distribution error is carefully addressed by utilizing the algorithmic structures and the martingale counterpart to Bernstein's 's inequality (i.e., Freedman's inequality).
In the process bounding the in-distribution error of our proposed PS algorithm that we built upon the technique of Dann et al. [2021], we correct a non-rigorous argument of Dann et al. [2021] (which we discuss in detail in Section E. and develop new technical argument to handle the statistical dependence induced by the data-dependent target policy in the actor-critic framework. Our new argument carefully incorporates the uniform convergence argument into the in-expectation bounds of PS. We give detailed description of this argument in Section E.3. As an immediate application, our technique fixes a technical mistake involving how to handle the statistical dependence induced by the min player in the self-play posterior sampling algorithm of Xiong et al. [2022].
Background and Problem Formulation
2.1 Episodic Time-inhomogenous Markoy Decision Process
Let S and A denote Lebesgue-measurabbe state and action spaces (possibly infinite), respec- tively. Let P(S) denote the space of all probability distributions over S. We consider an episodic time-inhomogencous Markov decision process M A,,, where P (Phhne[H)
3

---

{S x A + P(S)) are the transition probabilities (where [H] := (1...,HH)r fra.h e {S x A R] is the mean reward functions, and H E N is the length of the horizon for each episode. For any policy π = hae E {8 + P(A)}", the action-value functions and the value functions under policy are defined, respectively, Th (8,a) E r re(Ss;;a) | s]. Here E. denotes the expec-
(sh, an) as.. and V.. (s) En B<'Ei (s), tation with respect to the randomness of the trajectory (sh: ah..... SH, aH), with a; Ts(+(s;)
and 81+1 ~ P,(- a,) for all i. For any policy म, we define the visitation density probabil- ity functions dī = [d hemm where p is the Lebesgue measure on S x A and Pr((*h, an) = (8, a)(m, M) is the probability of policy reaching state-action pair (s,a) a) at timestep h. The Bellman operator Tē is defined as (T, a) == ra(s, a) + P. (-11-11-11)))))) [Q(s', a')], for any Q S x A + RR. Let x be an optimal policy, i.e., Q7 (s 2 Q7, a), v(s, a, TT S x A x [H] x II"l where I1 := {S + {(A)] is the set of all possible policies. For simplicity, we assume that the imitial state 91 deterministic across all episodes. We also assume that there is some > 0 such that for any , 8H uH TH) generated under any policy, [r S b, vh and |E rul s almost surely.2 This boundedness assumption is standard and subsumes the boundedness conditions in the previous works, e.g., Zanette et al. [2021] set 6 and Jin et al. [2021b] use b H (and further assume that Ta E [0, 1]. Vh). Without loss of generality, we assume that Z 1.
{S A R+}" (s, == (=)(s))a)==(sa)))))))
dp(s.a)
trajectory ($1, #1, fi,...,,
Additional Notation. For any S A + R and any π S + P(A), we overload the notation (T. == Eawa(-ls) [u(s, a)]. For any f S x A + R, denote the supremum norm || = max (aa (f(s, a)]- We write E[g]² == (E(g))² For a probability measure v on some measurable space (S2 B), we denote by supp(w) the support of v, supp(v) = (B E B (BB > 0}.
We denote S y to mean that x = Oly).
2.2 Offline Data Generation
Denote the pre-collected dataset by D == {(s) ah. MeM) B[r afj] (sh, (.)) We consider the adaptively collected data setting where the offline data is collected by time-varying behavior policies {μ]]e[[]] concretely, defined as follows.
he(M) where sh++1 ~ Ph(-1s%, af)) and
te[k]
Definition (Adaptively collected data"). n²th is a function of (15 ah rf (h))nele))
1E(k-11 Ak E [K].
n², For simplicity, we denote f = E = setting of adaptively collected data covers a common practice where the offline data is collected by using some adaptive experimentation [Zhan al., 2023]. When jd²
# d= and F, = Ex= [.. The
f recovers the
setting of independent episodes in Duan et al. [2020].
The goodness of learned policy á = (D) against comparator policy m for the underlying MDP M is measured by the (value) sub-optimality defined as
Value sub-optimality.
SubOpt M (#) = VT((s)) (s
Whenever the context is clear, we drop M in Q Vgr d and SubOpt (+)).
2.3 Policy and function classes
Next, we define the policy space and the action-value function space over which we optimize the value sub-optimality. We consider (Cartesian product) function class FF F x x FH e {S x A 6,6 The function class F induces the following (Cartesian product) policy class
'This assumption is merely for the sake of clean presentation which does affect any results.
2 Note that we allow the reward samples to be negative.
We replace the condition [rul 6, Vi with Suu--Gaussian condition: rı. Ha (Sh, an) wherein Ru (sn. an) nab-Gaussian with mean (sk. an)) - which replaces à our main theorems by + In(K H/ 't is essentially the "measurabilityy" condition in Zanette et al. [2021] and "compliance" condition in Jin
al. [2021b].

---

(T) = of (T) x... x (T),
(T), where a (T) == {m)(a)s) x exp(n Ei= (s ())
E g. F.. Vi nn [o.1]] for any T N. The motivation for the induced policy class [1 is from the soft policy iteration (SPI) update where we incrementally update the policy.
We now discuss set of assumptions that we impose on the policy and function classes.
Assumption 2.1 (Approximate realizability). There exist hEnlhe(m where &n 2 Ouch that, inf [a((s, un) - Q7 (n)) S En. wh E {M).
sup TI on Esupp(df) FEF
Assumption 2.1 establishes that F can realize Q for any π E (T) up to some error & E R## in the supremum norm over the jr-feaible state-action pairs. It strictly generalizes the assumption in Zanette et al. [2021] which restricts εn = O, Yh (i.e., assume realizability) and the assumption in Xie et al. [2021] which constrains the approximation error under any feasible state-action distribution.
The realizability in value functions alone known to be insufficient for sample-efficient offline RL [Wang et al., 2021]; thus, one needs to impose a stronger assumption for polynomial sample complexity of model-free methods." In this paper, we impose an assumption on the closedness of the Bellman operator.
Assumption 2.2 (General Restricted Bellman Closedness). There exists v E RR such that inf I15% - To S Shh, wh E [H].
sup P R.F.
Assumption 2.2 ensures that the value function space F and the induced policy class IT (T) for any 7 E N are closed under the Bellman operator up to some error v E Rd in the supremum norm. This assumption is direct generalization of the Linear Restricted Bellman Closedness in Zanette et al. [2020] from a linear function class to a general function class. As remarked by Zanette et al. [2021], the Linear Restricted Bellman Closedness is already strictly more general than the low-rank MDPs (Yngg and Wang, 2019, Jin et al., 2020].
2.4 Effective sizes of policy and function classes
When the function class and the policy class have finite elements, we their cardinality [Ful and |n
(T) to measure their sizes [Jiang et al., 2017, Xie et al., 2021]. When they have infinite elements, we use log-covering numbers, defined as
dy(c) = max In NCc; Fu, Il lloc), and dn( max In (C;; (T)) (I),,1- hE[H]
he|d]
where || 11,00 = sup.es SA [m(as) - x r'(als) for any n, n' E {S - P(A)) and ((e; X, || II) denotes the covering number of a pseudometric space (X, || [I) with metric [Zhang, 2023, e.g. Definition 4.1].
We also define a complexity measure that depends on a prior distribution po over F that we employ to favor certain regions of the function space, Our notion, presented in Definition 2, is simply a direct adaptation of a similar notation of Dann et al. [2021] the actor-critic setting.
Definition 2. For any function f' E Fot1 and any policy â ITall, define Fi = (J
Fn |f f I E), for any 2 O, and subsequently define
d = sup
Σ
Po. Po (R( (6(e = sup
Σ In
Pa (c Q
TEN.JEF
The quantity da(e) and (e) measures the concentration of the prior pa over all functions f f F that are e-close (element-wise under T and e-close (element-wise) Q respectively. If stronger version of Assumption 2.1 is met, i.e., Q E Fr. Vn E 11a h E [M]] we have (e) < do(e), Ve. For
'A stronger form of realizability sufficient for polynomial sample complexity, e.g., realizability density ratio w.r.t the behavior state-action distribution in dual- quil-primal methods [Zhan et al., 2022, Chen and Jiang. 2022, Rashidinejad et al., 2023] or realizability for the underlying MDP in mosel-bbsed methods [Uehara and Sun. 2022]. Instead, pursue model-free value-based methods.
5

---

the finite function class F and an uninformative prior (f.) = 1/1 under a stronger version of Assumption 2.2, i.e., V/ 0, Vh, we have do(e) - Σi In [Fx In F... For parametric model, where each fn f% is represented by d-dimensional parameter 0 E Df R prior over Ω2 induces a prior over F. If each 0g is compact, we can generally assume the prior that satisfies sup, In -.. S (cln/c//e) for some constant co. If fn = =sī is Lipschitz in we can assume that supg In Po.n (6 [-))))))) S eid In(e2/e) for some constants c1 c2. Overall, can assume that do(e) & (d /22/ fe). A similar discussion can be found in Dann et al. [2021].
3 Algorithms
Next, we present concrete instances of PS-based, RO-based, and VS-based algo- rithms. The RO-based and VS-based al- gorithms presented here are slight refine- ments of their original versions in Xie et al. [2021]. The PS- PS-based algorithm is novel. All three algorithms resemble the actor-critic style update, inspired by Zanette et al. [2021]. We refer to this generic framework as GOPO (Generic Offline Policy Optimization) presented in Algorithm 1. At each round f, critic estimates the value O of the ac- tor (i.e., policy T²) using the procedure CriticCompute on Line 3, and the actor improves the policy using a multiplicative weights up- date [Arora et al., 2012] (Line 4). After T iterations, GOPO returns a policy á that is sampled uniformly from the set of the obtained policies {T' )ee(T)
Algorithm 1
GOPO(D, T. CriticCompute
Generic Offline Policy Optimization Framework
Input: Offline data D, function class F, learning rate
7) > 0, and iteration number T
1: Uniform policy π² = { [TTHe
2: for t 1...., T T do
3:
Q' = CriticCompute
(x' .D.....)
4:
f (als) x o exp()))) ((s,))
5: end for
Output: म Uniform( ( ((fform((=))e((11)))
To incorporate the pessimism principle, a critic should generate pessimistic estimates of the value of the actor x' in Line 3. This is where the three approaches differ each invokes different method to compute the critic. Here, we provide a detailed description of the critic module for each approach. To aid the presentation, we introduce the total temporal difference (TD) loss T.a, defined as (f., fh+2)=+))= = E (fnn, fh+1;2 where 24, = (sh, ah, Th 1h+1), 2 = (s), (8++11,, #))2.
k a Te $h-1):
and (Jh, (b) = (Jn()), ax) -
Version Space-based Critic (VSC) (Algorithm 2). Given the actor n², at each step E [H].
VSC directly maintains a local regression constraint using the offline data: Lgee Su+1) S infgez (gh. fn+1) + B, where 3 is confidence parameter and (.((-.)) is serving as a proxy to the squared Bellman residual at step h. By taking the function that minimizes the initial value, VSC then finds the most pessimistic value function Q' from the version space F(3; m²) C F. In general, the constrained optimization Line 2 is computationally intractable. Note that minimax variant of GOPO+VSC first appeared in Xie et al. [2021], where they directly perform an (intractable) search over the policy space, instead using the multiplicative weights algorithm (Line 4) of Algorithm 1.
Regularized Optimization-based Critic (ROC) (Algorithm 3). Instead of solving the global constrained optimization VSC, ROC solves arg inf fEF (Afi(s1, m1) Lax (f)), where À is regularization parameter and L, (f), defined in Line of Algorithm 3. Note that in ROC, pessimism is implicitly encouraged through the regularization term Af1 (81, 7²). We remark that, unlike VSC, ROC admits tractable approximations that adversarial training and work competitively in practice [Cheng et al., 2022]. Note that a discounted variant of GOPO-ROC first appears in [Xie et al., 2021] discounted MDPs.
Algorithm 2 VSC(D, FF, T, Version Space-based Critic
Algorithm 3 ROC(D, F, A): Regularized Optimization-ban bassd Critic
1: F(B:r EJ: (Jn:
C (f) == H (er fn+1)
inf lyy (9h. + B. e [
inf H (gh, fb
2: Q' arg mrg x)
Q' arg fer (Ni((1, (f)
Output: Q'
Output: Q'

---

Posterior sampling-baser critic (PSC) in Algorithm 4. Instead of solving regularized minimax optimization, PSC samples the value function 2 from the data posterior *(f(D, Po(f) p(D),f, m²), where po( is the prior over F and p (D] T²) is the likelihood function of the offline data D. To formulate the likelihood function p p(D x²) ) we make use of the squared TD error (. and normalization method [Dann et al., 2021] to construct an unbiased proxy of the squared Bellman errors. In particular, p(D) π [I E/f,-00,A expl-74,,, (f% where y is learning rate and Po is an (unregularized) prior over FF. A value function sampled from the posterior with this likelihood function is encouraged to have small squared TD errors. The key ingredient in our algorithmic design is the "pessimistic" prior Po( = ( ()po(f) where we add new regularization term (xp(-Afi(s),)) कi ))) with À being a regularization parameter which is inspired by the optimistic prior in the online setting [Zhang, 2022, Dann et al., 2021]. This pessimistic prior encourages the value function sampled from the posterior to have a small value in the initial state, implicitly enforcing pessimism. We remark that PSC requires sampling oracle and expectation oracle (to compute the normalization term in the posterior distribution), which could be amenable to tractable approximations, including replacing expectation oracle with sampling oracle [Agarwal and Zhang, 2022] while the sampling oracle can be implemented via first-order sampling methods [Welling and Teh, 201 I] or ensemble methods [Osband et al., 2016].
expl=2fi,e(fe.ff
Algorithm 4 PSC(D, n², A, yi p.))): Posterior Sampling- based Critic
exp( exp(-xt,,, (fnfnnn))
1: Q' ~ M(I1, x²) x exp (-Af1(81, x)) po()) IInE(M) Big-ro,a exp( --p0-,,,1 1 (11.4441))
Output: Q'
4 Main Results
In this section, we shall present the upper bounds of the sub-optimality of the policies executed by GOPO-VSC, GOPO-ROC, and GOPO-PSC. Our upper bounds are expressed in terms of new notion of data diversity.
4.1 Data diversity
We now introduce the key notion of data diversity for offline RL. Since the offline learner does not have direct access to the trajectory of a comparator policy π E 11alt, they can only observe partial information about the goodness of π channeled through the "transferability" with the behavior policy μ.. The transferability from μ to x depends on how diverse the offline data induced by μt can be in supporting the extrapolation to æ. Many prior works require uniform diversity where μ covers all feasible scenarios of all comparator policies æ. The data diversity can be essentially captured by how well the Bellman error under the state-action distribution induced by f can predict the counterpart quantity under the state-action distribution induced by æ. Our notion of data diversity, which inspired by the notion of task diversity in transfer learning literature (Tripuraneni et al., 2020, Watkins et al., 2023], essentially encodes the ratio of some proxies of expected Bellman errors induced by μa and π, and is defined follows.
Definition 3. For any comparator policy π E IIall, we measure the data diversity of the behavior policy p with respect target policy π by
C(T; c) == max X(F.-F1) di, d.), 20, he
where Fr - Fr, is the Minkowski difference between the function class Fú, and itself, i.e. Fr. Ff := (Jn - Sh Sh. E F}, and xe(E; q,p) is the discrepancy belween distributions q and p under the witness of function class Q defined as
Xe(e: = inf {c 0: (1) C &.. E
with Q being a function class and p and q being distributions over the same domain.
Up to small additive error e, finite C(T; e) ensures that a proxy of the Bellman error under the T innduuced state action distribution is controlled by that under the p-induuedd state-action distribution.
7

---

Despite the abstraction in the definition of this data diversity, it is always upper bounded by the single-policy concentrability coefficient [Liu et al., 2019, Rashidinejad al., 2021] I] and the relative condition number [Agarwal et al., 2021, Uehara et al., 2022b, Uehara and Sun, 2022] that are both commonly used many prior offline RI, works. We further discuss our data diversity measure in more detail in Section 4.2.
4.2 Offline learning guarantees
We now utilize data diversity to give learning guarantees of the considered algorithms for extrapolation to arbitrary comparator policy E I1 To aid the representation, in all of the following theorems
shall set 17 V 4fe 4[e-2]6577 in Algorithm 1, where Vol(A) about to present,
In Vo)(A)
is the volume of the action set A (e.g.. Vol(A) = |A|] for finite A), and define, for simplicity, the misspecification enrors Smap K Σ h= (v) + bvn), Smsp == Smep +bK Σ D Σ vh. the optimization error Sopt == Hb (ol(A), and the complexity measures dope(e, T) = dote) dgle) }.
max max(dy(e)) dn(e, T)}, and (c, = max max (d)((), du(e, T),, 7 7H62..
Theorem (Guarantees for GOPO-VSC). Lel aue be the outpul of Algo- rithm invoked with CripicCompute being VSCID, (Algorithm 2) with 3 = OHHb² max{dopp(c, In.n(((H)))) [6]} + Ke + bK maXne[H] En)- Fix any E (0. 1]. Under Assumption 2-1-2.2, with probability at least 25 (over the randomness of the offline data), for any e, Ec, X O, and any E II""! we have
Hb² maxidopt (c, T), 6 Smop
AH C((T;
E [SubOpt, S
A
2K
He + &1 + Sopt.
Theorem 2 (Guarantees for GOPO-ROC), Let nTD be the output of Algorithm 1 invoked with CriticCompute being ROC(D, F, x², (Algorithm 3). Fix any å E (0,1). Under Assump- tion 2. 1-2.2, with probability least 1 26 (over the randomness of the offline data), for any C, > O, and any x E II we have
Hb max (dops (c. T), In H 3) +DKHH Smop AH C(TT)
E [SubOpt, (F))
2K
He + &1 Copt-
Theorem 3 (Guarantees for GOPO-PSC). Let h be the output of Algorithm 1 invoked with CriticCompute being PSC(D, F, n² X, Po) (Algorithm 4), Under Assumption 2.2, for any and e, E,, > O, and any π E I| we have
E [0, 144(e-2)68 2)6
[SubOpt, SSubOpt,(fP')) Hb max dpe T), In Kb + HHH maxfe, e, 8} 7Smp
X
AH C(T:EC) +
+ HE + e + Copt.
Kr
Our results provide family of upper bounds on the sub-optimality of each of (#*s, # #PS) indexed by our choices of the comparator with the data diversity C(T; additive (extrapolation) error ec, the discretization level e log-covering numbers, the "failure" probability 6, and other algorithm-dependeen parameters (A for n and (A, ?) for $P*). Note that the optimization error Sopt captures the eиror rate of the actor and can be made arbitrarily small with large iteration number T whereas Smaps Smsp- D, and & are simply misspecification errors aggregated over all stages, Also note that our bound does not scale with the complexity of the comparator policy class aall We next highlight the key characteristics of our main results in comparison with existing work.

---

(I) Tight characterization of data diversity. Our bounds in all the above theorems are expressed terms of (e)) Several remarks are in order. First, C(T;; 6c) a non-increasing function of 6c; thus (a);
uniform concentrability
al-
ways smaller or at least equal to C(x:0). In fact, it is possible that C(T;;) = oo yet E() < 00 for some > 0. For instance, if there exists g E Q such that g(x)) = 0, Vr E supp(p) and {ar g(x) + 0} has a positive measure under 9. then Xe(0: q.P) xe g EgggI g. q.p) = O. Second, C(T;0) 0) is always bounded from above by (often substantially smaller than) the single-policy concentrability coefficient between the r-induced and j-indduced state-action distribution [Liu et al., 2019, Rashidinejad et al., 2021], which been used extensively in recent offline RL works [Yin and Wang, 2021, "guyen-Tang et al., 2022a, 2023, Jin et al., 2022, Zhan al., 2022, Nguyen-Tang and Arora, 2023, Zhao et al., 2023]. This is essentially because d" can cover the region that is not covered by d' but still the integration of functions in Fh - Fh over two distributions are close to each other. Third, C(T; 0) is always upper bounded by the relative condition numbers used in [Agarwal et al., 2021,
single-polizy concentrabiliy
relative condition number
squared Bellman residual ratio
oo while
data diversity
The relations of sample- efficient offline RL classes under differ- ent data coverage measures. Given the same MDP and a target policy (e.g., an optimal policy of the MDP), each data coverage measure induces a correspond- ing set of behavior policies (represented by the rectangle labelled by the data cov- erage measure) from which the target policy is offline-learable.
Figure 1:
Uehara et al., 2022b, Uehara and Sun, 2022]. Our data diversity at c = O similar to the notion of distribution mismatch in Duan et al. [2020], Ji et al. [2022], though our notion is motivated by transfer learning and discovered naturally from our decoupling argument. Our data diversity measure at c is smaller than the Bellman residual ratio measure used in Xie et al. [2021] (follows using Jensen's s inequality). Finally, the concurrent work of Di et al. [2023] proposed a notion of D²-divergence to capture the data disparity of a data point to the offline data. Our data diversity is in general less restricted as we only need to ensure the diversity between two data distributions (of the target policy and the behavior policy), not necessarily between each of their individual data points.
In summary, C(T; c2). to the best of our knowledge, provides the tightest characterization of distri- bution mismatch compared to the prior data coverage notions. We sketch the relationships of the discussed notions Figure I, where with our data diversity notion, we show that the scenarios for the offline data in which offline RL is learnable are enlarged compared to the picture depicted by the prior data coverage notions.
MI Competing with all comparator policies simultaneously. Similar to some recent results in offline RL, our offline RL algorithms compete with all comparator policies that are supported by offline data in some sense. In particular, the choice of the comparator provides the flexibility to automatically compete with the best policy within a certain diversity level our choice. For instance, if we want to limit the level C(zzee) S C' for some arbitrary C >> O, our bound automatically competes with π = arg max ( (ViT (s) C(T;; c2) S C). This is immensely meaningful since the offline data might not support extrapolation to an optimal policy in practice.
(III) state-of-the-are bounds for standard assumptions. We compare our bounds with other recent guarantees of similar assumptions." 6 To ease comparison, we assume for simplicity, that there is no misspecification, i.c., 1/2 = &n = 0, Vh e [H], and T' 2 K In Vol(,A), and we minimize the bounds in Theorem and Theorem 3 with respect to X. The three theorems can then be simplified into a unified result presented in Proposition 1.
Proposition 1 (A unified guarantee for VS, RO and PS). Under Assumption 2.1-2.2 with no misspecification, ie., Vh. = En 0, vh E [M], Vi E { T #P*), E[SubbOpi = Ö(Hb T(L/K,T) 1/t:://VK/// + Eopt). where d(1/K, T) dope (I/K E = # and d(1/K,T) (1/K, T) if RPS, In addition,
'Recent primal-dual methods achieve favorable guarantees for offline RL. However, these guarantees are not directly comparable to the guarantees of our value-based methods due to different set of assumptions. Nonetheless, we make detailed discussion in Section A.2.

---

If Fr and (T) have finite elements for all h E [H]. d(1/K,T) O (maxkej)) (n) max(In (Fa,, In _ (T)I)):
Jf = a(),a) + (s,(s, w) : ||ll2 S bj is a linear model, where on : 3 R a known feauufeature map and w.l.o.g. max, ll I L, d(1/K, T) = Ogd (1+ AT.
Proposition 1 essentially asserts that VS-based, RO-based, and PS-based algorithms obtain compara- ble guarantees for offline RI. in the realizable case. We now compare our results to related work in various instantiation of function classes.
Compared with Xie et al. [2021] when the function class is finite. In this case, the analysis of the VS-based algorithms and RO-based algorithms of Xie et al. [2021] give the bounds that in our setting can be translated' into: Hbymmax In([Fh [n([F) C2(TT/K
and Hb C2(T) V maxA ( + Hb/VT, respectively, where C2(Z)) ==
I1. I1 Sa-111. [aX sgmell SEF 1fx 15x-T5566118..
Instead, our bounds for both the VS-based and RO-
based algorithms are Hby max, |1 (T))) C(T;; 1/VKKK + Hb/vT. We improve upon the results of Xie et al. [2021] on several fronts. First, our diversity measures C(T;; 1/K) is always smaller than their measure (T)),, since C(T; L/vK) S C(;;0) I (2(T). Second, for the VS-based algorithm, II (T) C II VT, our bound is always tighter. In fact, |II is arbitrarily large that bounds depending on this quantity is vacuous. Third, for the RO-based algorithm, the rates in terms of K in the bound of Xie al. [2021] are slower than that in our bound. Specifically, if 1175((()) (1), then these rates are K-1/3 1/3 K- (with an optimal choice of T K for both bounds). If we consider the worst case that TTx (T) = ( log (Frl), then these rates are K-1/5 vs K-1/4 (with optimal choice of T K22/ and T = vK in the respective bounds). Finally, our results hold under the general adaptively collected data rather than their independent episode setting. We summarize the bounds in the finite function class cases in Table 1, and give comparisons for the linear model cases in Table 2.
Compared with LCB-based algorithms. When Fn is a d-dimensional linear model with
feature maps for (on)ne(M)) our bounds reduce into Hby d K-1 C(T:1/V// (Proposition 1), which matches the order of (and potentially tighter than) the bound in Zanette et al. [2021], since C(T; L/vK) is always smaller (or at least equal to) than the relative condition num- Compared with the bound of LCB-based algo- rithms in Jin et al. [2021b]. we improve a factor vd and holds under the more general Assumption 2.2 which includes low-rank MDPs. In more refined analysis [Xiong et al., 2023], the LCB-based algorithm obtains the same dependence on d for low-rank MDPs as our guarantees. However, this improvement relies
ber max, sup 2,
uniform coverage assumption, i.e., on (1) an) O, which we do not require. Di et al. min Aminn (B(e)..))) [on (0n()),)))))) [2023] generalize the results of Xiong et al. [2023] from linear MDPs to MDPs with general function approximation. However, they still rely on uniform coverage assumption. Finally note that, for VS-based and RO-based algorithms, we provide f over the randomization of the algorithms, not for स itself.
bounds for a smoothing version of
Compared with model-based PS. Uchara and Sun [2022] consider model-based PS for offline RL, where they obtain the Bayesian sub-optimality bound of H /C In [MI/K where Bayes is the Bayesian version
relative condition number and M is a finite model class. Two key distinctions are that our method in Algorithm 4 is model-free and our achieved bound is in the frequentiit (i.e., worst-case) nature, which is a stronger result than the Bayesian bound of the same order.
5 Conclusion
We contributed to the understanding of sample-efficient offline RL in the context of (value) function approximation. We proposed a notion of data diversity that generalizes the previous data coverage measures and importantly expands the class of sample-efficient offline RL. We studied three different algorithms: VS. RO, and PS, where the PS- based algorithm is our novel proposal. We showed that VS, RO, and PS all have same-order guarantees under standard assumptions.
"ie al. [2021] consider discounted MDP and restricted policy class for the comparator class.
10

---

Acknowledgements
This research was supported, in part, by DARPA GARD award HRO01 12020004, NSF CAREER award IIS-1943251 funding from the Institute for Assured Autonomy (IAA) at JHU, and the Spring 22 workshop on "Learning and Games" at the Simons Institute for the Theory Computing.
References
Alekh Agarwal and Tong Zhang. Non-linesd lineai reinforcement learning in large action spaces: Structural conditions and sample-effeiency of posterior sampling. In Conference on Learning Theory, pages 2776-2814. PMLR, 2022. 2, 3,
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22(98): 1-76, 2021. 2, 8,9
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and a single sample path. In Gábor Lugosi and Hans UIrich Simon, editors, Learning Theory, 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006, Proceedings, volume 4005 Lecture Notes in Computer Science, pages 574-588. Springer, 2006.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of Computing, 8(6):111-164, 2012. doi: 10.4086/tcc.202.. v008a006. 6
Peter L Bartlett Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics, 33(4): 1497-157,7 2005. 35
Jinglin Chen and Nan Jiang. Information-theorrticc considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR, 2019. 2
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density- -ratio realizability: the power of gaps. In Uncertainty in Artificial Intelligence, pages 378-388. PMLR, 2022. 2, 5, 18
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In International Conference Machine Learning, pages 3852-3878. PMLR, 2022. 6,
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. In Advances in Neural Information Processing Systems, 2021. 2, 5, 6, 7, 21, 29, 30, 31, 34, 37
Qiwei Di, Heyang Zhao, Jiafan He, and Quanquan Gu. Pessimistic nonlinear squares value iteration for offline reinforcement learning. arXiv preprint arXfv:2310.01330, 2023. 9, 10
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709. PMLR, 2020. 4, 9, 17
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005. 1
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487. 2021. 3
David Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100-118; 1975. ISSN 0091 1798. 19
Germano Gabbianelli, Gergely Neu, Nneka Okolo, and Matteo Papini. Offline primal-dual reinforce- ment learning for linear mdps. arXiv preprint 2rX1v22305.12944, 2023. 18

---

Xiang Ji. Minshuo Chen, Mengdi Wang, and Tuo Zhao. Sample complexity of nonparamet- ric off-policy evaluation on -innnimesionnal manifolds using deep networks. arXiv preprint 00X2022206.02887, 2022. 9
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. 5, 21
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.
PMLR, 2020. 5
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. In A. Beygelzimer, Y. Dauphin, P. Liang. and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021b. 2, 4, 10, 18
Ying Jin, Zhimei Ren, Zhuoran Yang, and Zhaoran Wang. Policy learning" without overlap: Pes- simism and generalized empirical bernstein's 's inequality. arXiv preprint arXiv:2212.09900, 2022.
Sascha Lange. Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv preprint arXiv:2005.0/644 0/0000000000003... 2020.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with stationary distribution correction. Amir Globerson and Ricardo Silva, editors, Proceedings of the Thirty-Fifth Conference Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine Learning Research, pages 1180-1190. AUAI Press, 2019. 2, 8,
Pascal Massart. Some applications of concentration inequalities to statistics. Annales de la Faculté des Sciences de Toulouse, 9:245-303, 2000. 19
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. J. Mach. Learn. Res., 9:815-857, 2008. 2
Thanh Nguyen- Souuyen-Tangaan and Raman Arora. VIPer: Provably efficient algorithm for offline RL with neural function approximation. In The Eleventh International Conference on Learning Representations, 2023. 9
Thanh Tguyen-Tang. Sunil Gupta, A. Tuan Nguyen, and Svetha Venkatesh. Offline neural contextual bandits: Pessimism, optimization and generalization. In International Conference on Learning Representationss 2022a.
Thanh Nguyen-Tanne Sunil Gupta, Hung Tran-The. and Svetha Venkatesh. On sample complexity of offline reinforcement learning with deep reLU networks in besov spaces. Transactions of Machine Learning Research, 2022b.
Thanh Nguyen- Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforcement learning with linear function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9310-9318, 2023. 3,
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016.7 7
Asuman E Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. Revisiting the linear- programming framework for offline with general function approximation. International Conference Machine Learning, pages 26769-2679) PMLR, 2023. 18
12

---

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, 2021. 2, 8,
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao. Optimal conservative offline RL with general function approximation via augmented lagrangian. In The Eleventh International Conference on Learning Representations. 2023. 2, 5, 18
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 12241:12211 2014. 2
William R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25:285-294, 1933. 2
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in neural information processing systems, 33:7852-7862, 2020. 7
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference on Learning Representations, 2022. 2, 3, 8, 9, 10
Masatoshi Uchara, Chengchun Shi, and Nathan Kallus. A review of off-policy evaluation in rein- forcement learning. arXiv preprint arXiv:221..6635, 2022a. 1
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. In International Conference on Learning Representations, 2022b. 8, 9
Ruosong Wang, Dean Foster, and Sham M. Kakade. What are the statistical limits of offline RI. with linear function approximation? In International Conference on Learning Representations, 2021.
Austin Watkins, Enayat Ullah, Thanh Nguyen- Tang, and Raman Arora. Optimistic rates for multi-task representation learning. In seirth- Conference on Neural Information Processing Systems, 2023.7 7
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICMI.-II), pages 681-688, 2011. 7
Tengyang Xie. Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consister pessimism for offline reinforcement learning. Advances in neural information processing systems, 34, 2021. 2. 3, 6, 9, 10, 18
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, and Tong Zhang. A self-play posterior sampling algorithm for zero-sum markov games. In International Conference Machine Learning, pages 11496-24523 PMLR, 2022.
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline reinforcement Icarning with linear function approximation: Single-agent MDP and markov game. In The Eleventh International Conference on Learning Representations, 2023. 10, 18
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances neural information processing systems, 34, 2021. 2,
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems, 34:13624 13640, 2021. 2, 4, 5, 6, 10, 17, 18, 21, 22, 23, 42
13

---

Ruohan Zhan, Zhimei Ren, Susan Athey, and Zhengyuan Zhou. Policy learning with adaptively collected data. Management Science, 2023.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizabilitty and single-policy concentrability. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2730-2775. PMLR, 02-05 Jul 2022. 5, 9, 18
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM
Journal on Mathematics of Data Science, 4(2):834-857, 2022. 2, 7
Tong Zhang. Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023. 5
Yulai Zhao, Zhuoran Yang, Zhaoran Wang, and Jason Lee. Local optimization achieves global optimality in multi-agent reinforcement learning. arXiv preprint arXiv:2305.048/ 048/9, 2023.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang. Zhuoran Yang. and Tong Zhang.
A posterior sampling framework for interactive decision making. arXiv preprint arX1v:2211.01962, 2022. 2, 3
Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement learning. arXiv preprint arXiv:2301. 2023. 18
14

---

Contents
Introduction
2
Background and Problem Formulation
2.1
Episodic Time-inhomogenous Markov Decision Process
2.2 Offline Data Generation...
2.3 Policy and function classes
2.4
Effective sizes of policy and function classes
3
Algorithms
Main Results
4.1
Data diversity
4.2
Offline learning guarantees
5
Conclusion
10
Appendices
17
Appendix A
Extended Discussion
17
A.1 Linear function classes
17
A.2
Comparison with primal-dual methods for offline RL
18
Appendix B
Preparation
19
B.1
Variance condition and Bernstein's inequality
19
B.2
Functional projections for misspecification
20
B.3
Induced MDPs
21
B.4
Error decomposition
B.5 Decoupling lemma
22
B.6 Regret of the multiplicative weights algorithm for the actors
22
Appendix C Proof of Theorem
24
C.I Proof of Theorem
25
................................
C.2 Proof of Lemma C.1
................................
25
C,3 Proof of Lemma C.2
26
Appendix D Proof of Theorem 2
28
Appendix E Proof of Theorem 3
28
E. Generalized form of posterior and Proposition 2
29
E.2 Proof of Theorem
30
E,3 Proof of Proposition 2
30
E.3.1
Lower-bounding eer-ptttiionn function.
31
15

---

E.3.2
Upper-bounding log-partttinnn partition function
37
E.3.3
Proof of Proposition 2
40
Appendix
Proof of Proposition
40
Appendix G Support Lemmas
42
16

---

Appendices
Appendix A
Extended Discussion
We also extend the discussion of our data diversity in comparison to the existing distribution mismatch measures in the special case where each Fn is a linear function in known feature map.
A.1 Linear function classes
In this section, consider the linear model cases, where there known feature maps du. A A Rd and w.l.o.g. [аX)e[н] ())(;,)) & 1, such that Fn {Ør (:s)) )FT w E IRd, || S b). Recall that, in this case, e.g., it follows from [Zanette et al., 2021, Lemma 6], that we have
log Ne; || I1 S dlog(1 + ?)
log (c; M (T), II ll S dlog(1 + 166T Thus, bounds from Proposition 1 can simplified as
)
Ö O(Hby dloo(1 + 16bKT) 1/;11/KK)KK HbyT-1In Vol(A))
max 1/V In Vol(A))
= Hby
K
where we choose K. simplify the comparison, we assume that dC((T; 1/vK)//K//// In Vol(A).
Let us now compute various notions of data coverage in this linear model case. $ We first need to define the following quantities (various forms of covariance matrices).
Σn X +
on (sh at (s att""
K
AG = XI + Σ Φn (5 a on /L2
07 = Ey (0n an)l.
Σ, = E [d(sn, (s) ax) )
We define the following distribution mismatch quantities, which were used the literature.
Cpeni( = max kE
F
[[on(<n an)l=,
FEz [Ion(su, an)lax 1)
Cpeni-ade ado (Tt) = max
hE H
Cpacte (T) : max
[H]
Chep(T)) = max H
(E (sn an an))l
The sub-outine oobbbatttllityy bounds of various methods are summarized in Table For comparing our data diversity measure with different notions of distribution mismatch, we have
Opené ( 2 (T)) x C(T; 0)/ < Cbep(x)/K.
where the ">=" denotes that the involved terms scale in the same order and can be implied by Fredman's matrix inequality (see [Duan et al., 2020, Lemma B.5)) (under additional conditions). Note that C(T; 1/VK) S C(T;; 0), thus our data diversity is the tightest quantity among all that are considered.
17

---

Algorithm
Sub-optimality bound
PEVI [Jin et al., 2021b]
Hby TNve/puess) (T)
PEVI-ADV+ [Xiong et al., 2023]
H Cpeepei-aaa avi (T) d
PACLE [Zanette al., 2021]
Hby/Cpacle Cpacle (T)
VC [Xic et al., 2021, Scction 3]
Hby Cbep (T) d/K
RO [Xic et al., 2021, Scction 4]
Hby /Copp ( d/dKK
Ours (VS, RO, PS)
HbyC(T: d/K
Table 2: Sub-optimality bounds when the function class Fr is linear in Φn : S x A - Rd
Note that the data coverage measure in Xiong et al. [2023], roughly speaking, can be bounded as follows:
Cpevi-ado (T) < b²C (pevi(T).
where we use the inequality (V, V ( of) S 12. Thus the bound Xiong et al. [2023] in general has a tighter dependence on b (which implicitly depends on H) than all the bounds of all other works considered in Table 2, due to that Xiong et al. [2023] incorporated the variance information into the estimation via the variance- wariance-weighted value iteration algorithm. However, obtaining this improved bound in Xiong et al. [2023] relies on a uniform coverage assumption which we do not require.
A.2 Comparison with primal-dual methods for offline RL
As opposed to the value-based methods we considered in our paper, an important alternative approach to offline RL is the primal-dual methods [Zhan et al., 2022, Chen and Jiang, 2022, Rashidinejad et al., 2023, Gabbianelli et al., 2023, Ozdaglar et al., 2023]. However, the guarantees of primal-dual methods use different set of assumptions than the value-based methods we consider (the former assumes realizability for the ratio between the state-action occupancy density of the target policy and the state-action occupancy density the behavior policy, except for Gabbianelli et al. [2023] where this realizability assumption is implicitly encoded under a stronger assumption of linear MDP). This makes the results presented in our paper and the results in the primal-dual methods not directly comparable.
Since the work of Gabbianelli al. [2023] considers linear MDPs, it more comparable (than the other primal-dual methods we mentioned) to the instantiating of our results to the linear function class. Gabbianelli al. [2023] consider primal-dual methods for offline RL in both infinite-horizon discounted MDP and average-reward MDP. Our analysis framework for the regularized optimization method in the episodic MDP should work for the feinite-horizon discounted MDP as well, where the regularized optimization achieves the optimal sample complexity of (c-2)) while the sample complexity in Gabbianelli et al. [2023] this setting Ole-)). However, Gabbianelli et al. [2023] offers better computational complexity (O(K) vs (K7/5)) and also works in the average-reward MDP setting which is beyond the episodic MDP setting considered in our work; though our bounds hold for general function approximation that is beyond the strong assumption of linear MDPs.
The concurrent work of Zhu et al. [2023] combined the actor-critic framework with marginalized importance sampling (MIS) for an RO-based algorithm, which also improves the sub-optimal rate of order 1/K1/3 by Xie et al. [2021], Cheng et al. [2022] the optimal rate of order 1/ I/VK, Instead, we obtain the optimal rate of order 1/VK with a refined analysis for standard RO-based algorithm. That is, unlike Zhu et al. [2023], we do not use MIS; consequently, we do not require the realizability assumption for the ratio between the state-action occupancy density of the target policy and that of the behavior policy.
18

---

Appendix B Preparation
We now get into more involved parts where we present the proof process and the technical results for obtaining Theorem Theorem 2, and Theorem 3. In order to prove our main results in Section shall need some old tools and develop some new useful tools. For convenience, we start out with both old and new notations of quantities summarized in Table 3 that going to use frequently in our proofs.
Name
Notation
Expression
transition sample
=
(sh oh th gh44))
transition sample
Fu
(#u. One S141)
Bellman
E, (nr (s,1)(sh,
(T fa)( on)
TD loss function
La fu41t
(fr(en) rn fnez(8n41; La- (n+1i
empirical squared Bellman ervor (SBE)
L Uni Jn+1)
empirical bijs-adjustod SBE
Ca(f)
E# Lalfn fa+1) inf Σnn Lalen fues)
excess TD loss
A AL Ja+1i mm)
le (e JNH1s an) 1a (TT Saesiia)
Bp[]
* Σ E
B+l-((== F2)+(D
(+t sc]=1]
Table A summary of notations and quantities of interest.
The quantity 4(fn, f can be viewed as a temporal difference (TD) loss function defined on data point žn conditioned on each fn+1 and æ. The quantity T f.+4 can be viewed as the Bellman regression function, where, conditioned on each fr+1 and ft, for any (sh, ax), we have
Thfn+1 an) = EE [Th +
#)] = arg inf Er ls, la (g, fn+1;
Thus, the quantity AL (.h, fh41122) can be referred the excess TD loss, incurred by the predictor fr. relative to the TD regression function fh+ on data 2n and conditioned on fi+1 and π.
B.1 Variance condition and Bernstein's 's inequality
We also define the o-algebra A (DDx11 {($) ai r [eeep-i U (s a and denote E == [E[]) The following lemma establishes the variance condition on the excess TD loss, TD analogous to the variance condition that is widely used in the empirical process theory [Massart, 2000].
Lemma B.1. For any At ----maauurblle policy n, we have
EL, fn+ 21) (f fo- ( ah) Ex (L fh+1 21 36b2 (f fh+1) x
Proof of Lemma B.I. The result directly exploits the boundedness of the TD loss function and the squared loss is Lipschitz. In concrete, it is a direct application of Lemma G.I.
The following lemma establishes the martingale extension of Bernstein's s inequality, typically called Freedman's 's inequality [Freedman, 1975]. In this lemma, prove slightly modified version of the original Freedman's 's inequality for our own convenience. The proof for this lemma is elementary which we also show here.
19

---

Lemma B.2 (Freedman's 's inequality). Let X1....,Xy XT be any sequence of real-valued random
variables. Denote =-I-I=BB for all I. Define the random variables
= E[||X,,.. .........,,,,, X,-1]. Assume that X, S for some and [,[X,]
Σ
X
Ex
i=1
Then for any > with probability at least 1 8. for any X [0,1/R)
In(1/6)
$ (e ( + A
Proof of Lemma B.2. Let us define the following sequence of random variables: Zo = 1, =
Z [.
AN
We have
exx,
Zz-1 Belexxij = Zc-1-
B.[Zo] Et
Zo-1
Ee
Eeledx.
Thus, have
E E[ZT]
EEt
[TT]
E[Zr-1]
EiZo] =
Note that
AS
eA8
T
ZT
exp XS
Σ
In Is (eNee)
(3)
I [exx]
Et=1 [exx,
T
Since ZT 2 0, it follows from Markov's inequality that, for any 5 > 0, we have
Pr(Zr 1/8) S 6E[Zr] = 6.
We now bound the logarithmic moment generating function In IE, AXx using elementary inequalities: For any X E [0, 1/R,, we have
In Ee S E, [e - S XE + (e - 2x)",
(5)
where the first inequality uses In = < z - 1, Vz 2 0 and the second inequality uses that ea 1 + (e 2)²², Vz < 1 and that XX, <
S
Plugging Equation (5) into Equation (3), then all together into Equation (4) complete the proof.
B.2 Functional projections for misspecification
Since Assumption 2.1 and Assumption 2.2 allow misspecification up to some errors & and u, while we are working on the function class F, we rely on the following projection operators, Definition and Definition 5, to handle misspecification.
Definition 4 (Projection of action-value functions). For any -I=oft(T) for some T N, we define the projection of the state-action value function स onto F as
Proj=(Q") = arg min (1,n an) - QT, an)), vh E [H], (sh, an) E supp(d))) JEF
By Assumption 2.1, we have
( (sh, an) - o (sh, an) En. vh E [H), (sh, an) E supp(d)))
Definition (Projection of Bellman operations). For any f E F and f e II (T) for some T, we define the projection of the Bellman operation T onto F as
Proi>(1 f) = arg min {1lf% failloo vh e [W]]
feFF
By Assumption 2.2, we have
Projj (T= f) T fr.fnilloo Sh. Vh [H].
20

---

B.3 Induced MDPs
We now introduce the notion of induced MDPs which originally used in [Zanette al., 2021]. Definition (Induced MDPs), For any policy II and any sequence of functions Q Jeem E {S x A + R] the (Q, T) --i-nduce MDPs, denoted by M(Q. T) is the MDP that is identical to the original MDP M except only that the expected reward of MQ2 π) is given by f%% [he(m), where
T.Q. (s,a) = -ra(8,0) - 8% Jh "h"
By definition (TT, Q). Q the fixed point of the Bellman equation Q₁ = -T,, Qh+1
Lemma B.3. For any π E I! and any sequence of functions Q = {Quhemm (S x + +R", have
(M( =Q,
where M (TT, Q) is the induced MDP given in Definition 6.
B.4 Error decomposition
The key starting point for the proofs all of the three main theorems is the following error decom- position that decomposes the sub-optimality into three sources of errors: the Bellman error under the comparator policy и, the gap values in the initial states, and the online-regret term due to the induced MDPs. In online RL, the sub-optimality of greedy policy against optimal policy can be decomposed into the sub-optimality in the Bellman errors and the error the initial states [Dann et al., 2021], using the standard value-function error decomposition in [Jiang et al., 2017, Lemma 1J. However, our setting, we compete against an arbitrary policy æ (not necessarily an optimal policy) and the learned policy x' is not greedy with respect to the current action-value function Q' thus [Jiang et al., 2017, Lemma 1] cannot apply here. Instead, we develop an error decomposition Lemma B.4 which generalizes what was implicit in Zanette et al. [2021].
Lemma B.4 (Error decomposition). For any action-value functions Q (8 A- R}" and any policies f E Ialll
we have
H1
SubOpt M (+)
Σ
E. 1 (Qn, Qut))s an)] V/ + (ub
Proof of Lemma B.4. We have
SubOpt (#) = (iT - (11(
(V ((..(e))((1)) + v (Vi - vff(s))) + (VTTM)(es)((1)) (a
Σ (ET Qh+1) an) Q1(, #1) (s + Sub M(Q.*)
A=1
where in the last equality, for the first term, use, by Definition 6, that
(i((s) (o6s)>-VV,,mme VT =
Σ Eg an) - 5..0 an) = Σ Ex (Qn, Qn+1) ax)],
A=1
for the second term, we use, by Lemma B.3, that
(x = ($, #1) = (1,,
and for the last term, the definition of value sub-optimality in Equation (1).
21

---

B.5
Decoupling lemma
One of the central tools for our proofs is the following decoupling lemma. The decoupling lemma essentially decouples the Bellman residuals under the x x-induced state-action distribution into the squared Bellman residuals under the p-induced state-action distribution and the new data diversity measure in Definition 3 and additive terms of low order.
Lemma B.5 (Decoupling argument). Under Assumption for any f E F, any (T)
some T, any E IT any À > O, and any 2 O, we huve
R Ex (Jh. (5h, an) -
B [ (s+1) ah) + KVz + 4bKun
2
AH -((Te))
H
+
+ HE +
Σ
P/s
2K
h=1
where CIT; c) is defined in Definition 3.
Proof of Lemma B.5. We have
"
Ba 18 fh+
ΣE
Ex -
En (PProjs,TThAa - fs) an) +
V CC( ()p [Proos, (erroi,,(ii.++ (Ti()+1) mn) + He +
V (C(,,) (in ax)) +1 4bv)) HE
HC(T, c)
1n fntz) 11 4bbr)) + Hc+ D
h=1
K
EE (Sh, fs) az) 4bvr) + AHC(T,E))
+ HE D,
2A
2K
where the first incquality uses Assumption 2.2, the second inequality uses the definition of C2 (e). the third inequality uses Assumption 2.2 (again), the fourth inequality uses Cauchy-Schwarr Schwartz incquality. and the last inequality uses the AM-GM inequality yTy S 2A 2K y-
B.6 Regret of the multiplicative weights algorithm for the actors
Now we establish the regret bound for the online-regret term due to the induced MDPs. The result in the following lemma is quite standard and can be readily generalized from similar result in Zanette et al. [2021]. We present the proof here for completeness. Lemma B.6. Consider
arbitrary sequence of value functions (Quhe such that maxs, || S b and define the following sequence of policies (T(TTT(4)))) where
(-|s)) = Uniform(AA (A), Vs.
++1 (als) x (als) exp (s, V(s,a,h,t).
Th
Suppose 1
4(c- 2 and T 2 In VollA) where Vol(A) denotes the volume of the action set A. (e-2)
In A)
8 For arbitrary policy e we have
Σ
Vi ((TM((119999111 -
& 44b4ThT Vol(A).
When LA| < 0o, Vol(A)) -|A].
22

---

Proof of Lemma B.6. The proof for this lemma is quite standard as shown in Zanette et al. [2021]] We rewrote the proof with slight modification for completeness. For simplicity,
write M, := ( Q*). We will see that the key property that enables this lemma that 0 = fh.M (Lemma B.3), which allows relate the value difference lemma to the log policy ratio. Using the value difference lemma (Lemma G.2), we have
VT,M, ($1) - VT, (51) = Σ h=1
B A as): an);
where E, is the expectation the random trajectory (s1, di...... 8H 0. generated by (and the underlying MDP M2)). For any : + R, follows from the definition of {x") update that we have
"h (a|s) = (s, a) - log (Eaw [oxp (71% (s, a))1)
log
Ta((sss)
=n( VVss) log (Eanatt a) (exp -V())))
In the equation above, noting that Qi = Qhim. (Lemma B.3) and replacing V(s) by V we have
++1 (als) nA (s, log (Eawt)(()) eep (14
log A
(6)
7 (als)
where we define the advantage function AJr [A,,MbheT as
( = QT, a) - (s), ((s,,,)))
Note that |AT, , (s, a)l s 26. By choosing E (/bb), we have
log (Bana)((1))) exp (1 (8.
$ log (BowR((1s)
+ M.A.iM (s, a) + (e Ah
-log
1 (e A ATMM (s.
< log(1 1 + (e 24b)
4(e - 2)b
where the first inequality uses that ex < <e+x+(e-2)r" Vr < 1 and |nA (s, a)l S 1, V(s, a). the first equality that Eg (-1+) AA (s, 0, the second inequality uses that | (s, - 26, and the last inequality uses that log(1+r) < Vz 0. Combining Equation (7) and Equation (6), we have
A M. (s, < log T (a|s) (als) + 4(e 2)622n.
Thus, for any E [A], we have
E, Apt M, an) an)
1=1
(-Iss)]]) + 4(e 2yTb²n E (KImm(((sss)]](( E, (KL[((((1sss))ll (1
1
NNte that Pr((s1, ......, SH, aT) MM= = Pr((s1, o....., sH. an Ho,, Mc) since M, and M have iden- tical transition kernels.
23

---

1
[ (+1s)]]] - Ex, (((ss)) + 4(e - -2ybb'n
(-1s))]]
17
En (1L] + 4(e 2)T6211
1)
log (o)( + 4(e 2
where the second inequality uses the negaaiiivvtty of KL divergence, and the last inequality uses that K L ( = T (-Is)] + log( (V)() I log(Vol( where x is uniform over A and (A)( denotes the volume over the compact set A. Combining all pieces together, have
Σ Bn AT (sh, an) as)
- - 11 log( Vol(A)) 4(e 2)TH1."n
")
Minimizing the RHS of the above equation with respect 1 yields 1)
((e-2)b2T and
log Vol( (A)
T
Σ E Ah, (Sh, an) S 2H /4(e 2)12Tlog Vol(A) < 4Hby Plog Vol(A).
Finally, we need that
log Vol(AA
= V
4(e 2)02T S
2h'
which implies T 2
Vol(A) (e-2)
We are now ready to establish the proofs of our three main theorems.
Appendix C Proof of Theorem 1
To construct our proof for Theorem 1, we first establish two following lemmas. The first lemma, Lemma C. establishes that the in-distribution squared Bellman residuals are bounded by the unbiased proxy of the squared Bellman error L f) up some estimation and approximation errors. The second lemma, Lemma C.2, asserts that the unbiased proxy of the squared Bellman error at the projection of Q² is close zero, up to some estimation and approximation errors.
(f),
Lemma C.1. For any 0, >> O and any T E N, under Assumption 2.2, with probability at least 1 1- 8, it holds uniformly over all f E F and ã E [I= that
Es (f,, (fh, (8h,, an) < 2f= + 406(4 + 2)K 12bK
1=1
144(e 2)6² [d((c) dn(e, T) + In (1))),
where C+(f) = = La (fr, fa+1) - inf Σ L (gn. fb+1).
Lemma C.2. Under Assumption f.rr any T E N. with probability at least 1 1-8, 8, it holds uniformly for any E 10t (T) that
H
La (Proi=((()) & 36(e 2)02 H (2d(() + dnle, T) + In ) + 6b(3b + 4)cKH + 15bK
Σ
En
h=1
where Pr))x(Q**) is the projection of Q* onto F. formally defined in Definition 4.
24

---

C.1 Proof of Theorem
With the two lemmas above, we are ready to prove Theorem This proof is also laying a foundational step for our proofs of Theorem 2 and Theorem 3 that we shall present shortly. The proofs for the two lemmas above are presented immediately after the proof of Theorem 1.
Proof of Theorem 1. Using Lemma B.4, we have
SubOpt M (x')
Σ
E Leg aa) mf) SubOpt M. (x* ax))
A=1
where we denote
Mi M(Q', (M(Q',xx') x²);
A (81, 2, (T), VT (81).
Bounding Σe -t=l SubOpt Me (xt). Note that E SubOpt Me (m²²) can be controlled by standard
tools from online learning (Lemma B.6); thus it remains to control the first H + terms.
Bounding ,1Q, 7f). Due to Lemma C.2, the event that Projz E F(B; holds occur at probability at least 8. Furthermore, under this event, we have
410, (s1, m1) Q, VIT (s1)
< Proja (QT)) - VT (81)
S1
where the first inequality exploits Line 2 of Algorithm 2, and the last inequality uses Assumption 2.1.
Bounding Σm E2 (O,, 2 (sp. on)). It follows from Lemma B.5 that
H
H
B E ( 2 an))
HC(T;e)
E 1 an) 4bwn)
1m1
Amm
He D.
The term EiLE, E, @4 1 (sk, ) is bounded by Lemma C.1, with notice that Cx (Q") S (due to the definition F(3;=') x²) in Algorithm 2).
Combining the three steps above via the union bound completes our proof.
We now prove the two support lemmas.
C.2 Proof of Lemma C.1
Proof of Lemma C.I. Let us consider any fixed f E F and any π E I!a!! By Lemma B.1, we have
E (LL fn+li *{]] E (fh, ( a
Ex a (fh, fh+15 #b) < 3662 (fh, fa+ (s at
Combining with Lemma B.2, we have that with probability at least 1 8. for any E [0, 136
Σ Ex(ET (Jr. (141) an)
Σ ALa
K
< 36(e - 2)62,
Σ
Ex (Sr, Shoz) an (1/1) log(1/8).
25

---

By setting 1 72(e-2)62 the above inequality becomes
K
K
ExlER (fu. fh+1) an) 2
(fn $2 144(c - 2)6² Im(1/))
Σ
k
For any >> O, and for any f E F.F (T)) by definition of e-covering, there exist f' and x/ in the e-cover of F and II (T),
115 lo S <, T/ll1.00 Sc.
By simple calculations, have
18% (Jh, (nh, an) T (Fh an) 4b(b 2)c, A (J Sh+1; A (Sho fh = < 18b(b + 2)c.
Thus, by the union bound, have with probability least 1 6, it holds uniformly over all f F, E (T) that
"
K
1 k 52
Σ
Ex (fh, (f,,
fa+1) an 5
La (fr. fn+15 + 406(b 2) He
k=1k=
4=1
k=1
144(c 2)b²
ll. (T), 11,,))/0).
Finally, notice that
(TT fa+11 1x (Projr, (h S 6bvn
f(411
Thus, we have
"
K
ΣΣ (hh (c(s + 6bk
Σ
Vh-
h=1
We can then conclude our proof.
C.3 Proof of Lemma C.2
In order to prove Lemma C.2, we shall first prove the following lemma, which establishes the confidence radius of the empirical squared Bellman errors that we used establish the version space in Algorithm 2.
Lemma C.3. Consider any ā > 0,e E, let
B. 36(e - 2)b² (2dz(c) dn(c,T) + In(H/8)) + 6b(bb 4)cK.
With probability at least holds uniformly over any π E [T= f F, and h E [H] that
K
K
(TT/h+1(1))) r - -n 1)) S inf
Σ
(gn(2)) - 1 - Shtr m)+1))² + Be-
E.F
R=1
Proof of Lemma C.3. Let us fix any h E [H). For any (f.g.T) E FxFXx (T) and any k E [K] define the following random variable
(f.g.t) = (x)) r -
T 1))
- fn- i - 1))
Denote
[ EE(k-1] (E
B = E
bElH , (=hlhe
at rk,
& r..... Sh-1 at
&
26

---

By Lemma B.I, we have
ER [Z,, m)]
(gh, fn+ (5hs ah) 3662 8% (gh. Jh+ 1) ah)²
BR,b (f,,,
Thus, combing with Lemma B.2, for any (f,9,z) E F F II with probability at least 1 - 6, for any E [0, 1362
K
K
Zen((,g,T) 36(e - 2)b², (o,, (n+1) a/2 + In(1/5)
K
A ( (gg,T)]
Σ
Σ
1=1
k=1
By setting 1/(36(e- 2) the above inequality becomes
(R., 36(e 2)6² In(1/))
(8)
For any E > let F and II be e-covers of and (T)) respectively, with respect to || llx and || 1 respectively, where l v|ls == suP(s.a) (u(s,a) - v(s,a)l and || n ||,c,1 sup, EneA [m(a)) n' (als)]. Using the union bound, it follows from Equation (8) that with probability at least - 6, it holds uniformly over any h E [H] and any (f.g. T) F x F II that
Ze (f...T) 18(6 2)6² [ln(H/8) + 2dz(() dn(,,
For any (J,9,²) Fx (T)) there exist (e Te) E Ft F II such that Il - (f c, 119n - (o.) S. - (Te)llloo, S v [H] is easy to compute the discretization error that
(f. x) (f, 9c, me) S 18b(b + 1)c.
Using the discretization argument and the union bound complete our proof.
We are now ready prove Lemma C.2.
Proof of Lemma C.2. Consider the event that the inequality in Lemma C.3 holds. Under this event, for any E [T (T), we have
K
K
La (Proje,
Σ La (Q 2 + 6bK
La
6bKEn
Projs (Qh+1): )
4 Projroj
12bKEn
K
(gn, ProjFr., (:++1); + 3, + 12bKE, (for any gn E Fi)
L (gn, Q +)) 3. 15bK
km/
where we use Assumption 2.1 for the first, second, and last inequalities, the third inequality uses Lemma C.3, and the equality uses Q =T T Rearranging the last inequality completes our proof.
27

---

Appendix D Proof of Theorem 2
In this appendix, we present our complete argument to establish Theorem 2. In order prove Theorem 2, the key is to establish a connection from the squared Bellman error under the data distribution μ to the regularized objective in Algorithm This key idea should become clear in the following proof.
Proof of Theorem 2. Similar to the proof Theorem 1, our starting point is using Lemma B.4:
SubOpt M (x') = Σ En Le (Q) ( AiQ SubOpt A (**)
and we bound E SubOpt M (Λ*) using Lemma B.6. We now bound the remaining terms.
For any 7 > 0, we have
H
E
E h (2,, (sh
1=1
K
AHC(T,C)
Euleg (2
an) (6 + 4bbn) +
He +
2X
2K
C. (Q) + 0.5t, 0.5K22 + 2bKo
XHC(T,E)
+ He + V
A
2K
where the first inequality uses Lemma B.5 and the second inequality uses Lemma C.I, and here : 40-(000b+ 2)K He 126K Σ in + 144(e- 2002 [d>(e) + dn(e, T) + In(188). Thus, we
:=
have
H
Em 1 (O, 2 (sh. an)] - 41Q, (i1,
1=1
(2) AA Q, (51, mH) 0.5c + 0.5K Σ 1 + + Σ V/ AHC( c)
2K
He Σ
Vh
h=1
C. (Proix((Q*))) + AA, (QT (s1,xT) 0.5g + Σ 17 1 2bK Σ Kh
EHC(TTE) e)
H
+ HE+
Σ
Vh
2K
h=1
+ 161 0.50 + h== U + 2bk E un XHC(T,()
He + Σ
Vhs
2K
h=1
where the second inequality uses the fact that Q³ is minimizer over F 3 Proiz(Q of L (f) (S1 =f) (which has the same minimizer C. (f) A T)), and the last inequality uses Lemma C.2, and here we define t2 36(e 2)1² (2dr(c) du(e, T) In H1 6b(3h 4)eKH + 15bK Σ En.
Appendix E
Proof of Theorem 3
In this appendix, we give our complete proof for Theorem In order to develop our argument for proving Theorem 3, we shall start with generalized form of posterior sampling in Section E. and develop our key support result in Proposition We then use Proposition 2 and the similar machinery developed in Section D to complete argument for proving Theorem 3.
28

---

E.1 Generalized form of posterior and Proposition 2
We start with recalling the posterior distribution defined in Line 1 of Algorithm 4 as
exp (->La (fre fn+t2)
=) exp (xp mi)
II he(m Bfg-Po.. exp (-1 ( fn+1))
Similar to the proof strategy in Dann et al. [2021], we now consider slightly more general form of the posterior distribution with an extra parameter a E [0, 1] and in an equivalent but more useful form. In concrete, consider any E [0, 1] and define the potential functions:
K
(T, = - (op) +ay
Aba (Jh. Ju+1;
+ a LmnE fn-po
exp
AL fi+1i
R=1
((,T;:) = Σ (J;
h=1
Asf( T) fi(s (s)
where recall that A Jh+1; = defined in Table 3. Define the generalized posterior distribu- tion
D x) & exp - AAf((s1
-
(10)
where it is equivalent to the posterior defined in Equation (9) when a We shall Equation (10) for the posterior for the rest of this section. We shall also define the complexity measure of this generalized posterior counterpart that of the canonical posterior form Definition 2.
Definition 7. Define
-a/(1-a]]
Kn ()) = (1 In 1E Po.s
where recall that F (e; fh+1) = 1s' E Fn supsa (5' fn+)) a)l S E) which defined in Definition 2. Define the complexity measure
do(E,a):=
sup 7E k=1
(a,
(11)
Note that we have
lim do(e, do(e).
We now state our key milestone result Proposition 2 to support the argument for proving Theorem 3. The proof of Proposition 2 deferred to Section E.3.
Notation (. Note that in Algorithm 4, each policy x' for t E [T] is a random variable that depends both the offline data D and the randomization of sampling from the posteriors. That is, when conditioned on the offline data D, each म, still a random variable. We denote P,(-ID) as the posterior distribution of n conditioned D. Note that for any म Pa(-ID) and any L [T]. have मे E (T)).
Proposition 2. For any 7 E [0, 144(e-2)0) > 0, we have,
0, 8 O, a (0, 1). T E N, and any l. E (T) and
0.125 K D
(h) a1 AA (S1, #)
4=1
29

---

Kb2
I de + arH (ux())()),dT( T), In
+ +tabb2 KH max 83 + +HK
a
H
H
+
sup h= (T)
m,) +
sup *Em
In
(e(Fa(e; QT
h=1
now have all main components needed to construct our argument for proving Theorem
E.2 Proof of Theorem 3
Proof of Theorem 3. We start with the error decomposition argument.
Step 1: Error decomposition. Similar to the first step of the proof of Theorem 2, using Lemma B.4,
we have
(51, m1) SubOpt Me (T²) an) (1 = Σ Er (O (sh,
where we denote M, == M(Q,, 7 and Q ($1, == (51, (1,,,T) ((r((ss)) Since term
E SubOpt Me (T²) can be controlled Lemma B.6, remains control
H
= ED
E (Q) ( an) + A (81, ($1,*z) =1)
h=1
Σ En E (fh, fh (s an)l Arfi(s),ii)
Step Decoupling argument.
Using Lemma B.5, we have
H
En 1 Sn+1) an)) (111
0.125Kr
(he v 4bv)) + 0.5XHC(T,
Ky + (s,
He + Σ Vh
h=1
0.125Kr E Eg (sn - #1)
+4
0.5 6e)
K
He +
Σ
Ph
h=1
where ( 0.125Kg
EEIL uh +bb 1== 1/)
Applying Proposition 2, taking the limit - 1 and re-organizing the terms complete our proof.
remains to prove Proposition 2, which is the focus of the remaining appendix.
E.3 Proof of Proposition
Our proof strategy for Proposition 2 builds upon Dann et al. [2021] where the central idea in the proof is upper and lower bound the log-partition function which our case is as follows:
Z, = P.D)
( + XA (81, #) In(()
(12)
30

---

for any t E [T] and any TE N. The key technical distinction is that we need to handle the statistical
dependence induced by ((-P((1D) which is absent in Dann al. [2021]. In concrete, when depends on D, then
(fn. ax) # EK (fr, f1+11 o
since स depends on (sh ) We develop machinery to handle such issue in posterior sampling by carefully controlling the variance the variable of interest (thus we can leverage the variance- dependent concentration inequality in Lemma B.2) and integrating it into posterior sampling using uniform convergence argument. Roughly speaking, several milestone results during the process of developing proof argument, we need to bound the form of
(
[S(f, [
where S(f, n. D) is a function of f. , D. is useful to view S #) as a stochastic process indexed by @f. In our machinery, shall first construct upper bound on the variance of the random process, namely
v(f.) (p(s(f, 1
Using discretization argument, the union bound and Lemma B.2, have with probability least 1 - 6, for any / E FF (T)oft(T), for any E [0, S(,,AD) we have
S(, D) S (O((1) + ED [SU, , म, D)J + (e [S D) (n(N/8)
where OK (1) is a discretization error that can be controlled, and N a covering number of F x 11 (T). Note that S(f. ,,, D) often involves the squared loss which satisfies the Bernstein condition (see Lemma G.1) thus we can roughly bound Ep[S(f, 1, म. D) < a: a|Ep [S(f. म., D)] for some constant a. To integrate the high- gogh-rrobbbilityy bound into in-expected bound, we use the argument:
Ep B a) [S R. D) s 0x (1) + ED ED [S(f, D)] + (e (.-)))EBB Ep D) In(N/0) + Ssup S(f. $if.i H, D).
t
F.3.1 Lower-bounding log-partition function.
In this appendix, we give lower bound the log-partition function defined Equation (12). The final lower bound is presented in Proposition 3. In order to establish such lower bound, we first present a series of support lemmas that will culminate into Proposition 3.
The following lemma decomposes the log- eeg-partiioon function Z into different terms that we shall control separately.
Lemma E.1. For any t E [T] and any T E N. we have
Z, 2 E B/ \ASI #) (1 0.5cr p(filD, po(fi)
K
p(fn, fn+1/1,, PalSn, In+1)
+ 0.5a
Ep B1D
27
AL (Sn, (+11i2))
Br.t
"1
K Σ
+ - a) p(fn+1 / (S(++))
a BeInEg exp
AL (Le Shor1sz44)1
k=1
Ch.*
Proof of Lemma E.I. This is simple adaptation of the decomposition in [Dann et al., 2021. Lemma 6].
We now control each term of the above decomposition of Z separately where majority of these steps are where our technical arguments depart from those in Dann [2021]. In particular, Lemma E.4. Lemma E.5, and Lemma E.7 are our new technical results.
31

---

Bounding As-
Lemma E.2. We have
A, 2 (
Proof of Lemma E.2. It simply follows from that:
(1 - 0.5cx) In p(filD,)) R)
(o( = - (1-00:5a)0Ox((6(111...)) 0.
Bounding B Lemma F.3. For any f, 0 7 72(e-2)6* and h E [H], we have
In E (eLL-m))- (xp fn 2y((1 -
an)²
Proof of Lemma E.3. For simplicity, we write E = Ba We have
In Eexp (-2 fh+11 - E Eexp (- (-2y (fn, fhtti 21)) -1
s L2 (Jh: fn+ 2m) (e- 2-- EA (fr. fh+15 $ 2 (e - 2)2>36b2
) )8, fh+1, # #) an)
where the first inequality uses In S x 1, Vr 2 0. the second inequality uses e < 1 (e
2)x², 1|œ| < and |2-AALa (fh, fn+1i zn) < 18y6² < 1, the third inequality uses Lemma B.1 and
7 72(c 2)82.
Lemma E.4. Define the random variable
(fh fb+1i2)) AL (fnr fa+1i 21) - In B sn (...1.ra)))P exp exp (-2 (fr fa+1; 2x))
For any 7 E [0, 316 I E [0, bo > 0, >>8000 0, T E N with probability at least 6,
holds uniformly over all ă e II (T), fI E Fr. fntz E Fati that
K
k
fhhh + D c
2
k
where
D 120yb(b + 2)
c 32062>2(e 2)t,
(13)
Ek == (h,, fh+1) at).
Proof of Lemma E.4. For simplicity, denote
uk
In (. exp (-2yAL (fh, fn+1:
Ub 2 2y (ha
(14)
We = Uk
uks
= E (Jhr ( at):
We have
2 (s paneersrraa-PP(llll..... Inepp (-27 (fr, f641;2))) = -2ye
32

---

where the first inequality uses Jensen's inequality for concave function In(-) and the equality uses Lemma B.I. Now using Lemma E.3 with 144(e-2)b2 we have
uk S -
(15)
We also have Eeg- = -2 by Lemma B.I. Thus, we have
lual S 2 and E[wx] -2 uk S O.
Hence, we have
Ewi E(ux - ux)²
$ 2B(r + uz)
288 8-
3206272e3
where the first inequality uses Cauchy-Schwand inequality. the second inequality uses Lemma B.1 and that [ug| I 2ye2. and the last inequality uses that lex| S 2b. Also note that |wrk I 0k + [ug I
(962) + 2y(4b²) 26yb². Thus, by Lemma B.2, for any 8 > 0, for any E [0, 26 l. with probability least 1 5, we have
K
K
K
ln(1/0)
Wk
EwGs + (e - 2)t
W
t
1=1
k=1
k=1
Im((/0)
< 32062 2( 2)t
k=1
We apply the discretization argument and the union bound to obtain that: For any ö > 0,e > 0,
T E N it holds uniformly over all ã E 11 (T), fn E Fhi fh+11 E Frt1 that
K
c + 2dz(c)
dnle, T) + In(1/8)
wk S 3)002 2)
Σ
k=1
Lemma E.5. For any [0, 144(e-2joz1 e 0, 0.8.3 0, we have
K
B₁ 2
Σ
(Sh. (na
2 -120gb(b+ 2) - 640(e - 2 (2d=(c) + dule, T) + In(1/5)) 26 K8.
Proof of Lemma E.5. Define the random variables Ugy Uk Wk: eg Equation (14). Recall D,c defined in Equation (13) for any t E [0. 26 Define the event E' such that the inequality
K
K
Σ
(fn, fh+112 < 32062 2)t
ot DD
(16)
holds uniformly over all 11 (T), Fn, fr+1 E Fr41. By Lemma E.4, we have
Pr(E) 2 - 5, thus Pr(E") < 8.
We have
wi + cot) + in p(Jn, fo+1 fn+1)
33

---

K
(-wk Wi + cef) + p(fn, fn+1)
2 EDEa D) inf Eynp
Σ
po Sn+1)
K
= --EpEE=P((PD)) In I exp
(Wk oE
k=1
K
(E In
f In exp
ww ceti
k=1
k
- -E In B -opp exp
[w/ - ce
k=1
K
> -BD((E)B+=<((1))) In fn exp
(wn cett
26-yb² K8
D 26>b K6,
(17)
where the first equality uses Lemma G.3, the second inequality uses that Pr(E") S 8 and E cet) S Σk wk I 26>b² K and the last incquality uses Equation (16). Thus, using the same notations as Lemma Lemma E.4, we have
K
Uk + In p(hn In+1lD, (D Polfn fn+1)
ВA = EpBi
K
PlJn fnt1lD po Polfns fh+1)
= BDB)
(- wk + ce In
+
(-ux Uu cett)
K
2 - - --D-26-b2 + (T - C:E (opti,1)
2
where the inequality uses Equation (17) and Equation (15). Finally, setting
t 640b2 2)7 1362
completes our proof.
From squared Bellman errors to in-expectation squared Bellman errors and fixing rigorous argument of Dann et al. [2021]. Lemma E.5 only bounds BN with the squared Bellman errors ΣK E (fh, fn+1) a² while the in-expectation squared Bellman errors Σx= Ex [E (fr. (SA, an ) are what we need for showing Proposition 2. There is no an immediate path to go from the squared Bellman error to the in-expectation squared Bellman errors as the order of ED and ERMPL D) () are not exchangeable, i.e.,
K
(1D)
EA (fn, ( oh)
+ EDDEnP Di DjBy~MMiDDr
Σ Bun 18, (Jn, fho (sn, an)²)
(18)
A similar caveat arises in the online setting in Dann et al. [2021] | well. In particular, non-rigorous argument of [Dann et al., 2021, Lemma 8] is that they conclude (an online analogue of) the LHS of Equation (18) is equal to (an online analogue of) its RHS.
34

---

To fix this issue without ultimately incurring a sub-optimality rate that is slower than 1/vK, K, we need change the squared Bellman error into the mn-xpectation squared Bellman error, up some estimation error that scales faster than k for any 0. Note that, standard Azuma-Hoefiding inquality (and the union bound) give an estimation error that scales with K1/2, To achieve the logarithmic dependence on K, the following lemma exploits the non-negativity of the squared Bellman error and uses the localization argument of Bartlett et al. [2005] to obtain an estimation error rate that scales polylogarithmic with K.
Lemma E.6 (Improved online-to-bate argument for non-negative R.V.s INguyen- Tang et al., 2023]). Let { be any real-valued stochastic process adapted to the filtration {Fk), i.e. XN is Fk- measurable. Suppose that for any k, Xx H]] almost surety for some H > 0. For any K > with probability at least 5, we have:
K
16 Xx+
E [X
H log(log2(KH)/00 +
With Lemma E.6, we now actually make connection from the squared Bellman enror to the in-expectation squared Bellman eπrоr in the following lemma, which incorporates the uniform convergence argument into the posterior sampling in the same spirit with our earlier argument in Section E.3.
Lemma E.7. For any d,e E andd T N. any E [T],
we have
ED D) Σ
E (fn, fsh at2²
K
2 0..EED R.
Σ
Bu [8 (Jhn Jh+
- b(b+ - 213 13 (2d((c) + dn(e, +1n
In
2K82..
3
8
Proof of Lemma E.7. For simplicity, we denote X(f.D) = Ek E (fr, fn+2) (5% att) and
Xf) = (f D)}, and = -bKe 61 (2dx(c) + dule, T) + In 1K12
+ 2.
We de-
0
fine the event:
E { S 2X(f + A, Vfn E fa+1 E Fu+i. i II f (T)
Due to the non-negativity of E (Jn, (s, a) Lemma E.6 and the union bound, we have
Pr(E) ô and Pr(E") 8.
We have
2 BE X(,D)
www.::/wwww......-...---------e- 2 2
2 Wbb1":jBe..r.mmpp<>>>>p>a (P(()
2 (p21::_lee.rnmppp0//////aaa11111
EDDEaPP( B X() Ep1 (F (I
2 EDEE, X - A Ep (
= EDEE (D.) X(f) A 4KB Pr(E")
2 E X()) A 4Kb28
where the fourth inequality uses [X(]) > 4Kb2 and the last inequality uses Pr(E") 8.
35

---

Bounding Ch.
Lemma E.8. For any > 0 and T E N, we have
Ch,t 2
max (x - yabbKe.
*T)
where (a, R, is defined in Equation (11).
Proof of Lemma E.8. We have
K --
ALa a (Fh Shalizt) ) + (1 - anln p(Jn+1 1D,
Cr = PO a BaInBg-a Bo exp
Σ
po(s++))
(1 P1
a In InE exp
Al ATx Shot1 (htt +
p(Jn+1 (D, po(fn+1)
1
k=1
ALa Aha )
2 (1 - ED Bn 11
Byg-po exp
max (T)
(a, e, yabbKe.
where the first inequality uses Lemma G.3 and the last inequality uses the following inequalities: For any fh E Fa fh+1, we have
A (Jh. fh+1; 2n) S 6b| 6blE, (hh, f1+1)l S 6bc; thus
E -P exp
AL (Ths fhttiih) 2 -
k=1
We are now ready state the complete form of the lower bound of Z. Proposition 3. For any 7 E [0, ( 5 > and any [T], we have,
2 2 XED ERND, By ()),
K
0.125a7
Σ
Epp [ (Jh, fn+ (sn, )s)
km1
0.5aH (120>b(b + ke 640(e - 2) (2dz(e) + dmle, T) In(1/o))) - 13077 H88
H ((lb+2)K3 +
32
(d)(()) + dnle, T) + In
In 4Kb2
+ +1+ 31+2K066)
3
8
Kn(a,e, 706KKHe
RElloos(T)
Proof of Proposition 3. Using Lemma E.I, it suffices bound terms A, Bbs and C₁ defined in
Lemma E.I. For this purpose,
Lemma E.2: To bound A
Lemma E.5 and Lemma E.7: To bound BA.
Lemma E.8: To bound Ch,t-
The result is then simply direct combination of the above lemmas.
36

---

E.3.2 Upper-bounding log- wyg-partiioon function
In this appendix, we upper bound the oeg-parition function Z. While we follow the proof flow in Dann al. [2021], due the statistical dependence in the actor-critic framework of our algorithm. we require different technical arguments to establish this result. In particular, Lemma E.9 and Lemma are our new technical lemmas.
Proposition 4. For any e, 8 > 0. O, and & E [T], we have
Σ Impo((F((s))) + +4 a 3(e 3(e-2)) HKe²
H
Z: S Ae
inf *ETT-O/((T (T)
a
- -60ary(bb + 2)K aryb H (13 + 36(e - 2)) (2dr(c) dn(c,T) In(1/8) + 180ry888KK K KHb2..
where recall that Z, is defined in Equation (12).
Proof of Proposition 4. We have
2. =
([ + (n
EEpEa (-D) BnfB SaD
+ XAf (f
( +)
In p(f)
H
K
< P inf
on
A (Jn, Ju+1: + (AS1(11
Po(
h=1k=1
K ~
-EEDEe inf s~p
IE JANupO exp
1m
where the second equality uses the fact that DKL [pllø] 2 0 with the minimum occurring at = f and the inequality uses the triangle incquality. The first term is bounded by Lemma E.9 and Lemma E. and the second term is bounded by Lemma E.
It remains state and prove Lemma E.9, Lemma E.11 11 and Lemma E.
The following lemma bounds the in-epeectation of the loss AL by the in-expectation of the squared Bellman error.
Lemma E.9. For any distribution p over For any e, 0, r > any E [T], we have
K
AL (fr. fn+1i2h)
ary
kml
$ at 3(e 3(e + 3000b(bb + 2) 13 (2dz(c) + dn(c, + In(1/)) + 90y Kb25.
Σ
E (fh. fi+1) at)2
a
Proof of Lemma E.9. For simplicity, define
Ih == ay (fr, f14152)))
e E (fhr (o at.)
By Lemma B. we have
B|ra] a7
Bia < 3602 2e2
Thus. by Lemma B.2, for any 8 > 0, with probability at least - 8, for any t E [0, 1367762
we have
ln(1/6)
E[ra] + t(e 2)
B
B
t
37

---

Σ o + ln(1/8)
K
S (ar + -(e 2)3662 72)
Using the discretization argument and the union bound, we have that: For any <> 0, 0, we have Pr( F.) 2 6, thus Pr(E*) S 8,
where E denotes that event that for any E [0, 13076=
2dz(c) + du(e, + In(1/6)
T& I 300rr(b+++20 2) +ary t(c 2()-)))6 a 7²7²)
c
t
k=
any fn E Fri fh+1 E Fu+1, 7 11 (T). Thus, we have
K
K Σ
Ep (
Σ
Tk
= Epl (B
Σ
IK
+ ( Bsp
< =
(oor)bb++2)6
2dz(c) + dnle, T) + In(1/))
+ +(ay + +te 2)
9ayy
E
t
<EDEE-r/(D))//// 306(b 2)
c + 2dz(e) + dn(e, T) ln(1/ + 9a'.
+ (ary + - 2)36a
2)366 26,
t
Picking
/
1307b7 completes the proof.
The following lemma bounds the in-expectation negation of the loss proxy ALg.
Lemma E.10. For any 5 > 0, 0, > O. any fr E Fr. any t [T), and any distribution p over F. we have
ALa (fh. fn+1ish)
s 36(e 2)yb² (dr(e) + dn(e, T) In(1/8)) + 9yy''28 + 30>b(b + Ke.
Proof of Lemma E. For simplicity, define
= AL (fhr Snt1i
= E (fh. (5 o..).
By Lemma B. we have
I [v) -
E [
< 36622222
Thus, by Lemma B.2, for any 8 > 0, with probability at least 8, for any / [0, 1 we have
K
In(1/8)
Uk
E Elyn]
+
+ 2)
Σ
E.
Ely
k=1
h=
ln(1/8)
S 5 (1 366(c 2)622))
38

---

Setting t 36(e-2)627 13:62
in the above inequality, we obtain
yk 36(e (of(e-2)633 2)-22
Using the discretization argument and the union bound, we have that: For any <> 0, 0, we have
Pr(E) 2 1- 6, thus Pr(E") s
where E denotes that event,
K
Uk S 30yb(b + 2) 36(e 2)yb² (dz(c) d) Im(18))
any fa+1 Fhti, E (T).
Thus, we have
K
k
K
ED E /~p
Σ yk = Ebl (D
Σ
1/h
+ (BDI(F"JRA-P(1))
1/k
k=1
< (30>b(b+))K3 36(e 2276? + dm), ln(10)) (n(()) +
The following lemma bounds the in-expectation squared Bellman errors with the regularization term and the data distribution term, under the infimum realization of the data distribution p.
Lemma F.11. For any 0, 2 0, any E [T), we have
EDEE~P((1)) inf En T~p AAfi(51, #) + In p(f)
M
o
Pf(
h=1km1
Se
inf Inpo(Fa(e:(E) Q+)) + 4 (TTT
where recall that Fule; fn41) is defined in Desinition 2.
Proof of Lemma E.II. For any f E F(c; Q*), we have
1l. 15 V,
Thus, have
(f,, fs+1))
S [h f1tillo0 |T T - fb+1 1l
< |Tif Ti -1fftt1 1h+1llo
$ 2c.
Thus, by choosing
p(f) Poff) E F(a))) ()(F(E(7)
we have
inf E (AS((s1 7) +In p())
ΣΣ & (1+ a/)3
H K
+ 3 Po(
k=1k=1
< Ae - (npooo 43HKe..
We by now have everything needed to prove Proposition 2.
39

---

E.3.3 Proof of Proposition 2
Proof of Proposition 2. By Proposition 3, we have
Z, 2
AED
H
K
+ 0..12507
PIDD
Σ
E (Sh, (ʃh, fn+1) an)a]
k=1
- 0.5aH (1207b(b+ + 2) 640(c 2)7b² (2dz(E) + dn T) ln(1/)))) 13ar6b K H8
0.250HH
((bb+ 2) 2213 2d((() + (n(e.T) 5
In
+1 (1+2K66)
Σ
max xEII=Of(TT
(n yo6bK He.
By Proposition 4, we have
H En In (o + (a+ 3(e-2) HK²²
7. S
inf (EII-O/(T)
a
h=1
600 + 2) HE + y (13 + 36(e 2)) (2dr(c) dn(s,T) + +ln(1/6) + 180r HB25.
Thus, have
H
EpD 0.125a7 K
Σ
1 (fh, (n,, fh+1) an) AAfi )
4=1
Kb2
S de + ay/ max dule, T),
+ aryb² KH maxte, 8) + +HK
8
max (a, an) h=1 empet
sup RE h=1
Σ In
Po Po(Fi(e; (²
Appendix F Proof of Proposition
In this appendix, we prove Proposition which is a simple reduction from Theorem 1, Theorem and Theorem
Proof of Proposition 1. simplified bounds of all three algorithms into one unified form under no misspecification, and Part (ii) the specialization of the unified bound into the special cases of finite function classes and linear function classes.
We recall that Proposition I consists of two parts of statements: Part (i) the
Part (i): The unified sub-optimality bounds for VS, RO, and PS
We recall that the first part of Proposition I is that:
Vn E (# # "ro, EpSubOpt, = Ô H1b
Hb In Vol(A)
V ((/KK)/((m1//KK)
VR
(19)
where
ā(1/K) dopp (I/KTT) (1/K.T
if (""",ar0}
f
where we recall in Section 4.2 that
dope T) = max(dr(e))
40

---

Tp max(d=()), T), do(e) dy(E) ?HI? ?H12
and de(e), (e, T), do (e), and (e(e) are defined in Section 2.4. Also recall that for Proposition 1, we assume that there is no misspecification, i.c., En = Ph = 0, Vh E [M].
For Ahe. follows from Theorem 1, where we choose c = 1/VK, and c = 1/K that with probability least 1 26, have
SubOpt, S v H. 1/: max (1/K, + H) + H/VKK + Sopt
Hby In Vol(A)
- V 1K1--HHO C(;
T
Thus we have
Hb VK 1(7:1/VK) max (1KKT))) + Hby In (ol(
SubOpt, (#""))
0 (=
T
(20)
For #*9. The sub-optimality bound for # is obtained from Theorem 2 with the same parameter
setting as that for = where set = 1/K, e.. 1/VK, and T 2 K In Vol(.).. Additionally, shall need to set the regularization parameter X. Since the bound Theorem 2 holds for any X > 0,
shall minimize this bound with respect À > O, which results in the optimal À
2K max (1/K, (nH
A
H1 1CC,
and the sub-optimality bound
Hb VR
+ Hb /n Vol(A)
(f =
ClT:1/VK)
max/dopt
T
(21)
For tp* We specialize the sub-optimality of R2 from Theorem Similar the case of n and h we set: 1/K, & = 1/VK,, and T' K in Vol(A). Additionally, we need set the failure probability E [0, 1], the learning rate [0, 144te-2j6z and the regularization parameter À > 0. For 8, set 1/K, For A, we minimize the bound in Theorem 3 with respect to X, which results into À = X. which is give as
KH12 max (dpa (1 Ink (n(KIn(Kb2))
A
H H-C(m, 1/vK)
turns the sub-optimality bound into
(H* = = Hb VK
max(dpo (1/ (X(KKK)))))) (n(3)))) + Hb In Vol(A)
C(T:://VK)
T
(22)
Finally, we choose 7 [0, 144(e- 2 minimize de, mmx(dd>()) dn,, T), da(e) de(c) which occurs ? 144(e-2j0 and thus
7H. 7H }.
(c, T) max { ( (d>(), dn(s, T), 144(e - 2)da(c)
144(e (2)
(23)
H
H
Overall, we have that Equation (20), Equation (21), and Equation (22) can be unified into Equa- tion (19).
41

---

Part (ii): Specializing to the finite function classes and linear function classes
We consider two common cases.
Case 1. Finite function class. We consider the case that Fn and (T) have finite elements for all h [H]. Then we have d(()) (maaxNe[M) max In [Fll, In (T)))) Ve, due to that (c) S do(c) S H maXne(H] In Fr and Equation (23).
Case 2. Linear function class. We consider the case that the function class F4 is linear in some (known) feature map 0% :S x A + R. Concretely, the corresponding function class and the policy class defined in Section 2.3 are simplified into:
Fn {(s, a) + (on(s, a). w) ||w||2 - b}.
11 (T) = { (s. Eves exp (xp((onss,a').0) 1101 - nT)
exp( (p((on a),
We have
dr(e) dln(1 2b
=)
dn T) S dln(1 16nT
(e) do(e) eidH In(c2/e),
where the first two incqualities use [Zanette al., 2021, Lemma 6] and the last inequality follows the discussion in Section 2.4. Note that dn(c, T) depends only logarithmically T.
Appendix G Support Lemmas
In this section, for convenience, we present some simple yet useful lemmas that our proof's above often refer to.
The following lemma establishes the variance condition for the squared loss, which is typically used along with Bernstein's inequality.
Lemma G.1. Consider any real-valued function class F. Consider the squared loss L(f(x), y) (f(x) - y) Assume bounded loss ((f(x), y) < M for any f E F, for some M > 0. Let
f.(x) Elylæ] and assume that L(f=(x),y) < B² for some B > (we do not require that f- F).
Let z = (I, y) and define
6(2) = L(f(x), ((. G == [o(-) (
Then, for all o E G. we have
E,(o(2) 2(M² + B B3)
where By is the expectation taken over y given
Proof of Lemma G.I. Consider any o E 9 (with the corresponding f E F). For any æ, we have = -(()))
Thus, we have
0(2) = (f(x) -
2n)² 5 - ((()))-(())((()))--- (z) + (f-xx) - =1)
< 2(M + (f))
The first inequality uses Sauchy-Schward The second inequality uses that f- E F and L(f(x). S M vff F. Thus, for any x. we have
[y < 2(M + (²)( [+()))) = 2(M2 B²)En(o(=)}
The equation uses that [0)]] (f(x) f
42

---

The following lemma is simple decomposition of the value gap in the initial state, typically known as the performance difference lemma in the RL literature.
Lemma G.2 (Performance difference lemma). For any policy n. Tr, we have
(s1) V (s1)
Σ Br (Tk an) VI (sh)
where Ex denotes the expectation over the random trajectory (81, a.,...; 8hs an) generated by m (and the underlying MDP).
Proof of Lemma G.2. We simply expand (s1 Ee, (1 a1) + (12)(2)) and use recur- sion to obtain the lemma.
The following lemma presents a simple connection from a form of a log partition function to the expectation under the infimum realization of the sampling distribution. Lemma G.3. For any density functions p and po and any function f, we have
p(æ)
inf inf Emp(()) f(x) + In
- - Ezwpo exp(-f(x))
Po(x))
Proof of Lemma G.3. Define the density function
Po(x)) exp(-fff [(x)) where Z(f) (x exp(-f(xx))
((x)
Z(J)
Then, we have
Exnp(e) [(x) + In p(x)
Exnp(z) p(a))
Z())
(xr)
g(x))
KL[pllg] In (ff)
2 Z(f).
43


Reviews:
[{"review_id": "nwB2ZEvrBe", "reviewer": "Reviewer_niYV", "summary": "This paper introduces a novel data coverage measure called \"data diversity,\" which is more stringent than existing data coverage measures like single-policy concentrability. The authors claim that actor-critic algorithms based on VS, RO, and posterior sampling can achieve state-of-the-art sample complexity. The posterior sampling based algorithm is the first of its kind for offline RL.\n", "questions": "None", "limitations": "None", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The new data coverage measure is innovative and tighter than existing measures in the literature. The authors' demonstration of good sample complexity under this measure is an important contribution. Additionally, the framework and the posterior sampling approach for offline RL are novel.\n", "weaknesses": "However, I have some doubts about the claim that these algorithms achieve the state-of-the-art convergence rate. The policy $\\hat{\\pi}$ is obtained by uniformly drawing a $t$ from $[T]$ and letting $\\hat{\\pi}$ be $\\pi^t$. This policy is not a Markov policy. According to the definition of $V^{\\pi}$, $V^{\\hat{\\pi}}=\\frac{1}{T}\\sum_{i=1}^TV^{{\\pi}^i}$. Is this correct? The $1/T$ term comes from the additional expectation over the uniform distribution. For the chosen $t$, $\\pi^t$ can have constant variance, and as a result, the high probability bound may not hold for this chosen $\\pi^t$.\n\nOn the other hand, recent literature such as \"Optimal conservative offline RL with general function approximation via augmented Lagrangian\", \"Offline Primal-Dual Reinforcement Learning for Linear MDP\", and \"Revisiting the linear-programming framework for offline RL with general function approximation\" have policies that are Markov policies and achieve the state-of-the-art sample complexity. Therefore, the authors should compare their results with these papers.\n\nTo ensure a fair comparison, the output policy should be a Markov policy. If not, the authors need to clarify this in the introduction and after the theorems. Additionally, the authors should clearly explain the source of randomness for $\\hat{\\pi}$ in the theorems.\n\nIf the authors can address these issues clearly, I would increase the rating. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback. We address all of your concerns below.\n\n---\n####  **Concern 1**: **\"This policy ($\\hat{\\pi}$) is not a Markov policy ... \"**\n\n**Our response**: \nWe understand our notation in line 7 of Algorithm 1 might have caused some confusion. To clarify, $\\hat{\\pi}$ is simply chosen uniformly from the policy set $ \\{ \\pi^1, …, \\pi^T \\}$. We emphasize that $\\hat{\\pi}$ (as well as each $\\pi^t$) **is Markovian** (i.e., at each step $h$, each $\\pi^t_h$ depends solely on the current state). The uniform mixture of policies (resulting from the multiplicative weights algorithm) and its Markovian property are quite standard in the literature, e.g., see [ZWB21], [XCJ+21], [CXJA22].  \n\n---\n\n####  **Concern 2**: **Comparison with recent literature [1][2][3]**\n\n> **Relevant refs**: \n\n> [1] Paria Rashidinejad, Kunhe Yang, Stuart Russell, Jiantao Jiao. \"Optimal conservative offline RL with general function approximation via augmented Lagrangian\". ArXiv 2022 (cited as [RZY+22] in our submission). \n\n> [2] Germano Gabbianelli, Gergely Neu, Matteo Papini. \"Offline Primal-Dual Reinforcement Learning for Linear MDP\". ArXiv 2023. \n\n> [3] Asuman Ozdaglar, Jiawei Zhang, Kaiqing Zhang. “Revisiting the linear-programming framework for offline RL with general function approximation\". ArXiv 2022. \n\n**Our response**: \nWe believe that the primal-dual methods, e.g. [1][2][3] and [ZHH+22, CJ22] provide an important alternative to addressing offline RL. However, as we also acknowledged in footnote 5 of our submission, the guarantees of primal-dual methods use **a different set of assumptions** than the value-based methods we considered (the former assumes realizability for the ratio between the state-action occupancy density of the target policy and the state-action occupancy density of the behavior policy, except for [2] where this assumption is implicitly realized under a stronger assumption of linear MDP). This makes the results presented in our paper and the results in [1][3] **not directly comparable**, though our results and [1][3] both achieve the optimal sample complexity of $\\mathcal{O}(\\epsilon^{-2})$. \n\nSince [2] (which appeared online on May 22 after the main submission deadline) works in linear MDP, [2] is more comparable to the instantiation of our results to the linear function class. [2] consider primal-dual methods for offline RL in both infinite-horizon discounted MDP and average-reward MDP. Our analysis framework for the regularized optimization method in the episodic MDP should translate to the infinite-horizon discounted MDP as well, where the regularized optimization achieves the optimal sample complexity of $\\mathcal{O}(\\epsilon^{-2})$ while the sample complexity in [2] in this setting is $\\mathcal{O}(\\epsilon^{-4})$.  However, [2] offers a better computational complexity ($\\mathcal{O}(K)$ vs $\\mathcal{O}(K^{7/5})$ ) (where $K$ is the number of offline episodes) and also works in the average-reward MDP setting which is beyond the episodic MDP setting considered in our work; though our bounds hold for general function approximation that is beyond the strong assumption of linear MDPs in [2].  We will add this discussion and comparison in our revision."}, {"review_id": "1w0Jt90ftL", "reviewer": "Reviewer_YpYn", "summary": "This work aims to point out what enables the sample efficiency of offline reinforcement learning.\nThe authors first define a new notion of data diversity based on the inducing the Bellman error under one policy with the Bellman error under a different policy.\nThe authors then propose a unified view, Generic Offline Policy Optimisation framework, to study the three offline algorithms: version spaces, regularised optimisation, and posterior sampling.\nUnder standard assumption, the authors showed that all these three algorithms can achieve comparable upper bounds of the policies' sub-optimality.", "questions": "1. Can the authors comment on the *performance* as well as the *time complexity* of possible PS implementations?\n(See the major issue #1 in the weakness section)\n\n2. What are the slight refinements in line 190?\nThe authors claimed that they have made slight refinements to the RO-based and VS-based algorithms, but they haven't mentioned these refinements anywhere else.", "limitations": "See the major issue #2 in the weakness section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The proposed view is novel, and can unify the three different types of offline reinforcement learning algorithms.\n\n2. The whole work is very well presented, and the structure is super clear, which raises a high comprehensibility.\n\n3. All definitions and assumptions are explicitly and clearly given in Section 2. I personally love this practice, as it helps a lot on figuring the scope of this work.\n\n4. The results are also well-organised and clearly listed in Section 4.\n\n5. The connection between this work and [TJJ20] is clear, thus it's interesting to see that offline RL can be connected to transfer learning, though there are certain technical differences.", "weaknesses": "### Major\n\n1. **Practical issues of posterior sampling algorithms**:\nMy biggest concern about this work is the performance of the posterior sampling based algorithms in practice.\nI appreciate that the authors remark some feasible solutions to implement an offline RL algorithm based on posterior sampling from line 241 to line 245.\nHowever, given the tractable approximations from line 243 to line 245, I kind of worry the *performance* as well as the *time complexity* of the PS implementations.\nI'd be happy to raise my score if the authors can discuss further details about this concern in the updated version.\n\n2. **Discussion about the limitations**:\nThe authors mainly focus on the missing variance information in their discussion about the limitation of the work.\nGiven the assumptions listed in the Section 2.3 as well as the practical issues I mentioned above, the limitations can be expanded to cover all of them.\n\n### Minor\n\n1. $H$ in line 107 and line 110:\nThe authors can move the notation $H$ from line 110 where it's defined to line 107 where it first appears.\n\n2. $t$ in line 129 is not defined:\nThough the meaning of $t$ can be inferred given the context, it's better to be defined before its appearance in line 129.\n\n3. Introduction section is too lengthy\nI appreciate the gentle and comprehensive introduction to this work in Section 1.\nBut, it might be a bit lengthy, and as a result Section 5 is too short to further discussion about the limitation and future directions of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your positive feedback. We address all of your concerns and questions below.  \n\n---\n#### **Question 1**: **Practical issues of posterior sampling**\n\n**Our response**: We emphasize that **the focus of our paper is on the statistical aspects of offline RL** and **not** on the computational aspects (nor on any practical approximation or implementations). Our remarks on lines 243-245 serve merely as remarks regarding implementation/approximation for the interested readers/practitioners, rather than a formal treatment. We do not claim any practical insights into posterior sampling as a contribution. \n\nRegarding the performance and computational considerations regarding posterior sampling in practice, we would like to make the following comments. First, our posterior sampling is oracle-efficient, if we assume access to the expectation-computing oracle and the sampling oracle. As we noted in our paper (Lines 241-245), the expectation-computing oracle can potentially be replaced by another sampling oracle, inspired by the recent idea of [AZ22]. More specifically, $f’$ in the denominator of the likelihood in line 1 of Algorithm 4 can be replaced by a random sample from an inner-loop posterior distribution.  In turn, the sampling oracle in practice can be approximated by first-order sampling methods such as Langevin Monte Carlo. A rigorous treatment of this idea in our case is another avenue for future work. \n\nSecond, the performance (both statistically, computationally, and empirically) of such first-order sampling approximation to posterior sampling (even for online RL and especially for offline RL) is another active research area. As a concrete example of the success of first-order sampling approximation to posterior sampling, a recent work of [2] shows that in (online) high-dimensional linear contextual bandits, one can use Langevin Monte Carlo (LMC) to approximate the “feel-good” Thompson sampling [3] (a posterior sampling algorithm that lays a foundation for our pessimistic posterior sampling algorithm) where  LMC obtains an optimal sample complexity of $\\mathcal{O}(d^2/\\epsilon^2)$ with the computational complexity of $\\mathcal{O}(d^{9}/ \\epsilon^8)$ ([2] also showed the superior performance of LMC compared to standard posterior sampling in their experiments). \n\nThird, as a note about using sampling in place of optimization,  in certain non-convex settings, sampling even converges provably much faster than optimization (e.g., $\\mathcal{O}(d/\\epsilon)$ or $\\mathcal{O}(d^2 \\log(1/\\epsilon))$ vs $\\Omega((1/\\epsilon)^d)$ in the non-convex setting considered in [1]). Thus, it might be possible that the computational complexity of the LMC algorithm (to approximate our pessimistic posterior sampling) is smaller than that of the regularized optimization-based algorithm in certain scenarios. However, this speculation needs a more formal characterization which is also an avenue for future work. \n\nWe will add this discussion to our revised version. \n\n**Relevant refs**:\n \n[1] Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I. Jordan. “Sampling can be faster than optimization”. PNAS 2019. \n\n[2] Tom Huix, Matthew Zhang, and Alain Durmus. “Tight Regret and Complexity Bounds for Thompson Sampling via Langevin Monte Carlo”. AISTATS 2023. \n\n[3] Tong Zhang. “Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning”. SIAM 2022. (cited as [Zha22] in our submission)\n\n---\n#### **Question 2**: **Clarification of ”Slight refinements”**\n\n**Our response**:  We consider episodic time-inhomogeneous MDP instead of discounted MDP, thus the algorithms are refined accordingly. For the version space algorithm, compared to [XCJ+21], we employed the actor-critic framework instead of directly solving the min-max optimization over the function class and the policy class."}, {"review_id": "HbrQs9af8g", "reviewer": "Reviewer_ufo5", "summary": "This paper investigates the problem of sample-efficient learning from historical datasets in the context of offline reinforcement learning and explores the role of data diversity and posterior sampling in improving the efficiency of RL algorithms. The authors propose a new notion of data diversity and study three classes of offline RL algorithms based on version spaces, regularized optimization, and posterior sampling. They find that these algorithms achieve comparable sample efficiency, contrary to prior work. The paper also introduces a novel model-free posterior sampling algorithm for offline RL.\n\n", "questions": "n/a", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work studies offline RL problems within the context of general function approximation. The introduction of the novel notion of data diversity is intriguing, as it offers a fresh perspective on the problem. Additionally, the inclusion of the posterior sampling algorithm is interesting, as it appears to be a new contribution to the literature on offline RL theory. ", "weaknesses": "It is important to ensure the accuracy of the comparison with LCB-based algorithms, as the algorithm mentioned in [JYW21] may not be considered the SOTA algorithm when compared to improved LCB-based algorithms proposed in works such as [1] and [2], which have demonstrated better dependencies on d.\n\nAdditionally, it is worth noting that there has been an update in [XCJ+21], where a new arXiv version employs $\\Pi^{soft}$ instead of $\\Pi^{all}$. While this minor issue does not impact my evaluation, it would be beneficial for the authors to acknowledge this update and adjust the comparisons accordingly.\n\n[1] Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism\n\n[2] Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your positive feedback. We address all of your concerns below. \n\n---\n\n#### **Concern 1**:  **Compare with [1][2]**  \n**Relevant refs**: \n> [1] Ming Yin, Mengdi Wang, Yu-Xiang Wang. “Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism”. ICLR 2022. \n\n> [2] Wei Xiong, Han Zhon, Chengshuai Shi, Liwei Wang. “Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game”. ICLR 2023.\n\n**Our response**: We will update the comparison of the instantiation of our results to the linear function class to the results of [1][2] in our revision. In this case, the bounds in [1][2] have the same dependence on $d$ as our bound and have a tighter dependence on $H$. We remark that this improved dependence on $H$ of [1][2] is due to the variance-weighted value iteration algorithm that they employ to capture different (heteroscedastic) variance of the transition kernels $P_h$ at different time steps $h$. This improved dependence on $H$ comes at the cost that the algorithm is more complicated and they need the offline data to be explorative over all dimensions of the feature map so that the estimation error of the variance can be controlled. \n\nWe remark that leveraging the variance information (using the variance-weighted value iteration) as in [1][2] is **complementary/orthogonal** to the basic algorithms we study in our paper, i.e., this idea can be added to our algorithms to improve the dependence on $H$, as we discussed as future work in Section 5. \n\n---\n\n**Concern 2**: **Compare with updated version of [XCJ+21]**\n\n**Our response**: For the version space-based result, we compared with Theorem 3.1 of (the latest version of) [XCJ+21] where their bound scales with the complexity of the comparator policy class (not the soft policy class). We believe that the updated version was to correct their Theorem 3.2. For comparison in the linear case, we included the bound in their Theorem 3.2 of their updated version in Table 2 of our supplementary. For the regularized optimization-based algorithm, [XCJ+21] employed $\\Pi^{soft}$ instead of $\\Pi^{all}$, as we acknowledged in our Table 1.  Regardless, we fully acknowledged the invention of the version space-based algorithm and the regularized optimization-based algorithm (for offline RL) to [XCJ+21] (e.g. see Line 189-193)."}, {"review_id": "VSLgvSyb8C", "reviewer": "Reviewer_FhSe", "summary": "This paper proposes a new notion of data diversity that expands all the prior data diversity conditions in offline reinforcement learning literature. Based on this notion, the paper develops concrete value sampling-based, regularized optimization-based and posterior sampling-based algorithms with corresponding sample complexity results. The paper shows that these three algorithms can achieve comparable sample efficiency.", "questions": "Could you please explain how the new diversity notion is able to cover value sampling-based, regularized optimization-based, and posterior sampling-based algorithms, especially posterior sampling-based algorithms? Is it because the previous diversity conditions are not always able to cover all three types of algorithms? If the previous conditions are able to cover all three types, is the main advantage of the new notion its tightness? If the previous conditions cannot cover any of the algorithm types, could you describe the reason behind their failure and why the new notion is able to succeed? ", "limitations": "See weakness.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The proposed data diversity condition and its corresponding suboptimality guarantee seem to be general and tighter than previous diversity conditions characterizing the state-of-the-art bounds for the main streams of offline reinforcement learning frameworks. This data diversity condition is a potential inspiration for future work.\n\n2. The writing is clear and presents a fair and clean picture compared to previous results.", "weaknesses": "There are some typos and inconsistencies in the notation, such as $p_{0,h}$ in $p_{0,h}(\\mathcal{F}_h^{\\tilde{\\pi}}(\\epsilon; f\\_{h+1}))$ in line 176 and $f_h$ and $g_h$ in Algorithm 2, which should be $f$ and $g$, respectively. Similar inconsistencies appear in Algorithm 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your positive feedback. We elaborate further on the data diversity notion below. \n\n---\n\n**Question**: **About (the advantage of) data diversity**\n\n**Our response**: Our notion of data diversity provides a tighter characterization of distribution shift than the previous notions of data coverage and facilitates a unified framework for the analysis of the three algorithms we consider. That said, our tight(er) results (especially) for the regularized optimization-based method and the (new) posterior sampling-based method come from our refined analysis, not solely from the data diversity notion alone. The idea of the data diversity notion, which we discovered naturally and turns out to be inspired by the transfer learning literature, is to account for the error when we decouple the Bellman error under a target policy into the squared Bellman error under the behavior policy. With the data diversity notion, we showed that the scenarios for the offline data in which offline RL is learnable are enlarged compared to the picture depicted by the prior data coverage notions. With our refined analysis, we showed that the regularized optimization-based algorithm and the new (pessimistic) posterior sampling algorithm are not only provably efficient but also have comparable guarantees just as the (intractable) version space-based algorithm (under standard assumptions)."}]

Author rebuttal:

Meta-review: The paper considers a new notion of diversity in offline RL, and shows the efficiency of regularization optimization and posterior sampling approaches. It contains interesting ideas, and in general, the reviews are positive. However, there was some concern regarding the comparison to another series of works that can "directly" output Markov policies with "high" probability, while the present paper outputs a "mixture" policy. Directly outputting a Markov policy from the current results might lead to weaker guarantees. I concur with the reviewer, and agree that it would be good to comment on the difference, and remark that the results are not completely comparable/equally strong. I would recommend acceptance conditioned on that these remarks are added in the final version of the paper.
Decision: Accept (poster)