# Improving the Efficiency of Off-Policy Reinforcement Learning by Accounting for Past Decisions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 23 Dec 2021.

## Builds on (most cited first, 7 of 7)

- [Safe and Efficient Off-Policy Reinforcement Learning](https://mlsanity.com/paper/1606.02647/) (2016)
- [Sample Efficient Actor-Critic with Experience Replay](https://mlsanity.com/paper/1611.01224/) (2016)
- [Q(λ) with Off-Policy Corrections](https://mlsanity.com/paper/1602.04951/) (2016)
- [Adaptive Trade-Offs in Off-Policy Learning](https://mlsanity.com/paper/1910.07478/) (2019)
- [Multi-step Off-policy Learning Without Importance Sampling Ratios](https://mlsanity.com/paper/1702.03006/) (2017)
- [Revisiting Peng's Q(λ) for Modern Reinforcement Learning](https://mlsanity.com/paper/2103.00107/) (2021)
- [On Generalized Bellman Equations and Temporal-Difference Learning](https://mlsanity.com/paper/1704.04463/) (2017)

## Abstract (arXiv)

Off-policy learning from multistep returns is crucial for sample-efficient reinforcement learning, particularly in the experience replay setting now commonly used with deep neural networks. Classically, off-policy estimation bias is corrected in a per-decision manner: past temporal-difference errors are re-weighted by the instantaneous Importance Sampling (IS) ratio (via eligibility traces) after each action. Many important off-policy algorithms such as Tree Backup and Retrace rely on this mechanism along with differing protocols for truncating ("cutting") the ratios ("traces") to counteract the excessive variance of the IS estimator. Unfortunately, cutting traces on a per-decision basis is not necessarily efficient; once a trace has been cut according to local information, the effect cannot be reversed later, potentially resulting in the premature truncation of estimated returns and slower learning. In the interest of motivating efficient off-policy algorithms, we propose a multistep operator that permits arbitrary past-dependent traces. We prove that our operator is convergent for policy evaluation, and for optimal control when targeting greedy-in-the-limit policies. Our theorems establish the first convergence guarantees for many existing algorithms including Truncated IS, Non-Markov Retrace, and history-dependent TD(λ). Our theoretical results also provide guidance for the development of new algorithms that jointly consider multiple past decisions for better credit assignment and faster learning.