Abstract
In the fixed-budget best-arm identification (BAI) problem with Normal reward distributions, a forecaster must identify the best of $K$ arms within $T$ time steps. While frequentist algorithms can achieve a simple regret that decays exponentially with $T$, the Bayesian simple regret typically decays polynomially. This paper demonstrates a surprising discrepancy: the Bayes optimal algorithm—designed to minimize Bayesian simple regret—fails to achieve exponential simple regret in certain frequentist settings. By introducing the concept of "expected Bellman improvement" (EBI) to analyze the otherwise intractable recursive equations of the Bayes optimal policy, we prove that the algorithm's performance is fundamentally limited by its average-case optimization strategy.
Introduction
The Fixed-Budget Best Arm Identification (BAI) problem is a cornerstone of sequential decision-making. Given $K$ treatments and a finite budget of $T$ trials, the goal is to identify the treatment with the highest mean reward. Performance is measured by "simple regret," which quantifies the gap between the true best arm and the arm selected at the end of the experiment.
In statistical theory, we often distinguish between frequentist performance (performance on a fixed, specific instance) and Bayesian performance (average performance across a prior distribution). While the Bernstein–von Mises theorem suggests that Bayesian and frequentist methods often converge in static settings, this paper reveals a significant divergence in adaptive experiments. Specifically, we show that the Bayes optimal algorithm, the theoretical gold standard for average-case performance, is surprisingly suboptimal when evaluated through a frequentist lens.
The Expected Bellman Improvement (EBI)
The Bayes optimal algorithm is defined by a recursive Bellman equation that is notoriously difficult to compute or analyze directly. To bridge this gap, this research introduces the Expected Bellman Improvement (EBI).
EBI measures the expected reduction in simple regret resulting from a single additional sample of a specific arm. By redefining the Bayes optimal algorithm as one that greedily selects the arm with the largest EBI, we gain a mathematical framework to track how the algorithm allocates its budget. This allows for a rigorous analysis of the algorithm's sampling behavior in scenarios where the best arm appears "unlucky" in early trials.
The "Laziness" of Bayes Optimality
The core insight of this paper is the discovery of why the Bayes optimal algorithm fails to reach exponential convergence. In the frequentist world, a robust algorithm should eventually correct for early noise. However, the Bayes optimal algorithm is "lazy" by design: it seeks to minimize the average regret across all possible worlds defined by the prior.
If the best arm yields poor initial results due to random noise, the Bayes optimal algorithm may calculate that the probability of this arm being the winner is so low that it is no longer worth the budget to investigate it. Instead of attempting to recover the "unlucky" best arm, the algorithm spends its remaining samples distinguishing between other, more likely candidates. While this strategy minimizes average regret, it leads to a total failure in specific frequentist instances where the best arm started with a deficit.
Key Results and Simulations
The theoretical heart of the paper is Theorem 2, which proves that there exists a frequentist instance where the simple regret of the Bayes optimal algorithm is $\Omega(T^{-C})$. This is a polynomial decay rate, which stands in stark contrast to frequentist algorithms like Successive Rejects (SR), which achieve an exponential decay rate of $e^{-T}$.
To validate these theoretical findings, computer simulations were conducted using synthetic three-armed bandit environments with Gaussian rewards. The simulations compared a frequentist benchmark (Successive Rejects) against an Approximate Bayes Optimal (ABO) algorithm. The results confirmed the theory: while the frequentist algorithm's regret plummeted toward zero, the ABO algorithm's regret flattened, trapped by its own average-case logic.
Conclusion and Future Directions
This research highlights a fundamental tension in adaptive experimental design: optimizing for the average case can lead to disastrously sub-optimal behavior in specific, unlucky scenarios.
However, some questions remain. The current proof relies on a specific "worst-case" scenario where two suboptimal arms have identical means. The author proposes Conjecture 8, suggesting that the Bayes optimal algorithm might still achieve exponential convergence for "almost all" parameters, excluding these specific edge cases. Future work will focus on determining the boundaries of this suboptimality and whether more computationally efficient versions of the EBI-based algorithm can be developed for practical use.
Summary updated