Bandits Under an Equal Tuning Budget

Have you ever read a benchmark table and wondered how much of that ranking belongs to the algorithms, and how much belongs to whoever configured them? I know that question doesn't have a general answer - to answer it properly you would need every algorithm at every configuration, which is the thing the table was supposed to spare you from doing. But there is a narrower version that is answerable: inside one benchmark, on one environment family, with a tuning budget declared in advance and handed out equally, does the ranking hold? That one I could actually run, so I ran it, and the ranking did not hold.

The setting is request routing. Ten backends, each with its own latency distribution, and a router that has to pick one per request while learning which ones are fast - a multi-armed bandit, where the arm is a server and the reward is the reciprocal of the latency it returns. What makes it more than a textbook bandit is that the servers do not stay put: load shifts, the fastest backend stops being the fastest, and the optimal arm becomes a moving target. That is the case the non-stationary bandit literature exists for, and it is also the case where I expected the specialised algorithms to earn their keep.

The full benchmark, code, raw results and figures are at bandit-load-balancing-benchmark. This piece is the argument; the repository is the evidence.

What "regret" means, since every table below is measured in it

Every number in this article is a regret figure, so it's worth being precise about what it counts.

Regret is the price of not having been perfect. Imagine an oracle that knows, at every moment, which server is genuinely fastest, and always routes there. Your policy doesn't know that, so sometimes it routes elsewhere. Each time it does, it loses a little compared to the oracle - and regret is that loss, added up over the whole run.

Concretely: if the best server would have returned a reward of 0.10 on this request and the one you picked returned 0.06, you just accumulated 0.04 of regret. Do that ten thousand times and the total tells you how much the policy's ignorance cost.

Three consequences worth holding on to while reading the tables:

• Lower is better, and zero is the floor. A regret of 7.40 is not "7.4 of something bad", it's "over 10,000 requests, this policy fell 7.4 reward-units short of an oracle." Nothing can do better than 0.
• It is cumulative, so it only ever grows. A flat regret curve means the policy has found the best arm and is staying there. A straight rising line means it is still losing on every request - which is exactly what Round Robin does, forever, by design.
• "Dynamic" regret compares against a moving oracle. The usual definition compares against the single best fixed server in hindsight. That's meaningless here, because the best server changes partway through the run - so the comparison has to be against whichever server is best at that moment, $a^*(t)$, re-evaluated every round.

A reward, in this benchmark, is the reciprocal of latency: fast responses score high, slow ones score low. So regret is ultimately a statement about milliseconds - just accumulated in a form that stays comparable across scenarios where the absolute latencies differ.

The protocol, fixed before the runs

Servers (arms)      K = 10
Horizon             T = 10,000 rounds
Latency model       Gamma(k=5, θ), mean 10-100 ms, CV = 0.447
Reward              r = 1/L, online-normalised to [0,1]
Primary metric      dynamic regret, against the time-varying optimal arm

Scenarios           stationary · gradual drift · abrupt drift (breakpoint t = 5000)
Density sweep       dense_abrupt, stable-phase length P ∈ {250, 500, 1000, 2500, 5000}
Policies            ε-greedy · UCB1 · Thompson Sampling · SW-UCB · D-UCB
Baselines           Round Robin · Least Connections

Three commitments were made before any result was looked at, and they turn out to matter more than the algorithm list does.

Equal tuning budget. Every tunable policy got a grid of the same size - eight points each - searched on tuning instances that are disjoint from the evaluation instances. This sounds like housekeeping. It is the whole finding.

Dynamic regret, not static regret. As above: the oracle has to move when the environment does, or the metric stops measuring anything at $t = 5000$.

$N = 5$, not $N = 150$. This one is worth slowing down on, because it changes every p-value in the article.

There are 150 trajectories. They are not 150 independent experiments. They are 5 environment instances × 30 random seeds - meaning five different randomly-generated "clusters" (each with its own set of server speeds), each run thirty times with different noise.

