Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Nan Jiang
Computer Science & Engineering, University of Michigan
Lihong Li
Microsoft Research

NANJIANG @ UMICH . EDU

LIHONGLI @ MICROSOFT. COM

Abstract
We study the problem of off-policy value evaluation in reinforcement learning (RL), where one
aims to estimate the value of a new policy basedon data collected by a different policy. This problem is often a critical step when applying RL toreal-world problems. Despite its importance, existing general methods either have uncontrolledbias or suffer high variance. In this work, we
extend the doubly robust estimator for bandits tosequential decision-making problems, which getsthe best of both worlds: it is guaranteed to be unbiased and can have a much lower variance thanthe popular importance sampling estimators. We
demonstrate the estimator’s accuracy in several
benchmark problems, and illustrate its use as a
subroutine in safe policy improvement. We also
provide theoretical results on the inherent hardness of the problem, and show that our estimator
can match the lower bound in certain scenarios.

1. Introduction
We study the off-policy value evaluation problem, where one
aims to estimate the value of a policy with data collected byanother policy (Sutton & Barto, 1998). This problem is critical in many real-world applications of reinforcement learning (RL), whenever it is infeasible to estimate policy value
by running the policy because doing so is expensive, risky,or unethical/illegal. In robotics and business/marketing applications, for instance, it is often risky (thus expensive) to
run a policy without an estimate of the policy’s quality (Liet al., 2011; Bottou et al., 2013; Thomas et al., 2015a). In
medical and public-policy domains (Murphy et al., 2001;
Hirano et al., 2003), it is often hard to run a controlled
experiment to estimate the treatment effect, and off-policy
Proceedings of the 33 rd International Conference on Machine
Learning, New York, NY, USA, 2016. JMLR: W&CP volume 48.
Copyright 2016 by the author(s).

value evaluation is a form of counterfactual reasoning thatinfers the causal effect of a new intervention from historical
data (Holland, 1986; Pearl, 2009).
There are roughly two classes of approaches to off-policy
value evaluation. The first is to fit an MDP model from data
via regression, and evaluate the policy against the model.
Such a regression based approach has a relatively low variance and works well when the model can be learned tosatisfactory accuracy. However, for complex real-world
problems, it is often hard to specify a function class in regression that is efficiently learnable with limited data whileat the same time has a small approximation error. Furthermore, it is in general impossible to estimate the approximation error of a function class, resulting in a bias thatcannot be easily quantified. The second class of approaches
are based on the idea of importance sampling (IS), whichcorrects the mismatch between the distributions induced by
the target policy and by the behavior policy (Precup et al.,2000). Such approaches have the salient properties of being
unbiased and independent of the size of the problem’s state
space, but its variance can be too large for the method to be
useful when the horizon is long (Mandel et al., 2014).
In this work, we propose a new off-policy value evaluation
estimator that can achieve the best of regression based approaches (low variance) and importance sampling based
approaches (no bias). Our contributions are three-fold:
1. A simple doubly robust (DR) estimator is proposed for
RL that extends and subsumes a previous off-policy
estimator for contextual bandits.
2. The estimator’s statistical properties are analyzed,
which suggests its superiority over previous approaches. Furthermore, in certain scenarios, we provethat the estimator’s variance matches the Cramer-Rao
lower bound for off-policy value evaluation.
3. On benchmark problems, the new estimator is much
more accurate than importance sampling baselines,
while remaining unbiased in contrast to regressionbased approaches. As an application, we show how
such a better estimator can benefit safe policy iteration
with a more effective policy improvement step.

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

2. Related Work
This paper focuses on off-policy value evaluation in finitehorizon problems, which are often a natural way to model
real-world problems like dialogue systems. The goal is toestimate the expected return of start states drawn randomly
from a distribution. This differs from (and is somewhat
easier than) the setting considered in some previous work,often known as off-policy policy evaluation, which aims
to estimate the whole value function (Precup et al., 2000;
2001; Sutton et al., 2015). Both settings find important yet
different uses in practice, and share the same core difficultyof dealing with distribution mismatch.
The DR technique was first studied in statistics (Rotnitzky& Robins, 1995) to improve the robustness of estimation
against model misspecification, and a DR estimator has beendeveloped for dynamic treatment regime (Murphy et al.,2001). DR was later applied to policy learning in contextual
bandits (Dudı́k et al., 2011), and its finite-time varianceis shown to be typically lower than IS. The DR estimatorin this work extends the work of Dudı́k et al. (2011) tosequential decision-making problems. In addition, we showthat in certain scenarios the variance of DR matches thestatistical lower bound of the estimation problem.
An important application of off-policy value evaluation isto ensure that a new policy to be deployed does not havedegenerate performance in policy iteration; example algorithms for this purpose include conservative policy iteration (Kakade & Langford, 2002) and safe policy iteration (Pirotta et al., 2013). More recently, Thomas et al.
(2015a) incorporate lower confidence bounds with IS in approximate policy iteration to ensure that the computed policy
meets a minimum value guarantee. Our work compliments
their interesting use of confidence intervals by providing
DR as a drop-in replacement of IS. We show that after sucha replacement, an agent can accept good policies more aggressively hence obtain higher reward, while maintaining
the same level of safety against bad policies.

3. Background3.1. Markov Decision Processes
An MDP is defined by M = hS, A, P, R, γi, where S is thestate space, A is the action space, P : S × A × S → R
is the transition function with P (s0 |s, a) being the probability of seeing state s0 after taking action a at state s,
R : S × A → R is the mean reward function with R(s, a)being the immediate goodness of (s, a), and γ ∈ [0, 1]
is the discount factor. Let µ be the initial state distribution. A (stationary) policy π : S × A → [0, 1] assigns
each state s ∈ S a distribution over actions, where a ∈ A
has probability π(a|s). The distribution of a H-step trajectory τ = (s1 , a1 , r1 , . . . , sH , aH , rH , sH+1 ) is specified

by µ and π as follows: s1 ∼ µ, and for t = 1, . . . , H,at ∼ π0 (st ), st+1 ∼ P (·|st , at ), and rt has mean R(st , at )conditioned on (st , at ). We refer to such a distribution asτ ∼ (µ, π) in short. The H-step discounted value of π isv π,H := Eτ ∼(µ,π)

HhXiγ t−1 rt .

(1)

t=1

When the value of π is conditioned on s1 = s (and a1 =a), we define it as the state (and action) value function
V π,H (s) (and Qπ,H (s, a)). In some discounted problems
the true horizon is infinite, but for the purpose of policy
value evaluation we can still use a finite H (usually set to beon the order of O(1/(1 − γ))) so that v π,H approximatesv π,∞ with a bounded error that diminishes as H increases.
3.2. Off-policy Value Evaluation
For simplicity, we assume that the data (a set of length-H
trajectories) is sampled using a fixed stochastic policy1 π0 ,known as the behavior policy. Our goal is to estimate v π1 ,H ,the value of a given target policy π1 from data trajectories.
Below we review two popular families of estimators foroff-policy value evaluation.
Notation Since we are only interested in the value of π1 ,the dependence of value functions on policy is omitted. In
terms like V π1 ,H−t+1 (st ), we also omit the dependence
on horizon and abbreviate as V (st ), assuming there are
H + 1 − t remaining steps. Also, all (conditional) expectations are taken with respect to the distribution induced by(µ, π0 ), unless  stated otherwise. Finally, we
 use the shorthand: Et · := E · s1 ,a1 , . . . , st−1 , at−1 for conditional
expectations, and Vt · for variances similarly.
3.2.1. R EGRESSION E STIMATORS
If the true parameters of the MDP are known, the valueof the target policy can be computed recursively by the
Bellman equations: let V 0 (s) ≡ 0, and for h = 1, 2, . . . , H,
Qh (s, a) := Es0 ∼P (·|s,a) R(s, a) + γV h−1 (s0 ) , (2)V h (s) := Ea∼π1 (·|s) Qh (s, a) .
(3)
This suggests a two-step, regression based procedure forc fromoff-policy value evaluation: first, fit an MDP model M
data; second, compute the value function from Eqn.(3) usingb Evaluating the resulting
the estimated parameters Pb and R.
Hbvalue function, V (s), on a sample of initial states and theaverage will be an estimate of v π1 ,H . (Alternatively, one
could generate artificial trajectories for evaluation without
explicitly referring to a model (Fonteneau et al., 2013).)
When an exact state representation is used and each stateaction pair appears sufficiently often in the data, such regres1
Analyses in this paper can be easily extended to handle data
trajectories that are associated with different behavior policies.

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

