summaries: This paper proposes a novel advantage estimate for reinforcement learning based on estimating the extent to which past actions impact the current state. More precisely, the authors train a classifier to predict the action taken k-steps ago from the state at time t, the state at t-k and the time gap k. The idea is that when it is not possible to accurately predict the action, the action choice had no impact on the current state, and thus should not be assigned credit for the current reward, they refer to this as the "independence property" between current action and future states. Based on this idea, the authors introduce a "dependency factor", using the ratio P(s_{t+k},a_{t+k}|s_t,a_t)/P(s_{t+k},a_{t+k}|s_t). They later show that this can be reworked using Bayes theorem into a ratio of the form P(a_t|s_t,s_{t+k})/\pi(a_t|s_t) which is more convenient to estimate. The authors show mathematically that, when the dependency factor is computed with the true probabilities and use to weight each reward in a trajectory, the result is an unbiased advantage estimator. Importantly the expectation, in this case, is taken over trajectories sampled according to the policy pi conditioned only on S_t. This is distinct from the Monte-Carlo estimator which is based only on samples in which A_t, the action whose advantage is being estimated, was selected.

summaries: This paper proposes a new advantage estimator in reinforcement learning based on importance sampling. This form allows for a significantly lower-variance estimator for situations where the current action "stops mattering" to the future state. A control variate, as in Grathwohl et al., is used to combine the importance sampling estimator with the "standard" estimator in a way that is always unbiased and attempts to minimize the overall variance.

summaries: This paper tries to control the variance of advantage function by utilizing the independence property between current action and future states. The practical approach they are using is to learn a dependency model of reward function as a control variate to lower the variance. Using the control variate technique they derive a (maybe complicated) algorithm to update the policy by PPO. Empirical results seems competitive.

abstractText: Most of existing advantage function estimation methods in reinforcement learning suffer from the problem of high variance, which scales unfavorably with the time horizon. To address this challenge, we propose to identify the independence property between current action and future states in environments, which can be further leveraged to effectively reduce the variance of the advantage estimation. In particular, the recognized independence property can be naturally utilized to construct a novel importance sampling advantage estimator with close-to-zero variance even when the Monte-Carlo return signal yields a large variance. To further remove the risk of the high variance introduced by the new estimator, we combine it with existing Monte-Carlo estimator via a reward decomposition model learned by minimizing the estimation variance. Experiments demonstrate that our method achieves higher sample efficiency compared with existing advantage estimation methods in complex environments.

authors:
Shalabh Bhatnagar
Mohammad Ghavamzadeh
Mark Lee
Richard S Sutton

title: Incremental natural actor-critic algorithms. In Advances in neural information processing

authors:
Vincent François-Lavet
Raphael Fonteneau
Damien Ernst

title: How to discount deep reinforcement learning: Towards new dynamic strategies

venue: arXiv preprint arXiv:1512.02011,

authors:
Will Grathwohl
Dami Choi
Yuhuai Wu
Geoff Roeder
David Duvenaud

title: Backpropagation through the void: Optimizing control variates for black-box gradient estimation

venue: arXiv preprint arXiv:1711.00123,

authors:
Josiah P Hanna
Philip S Thomas
Peter Stone
Scott Niekum

title: Data-efficient policy evaluation through behavior policy search

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Nan Jiang
Alex Kulesza
Satinder Singh
Richard Lewis

title: The dependence of effective planning horizon on model accuracy

venue: In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems,

authors:
Hajime Kimura
Shigenobu Kobayashi

title: An analysis of actor-critic algorithms using eligibility traces: reinforcement learning with imperfect value functions

venue: Journal of Japanese Society for Artificial Intelligence,

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

authors:
Qiang Liu
Lihong Li
Ziyang Tang
Dengyong Zhou

title: Breaking the curse of horizon: Infinitehorizon off-policy estimation

venue: In Advances in Neural Information Processing Systems,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learning

venue: arXiv preprint arXiv:1312.5602,

authors:
Volodymyr Mnih
Adria Puigdomenech Badia
Mehdi Mirza
Alex Graves
Timothy Lillicrap
Tim Harley
David Silver
Koray Kavukcuoglu

title: Asynchronous methods for deep reinforcement learning

venue: In International conference on machine learning,

authors:
John Schulman
Sergey Levine
Pieter Abbeel
Michael Jordan
Philipp Moritz

title: Trust region policy optimization

venue: In International Conference on Machine Learning,

authors:
John Schulman
Philipp Moritz
Sergey Levine
Michael Jordan
Pieter Abbeel

title: Highdimensional continuous control using generalized advantage estimation

venue: arXiv preprint arXiv:1506.02438,

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
Richard S Sutton
David A McAllester
Satinder P Singh
Yishay Mansour

title: Policy gradient methods for reinforcement learning with function approximation

venue: In Advances in neural information processing systems,

authors:
Zhongwen Xu
Hado van Hasselt
David Silver

title: Meta-gradient reinforcement learning

venue: arXiv preprint arXiv:1805.09801,

heading: 1 INTRODUCTION

text:
Policy gradient method (Sutton et al., 2000) and its variants have demonstrated their success in solving a variety of sequential decision making tasks, such as games (Mnih et al., 2016) and continuous control (Lillicrap et al., 2015). The large variance associated with vanilla policy gradient estimator has prompted a series of previous works to use advantage function estimation, due to its varianceminimized form (Bhatnagar et al., 2008), to get a stable policy gradient estimation (Mnih et al., 2016; Schulman et al., 2015a;b; 2017). For a policy π and a state-action pair (s, a), all these works estimate the advantage function Aπ(s, a) by subtracting an estimate of the value function V π(s) from the estimate of Q-value Qπ(s, a). The estimation of Qπ(s, a) or V π(s) typically involves a discounted sum of future rewards, which still suffers from the high variance especially when facing the long time horizon.
Meanwhile, in many real-world reinforcement learning applications, we observe that not all future rewards have dependency with the current action. For example, consider a simple multi-round game where at the end of each round of this game, the agent will be assigned a reward, representing whether it wins this round. An episode of the whole game consists of multiple independent rounds. In this example, an action in the current round will not affect the rewards in future rounds, and not all rewards received in future states do contribute to the advantage function of the current action. However, most of existing RL methods (Sutton et al., 2000; Mnih et al., 2013; Schulman et al., 2015b) sum all future rewards to evaluate each action without considering their dependency. By identifying the independence between current action and future states in the environment, we are able to take advantage of such independence to reduce the variance of advantage estimation.
In this paper, we propose Independence-aware Advantage Estimation (IAE), an algorithm that can identify and utilize the independence property between current action and future states. We first introduce a novel advantage estimator that can utilize the independence property by importance sampling. The estimator formalizes a dependency factor Cπ , representing the contribution level of each future reward to advantage function estimation. For those states with no dependency on the current action, there will be a close-to-zero dependency factor Cπ , and the importance sampling estimator can reduce the variance of advantage estimation by ignoring the rewards on these states. For those states with a large dependency factor, the importance sampling estimator will potentially increase variance. In order to take advantage of variance reduction caused by small Cπ while removing the risk of increased variance by large Cπ , we further combine existing Monte-Carlo estimator with the proposed estimator by decomposing the reward into two estimators and learning the optimal
decomposition by minimizing the corresponding estimation variance. Ideally, when facing states with zero dependency on the current action, our model can learn to distribute all the reward into the importance sampling estimator, where the reward can be ignored; when those states yield extremely large Cπ , our model can learn to distribute part of rewards into the Monte-Carlo estimator to reduce the potential high variance caused by importance sampling. Details of our method are described in Section 3, 4 and 5.
Empirically, we show that our estimated advantage function is closer to ground-truth advantage function Aπ than existing advantage estimation methods such as Monte-Carlo and Generalized Advantage Estimation (Schulman et al., 2015b). We also test IAE advantage estimation in policy optimization algorithms, showing that our method outperforms other advantage estimation methods in sample efficiency. Results of our experiments are reported in Section 8.
Our contributions can be summarized as follows:
• As far as we know, we are the first to explore and utilize the independence property between current action and future states in environments to improve advantage estimation. The independence property can help us ignore the unnecessary high variance parts in MonteCarlo estimator which do not contribute to advantage function. • We propose a practical advantage estimation method to identify and utilize the indepen-
dence property in environments, which achieves better performance than other advantage estimation methods in both tabular settings and function approximation settings.

heading: 2 BACKGROUND

heading: 2.1 NOTATIONS & PROBLEM SETTINGS

text:
We consider a finite-horizon Markov Decision Process defined by (S,A, P,R, ρ0, γ, T ), where S is the set of states,A is the finite set of actions, P : S ×A×S → R denotes the transition probability, R : S × A → R denotes the reward function, ρ0 : S → R denotes the distribution of initial state S0, γ ∈ (0, 1] is the discount factor, T is the total time steps. We denote St, At, Rt as the random variable of state, action, reward at time t, and τt := (St, At, Rt, St+1, ..., ST , AT , RT ) as trajectory starting from time t.
We denote π : S × A → R as a stochastic policy, and use the notation of Qπ(st, at), V π(st), Aπ(st, at) as state-action value function, state value function and advantage function respectively. In the following discussions, we will recognize (st, at) as a constant state-action pair whose advantage function needed to be estimated.

heading: 2.2 ADVANTAGE FUNCTION ESTIMATORS

text:
Monte-Carlo estimator ÂMCt of advantage function A π(st, at) is formalized below:
ÂMCt := −Vθ(st) + T−t∑ k=0 γkRt+k,where τt ∼ Pπ(τt|st, at).
Here Vθ(st) denotes the function approximator of value function V π(st). We use τt ∼ Pπ(τt|st, at) to denote that trajectory τt is generated by policy π from st, at.
Some previous work focuses on reducing the variance of ÂMCt at the cost of introducing bias (Schulman et al., 2015b), by using the n-step TD estimator and GAE estimator of advantage function Aπ(st, at):
Â TD(n) t :=  −Vθ(st) + n−1∑ k=0 γkRt+k + γ nVθ(St+n), if n < T − t
ÂMCt , if n ≥ T − t
ÂGAEt := (1− λ) ∞∑ n=0 λnÂ TD(n+1) t ,where τt ∼ Pπ(τt|st, at).

heading: 3 UTILIZING INDEPENDENCE PROPERTY IN ADVANTAGE ESTIMATION

text:
In many cases, we can utilize the independence between current action and future states to avoid unnecessary parts of variance in the Monte-Carlo estimators. Consider the example where we have a current state st whose advantage functions with respect to all actions are needed to be estimated. For a set of st+k which can be reached from st, we have independence property such that the probability Pπ(st+k|st, at) is a constant with respect to at. Although the Monte-Carlo return estimator from st+k may have large variance, it is clear that the return after reaching st+k gives no contribution to Aπ(st, at) in this case.
In this section, we propose a new advantage estimator based on importance sampling, which removes the variance in Monte-Carlo return estimator after st+k by utilizing independence property, exactly as we described above. In later discussions, we will name the proposed estimator as importance sampling advantage estimator.
By importance sampling approach, we present our way to derive Aπ(st, at) into a form which utilizes independence property:
Aπ(st, at) = Eτt∼Pπ(τt|st,at) [ T−t∑ k=0 γkRt+k ] − Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkRt+k ]
= Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkRt+k( Pπ(St+k, At+k|st, at) Pπ(St+k, At+k|st) − 1) ] . (1)
To briefly summarize our derivation, we perform importance sampling in every future time t + k, estimating the discounted reward γkRt+k in distribution Pπ(St+k, At+k|st, at) by sampling on distribution Pπ(St+k, At+k|st). It is worth noting that when k ≥ 1, At+k is independently sampled by St+k, and we are able to omit At+k in the probability ratio.
For the simplicity of discussion, we will use the following definition:
Cπk (st, at, st+k, at+k) := Pπ(st+k, at+k|st, at) Pπ(st+k, at+k|st) − 1. (2)
where we call Cπk (st, at, st+k, at+k) the dependency factor, since the value captures how taking a specific action at changes the probability of reaching a future state-action pair (st+k, at+k). It is clear from equation 1 and equation 2 that future state pair st+k that has dependency factor Cπk (st, at, st+k, at+k) close to 0 has small contribution to A
π(st, at), which further demonstrates that the rewards from independent future states do not contribute to advantage estimation, even if Monte-Carlo return signal has high variance. In practice, we face the challenge to estimate the dependency factor Cπ by data samples. We propose a novel modeling method and a temporal difference training strategy to solve this problem, which is detailed in Section 5.

