PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient

Botao Hao, Yaqi Duan, Tor Lattimore, Csaba Szepesvári, Mengdi Wang

arXiv:2011.04019v1cs.LGmath.STstat.MLstat.TH

TL;DR

High-dimensional batch RL can require sample sizes scaling with the number of features, motivating sparse approaches. This paper analyzes sparse fitted-Q evaluation and optimization, finding feature-space learning possible and bounds tied to sparsity and data conditioning.

  • Problem

    When candidate feature counts are high, sample requirements for accurate policy evaluation or near-optimal policies can scale at least linearly with d.

    Source: §1 · p. 2

  • Method

    The paper analyzes sparse linear MDPs using Lasso fitted Q-evaluation and fitted Q-iteration, plus a group-Lasso-selected post-model-selection evaluator.

    Source: §1.1 · p. 2

  • Results

    Sparse linear DMDPs permit learning and planning in feature space from batch data; evaluation bounds avoid polynomial dependence on d, while optimization bounds and lower bounds reflect sparsity and covariance conditioning.

    Source: §1.1 · p. 2, §7 · p. 13

  • Takeaways & Limitations

    Well-conditioned data is crucial for sample-efficient sparse batch policy learning.

    Source: §1.1 · p. 2

    The results require a positive restricted minimal eigenvalue, meaning well-conditioned data or behavior-policy coverage over relevant features.

    Source: §4 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

The paper studies batch RL with high-dimensional features, where sample requirements can scale with feature count, and applies sparse approximation to improve sample efficiency. It develops theoretical analyses for sparse policy evaluation and optimization.

1 Introduction

  • With d candidate features, supervised-learning results imply sample requirements at least linear in d, motivating sparse methods when fewer features are relevant.The paper borrows sparse-learning techniques to improve batch RL sample efficiency.Source: §1 · p. 2

1.1 Contributions

  • Sparse Lasso fitted Q-evaluation yields a finite-sample bound with no polynomial dependence on d when the true MDP is sparse.The bound depends on the number of relevant features and the restricted minimal eigenvalue.Source: §1.1 · p. 2
  • Group Lasso feature selection reduces Lasso bias and yields a sharper, instance-dependent evaluation bound under an additional separability assumption.The bound uses a divergence measuring mismatch between the data distribution and target-policy occupancy distribution over the reduced feature space.Source: §1.1 · p. 2
  • Lasso fitted Q-iteration policy-error bounds and minimax lower bounds depend on the ratio of relevant features to the dataset covariance’s restricted minimal eigenvalue.The authors conclude that well-conditioned data is crucial for sample-efficient batch policy learning.Source: §1.1 · p. 2

1.2 Related work

  • Prior Lasso-TD analyses gave in-sample prediction bounds but did not establish target-policy estimation error bounds capturing distribution mismatch or minimax lower bounds [2011].The cited discussion names Ghavamzadeh et al. [2011] and Geist et al. [2012].Source: §1.2 · p. 3

2 Preliminaries

The preliminaries define the batch-learning setup and feature-based representation used to study sparse linear DMDPs. The central setting has unknown transitions and a dataset, with evaluation and optimization as the two tasks.

2.1 Problem definition

  • The learner knows the state and action spaces and can query rewards, while transitions are unknown and data comes from a behavior policy.The two tasks are estimating a target policy’s value and finding an optimal policy from the batch dataset.Source: §2.1 · pp. 4–5

2.2 Sparse linear Markov decision process

  • A feature map φ represents state-action functions as linear combinations φ(x,a)^⊤w, avoiding computation tied to the full state-space size.The feature class Gφ is the set of these linear functions.Source: §2.2 · p. 5
  • In a linear DMDP, the feature class is closed under the operators f ↦ Pfπ, supporting feature-space representations of policy values.The stated proposition gives a linear equation for the corresponding feature weights.Source: §2.2 · p. 6
  • Sparse linear DMDPs model settings where only s ≪ d features are relevant, making learning with more features than samples possible under that assumption.The paper motivates sparsity because agnostic feature choices can make d as large as or larger than the sample size.Source: §2.2 · p. 6

3 Sparsity-Aware Off-Policy Policy Evaluation

The section develops sparsity-aware methods for off-policy policy evaluation from logged data: Lasso fitted Q-evaluation and a post-selection estimator that screens features with group Lasso before refitting.

