# Dual-Directed Algorithm Design for Efficient Pure Exploration

arXiv: https://arxiv.org/abs/2310.19319 · HTML: https://mlsanity.com/paper/2310.19319/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2023.

## Built on by (most cited first, 6 of 6)

- [Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification](https://mlsanity.com/paper/2402.10592/) (2024)
- [Pure Exploration via Frank-Wolfe Self-Play](https://mlsanity.com/paper/2509.19901/) (2025)
- [UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity](https://mlsanity.com/paper/2511.22273/) (2025)
- [Learning with a Budget: Identifying the Best Arm with Resource Constraints](https://mlsanity.com/paper/2602.24146/) (2026)
- [Annealed Entropic Allocation for Ranking and Selection](https://mlsanity.com/paper/2606.11347/) (2026)
- [Ranking-and-Selection with Multiple Correct Answers and Non-Answerable Estimates](https://mlsanity.com/paper/2606.21889/) (2026)

## Abstract (arXiv)

While experimental design often focuses on selecting the single best alternative from a finite set (e.g., in ranking and selection or best-arm identification), many pure-exploration problems pursue richer goals. Given a specific goal, adaptive experimentation aims to achieve it by strategically allocating sampling effort, with the underlying sample complexity characterized by a maximin optimization problem. By introducing dual variables, we derive necessary and sufficient conditions for an optimal allocation, yielding a unified algorithm design principle that extends the top-two approach beyond best-arm identification. This principle gives rise to Information-Directed Selection, a hyperparameter-free rule that dynamically evaluates and chooses among candidates based on their current informational value. We prove that, when combined with Information-Directed Selection, top-two Thompson sampling attains asymptotic optimality for Gaussian best-arm identification, resolving a notable open question in the pure-exploration literature. Furthermore, our framework produces asymptotically optimal algorithms for pure-exploration thresholding bandits and varepsilon-best-arm identification (i.e., ranking and selection with probability-of-good-selection guarantees), and more generally establishes a recipe for adapting Thompson sampling across a broad class of pure-exploration problems. Extensive numerical experiments highlight the efficiency of our proposed algorithms compared to existing methods.