Year: 2021

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 uses the 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 existing best-known results (whereas the Bellman residuals are equally weighted). 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.

text: 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 uses the 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 existing best-known results (whereas the Bellman residuals are equally weighted). 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.

heading: 1 INTRODUCTION
text: Offline reinforcement learning (offline RL or batch RL Lange et al. (2012); Levine et al. (2020)) is the framework for learning a reward-maximizing policy in an unknown environment (Markov Decision Process or MDP)1 using the logged data coming from some behavior policy µ. Function approximations, on the other hand, are well-known for generalization in standard supervised learning. Offline RL with function representation/approximation, as a result, provides generalization across large state-action spaces for the challenging sequential decision-making 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 a view that Fitted Q-Iteration Gordon (1999); Ernst et al. (2005) can be 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) 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 to solve certain Atari games Mnih et al. (2015)).
1The environment could have other forms as well, e.g. partially-observed MDP (POMDP) or non-markovian decision process (NMDP).
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 are 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 et al. (2021); 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 et al. (2021a); Duan et al. (2021); Nguyen-Tang 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-free RL (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 to 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(H10) is far worse than the one that can learn in O(H3) 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 obtain 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 concentrability Rashidinejad et al. (2021); Xie et 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-adaptive bounds would indicate. Can the learning bounds reflect the nature of individual MDP instances when the MDP model has a 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?

heading: 1.1 RELATED THEORETICAL WORK
text: 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; Szepesvári and Munos, 2005; Antos et al., 2008a;b). Later, Chen and Jiang (2019); Le et 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 information-theoretical, due to the 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. 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 O(H3/dm 2) for time-inhomogeneous MDPs (Yin et al., 2021) and O(H2/dm ) for time-homogeneous MDPs (Yin and Wang, 2021a; Ren
et al., 2021). Under the single concentrability assumption, the tight rate O(H3SC?/ 2) 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. (2021a) considers function approximation under the Bellman-consistent assumptions, and, when realized to linear MDP setting, improve the sample complexity guarantee of Jin et al. (2021b) by an order O(d) (Theorem 3.2).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. 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 to [0, H], there is a H factor blow-up, which makes no horizon improvement 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 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.
Variance-aware studies. Talebi and Maillard (2018) first incorporate the variance structure in online tabular MDPs and Zanette and Brunskill (2019) tighten the result. For linear MDPs, Zhou et al. (2021) first uses variance structure to achieve the near-optimal result and the Weighted OFUL incorporates the variance structure explicitly in the regret bound. Recently, Variance-awareness is also considered in Zhang et al. (2021) for horizon-free setting and for OPE problem (Min et al., 2021).

heading: 1.2 OUR CONTRIBUTION
text: In this work, we study offline RL for time-inhomogeneous 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-aware 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 stateof-the-art guarantees. In addition, we further improve the state-action guarantee by designing an even tighter bonus (3). VAPVI-Improved (Theorem 3.3) is near-minimax optimal as indicated by our lower bound (Theorem 3.5). Importantly, the resulting learning bounds from VAPVI/VAPVI-Improved are able to characterize the adaptive nature of individual instances and yield different convergence rates for different problems. Algorithmically, 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 instance-adaptive guarantees.

heading: 2 PRELIMINARIES

