# Structured Best Arm Identification with Fixed Confidence

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2017.

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

- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Monte Carlo Tree Search Algorithms for Risk-Aware and Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2211.13032/) (2022)
- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [Planning in entropy-regularized Markov decision processes and games](https://mlsanity.com/paper/2604.19695/) (2026)
- [Best Arm Identification under Additive Transfer Bandits](https://mlsanity.com/paper/2112.04083/) (2021)
- [Max-Quantile Grouped Infinite-Arm Bandits](https://mlsanity.com/paper/2210.01295/) (2022)
- [Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors](https://mlsanity.com/paper/2602.03972/) (2026)
- [An Efficient Algorithm for Thresholding Monte Carlo Tree Search](https://mlsanity.com/paper/2601.22600/) (2026)
- [varepsilon-Good Action Identification in Fixed-Budget Monte Carlo Tree Search](https://mlsanity.com/paper/2605.11324/) (2026)
- [Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification](https://mlsanity.com/paper/2609.13703/) (2026)
- [How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction](https://mlsanity.com/paper/2609.18622/) (2026)

## Abstract (arXiv)

We study the problem of identifying the best action among a set of possible options when the value of each action is given by a mapping from a number of noisy micro-observables in the so-called fixed confidence setting. Our main motivation is the application to the minimax game search, which has been a major topic of interest in artificial intelligence. In this paper we introduce an abstract setting to clearly describe the essential properties of the problem. While previous work only considered a two-move game tree search problem, our abstract setting can be applied to the general minimax games where the depth can be non-uniform and arbitrary, and transpositions are allowed. We introduce a new algorithm (LUCB-micro) for the abstract setting, and give its lower and upper sample complexity results. Our bounds recover some previous results, which were only available in more limited settings, while they also shed further light on how the structure of minimax problems influence sample complexity.