# To bootstrap or to rollout? An optimal and adaptive interpolation

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

## 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.

## 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, 14 of 14)

- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency](https://mlsanity.com/paper/2209.13075/) (2022)
- [Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms](https://mlsanity.com/paper/1411.0169/) (2014)
- [On the Statistical Benefits of Temporal Difference Learning](https://mlsanity.com/paper/2301.13289/) (2023)
- [Effective Multi-step Temporal-Difference Learning for Non-Linear Function Approximation](https://mlsanity.com/paper/1608.05151/) (2016)
- [Adaptive Lambda Least-Squares Temporal Difference Learning](https://mlsanity.com/paper/1612.09465/) (2016)
- [Instance-Dependent Confidence and Early Stopping for Reinforcement Learning](https://mlsanity.com/paper/2201.08536/) (2022)
- [Performance of NPG in Countable State-Space Average-Cost RL](https://mlsanity.com/paper/2405.20467/) (2024)
- [Learning to Mix n-Step Returns: Generalizing lambda-Returns for Deep Reinforcement Learning](https://mlsanity.com/paper/1705.07445/) (2017)
- [TD or not TD: Analyzing the Role of Temporal Differencing in Deep Reinforcement Learning](https://mlsanity.com/paper/1806.01175/) (2018)
- [Demystifying the Recency Heuristic in Temporal-Difference Learning](https://mlsanity.com/paper/2406.12284/) (2024)

## 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.