A Bad Arm Existence Checking Problem

Koji Tabata, Atsuyoshi Nakamura, Junya Honda, Tamiki Komatsuzaki

Abstract

We study a bad arm existing checking problem in which a player's task is to judge whether a positive arm exists or not among given K arms by drawing as small number of arms as possible. Here, an arm is positive if its expected loss suffered by drawing the arm is at least a given threshold. This problem is a formalization of diagnosis of disease or machine failure. An interesting structure of this problem is the asymmetry of positive and negative (non-positive) arms' roles; finding one positive arm is enough to judge existence while all the arms must be discriminated as negative to judge non-existence. We propose an algorithms with arm selection policy (policy to determine the next arm to draw) and stopping condition (condition to stop drawing arms) utilizing this asymmetric problem structure and prove its effectiveness theoretically and empirically.

Introduction

In fields like medical diagnosis (e.g., cancer detection via Raman spectroscopy) or industrial monitoring, researchers often face a "needle in a haystack" problem. You have a large grid of points to test, and you need to know if any of them are anomalous. Testing every point is prohibitively expensive or slow; for instance, a single Raman spectral image can take hours or even days to acquire.

Traditional multi-armed bandit (MAB) frameworks, such as "Best Arm Identification" or "Thresholding Bandits," typically treat positive and negative results symmetrically—they try to classify every arm or find the absolute best one. This paper identifies a gap: if our only goal is to check for existence, we don't need to be symmetric. We can stop the moment we find one "bad" arm. The authors formalize this as the Bad Arm Existence Checking (BAEC) problem, aiming to minimize sample complexity (the total number of tests) while maintaining a guaranteed error rate ($\delta$).

Methodology

The authors propose a general framework called BAEC[ASP, LB, UB], which consists of an arm-selection policy (ASP) and stopping conditions based on lower and upper confidence bounds (LB, UB).

The core innovations are:

  • $\Delta$-Dependent Asymmetric Confidence Bounds: Unlike standard symmetric bounds, these bounds are "tilted." The upper confidence interval is narrower than the lower one. This reflects the fact that proving an arm is not positive (negative) is the bottleneck for a "negative" conclusion, whereas a single high-loss observation can quickly flag a "positive" arm.
  • $APT_P$ Selection Policy: This is a modification of the "Anytime Parameter-free Thresholding" (APT) policy. While the original APT favors arms with means closest to a threshold, $APT_P$ is designed to favor arms with means significantly larger than the threshold, effectively hunting for that one positive arm that allows the algorithm to terminate early.

The approach was evaluated using synthetic Bernoulli loss distributions and the real-world iPinYou Real-Time Bidding dataset to simulate high-stakes decision-making scenarios.

Key Insights

  • Asymmetry is an Asset: The fundamental realization is that the roles of positive and negative arms are different. Finding one positive arm is sufficient for a "yes" judgment, but all arms must be proven negative for a "no" judgment.
  • Optimizing the "Gray Zone": By defining a gap $\Delta = \theta_U - \theta_L$ and using constant sequences for confidence bounds, the algorithm can stop drawing "clearly negative" arms much sooner than traditional successive elimination methods.
  • Balanced Center: A specific threshold $\theta$ is defined to act as a "balanced center" between the upper and lower thresholds, specifically optimized for asymmetric bounds.

Empirical and Theoretical Results

The proposed BAEC algorithm demonstrates significant efficiency gains:

  • Efficiency: In simulations, the asymmetric stopping condition was 1.74 to 2.08 times faster than conventional symmetric bounds when arm means were near the thresholds.
  • Optimality: The algorithm is proven to be almost asymptotically optimal as the allowed error rate $\delta$ approaches zero.
  • Policy Performance: The $APT_P$ policy consistently outperformed standard selection policies like UCB and LUCB, particularly when multiple positive arms were present.
  • Worst-Case Bounds: Theoretical analysis showed an improvement in the worst-case sample complexity per arm by a factor of $\Omega(\frac{1}{\Delta^2} \ln \frac{\sqrt{K}}{\Delta^2})$.

Conclusion and Future Work

While the BAEC framework and $APT_P$ policy show great promise, there are areas for further exploration. The current theoretical support for the speed of $APT_P$ is limited, and the behavior of the algorithm when arms fall into the "neutral" zone (between $\theta_L$ and $\theta_U$) requires more robust handling. Future research will focus on providing a more rigorous theoretical analysis to explain the observed empirical performance and refining the handling of ambiguous cases.

Summary updated

Abstract

We study a bad arm existing checking problem in which a player's task is to judge whether a positive arm exists or not among given K arms by drawing as small number of arms as possible. Here, an arm is positive if its expected loss suffered by drawing the arm is at least a given threshold. This problem is a formalization of diagnosis of disease or machine failure. An interesting structure of this problem is the asymmetry of positive and negative (non-positive) arms' roles; finding one positive arm is enough to judge existence while all the arms must be discriminated as negative to judge non-existence. We propose an algorithms with arm selection policy (policy to determine the next arm to draw) and stopping condition (condition to stop drawing arms) utilizing this asymmetric problem structure and prove its effectiveness theoretically and empirically.
BibTeX
@article{tabata2020bad,
  author = {Koji Tabata and Atsuyoshi Nakamura and Junya Honda and Tamiki Komatsuzaki},
  title = {{A Bad Arm Existence Checking Problem}},
  journal = {Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=G-4YxBUesVg},
}
Figure