Model-Free Counterfactual Credit Assignment
Authors: Thomas Mesnard
Theophane Weber
Fabio Viola
Shantanu Thakoor
Alaa Saade
Anna Harutyunyan
Will Dabney
Tom Stepleton
Nicolas Heess
Marcus Hutter
Lars Holger Buesing
Remi Munos
Venue:  (2021)
Keywords: credit assignment
model-free RL
causality
hindsight

Abstract: Credit assignment in reinforcement learning is the problem of measuring an action’s influence on future rewards. 
In particular, this requires separating \emph{skill} from \emph{luck}, ie.\ disentangling the effect of an action on rewards from that of external factors and subsequent actions. To achieve this, we adapt the notion of counterfactuals from causality theory to a model-free RL setup. 
The key idea is to condition value functions on \emph{future} events, by learning to extract relevant information from a trajectory. We then propose to use these as future-conditional baselines and critics in policy gradient algorithms and we develop a valid, practical variant with provably lower variance, while achieving unbiasedness by constraining the hindsight information not to contain information about the agent’s actions. We demonstrate the efficacy and validity of our algorithm on a number of illustrative problems.

Under review as a conference paper at ICLR 2021
COUNTERFACTUAL CREDIT ASSIGNMENT IN MODEL-FREE REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Credit assignment in reinforcement learning is the problem of measuring an ac- tion's influence on future rewards. In particular, this requires separating skill from luck, ie, disentangling the effect of an action on rewards from that of external fac- tors and subsequent actions. To achieve this, we adapt the notion of counterfactu- als from causality theory to a model-free RL setup. The key idea is to condition value functions on future events, by learning extract relevant information from a trajectory. We then propose to use these as in policy gradient algorithms and we develop a valid, practical variant with prov- ably lower variance, while achieving unbiasedness by constraining the hindsight information not to contain information about the agent's actions. We demonstrate the efficacy and validity of our algorithm on a number of illustrative problems.
baselines and critics
INTRODUCTION
Reinforcement learning (RL) agents act in their environments and learn to achieve desirable out- comes by maximizing reward signal. A key difficulty is the problem of credit assignment (Minsky) 1961]. i.e. to understand the relation between actions and outcomes and to determine to what extent an outcome was caused by external, uncontrollable factors, i.e. determine the share of 'skill' and 'luck'. One possible solution to this problem is for the agent to build a model of the environment, and use it obtain more fine-grained understanding of the effects of action. While this topic has recently generated a lot of interest (Ha & Schmidhuber, 2018 Hamrick] 2019; Kaiser et al. 2019 Schrittwieser al. 2 it remains difficult to model complex. partially observed environments.
In contrast, model-free reinforcement learning algorithms such as policy gradient methods (Williams 1992, Sutton et al.) 2000) perform simple time-based credit assignment, where events and rewards happening after an action are credited to that action, post hoc ergo propter hoc. While unbiased in expectation, this coarse-grand caase-grained credit assignment typically has high variance, and the agent will require large amount of experience to learn the correct relation between actions and rewards. Another issue of model -free methods is that counterfuctual reasoning, i.e. reasoning about what would have happened had different actions been taken with everything else remaining the same, is not possible. Given a trajectory, model-free fadel-free methods can in fact only learn about the actions that were actually taken to produce the data, and this limits the ability of the agent to learn quickly. As environments grow in complexity due to partial observability, scale, long time horizons, and large number of agents, actions taken by the agent will only affect a vanishing part of the outcome, mak- ing it increasingly difficult to learn from classical reinforcement learning algorithms. We need better credit assignment techniques.
In this paper, we investigate a new method of credit assignment for model-free reinforcement learn- ing which we call Counterfactual Credit Assignment (CCA), that leverages hindsight information to implicitly perform counterfactual evaluation an estimate of the return for actions other than the ones which were chosen. These counterfactual returns can be used to form unbiased and lower vari- ance estimates of the policy gradient by building Iiture-conditional baselines. Unlike classical Q functions, which also provide an estimate of the return for all actions but do so by averaging over all possible futures, our methods provide trajectory-speciff counterfactual estimates, i.e. an estimate of the return for different actions, but keeping as many of the external factors constant between the return and its counterfactual estimate. Our method is inspired by ideas from causality theory. but does not require learning a model of the environment. Our main contributions are: a) proposing a set of environments which further our understanding of when difficult credit assignment leads to poor

---

