When and why randomised exploration works (in linear bandits)

Resumo Técnico: Quando e por que a exploração randomizada funciona (em bandits lineares)

Configuração do Problema
O artigo aborda o problema de bandit linear, um cenário de tomada de decisão sequencial onde um agente seleciona ações $X_t$ de um subconjunto fechado $\mathcal{X}$ da bola euclidiana unitária em $\mathbb{R}^d$. O agente recebe uma recompensa $Y_t$ com média $\langle X_t, \theta^\star \rangle$, onde $\theta^\star$ é um vetor de parâmetros desconhecido. O objetivo é minimizar o regret de $n$ passos, definido como a diferença cumulativa entre a recompensa da ação ótima e as ações tomadas.

Embora algoritmos otimistas (ex: Upper Confidence Bound) tenham estabelecido limites de regret frequentistas de $O(d\sqrt{n} \log n)$ para bandits lineares, algoritmos de exploração randomizada como Thompson Sampling têm sido historicamente mais difíceis de analisar neste cenário. Análises frequentistas anteriores de métodos randomizados frequentemente dependiam de "otimismo forçado" ou "inflação de posterior" — modificando o algoritmo para inflar artificialmente a variância da distribuição posterior para garantir o otimismo com alta probabilidade. Essas modificações tipicamente resultavam em limites de regret subótimos, como $O((d \log n)^{3/2}\sqrt{n})$, introduzindo um fator $\sqrt{d}$ extra em comparação com algoritmos otimistas. Além disso, limites inferiores recentes (Hamidi e Bayati, 2023; Zhang, 2022) demonstraram que o Thompson Sampling não modificado pode incorrer em regret linear em configurações patológicas específicas, sugerindo que a exploração randomizada não é universalmente ótima sem suposições estruturais.

Metodologia e Suposições
Os autores propõem um novo framework de análise que evita modificar o algoritmo randomizado (ou seja, sem otimismo forçado ou inflação de posterior). Em vez disso, a análise baseia-se em propriedades geométricas específicas do conjunto de ações $\mathcal{X}$.

1. Framework Algorítmico: O artigo considera uma classe de algoritmos randomizados onde, em cada passo $t$, um parâmetro $\theta_t$ é amostrado como $\theta_t = \hat{\theta}_{t-1} + V_{t-1}^{-1/2}\eta_t$, onde $\hat{\theta}_{t-1}$ é a estimativa de mínimos quadrados regularizada, $V_{t-1}$ é a matriz de design, e $\eta_t$ é uma perturbação rotacionalmente invariante. A ação é selecionada como $X_t = \arg\max_{x \in \mathcal{X}} \langle x, \theta_t \rangle$.
2. Suposições de Perturbação: As perturbações $\eta_t$ são assumidas como variáveis aleatórias independentes e rotacionalmente invariantes com momentos de segunda e quarta ordem limitados (ex: Gaussiana ou uniforme em uma esfera).
3. Suposições do Conjunto de Ações (Suavidade e Convexidade Forte): A principal contribuição teórica reside na Suposição 4.2, que exige que o conjunto de ações $\mathcal{X}$ seja um subconjunto fechado e absorvente da bola unitária tal que o quadrado de sua função de suporte, $J_{\mathcal{X}}^2$, seja tanto $m$-fortemente convexo quanto $M$-suave em relação a uma norma específica $\|\cdot\|_*$.
   • Convexidade Forte: Garante que a função de suporte não possua regiões "planas", garantindo que pequenas mudanças no espaço de parâmetros se traduzam em mudanças significativas no espaço de ações.
   • Suavidade: Garante que o gradiente da função de suporte (que mapeia parâmetros para ações) seja Lipschitz, evitando grandes saltos no regret devido a pequenas perturbações nos parâmetros.
   • Exemplos: Esta classe inclui bolas $\ell_q$ reescalonadas para $q \in (1, \infty)$.

Principais Contribuições e Análise
O artigo fornece uma análise de regret frequentista que não depende do framework de "otimismo diante da incerteza". Em vez disso, analisa diretamente a dinâmica do processo de exploração e a evolução dos conjuntos de confiança.

• Decomposição de Regret: Os autores decompõem o regret esperado em dois componentes: passos onde o algoritmo é "otimista" (o parâmetro amostrado produz um valor superior ao ótimo real) e passos onde ele não é.
• Exploração Não-Otimista: Um insight crítico é que mesmo quando uma amostra não é otimista, ela ainda fornece informação valiosa que reduz o conjunto de confiança. Os autores utilizam uma formulação de divergência de Bregman para o regret por passo, $r_t = D_{J_{\mathcal{X}}}(\theta^\star, \theta_t)$, e utilizam a convexidade forte e a suavidade de $J_{\mathcal{X}}^2$ para limitar essa divergência.
• Crescimento de Informação: A prova estabelece um limite inferior para o crescimento da matriz de design $V_t ao relacionar o ganho de informação esperado$\mathbb{E}_{t-1}[X_t X_t^\top]$ com a geometria dos elipsoides de confiança. Isso conecta o "tamanho" do espaço de parâmetros (medido por $V_t^{-1/2}$) à exploração real realizada.
• Evitando a Inflação: Ao contrário de trabalhos anteriores, esta análise não requer a inflação da variância da distribuição de amostragem. Ela demonstra que a aleatoriedade natural do algoritmo, combinada com as propriedades geométricas de $\mathcal{X}$, é suficiente para impulsionar a exploração e controlar o regret.

Principais Resultados
Sob as suposições declaradas, os autores provam que qualquer algoritmo randomizado que satisfaça as condições de perturbação alcança um limite de regret frequentista de:
$$R_n \lesssim O(d\sqrt{n} \log n)$$
Especificamente, o Teorema 4.1 fornece um limite da ordem $O(d\sqrt{n} \log n)$ (ignorando fatores logarítmicos em $n$ e $\delta$). Isso coincide com o limite inferior conhecido para bandits lineares (Rusmevichientong e Tsitsiklis, 2010) até os fatores logarítmicos.

Significância e Alegações
O artigo afirma resolver uma questão aberta importante sobre a dependência da dimensão do Thompson Sampling em bandits lineares.

• Dependência de Dimensão Ótima: Demonstra pela primeira vez que o Thompson Sampling não modificado (não inflado) pode alcançar a dependência de dimensão ótima ($O(d)$) em configurações de bandit linear estruturadas, especificamente quando o espaço de ações é suave e fortemente convexo.
• Mecanismo de Sucesso: O trabalho elucida por que a exploração randomizada funciona nesses cenários: as propriedades geométricas do conjunto de ações garantem que as perturbações no espaço de parâmetros explorem efetivamente o espaço de ações sem exigir otimismo artificial.
• Limitações e Escopo: Os autores reconhecem que seus resultados não contradizem os limites inferiores existentes que mostram regret linear para Thompson Sampling em espaços de ação não suaves ou não absorventes (ex: aqueles com braços "armadilha"). O sucesso do método depende de o conjunto de ações satisfazer as suposições de suavidade e convexidade forte. O artigo não afirma que essas condições são necessárias, mas sim que são suficientes para alcançar taxas ótimas sem modificações algorítmicas.

Em resumo, o artigo estabelece que, para uma ampla classe de conjuntos de ações bem comportados (incluindo bolas $\ell_q$), algoritmos de exploração randomizada alcançam naturalmente taxas de regret ótimas, removendo a necessidade das técnicas de inflação de variância ad-hoc anteriormente consideradas necessárias para garantias teóricas.