{'fraction_non_alphanumeric': 0.056135023759291754, 'fraction_numerical': 0.019382061241792693, 'mean_word_length': 3.874855824682814, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 41, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient

This paper provides a statistical analysis of high-dimensional batch Reinforcement Learning (RL) using sparse linear function approximation. When there is a large number of candidate features, our result sheds light on the fact that sparsity-aware methods can make batch RL more sample efficient. We first consider the off-policy policy evaluation problem. To evaluate a new target policy, we analyze a Lasso fitted Q-evaluation method and establish a finite-sample error bound that has no polynomial dependence on the ambient dimension. To reduce the Lasso bias, we further propose a post model-selection estimator that applies fitted Q-evaluation to the features selected via group Lasso. Under an additional signal strength assumption, we derive a sharper instance-dependent error bound that depends on a divergence function measuring the distribution mismatch between the data distribution and occupancy measure of the target policy. Further, we study the Lasso fitted Q-iteration for batch policy optimization and establish a finite-sample error bound depending on the ratio between the number of relevant features and restricted minimal eigenvalue of the data's covariance. In the end, we complement the results with minimax lower bounds for batch-data policy evaluation/optimization that nearly match our upper bounds. The results suggest that having well-conditioned data is crucial for sparse batch policy learning.


Introduction
We consider batch reinforcement learning (RL), where the problem is to evaluate a target policy or to learn a good policy based on a given dataset [Szepesvári, 2010, Lange et al., 2012. While in online RL the central question is how to sequentially interact with the environment to balance exploration and exploitation, in batch RL the dataset is given a priori and the focus is typically on learning a near-optimal policy or evaluating a given target policy.
To handle RL systems with large or even infinite state spaces, we focus on the use of linear function approximation [Bellman et al., 1963, Schweitzer and Seidmann, 1985, Bertsekas and Tsitsiklis, 1996, that is, using a weighted linear combination of available features (aka basis functions) to represent high-dimensional transition/value functions. Results from the supervised learning literature show that the sample size needed to get accurate policy evaluations or near-optimal policies must scale at least linearly with d, the number of features [e.g., Example 15.14 of Wainwright, 2019].
We leverage the idea of sparse approximation and focus on situations when a smaller number of unknown relevant features is sufficient for solving the RL problem. Sparse regression has proved to be a powerful method for high-dimensional statistical learning with limited data [Tibshirani, 1996, Chen et al., 2001, Bunea et al., 2007, Bickel et al., 2009, Rish and Grabarnik, 2014, and we will borrow techniques from the sparse learning literature to improve the sample efficiency of batch RL, an idea with a considerable history in RL as witnessed by our literature review that follows below.

Contributions
First, we consider the problem of off-policy policy evaluation (OPE), where the objective is to estimate the value function of a target policy from batch episodes that were generated from a possibly different behavior policy. To promote sparse solutions, we use fitted value iteration that iteratively fits state-action value functions using linear regression with 1 -regularization. We call this procedure as Lasso fitted Q-evaluation (Algorithm 1). For the analysis of our methods we introduce the novel notion of sparse linear MDPs and then establish a finite-sample error bound for Lasso fitted Q-evaluation in sparse linear MDPs that depends linearly on the number of relevant features and the restricted minimal eigenvalue. Importantly, the bound has no polynomial dependence on d, as long as the true MDP model is sparse. This appears to be the first theoretical bound for sparse batch policy evaluation.
Second, to reduce the Lasso bias, we propose an improved post model-selection estimator (Algorithm 2) that applies fitted Q-evaluation with a smaller feature set that is selected using group Lasso. Under an additional separability assumption, we derive a sharper and nearly minimax-optimal error bound that is instance-dependent. The error bound is determined by a divergence function measuring the distribution mismatch, restricted over the reduced feature space, between the data distribution and the occupancy distribution of the target policy. This divergence defined over the reduced feature space is significantly smaller than its counterpart over the full d-dimensional space. In other words, sparse feature selection reduces the distribution mismatch. We also provide a nearly-matching lower bound, and these two results sharply characterize the statistical limits of sparse off-policy evaluation.
We extend our analysis to the batch policy optimization problem, again in sparse linear MDPs. We analyze the Lasso fitted Q-iteration (Algorithm 3) and show that the ∞ -norm of policy error depends linearly on the ratio between the number of relevant features and the restricted minimal eigenvalue of the dataset's covariance matrix. Finally, we establish a minimax lower bound for sparse batch policy learning and show that the lower bound also depends on the aforementioned ratio. This is the first lower bound result, to the authors' best knowledge, demonstrating the critical role played by the minimal eigenvalue of the dataset's covariance matrix and the construction is highly non-trivial. The upper and lower bounds validate the belief that well-conditioned data is crucial for sample-efficient policy learning.

Related work
Off-policy policy evaluation (OPE). OPE often serves the starting point of batch RL. A direct approach was to fit value function from data using approximate dynamic programming, e.g., the policy evaluation analog of fitted Q-iteration [Ernst et al., 2005, Le et al., 2019 or least square policy iteration [Lagoudakis and Parr, 2003]. Another popular class of OPE methods used importance sampling to get unbiased value estimate of a new policy [Precup et al., 2000] and improved by doubly-robust technique to reduce the variance [Jiang and Li, 2016, Thomas andBrunskill, 2016]. To alleviate the curse of horizon [Li et al., 2015, Jiang and Li, 2016, Yin and Wang, 2020, marginalized importance sampling was suggested by estimating state marginal importance ratio without reweighting the entire trajectory [Hallak and Mannor, 2017, Liu et al., 2018, Xie et al., 2019. In general, estimating marginalized importance ratio could be sample-expensive and even intractable. Recently, practical duality-inspired methods were developed for estimating this ratio using function approximation [Nachum et al., 2019, Uehara and Jiang, 2019, Zhang et al., 2020a,b, Yang et al., 2020.
On the theoretical side, Uehara and Jiang [2019], Yin and Wang [2020], Kallus and Uehara [2020] established asymptotic optimality and efficiency for OPE in the tabular setting. Duan and Wang [2020] showed that fitted Q-evaluation with linear function approximation is minimax optimal and provided matching upper and lower bounds that depend on a distribution mismatch term. Another closely related work was by Le et al. [2019] who studied batch policy evaluation and optimization with more general function approximation. They showed the complexity of batch RL depends on the complexity of the function class, assuming a "concentration coefficient" condition ] that the state-action visitation density is bounded entrywisely across policies. More recently, Uehara and Jiang [2019] provided theoretical investigations into OPE using general function approximators for marginalized importance weights and value functions but did not show the statistical optimality.
Sparse learning in RL. The use of feature selection by regularization in RL has been explored in a number of prior works. Kolter and Ng [2009], Geist and Scherrer [2011], Hoffman et al. [2011], Painter-Wakefield and Parr [2012] studied on-policy evaluation with 1 -regularization for temporal-difference (TD) learning but none of them come with a theoretical analysis. Liu et al. [2012] studied off-policy evaluation by regularized TD learning but only provided algorithmic convergence guarantee without statistical error analysis. Ghavamzadeh et al. [2011], Geist et al. [2012 proposed Lasso-TD with finite-sample statistical analysis for estimating the value function in Markov reward process. In particular, they derived in-sample prediction error bound O((s log(d)/ψn) 1/2 ) under ψ-minimum eigenvalue condition on the empirical feature gram matrix. Although this bound also has no polynomial dependency on d, in-sample prediction error generally can not be translated to the estimation error of target policy in the OPE problem and their bound can not characterize the distribution mismatch between behavior policy and target policy. On the other hand, no minimax lower bound has been investigated so far.
In addition, Farahmand et al. [2008,2016] considered 2 -regularization in fitted Q-iteration/policy iteration for policy optimization in a reproducing kernel Hilbert space, and finite-sample performance bounds for these algorithms were proved built on a coefficient concentration condition. Calandriello et al. [2014] developed Lasso fitted Q-iteration for sparse multi-task reinforcement learning and assumed a generative model [Kakade et al., 2003]  T ) regret bound in high-dimensional sparse linear quadratic systems where p is the dimension of the state space.
Sparse linear regression. Sparse regression receives considerable attention in high-dimensional statistics in the past decade. Lasso [Tibshirani, 1996], is arguably the most widely used method to conduct sparse regression. Theoretical analysis of Lasso is well-studied in Zhao and Yu [2006], Bickel et al. [2009], Wainwright [2009. For a thorough review of Lasso as well as high-dimensional statistics, we refer the readers to Hastie et al. [2015], Wainwright [2019], Bühlmann and Van De Geer [2011]. However, extending existing analysis from regression to batch RL is much more involved due to the complex optimization structure, non-i.i.d data collection, and covariate shift.

Preliminaries
Notations. Denote [n] = {1, 2, . . . , n}. We identify vectors and functions in the obvious way by fixing an (arbitrary) ordering over the domain of the function. Similarly, for S finite and A ∈ R S×S will be treated as an |S| × |S| matrix. For a vector x ∈ R d , a matrix X ∈ R d×d and an index set S ⊆ [d], we define x S = (x j ) j∈S ∈ R S be the subvector over the restricted index set S and X S×S = (X ij ) i,j∈S ∈ R S×S . We write X j· as the jth row of X. Denote λ min (X), λ max (X) the smallest and largest eigenvalues of a symmetric matrix X. Denote , as "approximately less/greater than", omitting non-leading order terms (constant and polylog factors). For a set S let ∆ S denote the set of probability distributions over S.

Problem definition
A finite, infinite-horizon discounted Markov decision process (DMDP) can be described by the tuple M = (X , A, P, r, γ). Here, X is a finite set of states, A is a finite set of actions, P : X × A → ∆ X is the transition probability function, r : X × A → [0, 1] is the reward function and γ ∈ (0, 1) is the so-called discount factor. In this paper, for the sake of simplicity, we stick to finite DMDPs. However, our results can be extended to more general cases with routine work.
We define a (stationary) policy π as a X → ∆ A map, mapping states to distributions over actions. A policy, a distribution ξ 0 over X and a DMDP M together give rise to a probability measure P π over the set of infinitely long state-action histories: for a history of form x 1 , a 1 , r 1 , x 2 , a 2 , r 2 , . . . , P π (x 1 ) = ξ 0 (x 1 ) and for t = 1, 2, . . . , P π (a t |x 1 , a 1 , . . . , x t−1 , a t−1 , x t ) = π(a t |x t ) and P π (x t+1 |x 1 , a 1 , . . . , x t−1 , a t−1 , x t , a t ) = P (x t+1 |x t , a t ). We denote by E π the corresponding expectation operator. The value of policy π given the initial state distribution ξ 0 is v π , where E π depends on ξ 0 but just this dependence is not shown. We define v π : X → R, the value function of policy π, by letting v π (x) denote the value of π when it is started from state x.
A nonstationary policy is a sequence of maps from histories to probability distributions over actions and such a policy similarly induces a probability measure P π and an underlying expectation operator E π . An optimal policy π * maximizes the value from every state: v π * (x) = max π v π (x) for any x ∈ X where the maximum is over all policies, including nonstationary ones. As is well known, for finite DMDPs, a stationary optimal policy always exist [e.g., Szepesvári, 2010]. The value function shared by optimal policies is called the optimal value function and is denoted by v * .
We consider the following learning and optimization problems. The learner knows the state space X and action space A. The reward function r is given in the form of a black box, which the learner can use to evaluate r(x, a) for any pair of (x, a) ∈ X × A. The only unknown is the transition probability function P .
The learner is given a random dataset D = {(x n , a n , x n )} N n=1 generated by using a (possibly nonstationary and unknown) behavior policyπ in the DMDP M starting from some initial distribution which may be different from ξ 0 . We study two fundamental batch RL tasks: • Off-policy policy evaluation: given D and black box access to a target policy π, ξ 0 and r, estimate the value, v π ξ 0 , of π; • Batch policy optimization: given D and black box access to r, find an optimal policy.
Bellman operators. By slightly abusing the notation, we will view the transition probability kernel P as a left linear operator, mapping from R X to R X ×A : The Bellman optimality operator T : R X → R X is defined as The function v * ∈ R X is the unique solution to the Bellman optimality equation v = T v. The state-action value function of a policy π is defined as We also introduce the Bellman operator T π : R X → R X for policy π as: The function v π is the unique solution to the Bellman equation v π = T π v π .

Sparse linear Markov decision process
Bellman's curse of dimensionality refers to that DMDPs tend to have a state space where individual states have many components that can take on many values, hence the state space is intractably large. An early idea due to Bellman et al. [1963], Schweitzer andSeidmann [1985] is to use linear combination of finitely many, say, d basis functions, to express value functions and thus allow for computation and storage that is independent of the size of the state-space. Following this idea, let φ : X × A → R d be a feature map which assigns to each state-action pair a d-dimensional feature vector. A feature map combined with a parameter vector w ∈ R d gives rise to the linear function g w : X × A → R defined by g w (x, a) = φ(x, a) w, (x, a) ∈ X × A, and the subspace G φ = {g w : w ∈ R d } ⊆ R X ×A . Fix a feature map φ. For f : X × A → R, let f π : X → R be defined by f π (x) = a π(a|x)f (x, a). The idea of Bellman et al. [1963], Schweitzer andSeidmann [1985] to use features to find optimal policies with computation whose cost only depends on d and not on the cardinality of X , boosted with the use of action-value functions, can be formally justified in DMDPs such that G φ is closed under the application of any of the operators T π : X × A → X × A, T π f → r + γP f π for any policy π of the DMDP. This leads to the definition of linear DMDPs 1 [Yang and Wang, 2019, Jin et al., 2019, Agarwal et al., 2020a. Slightly deviating from the original definitions, here we say that a DMDP is linear if for some feature map φ, G φ is closed under the operators f → P f π for any policy π of the DMDP. The following is an immediate corollary of the definitions and forms the basis of our methods: Proposition 2.1. Let M be linear under φ and π a policy for M . Then, there exists some w ∈ R d such that g w = P v π and v π = r π + γg π w . Further, w also satisfies the linear equation g w = P r π + γP g π w . Conversely, if w satisfies this last equation then v π = r π + γg π w .
When little a priori information is available on how to choose the features, agnostic choices often lead to dimensions which can be as large as the number of samples n, if not larger. Without further assumptions, no procedure can achieve nontrivial performance guaranteed even when just considering simple prediction problems (e.g., predicting immediate rewards). However, effective learning with many more features than the sample-size is possible when only s d features are relevant. This motivates our assumption of sparse linear DMDPs.
We denote by M φ,s (X , A, γ) the set of all (s, φ)-sparse DMDP instances. Our second assumption concerns the dataset: Assumption 2.3. The dataset D consists of N = KL samples from K independent episodes τ 1 , . . . , τ K . Each episode τ k has L consecutive transitions generated by some unknown behavior policyπ k giving rise to a sample path τ k = (x

Sparsity-Aware Off-Policy Policy Evaluation
In this section we consider the off-policy policy evaluation (OPE) problem, i.e., to estimate the value of a target policy π from logged experiences D generated using unknown behavior policies. We propose two sparsity-aware algorithms to approximate state-action functions using sparse parameters.

Lasso fitted Q-evaluation
We propose a straightforward modification of the fitted Q-evaluation method [Le et al., 2019, Duan andWang, 2020] to account for sparsity. For t = 1, 2, . . . , T − 1, the algorithm produces w t+1 using Lasso-regularized regression so that g w t+1 ≈ P ((r + γg wt ) π ). To make the errors of different steps independent, the dataset D is split into T nonoverlapping folds D 1 , . . . , D T , so that all folds have R = K/T episodes in them and only data from fold t is used in step t. To define the algorithm, it is useful to introduce Q w = r + γg w where w ∈ R d . For a < b, we also define the operator Π [a,b] : R → [a, b] that projects its input to [a, b], i.e., Π [a,b] (x) = max(min(x, b), a). The pseudocode is given as Algorithm 1. In the last step, m = N samples 1 A different definition is called linear kernel MDP that the MDP transition kernel can be parameterized by a small number of parameters [Yang and Wang, 2020, Cai et al., 2019, Zanette et al., 2020, Zhou et al., 2020. are used to produce the final output to guarantee that the error introduced by the Monte-Carlo averaging is negligible compared to the rest.
Remark 3.1. The last step Monte Carlo averaging is only for numerical integration, where the samples are newly drawn inside the algorithm (independent from batch data), so there is no bias here. We set m = N to simplify the theory but it could be much larger than N for a more accurate approximation.

4:
Fit w t through sparse linear regression

Post model-selection fitted Q-evaluation
Sparse regularization is known to induce a small bias in regression. However, this bias could get compounded through the iterative procedure of Algorithm 1. To avoid such bias and improve the accuracy, we aim to identify the set of relevant features K before evaluating the policy based on the following proposition.
where φ π (x) = a π(a|x)φ(x, a) and all but s rows of K π are identically zero. This K π ∈ R d×d is known as the matrix mean embedding [Duan and Wang, 2020].
Thus we propose to estimate the set of relevant features K using group lasso [Yuan and Lin, 2006]. Once the relevant feature set is identified, any regular policy evaluation method can be used over the learned feature set K. In Algorithm 2, for the ease of comparability with the previous method, we consider vanilla fitted Q-evaluation.
Remark 3.3. One may wonder whether it is necessary to refit the iterative regression and why not simply use the estimated K π to get a plug-in estimator. This is because refitting typically performs strictly better than direct regularized learning and has less bias, as long as the feature selection succeeds [Belloni et al., 2013]. Algorithm 2 Post model-selection fitted Q-evaluation 1: Input: initial distribution ξ 0 , target policy π, dataset D of size N , m := N , number of iterations T , λ 2 , λ 3 > 0.

Performance Bounds For Sparse Off-Policy Evaluation
We study the finite-sample estimation error of Algorithms 1, 2. All the technical proofs are deferred to the Appendix. Let Σ be the expected uncentered covariance matrix of the batch data, given by where L is the length of one episode. We need a notion of restricted eigenvalue that is common in highdimensional statistics [Bickel et al., 2009, Bühlmann andVan De Geer, 2011].
Remark 4.2. The restricted eigenvalue C min (Σ, s) characterizes the quality of the distribution that generates the batch data set D. We need C min (Σ, s) > 0 meaning that the data is well-conditioned or the behavior policy provides good coverage over relevant features. This is a key condition to guarantee the success of sparse feature selection [Bickel et al., 2009]

Finite-sample error bounds of Algorithm 1
We first provide a statistical error bound for the Lasso fitted Q-evaluation (Algorithm 1).
Theorem 4.3 (OPE error bound for Algorithm 1). Suppose Assumptions 2.2, 2.3 hold and C min (Σ, s) > 0. Let Algorithm 1 take N samples satisfying N s ( 4.2) Theorem 4.3 shows that the OPE error for sparse linear DMDPs depends linearly on s/C min (Σ, s). For comparison, when the linear DMDPs model is not sparse, Duan and Wang [2020] proved the error bound (using our notations) of the form From the Definition 4.1, C min (Σ, d) < C min (Σ, s). Comparing the two results (setting δ = 1/N ), we expect the new error bound to be significantly tighter , i.e., C min (Σ, d) s 2 log(dN ) 1−γ C 2 min (Σ, s)d, when there is a high level of sparsity (s d).

Finite-sample error bounds of Algorithm 2
Next, we give a result for the post-selection model estimator for OPE (Algorithm 2). We will show that this algorithm provides a more accurate estimate under the additional condition that every relevant feature plays a nontrivial role in the transition dynamics.
Assumption 4.4 (Minimal signal strength). For some given δ > 0, the minimum signal strength satisfies where K π j· is the jth row of K π defined in Eq. (3.1).
Then we provide a critical lemma showing that the group lasso step in Algorithm 2 is guaranteed to identify a sufficiently sparse feature set including all the relevant features with high probability.
Lemma 4.5 (Feature screening). Suppose Assumptions 2.2, 2.3, 4.4 hold and C min (Σ, s) > 0. Set the regularization parameter λ 2 = 4 2 log(2d 2 /δ)/(N d) for some δ > 0 and let the sample size satisfy N Ls 2 log(d/δ)/C 2 min (Σ, s). Then with probability at least 1 − δ, the size of learned relevant feature set K satisfies | K| s and K ⊇ K where K is the true relevant feature set of M . Now we analyze the policy evaluation error of Algorithm 2. According to Cramer-Rao lower bound for tabular OPE [Jiang and Li, 2016] and the minimax lower bound for OPE with linear function approximation [Duan and Wang, 2020], we expect the optimal OPE error to depend on the distribution mismatch between the target policy and the behavior policy that generated the data. To define the notion of distribution mismatch, we first need the notion of occupancy measures: Definition 4.6 (Occupancy measures). Letμ be the expected occupancy measure of observations {(x n , a n )} N n=1 : µ(x, a) = N n=1 P(x n = x, a n = a)/N and µ π be the discounted occupancy distribution of (x h , a h ) under policy π and initial distribution ξ 0 : , ∀ x, a. Inspired by Theorem 5 of Duan and Wang [2020], we will measure the distribution mismatch using restricted chi-square divergences betweenμ and µ π .
Definition 4.7 (Restricted chi-square divergence). Let G be a set of real-valued functions over X and let p 1 and p 2 be probability distributions over X . We define the G-restricted chi-square divergence (or χ 2 G -divergence) between p 1 and p 2 as By using the feature screening Lemma 4.5, and a similar analysis as by Duan and Wang [2020], we obtain the following instance-dependent error bound for sparse off-policy evaluation.
Theorem 4.8 (Instance-dependent error bound for sparse OPE). Suppose Assumptions 2.2, 2.3, 4.4 hold and C min (Σ, s) > 0. Let δ ∈ (0, 1) and assume that Algorithm 2 is fed with N samples satisfy- Letting the number of iterations T → ∞, the following holds with probability at least 1 − 3δ, whereμ is the data generating distribution, G( K) is the reduced feature space.
Remark 4.9 (Reduced distribution mismatch via sparse feature selection.). The OPE error bound of Theorem 4.8 depends on the statistics χ 2 G( K) (µ π ,μ) that quantifies the distribution mismatch between data and the target policy. This result implies the uncertainty for evaluating a new policy from batch data crucially and jointly depends on the two distributions as well as the function class used for fitting. When K is a small subset of [d], we have χ 2 . Therefore our instance-dependent error bound is expected to be significantly smaller than its counterpart that does not exploit sparsity.

Minimax lower bound for OPE
To complete the picture, we provide a minimax lower bound of off-policy evaluation for the class of sparse linear DMDPs M φ,s (X , A, γ) (Assumption 2.2). The proof is an adaptation of the respective lower bound proof for linear MDPs (Theorem 3 in Duan and Wang [2020]). It implies the bound in Theorem 4.8 is nearly minimax-optimal.
Theorem 4.10 (Minimax lower bound for sparse policy evaluation). Suppose Assumption 2.3 holds. If where φ ∈ (R d ) X ×A , P M is the probability measure under the DMDP instance M and v π (·) sweeps through all algorithms that estimate values based on data D.
Remark 4.11. It is worth to mention that in Theorem 4.10, the distribution mismatch term 1 + χ 2 G(K) (µ π ,μ) may also contain a 1 − γ term in the worse case. Thus the lower bound of sparse off-policy policy evaluation also has a 1/(1 − γ) 3 dependency in the worse case that matches the result for the lower bound of sparse batch policy optimization in Theorem 5.2.

Sparsity-Aware Batch Policy Optimization
We extend our analysis to batch policy learning problem for sparse linear DMDPs. Consider the Lasso fitted Q-iteration (see Algorithm 3) that has been studied in Calandriello et al. [2014] as a special case of an algorithm for sparse multi-task RL. It resembles Algorithm 1 except for that it calculates the regression target with an additional "max" operation. The next theorem proves the approximate optimality of the learned policy using Lasso fitted Q-iteration.
Theorem 5.1 (Approximate optimality of the learned policy). Suppose Assumptions 2.2, 2.3 hold and (5.1) Theorem 5.1 suggests that the sample size needed to get a good policy depends mainly on the number of relevant features s, instead of the large ambient dimension d, provided that the data is well-conditioned. This result is not surprising: Calandriello et al. [2014] gave a similar upper bound for sparse FQI for the setting of generative model. Le et al. [2019] provided a generalization theory for policy evaluation/learning with a general function class and their error bound depends on the VC-dimension of the class, but it requires a stronger coefficient concentration condition.
In the end, we study the fundamental limits of sparse batch policy learning. We establish an informationtheoretic minimax lower bound that nearly match the aforementioned upper bound.
Theorem 5.2 (Minimax lower bound for batch policy optimization in sparse linear DMDPs). Suppose Assumption 2.3 holds and γ ≥ 2 3 . Let π denote an algorithm that maps dataset D to a policy π(D). If N sL(1 − γ) −1 , then for any π, there always exists a DMDP instance Theorems 5.1, 5.2 show that the statistical error of batch policy learning is fundamentally determined by the ratio s/C min (Σ, s). Note that there remains a gap s/C min (Σ, s) between Theorems 5.1 and 5.2, due to the nature of Lasso regression.
Remark 5.3 (Role of the minimal eigenvalue and well-conditioned data.). Earlier results such as those of , Antos et al. [2008], Le et al. [2019] require stronger forms of concentration condition that the state-action occupancy measure (or a ratio involving this measure) is entrywisely bounded across all policies. Such entrywise bound can be very large if the state-action space X is large. In contrast, our results only require that the data's covariance Σ is well-conditioned on restricted supports, which is a much weaker assumption. Further, one can use the empirical minimal eigenvalue to get a rough error estimate. Theorem 5.2 further validates that the minimal eigenvalue indeed determines the statistical limit of batch policy optimization. The result is the first of its kind to our best knowledge.

Experiment
In this section, we conducted some preliminary experiments with a Mountain Car [Moore, 1990] example to demonstrate the advantage of sparse learning in OPE problem. We use 800 radial basis functions for linear value function approximation and compare our Lasso-FQE with the standard FQE. We pick the random policy as the behavior one and a near-optimal policy as the target, and we measure the estimation error by | v − v * |/|v * |. We constructed multiple behavior policies with varying levels of -greedy noise, and plot their OPE error against their (restricted) χ 2 -divergence from the target policy. The results are averaged by 20 runs and summarized in Figure G in the appendix. It shows that our Lasso-FQE clearly has smaller estimation error compared with FQE, proving the sparse feature selection is effective in a practical RL example, and demonstrates how the distribution mismatch (χ 2 -divergence term) affects OPE error (with sample size fixed). The results confirm our theorems that the (restricted) chi-square divergence sharply determines the (sparse) OPE error.

Conclusion
In this work we focus on high-dimensional batch RL using sparse linear function approximation. While previous work in RL recognized the possibility of bringing tools from sparse learning to RL, they lacked a clean theoretical framework and formal results. By building on the strength of the linear DMDP framework, our result show that learning and planning in linear DMDPs can be done in the "feature space" even in the presence of sparsity and when only batch data is available. The appendix is organized as follows.
• Appendix A. Proofs of Propositions 2.1 and 3.2: properties of linear MDPs.
• Appendix B. Proofs of results about off-policy policy evaluation in Section 4.
• Appendix C. Proof of Theorem 5.1: upper bound of batch policy optimization.
• Appendix D. Proof of Theorem 5.2: minimax lower bound of batch policy optimiztion.
• Appendix E. Proofs of auxiliary lemmas.
• Appendix G. Results of experiments.

A Proofs concerning linear MDPs
Proof of Proposition 2.1. Let Q π = r + γP v π . Then, v π = Q π π , and hence since M is a linear MDP, P Q π π = g w with some w ∈ R d . Hence, P v π = g w . Furthermore, by its definition thus Q π = r + γg w . Then, applying (·) π on both sides and using again Q π π = v π , we get v π = r π + γg π w , which finishes the proof of the first part. Now, if w is as above, g w = P v π = P (r π + γ(P v π ) π ) = P (r π + γg π w ) = P r π + γP g π w . Finally, assuming that w satisfies the last identity, defining Q = r + γg w , we have Q = r + γ(P r π + γP g π w ) = r + γ(P (r + γg w ) π ) = r + γP Q π . As is well known, the unique fixed point of this equation is Q π . Hence, Q = Q π .
Proof of Proposition 3.2. Fix a policy π. Since M is a linear MDP, for every i ∈ [d] there exist w i ∈ R d such that P φ π i = g w i . Thus, for any (x, a) ∈ X × A, Thus, Eq. (3.1) holds if we choose Under the sparsity assumption, Assumption 2.2, there exists K ⊂ [d] such that w ij = 0 when j ∈ K. This shows that all but |K| rows of K π are identically zero, finishing the proof.

B Proofs of off-policy policy evaluation B.1 Proof of Theorem 4.3: lasso fitted Q-evaluation
Recall that we split the whole dataset D into T folds and each fold consists of R episodes or RL sample transitions. At tth phase, only the fresh fold of dataset Step 1: Approximate value iteration. We first show that the execution of Algorithm 1 is equivalent to approximate value iteration. Denote a Lasso estimator with respect to a function V at tth phase: Note that w t (·) only depends data collected at the tth phase. Define the parameterized value function as Define an approximate Bellman operator for target policy π, i.e. T

(t)
π : R X → R X as: π is a randomized operator that only depends data in the tth fold. It is easy to see that if ( w t ) T t=1 is the sequence of weights computed in Algorithm 1 then w t = w t (Π [0,1/(1−γ)] V π w t−1 ) and also Step 2: Linear representation of Bellman operator. Recall that the true Bellman operator for target policy π, i.e. T π : R X → R X is defined as We first verify for each phase t ∈ [T ], T π Π [0,1/(1−γ)] V π wt has a linear representation. From Assumption 2.2, it holds that For a vectorw t ∈ R d , we define its kth coordinate as It shows that T π Π [0,1/(1−γ)] V π wt has a linear representation if the reward could also be linearly represented. For notation simplicity, we drop the supscript of x (t) i and a (t) i for the following derivations when there is no ambiguity.
Step 3: Sparse linear regression. We interpretw t as the ground truth of the lasso estimator in Algorithm 1 at phase t, in terms of the following sparse linear regression: Therefore, {ε i } RL n=1 is a sequence of martingale difference noises and |ε i | ≤ 1/(1 − γ) due to the truncation operator Π [0,1/(1−γ)] . The next lemma bounds the difference between w t andw t within 1 -norm. The proof is deferred to Appendix E.2.
Step 4: Error decomposition. Recall that v π w T = 1 m m u=1 Π [0,1/(1−γ)] (Q w T ( x u , a u )) and we denotē v π w T = x V π w T (x)ξ 0 (x). According to Eq. (B.3), we decompose the policy evaluation error by Monte Carlo error, estimation error and approximation error as follows: Since x u , a u is i.i.d sampled from ξ 0 and π, standard Hoeffding's inequality shows that To bound the estimation error, combining Eqs. (B.2) and (B.6) together, we have

(B.11)
To bound approximation error, we expand it by Eq. (B.4): According to Eq. (B.11), we decompose This implies Combining Eqs. (B.9), (B.11) and (B.12) together, we have Iteratively implementing the above decomposition, we have Since we assume φ(x, a) ∞ ≤ 1, then ν π t ∞ ≤ 1 as well. Using the fact that T −1 Suppose the sample size satisfies holds with probability at least 1 − T δ. By elementary change of base formula and Taylor expansion, we have By properly choosing T = Θ(log(N/(1 − γ))/(1 − γ)), we have with probability at least 1 − δ, where we use N = T RL. Combining with Monte Carlo approximation error Eq. (B.10) This ends the proof.

B.2 Proof of Lemma 4.5: feature selection
We study the feature screening and sparsity properties of the model selected by the regularized estimator K π .
• Denote the design matrix as Note that X is a block diagonal matrix.
• For every β ∈ R d 2 , we define β j = (β j+(i−1)d : i ∈ [d]) as the vector formed by the coefficients corresponding to the jth variable. For instance, β * j is the jth row of K π . If J ⊆ [d], denote β J ∈ R d 2 by stacking the vectors β j 1{j ∈ J}. Write S(β) = {j : β j = 0} as the relevant feature set of β.
• For a vector β ∈ R d 2 , define the 2,p -norm for 1 ≤ p < ∞ as: , and the 2,0 -norm as: Therefore, we can rewrite Eq. (B.13) into an ordinary linear regression form with group sparse structure on the regression coefficients β * : Y = Xβ * + W.
Note that S(β * ) = K where K is defined in Assumption 2.2 since K π is row-sparse. The corresponding group lasso estimator defined in Eq. (3.2) can be rewritten into: and S( β) = K. The regularization parameter is chosen as for some δ > 0. Now we study the feature screening property of β in four steps.
Step 1. By the optimality of β, we have where the last inequality is from Hölder's inequality.
Step 2. Next, we will bound the noise term: (X W ) j 2 . From the definitions of X and W , we write it explicitly as It is easy to verify that {φ j (x n , a n )ε ni } N n=1 is also a martingale difference sequence for any i, j ∈ [d] and |φ j (x n , a n )ε ni | ≤ 1 since we assume φ(x, a) ∞ ≤ 1 for any state-action pair. According to Azuma-Hoeffding inequality (Lemma F.2), for all δ > 0, Using the union bound twice, the following holds, Letting δ = 2d 2 exp(− δ 2 /2N ), we have with probability at least 1 − δ,

Define an event A as
Then we have P(A) ≥ 1 − δ.
Step 3. According to Karush-Kuhn-Tucker (KKT) condition, the solution β of the optimization problem Eq. (B.14) satisfies Under event A and using KKT condition, we have if β j = 0, then (B.18) We define a notation of restricted maximum eigenvalue with respect to S(β * ) and X:  (B.21) holds with probability at least 1 − δ.
Step 4. It remains to control the in-sample prediction error X( β − β * ) 2 2 . Under event A, using Eq. (B.16) implies Adding d j=1 β j − β * j 2 λ 2 /2 to both sides and using the fact that β * j − β * j 2 + β j 2 − β j 2 = 0 for j = S(β * ), we have where the last inequality is from Cauchy-Schwarz inequality. Recall that the expected uncentered covariance matrix is defined as and we define the empirical uncentered covariance matrix as φ(x n , a n )φ(x n , a n ) = 1 K with N = KL. Denote the expected and empirical uncentered covariance matrices for the multivariate linear regression as We introduce a generalization of restricted eigenvalue condition (Definition 4.1) for multivariate linear regression.
Next lemma provides a lower bound for C min ( Φ, s). The proof is deferred to Appendix E.1.
. Given a positive semi-definite matrix Z ∈ R d×d and integer s ≥ 1, the restricted maximum eigenvalue of Z are defined as Using the definition of C max ( Σ, s), it holds that Summing the above inequality from 1 to d, This implies C max ( m) ≤ C max ( Σ, m). As shown in the Lemma 1 in Belloni et al. [2013], we have C max ( Σ, m) ≤ 4C max (Σ, m) for any m + s ≤ log(n) as long as n s.
Step 5. Recall that m = |S( β) \ S(β * )| and denote Suppose there is a m 0 ∈ M such that m > m 0 . From Eq. (B.25), we know that According to Lemma 3 in Belloni et al. [2013] for the sublinearity of sparse maximum eigenvalues, we have where the last inequality we use κ ≤ 2κ. Putting the above two results together, we have This leads a contradiction with the definition of M. Therefore, m ≤ m 0 for all m 0 ∈ M. This implies The term min m 0 ∈M C max (Σ, m 0 )/C min (Σ, s) essentially characterizes the condition number of Σ on a restricted support and is upper bounded by the condition number defined in the full support. Now we finish the proof of the first part of Lemma 4.5 and start to prove the second part of Lemma 4.5 under separability condition. According to Eq. (B.23), under event A we have From Eq. (B.24), Combining the above two inequality together and plugging in the choice of λ 2 , we can bound with probability at least 1 − δ. Under Assumption 4.4, the following holds that with probability at least 1 − δ, If there is a j ∈ S(β * ) but j / ∈ S( β), we have On the other hand, which leads a contradiction. Now we conclude that S( β) ⊇ K. This ends the proof.

B.3 Proof of Theorem 4.8: instance-dependent upper bound
We restate the instance-dependent error bound error bound of vanilla fitted Q-evaluation algorithm on the full support.
Theorem B.4 (Theorem 5 in Duan and Wang [2020]). Assume the DMDPs satisfy Assumption 2.2 and batch dataset satisfy Assumption 2.2. Suppose φ(x, a) Σ −1 φ(x, a) d for any pair of (x, a). Let δ ∈ (0, 1) and Algorithm 2 without feature selection stage takes N samples satisfying Set regularization parameter λ 3 = λ min (Σ) log(12d/δ)C 1 d/(1−γ). Letting the number of iteration T → ∞, the following holds with probability at least If the true relevant feature set K is known in an oracle case, we could directly run the algorithm on K such that all the dependency on d can be reduced to s and the instance-dependent term turns to be defined in the K that is much sharper than the original one. Fortunately, Lemma 4.5 implies K ⊇ K and | K| s. Suppose Rewriting Theorem B.4 with respect to K, we have where ν π t = [ν π t ] K and Σ = Σ K× K . The corresponding condition φ(x, a) Σ −1 φ(x, a) | K| can be satisfied due to C min (Σ, s) > 0 and φ(x, a) ∞ ≤ 1. From Definitions 4.6, 4.7 and Lemma B.2 in Duan and Wang [2020], we have Now we end the proof.
C Proof of Theorem 5.1: lasso fitted Q-iteration C.1 Proof of Theorem 5.1 The main structure of this proof is similar to the proof of Theorem 4.3 in Appendix B.1 but we need to utilize the contraction property of Bellman optimality operator. Recall that we split the whole dataset into T folds and each fold consists of R episodes or RL sample transitions. The overall sample size is N = T RL.
Step 1. We verify that the execution of Algorithm 3 is equivalent to the approximate value iteration. Recall that a generic Lasso estimator with respect to a function V at tth phase is defined in Eq. (B.1) as Define V w (x) = max a∈A (r(x, a) + γφ(x, a) w). For simplicity, we write w t := w t (V w t−1 ) for short. Define an approximate Bellman optimality operator T (t) : R X → R X as: Note this T (t) is a randomized operator that only depends data collected at tth phase. Algorithm 3 is equivalent to the following approximate value iteration: Recall that the true Bellman optimality operator T : R X → R X is defined as Step 2. We verify that the true Bellman operator on Π [0,1/(1−γ)] V w t−1 can also be written as a linear form. From Condition 2.2, there exists some functions ψ(·) = (ψ k (·)) k∈K such that for every x, a, x , the transition function can be represented as and |K| ≤ s. For a vectorw t ∈ R d , we define its kth coordinate as andw t,k = 0 if k / ∈ K. By the definition of true Bellman optimality operator in Eq. (C.3) and Eq. (C.4), Step 3. We start to bound V wt − v * ∞ for each phase t. By the approximate value iteration form Eq. (C.2) and the definition of optimal value function, (C.7) The first term mainly captures the error between approximate Bellman optimality operator and true Bellman optimality operator while the second term can be bounded by the contraction of true Bellman operator. From linear forms Eqs. (C.2) and (C.6), it holds for any x ∈ X , Applying Lemma B.1, with the choice of λ 1 = (1 − γ) −1 log(2d/δ)/RL, the following error bound holds with probability at least 1 − δ, where R satisfies R ≥ C 1 log(3d 2 /δ)s 2 /C min (Σ, s).
Note that the samples we use between phases are mutually independent. Thus Eq. (C.9) uniformly holds for all t ∈ [T ] with probability at least 1 − T δ. Plugging it into Eq. (C.8), we have for any phase t ∈ [T ], holds with probability at least 1 − δ.

D Proof of Theorem 5.2: minimax lower bound of policy optimization
We first restate the full statement of Theorem 5.2 and include an instance-dependent lower bound. Note that the worse-case lower bound Eq. (D.2) can be derived from instance-dependent lower bound Eq. (D.1) (See Appendix D.6.2 for details).
Full statement of Theorem 5.2 Suppose Assumption 2.3 holds and γ ≥ 2 3 . Let π denote an algorithm that maps dataset D to a policy π(D). If N sL(1 − γ) −1 , then for any π, there always exists an DMDP instance M ∈ M φ,s (X , A, γ) with feature φ ∈ (R d ) X ×A satisfying φ(x, a) ∞ ≤ 1 for all (x, a) ∈ X × A, then where µ * is the discounted state-action occupancy measure of π * . In addition, we have Remark Minimax sample complexity lower bound for solving MDP has been studied in the setting with a generative model that allows querying any (s, a) for independent samples. Azar et al. [2013] constructed a hard instance of tabular MDP and, by reducing policy optimization to a testing a Bernoulli distribution, proved a lower bound SA (1−γ) 3 which is known to be sharp. Yang and Wang [2019] extended the construction to linear MDP and show that the sample complexity lower bound is d (1−γ) 3 under a generative model. There also exists matching upper bound in the same setting.
Our Theorem 5.2 applies to the setting of batch episodic data where are highly dependent. Due to this major difference, we have to use a more intricate proof based on likelihood test to establish a minimax lower bound. Further, Theorem 5.2 characterizes for the first time that the lower bound depends on the minimal eigenvalue of the data's population covariance.

D.1 Reducing to likelihood test
We prove the minimax lower bound by conducting likelihood test. Similar to Lemma C.1 in Duan and Wang [2020], we have Lemma D.1 below.
Lemma D.1. Let M α and M β be two MDP instances with transition kernels p α (x | x, a) and p β (x | x, a). Suppose Assumption 2.3 holds. Define likelihood functions Denote P α the probability space generated by running M α following the behavioral policyπ. If P α then for any policy learning algorithm π, We learn from Lemma D.1 that as long as P α L β (D) Lα(D) ≥ 1 2 ≥ 1 2 and (D.3) hold, the lower bound is achieved at model M α or M β . In the following, we construct MDP models and analyze these two conditions separately.

D.2 Constructing MDP instances
We assume without loss of generality that the number of active features s is even. We consider a simplest case where the MDP only consists of two states, i.e. X = {x, x}. At each state, the agent chooses from s 2 + s(d − s) actions A = a 1 , a 2 , . . . , a s 2 ∪ ā i,k i = 1, 2, . . . , s 2 , k = ±1, ±2, . . . , ±(d − s) . Here, we only useā i,j in collecting the dataset D.
We first introduce Lemma D.2, which will be used in the construction of feature mapping φ : X ×A → R d .
Let Θ ∈ R s×s be the orthogonal matrix given in Lemma D.2. We fix K ⊆ [d] to be the active feature set and denote by φ K the corresponding coordinates of φ. We now construct φ K : X × A → R s as follows: For i = 1, 2, . . . , s 2 , k = ±1, ±2, . . . , ±(d − s), let where ς 1 , ς 2 ∈ (0, 1) will be determined later. By construction, we have φ K (x, a) ∞ ≤ 1 for any (x, a) ∈ X × A. Note that φ K abstracts all the dynamic informatrion for state-action pairs, and φ K c does not affect the transition model or reward function. Therefore, it is sufficient for us to use φ K when identifying the optimal policy or calculate value functions. We propose s Here, δ 1 , δ 2 ∈ 0, 2(1 − γ) are parameters reflecting the small differences among actions. The reward functions are the same for all models and are chosen as r(x, a i ) = r(x,ā i,k ) = 1, r(x, a i ) = r(x,ā i,k ) = 0, for i = 1, 2, . . . , s 2 , j = ±1, ±2, . . . , ±(d − s).

D.3 Analyzing the concentration of the likelihood ratio
We devise a behavior policyπ and verify the likelihood ratio condition under the data collecting scheme in Assumption 2.3. We start from an initial distributionξ 0 and take a behavior policyπ(ā i,k | x) =π(ā i,k | x) = Take and Parallel to Lemma C.3 in Duan and Wang [2020], we provide concentration results of the likelihood ratio in Lemma D.3. The proof can be found in Appendix E.2.1.

D.4 Calculating the gap in values
For model M i , the optimal policy is given by For computational simplicity, we take initial distribution ξ 0 := ξ 0 (x) ξ 0 (x) = 1 0 ∈ R 2 . In the following Lemma D.4, we provide an estimation for the difference between values of optimal and sub-optimal policies. See Appendix E.2.2 for the proof.
For model M i , x is an absorbing state under the optimal policy π * i . Therefore, µ * (x) = 1 and ν * K = φ K (x, a i ). Under our proposed behavior policyπ, we have To this end, we have This implies there always exists an DMDP instance M ∈ M φ,s (X , A, γ) with feature φ ∈ (R d ) X ×A satisfying φ(x, a) ∞ ≤ 1 for all (x, a) ∈ X × A, then where µ * is the discounted state-action occupancy measure of π * .

E.1 Proof of Lemma B.3
We prove if the population covariance matrix satisfies the restricted eigenvalue condition, the empirical covariance matrix satisfies it as well with high probability. Recall that h , a

For any
It is easy to verify E[v (k) ij ] = 0 and |v (k) ij | ≤ 1 since we assume φ(x, a) ∞ ≤ 1. Note that from the data collection process Assumption 2.3, samples between different episodes are independent. This implies v (1) ij , . . . , v (K) ij are independent. By standard Hoeffding's inequality (Proposition 5.10 in Vershynin [2010]), we have for some absolute constant C 0 > 0. Applying the union bound over i, j ∈ [d], we have Since the blocks of Ψ are the same, the following holds holds with probability 1 − δ.
Therefore, when the number of episodes K ≥ 32 2 log(3d 2 /δ)s 2 / C min (Ψ, s) 2 , the following holds with probability at least 1 − δ, Next lemma shows that if the restricted eigenvalue condition holds for one positive semi-definite block diagonal matrix Σ 0 , then it holds with high probability for another positive semi-definite block diagonal matrix Σ 1 as long as Σ 0 and Σ 1 are close enough in terms of entry-wise max norm.

E.2 Proof of Lemma B.1
We prove the 1 -norm bound of estimatingw t using a fresh fold of batch data. We overload the notation Σ to denote Similar to the proof of Lemma B.3 in Appendix E.1, we can have with probability at least 1 − δ, where C 1 is an absolute constant. When R ≥ C 1 32 2 log(3d 2 /δ)s 2 /C min (Σ, s), we have Applying Lemma E.1, we have C min ( Σ, s) > C min (Σ, s)/2 with probability at least 1 − δ. Note that {ε i φ j (x i , a i )} RL i=1 is a martingale difference sequence and |ε i φ j (x i , a i )| ≤ 1/(1 − γ). Similar to the proof of Eq. (B.17) by Azuma-Hoeffding inequality, Denote event E as Then P(E) ≥ 1 − δ. Under event E, applying (B.31) in Bickel et al. [2009], we have w t −w t 1 ≤ 16 √ 2sλ 1 C min (Σ, s) , holds with probability at least 1 − 2δ. This ends the proof.

G Preliminary experiments
The left panel in Figure G shows that our Lasso-FQE clearly has smaller estimation error compared with FQE, proving the sparse feature selection is effective in a practical RL example. The right panel in Figure G demonstrates how the distribution mismatch (χ 2 -divergence term) affects OPE error (with sample size fixed).
The results confirm our theorems that the (restricted) chi-square divergence sharply determines the (sparse) OPE error.