mlsanityData to 14 Oct 2026

A characterization of sample adaptivity in UCB data

arXiv 2503.04855 ↗First posted 6 Mar 2025stat.ML cs.LG math.PRcited by 2

Not on the map. Why?

Abstract (arXiv)

We characterize a joint CLT of the number of pulls and the sample mean reward of the arms in a stochastic two-armed bandit environment under UCB algorithms. Several implications of this result are in place: (1) a nonstandard CLT of the number of pulls hence pseudo-regret that smoothly interpolates between a standard form in the large arm gap regime and a slow-concentration form in the small arm gap regime, and (2) a heuristic derivation of the sample bias up to its leading order from the correlation between the number of pulls and sample means. Our analysis framework is based on a novel perturbation analysis, which is of broader interest on its own.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 12 of its 31 references that are in the map. First posted on arXiv 6 Mar 2025.

Builds on

12 of 31 references.

References · 12

  1. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 149
  2. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 114
  3. 2019Confidence Intervals for Policy Evaluation in Adaptive Experimentscited by 95
  4. 2017Why Adaptively Collected Data Have Negative Bias and How to Correct for Itcited by 36
  5. 2021A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithmscited by 30
  6. 2019Are sample means in multi-armed bandits positively or negatively biased?cited by 24
  7. 2021Online Multi-Armed Bandits with Adaptive Inferencecited by 22
  8. 2024UCB algorithms for multi-armed bandits: Precise regret and adaptive inferencecited by 19
  9. 2021The Fragility of Optimized Bandit Algorithmscited by 17
  10. 2021Weak Signal Asymptotics for Sequentially Randomized Experimentscited by 14
  11. 2022The Typical Behavior of Bandit Algorithmscited by 12
  12. 2023Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Riskcited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Bandit Allocational Instabilitycited by 3
  2. 2026Toward the Optimal Regret-Instability Trade-off in Multi-Armed Banditscited by 0