sion estimators have provably low variances and negligible
biases (Mannor et al., 2007), and often outperform alternatives in practice (Paduraru, 2013).
However, real-world problems usually have a large or eveninfinite state space, and many state-action pairs will not
be observed even once in the data, rendering the necessityof generalization in model fitting. To generalize, one canc (Jong &either apply function approximation to fitting M
Stone, 2007; Grünewälder et al., 2012), or to fitting thevalue function directly (Bertsekas & Tsitsiklis, 1996; Sutton& Barto, 1998; Dann et al., 2014). While the use of function
approximation makes the problem tractable, it can introduce
bias to the estimated value when the MDP parameters or thevalue function cannot be represented in the corresponding
function class. Such a bias is in general hard to quantify
from data, thus breaks the credibility of estimations given
by regression based approaches (Farahmand & Szepesvári,
2011; Marivate, 2015; Jiang et al., 2015).
3.2.2. I MPORTANCE S AMPLING E STIMATORSThe IS estimator provides an unbiased estimate of π1 ’svalue by averaging the following function of each trajectory (s1 , a1 , r1 , . . . , sH+1 ) in the data: define the per-step
importance ratio as ρt := π1 (at |st )/πQt0 (at |st ), and thecumulative importance ratio ρ1:t := t0 =1 ρt0 ; the basic(trajectory-wise) IS estimator, and an improved step-wiseversion are given as follows:
PH t−1 
VIS := ρ1:H ·
rt ,
(4)
t=1 γ
PH t−1
Vstep-IS := t=1 γ ρ1:t rt .
(5)
Given a dataset D, the IS estimator is simply the averageP(i)1
estimate over the trajectories, namely |D|
i=1 VIS , where(i)|D| is the number of trajectories in D and VIS is IS applied
to the i-th trajectory. (This averaging step will be omitted forthe other estimators in the rest of this paper, and we will only
specify the estimate for a single trajectory). Typically, IS(even the step-wise version) suffers from very high variance,
which easily grows exponentially in horizon.
A variant of IS, weighted importance sampling (WIS), is abiased but consistent estimator, given as follows together
P|D| (i)with its step-wise version: define wt = i=1 ρ1:t /|D| as
the average cumulative important ratio at horizon t in adataset D, then from each trajectory in D, the estimates
given by trajectory-wise and step-wise WIS are respectively
PH t−1 
VWIS = ρw1:H
rt ,
(6)
t=1 γ
H
PH t−1 ρ1:t
Vstep-WIS = t=1 γ(7)
wt rt .
WIS has lower variance than IS, and its step-wise version
is considered as the most practical point estimator in the IS
family (Precup, 2000; Thomas, 2015). We will compare to
the step-wise IS/WIS baselines in the experiments.