heading: 4 OPTIMAL COMBINATION WITH MONTE-CARLO ESTIMATOR

text:
The advantage estimation method proposed in section 3 nicely deal with those future rewards which are independent on current action, since we have dependency factor close to zero and further ignore those rewards. However, the importance sampling advantage estimator may badly deal with those rewards with large dependency factor, which can increase the variance in estimation. To illustrate, consider we have st whose advantage functions with respect to all actions are needed to be estimated. The Monte-Carlo return starting from st following π is close to a constant q, while there is a large gap between Pπ(St+k|st, at) and Pπ(St+k|st). This dependent case can cause high variance in importance sampling advantage estimator, even when Monte-Carlo estimation has low variance.
To deal with the potential high variance problem, we seek to find the optimal combination between the proposed importance sampling estimator and Monte-Carlo estimator. There have been some previous works (Grathwohl et al., 2017) focusing on combining two estimators by optimizing a control variate, producing an estimator with less variance. Inspired by that, we decompose the reward into two estimators with a reward decomposition model, and learn the reward decomposition model by minimizing estimation variance.
The following theorem demonstrates our derivation to combine two estimators:
Theorem 1. Suppose rt+k ∼ R̂(rt+k|st, at, τt+k), where R̂ is any probability distribution. Then
Aπ(st, at) = Eτt∼Pπ(τt|st,at) [ T−t∑ k=0 γk(Rt+k − rt+k) ] − Eτt∼Pπ(τt|st) [ T−t∑ k=0 γk(Rt+k − rt+k) ]
+ Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkrt+kC π k (st, at, St+k, At+k) ] (3)
The proof of theorem 1 is provided in Appendix A.1. The sum of all the terms containing rt+k in equation 3 constructs a control variate with zero expectations, while the expectation of rest of terms containing Rt+k is the value of advantage function Aπ(st, at). From equation 3, we find that rt+k determines the way in which rewards are divided into two estimators. If rt+k is close to 0, rewards are divided into the Monte-Carlo estimator; if rt+k is close to Rt+k, rewards are divided into the importance sampling advantage estimator. We parameterize rt+k as rt+k,ψ , seeking to optimize ψ to gain an advantage estimator with minimized variance. In practice, we represent rt+k,ψ by a neural network rψ(st, at, St+k, At+k, Rt+k, k), whose architecture is shown by Figure 6 in the appendix.
For simplicity, we will use Ĵψ(τt) and Îψ(τt, at) to denote two random variables inside of expectation in equation 3, which is written by:
Ĵψ(τt) := T−t∑ k=0 γk(Rt+k − rt+k); Îψ(τt, at) := T−t∑ k=0 γkrt+kC π k (st, at, St+k, At+k) (4)
We use Varψ(st, at) to denote the variance of advantage estimator derived from equation 3. Though we are not able to write the closed-form of variance in advantage estimation since we don’t know how three sampling processes in equation 3 are correlated, we are able to derive the variance upper bound of possible estimators by equation 5, whose proof is shown in Appendix A.2.
Varψ(st, at) ≤ 3 [ Varτt∼Pπ(τt|st,at) [ Ĵψ(τt) ] +Varτt∼Pπ(τt|st) [ Ĵψ(τt) ] +Varτt∼Pπ(τt|st) [ Îψ(τt, at) ]] (5)
Based on equation 5, we further derive the upper bound of variance which is friendly to optimize: Eat∼π(at|st) Varψ(st, at) ≤ 6Varτt∼Pπ(τt|st) [ Ĵψ(τt) ] + 3Eat∼π(at|st)Varτt∼Pπ(τt|st) [ Îψ(τt, at) ] (6)
We seek to optimize ψ to minimize the variance upper bound shown in equation 6. To achieve this, we firstly use two value function approximators Vw1(st), Iw2(st, at) to approximate the expectation of two estimators respectively:
Vw1(st) ≈ Eτt∼Pπ(τt|st) [ Ĵψ(τt) ] ; Iw2(st, at) ≈ Eτt∼Pπ(τt|st) [ Îψ(τt, at) ] (7)
To approximate the expectation, we use SGD to minimize the mean squared error. The parameter update process can be finally expressed as follows, where αw represents the step-size:
w′1 = w1 + αw(Ĵψ(τt)− Vw1(st))∇w1Vw1(st), τt ∼ Pπ(τt|st) (8) w′2 = w2 + αw(Îψ(τt, at)− Iw2(st, at))∇w2Iw2(st, at), τt ∼ Pπ(τt|st) (9)
If we assume that Vw1(st) and Iw2(st, at) accurately represent the expectation, then we get the gradient to optimizeψ as follows, in order to minimize the upper bound of Eat∼π(at|st) Varψ(st, at):
∇ψ ( 6Varτt∼Pπ(τt|st) [ Ĵψ(τt) ] + 3Eat∼π(at|st)Varτt∼Pπ(τt|st) [ Îψ(τt, at) ]) = 3Eτt∼Pπ(τt|st) [ 2∇ψ(Ĵψ(τt)− Vw1(st))2 +
∑ at π(at|st)∇ψ(Îψ(τt, at)− Iw2(st, at))2 ] (10)
We can use SGD to optimize ψ expressed by equation 11, where αψ represents the step-size:
ψ′ = ψ + αψ [ 2(Ĵψ(τt)− Vw1(st))∇ψĴψ(τt)
+ ∑ at π(at|st)(Îψ(τt, at)− Iw2(st, at))∇ψ Îψ(τt, at) ] , τt ∼ Pπ(τt|st) (11)
Here we will illustrate why performing gradient descent on ψ leads to an advantage estimation with lower variance. For a single rt+k,ψ , the gradient component in the first term of equation 11 pushes the rt+k,ψ to change towards the direction to the mean total return; meanwhile, the second term of equation 11 counteracts the gradient in the first term, preventing rt+k,ψ from constructing a constant return by the restriction in variance of importance sampling estimator∑T−t k=0 γ krt+k,ψC π k (st, at, St+k). When we have the independence property in environments (i.e. the value of Cπk is close to zero), the counteraction effect in the second term will disappear. With the gradient in the first term, rt+k,ψ will be rapidly optimized towards the mean total return, making the variance of advantage estimator to dramatically decrease along the training process.
By replacing the expectation terms in equation 3 by function approximators, the form of independence-aware advantage estimator is given by:
ÂIAEt := Ĵψ(τt)− Vw1(st) + Iw2(st, at),where τt ∼ Pπ(τt|st, at). (12)

heading: 5 DEPENDENCY FACTOR ESTIMATION

text:
The final challenge in our method is to estimate the dependency factor Cπ , which is crucial to make the advantage estimator low-biased. In this section, we will introduce our modeling and training method, which is able to give accurate dependency factor estimation in experiments.
It is hard to estimate the transition probability in equation 2 because of the high dimensionality of state space. Here we derive the ratio between two transition probability into a form which can be represented by an action classifier by equation 13, whose proof is shown in Appendix A.3.
Pπ(st+k, at+k|st, at) Pπ(st+k, at+k|st) = Pπ(at|st, st+k, at+k) π(at|st) = Pπ(at|st, st+k) π(at|st) , if k ≥ 1. (13)
In practice, we use an action classification modelPφ(at|st, st+k, k) to representPπ(at|st, st+k), using Cφ(st, at, st+k) :=
Pφ(at|st,st+k,k) π(at|st) to give an approximation of C π . We call Pφ(at|st, st+k, k) dependency model in later discussions.
Similar to the derivation in previous work (Liu et al., 2018), we show that the dependency model can be learned in an temporal difference manner:
Pπ(at|st, st+k2) = Est+k1∼Pπ(st+k1 |st+k2 ,st) [P π(at|st, st+k1)] , if k2 > k1 ≥ 1. (14)
Detailed proof of equation 14 is provided in Appendix A.4. Although the case is different from the common cases in temporal difference learning, it is clear that the samples of distribution Pπ(st+k1 |st+k2 , st) can be collected by directly rolling out policy π, then we are able to train model Pφ by minimizing temporal difference error. We use a mixture of temporal difference target and Monte-Carlo target to train model Cφ, which is detailed in Appendix B. Empirically, we demonstrate the effectiveness of our approach to accurately estimate dependency factor in section 8.2.

heading: 6 ALGORITHM

text: In this section, we present crucial algorithms details of the method presented in Section 3, 4 and 5.

heading: 6.1 MODEL DEPENDENCY AND PSEUDO-CODE

text:
We illustrate the general framework of our algorithm shown by Figure 1. The model of dependency factor Cπ , lying in the basic part of our algorithm, can be directly trained by samples of current policy π. Two value functions Iw1 and Vw2 are trained by SGD on MSE loss, shown in equation 8 and equation 9, given the the reward decomposition rψ as input. The reward decomposition model rψ is also trained by SGD shown in equation 11, given the output of Iw1 and Vw2 . The pseudo-code of our algorithm is provided by Algorithm 1.
Algorithm 1 Policy Optimization Algorithm by Independence-aware Advantage Estimation 1: Initialize policy parameters θ, dependency model parameters φ, decomposition model parame-
ters ψ, and value function parameters w1, w2. 2: for each iteration do 3: Sample trajectory τ with policy πθ 4: Update φ by temporal difference learning 5: Update w1, w2 to minimize mean squared error by equation 8 and equation 9 6: Update ψ to minimize variance upper bound by equation 11 7: Compute advantage estimation ÂIAEt at each time-step t by equation 12 8: Update θ by Proximal Policy Optimization 9: end for

heading: 6.2 COMPUTATIONAL COMPLEXITY

text:
There might be concerns about computational complexity for training dependency model and reward decomposition model, since the training requires O(T 2) number of (st, st+k) pairs as training samples. We apply two techniques, trajectory truncation and block-wise training, enabling our algorithm to have a comparable computational complexity with PPO algorithm.
Trajectory Truncation. We truncate the trajectory into slices of 128 timesteps similar to the approach in PPO algorithm. We apply our method into the truncated trajectories by considering a reward Qθ(st, at) at the last step. The reward decomposition model also considers the decomposition over the final reward Qθ(st, at).
Block-wise Training. When training dependency model and reward decomposition model, we provide a total of 1282 numbers of (st, st+k) pairs, and accumulate gradient for every valid (st, st+k) pair. Only 128 × 2 times of forward and backward passes in CNN feature extractor are computed though we deal with a squared number of training data, making our method computationally efficient. Our method requires less than 3 times training time compared to PPO algorithm.

heading: 7 RELATED WORK

text:
Policy gradient (Sutton et al., 2000) provides the basic form to optimize a parameterized policy in expected returns. Generalized Advantage Estimation (Kimura et al., 2000; Schulman et al., 2015b) replaces Monte-Carlo estimator by the mixture of N-step temporal difference estimator, reducing the variance of policy gradient estimator while introducing bias. Another series of previous works focus on how to optimize parameterized policy without focusing on the selection of estimator. Among these works, TRPO (Schulman et al., 2015a) and PPO (Schulman et al., 2017) are part of the recent works that reaches state-of-the-art performance on a variety of tasks.
Some of previous works have shown that RL algorithm tends to be unstable when planning horizon is long (Jiang et al., 2015). Another series of works (François-Lavet et al., 2015; Xu et al., 2018) focus on how to select discount factor γ to improve the performance of RL algorithm. Our method suggests another solution to the problem in RL, since IAE leads to substantial variance reduction in return signal even if the planning horizon is long, which improves the performance while keeping the long planning horizon.
Our method performs gradient descent on estimation variance to improve the estimator as training proceeds. This method has been used in recent works on various applications. One previous work (Hanna et al., 2017) focuses on optimizing a behaviour policy to minimize the variance of off-policy value estimation; another previous work (Grathwohl et al., 2017) focuses on getting the optimal variance balance between REINFORCE estimator and reparameterized gradient estimator by minimizing estimation variance.
In the problem of density ratio estimation, our method is similar to one previous work (Liu et al., 2018) which transforms the density ratio estimation problem into an temporal difference learning problem. Our method is different that we focus on estimating the dependency between current actions and future states in a fixed policy, while this previous work focuses on estimating the ratio of the future state reaching probability between two different policies.

heading: 8 EXPERIMENTS

