RECORD
UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity
Machine Learning · Submitted 27 Nov 2025
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim These results demonstrate the applicability of UCB algorithms to large-scale R&S problems with non-sub-Gaussian distributions.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Selecting the best alternative from a finite set is the central objective of ranking and selection (R&S) and best arm identification (BAI). Traditional R&S or BAI approaches have predominantly relied on Gaussian or sub-Gaussian assumptions on the performance distributions of all alternatives, which limit their applicability to non-sub-Gaussian---especially heavy-tailed---problems. The need to move beyond sub-Gaussianity may become even more critical in large-scale problems, which tend to be especially sensitive to distributional specifications. In this paper, motivated by the widespread use of upper confidence bound (UCB) algorithms in sequential decision making, we investigate their performance in large-scale, non-sub-Gaussian R&S settings. We consider the simplest category of UCB algorithms, where the UCB value for each alternative is defined as the sample mean plus an exploration bonus that depends only on its own sample size. We abstract this into a meta-UCB algorithm and propose letting it select the alternative with the largest sample size as the best upon stopping. For this meta-UCB algorithm, we first derive a distribution-free lower bound on the probability of correct selection. Building on this bound, we first study the indifference-zone formulation and show that the meta-UCB algorithm---and therefore a broad class of UCB algorithms---achieves sample optimality as long as the variances are uniformly bounded. We then extend sample optimality to a non-indifference-zone configuration with polynomially shrinking mean gaps under the same variance assumption. These results demonstrate the applicability of UCB algorithms to large-scale R&S problems with non-sub-Gaussian distributions. Numerical experiments support our results and provide additional insights into the comparative behaviors of UCB algorithms within and beyond our meta-UCB framework.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Selecting the best alternative from a finite set is the central objective of ranking and selection (R&S) and best arm identification (BAI). | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s1 | Traditional R&S or BAI approaches have predominantly relied on Gaussian or sub-Gaussian assumptions on the performance distributions of all alternatives, which limit their applicability to non-sub-Gaussian---especially heavy-tailed---problems. | background 0.68 | 0.04 | 0.02 | asserted 0.98 |
| s2 | The need to move beyond sub-Gaussianity may become even more critical in large-scale problems, which tend to be especially sensitive to distributional specifications. | background 0.86 | 0.06 | 0.03 | hedged possibility 1.00 |
| s3 | In this paper, motivated by the widespread use of upper confidence bound (UCB) algorithms in sequential decision making, we investigate their performance in large-scale, non-sub-Gaussian R&S settings. | contribution 0.99 | 0.63 | 0.04 | asserted 0.84 |
| s4 | We consider the simplest category of UCB algorithms, where the UCB value for each alternative is defined as the sample mean plus an exploration bonus that depends only on its own sample size. | method 0.92 | 0.48 | 0.02 | asserted 0.99 |
| s5 | We abstract this into a meta-UCB algorithm and propose letting it select the alternative with the largest sample size as the best upon stopping. | method 0.78 | 0.88 | 0.04 | asserted 0.80 |
| s6 | For this meta-UCB algorithm, we first derive a distribution-free lower bound on the probability of correct selection. | contribution 0.49 | 0.96 | 0.06 | asserted 0.99 |
| s7 | Building on this bound, we first study the indifference-zone formulation and show that the meta-UCB algorithm---and therefore a broad class of UCB algorithms---achieves sample optimality as long as the variances are uniformly bounded. | result 0.99 | 0.94 | 0.33 | asserted 1.00 |
| s8 | We then extend sample optimality to a non-indifference-zone configuration with polynomially shrinking mean gaps under the same variance assumption. | result 0.94 | 0.95 | 0.13 | asserted 1.00 |
| s9 | These results demonstrate the applicability of UCB algorithms to large-scale R&S problems with non-sub-Gaussian distributions. | interpretation 0.96 | 0.90 | 0.76 | asserted 1.00 |
| s10 | Numerical experiments support our results and provide additional insights into the comparative behaviors of UCB algorithms within and beyond our meta-UCB framework. | result 0.59 | 0.95 | 0.06 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Selecting the best alternative from a finite set is the central objective of ranking and selection (R&S) and best arm identification (BAI). Traditional R&S or BAI approaches have predominantly relied on Gaussian or sub-Gaussian assumptions on the performance distributions of all alternatives, which limit their applicability to non-sub-Gaussian---especially heavy-tailed---problems. The need to move beyond sub-Gaussianity may become even more critical in large-scale problems, which tend to be especially sensitive to distributional specifications. In this paper, motivated by the widespread use of upper confidence bound (UCB) algorithms in sequential decision making, we investigate their performance in large-scale, non-sub-Gaussian R&S settings. We consider the simplest category of UCB algorithms, where the UCB value for each alternative is defined as the sample mean plus an exploration bonus that depends only on its own sample size. We abstract this into a meta-UCB algorithm and propose letting it select the alternative with the largest sample size as the best upon stopping. For this meta-UCB algorithm, we first derive a distribution-free lower bound on the probability of correct selection. Building on this bound, we first study the indifference-zone formulation and show that the meta-UCB algorithm---and therefore a broad class of UCB algorithms---achieves sample optimality as long as the variances are uniformly bounded. We then extend sample optimality to a non-indifference-zone configuration with polynomially shrinking mean gaps under the same variance assumption. These results demonstrate the applicability of UCB algorithms to large-scale R&S problems with non-sub-Gaussian distributions. Numerical experiments support our results and provide additional insights into the comparative behaviors of UCB algorithms within and beyond our meta-UCB framework.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.