2019

Minimax Weight and Q-Function Learning for Off-Policy Evaluation

Uehara, Masatoshi, Huang, Jiawei, Jiang, Nan

Understand

We provide theoretical investigations into off-policy evaluation in reinforcement learning using function approximators for (marginalized) importance weights and value functions.

Our contributions include: (1) A new estimator, MWL, that directly estimates importance ratios over the state-action distributions, removing the reliance on knowledge of the behavior policy as in prior work (Liu et al., 2018).
(2) Another new estimator, MQL, obtained by swapping the roles of importance weights and value-functions in MWL.
MQL has an intuitive interpretation of minimizing average Bellman errors and can be combined with MWL in a doubly robust manner.

Built on

On value functions and the agent-environment boundary
Original
Jiang, N. (2019) · 1905
Earlier work this paper cites.
Double reinforcement learning for efficient off-policy evaluation in markov decision processes
Original
Kallus, N. and M. Uehara (2019a) · 1908
Earlier work this paper cites.
Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizon processes
Original
Kallus, N. and M. Uehara (2019b) · 1909
Earlier work this paper cites.
Algaedice: Policy gradient from arbitrary experience
Original
Nachum, O., B. Dai, I. Kostrikov, Y. Chow, L. Li, and D. Schuurmans (2019) · 1912
Earlier work this paper cites.
Large sample estimation and hypothesis testing
Newey, W. K. and D. L. Mcfadden (1994) · 1994
Earlier work this paper cites.
An analysis of temporal-difference learning with function approximation
Tsitsiklis, J. N. and B. Van Roy (1997) · 1997
Earlier work this paper cites.
Efficient and Adaptive Estimation for Semiparametric Models
Bickel, P. J., C. A. J. Klaassen, Y. Ritov, and J. A. Wellner (1998) · 1998
Earlier work this paper cites.
On the role of the propensity score in efficient semiparametric estimation of average treatment effects
Hahn, J. (1998) · 1998
Earlier work this paper cites.
Asymptotic statistics
van der Vaart, A. W. (1998) · 1998
Earlier work this paper cites.
Hierarchical reinforcement learning with the maxq value function decomposition
Dietterich, T. G. (2000) · 2000
Earlier work this paper cites.
Eligibility Traces for Off-Policy Policy Evaluation
Precup, D., R. S. Sutton, and S. P. Singh (2000) · 2000
Earlier work this paper cites.
Minimax confidence interval for off-policy evaluation and policy optimization
Original
Jiang, N. and J. Huang (2020) · 2002
Earlier work this paper cites.
Rademacher and Gaussian complexities: Risk bounds and structural results
Bartlett, P. L. and S. Mendelson (2003) · 2003
Earlier work this paper cites.
Efficient estimation of average treatment effects using the estimated propensity score
Hirano, K., G. Imbens, and G. Ridder (2003) · 2003
Earlier work this paper cites.
A paradox concerning nuisance parameters and projected estimating functions
Henmi, M. and S. Eguchi (2004) · 2004
Earlier work this paper cites.

Similar

Least-squares policy iteration
Lagoudakis, M. and R. Parr (2004) · 2004
Cited alongside, same era.
Tree-based batch mode reinforcement learning
Ernst, D., P. Geurts, and L. Wehenkel (2005) · 2005
Cited alongside, same era.
Finite time bounds for sampling based fitted value iteration
Szepesvari, C. and R. Munos (2005) · 2005
Cited alongside, same era.
Towards a unified theory of state abstraction for MDPs
Li, L., T. J. Walsh, and M. L. Littman (2006) · 2006
Cited alongside, same era.
Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path
Antos, A., C. Szepesvári, and R. Munos (2008) · 2008
Cited alongside, same era.
Projected equation methods for approximate solution of large linear systems
Bertsekas, D. P. and H. Yu (2009) · 2009
Cited alongside, same era.
Markov Chains and Stochastic Stability
Meyn, S. and R. L. Tweedie (2009) · 2009
Cited alongside, same era.
Rademacher complexity bounds for non-i.i.d. processes
Mohri, M. and A. Rostamizadeh (2009) · 2009
Cited alongside, same era.
Hilbert space embeddings and metrics on probability measures
Sriperumbudur, B. K., A. Gretton, K. Fukumizu, B. Schölkopf, and G. R. Lanckriet (2010) · 2010
Cited alongside, same era.
Dynamic programming and optimal control
Bertsekas, D. P. (2012) · 2012
Cited alongside, same era.
A kernel two-sample test
Gretton, A., K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola (2012) · 2012
Cited alongside, same era.
Foundations of machine learning
Mohri, M., A. Rostamizadeh, and A. Talwalkar (2012) · 2012
Cited alongside, same era.

Then

OpenAI gym
Original
Brockman, G., V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba (2016) · 2016
Later among the works it cites.
Doubly Robust Off-policy Value Evaluation for Reinforcement Learning
Jiang, N. and L. Li (2016) · 2016
Later among the works it cites.
Augmented minimax linear estimation
Original
Hirshberg, D. A. and S. Wager (2017) · 2017
Later among the works it cites.
Contextual Decision Processes with low Bellman rank are PAC-learnable
Jiang, N., A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire (2017) · 2017
Later among the works it cites.
On oracle-efficient pac rl with rich observations
Dann, C., N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire (2018) · 2018
Later among the works it cites.
Breaking the curse of horizon: Infinite-horizon off-policy estimation
Liu, Q., L. Li, Z. Tang, and D. Zhou (2018) · 2018
Later among the works it cites.
Reinforcement learning: An introduction
Sutton, R. S. and A. G. Barto (2018) · 2018
Later among the works it cites.
Information-theoretic considerations in batch reinforcement learning
Chen, J. and N. Jiang (2019) · 2019
Closest in time.
A kernel loss for solving the bellman equation
Feng, Y., L. Li, and Q. Liu (2019) · 2019
Closest in time.
Importance sampling policy evaluation with an estimated behavior policy
Hanna, J., S. Niekum, and P. Stone (2019) · 2019
Closest in time.
Batch policy learning under constraints
Le, H., C. Voloshin, and Y. Yue (2019) · 2019
Closest in time.
Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling
Xie, T., Y. Ma, and Y.-X. Wang (2019) · 2019
Closest in time.
Generalized optimal matching methods for causal inference
Kallus, N. (2020) · 2020
Closest in time.
Harnessing infinite-horizon off-policy evaluation: Double robustness via duality
Tang, Z., Y. Feng, L. Li, D. Zhou, and Q. Liu (2020) · 2020
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…