heading: 2.1 PROBLEM SETTINGS
text: Episodic time-inhomogeneous linear Markov decision process. A finite-horizon Markov Decision Process (MDP) is denoted as M = (S,A, P, r,H, d1) (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. A time-inhomogeneous transition kernel Ph : S ×A 7→ ∆S (∆S represents a probability simplex)
2This comparison is based on translating their infinite horizon discounted setting to the finite-horizon case.
maps each state action(sh, ah) to a probability distribution Ph(·|sh, ah) and Ph can be different across time. In addition, r : S × A 7→ R is the mean reward function satisfying 0 ≤ r ≤ 1. d1 is the initial state distribution. H is the horizon. A policy π = (π1, . . . , πH) assigns each state sh ∈ S a probability distribution over actions according to the map sh 7→ πh(·|sh) ∀h ∈ [H] and induces a random trajectory s1, a1, r1, . . . , sH , aH , rH , sH+1 with s1 ∼ d1, ah ∼ π(·|sh), sh+1 ∼ Ph(·|sh, ah),∀h ∈ [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). 3 An episodic MDP (S,A, H, P, r) is called a linear MDP with a known (unsigned) feature map φ : S × A → Rd if there exist d unknown (unsigned) measures νh = (ν (1) h , . . . , ν (d) h ) over S and an unknown vector θh ∈ Rd such that
Ph (s ′ | s, a) = 〈φ(s, a), νh (s′)〉 , rh (s, a) = 〈φ(x, a), θh〉 , ∀s′, s ∈ S, a ∈ A, h ∈ [H].
where ‖νh(S)‖2 ≤ √ d and max(‖φ(s, a)‖2 , ‖θh‖2) ≤ 1 for all h ∈ [H] and ∀s, a ∈ S × A. ‖µh(S)‖ = ∫ S ‖µh(s)‖ ds.
V -values and Q-values. For any policy π, the V -value functions V πh (·) ∈ RS and Q-value functions Qπh(·, ·) ∈ RS×A are defined as: V πh (s) = Eπ[ ∑H t=h rt|sh = s], Q π h(s, a) = Eπ[ ∑H t=h rt|sh, ah =
s, a], ∀s, a, h ∈ S,A, [H]. The performance measure is defined as vπ := Ed1 [V π1 ] = Eπ,d1 [∑H t=1 rt ] . The Bellman (optimality) equations follow ∀h ∈ [H]: Qπh = rh + PhV πh+1, V πh = Ea∼πh [Q π h], Q ? h = rh + PhV ? h+1, V ? h = maxaQ ? h(·, a) (where Qh, Vh, Ph are vectors). By Definition 2.1, the Q-values also admit linear structures, i.e. Qπh = 〈φ,wπh〉 for some wπh ∈ Rd (Lemma H.9). Lastly, for a policy π, we denote the induced occupancy measure over the state-action space at any time h ∈ [H] to be: for any E ⊆ S ×A, dπh(E) := E[(sh, ah) ∈ E|s1 ∼ d1, ai ∼ π(·|si), si ∼ Pi−1(·|si−1, ai−1), 1 ≤ i ≤ h] and Eπ,h[f(s, a)] := ∫ S×A f(s, a)d π h(s, a)dsda. Here for notation simplicity we abuse d π h(·) to denote either probability measure or density function.
Offline learning setting. The offline RL requires the agent to learn the policy π that maximizes vπ, provided with the historical data D = {(sτh, aτh, rτh, sτh+1)} h∈[H] τ∈[K] rolled out from some behavior policy µ. The offline nature requires we cannot change µ and in particular we do not know the data generating distribution of µ. To sum up, the agent seeks to find a policy πalg such that v? − vπalg ≤ for the given batch data D and a given targeted accuracy > 0.

heading: 2.2 ASSUMPTIONS
text: It is known that learning a 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 ∈ [H]:
Σph := Eµ,h [ φ(s, a)φ(s, a)> ] , (1)
since Σph measure the coverage of state-action space for data D, we make the following assumption. Assumption 2.2 (Feature Coverage). The data distributions µ satisfy the minimum eigenvalue condition: ∀h ∈ [H], κh := λmin(Σph) > 0 and denote κ = minh κh. Note κ is a system-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 simultaneously comparison to all the policies, which is stronger than competing with optimal policy only (whereas relaxed assumption suffices, e.g. supx∈Rd xΣπ?x > xΣµx> <∞ (Uehara and Sun, 2021)). As a consequence, the behavior distribution µ must be able to 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 Σph, which causes the alternative notion of κ := minh∈[H]{κh : s.t. κh = smallest positive eigenvalue at time h} (see Appendix G.1 for detailed discussions). In this scenario, learning the optimal policy cannot be guaranteed as a constant
3This definition is a standard extension over the tabular MDPs by referencing the similar notions from the bandit literature, i.e. from Multi-armed Bandit to Linear Bandit (Lattimore and Szepesvári, 2020).
suboptimality gap needs to be suffered due to the lack of coverage and this is called 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 Σ−1D exists and Min et al. (2021) for the OPE problem.
Next, for any function Vh+1(·) ∈ [0, H−h], we define the conditional variance σVh+1 : S×A → R+ as σVh+1(s, a)
2 := max{1,VarPh(Vh+1)(s, a)}.4 Based on this definition, we can define the variance-involved population covariance matrices as:
Λph := Eµ,h [ σVh+1(s, a) −2φ(s, a)φ(s, a)> ] .
In particular, when Vh = V ?h , we use the notation Λ ?p h instead. Since sup(s,a)∈S×A σVh(s, a) 2 ≤ H2, then by Assumption 2.2 we directly have the following corollary. Corollary 2.3. Define ιh := λmin(Λph), ι := minh ιh. Then ιh ≥ κh H2 > 0 ∀h ∈ [H], and ι > 0.

heading: 3 ALGORITHM
text: Least square regression is usually considered as one of “the default tools” for solving with problems with linear structures (e.g. LinUCB algorithm for linear Bandits) and finds its popularity in RL as well since Least-Square Value Iteration (LSVI, Jin et al. (2020)) is shown to be provably efficient for linear MDPs, due to that Vh+1(s′) is an unbiased estimator of [PhVh+1](s, a). Concretely, it solves the ridge regression problems at each time steps (with λ > 0 being the regularization parameter):
ŵh := argmin w∈Rd λ‖w‖22 + K∑ k=1 [ 〈φ(skh, akh), w〉 − rkh − Vh+1(s′kh+1) ]2 (2)
and has the closed-form solution ŵh = Σ−1h ∑K k=1 φ(s k h, a k h)[rk,h + Vh+1(s ′k h )] with Σ
−1 h =∑K
k=1 φ(s k h, a k h)φ(s k h, a k h) > + λI . In offline RL, this has also been used in pessimistic value iteration (Jin et 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 φ(s, a) = 1s,a (i.e. tabular MDPs)5, by direct calculation the learning bound has the formO(dH· ∑ h,s,a d π? h (s, a) √ 1 K·dµ
h (s,a)
) and
the optimal result (Yin and Wang (2021b) Theorem 4.1) gives O( ∑ h,s,a d π? h (s, a)
√ VarPs,a (r+V ? h+1 )
K·dµ h
(s,a) ).
The former has the horizon dependence H2 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.t V ?). If we go deeper, one could find that it might not be all that ideal to put equal weights on 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, ah corresponds to a different distribution P (·|sh, ah) and there are possibly infinite many of them). Therefore, conceptually, the sample piece (sh, ah, sh+1) that has higher variance distribution P (·|sh, ah) tends to be less “reliable” than the one (s′h, a ′ h, s ′ h+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.

heading: 3.1 VARIANCE-AWARE PESSIMISTIC VALUE ITERATION
text: Now we explain our framework that incorporates the variance information. By the offline nature, we can use the independent episodic data D′ = {(s̄τh, āτh, r̄τh, s̄τ ′h )} h∈[H] τ∈[K] (from µ) to estimate the conditional variance of any V -values Vh+1 via the definition [VarhVh+1](s, a) = [Ph(Vh+1)
2](s, a)− ([PhVh+1](s, a))2. For the second order moment, by Definition 2.1, it holds[ PhV 2 h+1 ] (s, a) = ∫ S V 2h+1 (s ′) dPh (s ′ | s, a) = φ(s, a)> ∫ S V 2h+1 (s ′) dνh (s ′) .
4The max(1, ·) applied here is for technical reason only. In general, it suffices to think σ2Vh+1 ≈ VarhVh+1. 5This provides a valid illustration since tabular MDP is a special case of linear MDPs.
Denote βh := ∫ S V 2 h+1 (s ′) dνh (s ′), then PhV 2h+1 = 〈φ, βh〉 and we can estimator it via:
β̄h = argmin β∈Rd K∑ k=1 [〈 φ(s̄kh, ā k h), β 〉 − V 2h+1 ( s̄kh+1 )]2 + λ‖β‖22 = Σ̄−1h K∑ k=1 φ(s̄kh, ā k h)V 2 h+1 ( s̄kh+1 ) and, similarly, the first order moment PhVh+1 := 〈φ, θh〉 can be estimated via:
θ̄h = argmin θ∈Rd K∑ k=1 [〈 φ(s̄kh, ā k h), θ 〉 − Vh+1 ( s̄kh+1 )]2 + λ‖θ‖22 = Σ̄−1h K∑ k=1 φ(s̄kh, ā k h)Vh+1 ( s̄kh+1 ) The final estimator is defined as σ̂2Vh(·, ·) := max{1, V̂arhVh+1(·, ·)} with V̂arhVh+1(·, ·) = 〈φ(·, ·), β̄h〉[0,(H−h+1)2] − [ 〈φ(·, ·), θ̄h〉[0,H−h+1] ]2 .6 In particular, when setting Vh+1 = V̂h+1,
it recovers σ̂h in Algorithm 1 line 8. Here Σ̄h = ∑K τ=1 φ(s̄ τ h, ā τ h)φ(s̄ τ h, ā τ h) > + λId.
Variance-weighted LSVI. The idea of LSVI (2) is based on approximate the Bellman updates: Th(V )(s, a) = rh(s, a) + (PhV )(s, a). With variance estimator σ̂h at hand, we can modify (2) to solve the variance-weighted LSVI instead (Line 10 of Algorithm 1)
ŵh := argmin w∈Rd λ‖w‖22+ K∑ k=1
[ 〈φ(skh, akh), w〉 − rkh − V̂h+1(s′kh+1) ]2 σ̂2h(s k h, a k h) = Λ̂−1h K∑ k=1 φ ( skh, a k h ) · [ rkh + V̂h+1 ( skh+1 )] σ̂2(skh, a k h)
where Λ̂h = ∑K k=1 φ(s k h, a k h)φ(s k h, a k h) >/σ̂2h(s k h, a k h) + λId. The estimated Bellman update T̂h (acts on V̂h+1) is defined as: (T̂hV̂h+1)(·, ·) = φ(·, ·)>ŵh and the pessimism Γh is assigned to update Q̂h ≈ T̂hV̂h+1 − Γh, i.e. Bellman update + Pessimism (Line 12-13 in Algorithm 1). Tighter Pessimistic Design. To improve the learning guarantee, we create a tighter penalty design that includes Λ̂−1h rather than Σ̄ −1 h and an extra higher order O( 1 K ) term:
Γh ← O (√ d · (φ(·, ·)>Λ̂−1h φ(·, ·)) 1/2 ) + 2H3 √ d
K
Note such a design admits no explicit factor in H in the main term (as opposed to Jin et al. (2021b)) therefore it is the key for achieving adaptive/problem-dependent 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 D = {(sτh, aτh, rτh, sτ ′h )} h∈[H] τ∈[K] and D ′ = {(s̄τh, āτh, r̄τh, s̄τ ′h )} h∈[H] τ∈[K] for different purposes (estimating variance and updating Q-values).

heading: 3.2 MAIN RESULT
text: We denote quantitiesM1,M2,M3,M4 as 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. If K > max{M1,M2,M3,M4} and √ d > ξ,
where ξ := supV ∈[0,H], s′∼Ph(s,a), h∈[H] ∣∣∣∣ rh+V (s′)−(ThV )(s,a)σV (s,a) ∣∣∣∣. Then for any 0 < λ < κ, with
probability 1− δ, for all policy π simultaneously, the output π̂ of Algorithm 1 satisfies
vπ − vπ̂ ≤ Õ (√ d · H∑ h=1 Eπ [√ φ(·, ·)>Λ−1h φ(·, ·) ]) + 2H4 √ d K
where Λh = ∑K k=1 φ(skh,a k h)·φ(s k h,a k h) >
σ2 V̂h+1(s k h ,ak h )
+ λId. In particular, we have with probability 1− δ,
v? − vπ̂ ≤ Õ (√ d · H∑ h=1 Eπ? [√ φ(·, ·)>Λ?−1h φ(·, ·) ]) + 2H4 √ d K
where Λ?h = ∑K k=1 φ(skh,a k h)·φ(s k h,a k h) >
σ2 V ? h+1 (sk h ,ak h )
+ λId and Õ hides universal constants and the Polylog terms.
6The truncation used here is a standard treatment for making the estimator to be within the valid range.
Algorithm 1 Variance-Aware Pessimistic Value Iteration (VAPVI) 1: Input: Dataset D = {(sτh, aτh, rτh)}K,Hτ,h=1 D
′ = {(s̄τh, āτh, r̄τh)}K,Hτ,h=1. Universal constant C. 2: Initialization: Set V̂H+1(·)← 0. 3: for h = H,H − 1, . . . , 1 do 4: Set Σ̄h ← ∑K τ=1 φ(s̄ τ h, ā τ h)φ(s̄ τ h, ā τ h) > + λI
5: Set β̄h ← Σ̄−1h ∑K τ=1 φ(s̄ τ h, ā τ h) · V̂h+1(s̄τh+1)2
6: Set θ̄h ← Σ̄−1h ∑K τ=1 φ(s̄ τ h, ā τ h) · V̂h+1(s̄τh+1)
7: Set [ V̂arhV̂h+1 ] (·, ·) = 〈 φ(·, ·), β̄h 〉 [0,(H−h+1)2] − [〈 φ(·, ·), θ̄h 〉 [0,H−h+1] ]2 8: Set σ̂h(·, ·)2 ← max{1, V̂arPh V̂h+1(·, ·)} 9: Set Λ̂h ← ∑K τ=1 φ (s τ h, a τ h)φ (s τ h, a τ h) > /σ̂2(sτh, a τ h) + λ · I ,
10: Set ŵh ← Λ̂−1h (∑K τ=1 φ (s τ h, a τ h) · ( rτh + V̂h+1 (s τ h+1) ) /σ̂2(sτh, a τ h) )
11: Set Γh(·, ·)← C √ d · ( φ(·, ·)>Λ̂−1h φ(·, ·) )1/2 + 2H 3 √ d K (Use ΓIh for the improved version)

heading: 12: Set Q̄h(·, ·)← φ(·, ·)>ŵh − Γh(·, ·)
text: 13: Set Q̂h(·, ·)← min { Q̄h(·, ·), H − h+ 1
}+ 14: Set π̂h(· | ·)← arg maxπh 〈 Q̂h(·, ·), πh(· | ·) 〉 A, V̂h(·)← maxπh 〈 Q̂h(·, ·), πh(· | ·) 〉 A 15: end for 16: Output: {π̂h}Hh=1.
Theorem 3.2 provides several improvements over the existing best-known results and we now explain it. However, before that, we first discuss about our theorem condition.
Comparing to Zhou et al. (2021). In the online regime, Zhou et al. (2021) is the first result that achieves optimal regret rate with O(dH √ T ) in the linear (mixture) MDPs. However, this tight rate is achieved based on the condition d ≥ H (see their Theorem 6 and Remark 7). In offline RL, VAPVI only requires a milder condition √ d > ξ comparing to d ≥ H (since for any fixed V ∈ [0, H], the standardized quantity r+V (s ′)−(ThV )(s,a) σV (s,a)
is bounded by constant with high probability, e.g. by chebyshev inequality), which makes our result apply to a wider range of linear MDPs.
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( √ d) on the feature dimension, and improves the horizon dependence as Λh < 1H2 Σh implies Λ −1 h 4 H2Σ−1h . In addition, when instantiate to the tabular case, i.e. φ(s, a) = 1s,a, VAPVI gives
O( √ d ∑ h,s,a d π? h (s, a)
√ VarPs,a (r+V ? h+1 )
K·dµ h
(s,a) ), which enjoys O(
√ H) improvement over PEVI (recall
Example 3.1) and the order O(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( 11−γ )) therefore is not optimal. Their general function approximation scheme provides nice characterizations for on-support error and off-support error, but the algorithmic framework is information-theoretical 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 no 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 Qπ ≤ 1, and their PACLE algorithm provides near-minimax optimal guarantee in this setting. However, when recovering to the standard setting Qπ ∈ [0, H], their bound will rescale by an H factor,7 which is suboptimal due to the variance-unawareness. The reason behind this is: when Qπ ≤ 1, lack of variance information encoding will not matter, since in this case VarP (V π) ≤ 1 has constant order (therefore will not affect the optimal rate); when Qπ ∈ [0, H], VarP (V π) can be as large as H2, effectively leveraging the variance information can help improve the sample efficiency,
7Check their Footnote 2 in Page 9.
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 ‖Eπ[φ(·, ·)]‖M−1 ≤ Eπ[‖φ(·, ·)‖M−1 ] by Jensen’s inequality and that norm ‖·‖M−1 is convex for some positive-definite matrix M . Adaptive characterization and faster convergence. Comparing to existing works, one major improvement is that the main term for VAPVI √ d ∑H h=1 Eπ? [√ φ(·, ·)>Λ?−1h φ(·, ·) ] admits no explicit dependence on H , which provides a more adaptive/instance-dependent characterization. For instance, if we ignore the technical treatment by taking λ = 0 and σ?h ≈ VarP (V ?h+1), then for the partially deterministic systems (where there are t stochastic Ph’s andH− t deterministic Ph’s), the main term diminishes to √ d ∑t i=1 Eπ? [√ φ(·, ·)>Λ?−1hi φ(·, ·) ] with hi ∈ {h : s.t. Ph is stochastic} and can be a much smaller quantity when t H . Furthermore, for the fully deterministic system, VAPVI automatically provides faster convergence rate O( 1K ) from the higher order term, given that the main term degenerates to 0. Those adaptive/instance-dependent features are not enjoyed by (Xie et al., 2021a; Zanette et al., 2021), as they always provide the standard statistical rate O( 1√
K ) (also
check Remark C.9 for a related discussion).

heading: 3.3 VAPVI-IMPROVED: FURTHER IMPROVEMENT IN STATE-ACTION DIMENSION
text: 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 (φ ≥ 0). Concretely, we replace the following ΓIh in Algorithm 1 instead, and call the algorithm VAPVI-Improved (or VAPVI-I for short). The proof can be found in Appendix D.
ΓIh(s, a)← φ(s, a)> ∣∣∣∣Λ̂−1h K∑
τ=1
φ (sτh, a τ h) · ( rτh + V̂h+1 (s τ h+1)− ( T̂hV̂h+1 ) (sτh, a τ h) )
σ̂2h(s τ h, a τ h) ∣∣∣∣+Õ(H3d/κK ) (3) Theorem 3.3. Let K be the number of episodes. If K > max{M1,M2,M3,M4} and √ d > ξ. Deploying ΓIh (3) in Algorithm 1. Then for any 0 < λ < κ, with probability 1− δ, for all policy π simultaneously, the output π̂ of Algorithm 1 (VAPVI-I) satisfies
vπ − vπ̂ ≤ Õ (√ d · H∑ h=1 √ Eπ[φ(·, ·)]>Λ−1h Eπ[φ(·, ·)] ) + Õ( H4d/κ K )
In particular, when choosing π = π?, the above guarantee holds true with Λ−1h replaced by Λ ?−1 h . Here Λ−1h , Λ ?−1 h , ξ are defined the same as Theorem 3.2.
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π ‖φ‖Λ−1h to ‖Eπ[φ]‖Λ−1h . Clearly, the two bounds differ by the magnitude of Jensen’s inequality. To provide a 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 consider the following assumption for our discussion. Assumption 3.4 (Rashidinejad et al. (2021); Xie et al. (2021b)). There exists a optimal policy π?, s.t. suph,s,a d π? h (s, a)/d µ h(s, a) := C ? <∞, where dπ is the marginal state-action probability under π.
In tabular RL, φ(s, a) = 1s,a and d = S ·A (S,A be the finite state, action cardinality), then
Theorem 3.2→ √ SA H∑ h ∑ s,a dπ ? h (s, a)
√ VarPs,a(r + V ? h+1) K · dµh(s, a) ≤ √ H3C?S2A K ;
Theorem 3.3→ √ SA H∑ h √√√√∑ s,a dπ ? h (s, a) 2 VarPs,a(r + V ? h+1) K · dµh(s, a) ≤ √ H3C?SA K .
(4)
Theorem 3.3 enjoys a S state improvement over Theorem 3.2 and nearly recovers the minimax rate√ H3C?S K (Xie et al., 2021b). The detailed derivation can be found in Appendix G. Also, to show our 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 c, c′ > 0 such that given dimension d, horizon H and sample size K > c′d3, one can always find a family of linear MDP instancesM such that (where Λ?h = ∑K k=1 φ(skh,a k h)·φ(s k h,a k h) >
Varh(V ?h+1)(s k h,a k h)
satisfies (Λ?h) −1 exists ∀M ∈M)
inf π̂ sup M∈M
EM [ v? − vπ̂ ]/(√ d · H∑ h=1 √ Eπ? [φ]>(Λ?h)−1Eπ? [φ] ) ≥ c. (5)
Theorem 3.5 nearly matches the main term in VAPVI-I (Theorem 3.3) and certifies it is near-optimal.

heading: 4 PROOF OVERVIEW
text: 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 lemma (Lemma H.7), we can convert bounding the suboptimality gap of v? − vπ̂ to bounding ∑H h=1 2 · Eπ [Γh(sh, ah)], given that |(ThV̂h+1 − T̂hV̂h+1)(s, a)| ≤ Γh(s, a) for all s, a, h. To bound ThV̂h+1 − T̂hV̂h+1, by decomposing it reduces to bounding the key quantity
φ(s, a)>Λ̂−1h [ K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ] (6)
The term is treated in two steps. First, we bound the gap of ∥∥∥σ2
V̂h+1 − σ̂2h ∥∥∥ so we can convert σ̂2h to σ2 V̂h+1 . Next, since Var [ rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) | sτh, aτh ] ≈ σ2 V̂h+1 , therefore by the variance-weighted scheme in (equation 6), we can leverage the recent technical development Bernstein inequality for self-normalized martingale (Lemma H.3) for acquiring the tight result, in contrast to the previous treatment of Hoeffding inequality for self-normalized martingale + Covering.8 For the second part, one needs to further convert σ2
V̂h+1 to σ?2h (Λ −1 h to Λ ?−1 h ) with appropriate
concentrations. The proof of Theorem 3.3 is similar but with more complicated computations and relies on using the linear representation of φ in ΓIh (3), 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 inequalities (e.g. from total variation to KL divergence). For completeness, we provide the full proof in Appendix E.

