Offline reinforcement learning practitioners usually train a family of value functions of growing size, from small networks to large ones, and must pick one using only logged data. The best existing rule of this kind, ModBE, starts with the smallest class and moves to the next larger one only when a one-sided statistical test shows the larger class reduces Bellman error, meaning the error in the value function's one-step consistency, by more than noise would explain. Its threshold assumes the logged transitions are independent. Real logs are long, correlated trajectories. A patient's vitals at hour 10 depend on hour 9, and a robot's state depends on its last state. Under that correlation the test's noise level is mis-estimated, so the rule graduates to bigger models too early or too late, and nobody has measured by how much.
We propose to recalibrate the graduation test itself. The statistic ModBE compares is a paired difference in per-transition loss between two nested model classes. The quantity that sets the test's noise level is therefore how long that difference sequence stays correlated over time. That is not the environment's mixing time (how quickly the state process forgets where it started), and it is not reward autocorrelation. We estimate the difference sequence's variance with a block bootstrap, which resamples contiguous stretches of a trajectory rather than single transitions. We pick the block length with a doubling rule that needs no prior knowledge of the mixing time. The result is a selection rule that keeps ModBE's fast rate where independence roughly holds and stays honestly calibrated when the data are a few long, sticky trajectories.
Core Claim
The claim is that, for nested-class model selection on correlated logs, the right correction targets the autocorrelation of the loss-difference process between adjacent classes, $d_t = \ell(f_k; z_t) - \ell(f_{k+1}; z_t)$. Here $\ell$ is the per-transition Bellman-error loss, $f_k$ is the fitted value function from class $\mathcal{F}_k$, and $z_t$ is the transition at time $t$. The test graduates from $\mathcal{F}_k$ to $\mathcal{F}_{k+1}$ when
$$\bar d_n > z_{1-\alpha}\,\hat\sigma_b / \sqrt{n}, \qquad \sigma^2 = \mathrm{Var}(d_t)\Big(1 + 2\sum_{j\ge 1}\rho_d(j)\Big),$$
where $n$ is the number of transitions, $\alpha$ the test level, $\hat\sigma_b$ the block-bootstrap estimate of the long-run standard deviation $\sigma$ at block length $b$, and $\rho_d(j)$ the lag-$j$ autocorrelation of $d_t$.
The long-run variance formula is the standard central limit result for mixing sequences. Two consequences follow from it.
The first is a miscalibration whose direction cannot be fixed by a blanket correction. Positive autocorrelation in $d_t$ makes the independence threshold too small, which produces premature graduation to large classes. Paired cancellation, where both models fail on the same hard stretches, can make $d_t$ far less correlated than the raw losses. A blanket mixing-time inflation, such as the one implied by the Markov-chain bounds in PAC-Bayesian Reinforcement Learning Trains Generalizable Policies, would then waste power.
The second is a conjecture we will try to prove. The graduation rule should satisfy a ModBE-style oracle inequality at rate $\sqrt{\tau_d / n}$, where $\tau_d \le \tau_{\text{mix}}$ is the effective correlation length of the difference process. The $\sqrt{\tau/n}$ form comes from the effective sample size $n/\tau$ of a mixing sequence.
Relation to Prior Work
Two papers supply the method.
Oracle Inequalities for Model Selection in Offline Reinforcement Learning introduced the one-sided excess Bellman error test over nested classes. It proves $1/\sqrt{n}$ oracle inequalities that avoid the $n^{-1/4}$ rate of naive two-sided validation. Its analysis assumes independent transitions. We keep its test structure and replace its threshold.
Bootstrapping Fitted Q-Evaluation for Off-Policy Inference proved that resampling individual transitions destroys temporal dependence and underestimates variance, and that resampling whole episodes is valid. It does this for evaluating one policy in one fixed class, and its intervals degrade below about 50 episodes. We reuse its resampling logic and apply it to the paired difference between classes. We also move it to within-trajectory blocks, so it works with few or single trajectories.
Three papers motivate the gap.
Pessimistic Model Selection for Offline Deep Reinforcement Learning is the closest existing method on correlated logs. It splits the log into temporal chunks, scores candidates with doubly robust value estimates, and picks the candidate with the highest lower confidence bound. It treats candidates as an unordered set, relies on asymptotic normality across chunks, and does not test excess risk between nested classes. We differ on all three points.
Structural Risk Minimization for Learning Nonlinear Dynamics shows that capacity penalties track the U-shaped test-error curve over nested classes. Its authors explicitly leave dependent, stochastic data streams open, and that is the regime we target.
Model Selection in Batch Policy Optimization constrains our ambitions. It proves that no offline selector can adapt simultaneously to approximation error, statistical complexity, and coverage. We therefore assume adequate coverage, as ModBE does, and claim adaptivity only to the first two plus temporal correlation.
For choosing the block length without knowing the mixing time, we borrow the geometric-doubling idea from Adapting to Mixing Time in Stochastic Optimization with Markovian Data. That paper uses doubling levels inside a gradient estimator. We use doubling block lengths $b = 1, 2, 4, \dots$ and stop when successive variance estimates agree within a tolerance, in the style of Lepski's method. This avoids the variance spikes that the same paper reports for unbounded telescoping.
Research Program
The work has three parts.
The first is the estimator and test. We will implement block-bootstrap calibration of ModBE's paired statistic with adaptive block length, on top of Fitted Q-Iteration (FQI) over two-layer networks of increasing width. This is the hierarchy ModBE itself uses. The implementation will handle three data shapes: many short episodes, a few long episodes, and one long non-episodic trajectory.
The second is analysis. We will bound the test's size and power under β-mixing (a standard notion of how fast dependence decays) of the logged process. We will then translate that into an oracle inequality in terms of $\tau_d$. Separately, we will characterize when $\tau_d$ is much smaller than $\tau_{\text{mix}}$, namely when the two classes' errors are driven by shared slowly varying state features.
The third is a controlled study of the tension between one-sided testing and pessimism. Both ModBE and the lower-confidence-bound rule are given the same correlation-calibrated variance, which lets us ask on correlated data whether conservatism or sharpness is the right default.
Baselines
The naive reference points are two. The first always picks the largest class, which is the cheapest rule practitioners use. The second is random hold-out validation of Bellman error, which ModBE reports was fooled by optimization noise on MountainCar. All selectors receive the same logged datasets, the same trained candidate networks, and the same number of evaluation passes, so the only difference between them is the selection rule.
The strongest nested-class competitor is ModBE as published, with its independence-based threshold. On CartPole and MountainCar its paper reports matching the oracle class, but no reported result was found on Lacuna for numerical values. Beating it means two things. On data with low correlation, the selected class and policy regret must be no worse. On sticky-trajectory variants, the false-graduation rate must stay at the nominal level where ModBE's does not, and regret must be lower.
The strongest unordered competitor on correlated logs is Pessimistic Model Selection. It reports a Pearson correlation of 0.895 between estimated and true policy value on its MuJoCo experiments, against 0.609 for the approximate-model baseline. Its regret numbers are not given in the file. We run it with its published chunk count on the same candidate pool. To beat it, we must show lower selection regret at equal data, especially when there are few trajectories.
On the Sepsis simulator, the two-stage selector from Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settings reports Spearman ρ = 0.89 for its fitted-Q-evaluation ranking. We use that as the bar for ranking quality.
The ablation that isolates our key ingredient replaces the paired-difference block bootstrap with three things. The first is a transition-level bootstrap. The second is a threshold inflated by a mixing-time estimate derived from reward autocorrelation, following the PAC-Bayes paper above. The third is a fixed block length.
Why not just…?
Why not just thin the data, keeping every τ-th transition, and run ModBE unchanged? This is the most serious threat. If the mixing time were known, thinning would restore near-independence with no new machinery. In practice τ must be estimated. The PAC-Bayes paper above notes that estimates based on reward autocorrelation tend to come out too small, which would leave the test miscalibrated. Thinning also discards a factor of τ in data even when the paired difference decorrelates much faster. We will run thinning at the true τ, which is known in the synthetic chains, and at an estimated τ. If thinning at the estimated τ matches our selector's size and regret, the contribution reduces to "thin your data," and we will report that.
Why not just run PMS, but order the candidates by size? Ordering alone does not change PMS's statistic. PMS still compares lower confidence bounds on absolute values, a two-sided comparison. ModBE argues this comparison is too conservative relative to excess-risk tests, so ordering only changes tie-breaking. The shared-variance comparison in our research program tests this directly.
Why not just bootstrap whole episodes, as in the fitted-Q-evaluation bootstrap paper? When episodes are plentiful, that is essentially our method with block length equal to the episode length, and we expect it to work. It is included as a baseline. It fails by construction for a single long trajectory, and it is documented to underestimate variance below about 50 episodes. Those regimes are where we expect adaptive within-trajectory blocks to matter.
Proposed Experiments
The synthetic study uses a two-state Markov chain with tunable stickiness, after the Dorfman and Levy experiments, feeding linear-in-features value classes of increasing degree. Because the minimal complete class and τ are known, we can measure the false-graduation rate, power, and selected index exactly as correlation grows. The decisive check is that independence-calibrated ModBE's false-graduation rate rises well above α as stickiness increases, while ours stays near α without power collapsing. If ModBE stays calibrated, the premise is wrong.
We then repeat ModBE's own CartPole and MountainCar setups. Each is run once in the regime of many short episodes and once with data reshaped into fewer, longer rollouts generated by a sticky behavior policy.
Finally, we use the Sepsis simulator with 20, 50, and 200 patient trajectories, and offline HalfCheetah and Walker2d logs. On these we report selection regret against the oracle class, Spearman rank correlation with true values, and selected class size.
A second decisive check is to compute $\tau_d$ and $\tau_{\text{mix}}$ empirically on each benchmark. If they are never meaningfully different, the paired-difference insight adds nothing beyond a generic mixing correction, and we would say so.
References
- PAC-Bayesian Reinforcement Learning Trains Generalizable Policies
- Oracle Inequalities for Model Selection in Offline Reinforcement Learning
- Bootstrapping Fitted Q-Evaluation for Off-Policy Inference
- Pessimistic Model Selection for Offline Deep Reinforcement Learning
- Structural Risk Minimization for Learning Nonlinear Dynamics
- Model Selection in Batch Policy Optimization
- Adapting to Mixing Time in Stochastic Optimization with Markovian Data
- Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settings