PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Masatoshi Uehara, Jiawei Huang, Nan Jiang

arXiv:1910.12809v4cs.LGstat.ML

TL;DR

The paper studies how to perform off-policy evaluation with function approximators despite horizon-induced variance and limitations of prior marginalized importance-sampling methods. It introduces MWL for direct state-action ratio learning and MQL by swapping weights with Q-functions, then establishes theoretical guarantees and connections to existing algorithms. In the tabular setting, state-action variants achieve the semiparametric lower bound, while the framework also supports doubly robust combinations and unified interpretations of several RL methods.

  • Problem

    Off-policy evaluation must estimate a target policy’s return from behavior-policy data, while unbiased estimators can have variance exponential in horizon and prior MIS requires behavior-policy knowledge.

  • Method

    The paper develops MWL for state-action importance-ratio learning and MQL by exchanging the roles of importance weights and Q-functions, with a doubly robust combination.

  • Results

    In the tabular setting, state-action MWL and MQL achieve the semiparametric lower bound for OPE, unlike their state-function variants.

  • Takeaways & Limitations

    The methods provide behavior-policy-agnostic ratio learning and a unified view of algorithms including LSTDQ, off-policy LSTD, model-based OPE, and step-wise importance sampling.

  • Takeaways & Limitations

    The analysis includes technical assumptions such as support and bounded-ratio conditions, and extending the discussed bias-variance trade-off from contextual bandits to sequential decision-making is not obvious.

Abstract

from arXiv · show

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.

1. Introduction

Off-policy evaluation is difficult because unbiased estimators can have exponentially increasing variance with horizon. The paper develops minimax estimators that learn marginalized weights and value functions with broader applicability and theoretical guarantees.

  • Off-policy evaluation estimates a new policy’s performance from data collected by another policy, but unbiased estimators can suffer variance exponential in horizon.This is known as the curse of horizon.
  • Marginalized importance sampling reduces variance by learning weights that convert behavior-policy state distributions into target-policy state distributions.The approach relies on relatively mild representation assumptions but prior work requires knowledge of the behavior policy.
  • MWL directly estimates importance ratios over state-action distributions without relying on knowledge of the behavior policy.
  • MQL swaps the roles of importance weights and Q-functions in MWL, and MWL and MQL can be combined through a doubly robust estimator.
  • In the tabular setting, state-action versions of MWL and MQL achieve the semiparametric lower bound, while their state-function variants do not.
  • The framework unifies several reinforcement-learning algorithms, including LSTDQ, off-policy LSTD, model-based OPE, and step-wise importance sampling.These algorithms arise as special cases under particular function-class choices.

2. Preliminaries

The paper formulates OPE in an infinite-horizon discounted MDP using state-action occupancy distributions and data generated under an exploratory behavior distribution. Its concentration arguments can extend beyond i.i.d. data.

  • An infinite-horizon discounted MDP is described by state and action spaces, transitions, rewards, a discount factor, and trajectory-generating policies.
  • The paper uses normalized discounted occupancy distributions over state-action pairs induced by a policy.
  • OPE estimates the discounted return of an evaluation policy from data generated by a different behavior policy.
  • The data distribution is assumed to be exploratory and to provide sufficient coverage of the state space.
  • The paper does not require the exploratory state distribution to equal the behavior policy’s discounted occupancy.
  • Although the exposition assumes i.i.d. data, the method requires empirical expectations to concentrate and can apply to suitably mixing single trajectories.

3. Overview of OPE Methods

OPE methods trade off representation assumptions, behavior-policy knowledge, and variance. Direct methods avoid behavior-policy knowledge but may require strong representations, while importance sampling faces horizon-driven variance and MIS can reduce it under state-distribution overlap.

  • Direct Methods: Direct methods estimate an MDP model or target-policy Q-function, avoid behavior-policy knowledge, and often require strong representation assumptions.
  • The overview compares OPE methods by behavior-policy requirements, function-approximation conditions, and whether discriminator classes operate on states or state-action pairs.
  • Importance Sampling: Importance sampling is unbiased but accumulates per-step action ratios across trajectories, producing exponential variance in horizon.
  • Importance Sampling: In stochastic MDPs with substantial stochasticity, combining importance sampling with direct methods cannot eliminate importance sampling’s exponential variance.
  • Marginalized Importance Sampling: MIS reweights individual rewards using marginalized ratios and can have lower variance than trajectory-level importance sampling when behavior and evaluation state distributions overlap.
  • Marginalized Importance Sampling: Prior MIS estimates state-distribution weights with two function approximators and requires knowledge of the behavior policy.