3 Sparsity-Aware Off-Policy Policy Evaluation

  • The section frames off-policy policy evaluation as estimating a target policy’s value from logged experience generated by unknown behavior policies, using two sparsity-aware algorithms.Both methods approximate state-action functions with sparse parameters.Source: §3 · p. 6

3.1 Lasso fitted Q-evaluation

  • Lasso fitted Q-evaluation applies L1-regularized regression iteratively, splitting the dataset into nonoverlapping folds so each step uses a separate fold.A final Monte Carlo averaging step uses newly drawn samples for numerical integration.Source: §3.1 · pp. 6–7

3.2 Post model-selection fitted Q-evaluation

  • The post-selection method uses group Lasso to identify relevant features, then applies fitted Q-evaluation on the selected feature set.The method targets accumulated Lasso bias; refitting is described as less biased when feature selection succeeds.Source: §3.2 · p. 7

4 Performance Bounds For Sparse Off-Policy Evaluation

The performance analysis ties sparse off-policy evaluation to well-conditioned batch data, derives bounds for Lasso and post-selection estimators, and provides a minimax lower bound for comparison.

4 Performance Bounds For Sparse Off-Policy Evaluation

  • The restricted eigenvalue Cmin(Σ, s) must be positive; it characterizes batch-data quality and indicates well-conditioning or good behavior-policy coverage over relevant features.This is identified as a key condition for successful sparse feature selection.Source: §4 · p. 8

4.1 Finite-sample error bounds of Algorithm 1

  • The Lasso fitted Q-evaluation error bound depends linearly on s/Cmin(Σ, s), and the authors expect it to be tighter than the nonsparse bound when s ≪ d.The comparison notes Cmin(Σ, d) < Cmin(Σ, s).Source: §4.1 · p. 9

4.2 Finite-sample error bounds of Algorithm 2

  • Under a minimal signal-strength assumption, group-Lasso screening identifies a feature set of size at most proportional to s that contains all relevant features with high probability.The post-selection estimator’s instance-dependent error bound uses a restricted chi-square divergence between the data distribution and target-policy occupancy distribution.Source: §4.2 · pp. 9–10

4.3 Minimax lower bound for OPE

  • The instance-dependent bound is described as nearly minimax-optimal, with its divergence restricted to the reduced feature space and reflecting data–target-policy distribution mismatch.The lower-bound analysis is for sparse linear DMDPs.Source: §4.3 · pp. 10–11, §4.2 · p. 10

5 Sparsity-Aware Batch Policy Optimization

The paper analyzes Lasso fitted Q-iteration for sparse batch policy optimization and relates its error to the number of relevant features and the restricted minimal eigenvalue of the data covariance. Its upper and lower bounds identify data conditioning as central to the statistical limits of sparse policy learning.

5 Sparsity-Aware Batch Policy Optimization

  • Lasso fitted Q-iteration estimates regression targets across dataset folds and outputs a policy that maximizes the fitted action-value function.Its regression target includes a max operation.Source: §5 · p. 11
  • With well-conditioned data, the sample size needed for a good policy depends mainly on the number of relevant features s rather than ambient dimension d.The Lasso fitted Q-iteration error depends on the ratio between relevant features and the covariance’s restricted minimal eigenvalue.Source: §5 · p. 11
  • The minimax lower bound for sparse batch policy learning nearly matches the upper bound and also depends on the ratio of relevant features to restricted minimal eigenvalue.The authors describe this as the first lower-bound result demonstrating the critical role of the minimal eigenvalue in batch policy optimization.Source: §5 · p. 12
  • A gap of s/Cmin(Σ, s) remains between the upper and lower bounds because of the nature of Lasso regression.The results require covariance conditioning on restricted supports, rather than entrywise bounds on occupancy measures across policies.Source: §5 · p. 12

6 Experiment

The Mountain Car experiment compares Lasso-FQE with standard FQE under varying behavior-policy noise. Lasso-FQE has smaller estimation error, while the observed error also varies with distribution mismatch.

6 Experiment

  • Lasso-FQE has smaller estimation error than standard FQE in the Mountain Car example.The comparison uses 800 radial basis functions, a random behavior policy, a near-optimal target policy, and averages results over 20 runs.Source: §6 · p. 12
  • The experiment measures relative value-estimation error, |bv −v∗|/|v∗|, against the restricted χ2-divergence from the target policy.Behavior policies vary in their ε-greedy noise level.Source: §6 · p. 12
  • With sample size fixed, the results show that distribution mismatch affects OPE error, consistent with the paper’s theorems.The passage says the restricted chi-square divergence sharply determines sparse OPE error.Source: §6 · p. 12

