2022

On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluation

Chen, Xiaohong, Qi, Zhengling

Understand

We study the off-policy evaluation (OPE) problem in an infinite-horizon Markov decision process with continuous states and actions.

We recast the $Q$-function estimation into a special form of the nonparametric instrumental variables (NPIV) estimation problem.
We first show that under one mild condition the NPIV formulation of $Q$-function estimation is well-posed in the sense of $L^2$-measure of ill-posedness with respect to the data generating distribution, bypassing a strong assumption on the discount factor $\gamma$ imposed in the recent literature for obtaining the $L^2$ convergence rates of various $Q$-function estimators.
Thanks to this new well-posed property, we derive the first minimax lower bounds for the convergence rates of nonparametric estimation of $Q$-function and its derivatives in both sup-norm and $L^2$-norm, which are shown to be the same as those for the classical nonparametric regression (Stone, 1982).

Built on

Xie, T., Ma, Y. & Wang, Y.-X. (2019), ‘Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling’, arXiv preprint arXiv:1906.03393
Original
1906
Earlier work this paper cites.
Kallus, N. & Uehara, M. (2019), ‘Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizon processes’, arXiv preprint arXiv:1909.05850
Original
1909
Earlier work this paper cites.
Uehara, M. & Jiang, N. (2019), ‘Minimax weight and q-function learning for off-policy evaluation’, arXiv preprint arXiv:1910.12809
Original
1910
Earlier work this paper cites.
Stone, C. J. (1982), ‘Optimal global rates of convergence for nonparametric regression’, The Annals of Statistics
1982
Earlier work this paper cites.
Cohen, A., Daubechies, I. & Vial, P. (1993), ‘Wavelets on the interval and fast wavelet transforms’, Applied and computational harmonic analysis
1993
Earlier work this paper cites.
Bradtke, S. J. & Barto, A. G. (1996), ‘Linear least-squares algorithms for temporal difference learning’, Machine learning
1996
Earlier work this paper cites.
Huang, J. Z. et al. (1998), ‘Projection estimation in multiple regression with application to functional anova models’, Annals of Statistics
1998
Earlier work this paper cites.
Precup, D., Sutton, R. S. & Singh, S. P. (2000), Eligibility traces for off-policy policy evaluation, in
2000
Earlier work this paper cites.
Dedecker, J. & Louhichi, S. (2002), Maximal inequalities and empirical central limit theorems, in
2002
Earlier work this paper cites.
Zhang, R., Dai, B., Li, L. & Schuurmans, D. (2020), ‘Gendice: Generalized offline estimation of stationary values’, arXiv preprint arXiv:2002.09072
Original
2002
Earlier work this paper cites.
Ai, C. & Chen, X. (2003), ‘Efficient estimation of models with conditional moment restrictions containing unknown functions’, Econometrica
2003
Earlier work this paper cites.
Newey, W. K. & Powell, J. L. (2003), ‘Instrumental variable estimation of nonparametric models’, Econometrica
2003
Earlier work this paper cites.
Bradley, R. C. (2005), ‘Basic properties of strong mixing conditions. a survey and some open questions’, Probability Surveys
2005
Earlier work this paper cites.
Ernst, D., Geurts, P., Wehenkel, L. & Littman, L. (2005), ‘Tree-based batch mode reinforcement learning’, Journal of Machine Learning Research
2005
Earlier work this paper cites.
Hall, P. & Horowitz, J. L. (2005), ‘Nonparametric methods for inference in the presence of instrumental variables’, The Annals of Statistics
2005
Earlier work this paper cites.
Levine, S., Kumar, A., Tucker, G. & Fu, J. (2020), ‘Offline reinforcement learning: Tutorial, review, and perspectives on open problems’, arXiv preprint arXiv:2005.01643
Original
2005
Earlier work this paper cites.
Blundell, R., Chen, X. & Kristensen, D. (2007), ‘Semi-nonparametric iv estimation of shape-invariant engel curves’, Econometrica
2007
Earlier work this paper cites.
Chen, X. (2007), ‘Large sample sieve estimation of semi-nonparametric models’, Handbook of Econometrics
2007
Earlier work this paper cites.
Liao, P., Qi, Z. & Murphy, S. (2020), ‘Batch policy learning in average reward markov decision processes’, arXiv preprint arXiv:2007.11771
Original
2007
Earlier work this paper cites.

Similar

