Fundamental Limitations of Fixed-Budget Best-Arm Identification

Technische Zusammenfassung: Fundamentale Limitationen der festen Budget-Best-Arm-Identifikation

Problemformulierung
Die Arbeit befasst sich mit dem Problem der Best-Arm-Identifikation (BAI) unter festem Budget, auch bekannt als Ranking and Selection. In diesem Szenario zieht ein Entscheider sequenziell Stichproben aus $K$ Armen, wobei jeder Arm unabhängige Belohnungen aus einer Verteilung mit einem unbekannten Mittelwert $\mu_k$ generiert. Das Ziel ist es, den Arm mit dem größten Mittelwert, $i^*(\mu)$, unter Verwendung eines festen Gesamtbudgets $T$ zu identifizieren. Die Leistungsmetrik ist die Wahrscheinlichkeit einer Fehlidentifikation, $p_{\mu, T}$, spezifisch deren exponentielle Abklingrate für $T \to \infty$:
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

Die zentrale theoretische Frage ist, ob eine „Komplexität“ für dieses Problem existiert. Eine Komplexität ist definiert als eine Funktion $\Gamma^*(\mu)$, die zwei Bedingungen erfüllt:

1. Universelle obere Schranke: Für jeden Algorithmus und jede Instanz $\mu$ ist die Abklingsrate des Fehlers nach oben durch $\Gamma^*(\mu)$ begrenzt.
2. Einheitliche Erreichbarkeit: Es existiert ein einziger Algorithmus, der diese Abklingrate $\Gamma^*(\mu)$ über alle Probleminstanzen hinweg gleichmäßig erreicht.

Die Arbeit untersucht, ob die statische Oracle-Rate, $\Gamma^*_{so}(\mu)$, als diese Komplexität dient. Das statische Oracle repräsentiert die optimale Fehlerabklingrate, die durch eine nicht-adaptive Strategie erreicht werden kann, welche die wahren Mittelwerte $\mu$ im Voraus kennt und die Stichproben auf feste Proportionen verteilt, um die Abklingsrate zu maximieren. Während adaptive Algorithmen so entworfen wurden, dass ihre Stichprobenanteile gegen diese optimalen statischen Proportionen konvergieren, blieb die Frage offen, ob ein adaptiver Algorithmus die statische Oracle-Abklingrate $\Gamma^*(\mu)$ über alle Instanzen hinweg einheitlich erreichen kann.

Methodik
Die Autoren verwenden einen Beweis durch Widerspruch, um zu zeigen, dass kein einzelner Algorithmus die statische Oracle-Rate für alle Instanzen einheitlich erreichen kann, wenn $K \geq 3$. Die Methodik stützt sich auf die folgenden Komponenten:

1. Schwierigkeitsverhältnisse (Difficulty Ratios): In Anlehnung an Degenne (2023) nutzt die Arbeit das Schwierigkeitsverhältnis $R_{H, \infty}(A, \mu)$, welches die Leistung eines Algorithmus $A$ relativ zu einer Benchmark-Schwierigkeitsfunktion $H(\mu)$ misst. Wenn eine Komplexität existiert, muss ein Algorithmus existieren, bei dem das Supremum dieses Verhältnisses über alle Instanzen $\leq 1$ ist.
2. Theorem 1 (Degenne 2023): Der Beweis nutzt eine Schlüsselungleichung aus Degenne (2023), die die Leistung einer konsistenten adaptiven Algorithmenfamilie begrenzt. Für jede Benchmark $H$ und eine Menge alternativer Instanzen $D(\mu)$ ist der Kehrwert des Worst-Case-Schwierigkeitsverhältnisses durch ein statisches Optimierungsproblem über Stichprobenanteile $\omega$ beschränkt:
   $$\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. Instanzkonstruktion: Um die Nichtexistenz von Komplexität zu beweisen, konstruieren die Autoren eine spezifische „Baseline“-Instanz $x$ und eine Familie alternativer Instanzen $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$.
   • $\lambda_A$: Unterscheidet sich von $x$ nur in den Armen 1 und 2. Die Unterscheidung von $x$ von $\lambda_A$ erfordert signifikante Stichproben der Arme 1 und 2.
   • $\lambda_{B,j}$ (für $j \in \{3, \dots, K\}$): Unterscheidet sich von $x$ nur in Arm $j$, wodurch Arm $j$ der neue beste Arm wird. Die Unterscheidung von $x$ von $\lambda_{B,j}$ erfordert signifikante Stichproben von Arm $j$.
   • Die Konstruktion stellt sicher, dass die „schwierigsten“ zu unterscheidenden Arme innerhalb der Familie variieren. Eine einzige Stichprobenallokation $\omega$ kann nicht gleichzeitig optimal sein, um $x$ von allen Mitgliedern von $D(x)$ zu unterscheiden, da die benötigte Information auf disjunkte Mengen von Armen konzentriert ist.