text:
In our experiments, we provide empirical results to answer the following questions:
• Can our dependency model training method in section 5 precisely estimates the dependency factor Cπ , and captures the independence property in environments?
• Can our method utilize the independence property to reduce the variance in advantage estimation, and further give more accurate advantage estimation than other advantage estimation methods?
• Can IAE improve the overall performance of policy optimization algorithm, for instance, PPO algorithm?
To answer the first question, we train the dependency model by method in section 5 and compare the prediction with ground-truth value, proving the capacity of our training method to model dependency factor Cπ . This part of results are detailed in section 8.2.
For the second question, we show that IAE method gives advantage estimation with less variance in tabular settings, and reduces value function training error in function approximation settings. In the Pixel Grid World environment, we further show that our method gives advantage estimation closer to ground-truth advantage function than MC and GAE method under cosine similarity metric. This part of results are detailed in section 8.3. To demonstrate how IAE method utilize independence property, we also provide case studies in Appendix C.3 to visualize the effect of variance reduction by low dependency factor in Pixel Grid World environment.
For the last question, we provide training curves in section 8.4 in Pixel Grid Worlds. Compared with PPO algorithm with Monte-Carlo advantage estimation and generalized advantage estimation, IAE method makes policy optimization process more sample-efficient.

heading: 8.1 ENVIRONMENT SETTINGS

text:
We perform experiment on two types of environments: finite-state MDPs and Pixel Grid World.
Finite-state MDP settings. To evaluate the quality of advantage estimation of our method in tabular cases, we construct different 3-state MDPs with different transition probability and reward functions. We categorize state transition probability settings into connected settings and isolated settings, and categorize reward settings into high-variance settings and low-variance settings. Detailed descriptions of transition probability and reward settings are provided in Appendix C.1.
Pixel Grid World Environment. To evaluate our method in function approximation settings, we build Pixel Grid World environment where observations are provided by high-dimensional images.
As illustrated in Figure 2a, the blue square represents the position of the agent and the yellow square represents the position of current goal. The agent gets positive reward for reaching the goal. To make the problem harder, the environment will do periodical reset multiple times in an episode, by which the agent and the goal are randomly repositioned. We use two different reward settings: per-step punishment setting and no punishment setting, which is detailed in Appendix C.1.
The hyper-parameters and network architectures we use in our experiments are presented in Appendix C.2.

heading: 8.2 DEPENDENCY FACTOR MODELING

text: In this section, we investigate our estimation of dependency factor Cπ , and show the general similarity between our estimation and ground-truth Cπ . We train our model Cφ by data generated by a fixed uniform random policy π. Figure 2a and 2b show the case where the dependency is precisely captured: given the future state st+k shown in Figure 2a, the model Pφ(at|st, st+k, k) correctly predicts down and right action that more likely lead current state st to future state st+k. We also build a dataset consisting of 300 random (st, st+k) pairs, where k is uniformly sampled from 1 to 30. We evaluate the mean KL divergence between ground-truth Pπ(at|st, st+k) and prediction Pφ(at|st, st+k, k) averaged in 10 runs, as shown in Figure 2c. The mean KL divergence decrease to a relatively small value during training, showing that the dependency model Pφ leads to a generally precise estimation of dependency factor Cπ .

heading: 8.3 THE VARIANCE AND ACCURACY OF INDEPENDENCE-AWARE ADVANTAGE ESTIMATION

text:
We evaluate the variance of IAE estimator on a variety of finite-state MDP settings. We train r(st, st+k) for 10000 episodes and then test the advantage estimator by performing advantage estimation multiple times to get the estimation variance. We compare the variance of IAE estimator with Monte-Carlo advantage estimator (MC) and importance sampling advantage estimator (IS). In this experiment, we use the precise value of dependency factor for IS and IAE estimator. Table 1
demonstrates the standard derivation of advantage estimation. In both environments suitable for MC estimation and ones suitable for IS estimation, our method gives estimation with less variance than both MC and IS method. In some cases, IAE estimation dramatically reduces the variance of both MC and IS estimation.
On function approximation settings, we show that our method dramatically reduces the mean squared error in training value function approximators, as shown in Figure 3a. We initialize reward decomposition model rψ to be zero for all inputs, which constructs a precise Monte-Carlo advantage estimator initially, and compare the value function training error with or without training rψ . When the reward decomposition model rψ is fixed, the loss of value function training keeps to be high because of the stochasticity of Monte-Carlo return signal, while in our method, the rψ makes reward to be distributed into importance sampling advantage estimator, making the mean squared error of value function to reduce. In Figure 3b, we show that IAE estimation has much higher cosine similarity to ground-truth advantage function, compared with Monte-Carlo and GAE estimation.
Besides, we investigate how independence property reduces the variance of estimation by visualizing the reward decomposition in Pixel Grid World Environment, which is detailed in Appendix C.3.

heading: 8.4 PERFORMANCE OF POLICY OPTIMIZATION

text:
We run Proximal Policy Optimization algorithm with IAE advantage estimation method, and compare the result to PPO algorithm with Monte-Carlo and GAE advantage estimation. Figure 4 shows
the result on two different reward settings. Compared with Monte-Carlo and GAE estimation, IAE estimation makes the policy improvement process more sample-efficient.

heading: 9 CONCLUSIONS

text:
In this work, we addressed the large variance problem in advantage estimation for policy gradient methods. We proposed a novel advantage estimation method by importance sampling, which identifies and utilizes the independence property, reducing the variance by ignoring those independent rewards. We further combined the proposed estimator with Monte-Carlo estimator in the optimal way, making the final IAE estimator to have low variance in general cases. The effectiveness of our method can be verified on Pixel-input environments compared with previous advantage estimation methods such as Monte-Carlo and Generalized Advantage Estimation.
There are a few directions to explore in the future. First, we only considered problems with discrete actions in this work, and we will extend our method to problems with continuous actions. Second, we will test our algorithm on more reinforcement learning environments, such as Atari games and continuous control tasks.

heading: A PROOFS

