# Model-based Bootstrap of Controlled Markov Chains

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 9 of its 38 references that are in the map.
- First posted on arXiv 12 May 2026.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)
- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 9 of 9)

- [Bootstrapping Fitted Q-Evaluation for Off-Policy Inference](https://mlsanity.com/paper/2102.03607/) (2021)
- [Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluation](https://mlsanity.com/paper/2007.13609/) (2020)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Uncertainty Quantification and Exploration for Reinforcement Learning](https://mlsanity.com/paper/1910.05471/) (2019)
- [On Applications of Bootstrap in Continuous Space Reinforcement Learning](https://mlsanity.com/paper/1903.05803/) (2019)
- [Nearly Optimal Latent State Decoding in Block MDPs](https://mlsanity.com/paper/2208.08480/) (2022)
- [Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity](https://mlsanity.com/paper/2211.07092/) (2022)
- [Bootstrap Model Aggregation for Distributed Statistical Learning](https://mlsanity.com/paper/1607.01036/) (2016)
- [Central Limit Theorems for Transition Probabilities of Controlled Markov Chains](https://mlsanity.com/paper/2508.01517/) (2025)

## Abstract (arXiv)

We propose and analyze a model-based bootstrap for transition kernels in finite controlled Markov chains (CMCs) with possibly nonstationary or history-dependent control policies, a setting that arises naturally in offline reinforcement learning (RL) when the behavior policy generating the data is unknown. We establish distributional consistency of the bootstrap transition estimator in both a single long-chain regime and the episodic offline RL regime. The key technical tools are a novel bootstrap law of large numbers (LLN) for the visitation counts and a novel use of the martingale central limit theorem (CLT) for the bootstrap transition increments. We extend bootstrap distributional consistency to the downstream targets of offline policy evaluation (OPE) and optimal policy recovery (OPR) via the delta method by verifying Hadamard differentiability of the Bellman operators, yielding asymptotically valid confidence intervals for value and Q-functions. Experiments on the RiverSwim problem show that the proposed bootstrap confidence intervals (CIs), especially the percentile CIs, outperform the episodic bootstrap and plug-in CLT CIs, and are often close to nominal (50%, 90%, 95%) coverage, while the baselines are poorly calibrated at small sample sizes and short episode lengths.