# Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 86 references that are in the map.
- First posted on arXiv 8 Aug 2021.

## Builds on (most cited first, 30 of 31)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates](https://mlsanity.com/paper/1610.00633/) (2016)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [Top-K Off-Policy Correction for a REINFORCE Recommender System](https://mlsanity.com/paper/1812.02353/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Counterfactual Off-Policy Evaluation with Gumbel-Max Structural Causal Models](https://mlsanity.com/paper/1905.05824/) (2019)
- [An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning](https://mlsanity.com/paper/1503.04269/) (2015)
- [Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning](https://mlsanity.com/paper/1909.05850/) (2019)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Estimating Dynamic Treatment Regimes in Mobile Health Using V-learning](https://mlsanity.com/paper/1611.03531/) (2016)
- [Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settings](https://mlsanity.com/paper/2001.04515/) (2020)
- [CoinDICE: Off-Policy Confidence Interval Estimation](https://mlsanity.com/paper/2010.11652/) (2020)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Inference and Uncertainty Quantification for Noisy Matrix Completion](https://mlsanity.com/paper/1906.04159/) (2019)
- [Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting](https://mlsanity.com/paper/2006.10460/) (2020)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Dynamic Causal Effects Evaluation in A/B Testing with a Reinforcement Learning Framework](https://mlsanity.com/paper/2002.01711/) (2020)
- [Reanalysis of Variance Reduced Temporal Difference Learning](https://mlsanity.com/paper/2001.01898/) (2020)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Statistical inference using SGD](https://mlsanity.com/paper/1705.07477/) (2017)
- [Steady State Analysis of Episodic Reinforcement Learning](https://mlsanity.com/paper/2011.06631/) (2020)
- [Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory](https://mlsanity.com/paper/1906.06781/) (2019)
- [Statistical Inference for Online Decision Making via Stochastic Gradient Descent](https://mlsanity.com/paper/2010.07341/) (2020)

## Built on by (most cited first, 26 of 26)

- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [Testing Stationarity and Change Point Detection in Reinforcement Learning](https://mlsanity.com/paper/2203.01707/) (2022)
- [High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization](https://mlsanity.com/paper/2401.09346/) (2024)
- [Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descent](https://mlsanity.com/paper/2212.14883/) (2022)
- [Statistical Inference with Stochastic Gradient Methods under φ-mixing Data](https://mlsanity.com/paper/2302.12717/) (2023)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Did we personalize? Assessing personalization by an online reinforcement learning algorithm using resampling](https://mlsanity.com/paper/2304.05365/) (2023)
- [Distributional Shift-Aware Off-Policy Interval Estimation: A Unified Error Quantification Framework](https://mlsanity.com/paper/2309.13278/) (2023)
- [Advancing Retail Data Science: Comprehensive Evaluation of Synthetic Data](https://mlsanity.com/paper/2406.13130/) (2024)
- [Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning](https://mlsanity.com/paper/2110.15501/) (2021)
- [Online Estimation and Inference for Robust Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2310.02581/) (2023)
- [Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation](https://mlsanity.com/paper/2510.12375/) (2025)
- [Doubly Inhomogeneous Reinforcement Learning](https://mlsanity.com/paper/2211.03983/) (2022)
- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [Asymptotic Analysis of Sample-averaged Q-learning](https://mlsanity.com/paper/2410.10737/) (2024)
- [Statistical Inference in Reinforcement Learning: A Selective Survey](https://mlsanity.com/paper/2502.16195/) (2025)
- [CLT and Edgeworth Expansion for m-out-of-n Bootstrap Estimators of The Studentized Median](https://mlsanity.com/paper/2505.11725/) (2025)
- [A Two-armed Bandit Framework for A/B Testing](https://mlsanity.com/paper/2507.18118/) (2025)
- [Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System](https://mlsanity.com/paper/2406.04374/) (2024)
- [Deep Spectral Q-learning with Application to Mobile Health](https://mlsanity.com/paper/2301.00927/) (2023)
- [An Online Bootstrap for Time Series](https://mlsanity.com/paper/2310.19683/) (2023)
- [Generalized Fitted Q-Iteration with Clustered Data](https://mlsanity.com/paper/2510.03912/) (2025)
- [Model-based Bootstrap of Controlled Markov Chains](https://mlsanity.com/paper/2605.12410/) (2026)
- [Nonparametric Variance-Penalized Actor-Critic: Statistical Inference for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2609.14327/) (2026)

## Abstract (arXiv)

The recent emergence of reinforcement learning has created a demand for robust statistical inference methods for the parameter estimates computed using these algorithms. Existing methods for statistical inference in online learning are restricted to settings involving independently sampled observations, while existing statistical inference methods in reinforcement learning (RL) are limited to the batch setting. The online bootstrap is a flexible and efficient approach for statistical inference in linear stochastic approximation algorithms, but its efficacy in settings involving Markov noise, such as RL, has yet to be explored. In this paper, we study the use of the online bootstrap method for statistical inference in RL. In particular, we focus on the temporal difference (TD) learning and Gradient TD (GTD) learning algorithms, which are themselves special instances of linear stochastic approximation under Markov noise. The method is shown to be distributionally consistent for statistical inference in policy evaluation, and numerical experiments are included to demonstrate the effectiveness of this algorithm at statistical inference tasks across a range of real RL environments.