Research map / Reinforcement learning / Policy gradient and actor-critic
The surprising efficiency of temporal difference learning for rare event prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that least-squares TD (LSTD) estimates rare-event quantities (mean first passage time, committor) with relative accuracy using polynomially many transitions in state count n, while Monte Carlo requires exponentially many.
Problem
Policy evaluation for rare events in Markov chains: MC estimators need data scaling with the inverse of the (exponentially small) target value and exponentially long trajectories, so relative accuracy is costly.
Approach
Derives a CLT for the tau-step LSTD estimator and an upper bound on its relative asymptotic variance in terms of path-connectivity quantities Q^tau(k,l) (not condition numbers or escape times); under minorizing-graph and sub-Gaussian transition tail assumptions, the bound is polynomial (n^3) in the number of states even when the MC error is exponential.
Key results
- For the mean first passage time and committor on a 1D chain, LSTD (tau=1) relative MSE grows more slowly than n^3, while MC relative MSE grows exponentially in n.
- Under stated assumptions, the relative asymptotic variance of LSTD is bounded by (C/alpha) e^{(log c)^2/beta} n^3 (or with factor tau when R is nonzero on D).
- Committor u(2) is shown to be at most on the order of exp(-n/(4pi)), so MC relative error explodes exponentially.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LSTD with τ=1 instead of Monte Carlo | Mean first passage time estimation · Mean first passage time | relative error scaling with n: grows more slowly than n^3; grows exponentially fast with n | Helped |
| Use LSTD with τ=1 instead of Monte Carlo | Committor estimation · Committor | relative error scaling with n: grows more slowly than n^3; grows exponentially fast with n | Helped |
| Increase lag time from τ=1 to τ≈30 (ablation) | LSTD · Mean first passage time and committor, n=40 | maximum relative asymptotic variance: τ≈30 | Helped |
| Initialize from the invariant distribution conditioned within D instead of uniformly on D (ablation) | LSTD · Mean first passage time and committor | maximum relative asymptotic variance: grow exponentially with n | Hurt |
| Initialize from the invariant distribution conditioned within D instead of uniformly on D (ablation) | LSTD · Mean first passage time and committor, n=80 | estimator defined: n=80 | Hurt |
Surprising findings
- With uniform initial distribution, LSTD relative MSE grows more slowly than n^3 empirically, despite the exponentially large escape times.
- When initial distribution is the conditioned invariant distribution, LSTD errors grow exponentially and the estimator can fail to be defined for n=80.
Limitations
- Analysis restricted to the tabular setting with finite state Markov chains; generalization to continuous spaces and function approximation left to future work.
- Assumes independently drawn trajectories rather than correlated samples from a single trajectory.
- Assumptions (minorizing graph connectivity, sub-Gaussian tails) are stated for the specific chain class and may not hold generally.
Experimental setup
Metrics: relative asymptotic variance relative mean squared error
Baselines: Monte Carlo estimator
Builds on: least-squares temporal difference learning Markov state models dynamical Galerkin approximation
Closest papers by meaning
- Discerning Temporal Difference Learning (AAAI 2024 · similarity 0.89)
- On Double Descent in Reinforcement Learning with LSTD and Random Features (ICLR 2024 · similarity 0.88)
- An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks (ICML 2024 · similarity 0.87)
- Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes (NeurIPS 2024 · similarity 0.87)
- Statistical Efficiency of Distributional Temporal Difference Learning (NeurIPS 2024 · similarity 0.87)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.