Parameter-Free Heavy-Tailed Bandits

Resumo Técnico: Bandidos de Cauda Pesada Sem Parâmetros

Enunciado do Problema

O artigo aborda o problema do bandido multi-braços estocástico (MAB) sob distribuições de recompensa de cauda pesada. Neste cenário, as recompensas $X$ satisfazem uma condição de momento finito $\mathbb{E}[|X|^{1+\epsilon}] \leq u$ para um expoente de cauda $\epsilon \in (0, 1]$ e um limite de momento $u < +\infty$. Embora estimadores robustos possam alcançar taxas de regret ótimas quando $\epsilon$ e $u$ são conhecidos, aplicações do mundo real (ex: finanças, publicidade) frequentemente carecem de estimativas confiáveis para esses parâmetros.

O problema central, proposto como uma questão em aberto por Genalti e Metelli (COLT 2025), é determinar as melhores garantias de regret possíveis para algoritmos que são isentos de suposições (assumption-free) em relação a $u$ e $\epsilon$. Especificamente, o artigo investiga:

1. Os trade-offs fundamentais entre regret livre de distribuição (pior caso) e dependente da distribuição (específico da instância) quando $u$ é desconhecido.
2. O custo adicional incorrido quando $\epsilon$ também é desconhecido.
3. Se um único algoritmo pode alcançar regret sublinear uniformemente para todo $\epsilon \in (0, 1]$.

Metodologia

Os autores empregam uma abordagem analítica de duas etapas:

1. Adaptatividade a $u$ ( $\epsilon$ fixo): Eles primeiro analisam o cenário onde $\epsilon$ é conhecido, mas $u$ é desconhecido. Eles definem duas taxas de regret:

   • $\Phi_{free}(K, T)$: Um limite de regret livre de distribuição e sem dependência de momento.
   • $\Phi_{dep}(K, T)$: Um limite de regret dependente da distribuição normalizado pela soma dos gaps.
     Utilizando um argumento de mudança de medida combinado com construções de instâncias específicas, eles derivam um limite inferior para o produto desses limites, estabelecendo uma "fronteira" de desempenho alcançável.

2. Design de Algoritmo (AdaR-ETC): Para corresponder aos limites derivados, os autores propõem o Adaptive Robust ETC (AdaR-ETC). Trata-se de uma estratégia de Explore-Then-Commit que utiliza:

   • Estimador de Mediana de Médias (MoM): Para estimar robustamente as médias dos braços sem exigir o conhecimento de $u$ ou $\epsilon$.
   • Exploração Agendada: O orçamento de exploração $L_T$ é ajustado via parâmetros $\alpha$ (controlando a dependência do horizonte) e $q$ (controlando a dependência do braço). No cenário de adaptatividade a $u$ (onde $\epsilon$ é conhecido), esses parâmetros são explicitamente definidos com base em $\epsilon$. No entanto, o algoritmo pode ser tornado totalmente livre de parâmetros (desconhecendo tanto $u$ quanto $\epsilon$) ao calibrar o cronograma de exploração para o ponto final de variância finita $\epsilon = 1$.

3. Adaptatividade a $(\epsilon, u)$ ( $\epsilon$ desconhecido): Os autores estendem a análise para o caso em que ambos os parâmetros são desconhecidos. Eles calam o algoritmo AdaR-ETC para o ponto final de variância finita $\epsilon = 1$ (definindo $q=1/3$ e $\alpha=2/3$) para criar uma estratégia única e livre de parâmetros. Em seguida, provam um limite inferior par para mostrar que esta calibração produz um perfil ótimo entre estratégias que mantêm a garantia ótima em $\epsilon=1$.

Contribuições Principais e Resultados

