Title: INFINITE-HORIZON OFF-POLICY POLICY EVALUATION WITH MULTIPLE BEHAVIOR POLICIES

Abstract: We consider off-policy policy evaluation when the trajectory data are generated by multiple behavior policies. Recent work has shown the key role played by the state or state-action stationary distribution corrections in the infinite horizon context for off-policy policy evaluation. We propose estimated mixture policy (EMP), a partially policy-agnostic methods to accurately estimate those quantities. With careful analysis, we show that EMP gives rise to estimates with reduced variance for estimating the state stationary distribution correction while it also offers a useful induction bias for estimating the state-action stationary distribution correction. In extensive experiments with both continuous and discrete environments, we demonstrate that our algorithm offers significantly improved accuracy compared to the state-of-the-art methods.

1. INTRODUCTION:

In many real-world decision-making scenarios, evaluating a novel policy by directly executing it in the environment is generally costly and can even be downright risky. Examples include evaluating a recommendation policy (Swaminathan et al., 2017; Zheng et al., 2018) , a treatment policy (Hirano et al., 2003; Murphy et al., 2001) , and a traffic light control policy ( Van der Pol & Oliehoek, 2016) . Off-policy policy evaluation methods (OPPE) utilize a set of previously-collected trajectories (for example, website interaction logs, patient trajectories, or robot trajectories) to estimate the value of a novel decision-making policy without interacting with the environment (Precup et al., 2001; Dudík et al., 2011) . For many reinforcement learning applications, the value of the decision is defined in a long-or infinite-horizon, which makes OPPE more challenging.

The state-of-the-art methods for infinite-horizon off-policy policy evaluation rely on learning (discounted) state stationary distribution corrections or ratios. In particular, for each state in the environments, these methods estimate the likelihood ratio of the long-term probability measure for the state to be visited in a trajectory generated by the target policy, normalized by the probability measure generated by the behavior policy. This approach can effectively avoid the exponentially high variance compared to the more classic importance sampling (IS) estimation methods (pre; Dudík et al., 2011; Hirano et al., 2003; Wang et al., 2017; Murphy et al., 2001) , especially for infinite-horizon policy evaluation (Liu et al., 2018; Nachum et al., 2019; Hallak & Mannor, 2017) . However, learning state stationary distribution requires detailed information on distributions of the behavior policy, and we call them policy-aware methods. As a consequence, policy-aware methods are difficult to apply when off-policy data are pre-generated by multiple behavior policies or when the behavior policy's form is unknown. To address this issue, Nachum et al. (2019) proposes a policy-agnostic method, DualDice, which learns the joint state-action stationary distribution correction that is much higher dimension, and therefore needs more model parameters than the state stationary distribution. Besides, there is no theoretic comparison between policy-aware and policy-agnostic methods.

In this paper, we propose a OPPE method with behavior policy learning, EMP (estimated mixture policy) for infinite-horizon off-policy policy evaluation with multiple known or unknown behavior policies. We call EMP a partially policy-agnostic method in the sense that, EMP does not require any information on each"physical" behavior policy, instead, it utilizes some aggregated information of the behavior policies learned from data. In detail, EMP includes a pre-estimation step using certain parametric model to learn a "virtual" policy (we call it the mixture policy and formally define it in Section 4). Hence, its performance depends on the accuracy of mixture policy estimation. Like the method in Liu et al. (2018) , EMP obtain OPPE also via learning the state stationary distribution correction, so it remains computationally cheap and is scalable in terms of the number of behavior policies. Besides, inspired by Hanna et al. (2019) , we provide a theoretic guarantee that EMP yields smaller mean square error (MSE) than the policy-aware methods in stationary distribution corrections learning, even in the single-behavior policy setting. On the other hand, compared to DualDice, EMP learns the state stationary distribution correction of smaller dimension, more importantly the estimation of the mixture policy can be considered as an inductive bias as far as the stationary distribution correction is concerned, and hence could achieve better performance when the pre-estimation is not expensive. In addition, we propose an ad-hoc improvement of EMP, whose theoretical analysis is left for future studies. EMP is compared with both policy-aware and policy-agnostic methods in a set of continuous and discrete control tasks and shows significant improvement.

2. BACKGROUND AND RELATED WORK:

We first introduce the general setting of OPPE in infinite horizon. Then we review two families of OPPE methods, based on importance sampling (IS) and stationary distribution correction learning, respectively.

2.1. INFINITE-HORIZON OFF-POLICY POLICY EVALUATION:

We consider a Markov Decision Process (MDP) and our goal is to estimate the infinite-horizon average reward. The environment is specified by a tuple M = S, A, R, T , consisting of a state space, an action space, a reward function, and a transition probability function. A policy π interacts with the environment iteratively, starting with an initial state s 0 . At step n = 0, 1, ... , the policy produces a distribution π(•|s n ) over the actions A, from which an action a n is sampled and applied to the environment. The environment stochastically produces a scalar reward r(s n , a n ) and a next state s n+1 ∼ T (•|s n , a n ). The infinite-horizon average reward under policy π is

R π = lim N →∞ 1 N + 1 N n=0 E π [r(s n , a n )] .

Without gathering new data, off-policy policy evaluation (OPPE) considers the problem of estimating the expected reward of a target policy π via pre-collected state-action-reward tuples from policies that are different from π, which are called behavior policies. In our paper, we consider the general setting that the data are generated by multiple behavior policies π j (j = 1, .., m). Most OPPE literature has focused on the single-behavior-policy case where m = 1. In this case, we denote the behavior policy by π 0 to distinguish from the multiple-behavior-policy case. Roughly speaking, most OPPE methods can be grouped into two categories: importance-sampling(IS) based OPPE and stationary-distribution-correction based OPPE.