heading: 5 DISCUSSION AND CONCLUSION
text: This work studies offline RL with linear MDP representation and contributes Variance Aware Pessimistic Value Iteration (VAPVI) 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 are 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-I 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 instance-dependent characterizations, the lower bound only holds true for a class of hard instances. In this sense, whether “instance-dependent optimality” can be achieved remains elusive in the current linear MDP setting (such a discussion is recently initiated in MAB problems (Xiao et al., 2021)). We leave this as future work.
8Variance-reweighting in (6) is important, since applying Bernstein inequality for self-normalized martingale (Lemma H.3) without variance-reweighting cannot provide any improvement.

heading: A NOTATION LIST
text: Σph Eµ,h [ φ(s, a)φ(s, a)> ] Λph Eµ,h [ σVh+1(s, a) −2φ(s, a)φ(s, a)> ] κ minh λmin(Σ p h) ι minh λmin(Λ p h) ≥ κ/H2 for any Vh
σ2V (s, a) max{1,VarPh(V )(s, a)} for any V σ2Vh+1(s, a) max{1,VarPh(Vh+1)(s, a)} σ̂2Vh(s, a) max{1, V̂arhVh+1(s, a)} Σ̄h ∑K τ=1 φ(s̄ τ h, ā τ h)φ(s̄ τ h, ā τ h) > + λId
Λ̂h ∑K k=1 φ(s k h, a k h)φ(s k h, a k h) >/σ̂2h(s k h, a k h) + λId
M1 max{2λ, 128 log(2d/δ), 128H4 log(2d/δ)/κ2} M2 max{ λ 2 κ log((λ+K)H/λδ) , 96 2H12d log((λ+K)H/λδ)/κ5}
M3 max { 512H4/κ2 log ( 2d δ ) , 4λH2/κ } M4 12 √ H4d log((λ+K)H/λδ)/κ
δ Failure probability
ξ supV ∈[0,H], s′∼Ph(s,a), h∈[H] ∣∣∣∣ rh+V (s′)−(ThV )(s,a)σV (s,a) ∣∣∣∣

heading: B EXTENDED LITERATURE REVIEW

heading: B.1 LINEAR MODEL REPRESENTATION AND ITS EXTENSION IN ONLINE RL
text: 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) propose Linear mixture MDP, which assumes the transition probability is a linear combination of some base kernels. Linear Bellman Complete model (Zanette et al., 2020) generalizes linear MDP model by allowing linear functions to approximate the Q-function and the function class is closed under the Bellman update. The notion of low Bellman rank (Jiang et al., 2017) subsumes not only linear MDPs but also models including linear quadratic regulator (LQR), Reactive POMDP (Krishnamurthy et 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 et 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 et al., 2021), reward-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 et al., 2021). In particular, Zhou et al. (2021) shows UCRL-VTR+ is near-minimax optimal when feature dimension d ≥ H .

heading: B.2 EXISTING RESULTS IN OFFLINE RL WITH MODEL REPRESENTATIONS
text: 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; Szepesvári and Munos, 2005; Antos et al., 2008a;b). Later, Chen and Jiang (2019); Le et 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 information-theoretical, due to the 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. 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 O(H3/dm 2) for time-inhomogeneous MDPs (Yin et al., 2021) and O(H2/dm ) for time-homogeneous MDPs (Yin and Wang, 2021a; Ren et al., 2021). Under the single concentrability assumption, the tight rate O(H3SC?/ 2) 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 are 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 (PEVI), which is an offline counterpart of LSVI-UCB in Jin et al. (2020). 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. (2021a) considers function approximation under the Bellman-consistent assumptions, and, when realized to linear MDP setting, improve the sample complexity guarantee of Jin et al. (2021b) by a order O(d) (Theorem 3.2).9 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. 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 a 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 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 in the offline regime.

heading: C PROOFS IN SECTION 3.2
text: Instead of proofing the result for v? − vπ̂ , in most parts of the proof we deal with V ?1 − V π̂1 , which is more general.

heading: C.1 SOME PREPARATIONS
text: Define the Bellman update error ζh(s, a) := (ThV̂h+1)(s, a) − Q̂h(s, a) and recall π̂h(s) = arg maxπh〈Q̂h(s, ·), πh(· | s)〉A, then by the direct application of Lemma H.8
V π1 (s)− V π̂1 (s) ≤ H∑ h=1 Eπ [ζh(sh, ah) | s1 = s]− H∑ h=1 Eπ̂ [ζh(sh, ah) | s1 = s] . (7)
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− δ, it holds for all h, s, a ∈ [H]×S ×A that |(ThV̂h+1− T̂hV̂h+1)(s, a)| ≤ Γh(s, a), then it implies ∀s, a, h ∈ S × A × [H], 0 ≤ ζh(s, a) ≤ 2Γh(s, a).
9This comparison is based on translating their infinite horizon discounted setting to the finite horizon case.
Furthermore, it holds for any policy π simultaneously, with probability 1− δ,
V π1 (s)− V π̂1 (s) ≤ H∑ h=1 2 · Eπ [Γh(sh, ah) | s1 = s] .
Proof of Lemma C.1. We first show given |(ThV̂h+1 − T̂hV̂h+1)(s, a)| ≤ Γh(s, a), then 0 ≤ ζh(s, a) ≤ 2Γh(s, a), ∀s, a, h ∈ S ×A× [H]. Step1: we first show 0 ≤ ζh(s, a), ∀s, a, h ∈ S ×A× [H].
Indeed, if Q̄h(s, a) ≤ 0, then by definition Q̂h(s, a) = 0 and in this case ζh(s, a) := (ThV̂h+1)(s, a) − Q̂h(s, a) = (ThV̂h+1)(s, a) ≥ 0; if Q̄h(s, a) > 0, then Q̂h(s, a) ≤ Q̄h(s, a) and
ζh(s, a) :=(ThV̂h+1)(s, a)− Q̂h(s, a) ≥ (ThV̂h+1)(s, a)− Q̄h(s, a) =(ThV̂h+1)(s, a)− (T̂hV̂h+1)(s, a) + Γh(s, a) ≥ 0.
Step2: next we show ζh(s, a) ≤ 2Γh(s, a), ∀s, a, h ∈ S ×A× [H].
Indeed, we have Q̂h(s, a) = max(Q̄h(s, a), 0) and this is because: Q̄h(x, a) = (T̂hV̂h+1)(x, a)− Γh(x, a) ≤ (ThV̂h+1)(x, a) ≤ H − h+ 1. Therefore, in this case we have:
ζh(s, a) :=(ThV̂h+1)(s, a)− Q̂h(s, a) ≤ (ThV̂h+1)(s, a)− Q̄h(s, a) =(ThV̂h+1)(s, a)− (T̂hV̂h+1)(s, a) + Γh(s, a) ≥ 2 · Γh(s, a).
For the last statement, denote F := {0 ≤ ζh(s, a) ≤ 2Γh(s, a), ∀s, a, h ∈ S × A × [H]}. Note conditional on F, then by equation 7, V π1 (s)− V π̂1 (s) ≤ ∑H h=1 2 ·Eπ[Γh(sh, ah) | s1 = s] holds for any policy π almost surely. Therefore,
P [ ∀π, V π1 (s)− V π̂1 (s) ≤ H∑ h=1 2 · Eπ[Γh(sh, ah) | s1 = s]. ]
=P [ ∀π, V π1 (s)− V π̂1 (s) ≤ H∑ h=1 2 · Eπ[Γh(sh, ah) | s1 = s] ∣∣∣∣∣F ] · P[F]
+P [ ∀π, V π1 (s)− V π̂1 (s) ≤ H∑ h=1 2 · Eπ[Γh(sh, ah) | s1 = s] ∣∣∣∣∣Fc ] · P[Fc]
≥P [ ∀π, V π1 (s)− V π̂1 (s) ≤ H∑ h=1 2 · Eπ[Γh(sh, ah) | s1 = s] ∣∣∣∣∣F ] · P[F] ≥ 1 · P[F] ≥ 1− δ,
which finishes the proof.

