Best-Of-N

Follow this topic Ask about this topic

Momentum

0 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 6Week of Sep 21

Latest papers 13

All topics

Sharp Non-Asymptotic Analysis of the Penalized Challenger in $β$ -EB-TCI for Bernoulli Bandits
Oct 1, 2026Nam Nguyen, Tuan Quang DamOptimal Sample Complexity Best-Of-N
Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam
Borrowed Strength: Best-of-N Search over a Code EncodingBreaks Self-Check Jailbreak Defenses
Jul 29, 2026Haoyu Zhang, Shibo Zheng, Xiangchen Guan +4LLM Defense Mechanisms Attack-Success Rate
1Northeastern University
Best-of-Evidence: Best-of-N Selection under Partial Verification
Jul 23, 2026Cenwei Zhang, Teng Fang, Yuxia Wang +3Best-Of-N Visual Evidence
IQuest Research · INSAIT · Technical University of Denmark
Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of- $K$ Objective
Jul 13, 2026Melveena Jolly, Midhun XavierRejection Sampling Best-Of-N
Independent Researcher
Best-of-Better- $N$ : Generating Pre-Aligned Responses with In-Context Learning
Jul 3, 2026Eric Lei, Hsiang Hsu, Chun-Fu ChenIn-Context Learning In-Context
JPMorganChase Global Technology Applied Research
Transition-Aware best-of-N sampling for Longitudinal Chest X-ray Reports
Jun 23, 2026Halil Ibrahim Gulluk, Max Van Puyvelde, Wim Van Criekinge +1Chest X-Ray Radiology Report Generation
Department of Electrical Engineering, Stanford University, Stanford, CA, USA · Department of Biomedical Data Science, Stanford University School of Medicine, Stanford, CA, USA · Department of Mathematical Modelling, Statistics & Bioinformatics, Ghent University, Ghent, Belgium
Predicting Inference-Time Scaling Gains from Labeled Validation-Set Output Statistics
Jun 2, 2026Luyang Zhang, Jingyan LiBest-Of-N Inference-Time
Carnegie Mellon University · Johns Hopkins University
BOKBO (Best of K Bad Options): Calibrated Abstention for VLA Policies
May 28, 2026Anya Singh, Cabrel Happi, Jai Relan +2Abstention Bad
Relling Systems
Reward Learning from Best-of- $N$ Preference Data: Targets, Tradeoffs, and Design Principles
May 28, 2026Rattana Pukdee, Maria-Florina Balcan, Pradeep RavikumarBest-Of-N Preference Learning
Machine Learning Department Carnegie Mellon University
On-Policy Distillation with Best-of-N Teacher Rollout Selection
May 10, 2026Ke Zhang, Yunjie Tian, Dongdi Zhao +4Online-Policy Distillation Token-Level Supervision
Johns Hopkins University · TikTok · University of California, San Diego +1
RSRCC: A Remote Sensing Regional Change Comprehension Benchmark Constructed via Retrieval-Augmented Best-of-N Ranking
Apr 22, 2026Roie Kazoom, Yotam Gigi, George Leifman +2Remote Sensing Change Detection
Google Research
Flexible Empowerment at Reasoning with Extended Best-of-N Sampling
Apr 17, 2026Taisuke KobayashiStochastic Exploration Offline Reinforcement Learning
National Institute of Informatics and The Graduate University for Advanced Studies, SOKENDAI Japan
SCATR: Simple Calibrated Test-Time Ranking
Apr 16, 2026Divya Shyamal, Marta Knežević, Lan Tran +3Test-Time Scaling Destination-Only Scoring
EPFL · MIT

Oct 1, 2026, cs.LGJ/K move · Enter open · S save

Sharp Non-Asymptotic Analysis of the Penalized Challenger in $β$ -EB-TCI for Bernoulli Bandits

Nam Nguyen, Tuan Quang Dam

Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam

Optimal Sample Complexity Best-Of-N Finite Time Analysis Sample Complexity Stochastic Exploration Penalties+1

Open paper AskPDF arXiv

Top-two algorithms are simple and effective for fixed-confidence best-arm identification, but their sharp non-asymptotic behavior is still not well understood. We study this problem for Bernoulli bandits through

β

-EB-TCI, the empirical-best top-two rule of Jourdan et al., whose challenger is chosen using a Bernoulli transportation cost with a logarithmic count penalty. We prove that, after the empirical leader has become the true best arm and its sampling fraction stays close to

β

, the stopping time is

T_β^{\star}(μ)\log(1/δ)

up to lower-order concentration terms. We also show that, in this regime, every challenger is sampled linearly often. Thus, for the original algorithm without forced exploration, the main remaining difficulty is to control when the empirical leader becomes permanently correct. These results imply a non-asymptotic high-probability bound for all Bernoulli instances with a unique best arm. If the algorithm satisfies a finite-mean sufficient-exploration condition, the bound further yields the sharp expected sample complexity. In particular, this gives the sharp expectation result for the unguarded Bernoulli rule when all arm means are pairwise distinct, using the sufficient-exploration result of Jourdan et al. Finally, if we add a mild forced-exploration rule that contributes only

O(\sqrt{Kt})

pulls up to time

t

, we obtain a self-contained expected sample-complexity theorem for any number of arms under the unique-best-arm assumption. We also identify a limitation of proof strategies that try to handle equal suboptimal means through a single index-comparison argument.

Momentum

Related topics

Latest papers 13