# Expected Eligibility Traces

arXiv: https://arxiv.org/abs/2007.01839 · HTML: https://mlsanity.com/paper/2007.01839/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2020.

## Built on by (most cited first, 27 of 27)

- [Learning Successor States and Goal-Dependent Values: A Mathematical Viewpoint](https://mlsanity.com/paper/2101.07123/) (2021)
- [Streaming Deep Reinforcement Learning Finally Works](https://mlsanity.com/paper/2410.14606/) (2024)
- [Maximum State Entropy Exploration using Predecessor and Successor Representations](https://mlsanity.com/paper/2306.14808/) (2023)
- [An Information-Theoretic Perspective on Credit Assignment in Reinforcement Learning](https://mlsanity.com/paper/2103.06224/) (2021)
- [Deep Policy Gradient Methods Without Batch Updates, Target Networks, or Replay Buffers](https://mlsanity.com/paper/2411.15370/) (2024)
- [Would I have gotten that reward? Long-term credit assignment by counterfactual contribution analysis](https://mlsanity.com/paper/2306.16803/) (2023)
- [Emphatic Algorithms for Deep Reinforcement Learning](https://mlsanity.com/paper/2106.11779/) (2021)
- [The Nature of Temporal Difference Errors in Multi-step Distributional Reinforcement Learning](https://mlsanity.com/paper/2207.07570/) (2022)
- [Learning Expected Emphatic Traces for Deep RL](https://mlsanity.com/paper/2107.05405/) (2021)
- [Beyond Uniform Credit Assignment: Selective Eligibility Traces for RLVR](https://mlsanity.com/paper/2605.05965/) (2026)
- [Selective Credit Assignment](https://mlsanity.com/paper/2202.09699/) (2022)
- [Hindsight-DICE: Stable Credit Assignment for Deep Reinforcement Learning](https://mlsanity.com/paper/2307.11897/) (2023)
- [Towards model-free RL algorithms that scale well with unstructured data](https://mlsanity.com/paper/2311.02215/) (2023)
- [From Past to Future: Rethinking Eligibility Traces](https://mlsanity.com/paper/2312.12972/) (2023)
- [Adaptive Pairwise Weights for Temporal Credit Assignment](https://mlsanity.com/paper/2102.04999/) (2021)
- [Predecessor Features](https://mlsanity.com/paper/2206.00303/) (2022)
- [Off-Beat Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2205.13718/) (2022)
- [Graph Backup: Data Efficient Backup Exploiting Markovian Transitions](https://mlsanity.com/paper/2205.15824/) (2022)
- [Sequence Compression Speeds Up Credit Assignment in Reinforcement Learning](https://mlsanity.com/paper/2405.03878/) (2024)
- [CADENT: Gated Hybrid Distillation for Sample-Efficient Transfer in Reinforcement Learning](https://mlsanity.com/paper/2602.02532/) (2026)
- [Temporal Imbalance of Positive and Negative Supervision in Class-Incremental Learning](https://mlsanity.com/paper/2603.02280/) (2026)
- [Revisiting Adam for Streaming Reinforcement Learning](https://mlsanity.com/paper/2605.06764/) (2026)
- [Investigating Action Encodings in Recurrent Neural Networks in Reinforcement Learning](https://mlsanity.com/paper/2605.16318/) (2026)
- [A Generalized Bootstrap Target for Value-Learning, Efficiently Combining Value and Feature Predictions](https://mlsanity.com/paper/2201.01836/) (2022)
- [Marginalized Operators for Off-policy Reinforcement Learning](https://mlsanity.com/paper/2203.16177/) (2022)
- [Stacked Universal Successor Feature Approximators for Safety in Reinforcement Learning](https://mlsanity.com/paper/2409.04641/) (2024)
- [Intentional Updates for Streaming Reinforcement Learning](https://mlsanity.com/paper/2604.19033/) (2026)

## Abstract (arXiv)

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.