Under review as a conference paper at ICLR 2021
policy learning: b) introducing new model-free policy gradient algorithms, with sufficient conditions for unbiasedness and guarantees for lower variance. In the appendix, we further c) present a collec- tion of model-based policy gradient algorithms extending previous work counterfactual policy search; d) connect the literature about causality theory, in particular notions of treatment effects, to concepts from the reinforcement learning literature.
2
COUNTERFACTUAL CREDIT ASSIGNMENT
2.1 NOTATION
We use capital letters for random variables and lowercase for the value they take. Consider generic MDP r. Given a current state x E X' and assuming an agent takes action A, the agent receives reward r(z, a) and transitions action, reward) of the agent at step t is denoted X, (resp. A.. Re). The initial state of the agent Xy a fixed ry- The agent acts according to a policy x. i.e. action A, sampled from the policy ()) where 0 are the parameters of the policy, and aims to optimize the expected discounted return E[G]- EE 7 Re]. The return G. from step t is G. = 7" Ryr. Finally, we define the score function ST(To,
state y p(-|2r, a). The state (resp.
Ve log (a)a the score function time t is denoted S. = Vo log To( ( In the case of a partially observed environment, we assume the agent receives observation Fre at every time step, and simply define X, to be the set of all previous observations, actions and rewards X, = (Oct), with O₂ = (E,, A Re-1) the probability distribution of a random variable X.
P(X) will denote
2.2 POLICY GRADIENT ALGORITHMS
We begin by recalling two forms of policy gradient algorithms and the credit assignment assump- tions they make. The first is the REINFORCE algorithm introduced by WWilliams (1992). which we will also call the single-action policy gradient estimator:
Proposition (single action estimator). The gradiens of E[G] is given by vgE[G] =
Ei xet S, (G: - V(X))) where V(X)) = E(G
The appeal of this estimator lies in its simplicity and generality: to evaluate it, the only requirement the ability to simulate trajectories, and compute both the score function and the return. Let us note two credit assignment features of the estimator. First, the score function S, is multiplied not by the whole return G, but by the return from time t. Intuitively, action A, can only affect states and rewards coming after time f, and it is therefore pointless to credit action A, with past rewards. Second, removing the value function (Xx.) from the return G, does not bias the estimator and typically reduces variance. This estimator updates the policy through the score term; note however (other
the learning signal only updates the policy no (a|X, X,) at the value taken by action A, values are only updated through normalization). The policy gradient theorem from (Sutton et al.] 2000), which we will also call all-action policy gradient, shows it is possible to provide learning signal to all actions, given we have access to a Q-function Q" (xr,a) |, x, A, a). which we will call critic in the following.
Proposition 2 (All-action policy gradient estimator). The gradient of [[G] is given by VgE[G] = E [E, 7t E. (a))((
A particularity of the all-actions policy gradient estimator is that the term at time for updating the policy VTT (alaaaXX)*))) Q* (Xe, a) depends only on past information; this is in contrast with the score function estimates above which depend on the return, a function of the entire trajectory. Proofs can be found in appendix D.I
2.3 INTUITIVE EXAMPLE HINDSIGHT REASONING AND SKILL VERSUS LUCK
Imagine a scenario in which Alice just moved to a new city, is learning to play soccer, and goes to the local soccer field to play a friendly game with a group of other kids she has never met. As the game goes on, Alice does not seem to play at her best and makes some mistakes. It turns out however her partner Megan is a strong player, and eventually scores the goal that makes the game a victory. What should Alice learn from this game?
'Previous actions and rewards are provided as part of the observation as it is generally beneficial to do so in partially observable Markoy decision processes.
2

---

Under review as a conference paper at ICLR 2021
When using the single-action policy gradient estimate, the outcome of the game being victory, and assuming a #1 reward scheme, all her actions are made more likely; this is in spite of the fact that during this particular game she may not have played well and that the victory is actually due to her strong teammate. From an RL point of view, her actions are wrongly credited for the victory and positively reinforced do not mitigate this issue, as Alice did not a priori know the skill of Megan, resulting in guess she had a 50% chance of winning the game and corresponding baseline of 0. This could be fixed by understanding that Megan's 's strong play were not a consequence of Alice's play, that her skill was a priori unknown but known in hindsight, and that it is therefore valid retroactively include her skill level in the baseline. A hindsight baseline, conditioned on Megan's is estimated skill level, would therefore be closer 1, driving the advantage (and corresponding learning signal) close to O.
result; effectively, Alice was lucky rather than skillful. Regular baselines
As pointed out by [Bussing et al. (2019), situations in which hindsight information is helpful in understanding trajectory are frequent. In that work, the authors adopt model-based framework, where hindsight information is used to ground counterfactual trajectories (i.e. trajectories under different actions, but same randomness). Our proposed approach follows a similar intuition, but is model-free: attempt measure measure-inseead of model- information known in hindsight to compute a conur-conniiional baseline, with the constraint that the captured information must not have been caused by the agent.
2.4 CONUUE-CNNDIIONNLL POLICY GRADIENT ESTIMATOR (FC-PG)
Intuitively, approach for assigning proper credit to action A, is as follows: via learning statistics P, we capture relevant information from the rest of the trajectory, c.g. including observations Oμ times 5' greater than f. We then learn value functions which are conditioned hindsight information contained in Φ,- In general, these future-conditional values and critics would be biased for use in policy gradient algorithm; we therefore need to correct their impact on the policy gradient through an importance correction term.
the additional
Theorem (Future single-action policy gradient estimator). Let De be an arbitrary random vari- able. The following is an unbiased estimator of the gradient of B[G];
VoE = E Σ S. GG Pr. ( (A.
(G:-
Te (A) ②.))
V(X,, (.))
(1)
where V(X,, xX, $1) ( is the future @D-conditional value function and TP (A₁ X2, Fc) the posterior probability of action At given (X,, (.). trajectories generated by policy ne.
Theorem 2 (Future all-action policy gradient estimator). The following is an unbiased estimator of the gradient of B.G]]
V&E
E Σ
Ve log (a) (al 2,) (Xe, 2..
where Q (X,, Dr, a) = E[G, X2, d,, A is the future-condiiioall Q function (critic). Further- more, we have
= E 1 (X,, t1, a) (-(a
x(a]Xe)
Proofs can be found in appendix D.2 These estimators bear similarity to (and indeed, generalize)
the Hindsight Credit Assignment estimator (Harutyunyan et al. 2019), see the literature review and appendix C for a discussion of the connections.
2.5 COUNTERFACTUAL CREDIT ASSIGNMENT POLICY GRADIENT (CCA-PG)
The previous section provides family of estimators, but does specify which + should be used, and what type of & would make the estimator useful. Instead of hand-crafting 4, we will learn to extract & from the trajectory (the sequence of observations) (Or) (0r)e2o- A useful representation & of the future will simultaneously satisfy two objectives:
2 is predictive of the outcome (the return) by learning a d--oonitional value function, through minimization of (G,- V(,,, 4. or (G, Q(X,, a, 2.))².
Note more generally that any function of X, and 4 can in fact he used valid baseline.
3

---

Under review as a conference paper at ICLR 2021
The statistic 4 is 'not consequence' of action Ag: this is done by minimizing (with respect to 42) a surrogate independence maximization (IM) loss LIM which is non-negative and zero if and only if A, and D are conditionally independent given X,.
Intuitively, the statistics capture exogenous factors to the agent (hence the conditional indepen- dence constraint), but that still significantly affect the outcome (hence the return prediction loss). The IM constraint enables us to derive the CCA-PG estimator:
Theorem 3 (single-action CCA-PG estimator). If A, is independent from Dg given X,, the following is an unbiased estimator of the gradient of [B[]]:
V =E En Se (G. -GG-VEEL (VX,, P1))
(3)
Furthermore, the hindsight advantage has no higher variance than the forward one: (G. VV,,, 2,))² s IE - (G. v(x.))
Theorem 4 (all-action CCA-PG estimator). Under the same condition, the following is unbiased estimator of the gradient of E[::
V& E
Σ
Σ V TOTO TTT (Xe, 2))
Also, have for all a, QTa (X,, E[Qu (X,, tt, a) Xx, A, = a).
Proofs can be found in appendix D.3 The benefit of the first estimator (cquation 3 is clear: under the specified condition, and compared the regular policy gradient estimator, the CCA estimator is also unbiased, but the variance of its advantage G2 - (Xx,, ([X,D1) D,) (the critical component behind variance of the overall estimator) is no higher.
For the all-action estimator, the benefits of CCA (equation are less self-evident, since this esti- mator has higher variance than the regular all action estimator (which has variance 0). The interest here lies in bias due to learning imperfect Q functions. Both estimators require learning a Q func- tion from data; any error in leads bias म. Learning Q(X,, requires averaging over all possible trajectories initialized with state X, and action a: in high variance situations, this will re- quire lot of data. In contrast, if the agent could measure a quantity & which has high impact on the return but is not correlated to the agent action A,, it could be far easier to learn Q(X,, D,, This is because Q(X,, Pr,a) a) computes the averages the return G, conditional on (X,, Qr, a); b has a high impact on Gr: the variance of that conditional return will be lower, and learning its average will in turn be simpler. Interestingly, note also that Q(X,, 2t, a) (in contrast to Q(X,, a)) is trajectory-specitee estimate of the return for counterfactual action.
2.6 ALGORITHMIC AND IMPLEMENTAIIN DETAILS
In this section, we provide one potential implementation of the CCA-PG estimator. Note however than in order to be valid, the estimator only needs to satisfy the conditional independence assump- tion, and alternative strategies could be investigated. The agent is composed of four components:
Agent network:
We assume the agent constructs an internal state X, from (O:)) e using arbitrary network, for instance an RNN, i.e. X, = (O, From X, the agent computes a policy (a)...)).
Additionally, we assume the agent uses hindsight network ip with parameters which computes a hindsight statistic & (p,(OO X, A)) (where (0, X, A) is the sequence of all observations, agent states and actions in the trajectory). which may depend arbitrarily on the vectors of observations, agent states and actions (in particular, it may depend on observations from timesteps t' 2 1). We investigated two architectures. The first is a backward RNN, where (Ø,, B,) = RNN (X,, B1+1), where B, is the state the backward RNN. Backward RNNs are justified in that they can extract information from arbitrary length sequences, and allow making the statistics 4, function of the entire trajectory. They also have the inductive bias of focusing more on near- frarrfuture observations.
Hindsight network:
The second is transformer (Vaswani et al.) 2017 Parisotto et al.) 2019). Alternative net- works could be used, such as attention-basee networks (Hung et al. 2019 or RIMs (Goyal
et al. 2019).
4

---

Under review as a conference paper at ICLR 2021
Value network:
The third component is future-conditional value network Vo Dt).
Hindsight classifier: The last component is a probabilistic classifier hiw with parameters w that takes Xx, Lt as input and outputs a distribution over At.
Learning is ensured through the minimization of four losses: the hindsight baseline loss Lis E (G, (X,, Dc))² (optimized with respect to f); the hindsight classifier loss, Csup E. Elog (A, (A, &t) (optimized with respect to w only all other parameters are treated as constants); the policy gradient surrogate loss LPG = >, log No (Ael - V(X,, Pr)). where the bar notation indicates that the quantity is treated as constant from the point of view of gradi- ent computation; and finally the aforementioned independence loss LIM, which ensures the condi- tional independence between A, and b, We investigated two IM losses. The first is the Kullback- Leibler divergence between the distributions 1 (A, and (.,
4c). In this case, the KL log IP= (a[Xx, +x)); IP=, (a)X,) is simply the policy No (a) Xx), and the posterior xxx, Xa, +x) can be approximated by probabilistic classifier hw (ee 2,). This results in (t) En To (a) (log To (x) log h (a|X,, Dx)). We also investigated the conditional mutual information between Ar and Φú; again approximated using h. We did not see significant differences between the two, with the KL slightly outperforming the mutual information. Finally, note that conversely to the classifier loss, when optimizing the IM loss, is treated as a constant.
can be estimated by En ( (a(Xx) (log IP [a)
Parameter updates and a figure depicting the architecture can be found in Appendix A
NUMERICAL EXPERIMENTS
Given its guarantees on lower variance and unbiasedness, we run all our experiments the single action version of CCA-PG.
3.1 BANDIT WITH FEEDBACK
We first demonstrate the benefits of hindsight value functions in toy problem designed to highlight these. We consider a contextual bandit problem with feedback. Given N, K E N. we sample for each episode an integer context -N < < N as well an exogenous noise e, [N o,). Upon taking action A E {-N,... agent is provided with K -ddiennsional feedback vector F = for -N < < N, and W E IR are fixed vectors; in our case, for each seed, they are sampled from standard Gaussian distribution and kept constant through all episodes. More details about this problem as well as variants are presented in Appendix B.1
.N. the agent receives reward R = (C-A)C++e Additionally. the
We, where Un. Vn R
For this problem, the optimal policy is to choose the reward R is the sum of the informative reward (C'' -
C, resulting in average reward of 0. However, and the noisy reward é,, uncorrelated to the action. The higher the standard deviation o,, the more difficult is to perform proper credit assignment, as high rewards of action. On the other hand, the feedback contains information about C, A and 6,. If the agent can extract information &b from F in order to capture information about 6, and use it to compute a hindsight value function, the effect of the perturbation 6, may be removed from the advantage, resulting in significantly lower variance estimator. However, if the agent blindly uses F' to compute the hindsight value information, information about the context and action will 'leak' into the hindsight value, leading an advantage of and no learning: intuitively, the agent will assume the outcome is entirely controlled by chance, and that all actions are equivalent, resulting in a form of learned helplessness.
more likely due high value of c, than appropriate choice
We investigate the proposed algorithm with N = 10, K= = 64. As can be seen on Fig. increasing the variance of the exogenous noise leads to dramatic decrease of performance for the vanilla PG estimator without the hindsight baseline; in contrast, the CCA-PG estimator is generally unaffected by the exogenous noise. For very low level of exogenous noise however, CCA-PG suffers from a decrease in performance. This is due to the agent computing a hindsight statistic & which is not perfectly independent from A, leading to bias in the policy gradient update. The agent attributes part of the reward to chance, despite the fact that in low-noise regime, the outcome is entirely due to the agent's 's action. To demonstrate this, and evaluate the impact of the independence constraint on performance, we run CCA-PG with different values of the weight AIM of the independence max-
5

---

Under review as a conference paper at ICLR 2021
imization loss, seen in Fig. | For lower values of this parameter, i.c. when & and A have larger
mutual information, the performance is dramatically degraded.
roward nolss 21d - 0.1 roward nalse 200 10.0
-20
-25
rewar
124010 no5e 555 100.0
rewerrd 70:50 d0d 1000.0
PG
CCA PG. hinosight entrosy weight - 0.0
CCA-PG, hinosight entrogy
hinesight entrogy woight
CCA PG, hinosight entrogy weight 10.0
-25
0.0
0.2
0.4
0.6 0.8 1.0
12
1.4
8795 rorment staps
0.25
0.25
0.75 L.00.00
anvtroommett stags
3.50
environment steps
147
Comparison of CCA-PG and PG in contextual bandits with feedback, for various levels of reward noise Results are averaged over 6 independent runs. Right: Performance of CCA-PG on the bandit task, for different values of Ams. Not properly enforeing the independence constraint results in strong degradation of performance.
Figure 1: Left:
3.2 KEY-TO-DOOR ENVIRONMENTS
Figure 2: Key-To-Door environments visual. The agent is represented by the heige pixel, key by brown, apples by green, and the final door by blue. The agent partial field of view, highlighted in white.
Task Description. We introduce the Key-To-Door family of environments as testbed of tasks where credit assignment is hard and is necessary for success. In this environment (cf. Fig. 2) the agent has to pick up key in the first room, for which it has immediate reward. In the second room, the agent can pick up 10 apples, that each give immediate rewards. the final room, the agent open door (only if it has picked up the key in the first room), and receive small reward. In this task, a single action (i.e picking up the key) has a very small impact on the reward receives in the final room, while its episode return is largely driven by its performance the second room (i.e picking apples).
We now consider two instances of the Key-To-Door family that illustrate the difficulty of credit assignment in the presence of extrinsic variance. In the Low-Variance-Kaa. Key-To- To-Door environment, and opening the final door also gets reward of Thus, an agent
each apple is worth a reward that solves the apple phase perfectly sees very little variance in its episode return and the learning signal for picking up the key and opening the door is relatively strong.
High- Variance Key-To-KKTTTaa To-Door keeps the overall structure of the Toy-To-Dorr task, but now the re- ward for each apple is randomly sampled to be either 1 or 10, and fixed within the episode. In this setting, even agent that has perfect apple-phase policy sees large variance in episode returns, and thus the learning signal for picking up the key and opening the door is comparatively weaker. Appendix[B22. B.2. has some additional discussion illustrating the difficulty of learning in such a setting.
environments, and compare it against Actor-Critic (Williams 1992), as well as contecoondiional HCA and Return-conditional HCA (Harutyunyan et al. 2019) as baselines. We test using both a Dackward-LSTM (referred to CCA-PG RNN) or attention model (referred to as CCA-PG Attn) for the hindsight function. Details for experimental setup are provided in Appendix B.2.2 All results reported as median performances 10 seeds.
Results We test CCA-PG

---

Under review as a conference paper at ICLR 2021
14
375
'12
Figure 3: Probability of opening the door and total reward obtained on the High- wwea--aaaannce--T-----ee- task (left two) and the Now-Variance-Key Key-To-Door task (right two).
We evaluate agents both on their ability to maximize total reward, as well as solve the specific credit assignment problem of picking up the key and opening the door. Figure compares CCA-PG with the baselines on the High-Variance- Vaaiaaaa-ainn-------- To-oor task. Both CCA-PG architectures outperform the baselines in terms of total reward, as well probability of picking up the key and opening the door.
This example highlights the capacity of CCA-PG to learn and incorporate trajectory-speecfic external factors into its baseline, resulting in lower variance estimators. Despite being difficult task for credit assignment, CCA-PG is capable of solving it quickly and consistently. On the other hand, vanilla actor-critic greatly impacted by this external variance, and needs around 10 environment steps to have an 80% probability of opening the door. CCA-PG also outperforms State- and Return- Conditional HCA, which do use hindsight information but a more limited way than CCA-PG.
On the www-Variance-Keee Meeraancee-----TT-ee Key-Too-Door task, due to the lack of extrinsic variance, standard actor-critic is able to perfectly solve the environment. However, it interesting to note that CCA-PG still matches this perfect performance. On the other hand, the other hindsight methods struggle with both door- opening and apple-gathering. This might be explained by the fact that both these techniques do not guarantee lower variance, and rely strongly their learned hindsight classifiers for their policy gradient estimators, which can be harmful when these quantities are not perfectly learned. See Appendix B.2.3 for additional experiments and ablations these environments.
These experiments demonstrate that CCA-PG is capable of efficiently leveraging hindsight informa- tion mitigate the challenge of external variance and learn strong policies that outperform baselines. At the same time, suffers no drop in performance when used cases where external variance is minimal.
3.3 TASK INTERLEAVING
Motivation. In the real world, human activity can be seen solving large number of loosely related problems. These problems are not solved sequentially, as one may temporarily engage with problem and only continue engaging with receive feedback from its earlier actions significantly later. At an abstract level, one could see this lifelong learning process as solving problems not in a sequential, but interleaved fashion instead. The structure of this interleaving also will typically vary over time. Despite this very complex structure and receiving high variance rewards from the future, humans are able quickly make sense of these varying episodes and correctly credit their actions. This learning paradigm is quite different from what is usually considered in reinforcement learning. Indeed, focus is mostly put on agents trained on a single task, with outcome dominated by the agent's 's actions, where long term credit assignment is not required and where every episode will be structurally the same. To the end of understanding the effects of this interleaving on lifelong learning, we introduce new class of environments capturing the structural properties mentioned above. In contrast to most work on multi-task learning, we do not assume a clear delineation be- tween subtasks -each agent will encounter multiple tasks in single episode, and it is the agent's responsibility to implicitly detect boundaries between them.
Task Description. As described in Fig. 4 this task consists of interleaved pairs of query-answer rooms with different visual contexts that represents different tasks. Each task has associated map- ping of 'good' (resp. 'bad') colors yielding to high (resp. zero) reward. Each episode is composed of randomly sampled tasks and color pairs within those tasks. The ordering and the composition of each episode is random across tasks and color pairs. A visual example what an episode looks like can be seen in Fig. 4 Additional details provided in B.3.T
7

---

Under review as a conference paper at ICLR 2021
Toak
Task
Task
TATAVAA Answer Room
Query Room
Epdodo
Figure 4: Multi Task Interleaving Description. Top left. Delayed feedback contextual bandit problem. Given a context shown as a surrounding visual pattern, the agent has to decide to pick up one of the two colored squares where only one will be rewarding. The agent is later teleported to the second room where it is provided with the reward associated with its previous choice and visual eue about which colored square it should have picked up. Top right: Different tasks which each different color mapping, visual context and associated reward. Bottom: Example of a generated episode, composed randomly sampled tasks and color pairs.
The tasks we will consider next (numbered # to #6) are respectively associated with a reward of 80, 4, 100, 6, 2 and 10. Tasks #2, #4, #5 and #6 referred to 'hard' while tasks # and #3 as 'easy" because of their large associated rewards. The settings 2, and 6-task are respectively considering tasks 1-2, 1-4 and 1-6. In addition the total reward, we record the probability of picking up the correct square for the easy and hard tasks separately. Performance in the hard tasks will indicate ability do fine ane-grained credit assignment.
Tasts
Tasks
Tasks
2706 001e T6855
OC Po an Bary Tydks
2.02
0.25
250
0.75
LO0
125
150
L/S
2:00
300
0.5
050
DJS
1:0
125
130
2/3
100
0.0
0.5
077
3,05
122
135 steps
1.0
200
Tasks
Tinks
Tasks
300
255
202
170
232
241
150
20.00
X2g
cnvironment ST000
367
envtronment StopS
149
cnVErnmentERRsp.
267
Figure 5: Probability of solving 'easy' and 'hard' tasks and total reward obtained for the Multi Task Inter- leaving, Top plot: Median over 10 seeds after doing mean over the performances in 'easy' or 'hard' tasks.
Results. While CCA-PG is able to perfectly solve both the 'easy' and 'hard' tasks in the three setups less than 5.10$ environment steps (Fig. 5), actor-critic is only capable solve the "easy' tasks for which the associated rewards are large. Even after 2. 10 environment steps, actor-critic still greatly impacted by the variance and remains incapable of solving 'hard' tasks any of the three settings. CCA also outperforms actor-critic in terms of the total reward obtained in each setting. State-conditional and Return-conditional HCA were also evaluated on this task but results not reported as almost learning taking place the 'hard' tasks. Details for experimental setup are provided in B.3.2] All results are reported as median performances over 10 seeds. More results along with ablation study can be found in B.3.3
Through efficient use hindsight, CCA-PG able to take into account trajectory-specifee factors such the kinds of rooms encountered in the episode and their associated rewards.
8

---

Under review as a conference paper at ICLR 2021
In the case of the Multi-Task Interleaving environment, informative hindsight function would capture the reward for different contexts and exposes as D all rewards obtained in the episode except those associated with the current context. This experiment again highlights the capacity of CCA-PG to solve hard credit assignment problems in a context where the return is affected by multiple distractors, while PG remains highly sensitive to them.
RELATED WORK
This paper builds on work from Buesing al. (2019) which shows how causal models and real data can be combined to generate counterfactual trajectories and perform off-policy evaluation for RL. Their results however require an explicit model of the environment. In contrast, our work proposes a model-free approach, and focuses on policy improvement. Oberst & Sontag (2019) also investigate counterfactuals in reinforcement learning, point out the issue of non-identiiaabliiy of the correct SCM, and suggest a sufficient condition for identifiability; we discuss this issue in appendix F. Closely related to our work Hindsight Credit Assignment, concurrent approach from HHarutyun yan et al. (2019); in this paper, the authors also investigate value functions and critics that depend on future information. However, the information the estimators depend on is hand-crafted (future state or return) instead of arbitrary functions of the trajectory; their estimators is not guaranteed to have lower variance. Our FC estimator generalizes their estimator, and CCA further character- izes which statistics of the future provide a useful estimator. Relations between HCA, CCA and The HCA approach is further extended by Young (2019), and Zhang et al. (20T9) who minimize surrogate for the variance of the estimator, but that surrogate cannot be guaranteed to actually lower the variance. Similarly to state-HCA, it treats each reward separately instead of taking trajectory-centrrc view as CCA. Guez et al. (2019) also investigate future-conditions value functions; similar to us, they learn statistics of the future 4 from which returns can be accurately predicted, and show that doing so leads to learning better representations (but use regular policy gradient estimators otherwise). Instead of enforcing information-theoree constraint, they bottleneck information through the size of the encoding Q. In domain adaptation (Ganin et al., 2016: Teeng et al. 2017), robustness to the training domain can be achieved by con- straining the agent representation not to be able to discriminate between source and target domains, mechanism similar to the one constraining hindsight features not being able to discriminate the agent's 's actions.
FC are discussed in appendix [
Both Andrychowiccc et al. (017) and Rauber et al. (2017) leverage the idea of using hindsight infor- mation to learn goal- cooall-ondtiooeed policies. Hung et al. (2019) leverage attention- based systems and episode memory perform long term credit assignment; however, their estimator will in general be biased. |Ferret et al.] (2019) looks at the question of transfer learning in RL and leverage trans- formers derive a heuristic perform reward shaping. AArjoaa et al. (2019) also addresses the problem of long-term credit assignment by redistributing delayed rewards earlier in the episode; their approach still fundamentally uses time as a proxy for eredit.
Previous research also leverages the fact that baselines can include information unknown to the agent time t (but potentially revealed in hindsight) but not affected by action As. see e.g. (Wu et al, 2018 Foerster et al., 2018 Andrychowicz et al., 2020 Vinyals et al.] 2019). Note however that all of these require privileged information, both in the form of feeding information to the baseline inaccessible to the agent, and in knowing that this information is independent from the agent's 's action A, and therefore won't 't bias the bascline. Our approach seeks to replicate a similar effect, but in a more general fashion and from an agent-centric point of view, where the agent learns itself which information from the future can be used to augment its baseline at time t.
5 CONCLUSION
In this paper we have considered the problem of credit assignment in RL. Building on insights from causality theory and structural causal models we have developed the concept of future-conditional value functions. Contrary to common practice these allow baselines and critics to condition on future events thus separating the influence of an agent's actions on future rewards from the effects of other random events thus reducing the variance of policy gradient estimates. A key difficulty lies in the fact that unbiasedness relies on accurate estimation and minimization of mutual information. Learning inaccurate hindsight classifiers will result in miscalibrated estimation of luck, leading to bias in learning. Future research will investigate how to scale these algorithms to more complex environments, and the benefits of the more general FC-PG and all-action estimators.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. In Advances in neural information processing systems, pp. 5048-5058, 2017.
OpenAl: Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert. Glenn Powell, Alex Ray, al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1):3-20, 2020.
Jose A Arjona-Meding Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brand- stetter, and Sepp Hochreiter. Rudder: Return decomposition for delayed rewards. Advances in Neural Information Processing Systems, pp. 3354-133553 2019.
Mare Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 449-458 JMLR. org, 2017.
Lars Buesing, Theophane Weber, and Shakir Mohamed. Stochastic gradient estimation with finite differences. In N/PS2016 Workshop on Advances Approximate Inference, 2016.
Lars Buesing, Theophane Weber, Yori Zwols, Sebastien Racaniere, Arthur Guez, Jean- cann-Bapistt Lespiau, and Nicolas Heess. Woulda, coulda, shoulda: Counterfactulll-guuie policy search. 2019 International Conference for Learning Representations (ICLR), 2019.
Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio. Gated feedback recurrent neural networks. In International conference on machine learning, pp. 2067-2075, 2015.
Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Rubinstein. tutorial on the cross-entropy method. Annals of operations research, 134(1):19-67, 2005.
Johan Ferret, Raphaël Marinier, Matthieu Geist, and Olivier Pietquin. Credit assignment as proxy for transfer in reinforcement learning. arXiv preprint arXiv: /ttp//99770002... 2019.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson.
Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural net- works. The Journal of Machine Learning Research, 17(1):2096 2030, 2016.
Paul Glasserman and David D Yao. Some guidelines and guarantees for common random numbers. Management Science, 3886)88,,,08, 1992.
Anirudh Goyal, Alex Lamb, Jordan Hoffmann, Shagun Sodhani, Sergey Levine, Yoshua Bengio, and Bernhard Schölkopf. Recurrent independent mechanisms. arXiv preprint arXiv:1909 10893, 2019.
Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates reinforcement learning. Journal of Machine Learning Research, 1770v3:44 2004.
Arthur Guez, Fabio Viola, Theophane Weber, Lars Buesing, Steven Kapturowski, Doina Precup, David Silver, and Nicolas Heess. Value-driven hindsight modelling. http://pppneeeeeeneeefffmntddddd
2019.
David Ha and Jürgen Schmidhuber. World models. arXiv preprint arX1vv1803.1012,, 2018.
Jessica Hamrick. Analogues of mental simulation and imagination in deep learning. Current
Opinion in Behavioral Sciences, 29:8-16, 2019.
10

---

Under review as a conference paper at ICLR 2021
Anna Harutyunyan, Will Dabney, Thomas Mesnard, Mohammad Gheshlaghi Azar, Bilal Piot, Nico- las Heess, Hado van Hasselt, Gregory Wayne, Satinder Singh, Doina Precup. et al. Hindsight credit assignment. In Advances in Neural Information Processing Systems, pp. 12467-12476, 2019.
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learn- ing continuous control policies by stochastic value gradients. In Advances in Neural Information Processing Systems, pp. 2944-2952, 2015.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8), 2012.
Chia-Chun Hung, Timothy Lillicrap, Josh Abramson, Yan Wu, Mchdi Mirza, Federico Carnevale, Arun Ahuja, and Greg Wayne. Optimizing agent behavior over long time scales by transporting value. Nature communications, 10(1):1-12, 2019.
Lukasz. Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, et al. Model-based reinforcement learning for atari. arXiv preprint /903. 2019.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization, arXiv preprint arXiv:1412.6980, 2014.
Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking masel-based reinforcement learning. arXiv preprint arXiv:1907.02057 2019.
Marvin Minsky. Steps toward artificial intelligence. Proceedings of the IRE, 49(1)-833, 1961.
Andrew Y Ng and Michael Jordan. Pegasus: A policy search method for large mdps and pomdps.
arXiv preprint 1XXix:331.3870 2013.
Michael Oberst and David Sontag. Counterfactual off offlcy evaluation with gumbel-man -mxx structural causal models. arXiv preprint 2ttt://90..0882,20000 2019.
Emilio Parisotto, H Francis Song, Jack W Rae, Razvan Pascanu, Caglar Gulcehre, Siddhant M Jayakumar, Max Jaderberg, Raphael Lopez Kaufman, Aidan Clark, Seb Noury, et al. Stabilizing transformers for reinforcement learning, arXiv preprint 1rXiv:1910.06764,, 2019.
Judea Pearl. Causality. Cambridge university press, 2009a.
Judea Pearl. Causality: Models, reasoning, and inference. 2009b.
Paulo Rauber, Avinash Ummadisingu, Filipe Mutz, and Juergen Schmidhuber. Hindsight policy gradients. arXiv preprint arXiv:1711.0600 2017.
Danilo Jimenez Rezende and Fabio Viola. Taming VAEs. arXiv preprint arXiv:1810.00597, 2018.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. arXiv preprint arXiv: 1911199115,,,,.. 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International Conference on Machine Learning, pp- 387-395, 2014.
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- fion processing systems. pp. 1057-1063, 2000.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7167-7176. 2017.
11

---

Under review as a conference paper at ICLR 2021
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. (11.55998-00 2017.
Joel Veness, Marc G Bellemare, Marcus Hutter, Alvin Chua, and Guillaume Desjardins. Compress and control. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft II using multi-agent reinforcement learning. Nature, 575(7782) 2019.
Lex Weaver and Nigel Tao. The optimal reward baseline for gradient-based reinforcement learning- In Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence, pp. 538- 545. Morgan Kaufmann Publishers Inc., 2001.
Théophane Weber, Nicolas Heess, Lars Buesing, and David Silver. Credit assignment techniques in stochastic computation graphs. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1650-2660,, 2019.
Ronald J Williams. Simple statistical gradient-foloowing algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-23) 256. 1992.
Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre M Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action-dependent factorized baselines. 2018 International Conference for Learning Representations (ICI.R, 2018.
Kenny Young. Variance reduced advantage estimation with 8-hindsight credit assignment. arXiv preprint arXiv:1911.0880 2019.
Pushi Zhang, Li Zhao, Guoqing Liu, Jiang Bian, Minglie Huang, Tao Qin, and Liu Yan. Independence-awware advantage estimation. http::/pppeeeeiiieeeeeemmmemeeep 2019.
12

---

Under review as a conference paper at ICLR 2021
Appendix
A
ARCHITECTURE
The parameter updates are as follows:
Parameter updates
For each trajectory (X,, A,, Re)120, compute the parameter updates
A0 XPG E, Ve log (A (Xx,, 2.)) Ans VeCns(t) AIM Vo E, CiM(t) Aw = V (t)
where the different the weights of each loss.
V
V4+1
V2+2
B
B
Be+3
Br-2
A
A
Aras
A4+2
X
X,
X++1
Xz+2
Q
O₂
OLI
Figure 6: Overall architecture for the RNN network. For simplicity we assume without loss of generality that B, and 4 include X,-
B
ADDITIONAL EXPERIMENTAL DETAILS
B.
BANDITS
B.1.1 ARCHITECTURE
For the bandit problems, the agent architecture is follows:
The hindsight feature & is computed by a backward RNN. We tried multiple cores for the RNN: GRU ( (Chung al. 2015) with 32 hidden units, recurrent adder (b, b + MLP(xx), where the MLP has two layers of 32 units), or an exponential averager (b, = Aby-1 (1 A).L.
The hindsight classifier fw is a simple MLP with two hidden layers with 32 units each.
The policy and value functions are computed as the output of simple linear layer with concatenated observation and feedback as input.
All weights are jointly trained with Adam (Kingma & Ba 2014).
Hyperparameters chosen follows (unless specified otherwise): learning rate 4e-4, entropy loss 4e-3, independence maximization tolerance 3PM = 0.1; Arva = Anw = 1; AIM is set through Lagrangian optimization (GECO, Rezende & Viola (018)).
13

---

Under review as a conference paper at ICLR 2021
B.1.2 ADDITIONAL RESULTS
Multiagent Bandit Problem: In the multi-agent version, which we will call MULTI-BANDIT, the environment is composed of M replicas of the bandit with feedback task. Each agent = 1,..., M interacts with its own version the environment, but feedback and rewards are coupled across is obtained by modifying the single agent version as follows:
agents;
The contexts C are sampled i.i.d. from {-N,.... NJ. C and A now denote the concate- nation of all agents' contexts and actions.
The feedback tensor is (M, K) dimensional, and is computed as +, tey; where the W are now three dimensional tensors. Effectively, the feedback for agent i depends on the context and actions of all other agents.
The observation for agent at step 2 is (0, F(t)), where F(t) (P.(0--1)+111B-
The terminal joint reward is Σ; -C - A/)) for all agents.
The multi-agent version does not require the exogenous noise as other agents play the role of exogenous noise: is minimal implementation of the example found in section 2.3
Finally, we report results from the MUL.TI-BANDIT version of the environment, which can be found in Fig. 7 As the number of interacting agents increases, the effective variance of the vanilla PG estimator increases as well, and the performance of each agent decreases. In contrast, CCA-PG agents learn faster and reach higher performance (though they never learn the optimal policy).
agents
agerts 20
50
nuth agents
roward
0.0
0.6
1.5
0.6
3,0
Figure Multiagent versions of bandit problems. CCA-PG agents outperform single timestep
version.
B.2 KEY TO DOOR TASKS
B.2.1 ENVIRONMENT DETAILS
Table shows the advantages for either picking up the key or not, for an agent that has a perfect apple-phase policy, but never picks up the key door, on Variance-Key-Toonee are 10 apples which can be worth 1 or 10, the return will be either 10 or 100. Thus the forward baseline in they key phase, i.c. before it has seen how much an apple is worth in the current episode, will be 55. As seen here, the difference in advantages due to Luck is far larger than the difference in advantage due Skill when not using hindsight, making learning difficult, leading the policy never learning to start picking up the key door. However, when we use hindsight-condiiioned baseline, we are able to learn a & (i.c. the value of a single apple in the current episode) that is completely independent from the actions taken by the agent, but which can provide perfect hindsight-condditined baseline of either 10 or 100.
Since there
14

---

Under review as a conference paper at ICLR 2021
Lucky
Unlucky
(high apple reward)
(low apple reward)
Skillful
Hindsight advantage
(Got key + Door)
Unskillful
0
(Did not get key or door)
Skillful
-44
Forward Advantage
(Got key Door)
Unskillful
45
-45
(Did not get key or door)
The advantage of the action of picking up a key in Bigh-Variance--ae Key-To To-Door, computed by an agent that always picks up every apple, and never picks up the key door. We see that an advantage learned using hindsight clearly diffcrentiates between the skillful and unskillful actions; whereas for an advantage learned without using hindsight, this difference is dominated by the extrinsic randomness.
Table 1:
B.2.2 ARCHITECTURE
The agent architecture is follows:
The observation shapes of (3, 3) and strides of (1, 1). The output of the CNN is the flattened and fed to linear layer of size 128.
first fed to 2-layer CNN with with (16,32) output channels, kernel
The agent state computed as a forward LSTM with a state size of 128. The input to the LSTM are the output of the previous linear layer, concatenated with the reward at the previous timestep.
The hindsight feature & is computed either by backward LSTM (i.e CCA-PG RNN) with a state size of 128 or by an attention mechanism Vaswani et al. 2017) (i.e CCA-PG Att) with value and key sizes of 64, 1 transformer block with 2 attention heads and I hidden layer mlp of size 1024, an output size of 128 and a rate of dropout of 0.1. The input provided is the concatenation of the output of the forward L.STM and the reward at the previous timestep.
The policy is computed the output of a simple MLP with layer with 64 units where the output of the forward LSTM provided as input.
The forward baseline is computed as the output of 3-layer MLP of 128 units each where the output of the forward LSTM is provided as input.
For CCA, the hindsight classifier h is computed as concatenation of the output of an MLP, with four hidden layers with 256 units each where the the concatenation the output the forward LSTM and the hindsight feature & is provided as input, and the log of the policy outputs.
For State HCA, the hindsight classifier A is computed as the output of an MLP, with four hidden layers with 256 units each where the the concatenation of the outputs of the forward LSTM at two given time steps is provided as input.
For Return HCA, the hindsight classifier h. is computed the output of MIP, with four hidden layers with 256 units each where the the concatenation of the output of the forward LSTM and the return is provided input.
The hindsight baseline is computed as the output a 3-layer MLP of 128 units each where the concatenation of the output of the forward LSTM and the hindsight feature & is pro- vided as input. The hindsight baseline is trained to learn the residual between the return and the forward baseline.
All weights are jointly trained with RMSprop (Hinton et al. 2012) with epsilon 1e-4, momentum O and decay 0.99.
15

---

Under review as a conference paper at ICLR 2021
CCA Att
CCA LSTM
PG
State HCA
Return HCA
Policy cost
1
1
1
Entropy Cost
5e-3
5e-3
5e-3
5e-3
5e-3
Forward baseline
5e-2
5e-2
5e-2
5e-2
5e-2
Conditional baseline cost
5e-2
5e-2
Hindsight classifier cost
le-2
1e-2
le-2
le-2
Action independence cost
le2
le2
Learning rate
5e-4
5e-4
1e-4
5e-4
1e-3
Table 2: High Variance- Key-To- Tey-To-Door hyperparameters
CCA Att
CCA LSTM
PG
State HCA
Return HCA
Policy cost
I
Entropy Cost
5e-3
5e-3
5e-3
5e-3
5e-3
Forward baseline cost
5e-2
5e-2
5e-2
5e-2
5e-2
Conditional baseline cost
5e-2
5e-2
Hindsight classifier cost
le-2
le-2
1e-2
1e-2
Action independence cost
le2
le2
Learning rate
5e-4
5e-4
5e-4
5e-4
5e-4
Table 3: Key-To-Door hyperparameters
For High-Vare Variance- Key-oo--- the optimal hyperparameters found and used for each algorithm can be found in Table
For Key-To-Doon the optimal hyperparameters found and used for each algorithm can be found in Table 3
The agents are trained on full-episode trajectories, using a discount factor of 0.99.
B.2.3
ADDITIONAL RESULTS
baseline loss (log scale)
101
CCA-PG CCA-PG
Figure Baseline loss for policy gradient versus conditioned baseline loss for CCA High Variance Key To Door.
10a
10
10-2
0.0
0.2
0.4
0.6
0.8
1.0
environment steps
1c9
As shown in Fig. in the case of of actor-critic, the baseline loss increases at first. As the reward associated with apples vary from one episode to another, getting more apples also means increasing forward baseline loss. On the other hand, as CCA is able to take into account trajectory specific exogenous factors, the hindsight baseline loss can nicely decrease as learning takes place.
Fig. shows the impact of the variance level induced by the apple reward discrepancy between episodes on the probability of picking up the key and opening the door. Thanks to the use of hind- sight in its value function, CCA-PG is almost not impacted by this whereas actor-critic sees its performances drops dramatically as variance increases.
Figure [0 a qualitative analysis of the attention weights learned by CCA-PG Att on the High- Variance- Key-To-Door task. For this experiment, interpretation of the hindsight function, and show both a heatmap of the attention weights over the entire episode, and histogram of attention weights at the step where the agent picks up the key. As
only single attention head for easier
16

---

Under review as a conference paper at ICLR 2021
1.0
PG 1-10
0.8
PG 1-1
Figure 9: Impact of variance eredit assignment perfor- mances. Probability of open- ing the door and total reward ob- tained as function of the vari- level induced by the apple reward discrepancy.
CCA PG Att 1-20
0.6
CCA-PG Att 1-10
CCA-PG Att 1-1
0.4
0.2
0.0
environment steps
1e9
Future
Figure 10: Visualization of attention weights the High- Variance-Kar Keynnnce--K--eeeee Key-To-Doov task. Left: 2-dimensional heatmap showing how the hindsight function each step attends to each step the future. Red lines indicate the timesteps which apples are picked up (marked as 'a'); green indicates the door (marked 'd'); yellow indicates the key (marked as 'k"). Right: bar plot attention over future timesteps, computed at the stop where the agent is just about to pick up the key.
expected, the attention is paid timesteps just after the agent picks up an apple since these are the points at which the apple reward is provided to the & computation. In particular, very little attention is paid to the timestep where the agent opens the door. These insights further show that the hindsight function learned is highly predictive of the episode return, while not having mutual information with the action taken by the agent, thus ensuring an unbiased policy gradient estimator.
B.3 MULTI TASKS INTERLEAVING
B.3.1 ENVIRONMENT DETAILS
For each task. random set, but fixed through training, set of out 10 colored squares are leading to positive reward. Furthermore, a small reward of 0.5 is provided to the agent when it picks up any colored square. Each episode are 140 steps long and it takes 9 steps for the agent to reach one colored square from it initial position.
B.3.2 ARCHITECTURE
We use the same architecture setup reported in Appendix B.2.2 The agents are also trained on full-episode trajectories, using a discount factor of 0.99.
For Multi Tasks Interlcaving, the optimal hyperparameters found and used for each algoritm found and used for each algorithm can be found in
17

---

Under review as a conference paper at ICLR 2021
CCA Att
CCA LSTM
PG
Policy cost
Entropy Cost
5e-2
5e-2
5e-2
Forward baseline cost
le-2
5e-3
5e-2
Conditional baseline cost
le-2
5e-3
Hindsight classifier cost
le-2
le-2
Action independence cost Learning rate
lel
lel
5c-4
5c-4
1c-3
Table Multi Tasks Interleaving hyperparameters
B.3.3
ADDITIONAL RESULTS
Task
Task
1.0
1.0
0.9
0.9
prob solve task
prob salve tack
0.8
0.8
0.7
OCA-PG Att
0.00
0.25
0.50
0.75
1.00 1.25 1.50 1.75 2.00
0.00
0.25
0.50
0.75
1.00
1.25
1,50
1.75
2,00
environment steps
169
enviranment steps
1e9
Task
Task
1.0
0.9
prob solve task
prob salve cask
0.8
0.8
0.7
0.7
0.6
0.6
0,
8.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
0.00
0.25
0.50
2,00 environment
0.75
1.00
1.25
1.50
1.75
steps
169
169
Task 5
Task 6
grob solve task
8.00
1.50
8.00
0.50
1.50 1.75
environment steps
169
environment steps
Figure 11: Probability of solving each task in the 6-task setup for Multi Task Interlcaving.
As explained in 3.3 CCA is able to solve all 6 tasks quickly despite the variance induced by the the other hand despite solving the easy tasks I and 3 for which
exogenous factors. Actor-critic the agent receives a big reward, it is incapable of reliably solve the 4 remaining tasks for which the associated reward is smaller. This helps unpacking Fig.
18

---

Under review as a conference paper at ICLR 2021
1.0
prob solve hard tasks
0.9
Figure 12: Impact of the number of back-propagation through time steps per- formed into the hindsight function for CCA RNN. Probahility of solving the hard tasks in the 6-task setup of Multi Task In- terleaving.
0.8
0.7
BPTT steps
BPTT steps
0.6
30 BPTT steps
140 BPTT steps
0.5
environment steps
1e9
B.3.4 ABLATION STUDY
Fig 12 shows the impact of the the number of back-propagation through time steps performed into the backward RNN of the hindsight function while performing full rollouts. This show that learning in hard tasks, where hindsight crucial for performances, is not much impacted by the number of back-propageae propagation steps performed into the backward RNN. This is great news as this indicates that learning challenging credit assignment tasks can happen when the hindsight function sees the whole future but only can backprop through limited window.
1.0
tasks
0.9
prob solve easy tasks
30 stops
0.9
50 steps
70 sleps
140 steps
0.7
0.6
0.5
0.6
0.4
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
environment steps
1e9
environment steps
1e9
Figure 13: Impact unroll length over the probability of solving hard and easy tasks for CCA RNN. Probability of picking up the correct squares for the hard and casy tasks in the 6-task setup of Multi Task Interleaving.
Fig 13 shows how performances of CCA with an RNN for the hindsight function are impacted by the unroll length. As expected, the less you are able to look into the future, the harder it becomes to solve this hard credit assignment task you become limited in your capacity take exogenous effects into account. The two previous results are exciting because to work at its fullest CCA seems only require to have access as many steps into the future possible while not needing to do back- propaaaaaan through the full sequence. This observation is really handy as the environments considered become more complex and with longer episodes.
C RELATION BETWEEN HCA, CCA, AND FC ESTIMATORS
The FC estimators generalizes both the HCA and CCA estimator. From FC, we can derive CCA by assuming that 4, and A, are conditionally independent (see next section). can also derive state and return HCA from FC.
For return HCA, we obtain both an all-action and baseline version of return HCA by choosing . G, For state HCA, first need to decompose the return into sums of rewards, and apply the policy gradient estimator to each reward separately. For pair (X,, Re++), and assuming that Reth function of X for simplicity, choose Φb X We then sum the different FC
19

---

Under review as a conference paper at ICLR 2021
estimators for different values of it and obtain both all-action and single-action version of state HCA.
Note however that HCA and CCA cannor be derived from one another. Both estimators leverage different approaches for unbiasedness, one (HCA) leveraging importance sampling, and the other (CCA) eschewing importance sampling in favor of constraint satisfaction (in the context of infer- ence, this similar to the difference between obtaining samples of the posterior by importance sampling versus directly parametrizing the posterior distribution).
D PROOFS
D.1 POLICY GRADIENTS
Proof of Proposition By linearity of expectation, the expected return can be written E[G] Σ. RR). Writing the expectation as an integral over trajectories, we have:
E(R
Σ
[(oo a.)) R(ar; (1)
Taking the gradient with respect to 0:
(allall Fo, (a)) )) R( ai)
VoE[Re] = Σ
Σ
as)
Sa Ag
We then rewrite (oTT(ax/(ss))
Vo log (aaa (r ) To (a (inr), and obtain
(To(as xx.) P(x. (1 ai)) )) A(ze,a) ai)
V R = Σ
VOTTe(s/(zs))
II
Vo To
Summing over t, we obtain
VE =E
Vo log (Arl
s'st
which can be rewritten (with a change of variables):
V [
=F
V log TO (A,
Et Re
t20
P'2
Vo log no Xp)
Σ
p' Re:
120
e21
=E
S.G.
220
To complete the proof, need to show that (X)) 0. By iterated expecta- tion. [XS)) = [X) = EVV(X, X,]]. and we have [[S
m. Voto(a|Xi) =o((.. Vol
20

---

Under review as a conference paper at ICLR 2021
Proof of Proposition We start from the single action
policy
gradient
VoE[G]
0 and analyse the term for time t, E[S,G,).
B[S,G]] (X,,
[[] Ab) =E (EI,,,Q(X,,A)))))
Vomo(a/x))Q(X..0 a)
The first and fourth inequality come from different applications iterated expectations, the second from the fact S, is constant conditional on X,, Ar, and the third from the definition of Q(,,, A.).
D.2 PROOF OF FC-PG THEOREM
(o(A.) Proof of theorem 7 We need to show that (4,x.)) V(X,, b.)] = O, so that
xx(A.) V(X,, P:) valid baseline. As previously, we proceed with the law of iterated (,,
pectations, by conditioning successively on X2 then t
(X, (A, X,, 1,)
(c)
E S P
v(X, 1.)
=E
E
S
V(X,, B.)
X,, P
P.
(A, Xt. L,)
S: To (e)
BB
v(X.. )E
Xx, 42
(Pe Xx, +b)
Then we note that
E St (x),)( [A, 4b)
(a| To(a|Xe)
X1, $b
Σ Px (a|X,,
VTo(a|Xi) 0.
(a((a|X, Pa 1c)
Proof of theorem]
2
We start from the definition of the Q function:
a(),, =E GG X,, A, = a| Es, G X,, L. A, a) X2, A, a]
1 Pr p/ a D. p.
We also have
P2 Pl (A, al 4, ②)
P = Xr. At)
Pa(A: = a(xx.)
which combined with the above, results in:
P. (A = al D1 = Φ)
Q(x,, a) P_ :p/x,)
Q(Xes 2.
TT(a(X.)
=E (A. a|X,, O. o) Q(Xe: Dr, a) X1
To (x)
For the compatibility with policy gradient, we start from:
BJS.G,] =B Σ Vomo(axx)
21

---

Under review as a conference paper at ICLR 2021
We replace Q(Xe, a) by the expression above and obtain
Pr (Ar alX,, 2; 2 Q(X, Pc, X;
E[S =E
(o)To(
Te(a
(x(A, a Xx; +t ())
18
E
(oTo(()(X1)
R(X,, Pex a) Xx
[e(a
E
E
Ve log Tol a|X,, D/ - ,)Q(X,, ter a) Xt
E8
Va log To (a/X,) (Ar a|x,, 2r x]Q(Xx; 21,
Note that in the case of large number of actions, the above can be estimated by
Ve log Te (A (A IP, (A]iX, 2 - 2) Q(x,, Pt. AD) To( (A((()))
where A is an independent sample from тe (-(x,)) note in particular that A₁ shall NOT be the action A₁ that gave rise to e which would result in biased estimator.
D.3 PROOF OF CCA-PG THEOREMS
Assume that b, and A, are conditionally independent on X,. Then, P.(A==aX.,) particular, is true when evaluating the random value A, From this simple observation, both CCA-PG theorems follow from the FC-PG theorems.
(A,, 1. In
To prove the lower variance of the hindsight advantage, note that V(G. V(X,, +) B( (X,,, 2.)) = (X, (.)?] VIG, - [[G,-V(X.). -[()))][[[GC.>>) VXX)) = [X))
where the second equality comes from the fact that (X, x,), Ø,] = V(X,, $,) To prove the first statement, we have (G, - (X,,, 2,)² G7 + V(,,, 2,)= -2,,, 2G.V(X, 2r), and apply the law of iterated expectations to the last term:
(X,,V p. =E|E(G,V(X, x,) 1.11
=X[V(X,, D,) 2.]] [E[ (X,, 4.)3
The proof for the second statement is identical. Finally, we note that by Jensen's 's inequality, we have E[V (X,, )b < ([V().) from which we conclude that V(G. V(X,, o.)) < V V(X.)]
D.4 PROOFS MODEL-BASER GRADIENT THEOREMS IN APPENDIX
Proof of Lemma 7 The proof follows from two simple facts. The first is that the return is de- terministic function G(X,, a, E,+). The second is that, from the law of iterated expectations we have EE,, [G(X,, a', ,,, Ex,+ [Eg ix,+ [G(X,, a', Ett )[] for any distribution of X,+. The left hand-side is Ex (((X))))) Taking the distribution of Xx+ to be p(. a), obtain the desired result.
Proof of Lemma
The policy gradient can be written:
P(ε,) (4
(5)
AI.E,
But also have:
P(E+)) = P(E-- = Jx
(144, (X
22

---

Under review as a conference paper at ICLR 2021
For simplicity, denote To(A|[[)) (44 Combined with equa- tion (5) we find:
KTO J
(6)
X.t.AGEE.M
Next, we analyze the same quantity but replacing
by G(Xi, Ar, Ect) and find:
Ix Jemnieen KTO Koo (A.
log no (0 A,,E))
J Je
Ac, (1 Volo/ixx)VVologoo()]] =
since (JN: (A O.
Subtracting equation
from 6 we obtain the desired result.
E RL ALGORITHMS, COMMON RANDOMNESS, STRUCTURAL CAUSAL MODELS
In this section, we provide an alternative view and intuition behind the CCA-PG algorithm by inves- tigating credit assignment through the lens of causality theory, in particular structural causal models (SCMs) (Pearl 2009a). We relate these ideas to the use of common random numbers (CRN), standard technique in optimization with simulators (Glasserman & Yao 1992). We start by pre- senting algorithms with full knowledge of the environment in the form of both perfect model and access the random number generator (RNG) and see how an SCM of the environment can improve credit assignment. We progressively relax assumptions until no knowledge of the environment or its random number generator is required and CCA-PG is recovered.
E.1 STRUCTURAL CAUSAL MODEL OF THE MDP
Structural causal models (SCM) Peaal 2009a) are, informally, models where all randomness is exogenous, and where all variables of interest are modeled as deterministic functions of other vari- ables and of the exogenous randomness. They are of particular interest in causal inference as they enable reasoning about interventions, i.e. how would the distribution of variable change under ex- ternal influence (such as forcing a variable take given value, or changing the process that defines varaible), and about counterfactual interventions, i.e. how would particular observed outcome (sample) of a variable have changed under external influence. Formally, a SCM a collection of model variables {V V), exogenous random variables {E E }.. and distributions {P) & E), one per exongeous variable, and where the exogenous random variables are all assumed to be inde- pendent. Each variable V is defined by function V (pa()V))))) where pa(V) is subset of V called the parents of V. The model can be represented by a directed graph in which every node has an incoming edge from each of its parents. For the SCM be valid, the induced graph has be a directed acyclic graph (DAG), i.e. there exists a topological ordering of the variables such that for any variable V. pa(V)) .V....., .,, V;-1:: in the following we will assume such an ordering. This provides a simple sampling mechanism for the model, where the exogenous random variables are first sampled according their distribution, and each node is then computed in indexing order. Note that any probabilistic model can be represented as SCM by virtue of reparametrization Kingma & Ba 42014); [Buesing et al. (2019). However, such a representation not unique, i.e. different SCMs can induce the same distribution.
We now parameterize the MDP given in section 2.1 as a SCM. The transition from X; to X under A, is given by the transition function fx: X++1 able random number E,N_ The policy function f maps a random number E policy parameters 8, and current state X, to the action A, (X,,, ET (). Together, f and E induce the pol- icy, a distribution ( X,) over actions. Without loss of generality we assume that the reward deterministic function of the state and action: R2 [R At). ex and E random
(x(,, Ar, EXX with exogenous vari-
23

---

Under review as a conference paper at ICLR 2021
variables with fixed distribution; all changes to the policy absorbed by changes to the de- terministic function f² Denoting & = (E, E note the next reward and state (Xp=1: Rt) are deterministic functions of X, and E,, since have X = f (X,, (",, ET, E,, and simi- larly Rg = r, l (X,, , 0). Let X (Xe)ess and similarly, & = (E) ,e Dest Through the composition of the functions fx, f and R. the return G2 (under policy Tо) is deterministic function (denoted G for simplicity) of Xx, Ar and Ext.
fX,,
E.2 MODEL-KNOWN POLICY GRADIENT
In this section, we assume perfect knowledge of the transition functions, franciooon reward functions, and SCM distribution. We use the term 'model-knwn rather than 'model-based" to describe this situation.
Consider time i, state Xz, and possible action for A,. The return Ge is given by the deterministic function G(x,, a, Ex+ ), and the Q function Q(X,, a) = Es,- [G, = a] is its expectation over the exogenous variables Egt. We are generally interested evaluating the function difference Q(X,,a) - Q(x,,a") for two actions a and a'. Note in particular that the advantage can be written A(X,,0) Eg'nom [Q(X,, a)
Q(X,,a'))) The Q function difference can be estimated by a difference G(X,, E G(X,, a', E where Ext and Ey are two independent samples. If we have direct access to E,+, for instance because we we have access to a simulator and to its random number generator, we can use common random numbers to potentially reduce variance: G(X,, a, E++) - G(X, a'iX,,a',Er, E,+).
Note that if actions were continuous, G differentiable and a' + 8 with å small, the quantity becomes 8Q (X,, a, & x 6, i.e. the gradient of the return with respect to the action a (see Silver et al. 2014 Heess al. 2015 Buesing et al. 2016). In general, we will be interested in cases where R may not be differentiable. However, the example highlights that the use of gradient methods implicitly assumes the of common random numbers, and that return differences computed with common random numbers can be seen as a numerical approximation to the gradient of the return.
Having access to the model, suppose make two sample estimate of the policy gradient using common random numbers, and use the return of one action as baseline for the other. The policy gradient estimate is
VoV(zo) = AA. (S,,, - NY,
where recall that we defined S, as Vo log no (A,/)A 0): In many situations this estimate will have lower variance than one obtained with state-conditional baseline (cf. eq. ( since the use of common noise for G will strongly correlate return and baseline (which differ only in single argument to the function G).
Since A, and A/ are samples from the same distribution, the update above remains valid if we swap A, and A/; averaging the two updates, we obtain a two point policy gradient:
1
2 A,E,,, [Y(, A,, G(X,, A/, &c ))
where Yú denotes the score function differential (Vo log (A, Vo log ( 0)). The use of model is required since we need returns from the same state with two different actions (note that the case of a POMDP the same initial state would require the same history, which often computationally excessive to do).
More generally, we could use K i.i.d. samples A(1)_ ..... empirical return as a bascline for each sample, which yields
((() and use the leave-one-out average
voV(zo)
1 E K
Σ Vo log To (A 1 A
(10)
where A; A (G(X, - G(X,, A.T E.+)
The idea of using multiple rollouts from the same initial state to perform more accurate credit as- signment for policy gradient methods has been used under the name vine by /Schllaa et al. (2015). The authors also note the need for common random numbers to reduce the variance of the multiple rollout estimate (see also Ng & Jordan 2013). Interestingly, if replace A by the argmax of soft- max of the A, we obtain a gradient estimate similar to that of the cross-entropy method, a classical and very effective planning algorithm (De Boer al. 2005
Langlois al. 2019).
24

---

Under review as a conference paper at ICLR 2021
E.3 MODEL-BASED COUNTERFACTUAN POLICY GRADIENT
In the previous section, we derived low-variance policy updates under the assumption that we have access to both perfect model and its noise generation process. We will now see how model- based counterfactual reasoning allows us to address both of these restrictions, recalling results from (Buesing et al. 2019). First we briefly recall what counterfactuals are. in particular in the context of reinforcement learning. Counterfactual query intuitively correspond to question of the form 'how would this precise outcome have changed, had changed a past action to another one?'. tural model that consists of outcome variables X and action variables A set to estimating the counterfactual outcome X' under an alternative action a' consists in the following three steps:
struc-
Abduction: infer the exogenous noise variables under the observation: & P(E[X).
Intervention: Fix the value of A to a'.
Prediction: Evaluate the outcome X' conditional on the fixed values & and A a'.
We begin with a lemma (following results from Buesing et al. (2019)) which explains that assum- ing model correctness, expectations of counterfactual estimates are equal to regular interventional expectations. Denote p(r[X;) the distribution of trajectories starting from X, and following ma- [(, a) the distribution of trajectories starting from Xt, A, = and following Te after A,, and ((T]X,, a, &ei the distribution of the trajectories starting Xx, A a, following the policy Te but forcing the value of all the SCM exogenous random variables to ε,, (note that this last distribution in fact a deterministic quantity, since all randomness has been fixed).
Lemma 1. Under the assumptions above,
Q(X,, xxxxxx((xXxx [G]
Ex -xxxx((Xx
EE, B i [a]]
(11)
In other words, we can use SCMs to perform off- off-policy or counterfactual evaluation without impor- tance sampling, as long as we can infer the exogenous variables of interest.
This lemma particularly useful when using an imperfect model, which we now assume is the only model available. We denote the 'real-world' or data distribution by pD and model distributions by Pas. Also, let GD denote the true return function and Ga the imperfect model of it. Using the model, model-basee variants of equation (8) are obtained by simply replacing p by PM:
VaV(zo) = E upm
&+) GM, A & ))},
(12)
Using an imperfect model, this update could have high bias. Instead of fully trusting the synthetic data generated by the model, the outer expectation with respect to PD and the inner ones with respect to PM- We obtain the following counterfactual policy gradient estimate:
combine model data and real data in equation (IT), by sampling
Lemma 2. Assuming model bias, the policy gradient update is equal
(oV = Σ Exx (p
-
(13)
where Sy Vo log No (x) is the score function for the counterfactual action, and where G¹ = Gm (Xe, Nr. Ex+ is the model-based counterfactual return estimate. If we explicitly marginalize out Al, we obtain:
Go)
]
Ex, (P)(X)) 1e (x(1)
Σ
(14)
Note that in contrast to eq. (3) and even when assuming a perfect model and posterior, the follow- ing update will generally be biased (we will later explain why):
(ZV( # =E>
7 /Ex,, (X,) EE, spsttE, (.A/ [S. G
(15)
25

---

Under review as a conference paper at ICLR 2021
In equations 13 and 14) above, Xx+ is sampled by the real environment, and E, is from the posterior noise given the observations (which would generally be given by Bayes rule, following P(E,+ (X,] P(E++ P(X, [E++ )). In particular, this estimate does not require access to the random number generator instead, it 'measures' (estimates) what noise in the model must have been give rise the observations given by the real environment.
The term G, = (,, E is the empirical real-world return, while G. = GM, E,-) is the counterfactual return that would have happened mutatis mutandis for action A/, under the same noise realization. A very slight modification to equation (13) is to use the environment only to sample the trajectory X₁+, but use the model for both evaluations of the return:
Ex,+ (X...p. [E (E ( as (X,, Ee, GM A,, A,,
(16)
This may lead to less variance, and potentially even less bias: even though G is a biased estimate of Gp. some of the bias will show up in both terms and cancel out, while it would remain in GD - G
Note also that in the presence of model bias, it is likely that equations (13) and (16) would suffer from significantly less issues (bias and variance) than their purely model-based alternative (12).
as the counterfactual updates are grounded in real data (Xe+ PD(()) and corresponding "reconstruction" instead of a prior sample.
E.4 FUTURE CONDITIONAL VALUE FUNCTIONS
In the previous section, we assumed knowledge of (potentially imperfect) model but no access to the random number generation; in this sub-section, make the inverse assumption: we assume we have access to the random number generation, but develop a model-free method that can leverage the access to the entropy engine without explicitly assuming the model.
Let us consider again the vanilla, single action policy gradient estimate:
(ZV( = E[S.(G, - V(X))
Classically, the baseline function is assumed to be function of X, (recall that in the POMDP case, X, includes the history of observations). If is a function of any quantity which is statistically dependent on Ag conditionally on X₁, the baseline could result in biased estimator for the policy gradient. A sufficient, standard assumption to guarantee this condition, is to not use any data from the future relative to time step as input for V, although such knowledge is available in principle in off-line policy updates. While the optimal baseline may not necessarily be a state value function, a good surrogate for determining a baseline is to minimize the variance of the advantage: for a state-dependent baseline, this corresponds to setting the baseline to the value function.
Note that in structural causal model the random variables & are explicitly assumed to have a distribution affected by other random variables, in particular & 1 A,,X, It therefore valid to include them in the baseline; by the same argument as above, a strong candidate baseline is therefore VX,, & E[G, (x,, Ex J. What does this baseline correspond to? Note that in this expectation the only randomness left is in action as; the corresponding generalized value function in fact V(X,, Ex+) = Σ. Ta (a) (s (XX,, a, E. Learning this value function is therefore very closely related to learning the return function G, which itself is closely related to learning the composition of the transition and reward functions. The corresponding policy gradient becomes:
E A, - V(X,, E, )]]
(17)
where V(X,, Ex+) can be learned by minimizing the square loss between a function of X,, E,+ and empirical returns G,. Note that this estimate of the advantage is also lower variance than that of (X,, and Jensen's 's inequality (see Weber et al. (2019) for a proof, generalized definitions of value functions, and conditions for valid baselines; and see Weaver & Tao (00T): Greensmith et al. al. (2004) for results on optimal baselines for policy gradients.).
G. V(X),, following V(X.)
E.5 RECOVERING MODEL-FREE COUNTERFACTUAL POLICY GRADIENTS (CCA-PG)
In the last two sections, relaxed the assumptions of having access to either a model of the envi- ronment, or to the access to the random number generator. In this section, we combine both ideas to recover our proposed algorithm, CCA-PG.
26

---

Under review as a conference paper at ICLR 2021
To do so, we follow the idea from section E.4 that future-conditional value function can be model- like and result in improved credit assignment; however, like in section E.3 instead of assuming knowledge of Ext. function of the trajectory, such as the sequence of states Xx+, the return, the sequence of observa- tions, actions, etc. In MDPs, Ft only needs to be function of present and future states, in POMDPs, Fi will need to be a function of the entire trajectory, for instance, of present and future agent state.
will estimate it from trajectory information. Let Ft represent any subset or
A first approach, related to distributional reinforcement learning (Veness et al. 2015 Bellemare iet al. 2017). is to forego modeling the environment (as in section E.3) and directly model distri- butions over returns or value functions. We can induce such probabilistic models over returns, by assuming given parametrized base distribution po (E), and approximate posterior q({[F), and value function E
). These components can be learned by the KI.-regularized regression
ΣE ((E.)))) log ((L + + (Q(x,, Er, G., p(E,)
This equation intuitively captures the idea of measuring a & from F, such that &, is approximately independent from the trajectory (represented by the KI. loss) yet good at predicting the return (rep- resented by the value loss). We can then train a policy with counterfactual policy gradient in the following way: For each time t, sample & from (F), compute V and Q and either apply up- date
This approach is flawed however: Even E 1 Ar|X, is assumed to hold under the prior, this will not hold in general under the the posterior q, i.e. which extent the agent knows about the true value of & will in general depend on A, For instance, consider a POMDP corresponding to a maze navigation task, where the only uncertainty is the maze layout. Including the maze layout in the value function will not bias the policy gradient update, and typically lower its variance. However, if we train (in a supervised fashion) network produce observations, and provided the value function with a hindsight estimate of the map, the resulting policy update would in general be biased. This is the same reason why equation (13) is in general biased, even assuming a perfect model and posterior.
estimate of the map given the agent's
For this reason, we forgo explicit probabilistic modeling, and choose an implicit approach, modeling a function L; of the trajectory that captures information for predicting return, and therefore only implicitly perfors inference over & Following the intuition developed this section, we require that b be independent of A, while predicting returns accurately, which finally connects back to the algorithms detailed in section 2
F LINKS TO CAUSALITY AND SIMPLE EXAMPLES
In this section, we will further link the ideas developed in this report to causality theory. In particular we will connect them to two notions of causality theory known as individual treatment effect (ITE) and average treatment effect (ATE). In the previous section, we extensively leveraged the framework of structural causal models. It is however known that distinct SCMs may correspond to the same distribution; learning a model from data, we may learn a model with correct distribution but with with incorrect structural parametrization and counterfactuals. We may therefore wonder whether counterfactuall-bssee approaches may be flawed when using such a model. We investigate this ques- tion, and analyze our algorithm in very simple settings for which closed-form computations can be worked out.
F.1 INDIVIDUAL AND AVERAGE TREATMENT EFFECTS
Consider a simple medical example which we model with an SCM as illustrated in figure 14 We assume population of patients, each with full medical state denoted S, which summarizes all factors, known or unknown, which affect a patient's future health such as genotype, phenotype etc. While S is never known perfectly, some of the patient's 's medical history H may be known, including current symptoms. On the basis of H, a treatment decision is taken; as is often done, for simplicity consider T' to be binary variable taking values in [1=' "==treatmenn'' 0='no treatment') }. Finally, health state and treatment T result in a observed medical outcome O, a binary variable taking values in (1='cd'"'', not cured'), For given value 5 and T = t, the outcome is function
27

---

Under review as a conference paper at ICLR 2021
(also denoted O for simplicity) ((s,t). Additional medical information F may be observed, e.g. further symptoms or information obtained after the treatment, from tests such as X-rays, blood tests, autopsy.
S
H
T
O
F
Figure 14: The medical treatment example as a structured causal model.
In this simple setting, we can charactertize the effectiveness of the treatment for an individual patient with profile $ by the Individual Treatment Effect (ITE) which is defined as the difference between the outcome under treatment and no treatment.
Definition (Individual Treatment Effect).
ITE(s) E s, do 1)] E do =]] 0(,, = -)s,=) (18)
The conditional average treatment effect is the difference in outcome between the choice of T =1
and T when averaging over all patients with the same set of symptoms h Definition 2 (Conditional Average Treatment Effect).
ATE(h) = E H = h. do(T = 1)] B = h, do = 0)] = p p(s
= s/H -) -0s,
(19)
Since the exogenous noise (here, S) generally not known, the ITE is typically an unknowable quantity. For a particular patient (with hidden state S), we will only observe the outcome under T 0 or 7 1, depending on which treatment option was chosen; the counterfactual outcome will typically be unknown. Nevertheless, for given SCM, it can be counterfactually estimated from the outcome and feedback, using the procedure detailed in section E.3 (we suppose included in F to simplify notation)
Definition (Counterfactually Estimated Individual Treatment Effect).
CF-ITE(H = h, f, 5(00 = P(S b,
(20)
CF-ITE|H = F = f.T= P(S = - f. T 1)0 8(0 1)
(21)
In general the counterfactually estimated ITE will be exactly the ITE, since there may be re- maining uncertainty on However, the following statements relate CF-ITE, ITE and ATE:
If S is identifiable from and with probability one, then the comterfactuallly-stitaeeed ITE is equal to the ITE.
The average (over S, conditional on H) of the ITE is equal to the ATE.
The average (over S and F, conditional on H) of CF-ITE is equal to the ATE.
Assimilating O to a reward, the above illustrates that the ATE (equation 19 essentially corresponds to difference of Q functions, the ITE (equation 18) to the return differences found in equations (8) and (I7). and the counterfactual ITE to the quantities found equations (13) and (14). In contrast, the advantage G, V(H.) is difference between return (a sample-level quantity) and value
28

---

Under review as a conference paper at ICLR 2021
function (a population-level quantity, which averages over all individuals with the same medical history H); this discrepancy explains why the return-basse advantage estimate can have very high variance.
As mentioned previously, for a given joint distribution over observations, rewards and actions, there may exist distinct SCMs that capture that distribution. Those SCMs will all have the same ATE, which measures the effectiveness a policy on average. But they will generally have different ITE and counterfactual ITE, which, when using model-based counterfactual policy gradient estimators, will lead to different estimators. Choosing the 'wrong' SCM will lead to the wrong counterfactual, and so we may wonder if this is a cause for concern for our methods.
We argue that in terms of learning optimal behaviors (in expectation), estimating inaccurate coun- terfactual is not cause for concern. Since all estimators have the same expectation, they would all lead to the correct estimates for the effect of switching policy for another, and therefore, will all lead to the optimal policy given the information available the agent. fact, one could go further and argue that for the purpose of finding good policies in expectations, we should only care about the counterfactual for precise patient inasmuch as it enables us to quickly and correctly taking bet- ter actions for future patients for whom the information available to make the decision (H) is very similar. This would encourage us to choose the SCM for which the CF-ITE has minimal variance, regardless of the value of the true counterfactual. In the next section, we elaborate on an example to highlight the difference in variance between different SCMs with the same distribution and optimal policy.
F.2 BETTING AGAINST A FATR COIN
We begin from a simple example, borrowed from Pearl (2009b), to show that two SCMs that induce the same interventional and observational distributions can imply different counterfactual distribu- tions. The example consists of game to guess the outcome of fair coin toss. The action A and state S both take their values in {hh 1). Under model I, the outcome O is 1 if A = S and O other- wise. Under model II, the guess is ignored, and the outcome is simply O 1 if = h. For both models, the average treatment effect A h] F[O = t] is 0 implying that in both models, one cannot do better than random guessing. Under model I. the counterfactual for having observed outcome O = 1 and changing the action, is always O O, and vice-versa (intuitively, changing the guess changes the outcome). Therefore, the ITE is 11. Under model II, all counterfactual outcomes equal to the observed outcomes, since the action has in fact no effect on the outcome. The ITE is always O.
In the next section, we will next adapt the medical example into a problem in which the choice of action does affect the outcome. Using the CF-ITE as an estimator for the ATE, we will find how the choice of the SCM affects the variance of that estimator (and therefore how the choice of the SCM should affect the speed at which we can learn which is the optimal treatment decision).
F.3 MEDICAL EXAMPLE
Take the simplified medical example from figure 14 where population of patients with the same symptoms come to the doctor, and the doctor has a potential treatment T to administer. The state S represents the genetic profile of the patient, which can be one of three (GENEA, GENER, GENEc} (each with probability 1/3). We assume that genetic testing is not available and that we do not know the value of S for each patient. The doctor has to make a decision whether to administer drugs to this population or not, based on repeated experiments; in other words, they have to find out whether the average treatment effect is positive or not. We consider the two following models:
In model I, patients of type GENEA always recover, patients of type GENEC never do, and patients of type GENEn recover if they get the treatment, and not otherwise; in particular, in this model, administering the drug never hurts.
In model II, patients of type GENEA and GENEg recover when given the drug, but not patients of type GENEç; the situation is reversed (GENEA and GENE, patients do not recover, GENEc do) when not taking the drug.
29

---

Under review as a conference paper at ICLR 2021
In both models the true value of giving the drug is 2/3, and not giving the drug 1/3, which leads to an ATE of 1/3. For each model, we will evaluate the variance of the CF-ITE, under one of the pair. The results
summarized in table 5 Under model A, the variance of the CF-ITE estimate (which the variance of the advantage used in CCA-PG gradient) is 1 166, while it is under model B, which would imply A is better model leverage counterfactuals into policy decisions.
four possible treatment-outcome
Treatment
Outcome
Type
CF--robb
CF-O
ITE
CF-V
CF-ITE
Var
Drug
Cured
GENEA
1/2
1/2
+1
GENEB
1/2
1/2
+1
+1
1/2
1/2
GENEC
0
1/6
Not cured
GENEA
0
0
GENEB
0
0
0
GENEC
1
0
0
-1
No Drug
Cured
GENEA
0
0
GENEB
0
0
0
0
GENEC
0
1
0
0
1
1
1/6
Not cured
GENEA
0
1/2
-1
-1
1
GENEg
1/2
1/2
-1
-1
1/2 -1/2
-1
GENEC
1/2
0
0
0
0
Table 5: CCA-PG variance estimates in the medical example. CF-Probs. Red value estimates for model blue ones are model CF-Prob denotes posterior probabilities the genetic state given the treatment and outcome O. CF-O the counterfactual outcome. The ITE is the individual treatment effect (difference between outcome and counterfactual outcome). CF-V is the counterfactual value function, computed as the average of CF-O O under the posterior probabilities for S. CF-ITE the counterfactual advantage estimate (difference between and CF-V), Var the variance CF-ITE under the prior probabilities for the outcome.
30


Reviews:
[{"review_id": "hHRwqN8KB9t", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "In this paper, the authors develop a new policy gradient method to reduce the variance in the gradient estimations.\nIn the commonly used policy method, the bias is a function of the state. e.g., V(x_t). In this paper, the authors propose to use bias V(x_t,\\phi_t) where \\phi_t is a statistics of future events such that \\phi_t is conditionally independent of the action at time t.\n\nThe authors show that using such statistics in V(x_t,\\phi_t) results in a reduction in the gradient estimate used in policy gradient methods. \n\n\nLater, the authors also show that their method performs well in practice.\n\n\nThere is a set of problems with the paper's presentation, which resulted in the negative evaluation.\nThe analysis in the paper is straightforward and also easy to follow. However, I could not find how the proposed algorithm learns the \\phi.\n\nI encourage the authors to improve the clarity, presentation, and language in this paper. \n\n1) I did not get what the authors mean by luck or skill. These terms do not seem to be coherent terms in this paper. I highly encourage the authors to rethink such usage. Unless the authors mathematically define it in the paper. \n\n2) \"Another issue of model-free methods is that counterfactual reasoning, i.e. reasoning about what would have happened had different actions been taken with everything else remaining the same, is not possible.\" \n\nCan the authors clarify it? Why is it not? When I learn a Q function, that tells me what would be the expected return if I choose other actions following the same policy, right? \nIf you mean evaluating other policies is not possible, I still doubt the statement is true. \n\n3) \"Given a trajectory, model-free methods can in fact only learn about the actions that were actually taken to produce the data, and this limits the ability of the agent to learn quickly.\"\n\nCan you clarify this? I can use function approximation based methods, and then, the first part of the authors' statement is no longer true. The second statement is inaccurate since the author did not quantify with respect to what method the quickness in learning is compared to.\n\n4) \"actions taken by the agent will only affect a vanishing part of the outcome\". What do the authors mean here? What the vanishing part of the outcome refers to?\n\n5) \"mak- ing it increasingly difficult to learn from classical reinforcement learning algorithms\", what the authors mean by learning from classical RL algorithm? and why the authors think a better credit assessment is needed and is the way to go. What motivates the authors to state the issue is the credit assignment?\n\n6) \"Second, removing the value function V (Xt) from the return Gt does not bias the estimator and typically reduces variance\". Would the author refer to a paper stating that removing the value function V (Xt) from the return Gt typically reduces variance?\n\n7)\"This estimator updates the policy through the score term; note however the learning signal only updates the policy πθ(a|Xt) at the value taken by action At = a \"\nI am not sure I understand this sentence. Is πθ(a|Xt) the policy, or it is πθ. Do authors have a different model for each state and action pair? Even in that case, since the need to normalize action probability, changing πθ(a|Xt) will affect other πθ(a|X) as well. Therefore, I am not sure what the authors mean here.\n\n8) Distinction between single action and all actions.\nIn both propositions 1 and 2, it seems that the learning signal is provided for both actions. It is not clear to me how the authors make the distinction. Especially here \n\"The policy gradient theorem from (Sutton et al., 2000), which we will also call all-action policy gradient, shows it is possible to provide learning signal to all actions,\".\nI am not sure what the authors mean. \n\nThe authors state that\"A particularity of the all-actions policy gradient estimator is that the term at time t for updating the policy ∇π(a|Xt)(Q(Xt, a) depends only on past information;\" but it seems to me that Q is a function of the measure on the future. Isnt it the case?\n\n9) To motivate the usage of phi, the authors talk\u0010 about a scenario in a soccer game, which again I could not find useful, especially when they bring luck and skill. \nThe authors state that \"When using the single-action policy gradient estimate, the outcome of the game being a victory, and ,assuming a ±1 reward scheme, all her actions are made more likely\". \nHow is it possible that all actions become more likely? when their probabilities should be sum to one?\nI am not sure again. Are the authors talking about using one trajectory for all the estimates? The update in proposition 1 shows that in the case the agent action does not change the outcome, then the gradient is zero.\n\n\n10) The authors state that\n\"In contrast, if the agent could measure a quantity Φt which has a high impact on the return but is not correlated to the agent action At , it could be far easier to learn Q(Xt , Φt , a).\"\nIt is not clear why learning Q(Xt, a) is harder than Q(Xt , Φt , a). So far, Q(Xt, a) seems an easier function to approximate and most likely needs a fewer sample to learn Q(x, a) than something presumably complicated like Q(x, \\phi , a).\n\n11) In section 3.1, I strongly encourage the authors to elaborate more clearly on what they do. Is W a scaler? if yes, then how F can be constructed?\n\nDo you draw U,V,W each time step??\n\n\n\n12) Aside from many unclear statements in this paper that the authors can easily address, I could not find how the authors find \\phi. Since this is the main key component of the paper, it would be great if the authors could explain it in depth. I also could not find it clear in the appendix. \n\n13) I strongly encourage the authors to expand their study on plain MDP before getting to the POMDP complication. It is not clear where the performance gain comes from.\n\n\n................................................................\n\nPost rebuttal. The confidence rating is reduced.\nI might have been mistaken, but the authors might find this paper useful. \"Troubling Trends in Machine Learning Scholarship\"\nAgain, I might be wrong, and the mentioned paper might be of no use here.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "PZ778K9KN2p", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "#### Summary:\nThe paper explores a new approach to credit assignment that complements existing work. It focuses on model-free approaches to credit assignment using hindsight information. In contrast to some prior work on this topic, e.g., (Harutyunyan et al. 2019), the paper does not rely explicitly on hand-crafted information, but instead learns to extract useful hindsight information. The contributions of the paper are two-fold. First, the paper introduces two new policy gradient estimators, FC-PG and CCA-PG, and it proves that the novel gradient estimators are unbiased. Second, it provides experimental evidence that the novel estimators are beneficial compared to some prior work (in particular (Harutyunyan et al. 2019)).  \n\n\n#### Comments:\n\nOverall, I found the contributions of the paper interesting, but I'm somewhat on the fence about this paper due to the following pros and cons. \n\nPros: The paper is clearly written, easy to follow, and interesting to read. It provides a good overview of the related work, and motivates well the problem at hand. Furthermore, the paper showcases that its algorithmic approach has theoretical grounding, and it experimentally verifies that it's beneficial compared to concurrent approach from (Harutyunyan et al. 2019). \n\nCons: Given that a very similar type of counterfactual credit assignment approach has already been proposed in prior work, the technical contributions (theorems) of the paper seem somewhat incremental. The experiments, while indicating potential benefits of the proposed approach, utilize relatively simple environments compared to some of the recent papers on credit assignment (e.g. (Arjona-Medina et al. 2019), (Guez et al 2019)). Moreover, the experiments could include more state of the art baselines. \n\nApart from these high level comments, the following comments include suggestions for improvements and questions.  \n\nRelated work: Since the hindsight credit assignment of (Harutyunyan et al. 2019) is a special case of FC-PG, this connection should be mentioned earlier in the paper, not just in the related work section. The flow of the paper is currently misleading, given that there is prior work that does propose quite similar ideas, e.g., the content between the title to section 2.4 does not seem to be reflect relevant prior work. Perhaps referencing relevant papers in earlier sections, or moving the related work section, would resolve this issue. \n\nNotation: Notation in the paper often omits important dependences, making some of the calculations confusing or not immediately clear. In the interest of making the claims more precise, it would be very useful to add important dependencies where needed. For example, in equation (1), does $P(a|X_t, \\Phi_t)$ depend on policy $\\pi$? Moreover, the notation does not seem to be consistent, e.g., policy $\\pi$ sometimes has dependency on $\\theta$ sometime not (in gradient calculations).  \n\nAppendix: I think adding some parts from the appendix could improve the clarity of the content. In particular, the last paragraph on Page 3 that starts with 'We ensure that these statistics...' is not providing sufficient explanations regarding the technical content important for understanding the results. It is also not clear if all the content in the appendix is relevant for the results described in the main text. \n\nMinor typos: \n-removed from the advantage, resulting a significantly lower variance estimator. --- resulting in?\n-$\\lambda_{IM}$ does not seem to be defined before being used (in the paragraph before section 3.2)\n-and the the benefits of the more general FC-PG and all-actions estimators. --- remove one 'the'?\n\n#### Questions:\n\nA) I'm a bit puzzled by the discussion regarding the conditional independence requirement in Section 2.5. Why is this an 'intuitive' requirement? How does it influence the interpretation in the  paragraph before Theorem 3? How does this compare to  (Harutyunyan et al. 2019) argument that '$h(.)$ quantifies the relevance of action a to the future state $X_k$'? \n\nB) The proof of Theorem 3 and Theorem 4 in Section D3 says that the theorems follows from Theorem 1 and Theorem 2 given the conditional independence assumption. Could you explain in more detail why the second statement (about variance) in Theorem 3 follows from Theorem 1 and 2? \n\nC) How does this approach compare to Ferret et al.: Self-Attentional Credit Assignment for Transfer in Reinforcement Learning?", "extra_scores": {}, "extra_text": {}}, {"review_id": "O3f9oS_X1Rj", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "\nThe message and paper propose a couple of environments where there is exogenous noise added to the reward function and the particular method in the paper specifically looks at this type of noise. While the method proposed may work in these types of environments it's not clear if more interesting environments do have these properties and we should be more concerned with this problem or that the environments used in the paper were specifically constructed to fit the use case of the algorithm.\n\nThe proposed method in the paper does offer interesting insight into how certain temporary consistent variables and the identification of such variables can help decrease the variance over policy estimates. However, the results in the paper are not overly convincing with respect to understanding the importance of this method on more realistic tasks that the community is generally interested in.\n\nSome more detailed notes:\n- The introduction does not state that the particular credit assignment problems being looked into is that of partially observed environments. Overall, I find the writing in the introduction to not motivate the problem well our lead the reader towards what to expect in the rest of the paper. This makes it very difficult to understand and appreciate the paper.\n- If it's still not clear from the middle section to let the detail of the contribution is going to be period by this point it sounds like the method is just going to be a modification to a q function.\n- There does not appear to be my significant information on how the mutual information metric is computed between the action space and latent variable space.", "extra_scores": {}, "extra_text": {}}, {"review_id": "K41vnJMig7f", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 work attempts to address the problem posed by high reward variance and low sample efficiency in model-free RL algorithms. The proposal is to use counterfactuals to do finer-grained credit-assignment and reasoning about alternative actions without having to learn a potentially difficult environment model. \n\nThis is done by conditioning the value function on a random variable $\\phi$ that attempts to capture everything else about the future trajectory not resulting from the current action. This is done by maximizing the independence between $\\phi$ and $A$ given the current state. A classifier that predicts action based on $\\phi$ is required to do the above. This is also learned from data.\n\nClaimed contributions:\nProposing a set of environments with difficult credit assignment.\nNovel algorithms that use counterfactuals that are unbiased and guarantee lower variance.\n\n+ The approach seems novel and interesting. \n+ The claimed contributions are supported to a large extent by theory and experimentation.\n+ The idea of constructing value functions conditioned on future trajectory information is not novel (Hindsight Credit Assignment does this), but the idea of learning the conditioning variable is (HCA uses states or returns).\n+ The paper is clearly written. The illustrative example of counterfactuals in hindsight with Alice and Megan is helpful.\n+ The approach is evaluated first on a bandit task and then on different versions of a partially observable gridworld environment and finally on a multi-task setting.\n+ Comparison to vanilla policy gradient and a couple of versions of prior work (HCA) over a substantial number of random seeds. \n+ The task interleaving setting is an interesting benchmark for multi-task settings. \n\nThis work builds off of HCA and mainly addresses the case of high variance in rewards where the prior work seems to fail. It performs similar to vanilla PG on environments with little randomness in reward for similar actions, but better than HCA. \n\nThe authors claim that they do not require a model of the environment but a classifier $h(A_T|X_T, \\phi)$ is learned which resembles an inverse model. Even though the approach does not require building a forward model, I am curious to know the performance of a model-based approach such as by Buesing et al. trained on the same data available for $h(A_T|X_T, \\phi)$ in these environments. Is it difficult to learn a model for the proposed tasks?\n\nI think the work contains enough novelty, the writing is clear and the experimentation is extensive. But, I am unsure whether to recommend acceptance without a model-based baseline trained on data available to the classifier used in this approach.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors aim to develop a new method for credit assignment, where certain types of future information is conditioned on.  The authors are well-aware that naive conditioning on future information introduces bias due to Berkson's paradox (explaining away), and introduce a number of corrections (described in section 2.4 and 2.5).

The authors illustrate their approach via a number of simulation studies and constructed problems.

I think it would be nice if the authors found a way of connecting their notion of counterfactual to one used in causal inference (for instance, I think there is a connection via e.g. importance correction terms).

Reviewers were worried about the contribution being incremental given existing work (from 2019), and relative simplicity of the evaluation of the approach, compared to existing similar work.

Decision: Reject