Independence-aware Advantage Estimation
Authors: Pushi Zhang
Li Zhao
Guoqing Liu
Jiang Bian
Minglie Huang
Tao Qin
Tie-Yan Liu
Venue:  (2020)
Keywords: Reinforcement Learning
Advantage Estimation

Abstract: 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. 

Under review as a conference paper at ICLR 2020
INDEPENDENCE-AWARE ADVANTAGE G ESTIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Most of existing advantage function estimation methods in reinforcement learn- ing suffer from the problem of high variance, which scales unfavorably with the time horizon. To address this challenge, we propose 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. particular, the recognized independence property can be naturally utilized to con- struct a novel importance sampling advantage estimator with close-to-zero vari- ance 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 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.
INTRODUCTION
Policy gradient method (Sutton et al. 2000) and its variants have demonstrated their success in solv- ing a variety of sequential decision making tasks, such as games (Mnih et al. (016)) 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 variance- minimized form (Bhatnagar
get stable policy gradient estimation (Mnih et al.) 2016 Schulman et al., 2015a b) 2017). p. For policy т and a state-action pair (s, a), all these works estimate the advantage function (s, a) by subtracting an estimate of the value function V V*(s) from the estimate of Q-value (T a). The estimation of (s,(sa) a) or V*((s) typically involves discounted sum of future rewards, which still suffers from the high variance especially when facing the long time horizon.
al.] 2008),
Meanwhile, in many real-world reinforcement learning applications, we observe that not all future rewards have dependency with the current action. For example, consider simple multi-round game where at the end 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 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 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 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 sam- pling. The estimator formalizes 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-Carla estimator with the proposed estimator by decomposing the reward into two estimators and learning the optimal

---

