  The question of how to determine which states and actions are responsible for
a certain outcome is known as the credit assignment problem and remains a
central research question in reinforcement learning and artificial
intelligence. Eligibility traces enable efficient credit assignment to the
recent sequence of states and actions experienced by the agent, but not to
counterfactual sequences that could also have led to the current state. In this
work, we introduce expected eligibility traces. Expected traces allow, with a
single update, to update states and actions that could have preceded the
current state, even if they did not do so on this occasion. We discuss when
expected traces provide benefits over classic (instantaneous) traces in
temporal-difference learning, and show that sometimes substantial improvements
can be attained. We provide a way to smoothly interpolate between instantaneous
and expected traces by a mechanism similar to bootstrapping, which ensures that
the resulting algorithm is a strict generalisation of TD($\lambda$). Finally,
we discuss possible extensions and connections to related ideas, such as
successor features.
