Resumo Técnico: Thompson Sampling com Correção de Fluxo para Bandidos Contextuais Não Estacionários

Formulação do Problema

O artigo aborda o desafio dos bandidos contextuais lineares não estacionários, um cenário onde a relação entre contextos, ações e recompensas evolui ao longo do tempo. Nos bandidos contextuais clássicos, assume-se que o vetor de parâmetros $w_t$ é estacionário. No entanto, em aplicações do mundo real (ex: sistemas de recomendação, precificação dinâmica, finanças), as preferências dos usuários e as condições de mercado sofrem deriva (drift), tornando os dados históricos sistematicamente enviesados se forem usados de forma ingênua.

A dificuldade central reside no equilíbrio entre reter dados históricos para reduzir a variância da posterior e descartar dados antigos para evitar o viés de modelos desatualizados. As abordagens existentes — como janelas deslizantes, desconto exponencial e reinicializações periódicas — tratam os dados históricos primariamente como um passivo a ser gerenciado por meio do descarte uniforme ou da redução de peso. Os autores argumentam que, quando a não estacionaridade apresenta uma estrutura previsível (ex: deriva gradual, periodicidade ou regimes recorrentes), as observações históricas contêm informações valiosas que podem ser aproveitadas se forem corrigidas para as mudanças ambientais intervenientes.

Metodologia: Thompson Sampling com Correção de Fluxo (FC-TS)

Os autores propõem o Thompson Sampling com Correção de Fluxo (FC-TS), um framework Bayesiano que transforma observações históricas em "pseudo-observações de tempo presente" antes de incorporá-las à posterior. O método desacopla o tratamento da não estacionaridade em dois componentes distintos: um operador de transporte e uma regra de ponderação de confiança.

1. Mecanismo Central

Em cada rodada $t$, para cada observação passada $(x_s, a_s, r_s)$, o FC-TS constrói uma recompensa transportada $\hat{r}_{s \to t}$:
$$\hat{r}_{s \to t} = r_s + \hat{\Delta}_{s \to t}(x_s, a_s)$$
onde $\hat{\Delta}_{s \to t}$ estima o deslocamento na recompensa média do tempo $s$ para $t$. Isso efetivamente faz a recompensa do passado "fluir" para o futuro para alinhá-la com o modelo de recompensa atual.

Para evitar que o ruído de estimativas de deriva imprecisas prejudique o modelo, cada observação transportada recebe um peso de confiança $\omega_{s,t} \in [0, 1]$. Este peso controla a influência da observação na posterior, inflando sua variância de ruído efetiva caso a correção seja incerta.

A posterior para uma ação $a$ é atualizada usando essas observações transportadas e ponderadas:
$$\Lambda_t^{(a)} = \lambda I + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} x_s x_s^\top$$
$$\eta_t^{(a)} = \lambda m_t^{(a)} + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} \hat{r}_{s \to t} x_s$$
$$\mu_t^{(a)} = (\Lambda_t^{(a)})^{-1} \eta_t^{(a)}$$
A seleção de ações procede via Thompson Sampling padrão utilizando a posterior Gaussiana $\mathcal{N}(\mu_t^{(a)}, (\Lambda_t^{(a)})^{-1})$.

2. Instanciações Estruturadas

O framework fornece um template unificado com instanciações específicas para três padrões de não estacionaridade comuns:

• Deriva Linear (Linear Drift): Assume que os parâmetros evoluem como $w_t^{(a)} \approx \theta^{(a)} + t \delta^{(a)}$. O operador de transporte utiliza uma estimativa de regressão ridge online $\hat{\delta}_t^{(a)}$ para deslocar as recompensas: $\hat{r}_{s \to t} = r_s + (t-s)\langle \hat{\delta}_t^{(a)}, x_s \rangle$. Os pesos decaem exponencialmente ($\omega_{s,t} = \gamma^{t-s}$) para contabilizar a incerteza de extrapolação.
• Variação Periódica (Periodic Variation): Assume que os parâmetros se repetem com período $P$. O operador de transporte é a identidade ($\hat{r}_{s \to t} = r_s$) para observações na mesma fase. Os pesos são determinados pela distância circular entre as fases, permitindo que o algoritmo reutilize dados de ciclos anteriores ($\omega_{s,t}$ depende da proximidade de fase).
• Regimes Recorrentes (Recurring Regimes): Lida com ambientes que alternam entre um conjunto finito de regimes. O algoritmo mantém um banco de posteriors específicos de cada regime. Ao detectar um ponto de mudança (via CUSUM nos resíduos de predição), ele recarrega a posterior do regime reincidente em vez de reiniciar do zero.

