Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism
Authors: Ming Yin
Yaqi Duan
Mengdi Wang
Yu-Xiang Wang
Venue: ICLR 2022 Poster (2022)
Keywords: reinforcement learning theory
markov decision process theory

Abstract: Offline reinforcement learning, which seeks to utilize offline/historical data to optimize sequential decision-making strategies, has gained surging prominence in recent studies. Due to the advantage that appropriate function approximators can help mitigate the sample complexity burden in modern reinforcement learning problems, existing endeavors usually enforce powerful function representation models (e.g. neural networks) to learn the optimal policies. However, a precise understanding of the statistical limits with function representations, remains elusive, even when such a representation is linear.


Towards this goal, we study the statistical limits of offline reinforcement learning with linear model representations. To derive the tight offline learning bound, we design the variance-aware pessimistic value iteration (VAPVI), which adopts the conditional variance information of the value function for time-inhomogeneous episodic linear Markov decision processes (MDPs). VAPVI leverages estimated variances of the value functions to reweight the Bellman residuals in the least-square pessimistic value iteration and provides improved offline learning bounds over the best-known existing results (whereas the Bellman residuals are equally weighted by design). More importantly, our learning bounds are expressed in terms of system quantities, which provide natural instance-dependent characterizations that previous results are short of. We hope our results draw a clearer picture of what offline learning should look like when linear representations are provided.


