Sparse Additive Off-Policy Evaluation for Reinforcement Learning with Potentially Limited Number of Trajectories

Tuoyi Zhao; Chengchun Shi; Zhengling Qi; Lan Wang

Source-linked AI summary

Sparse Additive Off-Policy Evaluation for Reinforcement Learning with Potentially Limited Number of Trajectories

Tuoyi Zhao, Chengchun Shi, Zhengling Qi, Lan Wang

arXiv:2608.22595v1Aug 23, 2026stat.MLcs.LGmath.ST

TL;DR

The paper addresses off-policy evaluation in high-dimensional, infinite-horizon reinforcement learning, where flexible value estimation must work with limited trajectories. It combines sparse additive Q-function modeling with group-regularized Bellman estimation and screening, deriving logarithmic dimension dependence and guarantees when either trajectories or horizon are large.

Problem
Existing high-dimensional off-policy evaluation can face ill-posed estimation and failed full-rank coverage conditions when features outnumber observed trajectories or time points.
Method
The paper models the target-policy Q-function with a sparse additive nonlinear class and estimates it using group-regularized Bellman equations with simultaneous feature screening.
Results
Theoretical error bounds depend on ambient dimension through log d and d0, while accurate value estimation is guaranteed when either n or T is sufficiently large.
Takeaways & Limitations
The framework provides an interpretable off-policy evaluation approach for large state spaces and can remain consistent as T grows even when n is fixed.
Takeaways & Limitations
Under approximate rather than exact sparsity, the convergence rate can acquire additional approximation-tail terms and an additional factor when translating coefficient error into value-function error.

Abstract

from arXiv · show

We develop a new framework for flexible, nonlinear, and interpretable off-policy evaluation for infinite-horizon reinforcement learning. To handle large state spaces and support transparent decision-making, we model the Q-function using a nonlinear function class with a sparse additive structure. We derive high-probability finite-sample error bounds for estimating the value function of a target policy and show that the bounds depend only logarithmically on the ambient dimension $d$, thereby alleviating the curse of dimensionality. In contrast to most existing theory for off-policy evaluation, which typically assumes access to many trajectories, our analysis guarantees accurate value estimation when either the number of trajectories or the time horizon is sufficiently large. In addition, we propose a group-sparsity-based feature screening procedure that identifies, with high probability, a reduced feature set containing all relevant covariates. Numerical experiments demonstrate the effectiveness of the proposed approach.

1 INTRODUCTION

The paper addresses high-dimensional infinite-horizon off-policy evaluation with a sparse, nonlinear approach that jointly evaluates policies and selects relevant features. Its theory supports accurate estimation when either trajectories or observed time points are sufficiently numerous, with dimension dependence controlled logarithmically.

The study targets off-policy evaluation in infinite-horizon offline reinforcement learning with very large state dimension d relative to n and T.Here, n is the number of observed trajectories and T is the number of observed time points.
The proposed framework uses sparse additive function approximation to estimate a target policy’s cumulative discounted value while performing policy evaluation and feature selection simultaneously.It extends an infinite-horizon Bellman estimating framework from low-dimensional to high-dimensional state spaces.
The analysis derives finite-sample error bounds whose ambient-dimension dependence enters through log d and the number of relevant features d0, avoiding polynomial dependence on d.This is intended to mitigate the curse of dimensionality in large state spaces.
Accurate value estimation is guaranteed when either the number of trajectories n or the number of decision points T is sufficiently large.The estimator remains consistent in probability as T tends to infinity even when n is fixed.
A group-sparsity-aware screening procedure identifies, with high probability, a reduced feature set containing all relevant features.The paper also reports numerical studies evaluating the proposed approach.

2 PRELIMINARIES

The preliminaries formulate offline policy evaluation from Markov trajectories and motivate modeling the target-policy Q-function sparsely in high-dimensional state spaces. The sparse-Q formulation reduces policy-evaluation dependence to decision-relevant coordinates under stated structural conditions.

Off-policy evaluation: Offline data comprise independent trajectories generated by a Markov decision process under a behavior policy, with states, actions, transitions, and rewards observed over time.The transition kernel governs the next state, and rewards have a boundedness assumption.
Off-policy evaluation: The goal is to estimate a stationary target policy’s expected cumulative discounted reward, or value function, using offline trajectories generated under potentially different behavior dynamics.The Q-function is the state-action value used to represent this policy performance.
Q-function modeling: High-dimensional feature spaces can contain more features than max{n, T}, causing existing coverage conditions based on feature-matrix eigenvalues to fail when matrices are not full rank.The paper introduces sparsity-aware Q-function modeling to address this setting.
Q-function modeling: The sparse-Q assumption posits an active feature set K with |K| ≤ d0 ≪ d, while each action’s Q-function depends only on a subset Sa of K.This sparsity is imposed directly on the target-policy Q-function rather than on the full transition structure.
Q-function modeling: Two alternative sufficient conditions imply that Qπ(x, a) = Qπ(xK, a): either rewards and the full transition kernel depend on xK, or rewards, the target policy, and active-state transitions do.These conditions illustrate settings supporting the sparse-Q assumption; the later analysis imposes that assumption directly.
Q-function modeling: The reduced-state perspective seeks the information needed for policy evaluation, not a sparse representation of the complete transition kernel.The active coordinates need not form a minimal sufficient state.

