Fundamental Limitations of Fixed-Budget Best-Arm Identification

Sintesi Tecnica: Limitazioni Fondamentali dell'Identificazione del Miglior Braccio a Budget Fisso

Formulazione del Problema
Il documento affronta il problema dell'Identificazione del Miglior Braccio (Best-Arm Identification, BAI) a Budget Fisso, noto anche come Ranking and Selection. In questo scenario, un decisore campiona sequenzialmente da $K$ bracci, ciascuno dei quali genera ricompense indipendenti da una distribuzione con una media $\mu_k$ ignota. L'obiettivo è identificare il braccio con la media più grande, $i^*(\mu)$, utilizzando un budget totale di campionamento fisso $T$. La metrica di prestazione è la probabilità di identificazione errata, $p_{\mu, T}$, specificamente il suo tasso di decadimento esponenziale per $T \to \infty$:
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

La questione teorica centrale è se esista una "complessità" per questo problema. Una complessità è definita come una funzione $\Gamma^*(\mu)$ che soddisfi due condizioni:

1. Limite Superiore Universale: Per ogni algoritmo e ogni istanza $\mu$, il tasso di decadimento dell'errore è limitato superiormente da $\Gamma^*(\mu)$.
2. Raggiungibilità Uniforme: Esiste un singolo algoritmo che raggiunge questo tasso di decadimento $\Gamma^*(\mu)$ uniformemente per tutte le istanze del problema $\mu$.

Il documento indaga se il tasso dell'oracolo statico, $\Gamma^*_{so}(\mu)$, funga da complessità per questo problema. L'oracolo statico rappresenta il tasso di decadimento dell'errore ottimale raggiungibile da una strategia non adattiva che conosce le vere medie $\mu$ in anticipo e alloca i campioni a proporzioni fisse per massimizzare il tasso di decadimento; sebbene siano stati progettati algoritmi adattivi le cui proporzioni di campionamento convergono a queste proporzioni statiche ottimali, rimaneva aperto il quesito se qualsiasi algoritmo adattivo potesse eguagliare il tasso di decadimento dell'oracolo statico uniformemente per tutte le istanze.

Metodologia
Gli autori utilizzano una dimostrazione per contraddizione per dimostrare che nessun singolo algoritmo può raggiungere il tasso dell'oracolo statico uniformemente per tutte le istanze quando $K \geq 3$. La metodologia si basa sui seguenti componenti:

1. Rapporti di Difficoltà: Seguendo Degenne (2023), il documento utilizza il rapporto di difficoltà $R_{H, \infty}(A, \mu)$, che misura la prestazione di un algoritmo $A$ rispetto a una funzione di difficoltà di riferimento $H(\mu)$. Se una complessità esiste, deve esistere un algoritmo in cui il supremo di questo rapporto su tutte le istanze sia $\leq 1$.
2. Teorema 1 (Degenne 2023): La dimostrazione sfrutta una chiave disuguaglianza di Degenne (2023) che limita la prestazione di qualsiasi famiglia di algoritmi adattivi coerenti. Per ogni benchmark $H$ e un insieme di istanze alternative $D(\mu)$, l'inverso del peggior rapporto di difficoltà è limitato da un problema di ottimizzazione statica sulle proporzioni di campionamento $\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. Costruzione dell'Istanza: Per dimostrare la non esistenza della complessità, gli autori costruiscono un'istanza "baseline" specifica $x$ e una famiglia di istanze alternative $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$.
   • $\lambda_A$: Differisce da $x$ solo nei bracci 1 e 2. Distinguere $x$ da $\lambda_A$ richiede un campionamento significativo dei bracci 1 e 2.
   • $\lambda_{B,j}$ (per $j \in \{3, \dots, K\}$): Differisce da $x$ solo nel braccio $j$, rendendo il braccio $j$ il nuovo miglior braccio. Distinguere $x$ da $\lambda_{B,j}$ richiede un campionamento significativo del braccio $j$.
     L'intera costruzione assicura che i bracci "più difficili" da distinguere varino attraverso la famiglia. Una singola allocazione di campionamento $\omega$ non può essere simultaneamente ottimale per distinguere $x$ da tutti i membri di $D(x)$ perché l'informazione richiesta è concentrata su insiemi disgiunti di bracci.

Risultati Chiave
Il documento stabilisce un risultato negativo fondamentale per la BAI a budget fisso:

• Ricompense Gaussiane: Per $K \geq 3$ bracci con ricompense gaussiane (varianza 1), gli autori dimostrano che per ogni famiglia di algoritmi coerenti $A$, esiste un'istanza $\mu$ tale che il rapporto di difficoltà rispetto all'oracolo statico superi 1. Nello specifico:
  $$\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)$$
  Questo limite inferiore è strettamente superiore a 1 per tutti i $K \geq 3$, provando che nessun algoritmo può eguagliare uniformemente l'oracolo statico.

• Generalizzazione alle Famiglie Esponenziali Naturali (NEF): Il risultato è esteso a qualsiasi famiglia esponenziale naturale (NEF) a un parametro. Utilizzando un'approssimazione quadratica locale della divergenza di Kullback-Leibler (KL), gli autori mostrano che il risultato gaussiano implica la stessa limitazione per tutte le NEF regolari a un parametro.

• Risposta alla Domanda Aperta: Questo lavoro risponde definitivamente alla domanda posta da Qin (2022) e formalizzata da Degenne (2023): la BAI a budget fisso non ammette una complessità per $K \geq 3$. Sebbene l'oracolo statico fornisca un limite inferiore al tasso di decadimento dell'errore, nessun singolo algoritmo adattivo può eguagliare uniformemente questo limite attraverso tutte le istanze del problema.

Significato e Rivendicazioni
Il documento sostiene di risolvere un vuoto teorico fondamentale nella comprensione della BAI a budget fisso.

• Limitazione dell'Adattività: Dimostra che la convergenza delle proporzioni di campionamento verso l'oracolo statico (un obiettivo di progettazione comune per gli algoritmi adattivi) è insufficiente per garantire l'eguaglianza del tasso di decadimento dell'errore dell'oracolo statico. Il "prezzo dell'adattività" nell'impostazione a budget fisso è che un algoritmo non può essere ottimale per tutte le istanze simultaneamente.
• Ambito: Il risultato colma una lacuna nella letteratura per $3 \leq K < e^{80/3}$ per ricompense gaussiane ed estende la non esistenza della complessità a tutte le NEF a un parametro.
• Confine Teorico: Il lavoro stabilisce che il tasso dell'oracolo statico non è una complessità universale per la BAI a budget fisso quando $K \geq 3$. Gli autori suggeriscono che ciò implica la necessità di obiettivi o benchmark teorici alternativi, poiché l'oracolo statico non può essere raggiunto uniformemente.

Il documento non propone nuovi algoritmi per superare questa limitazione, né suggerisce applicazioni specifiche oltre alle implicazioni teoriche per il Ranking-and-Selection e i Multi-Armed Bandits. Il contributo è strettamente un risultato negativo che definisce i limiti fondamentali di ciò che è realizzabile in questo contesto.