A Broader View of Thompson Sampling

Resumo Técnico: Uma Visão Mais Ampla do Amostragem de Thompson

Enunciado do Problema
A Amostragem de Thompson (TS) é uma heurística amplamente utilizada para o problema do Bandido Multi-Braço (MAB), conhecida por seu sucesso empírico e limites teóricos de arrependimento. No entanto, ao contrário das políticas de Limite Superior de Confiança (UCB) ou do índice de Gittins, o princípio de otimização explícito que governa o equilíbrio da TS entre exploração e exploração permanece opaco. Embora Gittins (1979) tenha formulado o MAB Bayesiano como um Processo de Decisão de Markov (MDP) para derivar uma política ótima, essa abordagem depende de recompensas descontadas em horizonte infinito. Essa formulação leva a "aprendizado incompleto" (falha em identificar o braço ótimo infinitas vezes), o que contradiz o objetivo central da literatura de MAB de minimização de arrependimento em horizonte finito (Robbins 1952; Lai e Robbins 1985). O artigo aborda a lacuna na compreensão da TS buscando uma formulação estacionária "fiel" que se alinhe à minimização de arrependimento em horizonte finito, mantendo a tratabilidade da programação dinâmica.

Metodologia
Os autores propõem uma estrutura de estacionarização fiel para reformular o problema não estacionário de minimização de arrependimento em horizonte finito em um problema de otimização online estacionário.

1. Objetivo de Arrependimento Quadrado: Em vez de minimizar diretamente o arrependimento cumulativo $R_T$ ou usar recompensas descontadas, os autores introduzem a minimização do arrependimento quadrado cumulativo $R_2$. Eles estabelecem um limite $R_T \leq \sqrt{R_2 \cdot T}$. Minimizar a soma em horizonte infinito dos arrependimentos quadrados $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ garante que a política atinja a taxa de arrependimento ótima $O(\sqrt{T})$, ao mesmo tempo que fornece um objetivo estacionário.
2. Equação de Bellman Estacionária: Este novo objetivo produz uma equação de Bellman estacionária para a função valor $V(\pi_t)$ (o arrependimento quadrado futuro mínimo):
   $$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$$
   Diferentemente do índice de Gittins (que maximiza a recompensa descontada linear), essa minimização é quadrática nas probabilidades de ação, levando a uma política ótima randomizada em vez de determinística.
3. Forma de Otimização Online: Através de uma mudança de variáveis focada na recompensa esperada da próxima rodada $x_t$, os autores derivam que a política ótima em $R_2$ ($Q_{R2}$) assume a forma de um problema de otimização online:
   $$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$$
   Aqui, o primeiro termo representa a exploração instantânea (ganância), e o segundo termo é uma regularização linear representando a exploração. O regularizador $\nu_{R2}(\pi_t)$ é derivado da equação de Bellman e mede a tensão entre exploração e exploração (a diferença no valor futuro entre puxar os braços).
4. Reinterpretando a Amostragem de Thompson: Os autores demonstram que a Amostragem de Thompson admite exatamente a mesma forma de otimização online:
   $$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$$
   No entanto, seu regularizador $\nu_{TS}(\pi_t)$ é a covariância biserial entre a lacuna de recompensa ($\theta_1 - \theta_2$) e a identidade do braço ótimo ($\text{sign}(\theta_1 - \theta_2)$). Este regularizador mede a incerteza sobre qual braço é melhor, em vez da tensão entre recompensa imediata e valor futuro.

Principais Contribuições

• Estacionarização Fiel: O artigo introduz uma formulação estacionária (minimização de arrependimento quadrado) que preserva a essência da minimização de arrependimento em horizonte finito, preenchendo a lacuna entre amostragem heurística e programação dinâmica principista.
• Unificação Estrutural: Revela que tanto a Amostragem de Thompson quanto a política ótima de Bellman ($Q_{R2}$) são instâncias de algoritmos de otimização online que trocam ganância por um regularizador.
• Identificação de Mecanismo: O artigo identifica o mecanismo específico que impulsiona a TS: ela regulariza a ganância com base na incerteza (covariância biserial), enquanto a política ótima regulariza com base na tensão (diferença de valor futuro).
• Melhoria de Política: Aproveitando a estrutura de Bellman, os autores propõem um passo padrão de melhoria de política para a TS. Ao avaliar a função valor da TS e inseri-la de volta na equação de Bellman, eles derivam uma política aprimorada ($Q_{TS'}$) que usa um regularizador baseado em tensão.

Resultados

• Lacuna de Desempenho: Experimentos numéricos em bandidos Gaussianos e Bernoulli mostram que a política ótima em $R_2$ ($Q_{R2}$) atinge um arrependimento cumulativo significativamente menor do que a Amostragem de Thompson. A lacuna é atribuída ao fato de o regularizador da TS ser uma medida de incerteza que falha em capturar a "tensão" quando o braço líder é incerto, mas o braço subótimo é superexplorado.
• Amostragem Orientada à Informação (IDS): O artigo descobre que a IDS, outra heurística, compartilha a mesma estrutura de regularizador baseada em tensão que a $Q_{R2}$ e desempenha-se quase idêntica à política ótima de Bellman, unindo perspectivas de teoria da informação e programação dinâmica.
• Melhoria de Um Passo: Um único passo de melhoria de política aplicado à Amostragem de Thompson fecha aproximadamente 90% da lacuna de desempenho entre a TS e a referência ótima de Bellman. Essa melhoria transforma efetivamente o regularizador da TS de uma medida de incerteza para uma medida de tensão.
• Propriedade Estrutural no Caso K-Braço: No cenário de $K$ braços, a política ótima de Bellman (e a TS aprimorada) atribui probabilidade positiva a no máximo dois braços em qualquer rodada, enquanto a TS padrão pode atribuir probabilidade positiva a todos os braços. O passo de melhoria de política concede a essa TS essa esparsidade estrutural.

Significado
O artigo afirma fornecer uma "visão mais ampla" da Amostragem de Thompson ao reformulá-la como um algoritmo de otimização online. Esta lente:

1. Explica a Heurística: Esclarece que a TS equilibra exploração e exploração ao regularizar a ganância com uma medida de incerteza residual.
2. Identifica Limitações: Aponta que a dependência da TS da incerteza em vez da tensão leva a comportamentos subótimos em regimes específicos (por exemplo, quando o braço ótimo é incerto, mas o braço subótimo é claramente superexplorado).
3. Permite Melhoria Principista: Oferece um framework rigoroso para melhorar algoritmos de amostragem posterior. Ao alinhar o regularizador com a medida de tensão ótima de Bellman, os autores demonstram que a TS pode ser significativamente aprimorada com sobrecarga computacional mínima (um único passo de iteração de política), aproximando-a do ótimo teórico sem abandonar sua natureza baseada em amostragem.