Self-Checking Anytime Value Intervals on Shifted Offline RL Benchmarks

Before deploying a reinforcement-learning policy in a hospital or a robot, one wants to know how well it will perform using only logged data from other policies. This task is called off-policy evaluation. Most methods return a single number with no statement of how wrong it might be. A different family of methods instead returns a guaranteed range. These iterative bound refinement methods keep a lower and an upper bound on the true value and squeeze them together step by step, so that stopping at any moment still yields a valid range. Lipschitz Value Iteration is the clearest example. It assumes the value function cannot change faster than a known rate $\eta$, a Lipschitz constant, across nearby states and actions. On that assumption it builds shrinking envelopes around the true value. These methods have been tested only on toy and simulator tasks with good data coverage. The standard benchmark for off-policy evaluation, where coverage is poor and estimators collapse, has never been run on them.

This note proposes to close that gap with one specific twist. Bound refinement methods have a self-diagnostic that point estimators lack. If the assumed $\eta$ is too small, the upper bound eventually drops below the lower bound, and the method shows that its own assumption is false. We propose to use this "bound crossing" signal to set $\eta$ from the data. We then audit, on benchmarks with known ground-truth returns, whether the absence of crossing actually predicts that the interval contains the truth. A second question is whether the resulting intervals are tight enough to make decisions, such as certifying which of several candidate policies is best and stopping computation once that is known.

Core Claim

We claim three things, each testable. First, the smallest $\eta$ at which Lipschitz Value Iteration's envelopes stop crossing is a data-driven floor on the admissible constant, and inflating it by a small factor gives intervals that cover ground truth at a rate we can measure. Second, crossing is necessary but not sufficient for an assumption to be valid, so the important empirical number is how often intervals miss the truth without any crossing. We call these silent failures. Third, the anytime property is worth something in practice. On policy selection, refining bounds only until one candidate's lower bound exceeds every rival's upper bound should cut compute substantially. It should also yield either a certified choice or an explicit statement that the data cannot separate the candidates. Point estimators never give that statement, and the benchmark data show they badly need it.

Prior Work and Positioning

The method comes from Off-Policy Interval Estimation with Lipschitz Value Iteration, with its conference version at Off-Policy Interval Estimation with Lipschitz Value Iteration. That work builds upper and lower Lipschitz envelopes over logged transitions and proves monotone, geometrically fast contraction. It shows the intervals cover the truth on a 1D task, Pendulum and an HIV simulator, where importance sampling gives near-zero lower bounds. It assumes $\eta$ is given, and notes that a too-small $\eta$ shows up as crossing bounds. We reuse its operator and its subsampling trick unchanged. Our additions are turning the crossing observation into a calibration procedure and testing it where coverage is poor.

The motivation comes from Benchmarks for Deep Off-Policy Evaluation, known as DOPE. It benchmarks point estimators: fitted Q-evaluation, model-based rollouts, importance sampling, doubly robust estimators, the DICE family of distribution-correction estimators, and the variational power method. It reports top rank correlation of about 0.69 on the well-covered RL Unplugged tasks, about 0.25 on the D4RL tasks with distribution shift, and no better than chance on AntMaze. DOPE contains no anytime interval method, so this proposal fills the evaluation cell DOPE left empty. The datasets come from D4RL.

Two interval methods built on different principles serve as competitors and as constraints on our expectations. CoinDICE builds confidence intervals from empirical likelihood over a ratio that reweights how often the data policy and the target policy visit each state-action pair. It keeps 95% coverage on Taxi with 20 trajectories, where bootstrap and Student's $t$ fail. It needs a saddle-point solve that can stall in poor local solutions with neural networks, and it was never run on D4RL. Deeply-Debiased Off-Policy Interval Estimation shows that standard double reinforcement learning loses nominal 0.9 coverage when its learned helper models converge slowly. Its triply robust correction restores coverage on CartPole and an OhioT1DM-based simulator. Both papers give statistical intervals, which are correct with high probability, rather than deterministic envelopes under a structural assumption. Neither has a built-in falsification signal.

The idea of stopping refinement once an interval clears a decision threshold comes from Gaussian quadrature for matrix inverse forms with applications. That paper stops Lanczos-based bounds as soon as they exclude an acceptance threshold and reports more than 800x speedups for determinantal point process sampling on Slashdot. We transfer the same stopping logic to pairwise comparisons between policies.

Research Program

The core object is the envelope update of Lipschitz Value Iteration. For logged transitions $(s_i,a_i,r_i,s_i')$, a target policy $\pi$, discount $\gamma$, a distance $d$ on state-action pairs, and constant $\eta$, the upper envelope is updated as

$$U_{t+1}(x)=\min_i\Big[r_i+\gamma\,U_t(s_i',\pi(s_i'))+\eta\,d\big(x,(s_i,a_i)\big)\Big].$$

The lower envelope $L_{t+1}$ is updated symmetrically with max and minus. Under a valid $\eta$ the two envelopes sandwich the true action-value function, the expected return from taking an action and then following $\pi$. Policy value bounds come from averaging the envelopes over initial states.

The calibration procedure runs a geometric sweep of $\eta$ downward from a deliberately loose value. It records $\hat\eta_{\min}$, the smallest value at which no logged state-action pair shows $U<L$ after convergence. We report intervals at $\eta=c\,\hat\eta_{\min}$ for a small grid of $c\ge 1$. The sweep reuses warm-started envelopes, so its cost is a modest multiple of a single run.

