A New Doubly Robust Policy Estimator on Infinite Horizon
Reinforcement Learning

Ziyang Tang * 1 Yihao Feng * 1 Qiang Liu 1

Abstract
Recently infinite horizon off-policy evaluation
method based on estimation of density ratio has
been proposed (Liu et al., 2018). Before that doubly robust estimator is the strongest baseline in
off-policy evaluation in finite horizon. A natural
question is if we can apply doubly robust method
in infinite horizon setting. This paper answer thatquestion and reveal an interesting connection between density ratio function and value function.
We provide both theoretical and empirical result
to show that our method yields significantly advantage over previous method.

1. Introduction
Reinforcement learning (RL) (Sutton & Barto, 1998) is oneof the most successful approaches to artificial intelligence,and has found successful applications in robotics, games,
dialogue systems, and recommendation systems, among others. One of the key problems in RL is policy evaluation:
given a fixed policy, estimate the average reward garneredby an agent that runs this policy in the environment. In thispaper, we consider the off-policy estimation problem, inwhich we want to estimate the expected reward of a given
target policy with samples collected by a different behavior
policy. This problem is of great practical importance inmany application domains where deploying a new policy
can be costly or risky, such as medical treatments (Murphy
et al., 2001), econometrics (Hirano et al., 2003), recommender systems (Li et al., 2011), education (Mandel et al.,2014), Web search (Li et al., 2015), advertising and marketing (Bottou et al., 2013; Chapelle et al., 2014; Tang et al.,2013; Thomas et al., 2017). It can also be used as a key
component for developing efficient off-policy policy optimization algorithms (Dudík et al., 2011; Jiang & Li, 2016;
Li et al., 2015; Thomas & Brunskill, 2016).
*
Equal contribution 1 Department of Computer Science,
UT Austin, TX, USA. Correspondence to: Ziyang Tang<ztang@cs.utexas.edu>, Yihao Feng <yihao@cs.utexas.edu>.

Real-world Sequential Decision Making workshop at ICML 2019.
Copyright 2019 by the author(s).

Most previous off-policy estimation methods are based on
importance sampling(IS) for trajectory (e.g., Liu, 2001). A
major limitation, however, is that this approach can become
inaccurate due to high variance introduced by the long trajectory. Indeed, most existing IS-based estimators computethe weight as the product of the importance ratios of many
steps in the trajectory. To alleviate the high variance problem, researcher introduce variance reduction technique forIS-based estimators. The most famous one is Doubly Robust
estimator (Jiang & Li, 2015).
Recently, Liu et al. (2018) proposes an estimation problem
for infinite horizon off-policy evaluation. The method isbased on estimate the density ratio between stationary distribution, rather than trajectory, which avoid the cumulative
product of across many steps in the trajectory, which substantially decrease its variance and eliminate the estimator’s
dependence on the horizon.
However, Liu et al. (2018) does not provide any variancereduction trick for its estimator. A natural question is to
ask if there is a easy way to do variance reduction for theinfinite horizon density ratio estimator.
In this paper, we develop a new doubly robust estimator
based on the infinite horizon density ratio estimator. We findinteresting connection between the density ratio function
and value function, and use them to construct a doubly
robust estimator to reduce the variance. Our method yields
a significant advantage compare to the previous estimator.