heading: C.2 BOUNDING
text: ∣∣∣(ThV̂h+1)(s, a)− (T̂hV̂h+1)(s, a)∣∣∣.
By Lemma C.1, it remains to bound |(ThV̂h+1)(s, a)−(T̂hV̂h+1)(s, a)|. Supposewh is the coefficient corresponding to the ThV̂h+1 (such wh exists by Lemma H.9), i.e. ThV̂h+1 = φ>wh, and recall
(T̂hV̂h+1)(s, a) = φ(s, a)>ŵh, then:( ThV̂h+1 ) (s, a)− ( T̂hV̂h+1 ) (s, a) = φ(s, a)> (wh − ŵh)
=φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 )) /σ̂2h(s τ h, a τ h) )
=φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( ThV̂h+1 ) (sτh, a τ h) /σ̂ 2 h(s τ h, a τ h) ) ︸ ︷︷ ︸
(i)
+ φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ) ︸ ︷︷ ︸
(ii)
.
(8)
The term (i) is dealt by the following lemma. Lemma C.2. Recall κ in Assumption 2.2. Suppose K ≥ max { 512H4/κ2 log (
2d δ
) , 4λH2/κ } ,
then with probability 1− δ, for all s, a, h ∈ S ×A× [H]∣∣∣∣∣φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( ThV̂h+1 ) (sτh, a τ h) /σ̂ 2(sτh, a τ h) )∣∣∣∣∣ ≤ 2λH3 √ d/κ K .
Proof. Recall ThV̂h+1 = φ>wh and apply Lemma H.6, we obtain with probability 1 − δ, for all s, a, h ∈ S ×A× [H],
φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( ThV̂h+1 ) (sτh, a τ h) /σ̂ 2(sτh, a τ h) )
=φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · φ(sτh, aτh)>wh/σ̂2(sτh, aτh) ) =φ(s, a)>wh − φ(s, a)>Λ̂−1h ( Λ̂h − λI ) wh = λ · φ(s, a)>Λ̂−1h wh
≤λ ‖φ(s, a)‖Λ̂−1h · ‖wh‖Λ̂−1h ≤ λ K ‖φ(s, a)‖(Λ̃ph)−1 · ‖wh‖(Λ̃ph)−1
≤ λ K
1 · √∥∥∥(Λ̃ph)−1∥∥∥ · 2H√d ·√∥∥∥(Λ̃ph)−1∥∥∥
where Λ̃ph := Eµ,h [ σ̂h(s, a) −2φ(s, a)φ(s, a)> ]
and the second inequality is by Lemma H.6 (with φ′ = φ/σ̂h and ‖φ/σ̂h‖ ≤ ‖φ‖ ≤ 1 := C) and the third inequality uses √ a> ·A · a ≤√
‖a‖2 ‖A‖2 ‖a‖2 = ‖a‖2 √ ‖A‖2 with a to be either φ or wh. Moreover, λmin(Λ̃ p h) ≥
κ/maxh,s,a σ̂h(s, a) 2 ≥ κ/H2 implies ∥∥∥(Λ̃ph)−1∥∥∥ ≤ H2/κ, therefore for all s, a, h ∈ S ×A× [H], with probability 1− δ∣∣∣∣∣φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( ThV̂h+1 ) (sτh, a τ h) /σ̂ 2(sτh, a τ h) )∣∣∣∣∣ ≤ 2λH3 √ d/κ K .
For term (ii), denote: xτ = φ(sτh,a τ h)
σ̂(sτh,a τ h) , ητ =
( rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂(sτh, a τ h),
then by Cauchy inequality it follows
∣∣∣∣∣φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) )∣∣∣∣∣ ≤ √ φ(s, a)>Λ̂−1h φ(s, a) · ||
K∑ τ=1
xτητ ||Λ̂−1h (9)
C.2.1 ANALYZING THE TERM √ φ(s, a)Λ̂−1h φ(s, a) Recall (in Theorem 3.2) the estimated Λ̂h = ∑K τ=1 φ (s τ h, a τ h)φ (s τ h, a τ h) > /σ̂2(sτh, a τ h) + λ · I and
Λh = ∑K τ=1 φ(s τ h, a τ h) >φ(sτh, a τ h)/σ
2 V̂h+1 (sτh, a τ h) + λI . Then we have the following lemma to control the term √ φ(s, a)Λ̂−1h φ(s, a).
Lemma C.3. Denote the quantities C1 = max{2λ, 128 log(2d/δ), 128H4 log(2d/δ)/κ2} and C2 = max{ λ 2 κ log((λ+K)H/λδ) , 96 2H12d log((λ + K)H/λδ)/κ5}. Suppose the number of episode K satisfies K > max{C1, C2}, then with probability 1− δ,
√ φ(s, a)Λ̂−1h φ(s, a) ≤ 2 √ φ(s, a)Λ−1h φ(s, a), ∀s, a ∈ S ×A.
Proof of Lemma C.3. By definition √ φ(s, a)Λ̂−1h φ(s, a) = ‖φ(s, a)‖Λ̂−1h . Then denote
Λ̂′h = 1
K Λ̂h, Λ
′ h =
1
K Λh,
where Λh = ∑K τ=1 φ(s τ h, a τ h) >φ(sτh, a τ h)/σ
2 V̂h+1 (sτh, a τ h) + λI . Under the condition of K, by
Lemma C.7, with probability 1− δ
∥∥∥Λ̂′h − Λ′h∥∥∥ ≤ sup s,a ∥∥∥∥∥φ(s, a)φ(s, a)>σ̂2h(s, a) − φ(s, a)φ(s, a) >
σ2 V̂h+1 (s, a) ∥∥∥∥∥ ≤ sup
s,a
∣∣∣∣∣ σ̂ 2 h(s, a)− σ2V̂h+1(s, a)
σ̂2h(s, a)σ 2 V̂h+1 (s, a)
∣∣∣∣∣ · ‖φ(s, a)‖2 ≤ sups,a ∣∣∣∣∣ σ̂ 2 h(s, a)− σ2V̂h+1(s, a) 1 ∣∣∣∣∣ · 1 ≤ 12 √ H4d
κK log
( (λ+K)H
λδ
) + 12λ H2 √ d
κK .
(10)
Next by Lemma H.5 (with φ to be φ/σV̂h+1 and C = 1), it holds with probability 1− δ,
∥∥∥∥Λ′h − (Eµ,h[φ(s, a)φ(s, a)>/σ2V̂h+1(s, a)] + λK Id )∥∥∥∥ ≤ 4√2√K ( log 2d δ )1/2 .
Therefore by Weyl’s spectrum theorem and the condition K > max{2λ, 128 log(2d/δ), 128H4 log(2d/δ)/κ2}, the above implies
‖Λ′h‖ =λmax(Λ′h) ≤ λmax ( Eµ,h[φ(s, a)φ(s, a)>/σ2V̂h+1(s, a)] ) + λ K + 4 √ 2√ K ( log 2d δ )1/2 = ∥∥∥Eµ,h[φ(s, a)φ(s, a)>/σ2V̂h+1(s, a)]∥∥∥2 + λK + 4 √ 2√ K ( log 2d δ
)1/2 ≤‖φ(s, a)‖2 + λ
K +
4 √
2√ K
( log 2d
δ
)1/2 ≤ 1 + λ
K +
4 √
2√ K
( log 2d
δ
)1/2 ≤ 2,
λmin(Λ ′ h) ≥λmin ( Eµ,h[φ(s, a)φ(s, a)>/σ2V̂h+1(s, a)] ) + λ K − 4 √ 2√ K ( log 2d δ )1/2 ≥λmin ( Eµ,h[φ(s, a)φ(s, a)>/σ2V̂h+1(s, a)] ) − 4 √ 2√ K ( log 2d δ
)1/2 ≥ κ H2 − 4 √ 2√ K ( log 2d δ )1/2 ≥ κ 2H2 .
Hence with probability 1− δ, ‖Λ′h‖ ≤ 2 and ∥∥Λ′−1h ∥∥ = 1/λmin(Λ′h) ≤ 2H2/κ. Similarly, one can
show ∥∥∥Λ̂′−1h ∥∥∥ ≤ 2H2/κ with high probability.
Now apply Lemma H.4 to Λ̂′h and Λ ′ h and a union bound, we obtain with probability 1− δ, for all s, a
‖φ(s, a)‖Λ̂′−1h ≤
[ 1 + √∥∥Λ′−1h ∥∥ ‖Λ′h‖ · ∥∥∥Λ̂′−1h ∥∥∥ · ∥∥∥Λ̂′h − Λ′h∥∥∥ ] · ‖φ(s, a)‖Λ′−1h
≤ [ 1 + √ 2H2
κ · 1 · 2H
2 κ · ∥∥∥Λ̂′h − Λ′h∥∥∥ ] · ‖φ(s, a)‖Λ′−1h
≤ 1 + √√√√48H4
κ2
(√ H4d
κK log
( (λ+K)H
λδ
) + λ H2 √ d
κK ) · ‖φ(s, a)‖Λ′−1h ≤ 1 + √√√√96H4
κ2
√ H4d
κK log
( (λ+K)H
λδ ) · ‖φ(s, a)‖Λ′−1h ≤ 2 ‖φ(s, a)‖Λ′−1h where the third inequality uses equation 10 and the last and the second last inequality use K > max{ λ 2
κ log((λ+K)H/λδ) , 96 2H12d log((λ + K)H/λδ)/κ5}. Note the above is equivalent to√ φ(s, a)Λ̂−1h φ(s, a) ≤ 2 √ φ(s, a)Λ−1h φ(s, a) by multiplying 1/ √ K on both sides.
C.2.2 ANALYZING THE TERM || ∑K τ=1 xτητ ||Λ̂−1
Lemma C.4. Recall xτ = φ(sτh,a τ h)
σ̂(sτh,a τ h)
and ητ = ( rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂(sτh, a τ h).
Let CH,d,κ := 12 √ H4d log((λ+K)H/λδ)/κ and denote
ξ := sup V ∈[0,H], s′∼Ph(s,a), h∈[H] ∣∣∣∣rh + V (s′)− (ThV ) (s, a)σV (s, a) ∣∣∣∣ .
If K ≥ 4C2H,d,κ, then with probability 1− δ,∥∥∥∥∥ K∑ τ=1 xτητ ∥∥∥∥∥ Λ̂−1 ≤ 16 √ d log ( 1 + K λd ) · log ( 4K2 δ ) + 4ξ log ( 4K2 δ ) ≤ Õmax {√ d, ξ } ,
where Õ absorbs the constants and Polylog terms.
Proof of Lemma C.4. By construction, we have ‖xτ‖ ≤ ‖φ/σ̂‖ ≤ 1 and by Lemma C.7, with probability 1− δ/3,
∥∥∥σV̂h+1 − σ̂h∥∥∥∞ = sups,a ∣∣∣σ2 V̂h+1 (s, a)− σ̂2h(s, a) ∣∣∣∣∣∣σV̂h+1(s, a) + σ̂h(s, a)∣∣∣ ≤ 1 2 ∥∥∥σ2 V̂h+1 − σ̂2h ∥∥∥ ∞ ≤ CH,d,κ √ 1 K
Therefore, when K ≥ 4C2H,d,κ, CH,d,κ √ 1 K ≤ 1/2 ≤ σV̂h+1(s τ h, a τ h)/2 and hence
|ητ | ≤ ∣∣∣∣∣∣ rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h)
σV̂h+1(s τ h, a τ h)− CH,d,κ K1/2
∣∣∣∣∣∣ ≤ 2 ∣∣∣∣∣∣ rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) σV̂h+1(s τ h, a τ h) ∣∣∣∣∣∣ ≤ 2 sup
V ∈[0,H], s′∼Ph(s,a)
∣∣∣∣r + V (s′)− (ThV ) (s, a)σV (s, a) ∣∣∣∣ := ξ.
Next, note V̂h+1 is estimated using the transition from h + 1 to H and σ̂h is estimated using independent episodes D′, therefore conditional on V̂h+1, we receive Var [ητ |Fτ−1] =Var [ ητ |sτh, aτh, V̂h+1 ] = Var [ rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ∣∣∣sτh, aτh, V̂h+1]
σ̂2(sτh, a τ h)
= VarV̂h+1(s
τ h, a τ h)
σ̂2(sτh, a τ h)
≤ 2VarV̂h+1(s
τ h, a τ h)
σ2 V̂h+1 (sτh, a τ h)
≤ 2
where the first inequality is by Lemma C.7 and the second one is by definition of σh,V (s, a)
2 := max{1,VarPh(V )(s, a)}. Thus, by Bernstein inequality for self-normalized martingale (Lemma H.3),10 with probability 1− δ,∥∥∥∥∥ K∑ τ=1 xτητ ∥∥∥∥∥ Λ̂−1 ≤ 16 √ d log ( 1 + K λd ) · log ( 4K2 δ ) + 4ξ log ( 4K2 δ ) ≤ Õmax {√ d, ξ }
where Õ absorbs the constants and Polylog terms.
RecallM1,M2,M3,M4 in List A. Based on the above results, we have the following key lemma: Lemma C.5. Assume K > max{M1,M2,M3,M4}, for any 0 < λ < κ, suppose √ d > ξ,
where ξ := supV ∈[0,H], s′∼Ph(s,a), h∈[H] ∣∣∣∣ rh+V (s′)−(ThV )(s,a)σV (s,a) ∣∣∣∣. Then with probability 1− δ, for all
h, s, a ∈ [H]× S ×A,∣∣∣(ThV̂h+1 − T̂hV̂h+1)(s, a)∣∣∣ ≤ Õ(√d√φ(s, a)Λ−1h φ(s, a))+ 2H3√dK , where Λh = ∑K τ=1 φ(s τ h, a τ h) >φ(sτh, a τ h)/σ
2 V̂h+1 (sτh, a τ h)+λI and Õ absorbs the universal constants
and Polylog terms.
Proof of Lemma C.5. Combing equation 8, Lemma C.2, equation 9, Lemma C.3 and C.4 and a union bound to finish the proof.
10To be rigorous, Lemma H.3 needs to be modified since the absolute value bound and the variance bound here are in the high probability sense. However, this will not affect the validity of the result as the weaker version can also be obtained (see Chung and Lu (2006) and a related discussion in Yin et al. (2021) Remark E.7.) To make the proof more readable, we do not include them here to avoid over-technicality.

heading: C.3 PROOF OF THE FIRST PART OF THEOREM 3.2
text: Theorem C.6 (First part of Theorem 3.2). Let K be the number of episodes. Suppose √ d > ξ, where
ξ := supV ∈[0,H], s′∼Ph(s,a), h∈[H] ∣∣∣∣ rh+V (s′)−(ThV )(s,a)σV (s,a) ∣∣∣∣ and K > max{M1,M2,M3,M4}11.
Then for any 0 < λ < κ, with probability 1 − δ, for all policy π simultaneously, the output π̂ of Algorithm 1 satisfies
vπ − vπ̂ ≤ Õ ( √ d ·
H∑ h=1 Eπ [( φ(·, ·)>Λ−1h φ(·, ·) )1/2]) + 2H4 √ d K
where Λh = ∑K τ=1 φ(sτh,a τ h)·φ(s τ h,a τ h) >
σ2 V̂h+1(s τ h ,aτ h )
+ λId and Õ absorbs the universal constants and the Polylog
terms.
Proof of Theorem C.6. Combing Lemma C.1 and Lemma C.5, we directly have with probability 1− δ, for all policy π simultaneously,
V π1 (s)− V π̂1 (s) ≤ Õ
( √ d ·
H∑ h=1 Eπ [( φ(·, ·)>Λ−1h φ(·, ·) )1/2∣∣∣s1 = s])+ 2H4√d K , (11)
now take the initial distribution d1 on both sides to get the stated result.

heading: C.4 TWO INTERMEDIATE RESULTS
text: The next two lemmas provide intermediate results in finishing the whole proofs.

