Infinite-horizon Off-Policy Policy Evaluation with Multiple Behavior Policies
Authors: Xinyun Chen
Lu Wang
Yizhe Hang
Heng Ge
Hongyuan Zha
Venue:  (2020)
Keywords: off-policy policy evaluation
multiple importance sampling
kernel method
variance reduction

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 novel class of 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.

Published as a conference paper at ICLR 2020
INFINITE-HORIZON OFF-POLICY POLICY EVALUATION WITH MULTIPLE BEHAVIOR POLICIES
Xinyun Chen's Lu Wang?; Yizhe Hang", Heng Ge & Hongyuan Zha
Insitute for Data and Decision Analytics, The Chinese University of Hong Kong, Shenzhen &
Shenzhen Institute of Artificial Intelligence and Robotics for Society
2 Department of Computer Science, East China Normal University
3 Department of Computer Science, University of Science and Technology of China
4 School of Mathematics and Statistics, Shandong University
5 Insitute for Data and Decision Analytics, The Chinese University of Hong Kong, Shenzhen &
Shenzhen Institute of Artificial Intelligence and Robotics for Society & Georgia Institute of Technology
1 *chenxing drrenxinyun@cuhte edu. cn, 2 'luwang@stur ecnu. edu. cn, 9hangyhan@mail ustc. edu. cn, "hengge@ma il, sdu, edu. cn, 5 "zhahy@ edu.
ABSTRACT
We consider off 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 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 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 also offers 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 of the-art art methods.
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 recommendation policy (Swaminathan et al. 2017 Zheng et al. 2018). a treatment policy (Hirano) et al. [0033] Murphy et 2001)) and a traffic light control policy (Van der Pol & Oliehoek 2016). Off-policy policy evaluation methods (OPPE) utilize a set of previously-colleteed trajectories (for example, website interaction logs, patient trajectories, or robot trajectories) to estimate the value of novel decision-making policy without interacting with the environment (Precup et al., 2001 Dudik al. 2011). For many reinforcement learning applications, the value of the decision defined in 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 (dis- counted) 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 trajectory generated by the targel 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. 20003: Wang et al. 2017 Murphy et al. 2001), especially for
policy evaluation (Liu et al. 2018 Nachum al. Halak & Mannor 2017). However, learning state stationary distribution requires detailed information on distributions of the behavior policy, and call them policy- aware methods. As consequence, policy-aware aware methods difficult to apply
"Corresponding author. On leave from College of Computing, Georgia Institute of Technology. 'Fqual Contribution.

---

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-rwaar tuples from policies that are different from æ, which are called behavior policies. In our paper, we consider the general Published as a conference paper at ICLR 2020
when off- off-policy data are pre-generated by multiple behavior policies when the behavior policy's form is unknown. To address this issue, Nachum et al. (2019) proposes a policy-agnose 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" each"physsseeeeeeeeee physicaa" 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 learn "virtual" policy (we call the mixture policy and formally define it in Section 4) Hence, its performance depends on the accuracy of mixture policy estimation. Like the method Liu 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 Linglebbehvion 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 aglict-agnostic methods in set of continuous and discrete control tasks and shows significant improvement.
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 INFNITE-HORIZON OFF-POLICY POLICY EVALUATION
We consider Markov Decision Process (MDP) and our goal is estimate the infinite-horizon
average reward. The environment is specified by a tuple M = (S, A, R, T), consisting of a state space, action space, reward function, and transition probability function. A policy interacts with the environment iteratively, starting with an initial state 80- At step n = 0, 1,... the policy produces distribution x (-1sn) over the actions A, from which action an is sampled and applied to the environment. The environment stochastically produces a scalar reward r(sn, an) and a next state $n+1 ~ T(-ssn, an). The infinite- horizon average reward under policy is
R₂ = lim N +20 N
Σ Ex [r(sn; (n)] ===
setting that the data are generated by multiple behavior policies T = ....... Most OPPE literature has focused on the wongleebehavior-pllle behavior policy by To to distinguish from the multiple-behavior bew--bbr-vooollccy case. Roughly speaking, most OPPE methods can grouped into two categories: imporiance-samplin((()) based OPPE and cudiinary-distrbuttioococerees based OPPE.
case where m 1. In this case, we denote the
2.2 IMPORTANCE SAMPLING POLICY EVALUATION
As for short-horizon off-policy policy evaluation, importance sampling policy evaluation (IS) meth-
ods (Precup al. 2001 Dudik et al. 2011 Swaminathan al. 2017 Precup et al. 2000 Horvitz &
2

---

Published as a conference paper at ICLR 2020
Thompson 1952) have shown promising empirical results. The main idea of importance sampling based OPPE is using importance weighting тT /Ty to correct the mismatch between the target policy т and the behavior policy π that generates the trajectory.
One key clement in our EMP method are inspired by importance sampling literature. Li et al. (0155)
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 an IS-based method, it involves a min-max problem; (2) EMP focuses on multiple-behavior-poleyy setting while these papers have focused on single-behavior setting.
2.3 POLICY EVALUATION VIA LEARNING STATIONARY DISTRIBUTION CORRECTION
The wate-offthe ofte-oof-hhearr methods for
off- policy policy evaluation are stationary-diittiiurion
correction based (Liu et al. 2018 Nachum al. 2019 Hallak & Mannor 2017). Let dza (s) and ds(s) be the stationary distribution of state & under the behavior policy To and target policy x respectively. The main idea of such methods is directly applying importance weighting by w dz 02/db /do on the stationary state-visitation distributions to avoid the exploding variance suffered from IS, and estimate the average reward as
T(ass) r(s, a))
R B(aaa)d, (r(s, a)] E (s)a))d
wi(s):
r(s,a)
(1)
Tu(aas)
For example. Liu et al. (2018) uses min-max approach to estimate w directly from the data. This class of methods require exact knowledge of behavior policy To and are not straightforward to apply in nultiple-behavoor-pliyy setting. Recently, Nachum et al. (2019) proposed DualDice to overcome such limitation by learning the state-action stationary distribution correction w(s, a)
d (als)/dn, (s)To(als).
3 SINGLE BEHAVIOR POLICY ESTIMATION
When the behavior policy To in (I) is unknown, a natural idea is to estimate it from data. In this section, we focus the standard case where the data are generated by single behavior policy 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 shall refer 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 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-hehavior-pllle cases in Section 4
3.1 LEARNING STATIONARY DISTRIBUTION CORRECTION WITH EXACT BEHAVIOR POLICY
Assume the data, consisting of state-action-next-eeeeee policy no. i.c. D {(s, ans s',)) distribution under the behavior and target policy respectively, and w = d,, dn, is the stationary distribution correction. In the rest of Section 3 by slight notation abuse, also denote (s(s a) d= (s) (als), d (s, a) = dz (T){s)s)))))) and dz (s, as, 8') = da (s)=o(a ( (s' (aslaa, s).
tuples, are generated by a single behavior 1, ..., NN. Recall that d,, and d, are the stationary state
We briefly review the BCH method proposed by Liu et al. 2018 As (s) is the stationary distribution of 8n as n + xo under policy ग, it follows that:
(s)) Talss)
dx(' = Σ (()0m(a)))7((11ssc
Σ
d (1)0((()))) Aol. To(als)
8.a
8.a
Therefore, for any function S:S R.
Σ w(s) x(als) dr (1)
[u(d)d (s)))))
Ta(als)
2,0,8!
3