2.2. IMPORTANCE SAMPLING POLICY EVALUATION:

As for short-horizon off-policy policy evaluation, importance sampling policy evaluation (IS) methods (Precup et al., 2001; Dudík et al., 2011; Swaminathan et al., 2017; Precup et al., 2000; Horvitz & Thompson, 1952) have shown promising empirical results. The main idea of importance sampling based OPPE is using importance weighting π/π j to correct the mismatch between the target policy π and the behavior policy π j that generates the trajectory.

One key element in our EMP method are inspired by importance sampling literature. Li et al. (2015) and Hanna et al. (2019) show that using estimated behavior policy in the importance weighting can reduce the mean square error (MSE). EMP also uses estimated policy, but there are two key difference between EMP and the previous works: (1) EMP is not an IS-based method, it involves a min-max problem;

(2) EMP focuses on multiple-behavior-policy setting while these papers have focused on single-behavior setting.

2.3. POLICY EVALUATION VIA LEARNING STATIONARY DISTRIBUTION CORRECTION:

The state-of-the-art methods for long-horizon off-policy policy evaluation are stationary-distributioncorrection based (Liu et al., 2018; Nachum et al., 2019; Hallak & Mannor, 2017) . Let d π0 (s) and d π (s) be the stationary distribution of state s under the behavior policy π 0 and target policy π respectively. The main idea of such methods is directly applying importance weighting by ω = d π /d π0 on the stationary state-visitation distributions to avoid the exploding variance suffered from IS, and estimate the average reward as

EQUATION

For example, Liu et al. (2018) uses min-max approach to estimate ω directly from the data. This class of methods require exact knowledge of behavior policy π 0 and are not straightforward to apply in multiple-behavior-policy setting. Recently, Nachum et al. (2019) proposed DualDice to overcome such limitation by learning the state-action stationary distribution correction ω(s, a) = d π (s)π(a|s)/d π0 (s)π 0 (a|s).

3. SINGLE BEHAVIOR POLICY ESTIMATION:

When the behavior policy π 0 in (1) is unknown, a natural idea is to estimate it from data. In this section, we focus on the standard case where the data are generated by a single behavior policy so that estimation of behavior policy is more straightforward. We first breifly review the method introduced by Liu et al. (2018) in Section 3.1, which we shall refer as the BCH method in the rest of the paper, to explain the min-max problem formulation of the stationary distribution correction learning task. In Section 3.2, we show that behavior policy estimation is beneficial in two aspects. First, it extends the stationary distribution correction method to settings where behavior policy is unknown. Second, even when the behavior policy is known with exact values, we prove that the stationary distribution correction learned using behavior policy estimation has smaller MSE than that using exact values. Later, we will extend this behavior policy estimation idea to more general multiple-behavior-policy cases in Section 4. We briefly review the BCH method proposed by Liu et al. (2018) . As d π (s) is the stationary distribution of s n as n → ∞ under policy π, it follows that: Recall that d π0 (s, a, s ) = d π0 (s)π 0 (a|s)T (s |a, s), so ω and the data sample satisfy the following equation

d π (s ) =

E (s,a,s )∼dπ 0 ω(s ) -ω(s) π(a|s) π 0 (a|s) f (s ) = 0, ∀f.

BCH solves the above equation via the following min-max problem:

EQUATION

and use kernel method to solve ω. The derivation of kernel method is put in Appendix A.

3.2. LEARNING STATIONARY DISTRIBUTION CORRECTION WITH ESTIMATED BEHAVIOR POLICY:

The objective function in the min-max problem (2), evaluated by data sample, can be viewed as a one-step importance sampling estimation. As shown in Hanna et al. (2019) , importance sampling with estimated behavior policy has smaller MSE. Motivated by this fact and the heuristic that better objective function evaluation will lead to more accurate solution, we show that the BCH method can also be improved by using estimated behavior policy to obtain smaller asymptotic MSE. We will use this result to build theoretic guarantee for the performance of EMP method in Section 4.

To formally state the theoretic result, we need to introduce more notation. Assume that we are given a class of stationary distribution correction Ω = {ω(η; s) : η ∈ E η }, and there exists η 0 ∈ E η such that the true distribution correction ω(s) = ω(η 0 ; s). Let ω(η; s) be the stationary distribution correction learned by the min-max problem (2) and ω(η; s) be that learned by a min-max problem similar to (2) with π 0 replaced with its estimation π0 . Intuitively, π0 is estimated from the data sample and appears in the denominator, as a result, it could cancel out a certain amount of random error in data sample. Following this intuition and applying the proof techniques in Henmi et al. (2007) , we establish the following theoretic guarantee that using estimated behavior policy1 yields better estimates of the stationary distribution correction. Theorem 1. Under Assumptions 1 and 2, we have, asymptotically

E[(η -η 0 ) 2 ] ≤ E[(η -η 0 ) 2 ].

As a direct consequence, we derive the finite-sample error bound for η.

Corollary 1. Let N be the number of (s, a, s ) tuples in the data. Under Assumptions 1 and 2,

E[(η -η 0 ) 2 ] = O 1 N .