text:
A.1 PROOF OF UNBIASEDNESS
In this section, we show the proof of theorem 1, which demonstrates that any choice of rt+k will not bias the combined estimator as long as rt+k is a function of st, at and τt+k.
Theorem 1. Suppose rt+k ∼ R̂(rt+k|st, at, τt+k), where R̂ is any probability distribution. Then
Aπ(st, at) = Eτt∼Pπ(τt|st,at) [ T−t∑ k=0 γk(Rt+k − rt+k) ] − Eτt∼Pπ(τt|st) [ T−t∑ k=0 γk(Rt+k − rt+k) ]
+ Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkrt+kC π k (st, at, St+k, At+k) ] , (1)
where Cπk (st, at, st+k, at+k) := Pπ(st+k, at+k|st, at) Pπ(st+k, at+k|st) − 1.
Proof. Denote r(st, at, τt+k) = E [rt+k|st, at, τt+k]. Since Aπ(st, at) can be written by
Aπ(st, at) = Eτt∼Pπ(τt|st,at) [ T−t∑ k=0 γkRt+k ] − Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkRt+k ] ,
We only need to prove that
Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkrt+kC π k (st, at, St+k, At+k) ]
= Eτt∼Pπ(τt|st,at) [ T−t∑ k=0 γkrt+k ] − Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkrt+k ] . (2)
We have derivation that
Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkrt+kC π k (st, at, St+k, At+k) ] + Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkrt+k ]
= Eτt∼Pπ(τt|st) [ T−t∑ k=0 γkrt+k(1 + C π k (st, at, St+k, At+k)) ]
= T−t∑ k=0 ∫ S ∑ at+k γkEτt+k∼Pπ(τt+k|st+k,at+k) [r(st, at, τt+k)] (1 + C π k (st, at, st+k, at+k))P π(st+k, at+k|st)dst+k
= T−t∑ k=0 ∫ S ∑ at+k γkEτt+k∼Pπ(τt+k|st+k,at+k) [r(st, at, τt+k)] Pπ(st+k, at+k|st, at) Pπ(st+k, at+k|st) Pπ(st+k, at+k|st)dst+k
= T−t∑ k=0 ∫ S ∑ at+k γkEτt+k∼Pπ(τt+k|st+k,at+k) [r(st, at, τt+k)]P π(st+k, at+k|st, at)dst+k
= Eτt∼Pπ(τt|st,at) [ T−t∑ k=0 γkrt+k ] ,
which proves equation 2 and further proves theorem 1.
A.2 UPPER BOUND OF VARIANCE
In this section, we show that the if we use the sum of three random variable in equation 3 as the advantage estimator, the variance of advantage estimation is bounded by three times the sum of the variance of estimation individual random variable inside expectation in equation 3. We begin with the following lemma:
Lemma 1. Suppose X1, X2, · · · , Xn are random variables. Then
Var [ n∑ i=1 Xi ] ≤ n n∑ i=1 Var[Xi].
Proof.
Var [ n∑ i=1 Xi ] = n∑ i=1 Var[Xi] + 2 ∑ 1≤i<j≤n Cov[Xi, Xj ]
≤ n∑ i=1 Var[Xi] + 2 ∑ 1≤i<j≤n √ Var[Xi]Var[Xj ]
Then we have
n n∑ i=1 Var[Xi]−Var [ n∑ i=1 Xi ]
≥ (n− 1) n∑ i=1 Var[Xi]− 2 ∑ 1≤i<j≤n √ Var[Xi]Var[Xj ]
= ∑
1≤i<j≤n
(√ Var[Xi]− √ Var[Xj ] )2 ≥ 0,
which proves lemma 1.
From lemma 1, it is clear that the variance of advantage estimation is bounded by three times the sum of three individual variances shown by equation 5.
A.3 ACTION PROBABILITY FORM FOR DEPENDENCY FACTOR
In this section, we give detailed proof of equation 13 in the main body, which is written by:
Pπ(st+k, at+k|st, at) Pπ(st+k, at+k|st) = Pπ(at|st, st+k, at+k) π(at|st) = Pπ(at|st, st+k) π(at|st) , if k ≥ 1. (3)
Proof. We separately prove the first and the second equation. The first equation is proved by:
Pπ(st+k, at+k|st, at) Pπ(st+k, at+k|st) = Pπ(st+k, at+k, st, at) Pπ(st, at) · P π(st) Pπ(st+k, at+k, st)
= Pπ(st+k, at+k, st, at) Pπ(st+k, at+k, st) · P π(st) Pπ(st, at) = Pπ(at|st, st+k, at+k)
π(at|st) .
The second equation is proved by:
Pπ(at|st, st+k, at+k) = Pπ(st, at, st+k, at+k)
Pπ(st, st+k, at+k)
= Pπ(st, at, st+k)P π(at+k|st, at, st+k) Pπ(st, st+k)Pπ(at+k|st, st+k) = Pπ(st, at, st+k)π(at+k|st+k) Pπ(st, st+k)π(at+k|st+k) = Pπ(st, at, st+k)
Pπ(st, st+k) = Pπ(at|st, st+k).
Thus, it is proved that at+k can be abandoned from the probability condition when k ≥ 1. When k = 0, the conditional probability can be directly given by a closed form solution:
Pπ(At = a|st, st+k, at+k) = {
1, a = at+k 0, a 6= at+k
A.4 DEPENDENCY FACTOR ESTIMATION
We prove that the dependency factor can be learned in an inverse temporal difference manner in this section, which is formulated by equation 14 in the main body:
Pπ(at|st, st+k2) = Est+k1∼Pπ(st+k1 |st+k2 ,st)P π(at|st, st+k1), if k2 > k1 ≥ 1.
Proof.
Est+k1∼Pπ(st+k1 |st+k2 ,st)P π(at|st, st+k1)
= ∫ S Pπ(st+k1 |st+k2 , st)Pπ(at|st, st+k1)dst+k1
= ∫ S Pπ(st+k1 , st+k2 , st) Pπ(st+k2 , st) Pπ(at, st, st+k1) Pπ(st, st+k1) dst+k1
= ∫ S Pπ(at, st, st+k1) Pπ(st+k2 , st) Pπ(st+k2 |st+k1 , st)dst+k1
= ∫ S Pπ(at, st, st+k1) Pπ(st+k2 , st) Pπ(st+k2 |st+k1)dst+k1
= ∫ S Pπ(at, st, st+k1 , st+k2) Pπ(st+k2 , st) dst+k1 = Pπ(at, st, st+k2)
Pπ(st+k2 , st) = Pπ(at|st, st+k2)

heading: B TEMPORAL DIFFERENCE LEARNING OF DEPENDENCY MODEL

text: We use a mixture of temporal difference and Monte-Carlo training target to train dependency model. For a trajectory sample τ = {si, ai, ri}Ti=1, we provide training target for Pφ(at|st, st+k, k) for every valid (t, k) pair, and use cross-entropy loss to update φ. For the Monte-carlo training target, we directly use one-hot probability distribution of action at as the ground-truth; for the temporal difference training target, we use distribution of Pφ(at|st, st+k−1, k − 1) as the ground-truth. We mix the two training target with 0.85k weight on Monte-Carlo target and 1 − 0.85k weight on temporal difference target to achieve the optimal bias-variance tradeoff.

heading: C EXPERIMENT

text:
C.1 ENVIRONMENT SETTINGS
Finite-state MDP settings. We construct different 3-state MDPs with different transition probability and reward functions. We categorize transition probability settings into two types:
• Connected settings, where there is high mutual reaching probability between every state pair, causing the n-step transition probability to converge rapidly into stationary distribution. We use the following transition matrix for connected settings:
P = [ 0.2 0.5 0.3 0.5 0.3 0.2 0.2 0.2 0.6 ] • Isolated settings, where there is low mutual reaching probability between some state pairs,
causing the n-step transition probability to converge slowly into stationary distribution. We use the following transition matrix for isolated settings:
P = [ 0.9 0.05 0.05 0.45 0.1 0.45 0.05 0.05 0.9 ]
In connected settings, the n-step transition probability is very close into stationary distribution, resulting in a small dependency factor in future rewards. Thus, importance sampling estimator will have lower variance in connected settings than in isolated settings.
We also categorize reward settings into two types:
• High-variance settings, where the variance of Monte-Carlo return signal is large compared to mean total return. We use the following reward function for high variance settings:
R = [3 2 1]
• Low-variance settings, where the variance of Monte-Carlo return signal is small compared to mean total return. We use the following reward function for low variance settings:
R = [2.1 2 1.9]
It is clear that Monte-Carlo advantage estimator will have larger variance in high-variance settings than in low-variance settings.
Pixel Grid World environment. We build Pixel Grid World environment where observations are provided by high-dimensional images. As shown in Figure 5, the blue square represents the position of the agent and the yellow square represents the position of current goal. The size of grid world is 8 × 8, and observations are provided by 128 × 128 × 3 RGB pixels. There are 4 actions in Pixel Grid World, making the agent to move toward 4 different directions. We use two reward settings in experiments:
• Per-step punishment setting, where agent gets r = −0.03 reward in every step before reaching goal, and r = 0 reward in every step after reaching goal. Agent gets r = 1 reward when reaching goal for the first time. • No punishment setting, where agent gets r = 1 reward when reaching goal for the first
time, and gets r = 0 reward otherwise.
To make the problem harder, the environment will do periodical reset multiple times in an episode, by which the agent and the goal are randomly repositioned. The reset period is set to be 30 steps, and an episode contains 5 rounds.
C.2 HYPER-PARAMETER SETTINGS AND NETWORK ARCHITECTURE
We use γ = 0.999 for all experiments in policy optimization. For GAE estimator, we use the default settings λ = 0.95 in all experiments. We use 8 parallel environments to gather data, use the trajectory truncation length of 128, and train each truncated trajectory with 5 epochs. We use a global Adam optimizer for training both dependency model and reward decomposition model, and set learning rate to be 2.5 × 10−4. For initialization, we use orthogonal initialization with √ 2 scale for all layers, except that we initialize the last weight matrix of D to be zeros. For training Pφ(at|st, st+k, k), we weight the MC loss by 0.85k and TD loss by 1− 0.85k, and use the mixture loss to train dependency model. For PPO algorithm, we use the same hyper-parameter settings with OpenAI Baseline.
We use the network architecture shown in Figure 6 for dependency model and reward decomposition model. We use the same CNN feature extractor settings as the settings in the OpenAI Baseline. For time embedding, we store embedding vector of 128 dimensions for each k ∈ {1, 2, · · · , 128} separately.
C.3 CASE STUDY ON REWARD DECOMPOSITION MODEL
In Pixel Grid World environment, we fix a stochastic policy and train model rψ to minimize estimation variance. When the model rψ is near convergence, we visualize reward decomposition for every future reward after a state-action pair (st, at). These results are shown in Figure 7. It is clear that all the independent rewards after reset are assigned to importance sampling estimator, which is multiplied by a small dependency factor and barely contribute to advantage estimation. By contrast, rewards before reset are assigned to the Monte-Carlo estimator, which contribute to advantage estimation.


summaries: This paper provides a new doubly robust estimator for off-policy policy evaluation, based on the new infinite horizon technique (i.e. using an estimate of the state density ratio as opposed to long products of action importance weights). They show the doubly robust estimator's bias is dependent on a product of the error of the value function estimate and stationary distribution ratio estimate, which provides improvements over the initial infinite horizon estimator. They also provide some nice discussion of the relation of their method and Lagrangian duality, which was quite interesting and insightful. Finally, the paper shows the usual empirical comparisons.

summaries: This paper provides an approach for reducing bias in long horizon off-policy evaluation (OPE) problems, extending recent work from Liu et al., 2018 that estimates the ratio of the stationary state distributions in off-policy evaluation for reducing variance. The paper provides a doubly robust method for reducing bias, since it requires separately estimating a value function. The key idea of the paper is to provide low variance, low bias OPE since their approach relies on accurately estimating the state distribution ratio and also the estimation of the value function.

summaries: This paper proposes a new algorithm for the off-policy evaluation problem in reinforcement learning. It combines the value function learning method and the stationary distribution ratio estimators. The proposed method achieves double robustness, which means the proposed estimator is consistent as long as the value function or ratio estimator is consistent. Empirical results on some control domains are presented to verify the effectiveness of the algorithm.

abstractText: Infinite horizon off-policy policy evaluation is a highly challenging task due to the excessively large variance of typical importance sampling (IS) estimators. Recently, Liu et al. (2018a) proposed an approach that substantially reduces the variance of infinite horizon off-policy evaluation by estimating the stationary density ratio, but at the cost of introducing biases due to errors in density ratio estimation. In this paper, we develop a bias-reduced augmentation of their method, which can take advantage of a learned value function to improve accuracy. Our method is doubly robust in that the bias vanishes when either the density ratio or value function estimation is perfect. In general, when either of them is accurate, the bias can also be reduced. Both theoretical and empirical results show that our method yields significant advantages over previous methods.

authors:
Søren Asmussen
Peter W Glynn

title: Stochastic simulation: algorithms and analysis, volume 57

venue: Springer Science & Business Media,

title: Dynamic Programming and Optimal Control

venue: Athena Scientific, 2nd edition,

authors:
Léon Bottou
Jonas Peters
Joaquin Quiñonero-Candela
Denis Xavier Charles
D. Max Chickering
Elon Portugaly
Dipankar Ray
Patrice Simard
Ed Snelson

title: Counterfactual reasoning and learning systems: The example of computational advertising

venue: Journal of Machine Learning Research,

authors:
Yichen Chen
Mengdi Wang

title: Stochastic primal-dual methods and sample complexity of reinforcement learning

venue: arXiv preprint arXiv:1612.02516,

authors:
Bo Dai
Niao He
Yunpeng Pan
Byron Boots
Le Song

title: Learning from conditional distributions via dual kernel embeddings

venue: In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
Bo Dai
Albert Shaw
Lihong Li
Lin Xiao
Niao He
Zhen Liu
Jianshu Chen
Le Song

title: SBEED: Convergent reinforcement learning with nonlinear function approximation

venue: In Proceedings of the Thirty-Fifth International Conference on Machine Learning (ICML),

authors:
Daniela Pucci de Farias
Benjamin Van Roy

title: The linear programming approach to approximate dynamic programming

venue: Operations Research,

authors:
Miroslav Dudı́k
John Langford
Lihong Li

title: Doubly robust policy evaluation and learning

venue: In Proceedings of the 28th International Conference on Machine Learning (ICML),

authors:
Mehrdad Farajtabar
Yinlam Chow
Mohammad Ghavamzadeh

title: More robust doubly robust off-policy evaluation

venue: In Proceedings of the 35th International Conference on Machine Learning (ICML),

authors:
Yihao Feng
Lihong Li
Qiang Liu

title: A kernel loss for solving the bellman equation

venue: Neural Information Processing Systems (NeurIPS),

authors:
Raphael Fonteneau
Susan A. Murphy
Louis Wehenkel
Damien Ernst

title: Batch mode reinforcement learning based on the synthesis of artificial trajectories

venue: Annals of Operations Research,

authors:
Carles Gelada
Marc G Bellemare

title: Off-policy deep reinforcement learning by bootstrapping the covariate shift

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Assaf Hallak
Shie Mannor

title: Consistent on-line off-policy evaluation

venue: In Proceedings of the 34th International Conference on Machine Learning (ICML),

authors:
Josiah Hanna
Scott Niekum
Peter Stone

title: Importance sampling policy evaluation with an estimated behavior policy

venue: In Proceedings of the 36th International Conference on Machine Learning,

authors:
Nan Jiang
Lihong Li

title: Doubly robust off-policy evaluation for reinforcement learning

venue: In Proceedings of the 23rd International Conference on Machine Learning (ICML),

authors:
Nathan Kallus
Masatoshi Uehara

title: Double reinforcement learning for efficient off-policy evaluation in markov decision processes

venue: arXiv preprint arXiv:1908.08526,

title: Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizon processes

venue: arXiv preprint arXiv:1909.05850,

authors:
Lihong Li
Wei Chu
John Langford
Xuanhui Wang

title: Unbiased offline evaluation of contextualbandit-based news article recommendation algorithms

venue: In Proceedings of the 4th International Conference on Web Search and Data Mining (WSDM),

authors:
Lihong Li
Rémi Munos
Csaba Szepesvári

title: Toward minimax off-policy value estimation

venue: In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
Bo Liu
Ji Liu
Mohammad Ghavamzadeh
Sridhar Mahadevan
Marek Petrik

title: Finite-sample analysis of proximal gradient td algorithms

venue: In UAI,

title: Monte Carlo Strategies in Scientific Computing

venue: Springer Series in Statistics. SpringerVerlag,

authors:
Yao Liu
Omer Gottesman
Aniruddh Raghu
Matthieu Komorowski
Aldo A Faisal
Finale DoshiVelez
Emma Brunskill

title: Representation balancing mdps for off-policy policy evaluation

authors:
Yao Liu
Pierre-Luc Bacon
Emma Brunskill

title: Understanding the curse of horizon in off-policy evaluation via conditional importance sampling

venue: arXiv preprint arXiv:1910.06508,

authors:
Yao Liu
Adith Swaminathan
Alekh Agarwal
Emma Brunskill

title: Off-policy policy gradient with state distribution correction

venue: arXiv preprint arXiv:1904.08473,

authors:
Susan A. Murphy
Mark van der Laan
James M. Robins

title: Marginal mean models for dynamic regimes

venue: Journal of the American Statistical Association,

authors:
Ofir Nachum
Yinlam Chow
Bo Dai
Lihong Li

title: Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections

title: Markov Decision Processes.: Discrete Stochastic Dynamic Programming

authors:
Mark Rowland
Anna Harutyunyan
Hado van Hasselt
Diana Borsa
Tom Schaul
Rémi Munos
Will Dabney

title: Conditional importance sampling for off-policy learning

authors:
Richard S. Sutton
Andrew G. Barto

title: Reinforcement Learning: An Introduction

authors:
Philip S. Thomas
Emma Brunskill

title: Data-efficient off-policy policy evaluation for reinforcement learning

venue: In Proceedings of the 33rd International Conference on Machine Learning (ICML),

authors:
Philip S. Thomas
Georgios Theocharous
Mohammad Ghavamzadeh
Ishan Durugkar
Emma Brunskill

title: Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing

venue: In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI),

authors:
Masatoshi Uehara
Jiawei Huang
Nan Jiang

title: Minimax weight and Q-function learning for off-policy evaluation, 2019

authors:
Tengyang Xie
Yifei Ma
Yu-Xiang Wang

title: Optimal off-policy evaluation for reinforcement learning with marginalized importance sampling

title: ADDITIONAL EXPERIMENTAL RESULTS We add a standard model-based baseline in Figure 4 following the same procedure as Liu et al. (2018a).3 Figure 4 shows that the performance of the model-based approach

heading: 1 INTRODUCTION

