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

By Masatoshi Uehara, Jiawei Huang, Nan Jiang. 2019

204 citations recorded by the source corpus.

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. (3) Several additional results that offer further insights into these methods, including the sample complexity analyses of MWL and MQL, their asymptotic optimality in the tabular setting, how the learned importance weights depend the choice of the discriminator class, and how our methods provide a unified view of some old and new algorithms in RL.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Reinforcement Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, background): “Recent work (Mousavi et al., 2020; Kallus and Uehara, 2019a,b; Tang et al., 2019; Uehara and Jiang, 2019) has refined this approach, in particular removing the need to have access to πβ .”
GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values (2020, background): “Inspired by Hallak & Mannor (2017); Liu et al. (2018), Gelada & Bellemare (2019); Uehara & Jiang (2019) pro-pose different estimators for learning density ratios, either with semi-gradient updates (Sutton, 1988) or by restricting the function class to Reproducing Kernel Hilbert Space.”
Reinforcement Learning via Fenchel-Rockafellar Duality (2020, background): “Unlike the previous form of the Lagrangian in (36), this optimization does not involve learning Q -values with respect to environment rewards, and in practice this distinction leads to much better optimization behavior (Uehara and Jiang, 2019).”
AlgaeDICE: Policy Gradient from Arbitrary Experience (2019, methodology): “If one were to follow derivations similar to AlgaeDICE but for the V -function LP, some form of explicit importance weighting (and thus knowledge of the behavior policy) would be required, as in recent work on off-policy estimation (Tang et al., 2019; Uehara and Jiang, 2019).”
Hyperparameter Selection for Offline Reinforcement Learning (2020, background): “A comprehensive empirical study of OPE methods was carried out in Voloshin et al. (2019). The study considered most of the aforementioned OPE methods and finds FQE to be surprisingly effective despite its simplicity. Compared to this work, Voloshin et al. (2019) examine simpler environments and data”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, methodology): “Starting with IH, this style of minimax estimator has recently attracted significant attention in OPE literature, including state-action extension of IH [54, 25] and DICE family of estimators [40, 61, 59, 10].”
Efficient Evaluation of Natural Stochastic Policies in Offline Reinforcement Learning (2020, background): “This is expected because both estimators are efficient in the tabular (hence parametric) setting when the evaluation policy is pre-specified (Uehara et al., 2020; Kallus and Uehara, 2019a); proving the analogous result for natural stochastic policy is future work.”
Instabilities of Offline RL with Pre-Trained Neural Representation (2021, unknown): “…2016, Guo et al., 2017, Wang et al., 2017, Liu et al., 2018, Farajtabar et al., 2018, Xie et al., 2019, Kallus and Uehara, 2019, Liu et al., 2019, Uehara and Jiang, 2019, Kallus and Uehara, 2020, Jiang and Huang, 2020, Feng et al., 2020, Yang et al., 2020, Nachum et al., 2019a, Zhang et al.,…”
Minimax Confidence Interval for Off-Policy Evaluation and Policy Optimization (2020, methodology): ““Value-learning” in a Nutshell MQL [1] seeks to find q such that q(s0, π) ≈ J(π).”
Provably Convergent Off-Policy Actor-Critic with Function Approximation (2019, background): “This density ratio can be learned by either Liu et al. (2018) as Liu et al. (2019) did or Hallak & Mannor (2017); Gelada & Bellemare (2019); Nachum et al. (2019); Uehara & Jiang (2019).”
Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation (2019, methodology): “This density ratio can be learned by either Liu et al. (2018) as Liu et al. (2019) did or (discounted) COP-TD, Nachum et al. (2019a), Uehara & Jiang (2019), Zhang et al. (2020a), and GradientDICE (Zhang et al., 2020b).”
Autoregressive Dynamics Models for Offline Policy Evaluation and Optimization (2021, methodology): “There exists a large body of work on OPE, including methods based on importance weighting (Precup, 2000; Li et al., 2014) and Lagrangian duality (Nachum et al., 2019; Yang et al., 2020; Uehara and Jiang, 2019).”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “One major line of work is concerned with the off-policy evaluation (OPE) problem [Li et al., 2015, Jiang and Li, 2016, Liu et al., 2018, Kallus and Uehara, 2019a,b, Uehara and Jiang, 2019, Xie et al., 2019, Yin and Wang, 2020, Duan and Wang, 2020].”
Is Pessimism Provably Efficient for Offline RL? (2020, unknown): “…et al., 2018; Liu et al., 2018; Xie et al., 2019; Nachum et al., 2019a;b; Tang et al., 2019; Kallus and Uehara, 2019; 2020; Jiang and Huang, 2020; Uehara et al., 2020; Duan et al., 2020; Yin and Wang, 2020; Yin et al., 2020; Nachum and Dai, 2020; Yang et al., 2020a; Zhang et al., 2020b) and the…”