Due to the space limit, we put the precise descriptions of Assumptions 1 and 2 (which involves details of the kernel method that solves the min-max problem (2)) for Theorem 1 and Corollary 1 to hold and their proofs are in Appendix B.

4. EMP FOR MULTIPLE BEHAVIOR POLICIES:

In this section, we apply the behavior policy estimation idea and develop our EMP method for OPPE in settings of multiple behavior policies and establish theoretic variance reduction results for EMP. In Section 4.1, we first clarify what is the policy to estimate from data when there are multiple behavior policies. Then, we introduce EMP in Section 4.2 and establish variance reduction result in 4.3.

4.1. MIXTURE POLICY AND MIXTURE STATE DISTRIBUTION:

Let's first take a closer look at the distribution of data generated by multiple behavior policies. In particular, we show that the data from different behavior policies can be pooled together as if they are generated by a virtual"mixture policy" π M , which plays a key role in derivation of EMP method.

In the multiple-behavior setting, we assume the state-action-next-state tuples are generated by m different unknown behavior policies π j , j = 1, 2, ..., m. For each j, there are N j state-action-nextstate tuples generated by π j and follows the corresponding stationary state distribution d πj . Let N = j N j and denote by w j = N j /N the proportion of data generated by policy π j . We use D M to denote the data set, then D M = {(s j,nj , a j,nj , s j,nj ) : j = 1, 2, .., m, n j = 1, 2, ..., N j }. Note that the policy label j in the subscript is only for notation clarity and it is not revealed in the data. Then, if we randomly draw a single (s, a, s ) tuple from D M , its distribution function is the mixture of state-action-next-state tuple distributions generated by each behavior policy:

d M (s, a, s ) := j w j d πj (s)π j (a|s)T (s |a, s).

With slight notation abuse, we write d M (s) = j w j d πj as the mixture state distribution. For each state-action pair (a, s), define the mixture policy π M (a|s) as the weighted average of the behavior policies:

EQUATION

The following result shows that, the multiple-behavior-policy data D M and the corresponding state distribution d M (s) can be viewed as if they were generated by the mixture policy π M Proposition 1. The state-action-next-station tuples generated by π M follows the distribution d M (s, a, s ). As a consequence, d M (s) is the stationary state distribution generated by π M .

Let ω M (s) = d π (s)/d M (s) be the likelihood ratio of the state distribution generated by the target policy over the mixture state distribution. We can estimate the average reward by ω M : Proposition 2. The average award satisfies

EQUATION

4.2. EMP METHOD:

Proposition 1 shows that d M (s), the state distribution generated by multiple behavior policies, is equal to the state stationary distribution generated by π M . If π M is known, then, following the same argument of BCH, we can learn ω M (s) = ω(η 0 ; s) via a similar min-max problem as (2), by replacing d π0 with d M and π 0 with π M , and then, estimate R π using (4), by replacing d π0 with d M , π 0 with π M and ω with ω M . But π M is usually unknown. Indeed, it involves not only the behavior polices π j , but also their stationary distributions d πj , which are unknown and hard to compute. In our EMP method, we will estimate π M directly from data, without learning π j and d πj . In particular, we assume the mixture policy π M belongs to some parametric family, i.e. π M (a|s) = π(θ M ; a, s).

For instance, π(θ; a, s) could be a regression model or a neural network. We then estimate θ M by MLE, i.e.

θM = arg max:

EQUATION

After this pre-estimation step, we replace the exact mixture policy π M with the estimated mixture policy π( θM ; •) and finally formulate the following min-max problem for EMP to learn ω M :

EQUATION

Applying Theorem 1, we build the following MSE bound for EMP method. Theorem 2. Under the same conditions of Theorem 1, if ω(η; s) and ω(η; s) are the stationary distribution correction learned from (6) and from the same min-max problem but with exact value of π M , then, asymptotically

E[(η -η 0 ) 2 ] ≤ E[(η -η 0 ) 2 ]. As a result, E[(η -η 0 ) 2 ] = O 1 N .

4.3. WHY POOLING IS BENEFICIAL FOR EMP:

One important feature of EMP is that it pools the data from different policy behaviors together and treat them as if they are from a single mixture policy. Of course, pooling makes EMP applicable to settings with minimal information on the behavior policies, for instance, EMP does not even require the knowledge on the number of behavior policies. In this part, we show that, the pooling feature of EMP is not just a compromise to the lack of behavior policy information, it also leads to variance reduction in an intrinsic manner.

If instead, the data are treated separately according to the behavior policies, we can still use EMP, or any OPPE method for single behavior policy, to obtain the stationary distribution correction ω j = d π /d πj for each behavior policy. Given ω j , a common approach for variance reduction is to apply multiple importance sampling (MIS) (Tirinzoni et al., 2019; Veach & Guibas, 1995) technique and the average reward estimator is of the form

EQUATION

)

where the function h is often referred to as heuristics and must be a partition of unity, i.e., j h j (s) = 1 for all s ∈ S. It has been proved by Veach & Guibas (1995) that MIS is unbiased, and, for given w j = N j /N , there is an optimal heuristic function to minimize the variance of RMIS .

Proposition 3. (Veach & Guibas, 1995) For MIS with fixed values of w j , j = 1, 2, ..., m, among all possible values of heuristics h, the balanced heuristic

h j (s) = w j d πj (s) m j=1 w j d πj (s)

, ∀j = 1, 2, ..., m and s ∈ S, reaches the minimal variance.