O framework também suporta composição, permitindo o tratamento simultâneo de deriva linear e periodicidade ao combinar as respectivas regras de transporte e ponderação.

Principais Contribuições

1. Atualizações de Posterior com Correção de Fluxo: O artigo introduz uma visão baseada em transporte para a não estacionaridade, onde as recompensas passadas são corrigidas em pseudo-observações de tempo presente e incorporadas via atualizações Bayesianas ponderadas por confiança, em vez de serem descartadas uniformemente.
2. Design de Algoritmo Modular: O FC-TS é definido por um operador de transporte e uma regra de ponderação genéricos, instanciados para deriva linear, variação periódica e regimes recorrentes. Isso inclui uma variante adaptativa que combina tendências e múltiplas periodicidades.
3. Validação Empírica: Uma avaliação extensiva através de cinco estudos de caso (deriva linear, variação periódica, regimes recorrentes, não estacionaridade composta e seleção de portfólio semi-sintética) demonstra que o FC-TS supera as linhas de base de esquecimento de última geração.

Resultados Experimentais

Os autores avaliaram o FC-TS contra quatro baselines: Standard TS (STD-TS), Sliding Window TS (SW-TS), Discounted TS (D-TS) e Restarting TS (R-TS).

• Ganhos de Desempenho: O FC-TS alcançou o menor regret cumulativo em todos os cinco cenários, com melhorias variando de 14,1% a 59,0% sobre a linha de base mais forte em cada ambiente específico.

• Insights Específicos por Caso:

  • Deriva Linear: O FC-TS igualou-se ao SW-TS durante a fase de aquecimento (warm-up), mas separou-se progressivamente conforme as estimativas de deriva estabilizaram, vencendo 8 de 10 sementes.
  • Variação Periódica: O FC-TS mostrou o maior ganho sintético (50,0%) devido à "memória de fase", acumulando dados de ciclos anteriores. O regret por ciclo caiu de ~70 para ~4, enquanto as linhas de base estagnaram.
  • Regimes Recorrentes: O FC-TS alcançou uma melhoria de 59,0% ao recarregar as posteriors específicas de regime após a detecção de uma troca, evitando a penalidade de "cold start" das reinicializações.
  • Não Estacionaridade Composta: Em ambientes com tanto deriva quanto mudanças abruptas, o FC-TS combinou com sucesso a correção de deriva (para evolução suave) e resets de regime (para mudanças abruptas), gerando uma melhoria de 29,5%.
  • Portfólio Semi-Sintético: Em uma tarefa financeira com ciclos mensais/trimestrais sobrepostos e deriva de crescimento-para-valor, a variante adaptativa do FC-TS melhorou o regret em 28,1% em relação à melhor linha de base (D-TS). Estudos de ablação confirmaram que a correção de deriva foi o componente dominante desse ganho.

• Descobertas de Ablação:

  • Tamanho de Amostra Efetivo: Reter mais dados sem a correção de transporte (a ablação "no-transport") resultou em um regret maior do que os métodos que descartam dados, confirmando que dados obsoletos introduzem viés sistemático.
  • Valor do Transporte: O próprio operador de transporte foi responsável por uma redução de 47–57% no regret em comparação com a variante sem transporte em várias escalas de deriva, provando que o mecanismo de correção, e não apenas a reconstrução da posterior, impulsiona o desempenho.

Significância e Alegações

O artigo afirma que a não estacionaridade estruturada é melhor endereçada corrigindo e reutilizando a experiência do que descartando-a uniformemente.

Os autores enfatizam que, quando a deriva do ambiente é previsível (gradual, periódica ou recorrente), os dados históricos são um ativo em vez de um passivo. Ao modelar explicitamente o "fluxo" da distribuição de recompensa ao longo do tempo, o FC-TS mantém um tamanho de amostra efetiva muito maior do que os métodos baseados em esquecimento. Os resultados sugerem que a chave para a eficiência de amostragem em bandidos não estacionários reside em reponderar e corrigir as observações históricas com base na estrutura temporal específica do ambiente, em vez de aplicar uma regra de esquecimento única e uniforme.

O artigo conclui modestamente, observando que trabalhos futuros incluem o aprendizado de estruturas de deriva online com incerteza calibrada, a extensão do framework para bandidos neurais ou de modelos lineares generalizados e o desenvolvimento de salvaguardas para cenários de alto risco com mudanças de distribuição não modeladas.