Research map / Reinforcement learning / Policy gradient and actor-critic
From Past to Future: Rethinking Eligibility Traces
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.
Introduces bidirectional value functions combining past (backward) and future (forward) expected returns, derives Bellman equations and online updates, and uses them (BiTD variants) for policy evaluation on a chain domain where they outperform TD(λ) in some settings.
Problem
Eligibility traces in TD(λ) with nonlinear function approximation use outdated gradients, causing updates to previous states that run counter to the backward-view intuition, and policy evaluation can be slow.
Approach
Defines a bidirectional value function (sum of backward value of past discounted rewards and forward value of future returns), derives its Bellman equation and online TD/MC update rules, and parameterizes forward, backward and bidirectional heads of one network so that learning the auxiliary heads helps learn the forward value.
Key results
- All BiTD variants reach lower MSTDE than TD(λ) for a given number of samples in the chain domain, with hyperparameters tuned by AUC.
- TD(λ) performance deteriorates monotonically as λ increases and is best at λ=0, while BiTD-FR is better at intermediate λ, peaking around λ=0.4.
- The paper proves the backward and bidirectional Bellman operators are contraction mappings in the tabular setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BiTD-FR instead of TD(λ) | Policy evaluation with nonlinear approximation · Random chain domain | MSTDE | Helped |
| Use BiTD-BiR instead of TD(λ) | Policy evaluation with nonlinear approximation · Random chain domain | MSTDE | Helped |
| Use BiTD-FBi instead of TD(λ) | Policy evaluation with nonlinear approximation · Random chain domain | MSTDE | Helped |
| Increase λ above 0 | TD(λ) · Random chain domain | MSTDE | Hurt |
| Use intermediate λ values rather than λ = 0 (ablation) | BiTD-FR · Random chain domain | MSTDE | Helped |
| Directly approximate the forward value function (BiTD-FR or BiTD-FBi) rather than indirectly (BiTD-BiR) (ablation) | BiTD · Random chain domain | MSTDE | Helped |
Surprising findings
- TD(λ) with nonlinear function approximation can update prior states in a direction opposite to the intended one because of outdated eligibility-trace gradients.
- The bidirectional operator's contraction rate is worse than the forward rate γ, per the paper's own worst-case analysis.
Limitations
- Experiments are limited to a small synthetic 9-state chain with a single-layer network.
- Only on-policy prediction is studied; off-policy and control extensions are left to future work.
- Worst-case convergence rate of the bidirectional operator is worse than that of the standard forward operator.
Experimental setup
Datasets: 9-state random chain domain (synthetic)
Benchmarks: 9-state random chain domain
Metrics: MSTDE error area under curve
Baselines: TD(λ) Monte Carlo
Builds on: TD(λ) expected eligibility traces Boyan's chain
Closest papers by meaning
- Expected Eligibility Traces (AAAI 2021 · similarity 0.90)
- Policy Learning for Balancing Short-Term and Long-Term Rewards (ICML 2024 · similarity 0.83)
- On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation (NeurIPS 2024 · similarity 0.83)
- Adaptive Exploration for Multi-Reward Multi-Policy Evaluation (ICML 2025 · similarity 0.83)
- Towards Assessing and Benchmarking Risk-Return Tradeoff of Off-Policy Evaluation (ICLR 2024 · similarity 0.83)
- Learning the Optimal Policy for Balancing Short-Term and Long-Term Rewards (NeurIPS 2024 · similarity 0.83)
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.