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

Introduction

In reinforcement learning (RL), off-policy evaluation (OPE) refers to the problem of estimating the performance of a new policy using historical data collected from a different policy, which is of crucial importance to the real-world applications of RL. The problem is genuinely hard as any unbiased estimator has to suffer a variance exponential in horizon in the worst case (Li et al., 2015; Jiang and Li, 2016), known as the curse of horizon.

Recently, a new family of estimators based on marginalized importance sampling (MIS) receive significant attention from the community (Liu et al., 2018; Xie et al., 2019), as they overcome the curse of horizon with relatively mild representation assumptions. The basic idea is to learn the marginalized importance weight that converts the state distribution in the data to that induced by the target policy, which sometimes has much smaller variance than the importance weight on action sequences used by standard sequential IS. Among these works, Liu et al. (2018) learn the importance weights by solving a minimax optimization problem defined with the help of a discriminator value-function class.

In this work, we investigate more deeply the space of algorithms that utilize a value-function class and an importance weight class for OPE. Our main contributions are:

(Section 4) 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).

(Section 5) By swapping the roles of importance weights and Q-functions in MWL, we obtain a new estimator that learns a Q-function using importance weights as discriminators. The procedure and the guarantees of MQL exhibit an interesting symmetry w.r.t. MWL. We also combine MWL and MQL in a doubly robust manner and provide their sample complexity guarantees (Section 6).

(Section 7) We examine the statistical efficiency of MWL and MQL, and show that by modeling state-action functions, MWL and MQL are able to achieve the semiparametric lower bound of OPE in the tabular setting while their state-function variants fail to do so.

Our work provides a unified view of many old and new algorithms in RL. For example, when both importance weights and value functions are modeled using the same linear class, we recover LSTDQ (Lagoudakis and Parr, 2004) and off-policy LSTD (Bertsekas and Yu, 2009; Dann et al., 2014) as special cases of MWL/MQL and their state-function variants. This gives LSTD algorithms a novel interpretation that is very different from the standard TD intuition. As another example, (tabular) model-based OPE and step-wise importance sampling—two algorithms that are so different that we seldom connect them to each other—are both special cases of MWL.

Preliminaries

An infinite-horizon discounted MDP is often specified by a tuple $(\mathcal{S},\mathcal{A},P,\mathcal{R},\gamma)$ where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ is the transition function, $\mathcal{R}:\mathcal{S}\times\mathcal{A}\to\Delta([0,R_{\max}])$ is the reward function, and $\gamma\in[0,1)$ is the discount factor. We also use $\mathcal{X}:=\mathcal{S}\times\mathcal{A}$ to denote the space of state-action pairs. Given an MDP, a (stochastic) policy $\pi:\mathcal{S}\to\Delta(\mathcal{A})$ and a starting state distribution $d_{0}\in\Delta(\mathcal{S})$ together determine a distribution over trajectories of the form $s_{0},a_{0},r_{0},s_{1},a_{1},r_{1},\ldots$, where $s_{0}\sim d_{0}$, $a_{t}\sim\pi(s_{t})$, $r_{t}\sim\mathcal{R}(s_{t},a_{t})$, and $s_{t+1}\sim P(s_{t},a_{t})$ for $t\geq 0$. The ultimate measure of the a policy’s performance is the (normalized) expected discounted return:

A concept central to this paper is the notion of (normalized) discounted occupancy:

where $d_{\pi,t}\in\Delta(\mathcal{X})$ is the distribution of $(s_{t},a_{t})$ under policy $\pi$. (The dependence on $d_{0}$ is made implicit.) We will sometimes also write $s\sim d_{\pi,\gamma}$ for sampling from its marginal distribution over states. An important property of discounted occupancy, which we will make heavy use of, is

It will be useful to define the policy-specific Q-function:

We are concerned with estimating the expected discounted return of an evaluation policy $\pi_{e}$ under a given initial distribution $d_{0}$, using data collected from a different behavior policy $\pi_{b}$. For our methods, we will consider the following data generation protocol, where we have a dataset consisting of $n$ i.i.d. tuples $(s,a,r,s^{\prime})$ generated according to the distribution:

On the i.i.d. assumption

Although we assume i.i.d. data for concreteness and the ease of exposition, the actual requirement on the data is much milder: our method works as long as the empirical expectation (over $n$ data points) concentrates around the exact expectation w.r.t. $(s,a,r,s^{\prime})\sim d_{\pi_{b}}$ for some $d_{\pi_{b}}$.We assume $a\sim\pi_{b}(s)$ throughout the paper since this is required by previous methods which we would like to compare to. However, most of our derivations do not require that the data is generated from a single behavior policy (which is a common characteristic of behavior-agnostic OPE methods). This holds, for example, when the Markov chain induced by $\pi_{b}$ is ergodic, and our data is a single long trajectory generated by $\pi_{b}$ without resetting. As long as the induced chain mixes nicely, it is well known that the empirical expectation over the single trajectory will concentrate, and in this case $d_{\pi_{b}}(s)$ corresponds to the stationary distribution of the Markov chain.We consider precisely this setting in Appendix C.1 to solidify the claim that we do not really need i.i.d.ness.

Overview of OPE Methods

