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

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 $n\to\infty$. 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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning

• arXiv preprint · 5 October 2026

  Two-Sample Testing via Path-based Inference

  Eshant English, Wei-Cheng Lai, Yanfeng Yang and 3 others
• arXiv preprint · 6 October 2026

  Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?

  Yiran Zhang, Mo Zhou, Weihang Xu and 2 others
• arXiv preprint · 5 October 2026

  From Pixels, Without Pre-training: Joint Generative and Self-Supervised Representation Learning in One Model

  Vicente Balmaseda, Ching-Long Lin and Tianbao Yang
• arXiv preprint · 6 October 2026

  Learning a Mixture of GFlowNets

  Tiago da Silva, Amauri H. Souza and Salem Lahlou
• arXiv preprint · 5 October 2026

  Retrieval-Based In-Context Learning: A Domain Adaptation Framework

  Yilun Zhu, Naihao Deng, Yingcong Li and 2 others

All new papers in Machine Learning