A Batch Sequential Halving Algorithm without Performance Degradation
In this paper, we investigate the problem of pure exploration in the context of multi-armed bandits, with a specific focus on scenarios where arms are pulled in fixed-size batches. Batching has been shown to enhance computational efficiency, but it can potentially lead to a degradation compared to the original sequential algorithm's performance due to delayed feedback and reduced adaptability. We introduce a simple batch version of the Sequential Halving (SH) algorithm (Karnin et al., 2013) and provide theoretical evidence that batching does not degrade the performance of the original algorithm under practical conditions. Furthermore, we empirically validate our claim through experiments, demonstrating the robust nature of the SH algorithm in fixed-size batch settings.
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencyMulti-Armed BanditsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Anytime Sequential Halving in Monte-Carlo Tree Search
Monte-Carlo Tree Search (MCTS) typically uses multi-armed bandit (MAB) strategies designed to minimize cumulative regret, such as UCB1, as its selection strategy. However, in the root node of the search tree, it is more …
Board GamesRevisiting Tree Search for LLMs: Gumbel and Sequential Halving for Budget-Scalable Reasoning
Neural tree search is a powerful decision-making algorithm widely used in complex domains such as game playing and model-based reinforcement learning. Recent work has applied AlphaZero-style tree search to enhance the re…
Reinforcement LearningUltra Fast Medoid Identification via Correlated Sequential Halving
The medoid of a set of n points is the point in the set that minimizes the sum of distances to other points. It can be determined exactly in O(n^2) time by computing the distances between all pairs of points. Previous wo…
Ultra Fast Medoid Identification via Correlated Sequential Halving
The medoid of a set of n points is the point in the set that minimizes the sum of distances to other points. It can be determined exactly in O(n^2) time by computing the distances between all pairs of points. Previous wo…
Bayesian online learning in the one-pass regime: Frequentist validity and uncertainty quantification
Bayesian online learning provides a coherent framework for sequential inference. However, its theoretical understanding remains limited, particularly in the one-pass setting. Existing theoretical guarantees typically req…