Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

Formulação do Problema
Este artigo investiga bandits logísticos estocásticos sob o objetivo de arrependimento simples. Neste cenário, um agente interage com um ambiente ao longo de $T$ rodadas, selecionando ações $A_t$ de um conjunto $\mathcal{A}$ e observando recompensas Bernoulli $X_t$ com média $\mu(\phi(A_t)^\top \theta^*)$, onde $\mu$ é a função sigmoide, $\phi$ é um mapa de características conhecido e $\theta^*$ é um parâmetro desconhecido em $\mathbb{R}^d$. Diferentemente do arrependimento cumulativo, onde o objetivo é maximizar a soma das recompensas durante a exploração, o objetivo de arrependimento simples avalia o agente exclusivamente pela qualidade de uma única recomendação final $\hat{a}$ após $T$ rodadas. O arrependimento é definido como a diferença entre a recompensa esperada da ação ótima e a recompensa esperada da ação recomendada.

Um desafio crítico nos bandits logísticos é a informatividade não uniforme das ações. Devido ao vínculo sigmoide, ações em regiões "saturadas" (onde a recompensa média está próxima de 0 ou 1) geram recompensas quase determinísticas, mas fornecem pouca informação sobre o parâmetro $\theta^*$. Por outro lado, ações próximas à origem (onde a sigmoide é mais íngreme) são altamente informativas, mas podem gerar recompensas imediatas mais baixas. Isso cria uma geometria onde as ações melhores para a recompensa imediata (exploração) diferem daquelas melhores para identificar a ação ótima (exploração).

Metodologia
Os autores propõem dois algoritmos conscientes da curvatura, projetados para explorar a geometria local da função sigmoide:

1. MULOG (Max-Uncertainty-Log): Um algoritmo determinístico de exploração pura.

   • Mecanismo: O MULOG mantém um conjunto de confiança $W_t$ para $\theta^*$ e constrói uma matriz de projeto ponderada pela curvatura $L_t$. A pontuação de incerteza para uma ação $a$ e parâmetro $\theta$ é definida como $U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$, onde $\dot{\mu}$ é a derivada da sigmoide (representando a curvatura local).
   • Seleção: Em cada rodada, o algoritmo seleciona o par ação-parâmetro $(A_t, \theta_t)$ que maximiza essa pontuação de incerteza.
   • Terminação: Após $T$ rodadas, retorna a ação gananciosa em relação a um vetor de parâmetros amostrado do conjunto de confiança final.
   • Otimização: Para conjuntos de ações finitos, a etapa de seleção reduz-se a resolver uma coleção finita de problemas de otimização convexa.

2. THATS (Try Hard Thompson Sampling): Uma alternativa randomizada e computacionalmente mais leve.

   • Mecanismo: Em vez de resolver para a incerteza máxima exata, o THATS amostra uma direção $\tilde{\theta}_t$ de uma distribuição Gaussiana centrada em zero com covariância $L_t^{-1}$.
   • Seleção: Seleciona a ação que maximiza a pontuação de incerteza randomizada $\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$, onde $\bar{\theta}_t$ é uma estimativa de máxima verossimilhança restrita.
   • Compromisso: Esta abordagem evita a otimização convexa exigida pelo MULOG, mas incorre em um custo estatístico, resultando em um limite de arrependimento ligeiramente mais frouxo.

Contribuições Principais

• Limite Inferior Minimax: O artigo estabelece um limite inferior minimax de primeira ordem da ordem $\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, onde $\kappa^*$ é a inclinação inversa da sigmoide na ação ótima (ou seja, $\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$).
  • Mecanismo de Dificuldade Distinto: Diferentemente dos limites inferiores de arrependimento cumulativo (por exemplo, Abeille et al., 2021), que dependem do custo da informação (forçando o agente a jogar braços quase ótimos), este limite inferior é derivado de uma construção de "hipercubo saturado deslocado". Nesta construção, tanto a informação estatística quanto a sensibilidade de valor são controladas pela mesma curvatura local em uma região saturada. Isso revela que, mesmo com a liberdade de amostrar puramente para informação, o problema permanece difícil se a ação ótima estiver em uma região plana da sigmoide.
• Algoritmos Ótimos:
  • O MULOG alcança um limite superior de arrependimento simples de $\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, correspondendo ao limite inferior até fatores logarítmicos. Esta é a primeira garantia direta de exploração pura para bandits logísticos que alcança optimalidade minimax instância a instância.
  • O THATS alcança um limite de $\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$. O fator extra $\sqrt{d}$ surge do uso de uma aproximação randomizada agnóstica à geometria para a direção de máxima incerteza.
• Insight Geométrico: Os autores demonstram que a geometria do pior caso (instâncias saturadas deslocadas) não é o único caso. Eles mostram que "ações de baixa recompensa informativas" (sondas) podem existir no conjunto de ações. Essas ações residem na região de alta curvatura da sigmoide, fornecendo informação significativa sobre a direção ótima, apesar de terem recompensas esperadas baixas.

Resultados

• Teóricos: Os limites derivados confirmam que a dificuldade do arrependimento simples logístico é governada pela curvatura na ação ótima. Os algoritmos controlam com sucesso a incerteza nas direções de características ponderadas pela curvatura.
• Empíricos: Experimentos em geometrias "difíceis" (hipercubos saturados deslocados) e geometrias "fáceis" (com braços sondadores informativos adicionados) corroboram as descobertas teóricas:
  • Em instâncias difíceis, o MULOG e o THATS performam conforme previsto pelos limites minimax.
  • Em instâncias fáceis com braços sondadores, métodos de exploração pura (MULOG e THATS) superam significativamente as linhas de base de arrependimento cumulativo (como Amostragem de Thompson Cumulativa e conversões online-para-lote). Os métodos de exploração pura amostram ativamente as sondas de baixa recompensa e alta informação, reduzindo drasticamente as rodadas necessárias para atingir um limiar baixo de arrependimento simples.
  • Métodos de arrependimento cumulativo falham em explorar essas sondas efetivamente porque sua conversão online-para-lote penaliza a inclusão de ações de baixa recompensa na distribuição de recomendação final.

Significado
O artigo afirma que a exploração pura em bandits logísticos possui uma geometria distinta dos problemas de arrependimento cumulativo. A contribuição principal é identificar que a curvatura local na ação ótima ($\kappa^*$) é o fator governante para a taxa minimax de primeira ordem. Ao desenvolver algoritmos que levam explicitamente em conta essa curvatura, os autores alcançam desempenho minimax-ótimo no pior caso. Além disso, o trabalho destaca uma implicação prática: em cenários como testes A/B ou coleta de dados de modelos de recompensa, buscar ativamente ações "informativas mas de baixa recompensa" pode acelerar substancialmente a identificação da melhor política final, um comportamento que algoritmos padrão de arrependimento cumulativo são estruturalmente incapazes de exibir. Os resultados servem como ponto de partida para uma teoria mais precisa de exploração focada em decisão em bandits não lineares.