Antos, A., Szepesvári, C. & Munos, R. (2008 a
2008
Cited alongside, same era.
Antos, A., Szepesvári, C. & Munos, R. (2008 b
2008
Cited alongside, same era.
Tsybakov, A. B. (2009), Introduction to Nonparametric Estimation
2009
Cited alongside, same era.
Chen, X. & Reiss, M. (2011), ‘On rate optimality for ill-posed inverse problems in econometrics’, Econometric Theory
2011
Cited alongside, same era.
Darolles, S., Fan, Y., Florens, J.-P. & Renault, E. (2011), ‘Nonparametric instrumental regression’, Econometrica
2011
Cited alongside, same era.
Tropp, J. (2011), ‘Freedman’s inequality for matrix martingales’, Electronic Communications in Probability
2011
Cited alongside, same era.
Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D. & Riedmiller, M. (2014), Deterministic policy gradient algorithms, in
2014
Cited alongside, same era.
Chen, X. & Christensen, T. M. (2015), ‘Optimal uniform convergence rates and asymptotic normality for series estimators under weak dependence and weak conditions’, Journal of Econometrics
2015
Cited alongside, same era.
Tropp, J. A. (2015), ‘An introduction to matrix concentration inequalities’, arXiv preprint arXiv:1501.01571
Original
2015
Cited alongside, same era.
Farahmand, A.-m., Ghavamzadeh, M., Szepesvári, C. & Mannor, S. (2016), ‘Regularized policy iteration with nonparametric function spaces’, The Journal of Machine Learning Research
2016
Cited alongside, same era.
Pinto, L. & Gupta, A. (2016), Supersizing self-supervision: Learning to grasp from 50k tries and 700 robot hours, in
2016
Cited alongside, same era.
Thomas, P. S., Theocharous, G., Ghavamzadeh, M., Durugkar, I. & Brunskill, E. (2017), Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing, in
2017
Cited alongside, same era.

Then

Nachum, O., Chow, Y., Dai, B. & Li, L. (2019), Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections, in
2019
Later among the works it cites.
Duan, Y., Jia, Z. & Wang, M. (2020), Minimax-optimal off-policy evaluation with linear function approximation, in
2020
Later among the works it cites.
Feng, Y., Ren, T., Tang, Z. & Liu, Q. (2020), Accountable off-policy evaluation with kernel bellman statistics, in
2020
Later among the works it cites.
Kallus, N. & Uehara, M. (2020), Statistically efficient off-policy policy gradients, in
2020
Later among the works it cites.
Shi, C., Zhang, S., Lu, W. & Song, R. (2020), ‘Statistical inference of the value function for reinforcement learning in infinite horizon settings’, Journal of the Royal Statistical Society: Series B, in press
2020
Later among the works it cites.
Tang, Z., Feng, Y., Li, L., Zhou, D. & Liu, Q. (2020), Doubly robust bias reduction in infinite horizon off-policy estimation, in
2020
Later among the works it cites.
Uehara, M., Huang, J. & Jiang, N. (2020), Minimax weight and q-function learning for off-policy evaluation, in
2020
Later among the works it cites.
Zhang, S., Liu, B. & Whiteson, S. (2020), Gradientdice: Rethinking generalized offline estimation of stationary values, in
2020
Later among the works it cites.
Agarwal, A., Kakade, S. M., Lee, J. D. & Mahajan, G. (2021), ‘On the theory of policy gradient methods: Optimality, approximation, and distribution shift’, Journal of Machine Learning Research
2021
Later among the works it cites.
Chen, Y., Xu, L., Gulcehre, C., Paine, T. L., Gretton, A., de Freitas, N. & Doucet, A. (2021), ‘On instrumental variable regression for deep offline policy evaluation’, arXiv preprint arXiv:2105.10148
Original
2021
Later among the works it cites.
Duan, Y., Wang, M. & Wainwright, M. J. (2021), ‘Optimal policy evaluation using kernel-based temporal difference methods’, arXiv preprint arXiv:2109.12002
Original
2021
Later among the works it cites.
Jin, Y., Yang, Z. & Wang, Z. (2021), Is pessimism provably efficient for offline rl?, in
2021
Later among the works it cites.
Shi, C., Wan, R., Chernozhukov, V. & Song, R. (2021), Deeply-debiased off-policy interval estimation, in
2021
Later among the works it cites.
Uehara, M., Imaizumi, M., Jiang, N., Kallus, N., Sun, W. & Xie, T. (2021), ‘Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency’, arXiv preprint arXiv:2102.02981
Original
2021
Later among the works it cites.
Uehara, M. & Sun, W. (2021), ‘Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage’, arXiv preprint arXiv:2107.06226
Original
2021
Later among the works it cites.
Wang, J., Qi, Z. & Wong, R. K. (2021), ‘Projected state-action balancing weights for offline reinforcement learning’, arXiv preprint arXiv:2109.04640
Original
2021
Later among the works it cites.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P. & Agarwal, A. (2021), ‘Bellman-consistent pessimism for offline reinforcement learning’, arXiv preprint arXiv:2106.06926
Original
2021
Later among the works it cites.
Xu, T., Yang, Z., Wang, Z. & Liang, Y. (2021), ‘Doubly robust off-policy actor-critic: Convergence and optimality’, arXiv preprint arXiv:2102.11866
Original
2021
Later among the works it cites.
Zanette, A., Wainwright, M. J. & Brunskill, E. (2021), ‘Provable benefits of actor-critic methods for offline reinforcement learning’, Advances in neural information processing systems
2021
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…