4. Minimax Weight Learning (MWL)

MWL learns state-action importance ratios through a minimax objective whose discriminators include the target Q-function, enabling behavior-policy-agnostic reward reweighting. Its guarantees depend on function-class coverage and support assumptions, while linear and kernel cases connect it to existing methods.

  • MWL uses a Q-function discriminator class realizing Qπe to learn importance weights over state-action pairs without knowing πb.
  • The learned weights directly reweight behavior-policy rewards to estimate the evaluation-policy return.
  • MWL assumes a compact state-action space and bounded importance ratios, with finite-space results requiring only minor modifications.
  • The true importance ratio satisfies the population loss equations and is unique under richer function conditions and full state-action support.
  • MWL minimizes a finite-sample minimax objective over a weight class and discriminator class.The empirical estimator replaces exact expectations with sample averages.
  • Qπe belonging to the convex hull of the discriminator class, together with a small minimax residual, is sufficient for accurate estimation; weight-class realizability is not always necessary.
  • Case Studies: With RKHS discriminators, the inner maximization has a closed form; with shared linear classes, MWL connects to LSTDQ.
  • Connections: The framework also connects to off-policy LSTD, kernel mean matching, and step-wise importance sampling under specific choices of function classes or discount factor.

5. Minimax Q-Function Learning (MQL)

MQL learns the target policy’s Q-function by using importance weights as discriminators, yielding an objective interpretable as average Bellman error. Its theory covers relaxed representation conditions, statistical efficiency, and connections to established RL estimators.

  • Estimator: MQL swaps the roles of value-function and importance-weight classes to learn Qπe from off-policy data.Its objective uses importance weights as discriminators.
  • Estimator: The MQL loss becomes an average Bellman error under the distribution induced by the importance-weight function.When that distribution is dπe,γ, the resulting error directly relates to OPE estimation accuracy.
  • Theory: Qπe uniquely makes the MQL loss zero when the data state-action distribution has positive support everywhere.The uniqueness statement holds for all square-integrable discriminator functions.
  • Theory: MQL remains accurate under certain representation conditions and can relax direct realizability of Qπe through convex-hull importance-weight classes.With tabular Q and state-action indicators, its sample estimator coincides with the model-based solution.
  • Theory: Squared Bellman error corresponds to an overly rich discriminator class whose sample complexity can be unaffordable in large state spaces.The paper frames discriminator choice as a statistical-efficiency consideration.
  • Connections: An RKHS discriminator class gives MQL a closed-form inner maximization expressed through kernel-weighted Bellman-error products.The paper also relates this formulation to prior value-based RL methods, while emphasizing MQL’s off-policy OPE setting.
  • Connections: Using the same linear class for Q-functions and importance weights makes MQL recover LSTDQ, while the corresponding OPE estimator matches MWL’s linear-class estimator.Related transformations also connect these methods to off-policy LSTD variants.

6. Doubly Robust Extension and Sample Complexity of MWL & MQL

The paper combines MWL and MQL through a doubly robust estimator, avoiding the need to choose between them. Its guarantees unify the estimators and provide sample-complexity results, including extensions to β-mixing data.

  • Doubly robust extension: MWL and MQL can be combined through a doubly robust estimator instead of choosing one approach.The combined population estimator is introduced as a natural application of the doubly robust trick.
  • Doubly robust extension: The combined estimator equals the target policy value when either the importance-weight model or the Q-function model is correct.This is the usual doubly robust property: one well-specified model can suffice.
  • Unified analysis: The unified estimator contains MWL and MQL as special cases obtained by setting q or w to the constant zero function.This framework is used to generalize their earlier theoretical results.
  • Unified analysis: Its estimation error admits a product form involving importance-weight error and Q-function or value-function error.The population deviation is expressed under the behavior-policy state-action distribution.
  • Sample complexity: Setting q′ = 0 or w′ = 0 recovers the corresponding MWL or MQL theorem, yielding their sample-complexity guarantees as corollaries.The general guarantee is stated for empirical losses and Rademacher-complexity terms.
  • Sample complexity: Similar guarantees extend to non-i.i.d. data under β-mixing assumptions.The extension is given in Appendix C.1.

