Resumo Técnico: Bandido Logístico Multinomial Eficiente via Direções Frequentes

Declaração do Problema

O artigo aborda o desafio dos Bandidos Logísticos Multinomiais (MLogB), um framework de tomada de decisão sequencial onde um agente seleciona uma ação $x_t \in \mathbb{R}^d$ e observa um feedback categórico $y_t \in \{0, \dots, K\}$. A distribuição de probabilidade dos resultados segue um modelo logístico multinomial parametrizado por uma matriz desconhecida $W^* \in \mathbb{R}^{K \times d}$. O objetivo é minimizar o regret cumulativo, definido como a diferença entre a recompensa esperada da ação ótima e a ação escolhida pelo agente.

Embora os algoritmos de estado da arte existentes, como o OFUL-MLogB [Zhang e Sugiyama, 2023], alcancem limites de regret quase ótimos de $\tilde{O}(Kd\sqrt{T})$, eles sofrem com custos computacionais proibitivos em cenários de alta dimensão. Especificamente, o OFUL-MLogB depende da manutenção e manipulação de uma matriz Hessiana completa de $Kd \times Kd$ para a estimativa de parâmetros (via Online Newton Step) e construção de recompensa otimista. Isso resulta em:

• Complexidade de Tempo: $O(|A_t|K^3d^2 + K^3d^3)$ por rodada.
• Complexidade de Espaço: $O(K^2d^2)$ por rodada.

Esses custos tornam o algoritmo impraticável para espaços de ação de alta dimensão ($d$) ou grandes conjuntos de resultados ($K$).

Metodologia: EOFD-MLogB

Os autores propõem o EOFD-MLogB (Eficiência via Otimismo através de Direções Frequentes), um algoritmo que integra o esboço (sketching) de matriz por Direções Frequentes (FD) ao framework do OFUL-MLogB para reduzir a complexidade computacional enquanto preserva garantias teóricas.

1. Manutenção Espectral via FD Adaptado

Em vez de armazenar a Hessiana completa $H_t$, o EOFD-MLogB mantém uma decomposição espectral de baixo rank de uma Hessiana esboçada $Z_t$:
$$Z_t = \lambda I_{Kd} + V_t \Lambda_t V_t^\top$$
onde $V_t \in \mathbb{R}^{Kd \times m}$ possui colunas ortonormais, $\Lambda_t \in \mathbb{R}^{m \times m}$ é diagonal, e $m \ll d$ é o tamanho do esboço.

• Atualização de Bloco FD: Como a atualização da Hessiana no MLogB é uma matriz de rank-$K$ ($\nabla^2 \ell_t = \nabla \sigma(W_t x_t) \otimes x_t x_t^\top$), o algoritmo realiza uma atualização de bloco FD. Ele fatoriza a atualização de rank-$K$ em $B_t B_t^\top$ e anexa $B_t$ ao esboço atual $[V_t \Lambda_t^{1/2}, B_t]$. Um SVD é computado, e as $m$ principais direções singulares são retidas, descartando o restante em um termo de erro de esboço cumulativo $\rho_{1:t}$.

2. Atualização de Parâmetro Eficiente

A atualização de parâmetros no OFUL-MLogB envolve um programa quadrático convexo-concavo (QCQP) restrito sobre um elipsoide definido pela Hessiana.

• Redução à Busca de Raiz: Ao utilizar a forma espectral da Hessiana substituta (surrogate) $\tilde{Z}_t$, o problema de projeção de alta dimensão é reduzido à busca de uma raiz $\nu$ de uma função escalar monotônica $f(\nu) = S^2$. Isso permite que a projeção seja computada eficientemente sem decomposição em autovalores completa, utilizando a identidade de Woodbury para inversão de matrizes.

3. Construção de Recompensa Otimista Eficiente

O bônus otimista em MLogB envolve o cálculo de normas espectrais de alta dimensão, especificamente $\|H_t^{-1/2}(I_K \otimes x)\|_2$.

• Redução de Dimensionalidade: Os autores provam (Lema 1) que, ao utilizar a matriz esboçada $Z_t$, este cálculo de norma espectral $Kd \times Kd$ reduz-se ao cálculo da norma espectral de uma matriz simétrica $A(x)$ de $K \times K$. Isso elimina a dependência de $d$ no cálculo da norma espectral, reduzindo o custo de $O(K^3d^2)$ para $O(K^3 + K^2m + Kdm)$.

Principais Contribuições

1. Eficiência Algorítmica: O EOFD-MLogB alcança uma complexidade de tempo dominante por rodada de $O(Kd(m+K)^2)$ e complexidade de espaço de $O(Kd(m+K))$. Isso representa uma melhoria significativa em relação à dependência cúbica de $d$ nos métodos anteriores, tornando o algoritmo escalável para cenários de alta dimensão.
2. Garantias Teóricas: O artigo estabelece um limite de regret de $\tilde{O}(\Delta_T (Kd \ln \Delta_T + m)\sqrt{T})$, onde $\Delta_T = 1 + \rho_{1:T}/\lambda$ é um fator de esboço dependente do erro de esboço cumulativo $\rho_{1:T}$.
   • O termo de erro $\rho_{1:T}$ é limitado pela cauda espectral truncada em $m$ da Hessiana cumulativa.
   • Quando a Hessiana acumulada é aproximadamente de baixo rank (ou seja, a cauda espectral decai rapidamente), $\Delta_T \approx 1$, e o limite de regret aproxima-se o do OFUL-MLogB original.
3. Aplicabilidade Geral: As técnicas de redução espectral (Lema 1 e Lema 2) mostram-se aplicáveis a outros algoritmos de MLogB de segunda ordem e bandidos lineares generalizados que dependem de atualizações baseadas em Hessiana, não apenas ao OFUL-MLogB.

Resultados Experimentais

Experimentos foram conduzidos no conjunto de dados MNIST (convertido para um problema de bandit contextual) e dados sintéticos com dimensões elevadas ($d=100, 400$).

• Desempenho: O EOFD-MLogB mantém um desempenho de regret competitivo, alcançando curvas comparáveis ao OFUL-MLogB em configurações tanto multinomiais quanto binárias.
• Eficiência: O método proposto demonstra acelerações substanciais. No MNIST, reduziu o tempo de computação por rodada em aproximadamente 80%, incorrendo em apenas um overhead de ~10% no regret. Em dados sintéticos, as reduções de tempo excederam 35% (multinomial) e 80% (binário).

Significância e Alegações

O artigo afirma que o EOFD-MLogB aborda com sucesso os custos de Hessiana completa "proibitivos" dos algoritmos de MLogB de segunda ordem existentes. Ao utilizar a técnica de esboço Direções Frequentes (Frequent Directions), os autores demonstram que é possível:

• Reter os benefícios teóricos dos métodos de segunda ordem (atualizações conscientes da curvatura e conjuntos de confiança estreitos).
• Reduzir drasticamente o overhead computacional em regimes de alta dimensão.
• Manter garantias de regret que são quase ótimas, desde que a estrutura da Hessiana subjacente seja aproximadamente de baixo rank.

O trabalho destaca que, embora as técnicas de esboço padrão (como as usadas em bandidos lineares) não se apliquem diretamente ao cenário não linear do MLogB devido à falta de reduções de forma fechada, as reduções espectrais adaptadas à estrutura específica do modelo logístico multinomial podem superar esses gargalos. Os autores observam que trabalhos futuros poderiam focar na seleção adaptativa do tamanho do esboço $m$ e no desenvolvimento de condições para controlar diretamente o fator de esboço $\Delta_T$.