text:
A key problem in reinforcement learning (RL) (Sutton & Barto, 1998) is off-policy policy evaluation: given a fixed target policy of interest, estimating the average reward garnered by an agent that follows the policy, by only using data collected from different behavior policies. This problem is widely encountered in many real-life applications (e.g., Murphy et al., 2001; Li et al., 2011; Bottou et al., 2013; Thomas et al., 2017), where online experiments are expensive and high-quality simulators are difficult to build. It also serves as a key algorithmic component of off-policy policy optimization (e.g., Dudı́k et al., 2011; Jiang & Li, 2016; Thomas & Brunskill, 2016; Liu et al., 2019b).
There are two major families of approaches to policy evaluation. The first approach is to build a simulator that mimics the reward and next-state transitions of the real environment (e.g., Fonteneau et al., 2013). While straightforward, this approach strongly relies on the model assumptions in building the simulator, which may invalidate evaluation results. The second approach is to use importance sampling to correct the sampling bias in off-policy data, so that an (almost) unbiased estimator can be obtained (Liu, 2001; Strehl et al., 2010; Bottou et al., 2013). A major limitation, however, is that importance sampling can become inaccurate due to high variance. In particular, most existing IS-based estimators compute the weight as the product of the importance ratios of many steps in the trajectory, causing excessively high variance for problems with long or infinite horizon, yielding a curse of horizon (Liu et al., 2018a).
Recently, Liu et al. (2018a) proposes a new estimator for infinite-horizon off-policy evaluation, which presents significant advantages to standard importance sampling methods. Their method directly estimates the density ratio between the state stationary distributions of the target and behavior policies, instead of the trajectories, thus avoiding exponential blowup of variance in the horizon. While Liu et al.’s method shows much promise by significantly reducing the variance, in practice, it may suffer from high bias due to the error or model misspecficiation when estimating the density ratio function.
∗The first two authors contributed equally to this work.
In this paper, we develop a doubly robust estimator for infinite horizon off-policy estimation, by integrating Liu et al.’s method with information from an additional value function estimation. This significantly reduces the bias of Liu et al.’s method once either the density ratio, or the value function estimation is accurate (hence doubly robust). Since Liu et al.’s method already promises low variance, our additional bias reduction allows us to achieve significantly better accuracy for practical problems.
Technically, our new bias reduction method provides a new angle of double robustness for off-policy evaluation, orthogonal to the existing literature of doubly robust policy evaluation that solely devotes to variance reduction (Jiang & Li, 2016; Thomas & Brunskill, 2016; Farajtabar et al., 2018), mostly based on the idea of control variates (e.g. Asmussen & Glynn, 2007). Our double robustness for bias reduction is significantly different, and instead yields an intriguing connection with the fundamental primal-dual relations between the density (ratio) functions and value functions (e.g., Bertsekas, 2000; Puterman, 2014). This new perspective can inspire more efficient algorithms for policy evaluation, and lead to unified frameworks for these types of double robustness in future work.

heading: 2 BACKGROUND

text:
Infinite Horizon Off-Policy Estimation Let M = 〈S,A, r,T , µ0〉 be a Markov decision process (MDP) with state space S, action space A, reward function r, transition probability function T , and initial-state distribution µ0. A policy π maps states to distributions over A, with π(a|s) being the probability of selecting a given s. The average discounted reward for π, with a given discount γ ∈ (0, 1) 1, is defined as
Rπ := lim T→∞ Eτ∼π
[∑T t=0 γ
trt∑T t=0 γ t
] ,
where τ = {st, at, rt}0≤t≤T is a trajectory with states, actions, and rewards collected by following policy π in the MDP, starting from s0 ∼ µ0. Given a set of n trajectories, D = {s(i)t , a (i) t , r (i) t }1≤i≤n,0≤t≤T , collected under a behavior policy π0(a|s), the off-policy evaluation problem aims to estimate the average discounted reward Rπ for another target policy π(a|s).
Estimation via Value Function The value function for policy π is defined as the expected accumulated discounted future rewards started from a certain state: V π(s) = Eτ∼π[ ∑∞ t=0 γ
trt|s0 = s]. We use rπ(s) = Ea∼π(·|s)[r(s, a)] to denote the average reward for state s given policy π. Under the definition, the value function can be seen as a fixed point of the Bellman equation:
V π(s) = rπ(s) + γPπV π(s), PπV π(s) := Ea∼π(·|s),s′∼T (·|s,a)[V π(s′)], ∀s ∈ S, (1)
where PπV (s) is the average of the next value function given the current state s and policy π; see Appendix A.1 for details.
The value function and the expected reward Rπ is related in the following straightforward way
Rπ = (1− γ)Es∼µ0 [V π(s)], (2) where the expectation is with respect to the distribution µ0(s) of the initial states s0 at time t. Therefore, given an approximation V̂ of V π, and samples D0 := {s(i)0 }1≤i≤n0 drawn from µ0(s), we can estimate Rπ by
R̂πVAL[V̂ ] = (1− γ) n0 n0∑ i=1 V̂ (s (i) 0 ).
Note that this estimator is off-policy in nature, since it requires no samples from the target policy π.
Estimation via State Density Function Denote dπ,t(·) as average visitation of st in time step t. The state density function, or the discounted average visitation, is defined as:
dπ(s) := lim T→∞
∑T t=0 γ
tdπ,t(s)∑T t=0 γ t = (1− γ) ∞∑ t=0 γtdπ,t(s),
1For average case when γ = 1, the definition of Rπ is the same. However, the definition of value function is different. We will assume γ < 1 throughout our main paper for simplicity; for average case check appendix B for more details.
where (1− γ) can be viewed as the normalization factor introduced by ∑∞ t=0 γ t.
Similar to Bellman equation for value function, the state density function can also be viewed as a fixed point to the following recursive equation (Liu et al., 2018a, Lemma 3):
dπ(s ′) = (1− γ)µ0(s′) + γT πdπ(s′), where T πdπ(s′) := ∑ s,a T (s′|s, a)π(a|s)dπ(s). (3)
The operator T π is an adjoint operator of Pπ used in (1); see Appendix A.1 for a discussion. If the density function dπ is known, it provides an alternative way for estimating the expected reward Rπ , by noting that
Rπ = Es∼dπ,a∼π(·|s)[r(s, a)]. (4)
We can see that both density function dπ and value function V π can be used to estimate the expected reward Rπ . We clarify the connection in detail in Appendix A.1.
Off-Policy State Visitation Importance Sampling Equation (4) can not be directly used for offpolicy estimation, since it involves expectation under the behavior policy π. Liu et al. (2018a) addressed this problem by introducing a change of measures via importance sampling:
Rπ = Es∼dπ0 ,a∼π0(·|s) [ wπ/π0(s) π(a|s) π0(a|s) r(s, a) ] , with wπ/π0(s) = dπ(s) dπ0(s) , (5)
where wπ/π0(s) is the density ratio function of dπ and dπ0 .
Given an approximation ŵ of wπ/π0 , and samples D = {s (i) t , a (i) t , r (i) t }1≤i≤n,0≤t≤T collected from policy π0, we can estimate Rπ as:
R̂πSIS[ŵ] = 1
Z n∑ i=1 T∑ t=0 γtŵ(s (i) t ) π(ai|si) π0(ai|si) ri, Z = n∑ i=1 T∑ t=0 γtŵ(s (i) t ) π(a (i) t |s (i) t ) π0(a (i) t |s (i) t ) , (6)
where Z is the normalized constant of the importance weights.

heading: 3 DOUBLY ROBUST ESTIMATOR

text:
Doubly robust estimator is first proposed into reinforcement learning community to solve contextual bandit problem by Dudı́k et al. (2011) as an estimator combining inverse propensity score (IPS) estimator and direct method (DM) estimator.
Jiang & Li (2016) 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. Inspired by previous works, we propose a new doubly robust estimator based on our infinite horizon off-policy estimator R̂πSIS.

heading: 3.1 DOUBLY ROBUST ESTIMATOR FOR INFINITE HORIZON MDP

text:
The value-based estimator R̂πVAL[V̂ ] and density-ratio-based estimator R̂ π SIS[ŵ] are expected to be accurate when V̂ and ŵ are accurate, respectively. Our goal is to combine their advantages, obtaining a doubly robust estimator that is accurate once either V̂ or ŵ or is accurate.
To simplify the problem, it is useful to examine the limit of infinite samples, with which R̂πVAL[V̂ ] and R̂πSIS[ŵ] converge to the following limit of expectations:
RπSIS[ŵ] := lim n,T→∞ R̂πSIS[ŵ] = ∑ s rπ(s)dπ0(s)ŵ(s), (7)
RπVAL[V̂ ] := lim n0→∞ R̂πVAL[V̂ ] = (1− γ) ∑ s V̂ (s)µ0(s). (8)
Here and throughout this work, we assume V̂ and ŵ are fixed pre-defined approximations, and only consider the randomness from the data D. A first observation is that we expect to have rπ ≈ V̂ − γPπV̂ by Bellman equation (1), when V̂ approximates the true value V π . Plugging this into RπSIS[ŵ] in Equation (7), we obtain the following “bridge estimator”, which incorporates information from both ŵ and V̂ :
Rπbridge[V̂ , ŵ] = ∑ s ( V̂ (s)− γPπV̂ (s) ) dπ0(s)ŵ(s), (9)
where operator Pπ is defined in Bellman equation (1). The corresponding empirical estimator is defined by
R̂πbridge[V̂ , ŵ] = n∑ i=1 T−1∑ t=0 ( 1 Z1 γtŵ(s (i) t )V̂ (s (i) t )− 1 Z2 γt+1ŵ(s (i) t ) π(ai|si) π0(ai|si) V̂ (s (i) t+1) ) , (10)
where Z1 = ∑n i=1 ∑T−1 t=0 γ tŵ(s (i) t ) and Z2 = ∑n i=1 ∑T−1 t=0 γ t+1ŵ(s (i) t )βπ/π0(a (i) t |s (i) t ) are selfnormalized constant of important weights each empirical estimation.
However, directly estimating Rπ using the bridge estimator R̂πbridge[V̂ , ŵ] yields a poor estimation, because it includes the errors from both ŵ and V̂ and can be “doubly worse”. However, we can construct our “doubly robust” estimator by canceling Rπbridge[V̂ , ŵ] out from R π SIS[ŵ] and R π VAL[V̂ ]:
RπDR[V̂ , ŵ] = ∑ s
rπ(s)dπ0(s)ŵ(s)︸ ︷︷ ︸ RπSIS[ŵ]
+ (1− γ) ∑ s
V̂ (s)µ0(s)︸ ︷︷ ︸ RπVAL[V̂ ]
− ∑ s ( V̂ (s)− γPπV̂ (s) ) dπ0(s)ŵ(s)︸ ︷︷ ︸
Rπbridge[V̂ ,ŵ]
.
(11) And its corresponding empirical estimator can be written as:
R̂πDR[V̂ , ŵ] = R̂ π SIS[ŵ] + R̂ π VAL[V̂ ]− R̂πbridge[V̂ , ŵ] .
Doubly Robust Bias Reduction The double robustness of R̂πDR[V̂ , ŵ] is reflected in the following key theorem, which shows that it is accurate once either V̂ or ŵ is accurate.
Theorem 3.1 (Doubly Robustness). Let RπDR[V̂ , ŵ] := limn0,n,T→∞ R̂πDR[V̂ , ŵ] be the limit of R̂πDR when it has infinite samples. Following the definition above, we have
RπDR[V̂ , ŵ]−Rπ = Es∼dπ0 [ εŵ(s)εV̂ (s) ] , (12)
where εV̂ and εŵ are errors of V̂ and ŵ, respective, defined as follows
εŵ = dπ(s)
dπ0(s) − ŵ(s), εV̂ (s) = V̂ (s)− r π(s)− γPπV̂ (s).
The error εŵ of ŵ is measured by the difference with the true density ratio dπ(s)/dπ0(s), and the error εV̂ of V̂ is measured using the Bellman residual.
From the theorem we can see that, if V̂ is exact (V̂ ≡ V π), we have εV̂ ≡ 0; if ŵ is exact (ŵ ≡ dπ/dπ0 ), we have εŵ ≡ 0. Therefore, our estimator is consistent (i.e., limn,n0→∞ R̂πDR[V̂ , ŵ] = Rπ) if either V̂ or ŵ are exact. The estimator is thus doubly robust in this sense. In contrast, R̂πSIS[ŵ] and R̂πVAL[V̂ ] can be more sensitive to the error of ŵ and V̂ , respectively:
RπSIS[ŵ]−Rπ = Es∼dπ0 [εŵ(s)r π(s)] , RπVAL[V̂ ]−Rπ = Es∼dπ0 [ wπ/π0(s)εV̂ (s) ] .
Variance Analysis Different from the bias reduction, the doubly robust estimator does not guarantee to the reduce the variance over R̂πSIS[ŵ] or R̂ π VAL[V̂ ] in general. However, as we show in the following result, we can break the variance of R̂πDR[V̂ , ŵ] into two parts. The first is the variance of R̂πVAL[V̂ ] which is often relatively small. The second is generally no greater than the variance of R̂πSIS[ŵ], and can be much smaller when V̂ ≈ V π. Moreover, R̂πVAL[V̂ ] and R̂πSIS[ŵ] avoid the curse of horizon by design, so their variances tend to be much smaller than the corresponding estimators that apply IPS correction on the trajectories.
Algorithm 1 Infinite Horizon Doubly Robust Estimator
Input: Transition data Dπ0 = {s (i) t , a (i) t , r (i) t }1≤i≤n,0≤t≤T from policy π0;
D0 = {s(j)0 }1≤j≤n0 be samples from initial distribution µ0 target policy π, value function estimate V̂ ; density ratio estimate ŵ.
Estimation: Use R̂πDR in (11) to estimate Rπ using sample from D and D0.
Proposition 3.1 (Variance Analysis). Assume R̂πDR[V̂ , ŵ] is estimated based on sampleD0 ∼ µ0 and Dπ0 ∼ dπ0 , which we assume to be independent of each other. We have
VarD0,Dπ0 [ R̂πDR[V̂ , ŵ] ] = VarD0 [ R̂πVAL[V̂ ] ] + VarDπ0 [ R̂πres[V̂ , ŵ] ] , (13)
with R̂πres[V̂ , ŵ] := R̂ π SIS[ŵ]− R̂πbridge[V̂ , ŵ] = ÊDπ0 [ ε̂V̂ (s)ŵ(s) ] and ε̂V̂ (s) the TD error of V̂ ,
ε̂V̂ (s) = r̂ π(s)− V̂ (s) + γP̂πV̂ (s),
with r̂π(s) = r(s, a)π(a|s)/π0(a|s), P̂πV̂ (s) = π(a|s)/π0(a|s)V̂ (s′). Therefore, VarDπ0 (R̂ π res[V̂ , ŵ]) can be small when V̂ is close to the true value V π , or ε̂V̂ (s) ≈ 0.
From the proposition we can see that when V̂ is close to the true value V π, the variance of the residual ε̂V̂ may be negligibly small compared to the variance of R̂ π SIS[ŵ]. A further comparison of the variances between R̂πres[V̂ , ŵ] and R̂ π SIS[ŵ] is provided in Appendix A.3. In the case when the TD
error ε̂V̂ is negligible, we have VarD0,Dπ0 [ R̂πDR[V̂ , ŵ] ] ≈ VarD0 [ R̂πVAL[V̂ ] ] . Typically, the variance
of R̂πVAL[V̂ ] is smaller than R̂ π SIS[ŵ] since the variance of importance sampling methods heavily depends on the effective sample size, which is less controllable compared to R̂πVAL[V̂ ]. Therefore, the variance of our doubly robust estimator may even be smaller than that of R̂πSIS[ŵ] in practice.
The variance in (13) is a sum of two terms because of the assumption that samples from µ0 and dπ0 are independent. In practice, they have dependency but it is possible to couple the samples from µ0 and dπ0 in a certain way to further decrease the variance, which we leave as future work.
Proposed Algorithm for Off-Policy Evaluation Suppose we have already obtained V̂ and ŵ, as estimations of V π and wπ/π0 , respectively, we can directly use equation (11) to estimate R
π . A detail procedure is described in Algorithm 1.

