Technical Summary: Closing the Gap on the Sample Complexity of 1-Identification

Problem Formulation

The paper addresses the 1-identification problem, a pure-exploration variant of the multi-armed bandit (MAB) framework. The objective is to determine whether there exists at least one arm $a$ in a set of $K$ arms such that its mean reward $r_a$ exceeds a known threshold $\mu_0$.

• Positive Instance: $\max_a r_a > \mu_0$. The algorithm must identify (at least) one such arm.
• Negative Instance: $\max_a r_a < \mu_0$. The algorithm must output "None".
• Guarantee: The algorithm must be $\delta$-Probably Approximately Correct (PAC), ensuring the probability of a correct decision is at least $1-\delta$. The primary metric of interest is the expected sample complexity $E[\tau]$.

The problem is distinct from standard Best-Arm Identification (BAI) as it does not require ranking all arms or identifying the single best arm, but rather finding any arm above a threshold. While the sample complexity for negative instances is well-understood (closely related to BAI), the complexity for positive instances, particularly those with multiple qualified arms ($m > 1$), has remained an open problem with loose existing bounds.

Methodology

1. Lower Bound Analysis

The authors derive a new lower bound for positive instances using a novel optimization formulation, moving away from the traditional "Simulator" framework which often yields loose bounds for complex instances.

• Symmetry Reduction: The proof begins by showing that for lower bound purposes, one can restrict attention to symmetric algorithms (algorithms invariant under arm label permutations).
• Convex Optimization: The core of the lower bound proof involves constructing a convex optimization problem. The expected sample complexity $E[\tau]$ is shown to be lower-bounded by the optimal value of this problem.
• Dual Solution: By constructing a specific feasible dual solution, the authors derive a tight lower bound that depends on both the confidence parameter $\delta$ and the instance-dependent gaps. The bound is expressed as:
  $$\Omega\left( \min_{1 \le j \le m} \left\{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + \frac{H(j)}{\log^2(m+1)} \right\} \right)$$
  where $\Delta_{j,0} = \mu_j - \mu_0$ and $H(j)$ is a complexity term involving the gaps between arms.

2. Algorithm Design: PSEEB

To match the lower bound, the paper proposes Parallel Sequential Exploration–Exploitation on Brackets (PSEEB).

• Bracketing Mechanism: The algorithm generates a nested family of "brackets" (subsets of arms) $\{B_b\}$ based on a single random permutation of the arms. $B_1 \subset B_2 \subset \dots \subset B_{\lceil \log_2 K \rceil + 1} = [K]$, where $|B_b| \approx 2^b$.
• Parallel Execution: The algorithm runs $\lceil \log_2 K \rceil + 1$ independent copies of a base Sequential Exploration-Exploitation (SEE) algorithm (adapted from Li and Cheung, 2025). Each copy operates exclusively on one bracket $B_b$.
• Round-Robin Scheduling: The copies are executed in a round-robin fashion. The global algorithm terminates as soon as any copy outputs a valid arm or "None".
• Stopping Rules:
  • Only the copy operating on the full set of arms ($B_{\lceil \log_2 K \rceil + 1}$) is permitted to output "None".
  • Copies operating on smaller brackets continue sampling even if they suspect no qualified arm exists within their subset, ensuring they do not prematurely terminate and miss a qualified arm that might be in a larger bracket.

Key Contributions and Results

1. Tight Lower Bound

The paper establishes a new lower bound for positive instances that is jointly optimal in both the $\delta$-dependent term ($\log(1/\delta)$) and the $\delta$-independent term.

• Previous works (e.g., Degenne and Koolen, 2019; Li and Cheung, 2025) achieved near-optimality only for cases with a single qualified arm ($m=1$) or under restricted settings.
• The new bound resolves the open problem regarding the complexity of instances with multiple qualified arms ($m > 1$), identifying $\min_{1 \le j \le m} \{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + H(j) \}$ as the correct instance-dependent complexity measure.

2. Nearly Optimal Upper Bound

The proposed PSEEB algorithm achieves an upper bound on expected sample complexity that matches the new lower bound up to polynomial logarithmic factors in $K$ and the gaps.

• Positive Instances: $E[\tau] \le O\left( \log K \cdot \min_{1 \le j \le m} \left\{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + \text{poly}(\log K, \log(1/\Delta)) \cdot H(j) \right\} \right)$.
• Negative Instances: The algorithm maintains the known optimal bounds for negative instances, $O(H_1^{neg} \log(1/\delta))$.
• Strong $\delta$-PAC: The algorithm is proven to be Strong $\delta$-PAC, meaning the expected sample complexity is finite for all instances, ruling out pathological behaviors where $E[\tau] = \infty$.

Significance and Claims

The paper claims to close the gap on the sample complexity of 1-identification for the first time in the general case of multiple qualified arms.

• Resolution of Open Problem: It explicitly resolves the open problem left by Li and Cheung (2025) regarding the improvability of the $\delta$-independent term for $m > 1$.
• Methodological Advancement: The reduction of the lower bound derivation to a convex optimization problem is presented as a significant simplification over previous "Simulator" frameworks, yielding tighter and more general results.
• Algorithmic Efficiency: By utilizing a parallel bracketing strategy, PSEEB efficiently handles the uncertainty of which arm is qualified without needing to identify the specific "best" qualified arm, thereby avoiding the unnecessary sampling costs associated with reducing 1-identification to standard BAI.

The authors note that while the bounds are nearly optimal, refining the logarithmic factors remains a direction for future research. The work provides a complete characterization of the sample complexity landscape for 1-identification across both positive and negative instances.