Bayes Optimal Algorithm is Suboptimal in Frequentist Best Arm Identification

Junpei Komiyama

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

Abstract

We consider the fixed-budget best-arm identification problem with Normal reward distributions. In this problem, the forecaster is given $K$ arms (or treatments) and $T$ time steps. The forecaster attempts to find the best arm, defined by the largest mean, via an adaptive experiment conducted using an algorithm. The algorithm's performance is measured by the simple regret, that is, the quality of the estimated best arm. The frequentist simple regret can be exponentially small to $T$, whereas the Bayesian simple regret is polynomially small to $T$. This paper demonstrates that Bayes optimal algorithm, which minimizes the Bayesian simple regret, does not produce an exponential simple regret for some parameters, a finding that contrasts with the many results indicating the asymptotic equivalence of Bayesian and frequentist algorithms in the context of fixed sampling regimes. While the Bayes optimal algorithm is described in terms of a recursive equation that is virtually impossible to compute exactly, we establish the foundations for further analysis by introducing a key quantity that we call the expected Bellman improvement.
BibTeX
@misc{komiyama2022bayes,
  author = {Junpei Komiyama},
  title = {{Bayes Optimal Algorithm is Suboptimal in Frequentist Best Arm Identification}},
  year = {2022},
  eprint = {2202.05193},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2202.05193},
}
Figure