TL;DR
This paper introduces the batched coarse ranking problem in Multi-Armed Bandits (MAB), where the goal is to partition arms into clusters of specific sizes based on their hidden means using a limited number of interaction rounds. The authors provide near-optimal algorithms for both fixed-budget and fixed-confidence settings, demonstrating that high-quality ranking is possible even when the number of policy changes (batches) is very small.
The Challenge of Coarse Ranking in Batches
In traditional Multi-Armed Bandit problems, researchers often look for the single "best" arm or the "top-$m$" arms. Coarse ranking generalizes these tasks: given $n$ arms, the objective is to sort them into $k$ clusters of predefined sizes (e.g., the top 10, the next 20, and the rest).
Most existing MAB algorithms are "fully adaptive," meaning they decide which arm to pull next based on every single previous result. However, in many real-world scenarios—like medical trials, crowdsourcing, or large-scale simulations—this level of continuous adaptation is impractical. It is often much more efficient to pull arms in batches, where a set of pulls is determined at the start of a round, and the policy is only updated after the entire batch is processed. This paper explores the fundamental trade-offs between the total number of arm pulls and the number of rounds (batches) required to achieve an accurate coarse ranking.
Proposed Methods: SRank and BRank
The authors propose two primary algorithms based on the "Successive Rejects" (SAR) framework, adapted for coarse ranking under batched constraints:
- SRank (Fixed Budget): Designed for scenarios with a set number of total pulls ($T$) where the goal is to minimize the probability of misclassification. It proceeds in $R$ rounds, identifying and "locking in" the arms with the largest empirical gaps (the distance between their estimated mean and the cluster boundaries) in each round.
- BRank (Fixed Confidence): Used when the objective is to reach a specific success probability ($1-\delta$) using the minimum number of pulls. It gradually builds clusters by identifying arms whose empirical means are sufficiently far from the boundaries of the "closest" clusters.
To analyze these algorithms, the researchers introduce a new Instance Complexity measure, $H^{(\mathbf{m})}(I)$. This metric characterizes how difficult a specific set of arms is to rank based on the "gaps" between their means and the target cluster boundaries, successfully generalizing well-known complexity measures for simpler tasks like best-arm identification.
Experimental Setup and Datasets
The algorithms were evaluated on both synthetic and real-world data to validate their theoretical guarantees:
- Synthetic (Uniform & Normal): Environments with 500 arms where means are either spaced uniformly or sampled from a truncated normal distribution.
- Real-World (Movie): A subset of the MovieLens dataset containing 588 movies. The "mean" for each arm (movie) was the average user rating, normalized to a $[0, 1]$ scale.
Key Results and Insights
The batched model directly addresses the need for parallelism. By reducing the number of rounds, the learning process can be distributed more effectively, which is crucial for modern large-scale machine learning systems.
One of the most striking findings is the power of just a few rounds. You do not need many batches to see massive improvements over non-adaptive (uniform) sampling. In experiments, moving from 1 round (uniform) to just 2 or 5 rounds significantly reduced the number of misclassified arms.
- SRank Performance: In the fixed-budget setting, SRank with only 5 rounds performed nearly as well as fully adaptive state-of-the-art algorithms (like SAR), while vastly outperforming uniform sampling.
- BRank Performance: In the fixed-confidence setting, BRank successfully solved the coarse ranking problem with significantly fewer pulls than uniform sampling, while using a very small number of rounds (often fewer than 10).
- Theoretical Tightness: The authors proved lower bounds showing that their algorithms are "almost tight." This means that for a given number of rounds, you generally cannot achieve a better success probability or fewer pulls than what SRank and BRank provide. The error probability in the fixed-budget case decreases exponentially with the budget $T$, scaled by the instance complexity and the number of rounds.
Limitations and Future Work
While the upper bounds (the algorithms) are general, the lower bounds proved in the paper currently only hold for a specific cluster size vector $\mathbf{m} = (0, 1, n)$. Proving a general lower bound for any arbitrary cluster configuration remains an open challenge.
Additionally, the current model assumes the sizes of the clusters are known in advance. Future research could explore "agnostic" coarse ranking where the target cluster sizes are not predefined. Finally, extending this framework to "restless" or non-stationary bandits—where the distribution of each arm changes over time—would be a valuable next step for dynamic real-world applications.
Summary updated