Resumo Técnico: Arrependimento Near-Ótimo em Bandits de Kernel Adversariais

1. Formulação do Problema

O artigo aborda o problema dos bandits de kernel adversariais, uma generalização dos bandits lineares adversariais onde as funções de perda pertencem a um Espaço de Hilbert de Reprodutor de Kernel (RKHS).

• Configuração: Em cada rodada $t \in [T]$, um agente seleciona uma ação $x_t$ de um conjunto de ações finito $\mathcal{X} \subset \mathbb{R}^d$. Simultaneamente, um adversário cego seleciona um vetor $w_t$ no RKHS $\mathcal{H}$.
• Perda: O agente incorre em uma perda $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$, onde $\Phi: \mathcal{X} \to \mathcal{H}$ é o mapa de características associado a um kernel simétrico e definido positivo $K$.
• Feedback: O agente observa apenas a perda escalar $\ell_t(x_t)$, e não o vetor $w_t$ ou a função de perda completa.
• Objetivo: Minimizar o arrependimento esperado $R_T$ contra a melhor ação fixa $x^*$ a posteriori:
  $$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$$
• Pressupostos: O adversário é limitado ($\|w_t\|_{\mathcal{H}} \le B$), e o kernel é limitado ($K(x,x) \le 1$). Crucialmente, ao contrário de trabalhos anteriores de Chatterji et al. [2019], o adversário não está restrito a perdas de posto único (ou seja, $w_t$ não precisa ser da forma $\Phi(z_t)$); $w_t$ pode ser qualquer elemento de $\mathcal{H}$ com norma limitada.

2. Metodologia e Algoritmo

Os autores propõem um algoritmo baseado em Pesos Exponenciais (Exp2) adaptado para espaços de características de dimensão infinita. O desafio central é que os estimadores ponderados por importância padrão em bandits lineares tornam-se ilimitados quando o mapa de características reside em um RKHS de dimensão infinita devido aos autovalores que tendem a zero do operador de covariância.

Para superar isso, os autores introduzem duas modificações-chave:

1. Estimador Ponderado por Importance Regularizado:
   Em vez de inverter o operador de covariância empírico $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$, o algoritmo utiliza uma versão regularizada por ridge $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$. O estimador é definido como:
   $$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$$
   Essa regularização garante que o estimador permaneça limitado mesmo quando $\Sigma_t$ possui autovalores próximos de zero. No entanto, isso introduz um viés sistemático: $\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$.

2. Termo de Correção de Viés Explícito:
   Para compensar o viés da regularização, o algoritmo constrói um proxy de perda corrigido $\hat{\ell}_t(x)$:
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   onde o termo de correção é $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$.

   • Mecanismo: O termo de correção é derivado diretamente da expressão de viés em forma fechada. Ele atua como um limite superior pontual sobre o viés, garantindo que o proxy de perda esperado subestime a perda verdadeira para o comparador (a melhor ação fixa). Essa escolha estrutural garante que o resíduo do lado do comparador na decomposição do arrependimento seja não positivo, deixando apenas um resíduo do lado do agente controlável.

3. Estratégia de Exploração:
   O algoritmo mantém uma distribuição $p_t$ que é uma mistura da distribuição atual de pesos exponenciais $q_t$ e uma distribuição de exploração fixa $\nu_G$. A distribuição de exploração é escolhida por meio de um projeto G-ótimo regularizado para garantir que a dimensão efetiva seja controlada.

3. Contribuições Principais

• Design do Algoritmo: Um algoritmo principiado que combina pesos exponenciais com um estimador regularizado e um termo de correção de viés explícito. Essa abordagem evita a suposição restritiva de adversário de posto único exigida por Chatterji et al. [2019].
• Análise de Arrependimento via Dimensão Efetiva: Os autores derivam um limite de arrependimento dependente da dimensão efetiva $d^*(\lambda)$ do kernel, definida como:
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• Remoção da Suposição de Posto Único: O framework permite perdas arbitrárias limitadas em RKHS, ampliando significativamente a aplicabilidade em comparação com trabalhos anteriores que dependiam de estimadores baseados em projeção que exigiam restrições de posto único.

4. Resultados Principais

O artigo estabelece um limite de arrependimento da forma:
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
onde $d^*(\lambda)$ captura a complexidade do kernel. Essa taxa coincide com as taxas ótimas conhecidas para o problema de bandits de kernel estocásticos (até fatores logarítmicos).

Taxas Específicas de Kernel:

• Kernel Matérn$(\nu, d)$: Para um kernel Matérn com suavidade $\nu$ em $\mathbb{R}^d$, a dimensão efetiva produz um limite de arrependimento de:
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  Isso melhora a taxa anterior de melhor conhecimento de $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$ de Chatterji et al. [2019] e coincide com o limite inferior de trabalho concorrente [Iwazaki, 2026] até fatores logarítmicos. Notavelmente, a taxa anterior nem era sublinear quando $\nu < d/2$, enquanto o novo limite é sempre sublinear.
• Kernel Exponencial Quadrático (SE): O limite recupera a taxa near-ótima $\tilde{O}(\sqrt{T})$, coincidindo com Chatterji et al. [2019] mas sem a restrição de posto único.
• Decaimento Geral de Autovalores:
  • Decaimento Polinomial ($\mu_j \le C j^{-\beta}$): Alcança $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$.
  • Decaimento Exponencial ($\mu_j \le C e^{-\beta j}$): Alcança $R_T = \tilde{O}(\sqrt{T})$.

5. Significado e Alegações

O artigo alega fechar a lacuna entre o desempenho de bandits de kernel adversariais e estocásticos. Especificamente:

• Optimalidade: As taxas derivadas coincidem com as taxas ótimas conhecidas para bandits de kernel estocásticos (por exemplo, via SupKernelUCB ou métodos de otimização bayesiana) até fatores logarítmicos.
• Avanço Teórico: Ao remover a suposição de adversário de posto único, os resultados aplicam-se a uma classe mais geral e realista de ambientes adversariais onde a função de perda é um elemento limitado arbitrário do RKHS.
• Comparação com Trabalhos Anteriores: O trabalho melhora Chatterji et al. [2019] para kernels Matérn e decaimento polinomial geral, fornecendo limites mais apertados que são sublineares em $T$ sob condições onde os limites anteriores não o eram.
• Trabalho Concorrente: Os autores reconhecem trabalho independente e concorrente de Iwazaki [2026] que alcança resultados semelhantes usando uma abordagem intimamente relacionada (pesos exponenciais com estimadores regularizados e correção de viés). O artigo nota diferenças menores na configuração do problema (por exemplo, adversário cego vs. adaptativo, medidas de complexidade específicas), mas afirma que as contribuições algorítmicas e analíticas centrais são essencialmente equivalentes.

O artigo conclui que o método proposto fornece uma solução near-ótima para o problema de bandits de kernel adversariais, lidando efetivamente com os desafios de espaços de características de dimensão infinita através de regularização e correção explícita de viés.