7. Statistical Efficiency in the Tabular Setting

In the tabular setting, MWL and MQL achieve asymptotic efficiency at the semiparametric lower bound for off-policy evaluation. This optimality is asymptotic, while alternative explicit importance weighting may help with limited data.

  • Statistical efficiency: MWL and MQL achieve the semiparametric lower bound of off-policy evaluation in the tabular setting.Their state-action function models attain efficiency that state-function variants MSWL and MVL do not.
  • Statistical efficiency: √n(Rw,n[ ˆwn] − Rπe) and √n(Rq[ˆqn] − Rπe) weakly converge to normal distributions under geometric ergodicity.The theorem applies to the tabular setting and assumes the whole data set is geometrically ergodic.
  • Statistical efficiency: The asymptotic variance of the proposed estimators matches the semiparametric lower bound for OPE.MSWL and MVL instead have asymptotic variance greater than this lower bound.
  • Empirical and scope considerations: MWL significantly outperforms MSWL in Taxi experiments in the tabular setting.The authors qualify their optimality claim as asymptotic and leave limited-data regularization effects for future work.

8. Experiments

The experiments evaluate MWL and MQL against MSWL and DualDICE in CartPole with function approximation, using neural-network approximators and kernel discriminators. Figure 1 reports accuracy as log MSE of relative errors across sample sizes.

  • Experimental setup: MWL and MQL are compared with MSWL and DualDICE in CartPole with function approximation.The methods use neural networks with two hidden layers for main function classes, while discriminator classes use an RBF kernel except for DualDICE.
  • Experimental setup: The experiments use neural networks with 2 hidden layers as function approximators for the main function classes.An RBF kernel is used for discriminator classes except for DualDICE.
  • Results: Figure 1 shows the log MSE of relative errors as the sample size varies, with MQL appearing in the comparison.The cited passage introduces the figure-based comparison but does not state the complete empirical ranking.

9. Discussions

The discussion examines how discriminator-class choice affects learned importance weights and highlights a symmetry between MWL and MQL. It also frames the methods within broader algorithmic connections and notes an unresolved sequential decision-making trade-off.

  • Dependence on discriminator class: The feasible MWL weighting functions depend strongly on the discriminator class F and may not be unique.Special discriminator choices can yield simple weighting functions, including constants, that still produce accurate estimates with low variance.
  • Algorithmic connections: A sufficiently rich history-dependent discriminator class makes step-wise importance sampling a special case of MWL.In a history-based MDP, the marginal density ratio corresponds essentially to the cumulative importance-weight product used by step-wise IS.
  • Open questions: Choosing simple weighting functions creates a bias-variance trade-off whose extension from contextual bandits to sequential decision-making is not obvious.The discussion connects this trade-off to prior understanding in contextual bandits while marking sequential decision-making as unresolved.
  • Duality between MWL and MQL: MWL and MQL exhibit a symmetry in both their estimation procedures and guarantees, resembling value-function/distribution duality in MDP linear programming.The paper identifies formalizing this intuition as an interesting direction.

A. Proofs and Additional Results of Section 4 (MWL)

The MWL proofs establish identification, error control, and connections to Q-learning formulations under suitable function-class assumptions. They also show equivalences with MQL, LSTD-style estimators, and direct state-action ratio estimation.

  • Identification: MWL’s population loss vanishes at the true marginalized importance ratio under the stated identification conditions.The ratio is uniquely characterized when behavior state-action coverage and the lemma’s converse condition hold.
  • Error bounds: MWL’s OPE error is bounded by the largest population loss over the discriminator class, with approximation error added when Qπe is not exactly represented.The additional approximation term disappears when Qπe belongs to conv(F).
  • Identification: An RKHS discriminator with an ISPD kernel preserves uniqueness, so the MWL minimizer equals wπe/πb when the ratio class is realizable.The same conclusion holds for the full L2 discriminator class.
  • Connections: When all function approximators use the same linear class, MWL and MQL recover LSTDQ and off-policy LSTD variants, although their empirical objectives can differ.The state-action formulation also directly estimates the ratio, whereas a related state-based approach requires additional estimation steps.
  • MQL: If Qπe is represented in the chosen class and behavior coverage holds, MQL recovers Qπe and its induced return equals Rπe.A constant candidate can also yield the correct return under the sufficient condition described in the proofs.