Those thirty runs are not independent of each other. They share the same underlying cluster: the same gap between the fastest and second-fastest server, the same overall difficulty. If instance #3 happens to be an easy one, all thirty of its runs will look good, and averaging them just measures instance #3 thirty times with more confidence. What varies independently is the instance, not the run.

So the honest sample size is 5, and every statistical test here is paired across those five. Small $n$ has a visible consequence in the tables: the Wilcoxon signed-rank test cannot report anything below $p = 0.0625$ when $n = 5$, no matter how cleanly separated the two policies are - that is simply the smallest value the test can produce with five pairs. So the paired $t$-test is the one doing the discriminating, and Wilcoxon is reported alongside it only to confirm the direction agrees.

Finding 1: the ranking is partly just the budget

The textbook expectation is that directed exploration beats random exploration - UCB and Thompson Sampling should beat ε-greedy. Run at default settings, that is exactly what this benchmark reproduces. Run under an equal budget, it inverts.

Final cumulative dynamic regret, $T = 10{,}000$, mean ± std over 150 trajectories.

Tuned ε-greedy scores 7.40 on the stationary scenario against UCB's 93.24 - an order of magnitude the other way from the expected result. And the reason is not subtle once you write out what the default constant actually does. With c = 0.1, d = 1, K = 10, the schedule is $\epsilon_t = \min(1, cK/d^2t) = \min(1, 1/t)$, so the total exploration over the entire horizon is

$\sum_{t=1}^{10000} \epsilon_t \approx 1 + \ln(10000) \approx 9.8 \text{ rounds}$

Nine point eight random explorations, across ten arms, over ten thousand requests - roughly one look at each server for the entire run. The measured non-greedy rate confirms it at 0.36%. Auer et al. (2002), the result usually cited to justify this schedule at all, requires $c > 5$; c = 0.1 is fifty times below that, so the bound being invoked does not even apply. The "premature convergence to a suboptimal arm" that the default configuration displays is not an empirical discovery about ε-greedy - it is the arithmetic consequence of a constant, and any benchmark that reports it as a property of the mechanism is mislabelling its own result.

Someone will reasonably object here that tuning on eight grid points is itself arbitrary, and that a different budget would produce a different ranking again - which is exactly the point I am making, not an objection to it. The claim is not "ε-greedy is better than UCB." The claim is that "A beats B" is not a well-formed statement about bandit algorithms until the tuning budget is part of the sentence, and that most empirical comparisons, including the first draft of this one, do not put it there.

Finding 2: the forgetting mechanisms tuned themselves out of existence

SW-UCB and D-UCB are the two policies in the lineup specifically designed for non-stationary environments. SW-UCB estimates each arm's mean from a sliding window of the last $\tau$ observations, so old data ages out; D-UCB does the same continuously by discounting past observations by $\gamma$ per round. Both are built on the premise that after a breakpoint, stale evidence is worse than no evidence.

The grid search disagreed, and the shape of the disagreement is what makes it interesting. On the first pass both optima landed on the last point of the grid, with the trend still monotone through it - which is not a result, it is a broken grid. Turning a dial to its stop while the signal is still improving and reporting the stop as the optimum tells you about the dial, not the signal. So the grid was extended, and the optimum kept moving outward until it hit the only place it could stop:

$\tau = T$ means the window covers the whole history and nothing is ever forgotten. $\gamma = 1$ means the discount does nothing. Both limits are plain UCB. The equal-budget tuning procedure, given a free choice, configured both non-stationary algorithms into the stationary algorithm.

Read left to right, both grids are a dial running from "forget aggressively" to "don't forget at all" - and on both dials, regret fell the whole way toward the right-hand end. The end of the dial is not a tuning choice; it is the algorithm turning into a different algorithm.

