Research map / Reinforcement learning / MDPs and planning
Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation
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 combining a target network with over-parameterized linear TD yields convergence for off-policy bootstrapping, including with normalized importance sampling on trajectory data, and extends to Q-learning.
Problem
Off-policy bootstrapped value estimation with function approximation (the deadly triad) diverges, and over-parameterization alone or target networks alone do not guarantee convergence.
Approach
Combine a hard-updated target network with over-parameterized linear features (d > number of observed state-action pairs) so the TD fixed point is independent of the data distribution; the target-network update makes the iteration contractive, and NIS-corrected next-action transitions on full trajectories remove the remaining condition.
Key results
- On Baird's counterexample, over-parameterized target TD converges while TD diverges (spectral metric 1.12 for TD vs 1-3.8e-3 for target TD).
- Over-parameterized target TD with NIS correction on Four Room reaches zero EMSBE, while plain IS-corrected variant diverges.
- Expected-update error bound: ||Phi theta* - q||_inf <= 2/(1-gamma) inf_theta ||Phi theta - q||_inf.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add a target network to TD | TD · Two-state counterexample | convergence rate metric: 1.12 -> 1- 3.8\mathrm{e}{-3} | Helped |
| add a target network to over-parameterized TD (ablation) | OTD · Baird's counterexample | value prediction error | Helped |
| use over-parameterization without a target network (ablation) | TD · Baird's counterexample | convergence | Hurt |
| use a target network without over-parameterization (ablation) | TD · off-policy expected updates | convergence | Hurt |
| use ordinary importance sampling instead of normalized importance sampling (ablation) | OTTD with trajectory data · Four Room | value prediction error | Hurt |
| increase the dataset size with NIS correction (ablation) | OTTD with NIS correction · Four Room | value prediction error | Helped |
| use NIS correction instead of sampling the next action from the target policy (ablation) | OTTD with trajectory data · Four Room | value prediction error | No clear effect |
Surprising findings
- Over-parameterization alone (OTD) still diverges on Baird's counterexample, and a target network alone does not guarantee convergence in the under-parameterized case.
Limitations
- Restricted to linear function approximation; extension to neural networks left open.
- Convergence for OTTD on non-trajectory data still requires an infinity-norm condition on NM^dagger.
- Truncated continuing-task trajectories introduce extra error; only an MSE-based bound is given.
Experimental setup
Datasets: Baird's counterexample Four-room task (episodic, random behaviour policy)
Benchmarks: Baird's counterexample Four-room task Two-state counterexample
Metrics: maximal value prediction error infinity-norm value error EMSBE convergence rate metric lim ||C||^(1/t)
Baselines: TD over-parameterized TD residual minimization Baird RM GTD2 TDC LSTD
Builds on: temporal difference learning residual minimization Q-learning normalized importance sampling
Closest papers by meaning
- Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction (NeurIPS 2019 · similarity 0.91)
- Long-Horizon Q-Learning: Accurate Value Learning via n-Step Inequalities (NeurIPS 2026 · similarity 0.89)
- A Generalized Bootstrap Target for Value-Learning, Efficiently Combining Value and Feature Predictions (AAAI 2022 · similarity 0.89)
- A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning (NeurIPS 2025 · similarity 0.88)
- Horizon Adaptive Offline Policy Learning via Value Stitching (NeurIPS 2026 · similarity 0.87)
- Flattening Hierarchies with Policy Bootstrapping (NeurIPS 2025 · similarity 0.86)
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.