heading: C.4.1 BOUNDING THE VARIANCE
text: Lemma C.7. Recall the definition σ̂h(·, ·)2 = max{1, V̂arPh V̂h+1(·, ·)} + 1 and σV̂h+1(·, ·) 2 := max{1,VarPh V̂h+1(·, ·)} + 1. Moreover, [ V̂arhV̂h+1 ] (·, ·) = 〈 φ(·, ·), β̄h 〉 [0,(H−h+1)2] −[〈
φ(·, ·), θ̄h 〉
[0,H−h+1] ]2 (where β̄h and θ̄h are defined in Algorithm 1). Let K ≥ max { 512(1/κ)2 log ( 4Hd δ ) , 4λ/κ } , then with probability 1− δ,
sup h ||σ̂2h − σ2V̂h+1 ||∞ ≤ 12
√ H4d
κK log
( (λ+K)H
λδ
) + 12λ H2 √ d
κK .
Proof. Step1: we first show for all h, s, a ∈ [H]× S ×A, with probability 1− δ∣∣∣〈φ(s, a), β̄h〉[0,(H−h+1)2] − Ph(V̂h+1)2(s, a)∣∣∣ ≤ 4 √ H4d
κK log
( (λ+K)H
λδ
) + 4λ H2 √ d
κK .
Proof of Step1. Note∣∣∣〈φ(s, a), β̄h〉[0,(H−h+1)2] − Ph(V̂h+1)2(s, a)∣∣∣ ≤ ∣∣∣〈φ(s, a), β̄h〉 − Ph(V̂h+1)2(s, a)∣∣∣ =
∣∣∣∣∣φ(s, a)>Σ̄−1h K∑ τ=1 φ(s̄τh, ā τ h) · V̂h+1(s̄τh+1)2 − Ph(V̂h+1)2(s, a) ∣∣∣∣∣ =
∣∣∣∣∣φ(s, a)>Σ̄−1h K∑ τ=1 φ(s̄τh, ā τ h) · V̂h+1(s̄τh+1)2 − φ(s, a)> ∫ S (V̂h+1) 2(s′)dνh(s ′) ∣∣∣∣∣ =
∣∣∣∣∣φ(s, a)>Σ̄−1h K∑ τ=1 φ(s̄τh, ā τ h) · V̂h+1(s̄τh+1)2 − φ(s, a)>Σ̄−1h ( K∑ τ=1 φ(s̄τh, ā τ h)φ(s̄ τ h, ā τ h) > + λI) ∫ S (V̂h+1) 2(s′)dνh(s ′) ∣∣∣∣∣ ≤
∣∣∣∣∣φ(s, a)>Σ̄−1h K∑ τ=1 φ(s̄τh, ā τ h) · ( V̂h+1(s̄ τ h+1) 2 − Ph(V̂h+1)2(s̄τh, āτh) )∣∣∣∣∣︸ ︷︷ ︸
1
+λ ∣∣∣∣φ(s, a)>Σ̄−1h ∫ S (V̂h+1) 2(s′)dνh(s ′) ∣∣∣∣︸ ︷︷ ︸ 2
11The definition ofMi is in List A.
For 2 , since K ≥ max { 512(1/κ)2 log (
4Hd δ
) , 4λ/κ } , by Lemma H.6 and a union bound over
h ∈ [H], with probability 1− δ for all h, s, a ∈ [H]× S ×A,
2 ≤λ ‖φ(s, a)‖Σ̄−1h ∥∥∥∥∫ S (V̂h+1) 2(s′)dνh(s ′) ∥∥∥∥ Σ̄−1h
≤λ 2√ K ‖φ(s, a)‖(Σph)−1 2√ K ∥∥∥∥∫ S (V̂h+1) 2(s′)dνh(s ′) ∥∥∥∥ (Σph) −1 ≤ 4λ ∥∥(Σph)−1∥∥ H2√dK ≤ 4λH2 √ d κK .
(12)
For 1 , we have
1 ≤ ‖φ(s, a)‖Σ̄−1h ∥∥∥∥∥ K∑ τ=1 φ(s̄τh, ā τ h) · ( V̂h+1(s̄ τ h+1) 2 − Ph(V̂h+1)2(s̄τh, āτh) )∥∥∥∥∥
Σ̄−1h
(13)
Note V̂h+1 leverages the random transition from time t+ 1 to H , therefore conditional on V̂h+1, the transitions (s̄τh, ā τ h, s̄ τ h+1) are conditional independent w.r.t to different τ . Thus, define xτ = φ(s̄ τ h, ā τ h) (‖φ‖2 ≤ 1) and ητ = V̂h+1(s̄τh+1)2−Ph(V̂h+1)2(s̄τh, āτh) is H2-subgaussian, by Lemma H.2 (where t = K and L = 1) with probability 1− δ,12
P ∥∥∥∥∥ K∑ τ=1 φ(s̄τh, ā τ h) · ( V̂h+1(s̄ τ h+1) 2 − Ph(V̂h+1)2(s̄τh, āτh) )∥∥∥∥∥
Σ̄−1 h
≤ √ 8H4 · d
2 log
( λ+K
λδ )∣∣∣∣∣∣V̂h+1  ≥ 1−δ.
DenoteA := {∥∥∥∑Kτ=1 φ(s̄τh, āτh) · (V̂h+1(s̄τh+1)2 − Ph(V̂h+1)2(s̄τh, āτh))∥∥∥
Σ̄−1h
≤ √ 8H4 · d2 log ( λ+K λδ )} ,
then P(A) = E[1(A)] = E[E[1(A)|V̂h+1]] = E[P(A|V̂h+1)] ≥ E[1 − δ] = 1 − δ. Apply a union bound for h ∈ [H], we have with probability 1− δ, for all h ∈ [H],∥∥∥∥∥ K∑ τ=1 φ(s̄τh, ā τ h) · ( V̂h+1(s̄ τ h+1) 2 − Ph(V̂h+1)2(s̄τh, āτh) )∥∥∥∥∥
Σ̄−1h
≤ √ 4H4d log ( (λ+K)H
λδ
) (14)
and similar to 2 , with probability 1− δ for all h, s, a ∈ [H]× S ×A,
‖φ(s, a)‖Σ̄−1h ≤ 2 ∥∥(Σph)−1∥∥1/2√ K ≤ 2√ κK . (15)
Combing equation 12, equation 13, equation 14 and equation 15 we obtain with probability 1− δ for all h, s, a ∈ [H]× S ×A,
∣∣∣〈φ(s, a), β̄h〉[0,(H−h+1)2] − Ph(V̂h+1)2(s, a)∣∣∣ ≤ 4 √ H4d
κK log
( (λ+K)H
λδ
) + 4λ H2 √ d
κK .
Step2: we show for all h, s, a ∈ [H]× S ×A, with probability 1− δ ∣∣∣〈φ(s, a), θ̄h〉[0,H−h+1] − Ph(V̂h+1)(s, a)∣∣∣ ≤ 4 √ H2d
κK log
( (λ+K)H
λδ
) + 4λ H √ d
κK . (16)
The proof of Step2 follows nearly the identical way as Step1 except V̂ 2h is replaced by V̂h. Step3: We prove suph||σ̂2h − σ2V̂h ||∞ ≤ 12 √ H4d κK log ( (λ+K)H λδ ) + 12λH 2 √ d κK .
12Note similar technique is applied in Cai et al. (2020) Lemma D.1.
Proof of Step3. By equation 16,∣∣∣[〈φ(·, ·), θ̄h〉[0,H−h+1]]2 − [Ph(V̂h+1)(s, a)]2∣∣∣ = ∣∣∣〈φ(s, a), θ̄h〉[0,H−h+1] + Ph(V̂h+1)(s, a)∣∣∣ · ∣∣∣〈φ(s, a), θ̄h〉[0,H−h+1] − Ph(V̂h+1)(s, a)∣∣∣ ≤2H · ∣∣∣〈φ(s, a), θ̄h〉[0,H−h+1] − Ph(V̂h+1)(s, a)∣∣∣ ≤ 8 √ H4d
κK log
( (λ+K)H
λδ
) + 8λ H2 √ d
κK .
Combining this with Step1 we receive ∀h, s, a ∈ [H]× S ×A, with probability 1− δ∣∣∣∣V̂arhV̂h+1(s, a)−VarPh V̂h+1(s, a)∣∣∣∣ ≤ 12 √ H4d
κK log
( (λ+K)H
λδ
) + 12λ H2 √ d
κK .
Finally, by the non-expansiveness of operator max{1, ·}+ 1, we have the stated result.
C.4.2 A CRUDE BOUND ON suph||V ?h − V̂h||∞.
Lemma C.8. Define σ̂h(s, a) = √ max { 1, V̂arPh V̂h+1(s, a) } + 1, if K ≥
max{M1,M2,M3,M4} and K > C ·H4κ2, then with probability at least 1− δ,
sup h ∥∥∥V ?h − V̂h∥∥∥∞ ≤ Õ ( H2 √ d√ κK ) .
Proof. Step1: We show with probability at least 1− δ, suph ∥∥V ?h − V π̂h ∥∥∞ ≤ Õ (H2√d√κK ).
Indeed, combing Lemma C.1 and Lemma C.5, similar to the proof of Theorem C.6, we directly have with probability 1− δ, for all policy π simultaneously, and for all s ∈ S, h ∈ [H]
V πh (s)− V π̂h (s) ≤ Õ
( √ d ·
H∑ t=h Eπ [( φ(·, ·)>Λ−1t φ(·, ·) )1/2∣∣∣sh = s])+ 2H4√d K , (17)
Next, since K ≥ max { 512(1/κ)2 log (
4Hd δ
) , 4λ/κ } , by Lemma H.6 and a union bound over
h ∈ [H], with probability 1− δ
sup s,a ‖φ(s, a)‖Λ̂−1h ≤ 2√ K sup s,a ‖φ(s, a)‖Λp−1h ≤ 2H√ κK , ∀h ∈ [H].
Lastly, taking π = π? in equation 17 to obtain
0 ≤ V π ?
h (s)− V π̂h (s) ≤Õ
( √ d ·
H∑ t=h Eπ? [( φ(·, ·)>Λ−1t φ(·, ·) )1/2∣∣∣sh = s])+ 2H4√d K
≤Õ ( H2 √ d√
κK
) + 2H4 √ d
K .
(18)
This implies by using the condition K > C ·H4κ2, we finish the proof of Step1. Step2: We show with probability 1− δ, suph ∥∥∥V̂h − V π̂h ∥∥∥∞ ≤ Õ (H2√d√κK ).
Indeed, applying Extended Value Difference Lemma H.7 for π = π′ = π̂, then with probability 1− δ, for all s, h ∣∣∣V̂h(s)− V π̂h (s)∣∣∣ = ∣∣∣∣∣ H∑ t=h Eπ̂ [ Q̂h(sh, ah)− ( ThV̂h+1 ) (sh, ah) ∣∣∣sh = s] ∣∣∣∣∣
≤ H∑ t=h ∥∥∥(T̂hV̂h+1 − ThV̂h+1)(s, a)∥∥∥+ ‖Γh(s, a)‖ ≤Õ ( H √ d ∥∥∥∥√φ(s, a)Λ−1h φ(s, a)∥∥∥∥)+ 4H4 √ d
K ≤ Õ
( H2 √ d√
κK
)
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 a union bound we finish the proof of the lemma.
Remark C.9. Note as an intermediate calculation, equation 18 ensures a learning bound with order Õ(H 2 √ d√
κK ). Here, the convergence rate is the standard statistical rate 1√ K and the H2 dependence is loose. However, the feature dependence √ d/κ is roughly tight, since, in the well-explored case
(Assumption 2 of Wang et al. (2021a)), κ = 1/d and the √ d/κ = √ d2 recovers the optimal feature dependence dH √ T in the online setting (Zhou et al., 2021). If κ 1/d, then doing offline learning requires sample size proportional to d/κ, 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 if the sample/episode size K →∞.