heading: 4 DOUBLE ROBUSTNESS AND LAGRANGIAN DUALITY

text:
In this section, we reveal a surprising connection between our double robustness and Lagrangian duality. We show that our doubly robust estimator is equivalent to the Lagrangian function of a primal-dual formulation of policy evaluation. This connection is of interest in itself, and may provide a foundation for deriving more effective algorithms.
We start with the following classic, optimization formulation of policy evaluation (Puterman, 2014):
Rπ = min V
{ (1− γ)
∑ s µ0(s)V (s) s.t. V (s) ≥ rπ(s) + γPπV (s), ∀s
} , (14)
where we find V to maximize its average value, subject to an inequality constraint on the Bellman equation. It can be shown that the solution of (14) is achieved by the true value function V π, hence yielding a true expected reward Rπ .
Introducing a Lagrangian multiplier ρ ≥ 0, we can derive the Lagrangian function L(V, ρ) of (14), L(V, ρ) = (1− γ) ∑ s µ0(s)V (s)− ∑ s ρ(s)(V (s)− rπ(s) + γPπV (s)). (15)
Comparing L(V, ρ) with our estimator R̂πDR[V̂ , ŵ] in (11), we can see that they are in fact equivalent in expectation.
Theorem 4.1 (Primal Dual). I) Define wρ/π0(s) = ρ(s) dπ0 (s) . We have
L(V, ρ) = RπDR[V,wρ/π0 ], and hence L(V, dπ) = L(V π, ρ) = Rπ, ∀ V, ρ,
which suggests that L(V, ρ) is “doubly robust” in that it equals Rπ if either V = V π or ρ = dπ .
II) The primal problem (14) forms a strong duality with the following dual problem,
Rπ = max ρ≥0 {∑ s ρ(s)rπ(s) s.t. ρ(s′) = (1− γ)µ0(s′) + γT πρ(s′), ∀s′ } , (16)
where T π is defined in (3).
This shows that the dual problem is equivalent to constraint ρ using the fixed point equation (3) and maximize the average reward given distribution ρ. Since the unique fixed point of (3) is dπ(s), the solution of (16) naturally yields the true reward Rπ , hence forming a zero duality gap with (14).
It is natural to intuit the double robustness of the Lagrangian function. From (15), L(V, ρ) can be viewed as estimating the reward Rπ using value function with a correction of Bellman residual (V − rπ − γPπV ). If V = V π, the estimation equals the true reward and the correction equals zero. From the dual problem (16), L(V, ρ) can be viewed as estimating Rπ using density function ρ, corrected by the residual (ρ− (1− γ)µ0 − γT πρ). We again get the true reward if ρ = dπ . It turns out that we can use the primal-dual formula when γ = 1 to obtain the double robust estimator for the average reward case. We clarify it in appendix B.
Remark The fact that the density function dπ forms a dual variable of the value function V π is widely known in the optimal control and reinforcement learning literature (e.g., Bertsekas, 2000; Puterman, 2014; de Farias & Van Roy, 2003), and has been leveraged in various works for policy optimization. However, it does not seem to be well exploited in the literature of off-policy policy evaluation.

heading: 5 RELATED WORK

text:
Off-Policy Value Evaluation The problem of off-policy value evaluation has been studied extensively in contextual bandits and MDPs (Fonteneau et al., 2013; Li et al., 2015; Jiang & Li, 2016; Thomas & Brunskill, 2016; Liu et al., 2018b; Farajtabar et al., 2018; Hanna et al., 2019; Xie et al., 2019; Rowland et al., 2019). However, most of the existing works are based on importance sampling (IS) to correct the mismatch between the distribution of the whole trajectories induced by the behavior and target policies, which faces the “curse of horizon” (Liu et al., 2018a) when extended to long-horizon (or infinite-horizon) problems.
Several other works (Guo et al., 2017; Hallak & Mannor, 2017; Liu et al., 2018a; Gelada & Bellemare, 2019; Nachum et al., 2019; Liu et al., 2019a) have been proposed to address the high variance issue in the long-horizon problems. Liu et al. (2018a) apply importance sampling on the average visitation distribution of state-action pairs, instead of the distribution of the whole trajectories, providing an effective approach to break “the curse of horizon”. However, they require to learn a density ratio function over the whole state-action pairs, which may induce large bias. Our work incorporates the density ratio and value function estimation, which significantly reduces the induced bias of two estimators, resulting a doubly robust estimator.
Our work is also closely related to DR techniques used in finite horizon problems (Murphy et al., 2001; Dudı́k et al., 2011; Jiang & Li, 2016; Thomas & Brunskill, 2016; Farajtabar et al., 2018), which incorporate an approximate value function as control variates to IS estimators. Different from existing DR approaches, our work is related to the well known duality between the density and the value function, which reveals the relationship between density (ratio) learning (Liu et al., 2018a) and value function learning. Based on this interesting observation, we further obtain the doubly robust estimator for estimating average reward in infinite-horizon problems.
A recent work (Xie et al., 2019) has also explored the idea of tracking marginal state distribution shifts at every single time step in an episode, instead of the stationary state distribution across all time steps (Liu et al., 2018a). It provides additional benefits for understanding and analyzing problems
such as short horizon and time-variant MDPs. They call this approach marginalized importance sampling (MIS). Later on, Kallus & Uehara (2019a) incorporate the DR technique to improve the MIS estimator. Independent of this work, Kallus & Uehara (2019b); Uehara et al. (2019) extend previous works to propose estimators can be viewed as a variant of ours.
Primal-Dual Value Learning Primal-dual optimization techniques have been widely used for off-policy value function learning and policy optimization (Liu et al., 2015; Chen & Wang, 2016; Dai et al., 2017; 2018; Feng et al., 2019). Nevertheless, the duality between density and value function has not been well explored in the literature of off policy value estimation. Our work proposes a new doubly robustness technique for off-policy value estimation, which can be naturally viewed as the Lagrangian function of the primal-dual formulation of policy evaluation, providing an alternative unified view for off policy value evaluation.

heading: 6 EXPERIMENT

text:
In this section, we conduct simulation experiments on different environmental settings to compare our new doubly robust estimator with existing methods. We mainly compare with infinite horizon based estimator including state importance sampling estimator (Liu et al. (2018a)) and value function estimator. We do not report results on the vanilla trajectory-based importance sampling estimators because of their significant higher variance, but we do compare with the doubly robust version induced by Thomas & Brunskill (2016) (self-normalized variant of Jiang & Li (2016)). In all experiments we compare with Monte Carlo and naive average as Liu et al. (2018a) suggested. The ground truth for each environment is calculated by averaging Monte Carlo estimation with a very large sample size.
Taxi Environment We follow Liu et al. (2018a)’s tabular environment Taxi, which has 2000 states and 6 actions in total. For more experimental details, please check appendix C.1.
We pre-train two different V̂ and Ṽ trained with a small and fairly large size of samples, respectively, where Ṽ is very close to true value function V π but V̂ is relatively further from it. Similarly we pre-train ρ̂ and ρ̃ ≈ dπ . For estimation we use a mixed ratio α, β to control the bias of the input V, ρ, where V = αV̂ + (1− α)Ṽ and ρ = βρ̂+ (1− β)ρ̃. Figure 1(a)-(c) show results of comparison for different methods as we changing the number of trajectories. We can see that the MSE performance of value function(R̂πVAL) and state visitation importance sampling(R̂πSIS) estimators are mainly impeded by their large biases, while our method has much less bias thus it can keep decreasing as sample size increase and achieves same performance as on policy estimator. Figure 1(d) shows results if we change the horizon length. Notice that here we keep the number of samples to be the same, so if we increase our horizon length we will decrease the number of trajectories in the same time. We can see that our method alongside with all infinite horizon methods will get better result as horizon length increase. Figure 1(e)-(f) indicate the “double robustness” of our method, where our method benefits from either a better V or a better ρ.
Puck-Mountain Puck-Mountain is an environment similar to Mountain-Car, except that the goal of Puck-Mountain is to push the puck as high as possible in a local valley, which has a continuous state space of R2 and a discrete action space similar to Mountain-Car. We use the softmax functions of an optimal Q-function as both target policy and behavior policy, where the temperature of the behavior policy is higher (encouraging exploration). For more details of constructing policies and training algorithms for density ratio and value functions, please check appendix C.2.
Figure 2(a)-(c) show results of comparison for different methods as we changing the number of trajectories. Similar to taxi, we find our method has much lower bias than density ratio and value function estimation, which yields a better MSE. In Figure 2(d) the performance for all infinite horizon estimator will not degenerate as horizon increases, while finite horizon method such as finite weighted horizon doubly robust will suffer from larger variance as horizon increases.
InvertedPendulum InvertedPendulum is a pendulum that has its center of mass above its pivot point. We use the implementation of InvertedPendulum from OpenAI gym (Brockman et al., 2016), which is a continuous control task with state space in R4 and we discrete the action space to be {−1,−0.3,−0.2, 0, 0.2, 0.3, 1}. More experiment details can be found in appendix C.2. In Figure 3(a)-(c) our method again significantly reduces the bias, which yields a better MSE comparing with value and density estimation. Figure 3(d) also shows that our method consistently outperforms all other methods as the horizon increases with a fixed total timesteps.

