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

References

• Antos A, Szepesvári C, Munos R (2008) Fitted Q-iteration in continuous action-space MDPs. Adv. Neural Inform. Processing Systems 20:9–16.Google Scholar
• Bertsekas DP (2012) Dynamic Programming and Optimal Control, 4th ed. Athena Scientific Optimization and Computation Series (Athena Scientific, Belmont, MA).Google Scholar
• Bickel PJ, Klaassen CAJ, Ritov Y, Wellner JA (1998) Efficient and Adaptive Estimation for Semiparametric Models (Springer, New York).Google Scholar
• Boyan JA (1999) Least-squares temporal difference learning. Proc. Internat. Conf. Machine Learn. (ICML), 49–56.Google Scholar
• Bradley RC (2005) Basic properties of strong mixing conditions. A survey and some open questions. Probab. Surveys 2:107–144.Crossref, Google Scholar
• Brockman G, Cheung V, Pettersson L, Schneider J, Schulman J, Tang J, Zaremba W (2016) OpenAI gym. Preprint, submitted June 5, https://arxiv.org/abs/1606.01540.Google Scholar
• Chen X (2007) Large sample sieve estimation of semi-nonparametric models. Heckman JJ, Leamer EE, eds. Handbook of Econometrics (Elsevier, New York), 6:5549–5632.Crossref, Google Scholar
• Chen X, Shen X (1998) Sieve extremum estimates for weakly dependent data. Econometrica 66:289–314.Crossref, Google Scholar
• Chernozhukov V, Chetverikov D, Demirer M, Duflo E, Hansen C, Newey W, Robins J (2018) Double/debiased machine learning for treatment and structural parameters. Econom. J. 21:C1–C68.Crossref, Google Scholar
• Dudik M, Erhan D, Langford J, Li L (2014) Doubly robust policy evaluation and optimization. Statist. Sci. 29:485–511.Crossref, Google Scholar
• Ertefaie A (2014) Constructing dynamic treatment regimes in infinite-horizon settings. Preprint, submitted June 3, https://arxiv.org/abs/1406.0764.Google Scholar
• Farajtabar M, Chow Y, Ghavamzadeh M (2018) More robust doubly robust off-policy evaluation. Proc. 35th Internat. Conf. Machine Learn., 1447–1456.Google Scholar
• Gottesman O, Johansson F, Komorowski M, Faisal A, Sontag D, Doshi-Velez F, Celi LA (2019) Guidelines for reinforcement learning in healthcare. Nature Medicine 25:16–18.Crossref, Google Scholar
• Hahn J (1997) Efficient estimation of panel data models with sequential moment restrictions. J. Econometrics 79:1–21.Crossref, Google Scholar
• Hernández-Lerma O, Lasserre JB (2012) Discrete-Time Markov Control Processes: Basic Optimality Criteria, vol. 30 (Springer Science & Business Media, New York)Google Scholar
• Hirano K, Imbens G, Ridder G (2003) Efficient estimation of average treatment effects using the estimated propensity score. Econometrica 71:1161–1189.Crossref, Google Scholar
• Huang J, Jiang N (2020) From importance sampling to doubly robust policy gradient. Proc. Internat. Conf. Machine Learn. (PMLR), 4434–4443.Google Scholar
• Ibragimov IA, Linnik YV (1971) Independent and Stationary Sequences of Random Variables (Walters-Noordhof, The Netherlands).Google Scholar
• Jiang N, Li L (2016) Doubly robust off-policy value evaluation for reinforcement learning. Proc. 33rd Internat. Conf. Machine Learn., 652–661.Google Scholar
• Jones GL (2004) On the Markov chain central limit theorem. Probab. Surveys 1:299–320.Crossref, Google Scholar
• Kallus N (2018) Balanced policy evaluation and learning. Adv. Neural Inform. Processing Systems 31:8895–8906.Google Scholar
• Kallus N, Uehara M (2019) Intrinsically efficient, stable, and bounded off-policy evaluation for reinforcement learning. Adv. Neural Inform. Processing Systems 32:3320–3329.Google Scholar
• Kallus N, Uehara M (2020a) Double reinforcement learning for efficient off-policy evaluation in Markov decision processes. J. Machine Learn. Res. 21(167):1–63.Google Scholar
• Kallus N, Uehara M (2020b) Efficient evaluation of natural stochastic policies in offline reinforcement learning. Preprint, submitted June 3, https://arxiv.org/abs/2006.03886.Google Scholar
• Kallus N, Uehara M (2020c) Statistically efficient off-policy policy gradients. Proc. Internat. Conf. Machine Learn. (PMLR), 5089–5100.Google Scholar
• Khan S, Tamer E (2010) Irregular identification, support conditions, and inverse weight estimation. Econometrica 78:2021–2042.Crossref, Google Scholar
• Klaassen CAJ (1987) Consistent estimation of the influence function of locally asymptotically linear estimators. Ann. Statist. 15:1548–1562.Crossref, Google Scholar
• Kosorok MR (2008) Introduction to Empirical Processes and Semiparametric Inference. Springer Series in Statistics (Springer, New York).Crossref, Google Scholar
• Lagoudakis M, Parr R (2004) Least-squares policy iteration. J. Machine Learn. Res. 4:1107–1149.Google Scholar
• Li L, Munos R, Szepesvari C (2015) Toward minimax off-policy value estimation. Proc. 18th Internat. Conf. Artificial Intelligence Statist. (San Diego, CA), 608–616.Google Scholar
• Liu Q, Li L, Tang Z, Zhou D (2018a) Breaking the curse of horizon: Infinite-horizon off-policy estimation. Adv. Neural Inform. Processing Systems 31:5356–5366.Google Scholar
• Liu Y, Gottesman O, Raghu A, Komorowski M, Faisal AA, Doshi-Velez F, Brunskill E (2018b) Representation balancing MDPs for off-policy policy evaluation. Adv. Neural Inform. Processing Systems 31:2644–2653.Google Scholar
• Luckett DJ, Laber EB, Kahkoska AR, Maahs DM, Mayer-Davis E, Kosorok MR (2020) Estimating dynamic treatment regimes in mobile health using v-learning. J. Amer. Statist. Assoc. 115(530):692–706.Crossref, Google Scholar
• Mahmood AR, van Hasselt HP, Sutton RS (2014) Weighted importance sampling for off-policy learning with linear function approximation. Adv. Neural Inform. Processing Systems 27:3014–3022.Google Scholar
• Mandel T, Liu Y, Levine S, Brunskill E, Popovic Z (2014) Off-policy evaluation across representations with applications to educational games. Proc. 13th Internat. Conf. Autonomous Agents Multi-agent Systems, 1077–1084.Google Scholar
• Meyn S, Tweedie RL (2009) Markov Chains and Stochastic Stability, 2nd ed. (Cambridge University Press, New York).Crossref, Google Scholar
• Munos R, Stepleton T, Harutyunyan A, Bellemare M (2016) Safe and efficient off-policy reinforcement learning. Adv. Neural Inform. Processing Systems 29:1054–1062.Google Scholar
• Murphy SA (2003) Optimal dynamic treatment regimes. J. Royal Statist. Soc. Ser. B Statist. Methodology 65:331–355.Crossref, Google Scholar
• Murphy SA, Van Der Laan MJ, Robins JM (2001) Marginal mean models for dynamic regimes. J. Amer. Statist. Assoc. 96:1410–1423.Crossref, Google Scholar
• Nachum O, Chow Y, Dai B, Li L (2019) DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections. Adv. Neural Inform. Processing Systems, vol. 32.Google Scholar
• Nedić A, Bertsekas DP (2003) Least squares policy evaluation algorithms with linear function approximation. Discrete Event Dynam. Systems 13:79–110.Crossref, Google Scholar
• Newey WK (1990) Semiparametric efficiency bounds. J. Appl. Econometrics 5(2):99–135.Crossref, Google Scholar
• Precup D, Sutton R, Singh S (2000) Eligibility traces for off-policy policy evaluation. Proc. 17th Internat. Conf. Machine Learn., 759–766.Google Scholar
• Robins JM, Rotnitzky A, Zhao LP (1994) Estimation of regression coefficients when some regressors are not always observed. J. Amer. Statist. Assoc. 89:846–866.Crossref, Google Scholar
• Rotnitzky A, Smucler E, Robins J (2021) Characterization of parameters with a mixed bias property. Biometrika 108(1):231–238.Google Scholar
• Scharfstein D, Rotnizky A, Robins JM (1999) Adjusting for nonignorable dropout using semi-parametric models. J. Amer. Statist. Assoc. 94:1096–1146.Crossref, Google Scholar
• Smucler E, Rotnitzky A, Robins JM (2019) A unifying approach for doubly-robust ℓ1 regularized estimation of causal contrasts. Preprint, submitted April 7, https://arxiv.org/abs/1904.03737v1.Google Scholar
• Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction (MIT Press, Cambridge, MA).Google Scholar
• Sutton RS, Maei HR, Szepesvári C (2009a) A convergent o(n) temporal-difference algorithm for off-policy learning with linear function approximation. Adv. Neural Inform. Processing Systems 21:1609–1616.Google Scholar
• Sutton RS, Maei HR, Precup D, Bhatnagar S, Silver D, Szepesvári C, Wiewiora E (2009b) Fast gradient-descent methods for temporal-difference learning with linear function approximation. Proc. 26th Annual Internat. Conf. Machine Learn. (ICML), 993–1000.Google Scholar
• Tan Z (2007) Comment: Understanding OR, PS and DR. Statist. Sci. 22(4):560–568.Google Scholar
• Tang Z, Feng Y, Li L, Zhou D, Liu Q (2020) Harnessing infinite-horizon off-policy evaluation: Double robustness via duality. ICLR 2020, 1–20. https://iclr.cc/virtual_2020/poster_S1glGANtDr.html. Google Scholar
• Thomas P, Brunskill E (2016) Data-efficient off-policy policy evaluation for reinforcement learning. Proc. 33rd Internat. Conf. Machine Learn. 2139–2148.Google Scholar
• Tsiatis AA (2006) Semiparametric Theory and Missing Data. Springer Series in Statistics (Springer, New York).Google Scholar
• Uehara M, Huang J, Jiang N (2020) Minimax weight and q-function learning for off-policy evaluation. Proc. Internat. Conf. Machine Learn., 9659–9668.Google Scholar
• Ueno T, Kawanabe M, Mori T, Maeda SI, Ishii S (2011) Generalized TD learning. J. Machine Learn. Res. 12:1977–2020.Google Scholar
• van der Vaart AW (1998) Asymptotic Statistics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Xie T, Ma Y, Wang YX (2019) Toward optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Adv. Neural Inform. Processing Systems 32:9665–9675.Google Scholar
• Yu H (2012) Least squares temporal difference methods: An analysis under general conditions. SIAM J. Control Optim. 50(6):3310–3343.Crossref, Google Scholar
• Yu H, Mahmood AR, Sutton RS (2018) On generalized Bellman equations and temporal-difference learning. J. Machine Learn. Res. 19(1):1864–1912.Google Scholar
• Zheng W, van Der Laan MJ (2011) Cross-validated targeted minimum-loss-based estimation. van Der Laan MJ, Rose S, eds. Targeted Learning: Causal Inference for Observational and Experimental Data. Springer Series in Statistics (Springer, New York), 459–474.Crossref, Google Scholar