---

Published as a conference paper at ICLR 2020
Recall that dxo (s, 5') = d ( (a,ss).. s), equation
and the data sample satisfy the following
( (w(s') w(s) m(als) f(s))
0, vf.
mo(a|s)
BCH solves the above equation via the following min-max problem:
[[ ((u(6) (w(6))((s) w(s)
min max E )
_ f(s')
and use kernel method to solve w. 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 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 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, need to introduce more notation. Assume that we are given class of stationary distribution correction !2 = {w<(1 8) E }. and there exists 1/o E E,, such that
the true distribution correction w(s w (1oo 8). Let (T); be the stationary distribution correction learned by the min-max problem and w (f); be that learned by a min-max problem similar to (2) with To replaced with its estimation Ag. Intuitively, fo is estimated from the data sample and appears in the denominator, as result, it could cancel out 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 policy yields better estimates of the stationary distribution correction.
Theorem 1. Under Assumptions
and we have, asymptotically
El( no) < El(T n7o)?).
As direct consequence, we derive the finite-sample error bound for vj.
Corollary 1. Let N be the number of (8, s') tuples in the data. Under Assumptions and
( - m = O (N N
Due to the space limit, we put the precise descriptions of Assumptions | and 2 (which involves details of the kernel method that solves the min-max problem (2h for Theorem and Corollary 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 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 4.3
4.1 MIXTURE POLICY AND MIXTURE STATE DISTRIBUTION
Let's first take 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 they are generated by
policy" nM, which plays key role in derivation of EMP method.
We use MI.E obtain no-
4

---

Published as a conference paper at ICLR 2020
In the multiple- beehiple-behavior setting, assume the stte--acton--next-stiiee next-state tuples are generated by different unknown behavior policies T.. = ......., m. For each j. there are N, state-actionnnxx. state tuples generated by Ty and follows the corresponding stationary state distribution dzy- Let N= = Σj Nj and denote by wi = Nj/N the proportion of data generated by policy тz. We use MM to denote the data set, then DM = [(. a.j.ny ) j 1, m, Rj = 1, 2...... N2}- Note that the policy label j in the subscript is only for notation clarity and it is not revealed in the data. Then, we randomly draw a single (s, a, s') tuple from D M.. its distribution function is the mixture of weree-attoonn-e----tee tuple distributions generated by each behavior policy:
das (8, a,
Σ Euddr (s)d (a)))(a)))TT()))) 8).
With slight notation abuse, we write (s) E, wydn, as the mixture state distribution. For each state-action pair (a, 8), define the mixture policy Tas(s)s) as the weighted average of the behavior policies:
TM (a = = Wydr, (s) dsr(s) T (y((ss))
(3)
The following result shows that, the multiple- multiple-behavior behavior behavior-policy data DM and the corresponding state distribution d (s) can be viewed as if they were generated by the mixture policy лм Proposition 1. The state-action aacion-next-staree
tuples generated by αM follows the distribution dar(s, a, 8'). As consequence, ( the stationary state distribution generated by TM--
Let dz (d) 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 wM:
Proposition The average award satisfies
(a)s)) Tar r(s,
Rr B(s,a)ydar (M(())
4.2 EMP METHOD
Proposition I shows that ds)(s), the state distribution generated by multiple behavior policies, is equal to the state stationary distribution generated by TM. If Tas is known, then, following the same argument of BCH, we can learn (s) (no; s) via similar min-max problem (2). by replacing dn, with da and To with TM, and then, estimate RS using 4 by replacing dx, with dus- To with πM and w with was But JM is usually unknown. Indeed, involves not only the behavior polices v. but also their stationary distributions day. which are unknown and hard to compute. In will estimate aas directly from data, without learning My and dzy- In partieular,
EMP method, we assume the mixture policy πM belongs to some parametric family, i.c. TM = (00; s). For instance, (0; a, s) could be a regression model neural network. We then estimate OM by MLE, i.e.
N
0s = max
log(n((;; sj,, aj.n)).
(5)
After this pre-estimation step, replace the exact mixture policy RM with the estimated mixture policy I -0 and finally formulate the following min-max problem for EMP learn wM:
[ (w(m:=))-<(n: w(1:)
T(lss)
T (OMia, a. 5(67)
min max E (s "
Applying Theorem D we build the following MSE bound for EMP method.
Theorem 2. Under the same conditions of Theorem 7 if w(īss) and w(;;; 8) are the stationary distribution correction learned from (6) and from the same min-max problem but with exact value of TM, then, asymptotically
El 7 < El =1)
As result, F(( [[())= 0
5

---

Published as a conference paper at ICLR 2020
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 if they are from single mixture policy. Of course, pooling makes EMP applicable to settings with minimal information the knowledge on the number of behavior policies. In this part, we show that, the pooling feature of EMP is not just compromise the lack of behavior policy information, it also leads to variance reduction an intrinsic manner.
the behavior policies, for instance, EMP does not even require
If instead, the data are treated separately according to the behavior policies, can still use EMP, or any OPPE method for single behavior policy, to obtain the stationary distribution correction wy = dz, for each behavior policy. Given wy, 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
2
RMIS
with rs) Σ T(cls)r(s.a)
where the function h is often referred to as heuristics and must be partition of unity, i.e., Σ, (x) 1 for all s E S. It has been proved by Veach & Guibas (1995) that MIS is unbiased, and, for given wy = NN,N, there is an optimal heuristic function to minimize the variance of RMIS.
Proposition 3. (Veach & Guibas 1995) For MIS with fixed values of wj, j = 1,2,.... m, among all possible values of heuristics h, the balanced heuristic
()) Vj 1,2, m and s E S,
(s(s) Σラ= (idd,(()
reaches the minimal variance.
Plug the optimal heuristic (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 WM. EMP also learns the optimal MIS weight inexplicitly.
Tuncate length
Tuncate length
0.04
1.85
BCH
0.08
1.25
0.02
0.95
0.65
0.35
0.35
0.00
200
400
200
400
600
800
State Distribution
Number of Trajectories
Number of Trajectories
(a) State Distribution Comparison
(b) TV Distance
Figure (a) shows that scatter plot of pairs (d=... dz) and pairs (d-..-- dz). 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'mc and dx. drem and d, respectively, along different number of trajectories and the length of horizons.
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 [DI for the details), in both
(Section 5.1 and multiple-behhh behavior settings (Section 5.2 with follow- ing 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.
seggle-behavor-ppee

---

Published as a conference paper at ICLR 2020
GridWorld
Taxi
SinglePath
Pendulum
3.5
3.0
lagMSE
0.0
2.0
402
$10
$10
800
200
403
603
600
200
410
910
2003
-10
-2-
logMSE
-15
0.4
0.2
0.0
14
200
402
200
820
200
400
600
002
200
403
003
200
200
400
500
600
Number of Trajectories
Tuncated length
Number of Trajectories
Tuncated length
Figure 2: Single-behavior-polfe 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.
5.1 RESULTS FOR SINGLE BEIAVVIO POLICY
In this section, we compare the EMP method with BCH, DialDice and step-wise importance sampling (IS) in the setting of single-behavior policy, i.e. the data is generated from single behavior policy.
Experiment Set-up. A single behavior policy is learned by a certain reinforcement learning algo- rithm 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 estimate the behaviour policy in EMP method 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 I we use the Taxi domain as example to compare the stationary distribution din.. and d=... learned by BCH (using exact behavior policy) and EMP (using estimated behavior policy). Figure [[a) plots the scatter pairs (dxme dx) and (dmeas dx) estimated by 200 trajectories of 200 steps. shows that di approximate da better than d' Figure ((b) and Figure I(b) compare the TV distance from d and diua to d The results indicate that both di and d= converge, while dios converges faster and is significantly closer to d, when the data size is small. These observations are well consistent with Theorem [
Policy Evaluation Performance. Figure 2 reports the MSE of policy evaluation by EMP, BCH, DualDice and IS methods for the different environments. We observe that, (i) EMP consistently obtains smaller MSE than the other three methods for different sample scales and different environ- ments. (ii) The performance 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, compare the performance of EMP with multiple-bchavior version of BCH method, DualDice and MIS (Precup et al. 2000). and explore potential improvement EMP methods.
DuulDDiee was actually designed for discounted problems, not the average problem as considered paper. However, it the only policy-agnostic algorithm for off-policy evaluation in literature, to knowledge.
our
We use Q-lcarning in discrete control tasks and Actor Critic in continuous control tasks.
'For discrete state-action space, we estimate the behavior policy by count count-frequenyy For continuous state- action space, we fit the behavior policy hy neural network model and use MI.E to estimate the model parameters. The details given in Appendix D.2

---

Published as a conference paper at ICLR 2020
BCH (pooled)
EMP
DualDice
MIS
GridWorld
Taxi
SinglePath
Pendulum
2.5
-1.5
log14SE
-25
3.0
-2
0.0
-0.5
200
0.30
620
110
200
933
600
560
203
102
600
80.0
233
950
080
300
1010
2.2
loghSE
0.5
200
400
Trajectories
length
Trajectories
longth
Figure 3: Multiple-behavior-pliyy results of BCH (pooled), EMP, DualDice and MIS across continu- ous and discrete environments with average reward.
EMP (single)
EMP
KL-EMP
GridWorld
Taxi
SinglePath
Pendulum
0.6
0.4
logAAS
3.0
0.2
0.0
-02
-8.3
-0.4
200
4.30
610
600
200
433
660
860
200
400
600
000
230
400
000
800
1000
0.50
loghISE
0.25
-35
0.20
-05
400
Trajectories
length
Trajectories
length
Figure 4: Multiple-behavio-ppoiie results of EMP (single), EMP, KL-EMM across continuous and
discrete environments with average reward.
8

---

Published as a conference paper at ICLR 2020
Experiment Setup. For each environment, use 5 behavior policies to generate the data. They obtained by reinforcement learning after different number of training steps, i.c. the first 20%, 40%, 50%, 70%, 90% of training steps by which we learn the target policy. To form the multiple-behavion policy samples, we generate same number of trajectories 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-awar BCH in the multiple- behavior-policy setting, we develop an extension BCH method called BCH (pooled), which utilize the exact values of all the behavior policies 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 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 [ shows that EMP outperforms EMP (single), which consistent with the theoretic variance reduction result. On the other hand, the optimality of EMP Proposition
3 holds for fixed wj, we now explore the possibility of further variance reduction via optimizing w i.e. by re-weighting the proportion of samples generated by different behavior policies. In detail, we implement variation of EMP which the data samples are re-weighted according the KL-divergence between its behavior policy and the target policy Figure 4 also shows that the performance 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.
CONCLUSION
In this paper, we advocate the viewpoint of partial policy-awareness and the benefits of estimating "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.
Acknowledgement: We thank Zhaoyuan Li for her helpful technical comments on the proofs. Xinyun Chen is grateful the financial support from NSFC Grant No. 91646206 and 11901493, Part of the work done by Hongyuan Zha is supported by Shenzhen Institute of Artificial Intelligence and Roboties for Society, and Shenzhen Research Institute Big Data.
ACKNOWLEDGMENTS
We thank Zhaoyuan Li for her helpful technical comments the proofs. Xinyun Chen is grateful to the financial support from NSFC Grant No. 91 91646206 and 11901493. Part of the work done by Hongyuan Zha is supported by Shenzhen Institute of Artificial Intelligence and Robotics for Society, and Shenzhen Research Institute of Big Data.
"The details of BCH (pooled) are given in Appendix D.4
'The details of KL-FMP given in Appendix D.3

---

Published as a conference paper at ICLR 2020
REFERENCES
Dietterich and Thomas G. Hierarchical reinforcement learning with the maxq value function decom- position. Journal of artificial intelligence research, 13:227-303, 2000.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In ICML, pp. 1097-1104, 2011.
Assaf Hallak and Shie Mannor. Consistent on-line off-policy evaluation. In ICML, pp. 1372-1383, 2017.
Josiah Hanna, Scott Niekum, and Peter Stone. Importance sampling policy evaluation with an estimated behavior policy. In ICML, pp. 2605-2613, 2019.
Masayuki Henmi, Ryo Yoshida, and Shinto Eguchi. Importance sampling via the estiamted sampler. Biometrika, (4):985-1) 191,,9911111 2007.
Keisuke Hirano, Guido W Imbens, and Geert Ridder. Efficient estimation of average treatment effects using the estimated propensity score. Econometrica, pp- 1161-1189, 2003.
Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from finite universe. Journal of the American statistical Association, 47(260):663 666-665))6666666-0- 1952.
Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. JMLR, 2015.
Qaing Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. In NeurIPS, 2018.
Susan A Murphy, Mark der Laan, James M Robins, and Conduct Problems Prevention Re- search Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, pp. 1410-1423, 2001.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In NeurIPS, 2019.
Doina Precup, Richard S. Sutton, and Satinder P. Singh. Eligibility traces for off-policy policy evaluation. In ICML, pp. 759-766, 2000.
Doina Precup, Richard S. Sutton, and Sanjoy Dasgupta. Off Off-policy temporal-diiference learning with function approximation. In ICMI,, pp. 417-424, 2001.
Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miroslav Dudík, John Langford, Damien Jose, and Imed Zitouni. Off Off-policy evaluation for slate recommendation. In NeurIPS, pp- 3632-3642, 2017.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In ICML, pp.
2016.
Andrea Tirinzoni, Mattia Salvini, and Marcello Restelli. Transfer of samples in policy search via multiple importance sampling. In ICMI, pp. 6264-6274, 2019.
Elise Van der Pol and Frans A Oliehock. Coordinated deep reinforcement learners for traffic light control. In NewrIPS, 2016.
Eric Veach and Leonidas J Guibas. Optiamlly combining sampling techniques for Monte Carlo rendering. In SIGGRAPH, pp. 419-428, 428, 1995.
Yu-Xiang Wang, Alckh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evaluation in contextual bandits. In ICML., pp. 3589-3597, 2017.
Guanjie Zheng, Fuzheng Zhang, Zihan Zheng, Yang Xiang, Nicholas Jing Yuan, Xing Xie, and Zhenhui Li. Drm: A deep reinforcement learning framework for news recommendation. In WWW. pp. 167-176, 2018.
10

---

Published as a conference paper at ICLR 2020
A KERNEL METHOD
We use the reproducing kernel Hilbert space solve the mini-max problem of BCH (Liu al. (2018)). The key property of RKHS we leveraged is called reproducing property. The reproducing property claims, for any function f E H (H is RKHS), the evaluation f at point x equals its inner product with another function in RKHS: f(s (f.
) We use the reproducing property to obtain the closed form representation of m L(w, f)2 which is shown as follows:
Given the objective function of BCH L(w, f) =') (w)()
r(als =a(a)))-w
max f(w " (5 ( (wi a, (w: (,, 3']
JEF
This equation has been proved BCH Liu et al. 2018).
B PROOF OF THEOREM
B. ASSUMPTIONS
In this appendix, we provide the mathematical details and proof of Theorem some notations and assumptions.
| We first introduce
We assume the behavior policy To(als) belongs to a class of policies II = {T(0 a, s) Eg where En the parameter space, i.e. there exists Og &a such that (a(a))) = (06; a, 8). The estimated behavior policy tto ta(a))) = <00; a, s) obtained via maximum likelihood method, i.e.
i = arg max
log(T (e([T((;)))) 8n, an)))-
80;
We assume central limit theorem holds for 0: Assumption 1. (CLT of MLE)
Ep (0 O(1N))
O(1/N)
Recall that have assumed in Section 3.2 that the stationary distribution correction w(s) s). Using the kernel method introduced in Appendix A we estimate ((s) = w(r:: s) by
arg min
G(n, 2,,,
ISIJEN
with 24 = (s1, 0i st)) and
Ginn, 8; (F,, (w(T: ((m)))))((((a)))))))
x (ailss)) wn, (ulmis)) T(asls,) - w(n k(5),, 8/). a(0.ay.8)
=(0, ai si)
The BCH method estimate by
i - arg min
Σ
G(n, 0o: v,))
ISUS
Assumption 2.
We assume the following regularity conditions on G:
1. G is second order differentiable.
2. EE00,0,G'(mn. 00; is finite.
3. GE00 0o: 3z, 2;)] finite and non-zero.
4. El Gmo. Oo: }² is finite.
Here simply write IF Fe E for the simplicity of notation.
11

---

Published as a conference paper at ICLR 2020
B.2 PROOF OF THEOREM
Theorem 1. Under Assumptions 7 and 2 we have, asymptotically
( no) - El n7))
Proof. Following the kernel method, == arg min arg min
Σ
G(n, 0; (I2, 25)) with = (8i,0;, az 81) and of _ 81+1-
IS1JSN
Then, Eigusen G 0: (z), = 0, we have
0
NVN Σ
0,, coi (zi + VN 770) N2
Σ
8,G(no. Ooi (z))
ISúJSN
1SiJJS
VN(O - 0) N2
G(no, 0o: (x2,
ISUJN
1
0, Ooi (xI, VN E [8,G(1o, 0o: (2))
NVN
ISUJNN
VNO B)E (00 0o: (21, x2))] + op()).
By definition, is the solution to the optimization problemmax, E1 Eisijen G(n, On: (I,, 22)). There- T [0, to: [2)]] (1).
fore, 0 NUN Eie G, Bo: (z,, (,,,))))
Define S(A: (z,, =z)) = log( (0; 8,, a,)) + log (0; Sy. (g))).))) Similarly, is the optimal solution to arg maxe EigigeN S(0; (z; 22))) Therefore, 0 = NVN EigiJeN S (I,, + vN
0o E (00: [2]]] + (1). Following the proof of Theorem of (Henmin et al. 2007),
suffices to prove that
(2))))))] x2))] = EE [--,, 0o: (21,,2))0055(00 (m) E 110,,,,(rmn 0o: (x),
x2))
(8)
One can check
E G(n. do: x2))
T(a](s)) - ( (uttn: 82) T(a2)82)
=E
k(s',, 2/2)
( $1)
w(po (2)
π T00: 01)
T(Bo: 02,
(omu(n: 82) (Bu; az 82)
T(22))))
0 sb))
(w(no:)))) (ail())) - w(no: 81))
+
T(bu;
=E (ko(s), x5) + kiss s1))
O,w $1)
π (())))))
(w(7i 82)
x (
((7o: sb)
T(O a(oi a1, $1)
x (0o: a2, $2)
The last equality holds because (x1, x22 d (1)))((1))))))))))))))))) of derivation, in the rest of proof, we denote
@ dra (82 ) (22: mo). For the simplicity
(a1l$1))
w()u 82) (a2l52)
91 (n $1) (fo; a1, $1)
(,w((oo s)), 92
(not:s))
π T(00; ag, $2)
On the other hand, note that
(01 $1)
(0:
OgS(0: (21,
T(0 ((0:01,80 81)2
7 70;;22 52)
Then, we derive
E 10d, 0: x2))
81)
do (fo: a2 82)
E (M((), 1/2) + k(s s1))
Oppo s1)
(00: 01,0011111 s1)2
92 w(no: s2)
T(00; a2, $2)2 91
T a1, 81)
OoT(On; a2, 82)
E (M(61) 2/) + kk x1))
x(00;01, $1 9192 a(00; S2)2
9192
E (K(() s/)) + k(s s(1)
w(1o:
+
( 01, $1)
T(00 02, 82)
E 0, 0o: (2) (2 x22)) + E [(((51 1/2 k( (H1 + H2))
12

---

Published as a conference paper at ICLR 2020
w(maiss)
Here, we denote H1
92: H₂
a (Bojaz .0)) 91. Note that
x (00:01181)
B|02|a1, 81, s/ 5/2 E
W(mo: 82)
w(no: 5b) lai, 81, 86 56 0,
π T(00. 02 $2)
Flgi 82, 61, [/2 IR
(onju(1o: 81)
T(ai(s1)
laz, 82, 19,00 0. )npe(tn: o1)
T (Bo; 01, 01, 81)
Therefore, ([((((1 1/2) s1)) (H1 H2)] 0. So obtain
B.3 PROOF OF COROLLARY 1
Corollary 1. Let N be the number of (8, 8') tuples in the data. Under Assumptions and
(
7o = O N
Proof. In the prove of Theorem
1 we see that
Σ
8, Po: x5)) Ki n1) + K2(0 - 0) = Op()).
N
ISUJSN
with K₁ IE [8 G(no, Co: (2)) and K2 [0, 0o: (x11 Therefore,
27
Ei(A - - no $ 2
K3 00) + E
Σ
0,G Out (2s,, 2,))
N2
ISUSN
We assume that CLT holds for the maximum likelihood estimator ô, i.. B[( - 0,) OL/NN).
Besides, as G 0o: (1)) = O, under Condition of Assumption 2 central limit theorem (for stationary Markov chain) and have
we can apply the
E
Σ ISUJEN
a,G(m, to: 0o: (21522))
0(1)
NVN
C PROOFS OF THEORETIC RESULTS FOR EMP
Propostion 1. The ceee-actioon-ex--satieeee tuples generated by aMs follows the distribution dyr(s, a, 8¹). As consequence, ds((s) is the stationary state distribution generated by Tas-
Proof. It suffices check that for any s',
ds' = Σ (dl
(9)
8,a
For each behavior policy Ty we have
da,(s') = Σ
8.0
Therefore,
Σ (wydas(s)) ΣΣ wrdn, (cls) s).
8,0
Note that the left hand side is simple dar (s'). In the right hand side,
E3 widn, (s)
(s)d
Σ werdr (o (8)
Ee whdd, (s) (T((ass)) = ddr(s))tarall))
and then we immediately obtain 9
13

---

Published as a conference paper at ICLR 2020
Propostion 2. The average award satisfies
wwr(s) ((als)
R Flgaa))ddss
(al(s (s,,a)
Proof.
(ea w(s)) x(als)
= Σ (s)) ((als)
(al(a ((,,0) (
(as(als) r(s, a) Σ w ( (s)s)
8,
-E w(s) {(ass) Tas(als)
r(s, r(s,a)d Σ s,a
dm (sss))(ss)((as)rss = R.
Theorem 2. Under the same conditions of Theorem [ if s) and (fi:s) s) are the stationary distribution correction learned from (6) and from the same min-max problem but with exact value of T,, then, asymptotically
El no) - El( 70)
As a result, El( - noo) 0
Proof. The proof follows immediately from that of Theorem In particular, assume TM { a, : } and the estimated RM = x0;;-) obtained via
N₂ M
i = arg max 0
log( (T(( sy,, az,n)).
==1
The rest part of the proof follows the same argument in the proof of Theorem
D EXPERIMENTAL DETAILS
D.1 ENVIRONMENT DESCRIPTION
Taxi (Detterrich & G. 2000) is a 5 x 5 grid world simulating taxi movement. Six actions are contained in Taxi: moves North, East, South, West, pick up and drop off passenger. reward of 20 is received when it picks
passenger or drops her/he off at the right place, and reward of -1 for each time step. The passengers are allow randomly appear and disappear at every corner of the map at each time step. The 5 grid size yields 2000 states in total (25 x 24 x 5, corresponding to 25 taxi locations, passenger appearance status and taxi status (empty or with one of destinations)).
Gridworld (Thomas & Brunskill] 2016) is 4 x 4 grid world which including one reward state, one terminate state and one fire state and thirteen normal state. Four action can taken in this environment: up, down, left and right. A reward of -1 will be received while the agent in normal states, reward is obtained 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 to state 1 or cause the agent remain in state n. If the agent arrives at new state, will receive a +1 reward, otherwise it will get a reward.
Pendulum has continuous state space of R3 which describes the triangle of and action space of [-
D.2 MIXTURE POLICY ESTIMATION
For the discrete environments Taxi, Gridworld and SinglePath, the MLE estimate coincide with count-frequency, and therefore, we directly estimate
(als) Σ, EN 1(aj,n =a, 8j,n = 8)
E, N 1(8j,n =
14

---

Published as a conference paper at ICLR 2020
For the continuous environment Pendulum, we train two-layer MLP neural network to estimate the policy. The size of the two hidden layers 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.
neural network model the policy. In detail,
D.3 KL-EMP
In EMP algorithm, the proportion of samples from policy Ty in the data buffer, wj, is fixed. In an ad-hoc way, we optimize the weights w according to the KL-divergence between the behavior policy 3 and the target policy. Then, we will generate a new data buffer as follows. First, we sample j E f1,2. m) with probability wj wy7, Then, given j. we sample uniformly from the subgroup of data generated by j. Note that, implement KL-EMP, one do not need know the exact value of Ty, 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:
KL Eves 1 = arg Σ Es 1(i arg minigksm D (
(10)
E.es 1(j = arg min gskmm Der (x
|S]
To implement this method for infinite continuous state space, replace the set of all possible states (IO) with the set all states that has been visited in the data buffer. Besides, the behavior policy ma is unknown, estimate the KL-divergence ( (T((1s)[=x<<(13)))
neural network
to learn Ta from the subgroup of data that are generated from policy TT-
The numerical results show that using the KL weights (w could achieve smaller MSE compared using {wj} 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. 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-awan 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
( (w(s))
(aass) T,(a
min max E B(SNNY)
w(s)
f(5')
(11)
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) 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.
15

---

Published as a conference paper at ICLR 2020
EMP (single)
BCH
BCH (KL-pooledd
EMP
BCH (pooled)
KL-EMP
GridWorld
SinglePath
Pendulum
0.75
logM
2.0
0.20
-0.
200
4.00
630
600
200
430
600
860
200
400
660
000
230
400
800
800
1000
11.
135
logMSE
0.20
0.25
-65
-35
200
400
1000
Trajectorios
length
Trajectories
Tuncated length
Figure 5: Results of policy-aware OPPE methods (BCH, BCH (pooled) and BCH (KL-pooled) version (EMP (single), EMP and KL-EMP) across
and their corresponding partially continuous and discrete environments with average reward.
16


Reviews:
[{"review_id": "Sygmew3xqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose here a method for off-policy policy evaluation (OPPEval), to use the reinforcement reinforcement learning on infinite horizon problems from previously-collected trajectories. \n\nThe authors frame their work that much of the focus in the OPPEval field has been on, as they call, \"policy-aware\" methods that use information from the policy  to improve estimates  to cope with the mismatch between then behaviour and the estimated target policy (such as IS, WIS, etc) when computing state stationary distribution. These contrast \"policy agnostic\" methods (DualDICE, Nachum et al, 2019) that suffer from the curse of dimensionality in estimating the much higher dimensional state-action stationary distributions but do not depend on policy information. \nThe manuscripts novelty rests in a comparing and relating  these agnostic/aware approaches and propose a partially policy-agnostic method (EMP) that strives to combine advantages from both approaches by following a mixture approach (effectively a mixture of weighted policies). The authors provide a derivation of their methods bounds and show that their method outperforms policy-aware methods as well as policy-agnostic methods. In the comprehensive experiments they compare recent methods by Liu et al (BCH) and WIS (I suppose they mean weighted importance sampling following Prenup et al 2000, as no citation given) ), as well a a new policy-agnostic method they propose here (SADL). In all cases the results  favour the proposed new method (EMP). The results advance the field by providing a pathway to improved estimation results (lower uncertainty) by using policy mixtures.  \nWhile I have not checked the derivations line-by-line the results are consistent and interesting, although not entirely clear to me why this is an important contribution to a representational learning conference. \n\nA key question to this paper (and the OPPEval field) is to evaluate their methods  more consistently in closed-loop agent experiments - after training on the historical data. Perhaps for a representational learning conference this would be more appropriate way to convince one of the strength of the results.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SklbL9CnFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "  *Synopsis*:\n  The main contribution of this paper is the development of estimated mixture policy (EMP), which takes ideas from the new off-policy policy evaluation infinite horizon estimators (i.e. Liu) and from a recent development in more traditional importance weight approaches using regression importance sampling (i.e. Hannah). This new method provides a nice extension of Liu's algorithm to many policies, and to when the policy is unknown. The paper provides some nice analysis inspired by Hannah. Finally, they provide empirical results.\n\n\n  *Review*:\n\n  While I think the method has potential interest to the community, I found the empirical results lacking (particularly in missing competitors). I also have some concerns about the theory as there seems to be many typos and consistency issues making much of it hard to follow. Overall, I think this paper is not quite up for publication, but if the authors address my consistency/missing proofs issues and provide a comparison to DualDice I will increase my score.\n\n  1. I don't find the reason provided for not including DualDICE compelling and think it is an important competitor here, as there are many similarities between the two methods.\n     - It would also be interesting to reproduce the results provided by Liu et al with the model based approach, and the on-policy oracle. I don't think these are as pressing as DualDice but still interesting.\n\n  2. There are many consistency issues with respect to notation, and some odd notation choices as compared to the rest of the literature:\n     - What is script \\epsilon in the equation in 2.1? It looks like it should be an expectation over d_\\pi, but I've never seen this notation before.\n     - The indicies of sums and sets often change between one based and zero based indexing. This should be unified (preferably to one based). For example, section 2.1 \\pi_j(j=0,1,2,...,m) and m=1 for one policy doesn't work. Either \\pi_j(j=0,1,2,...m-1) or m=0. This occurs throughout the proofs in the appendix as well.\n     - What is script \\Epsilon_\\theta? Do you mean script F_\\theta? And then what does it mean for \\theta_0 \\in E_1? There seems to be many definitions missing.\n\n  2.5. There are also some issues with the presentation of the theory over the consistency issues already mentioned.\n     - The assumptions and conditions for the theorems presented in the main text should be clearly specified in the theory statement.\n     - The proof to theorem 2 (i.e. in the appendix) should be provided.\n     - The proof of proposition 4 seems to be missing as well.\n\n  *Questions*\n  Q1 What are the properties of SADL? Why was this used instead of DualDICE in the comparison?\n\n  Q2 How would BCH do if we used the mixture policy as the behavior policy in the multiple behavior policy case? How would it compare to your method? This could be an interesting comparison, just to test if the lower MSE argument holds up in the multiple behavior policy case.\n\n  Q3 What is the meaning of partially-policy-agnostic? It is unclear to me how it is different from the policy-agnostic approaches. If all that is different is you are estimating the behavior to use in the usual infinite-horizon approach, should this be in a separate category from policy-agnostic approaches? (I would say probably not, but I think you could make a case for it).\n\n  Q4 \"Then, a single (s,a,s') tuple simply follows the marginal distribution...\". Is this trivially true?\n\n  *Minor comments not taken into account in the review*\n  - section 2.1 \"target policy \\pi via a pre-collected...\" -> remove \"a\"\n  - The layout of the related works section is a bit hard to follow.\n  - \"Recently, Nachum et. al. (2019) proposes DualDice\": proposes->proposed\n  - \"by their estimated values in two folds\": do you mean in two ways? This is unclear.\n  - Section 3.1: \"notation abusion\" -> notation abuse\n  - Equation right after equation 1: \"d_\\pi_0(s)\\pi(a|s)\" -> \"d_\\pi_0(s)\\pi_0(a|s)\"\n  - \"The derivation of kernel method are put in...\" -> \"The derivation of the kernel method is put in...\"\n  - \"we need introduce more notation\" -> \"we need to introduce more notation\"\n  - Section 4: \"detailed description on the data sample\": \"on\"->\"of\"\n  - \"In this light by pooling the data together....\" These two sentences should be put together.\n  - I would like if your theorems were restated in the appendix, for ease of reading.\n\n-----------\nPost Rebuttal\n\nI'd like to thank the author for their thorough response! Given the major additions to the paper including empirical comparisons and clarity for the theory I've decided to update my score to reflect my new feelings (i.e. to a 6). I think this paper is well worth accepting in its current form.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJx9Xl7aYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "After rebuttal:\nThank author for the clarification. The new version looks better and I tend to accept the paper in the current version.\n=========\nThis 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.\n\nTechnical Concerns:\nThe major concern I have is in continuous case, it is almost impossible to pre-assume a model for learning the mixed policy $\\hat{\\pi_0}$. For example, if the sample policies $\\pi_j$ are all Gaussians, then $\\pi_0$ according to equation (4) would be a complicated mixture distribution (not even a Gaussian mixture since it involves ratio of $d_{\\pi_j}$ 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.\nAnd 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 $\\pi_0$?\n\nClarity Concern:\nThe 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 $\\pi_0$ using an undefined $d_{\\pi_0}$. I think you should rewrite $d_{\\pi_0}$ as the weighted summation of $d_{\\pi_j}$. 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.\nThe 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 $\\pi_k$ in section E.3 equation (12)? How do you compute KL divergence in this equation for empirical distribution?\n\nSome minor issues:\n1. You should replace 'for all' to $\\forall$ when writing equation, like equation before (2), equation (6) and equation in proposition 4.\n2. You'd better to separate legend with figure in order to make the legend larger and figure clearer.\n\nOverall, 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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a method to address off-policy policy evaluation in the infinite horizon case, when the available data comes from multiple unknown behavior policies.  Their solution -- the estimated mixture policy -- combines recent ideas from both infinite horizon OPE and regression importance sampling, a recent importance sampling based method.  At first, the reviewers were concerned about writing clarity, feasibility in the continuous case, and comparisons to contemporary methods like DualDICE.  After the rebuttal period, the reviewers agreed that all the major issues had been addressed through clarifications, rewriting, code release, and additional empirical comparisons.  Thus, I recommend to accept this paper.
Decision: Accept (Poster)