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