We build a single harness that wraps the DOPE task suites, both RL Unplugged and D4RL, and treats every estimator as a function from data and policy to an interval. We run each task with state features standardized per dimension, and as an ablation with $d$ computed in the embedding of a dynamics model trained on a held-out data split. The embedding tests whether a better metric, not a better operator, is what removes vacuous widths.

For policy selection we compute interval pairs for all DOPE candidate policies on a task. We refine them in the order that most reduces overlap with the current leader, and stop when the leader's lower bound exceeds every rival's upper bound or the compute budget runs out.

Baselines

The naive reference is the trivial interval from reward bounds, $[r_{\min}, r_{\max}]/(1-\gamma)$. Any method whose width is not clearly smaller than this is vacuous. We report width as a fraction of it so readers can judge vacuity directly. For ranking, the naive reference is random ordering, which DOPE shows is the effective level of every non-importance-sampling estimator on AntMaze.

The strongest point-estimate competitor is the best DOPE estimator per domain. This is fitted Q-evaluation or the autoregressive model-based estimator, which reaches 0.90+ rank correlation on several RL Unplugged tasks. On rank correlation the target figures are DOPE's reported top values of about 0.69 on RL Unplugged and about 0.25 on D4RL. Matching about 0.69 on RL Unplugged while beating about 0.25 on D4RL using interval midpoints would be a clear win. On D4RL alone, the bar is certified selections whose Regret@1 is no worse than the best point estimator's, with no silent failures. We use DOPE's released policies and ground-truth values, so the comparison involves no retraining.

The strongest interval competitor is a bootstrap over fitted Q-evaluation. It is the obvious recipe and is cheap, but no reported result was found on Lacuna for bootstrapped fitted Q-evaluation intervals on DOPE, so we establish that number ourselves. Next to it we run CoinDICE, whose only reported anchor in the file is 95% coverage on Taxi with 20 trajectories. No reported result was found on Lacuna for CoinDICE on D4RL. We also run the triply robust estimator of Deeply-Debiased Off-Policy Interval Estimation, whose reported anchor is holding the nominal 0.9 coverage where standard double reinforcement learning falls below it. All interval methods get the same data, the same wall-clock budget per policy on the same GPU, and the same tuning budget of 20 configurations, selected on a validation set of policies disjoint from the test policies. Beating them means equal or higher coverage at nominal level with smaller median normalized width, or the same width with fewer silent failures.

Two ablations isolate the key ingredient. The first replaces crossing calibration with $\eta$ estimated as the maximum gradient norm of a fitted Q-network over the data. The second fixes $\eta$ at the best value chosen with oracle access to ground truth. The gap between calibrated and oracle $\eta$ measures what the self-check leaves on the table. The gap between calibrated and gradient-norm $\eta$ measures whether the self-check adds anything at all.

Why not just…?

Why not just bootstrap fitted Q-evaluation and skip the envelopes? This is the real threat. Bootstrap intervals are cheap and will often be narrower. The evidence against relying on them is indirect. CoinDICE shows bootstrap undercovers at small sample sizes, and DOPE shows fitted Q-evaluation itself is badly biased under shift, which resampling cannot fix. Our coverage audit settles it on the same tasks. If bootstrap matches calibrated Lipschitz Value Iteration's coverage on D4RL at lower width, we will report that the envelope machinery is not worth it there. The remaining argument for envelopes would then be the crossing signal and anytime stopping.

Why not just estimate $\eta$ from a fitted network's gradients? A network's gradient norm reflects the network, not the true value function, and it can underestimate sharp value changes near terminal or goal states. Those states are exactly where AntMaze is hard. This is run as an ablation. If it matches crossing calibration on coverage, the calibration procedure is unnecessary and we will say so.

Why not just use CoinDICE or triply robust intervals, which need no Lipschitz assumption? They replace a structural assumption with assumptions about the optimizer and the convergence of helper models, and neither offers an internal signal when those assumptions fail. They are run head-to-head. The comparison of interest is silent failure rate as a function of state dimension, which also answers the open question of where Lipschitz bounds become vacuous relative to empirical likelihood.

Why not just keep point estimators and add more data? DOPE's AntMaze result shows that collapse there is not a sample-size problem the estimator can detect. An interval method that reports "cannot separate" on AntMaze is more useful than a confident wrong ranking, and we measure exactly that.

Proposed Experiments

The first decisive check is the silent-failure audit. Across all DOPE tasks and policies, we tabulate coverage of ground truth separately for runs with and without crossing at the chosen $\eta$. The hypothesis fails if silent failures exceed the nominal miss rate of the statistical baselines. In that case the self-check is unreliable and the method's advantage disappears.

The second check is the vacuity map. We plot normalized width against state dimension and dataset type, from Hopper up through the 39-dimensional Adroit tasks and the AntMaze variants, comparing raw-feature and learned-embedding metrics. This locates where the covering-radius limit makes envelopes useless, which the original paper leaves unquantified.

The third check is certified selection. On each task we report Regret@1, the fraction of tasks where a certificate is issued, and the compute saved by early stopping relative to running every interval to convergence. Success means certificates are issued on most RL Unplugged tasks, with no incorrect certificate anywhere. On AntMaze we expect the method to decline to certify, and declining there is the correct output rather than a failure.

A final sanity check reruns the original 1D, Pendulum and HIV settings through our harness. It confirms that calibrated $\eta$ reproduces the published behavior of always covering the truth and avoiding importance sampling's near-zero lower bound. This rules out a harness bug before any negative D4RL finding is interpreted.