1. A Fronteira de Trade-off para $u$ Desconhecido
O artigo prova que, para qualquer estratégia que desconheça $u$, existe um trade-off nítido entre garantias livres de distribuição e dependentes da distribuição. Especificamente, para $\epsilon$ fixo:
$$\Phi_{dep}(K, T) \cdot \Phi_{free}(K, T)^{\frac{1+\epsilon}{\epsilon}} = \Omega\left(T^{\frac{1+\epsilon}{\epsilon}}\right)$$
Isso implica que melhorar a taxa de pior caso (livre de distribuição) necessariamente deteriora a taxa dependente da instância. Os autores caracterizam a "fronteira-K" e a "fronteira-T", mostrando que nenhum algoritmo único pode otimizar ambos simultaneamente.

2. O Algoritmo AdaR-ETC
O AdaR-ETC proposto alcança limites de regret que correspondem à fronteira teórica até fatores logarítmicos. Ao ajustar os parâmetros $\alpha$ e $q$, o algoritmo pode selecionar qualquer ponto operacional na fronteira de trade-off.

• Limite livre de distribuição: $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+\epsilon}(1-q)} T^{\alpha}\right)$
• Limite dependente da distribuição: $\tilde{O}\left(K^{q-1} T^{\beta_\alpha}\right)$
  onde $\beta_\alpha = (1-\alpha)(1+\epsilon)/\epsilon$.
  O ponto "equilibrado" (dependência igual de $K$ e $T$) resulta em uma taxa de $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+2\epsilon}} T^{\frac{1+\epsilon}{1+2\epsilon}}\right)$. Para o caso de variância finita ($\epsilon=1$), isso resulta em uma taxa de $\tilde{O}(T^{2/3})$, que é estritamente pior que a taxa de $\tilde{O}(\sqrt{T})$ alcançável quando $u$ é conhecido, quantificando o "preço da adaptatividade".

3. Limites da Adaptatividade Simultânea de $(\epsilon, u)$
Quando $\epsilon$ também é desconhecido, os autores propõem calibrar o AdaR-ETC para $\epsilon=1$.

• Sublinearidade Pontual: Para qualquer $\epsilon > 0$ fixo, o algoritmo calibrado alcança regret sublinear.
• Impossibilidade de Uniformidade: O artigo prova que nenhuma estratégia única pode garantir regret sublinear uniformemente para todo $\epsilon \in (0, 1]$. À medida que $\epsilon \to 0$, o expoente de $T$ aproxima-se de 1, o que significa que o regret torna-se linear.
• Otimalidade da Calibração: Entre as estratégias que mantêm a garantia ótima de $\tilde{O}(K^{1/3}T^{2/3})$ em $\epsilon=1$, o AdaR-ETC calibrado para $\epsilon=1$ mostra-se ótimo na fronteira para todos os outros $\epsilon$.

Significância e Alegações

O artigo afirma resolver o problema aberto do COLT 2025 sobre bandidos de cauda pesada sem suposições. Sua principal significância reside em:

• Caracterização do Custo Estatístico: Ele fornece uma caracterização precisa do custo estatístico de adaptar-se a caudas pesadas desconhecidas, demonstrando que a adaptação à escala desconhecida ($u$) e ordem ($\epsilon$) introduz trade-offs fundamentais, em vez de apenas fatores constantes.
• Fronteira vs. Oráculo: Estabelece que não existe uma "curva de oráculo" que seja ótima para todas as ordens de momento; em vez disso, a adaptação é descrita por uma fronteira.
• Solução Algorítmica: Fornece um algoritmo simples e livre de parâmetros (AdaR-ETC) que alcança esses trade-offs ótimos sem exigir conhecimento prévio das propriedades de cauda da distribuição.

Os autores afirmam explicitamente que seus resultados não recuperam taxas de oráculo sem suposições estruturais adicionais, confirmando que o "preço da adaptatividade" é inerente ao cenário de cauda pesada. Eles identificam os limites do regret sublinear uniforme e sugerem que trabalhos futuros devem focar no design de versões anytime do algoritmo e na identificação das suposições adicionais mais fracas necessárias para recuperar as taxas de oráculo.