Empirical Analysis of Off-Policy Policy Evaluation for Reinforcement Learning

Cameron Voloshin 1 Hoang M. Le 1 Yisong Yue 1

Abstract
Off-policy policy evaluation (OPE) is the task ofpredicting the online performance of a policy using only pre-collected historical data (collectedfrom an existing deployed policy or set of policies). For many real-world applications, accurate
OPE is crucial since deploying bad policies canbe prohibitively costly or dangerous. With theincreasing interest in deploying learning-based
methods for safety-critical applications, the studyof OPE has also become correspondingly more
important. In this paper, we present the first comprehensive empirical analysis of most of the recently proposed OPE methods. Based on thousands of experiments and detailed empirical analyses, we offer a summarized set of guidelines
for effectively using OPE in practice, as well assuggest directions for future research to address
current limitations.

1. Introduction
Off-policy policy evaluation (OPE) aims to estimate thevalue of a new policy from a pre-collected dataset (Dannet al., 2014). In many real-world applications of reinforcment learning (RL), deploying a new policy to estimate
its value can be prohibitively expensive (Jiang & Li, 2016).
Testing a new policy, without analyzing how it will perform,in systems such as robotics, autonomous vehicles, trading,advertising, drug trials, traffic control put people, capital andequiptment at risk (Li et al., 2011; Wiering, 2000; Bottou
et al., 2013; Bang & Robins, 2005). It is critically importantto generate accurate counter-factual predictions of how wella new policy performs without running the policy.
Contemporary methods can be partitioned into three classesof algorithms (Farajtabar et al., 2018). The first class isthe direct methods (DM). DM aim to fit the value of apolicy directly through model-free function approximation
or by fitting a model of the environment and averaging over1

California Institute of Technology, Pasadena, CA. Correspondence to: Cameron Voloshin <cvoloshi@caltech.edu>.
Real-world Sequential Decision Making workshop at ICML 2019.
Copyright 2019 by the author(s).

rollouts within such a model. Alternatively, the second classis the inverse propensity score (IPS) methods, also known asimportance sampling (IS) methods. IPS methods estimate
the value of a policy by rescaling rewards by importancesample weights, a measure of how likely a reward is undera new policy compared to the data-generating policy. The
third class is the Doubly-Robust methods (DRM), which
blends between the IPS methods and an estimate of theaction-value function, typically supplied by a DM.
Many of these algorithms were initially designed for OPE in
the bandit scenario (Precup et al., 2000; Dudı́k et al., 2011;
Swaminathan et al., 2017; Wang et al., 2017). Later thesemethods were generalized and new methods were createdto tackle the RL problems (Precup et al., 2000; Mahmood
et al., 2014; Jiang & Li, 2016; Thomas et al., 2015; Harutyunyan et al., 2016; Thomas & Brunskill, 2016; Farajtabar
et al., 2018; Liu et al., 2018; Le et al., 2019). Yet, existing
benchmarking of the algorithms is lacking, not comprehensive, and fails to provide insight into areas where methods
particularly shine and where current research should focus.
We aim to present a benchmark which highlights challenges
one expects to face when tackling the RL setting. We implement the majority of contemporary OPE methods and reportconsice findings based on a systematic evaluation.

2. Notation
We will use a notational standard that is common acrossmodern OPE literature (Thomas & Brunskill, 2016). We
define a markov decision process by hX, A, P, R, γi, where
X is the state space, A is the action space, P : X × A → X
is the transition function with P (x0 |x, a) giving the probability entering state x0 by taking action a in state x,
R : X × A → R is the reward function with R(x, a) giving
the reward of taking action a in state x, and γ ∈ (0, 1] isthe discount factor. Let d0 be the initial state distribution.
Let a policy π : X × A → [0, 1] be a distribution of actions
for each state where an action a ∈ A in state x ∈ X has
probability π(a|x).
We assume we are given a historical dataset, D, of the form
|D|
D = {τ i = (xi0 , ai0 , r0i , si1 , . . .)}i=1 where i denotes theith trajectory in D. Each trajectory i is generated by a,possibly unique, policy πi . In the event that there is only
one data-generating policy, we call this policy πb , baseOff-Policy Policy Evaluation for Reinforcement Learning|D|

policy. Hence D = {(τ i , πi )}i=1 , where τ i ∼ πi . Let
Qmin(j 0 ,|τ i |−1) πe (ait |xit )ρij:j 0 = ρj:j 0 (τ i , πe , πi ) = t=jbe theπi (ait |xit )importance weight between an evaluation policy, πe , anda base policy πi (Thomas & Brunskill, 2016). Let wj:j 0 =P|D| i1
i=1 ρj:j 0 be a normalization factor of the importance|D|
weights. For convenience, when t0 < t, let ρit:t0 = 1 for any
trajectory i.

Sequential Doubly-Robust (SDR): (Jiang & Li, 2016)|D|

1 X Hi
V,|D| i=1 Seq−DR

VSDR =

0
VSeq−DR≡0

