Abstract
The classification bandit problem aims to determine whether a set of given $K$ arms contains at least $L$ good arms or not. Here, an arm is said to be good if its expected reward is no less than a pre-defined threshold. This paper, presented at AISTATS 2023, introduces P-tracking (Posterior Tracking), a new algorithm that achieves theoretical optimality while being significantly faster and more sample-efficient than previous state-of-the-art methods.
Introduction
The authors address the classification bandit problem in the fixed-confidence pure exploration setting. A practical example is cytodiagnosis, where a doctor must decide if a specimen with thousands of cells ($K$ arms) contains at least $L$ malignant cells. The goal is to reach a correct binary decision with a pre-defined confidence level $1-\delta$ using the minimum number of samples.
Existing "tracking" algorithms, such as C-Tracking and D-Tracking, are asymptotically optimal but suffer from two major practical flaws: high computational complexity—requiring the solution of complex optimization problems in every round—and inefficient "forced exploration" rules that waste samples on non-informative arms.
Methodology
P-tracking introduces two primary innovations to overcome these limitations:
- Implicit Exploration via Posterior Sampling: Instead of empirical means and rigid forced exploration, P-tracking employs a Bayesian approach. It draws samples from the posterior distribution of each arm. The inherent uncertainty in these samples provides "implicit" exploration, naturally focusing on arms with high uncertainty without needing artificial rules.
- Efficient $O(K)$ Optimization: The authors demonstrate that the complex semi-infinite linear program used for optimal arm allocation can be reduced to a discrete optimization problem solvable in $O(K \log K)$ or even $O(K)$ time. This makes the algorithm scalable to large-scale problems.
Key Insights
- Structural Efficiency: Classifying a set is more efficient than identifying every arm's status. Sample complexity scales with $O(L \log 1/\delta)$ for positive models, rather than $O(K \log 1/\delta)$.
- Posterior Samples as Plug-ins: Using posterior samples to calculate optimal allocations allows the algorithm to bypass forced exploration while maintaining asymptotic optimality.
- Geometric Guarantees: The authors provide a geometric proof showing that posterior sampling ensures sufficient exploration to identify the true optimal allocation.
Experimental Results
The algorithm was evaluated using synthetic Bernoulli bandit environments with varying numbers of arms ($K$), thresholds ($L$), and actual good arms ($M$).
Sample Efficiency
In large-scale simulations ($K=100$), P-tracking consistently outperformed C-Tracking, D-Tracking, and heuristics like LUCB and Thompson Sampling-CB in terms of average stopping time.
Exploration Patterns
Heat maps of arm selection reveal that P-tracking avoids the "striped" patterns characteristic of forced exploration in traditional tracking algorithms. This indicates a more adaptive and focused sampling strategy.
Conclusion and Future Work
P-tracking represents a significant advancement in classification bandits, offering both theoretical optimality and practical efficiency. Future research directions include extending the $O(K)$ optimization and optimality proofs to broader distribution classes (e.g., Gaussian) and adapting the posterior tracking framework to the fixed-budget setting.
Summary updated