Plug the optimal heuristic h j (s) into MIS estimator (7), and we will obtain that the optimal MIS estimator coincides with the EMP estimator (4). In this light, by pooling the data together and directly learning ω M , EMP also learns the optimal MIS weight inexplicitly. 

5. EXPERIMENT:

In this section, we evaluate EMP on OPPE problems in three discrete-control tasks Taxi, Singlepath, Gridworld and one continuous-control task Pendulum (see Appendix D.1 for the details), in both single-behavior-policy (Section 5.1)and multiple-behavior-policy settings (Section 5.2), with following purposes: (i) to compare the performance of EMP with existing OPPE methods; (ii) to validate the theoretical properties for EMP; (iii) to explore potential improvement of EMP methods for future study. We will release the codes with the publication of this paper for relevant study. 

5.1. RESULTS FOR SINGLE BEHAVIOR POLICY:

In this section, we compare the EMP method with BCH, DualDice 2 and step-wise importance sampling (IS) in the setting of single-behavior policy, i.e. the data is generated from a single behavior policy.

Experiment Set-up. A single behavior policy is learned by a certain reinforcement learning algorithm 3 for evaluating BCH and IS. This single behavior policy then generates a set of trajectories consisting of s-a-s-r tuples. These tuples are used to estimate the behaviour policy in EMP method 4 as well as estimating the stationary distribution corrections for estimating the average step reward of the target policy.

Stationary Distribution Learning Performance. To validate Theorem 1, we use the Taxi domain as an example to compare the stationary distribution dπtrue and dπesti learned by BCH (using exact behavior policy) and EMP (using estimated behavior policy). Figure 1 The results indicate that both dπtrue and dπesti converge, while dπesti converges faster and is significantly closer to d π when the data size is small. These observations are well consistent with Theorem 1.

Policy Evaluation Performance. Figure 2 reports the MSE of policy evaluation by EMP, BCH, DualDice and IS methods for the 4 different environments. We observe that, (i) EMP consistently obtains smaller MSE than the other three methods for different sample scales and different environments. (ii) The performance of EMP, BCH and DualDice improves as the number of trajectories and length of horizons increase, while the IS method suffers from growing variance.

5.2. RESULTS FOR MULTIPLE UNKNOWN BEHAVIOR POLICIES:

In this section, we compare the performance of EMP with a multiple-behavior version of BCH method, DualDice and MIS (Precup et al., 2000) , and explore potential improvement of EMP methods.

2 DualDice was actually designed for discounted problems, not for the average problem as considered in this paper. However, it is the only policy-agnostic algorithm for off-policy evaluation in literature, to the best of our knowledge. 3 We use Q-learning in discrete control tasks and Actor Critic in continuous control tasks. 4 For discrete state-action space, we estimate the behavior policy by count-frequency. For continuous stateaction space, we fit the behavior policy by a neural network model and use MLE to estimate the model parameters. The details are given in Appendix D.2. Experiment Setup. For each environment, we use 5 behavior policies to generate the data. They are obtained by reinforcement learning after different number of training steps, i.e. the first 20%, 40%, 50%, 70%, 90% of training steps by which we learn the target policy. To form the multiple-behaviorpolicy samples, we generate same number of trajectories of equal length from each policy.

Policy Evaluation Performance. We implement 4 methods: EMP, BCH, DualDice and WIS introduced in pre using balanced heuristics. To compare with policy-aware BCH in the multiplebehavior-policy setting, we develop an extension BCH method called BCH (pooled), which utilize the exact values of all the behavior policies5 . Figure 3 shows that, in all 4 environments, we found EMP consistently obtain smaller MSE than the other three methods.

Pooling is Beneficial. To validate the variance reduction result Proposition 3, we compare EMP with its variation EMP (single) in which trajectories from different behaviors are not pooled. In detail, EMP (single) applies EMP to each group of data generated by same behavior policy and return the mean average reward estimation. Figure 4 shows that EMP outperforms EMP (single), which is consistent with the theoretic variance reduction result. On the other hand, the optimality of EMP in Proposition 3 holds for fixed w j , we now explore the possibility of further variance reduction via optimizing w j , i.e. , by re-weighting the proportion of samples generated by different behavior policies. In detail, we implement a variation of EMP in which the data samples are re-weighted according to the KL-divergence between its behavior policy and the target policy6 . Figure 4 also shows that the performance of KL-EMP has greater improvement with the increase of sample size and could outperform EMP in cases of large sample size where the KL-divergence is better estimated.

6. CONCLUSION:

In this paper, we advocate the viewpoint of partial policy-awareness and the benefits of estimating a "virtual" mixture policy for off-policy policy evaluation. The theoretical results of reduced variance coupled with experimental results illustrate the power of this class of methods. One key question that still remains is the following: if we are willing to estimate the individual behavior policies, can we further improve EMP by developing an efficient algorithm to compute the optimal weights? The preliminary experiment results suggest that the answer would be yes, and we will leave this for future study.

A KERNEL METHOD:

We use the reproducing kernel Hilbert space to solve the mini-max problem of BCH (Liu et al. (2018) ). The key property of RKHS we leveraged is called reproducing property. The reproducing property claims, for any function f ∈ H (H is a RKHS), the evaluation of f at point x equals its inner product with another function in RKHS:

f (s) = f, k(s, •) H .

