2019

Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning

Kallus, Nathan, Uehara, Masatoshi

Understand

Off-policy evaluation (OPE) in reinforcement learning is notoriously difficult in long- and infinite-horizon settings due to diminishing overlap between behavior and target policies.

In this paper, we study the role of Markovian and time-invariant structure in efficient OPE.
We first derive the efficiency bounds for OPE when one assumes each of these structures.
This precisely characterizes the curse of horizon: in time-variant processes, OPE is only feasible in the near-on-policy setting, where behavior and target policies are sufficiently similar.

Built on

Smucler E, Rotnitzky A, Robins JM (2019) A unifying approach for doubly-robust ℓ 1 \ell_{1} regularized estimation of causal contrasts. arXiv preprint arXiv:1904.03737
Original
1904
Earlier work this paper cites.
Yu H, Mahmood AR, Sutton RS (2018) On generalized bellman equations and temporal-difference learning. The Journal of Machine Learning Research 19(1):1864–1912
1912
Earlier work this paper cites.
Ibragimov IA, Linnik YV (1971) Independent and stationary sequences of random variables (The Netherlands: Walters-Noordhof)
1971
Earlier work this paper cites.
Klaassen CAJ (1987) Consistent estimation of the influence function of locally asymptotically linear estimators. The Annals of Statistics 15:1548–1562
1987
Earlier work this paper cites.
Newey WK (1990) Semiparametric efficiency bounds. Journal of applied econometrics 5(2):99–135
1990
Earlier work this paper cites.
van der Vaart AW (1991) On differentiable functionals. Ann. Statist. 19:178–204
1991
Earlier work this paper cites.
Davidson JEH (1994) Stochastic limit theory :an introduction for econometricians . Advanced texts in econometrics (Oxford)
1994
Earlier work this paper cites.
Robins JM, Rotnitzky A, Zhao LP (1994) Estimation of regression coefficients when some regressors are not always observed. Journal of the American Statistical Association 89:846–866
1994
Earlier work this paper cites.
Hahn J (1997) Efficient estimation of panel data models with sequential moment restrictions. Journal of Econometrics 79:1–21
1997
Earlier work this paper cites.
Bickel PJ, Klaassen CAJ, Ritov Y, Wellner JA (1998) Efficient and Adaptive Estimation for Semiparametric Models (Springer)
1998
Earlier work this paper cites.
Chen X, Shen X (1998) Sieve extremum estimates for weakly dependent data. Econometrica 66:289–314
1998
Earlier work this paper cites.
van der Vaart AW (1998) Asymptotic statistics (Cambridge, UK: Cambridge University Press)
1998
Earlier work this paper cites.
Boyan JA (1999) Least-squares temporal difference learning. ICML , 49–56
1999
Earlier work this paper cites.
Scharfstein D, Rotnizky A, Robins JM (1999) Adjusting for nonignorable dropout using semi-parametric models. Journal of the American Statistical Association 94:1096–1146
1999
Earlier work this paper cites.
Tripathi G (1999) A matrix extension of the Cauchy-Schwarz inequality. Economics Letters 63:1–3
1999
Earlier work this paper cites.
Precup D, Sutton R, Singh S (2000) Eligibility traces for off-policy policy evaluation. In Proceedings of the 17th International Conference on Machine Learning 759–766
2000
Earlier work this paper cites.
Murphy SA, Van Der Laan MJ, Robins JM (2001) Marginal mean models for dynamic regimes. Journal of the American Statistical Association 96:1410–1423
2001
Earlier work this paper cites.
Hirano K, Imbens G, Ridder G (2003) Efficient estimation of average treatment effects using the estimated propensity score. Econometrica 71:1161–1189
2003
Earlier work this paper cites.
Murphy SA (2003) Optimal dynamic treatment regimes. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 65:331–355
2003
Earlier work this paper cites.
Nedić A, Bertsekas DP (2003) Least squares policy evaluation algorithms with linear function approximation. Discrete Event Dynamic Systems 13:79–110
2003
Earlier work this paper cites.

Similar

