Posterior Tracking Algorithm for Classification Bandits

Koji Tabata, Junpei Komiyama, Atsuyoshi Nakamura, Tamiki KomatsuzakiAISTATS 2023 · OpenReview

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:

  1. 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.
  2. 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.

Average stopping times for K=100. P-tracking (blue) consistently shows the lowest number of samples required across different thresholds (L) and actual good arm counts (M).

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.

Heat maps of arm selection. P-tracking (a) exhibits a smoother, more adaptive sampling distribution compared to the rigid, striped forced exploration of C-Tracking (b) and D-Tracking (c).

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

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 ...
BibTeX
@inproceedings{tabata2023posterior,
  author = {Koji Tabata and Junpei Komiyama and Atsuyoshi Nakamura and Tamiki Komatsuzaki},
  title = {{Posterior Tracking Algorithm for Classification Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=Qnz_TMm6DKv},
}
Figure