When Is Allocation Stability Necessary for Gaussian Inference in Variance-Aware UCB?

Stability is sufficient, not always necessary

The paper asks whether allocation stability — the ability to approximate an arm's final pull count by a deterministic sequence with vanishing relative error — is required for Gaussian inference from bandit data. The answer splits in two. For a fixed target, such as one arm's mean or the difference of the two means, the usual Wald statistic keeps a standard normal limit even when the optimal arm's count is unstable. For a target whose coefficient vector is allowed to vary with the horizon, the same Gaussian approximation holds uniformly if and only if the optimal-arm count is stable.

The condition attached to both results is that each arm's effective sample size diverges: the product of its final pull count and its reward variance must go to infinity in probability. The setting is narrow by design — two arms, rewards bounded in [0,1], a known horizon, and reward laws that may themselves change with the horizon. Within that setting the authors locate exactly where stability stops being a prerequisite and where it becomes one.

Variance-aware bonuses disperse the optimal-arm count

Canonical UCB adds an exploration bonus built from a common bound on the reward range. A variance-aware rule instead uses each arm's estimated standard deviation, taking the larger of a standard-deviation term and an inverse-count term, with a fixed exploration factor ρ log T applied at every round. The paper's motivating figure compares the two rules on a two-arm instance with T = 10^6 rounds and ρ = 2: the number of pulls from the optimal arm is concentrated under canonical UCB but far more dispersed under the variance-aware rule.

That dispersion matters because the standard justification for Wald inference assumes each arm's count can be replaced by a deterministic number, after which a martingale central limit theorem applies to the normalized reward sums. If the count is genuinely random, that substitution is no longer available. The paper therefore treats the variance-aware rule as a test case in which the failure of stability can actually be observed, rather than assumed away.

A three-part criterion separates stable from unstable counts

The suboptimal arm's count is always stable under this policy. The optimal arm's count is not, and the paper gives an if-and-only-if criterion: instability occurs exactly when three conditions hold simultaneously along some subsequence of horizons. First, the reward gap Δ must sit near σ2 times the square root of c_T / T, up to a term of order σ2 times the square root of T. Second, the ratio of the two standard deviations must be small, of order c_T to the power −3/4. Third, c_T cubed divided by T times σ2 squared must be bounded.

These conditions describe a critical window in which fluctuations in the suboptimal arm's sample mean can shift the optimal-arm allocation at first order. Inside that window the paper shows that every subsequence of horizons has a further subsequence along which the rescaled optimal-arm count, divided by T over the square root of c_T, converges to a nonconstant random variable. So the count is not merely hard to approximate deterministically; its limit law is genuinely random.

Fixed targets keep standard normal limits

The central inferential result is that for every fixed nonzero coefficient vector u, the Wald statistic for the linear combination of arm means converges to a standard normal, even when the optimal-arm count is unstable. Consequently the usual Wald intervals for either arm mean and for their difference have asymptotically correct coverage under the diverging effective-sample-size condition.

The proof does not pretend the count is deterministic. It compares the policy pathwise with an auxiliary policy that replaces the optimal arm's empirical index by its population counterpart. That auxiliary policy's final optimal-arm count is independent of the entire reward sequence of the optimal arm and approximates the original count with vanishing relative error. The count may remain random, but because it is measurable once the suboptimal arm's rewards are revealed, it can serve as a random normalizer inside a martingale central limit theorem. This is the mechanism that lets a random allocation still deliver a Gaussian limit.

Uniformity is where stability becomes necessary

The fixed-target result is pointwise: the coefficient vector is held fixed as T grows. The stronger requirement is that the Gaussian approximation hold uniformly over all deterministic nonzero coefficient vectors, equivalently that the supremum over u and over thresholds z of the gap between the Wald statistic's distribution and the standard normal vanish. Under the same effective-sample-size condition, the paper proves this uniform approximation holds if and only if the optimal-arm count is stable.

When stability fails, the paper goes further and identifies which coefficient scales still produce standard limits and which produce nonstandard ones. The nonstandard limits arise for linear combinations whose coefficients vary with the horizon, because the rescaled optimal-arm count and the two studentized sample-mean errors then have a joint limit rather than separate ones. This is the precise sense in which stability is necessary: not for inference about a target you name in advance, but for a guarantee that covers every target at once.

Lower regret comes with a longer mean-difference interval

The paper also compares variance-aware and canonical UCB on regret and on Wald interval lengths. In the regime where the gap shrinks with the horizon, the pseudo-regret ratio of variance-aware to canonical UCB converges to 1/λ, which is at least 2, while the ratio of mean-difference interval lengths converges to the square root of λ, which is below 1. The two ratios multiply to 1 in the limit, so the policy with lower regret pays for it with a longer interval for the mean difference.

The reason is that the suboptimal arm's count controls the squared mean-difference interval length to first order under both policies. More pulls of arm 2 raise regret but shorten that interval. The interval for the optimal arm's mean behaves in the opposite direction: under variance-aware UCB the optimal arm receives a vanishing fraction of the budget, so its interval is longer than under canonical UCB by a diverging factor. The paper also notes that the mean-difference interval under variance-aware UCB matches the first-order length of Neyman allocation based on the true variances, even though the optimal-arm counts may differ on their own scale.

Simulations show the predicted coverage gap

The numerical illustration uses the paper's example reward laws with ρ = 2 and T = 10^8, running 6,000 independent pairs of experiments in which both policies see the same reward sequence for each arm. For the fixed targets (1,0) and (1,−1), the Wald statistic looks standard normal under both policies. For the changing target u_T = (1, (2√c_T)^{-1}), the variance-aware rule produces the nonstandard limit the theory predicts, while canonical UCB stays standard normal.

The coverage table reflects this. At the nominal 95% level, the changing target is covered 92.87% of the time under variance-aware UCB and 94.48% under canonical UCB; at the nominal 90% level the corresponding figures are 85.97% and 89.12%. Fixed targets sit close to nominal under both policies. The authors note that coverage errors appear even for fixed targets with standard normal limits, and they leave open a quantitative account of how those errors depend on the horizon, the gap, and the two variances. They also flag an incomplete case for horizon-varying coefficients when the limiting rescaled count has an atom at zero, and they restrict attention to a fixed exploration factor and two arms.

Sort your target before demanding stability

The paper's most useful distinction is between two questions that are easy to conflate. If you plan to report a Wald interval for one arm's mean or for the difference of the two means, the fixed-target result says you do not need the optimal-arm count to be stable; you need each arm's pull count times its variance to diverge. If instead you need a guarantee that holds across a family of targets whose coefficients change with the horizon, stability of the optimal-arm count is exactly the dividing line, and the paper's three-part criterion on the gap and variances tells you when that line is crossed.

The second distinction is between regret and estimation. Under this policy, the same suboptimal-arm count that lowers regret lengthens the mean-difference interval, so a comparison that reports only regret is incomplete. The paper's own comparison puts the trade-off in concrete terms: the regret ratio is at least 2 while the mean-difference interval ratio is below 1, and their product tends to 1.

Sources used in this answer