mlsanityData to 14 Oct 2026

To bootstrap or to rollout? An optimal and adaptive interpolation

arXiv 2411.09731 ↗First posted 14 Nov 2024cs.LG math.ST stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Bootstrapping and rollout are two fundamental principles for value function estimation in reinforcement learning (RL). We introduce a novel class of Bellman operators, called subgraph Bellman operators, that interpolate between bootstrapping and rollout methods. Our estimator, derived by solving the fixed point of the empirical subgraph Bellman operator, combines the strengths of the bootstrapping-based temporal difference (TD) estimator and the rollout-based Monte Carlo (MC) methods. Specifically, the error upper bound of our estimator approaches the optimal variance achieved by TD, with an additional term depending on the exit probability of a selected subset of the state space. At the same time, the estimator exhibits the finite-sample adaptivity of MC, with sample complexity depending only on the occupancy measure of this subset. We complement the upper bound with an information-theoretic lower bound, showing that the additional term is unavoidable given a reasonable sample size. Together, these results establish subgraph Bellman estimators as an optimal and adaptive framework for reconciling TD and MC methods in policy evaluation.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 14 of its 50 references that are in the map. First posted on arXiv 14 Nov 2024.

Builds on

14 of 50 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Demystifying the Recency Heuristic in Temporal-Difference Learning18 Jun
  2. 2024Performance of NPG in Countable State-Space Average-Cost RL30 May

Other references · 12

  1. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  2. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  3. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  4. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 17
  5. 2022Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiencycited by 10
  6. 2014Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histogramscited by 9
  7. 2023On the Statistical Benefits of Temporal Difference Learningcited by 8
  8. 2016Effective Multi-step Temporal-Difference Learning for Non-Linear Function Approximationcited by 7
  9. 2016Adaptive Lambda Least-Squares Temporal Difference Learningcited by 5
  10. 2022Instance-Dependent Confidence and Early Stopping for Reinforcement Learningcited by 5
  11. 2017Learning to Mix n-Step Returns: Generalizing lambda-Returns for Deep Reinforcement Learningcited by 4
  12. 2018TD or not TD: Analyzing the Role of Temporal Differencing in Deep Reinforcement Learningcited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Model-based Bootstrap of Controlled Markov Chains
  2. 2026Model-based Bootstrap for Offline Policy Evaluation in Tabular Reinforcement Learning
  3. 2026Offline Policy Evaluation via Mixed Bellman Residuals and Adaptive Critic Representations
  4. 2022A Generalized Bootstrap Target for Value-Learning, Efficiently Combining Value and Feature Predictions
  5. 2025Bellman Calibration for V-Learning in Offline Reinforcement Learning
  6. 2021Bootstrapping Fitted Q-Evaluation for Off-Policy Inference
  7. 2026Reusing Rollouts under Policy Lag: Prefix-Normalized Policy Optimization for LLM Reinforcement Learning
  8. 2026Cross-Rollout Bellman Closure for Long-Horizon Agentic Reinforcement Learning