Model-based Bootstrap of Controlled Markov Chains

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Model-based Bootstrap of Controlled Markov Chains

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neuralnetworks

machine learning, deep learning, neural networks

Model-based Bootstrap of Controlled Markov Chains

arXiv:2605.12410v1 [stat.ML] 12 May 2026

Ziwei Su Department of Industrial Engineering and Management Sciences Northwestern University Evanston, IL 60208, USA [email protected] Imon Banerjee Department of Industrial Engineering and Management Sciences Northwestern University Evanston, IL 60208, USA [email protected] Diego Klabjan Department of Industrial Engineering and Management Sciences Northwestern University Evanston, IL 60208, USA [email protected]

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.

Introduction

The bootstrap—first proposed by Efron [1979]—quickly became a cornerstone of modern statistical inference. Even when analytic variance formulas are available, bootstrap methods may deliver sharper finite-sample confidence intervals (CIs) with improved coverage; see Hall [2013, p. 14]. Despite these advantages, existing bootstrap approaches face two important limitations in the reinforcement learning setting: (i) bootstrap methods for Markov transition matrices remain comparatively sparse, and (ii) existing approaches are not designed to handle the non-stationarity that arises naturally in reinforcement learning. This limitation is particularly relevant in offline reinforcement learning (RL), where the control policy (behavior policy) that generates the offline data may be nonstationary Preprint.

and history-dependent. To address this gap, we propose a new model-based bootstrap method for transition kernels in finite CMCs with possibly nonstationary or history-dependent control policies. To set the stage, we introduce some notation. Assume that the state process {Xi }i≥0 takes values in a finite state space S with |S| = S, and the action process {A i }i≥0 takes values in a finite action space A with |A| = A. A CMC is a paired state-action process (Xi , Ai ) i≥0 ; conditioned on Ai , the state sequence {Xi } follows a Markov transition kernel M , where (a)

Ms,t := P (Xi+1 = t | Xi = s, Ai = a) for all time points i, s, t ∈ S, and a ∈ A [Borkar, 1991]. We observe an offline dataset Dn = (k) (k) (k) (Xi , Ai , Xi+1 ) : k = 1, . . . , K, i = 0, . . . , T − 1 of K episodes generated by an unknown behavior policy πb , each of length T , such that n = KT . Note that K is allowed to be 1 and the policy πb may be nonstationary and history-dependent. (k) P (a) (k) (k) (a) We compute from Dn the counts Ns,t := = s, Ai = a, Xi+1 = t , Ns := i,k 1 Xi P (a) P (a) t Ns,t , and Ns := a Ns . We use the counts to compute the count-based empirical transition (a)

(a)

estimator M̂s,t := Ns,t /Ns

(a)

and the empirical behavior policy π̂b (a | s) := Ns /Ns .

Model-based Bootstrap: We now describe the proposed model-based bootstrap method. Denote (a) (a) the block matrices stacking the entries Ms,t and M̂s,t by M and M̂, respectively. The bootstrap CMC {(Xi∗ , A∗i )}i≥0 has the empirical transition kernel M̂ and the empirical behavior policy π̂b . ∗(k) ∗(k) ∗(k) We generate the bootstrap dataset Dn∗ = (Xi , Ai , Xi+1 ) : k = 1, . . . , K, i = 0, . . . , T − 1 from the bootstrap CMC with the same episodic structure as Dn , and compute the bootstrap ∗(k) P ∗(a) ∗(a) ∗(a) ∗(a) ∗(k) transition estimator M̂s,t := Ns,t /Ns from Dn∗ , where Ns,t := i,k 1 Xi = s, Ai = P ∗(a) ∗(a) ∗(k) := t Ns,t . We denote the block transition matrix stacking the entries a, Xi+1 = t and Ns ∗(a)

M̂s,t by M̂∗ . We repeat the bootstrap B times independently to obtain B bootstrap replicates M̂∗(1) , . . . , M̂∗(B) . We describe two downstream applications (OPE, OPR) in offline infinite-horizon discounted RL. In OPE, for a fixed target policy π, we substitute M̂ into the Bellman equations to obtain plug-in estimators V̂π and Q̂π of the value function Vπ and action-value function Qπ , respectively. We then ∗(j) ∗(j) substitute M̂∗(j) in place of M̂ to obtain bootstrap counterparts V̂π and Q̂π . In OPR, we solve the optimal Bellman equations under M̂ to obtain the plug-in estimators V̂⋆ and Q̂⋆ of the optimal value function V⋆ and optimal action-value function Q⋆ , respectively. We then substitute M̂∗(j) in ∗(j) ∗(j) place of M̂ to obtain bootstrap counterparts V̂⋆ and Q̂⋆ . We compute 100(1 − α)% CIs for Vπ , Qπ , or V⋆ , Q⋆ from the empirical α/2 and 1 − α/2 quantiles of their B bootstrap replicates. The focus of this paper shall be to establish distributional consistency of M̂∗ in two settings: the single-chain regime (K = 1, T → ∞) in Theorem 1, and the episodic offline-RL regime (T √ fixed, K → ∞) in Proposition 1. In both settings, conditional on Dn , n vec(M̂∗ − M̂) converges √ in distribution to the same Gaussian limit as n vec(M̂ − M). Proposition 2 extends this to OPE and OPR targets via the delta method. We validate the finite-sample performance of our proposed model-based bootstrap CIs on the RiverSwim problem, where the proposed model-based bootstrap percentile CIs achieve near-nominal coverage while baselines systematically undercover. We now briefly summarize the key contributions of this paper. • Bootstrap distributional consistency. To the best of our knowledge, we establish the first distributional consistency result for the proposed model-based bootstrap in finite CMCs with possibly nonstationary or history-dependent control policies. Theorem 1 covers the singlechain regime (K = 1, T → ∞) and Proposition 1 covers the episodic offline-RL regime √ (T fixed, K → ∞). In both regimes, we establish that conditional on Dn , n vec(M̂∗ − M̂) √ converges in distribution to the same Gaussian law as n vec(M̂ − M) given in Su et al. [2026, Corollary 1]. The proof hinges on a novel bootstrap law of large numbers (LLN) ∗(a) (a) Ns /n → ps a.s. and a novel use of the martingale CLT for the bootstrap transition increments. (See Section 4.2.) 2

• Bootstrap validity for OPE and OPR. In Proposition 2, we are the first one to extend bootstrap distributional consistency to the downstream RL targets Vπ , Qπ , V⋆ and Q⋆ with non-stationary or history-dependent behavior policies. For OPE, we establish that √ √ conditional on Dn , n(V̂π∗ − V̂π ) and n(Q̂∗π − Q̂π ) converge in distribution to the √ √ same Gaussian limits as n(V̂π − Vπ ) and n(Q̂π − Qπ ), respectively, given in Su √ et al. [2026, Theorem 2]. For OPR, we establish that conditional on Dn , n(V̂⋆∗ − V̂⋆ ) √ converges in distribution to the same Gaussian limit as n(V̂⋆ − V⋆ ) given in Su et al. [2026, Theorem 3]. The proof exploits the delta method by verifying Hadamard differentiability (see Appendix D.2) of the Bellman operators with respect to the transition block matrix. (See Section 4.3.) • Finite-sample coverage on RiverSwim. Proposition 2 guarantees the asymptotic validity of the proposed model-based bootstrap CIs for OPE and OPR. In the setting of Zhu et al. [2024], we validate the model-based bootstrap CIs empirically on the RiverSwim problem [Strehl and Littman, 2004]. In a coverage study with B = 1000 bootstrap replicates and Nreps = 1000 Monte Carlo replications, the model-based bootstrap CIs, especially the percentile CI, substantially outperform the episodic bootstrap and plug-in CLT CIs across the OPE and OPR tasks considered. The percentile CI attains near-nominal coverage at nominal 50% (about 0.48–0.54), 90% (about 0.87–0.94), and 95% (about 0.92–0.97) in the better-sampled regimes, notably for OPE and for OPR with T ∈ {50, 100} at n ≥ 500. (See Section 5.) The rest of the paper is organized as follows. Section 2 reviews background and related work. Section 3 formalizes the problem setup and introduces the bootstrap formally. Section 4 states the main theoretical results. Section 5 presents the numerical experiments. Section 6 concludes the paper.

Background and Related Work

The practice of using CLTs for statistical inference, such as for Markov chains and controlled Markov chains [Billingsley, 1961, Zhu et al., 2024, Su et al., 2026], is well established in the literature. These plug-in CIs, however, require covariance estimation, and the resulting errors degrade finitesample CI coverage. The bootstrap addresses this: the intuitive appeal, computational simplicity, and better performance in complex models or nonstandard error structure of the bootstrap [Hall and Padmanabhan, 1992] lead to its widespread use in modern statistical inference [Modayil and Kuipers, 2004, Han and Liu, 2016, Nakkiran et al., 2020]. The applications of the bootstrap span sparse principal component analysis [Babamoradi et al., 2013, Rahoma et al., 2021], time-series forecasting [Ruiz and Pascual, 2002], econometric and financial inference [Horowitz, 2019, Gonçalves et al., 2023], and clustering and classification [Jedra et al., 2023, Jain and Moreau, 1987]. Directly relevant to this paper, bootstrap methods are widely applied in Markov chains [Kulperger and Rao, 1989, Athreya and Fuh, 1992]. Closest in spirit to this paper, Horowitz [2003] introduces a model-based bootstrap for stationary Markov chains by resampling from an estimated transition kernel under geometric mixing and a Cramér-type moment condition, while Bertail and Clémençon [2006] develops a regenerative block bootstrap for Harris recurrent chains via Nummelin splitting, requiring explicit identification of a minorization condition and an accessible small set. However, these methods do not provide guarantees for the finite CMC setting with possibly nonstationary or history-dependent control policies. RL is another domain where bootstrap methods are widely applied [Krishnamurthy, 2016, Faradonbeh et al., 2019, Ramprasad et al., 2023, Banerjee, 2023, Banerjee et al., 2025, Banerjee and Chakrabarty, 2025]. For OPE, Kostrikov and Nachum [2020] applies Efron’s bootstrap to empirical transition tuples treated as i.i.d. draws from a stationary occupancy distribution. This requires a stationary behavior policy and ignores within-episode dependence. Hanna et al. [2017] proposes model-based bootstrap methods that learn transition dynamics from offline data, simulate trajectories under the target policy using the learned model, and bootstrap trajectory-level cumulative rewards to construct high-confidence lower bounds on policy value. This approach does not establish distributional consistency of the bootstrap estimator. Hao et al. [2021] establishes bootstrap validity for a finitehorizon episodic bootstrap via fitted Q-evaluation, under the assumption that a large number of independent i.i.d. episodes are available. This assumption does not cover the finite CMC setting with 3

possibly nonstationary or history-dependent control policies, and the episodic bootstrap can be poorly calibrated when the number of episodes is small, which brings us to the following open problems. Open problems. We address two open problems in the theory of bootstrap for finite CMCs: (i) Is it possible to develop a model-based bootstrap for finite CMCs that does not require stationarity or Markovianity of the control policy? (ii) Can we then establish distributional consistency of the bootstrap transition estimator, then lift this result to common RL tasks like OPE and OPR? We move on to formally state the problem and introduce the model-based bootstrap method.

Problem Statement

In order to formalize our results, we introduce some notation. We consider a finite CMC {(Xi , Ai )}i≥0 with finite state space S and finite action space A, with S = |S| and A = |A|. All random variables are defined on a filtered probability space (Ω, F, F, P), where F := {Fj }j≥0 , Fj := σ(H0j ) is a filtration with Fj ⊂ F, and Hpj := {(Xi , Ai )}ji=p denotes the history from time p (a)

to j. The environment dynamics are governed by an unknown transition kernel Ms,t = P(Xi+1 = t | Xi = s, Ai = a) for s, t ∈ S, a ∈ A. The transition kernel M satisfies the Markov prop (a ) erty Msi ,si i+1 = P (Xi+1 = si+1 | Xi = si , Ai = ai ) = P Xi+1 = si+1 | H0i = H0i , where hi0 := {X0 = s0 , A0 = a0 , . . . , Xi = si , Ai = ai } is the sample history up to time i. For each (a) s ∈ S, let Ms := [Ms,t ]t∈S, a∈A ∈ RS×A , and let M := [M1 , . . . , MS ]⊤ ∈ RSA×S be the block (a)

transition matrix stacking Ms,t entries. We observe K episodes of fixed length T generated by an unknown behavior policy πb , which may be (k) (k) (k) nonstationary and history-dependent. The observed offline dataset is Dn = (Xi , Ai , Xi+1 ) : k = 1, . . . , K, i = 0, . . . , T − 1 , where n = KT . For the episodic regime, we consider T to be fixed and asymptotics are in K → ∞. From Dn we construct the count-based empirical transition estimator and the empirical behavior policy (a)

(a)

M̂s,t := (a)

where Ns,t :=

(a)

Ns,t

π̂b (a | s) :=

, (a)

(k) (a) 1 Xi(k) = s, A(k) = a, Xi+1 = t , Ns := i

i,k

Ns , Ns

(3.1)

P (a) (a) t Ns,t , and Ns := a Ns .

The empirical block transition matrix M̂ := [M̂1 , . . . , M̂S ]⊤ ∈ RSA×S , where M̂s := (a) [M̂s,t ]t∈S, a∈A , is defined analogously to M. 3.1

Model-based Bootstrap

We now formally introduce the model-based bootstrap method for finite CMCs. We consider the bootstrap CMC {(Xi∗ , A∗i )}i≥0 with empirical transition kernel M̂ and empirical behavior policy π̂b . To generate B bootstrap replicates, we first compute M̂ and π̂b via (3.1). In the j-th replicate, we simulate K episodes of length T from the bootstrap CMC: episode k starts at the ∗(k,j) (k) observed initial state X0 := X0 and transitions are generated sequentially by sampling action ∗(k,j)

∗(k,j)

∼ π̂b (· | Xi

)

i ) and next state Xi+1 ∼ M̂ ∗(k,j) for i = 0, . . . , T − 1. We obtain the Xi ,· ∗(j) ∗(k,j) ∗(k,j) ∗(k,j) bootstrap dataset Dn := (Xi , Ai , Xi+1 ) : k = 1, . . . , K, i = 0, . . . , T −1 as a result.

∗(j)

∗(a,j)

We then use each Dn to compute the bootstrap transition estimator M̂s,t := Ns,t /Ns , ∗(k,j) P P ∗(a,j) ∗(a,j) ∗(k,j) ∗(k,j) ∗(a,j) where Ns,t := i,k 1 Xi = s, Ai = a, Xi+1 = t and Ns := t Ns,t . For ∗(j)

each s ∈ S, let M̂s

∗(a,j)

:= [M̂s,t

∗(j)

]t∈S, a∈A , and let M̂∗(j) := [M̂1

∗(j) ⊤

, . . . , M̂S

] be the j-th

∗(a,j)

bootstrap block transition matrix stacking M̂s,t entries. We repeat this process independently for ∗(1) j = 1, . . . , B to obtain B bootstrap replicates M̂ , . . . , M̂∗(B) . Remark 1. The total bootstrap computational cost is O(Bn) = O(BKT ), linear in dataset size n and number of bootstrap replicates B. 4

We now turn to the formal statements of our main results.

Main Theoretical Results

The goal of this section is to establish our main results: distributional consistency of the model-based bootstrap in finite CMCs for the bootstrap transition estimator M̂ ∗ and, via the delta method, for the bootstrap plug-in value and Q-function estimators. We begin by introducing some standard assumptions. 4.1

Assumptions

The three assumptions below control, respectively, the frequency of return visits to each state–action pair, the rate of mixing of the paired state–action process {(Xi , Ai )}i≥0 , and the positivity of the limiting state–action visitation frequencies. Together they underpin the CLT for the empirical transition estimator established by Su et al. [2026] and ensure that the bootstrap chain inherits the same asymptotic properties. For every (s, a) ∈ S × A, we recursively define the hitting and return times to state–action pair (s, a) as follows. (1) Definition 1 (Hitting and Return Times). The first hitting time to (s, a) is τs,a := min{i > 0 : Xi = s, Ai = a}. For i ≥ 2, the i-th return time is n o (i) τs,a := min k > 0 : XPi−1 τ (j) +k = s, APi−1 τ (j) +k = a . j=1

s,a

j=1

s,a

Assumption 1 requires the conditional expected return time to grow at most sublinearly in the visit index. Assumption Growth). For any (s, a) ∈ S × A, there exists β ∈ (0, 1) h 1 (Sublinear Return-Time i (i)

such that E τs,a FPi−1 τ (p) ≤ Ti a.s., Ti = O(iβ ). p=1

s,a

Our next assumption is on the rate of mixing. We define the weak η̄-mixing coefficient for the CMC {(Xi , Ai )} as follows. Definition 2 (Weak η̄-Mixing Coefficient). For i < j ≤ n, T ⊆ (S × A)n−j+1 , s1 , s2 ∈ S, and a1 , a2 ∈ A, let i−1 ηi,j (T , s1 , s2 , a1 , a2 , hi−1 = hi−1 0 , n) := P (Xj , Aj , . . . , Xn , An ) ∈ T | Xi = s1 , Ai = a1 , H0 0

− P (Xj , Aj , . . . , Xn , An ) ∈ T | Xi = s2 , Ai = a2 , H0i−1 = hi−1 . 0

The weak η̄-mixing coefficient for the CMC is η̄i,j (n) :=

sup T ,s1 ,s2 ,a1 ,a2 ,hi−1 , 0 P Xi =s1 ,Ai =a1 ,H0i−1 =hi−1 >0, 0 P Xi =s2 ,Ai =a2 ,H0i−1 =hi−1 >0 0

( (

ηi,j (T , s1 , s2 , a1 , a2 , hi−1 0 , n).

) )

We omit the dependence on n in η̄i,j by convention [Kontorovich and Ramanan, 2008]. The coefficient η̄i,j quantifies the worst-case influence of the state–action pair at time i on the trajectory distribution from time j onward. Assumption 2 imposes a uniform bound on the cumulative decay of η̄-mixing coefficients. Sufficient conditions for Assumption 2 in terms of separate mixing coefficients for the state and action processes are given in Appendix A. Assumption 2 (Weak Mixing). There exists a finite constant C∆ such that ∥∆n ∥ := max1≤i≤n (1 + η̄i,i+1 + · · · + η̄i,n ) ≤ C∆ for all n. We next define the ergodic occupation measure of the CMC as the Cesàro limit of the marginal state–action distributions. (a) Definition 3 (Ergodic Occupation Measure). The ergodic occupation measure of the CMC is ps := P n−1 limn→∞ n1 i=0 P(Xi = s, Ai = a), whenever the limit exists for all (s, a) ∈ S × A. 5

Assumption 3 requires the ergodic occupation measure to exist and be uniformly bounded away from zero. Assumption 3 (Positive Ergodic Occupation Measure). The CMC admits an ergodic occupation (a) measure, and mins,a ps ≥ p0 > 0. 4.2

Bootstrap Distributional Consistency

We now state our main results. Theorem 1 establishes bootstrap distributional consistency for the single long-chain setting; the episodic extension follows as Proposition 1. √ Theorem 1 (Single Chain Bootstrap Distributional Consistency). Let ξ¯ := n vec(M̂∗ − M̂) be the vector of differences between M̂∗ and M̂. Suppose Dn = {(X0 , A0 , X1 ), . . . , (Xn−1 , An−1 , Xn )} is a single trajectory of length n satisfying Assumptions 1–3, and there exists (s0 , a0 ) ∈ S × A with (a0 ) Ms0 ,s 0 > 0. Then, for P-almost every sequence of datasets (Dn )n≥1 , conditional on Dn , ξ¯ =

√

n vec(M̂∗ − M̂) − → N (0, Λ̄), as n → ∞.

The elements of Λ̄ are given by Λ̄sat, s′ a′ t′ , which denotes the covariance between the (s − 1)SA + ¯ Value Λ̄sat, s′ a′ t′ has the (a − 1)S + t-th and the (s′ − 1)SA + (a′ − 1)S + t′ -th elements of ξ. (a) (a) (a) 1 ′ ′ ′ expression Λ̄sat, s′ a′ t′ := 1 (s, a) = (s , a ) (a) 1{t = t } Ms,t − Ms,t Ms,t′ . ps

Proof sketch. The complete proof is given in Appendix C; the supporting lemmas are collected in Appendix B. We sketch the three main steps here. Step 1 (Bootstrap LLN). The pivotal intermediate result, established formally as Lemma 7 in Ns∗(a) E[Ns∗(a) |Dn ] Ns∗(a) · . We show that the = ∗(a) n n E[Ns |Dn ] ∗ first term converges to 1 a.s. This requires ∥∆n ∥ to be eventually bounded, which we establish in (a) Lemma 5 in Appendix B.3. The second term converges to ps a.s. by Lemma 6 in Appendix B.4. ∗(a)

Appendix B.5, is Ns

a.s.

(a)

/n −−→ ps . We write

Step 2 (Decomposition). For each (s, a, t), write Sn∗,sat := √

n−1 X

1 (a)

n ps

√

∗(a)

(a)

n(M̂s,t − M̂s,t ) = Sn∗,sat + Rn∗,sat , where

(a) ∗ 1{Xi∗ = s, A∗i = a, Xi+1 = t} − M̂s,t 1{Xi∗ = s, A∗i = a}

i=0

is the leading martingale sum, and Rn∗,sat :=

− ∗(a)

∗(a)

n−1 1 1 X (a) ∗ ∗ ∗ ∗ ∗ √ 1 {X = s, A = a, X = t}− M̂ 1 {X = s, A = a} . s,t i i i+1 i i (a) n i=0 ps (a) a.s.

By Step 1, n/N√ − 1/ps −−→ 0. We show that the sum in Rn∗,sat has conditional variance O(n), s and divided by n it is OP (1). By the Slutsky’s theorem, Rn∗,sat = oP (1), and it suffices to analyze Sn∗,sat . Step 3 (Conditional Martingale CLT). We show the sum Sn∗,sat is a martingale difference array under joint filtration Fn,i := σ(Dn , X0∗ , A∗0 , . . . , Xi∗ , A∗i ) and P. Then, we show that the Lindeberg condition holds for all large enough n, the predictable quadratic variation converges a.s. to Λ̄sat,sat (a) (a) via Lemma 7, and M̂s,t → Ms,t a.s. We then apply the martingale CLT [Hall and Heyde, 1980, d

Corollary 3.1] conditioned on Dn , yielding Sn∗,sat − → N (0, Λ̄sat,sat ). The multivariate statement follows by the Cramér–Wold theorem [Cramér and Wold, 1936]. √ Remark 2. Λ̄ is the asymptotic covariance of n vec(M̂ − M) given in Su et al. [2026, Corollary 1]. We now move to the episodic setting. Offline RL datasets are almost always episode-structured, arising from an environment that resets between episodes under a behavior policy that may be nonstationary or history-dependent across episodes. Theorem 1 does not directly cover this structure, as the episodes are separated by resets and do not form a single uninterrupted CMC. 6

(k) (k) (k) Here, we observe an offline dataset Dn = (Xi , Ai , Xi+1 ) : k = 1, . . . , K, i = 0, . . . , T − 1 of K episodes of fixed length T , such that n = KT . To apply Theorem 1, we embed the episodic data into a single chain by inserting, between episode k and episode k + 1, a pseudo-transition under (k) (k+1) a dummy reset action a† ∈ / A that maps XT to the observed initial state X0 of the next episode. f to denote the resulting transition kernel The extended action space is Ae = A ∪ {a† }, and we use M e We note that no structural restriction is imposed linking X (k+1) to X (k) . on S × A. 0 T ei , A ei , X ei+1 )}n′ −1 , with n′ = K(T + 1) − 1, be the concatenated single-chain Formally, let D̃ := {(X i=0 ei ∈ S and A ei ∈ Ae are given by dataset in the format of Theorem 1, where X e(k−1)(T +1)+j := X (k) , X j

k = 1, . . . , K, j = 0, . . . , T ;

e(k−1)(T +1)+j := A(k) , A j

k = 1, . . . , K, j = 0, . . . , T − 1;

ek(T +1)−1 := a† , A

k = 1, . . . , K − 1.

(a) f, where M fs,t ei , A ei )}i≥0 forms a CMC on S × Ae with transition kernel M The paired process {(X = (a ) (a) † (a† ) f f Ms,t for a ∈ A, and we can take M as any stochastic kernel on S such that Ms,t > 0 for all

s, t ∈ S, since a† -transitions are excluded from M̂. The following proposition extends Theorem 1 to the episodic setting. (k) (k) (k) Proposition 1. Suppose k = 1, . . . , K and let Dn = (Xi , Ai , Xi+1 ) i∈{0,...,T −1} is an offline ei , A ei )} with dataset of K episodes of fixed length T , such that n = KT . Suppose the CMC {(X f satisfies Assumptions 1–3 on S × A, e and there exists (s0 , a0 ) ∈ S × A with transition kernel M (a )

0 Ms0 ,s 0 > 0.

Then, for P-almost every sequence of datasets (Dn )n≥1 , conditional on Dn , √ d n vec(M̂∗ − M̂) − → N (0, Λ̄), as K → ∞ and T fixed. ei , A ei )} are satisfied whenever the individual episodes satisfy Assumptions 1–3. The conditions on {(X More generally, they accommodate policy dependence across episodes, since they are imposed on the concatenated chain rather than on individual episodes. The proof of this proposition can be found in Appendix D.1. ∗(k)

(k)

Remark 3. We initialize each bootstrap episode by setting X0 := X0 , copying the observed start states directly from Dn . Since the initial state distribution may be nonstationary and historydependent, estimating it is both impractical and unnecessary; Proposition 1 confirms that this choice does not affect bootstrap distributional consistency. (a)

Remark 4. We estimate the behavior policy by the one-step empirical estimator π̂b (a | s) = Ns /Ns . Theorem 1 and Proposition 1 confirm this one-step estimate suffices even when πb is nonstationary or (a) history-dependent, as the asymptotic distributions depend on the ergodic occupation measure ps induced by πb rather than its history-dependent structure. We now move to the downstream RL applications of Theorem 1 and Proposition 1. 4.3

Applications to OPE and OPR

We consider downstream RL tasks (OPE and OPR) under the offline infinite-horizon discounted RL setting with a known reward function r : S × A → R. OPE concerns using Dn to estimate the value function Vπ and Q-function Qπ for a fixed stationary target policy π. Let Π = diag(π1 , . . . , πS ) ∈ RS×SA denote the associated policy matrix, where πs := [π(s, 1), . . . , π(s, A)]. Vπ and Qπ are the unique solutions to the Bellman equations [Bertsekas, 2011, Agarwal et al., 2019] Vπ = (I − γΠM)−1 g,

Qπ = (I − γMΠ)−1 r, (4.1) P where 0 < γ < 1 is the discount factor, g(s) := a π(s, a)r(s, a), g := (g(s) : s ∈ S), and r := (r(s, a) : s ∈ S, a ∈ A). 7

OPR concerns using Dn to estimate the optimal policy π⋆ , optimal value function V⋆ and optimal Q-function Q⋆ . The optimal Q-function Q⋆ and value function V⋆ are the unique solutions to the optimal Bellman equations X (a) Q⋆ (s, a) = r(s, a) + γ Ms,t max Q⋆ (t, a′ ), V⋆ (s) = max Q⋆ (s, a), (4.2) ′ t∈S

a ∈A

a∈A

and the optimal policy satisfies π⋆ (s) ∈ arg maxa∈A Q⋆ (s, a) for each s ∈ S. We obtain plug-in estimators V̂π and Q̂π for OPE by replacing M with M̂ in (4.1): V̂π = (I − γΠM̂)−1 g,

Q̂π = (I − γ M̂Π)−1 r.

(4.3) (a)

(a)

For OPR, we obtain plug-in estimators Q̂⋆ , V̂⋆ , and π̂⋆ by solving (4.2) with Ms,t replaced by M̂s,t . We use the bootstrap replicates M̂∗(1) , . . . , M̂∗(B) to obtain bootstrap replicates for OPE and OPR targets as follows. In the j-th replicate, we compute bootstrap plug-in value and Q-function estimators ∗(j) ∗(j) V̂π and Q̂π for OPE by replacing M with M̂∗(j) in (4.1): V̂π∗(j) = (I − γΠM̂∗(j) )−1 g,

Q̂∗(j) = (I − γ M̂∗(j) Π)−1 r. π

(4.4)

∗(j) ∗(j) ∗(j) (a) For OPR, we obtain bootstrap plug-in estimators Q̂⋆ , V̂⋆ , and π̂⋆ by solving (4.2) with Ms,t ∗(a,j) replaced by M̂s,t . We repeat this process independently for j = 1, . . . , B to obtain B bootstrap ∗(j) ∗(j) ∗(j) ∗(j) B replicates V̂π , Q̂π , V̂⋆ , Q̂⋆ . j=1

We construct CIs for any coordinate of Vπ from the B bootstrap replicates as follows. The CI constructions for Qπ , V⋆ and Q⋆ are analogous. Recall that we denote the plug-in estimator by ∗(1) ∗(B) V̂π , and the bootstrap replicates by V̂π , . . . , V̂π . We further denote the empirical α-quantile ∗(j) B ∗ of {V̂π (s)}j=1 for some s ∈ S by qα . The 100(1 − α)% bootstrap percentile CI for Vπ (s) is ∗ ∗ ∗ ∗ qα/2 , q1−α/2 . The bootstrap pivot CI is 2V̂π (s) − q1−α/2 , 2V̂π (s) − qα/2 . Remark 5. Constructing CIs for OPE and OPR targets requires an additional O(B) Bellman solves, negligible compared to the O(Bn) bootstrap simulation cost. We now state the bootstrap distributional consistency results for the plug-in value and Q-function estimators for OPE and OPR, both in the single-chain and episodic settings. We define the asymptotic covariance matrices ΣπV := γ 2 (I − γΠM)−1 Π ⊗ Vπ⊤ Λ̄ Π⊤ (I − γM⊤ Π⊤ )−1 ⊗ Vπ , ⊤ ΣπQ := γ 2 (I − γMΠ)−1 ⊗ Q⊤ Λ̄ (I − γΠ⊤ M⊤ )−1 ⊗ ΠQπ . πΠ We further define Π⋆ as the policy matrix associated with π⋆ , and π ′ as any policy with policy matrix Π′ . The following proposition then lifts the bootstrap distributional consistency results to the plug-in value and Q-function estimators for OPE and OPR, both in the single-chain and episodic settings. Proposition 2 (Bootstrap Validity for OPE and OPR). Under the conditions of Theorem 1 (singlechain) or Proposition 1 (episodic), for any fixed target policy π, d d √ √ n V̂π∗ − V̂π − → N (0, ΣπV ), n Q̂∗π − Q̂π − → N (0, ΣπQ ), conditionally on Dn , in probability, as n → ∞. Suppose in addition the following non-degeneracy condition: min min Q⋆ (s, π⋆ (s)) − Q⋆ (s, a) > 0. s∈S a̸=π⋆ (s)

Then

√

d n V̂⋆∗ − V̂⋆ − → N (0, ΣπV⋆ ), conditionally on Dn , in probability, as n → ∞.

n Q̂∗⋆ − Q̂⋆

− → N (0, ΣπQ⋆ ),

√ √ Remark 6. ΣπV and ΣπQ are the asymptotic covariances of n(V̂π − Vπ ) and n(Q̂π − Qπ ) given √ in Su et al. [2026, Theorem 2], and ΣπV⋆ is the asymptotic covariance of n(V̂⋆ − V⋆ ) given in Su et al. [2026, Theorem 3].

This proposition guarantees that percentile and pivot bootstrap CIs are asymptotically valid for Vπ , Qπ , V⋆ and Q⋆ . The proof of this proposition can be found in Appendix D.2. 8

Numerical Experiments

Following existing benchmarks, which broadly focus on the stationary setting, we replicate the small state-space RiverSwim experiment of Zhu et al. [2024] to evaluate finite-sample CI coverage for the proposed model-based bootstrap. The RiverSwim MDP has S = 6 states and A = 2 actions, with rewards r(1, 0) = 1, r(6, 1) = 10, and r(s, a) = 0 otherwise, and discount factor γ = 0.95. Figure 1 in Appendix E illustrates the transition and reward structure of our RiverSwim setup. The experiment is deliberately challenging for inference because the behavior policy visits upstream states (near state 6) rarely, while the optimal policy is nearly degenerate at the left-most state 1. We use the stationary behavior policy πb (1 | s) = 0.8 for all states, B = 1000 bootstrap replicates, and Nreps = 1000 Monte Carlo replications. For OPE, we evaluate fixed target policies including uniform (π(1 | s) = 0.5), mostly-right (π(1 | s) = 0.8), and mostly-left (π(1 | s) = 0.2) policies for horizon length T = 50. For OPR, we evaluate the optimal value and action-value targets across horizons T ∈ {10, 50, 100}. Table 1 in Appendix E summarizes the settings of all experiments. We compare percentile and pivot CIs from the proposed model-based bootstrap with the episodic bootstrap [Hao et al., 2021] and plug-in CLT CIs [Zhu et al., 2024, Su et al., 2026]. Across the OPE and OPR tasks, the model-based bootstrap, especially the percentile CI, substantially improves coverage relative to the episodic bootstrap and plug-in CLT baselines. For OPE at n ≥ 500, and for OPR with T ∈ {50, 100} at n ≥ 500, the model-based bootstrap percentile CI attains near-nominal coverage at nominal 50% (about 0.48–0.54), 90% (about 0.87–0.94), and 95% (about 0.92–0.97). The CI coverage for model-based bootstrap is weakest for rarely visited state–action pairs (near state 6) and for the short-horizon OPR setting T = 10, as expected from the strained asymptotic and non-degeneracy conditions. Detailed coverage tables and figures are reported in Appendix E.

Conclusion

We propose and analyze a model-based bootstrap for finite CMCs with possibly nonstationary or history-dependent control policies, motivated by the offline RL setting. We establish the bootstrap distributional consistency of the transition estimators in both the single long chain and episodic RL settings. We lift the bootstrap distributional consistency to OPE and OPR targets, exploiting the delta method by verifying Hadamard differentiability of the Bellman operators. While our theoretical and numerical results are promising, we acknowledge several important considerations on the limitations and future directions of our work. First, we assume that the reward function is known in downstream RL tasks to avoid confusion in bootstrap targets. When the reward function is unknown and estimated from data, our bootstrap validity for OPE and OPR continues to hold if the reward estimate converges in probability to the mean reward, although finite-sample performance may be affected by the additional estimation error, which warrants further study. Second, we limit our current analysis to a finite state–action space. Extending our result to function approximation or continuous state-action spaces is an important future direction. Third, we only consider the asymptotic regime of fixed T and K → ∞ for the episodic setting. We do not consider the asymptotic regime where K is fixed and greater than 1 and T → ∞, and it remains an open question whether the bootstrap is consistent in this regime. Lastly, further experiments with non-stationary behavior policies, which the theory accommodates, remain to be conducted.

References A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32:96, 2019. K. Athreya and C.-D. Fuh. Bootstrapping markov chains: countable case. Journal of Statistical Planning and Inference, 33(3):311–331, 1992. H. Babamoradi, F. van den Berg, and Å. Rinnan. Bootstrap based confidence limits in principal component analysis—a case study. Chemometrics and Intelligent Laboratory Systems, 120:97–105, 2013. 9

I. Banerjee. Probably Approximately Correct Bounds for Estimating Markov Transition Kernels. PhD thesis, Purdue University, 2023. I. Banerjee and S. Chakrabarty. Small resamples, sharp guarantees: Convergence rates for resampled studentized quantile estimators. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. I. Banerjee, H. Honnappa, and V. Rao. Off-line estimation of controlled markov chains: Minimaxity and sample complexity. Operations Research, 2025. P. Bertail and S. Clémençon. Regenerative block bootstrap for markov chains. Bernoulli, 12(4): 689–712, 2006. D. P. Bertsekas. Dynamic programming and optimal control, 3rd edition, volume II. Belmont, MA: Athena Scientific, 2011. P. Billingsley. Statistical methods in Markov chains. The Annals of Mathematical Statistics, pages 12–40, 1961. V. S. Borkar. Topics in controlled Markov chains. Taylor & Francis, 1991. H. Cramér and H. Wold. Some theorems on distribution functions. Journal of the London Mathematical Society, 1(4):290–294, 1936. R. L. Dobrushin. Central limit theorem for nonstationary Markov chains. I. Theory of Probability & Its Applications, 1(1):65–80, 1956. B. Efron. Bootstrap methods: Another look at the jackknife. The Annals of Statistics, pages 1–26, 1979. M. K. S. Faradonbeh, A. Tewari, and G. Michailidis. On applications of bootstrap in continuous space reinforcement learning. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 1977–1984. IEEE, 2019. S. Gonçalves, U. Hounyo, A. J. Patton, and K. Sheppard. Bootstrapping two-stage quasi-maximum likelihood estimators of time series models. Journal of Business & Economic Statistics, 41(3): 683–694, 2023. P. Hall. The bootstrap and Edgeworth expansion. Springer Science & Business Media, 2013. P. Hall and C. C. Heyde. Martingale Limit Theory and Its Application. Academic Press, London, United Kingdom, 1980. P. Hall and A. Padmanabhan. On the bootstrap and the trimmed mean. Journal of Multivariate Analysis, 41(1):132–153, 1992. J. Han and Q. Liu. Bootstrap model aggregation for distributed statistical learning. Advances in Neural Information Processing Systems, 29, 2016. J. Hanna, P. Stone, and S. Niekum. Bootstrapping with models: Confidence intervals for off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017. B. Hao, X. Ji, Y. Duan, H. Lu, C. Szepesvari, and M. Wang. Bootstrapping fitted q-evaluation for off-policy inference. In International Conference on Machine Learning, pages 4074–4084. PMLR, 2021. J. L. Horowitz. Bootstrap methods for markov processes. Econometrica, 71(4):1049–1082, 2003. J. L. Horowitz. Bootstrap methods in econometrics. Annual Review of Economics, 11(1):193–224, 2019. A. K. Jain and J. Moreau. Bootstrap technique in cluster analysis. Pattern Recognition, 20(5): 547–568, 1987. Y. Jedra, J. Lee, A. Proutiere, and S.-Y. Yun. Nearly optimal latent state decoding in block mdps. In International Conference on Artificial Intelligence and Statistics, pages 2805–2904. PMLR, 2023. 10

L. A. Kontorovich and K. Ramanan. Concentration inequalities for dependent random variables via the martingale method. Annals of Probability, 36(6):2126–2158, 2008. I. Kostrikov and O. Nachum. Statistical bootstrapping for uncertainty estimation in off-policy evaluation. arXiv preprint arXiv:2007.13609, 2020. V. Krishnamurthy. Partially observed Markov decision processes. Cambridge university press, 2016. R. Kulperger and B. P. Rao. Bootstrapping a finite state markov chain. Sankhyā: The Indian Journal of Statistics, Series A, pages 178–191, 1989. C. D. Meyer, Jr. The condition of a finite markov chain and perturbation bounds for the limiting probabilities. SIAM Journal on Algebraic Discrete Methods, 1(3):273–283, 1980. J. Modayil and B. Kuipers. Towards bootstrap learning for object discovery. In AAAI-2004 workshop on anchoring symbols to sensor data, 2004. P. Nakkiran, B. Neyshabur, and H. Sedghi. The deep bootstrap framework: Good online learners are good offline generalizers. arXiv preprint arXiv:2010.08127, 2020. A. Rahoma, S. Imtiaz, and S. Ahmed. Sparse principal component analysis using bootstrap method. Chemical Engineering Science, 246:116890, 2021. P. Ramprasad, Y. Li, Z. Yang, Z. Wang, W. W. Sun, and G. Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. Journal of the American Statistical Association, 118 (544):2901–2914, 2023. E. Ruiz and L. Pascual. Bootstrapping financial time series. Journal of Economic Surveys, 16(3): 271–300, 2002. A. L. Strehl and M. L. Littman. An empirical evaluation of interval estimation for markov decision processes. In 16th IEEE International Conference on Tools with Artificial Intelligence, pages 128–135. IEEE, 2004. Z. Su, I. Banerjee, and D. Klabjan. Central limit theorems for transition probabilities of controlled markov chains. arXiv preprint arXiv:2508.01517, 2026. A. W. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000. Y. Zhu, J. Dong, and H. Lam. Uncertainty quantification and exploration for reinforcement learning. Operations Research, 72(4):1689–1709, 2024.

Sufficient Conditions for Assumption 2

Assumption 2 requires a uniform bound on the cumulative weak η̄-mixing coefficients of the joint state–action process {(Xi , Ai )}i≥0 , which can be difficult to verify directly. Following Su et al. [2026], Banerjee et al. [2025], we give two separate conditions—one for the action process and one for the state process—whose conjunction implies Assumption 2. Mixing of actions. For integers p > i + j > i ≥ 0, we define the γ-mixing coefficient p−1 i i γp,j,i := sup P Ap = · Xp = sp , Hi+j = hp−1 , H = h 0 0 i+j i sp , hp−1 i+j , h0

p−1 i i P(Xp =sp , Hi+j =hp−1 i+j , H0 =h0 )>0

p−1 − P Ap = · Xp = sp , Hi+j = hp−1 i+j

, TV

where ∥ · ∥TV denotes the total variation distance (TV). Thus γp,j,i measures the worst-case sensitivity p−1 of the action distribution at time p to the distant past H0i , given the more recent history Hi+j . It thereby quantifies how much the dependence on old history of the behavior policy can alter future action selection. We now impose a summability condition on these coefficients. Assumption 4 (Mixing of Actions). There exists a constant C ≥ 0 such that ∞ ∞ X X C sup γp,j,i ≤ . 2 i≥1 j=1 p=i+j+1 When the sequence of actions ap is Markovian, i.e. it depends only on the current state Xp , then γp,j,i = 0 for all p, j, i; thus, Assumption 4 holds with C = 0. This covers any stationary or non-stationary Markov behavior policy. Mixing of states. For all integers j ≥ i ≥ 0, define the θ-mixing coefficient θ̄i,j :=

P (Xj = · | Xi = s1 , Ai = a1 )

sup (s1 ,a1 ),(s2 ,a2 )∈S×A, (s1 ,a1 )̸=(s2 ,a2 ) P(Xi =s1 ,Ai =a1 )>0, P(Xi =s2 ,Ai =a2 )>0

− P (Xj = · | Xi = s2 , Ai = a2 )

. TV

Thus θ̄i,j measures the rate at which the state process forgets its initial state–action pair, extending Dobrushin’s coefficients [Dobrushin, 1956] to the controlled setting. We now impose a summability condition on these coefficients. Assumption 5 (Mixing of States). There exists a constant Cθ ≥ 0 such that ∞ X sup θ̄i,j ≤ Cθ . i≥1 j=i+1

Neither assumption implies the other. A CMC with deterministic actions satisfies Assumption 4 with C = 0 regardless of state mixing. Conversely, a CMC in which states are drawn i.i.d. satisfies Assumption 5 with Cθ = 0 regardless of the behavior policy. The two conditions are therefore independent. Finally, if Assumptions 4 and 5 hold, Banerjee et al. [2025, Lemma 3] implies that ∥∆n ∥ ≤ C +Cθ +1 for all n. In particular, Assumption 2 holds with C∆ = C + Cθ + 1.

Auxiliary Lemmas for Theorem 1

B.1

Consistency of the Empirical Behavior Policy

Before we introduce the consistency of the empirical behavior policy, we introduce some requisite P (a) (a′ ) notation. We define a stationary behavior policy π̄b (a | s) := ps /ps , where ps := a′ ∈A ps is the sum of the ergodic occupation measure by actions. We now state the consistency of the empirical behavior policy. 12

Lemma 3 (Consistency of π̂b ). Under Assumptions 1–3, a.s.

π̂b (a | s) −−→ π̄b (a | s)

for every (s, a) ∈ S × A. (a)

a.s.

(a)

Proof. As Assumptions 1–3 hold, by Su et al. [2026, Lemma 2], Ns /n −−→ ps for every (s, a). Summing over a ∈ A, X Ns(a) a.s. Ns = −−→ ps . n n a (a)

Assumption 3 gives ps

≥ p0 > 0; thus, ps ≥ p0 > 0. The continuous mapping theorem then yields (a)

π̂b (a | s) = B.2

(a)

Ns /n a.s. ps −−→ = π̄b (a | s). Ns /n ps

Properties of the Reference State–Action Chain

The analysis rests on a reference state–action Markov chain that couples the true transition kernel M with the stationary behavior policy π̄b . We begin by formally introducing the transition kernel of the reference state-action chain. Definition 4 (Reference State–Action Chain). The reference state–action chain on S ×A has one-step transition kernel (a) K (s, a), (t, b) := Ms,t π̄b (b | t), (s, a), (t, b) ∈ S × A. We record the key structural properties of K that are used throughout the proofs. Lemma 4 (Properties of the Reference State–Action Chain). Under Assumptions 1–3 and the (a0 ) self-loop condition Ms0 ,s 0 > 0: (a)

(i) p = (ps )(s,a)∈S×A is the unique stationary distribution of K. (ii) K is irreducible and aperiodic on S × A. Proof. (i) Unique stationarity. Since p is the ergodic occupation measure under (M, πb ), we have X (l) (l) ps = pt Mt,s . (t,l)

Therefore X (t,l)∈S×A

(a) X (l) (l) ps (l) pt K (t, l), (s, a) = pt Mt,s π̄b (a | s) = ps · = p(a) s , ps (t,l)

hence p satisfies pK = p. An irreducible Markov chain on a finite state space has a unique stationary distribution; uniqueness then follows from part (ii). (ii) Irreducibility and aperiodicity. By Assumption 1, in the original CMC with control policy πb , the hitting and return times to every state–action pair are finite a.s.; hence every state–action pair is hit and returned to infinitely often a.s. Therefore, for any two state–action pairs (s, a), (t, b) ∈ S × A, there exists a finite path from (s, a) to (t, b) with positive probability under the original CMC. (a)

By Assumption 3, ps

≥ p0 > 0 for all (s, a); hence (a)

π̄b (a | s) =

ps >0 ps

for all (s, a) ∈ S × A. Therefore, every positive-probability path segment under the original CMC has positive probability under the reference state–action kernel K, because each state transition along the path has positive transition probability and π̄b assigns positive probability to every action at every state. Thus K is irreducible. 13

For aperiodicity, Assumption 3 gives ps =

(a)

′

) p(a ≥ p0 > 0 s

and

π̄b (a | s) =

a′

ps >0 ps

for all (s, a).

Then by the self-loop condition, we have 0) π̄b (a0 | s0 ) > 0. K (s0 , a0 ), (s0 , a0 ) = Ms(a0 ,s 0 A positive self-loop in a finite irreducible chain forces the period of the entire chain to be one; thus, K is aperiodic. B.3

Eventual Mixing Bound for the Bootstrap CMC

The bootstrap CMC {(Xi∗ , A∗i )} replaces the true kernel M and the stationary policy π̄b with their empirical counterparts M̂ and π̂b , respectively. Let Hp∗j denote the history of the bootstrap CMC ∗ ∗ ∗ ∗ from time p to j, and h∗j p := {Xp = sp , Ap = ap , . . . , Xj = sj , Aj = aj }. We define the weak mixing coefficients for the bootstrap CMC {(Xi∗ , A∗i )} as follows. Definition 5 (Weak Mixing Coefficients for the Bootstrap CMC). For i < j ≤ n, T ⊆ (S ×A)n−j+1 , ∗ s1 , s2 ∈ S, and a1 , a2 ∈ A, let ηi,j (T , s1 , s2 , a1 , a2 , h∗i−1 , n) := P (Xj∗ , A∗j , . . . , Xn∗ , A∗n ) ∈ 0 T | Xi∗ = s1 , A∗i = a1 , H0∗i−1 = h∗i−1 − P (Xj∗ , A∗j , . . . , Xn∗ , A∗n ) ∈ T | Xi∗ = s2 , A∗i = 0 ∗i−1 ∗i−1 a2 , H0 = h0 . The weak η̄-mixing coefficient for the bootstrap CMC is ∗ η̄i,j (n) :=

∗ ηi,j (T , s1 , s2 , a1 , a2 , h∗i−1 , n). 0

sup

T ,s1 ,s2 ,a1 ,a2 ,h∗i−1 , 0 ∗i−1 P Xi∗ =s1 ,A∗ =h∗i−1 >0, i =a1 ,H0 0 ∗i−1 ∗i−1 =a ,H =h >0 P Xi∗ =s2 ,A∗ 2 i 0 0

) )