A straightforward approach to OPE is to estimate an MDP model from data, and then compute the quantity of interest from the estimated model. An alternative but closely related approach is to fit $Q^{\pi_{e}}$ directly from data using standard approximate dynamic programming (ADP) techniques, e.g., the policy evaluation analog of Fitted Q-Iteration (Ernst et al., 2005; Le et al., 2019). While these methods overcome the curse of dimensionality and are agnostic to the knowledge of $\pi_{b}$, they often require very strong representation assumptions to succeed: for example, in the case of fitting a Q-value function from data, not only one needs to assume realizability, that the Q-function class (approximately) captures $Q^{\pi_{e}}$, but the class also needs to be closed under Bellman update $B^{\pi_{e}}$ (Antos et al., 2008), otherwise ADP can diverge in discounted problems (Tsitsiklis and Van Roy, 1997) or suffer exponential sample complexity in finite-horizon problems (Dann et al., 2018, Theorem 45); we refer the readers to Chen and Jiang (2019) for further discussions on this condition. When the function approximator fails to satisfy these strong assumptions, the estimator can potentially incur a high bias.

Importance Sampling (IS)

IS forms an unbiased estimate of the expected return by collecting full-trajectory behavioral data and reweighting each trajectory according to its likelihood under $\pi_{e}$ over $\pi_{b}$ (Precup et al., 2000). Such a ratio can be computed as the cumulative product of the importance weight over action ($\frac{\pi_{e}(a|s)}{\pi_{b}(a|s)}$) for each time step, which is the cause of high variance in IS: even if $\pi_{e}$ and $\pi_{b}$ only has constant divergence per step, the divergence will be amplified over the horizon, causing the cumulative importance weight to have exponential variance, thus the “curse of horizon”. Although techniques that combine IS and direct methods can partially reduce the variance, the exponential variance of IS simply cannot be improved when the MDP has significant stochasticity (Jiang and Li, 2016).

Marginalized Importance Sampling (MIS)

MIS improves over IS by observing that, if $\pi_{b}$ and $\pi_{e}$ induces marginal distributions over states that have substantial overlap—which is often the case in many practical scenarios—then reweighting the reward $r$ in each data point $(s,a,r,s^{\prime})$ with the following ratio

can potentially have much lower variance than reweighting the entire trajectory (Liu et al., 2018). The difference between IS and MIS is essentially performing importance sampling using Eq.(1) vs. Eq.(2). However, the weight $w^{\mathcal{S}}_{\pi_{e}/\pi_{b}}$ is not directly available and has to be estimated from data. Liu et al. (2018) proposes an estimation procedure that requires two function approximators, one for modeling the weighting function $w^{\mathcal{S}}_{\pi_{e}/\pi_{b}}(s)$, and the other for modeling $V^{\pi_{b}}$ which is used as a discriminator class for distribution learning. Compared to the direct methods, MIS only requires standard realizability conditions for the two function classes, though it also needs the knowledge of $\pi_{b}$. A related method for finite horizon problems has been developed by Xie et al. (2019).

Minimax Weight Learning (MWL)

In this section we propose a simple extension to Liu et al. (2018) that is agnostic to the knowledge of $\pi_{b}$. The estimator in the prior work uses a discriminator class that contains $V^{\pi_{e}}$ to learn the marginalized importance weight on state distributions (see Eq.(3)). We show that as long as the discriminator class is slightly more powerful—in particular, it is a Q-function class that realizes $Q^{\pi_{e}}$—then we are able to learn the importance weight over state-action pairs directly:

Before giving the estimator and its theoretical properties, we start with two assumptions that we will use throughout the paper, most notably that the state-action distribution in data well covers the discounted occupancy induced by $\pi_{b}$.

Assume $\mathcal{X}=\mathcal{S}\times\mathcal{A}$ is a compact space. Let $\nu$ be its Lebesgue measure. When $\nu$ is the counting measure for finite $\mathcal{X}$, all the results hold with minor modifications.

There exists $C_{w}<+\infty$ such that $w_{\pi_{e}/\pi_{b}}(s,a)\leq C_{w}$ $\forall(s,a)\in\mathcal{X}$.

In the rest of this section, we derive the new estimator and provide its theoretical guarantee. Our derivation (Eqs.(5)–(7)) provides the high-level intuitions for the method while only invoking basic and familiar concepts in MDPs (essentially, just Bellman equations). The estimator of Liu et al. (2018) can be also derived in a similar manner.

To recap, it suffices to find any $w$ that satisfies the above equation. Since we do not know $Q^{\pi_{e}}$, we will use a function class $\mathcal{F}$ that (hopefully) captures $Q^{\pi_{e}}$, and find $w$ that minimizes (the absolute value of) the following objective function that measures the violation of Eq.(4) over all $f\in\mathcal{F}$:

When the behavior policy $\pi_{b}$ is known, we can incorporate this knowledge by setting $\mathcal{W}=\{s\mapsto w(s)\frac{\pi_{e}(a|s)}{\pi_{b}(a|s)}:w\in\mathcal{W}^{\mathcal{S}}\}$, where $\mathcal{W}^{\mathcal{S}}$ is some function class over the state space. The resulting estimator is still different from (Liu et al., 2018) since our discriminator class is still over the state-action space.

1 Case Studies

The estimator in Eq.(4) requires solving a minimax optimization problem, which can be computationally challenging. Following Liu et al. (2018) we show that the inner maximization has a closed form solution when we choose $\mathcal{F}$ to correspond to a reproducing kernel Hilbert space (RKHS) $\mathcal{H}_{K}$ be a RKHS associated with kernel $K(\cdot,\cdot)$. We include an informal statement below and defer the detailed expression to Appendix A.2 due to space limit.

