A Survey of Temporal Credit Assignment in Deep Reinforcement Learning
Authors: Eduardo Pignatelli
Johan Ferret
Matthieu Geist
Thomas Mesnard
Hado van Hasselt
Laura Toni
Venue: Accepted by TMLR ()

Abstract: The Credit Assignment Problem (CAP) refers to the longstanding challenge of Reinforcement Learning agents to associate actions with their long-term consequences. Solving the CAP is a crucial step towards the successful deployment of RL in the real world since most decision problems provide feedback that is noisy, delayed, and with little or no information about the causes. These conditions make it hard to distinguish serendipitous outcomes from those caused by informed decision-making.
However, the mathematical nature of credit and the CAP remains poorly understood and defined.
In this survey, we review the state of the art of Temporal Credit Assignment (CA) in deep RL. We propose a unifying formalism for credit that enables equitable comparisons of state-of-the-art algorithms and improves our understanding of the trade-offs between the various methods. We cast the CAP as the problem of learning the influence of an action over an outcome from a finite amount of experience. We discuss the challenges posed by delayed effects, dilution, and a lack of action influence, and analyse how existing methods aim to address them. Finally, we survey the protocols to evaluate a credit assignment method and suggest ways to diagnose the sources of struggle for different methods.
Overall, this survey provides an overview of the field for new-entry practitioners and researchers, it offers a coherent perspective for scholars looking to expedite the starting stages of a new study on the CAP, and it suggests potential directions for future research.

Published in Transactions on Machine Learning Research (04/2024)
A Survey of Temporal Credit Assignment in Deep Reinforcement Learning
Eduardo Pignatelli
epignatelli@ucl.ccc.u uk
University College London
Johan Ferret Google DeepMind
jfereet@ggongee.cmm
Hado van Hasselt Google Mied
hado hado@google.com
Matthieu Geist
mfgelst@@gogle..com
Google DeepMind
Thomas Mesnard Google Mied
mesnard@google.com
Olivier Pietquin Google DeepMind
pietquin Agoogle.e@goo
Laura Toni University College London
LtoniQucl.ccm uk
Reviewed OpenReview: https: // opwnreeveee....ee.e.mmmm net/ pormff id- bittr6Lggff
Abstract
The Credit. Assignment Problem (CAP) refers to the longstanding challenge of Reinforce- ment Learning (RL) agents to associate actions with their long-term consequences. Solving the CAP is crucial step towards the successful deployment of RL in the real world since most decision problems provide feedback that is noisy, delayed, and with little or no informa- tion about the causes. These conditions make it hard to distinguish serendipitous outcomes from those caused by informed decision-making and the CAP remains poorly understood and defined. In this survey, we review the state of the art Temporal Credit Assignment (CA) in deep RL. We propose a unifying formalism for credit that enables equitable comparisons of state of the art algorithms and improves our understanding of the trade-offs between the various methods. We cast the CAP the problem of learning the influence of action over outcome from finite amount of experience. We discuss the challenges posed by delayed effects, transpositions, and lack of action influence, and analyse how existing methods aim to address them. Finally, we sur- vey the protocols to evaluate a credit assignment method and suggest ways to diagnose the sources of struggle for different methods. Overall, this survey provides an overview the field for new-entry practitioners and rescarchers, it offers coherent perspective for scholars looking to expedite the starting stages of study the CAP, and suggests potential directions for future research.
However, the mathematical nature of credit

---

Published in Transactions on Machine Learning Research (04/2024)
1 Introduction
RL is poised to impact many real world problems that require sequential decision making, such as strategy
(Silver et al., 2016; 2018; Schrittwieser et al., 2020; Authony et al., 2020; Vinyals et al., 2019; Perolat et al., 2022) and arcade video games (Mnih et al., 2013; 2015; Badia et al., 2020; Wurman et al., 2022),
climate control (Wang& & Hong, 2020), energy management (Gao, 2014), car driving (Filos et al., 2020)
and stratospheric balloon navigation (Bellemare et al., 2020), designing circuits (Mirhoseini et al., 2020).
cybersecurity (Nguyen & Reddi, 2021), robotics (Kormushev et al., 2013), or physics (Degrave el al., 2022).
One fundamental mechanism allowing RL agents to succeed in these scenarios is their ability to evaluate the influence of their actions over outcomes e.g., a win, loss, a particular event, a payoff. Often, these outcomes are consequences of isolated decisions taken in a very remote past: actions can have long-term effects. The problem of learning to associate actions with distant, future outcomes is known as the temporal Credit Assignment Problem (CAP): to distribute the credit of success among the multitude of decisions involved (Minsky, 1961). Overall, the influence that an action has on an outcome represents knowledge in the form of associations between actions and outcomes (Sutton et al., 2011; Zhang et al., 2020). These associations constitute the scaffolding that agencies can use to deduce, reason, improve and act to address mecision-making problems and ultimately improve their data efficiency.
Solving the CAP is paramount since most decision problems have two important characteristics: they take a long time to complete, and they seldom provide immodiate feedback, but often with delay and little insight as to which actions caused it. These conditions produce environments where the feedback signal is weak, noisy, deceiving, and the ability to separate serendipitous outcomes from those caused by informed decision- making becomes hard challenge. Furthermore, these environments grow in complexity with the aim to scale to real-world tasks (Rahmandad et al., 2009; Luoma et al., 2017), the actions taken by an agent affect an increasingly vanishing part. of the outcome. In these conditions it becomes challenging to learn value functions that accurately represent the influence of an action and to be able to distinguish and order the relative long-term values of different actions. In fact, canonical Deep Reinforcement Learning (Deep RL) solutions to control are often brittle to the hyperparameter choice (Henderson et al., 2018), inelastic to generalise zero-shot to different tasks (Kirk et al., 2023), prone to overfitting (Behzadan & Hsu, 2019; Wang et al., 2022), and sample-inefficintt (Ye et al., 2021; Kapturowski et al., 2023). Overall, building a solid foundation of knowledge that can unlock solutions to complex problems beyond those already solved calls for better CA techniques (Mesnard et al., 2021).
In the current state of RL, action values are a koy proxy for action influence. Values actualise a return by synthesising statistics of the fulure into properties of the present: they transform a signal dependent on the future into one dependent only on the present. Recently, the advent of Deep RL (Arulkumaran et al,, 2017) granted access to new avenucs to express credit through values, either by using memory (Goyal et al., 2019; Hung et al., 2019), associative memory (Hung et al., 2019; Ferret et al., 2021a; Raposo et al., 2021), counterfactuals (Mesnard et al., 2021), planning (Edwards et al., 2018; Goyal et al., 2019; van Hassolt et al., 2021) or by meta-learning (Xu et al., 2018; Houthooft et al., 2018; Oh et al., 2020; Xu et al., 2020; Zahavy et al., 2020). The research on CAP is now fervent, and with a rapidly growing corpus of works.
Motivation. Despite its central role, there is little discussion on the precise mathematical nature of credit. While these proxies are sufficient to unlock solutions to complex tasks, it remains unclear where to draw the line between a generic measure of action influence and credit. Existing works focus on partial aspects or sub-problems (Hung et al., 2019; Arjona-Medina et al., 2019; Arunugam et al., 2021) and not all works refer to the CAP explicitly in their text (Andrychowicz et al., 2017; Nota ct al., 2021; Goyal et al., 2019), despite their findings providing relevant contributions to address the problem. The resulting literature is fragmented and lacks a space to connect recent works and put their efforts perspective for the future. The field still holds open questions:
Q1. What is the credit of an action? How is it different from an action value? And what is the CAP? What in words, and what in mathematics?
Q2. How do agents learn to assign credit? What are the main methods in the literature and how can they be organised?
2

---

Published in Transactions on Machine Learning Research (04/2024)
Q3. How can evaluate whether method is improving on challenge? How monitor advance- ments?
Goals. Here, propose potential answers to these questions and out realign the fundamental issue raised by Minsky (1961) to the Deep RL framework. Our main goal is to provide overview of the field to new-entry practitioners and rescarchers, and, for scholars looking to develop the field further, to put the heterogeneous set of works into a comprehensive, coherent perspective. Lastly, we aim to reconnect works whose findings are relevant for CAP, but that do not refer to directly. To the best of our knowledge, the work by Ferret (2022, Chapter 4) is the only effort in this direction, and the literature offers no explicit surveys on the temporal CA problem Deep RL.
Scope. The survey focuses temporal CA in singlo-agent Deep RL, and the problems of (i) quantifying the influence of an action mat mathematiaalyy and formalising mathematical objective for the CA problem (ii) defining its challenges, and categorising the existing methods to learn the quantities above, (Mi) defining suitable evaluation protocol to monitor the advancement of the field. We do not discuss structural CA in Deep Neural Networks (DNNs), that is, the problem of assigning credit or blame to individual parameters of DNN (Schmidhuber, 2015; Balduzzi et al., 2015). We also do not discuss CA multi-agent RI., that is, ascertain which agents are responsible for creating good reinforcement signals (Chang et al., 2003; Focrster et al., 2018). When credit (assignment) is used without any preceding adjective, we always refer temporal credit (assignment). In particular, with the adjective temporal we refer to the fact that "each ultimate success is associated with a vast number of infernal decisions" (Minsky, 1961) and that these decisions, together with states and rewards, are arranged to form temporal sequence.
The survey focuses on Deep RL. In surveying existing formalisms and methods, we only look at the Deep RL literature, and when proposing new ones, we tailor them to Deep RL theories and applications. We exclude from the review methods specifically designed to solve decision problems with linear or tabular RL, as they do not bode well for scaling to complex problems.
Outline. We address Q1., Q2. and Q3. in the three major sections of the manuscript. Respectively;
Section addresses Q1., proposing a definition of credit and the CAP and providing a survey of action influence measures.
Section and Section 6 address Q2., discussing the key challenges to solving the CAP and the existing methods to assign credit, respectively.
Section answers Q3., reviewing the problem setup, the metries, and the evaluation protocols to monitor advancements the field.
Section 8 summarises the main points of the manuscript and provides a critical discussion to highlight the open challenges.
For each question, we contribute by: (a) systematising cristing works into simpler, coherent space; (b) dis- cussing it, and (c) synthesising our perspective into a unifying formalism. Table outlines the suggested reading flow according to the type of reader.
Reader type
Suggested Flow
Specialised CA scholar
+ + 1-8-445-2
5 + +2
RL researcher
1+8-4455-6
Deep Learning researcher
1-3-445-664
Practitioner (applied rescarcher)
6-44-33
Proposing new CA method
8+7-6-224
Table 1: Suggested flow of reading by type of reader support the outline in Section 1. Numbers represent section numbers.
3

---