heading: C.5 PROOF OF THE SECOND PART OF THEOREM 3.2
text: Lemma C.10. Recall σ̂h = √ max { 1, V̂arPh V̂h+1 } + 1 and σ?h = √ max { 1,VarPhV ? h+1 } + 1.
Let K ≥ max { 512(1/κ)2 log (
4Hd δ
) , 4λ/κ } and K ≥ max{M1,M2,M3,M4}, then with prob-
ability 1− δ,
sup h ||σ̂2h − σ?2h ||∞ ≤ Õ
( H3 √ d√
κK
) .
Proof. By definition and the non-expansiveness of max{1, ·}+ 1, we have∥∥∥σ2 V̂h+1 − σ?2h ∥∥∥ ∞ ≤ ∥∥∥VarV̂h+1 −VarV ?h+1∥∥∥∞
≤ ∥∥∥Ph (V̂ 2h+1 − V ?2h+1)∥∥∥∞ + ∥∥∥(PhV̂h+1)2 − (PhV ?h+1)2∥∥∥∞ ≤ ∥∥∥V̂ 2h+1 − V ?2h+1∥∥∥∞ + ∥∥∥(PhV̂h+1 + PhV ?h+1)(PhV̂h+1 − PhV ?h+1)∥∥∥∞ ≤2H ∥∥∥V̂h+1 − V ?h+1∥∥∥∞ + 2H ∥∥∥PhV̂h+1 − PhV ?h+1∥∥∥∞ ≤ Õ ( H3 √ d√
κK
) .
with probability 1− δ for all h ∈ [H], 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 C1 = max{2λ, 128 log(2d/δ), 128H4 log(2d/δ)/κ2} and C2 = max{ λ 2 κ log((λ+K)H/λδ) , 96 2H12d log((λ + K)H/λδ)/κ5}. Suppose the number of episode K satisfies K > max{C1, C2}, then with probability 1− δ,√ φ(s, a)Λ−1h φ(s, a) ≤ 2 √ φ(s, a)Λ?−1h φ(s, a), ∀s, a ∈ S ×A,
Proof of Lemma C.11. By definition √ φ(s, a)Λ−1h φ(s, a) = ‖φ(s, a)‖Λ−1h . Then denote
Λ′h = 1
K Λh, Λ
?′ h = 1
K Λ?h,
where Λh = ∑K τ=1 φ(s τ h, a τ h) >φ(sτh, a τ h)/σ 2 V ?h+1 (sτh, a τ h) + λI . Under the condition of K, by Lemma C.10, with probability 1− δ∥∥∥Λ?′h − Λ′h∥∥∥ ≤ sup s,a ∥∥∥∥∥φ(s, a)φ(s, a)>σ?2h (s, a) − φ(s, a)φ(s, a) >
σ2 V̂h+1 (s, a) ∥∥∥∥∥ ≤ sup
s,a
∣∣∣∣∣σ ?2 h (s, a)− σ2V̂h+1(s, a)
σ?2h (s, a)σ 2 V̂h+1 (s, a)
∣∣∣∣∣ · ‖φ(s, a)‖2 ≤ sups,a ∣∣∣∣∣σ ?2 h (s, a)− σ2V̂h+1(s, a) 1 ∣∣∣∣∣ · 1 ≤ Õ ( H3 √ d√
κK
) .
(19)
Next by Lemma H.5 (with φ to be φ/σV ?h+1 and C = 1), it holds with probability 1− δ,∥∥∥∥Λ?′h − (Eµ,h[φ(s, a)φ(s, a)>/σ2V ?h+1(s, a)] + λK Id )∥∥∥∥ ≤ 4√2√K ( log 2d δ )1/2 .
Therefore by Weyl’s spectrum theorem and the condition K > max{2λ, 128 log(2d/δ), 128H4 log(2d/δ)/κ2}, the above implies∥∥∥Λ?′h ∥∥∥ =λmax(Λ?′h ) ≤ λmax (Eµ,h[φ(s, a)φ(s, a)>/σ2V ?h+1(s, a)])+ λK + 4 √ 2√ K ( log 2d δ
)1/2 ≤ ∥∥∥Eµ,h[φ(s, a)φ(s, a)>/σ2V ?h+1(s, a)]∥∥∥+ λK + 4 √ 2√ K ( log 2d δ
)1/2 ≤‖φ(s, a)‖2 + λ
K +
4 √
2√ K
( log 2d
δ
)1/2 ≤ 1 + λ
K +
4 √
2√ K
( log 2d
δ
)1/2 ≤ 2,
λmin(Λ ?′ h ) ≥λmin ( Eµ,h[φ(s, a)φ(s, a)>/σ2V ?h+1(s, a)] ) + λ K − 4 √ 2√ K ( log 2d δ )1/2 ≥λmin ( Eµ,h[φ(s, a)φ(s, a)>/σ2V ?h+1(s, a)] ) − 4 √ 2√ K ( log 2d δ
)1/2 ≥ κ H2 − 4 √ 2√ K ( log 2d δ )1/2 ≥ κ 2H2 .
Hence with probability 1 − δ, ∥∥∥Λ?′h ∥∥∥ ≤ 2 and ∥∥∥Λ?′−1h ∥∥∥ = 1/λmin(Λ?′h ) ≤ 2H2/κ. Similarly,∥∥∥Λ′−1h ∥∥∥ ≤ 2H2/κ with high probability.
Now apply Lemma H.4 to Λ? ′ h and Λ ′ h and a union bound, we obtain with probability 1− δ, for all s, a
‖φ(s, a)‖Λ′−1h ≤ [ 1 + √∥∥Λ?′−1h ∥∥ ∥∥Λ?′h ∥∥ · ∥∥Λ′−1h ∥∥ · ∥∥Λ?′h − Λ′h∥∥] · ‖φ(s, a)‖Λ?′−1h ≤ [ 1 + √ 2H2
κ · 1 · 2H
2 κ · ∥∥Λ?′h − Λ′h∥∥
] · ‖φ(s, a)‖
Λ? ′−1 h
≤ 1 + √√√√H4
κ2
[ Õ ( H3 √ d√
κK
)] · ‖φ(s, a)‖ Λ? ′−1 h ≤ 2 ‖φ(s, a)‖ Λ? ′−1 h
where the third inequality uses equation 19 and the last inequality uses K > max{ λ 2
κ log((λ+K)H/λδ) , 96 2H12d log((λ+K)H/λδ)/κ5}. The claimed result follows straightfor-
wardly by multiplying 1/ √ K on both sides of the above.
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 π = π?, then with probability 1− δ,
vπ ? − vπ̂ ≤ Õ ( √ d ·
H∑ h=1 Eπ? [( φ(·, ·)>Λ−1h φ(·, ·) )1/2]) + 2H4 √ d K ,
Now apply Lemma C.11 and a union bound, with probability 1− δ,
0 ≤ v? − vπ̂ ≤ Õ ( √ d ·
H∑ h=1 Eπ? [( φ(·, ·)>Λ?−1h φ(·, ·) )1/2]) + 2H4 √ d K .