Just as our method corresponds to LSTDQ in the linear setting, it is worth pointing out that the method of Liu et al. (2018)—which we will call MSWL (minimax state weight learning) for distinction and easy reference—corresponds to off-policy LSTD (Bertsekas and Yu, 2009; Dann et al., 2014); see Appendix A.5 for details.

2 Connections to related work

In the special case of $\gamma=0$, i.e., when the problem is a contextual bandit, our method essentially becomes kernel mean matching when using an RKHS discriminator (Gretton et al., 2012), so MWL can be viewed as a natural extension of kernel mean matching in MDPs.

Minimax Q-Function Learning (MQL)

In Section 4, we show how to use value-function class as discriminators to learn the importance weight function. In this section, by swapping the roles of $w$ and $f$, we derive a new estimator that learns $Q^{\pi_{e}}$ from data using importance weights as discriminators. The resulting objective function has an intuitive interpretation of average Bellman errors, which has many nice properties and interesting connections to prior works in other areas of RL.

Loss Function

Similar to the situation of MWL, we can use a rich function class $\mathcal{G}$ to model $w_{\pi_{e}/\pi_{b}}$, and find $q$ that minimizes the RHS of the above equation for all $g\in\mathcal{G}$, which gives rise to the following estimator:

Similar to the case of MWL, we show that under certain representation conditions, the estimator will provide accurate estimation to $R_{\pi_{e}}$.

1 Case Studies

In the next example, we choose $\mathcal{G}$ to be a rich $L^{2}$-class with bounded norm, and recover the usual (squared) Bellman error as a special case. A similar example has been given by Feng et al. (2019).

Note that the standard Bellman error cannot be directly estimated from data when the state space is large, even if the $\mathcal{Q}$ class is realizable (Szepesvari and Munos, 2005; Sutton and Barto, 2018; Chen and Jiang, 2019). From our perspective, this difficulty can be explained by the fact that squared Bellman error corresponds to an overly rich discriminator class that demands an unaffordable sample complexity.

The next example is RKHS class which yields a closed-form solution to the inner maximization as usual.

When $\mathcal{G}=\{g(s,a);\langle g,g\rangle_{\mathcal{H}_{K}}\leq 1\}$, we have the following:

2 Connection to Kernel Loss (Feng et al., 2019)

where $\mathcal{G}^{\mathcal{S}}$ is an RKHS over the state space. While their method is very similar to MQL when written as the above expression, they focus on learning a state-value function and need to be on-policy for policy evaluation. In contrast, our goal is OPE (i.e., estimating the expected return instead of the value function), and we learn a Q-function as an intermediate object and hence are able to learn from off-policy data. More importantly, the importance weight interpretation of $g$ has eluded their paper and they interpret this loss purely from a kernel perspective. In contrast, by leveraging the importance weight interpretation, we are able to establish approximation error bounds based on representation assumptions that are fully expressed in quantities directly defined in the MDP. We also note that their loss for policy optimization can be similarly interpreted as minimizing average Bellman errors under a set of distributions.

Furthermore, it is easy to extend their estimator to the OPE task using knowledge of $\pi_{b}$, which we call MVL; see Appendix B.2 for details. Again, just as we discussed in Appendix A.5 on MSWL, when we use linear classes for both value functions and importance weights, these two estimators become two variants of off-policy LSTD (Dann et al., 2014; Bertsekas and Yu, 2009) and coincide with MSWL and its variant.

Doubly Robust Extension and Sample Complexity of MWL & MQL

In the previous sections we have seen two different ways of using a value-function class and an importance-weight class for OPE. Which one should we choose?

In this section we show that there is no need to make a choice. In fact, we can combine the two estimates naturally through the doubly robust trick (Kallus and Uehara, 2019b) (see also (Tang et al., 2020)), whose population version is:

As before, we write $R_{n}[w,q]$ as the empirical analogue of $R[w,q]$. While $w$ and $q$ are supposed to be the MWL and MQL estimators in practice, in this section we will sometimes treat $w$ and $q$ as arbitrary functions from the $\mathcal{W}$ and $\mathcal{Q}$ classes to keep our results general. By combining the two estimators, we obtain the usual doubly robust property, that when either $w=w_{\pi_{e}/\pi_{b}}$ or $q=Q^{\pi_{e}}$, we have $R[w,q]=R_{\pi_{e}}$, that is, as long as either one of the models works well, the final estimator behaves well.See Kallus and Uehara (2019b, Theorem 11,12) for formal statements.

When $q^{\prime}=\mathbf{0}$, the first statement is reduced to Theorem 2. When $w^{\prime}=\mathbf{0}$, the second statement is reduced to Theorem 5.

where $\mathfrak{R}_{n}(\mathcal{W},\mathcal{F})$ is the Rademacher complexity See Bartlett and Mendelson (2003) for the definition. of the function class $\{(s,a,s^{\prime})\mapsto w(s,a)(\gamma f(s^{\prime},\pi_{e})-f(s,a))~{}:~{}~{}w\in\mathcal{W},f\in\mathcal{F}\}.$

where $\mathfrak{R}_{n}(\mathcal{Q},\mathcal{G})$ is the Rademacher complexity of the function class $\{(s,a,r,s^{\prime})\mapsto g(s,a)\{r+\gamma q(s^{\prime},\pi_{e})-q(s,a)\}~{}:~{}~{}q\in\mathcal{Q},g\in\mathcal{G}\}.$

Statistical Efficiency in the Tabular Setting

As we have discussed earlier, both MWL and MQL are equivalent to LSTDQ when we use the same linear class for all function approximators. Here we show that in the tabular setting, which is a special case of the linear setting, MWL and MQL can achieve the semiparametric lower bound of OPE (Kallus and Uehara, 2019a), because they coincide with the model-based solution. This is a desired property that many OPE estimators fail to obtain, including MSWL and MVL.

