Abstract

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.

Key words and phrases: High-dimensional data, Off-policy evaluation, Rein- forcement learning, Sparsity

Information

Preprint No.SS-2025-0457
Manuscript IDSS-2025-0457
Complete AuthorsTuoyi Zhao, Chengchun Shi, Zhengling Qi, Lan Wang
Corresponding AuthorsLan Wang
Emailslxw611@miami.edu

References

  1. Proceedings of 1995 34th IEEE conference on decision and control, Volume 1, pp. 560–564. IEEE.
  2. Bibaut, A., M. Petersen, N. Vlassis, M. Dimakopoulou, and M. van der Laan (2021). Sequential causal inference in a single world of connected units.
  3. Bickel, P. J., Y. Ritov, and A. B. Tsybakov (2009). Simultaneous analysis of Lasso and Dantzig selector. The Annals of Statistics 37(4), 1705 – 1732.
  4. Bradley, R. C. (2005). Basic properties of strong mixing conditions. a survey and some open questions. Probability Surveys 2, 107–144.
  5. Candes, E. and T. Tao (2007). The Dantzig selector: Statistical estimation when p is much larger than n. The Annals of Statistics 35(6), 2313 – 2351.
  6. Duan, Y., Z. Jia, and M. Wang (2020). Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pp. 2701–2709. PMLR.
  7. Farahmand, A.-m., M. Ghavamzadeh, C. Szepesv´ari, and S. Mannor (2016). Regularized policy iteration with nonparametric function spaces. The Journal of Machine Learning Research 17(1), 4809–4874.
  8. Geist, M. and B. Scherrer (2011). l1-penalized projected Bellman residual. In European Workshop on Reinforcement Learning, pp. 89–101. Springer.
  9. Ghavamzadeh, M., A. Lazaric, R. Munos, and M. Hoffman (2011). Finite-sample analysis of Lasso-TD. In International Conference on Machine Learning.
  10. Golowich, N., A. Moitra, and D. Rohatgi (2024). Exploring and learning in sparse linear mdps without computationally intractable oracles. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 183–193.
  11. Gottesman, O., Y. Liu, S. Sussex, E. Brunskill, and F. Doshi-Velez (2019). Combining parametric and nonparametric models for off-policy evaluation. In International Conference on Machine Learning, pp. 2366–2375. PMLR.
  12. Hao, B., Y. Duan, T. Lattimore, C. Szepesv´ari, and M. Wang (2021a). Sparse feature selection makes batch reinforcement learning more sample efficient. In International Conference on Machine Learning, pp. 4063–4073. PMLR.
  13. Hao, B., T. Lattimore, C. Szepesv´ari, and M. Wang (2021b). Online sparse reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 316–324. PMLR.
  14. Hoffman, M. W., A. Lazaric, M. Ghavamzadeh, and R. Munos (2011). Regularized least squares temporal difference learning with nested l2 and l1 penalization. In European Workshop on Reinforcement Learning, pp. 102–114. Springer.
  15. Huang, J. Z. (1998). Projection estimation in multiple regression with application to functional ANOVA models. The Annals of Statistics 26(1), 242–272.
  16. Jiang, N. and L. Li (2016). Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 652–661. PMLR.
  17. Jin, C., Z. Yang, Z. Wang, and M. I. Jordan (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137–2143. PMLR.
  18. Kallus, N. and M. Uehara (2022). Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning. Operations Research 70(6), 3282–3302.
  19. Kolter, J. Z. and A. Y. Ng (2009). Regularization and feature selection in least-squares temporal difference learning. In Proceedings of the 26th annual international conference on machine learning, pp. 521–528.
  20. Lagoudakis, M. G. and R. Parr (2003). Least-squares policy iteration. The Journal of Machine Learning Research 4, 1107–1149.
  21. Liao, P., P. Klasnja, and S. Murphy (2021). Off-policy estimation of long-term average outcomes with applications to mobile health. Journal of the American Statistical Association 116(533), 382–391.
  22. Liao, P., Z. Qi, R. Wan, P. Klasnja, and S. A. Murphy (2022). Batch policy learning in average reward markov decision processes. Annals of statistics 50(6), 3364–3387.
  23. Liu, B., S. Mahadevan, and J. Liu (2012). Regularized off-policy TD-learning. In F. Pereira, C. Burges, L. Bottou, and K. Weinberger (Eds.), Advances in Neural Information Processing Systems, Volume 25. Curran Associates, Inc.
  24. Liu, H., J. Zhang, X. Jiang, and J. Liu (2010, 13–15 May). The group Dantzig selector. In Y. W.
  25. Teh and M. Titterington (Eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, Volume 9 of Proceedings of Machine Learning
  26. Research, Chia Laguna Resort, Sardinia, Italy, pp. 461–468. PMLR.
  27. Liu, Q., L. Li, Z. Tang, and D. Zhou (2018). Breaking the curse of horizon: Infinite-horizon offpolicy estimation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Advances in Neural Information Processing Systems, Volume 31. Curran Associates, Inc.
  28. Liu, Y., O. Gottesman, A. Raghu, M. Komorowski, A. A. Faisal, F. Doshi-Velez, and E. Brunskill
  29. (2018). Representation balancing MDPs for off-policy policy evaluation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Advances in Neural Information Processing Systems, Volume 31. Curran Associates, Inc.
  30. Lobo, M. S., L. Vandenberghe, S. Boyd, and H. Lebret (1998). Applications of second-order cone programming. Linear Algebra and its Applications 284(1-3), 193–228.
  31. Luckett, D. J., E. B. Laber, A. R. Kahkoska, D. M. Maahs, E. Mayer-Davis, and M. R. Kosorok
  32. (2020). Estimating dynamic treatment regimes in mobile health using v-learning. Journal of the American Statistical Association 115(530), pp. 692–706.
  33. Ma, T., J. Zhu, H. Cai, Z. Qi, Y. Chen, C. Shi, and E. B. Laber (2026). Sequential knockoffs for variable selection in reinforcement learning. Journal of the American Statistical Association 0(ja), 1–29.
  34. Mandel, T., Y.-E. Liu, S. Levine, E. Brunskill, and Z. Popovic (2014). Offline policy evaluation across representations with applications to educational games. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, pp. 1077–1084.
  35. Munos, R. (2003). Error bounds for approximate policy iteration. In Proceedings of the Twentieth International Conference on Machine Learning, pp. 560–567.
  36. Murphy, S. A. (2003). Optimal dynamic treatment regimes. Journal of the Royal Statistical Society Series B: Statistical Methodology 65(2), 331–355.
  37. Murphy, S. A., M. J. van der Laan, J. M. Robins, and C. P. P. R. Group (2001). Marginal mean models for dynamic regimes. Journal of the American Statistical Association 96(456), 1410–1423.
  38. Painter-Wakefield, C. and R. Parr (2012). Greedy algorithms for sparse reinforcement learning. In Proceedings of the 29th International Conference on Machine Learning, pp. 867–874.
  39. Ravikumar, P., J. Lafferty, H. Liu, and L. Wasserman (2009). Sparse additive models. Journal of the Royal Statistical Society Series B: Statistical Methodology 71(5), 1009–1030.
  40. Schumaker, L. (2007). Spline functions: basic theory. Cambridge University Press.
  41. Shi, C., S. Zhang, W. Lu, and R. Song (2022). Statistical inference of the value function for reinforcement learning in infinite-horizon settings. Journal of the Royal Statistical Society Series B: Statistical Methodology 84(3), 765–793.
  42. Sutton, R. S. and A. G. Barto (2018). Reinforcement Learning: An Introduction. Cambridge,
  43. MA, USA: A Bradford Book.
  44. Tang, L., R. Rosales, A. Singh, and D. Agarwal (2013). Automatic ad format selection via contextual bandits. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pp. 1587–1594.
  45. Thomas, P. and E. Brunskill (2016). Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 2139–2148. PMLR.
  46. Thomas, P., G. Theocharous, M. Ghavamzadeh, I. Durugkar, and E. Brunskill (2017). Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing. In Proceedings of the AAAI Conference on Artificial Intelligence, Volume 31, pp. 4740–4745.
  47. Tosatto, S., M. Pirotta, C. d’Eramo, and M. Restelli (2017). Boosted fitted Q-iteration. In International Conference on Machine Learning, pp. 3434–3443. PMLR.
  48. Wang, J., Z. Qi, and R. K. W. Wong (2023). Projected state-action balancing weights for offline reinforcement learning. The Annals of Statistics 51(4), 1639 – 1665.
  49. Yin, M. and Y.-X. Wang (2020). Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 3948–3958. PMLR.
  50. Yuan, M. and Y. Lin (2006). Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B: Statistical Methodology 68(1), 49–67. Yale University

Acknowledgments

The research of Zhao was supported in part by R01HL158075, P50HD052120,

and the Lambert Family Fellowship. The research of Wang was partially

supported by NSF DMS-2610563.

Supplementary Materials

Our supplementary material contains the technical derivations and detailed

numerical results. It consists of four parts. The first part provides additional details on the sparsity-aware Q-functions and the properties of B-

spline functions used in our analysis. The second part contains technical

lemmas. Lemma 3 and 5 provide spectral results related to ˆ︁Σ. Lemma 4

shows that the optimal model coefficients (α∗, β∗)⊕are feasible. The third

part provides the proofs of our main results, Theorem 5, 6, and 7. The final

part provides the numerical results corresponding to Section 5, which are

omitted from the main text due to the page limit.

Supplementary materials are available for download.