7 Conclusion

The conclusion presents a statistical framework for high-dimensional batch RL with sparse linear function approximation. It says the results allow learning and planning in feature space despite sparsity and the use of batch data.

7 Conclusion

  • The paper focuses on high-dimensional batch RL using sparse linear function approximation.Source: §7 · p. 12
  • The authors say earlier RL work recognized sparse-learning tools but lacked a clean theoretical framework and formal results.Source: §7 · pp. 12–13
  • The results show that learning and planning in linear DMDPs can be done in feature space despite sparsity and batch-only data.Source: §7 · p. 13

A Proofs concerning linear MDPs

The appendix proves structural properties of linear MDPs and develops the Lasso fitted Q-evaluation error argument. The proof links Bellman relations to sparse regression, then bounds evaluation error through estimation, Monte Carlo, and approximation components.

A Proofs concerning linear MDPs

  • For a fixed policy, the proof represents its value and Q-functions through linear relations, with Qπ as the unique fixed point of the resulting equation.Under the sparsity assumption, all but |K| rows of Kπ are identically zero.Source: A Proofs concerning linear MDPs · p. 17

B.1 Proof of Theorem 4.3: lasso fitted Q-evaluation

  • The fitted Q-evaluation proof treats each phase’s Lasso fit as a sparse linear regression with martingale-difference noise bounded by truncation.The bound on the noise is |εi| ≤ 1/(1 −γ).Source: §B.1 · p. 19
  • The proof uses a positive restricted minimum eigenvalue and a phase sample-size condition to control the Lasso estimation error.It applies the resulting bound across phases and chooses T proportional to log(N/(1 −γ))/(1 −γ).Source: §B.1 · pp. 19, 21, 22
  • The evaluation-error argument decomposes error into estimation, Monte Carlo, and approximation components before iterating the bound across phases.The algorithm’s phase-wise estimates depend on data collected at their respective phases.Source: §B.1 · pp. 18–20

B.2 Proof of Lemma 4.5: feature selection

The proof establishes that group-Lasso model selection screens relevant features while controlling selected-set size under restricted-eigenvalue conditions, then uses the selected set for a sharper instance-dependent evaluation bound.

B.2 Proof of Lemma 4.5: feature selection

  • If the population restricted eigenvalue is positive, the empirical multivariate restricted eigenvalue exceeds half its population value with probability at least 1−δ at the stated sample size.The condition is N ≥ 322L log(3d²/δ)s²/eCmin(Ψ,s)².Source: §B.2 · pp. 26–27
  • The selected-set size is bounded by a ratio of restricted maximum to minimum eigenvalues, which characterizes restricted-support conditioning.That ratio is upper bounded by the condition number defined on the full support.Source: §B.2 · pp. 27–28
  • With probability at least 1−δ, the selected feature set contains the true relevant set K.The proof establishes this screening property under Assumption 4.4.Source: §B.2 · p. 28

B.3 Proof of Theorem 4.8: instance-dependent upper bound

  • After screening, the instance-dependent fitted Q-evaluation bound is rewritten on the selected support, whose size is at least |K| and at most order s.The divergence term is then defined on the reduced feature space.Source: §B.3 · p. 29

C.1 Proof of Theorem 5.1

The proof represents Lasso fitted Q-iteration as approximate value iteration and derives a high-probability value-error bound by combining per-phase approximation control with Bellman contraction.

C.1 Proof of Theorem 5.1

  • Algorithm 3 is equivalent to an approximate value iteration using a randomized Bellman optimality operator built from each phase’s data.The proof defines the phase-specific operator and the value function used in that iteration.Source: §C.1 · p. 30
  • The proof controls the approximation error phase by phase and uses contraction of the true Bellman operator to control the propagated error.It then chooses T = Θ(log(N/(1−γ))/(1−γ)) to obtain the final high-probability bound.Source: §C.1 · pp. 31–32
  • The per-phase error bound requires R ≥ C1 log(3d²/δ)s²/Cmin(Σ,s) samples per fold.The proof uses independent data between phases and applies the per-phase bound uniformly across them.Source: §C.1 · p. 31
  • The final value-error bound holds with probability at least 1−δ under the stated sample-size condition.The proof concludes by combining the phase-wise estimates and choosing the iteration count appropriately.Source: §C.1 · p. 32

D Proof of Theorem 5.2: minimax lower bound of policy optimization

