Introduction
In the "pure exploration" setting of Multi-Armed Bandits (MAB), an agent seeks to identify the best-performing action (the "arm") with a very high confidence level ($1-\delta$) while minimizing the number of trials or queries. In high-stakes real-world scenarios—such as clinical trials or product testing—the acceptable error probability $\delta$ must be extremely small. Traditionally, this makes the $\log(1/\delta)$ factor in query complexity a significant bottleneck.
Standard algorithms typically exhibit a query complexity where the difficulty of "discovering" the best arm is multiplied by this confidence factor (i.e., $\text{Discovery} \times \log(1/\delta)$). However, for many structured MAB problems where arms have known relationships (e.g., linear or unimodal rewards), it is often much easier to verify that a specific candidate is the best arm than it is to discover it from scratch.
This paper introduces the Explore-Verify framework, a general strategy that decouples the task into a low-confidence discovery phase and a high-confidence verification phase. By doing so, the authors prove that identifying the best arm is essentially as easy as verifying it, turning a multiplicative query complexity into a much more efficient additive one.
The Explore-Verify Framework
The core methodological contribution is the Explore-Verify Framework, which operates in a continuous loop until the best arm is confidently identified:
- Explore: The algorithm calls a
FindBestArmprocedure with a constant (relaxed) failure probability. Because the confidence requirement is low, this step is relatively cheap. It outputs a candidate arm and an "advice vector" (estimates of the reward gaps between arms). - Verify: The algorithm then calls a
VerifyBestArmprocedure using the candidate and the advice. This procedure is designed to be highly query-efficient, focusing its queries on the most "dangerous" competitors to the candidate to achieve the target high-confidence $1-\delta$. - Iterate: If the verification phase fails to confirm the candidate, the algorithm repeats the loop, slightly increasing the confidence requirements for the next round.
The mathematical advantage of this framework is that the heavy lifting of discovery is performed with low confidence, while the expensive high-confidence work is reserved only for verifying the likely correct candidate. This results in a total expected query complexity of: $$O(H_{explore} + H_{verify} \log(1/\delta))$$ This additive relationship is a substantial improvement over the standard $O(H_{explore} \log(1/\delta))$.
Applications and Key Results
The framework is evaluated across several mathematical bandit models, demonstrating that it matches or beats state-of-the-art solutions for specific structured problems.
As summarized in the table above, the Explore-Verify framework yields significant improvements:
- Linear Bandits: Where arm rewards are a linear function of their features in $d$-dimensional space. The framework achieves a complexity scaling with $\rho^*(Y^*)\log(1/\delta)$, where $\rho^*$ is a complexity measure from optimal experimental design. For small $\delta$, this can be up to a factor of $d$ better than previous results.
- Dueling Bandits: Where the agent compares pairs of arms rather than observing absolute rewards. Under the Condorcet assumption, the solution improves the dependence on the number of arms $K$ compared to previous generic monitoring frameworks.
- Unimodal Bandits: Where arms are nodes on a graph and rewards increase toward a single peak. On line graphs, the constant term (independent of $\delta$) is significantly reduced by replacing global gap dependencies with local neighbor gaps.
- Graphical Bandits: A generalization of dueling bandits restricted by a graph, showing a $\log^2(K)$ improvement ratio.
Key Insights
- Verification is Cheaper than Discovery: In structured settings, the "local" evidence needed to prove optimality (e.g., checking immediate neighbors in a unimodal graph) is often much smaller than the "global" evidence needed to find the optimum from scratch.
- The Power of Advice: The exploration phase does more than just output a candidate; its "advice vector" allows the verification phase to intelligently focus its queries, drastically reducing unnecessary exploration.
- Additive Complexity: The most significant theoretical insight is proving that for a wide class of problems, the dependence on the confidence parameter $\delta$ can be isolated to the verification cost ($H_{verify}$) rather than the discovery cost ($H_{explore}$).
Limitations and Future Work
While powerful, the framework has a few notable limitations:
- Oracle Dependency: The strategy requires the existence of efficient
FindBestArmandVerifyBestArmsub-routines for a given structure. If verification isn't inherently easier for a specific problem, the framework provides no benefit. - Parameter Tuning: The paper suggests default values for internal confidence parameters, but optimal performance in practice might require prior knowledge of the ratio between exploration and verification costs.
- PAC Setting: The paper primarily focuses on identifying the exact best arm. While the authors mention the framework can be extended to the "Probably Approximately Correct" (PAC) setting (finding an arm that is "good enough"), detailed proofs for that variant are left for future work.
Summary updated