mlsanityData to 7 Oct 2026

Model-based Bootstrap of Controlled Markov Chains

arXiv 2605.12410 ↗First posted 12 May 2026stat.ML cs.LG math.OCcited by 0

On the map: Offline RL and imitation learning from data → Offline RL algorithms

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.

Key facts. No citing papers in the map yet (data through 7 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.

Builds on

9 of 38 references.

Closest ancestors · 1

Same direction, newest first

  1. 2021Bootstrapping Fitted Q-Evaluation for Off-Policy Inference6 Feb

Other references · 8

  1. 2020Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluationcited by 28
  2. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  3. 2019Uncertainty Quantification and Exploration for Reinforcement Learningcited by 11
  4. 2019On Applications of Bootstrap in Continuous Space Reinforcement Learningcited by 9
  5. 2022Nearly Optimal Latent State Decoding in Block MDPscited by 5
  6. 2022Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexitycited by 5
  7. 2016Bootstrap Model Aggregation for Distributed Statistical Learningcited by 4
  8. 2025Central Limit Theorems for Transition Probabilities of Controlled Markov Chainscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2022Bootstrapped Transformer for Offline Reinforcement Learning
  2. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learning
  3. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimation
  4. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation
  5. 2022Conservative Bayesian Model-Based Value Expansion for Offline Policy Optimization
  6. 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data
  7. 2023The In-Sample Softmax for Offline Reinforcement Learning
  8. 2022Regularizing a Model-based Policy Stationary Distribution to Stabilize Offline Reinforcement Learning