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

Motivation

• Off-policy evaluation estimates a target policy's performance from offline data generated by another behavior policy, avoiding the risks and costs of online testing.It is especially relevant where real-world interactions are expensive, risky, or ethically constrained.Source: §1 · pp. 1–2

Related work

• Most existing OPE guarantees assume many trajectories, while Kallus and Uehara (2022) require density-ratio estimation and Shi et al. (2022) provide limited-trajectory guarantees when decision points are sufficiently numerous.Existing approaches also include model-based, importance-sampling, value-function, and doubly robust methods, each balancing bias and variance differently.Source: §1 · p. 2

Problem setting

• The study targets infinite-horizon offline reinforcement learning with a Markov decision process and group-wise sparsity when state dimension d is much larger than both n and T.Here n is the number of observed trajectories and T is the number of observed time points.Source: §1 · pp. 2–3

Contributions

• The proposed algorithm jointly evaluates a target policy and selects features, extending Shi et al. (2022)'s infinite-horizon Bellman estimating framework to high-dimensional state spaces.It uses group regularization to handle spline-expanded coefficient dimensions that can exceed nT, with new analysis for Markov dependence and spline approximation error.Source: §1 · p. 3
• Error bounds depend on ambient dimension d only through log d and the number of relevant features d0, and estimation remains consistent as T grows even when n is fixed.Accurate estimation is guaranteed when either the number of trajectories n or the number of decision points T is sufficiently large; screening identifies a reduced set containing all relevant features with high probability.Source: §1 · p. 3

2.1 Off-policy Evaluation for Reinforcement Learning

• The data comprise independent behavior-policy trajectories from an MDP, and the evaluation target is the expected discounted reward of a stationary policy estimated from offline data.The Q-function is the state-action value associated with that target policy; rewards are assumed bounded.Source: §2.1 · pp. 3–4

2.2 Q-function Modeling under Sparsity Constraint

• The target-policy Q-function is assumed to depend, for each action, only on a subset of a shared active feature set, rather than imposing sparsity on the full transition model.The active set has size at most d0, much smaller than d; this formulation targets long-run policy performance and differs from the transition-structure sparsity of Hao et al. (2021a).Source: §2.2 · pp. 4–5
• Sparsity follows if rewards and transitions depend on a reduced state, or if rewards and the target policy do so alongside a reduced-state transition condition; these are illustrative sufficient conditions, not analysis assumptions.Under either condition, Qπ(x, a) = Qπ(xK, a); the subsequent analysis imposes sparse-Q Assumption 1 directly.Source: §2.2 · p. 5

2.3 Notation

• The notation defines vector, matrix, and bounded-function norms, subset and subvector conventions, and an asymptotic comparison used throughout the analysis.For example, ∥A∥2 denotes the matrix operator norm and a(n) ≲ b(n) means a(n) is bounded above by a constant multiple of b(n).Source: §2.3 · p. 6

3.1 Sparse Additive Modeling of the Q function

• Sparse additivity models Q using nonlinear univariate state effects; spline bases make estimation linear in grouped coefficients while retaining nonlinear dependence.The framework considers d much larger than n and T and focuses on binary actions, while extending to any finite action space.Source: §3.1 · p. 6

3.2 Assumptions for Function Approximation

• Component functions are assumed ν-smooth with ν ≥ 3, relaxable to ν ≥ 2 when d is small and independent of n and T, and approximated by B-splines of order m = ⌊ν⌋ with error O(L^-m).Source: §3.2 · p. 7
• Allowing L to diverge reduces approximation bias while retaining group structure; the theoretical derivations take L ≍ (nT)^(1/(2m−1)).Source: §3.2 · p. 7

3.3 Regularized Estimation in High Dimensions

• Group-Dantzig constraints address ill-posed high-dimensional Bellman equations by regularizing feature-wise spline coefficient groups while leaving intrinsic action parameters unpenalized.The analysis must account for Markov-dependent Bellman scores.Source: §3.3 · pp. 8–9

4.1 Additional Technical Conditions

• The restricted eigenvalue condition requires behavior-policy variation in relevant sparse spline directions after accounting for target-policy continuation features, and longer trajectories cannot fix absent long-run coverage.The condition can fail with rarely selected relevant actions, poorly visited regions, or near-collinearity; it imposes no separate pointwise overlap or target-policy eigenvalue condition.Source: §4.1 · pp. 10–11
• Assumption 4 controls empirical Bellman-matrix concentration and is needed to assess accuracy when T is large, but not when n is large.Under stationarity, it can be reduced to geometric ergodicity; temporal dependence reduces the effective number of approximately independent observations.Source: §4.1 · p. 11

4.2 Finite-sample Error Bound for the Estimated Coefficients

