Measuring When Bootstrapping Breaks: Random-Feature Bandwidth as a Coverage Dial in Offline RL

Offline reinforcement learning trains a decision-making policy from a fixed log of past experience, with no further interaction. A string of lower bounds shows this can fail even when things look ideal. Two conditions seem as if they should be enough: the model family contains the true value function ("realizability"), and the data spans every direction of the feature space ("coverage"). They are not. The failure comes from bootstrapping. Each value estimate is regressed onto the model's own next-step prediction, and the small error from squeezing that target back into the model family can grow geometrically over the horizon. What is missing is a way to see this failure coming on a real dataset. The lower bounds identify adversarial instances. They do not tell a practitioner whether their own features and data will amplify error.

We propose to use random Fourier features as a controlled instrument for exactly this question. Random Fourier features are an explicit, randomly sampled feature map whose inner products approximate a smooth kernel such as the Gaussian. In these features, two numbers, the kernel bandwidth and the feature count, move a representation smoothly between "too coarse to represent the value function" and "too fine to be covered by the data." We will derive and validate a statistic computable from the data alone that predicts how much a linear value estimator built on these features will amplify error per step. We then use it to choose bandwidth, width, and regularization so that approximation error and amplification are balanced. The two-sentence version: realizability and coverage trade off along a single knob in kernel features, and that trade-off can be estimated from data before trusting any value estimate. If the estimated amplification factor predicts actual off-policy evaluation error better than standard selection rules, it gives the lower-bound literature a usable diagnostic rather than only a warning.

Core Claim

The hardness results locate the problem precisely. What are the Statistical Limits of Offline RL with Linear Function Approximation? proves an $\Omega((d/2)^H)$ sample lower bound under linear realizability and well-conditioned coverage. It also shows that least-squares policy evaluation succeeds only when per-step distribution shift is small, with errors multiplying across steps. Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation shows that "over-coverage," meaning irrelevant data that satisfies concentrability yet hides the signal, forces exponential dependence without Bellman completeness. Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data goes further. It shows the function class itself distorts coverage: merging states with similar features yields an aggregated concentrability coefficient that can be catastrophic even when raw coverage looks fine. It also shows trajectory data does not escape the $\Omega(2^H)$ bound. These three papers motivate the proposal. They show that whether error compounds depends jointly on the representation and the data, not on either alone.

Random Fourier features make that joint dependence tunable. A wide bandwidth merges many states, which is the aggregation failure. A narrow bandwidth with many features resolves states finely but spreads the data thinly, which is the over-coverage and variance failure. Optimal Rates for Random Fourier Features supplies the realizability side. For a value function of bounded kernel norm, the approximation error of an $m$-feature map decays as $O(m^{-1/2})$, with only a logarithmic dependence on domain size in the uniform bound.

For the coverage side we define a per-step amplification factor. Let $z(s,a)\in\mathbb{R}^m$ be the random-feature map at bandwidth $\sigma$, let $\Sigma = \mathbb{E}_{\mathcal{D}}[z(s,a)z(s,a)^\top] + \lambda I$ be the regularized data covariance with ridge strength $\lambda$, and let $\pi$ be the policy being evaluated. The factor is

$$\rho(\sigma,m,\lambda) = \gamma \left\| \Sigma^{-1/2}\, \mathbb{E}_{\mathcal{D}}\!\left[z(s,a)\, z(s',\pi(s'))^\top\right] \Sigma^{-1/2} \right\|_2 ,$$

