2020

Minimax Value Interval for Off-Policy Evaluation and Policy Optimization

Jiang, Nan, Huang, Jiawei

Understand

We study minimax methods for off-policy evaluation (OPE) using value functions and marginalized importance weights.

Despite that they hold promises of overcoming the exponential variance in traditional importance sampling, several key problems remain: (1) They require function approximation and are generally biased.
For the sake of trustworthy OPE, is there anyway to quantify the biases? (2) They are split into two styles ("weight-learning" vs "value-learning").
Can we unify them? In this paper we answer both questions positively.

Built on

Algaedice: Policy gradient from arbitrary experience
Original
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans · 1912
Earlier work this paper cites.
Zur theorie der gesellschaftsspiele
J v Neumann · 1928
Earlier work this paper cites.
On general minimax theorems
Maurice Sion et al · 1958
Earlier work this paper cites.
Integral probability metrics and their generating classes of functions
Alfred Müller · 1997
Earlier work this paper cites.
Eligibility Traces for Off-Policy Policy Evaluation
Doina Precup, Richard S Sutton, and Satinder P Singh · 2000
Earlier work this paper cites.
R-max-a general polynomial time algorithm for near-optimal reinforcement learning
Ronen I Brafman and Moshe Tennenholtz · 2003
Earlier work this paper cites.
On the sample complexity of reinforcement learning
Sham Machandranath Kakade · 2003
Earlier work this paper cites.
Robust control of markov decision processes with uncertain transition matrices
Arnab Nilim and Laurent El Ghaoui · 2005
Earlier work this paper cites.
Finite-time bounds for fitted value iteration
Rémi Munos and Csaba Szepesvári · 2008
Earlier work this paper cites.
Error Propagation for Approximate Policy and Value Iteration
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos · 2010
Earlier work this paper cites.
Doubly Robust Policy Evaluation and Learning
Miroslav Dudík, John Langford, and Lihong Li · 2011
Earlier work this paper cites.
Playing atari with deep reinforcement learning
Original
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller · 2013
Earlier work this paper cites.

Similar

Toward minimax off-policy value estimation
Lihong Li, Rémi Munos, and Csaba Szepesvári · 2015
Cited alongside, same era.
Doubly Robust Off-policy Value Evaluation for Reinforcement Learning
Nan Jiang and Lihong Li · 2016
Cited alongside, same era.
Contextual decision processes with low Bellman rank are PAC-learnable
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire · 2017
Cited alongside, same era.
Primal-dual π \pi learning: Sample complexity and sublinear run time for ergodic markov decision problems
Original
Mengdi Wang · 2017
Cited alongside, same era.
Breaking the curse of horizon: Infinite-horizon off-policy estimation
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou · 2018
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Cited alongside, same era.
CS 598: Notes on Rmax exploration
Nan Jiang · 2018
Cited alongside, same era.
Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang · 2019
Cited alongside, same era.
Off-policy policy gradient with state distribution correction
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill · 2019
Cited alongside, same era.
Off-policy estimation of long-term average outcomes with applications to mobile health
Original
Peng Liao, Predrag Klasnja, and Susan Murphy · 2019
Cited alongside, same era.
Gendice: Generalized offline estimation of stationary values
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans · 2019
Cited alongside, same era.
A kernel loss for solving the bellman equation
Yihao Feng, Lihong Li, and Qiang Liu · 2019
Cited alongside, same era.

Then

Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizon processes
Original
Nathan Kallus and Masatoshi Uehara · 2019
Later among the works it cites.
Off-policy deep reinforcement learning without exploration
Scott Fujimoto, David Meger, and Doina Precup · 2019
Later among the works it cites.
Information-theoretic considerations in batch reinforcement learning
Jinglin Chen and Nan Jiang · 2019
Later among the works it cites.
Empirical study of off-policy policy evaluation for reinforcement learning
Original
Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue · 2019
Later among the works it cites.
Minimax Weight and Q-Function Learning for Off-Policy Evaluation
Masatoshi Uehara, Jiawei Huang, and Nan Jiang · 2020
Closest in time.
Accountable off-policy evaluation with kernel bellman statistics
Yihao Feng, Tongzheng Ren, Ziyang Tang, and Qiang Liu · 2020
Closest in time.
CoinDICE: Off-Policy Confidence Interval Estimation
Bo Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvari, and Dale Schuurmans · 2020
Closest in time.
Understanding the curse of horizon in off-policy evaluation via conditional importance sampling
Yao Liu, Pierre-Luc Bacon, and Emma Brunskill · 2020
Closest in time.
Conditional importance sampling for off-policy learning
Mark Rowland, Anna Harutyunyan, Hado van Hasselt, Diana Borsa, Tom Schaul, Rémi Munos, and Will Dabney · 2020
Closest in time.
GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values
Shangtong Zhang, Bo Liu, and Shimon Whiteson · 2020
Closest in time.
Harnessing infinite-horizon off-policy evaluation: Double robustness via duality
Ziyang Tang, Yihao Feng, Lihong Li, Dengyong Zhou, and Qiang Liu · 2020
Closest in time.
Reinforcement learning via fenchel-rockafellar duality
Original
Ofir Nachum and Bo Dai · 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…