Technical Summary: Model-based Bootstrap of Controlled Markov Chains

Problem Statement

The paper addresses the challenge of statistical inference for finite Controlled Markov Chains (CMCs) in settings where the behavior policy generating the data may be nonstationary or history-dependent. This scenario is prevalent in offline reinforcement learning (RL), where data is collected by an unknown policy $\pi_b$ that does not necessarily satisfy stationarity or Markovianity assumptions.

Existing bootstrap methods for Markov chains often rely on stationarity or specific mixing conditions that do not hold for general CMCs with history-dependent controls. Furthermore, standard plug-in confidence intervals (CIs) based on Central Limit Theorems (CLTs) require covariance estimation, which can degrade finite-sample performance. The authors identify two open problems:

1. Can a model-based bootstrap be developed for finite CMCs without requiring stationarity or Markovianity of the control policy?
2. Can the distributional consistency of such a bootstrap estimator be established and extended to downstream RL tasks like Off-Policy Evaluation (OPE) and Optimal Policy Recovery (OPR)?

Methodology

Model and Data Setup

The authors consider a finite CMC $\{(X_i, A_i)\}_{i \ge 0}$ with state space $\mathcal{S}$ and action space $\mathcal{A}$. The transition kernel is $M(a)_{s,t} = P(X_{i+1}=t | X_i=s, A_i=a)$. The observed offline dataset $\mathcal{D}_n$ consists of $K$ episodes of fixed length $T$ (where $n=KT$), generated by an unknown behavior policy $\pi_b$. The policy $\pi_b$ is allowed to be nonstationary and history-dependent.

From $\mathcal{D}_n$, the authors compute:

• Count-based empirical transition estimator: $\hat{M}(a)_{s,t} = N(a)_{s,t} / N(a)_s$.
• Empirical behavior policy: $\hat{\pi}_b(a|s) = N(a)_s / N_s$.

Model-Based Bootstrap Procedure

The proposed method constructs a bootstrap CMC $\{(X^*_i, A^*_i)\}_{i \ge 0}$ using the empirical transition kernel $\hat{M}$ and the empirical behavior policy $\hat{\pi}_b$.

1. Initialization: For each bootstrap replicate $j$, the process starts at the observed initial state of the original episode, $X^{*(k,j)}_0 = X^{(k)}_0$.
2. Simulation: Transitions are generated sequentially by sampling actions $A^{*(k,j)}_i \sim \hat{\pi}_b(\cdot | X^{*(k,j)}_i)$ and next states $X^{*(k,j)}_{i+1} \sim \hat{M}(A^{*(k,j)}_i)_{X^{*(k,j)}_i, \cdot}$.
3. Estimation: From the simulated dataset $\mathcal{D}^*_n$, a bootstrap transition estimator $\hat{M}^*$ is computed.
4. Replication: This process is repeated $B$ times to obtain bootstrap replicates $\hat{M}^{*(1)}, \dots, \hat{M}^{*(B)}$.

Downstream Applications

The bootstrap is applied to two downstream targets:

• Off-Policy Evaluation (OPE): Estimating value functions $V_\pi$ and Q-functions $Q_\pi$ for a fixed target policy $\pi$ by solving Bellman equations with $\hat{M}$ and $\hat{M}^*$.
• Optimal Policy Recovery (OPR): Estimating optimal value functions $V_\star$ and $Q_\star$ by solving optimal Bellman equations with $\hat{M}$ and $\hat{M}^*$.

Confidence intervals are constructed using the empirical quantiles of the bootstrap replicates (percentile CI) or via pivot methods.

Key Theoretical Contributions

1. Bootstrap Distributional Consistency

The paper establishes the first distributional consistency results for model-based bootstraps in finite CMCs with potentially nonstationary or history-dependent policies.

• Single-Chain Regime ($K=1, T \to \infty$): Theorem 1 proves that conditional on the data $\mathcal{D}_n$, $\sqrt{n} \text{vec}(\hat{M}^* - \hat{M})$ converges in distribution to a Gaussian limit $N(0, \bar{\Lambda})$, matching the asymptotic distribution of the original estimator $\sqrt{n} \text{vec}(\hat{M} - M)$.
• Episodic Regime ($T$ fixed, $K \to \infty$): Proposition 1 extends this result to the episodic setting by embedding the episodes into a single chain via pseudo-transitions. It confirms that the bootstrap remains consistent even when episodes are separated by resets.

Technical Tools:

• A novel Bootstrap Law of Large Numbers (LLN) for visitation counts ($N^*_s/n \to p_s$ a.s.).
• A novel application of the Martingale Central Limit Theorem (CLT) for bootstrap transition increments, utilizing weak mixing conditions (Assumptions 1–3) to handle the dependence structure.

2. Validity for OPE and OPR

Proposition 2 extends the distributional consistency to the value and Q-function estimators using the Delta Method.

• The authors verify the Hadamard differentiability of the Bellman operators with respect to the transition block matrix.
• For OPE, the bootstrap replicates of $V_\pi$ and $Q_\pi$ converge to the same Gaussian limits as the original estimators.
• For OPR, under a non-degeneracy condition (strictly positive gap between optimal and suboptimal actions), the bootstrap replicates of $V_\star$ and $Q_\star$ also achieve distributional consistency.

Experimental Results

The authors evaluate the finite-sample performance on the RiverSwim problem ($S=6, A=2$), a benchmark known for difficult exploration due to imbalanced visitation frequencies and near-degenerate optimal policies.

• Setup: Comparisons were made against the episodic bootstrap (Hao et al., 2021) and plug-in CLT CIs (Zhu et al., 2024; Su et al., 2026) across various sample sizes ($n$) and episode lengths ($T$).
• Findings:
  • The proposed model-based bootstrap percentile CIs substantially outperform baselines, achieving near-nominal coverage (e.g., 0.48–0.54 for 50%, 0.87–0.94 for 90%, 0.92–0.97 for 95%) in well-sampled regimes ($n \ge 500$).
  • Baselines (episodic bootstrap and plug-in CLT) exhibit systematic undercoverage, particularly at small sample sizes and short episode lengths.
  • The episodic bootstrap fails completely at $n=50$ when $T \ge 50$ (collapsing to zero coverage) because a single episode eliminates bootstrap variation.
  • Performance is weakest for rarely visited state-action pairs (near state 6) and short horizons ($T=10$), consistent with the theoretical constraints of asymptotic normality and non-degeneracy.

Significance and Limitations

Significance:
The paper provides a rigorous theoretical foundation for using model-based bootstraps in offline RL, specifically addressing the gap where behavior policies are nonstationary or history-dependent. It demonstrates that such bootstraps yield asymptotically valid confidence intervals for both transition kernels and downstream RL targets without requiring explicit covariance estimation.

Limitations and Future Directions (as stated by the authors):

• Reward Function: The analysis assumes a known reward function. While the authors note validity likely holds if the reward estimate converges, finite-sample effects of reward estimation error are not analyzed.
• State-Action Space: The current results are limited to finite state-action spaces. Extension to function approximation or continuous spaces is left for future work.
• Asymptotic Regimes: The episodic analysis assumes $T$ is fixed and $K \to \infty$. The consistency of the bootstrap in the regime where $K$ is fixed ($K>1$) and $T \to \infty$ remains an open question.
• Non-Stationary Policies: While the theory accommodates non-stationary policies, the numerical experiments primarily used stationary behavior policies; further experiments with non-stationary policies are suggested.