C.1. Relaxing the i.i.d. data assumption

The appendix extends the analysis beyond i.i.d. samples to dependent trajectories under ergodicity and β-mixing assumptions. It also establishes tabular efficiency results and documents the inefficiency of related state-function estimators.

  • Relaxing the i.i.d. assumption: MWL’s sample-complexity analysis extends from i.i.d. data to a single long behavior-policy trajectory when the induced Markov chain is ergodic and mixes suitably.The trajectory is converted into transition tuples before applying the estimator.
  • Relaxing the i.i.d. assumption: Under stationary β-mixing data, a subsampling argument yields a high-probability bound involving empirical Rademacher complexity and the mixing coefficient.The confidence condition depends on the selected subsample sizes and β(a2).
  • Statistical efficiency: In the tabular setting, MWL and MQL are asymptotically normal with variance matching the semiparametric lower bound for OPE.The result assumes geometric ergodicity of the full data process.
  • Scope: Extending the tabular optimality theorem to continuous spaces is left for future work and would require growing basis dimensions and smoothness conditions.The paper describes the extension as possible but says its proof is not obvious.
  • Statistical inefficiency: MSWL and MVL correspond to off-policy LSTD variants, but their tabular asymptotic variances are larger than the semiparametric lower bound.The comparison identifies these estimators as statistically inefficient in the stated setting.

D.3. Experiments

The experiments evaluate MWL and MQL against MSWL and DualDICE in Taxi and CartPole settings. The reported results support the theoretical efficiency advantage of MWL over MSWL in the tabular experiment.

  • Taxi experiment: The Taxi comparison includes MSWL with exact πe, plug-in MSWL with estimated πe, and MWL, with MWL equal to MQL in this setting.The behavior policy mixes the target policy with a second policy, using α values 0.2 and 0.4.
  • Taxi experiment: In Taxi, MWL is significantly better than MSWL and slightly better than plug-in MSWL across the reported settings.The comparison uses tabular representations, a single trajectory, varying truncation sizes, and 200 replications per case.
  • CartPole experiment: The CartPole study compares MWL, MQL, MSWL, and DualDICE using neural-network function approximators and a state-action-dependent noisy transition model.CartPole uses an infinite-horizon discounted setting with γ = 0.999.
  • CartPole experiment: CartPole policies use τ = 1.0 for behavior and τ ∈ {0.25, 0.5, 1.5, 2.0} for target policies, with trajectories collected for 1000 steps.Terminal states are padded by repeating the last state and continuing action sampling.
  • Evaluation metric: The reported CartPole metric is normalized MSE over 25 trials, with returns estimated from 500 on-policy Monte Carlo trajectories.The normalization makes a behavior-return baseline equal to 0 after logarithmic transformation.

E.4. Error bars

The appendix defines the plotted error bars and illustrates how discriminator choice changes the MWL estimator. A sufficiently rich history-dependent discriminator recovers step-wise importance sampling rather than the marginalized state-action ratio.

  • Error bars: The plotted normalized MSE averages trial-level variables, with twice the standard error shown as a 95% confidence interval under logarithmic transformation.The interval bounds use the sample standard deviation of the trial-level quantity.
  • Error bars: Figure 3 compares MQL, MWL, DualDICE, and MSWL, varying target policies on the left and sample size on the right.The left panel fixes 200 trajectories, while the right fixes τ = 1.5.
  • Discriminator choice: With an overly rich history-dependent discriminator, MWL reduces to the step-wise IS estimator in discounted episodic problems.Under the stated nonzero-history-density assumption, the true marginalized state-action ratio is not feasible in that discriminator class.
Loading 1910.12809v4…