Self-Concordant Perturbations for Linear Bandits

Resumo Técnico: Perturbações Autoconcordantes para Bandidos Lineares

Configuração do Problema
O artigo aborda o problema dos bandidos lineares adversariais, um cenário de otimização online onde um agente seleciona sequencialmente ações $a_t$ de um corpo convexo $K \subset \mathbb{R}^d$. Em cada rodada, o agente sofre uma perda $\langle y_t, a_t \rangle$ determinada por um vetor de perda desconhecido $y_t$, recebendo apenas este feedback escalar. O objetivo é minimizar o regret, definido como a diferença entre a perda cumulativa do agente e a perda cumulativa da melhor ação fixa em retrospectiva (in hindsight).

Existem duas famílias algorítmicas primárias para este cenário: Follow-the-Regularized-Leader (FTRL) e Follow-the-Perturbed-Leader (FTPL). Embora um framework unificado (GBPA) conecte ambos no cenário de informação completa, a distinção é crítica em bandidos: o FTRL requer mecanismos explícitos de exploração estocástica, enquanto o FTPL é inerentemente estocástico, selecionando ações a partir dos pontos extremos do conjunto de ações. Algoritmos existentes com taxas ótimas dependem frequentemente de pré-processamentos ou esquemas de exploração complexos e específicos do domínio (ex: elipsoides abrangentes) em vez de surgirem naturalmente do framework de barreira autoconcordante utilizado pelo algoritmo SCRIBLE. O SCRIBLE alcança um regret de $O(d^{3/2}\sqrt{n \ln n})$ em corpos convexos gerais e $O(d\sqrt{n \ln n})$ na bola $\ell_2$, mas sofre de uma variância de exploração subótima no hipercubo.

Metodologia: O Framework SC-FTPL
Os autores introduzem o BANDITS-GBPA, um framework unificador que estende o GBPA de informação completa para o cenário de bandidos. Este framework separa o algoritmo em uma função potencial $\Phi$, um esquema de amostragem $S$ e um esquema de estimativa $E$.

Dentro deste framework, o artigo propõe o algoritmo Self-Concordant Follow-the-Perturbed-Leader (SC-FTPL). A inovação central é a introdução de perturbações autoconcordantes.

• Definição: Uma distribuição de probabilidade $D$ em $\mathbb{R}^d$ é uma perturbação $\vartheta$-autoconcordante para um corpo convexo $K$ se existe uma barreira $R$ $\vartheta$-autoconcordante em $K$ tal que o gradiente da conjugada de Fenchel de $R$ é igual à esperança do gradiente da função de suporte de $K$ sob a perturbação:
  $$\nabla R^*(\theta) = \mathbb{E}_{\xi \sim D}[\nabla \phi_K(\theta + \xi)]$$
  Esta definição garante que a distribuição de perturbação $D$ "replica" as propriedades geométricas da barreira autoconcordante $R$ dentro de um contexto de FTPL.

• Algoritmo: O SC-FTPL mantém uma estimativa cumulativa de perdas $\hat{Y}_{t-1}$. Em cada etapa, ele amostra uma perturbação $\xi_t \sim D$ e seleciona a ação:
  $$a_t = \arg \min_{a \in K} \langle a, \eta \hat{Y}_{t-1} - \xi_t \rangle$$
  O vetor de perda é estimado usando o padrão estimador de segundo momento inverso $\hat{y}_t = Q_t^{-1} a_t \langle y_t, a_t \rangle$, onde $Q_t = \mathbb{E}_{t-1}[a_t a_t^\top]$.

Principais Contribuições