That is not a claim resting on the numbers being close. It rests on them being identical: tuned SW-UCB's final regret is 93.24 ± 34.49 on the stationary scenario, and UCB's is 93.24 ± 34.49. In the density sweep, the per-instance difference between tuned SW-UCB and UCB is exactly +0.00 on 5 of 5 instances at every single drift density tested. They are not similar policies - after tuning, they are the same policy, running the same code path.

The mechanism behind this is measurable rather than rhetorical, and it's easier to see on a timeline than in a sentence. Forgetting has a cost and a payoff, and they arrive on completely different schedules:

So forgetting only pays for itself when breakpoints arrive often enough to outweigh a cost charged on every single round in between. That is a race between two rates, and it is winnable in principle - which is why the sweep below exists. In this environment family the normalised-reward gap between the two best arms is 0.0823, and solving the sliding-window confidence condition $\sqrt{2\ln\tau \cdot K/\tau} \lesssim \text{gap}$ at that value gives $\tau \approx 30{,}481$ - three times the entire horizon. There is no window size that both forgets usefully and still resolves the two best arms; the environment does not leave room for one to exist.

So the obvious next question is whether denser drift changes it. The stable-phase length $P$ was swept from 5000 down to 250 - from a single breakpoint to thirty-nine of them - with the protocol fixed in advance and a commitment to report the outcome either way.

No crossover anywhere in the range. D-UCB is worse than UCB on 5 of 5 instances at every density tested, paired $t$-test $p \le 0.032$ throughout; the default-configured forgetting policies are worse by a factor of two and stay there. If forgetting ever paid for itself in this environment, these columns would cross somewhere, and they do not.

Finding 3: the crossover that is in the sweep, that nobody was looking for

The sweep was built to find a crossover for the forgetting policies. It contains one anyway - between the two policies that were never the subject of the experiment.

Running the same paired-across-instances test on Thompson Sampling against UCB at each drift density:

The sign flips, and it flips at a locatable place: between $P = 2500$ and $P = 5000$, with $P = 2500$ sitting almost exactly on the boundary - a mean difference of 2.7 on regrets around 110, mixed signs across instances, $p = 0.885$. That is what a genuine crossing looks like when you catch it near the middle rather than at the ends.

The explanation is the same property in both directions. Thompson Sampling's posterior standard deviation shrinks as $\sigma_0/\sqrt{n+1}$, so the more evidence it gathers the harder it commits - which is exactly what you want when the world holds still, and exactly what hurts you when the world moves and all that accumulated confidence is now confidence in the wrong arm. UCB's exploration bonus grows with $\sqrt{\ln t / n}$ and never fully switches off, so it is permanently paying a little to keep looking, and that standing subscription is what lets it re-identify a new optimum quickly. Sparse drift rewards commitment; dense drift rewards never quite committing.

This matters beyond being a tidy story, because it is the resurrection of a hypothesis clause that had been quietly dropped. The pre-registered H1 had two halves - (a) UCB ≈ Thompson Sampling, and (b) both beat ε-greedy - and an earlier draft of the results tested (b), reported it, and simply stopped mentioning (a), even though the data contradicted (a) plainly. Recovering it turned a dropped half-hypothesis into the sharpest finding in the sweep. The uncomfortable version of that sentence is that the most interesting result in this study was one I had already thrown away once.

Finding 4: bandits beat the classical policies, conditional on tuning

The comparison against what actually runs in production load balancers is the least surprising part, but it is the part with the physical units attached.

Mean request latency; parenthesis = speedup over Least Connections.

Every tuned bandit policy beat Least Connections on 5 of 5 instances across all three scenarios - fifteen comparisons, every one of them consistent in sign, worst paired $t$-test $p = 0.0379$. On dynamic regret the improvement ranges from 2.2× to 48×, median 5.2×.

The caveat that belongs next to that table: Least Connections needs no configuration whatsoever, and the bandits need a reward scale. In this benchmark that scale is estimated online, from each policy's own observed history - the earlier version used hard-coded percentile constants taken from the evaluation environment's own latency distribution, which is oracle information nobody has before deployment, and it was removed. But the residual asymmetry is real and is not removed: the bandits carry a mechanism the baselines do not need, and its cost is not charged anywhere in the table above.