Published in Transactions on Machine Learning Research (04/2024)
2
Related Work
Three existing works stand out for proposing a better understanding of the CAP explicitly. Ferret (2022, Chapter 4) designs a conceptual framework to unify and study credit assignment methods. The chapter proposes a general formalism for a range of credit assignment functions and discusses their characteristics and general desiderata. Unlike Ferret (2022, Chapter 4), we survey potential formalisms for a mathematical definition of credit (Section 4); given the new formalism, we propose an alternative view of the methods to assign credit (Section 6), and an evaluation protocol to measure future advancements in the field. Arumugam et al. (2021) ) analyses the CAP from an information theoretic perspective. The work focuses on the notion of information sparsity to clarify the role of credit in solving sparse reward problems in RL. Despite the work questioning what credit. is mathematically, it does not. survey existing material, and it does not provide a framework that can unify existing approaches to represent credit under a single formalism. Harutyunyan et al. (2019) propose a principled method to mcasure the credit of an action. However, the study does not aim to survey existing methods to measure credit, the methods to assign credit, and the methods to evaluate credit assignment. method, and does not aim to organise them into cohesive synthesis.
The literature also offers surveys on related topics. We discuss them in Appendix A to preserve the fluidity of the manuscript.
As a result, none of these works position CAP in a single space that enables thorough discussion, assessment and critique. Instead, we propose a formalism that unifies the existing quantilies that represent the influence of an action (Section 4). Based on this, we can analyse the advantages and limitations of existing measures of action influence. The resulting framework provides way to gather the variety of existing methods that learn these quantities from experience (Section 6), and to monitor the advancements in solving the CAP.
3 Notation and Background
Here we introduce the notation that we will follow in the rest of the paper and the required background.
Notations. We use calligraphic characters to denote sets and the corresponding lowercases to denote their elements, for example, x E X. For a measurable space (X, Σ), we denote the set of probability measures over X' with A(X). We use an uppercase letter X indicate a random variable, and the notation Fx to denote its distribution over the sample set X, for example, Px X' A(Y). When we mention random event X (for example, random action) we refer to random draw of a specific value E X from its distribution Px and we write, X ~ Fx. When a distribution is clear from the context, we omit it from the subscript and write P(X) instead of Px (x)). We use (x(x) for the indicator function that maps an element I E X' to 1 if x E y C X' and otherwise. We use R to denote the set of real numbers and B = {0, 1} to denote the Boolean domain. We use (x) = || = sup, |aa| to denote the Ê-infinity norm of a vector x of components F,, We write the Hallback--eibler divergence between two discrete probability distributions (X) and (X( with sample space X as: (X))P()))P(())))))
(X)
(PPx)P (og(F(())/P(()))
Reinforcement Learning. We consider the problem of learning by interacting with an environment. A program (the agent) interacts with an encironment by making decisions (actions). The action is the agent's interface with the environment. Before each action, the agent may observe part of the environment and take suitable actions. The action changes the state of the environment. After each action, the agent may perceive a feedback signal (the reward). The goal of the agent is to learn a rule of behaviour (the policy) that maximises the expected sum of rewards.
Markov Decision Processes (MDPs). MDPs formalise decision-making problems. This survey focuses on the most common MDP settings for Deep RL. Formally, discounted MDP (Howard, 1960; Puterman, 2014) is defined by a tuple M = (S, RR, u, 7). S is a finite set of states (the slate space) and A is a finite set of actions (the action space). R: x A [rmin: Tmaa] is a deterministic, bounded reward function that maps a statc-action pair to a scalar reward r. 7 E [0, 1] is a discount factor and j S x A + A(S) is a transition kernel, which maps a state-action pair to probabilities over states. We refer an arbitrary state E S with 8, an action E A with and a reward r E [Fminy Fmaa] with r. Given a state-action tuple
4

---

Published in Transactions on Machine Learning Research (04/2024)
(s,a), the probability of the next random state S141 being s' depends state-trunsition distribution: (S = SS, = 8, A, = a) jus' |s, a), Vs, E S. We refer to St as the random stale at time t. The probability of the action depends on the agent's 's policy, which is a stationary mapping π : + ((A), from a state to a probability distribution over actions.
These settings give rise to a discrete-time, stateless (Markovian), Random Process (RP) with the additional notions of actions to represent decisions and rewards for feedback signal. Given an initial state distribution P (So); the process begins with random state 8o ~ Pyo Starting from So, at each time t the agent interacts with the environment by choosing next state St+1 ~ P,. If a state is also an absorbing state (s E S C S), the MDP transitions to the same state 8, with probability 1 and reward O, and we say that the episode terminates. We refer to the union of each temporal transition (st, Te, as a trajectory or episode d = { Te, the horizon of the episode.
action A, (-1ss),,, observing the reward Te Rs As) and the
Tt,
Tey: 0 S S T), where T is
We mostly consider episodic settings where the probability of ending in an absorbing state in finite time is 1, resulting in the random horizon T. We consider discrete action spaces A {a; 1 S n) only,
A trajectory is also a random variable in the space of all trajectorics D = (S x Ax and its distribution is the joint of all of its components PD( = IP PA.SS. ( 01, fi,..., sT.) Given an MDP . = (S, R. 2) and fixing a policy a produces a Markov Process (MP) M and induces a distribution over trajectory P,,= (D).
We refer to the return random variable Ze as the sum of discounted rewards from time & to the end of the episode, Z,
The control objective of an RL problem is to find a policy x¹ that maximises the expected return,
n" E argmax E E,,,
Σ 7 R(S Ad) E [Zo]]
(1)
Partiall--Observable MDPs (POMDPs). POMDPs are MDPs in which agents do not get to observe a true state of the environment, but only a transformation of it, and are specified with an additional tuple (O),o); where O is an observation space, and no S AOO) is observation kernel, that maps the true environment state to observation probabilities. Because transitioning between observations is not Markovian, policies are a mapping from partial trajectories, which we denole as histories, to actions. Histories are sequences of transitions fü- = {Oo} U {Ax, RR, Ok+1 :< k < (0x R)*== = H.
Generalised Policy Iteration (GPI). We now introduce the concept of value functions. The state value function of a policy æ is the expected return of the policy from state 8t, (=(s) = Eu, = s]. The action-value function (or Q-function) of a policy æ is the expected return of the policy from state 8; the agent takes or, 9t (s. = E,,, [Z.[S s, A, = a). Policy Evaluation (PE) then the process that maps policy π to its value function. A canonical PE procedure starts from an arbitrary value function Vo and iteratively applics the Bellman operator, T, such that:
(2) where 0g denotes the value approximation at iteration k, A, ~ Pr(()))), and S ~ Pp, A.). The Bellman operator is y-contraction in the fo and the & norms, and its fixed point the value of the policy и. Hence, successive applications of the Bellman operator improve the prediction accuracy because the current value gets closer to the true value of the policy. We refer to the PE as the prediction objective (Sutton & Barto, 2018). Policy improvement maps policy to improved policy:
( = T [6r (S.) == E.., [R(S,, + (Dx(S++))
mh+ i (a| = G( S] [a (argmax (R(S,u) + (S)) 1laa) (argmax (S,(S, ueA
"EA
We refer to GPI as general method to solve the control problem (Sutton & Barto, 2018) deriving from the composition of PE and Policy Improvement (PI). In particular, we refer to the algorithm that alternates arbitrary number k of PF steps and one PI step as Modified Policy Iteration (MPI) (Puterman & Shin,
5

---

Published in Transactions on Machine Learning Research (04/2024)
1978; Scherrer et al., 2015). For & = MPI recovers Value Iteration, while for k - too, it recovers Policy Iteration. For any value of & E [1, +00, and under mild assumptions, MPT converges to an optimal policy (Puterman, 2014).
In Deep RL we parameterise a policy using a neural network with parameters set 0 and denote the distribution over action as (als, 0). We apply the same reasoning for value functions, with parameters set o, which leads to v(s, Φ) and g(s, a, 6) for the state and action value functions respectively.
4 Quantifying action influences
We start by answering Q1., which aims to address the problem of what to mcasure, when referring to credit. Since Minsky (1961) raised the Credit Assignment Problem (CAP), a multitude of works paraphrased his words:
The problem of how to incorporate knowledge" and "given an outcome, how relevant were past decisions?" (Harulyunyan et al., 2019),
"Is concerned with identifying the contribution of past actions observed future outcomes" (Aru- mugam et al., 2021),
"The problem of measuring on actions influence on future rewards" (Mesnard et al., 2021),
"An agent must assign credit or blame for the rewards it obtains to past states and actions" (Chelu et. al., 2022),
"The challenge of matching observed outcomes in the future to decisions made in the past" (Venuto ct al., 2022),
"Given an observed outcome, how much did previous actions contribute to its realization!"" (Ferret, 2022, Chapter 4.1).
These descriptions converge Minsky's original question and show agreement in the literature on an informal notion of credit. In this introduction, we propose to reflect the different metrics that exist in the literature to quantify it. We generalise the idea of action value, which often only refers to g-values, to that of action influence, which describes a broader range of metrics used to quantify the credit of an action. While we do not provide a definitive answer on what credit should be, we review how different works in the existing RL literature have characterised it. We now start by developing an intuition of the notion of credit.
Consider Figure 1, inspired to both Figure of Harutyunyan et al. (2019) and to the umbrella problem Osband et al. (2020). The action taken zo determines the return of the episode by itself. From the point of view of control, any policy that always takes d' in Zn (i.e., X' E II x (a'[zz) =), and then any other action afterwards, is an optimal policy. From the CAP point of view, some optimal actions, namely those after the first one, do not actually contribute to optimal returns. Indeed, alternative actions still produce optimal returns and contribute equally to each other to achieve the goal, so their credit is equal. We can see that, in addition to optimality, credit not only identifies optimal actions but informs them of how necessary they are to achieve an outcome of interest.
From the example, we can deduce that credit evaluates actions for their potential to influence an outcome. The resulting CAP is the problem of estimating the influence of an action over an outcome from exper- imental data and describes pure association between them.
Why solving the CAP? Action evaluation is a cornerstone of RL. In fact, solving control problem often involves running a GPI scheme. Here, the influence of an action drives learning, for it suggests a possible direction to improve the policy. For example, the action-value plays that role in Equation (3). It follows that the quality of the measure of influence fundamentally impacts the quality of the policy improvement. Low quality evaluations can lead the policy to diverge from the optimal one, hinder learning, and slow down progress (Sutton & Barto, 2018; van Hasselt et al., 2018). On the contrary, high quality evaluations provide accurate, robust. and reliable signals that foster convergence, sample-efficiency and low variance. While

---

Published in Transactions on Machine Learning Research (04/2024)
222
3z3
a
1i !!
"!
22
3z
AAA
F0
a"
Figure A simplified MDP to develop an intuition of credit. The agent starts in zo; and can choose between two actions, a' and a" in each state; the reward is when reaching the upper, solid red square, and otherwise. The first action determines the outcome alone.
simple evaluations are enough for specialised experiments, the real world is complex blend of multiple, sometimes hierarchical tasks. In these cases, the optimal value changes from one task to another, and these simple evaluations do not bode well to adapt to general problem solving. Yet, the causal structure that underlies the real word is shared among all tasks, and the modularity of its causal mechanisms is often a valuable property to incorporate. In these conditions, learning to assign credit in one environment becomes a lever to assign credit another (Ferret et al., 2021a), and ultimately makes learning faster, more accurate and more efficient. For these reasons, and because an optimal policy only requires discovering one single optimal trajectory, credit stores knowledge beyond that expressed by optimal behaviours alone, and solving the control problem is not sufficient to solve the CAP, with the former being an underspecification of the latter.
4.1 Are all action values, credit?
As we stated earlier, most Deep RL algorithms use some form of action influence to evaluate the impacts of an action on an outcome. This fundamental requirement rank actions and select the optimal one to solve complex tasks. For example, many model-free methods use the state-action value function q" (s, a) to evaluate actions (Mnih et al., 2015; Hasselt et al., 2016), where actions contribute much as the expected return they achieve at termination of the episode. Advantage Learning (AL) (Baird, 1999; Mnih et al., 2016; Wang et al., 2016b, Chapter 5) uses the advantage function (" az) q (s, a,) v (s:) to mcasure credit, whilc other works study the effects of the action-gap (Farahmand, 2011; Bellemare et al., 2016; Vieillard et al., 2020b) on it, that is, the relative difference between the expected return of the best action and that of another action, usually the second best.. Action influence also key ingredient of actor-critic and policy gradient methods (Lillicrap et al., 2015; Mnih et al., 2016; Wang et al., 2016a), where the policy gradient is proportional to [A" (s, a) log IT (A[s)), with A a) estimating the influence of the action A.
These proxies are sufficient to select optimal actions and unlock solutions to complex tasks (Silver et al., 2018; Wang et al., 2016b; Kapturowski et al., 2019; Badia et al., 2020; Ferret et al., 2021b). However, while many works explicitly refer to the action influence as a measure of credit, the term is not formally defined and, it remains unclear where draw the line between credit and other quantitics. Key questions arise: What is the difference belween these quantities and credit? Do they actually represent credil as originally formulated by Minsky (1961)? If so, under what conditions do they do? Without clear definition of what to measure, we do not have an appropriate quantity to target when designing an algorithm to solve the CAP. More importantly, we do not have an appropriate quantity to use as a single source of truth and term of reference to measure the accuracy of other metrics of action influence, and how well they approximate credit. To fill this gap, we proceed as follows:
Section 4.2 formaliscs what is a gool or outcome: what we evaluate the action for;
Section 4.3 unifies existing functions under common formalism;
TTo be consistent with the RI. literature we abuse notation and denote the advantage with a capital letter A despite not being random and being the same symbol of the action Aç.

---

Published in Transactions on Machine Learning Research (04/2024)
Section 4.4 formalises the CAP following this definition;
Section 4.5 analyses how different works interpreted and quantified action influences and reviews
lhem;
Section 4.6 distils the properties that existing measures of action influence exhibit.
We suggest the reader only interested in the final formalism to directly skip to Section 4.4, and to come back to the next sections to understand the motivation behind it.
4.2 What is goal?
Because credit measures the influence of an action upon achieving a certain goal, to define credit formally we must be able describe goals formally, and without clear understanding of what constitutes one, an agent cannot construct learning signal to evaluate its actions. Goal is synonym for purpose, which informally describe as performance to meet or a. prescription to follow. Defining goal rigorously allows making the relationship between the action and the goal explicit (Ferret, 2022, Chapter 4) and enables the agent to decompose complex behaviour into elementary ones in a compositional (Sution et al., 1999; Bacon et al., 2017), and possibly hierarchical way Berlia,, 2019; Pateria et al., 2021; Hafner et al., 2022). This idca at the foundation of many CA methods (Sutton al., 1999; 2011; Schaul et al., 2015a; Andrychowicz et al., 2017; Harutyunyan et al., 2019; Bacon et al., 2017: Smith et al., 2018; Riemer al., 2018; Bagaria & Konidaris, 2019; Harutyunyan et al., 2018; Klissarov & Precup, 2021). We proceed with formal definition of goals in the next paragraph, and review how these goals are represented in seminal works on CA in the one after. This will lay the foundation for unifying notion of credit later in Sections 4.3.
Defining goals. To define goals formally, we adopt the reward hypothesis, which posits:
That all of what mean by goals and purposes be well thought of mazimization of the expected value of the cumulative sum of a received scalar signal (reward). (Sutton, 2004).
Here, the goal is defined as the behaviour that results from the process of maximising the return. The reward hypothesis has been further advanced by later studies (Abel et al., 2021b; Pitis, 2019; Shakerinava & Ravanbakhsh, 2022; Bowling et al., 2023). In the following text, we employ the goal definition in Bowling et al. (2023), which we report hereafter:
Definition 1 (Goal). Given distribution of finite histories P(H), HH E H. define goal partial ordering over P(H), and for all h h' E H we write h 2 h to indicate that h is preferred to h' or that the bwo are indifferently preferred.
Here, H is random history in the set of all histories H. as described in Section 3, and P(H) is an unknown distribution over histories, different from that induced by the policy and the environment. An agent behaviour and an environment then induce a new distribution over histories, and we obtain P (H) as described in Section 3. This in turn allows defining a partial ordering over policies, rather than histories, and we write analogously 2 T' to indicate the preference. For the Markov Reward Theorem (Bowling et al., 2023, Theorem 4.1) and under mild conditions (Bowling al., 2023), there cxists deterministic, Markov reward function? R O x A + [0, 1] such that the maximisation of the expected sum of rewards is consistent with the preference relation over policies.
Subjective and objective goals. The Markov Reward Theorem holds both if the preferences are defined internally by the agent itself - this is the case of intrinsic motivation (Piaget et al., 1952; Chentanez et al., 2004; Barto et al., 2004; Singh et al., 2009; Barto, 2013; Colas et al., 2022) and in case they originate from an external entity, such as an agent-designas
In the first case, the agent doing the maximisation the
We omit the transition dependent discounting for the sake of conciseness and because not relevant to our problem. The reader can consult Pitis (2019); White (2017) for details.
8

---

Published in Transactions on Machine Learning Research (04/2024)
same the one holding the ordering over policies, and we refer to the corresponding goal as subjective gool. In the second case, an agent designer or unknown, non-observable entity holds the ordering and a separate learning agent is the one pursuing the optimisation process, We refer to goal as an objective gool in this latter case. These scttings usually correspond to the distinction between goals and sub-goals in the literature (Liu et al., 2022).
Outcomes. A particularly interesting use of goals for CA is in hindsight (Andrychowicz et al., 2017). Here the agent acts with a goal in mind, but it evaluates a trajectory as a reward function - one different from the original one was maximised in the current trajectory. We discuss the benefits of these methods in Section 6.4. When this is the case, we use the term outcome to indicate a realised goal in hindsight. In particular, given history H (H), there exists deterministic, Markov reward function R that is maximal in H. We refer to the corresponding H as outcome. For example, consider trajectory h that ends in certain stale There exist a Markov reward function that outputs always 0 and 1 only when the is the final state of h. We refer to h as an outcome.
In other words, this way of defining goals or outcomes corresponds to defining a task to solve, which in turn can be expressed through a reward function with the characteristics described above. Vice-versa, the reward function can encode a task. When credit is assigned with respect to a particular goal or outcome, it then evaluates the influence of an action to solving that particular task. As discussed above, this is key to decomposing and recomposing complex behaviours and the definition aligns with that of other disciplines, such as psychology where a gool .oml...is is a cognilive representation of something that is possible in the future (Elliot & Fryer, 2008) or philosophy, where representations do not merely read the world as it is, but they express preferences over something that is possible in the future (Hoffman, 2016; Prakash et al., 2021; Le Lan et al., 2022).
Representing goals and outcomes. However, expressing the relation between actions and goals explic- itly, that is, when the function that returns the credit of an action has a goal as an input, raises the problem of how to represent a goal for computational purposes. This is important because among the CA methods that define goals explicitly (Sutton et al., 2011; Schaul et al., 2015a; Andrychowiez et al., 2017; Rauber al., 2019; Harutyunyan et al., 2019; Tang & Kucukelbir, 2021; Arulkumaran et al., 2022; Chen et al., 2021), not many of them use the rigour of gencral-purpose definition of goal such as that in Bowling et al. (2023). In these works, the goul-representalioo space, which we denote as y E G, is arbitrarily chosen to represent specific features of a trajectory. It denotes an object, rather than a performance or prescription to meet. can be a state (Sutton et al., 2011; Andrychowicz et al., 2017) and
For example, a goal-representation E 9 = S. It can be a specific observation (Nair et al., 2018) with g E g = O. Alternatively, it can be an ract features vector (Mesnard et al., 2021) that reports on some characteristics of a history, and we have g E 9 = Rdd where d is the dimensionality of the vector. Even, goal can be represented by a natural language instruction (Luketina et al., 2019) and g G = Rd is the embedding of that piece of text. A goal can be represented by scalar g E G = IR. (Chen et al., 2021) that indicates a specific return to achieve, or even a full command (Schmidhuber, 2019), that is return to achieve is a specific window of time.
While these representations are all useful heuristics, they lack formal rigour and leave space for ambiguities. For example, saying that the goal is a state might mean that visiting the state at the end of the trajectory is the goal or that visiting it the middle of is the goal. This is often not formally defined, and what is the reward function that corresponds to that specific representation of goal is not always clear. In the following text, when surveying method or metric that specifies a goal, we refer to the specific goal representation used in the work and make effort to detail what is the reward function that underpins that goal representation.
4.3
What is an assignment?
Having established a formalism for goals and outcomes, we are now ready to describe credit formally and we proceed with a formalism that unifies the existing measures of action influence. We first describe a generic function that generalises most CAs, and then proceed to formalise the CAP. Overall, this formulation provides term of reference for the quantities described in Section 4.5. We now formalise an assignment:
9

---

Published in Transactions on Machine Learning Research (04/2024)
Definition 2 (Assignment). Consider on action E A, goal 9 9, and contert E C. We use the term assignment function or simply assignment to denote function K. that maps a context, an action, and on outcome to a quantity E y, which we refer to as the inftuence of the action:
K: K:CxAx
(4)
Here, a context c E C represents some input data and can be arbitrarily chosen depending on the assignment in question. For example, e can be a state 8. A context must hold information about the present, for example, the current state or the current observation; it may contain information about the past, for example, the sequence of past decisions that occurred until now for POMDP; to evaluate the current action, it can contain information about what future actions will be taken in in-potentia, for example by specifying policy to follow when a E A is not taken, or a fixed trajectory, in which case the current action is evaluated in hindsight (Andrychowicz et al., 2017).
In the general case, the action influence is a random variable Y E y C R This the case, for example, of the action-value distribution (Bellemare et al., 2017) as described in Equation 10, where the action influence is defined over the full distribution of returns. However, most methods extract some scalar measures of the full influence distribution, such expectations (Watkins, 1989), and the action influence becomes a scalar E R. In the following text, we mostly consider scalar forms of the influence y = R as these represent the majority of the existing formulations.
In practice, an assignment provides a single mathematical form to talk about the multitude of ways to quantify action influence that are used in the literature. takes an action a E A, some contextual data c E C and a goal g E and maps to some measure of action influence. While maintaining the same mathematical form, different assignments can return different values of action influence and steer the improvement in different directions.
Equation (4) also resembles the General Value Function (GVF) (Sutton et al., 2011), where the influence y (s, a, g) is the expected return of the policy π when taking action in state s, with respect a goal However, in GVFs: (i) y is an action value and does not generalise other forms of action inffuence; the goal is an MDP state g E S and does not generalise to our notion of goals in Section 4.2; the function only considers forward predictions and does not generalise to evaluating an action in hindsight (Andrychowicz et al., 2017). Table 2 at page 11 contains further details on the comparison and further specifies the relationship between the most common functions and their corresponding assignment.
4.4 The credit assignment problem
The generality of the assignment formalism reflects the great heterogeneity of action influence metrics, which we review later in Section 4.5. This heterogeneity shows that, even if most studies agree on an intuitive notion of credit, they diverge in practice on how to quantify credit mathematically. Having unified the existing assignments in the previous section, we now proceed to formalise the CAP analogously. This allows us to put the existing methods into a coherent perspective as guarantee for a fair comparison, and to maintain the heterogeneity of the existing measures of action influence.
We cast the CAP as the problem of approximating a measure of action influence from experience. We assume standard model-free, Deep RT settings and consider an assignment represented as a neural network : : C xxxx 9 x + > R with parameters & + R. that can be used to approximate the credit of the actions. This usually represents the critic or the value function of an RL algorithm. In addition, we admit stochastic function to represent the policy, also in the form of a neural network f : x θ A(A), with parameters set f E e Rm We assume that n < [S] x [A] and m < (S] x [A] and note that often subsets of parameters are shared among the two functions.
We further assume that the agent has access to a set experiences D and that it can sample from it according to a distribution D PD- This can be a pro-compiled set of external demonstrations, where (D( = U(D), or an MDP, where Pc (P,,(()) or even a fictitious model of an MDP Pc FF.. where f is function internal to the agent, of the same form of μ.. These are also mild assumptions as they
10

---

Published in Transactions on Machine Learning Research (04/2024)
Assignment
Action influence
Context
Action
Goal
State-action-value
q" (s.
s
E
g e
Advantage
(s) v(s)
s
E A
g e R
General q-value function
q (s,
8 S
E A
S
Distributional action-value
(=,s,a)
S 8
E A
{0, .
Distributional advantage
DKL (x
S S
E A
E { 72
Hindsight advantage
Po(As|st.7t) Zt
m(Aa)s))
8 S, ht E H.
E h
g IR
Counterfactual advantage
PD(A, = S = =, 8, f)((s,,
8 8 S
a E h
E R
Posterior value Policy-conditioned value
Ei Pur (U, uhle v (0r,
o 0 GEO.ERR
A A~1
E IR
a
s SES,TEII
a aEA
E R
Table 2: A list of the most common action influences and their assignment functions in the Deep RL literature analysed in this survey. For each function, the table specifies the influence, the context representation, the action, and the goal representation the corresponding assignment function E
correspond to, respectively, offline settings, online settings, and model-based settings where the model is Iearned. We detail these scttings in Appendix B. We now define the CAP formally.
Definition 3 (The credit assignment problem). Consider MDP M, goul G, and set of experience D. Consider arbilrary assignment K E K. as described in Equation (4). Given porameterised function K:Cx Ax + + R with parameters set ø E & C R", we refer to the Credit Assignment Problem the problem of Souding the set of paramelers & E & such that:
K(c,0,9.0) K(c,a,)) CcE
(5)
Different choices of action influence have great impact the hardness of the problem. In particular, there is trade-off between:
(a) how effective the chosen measure of influence is to inform the direction of the policy improvement,
(b) how easy it is to learn that function from experience.
For example, using causal influence (Janzing al., 2013) as a measure of action influence makes the CAP hard to solve in practice. In fact, discovering causal mechanisms from associations alone is notoriously challenging (Pearl, 2009; Bareinboim et al., 2022), and pure causal relationships rarely observed in nature (Pearl et al., 2000) but in specific experimental conditions. However, causal knowledge is reliable, robust to changes in the experience collected and effective, and causal mechanisms can be invariant to changes in the goal. On the contrary, q-values are easier to learn as they represent a measure of statistical correlation between state-actions and outcomes, but their knowledge is limited to the bare minimum necessary to solve control problem. This makes them more brittle to sudden changes the environment, for example, open-ended settings (Abel et al., 2023). Which quantity problem is still the subject of investigation in the literature, seek to use the most general measure of influence that can be learned with the least amount of experience.
in each specific instance each specific show in the next sections. Ideally, we
4.5 Existing assignment functions
We now survey the most important assignment functions from the literalure and their corresponding measure of action influence. The following list is not exhaustive, but rather is representative the limitations of existing credit formalisms. For brevity, and without loss of generality, we omit functions that do not explicitly evaluate actions (for example, stato-values,, but we notice that it is still possible to reinterpret an assignment to state assignment to set of actions for it affects all the actions that led to that state.
11

---

Published in Transactions on Machine Learning Research (04/2024)
Statc-action values (Shannon, 1950; Schultz, 1967; Michie, 1963; Watkins, 1989) are hallmark of RL, and are described by the following expression: EE,
[ =
s, 5, al.
(6)
Here, the context is a state S in the case of MDPs history h E H for a POMDP. The q-function quantifies the credit of an action by the expected return of the action in the context.
g-values are among the simplest ways to quantify credit and offer a basic mechanism to solve control prob- lems. However, while g-functions offer solid theorctical guarantoes in tabular RL, they can be unstable in Deep RL. When paired with bootstrapping and off-policy learning, q-values are well known to diverge from the optimal solution (Sutton & Barto, 2018). van Hasselt et al. (2018) provide empirical evidence of the phenomenon, investigating the relationship between divergence and performance, and how different variables affect divergence. In particular, the work shows that the Deep Q-Network (DQN) (Mnih et al., 2015) is not guaranteed to converge to the optimal q-function. The divergence rate on both evaluation and control prob- lems increases depending on specific mechanisms, such as the amount of bootstrapping, or the amount of prioritisation of updates (Schaul et al., 2015b).
An additional problem arises when employing GPT schemes to solve control problems. While during evalua- tion the policy is fixed, here the policy continuously changes. It becomes more challenging to track the target of the update while converging to it, the change of policy makes the problem appear non-stationary from the point of view of the value estimation. In fact, even if the policy changes, there is no signal that informs the policy evaluation about the change. To mitigate the issue, many methods either use a fixed network as an evaluation larget (Mnih et. al., 2015), perform Polyak averaging of the larget network (Haarnoja et al., 2018), or clip the gradient update to a maximum cap (Schulman et al., 2017). To further support the idea, theoretical and empirical evidence (Bellemare et al., 2016) shows that the q-function is inconsistent: for any suboptimal action a, the optimal value function q" (s, a) describes the value of non-stationary policy, which selects a different action n² (s) (rather than a) at each visit. of 8.
The non-stationarity of v-luus for suboptimal actions has also been shown empirically. Schaul et al. (2022) measure the per-state policy change W(, = EeEa [[als)) - ra(a)s) for several Atari 2600 games Arcade Learning Fnvironment. (ALE) (Bellemare et al., 2013), and show that the action-gap undergoes brutal changes despite the agent maintaining a constant value of expected returns.
In practice, Deep RL algorithms often use q-targets to approximate the value, for example, n-step targets (Sutton & Barto, 2018, Chapter 7), or X-returns (Watkins, 1989; Jaakkola et al., 1993; Sutton & Barto, 2018, Chapter 12). However, we consider them as methods, rather than quantitics to measure credit, since they all ultimately aim to converge to the g-value. For this reason, we discuss them in Section 6.1.
Advantage (Baird, 1999) measures, in a given state, the difference between the q-value of an action and the value of its state
(7)
Here, the context e is the same as in Equation (6). Because a (s) = EaEA ())(s) and AT a) g" (s(ss) a) - E, Ex (s, a)), the advantage quantifies how much an action is better than average.
=
As also shown in Bellemare et al. (2016), using the advantage to quantify credit can increase the action-gap. Empirical evidence has shown the consistent benefits of advantage over q-values (Baird, 1999; Wang et al., 2016b; Bellemare et al., 2016; Schulman et al., 2016), and the most likely hypothesis is its regularisation effects (Vieillard et al., 2020b;a; Ferret et al., 2021a). On the other hand, when estimated directly and not by composing state and state-action values, for example in Pan et al. (2022), the advantage does not permit bootstrapping. This is because advantage lacks an absolute measure of action influence, and only maintains one that is relative to the other possible actions.
Overall, canonical benchmarks for both evaluation (Wang et al., 2016b) and control (Bellemare et al., 2013), advantage has been shown to improve over g-values (Wang et al., 2016b). In particular, policy evaluation experiences faster convergence in large action spaces because the state-value (*()) can hold
12

---

Published in Transactions on Machine Learning Research (04/2024)
information that is shared between multiple actions. For control, it improves the score over several Atari 2600 games compared to both double q-learning (van Hasselt et al., 2016) and Prioritised Experience Replay (PER) (Schaul et al., 2015b).
General Value Functions (GVFs) (Sutton et al., 2011; Schaul et al., 2015a) are set of q-value functions that predict returns for multiple reward functions:
T
q nT (s. a) =E (s.
Σ A(S): = A, =a VR E R].
where R a rseudo-reward function and R is an arbitrary, pre-defined set of reward functions. Notice that we omit the pseudo-termination and pscudo-discounting terms that appear their original formulation (Sutton et al., 2011) to maintain the focus on credit assignment. The context is the same of q-values and S.
advantage, and the goal that the pseudo-reward represents is to reach specific state g
When first introduced (Sutton et al., 2011), the idea of GVFs stemmed from the observation that canonical value functions are limited to address only a single task at time. Solving a new task would require learning a value function er-novo. By maintaining multiple assignment functions at the same time, one for each goal, GVFs can instantly quantify the influence of an action for multiple goals simultaneously. However, while GVFs maintain multiple assignments, the goal is still not an explicit input of the value function. Instcad, it is left implicit, and each assignment serves the ultimale goal to maximise a different pseudo-reward function (Sutton et al., 2011).
Universal Value Functions Approximators (UVFAs) (Schaul et al., 2015a) scale GVFs to Deep RL and advance their idea further by conflating these multiple assignment functions into a single one, represented as a deep neural network. Here, unlike for state-action values and GVFs, the goal is an explicit input of the assignment:
(" = Rp A, a, G. =
(9)
The action influence here is mcasured for a goal explicitly. This allows to leverage the generalisation capacity of deep neural networks and to generalise not only over the space of states but also over that of goals.
Distributional values (Jaquette, 1973; Sobel, 1982; White, 1988; Bellemare et al., 2017) consider the full return distribution Z instead of its expected value:
(" = A. s.),=a),
(10)
where (Z,)
(Z+) is the distribution over returns. Notice that we use uppercase Q to denote the value distri- bution and the lowercase q for its expectation (Equation (6)).
To translate the idea into a practical algorithm, Bellemare et al. (2017) proposes a discretised version of the value distribution by projecting P.,,(2p on finite support C = {0 < S C). The discretised value distribution then becomes (*((saa) = Po(ZZ = s, Ar = a), where Pc is a categorical Bernoulli that describes the probability that a return c E is achieved. Here, the context is the current MDP state and the goal is the expected return. Notice that while the optimal expected value function q" (x, a) is unique, general, there are many optimal value distributions since different optimal policies can induce different value distributions.
Experimental evidence (Bellemare et al., 2017) suggests that distributional values provide better quantifi- cation of the action influence, leading to superior results in well known benchmarks for control (Bellemare et al., 2013). However, it is yet not clear why distributional values improve over their expected counterparts. One hypothesis is that predicting for multiple goals works as an auxiliary task (Jaderberg et al., 2017), which often leads to better performance. Another hypothesis is that the distributional Bellman optimality operator proposed in Bellemare et al. (2017) produces a smoother optimisation problem, but the evidence remains weak inconclusive (Sun et al., 2022).
13

---

Published in Transactions on Machine Learning Research (04/2024)
Distributional advantage (Arumugam et al., 2021) proposes a distributional equivalent of the advantage:
A"
= == Dxr. (s))
(11)
and borrows the properties of both distributional values and the expected advantage. Intuitively, Equa- tion (11) shows how much knowing the action changes the value distribution. To do so, it measures the change of the value distribution, for given state-action pair, relative to the distribution for the particular state only. The KL divergence between the two distributions can then be interpreted as the distributional analogue of Equation (7), where the two quantities appear in their expectalion instead. The biggest draw- back of this measure of action influence that it is only treated in theory, and there is no empirical evidence that supports distributional advantage as a useful proxy for credit in practice. Future works should consider providing empirical evidence on how this measure of action influence behaves compared to q-values and distributional values.
Hindsight advantage (Haruty yunyan et al., 2019) stems from conditioning the action influence on future states or returns. The return- condition hindsight advantage function can be written as follows:
a a (1--)))=1111))1
PA(A: = alS. -a|A==||.--- =) =))
AT (" a, = (=) P (A.
s, -..
(12)
Here a=) denotes the return- return-conditional advantage and (a = s, Z. = 2) is the return- conditional hindsight distribution and describes the probability that an action a has been taken in 8, given that we observed the return = at the end of the episode, after following т. The conlext is a state, and the goal is the expected return, which, in this case, corresponds also to the value of the return collected in the current trajectory.
The idea of hindsight - initially presented in Andrychowiez et al. (2017) - is that even if the trajectory does not provide useful information for the main goal, it can be revisited as if the goal was the outcome just achieved. Hindsight advantage brings this idea to the extreme and rather than evaluating only for a pre-defined set of goals such as in Andrychowicz et al. (2017), it evaluates for every experienced state or return. Here, the action influence is quantified by that proportion of return determined by the ratio in Equation (12). To develop an intuition of it, if the action a Icads to the return & with probability > 0 such that P Fn,x(A, = a.S. 8, Z, 2) > 0, but the behaviour policy takes a with probability 0, the credit of the action is 0. There exists also state-conditional formulation rather than a cetunncondditonall one, and we refer to Harutyunyan et al. (2019) for details on it to keep the description concisc.
Future-conditional advantage (Mesnard et al., 2021) generalises hindsight advantage to use an arbitrary property of the future:
(s. a, = -) aA =,
F. = (s,
(13)
Here, F: - R is an n-dimensional feature of trajectory d, and F; is that feature for trajectory that starts at lime L and ends at the random horizon T. q" (s,a, = [ 8, F. = ʃ. A. = a) denotes the future-conding conditiondd state-action value function. The context is tuple of state and feature (s, f); the goal is the expected return observed at the end of the trajectory. Notice that you can derive the hindsight advantage by setting F= = Z.
To develop an intuition, F can represent, for example, whether a day is rainy, and the future-conditional advantage expresses the probability of an action a, given that the day will be rainy.
Counterfactual advantage (Mesnard et al., 2021) proposes specific choice of F such that F is inde- pendent of the current action. This produces future-conditional advantage that factorises the influcnce of an action in two components: the contribution deriving from the intervention itself (the action) and the luck represented by all the components not under the control of the agent at the time t, such as fortuitous outcomes of the stato-transition dynamics, exogenous reward noise, or future actions. The form is the same as that in Equation 13, with the additional condition that the feature F, is independent of the action A, and we have [p( (PP S. s),|P(A,|S: = 8, F, f) = 0.
14

---

Published in Transactions on Machine Learning Research (04/2024)
The main intuition behind counterfactual advantage is the following. While to compute counterfactuals we need access to model of the environment, in model-free settings we can still compute all the relevant information Ft that does not depend on this model. Once learned, a model of F can then represent a valid baseline to compute counterfactuals in a model-free way. To stay in the scope of this section, we detail how to learn this quantity in Section 6.4.
Posterior value functions (Nota al., 2021) reflect on partial-observabliiyy and propose a character- isation of the hindsight, advantage bespoke to POMDPs. The intuition behind Posterior Value Funetions (PVFs) is that the evaluated action only accounts for small portion of the variance of returns. The majority of the variance is often due to the part of the trajectory that still has to happen. For this reason, incorpo- rating in the baseline information of the future could have a greater impact in reducing the variance of the policy gradient estimator. PVFs focus on the variance of a future-conditional baseline (Mesnard et al., 2021) caused by the partial observability. Nota et al. (2021) factorises a state s into an observable component o and an non-observable one u, and formalises the PVF as follows:
(he)
Σ PM (uln(()))))"""" ul/t)) uEU
ue),
(14)
where u E U is the non-observable component of st such that s o3, Notice that this method is not taking into account actions. However, it is trivial to derive the corresponding Posterior Oetion-Valur Function (PAVF) as (h( a) R(st, a.) + y0 (h(+1).
Poliey-conditooned values (Harb et al., 2020; Faccio et al., 2021) are value functions that include the policy as an imput. For example, a ponicy-conditioned state-action value has the form:
(ss, a, = q²((s,).
(15)
but representation of the policy π is used as explicit input of the influence function. Here, the context is the union of the current MDP state s and the policy n, and the goal is the expected return at termination.
The main difference with state-action values is that, all clse being equal, ((s, n, g) produces diffcrent values inslantly when æ varies, since π is now an explicit input. For this reason, q(8, v,a) can generalise over the space of policies, while q" a) cannot. Using the policy as an input raises the problem of representing a policy in a way that can be fed to a neural network. Harb al. (2020) and Faccio al. (2021) propose two methods to represent policy. To keep our attention the CAP, possible ways to represent a policy (Harb et al., 2020; Faccio et al., 2021). Here we limit to convey that the problem of representing policy has been already raised in the literature.
refer to their works for further details
4.6 Discussion
The sheer variety of assignment functions described above leads to equally broad range of metrics to quantify action influence and what is the best assignment function for a specific problem remains an open question. While we do not provide a definitive answer to the question of which properties are necessary or sufficient for an assignment function to output a satisfactory measure of crodit, we set out to draw attention to the problem by abstracting out some the properties that the metrics above share or lack. We identify the following properties of an assignment function and summarise our analysis in Table 3.
Explicitness. We use the term explicilness when the goal appears as an explicit input of the assignment and it is not left implicit inferred from experience. Using the goal an input allows generalising CA over the space of goals. The decision problem can then more casily be broken down into subroutines that are both independent of each other and independently useful to achieve some superior goal
Overall, explicitness allows incorporating more knowledge because the assignment spans each goal without losing information about others, only limited by the capacity of the function approximator. For example, UVFAs, hindsight advantages, and future conditional advantages are explicit assignments. As discussed in the previous section, distributional values can also be interpreted as explicitly assigning credit for each atom
15

---

Published in Transactions on Machine Learning Research (04/2024)
Name
Explicitness
Recursivity
Future-dependent
Causality
State-action value
Advantage
GVFs/UVFAs
Distributional action-value
Distributional advantage
0
Hindsight advantage
Counterfactual advantage
Posterior value
Observation-action value
Policy-conditioned value
Table 3: A list of the most common aclion influences and their assignment functions in the Deep RL literature analysed in this survey, and the properties they respect. Respectively, empty circles, half circles and bullets indicate that the property is not respected, that it is only partially respected, and it is fully respected. See Sections 4.5 and 4.6 for details.
of the quantised return distribution, which is why we only partially consider them having this property Table 3. Likewise, hindsight. and future-conditional advantage, while not conditioning on goal explicitly, can be interpreted conditioning the influence on sub-goals that are states or returns, and future statistics, respectively. For this reason, we consider them as partially explicit assignments.
Recursivity. We use the term recursivity characterise the ability of an assignment function support bootstrapping (Sutton & Barto, 2018). When assignment is recursive, it respects relationship of the type: ((C441,441.9)) = ((((s, g),g),, [(K),,,,)))))
where ff projects the influence from the time t to ++1. 1. For example, goal-conditioned g-values can be written as: is the reward function for the goal g.
(++1,g) = R(st, at, g) +7 (&t, (e,9), where R(8t, ae.
Recursivity provides key advantages when learning credit, which we discuss more in detail in Section In theory, reduces the variance of the estimation at the cost of bias (Sutton & Barto, 2018): since the agent does not complete the trajectory, the return it observes is imprecise but varies less. In practice, bootstrapping is often necessary in Deep RL when the length of the episode for certain environments makes full Monte-Carlo estimations intractable due to computational and memory constraints.
When the inffuence function does not support bootstrapping, the agent must obtaín complete episodes to have unbiased samples of the return. For example, Direct Advantage Estimation (DAE) (Pan et al., 2022) uses the advantage function as a measure of credit, but it does not decompose the advantage into its recursive components that support bootstrapping (q(s, a) and v(s)), and requires full Monto- Carlo returns to approximate it. This is often ill-advised it increases the variance of the estimate of the return. For this reason, we consider the advantage to only partially satisfy recursivity.
Future-dependent. We use the term inture-dependent for assignments that take as input information about what actions will be or have been taken after the time t at which the action A, is evaluated. This is key because the influence of the current action depends also on what happens after the action. For example, picking up key is not meaningful the policy does not lead to opening the door afterwards.
Future actions can be specified in-poteniio, for example, by specifying policy to follow after the action. This is the case of condiiocon value function, whose benefit is to explicitly condition on the policy such that, if the policy changes, but the action remains the same, the influence of the action changes instantly. They can also be specified in realisation. This is the case, for example, of hindsight evaluations (Andrychowicz et al., 2017) such as the hindsight advantage, the counterfactual advantage, and the PVF where the influence is conditioned on some features of the future trajectory.
However, these functions only consider features of the future: the hindsight advantage considers only the final state or the final return of trajectory; the counterfactual advantage considers some action-independent
16

---

Published in Transactions on Machine Learning Research (04/2024)
features of the future; the posterior value function considers only the non-observable components. Because futures are not considered fully, we consider these functions as only partially specifying the future.
Furthermore, while state-action value functions, the advantage and their distributional counterparts specify a policy in principle, that information is not an explicit input of the assignment, but only left implicit. In practice, in Deep RI, if the policy changes, the output of these assignments does not change unless retraining.
Causality. We refer to a causal assignment when the influence that it produces is also a measure of causal inffuence (Janzing et al., 2013). For example, the countorfactual advantage proposes an interpretation of the action influence closer to causality, by lactorising the influence of an action in two. The first factor includes only the non-controllable components of the trajectory (e.g., exogenous reward noise, stochasticity of the state-transition dynamics, stochasticity in the observation kernel), those not under direct control of the agent at time t, such future actions. The second factor includes only the effects of the action alone. The interpretation is that, while the latter is due to causation, the former is only due to fortuitous correlations. This vicinity to causality theory exists despite the counterfactual advantage not being a satisfactory measure of causal influence as described in Janzing et al. (2013). Distributional advantage in Equation 11 can also be interpreted as containing elements of causality, In fact, we have that the expectation of the advantage over states and actions is the Conditional Mutual Information (CMI) between the policy and the return, conditioned on the state-transition dynamics: E,, (Q" (s)))))(""s)) = I[Is = s); (8)). The CMI (with its limitations (Janzing et al., 2013)) is known measure of causal inftuence.
Overall, these properties define some characteristics of an assignment, each one bringing positive and negative aspects. Explicitness allows maintaining the influence of an action for multiple goals at the same time, promoting the reuse of information and a compositional onset of behaviour. Recursivity ensures that the influence can be learned via bootstrapping. Future-dependency separates assignments by whether they include information about future actions. Finally, causality filters out the spurious correlations evaluating the effects of the action alone.
4.7 Summary
In this section, we addressed Q1. and discussed the problem of how to quantify action influences. In Section 4.1 we formalised our question: "How do different works quantify action influences and "Are these quantities satisfactory measures of credit?". We proceeded to answer the questions. In Section 4.2 we formalised the concept of outcome as some arbitrary function of a given history. In Section 4.3 we defined the assignment function as a function that returns a measure of action influence, In Section 4.4 we used this definition to formalise the CAP as the problem of learning a measure of action influence from experience. We refer to the set of protocols of this learning process as credit assignment method. In Section 4.5 we surveyed existing mcasures of action influence from literature, detailed the intuition behind them, their advantages and drawbacks. Finally, in Section 4.6 we discussed how these measures of action influence relate to each other, the properties that they share and those that are rarer in literature, but still promising for future advancements. In the next sections, we proceed to address Q2. Section 5 describes the obstacles to solving the CAP and Section 6 surveys the methods to solve the CAP.
5 The challenges to assign credit in Deep RL
Having clarified what measures of action influence are available in the literature, we now look at the obstacles that arise to learn them and, logether with Section 6, answer Q2.. We first survey the literature to identify known issues to assign credit and then systematise the relevant issues into CA challenges. These challenges provide a perspective to understand the principal directions of development of CA methods and are largely independent of the choice of action influence. However, using a measure of influence over another can still impact the prominence of each challenge.
We identify the following issues to assign credit: (a) delayed rewards (Raposo et al., 2021; Hung et al., 2019; Arjona-Medina et al., 2019; Chelu et al., 2022): reward collection happens long after the action that determined it, causing its influence to be perceived as faint; (b) sparse rewards (Arjona-Medina Medina al., 2019;
17

---

Published in Transactions on Machine Learning Research (04/2024)
(a) Depth of the MDP.
(b) Density of the MDP.
(c) Breadth of the MDP.
Figure 2: Visual intuition of the three challenges to temporal CA and their respective set of solutions, using the graph analogy. Nodes and arrows represent, respectively, MDP states and actions. Blue nodes and arrows denote the current episode. Black ones show states that could have potentially been visited, but have not. Square nodes denote goals. Forward arrows (pointing right) represent environment interactions, whereas backward arrows (pointing left) denote credit propagation via state-action back-ups. From top left: (a) the temporal distance between the accountable action and the target state requires propagating credit deep back in time; (b) considering any state as target increases the density of possible associations and reduces information sparsity; and finally, (c) the breadth of possible pathways leading to the target state.
Seo et al., 2019; Chen & Lin, 2020; Chelu al., 2022): the reward function is everywhere, and rarely spikes, causing uninformative Temporal Difference (TD) errors; (c) partial observability (Harutyunyan et al., 2019): where the agent does not hold perfect information about the current state; (d) high variance (Harutyunyan et al., 2019; Mesnard et al., 2021; van Hasselt et al., 2021) of the optimisation process; (e) the resort to time as a hcuristic to determine the crodit of an action (Harutyunyan et al., 2019; Raposo et al., 2021): (f) the lack counterfactual CA (Harutyunyan et al., 2019; Foerster et al., 2018; Mesnard et al., 2021; Buesing al., 2019; van Hasselt al., 2021): (g) slow convergence AArjna-Mediin
al., 2019).
While these issues all very relevant to the CAP, their classification is also tailored to control problems. Some of these are described by the use of particular solution, such as (e), the lack thereof, like (l), rather than by characteristic of the decision or of the optimisation problem. Here, we systematise these issues and transfer them to the CAP. We identify three principal characteristics of MDPs, which we refer to as dimensions of the MDP: depth, density and breadth (see Figure 2). Challenges to CA emerge when pathological conditions on depth, density, and breadth produce specific phenomena that mask the learning signal be unreliable, inaccurate, insufficient correctly reinforce an action. We now detail these three dimensions and the corresponding challenges that arise.
5.1 Delayed effects due to high MDP depth
We refer to the depth of an MDP as the number of temporal steps that intervene between a highly influential action and an outcome (Ni et al., 2023). When this happens, we refer to the action as a remote action, and the outcome as a delayed outcome. When outcomes are delayed, the increase of temporal distance often corresponds combinatorial increase of possible alternative futures and the paths to get them. In these conditions, recognising which action responsible for the outcome is harder, since the space of
18

---

Published in Transactions on Machine Learning Research (04/2024)
possible associations is very large. We identify two main reasons for outcome to be delayed, depending on whether the decision after the remote action influences the outcome not.
The first reason for delayed effects is that the success of the action is not immediate but requires a sequence of actions to be performed afterwards, which causes the causal chain leading to success to be long. This issue originates from the typical hierarchical structure of many MDPs, where the agent must first perform a sequence of actions to reach a subjective sub-goal, and then perform another sequence to reach another. The key-to-door task (Hung et al., 2019) is good example of this phenomenon, where the agent must first collect key, to be able to open door later.
The second reason is delayed reinforcements: outcomes are only observed after long time horizon, and any decision laken after the remote action does not influence the outcome significantly. The phenomenon was first noted in behavioural psychology and is known as the delayed reinforcement problem (Lattal, 2010),
Reinforcement is delayed whenever there a period of time between the response producing the reinforcer and ils subsequend delivery. (Lattal, 2010)
The main challenge with delayed reinforcements is in being able to ignore the series of irrelevant decisions that are encountered between the remote action and the delayed outcome, focus on the actions that are responsible for the outcome, and assign credit accordingly. This is a key requirement because most CA methods rely on temporal recency as a heuristic to assign credit (Klopf, 1972; Sutton, 1988; Mahmood et al., 2015; Sutton et al., 2016; Jiang et al., 2021a). When this is the case, the actions in the proximity of achieving the goal are reinforced, even not actually being responsible for the outcome (only the remote action is), just because they are temporally close to the outcome.
While recent works advance proposals on how to measure the MDP depth, for example, CA length (Ni ct al., 2023), there is currently no formal agreement in the literature on how to diagnose the presence of delayed effects.
5.2 Low action influence due to low MDP density
If delayed effects are characterised by a large temporal distance between an action and the outcome, MDP sparsity derives from a lack of influence between them. Even if the literature often confounds sparse and delayed rewards, there a substantial difference between them. With delayed effects, actions can cause outcomes very frequently, except with delay. Here, actions have little or no impact on the outcome, and outcomes do not vary regardless of the actions laken, but in few, rare instances. We identify two main reasons.
The first one is highly stochastic stato-transition dynamics, which can be diagnosed by measuring the entropy of the slate-transition distribution H(P,,) and/or of the reward function H()())). In highly stochastic MDPs, actions hardly affect the future states of the trajectory, the agent is unable to make predictions with high confidence, and therefore cannot select actions that are likely to lead to the goal.
The second reason is the low goal density. This is the canonical case of reward sparsity in RL, where the goal is only achievable in small subset of the state space, for a specific sequence of actions. Formally, can measure the sparsity of an MDP using the notion of information sparsity (Arumugam et al., 2021).
Definition 4 (MDP sparsity). An MDP is e e-information sparse if:
max
(DE u.a (Z)s, P xell (Z]s)) (Z SE,
(16)
where E,,, denotes the expectation over the stationary distribution induced by the policy and the state- transition dynamics. The information sparsity of an MDP is the maximum information gain that can be obtained by an agent. When this is low everywhere, and only concentrated in a small subset of decisions, CA methods often struggle to assign credit, because the probability of behaving optimally is lower (Abel et al., 2021a), and there is rarely a signal to propagate.
19

---

Published in Transactions on Machine Learning Research (04/2024)
5.3 Low action influence due to high MDP breadth
We use the lerm breadth of an MDP to denote the number of alternative histories h that produce the same outcome g. We then use the term dilution of credit, when many optimal pathways exist, and there is no bottleneck decision that the agent has to necessarily make to achieve the goal. We formalise the concept using the notion of the null space of a policy (Schaul et al., 2022):
NT)l(T) == (9]o=(s) oz' (8)) (5)) n' N' EI.
(17)
(u)l(z) is the null space of a policy defined to be the subset of the space of all policies 52 C II such that two policies n, E Ω have the same expected state-value v² (s) - vz (8) in all the states of the MDP 8 E S.
Credit dilution is often not a challenge for control because optimal behaviours are more probable. However, it can be problematic for CA. Most of the common basclincs, such as Advantage Actor Critic (A2C) (Mnih et al., 2016) or Proximal Policy Optimisation (PPO) (Schulman el al., 2017), stop exploring after a small subset of optimal histories is found (or after a certain amount of time). Indeed, when diam(Null(z")) is large, there are many optimal historics. Yet, most of them are not included in the experience set C since exploration stopped prematurely, and credit will not be improved for those. This is particularly relevant for assignments that, measure the influence of an action relative to another. For example, the advantage (T = q=(s, a)- - En' [g" (s" is inaccurate if (s, is inaccurate, which requires taccurately ovaluating q. Va' E A. This often results in a low diversity of behaviours (Parker-Holder et al., 2020), and a poor robustness to changes in the environment (Eysenbach & Levine, 2022).
5.4 Relationship with the exploration problem
One additional challenge in practical experiments that it is often hard to disentangle the impacts of CA from those of exploration. In fact, discerning the effects of the two is often only done qualitatively. Here, we discuss the connection between the two problems, if they can be studied independently, and whether it is possible to find way to diagnose and separate the effect of one from the other.
We use the interpretation of exploration as the problem of acting in an unknown environment to discover lemporal sequences of slates, actions and rewards with the purpose of acquiring new information (Amin et al., 2021; Jiang et al., 2023). The acquired experiences then become part of the experience set C, which is used to solve the CAP as described in Equation (5).
To visualise the difference between the exploration problem and the CAP, consider the usual key-to-door environment, where the agent needs to pick up key, which opens door, behind which lies a reward. While highly improbable (Abel et al., 2021a), this successful event is the result of chance and random behaviour". Nevertheless, it is the responsibility of exploration to discover for the first time an optimal history, and to keep feeding the set C with useful discoveries. Then, once the successful experience C* is in the set C, it becomes the responsibility of the CA method to consume that experience and extract a measure of influence from the relationship context-action-outonn
(Equation (4)) that supports effective improvements.
This is key difference because the very same behaviour has a different cause whether it comes from exploration from CA. If due to exploration, it happens by chance, making it unlikely to occur again. If due to accurate CA, it is the result of informed decision-making, and funded on the ability to forecast (Sutton et al., 2011) the effects of an action. Then, when assignments start to be accurate enough, policy improvement further increases the probability of visiting optimal trajectorics in a virtuous cycle that also improves CA. Many studies show how common RL baselines often struggle to extract a reliable signal from a small set of isolated successes. This is the case, for example, of A2C (Oh et al., 2018), DQN (Schaul et al., 2015b) or PPO (Arjona-Medina et al., 2019). To further support the claim, increasing the sampling probability of a success, for example through PER (Schaul al., 2015b) or Self-Imitation Learning (SIL) (Oh et al., 2018), shows great improvements in CA.
We can draw two conclusions from the arguments above. On one hand, if there is a minimum number of optimal trajectories C c C in C, exploration has done its job and failures can be attributed to poor CA. On
OOr, rather, by the laws dictated by the exploration algorithm.
20

---

Published in Transactions on Machine Learning Research (04/2024)
the other hand, natural question arises: "What is the minimum rate of successes Gmin |c*1 that CA method requires to slarl converging to an optimal policy?". This is fundamental open question in the current literature, and an answer to it can produce valid tool to evaluate a CA method. All else being equal, the lowest the ratio C²/C /C, the better the method, because it requires exploration to randomly collect optimal histories at a lower rate, and can solve harder MDPs (Abel et al., 2021a).
5.5 Summary
In this section, we surveyed the literature and discussed both the obstacles and the current, limitations to solving the CAP. These include delayed rewards, sparse rewards, partial observability, high variance, the lack of counterfactual CA,, and sample efficiency. Then, we systematisod these issues into challenges that emerge from specific properties of the decision problem, which we refer to as dimensions of the MDP: depth, density, and breadth. Challenges emerge when pathological conditions these dimensions produce specific phenomena that mask the learning signal to be unreliable, inaccurate, insufficient to correctly reinforce an action: delayed effects, sparsity, and credit dilution. We have provided an intuition of this classification with the aid of graphs and proceeded to detail each challenge. Finally, we discussed the connection ween the CAP and the exploration problem, suggesting a way to diagnosc when a failure caused by one or the other, and disentangling exploration from CA.
With these challenges in mind, we now proceed to review the state of the art in CA, and discuss the methods that have been proposed to address them.
6 Methods to assign credit in Deep RL
Following the definition of CAP in Section 4.4, a credit assignment method is then algorithm that takes initial guess K K and finite set of experience D = (8 x A R)T, and, by sampling and learning from transitions D ~ PD*, it recursively produces a better approximation of the true assignment K.
In this section, we present a list. of the credit assignment hods focused on Deep RL. Our classification aims to identify the principal directions of development and to minimise the intersection between each class of methods. We aim to understand the density around each set of approaches, to locate the branches suggesting the most promising results, and to draw trend of the latest findings. This can be helpful to both the researchers the CAP who want to have bigger picture of the current state of the art, to general RL practitioners and research engineers to identify the most suitable methods to use in their applications, and to the part of the scientific community that focuses on different problems, but that can benefit from the insights on CA. We define a CA method according to how it specifies three elements:
(a) The measure of action influence via the assignment function K.
(b) The protocol that the method uses to approximate K from the experience D.
(c) The mechanism Pp(d) to collect and sample from d E D.
This provides consistency with the framework just proposed and allows categorising cach method by the mechanisms that it uses to assign credit. Therefore, for each method, we report the three elements described above. We identify the following categories:
1. Methods using time contiguity heuristic (Section 6.1).
2. Those decomposing returns into per-timestey utilities (Section 6.2).
3. Those conditioning on predefined goals explicitly (Section 6.3).
Methods conditioning the present on future outcomes in hindsight (Section 6.4).
"To enhance the flow of the mamuscript, we formalise contentual distributions Appendix and since they are intuitive concepts, we describe them words when surveying the methods.
21

---

Published in Transactions on Machine Learning Research (04/2024)
5. Modelling trajectories sequences (Section 6.5).
6. Those planning or learning backwards from an outcome (Section 6.6).
Meta-learning different proxies for credit (Section 6.7).
Note that, we do not claim that this list of methods is exhaustive. Rather, as in Section 4.5, this taxonomy is representative of the main approaches and a tool to understand the current state of the art in the field. We are keen to reccive foodback on missing methods from the list to improve further revisions of the manuscript. We now proceed describe the methods, which we also summarise Table 4.
Publication
Method
Class
Depth
Density
Breadth
Baird (1999)
AL
Time
Wang et al. (2016b)
DDQN
Time
Pan et al. (2022)
DAE
Time
Klopf (1972)
ET
Time
Sulton et al. (2016)
ETD
Time
Bacon et al. (2017)
Option-critic
Time
Hung et al. (2019)
TVT
Return decomposition
Arjona-Ment Medinaa al. (2019)
RUDDER
Return decomposition
Ferret et al. (2021a)
SECRET
Return decomposition
Ren et al. (2022)
RRD
Return decomposition
Raposo et al. (2021)
SR
Return decomposition
Sutton et al. (2011)
GVF
Auxiliary goals
0
Schaul et al. (2015a)
UVFA
Auxiliary goals
0
Andrychowicz et al. (2017)
HER
Future-condittoning
Rauber et al. (2019)
HPG
Future-conditioning
Harutyunyan al. (2019)
HCA
Future-conditioning
Schmidhuber (2019)
UDRL
Future-conditioning
Mesnard et al. (2021)
CCA
Future-conditioning
Nota et al. (2021)
PPG
Future-conditioning
Janner et al. (2021)
TT
Sequence modelling
Chen et al. (2021)
DT
Sequence modelling
Goyal et al. (2019)
Recall traces
Backward planning
Edwards et al. (2018)
FBRL
Backward planning
Nair al. (2020)
TRASS
Backward planning
van Hasselt al. (2021)
ET(A)
Learning predecessors
Xu al. (2018)
MG
Meta-Learning
Yin al. (2023)
Distr. MG
Meta-Learning
Table 4: List of the representative algorithms for CA classified by the CA challenge they aim address. For each method, report the publication that proposed it, the class assigned to it, and whether it is designed to address each challenge described in Section 5. Hollow circles mean that the method does not address the challenge, and the full circle represents the opposite.
6.1 Time as a heuristic
One common way to assign credit is to use time contiguity as proxy for causality: an action is as influential as it temporally close to the outcome. This means that, regardless of the action being an actual cause of the outcome, if the action and the outcome appear temporally close in the same trajectory, the action is assigned high credit. At their foundation, there is TD learning (Sutton, 1988), which describe below.
TD learning (Sutton, 1984: 1988: Sutton & Barto, 2018) iteratively updates an initial guess of the value function according to the difference wetween expected and observed outcomes. More specifically, the agent
22

---

Published in Transactions on Machine Learning Research (04/2024)
starts with an initial guess of values, acts in the environment, observes returns, and aligns the current guess to the observed return. The difference between the expected return and the observed one is the TD error dy:
6, R(st, az) + 79" (st+1, a+-1) - q" (st,
(18)
with 0+41 ~ x and 81+1 ~ j..
When the temporal distance between the goal and the action is high a premise at the base of the CAP it is often improbable to observe very far rewards. As time grows, so does the variance of the observed outcome; due to the intrinsic stochasticity of the environment dynamics, and the policy. To mitigate the issue, TD methods often replace the theoretical measure of influence with approximation: the TD target. In TD learning, the value function is updated to approximale the largel, and not the theoretical measure of action influence underneath it. Since policy improvement uses the current approximation of the value to update the policy, future behaviours are shaped according to it, and the TD target drives the learning process.
We separate the methods in this category in three subgroups: those specifically designed around the ad- vantage function, those ro-weighing updates to stabilise learning, and those assigning credit to subsets of temporally exlended courses of actions.
6.1.1 Advantage-based approaches
The first subset of methods uses the advantage (sce Section 4.5) as a measure of action influence, but still uses time as heuristic to learn it.
Actor-Critic (AC) methods with a baseline function (Sutton & Barto, 2018, Chapter 13) approximate the action influence using some estimator of the advantage function (Equation 7). In fact, the policy gradient is proportional to Fu,i(("* (s,a) b(s) log (a]s)] and if we choose v" (s) as our baseline b(s), we get Ep.-((AT(ss (s, a)) Vog T [a]ss]] because q (s, (s, = as, The use of an action-indeppndeen baseline function usually helps to reduce the variance of the evaluation, and thus of the policy gradients, while maintaining an unbiased estimate of it (Sutton & Barto, 2018). What function to use as a baseline is the subject of major studies, and different choices of baselines often yield methods that go beyond using time as a heuristic (Harutyunyan et al., 2019; Mesnard et al., 2021; Nota et al., 2021; Mesnard et al., 2023).
Advantage Learning (AL) Baird (1999) also uses time as proxy for causality. There are many instances of AL in the Deep RL literature. The Ducling Deep Q-Network (DDQN) (Wang et al., 2016b) improves on DQN by calculating the q-value as the sum between the state-value function and a normalised version of the advantage. Even if this results in using the q-value as a measure of action influence and K(s,a) oz (s) + (s) E. AT (s,a')) l'),,)),, approximating the advantage is a necessary step of it.
DAE (Pan al., 2022) follows Wang et al. (2016b) with the same specification of the advantage but provides better connections between the advantage and causality theory. In particular, for fully observable MDPs, the causal effect of an action upon a scalar outcome G is defined as [[G]ss, (assaaa-[[c E[]]s] If we choose the return Z as outcome, this actually corresponds to the advantage B[Z]s, a] - E[ = 9dd (s. Q) - v (s), which becomes an approximate expression for the causal influence of an action upon the random return, as discussed also in Arumugam et al. (2021). Here, the context is an MDP state, the action is the greedy action with respect to the current advantage estimation, and the goal is the expected return at lermination.
As explained in Section 5.3, advantage can be decomposed in two terms AT a) (=) - (s, Since v (s) Ez[g" (s, a)), it is clear that the accuracy of the advantage depends on the accuracy of the g-values of all actions. It has been shown that, because of this, estimating and incorporating the advantage in the vavalue has a regularisation effect (Vieillard et al., 2020a). Another effect is increasing the action-gap (i.e. the difference in value between the best and second-best action), which facilitates value learning. Because evaluations are more accurate for a greater portion of the state-action space, AL-based methods contribute to address MDP breadth, as shown in Table 4.
23

---

Published in Transactions on Machine Learning Research (04/2024)
6.1.2 Re-weighing updates and compound targets
The second subset of methods in this category re-weighs temporal updates according to some houristios, which we detail below. Re-weighing updates can be useful to emphasise or de-emphasise important states or actions to stabilise learning in Deep RL (van Hasselt al., 2018).
Eligibility Traces (ET) (Klopf, 1972; Singh & Sutton, 1996; Precup, 2000a; Geist et al., 2014; Mousavi et al., 2017) credit the long-term impact of actions on future rewards by keeping track of the influence of past actions the agent's future reward. Specifically, an eligibility trace (Sutton & Barto, 2018, Chapter 12) is a function that assigns weight to each stale-action pair, based on the recency of the last visit to it. A trace (s) spikes every time state (or state-action) is visited and decays exponentially over time until the next visit or until it extinguishes. At each update, the TD error, which determines the magnitude of the update, is scaled by the value of the trace at that state, and 8. = 6jer(s). There are several types of cligibility traces, depending on the law of decay of the trace. For example, with accumulating traces (Klopf, 1972), every visit causes an increment of the trace. Replacing traces (Singh & Sutton, 1996) are capped to a specific value, instead.
Deep Q(A)-Networks (DQ(A)Ns) (Mousavi et al., 2017) implement cligibility traces on top of DQN (Mnih et al., 2015). Here, the eligibility trace is a vector e E Rd with the same number of components d as the parameters of the DNN, and the action influence is measured by the q-value with parameters set 0 E IRd. The context is an MDP state, the action is an off-policy action in a transition arbitrarily chosen from the buffer; the goal is the expocted return. The ET information is embedded in the paramcters @ since they are updated according to 0 + 0 + de. Here is the eligibility trace, incremented each update by the value gradient (Sutton & Barto, 2018, Chapter 12): < yde + (s.
Finally, successive works advanced on the idea of ETs, and proposed different updates for the eligibility vector (Singh & Sutton, 1996; van Hasselt & Sutton, 2015; Precup, 2000a).
Emphatic Temporal Differences (ETDs) (Sutton et al., 2016; Mahmood et al., 2015; Jiang et al., 2021b) continue on the idea of ETs to weigh TD updates with a trace. They aim to address the issue that canonical ETs may suffer from early divergence when combined with non-linear function approximation and off- off-policy learning. The re-weighing in ETD is based on the emphatic trace, which encodes the degree of bootstrapping of a state.
Originating from tabular and linear RL, the intuition behind ETDs is that states with high uncertainty - the states encountered long after the stale-action pair of evaluation - are more reliable, and vice versa. The main adaptation of the algorithm to Deep RL is by Jiang et al. (2021b), who propose the Windowed Emphatic TD(A) (WETD) algorithm. In this approach, ETD is adapted to incorporate update windows of length n, introducing a mixed update scheme where each state in the window is updated with a variable bootstrapping length, all bootstrapping on the last state in the window. The influence of an action in WETD is the same as for any other ET, but the trace itself is different and measures the amount of bootstrapping of the current estimate.
ETDs provide an additional mechanism to re-weigh updates, the interest function i S - [0, oo). By emphasising or de-emphasisiin the interest of a state, the interest function can be a helpful tool to encode the influence of the actions that had led to that state. Because hand-crafting an interest function requires human interventions, allowing suboptimal and biased results, Klissarov et al. (2022) proposes a method to learn and adapt the interest function at cach update using meta-gradients. Improvements on both discrete control, such as ALE, and on continuous control problems, such MuJoCo (Todorov et al., 2012), suggest that the interest function can be helpful to assign credit faster and more accurately.
Re-weighing updates includes a set of techniques to adjust the influence of past actions based on their temporal proximity to the current state. Such methods aim to miligate the limitations of TD met by dynamically adjusting the weight assigned to past actions, thereby emphasizing or de-emphasizing their contribution to future rewards. For this reason, these mothods can be soen as potential solutions to mitigate the impacts of delayed effects and improve credit assignment in settings with high MDP depth, as shown in Table 4.
24

---

Published in Transactions on Machine Learning Research (04/2024)
6.1.3 Assigning credit to temporally extended actions
The third and last subset of methods in this category assigns credit to temporally extended actions rather than a single, atomic action. This is formalised in the oplions framework (Sutton el al., 1999; Precup, 2000b).
For the purpose of CA, options, also known skills (Haarnoja et al., 2017; Eysenbach et al., 2018), can be described as the problem of achieving sub-goals, such that an optimal policy can be seen as the composition of elementary behaviours. For example, in a key-to-door environment, such as MiniGrid (Chevalier-Boissee et al., 2018) or MiniHack (Samvelyan et al., 2021) the agent might select the option pick up the key, followed by open the door. Each of this macro-action requires a lower level policy to be executed. For example, pick up the key requires selecting the actions that lead to reach the key before grabbing it. In the option framework, credit is assigned for each specifie subgoal (the macro-action), with the benefits already described for the explicitness property, from Section 4.6. The idea stems from the intuition that it is easier to assign credit to macro-actions since a sequence of options is usually shorter than sequence of atomic actions, reducing the overall temporal distance to the time of achieving the goal.
However, since the option literature often does not explicitly condition on goals, but uses other devices to decompose the CA problem, we review works about learning options next, and dedicate a separate section to auxiliary goal-conditionin in Section 6.3.
The option-critic architecture (Bacon et al., 2017) scales options to Deep RL and mirrors the actor- critic architecture but considering options rather than actions. The option-critic architecture allows learning both how to execute specific option, and which option to execute at each time simultaneously and online. The option executes using the call-and-return model. Starting from a. state 8, the agent picks an option w according to its policy over options uy. This option then determines the primitive action selection process through the intra-policy Tw until the option termination function B signals to stop. Learning options, and assigning credit to its actions, is then possible using the intra-option policy grudient and the termination gradient theorems (Bacon et al., 2017), which define the gradient (thus the corresponding update) for all three elements of the learning process: the option w E Ω, their termination function 3(s) and the policy over options πΩ. Here, the context is state s E S, the actions to assign credit to are both the intra-option action a E A and the option w E S2, and the goal is to maximise the return.
On the same lines, Riemer et al. (2018) propose hierarchical option-critics, which allows learning options at multiple hierarchical levels of resolution nested options but still only on a fixed number of pre-selected options. Klissarov & Precup (2021) further improve on this method by updating all options with a single batch of experience.
In the context of the option-critic architecture, CA occurs at multiple levels of the hierarchy. At the lower, intra-option level, where individual actions are taken, credit assignment involves determining the contribution of each action to the achievement of sub-goals. This is essential for learning effective policies for executing primitive actions within each option. At the higher level of the hierarchy, credit assignment involves attributing credit to options for achieving higher-level goals and involves identifying the contribution of each option to achieving the overall task objective. The hierarchical structure of the option-critie archilecture facilitates credit assignment by decomposing the learning problem into multiple levels of abstraction. For their ability to decompose bigger task into smaller sub-problens, these methods naturally improve credit assignment when effects are delayed and in settings with high MDP depth (see Table 4).
6.1.4 Summary and discussion
The methods we covered in this section use the temporal distance between the context-action pair and a reward to mcasure the action influence. The closer is the action, the higher is its influence and vice versa. While this could maybe be a reasonable assumption when the policy is optimal, it is not the case for the early exploratory stages of learning, In fact, as described in Section 5.4, highly influential actions are often taken long before their rewards are collected while exploring. For example, in our usual key-to-door example, the agent would pick up the key, perform hundreds of random, unnecessary actions, and the goal-tile only reached after those. In these cases, the two events are separated by "maltilude of [random and non-influential]
25

---

Published in Transactions on Machine Learning Research (04/2024)
decisions" (Minsky, 1961). Because these non-inftuential actions are temporally closer to reaching the goal- tile than that of picking up the key, these methods mistakenly assign them high influence and, in particular, a higher influence than to pick up the key.
Today, methods that assign credit only by looking at the temporal distance between the action and the outcome usually underperform on tasks with delayed effects (Arjona-Medina et al., 2019). Nevertheless, some of the branches in this category improve assignments in condition of high MDP depth by re-weighing updates, using advantage or breaking down the task into multiple, composable subtasks.
6.2 Decomposing return contributions
To improve CA in settings with high MDP depth, the line of research we describe next focuses on decomposing returns into per-timestep contributions. These works interpret the CAP a redistribution problem: the return observed at termination is re-distributed to each time-step with auxiliary mechanism that depends on each method and complements TD learning.
Temporal Value Transport (TVT) (Hung et al., 2019) uses an external long-term memory system to improve on delayed tasks. The memory mechanism is based on the Differentiable Neural Computer (DNC) (Grefenstette et al., 2015; Graves al., 2016), neural network then reads events from an external memory matrix, represented as the hidden state of a Long-Short-Tie Schor--Ter--Mee Term-Memory (LSTM). The agent decides read from and write into it. To write, state-action-reward triples are projected to lower dimensional space, and processed by the DNC. During training, this works a Irigger: when a past state-action pair is read from memory, it gets associated with the current one, transporting the state-action value credit- from the present to the remote state. To read, the stato-action-rowardd is reconstructed from the latent code. During inference, this acts as a proxy for credit. If a past state-action-reward triple is retrieved from the memory, it means that correlated with the current return. This allows to use the retrieval score of a past transition as measure of the influence of its action.
Return Decomposition for Delayed Rewards (RUDDER) (Arjona-Mediing et al., 2019) stems from the intuition that, if we can construct a reward function that redistributes the rewards collected in trajectory such that the expected future reward is zero, we obtain an instantaneous signal that immediately informs the agent about future rewards. The method proposes to learn a. function f : (S x A)T - IR that maps a sequence of state-action pairs to the sum of discounted rewards, including the past, present and future rewards. In practice, f is implemented as an LSTM, which is trained to fit subset of the whole experience set D, D. D, is cucstr to contain only trajectories containing delayed rewards, and experience is sampled proportionally to the current prediction error. The underlying hypothesis is that, by fitting the return, the LSTM's hidden state holds useful information to redistribute the return to the most relevant transitions in the sequence.
Once f represents a faithful model of the return, at each iteration of the RL algorithm, RUDDER uses the LSTM to infer the return for each 8t, 0r ind ~ PA It then uses the difference between the inferred returns (i.., the redistributed returns) at two consecutive time steps as a reward perform canonical TD learning. This quantity, represents the credit of a state-action pair:
K K(st, ar) = f(s441, a++1) - f(st, a.)
(19)
Here, ((5411,041))1 f(s, a.) ) (s, is the reward function of M (S,AR R, p,,,), 7), an MDP return- RR, p,7): M and M have the same set of optimal policies, but the reward function R' of M is such that the sum of expected future rewards is zero for all states (all the future rewards are paid in the current state). The context is a history h = (ot, or, : 0 < t T} from the assigned MDP, the action is an action from the trajectory a E h and the goal is the achieved return.
equivalent to = R,
Self- Attentional Credit Assignment for Transfer (SECRET) (Ferret et al., 2021a) uses a causal Transformer-like architecture (Vaswani et al., 2017) with a self-attention mechanism (Lin et al., 2017) in the standalone supervised task of reconstructing the sequence of rewards from observations and actions. then views attention weights over past state-action pairs as credit for the generated rewards. This was shown to
26

---

Published in Transactions on Machine Learning Research (04/2024)
help in settings of high MDP depth in a way that transfers to novel tasks when trained over distribution of tasks. We can write its measure of action influence as follows:
T
(st,, as) = Σ 1(s - 8, A. =aa Σ (rrr
(20)
Here, Otei is the attention weight on (o;, a:) when predicting the reward rj- Also, here the context is a history h, the action is an action from the trajectory a E h, and the goal is the achieved return.
Synthetic returns (SR) (Raposo et al., 2021) assume only one state-action to be responsible for the terminal reward. They propose form of state pairs association where the earlier state (the operant) is a leading indicator of the reward obtained in the later one (the reinforeer). The association model is Iearned with form of episodic memory. Each entry in the memory buffer, which holds the states visited in the current episode, is associated with reward the synthetic reward- via supervised learning, At training time, this allows propagating credit directly from the reinforcer to the operant, bypassing the local temporal difference. When this reward model is accurately learned, each time the operant is observed, the synthetic reward model spikes, indicating a creditable state-action pair. Here the synthetic reward acts as a measure of causal influence, and we write:
K(s,a) = - (8) ((()-
(21)
Here [(s) is the synthetic reward function, and it is trained with value regression on the loss ||re u(s:) Eken f(si) b(s:)ll, where h(s;) and b(s:) are auxiliary neural networks optimised together with J. As for Arjona-Medina et al. (2019), the context is history h from the assigned MDP, the action is an action from the trajectory E h, and the goal is the achieved return. This method is, however, stable only within a narrow range of hyperparameters and assumes that only one single action is to be credited.
6.2.1 Summary and discussion
The methods in this section assign credit by decomposing returns into per time-step contributions and then learning values from this new, clearer reward signal. For the purposes of this survey, they mainly differ by the method used to redistribute the contributions to each context-action pair. TVT uses an external memory system, RUDDER uses contribution analysis, SECRET exploits the Transformer's 's self-attention weights, SR use a gating function. Their motivation stems from improving on delayed effects, which they often state as an explicit goal, and for this reason, we report them as improving CA in settings of high MDP depth (Table 4).
Indeed, the empirical evidence they provide suggests that improvements are consistent, and redistribution methods provide benefits over their TD learning baselines. On the other hand, these methods do not provide formal guarantees that the assignments improve over TD learning, and there is currently gap to fill to justify these improvements also thcoretically. This is the case, for example, of other methods (Harutyunyan et al., 2019; Wang et al., 2016b; Mesnard el al., 2021; van Hasselt et al., 2021) that prove to reduce the variance of the evaluation, some of which we describe in later sections.
6.3 Conditioning predefined set of auxiliary goals
The methods in this category evaluate actions for their ability to achieve multiple goals explicitly. They do so by conditioning the value function on a goal and then using the resulting value function to evaluate actions. The intuition behind them is that the agent's knowledge about the future can be decomposed into more elementary associations between states and goals. We now describe the two most influential methods in this category.
General Value Functions (GVFs) (Sutton et al., 2011), described in Scction 4.5, stem from the idea that knowledge about the world can be expressed in the form of predictions. These predictions can then be organised hierarchically to solve more complex problems. While GVFs carry several modifications to the
27

---

Published in Transactions on Machine Learning Research (04/2024)
canonical value, we focus on its goal-conditionin for the purpose of this review, which is also its foundational idea. GVFs conditions the action value a goal to express the expected return with respect to the reward function that the goal induces. In their original formulation (Sutton et al., 2011), GVFs are a set of value functions, one for each goal. The goal is any object in a predefined goal set of MDP states g E S, and the resulting measure of action influence is the following:
((s, ass,a.g) g) - =
(22)
that is the g-function with respect to the goal-conditioned reward function R(s,a, a.g), which is 0 everywhere, and I when certain stale is reached. Because GVTs evaluate action for what it is going to happen in the
future, GVFs are forward methods, and interpret the CAP as prediction problem: "What is the expected return of this action, given that is the goal?".
Universal Value Functions Approximators (UVFAs) (Schaul et al., 2015a) scale the idea of GVFs to large set of goals, by using single value function to learn the whole space of goals. One major benefit of UVFAs over GVFs is that they are readily applicable to Deep RL by simply adding the goal as an input to the value function approximator. This allows the agent to learn end-to-end with bootstrapping and allows for exploiting shared prediction structure across different states and goals. Since they derive from GVFs, UVFA share most of their characteristics. The context is an MDP state E S; the goal is still any object in a predefined goal set of states, E S, and the credit of an action is the expected return of the reward function induced by the goal (see Equation (22)).
6.3.1 Summary and discussion
The methods in this category stand out for using an explicil goal to assign credit, as described in Section 4.6. What distinguishes these methods from those that follow in the next section (which also use goals explicitly) is their flexibility. While in hindsight methods choose the goal after completing a trajectory, or based on information acquired during training, these methods do not. Instead, the set of goals of a GVF predefined in Sutton al. (2011). UVFAs, even if they can generalise to new goals in theory, they are designed with that purpose in mind, and their application is limited. This represents both strong limitation of these methods, and gap to fill in the literature, since it limits both their fiexibility and their autonomy to adapt to different tasks, requiring the human designer to specify the set of goals ex-ante and to provide the set of goals as an input at the start of training.
Furthermore, their interpretation of credit still linked to the idea of temporal contiguity described in Section 6.1. For this reason, they share many drawbacks and limitations with those methods and perform poorly when the MDP is deep, especially if not accompanied by more advanced techniques. To the best of our knowledge, there are examples in the literature that pair these methods with more advanced CA techniques (e.g., options), which represents a gap to fill.
On the other hand, by specifying a goal explicitly (GVFs) and by genoralising over the goal space (UVFA), conditioning on a predefined set of goals provides a way to extract signals from the environment even when the signal is sparse and action influence is low. Tn fact, even when the main task is complex, the set of auxiliary goals is designed to provide a useful signal for learning. This is the reason why we consider these methods improving CA when the MDP is sparse (see Table 4).
6.4 Conditioning in hindsight
The methods in this category are characterised by the idea of re-evaluating the action influence according to what the agent achieved, rather than what it was supposed to achieve. This means that, given trajectory h, we can choose some goal g E G (after collecting h) and evaluate the influence of all the actions in h upon achieving g-
We separate the methods in this category into three subgroups.
(i) Those that ro-label the past experience under a different perspective, such as achieving different goal than the one the agent started.
28

---

Published in Transactions on Machine Learning Research (04/2024)
(ti) Those that condition the action evaluation some properties of the future during training, which becomes an explicit performance request at inference time.
(tti) Those that condition on future factors that are independent on the evaluated action, but that still influence future returns.
6.4.1 Relabelling experience
Hindsight Experience Replay (HER) (Andrychowiez el al., 2017) stems from the problem of learning in sparse rewards environments, which is an example of low action influence in our framework (see Section 5.2. The method exploits the fact that even if a trajectory is suboptimal for the overall implicit goal to maximise MDP returns, it can be viewed as optimal if the goal is to achieve its final state.
In practice, HER brings together UVFAs and experience replay (Lin, 1992) to re-examine trajectories. After collecting a set of trajectories from the environment, the agent stores each transition in a replay buffer, together with both the state it sought to reach and the one that it actually did reach. This allows optimising (* a, 9) for both goals. We refer to this process of re-examining a trajectory collected with a prior goal in mind and evaluating it according to the actually realised outcome as hindsight conditioning, which also the main innovation that HER brings to the CAP. Notice that the original goal is important because the trajectory is collected with policy that aims to maximise the return for that specific goal.
However, in HER, the goal set is still predefined, which requires additinnal specifications from the agent- designer and can limit the autonomy of the overall agent, which increases the autonomy of the agent. HER uses the coalicondi g-values described in Section 6.3 to measure action influence:
K(st, Ge, ST) q" (Se, ST).
(23)
Here the context is a history from the MDP, the action is an action from the trajectory a E h, and the goal g is to visit a state ST at the end of a trajectory.
Since HER limited to off-policy learning with experience replay, Hindsight Policy Gradients (HPGs) (Rauber et al., 2019) transfers the findings of HER to Policy Gradient. (PG) methods, and ex- tend it to online settings. Instead of updating the policy based the actual reward received, Hindsight Policy Gradient (HPG) updates the policy based the hindsight reward, which is calculated based on the new goals that were defined using HER. The main difference with HER is that in HPGs, both the critic and the actor are conditioned on the additional goal. This results in a goal-conditioned policy x(11S = 8, G = g). describing the probability of taking an action, given the current state and a realised outcome. The action influence used in HPG is the advantage formulation of the hindsight policy gradients:
K(s K(s,u,g) 4- (8, ()) (*,
(24)
where g) and (8. g) are the goal-conditioned value functions. Here the context e is a history h (or,at, ae, rt : S l S T), the goal arbitrarily sampled from a goal set., 9 E G. Like HER, HPG is tailored to tasks with low action influence due to low MDP density, and it is shown to be effective in sparse reward settings. Overall, HER and HPG are the first completed work to talk about hindsight as the re-examination of outcomes for CA. Their solution is not particularly interesting for the CAP as they do not cast their problem as CAP and they do not connect the finding to the CAP explicitly. However, they are key precursors of the methods that we review next, which instead provide novel and reusable developments for CAP specifically.
6.4.2 Conditioning on the future
Hindsight Credit Assignment (HCA) Traditional reinforcement lcarning algorithms often struggle with credit assignment as they rely solely on foresight: they evaluate actions against a predetermined goal, selected before acting. These methods operate under the assumption that we lack knowledge of what occurs beyond a given time step, making accurate credit assignment challenging, espocially in tasks with delayed effects. (Harutyunyan al., 2019), on the other hand, centres on utilising hindsight information, acknowledg- ing that credit. assignment and learning typically take place after the agent completes its current tratoryyry.
29

---

Published in Transactions on Machine Learning Research (04/2024)
This approach enables to leverage this additional data to refine the learning of critical variables necessary for credit assignment.
(Harutyunyan et al., 2019) introduces a new family of algorithms known as Hindsight Credit Assignment (HCA). Hindsight Credit Assignment (HCA) algorithms explicitly assign credit to past actions based on the likelihood of those actions having been taken, given that certain outcome has been observed. This is achieved by comparing learned hindsight distribution over actions, conditioned by future state or return, with the policy that generated the trajectory.
More precisely, the hindsight distribution, h(als,, T.9) is the likelihood of an action a, given the outcome g experienced in the trajectory d ~ F F..((DSS = 8, ag ~> T). In practice, Harutyunyan et al. (2019) consider two classes of outcomes: states and returns. We refer to the algorithms that derive from these two classes of goals as state- and Seturn-HCA. For state-HCA, the context с is the current state 8 at time t; the outcome is a future state in the trajectory sy E d where t' > t; the credit is the ratio between the stato-conditional hindsight distribution and the policy s(alss) For return- HCA, the context с is identical; the outcome is the observed return Zú; the credit is the ratio between the return-conditional hindsight distribution and the policy 1 <(als)) [1) The resulting ratios provide a measure of how crucial a particular action was in achieving the outcome. A ratio deviating further from 1 indicales a greater impact (positive or negalive) of that action on the outcome. For example, return- return-HCA measures the influence of an action with the hindsight advantage described Scction 4:
K(8,, de, 21) = ((1-))-)0))))) T(rlS = =st)
P P (v. Se = 81, Zt = 2t)
2t.
(25)
To compute the hindsight distribution, HCA algorithms employ a technique related to importance sampling, Importance sampling estimates the expected value of a function under one distribution (the hindsight distri- bution) using samples from another distribution (the policy distribution). In the context. of HCA, importance sampling weights are determined based on the likelihood of the agent taking each action in the trajectory, given the hindsight state compared to the likelihood of the policy for that same action. Once the hindsight distribution is computed, HCA algorithms can be used to update the agent's 's policy and value function. One approach involves using the hindsight distribution to reweight the agent's 's experience. This means the agent will learn more from actions that were more likely to have contributed to the observed outcome.
Besides advancing the idea of hindsight, (Harutyunyan et al., 2019) carries one novelty: the possibility to drop the typical policy evaluation settings, where the goal is to learn value function by the repeated application of the Bellman expectation backup. Instead, action values are defined as a measure of the likelihood that the action and the outcome appear together in the trajectory, and are a precursor of the sequence modelling techniques described in the next section (Section 6.5).
Poside-Down RL (UDRL) (Schmidhuber, 2019; Srivastava et al., 2019; Ashley et al., 2022; Strupl et al., 2022) is another implementation of the idea to condition on the future. The intuition behind Upside- Down RL (UDRL) is that rather than conditioning returns on actions, which is the case of the methods in Section 6,1, we can invert the dependency and condition actions on returns instead. This allows using returns as an input and inferring the action distribution that would achieve that return. The action distribution is approximated using a neural network, the behaviour policy, that is trained via maximum likelihood estimation using trajectories collected online from the environment. In UDRL the context is completed trajectory d; the outcome is a command that achieves the return Z& in H = T - k timo-steps, which we denote as = (Zu, H); the credit of an action is its probability according to the behaviour function, x(als,g). In addition to HCA, UDRL also conditions the return to be achieved in a specific timespan.
Posterior Policy Gradients (PPGs) (Nota et al., 2021) further the idea of hindsight to provide lower- variance, future-conditioned baselines for policy gradient methods. At the base of PPG there is a novel value estimator, the PVF. The intuition behind PVFs that in POMDPs the state value is not a valid bascline because the true state is hidden from the agent, and the observation cannot provide as a sufficient statistic for the return. However, after full episode, the agent has more information to calculate better,
30

---

Published in Transactions on Machine Learning Research (04/2024)
posteriori guess of the state value at earlier states in the trajectory. Nota et al. (2021) refers to the family of possible a posteriori estimations of the state value the PVF. Formally, a PVF decomposes state into its current observation Or, and some hidden state that is not observable and typically unknown b,. The value of a state can then be written as the expected observation-action value function over the possible non-observable components ur E u = R2. The action influence of a PPG is quantified by the expression:
(o.)) = E [P(u, = =(hh)((0;; NEU
(26)
Notice that, as explained in Section 4.5, the PVF does not depend on an action. However, we can derive the corresponding action-value formulation with q" g"( a) R(st, az) + +00 (h++1)- Here, the context is an observation, the action is the current action and the goal is the observed return. In practice, PVF advances HCA by learning which statistics of the trajectory (d) are useful to assign credit, rather than specifying it objectively as state or return.
6.4.3 Exposing irrelevant factors
Counterfactual Credit Assignment (CCA) For being data efficient, credit assignment methods need to disentangle the effects of a given action of the agent from the effects of external factors and subsequent actions. External factors in reinforcement learning are any factors that affect the state of the environment or the agent's ' reward but are outside the agent's 's control. This can include things like the actions of other agents in the environment, changes in the environment state due to natural processes or events. These factors can make credit assignment difficult because they can obscure the relationship between the agent's actions and its rewards.
Mesnard et al. (2021) proposes to get inspiration from the counterfactuals from causality theory to improve credit assignment in model-free reinforcement lcarning. The key idca is to condition value functions on future events, and learn to extract relevant information from a trajectory. Relevant information here corresponds to all information that is predictive of the return while being independent of the agent's action at time t. This allows the agent to separate the effect of its own actions, the skills, from the effect of external factors and subsequent actions, the luck, which will enable refined credit assignment and therefore faster and more stable learning. It shows that these algorithms have provably lower variance than vanilla policy gradient, and develops valid, practical variants that avoid the potential bias from conditioning future information. One variant explicitly tries to remove information from the hindsight conditioning that depends on the current action while the second variant avoids the potential bias from conditioning on future information thanks to a technique related to important sampling. The empirical evidence in Mesnard et al. (2021) suggests that CCA offers great improvements in tasks with delayed effects.
6.4.4 Summary and discussion
The methods in this section bring many independent novelties to CA. The most relevant for our scope is the idea of hindsight conditioning, which can be summarised as evaluating past actions using additional information about the future, usually not available at the time the action was taken. They differ from those in Section 6.3, as they do not act on a pre-defined objective set of goals, but these are chosen in hindsight.
One drawback of these methods is that they must be able to generalise to a large goal space to be effective, which is not a mild requirement because the ability to generalise often correlates with the size of the network. This can limit the applicability of the method, espocially in cases of low computation and memory budgets.
One of the greatest benefits of these methods is to always have a signal to learn from because, by construction, there is always goal that has been achieved in the current trajectory, for example, the final state, or the terminal return. This, in turn, produces a higher number of context-action-ontoon into additional training data that is often beneficial in supervised problems, and results in an overall denser signal. These improvements in MDPs with low density, which we report in Table 4, are supported by both empirical evidence and thcorctical guarantces to reduce the variance of the evaluations (Harutyunyan et al., 2019; Wang et al., 2016b; Mesnard et al., 2021; van Hasselt et al., 2021). Incorporating information about the future (for example, future returns or states), is most likely one major reason why these algorithms
associations, translates
31

---

Published in Transactions on Machine Learning Research (04/2024)
overperform the others. In fact, when this information is designed to express particular features, such action-independenne or independence to irrelevant factors, such as in Mesnard et al. (2021), the gap increases even further.
Finally, some of these methods (Mesnard et al., 2021) also incentivise the discovery of multiple pathways to the same goal, by identifying decisions that are irrelevant to the outcome, resulting the fact that any of them can be taken without affecting the outcome. The only requirement is to employ an actor-critic algorithm, which we consider mild assumption, since transitioning from actor-critic to value- basue settings is usually trivially achievable.
6.5 Modelling trajectories as sequences
The methods in this category are based on the observation that RL can be seen as a sequence modelling problem. Their main idea is to transfer the successes of sequence modelling in Natural Language Processing (NLP) to improve RL.
On a high level, they all share the same assumption: a sequence in RL is a sequence of transitions (s, a, r), and they differ in either how to model the sequence, the problem they solve, or the specific method they transfer from NLP.
Trajectory Transformers (TTs) (Janner et al., 2021) implements a decoder-only (Radford et al., 2018; 2019) Transformer (Vaswani et al., 2017) to model the sequence of transitions. TTs learn from an observa- tional stream of data, composed of expert demonstrations resulting in offline RL training protocol. The main idea of TTs is to model the next token in the sequence, which is composed by the next state, the next action, and the resulting reward. This enables planning, which TTs exploit to plan via beam search. Notice that, for any of these paradigms, if the sequence model is autoregressive - the next prediction depends only on the past history, but since a full episode is available, the future-condiiioned probabilities are still well-defined, and also TTs can condition on the future. In TTs the action influence is the product between the action probability according to the demonstration dataset and its vavaue
K(tt, a2, 21) = PP(A, arl = = at).
(27)
Here, the context e is an MDP state c = 5 E S, the action is arbitrarily selected, and the goal is the return distribution P(Z).
Decision Transformers (DTs) (Chen et al., 2021) proceed on the same lines TT's but ground the problem in learning, rather than planning. DTs interpret a sequence as a list of (s,, a, Z,) triples, where Z, is the return-to-go. They then use a Transformer to learn a model of the actor that takes the current state and the return as input and outputs a distribution over actions. In addition, they optionally learn a model of the critic as well, which takes the current state and each action in the distribution to output the value of each action. The sequences are sampled from expert or semi-expert demonstrations, and the model is trained to maximise the likelihood of the actions taken by the expert. From the perspective of CA, TTs and DTs are equivalent, and they share the same limitation in that they struggle to assign credit accurately to experience beyond that of the offline dataset. Furthermore, like HCA (Harutyunyan et al., 2019), DTs bring more than one novelty to RL. Besides modelling the likelihood of the next token, they also use returns as input to the model, resulting in a form of future conditioning. However, for CA and this section, we are only interested in their idea of sequence modelling and we will not discuss the other novelties. There exist further extensions to DT both to online settings (Zheng et al., 2022) and to model quantities beyond the return (Furuta et al., 2022). The former allows assigning credit by modelling transition sequences in online settings. The latter, instead, generalises sequence modelling to transitions with additional arbitrary information attached - the same way, Future-Conditional Policy Gradient (PC-PG) generalise HCA.
6.5.1 Summary and discussion
Sequence modelling in RL transfers the advances in sequence modelling for NLP to Deep RL setting. The main idea is to measure credit by estimating the probability of the next. action (or the next token), conditioned
32

---

Published in Transactions on Machine Learning Research (04/2024)
on the context and the goal defined in hindsight, according to an offline dataset of expert trajectories (Chen et al., 2021; Janner et al., 2021).
While some works propose adaptation to online fine-tuning (Lee et al., 2022), these methods mostly learn from offline datasets and the idea to apply sequence modelling online is underexplored. This represents a strong limitation as it limits the generalisation ability of these methods. For example, DT often fail to generalise to returns outside the training distribution.
The distribution that measures this likelihood F(a c, 9) can be interpreted as the hindsight distribution (Harutyunyan et al., 2018) described in Section 6.4. Their development has a similar pattern to that of hindsight methods and progressively generalises to more complex settings, such as online learning (Zheng et al., 2022) and more general outcomes (Furuta et. al., 2022). In practice, these two trends converge logether to model the likelihood of action, states and rewards, which hindsight methods call the hindsight distribution. Yet, this set of methods would benefit from a better connection to the RL theory. This has been the case for hindsight methods, which leverage notions from causality and the policy gradient theorem (Sutton & Barto, 2018) to achieve better experimental results (Mesnard et al., 2021). For the same reasons explained for hindsight methods in Section 6.4, these methods improve CA when the MDP has low density and the action influence is low (see Table 4).
Nevertheless, sequence modelling remains a promising direction for CA, especially for their ability to scale to large datasets (Reed et al., 2022). It is not clear how these methods position with respect to the CA challenges described in Section 5, for the lack of experimentation on tasks that explicitly stress the agent's ability to assign credit. However, in their vicinity to future-conditioned methods, they bear some of the same advantages and also share some limitations. In particular, for their ability to define outcomes in hindsight, regardless of an objective learning signal, they bode well in tasks with low action influence.
6.6 Planning and learning backwards
The methods in this category extend CA to potential predecessor decisions that have not been taken, but could have led to the same outcome (Chelu et al., 2020). The main intuition is that, environments with low action influence, highly influential actions are rare, and when a goal is achieved the agent should use that event to extract as much information as possible to assign credit to relevant decisions.
We divide the section into two major sub-categories, depending on whether the agent identifies prodecessor states by planning with an inverse model, or by learning relevant statistics without it.
6.6.1 Planning backwards
Recall traces (Goyal et al., 2019) combinc model-free updates from Section 6.1 with learning a backward model of the environment. A backward model μ ( = 8, A,- = a) describes the probability of a state S;-1 being the predecessor of another state s, given that the action a was taken. This backward action is sampled from backward policy, Tsso,-lss:), which predicts the previous action, and a backward dynamics.
By autoregressively sampling from the backward policy and dynamics, the agent can cross the MDP back- wards, starting from a final state, sr, up until a starting state, so to produce new trajectory, called recall trace. This allows the agent to collect experience that always leads to a certain state, ST, but that does so from different starting points, discovering multiple pathways to the same goal.
Formally, the agent alternates between steps of GPI via model-free updates and steps of behaviour cloning on trajectories collected via the backward model. Trajectories are reversed to match the forward arrow of time before cloning. This is key step towards solving the CAP as it allows propagating credit to decisions that have not been taken but could have led to the same outcome without interacting with the environment directly. Recall-traces measure the influence of an action by its g-value, but differ from any other method using the same action influence because the contextual data is produced via backward crossing. The goal is to maximise the expected returns.
The same paradigm has been presented in a concurrent work (Edwards et al., 2018) as (FBRL.. The benefits of backward model have also been further investigated in her studies. Wang et al.
RL
33

---

Published in Transactions on Machine Learning Research (04/2024)
(2021) investigate the problem in offiine settings, and show that backward models enable better generalisation than forward ones. van Hasselt et al. (2019) provide empirical evidence suggesting that assigning credit from hypothetical transitions, that is, via planning, improves the overall efficiency in control problems. Chelu et al. (2020) and van Hassolt et al. (2019) further show that backward planning provides even greater benefits than forward planning when the stale-transition dynamics are stochastic.
6.6.2 Learning predecessors
Expected Eligibility Trace (ET())) (van Hasselt et al., 2021) provide a model-free alternative to backward planning that assigns credit. to potential predecessors decisions of the outcome: decisions that have been taken in the past but have not in the last episode. The main idea is to weight the action value by expected cligibility trace, that is, the instantancous trace (sce Scction 6.1), but expectation over the random trajectory, defined by the policy and the state-transition dynamics.
The Deep RL implementation of ET(() considers the expected trace upon the action value representation usually the last layer of ncural network value approximator. Like for other ETs algorithms, ET(() measures action influence using the g-value of the decision and encodes the information of the trace in the parameters of the function approximator. In this case, the authors interpret the value network as a composition of a non-linear representation function ((s) and a linear value function v(s;) = w (ss). The expected trace e(s) EΦ(s) is then the result of applying a second linear operator on the representation. c(s) then trained minimise the expected &g norm between the current estimation of e(s) and the instantaneous
trace.
6.6.3 Summary and discussion
The methods this section assign credit by considering the effects of decisions that have not been taken, but could have led the same outcome. The intuition behind them is that, in tasks where the action influence is low due to low MDP density, creditable actions are rare findings. When this happens the agent can use that occurrence to extract as much information as possible from them.
One of methods does so by learning inverse models of the state-transition dynamics and walking backwards from the outcome. Chelu et al. (2020); van Hasselt et al. (2019) further analyse the conditions in which backward planning is beneficial. Another set methods exploits the idea of eligibility traces and keeps a measure of the marginal state-action probability to assign credit to actions that could have led to the same outcome. Overall, these methods are designed to thrive in tasks where the action influence is low. Also, for their ability to start from high-value state, backward planning methods can find higher number of optimal transpositions, and therefore provide less biased estimate of the credit of state-action pair.
6.7 Meta-learning proxies for credit
The methods in this category aim meta-learn key hyperparameters of canonical TD methods. In fact, RL methods are often brittle to the choice of hyperparameters, for example, the number of steps to look-ahead in bootstrapping, what discount factor to use, or parameersss specific to the method at hand. How to select these meta-parameters is an accurate balance that depends on the task, the algorithm, and the objective of the agent.
For this reason, it is sometimes difficult to analyse them using the usual framework, and we present them differently, by describing their main idea, and the way they are implemented in Deep RL.
Meta Gradient (MG) RL (Xu et al., 2018) remarks how different CA measures of action influence impact the performance on control problems, and proposes to answer the question: "Among the most common TD largets, which one results in the best performance?". ? The method interprets the target as a parametric, differentiable function that can be used and modified by the agent to guide its behaviour to achieve the highest returns.
In particular, Meta- Gradients consider the A-return (Sutton, 1988) target, for it can generalise the choice of many targets (Schulman et al., 2016). It then learns its meta-parameters: the bootstrapping parameter X
34

---

Published in Transactions on Machine Learning Research (04/2024)
and the discount factor n. The connection between MG and CA is that, different pairs of meta-parameters evaluate actions differently. For example, changing the discount factor can move the focus of the assignment from early to late actions with effects on policy improvements (Xu et al., 2018). In fact, adapting and learning the meta-parameters online effectively corresponds to meta-learning a mcasure of action inffuence, and profoundly affects credit.
Meta-learning credit assignment strategies has been further extended distributional (Yin et al., 2023) and continual (Zheng et al., 2020) settings. Badia et al. (2020) investigated the effects of meta-learning the discount factor and the exploration rate to balance out short and long-ted Bangterm rewards.
6.7.1 Summary and discussion
Overall, these methods assign credit to actions by applying canonical TD learning algorithms with meta-learnt mcasure of action influence. The goal can come in the form of an update target (Xu et al., 2018; Zheng et al., 2018; Xu et al., 2020), a full return distribution (Yin et al., 2023), or a reward function (Zheng et al., 2020). This allows agents to adapt their influence function online, especially improving in conditions of high MDP depth.
7 Evaluating credit
Like accurate evaluation is fundamental to RL agents to improve their policy, an accurate evaluation of a CA method is fundamental to CA research to monitor if and how method is advancing the field. The aim of this section is to survey the state of the art of the metrics, the tasks, and the evaluation protocols to evaluate CA method. We discuss the main components of the evaluation procedure, the performance metrics, the tasks, and the evaluation protocols.
7.1 Metrics
We calegorise existing metrics lo evaluate a CA method in two main classes:
(a) The metrics that are already used for control problems. These mostly aim to assess the agent's ability to make optimal decisions, but they do not explicitly measure the accuracy of the action influence.
(b) The metrics that target the quality of an assignment directly, which usually aggregate metrics throughout the RL training procedure.
We now proceed describe the two classes of metrics.
7.1.1 Metrics borrowed from control
Bias, variance and contraction rate. The first, intuitive, obvious proxy assess the quality of a credit assignment. method is its theoretical performance in suitable control problems: the bias, variance, and contraction rate of the policy improvement operator described in Rowland et al. (2020). Notice that these metrics are not formally defined for all the methods, either because some variables cannot be accessed or because the operators they act on are not formally defined for the method in question. For the evaluation operator described in Equation (2), we can specify these quantities as follows.
[TV* TV-S (s) [V=(s) ((ts)) (s)
= sup SES
(28)
is the contraction rate and describes how fast the assignment converges thus how efficient it is. Here (s)s and (**(s) are two estimates of the state-value, which highlights that these set of metrics not suitable to evaluate methods using any measure of action influence.
fixed point, does so, and
35

---

Published in Transactions on Machine Learning Research (04/2024)
If T is contractive, then I < 1AV and V and there exist fixed-point bias of T given by:
6 = ( (s)le,
(29)
where (s) is the true, unique fixed point of T, whose existence is guaranteed by r < 1. For every evaluation operator T, there is an update rule A RISl x H + R that takes input the current estimation of the state-value function, and a trajectory and outputs the updated function. A has a variance:
V == == DI (s))
(30)
These three quantities are usually in a trade-off (Rowland al., 2020). Indeed, many (if not all) studies on credit assignment (Hung et al., 2019; Mesnard et al., 2021; Ren al., 2022; Raposo et al., 2021) report the empirical return and its variance. Because the contraction rate is often harder to calculate, an alternative metric is the tine-to-performance which evaluates the number of interactions necessary to reach given performance. These mostly aim at showing improvement in sample elficiency and/or asymplotic performance. While useful, this is often not enough to assess the quality of credit assignment, as superior returns can be the result of better exploration, better optimisation, better representation learning, luck (as per the environment dynamics' stochasticity) or of combination of such factors. Using empirical returns makes the evaluation method empirically viable for any measure of action influence described in Section 4, even if these metrics are not formally defined for them. Nonetheless, when the only difference between two RL algorithms lies in how credit is assigned, and this is not confounded by the aforementioned factors, it is generally safe to attribute improvements to superior credit, given that the improvements are statistically significant (Henderson et al., 2018; Agarwal et al., 2021).
Task completion rate. A related, but more precise, metric is the success rate. Given a budget of trials, the success rate measures the frequency of task completion, that is, the number of times the task was solved over the total number of episodes: G = |C*|/|[] Here, C* is a set of optimal historics experienced by the agent, and C is the full set of histories used to train it. Considering success rates instead of bias, variance, and trade-off is useful as it alleviates another issue of these performance metrics: there is no distinction between easy-to-optimise rewards and hard-to-optimise rewards. This is evident in the key-to- door task with distractors (Hung et al., 2019), which we describe in detail later in Section 7.2. Due to the stochasticity from the apple phase (the distractors), it is generally impossible to distinguish performance on apple picking (casy-to-optimise rewards) and door opening (hard-to-oppimiie rewards that superior credit assignment methods usually obtain). Furthermore, the minimum success rate Gmin could also be an effective metric to disentangle the effects of exploration from those of CA as discussed in Section 5.4, despite never being employed for that purpose. However, notice that this clarity in reporting credit comes at a cost. In fact, even if these kinds of metrics are more precise than performance metrics, they require expert knowledge of the task. They often suffer from the same confounders as bias, variance, and contraction rate.
Value error. As the value function is at the heart of many credit assignment methods, another proxy for the quality of the credit is the quality of value estimation, which can be estimated from the distribution of TD errors (Andrychowicz et al., 2017; Rauber et al., 2019; Arjona-Medina et al., 2019). We can then generalise the value error to one of influence error: (I]lK(s, a. K(s, a, g)]l,), where || lls denotes the tth norm of vector, [(s, a, g) is the current approximation of influence and ((s, a, .g is the true influence. A drawback of the inffuence error (and the value error) is that it can be misleading. When does not fully converge, for example, because of high MDP sparsity (see Section (b), it can happen that the value error is very low. This is because the current policy never visits state with a return different from zero, and the value function collapses to always return zero. Nevertheless, this metric is a viable option to evaluate RL methods that use some form of action influence. It is not applicable, for example, to PG methods using Monte-Carlo returns to improve parametric policy via gradient ascent (Sutton & Barto, 2018), or to sequence modelling methods (see Section 6.5 that only approximate the action probabilities of a predefined set of demonstrations.
algorithm
36

---

Published in Transactions on Machine Learning Research (04/2024)
7.1.2 Bespoke metrics for credit assignments
We now review metrics that measure the quality of individual credit assignments, that is, how well actions are mapped to corresponding outcomes, or how well outcomes are redistributed to past actions. Usually, these metrics are calculated in hindsight, after outcomes have been observed.
Using knowledge about the causal structure. Suppose we have expert knowledge about the causal structure of the task at hand, i.e. which actions cause which outcomes. This is oflen the case since humans we often have instinctive understanding of the tasks agents tackle. In such case, given observed outcome from agent's 's trajectory, one compare credit assignments, which approxinate such cause and effect relationships, to the ground truth represented by our causal model of the task. We give several examples from the literature. In Delayed Catch, Raposo et al. (2021) assess whether credit assigned to the actions that lead to catches or to the end-of-episode reward since they know that these actions are causing the experienced rewards. They do the samne on the Atari game Skinng, which is a more complex task but that shares the fact that only a subset of the actions of the agent yield rewards. For example, in Skiing, going between ski poles is the only thing that grants rewards (with dclay) at the end of an episode. Ferret et al. (2021a) adopt similar approach and look at the influence attributed to actions responsible for trigger switches in the Triggers environment, which contribute alone to the end-of-episode reward. Similarly, Aijona-Medina et al. (2019) look at redistributions of RUDDER on several tasks, including the Atari 2600 game Bowling.
Counterfactual simulation. A natural approach, which nonetheless seldom explored in the literature, is counterfactual simulation. On a high level, it consists in asking what would have happened if actions that are credited for particular outcomes had been replaced by another action. This is close to the notion of hindsight advantage.
Comparing to actual values of the estimated quantity. This only applies to methods whose credit assignments are mathematically grounded, in the sense that they are the empirical approximations of well- defined quantities. general, one can leverage extra compute and the ability to reset a simulator to arbitrary states to obtain accurate estimations of the underlying quantity, and compare it to the actual, resourco-constrained quantity estimated from experience.
7.2 Tasks
In what follows, we present environments that we think are most relevant to evaluate credit assignment methods and individual credit assignments. The most significant tasks are those that present all three chal- lenges assign credit: delayed rewards, transpositions, and sparsity of the influence. This often corresponds to experiments that have reward delay, high marginal entropy of the reward, and partial observability. To benchmark explicit credit assignment methods, we additionally need to be able to recover the ground truth inffuence of actions w.r.t. given outcomes, or we can use our knowledge of the environment and develop more subjective measures.
7.2.1 Diagnostic tasks
Diagnostic tasks are useful as sanity chocks for RL agents and present the advantage of running rather quickly, compared to complex environments with visual input that may imply several millions of samples before agents manage to solve the task at hand. Notice that these tasks may not be representative of the performance of the method at scale, but provide useful signal to diagnose the behaviour of the algorithm in the challenges described in Section 5. Sometimes, the same environment can represent both a diagnostic task and an experiment. at scale, simply by changing the space of the observations or the action space.
We first present chain-like environments, that can be represented graphically by a chain (environments a c), and then grid-like environment (environment d), that has more natural grid representations for both the environment and the state.
37

---

Published in Transactions on Machine Learning Research (04/2024)
a) Aliasing chain. The aliasing chain (introduced in Harutyunyan et al. (2019) as Delayed Effect) is an enviromment whose outcome depends only on the first action. A series of perceptually aliased and zero-reward states follow this first action, and an outcome is observed at the end of the chain (+1 or -1 depending on the binary first action).
b) Discounting chain. The discounting chain (Osband et al., 2020) is an environment in which first action leads to series of states with inconsequential decisions with final reward that is either 1 or 1 + e, and a variable length. It highlights issues with the discounting horizon.
<) Ambiguous bandit. The ambiguous bandit (Harutyunyan et al., 2019) is a variant of a two-armed bandit problem. The agent is given two actions: one that transitions to stale with a slightly more advantageous Gaussian distribution over rewards with probability -- E, and another that does so with probability
d) Triggers. Triggers (Ferret et al., 2021a) is a family of environments and corresponding discrete control tasks that are suited for the quantitative analysis of the credit assignment abilities of RT. algorithms. Fach environment is a bounded square-shaped 2D gridworld where the agent collects rewards that are conditioned on the previous activation of all the triggers of the map. Collecting all triggers turns the negative value of rewards into positive and this knowledge can be exploited to assess proper credit assignment: the actions of collecting triggers appear natural to be credited. The environments are procedurally generated: when requesting a new environment, random layout is drawn according to the input specifications.
7.2.2 Tasks at scale
In the following, we present higher-dimension benchmarks for agents equipped with credit assignment capa- bilities.
Atari. The Arcade Learning Environment (Bellemare et al., 2013) (ALE) is an emulator in which RL agents compete to reach the highest scores on 56 classic Atari games. We list the ones we deem interesting for temporal credit assignment assessment due to delayed rewards, which were first highlighted by Arjona- Medina et al. (2019). Bowling: like in real-life bowling, the agent must. throw a bowling ball at pins, while ideally curving the ball so that it can clear all pins in one throw. The agent experiences rewards with a high delay, at the end of all rolls (between 2 and 4 depending on the number of strikes achieved). Venture: the agent must enter room, collect treasure and shoot monsters. Shooting monsters only give rewards after the treasure was collected, and there is no in-game reward for collecting it. Seaquest: the agent controls a submarine and must sink enemy submarines. To reach higher scores, the agent has to additionally rescue divers that only provide reward once the submarine lacks oxygen and surfaces to replenish it. Solaris: the agent controls spaceship that carns points by hunting enemy spaceships. These shooting phasos are followed by the choice of the next zone to explore on a high-level map, which conditions future rewards. Skiing: the agent controls skier who has to go between poles while going down the slope. The agent gets reward until reaching the bottom of the slope, at which time it receives reward proportional to the pairs of poles it went through, which makes for long-term credit assignment.
VizDoom. VizDoom (Kempka et al., 2016) is a suite partially observable 3D tasks based on the classical Doom video game, first-person shooter. As mentioned before, it an interesting sandbox for credit assignment because it optionally provides high-level information such as labelled game objects, depth as well top-view minimap representation; all of which can be used for approximate optimally efficient credit assignment algorithms.
BoxWd BoxWorld (Zambaldi et al., 2018) is a family of environments that shares similarities with Triggers, while being more challenging. Environments are also procodurally-gennrate squarc-shaped 2D gridworlds with discrete controls. The goal is reach a gem, which requires going through a series of boxes protected by locks that can only be opened with keys of the same colour while avoiding distractor boxes.
38

---

Published in Transactions on Machine Learning Research (04/2024)
The relations between keys and locks can be utilised to assess assigned credit since the completion of the task (as well as intermediate rewards for opening locks) depends on the collection of the right keys.
Sokoban. Sokoban (Racanière et al., 2017) is a family of environments that is similar to the two previous ones. The agent must push boxes to intended positions on the grid while avoiding dead-end situations (for instance, if block is stuck against walls on two sides, it cannot be moved anymore). While there is no definite criterion to identify decisive actions, actions that lead to dead-ends are known and can be exploited to assess the quality of credit assignment.
DeepMind Lab. DeepMind Lab (Beattie et al., 2016) (DMLab) is a suite of partially observable 3D tasks with rich visual input. We identify several tasks that might be of interest to assess credit assignment capabilities, some of which were used in recent work. Keys-Doors: the agent navigates to keys that open doors (identified by their shared colour) so that can get to an absorbing state represented by cake. Ferret et al. (2021a) consider harder variant of the task where collecting keys is not directly rewarded anymore and leedback is delayed until opening doors. Keys- Leeys-Appess-Doort Doors: Hung et al. (2019) consider an exlended version of the previous task. The agent still has to collect key, but after a fixed duration a distractor phase begins in which it can only collect small rewards from apples, and finally, the agent must find and open a door with the key it got in the initial phase. To solve the task, the agent has to learn the correlation or causation link between the key and the door, which is made hard because of the extended temporal distance between the two events and of the distractor phase. Deferred Effects: the agent navigates between two rooms, the first one of which contains apples that give low rewards, while the other contains cakes that give high rewards but it is entirely in the dark. The agent can turn the light on by reaching the switch in the first room, but it gets an immediate negative reward for it. In the end, the most successful policy is to activate the switch regardless of the immediate cost so that a maximum number of cakes can be collected in the second room before the time limit.
7.3 Protocol
Online evaluation. The most standard approach is to evaluate the quality of credit assignment methods and individual credit assignments along the RL training procedure. As the policy changes, the credit assignments change since the effect of actions depends on subsequent actions (which are dictated by the policy). One can dynamically track the quality of credit assignments and that of the credit. assignment method using the metrics developed in the previous section. For the credit assignment method, since it requires a dataset of interaction, one can consider using the most trajectories produced by the agent. An advantage of this approach is that allows evaluating the evolution of the credit assignment quality along the RL training, with evolving policy and resulting dynamics. Also, since the goal of credit assignment is to help turn feedback into improvements, it makes sense to evaluate it in the context of said improvements. While natural, online evaluation means one has little control over the data distribution of the evaluation. This is problematic because it is generally hard to disentangle credit quality from the nature of the trajectories it is evaluated on. A corollary is that outcomes that necessitate precise exploration (which can be the outcomes for which agents would benefit most from accurate credit assignment) might not. be explored.
Offiine evaluation. An alternative is to consider offiine evaluation. It requires dataset of interactions, either collected before during the RL training. Credit assignments and the credit assignment method then use the parameters learned during the RL training while being evaluated on the offline data. As the policy in the oflline data is generally not the latest policy from the online training, oflline evaluation is better suited for colicy-conditionas credit assignment or (to some extent) jijjectory-coddiionnee credit assignment. Indeed, other forms of credit assignment are specific to a single policy, and evaluating these on data generated from another policy would not be accurate. An important advantage of offline evaluation is that it alleviates the impact of exploration, one controls the data distribution credit is evaluated on.
39

---

Published in Transactions on Machine Learning Research (04/2024)
8 Closing, discussion and open challenges
The CAP is the problem to approximate the influence of an action from finite amount of experience, and it is of critical importance to deploy RL agents into the real world that are effective, general, safe and interpretable. However, there is a misalignment in the current literature on what credit means in words and how it is formalised. In this survey, we put the basis to reconcile this gap by reviewing the state of the art of the temporal CAP in Deep RI, locusing on three major questions.
8.1 Summary
Overall, we observed three major fronts of development around the CAP.
The first concern the problem of how to quanlify action influence (Q1.). We addressed Q1. in Section 4, and analysed the quantities that existing works use to represent the influence of an action. In Section 4.1 we unifiod these measures of action influence with the assignment definition. In Sections 4.3 and 4.5 we showed that the existing literature agrees over an outcome, but that it does not translate that well into mathematics and none of the current quantities align with the purpose. As a consequence, we proposed a set of principles that we suggest measure of action influence should respect to represent credit.
intuition of credil as a measure of the influence of an action
The second front aims to address the question of how to learn action influence from experience and to describe the existing methods to assign credit. In Section 5 we looked at the challenges that arise from learning these measures of action inftuence and, together with Section 6, answered Q2.. We first reviewed the most common obstacles to learning already identified in the literature and realigned them to our newly developed formalism. We identified three dimensions of an MDP, depth, breadth, and density and described pathological conditions on each of them that hinder the CA. In Section 6 we defined CA method as an algorithm whose aim is to approximate a measure of action influence from a finite amount of experience. We categorised methods into those that: (i) use temporal contiguity as a proxy for causal influence; (ii de- compose the total return into smaller per-timestep contributions; (tii condition the present on information about the future using the idea of hindsight; (iv) use sequence modelling and represent action influence the likelihood of action to follow state and predict an outcome; (v) learn to imagine backward transitions that always start at key state and propagate back to the state that could generate them; (vi) meta-lcarn action influence measures.
Finally, the third research front deals with how to evaluate quantities and methods to assign credit and aims to provide an unbiased estimation of the progress in the field. In Section we addressed Q3. and analysed how current methods evaluate their performance and how we can monitor future advancements. We discussed the resources that each benchmark has to offer and their limitations. For example, diagnostic benchnarks do not isolate the specific CAP challenges identified in Section 5; delayed effects, transpositions, and sparsity. Benchmarks at scale often cannot disentangle the CAP from the exploration problem, and it becomes hard to understand whether a method is advancing one problem or another.
8.2 Discussion and open challenges
As this survey suggests, the work in the field is now fervent and the number of studies in a bullish trend, with many works showing substantial gains in control problems only by to the best of our current knowledge advancing on the CAP alone (Bellemare et al., 2017; van Hasselt et al., 2021; Edwards et al., 2018; Mcsnard et al., 2021; 2023).
We observed that the take-off of CA research in the broader area of RL research is only recent. The most probable reason for this is to be found in the fact that the tasks considered in carlier Deep RL research were explicitly designed to be simple from the CA point of view. Using tasks where assigning credit is hard would have - and probably still does, e.g., Küttler et al. (2020) obfuscate other problems that it was necessary to solve before solving the CAP. For example, adding the CAP on the top of scaling RI. to high-dimensional observations (Arulkumaran et al., 2017) or dealing with large action spaces Obulac-Aroole et al., 2015; van Hasselt & Wiering, 2009) would have, most likely, concealed any evidence of progress for the underlying
40

---

Published in Transactions on Machine Learning Research (04/2024)
challenges. This is also why CA methods do not usually shine in classical benchmarks (Bellemare et al., 2013), and peer reviews are often hard on these works. Today, thanks to the advancements in other areas of RL, the field is in a state where improving on the CAP is a compelling challenge.
Yet, the CAP still holds open questions and there still much discussion required to consider the problem solved. In particular, the following observations describe our positions with respect to this survey.
Aligning future works to a common problem definition. The lack of a review since its conception (Minsky, 1961) and the rapid advancements produced a fragmented landscape of definitions for action influ- ence, an ambiguity in the meaning of credit assignment, a misalignment between the general intuition and its practical quantification, and general lack of coherence in the principal directions of the works. While this diversity is beneficial for the diversification of the rescarch, it is also detrimental to comparing the methods. Future works aiming to propose new CA method should clarify these preliminary concepts. Answers to "What is the choice of the measure of action influence? Why the choice? What is the method of learning it from experience? How is it evaluated?" would be good a starting point.
Characterising credit. " "What is the minimum set of properties that measure of action influence should respect to inform controly What the more desirable ones?". This question remains unanswered, with some ideas in Ferret (2022, Chapler 4), and we still need to understand what characterises a proper measure of credit.
Causality. The relationship between CA and causality is underexplored, but in small subset of works (Mesnard et al., 2021; Pitis et al., 2020; Buesing et al., 2019). The literature lacks a clear and complete formalism that casts the CAP as a problem of causal discovery. Investigating this connection and formalising a measure of action influence that is also satisfactory measure of causal influence would help better understand the effects of choosing measure of action influence over another. Overall, we need to better understand the connections between CA and causality; what happens when credit a strict measure of causal influence? How do current algorithms perform with respect to this measure? Can we devise an algorithm that exploits a causal measure of influence?
Optimal eredit. Many works refer to optimal credit to assigning credit optimally, but it is unclear what that formally means. "When is credit optimal?" remains unanswered.
Combining benefits from different methods. Methods conditioning on the future currently show superior results compared to methods in other categories. These promising methods include hindsight (Section 6.4), sequence modelling (Section 6.5) and backward learning and planning methods (Section 6.6). However, while hindsight methods are advancing fast, sequence modelling and backward planning methods are underinvestigated. We need better understanding of the connection between these two worlds, which could potentially lead to even better ways of assigning credit. Could there be a connection between these methods? What are the effects of combining backward planning methods with more satisfactory measures of influence, for example, with CCA?
Benchmarking. The benchmarks currently used to review a CA method (Chevalier-Boisver et al., 2018; Bellemare et al., 2013; Samvelyan et al., 2021) (see Section 7.2) are often borrowed from control problems, leading to the issues discussed in Section and recalled in the summary above. On complementary note, al., 2019; Mesnard et al., 2021),
CA methods are often evaluated in actor-critic settings (Harutyunyan which adds layers of complexity that are not necessary. This, together with the inclusion of other unnecessary accessories, can obfuscate the contributions of CA to the overall RL success. As a consequence, the literature lacks fair comparison among all the methods, and it is not clear how all the methods in Section 6 behave with respect to each other against the same set of benchmarks. This lack of understanding of the state of the art leads to a poor signal to direct future research. We call for a new, communit--driver single set of benchmarks that disentangles the CAP from the exploration problem and isolate the challenges described in Section How to disentangle the CAP and the exploration problem? How to isolate each challenge? Shall evaluate in value-based settings, and would the ranking wetween the methods be consistent with
41

---

Published in Transactions on Machine Learning Research (04/2024)
evaluation in actor-critic settings? While we introduced some ideas in Section 5.4, these questions still unanswered.
Reproducibility. Many works propose open-source code, but experiments are often not reproducible, their code is hard to read, hard to run and hard to understand. Making code public is not enough, and cannot be considered open-source it is not easily usable. Other than public, open-source code should be accessible, documented, easy to run, and accompanied by contimuous support for questions and issues that may arise from its later usage. We need future research to aequire more rigour the way to publish, present, and support the code that accompanies scientific publications. In particular, we need (i) a formalised, shared and broadly agreed standard that is not necessarily new standard; (ti for new studies to adhere to this standard, and (tii) for publishers to review the accompanying code at least as thoroughly as when reviewing scientific manuscripts.
Monitoring advancements. The community lacks database containing comprehensive, curated results of each baseline. Currently, baselines are often re-run when new method is proposed. This can po- tentially lead to comparisons that are unfair both because the baselines could be suboptimal (e-g., in the hyperparameters choice, training regime) and their reproduction could be not faithful (e.g. in translating the mathematics into code). When these conditions are not met, is not clear whether a. new method is advancing the field because it assigns credit better or because of misaligned baselines. We call for new, community-driven database holding the latest evaluations of each baseline. The evaluation should be driven by the authors and the authors be responsible for its results. When such database will be available, new publications should be tested against the same benchmarks and not re-run previous basclines, but rather refer to the curated results stored in the database.
Peer reviewing CA works. As a consequence of the issues identified above, and because CA methods do not usually shine in classical benchmarks (Bellemare et al., 2013), peer reviews often do not have the tools to method and its improvements. On one hand, we need a clear evaluation protocol,
capture the novelties including a shared benchmark and leaderboard to facilitate peer reviews. On the other hand, peer reviews must steer away from using tools and metrics that would be used for control, and use those appropriate for the CAP instcad.
Lack of priors and foundation models. Most of the CA methods start to learn credit from scratch, without any prior knowledge but the one held by the initialisation pattern of its underlying network. This represents a main obstacle to making CA efficient because, at each new learning phase, even elementary associations must be learned from scratch. In contrast, when facing a new task, humans often rely on their prior knowledge to determine the influence of an action. In the current state of the art, the use of priors to assign credit more efficiently is overlooked. Vice versa, the relevance of the CAP and the use more advanced methods for CA (Mesnard al., 2021; 2023; Edwards et al., 2018; van Hasselt et al., 2021) is often underestimated for the development of foundation models in RI.
8.3 Conclusions
To conclude, in this survey, we have set out to formally settle the CAP Deep RL. The resulting material does not aim to solve the CAP, but rather proposes a unifying framework that enables a fair comparison among the methods that assign credit and organises existing material to expedite the starting stages of new studies. Where the literature lacks answers, we identify the gaps and organise them in a list of challenges. We kindly encourage the research community to join in solving these challenges in a shared effort, and hope that the material collected in this manuscript can be helpful resource to both inform future advancements in the field and inspire new applications in the real world.
References
David Abel, Cameron Allen, Dilip Arumugam, D Ellis Hershkowitz, Michael Littman, and Law- L.S Wong. Bad-policy density: A measure of reinforcement. learning hardness. aiv preprint
42

---

Published in Transactions on Machine Learning Research (04/2024)
arXiv:2110.03424, 2021a.
David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman, Doina Precup, and Satinder Singh. On the expressivity of markov reward. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Newral Information Processing Systems, 2021b.
David Abel, Andre Barreto, Benjamin Van Roy, Doina Precup, Hado Hasselt, and Satinder Singh, A definition of continual reinforcement learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openrevian wtt.pparrrreeeeeeeoooonaaaa///// net//oorum:dd22229WEWWY
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Mare Bellemare. Deep reinforcement learning at the edge of the statistical precipice. Advances in neural information processing systems, 34:29304 29320, 2021.
Mostafa Al-Emran. Hierarchical reinforcement learning: a survey. International journal of computing and digital systems, 4(02), 2015.
Susan Amin, Maziar Gomrokchi, Harsh Satija, Herke van Hoof, and Doina Precup. A survey of exploration methods in reinforcement learning. arXiv preprint arXin:2109.001 2021.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Picter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in neural information processing systems, volume 30, 2017. URL httpss////ooeeeing.eeeeee www..euurric... cc/ pdf.
Thomas Anthony, Tom Eccles, Andrea Tacchetti, János Kramár, Ian Gemp, Thomas Hudson, Nicolas Porcel, Marc Lanctot, Julien Pérolat, Richard Everett, et al. Learning to play no-press diplomacy with best response policy iteration. Advances in Neural Information Processing Systems, 33:17987 18003, 2020.
Jose A Arjona-Medina, Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brandstetter, and Sepp Hochreiter. Rudder: Return decomposition for delayed rewards. Advances in Neural Information Processing Systems, 32, 2019.
Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26 38, 2017.
Kai Arulkumaran, Dylan R Ashley, Jürgen Schmidhuber, and Rupesh K Srivastava. All you need is super- vised learning: From imitation learning to meta-rl with upside down rl. arXiv preprint orXiv:2202.11966 2022.
Dilip Arumugam, Peter Henderson, and Pierre-Lue Bacon. An information--thoreliec perspective on credit assignment in reinforcement learning. CoRR, abs/2103.06224 2021. URL https://arxixi org/abs/2103, 06224.
Dylan R Ashley, Kai Arulkumaran, Jürgen Schmidhuber, and Rupesh Kumar Srivastava. Learning relative return policies with upside-down reinforcement learning. arXie preprint urXiv:290.112744 2022.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of the AAAI conference artificial intelligence, volume 31, 2017.
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhao- han Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benehmark. In Inter- national Conference on Machine Learning, pp. 507 517. PMLR, 2020.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In International Conference on Learning Represenlations, 2019.
Leemon C III Baird. Reinforcement Learning Through Gradient Descent. PhD thesis, US Air Force Academy, 1999.
43

---

Published in Transactions on Machine Learning Research (04/2024)
David Balduzzi, Hastagiri Vanchinathan, and Joachim Buhmann. Kickback cuts backprop's red-tape: Bi- ologically plausible credit assignment in neural networks. In Proceedings of the AAAT Conference Artificial Intelligence, volume 29, 2015.
Elias Bareinboim, Juan D. Correa, Duligur lbeling, and Thomas Ieard. On Pearls Hierarchy and the Foun- dations of Causal Inference, pp. 507556. Association for Computing Machinery, New York, NY, USA, 1 edition, 2022. ISBN 4704986395. URL https://doi. org/ http:///oo..orr/1111/////55/5//1 1115/3501114.3501101
Andrew G Barto. Intrinsic motivation and reinforcement learning. Intrinsically motivated learning in natural and arlificial systems, pp. 17 47, 2013.
Andrew G Barto and Sridhar Mahadevan. Recent advances in hicrarchical reinforcement learning. Discrete event dynamic systems, 13(1):11-77, 2003.
Andrew G Barto, Satinder Singh, Nuttapong Chentancz, al. Intrinsically motivated learning of hierarchical collections of skills. In Proceedings of the 3rd International Conference on Develoyment and Learning. volume 112, pp. 19. Citeseer, 2004.
Charles Beattie, Joel Z Leibo, Denis Teplyashin, Tom Ward, Marcus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Victor Valdés, Amir Sadik, et al. Deepmind lab. arXiv preprint 16X.::161..03800 2016.
Vahid Behzadan and William Hsu. arXiv:1906. 01121, 2019.
Adversarial exploitation of policy imitation.
arXiv preprint
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
Marc G Bellemare, Georg Ostrovski, Arthur Guez, Philip Thomas, and Rémi Munos. Increasing the action gap: New operators for reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Mare G Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. International Conference on Machine Learning, pp. 449-458. Proceedings of Machine Learning Research, 2017.
Marc G Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C Machado, Subhodeep Moitra, Sameera Ponda, and Ziyu Wang. Autonomous navigation of stratospheric balloons using rein- forcement learning. Nature, 588(783)):77-82, 2020.
Michael Bowling, John D Martin, David Abel, and Will Dabney. Settling the reward hypothosis. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarleu (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 3003-30 3020. PMLR, 23-29 Jul 2023. URL https: htttps://proceeding/ mlr. press/v202/ Theess/v202/bowlingg22 html.
Lars Buesing, Theophanc Weber, Yori Zwols, Nicolas Hoess, Sebastien Racaniere, Arthur Guez, and Jean- Baptiste Lespiau. Woulda, coulda, shoulda: Counterfactually-guiiee policy search. In International Conference Learning Representations, 2019. URL https:///penrrevier.
Yu-Han Chang, Tracey Ho, and Leslie Kaelbling. All learning is local: Multi-agent learning in global reward games. Advances in neural information processing systems, 16, 2003.
Veronica Chelu, Doina Precup, and Hado P van Hasselt. Forethought and hindsight in credit assign- ment. In Н. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Н. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2270 2281. Curran Associates, Inc., 2020. URL https: / //proceedings. neurips
pdf.
Veronica Chelu, Diana Borsa, Doina Precup, and Hado van Hasselt. Selective credit assignment. arXiv preprint ar XrX::22202.09699 2022.
44

---

Published in Transactions on Machine Learning Research (04/2024)
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. In Advances in Newral Information Processing Systems, volume 34, pp. 15084 15097, 2021. URL https: Paper.pdf.
//proceedings. ctw.eedddnnnneuuisss..ommmm haa.r//s//ppprr.....////////aaa0
Zhixin Chen and Mengxiang Lin. Self-imitation learning in sparse reward settings.
arXiv preprint
arXiv:2010.06962, 2020.
Nuttapong Chentanez, Andrew Barto, and Satinder Singh. Intrinsically motivated reinforcement learning. Aduances in neural information processing systems, 17, 2004.
Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. http:////ggttub..ccaaiaannnnnee www////xiimm//////mcmm..aa gaapee////gmmmmiiiiii.... 2018.
Cédric Colas, Tristan Karch, Olivier Sigaud, and Pierre-Yoe Yves Oudeyer. Autotelic agents with intrinsically motivated goal-conditioned reinforcement learning: short survey, Journal of Artificial Intelligence Re- search, 74:1159-111 1199, 2022.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmalcki, Diego de Las Casas, et al. Magnetic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897):4144419, 2022.
Gabriel Dulac-Arnold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillierap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep reinforcement learning in large discrete action spaces. arXic preprint arXi::1512.0000 2015.
Ashley D Edwards, Laura Downs, and James C Davidson. Forward-backward reinforcement lcarning. arXiv preprint ar Xiv:18803 10227, 2018.
Andrew Elliot and James W Fryer. The goal construct in psychology. In Handbook of motivation science, volume 18, pp. 235 250, 2008.
Benjamin Eysenbach and Sergey Levine. Maximum entropy RT (provably) solves some robust. RL, problems. In International Conference Learning Representations, 2022.
Benjamin Eysenbach, Abhishek Gupta, Julian Tbarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations, 2018.
Francesco Faccio, Louis Kirsch, and Jürgen Schmidhuber. Parameter-based value functions. In International Conference Learning Representations, 2021. URL http:://ppppeeeeeeeeeeeeeerrtrra
Amir-massoute Farahmand. Action-gay gap phenomenon in reinforcement learning. Advances in Neural Infor- mation Processing Systems, 24, 2011.
Johan Ferret. On Actions that Matter: Credit Assignment and Interpretability in Reinforcement Learning.
PhD thesis, Université de Lille, 2022.
Johan Ferret, Raphaäl Marinier, Matthicu Gcist, and Olivier Pictquin. Sclf-attentional credit assignment for transfer in reinforcement. learning. In Proceedings of the Twenly-Ninth International Joinl Conference on Artificial Intelligence, 1JCAT 2021a. ISBN 9780999241165.
Johan Ferret, Olivier Pietquin, and Matthieu Geist. Self-imitation advantage learning. In AAMAS 2021-20th International Conference on Autonomous Agents and Multiagent Systems, 2021b.
Angelos Filos, Panagiotis Tigkas, Rowan McAllister, Nicholas Rhinehart, Sergey Levine, and Yarin Gal. Can autonomous vehicles identify, recover from, and adapt to distribution shifts? International Conference on Machine Learning, pp. 3145 3153. PMLR, 2020.
Yannis Flet-Berliac. The promise of hierarchical reinforcement learning. The Gradient, 9, 2019.
45

---

Published in Transactions on Machine Learning Research (04/2024)
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Coun- terfactual multi-agent policy gradients. In Proceedings of the AAAT conference arbificial intelligence, volume 32, 2018.
Hiroki Furuta, Yutaka Matsuo, and Shixiang Shane Gu. Generalized decision transformer for offline hindsight information matching. In International Conference on Learning Represenlations, 2022. URL https: / //openreview "eppenreiee..net/formne"
Jim Gao. Machine learning applications for data center optimization, 2014.
Javier García, Fern, and o Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(42):1437 1480, 2015. URL http://jmlr wtapenl...rrr/rreeeeeee ptgppppers//11//grcaall.. html.
Matthicu Geist, Bruno Scherrer, ct al. Off-policy learning with cligibility traces: survey. J. Mach. Learn. Res., 15(1):289 333, 2014.
Anirudh Goyal, Philemon Brakel, William Fedus, Soumye Singhal, Timothy Lillicrap, Sergey Levine, Hugo Larochelle, and Yoshua Bengio. Recall traces: Backtracking models for efficient reinforcement learning.
In International Conference on Learning Representations, 2019. URL http::///pperreeeeeeeeefooooeooe id=HygsfnR9Ym.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Tvo Danihelka, Agnieszka Grabska-Barwinska. Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471 471-476,, 2016.
Edward Grefenstetle, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. Advances in neural information processing systems, 28, 2015.
Nathan Grinsztajn, Johan Ferret, Olivier Pictquin, Matthicu Geist, et al. There is no turning back: A self-supervised approach for reversibility-waare reinforcement learning. Advances in Neural Information Processing Systems, 34:1898 1911, 2021.
Arthur Guez, Fabio Viola, Theophane Weber, Lars Buesing, Steven Kapturowski, Doina Precup, David Silver, and Nicolas Heess. Value-driven hindsight modelling. Advances in Neural Information Processing Systems, 1112449--1550 2020.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International conference on machine learning, pp. 1352 1361. PMLR, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-poliey maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, pp. 1861-186 1870. Proceedings of Machine Learning Research, 2018.
Danijar Hafner, Kuang-Huc Huci Lee, Ian Fischer, and Picter Abbeel. Deep hicrarchical planning from pixels. Advances in Neural Information Processing Systems, 35:26091 -21004, 2022.
Jean Harb, Tom Schaul, Doina Precup, and Pierre-Lue Bacon. Policy evaluation networks, arXiv preprint arXiv:200..1188 11833, 2020.
Anna Harutyunyan, Peter Vrancx, Picrre-Lue Bacon, Doina Precup, and Ann Nowc. Learning with options that terminate off-policy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Anna Harutyunyan, Will Dabney, Thomas Mesnard, Mohammad Gheshlaghi Azar, Bilal Piot, Nicolas Heess, Hado P van Hasselt, Gregory Wayne, Satinder Singh, Doina Precup, et al. Hindsight credit assignment. Advances in neural information processing systems, 32, 2019.
46

---

Published in Transactions on Machine Learning Research (04/2024)
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAT conference on artificial intelligence, volume 32, 2018.
Donald D Hoffman. The interface theory of perception. Current Directions in Psychological Science, 25(3): 157 161, 2016.
Rein Houthooft, Yuhua Chen, Phillip Isola, Bradly Stadie, Filip Wolski, OpenAI Jonathan Ho, and Pieter Abbeel. Evolved policy gradients. Advances in Neural Information Processing Systems, 31, 2018.
Ronald A Howard. Dynamic programming and Morkow processes. John Wiley, 1960.
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):5223, 2019. ISSN 2041-1723. doi: 00.1038/s41467-019 13073-w. w. URL https: 1ttp///0..1///111710001111110
Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence of stochastic iterative dynamic pro- gramming algorithms. Advances in neural information processing systems, 6, 1993.
Max Jaderberg, Volodymyr Mnih, Wojeiech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. In International Conference on Learning Representations, 2017. URL https://openrevias wwtp:/oounnddddSSd/pppa
Michael Janner, Qiyang Li, and Sergey Levine. Offline reinforcement learning as one big sequence modcling problem. In Advances in Neural Information Processing Systems, 2021.
Dominik Janzing, David Balduzzi, Moritz Grosse Wentrup, and Bernhard Schölkopf. Quantifying causal influences. The Annals Of Statistics, pp.
2013.
Stratton C Jaquette. Markov decision processes with a optimality criterion: Discrete time. The Annals of Statistics, 1(3):496-505, 1973.
Minqi Jiang, Edward Grefenstette, and Tim Rockläschel. Prioritized level replay. In International Conference on Machine Learning, pp. 4940-4950. Proceedings of Machine Learning Research, 2021a.
Minqi Jiang, Tim Rocktäschel, and Edward Grefenstette. General intelligence requires rethinking explo- ration. Royal Society Open Science,
2023.
Ray Jiang, Tom Zahavy, Zhongwen Xu, Adam White, Mattco Hessel, Charles Blundell, and Hado Hasselt. Emphatic algorithms for deep reinforcement learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5023 5033. PMLR, 18 24 Jul 2021b. URL press/v139/jiang211 html.
mlr.
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney. Recurrent experience replay in distributed reinforcement learning. In International conference on learning representations, 2019.
Steven Kapturowski, Victor Campos, Ray Jiang, Nemanja Rakicevic, Hado Hasselt, Charles Blundell, and Adria Puigdomenech Badia. Human-level atari 200x faster. In The Eleventh International Conference on Learning Represenlations, 2023. URL https: http///ppp//eeeeeeee/eeeeeeeeeee net/ neet://orumiddddeceyyyHtttt
Michal Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaškowski. Vizdoom: A doom-based ai research platform for visual reinforcement learning. In 2016 IEEE conference on computa- tional intelligence and games (CIG), pp. 1 IEEE, 2016.
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. A survey of zero-shot generalisation in deep reinforcement learning. Journal of Artificial Intelligence Research, 76:201-220 2244, 2023.
47

---

Published in Transactions on Machine Learning Research (04/2024)
Martin Klissarov and Doina Precup. Flexible option learning. Advances in Neural Information Processing Systems, 34:4632-4666 4646, 2021.
Martin Klissarov, Rasool Fakoor, Jonas Mueller, Kavosh Asadi, Taesup Kim, and Alex Smola. Adaptive interest for emphatic reinforcement learning. In Decision Awareness in Reinforcement Learning Workshop at ICML 2022, 2022. URL https://opennrevie http:///ppppaeeeeeee.aeerrrfrrra .etf/forrumiicc222333RRR.
A Harry Klopf. Brain function and adaptive systems: heterostatic theory. Technical Report 133, Air Force Cambridge Research Laboratories. Special Reports, Bedford, Massachusets, 1972.
Petar Kormushev, Sylvain Calinon, and Darwin G Caldwell. Reinforcement learning in robotics: Applications and real-world challenges. Robotics, 2(3):122 148, 2013.
Heinrich Küttler, Nantas Nardelli, Alexander Miller, Roberta Railcanu, Marco Selvatici, Edward Grefen- stelte, and Tim Rocktäschel. The nethack learning environment. Advances in Neurul Information Pro- cessing Systems, 33:7671-7684 2020.
Kennon A Lattal. Delayed reinforcement of operant behavior. Journal of the Experimental Analysis of 139, 2010.
Behavior,
Charline Le Lan, Stephen Tu, Adam Oberman, Rishabh Agarwal, and Marc G Bellemare. On the general- ization of representations in reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 4132-4157. PMLR, 2022.
Kuang-Huei Lee, Ofir Nachum, Mengjiao Yang, Lisa Lee, Daniel Freeman, Winnie Xu, Sergio Guadarrama, lan Fischer, Eric Jang, Henryk Michalewski, et al. Multi-game decision transformers. arXi preprint arXiv:2205 15241, 2022.
Timothy Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.00 02971,, 2015.
Long-Ji Lin. Sel--inpo reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3):293 321, 1992.
Zhouhan Lin, Minwei Feng, Cicoro Nogucira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. A structured self-attentive sentence embedding. In International Conference on Learning Repre- sentations, 2017.
Minghuan Liu, Menghui Zhu, and Weinan Zhang. Goal-conditioned reinforcement, learning: Problems and solutions. arXiv preprint arXiv:2201.0822 2022.
J Luketina, N Nardelli, G Farquhar, J Foerster, J Andreas, E. Grefenstette, S Whiteson, and T Rocktäschel. A survey of reinforcement learning informed by natural language. In Proceedings of the Twenty-Eightt International Joint Conference on Artificial Intelligence, IJCAI 2019, August 10-16 2019, Macao, China. volume 57, pp. 6309 6309-6317. AAAI Press (Association for the Advancement of Artificial Intelligence). 2019.
Jukka Luoma, Sampsa Ruutu, Adelaide Wilcox King, and Henrikki Tikkanen. Time delays, competitive interdependence, and firm performance. Strategic Management Journal, 38(3):506-52) 2017.
A Rupam Mahmood, Huizhen Yu, Martha White, and Richard S Sutton. Emphatic temporal -iffereee learning. ar preprint 1rXiv:1507.01569 2015.
Matheus RF Mendonca, Artur Ziviani, and André MS Barreto. Graph-based skill acquisition for reinforce- ment learning. ACM Computing Surveys (CSUR), 52(1):1 26, 2019.
Thomas Mesnard, Theophane Weber, Fabio Viola, Shantamu Thakoor, Alaa Saade, Anna Harutyunyan, Will Dabncy, Thomas S Stepleton, Nicolas Heess, Arthur Guez, et al. Counterfactual credit assignment in model-free reinforcement learning. In International Conference on Machine Learning, pp. 7654-7664. Proceedings of Machine Learning Research, 2021.
48

---

Published in Transactions on Machine Learning Research (04/2024)
Thomas Mesnard, Wenqi Chen, Alaa Saade, Yunhao Tang, Mark Rowland, Theophane Weber, Clare Lyle, Audrumas Gruslys, Michal Valko, Will Dabney, Georg Ostrovski, Eric Moulines, and Remi Munos. Quan- tile credit assignment. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learn- ing, volume 202 of Proceedings of Machine Learning Research, pp. 11517-4531.. PMLR, 23 23-29 Jul 2023. html.
URL btttps:/proceeeidie .ml.iinnn..........mm..m...... betrgs..mr..prssee.
Donald Michie. Experiments on the mechanization of game-learuing part i. characterization of the model and its parameters. The Computer Journal, 6(3): (23))2222220 236, 1963.
Marvin Minsky, Steps toward artificial intelligence. Proceedings of the IRE, 49(1):8-30 30, 1961. ISSN 00968390.
doi: 10.1109/JPPOO..100 227777.
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bac, et al. Chip placement with deep reinforcement learning. arXiv preprint arXiv:2004.107/3 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglon, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. In Advances in Neural Information Processing Systems, Deep Learning Workshop, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7440):522 533, 2015.
Volodymyy Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Inter- national conference on machine learning, pp. 1928 1937. PMLR, 2016.
Seyed Sajad Mousavi, Michael Schukat, Enda Howley, and Patrick Mannion. Applying q (A)-learning in deep reinforcement learning to play atari games. In AAMAS Adoptive Learning Agents (ALA) Workshop, pp. 6, 2017.
Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Visual rein- forcement learning with imagined goals. Advances in newral information processing systems, 31, 2018.
Suraj Nair, Mohammad Babacizadch, Chelsea Finn, Sergey Levine, and Vikash Kumar. Trass: Time reversal self-supervision. In 2020 IEEE International Conference on Robolics and Aulomalion (ICRA), pp. 115- 121. IEEE, 2020.
Thanh Thi Nguyen and Vijay Janapa Reddi. Deep reinforcement learning for cyber security. IEEE Trans- actions on Neural Networks and Learning Systems, 2021.
Tianwei Ni, Michel Ma, Benjamin Eysenbach, and Pierre- Bacon, When do transformers shine in RL? de- coupling memory from credit assignment. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: http://ppperrreieeeeeettooraraaa met//oorumid-APPGBBBE
net
Chris Nota, Philip Thomas, and Bruno C. Da Silva. Posterior value functions: Hindsight baselines for policy gradient methods. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8238 8247. PMLR, 18 24 Jul 2021. URL https: /ptp:///eccccee...////e mlr. www.speeesssveeee v139/nota2ia. html..
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In International Confer- ence on Machine Learning, pp. 3878 3887. PMLR, 2018
Junhyuk Oh, Matteo Hessel, Wojciech M. Czarnecki, Zhongwen Xu, Hado P van Hasselt, Satinder Singh, and David Silver. Discovering reinforcement learning algorithms. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (ods.), Advances in Neural Information Processing Systems, volume 33, pp. 1060-1070. Curran Associates, Inc., 2020. URL https://proceeete oascea1100ggesss43e/////ee221110 .df..
49

---

Published in Transactions on Machine Learning Research (04/2024)
Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba. Szepesvári, Satinder Singh, Benjamin Van Roy, Richard Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. In International Conference on Learning Representations, 2020. URL https://openreviis wtwpeerreeeee.nne/fouuruaaaaaa met:/forum?iddryyff-kWk..
Rsiao-Ru Pan, Nico Gürtler, Alexander Neitz, and Bernhard Schölkopf. Direct advantage estimation. Ad- vances in Neural Information Processing Systems, 35:11869-11880, 2022.
Jack Parker-Holed Aldo Pacchiano, Krzysztof M Choromanski, and Stephen J Roberts. Effective diversity in population based reinforcement learning. Advances in Newral Information Processing Systems, 33: 18050-18062, 2020.
Shubham Pateria, Budhitama Subagdja, Ah-hwee Tan, and Chai Quek. Hierarchical reinforcement learning: A comprehensive survey. ACM Computing Surveys (CSUR), 54(5):1-33 2021.
Judea Pearl. Causal inference in statistics: An overview. Statistics Surveys, 3:96 1966-14,110 2009.
Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: CambrriggUnnivorstttypeesss 19(2):3, 2000.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6623):990 996, 2022.
Jean Piaget, Margaret Cook, et al. The origins of intelligence in children, volume 8, International Universities Press New York, 1952.
Silviu Pitis. Rethinking the discount factor in reinforcement learning: A decision theoretic approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7949-7956, 2019.
Silviu Pitis, Elliot Creager, and Animesh Garg. Counterfactual data augmentation using locally factored dynamics. Advances in Newral Information Processing Systems, 33:3976 3990, 2020.
Chetan Prakash, Kyle D Stephens, Donald D Hoffman, Manish Singh, and Chris Fields. Fitness beats truth in the evolution of perception. Acta Biotheoretica, 69:319-341 341, 2021.
Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 2000a.
Doina Precup. Temporal abstraction in reinforcement learning. PhD thesis, University of Massachusctts Amherst, 2000b.
Martin L Puterman. Markow decision processes: discrele stochastic dynamic programmingg John Wiley & Sons, 2014.
Martin L Puterman and Moon Chirl Shin. Modified policy iteration algorithus for discounted markov decision problems. Management Science, 24(11):112-11137, 1978.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adríà Puigclomnech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. Imagination- augmented agents for deep reinforcement lcarning. Advances in neural information processing systems. 30, 2017.
Alec Radford, Karthik Narasinhan, Tim Salimans, llya Sutskever, et al. Improving language understanding by generative pre-training. OpenAl blog, 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl 7 blog, 188):9, 2019.
Hazhir Rahmandad, Nelson Repenning, and John Sterman. Effects of feedback delay on learning. System Dynamics Review, 25(4):309 338, 2009.
50

---

Published in Transactions on Machine Learning Research (04/2024)
David Raposo, Sam Ritter, Adam Santoro, Greg Wayne, Theophane Weber, Matt Botvinick, Hado Hasselt, and Francis Song. Synthetic returns for long-term credit assignment. CoRR, 2021.
Paulo Rauber, Avinash Ummadisingu, Filipe Mutz, and Jürgen Schmidhuber. Hindsight policy gradients. In International Conference on Learning Representations, 2019. URL https////operreeee.eeee/eooooo id=Bkg2viA5FQ.
Scott Reed, Konrad Zoina, Emilio Parisotto, Sergio Gomez Colmenarejo, Alexander Novikov, Gabriel Barth- Maron, Mai Gimenez, Yury Sulsky, Jackie Kay, Jost Tobias Springenberg, et al. A generalist agent. arXiv preprint 2rx: 06175, 2022.
Zhizhou Ren, Ruihan Guo, Yuan Zhou, and Jian Peng. Learning long-term reward redistribution via ran- domized return decomposition. In International Conference Learning Representations, 2022. URL https://openrevior
Matthew Riemer, Miao Liu, and Gerald Tesauro. Learning abstract options. Advances nearol information processing systems, 31, 2018.
Mark Rowland, Will Dabney, and Rémi Munos. Adeptive trade-offs in off-policy learning. In International Conference on Artificial Intelligence and Statistics, pp. 34 44. PMLR, 2020.
Mikayel Samvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holder Minqi Jiang, Eric Hambro, Fabio Petroni, Heinrich Kuttler, Edward Grefenstette, and Tim Rocktäschel. Minihack the planet: A sand- box for open-ended reinforcement learning research. In Thirly-fifth Conference Neural Information Processing Systems Datasets and Benchmarks Track (Round 1). 2021. URL https://openrevveew net//
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1312-1333 Lille, France, 07-09 Jul 2015a. mlr PMLR. URL https://proceedding www.mlllprree.. wwt.:pprss/////eere http///////ccaass/////// htmll
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:151.005052 2015b.
Tom Schaul, André Barreto, John Quan, and Georg Ostrovski. The phenomenon of policy churn. ar preprint arXic:2206.0013: 00730, 2022.
Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and its application to the game tetris. Journal of Machine Learning Research, 16649):1699-166, 2015.
Juergen Schmidluber, Reinforcement learning upside down: Don't predict rewards just map them to actions. arXiv preprint 15::::1912028877 2019.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. Newral Networks, 61:85 117, 2015.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering alari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604 600-669, 2020.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. In Proceedings of the International Conference on Learning Representations (ICLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimiza- tion algorithms. arXiv preprint arXiv: 177.. 06347, 2017.
Donald G Schultz. State functions and linear control systems. McGrow-Hir Hill Book Company, 1967.
51

---

Published in Transactions on Machine Learning Research (04/2024)
Minah Seo, Luiz Felipe Vecchietti, Sangkeum Lee, and Dongsoo Har. Rewards prediction-based credit assignment for reinforcement learning with sparse binary rewards. TEEE Access, 7:118776-11877 2019.
Mehran Shakerinava and Siamak Ravanbakhsh. Utility theory for sequential decision making, In International Conference on Machine Learning, pp. 19616-19625. PMLR, 2022.
Clande E. Shannon. Programming computer for playing chess. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 41(314):256 275, 1950.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Dricssche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(758)):4844459) 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, ct al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140--1 1144, 2018.
Satinder Singh, Richard Lewis, and Andrew Barlo. Where do rewards come from. Proceedings of the annual conference of the cognétive science society, pp. 2601 2601-2606. Cognitive Science Society, 2009.
Satinder P Singh and Richard S Sutton. Reinforcement learning with replacing eligibility traces. Machine learning, 22(1):123-158, 1996.
Matthew Smith, Herke Hoof, and Joelle Pineau. An inference-based policy gradient method for learning options. In International Conference on Machine Learning, pp. 4703-4712. PMLR, 2018.
Matthew J Sobel. The variance of discounted markov decision processes. Journal of Applied Probability, 19 (4):794-802, 1982.
Rupesh Kumar Srivastava, Pranav Shyam, Filipe Mutz, Wojciech Jaskowski, and Jürgen Schmidhuber. Training agents using upsido-down reinforcement learning. CoRR, hbs/1912.02877, 2019. URL http: //arxiv.org/abs//1111.. 02877.
Miroslav Strupl, Francesco Faccio, Dylan R Ashley, Jürgen Schmidhuber, and Rupesh Kunar Srivastava. Upside-down reinforcement learning can diverge in stochastic environments with episodic resets. arXiv preprint ar Xiv:22200 06595,, 2022.
Ke Sun, Bei Jiang, and Linglong Kong. How does value distribution in distributional reinforcement learning help optimization? arXiv preprint drXiv:2209.14513 14513, 2022.
Richard S Sutton. Temporal credit assignment in reinforcement learning. PhD thesis, University of Mas- sachusetts, 1984.
Richard S Sutton. Learning predict by the methods of temporal differences. Muchine learning, 3:9 44, 1988.
Richard S. Sutton. The reward hypothesis. http://incomppeeeiddss...e// rewardhypothesis. html, 2004.
ualberta. ca/RLAI/
Richard S Sutton and Andrew G Barto. Reinforcement Learning: an introduction. MIT Press, 2nd edition, 2018. ISBN 9781626239777. URL http://haoonaccccaaaaa..aeeeeear pdf.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181-211 1999.
Richard S Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M Pilarski, Adam White, and Doina Precup. Horde: A scalable real-time architecture for learning knowledge from unsupervised sensori- motor interaction. In The 10th International Conference on Autonomous Agents and Multiagent Systems- Volume 2, pp. 761-768, 2011.
52

---

Published in Transactions on Machine Learning Research (04/2024)
Richard S Sutton, A Rupam Mahmood, and Martha White. An emphatic approach to the problem of off-
policy temporal-difference learning. The Journal of Machine Learning Research, 17(1):2603-2060 2631,, 2016.
Yunhao Tang and Alp Kucukelbir. Hindsight expectation maximization for goal-conditioned reinforcement
learning. In International Conference on Artificial Intelligence and Statistics, pp. 2863 2871. PMLR, 2021.
Emanuel Todorov Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model- control. In International conference on intelligent robots and systems, pp. 5026 5033. LEEE, 2012.
Hado van Hasselt and Richard Sutton. Learning to predict independent of span. ar preprint arXiv:1508. wrXh::550800458, 2015.
Hado van Hasselt and Marco Wicring. Using continuous action spaces to solve discrete problems. In 2009 International Joinl Conference on Neurul Nelworks, pp. 1149 1156. IEEE, 2009.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In Proceedings of the AAAT conference artificial intelligence, volume 30, 2016.
Hado van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Modayil. Deep reinforcement learning and the deadly triad. arXiv preprint arXiv:1822.022 026488 2018.
Hado van Hasselt, Sephora Madjiheurem, Matteo Hessel, David Silver, André Barreto, and Diana Borsa. Expected cligibility traces. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9997-10005, 2021.
Hado P van Hasselt, Matteo Hessel, and John Aslanides. When parametric models in reinforcement learning? Advances in Neural Information Processing Systems, 32, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
David Venuto, Elaine Lau, Doina Precup, and Ofir Nachum. Policy gradients incorporating the future. In International Conference on Learning Representations, 2022. URL sttps://openrevieee htwpppporrrrioeeeoooooonttaaaaaa net/forum?id= EHaUT1m2eHg.
Nino Vieillard, Tadashi Kozuno, Bruno Scherrer, Olivier Pietquin, Rémi Munos, and Matthieu Geist. Lever- age the average: an analysis of kl regularization in reinforcement learning. Advances in Neural Information Processing Systems, 33:12163 12174, 2020a.
Nino Vieillard, Olivier Pietquin, and Matthieu Geist. Munchausen reinforcement learning. Advances in Newral Information Processing Systems, 33:4235 1246,226,664 2020b.
Oriol Vinyals, Igor Babuschkin, Junyoung Chung, Michael Mathieu, Max Jaderberg, Wojtek Czarnecki, Andrew Dudzik, Aja Huang, Petko Georgiev, Richard Powell, Timo Ewalds, Dan Horgan, Manuel Kroiss, Ivo Danihelka, John Agapiou, Junhyuk Oh, Valentin Dalibard, David Choi, Laurent Sifre, Yury Sulsky, Sasha Vezhnevets, James Molloy, Trevor Cai, David Budden, Tom Paine, Caglar Gul- cehre, Ziyu Wang, Tobias Pfaff, Toby Pohlen, Dani Yogatama, Julia Cohen, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Chris Apps, Koray Kavukcuoglu, Demis Hassabis, and David Sil- ver. AlphaStar: Mastering the Real-Time Strategy Game StarCraft II. weaerring-eallttee teme-ttmmesseeee seelllltim-ssstateeeeee strategy- game- seeee-ssttrrrata//ae// 2019.
com/blog/
Jianhao Wang, Wenzhe Li, Haozhe Jiang, Guangxiang Zhu, Siyuan Li, and Chongjie Zhang. Offine re- inforcement learning with reverse mosel-based imagination. Advances in Neural Information Processing Systems, 34:29400-29492, 2021.
Tony Tong Wang, Adam Gleave, Nora Belrosc, Tom Tseng, Joseph Miller, Michael Dennis, Yawen Duan, Viktor Pogrebniak, Sergey Levine, and Stuart Russell. Adversarial policies beat professional- go ais. arXiv preprint Xix::2211.00000 200002 2022.
53

---

Published in Transactions on Machine Learning Research (04/2024)
Zhe Wang and Tianzhen Hong. Reinforcement learning for building controls: The opportunities and chal- lenges. Applied Eneryy, 269:115036, 2020.
Ziyu Wang, Victor Bapst, Nicolas Heess, Volodymyr Mnih, Remi Munos, Koray Kavukeuoglu, and Nando de Freitas. Sample efficient actor-critic with experience replay. In International Conference on Learning Representations, 2016a.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995- 2003. PMLR, 2016b.
Christopher J C H Watkins. Learning from delayed rewards. PhD thesis, King's College, Cambridge, United Kingdom, 1989.
Douglas J White. Mean, variance, and probabilistic criteria in finite markov decision processes: A review.
Journal of Optimization Theory and Applications, 56:1- 29, 1988.
Martha White. Unifying task specification in reinforcement learning, In International Conference on Machine Learning, pp. 3742-3750. PMLR, 2017.
Peter Wurman, Samuel Barrett, Kenta Kawamoto, James MacGlashan, Kaushik Subramanian, Thomas J Walsh, Roberto Capobianco, Alisa Devlic, Franziska Eckert, Florian Fuchs, et al. Outracing champion gran turismo drivers with deep reinforcement learning. Nature, 602(7896) :223-)2:222225555 2022.
Zhongwen Xu, Hado P van Hasselt, and David Silver. Mela-gradient reinforcement learning. Advances in neural information processing systems, 31, 2018.
Zhongwen Xu, Hado P van Hasselt, Matteo Hessel, Junhyuk Oh, Satinder Singh, and David Silver. Meta- gradient reinforcement learning with an objective discovered online. Advances in Neural Information Processing Systems, 33:15254 15264, 2020.
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Picter Abbeel, and Yang Gao. Mastering atari games with limited data. Advances in Neural Information Processing Systems, 34:25476-2555 254488,25448, 2021.
Haiyan Yin, Shuicheng YAN, and Zhongwen Xu. Distributional meta-gradient reinforcement learning. The Eleventh International Conference on Learning Representations, 2023. URL https:// met/fforum?'d++LCmmUaaau
Tom Zahavy, Zhongwen Xu, Vivek Veeriah, Matteo Hessel, Junhyuk Oh, Hado van Hasselt, David Silver, and Satinder Singh. Self-tuning deep reinforcement learning. arXiv preprint arXiv:2002. 12928, 2020.
Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et al. Relational deep reinforcement lcarning. arXiv preprinl ar Xiv: 01830, 2018
Shangtong Zhang, Vivek Veeriah, and Shimon Whiteson. Learning retrospective knowledge with reverse reinforcement learning. Advunces in Neural Information Processing Systems, 13:199966-1996 2020.
Qinqing Zheng, Amy Zhang, and Aditya Grover. Online decision transformer. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 27042 27059. PMLR, 17 23 Jul 2022. URL https: //wp://edno.c......mm/om.// mll..mm.......... press/vv62/ wttees//vv2///eeg2222c html.
Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods. Advances in Neural Information Processing Systems, 31, 2018
Zeyu Zheng, Junhyuk Oh, Matteo Hessel, Zhongwen Xu, Manuel Kroiss, Hado van Hasselt, David Silver, and Satinder Singh. What can learned intrinsic rewards capture? In International Conference on Machine Learning, pp. 11436 11446. PMLR, 2020.
54


Reviews:
[{"review_id": "X33tMTDwGH", "reviewer": "Reviewer_icBr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Comments: 1.The paper clearly defines the concept of credit assignments. 2.The paper thinks the action-value function is also a form of credit assignment. But I think it is not true. Learning an immediate reward function that assigns the credit can be called as the credit assignment function. Other forms can not viewed as a valid credit assignment function. 3.The paper does not provide quantitative comparison or analysis of current credit assignment methods. 4.Some definitions that measures the credit assignment function rather than the training performance or value errors.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary: This paper writes a sufficient and detailed survey of temporal credit assignment in Deep Reinforcement Learning. The paper firstly formally defines the MDP, the goal, and the credit assignment function. Then the paper discuss the current assignment functions used in most reinforcement learning algorithms. After that the paper introduces several challenges to assign credit in deep RL: delayed effects due to MDP depth, low action influence due to low MDP density, low action influence due to high MDP breadth, and discuss the relationship with the exploration problem. Then the paper classifies RL methods in \"Time as a heuristic\", \"Decomposing return contributions\", “Conditioning on a predefined set of goals”, \"Modeling transitions as sequences\", \"Planning and learning backwards\", \"Meta-learning proxies for credit\". Then the paper propose some evaluation metrics to evaluate the credit assignment in deep RL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please clarify about the following points:\n1.The paper thinks the action-value function is also a form of credit assignment. But I think it is not true. Learning an immediate reward function that assigns the credit can be called as the credit assignment function. Other forms can not viewed as a valid credit assignment function.\n2.The paper does not provide quantitative comparison or analysis of current credit assignment methods.\n3.Some definitions that measures the credit assignment function rather than the training performance or value errors.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "D55vqj0j12", "reviewer": "Reviewer_n7vN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper surveys a broad spectrum of material. \n* It formulates fundamental questions and proposes a unified view of CAP. This is very useful both for researchers and the people who enter the field of RL.\n* The paper provides food for thought, identifies the gaps in the current state-of-the-art, and organizes them in a list of challenges.\n\nWeaknesses:\n* The paper has several technical errors that are misleading to various degrees, e.g.:\n  * The sum in the definition of $Z_t$ (above eq. (1)) should iterate over $k$. \n  * In eq. (8) the items under the curly bracers should be swapped.\n  * There seems to be an inconsistency in defining GVF and UFVAs in Section 4.5 and Table 2.\n  * Equations (12) and (26) lack the bracer, i.e., $(1 - ...)z$.\n  * The intuition at the end of the paragraph \"Hindsight advantage\" is not clear. Can we have $\\pi(a|s)=0$ and $\\mathbb P_D(a|s,z)>0$? (it is not clear that this is the case by reading Harutyunyan et al., 2019).\n  * Eq. (17) is unclear.\n  * It seems that in the sentence directly preceding eq. (30), there should be \"for all $V$ and $V'$, \\Gamma<1$.\n  * It seems that there should be $\\hat{V^\\pi}$ eq. (30).\n* The paper is long with over 43 pages. Some information is duplicated, and the text, while often easy to read, is quite verbose. \n* The paper includes the Acknowledgments section, where the initials of the main author together with the grant number are provided. Additionally, a 'thank you' is given to a person mentioned by the first and the last name. \n* There are several typos and missing spaces.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper surveys approaches to the credit assignment problem (CAP) in Deep RL and proposes a unifying framework. Three lines of research in CAP are described: (a) action influence quantification, (b) learning of action influence, and (c) evaluation. Challenges and open problems in the field are laid out together with future research directions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the above section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "H23J6rHpbR", "reviewer": "Reviewer_3PaG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The first three sections of the paper are an effective setup for a survey on this topic. Section 4 is an interesting discussion and formalization of credit assignment. Section 5 thoughtfully teases apart different types of challenges for effective credit assignment in MDPs.\n\nUnfortunately, Sections 6 and 7 do not make the best use of these foundations. For example, Table 4 contains some interesting claims about the types of challenges defined in Section 5 that different methods address, but it is unclear to me how this table was constructed and I could not find any reference to the table in the text for further discussion.\n\nThe paper varies significantly in quality and attention to detail across sections. The paper is largely well written up to Section 4. Section 4 is careful about defining common terms such as \"goal\", \"outcome\", \"(action) influence\", and \"(credit) assignment\", while the sections that follow are more ambiguous in their language, particularly around the terms \"value\" and \"return\". It is often unclear to me if these \"values\" and \"returns\" are meant to reference only cumulative or discounted future rewards, and thus only pertain to state value, action value, or advantage credit assignments only or if they are referring to \"values\" and \"returns\" in a more general sense.\n\nThe method descriptions in Section 6 can be effective in that they describe how a method works and how it relates to previously discussed concepts. For example, the RUDDER subsection in Section 6.2 is effective in this way (in spite of some shortcomings, see items in Requested Changes on this subsection). These method descriptions can also be poor in that they do little more than present a reference and a high level description of the algorithm, without highlighting its relationship to credit assignment. For example, the PGIF subsection in Section 6.4.2.\n\nThe summaries at the subsections in Section 6 are confusing. Related, summaries or later parts of the paper may make strong declarative statements that are surprising given the previous content. For example, in the summary of Section 6.2, it states that a measure of action influence is not a satisfactory quantification of credit and cites Section 4.3, but Section 4.3 defines a general notion of assignment that each quantity talked about so far fits within. Another example is in the third paragraph of Section 8.1 where it states that \"we highlighted that current benchmarks are not fit for the purpose\". While \"the purpose\" could be clarified, my sense of the discussion of benchmarks in the previous section were that each benchmark had something different to offer, not that all of them were critically lacking.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper surveys the area of temporal credit assignment in deep reinforcement learning. This paper seeks to organize and compare different types of credit assignment, challenges to credit assignment, methods for learning credit assignment, and credit assignment evaluation procedures from the literature. Toward this end, this paper formalizes notions of action influence and credit assignment, describes desirable properties for an action influence, and organizes contributions by building on these theoretical foundations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please improve Section 6 to explain how each learning method relates or could be combined with each type of assignment described in the previous Section.\n\nPlease improve the summaries in Section 6.\n\nPlease make the paper more consistent across Sections in terms of the claims that are made.\n\nPlease edit the paper to correct typos, improve wording, add missing words, and clarify references.\n\nSome examples in no particular order:\n\n1. At the end of Section 4.1, the last bullet point is missing an \"s\" and a word. I expect is should read \"Section 4.6 distils the properties that existing measure*s* of action influence **exhibit**.\"\n2. There appears to be a hat missing from $V$ in Equation (30).\n3. In the summary of Section 6.2, it is unclear to what \"their\" is referring in the sentence, \"Despite their measure of action influence not being a satisfactory quantification of credit . . .\"\n4. In the last sentence of the summary of Section 6.2, it is unclear to what \"these models\" refers.\n6. In the RUDDER subsection in Section 6.2 just after Equation (20), what is $\\mathcal{M}^*$?\n7. In the RUDDER subsection, you have $g = z^* \\in \\mathbb{R}$ at the end of the sentence as if it's describing an optimal policy but I think you meant to describe the maximum expected return. In addition to this confusion, I do not understand why the symbols $g$ and $z^*$ are used here, especially when $g$ is used for the function that returns the discounted sum of rewards along a trajectory, $d$. I also do not understand how $g$ can generate that output without being an explicit function of $d$.\n8. Section 5.4 is particularly confusing. The second paragraph of Section 5.4 especially contains many typos and awkward wordings.\n9. The first sentence in Section 8.1, \"tree\" -> \"three\".\n\nAll of these issues should be addressed for me to recommend acceptance.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper reviews the Credit Assignment Problem (CAP) in Reinforcement Learning (RL), focusing on Temporal Credit Assignment (CA) in deep RL. It proposes a unified formalism for credit, addresses challenges such as delayed effects, and suggests evaluation protocols. Overall, it provides insights for newcomers and suggests future research directions in the CAP.

The paper has many strong points: clear definitions, comprehensive survey, formulation of fundamental questions, identification of gaps and challenges, effective setup, interesting discussion, and thoughtful analysis.

On the other hand, the reviewers raised several technical and presentation issues, which were partially addressed by the updated version provided by the authors. After reading the new version of the paper, the reviewers feel that some points were not properly fixed (see the message by reviewer 3PaG posted on February 29th).

The authors need to provide a new version of their paper addressing all the open issues.
Decision: Accept (poster)