This variance matches the semiparametric lower bound for OPE given by Kallus and Uehara (2019a, Theorem 5).

The details of this theorem and further discussions can be found in Appendix D, where we also show that MSWL and MVL have an asymptotic variance greater than this lower bound. To back up this theoretical finding, we also conduct experiments in the Taxi environment (Dietterich, 2000) following Liu et al. (2018, Section 5), and show that MWL performs significantly better than MSWL in the tabular setting; see Appendix D.3 for details. It should be noted, however, that our optimal claim is asymptotic, whereas explicit importance weighting of MSWL and MVL may provide strong regularization effects and hence preferred in the regime of insufficient data; we leave the investigation to future work.

Experiments

We empirically demonstrate the effectiveness of our methods and compare them to baseline algorithms in CartPole with function approximation. We compare MWL & MQL to MSWL (Liu et al., 2018, with estimated behavior policy) and DualDICE (Nachum et al., 2019a). We use neural networks with 2 hidden layers as function approximators for the main function classes for all methods, and use an RBF kernel for the discriminator classes (except for DualDICE); due to space limit we defer the detailed settings to Appendix E. Figure 1 shows the log MSE of relative errors of different methods, where MQL appears to the best among all methods. Despite that these methods require different function approximation capabilities and it is difficult to compare them apple-to-apple, the results still show that MWL/MQL can achieve similar performance to related algorithms and sometimes outperform them significantly.

Discussions

We conclude the paper with further discussions.

Every episodic MDP can be viewed as an equivalent MDP whose state is the history of the original MDP. The marginal density ratio in this history-based MDP is essentially the cumulative product of importance weight used in step-wise IS, and from Lemma 11 we know that such a function is the unique minimizer of MWL’s population loss if $\mathcal{F}$ is chosen to be a sufficiently rich class of functions over histories. See Appendix F for more details on this example.

Duality between MWL and MQL From Sections 4 and 5, one can observe an obvious symmetry between MWL and MQL from the estimation procedures to the guarantees, which reminds us a lot about the duality between value functions and distributions in linear programming for MDPs. Formalizing this intuition is an interesting direction.See the parallel work by Nachum et al. (2019) and the follow-up work of Jiang and Huang (2020) for some intriguing discussions on this matter.

Acknowledgements

We would like to thank the anonymous reviewers for their insightful comments and suggestions.

Masatoshi Uehara was supported in part by MASASON Foundation.

References

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

We first give the formal version of Lemma 1, which is Lemmas 11 and 12 below, and then provide their proofs.

For any function $g(s,a)$, define the map; $g\to\delta(g,s^{\prime},a^{\prime})$;

Then, $\delta(d_{\pi_{e},\gamma},s^{\prime},a^{\prime})=0\,\forall(s^{\prime},a^{\prime})$.

This concludes $\delta(d_{\pi_{e},\gamma},s^{\prime},a^{\prime})=0\,\forall(s^{\prime},a^{\prime})$. ∎

Here, we denote $\beta_{\pi_{e}/\pi_{b}}(s,a)=\pi_{e}(a|s)/\pi_{b}(a|s)$. Then, we have

Here, we have used Lemma 11: $\delta(d_{\pi_{e},\gamma},s^{\prime},a^{\prime})=0\,\forall(s^{\prime},a^{\prime})$.

Here, the expectation is taken with respect to the density $P(s_{1}|s_{0},a_{0})\pi_{e}(a_{1}|s_{1})P(s_{2}|s_{1},a_{1})\cdots$. Then, $f=f_{g}$ is a solution to $g=\prod f$.

In the first line, we have used Lemma 13. From the first line to the second line, we have used Lemma 14.

Finally, from the definition of $\hat{w}$,

For completeness we include the proof below:

For any $w$ and for any $q^{\dagger}\in\mathcal{F}$,

Here, from (15) to (16), we have used a reproducing property of RKHS; $f(s,a)=\langle f(\cdot),K((s,a),\cdot)\rangle$. From (16) to (17), we have used a linear property of the inner product.

from Cauchy–-Schwarz inequality. This is equal to

Other term are derived in a similar manner. Here, we have used a kernel property

The first statement is obvious from Lemma 12 and the proof is omitted, and here we prove the second statement on the ISPD kernel case. If we can prove Lemma 12 when replacing $L^{2}(\mathcal{X},\nu)$ with RKHS associated with an ISPD kernel $K(\cdot,\cdot)$, the statement is concluded. More specifically, what we have to prove is

This is proved by Mercer’s theorem (Mohri et al., 2012). From Mercer’s theorem, there exist an orthnormal basis $(\phi_{j})_{j=1}^{\infty}$ of $L^{2}(\mathcal{X},\nu)$ such that RKHS is represented as

Suppose $w_{0}(s,a)=C~{}\forall(s,a)$. Then, for $f=Q^{\pi_{e}}$ we have

A.2 The RKHS Result

A.3 Details of Example 2 (LSTDQ)

Here we provide the detailed derivation of Eq.(2), that is, the closed-form solution of MWL when both $\mathcal{W}$ and $\mathcal{F}$ are set to the same linear class. We assume that the matrix being inverted in Eq.(2) is non-singular.

Consider $w\in\mathcal{W}$ whose parameter is $\alpha$ and $f\in\mathcal{F}$ whose parameter is $\beta$. Then