Kernergebnisse
Die Arbeit etabliert ein fundamentales negatives Resultat für die Best-Arm-Identifikation mit festem Budget:

• Gaußsche Belohnungen: Für $K \geq 3$ Arme mit Gaußschen Belohnungen (Varianz 1) beweisen die Autoren, dass für jede konsistente Algorithmenfamilie $A$ eine Instanz $\mu$ existiert, für die das Schwierigkeitsverhältnis relativ zum statischen Oracle größer als 1 ist. Speziell gilt:
  $$\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)$$
  Diese untere Schranke liegt für alle $K \geq 3$ strikt über 1, was beweist, dass kein Algorithmus das statische Oracle einheitlich erreichen kann.

• Verallgemeinerung auf Natürliche Exponentialfamilien (NEF): Das Ergebnis wird auf jede einparametrige natürliche Exponentialfamilie (NEF) ausgeweitet. Durch Verwendung einer lokalen quadratischen Approximation der Kullback-Leibler-Divergenz zeigen die Autoren, dass das Gaußsche Ergebnis dieselbe Limitation für alle regulären einparametrischen NEFs impliziert.

• Beantwortung der offenen Frage: Diese Arbeit beantwortet definitiv die von Qin (2022) aufgeworfene und von Degenne (2023) formalisierte offene Frage: Die Best-Arm-Identifikation mit festem Budget besitzt für $K \geq 3$ keine Komplexität. Während das statische Oracle eine untere Schranke für die Fehlerabklingrate darstellt, kann kein einziger adaptiver Algorithmus diese Schranke über alle Probleminstanzen hinweg einheitlich erreichen.

Bedeutung und Ansprüche
Die Arbeit beansprucht, eine fundamentale theoretische Lücke im Verständnis der Best-Arm-Identifikation mit festem Budget geschlossen zu zu haben.

• Limitation der Adaptivität: Sie zeigt, dass die Konvergenz der Stichprobenanteile gegen das statische Oracle (ein häufiges Designziel adaptiver Algorithmen) nicht ausreicht, um die Abklingrate des statischen Oracles zu erreichen. Der „Preis der Adaptivität“ im Setting mit festem Budget besteht darin, dass ein Algorithmus nicht gleichzeitig für alle Instanzen optimal sein kann.
• Geltungsbereich: Das Ergebnis schließt eine Lücke in der Literatur für $3 \leq K < e^{80/3}$ bei Gaußschen Belohnungen und erweitert die Nichtexistenz von Komplexität auf alle einparametrischen NEFs.
• Theoretische Grenze: Die Arbeit etabliert, dass die statische Oracle-Rate keine universelle Komplexität für die Best-Arm-Identifikation mit festem Budget ist, wenn $K \geq 3$. Die Autoren deuten an, dass dies die Notwendigkeit alternativer theoretischer Ziele oder Benchmarks impliziert, da das statische Oracle nicht einheitlich erreicht werden kann.

Die Arbeit schlägt keine neuen Algorithmen vor, um diese Limitation zu überwinden, noch deutet sie auf spezifische Anwendungen über die theoretischen Implikationen für Ranking-and-Selection und Multi-Armed Bandits hinaus. Der Beitrag ist strikt ein negatives Resultat, das die fundamentalen Grenzen dessen definiert, was in diesem Setting erreichbar ist.