Online algorithms such as cache eviction rules or hospital-bed allocation rules must act without seeing the future. Increasingly they are tuned or trained on recorded traces, then judged by their competitive ratio: on each input sequence, their cost divided by the cost of a clairvoyant optimum that knew the whole sequence in advance. A practical question sits between theory and deployment and has no answer yet. How many recorded episodes are needed before a learned policy's competitive ratio is within $\epsilon$ of the best achievable, and how does that number change as episodes get longer? Reinforcement learning theory has argued for a decade about how sample requirements scale with episode length (the horizon $H$). The answer has swung between $H^2$, polylogarithmic in $H$, and "it depends on how you normalize rewards." Competitive analysis has never asked the question, because it treats the learned predictor as a black box.
Our central claim is that the competitive ratio carries its own normalization. Dividing by the clairvoyant optimum's cost rescales each instance by an amount that grows with the horizon whenever the optimum's cost does. As a result, the horizon should not be what controls sample complexity. What controls it is the density of unavoidable cost, meaning how much cost even the clairvoyant optimum pays per step. When that density is bounded below, we predict that longer episodes need fewer episodes to learn a near-optimal competitive policy. When it vanishes, as with sparse costs, the hard long-horizon regime that reinforcement learning theorists worried about returns. We propose to state this as a variance-aware bound and then test it where these theories have never been tested: on real memory traces, Mixture-of-Experts inference traces, and COVID-19 hospitalization data.
Core Claim
Fix a distribution $D$ over input sequences $\sigma$ of length $H$ and a policy class $\Pi$. Write $R_\pi(\sigma) = \mathrm{cost}(\pi,\sigma)/\mathrm{OPT}(\sigma)$ for the per-instance ratio, where $\mathrm{OPT}$ is the clairvoyant offline optimum. Write $\rho(\sigma) = \mathrm{OPT}(\sigma)/H$ for the optimum's cost density, and assume per-step costs lie in $[0,1]$. The learner sees $N$ sampled sequences and must output a policy whose expected ratio is within $\epsilon$ of the best in $\Pi$.
We conjecture that, under a mixing condition on the request process, the number of episodes required behaves as
$$N(\epsilon, H) \;\approx\; \log\frac{|\Pi|}{\delta}\left(\frac{c}{\rho^2 H \epsilon^2} + \frac{r_{\max}}{\epsilon}\right).$$
Here $\delta$ is the failure probability, $r_{\max}$ is the worst-case ratio (for example $k$ for paging with a cache of $k$ pages), and $c$ is a constant tied to how fast correlations decay along the sequence. The form comes from a Bernstein-type bound, which pays for variance rather than range. A ratio of two sums of $H$ weakly dependent terms, whose denominator grows like $\rho H$, has variance on the order of $1/(\rho^2 H)$ by the delta method.
Three regimes follow, and each is falsifiable. If $\rho$ is fixed, the episode count should fall like $1/H$ until the range term takes over, so the total number of observed steps stays roughly flat. If $\rho \to 0$ as $H$ grows, the variance term grows and horizon dependence comes back. If neither happens empirically, and a crude range-based bound already predicts the curves, then the refinement is unnecessary. We will report that outcome too.
Relation to Prior Work
Three horizon-complexity results motivate the claim, and one constrains it. Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning uses a variance Bellman equation to prove that $H^2$ dependence is tight when per-step rewards lie in $[0,1]$. Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (EULER) shows the leading regret term becomes horizon-free when total reward is bounded. Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? achieves $\log H$ sample complexity under normalized rewards, but with an exponential-time algorithm.
Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon is the constraint. It argues that normalizing total reward by fiat hides real long-horizon difficulty. All four papers bound value suboptimality under a normalization chosen by the analyst, and none of them runs experiments. We instead study a normalization chosen by the problem itself, namely the optimum's cost on each instance. This turns the normalization debate into a measurable quantity, $\rho$.
On the competitive side, Online Resource Allocation with Samples is the closest existing work. It proves a competitive ratio of $1-\Theta(1/(p\sqrt{m}))$ when a fraction $p$ of arrivals is sampled before allocation. That is a within-instance sampling model with no sequential state and no notion of learning across episodes; we study cross-episode learning and its dependence on episode length.
Two other papers supply the policies we will train. Towards Optimal Robustness in Learning-Augmented Paging combines a predictor with a robust fallback (RPB-OM). It keeps $H_k + O(1)$ robustness while matching the optimum under perfect predictions, but it never asks how much data the predictor needs. A new paging problem for Mixture-of-Experts LLMs - extended version introduces layered paging and the layer-aware rule LLRU. Its cyclic structure gives a natural, controllable horizon.
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities motivates a secondary benchmark: the best causal policy rather than the clairvoyant one. We use it only where that benchmark is computable.
Finally, Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning is the methodological model. It shows that TD3-BC collapses between 1M and 5k samples while imitation stays stable, which tells us that we must sweep data sizes down to tiny regimes rather than report one large-data number.
Research Program
The theoretical part proves the bound above for finite and parametric policy classes under a mixing assumption on $D$. It has three pieces. The first is a matching lower bound in the fixed-$\rho$ regime, built from a bandit-style hard instance in the spirit of the UCFH lower-bound construction. The second is a construction showing that $\rho \to 0$ forces horizon dependence, which connects directly to the Jiang–Agarwal conjecture. The third replaces the policy count $|\Pi|$ with a covering number for predictor-driven policies such as RPB-OM with a learned next-arrival regressor.
The algorithmic part is deliberately simple: policy selection by successive elimination using empirical-Bernstein confidence intervals on the ratio. This is cheap, unlike OTS, so the theory can actually be run. The empirical part measures, for each domain, the episode count $N^*(\epsilon)$ needed to come within $\epsilon$ of the best policy in the class on held-out sequences. We measure it across a grid of horizons $H$ and densities $\rho$.
We control $H$ and $\rho$ separately in three domains. In paging, $H$ is the trace window length. $\rho$ is the clairvoyant (Belady) optimum's miss rate per request, which we vary through cache size relative to working-set size. In layered MoE paging, $H$ is the number of token-cycles through the $\ell$ layers. In resource allocation, $H$ is arrivals per period, and $\rho$ is set by scarcity of supply relative to demand.
Baselines
The do-nothing reference is the classical policy that needs no data. That means LRU and LLRU for paging (the latter from A new paging problem for Mixture-of-Experts LLMs - extended version), ONLINEMIN for randomized paging, and a static protection level for allocation. Any learned policy must beat these on held-out ratio to justify its data. For allocation, Online Resource Allocation with Samples reports that naive methods without sample information fall to a competitive ratio of 0.66 on the CDC data.
The strongest existing method differs by domain. For allocation, it is the sample-calibrated protection-level algorithm of Online Resource Allocation with Samples. That paper reports an average competitive ratio between 0.88 and 0.97 on 83 bi-weekly periods of CDC COVID-19 hospitalization data (a reward ratio, so higher is better). We rerun it on the same periods with the same sampling probability $p$, and beating it means a higher average ratio at equal total observed arrivals. For paging, the strongest existing method is RPB-OM with POPU/PLECO predictors from Towards Optimal Robustness in Learning-Augmented Paging. No reported result was found on Lacuna for its numerical miss counts on SPEC CPU 2006, BrightKite or CitiBike, so we reproduce it ourselves. We give it the same training windows, the same cache sizes up to $k=1000$, and the same hyperparameter search budget as our selector.
Two ablations isolate the key ingredient. The first replaces Bernstein intervals with Hoeffding intervals scaled to the worst-case ratio range. This tests whether variance-awareness is what buys the claimed $1/H$ savings. The second trains and selects on unnormalized total cost instead of the ratio. Under per-step bounded costs, that objective should inherit the $H^2$ behaviour that UCFH predicts. Comparing the two objectives' $N^*$ curves therefore tests the self-normalization claim directly.
A behaviour-cloning baseline that imitates the Belady eviction decisions is included as the imitation competitor. It shares the same predictor architecture and data budget as our selector.
Why not just…?
Why not just deploy LRU, LLRU or ONLINEMIN and skip learning? These policies need zero samples, so if they already sit near the best policy in the class, the sample-complexity question is moot. The evidence says they do not always. LRU thrashes in layered MoE paging (A new paging problem for Mixture-of-Experts LLMs - extended version), and sample-free allocation is capped at $1/(2-\alpha)$ (Online Resource Allocation with Samples). Our curves report each learned policy's ratio at $N=0$ (the classical rule) alongside its learned value. If a domain shows no gap, we say so.
Why not just use a Hoeffding bound on the ratio, which is already horizon-free because the ratio is bounded by $k$? This is the real threat. Uniform convergence over $\Pi$ with range $k$ gives $N = O(k^2 \log|\Pi|/\epsilon^2)$ with no $H$ at all. Our claim is that this bound is horizon-free but loose by a factor that grows with $H$ when $\rho$ is fixed. The Hoeffding ablation settles the question empirically. If Hoeffding-based selection reaches $\epsilon$ with as few episodes as Bernstein-based selection across all $H$, the variance term buys nothing, and the contribution reduces to the $\rho \to 0$ lower-bound analysis.
Why not just imitate the clairvoyant optimum, given that imitation was the robust choice in low-data offline RL? The finding in Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning makes this plausible. However, imitating Belady trains on actions that depend on future requests, which a causal policy cannot reproduce. Imitation also carries no robustness guarantee when the test distribution shifts, as Towards Optimal Robustness in Learning-Augmented Paging shows for unguarded predictors. We include imitation in every sweep, and also wrap it in the RPB robust fallback. If it matches our selector's $N^*$, the bound still applies to it as a member of $\Pi$.
Proposed Experiments
The decisive check is a log-log plot of $N^*(\epsilon)$ against $H$ at fixed $\rho$, for SPEC CPU 2006 traces, BrightKite, CitiBike, MoE expert-access traces, and the CDC hospitalization periods. A slope near $-1$, flattening into a plateau, supports the self-normalization claim. A slope of zero means the range term dominates and Hoeffding suffices. Positive slopes, especially under the unnormalized-cost ablation, would reproduce UCFH-style horizon growth.
The second check holds $H$ fixed and lowers $\rho$, through larger caches or more abundant supply. We expect $N^*$ to grow like $1/\rho^2$. That growth would be the empirical face of the sparse-cost difficulty described in Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon.
The third check asks whether the bound's predicted $N^*$, with $c$ estimated from autocorrelation of per-step costs on training traces, falls within a constant factor of the measured $N^*$ across domains. That is the test this literature has never been put to.
The CDC data, with only 83 periods, serves as the extreme low-data case. There we report whether ratio-aware selection matches or exceeds the published 0.88–0.97 range using fewer periods than the original method's calibration requires. On SPEC CPU 2006, we report wall-clock overhead per request against LRU, because a method whose selection cost exceeds its savings would repeat the empirical gap this project sets out to close.
References
- Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
- Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
- Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
- Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon
- Online Resource Allocation with Samples
- Towards Optimal Robustness in Learning-Augmented Paging
- A new paging problem for Mixture-of-Experts LLMs - extended version
- Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
- Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning