# The surprising efficiency of temporal difference learning for rare event prediction

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 5 of its 34 references that are in the map.
- First posted on arXiv 27 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Inexact iterative numerical linear algebra for neural network-based spectral estimation and rare-event prediction](https://mlsanity.com/paper/2303.12534/) (2023)
- [On the Statistical Benefits of Temporal Difference Learning](https://mlsanity.com/paper/2301.13289/) (2023)

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

- [Deep Learning for Markov Chains: Lyapunov Functions, Poisson's Equation, and Stationary Distributions](https://mlsanity.com/paper/2508.16737/) (2025)
- [Path-Coupled Bellman Flows for Distributional Reinforcement Learning](https://mlsanity.com/paper/2605.08253/) (2026)
- [An exact multiple-time-step variational formulation for the committor and the transition rate](https://mlsanity.com/paper/2509.03539/) (2025)
- [Is Backpropagation Optimal? When Synthetic Gradients Improve Sample Efficiency](https://mlsanity.com/paper/2605.27946/) (2026)
- [General Value Functions for Remaining Useful Life and Failure-Mode Prediction](https://mlsanity.com/paper/2607.22268/) (2026)
- [Machine learning kinetics from molecular dynamics data](https://mlsanity.com/paper/2609.17736/) (2026)
- [Retimed Bellman Flows: Escaping the Impossible Triangle of Velocity Bootstrapping](https://mlsanity.com/paper/2609.32828/) (2026)

## Abstract (arXiv)

We quantify the efficiency of temporal difference (TD) learning over the direct, or Monte Carlo (MC), estimator for policy evaluation in reinforcement learning, with an emphasis on estimation of quantities related to rare events. Policy evaluation is complicated in the rare event setting by the long timescale of the event and by the need for relative accuracy in estimates of very small values. Specifically, we focus on least-squares TD (LSTD) prediction for finite state Markov chains, and show that LSTD can achieve relative accuracy far more efficiently than MC. We prove a central limit theorem for the LSTD estimator and upper bound the relative asymptotic variance by simple quantities characterizing the connectivity of states relative to the transition probabilities between them. Using this bound, we show that, even when both the timescale of the rare event and the relative accuracy of the MC estimator are exponentially large in the number of states, LSTD maintains a fixed level of relative accuracy with a total number of observed transitions of the Markov chain that is only polynomially large in the number of states.