Resumo Técnico: Um Algoritmo Conjuntamente Eficiente e Ótimo para Bandidos GLB Heterocedásticos com Corrupções Adversariais

1. Configuração do Problema

O artigo aborda o problema de Bandidos de Modelos Lineares Generalizados (GLBs) Heterocedásticos na presença de corrupções adversariais. Esta configuração unifica três aspectos desafiadores da tomada de decisão sequencial:

1. Modelos Lineares Generalizados (GLMs): A recompensa esperada para um braço $x_t \in \mathbb{R}^d$ segue um GLM, $E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$, onde $\mu$ é uma função de ligação inversa conhecida e $\theta^\star$ é um parâmetro desconhecido. Este arcabouço abrange bandidos logísticos, de Poisson e gaussianos lineares.
2. Heterocedasticidade: A variância da recompensa não é constante, mas varia entre os braços e os passos de tempo. Especificamente, $\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$, onde $g(\tau_t)$ é um parâmetro de dispersão que pode ser exogenamente variável no tempo (ex: em bandidos gaussianos) ou determinado endogenamente pela escolha do braço (ex: em bandidos logísticos/Poisson).
3. Corrupções Adversariais: Um adversário adaptativo manipula a recompensa observada em cada passo $t$ adicionando uma corrupção $c_t$, de tal forma que o aprendiz observa $\tilde{r}_t = r_t + c_t$. O adversário opera sob uma restrição de orçamento total $\sum_{t=1}^T |c_t| \le C$.

O objetivo é minimizar o pseudo-regret cumulativo, definido como a diferença entre a recompensa esperada do braço ótimo e o braço escolhido ao longo de $T$ rodadas.

2. Metodologia: HCW-GLB-OMD

Os autores propõem o HCW-GLB-OMD (Hessian-Confidence Weighted GLB-OMD), um algoritmo projetado para ser tanto computacionalmente eficiente quanto estatisticamente ótimo. O algoritmo integra dois componentes primários:

A. Estimador de Descida de Gradiente Online (OMD)

Ao contrário de abordagens anteriores que dependem de Estimativa de Máxima Verossimilhança (MLE) em lote, o que cria um descompasso de índice temporal entre pesos locais e estimativas globais, o HCW-GLB-OMD utiliza um estimador OMD online. A atualização do parâmetro no passo $t$ é definida como:
$$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$$
onde $\tilde{\ell}_t$ é uma log-verossimilhança negativa ponderada. Esta abordagem online garante que o estimador, o braço e os pesos estejam alinhados no mesmo passo de tempo local, facilitando uma análise rigorosa dos impactos da corrupção.

B. Pesos de Confiança Baseados no Hessiano

Para alcançar robustez contra corrupções, o algoritmo atribui um peso de confiança $w_t$ a cada observação com base no Hessiano local (curvatura) da função de ligação e do parâmetro de dispersão:
$$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$$
Aqui, $\|x_t\|_{H_t^{-1}}$ quantifica a incerteza na direção de $x_t$.

• Mecanismo: Se uma direção de braço for altamente incerta (grande norma na inversa do Hessiano) em relação à dispersão, o peso $w_t$ é reduzido ($<1$). Isso reduz o peso das observações de direções vulneráveis à manipulação adversária.
• Consciência de Curvatura: Diferente dos métodos de bandidos lineares que utilizam uma matriz de design, este método utiliza o Hessiano $\nabla^2 \tilde{\ell}_t$, que incorpora a inclinação local $\dot{\mu}$. Isso permite que o algoritmo se adapte à geometria específica do GLM (ex: a saturação em bandidos logísticos).

C. Sequências de Confiança Robustas à Corrupção

Os autores constroem um conjunto de confiança $C_t(\delta)$ que considera tanto o erro de estimação quanto a corrupção adversária. O raio deste conjunto inclui um termo aditivo proporcional ao orçamento de corrupção $C$:
$$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$$
A prova desta sequência baseia-se em um argumento de supermartingal aplicado a uma razão de verossimilhança ponderada, utilizando a concavidade do mapeamento $x \mapsto x^{w_t}$ para lidar com casos onde $w_t < 1$.