Given the objective function of BCH L(w, f ) = E (s,a,s )∼dπ 0 [(ω(s) π(a|s π0(a|s)-ω )f (s )]. We use the reproducing property to obtain the closed form representation of max f ∈F L(w, f ) 2 , which is shown as follows:

max f ∈F L(w, f ) 2 = E (s,a,s )∼dπ 0 ,(s,ā,s )∼dπ 0 [∆ (ω; s, a, s ) ∆ (w; s, a, s ) k (s , s )]

. This equation has been proved in BCH Liu et al. (2018) .

B PROOF OF THEOREM 1 B.1 ASSUMPTIONS:

In this appendix, we provide the mathematical details and proof of Theorem 1. We first introduce some notations and assumptions.

We assume the behavior policy π 0 (a|s) belongs to a class of policies Π = {π(θ; a, s) : θ ∈ E θ }, where E θ is the parameter space, i.e. there exists θ 0 ∈ E θ such that π 0 (a|s) = π(θ 0 ; a, s). The estimated behavior policy π0 (a|s) = π( θ; a, s) is obtained via maximum likelihood method, i.e. θ = arg max N n=1 log(π(θ; s n , a n )).

We assume central limit theorem holds for θ: Assumption 1. (CLT of MLE)

E D [( θ -θ 0 ) 2 ] = O(1/N ).

Recall that we have assumed in Section 3.2 that the true stationary distribution correction ω(s) = ω(η 0 ; s). Using the kernel method introduced in Appendix A, we estimate ω(s) = ω(η; s) by

η = arg min η 1≤i,j≤N G(η, θ; x i , x j ), with x i = (s i , a i , s i ) and G(η, θ; (x i , x j )) = ω(η; s i ) π(a i |s i ) π( θ, a i , s i ) -ω(η, s i ) ω(η; s j ) π(a j |s j ) π( θ, a j , s j ) -ω(η, s j ) k(s i , s j ).

The BCH method estimate θ by

η = arg min η 1≤i,j≤N G(η, θ 0 ; x i , x j ).

Assumption 2. We assume the following regularity conditions on G:

1. G is second order differentiable. 2. E[∂ η ∂ θ G(η 0 , θ 0 ; x i , x j )] is finite. 3. E[∂ 2 η G(η 0 , θ 0 ; x i , x j )] is finite and non-zero. 4. E[∂ η G(η 0 , θ 0 ; x i , x j ) 2 ] is finite.

Here we simply write E xi∼dπ 0 ,xj ∼dπ 0 as E for the simplicity of notation.

B.2 PROOF OF THEOREM 1:

Theorem 1. Under Assumptions 1 and 2, we have, asymptotically

E[(η -η 0 ) 2 ] ≤ E[(η -η 0 ) 2 ].

Proof. Following the kernel method,

η = arg min η = arg min η 1≤i,j≤N G(η, θ; (x i , x j )) with x i = (s i , a i , s i ) and s i s i+1 .

Then, 1≤i,j≤N ∂ η G(η, θ; (x i , x j )) = 0, we have

0 = 1 N √ N 1≤i,j≤N ∂ η G(η 0 , θ 0 ; (x i , x j )) + √ N (η -η 0 ) 1 N 2 1≤i,j≤N ∂ 2 η G(η 0 , θ 0 ; (x i , x j )) + √ N ( θ -θ) 1 N 2 1≤i,j≤N ∂ θ ∂ η G(η 0 , θ 0 ; (x i , x j )) = 1 N √ N 1≤i,j≤N ∂ η G(η 0 , θ 0 ; (x i , x j )) + √ N (η -η 0 )E ∂ 2 η G(η 0 , θ 0 ; (x 1 , x 2 )) + √ N ( θ -θ)E [∂ θ ∂ η G(η 0 , θ 0 ; (x 1 , x 2 ))] + o p (1)

. By definition, η is the solution to the optimization problemmax η 1≤i,j≤N G(η, θ 0 ; (x i , x j )). Therefore, 0 = 1

N √ N 1≤i,j≤N ∂ η G(η 0 , θ 0 ; (x i , x j ))+ √ N (η -η 0 )E ∂ 2 η G(η 0 , θ 0 ; (x 1 , x 2 )) + o p (1). Define S(θ; (x i , x j )) = log(π(θ; s i , a i )) + log(π(θ; s j , a j )). Similarly, θ is the optimal solution to arg max θ 1≤i,j≤N S(θ; (x i , x j )). Therefore, 0 = 1 N √ N 1≤i,j≤N ∂ θ S(θ 0 ; (x i , x j )) + √ N ( θ - θ 0 )E ∂ 2 θ S(θ 0 ; (x 1 , x 2 )) + o p (1)

. Following the proof of Theorem 1 of (Henmin et al. 2007) , it suffices to prove that

E [∂ θ ∂ η G(η 0 , θ 0 ; (x 1 , x 2 ))] = E [-∂ η G(η 0 , θ 0 ; (x 1 , x 2 ))∂ θ S(θ 0 ; (x 1 , x 2 ))] . (8) One can check E [∂ η G(η 0 , θ 0 ; (x 1 , x 2 ))] =E k(s 1 , s 2 ) ∂ η ω(η 0 ; s 1 ) π(a 1 |s 1 ) π(θ 0 ; a 1 , s 1 ) -∂ η ω(η 0 ; s 1 ) ω(η 0 ; s 2 ) π(a 2 |s 2 ) π(θ 0 ; a 2 , s 2 ) -ω(η 0 ; s 2 ) + ∂ η ω(η; s 2 ) π(a 2 |s 2 ) π(θ 0 ; a 2 , s 2 ) -∂ η ω(η 0 ; s 2 ) ω(η 0 ; s 1 ) π(a 1 |s 1 ) π(θ 0 ; a 1 , s 1 ) -ω(η 0 ; s 1 ) =E (k(s 1 , s 2 ) + k(s 2 , s 1 )) ∂ η ω(η 0 ; s 1 ) π(a 1 |s 1 ) π(θ 0 ; a 1 , s 1 ) -∂ η ω(η 0 ; s 1 ) ω(η 0 ; s 2 ) π(a 2 |s 2 ) π(θ 0 ; a 2 , s 2 ) -ω(η 0 ; s 2 )

The last equality holds because (x 1 , x 2 ) ∼ d π0 (s 1 )π(x 1 ; η 0 ) ⊗ d π0 (s 2 )π(x 2 ; η 0 ). For the simplicity of derivation, in the rest of proof, we denote

g 1 = ∂ η ω(η 0 ; s 1 ) π(a 1 |s 1 ) π(θ 0 ; a 1 , s 1 ) -∂ η ω(η 0 ; s 1 ), g 2 = ω(η 0 ; s 2 ) π(a 2 |s 2 ) π(θ 0 ; a 2 , s 2 )

-ω(η 0 ; s 2 ).

On the other hand, note that

∂ θ S(θ; (x 1 , x 2 )) = ∂ θ π(θ; a 1 , s 1 ) π(θ; a 1 , s 1 ) 2 + ∂ θ π(θ; a 2 , s 2 ) π(θ; a 2 , s 2 ) 2 . Then, we derive E [∂ θ ∂ η G(η 0 , θ; (x 1 , x 2 ))] = E (k(s 1 , s 2 ) + k(s 2 , s 1 )) -∂ η ω(η 0 ; s 1 ) ∂ θ π(θ 0 ; a 1 , s 1 ) π(θ 0 ; a 1 , s 1 ) 2 • g 2 -ω(η 0 ; s 2 ) ∂ θ π(θ 0 ; a 2 , s 2 ) π(θ 0 ; a 2 , s 2 ) 2 • g 1 = E (k(s 1 , s 2 ) + k(s 2 , s 1 )) - ∂ θ0 π(θ 0 ; a 1 , s 1 ) π(θ 0 ; a 1 , s 1 ) 2 g 1 g 2 - ∂ θ π(θ 0 ; a 2 , s 2 ) π(θ 0 ; a 2 , s 2 ) 2 g 1 g 2 -E (k(s 1 , s 2 ) + k(s 2 , s 1 )) ∂ η ω(η 0 ; s 1 ) π(θ 0 ; a 1 , s 1 ) g 2 + ω(η 0 ; s 2 ) π(θ 0 ; a 2 , s 2 ) g 1 E [-∂ η G(η 0 , θ 0 ; (x 1 , x 2 ))∂ θ S(θ 0 ; (x 1 , x 2 ))] + E [(k(s 1 , s 2 ) + k(s 2 , s 1 )) (H 1 + H 2 )] .

Here, we denote H 1 = ∂ηω(η0;s 1 ) π(θ0;a1,s1) g 2 , H 2 = ω(η0;s 2 ) π(θ0;a2,s2) g 1 . Note that

E[g 2 |a 1 , s 1 , s 1 , s 2 ] = E ω(η 0 ; s 2 ) π(a 2 |s 2 ) π(θ 0 , a 2 , s 2 ) -ω(η 0 , s 2 ) |a 1 , s 1 , s 1 , s 2 = 0, E[g 1 |a 2 , s 2 , s 1 , s 2 ] = E ∂ η ω(η 0 ; s 1 ) π(a 1 |s 1 ) π(θ 0 ; a 1 , s 1 ) -∂ η ω(η 0 ; s 1 ) |a 2 , s 2 , s 1 , s 2 = 0.

Therefore, E[(k(s 1 , s 2 ) + k(s 2 , s 1 )) (H 1 + H 2 )] = 0. So we obtain (8).

B.3 PROOF OF COROLLARY 1:

Corollary 1. Let N be the number of (s, a, s ) tuples in the data. Under Assumptions 1 and 2,

E[(η -η 0 ) 2 ] = O 1 N .

Proof. In the prove of Theorem 1, we see that

1 N 2 1≤i,j≤N ∂ η G(η 0 , θ 0 ; (x i , x j )) + K 1 (η -η 0 ) + K 2 ( θ -θ) = o p (1).

with

K 1 = E ∂ 2 η G(η 0 , θ 0 ; (x 1 , x 2 )) and K 2 = E [∂ θ ∂ η G(η 0 , θ 0 ; (x 1 , x 2 ))]. Therefore, E[(η -η 0 ) 2 ] ≤ 2K -2 1   K 2 2 E[( θ -θ 0 ) 2 ] + E      1 N 2 1≤i,j≤N ∂ η G(η 0 , θ 0 ; (x i , x j ))   2       .

We assume that CLT holds for the maximum likelihood estimator θ, i.e.

E[( θ -θ 0 ) 2 ] = O(1/N ).

Besides, as E[∂ η G(η 0 , θ 0 ; (x i , x j ))] = 0, under Condition 4 of Assumption 2, , we can apply the central limit theorem (for stationary Markov chain) and have

E      1 N √ N 1≤i,j≤N ∂ η G(η 0 , θ 0 ; (x i , x j ))   2    = O(1).

C PROOFS OF THEORETIC RESULTS FOR EMP:

Propostion 1. The state-action-next-station tuples generated by π M follows the distribution d M (s, a, s ). As a consequence, d M (s) is the stationary state distribution generated by π M .

Proof. It suffices to check that for any s ,

EQUATION

For each behavior policy π j , we have

d πj (s ) = s,a d πj (s)π j (a|s)T (s |a, s).

Therefore, j w j d πj (s ) = s,a j w j d πj (s)π j (a|s)T (s |a, s).

Note that the left hand side is simple d M (s ). In the right hand side,

j w j d πj (s)π j (a|s) = k w k d π k (s) j w j d πj (s) k w k d πj (s) π j (a|s) = d M (s)π M (a|s),

and then we immediately obtain (9).

Published as a conference paper at ICLR 2020 Propostion 2. The average award satisfies

R π = E (s,a)∼d M ω M (s) π(a|s) π M (a|s) r(s, a) .

Proof.

E (s,a)∼d M ω(s) π(a|s) π M (a|s) r(s, a) = s,a ω(s) π(a|s) π M (a|s) r(s, a) j w j d πj (s)π j (a|s) = s,a ω(s) π(a|s) π M (a|s) r(s, a)d M (s)π M (s) = s,a d M (s)ω(s)π(a|s)r(s, a) = R π .

Theorem 2. Under the same conditions of Theorem 1, if ω(η; s) and ω(η; s) are the stationary distribution correction learned from ( 6) and from the same min-max problem but with exact value of π M , then, asymptotically

E[(η -η 0 ) 2 ] ≤ E[(η -η 0 ) 2 ]. As a result, E[(η -η 0 ) 2 ] = O 1 N .

Proof. The proof follows immediately from that of Theorem 1. In particular, assume π M ∈ {π(θ; a, s) : θ ∈ E θ } and the estimated πM = π( θ; •) is obtained via

θ = arg max θ j Nj n=1 log(π(θ; s j,n , a j,n )).

The rest part of the proof follows the same argument in the proof of Theorem 1.

D EXPERIMENTAL DETAILS D.1 ENVIRONMENT DESCRIPTION:

Taxi (Dietterich & G, 2000) is a 5 × 5 grid world simulating a taxi movement. Six actions are contained in Taxi: moves North, East, South, West, pick up and drop off a passenger. A reward of 20 is received when it picks up a passenger or drops her/he off at the right place, and a reward of -1 for each time step. The passengers are allow to randomly appear and disappear at every corner of the map at each time step. The 5 × 5 grid size yields 2000 states in total (25 × 24 × 5, corresponding to 25 taxi locations, 24 passenger appearance status and 5 taxi status (empty or with one of 4 destinations)).

Gridworld (Thomas & Brunskill, 2016) For the continuous environment Pendulum, we use a neural network to model the policy. In detail, we train a two-layer MLP neural network to estimate the policy. The size of the two hidden layers are both 32 with the learning rate 0.001 and tanh activation function. We use MEL (5) and Adam optimizer to train the neural network with batch size 128.

D.3 KL-EMP:

In EMP algorithm, the proportion of samples from policy π j in the data buffer, w j , is fixed. In an ad-hoc way, we optimize the weights w KL j according to the KL-divergence between the behavior policy π j and the target policy. Then, we will generate a new data buffer as follows. First, we sample j ∈ {1, 2, ..., m} with probability w KL j . Then, given j, we sample uniformly from the subgroup of data generated by j. Note that, to implement KL-EMP, one do not need to know the exact value of π j , but one need to know which data are generated from which policy.

In the numerical experiment, we use the following formula to compute w KL for finite state space: To implement this method for infinite or continuous state space, we replace the set of all possible states S in (10) with the set of all states that has been visited in the data buffer. Besides, the behavior policy π k is unknown, to estimate the KL-divergence D KL (π(•|s)|π k (•|s)), we use a neural network to learn π k from the subgroup of data that are generated from policy π k .

The numerical results show that using the KL weights {w KL j } could achieve smaller MSE compared to using {w j } as given by the data sample. We believe this approach deserves more careful analysis in future research studies.

D.4 ADDITIONAL EXPERIMENT RESULTS:

Note that EMP, EMP (single) and KL-EMP all have their policy-aware analogues. In order to test the variance reduction effect of policy estimation, we implement the policy-aware version for each EMP-type algorithm and compare their performances.

The policy-aware version of EMP (single) is naive BCH, in which we first apply BCH to each behavior policy and then return the estimation average. The policy-aware version of EMP is named as BCH (pooled). In BCH (pooled), the corresponding min-max problem formation is min ω max f E (j,s,a,s )∼D ω(s ) -ω(s) π(a|s) π j (a|s)

EQUATION

)

