# Multi-step Off-policy Learning Without Importance Sampling Ratios

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2017.

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

- [A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning](https://mlsanity.com/paper/2104.13844/) (2021)
- [A Deep Reinforcement Learning Approach to Marginalized Importance Sampling with the Successor Representation](https://mlsanity.com/paper/2106.06854/) (2021)
- [The Statistical Benefits of Quantile Temporal-Difference Learning for Value Estimation](https://mlsanity.com/paper/2305.18388/) (2023)
- [Self-Imitation Learning via Generalized Lower Bound Q-learning](https://mlsanity.com/paper/2006.07442/) (2020)
- [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)
- [Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation](https://mlsanity.com/paper/2405.21043/) (2024)
- [Continual Auxiliary Task Learning](https://mlsanity.com/paper/2202.11133/) (2022)
- [Trajectory-Aware Eligibility Traces for Off-Policy Reinforcement Learning](https://mlsanity.com/paper/2301.11321/) (2023)
- [Learning Expected Emphatic Traces for Deep RL](https://mlsanity.com/paper/2107.05405/) (2021)
- [Demystifying the Recency Heuristic in Temporal-Difference Learning](https://mlsanity.com/paper/2406.12284/) (2024)
- [An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environment](https://mlsanity.com/paper/2109.05110/) (2021)
- [An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Task](https://mlsanity.com/paper/2106.00922/) (2021)
- [K-Nearest-Neighbor Resampling for Off-Policy Evaluation in Stochastic Control](https://mlsanity.com/paper/2306.04836/) (2023)
- [Importance Sampling Placement in Off-Policy Temporal-Difference Methods](https://mlsanity.com/paper/2203.10172/) (2022)
- [Analysis of Off-Policy Multi-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2402.15781/) (2024)
- [Two-Step Q-Learning](https://mlsanity.com/paper/2407.02369/) (2024)
- [Improving the Efficiency of Off-Policy Reinforcement Learning by Accounting for Past Decisions](https://mlsanity.com/paper/2112.12281/) (2021)
- [Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.08941/) (2025)

## Abstract (arXiv)

To estimate the value functions of policies from exploratory data, most model-free off-policy algorithms rely on importance sampling, where the use of importance sampling ratios often leads to estimates with severe variance. It is thus desirable to learn off-policy without using the ratios. However, such an algorithm does not exist for multi-step learning with function approximation. In this paper, we introduce the first such algorithm based on temporal-difference (TD) learning updates. We show that an explicit use of importance sampling ratios can be eliminated by varying the amount of bootstrapping in TD updates in an action-dependent manner. Our new algorithm achieves stability using a two-timescale gradient-based TD update. A prior algorithm based on lookup table representation called Tree Backup can also be retrieved using action-dependent bootstrapping, becoming a special case of our algorithm. In two challenging off-policy tasks, we demonstrate that our algorithm is stable, effectively avoids the large variance issue, and can perform substantially better than its state-of-the-art counterpart.