Abstract
Identifying the top $M$ arms in a multi-armed bandit (MAB) problem under a fixed budget is a fundamental challenge in pure exploration. Traditional methods like Successive Accepts and Rejects (SAR) employ linear budget allocation, which can be suboptimal depending on the reward distribution. This paper introduces Nonlinear Sequential Accepts and Rejects (NSAR), which utilizes a tunable nonlinear budget allocation strategy. By adjusting a parameter $p$, NSAR adapts to different reward regimes, achieving a significant $O(\log K)$ reduction in sample complexity over state-of-the-art methods. Numerical experiments across various synthetic environments demonstrate that NSAR consistently outperforms existing algorithms in identifying the best arms.
Introduction
In the classic Multi-Armed Bandit (MAB) problem, an agent pulls "arms" to receive rewards from unknown distributions. While much research focuses on minimizing cumulative regret—balancing exploration and exploitation—many real-world applications require pure exploration. In these scenarios, the goal is to identify the $M$ best arms within a fixed budget of $T$ total pulls. For instance, in mobile channel allocation, a device must rapidly identify the highest-quality frequencies before initiating communication.
Existing algorithms, such as Successive Accepts and Rejects (SAR), typically divide the sampling budget linearly across rounds. However, linear allocation is often suboptimal, particularly when the reward gaps between arms follow specific patterns. This paper proposes Nonlinear Sequential Accepts and Rejects (NSAR), which introduces a tunable nonlinearity into the budget allocation process to enhance identification accuracy.
The NSAR Algorithm
NSAR operates in rounds, similar to the SAR framework. In each round, the algorithm pulls the remaining arms and deactivates one arm—either "accepting" it into the top $M$ set or "rejecting" it—based on its empirical performance relative to a threshold.
The innovation of NSAR lies in its nonlinear budget allocation. The number of pulls allocated to arms in round $r$ is determined by a function $(K - r + 1)^p$, where $K$ is the total number of arms and $p \in (0, 2]$ is a tunable parameter:
- $p = 1$: Recovers the standard linear SAR.
- $p < 1$: Allocates more budget to earlier rounds, which is beneficial when many arms are competitive and need more initial samples to distinguish.
- $p > 1$: Reserves more budget for later rounds, ideal for scenarios where only a few arms are truly competitive.
Theoretical Insights and Complexity
The authors identify two primary reward regimes that dictate the optimal choice of $p$. "Regime 1" describes environments with many competitive arms, where $p < 1$ is optimal. "Regime 2" describes environments with few competitive arms, where $p > 1$ is preferred.
By selecting the appropriate nonlinearity, NSAR can theoretically eliminate a $\log K$ factor from the sample complexity. In bandit theory, moving from a complexity of $O(K \log K)$ to $O(K)$ represents a substantial improvement in efficiency.
Experimental Results
The effectiveness of NSAR was evaluated through synthetic numerical experiments using Bernoulli and Beta distributions across six distinct setups. These setups ranged from simple scenarios with a single group of suboptimal arms to complex "needle in a haystack" environments where a suboptimal arm is nearly indistinguishable from the top $M$ threshold.
In simulations with $K=50$ arms, NSAR consistently demonstrated lower error probabilities compared to SAR, AT-LUCB (an anytime algorithm), and uniform allocation (UNI). The results indicate that NSAR is robust; even without perfect tuning of $p$, choosing a value in the correct range (e.g., $p \in (1, 2]$ for Regime 2) leads to superior performance.
Conclusion
NSAR provides a flexible and powerful framework for top-$M$ arm identification by leveraging nonlinear budget allocation. By adapting to the "crowdedness" of competitive arms, it achieves significant theoretical and empirical gains over linear methods. While the current implementation requires qualitative intuition to select the parameter $p$, future work aims to develop an adaptive version of NSAR that can automatically tune the nonlinearity parameter as data is collected, further automating the exploration process.
Summary updated