3.3. Doubly Robust Estimator for Contextual Bandits
Contextual bandits may be considered as MDPs with horizon 1, and the sample trajectories take the form of (s, a, r).
Suppose now we are given an estimated reward function
b possibly from performing regression over a separate
R,dataset, then the doubly robust estimator for contextual bandits (Dudı́k et al., 2011) is defined as:b a) ,VDR := Vb (s) + ρ r − R(s,
(8)
P
(a|s)
b a). It iswhere ρ := ππ01 (a|s)
and Vb (s) := a π1 (a|s)R(s,b a) , as long as Rbeasy to verify that Vb (s) = Ea∼π0 ρR(s,and ρ are independent, which implies the unbiasedness ofb a) is a good estimate of
the estimator. Furthermore, if R(s,br, the magnitude of r − R(s, a) can be much smaller thanb a)) tends
that of r. Consequently, the variance of ρ(r − R(s,to be smaller than that of ρr, implying that DR often has alower variance than IS (Dudı́k et al., 2011).
In the case where the importance ratio ρ is unknown, DR
estimates both ρ and the reward function from data using
some parametric function classes. The name “doubly robust”
refers to fact that if either function class is properly specified,the DR estimator is asymptotically unbiased, offering two
chances to ensure consistency. In this paper, however, weare only interested in DR’s variance-reduction benefit.
Requirement of independence In practice, the target policy π1 is often computed from data, and for DR to stay unbiased, π1 should not depend on the samples used in Eqn.(8);b should be inthe same requirement applies to IS. While R
dependent of such samples as well, it is not required thatb be independent of each other. For example, we
π1 and Rb although an
can use the same dataset to compute π1 and R,
independent dataset is still needed to run the DR estimatorin Eqn.(8). In other situations where π1 is given directly,
to apply DR we can randomly split the data into two parts,
b and the other for applying Eqn.(8). The
one for fitting R
same requirements and procedures apply to the sequential
case (discussed below). In Section 6, we will empiricallyvalidate our extension of DR in both kinds of situations.

4. DR Estimator for the Sequential Setting
4.1. The Estimator
We now extend the DR estimator for bandits to the sequential case. A key observation is that Eqn.(5) can be written in0
a recursive form. Define Vstep-IS:= 0, and for t = 1, . . . , H,


H+1−t
H−t
Vstep-IS:= ρt rt + γVstep-IS.
(9)H
It can be shown that Vstep-IS
is equivalent to Vstep-IS given
in Eqn.(5). While the rewriting is straight-forward, therecursive form provides a novel and interesting insight that

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

is key to the extension of the DR estimator: that is, we canview the step-wise importance sampling estimator as dealing
with a bandit problem at each horizon t = 1, . . . , H, where
st is the context, at is the action taken, and the observed
H−tstochastic return is rt + γVstep-IS, whose expected value isb an estimate ofQ(st , at ). Then, if we are supplied with Q,
Q (possibly via regression on a separate dataset), we canapply the bandit DR estimator at each horizon, and obtain0
the following unbiased estimator: define VDR:= 0, and


H+1−t
H−t
b t , at ) . (10)VDR:= Vb (st ) + ρt rt + γVDR
− Q(sHThe DR estimate of the policy value is then VDR := VDR.

4.2. Variance Analysis
In this section, we analyze the variance of DR in Theorem 1
and show that DR is preferable than step-wise IS when ab is available. The analysis is given ingood value function Q
the form of the variance of the estimate for a single trajectory, and the variance of the estimate averaged over a dataset
D will be that divided by |D| due to the i.i.d. nature of D.
Due to space limit, the proof is deferred to Appendix A.
Theorem 1. VDR is an unbiased estimator of v π1 ,H , whose
variance is given recursively as follows: ∀t = 1, . . . , H,h 
 H+1−t i
Vt VDR= Vt V (st ) + Et Vt ρt ∆(st , at ) sthh
 i
 H−t i
+ Et ρ2t Vt+1 rt + Et γ 2 ρ2t Vt+1 VDR, (11)
b t , at ) − Q(st , at ) andwhere ∆(st , at ) := Q(s0
VH+1 VDR sH , aH = 0.
On the RHS of Eqn.(11), the first 3 terms are variances
due to different sources of randomness at time step t: statetransition randomness, action stochasticity in π0 , and reward
randomness, respectively; the 4th term contains the variancefrom future steps. The key conclusion is that DR’s varianceb via the error function ∆ = Q
b − Q in the 2nd
depends on Q
b will enjoy reduced variance,
term, hence DR with a good Q
and in general outperform step-wise IS as the latter is simplyb ≡ 0.
DR’s special case with a trivial value function Q
4.3. Confidence Intervals
As mentioned in the introduction, an important motivationfor off-policy value evaluation is to guarantee safety before
deploying a policy. For this purpose, we have to characterize the uncertainty in our estimates, usually in terms ofa confidence interval (CI). The calculation of CIs for DR
is straight-forward, since DR is an unbiased estimator applied to i.i.d. trajectories and standard concentration bounds
apply. For example, Hoeffding’s inequality states that for
random variables with bounded range b, the deviation of
the average from n independent samples from the expectedq1
value is at most b 2nlog 2δ with probability at least 1 − δ.
In the case of DR, n = |D| is the number of trajectories,δ the chosen confidence level, and b the range of the estimate, which is a function of the maximal magnitudes of rt ,b t , at ), ρt and γ. The application of more sophisticatedQ(sbounds for off-policy value evaluation in RL can be foundin Thomas et al. (2015a). In practice, however, strict CIs
are usually too pessimistic, and normal approximations areused instead (Thomas et al., 2015b). In the experiments, wewill see how DR with normally approximated CIs can leadto more effective and reliable policy improvement than IS.
4.4. An Extension
From Theorem 1, it is clear that DR only reduces the variance due to action stochasticity, and may suffer a largeb = Q, asvariance even with a perfect Q-value function Q
long as the MDP has substantial stochasiticity in rewards
and/or state transitions. It is, however, possible to address
such a limitation. For example, one modification of DR thatfurther reduces the variance in state transitions is:

H+1−t
H−t
VDR-v2= Vb (st ) + ρt rt + γVDR-v2
b t , at ) − γ Vb (st+1 ) Pb(st+1 |st ,at ) ,
− R(s
(12)
P (st+1 |st ,at )where Pb is the transition probability of the MDP model thatb While we can show that this estimator
we use to compute Q.
is unbiased and reduces the state-transition-induced varianceb and Pb (we omit
with a good reward & transition functions R
proof), it is impractical as the true transition function P is
unknown. However, in problems where we are confident
that the transition dynamics can be estimated accurately(but the reward function may be poorly estimated), we canassume that P (·) = Pb(·), and the last term in Eqn.(12)becomes simply γ Vb (st+1 ). This generally reduces morevariance than the original DR at the cost of introducing asmall bias. The bias is bounded in Proposition 1, whose
proof is deferred to Appendix B. In Section 6.1.3 we will
demonstrate the use of such an estimator by an experiment.
Proposition 1. Define  = maxs,a kPb(·|s, a)−P (·|s, a)k1 .
Then, the bias of DR-v2, computed by Eqn.(12) Pwith theHapproximation Pb/P ≡ 1, is bounded by Vmax t=1 γ t ,where Vmax is a bound on the magnitude of Vb .

5. Hardness of Off-policy Value Evaluation
In Section 4.4, we showed the possibility of reducing variance due to state transition stochasticity in a special scenario.
A natural question is whether there exists an estimator thatcan reduce such variance without relying on strong assumptions like Pb ≈ P . In this section, we answer this question
by providing hardness results on off-policy value evaluation
via the Cramer-Rao lower bound (or C-R bound for short),
and comparing the C-R bound to the variance of DR.

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Before stating the results, we emphasize that, as in otherestimation problems, the C-R bound depends crucially on
how the MDP is parameterized, because the parameterization captures our prior knowledge about the problem. In
general, the more structural knowledge is encoded in parameterization, the easier it is to recover the true parametersfrom data, and the lower the C-R bound will be. Whilestrong assumptions (e.g., parametric form of value function)
are often made in the training phase to make RL problems
tractable, one may not want to count them as prior knowledge in evaluation, as every assumption made in evaluation
decreases the credibility of the value estimate. (This is
why regression-based methods are not trustworthy; see Section 3.2.1.) Therefore, we first present the result for thehardest case when no assumptions (other than discrete decisions & outcomes) – especially the Markov assumption thatthe last observation is a state – are made, to ensure the mostcredible estimate. A relaxed case is discussed afterwards.
Definition 1. An MDP is a discrete tree MDP if• State is represented by history: that is, st = ht , where
ht := o1 a1 · · · ot−1 at−1 ot . The ot ’s are called observations. We assume discrete observations and actions.
• Initial states take the form of s = o1 . Upon taking actiona, a state s = h can only transition to a next state in theform of s0 = hao, with probability P (o|h, a).
• As a simplification, we assume γ = 1, and non-zerorewards only occur at the end of each trajectory. An additional observation oH+1 encodes the reward randomness
so that reward function R(hH+1 ) is deterministic, and an
MDP is solely parameterized by transition probabilities.
Theorem 2. For discrete tree MDPs, the variance of any
unbiased off-policy value estimator is lower bounded by
H+1
X h

i
E ρ21:(t−1) Vt V (st ) .
(13)
t=1

Observation 1. The variance of DR applied to a discreteb = Q is equal to Eqn.(13).
tree MDP when Q
Proof of Obs.1. The result follows directly by unfolding therecursion in Eqn.(11) andnoticing
that
∆
≡
0,
V
t+1


  rt ≡0 for t < H, and VH+1 V (sH+1 ) = VH+1 rH .
Implication When minimal prior knowledge is available,
the lower bound in Theorem 2 equals the variance of DRwith a perfect Q-value function, hence the part of variancedue to state transition stochasticity (which DR fails to improve even with a good Q-value function) is intrinsic to the
problem and cannot be eliminated without extra knowledge.
b is, the lower the variance
Moreover, the more accurate Q
DR tends to have. A related hardness result is given by Li
et al. (2015a) for MDPs with known transition probabilities.
Relaxed Case In Appendix C, we discuss a relaxed casewhere the MDP has a Directed Acyclic Graph (DAG) structure, allowing different histories of the same length to be
identified as the same state, making the problem easier than

the tree case. The two cases share almost identical proofs,
and below we give a concise proof of Theorem 2; readers
can consult Appendix C for a fully expanded version.
Proof of Theorem 2. In the proof, it will be convenient toindex rows and columns of a matrix (or vector) by histories,
so that Ah,h0 denotes the (h, h0 ) entry of matrix A. Furthermore, given a real-valued function f , [f (h, h0 )]h,h0 denotes
a matrix whose (h, h0 ) entry is given by f (h, h0 ).
We parameterize a discrete tree MDP by µ(o) and P (o|h, a),for h of length 1, . . . , H. For convenience, we treat µ(o)as P (o|∅), and the model parameters can be encoded as avector θ with θhao = P (o|h, a), where ha contains |ha| =0, . . . , H alternating observations & actions.
These parameters are subject to the normalization constraints that have to be taken
P into consideration in the CR bound, namely ∀h, a, o∈O P (o|h, a) = 1. In matrix
form, we have F θ = 1, where F is a block-diagonal matrix with each block being a row vector of 1’s; specifically,Fha,h0 a0 o = 1{ha = h0 a0 }. Note that F is the Jacobianof the constraints. Let U be a matrix whose column vectors consist of an orthonormal basis for the null space of F .
From Moore Jr (2010, Eqn. (3.3) and Corollary 3.10), we
obtain a Constrained Cramer-Rao Bound (CCRB):KU (U > IU )−1 U > K > ,(14)

where I is the Fisher Information Matrix (FIM) without taking the constraints into consideration, and K the Jacobian of
the quantity v π1 ,H that we want to estimate. Our calculationof the CCRB consists of four main steps.
1) Calculation of I: By definition, the FIM I is comh
> i∂ log P0 (hH+1 )
0 (hH+1 )puted as E ∂ log P∂θ, with∂θP0 (hH+1 ) := µ(o1 )π0 (a1 |o1 )P (o2 |o1 , a1 ) . . . P (oH+1 |hH , aH )being the probability of observing hH+1 under policy π0 .
Define a new notation g(hH+1 ) as a vector of indicator functions, such that g(hH+1 )hao = 1 whenever
hao is a prefix of hH+1 . Using this notation, we
0 (hH+1 )have ∂ log P∂θ= θ◦−1 ◦ g(hH+1 ), where ◦ denotes element-wise
power/multiplication. We rewriteitheh>FIM as I = E [θh−1 θh−1=0 ]h,h0 ◦ g(hH+1 )g(hH+1 )


−1 −1
>
[θh θh0 ]h,h0 ◦ E g(hH+1 )g(h
 H+1 ) . Now we com>pute E g(hH+1 )g(hH+1 ) . This matrix takes 0 in
all the entries indexed by hao and h0 a0 o0 when neither of the two strings is a prefix of the other. For
the other entries, without loss of generality, assume
h0 a0 o0 is a prefix of hao; the other case is similar as
I is symmetric. Since g(hH+1 )hao g(hH+1 )h0 a0 o0 =1 if and only if hao is a prefix of hH+1 , we have
E g(hH+1 )(hao) · g(hH+1 )(h0 a0 o0 ) = P0 (hao), and conseP0 (hao)P0 (ha)quently I(hao),(h0 a0 o0 ) = P (o|h,a)P(o0 |h0 ,a0 ) = P (o0 |h0 ,a0 ) .
2) Calculation of (U > IU )−1 : Since I is quite dense, itDoubly Robust Off-policy Value Evaluation for Reinforcement Learningis hard to compute the inverse of U > IU directly. Note,however, that for any matrix X with matching dimensions,
U > IU = U > (F > X > + I + XF )U , because by definition
U is orthogonal to F . Observing this, we design X to make
D = F > X > + I + XF diagonal so that U > DU is easy
to invert. This is achieved by letting X(h0 a0 o0 ),(ha) = 0
except when h0 a0 o0 is a prefix of ha, in which case we set
P0 (ha)X(h0 a0 o0 ),(ha) = − P (o0 |h0 ,a0 ) . It is not hard to verify that D
0 (ha)
is diagonal with D(hao),(hao) = I(hao),(hao) = PP(o|h,a)
.

