Automated hyperparameter tuning scores each candidate setting on a validation set and then keeps searching. When that validation score is noisy, for example because of a small holdout split or seed-to-seed training variance, the search can "win" by chasing lucky draws. In roughly one run in ten, the configuration it returns tests worse than the default it started from. Reinforcement learning has a precise account of a related problem: when the environment randomly throws away the agent's progress, planning far ahead is worth exactly as much as planning with a smaller discount factor. In other words, noise makes the future count for less. We propose to carry that account over to Bayesian hyperparameter search. A single measurable quantity, how often a validation ranking between two configurations survives a fresh resample, would set both how many steps ahead the search should plan and when it should stop.
The work also tests a benchmarking claim. The standardized hyperparameter-optimization benchmarks that most papers report on replace real training with deterministic lookup tables or neural surrogates. That design removes the very noise that makes deep planning and long searches harmful. We expect such benchmarks to rank optimizers in favor of methods that plan further or search longer, and we expect those rankings to change once realistic, calibrated validation noise is restored.
Core Claim
Bayesian optimization (BO) fits a probabilistic model, called a surrogate, to past evaluations and picks the next configuration by maximizing an acquisition function, a score for how useful an evaluation would be. Most acquisition functions are myopic: they value only the next step. Non-myopic variants simulate several future steps. Why Non-myopic Bayesian Optimization is Promising and How Far Should We Look-ahead? uses rollouts for this and adjusts the lookahead depth $h$ by bounding how surrogate error propagates. On noiseless synthetic functions it finds that the best $h$ is usually 2 or 3. Understanding Short-Horizon Bias in Stochastic Meta-Optimization shows the opposite failure in gradient-based tuning: horizons that are too short choose learning rates orders of magnitude too small. Together these papers imply a U-shaped curve, where test performance is poor at very short and very long horizons. Neither paper says how validation noise moves the bottom of that U.
Our claim is that validation noise moves the optimum toward shorter horizons in a predictable way. The prediction comes from treating noisy improvement as reset noise. Transition Noise Facilitates Interpretability and Noise as a Natural Regularizer in Markov Decision Processes prove that an agent which, with probability $1-\alpha$, is sent back to a base distribution is solving the noiseless problem with discount $\gamma' = \alpha\gamma$. In hyperparameter search, an apparent improvement that does not hold up on resampling plays the role of a reset: the search moved, but the true value it gained is zero.
We define the rank reliability $\alpha(\delta) = 2P(\text{order agrees on an independent resample} \mid \text{validation gap } \delta) - 1$. It equals 1 when every validation ordering at gap $\delta$ replicates and 0 when orderings are coin flips. The proposed effective planning horizon is
$$H_t = \frac{1}{1-\alpha(\delta_t)\,\gamma},$$
where $\delta_t$ is the typical size of recent incumbent improvements and $\gamma$ is the nominal per-step discount on lookahead value.
As search goes on, improvements shrink, so $\alpha(\delta_t)$ falls and $H_t$ shrinks toward 1. At that point the search is effectively myopic. Once the reliability-discounted one-step value no longer covers the cost of an evaluation, the search should stop. One estimated curve therefore governs lookahead depth and stopping together. We present this as a mapping to be tested, not as a theorem. The MDP proofs cover transition noise, while validation noise is observation noise. Noise as a Natural Regularizer also shows that the equivalence fails when there are irreversible hazards. Settling whether the reset model fits hyperparameter search is the first aim of the project.
Research Program
The first part is measurement. We will build noise-calibrated versions of standard benchmark tasks. Wherever a benchmark stores replicate seeds or folds, we use them directly. Elsewhere we generate replicates with the raw-evaluation mode of HPOBench on tabular tasks, subsampled to $n=500$ and $n=5000$ to mirror the sample-size effect reported in Overtuning in Hyperparameter Optimization. From the replicates we estimate empirical $\alpha(\delta)$ curves per task.
We then attach a noise model fitted to those curves to the deterministic surrogates of YAHPO Gym. This produces a benchmark with a controllable noise dial while keeping YAHPO's continuous search spaces, which matter because of the tabular trap: discretized grids distort how BO maximizes its acquisition function. Every query returns a noisy "validation" score and a separately drawn "test" score, so overtuning can be measured directly.
The second part is analysis. Across the noise dial, we sweep fixed lookahead depths $h \in \{1,2,3,5\}$ of a rollout acquisition and record the depth that minimizes test regret, $h^*$. We then check whether $h^*$ follows the trend $1/(1-\alpha\gamma)$ predicted by the reset analogy. We separately record, for each optimizer, the trial count at which test regret is lowest. The same sweep shows whether optimizer rankings measured on the noiseless surrogate survive the move to calibrated noise.
The third part is the method. The adaptive rule estimates $\alpha(\delta)$ online from a small number of replicate re-evaluations of the incumbent and its nearest rivals. It sets the rollout depth from $H_t$ and stops when the discounted one-step value falls below cost. Replicate evaluations are charged against the same budget as ordinary trials.
Baselines
The naive reference point is random search, together with the default configuration. The default matters because severe overtuning is defined relative to it.
The strongest practical competitors are SMAC and HEBO with ordinary myopic acquisitions. Overtuning in Hyperparameter Optimization finds that these overtune less than random search, because their surrogates smooth validation noise. Across its reanalysis of benchmark suites including LCBench, FCNet, PD1, TabRepo, TabZilla and WDTB, it reports about 60% of runs with no overtuning, about 30% mild and about 10% severe. That 10% severe rate is the number to reduce. No reported test-regret figure for SMAC or HEBO on these specific suites was found on Lacuna, so we will measure it ourselves.
The strongest method-level competitor is the adaptive rolling-horizon rollout of Why Non-myopic Bayesian Optimization is Promising. Its reported results are over 85% gap improvement relative to initial data and an optimal horizon of 2 or 3 steps, both on synthetic noiseless functions. It is the closest competitor because it already adapts $h$, although its rule is driven by surrogate misspecification rather than resampling reliability.
For stopping, we compare against Pandora's Box Gittins Index and log expected improvement per cost, from Cost-aware Stopping for Bayesian Optimization. That paper reports degradation on small LCBench datasets, but no numeric cost-adjusted regret was found on Lacuna. We also include the epoch-level early stopping of Bayesian Optimization Meets Bayesian Optimal Stopping.
Fairness rules apply to all methods:
- Every method returns its incumbent by surrogate posterior mean rather than by best observed score. This removes the cheapest fix for overtuning from the comparison.
- Every method receives the same total evaluation budget, counted including any replicates or cross-validation folds, the same initial design, and 30 seeds per task.
Two ablations isolate the key ingredient:
- Same horizon schedule, wrong signal: apply our horizon schedule but drive it with the GP's fitted noise variance instead of the replicate-estimated $\alpha$.
- Myopic plus α-stopping: fix $h=1$ and keep only α-based stopping.
The method beats the competitors if it lowers mean test regret and the severe-overtuning rate relative to the best competitor at matched budget, with a paired significance test across tasks, and does not lose at the low-noise end of the dial.
Why not just…?
Why not just use myopic BO, whose GP noise term already smooths validation noise? The Overtuning study is real evidence for this alternative. If posterior-mean incumbents plus myopic SMAC or HEBO already bring severe overtuning near zero, the horizon story matters little. The fixed-$h$ sweep settles this directly. If $h^*=1$ at every noise level and α-stopping adds nothing, we will report that the horizon mechanism is irrelevant for hyperparameter search.
Why not just use the existing rolling-horizon rule? It may already shrink $h$ under noise, because noise inflates surrogate uncertainty. The first ablation tests exactly this. Our hypothesis is that resampling reliability, which compares validation against a fresh draw, captures validation-test disagreement that the surrogate's own noise estimate cannot see. If the ablation matches our rule, the contribution reduces to the benchmarking finding.
Why not just use 5-fold cross-validation? It reduces noise but costs five times as much per evaluation. Overtuning in Hyperparameter Optimization reports that high-capacity models at $n=500$ still overtune under it. We run SMAC with cross-validation at equal total budget. If it wins, then spending budget on lower noise beats spending it on planning, and that finding is equally reportable.
Why not just use an existing cost-aware stopping rule? Those rules value continuing to search by expected validation improvement, and their authors attribute the failures on small datasets to validation-test rank inversion. Our stopping criterion discounts that value by $\alpha$, so the comparison on small LCBench tasks is the direct test.
Decisive Checks
The benchmarking claim fails if the Kendall rank correlation between optimizer rankings on the noiseless YAHPO surrogate and on the raw-replicate ground truth stays as high as YAHPO's own surrogate fidelity. YAHPO reports Spearman rank correlations of 0.90 and 0.99. We would treat a drop well below that range, concentrated on non-myopic and long-budget methods, as confirmation.
The mechanism claim fails if the measured $h^*$ does not decrease monotonically with noise, or if $1/(1-\alpha\gamma)$ fitted on half the tasks does not predict $h^*$ on the held-out half better than a constant does.
The method claim fails if the α-driven schedule does not beat both the GP-noise ablation and SMAC with cross-validation on the severe-overtuning rate at matched budget.
We also run a separate hazard check, modeled on the Tightrope failure case of Noise as a Natural Regularizer. On tasks with divergence-prone regions, such as high learning rates, discounting alone should be insufficient. If it is, that is a predicted boundary of the claim, not a contradiction of it.
References
- Why Non-myopic Bayesian Optimization is Promising and How Far Should We Look-ahead? A Study via Rollout
- Understanding Short-Horizon Bias in Stochastic Meta-Optimization
- Transition Noise Facilitates Interpretability
- Noise as a Natural Regularizer in Markov Decision Processes: Connecting Environmental Stochasticity and Policy Simplicity
- HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO
- Overtuning in Hyperparameter Optimization
- YAHPO Gym - An Efficient Multi-Objective Multi-Fidelity Benchmark for Hyperparameter Optimization
- Cost-aware Stopping for Bayesian Optimization
- Bayesian Optimization Meets Bayesian Optimal Stopping