( (

∗ Then, the bootstrap CMC counterpart of ∥∆n ∥ in Assumption 2 is ∥∆∗n ∥ := max1≤i≤n (1 + η̄i,i+1 + ∗ · · · + η̄i,n ).

We formally introduce the transition kernel of the Markov chain of bootstrap state–action pairs that is used throughout the proofs. Definition 6 (Bootstrap State–Action Chain). The bootstrap state–action chain on S × A has one-step transition kernel (a) Kn∗ (s, a), (t, b) := M̂s,t π̂b (b | t), (s, a), (t, b) ∈ S × A. The following lemma shows that the bootstrap CMC {(Xi∗ , A∗i )} inherits the mixing properties of the CMC {(Xi , Ai )} in Assumption 2 for all sufficiently large n, almost surely. Lemma 5 (Eventual Mixing Bound for Bootstrap Chain). There almost surely exist a finite (random) ∗ N0 and a deterministic constant C∆ < ∞ such that ∗ ∥∆∗n ∥ ≤ C∆

for all n ≥ N0 .

Proof. We proceed in five steps. Let N0 be the (a.s. finite) random index beyond which all the entrywise convergences invoked in Steps 1–4 have taken effect simultaneously; its finiteness follows from the fact that each individual a.s. convergence has a finite threshold, and a finite maximum of a.s.-finite random variables is a.s. finite. All statements below hold for all n ≥ N0 a.s. Step 1 (Entrywise convergence). By Lemma 3, π̂b → π̄b a.s. By Su et al. [2026, Lemma 2], (a) (a) M̂s,t → Ms,t a.s. for every (s, a, t). Hence Kn∗ → K entrywise a.s. (a)

Step 2 (Eventual irreducibility). By Assumption 3 and Su et al. [2026, Lemma 2], Ns /n → (a) (a) ps ≥ p0 > 0 a.s. Thus, Ns > 0 for all (s, a) and all n ≥ N0 . When this holds, π̂b (a | s) > 0 and (a) (a) M̂s,t > 0 for all (s, a, t) such that Ms,t > 0. 14

Since K is irreducible by Lemma 4 (ii), for any z, w ∈ S × A, there exists a finite sequence z = z0 , z1 , . . . , zℓ = w such that K(zi−1 , zi ) > 0 for each i = 1, . . . , ℓ. Each such step satisfies (a) (a) K(zi−1 , zi ) = Ms,t π̄b (l | t) for the corresponding (s, a, t, l), which requires Ms,t > 0; since (a)

(a)

M̂s,t > 0 for all n ≥ N0 whenever Ms,t > 0, we have Kn∗ (zi−1 , zi ) > 0 for every step; thus, the same path has strictly positive probability under Kn∗ . Hence Kn∗ is irreducible for all n ≥ N0 . (a )

(a )

0 0 0 0 Step 3 (Eventual aperiodicity). Since Ns0 ,s Ms0 ,s 0 /n → ps0 0 > 0 a.s., we have Ns0 ,s0 > 0 for (a0 ) all n ≥ N0 ; thus, M̂s0 ,s0 > 0, which gives 0) Kn∗ (s0 , a0 ), (s0 , a0 ) = M̂s(a0 ,s π̂b (a0 | s0 ) > 0. 0 ∗ A positive self-loop in the irreducible Kn forces aperiodicity for all n ≥ N0 .

Step 4 (Uniform Doeblin minorization and geometric ergodicity). Since K is finite, irreducible, and aperiodic by Lemma 4 (ii), it is primitive: there exists r ≥ 1 such that K r (z, w) > 0 for all z, w ∈ S × A, where X K r (z, w) := K(z, z1 ) K(z1 , z2 ) · · · K(zr−1 , w) z1 ,...,zr−1 ∈S×A

is the r-step transition kernel (K 1 := K). We define η := min K r (z, w) > 0. z,w∈S×A

Since entrywise convergence is preserved under matrix multiplication, Kn∗r → K r entrywise a.s.; thus, for all n ≥ N0 , η Kn∗r (z, w) ≥ ∀ z, w ∈ S × A. 2 Let ν(z) := 1/(SA) for all z ∈ S ×A be the uniform distribution on S ×A, and set δ := SA η/2 > 0. Then for all n ≥ N0 a.s., Kn∗r (z, ·) ≥ δ ν(·) for all z. This is a uniform Doeblin minorization with deterministic r, δ, ν depending only on K. We now derive the geometric ergodicity of Kn∗ for all n ≥ N0 a.s. from the uniform Doeblin minorization. The first step is to derive a TV contraction for Kn∗r with contraction factor 1 − δ: for any two probability measures µ1 , µ2 on S × A, ∥µ1 Kn∗r − µ2 Kn∗r ∥TV ≤ (1 − δ)∥µ1 − µ2 ∥TV . We now derive the TV contraction explicitly. We write each row of Kn∗r as K ∗r (z, ·) − δ ν(·) , Kn∗r (z, ·) = δ ν(·) + (1 − δ) Rz (·), Rz (·) := n 1−δ where Rz is a probability measure. For any probability measure µ on S × A, X X µ(z) Kn∗r (z, w) = µ(z) δ ν(w) + (1 − δ) Rz (w) (µKn∗r )(w) = z

= δ ν(w) + (1 − δ)

µ(z) Rz (w),

P where the last step uses z µ(z) = 1. Then, for any two probability measures µ1 , µ2 on S × A, we ∗r subtract µ1 Kn from µ2 Kn∗r : ! X X ∗r ∗r µ1 Kn − µ2 Kn = (1 − δ) µ1 (z) Rz − µ2 (z) Rz . z

Taking the TV norm and applying the triangle inequality, X ∥µ1 Kn∗r − µ2 Kn∗r ∥TV = (1 − δ) (µ1 (z) − µ2 (z)) Rz z

1−δ X X (µ1 (z) − µ2 (z)) Rz (w) 2 w z X 1−δ X ≤ |µ1 (z) − µ2 (z)| Rz (w) 2 z w =

= (1 − δ) ∥µ1 − µ2 ∥TV , 15

where the final equality uses

w Rz (w) = 1 since each Rz is a probability measure.

∗(a)

Let p̂∗ := (p̂s )(s,a)∈S×A denote the stationary distribution of Kn∗ . For all n ≥ N0 , since Kn∗ is irreducible and aperiodic a.s., p̂∗ is the unique stationary distribution of Kn∗ , and p̂∗ Kn∗ = p̂∗ . We use this stationarity to bound ∥Kn∗mr (z, ·) − p̂∗ (·)∥TV by induction on m. When m = 0, the bound holds trivially since ∥δz − p̂∗ ∥TV ≤ 1 = (1 − δ)0 . Suppose the bound holds for some m ≥ 0, i.e. ∥δz Kn∗mr − p̂∗ ∥TV ≤ (1 − δ)m . Applying the TV contraction with µ1 = δz Kn∗mr and µ2 = p̂∗ , ∗(m+1)r and rewriting Kn = Kn∗mr Kn∗r , we have δz Kn∗(m+1)r − p̂∗ TV = (δz Kn∗mr )Kn∗r − p̂∗ Kn∗r TV ≤ (1 − δ) δz Kn∗mr − p̂∗ TV ≤ (1 − δ)m+1 , where the second inequality applies the induction hypothesis. Hence for all m ≥ 0, sup Kn∗mr (z, ·) − p̂∗ (·) TV ≤ (1 − δ)m . z

For any t ≥ 0, we can write t = mr + s with m ≥ 0 and 0 ≤ s < r. Applying the TV contraction to the pair (δz Kn∗s , p̂∗ ) over m further blocks of r steps, and using p̂∗ Kn∗mr = p̂∗ , we have Kn∗t (z, ·) − p̂∗ (·) TV = δz Kn∗s Kn∗mr − p̂∗ Kn∗mr TV ≤ (1 − δ)m δz Kn∗s − p̂∗ TV ≤ (1 − δ)m . We define ρ∗ := (1 − δ)1/r ∈ (0, 1) and C∗ := (1 − δ)−1 < ∞. They are deterministic constants depending only on K, since δ depends only on K. As (1 − δ)m = (1 − δ)(t−s)/r ≤ (1 − δ)−1 (1 − δ)t/r = C∗ ρt∗ , we conclude sup Kn∗t (s, a), · − p̂∗ (·) TV ≤ C∗ ρt∗ , t ≥ 0. (s,a)∈S×A

Step 5 (Applying Banerjee et al. [2025, Lemma 3]). Since π̂b is a stationary Markov policy, Assumption 4 holds for the bootstrap CMC with C = 0. It remains to verify Assumption 5 for the bootstrap CMC. We define the θ̄-mixing coefficient of the bootstrap CMC as ∗ θ̄i,j :=

P Xj∗ = · | Xi∗ = s1 , A∗i = a1

sup

(s1 ,a1 ),(s2 ,a2 )∈S×A, (s1 ,a1 )̸=(s2 ,a2 ) ∗ ∗ P(Xi∗ =s1 ,A∗ i =a1 )>0, P(Xi =s2 ,Ai =a2 )>0

− P Xj∗ = · | Xi∗ = s2 , A∗i = a2

. TV

We connect the bound in Step 4 to the θ̄-mixing coefficient as follows. For any two distributions µ, ν on S × A with S-marginals µX , νX , we demonstrate that marginalization cannot increase total variation: for every B ⊆ S, |µX (B) − νX (B)| = |µ(B × A) − ν(B × A)| ≤ ∥µ − ν∥TV , ∗(j−i)

hence ∥µX − νX ∥TV ≤ ∥µ − ν∥TV . Applying this to µ = Kn S-marginal is denoted by µ̂∗X , gives

((sk , ak ), ·) and ν = p̂∗ , whose

P(Xj∗ = · | Xi∗ = sk , A∗i = ak ) − µ̂∗X (·) TV ≤ Kn∗(j−i) (sk , ak ), · − p̂∗ (·) TV ≤ C∗ ρj−i ∗ . By the triangle inequality, ∗ θ̄i,j ≤ 2C∗ ρj−i j > i ≥ 1. ∗ , Therefore ∞ X X 2C∗ ρ∗ ∗ sup θ̄i,j ≤ 2 C∗ ρj∗ = < ∞, 1 − ρ∗ i≥1 j>i j=1 ∗ ∗ ρ∗ and Assumption 5 holds for the bootstrap CMC. Let C∆ := 2C 1−ρ∗ + 1. Banerjee et al. [2025, ∗ ρ∗ Lemma 3] then implies that Assumption 2 holds for the bootstrap CMC, and ∥∆∗n ∥ ≤ 0+ 2C 1−ρ∗ +1 = ∗ C∆ for all n ≥ N0 a.s. This completes the proof.

B.4

Continuity of the Stationary Distribution Map

Lemma 6 (Continuity of the Stationary Distribution Map). On the almost sure event of Lemma 5, a.s.

p̂∗(a) −−→ p(a) s s

for every (s, a) ∈ S × A.

Proof. By Lemma 4, K is irreducible and aperiodic on the finite state space S × A. Since every irreducible finite-state chain is positive recurrent, K is ergodic, and its stationary distribution p is unique. By Lemma 5, Kn∗ is irreducible and aperiodic for all n ≥ N0 a.s. Therefore, Kn∗ is eventually ergodic, with unique stationary distribution p̂∗ for each n ≥ N0 . Then by Meyer [1980, Theorem 4.1], the limiting probability vector of an ergodic chain is a continuous function of the transition matrix. ∗(a) a.s. (a) Since Kn∗ → K entrywise a.s. by Lemma 5 Step 1, we conclude p̂s −−→ ps for every (s, a) ∈ S × A. B.5

Bootstrap Visitation Count Law of Large Numbers

Lemma 7 (Bootstrap Visitation Count LLN). For each (s, a) ∈ S × A, ∗(a)

Ns n

∗(a)

Proof. We begin by defining µ∗n := E[Ns ∗(a) Ns

a.s.

−−→ p(a) s . | Dn ] and writing

∗(a) Ns µ∗n = · = Term 1 · Term 2. µ∗n n

n We handle Term 2 first, then Term 1.

Term 2 (Expectation convergence). Let νn∗ denote the initial distribution of (X0∗ , A∗0 ) under Kn∗ . Then n−1 X µ∗n = (νn∗ Kn∗i )(s, a), i=0

Pn−1 ∗(a) ∗(a) hence µ∗n − np̂s = i=0 [(νn∗ Kn∗i )(s, a) − p̂s ]. By Lemma 5 (Step 4), supz ∥Kn∗i (z, ·) − p̂∗ ∥TV ≤ C∗ ρi∗ for all n ≥ N0 a.s. Since νn∗ is a probability measure, X ∥νn∗ Kn∗i − p̂∗ ∥TV ≤ νn∗ (z) Kn∗i (z, ·) − p̂∗ TV ≤ C∗ ρi∗ . z

Therefore, for all n ≥ N0 a.s., µ∗n − np̂∗(a) ≤ s

∞ X

C∗ ρi∗ =

i=0

C∗ < ∞. 1 − ρ∗

∗(a) ∗(a) a.s. (a) Hence µ∗n /n = p̂s + O(1/n). Since p̂s −−→ ps by Lemma 6, µ∗n a.s. (a) −−→ ps .

Term 1 (Concentration). On the probability-one event where N0 < ∞ (Lemma 5), choose (a) ∗ N1 ≥ N0 such that µ∗n ≥ (ps /2) n and ∥∆∗n ∥ ≤ C∆ for all n ≥ N1 (which holds a.s. by Term 2 and Lemma 5). Apply Banerjee et al. [2025, Lemma 6] to the bootstrap chain with kernel Kn∗ : for every ε > 0 and n ≥ N1 , ! ! ∗(a) (a) Ns µ∗n 2 ε2 (ps )2 n ε2 P − 1 > ε ≤ 2 exp − ≤ 2 exp − . ∗2 µ∗n 2n∥∆∗n ∥2 8C∆ ∗(a)

The right-hand side is summable in n; by the Borel–Cantelli lemma, Ns

a.s.

/µ∗n −−→ 1. (a)

Since both Term 1 and Term 2 converge a.s., their product converges a.s. to ps . This completes the proof. 17

Proof of Theorem 1

Proof. We work on the joint probability space (Ω, F, P) carrying both the observed data Dn and the bootstrap randomness; all convergence statements are under P. Define the joint filtration Fn,i := σ(Dn , X0∗ , A∗0 , . . . , Xi∗ , A∗i ). √ ∗(a) (a) We proceed in four steps. First, we decompose n(M̂s,t − M̂s,t ) into a leading term and a remainder. Second, we show the remainder is negligible. Third, we show the leading term converges in distribution to N (0, Λ̄sat,sat ) conditionally on Dn . This is the univariate, one-dimensional √ ∗(a) (a) convergence of n(M̂s,t − M̂s,t ). Finally, we use the Cramér–Wold theorem to extend the √ univariate convergence to the multivariate convergence of n vec(M̂∗ − M̂) to N (0, Λ̄) conditionally on Dn . Step 1: Decomposition. Fix (s, a, t) ∈ S × A × S. Define (a) ∗ ξi∗ := 1{Xi∗ = s, A∗i = a} 1{Xi+1 = t} − M̂s,t . ∗(a)

∗(a)

Since M̂s,t = Ns,t /Ns √

, we have ∗(a)

√ ∗(a) (a) n M̂s,t − M̂s,t = n

Since

√

∗(a)

n/Ns

Ns,t

(a) − M̂s,t ∗(a) Ns

√

√ n−1 n X ∗ ∗(a) (a) ∗(a) = ∗(a) Ns,t − M̂s,t Ns ξi . = ∗(a) Ns Ns i=0 n

√ (a) √ (a) ∗(a) = 1/( n ps ) + (1/ n)(n/Ns − 1/ps ), we can write √

∗(a)

(a)

n M̂s,t − M̂s,t

= Sn∗,sat + Rn∗,sat ,

where Sn∗,sat := √

n−1 X

1 (a)

n ps

ξi∗ ,

Rn∗,sat :=

i=0

− ∗(a)

n−1

1 1 X ∗ √ ξ . (a) n i=0 i ps

Step 2: Remainder is negligible. Define n−1

1 X ∗ Zn∗ := √ ξ , n i=0 i ∗(a) (a) such that Rn∗,sat = n/Ns − 1/ps · Zn∗ . Our goal is to show Rn∗,sat = oP (1), which follows ∗(a) (a) a.s. from Zn∗ = OP (1) and n/Ns − 1/ps −−→ 0.

We start by bounding the variance of Zn∗ . On the event {Xi∗ = s, A∗i = a}, the bootstrap chain (a) reaches next state t with probability M̂s,t , hence E[ξi∗ | Fn,i ] = 1{Xi∗ = s, A∗i = a} M̂s,t − M̂s,t (a)

(a)

= 0.

Hence (ξi∗ ) is a martingale difference sequence under (Fn,i ) and P. For i < j, the tower property gives E[ξi∗ ξj∗ ] = E ξi∗ E[ξj∗ | Fn,j ] = 0, thus cross-terms in Var[Zn∗ ] vanish. The conditional second moment of ξi∗ is 1 (a) (a) E (ξi∗ )2 | Fn,i = 1{Xi∗ = s, A∗i = a} M̂s,t 1 − M̂s,t ≤ , 4 18

∗ = t} given Fn,i on {Xi∗ = s, A∗i = a} is Bernoulli(M̂s,t ). Summing over i, we get since 1{Xi+1 (a)

Var[Zn∗ ] = =

n−1 1 X ∗ 2 E (ξi ) n i=0 n−1 1X ∗ 2 E E (ξi ) | Fn,i n i=0 n−1

1X1 ≤ n i=0 4 =

1 . 4

For any M > 0, by the Chebyshev’s inequality, Var[Zn∗ ] 1 P |Zn∗ | > M ≤ ≤ , M2 4M 2 ∗(a)

hence Zn∗ = OP (1). Since Ns (a) a.s. 1/ps −−→ 0.

a.s.

(a)

/n −−→ ps

∗(a)

> 0, the continuous mapping theorem gives n/Ns

−

To show Rn∗,sat = oP (1), we consider any ε, δ > 0 and choose M large enough that 1/(4M 2 ) < δ/2. ∗(a) (a) We define the event En := {|n/Ns − 1/ps | > ε/M } ∪ {|Zn∗ | > M }. On the event Enc , both ∗(a) (a) ∗(a) (a) |n/Ns −1/ps | ≤ ε/M and |Zn∗ | ≤ M hold; thus, we have |Rn∗,sat | = |n/Ns −1/ps |·|Zn∗ | ≤ (ε/M ) · M = ε. Therefore, P |Rn∗,sat | > ε = P |Rn∗,sat | > ε, Enc + P |Rn∗,sat | > ε, En = 0 + P |Rn∗,sat | > ε, En ≤ P |Zn∗ | > M 1 ≤ 4M 2 δ < . 2 d

Since δ is arbitrary, we have Rn∗,sat = oP (1), and it suffices to show Sn∗,sat − → N (0, Λ̄sat,sat ) under P. Step 3: One Dimensional Martingale CLT. Define d∗,sat n,i+1 := √

ξi∗ (a)

n ps

Pn−1 ∗,sat ∗,sat ∗ so that Sn∗,sat = i=0 d∗,sat n,i+1 . Since E[ξi | Fn,i ] = 0, we have E[dn,i+1 | Fn,i ] = 0, and (dn,i+1 ) is a martingale difference array under P with respect to the joint filtration (Fn,i ). To prove the CLT for Sn∗,sat , we verify the Lindeberg condition. Since |ξi∗ | ≤ 1, we have |d∗,sat n,i+1 | ≤ √ (a) (a) −2 1/( n ps ). For any ε > 0, we set n0 := ⌈(ε ps ) ⌉, where ⌈x⌉ denotes the smallest integer ∗,sat greater than or equal to x. For all n ≥ n0 , |d∗,sat n,i+1 | ≤ ε; thus, {|dn,i+1 | > ε} = ∅ and n−1 X

h ∗,sat 2 E (d∗,sat n,i+1 ) 1 |dn,i+1 | > ε

i Fn,i = 0.

i=0

Hence, the Lindeberg condition holds for all n ≥ n0 . We now derive the asymptotic variance of Sn∗,sat by analyzing the predictable quadratic variation Pn−1 ∗,sat 2 i=0 E[(dn,i+1 ) | Fn,i ]. Using E[(ξi∗ )2 | Fn,i ] = 1{Xi∗ = s, A∗i = a}M̂s,t (1 − M̂s,t ), (a)

(a)

we have

1{Xi∗ = s, A∗i = a} (a) (a) 2 ) | F = E (d∗,sat M̂s,t 1 − M̂s,t . n,i n,i+1 (a) 2 n (ps ) Summing over i = 0, . . . , n − 1, we get n−1 X

∗(a) Ns (a) (a) 2 M̂s,t 1 − M̂s,t . E (d∗,sat n,i+1 ) | Fn,i = (a) 2 n (ps ) i=0

∗(a)

a.s.

(C.1)

(a) a.s.

(a)

By Lemma 7, Ns /n −−→ ps , and by Su et al. [2026, Lemma 2], M̂s,t −−→ Ms,t . Therefore, the right-hand side of (C.1) converges a.s. to (a) (a) Ms,t 1 − Ms,t = Λ̄sat,sat . (a) ps By the martingale CLT [Hall and Heyde, 1980, Corollary 3.1], applied conditionally on Dn for P-a.e. d Dn , we obtain that, conditional on Dn , Sn∗,sat − → N (0, Λ̄sat,sat ) for P-almost every (Dn ). Combined √ ∗(a) (a) d with Rn∗,sat = oP (1), we conclude that, conditional on Dn , n(M̂s,t − M̂s,t ) − → N (0, Λ̄sat,sat ) for P-almost every (Dn ). Step 4: Multivariate CLT via Cramér–Wold. Step 3 establishes the marginal CLT for each scalar √ (a) ∗(a) coordinate n(M̂s,t − M̂s,t ). We now extend this to the joint distribution over all coordinates simultaneously. √ Let Sn∗ := (Sn∗,sat )(s,a,t) denote the stacked vector, such that n vec(M̂∗ − M̂) = Sn∗ + oP (1), using Rn∗,sat = oP (1) from Step 2. By the Cramér–Wold theorem, a random vector converges in distribution to a multivariate normal if and only if every fixed linear combination of its coordinates 2 does. It therefore suffices to show that for every fixed u ∈ RS A , d

u⊤ Sn∗ − → N (0, u⊤ Λ̄ u),

conditional on Dn , for P-a.e. (Dn ).

(a)

We fix such u and let p0 := mins,a ps

> 0. We define the projected increments X d˜∗n,i+1 := usat d∗,sat n,i+1 s,a,t

Pn−1 and the projected partial sum S̃n∗ := i=0 d˜∗n,i+1 , so that u⊤ Sn∗ = S̃n∗ . Since each d∗,sat n,i+1 has ∗ ∗ ˜ ˜ zero P-conditional mean given Fn,i , the same holds for dn,i+1 ; thus, (dn,i+1 ) is a martingale difference array under P with respect to (Fn,i ). We now verify the Lindeberg condition. Since √ (a) √ √ ˜∗ |d∗,sat n,i+1 | ≤ 1/( n ps ) ≤ 1/( n p0 ), the triangle inequality gives |dn,i+1 | ≤ ∥u∥1 /( n p0 ). For any ε > 0, we set n0 := ⌈∥u∥21 /(εp0 )2 ⌉. For all n ≥ n0 , we have |d˜∗n,i+1 | ≤ ε; thus, n−1 X

h E (d˜∗n,i+1 )2 1 |d˜∗n,i+1 | > ε

i Fn,i = 0.

i=0

Hence, the Lindeberg condition holds for all n ≥ n0 . P ∗,sat 2 We next compute the predictable quadratic variation. We expand (d˜∗n,i+1 )2 = s,a,t usat dn,i+1 to get X X ∗,s′ a′ t′ E (d˜∗n,i+1 )2 | Fn,i = usat us′ a′ t′ E d∗,sat n,i+1 dn,i+1 | Fn,i . s,a,t s′ ,a′ ,t′ ′

′

We observe that when (s, a) ̸= (s , a ),

1{Xi∗ = s, A∗i = a} · 1{Xi∗ = s′ , A∗i = a′ } = 0, ′ ′ ′

∗,s a t since the chain occupies a single state–action pair at each step; hence d∗,sat n,i+1 · dn,i+1 = 0 and those cross-row terms vanish. For the diagonal terms (s, a) = (s′ , a′ ), we condition on Fn,i and use that

∗ (1{Xi+1 = t})t∈S given (Xi∗ = s, A∗i = a) follows a multinomial distribution with 1 trial and event (a) (a) probabilities (M̂s,1 , . . . , M̂s,S ). The second moment formula of the multinomial distribution gives

′ E ξi∗,sat ξi∗,sat | Fn,i (a) (a) ∗ ∗ = 1{Xi∗ = s, A∗i = a} × E (1{Xi+1 = t} − M̂s,t )(1{Xi+1 = t′ } − M̂s,t′ ) | Xi∗ = s, A∗i = a, Dn (a) (a) = 1{Xi∗ = s, A∗i = a} M̂s,t 1{t = t′ } − M̂s,t′ . Therefore n−1 X

X Ns∗(a) X E (d˜∗n,i+1 )2 | Fn,i = usat usat′ (a) 2 s,a n (ps ) t,t′ i=0 (a)

× M̂s,t ∗(a)

Since Ns

a.s.

(a)

(a) 1{t = t′ } − M̂s,t ′ .

(a)

/n −−→ ps and M̂s,t → Ms,t a.s., the quadratic variation converges a.s. to X 1 X (a) s,a ps t,t′

(a) (a) (a) usat usat′ Ms,t 1{t = t′ } − Ms,t Ms,t′ = u⊤ Λ̄ u.

Hence, conditional on Dn , S̃n∗ − → N (0, u⊤ Λ̄u) for P-almost every (Dn ). Since u is arbitrary, the Cramér–Wold theorem gives that, for P-almost every sequence of datasets (Dn )n≥1 , conditional on Dn , √ d n vec(M̂∗ − M̂) − → N (0, Λ̄). This completes the proof.

Proofs of Propositions

D.1

Proof of Proposition 1

Proof. We use the notation introduced in Section 4.2. ′

ei , A ei , X ei+1 )}n −1 with n′ = K(T + We recall that the concatenated single-chain dataset is D̃ := {(X i=0 e(k−1)(T +1)+j := X (k) and A e(k−1)(T +1)+j := 1)−1. The concatenated dataset is defined by setting X j (k)

for j = 0, . . . , T − 1, and inserting at each episode boundary k = 1, . . . , K − 1 a pseudoek(T +1)−1 := a† mapping X (k) to X (k+1) . The extended action space is Ae = A ∪ {a† }, transition A Aj

(a)

ei , A ei )} is a CMC on S × Ae with transition kernel M f, where M fs,t = and the resulting process {(X (a ) (a) † fs,t > 0 for all s, t ∈ S. Ms,t for a ∈ A and M ei , A ei )} satisfies Assumptions 1–3 on S × A, e and there exists (s0 , a0 ) ∈ S × A By hypothesis, {(X (a0 ) with Ms0 ,s0 > 0. Applying Theorem 1 to D̃ gives that, for P-almost every (Dn )n≥1 , conditional on Dn , √ ˆ∗ f ˆ d ¯ f e − M) − → N (0, Λ), as K → ∞, n′ vec(M ¯ e where Λ is the asymptotic covariance matrix. Among the T + 1 steps per episode, exactly T involve actions in A; thus the ergodic occupation measure of the concatenated chain satisfies ¯ (a) T T +1 e p̃(a) s = T +1 ps for a ∈ A, giving Λsat,sat = T Λ̄sat,sat for all (s, a, t) ∈ S × A × S. Since a† -transitions are excluded from M̂ (the empirical estimator uses only a ∈ A), we take the marginals of the Gaussian limit to get √ d ¯ e n′ vec(M̂∗ − M̂) − → N (0, Λ| S×A×S ), 21

¯ ¯ e e where Λ| S×A×S denotes the restriction of Λ to the entries corresponding to (s, a, t) ∈ S × A × S. Among the T + 1 steps per episode, exactly T involve actions in A; thus the ergodic occupation mea¯ (a) (a) T +1 e sure of the concatenated chain satisfies p̃s = T T+1 ps for a ∈ A, giving Λ sat,sat = T Λ̄sat,sat . Since n′ = K(T + 1) − 1 and n = KT , we have KT T T n = = → , as K → ∞. n′ K(T + 1) − 1 T + 1 − 1/K T +1 √ Therefore, re-normalizing vec(M̂∗ − M̂) by n yields r √ n √ ′ d ¯ ∗ ∗ T e n vec(M̂ − M̂) = n vec( M̂ Λ| = N (0, Λ̄). − M̂) − → N 0, S×A×S T +1 n′ D.2

Proof of Proposition 2

The proof applies the bootstrap delta method to Theorem 1 (single-chain) or Proposition 1 (episodic). Before we provide the formal proof, we recall Hadamard differentiability [Van der Vaart, 2000, Chapter 20.2]. A map ϕ : Dϕ → E, defined on a subset Dϕ of a normed space D and taking values in another normed space E, is Hadamard differentiable at θ ∈ Dϕ tangentially to D0 ⊆ D if there exists a continuous linear map ϕ′θ : D0 → E such that ϕ(θ + thn ) − ϕ(θ) − ϕ′θ (h) → 0 as t → 0, for every hn → h ∈ D0 . t E √ d The bootstrap delta method [Van der Vaart, 2000, Theorem 23.9] then states: if n(θ̂∗ − θ̂) − →L conditionally on Dn in probability, and ϕ is Hadamard differentiable at θ tangentially to a subspace √ d D0 , then n(ϕ(θ̂∗ ) − ϕ(θ̂)) − → ϕ′θ (L) conditionally on Dn in probability. The proof of Proposition 2 is as follows. Proof. OPE targets Vπ and Qπ . We first derive the bootstrap consistency results for the OPE targets Vπ . The bootstrap consistency for Qπ is entirely analogous. Consider any fixed stationary target policy π with block-diagonal policy matrix Π. The value function is given by the Bellman equation Vπ (M) = (I − γΠM)−1 g. 2

We show that the map Vπ : RS A → RS is Hadamard differentiable at M. Let H be any perturbation matrix and t > 0 sufficiently small. Using the matrix property A−1 − B −1 = A−1 (B − A)B −1 , we have Vπ (M + tH) − Vπ (M) = (I − γΠ(M + tH))−1 − (I − γΠM)−1 g = (I − γΠ(M + tH))−1 (γΠtH)(I − γΠM)−1 g = tγ(I − γΠ(M + tH))−1 ΠH Vπ (M). Dividing by t and taking t → 0, we get Vπ (M + tH) − Vπ (M) → γ(I − γΠM)−1 ΠH Vπ (M). t 2

′ ′ We define the linear map VM : RS A → RS by VM (H) := γ(I − γΠM)−1 ΠH Vπ (M). The ′ derivative VM is linear and continuous in H, hence for any Hn → H, we have

Vπ (M + tHn ) − Vπ (M) ′ − VM (H) → 0. t E Therefore, M 7→ Vπ (M) is Hadamard differentiable at M. Since Theorem 1 and Proposition 1 √ d establish that n vec(M̂∗ − M̂) − → N (0, Λ̄) conditionally on Dn —the same Gaussian law as 22

√

′ n vec(M̂ − M) in Su et al. [2026, Corollary 1]—the bootstrap delta method with derivative VM gives, conditionally on Dn in probability, √ d n(V̂π∗ − V̂π ) − → N (0, ΣπV ), √ where ΣπV is the asymptotic covariance of n(V̂π −Vπ ) in Su et al. [2026, Theorem 2]. The statement ′ for Qπ is analogous with VM replaced by the analogous Q′M and ΣπV replaced by ΣπQ .

OPR targets V⋆ and Q⋆ . We next derive the bootstrap consistency result for the OPR target V⋆ . The bootstrap consistency for Q⋆ is entirely analogous. The optimal-value functional M 7→ V⋆ (M) is not directly Hadamard differentiable, because the policy-selection map M 7→ π⋆ (M) involves an argmax. We resolve this via the non-degeneracy condition: min min Q⋆ (s, π⋆ (s)) − Q⋆ (s, a) > 0. s∈S a̸=π⋆ (s)

We claim that this condition implies that π⋆ is locally constant in a neighborhood of M. We denote the optimal Q-function under M′ by Q⋆ (M′ ). By the non-degeneracy condition, define ∆ := min min {Q⋆ (M; s, π⋆ (M; s)) − Q⋆ (M; s, a)} > 0. s∈S a̸=π⋆ (s)

Since the finite discounted optimal Bellman equation has a unique fixed point and the Bellman optimality operator is continuous in M′ , the map M′ 7→ Q⋆ (M′ ) is continuous. Hence there exists a neighborhood U of M such that, for every M′ ∈ U, max max |Q⋆ (M′ ; s, a) − Q⋆ (M; s, a)| < ∆/4. s∈S a∈A

Therefore, for every s ∈ S and every a ̸= π⋆ (M; s), Q⋆ (M′ ; s, π⋆ (M; s)) − Q⋆ (M′ ; s, a) = Q⋆ (M; s, π⋆ (M; s)) − Q⋆ (M; s, a) + [Q⋆ (M′ ; s, π⋆ (M; s)) − Q⋆ (M; s, π⋆ (M; s))] − [Q⋆ (M′ ; s, a) − Q⋆ (M; s, a)] ≥ Q⋆ (M; s, π⋆ (M; s)) − Q⋆ (M; s, a) − 2 max |Q⋆ (M′ ; s, a) − Q⋆ (M; s, a)| s,a

> ∆ − ∆/2 = ∆/2 > 0. ′

′

Thus π⋆ (M) = π⋆ (M ) for all M ∈ U. a.s.

By Su et al. [2026, Lemma 1], we have M̂ −−→ M. Then M̂ ∈ U and Π̂⋆ = Π⋆ for large n a.s. On this probability one event, the OPR functional locally coincides with the fixed-policy map M′ 7→ V⋆ (M′ ), which is Hadamard differentiable by the aforementioned OPE argument. We can ′ therefore apply the bootstrap delta method with the same derivative VM as in the OPE case. √ d Since Theorem 1 and Proposition 1 establish that n vec(M̂∗ − M̂) − → N (0, Λ̄) conditionally on Dn —the same Gaussian law as Su et al. [2026, Corollary 1]—applying the bootstrap delta method yields, conditional on Dn in probability, d √ n V̂⋆∗ − V̂⋆ − → N (0, ΣπV⋆ ), as n → ∞, √ where ΣπV⋆ is the asymptotic covariance of n(V̂⋆ −V⋆ ) in Su et al. [2026, Theorem 3]. The statement ′ for Q⋆ is analogous with VM replaced by the analogous Q′M and ΣπV⋆ replaced by ΣπQ⋆ .

(1, 0.7, 0)

(1, 0.6, 0) (1, 0.3, 0)

(0, 1, 1)

(1, 0.6, 0) (1, 0.3, 0)

2 (0, 1, 0) (1, 0.1, 0)

(1, 0.6, 0) (1, 0.3, 0)

3 (0, 1, 0) (1, 0.1, 0)

(1, 0.6, 0) (1, 0.3, 0)

4 (0, 1, 0) (1, 0.1, 0)

(1, 0.3, 10) (1, 0.3, 0)

5 (0, 1, 0) (1, 0.1, 0)

6 (0, 1, 0) (1, 0.7, 10)

Figure 1: The RiverSwim MDP with S = 6 states. Arc labels (a, p, r): action (0 = swim left, 1 = swim right), transition probability p, immediate reward r.

Details of Numerical Experiments

We evaluate finite-sample CI coverage of the proposed bootstrap on the RiverSwim problem [Strehl and Littman, 2004], replicating the experimental setup of the small state-space regime of Zhu et al. [2024]. Our RiverSwim state–action space has S = 6 states {1, . . . , 6} and A = 2 actions (0: swim left, 1: swim right). We set the rewards as r(1, 0) = 1, r(6, 1) = 10, r(s, a) = 0 otherwise, and discount factor γ = 0.95. Figure 1 illustrates the transition and reward structure of our RiverSwim setup. RiverSwim is designed to be difficult for exploration: the transition structure induces highly imbalanced visitation frequencies across state–action pairs, with upstream states (near state 6) visited far less frequently than downstream states (near state 1). Moreover, at its left-most state 1, the optimal policy is nearly degenerate, with Q⋆ (1, 0) ≈ Q⋆ (1, 1), thus the optimal action is only weakly identifiable. This places the problem near the boundary of optimal policy degeneracy and the transition probabilities for rarely visited state–action pairs are weakly estimated, thus the conditions for asymptotic normality in Proposition 2 are most strained. In all experiments, we employ a stationary behavior policy πb (1 | s) = 0.8 for all s. We use B = 1000 bootstrap replicates and Nreps = 1000 Monte Carlo replications, and compare the modelbased bootstrap (percentile and pivot CIs) against the episodic bootstrap [Hao et al., 2021] and plug-in CLT CIs [Zhu et al., 2024, Su et al., 2026]. We evaluate coverage at the nominal 95% level (α = 0.05) for the entries Q(1, 0), Q(3, 1), Q(6, 0), and V (1)–V (6); full results appear in Tables 2–7. Figures 2 and 3 display the coverages of the n ∈ {500, 1000} subset for the selected entries Q(1, 0), Q(3, 1), Q(6, 0), V (2), V (4), and V (5) in OPE and OPR, respectively. Appendices E.3 and E.4 report additional experiments at nominal 50% and 90%, respectively. Table 1 summarizes the settings of all experiments and the corresponding coverage tables; all coverage tables use a green cell-shading scheme described below. Cell shading. In all coverage tables, we shade the cells green in proportion to empirical coverage relative to the nominal level. White indicates coverage at or below a floor value; full green indicates coverage at or above nominal; intermediate shades indicate coverages between the floor and nominal. The floor values are 0.75 (nominal 95%), 0.70 (nominal 90%), and 0.30 (nominal 50%). For OPE, we conclude that the model-based bootstrap substantially outperforms the episodic bootstrap and plug-in CLT across all three target policies, with the percentile CI delivering the strongest overall performance and near-nominal coverage at n = 500–1000. The performance of the model-based bootstrap is weakest for entries associated with state 6, where visitation is sparse and the corresponding transition probabilities are weakly identified. Undercoverage at these entries persists at n = 100 and is most severe for the mostly-left policy. The episodic bootstrap fails to produce valid intervals at n = 50, where a single episode eliminates all bootstrap variation, and suffers undercoverage at n ≤ 500. The plug-in CI is moderately undercovered at n ≤ 100 for all policies. Coverage improves monotonically with n for all methods. The same conclusions hold at nominal 50% and 90% (Appendix E.3). For OPR, we conclude that the model-based bootstrap with percentile CI performs markedly better than the baselines and is the strongest method in the OPR study, achieving near-nominal coverage at n = 500–1000 for T = 50 and T = 100. The performance of the model-based bootstrap is weakest at T = 10, where coverage at n = 1000 remains below nominal, and coverage improves monotonically with T . The pivot CI undercovers at all (n, T ) combinations, most severely at Q⋆ (1, 0), where Q⋆ (1, 0) ≈ Q⋆ (1, 1) and the non-degeneracy condition in Proposition 2 is weakest. The episodic bootstrap collapses to zero coverage at n = 50 when T ≥ 50, where at most one complete episode is available. At T = 10 the collapse is avoided but coverage remains well below nominal. The plug-in CI severely undercovers at n ≤ 100 and approaches near-nominal performance only at n = 1000, T = 100 for the rightmost states and state-action pairs. Coverage improves 24

Uniform

Coverage Plug-in n = 500 0.15

(right) = 0.8

0.15

0.05

0.15

0.05

0.15

n = 1,000

MB percentile

0.15 MB pivot

(right) = 0.2

0.15

Episodic percentile

0.15 Episodic pivot

T = 50

Nominal 0.95

Figure 2: Empirical coverage relative to the Plug-in (CLT) baseline for Qπ (1, 0), Qπ (3, 1), Qπ (6, 0), V π (2), V π (4), V π (5) in RiverSwim. Horizontal lines mark the nominal 0.95 level for each entry. Columns correspond to the uniform, mostly-right, and mostly-left target policies, rows correspond to n ∈ {500, 1000}, and all panels use T = 50. This figure visualizes the n ∈ {500, 1000} subset of Tables 2–4. Labels Q1–Q3 and V2, V4, V5 correspond to these entries respectively. Full results appear in Tables 2–4. monotonically with n for all methods, and with T for the model-based bootstrap and plug-in CI. The same conclusions hold at nominal 50% and 90% (Appendix E.4). (a)

Handling zero counts. We handle state-action pairs where Ns = 0 in the bootstrap simulation as follows. In bootstrap simulation, we use the repaired kernel ( (a) (a) M̂s,· , Ns > 0, sim,(a) M̂s,· = (a) δs , Ns = 0, where δs is the point mass at s. We thus treat an unobserved state-action pair as a self-loop in bootstrap simulation rather than assigning fictitious transition probabilities. Similarly, if Ns = 0, we set π̂b (· | s) to the uniform distribution. Under Assumption 3, these rules are used with probability tending to zero and hence have no asymptotic effect. We organize the remainder of this appendix as follows. Appendix E.1 reports OPE (V π , Qπ ) results at nominal 95%; Appendix E.2 reports OPR (V⋆ , Q⋆ ) results at nominal 95%; Appendices E.3 and E.4 report OPE and OPR results at nominal 50% and 90%, respectively. Figures 4 and 5 display OPE coverages for the n ∈ {500, 1000} subset at nominal 50% and 90%; Figures 6 and 7 display the corresponding OPR results. E.1

OPE (V π , Qπ )

T = 10

Coverage Plug-in n = 500 0.6

T = 50

0.6

0.4

0.2

0.0

0.2

0.6

0.4

0.2

0.0

0.6

0.2

n = 1,000

MB percentile

0.2 MB pivot

T = 100

0.6

Episodic percentile

0.2 Episodic pivot

Nominal 0.95

Figure 3: Empirical coverage relative to the Plug-in (CLT) baseline for Q⋆ (1, 0), Q⋆ (3, 1), Q⋆ (6, 0), V⋆ (2), V⋆ (4), V⋆ (5) in RiverSwim. Horizontal lines mark the nominal 0.95 level for each entry. Columns correspond to T ∈ {10, 50, 100}, rows correspond to n ∈ {500, 1000}, and the target policy is optimal. This figure visualizes the n ∈ {500, 1000} subset of Tables 5–7. Labels Q1–Q3 and V2, V4, V5 correspond to these entries respectively. Full results for all n appear in Tables 5–7.

Table 1: Settings for all RiverSwim coverage tables in this appendix. K = n/T is the number of episodes. Policy abbreviations: uniform policy π(a | s) = 0.5; mostly-right policy π(1 | s) = 0.8; mostly-left policy π(0 | s) = 0.8; optimal policy π ⋆ . All experiments use B = 1000 bootstrap replicates and Nreps = 1000 Monte Carlo replications. Tables 2–4 report OPE coverages and Tables 5–7 report OPR coverages at nominal 95%. The 50% and 90% rows refer to additionalnominal-level tables in Appendices E.3 and E.4. Table 2 3 4 5 6 7 8 / 11 9 / 12 10 / 13 14 / 15 16 / 17 18 / 19

n {50, 100, 500, 1000} {50, 100, 500, 1000} {50, 100, 500, 1000} {50, 100, 500, 1000} {50, 100, 500, 1000} {100, 500, 1000} {50, 100, 500, 1000} {50, 100, 500, 1000} {50, 100, 500, 1000} {50, 100, 500, 1000} {50, 100, 500, 1000} {100, 500, 1000}

T 50 50 50 50 10 100 50 50 50 10 50 100

K {1, 2, 10, 20} {1, 2, 10, 20} {1, 2, 10, 20} {1, 2, 10, 20} {5, 10, 50, 100} {1, 5, 10} {1, 2, 10, 20} {1, 2, 10, 20} {1, 2, 10, 20} {5, 10, 50, 100} {1, 2, 10, 20} {1, 5, 10}

Nominal 95% 95% 95% 95% 95% 95% 50%, 90% 50%, 90% 50%, 90% 50%, 90% 50%, 90% 50%, 90%

Policy uniform mostly-right mostly-left optimal optimal optimal uniform mostly-right mostly-left optimal optimal optimal

Table 2: Empirical coverage (nominal 95%) for a fixed target policy π (uniform over actions) in RiverSwim. Comparison of model-based bootstrap (ours), episodic bootstrap, and plug-in CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.873 0.806 0.373 0.873 100 0.948 0.965 0.635 0.948 500 0.944 0.980 0.903 0.944 1000 0.947 0.961 0.924 0.947 Model-based bootstrap with percentile CI 50 0.896 0.886 0.182 0.896 100 0.937 0.958 0.333 0.937 500 0.950 0.961 0.892 0.950 0.952 0.954 0.964 0.952 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.546 0.575 0.535 0.546 500 0.906 0.933 0.854 0.906 1000 0.921 0.938 0.894 0.921 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.515 0.539 0.227 0.515 500 0.910 0.921 0.842 0.910 1000 0.931 0.933 0.940 0.931 Plug-in (CLT) CI 50 0.849 0.790 0.206 0.849 100 0.929 0.926 0.371 0.929 500 0.948 0.957 0.866 0.948 1000 0.949 0.955 0.937 0.949 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.856 0.957 0.950 0.946

0.794 0.959 0.959 0.952

0.664 0.946 0.989 0.972

0.494 0.804 0.952 0.942

0.374 0.629 0.874 0.927

0.882 0.938 0.953 0.948

0.870 0.946 0.956 0.952

0.629 0.905 0.970 0.964

0.435 0.669 0.980 0.971

0.229 0.362 0.896 0.966

0.000 0.551 0.912 0.922

0.000 0.566 0.926 0.935

0.000 0.575 0.957 0.950

0.000 0.431 0.898 0.909

0.000 0.535 0.818 0.891

0.000 0.519 0.915 0.933

0.000 0.530 0.915 0.936

0.000 0.512 0.944 0.943

0.000 0.476 0.934 0.944

0.000 0.228 0.829 0.936

0.810 0.929 0.952 0.947

0.777 0.922 0.952 0.951

0.619 0.899 0.964 0.959

0.358 0.603 0.945 0.951

0.315 0.405 0.822 0.922

Table 3: Empirical coverage (nominal 95%) for a fixed target policy π with π(right | s) = 0.8 for all s in RiverSwim. Comparison of model-based bootstrap (ours), episodic bootstrap, and plug-in CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.430 0.407 0.403 0.430 100 0.646 0.630 0.608 0.646 500 0.888 0.898 0.880 0.888 1000 0.898 0.908 0.907 0.898 Model-based bootstrap with percentile CI 50 0.430 0.431 0.095 0.430 100 0.670 0.671 0.299 0.670 500 0.955 0.959 0.956 0.955 0.943 0.942 0.972 0.943 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.436 0.398 0.522 0.436 500 0.863 0.868 0.821 0.863 1000 0.876 0.881 0.868 0.876 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.492 0.481 0.098 0.492 500 0.902 0.911 0.878 0.902 1000 0.919 0.923 0.942 0.919 Plug-in (CLT) CI 50 0.410 0.397 0.343 0.410 100 0.654 0.647 0.565 0.654 500 0.919 0.923 0.917 0.919 1000 0.919 0.923 0.921 0.919 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.430 0.642 0.890 0.897

0.408 0.632 0.895 0.906

0.395 0.623 0.902 0.909

0.371 0.591 0.921 0.922

0.358 0.558 0.879 0.925

0.430 0.670 0.956 0.944

0.431 0.671 0.958 0.945

0.432 0.672 0.963 0.946

0.433 0.673 0.970 0.949

0.263 0.500 0.980 0.965

0.000 0.441 0.862 0.870

0.000 0.410 0.865 0.877

0.000 0.362 0.870 0.876

0.000 0.291 0.877 0.882

0.000 0.431 0.818 0.886

0.000 0.491 0.903 0.919

0.000 0.485 0.910 0.925

0.000 0.480 0.906 0.927

0.000 0.469 0.908 0.920

0.000 0.204 0.907 0.929

0.405 0.653 0.920 0.919

0.396 0.645 0.925 0.922

0.384 0.631 0.918 0.925

0.367 0.594 0.922 0.930

0.349 0.566 0.911 0.931

Table 4: Empirical coverage (nominal 95%) for a fixed target policy π with π(right | s) = 0.2 for all s in RiverSwim. Comparison of model-based bootstrap (ours), episodic bootstrap, and plug-in CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.845 0.721 0.281 0.845 100 0.921 0.933 0.573 0.921 500 0.946 0.956 0.962 0.946 1000 0.944 0.952 0.962 0.944 Model-based bootstrap with percentile CI 50 0.780 0.710 0.392 0.780 100 0.910 0.867 0.550 0.910 500 0.944 0.952 0.890 0.944 0.947 0.948 0.950 0.947 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.560 0.598 0.490 0.560 500 0.903 0.924 0.947 0.903 1000 0.922 0.936 0.949 0.922 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.504 0.501 0.371 0.504 500 0.911 0.910 0.867 0.911 1000 0.932 0.929 0.941 0.932 Plug-in (CLT) CI 50 0.856 0.675 0.158 0.856 100 0.936 0.882 0.304 0.936 500 0.946 0.952 0.872 0.946 1000 0.948 0.947 0.936 0.948 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.825 0.919 0.947 0.943

0.705 0.908 0.945 0.944

0.501 0.830 0.951 0.937

0.331 0.718 0.976 0.969

0.276 0.571 0.959 0.963

0.762 0.899 0.943 0.949

0.638 0.875 0.944 0.949

0.408 0.796 0.948 0.951

0.308 0.680 0.967 0.957

0.402 0.588 0.891 0.958

0.000 0.564 0.901 0.919

0.000 0.578 0.906 0.915

0.000 0.545 0.899 0.933

0.000 0.419 0.931 0.955

0.000 0.490 0.937 0.941

0.000 0.501 0.911 0.930

0.000 0.484 0.907 0.931

0.000 0.451 0.918 0.934

0.000 0.406 0.953 0.948

0.000 0.379 0.868 0.944

0.810 0.933 0.947 0.945

0.685 0.898 0.948 0.947

0.475 0.822 0.944 0.944

0.302 0.663 0.931 0.943

0.175 0.319 0.867 0.946

E.2

OPR (V⋆ , Q⋆ )

Table 5: Empirical coverage (nominal 95%) for selected entries of Q⋆ and V⋆ in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap and plug-in CI, episode length T = 50. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 50 0.246 0.720 0.306 0.246 100 0.361 0.555 0.503 0.361 500 0.468 0.735 0.831 0.468 1000 0.471 0.801 0.887 0.471 Model-based bootstrap with percentile CI 50 0.433 0.433 0.289 0.433 100 0.667 0.670 0.501 0.667 500 0.957 0.953 0.971 0.957 0.938 0.945 0.960 0.938 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.159 0.251 0.369 0.159 500 0.444 0.698 0.776 0.444 1000 0.453 0.783 0.845 0.453 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 0.434 0.438 0.225 0.434 100 500 0.886 0.893 0.906 0.886 1000 0.905 0.911 0.923 0.905 Plug-in (CLT) CI 50 0.251 0.321 0.313 0.251 0.373 0.521 0.514 0.373 100 500 0.489 0.864 0.895 0.489 1000 0.497 0.885 0.927 0.497

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.609 0.498 0.613 0.676

0.742 0.554 0.707 0.781

0.316 0.503 0.784 0.856

0.309 0.509 0.827 0.893

0.286 0.466 0.834 0.901

0.433 0.668 0.956 0.933

0.433 0.670 0.953 0.945

0.430 0.668 0.958 0.945

0.429 0.669 0.964 0.947

0.325 0.555 0.970 0.950

0.000 0.225 0.590 0.657

0.000 0.247 0.676 0.764

0.000 0.213 0.749 0.826

0.000 0.225 0.783 0.849

0.000 0.290 0.776 0.861

0.000 0.432 0.890 0.904

0.000 0.438 0.893 0.911

0.000 0.430 0.882 0.911

0.000 0.428 0.880 0.912

0.000 0.293 0.899 0.911

0.306 0.465 0.772 0.846

0.318 0.521 0.864 0.885

0.323 0.526 0.880 0.914

0.321 0.515 0.882 0.924

0.306 0.500 0.880 0.925

Table 6: Empirical coverage (nominal 95%) for selected entries of Q⋆ and V⋆ in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap and plug-in CI, episode length T = 10. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 50 0.047 0.517 0.049 0.047 0.102 0.468 0.110 0.102 100 500 0.302 0.357 0.388 0.302 1000 0.375 0.484 0.555 0.375 Model-based bootstrap with percentile CI 50 0.115 0.115 0.014 0.115 100 0.237 0.237 0.048 0.237 500 0.748 0.748 0.337 0.748 0.899 0.901 0.648 0.899 1000 Episodic bootstrap with pivot CI 50 0.014 0.447 0.048 0.014 100 0.048 0.419 0.111 0.048 500 0.257 0.309 0.388 0.257 1000 0.365 0.472 0.544 0.365 Episodic bootstrap with percentile CI 50 0.115 0.114 0.006 0.115 100 0.234 0.233 0.032 0.234 0.716 0.717 0.276 0.716 500 1000 0.862 0.865 0.602 0.862 Plug-in (CLT) CI 50 0.043 0.043 0.037 0.043 100 0.092 0.105 0.084 0.092 500 0.328 0.438 0.388 0.328 1000 0.388 0.618 0.617 0.388

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.546 0.221 0.333 0.443

0.667 0.589 0.350 0.476

0.052 0.120 0.386 0.502

0.052 0.118 0.410 0.557

0.046 0.104 0.347 0.500

0.115 0.237 0.748 0.899

0.115 0.237 0.748 0.901

0.115 0.237 0.748 0.900

0.115 0.237 0.747 0.897

0.036 0.086 0.417 0.690

0.454 0.165 0.289 0.433

0.586 0.535 0.303 0.464

0.010 0.059 0.334 0.489

0.012 0.049 0.344 0.540

0.042 0.086 0.337 0.487

0.115 0.234 0.717 0.860

0.114 0.233 0.717 0.865

0.113 0.233 0.715 0.865

0.109 0.233 0.715 0.867

0.011 0.056 0.347 0.650

0.047 0.104 0.380 0.514

0.043 0.105 0.438 0.618

0.039 0.101 0.441 0.640

0.041 0.092 0.429 0.648

0.041 0.092 0.389 0.601

Table 7: Empirical coverage (nominal 95%) for selected entries of Q⋆ and V⋆ in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap, and plug-in CI, episode length T = 100. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 100 0.350 0.549 0.524 0.350 500 0.482 0.759 0.853 0.482 1000 0.502 0.842 0.902 0.502 Model-based bootstrap with percentile CI 100 0.689 0.693 0.566 0.689 500 0.949 0.953 0.975 0.949 1000 0.942 0.944 0.952 0.942 Episodic bootstrap with pivot CI 100 0.000 0.000 0.000 0.000 500 0.422 0.689 0.742 0.422 1000 0.476 0.808 0.855 0.476 Episodic bootstrap with percentile CI 100 0.000 0.000 0.000 0.000 500 0.842 0.842 0.838 0.842 1000 0.902 0.907 0.918 0.902 Plug-in (CLT) CI 100 0.366 0.560 0.571 0.366 500 0.499 0.875 0.915 0.499 1000 0.520 0.908 0.933 0.520

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.521 0.655 0.724

0.549 0.742 0.830

0.527 0.808 0.887

0.545 0.863 0.907

0.492 0.872 0.908

0.691 0.951 0.938

0.693 0.953 0.944

0.692 0.955 0.941

0.695 0.963 0.948

0.611 0.967 0.953

0.000 0.589 0.700

0.000 0.673 0.797

0.000 0.719 0.844

0.000 0.760 0.867

0.000 0.764 0.868

0.000 0.843 0.905

0.000 0.842 0.907

0.000 0.829 0.906

0.000 0.818 0.903

0.000 0.823 0.896

0.482 0.808 0.891

0.560 0.875 0.908

0.575 0.897 0.926

0.561 0.910 0.932

0.544 0.904 0.933

E.3

OPE: Additional Nominal Levels (50% and 90%) Uniform

Coverage Plug-in n = 500 0.1

(right) = 0.8

0.1

0.0

0.1

0.0

0.1

n = 1,000

0.0

0.1

MB percentile

0.1 MB pivot

(right) = 0.2

0.1

Episodic percentile

0.1 Episodic pivot

T = 50

Nominal 0.50

Figure 4: Empirical coverage relative to the Plug-in (CLT) baseline for Qπ (1, 0), Qπ (3, 1), Qπ (6, 0), V π (2), V π (4), V π (5) in RiverSwim at nominal 50%. Horizontal lines mark the nominal 0.50 level for each entry. Columns correspond to the uniform, mostly-right, and mostly-left target policies, rows correspond to n ∈ {500, 1000}, and all panels use T = 50. Full results appear in Tables 8–10.

Uniform

Coverage Plug-in n = 500 0.15

(right) = 0.8

0.15

0.05

0.15

0.05

0.15

n = 1,000

MB percentile

0.15 MB pivot

(right) = 0.2

0.15

Episodic percentile

0.15 Episodic pivot

T = 50

Nominal 0.90

Figure 5: Empirical coverage relative to the Plug-in (CLT) baseline for Qπ (1, 0), Qπ (3, 1), Qπ (6, 0), V π (2), V π (4), V π (5) in RiverSwim at nominal 90%. Horizontal lines mark the nominal 0.90 level for each entry. Columns correspond to the uniform, mostly-right, and mostly-left target policies, rows correspond to n ∈ {500, 1000}, and all panels use T = 50. Full results appear in Tables 11–13.

Table 8: Empirical coverage (nominal 50%) for a fixed target policy π (uniform over actions) in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.543 0.478 0.253 0.543 100 0.550 0.602 0.435 0.550 500 0.506 0.513 0.492 0.506 1000 0.502 0.502 0.489 0.502 Model-based bootstrap with percentile CI 50 0.432 0.471 0.104 0.432 100 0.499 0.570 0.184 0.499 500 0.515 0.494 0.538 0.515 0.492 0.489 0.521 0.492 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.302 0.361 0.286 0.302 500 0.481 0.486 0.444 0.481 1000 0.477 0.494 0.452 0.477 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.300 0.319 0.130 0.300 500 0.482 0.473 0.475 0.482 1000 0.475 0.480 0.470 0.475 Plug-in (CLT) CI 50 0.405 0.392 0.083 0.405 100 0.485 0.489 0.185 0.485 500 0.511 0.488 0.452 0.511 1000 0.493 0.485 0.479 0.493 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.548 0.571 0.505 0.497

0.457 0.586 0.515 0.496

0.375 0.582 0.532 0.511

0.262 0.504 0.521 0.492

0.255 0.453 0.502 0.506

0.434 0.507 0.500 0.483

0.444 0.536 0.494 0.476

0.239 0.541 0.522 0.501

0.301 0.503 0.540 0.512

0.084 0.155 0.519 0.551

0.000 0.306 0.467 0.480

0.000 0.338 0.479 0.488

0.000 0.386 0.472 0.497

0.000 0.273 0.465 0.458

0.000 0.292 0.422 0.446

0.000 0.312 0.487 0.478

0.000 0.323 0.477 0.464

0.000 0.309 0.467 0.484

0.000 0.284 0.478 0.466

0.000 0.127 0.445 0.490

0.416 0.479 0.500 0.485

0.392 0.484 0.486 0.484

0.284 0.456 0.488 0.489

0.174 0.305 0.485 0.482

0.077 0.140 0.440 0.497

Table 9: Empirical coverage (nominal 50%) for a fixed target policy π (mostly-right: π(1 | s) = 0.8) in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.271 0.224 0.232 0.271 100 0.427 0.406 0.422 0.427 500 0.507 0.508 0.483 0.507 1000 0.480 0.485 0.477 0.480 Model-based bootstrap with percentile CI 50 0.304 0.310 0.005 0.304 100 0.434 0.445 0.036 0.434 500 0.523 0.526 0.518 0.523 0.495 0.497 0.525 0.495 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.229 0.205 0.309 0.229 500 0.465 0.453 0.411 0.465 1000 0.444 0.449 0.452 0.444 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.240 0.237 0.077 0.240 500 0.470 0.465 0.447 0.470 1000 0.474 0.473 0.484 0.474 Plug-in (CLT) CI 50 0.195 0.188 0.119 0.195 100 0.332 0.324 0.208 0.332 500 0.503 0.499 0.462 0.503 1000 0.487 0.488 0.491 0.487 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.261 0.424 0.505 0.485

0.229 0.415 0.509 0.486

0.198 0.389 0.519 0.489

0.180 0.352 0.527 0.492

0.219 0.390 0.533 0.487

0.306 0.434 0.526 0.491

0.310 0.443 0.524 0.494

0.307 0.447 0.528 0.501

0.306 0.448 0.500 0.503

0.041 0.163 0.526 0.515

0.000 0.229 0.467 0.446

0.000 0.213 0.454 0.450

0.000 0.193 0.445 0.452

0.000 0.155 0.452 0.459

0.000 0.250 0.437 0.465

0.000 0.241 0.474 0.467

0.000 0.239 0.464 0.470

0.000 0.236 0.450 0.482

0.000 0.237 0.439 0.469

0.000 0.140 0.447 0.467

0.195 0.331 0.504 0.485

0.186 0.323 0.502 0.492

0.184 0.316 0.494 0.498

0.185 0.285 0.485 0.499

0.161 0.255 0.493 0.496

Table 10: Empirical coverage (nominal 50%) for a fixed target policy π (mostly-left: π(0 | s) = 0.8) in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.533 0.459 0.234 0.533 100 0.557 0.573 0.440 0.557 500 0.531 0.483 0.534 0.531 1000 0.506 0.512 0.519 0.506 Model-based bootstrap with percentile CI 50 0.389 0.296 0.229 0.389 100 0.511 0.444 0.312 0.511 500 0.523 0.495 0.498 0.523 0.493 0.490 0.501 0.493 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.318 0.375 0.249 0.318 500 0.495 0.466 0.514 0.495 1000 0.484 0.466 0.498 0.484 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.293 0.303 0.206 0.293 500 0.500 0.472 0.475 0.500 1000 0.479 0.462 0.480 0.479 Plug-in (CLT) CI 50 0.407 0.284 0.073 0.407 100 0.505 0.466 0.154 0.505 500 0.523 0.485 0.453 0.523 1000 0.497 0.502 0.494 0.497 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.530 0.559 0.519 0.499

0.449 0.560 0.514 0.505

0.294 0.500 0.519 0.513

0.145 0.359 0.511 0.517

0.227 0.445 0.520 0.521

0.364 0.506 0.514 0.501

0.297 0.475 0.511 0.494

0.087 0.404 0.521 0.507

0.036 0.325 0.518 0.499

0.238 0.324 0.501 0.512

0.000 0.317 0.492 0.477

0.000 0.351 0.487 0.477

0.000 0.354 0.493 0.478

0.000 0.313 0.498 0.498

0.000 0.255 0.473 0.497

0.000 0.310 0.495 0.475

0.000 0.296 0.482 0.469

0.000 0.322 0.490 0.475

0.000 0.308 0.474 0.480

0.000 0.203 0.462 0.480

0.391 0.510 0.520 0.496

0.331 0.480 0.504 0.503

0.230 0.426 0.514 0.502

0.143 0.323 0.461 0.495

0.077 0.142 0.432 0.488

Table 11: Empirical coverage (nominal 90%) for a fixed target policy π (uniform over actions) in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.842 0.784 0.365 0.842 100 0.912 0.952 0.621 0.912 500 0.903 0.935 0.850 0.903 0.888 0.906 0.884 0.888 1000 Model-based bootstrap with percentile CI 50 0.821 0.836 0.168 0.821 100 0.894 0.922 0.322 0.894 500 0.909 0.917 0.860 0.909 1000 0.896 0.903 0.930 0.896 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.546 0.575 0.535 0.546 500 0.863 0.888 0.790 0.863 1000 0.865 0.886 0.848 0.865 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 0.515 0.539 0.227 0.515 100 500 0.863 0.867 0.800 0.863 1000 0.874 0.891 0.896 0.874 Plug-in (CLT) CI 50 0.791 0.738 0.174 0.791 0.878 0.893 0.341 0.878 100 500 0.902 0.903 0.815 0.902 0.901 0.897 0.885 0.901 1000 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.834 0.925 0.904 0.899

0.772 0.936 0.919 0.905

0.649 0.934 0.957 0.938

0.479 0.785 0.911 0.894

0.362 0.614 0.829 0.879

0.814 0.893 0.903 0.896

0.811 0.917 0.911 0.899

0.560 0.861 0.926 0.918

0.433 0.662 0.946 0.929

0.183 0.324 0.871 0.935

0.000 0.551 0.871 0.871

0.000 0.566 0.875 0.876

0.000 0.575 0.907 0.898

0.000 0.431 0.838 0.866

0.000 0.535 0.752 0.841

0.000 0.519 0.867 0.878

0.000 0.530 0.866 0.884

0.000 0.512 0.889 0.896

0.000 0.476 0.877 0.898

0.000 0.228 0.781 0.877

0.770 0.872 0.899 0.895

0.723 0.881 0.906 0.897

0.570 0.855 0.914 0.906

0.342 0.565 0.889 0.896

0.246 0.344 0.772 0.878

Table 12: Empirical coverage (nominal 90%) for a fixed target policy π (mostly-right: π(1 | s) = 0.8) in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.424 0.390 0.393 0.424 100 0.637 0.618 0.595 0.637 500 0.858 0.864 0.839 0.858 1000 0.857 0.860 0.858 0.857 Model-based bootstrap with percentile CI 50 0.421 0.425 0.057 0.421 100 0.654 0.654 0.218 0.654 500 0.922 0.926 0.907 0.922 0.888 0.894 0.931 0.888 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.436 0.398 0.522 0.436 500 0.808 0.810 0.763 0.808 1000 0.822 0.825 0.819 0.822 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.492 0.481 0.098 0.492 500 0.859 0.865 0.843 0.859 1000 0.854 0.859 0.892 0.854 Plug-in (CLT) CI 50 0.393 0.372 0.308 0.393 100 0.632 0.612 0.515 0.632 500 0.877 0.885 0.861 0.877 1000 0.869 0.876 0.866 0.869 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.418 0.632 0.864 0.857

0.393 0.622 0.866 0.861

0.372 0.605 0.874 0.875

0.349 0.566 0.882 0.874

0.349 0.542 0.846 0.880

0.421 0.655 0.920 0.887

0.423 0.655 0.926 0.896

0.426 0.661 0.919 0.906

0.426 0.664 0.924 0.903

0.208 0.440 0.942 0.923

0.000 0.441 0.808 0.822

0.000 0.410 0.813 0.827

0.000 0.362 0.823 0.826

0.000 0.291 0.811 0.831

0.000 0.431 0.766 0.839

0.000 0.491 0.861 0.856

0.000 0.485 0.866 0.857

0.000 0.480 0.855 0.863

0.000 0.469 0.852 0.857

0.000 0.204 0.862 0.874

0.387 0.628 0.877 0.869

0.372 0.611 0.884 0.873

0.359 0.594 0.886 0.882

0.347 0.560 0.877 0.878

0.318 0.515 0.862 0.886

Table 13: Empirical coverage (nominal 90%) for a fixed target policy π (mostly-left: π(0 | s) = 0.8) in RiverSwim. Comparison of model-based bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 50. Qπ coverage n Q (1, 0) Qπ (3, 1) Qπ (6, 0) V π (1) Model-based bootstrap with pivot CI 50 0.821 0.694 0.280 0.821 100 0.878 0.911 0.567 0.878 500 0.907 0.909 0.922 0.907 1000 0.892 0.901 0.930 0.892 Model-based bootstrap with percentile CI 50 0.721 0.654 0.377 0.721 100 0.865 0.808 0.501 0.865 500 0.908 0.905 0.858 0.908 0.898 0.895 0.905 0.898 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.560 0.598 0.490 0.560 500 0.849 0.870 0.892 0.849 1000 0.871 0.888 0.905 0.871 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.504 0.501 0.371 0.504 500 0.856 0.860 0.833 0.856 1000 0.874 0.873 0.899 0.874 Plug-in (CLT) CI 50 0.793 0.621 0.144 0.793 100 0.889 0.842 0.288 0.889 500 0.908 0.903 0.822 0.908 1000 0.902 0.901 0.890 0.902 π

V (2)

V π coverage V π (3) V π (4)

V π (5)

V π (6)

0.802 0.884 0.907 0.889

0.684 0.873 0.911 0.897

0.468 0.794 0.906 0.906

0.292 0.668 0.937 0.930

0.274 0.565 0.910 0.922

0.696 0.850 0.905 0.893

0.594 0.819 0.905 0.897

0.356 0.740 0.904 0.897

0.224 0.644 0.922 0.907

0.391 0.545 0.871 0.916

0.000 0.564 0.861 0.870

0.000 0.578 0.861 0.866

0.000 0.545 0.865 0.875

0.000 0.419 0.879 0.907

0.000 0.490 0.877 0.895

0.000 0.501 0.854 0.883

0.000 0.484 0.851 0.881

0.000 0.451 0.864 0.885

0.000 0.406 0.895 0.903

0.000 0.379 0.829 0.898

0.769 0.885 0.909 0.896

0.635 0.861 0.906 0.903

0.421 0.777 0.907 0.897

0.276 0.620 0.868 0.893

0.155 0.276 0.818 0.889

E.4

OPR: Additional Nominal Levels (50% and 90%) T = 10

Coverage Plug-in n = 500

T = 50

T = 100

0.4

0.2

0.0

0.2

0.4

0.2

0.0

n = 1,000

0.2

MB percentile

0.2 MB pivot

Episodic percentile

0.2 Episodic pivot

Nominal 0.50

Figure 6: Empirical coverage relative to the Plug-in (CLT) baseline for Q⋆ (1, 0), Q⋆ (3, 1), Q⋆ (6, 0), V⋆ (2), V⋆ (4), V⋆ (5) in RiverSwim at nominal 50%. Horizontal lines mark the nominal 0.50 level for each entry. Columns correspond to T ∈ {10, 50, 100}, rows correspond to n ∈ {500, 1000}. Full results appear in Tables 14–18.

T = 10

Coverage Plug-in n = 500 0.6

T = 50

0.6

0.4

0.2

0.0

0.2

0.6

0.4

0.2

0.0

0.6

0.2

n = 1,000

MB percentile

0.2 MB pivot

T = 100

0.6

Episodic percentile

0.2

Episodic pivot

Nominal 0.90

Figure 7: Empirical coverage relative to the Plug-in (CLT) baseline for Q⋆ (1, 0), Q⋆ (3, 1), Q⋆ (6, 0), V⋆ (2), V⋆ (4), V⋆ (5) in RiverSwim at nominal 90%. Horizontal lines mark the nominal 0.90 level for each entry. Columns correspond to T ∈ {10, 50, 100}, rows correspond to n ∈ {500, 1000}. Full results appear in Tables 15–19. Table 14: Empirical coverage (nominal 50%) for Q⋆ and V⋆ in RiverSwim. Comparison of modelbased bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 10. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 50 0.013 0.177 0.028 0.013 100 0.037 0.087 0.066 0.037 500 0.186 0.236 0.246 0.186 0.263 0.355 0.361 0.263 1000 Model-based bootstrap with percentile CI 50 0.102 0.102 0.000 0.102 0.203 0.201 0.002 0.203 100 500 0.440 0.438 0.110 0.440 1000 0.486 0.489 0.337 0.486 Episodic bootstrap with pivot CI 50 0.002 0.222 0.043 0.002 100 0.019 0.098 0.095 0.019 500 0.139 0.183 0.253 0.139 1000 0.237 0.323 0.338 0.237 Episodic bootstrap with percentile CI 50 0.105 0.106 0.006 0.105 100 0.205 0.205 0.019 0.205 500 0.421 0.417 0.164 0.421 1000 0.475 0.480 0.323 0.475 Plug-in (CLT) CI 50 0.011 0.014 0.011 0.011 100 0.036 0.049 0.044 0.036 500 0.133 0.190 0.193 0.133 1000 0.203 0.326 0.326 0.203

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.102 0.053 0.220 0.328

0.245 0.108 0.234 0.351

0.017 0.053 0.247 0.368

0.016 0.055 0.251 0.370

0.027 0.057 0.223 0.326

0.101 0.202 0.442 0.489

0.102 0.201 0.438 0.489

0.102 0.201 0.437 0.490

0.102 0.196 0.439 0.485

0.001 0.015 0.206 0.427

0.106 0.036 0.168 0.295

0.293 0.125 0.180 0.320

0.008 0.030 0.191 0.332

0.010 0.034 0.195 0.326

0.040 0.074 0.210 0.298

0.105 0.204 0.419 0.473

0.106 0.205 0.417 0.480

0.104 0.206 0.423 0.466

0.101 0.203 0.421 0.463

0.011 0.045 0.220 0.402

0.016 0.049 0.183 0.320

0.014 0.049 0.190 0.326

0.013 0.049 0.204 0.321

0.026 0.055 0.199 0.318

0.025 0.048 0.183 0.301

Table 15: Empirical coverage (nominal 90%) for Q⋆ and V⋆ in RiverSwim. Comparison of modelbased bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 10. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 50 0.047 0.479 0.047 0.047 100 0.098 0.364 0.106 0.098 500 0.293 0.347 0.377 0.293 1000 0.364 0.469 0.548 0.364 Model-based bootstrap with percentile CI 50 0.115 0.115 0.011 0.115 100 0.237 0.237 0.035 0.237 500 0.730 0.729 0.292 0.730 0.860 0.862 0.607 0.860 1000 Episodic bootstrap with pivot CI 50 0.011 0.441 0.047 0.011 0.041 0.288 0.108 0.041 100 500 0.243 0.296 0.372 0.243 1000 0.343 0.452 0.519 0.343 Episodic bootstrap with percentile CI 50 0.115 0.114 0.006 0.115 100 0.232 0.232 0.030 0.232 500 0.677 0.681 0.253 0.677 1000 0.805 0.807 0.562 0.805 Plug-in (CLT) CI 50 0.034 0.038 0.034 0.034 100 0.078 0.096 0.078 0.078 500 0.283 0.393 0.350 0.283 1000 0.358 0.578 0.587 0.358

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.407 0.155 0.325 0.430

0.620 0.464 0.341 0.461

0.052 0.118 0.372 0.487

0.052 0.118 0.392 0.535

0.045 0.098 0.337 0.492

0.115 0.237 0.729 0.859

0.115 0.237 0.729 0.862

0.115 0.237 0.730 0.860

0.115 0.237 0.731 0.860

0.025 0.067 0.386 0.664

0.413 0.106 0.276 0.411

0.574 0.395 0.291 0.444

0.010 0.056 0.319 0.470

0.012 0.049 0.330 0.508

0.042 0.083 0.324 0.470

0.114 0.232 0.679 0.804

0.114 0.232 0.681 0.807

0.113 0.232 0.675 0.809

0.109 0.231 0.668 0.808

0.011 0.054 0.333 0.629

0.040 0.090 0.338 0.482

0.038 0.096 0.393 0.578

0.034 0.089 0.397 0.598

0.034 0.078 0.379 0.603

0.041 0.090 0.370 0.558

Table 16: Empirical coverage (nominal 50%) for Q⋆ and V⋆ in RiverSwim. Comparison of modelbased bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 50. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 50 0.100 0.234 0.191 0.100 100 0.164 0.237 0.335 0.164 500 0.262 0.451 0.476 0.262 1000 0.251 0.475 0.479 0.251 Model-based bootstrap with percentile CI 50 0.292 0.289 0.101 0.292 100 0.445 0.437 0.225 0.445 500 0.528 0.522 0.535 0.528 0.484 0.485 0.503 0.484 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 0.082 0.121 0.199 0.082 100 500 0.247 0.418 0.431 0.247 1000 0.235 0.444 0.449 0.235 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.225 0.221 0.139 0.225 500 0.472 0.461 0.456 0.472 1000 0.458 0.451 0.463 0.458 Plug-in (CLT) CI 50 0.102 0.171 0.163 0.102 100 0.180 0.278 0.261 0.180 500 0.288 0.472 0.488 0.288 1000 0.285 0.484 0.486 0.285

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.181 0.212 0.395 0.448

0.251 0.232 0.451 0.475

0.154 0.256 0.477 0.488

0.161 0.264 0.504 0.488

0.176 0.309 0.490 0.482

0.289 0.449 0.519 0.486

0.289 0.437 0.522 0.485

0.291 0.436 0.521 0.495

0.288 0.441 0.521 0.488

0.151 0.298 0.538 0.492

0.000 0.116 0.371 0.420

0.000 0.121 0.417 0.444

0.000 0.109 0.432 0.455

0.000 0.122 0.430 0.451

0.000 0.154 0.424 0.447

0.000 0.214 0.461 0.460

0.000 0.221 0.461 0.451

0.000 0.221 0.456 0.466

0.000 0.219 0.440 0.458

0.000 0.174 0.451 0.457

0.156 0.269 0.479 0.468

0.171 0.278 0.472 0.484

0.166 0.278 0.474 0.483

0.173 0.275 0.474 0.481

0.165 0.271 0.473 0.484

Table 17: Empirical coverage (nominal 90%) for Q⋆ and V⋆ in RiverSwim. Comparison of modelbased bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 50. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 50 0.230 0.633 0.298 0.230 0.333 0.476 0.487 0.333 100 500 0.453 0.718 0.806 0.453 1000 0.449 0.777 0.844 0.449 Model-based bootstrap with percentile CI 50 0.421 0.418 0.251 0.421 100 0.648 0.649 0.466 0.648 500 0.913 0.917 0.935 0.913 0.874 0.883 0.907 0.874 1000 Episodic bootstrap with pivot CI 50 0.000 0.000 0.000 0.000 100 0.159 0.251 0.369 0.159 500 0.416 0.668 0.720 0.416 1000 0.428 0.754 0.803 0.428 Episodic bootstrap with percentile CI 50 0.000 0.000 0.000 0.000 100 0.434 0.438 0.225 0.434 0.835 0.842 0.854 0.835 500 1000 0.843 0.849 0.865 0.843 Plug-in (CLT) CI 50 0.231 0.300 0.296 0.231 100 0.349 0.490 0.484 0.349 500 0.469 0.818 0.853 0.469 1000 0.478 0.839 0.880 0.478

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.531 0.422 0.599 0.655

0.650 0.474 0.694 0.762

0.300 0.453 0.763 0.828

0.295 0.468 0.803 0.855

0.278 0.461 0.809 0.861

0.419 0.651 0.913 0.877

0.418 0.649 0.917 0.883

0.421 0.652 0.919 0.897

0.415 0.651 0.918 0.896

0.303 0.520 0.922 0.902

0.000 0.225 0.562 0.636

0.000 0.247 0.652 0.742

0.000 0.213 0.701 0.800

0.000 0.225 0.736 0.806

0.000 0.290 0.733 0.819

0.000 0.432 0.833 0.848

0.000 0.438 0.842 0.849

0.000 0.430 0.827 0.860

0.000 0.428 0.817 0.852

0.000 0.293 0.847 0.858

0.288 0.440 0.752 0.821

0.299 0.490 0.818 0.839

0.302 0.495 0.832 0.870

0.295 0.477 0.835 0.875

0.294 0.468 0.823 0.880

Table 18: Empirical coverage (nominal 50%) for Q⋆ and V⋆ in RiverSwim. Comparison of modelbased bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 100. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 100 0.156 0.226 0.343 0.156 500 0.244 0.486 0.467 0.244 1000 0.291 0.507 0.505 0.291 Model-based bootstrap with percentile CI 100 0.447 0.444 0.276 0.447 500 0.504 0.522 0.515 0.504 1000 0.529 0.523 0.524 0.529 Episodic bootstrap with pivot CI 100 0.000 0.000 0.000 0.000 500 0.208 0.407 0.393 0.208 1000 0.272 0.462 0.456 0.272 Episodic bootstrap with percentile CI 100 0.000 0.000 0.000 0.000 500 0.434 0.444 0.427 0.434 1000 0.487 0.480 0.469 0.487 Plug-in (CLT) CI 100 0.176 0.284 0.301 0.176 500 0.272 0.497 0.481 0.272 1000 0.324 0.519 0.502 0.324

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.207 0.416 0.506

0.219 0.484 0.507

0.263 0.489 0.511

0.278 0.497 0.505

0.311 0.496 0.506

0.451 0.507 0.531

0.444 0.522 0.523

0.452 0.523 0.524

0.453 0.501 0.521

0.339 0.511 0.516

0.000 0.355 0.448

0.000 0.404 0.462

0.000 0.412 0.478

0.000 0.419 0.464

0.000 0.410 0.461

0.000 0.440 0.481

0.000 0.444 0.480

0.000 0.422 0.480

0.000 0.433 0.468

0.000 0.421 0.469

0.277 0.481 0.512

0.284 0.497 0.519

0.294 0.492 0.516

0.303 0.479 0.502

0.276 0.478 0.506

Table 19: Empirical coverage (nominal 90%) for Q⋆ and V⋆ in RiverSwim. Comparison of modelbased bootstrap, episodic bootstrap, and plug-in (CLT) CI, episode length T = 100. Q⋆ coverage n Q⋆ (1, 0) Q⋆ (3, 1) Q⋆ (6, 0) V⋆ (1) Model-based bootstrap with pivot CI 100 0.333 0.492 0.512 0.333 500 0.469 0.743 0.821 0.469 1000 0.479 0.819 0.865 0.479 Model-based bootstrap with percentile CI 100 0.662 0.662 0.529 0.662 500 0.907 0.900 0.944 0.907 0.897 0.903 0.918 0.897 1000 Episodic bootstrap with pivot CI 100 0.000 0.000 0.000 0.000 500 0.396 0.661 0.715 0.396 1000 0.455 0.779 0.817 0.455 Episodic bootstrap with percentile CI 100 0.000 0.000 0.000 0.000 500 0.795 0.776 0.794 0.795 1000 0.854 0.857 0.869 0.854 Plug-in (CLT) CI 100 0.355 0.539 0.537 0.355 500 0.485 0.829 0.878 0.485 1000 0.506 0.870 0.891 0.506

V⋆ (2)

V⋆ coverage V⋆ (3) V⋆ (4)

V⋆ (5)

V⋆ (6)

0.460 0.635 0.706

0.485 0.726 0.811

0.477 0.786 0.855

0.515 0.841 0.870

0.483 0.843 0.875

0.661 0.907 0.902

0.662 0.900 0.903

0.660 0.905 0.903

0.667 0.917 0.905

0.580 0.937 0.899

0.000 0.566 0.676

0.000 0.648 0.774

0.000 0.697 0.811

0.000 0.733 0.828

0.000 0.733 0.813

0.000 0.790 0.851

0.000 0.776 0.857

0.000 0.782 0.854

0.000 0.763 0.856

0.000 0.786 0.857

0.468 0.791 0.873

0.539 0.829 0.870

0.540 0.860 0.880

0.524 0.873 0.890

0.516 0.861 0.885

Record · ID 178880 · SHA-256 8d8164531031fd44
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.