>

−1

>

−1

With the above trick, we have (U IU ) = (U DU ) .
Since CCRB is invariant to the choice of U , we choose
U to be diag({U(ha) }), where U(ha) is a diagonal blockwith columns forming an orthonormal basis of the nullspace of the none-zero part of F(ha),(·) (an all-1 row vector). It is easy to verify that such U exists and is column
orthonormal, with F U = [0](ha),(ha) . We also rewrite
D = diag({D(ha) }) where D(ha) is a diagonal matrix with0 (ha)(D(ha) )o,o = PP(o|h,a), and we have U (U > IU )−1 U > =−1 >>diag({U(ha) U(ha)D(ha) U(ha)U(ha) }).
The final step is to notice that each block in the expression
1
above is simply P0 (ha)times the CCRB of a multinomial distribution p = P (·|h, a), which is diag(p) − pp> (Moore Jr,
2010, Eqn. (3.12)).
3) Calculation of P
K: Recall P
that we want to estimatev = v π1 ,H = o1 µ(o1 ) a1 π1 (a1 |o1 ) · · ·P
oH+1 P (oH+1 |hH , aH )R(hH+1 ) .
Its Jacobian, K = ∂v/∂θ, can be computed byK(hao) = P1 (ha)V (hao), where P1 (o1 a1 · · · ot at ) :=µ(o1 )π1 (a1 ) · · · P (ot |ht−1 , at−1 )π1 (at |ht ) is the probability of observing a sequence under policy π1 .
4) The C-R bound: Putting all the pieces together,
Eqn.(14) is equal to
P P1 (ha)2 P
2
ha P0 (ha)o P (o|h, a)V (hao)
2 
P
P
(o|h,
a)V
(hao)
−
o


2
PH P
1 (ha)= t=0 |ha|=t P0 (ha) P
P0 (ha)2 V V (hao) h, a .
Noticing thatP P1 (ha)/P0 (ha) is the cumulative importanceratio, and |ha|=t P0 (ha)(·) is taking expectation over sample trajectories, the lower bound is equal to
H
h
X
X h

i H+1iE ρ21:t Vt+1 V (st+1 ) =E ρ21:(t−1) Vt V (st ) .
t=0

t=1

6. Experiments
Throughout this section, we will be concerned with the comparison among the following estimators. For compactness,
we drop the prefix “step-wise” from step-wise IS & WIS.
Further experiment details can be found in Appendix D.

1. (IS) Step-wise IS of Eqn.(5);2. (WIS) Step-wise WIS of Eqn.(7);3. (REG) Regression estimator (details to be specified foreach domain in the “model fitting” paragraphs);
4. (DR) Doubly robust estimator of Eqn.(10);b5. (DR-bsl) DR with a state-action independent Q.
6.1. Comparison of Mean Squared Errors
In these experiments, we compare the accuracy of the point
estimate given by each estimator. For each domain, a policy
πtrain is computed as the optimal policy of the MDP model
estimated from a training dataset Dtrain (generated using
π0 ), and the target policy π1 is set to be (1 − α)πtrain + απ0
for α ∈ {0, 0.25, 0.5, 0.75}. The parameter α controls
similarity between π0 and π1 . A larger α tends to makeoff-policy evaluation easier, at the cost of yielding a moreconservative policy when πtrain is potentially of high quality.
We then apply the five estimators on a separate dataset Devalto estimate the value of π1 , compare the estimates to thegroundtruth value, and take the average estimation errors
across multiple draws of Deval . Note that for the DR estimab should be independent
tor, the supplied Q-value function Qof the data used in Eqn.(10) to ensure unbiasedness. We
therefore split Deval further into two subsets Dreg and Dtest ,b from Dreg and apply DR on Dtest .
estimate Q
In the above procedure, DR does not make full use of data,as the data in Dreg do not go into the sample average inEqn.(10). To address this issue, we propose a more datab has toefficient way of applying DR in the situation when Q
be estimated from (a subset of) Deval , and we call it k-fold
DR, inspired by k-fold cross validation in supervised learning: we partition Deval into k subsets, apply Eqn.(8) to eachb estimated from the remaining data, and finallysubset with Q
average the estimate over all subsets. Since the estimate
from each subset is unbiased, the overall average remains
unbiased, and has lower variance since all trajectories go
into the sample average. We only show the results of 2-fold
DR as model fitting is time-consuming.
6.1.1. M OUNTAIN C AR
Domain description Mountain car is a popular RL benchmark problem with a 2-dimensional continuous state space,
3 discrete actions, and deterministic dynamics (Singh & Sutton, 1996). We set the horizon to be 100 time steps, and theinitial state distribution to uniformly random. The behavior
policy is uniformly random over the 3 actions.
Model fitting We use state aggregations: the two statevariables are multiplied by 26 and 28 respectively, and therounded integers are treated as the abstract state. We thenestimate an MDP model from data using a tabular approach.
Data sizes & other details We choose |Dtrain | = 2000 andDoubly Robust Off-policy Value Evaluation for Reinforcement Learning
π1 = πtrain

-0.5

-1

-1
DR
IS
WIS
REG
DR-bsl

-2
2000

4000

π1 = 0.5 πtrain + 0.5 π0

0

0

-0.5

-1

-1

-1.5

-1.5

-2

2000

2000
|Dtest|

4000

-0.5
DR
IS
WIS
REG
DR-bsl

-1.5

0

1000

π1 = 0.5 πtrain + 0.5 π0

0.5

0

2000
|Dtest|4000

Figure 1. Comparison of the methods as point estimators on Mountain Car. 5000 trajectories are generated for off-policy evaluation,
and all the results are from over 4000 runs. The subgraphs correspond to the target policies produced by mixing πtrain and π0 withdifferent portions. X-axes show the size of Dtest , the part of thedata used for IS/WIS/DR/DR-bsl. The remaining data are used byb Y-axes show thethe regression estimator (REG; DR uses it as Q).
RMSE of the estimates divided by the true value in logarithmic
scale. We also show the error of 2-fold DR as an isolated point ().