Under review as a conference paper at ICLR 2020
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-Carke estimator to reduce the potential high variance caused by importance sampling. Details of method are described in Section 3 [
Empirically, show that our estimated advantage function is closer ground-truth advantage function A" than existing advantage estimation methods such as Monte-Carlo and Generalized Ad- vantage Estimation (Schulman
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 g
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 Monte- Carlo estimator which do not contribute advantage function.
We propose practical advantage estimation method to identify and utilize the indepen- dence property environments, which achieves better performance than other advantage estimation methods in both tabular settings and function approximation settings.
2 BACKGROUND
2.1 NOTATIONS & PROBLEM SETTINGS
We consider a finite-horizon Markov Decision Process defined by (S, R, Po. 7, T, where the set of states, is the finite set of actions, P S A S + R denotes the transition probability, R S A + IR denotes the reward function, Po S + IR denotes the distribution of initial state So. (0, 1] is the discount factor, T is the total time steps. We denote St, At, R₂ the random variable of state, action, reward at time f, and T. == (St, A,, R2, St41, Ar, Rr) as trajectory starting from time
S x A + R as a stochastic policy, and use the notation of Q" (s,, az). V*(ss). AT AT (st, (x) as state-action value function, state value function and advantage function respectively. In the following discussions, we will recognize (s ax) as a constant state-action pair whose advantage function needed to be estimated.
We denote
2.2 ADVANTAGE FUNCTION ESTIMATORS
Monte-Carlo estimator AMC of advantage function A" A3(ss,, az) is formalized below:
AMC = - Vo()))
Ret where ~ pa (Telss,
k=
Here (o(ss) denotes the function approximator of value function (*()s. We use ~ (T(lss, to denote that trajectory tr is generated by policy æ from 8t, az.
Some previous work focuses on reducing the variance of AMC at the cost of introducing bias (Schul- man et al. 2015b), by using the n-step TD estimator and GAE estimator of advantage function (St, d:):
n-1
-Vo(+))
Re+k + Vo if
A TD)))
k=0
AMC
if n > T -
GAA = (1 A)
n A TD(++1)
where ~ pd (T ot).
0=
2

---

Under review as a conference paper at ICLR 2020
3 UTILIZING INDEPENDENCE PROPERTY IN ADVANTAGE ESTIMATION
In many cases, we can utilize the independence between current action and future states to avoid unnecessary parts of variance in the Monte-Cart Carlo estimators. Consider the example where we have current state 9; whose advantage functions with respect to all actions are needed to be estimated. For set of St+k which can be reached from $1, we have independence property such that the probability Pa (Se4&] St, (x) is a constant with respect to O₁, Although the Monte-Carlo return estimator from $14& may have large variance, it is clear that the return after reaching 8t+ gives no contribution to A" (8), (g) in this case.
In this section, propose the variance in Monte-Carlo return estimator after St4k by utilizing independence property, exactly as we described above. In later discussions, we will name the proposed estimator importance sampling ad advantage estimator.
advantage estimator based importance sampling, which removes
By importance sampling approach, we present our way derive A A ac) into a form which utilizes independence property:
A (" = (x)l,,))))))))
Σ 7tth Betk
- (raoee(rrlee)
Σ
Re+#
km
(*( A4tk|se; az) 1)
Σ
7t Reth
(1)
p (T(S++k A
To briefly summarize our derivation, we perform importance sampling in every future time t k estimating the discounted reward 7 Re+* in distribution px (S A (se. a,) by sampling on
distribution (S Ar+ 8t). It is worth noting that when k: 2 1, Ac-R independently sampled by S.+k. and we are able to omit Ae4 in the probability ratio.
For the simplicity of discussion, we will use the following definition:
C (St, at, Sttks ac+s) = pd (8E4k; 0e+k(81,
P* (* (#41445:
where we call C (st, at, Setk, a++x) the dependency factor, since the value captures how taking a specific action ag changes the probability of reaching future state-action pair (St+): 0++k)- clear from equation [ and equation / that future state pair St+. that has dependency factor C (Se, de, St4k, ac+k) close to O has small contribution to A de), which further demonstrates that the rewards from independent future states do not contribute to advantage estimation, even Monte-Cate Carlo return signal has high variance. In practice, dependency factor C by data samples. We propose a novel modeling method and a temporal dif- ference training strategy to solve this problem, which is detailed in Section
face the challenge to estimate the
4 OPTIMAL COMBINATION WITH MONTE-CARLO ESTIMATOR
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 ad advantage estimator may badly deal with those rewards with large dependency factor, which can increase the variance in estimation. To illustrate, consider we have whose advantage functions with respect to all actions are needed to be estimated. The Monte-Carlo return starting from 8, following и is close to a constant q, while there large gap between pa (St+ k|,,,, az) and pa (S.+alss). 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, 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 control variate, producing an estimator with less variance. Inspired by that, we decompose the reward into two estimators with reward decomposition model, and learn the reward decomposition model by minimizing estimation variance.
The following theorem demonstrates our derivation combine two estimators:
3

---

Under review as a conference paper at ICLR 2020
Theorem 1. Suppose ri+k
R(re+a/st, au Tetk), where R is any probability distribution. Then
(Resk - -maw
Σ (Resa -rekk) reta))
A" (st, ae) = ((
+ (TpoP
Σ re (81, as Setky
The proof of theorem is provided in Appendix A.1 The sum of all the terms containing T+++ in equation 3 constructs a control variate with zero expectations, while the expectation of rest of terms containing Re+* is the value of advantage function A (s,,,a)), From equation B we find that r*+A determines the way in which rewards are divided into two estimators. If rc- is close to O, rewards divided into the Monte-Carlo estimator; if r is close RE+K. rewards are divided into the importance sampling advantage estimator. We parameterize T as Tt+k,v- seeking to optimize vi to gain advantage estimator with minimized variance. In practice, we represent
by a neural network Tw (St, a, Sitk, A Retk, k), whose architecture is shown by Figure 6 in the appendix.
For simplicity, we will use (T,) and (T), az) to denote two random variables inside of expecta- which is written by:
tion in equation 3
Je(T)) := == = (RRei rets); (o(T,
reta (St, at, St4k, Al+k)
(4)
1=0
4=0
We use Var (St, ae) to denote the variance of advantage estimator derived from equation 3 Though we are not able to write the closed-form variance 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
Varg as) < 3 Var (Tx( + Var,, an [Jo(T))] + Var,,
[ an)
(5)
Based equation 5 we further derive the upper bound of variance which is friendly to optimize:
Eue s.) Var (Se, as) S (Val)..
(Jo(Ta) + B(ass Var
Ls (Te az)
We seek to optimize to minimize the variance upper bound shown in equation To achieve this, we firstly use two value function approximators Var, (st). hay (St, at) to approximate the expectation of two estimators respectively:
V (st) ss (x( (Jo(TT)) In In, a.) so (npr((
[Tr at)
To approximate the expectation, we use SGD to minimize the mean squared error. The parameter update process can be finally expressed as follows, where aw represents the step-size:
w/ = wi + Oun (Fs((T)) - Vay (st)) V Van, (8t), T ~ Pa (Te(8=)
(8)
w/g w2 + anw (I a.) Lwz (st, a:) wy w ( (St, ot); Te pd (Tels:)
(9)
If we assume that Vn,, (st) and Iw, (st, at) accurately represent the expectation, then we get the gradient to optimize vi as follows, in order to minimize the upper bound of E,, ~((eloo)))) (st, at):
[Jo(To) + (Eaent(ar)a.) Var (m.ls)) (()(taa)))
V (tela))
2V (J P=(
Ve, (s))) + Σ
- ai))
(10)
We can use SGD to optimize a expressed by equation 11 where On represents the step-size:
v/ vb + a (()
Vi,
Σ t ((alss)(( (8,, V te (=(r((s))
(11)
a
4

---

Under review as a conference paper at ICLR 2020
Here will illustrate why performing gradient descent leads to an advantage estimation with lower variance. For a single "t+k,y, the gradient component in the first term of equa- tion II pushes the Tt+k, to change towards the direction the mean total return; meanwhile, the second term of equation 11 counteracts the gradient the first term, preventing T++,,y from constructing constant return by the restriction in variance of importance sampling estimator Ex 7 Te+kkp 7 Cg (st, at, St++). When we have the independence property in environments (i.e. the value of Cg is close to zero), the counteraction effect in the second term will disappear. With gradient in the first term, T++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:
AIYE == (T() Ve, (st) + Iwo (st, ar), where Tι P" (Te
(12)
DEPENDENCY FACTOR ESTIMATION
The final challenge in our method 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 hard estimate the transition probability in equation 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 I3 whose proof shown in Appendix A.3
pa (s1+k: 14,x PR (s ac+k(s:)
p (a (c+k)
pd (a 814x) π (at(s))
if
(13)
(
In practice, ing (St, az, Sc+R) == Po(a.js.. to give an approximation of C*, We call Pa Pa 8 k.)
action classification model Pa(a:) 8t, Sitk, k) to represent pat (at (0e) 8144),
dependency model in later discussions.
Similar to the derivation previous work (Liu et al. 2018), we show that the dependency model can be learned in an temporal difference manner:
Da (ae) Se; k24 EsLe,, (s (o44e)))) p (at St
ki (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 clear that the samples of distribution pa (*t+k, (8t+ 8t) can be collected by directly rolling out policy then we are able to train model Pa by minimizing temporal difference error. We use a mixture of temporal difference tar- get and Monte-Carle target train model Cg. which is detailed in Appendix B Empirically, demonstrate the effectiveness of our approach to accurately estimate dependency factor in section
8.
6 ALGORITHM
In this section, we present crucial algorithms details of the method presented in Section and
6.1 MODEL DEPENDENCY AND PSEUDO-CODE
We illustrate the general framework of our algorithm shown by Figure | 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 In, and Vaz are trained by SGD on MSE loss, shown in equation and equation 9 given the the reward decomposition rv as input. The reward decomposition model ry is also trained by SGD shown in equation II given the output of I,, and Vnng The podudo-code of our algorithm provided by Algorithm
5

---

Under review as a conference paper at ICLR 2020
Ceroaing
deserdeecy (ep)
(e Weiko!
Compute Acuntagge
Vensadul
Model
PNI
Follet
Figure 1: Model Dependency Graph.
Algorithm Policy Optimization Algorithm by Independence-aware Advantage Estimation
Initialize policy parameters 0, dependency model parameters d, decomposition model parame- ters v. and value function parameters W1, W2.
2: for each iteration do
3: Sample trajectory with policy ne
4: Update & by temporal difference learning
5: Update w1, W2 minimize mean squared emror by equation 8 and equation 9
6: Update f/ to minimize variance upper bound by equation 11
7: Compute advantage estimation ALAE at each time-step by equation I2
8: Update by Proximal Policy Optimization
9: end for
6.2 COMPUTATIONAL COMPLEXITY
There might be concerns about computational complexity for training dependency model and reward decomposition model, since the training requires (TT) number (st, $c+*) pairs as training sam- ples. We apply 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 ap- proach PPO algorithm. We apply our method into the truncated trajectories by considering reward (s(s, at) at the last step. The reward decomposition model also considers the decomposi- tion over the final reward (s(s.a0))
Block-wise Training. When training dependency model and reward decomposition model, we provide total of 1282 numbers of (st, 81+4) pairs, and accumulate gradient for every valid (St, St-k) pair. Only 128 x 2 times of forward and backward passes in CNN feature extractor are computed though we deal with squared number training data, making our method computa- tionally efficient. Our method requires less than times training time compared to PPO algorithm.
7 RELATED WORK
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 optimize parameterized policy without focusing the selection of estimator. Among these works, TRPO (Schulman et al,, (2055)) and PPO (Schulman et al., (017) are part of the recent works that reaches ttate-of-the-ane performance variety of tasks.

---

Under review as a conference paper at ICLR 2020
Some of previous works have shown that RL algorithm tends to be unstable when planning horizon is long (Jiang et al. 2013). Another series of works (François- Lavet et al., 2013: Xu et al. 2018 focus on how to select discount factor y improve the performance of RL algorithm. Our method suggests another solution to the problem in RI, 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 train- ing 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- off-policy value estimation: another previous work (Grathwohl et al.) (017) 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 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.
EXPERIMENTS
In our experiments, provide empirical results to answer the following questions:
Can our dependency model training method in section precisely estimates the dependency factor C"T, 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 esti- mation 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 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- trudh--tuhhhhhh 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 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- Monte-Carlo advantage estimation and generalized advantage estimation, IAE method makes policy optimization process more sample-efficient.
8.1 ENVIRONMENT SETTINGS
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 tab- ular 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. De- tailed descriptions of transition probability and reward settings are provided in Appendix C.I
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.
7

---

Under review as a conference paper at ICLR 2020
6.2
620
6.0
61
0.2
0.27
(a)
(b)
(c)
Figure 2: Results on dependency factor modeling. (a): The top and bottom image respectively illus- trate 8; and 84+k in the case study, and here we set to be 7. (b): Dashed lines show the true dis- tribution of Pd (ag $t, St-&); solid lines show the dependency model prediction Pa(ay] $t, Sc+ks k); x-axis represents the number of training iterations of dependency model. Four different colors rep- resent four different actions. Blue line shows the KL divergence between predicted distribution and true distribution. (c): The blue line shows the mean KL divergence between p" (ax St, S14k) and Po (as St, St4k, k) the dataset of random (st, St+k) pairs, averaged in 10 runs.
Connected-low
Isolated-low
Connected- -igh Isolated high
MC
0.63
1.66
6.21
16.58
IS
1.43
8.68
1.45
8.63
IAE
0.59
0.60
0.68
0.71
Table 1: Standard derivation of various estimators in different transition probability settings (con- nected and isolated) and different reward settings (low-variance and high-variance).
As illustrated 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 randomly repositioned. We use different reward settings: per-step punishment setting and no punishment setting, which is detailed in Appendix C.I
The hyper-parameterr and network architectures use in experiments presented in Ap- pendix
8.2 DEPENDENCY FACTOR MODELING
In this section, we investigate our estimation of dependency factor C",, and show the general simi- larity between our estimation and ground-truth C We train our model Co by data generated by fixed uniform random policy Figure 2a 2nd 2b show the case where the dependency is precisely captured: given the future state $1+k shown in Figure 2a the model Pa St, 8L+k, k) correctly predicts down and right action that more likely lead current state 8; future state 8t+E- We also build a dataset consisting of 300 random 8t+k) pairs, where k is uniformly sampled from to 30. We evaluate the
KI. divergence between ground-truth pa (ay]8t, 8t+&) and prediction Po Po St, St+k, k) averaged in 10 runs, as shown in Pigure[2c] The mean KI. divergence decrease to relatively small value during training, showing that the dependency model P& leads to generally precise estimation of dependency factor C*
8.3 THE VARIANCE AND ACCURACY INDEPENDENCE-AWANN ADVANTAGE ESTIMATION
We evaluate the variance of IAE estimator r(st, $t+*) for 10000 episodes and then test the advantage estimator by performing advantage es- timation multiple times to get the estimation variance. We compare the variance of IAE estimator with Moote-Carlo advantage estimator (MC) and importance sampling advantage estimator (IS). In this experiment, the precise value of dependency factor for IS and IAE estimator. Table
variety of finite-state MDP settings. We train
8

---

Under review as a conference paper at ICLR 2020
Sread Hoetscol
9
20000
40030
1000
100833
20000
40930
00030
50083
33300
(a)
(b)
Figure 3: (a): Mean squared error two value functions Voy and Tu averaged in 10 runs on Pixel Grid World. Green and red lines show the MSE of Vw, and wuy respectively, when T is fixed; blue and orange lines show the MSE of Vw, and Lw respectively. when ry is trained by our method. (b): The cosine similarity between advantage estimation and ground-truth advantage function. We compare IAE estimation, Monte-Care Carlo estimation and GAE estimation.
car
-2-
Tresston 1076
Tenoucpa" 3076
(b)
Figure 4: Overall performance curve. Figure (a) and (b) respectively show the training
Pixel Grid World environment in per-step punishment setting and no punishment setting, averaged in 10 random seeds. In per-step punishment setting agent gets negative rewards before reaching goals, while in no punishment setting agent gets no reward before reaching goals.
demonstrates the standard derivation advantage estimation. both environments suitable for MC estimation and ones suitable for IS estimation, method gives estimation with less variance than both MC and IS method. some cases, IAE estimation dramatically reduces the variance 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, ward 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 without training Tú. When the reward decomposition model Te is fixed, the loss of value function training keeps to be high because of the stochasticity of Monte-Carke return signal, while reward to be distributed into importance sampling advantage estimator, making the mean squared error of value function to reduce. In Figure 33b we show that IAE estimation has much higher cosine similarity to ground-trum -ruth advantage function, compared with Monte-Carle and GAE estimation.
shown in Figure 3a We initialize
method, the T makes
Besides, we investigate how independence property reduces the variance estimation by visualizing the reward decomposition in Pixel Grid World Environment, which is detailed in Appendix C.3
8.4 PERFORMANCE OF POLICY OPTIMIZATION
We run Proximal Policy Optimization algorithm with IAE advantage estimation method, and com- pare the result to PPO algorithm with Monte-Carlo and GAE advantage estimation. Figure shows

---

Under review as a conference paper at ICLR 2020
the result on two different reward settings. Compared with Monte-Carke and GAE estimation, IAE estimation makes the policy improvement process more sample-efficient
CONCLUSIONS
In this work, we addressed the large variance problem advantage estimation for policy gradient methods. We proposed a novel advantage estimation method by importance sampling, which iden- tifies 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 Carle and Generalized Advantage Estimation.
There few directions to explore in the future. First, only considered problems with discrete actions in this work, and we will extend our method to problems with continuous actions. Second, will test algorithm more reinforcement learning environments, such Atari games and continuous control tasks.
REFERENCES
Shalabh Bhatnagar, Mohammad Ghavamzadeh, Mark Lee, and Richard S Sutton. Incremental nat- ural actor-critic algorithms. In Advances in neural information processing systems, pp. 105-112, 2008.
Vincent François- Raphael Fonteneau, and Damien Ernst. How to discount deep reinforce- ment learning: Towards dynamic strategies. arXiv preprint /5/.020 2015.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. arXiv preprint arXiv:1711.00122 2017.
Josiah P Hanna, Philip S Thomas, Peter Stone, and Scott Niekum. Data-efficient policy evaluation through behavior policy search. In Proceedings of the 34th International Conference on Machine Learming- Volume 70, pp.
JMLR. org, 2017.
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon on model accuracy. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp. 1181-1889 International Foundation for Autonomous Agents and Multiagent Systems, 2015.
Hajime Kimura, Shigenobu Kobayashi, et al. An analysis of actor-critic algorithms using eligibility traces: reinforcement learning with imperfect value functions. Journal of Japanese Society for Artificial Intelligence, 15(2):267-275, 2000.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509 559900297, 2015.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off- off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5356- 5366, 2018
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602. 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, 1928-1937, 2016.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897, 2015a.
10

---

Under review as a conference paper at ICLR 2020
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438, 2015b.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural informa- lion processing systems, pp. 1057-1063, 2000.
Zhongwen Xu, Hado van Hasselt, and David Silver. Meta-gradient reinforcement learning. arXiv preprint 1rxiv:/8050090000 2018.

---

Under review as a conference paper at ICLR 2020
A PROOFS
A.1 PROOF OF UNBIASEDNESS
In this section, show the proof of theorem 1 which demonstrates that any choice of ri+k will not bias the combined estimator as long as r is function of St, and Tt+k-
Theorem 1. Suppose re+k R((e+x|55, at Te+k), where R any probability distribution. Then
A" (s(st.a)) ue) = En
Σ
(Re++ rata))
Er Pa
Σ ( reta)
rh (sr, as, Setnr
(1)
Pd (si+k: 06tx|s8, 1.
where C% 0c, a4+k)
p= ( as+b(s))
Proof. Denote r(st, an T+++) E [re+k aes Te+R).
Since (st,,, az) can be written by
T-t Σ k=
A (s;, az) = EE (mlla,)))
Σ tht RE+K
7h Re-k
We only need to prove that
E (T((s))))
y T (st, (s,, as Si+R Acta)
T-
E Pn
Σ rutk k=
Σ k=0
y reth
(2)
We have derivation that
T
y Fre+& ar, Setk, Am*s) + Bn-Pr(rule)
Σ retk
* (1 Cs an Sut Acttl))
Bruye P (r(ses
(r(s, ai Teth (1
844k, ((x)) (se+k, (
p (3 (444 pa (Stt), (e4k)s))ds pa (8ttk, (
h
B Bruss Pa [r(s,, an T++)]
Σ
Σ
E Br Mo [r(s, ar, T(+)) pd (8 actb/s at dd)sk
K=O
T-
= EE (T))s,a))
k retk
which proves equation 2 and further proves theorem 1.
12

---

Under review as a conference paper at ICLR 2020
A.2 UPPER BOUND OF VARIANCE
In this section, show that the if the sum of three random variable in equation g 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 We begin with the following lemma:
Lemma 1. Suppose X1, ..... Xn are random variables. Then
Var
Σ
X
S
Var X,].
Proof.
Var
X
Var[X;] +2
Σ
Cor[X,,
1=1
1gisjsn
Var +2
Σ
Var(XX]Var[())
1sijjsn
Then we have
n
Σ Var [X,] Var Σ Xi
2 (n 1)
Var[X;] -2 Σ
V Xa Var[X,]
i=1
Isicisn
2 Var(Xy)]
Var(X.
0,
15Kcj5n
which proves lemma 1.
From lemma it clear that the variance of advantage estimation 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 in the main body, which is written by:
pa (sttk, 0244 (8; ar)
pr (at (st, St4k, a14k).
pd ("r 8144) π (ag(s=))
if 2
(3)
Ps (Bt4k, (1+1(81)
(ap(s))
Proof. We separately prove the first and the second equation. The first equation is proved by:
p (5 act
p (St4k) Ge+k, St, at)
pT
pa (8ttk; (1854,,,4428811 (142(88)
Pa Psts, at)
ps (81+k, aetk, 81)
Pd ("((sk St, 0t)
(T((s)
p (= 81)
p (t))
pa (aclss S14k,
(())))))
13

---

Under review as a conference paper at ICLR 2020
The second equation is proved by:
P 01, 8ttk; Octk)
pd (aclls Setk, actk)
(r Sitk: ax+k)
Pf (F Sit Pn (ae+klse, de s(tk)
(5 8(th) PM (aL+ 8e, S6th)
p5 ot, 81th )
pr (st, S1th $Ltx) (
P (st, 81tk) P (c.)s..844a))
pa (8r, 81tk)
Thus, proved that a++A can be abandoned from the probability condition when & 2 1. When k = O, the conditional probability can be directly given by a closed form solution:
pd (A = alst, Sitk acts) =
1,
Ge+k
0, + at+k
A.4 DEPENDENCY FACTOR ESTIMATION
We prove that the dependency factor can be learned an inverse temporal difference manner in this section, which is formulated by equation i4 the main body:
St+kg)
Ea (r ( (etkg (5 St, St k2 kn 2
Proof.
E Ba p (5 la (21k)) P (aels S(tki)
pd (s1tks 8t 88- 84) pd (arlst, 8 ddstth
p ; S14b2, st)
p Se, S1t ds1+hi pa (ot,
pm (T 5t)
P 8t 8ttks pa (St4ky ds)
p (T(stt2::8)) 8t)
p (1, 81tki) Pit (8r+baz 8t)
p (St+k2 St4 ds
p (at, 8t: 814kj, 8 8tt detthi (= 81)
pdt (at, St, 81tk2) pd (111)))
Px (81+k2; 81)
B TEMPORAL DIFFERENCE LEARNING OF DEPENDENCY MODEL
We use a mixture of temporal difference and Monte-Carlo training target to train dependency model. For trajectory sample every valid (t, k) pair, and use cross-entropy loss to update Φ. For the Monte-carlo training target, directly one-hot probability distribution of action a; the ground- tround-truth; for the temporal difference training target, we use distribution Po (at [st 81+k-1, k - 1) as the ground-truth. We mix the two training target with 0.85* weight on Monte-Carlo target and 1 0.85* weight on temporal difference target to achieve the optimal bias-variance tradeoff.
{s,, a, Tr) provide training target for Po(ar]s,, St+k, k) for
14

---

Under review as a conference paper at ICLR 2020
Figure 5: Observation in Pixel Grid World.
C EXPERIMENT
C.I ENVIRONMENT SETTINGS
Finite-state MDP settings. We construct different 3-state MDPs with different transition proba- bility 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 distribu- tion. We use the following transition matrix for connected settings:
0.2
0.5
0.37
p
0.5
0.3
0.2
0.2
0.2
0.6
Isolated settings, where there 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:
0.9
0.05
0.057
0.45
0.45
0.05
0.05
0.9
In connected settings, the n-step transition probability very close into stationary distribution, re- sulting in 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-Cane return signal is large compared mean total return. We the following reward function for high variance settings:
1]
Low-variance settings, where the variance of Monte- Carte return signal is small compared to mean total return. We use the following reward function for low variance settings:
R= 22.1
2 1.9]
clear that Monte-Carlo advantage estimator will have larger variance in high-variance settings than in lowvaariance settings.
Pixel Grid World environment. We build Pixel Grid World environment where observations are provided by high-dimensional images. As shown in Figure 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 actions Pixel
8 8, and observations provided by 128 128 x 3 RGB pixels. There Grid World, making the agent to move toward different directions. We use two reward settings in experiments:
Per-step punishment setting, where agent gets = - -0.03 reward in every step before reaching goal, and r 0 reward every step after reaching goal. Agent gets r 1 reward when reaching goal for the first time.
No punishment setting, where agent gets r reward when reaching goal for the first time, and gets reward otherwise.
15

---

Under review as a conference paper at ICLR 2020
Fecuue
shan paraaters
P6
ertoeciig
(a)
Pank
Feature Extratoo
parsmeters
Ria
Festure Extractor
ombodd
(b)
Figure 6: Network architecture for dependency model and reward decomposition model.
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 rounds.
C.2 HYPER-PARAMETER SETTINGS AND NETWORK ARCHITECTURE
We use 7 = 0.999 for all experiments in policy optimization. For GAE estimator, we use the default settings A = 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 epochs. We use global Adam optimizer for training both dependency model and reward decomposition model, and set learning rate to be 2.5 x 10-1 For initialization, scale for all layers, except that we initialize the last weight matrix of to be zeros. For training Po st, St+k, k), weight the MC loss by 0.85* and TD loss by 0.85* and use the mixture settings with
use orthogonal initialization with v2
loss to train dependency model. For PPO algorithm, we use the same OpenAl Baseline.
We use the network architecture shown in Fig dependency model and reward decomposition model. We use the same CNN feature extractor settings the settings in the OpenAl Baseline. For time embedding, we store embedding vector of 128 dimensions for each E (1,2, ... 128) separately.
16

---

Under review as a conference paper at ICLR 2020
Dependence Fector
RAY
0.8
0.4
0.0
(a)
1.0
Mamoed Bd
0.6
0.2
-0.2
20 40
100
120
(b)
Figure 7: Case study reward decomposition model. We fix state-action pair (St, 0z) and visu- alize reward decomposition for every future reward. The x-axis represents the interval from current state to future states St+kk, green line represents the dependency factor of future states, blue and orange lines are future rewards that assigned to Monte-Cart estimator and importance sampling estimator respectively, and red lines the estimation by importance sampling estimator on each future time. Black dashed lines represent periodical resets.
C.3 CASE STUDY ON REWARD DECOMPOSITION MODEL
In Pixel Grid World environment, fix stochastic policy and train model Ty minimize esti- mation variance. When the model re near convergence, we visualize reward decomposition for every future reward after state-action pair (st, az). These results are shown in Figure It is clear that all the independent rewards after reset are assigned to importance sampling estimator, which multiplied by small dependency factor and barely contribute advantage estimation. By con- trast, rewards before reset are assigned to the Monte-Carlo estimator, which contribute to advantage estimation.
17


Reviews:
[{"review_id": "rkgZgJThtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThey go on to say that this estimator will tend to have lower variance than the conventional Monte-Carlo estimator when future rewards are independent of current actions. However, the variance can actually be higher, due to the importance sampling ratio used, when future rewards are highly dependent on the current action. They propose a method to combine the two estimators on a per reward while maintaining unbiasedness using a control variate style decomposition. This introduces a tunable reward decomposition parameter which determines how to allocate each reward between the two estimators. The authors propose a method to tune this parameter by approximately optimizing an upper bound on the variance of the combined estimator.\n\nAs a final contribution, the authors introduce a temporal-difference method of estimating the action probability P(a_t|s_t,s_{t+k}) required by their method.\n\nIn the experiments, the authors provide empirical evidence that various aspects of their proposed method can work as suggested on simple problems. They also provide a simple demonstration where their advantage estimator is shown to improve sample efficiency in a control problem.\n\nThis paper suffers from moderate clarity issues, but I lean toward acceptance primarily because I feel that the central idea is a solid contribution. The idea of improving credit assignment by explicitly estimating how much actions impact future states seems reasonable and interesting. The temporal difference method introduced for estimating P(a_t|s_t,s_{t+k}) is also interesting and clever. I'm less confident in the introduced method for trading off between the Monte Carlo and importance sampling estimators. The experiments seem reasonably well executed and do a fair job of highlighting different aspects of the proposed method.\n\nThe derivation of the combined estimator was very confusing to me. It's strange that the derivation of the variance lower bound includes terms which are drawn from both a state conditional and state-action conditional trajectory. You're effectively summing variances computed with respect to two different measures, but the quantity being bounded is referred to as just the \"variance of the advantage estimator\". What measure is this variance supposed to be computed with respect to? Especially given that as written the two estimators rely on samples drawn from two different measures. It doesn't help that the advantage estimator whose variance is being constructed is never explicitly defined but just referred to as \"advantage estimator derived from equation 3\". Nevertheless, if we ignore the details of what exactly it is a lower bound of, the sum of the three variances in equation 5 seems a reasonable surrogate to minimize.\n\nRelated to the above point I don't fully understand what the variances shown in table 1 mean in the experiments section. For the IAE estimator for example, is the variance computed based on each sample using three independent trajectories (one for each term) or is it computed from single trajectories? If it's from single trajectories I can't understand how the expression would be computed.\n\nQuestions for the authors:\n-Could you please explicitly define the \"advantage estimator derived from equation 3\"?\n-Could you please explain precisely how the variance is computed in table 1?\n\nUpdate:\n\nHaving read the other reviews and authors response I will maintain my score of a weak accept, though given more granularity I would raise my score to a 7 after the clarifications. I appreciate the authors' clarification of the advantage estimator and feel the related changes to the paper are very helpful. I still feel the central idea of the work is quite strong. \n\nHowever, I also feel the control variate part of the work is very loosely specified. In particular, given the use of function approximation in practice instead of actually sampling 3 trajectories the validity of the control variate method applied is questionable. As the authors say \"if the random variable in either term has high variance, function approximators will tend to have large error\", This may be true initially but the function approximator can already reduce variance over time by learning, so it's not clear how the function approximators and control variate complement each other. This is something I feel would be worthwhile to explore more in future work.\n\nAlso, I feel it's worth pointing out that a concurrent paper presenting a very similar idea is scheduled to be presented at NeurIPS 2020, which can be found here: https://papers.nips.cc/paper/9413-hindsight-credit-assignment. I don't feel this in any way undermines the contribution of the work presented here, but merely wanted to make the meta reviewer aware in case it was relevant to their decision. In fact, I feel this work complements that one in a number of ways, including the presentation of the temporal difference method for learning the action probabilities.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "r1eBkmmRFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe overall setting makes sense. I found your example (in the second paragraph of the introduction) initially somewhat misleading, though: in the setting where a game is composed of fully independent rounds, surely these would simply be modeled as completely separate MDPs. Even if not, settings where the rounds are reset after a variable length of time (e.g. the round ends when one player achieves some objective) would *not* fit the exact independence structure you assume at the start of Section 3, if your current action affects when the game will reset. But of course your estimator does not rely on actual *independence* (C = 0); it can take advantage of only \"weak dependence\" (and moreover this dependence need not be pre-specified). You might think about emphasizing this a little more in the introduction to emphasize that the estimator is general, and you're looking for one that can take advantage of these kinds of situations.\n\nIt might be worth noting after (2) that $C^\\pi_k$ is upper-bounded by $1 / P^\\pi(a_t \\mid s_t) - 1$, so that the importance sampler is always well-defined and unbiased when action probabilities are nonzero. This does raise an issue: a policy which *ever* deterministically avoids an action, i.e. $\\pi(a_t \\mid s_t)$ in (13) is 0, will break the method. This is worth explicitly stating somewhere.\n\nSomething worth thinking about a bit: any choice of weights for your control variate provably doesn't affect your estimator in expectation (and you try to decrease its variance), so that bad estimation of e.g. the quantities in (7) won't lead you to being \"incorrect,\" just higher-variance. But a bad choice of parameters in your $C^\\pi$ estimator *would* bias your estimates. This is in some ways the same as the effect of using a value function or $Q$-function approximator, but can we say anything about the ways in which a bad $C$ estimator would likely affect the overall optimization process, perhaps in some very simple case? Would an unbiased $C$ estimator lead to an unbiased advantage estimator? (Not that it's clear how to get an unbiased estimator of the ratio in $C$ anyway.)\n\nSome minor points on notation: Using $r_{t+k}$ for the control variate was initially confusing to me, because elsewhere you've used e.g. $S_t$ for the random variable of a state and $s_t$ as the value of that state -- it made me think that $r_{t+k}$ was somehow supposed to be the value of a reward $R_{t+k}$. Another letter might be better. Similarly, $V_{w_1}(s_t)$ of (7) isn't really a value function; it's the difference between the value function and the sum of discounted control variates. Also, $C_\\phi$ doesn't estimate $C^\\pi$: it estimates $C^\\pi + 1$, so it might make more sense notationally to just subtract one from the definition of $C_\\phi$.\n\nOverall: I think the idea in this paper is sensible, the derivations fairly clear, and it seems to help empirically. It does add a lot of \"moving parts\" to the already-complicated RL setup, though, and I'm not well-versed enough in the RL literature to have much of a sense of how convincing these experiments are; hopefully another reviewer is.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gG5UblqS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe major concern is the novelty. It is similar to many of the control variate technique papers (e.g. Liu et al. (2017)), which learn a model to decrease the variance in a certain way. I don't see from the paper for the advantage of applying control variate over advantage function compared to previous methods.\n\nThe minor concern is for the clarity. Section 4 is unsatisfactory. The derivation seems correct to me, however, there are too many parameters introduce to optimize, which I cannot directly get the main page of what the algorithm is doing for the first time read. From the algorithm box, there are totally 5 different parameter: $\\theta, \\phi, w_1, w_2$ and $\\psi$ to update which make the algorithm pretty messy. I believe there are better way to either get a simpler algorithm or demonstrate your algorithm in a better way. Section 5 is even harder to understand. Could you explain why equation (14) is similar to Liu ei al. 2018?\n\nOverall I tends to reject the paper at the moment. I encourage the authors to do more surveys on control variate technique in policy optimization and highlight the novelty of why controlling the variance of the advantage function can help to boost the performance of policy optimization.\n\nReference:\n1. Liu, Hao, et al. \"Action-depedent Control Variates for Policy Optimization via Stein's Identity.\" arXiv preprint arXiv:1710.11198 (2017).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Policy gradient methods typically suffer from high variance in the advantage function estimator. The authors point out independence property between the current action and future states which implies that certain terms from the advantage estimator can be omitted when this property holds. Based on this fact, they construct a novel important sampling based advantage estimator. They evaluate their approach on simple discrete action environments and demonstrate reduced variance and improved performance.

Reviewers were generally concerned about the clarity of the technical exposition and the positioning of this work with respect to other estimators of the advantage function which use control variates. The authors clarified differences between their approach and previous approaches using control variance and clarified many of the technical questions that reviewers asked about.

I am not convinced by the merits of this approach. While, I think the fundamental idea is interesting, the experiments are limited to simple discrete environments and no comparison is made to other control variate based approaches for reducing variance. Furthermore, due to the function approximation which introduces bias, the method should be compared to actor critic methods which directly estimate the advantage function. Finally, one of the advantages of on policy policy gradient methods is its simplicity. This method introduces many additional steps and parameters to be learned. The authors would need to demonstrate large improvements in sample efficiency on more complex tasks to justify this added complexity. At this time, I do not recommend this paper for acceptance.
Decision: Reject