They both pool the data from different behavior policies together and the main difference is that BCH (pooled) uses the exact behavior policies.

The policy-aware version of KL-EMP is called BCH (KL-polled). The main difference between BCH (KL-polled) and BCH (polled) is that BCH (KL-polled) utilizes KL-divergence to optimize the weights.

Comparison results are shown in Figure 5 . We observe that the partially policy-agnostic methods consistently outperform their policy-aware analogues. 

:

We use MLE to obtain π0.

The details of BCH (pooled) are given in Appendix D.4

The details of KL-EMP are given in Appendix D.3

Figures and Tables:

LEARNING STATIONARY DISTRIBUTION CORRECTION WITH EXACT BEHAVIOR POLICY Assume the data, consisting of state-action-next-state tuples, are generated by a single behavior policy π 0 , i.e. D = {(s n , a n , s n ) : n = 1, 2, ..., N }. Recall that d π0 and d π are the stationary state distribution under the behavior and target policy respectively, and ω = d π /d π0 is the stationary distribution correction. In the rest of Section 3, by slight notation abuse, we also denote d π (s, a) = d π (s)π(a|s), d π0 (s, a) = d π0 (s)π 0 (a|s) and d π0 (s, a, s ) = d π0 (s)π 0 (a|s)T (s |a, s).