heading: D PROOF OF THEOREM 3.3
text: First of all, we show the following lemma.
Lemma D.1. Suppose K > max{M1,M2,M3,M4}. Plug ΓIh(s, a)← φ(s, a)> ∣∣∣∣∣∣Λ̂−1h K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( T̂hV̂h+1 ) (sτh, a τ h) ) σ̂2h(s τ h, a τ h) ∣∣∣∣∣∣+Õ(H 3d/κ K )
in Algorithm 1 and let Th be the Bellman operator and T̂h be the approximated Bellman operator. Then we have with probability 1− δ:
|(ThV̂h+1 − T̂hV̂h+1)(s, a)| ≤ Γh(s, a) ∀s, a ∈ S ×A.
Proof of Lemma D.1. Suppose wh is the coefficient corresponding to the ThV̂h+1 (such wh exists by Lemma H.9), i.e. ThV̂h+1 = φ>wh, and recall (T̂hV̂h+1)(s, a) = φ(s, a)>ŵh, then:( ThV̂h+1 ) (s, a)− ( T̂hV̂h+1 ) (s, a) = φ(s, a)> (wh − ŵh)
=φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 )) /σ̂2h(s τ h, a τ h) )
=φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( ThV̂h+1 ) (sτh, a τ h) /σ̂ 2 h(s τ h, a τ h) ) ︸ ︷︷ ︸
(i)
+ φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( T̂hV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ) ︸ ︷︷ ︸
(ii)
+ φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · (( T̂hV̂h+1 ) (sτh, a τ h)− ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ) ︸ ︷︷ ︸
(iii)
(20)
For term (i), by Lemma C.2 it is bounded by 2λH 3 √ d/κ
K with probability 1− δ/2. 13
For term (ii), it is bounded by
φ(s, a)> ∣∣∣∣∣∣Λ̂−1h K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( T̂hV̂h+1 ) (sτh, a τ h) ) σ̂2h(s τ h, a τ h) ∣∣∣∣∣∣ . For term (iii), by Cauchy inequality
φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · (( T̂hV̂h+1 ) (sτh, a τ h)− ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) )
≤‖φ(s, a)‖Λ̂−1h · ∥∥∥∥∥ K∑ τ=1 φ (sτh, a τ h) · (( T̂hV̂h+1 ) (sτh, a τ h)− ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ∥∥∥∥∥ Λ̂−1h
≤ 2H√ κK · ∥∥∥∥∥ K∑ τ=1 φ (sτh, a τ h) · (( T̂hV̂h+1 ) (sτh, a τ h)− ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ∥∥∥∥∥ Λ̂−1h
≤ 2H√ κK · Õ( H2 √ d/κ√ K ) · √ d = Õ( H3d/κ K )
where the first inequality is by Lemma H.6 (with φ′ = φ/σ̂h and ‖φ/σ̂h‖ ≤ ‖φ‖ ≤ 1 := C) and the third inequality uses √ a> ·A · a ≤ √ ‖a‖2 ‖A‖2 ‖a‖2 = ‖a‖2 √ ‖A‖2 with a to be either φ or wh. Moreover, λmin(Λ̃ p h) ≥ κ/maxh,s,a σ̂h(s, a)2 ≥ κ/H2 implies
∥∥∥(Λ̃ph)−1∥∥∥ ≤ H2/κ. The second inequality is true by denoting xτ = φ(sτh, a τ h)/σ̂(s τ h, a τ h) and
ητ = (( T̂hV̂h+1 ) (sτh, a τ h)− ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂h(s τ h, a τ h)
and use Lemma H.10 as the condition for applying Lemma H.2. By collecting those three terms together we have the result.

heading: D.1 PROOF OF THEOREM 3.3
text: Proof. Use Lemma D.1 as the condition for Lemma C.1 and average over initial distribution d1, we obtain with probability 1− δ,
v? − vπ̂ ≤ H∑ h=1 Eπh [φ(s, a)] > ∣∣∣∣∣∣Λ̂−1h K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( T̂hV̂h+1 ) (sτh, a τ h) ) σ̂2h(s τ h, a τ h) ∣∣∣∣∣∣+ Õ(H 4d/κ K )
(21) Denote Ah := ∑K τ=1 φ(sτh,a τ h)·(r τ h+V̂h+1(s τ h+1)−(ThV̂h+1)(s τ h,a τ h))
σ̂2h(s τ h,a τ h)
, then
Eπh [φ(s, a)] > ∣∣∣∣∣∣Λ̂−1h K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( T̂hV̂h+1 ) (sτh, a τ h) ) σ̂2h(s τ h, a τ h) ∣∣∣∣∣∣ ≤Eπh [φ] > · ∣∣∣Λ̂−1h Ah∣∣∣+ Eπh [φ]> ∣∣∣∣∣∣Λ̂−1h K∑ τ=1 φ (sτh, a τ h) · ( ThV̂h+1 (sτh, aτh)− T̂hV̂h+1 (sτh, aτh) ) σ̂2h(s τ h, a τ h)
∣∣∣∣∣∣ 13Note Here Lemma C.2 still applies even if the Γh changes since it works for all V̂h ∈ [0, H] so that
‖wh‖2 ≤ 2H √ d and the truncation (Line 13 in Algorithm 1) guarantees this.
For the second term, it can be bounded similar to term (iii) in Lemma D.1 and for the first term by Cauchy’s inequality it is bounded by
‖Eπh [φ]‖Λ̂−1h · ‖Ah‖Λ̂−1h ≤ Õ( √ d) ‖Eπh [φ]‖Λ̂−1h ≤ Õ( √ d ‖Eπh [φ]‖Λ−1h )
where the first inequality is identical to the analysis in Section C.2.2 and the second inequality is identical to the analysis in Section C.2.1 with φ replaced by E[φ]. Plug this back to equation 21 we finish the proof for the first part. For the second part, converting Λ−1h to Λ ?−1 h is identical to Section C.5. This finishes the proof.

heading: E PROOF OF MINIMAX LOWER BOUND THEOREM 3.5
text: The proof follows the lower bound proof of Zanette et al. (2021). For completeness, we provide all the details in below.

heading: E.1 CONSTRUCTION
text: Similar to the proof of [Zanette et al. (2021), Theorem 2], we construct a family of MDPs, each parameterized by a Boolean vector u = (u1, . . . , uH) with each uh ∈ {−1,+1}d−2 for h ∈ [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−2. Feature map: The feature map φ : S ×A 7→ Rd is given by
φ(+1, a) =  a√2d1√ 2
0
 ∈ Rd, φ(−1, a) =  a√2d0
1√ 2  ∈ Rd. The construction ensures the condition ‖φ(s, a)‖2 ≤ 1 for any (s, a) ∈ S ×A.
Transition kernel: The transition probability Ph(s′ | s, a) is independent of action a. In other words, the Markov decision process reduces to a homogeneous Markov chain with transition matrix
P =
( 1 2 1 2
1 2 1 2
) ∈ R2.
By letting
νh(+1) = νh(−1) = 0d−21√ 2
1√ 2  ∈ Rd, we have Ph(s′ | s, a) = 〈φ(s, a), νh(s′)〉 to be a valid probability transition.
Reward observations: For any MDP Mu, at each times step h, the reward follows a Gaussian distribution with
Ru,h(s, a) ∼ N ( s√ 6 + δ√ 2d 〈a, uh〉, 1 ) ,
where δ ∈ [ 0, 1√
3d
] determines to what extent the MDP models are different from each
other. The mean reward function satisfies ru,h(s, a) = 〈φ(s, a), θu,h〉 with
θu,h =  δuh1√ 3
− 1√ 3  ∈ Rd. Offline data collection Scheme: The dataset D = {(sτh, aτh, rτh, sτh+1)} h∈[H] τ∈[K] consist of K i.i.d.
trajectories. All the trajectories initiate from uniform distribution. We take a behavior policy µ(· | s) that is independent of state s. Let {e1, e2, . . . , ed−2} be the canonical bases of Rd−2 and 0d−2 ∈ Rd−2 be the zero vector. The behavior policy µ is set as
µ(ej | s) = 1d for any j ∈ [d− 2] and µ(0d−2 | s) = 2 d .

heading: E.2 OVERVIEW OF PROOF
text: The proof of the theorem is based on Assouad’s method, where we first reduce the problem to binary hypothesis tests (Lemmas E.1 and E.2) and then connect the testing error to the uncertainty quantity in the upper bound (Lemma E.3). Lemma E.1 (Reduction to testing). There exists a universal constant c1 > 0 such thata
inf π̂ max u∈U
Eu [ V ?u − V π̂u ] ≥ c1 δ √ dH min
u,u′∈U :DH(u′;u)=1 inf ψ
[ Pu(ψ 6= u) + Pu′(ψ 6= u′) ] , (22)
where π̂ denotes the output of any algorithm that maps from observations to an estimated policy. ψ is any test function for parameter u and DH is the hamming distance.
Lemma E.2. There exists a universal constant c2 > 0 such that when taking δ := c2 d√K , we have
min u,u′∈U :DH(u′;u)=1 inf ψ
[ Pu(ψ 6= u) + Pu′(ψ 6= u′) ] ≥ 1
2 . (23)
When K & d3, δ := c2 d√ K
ensures that δ ≤ 1/ √
3d. Combining Lemmas E.1 and E.2 yields a lower bound
inf π̂ max u∈U
Eu [ V ?u − V π̂u ] ≥ c d √ dH√ K , (24)
where c > 0 is a universal constant. We then use the following Lemma E.3 to connect the above lower bound to the uncertainty term √ d · ∑H h=1 √ Eπ? [φ]>(Λ?h)−1Eπ? [φ] for the chosen linear MDP instances classM. Lemma E.3. There exists a universal constant c3 > 0 such that for all M ∈M,
H∑ h=1 √ Eπ? [φ]>(Λ?h)−1Eπ? [φ] ≤ c3 dH√ K . (25)
Plugging inequality equation E.3 into the bound equation 24, we obtain the minimax lower bound equation 5 in the statement of theorem.

heading: E.3 REDUCTION TO TESTING VIA ASSOUAD’S METHOD
text: Proof of Lemma E.1. For any index vector u = (u1, . . . , uH) ∈ U = {−1,+1}(d−2)×H , the optimal policy for MDP instance Mu is simply
π?h(·) = uh for h ∈ [H]. Similar to the proof of Lemma 9 in Zanette et al. (2021), we can show that the value suboptimality of policy π on MDP Mu is given by
V ?u − V πu = δ√ 2d H∑ h=1 ∥∥uh − Eπ[ah]∥∥1. Define uπ = (uπ1 , . . . , u π H) with u π h := sign ( Eπ[ah]
) , then the `1-norm is lower bounded as∥∥uh − Eπ[ah]∥∥1 ≥ DH(uπh;uh),
where DH(·; ·) denotes the Hamming distance. It follows that
V ?u − V πu ≥ δ√ 2d DH(u π;u). (26)
We then apply Assouad’s method (Lemma 2.12 in Sampson and Guttorp (1992)) and obtain that
inf û∈U max u∈U
Eu [ DH(û;u) ] ≥ (d− 2)H
2 min u,u′∈U :DH(u′;u)=1 inf ψ
[ Pu(ψ 6= u) + Pu′(ψ 6= u′) ] , (27)
where ψ is any test functions mapping from observations to {u, u′}. Combining inequalities equation 26 and equation 27, we finish the proof.

heading: E.4 LOWER BOUND ON THE TESTING ERROR
text: 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 KullbackLeibler divergence and obtain
min u,u′∈U :DH(u′;u)=1 inf ψ
[ Pu(ψ 6= u) + Pu′(ψ 6= u′) ] ≥ 1− ( 1 2 maxu,u′∈U :DH(u′;u)=1 DKL(Qu‖Qu′) )1/2 .
(28)
It only remains to estimate DKL(Qu‖Qu′). The probability density Qu takes the form
Qu(D) = K∏ k=1 ξ1(s k 1) H∏ h=1 µ ( akh | skh) [ Ru,h(s k h, a k h) ] (rkh) Ph(skh+1 | skh, akh)
where ξ1 = [ 1 2 , 1 2 ] is the initial distribution. It follows that
DKL(Qu‖Qu′) = Eu [ log(Qu/Qu′) ]
= K · H∑ h=1 Eu [ log ([ Ru,h(s 1 h, a 1 h) ] (r1h) /[ Ru′,h(s 1 h, a 1 h) ] (r1h) )] = K
d d−2∑ j=1 DKL ( N ( δ√ 2d 〈ej , uh〉, 1 ) ∥∥∥ N ( δ√ 2d 〈ej , u′h〉, 1 )) .
If we take δ = c2 d√ K , then inequality equation 28 ensures inequality equation 23, as claimed in the statement of the lemma.

heading: E.5 CONNECTION TO THE UNCERTAINTY TERM
text: Proof of Lemma E.3. We first calculate the explicit form of the inverse of variance-rescaled covariance matrix Λ?,ph . For each time step h ∈ [H], the value function V ?u,h+1 takes the form
V ?u,h+1 = Eπ?ru,h+1 + ( Pπ ? h+1V ? u,h+2 ) .
Since ( Ph+1V ?u,h+2 ) (+1) = ( Ph+1V ?u,h+2 ) (−1) and ru,h+1(+1, a)− ru,h+1(−1, a) = 2/ √ 6, we have
VarPh(V ? u,h+1)(+1, a) = VarPh(Eπ?ru,h+1)(+1, a) =
1 6 .
Similarly,
VarPh(V ? u,h+1)(−1, a) = VarPh(V ?u,h+1)(+1, a) =
1 6 .
By routine calculation, we find that the population-level rescaled covariance matrix takes the form
Λ?,ph = 3K
2
( 2 d2 Id−2
1 d √ d 1(d−2)×2
1 d √ d 12×(d−2) I2
) ∈ Rd×d
for any h ∈ [H]. Applying Gaussian elimination on Λ?,ph , we have
(Λ?,ph ) −1 =
2
3K
d22 {Id−2 + 1d−21(d−2)×(d−2)} − d √ d 2(d−2)1(d−2)×2
− d √ d
2(d−2)12×(d−2) 1 d−2
( d− 1 1
1 d− 1
) .
For each time step h ∈ [H], we have (by Jensen’s inequality)√ Eπ? [φ]>(Λ?h)−1Eπ? [φ] ≤ 1
2 ∥∥φ(+1, uh)∥∥(Λ?,ph )−1 + 12∥∥φ(−1, uh)∥∥(Λ?,ph )−1 . Recall that by our construction,
φ(+1, uh) =  uh√2d1√ 2
0
 ∈ Rd, φ(−1, uh) =  uh√2d0
1√ 2  ∈ Rd. It follows that∥∥φ(+1, uh)∥∥2(Λ?,ph )−1 = ∥∥φ(−1, uh)∥∥2(Λ?,ph )−1
= 2
3K
{ d
4 u>h { Id−2 + 1 d−21(d−2)×(d−2) } uh −
d
2(d− 2) 1>d−2uh + d− 1 2(d− 2) } = 2
3K
{ d2
4 +
d 4(d− 2) ( 1− 1>d−2uh )2 + 1 4 } ≤ 2
3K
{ d2
4 + d(d− 1)2 4(d− 2) + 1 4
} = 2
3K
{ d2
2 + d− 1 2(d− 2)
} . d2/K.
Therefore, √ Eπ? [φ]>(Λ?h)−1Eπ? [φ] . d/ √ K.
Taking the summation over h ∈ [H], we obtain the bound equation 25 as claimed in the lemma statement.

heading: F A NUMERICAL SIMULATION

heading: F.1 A LINEAR MDP CONSTRUCTION
text: 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 use consists of |S| = 2 states and |A| = 100 actions, and feature dimension d = 100. We set S = {0, 1} and A = {0, 1, . . . , 99} respectively. For each action a ∈ {0, 1, . . . , 99}, we use binary encoding to obtain a vector a ∈ R8 using its binary representation (i.e. each coordinate is either 0 or 1). we interchangebly use a and and its vector representation a for the ease of explanation. We first define
δ(s, a) = { 1 if 1{s = 0} = 1{a = 0} 0 otherwise , then the non-stationary linear MDP is specified by the
following configuration
• Feature mapping: φ(s, a) = ( a>, δ(s, a), 1− δ(s, a) )> ∈ R10 • The true measure νh
νh(s) = (0, . . . , 0, (1− s)⊕ αh, s⊕ αh) ,
where {αh}h∈[H] is a sequence of integers taking values 0 or 1 and ⊕ is the standard XOR operator. We define
θh ≡ (0, . . . , 0, r, 1− r) ∈ R10
with the choice of r = 0.9. The transition follows Ph(s′|s, a) = 〈φ(s, a), νh(s′)〉 and the mean reward function rh(s, a) = 〈φ(s, a), θh〉. • Behavior policy: always choose action a = 0 with probability p, and other actions uniformly
with probability (1 − p)/99. The initial distribution chooses s = 0 and s = 1 with equal probability 1/2. We use p = 0.6.

heading: F.2 EMPIRICAL COMPARISON BETWEEN PEVI AND VAPVI ON THE CONSTRUCTED LINEAR
text: MDP
We compare Pessimistic Value Iteration (PEVI) in Jin et al. (2021b) and our VAPVI Algorithm 1 in Figure 1, with horizon to be H = 20, 30, 50. In addition, we add the non-pessimistic version for both algorithms, i.e. least-square value iteration (LSVI) and variance-aware value iteration (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 λ = 1 used in theory (Jin et 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 [ dH · ( φ(·, ·)>Σ−1h φ(·, ·) )1/2] is overly pessimistic comparing to our
O [√ d · ( φ(·, ·)>Λ−1h φ(·, ·) )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 σ̂h(·, ·)2 ← max{1, V̂arPh V̂h+1(·, ·)} so σ̂h(·, ·)2 will just be 1 when the estimated variance is 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.

heading: G SOME MISSING DERIVATIONS AND DISCUSSIONS

heading: G.1 REGARDING COVERAGE ASSUMPTION
text: Now we discuss the feature coverage assumption. Indeed, even if Assumption 2.2 is not satisfied, we can still learn in the effective subspan of Σph := Eµ,h [ φ(s, a)φ(s, a)> ] . Indeed, since Σph is symmetric, by orthogonal decomposition we have Σph = ZhΛZ > h , where Zh (can be estimated using the samples for practical purpose) consists of orthogonal basis and Λ consists of eigenvalues of Σph in the diagonal. Suppose we do not have a full coverage, i.e.
Λ = diag[λ1, λ2, ..., λd′ , 0, ..., 0] with d ′ < d,
then we can create transformed features φ′h(s, a) = Zh · φh(s, a), and then Eµ,h [ φ′h(s, a)φ ′ h(s, a) >] = Λ = diag[λ1, λ2, ..., λd′ , 0, ..., 0]. Then we can do learning w.r.t. the truncated features φ′h|1:d′ ’s only instead of the original φ. It reduces to the weaker notion of κ := minh∈[H]{κh : s.t. κh = smallest positive eigenvalue at time h}.

heading: G.2 DERIVATION OF EQUATION 4
text: When reducing Theorem 3.2,3.3 to the tabular case, set φ(s, a) = 1s,a, d = SA, λ = 0, and recall by Assumption 3.4 (let’s assume π? is a deterministic policy as it always exists in tabular MDP) C? := suph,s,a d π? h (s, a)/d µ h(s, a), then for Theorem 3.2
√ d · H∑ h=1 Eπ? [√ φ(·, ·)>Λ?−1h φ(·, ·) ] = √ d · H∑ h=1 ∑ s,a dπ ? h (s, a) √ 1>s,aΛ ?−1 h 1s,a
= √ SA · H∑ h=1 ∑ s,a dπ ? h (s, a)
√ 1>s,adiag { VarP·,·(V ? h+1)
nh,·,·
} 1s,a
= √ SA · H∑ h=1 ∑ s,a dπ ? h (s, a)
√ VarPs,a(V ? h+1)
nh,s,a nh,s,a := K∑ τ=1 1[sτh, a τ h = s, a]
. √ SA · H∑ h=1 ∑ s,a dπ ? h (s, a)
√ VarPs,a(V ? h+1)
K · dµh(s, a)
≤ √ SAC?/K · H∑ h=1 ∑ s,a √ dπ ? h (s, a)VarPs,a(V ? h+1) = √ SAC?/K ·
H∑ h=1 ∑ s √ dπ ? h (s, π ?(s))VarPs,π?(s)(V ? h+1)
≤ √ SAC?/K · H∑ h=1 √ S · ∑ s dπ ? h (s, π ?(s))VarPs,π?(s)(V ? h+1) ≤ √ S2AC?/K ·
√√√√H H∑ h=1 ∑ s dπ ? h (s, π ?(s))VarPs,π?(s)(V ? h+1)
= √ S2AC?/K · √√√√H · H∑ h=1 Eπ? h [VarP(·,·)(V ? h+1)] ≤ √ H3S2AC?/K
where the first inequality 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
√ d · H∑ h=1 √ Eπ? [φ]>Λ?−1h Eπ? [φ] = √ d · H∑ h=1 √ Vec{dπ?}Λ?−1h Vec{dπ ?}
= √ d · H∑ h=1
√ Vec{dπ?}diag { VarP·,·(V ? h+1)
nh,·,·
} Vec{dπ?}
= √ SA · H∑ h=1 √√√√∑ s,a dπ ? h (s, a) 2 VarPs,a(V ? h+1) nh,s,a
. √ SA · H∑ h=1 √√√√∑ s,a dπ ? h (s, a) 2 VarPs,a(V ? h+1) K · dµh(s, a) ≤ √ SAC?/K ·
H∑ h=1 √∑ s,a dπ ? h (s, a)VarPs,a(V ? h+1)
= √ SAC?/K · H∑ h=1 √∑ s dπ ? h (s, π ?(s))VarPs,π?(s)(V ? h+1) ≤ √ SAC?/K ·
√√√√H · H∑ h=1 Eπ? h [VarP(·,·)(V ? h+1)] ≤ √ H3SAC?/K.

heading: H AUXILIARY LEMMAS
text: Lemma H.1 (Matrix McDiarmid inequality / Matrix Chernoff bound (Tropp, 2012)). Let zk, k = 1, . . . ,K be independent random vectors in Rd, and let H be a mapping that maps K vectors to a d× d symmetric matrix. Assume there exists a sequence of fixed symmetric matrices {Ak}k∈[K] such that for zk, z′k ranges over all possible values for each k ∈ [K], it holds
(H(z1, . . . , zk, . . . , zK)−H(z1, . . . , z′k, . . . , zK))2 A2k. Define σ2 := ∥∥∑
k A 2 k ∥∥. Then for any t > 0, P {‖H(z1, . . . , zK)− EH(z1, . . . , zK)‖ ≥ t} ≤ d · exp ( −t2
8σ2 ) Lemma H.2 (Hoeffding inequality for self-normalized martingales (Abbasi-Yadkori et al., 2011)). Let {ηt}∞t=1 be a real-valued stochastic process. Let {Ft}∞t=0 be a filtration, such that ηt is Ftmeasurable. Assume ηt also satisfies ηt given Ft−1 is zero-mean and R-subgaussian, i.e.
∀λ ∈ R, E [ eληt | Ft−1 ] ≤ eλ 2R2/2
Let {xt}∞t=1 be an Rd-valued stochastic process where xt is Ft−1 measurable and ‖xt‖ ≤ L. Let Λt = λId + ∑t s=1 xsx
> s . Then for any δ > 0, with probability 1− δ, for all t > 0,∥∥∥∥∥ t∑ s=1 xsηs ∥∥∥∥∥ 2
Λ−1t
≤ 8R2 · d 2 log
( λ+ tL
λδ
) .
Lemma H.3 (Bernstein inequality for self-normalized martingales (Zhou et al., 2021)). Let {ηt}∞t=1 be a real-valued stochastic process. Let {Ft}∞t=0 be a filtration, such that ηt is Ft-measurable. Assume ηt also satisfies
|ηt| ≤ R,E [ηt | Ft−1] = 0,E [ η2t | Ft−1 ] ≤ σ2.
Let {xt}∞t=1 be an Rd-valued stochastic process where xt is Ft−1 measurable and ‖xt‖ ≤ L. Let Λt = λId + ∑t s=1 xsx
> s . Then for any δ > 0, with probability 1− δ, for all t > 0,∥∥∥∥∥ t∑ s=1 xsηs ∥∥∥∥∥ Λ−1t ≤ 8σ √ d log ( 1 + tL2 λd ) · log ( 4t2 δ ) + 4R log ( 4t2 δ ) Lemma H.4 (Converting the variance under the matrix norm). Let Λ1 and Λ2 ∈ Rd×d are two positive semi-definite matrices. Then:∥∥Λ−11 ∥∥ ≤ ∥∥Λ−12 ∥∥+ ∥∥Λ−11 ∥∥ · ∥∥Λ−12 ∥∥ · ‖Λ1 − Λ2‖ and
‖φ‖Λ−11 ≤ [ 1 + √∥∥Λ−12 ∥∥ ‖Λ2‖ · ∥∥Λ−11 ∥∥ · ‖Λ1 − Λ2‖] · ‖φ‖Λ−12 . for all φ ∈ Rd.
Proof. For the first part, note∥∥Λ−11 ∥∥ ≤ ∥∥Λ−12 ∥∥+ ∥∥Λ−11 − Λ−12 ∥∥ ≤ ∥∥Λ−12 ∥∥+ ∥∥Λ−12 ∥∥ ‖Λ1 − Λ2‖ ∥∥Λ−11 ∥∥ For the second one,
‖φ‖Λ−11 = √ φ>Λ−11 φ = √ φ> ( Λ−11 − Λ −1 2 ) φ+ φ>Λ−12 φ
= √ φ>Λ
−1/2 2
( Λ
1/2 2 Λ −1 1 Λ 1/2 2 − I + I ) Λ −1/2 2 φ ≤ √ ‖φ‖Λ−12 · ( 1 + ∥∥∥Λ1/22 Λ−11 Λ1/22 − I∥∥∥) ‖φ‖Λ−12 ≤ ( 1 + ∥∥∥Λ1/22 Λ−11 Λ1/22 − I∥∥∥1/2) · ‖φ‖Λ−12 = ( 1 +
∥∥∥Λ1/22 Λ−11 (Λ2 − Λ1) Λ−12 Λ1/22 ∥∥∥1/2) · ‖φ‖Λ−12 ≤ ( 1 + √ ‖Λ2‖ ∥∥Λ−11 ∥∥ ∥∥Λ−12 ∥∥ ‖Λ1 − Λ2‖) · ‖φ‖Λ−12
Lemma H.5 (Lemma H.4 of Min et al. (2021)). let φ : S × A → Rd satisfies ‖φ(s, a)‖ ≤ C for all s, a ∈ S × A. For any K > 0, λ > 0, define ḠK = ∑K k=1 φ(sk, ak)φ(sk, ak)
> + λId where (sk, ak)’s are i.i.d samples from some distribution ν. Then with probability 1− δ,∥∥∥∥ ḠKK − Eν [ ḠK K ]∥∥∥∥ ≤ 4√2C2√K ( log 2d δ )1/2 .
Proof of Lemma H.5. For completeness, we provide the proof of Lemma H.5. Let xk = φ(sk, ak). Denote Σ̃h as the matrix obtained by replacing the k-th vector xk in Σ̂h by x̃k and leaving the rest K1 vectors unchanged. Then(
Σ̂h K − Σ̃h K
)2 = ( xkx
> k − x̃kx̃>k K ) 1 K2 ( 2xkx > k xkx > k + 2x̃kx̃ > k x̃kx̃ > k ) 4C 4 K2 Id := A 2 k.
Notice that ∥∥∥∑Kk A2k∥∥∥ = 4C4K , by Lemma H.1 we have the result.
Lemma H.6 (Lemma H.5. of Min et al. (2021)). Let φ : S × A → Rd be a bounded function s.t. ‖φ‖2 ≤ C. Define ḠK = ∑K k=1 φ(sk, ak)φ(sk, ak)
> + λId where (sk, ak)’s are i.i.d samples from some distribution ν. Let G = Eν [φ(s, a)φ(s, a)>]. Then for any δ ∈ (0, 1), if K satisfies
K ≥ max { 512C4 ∥∥G−1∥∥2 log(2d
δ
) , 4λ ∥∥G−1∥∥} .
Then with probability at least 1− δ, it holds simultaneously for all u ∈ Rd that
‖u‖Ḡ−1K ≤ 2√ K ‖u‖G−1 .
Lemma H.7 (Extended Value Difference (Section B.1 in Cai et al. (2020))). Let π = {πh}Hh=1 and π′ = {π′h}Hh=1 be two arbitrary policies and let {Q̂h}Hh=1 be any given Q-functions. Then define V̂h(s) := 〈Q̂h(s, ·), πh(· | s)〉 for all s ∈ S. Then for all s ∈ S,
V̂1(s)− V π ′ 1 (s) = H∑ h=1 Eπ′ [ 〈Q̂h (sh, ·) , πh (· | sh)− π′h (· | sh)〉 | s1 = s ] +
H∑ h=1 Eπ′ [ Q̂h (sh, ah)− ( ThV̂h+1 ) (sh, ah) | s1 = s ] (29) where (ThV )(·, ·) := rh(·, ·) + (PhV )(·, ·) for any V ∈ RS .
Proof. Denote ξh = Q̂h − ThV̂h+1. For any h ∈ [H], we have
V̂h − V π ′ h = 〈Q̂h, πh〉 − 〈Qπ ′ h , π ′ h〉
= 〈Q̂h, πh − π′h〉+ 〈Q̂h −Qπ ′ h , π ′ h〉 = 〈Q̂h, πh − π′h〉+ 〈Ph(V̂h+1 − V π ′ h+1) + ξh, π ′ h〉 = 〈Q̂h, πh − π′h〉+ 〈Ph(V̂h+1 − V π ′ h+1), π ′ h〉+ 〈ξh, π′h〉
recursively apply the above for V̂h+1 − V π ′
h+1 and use the Eπ′ notation (instead of the inner product of Ph, π′h) we can finish the prove of this lemma.
Lemma H.8. Let π̂ = {π̂h}Hh=1 and Q̂h(·, ·) be the arbitrary policy and Q-function and also V̂h(s) = 〈Q̂h(s, ·), π̂h(·|s)〉 ∀s ∈ S. and ζh(s, a) := (ThV̂h+1)(s, a) − Q̂h(s, a) (element-wisely) to be the Bellman update error. Then for any arbitrary π, we have
V π1 (s)− V π̂1 (s) = H∑ h=1 Eπ [ζh(sh, ah) | s1 = s]− H∑ h=1 Eπ̂ [ζh(sh, ah) | s1 = s]
+ H∑ h=1 Eπ [ 〈Q̂h (sh, ·) , πh (·|sh)− π̂h (·|sh)〉 | s1 = x ] where the expectation are taken over sh, ah.
Proof. Note the gap can be rewritten as
V π1 (s)− V π̂1 (s) = V π1 (s)− V̂1(s) + V̂1(s)− V π̂1 (s). By Lemma H.7 with π = π̂, π′ = π, we directly have V π1 (s)−V̂1(s) = H∑ h=1 Eπ [ζh(sh, ah) | s1 = s]+ H∑ h=1 Eπ [ 〈Q̂h (sh, ·) , πh (·|sh)− π̂h (·|sh)〉 | s1 = s ] (30) Next apply Lemma H.7 again with π = π′ = π̂, we directly have
V̂1(s)− V π̂1 (s) = − H∑ h=1 Eπ̂ [ζh(sh, ah) | s1 = s] . (31)
Combine the above two results we prove the stated result.
Lemma H.9. For a linear MDP, for any 0 ≤ V (·) ≤ H , then there exists a wh ∈ Rd s.t. ThV = 〈φ,wh〉 and ‖wh‖2 ≤ 2H √ d for all h ∈ [H]. Here Th(V )(s, a) = rh(x, a) + (PhV )(s, a).
Similarly, for any π, there exists wπh ∈ Rd, such that Qπh = 〈φ,wπh〉 with ‖wπh‖2 ≤ 2(H − h+ 1) √ d.
Proof. By definition, ThV = rh + (PhV ) = 〈φ, θh〉+ 〈φ, ∫ S V (s)dνh(s)〉
⇒ wh = θh + ∫ S V (s)dνh(s),
therefore ‖wh‖2 ≤ ‖θh‖2 + H · ‖νh(S)‖ ≤ 1 + H √ d ≤ 2H √ d. The proof of the second part is similar by backward induction and the fact V πh ≤ H − h+ 1 for any π.
Lemma H.10. For any pessimistic bonus design Γh, suppose K > max{M1,M2,M3,M4}, then with probability 1− δ, Algorithm 1 yields∥∥∥ThV̂h+1 − T̂hV̂h+1∥∥∥
∞ ≤ Õ( H2 √ d/κ√ K )
Proof of Lemma H.10. Suppose wh is the coefficient corresponding to the ThV̂h+1 (such wh exists by Lemma H.9), i.e. ThV̂h+1 = φ>wh, and recall (T̂hV̂h+1)(s, a) = φ(s, a)>ŵh, then:( ThV̂h+1 ) (s, a)− ( T̂hV̂h+1 ) (s, a) = φ(s, a)> (wh − ŵh)
=φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 )) /σ̂2h(s τ h, a τ h) )
=φ(s, a)>wh − φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( ThV̂h+1 ) (sτh, a τ h) /σ̂ 2 h(s τ h, a τ h) ) ︸ ︷︷ ︸
(i)
+ φ(s, a)>Λ̂−1h ( K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ) ︸ ︷︷ ︸
(ii)
.
(32)
For term (i), it is bounded by 2λH 3 √ d/κ
K with probability 1− δ by Lemma C.2. For term (ii), by Cauchy inequality it is bounded by
‖φ(s, a)‖Λ̂−1h · ∥∥∥∥∥ K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ∥∥∥∥∥ Λ̂−1h
≤ 2H√ κK ∥∥∥∥∥ K∑ τ=1 φ (sτh, a τ h) · ( rτh + V̂h+1 ( sτh+1 ) − ( ThV̂h+1 ) (sτh, a τ h) ) /σ̂2h(s τ h, a τ h) ∥∥∥∥∥ Λ̂−1h
≤ 2H√ κK · Õ(H
√ d) = Õ( H2 √ d/κ√ K ),
where the first inequality is by Lemma H.6 (with φ′ = φ/σ̂h and ‖φ/σ̂h‖ ≤ ‖φ‖ ≤ 1 := C) and the third inequality uses √ a> ·A · a ≤ √ ‖a‖2 ‖A‖2 ‖a‖2 = ‖a‖2 √ ‖A‖2 with a to be either φ or wh. Moreover, λmin(Λ̃ p h) ≥ κ/maxh,s,a σ̂h(s, a)2 ≥ κ/H2 implies
∥∥∥(Λ̃ph)−1∥∥∥ ≤ H2/κ. The second inequality comes from Lemma H.2 with R = H since |ητ | = |(rτh + V̂h+1 ( sτh+1 ) − (ThV̂h+1)(sτh, aτh))/σ̂h(sτh, aτh)| ≤ H and |xτ | = |φ(sτh, aτh)/σ̂h(sτh, aτh)| ≤ 1. The final result is obtained by absorbing the term (i) via the condition K > max{M1,M2,M3,M4}.

Review summaries:
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.