Expected Eligibility Traces

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(λ). Finally, we discuss possible extensions and connections to related ideas, such as successor features. Appropriate credit assignment has long been a major research topic in artificial intelligence (Minsky 1963). To make effective decisions and understand the world, we need to accurately associate events, like rewards or penalties, to relevant earlier decisions or situations. This is important both for learning accurate predictions, and for making good decisions. Temporal credit assignment can be achieved with repeated temporal-difference (TD) updates (Sutton 1988). One-step TD updates propagate information slowly: when a surprising value is observed, the state immediately preceding it is updated, but no earlier states or decisions are updated. Multistep updates (Sutton 1988; Sutton and Barto 2018) propagate information faster over longer temporal spans, speeding up credit assignment and learning. Multi-step updates can be implemented online using eligibility traces (Sutton 1988), without incurring significant additional computational expense, even if the time spans are long; these algorithms have computation that is independent of the temporal span of the prediction (van Hasselt and Sutton 2015) . Traces provide temporal credit assignment, but do not assign credit counterfactually to states or actions that could have led to the current state, but did not do so this time.