2020

Accountable Off-Policy Evaluation With Kernel Bellman Statistics

Feng, Yihao, Ren, Tongzheng, Tang, Ziyang et al.

Understand

We consider off-policy evaluation (OPE), which evaluates the performance of a new policy from observed data collected from previous experiments, without requiring the execution of the new policy.

This finds important applications in areas with high execution cost or safety concerns, such as medical diagnosis, recommendation systems and robotics.
In practice, due to the limited information from off-policy data, it is highly desirable to construct rigorous confidence intervals, not just point estimation, for the policy performance.
In this work, we propose a new variational framework which reduces the problem of calculating tight confidence bounds in OPE into an optimization problem on a feasible set that catches the true state-action value function with high probability.

Built on

Probability inequalities for sums of bounded random variables
Hoeffding, W · 1963
Earlier work this paper cites.
Markov Decision Processes: Discrete Stochastic Dynamic Programming
Puterman, M. L · 1994
Earlier work this paper cites.
Residual algorithms: Reinforcement learning with function approximation
Baird, L. C · 1995
Earlier work this paper cites.
Reinforcement Learning: An Introduction
Sutton, R. S. and Barto, A. G · 1998
Earlier work this paper cites.
Marginal mean models for dynamic regimes
Murphy, S. A., van der Laan, M., and Robins, J. M · 2001
Earlier work this paper cites.
Efficient estimation of average treatment effects using the estimated propensity score
Hirano, K., Imbens, G. W., and Ridder, G · 2003
Earlier work this paper cites.
Kernel least-squares temporal difference learning
Xu, X., Xie, T., Hu, D., and Lu, X · 2005
Earlier work this paper cites.
Kernelizing lspe ( λ \lambda )
Jung, T. and Polani, D · 2007
Earlier work this paper cites.
Random features for large-scale kernel machines
Rahimi, A. and Recht, B · 2007
Earlier work this paper cites.
Kernel-based least-squares policy iteration for reinforcement learning
Xu, X., Hu, D., and Lu, X · 2007
Earlier work this paper cites.
Kernelized value function approximation for reinforcement learning
Taylor, G. and Parr, R · 2009
Earlier work this paper cites.
Interval estimation for reinforcement-learning algorithms in continuous-state domains
White, M. and White, A · 2010
Earlier work this paper cites.
Doubly robust policy evaluation and learning
Dudík, M., Langford, J., and Li, L · 2011
Earlier work this paper cites.
Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms
Li, L., Chu, W., Langford, J., and Wang, X · 2011
Earlier work this paper cites.

Similar

Modelling transition dynamics in mdps with rkhs embeddings
Grunewalder, S., Lever, G., Baldassarre, L., Pontil, M., and Gretton, A · 2012
Cited alongside, same era.
Counterfactual reasoning and learning systems: The example of computational advertising
Bottou, L., Peters, J., Quiñonero-Candela, J., Charles, D. X., Chickering, D. M., Portugaly, E., Ray, D., Simard, P., and Snelson, E · 2013
Cited alongside, same era.
Openai gym
Original
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W · 2016
Cited alongside, same era.
CVXPY: A Python-embedded modeling language for convex optimization
Diamond, S. and Boyd, S · 2016
Cited alongside, same era.
Regularized policy iteration with nonparametric function spaces
Farahmand, A.-m., Ghavamzadeh, M., Szepesvári, C., and Mannor, S · 2016
Cited alongside, same era.
Doubly robust off-policy evaluation for reinforcement learning
Jiang, N. and Li, L · 2016
Cited alongside, same era.
Data-efficient off-policy policy evaluation for reinforcement learning
Thomas, P. S. and Brunskill, E · 2016
Cited alongside, same era.
Bootstrapping with models: Confidence intervals for off-policy evaluation
Hanna, J. P., Stone, P., and Niekum, S · 2017
Cited alongside, same era.
Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing
Thomas, P. S., Theocharous, G., Ghavamzadeh, M., Durugkar, I., and Brunskill, E · 2017
Cited alongside, same era.
Optimal and adaptive off-policy evaluation in contextual bandits
Wang, Y.-X., Agarwal, A., and Dudík, M · 2017
Cited alongside, same era.
A rewriting system for convex optimization problems
Agrawal, A., Verschueren, R., Diamond, S., and Boyd, S · 2018
Cited alongside, same era.
More robust doubly robust off-policy evaluation
Farajtabar, M., Chow, Y., and Ghavamzadeh, M · 2018
Cited alongside, same era.

Then

Breaking the curse of horizon: Infinite-horizon off-policy estimation
Liu, Q., Li, L., Tang, Z., and Zhou, D · 2018
Later among the works it cites.
Policy certificates: Towards accountable reinforcement learning
Dann, C., Li, L., Wei, W., and Brunskill, E · 2019
Later among the works it cites.
A kernel loss for solving the bellman equation
Feng, Y., Li, L., and Liu, Q · 2019
Later among the works it cites.
Off-policy estimation of long-term average outcomes with applications to mobile health
Original
Liao, P., Klasnja, P., and Murphy, S · 2019
Later among the works it cites.
Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections
Nachum, O., Chow, Y., Dai, B., and Li, L · 2019
Later among the works it cites.
Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling
Xie, T., Ma, Y., and Wang, Y.-X · 2019
Later among the works it cites.
Minimax-optimal off-policy evaluation with linear function approximation
Duan, Y., Jia, Z., and Wang, M · 2020
Closest in time.
Minimax confidence interval for off-policy evaluation and policy optimization
Original
Jiang, N. and Huang, J · 2020
Closest in time.
Provably efficient reinforcement learning with linear function approximation
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I · 2020
Closest in time.
Double reinforcement learning for efficient and robust off-policy evaluation
Kallus, N. and Uehara, M · 2020
Closest in time.
Black-box off-policy estimation for infinite-horizon reinforcement learning
Mousavi, A., Li, L., Liu, Q., and Zhou, D · 2020
Closest in time.
Doubly robust bias reduction in infinite horizon off-policy estimation
Tang, Z., Feng, Y., Li, L., Zhou, D., and Liu, Q · 2020
Closest in time.
Minimax weight and q-function learning for off-policy evaluation
Uehara, M., Huang, J., and Jiang, N · 2020
Closest in time.
Gendice: Generalized offline estimation of stationary values
Zhang, R., Dai, B., Li, L., and Schuurmans, D · 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…