|Deval | = 5000. DR-bsl uses the step-dependent constantb t , at ) = Rmin (1 − γ H−t+1 )/(1 − γ).
Q(sResults See Fig.1 for the errors of IS/WIS/DR-bsl/DR on
Dtest , and REG on Dreg . As |Dtest | increases, IS/WIS getsincreasingly better, while REG gets worse as Dreg contains
less data. Since DR depends on both halves of the data,
it achieves the best error at some intermediate |Dtest |, andbeats using all the data for IS/WIS in all the 4 graphs. DRb being a constant guess,bsl shows the accuracy of DR with Q
and it already outperforms IS/WIS most of the time.
6.1.2. S AILING
Domain description The sailing domain (Kocsis &Szepesvári, 2006) is a stochastic shortest-path problem,
where the agent sails on a grid. A state contains 4 integer variables, each representing location
or direction. There√
are 8 actions, and Rmin = −3 − 4 2 and Rmax = 0.
Model fitting We apply Kernel-based Reinforcement
Learning (Ormoneit & Sen, 2002) with smoothing kernelexp(−k · k/0.25), where k · k is the `2 -distance in S × A.
Data sizes & other details The data sizes are |Dtrain | =1000 and |Deval | = 2500. DR-bsl uses the step-dependent

-1
-1.5
-2

2000

0

0

-0.5

-0.5

-1

-1

-1.5

-1.5

1000

2000

π1 = 0.25 πtrain + 0.75 π0

0.5

0

-2

-2
0

-0.5

4000

π1 = 0.25 πtrain + 0.75 π0

0

-0.5

0

-1

π1 = 0.75 πtrain + 0.25 π0

0.5

0

-2

-2
0

Log10 of relative RMSE

-1.5

π1 = πtrain

0.5
Log10 of relative RMSE

-0.5

-1.5

π1 = 0.75 πtrain + 0.25 π00Log10 of relative RMSE

Log10 of relative RMSE

0

-2
0

1000
|Dtest|

2000

0

1000
|Dtest|2000

Figure 2. Comparison of the methods as point estimators on Sailing(4000 runs). 2500 trajectories are used in off-policy evaluation.

b t , at ) = Rmin /2 · (1 − γ H−t+1 )/(1 − γ).
constant Q(sResults See Fig.2. The results are qualitatively similar to
Mountain Car results in Fig.1, except that: (1) WIS is as
good as DR in the 2nd and 3rd graph; (2) in the 4th graph,
DR with a 3:2 split outperforms all the other estimators (including the regression estimator) with a significant margin,
and a further improvement is achieved by 2-fold DR.
6.1.3. KDD C UP 1998 D ONATION DATASETIn the last domain, we use the donation dataset from KDD
Cup 1998 (Hettich & Bay, 1999), which records the email
interactions between an agent and potential donators. A
state contains 5 integer features, and there are 12 discrete
actions. All trajectories are 22-steps long and there is no
discount. Since no groundtruth values are available for thetarget policies, we fit a simulator from the true data (seeappendix for details), and use it as groundtruth for everything henceforward: the true value of a target policy iscomputed by Monte-Carlo roll-outs in the simulator, and theoff-policy evaluation methods also use data generated fromthe simulator (under a uniformly random policy). Amongthe compared estimators, we replace DR with DR-v2 (Section 4.4; reason explained below), and use the 2-fold trick.
b is estimated as follows:
The MDP model used to compute Q
each state variable is assumed to evolve independently (areasonable assumption for this dataset), and the marginaltransition probabilities are estimated using a tabular approach, which is exactly how the simulator is fit from realdata. Reward function, on the other hand, is fit by linear

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning
IS
WIS
DR-v2
DR-bsl
REG

-0.5

-1

good policies

bad policies

12

Value improvement

Log10 of relative RMSE

0

C=0

DR

10

C=1

IS

8

C=2

0

−0.5

6
4

−1

2
0

-1.5

−2

0

2000
|D|

4000

−1.5

0

2000
|D|

4000

-2
0

0.25

0.5

0.75

Mixture (0: π train )Figure 3. Results on the donation dataset, averaged over about
5000 runs. DR-v2 is the estimator given in Eqn.(12) with the 2fold trick. The whole dataset is applied to other estimators. X-axis
shows the portion of which π0 is mixed into πtrain .

regression using the first 3 state features (on the contrast, all
the 5 features are used when fitting the simulator’s reward
function). Consequently, we get a model with an almost
perfect transition function and a relatively inaccurate reward
function, and DR-v2 is supposed to work well in such asituation. The results are shown in Fig.3, where DR-v2 isthe best estimator in all situations: it beats WIS when π1 is
far from π0 , and beats REG when π1 and π0 are close.
6.2. Application to Safe Policy Improvement
In this experiment, we apply the off-policy value evaluation
methods in safe policy improvement. Given a batch dataset
D, the agent uses part of it (Dtrain ) to find candidate policies, which may be poor due to data insufficiency and/or
inaccurate approximation. The agent then evaluates thesecandidates on the remaining data (Dtest ) and chooses a policy based on the evaluation. In this common scenario, DRb
has an extra advantage: Dtrain can be reused to estimate Q,
and it is not necessary to hold out part of Dtest for regression.
Due to the high variance of IS and its variants, acting greedily w.r.t. the point estimate is not enough to promote safety.
A typical approach is to select the policy that has the highest
lower confidence bound (Thomas et al., 2015b), and holdon to the current behavior policy if none of the bounds isbetter than the behavior policy’s value. More specifically,
the bound is V† − Cσ† , where V is the point estimate, σis the empirical standard error, and C ≥ 0 controls confidence level. † is a placeholder for any method that works
by averaging a function of sample trajectories; examples
considered in this paper are the IS and the DR estimators.
The experiment is conducted in Mountain Car, and mostof the setting is the same as Section 6.1.1. Since we
do not address the exploration-exploitation problem, we
keep the behavior policy fixed as uniformly random, andevaluate the recommended policy once in a while as the

Figure 4. Safe policy improvement in Mountain Car. X-axis shows
the size of data and y-axis shows the true value of the recommended
policy subtracted by the value of the behavior policy.

agent gets more and more data. The candidate policies are
generated as follows: we split |D| so that |Dtrain |/|D| ∈{0.2, 0.4, 0.6, 0.8}; for each split, we compute optimal
πtrain from the model estimated on Dtrain , mix πtrain and π0
with rate α ∈ {0, 0.1, . . . , 0.9}, compute their confidencebounds by applying IS/DR on D \ Dtrain , and finally pick
the policy with the highest score over all splits and α’s.
The results are shown on the left panel of Fig.4. From thefigure, it is clear that DR’s value improvement largely outperforms IS, primarily because IS is not able to accept a target
policy that is too different from π0 . However, here πtrain
is mostly a good policy (except when |D| is very small),hence the more aggressive an algorithm is, the more value it
gets. As evidence, both algorithms achieve the best value
with C = 0, raising the concern that DR might make unsafe
recommendations when πtrain is poor.
To falsify this hypothesis, we conduct another experiment inparallel, where we have πtrain minimize the value instead of
maximizing it, resulting in policies worse than the behavior
policy, and the results are shown on the right panel. Clearly,
as C becomes smaller, the algorithms become less safe,
and with the same C DR is as safe as IS if not better at|D| = 5000. Overall, we conclude that DR can be a drop-in
replacement for IS in safe policy improvement.

7. Conclusions
We proposed a doubly robust (DR) estimator for off-policy
value evaluation, and showed its high accuracy as a point
estimator and usefulness in safe policy improvement. Hardness results on the problem are also provided, and the variance of DR can match the lower bound in certain scenarios.
Building on a preliminary version of this work, Thomas& Brunskill (2016) showed that our DR estimator can beviewed as an application of control variates for variancereduction, and designed more advanced DR-based estimators. Future work includes applying such DR techniques toreal-world problems to access its effectiveness in practice.

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Acknowledgements
We thank Xiujun Li for his help on the KDD donation
dataset experiment. We also thank Satinder Singh, Michael
Littman, Susan Murphy, Emma Brunskill, and the anonymous reviewers for their detailed and helpful comments, aswell as Philip Thomas for an independent implementationand verification of the algorithm.
Most of this work was done during Nan Jiang’s internshipin Microsoft Research. The work was partially supported
by NSF grant IIS 1319365 for Nan Jiang in University ofMichigan. Any opinions, findings, conclusions, or recommendations expressed here are those of the authors and do
not necessarily reflect the views of the sponsors.

References
Bertsekas, Dimitri P and Tsitsiklis, John N. Neuro-Dynamic
Programming (Optimization and Neural Computation
Series, 3). Athena Scientific, 1996.
Bottou, Léon, Peters, Jonas, Quiñonero-Candela, Joaquin,Charles, Denis Xavier, Chickering, D. Max, Portugaly,
Elon, Ray, Dipankar, Simard, Patrice, and Snelson, Ed.
Counterfactual Reasoning and Learning Systems: The
Example of Computational Advertising. Journal of Machine Learning Research, 14:3207–3260, 2013.
Dann, Christoph, Neumann, Gerhard, and Peters, Jan. Policy evaluation with temporal differences: A survey andcomparison. The Journal of Machine Learning Research,
15(1):809–883, 2014.
Dudı́k, Miroslav, Langford, John, and Li, Lihong. Doubly
Robust Policy Evaluation and Learning. In Proceedings ofthe 28th International Conference on Machine Learning,pp. 1097–1104, 2011.
Farahmand, Amir-massoud and Szepesvári, Csaba. Modelselection in reinforcement learning. Machine learning,85(3):299–332, 2011.

Hirano, Keisuke, Imbens, Guido W., and Ridder, Geert.
Efficient estimation of average treatment effects using
the estimated propensity score. Econometrica, 71(4):1161–1189, 2003.
Holland, Paul W. Statistics and causal inference. Journalof the American Statistical Association, 81(6):945–960,
1986.
Jiang, Nan, Kulesza, Alex, and Singh, Satinder. Abstraction
Selection in Model-based Reinforcement Learning. In
Proceedings of the 32nd International Conference on
Machine Learning, pp. 179–188, 2015.
Jong, Nicholas K and Stone, Peter. Model-based function
approximation in reinforcement learning. In Proceedings of the 6th International Conference on Autonomous
Agents and Multiagent Systems, pp. 95, 2007.
Kakade, Sham and Langford, John. Approximately Optimal
Approximate Reinforcement Learning. In Proceedings ofthe 19th International Conference on Machine Learning,volume 2, pp. 267–274, 2002.
Kocsis, Levente and Szepesvári, Csaba. Bandit based montecarlo planning. In Machine Learning: ECML 2006, pp.
282–293. Springer Berlin Heidelberg, 2006.
Li, Lihong, Chu, Wei, Langford, John, and Wang, Xuanhui.
Unbiased Offline Evaluation of Contextual-bandit-based
News Article Recommendation Algorithms. In Proceedings of the 4th International Conference on Web Searchand Data Mining, pp. 297–306, 2011.
Li, Lihong, Munos, Remi, and Szepesvári, Csaba. Toward
minimax off-policy value estimation. In Proceedingsof the Eighteenth International Conference on Artificial
Intelligence and Statistics (AISTATS-15), pp. 608–616,
2015a.
Li, Xiujun, Li, Lihong, Gao, Jianfeng, He, Xiaodong, Chen,
Jianshu, Deng, Li, and He, Ji. Recurrent reinforcement
learning: A hybrid approach, 2015b. arXiv:1509.03044.

Fonteneau, Raphael, Murphy, Susan A., Wehenkel, Louis,
and Ernst, Damien. Batch mode reinforcement learning
based on the synthesis of artificial trajectories. Annals of
Operations Research, 208(1):383–416, 2013.

Mandel, Travis, Liu, Yun-En, Levine, Sergey, Brunskill,
Emma, and Popovic, Zoran. Offline policy evaluation
across representations with applications to educational
games. In Proceedings of the 13th International Conference on Autonomous Agents and Multi-Agent Systems, pp.
1077–1084, 2014.

Grünewälder, S, Lever, G, Baldassarre, L, Pontil, M, andGretton, A. Modelling transition dynamics in MDPs
with RKHS embeddings. In Proceedings of the 29th
International Conference on Machine Learning, pp. 535–
542, 2012.

Mannor, Shie, Simester, Duncan, Sun, Peng, and Tsitsiklis, John N. Bias and variance approximation in valuefunction estimates. Management Science, 53(2):308–322,
2007.

Hettich, S. and Bay, S. D. The UCI KDD Archive. http://kdd.ics.uci.edu, 1999.

Marivate, Vukosi N. Improved Empirical Methods in
Reinforcement-Learning Evaluation. PhD thesis, Rutgers University, New Brunswick, NJ, 2015.

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Moore Jr, Terrence Joseph. A theory of Cramer-Rao bounds
for constrained parametric models. PhD thesis, University of Maryland, College Park, 2010.
Murphy, Susan A., van der Laan, Mark, and Robins,
James M. Marginal Mean Models for Dynamic Regimes.
Journal of the American Statistical Association, 96(456):
1410–1423, 2001.
Ormoneit, Dirk and Sen, Śaunak. Kernel-based reinforcement learning. Machine learning, 49(2-3):161–178,
2002.
Paduraru, Cosmin. Off-policy Evaluation in Markov Decision Processes. PhD thesis, McGill University, 2013.
Pearl, Judea. Causality: Models, Reasoning, and Inference.
Cambridge University Press, 2nd edition, 2009. ISBN
052189560X.
Pirotta, Matteo, Restelli, Marcello, Pecorino, Alessio, andCalandriello, Daniele. Safe policy iteration. In Proceedings of the 30th International Conference on Machine
Learning, number 3, pp. 307–317, 2013.
Precup, Doina. Temporal abstraction in reinforcement learning. PhD thesis, University of Massachusetts Amherst,
2000.
Precup, Doina, Sutton, Richard S., and Singh, Satinder P.
Eligibility Traces for Off-Policy Policy Evaluation. In
Proceedings of the 17th International Conference on Machine Learning, pp. 759–766, 2000.
Precup, Doina, Sutton, Richard S., and Dasgupta, Sanjoy.
Off-Policy Temporal-Difference Learning with Funtion
Approximation. In Proceedings of the 18th International
Conference on Machine Learning, pp. 417–424, 2001.
Rotnitzky, Andrea and Robins, James M. Semiparametric regression estimation in the presence of dependent
censoring. Biometrika, 82(4):805–820, 1995.
Singh, Satinder P and Sutton, Richard S. Reinforcement
learning with replacing eligibility traces. Machine learning, 22(1-3):123–158, 1996.
Sutton, Richard S. and Barto, Andrew G. Reinforcement
Learning: An Introduction. MIT Press, Cambridge, MA,
March 1998. ISBN 0-262-19398-1.
Sutton, Richard S., Mahmood, Ashique Rupam, andWhite, Martha. An emphatic approach to the problem of off-policy temporal-difference learning. CoRR
abs/1503.04269, 2015.
Thomas, Philip. Safe Reinforcement Learning. PhD thesis,
University of Massachusetts Amherst, 2015.

Thomas, Philip and Brunskill, Emma. Data-Efficient OffPolicy Policy Evaluation for Reinforcement Learning.
In Proceedings of the 33rd International Conference on
Machine Learning, 2016.
Thomas, Philip, Theocharous, Georgios, and Ghavamzadeh,
Mohammad. High Confidence Off-Policy Evaluation. In
Proceedings of the 29th AAAI Conference on Artificial
Intelligence, 2015a.
Thomas, Philip, Theocharous, Georgios, and Ghavamzadeh,
Mohammad. High Confidence Policy Improvement. In
Proceedings of the 32nd International Conference on
Machine Learning, pp. 2380–2388, 2015b.

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

A. Proof of Theorem 1
0=
Proof. For the base case t = H + 1, since VDR
V (sH+1 ) = 0, it is obvious that at the (H + 1)-th step
the estimator is unbiased with 0 variance, and the theorem
holds. For the inductive step, suppose the theorem holds forstep t + 1. At time step t, we have: H+1−t 
Vt VDRh i  2
H+1−t 2= Et VDR− Et V (st )
h
 2
H−t
b t , at )= Et Vb (st ) + ρt rt + γVDR
− Q(s
i


− V (st )2 + Vt V (st )hb t , at ) + Vb (st )= Et ρt Q(st , at ) − ρt Q(s
i
 2
H−t
+ ρt rt + γVDR
− Q(st , at )− V (st )2+ Vt V (st )h= Et − ρt ∆(st , at ) + Vb (st ) + ρt (rt − R(st , at ))

2
H−t
+ ρt γ VDR− Et+1 V (st+1 )i− V (st )2 + Vt V (st )
(15)
h h
ii
2
= Et Et − ρt ∆(st , at ) + Vb (st ) − V (st )2 st
h

i


+ Et Et+1 ρ2t (rt − R(st , at ))2 + Vt V (st )hh2 ii
H−t− Et+1 V (st+1 )+ Et Et+1 ρt γ VDR
h 
h
i
 i
= Et Vt − ρt ∆(st , at ) + Vb (st ) st + Et ρ2t Vt+1 rt
h
 H−t
i


+ Et ρ2t γ 2 V VDR
st , at + Vt V (st )
h 
h
i
 i
= Et Vt ρt ∆(st , at ) st + Et ρ2t Vt+1 rth H−t i
+ Et ρ2t γ 2 Vt+1 VDR+ Vt V (st ) .

This completes the proof. Note that from Eqn.(15) to thenext step, we have used the fact that conditioned
on

 st
H−t
and at , rt − R(st , at ) and VDR− Et+1 V (st+1 ) are
independent and have zero means, and all the other terms
are constants. Therefore, the square of the sum equals thesum of squares in expectation.

B. Bias of DR-v2
Proof of Proposition 1. Let VDR-v2’ denote Eqn.(12) withapproximation Pb = P . Since VDR-v2 is unbiased, the bias of
VDR-v2’ is then the expectation of VDR-v2’ − VDR-v2 . Define
h
i
H+1−t
H+1−t
βt = Et VDR-v2’− VDR-v2.
Then, β1 is the bias we try to quantify, and is a constant. In general, βt is a random variable that depends

on s1 , a1 , . . . , st−1 , at−1 . Now we have
h

H−t
H−t
βt = Et ρt γ VDR-v2’− VDR-v2− ρt γ Vb (st+1 )
h

i

h

!
i
Pb(st+1 |st , at )−1
P (st+1 |st , at )= Et ρt γβt+1 − Et ρt γ Vb (st+1 )!
iPb(st+1 |st , at )−1 .
P (st+1 |st , at )In the second term of the last expression, the expectation istaken over the randomness of at and st+1 ; we keep at as arandom variable and integrate out st+1 , and get!
ihb(st+1 |st , at )P
Et ρt γ Vb (st+1 )−1P (st+1 |st , at )!
hhii
Pb(st+1 |st , at )b
= Et Et+1 ρt γ V (st+1 )−1P (st+1 |st , at )!
hiXb(s0 |st , at )P00
P (s |st , at )Vb (s )= Et ρt γ−1
0
P (s |st , at )
s0
h

i
X
= Et ρt γ
Vb (s0 ) Pb(s0 |st , at ) − P (s0 |st , at ) .
s0

Recall that the expectation of the importance ratio is always
1, hencehiβt ≤ Et ρt γ (βt+1 + Vmax )hi= Et ρt γβt+1 + γVmax .
With an abuse of notation, we reuse βt as its maximal absolute magnitude over all sample paths s1 , a1 , . . . , st−1 , at−1 .
Clearly we have βH+1 = 0, andβt ≤ γ(βt+1 + Vmax ).
PHHence, β1 ≤ Vmax t=1 γ t .

C. Cramer-Rao bound for discrete DAG
MDPs
Here, we prove a lower bound for the relaxed setting where
the MDP is a layered Directed Acyclic Graph instead of atree. In such MDPs, the regions of the state space reachable
in different time steps are disjoint (just as tree MDPs), buttrajectories that separate in early steps can reunion at a samestate later.
Definition 2 (Discrete DAG MDP). An MDP is a discrete
Directed Acyclic Graph (DAG) MDP if:• The state space and the action space are finite.
• For any s ∈ S, there exists a unique t ∈ N such that,
maxπ:S→A P (st = s π) > 0. In other words, a state
only occurs at a particular time step.
• As a simplification, we assume γ = 1, and non-zerorewards only occur at the end of each H-step long tra-

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

jectory. We use an additional state sH+1 to encode thereward randomness so that reward function R(sH+1 )is deterministic and the domain can be solely parameterized by transition probabilities.
Theorem 3. For discrete DAG MDPs, the variance of any
unbiased estimator is lower bounded by
H+1
X
t=1

2

i
t−1 , at−1 )
V
V
(s
)
,
t
t
P0 (st−1 , at−1 )2

h P (sE1where for trajectory τ ,P0 (τ ) = µ(s1 )π0 (a1 |s1 )P (s2 |s1 , a1 ) . . . P (sH+1 |sH , aH ),and P0 (st , at ) is its marginal probability; P1 (·) is similarly
defined for π1 .
Remark Compared to Theorem 2, the cumulative importance ratio ρ1:t−1 is replaced by the state-action occupancy ratio P1 (st−1 , at−1 )/P0 (st−1 , at−1 ) in Theorem 3.
The two ratios are equal when each state can only bereached  by a unique sample path. In general,how2
2
ever,
E
P
(s
,
a
)
/P
(s
,
a
)
V
V
(s
)
≤
1 t−1 t−1
0 t−1 t−1tt
 2E ρ1:t−1 Vt V (st ) , hence DAG MDPs are easier thantree MDPs for off-policy value evaluation.
Below we give the proof of Theorem 3, which is almost
identical to the proof of Theorem 2.

Proof of Theorem 3. We parameterize the MDP by µ(s1 )and P (st+1 |st , at ) for t = 1, . . . , H. For convenience
we will treat µ(s1 ) as P (s1 |∅), so all the parameters
can be represented as P (st+1 |st , at ) (for t = 0 there
is a single s0 and a). These parameters are subject
to the normalization constraints that have to be taken
into considerationin the Cramer-Rao bound, namely
P∀t, st , at , st+1 P (st+1 |st , at ) = 1.


 
1···1
1


1
1
·
·
·
1


 
(16)

 θ =  .. 
..


.
.
1···1
1
where θst ,at ,st+1 = P (o|st , at ). The matrix on the left iseffectively the Jacobian of the constraints, which we denote
as F . We index its rows by (st , at ), so F(st ,at ),(st ,at ,st+1 ) =1 and other entries are 0. Let U be a matrix whose column
vectors consist an orthonormal basis for the null space of F .
From Moore Jr (2010, Eqn. (3.3) and Corollary 3.10), we
have the Constrained Cramer-Rao Bound (CCRB) being2
2

In fact, existing literature on Contrained Cramer-Rao Bound
does not deal with the situation where the unconstrained parameters break the normalization constraints (which we are facing).
However, this can be easily
P tackled by changing the model slightly
to P (o|h, a) = θhao / o0 θhao0 , which resolves the issue andgives the same result.

(the dependence on θ in all terms are omitted):
KU (U > IU )−1 U > K > ,(17)

where I is the Fisher Information Matrix (FIM), and K is
the Jacobian of the quantity we want to estimate; they arecomputed below. We start with I, which ish  ∂ log P (τ )   ∂ log P (τ ) > i
0
0
I=E
.
(18)
∂θ
∂θ
To calculate I, we define a new notation g(τ ), which is avector of indicator functions and g(τ )st ,at ,st+1 = 1 when(st , at , st+1 ) appears in trajectory τ . Using this notation,
we have∂ log P0 (τ )= θ◦−1 ◦ g(τ ),(19)∂θwhere ◦ denotes element-wise power/multiplication. Then
we can rewrite the FIM ashi
I = E [θi−1 θj−1 ]ij ◦ (g(τ )g(τ )> )
= [θi−1 θj−1 ]ij ◦ E (g(τ )g(τ )> ) ,(20)
where [θi−1 θj−1 ]ij is a matrix expressed by its (i, j)-th ele
ment. Now we compute E g(τ )g(τ )> . On the diagonal,
P0 (st ,at )it is P0 (st , at , st+1 ), so the diagonal of I is P (s;t+1 |st ,at )for non-diagonal entries whose row indexing and column
indexing tuples are at the same time step, the value is 0;
in other cases, suppose row is (st , at , st+1 ) and column is
st0 , at0 , st0 +1 , and without loss of generality assume t0 < t,then the entry is P0 (st0 , at0 , st0 +1 , st , at , st+1 ), with the corP (s 0 ,a 0 ,s 0 ,st ,at ,st+1 )responding entries in I being P (s0 0 t |st 0 ,at 0+1=
t +1 tt )P (st+1 |st ,at )P0 (st0 , at0 )P0 (st , at |st0 +1 ).
Then, we calculate (U > IU )−1 . To avoid the difficulty of
taking inverse of this non-diagonal matrix, we apply thefollowing trick to diagonalize I: note that for any matrix X
with matching dimensions,
U > IU = U > (F > X > + I + XF )U,(21)

because by definition U is orthogonal to F . We can design
X so that D = F > X > + I + XF is a diagonal matrix,
and D(st ,at ,st+1 ),(st ,at ,st+1 ) = I(st ,at ,st+1 ),(st ,at ,st+1 ) =P0 (st ,at )This is achieved by having XF elimiP (st+1 |st ,at ) .
nate all the non-diagonal entries of I in the upper triangle without touching anything on the diagonal or below,
and by symmetry F > X > will deal with the lower triangle. The particular X we take is X(st0 ,at0 ,st0 +1 ),(st ,at ) =−P0 (st0 , at0 )P0 (st , at |st0 +1 )I(t0 < t), and it is not hard toverify that this construction diagonalizes I.
With the diagonalization trick, we have (U > IU )−1 =(U > DU )−1 . Since CCRB is invariant to the choice ofU , and we observe that the rows of F are orthogonal, wechoose U as follows: let n(st ,at ) be the number of 1’s inF(st ,at ),(·) , and U(st ,at ) be the n(st ,at ) ×(n(st ,at ) −1) matrix

Doubly Robust Off-policy Value Evaluation for Reinforcement Learningwith orthonormal columns in the null space of 1 . . . 1(n(st ,at ) 1’s); finally, we choose U to be a block diagonal matrix U = diag({U(st ,at ) }), where U(st ,at ) ’s are
the diagonal blocks, and it is easy to verify that U iscolumn orthonormal and F U = 0. Similarly, we write
D = diag({D(st ,at ) }) where D(st ,at ) is a diagonal matrix
with (D(st ,at ) )st+1 ,st+1 = P0 (st , at )/P (st+1 |st , at ), andU (U > IU )−1 U > = U (U > DU )−1 U >>= U (diag({U(s})diag({D(st ,at ) })diag({U(st ,at ) }))−1 U
t ,at )
−1>
= U diag({ U(sD(st ,at ) U(st ,at )})Ut ,at )
−1 >>= diag({U(st ,at ) U(sD(st ,at ) U(st ,at )U(st ,at ) }).
t ,at )
(22)

Notice that each block in Eqn.(22) is simply 1/P0 (st , at )times the CCRB of a multinomial distribution P (·|st , at ).
The CCRB of a multinomial distribution p can be easily computed by an alternative formula (Moore Jr, 2010,
Eqn. (3.12))), which gives diag(p) − pp> , so we have,−1 >>U(st ,at ) U(sD(st ,at ) U(st ,at )U(st ,at )t ,at )=diag(P (·|st , at )) − P (·|st , at )P (·|st , at )>.
P0 (st , at )(23)

We then calculate K. Recall that we want to estimateXX
v = v π1 ,H =µ(s1 )
π1 (a1 |s1 ) . . .
s1

X

a1

P (sH+1 |sH , aH )R(sH+1 ) ,

(24)

sH+1

and its Jacobian is K=(∂v/∂θt )> , with
K(st ,at ,st+1 ) = P1 (st , at )V (st+1 ), where P1 (τ ) =µ(s1 )π1 (a1 ) . . . P (sH+1 |sH , aH ) and P1 (st , at ) is themarginal probability.
Finally, putting all the pieces together, we have Eqn.(17)equal toX P1 (st , at )2  X
P (st+1 |st , at )V (st+1 )2
P
(s
,
a
)
0
t
t
st ,a
st+1
X
2 
−
P (st+1 |st , at )V (st+1 )
st+1

=

H X
X

P0 (st , at )t=0 st
P1 (st , at )2 
V V (st+1 ) st , a
2
P0 (st , at )Hh P (s , a )2
X

i
1 t t
=
E
V
V
(s
)
t+1
t+1
P0 (st , at )2
t=0

=

H+1
X
t=1

2

i
t−1 , at−1 )Vt V (st ) .
2
P0 (st−1 , at−1 )h P (sE

1

D. Experiment Details
Here, we provide full details on the experiments that areomitted in the main paper due to space limit.
D.1. Mountain Car
Domain Description Mountain car is a widely usedbenchmark problem for RL with a 2-dimensional continuous state space (position and velocity) and deterministic dynamics (Singh & Sutton, 1996). The state space is[−1.2, 0.6] × [−0.07, 0.07], and there are 3 discrete actions.
The agent receives −1 reward every time step with a discount factor 0.99, and an episode terminates when the first
dimension of state reaches the right boundary. The initialstate distribution is set to uniformly random, and behavior
policy is uniformly random over the 3 actions. The typicalhorizon for this problem is 400, which can be too large for
IS and its variants, therefore we accelerate the dynamics
such that given (s, a), the next state s0 is obtained by callingthe original transition function 4 times holding a fixed, andwe set the horizon to 100. A similar modification was taken
by Thomas (2015), where every 20 steps are compressed as
one step.
Model Construction The model we construct for thisdomain uses a simple discretization (state aggregation): thetwo state variables are multiplied by 26 and 28 respectively
and the rounded integers are treated as the abstract state. We
then estimate the model parameters from data using a tabular
approach. Unseen aggregated state-action pairs are assumed
to have reward Rmin = −1 and a self-loop transition. Boththe models that produces πtrain and that used for off-policy
evaluation are constructed in the same way.
Data sizes & other details
The dataset sizes are|Dtrain | = 2000 and |Deval | = 5000. We split Deval suchthat Dtest ∈ {10, 100, 1000, 2000, 3000, 4000, 4900, 4990}.
DR-bsl uses the step-dependent constant function
H−t+1)
b t , at ) = Rmin (1 − γ
Q(s
.
1−γ
Since the estimators in the IS family typically has ahighly skewed distribution, the estimates can occasionally go largely out of range, and we crop such outliers in[Vmin , Vmax ] to ensure that we can get statistically significant experiment results within a reasonable number of simulations. The same treatment is also applied to the experiment
on Sailing.

D.2. Sailing
Domain Description The sailing domain (Kocsis &Szepesvári, 2006) is a stochastic shortest-path problem,
where the agent sails on a grid (in our experiment, a mapof size 10 × 10) with wind blowing in random directions,Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

aiming at the terminal location on the top-right corner. The
state is represented by 4 integer variables, representing either location or direction. At each step, the agent chooses tomove in one of the 8 directions, (moving against the wind or
running off the grid is prohibited), and receives a negative reward that depends on moving direction, wind
√ direction, andother factors, ranging from Rmin = −3−4 2 to Rmax = 0(absorbing). The problem is non-discounting, and we use
γ = 0.99 for easy convergence when computing πtrain .
Model Construction We apply Kernel-based Reinforcement Learning (Ormoneit & Sen, 2002) and supply asmoothing kernel in the joint space of states and actions.
The kernel we use takes the form exp(−k · k/b), where k · kis the `2 -distance in S × A,3 and b is the kernel bandwidth,
set to 0.25.
Data sizes & other details The data sizes are |Dtrain | =1000 and |Deval | = 2500, and we split Deval such that
Dtest ∈ {5, 50, 500, 1000, 1500, 2000, 2450, 2495}. DRbsl uses the step-dependent constant function
H−t+1

b t , at ) = Rmin 1 − γ
,
Q(s
2
1−γ
for the reason that in Sail Rmin is rarely reached hence too
pessimistic as a rough estimate of the magnitude of reward
obtained per step.
D.3. KDD Cup 1998 Donation Dataset
Here are further details for experiments with the KDD donation dataset:
1. The size of dataset generated from the simulator for offpolicy evaluation is equal to that of the true dataset (theone we use to fit the simulator at the very beginning;
there are 3754 trajectories in that dataset).
2. The policy πtrain is generated by training a recurrent
neural network on the original data to fit a Q-valuefunction (Li et al., 2015b).
3. Since there are many possible next-states for eachstate-action pair, for computational efficiency we use ab using thesparse-sample approach when estimating Q
c: for each (s, a), we randomly sample
fitted model M
several next-states from Pb(·|s, a), and cache them as
a particle representation for the next-state distribution.
The number of particles is set to 5 which is enough toensure high accuracy.

3
The difference of two directions is defined as the angle between them (in degrees) divided by 45◦ . For computational efficiency, the kernel function is cropped to 0 whenever two stateaction pairs deviate more than 1 in any of the dimensions.