2. Background2.1. Off-Policy Evaluation
Consider a Markov decision process(MDP) M =hS, A, r, T i with state space S, action space A, reward
function r, and transition probability function T . The average discounted reward for a target policy π is definedas:PT
γ t rt],Rπ := lim Eτ ∼π [ Pt=0
T
t
T →∞
t=0 γ
where τ = {si , ai , ri }1≤i≤n is trajectory with state, action,
reward simulated in MDP under policy π.

A New Doubly Robust Policy Estimator on Infinite Horizon Reinforcement Learning

Denoted dπ,t (·) as average visitation of st in time step t, we
can define the stationary distribution, or sometimes we callit discounted average visitation, dπ as:∞XPTdπ (s) := lim

T →∞tt=0 γ dπ,t (s)= (1 − γ)γ t dπ,t (s).
PT
t
γ
t=0
t=0

Actually this can be viewed as a stochastic gradient descent
under the following objective functional:
min D[V ] := Es∼dπ0 [(BV (s))2 ].
V(6)

In this objective, the gradient with respect to V (s) is2(V (s) − (r + γV (s0 ))) which leads to equation (5).

HereP∞ (1t − γ) is the normalization factor introduced by
t=0 γ .

Another way is to introduce a test function to the objective
and let the functional G as:

Using stationary distribution we can rewrite our average
discounted reward as:

G[f, V ] := Es∼dπ0 [f (s)BV (s)].

Rπ = Es∼dπ ,a∼π(·|s) [r(s, a)]

(1)

(7)

We know that if V = V π , G[f, V ] = 0 for all test functionf.
Now we can redefine the objective for solving V as,

The Off-Policy evaluation problem gives you data{si , ai , s0i , ri } collected under a behavior policy π0 (a|s),
and we want to estimate the average discounted reward foranother target policy π(a|s).
2.2. Value function Estimator
The value function for policy π is defined as the expecteddiscounted reward sum start from a certain state:V π (s) = Eτ ∼π [∞X

γ t rt |s = s0 ],

f ∈F

(8)

When the function space F = {Es∼dπ0 [f (s)2 ] ≤ 1} is in l2 ,e is equivalent to the previous
the new objective function D
objective function D.
Using V π to estimate Rπ Suppose now we have alreadyget an estimation of V , we could estimate Rπ as a functional:
Rval [V ] = (1 − γ)Es∼d0 [V (s)].

(2)

(9)

π

If V = V , the estimator is unbiased.

t=0

where τ =policy π.

D̃[V ] := max G[f, V ].

{(s0 , a0 , r0 )}∞i=0 is a trajectories draw from

Using the definition we can derive a Bellman equation for
V π:
V π (s) = Ea,s0 |s∼π [r(s, a) + γV (s0 )], ∀s ∈ S(3)

If we can evaluate the value function accurately, we can use
it to estimate the average discounted reward:

2.3. Density Ratio Estimation
The density ratio is defined as the ratio between stationary
distribution of π and π0 :wπ/π0 (s) =dπ (s).
dπ0 (s)(10)

Notice that if we get the true density ratio, we can estimate
Rπ using π0 samples with importance sampling method:
Rπ =Es∼dπ ,a∼π(·|s) [r(s, a)]∞X
Rπ =(1 − γ)Eτ ∼π [γ t rt ]=Es∼dπ0 ,a∼π0 (·|s) [wπ/π0 (s)t=0∞X=(1 − γ)Es∼d0 [Eτ ∼π [γ t rt |s0 = s]]t=0=(1 − γ)Es∼d0 [V π (s)].
Solving V π If we define an Temporal Difference(TD)(Sutton, 1988) target over function f as:
Bf (s) = f (s) − Ea,s0 |s∼π [r(s, a) + γf (s0 )].

(4)

We often use the TD method to solve V π using the following
fixed point recursion:0

V (s) ← V (s) + α(r + γV (s ) − V (s)).

(5)π(a|s)
r(s, a)].
π0 (a|s)(11)

Solving density ratio wπ/π0 Liu et al. (2018) proposes amethod to estimate the density ratio between distribution
over stationary on state, using a Bellman like recursive
equation
We skip the derivation for how we get those equation, butjust state the result. The estimation of density ratio w can be
written as a optimization problem on the following objectivefunctional:
L[w, f ] := γE(s,a,s0 )∼dπ0 [(w(s)βπ/π0 (a|s)−w(s0 ))f (s0 )] + (1 − γ)Es∼d0 [(1 − w(s))f (s)].

A New Doubly Robust Policy Estimator on Infinite Horizon Reinforcement Learning

We further define D[w] to be the the largest value of L[w, f ]among all the test function f , our goal is to find w minimize
D[w]:
min D[w] := max L[w, f ]2 ,
(12)
w

f ∈F

where F is the space of test function f , typically taken to
be Reproducing Kernel Hilbert Space(RKHS).
Estimate Rπ using w Suppose now we have already get
an estimation of w, we could estimate Rπ as a functional:
Rden [w] = E(s,a)∼dπ0 [w(s)βπ/π0 (a|s)r(s, a)](13)where βπ/π0 (a|s) = ππ(a|s)
for short.
0 (a|s)2.4. Connection
Liu et al. (2018) also proposes an interesting connection forL(w, f ) and the value function V π for the estimation:

Algorithm 1 A New Doubly Robust Estimator
Input: History transition data D = {si , ai , s0i , ri }1≤i≤nfrom policy π0 ; a target policy π for which we want toestimate the expected reward;
Use D[V ] in Equation (5) as objective to train a goodvalue function V under some parametric space.
Use D[w] in Equation (12) as objective to train a good
density ratio w under some parametric space.
Use Rdoubly [w, V ] in (16) to estimate Rπ using sample
from D.
Notice that if V = V π , we can use R[V ] + G(V, f ) to as anunbiased estimator, since G(V, f ) = 0 for all test function
f . Similarly, if w = wπ/π0 , we can use R[w] + L(w, f ) as
an unbiased estimator.
Now we connect them together and define a new bivariate
functional C[w, V ] as:C[w, V ] := Es∼dπ0 [w(s)(V (s)−γEs0 ,a|s∼π0 [βπ/π0 (a|s)V (s0 )])].

Theorem 2.1. Define Rden [w] to be the reward estimate
using estimated density ratio w(s) (which may not equal thetrue ratio wπ/π0 ) and infinite number of trajectories from
dπ0 , that is,

Now we show our key observation that this connection
functional can connect the density ratio and value function
together.

Rden [w] := E(s,a,s0 )∼dπ0 [w(s)βπ/π0 (a|s)r(s, a)] .

Lemma 3.1. Compare C[w, V ] with G[w, V ], we have:

Assume w is properly normalized such that Es∼dπ0 [w(s)] =1, we have L[w, V π ] = Rπ −Rden [w]. Therefore, if ±V π ∈F, we have |Rden [w] − Rπ | ≤ maxf ∈F L[w, f ].

C[w, V ] = G[w, V ] + Rden [w]Under this theorem, if V π ∈ F we can safely use R[w] asestimation of Rπ .

3. Doubly Robust Estimator(14)

Proof. Collect the term inside expectation we can easily get
the equation.
Lemma 3.2. Compare C[w, V ] with L[w, V ], we have:C[w, V ] = Rval [V ] − L[w, V ](15)

Doubly robust estimator is first proposed to solve Causal
effect (Funk et al., 2011) as an estimator combining Inverse Propensity Score(IPS) estimator and Regression modeling(Reg) estimator.

Proof. Rval [V ] = (1 − γ)Es∼d0 [V (s)]. Rewrite L[w, V ]using the lemma (5) and equation (25) in (Liu et al., 2018)
we have (or simply use dπ0 = (1 − γ)d0 + γT π0 dπ0 trick.):
L[w, V ] =γE(s,a,s0 )∼dπ0 w(s)βπ/π0 (a|s) − w(s0 ) V (s0 ) +Jiang & Li (2015) introduce the idea of doubly robust estimator into off policy evaluation in Reinforcement Learning.
It incorporates an approximate value function as a control
variate to reduce the variance of importance sampling estimator.

(1 − γ)Es∼d0 [(1 − w(s))V (s)]=γE(s,a,s0 )∼dπ0 w(s)βπ/π0 (a|s) V (s0 ) −Inspired by this method and Liu et al. (2018)’s theorem
about the connection for density ratio wπ/π0 and value function V π , we come up with an idea to use a new doubly
robust estimator as our infinite horizon off policy estimator.
Suppose we have already get the our function approximation
for density w and value function V , where w is close towπ/π0 and V is close to value function for policy π V π .

γEs0 ∼T π0 dπ0 [w(s0 )V (s0 )] + (1 − γ)Es∼d0 [(1 − w(s))V (s)]=γE(s,a,s0 )∼dπ0 w(s)βπ/π0 (a|s) V (s0 ) − Es∼dπ0 [w(s)V (s)]+ (1 − γ)Es∼d0 [w(s)V (s)] + (1 − γ)Es∼d0 [(1 − w(s))V (s)]= − Es∼dπ0 [w(s)(V (s) − γβπ/π0 (a|s)V (s0 ))]+ (1 − γ)Es∼d0 [V (s)]= − C[w, V ] + Rval [V ].

(a) Pendulum-v0

1.5

1.5

0.5

0.5
log10 MSE

log10 MSE

A New Doubly Robust Policy Estimator on Infinite Horizon Reinforcement Learning

0.5
1.5

2.5
10
20
40 60 100 150(b) # of Trajectories (n), T = 500

0.5
1.5
2.5
10
20
40 60 100 150(c) # of Trajectories (n), T = 1000

Doubly Robust
Density Ratio
Value Estimate
Naive Averge
oracleFigure 1. Result on Pendulum-v0 environment. (b)-(c) show the results in the discount case with γ = 0.99, (b)3.1. Doubly Robust Estimator of Rπ
Now we use the following estimator to estimate Rπ :Rdoubly [w, V ] = Rden [w] + Rval [V ] − C[w, V ](16)

Our main theorem tells us that if either V or w is estimatedcorrectly, the doubly robust estimator is unbiased.
Theorem 3.3. If w = wπ/π0 or V = V π , Rdoubly [w, V ] isan unbiased estimator of Rπ .
Proof. If w = wπ/π0 , Rden [w] = Rπ , Rval [V ] −C(w, V ) = L[w, V ] = 0. If V = V π , Rval [V ] = Rπ ,Rden [w] − C[w, V ] = −G[w, V ] = 0.
We can further analyze its variance in future.
3.2. Proposed algorithm
Solve the optimization for value function V and density
ratio w respectively by minimizing D[w] and D[V ], thenuse Rdoubly [w, V ] to estimate Rπ . A detail procedure is
described in Algorithm 1.

4. Experiment4.1. Evaluation on Pendulum
We test Pendulum, which has a continuous state space of R3
and action space of [−2, 2]. The initial state randomly startwith angle from −π to π and a random velocity from −1
to 1. In this environment, we want to control the pendulum
to make it stand up as fast as possible. The policy is taken
to be a truncated Gaussian whose mean is a neural networkof the states and variance a constant. There is no ending
state for this environment, and at each state the reward is
calculated as how much you are close to the stand up status.
We train a near-optimal policy π∗ using REINFORCE and
set it to be the target policy. The behavior policy is set tobe π = (1 − α)π∗ + απ+ , where α is a mixing ratio, andπ+ is another policy from REINFORCE when it has notconverged.

Our results are shown in Figure 1, where we find that our
proposed doubly robust policy evaluation method outperforms density ratio estimation (Liu et al., 2018) and off
policy value estimation methods on two different trajectory
length cases (T = 500 and T = 1000). As is shown in Figure 1, our proposed doubly robust can be accurate as longas either density ratio Rden [w] or value function Rval [V ]estimator is accurate, which can enjoy the benefits of both
estimators in different settings to make the reward estimatorrobust when the samples from target policy is unavailable.

5. Conclusion
In this paper, we develop a new doubly robust estimator
based on the infinite horizon density ratio and off policy
value estimation. Our new proposed doubly robust estimatorcan be accurate as long as one of the estimators are accurate,
which yields a significant advantage comparing to previous
estimators. As future work, we will validate our method
on more complex environments and provide a theoreticalvariance and bias sample analysis.

References
Bottou, L., Peters, J., Quiñonero-Candela, J., Charles, D. X.,
Chickering, D. M., Portugaly, E., Ray, D., Simard, P., andSnelson, E. Counterfactual reasoning and learning systems: The example of computational advertising. Journalof Machine Learning Research, 14:3207–3260, 2013.
Chapelle, O., Manavoglu, E., and Rosales, R. Simple andscalable response prediction for display advertising. ACM
Transactions on Intelligent Systems and Technology, 5(4):61:1–61:34, 2014.
Dudík, M., Langford, J., and Li, L. Doubly robust policy
evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning (ICML), pp.
1097–1104, 2011.
Funk, M. J., Westreich, D., Wiesen, C., Stürmer, T.,
Brookhart, M. A., and Davidian, M. Doubly robust

A New Doubly Robust Policy Estimator on Infinite Horizon Reinforcement Learning

estimation of causal effects. American journal of epidemiology, 173(7):761–767, 2011.

on Information & Knowledge Management (CIKM), pp.
1587–1594, 2013.

Hirano, K., Imbens, G. W., and Ridder, G. Efficient estimation of average treatment effects using the estimatedpropensity score. Econometrica, 71(4):1161–1189, 2003.

Thomas, P. S. and Brunskill, E. Data-efficient off-policy
policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine
Learning (ICML), pp. 2139–2148, 2016.

Jiang, N. and Li, L. Doubly robust off-policy value
evaluation for reinforcement learning. arXiv preprint
arXiv:1511.03722, 2015.
Jiang, N. and Li, L. Doubly robust off-policy evaluation
for reinforcement learning. In Proceedings of the 23rd
International Conference on Machine Learning (ICML),
pp. 652–661, 2016.
Li, L., Chu, W., Langford, J., and Wang, X. Unbiased offline evaluation of contextual-bandit-based news article
recommendation algorithms. In Proceedings of the 4th International Conference on Web Search and Data Mining(WSDM), pp. 297–306, 2011.
Li, L., Chen, S., Gupta, A., and Kleban, J. Counterfactual
analysis of click metrics for search engine optimization:
A case study. In Proceedings of the 24th International
World Wide Web Conference (WWW), Companion Volume,pp. 929–934, 2015.
Liu, J. S. Monte Carlo Strategies in Scientific Computing.
Springer Series in Statistics. Springer-Verlag, 2001. ISBN
0387763694.
Liu, Q., Li, L., Tang, Z., and Zhou, D. Breaking the curseof horizon: Infinite-horizon off-policy estimation. In
Advances in Neural Information Processing Systems, pp.
5361–5371, 2018.
Mandel, T., Liu, Y.-E., Levine, S., Brunskill, E., andPopovic, Z. Offline policy evaluation across representations with applications to educational games. In Proceedings of the 13th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp.
1077–1084, 2014.
Murphy, S. A., van der Laan, M., and Robins, J. M. Marginal
mean models for dynamic regimes. Journal of the American Statistical Association, 96(456):1410–1423, 2001.
Sutton, R. S. Learning to predict by the methods of temporal
differences. Machine learning, 3(1):9–44, 1988.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An
Introduction. MIT Press, Cambridge, MA, March 1998.
ISBN 0-262-19398-1.
Tang, L., Rosales, R., Singh, A., and Agarwal, D. Automatic ad format selection via contextual bandits. In
Proceedings of the 22nd ACM International ConferenceThomas, P. S., Theocharous, G., Ghavamzadeh, M., Durugkar, I., and Brunskill, E. Predictive off-policy policy
evaluation for nonstationary decision problems, with applications to digital marketing. In Proceedings of the 31st
AAAI Conference on Artificial Intelligence (AAAI), pp.
4740–4745, 2017.