3. Principais Contribuições e Resultados

A. Limite Superior de Regret

O artigo estabelece um limite superior de regret para o HCW-GLB-OMD sob a suposição de que a função de ligação $\mu$ é autoconcordante (Assunção 3). Com probabilidade de pelo menos $1-\delta$, o regret é limitado por:
$$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$$
Onde:

• $\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$ é a inclinação da função de ligação no braço ótimo.
• $g_{\max} = \max_t g(\tau_t)$ é a dispersão máxima.
• $\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$ é o parâmetro de curvatura.
• $C$ é o orçamento total de corrupção.

Significância do Limite:

• Otimalidade Caso a Caso (Instance-Wise): O termo principal $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$ depende da inclinação real no braço ótimo, em vez da curvatura de pior caso $\kappa$. Isso coincide com o limite inferior minimax para GLBs sem corrupção.
• Robustez à Corrupção: O termo de corrupção escala linearmente com $C$ (especificamente $d(g_{\max} + \kappa)C$), o que é minimax otimável até um fator de curvatura $\kappa$.
• Unificação: O limite recupera simultaneamente resultados de estado da arte para bandidos lineares heterocedásticos, bandidos logísticos e bandidos de Poisson.

B. Limite Inferior Unificado de Regret

Os autores provam um limite inferior unificado para qualquer GLB heterocedástico autoconcordante com corrupções adversariais:
$$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$$
Este limite inferior:

• Subsume limites inferiores existentes para problemas específicos como bandidos logísticos, bandidos lineares heterocedásticos e bandidos lineares corrompidos.
• Confirma que o termo principal do algoritmo é minimax otimável caso a caso.
• Demonstra que o termo de corrupção $dC$ é inevitável, embora o limite superior atualmente inclua um fator $\kappa$ extra no termo de corrupção ($d\kappa C$).

C. Eficiência Computacional

Uma contribuição crítica é a eficiência do algoritmo. Ao utilizar a atualização OMD online e atualizações recursivas do Hessiano, o HCW-GLB-OMD alcança complexidade de espaço e tempo de $O(1)$ por iteração. Isso contrasta com algoritmos anteriores robustos à corrupção para GLMs (ex: CR-Eluder-UCB, GAdaOFUL) que frequentemente exigem complexidade $O(t)$ devido ao processamento em lote ou construções complexas de conjuntos de confiança.

4. Significância e Alegações

O artigo afirma fornecer o primeiro algoritmo conjuntamente eficiente e ótimo para GLBs heterocedásticos sob corrupções adversariais. Sua principal significância reside em:

1. Preencher a Lacuna: Ele resolve o compromisso entre eficiência computacional e otimalidade estatística em GLBs corrompidos. Trabalhos anteriores ou alcançavam a otimalidade com alto custo computacional ou a eficiência com limites de regret subótimos (frequentemente escalando com a curvatura de pior caso $\kappa$).
2. Otimalidade Caso a Caso: O algoritmo alcança limites de regret que se adaptam à dificuldade específica da instância (via $\dot{\mu}_{t,\star}$), em vez de depender de suposições de pior caso, mesmo na presença de corrupções.
3. Arcabouço Unificado: Oferece um único arcabouço teórico que cobre um amplo espectro de problemas de bandidos (lineares, logísticos, Poisson, heterocedásticos) sem exigir modificações algorítmicas específicas para cada problema.

Os autores observam uma lacuna remanescente: o termo de corrupção no limite superior escala com $d\kappa C$, enquanto o limite inferior é $dC$. Eles conjecturam que o fator $\kappa$ no termo de corrupção é um artefato da análise e que um limite $O(dC)$ é alcançável, mas isso permanece um problema em aberto. Adicionalmente, a análise atual assume que o parâmetro de dispersão $\tau_t$ é conhecido pelo aprendiz; lidar com $\tau_t$ desconhecido é identificado como uma direção futura.