3 NONLINEAR SPARSE MODELING AND ESTIMATION FOR OFF-POLICY EVALUATION

The method combines nonlinear additive Q-function modeling with spline approximation and group-regularized Bellman estimation. It is designed for settings where spline-expanded parameters outnumber observations and supports simultaneous value estimation and feature relevance assessment.

Sparse additive modeling: The model uses an additive Q-function representation with unknown univariate component functions, capturing nonlinear effects without estimating a fully nonparametric multivariate function.This structure is intended to balance flexibility, interpretability, and statistical efficiency in high-dimensional reinforcement learning.
Sparse additive modeling: Under the sparse-Q assumption, each active component is approximated by B-spline basis functions, with approximation error explicitly included in the theory.The smoothness class assumes ν ≥ 3, with relaxation to ν ≥ 2 in a fixed low-dimensional setting.
Sparse additive modeling: The number of basis functions L may diverge with n or T, and the theoretical choice is L ≍ (nT)^(1/(2m−1)).This allows flexible approximation while retaining group structure in estimation.
Regularized estimation: Because d greatly exceeds max{n, T}, the Bellman estimating equations can be ill-posed when the number of unknown parameters exceeds the number of equations.The proposed estimator addresses this through group-wise regularization.
Regularized estimation: A group-Dantzig-type constrained procedure estimates the model coefficients while explicitly incorporating groups of spline coefficients associated with state variables.The intercept-like parameters remain unpenalized, whereas spline coefficient groups are regularized under Markov-dependent Bellman scores.
Value estimation and interpretation: The fitted Q-function is evaluated through the additive basis expansion, and the group structure supports feature screening and more interpretable policy evaluation.Groups can represent state variables or other scientifically meaningful feature collections.

4 FINITE-SAMPLE ERROR BOUNDS

The paper derives high-probability finite-sample guarantees for sparse additive off-policy evaluation in high-dimensional settings. The bounds support consistency when either trajectories or horizon grow, while additional conditions govern coverage, approximation, and feature screening.

Technical conditions: The restricted eigenvalue condition imposes coverage only over a sparse cone and accounts for target-policy-weighted continuation features.It requires sufficient variation in relevant sparse spline directions after accounting for discounted continuation features; increasing T cannot repair missing long-run coverage.
Consistency: Value estimation is consistent when either the number of trajectories n or the time horizon T is sufficiently large.The theory allows T →∞ with n fixed, while one additional covariance-concentration assumption is unnecessary when n is large.
Finite-sample coefficient bounds: The finite-sample coefficient bounds depend on ambient dimension d only through log(nT ∨d), avoiding polynomial dependence on d.The guarantee holds with probability at least 1 −exp{−c log(nT ∨d)} under the stated assumptions.
Finite-sample coefficient bounds: The estimator remains consistent under fixed polynomial growth of d when the sparsity size satisfies the stated growth conditions.The polynomial-growth regime illustrates dimensional dependence; the theorem permits other growth rates satisfying its assumptions and vanishing bounds.
Approximate sparsity: Approximate group sparsity can preserve exact-sparsity rates only when coefficient-tail decay is quantitatively stronger than RS = o(1).Approximation tails add coefficient-error terms, and translating them into value-function error introduces an additional factor of L.
Feature screening: The proposed group-sparsity-aware screening procedure removes irrelevant feature groups when estimation error is controlled and active components have sufficient marginal signal.Selected features are defined using thresholded group norms of coefficient blocks.

5 NUMERICAL EXAMPLES

The numerical examples compare GD with SAVE and Lasso-FQE in simulated high-dimensional settings and CartPole. GD is reported as the most reliable or stable method across the examined configurations.

GD is compared with SAVE and Lasso-FQE in the numerical studies.
For d = 10, GD remains nearly unbiased, with RMSE generally decreasing as n or T increases.
For d = 100, GD maintains small bias and low variability across the evaluated (n, T) combinations.
SAVE is substantially less stable in the high-dimensional setting, occasionally producing extreme estimates and large RMSEs.
In CartPole, GD delivers the most stable performance across reported configurations, even though the true Q-function is not purely additive.
The sparse-completeness argument establishes that the target-policy Q-function depends only on an active feature set under the stated conditions.