Jones GL (2004) On the markov chain central limit theorem. Probab. Surveys 1:299–320
2004
Cited alongside, same era.
Lagoudakis M, Parr R (2004) Least-squares policy iteration. Journal of Machine Learning Research 4:1107–1149
2004
Cited alongside, same era.
Bradley RC (2005) Basic properties of strong mixing conditions. a survey and some open questions. Probability Surveys 2:107–144
2005
Cited alongside, same era.
Kallus N, Uehara M (2020b) Efficient evaluation of natural stochastic policies in offline reinforcement learning. arXiv preprint arXiv: 2006.03886
2006
Cited alongside, same era.
Tsiatis AA (2006) Semiparametric Theory and Missing Data . Springer Series in Statistics (New York, NY: Springer New York)
2006
Cited alongside, same era.
Chen X (2007) Chapter 76 large sample sieve estimation of semi-nonparametric models. Handbook of Econometrics 6:5549–5632
2007
Cited alongside, same era.
Tan Z (2007) Comment: Understanding or, ps and dr. Statistical Science 22(4):560–568, ISSN 08834237
2007
Cited alongside, same era.
Antos A, Szepesvári C, Munos R (2008) Fitted q-iteration in continuous action-space mdps. Advances in Neural Information Processing Systems 20 , 9–16
2008
Cited alongside, same era.
Kosorok MR (2008) Introduction to Empirical Processes and Semiparametric Inference . Springer Series in Statistics (New York, NY: Springer New York)
2008
Cited alongside, same era.
Meyn S, Tweedie RL (2009) Markov Chains and Stochastic Stability (New York: Cambridge University Press), 2nd ed. edition
2009
Cited alongside, same era.
Zheng W, van Der Laan MJ (2011) Cross-validated targeted minimum-loss-based estimation. Targeted Learning: Causal Inference for Observational and Experimental Data , 459–474, Springer Series in Statistics (New York, NY: Springer New York)
2011
Cited alongside, same era.
Bertsekas DP (2012) Dynamic programming and optimal control . Athena Scientific optimization and computation series (Belmont, Mass: Athena Scientific), 4th ed. edition
2012
Cited alongside, same era.

Then

Brockman G, Cheung V, Pettersson L, Schneider J, Schulman J, Tang J, Zaremba W (2016) OpenAI gym. arXiv preprint arXiv:1606.01540
Original
2016
Later among the works it cites.
Jiang N, Li L (2016) Doubly robust off-policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on International Conference on Machine Learning-Volume 652–661
2016
Later among the works it cites.
Munos R, Stepleton T, Harutyunyan A, Bellemare M (2016) Safe and efficient off-policy reinforcement learning. Advances in Neural Information Processing Systems 29 , 1054–1062
2016
Later among the works it cites.
Thomas P, Brunskill E (2016) Data-efficient off-policy policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning 2139–2148
2016
Later among the works it cites.
Chernozhukov V, Chetverikov D, Demirer M, Duflo E, Hansen C, Newey W, Robins J (2018) Double/debiased machine learning for treatment and structural parameters. Econometrics Journal 21:C1–C68
2018
Later among the works it cites.
Farajtabar M, Chow Y, Ghavamzadeh M (2018) More robust doubly robust off-policy evaluation. In Proceedings of the 35th International Conference on Machine Learning 1447–1456
2018
Later among the works it cites.
Kallus N (2018) Balanced policy evaluation and learning. Advances in Neural Information Processing Systems , 8895–8906
2018
Later among the works it cites.
Luckett DJ, Laber EB, Kahkoska AR, Maahs DM, Mayer-Davis E, Kosorok MR (2018) Estimating dynamic treatment regimes in mobile health using v-learning. Journal of the American Statistical Association 1–34
2018
Later among the works it cites.
Sutton RS, Barto AG (2018) Reinforcement learning: An introduction (Cambridge: MIT press)
2018
Later among the works it cites.
Gottesman O, Johansson F, Komorowski M, Faisal A, Sontag D, Doshi-Velez F, Celi LA (2019) Guidelines for reinforcement learning in healthcare. Nat Med 25:16–18
2019
Closest in time.
Kallus N, Uehara M (2019) Intrinsically efficient, stable, and bounded off-policy evaluation for reinforcement learning. Advances in Neural Information Processing Systems 32 , 3320–3329
2019
Closest in time.
Nachum O, Chow Y, Dai B, Li L (2019) Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems 2019 (To appear)
2019
Closest in time.
Rotnitzky A, Smucler E, Robins J (2019) Characterization of parameters with a mixed bias property. arXiv preprint arXiv:1509.02556
Original
2019
Closest in time.
Xie T, Ma Y, Wang YX (2019) Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in Neural Information Processing Systems 32 , 9665–9675
2019
Closest in time.
Huang J, Jiang N (2020) From importance sampling to doubly robust policy gradient. International Conference on Machine Learning , 4434–4443 (PMLR)
2020
Closest in time.
Tang Z, Feng Y, Li L, Zhou D, Liu Q (2020) Harnessing infinite-horizon off-policy evaluation: Double robustness via duality. ICLR 2020 (To appear)
2020
Closest in time.
Uehara M, Huang J, Jiang N (2020) Minimax weight and q-function learning for off-policy evaluation. International Conference on Machine Learning , 9659–9668
2020
Closest in time.
Ueno T, Kawanabe M, Mori T, Maeda SI, Ishii S (2011) Generalized td learning. Journal of Machine Learning Research 12:1977––2020
2020
Closest in time.
Huang A, Jiang N (2022) Beyond the return: Off-policy function estimation under user-specified error-measuring distributions. arXiv preprint arXiv:2210.15543
Original
2022
Closest in time.
Khan S, Tamer E (2010) Irregular identification, support conditions, and inverse weight estimation. Econometrica 78:2021–2042
2042
Closest in time.

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…