Model-based Bootstrap of Controlled Markov Chains
Authors: Ziwei Su, Imon Banerjee, Diego Klabjan
Summary
The authors develop a bootstrap method for estimating uncertainty in finite-state Markov chains with control (important for offline reinforcement learning when you don't know the data-collection policy). Classical bootstrap theory assumes fixed distributions, but in RL the policy can be nonstationary or history-dependent. They prove the bootstrap transition estimator is distributionally consistent in both single-trajectory and episodic settings, using a novel bootstrap law of large numbers for state visitation counts and a martingale central limit theorem for transition increments. This consistency extends to downstream tasks like policy evaluation and optimal policy recovery, yielding valid confidence intervals.
Main takeaways:
- Standard bootstrap theory doesn't cover controlled Markov chains with unknown, possibly nonstationary behavior policies (common in offline RL)
- The authors prove bootstrap distributional consistency for transition probabilities in both long-chain and episodic regimes
- Key tools: a bootstrap LLN for visitation counts and a martingale CLT for transition increments
- The method extends to policy evaluation and optimal policy recovery via the delta method, giving asymptotically valid confidence intervals
- Experiments show the bootstrap CIs often achieve nominal coverage and outperform plug-in CLT and episodic bootstrap baselines
Relevance
Tangential — relevant only if I ever need rigorous uncertainty quantification in RL settings. The episodic structure and behavior-policy uncertainty loosely echo my work on persona-conditioned behavior (different system prompts = different "policies"), but the connection is abstract.
Threat model
Potential threat/caveat for clean result "Fine-tuning one persona on a two-marker chunk and another on the start marker plants the end marker at every donor answer's end, not chained to the start (LOW confidence)": this item discusses evaluation.
Abstract
arXiv:2605.12410v1 Announce Type: new Abstract: 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.