The lower-bound proof constructs hard batch-episodic instances and uses likelihood testing to show that policy optimization difficulty depends on the data covariance’s restricted minimum eigenvalue.

D Proof of Theorem 5.2: minimax lower bound of policy optimization

  • Theorem 5.2 establishes a minimax lower bound for batch episodic policy optimization that depends on the population covariance’s minimal eigenvalue.The setting uses dependent batch episodic data, unlike a generative model that supplies independent samples at queried state-action pairs.Source: D Proof of Theorem 5.2: minimax lower… · pp. 32–33

D.1 Reducing to likelihood test

  • The lower bound is proved by reducing the problem to a likelihood test between two MDP instances.The test applies when the likelihood-ratio conditions in Lemma D.1 hold.Source: §D.1 · p. 33

D.2 Constructing MDP instances

  • The hard instances use two states and an active feature set that captures the transition and reward dynamics relevant to identifying the optimal policy.The construction states that inactive features do not affect the transition model or reward function.Source: §D.2 · pp. 33–34

D.3 Analyzing the concentration of the likelihood ratio

  • Under condition (D.6), the likelihood test applies to every pair of distinct constructed models.Lemma D.3 supplies the likelihood-ratio concentration result used for this step.Source: §D.3 · p. 35

D.4 Calculating the gap in values

  • Lemma D.4 bounds the value gap between the optimal policy and policies that do not choose the model’s optimal action.The proof uses this gap to set the separation parameter for the likelihood test.Source: §D.4 · p. 35

D.5 Choosing parameters

  • The proof chooses construction parameters to maximize the separation ρ′ subject to the likelihood-concentration constraint.With the resulting choices, the conditions of Lemmas D.3 and D.4 hold.Source: §D.5 · p. 36

D.6 Relating to mismatch terms

  • For the covariance Σ defined in (D.16), the construction yields equality between its minimum eigenvalue and its s-restricted minimum eigenvalue, so λmin(Σ) = Cmin(Σ,s).Source: §D.6.2 · p. 38

D.6.2 Restricted minimum eigenvalue

  • In the constructed instance, Cmin(Σ,s) equals the minimum eigenvalue of the active-feature covariance block.The proof establishes this equality by showing that the corresponding eigenvector has s-sparse support.Source: §D.6.2 · p. 38

E.1 Proof of Lemma B.3

These appendix proofs establish concentration of empirical restricted eigenvalues and fresh-fold estimation errors, then provide supporting concentration arguments for the lower-bound construction and its value-gap calculation.

E.1 Proof of Lemma B.3

  • The empirical restricted eigenvalue remains above half the population value with probability at least 1−δ when the stated episode count is met.The episode requirement is K ≥ 322 log(3d²/δ)s²/eCmin(Ψ,s)².Source: §E.1 · p. 39

E.2 Proof of Lemma B.1

  • For fresh-fold estimation of w̄, the proof controls the ℓ1 error when R is at least a constant times log(3d²/δ)s²/Cmin(Σ,s).The resulting bound holds with probability at least 1−2δ.Source: §E.2 · p. 40

E.2.1 Proof of Lemma D.3

  • The likelihood-ratio concentration proof invokes Freedman’s inequality for conditional variances and Bernstein’s inequality across independent trajectories.It combines the resulting bounds with condition (D.6).Source: §E.2.1 · pp. 41–42

E.2.2 Proof of Lemma D.4

  • The value-gap proof reduces the comparison to expressions involving the policy transition matrix, then substitutes intermediate identities.The excerpt concludes by completing that proof.Source: §E.2.2 · pp. 42–43

F Supporting lemmas

  • The supporting Azuma–Hoeffding inequality bounds deviations of a martingale difference sequence with increments in specified intervals.Its tail bound depends on the increment interval widths.Source: F Supporting lemmas · p. 43

G Preliminary experiments

Figure G compares Lasso-FQE with FQE and examines how distribution mismatch affects off-policy evaluation error. The experiments report that chi-square divergence sharply determines sparse OPE error.

G Preliminary experiments

  • Lasso-FQE has smaller estimation error than FQE in the practical RL example shown in Figure G.The authors describe this comparison as evidence that sparse feature selection is effective in this example.Source: G Preliminary experiments · p. 43
  • With sample size fixed, Figure G's right panel shows how the chi-square divergence term affects OPE error.Source: G Preliminary experiments · p. 43
  • The authors report that restricted chi-square divergence sharply determines sparse OPE error, confirming their theorems.Source: G Preliminary experiments · p. 43

Related papers

Loading 2011.04019v1…