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→∞. 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
- Optimal sampling density design for homotopic off-the-grid deconvolution
- Optimal Dynamic Resource Allocation for Multicore Real-time Systems
- Optimal Allocation and Volume under Surface
- Randomized Adaptive Sequential Allocation and the Limits of Bounded Exposure to Inferior Treatments
- Error analysis and optimal sample allocation for randomized unbiased estimation: the single term estimator
BibTeX
@misc{liu2026sampling,
title = {{Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime}},
author = {Yujie Liu and Vincent Y. F. Tan and Yunbei Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06213},
eprint = {2610.06213},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06213},
}
RIS
TY - UNPB
TI - Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime
AU - Yujie Liu
AU - Vincent Y. F. Tan
AU - Yunbei Xu
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06213
UR - https://arxiv.org/abs/2610.06213
AB - 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.
ER -