s,a d π (s)π(a|s)T (s |s, a) = s,a ω(s) π(a|s) π 0 (a|s) d π0 (s)π 0 (a|s)T (s |a, s), ∀s . Therefore, for any function f : S → R, s ω(s )d π0 (s )f (s ) = s,a,s ω(s) π(a|s) π 0 (a|s) d π0 (s)π 0 (a|s)T (s |a, s)f (s ).

Figure 1: (a) shows that scatter plot of pairs ( dπtrue , d π ) and pairs ( dπesti , d π ). The diagonal line indicates exact estimation. The default values of the number of trajectories is 200, and the length of horizon is 200. (b) shows the weighted total variation distance (TV distance) between dπtrue and d π , dπesti and d π respectively, along different number of trajectories and the length of horizons.

Figure 2: Single-behavior-policy results of BCH, EMP, DualDice and WIS across continuous and discrete environments with average reward. Each node indicates the mean value and the bars represents the standard error of the mean.

(a) plots the scatter pairs ( dπtrue , d π ) and ( dπesti , d π ) estimated by 200 trajectories of 200 steps. It shows that dπesti approximate d π better than dπtrue . Figure 1(b) and Figure 1(b) compare the TV distance from dπtrue and dπesti to d π .

Figure 3: Multiple-behavior-policy results of BCH (pooled), EMP, DualDice and MIS across continuous and discrete environments with average reward.