heading: 7 CONCLUSION

text: 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 estimator can be accurate as long as one of the estimators are accurate, which yields a significant advantage comparing to previous estimators. Future directions include deriving more novel optimization algorithms to learn value function and density(ratio) function by using the primal dual framework.

heading: ACKNOWLEDGEMENT

text: This work is supported in part by NSF CRII 1830161 and NSF CAREER 1846421. We would like to acknowledge Google Cloud for their support.

heading: A PROOF

heading: A.1 TRANSITION OPERATOR FOR BELLMAN EQUATION

text:
For simplicity, we define the following two operators thorough our proofs to simplify our notations.
Definition A.1. Given a policy π and the unknown environment transition T , we define T π and Pπ over any function f : S → R as
(T πf) (s′) = ∑ s,a T (s′|s, a)π(a|s)f(s)
(Pπf) (s) = ∑ s′,a T (s′|s, a)π(a|s)f(s′)
Using these operator notations, we can rewrite the above two recursive equations as:
V π = rπ + γPπV π, dπ = (1− γ)µ0 + γT πdπ,
where rπ(s) = Ea∼π(·|s)[r(s, a)].
These transition operators have the following nice adjoint property.
Lemma A.2. For two function f and g, if the following summation is finite, we will have∑ s (Pπf) (s)g(s) = ∑ s f(s) (T πg) (s). (17)
Proof.
∑ s (Pπf) (s)g(s) = ∑ s ∑ s′,a T (s′|s, a)π(a|s)f(s′)  g(s) = ∑ s′ f(s′) (∑ s,a T (s′|s, a)π(a|s)g(s)
) = ∑ s′ f(s′) (T πg) (s′)
Using this property we can actually using Bellman Equations to re-derive the two different way to get Rπ .
Rπ = lim T→∞
Eτ(i)∼π[ ∑T t=0 γ
trt∑T t=0 γ t ]
= ∑ s V π(s)(1− γ)µ0(s)
= ∑ s V π(s) (I − γT π) dπ(s)
= ∑ s (I − γPπ)V π(s)dπ(s)
= ∑ s rπ(s)dπ(s).

heading: A.2 PROOF OF THEOREM 3.1

text:
Theorem 3.1 (Doubly Robustness). Let RπDR[V̂ , ŵ] := limn0,n,T→∞ R̂πDR[V̂ , ŵ] be the limit of R̂πDR when it has infinite samples. Following the definition above, we have
RπDR[V̂ , ŵ]−Rπ = Es∼dπ0 [ εŵ(s)εV̂ (s) ] , (12)
where εV̂ and εŵ are errors of V̂ and ŵ, respective, defined as follows
εŵ = dπ(s)
dπ0(s) − ŵ(s), εV̂ (s) = V̂ (s)− r π(s)− γPπV̂ (s).
The error εŵ of ŵ is measured by the difference with the true density ratio dπ(s)/dπ0(s), and the error εV̂ of V̂ is measured using the Bellman residual.
Proof. Using the property of the operator, we can rewrite (1− γ)µ0(s) using Bellman equation as dπ − γT πdπ , thus we have
RπVAL[V̂ ] =(1− γ) ∑ s V̂ (s)µ0(s)
= ∑ s V̂ (s) (dπ − γT πdπ) (s)
= ∑ s (I − γPπ) V̂ (s)dπ(s).
and similarly if we break rπ as (I − γPπ)V π , for RπSIS[ŵ] we have: RπSIS[ŵ] = ∑ s (I − γPπ)V π(s)dŵ(s),
where dŵ = dπ0ŵ for short. Compare with Rπ = ∑ s (I − γPπ)V π(s)dπ(s), we can see the main difference between RπSIS and RπVAL with R π are they replace dπ and dŵ and V π with V̂ respectively. If we add them together and minus the connection estimator, we have we will have: RπDR[V̂ , ŵ]−Rπ =RπSIS[ŵ] +RπVAL[V̂ ]−Rπbridge[V̂ , ŵ]−Rπ
= ∑ s ( (I − γPπ)V π(s)dŵ(s) + (I − γPπ) V̂ (s)dπ(s)
− (I − γPπ) V̂ (s)dŵ(s)− (I − γPπ)V π(s)dπ(s) )
= ∑ s (I − γPπ) (V π − V̂ )(s)(dŵ − dπ)(s)
= ∑ s dπ0(s)εV̂ (s)εŵ(s)
=Es∼dπ0 [εV̂ (s)εŵ(s)] ,
where the third equation is because (I − γPπ) (V π − V̂ ) = (I − γPπ)V π − (I − γPπ) V̂ = rπ − (I − γPπ) V̂ . Similarly, the bias for RπDR and RπSIS can be calculated as:
RπSIS[ŵ]−Rπ = ∑ s (I − γPπ)V π(s) (dŵ(s)− dπ(s))
= ∑ s rπ(s)dπ0(s)εŵ(s) =Es∼dπ0 [εŵ(s)r π(s)],
and RπVAL[V̂ ]−Rπ = ∑ s (I − γPπ) (V̂ (s)− V π(s))dπ(s)
= ∑ s εV̂ (s)wπ/π0(s)dπ0(s)
=Es∼dπ0 [wπ/π0(s)εV̂ (s)].

heading: A.3 MORE DISCUSSIONS ON THE VARIANCE IN PROPOSITION 3.1

text:
Recall the proposition 3.1.
Proposition 3.1 (Variance Analysis). Assume R̂πDR[V̂ , ŵ] is estimated based on sampleD0 ∼ µ0 and Dπ0 ∼ dπ0 , which we assume to be independent of each other. We have
VarD0,Dπ0 [ R̂πDR[V̂ , ŵ] ] = VarD0 [ R̂πVAL[V̂ ] ] + VarDπ0 [ R̂πres[V̂ , ŵ] ] , (13)
with R̂πres[V̂ , ŵ] := R̂ π SIS[ŵ]− R̂πbridge[V̂ , ŵ] = ÊDπ0 [ ε̂V̂ (s)ŵ(s) ] and ε̂V̂ (s) the TD error of V̂ ,
ε̂V̂ (s) = r̂ π(s)− V̂ (s) + γP̂πV̂ (s),
with r̂π(s) = r(s, a)π(a|s)/π0(a|s), P̂πV̂ (s) = π(a|s)/π0(a|s)V̂ (s′). Therefore, VarDπ0 (R̂ π res[V̂ , ŵ]) can be small when V̂ is close to the true value V π , or ε̂V̂ (s) ≈ 0.
Proof. Since R̂πDR[V̂ , ŵ] = R̂ π VAL[V̂ ] + R̂ π res[V̂ , ŵ] and we have the assumption that the samples from D0 and Dπ0 are independent, the proposition comes immediately.
Intuitively, the variance of R̂πres[V̂ , ŵ] is less than R̂ π SIS[ŵ]. We want to quantitatively study every pieces of orthogonal randomness of R̂πres[V̂ , ŵ] and R̂ π SIS[ŵ] in details, and we state the analysis as the following theorem.
Theorem A.3. Let VarDπ0 [ R̂πres[V̂ , ŵ] ] be defined in Proposition 3.1, and suppose the normalization is constant (and hence an ordinary importance sampling which is unbiased). Then we can further break it into two terms
VarDπ0 [ R̂πres[V̂ , ŵ] ] = 1
n
( Var [ ŵ(s)εV̂ (s) ] + E [ ŵ(s)2 (δ1(s, a) + γδ2(s, a, s ′)) 2 ]) , (18)
where εV̂ (s) = V̂ (s)−r π(s)−γPπV̂ (s′) is the Bellman residual(not the empirical one), δ1(s, a) =
π(a|s) π0(a|s)r(s, a)− r π(s) is the randomness for action and δ2(s, a, s′) = π(a|s) π0(a|s) V̂ (s ′)−PπV̂ (s) is the randomness for transition operator over function V̂ . Both δ1 and δ2 is zero mean if we condition over s.
Compared with Var [ R̂πSIS[ŵ] ] we have:
Var [ R̂πSIS[ŵ] ] = 1
n (Var [ŵ(s)rπ(s)] + E
[ ŵ(s)2δ1(s, a) 2 ] ) (19)
Proof. R̂πres[V̂ , ŵ] can be written as
R̂πres[V̂ , ŵ] = 1
n
∑ ŵ(s) ( βπ/π0(a|s)(r + γV̂ (s ′))− V̂ (s) ) ,
where βπ/π0(a|s) is short for π(a|s) π0(a|s) . We can break βπ/π0(a|s)(r + γV̂ (s ′))− V̂ (s) into
βπ/π0(a|s)(r(s, a) + γV̂ (s ′))− V̂ (s)
=(−V̂ (s) + rπ(s) + γPπV̂ (s)) + (βπ/π0(a|s)r(s, a)− r π(s))︸ ︷︷ ︸
δ1
+γ (βπ/π0(a|s)V̂ (s ′)− PπV̂ (s))︸ ︷︷ ︸
δ2
=− εV̂ (s) + δ1(s, a) + γδ2(s, a, s ′).
where εV̂ = V̂ − r π − PπV̂ is the Bellman residual and the if we condition over s we have the expectations for δ1 and δ2 are 0. Also notice that if we condition over s then εV̂ (s) become a constant thus it is independent to δ1 and δ2. Thus we have:
Var [ ŵ(s) ( βπ/π0(a|s)(r + γV̂ (s ′))− V̂ (s) )]
=Var [ ŵ(s) ( −εV̂ (s) + δ1(s, a) + γδ2(s, a, s ′) )]
=Var [ ŵ(s)εV̂ (s) ] + E [ ŵ(s)2 (δ1(s, a) + γδ2(s, a, s ′)) 2 ]
Therefore we have: Var [ R̂πDR[V̂ , ŵ] ] = (1− γ)2
n0 Var[V̂ (s0)]+
1 n (Var [ ŵ(s)εV̂ (s) ] +E [ ŵ(s)2 (δ1(s, a) + γδ2(s, a, s ′)) 2 ] ).
For Var [ R̂πSIS[ŵ] ] we have:
Var [ R̂πSIS[ŵ] ] = 1 n Var [ ŵ(s)βπ/π0(a|s)r(s, a) ] = 1
n Var [ŵ(s)rπ(s) + ŵ(s)δ1(s, a)]
= 1
n (Var [ŵ(s)rπ(s)] + E
[ ŵ2(s)δ1(s, a) 2 ] ).
From the theorem we can see that the variance of residual comes from two parts, the majority part relies on the variance of |εV̂ (s)| is usually much smaller than r
π as the majority variance of state visitation importance sampling. When V̂ ≈ V π, εV̂ (s) ≈ 0, the variance of residual only comes from δ1(s, a) and δ2(s, a, s′).
In practice when we get trajectories data from π0, to get samples uniformly from dπ0 , we can either draw sample st depends on its discounted factor γt or add an importance weight γt as we did in our empirical estimator in equation (6) and equation (10).

heading: A.4 PROOF OF THEOREM 4.1

