# Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime

arXiv: https://arxiv.org/abs/2610.06213 · HTML: https://mlsanity.com/paper/2610.06213/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Builds on (most cited first, 12 of 12)

- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Online Multi-Armed Bandits with Adaptive Inference](https://mlsanity.com/paper/2102.13202/) (2021)
- [Weak Signal Asymptotics for Sequentially Randomized Experiments](https://mlsanity.com/paper/2101.09855/) (2021)
- [The Typical Behavior of Bandit Algorithms](https://mlsanity.com/paper/2210.05660/) (2022)
- [Inference with the Upper Confidence Bound Algorithm](https://mlsanity.com/paper/2408.04595/) (2024)
- [Stable Thompson Sampling: Valid Inference via Variance Inflation](https://mlsanity.com/paper/2505.23260/) (2025)
- [Risk and optimal policies in bandit experiments](https://mlsanity.com/paper/2112.06363/) (2021)
- [Statistical Inference under Adaptive Sampling with LinUCB](https://mlsanity.com/paper/2512.00222/) (2025)
- [Thompson sampling: Precise arm-pull dynamics and adaptive inference](https://mlsanity.com/paper/2601.21131/) (2026)
- [A Diffusion Analysis of Policy Gradient for Stochastic Bandits](https://mlsanity.com/paper/2603.10219/) (2026)

## Abstract (arXiv)

We study the sampling allocation of LinUCB in the small-gap regime, where the reward gaps are of order at most n-1/2 over the decision horizon n. This scaling captures the hard instances underlying worst-case regret lower bounds, for which LinUCB is known to be near optimal up to logarithmic factors in n. Using a mean-field perspective, we characterize this allocation through the empirical sampling distribution, a macroscopic object that averages the effect of adaptive decisions over the horizon, and identify its limit as n→∞. We establish that in this regime, the empirical sampling distribution induced by LinUCB converges to the set of D-optimal designs. This central result reveals that, in the small-gap regime, LinUCB not only achieves near optimal minimax regret but also allocates samples in a way that is asymptotically efficient for learning the reward parameter, thereby connecting regret-driven online learning with information-efficient experimental design. Building on the optimal design limit, we obtain two useful consequences. First, we refine the asymptotic regret analysis of LinUCB in the small-gap regime by characterizing its leading-order constant in the limit. Second, we show that, despite LinUCB's adaptive sampling strategy, the regularized least-squares estimator satisfies a central-limit-type theorem in the small-gap regime, thereby enabling valid statistical inference for the reward parameter.