1. Framework Unificado (BANDITS-GBPA): Os autores formalizam um framework que abrange tanto as abordagens FTRL quanto FTPL para bandidos lineares, estendendo a análise do GBPA de feedback de informação completa para o de bandidos. Diferente do cenário de informação completa, o FTPL não é estritamente um subconjunto do FTRL aqui, mas o framework permite uma estrutura analítica comum.
2. Perturbações Autoconcordantes: O artigo identifica e analisa uma família de distribuições de perturbação que replicam as propriedades das barreiras autoconcordantes. Isso une a lacuna entre as propriedades de regularização do SCRIBLE e a exploração inerente do FTPL.
3. Construções Explícitas: Os autores constroem perturbações autoconcordantes específicas para dois conjuntos de ações canônicos:
   • Hipercubo $[-1, 1]^d$: Usando a barreira entrópica, derivam uma perturbação com marginais independentes.
   • Bola $\ell_2$ $B_d$: Usando a barreira logarítmica, constroem uma perturbação baseada em uma distribuição $t$ multivariada escalonada.

Resultados e Limites de Regret
O artigo fornece garantias de regret para o SC-FTPL no hipercubo e na bola $\ell_2$, assumindo taxas de aprendizado apropriadas e condições de horizonte ($n/\ln n$ suficientemente grande em relação à dimensão).

• Hipercubo: O SC-FTPL alcança um limite de regret de $O(d\sqrt{n \ln n})$.

  • Isso coincide com o limite inferior minimax estabelecido por Dani et al. (2007), exceto pelos fatores logarítmicos.
  • Representa uma melhoria de $\sqrt{d}$ em relação ao algoritmo SCRIBLE (que alcança $O(d^{3/2}\sqrt{n \ln n})$ no hipercubo).
  • A melhoria advém do fato de o esquema de amostragem do FTPL concentrar-se em pontos extremos, o que reduz a variância do estimador do vetor de perda na norma local em comparação com a amostragem de elipsoide de Dikin usada pelo SCRIBLE.
  • A complexidade computacional por rodada é $O(d)$.

• Bola $\ell_2$: O SC-FTPL alcança um regret de $O(d\sqrt{n \ln n})$.

  • Isso iguala o desempenho do SCRIBLE na bola $\ell_2$.
  • A análise para este caso é mais complexa porque a norma local do estimador não admite um limite quase-certo uniforme independente da estimativa de perda cumulativa. Os autores empregam um argumento inovador envolvendo uma supermartingal e argumentos de tempo de parada (usando a desigualdade de Ville) para controlar o crescimento do estimador cumulativo e lidar com a falta de limites uniformes.
  • A complexidade computacional por rodada também é $O(d)$.

Significância e Alegações
O artigo alega que o SC-FTPL fornece uma abordagem unificada e baseada em perturbação para bandidos lineares que recupera os benefícios da regularização autoconcordante sem exigir os mecanismos de exploração explícitos e frequentemente complexos dos métodos baseados em FTRL.

• Otimalidade no Hipercubo: A principal significância reside em alcançar a taxa ótima no hipercubo sem esquemas de amostragem específicos do domínio, melhorando o estado da arte (SCRIBLE) por um fator de $\sqrt{d}$.
• Ponte Teórica: O trabalho demonstra que o FTPL pode ser rigorosamente analisado usando a maquinaria de barreiras autoconcordantes, desde que as perturbações sejam escolhidas para replicar a geometria da barreira.
• Modéstia sobre Generalização: Os autores observam que, embora construam perturbações para o hipercubo e a bola $\ell_2$, a existência de perturbações autoconcordantes para corpos convexos gerais permanece uma questão aberta. Eles também reconhecem que o limite de regret na bola $\ell_2$ iguala o do SCRIBLE, mas não o supera, e que a análise exigiu instrumentação técnica adicional (tempos de parada) não necessária para o caso do hipercubo.

O artigo conclui identificando direções abertas, incluindo determinar se a taxa $O(d\sqrt{n \ln n})$ é apertada para o FTPL na bola $\ell_2$ para qualquer esquema de perturbação, e investigar se a barreira entrópica (uma barreira autoconcordante universal) admite uma distribuição de perturbação correspondente para corpos convexos gerais.