Hi +2−tHi +1−tb t , at ))VSDR= Vb (xt ) + ρ0:t (rt + γVSeq−DR− Q(sDoubly-Robust (DR): (Thomas & Brunskill, 2016)|D|

Finally, given a desired evaluation policy πe , we define thevalue of πe as|τ |−1X
V (πe ) = Ex∼d0 
γ t rt |x0 = x ,t=0with at ∼ πe (·|xt ), xt+1 ∼ P (·|xt , at ), rt ∼ R(xt , at ),τ = (x0 , a0 , r0 , . . .). Unless otherwise specified, we omit
dependence on πe and abbreviate the value as V .

VDR =1 Xb iV (x0 )+
|D| i=1|D| ∞1 XX t i i b i i
γ ρ0:t [rt − Q(xt , at ) + γ Vb (xit+1 )]|D| i=1 t=0
Weighted Doubly-Robust (WDR): (Thomas & Brunskill,
2016)
|D|

VW DR =

3. Methods

1 Xb iV (x0 )+
|D| i=1|D| ∞X
X

3.1. Inverse Propensity Scoring (IPS) Methods
There are several variations of the IPS method. Let Hi =|τi | − 1,
Table 1. IPS methods. (Dudı́k et al., 2011; Jiang & Li, 2016)

γt

i=1 t=0

MAGIC: (Thomas & Brunskill, 2016) Given gJ = {g i |i ∈J ⊆ N ∪ {−1}} whereg j (D) =

|D| j
X
X

γt

i=1 t=0P OLICYS TANDARD
ρi0:H
i

IS

P|D|

WIS

P|D| ρi0:Hi PHi t
i=1 w0:H (t=0 γ rt )

i=1

|D|

(

PHi

t
t=0 γ rt )S TEP - WISEit ρ0:tt=0 γ |D| rt

P|D| PHi
i=1

i

i=1

i

t ρ0:tt=0 γ w0:t rt

P|D| PHi

ρi0:t i b i i[r − Q(xt , at ) + γ Vb (xit+1 )]w0:t t

|D| j
X
X

|D|
ρi0:t i X j+1 ρi0:t b irt +γ
V (xj+1 )−
w0:t
w0:t
i=1

γt(

i=1 t=0ρi
ρi0:t b i i
Q(xt , at ) − 0:t−1 Vb (xit )),w0:tw0:t−1then define dist(y, Z) = minz∈Z |y − z| andbbn (j) = dist(g J (D), CI(g ∞ (D), 0.5))
j

Table 1 shows the calculation for the four traditional IPS
estimators: VIS , VStep−IS , VW IS , VStep−W IS . In addition,
we include the following method as well since it is a RaoBlackwellization (Liu et al., 2018) of the IPS estimators:

then, for a |J|−simplex ∆|J| we can calculate
b n + bbbbT ]xxb∗ ∈ arg min xT [ΩState Density Ratio Estimation (IH): (Liu et al., 2018)

which, finally, yields|D| HiXX

γ t ω(sit )ρt:t rti
VIH =P|D| PHi t0i0
0 0
i=1 t=0i0 =0t0 =1 γ ω(st0 )ρt :tPT
γ t dπe (sit )ω(sit ) = lim Pt=0
T
i
t
t→∞
t=0 γ dπb (st )where πb is assumed to be a fixed data-generating policy,
and dπ is the distribution of states when executing π froms0 ∼ d0 . The details for how to find ω can be found in
Algorithm 1 and 2 of (Liu et al., 2018).

b n (i, j) = Cov(g J (D), g J (D))Ω
ijx∈∆|J|VM AGIC = (bx∗ )T gJ .
MAGIC can be thought of as a weighted average of different
blends of the DM and DRM. In particular, for some i ∈ J,
g i represents estimating the first i steps of V (πe ) according
to DR (or WDR) and then estimating the remaining steps
b Hence, VM AGIC finds the most appropriate set of
via Q.
weights which trades off between using a direct method anda DRM.
3.3. Direct Methods (DM)3.2. Doubly-Robust Methods (DRM)

3.3.1. M ODEL -BASEDb
DRM rely on being supplied an action-value function Q,b
an estimate of Q, from which one can also yield V (x) =Pba∈A π(a|x)Q(x, a). Let Hi = |τi | − 1.

Fitting the MDP (MDP): (Jiang & Li, 2016) An approach tomodel-based value estimation is to directly fit the transition

Off-Policy Policy Evaluation for Reinforcement Learning

dynamics P (xt+1 |xt , at ), reward R(xt , at ), and terminal
condition P (xt+1 ∈ Xterminal |xt , at ) of the MDP using
some for of maximum likelihood or function approximation.
This yields a simulation environment from which one canextract the value ofPa policy using an average over rollouts.
T
Thus, V (π) = E[ t=1 γ t r(xt , at )|x0 = x, a0 = π(x0 )]where the expectation is over initial conditions x ∼ d0 andthe transition dynamics of the simulator.

i
Rt:H
=
i

Hi
X

γ j−t ρi(t+1):j r(xij , aij )

j=t

and
b a0 ; θ)]a0 ∈Aqθ (x, a, r) = diag[πe (a0 |x)]a0 ∈A [Q(x,− r[1{a0 = a}]a0 ∈Awhere 1 is the indicator function, then
|D| H

3.3.2. M ODEL -F REE
Every estimator in this section will approximate Q withb θ), parametrized by some θ. From Q
b the OPE estimateQ(·;
we seek is|D|
1 XX
b i0 , a; θ)V =πe (a|s)Q(s|D| i=1a∈A

Let Hi = |τi | − P
1, the length of trajectory i. Note that
Eπe Q(xt+1 , ·) = a∈A πe (a|xt+1 )Q(xt+1 , a).
Direct Model Regression (Reg): (Farajtabar et al., 2018)|D| Hi

2
1 XX
i
b
b it , ait ; θ)Q(·, θ) = minγ t ρi0:t Rt:H
−
Q(x
i
θ |D|
i=1 t=0
i
Rt:H
=
i

Hi
X

i
XX
b θ) = min 1Q(·,
γ 2t (ρi0:t−1 )2 ×
θ |D|
i=1 t=0ii
ρit qθ (xit , ait , Rt:H
)T Ωπb (xit )qθ (xit , ait , Rt:H)ii

4. Environments
For every environment, we initialize the environment with afixed horizon length T . If the agent reaches a goal before
T or if the episode is not over by step T , it will transition
to an environment-dependent absorbing state where it will
stay until time T .
4.1. Toy-Graph0γ t −t ρi(t+1):t0 rti0

R = +1 or R ~ ((+1,1)t0 =tb θ) =
Fitted Q Evaluation (FQE): (Le et al., 2019) Q(·,b k wherelimk→∞ Q|D| HiXX

b k−1 (xi , ai ; θ) − y i )2
b k = min 1
(Q
Q
t t
t
θ |D|
i=1 t=0b k−1 (xit+1 , ·; θ)yti ≡ rti + γEπe Q
Retrace(λ) (R(λ)), Tree-Backup (Tree), Qπ (λ): (Munos
et al., 2016; Precup et al., 2000; Harutyunyan et al., 2016)b θ) = limk→∞ Q
b k whereQ(·,b k (x, a; θ) = Q
b k−1 (x, a; θ)+
Q
t
X Y
t
Eπb [
γ
cs yt |x0 = x, a0 = a]
t≥0

s=1

and
b k−1 (xt+1 , ·; θ) − Q
b k−1 (xt , at ; θ)yt = rt + γEπe Qπe (as |xs )λ min(1, πb (as |xs ) ) R(λ)
cs = λπe (as |xs )
T ree


λ
Qπ (λ)
More Robust Doubly-Robust (MRDR): (Farajtabar et al.,2018) GivenΩπb (x) = diag[1/πb (a|x)]a∈A − eeT
e = [1, . . . , 1]T

a=0

a=0

1

3

2T-3

a=1
0

ABS
a=0
a=1

2

a=1

4

2T-2

R = −1 or R ~ ((−1,1)

Figure 1. Toy-Graph Environment

Figure 1 shows a visualization of the Toy-Graph environment. The graph is initialized with horizon T and withabsorbing state xabs = x0 = 0. In each episode, the agent
starts at a single starting state x0 = 0 and has two actions,a = 0 and a = 1. At each time step t < T , the agent
can enter state xt+1 = 2t + 1 by taking action a = 0, or
xt+1 = 2t + 2 by taking action a = 1. If the environmentis stochastic, we simulate noisy transitions by allowing theagent to slip into xt+1 = 2t+2 instead of xt+1 = 2t+1 andvice-versa with probability .25. At the final time t = T , theagent always enters the terminal state xabs = 0. The reward
is +1 if the agent transitions to an odd state, otherwise is −1.
If the environment provides sparse rewards, then r = +1
if xT −1 is odd, r = −1 if xT −1 is even, otherwise r = 0.
Similarly to deterministic rewards, if the environment’s rewards are stochastic, then the reward is r ∼ N (1, 1) if theOff-Policy Policy Evaluation for Reinforcement Learning

agent transitions to an odd state, otherwise r ∼ N (−1, 1).
If the rewards are sparse and stochastic then r ∼ N (1, 1) if
xT −1 is odd, otherwise r ∼ N (−1, 1) and r = 0 otherwise.
Table 2. Toy-Graph Policies
P OLICY

π(a = 0)π(a = 1)

.2
.6
.8

.8
.4
.2

πT G,0πT G,1πT G,24.2. Toy Mountain Car (Toy-MC)

a=1

a=
-10

10

-1

a= 0
a= 1

a= 0
0

0
+
R=

11

ABS

1

1

Barto, 2018). The car starts in a valley and has to go backand forth to gain enough momentum to scale the mountainand reach the end goal. The state space is given by the
position and velocity of the car. At each time step, the car
has the following options: accelerate backwards, forwards
or do nothing. The reward is r = −1 for every time step
until the car reaches the goal. While the original trajectory
length is capped at 200, we decrease the effective length
by applying every action at five times before observing
xt+1 . Furthermore, we modify the random initial position
from being uniformly between [−.6, −.4] to being one of{−.6, −.5, −.4}, with no velocity. The environment is initialized with a horizon T and absorbing state xabs = [.5, 0],
position at .5 and no velocity.
Table 4. MC Policies. These policies are epsilon greedy. With
probability 1 −  select maxa Q(x, a) otherwise select randomly.
Q is trained with DQN (Mnih et al., 2013; Van Hasselt et al., 2016)
P OLICY

D ESCRIPTION

πM C,0πM C,1

1.
0.

R ANDOM P OLICYA LWAYS FOLLOW Q

a= 1

5. Experimental Analysis
5.1. Preliminary Details
Figure 2. Toy-MC Environment

Figure 2 shows a visualization of the Toy-MC environment.
This environment is a 1-D graph-based simplification of
Mountain Car (see following description for the standard
version). The agent starts at x0 = 0, the center of the valley
and can go left or right. There are 21 total states, 10 to theleft of the starting position and 11 to the right of the starting
position, and a terminal absorbing state xabs = x0 = 0. The
agent recieves a reward of r = 0 at every timestep unlessreaching x = +11, where the agent transitions to xabs , theepisode terminates, and the agent receives a reward of +1.
If the agent reaches x = −10 and continues left then theagent remains in x = −10. If the agent does not reach statex = +11 by step T then the episode terminates and theagent transitions to the absorbing state.

An experiment generally consists of selecting an environment, the data-collecting policy (πb ), the evaluation policy(πe ), and the number of trajectories to collect (|D|). We
rollout πb a total of |D| times to generate a dataset onto
which we apply different methods to calculate Vb (πe ), an
estimate of the value. We rollout πe a total of |D| times
from which we calculate (a monte-carlo estimate of) thetrue on-policy value V (πe ). Each experiment is repeated
10 times with different random seeds. For each method
we computemean squared error (MSE) over the seeds,
Pthe
10
1
2
b
MSE= 10i=1 (V (πe )i − V (πe )i ) , a standard metric forOPE (Farajtabar et al., 2018).
We have run thousands of experiments and have highlighted
the details in tables. Methods that are within 2× the lowest
MSE among the set of experiments are highlighted in bold.
5.2. Horizon and Environment

Table 3. Toy-MC Policies
P OLICY

π(a = 0)π(a = 1)

πT M C,0
πT M C,1

.55
.4

.45
.6

4.3. Mountain Car
We use the OpenAI version of Mountain Car with a few
simplifying modifications (Brockman et al., 2016; Sutton &What is the effect of horizon on OPE methods? What effectdo sparse/dense rewards and determinstic/stochastic transitions or rewards have on how well methods can be expected
to perform?
Table 5 and Table 6 illustrate the effects on the methods
from increasing the horizon on the Toy-Graph environment from T = 4 to T = 16 under complete determinism and dense rewards. While every method experiences

Off-Policy Policy Evaluation for Reinforcement Learning

an increase in error due to increased horizon but fixed
number of trajectories, methods that rely on terms with
ρ (REG,MRDR,R(λ),Qπ (λ), both DM and DRM counterparts, and IPS) suffer substantially more. The repeatedmultiplication of importance weights causes the variance ofthe ρ term to blows up exponentially which can cripple IPS
and DRM-based performance (Liu et al., 2018).
Secondly, for finite state and actions spaces, the inherent
bellman error is zero:sup inf kf − Tπe gkπe = 0

g∈F f ∈F

for F , an |S|×|A|-dimensional table, and k·kπe , the `2 norm
weighted by the πe -induced state-action distribution, andTπ Q = r + γEx0 ∼X [Q(x0 , π(x0 )]. Direct methods such as
FQE and Qπ (λ), without ρ terms, are all capable of finding
an unbiased Qπe which is the fixed point to T πe Qπe = Qπewhen using F in a finite state and action space environment.
Thus, these methods have very small error regardless of horizon. We examine the extent of the bias when the inherent
bellman error is not zero in the later sections.
Table 5. MSE Toy-Graph. T = 4. |D| = 1024. πb = πT G,0 .
πe = πT G,2 . Tabular (Tab) function class. Deterministic transitions and rewards. Reward is received at every timestep.

Table 6. MSE Toy-Graph. T = 16. |D| = 1024. πb = πT G,0 .
πe = πT G,2 . Tabular (Tab) function class. Deterministic transitions and rewards. Reward is received at every timestep.
DMb (TAB .)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)T REE

6 E -032E1
3E1
1 E -03
6E0
1 E -03
1E1

8E0
1E2
4E1
1 E -03
5E0
1 E -03
8E0

8E0
1E2
4E1
1 E -03
5E0
1 E -03
8E0

4E0
2E1
3E2
1 E -03
4E0
1 E -03
5E0

2 E -022E1
3E2
1 E -03
6E0
1 E -03
1E1

IPS
M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

6 E -02
6E1
5E1
3E2

2E1
1E1

Table 7. MSE Toy-Graph. T = 4. |D| = 1024. πb = πT G,0 .
πe = πT G,2 . Tabular (Tab) function class. Stochastic transitions
and deterministic rewards. Reward is received at every timestep.
DM

DM

b WITH
DRM: C OMBINING Q

b (TAB .)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)T REE

3 E -033 E -01
1 E -01
6 E -04
6 E -04
6 E -04
6 E -04

4 E -025 E -033 E -026 E -04
6 E -04
6 E -04
6 E -04

4 E -025 E -033 E -026 E -04
6 E -04
6 E -04
6 E -04

3 E -02
4 E -032 E -01
6 E -04
6 E -04
6 E -04
6 E -04

3 E -022 E -022 E -01
6 E -04
6 E -04
6 E -04
6 E -04IPS
M ETHODS TANDARD

IH
IS
WIS
NAIVE

8 E -03
2E0
3 E -01
2E1

S TEP - WISE
2 E -01
6 E -02

Under stochastic transitions as seen in Table 7 and Table
8, the spread in the performance of the methods becomestighter: the best and worst case performances are within
2 orders of magnitude rather than 4 orders of magnitude(Table 5 and Table 6). The environment is homogenizing thepolicies and making them closer together (we will describe
this in further detail in the Policy Mismatch section).
Unlike stochasticity in the environment which makes DRM
help most methods (other than FQE and Qπ (λ)), stochasticity of rewards has the opposite effect as seen in Table 9.

b WITH
DRM: C OMBINING Q

b WITH
DRM: C OMBINING Q

b (TAB .)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)T REE

2 E -02
9 E -028 E -02
1 E -023 E -025 E -023 E -02

1 E -01
1 E -01
1 E -01
9 E -02
9 E -02
1 E -01
9 E -02

1 E -01
1 E -01
1 E -01
9 E -02
9 E -02
1 E -01
9 E -02

1 E -01
9 E -02
1 E -01
9 E -02
9 E -02
9 E -02
9 E -023 E -025 E -02
1 E -012 E -022 E -023 E -022 E -02IPS
M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

3 E -02
4 E -01
3 E -01
5E0

1 E -01
6 E -02

Direct methods relying on regressing on rewards, such as
MRDR and Reg, will perform worse and require more data.
We found sparsity of reward to have no notable effect on
how the OPE methods perform.
Most notably the top performer is direct FQE. MDP and IH,
particularly when T is large, are close competitors. Among
the DRM, only MAGIC remains somewhat competitive.
Since MAGIC is a blend between a direct method and WDRof that direct method, the choice of the set J (see descriptionof the method) is critical to its performance. The authors offer some heuristics for selecting J but a principled approachremains an interesting open problem.

Off-Policy Policy Evaluation for Reinforcement Learning
Table 8. MSE Toy-Graph. T = 16. |D| = 1024. πb = πT G,0 .
πe = πT G,2 . Tabular (Tab) function class. Stochastic transitions
and deterministic rewards. Reward is received at every timestep.
DM

b WITH
DRM: C OMBINING Q

b (TAB .)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)T REE

3 E -02
7E0
7E0
4 E -02
3E0
2 E -01
4E0

2E1
3E0
8E0
3E0
3E0
3E0
4E0

2E1
3E0
8E0
3E0
3E0
3E0
4E0

1E1
7E0
3E1
1E0
8 E -01
1E0
8 E -01

6 E -02
9E0
3E1
4 E -01
3E0
3 E -01
4E0

IPS
M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

3 E -02
2E1
1E1
7E1

7E0
9 E -01

M=

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)T REE

9 E -02
1E2
7E1
6 E -02
7E0
5 E -01
1E1

1E3
7E2
3E3
2E2
4E1
2E2
1E2

1E3
7E2
3E3
2E2
4E1
2E2
1E2

1E1
1E3
2E3
2E0
6E0
1E0
8E0

2E0
1E2
5E2
7 E -02
6E0
5 E -01
1E1

IPS
M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

1 E -01
1E4
5E1
3E2

1E2
1E1

5.3. Policy Mismatch
To what extent does the difference between the evaluation
and base policy influence OPE methods?
When the base policy is equivalent to the evaluation policy,
ρt:t0 ≡ 1 for any t, t0 . Importance weight-based methods
reduce to on-policy value evaluation and the estimators takea sample average of the rewards in the dataset. However, as
Q πe (x,a)
the policies diverge, the variance of ρ =πb (x,a) grows
exponentially. While we have illustrated in the last sectionthat horizon and stochasticity in the environment can leadto trouble for methods relying on importance weights ρ, wehave found that it does not always. We quantify the amountof policy mismatch by calculating the conservative estimate.

(1)

Table 10. MSE Toy-Graph. T = 4. |D| = 1024. πb = πT G,1 .
πe = πT G,2 . Tabular (Tab) function class. Stochastic transitions
and deterministic rewards. Reward is recieved at every timestep.
DM

b WITH
DRM: C OMBINING Q

b (TAB .)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)T REE

7 E -035 E -033 E -022 E -033 E -03
4 E -033 E -038 E -033 E -033 E -033 E -033 E -033 E -033 E -038 E -033 E -033 E -033 E -033 E -033 E -033 E -038 E -033 E -032 E -033 E -033 E -033 E -033 E -03

4 E -035 E -03
1 E -022 E -033 E -03
4 E -033 E -03IPS

b WITH
DRM: C OMBINING Q

b (TAB .)Q!T

Clearly M > ρ0:T for any T .

Table 9. MSE Toy-Graph. T = 16. |D| = 1024. πb = πT G,0 .
πe = πT G,2 . Tabular (Tab) function class. Deterministic transitions and stochastic rewards. Reward is received at every timestep.
DMπe (x, a)sup(x,a)∈X×A πb (x, a)

M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

3 E -038 E -036 E -036 E -01

5 E -03
4 E -03

Table 11. MSE Toy-Graph. T = 16. |D| = 1024. πb = πT G,1 .
πe = πT G,2 . Tabular (Tab) function class. Stochastic transitions
and deterministic rewards. Reward is recieved at every timestep.
DM

b WITH
DRM: C OMBINING Q

b (TAB .)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)T REE

2 E -027 E -025 E -02
1 E -023 E -02
1 E -025 E -02

1 E -01
3 E -023 E -023 E -023 E -023 E -023 E -02

1 E -01
3 E -023 E -023 E -023 E -023 E -023 E -022 E -01
3 E -023 E -023 E -023 E -023 E -02
4 E -02

4 E -023 E -025 E -02
1 E -023 E -022 E -022 E -02IPS
M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

2 E -023 E -01
9 E -02
7E0

8 E -023 E -02

Table 7 and Table 10 illustrate the difference between M =
.8 4
4
( .8
.2 ) = 256 and M = ( .6 ) ≈ 3.16, respectively. Since
M is a measure of policy similarity, then we can expect
the error to be smaller for smaller M across the board. In
these experiments the error is lower by about an order ofmagnitude.

Off-Policy Policy Evaluation for Reinforcement Learning

Similarly, 8 and Table 11 illustrate the difference between1616
M = ( .8
≈ 4.29 × 109 and M = ( .8
≈ 100. The
.2 )
.6 )
crucial distinction between M small and M large is the reaction of the DRM estimators to importance weights. When
M is small, DRM help some DM (like Reg and MRDR)
and only mildly hurt other direct methods’ performance,
while when M is large they generally hurt DM across theboard. We find it difficult to predict when DRM will help
with this experiment, but have found that there is normallya DM which performs better than any DRM.
5.4. State Distribution Mismatch
Under what conditions do IPS methods perform well but IH
does not?
IH (Liu et al., 2018) greatly circumvents the issue of policy
mismatch and horizon by learning a ratio of state visitation
frequency. We have already seen an instance where learning
this state ratio distribution is challenging. In particular
notice that in Table 5 and Table 6, IH struggles slightly andwe wish to understand why.

Table 12. MSE Toy-MC. T = 250. |D| = 1024. πb = πT M C,0 .
πe = πT M C,1 . Tabular (Tab) function class.
DM

b WITH
DRM: C OMBINING Q

b (TAB .)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)T REE

8 E -027 E -038 E -035 E -05
2 E -01
8 E -04
4 E -01

1E0
2E3
6E0
2E3
4E0
4E1
2E1

2 E -02
4E1
2 E -01
2E1
2 E -04
5 E -01
4 E -032 E -02
4E1
2 E -01
2E1
2 E -04
6 E -01
9 E -04

2 E -02
3E1
2 E -012E1
7 E -04
5 E -012 E -03IPS
M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

1 E -01
4 E -033 E -04
3 E -01

4 E -03
9 E -04

For the Toy-MC environment, even though T is very large,
because the environment terminates when the agent reaches
the goal, the horizon over which ρ compounds is significantly shorter. Hence IPS (and DRM) actually should standa chance here. Table 12 is generated with a policy that goesright with probability .55 while the evaluation goes rightwith probability .4. In this environment, a base policy which
preferentially goes right causes the environment to terminate(since the goal is reached) and would take a lot of data to explore all the states to the left. IH has a large error comparedto many DM, DR methods, and even standard IS. On theother hand, when reversing the probabilities with which theagent goes right , the IH estimator struggles less (achieving
3e-4 error, several orders of magnitude less than in Table12) since the evaluation policy induces a set of states that iswell within the base policy’s support. This issue illustrates
IH’s sample inefficiency and serves as an example of how
standard IS can beat IH when the the policies induce a large
enough support mismatch.
5.5. Function Class
How does the choice of function class and/or representationinfluence affect performance of OPE methods?
Since direct methods rely on reductions to supervised regression in order to get an OPE estimate, their performance
could potentially be influenced by their ability to generalize
to unseen states. Once the state space becomes continuous
then we cannot be sure that the inherent bellman error iszero for our choice of function class. Measuring the amountof inherent bellman error is intractable (Sutton & Barto,2018).
Table 13. MSE MC. Linear Function class. T = 250. |D| = 128.
πb = πM C,0 . πe = πM C,1 .
b WITH
DRM: C OMBINING Q

DMb (L IN .)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)
T REE

5E1
6E2
7E2
2E2
3E1
4E1
3E1

3E2
4E2
4E2
2E2
1E1
2E2
1E1

3E2
4E2
4E2
2E2
1E1
2E2
1E1

2E3
8E3
5E2
2E4
7E2
1E3
7E2

6E2
2E3
4E2
1E3
7E2
1E3
7E2

IPS
M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

2E3
1E3
2E1
3E3

5E2
2E2

Table 13 and Table 14 illustrate the results of using a linear
vs neural network function class on the MC environment.
Increasing the complexity of the function class does notnecessarily lead to an improvement in performance acrossthe board. In fact, among direct methods, only FQE saw improvement. Reg and MRDR saw little change. R(λ), Qπ (λ),
Tree, and MDP saw dramatic declines in performance.
5.6. Technical Challenges
How long does it take to run these methods? What are thechallenges of each method?
For this qualitative analysis, we consider a single trainingOff-Policy Policy Evaluation for Reinforcement Learning
Table 14. MSE MC. Neural Network function class. T = 250.
|D| = 128. πb = πM C,0 . πe = πM C,1 .
DM

b WITH
DRM: C OMBINING Q

b (NN.)Q

D IRECT

SDR

DR

WDR

MAGIC

MDP
R EG
MRDR
FQE
R(λ)
Qπ (λ)
T REE

8E2
7E2
9E2
5E1
9E2
3E3
1E3

4E2
4E2
5E2
2E2
1E3
4E3
1E3

4E2
4E2
5E2
2E2
1E3
4E3
1E3

2E3
5E2
2E2
1E4
2E3
5E4
3E3

1E3
2E2
4E2
3E3
2E3
8E3
2E3

because they are iterative approaches, they rely on moving
targets and the quality of their performance relies on how
well the loss stays under control as the errors compound
between fitting Qk on Qk−1 . In addition, these methods
tend to oscillate and their convergence is finnicky. Tricks
and tips that make DQN more stable can be developed tohelp these methods fit.
While MRDR was designed so that DR MRDR beats DR
Reg, we find MRDR to be ill conditioned in discrete settings
and the choice of regularization impacts its performance.

6. DiscussionIPS
M ETHODS TANDARDS TEP - WISE

IH
IS
WIS
NAIVE

1E3
1E3
8E1
3E3

5E2
2E2

batch B ⊂ {(xit , ait , rti , xit+1 )} = D and the neural network
function class.
Closed form methods such as the IPS methods (other thanIH) will run the fastest, since there is no reliance on training
or inference. IH runs fairly quickly as well up to the choiceof batch size |B|. In fact, part of the algorithm for IH requires creating a kernel matrix, a metric of state similarity,of size |B| × |B|. As |B| grows, the algorithm will slow.
Yet, the larger the kernel matrix, the better the algorithm
performs because it is able to properly assign similar visitation frequency weight to neighboring states. If |B| is too
small, all the states seem independent. For IH to function
properly, |B| has to be chosen to be as large as possible
while weighing the computational cost.
To calculate the direct methods, model free methods require
O(|D|) calls to the neural network. Model based methods (such as MDP) require O(T |D|) calls. Doubly-Robustb for every trajectory i andmethods demand an estimate Q
time t, which requires O(T |D|) and O(T 2 |D|) calls formodel free and model based, respectively. In general inference is fast since it can be done in batch. However, because
MDP requires rollouts (depending on calls to πe ) it must be
done serially and this has a huge impact on the run-time of
DR-based MDP.
We found R(λ), Qπ (λ), Tree can be quite expensive to run
in practice, especially when using neural networks. For
every item (xit , ait ) ∈ B ⊂ D, they all require calculatingb i0 , ai0 ) for every t0 > t. On average, this requires
Q(xttO(T |B|) calls to the neural network to do a single step ofgradient descent. On the other hand, FQE is generally cheap,
only requiring |B| calls per gradient step.
FQE, R(λ), Qπ (λ), Tree suffer from similar issues that haveplagued standard DQN (Mnih et al., 2013). In particular,

We have found that direct FQE tends to perform consistently
well when the model class is chosen appropriately (tabular
in discrete settings and neural network in continuous settings). This would be our choice, in practice. DR methods
rarely outperform the best direct method, but do help struggling direct methods when the effective horizon is shortenough. Yet we have not found a consistent way to predict
when a DR approach would help a method. DR methods
are particularly prone to error when there is modest to longhorizons and sufficient policy mismatch. IH, designed to fix
the pitfalls of DR methods, can be robust to lengthy horizon
and policy mismatch. However it is sensitive to hyperparameter tuning and base vs evaluation policy support mismatchin the absense of large quantities of data. IPS methods
generally only perform well when the effective horizon isshort and there is sufficient policy match. As expected, DR
MRDR performs better than DR Reg in general, but neitherof these methods is consistently among the best.
A few avenues for research that we have found include• Creating a blend between DM and IH (like DR createsa blend between DM and IPS).
• Embedding actions into IH to learn state-action density,
which may make it robust to its current issues• Finding a principled way of choosing the set J in
MAGIC and the batch size in IH• Finding ways to stabilize iterative methods like FQE
We leave the study of how high dimensional state spaces,such as pixel-based Atari, and POMPDs affect the methods
to future work.

Off-Policy Policy Evaluation for Reinforcement Learning

References
Bang, H. and Robins, J. M. Doubly robust estimation in missing
data and causal inference models. Biometrics, 61(4):962–973,
2005. doi: 10.1111/j.1541-0420.2005.00377.x.
Bottou, L., Peters, J., nonero Candela, J. Q., Charles, D. X., Chickering, D. M., Portugaly, E., Ray, D., Simard, P., and Snelson, E.
Counterfactual reasoning and learning systems: The example
of computational advertising. Journal of Machine Learning
Research, 14:3207–3260, 2013.
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman,J., Tang, J., and Zaremba, W. Openai gym, 2016.
Dann, C., Neumann, G., and Peters, J. Policy evaluation withtemporal differences: A survey and comparison. The Journal of
Machine Learning Research, 15(1):809–883, 2014.
Dudı́k, M., Langford, J., and Li, L. Doubly robust policy evaluation and learning. In Proceedings of the 28th International
Conference on International Conference on Machine Learning,pp. 1097–1104. Omnipress, 2011.
Farajtabar, M., Chow, Y., and Ghavamzadeh, M. More robust
doubly robust off-policy evaluation. In ICML, 2018.
Harutyunyan, A., Bellemare, M. G., Stepleton, T., and Munos, R.
Q(lambda) with off-policy corrections. In ALT, 2016.
Jiang, N. and Li, L. Doubly robust off-policy value evaluation
for reinforcement learning. In International Conference on
Machine Learning, pp. 652–661, 2016.
Le, H. M., Voloshin, C., and Yue, Y. Batch policy learning underconstraints. arXiv preprint arXiv:1903.08738, 2019.
Li, L., Chu, W., Langford, J., and Wang, X. Unbiased offline evaluation of contextual-bandit-based news article recommendation
algorithms. pp. 297–306, 01 2011. doi: 10.1145/1935826.
1935878.
Liu, Q., Li, L., Tang, Z., and Zhou, D. Breaking the curse ofhorizon: Infinite-horizon off-policy estimation. In Advances in
Neural Information Processing Systems, pp. 5361–5371, 2018.
Mahmood, A. R., van Hasselt, H. P., and Sutton, R. S. Weighted
importance sampling for off-policy learning with linear function
approximation. In Ghahramani, Z., Welling, M., Cortes, C.,
Lawrence, N. D., and Weinberger, K. Q. (eds.), Advances in
Neural Information Processing Systems 27, pp. 3014–3022.
Curran Associates, Inc., 2014.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou,I., Wierstra, D., and Riedmiller, M. Playing atari with deep
reinforcement learning. In NIPS Deep Learning Workshop.
2013.
Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M.
Safe and efficient off-policy reinforcement learning. In Lee,D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett,
R. (eds.), Advances in Neural Information Processing Systems
29, pp. 1054–1062. Curran Associates, Inc., 2016.
Precup, D., Sutton, R. S., and Singh, S. P. Eligibility traces foroff-policy policy evaluation. In Proceedings of the SeventeenthInternational Conference on Machine Learning, ICML ’00, pp.
759–766, San Francisco, CA, USA, 2000. Morgan Kaufmann
Publishers Inc. ISBN 1-55860-707-2.

Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Swaminathan, A., Krishnamurthy, A., Agarwal, A., Dudik, M.,
Langford, J., Jose, D., and Zitouni, I. Off-policy evaluation forslate recommendation. In Guyon, I., Luxburg, U. V., Bengio,S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R.
(eds.), Advances in Neural Information Processing Systems 30,
pp. 3632–3642. Curran Associates, Inc., 2017.
Thomas, P. and Brunskill, E. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference
on Machine Learning, pp. 2139–2148, 2016.
Thomas, P., Theocharous, G., and Ghavamzadeh, M. Highconfidence off-policy evaluation, 2015.
Van Hasselt, H., Guez, A., and Silver, D. Deep reinforcement
learning with double q-learning. In AAAI, volume 2, pp. 5.
Phoenix, AZ, 2016.
Wang, Y.-X., Agarwal, A., and Dudı́k, M. Optimal and adaptive
off-policy evaluation in contextual bandits. In International
Conference on Machine Learning, pp. 3589–3597, 2017.
Wiering, M. Multi-agent reinforcement learning for traffic lightcontrol. In Machine Learning: Proceedings of the SeventeenthInternational Conference (ICML’2000), pp. 1151–1158, 2000.