Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient

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; Levine et al., 2020). 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.

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.

2 Related work

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; Munos and Szepesvári, 2008; 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 and Brunskill, 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 (Munos and Szepesvári, 2008) 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.

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 $\mathcal{O}((s\log(d)/\psi n)^{1/2})$ under $\psi$-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.

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

A finite, infinite-horizon discounted Markov decision process (DMDP) can be described by the tuple $M=(\mathcal{X},\mathcal{A},P,r,\gamma)$. Here, $\mathcal{X}$ is a finite set of states, $\mathcal{A}$ is a finite set of actions, $P:\mathcal{X}\times\mathcal{A}\to\Delta_{\mathcal{X}}$ is the transition probability function, $r:\mathcal{X}\times\mathcal{A}\to$ is the reward function and $\gamma\in(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 consider the following learning and optimization problems. The learner knows the state space $\mathcal{X}$ and action space $\mathcal{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)\in\mathcal{X}\times\mathcal{A}$. The only unknown is the transition probability function $P$. The learner is given a random dataset $\mathcal{D}=\{(x_{n},a_{n},x_{n}^{\prime})\}_{n=1}^{N}$ generated by using a (possibly nonstationary and unknown) behavior policy $\bar{\pi}$ in the DMDP $M$ starting from some initial distribution which may be different from $\xi_{0}$. We study two fundamental batch RL tasks:

Off-policy policy evaluation: given $\mathcal{D}$ and black box access to a target policy $\pi$, $\xi_{0}$ and $r$, estimate the value, $v^{\pi}_{\xi_{0}}$, of $\pi$;

Batch policy optimization: given $\mathcal{D}$ and black box access to $r$, find an optimal policy.

The function $v^{\pi}$ is the unique solution to the Bellman equation $v^{\pi}={\mathcal{T}}_{\pi}v^{\pi}$.

2 Sparse linear Markov decision process

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\ll d$ features are relevant. This motivates our assumption of sparse linear DMDPs.

We denote by $\mathcal{M}_{\phi,s}(\mathcal{X},\mathcal{A},\gamma)$ the set of all $(s,\phi)$-sparse DMDP instances. Our second assumption concerns the dataset:

The dataset $\mathcal{D}$ consists of $N=KL$ samples from $K$ independent episodes $\tau_{1},\ldots,\tau_{K}$. Each episode $\tau_{k}$ has $L$ consecutive transitions generated by some unknown behavior policy $\bar{\pi}_{k}$ giving rise to a sample path $\tau_{k}=(x_{0}^{(k)},a_{0}^{(k)},x_{0}^{(k)^{\prime}},\ldots,x_{L-1}^{(k)},a_{L-1}^{(k)},x_{L-1}^{(k)^{\prime}})$.

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 $\pi$ from logged experiences $\mathcal{D}$ generated using unknown behavior policies. We propose two sparsity-aware algorithms to approximate state-action functions using sparse parameters.

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.

2 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 $\mathcal{K}$ before evaluating the policy based on the following proposition.

Under Assumption 2.2, there exists a $d\times d$ matrix $K^{\pi}$ such that $\forall~{}(x,a)\in\mathcal{X}\times\mathcal{A}$

Thus we propose to estimate the set of relevant features $\mathcal{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 $\widehat{\mathcal{K}}$. In Algorithm 2, for the ease of comparability with the previous method, we consider vanilla fitted Q-evaluation.

One may wonder whether it is necessary to refit the iterative regression and why not simply use the estimated $\widehat{K}^{\pi}$ 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).

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 $\Sigma$ 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 high-dimensional statistics (Bickel et al., 2009; Bühlmann and Van De Geer, 2011).

The restricted eigenvalue $C_{\min}(\Sigma,s)$ characterizes the quality of the distribution that generates the batch data set $\mathcal{D}$. We need $C_{\min}(\Sigma,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). To ensure the success of policy evaluation/optimization with linear function approximation, similar assumptions regarding $\Sigma$ in RL literature also appear in Abbasi-Yadkori et al. (2019a) (Assumption A.4), Duan and Wang (2020) (Theorem 2), Lazic et al. (2020) (Assumption A.3), Abbasi-Yadkori et al. (2019b) (Assumption A.3) and Agarwal et al. (2020b) (Assumption 6.2).

We first provide a statistical error bound for the Lasso fitted Q-evaluation (Algorithm 1).

Suppose Assumptions 2.2, 2.3 hold and $C_{\min}(\Sigma,s)>0$. Let Algorithm 1 take $N$ samples satisfying $N\gtrsim s^{2}\log(d/\delta)L(1-\gamma)^{-1}/C_{\min}(\Sigma,s).$ Set the number of iterations $T=\Theta(\log(N/(1-\gamma))/(1-\gamma))$ and $\lambda_{1}=(1-\gamma)^{-1}\sqrt{T\log(2d/\delta)/N}$. Then, with probability at least $1-2\delta$,

Theorem 4.3 shows that the OPE error for sparse linear DMDPs depends linearly on $s/C_{\min}(\Sigma,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}(\Sigma,d)<C_{\min}(\Sigma,s)$. Comparing the two results (setting $\delta=1/N$), we expect the new error bound to be significantly tighter , i.e., $C_{\min}(\Sigma,d)\frac{s^{2}\log(dN)}{1-\gamma}\ll C^{2}_{\min}(\Sigma,s)d$, when there is a high level of sparsity ($s\ll d$).

2 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.

For some given $\delta>0$, the minimum signal strength satisfies

where $K_{j\cdot}^{\pi}$ is the $j$th row of $K^{\pi}$ 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.

Suppose Assumptions 2.2, 2.3, 4.4 hold and $C_{\min}(\Sigma,s)>0$. Set the regularization parameter $\lambda_{2}=4\sqrt{2\log(2d^{2}/\delta)/(Nd)}$ for some $\delta>0$ and let the sample size satisfy $N\gtrsim Ls^{2}\log(d/\delta)/C_{\min}^{2}(\Sigma,s)$. Then with probability at least $1-\delta$, the size of learned relevant feature set $\widehat{\mathcal{K}}$ satisfies $|\widehat{\mathcal{K}}|\lesssim s$ and $\widehat{\mathcal{K}}\supseteq\mathcal{K}$ where $\mathcal{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:

Inspired by Theorem 5 of Duan and Wang (2020), we will measure the distribution mismatch using restricted chi-square divergences between $\bar{\mu}$ and $\mu^{\pi}$.

Let $\mathcal{G}$ be a set of real-valued functions over $\mathcal{X}$ and let $p_{1}$ and $p_{2}$ be probability distributions over $\mathcal{X}$. We define the $\mathcal{G}$-restricted chi-square divergence (or $\chi^{2}_{\mathcal{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.

Suppose Assumptions 2.2, 2.3, 4.4 hold and $C_{\min}(\Sigma,s)>0$. Let $\delta\in(0,1)$ and assume that Algorithm 2 is fed with $N$ samples satisfying $N\gtrsim L\log(d^{2}/\delta)s^{2}/C_{\min}^{2}(\Sigma,s)+\gamma^{2}L\log(s/\delta)s/(1-\gamma)^{2}.$ Set $\lambda_{2}=4\sqrt{2\log(2d^{2}/\delta)/Nd},\lambda_{3}=\lambda_{\min}(\Sigma)\log(12|\widehat{\mathcal{K}}|/\delta)L|\widehat{\mathcal{K}}|$. Letting the number of iterations $T\to\infty$, the following holds with probability at least $1-3\delta$,

where $\bar{\mu}$ is the data generating distribution, $\mathcal{G}(\widehat{\mathcal{K}})$ is the reduced feature space.

The OPE error bound of Theorem 4.8 depends on the statistics $\chi^{2}_{\mathcal{G}(\widehat{\mathcal{K}})}(\mu^{\pi},\bar{\mu})$ 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 $\widehat{\mathcal{K}}$ is a small subset of $[d]$, we have $\chi^{2}_{\mathcal{G}(\widehat{\mathcal{K}})}\ll\chi^{2}_{\mathcal{G}([d])}$. Therefore our instance-dependent error bound is expected to be significantly smaller than its counterpart that does not exploit sparsity.

3 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 $\mathcal{M}_{\phi,s}(\mathcal{X},\mathcal{A},\gamma)$ (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.

Suppose Assumption 2.3 holds. If $N\gtrsim sL(1-\gamma)^{-1}$, then

It is worth to mention that in Theorem 4.10, the distribution mismatch term $1+\chi^{2}_{\mathcal{G}(\mathcal{K})}(\mu^{\pi},\bar{\mu})$ may also contain a $1-\gamma$ term in the worse case. Thus the lower bound of sparse off-policy policy evaluation also has a $\sqrt{1/(1-\gamma)^{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.

Suppose Assumptions 2.2, 2.3 hold and $C_{\min}(\Sigma,s)>0$. Let $N\gtrsim s^{2}L(1-\gamma)^{-1}/C_{\min}(\Sigma,s).$ Let Algorithm 3 take $T=\Theta(\log(N/(1-\gamma))/(1-\gamma))$ and $\lambda_{1}=(1-\gamma)^{-1}\sqrt{T\log(2d/\delta)/N}$. Then, with probability at least $1-\delta$,

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 information-theoretic minimax lower bound that nearly match the aforementioned upper bound.

Theorems 5.1, 5.2 show that the statistical error of batch policy learning is fundamentally determined by the ratio $s/C_{\min}(\Sigma,s)$. Note that there remains a gap $\sqrt{s/C_{\min}(\Sigma,s)}$ between Theorems 5.1 and 5.2, due to the nature of Lasso regression.

Earlier results such as those of Munos and Szepesvári (2008); 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 $\mathcal{X}$ is large. In contrast, our results only require that the data’s covariance $\Sigma$ 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 $|\widehat{v}-v^{*}|/|v^{*}|$. We constructed multiple behavior policies with varying levels of $\epsilon$-greedy noise, and plot their OPE error against their (restricted) $\chi^{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 ($\chi^{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.

References

Appendix A Proofs concerning linear MDPs

Now, if $w$ is as above, $g_{w}=Pv_{\pi}=P(r^{\pi}+\gamma(Pv_{\pi})^{\pi})=P(r^{\pi}+\gamma g_{w}^{\pi})=Pr^{\pi}+\gamma Pg_{w}^{\pi}$.

Finally, assuming that $w$ satisfies the last identity, defining $Q=r+\gamma g_{w}$, we have $Q=r+\gamma(Pr^{\pi}+\gamma Pg_{w}^{\pi})=r+\gamma(P(r+\gamma g_{w})^{\pi})=r+\gamma PQ^{\pi}$. As is well known, the unique fixed point of this equation is $Q_{\pi}$. Hence, $Q=Q_{\pi}$. ∎

Under the sparsity assumption, Assumption 2.2, there exists $\mathcal{K}\subset[d]$ such that $w_{ij}=0$ when $j\not\in\mathcal{K}$. This shows that all but $|\mathcal{K}|$ rows of $K^{\pi}$ are identically zero, finishing the proof. ∎

Appendix B Proofs of off-policy policy evaluation

Recall that we split the whole dataset $\mathcal{D}$ into $T$ folds and each fold consists of $R$ episodes or $RL$ sample transitions. At $t$th phase, only the fresh fold of dataset $\mathcal{D}_{t}=\{(x_{i}^{(t)},a_{i}^{(t)},x_{i}^{(t)^{\prime}})\}_{i=1}^{RL}$ is used.

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 $t$th phase:

Note that $\widehat{w}_{t}(\cdot)$ only depends data collected at the $t$th phase. Define the parameterized value function as

Note this $\widehat{{\mathcal{T}}}_{\pi}^{(t)}$ is a randomized operator that only depends data in the $t$th fold. It is easy to see that if $(\widehat{w}_{t})_{t=1}^{T}$ is the sequence of weights computed in Algorithm 1 then $\widehat{w}_{t}=\widehat{w}_{t}(\Pi_{[0,1/(1-\gamma)]}V_{\widehat{w}_{t-1}}^{\pi})$ and also

We first verify for each phase $t\in[T]$, ${\mathcal{T}}_{\pi}\Pi_{[0,1/(1-\gamma)]}V^{\pi}_{\widehat{w}_{t}}$ has a linear representation. From Assumption 2.2, it holds that

and $\bar{w}_{t,k}=0$ if $k\notin\mathcal{K}$. Then we have

It shows that ${\mathcal{T}}_{\pi}\Pi_{[0,1/(1-\gamma)]}V^{\pi}_{\widehat{w}_{t}}$ has a linear representation if the reward could also be linearly represented. For notation simplicity, we drop the supscript of $x_{i}^{(t)}$ and $a_{i}^{(t)}$ for the following derivations when there is no ambiguity.

Step 3: Sparse linear regression. We interpret $\bar{w}_{t}$ as the ground truth of the lasso estimator in Algorithm 1 at phase $t$, in terms of the following sparse linear regression:

where $\varepsilon_{i}=\Pi_{[0,1/(1-\gamma)]}V^{\pi}_{\widehat{w}_{t-1}}(x_{i}^{\prime})-\phi(x_{i},a_{i})^{\top}\bar{w}_{t}$. Define a filtration $\{\mathcal{F}_{i}\}_{i=1,\ldots,RL}$ with $\mathcal{F}_{i}$ generated by $\{(x_{1},a_{1}),\ldots,(x_{i},a_{i})\}$. By the definition of $V_{\widehat{w}_{t-1}}$ and $\bar{w}_{t}$ in Eq. (B.5), we have

Consider the sparse linear regression described in Eq. (B.7). Suppose the restricted minimum eigenvalue of $\Sigma$ satisfy $C_{\min}(\Sigma,s)>0$ and the number of episodes used in phase $t$ satisfies

for some absolute constant $C_{1}>0.$ With the choice of $\lambda_{1}=(1-\gamma)^{-1}\sqrt{\log(2d/\delta)/(RL)}$, the following holds with probability at least $1-\delta$,

Note that the samples we use between phases are mutually independent. Thus, Eq. (B.8) uniformly holds for all $t\in[T]$ with probability at least $1-T\delta$.

Step 4: Error decomposition. Recall that $\widehat{v}_{\widehat{w}_{T}}^{\pi}=\frac{1}{m}\sum_{u=1}^{m}\Pi_{[0,1/(1-\gamma)]}(Q_{\widehat{w}_{T}}(\widetilde{x}_{u},\widetilde{a}_{u}))$ and we denote $\bar{v}^{\pi}_{\widehat{w}_{T}}=\sum_{x}V^{\pi}_{\widehat{w}_{T}}(x)\xi_{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 $\widetilde{x}_{u},\widetilde{a}_{u}$ is i.i.d sampled from $\xi_{0}$ and $\pi$, standard Hoeffding’s inequality shows that

To bound approximation error, we expand it by Eq. (B.4):

Combining Eqs. (B.9), (B.11) and (B.12) together, we have

Iteratively implementing the above decomposition, we have

Since we assume $\|\phi(x,a)\|_{\infty}\leq 1$, then $\|\nu_{t}^{\pi}\|_{\infty}\leq 1$ as well. Using the fact that $\sum_{t=0}^{T-1}\gamma^{t}\leq 1/(1-\gamma)$, we have

for a sufficient large constant $C_{1}>0$. Applying Lemma B.1 over $t=0,\ldots,T-1$, it implies

holds with probability at least $1-T\delta$. By elementary change of base formula and Taylor expansion, we have

By properly choosing $T=\Theta(\log(N/(1-\gamma))/(1-\gamma))$, we have with probability at least $1-\delta$,

where we use $N=TRL$. Combining with Monte Carlo approximation error Eq. (B.10) This ends the proof. $\blacksquare$

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 $\widehat{K}^{\pi}$. Recall that from the identity Eq. (3.1), we solve the following multivariate regression problem:

Note that $X$ is a block diagonal matrix.

Therefore, we can rewrite Eq. (B.13) into an ordinary linear regression form with group sparse structure on the regression coefficients $\bm{\beta}^{*}$:

Note that ${\mathcal{S}}(\bm{\beta}^{*})=\mathcal{K}$ where $\mathcal{K}$ is defined in Assumption 2.2 since $K^{\pi}$ is row-sparse. The corresponding group lasso estimator defined in Eq. (3.2) can be rewritten into:

and ${\mathcal{S}}(\widehat{\bm{\beta}})=\widehat{\mathcal{K}}$. The regularization parameter is chosen as

Now we study the feature screening property of $\widehat{\bm{\beta}}$ in four steps.

Step 1. By the optimality of $\widehat{\bm{\beta}}$, we have

where the last inequality is from H$\ddot{\text{o}}$lder’s inequality.

Step 2. Next, we will bound the noise term: $\|(X^{\top}W)^{j}\|_{2}$. From the definitions of $X$ and $W$, we write it explicitly as

It is easy to verify that $\{\phi_{j}(x_{n},a_{n})\varepsilon_{ni}\}_{n=1}^{N}$ is also a martingale difference sequence for any $i,j\in[d]$ and $|\phi_{j}(x_{n},a_{n})\varepsilon_{ni}|\leq 1$ since we assume $\|\phi(x,a)\|_{\infty}\leq 1$ for any state-action pair. According to Azuma-Hoeffding inequality (Lemma F.2), for all $\widetilde{\delta}>0$,

Using the union bound twice, the following holds,

Letting $\delta=2d^{2}\exp(-\widetilde{\delta}^{2}/2N)$, we have with probability at least $1-\delta$,

Step 3. According to Karush–Kuhn–Tucker (KKT) condition, the solution $\widehat{\bm{\beta}}$ of the optimization problem Eq. (B.14) satisfies

Under event $\mathcal{A}$ and using KKT condition, we have if $\widehat{\bm{\beta}}^{j}\neq 0$, then

We define a notation of restricted maximum eigenvalue with respect to ${\mathcal{S}}(\bm{\beta}^{*})$ and $X$:

Denote $\widehat{m}=|{\mathcal{S}}(\widehat{\bm{\beta}})\setminus{\mathcal{S}}(\bm{\beta}^{*})|$. Then we have

Combining Eqs. (B.18) and (B.20) together, we have

holds with probability at least $1-\delta$.

Step 4. It remains to control the in-sample prediction error $\|X(\widehat{\bm{\beta}}-\bm{\beta}^{*})\|_{2}^{2}$. Under event $\mathcal{A}$, using Eq. (B.16) implies

Adding \sum_{j=1}^{d}\big{\|}\widehat{\bm{\beta}}^{j}-\bm{\beta}^{*j}\big{\|}_{2}\lambda_{2}/2 to both sides and using the fact that $\|\bm{\beta}^{*j}-\bm{\beta}^{*j}\|_{2}+\|\widehat{\bm{\beta}}^{j}\|_{2}-\|\widehat{\bm{\beta}}^{j}\|_{2}=0$ for $j\neq{\mathcal{S}}(\bm{\beta}^{*})$, 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

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 $\widetilde{C}_{\min}(\widehat{\Phi},s)$. The proof is deferred to Appendix E.1.

On the other hand, from Eq. (B.22), we know that

This implies that $\|(\widehat{\bm{\beta}}-\bm{\beta}^{*})_{{\mathcal{S}}(\bm{\beta}^{*})^{c}}\|_{2,1}\leq 3\|(\widehat{\bm{\beta}}-\bm{\beta}^{*})_{{\mathcal{S}}(\bm{\beta}^{*})}\|_{2,1}$. Applying Lemma B.3, the following holds with probability at least $1-\delta$,

Plugging the above bound into Eq. (B.22),

Combining with Eq. (B.21) and the choice of $\lambda_{2}$ in Eq. (B.15), we reach

Consider a sequence of vectors $\bm{\beta}_{1},\ldots,\bm{\beta}_{d}$ satisfying $\|(\bm{\beta}_{j})_{{\mathcal{S}}^{c}}\|_{1}\leq 3\|(\bm{\beta}_{j})_{{\mathcal{S}}}\|_{1}$. Then for $\bm{\beta}=(\bm{\beta}_{1}^{\top},\ldots,\bm{\beta}_{d}^{\top})^{\top}$, we have

Therefore, we conclude $\widetilde{C}_{\min}(\Psi,s)\geq C_{\min}(\Sigma,s)>0$ such that

with probability at least $1-\delta$, as long as $N\geq 32^{2}L\log(3d^{2}/\delta)s^{2}/C_{\min}^{2}(\Sigma,s)$.

Using the definition of $C_{\max}(\widehat{\Sigma},s)$, it holds that

Summing the above inequality from 1 to $d$,

This implies $\widetilde{C}_{\max}(\widehat{m})\leq C_{\max}(\widehat{\Sigma},\widehat{m})$. As shown in the Lemma 1 in Belloni et al. , we have $C_{\max}(\widehat{\Sigma},m)\leq 4C_{\max}(\Sigma,m)$ for any $m+s\leq\log(n)$ as long as $n\gtrsim s$.

Step 5. Recall that $\widehat{m}=|{\mathcal{S}}(\widehat{\bm{\beta}})\setminus{\mathcal{S}}(\bm{\beta}^{*})|$ and denote

Suppose there is a $m_{0}\in\mathcal{M}$ such that $\widehat{m}>m_{0}$. From Eq. (B.25), we know that

According to Lemma 3 in Belloni et al. for the sublinearity of sparse maximum eigenvalues, we have

where the last inequality we use $\lceil\kappa\rceil\leq 2\kappa$. Putting the above two results together, we have

This leads a contradiction with the definition of $\mathcal{M}$. Therefore, $\widehat{m}\leq m_{0}$ for all $m_{0}\in\mathcal{M}$. This implies

The term $\min_{m_{0}\in\mathcal{M}}C_{\max}(\Sigma,m_{0})/C_{\min}(\Sigma,s)$ essentially characterizes the condition number of $\Sigma$ 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 $\mathcal{A}$ we have

Combining the above two inequality together and plugging in the choice of $\lambda_{2}$, we can bound

with probability at least $1-\delta$. Under Assumption 4.4, the following holds that with probability at least $1-\delta$,

If there is a $j\in{\mathcal{S}}(\bm{\beta}^{*})$ but $j\notin{\mathcal{S}}(\widehat{\bm{\beta}})$, we have

which leads a contradiction. Now we conclude that ${\mathcal{S}}(\widehat{\bm{\beta}})\supseteq\mathcal{K}$. This ends the proof. $\blacksquare$

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.

Assume the DMDPs satisfy Assumption 2.2 and batch dataset satisfy Assumption 2.2. Suppose $\phi(x,a)^{\top}\Sigma^{-1}\phi(x,a)\lesssim d$ for any pair of $(x,a)$. Let $\delta\in(0,1)$ and Algorithm 2 without feature selection stage takes $N$ samples satisfying

Set regularization parameter $\lambda_{3}=\lambda_{\min}(\Sigma)\log(12d/\delta)C_{1}d/(1-\gamma)$. Letting the number of iteration $T\to\infty$, the following holds with probability at least $1-\delta$,

If the true relevant feature set $\mathcal{K}$ is known in an oracle case, we could directly run the algorithm on $\mathcal{K}$ such that all the dependency on $d$ can be reduced to $s$ and the instance-dependent term turns to be defined in the $\mathcal{K}$ that is much sharper than the original one. Fortunately, Lemma 4.5 implies $\widehat{\mathcal{K}}\supseteq\mathcal{K}$ and $|\widehat{\mathcal{K}}|\lesssim s$. Suppose

Rewriting Theorem B.4 with respect to $\widehat{\mathcal{K}}$, we have

where $\widetilde{\nu}_{t}^{\pi}=[\nu_{t}^{\pi}]_{\widehat{\mathcal{K}}}$ and $\widetilde{\Sigma}=\Sigma_{\widehat{\mathcal{K}}\times\widehat{\mathcal{K}}}$. The corresponding condition $\phi(x,a)^{\top}\Sigma^{-1}\phi(x,a)\lesssim|\widehat{\mathcal{K}}|$ can be satisfied due to $C_{\min}(\Sigma,s)>0$ and $\|\phi(x,a)\|_{\infty}\leq 1$. From Definitions 4.6, 4.7 and Lemma B.2 in Duan and Wang , we have

Appendix C Proof of Theorem 5.1: lasso fitted Q-iteration

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=TRL$.

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 $t$th phase is defined in Eq. (B.1) as

Note this $\widehat{{\mathcal{T}}}^{(t)}$ is a randomized operator that only depends data collected at $t$th phase. Algorithm 3 is equivalent to the following approximate value iteration:

Step 2. We verify that the true Bellman operator on $\Pi_{[0,1/(1-\gamma)]}V_{\widehat{w}_{t-1}}$ can also be written as a linear form. From Condition 2.2, there exists some functions $\psi(\cdot)=(\psi_{k}(\cdot))_{k\in\mathcal{K}}$ such that for every $x,a,x^{\prime}$, the transition function can be represented as

and $\bar{w}_{t,k}=0$ if $k\notin\mathcal{K}$. By the definition of true Bellman optimality operator in Eq. (C.3) and Eq. (C.4),

Step 3. We start to bound $\|V_{\widehat{w}_{t}}-v^{*}\|_{\infty}$ for each phase $t$. By the approximate value iteration form Eq. (C.2) and the definition of optimal value function,

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\in\mathcal{X}$,

Applying Lemma B.1, with the choice of $\lambda_{1}=(1-\gamma)^{-1}\sqrt{\log(2d/\delta)/RL}$, the following error bound holds with probability at least $1-\delta$,

where $R$ satisfies $R\geq C_{1}\log(3d^{2}/\delta)s^{2}/C_{\min}(\Sigma,s).$

Note that the samples we use between phases are mutually independent. Thus Eq. (C.9) uniformly holds for all $t\in[T]$ with probability at least $1-T\delta$. Plugging it into Eq. (C.8), we have for any phase $t\in[T]$,

holds with probability at least $1-\delta$.

To bound the second term in Eq. (C.7), we use the contraction property of true Bellman operator such that

Plugging Eqs. (C.10) and (C.11) into Eq. (C.7), it holds that

with probability at least $1-\delta$. Recursively using Eq. (C.12), the following holds with probability $1-\delta$,

where the first inequality is due to that $\Pi_{[0,1/(1-\gamma)]}$ can only make error smaller and the last inequality is from $\sum_{t=1}^{T-1}\gamma^{t}\leq 1/(1-\gamma)$. By properly choosing $T=\Theta(\log(N/(1-\gamma))/(1-\gamma))$, it implies

holds with probability at least $1-\delta$. From Proposition 2.14 in Bertsekas ,

Putting the above together, we have with probability at least $1-\delta$,

for some sufficiently large constant $C_{1}$. This ends the proof. $\blacksquare$

Appendix 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).

where $\mu^{*}$ is the discounted state-action occupancy measure of $\pi^{*}$. In addition, we have

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. constructed a hard instance of tabular MDP and, by reducing policy optimization to a testing a Bernoulli distribution, proved a lower bound $\frac{SA}{(1-\gamma)^{3}}$ which is known to be sharp. Yang and Wang extended the construction to linear MDP and show that the sample complexity lower bound is $\frac{d}{(1-\gamma)^{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 , we have Lemma D.1 below.

Let $M_{\alpha}$ and $M_{\beta}$ be two MDP instances with transition kernels $p_{\alpha}(x^{\prime}\,|\,x,a)$ and $p_{\beta}(x^{\prime}\,|\,x,a)$. Suppose Assumption 2.3 holds. Define likelihood functions

then for any policy learning algorithm $\widehat{\pi}$,

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. $\mathcal{X}=\{\overline{x},\underline{x}\}$. At each state, the agent chooses from $\frac{s}{2}+s(d-s)$ actions \mathcal{A}=\big{\{}a_{1},a_{2},\ldots,a_{\frac{s}{2}}\big{\}}\cup\big{\{}\bar{a}_{i,k}\,\big{|}\,i=1,2,\ldots,\frac{s}{2},\,k=\pm 1,\pm 2,\ldots,\pm(d-s)\big{\}}. Here, we only use $\bar{a}_{i,j}$ in collecting the dataset $\mathcal{D}$.

$\Theta$ is orthogonal and satisfies (D.5). ∎

where $\varsigma_{1},\varsigma_{2}\in(0,1)$ will be determined later. By construction, we have $\|\phi_{\mathcal{K}}(x,a)\|_{\infty}\leq 1$ for any $(x,a)\in\mathcal{X}\times\mathcal{A}$. Note that $\phi_{\mathcal{K}}$ abstracts all the dynamic informatrion for state-action pairs, and $\phi_{\mathcal{K}^{c}}$ does not affect the transition model or reward function. Therefore, it is sufficient for us to use $\phi_{\mathcal{K}}$ when identifying the optimal policy or calculate value functions.

We propose $\frac{s}{2}$ MDP models $M_{1},M_{2},\ldots,M_{\frac{s}{2}}$, where $M_{i}$ has transition kernel $p_{i}(x^{\prime}\,|\,x,a)=\phi_{\mathcal{K}}(x,a)^{\top}\psi_{i}(x^{\prime})$ given by

Here, \delta_{1},\delta_{2}\in\big{[}0,2(1-\gamma)\big{)} are parameters reflecting the small differences among actions.

The reward functions are the same for all models and are chosen as

for $i=1,2,\ldots,\frac{s}{2}$, $j=\pm 1,\pm 2,\ldots,\pm(d-s)$.

D.3 Analyzing the concentration of the likelihood ratio

Parallel to Lemma C.3 in Duan and Wang , we provide concentration results of the likelihood ratio in Lemma D.3. The proof can be found in Appendix E.2.1.

If we take $\delta_{1},\delta_{2}\geq 0$ such that

then for any $i,j=1,2,\ldots,s$, $i\neq j$, it holds that

Lemma D.3 suggests that as long as (D.6) is satisfied, the likelihood test in Lemma D.1 works for any pair of indices $(\alpha,\beta)=(i,j)$, $i\neq j$.

D.4 Calculating the gap in values

For model $M_{i}$, the optimal policy is given by

If $\delta_{1}\leq\frac{1-\gamma}{\gamma}$, $\delta_{2}\leq\varsigma_{2}$, then for any policy $\pi$ such that $\pi(\overline{x})\neq a_{i}$, it holds that

then condition (D.3) in Lemma D.1 holds for any $(\alpha,\beta)=(i,j)$, $i\neq j$.

D.5 Choosing parameters

We now integrate Lemmas D.1, D.3 and D.4. Specifically, we choose parameters $\varsigma_{1},\varsigma_{2},\delta_{1},\delta_{2}$ and $\bar{\xi}$ that maximize $\rho^{\prime}$ in (D.8) under the constraint (D.6).

We first consider the optimization problem

Plugging (D.9) into (D.8) and assuming that $p_{\min}\geq\frac{\varsigma_{2}}{2}$, we have

We maximize the right hand side of (D.10) over $\varsigma_{2}$, and obtain

We further let \varsigma_{1}\in\big{[}\frac{1-\gamma}{2\gamma},1-\frac{1-\gamma}{2\gamma}\big{)} and suppose the sample size

In this case, $p_{\min}\geq\frac{\varsigma_{2}}{2}$ and $\delta_{1}\vee\delta_{2}\leq\frac{p_{\min}}{100\sqrt{L}}\leq\varsigma_{2}\leq\frac{1-\gamma}{\gamma}$.

In summary, if the sample size $N$ satisfies (D.11) and we take

then the conditions in Lemmas D.3 and D.4 are satisfied and (D.4) holds for

Remark that under this construction, we still have the flexibility to take $\varsigma_{1}\nearrow 1-\frac{1-\gamma}{2\gamma}$ so that $\Sigma^{\circ}$ is very ill-conditioned. For instance, if we take $\varsigma_{1}=1-\frac{1-\gamma}{\gamma}$, then ${\rm det}(\Sigma^{\circ})$ or $\lambda_{\min}(\Sigma^{\circ})$ at least has the order of $(1-\gamma)^{3}$.

In order that condition (D.11) is as weak as possible, we take $\gamma\geq\frac{2}{3}$, $\varsigma_{1}=\frac{1-\gamma}{2\gamma}$ and $\bar{\xi}(\overline{x})=\bar{\xi}(\underline{x})=\frac{1}{2}$. In this setting, if $N\geq 2000sL(1-\gamma)^{-1}$ then (D.11) holds.

D.6 Relating to mismatch terms

In this part, we relate $\frac{\Sigma_{22}^{\circ}}{{\rm det}(\Sigma^{\circ})}$ in (D.12) to mismatch terms $\chi_{\mathcal{G}(\mathcal{K})}^{2}(\mu^{*},\bar{\mu})$ and $C_{\min}(\Sigma,s)$.

According to Lemma B.2 in Duan and Wang , we have

For model $M_{i}$, $\overline{x}$ is an absorbing state under the optimal policy $\pi_{i}^{*}$. Therefore, $\mu^{*}(\overline{x})=1$ and $\nu_{\mathcal{K}}^{*}=\phi_{\mathcal{K}}(\overline{x},a_{i})$. Under our proposed behavior policy $\bar{\pi}$, we have

where $\mu^{*}$ is the discounted state-action occupancy measure of $\pi^{*}$.

D.6.2 Restricted minimum eigenvalue

In the following, we specify the choice of $\phi_{\mathcal{K}^{c}}(\overline{x},\bar{a}_{i,k})$ and $\phi_{\mathcal{K}^{c}}(\underline{x},\bar{a}_{i,k})$ and show that if

Under condition (D.14), it holds that $\Sigma_{22}^{\circ}\geq\Sigma_{11}^{\circ}$, therefore, $\frac{\Sigma_{22}^{\circ}}{{\rm det}(\Sigma^{\circ})}\geq\frac{{\rm Tr}(\Sigma^{\circ})}{2{\rm det}(\Sigma^{\circ})}$. In addition, for the $2$-by-$2$ matrix $\Sigma^{\circ}$, we have $\lambda_{\min}(\Sigma^{\circ})+\lambda_{\max}(\Sigma^{\circ})={\rm Tr}(\Sigma^{\circ})$ and $\lambda_{\min}(\Sigma^{\circ})\lambda_{\max}(\Sigma^{\circ})={\rm det}(\Sigma^{\circ})$. It follows that

We next relate $\lambda_{\min}(\Sigma^{\circ})$ to $C_{\min}(\Sigma,s)$.

for $i=1,2,\ldots,\frac{s}{2}$, $k=\pm 1,\pm 2,\ldots,\pm(d-s)$. It holds that $\|\phi_{\mathcal{K}^{c}}(\overline{x},\bar{a}_{i,k})\|_{\infty}\leq 1$ and $\|\phi_{\mathcal{K}^{c}}(\underline{x},\bar{a}_{i,k})\|_{\infty}\leq 1$. For notational simplicity, let $\mathcal{K}=[s]$. Under our proposed behavior policy $\bar{\pi}(\bar{a}_{i,k}\,|\,\overline{x})=\bar{\pi}(\bar{a}_{i,k}\,|\,\underline{x})=\frac{1}{s(d-s)}$, we have

By (D.13), $\lambda_{\min}(\Sigma_{\mathcal{K}})=\lambda_{\min}(\Sigma^{\circ})$. We also note that ${\rm Tr}(\Sigma^{\circ})=\bar{\xi}(\overline{x})\|(1-\varsigma_{1},\varsigma_{1})\|_{2}^{2}+\bar{\xi}(\underline{x})\|(\varsigma_{2},1-\varsigma_{2})\|_{2}^{2}\leq 1$, and therefore

It follows that $\lambda_{\min}(\Sigma)=\lambda_{\min}(\Sigma^{\circ})$, which further implies $C_{\min}(\Sigma,s)\geq\lambda_{\min}(\Sigma)=\lambda_{\min}(\Sigma^{\circ})$. On the other hand, the eigenvector of $\Sigma$ corresponding to $\lambda_{\min}(\Sigma^{\circ})$ has support set $\mathcal{K}$ and is $s$-sparse. Hence, $\lambda_{\min}(\Sigma^{\circ})\geq C_{\min}(\Sigma,s)$. In this way, we have proved $C_{\min}(\Sigma,s)=\lambda_{\min}(\Sigma^{\circ})$ for $\Sigma$ defined in (D.16).

In the special case where $\varsigma_{1}=\varsigma_{2}=\frac{1-\gamma}{2\gamma}$ and $\bar{\xi}(\overline{x})=\bar{\xi}(\underline{x})=\frac{1}{2}$, condition (D.14) holds. Plugging (D.15) into (D.12), we finish our proof of Theorem 5.2.

Appendix E Proofs of auxiliary results

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

for some absolute constant $C_{0}>0$. Applying the union bound over $i,j\in[d]$, we have

Since the blocks of $\Psi$ are the same, the following holds holds with probability $1-\delta$.

Therefore, when the number of episodes $K\geq 32^{2}\log(3d^{2}/\delta)s^{2}/\widetilde{C}_{\min}(\Psi,s)^{2}$, the following holds with probability at least $1-\delta$,

Next lemma shows that if the restricted eigenvalue condition holds for one positive semi-definite block diagonal matrix $\Sigma_{0}$, then it holds with high probability for another positive semi-definite block diagonal matrix $\Sigma_{1}$ as long as $\Sigma_{0}$ and $\Sigma_{1}$ are close enough in terms of entry-wise max norm.

Let $\Sigma_{0}$ and $\Sigma_{1}$ be two positive semi-definite block diagonal matrices. Suppose that the restricted eigenvalue of $\Sigma_{0}$ satisfies $\widetilde{C}_{\min}(\Sigma_{0},s)>0$ and $\|\Sigma_{1}-\Sigma_{0}\|_{\infty}\leq\widetilde{C}_{\min}(\Sigma_{0},s)/(32s)$. Then the restricted eigenvalue of $\Sigma_{1}$ satisfies $\widetilde{C}_{\min}(\Sigma_{1},s)>\widetilde{C}_{\min}(\Sigma_{0},s)/2$.

Applying Lemma E.1 with $\widehat{\Psi}$ and $\Psi$, we have the restricted eigenvalue of $\widehat{\Phi}$ satisfies $\widetilde{C}_{\min}(\widehat{\Psi},s)>\widetilde{C}_{\min}(\Psi,s)/2$ with probability at least $1-\delta$, as long as the sample size $N\geq 32^{2}L\log(3d^{2}/\delta)s^{2}/\widetilde{C}_{\min}(\Psi,s)^{2}$. This ends the proof. $\blacksquare$

E.2 Proof of Lemma B.1

Similar to the proof of Lemma B.3 in Appendix E.1, we can have with probability at least $1-\delta$,

where $C_{1}$ is an absolute constant. When $R\geq C_{1}32^{2}\log(3d^{2}/\delta)s^{2}/C_{\min}(\Sigma,s)$, we have

Applying Lemma E.1, we have $C_{\min}(\widehat{\Sigma},s)>C_{\min}(\Sigma,s)/2$ with probability at least $1-\delta$. Note that $\{\varepsilon_{i}\phi_{j}(x_{i},a_{i})\}_{i=1}^{RL}$ is a martingale difference sequence and $|\varepsilon_{i}\phi_{j}(x_{i},a_{i})|\leq 1/(1-\gamma)$. Similar to the proof of Eq. (B.17) by Azuma-Hoeffding inequality,

holds with probability at least $1-2\delta$. This ends the proof. $\blacksquare$

If we take $\delta_{1}\vee\delta_{2}\leq\frac{p_{\min}}{2}$, then $|\Lambda_{l}^{(k)}|\leq\frac{1}{2}$ and

Denote \Xi_{k}:=\frac{1}{L}\sum_{l=0}^{L-1}\big{(}\phi(s_{l}^{(k)},a_{l}^{(k)})^{\top}(\psi_{i}(\overline{x})-\psi_{j}(\overline{x}))\big{)}^{2}. Note that

Plugging (E.4) and (E.5) into (E.1) and applying condition (D.6), we obtain (D.7).

E.2.2 Proof of Lemma D.4

We consider another policy $\pi_{i}^{\prime}$ such that $\pi_{i}^{\prime}(\overline{x})=a_{j}$ for some $a_{j}\neq a_{i}$ and $\pi_{i}^{\prime}(\underline{x})=\pi_{i}^{*}(\underline{x})$. It holds that

Under model $M_{i}$, when $\delta_{2}\leq\varsigma_{2}$, $\pi_{i}^{*}$ and $\pi_{i}^{\prime}$ satisfy

Under the condition $\delta_{1}\leq\frac{1-\gamma}{\gamma}$, we have $\gamma\delta_{1}\leq 1-\gamma\leq 1-\gamma p_{i}^{\pi_{i}^{*}}(\underline{x}\,|\,\underline{x})$, therefore,

Plugging (E.8) and (E.9) into (E.7), we finish our proof. ∎

Appendix F Supporting lemmas

Let $\mathcal{F}_{n}=\sigma(x_{1},\ldots,x_{n})$ be a sequence of $\sigma$-fields known as a filtration. Let $\{(x_{n},\mathcal{F}_{n})\}_{n=1}^{\infty}$ be a martingale difference sequence for which there are constants $\{(a_{k},b_{k})_{k=1}^{n}\}$ such that $x_{k}\in[a_{k},b_{k}]$ almost surely for $k=1,\ldots,n$. Then for all $t\geq 0$,

Appendix 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 ($\chi^{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.