Published as a conference paper at ICLR 2022
NEAR-OPTIMAL OFFLINE REINFORCEMENT LEARNING WITH LINEAR REPRESENTATION: LEVERAGING VARI- ANCE INFORMATION WITH PESSIMISM
Ming Yin"
Yaqi Duan' i
Mengdi Wang!
Yu-Xiang Wang"
"Department of Computer Science
'Department of Electrical and Computer Engineering
University of California, Santa Barbara
Princeton University
fming linggyinn yin, yuxiangu)@cs. ucsb. edu
mengdiv) @
0pr beeenggollwerinnetoo.... wnnetonneedeee
ABSTRACT
Offline reinforcement learning, which seeks to utilize offline/historiaal data to optimize sequential decision- makinn strategies, has gained surging prominence in recent studies. Due to the advantage that appropriate function approximators can help mitigate the sample complexity burden in modern reinforcement learning problems, existing endeavors usually enforce powerful function representation models (e.g. neural networks) to learn the optimal policies. However, a precise understanding of the statistical limits with function representations, remains elusive, even when such a representation is linear.
Towards this goal, we study the statistical limits of offline reinforcement learning with linear model representations. To derive the tight offline learning bound, we design the variance-aware pessimistic value iteration (VAPVI), which adopts the conditional variance information the value function for time-nnommognncous episodic linear Markov decision processes (MDPs). VAPVI leverages estimated variances of the value functions to reweight the Bellman residuals in the least- square pessimistic value iteration and provides improved offline learning bounds over the best-known existing results (whereas the Bellman residuals are equally weighted by design). More importantly, our learning bounds are expressed in terms characterizations
of system quantities, which provide natural that previous results are short of. We hope our results draw clearer picture of what offfine learning should look like when linear representations are provided.
INTRODUCTION
Offline reinforcement learning (offline RL or batch RL Lange et al. (2012); Levine et al. (2020) is the framework for learning reward-maximen Decision Process or MDP) using the logged data coming from some behavior policy μ.. Function approximations, the other hand, are well-known for generalization in the standard supervised learning. Offline RL with function represenlaion/apprcimaaioon as result, provides generalization across large state-action spaces for the challenging sequential decision-mate makiin problems when no iteration is allowed (as opposed to online learning). This paradigm is crucial to the success of modern RL problems as many deep RL algorithms find their prototypes in the literature of offline RL. For example, Xie and Jiang (2020) provides view that Fitted Q- Iteration (Gordon, 1999; Ernst et al., 2005) can considered as the theoretical prototype of the deep Q-networks algorithm (DQN) Mnih et al. (2015) with neural networks being the function representors. On the empirical side, there are a huge body of deep RL-based algorithms (Mnih et al., 2015; Silver et al., 2017; Fujimoto et al., 2019; Kumar et al., 2019; Wu et al., 2019; Kidambi et al., 2020; Yu et al., 2020; Kumar et al., 2020; Janner et al., 2021; ; Chen et al., 2021a; Kostrikov et al., 2022) that utilize function approximations to achieve respective successes in the offline regime. However, it is also realized that practical function approximation schemes can be quite sample inefficient (e.g. millions of samples are needed for deep Q-network solve certain Atari games Mnih et al. (2015)).
policy in an unknown environment (Markov
'The environment could have other forms as well, e.g. partielly-observed MDP (POMDP) non-markovian decision process (NMDP).

---

Published as a conference paper at ICLR 2022
To understand this phenomenon, there are numerous studies consider how to achieve sample efficiency with function approximation from the theoretical side, as researchers find sample efficient algorithms possible with particular model representations, in either online RL (e.g. Yang and Wang (2019; 2020); Modi et al. (2020); Jin et al. (2020); Ayoub et al. (2020); Jiang et al. (2017) Du et al. (2019); Sun et al. (2019); Zanette et al. (2020); Zhou al. (2021a); Jin et al. (2021a); Du et al. (2021)) or offline RL (e.g. Munos (2003); Chen and Jiang (2019); Xie and Jiang (2020); Jin et al. (2021b); Xie al. (2021a) Min et al. (2021); Duan al. (2021); Nguyen-Targ et al. (2021); Zanette et al. (2021)).
Among them, the linear MDP model (Yang and Wang. 2020; Jin et al., 2020), where the transition is represented as a linear combinations of the given d-dimensional feature, is (arguably) the most studied setting in function approximation and there are plenty of extensions based upon it (e.g. generalized linear model ( (Wang et al., 2021b), reward-fres frree RI. (Wang et al., 2020), gap-dependent analysis (He et al., 2021) or generative adversarial learning (Liu et al., 2021)). Given its prosperity, however, there are still unknowns for understanding function representations in RL., especially in the offline case.
While there are surging researches in showing provable sample efficiency (polynomial sample complexity is possible) under a variety of function approximation schemes, how improve the sample efficiency for a given class of function representations remains understudied. For instance, given a neural network approximation class, an algorithm that learns the optimal policy with complexity O (0) is far worse than the one that can learn in ((H)) sample complexity, despite that both algorithms are considered sample efficient. Therefore, how to achieve the optimal/tight sample complexity when function approximation is provided is a valuable question to consider. On the other hand, it is known that tight sample complexity, due to the limit of the existing statistical analysis tools, can be very tough to establish when function representation has a very complicated form. However, does this mean tight analysis is not hopeful even when the representation is linear?
Second, in the existing analysis of offline RL (with function approximation or simply the tabular MDPs), the learning bounds depend either explicitly on the data-coverage quantities (e.g. uniform concentrability coefficients Chen and Jiang (2019): Xie and Jiang (2020), uniform visitation measure Yin et al. (2021); Yin and Wang (2021a) and single concen- trability Rashidinejad al. (2021); Xie al. (2021b)) or the horizon length H (Jin et al., 2021b; Uehara and Sun, 2021). While those results are valuable as they do not depend on the structure of the particular problem (therefore, remain valid even for pathological MDPs), in practice, the empirical performances of offline reinforcement learning are often far better than those non-adapioe non-adaptive bounds would indicate. Can the learning bounds reflect the nature of individual MDP instances when the MDP model has certain function representation?
In this work, we think about offline RL from the above two aspects. In particular, we consider the fundamental linear model representations and ask the following question of interest:
Can we achieve the statistical limits for offline RL when models have linear representations?
1.1 RELATED WORKS
Offline RL with general function representations. The finite sample analysis of offline RL with function approximation is initially conducted by Fitted Q-Iteration (FQI) type algorithms and can be dated back to (Munos, 2003; Szepesvári and Munos, 2005; Antos et al., 2008a;b). Later, Chen and Jiang (2019); Le al. (2019); Xie and Jiang (2020) follow this line of research and derive the improved learning results. However, owing to the aim for tackling general function approximation, those learning bounds are expressed in terms of the stringent concentrability coefficients (therefore, are less adaptive to individual instances) and are usually only informationnthhoreiiie computational intractability of the optimization procedure over the general function classes. Other works impose weaker assumptions (c.g. partial coverage (Liu et al., 2020; Kidambi et al., 2020; Uehara and Sun, 2021)),, and their finite sample analysis are generally suboptimal in terms of H or the effective horizon (1 -1
due to the
Offline RL with tabular models. For tabular MDPs, tight learning bounds can be achieved under several tata-coverage assumptions. For the class of problems with uniform data- visitation measure dm,, the near-optimal sample complexity bound has the rate O /dm=²) for imm-innhomges MDPs ( (Yin et al., 2021) and O(H²) <d))) for hime-homogeneous MDPs (Yin and Wang, 2021a; Ren
2

---

Published as a conference paper at ICLR 2022
et al., 2021). Under the single concentrability assumption, the tight rate (CH is obtained by Xie et al. (2021b). In particular, the recent study Yin and Wang (2021b) introduces the intrinsic offline learning bound that is not only instance-dependent but also subsumes previous optimal results.
Offline RL with linear model representations. Recently, there is more focus on studying the provable efficient offline RL under the linear model representations. Jin et al. (2021b) first shows offline RL with linear MDP is provably efficient by the pessimistic value iteration. Their analysis deviates from their lower bound by a factor of d H (check their Theorem 4.4 and 4.6). Later, Xie et al. a) considers function approximation under the Bellman-consisten assumptions, and, when realized to linear MDP setting. improves the sample complexity guarantee of Jin al. (2021b) by an order (dd) (Theorem 3.2).² However, their improvement only holds for finite action space (due to the dependence log [A) and by the direct reduction (from Theorem 3.1) their result does not imply a computationally tractable algorithm with the same guarantee. Concurrently, Zanette et al. (2021) considers the Linear Bellman Complete model and designs the actor-critic style algorithm that achieves tight result under the assumption that the value function is bounded by 1. While their algorithm is efficient (which is based on solving a sequence of second-order cone programs), the resulting learning bound requires the action space to be finite due to the mirror descent updates in the Actor procedure (Agarwal et al., 2021). Besides, assuming the value function to be less than 1 simplifies the challenges in dealing with horizon H since when rescaling their result [0, H), there is a H factor blow-up, which makes no horizon improvement comparing to Jin et al. (2021b). As a result, none of the existing algorithms can achieve the statistical limit for the well-structured linear MDP model with the general (infinite or continuous) state-action spaces. On the other hand, Wang al. [a); Zanette (2021) study the statistical hardness of offline RL with linear representations by proving the exponential lower bounds. Recently, Foster et al. (2021) shows realizability and concentrability are not sufficient for offline learning when state space arbitrary large.
Variance-aware studies. Talebi and Maillard (2018) first incorporates the variance structure in online tabular MDPs and Zanette and Brunskill (2019) tightens the result. For linear mixture MDPs, Zhou et al. (2021a) first uses variance structure to achieve near-optimal result and the Weighted OFUL incorporates the variance structure explicitly in the regret bound. Recently, Variance-awarenee is also considered in Zhang et al. (2021) for norizon-free setting and for OPE problem (Min et al., 2021). In particular, We point out that Min et al. (2021) is the first work that uses variance reweighting for policy evaluation in offline RL, which inspires our study for policy optimization problem. The guarantee of Min et al. (2021) strictly improves over Duan et al. (2020) for OPE problem.
1.2 OUR CONTRIBUTION
In this work, we study offline RL for iim-iinhomogeneous episodic linear Markov decision processes. Linear MDPs serve as one critical step towards understanding function approximation in RL since: 1. unlike general function representation, linear MDP representation has the well-structured form by the given feature representors, which makes delicate statistical analysis hopeful: 2. unlike tabular representation, which only works for finite models, linear MDP provides generalization as it adapts to infinite or continuous state-action spaces. Especially, we design the variance-awar pessimistic value iteration (VAPVI, Algorithm 1) which incorporates the conditional variance information of the value function and, by the variance structure, Theorem 3.2 is able to improve over the aforementioned state- of-the-art guarantees. In addition, we further improve the state-action guarantee by designing an even tighter bonus (4). VAPVI-Improved (Theorem 3.3) is near-minimax optimal as indicated by our lower bound (Theorem 3.5). Importantly, the resulting learning bounds from HAPVI/VAPVI-Impiie are able to characterize the adaptive nature of individual instances and yield different convergence rates for different problems. Algorithmically, our algorithm builds upon the nice Min et al. (2021) with pessimism as we use the estimated variances to reweight the Bellman residual learning objective so that the (training) samples with high uncertainty get less attention (Section 3). This is the key to obtaining anstance-adaptive guarantees.
PRELIMINARIES
This comparison is based translating their infinite horizon discounted setting to the finite-horizon case.
3

---

Published as a conference paper at ICLR 2022
2.1
PROBLEM SETTINGS
Episodic time-inhomogeneous linear Markov decision process. A finite-horizon Markov Decision Process (MDP) is denoted as M AS, P. r, H, di) (Sutton and Barto, 2018), where S is the arbitrary state space and A is the arbitrary action space which can be infinite or even continuous. immeinnomogeneous transition kernel Pr. : S A+ A (A represents a probability simplex) maps each state action sh, ah) to probability distribution PA (- a4) and Pa can be different across time. In addition, r S A + is the mean reward function satisfying S r S 1. di is the initial state distribution. H is the horizon. A policy = (#1...., TH) assigns each state 8h E S probability distribution over actions according to the map 8h + (T((-)))) 4h E [M] and induces a random trajectory 81, " dH, TH, # with 81 d1, dA TT( T-|[s)), 8h+1 5h+1 (ss. an). Vh E [H]. In particular, we adopts the linear MDP protocol from Jin et al. (2020; 2021b), meaning that the transition kernel and the mean reward function admit linear structures in the feature map.
Definition 2.1 (Linear MDPs). An episodic MDP (S,A, P,r) is called a linear MDP with a known (unsigned) feature map é : S x A - Rd if there exist d unknown (unsigned) measures Ph= (v)) 1 (,))) over S and an unknown vector 8, IRd such that
Pr (s' s,a) = ()(s, (s')), rh (s, = (0(z,, (,(z,a), 0)) ss' a he
where || (S)]22 S vd and max(Ilo(s, ())2, s 1 for all h E [M]] and Vs,a E S.X.A I| (S)] = Is [1 ds.
V-values and Q-values. For any policy n,, the V-value functions (,)()) E R and Q-value functions QT(-.-) E SSAA are defined as: (s) = E. E/ F1(S). s), (% a) = E. 1Σ t= relsh, On s. Vs, as S,A, [H]. The performance measure is defined as = Ed, [V]] E.,d, EE The Bellman (optimality) equations follow wh E [H]: Q Ta + PA V, = = 10% Qi ra + Ps 1 V/2 = max. Qī,(, a) (where Qn, Vh, Ph. are vectors). By Definition 2.1. the Q-values also admit linear structures, i.e. Q% (o, w(f)) for some wo E IRd (Lemma H.9). Lastly, for a policy t, we denote the induced occupancy measure over the state-action space at any time f E [H] to be: for any E' C S A, di. (ED ;= [((,,, on) Elss ~ d1,a, T(-(s),, Pi-1(-ls;-1- (119-1,,,-11) a4-1): 1
i < h] and E., (f a)l := SSxA {s, a)d (s, a)dsda. Here for notation simplicity we abuse di (-) to denote either probability measure or density function.
Offline learning setting. Offline RL requires the agent learn the policy ा that maximizes v²,
provided with the historical data ((5%, oh rī, +)++)) rolled out from some behavior policy μr. cannot change μ and in particular we do not know the data generating
The offline nature requires distribution of μ.. To sum up, the agent seeks to find a policy Talg such that V² Jut S e for the given batch data 'D and given targeted accuracy
0.
2.2 ASSUMPTIONS
It is known that learning near- near-optimal policy from the offline data D cannot be sample efficient without certain data-coverage assumptions (Wang et al., 2021a; Yin and Wang, 2021b). To begin with, we define the population covariance matrix under the behavior policy μ for all h E (M]:
Σ == Ep,h [Ø(s, a) I
(1)
since Di measure the coverage of state-action space for data D, we make the following assumption. Assumption 2.2 (Feature Coverage). The data distributions i satisfy the minimum eigenvalue condition: vh E [H. K₁.- == Amin ( (5%) > 0 and denote k = ming Kh. Note k is a systen-dependent (non-universal) quantity as it is upper bounded by 1/d (Assumption 2 in Wang et al. (2021a)).
We make this assumption for the following reasons. First of all, our offline learning guarantee (Theorem 3.2) provides simultancously comparison to all the policies, which is stronger than only
competing with the optimal policy (whereas relaxed assumption suffices, e.g. suPrerd ".i
a < 0o
This definition is standard extension over the tabular MDPs by referencing the similar notions from the bandit literature, i.e. from Multi-armed Bondit to Linear Bandit (Lattimore and Szepesvári, 2020).
4

---

Published as a conference paper at ICLR 2022
(Uchara and Sun, 2021)). As consequence, the behavior distribution j must be able explore each feature dimension for the result to be valid. Second, even if Assumption 2.2 does not hold, we can always restrict our algorithmic design to the effective subspan of 2 which causes the alternative notion of k == min for detailed discussions). In this scenario, learning the optimal policy cannot be guaranteed constant suboptimality gap needs to be suffered due to the lack of coverage and this is formed as assumption-free RL in Yin and Wang (2021b). Lastly, previous works analyzing the linear MDPs impose very similar assumptions, e.g. Xie et al. (2021a) Theorem 3.2 where Ep I exists and Min et al. (2021) for the OPE problem.
[Ra { s.l. Ky = smallest positive eigenvalue at time h (see Appendix G.
Next, for any function V.+ E [0, H hh, we define the conditional variance Vvai : SSx A + R+ as V1 as) := max Varp, (Vn+1)ss,a)) a)). Based this definition, we can define the variance-involved population covariance matrices as:A := Bu, (o ((,,)))((),))(()1)_) In particular, when VA= = Vn= we use the notation A% instead.
ALGORITHM
Least square regression is usually considered as one of the "default" tools for handling problems with linear structures (e.g. LinUČB algorithm for linear Bandits) and finds its popularity in RL as well since Peast-Square Value Iteration (LSVI, Jin et al. (2020) is shown to be provably efficient for linear MDPs, due to that Vs+1 (s') is an unbiased estimator of [Pr V a). Concretely, it solves the ridge regression problems each time steps (with
being the regularization parameter):
K >
Wh := argmin Allw|| + weRd
(0(5 ah)) w) - r (ohi(
and has the closed-form solution in = =x Ex (( (rKA + ( with Σ Ek= Φs a (s a + AL. In offline RL, this has also been leveraged in pessimistic value iteration (Jin al., 2021b) and fitted Q-evaluation (Duan et al., 2020). Nevertheless, LSVI could only yield suboptimal guarantees, as illustrated by the following example.
Example 3.1. Instantiate PEVI (Theorem 4.4 in Jin et al. (2021b)) with o(s,a) = Laa (i.e. tabular MDPsf by direct calculation the learning bound has the form O Em.,, dT.' (s, a) (ed), and
Varp (++Vi R Kidf(aa)))
the optimal result (Yin and Wang (2021b) Theorem 4.1) gives O J. (s. (s)a) The former has the horizon dependence 22 and the latter is H3/2 by law of total variance.
Motivation. By comparing the above two expressions, it can be seen that PEVI cannot get rid of the explicit H factor due to missing the variance information (W.r. V*). If we go deeper, one could find that it might not be all that ideal put equal weights all the training samples in the least square objective (2), since, unlike linear regression where the randomness coming from one source distribution, we are regressing over a sequence of distributions in RL (i.e. each Sh, an corresponds to a different distribution P(-|sh, ax) and there are possibly infinite many of them). Therefore, conceptually, the sample piece (sh, 0h, $1++1 that has higher variance distribution P(-|sh, an) tends to be less "reliable" than the one (5), a/ sh+1) with lower variance (hence should not have equal weight in (2)). This suggests reweighting scheme might help improve the learning guarantee and reweighting over the variance of the value function stands as a natural choice.
3.1 VARIANCE- AWARE PESSIMISTIC VALUE ITERATION
Now explain framework that incorporates the variance information. Our design is motivated by previous Zhou al. (2021a) (for online learning) and Min et al. (2021) (for policy evaluation).
By the offline nature, we can use the independent episodic data D' = {3% 0h 1% 87 [T((K] μ)) estimate the conditional variance of any V-values V4+1 via the definition [Varg V)+
kE(A) (from
"The max(1,)) :) applied here for technical reason only. In general, suffices to think oي,مة a Vara Va+1.
Thii provides valid illustration since tabular MDP is special case of linear MDPs.
5

---

Published as a conference paper at ICLR 2022
(Pr(( ((PaVi+alssaa) a)). For the second order moment, by Definition 2.1, it holds [ (s,a) S/ Vi+ (s') dPh. (s' s, o(s,a)) J. Va+t (s') dr (s')
Denote 3n : IS Visti (5') dep (s'), then Ps PA h441 = (d, and can estimator it via:
Kolst, at), 88 Vh+1 (sh+1) ]² 2||lllk = S Σ o6 Vi (sh:11)
8n argmin SEk R=1
and, similarly, the first order moment Pa Vn+1 == (cb 0n) can be estimated via:
K Σ
(K((s at). Vh+11 (sh+1) )² + 211011 2np Σ blsh Vott (sitt)
bn = argmin
BERM
The final estimator is defined as 02 (1+)) = max(1, Vara Vn+1(:-)) with Var1V=+1(:s)) - [(((; (.) 2. In particular, when setting Va-1 Va+1, it recovers T% in Algorithm line 8. Here Σn Σx= (53%, 0,), aT) + Ald-
Variance-weighted LSVI. The idea of LSVI (2) is based on approximate the Bellman updates: Ti (V) a) ra a) + (P, (s,, a). With variance estimator ō₁ at hand, we can modify (2) to solve the weighte LSVI instead (Line 10 of Algorithm 1)
[o(sh ag) w) r ( S
+ (shiah) [rR Vee1 (o%-1) (9(ak,, aN
C. = argmin Allwa1 + wead
where An = -Et= (s do( , /6 a ) Ald. The estimated Bellman update Ta (acts on 1)+1) 11 is defined as: (Th ()+ = ((. -T,,)T Th and the pessimism Th is assigned to update Qn 20 Tn Vh+1 ------h Th. i.e. Bellman update- Pessimism (Line 10-12 in Algorithm 1).
Tighter Pessimistic Design. To improve the learning guarantee, create tighter penalty design that includes A rather than Ex11 and an extra higher order 0 + term:
DA + (va (e(:.) 'A, o( () 2H'
Note such design admits explicit factor in H in the main term (as opposed to Jin al. (2021b)) therefore is the key for achieving adaptive/problemm dewrobblemmdeeedeeett results (as we shall discuss later). The full algorithm VAPVI is stated in Algorithm 1. In particular, we halve the offline data into two independent parts with = (6T 0h ri ) he[Hn] and {33, , 0% 1h 57 ) re(K] purposes (estimating variance and updating Q-values).
(e((A) for different
3.2
MAIN RESULT
We denote quantities M1,M2,Ma, M4 in the notation list A. Then VAPVI provides the following result. The complete proof is provided in Appendix C.
Theorem 3.2. Let K be the number of episodes. K > max Ma, and vd > g, where& & == supvelo.m) PPlo,,),) hE(H]
Then for any < < K, with
(v.0)
probability 1 - 8. for all policy simultaneously, the output â of Algorithm satisfies
"" - & <ō(va. Σ Ex [VoC.)
H
2H
K
where Ap = >K dl (l
+ Ala- In particular, we have with probability 1 8.
11 x
w' < Ō(Vā. Σ E. VOG.NAATT 2H Va
(3)
K
where A₁ = Ek of (
+ Ala and Ô hides universal constants and the Polylog terms.
'The truncation used here is standard treatment for making the estimator be within the valid range.

---

Published as a conference paper at ICLR 2022
Algorithm 1 Variance-Aware Pessimistic Value Iteration (VAPVI)
1: Input: Dataset D = {55, ah, rh) 7.hh1 D'
K.H.
(33, 07 PT) Universal constant C.
2: Initialization: Set (+) +
for H. L....,
4: o Phhasel: Regular Leuat- Value Iteration for conditional variances
5: Set En,, Σ (55 (55 T + AT
6: Set 5p + Ex EE ((3 0%) (5
7:
Set On <- " (s5 0T) (5744)
Set Vara Vn+1](,,
(.()))))))) [o.cu-++1)]] [(((,)), 0n) (()) (o.1- 1
9:
Set (1 -32 + 1 Vare, Vnt1(s-))
10:
Phase2: Woighted squar-square Value Iteration for pessimistic updates
11:
Set Ar + Σr= @ (8% añ) o (8%, ah) 109 ah)) - -.
12:
Set Th - Az Ex= 2 (5% aR)
(1% + PAtz (sh+2))
10 ah))
13:
Set (a) )) + Cvd. (o(s-) .) "A (()))))))
+ 242.aa
(Use 12I, for the improved version)
14:
Set (.(: t -(,--) Wn -)
15:
Set (.() --min/ (Qx(.-), ), h
16:
(: +) <- arg max ())())),m) x) Pa()) + maxa5 (Qn(s)), ma(: 11))
17:
end for
18: Output: [fn])=r
H
Theorem 3.2 provides improvements over the existing best-known results and we now explain However, before that, we first discuss about our theorem condition.
Comparing to Zhou et al. (2021a). In the online regime, Zhou et al. (2021a) is the first result that achieves optimal regret rate with OdH in the linear (mixture) MDPs. However, this result requires the condition d 2 H (their Theorem 6 and Remark 7). In offline RL, VAPVI only requires a milder condition Vd > & comparing to d 2 H (since for any fixed V E H), the standardized quantity
is bounded by constant with high probability, egg. by chebyshev inequality), which makes our result apply to a wider range of linear MDPs.
(T)
(s.a)
Comparing to Jin et al. (2021b). Jin et al. (2021b) first shows pessimistic value iteration (PEVI) is provably efficient for Linear MDPs in offline RL. VAPVI improves PEVI over O(vd) on the feature dimension, and improves the horizon dependence as An > म E, implies A,= < 11 In addition, when instantiate the tabular case, i.e. Φ(s,a) = 1,,a, VAPVI gives En.a di. ()) Varp,. (r+V which enjoys O(VH) improvement over PEVI (recall (a.)(aa))) Example 3.1) and the order ((H3/2) is tight (check Section G for the detailed derivation).
Comparing to Xie et al. (2021a). Their linear MDP guarantee in Theorem 3.2, enjoys the same rate as VAPVI in feature dimension but the horizon dependence is essentially the same as Jin et al. (2021b) (by translating H = O( ((2_,)) )) therefore is not optimal. The general function approximation scheme in Xie et al. (2021a) provides elegant characterizations for on-support error and off-support error, but the algorithmic framework is information-theoretiiee only (and the practical version PSPI will not yield the same learning guarantee). Also, due to the use finite function class and policy class, the reduction to linear MDP only works with finite action space. As a comparison, VAPVI has constraints on any of these.
Comparing to Zanette et al. (2021). Concurrently, Zanette et al. (2021) considers offline RL with the linear Bellman complete model, which is more general than linear MDPs and, with the assumption Qx < 1, their PACLE algorithm provides mear-minimax optimal guarantee in this setting. However, when recovering to the standard setting QT E [0, HJ. their bound will rescale by an H factor, ? which could be suboptimal due the variance-unawwreeess. The reason behind this is: when Q= < lack of variance information encoding will not matter, since in this case Varp(V*) < 1 has constant
Check their Footnote in Page 9.
7

---

Published as a conference paper at ICLR 2022
order (therefore will not affect the optimal rate); when Q E [0, H], Varp(VV) can be as large as H², effectively leveraging the variance information can help improve the sample efficiency, e.g. via law of total variances, just like VAPVI does. On the other hand, their guarantee also requires finite action space, due to the mirror descent style analysis. Nevertheless, we do point out Zanette et al. (2021) has improved state-action measure than VAPVI, as || [o(: ( M S TE (=(])((; -) a] by Jensen's inequality and that norm ||- I- is convex for some positive-definit matrix M.
Adaptive characterization and faster convergence. Comparing to existing works, one major
improvement is that the main term for VAPVI Vd Ex- I Af
admits no characterization. For
explicit dependence on H, which provides a more adaptive/instanc--eppee instance, if we ignore the technical treatment by taking À 0 and o R Varp(Vi 1)) ). then for the partially deterministic systems (where there are t stochastic P/ 's and H -t deterministic Pa 's), the
main term diminishes to va E, [V TT,, "(. with h2 E (h: s.t. Ph. is stochastic) and can be much smaller quantity when < H. Furthermore, for the fully deterministic system, VAPVI automatically provides faster convergence rate O from the higher order term, given that the main term degenerates to O. Those adaptive/instanc--deee et al., 2021a; Zanette et al., 2021), as they always provide the standard statistical rate 0 (also check Remark C.9 for related discussion).
features are not enjoyed by (Xie
3.3 VAPVI-IMPROVED, FURTHER IMPROVEMENT IN STATE-ACTION DIMENSION
Can we further improve the VAPVI? Indeed, by deploying a carefully tuned tighter penalty, we are able to further improve the state-action dependence if the feature is non-negative (ø 2 0). Concretely, we replace the following 1/ in Algorithm instead, and call the algorithm VAPVI-Improved (or VAPVI-I for short). The proof can be found in Appendix D.
Φ (5% oh) (1% PA+1 (0%+1)) (Tr (Ptt a
K
HddR K
(l((, + o(o.a) A
Σ
+0
(4)
0% 07,)
Theorem 3.3. Suppose the feature is non-negative (o 2 0). Let K be the number of episodes. If
K > mmxx,M, Ma, and vd &. Deploying Tí (4) in Algorithm 1. Then for any 0 < < k, with probability 5, for all policy a simultaneously, the outpur tे of Algorithm (VAPVI-I) satisfies
H
H'd/e
" sōlVa. Σ ET lo ) + 5
K
In particular, when choosing ग = x²,, the above guarantee holds true with A, replaced by A,, A { are defined the same as Theorem 3.2. Here A,7 11,
Theorem 3.3 maintains nearly all the features of Theorem 3.2 (except higher order term is slightly worse) and the dominate term evolves from E,, || to [[ [ Clearly, the two bounds differ by the magniude of Jensen's 's inequality. To provide concrete view of how much improvement is made, we check the parameter dependence in the context of tabular MDPs (where we ignore the higher order term for conciseness). In particular, we compare the results under the dingle-policy concentrability.
Assumption 3.4 (Rashidinejad et al. (2021); Xie et al. (2021b)). There exists a optimal policy n", s.t. suph.s.a d% a))")) a) == C* < co, where d= is the marginal state action probability under n.
In tabular RL, o(s, 1.aa and d = S (S, A be the finite state, action cardinality), then
Varr... (r (V+i)
S
Theorem 3.2 + SS SA
di (s, (s)
K . (s,
K
5.a
(5)
Varp, (r Vitn)
HAC*SA
T Theorem& 3.3 -VVAA Σ
Σ
dī. as)
K di (s,
K
8

---

Published as a conference paper at ICLR 2022
Theorem 3.3 enjoys S state improvement over Theorem 3.2 and nearly recovers the minimax rate (Xie al., 2021b). The detailed derivation can be found in Appendix G. Also, to show result is near-optimal, we provide the corresponding lower bound. The proof is in Appendix E. Theorem 3.5 (Minimax lower bound). There exist a pair of universal constants e, > 0 such that
V V=
RACLS K
given dimension d, horizon H and sample size K >> c'd.. one can always find family of linear
( - satisfies (Az)) exists and
MDP instances M such that (where Ai, = ->k=1 Vara Melee
Varn(VV411 (6h att MAA MM)
H Σ
inf sup EM(V" "op0-v"j / Vd. MEM
V E. (A;)) 2c
(6)
h=l
Theorem 3.5 nearly matches the main term in VAPVI-I (Theorem 3.3) and certifies is near-optimal.
PROOF OVERVIEW
Due to the space constraint, we could only provide a brief overview of the key proving ideas of the theorems. We begin with Theorem 3.2. First, by the extended value difference lemmu (Lemma H.7), we can convert bounding the suboptimality gap of v* - v to bounding Σ 2- Ex (sh, an)], given that 1(T% Vh+ Th Th a)l s [s a) for all s, s,a. h. To bound Th Va+1 T Vn+1, by decomposing it reduces to bounding the key quantity
K
((s.a) A
Σ
o (sh. aR) (r% + Vu+1 (sh+1) (Th Vo-i))) (5 a71)
lo oh)
(7)
The term is treated in two steps. First, we bound the gap of 0 Pati -0h
so we can convert 0 to
therefore by the variance-weighttd scheme in (equation 7), can leverage the recent technical development Bernstein inequality for self- self-normalized martingale (Lemma H.3) for acquiring the tight result, in contrast the previous treatment of Hoeffding inequality for self-normalized martingale + Covering." For the second part, one needs to further convert o² Vu41 to o (A to 1 with appropriate
a2
Vn-1" Next, since Var rr + Dh+1 (+h+1) - (Th Ph+1) (0%, a7) 8/, 07
V
concentrations. The proof of Theorem 3.3 is similar but with more complicated computations and relies on using the linear representation of ςi in 1 (4), so that the expectation over π is inside the square root by taking expectation over the linear representation at the beginning. The lower bound proof uses a simple modification of Zanette et al. (2021) which consists of the reduction from learning to testing with Assouad's method, and the use of standard information incqualities (e.g. from total variation to KL divergence). For completeness, we provide the full proof in Appendix E.
5 DISCUSSION AND CONCLUSION
This work studies offline RL with linear MDP representation and contributes Variance Aware Pessimistic Value Iteration (VAPVT) which adopts the conditional variance information of the value function. VAPVI uses the estimated variances to reweight the Bellman residuals in the least-square pessimistic value iteration and provides improved offline learning bounds over the existing best-known results. VAPVI-I further improves over VAPVI in the state-action dimension and is near-minimax optimal. One highlight of the theorems is that our learning bounds expressed in terms of system quantities, which automatically provide natural instance-dependent characterizations that previous results are short of.
On the other hand, while VAPVI/VAPVI- close the existing gap from previous literature (Jin et al., 2021b; Xie et al., 2021a), the optimal guarantee is in the minimax sense. Although our upper bounds possess bestance-dependers instances. In this sense, whether "instance-dependent optimality" can be achieved remains elusive in the current linear MDP setting (such discussion is recently initiated in MAB problems (Xiao et al., 2)). We leave this as future work.
characterizations, the lower bound only holds true for a class of hard
Variance-rewweighingg in (7) is important, since applying Bernstein inequality for self-normalized martingale (Lemma H.3) without rareihhe-r cannot provide any improvement.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors would like to thank Quanquan Gu for explaining Min al. (2021) and introducing couple of related literatures. Ming Yin would like to thank Zhuoran Yang for the helpful suggestions and Dan Qiao for a careful proofreading. Mengdi Wang gratefully acknowledges funding from Office of Naval Research (ONR) 100014--1-1-2288 Air Force Office of Scientific Research (AFOSR) 119550-19-1-02000 and NSF 19-589, CMMI-1653435, Yu-Xiang Wang gratefully acknowledges funding from National Science Foundation (NSF) #20071 17 and #2003257.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Sanae Amani, Christos Thrampoulidis, and Lin F Yang. Safe reinforcement learning with linear function approximation. arXiv preprint arXiv:2106. 06239, 2021.
Andras Antos, Remi Munos, and Csaba Szepesvari. Fitted q-iteration in continuous action-space mdps. In Advances Neural Information Processing Systems, pages 9-16, 2008a.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008b.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pages 463-474. PMLR, 2020.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
Jinglin Chen and Nan Jiang. Information-theerrtiic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051, 2019.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Michael Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. arXiv preprint arXiv:2106.01345, 202
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player markov games with linear function approximation. arXiv preprint arXiv:2102.07404, 2021b.
Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a survey. Internet Mathematics, 3(1):99-227, 2006.
Simon Du Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674. PMLR, 2019.
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. International Conference on Machine Learning, 2021.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference Machine Learning, pages 8334-8342, 2020.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. International Conference on Machine Learning, 2021.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
10

---

Published as a conference paper at ICLR 2022
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10119 2021.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference Machine Learning, pages 2052-2062. PMLR, 2019.
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00444/ 2021.
Geoffrey J Gordon. Approximate solutions to Markov decision processes. Carnegie Mellon University, 1999.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171- 4180. PMLR, 2021.
Michael Janner, Qiyang Li, and Sergey Levine. Reinforcement learning as one hig sequence modeling problem. arXiv preprint arXiv:2106.02039 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-lcarnable. In International Conference on Machine Learning- Voluuee 70, pages (013,, 2017.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00815, 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.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. Advances in Neural Information Processing Systems, 2020.
Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with in-sample q-learming. In International Conference on Learning Representations, 2022.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in neural in information processing systems, 2016
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. Advances in Neural Information Processing Systems, 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learnonneeeeettaannnggng. In Reinforcement learning, pages 45-73. Springer, 2012.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna- lional Conference on Machine Learning, pages 3703-3712, 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv preprint arXiv:2005.01644 2020.
Yao Liu, Adith Swaminathan, Alckh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint XXiv:2007.08202.. 2020.
11

---

Published as a conference paper at ICLR 2022
Zhihan Liu, Yufeng Zhang, Zuyue Fu, Zhuoran Yang. and Zhaoran Wang. Provably efficient genera- tive adversarial imitation learning for online and offline setting with linear function approximation. arXiv preprint arXiv:2108.08770 2021.
Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 5187755)))))552-3333 2015.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
Rémi Munos. 2003.
Error bounds for approximate policy iteration. ICML., volume 3, pages 560-567,
Thanh Nguyen- Tang, Sunil Gupta, Hung Tran-The, and Svetha Venkatesh. On finite-sample analysis of offline reinforcement learning with deep relu networks. arXiv preprint arXiv:2 2021.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale pessimism. arXiv preprint arXiv:2103.12021,
2021.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. Advances neural information processing systems, 2021.
Paul D Sampson and Peter Guttorp. Nonparametric estimation of nonstationary spatial covariance structure. Journal of the American Statistical Association, 178417)108--19 1992.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint 220.:229...18990. 2022.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359, 2017.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages
PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning An introduction. MIT press, 2018.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pages 880-887, 2005.
Mohammad Sadegh Talebi and Odarric-Ambrym Maillard. Variance-aware regret bounds for undis- counted reinforcement learning mdps. In Algorithmic Learning Theory, pages 770-805. PMLR, 2018.
Joel A Tropp.
User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389 434, 2012.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage. arXiv preprint arXiv:2107.06226. 2021.
Ruosong Wang, Simon Du, Lin F Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 2020.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? International Conference on Learning Representations, 2021a.
12

---

Published as a conference paper at ICLR 2022
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism in rein- forcement learning with generalized linear function approximation. In International Conference on Learning Representations, 2021b.
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv: 19t1::1911.13... 2019.
Chenjun Xiao, Yifan Wu, Jincheng Mei, Bo Dai, Tor Lattimore, Lihong Li, Csaba Szepesvari, and Dale Schuurmans. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning, pages 11362-11371. PMLR, 2021.
Tengyang Xie and Nan Jiang. Q approximation schemes for batch reinforcement learning: A theoretical comparison. In Uncertainty in Artificial Intelligence, pages 550-559, 2020.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consisten pessimism for offline reinforcement learning. Advances in neural information processing systems, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 2021b.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR. 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2020.
Ming Yin and Yu- Xiani Wang. Optimal uniform ope and model-based offline reinforcement learning in homm--homgeneous, reward-free and task-agnostic settings. Advances in neural information processing systems, 2021a.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 2021b.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence offline policy evaluation for reinforcement learning. In International Conference Artificial Intelligence and Statistics, pages 1567-1575. PMLR, 2021.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model based offline policy optimization. arXiv preprint 2rXiv:2005.132. 2020.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. International Conference on Machine Learning, 2021.
Andrea Zanette and Emma Brunskill. Tighter problem -dpeedded regret bounds in reinforcement learning without domain knowledge using value function bounds, In International Conference on Machine Learning, pages 7304-7312, PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. International Conference Machine Learning, PMLR, 2020.
pages
Andrea Zanette, Martin J. Wainwright, and Emma Brunskill, Provable benefits of actor-critic methods for offline reinforcement learning, 2021.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Variance- confidence set: Variance- dependent bound for linear bandits and horizon-fire free bound for linear mixture mdp. arXiv preprint arXiv:2101 12745, 2021.
13

---

Published as a conference paper at ICLR 2022
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 2021a.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12793- 12802. PMLR, 2021b.
14

---

Published as a conference paper at ICLR 2022
Appendix
A
NOTATION LIST
En [o(s, a))(s,)) a
Ap
En Vn++
ming Amin (2%)
ming Amin (A%) 2 k/H² for any Vn
t
(x)
max (1, Varp, (V) a)) for any V
(8,0)
max (1, Varp, (V (V,+))
R ())
max Var, (
Σn
Dr 655 (70(5% "h)T + Ala
An
E ( at ( / at) Ala
K
Mi
max max (2A, 128 log (2d/ 6), 128 log (2d/0)/²²)
M2
[loo((A+K)H/AM)) 962 H dog (A /\6)//)/kk) max
max
M3
(512114 log 2 4AH13/K
M4
12 / (oggH H
6
Failure probability
(ntV()))((TV)(ea)) (s.0)
g
supvejo.H1 s'~Ph(ssa), NE(M]
CH.d,K.K
36
H' log
(A+K)2KdH²
12A H!vA
A8
B EXTENDED LITERATURE REVIEW
B. LINEAR MODEL REPRESENTATION AND ITS EXTENSION IN ONLINE RL
There are numerous works in online RL that study linear model representations. Yang and Wang (2019; 2020); Jin et al. (2020) propose Linear MDP, which assumes the transition kernel and the reward are linear in given features. Cai et al. (2020); Ayoub et al. (2020); Modi et al. (2020); Zhou et al. (2021b) propose Linear mixture MDP, which assumes the transition probability a linear combination of some base kernels. Linear Bellman Complete model (Zanette al., 2020) generalizes linear MDP model by allowing linear functions to approximate the Q-function and the function class closed under the Bellman update. The notion of low Bellman rank (Jiang al., 2017) subsumes not only linear MDPs but also models including linear quadratic regulator (L.QR), Reactive POMDP (Krishnamurthy al., 2016) and Block MDP (Du et al., 2019). There are also other models, e.g. factored MDP (Sun et al., 2019), Bellman Eluder dimension (Jin et al., 2021a) and Bilinear class (Du al., 2021). With the linear MDP model itself, there are also fruitful extensions, e.g. gap-dependent analysis with logarithmic regret (He et al., 2021), low-switching cost RL (Gao et al., 2021), safe RL (Amani al., 2021), reward-free free RL (Wang et al., 2020), generalized linear model (GLM) (Wang et al., 2021b), two-player markov game (Chen et al., 2021b) and generative adversarial learning (Liu al., 2021). In particular, Zhou et (2021a) shows UCRL-VTR+ is near-minimax optimal when feature dimension d 2 H.
B.2 EXISTING RESULTS IN OFFLINE RL WITH MODEL REPRESENTATIONS
Offline RL with general function representations. The finite sample analysis of offline RL with function approximation is initially conducted by Fitted Q-Iteration (FQI) type algorithms and can be dated back to (Munos, 2003; Szepesvári and Munos, 2005; Antos et al., 2008a;b). Later, Chen and Jiang (2019); Le al. (2019); Xie and Jiang (2020) follow this line of research and derive the
15

---

Published as a conference paper at ICLR 2022
improved learning results. However, owing to the aim for tackling general function approximation, those learning bounds are expressed in terms of the stringent concentrability coefficients (therefore, due to the
are less adaptive to individual instances) and are usually only information-theorett computational intractability of the optimization procedure over the general function classes. Other works impose weaker assumptions (e.g. partial coverage (Liu et al., 2020; Kidambi et al., 2020; Uehara and Sun, 2021)), and their finite sample analysis are generally suboptimal in terms of H or the effective horizon (1 (1-33 -)-
Offline RL with tabular models. For tabular MDPs, tight learning bounds can be achieved under several data-coverage assumptions. For the class of problems with uniform data-visitation measure dm the near-optimal sample complexity bound has the rate HHH /dme²) for time- -mm-innhoooeeeeus MDPs (Yin et al., 2021) and O /dm+)) for tim-hhomgeeneus MDPs (Yin and Wang. 2021a; Ren et al., 2021). Under the single concentrability assumption, the tight rate O(H /ea)
) is obtained particular, the recent study Yin and Wang (2021b) introduces the intrinsic
by Xie et al. (2021b). offline learning bound that is not only instance-dependent but also subsumes previous optimal results. More recently, Shi et al. (2022) uses model-free approach to achieve minimax rate with a larger c-range.
Offline RL with linear model representations. Recently, there are more focus on studying the provable efficient offline RL under the linear model representations. Jin et al. (2021b) first shows offline RI. with linear MDP is provably efficient by the pessimistic value iteration (PEVI), which is an offline counterpart of LSVI-UCB in Jin et al. (2020). Their analysis deviates from their lower bound by factor of d H (check their Theorem 4.4 and 4.6). Later, Xie et al. (2021a) considers function approximation under the Bellman-consistent assumptions, and, when realized linear MDP setting, improve the sample complexity guarantee of Jin et al. (2021b) by a order (d) (Theorem 3.2). However, their improvement only holds for finite action space (due to the dependence log [-A)) and by the direct reduction (from Theorem 3.1) their result does not imply computationally tractable algorithm. In addition, there is no improvement on the horizon dependence. Concurrently, Zanette et al. (2021) considers the Linear Bellman Complete model (which originates from its online version Zanette et al. (2020)) and designs the actor-critic style algorithm that achieves tight result under the assumption that the value function is bounded by 1. While their algorithm is efficient (which is based on solving a sequence of second-order cone programs), the resulting learning bound requires the action space to be finite due to the mirror descent/natural policy gradient updates in the Actor procedure (Agarwal et al., 2021). Besides, assuming the value function to be less than 1 simplifies the challenges in dealing with horizon H since when rescale their result to [0, H). there is H factor blow-up, which makes no improvement in the horizon dependence comparing to Jin et al. (2021b). On the other hand, Wang et al. (2021a): Zanette (2021) study the statistical hardness of offline RL with linear representations by proofing the exponential lower bounds. As result, none of the existing algorithms can achieve the statistical limit for the well-structured linear MDP model with the general (infinite or continuous) state-action spaces in the offline regime.
C PROOFS IN SECTION 3.2
Instead of proofing the result for 8- - va, in most parts of the proof we deal with 1/* - V/8 which is more general.
C.I SOME PREPARATIONS
Define the Bellman update error (s) (s),)) as, a) and recall (s)
arg max,, Kn (Q, )), nn s)), then by the direct application of Lemma H.8
H
H
Vi (s) - V (s) S
En (SA (Sh, ax) = s]
Σ
Ex Is (8h, an) | 81 ss]
(8)
A=1
A=1
The next lemma shows it is sufficient to bound the pessimistic penalty, which is the key in the proof.
Lemma C.1. Suppose with probability 1 5,6, 6, it holds for all h, s, E [H] x S x A that [(T Vh+1
Ta V1+1)(ss)) & au(s,a), then it implies Vs, a, h S A x H. 0 (a(s,a) S 2 (s,
16

---

Published as a conference paper at ICLR 2022
Furthermore, it holds for any policy simultaneously, with probability 1 5,
H
(T(()) - VF
S
Σ 2.
Ex (T ax) 81 = =s].
h=1
Proof of Lemma C.I. We first show given (Th V - (s, & Tn(s,a), then 0 1 (1, & 2T)(s, Vs, a, E A H
Step1: we first show 0 v Sh a). Vs, a, E S A x [H].
Indeed, if a)) v 0, then by definition (1 a) = 0 and in this case (h(s,a) = (Th (s)))s)))) as) (ss,)) 2 0: if (s) O. then (s, a) (s(s,)) and
(x( = (Th (TA (n( (Thh))))(ss)) -n((s,))))) =(Th ())
+ (n) 2 0.
Step2: next show (= - Vs, e.t.a.h8xxxc [H].
Indeed, we have (n) a) max a),0) 0) and this because: Qu(x, a) (P (1, & (TAV++1((z,)) - H + 1. Therefore, in this case we have:
an) = To
(Th 1) (s, (s) S ((s,) (Tr +Tn(s, 22-
Qx(s,a)
For the last statement, denote 10 (s) s 2l,(s,,),, E e [A]] Note
conditional on B. then by equation 8. (T 1/((s) s Σ 2- (sn an) $1 s) holds for any policy almost surely. Therefore.
P VT, (s) 1/ S
Σ
2 Ex (T |81 =s]
h=1
=P
Vi, (T(() - (8) < Σ
2 E, I 0n)
|11 3
[P((
h=1
+P
VT. (T((s) (i( - Σ
2 E, (Thh,, an)
|8| =
8"
PPT
1=1
>P
VTT (s) -1) < Σ
2 E. ( an)
|81 =
PP3)
21
2
8,
A=1
which finishes the proof.
C.2 BOUNDING -(th
-(th. (s, a)). Suppose w/, is the coefficient By Lemma C. it remains to bound (Ta Vh (Fr corresponding the Ta Vitt (such wa exists by Lemma H.9), ie. Ta V. Φ wh. and recall
17

---

Published as a conference paper at ICLR 2022
(N)4)))() = Ō(s. a)_ Th then:
(ThWatz) (8,a) (Fh
(s,a) = =(s,aa) (wn - (h))
=0(s, a) T wh 0(8,a) (T A
Σ (sh. (rh + Vutaa (sh+1) 10% (5/ ah))
K
0s)
Twh wh a(s,a)TTr
Σ
① (8% ah) (Th (sh (57 ah)
K
+ 0088 (5,a Tx=
Σ
(sh AT) (1h + Va+i (sh+1)
Th Pati)) (0% (7)) 10%
(ii)
The term (i) is dealt by the following lemma.
Lemma C.2. Recall k in Assumption 2.2. Suppose K 2 max (512H*/ /k² log (2)) 4AH2/11))
then with probability for all 8, s,a, E S Ax x [M]
2AHaaa
((s,a) wh -- Ar
Σ o (s%. 07) (Th / ah) S
K
Proof. Recall Tn V V+1 = Tt wn and apply Lemma H.6, we obtain with probability 1 - 8, for all
3. h E S A [H].
((s.a) wn Twn ((),a) An '
Σ (s%, (TA (6% aT) 10 a7))
o)(s,a) Wh - ((s, (ls,a)_a AnT"
Σ Φ (sh, a%) plsh ah) "n/oo (sh, a5)
a)( wh o(s, a) ATj''
[An \1) wh x ((s.a) a) T wm
A
X
<)|lo(s, /| 11mll17-1 s K
((((s,))l(ág)= ||wnllkg))-
V|(Agg-11 2HV6 v|(08)-11
where Ng = En, [0, -2b(s, a))(s, a) {] and the second inequality is by Lemma H.6 (with
0' 6/ō, and |0/0nll < |ol|| < 1 C)' and the third inequality uses Val a <
/ [| A|l aal |al|2 |4 with be either
wh. Moreover, Amin (Ap) 2
x/ aa (s, 2 x/ 2 implies (AR) < H²2 H2//s, therefore for all s, s,a, E [H]].
with probability --6 5
K Σ rm1
AAH'Vdji
((),a)TT wn - (0),,))TT T
(8h, ah) (Th (shs (h) 162 ())
K
18

---

Published as a conference paper at ICLR 2022
77 = (1h + Vn+1 (sh+1) Po+1)) (0h, a7) /0(5),
For term (ii), denote: 2, then by Cauchy inequality it follows
((s,a)TT,
Σ
(8/: oh) (1h Vn+1 (oh+1) (Th Phtt)) (sh: 10 ah
K
S (Vo(s,a) ((( a()
Σ Mr 1
(10)
a)( d(s,a)
C.2.1 ANALYZING THE TERM
Recall (in Theorem 3.2) the estimated π = 2 (8%, (1))) (5) (s), (s%. at) 10 ob)) + and An = Σ 618 9 (15 0 Van, (5: 0%)) + AI. Then we have the following lemma to control the term Vo(s a).
Lemma C.3. Denote the quantities C1 max 128 log(2d/6), 128H log(2d/))/n²) and C2 max ( (Too(((+))H/A)) 962 ddd + K)H//6)/K*)) Suppose the number of episode
K satisfies K > max(C1, C2), then with probability 1 - 5,
(olssa) V a(s s a( a(s, oss,a), Ms,aeSxA
Proof of Lemma C.3, By definition
/ 0(s a) d(s, a) = ( Then denote
1 An. Mh An.
N
K
where AG = ΣK o(5 TT))TT(ss
oss, /03 o (5) + Al. Under the condition of K, by
Lemma C.7, with probability 8
((s (8),))
((
N Ao sup
(s,
Bars (8,a)
(s, a)
(8,a)
(8, a)
22 (8, 11 (11)
sup 8.0
|lo(s, a)ll
sup 5,a
Vi
(s, a)o?
(8,a)
Pn+1
H'd
(A+ + K)H
+ 12A H2vd
< 12
log
kK
2d
KK
Next by Lemma H.5 (with ø to be 0/Op.,, and C' = 1), it holds with probability - 8,
J/ - (uulloss 102 Po (s, a)]
A 11)
4
2d
1/2
+
5
log
K
KK
19

---

Published as a conference paper at ICLR 2022
Therefore by Weyl's spectrum max(2X, 128 log(2d/8)) 1 (og(2d/6)/ k)/""), the above implies
theorem and the condition
K
|| Amax (N/) S Amax ()) a) / /0 (8,
+
A K
4v2
log
2d
1/2
VK
8
A
4
2d
1/2
-Eunll(s,
10 Puu
(s.a)]
+
log
K
VK
A
4v2
2d
1/2
A
4
2d
1/2
s {1b(,,
log
51
+
log
S
2,
VK
K
VK
Aminn (N/)) mimu (u, a) 10 (s.a))
+
A
4
log
2d
1/2
K
VK
8
4
2d
1/2
2 Amin
(Eu.n(((s, a))ss, a) /0 / (8,a)]
log
VK
K
4
2d
K
log
H2
5
2H2
Hence with probability 1 8, || s 2 and ||/ 1/ 1/Amin (A/) 2H2//.. Similarly, one can
show
<
2H2 with high probability.
Now apply Lemma H.4 to N/. and A/, and union bound, we obtain with probability 1 1- 6, for all 8,
(6(ssa))lzz
||
|
|
1|
A
Aull
[1((,,))lla;
2H
2H²
| Mall
+
110(, (10(s,))lax=
48H
H'd
(A +HH
H2Vd
log
(10(s,))lls;
R2
KK
A8
kK
96H
H'd
(A+ K)H
K
1+
log
11o(s, a)l s 221l0(s,
K2
kK
A5
where the third inequality uses equation 11 and the last and the second last inequality use K max I X² (| "dd K))/A6)/N=*, Note the above is equivalent to Vols, ( s 2 0(s a) o(s by multiplying 1/v K on both sides.
C.2.2 ANALYZING THE TERM
| 111111a111
Lemma C.4. Recall x, = aa (())
and Mr = (1% + Vh+1 (sh+1) (Th (5h, (5) 10(5) ah)
H&g log (A+K)2KdHaa)
+ 12A H2va and denote
Let CH.d.a.K = 36
rh (V) - (ThV)
{ : Vejo.H], (s,,), he[H]
sup
ov(s,
20

---

Published as a conference paper at ICLR 2022
If K 2 4C H.K.KK and K 2 O(H5)/k), then with probability 1-8, 8,
K
K
(4K2
[4k2
Σ F+TTT
S $16 Iooo (1+
log
+ 46 log
S Ō max { (V..g),
Xd
8
5
where Ô absorbs the constants and Polylog terms.
Proof of Lemma C.4. By construction, we have || S ||0/ā|| probability 1 - 8/3,
S 1 and by Lemma C.7, with
o Va+i (5, - (7 a)
| - 3m
09 $/ - 0% 3 &CH.aKy I K
ssu 8,0
$ 2
D (s, a) + ( a)
Therefore, when K 2 4C 4C H.d.K.K CH.d,..K V K S $1/25
Bati (5% 0/)2 and hence
r/ + Vh+i (sh+1)
(Tn (7)
r% + Pht1 (sh+2)
(Th Phttt) (0% o7)
Ind1 5
2
Vnts (5%:
CuidinK
P (5h 07)
K-72
r r+ V (s') (Th (s,a) (s,aa
2
sup Ve(o, (s.a)
(s
Next, for a fixed function V, we define the Bellman error as = then
a).
Var r + Vn+1 (5h+1) - (( Vittt))) (sh, an) Fr
Var [n+ [F- =
62(5%, 07))
Var BA Vht1 0)) - BB h+1 (5%, a7) + BA Vi 97) Fr
/ (s% o7))
Var [B 1 (5% an)
[+
8H
Bn 3h -
BBV
7 a7p))
Var [B. h (8% [F + 16H
| - -Vi+i
(2( (7))
Var [B 1 (5)
[r-1] H(
vKk
Var [Bx Vitt (hh an) s/y a7p]
+ Ö V'
Vnk
2 (S a%))
Vary,,, (5% a7) + Ō HDdd
2ar (8% + + + H'V
Ō H'V
VRk
vKk
2
VKR
63 ag)
(32 a7))
2 (5 a
sō(1)
where the first inequality is by Lemma H.1,, the second inequality is by To is non-expansive, the third inequality is by Lemma C88, the next equality is by Markovian property, and the fourth inequality by Lemma C.7 and Lemma 10 The fifth inequality uses definition as) := max [1, Varrs (V) a)} and the last one is by condition K 2 O(H"d/k) and (s, := max(1, (1, Varn, (V*) (s, 2 1. Thus, by Bersstei inequality for self-normalized martingale
21

---

Published as a conference paper at ICLR 2022
(Lemma H.3), with probability 1 1 5,
K
(v dlog
4K2
(4K² I max [vd,e}
s
1+ Ad
log
+ 4glog
8
Â-1
where O absorbs the constants and Polylog terms.
Recall
M4 in List A. Based on the above results, we have the following key lemma:
Lemma C.5. Assume K > max M2, M3, M4). for any 0 < X suppose vd
+x+V( ()s.a) (v,0)
where Ç == su,velo.H, S' ke
Then with probability 1 8, for all
h, E H x xXSxA.
(Th (TA - In (s sō
= (V +
2H
K
where A₁ = Σr= 6(5 a 6(5% 072 Bnts (7) + XI and Ô absorbs the universal constants and Polylog terms.
Proof of Lemma C.5. Combing equation 9, Lemma C.2, equation 10, Lemma C.3 and C.4 and union bound finish the proof.
C.3 PROOF OF THE FIRST PART OF THEOREM 3.2
Theorem C.6 (First part of Theorem 3.2). Let K be the number of episodes. Suppose vd > &. where ++²) (TaV (+++)(((TTVVV)))
< = supvelo, MI, P'=Pa,(s,), NE(N)
and K > max Ma, Ma
(v(s.))
Then for any 0 < Ks with probability 1 6, for all policy simultaneously, the oulput क of Algorithm I satisfies
2H'Vd
0 x z
Vd. ΣE E (o(..)) A (..1)
K
where An = Dt=
+ Ala and Ō absorbs the universal constants and the Polylog
terms.
Proof of Theorem C.6. Combing Lemma C.I and Lemma C.5, we directly have with probability 1 8, for all policy i simultaneously,
((:)))) s) =1)
2H Vd
-
Vd
Σ ES
(p(..))
(12)
h=1
now take the initial distribution di on both sides to get the stated result.
C.4 Two INTERMEDIATE RESULTS
The next two lemmas provide intermediate results in finishing the whole proofs.
'To be rigorous, Lemma H.3 needs be modified since the absolute value bound and the variance bound here the high probability sense. However, this will not affect the validity of the result the weaker version can also he obtained (see Chung and Lu (2006) and related discussion Yin et al. (2021) Remark E.7.) To make the proof more readable, we do not include them here to avoid over-technicality. The definition of M, is in List
22

---

Published as a conference paper at ICLR 2022
C.4.1 BOUNDING THE VARIANCE
Lemma C.7. Recall the definition onl max(1, Varp, Vn+I(:-)) + 1 and vats (:,))2 = max(1, Varp, (++)(;,-)} + 1. Moreover, [Varn Vn+i](..)) = (,B)) (o.H--++122]]]
((o(s)),)) --+)] (where Bn and On are defined in Algorithm 1). Let K 2 max (512(1 log (4ndd) A2/x3, then with probability -,
H
(A+ + K)2KdH²)
H² H3 + 12A
प sup h
of 1
1lo0 S 36
log
kK
A6
KK
Proof. Stepl: we first show for all h, 8, E [H] x S x A, with probability 1 6
H4d
(A+ K))KKH2
H²2 H2Va
(o(s, a), -
- PA(Mat))(s,aa)
$12
log
)
kK
A8
kK
Proof of Stepl. Note
(Ø(s, a). Ba)
(o.00-- (1 ( an) $ - (Pa((at))(s.a))
((s,a) Dx
66 ah) 1 Pa Pa(Pn+z)((s,a))
(63 a)) (n+1(5 -(s,a))) / (V
as 1x
Σ
((, T spp
K
- o (53,,
K 55
(5 ald oh ab) + an) / (Pote) (s' (s')ctn(s))
< (s,a))
(5% ah) (Vh+1(56+112 Pr 2
+* 0(a,)) 55 / (d
4Hd For 2, since K 2 max {512(1/k)2 log
AA/k=, by Lemma H.6 and a union bound over E [H]. with probability 1 1-6 for all h 8, a E [H] x S A.
1/8 (s)+))((s))dun(()
<\(1o(s,a))ss
2 VK (0(5,)))(x))
2
2
1
H2Vd
Hº
<\
S 4X
VK
(E%)-1
K
KK
(13)
For D, we have
K Σ
① < (10(s, ||
65 ab)
(Piti (P (
(14)
Bounding using covering. Note for any fix Vh41, we can define x, = 653 ag) (10112 Σ 1) and
7 = ( - Pr, (V,+4)))) (3) a is H2 subgaauussi,n by Lemma H.2 (where t = K and
1) with probability 1-8 8.
(sh ah) (V Pa(Va+1) 1) (8h Σ
k
S <vi /8HH.. T/
log
(A+K*
A8
let Ni((e) be the minimal e-cover (with respect the supremum norm) of Vn = {Vn Vv(+) ((5.) max,cA min(f(ss TO Ci CivA o(, ));)(()))) C₂2 H - h h+ 13++ That is, for any
23

---

Published as a conference paper at ICLR 2022
V E Vh, there exists value function V E (c) such that supses (V(s) - V'(()) < Now by union bound, we obtain with probability 1 1-6
d
(A+
sup Vo. 1N (1(e)
Σ (sh ah) (Va+1(5h+1)2 Pa (Va+1)) Pa
8114
2
log
Ad
|N
which implics
K
Σ
(5 anj
(V++1(5h+1)2= -
d log
(X+ Winr(ell
8/
+ 4H² VeK3/>
2
choosing = dv//Ks applying Lemma B.3 of Jin et al. (2021b)" to the covering number N (E) w.r.t. V/+1, we can further bound above by
d3
A + K 2dHK
(A K
S
8H4
log
+ A
6 H+ d3 delog
2dHK
A8
A8
Apply a union bound for h E [H], we have with probability for all h E [H].
(A+ K)2KdH²
Σ o(3% ah)) (Vh+1 PP 15)
S 6
H log
26
(15)
and similar to 2 with probability for all h, [H] x X A.
2 (2x))1111 1/2
|| a) a)l S
(16)
VK
VKK
Combing equation 13, equation 14, equation 15 and equation 16 we obtain with probability 1 - 5 for all h, [M] x S A,
H'd
(A+ K)2KdH
H Vd KK
(ō(s. a), Bo) (( s 12
log
+4X
kK
A8
Step2: we show for all h, s, [H] A, with probability 1 8
H2B kK
(A Ky2K
HVd
(0(s, 01) Pa (M.( $ 12
log
+ 44
A6
k.K
(17)
The proof of Step2 follows nearly the identical way as Stepl except 1/ is replaced by DA
Step3: We prove sup, | - of 11x0 S /
H4ds kk
log (A+K)2Kaнн²² + 12X Ha Kk
Proof of Step3. By equation 17.
[(((=:)) 0n) -- 12- [P (s,
()(s,)) On) Ow)o, + PA (v ())
((((, (lls,,a,,nlo..c 0n) PP (8,
H4d3
(A+
K2KdHH²
H2 Hd Vd.
<2H (0(s..), (V | $ 24
log
8A
kK
A6
KK
Note the result in Jin al. (2021b) applies even though we have constant Cz.
24

---

Published as a conference paper at ICLR 2022
Combining this with Step1 receive wh, s,a E [H] 8 x A, with probability 1 -
H
(A++))2KdH)
H2
Vara Vh+ (s, - pa (s, - /
log
+ 12A
kk
AØ
kK
Finally, by the non expansivveness of operator max(1, 1111)) }, we have the stated result.
C.4.2 CRUDE BOUND ON sup, IV Valloc.
Lemma C.8. Define (s)
mmxx (1 Varp, Va- (s,a)))) +1, if K
z
Ma, and K C. H², then with probability at least
Havd VRK
sup
V/
PA
Sō
Proof. Stepl:
We show with probability at least sup, |
IVVa VKK
Indeed, combing Lemma C.1 and Lemma C.5, similar to the proof of Theorem C.6, we directly have with probability for all policy π simultancously, and for all E S, [H]
"
21
(b) - (8)
vi 5ō Vd.
Σ
Ex
(o(s)))Tp
(.. (o(
5)) +
(18)
K
t=h
Next, since K max { 5512(1/k) log (HHd) 442/x]. by Lemma H.6 and a union bound over [H], with probability 1-6
2
2H
sup | 1))
sup |0((,
Wh E [
VK
VRK
Lastly, taking π = x* equation 18 to obtain
H Σ
=x=]] 11)
2H
0 VR (8) <ō
Vd.
Exi
1/2
8h =
K
t=h
(19)
H /dvd
Vd
VRK
This implies by using the condition K C. H we finish the proof Stepl.
Step2: We show with probability 1 1 5, sup,
1h
v < Ō H²Va VRK
Indeed, applying Extended Value Difference Lemma H.7 for nt म. then with probability 1 1-6 5, for all s, h
H Σ
(x))s) - vi((s)
Ex T=h
[Q an) (Ta (sh, an) sn =
(Th Vn Th (
4H'Vd
H22d VnK
<ō (HVd v ((6..))AA
<ō
K
25

---

Published as a conference paper at ICLR 2022
where the second inequality uses Lemma C,5 and the last inequality follows the same procedure as Step1.
Step3:
Combine Step1 and Step2, by triangular inequality and union bound we finish the proof of the lemma.
Remark C.9. Note as an intermediate calculation, equation 19 ensures a learning bound with order Ō Hd VaK ). Here, the convergence rate is the standard statistical rale V/ and the H² dependence is loose. However, the feature dependence Vdjk is roughly tight, since, in the well-explored case (Assumption 2 of Wang et al. (2021a)), K k= = and the /d/K v recovers the optimal feature dependence d.H V in the online setting (Zhou et al., 2021a). If < 1/d, then doing offline learning requires sample size proportional d//s, which reveals offline RL is harder when the exploration of behavior policy is insufficient. When = 0, learning the optimal policy accurately cannot be guaranteed even the sample/episode size K 0C.
C.5 PROOF OF THE SECOND PART OF THEOREM 3.2
Lemma C.10. Recall on V mmx {1. Varpa Vn+11 } and o /mmx {1, Varr, Vi+13 1.
Let K 2 max (512(1/k)) log 4l/d) 42/11) and K 2 ability - 6,
Ma), then with prob-
@ - 21x S Hava
VRR
Proof. By definition and the non-expansiveness of max } 1, we have
Varl Var 11
5
< 1h
2
- Vi.11
+ +1 - (PA Vi+ti
h+1
2
1+1
Vi+
+
(PA + PA PA.Vii Ph+1
Ps V 1)
Ha Vd
<2H V
Vit+a
+ 2H
P PA
Sō
VRK
with probability 1- 8 for all h [M]], where the last inequality comes from Lemma C.8. Combining this with Lemma C.7, we have the stated result.
Lemma C.11. Denote the quantities C₁ max 128 log(22/)), 128/1 log(2d/6)/n²) and C2 = = ( (= 962 Hodd + K)H/A6)/x* Suppose the number of episode K satisfies K > max{Cr, C2), then with probability 1 - 5.
Vo(s, a) ((s S -
()s,)), Vs,aESxA,
Proof of Lemma C.II. By definition / a)s ((s, = ||(ss, a) A) Then denote
1 N = FERKA A/ A
N, An.
A
To he absolutely rigorous, we canmot directly apply Lemma C.5 here since the crude bound has already been used in Lemma C.4. However, this can he resolved completely by first deriving sup, V - V. so> that has 1/VK rate without using Lemma C.5 (which we call Lemma C.8"), ), and we can use Lemma C.8 to show similar result Lemma C.5* Finally, we use Lemma C.5' here to finish the proof of this Lemma C.8. However, avoid explicitly doing this prevent over-technicality
cruder bound for
26

---

Published as a conference paper at ICLR 2022
where A₁. Σr= ((5) af)) ((8,, 07
0%) + AI.
Under the condition of K, by
Lemma C.10, with probability 1 -
AA
- sup l/l
((8 ((s (s,a))
((,a))((,a))
Pati (8,
3,a
(s,
Bi ()) os, V Va+1
oh 0 (8,0)
o (s,a) (20)
sup s,a
||((s,))11 I sup 8,0
Vas
1
())
1
Vd
VKK
Next by Lemma H.5 (with @ to be //ovi, and C 1), holds with probability 5,
A
(Enalo(s, a) /o Ki (s, la)
4v2 VK
log
2d
1/2
Therefore by Weyl's spectrum theorem and the max (22, 128 log (2d())))) 128H log(2d/8)) /w2)) the above implies
condition
K
|M || mma((A))) & Amax (Eulld(s.a)) a) /ot; (5.
4v2
2d
1/2
+
log
K
VK
4/2
2d
1/2
$ B
(3,
+
log
K
VK
4v
2d 1/2
X
4
2d
1/2
$ =110(s
log
S1+
log
22
K
K
VK
8
X
4V2
2d
1/2
Amin (Ah) Ama (Eunlo(s,a)(ss.... a) /oi (s, (s.
+
log
K
VK
8
2 Amin
Caan a) /o
(8, (s,
4
log
2d
1/2
K
K
4
2d
1/2
k
log
H
K
8
2H²
Hence with probability 1 8, A
- 2 and
| -1| -1
(Amii(A)) S 2H²/K. Similarly,
| < 2/12/1 with high probability.
Now apply Lemma H.4 to Ag and M₁, and a union bound, obtain with probability for all
| (0((, 5 1 V A
11 |4
||,, I1
||
-xll|
I))(s,))laa?-
2 .
2H
+
-|AA
-Alll
a1)(s,
4 R2
a VRK
[1((,,,))) S 22116(,,0))a,;--
where the third inequality uses equation 20 and the last inequality uses K > max ( (Rog[((A KJH/A8J 1/2 log(a K)H/)))))))))) /n The claimed result follows straightfor- wardly by multiplying 1/vK K on both sides of the above.
X²
27

---

Published as a conference paper at ICLR 2022
Proof of Theorem 3.2. The first part of the theorem has been shown in Theorem C.6. For the second part. apply Theorem C.6 with π = H², then with probability 1-6, 5,
Vd
H
Em.
(( )
+
2H+Vd
K
Am1
Now apply Lemma C.11 and a union bound, with probability 1 - 6,
05 v² 0x < Vd.
Σ
Em
[ - "o(..) " /)(] +
2H
K
h=1
D PROOF OF THEOREM 3.3
First of all, we show the following lemma.
Lemma D.1. Suppose K >> mmx 1a,x Mas Plug
( ah) (1% + Vh+1 (sh+1) -Th (htt)t)) (0h, a7))
Had/K
as - o(
A
+Õ
(5 a7))
K
in Algorithu I and let Th be the Bellman operator and Tr, be the approximated Bellman operator. Then we have with probability - 5: (Tr. Tn. P S oT),,)) E
Proof of Lemma D.I. Suppose wh the coefficient corresponding to the Vn+z (such wh exists by Lemma H.9), i.e. Tn Vn+1 = =T Wh. and recall (Tr ()))))(sss a) = ols, a) wp. then:
Th Pn+1) (8, (Th (nt1) (s,a) = $(5,a) a) (wn
=0(8, a) wh - a) A
Σ ò (sh,a7) (r% + Vata (sh+ 10 (5% a7))
o() Twm wh a(s,a) AA
Σ 2 (8% ah) (ThVnts) (5) /3 (h)
(1)
K
+ o(s, ((s,a)TA,
Σ
① (5% ah)) (rh + Vn+a (sh+z)
( Poott) (5h at)) 16% a7))
(1)
K
+ ((s,a) ((s,,))A,7'
Σ
((ta (sho ah) (Th (h- (oho (h)) 10% a
(iii)
(21)
For term (i), by Lemma C.2 it is bounded by 2AH3Var with probability - 5/2. 13 For term (ii), it is bounded by
s (8ho (5h. (1% + Voui (sh+ (Th Pitt (5% (8%)
a(s,a)
(7 a7)
Note Here Lemma C.2 still applics even the T, changes since it works for all 1/ E [0, H] so that [walla ll 2H and the truncation (Line in Algorithm 1) guarantees this.
28

---

Published as a conference paper at ICLR 2022
For term (iii), by Cauchy inequality
(B,
(th ((TiPrnn)) (8%) (Th Phai (6% af) 10% an)
Σ ④ (sh ah) ( (Th (6h, (TA (5h (5) /67 ah) 5
(l0(s,,)llx,
K
2H
Σ
② ah)
(ThhPhtt) (6) uh) - (ThPhtt)) (oh+))))0..1)) (0h.0h)) /0/ añ)
VRK
211
Ō V vd= 49/ K
VEK
VK
where the first inequality is by Lemma H.6 (with d' = 6/ō and | || S ||भ|| < 1 := C) and the third inequality uses va a.a S V|lall2 |All2 ||a|| |all2 / /I|AIl2 with a to be either e or wh. Moreover, Amin (Ar) 2 K/ aa (s a)² 2 k/H² implies (AΣ))
H² /k.
The second inequality is true by denoting 2, = (55 / a7) and
T/+ = ( (hh (5%, a..) V (5% ah)) (6 af
and use Lemma H.10 10 as the condition for applying Lemma H.2. By collecting those three terms together we have the result.
D.1 PROOF OF THEOREM 3.3
Proof. Use Lemma 1.1 as the condition for Lemma C.I and average over initial distribution di, we obtain with probability 1 6,
0"
@ (5%% (rh + Vn+1 (5%+1)
(T (otit)) (0% am))
+ Ō H.djK
ET, (s(sa))] Σ h=1
(8% a7)
K
(22)
(rk+Va+ ( Ta 1) then
Denote A = Ex=
(1(05.0%)
K Φ (sh1 ap)
(1% Vn+1 (sh+1) - (Th (Ttt))))) (5% aR)
Er, [6(s,a)]'
t (8%: ...)
& (8% a7))
(Th (8%, 07) - In Vnt1 (6)
<ENr [0] -0] -AAn'An An
Ban [0]
An
(5 07,)
For the second term, it can be bounded similar to term (iii) in Lemma D.I and for the first term we have the following:
ETA [0]] T
Nr An = Ema, [6] AA An Ar A s ||E,,, lollx, || An Anl
< [0ll,, ||Anllls; S <Õ(va) E.. loll,, I
where the first inequality uses Cauchy's 's inequality, the second inequality uses A, is coordinate-wise positive (since we assume here Φ 2 0), the third inequality is identical to the analysis in Section C.2.2 and the fourth inequality is identical to the analysis in Section C with o replaced by E[o). Plug this back to equation 22 we finish the proof for the first part. For the second part, converting A, to A is identical to Section C.5. This finishes the proof.
29

---

Published as a conference paper at ICLR 2022
E PROOF OF MINIMAX LOWER BOUND THEOREM 3.5
The proof follows the lower bound proof Zanette et al. (2021). For completeness, we provide all the details in below.
E.1 CONSTRUCTION
Similar to the proof of [Zanette et al. (2021), Theorem 2}, we construct family of MDPs, each parameterized by a Boolean vector (u1..... UH) with each up {-1,+11d-2 for h E [H]. The MDPs share the same transition kernel and are only different in the reward observations.
State space: At each time step h, there are two states S = (+1,-1}.
Action space: The action space A = [-1,0,+1]d=?
Feature map: The feature map Ø S A IR given by
R
v2d
((+1,a) =
E RR
61-1,a)
E Rdd.
v2
The construction ensures the condition [lo(s, a)
12 S for any (s, a) E x A.
Transition kernel: The transition probability Ps(s' a) is independent of action a. In other words, the Markov decision process reduces homogeneous Markov chain with transition matrix
P
R
By letting
0
Mh (+1) (-(1-)
E Rdd
we have Pa a) (b(s, a), en (s')) to be valid probability transition. Reward observations: For any MDP Mu, at each times step h, the reward follows Gaussian distribution with
Ry, (s, a) ~ N ( s
8 (a, un).
/6
V2d"
where E [0. /3d_ determines to what extent the MDP models are different from each
other. The reward function satisfies Fu, (s, (ø(s, a), Ou,n) with
8un
0u,
V3
E Rd
Offline data collection Scheme: The dataset = ((8T, 0h rh 87 87 Tejk] consist of i.i.d.
trajectories. All the trajectories initiate from uniform distribution. We take behavior policy n(( 8) that independent of state Let {er, ......, ed-2) be the canonical bases of R 2 and 0a-2 E IRd-2 be the zero vector. The behavior policy μ is set as
for any j E [d ((e 8) =
and
10 =
E.2 OVERVIEW OF PROOF
The proof of the theorem is based on Assouad's method, where first reduce the problem to binary hypothesis tests (Lemmas E. and E.2) and then connect the testing error to the uncertainty quantity in the upper bound (Lemma E.3).
30

---

Published as a conference paper at ICLR 2022
Lemma E.1 (Reduction testing). There exists universal constant c1 such thata
inf max Eus [V: v 2 c1 H u, (W WEll
min inf [Pu + u) + Par (eb #u)], (23)
where से denotes the oulput of any algorithm that maps from observations to an estimated policy, vp any test function for parameter u and DH is the hamming distance.
Lemma E.2. There exists universal constant c2 such that when taking 8 == VR have
1
min u, (e
inf [T u) P. (w + u')]
(24)
When K 2 d,, == and ensures that 8 < 1/ v/d. Combining Lemmas E.1 and E.2 yields lower bound
VK
dvdH
inf max E. wEll
V
2
(25)
VK
where с > 0 is universal constant. We then use the following Lemma E.3 to connect the above lower bound to the uncertainty term Vd. Σ v E instances class M.
(1 for the chosen linear MDP (
Lemma F.3. There exists universal constant cg > such that for all M e M,
H
d H
Σ
B (A)
S c3
(26)
VK
Plugging inequality equation E.3 into the bound equation 25, obtain the minimax lower bound equa- tion 6 in the statement of theorem.
E.3 REDUCTION TO TESTING VIA ASSOUAD'S METHOD
Proof of Lemma E.I. For any index vector (u), un) E (-1 +1, ( x the optimal policy for MDP instance Ma is simply
(+)
for h E [H]
Similar to the proof of Lemma 9 in Zanette et al. (2021), show that the value suboptimality of policy π on MDP M,, given by
H
V
V
un.
Ex [an]]]]
2d
Define ut (wF 2. with up, sign (En [an)) then the f--orm is lower bounded as
In F. (ax ||| 2 (u]; un).
where ( denotes the Hamming distance. It follows that
8 Du (uT;
V* V 2
(27)
V2d
We then apply Assouad's method (Lemma 2.12 in Sampson and Guttorp (1992)) and obtain that
inf max E,, DD (ū;; (ū; (d 2)H1
min N.w Eu (M(a))
inf [IP ( *
P.r (bb a²)]. (28)
2
where 2 is any test functions mapping from observations to {u, u/). Combining inequalities equa- tion 27 and equation 28, finish the proof.
31

---

Published as a conference paper at ICLR 2022
E.4 LOWER BOUND ON THE TESTING ERROR
Proof of Lemma E.2. The proof of Lemma E.2 is similar to that of Lemma 10 in Zanette et al. (2021).
We first apply Theorem 2.12 in Sampson and Guttorp (1992) to lower bound the testing error using Kullback-Leibler divergence and obtain
min inf [P + u) + Da V
PP + u') 2 [
1-
DKL (2.((2111.))
1/2
max u, w. CUI (1
(29)
only remains to estimate (2.
The probability density 2, takes the form
K
H II
Qx = II (1ft)
m(ah (1)) [R at)] (r%) Ph(sh+1 sh)
1=1
A=1
where E
11 is the initial distribution. It follows that 2 2]
Dxz(Qul(w)) E,, log Qw/Qw:))
H
K.
Eu log (1 Runh ( (sh, a (rk) (ree))/(RReeee (R (s)))))))()))) (x))
h=1
2
K
DKL (N( (22 (e%, un). W (eg, uh).
= d
we take a then inequality equation 29 ensures inequality equation 24, as claimed in the <K* statement of the lemma.
E.5 CONNECTION TO THE UNCERTAINTY TERM
Proof of Lemma E.3. We first calculate the explicit form of the inverse of variance-rescaled covari- ance matrix TPP, For each time step E [H]. the value function Vith+ takes the form
V Vo,++1 Tu,b1 + (1771 Vū,+22).
Since (Po+1 V*+ (+1) (PM+1 Vi (W,+22 and wa..i1(+1111 -u.tti--1,)) = 2/V6, we have
Var (V (+1,+)) Varg, (Bm
Similarly,
1 Varp, (Va,)+1((11,d) Varp, (V
By routine calculation, find that the population-level rescaled covariance matrix takes the form
3K
L
dvd (d-2)xx
P.P R
E Rddxd
8/a 1x
I
for any h E [H]. Applying Gaussian elimination A we have
L 1 +
d 1(d- 2)x2
2
2
(AA-)-1= 3K
dva 1 12x(2-2)
d-1
2(d 2)
d -
32

---

Published as a conference paper at ICLR 2022
For each time step h [H], we have (by Jensen's inequality)
Ex (A,) [6] - E1l0(+1, un) (()0 + Recall that by our construction,
- un leagog
22d
(++1 =
E Rd
6(-1,up)
E Rdd.
V
V2
follows that
| (1+1,,m)li www (A:P))1 = | w
2
{
d
d --1 2(d - 2)
U1
T
(1d-2
-ー2 (d= Jun
2(d 2) 1 d-2 th
3K
4
2
d²
d
11
(1 1 22 + 4
3K
4(d - 2)
d2
d(d 1)2
1
2
{
d2
d- }
3K
4
+
4(d 2 2)
+
4
=
3K
2
+
2(d - 2) f
2 &d2/E
Therefore.
V EE (o] (A S d/vK.
Taking the summation over h E [f]) we obtain the bound equation 26 as claimed in the lemma statement.
F A NUMERICAL SIMULATION
F.I A LINEAR MDP CONSTRUCTION
We consider a synthetic linear MDP example that is similar to Min et al. (2021) but with some
modifications for the offline learning task. The MDP instance we consists of [S] 2 states and |A| = 100 actions, and feature dimension d = 100. We set S = (0, and A = {0, 1,....999 99) respectively. For each action E {0, (0,,,,.,,999 tor a E R& using its binary representation (i.e. each coordinate is either 0 or 1). we inter- changebly use a and and its vector representation for the ease of explanation. We first define
we use binary encoding to obtain a vec-
if ifs 0} 1 0} then the non-stationary linear MDP is specified by the
5(8, a) otherwise
following configuration
Feature mapping:
((s, = (00))(aa____ 1-(,a),,1sss))) - E R
8(s,a)) T
The true measure P/
vn (s) (0..... . (1 - 3 az, on),
where Taihnein Iee is a sequence of integers taking values 0 or 1 and + is the standard XOR operator. We define
0₂ = (O. 0, with the choice of r = 0.9. The transition follows Pa(s' a) = (d(s, a), un(s') and the mean reward function r4 (s, a) (d(s. a), 0x).
1 - -r) E R
Behavior policy: always choose action 0 with probability p, and other actions uniformly
with probability (1 - -p/999 The initial distribution chooses s = 0 and s = 1 with equal probability 1/2. We 0.6.
33

---

Published as a conference paper at ICLR 2022
Scoopimalty 000
620
2083
100
(a) Suboptimality vs. Episode K (b) Suboptimality vs. Episode K (c) Suboptimality vs. Episode K (Horizon H = 30)
(Horizon H = 20)
(Horizon H = 50)
Figure 1: Comparison between PEVI and VAPVI in the non non-stationary linear MDP instance described above. In each figure, y-axis denotes suboptimality gap o* v² x-axis denotes number of episodes K. The problem horizons are fixed to be = 20, 30, 50. The solid line denotes the average suboptimality gap over 50 trials and the error bar area is the corresponding standard deviation. The range of K is from to 1000.
F.2 EMPIRICAL COMPARISON BETWEEN PEVI AND VAPVI ON THE CONSTRUCTED LINEAR MDP
We compare Pessimistic Value Iteration (PEVI) in Jin et al. (2021b) and our VAPVI Algorithm in Figure 1, with horizon to be H 20, 30, 50. In addition, we add the non- non-pessimistic version for both algorithms, i.e. least-square value iteration (LSVI) and variance-aware value itcration (VAVI). The true optimal value v* is computed via value iteration using the underlying transition kernels. For the empirical validation of VAPVI, we do not split the data and, in particular, in all the methods we choose À= 0.01 (instead of À used in theory (Jin al., 2021b) which causes over-regularization in the simulation).
We can observe VAPVI outperforms PEVI and the gap becomes larger when horizon H increases. One main reason for this to happen is due to the bonus used in PEVI (Jin et al., 2021b)
o aH (oG.)) (x)))))))))))) 2/2
is overly pessimistic comparing to our
o [va (o(,-) AZ A 1/2
when H becomes larger and this could potentially make the learning less accurate. In addition, both non-pessimistic algorithms exhibit similar accuracy, and this is partially owing to our truncation scheme (. -2 + max(1, Varrs, (, :}} so 0x(,, (2 will just be 1 when the estimated variance small. Lastly, variance-aware pessimism eventually outperforms non-pessimism algorithms when sample size is large and this might come from that the pessimistic bonus is estimated more accurately when more samples are collected.
G SOME MISSING DERI VATIONS AND DISCUSSIONS
G.1 REGARDING COVERAGE ASSUMPTION
Now we discuss the feature coverage assumption. Indeed, even if Assumption 2.2 is not satisfied, can still learn in the effective subspan of Σ) E,,, (0(s, (s, a) "] Concretely, since Σg is symmetric, by orthogonal decomposition we have Σリ A, where Zn, (can be estimated using the samples for practical purpose) consists of orthogonal basis and A consists of eigenvalues of 2 in the diagonal. Suppose we do not have a full coverage, i.e.
A diag[A1, A2, Adi 0, ..., 0] with d' << d, then we can create transformed features 5f (s, a) = Z,, (n(s,, a), and then
Eyth h 10 (s, (),, ] = A = diag[A1, A2, Agr O.., 0].
Then we can do learning w.r.t. the truncated features &f haw 's instead of the original Φ. reduces to the weaker notion of minge [H) : s.l. Ky smallest positive eigenvalue at time h).
34

---

Published as a conference paper at ICLR 2022
G.2 DERIVATION OF EQUATION 5
When reducing Theorem 3.2.3.3 to the tabular case, set a)s = 1,,,, a.a.d= SA, 0. and recall by Assumption 3.4 (let's assume x² is a deterministic policy as it always exists in tabular MDP) (s, a), then for Theorem 3.2
C* su d% (s, a) (6,
H Vd. E. [VOG.TAA (0..) Vd. Σ dh a 1I 'I
h=1 K
H VSA (8,
Varr., (Vita)
dia
Bh...
Jml a,
Hf
Vare (Vit1) nh,sa
K Σ
VSA
(8,0))
1sh 8.0]
h=l 4,4
H
Varp, (Vi+1)
H
E SA (3,0)y
SASAA K (K,(),,))
dh (s, Varp, (Vi+1)
h=1 6,0
h=1
5.0
= /SAC*/R /K- ΣΣ
1/ (8) (Vi+1)
S /SAC
5.
dī. (8, (s. (Vit1)
S AS
H
d (S) (Vina)
= VS*AC*/K
H Σ
B [arp (arr V AC*/K
where the first incquality is by Chernoff bound and the last one is by Lemma 3.4. of Yin and Wang (2020) (Law of total variances). The rest of them are from Cauchy's inequality. Similarly, for Theorem 3.3, we also have
H
H
Va.
Em
[0] AA [ol
[o] vd. Σ h=1
v Veo(dt" - [ee
H
Varp, (Vi+1)
d.
Veeld= Jdiag
Vec(du>>
nh...
Varp.. (Viet) nhha.a
SSA
Σ d (s,
h=1
2,a
Varr,, (Vit))
E SA
d (s,
K (.
5,0
H1
SAC*
di (s, (s,a) Vitta
h=1
4,a
H
VSAC-/K
di (s, n (s)) (Vitz)
A=1
H
SACCAK
H
Σ h=1
Rag [Varp (Varp,,, (WAL))s S..0ls/HHSS HSSAAC//K
35

---

Published as a conference paper at ICLR 2022
H AUXILIARY LEMMAS
Lemma H.1 (Matrix McDiarmid inequality Matrix Chernoff bound (Tropp. 2012)). Let 2k, k = 1...., K be independent random vectors in R and let H be mapping that maps K vectors to x d symmetric matrix. Assume there exists a sequence of fixed symmetric matrices (AkkkE]K) such that for 2k: 2 ranges over all possible values for each &o E [K]. it holds
(#1 2k.. ,.,,))))))).......))))))...... (Z1, , = Az.
Define 0² = 1E Agll- Then for any t > 0,
+2
{I (21..... =k) (H 2k) 2 f S d exp
802
Lemma H.2 (Hoeffding inequality for self-normalized martingales (Abbasi- Yadakri et al., 201 2011)). 1)). Let {m be a real-valued stochastic process. Let {Fr] be a filtration, such that nh is Fi- measurable. Assume Th also satisfies ttt given Fi-1 is zero-mean and R-subgaussian, i.c.
E IR, E [ [F-1]] S R2212
Let {3a) be an Rd -vauued stochastic process where Ią is Ft-1 measurable and ||zlll & Let A = Ala + E.=1 T. Then for any 5 > O, with probability 1 5, for all t > 0,
d (X+tL) tL
Σ
SR
log
2
A0
Lemma H.3 (Bernstein inequality for self-normalized martingales (Zhou et al., 2021a)). Let {1e J be real-valued stochastic process. Let {Fr) be filtration, such that To is Femmasurrabl. Assume Ty also satisfies
Ind S [m Fi-1l 0, E [ Fi-1] 0
Let {x:] be an Rd -valued stochastic process where xe is F measurable and || S Let
A+ = Aaa + E.= T, Then for any > O, with probability 8, for all t > 0,
< 80 dlog (1+
f.2
412
( [4t2
X
log
+ 4R log
Ad
AT
Lemma H.4 (Converting the variance under the matrix norm). Let A and A2 Raxd are two positive semi-defiiite matrices. Then:
|| || < A
|| + || || ||A_
I| ||A, Azll
and
| <
1 v 11I155 ||
|
||T 1|A1 A2ll
for all á E Rdd.
Proof. For the first part, note
|| < ||^ + --- |157|| "1 || - Aell |T
For the second one,
| VO 0 VōT (AT -A-") A7 Φ + oT A5¹
TTA5" 0
T
A, 1/2 /1 A, 1 1011221+1/ 1I
A₂ 1/12 $5 S / /110ll (1+ A /0/²,/1/ - -1l) l1bll
1 1/ A 12222
)
|| 1 A3/2A (A2 -A1) A1) 15/12/21112 ||01ll
V
A2ll A |1 ||
||A, -A2ll) |l
36

---

Published as a conference paper at ICLR 2022
Lemma H.5 (Lemma H.4 of Min et al. (2021)). let 8 A Rd satisfies (lo(s, & for all 5, 8 x A. For any 0, >
define GK -En= 0(sk, (g)o(sk, Aaa where (sk, (4) 's are iid samples from some distribution Then with probability 8,
GK
GK K
4V2C² VK
2d 1/2
En
log 8
Proof of Lemma H.5. For completeness, we provide the proof of Lemma H.5. Let 23 = (88 Ok). Denote En as the matrix obtained by replacing the k-th vector in En by Ty and leaving the rest K vectors unchanged. Then
Σn K
Σn K
1 K
(2n oxa + 2T ( 3
4C K2
la A
K
Notice that
Σx
A
10d R.
by Lemma H.1 we have the result.
Lemma H.6 (Lemma H.5. of Min et al. (2021)). Let Ø S A + AR R be bounded function s.f.
1 S C. Define Gx = > k=1 (s as (x)((sk az) + Na where (sk, ax) 's are i..d samples from
some distribution Let G = Ex (s)(s, a) J. Then for any d E (0, 1), if K satisfies
K> max 512C* G log log (2))
2d
|
4A
Then with probability at least 1 - 8, it holds simultaneously for all u E IRd that
|ulll, S VK |1w|l--..
Lemma H.7 (Extended Value Difference (Section B.1 in Cai et al. (2020))). Let {TT Thom and n' { H h=1 be two arbitrary policies and let (Qn) h=1 { be any given Q-functions. Then define (s(s)) = (Q)(s,)), mnl 8)) for all 8 E S. Then all E S,
H
Pi(s) - VT (8)
Σ
E
@2n (shs ; (-1 (18)))) m (. (88))) 81 =8
==
(30)
H
[Q (sh, on) -(Th an) ||1 =
Eyd
where := + (PaV) for any V E R.S.
Proof. Denote En =Qn -Tnint1- For any h E [H], have
V% VA [Qh Tn) -QQ% mh)
QQn Th - T/)) + (Qn - Q mh)h
QRi Th T/)) + (Ph (Ph(Vn+) V + Eh. m//h
(Qn Th - 7/.) + (Pn [h++ Vitti,, x/)) + (En, 7/,}
recursively apply the above for Drat - Vi and use the Exr notation (instead of the inner product of Ph, n²()) we can finish the prove this lemma.
Lemma H.8. Let मे
(f and Qn((s.) be the arbitrary policy and Q-function and also (s(s) (x, F (-1s)) Vs S. and Cn (r(8, a) (Th, (Tr Qn(8, a) (element-wisely)
37

---

Published as a conference paper at ICLR 2022
be the Bellman update enror. Then for any arbitrary have
H
(T)
(s)
Σ
E Ich (Sh, an) 1 s1 = Σ
Ea Isn (sh, and
81
H
(Qh (8h,,) , Tu (-18n) - Rn (-1sa) | 81
1=1
where the expectation are taken over O/-
Proof. Note the gap can be rewritten as
- -())) (1))
By Lemma H.7 with
n. n² тT, directly have
(s( (s) Σ Ba Ks an) 81 = s)+ Σ E [ (sps :), Th (-1sp) Rn (+1s))
1s 8
(31)
Next apply Lemma H.7 again with π = T = R., we directly have
(s) - (z) Σ Ea Isn (sh, an) 111 = s]
(32)
Combine the above results we prove the stated result.
Lemma H.9. For linear MDP. for any 0 S V() S H. then there exists wa E Rd s.l. TvV =
(6, way and [|l, la < 2H vd for all h E [H]. Here Tv(V a) (2 a) + (P, (s, Similarly, for any n, there exists w Rd such that Q (é. wx) with || S 2H + 1)Vd.
Proof. By definition,
TvV (PaV) = Op) (Ø, / v(s)dun(s))
+ wh = On + ((s)dun(s),
therefore ||w,|], < |0011 H (S)]| < 1 + H 2H vd. The proof of the second part is similar by backward induction and the fact V < H - h + for any π.
Lemma H.10. For any pessimistic bonus design The suppose K > Max Ms) then with probability 1 - 5, Algorithm I yields
σ H2 d/k
Th 17 - i Pi
<
VK
38

---

Published as a conference paper at ICLR 2022
Proof of Lemma H.10. Suppose wP is the coefficient corresponding the Ta Vn+1 (such wn exists by Lemma H.9), i.e. Tn Vn+1+ = x0 wh. and recall (Th Vn+ (s, a) = ((s a) th then:
(Th Vh+11) (s, (Th
(s, = ((s,0) a) (wn (h.)
k
=0(s, a) wh - ((s,a) TAn
Σ
Φ a)) (1% + Vi+a (sh+1) 1o ahp)
K
= =((s,)) wh a(s,a)]Ay
Σ
② (8h ah) (Th (5) 10 a7))
(i)
K
Σ
o (0% ah)
(1h + Ph+i (sh+2)
(Th Pnri (oh) 10%(0% ah)
(ii)
(33)
For term (i), it bounded by 2AH with probability 1 by Lemma C.2.
K
For term (i), by Cauchy inequality it is bounded by
| a)
0)1,
Σ ① (sh. an) (1h + Pa+a (sh+1) (ThPeott) (0% ah)) 10% ap)
2H
Σ d (8% ah) (1h + Vnta (sh+1) Phttt (0h (0h 16 ab)
VRK
2H Ō(HV))= = H2 / and the third inequality uses Va A.as S VI /lall Alla ||l|| ||al|2 v A with a to be either
VKK
VK
where the first inequality is by Lemma H.6 (with & = Φ/ōn and 10/ōal S |ool S 1 == c)
or wi- Moreover, Amiu (Á%) x/ maxx,e, (s) k/H2² implies ((A) -
11
The second inequality comes from Lemma H.2 with R = H since |ny = 1(r% + PA+1 (5h+1)
(Tr 1)) (ooea.a))/// (1)% a²)1= S H and | 10 / (8% af)) S 1.
The final result is obtained by absorbing the term (i) via the condition K max max MM, Ma..
Lemma H.11. Suppose random variables || < 2H, || S 2H, then
Var(XX Var(Y)) < 8H ||X Y lloo
Proof of Lemma H.11.
|Var(X) -
B| - (B[X]2 - ][Y]) = |B[(X + Y) - Y)] - -)]- + X -YDI
<B[[X + - |X- YI] +4H -
X4 -Y]+++]44 - = =SH ||X Yl
39


Reviews:
[{"review_id": "Z8guUxjZUVr", "reviewer": "Reviewer_VQKc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is overall clear and easy to follow. Incorporating variance information is a promising direction that can date back to the analysis of UCBVI, which can generally obtain better results.\n\nI have some minor comments:\n\n1. Perhaps it’s better to make some remarks in the algorithm on which step use which parts of data, that can be much more clear compared with current presentation.\n\n2. There are some minor typos in the paper, e.g. in Section 3.3 “the proof can be found in Appendix D” rather than “can be bound in Appendix D”, for Theorem 3.5 the sum term should be in the denominator. Please go through the paper again to eliminate this kind of typo.\n\n3. In the current presentation, it’s not clear where the improvement in Section 3.3 comes from. It’s acceptable due to the space constraint, but I hope there can be some intuitive interpretation on that.\n\n4. Is the lower bound of Theorem 3.5 matches the upper bound of Theorem 3.3 up to logarithm factors and higher order term? I think so, but the authors don’t provide sufficient discussion on this. And I also want to ask if there’s a separation for tabular setting and linear setting, i.e. the worst case of linear setting is beyond the tabular setting?\n\nI hope the authors can continuously improve on these aspects, which will further improve the readability.\n", "summary_of_the_paper": "This paper considers offline policy optimization with linear function approximation that incorporates the variance information into consideration, which eventually leads to a better statistical error and fine-grained statistical analysis.", "summary_of_the_review": "The overall idea is clear and easy to follow, but it can be much better if the authors can polish the paper again and provide more discussion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Uw4PcecaDz", "reviewer": "Reviewer_exon", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall comments : \n\n- This paper focuses on the problem of understanding statistical limit of offline RL algorithms, under linear representations. The authots propose a variance aware approach for offline RL, which leads to the pessimistic value estimation. The idea of pessimism has been extensively studied for offline RL recently. \n- The core idea of the algorithm is to use the variance term, to re-weight the Bellman updates - and provide improved bounds for offline RL). The paper exploits the reweighted Bellman update, which leads to the improved bounds. \n- Recent works has studied the statistical limits for offline RL (Wang et al). This paper can be seen as a follow-up along those lines, studying the limits for offline RL under linear MDP assumptions. As pointed out, even though several works already address this (e.g Jin et al 2021), they all use the standard Bellman update leading to the bound for offline RL. In contrast, this paper uses the pessimistic value, based on the variance, and argues that the re-weighting is helpful for improving bounds. The core idea is to modify the LSVI update with a variance weighting term and an additional pessimism bonus.\n- The paper is well written, and section 3 is quite easy to follow. Most importantly, it is great to see example 3.1 where the authors clearly state how existing results that equally weighs the samples has dependency on the H factor that this work is trying to avoid. More importantly, the comparisons with previous works are useful to get an understanding of the contributions of this work. \n\n\n\nFew weaknesses of the work  and negative comments : \u000b\n- I am not an expert in following the proof details of this work; therefore the comments below are not on the technical details of the proof. \n- My overall impression of a work like this is that - the variance penalty term and the re-weighting of the Bellman update does not necessarily give better insights about offline RL, other than the fact that it helps improve the bound. This is similar to any other empirical works, which can re-weight the Bellman update and claiming to have improved results. \n- What is the key novelty in the paper that leads to the improved bound? Is there a specific technical novelty introduced in the proof that leads to the improved result? Can the authors point this out exactly?\n- Otherwise, simply re-weighting the update and following similar analysis as in the vast majority of works studying offline RL theory is not a significant contribution and does not lead to new insights. The Bellman re-werighting idea has been well studied and exploited in many previous empirical works in RL. \n- How does the variance term help for offline RL? To me, it seems like the idea is a nice trick to include the variance term in the update. I do not see any bottlenecks to try this out empirically in any existing offline RL algorithm on any benchmark task like D4RL? I believe this update will be quite easy to plug in, and it would be nice to examine the significance of the variance and re-weighting term. \n\n", "summary_of_the_paper": "This paper proposes a re-weighting of the Bellman update for offline RL, using the variance term, that leads to an improved bound for offline RL. The paper is well written and easy to follow, with the key improvement (theoretically) easy to see. The core idea of the algorithm is a simple trick to re-weight the update and the analysis follows as in other offline RL works examining the statistical significance for offline value estimation.\n\n\n", "summary_of_the_review": "I do not think without experiments, the work has enough technical and theoretical novelty (in terms of proof details) for acceptance. Simply improving the bound, by re-weighting the update and following similar analysis as other offline RL works do not, in my opinion, pass the criterion. I may be wrong, as I am not an expert in following the technical proofs of the paper. \u000b", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OzlBKOlnTA6", "reviewer": "Reviewer_UKxA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe paper is clearly written. Rigorous theory is backed up by neat intuitions. The presentation is very fluent and readers are able to capture the high-level intuitions smoothly. \nThis work contributes to the study of value-basic pessimistic RL by closing the gap in suboptimality bounds. It also related RL to OPE by showing the variance-aware technique in OPE also applies to policy learning. I believe these are important insights towards a complete picture of pessimism. \n\nWeakness / questions:\nThe current setting of the paper is well studied and complete, but it might be a little restricted. For example, a nice point of the PEVI paper (Jin et al. 2021b) is that the suboptimality directly depends on the dataset, not restricting to behavior policy. I am interested whether such variance-incorporated ideas can be used for fully data-dependent constructions. This might also be interesting for a better understanding of what a static dataset can provide. \nInvertibility of covariance matrix: the feasibility algorithm of PEVI is actually not influenced by singular covariance matrix, as long as that is in line to the actual optimal policy, or the policy in comparison (i.e., both behavior and optimal policy miss some subspace). I am curious what happens when the covariance matrix is not invertible, so that Lambda_h^* does not exist. It might depend on the relationship between \\mu to optimal policy? Not expecting an exact result, but some discussions might be interesting. \n", "summary_of_the_paper": "This paper studies an extension of value-based pessimistic offline RL in linear settings, where variance information is included in the pessimistic penalty to provide a refined quantification of uncertainty. Although a little restricted to the behavior policy setting, careful treatment of uncertainty leads to improved suboptimality bound than the literature, nearly closes the gap in statistical limits of such approach, bringing insights into pessimistic offline RL.", "summary_of_the_review": "In general, this paper is clearly written and elegantly presented. The combination of rigorous theory and high-level intuitions make it fluent to follow. This work provides a refined treatment of pessimistic penalty functions, which leads to tighter upper bounds and nearly matching lower bounds. Although complete for the current setting, I think the paper can be improved by adding some broader considerations to more general cases to bring more insights beyond the restrictions of fixed behavior policy and well-behaved covariance matrix. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ImaV3rSrbX5", "reviewer": "Reviewer_of24", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n* The paper is well organized, theoretically grounded\n* The results seem of reasonable significance.\n* The related work in this area is well explained.\n\n\nWeakness:\n\n*There is a lack of empirical evaluation carried out, to showcase how the lower bound estimation \n* It's hard to follow for those who are not familiar with this sub-field. \n\n\n* Minor typo in Introduction(section 1): \"stat\" -> \"state\"", "summary_of_the_paper": "The given work proposes the introduction of a pessimistic lower bound for reinforcement learning agents.The estimated variances are used to re-weight the Bellman residual learning objective, such that the samples with higher uncertainty are correspondingly penalized.\n\n", "summary_of_the_review": "Overall, the paper is well motivated, aiming to solve an important problem in the area of offline reinforcement learning. The work is theoretically well grounded, studying offline reinforcement learning for time-inhomogeneous episodic linear Markov decision processes. While the paper is reasonably well organized, it's quite hard to grasp the fundamental concepts especially for those not an expert in this sub-field.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors motivate the paper well by the gap between the upper bound of the popular offline RL algorithm and the lower bound of the offline RL. By exploiting the special linear structure, the authors designed a variance-aware pessimistic value iteration, in which the variance estimation is used for reweighting the Bellman loss. Finally, the upper bound of the proposed algorithm in terms of the algorithm quantity is proposed, which is more refined to reflexing the problem-dependency. These results are interesting to the offline RL theoretical community. 

As the reviewers suggested, several improvements can be made to further refinement, e.g., 

- The intuition about the self-normalization in the algorithm exploited to improve the upper bound should be introduced. 
- The discussion in Sec 3.3t about the insight of the improvement of the upper bound is not sufficient. 
- The extra computational cost about the variance should be discussed.
Decision: Accept (Poster)