Fundamental Limitations of Fixed-Budget Best-Arm Identification

Technische Samenvatting: Fundamentele Beperkingen van Fixed-Budget Best-Arm Identification

Probleemformulering
Het artikel behandelt het probleem van Fixed-Budget Best-Arm Identification (BAI), ook wel bekend als Ranking and Selection. In deze setting neemt een besluitvormer sequentieel steekproeven uit $K$ armen, die elk onafhankelijke beloningen genereren uit een distributie met een onbekende gemiddelde $\mu_k$. Het doel is om de arm met het grootste gemiddelde te identificeren, $i^*(\mu)$, met behulp van een vast totaal budget $T$. De prestatie-indicator is de kans op foutieve identificatie, $p_{\mu, T}$, specifiek de exponentiële vervalrate naarmate $T \to \infty$:
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

De centrale theoretische vraag is of er een "complexiteit" bestaat voor dit probleem. Een complexiteit wordt gedefinieerd als een functie $\Gamma^*(\mu)$ die twee voorwaarden vervult:

1. Universele Bovengrens: Voor elk algoritme en elke instantie $\mu$ is de foutenvervalrate begrensd door $\Gamma^*(\mu)$.
2. Uniform Bereikbaarheid: Er bestaat een enkel algoritme dat deze vervalrate $\Gamma^*(\mu)$ uniform bereikt voor alle instanties $\mu$.

Het onderzoek onderzoekt of de statische oracle rate, $\Gamma^*_{so}(\mu)$, als deze complexiteit dient. De statische oracle vertegenwoordigt de optimale foutenvervalrate die bereikbaar is door een niet-adaptieve strategie die de ware gemiddelden $\mu$ vooraf kent en de steekproeven verdeelt over vaste proporties om de vervalrate te maximaliseren. Hoewel adaptieve algoritmen zijn ontworpen zodat hun steekproefverhoudingen convergeren naar deze optimale statische proporties, bleef het een open vraag of een adaptief algoritme de foutenvervalrate van de statische oracle uniform over alle instanties kan evenaren.

Methodologie
De auteurs maken gebruik van een bewijs uit het ongerijmde om aan te tonen dat geen enkel algoritme de statische oracle rate uniform voor alle instanties kan bereiken wanneer $K \geq 3$. De methodologie rust op de volgende componenten:

1. Moeilijkheidsratio's: Volgens Degenne (2023) maakt het artikel gebruik van de moeilijkheidsratio $R_{H, \infty}(A, \mu)$, die de prestaties van een algoritme $A$ meet ten opzichte van een benchmark moeilijkheidsfunctie $H(\mu)$. Als een complexiteit bestaat, moet er een algoritme zijn waarbij het supremum van deze ratio over alle instanties $\leq 1$ is.
2. Theorem 1 (Degenne 2023): Het bewijs maakt gebruik van een cruciale ongelijkheid uit Degenne (2023) die de prestaties van elk consistent adaptief algoritmefamilie begrenst. Voor elke benchmark $H$ en een verzameling alternatieve instanties $D(\mu)$, wordt de inverse van de slechtste-geval moeilijkheidsratio begrensd door een statisch optimalisatieprobleem over steekproefverhoudingen $\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. Constructie van Instanties: Om het niet-bestaan van complexiteit te bewijzen, construeren de auteurs een specifieke "baseline" instantie $x$ en een familie van alternatieve instanties $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$.
   • $\lambda_A$: Verschilt van $x$ alleen in armen 1 en 2. Het onderscheiden van $x$ van $\lambda_A$ vereist aanzienlijke bemonstering van armen 1 en 2.
   • $\lambda_{B,j}$ (voor $j \in \{3, \dots, K\}$): Verschilt van $x$ alleen in arm $j$, waardoor arm $j$ de nieuwe beste arm wordt. Het onderscheiden van $x$ van $\lambda_{B,j}$ vereist aanzienlijke bemonstering van arm $j$.
   • De constructie zorgt ervoor dat de "moeilijkste" armen om te onderscheiden variëren binnen de familie. Een enkele steekproefallocatie $\omega$ kan niet tegelijkertijd optimaal zijn voor het onderscheiden van $x$ van alle leden van $D(x)$, omdat de benodigde informatie geconcentreerd is op disjuncte sets van armen.

Kernresultaten
Het artikel stelt een fundamenteel negatief resultaat vast voor fixed-budget BAI:

• Gaussische Beloningen: Voor $K \geq 3$ armen met Gaussische beloningen (variantie 1), bewijzen de auteurs dat er voor elk consistent algoritmefamilie $A$ een instantie $\mu$ bestaat waarvoor de moeilijkheidsratio ten opzichte van de statische oracle groter is dan 1. Specifiek:
  $$\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)$$
  Deze ondergrens is strikt groter dan 1 voor alle $K \geq 3$, wat bewijst dat geen enkel algoritme de statische oracle uniform kan evenaren.

• Generalisatie naar Natural Exponential Families (NEF): Het resultaat wordt uitgebreid naar elke één-parameter natural exponential family (NEF). Door een lokale kwadratische benadering van de Kullback-Leibler (KL) divergentie te gebruiken, tonen de auteurs aan dat het Gaussische resultaat dezelfde beperking impliceert voor alle reguliere één-parameter NEF's.

• Beantwoording van de Openstaande Vraag: Dit werk geeft een definitief antwoord op de openstaande vraag gesteld door Qin (2022) en geformaliseerd door Degenne (2023): Fixed-budget BAI bezit geen complexiteit voor $K \geq 3$. Hoewel de statische oracle een ondergrens biedt op de foutenvervalrate, kan geen enkel adaptief algoritme deze grens uniform over alle problematische instanties bereiken.

Betekenis en Claims
Het artikel claimt een fundamentele theoretische kloof in het begrip van fixed-budget BAI te hebben opgelost.

• Beperking van Adaptiviteit: Het toont aan dat de convergentie van steekproefverhoudingen naar de statische oracle (een veelvoorkomend ontwerpdoel in adaptieve algoritmen) onvoldoende is om de foutenvervalrate van de statische oracle te evenaren. De "prijs van adaptiviteit" in de fixed-budget setting is dat een algoritme niet tegelijkertijd optimaal kan zijn voor alle instanties.
• Reikwijdte: Het resultaat vult een gat in de literatuur voor $3 \leq K < e^{80/3}$ voor Gaussische beloningen en breidt de non-existentie van complexiteit uit naar alle één-parameter NEF's.
• Theoretische Grens: Het werk stelt vast dat de statische oracle rate niet een universele complexiteit is voor fixed-budget BAI wanneer $K \geq 3$. De auteurs suggereren dat dit impliceert dat er behoefte is aan alternatieve theoretische doelen of benchmarks, aangezien de statische oracle niet uniform bereikt kan worden.

Het artikel stelt geen nieuwe algoritmen voor om deze beperking te overwinnen, noch suggereert het specifieke toepassingen buiten de theoretische implicaties voor Ranking-and-Selection en Multi-Armed Bandits. De bijdrage is strikt een negatief resultaat dat de fundamentele limieten definieert van wat bereikbaar is in deze setting.