• The coefficient error bounds hold with high probability and depend on ambient dimension only through a logarithmic factor, permitting consistency under polynomial dimension growth when sparsity conditions hold.The polynomial-growth regime illustrates the dimensional dependence; the theorem applies to other growth rates when its assumptions hold and the upper bounds vanish.Source: §4.2 · pp. 11–12
• Approximate sparsity preserves the exact-sparsity convergence rate only with a sufficiently fast quantitative decay of the coefficient tail; RS = o(1) alone is generally insufficient.The approximation tail adds terms to coefficient error, and translating that error to value-function error introduces an additional factor of L.Source: §4.2 · p. 12

4.3 Finite-sample Error Bound of Value Function

• The value-function bound is high-probability; for integrated error, a bounded density and deterministic policy yield a sharper bound, with spline approximation error negligible under the stated L choice.The approximation error can be absorbed into the estimation error for the uniform and integrated bounds.Source: §4.3 · pp. 12–13
• The result establishes long-trajectory consistency in both estimation-error magnitude and guarantee confidence, unlike Hao et al. (2021a), whose stated conditions do not allow confidence to improve by lengthening fixed-count trajectories.In the cited analysis, increasing trajectory length at fixed trajectory count does not let failure probability converge to zero.Source: §4.3 · p. 13

4.4 Feature Screening

• The screening procedure uses group structure to select features by coefficient-group norms exceeding a threshold, with a theoretical guarantee under suitable conditions.Its effectiveness requires active-component marginal signal not to be dominated by estimation error.Source: §4.4 · p. 13

5 NUMERICAL EXAMPLES

• GD is compared with SAVE from Shi et al. (2022) and Lasso-FQE (LFQ) from Hao et al. (2021a).The paper denotes its proposed estimator GD because estimation uses a group Dantzig structure.Source: §5 · p. 13

5.1 Experiment 1

• Experiment 1 evaluates bias at x = 0 for d = 10 and d = 100, across n = 20–50 and T = 20–40, using 100 independent runs.The larger state has d = 100 ≫ max{n, T}.Source: §5.1 · p. 14
• In Experiment 1, GD remained nearly unbiased for d = 10 and had small bias and low variability for d = 100; SAVE sometimes produced extreme estimates at d = 100.Lasso-FQE had substantial positive bias for shorter trajectories; SAVE’s large standard deviations and RMSEs occurred at (n, T) = (30, 40), (40, 30), and (50, 30).Source: §5.1 · p. 14
• GD was the most reliable across the low- and high-dimensional experiments and the most stable across reported CartPole configurations, despite a non-additive true Q-function.In CartPole, SAVE was substantially less stable.Source: §5.1 · p. 14, §5.2 · p. 15

5.2 Experiment 2: Cartpole

• For CartPole, Lasso-FQE had systematic negative bias at small T that decreased with longer trajectories, while SAVE’s RMSE reached 357.95 at (n, T) = (80, 50).The state included d0 = 4 relevant and d = 80 total variables; the reported true value at x = 0 was approximately 33.50.Source: §5.2 · pp. 14–15

A.1 Sparse Q Function and Sparse Completeness

• Under sparse completeness, the active-coordinate function class GK is closed under Γπ, and the appendix concludes this implies Assumption 1 directly.The appendix establishes Q ∈ GK by induction from the reward function and the operator’s closure on GK.Source: §A.1 · p. 15

A.2 Sufficient State

• Ma et al. (2023) define XK as sufficient when reward and next-state coordinates XK are conditionally independent of current Xt,Kc given (Xt,K, At).Source: §A.2 · p. 15
• Ma et al. (2023) show that if XK is sufficient, an optimal policy exists that depends only on XK, so policies can be restricted to functions of sufficient states.Source: §A.2 · p. 16

A.3 Proof of Proposition 1

• Under either sufficient condition, the Bellman operator preserves G_K, the class of bounded functions depending on the state only through x_K.The proof establishes preservation either when the full transition kernel and reward depend on x_K, or when the reduced transition property holds and the target policy depends only on active coordinates.Source: §A.3 · pp. 16–17
• Bellman iterates from zero converge uniformly to Qπ, so Qπ(x, a) = Qπ(x_K, a) for every state-action pair.The proof uses contraction for γ < 1 and closure of G_K under uniform limits.Source: §A.3 · p. 17
• Taking S_a = K for every action and |K| ≪ d establishes Assumption 1.Source: §A.3 · p. 17

Appendix B. Properties of B-spline basis functions