Note that this is just a set of linear equations where the number of unknowns is the same as the number of equations, and the $\hat{\alpha}$ in Eq.(2) is precisely the solution to Eq.(18) when the matrix multiplied by $\alpha^{\top}$ is non-singular.

A.4 Connection to Dual DICE (Nachum et al., 2019a)

Nachum et al. (2019a) proposes an extension of Liu et al. (2018) without the knowledge of the behavior policy, which shares the same goal with our MWL in Section 4. In fact, there is an interesting connection between our work and theirs, as our key lemma (12) can be obtained if we take the functional gradient of their loss function. (Ideal) DualDICE with the chi-squared divergence $f(x)=0.5x^{2}$ is described as follows;

Estimate the ratio as $\nu(s,a)-(\mathcal{B}\nu)(s,a)$.

Because this objective function includes an integral in $(\mathcal{B}\nu)(s,a)$, the Monte-Carlo approximation is required. However, even if we take an Monte-Carlo sample for the approximation, it is biased. Therefore, they further modify this objective function into a more complex minimax form. See (11) in (Nachum et al., 2019a).

Here, we take a functional derivative of (19)(Gateaux derivative) with respect to $\nu$. The functional derivative at $\nu(s,a)$ is

The first order condition exactly corresponds to our Lemma 12:

where $w(s,a)=\nu(s,a)-(\mathcal{B}\nu)(s,a)$. Our proposed method with RKHS enables us to directly estimate $w(s,a)$ in one step, and in contrast their approach requires two additional steps: estimating $(\mathcal{B}\nu)(s,a)$ in the loss function, estimating $\nu(s,a)$ by minimizing the loss function, and taking the difference $\nu(s,a)-(\mathcal{B}\nu)(s,a)$.

A.5 Connection between MSWL (Liu et al., 2018) and Off-policy LSTD

We call this method MSWL (minimax state weight learning) for easy reference. A slightly different but closely related estimator is

Although the two objectives are equal in expectation, under empirical approximations the two estimators are different. In fact, Eq.(21) corresponds to the most common form of off-policy LSTD (Bertsekas and Yu, 2009) when both $\mathcal{W}^{\mathcal{S}}$ and $\mathcal{F}^{\mathcal{S}}$ are linear (similar to Example 2). In the same linear setting, Eq.(20) corresponds to another type of off-policy LSTD discussed by Dann et al. (2014). In the tabular setting, we show that cannot achieve the semiparametric lower bound in Appendix D.

Appendix B Proofs and Additional Results of Section 5 (MQL)

Then, $\forall g\in L^{2}(\mathcal{X},\nu)$,

We prove the uniqueness part. Recall that $Q^{\pi_{e}}$ is uniquely characterized as (Bertsekas, 2012): $\forall(s,a)$,

Note that the left hand side term is seen as

We prove the first statement. For fixed any $q$, we have

Then, the second statement follows immediately based on the definition of $\hat{q}$. ∎

The proof is omitted due to similarity to the MWL case.