a j,n = a, s j,n = s) j Nj n=1 1(s j,n = s) .

j = arg min 1≤k≤m D KL (π(•|s)||π k (•|s))) m i=1 s∈S 1(i = arg min 1≤k≤m D KL (π(•|s)||π k (•|s))) = s∈S 1(j = arg min 1≤k≤m D KL (π(•|s)||π k (•|s))) |S|(10)

Figure 5: Results of policy-aware OPPE methods (BCH, BCH (pooled) and BCH (KL-pooled)) and their corresponding partially policy-agnostic version (EMP (single), EMP and KL-EMP ) across continuous and discrete environments with average reward.

is a 4 × 4 grid world which including one reward state, one terminate state and one fire state and thirteen normal state. Four action can be taken in this environment: up, down, left and right. A reward of -1 will be received while the agent in normal states, 1 reward is obtained in reward state, 100 reward is got in terminate state and -11 reward will got in fire state.SinglePath has 5 states, 2 actions. The agent begins in state 0 and both actions either take the agent from state n to state n + 1 or cause the agent to remain in state n. If the agent arrives at a new state, it will receive a +1 reward, otherwise it will get a 1 reward.

Table content: <table><tr><td>Pendulum has a continuous state space of R 3 which describes the triangle of and a action space of</td></tr><tr><td>[-2, 2].</td></tr><tr><td>D.2 MIXTURE POLICY ESTIMATION</td></tr></table>

Peer review (iclr2020):
After rebuttal: Thank author for the clarification. The new version looks better and I tend to accept the paper in the current version. ========= This paper provides a algorithm to solve infinite horizon off policy evaluation with multiple behavior policies by estimate a mixed policy under regression, and follows the same method of BCH. The intuition of using an estimated policy comes from Hanna et al. (2019) which shows that an estimated policy ratio can reduce variance even it introduces additional bias. The authors provide theoretical proof on that and arguing that their method is not worse than BCH one. Empirical results show that in general their method performs as good as previous baseline. I believe this method is novel and natural and worth investigating. Technical Concerns: The major concern I have is in continuous case, it is almost impossible to pre-assume a model for learning the mixed policy . For example, if the sample policies are all Gaussians, then according to equation (4) would be a complicated mixture distribution (not even a Gaussian mixture since it involves ratio of which is hard to compute). If the model is not precise, we cannot achieve the bias/variance tradeoff where the bias introduce by model mismatching can be arbitrarily large. And according to the experimental details in appendix E, I didn*t find any useful model assumption to address that issue. So my question would be: what model are you using when doing regression for ? Clarity Concern: The written of the paper is not satisfactory. The major contribution should be highlight in section 4, which from my first time reading is very unclear. The key observation of equation (4) uses a recursive definition, where we define using an undefined . I think you should rewrite as the weighted summation of . And you should avoid repeating similar equation like (2) (3) (6) and (7) where you can cite equation (2) in general or use a short notation for that equation, otherwise it is hard to contract the contribution of the paper. The experiment part is also unclear. Here*s some questions: 1) How many repetitions you apply for each figure? It seems not smooth enough. 2) Which estimator you use for you regression? Maximum Likelihood Estimation? Which model you are using for each environment (I know for tabular MLE is count based)? 3) What is in section E.3 equation (12)? How do you compute KL divergence in this equation for empirical distribution? Some minor issues: 1. You should replace *for all* to when writing equation, like equation before (2), equation (6) and equation in proposition 4. 2. You*d better to separate legend with figure in order to make the legend larger and figure clearer. Overall, I think this work is very novel and natural, but should give more consideration on the model selection. I tend to reject the paper by the current version and encourage the authors to submit to another conference after the revision.