• The analysis uses order-m normalized B-splines with m fixed by smoothness and equally spaced distinct knots; it also uses a rescaled basis.Source: Appendix B · p. 17
• The B-spline basis functions form a partition of unity, satisfy 0 ≤ b_j(x) ≤ 1, and at most m are nonzero at any x.The stated bound is a basis property and does not depend on the distribution of X.Source: Appendix B · p. 18
• For equally spaced knots and fixed order m, B-spline stability yields eigenvalue bounds with constants independent of L.The passage invokes the standard stability property; the supplied text does not give the bounds’ exact values.Source: Appendix B · pp. 18–19

Appendix C. Additional technical details

• A matrix Freedman argument establishes a good event on which the estimator pair is feasible for optimization problem (11).Source: Appendix C · pp. 20, 23, 24
• For bounded horizons, the proof absorbs the factor T^1/2 into a constant in its high-probability bound.Source: Appendix C · p. 25
• For diverging horizons, the proof uses exponential β-mixing and Berbee coupling to form independent odd- and even-numbered blocks, then applies Hoeffding bounds.Source: Appendix C · pp. 26–27
• Lemma 23 states concentration bounds for independent mean-zero matrices and adapted matrix martingale differences, using Bernstein- and Azuma-type inequalities.Source: Appendix C · pp. 29–30
• Lemma 24 orders trajectories and time steps into a filtration so the summands, with inserted zero increments, form matrix martingale difference sequences.Source: Appendix C · pp. 32–33
• Under Assumption (A4), the state process is exponentially β-mixing, and the proof partitions time into consecutive blocks of length q, except possibly the last.The number of blocks is m = ⌈T/q⌉.Source: Appendix C · p. 33
• Berbee coupling produces mutually independent odd and even block-sum families with matching marginals and controlled mismatch probabilities.The block sums are measurable functions of state blocks, and the coupling auxiliaries can be chosen independently across trajectories.Source: Appendix C · pp. 33–34
• The total failure probability is at most exp{−3 log(nT ∨ d)} for sufficiently large nT ∨ d in both diverging- and bounded-T cases.The proof first bounds it by (4+2Cβ)(nT ∨ d)−4 in the diverging-T case.Source: Appendix C · p. 35

D.1 Proof of Theorem 10

• The proof defines coefficient supports whose union has size at most 2d0 and partitions the coefficient vector into group components.It denotes the selected coordinate and group supports by S and S, respectively.Source: §D.1 · p. 35
• The proof also considers relaxing the sparsity assumption to allow a group-norm tail.The supplied passage does not specify the resulting bound.Source: §D.1 · p. 37
• Combining upper and lower quadratic-form bounds yields an inequality that is solved for the coefficient-error bound.The proof first establishes the bounds on the relevant events.Source: §D.1 · pp. 37–38
• For the special case d = O(1), the passage invokes Lemma 24 on event G3, but the quoted text provides no further result or conditions.Source: §D.1 · p. 38

D.2 Proof of Theorem 12

• The triangle inequality bounds the value error by the estimator’s error relative to V^π* and the difference between V^π* and V^π.The remaining proof focuses on the estimation error.Source: §D.2 · p. 39
• The generalized test-error bound assumes the density μ̃_x is uniformly bounded by c̃_μ.Source: §D.2 · p. 40
• With L = (nT)^(1/(2m−1)), the approximation error d0L^−m is dominated by the preceding estimation error on the same event.Source: §D.2 · p. 42

• The proof bounds target-policy value error by the sum of the estimation error relative to V^π∗ and the difference between V^π∗ and V^π.Source: Proof · p. 42
• The remaining proof focuses on the estimation error.Source: Proof · p. 42
• The generalized test-error argument assumes μ̃_x ≤ c̃_μ; for stationary deterministic policies, the resulting matrix is block diagonal.Source: Proof · p. 43
• With L = (nT)^(1/(2m−1)), approximation error d_0L^-m is dominated by the preceding estimation error, with probability at least 1−exp{−c3 log(nT ∨ d)}.Source: Proof · pp. 43–44

D.3 Proof of Theorem 14

• Under Theorem 14’s condition, the proof considers an active feature for which an action exists and establishes a bound uniformly over action-state pairs.The supplied passages do not include the bound’s expression.Source: §D.3 · pp. 44–45
• Assuming an active index is omitted from the selected set leads to a contradiction as nT → ∞, because v is bounded away from zero.The contradiction uses the inequalities for every action and sufficiently large nT.Source: §D.3 · pp. 45–46
• The desired result follows on G1 ∩ G2, which occurs with the probability stated in Theorem 10.Source: §D.3 · p. 46

• Table 1 reports simulation results for d = 10, with each entry giving bias (SD) and RMSE.Source: Table 1 · p. 47
• Table 2 reports simulation results for d = 100, with each entry giving bias (SD) and RMSE.Source: Table 2 · p. 47
• Table 3 reports Cartpole environment simulation results, with each entry giving bias (SD) and RMSE.Source: Table 3 · p. 47