Tree-based Adaptive Block Elimination with Exemplar Sampling for Best Arm Identification

We study fixed-budget best-arm identification over a finite set of candidate arms equipped with a metric. The finite action set may be large, making exhaustive arm-level exploration costly even when nearby arms have similar mean rewards. We propose TABLE (Tree-based Adaptive Block Elimination with Exemplar Sampling), which maintains a hierarchical partition of the candidate set, represents each active block by a small set of geometrically selected exemplars, uses top-two posterior sampling to focus exploration on competitive exemplars, and eliminates or refines blocks using confidence evidence. The resulting algorithm trades exhaustive arm-level sampling for a combination of statistical uncertainty and geometric approximation error. We provide a structured certification analysis that makes this trade-off explicit. Under valid adaptive confidence radii, a representability condition, and stated progress and terminal-state conditions, TABLE safely preserves the optimal block and identifies the best arm once statistical and geometric uncertainty fall below the global arm gap. For sub-Gaussian rewards, we give an implementable fixed-parameter confidence calibration and an oracle exponential expression for the error probability intersected with the favorable trajectory event; the unconditional bound retains the probability of its complement. Experiments on Bernoulli metric bandit and a structured dynamic-pricing benchmark show that TABLE is especially effective in low- and moderate-budget regimes.