{'fraction_non_alphanumeric': 0.05831912717354245, 'fraction_numerical': 0.019979543129901123, 'mean_word_length': 3.821716258425119, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 36, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning

This paper considers batch Reinforcement Learning (RL) with general value function approximation. Our study investigates the minimal assumptions to reliably estimate/minimize Bellman error, and characterizes the generalization performance by (local) Rademacher complexities of general function classes, which makes initial steps in bridging the gap between statistical learning theory and batch RL. Concretely, we view the Bellman error as a surrogate loss for the optimality gap, and prove the followings: (1) In double sampling regime, the excess risk of Empirical Risk Minimizer (ERM) is bounded by the Rademacher complexity of the function class. (2) In the single sampling regime, sample-efficient risk minimization is not possible without further assumptions, regardless of algorithms. However, with completeness assumptions, the excess risk of FQI and a minimax style algorithm can be again bounded by the Rademacher complexity of the corresponding function classes. (3) Fast statistical rates can be achieved by using tools of local Rademacher complexity. Our analysis covers a wide range of function classes, including finite classes, linear spaces, kernel spaces, sparse linear features, etc.


Introduction
Statistical learning theory, since its introduction in the late 1960's, has become one of the most important frameworks in machine learning, to study problems of inference or function estimation from a given collection of data [Hastie et al., 2009, Vapnik, 2013, James et al., 2013. The development of statistical learning has led to a series of new popular algorithms including support vector machines [Cortes andVapnik, 1995, Suykens andVandewalle, 1999], boosting [Freund et al., 1996, Schapire, 1999, as well as many successful applications in fields such as computer vision [Szeliski, 2010, Forsyth andPonce, 2012], speech recognition [Juang andRabiner, 1991, Jelinek, 1997], and bioinformatics [Baldi et al., 2001].
Notably, in the area of supervised learning, a considerable amount of effort has been spent on obtaining sharp risk bounds. These are valuable, for instance, in the problem of model selection-choosing a model of suitable complexity. Typically, these risk bounds characterize the excess risk-the suboptimality of the learned function compared to the best function within a given function class, via proper complexity measures of that function class. After a long line of extensive research [Vapnik, 2013, Vapnik and Chervonenkis, 2015, Bartlett et al., 2005, 2006, risk bounds are proved under very weak assumptions which do not require realizability-the prespecified function class contains the ground-truth. The complexity measures for general function classes have also been developed, including but not limited to metric entropy [Dudley, 1974], VC dimension [Vapnik and Chervonenkis, 2015] and Rademacher complexity [Bartlett and Mendelson, 2002]. (See e.g. Wainwright [2019] for a textbook review.) Concurrently, batch reinforcement learning [Lange et al., 2012, Levine et al., 2020]-a branch of Reinforcement Learning (RL) that learns from offline data, has been independently developed. This paper considers the value function approximation setting, where the learning agent aims to approximate the optimal value function from a restricted function class that encodes the prior knowledge. Batch RL with value function approximation provides an important foundation for the empirical success of modern RL, and leads to the design of many popular algorithms such as DQN [Mnih et al., 2015] and Fitted Q-Iteration with neural networks [Riedmiller, 2005, Fan et al., 2020.
Despite being a special case of supervised learning, batch RL also brings several unique challenges due to the additional requirement of learning the rich temporal structures within the data. Addressing these unique challenges has been the main focus of the field so far [Levine et al., 2020]. Consequently, the field of statistical learning and batch RL have been developed relatively in parallel. In contrast to the mild assumptions required and the generic function class allowed in classical statistical learning theory, a majority of batch RL results , Antos et al., 2008, Lazaric et al., 2012, Chen and Jiang, 2019 remain under rather strong assumptions which rarely hold in practice, and are applicable only to a restricted set of function classes. This raises a natural question: can we bring the rich knowledge in statistical learning theory to advance our understanding in batch RL?
This paper makes initial steps in bridging the gap between statistical learning theory and batch RL. We investigate the minimal assumptions required to reliably estimate or minimize the Bellman error, and characterize the generalization performance of batch RL algorithms by (local) Rademacher complexities of general function classes. Concretely, we establish conditions when the Bellman error can be viewed as a surrogate loss for the optimality gap in values. We then bound the excess risk measured in Bellman errors. We prove the followings: • In the double sampling regime, the excess risk of a simple Empirical Risk Minimizer (ERM) is bounded by the Rademacher complexity of the function class, under almost no assumptions.
• In the single sampling regime, without further assumptions, no algorithm can achieve small excess risk in the worse case unless the number of samples scales up polynomially with respect to the number of states.
• In the single sampling regime, under additional completeness assumptions, the excess risks of Fitted Q-Iteration (FQI) algorithm and a minimax style algorithm can be again bounded by the Rademacher complexity of the corresponding function classes.
• Fast statistical rates can be achieved by using tools of local Rademacher complexity.
Finally, we specialize our generic theory to concrete examples, and show that our analysis covers a wide range of function classes, including finite classes, linear spaces, kernel spaces, sparse linear features, etc.

Related Work
We restrict our discussions in this section to the RL results under function approximation.
Batch RL There exists a stream of literature regarding finite sample guarantees for batch RL with value function approximation. Among the works, fitted value iteration  and policy iteration [Antos et al., 2008, Farahmand et al., 2008, Lazaric et al., 2012, Farahmand et al., 2016, Le et al., 2019 are canonical and popular approaches. When using a linear function space, the sample complexity for batch RL is shown to depend on the dimension [Lazaric et al., 2012]. When it comes to general function classes, several complexity measures of function class such as metric entropy and VC dimensions have been used to bound the performance of fitted value iteration and policy iteration , Antos et al., 2008, Farahmand et al., 2016. Throughout the existing theoretical studies of batch RL, people commonly use concentrability, realizability and completeness assumptions to prove polynomial sample complexity. Chen and Jiang [2019] justify the necessity of low concentrability and hold a debate on realizability and completeness. Xie and Jiang [2020a] develop an algorithm that only relies on the realizability of optimal Q-function and circumvents completeness condition. However, they use a stronger concentrability assumption and the error bound has a slower convergence rate. While the analyses in Chen and Jiang [2019] and Xie and Jiang [2020a] are restricted to discrete function classes with a finite number of elements, Wang et al. [2020a] investigate value function approximation with linear spaces. It is shown that data coverage and realizability conditions are not sufficient for polynomial sample complexity in the linear case.
Off-policy evaluation Off-policy evaluation (OPE) refers to the estimation of value function given offline data [Precup, 2000, Precup et al., 2001, Xie et al., 2019, Kallus and Uehara, 2020, Yin et al., 2020, Uehara et al., 2021, which can be viewed as a subroutine of batch RL. Combining OPE with policy improvement leads to policy-iteration-based or actor-critic algorithms [Dann et al., 2014]. OPE is considered as a simpler problem than batch RL and its analyses cannot directly translate to guarantees in batch RL.
Online RL RL in online mode is in general a more difficult problem than batch RL. The role of value function approximation in online RL remains largely unclear. It requires better tools to measure the capacity of function class in an online manner. In the past few years, there are some investigations in this direction, including using Bellman rank [Jiang et al., 2017] and Eluder dimension [Wang et al., 2020b] to characterize the hardness of RL problem.

Preliminaries
We consider the setting of episodic Markov decision process MDP(S, A, H, P, r), where S is the set of states which possibly has infinitely many elements; A is a finite set of actions with |A| = A; H is the number of steps in each episode; P h (· | s, a) gives the distribution over the next state if action a is taken from state s at step h ∈ [H]; and r h : S × A → [0, 1] is the deterministic reward function at step h. 1 In each episode of an MDP, we start with a fixed initial state s 1 . Then, at each step h ∈ [H], the agent observes state s h ∈ S, picks an action a h ∈ A, receives reward r h (s h , a h ), and then transitions to the next state s h+1 , which is drawn from the distribution P h (· | s h , a h ). Without loss of generality, we assume there is a terminating state s end which the environment will always transit to at step H + 1, and the episode terminates when s end is reached.
A (non-stationary, stochastic) policy π is a collection of H functions π h : S → ∆ A h∈ [H] , where ∆ A is the probability simplex over action set A. We denote π h (· | s) as the action distribution for policy π at state s and time h. Let V π h : S → R denote the value function at step h under policy π, which gives the expected sum of remaining rewards received under policy π, starting from s h = s, until the end of the episode. That is, Accordingly, the action-value function Q π h : S × A → R at step h is defined as, Since the action spaces, and the horizon, are all finite, there always exists (see, e.g., Puterman [2014]) an optimal policy π ⋆ which gives the optimal value V ⋆ h (s) = sup π V π h (s) for all s ∈ S and h ∈ [H]. For notational convenience, we take shorthands P h , P π h , P ⋆ h as follows, where (s, a) is the state-action pair for the current step, while (s ′ , a ′ ) is the state-action pair for the next step, We further define Bellman operators T π h , T ⋆ h : Then the Bellman equation and the Bellman optimality equation can be written as: The objective of RL is to find a near-optimal policy, where the sub-optimality is measured by V ⋆ 1 (s 1 ) − V π 1 (s 1 ). Accordingly, we have the following definition of ǫ-optimal policy.

(Local) Rademacher complexity
In this paper, we leverage Rademacher complexity to characterize the complexity of a function class. For a generic real-valued function space F ⊆ R X and n fixed data points X = {x 1 , . . . , x n } ∈ X n , the empirical Rademacher complexity is defined as Rademacher random variables and the expectation is taken with respect to the uncertainties in {σ i } n i=1 . Let ρ be the underlying distribution of x i . We further define a population Rademacher complexity R ρ n (F) := E ρ [ R X (F)] with expectation taken over data samples X. Intuitively, R ρ n (F) measures the complexity of F by the extent to which functions in the class F correlate with random noise σ i . This paper further uses the tools of local Rademacher complexity to obtain results with fast statistical rate. For a generic real-valued function space F ⊆ R X , and data distribution ρ. Let T be a functional T : F → R + , we study the local Radmacher complexity in the form of A crucial quantity that appears in the generalization error bound using local Rademacher complexity is the critical radius [Bartlett et al., 2005]. We define as follows.
Definition 2.3 (Critical radius of local Radmacher complexity). The critical radius of the local Radmacher complexity R ρ n ({f ∈ F | T (f ) ≤ r}) is the infimum of the set B, where set B is defined as follows: for any r ⋆ ∈ B, there exists a sub-root function ψ such that r ⋆ is the fixed point of ψ, and for any r ≥ r ⋆ we have We typically obtain an upper bound of this critical radius by constructing one specific sub-root function ψ satisfying (1).

Batch RL with Value Function Approximation
This paper focuses on the offline setting where the data in form of tuples D = {(s, a, r, s ′ , h)} are collected beforehand, and are given to the agent. In each tuple, (s, a) are the state and action at the h th step, r is the resulting reward, and s ′ is the next state sampled from P h (·|s, a). For each h ∈ [H], we have access to n data, that are i.i.d sampled with marginal distribution µ h over (s, a) at the h th step. We denote µ = µ 1 × µ 2 × . . . × µ H . For each h ∈ [H], we further denote the marginal distribution of s ′ in tuple (s, a, s ′ , h) as ν h , and let ν = ν 1 × ν 2 × . . . × ν H . Throughout this paper, we will consistently use µ and ν to only denote the probability measures defined above.
We assume data distribution µ is well-behaved and satisfies the following assumption.
Assumption 1 (Concentrability). Given a policy π, let P π h denote the marginal distribution at time step h, starting from s 1 and following π. There exists a parameter C such that sup (s,a,h)∈S×A× [H] dP π h dµ h (s, a) ≤ C for any policy π.
Assumption 1 requires that for any state-action pair (s, a), if there exists a policy π that reaches (s, a) with some descent amount of probability, then the chance that sample (s, a) appears in the dataset would not be low. Intuitively, Assumption 1 ensures that the dataset D is representative for all the "reachable" state-action pairs. The assumption is frequently used in the literature of batch RL, e.g. equation (7) in Munos [2003], Definition 5.1 in Munos [2007], Proposition 1 in Farahmand et al. [2010], Assumption 1 in Chen and Jiang [2019], etc. We remark that Assumption 1 here is the only assumption of this paper regarding the properties of the batch data.
We consider the setting of value function approximation, where at each step h we use a function f h in class F h to approximate the optimal Q-value function. For notational simplicity, we denote f := (f 1 , · · · , f H ) ∈ F with F := F 1 × · · · × F H . Since no reward is collected in the (H + 1) th steps, we will always use the convention that f H+1 = 0 and In valued-based batch RL, we take the offline dataset D as input and output an estimated optimal Q-value function f and the associated policy π f . We are interested in the performance of π f , which is measured by suboptimality in values, i.e., V ⋆ 1 (s 1 )−V π f 1 (s 1 ). However, this gap is highly nonsmooth in f , which is similar to the case of supervised learning where the 0 − 1 losses for classification tasks are also highly nonsmooth and intractable. To mitigate this issue, a popular approach is to use a surrogate loss-the Bellman error.
The following lemma shows that under Assumption 1, one can control the suboptimality in values by the Bellman error.
Lemma 3.2 (Bellman error to value suboptimality). Under Assumption 1, for any f ∈ F, we have that , where C is the concentrability coefficient in Assumption 1.
Therefore, the Bellman error E(f ) is indeed a surrogate loss for the suboptimality of π f under mild conditions. In the next two sections, we will focus on designing efficient algorithms that minimize the Bellman error.

Results for Double Sampling Regime
As a starting point for Bellmen error minimization, we consider an empirical version of E(f ) computed from samples. A natural choice of this empirical proxy is as followŝ where V f h+1 (s) := max a∈A f h+1 (s, a). Unfortunately, the estimatorL B is biased due to the error-in variable situation [Bradtke and Barto, 1996]. In particular, we have the following decomposition.
That is, the Bellman error and the expectation ofL B differ by a variance term. This variance term is due to the stochastic transitions in the system, which is non-negligible even when f approximates the optimal value function Q ⋆ . A direct fix of this problem is to estimate the variance by double samples, where two independent samples of s h+1 are drawn when being in state s h [Baird, 1995].
Formally, in this section, we consider the setting where for any (s, a, r, s ′ , h) in dataset D, there exists a paired tuple (s, a, r,s ′ , h) which share the same state-action pair (s, a) at step h, while s ′ ,s ′ being two independent samples of the next state. Such data can be collected for instance if a simulator is avaliable, or the system allows an agent to revert back to the previous step. For simplicity, we denote this dataset as D = {(s, a, r, s ′ ,s ′ , h)} without placing additional constraints.
We construct the following empirical risk, which further estimates the variance term in (5) via double samples, We can show that, for any fixed f ∈ F, EL DS (f ) = E(f ), i.e.,L DS is an unbiased estimator of the Bellman error. Our algorithm for this setting is simply the Empirical Risk Minimizer (ERM), and we prove the following guarantee.
Theorem 4.1. There exists an absolute constant c > 0, with probability at least 1 − δ, the ERM estimator f = arg min f ∈FLDS (f ) satisfies the following: Here, we use shorthand Most importantly, we remark that Theorem 4.1 holds without any assumption on the input data distribution or the properties of the MDP. Function class F can also be completely misspecificed in the sense the optimal value function Q ⋆ may be very far from F. This allows Theorem 4.1 to be widely applicable to a large number of applications.
However, a major limitation of Theorem 4.1 is its reliance on double samples. Double samples are not available in most dynamical systems that have no simulators or can not be reverted back to the previous step. In next section, we analyze algorithms in the standard single sampling regime.

Results for Single Sampling Regime
In this section, we focus on batch RL in the standard single sampling regime, where each tuple (s, a, r, s ′ , h) in dataset D has a single next step s ′ following (s, a). We first present a sample complexity lower bound for minimizing the Bellman error, showing that in order to acheive an excess risk that does not scale polynomially with respect to the number of states, it is inevitable to have additional structural assumptions on function class F and the MDP. Then we analyze fitted Q-iteration (FQI) and a minimax estimator respectively, under different completeness assumptions. In addition to Rademacher complexity upper bounds similar to Theorem 4.1, we also utilize localization techniques and prove bounds with faster statistical rate in these two schemes.

Lower bound
Recall that when double samples are available, the excess risk of ERM estimator is controlled by Rademacher complexities of function classes (Theorem 4.1). In the single sampling regime, one natural question to ask is whether there exists an algorithm with a similar guarantee (i.e. the excess risk is upper bounded by certain complexity measure of the function class). Unfortunately, without further assumptions, the answer is negative.
Theorem 5.1. Let A be an arbitrary algorithm that takes any dataset D and function class F as input and outputs an estimatorf ∈ F. For any S ∈ N + and sample size n ≥ 0, there exists an S-state, single-action MDP paired with a function class F with |F| = 2 such that thef output by algorithm A satisfies Here, the expectation is taken over the randomness in D.
Theorem 5.1 reveals a fundamental difference between the single sampling regime and the double sampling regime. The lower bound in inequality (6) depends polynomially on S-the cardinality of state space, which is considered to be intractably large in the setting of function approximation. In batch RL with single sampling, despite the use of function class F, the hardness of Bellman error minimization is still determined by the size of state space. This also suggests that minimizing Bellman error in the single sampling regime, is intrinsically different from the classic supervised learning due to the additional temporal correlation structure presented within the data.
We remark that unlike most lower bounds of similar type in prior works Barto, 2018, Sun et al., 2019], which only apply to certain restrictive classes of algorithms, Theorem 5.1 is completely informationtheoretic, and applies to any algorithm.
To circumvent the hardness result in Theorem 5.1, additional structural assumptions are necessary. In the following, we provide statistical gurantees for two batch RL algorithms, where different completeness assumptions on F are used.

Fitted Q-iteration (FQI)
We consider the classical FQI algorithm. We assume that function class F = F 1 × . . . × F H is (approximately) closed under the optimal Bellman operators T ⋆ 1 , . . . , T ⋆ H , which is commonly adopted by prior analyses of FQI Szepesvári, 2008, Chen and.
The FQI algorithm is closely related to approximate dynamic programming [Bertsekas and Tsitsiklis, 1995]. It starts by settingf H+1 := 0 and then recursively computes Q-value functions at h = H, H − 1, . . . , 1. Each iteration in FQI is a least squares regression problem based on data collected at that time step. For h ∈ [H], we denote D h as set of data at the h th step. The details of FQI are specified in Algorithm 1. In the following Theorem 5.2, we upper bound the excess risk of the output of FQI in terms of Rademacher complexity.
Theorem 5.2 (FQI, Rademacher complexity). There exists an absolute constant c > 0, under Assumption 2, with probability at least 1 − δ, the output of FQIf satisfies We remark that Assumption 2 immediately implies that min f ∈F E(f ) ≤ ǫ. Therefore, although the minimal Bellman error min f ∈F E(f ) does not explicitly appear on the right hand side, inequality (7) is still a variant of excess risk bound.
For typical parametric function classes, the Rademacher complexity scales as n −1/2 (see Section 6). Therefore, Theorem 5.2 guarantees that the excess risk decrease as n −1/2 , up to a constant error ǫ due to the approximate completeness (in Assumption 2). However, since Bellman error is the average of squared L 2 -norms (Definition 3.1), one may expect a faster statistical rate in this setting, similar to the case of linear regression. For this reason, we take advantage of the localization techniques and develop sharper error bounds in Theorem 5.3.
Theorem 5.3 (FQI, local Rademacher complexity). There exists an absolute constant c > 0, under Assumption 2, with probability at least 1 − δ, the output of FQIf satisfies Here r ⋆ h is the critical radius of local Rademacher complexity On the RHS of inequality (8), the first term ǫ measures model misspecification. The other two terms c( √ ǫ · ∆+∆) can be viewed as statistical errors since ∆ → 0 as sample size n → ∞. For typical parametric function classes, the critical radius of the local Rademacher complexity scales as n −1 (see Section 6), which decreases much faster than standard Rademacher complexity. That is, Theorem 5.3 indeed guarantees faster statistical rate comparing to Theorem 5.2.
Finally, we remark that f † h in Theorem 5.3 depends onf h+1 and therefore is random. We will show later in Section 6 for many examples, the critical radius can be upper bounded independent of the choice of f † h , in which case the randomness in f † h does not affect the final results.

Minimax Algorithm
The (approximate) completeness of F in Assumption 2 can be stringent sometimes. For instance, if there is a new function f h attached to F h , for the sake of completeness, we need to enlarge F h−1 by adding several approximations of T ⋆ h−1 f h . The same goes for F h−2 , . . . , F 1 . After amplifying the function classes one by one for each step, we may obtain an exceedingly large F.
To avoid the issue above posted by the completeness assumptions on F, we introduce a new function class G = G 1 × · · · × G H , where G h consists of functions mapping from S × A to [−H, H]. We assume that for each f h+1 ∈ F h+1 , one can always find a good approximation of T ⋆ h f h+1 in this helper function class G h .
According to (5), we can approximate Bellman error E(f ) by subtracting the variance term fromL B (f ).
averaged over data provides a good estimator of the variance term. Following this intuition, we define a new losŝ The minimax algorithm [Antos et al., 2008, Chen and] then computeŝ Now we are ready to state our theoretical guarantees for the minimax algorithms.
Theorem 5.4 (Minimax algorithm, Rademacher complexity). There exists an absolute constant c > 0, under Assumption 3, with probability at least 1 − δ, the minimax estimatorf satisfies: As is shown in Theorem 5.4, the excess risk is simultaneously controlled by the Rademacher complexi- . Similar to the results for FQI, we can also develop risk bounds with faster statistical rate using the localization techniques. For technical reasons that will be soon discussed, we introduce the following assumption, which can be viewed a variant of the concentrability coefficient in Assumption 1 under different initial distributions.
Assumption 4. For any policy π and h ∈ [H], let P π h,t (or P π h,t ) denote the marginal distribution at t > h, starting from µ h at time step h (or from ν h × Unif(A) at h + 1) and following π. There exists a parameter C such that For notational convenience, we define we are ready to state the excess risk bound of the minimax algorithm in terms of local Rademacher complexity as follows.
Theorem 5.5 (Minimax algorithm, local Rademacher complexity). There exists an absolute constant c > 0, under Assumptions 3 and 4, with probability at least 1 − δ, the minimax estimatorf satisfies: where C is the concentrability coefficient in Assumption 4, and r ⋆ f,h , r ⋆ g,h ,r ⋆ f,h are the critical radius of the following local Rademacher complexities respectively: Similar to Theorem 5.3, our upper bound in (9) can also be viewed as a combination of model misspec- As n → ∞, the model misspecification error is nonvanishing and the statistical error tends to zero. Again for typical parametric function classes, the critical radius of the local Rademacher complexity scales as n −1 (see Section 6), and Theorem 5.5 claims the excess risk of the minimax algorithm also decreases as n −1 except a constant model misspecification error ǫ.
Intuitively, Assumption 4 is required in Theorem 5.5 to allow that . We conjecture such additional assumption is unavoidable if we would like to upper bound the excess risk using the local Rademacher complexity of F h , G h and V F h+1 for the minimax algorithm.
In Appendix C, we present an alternative version of Theorem 5.3, which does not require Assumption 4 but bound the excess risk using the local Rademacher complexity of a composite function class depending on the loss, F, and G. The alternative version recovers the sharp result in Chen and Jiang [2019] when the function classes F and G both have finite elements.
Finally, our upper bounds for the minimax algorithm contain Radermacher complexities of the function class V F . We can conveniently control them using the Radermacher complexities of function class F as follows.
Proposition 5.6. Let F be a set of functions over S × A and ρ be a measure over S. We have the following inequality, where A is the cardinality of the set A.

Examples
Below we give four examples of function classes, each with an upper bound on Rademacher complexity, as well as the critical radius of the local Rademacher complexity. Throughout this section we use notation r ⋆,ρ n (F, f o ) to denote the critical radius of local Rademacher complexity R ρ n ({f ∈ F | f − f o Function class with finite element. First, we consider the function class F with |F| < ∞. Under the normalization that f ∈ [0, H] for any f ∈ F, we have the following.
Proposition 6.1. For function class F defined above, for any data distribution ρ and any anchor function Linear functions. Let φ : S × A → R d be the feature map to a d-dimensional Euclidean space, and consider the function class Under the normalization that φ(s, a) ≤ 1 for any (s, a), we have Proposition 6.2. For linear function class F defined above, for any data distribution ρ and any anchor function f o ∈ F:

Functions in RKHS. Consider a Reproducing Kernel Hilbert Space
Suppose that E (s,a)∼ρ k (s, a), (s, a) < +∞. Let λ i (T ) ∞ i=1 be the eigenvalues of T , arranging in a nonincreasing order. Then Proposition 6.3. For kernel function class F defined above, for any data distribution ρ and any anchor function f o ∈ F: Sparse linear functions. Let φ : S × A → R d be the feature map to a d-dimensional Euclidean space, and consider the function class Proposition 6.4. There exists an absolute constant c > 0, for sparse linear function class F defined above, assume the data distribution ρ satisfies the conditions specified above, then for any anchor function f o ∈ F: End-to-end results. Finally, to obtain an end-to-end result that upper bounds the suboptimality in values for specific function classes listed above, we can simply combine (a) the result that upper bound the value suboptimality using the Bellman error (Lemma 3.2); (b) the results that upper bound the Bellman error in terms of (local) Rademacher complexity (Theorems 4.1, 5.2-5.5); (c) the upper bounds of (local) Rademacher complexity for specific function classes (Propositions 6.1-6.4).

Conclusion
This paper studies batch RL with general value function approximation from the lens of statistical learning theory. We identify the intrinsic difference between batch reinforcement learning and classical supervised learning (Theorem 5.1) due to the additional temporal correlation structure presented in the RL data. Under mild conditions, this paper also provides upper bounds on the generalization performance of several popular batch RL algorithms in terms of the (local) Rademacher complexities of general function classes. We hope our results shed light on the future research in further bridging the gap between statistical learning theory and RL. Throughout the supplementary materials, we omit the subscript ρ in population Rademacher complexty R ρ n (·) if the distribution is clear from the context. In this part, we prove Theorem 4.1 in Section 4. We first define some auxiliary notations to simplify the writing. We divide the dataset where f H+1 := 0. Note that the loss functionL DS (f ) is an empirical estimation of E(f ). Theorem 4.1 provides an upper error bound for the BRM estimatorf = arg min f ∈FLDS (f ), of which the proof is given below.
Theorem 4.1. There exists an absolute constant c > 0, with probability at least 1 − δ, the ERM estimator f = arg min f ∈FLDS (f ) satisfies the following: Proof of Theorem 4.1. We apply the uniform concentration inequalites in Lemma G.1. Let f † be a minimizer of the Bellman error within the function class and reduce eq. (10) to It then remains to simplify the form of Rademacher complexity R n L DS (f ) f ∈ F . Due to the sub-additivity of Rademacher complexity, we have In order to tackle the term on the right hand side, we apply the vector-form contraction property of Rademacher complexity in Lemma G.7. By letting we can write Since the spectral norm Ã 2 ≤ 4 and Lemma G.7 then implies Recalling that s ′ ands ′ are i.i.d. conditioned on (s, a), we use the sub-additivity of Rademacher complexity and find that where ν h is the marginal distribution of s ′ in the h th step. Note that {r h } is a singleton, therefore, R n ({r h }) = 0. It follows from eqs. (13) and (14) that Combining eqs. (12) and (15), we learn that Plugging eq. (16) into eq. (11), we finish the proof.

B Proof of Results for FQI (Theorems 5.2 and 5.3)
In this section, we analyze the FQI estimator defined in Algorithm 1. For any f h ∈ F h and f h+1 ∈ F h+1 , we denote Note that each iteration in FQI solves an empirical loss minimization problemf h : .

Recall that
In the sequel, we develop upper bounds for Bellman error E(f ) based on (local) Rademathcer complexities.
B.1 Analyzing FQI with Rademacher Complexity (Theorem 5.2) Theorem 5.2 (FQI, Rademacher complexity). There exists an absolute constant c > 0, under Assumption 2, with probability at least 1 − δ, the output of FQIf satisfies Proof of Theorem 5.2. By Lemma G.1, with probability at least 1 − δ, for any f h ∈ F h , We further use the relation and Assumption 2. It follows that We now simplify the Rademacher complexity term in eq. (21). Due to the symmmetry of Rademacher random variables, we have According to the contraction property of Rademacher complexity (see Lemma G.6), we have Plugging eq. (23) into eq. (21) and applying union bound, we find that with probability at least 1 − δ, which completes the proof.
Here r ⋆ h is the critical radius of local Rademacher complexity Proof of Theorem 5.3. Recall that we have shown in eq. (22) that ℓ(f, g) is (4H)-Lipchitz in its first argument f . Under Assumption 2, for f † h shown in eq. (18), we have When applying Theorem G.3, we are supposed to take a sub-root function larger than Note that µ h ≤ r and the positive fixed point r ⋆ h of ψ h is the corresponding critical radius. In the second inequality, we have used the contraction property of Rademacher complexity (see Lemma G.6) and the Lipschitz continuity of ℓ. The equality in the last line is due to the symmetry of Rademacher random variables. According to Lemma G.5, the positive fixed point of 128H 3 ψ h r 16H 2 is upper bounded by 1024H 4 r ⋆ h . We apply eq. (90) in Theorem G.3 and use the eq. (20) andl It follows that for a fixed parameter θ, with probability at least 1 − δ, where c > 0 is a universal constant. By union bound and Assumption 2, we have We further take θ := 1 + In this part, we prove the statistical guarantees for minimax algorithm in Section 5.3.
Notations We first introduce some notations that will be used later in the analyses. For any vector-valued Let T ⋆ , T † , T be their vector form, given by for any f ∈ F.
Similar to the definition of ℓ in eq. (17), for any g h ∈ G h ∪ F h and f h+1 ∈ F h+1 , we take The loss function in minimax algorithm then can be written as Note that With our newly-defined notations, we formulate the minimax estimator aŝ In the analysis of minimax algorithm, we take f † as the function in F that minimizes the Bellmen risk, i.e.

Main results
Theorem 5.4 (Minimax algorithm, Rademacher complexity). There exists an absolute constant c > 0, under Assumption 3, with probability at least 1 − δ, the minimax estimatorf satisfies: Theorem 5.5 (Minimax algorithm, local Rademacher complexity). There exists an absolute constant c > 0, under Assumptions 3 and 4, with probability at least 1 − δ, the minimax estimatorf satisfies: where C is the concentrability coefficient in Assumption 4, and r ⋆ f,h , r ⋆ g,h ,r ⋆ f,h are the critical radius of the following local Rademacher complexities respectively: Aside from Theorems 5.4 and 5.5, we also have an alternative statistical guarantee for E(f ) using local Rademacher complexity for composite function L MM (f, T † f ). See Theorem C.1 below.
Theorem C.1 (Minimax algorithm, local Rademacher complexity, alternaltive). There exists an absolute constant c > 0, under Assumption 3, with probability at least 1 − δ, the minimax estimatorf satisfies: where r ⋆ L and r ⋆ g,h are the critical radius of the following local Rademacher complexities respectively: In contrast to Theorem 5.5, Theorem C.1 does not rely on the additional Assumption 4. In general, Theorem C.1 provides a tighter upper bound for E(f ) than Theorem 5.5 when the function class L MM (f, T † f ) f ∈ F has a clear structure and r ⋆ L is easy to estimate. For instance, this is the case if both f and G have finite elements. Based on Theorem C.1, we can recover the sharp results for finite function classes in Chen and Jiang [2019].
Assumption 3 used in our analysis of minimax algorithm can be relaxed to: "There exist constants ǫ > 0 and ζ ∈ [0, 1) such that inf In this way, we only need a high-quality approximation of T ⋆ f in G when f lies within a neighborhood of the optimal Q-function. We can easily generalize our analyses to this case. However, in order to avoid unnecessary clutter, we stick to the current Assumption 3.
Proof outline Our analyses in this section are devoted to the proofs of Theorems 5.4, 5.5 and C.1.

We first translate the estimation of E(f ) into deriving uniform concentration bounds forL MM
The error decomposition lemma is shared among the proofs of Theorems 5.4, 5.5 and C.1.
2. We then develop the desired uniform concentration bounds using Rademacher complexities (Appendix C.2) and local Rademacher complexities (Appendix C.3) separately. In particular, when tack- , we have two alternative analyses involving local Rademacher complexities of different types of function classes. One leads to Theorem 5.5 and the other results in Theorem C.1.
3. In Appendix C.4, we integrate the error decomposition result and uniform concentration bounds, and finish the proofs of theorems.

C.1 Error Decomposition
We provide a decomposition of the Bellman error E(f ) and upper bound the error using some uniform concentration inequalities.
Lemma C.2 (Error decomposition). Suppose there exist α > 0 and Err f , Err g > 0 such that the following concentration inequailities hold simultaneously.
1. For any f ∈ F, 2. For any g ∈ G, Then under Assumption 3, the Bellman error satisfies Proof. By definition of function E µ L MM (f, g) in eq. (25), we find that for any f ∈ F, We learn from Assumption 3 that T † f − T ⋆ f 2 µ ≤ ǫ for any f ∈ F, therefore, which implies By virtue of eq. (28), In the following, we leverage eq. (29) to We use the definition of L MM and find that Since (f, g) := (f , Tf ) solves the minimax optimizaiton problem eq. (26), we haveL MM f , Tf ≤ L MM f † , T f † . Due to the optimality of T , it also holds thatl( Tf ,f ) ≤l(T †f ,f ). To this end, eq. (33) reduces toL Additionally, eq. (29) implieŝ It then follows from eq. (34) that Combining eq. (32) and eq. (35), we obtain eq. (30).

C.2 Analyzing Minimax Algorithm with Rademacher Complexity
In what follows, we develop uniform concentration inequalities eqs. (28) and (29) using Rademacher complexities.
Lemma C.3. With probability at least 1 − δ, We apply Lemma G.1 and find that Due to the symmetry of Rademacher random variables, we have We now use Lemma G.7 to simplify the term R n L MM f, Here, Integrating the pieces, we finish the proof of Lemma C.3. Lemma C.4. With probability at least 1 − δ, for any g ∈ G, Proof. Note that ℓ(g, f † ) − ℓ T † f † , f † ≤ 2H 2 . By Lemma G.1, with probability at least 1 − δ, for any g ∈ G, We observe that (37) Similar to eq. (22), we can show that ℓ(g h , f † h+1 ) is (4H)-Lipschitz with respect to g h , therefore, Combining eq. (36) -eq. (38), we complete the proof.

C.3 Analyzing Minimax Algorithm with Local Rademacher Complexity
In this part, Lemmas C.5 and C.6 are devoted to the uniform concentration ofL MM f, T † f −L MM f † , T † f † and Lemma C.7 is concerned withl g, f † −l T † f † , f † . The proof of Theorem C.1 uses Lemmas C.5 and C.7, while Theorem 5.5 uses Lemmas C.6 and C.7.
Concentration inequality eq. (28),L MM f, T † f −L MM f † , T † f † Lemma C.5 below will be used as a buiding block of the proof of Theorem C.1.
Lemma C.5. There exists a universal constant c > 0 such that under Assumption 3, for any fixed parameter θ > 1, with probability at least 1 − δ, we have for any f ∈ F, with Proof. We consider using Theorem G.3 to analyze the concentration ofL MM f, Similar to eq. (22), we can show that for any f ∈ F, By Cauchy-Schwarz inequality, where we have used Assumption 3. It follows that We also learn from eq. (31) that We combine eq. (40) and eq. (41) and find that Var We now apply Theorem G.3 and aim to find a sub-root function ψ L such that ψ L (r) ≥ ψ(r) for (42) Note that by eqs. (40) and (41), we have Let r ⋆ L be the positive fixed point of ψ L . Lemma G.5 implies the positive fixed point of mapping r → 16H 2 ψ L r/2 is upper bounded by 128H 4 r ⋆ L . We then obtain eq. (39) by applying eq. (90) in Theorem G.3. While Lemma C.5 above uses the local Rademacher complexity of a composite function L MM (f, T † f ), Lemma C.6 below provides an alternative concentration inequality forL MM f, Lemma C.6. Suppose Assumptions 3 and 4 hold. There exists a universal constant c > 0 such that for any fixed parameter θ > 1, with probability at least 1 − δ, for any f ∈ F, with Here, C is the concentrability coefficient in Assumption 4.
Proof. In this proof, we estimate the critical radius of ψ(r) in eq. (42) in an alternative way. In particular, we use parameters r ⋆ f,h , r ⋆ g,h and r ⋆ f,h defined in the statement of Theorem 5.5. The key step is to upper bound ψ(r) by the local Rademacher complexities . Similar to Lemma C.3, one can show that there exists a univeral constant c > 0 such that In the sequel, we simplify ψ h,1 , ψ h,2 and ψ h,3 . For any f ∈ F(r), due to eq. (41), we have We use Lemma F.1 and find that under Assumptions 3 and 4, for any f ∈ F,

It follows that
Recall that r ⋆ f,h , r ⋆ g,h and r ⋆ f,h+1 are respectively the fixed points of According to Lemma G.5, the positive fixed points of ψ h,1 , ψ h,2 and ψ h,3 are upper bounded by 8 Cr ⋆ f,h , 4 Cr ⋆ g,h + 32ǫ Cr ⋆ g,h and 8 C r f,h , therefore, the critical radius r ⋆ of ψ(r) satisfies where c, c ′ > 0 are universal constants. We then apply eq. (90) in Theorem G.3 and obtain eq. (43).
Concentration inequality eq. (29),l g, f † −l T † f † , f † Lemma C.7. Suppose Assumption 3 holds. Then there exists a universal constant c > 0 such that for any fixed parameter θ > 1, with probability at least 1 − δ, with Proof. Note that We can analyze the concentration of ℓ in a way similar to Theorem 5.3. It follows that for any h ∈ [H], with probability at least 1 − δ, for any g h ∈ G h , where c 1 , c 2 , c 3 are the constants in Theorem G.3. By union bound, we can further derive eq. (44).
Proof of Theorems 5.5 and C.1. Plugging Lemmas Lemmas C.5 and C.7 into Lemma C.2 yields that with probability at least 1 − δ, for a universal constant c > 0. By letting we have which finishes the proof of Theorem C.1. Similarly, by combining Lemmas C.2, C.6 and C.7, we prove Theorem 5.5.
D Examples (Propositions 6.1 to 6.4) In this part, we provide estimates for the (local) Rademacher complexities of four special function spaces, namely function class with finite elements, linear function space, kernel class and sparse linear space. The results presented here slightly generalize Propositions 6.1 to 6.4.
D.1 Function class with finite elements (Proposition 6.1) Lemma D.1 (Full version of Proposition 6.1). Suppose F is a discrete function class with |F| < ∞ and f ∈ [0, D] for any f ∈ F. Then for any distribution ρ, For any function f • with range in [0, D], we have ψ is a sub-root function with positive fixed point We remark that Proposition 6.1 is a corollary of Lemma D.1 with D := H. In order to prove Lemma D.1, we first present a preliminary lemma that will be used later. See Lemma D.2.
Lemma D.2. Suppose a random variable X satisfies |X| ≤ D and E[X] = 0. Then for any λ > 0, we have Proof. Note that X ≤ D and the mapping x → e x −1−x x 2 is nondecreasing, therefore, e λX −1−λX where we have used the fact E[X] = 0. Since 1 + x ≤ e x for any x ∈ R, eq. (48) implies eq. (47).
We are now ready to prove Lemma D.1.
Proof of Lemma D.1. We can easily see that eq. (45) is a corollary of eq. (46) by letting f • = 0 and r = D 2 , therefore, we focus on proving eq. (46). By definition of Rademacher complexity and the symmetry of Rademacher variables, we have For any λ > 0, it holds that where the last line is due to Jensen's inequality. Since (σ 1 , X 1 ), . . . , (σ n , X n ) are i.i.d. samples, Note that We apply Lemma D.2 and derive that Combining eqs. (49) to (51), we obtain For r ≥ D 2 log |F | n , by letting λ := ≤ 1 for any x ≤ 1. When 0 ≤ r < D 2 log |F | n , by letting Integrating the pieces, we complete the proof of eq. (46).
It is easy to see that the right hand side of eq. (46) where B > 0. It holds that n .
For any f • ∈ F, we have ψ is sub-root and has a positive fixed point Proposition 6.2 in Section 6 is a corollary to Lemma D.3. In Proposition 6.2, conditions w ≤ H and φ(s, a) ≤ 1 ensure f ∞ ≤ H for f = w ⊤ φ and therefore f 2 ρ ≤ H 2 . By letting B := H 2 in Lemma D.3, we obtain Proposition 6.2.
Proof of Lemma D.3. Lemma D.3 can be viewed as a consequence of Lemma D.4 in Appendix D.3. Without loss of generality, suppose that φ is orthonormal in L 2 (ρ), that is, Define a kernel function k (s, a), (s ′ , a ′ ) = φ(s, a) ⊤ φ(s ′ , a ′ ). The RKHS associated with kernel k is the linear space spanned by φ endorsed with inner product f,

D.3 Kernel Class (Proposition 6.3)
We now consider kernel class, that is, a sphere in an RKHS H associated with a positive definite kernel k : X × X → R. In our paper, X = S × A. Let ρ be a distribution over X . We are interested in Rademacher complexities of function class Here, · K denotes the RKHS norm and D, B ≥ 0 are some constants. Suppose that E ρ k(X, X) < ∞ for X ∼ ρ. We define an integral operator T : L 2 (ρ) → L 2 (ρ) as It is easy to see that T is positive semidefinite and trace-class. Let {λ i } ∞ i=1 be the eigenvalues of T , arranging in a nonincreasing order. By using these eigenvalues, we have an estimate for (local) Rademacher complexities of F in Lemma D.4 below.
Lemma D.4 (Full version of Proposition 6.3). For function class F defined in eq. (53), we have Let f • be an arbitrary function in F. The local Rademacher complexity around f • satisfies ψ is a sub-root function with positive fixed point In Proposition 6.3, we assume that k(x, x) ≤ 1 for any x ∈ X and f K ≤ H for any f ∈ F. It is then To this end, Proposition 6.3 is a consequence of lemma D.4 by taking D := H and B := H 2 . We remark on the rate of r ⋆ with respect to sample size n. Firstly, it is evident that r ⋆ n − 1 2 . When λ i i −α for α > 1, r ⋆ h has order n − α 1+α which is typical in nonparametric estimation. When the eigenvalues {λ i } ∞ i=1 decay exponentially quickly, i.e. λ i exp(−βi α ) for α, β > 0, r ⋆ can be of order n −1 (log n) 1/α . Our proof of Lemma D.4 is based on a classical result shown in Theorem D.5.
For any positive semidefinite (PSD) matrix M ∈ R d×d , let M † denote its Moore-Penrose inverse and √ M † ∈ R d×d be the unique PSD matrix such that for any x ∈ R d . For any two distributions µ and ν on a same metric space (X, d), we say a measure p(X, Y ) over X × X is a coupling of µ and ν if the marginal distributions of p are µ and ν respectively, i.e. p(·, X) = µ and p(X, ·) = ν. The quadratic Wasserstein metric of µ and ν is defined as where C(µ, ν) is the collection of all couplings of µ, ν.
Main results Before the statement of main results, we first introduce the notion of T 2 property. See Definition D.6 below.
We remark that T 2 is a broad class that contains many common distributions as special cases. For example, Gaussian distribution N (·, M ) satisfies T 2 M 2 -inequality. Strongly log-concave distributions are T 2 . Suppose ρ is a continuous measure with a convex and compact support set. If its smallest density is lower bounded within the support, then ρ is T 2 .
We have an estimate of the (local) Rademacher complexities of F s in Lemma D.7.
Moreover, when n ≥ cs log d, for any f • ∈ F s , the local Rademacher complexity of F s satisfies Here, ψ(r) is a sub-root function with a unique positive fixed point r ⋆ = c 2 (1 + η s ) 2 · s log d n .

Proof of main results
In the sequel, we prove Lemma D.7. We first present some preliminary results.
By definition of ψ 2 -norm and our assumption Therefore, by Jensen's inequality Recall that X i 1 {|X i |>R} ψ 1 ≤ κ 1 , which implies there exists a universal constant c ≥ 1 such that P |X i |1 {|X i |≥R} > t ≤ ce −ct/κ 1 . Using this fact, we find that Integrating the pieces, we finish the proof.
Lemma D.9. Let X 1 , X 2 , . . . , X n ∈ R d be i.i.d. random vectors satisfying T 2 (σ)-inequality and E[X 1 X ⊤ 1 ] = M ∈ R d×d . Suppose that n ≥ d. Let σ 1 , σ 2 , . . . , σ n be Rademacher random variables independent of X 1 , X 2 , . . . , X n . Then Y := 1 n n k=1 σ k X k M † satisfies Proof. We take shorthands X := [X 1 , X 2 , . . . , X n ] ∈ R d×n , σ := (σ 1 , . . . , σ n ) ⊤ ∈ R n and rewrite Y as In the following, we analyze these two terms separately. Note -Lipschitz with respect to σ in the Euclidean norm. Moreover, Y is convex in σ and the Rademacher random variables are independent and bounded. We use Talagrand's inequality (See Theorem 4.20 and Corollary 4.23 in van Handel [2014].) and obtain that there exists a universal constant c > 0 such that We next consider the concentration of √ M † X 2 . For random vector X, we define Since X satisfies T 2 (σ)-inequality, according to Gozlan's theorem (Theorem 4.31 in van Handel [2014]), we find that We now apply Theorem 5.39 in Vershynin [2010] and obtain that which further implies Combining eq. (58) and eq. (59), we learn that As for the second term E σ [Y | X] − EY , we use the T 2 (σ) property of sample distribution and Gozlan's theorem (Theorem 4.31 in van Handel [2014]). We first show that E σ [Y | X] is M † 2 n -Lipschitz with respect to Frobenius norm · F . In fact, We then apply Gozlan's theorem and find that there exists a universal constant c > 0 such that for any t 1 > 0.
Integrating eq. (60) and eq. (61) and using the condition n ≥ d, we find that If 0 ≤ t 1 ≤ √ n, then by letting t 2 = √ n, we have Otherwise, when t 1 > √ n, we take t 2 = t 1 and obtain We then finish the proof by combining these two cases.
We are now ready to prove Lemma D.7.
To this end, in the following, we focus on the local Rademacher complexity R ρ n f ∈ F s f 2 ρ ≤ r . To simplify the notation, we write x := (s, a). Note that We fix α, {σ k } n k=1 and {x k } n k=1 and then optimize w ∈ R s . Since x k ∈ supp(ρ), one always has 1 n K k=1 σ k φ α (x k ) ∈ range(Σ α ) with probability one. The supremum is therefore acheived at It follows that We further upper bound the local Rademacher complexity by In the following, we estimate the two terms in the right hand side of eq. (62) separately.

E Proof of Lower Bound (Theorem 5.1)
In this section, we will prove a stronger version of Theorem 5.1, which is Theorem E.1. In Theorem E.1, we show that in the same setting as Theorem 5.1, even if additionally assuming Assumption 1 holds with C = 1, i.e., µ h is the true marginal distribution of the single-action MDP, and the algorithm knows {µ h } H h=1 , it still takes Ω( √ S ε 2 ) samples for the learning algorithm A to achieve ε optimality gap for Bellman error. This further justifies the necessity of Assumption 2 and Assumption 3 in the single sampling regime.
Theorem 5.1. Let A be an arbitrary algorithm that takes any dataset D and function class F as input and outputs an estimatorf ∈ F. For any S ∈ N + and sample size n ≥ 0, there exists an S-state, single-action MDP paired with a function class F with |F| = 2 such that thef output by algorithm A satisfies Here, the expectation is taken over the randomness in D.
Below we will prove Theorem E.1. To better illustrate the idea of the hard instance, we will first prove a slightly weaker version with C = 2 (Theorem E.2) in Appendix E.1 and in Appendix E.2 we will prove Theorem E.1 by slightly twisting the proof in Appendix E.1.

E.1 Warm-up with C = 2
We construct the hard instances for single sampling in the following way.
Hard Instance Construction: We first generate a uniform random bit c ∈ {−1, 1}, and a Radamacher vector σ ∈ {±1} S . For each c, σ, we define MDP M ε c,σ = (S, A, H, P ε c,σ , r) below, where 0 < ε < 0, 5. The claim is the distribution of M ε c,σ serves as the distribution of hard instances. Note that only P ε c,σ in the tuple defining M ε c,σ depends on c and σ. Here the probability transition matrix M ε c,σ is the same for all h = 1, 2, . . . , H.
Let S = {s start } ∪ {1, . . . , S} ∪ {t j,k } j,k∈{−1,1} , H = 2, |A| = 1 and the initial state is s start . Since there's only one action, below we will just drop the dependence on action and thus simplify the notation. We will always define the probability transition matrix in the way such that in the 2nd step, we will reach some state among 1, . . . , S and in the 3rd step, we will reach some state among t j,k .
Function class: F = {f 1 , f −1 }, where f c (s start ) = 1 2 , f c (i) = 1 2 , ∀1 ≤ i ≤ S and f c (t j,k ) = k max(c,j)+1 2 , ∀c, j, k ∈ {±1}. Compared to the notation in the main paper, we drop the dependency on h for f ∈ F. This is because the MDP will reach a disjoint set of states for each step h (see below).
(c) Illustration of P ε 1,σi . When c = 1, there are two different but equally likely types of state i, depending on their probability transition matrix for the next step.
(d) Illustration of P ε −1,σi . When c = 1, there are two different but equally likely types of state i, depending on their probability transition matrix for the next step. Figure 1: Graphical illustration of the hard instances M ε c,σ . As shown in Equation (65), the total Bellman error is only determined by the Bellman error for h = 2, which is equal to optimal error + ε 2 12 1 [c = c ′ ] if f c ′ is the returned function. The main idea of the proof is to show it's difficult to guess c via the observed dataset D if D only contains single-sampled data. As a sanity check, for any c and sample (i, t j,k ), if σ i unif ∼ {±1}, the marginal distribution of t j,k is always uniform, but for double sampling of form (i, t j,k , t j ′ ,k ′ ), we can decide c by simply looking at histogram of (t j,k , t j ′ ,k ′ ).
Underlying distribution: We define the underlying distribution for batch data µ as µ 2 (i) = 1 S and µ 3 (t j,k ) = 1 4 , we can check that Assumption 1 is satisfied with C = 2 as ε < 0.5. Define T 1 c,σ , T 2 c,σ , T 3 c,σ be the Bellman operator of M ε c,σ , we have ∀σ ∈ {−1, 1} S , ∀c, c ′ ∈ {−1, 1}, From eq. (65) we can see minimizing Bellman error in this case is equivalent to predict −c. And any algorithm predicts c wrongly, i.e., outputs f c ′ with c ′ = c with constant probability, will suffer Ω(ε 2 ) expected optimality gap. More specifically, we can show that for random σ, it's information-theoretically hard to predict c correctly given D, which leads to the following theorem.
sampled from M ε c,σ and µ, we have for any learning algorithm A with n = O( √ S ε 2 ) samples, Or equivalently (and more specifically), if we view A(D) as the modified version of A, whose range is {−1, 1} and satisfies A = f c with c = A(D). Then we have Towards proving Theorem E.2, we need the following lower bound, where µ 2 • P ε c,σ is defined as the joint distribution of (s, s ′ ), where s ∼ µ 2 and s ′ ∼ P c,σ|s . Note that when ε = 0, P 0 c,σ (· | i) becomes uniform distribution for every 1 ≤ i ≤ S, and thus is independent of c, σ, which could be denoted by P 0 therefore.
Proof. For convenience, we denote µ 2 • P 0 n by P and E σ µ 2 • P ε c,σ n by Q. By Pinsker's inequality, we have P − Q T V ≤ 2KL(P, Q), for any distribution P, Q. Thus it suffices to upper bound KL(P, Q) by 0.05.
Proof of Theorem E.2. In our case, since r is known and |A| = 1, we can simplify the each data in D into the form of (s, s ′ , h). Further since the probability transition matrix for h = 1 and h = 3 are known, below we will assume D only contains n pairs of (s, s ′ , 2), and we will call these states by {s i } n i=1 and c,σ f c ′ 1 2,µ 2 and f c ′ − T 3 c,σ f c ′ 1 2,µ 2 are constant for all c, c ′ , we only need to consider f c ′ − T 2 c,σ f c ′ 2 2,µ 3 as our loss. Recall we define µ 2 • P ε c,σ as the joint distribution of (s, s ′ ), where s ∼ µ 2 and s ′ ∼ P c,σ|s . Thus the dataset D can be viewed as sampled from E c,σ (µ 2 • P c,σ ) n , i.e., D is sampled from a mixture of product measures.
By Lemma E.3, we know Thus if we denote the distribution of widetildeA(D) by X c , where D ∼ E σ µ 2 • P ε c,σ n and σ ∼ {−1, 1} S , and A can be random, the above inequality implies P [X −1 = X 1 ] ≤ 0.2, and therefore we have E.2 Proof of Theorem E.1 Now we will prove Theorem E.1 by slightly twisting the distribution of hard instances (MDPs) constructed in the previous subsection.
By symmetry, it also holds that Lemma G.1. Let F be a class of functions with ranges in [a, b]. With probability at least 1 − δ, P f ≤ P n f + 2R n (F) + (b − a) 2 log(2/δ) n , for any f ∈ F . Also, with probability at least 1 − δ, P n f ≤ P f + 2R n (F) + (b − a) 2 log(2/δ) n , for any f ∈ F .
Proof. Consider the empirical process sup f ∈F (P f − P n f ). By McDiarmid's inequality, with probability at least 1 − δ, The basic property of Rademacher complexity ensures that Combining eqs. (88) and (89), we finish the proof.

G.2 Concentration with Local Rademacher complexity
In this part, we present some auxiliary results regarding local Rademacher complexity. In particular, Lemma G.2 guarantees the well-definedness of critical radius, Theorem G.3 provides concentration inequalities and Lemma G.5 gives some useful properties of sub-root functions.

G.2.1 Well-definedness of critical radius
Recall that in Definition 2.3, the critical radius r ⋆ of local Rademacher complexity R ρ n ({f ∈ F | T (f ) ≤ r}) is defined as the possitive fixed point of some sub-root functions ψ(r). The following Lemma G.2 ensures that r ⋆ exists and is unique.

G.2.2 Concentration inequalities
Throughout the paper, we use Theorem G.3 below to prove uniform concentration with local Rademacher complexity. Theorem G.3 is a variant of Theorem 3.3 in Bartlett et al. [2005]. Theorem G.3 (Corollary of Theorem 3.3 in Bartlett et al. [2005]). Let F be a class of functions with ranges in [a, b] and assume that there are some functional T : F → R + and some constants B and η such that for every f ∈ F, Var[f ] ≤ T (f ) ≤ B(P f + η). Let ψ be a sub-root function and let r ⋆ be the fixed point of ψ. Assume that ψ satisfies, for any r ≥ r ⋆ , ψ(r) ≥ BR n f ∈ F T (f ) ≤ r . Then for any θ > 1, with probability at least 1 − δ, P f ≤ θ θ − 1 P n f + c 1 θ B r ⋆ + c 2 (b − a) + c 3 Bθ log(1/δ) n + η θ − 1 , for any f ∈ F .