where $\gamma$ is the discount and $(s,a,s')$ are logged transitions. This is the operator norm of the empirical projected Bellman map in the data's own geometry. When $\rho<1$ the iterated regression contracts. When $\rho>1$, any per-step projection error $\epsilon$ is magnified roughly as $\epsilon\sum_{h<H}\rho^h$. This form follows from unrolling linear fitted evaluation, as in the analysis of What are the Statistical Limits of Offline RL with Linear Function Approximation?. Our predicted evaluation error is therefore

$$\widehat{\mathrm{Err}}(\sigma,m,\lambda) = \big(\epsilon_{\text{approx}}(\sigma,m) + \epsilon_{\text{stat}}(\sigma,m,\lambda)\big)\cdot \sum_{h=0}^{H-1}\rho(\sigma,m,\lambda)^h .$$

Here $\epsilon_{\text{approx}}$ is estimated from held-out Bellman residuals and $\epsilon_{\text{stat}}$ from the effective degrees of freedom of the ridge fit.

The claim is empirical and falsifiable. Across the bandwidth, width, and ridge grid, the minimizer of $\widehat{\mathrm{Err}}$ should select representations whose true evaluation error is near the best available. Held-out Bellman residual alone, which sees only the realizability term, and $\rho$ alone, which sees only the coverage term, should both select worse. We do not claim to circumvent the lower bounds. On the hard instances of What are the Statistical Limits of Offline RL with Linear Function Approximation?, the correct behavior of the diagnostic is to report $\rho>1$ at every setting and refuse to certify the estimate.

Relation to Prior Work

The closest existing work is Self-Supervised Reinforcement Learning that Transfers using Random Features (RaMP). It pretrains an ensemble of 2048 neural Q-functions, each predicting the discounted future sum of one random feature, then fits reward weights by ridge regression and plans with random shooting. RaMP uses random features as reward bases for transfer. It never asks whether the resulting linear value estimates compound error, and it gives no way to choose the feature distribution. We use random features for a different purpose, as a controlled family in which to measure and select the realizability–coverage balance. We evaluate a fixed policy offline rather than transferring across rewards. Information-Based Exploration via Random Features for Reinforcement Learning uses random-feature uncertainty to guide online exploration. That is a coverage-seeking use, and it is unavailable when data are fixed.

Two lines of positive results constrain the design. Batch Value-function Approximation with Only Realizability (BVFT) selects among candidate value functions by pairwise tournaments and needs only realizability plus exploratory data. It is the natural competitor for choosing among our bandwidth settings, and we run it as such. Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^\pi$-Realizability and Concentrability and the linear-programming approach of Revisiting the Linear-Programming Framework for Offline RL with General Function Approximation achieve polynomial rates under stronger or differently structured assumptions, but through computationally intractable optimization. Our diagnostic is a single $m\times m$ eigenvalue computation. It is cheap by design, and its value rests on predictive accuracy, not on a minimax guarantee. From the kernel side, How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets supplies two methods: sampling frequencies from convolved spectral densities to mix bandwidths at constant feature dimension, and block-parallel training at large $m$. Mixed-bandwidth maps enter our search space as candidates that might resolve some regions finely while merging others.

Research Program

The work has three parts.

The first part is analytic. We will bound linear fitted evaluation error on random-feature maps in terms of $\rho$ and the kernel approximation error, using the $O(m^{-1/2})$ rate of Optimal Rates for Random Fourier Features for value functions of bounded kernel norm. We will also bound the error of the empirical $\rho$ as an estimate of its population value, as a function of dataset size and $\lambda$. We will then work out $\rho$ in closed form on two families. One is simple chain MDPs where bandwidth controls state merging, which reproduces the aggregation trap of Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data. The other is the hard construction of What are the Statistical Limits of Offline RL with Linear Function Approximation?. This tells us in advance where the diagnostic should fire.

The second part is the selection procedure itself: fit ridge fitted Q-evaluation on a grid of $(\sigma, m, \lambda)$ and of mixed-bandwidth spectral densities, compute $\widehat{\mathrm{Err}}$, and return the minimizer.

The third part tests whether the selected critic also yields better policies. We use it inside a simple pessimistic actor update, where the actor is penalized for leaving the data distribution. The purpose is to check whether selection quality carries over to control. We do not expect to top the deep-network leaderboard.

Baselines

The naive reference is ridge fitted Q-evaluation with random Fourier features at the median-distance bandwidth heuristic, a fixed large width, and a fixed ridge. This is what a practitioner would try first. Any selection rule must beat it to matter.

The first real competitor is held-out Bellman-residual selection over the same grid. It is cheap, standard, and captures the realizability term, so it is the most likely rule to match ours.

The second is BVFT from Batch Value-function Approximation with Only Realizability. We run it as a tournament over the value functions produced by every grid point, with the same data and the same candidate set. It is the only method in the file with a realizability-only selection guarantee, so it is the strongest principled competitor. We found no reported result on Lacuna for BVFT as an evaluation selector on D4RL.

Two ablations isolate the key ingredient, which is the product of both terms. The first uses $\rho$ alone, choosing the most contractive setting. The second uses $\epsilon_{\text{approx}}$ alone, which amounts to Bellman residual. A third ablation replaces random features with the penultimate layer of a network critic trained offline. We then compute the same $\rho$ on it. This tests whether the diagnostic is specific to kernel features or general.

For the policy-level comparison, the reference ceiling is ReBRAC from Revisiting the Minimalist Approach to Offline Reinforcement Learning. It reports an average normalized score of 81.2 on D4RL Gym-MuJoCo locomotion and 76.8 on AntMaze. We will retrain it with its published tuning protocol on the same datasets and seeds.

Fairness is enforced by giving every selector the same grid, the same evaluation-free data, and the same wall-clock budget. Beating the baselines means lower median absolute evaluation error, and higher rank correlation between predicted and true error, than Bellman residual and BVFT on a majority of datasets, with non-overlapping bootstrap intervals.

Why not just…?

Why not just select bandwidth by held-out Bellman residual? Residual measures how well one step of the Bellman map is fit. It is blind to amplification. What are the Statistical Limits of Offline RL with Linear Function Approximation? is precisely a setting where the one-step fit is perfect and evaluation still fails exponentially. Still, on benign D4RL data, residual may track $\widehat{\mathrm{Err}}$ closely. That is a real threat. The residual-only ablation settles it directly: if it matches us on real data, we will report that the amplification term matters only on constructed or narrow-coverage datasets.

Why not just use BVFT? BVFT has guarantees but assumes fully exploratory data. Its tournament also scales quadratically in candidates and its sample dependence is $\epsilon^{-4}$ (Batch Value-function Approximation with Only Realizability). We expect it to degrade on narrow datasets such as medium-expert mixtures. We run it head-to-head rather than argue this.

Why not just increase the ridge penalty until evaluation is stable? Larger $\lambda$ shrinks $\rho$ but biases the estimate toward zero. Stability and accuracy are different targets. Because $\lambda$ is part of our grid, the comparison is internal: if "largest $\lambda$ with $\rho<1$" selects as well as $\widehat{\mathrm{Err}}$, the product form is unnecessary and we will say so.

Why not just use a deep critic such as ReBRAC? For raw benchmark score, this may well be the right answer, and we do not expect to exceed 81.2. Deep critics give no inspectable amplification quantity, however, and Revisiting the Minimalist Approach to Offline Reinforcement Learning reports catastrophic drops when single components such as LayerNorm are removed. The learned-feature ablation tests whether our diagnostic can at least flag when such critics are untrustworthy.

Proposed Experiments and Decisive Checks

Synthetic tests come first. We use chain MDPs with known value functions and tunable state merging, and the hard instance of What are the Statistical Limits of Offline RL with Linear Function Approximation? at horizons 5 to 30. We check two things. On the hard instance, $\rho$ should exceed 1 at every grid point, with true error growing geometrically at a matching rate. On chains, the U-shaped true error against bandwidth should be tracked by $\widehat{\mathrm{Err}}$ and missed by residual-only selection.

The main test is off-policy evaluation on D4RL Gym-MuJoCo (HalfCheetah, Hopper, Walker2d; random, medium, medium-replay, medium-expert), described in D4RL: Datasets for Deep Data-Driven Reinforcement Learning. We evaluate a pool of target policies whose true values we obtain by simulator rollouts. The metrics are absolute evaluation error of each selector's pick, regret relative to the best grid point, and Spearman correlation between predicted and true error across the grid.

AntMaze and Maze2D are the stitching-heavy stress tests. There, fine bandwidths should expose over-coverage.

Finally, we run the policy-level comparison against ReBRAC's reported and retrained scores.

The decisive outcomes are three. Our selector must beat both Bellman residual and BVFT on evaluation regret across most D4RL datasets. Both single-term ablations must lose. And the diagnostic must correctly refuse certification on the synthetic hard instance. If the first holds but the ablations tie, the proposal reduces to "Bellman residual suffices on these benchmarks." That would itself be a useful negative finding, and we would report it.