A.3 Proof of Proposition 1

The proposition proof shows that sparse function classes remain closed under the target-policy Bellman operator, yielding a Q-function that depends only on active coordinates. The appendix also records the B-spline basis properties used in the analysis.

GK consists of bounded functions whose state dependence is restricted to the active coordinates xK.
Under the first sufficient condition, the transition kernel and reward depend on the state through xK, so Γπ preserves GK.
Bellman iterates starting from zero remain in GK and converge uniformly to the unique bounded fixed point Qπ.
Consequently, Qπ(x, a) = Qπ(xK, a), and choosing Sa = K establishes the sparse representation when |K| ≪ d.
The B-spline construction uses fixed-order bases with equally spaced knots and a rescaled basis for each state variable.
B-spline basis functions are nonnegative, form a partition of unity, and have local support with at most m nonzero components at any x.

Appendix C. Additional technical details

The appendix develops concentration arguments for dependent trajectory data by combining martingale tools, mixing assumptions, block coupling, and matrix concentration inequalities. These steps produce high-probability events with logarithmic dependence on nT ∨ d.

Martingale-difference decompositions and matrix Freedman inequalities control empirical deviations under trajectory dependence.
The technical lemmas establish feasibility of the oracle and estimated coefficient vectors for the optimization problem on the relevant good events.
The proof uses β-mixing of the Markov chain and Berbee coupling to construct approximately independent blocks.
Odd and even coupled blocks are handled as independent mean-zero sums using Hoeffding’s inequality.
Matrix concentration bounds are combined through finite unions over matrix entries to form high-probability good events.
The total failure probability in both diverging-T and bounded-T cases is bounded by an exponential function of log(nT ∨ d).

D.1 Proof of Theorem 10

The theorem proof bounds estimation error by combining feasibility, sparsity, and quadratic-form control. It separately treats growing and fixed dimensions and derives the stated error rates under the required conditions.

The proof partitions coefficient errors into active and inactive groups and uses sparsity to control the relevant support size.
Feasibility of the estimated and oracle coefficients yields a cone-type inequality for the coefficient error.
Solving the resulting quadratic inequality produces the stated ℓ2- and ℓ1-error bounds.
When d0 is fixed and L ≍ (nT)^(1/(2m−1)), the required condition holds whenever 2m − 1 > 2.
The proof also treats the special case d = O(1) using the corresponding good-event bounds.

D.2 Proof of Theorem 12

The proof decomposes value-function error into estimation and policy-related terms, then controls the resulting bounds under stated assumptions. Choosing L = (nT)^(1/(2m−1)) makes approximation error dominated by estimation error.

The value-function error is decomposed using the triangle inequality into estimation and policy-related components.
The proof combines intermediate inequalities with Theorem 10 on the event G1 ∩ G2 to obtain the stated bound.
The generalized test-error argument assumes that the density μ̃_x is uniformly bounded.
L = (nT)^(1/(2m−1)) makes approximation error d0L^−m dominated by the preceding estimation error.

Proof

This proof bounds generalized test error by combining approximation and estimation terms under a bounded-density assumption. It uses matrix structure and Theorem 10 to establish the resulting high-probability control.

The value-function error is split into estimation and policy-approximation terms using the triangle inequality.
With probability at least 1−exp{−c3 log(nT ∨ d)}, the functional approximation error is bounded under the specified choice of L.
The generalized test-error bound assumes μ̃_x ≤ c̃μ.
The proof uses Jensen’s inequality and block-diagonal matrix structure to control the relevant terms.
L = (nT)^(1/(2m−1)) makes approximation error d0L^−m dominated by the preceding estimation error.

D.3 Proof of Theorem 14

The proof establishes feature-screening recovery by showing that an active feature cannot be excluded under the theorem’s conditions. The contradiction argument applies for sufficiently large nT.

For an active feature xs with s ∈ K, the theorem guarantees an action satisfying the required signal condition.
The argument is uniform over all action-state pairs and applies for sufficiently large nT.
Assuming an active index belongs to K but not K̂ leads to a contradiction as nT → ∞.
The desired result follows on the event G1 ∩ G2, whose probability is given by Theorem 10.

Appendix E. Numerical Result

The numerical appendix reports simulation results for settings with different ambient dimensions and for the CartPole environment. Entries are summarized using bias, standard deviation, and RMSE.

The d = 10 simulation table reports bias (SD) / RMSE for each entry.
The d = 100 simulation table reports bias (SD) / RMSE for each entry.
The CartPole simulation table reports bias (SD) / RMSE for each entry.