Nonlinear sequential accepts and rejects for identification of top arms in stochastic bandits

Shahin Shahrampour, Vahid Tarokh

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.

Comparison of sampling complexity between SAR and NSAR across two reward regimes.

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.

Error probabilities for different algorithms across six experimental setups with M=2 and M=4.

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

Abstract

We address the M-best-arm identification problem in multi-armed bandits. A player has a limited budget to explore K arms (M <; K), and once pulled, each arm yields a reward drawn (independently) from a fixed, unknown distribution. The goal is to find the top M arms in the sense of expected reward. We develop an algorithm which proceeds in rounds to deactivate arms iteratively. At each round, the budget is divided by a nonlinear function of remaining arms, and the arms are pulled correspondingly. Based on a decision rule, the deactivated arm at each round may be accepted or rejected. The algorithm outputs the accepted arms that should ideally be the top M arms. We characterize the decay rate of the misidentification probability and establish that the nonlinear budget allocation proves to be useful for different problem environments (described by the number of competitive arms). We provide comprehensive numerical experiments showing that our algorithm outperforms the state-of-the-art using suitable nonlinearity.
BibTeX
@inproceedings{shahrampour2017nonlinear,
  author = {Shahin Shahrampour and Vahid Tarokh},
  title = {{Nonlinear sequential accepts and rejects for identification of top arms in stochastic bandits}},
  booktitle = {Allerton},
  year = {2017},
  url = {https://openreview.net/forum?id=SryxsvF5hlz},
}
Figure