text:
Theorem 4.1 (Primal Dual). I) Define wρ/π0(s) = ρ(s) dπ0 (s) . We have
L(V, ρ) = RπDR[V,wρ/π0 ], and hence L(V, dπ) = L(V π, ρ) = Rπ, ∀ V, ρ,
which suggests that L(V, ρ) is “doubly robust” in that it equals Rπ if either V = V π or ρ = dπ .
II) The primal problem (14) forms a strong duality with the following dual problem,
Rπ = max ρ≥0 {∑ s ρ(s)rπ(s) s.t. ρ(s′) = (1− γ)µ0(s′) + γT πρ(s′), ∀s′ } , (16)
where T π is defined in (3).
Proof. The Lagrangian can be written as: L(V, ρ) =(1− γ) ∑ s µ0(s)V (s)− ∑ s ρ(s) (V (s)− rπ(s)− γPπV (s))
= ∑ s
(1− γ)µ0(s)V (s)︸ ︷︷ ︸ =RπVAL[V ]
− ∑ s
ρ(s) (I − γPπ)V (s)︸ ︷︷ ︸ =Rπbridge[V,wρ/π0 ]
+ ∑ s
ρ(s)rπ(s)︸ ︷︷ ︸ =RπSIS[wρ/π0 ]
= ∑ s (1− γ)µ0(s)V (s)− ∑ s (I − γT π) ρ(s)V (s) + ∑ s ρ(s)rπ(s)
= ∑ s ((1− γ)µ0(s)− (I − γT π)ρ(s))V (s) + ∑ s ρ(s)rπ(s).
We can see that the Lagrangian L(V, ρ) is actually our doubly robust estimator RπDR[V,wρ/π0 ].
From the last equation we can derive our dual as:
max ρ≥0 ∑ s ρ(s)rπ(s)
s.t. ρ(s) = (1− γ)µ0(s) + γT πρ(s), ∀s .

heading: B DOUBLY ROBUST ESTIMATOR FOR AVERAGE CASE

heading: B.1 PRIMAL DUAL FRAMEWORK

text:
We start from primal dual framework to get our doubly robust estimator similar to section 4. To estimate the average reward of a given policy π, we can consider solve the following linear programming:
max ρ≥0 ∑ s ρ(s)rπ(s)
s.t. ∑ s ρ(s) = 1, ρ(s) = T πρ(s), ∀s, (20)
where ρ(s) is the stationary distribution of states under Pπ, and the objective is the average reward given π.
Consider the Lagrangian of above linear programming: L(V, ρ, v̄) = ∑ s ρ(s)rπ(s)− ∑ s V (s)(ρ(s)− T πρ(s))− v̄( ∑ s ρ(s)− 1)
= v̄ − ∑ s ρ(s)(V (s)− rπ(s)− PπV (s) + v̄). (21)
From Equation (21) we can get the dual formula as:
min V,v̄ v̄
s.t. v̄ + V (s)− PπV (s)− rπ(s) ≥ 0, ∀s, (22)
where V (s) is the value function and v̄ is the average reward we want to optimize.
Notice that in average case, V π(s) can be viewed as the fixed-point solution to the following Bellman equation:
V π(s)− Es′,a|s∼dπ [V π(s′)] = Ea|s∼π[r(s, a)− v̄].
Note that this explains the constraint and only if we pick v̄ = Rπ, we can find a V to guarantee the constraint v̄ + V (s)− PπV (s)− rπ(s) ≥ 0 holds true.

heading: B.2 DOUBLY ROBUST ESTIMATOR

text:
We want to build the doubly robust estimator via the lagrangian. However, the Lagrangian consist of three term ρ, V and v̄. It is counter-intuitive if we already given an estimator of v̄ ≈ Rπ into our estimator.
A better way to solve this problem is to remove the constraint ∑ ρ(s) = 1, but we divide it as an self-normalization. Then our Lagrangian becomes
L(V, ρ) =
∑ s ρ(s)r π(s)− ∑ s V (s)(ρ(s)− T πρ(s))∑ ρ(s) .
which can be utilized to define the doubly robust estimator for average reward.
Definition B.1. Given a learned value function V̂ (s) for policy π and an estimated density ratio ŵ(s) for wπ/π0(s), we define
R̂πDR[V̂ , ŵ] :=
∑ s,a,r,s′∈D ŵ(s) ( βπ/π0(a|s)(r + V̂ (s′))− V̂ (s) ) ∑ s∈D ŵ(s) ,
where βπ/π0(a|s) = π(a|s) π0(a|s) .
Similarly to Theorem 3.1 we will have our double robustness for our average doubly robust estimator:
Theorem B.2. Suppose we have infinite samples and we can get
RπDR[V̂ , ŵ] = Es∼dπ0
[ ŵ(s) ( rπ(s)− V̂ (s) + PπV̂ (s) )] Es∼dπ0 [ŵ(s)] .
Then we have RπDR[V̂ , ŵ]−Rπ = Es∼dπ0 [ εŵ(s)εV̂ (s) ] , (23)
where εV̂ and εŵ are errors of V̂ and ŵ, respective, defined as follows
εŵ = ŵ(s) Es∼dπ0 [ŵ(s)] − dπ(s) dπ0(s) , εV̂ (s) = rπ − V̂ + P πV̂ −Rπ.
Proof. A key observation is that
Es∼dπ0 [wπ/π0(s)εV̂ (s)] =Es∼dπ [r π(s)− V̂ (s) + Pπŵ(s)−Rπ]
= (Es∼dπ [rπ(s)]−Rπ) + Es∼dπ [−V̂ (s) + Pπŵ(s)] =0
Thus we have
RπDR[V̂ , ŵ]−Rπ =Es∼dπ0
[ ŵ(s)
Es∼dπ0 [ŵ(s)] ( Rπ + εV̂ (s)
)] −Rπ
=Es∼dπ0
[ ŵ(s)
Es∼dπ0 [ŵ(s)] εV̂ (s)
]
=Es∼dπ0
[ ŵ(s)
Es∼dπ0 [ŵ(s)] εV̂ (s)
] − Es∼dπ0 [wπ/π0(s)εV̂ (s)]
=Es∼dπ0 [ εŵ(s)εV̂ (s) ] .
Similar to discounted case we have RπDR[V̂ , ŵ] = R π if either ŵ or V̂ is accurate.

heading: C EXPERIMENTAL DETAILS

heading: C.1 TABULAR CASE: TAXI

text:
Behavior and Target Policies Choosing We use an on-policy Q-learning to get a sequence of policy π0, π1, ..., π19 as data size increases. We pick the last policy π19 (almost optimum) as our target policy and π18 as our behavior policy to guarantee that those policies are not far away. We set our discounted factor γ = 0.99.
Train V̂ and ρ̂ Separate from testing, we use a set of independent sample to first train a value function V̂ and a density function ρ̂. Both V̂ and ρ̂ have bias due to finite sample approximation.
For training V̂ and ρ̂, we choose to use Monte Carlo method to estimate V̂ and ρ̂. We first use the finite samples to get an estimated model T̂ (s′|s, a) and rewards function r̂(s, a) and d̂0. Then we solve the following linear equation (by iteration like power method, which is actually Monte Carlo):
V̂ (s) = ∑ a π(a|s)Q̂π(s, a),
Q̂π(s, a) = r̂(s, a) + γ ∑ s′ T̂ (s′|s, a)V̂ (s′),
ν̂(s, a) = ρ̂(s)π(a|s), ρ̂(s) = (1− γ)d̂0(s) + γ ∑ s,a T̂ (s′|s, a)ν̂(s, a).
Estimate Rπ Using V̂ and ρ̂ We put V̂ and ρ̂ into the Lagrangian as equation (15) as our doubly robust estimator. For those states we haven’t visited, we set V̂ (s) and ρ̂(s) as 0 and we self-normalized the ρ̂ to get a fair estimation.

heading: C.2 CONTINUOUS STATES OFF-POLICY EVALUATION

text:
Evaluation Environments We evaluate our method on two infinite horizon environments: PuckMountain and InvertedPendulum.
Puck-Mountain is an environment similar to Mountain-car, except that the goal of the task is to push the puck as high as possible in a local valley whose initial position is at the bottom of the valley. If the ball reaches the top sides of the valley, it will hit a roof and changes the speed to its opposite direction with half of its original speeds. The rewards was determined by the current velocity and height of the puck.
InvertedPendulum is a pendulum that has its center of mass above its pivot point. It is unstable and without additional help will fall over. We train a near optimal policy that can make the pendulum balance for a long horizon. For both behavior and target policies, we assume they are good enough to keep the pendulum balance and will never fall down until they reach the maximum timesteps. We use the implementation from OpenAI Gym (Brockman et al., 2016) and changing the dynamic by adding some additional zero mean Gaussian noise to the transition dynamic.
Behavior and Target Policies Learning We use the open source implementation2 of deep Qlearning to train a 32 × 32 MLP parameterized Q-function to converge. We then use the softmax policy of learned the Q-function as the target policy π, which has a default temperature τ = 1. For the behavior policy π0, we set a relative large temperature which encourages exploration. We set the temperature of the behavior policy τ0 = 1.88 for Puck-Mountain and τ0 = 1.50 for InvertedPendulum respectively.
Training of density ratio ŵ(s) and value function V̂ (s) We use a seperate training dataset with 200 trajectories whose horizon length is 1000 to learn the density ratio ŵ(s) and the value function
2https://github.com/openai/baselines
Algorithm 2 Optimization of density ratio ŵ Input: Transition data D = {si, ai, s′i, ri}ni=1 from the behavior policy π0; a target policy π for which we want to estimate the expected reward. Discount factor γ ∈ (0, 1), starting state D0 = {s(0)j }mj=1 from initial distribution. Initial the density ratio w(s) = wθ(s) to be a neural network parameterized by θ, f(s) = fβ(s) to be a neural network parameterized by β. We need to ensure that the final layer of θ is a softmax layer. for iteration = 1,2,...,T do
Randomly choose a batchM⊆ {1, . . . , n} uniformly from the transition data D and a batch M0 ⊆ {1, . . . ,m} uniformly from start states D0. for iteration = 1,2,..., K do
Update the parameter β by β ← β + β∇βL̂(wθ, φβ), where
L̂(wθ, fβ) = 1 |M| ∑ i∈M ( (w(s′i)− γw(si) π(ai|si) π0(ai|si) − 1 2 f(s′i))f(s ′ i) ) −(1−γ) 1 |M0| ∑ j∈M0 f(sj)
end for Update the parameter θ by θ ← θ − θ∇θL̂(wθ, fβ).
end for Output: the density ratio ŵ = wθ.
Algorithm 3 Optimization of value function V̂ Input: Transition data D = {si, ai, s′i, ri}ni=1 from the behavior policy π0; a target policy π for which we want to estimate the expected reward. Discount factor γ ∈ (0, 1). Initial the value function V (s) = Vφ(s) to be a neural network parameterized by φ, f(s) = fβ(s) to be a neural network parameterized by β.
for iteration = 1,2,...,T do Randomly choose a batchM⊆ {1, . . . , n} uniformly from the transition data D. for iteration = 1,2,..., K do
Update the parameter β by β ← β + β∇βL̂(Vφ, φβ), where
L̂(Vφ, fβ) = 1 |M| ∑ i∈M (( Vφ(si)− π(ai|si) π0(ai|si) (ri + γVφ(s ′ i)) ) fβ(si)− 1 2 fβ(si) 2 ) end for Update the parameter φ by φ← φ− φ∇φL̂(Vφ, fβ).
end for Output: the density ratio V̂ = Vφ.
V̂ (s). For the training of density ratio, we adapt the algorithm 2 in Liu et al. (2018a) to train a neural network parameterized wθ(s). Instead of taking the test function f(s) into an RKHSHK, we parameterize the test function f(s) = fβ(s) to be a neural network with parameter β, and perform minimax optimization over parametr θ and β. A detail description can be found in Algorithm 2.
Similarly, for the training of value function, we use primal-dual based optimization methods (Dai et al., 2018; Feng et al., 2019) to minimize the bellman residual:
min φ max fβ∈F
1 |M| ∑ i∈M (( Vφ(si)− π(ai|si) π0(ai|si) (ri + γVφ(s ′ i)) ) fβ(si)− 1 2 fβ(si) 2 ) ,
where Vφ(s) is the parameterized value function and fβ(s) is the test function. We also perform minimax over parameter φ and β. A detail description can be found in Algorithm 3.
For the network structures, we use 32×32 feed forward neural networks to parameterize value function Vφ and density ratio wθ(s), and we use one hidden neural network with 10 units to parameterize the test function fβ(s). We use Adam Optimizer for all our experiments.
Estimate Rπ using V̂ and ŵ Given data samples from the policy π0, We can directly use R̂πDR in equation (11) to estimate Rπ .

heading: D ADDITIONAL EXPERIMENTAL RESULTS

text:
We add a standard model-based baseline in Figure 4 following the same procedure as Liu et al. (2018a).3 Figure 4 shows that the performance of the model-based approach largely depends of the size of the data, which is consistent with that in Liu et al. (2018a).
3https://github.com/zt95/infinite-horizon-off-policy-estimation.

title: DOUBLY ROBUST BIAS REDUCTION IN INFINITE HORIZON OFF-POLICY ESTIMATION