What was pre-registered, and what happened

Three of four rejected, one of them in the direction opposite to what I predicted. A benchmark that only ever confirms its author's expectations is not measuring anything, so this is the outcome I would rather report than the tidy one - but I want to be precise about why it is reportable, and it is not because being wrong is virtuous. It is because the protocol was fixed before the runs, which is the only thing that makes "I predicted the opposite" a fact about the environment rather than a fact about my memory.

Re-checking the numbers to write this up

Every table above was regenerated from the committed results while writing this piece rather than copied from the repository's own summary, and three of that summary's sentences did not survive the check. All three are the same failure - an aggregate that entered prose without a script behind it - which is the failure the repository has an entire catalogue entry about.

The summary reported a median improvement of 8.1× over Least Connections. Recomputed, the median is 5.2×; 8.10× is the value of one cell in the table (D-UCB, gradual drift), lifted and relabelled as an aggregate. No definition of the median I could construct - per-instance ratios, ratio of means, including or excluding default configs, against Round Robin instead - lands anywhere near 8.1.

It reported that TS beats UCB consistently, $p = 0.007$. That holds on stationary (5/5, $p = 0.0067$) and abrupt drift (5/5, $p = 0.0066$), and fails on gradual drift, where it is 4/5 and $p = 0.206$. One scenario's $p$-value had been promoted to a general claim.

It reported that at default settings D-UCB is statistically indistinguishable from Least Connections. Paired across instances it is distinguishable in all three scenarios ($p = 0.0087$, $0.0088$, $0.0367$) - the differences are small in magnitude but consistent in sign, which is precisely the situation a paired test is built to detect. The correct word is practically indistinguishable, and the difference between those two words is the difference between a claim about effect size and a claim about evidence.

None of this touches the findings - the underlying results are the same, and the corrected numbers argue the same direction. What it does show is that an audit is not a thing you finish. The catalogue of pitfalls that came out of this project has "never hand-type an aggregate" as one of its entries, and the summary written after that catalogue existed still hand-typed three.

Limitations, stated rather than implied

The scope conditions are narrow and worth naming precisely, because the second finding in particular is exactly the kind of result that gets over-generalised into "forgetting mechanisms don't work."

This environment is exogenous. Latency is drawn from a distribution that depends on which server was chosen and on the timestep, and on nothing else - routing a request to a backend does not make that backend slower. A real load balancer is endogenous: the router's decisions change the load it is subsequently measuring, which creates a feedback loop with no counterpart here. Every result above is about learning a moving target, not about learning a target that moves because you looked at it.

Large gaps, homogeneous noise, $K = 10$. The normalised gap of 0.0823 is what makes forgetting unaffordable; environments with tighter gaps or heavier-tailed noise raise UCB's re-identification cost and are the natural place to look for the crossover this sweep did not find.

$n = 5$. Five independent instances is enough to detect the consistent-sign effects reported here and not enough for anything subtler. Where a result is near the boundary - the $P = 2500$ row - it is reported as near the boundary rather than resolved.

Simulation, not a cluster. Nothing here has been run against real servers.

What I actually took from it

The result I expected to be able to reuse was a ranking - some ordering of policies I could carry to the next routing problem. That is not what survived. What survived is a reading habit: when a comparative table has no tuning budget attached to it, I now treat the ranking as partly a statement about the authors' attention, and I look first at whether the loser's constants came from anywhere other than a previous paper's default.

And the write-up itself is where two of the findings above actually came from - the TS/UCB crossover exists in data that had been sitting in the repository for weeks, and it only got tested because writing the section forced a question about what else the sweep contained. Which is the argument for writing these up at all: the analysis is not finished when the runs finish, and a result that nobody has been made to explain in full sentences has not really been checked yet.