Fundamental Limitations of Fixed-Budget Best-Arm Identification

Technical Summary: Fundamental Limitations of Fixed-Budget Best-Arm Identification

Problem Formulation
The paper addresses the problem of Fixed-Budget Best-Arm Identification (BAI), also known as Ranking and Selection. In this setting, a decision-maker sequentially samples from $K$ arms, each generating independent rewards from a distribution with an unknown mean $\mu_k$. The goal is to identify the arm with the largest mean, $i^*(\mu)$, using a fixed total sampling budget $T$. The performance metric is the probability of incorrect identification, $p_{\mu, T}$, specifically its exponential decay rate as $T \to \infty$:
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

The central theoretical question is whether a "complexity" exists for this problem. A complexity is defined as a function $\Gamma^*(\mu)$ that satisfies two conditions:

1. Universal Upper Bound: For every algorithm and every instance $\mu$, the error decay rate is bounded above by $\Gamma^*(\mu)$.
2. Uniform Achievability: There exists a single algorithm that achieves this decay rate $\Gamma^*(\mu)$ uniformly across all problem instances $\mu$.

The paper investigates whether the static oracle rate, $\Gamma^*_{so}(\mu)$, serves as this complexity. The static oracle represents the optimal error decay rate achievable by a non-adaptive strategy that knows the true means $\mu$ in advance and allocates samples to fixed proportions to maximize the decay rate. While adaptive algorithms have been designed to have sampling proportions that converge to these optimal static proportions, it remained an open question whether any adaptive algorithm could match the static oracle's error decay rate uniformly across all instances.

Methodology
The authors employ a proof by contradiction to demonstrate that no single algorithm can achieve the static oracle rate uniformly for all instances when $K \geq 3$. The methodology relies on the following components:

1. Difficulty Ratios: Following Degenne (2023), the paper utilizes the difficulty ratio $R_{H, \infty}(A, \mu)$, which measures the performance of an algorithm $A$ relative to a benchmark difficulty function $H(\mu)$. If a complexity exists, there must be an algorithm where the supremum of this ratio over all instances is $\leq 1$.
2. Theorem 1 (Degenne 2023): The proof leverages a key inequality from Degenne (2023) that bounds the performance of any consistent adaptive algorithm family. For any benchmark $H$ and a set of alternative instances $D(\mu)$, the inverse of the worst-case difficulty ratio is bounded by a static optimization problem over sampling proportions $\omega$:
   $$\left( \sup_{\lambda \in D(\mu)} R_{H, \infty}(A, \lambda) \right)^{-1} \leq \sup_{\omega \in \Delta_K} \inf_{\lambda \in D(\mu)} \left( H(\lambda) \sum_{k=1}^K \omega_k \text{KL}(\mu_k, \lambda_k) \right)$$
3. Instance Construction: To prove the non-existence of complexity, the authors construct a specific "baseline" instance $x$ and a family of alternative instances $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$.
   • $\lambda_A$: Differs from $x$ only in arms 1 and 2. Distinguishing $x$ from $\lambda_A$ requires significant sampling of arms 1 and 2.
   • $\lambda_{B,j}$ (for $j \in \{3, \dots, K\}$): Differs from $x$ only in arm $j$, making arm $j$ the new best arm. Distinguishing $x$ from $\lambda_{B,j}$ requires significant sampling of arm $j$.
   • The construction ensures that the "hardest" arms to distinguish vary across the family. A single sampling allocation $\omega$ cannot be simultaneously optimal for distinguishing $x$ from all members of $D(x)$ because the required information is concentrated on disjoint sets of arms.

Key Results
The paper establishes a fundamental negative result for fixed-budget BAI:

• Gaussian Rewards: For $K \geq 3$ arms with Gaussian rewards (variance 1), the authors prove that for any consistent algorithm family $A$, there exists an instance $\mu$ such that the difficulty ratio relative to the static oracle exceeds 1. Specifically:
  $$\inf_{A \in \mathcal{C}_{cons}} \sup_{\mu} R_{H_{so}, \infty}(A, \mu) \geq 1 + \sum_{j=3}^K \frac{1}{(1 + \sqrt{j-1})^2} > 1 + \frac{1}{8} \log(K)$$
  This lower bound strictly exceeds 1 for all $K \geq 3$, proving that no algorithm can uniformly match the static oracle.

• Generalization to Natural Exponential Families (NEF): The result is extended to any one-parameter natural exponential family (NEF). By using a local quadratic approximation of the Kullback-Leibler (KL) divergence, the authors show that the Gaussian result implies the same limitation for all regular one-parameter NEFs.

• Answering the Open Question: This work definitively answers the open question posed by Qin (2022) and formalized by Degenne (2023): Fixed-budget BAI does not admit a complexity for $K \geq 3$. While the static oracle provides a lower bound on the error decay rate, no single adaptive algorithm can achieve this bound uniformly across all problem instances.

Significance and Claims
The paper claims to resolve a fundamental theoretical gap in the understanding of fixed-budget BAI.

• Limitation of Adaptivity: It demonstrates that the convergence of sampling proportions to the static oracle (a common design goal in adaptive algorithms) is insufficient to guarantee matching the static oracle's error decay rate. The "price of adaptivity" in the fixed-budget setting is that an algorithm cannot be optimal for all instances simultaneously.
• Scope: The result fills a gap in the literature for $3 \leq K < e^{80/3}$ for Gaussian rewards and extends the non-existence of complexity to all one-parameter NEFs.
• Theoretical Boundary: The work establishes that the static oracle rate is not a universal complexity for fixed-budget BAI when $K \geq 3$. The authors suggest that this implies the need for alternative theoretical targets or benchmarks, as the static oracle cannot be uniformly achieved.

The paper does not propose new algorithms to overcome this limitation, nor does it suggest specific applications beyond the theoretical implications for Ranking-and-Selection and Multi-Armed Bandits. The contribution is strictly a negative result defining the fundamental limits of what is achievable in this setting.