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

arXiv:2610.06213v1 Announce Type: new Abstract: 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 noinfty. 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.

Related

• Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory
• Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
• Stochastic Linear Bandits with Parameter Noise

Source: arXiv cs.LG | 2026-10-06