From the first line to the second line, we use a reproducing property of RKHS; $g(s,a)=\langle g(\cdot),K((s,a),\cdot\rangle_{\mathcal{H}_{K}}$. From the second line to the third line, we use a linear property of the inner product. From third line to the fourth line, we use a Cauchy–schwarz inequality since $\mathcal{G}=\{g;\langle g,g\rangle_{\mathcal{H}_{K}}\leq 1\}$.

Then, the last expression $\langle g^{*},g^{*}\rangle_{\mathcal{H}_{K}}$ is equal to

Assume $Q^{\pi_{e}}$ is included in $\mathcal{Q}$ and $d_{\pi_{b}}(s,a)>0\,\forall(s,a)$. Then, if $\mathcal{G}$ is $L^{2}(\mathcal{X},\nu)$, $\hat{q}=Q^{\pi_{e}}$. Also if $\mathcal{G}$ is a RKHS associated with an ISPD kernel, $\hat{q}=Q^{\pi_{e}}$

The first statement is obvious from Lemma 4. The second statement is proved similarly as Theorem 15. ∎

Suppose $q_{0}(s,a)=C$. Then, for $g=w_{\pi_{e}/\pi_{b}}$, we have

B.2 Minimax Value Learning (MVL)

Again, similar to the situation of MSWL as we discussed in Appendix A.5, these two losses are equal in expectation but exhibit different finite sample behaviors. When we use linear classes for both value functions and importance weights, these two estimators become two variants of off-policy LSTD (Dann et al., 2014; Bertsekas and Yu, 2009) and coincide with MSWL and its variant.

Appendix C Proofs and Additional Results of Section 6 (DR and Sample Complexity)

From (28) to (29), this is just by algebra following the definition of $R[\cdot,\cdot]$. From (29) to (30), we use the following lemma. ∎

The first equation comes form Lemma 12 with $f(s,a)=q(s,a)-Q^{\pi}(s,a)$. The second equation comes from Lemma 4 with $g(s,a)=w(s,a)-w_{\pi_{e}/\pi_{b}}(s,a)$. ∎

We begin with the second statement, which is easier to prove from Lemma 7:

Next, we prove the first statement. From Lemma 7,

Finally, from the definition of $\hat{w}$ and $\hat{q}$, we also have

We prove the first statement. The second statement is proved in the same way. We have

where $\mathfrak{R}^{\prime}_{n}(\mathcal{F},\mathcal{W})$ is the Rademacher complexity of the function class

Here, we just used an uniform law of large number based on the Rademacher complexity noting $|\left(w(s,a)(\gamma f(s^{\prime},\pi_{e})-f(s,a))\right)|$ is uniformly bounded by $C_{f}C_{w}$ up to some constant (Bartlett and Mendelson, 2003, Theorem 8). From the contraction property of the Rademacher complexity (Bartlett and Mendelson, 2003, Theorem 12),

where $\mathfrak{R}_{n}(\mathcal{F},\mathcal{W})$ is the Rademacher complexity of the function class

Finally, Combining (31), (32) and (C), the proof is concluded. ∎

Although the sample complexity results in Section 6 are established under i.i.d. data, we show that under standard assumptions we can also handle dependent data and obtain almost the same results. For simplicity, we only include the result for $\hat{w}_{n}$.

In particular, we consider the setting mentioned in Section 2, that our data is a single long trajectory generated by policy $\pi_{b}$:

We assume that the Markov chain induced by $\pi_{b}$ is ergodic, and $s_{0}$ is sampled from its stationary distribution so that the chain is stationary. In this case, $d_{\pi_{b}}$ corresponds to such a stationary distribution, which is also the marginal distribution of any $s_{t}$. We convert this trajectory into a set of transition tuples $\{(s_{i},a_{i},r_{i},s_{i}^{\prime})\}_{i=0}^{n-1}$ with $n=T$ and $s_{i}^{\prime}=s_{i+1}$, and then apply our estimator on this data. Under the standard $\beta$-mixing conditionRefer to (Meyn and Tweedie, 2009) regarding the definition. (see e.g., Antos et al., 2008), we can prove a similar sample complexity result:

Assume $\{s_{i},a_{i},r_{i},s^{\prime}_{i}\}_{i=1}^{n}$ follows a stationary $\beta$–mixing distribution with $\beta$–mixing coefficient $\beta(k)$ for $k=0,1,\cdots$. For any $a_{1},a_{2}>0$ with $2a_{1}a_{2}=n$ and $\delta>4(a_{1}-1)\beta(a_{2})$, with probability at least $1-\delta$, we have (all other assumptions are the same as in Theorem 9(1))

where $\mathfrak{\hat{R}}_{a_{1}}(\mathcal{F},\mathcal{W})$ is the empirical Rademacher complexity of the function class $\{(s,a,s^{\prime})\mapsto\{w(s,a)(\gamma f(s^{\prime},\pi_{e})-f(s,a)):w\in\mathcal{W},f\in\mathcal{F}\}$ based on a selected subsample of size $a_{1}$ from the original data (see Mohri and Rostamizadeh (2009, Section 3.1) for details), and $\delta^{\prime}=\delta-4(a_{1}-1)\beta(a_{2})$.

Appendix D Statistical Efficiency in the Tabular Setting

As we already have seen in Example 7, when $\mathcal{W},\mathcal{F},\mathcal{Q},\mathcal{G}$ are the same linear class, MWL, MQL, and LSTDQ give the same OPE estimator. These methods are also equivalent in the tabular setting—as tabular is a special case of linear representation (with indicator features)—which also coincides with the model-based (or certainty-equivalent) solution. Below we prove that this tabular estimator can achieve the semiparametric lower bound for infinite horizon OPE (Kallus and Uehara, 2019a). Semiparametric lower bound is the non–parametric extension of Cramer–Rao lower bound (Bickel et al., 1998). It is the lower bound of asymptotic MSE among regular estimators (van der Vaart, 1998). Though there are many estimators for OPE, many of the existing OPE methods do not satisfy this property.

Here, we have the following theorem; the proof is deferred to Appendix D.4.

This variance matches the semiparametric lower bound for OPE given by Kallus and Uehara (2019a, Theorem 5).

Theorem 21 could be also extended to the continuous sample space case in a nonparametric manner, i.e., replacing $\phi(s,a)$ with some basis functions for $L^{2}$–space and assuming that its dimension grows with some rate related to $n$ and the data–generating process has some smoothness condition (Newey and Mcfadden, 1994). The proof is not obvious and we leave it to future work.

In the contextual bandit setting, it is widely known that the importance sampling estimator with plug-in weight from the empirical distribution and the model-based approach can achieve the semiparametric lower bound (Hahn, 1998; Hirano et al., 2003). Our findings are consistent with this fact and is novel in the MDP setting to the best of our knowledge.

D.2 Statistical inefficiency of MSWL and MVL for OPE

Here, we compare the statistical efficiency of MWL, MQL with MSWL, MVL in the tabular setting. First, we show that MSWL, MVL positing the linear class is the same as the off-policy LSTD (Bertsekas and Yu, 2009; Dann et al., 2014). Then, we calculate the asymptotic MSE of these estimators in the tabular case and show that this is larger than the ones of MWL and MQL.

By slightly modifying Liu et al. (2018, Theorem 4), MSWL is introduced based on the following relation;

Then, the estimator for $\frac{d_{\pi_{e}}(s)}{d_{\pi_{b}}(s)}$ is given as

Then, the final estimator for $R_{\pi_{e}}$ is

In MVL, the estimator for $V^{\pi_{e}}(s)$ is constructed based on the relation;

Then, the estimator for $V^{\pi_{e}}(s)$ is given by

Then, the final estimator for $R_{\pi_{e}}$ is still $(D_{v_{1}})^{\top}D^{-1}_{v_{2}}D_{v_{3}}$. This is exactly the same as the estimator obtained by off-policy LSTD (Bertsekas and Yu, 2009).

Another formulation of MSWL and MVL

According to Liu et al. (2018, Theorem 4), we have

They construct an estimator for $\frac{d_{\pi_{e},\gamma}(s)}{d_{\pi_{b}}(s)}$ as;

Note that compared with the previous case (34), the position of the importance weight $\pi_{e}/\pi_{b}$ is different. In the same way, MVL is constructed base on the relation;

The estimator for $V^{\pi_{e}}(s)$ is given by

When positing linear models, in both cases, the final estimator for $R_{\pi_{e}}$ is

This is exactly the same as the another type of off-policy LSTD (Dann et al., 2014).

Statistical inefficiency of MSWL, MVL and off-policy LSTD

Next, we calculate the asymptotic variance of $D_{v1}D^{-1}_{v2}D_{v3}$ and $D_{v1}D^{-1}_{v4}D_{v3}$ in the tabular setting. It is shown that these methods cannot achieve the semiparametric lower bound (Kallus and Uehara, 2019a). These results show that these methods are statistically inefficient. Note that this implication is also brought to the general continuous sample space case since the the asymptotic MSE is generally the same even in the continuous sample space case with some smoothness conditions.

Assume the whole data is geometrically Ergodic. In the tabular setting, $\sqrt{n}(D_{v1}D^{-1}_{v2}D_{v3}-R_{\pi_{e}})$ weakly converges to the normal distribution with mean and variance;

This is larger than the semiparametric lower bound.

Assume the whole data is geometrically Ergodic. In the tabular setting, $\sqrt{n}(D_{v1}D^{-1}_{v4}D_{v3}-R_{\pi_{e}})$ weakly converges to the normal distribution with mean and variance;

This is larger than the semiparametric lower bound.

D.3 Experiments

We show some empirical results that back up the theoretical discussions in this section. We conduct experiments in the Taxi environment (Dietterich, 2000), which has 20000 states and 6 actions; see Liu et al. (2018, Section 5) for more details. We compare three methods, all using the tabular representation: MSWL with exact $\pi_{e}$, MSWL with estimated $\pi_{e}$ (“plug-in”), and MWL (same as MQL). As we have mentioned earlier, this comparison is essentially among off-policy LSTD, plug-in off-policy LSTD, and LSTDQ.

We choose the target policy $\pi_{e}$ to be the one obtained after running Q-learning for 1000 iterations, and choose another policy $\pi_{+}$ after 150 iterations. The behavior policy is $\pi_{b}=\alpha\pi_{e}+(1-\alpha)\pi_{+}$. We report the results for $\alpha\in\{0.2,\,0.4\}$. The discount factor is $\gamma=0.98$.

We use a single trajectory and vary the truncation size $T$ as $\times 10^{4}$. For each case, by making $200$ replications, we report the Monte Carlo MSE of each estimator with their $95\%$ interval in Figure 2.

It is observed that MWL is significantly better than MSWL and MWL is slightly better than plug-in MSWL. This is because MWL is statisitcally efficient and MSWL is statistically inefficient as we have shown earlier in this section. The reason why plug-in MSWL is superior to the original MSWL is that the plug-in based on MLE with a well specified model can be viewed as a form of control variates (Henmi and Eguchi, 2004; Hanna et al., 2019). Whether the plug-in MSWL can achieve the semiparametric lower bound remains as future work.

D.4 Proofs of Theorems 21, 22, and 23

Recall that the estimator is written as $D^{\top}_{q1}D^{-1}_{q2}D_{q3}$, where

Recall that $D^{-1}_{q2}D_{q3}=\hat{\beta}$ is seen as Z–estimator with a parametric model $q(s,a;\beta)=\beta^{\top}\phi(s,a)$. More specifically, the estimator $\hat{\beta}$ is given as a solution to

Following the standard theory of Z–estimator (van der Vaart, 1998), the asymptotic MSE of $\beta$ is calculated as a sandwich estimator;

where $\beta^{\top}_{0}\phi(s,a)=Q^{\pi_{e}}(s,a)$ and

From now on, we simplify the expression $D^{\top}_{q1}D^{-1}_{1}D_{2}{D^{-1}_{1}}^{\top}D_{q1}$. First, we observe

where $[D_{q1}]_{|S|i_{1}+i_{2}}$ is a element corresponding $(S_{i_{1}},A_{i_{2}})$ of $D_{q1}$. In addition,

where $P^{\pi_{e}}$ is a transition matrix between $(s,a)$ and $(s^{\prime},a^{\prime})$, and $I$ is an identity matrix.

Recall that $D^{-1}_{v2}D_{v3}=\hat{\beta}$ is seen as Z–estimator with a parametric model $v(s;\beta)=\beta^{\top}\phi(s)$. More specifically, the estimator $\hat{\beta}$ is given as a solution to

Following the standard theory of Z–estimator (van der Vaart, 1998), the asymptotic variance of $\beta$ is calculated as a sandwich estimator;

where $\beta^{\top}_{0}\phi(s)=V^{\pi_{e}}(s)$ and

From now on, we simplify the expression $D^{\top}_{v1}S^{-1}_{1}S_{2}(S^{-1}_{1})^{\top}D_{v1}$. First, we observe

where $[D_{v1}]_{i}$ is $i$–th element. In addition,

where $P^{\pi_{e}}$ is a transition matrix from the current state to the next state.

Finally, we show this is larger than the semiparametric lower bound. This is seen as

Then, we show this is larger than the semiparamatric lower bound. This is seen as

Appendix E Experiments in the Function Approximation Setting

In this section, we empirically evaluate our new algorithms MWL and MQL, and make comparison with MSWL (Liu et al., 2018) and DualDICE (Nachum et al., 2019b) in the function approximation setting.

We consider infinite-horizon discounted setting with $\gamma=0.999$, and test all the algorithms on CartPole, a control task with continuous state space and discrete action space. Based on the implementation of OpenAI Gym (Brockman et al., 2016), we define a new state-action-dependent reward function and add small Gaussian noise with zero mean on the transition dynamics.

To obtain the behavior and the target policies, we first use the open source codehttps://github.com/openai/baselines of DQN to get a near-optimal $Q$ function, and then apply softmax on the $Q$ value divided by an adjustable temperature $\tau$:

We choose $\tau=1.0$ as the behavior policy and $\tau=0.25,0.5,1.5,2.0$ as the target policies. The training datasets are generated by collecting trajectories of the behavior policy with fixed horizon length 1000. If the agent visits the terminal states within 1000 steps, the trajectory will be completed by repeating the last state and continuing to sample actions.

E.2 Algorithms Implementation

We use the loss functions and the OPE estimators derived in this paper and previous literature (Liu et al., 2018; Nachum et al., 2019b), except for MWL, in which we find another equivalent loss function can work better in practice:

In all algorithms, we keep the structure of the neural networks the same, which have two hidden layers with 32 units in each and ReLU as activation function. Besides, the observation is normalized to zero mean and unit variance, and the batch size is fixed to 500. In MSWL, the normalized states are the only input, while in the others, the states and the actions are concatenated and fed together into neural networks.

As for DualDICE, we conduct evaluation based on the open source implementationhttps://github.com/google-research/google-research/tree/master/dual_dice. The learning rate of $\nu-$network and $\zeta-$network are changed to be $\eta_{\nu}=0.0005$ and $\eta_{\zeta}=0.005$, respectively, after a grid search in $\eta_{\nu}\times\eta_{\zeta}\in\{0.0001,0.0005,0.001,0.0015,0.002\}\times\{0.001,0.005,0.01,0.015,0.02\}$.

In MSWL, we use estimated policy distribution instead of the true value to compute the policy ratio. To do this, we train a 64x64 MLP with cross-entropy loss until convergence to approximate the distribution of the behavior policy. The learning rate is set to be 0.0005.

Besides, we implement MQL, MWL and MSWL with $\mathcal{F}$ corresponding to a RKHS associated with kernel $K(\cdot,\cdot)$. The new loss function of MWL (39) can be written as:

where $\mathbf{x}_{i},\mathbf{x}_{j}$ corresponds to state vectors in MSWL, and corresponds to the vectors concatenated by state and action in MWL and MQL. Denote $h$ as the median of the pairwise distance between $\mathbf{x}_{i}$, we set $\sigma$ equal to $h,\frac{h}{3}$ and $\frac{h}{15}$ in MSWL, MWL and MQL, respectively. The learning rates are fixed to 0.005 in these three methods.

In MSWL and MWL, to ensure that the predicted density ratio is non-negative, we apply $\log(1+\exp(\cdot))$ as the activation function in the last layer of the neural networks. Moreover, we normalize the ratio to have unit mean value in each batch, which works better.

E.3 Results

We generate $N$ datasets with different random seeds. For each dataset, we run all these four algorithms from the beginning until convergence, and consider it as one trial. Every 100 training iterations, the estimation of value function is logged, and the average over the last five logged estimations will be recorded as the result in this trial. For each algorithm, we report the normalized MSE, defined by

where $\hat{R}_{\pi_{e}}^{(i)}$ is the estimated return in the $i$-th trial; $R_{\pi_{e}}$ and $R_{\pi_{b}}$ are the true expected returns of the target and the behavior policies, respectively, estimated by 500 on-policy Monte-Carlo trajectories (truncated at $H=10000$ steps to make sure $\gamma^{H}$ is sufficiently small). This normalization is very informative, as a naïve baseline that treats $R_{\pi_{e}}\approx R_{\pi_{b}}$ will get $0.0$ (after taking logarithm), so any method that beats this simple baseline should get a negative score. We conduct $N=25$ trials and plot the results in Figure 3.

E.4 Error bars

We denote $x_{i}=\frac{(\hat{R}_{\pi_{e}}^{(i)}-R_{\pi_{e}})^{2}}{(R_{\pi_{b}}-R_{\pi_{e}})^{2}}$. As we can see, the result we plot (Eq.(42)) is just the average of $N$ i.i.d. random variables $\{x_{i}\}_{i=1}^{n}$. We plot twice the standard error of the estimation—which corresponds to $95\%$ confidence intervals—under logarithmic transformation. That is, the upper bound of the error bar is

where $\sigma$ is the sample standard deviation of $x_{i}$.

Appendix F Step-wise IS as a Special Case of MWL

We show that step-wise IS (Precup et al., 2000) in discounted episodic problems can be viewed as a special case of MWL, and sketch the proof as follows. In addition to the setup in Section 2, we also assume that the MDP always goes to the absorbing state in $H$ steps from any starting state drawn from $d_{0}$. The data are trajectories generated by $\pi_{b}$. We first convert the MDP into an equivalent history-based MDP, i.e., a new MDP where the state is the history of the original MDP (absorbing states are still treated specially). We use $h_{t}$ to denote a history of length $t$, i.e., $h_{t}=(s_{0},a_{0},r_{0},s_{1},\ldots,s_{t})$. Since the history-based MDP still fits our framework, we can apply MWL as-is to the history-based MDP. In this case, each data trajectory will be converted into $H$ tuples in the form of $(h_{t},a_{t},r_{t},h_{t+1})$.