Fundamental Limitations of Fixed-Budget Best-Arm Identification

Resumo Técnico: Limitações Fundamentais da Identificação do Melhor Braço com Orçamento Fixo

Formulação do Problema
O artigo aborda o problema da Identificação do Melhor Braço (Best-Arm Identification - BAI) com Orçamento Fixo, também conhecido como Ranking e Seleção. Neste cenário, um tomador de decisão amostra sequencialmente $K$ braços, cada um gerando recompensas independentes de uma distribuição com uma média desconhecida $\mu_k$. O objetivo é identificar o braço com a maior média, $i^*(\mu)$, utilizando um orçamento total de amostragem fixo $T$. A métrica de desempenho é a probabilidade de identificação incorreta, $p_{\mu, T}$, especificamente sua taxa de decaimento exponencial conforme $T \to \infty$:
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

A questão teórica central é se existe uma "complexidade" para este problema. Uma complexidade é definida como uma função $\Gamma^*(\mu)$ que satisfaz duas condições:

1. Limite Superior Universal: Para todo algoritmo e toda instância $\mu$, a taxa de decaimento do erro é limitada superiormente por $\Gamma^*(\mu)$.
2. Alcançabilidade Uniforme: Existe um único algoritmo que alcança esta taxa de decaimento $\Gamma^*(\mu)$ uniformemente para todas as instâncias do problema $\mu$.

O artigo investiga se a taxa do oráculo estático (static oracle), $\Gamma^*_{so}(\mu)$, serve como esta complexidade. O oráculo estático representa a taxa de decaimento de erro ótima alcançável por uma estratégia não adaptativa que conhece as médias verdadeiras $\mu$ antecipadamente e aloca amostras em proporções fixas para maximizar a taxa de decaimento. Embora algoritmos adaptativos tenham sido desenhados para que suas proporções de amostragem converjam para estas proporções estáticas ótimas, permanecia uma questão em aberto se qualquer algoritmo adaptativo poderia igualar a taxa de decaimento de erro do oráculo estático uniformemente para todas as instâncias.

Metodologia
Os autores empregam uma prova por contradição para demonstrar que nenhum algoritmo único pode alcançar a taxa do oráculo estático uniformemente para todas as instâncias quando $K \geq 3$. A metodologia baseia-se nos seguintes componentes:

1. Razões de Dificuldade: Seguindo Degenne (2023), o artigo utiliza a razão de dificuldade $R_{H, \infty}(A, \mu)$, que mede o desempenho de um algoritmo $A$ em relação a uma função de dificuldade de referência $H(\mu)$. Se uma complexidade existe, deve haver um algoritmo onde o supremo desta razão sobre todas as instâncias seja $\leq 1$.
2. Teorema 1 (Degenne 2023): A prova utiliza uma desigualdade fundamental de Degenne (2023) que limita o desempenho de qualquer família de algoritmos adaptativos consistentes. Para qualquer benchmark $H$ e um conjunto de instâncias alternativas $D(\mu)$, o inverso da pior razão de dificuldade é limitado por um problema de otimização estática sobre proporções de amostragem $\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. Construção de Instância: Para provar a não existência de complexidade, os autores constroem uma instância "base" específica $x$ e uma família de instâncias alternativas $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$.
   • $\lambda_A$: Diferencia-se de $x$ apenas nos braços 1 e 2. Distinguir $x$ de $\lambda_A$ requer amostragem significativa dos braços 1 e 2.
   • $\lambda_{B,j}$ (para $j \in \{3, \dots, K\}$): Diferencia-se de $x$ apenas no braço $j$, tornando o braço $j$ o novo melhor braço. Distinguir $x$ de $\lambda_{B,j}$ requer amostragem significativa do braço $j$.
   • A construção garante que os braços "mais difíceis" de distinguir variam ao longo da família. Uma única alocação de amostragem $\omega$ não pode ser simultaneamente ótima para distinguir $x$ de todos os membros de $D(x)$ porque a informação necessária está concentrada em conjuntos de braços disjuntos.

Principais Resultados
O artigo estabelece um resultado negativo fundamental para o BAI com orçamento fixo:

• Recompensas Gaussianas: Para $K \geq 3$ braços com recompensas Gaussianas (variância 1), os autores provam que, para qualquer família de algoritmos consistentes, existe uma instância $\mu$ tal que a razão de dificuldade relativa ao oráculo estático excede 1. Especificamente:
  $$\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)$$
  Este limite inferior é estritamente maior que 1 para todos os $K \geq 3$, provando que nenhum algoritmo pode igualar o oráculo estático uniformemente.

• Generalização para Famílias Exponenciais Naturais (NEF): O resultado é estendido para qualquer família exponencial natural (NEF) de um parâmetro. Usando uma aproximação quadrática local da divergência de Kullback-Leibler (KL), os autores mostram que o resultado Gaussiano implica a mesma limitação para todas as NEFs regulares de um parâmetro.

• Respondendo à Questão em Aberto: Este trabalho responde definitivamente à questão levantada por Qin (2022) e formalizada por Degenne (2023): O BAI com orçamento fixo não admite uma complexidade para $K \geq 3$. Embora o oráculo estático forneça um limite inferior para a taxa de decaimento do erro, nenhum algoritmo adaptativo único pode alcançar este limite uniformemente para todas as instâncias do problema.

Significado e Alegações
O artigo afirma resolver uma lacuna teórica fundamental na compreensão do BAI com orçamento fixo.

• Limitação da Adaptatividade: Demonstra que a convergência das proporções de amostragem para o oráculo estático (um objetivo comum no design de algoritmos adaptativos) é insuficiente para garantir o alcance da taxa de decaimento de erro do oráculo estático. O "preço da adaptatividade" no cenário de orçamento fixo é que um algoritmo não pode ser ótimo para todas as instâncias simultaneamente.
• Escopo: O resultado preenche uma lacuna na literatura para $3 \leq K < e^{80/3}$ para recompensas Gaussianas e estende a não existência de complexidade para todas as NEFs de um parâmetro.
• Fronteira Teórica: O trabalho estabelece que a taxa do oráculo estático não é uma complexidade universal para o BAI com orçamento fixo quando $K \geq 3$. Os autores sugerem que isso implica a necessidade de alvos ou benchmarks alternativos, uma vez que o oráculo estático não pode ser alcançado uniformemente.

O artigo não propõe novos algoritmos para superar esta limitação, nem sugere aplicações específicas além das implicações teóricas para Ranking-and-Selection e Multi-Armed Bandits. A contribuição é estritamente um resultado negativo definindo os limites fundamentais do que é alcançável neste cenário.