Resumo Técnico: Aprendizado On-Policy e Off-Policy para Grandes Espaços de Ação

Declaração do Problema

A tese aborda o desafio fundamental de aprender em sistemas interativos, especificamente bandidos contextuais, onde o espaço de ações $K$ é extremamente grande (variando de milhares a milhões). Em tais configurações, algoritmos padrão para aprendizado tanto on-policy (online) quanto off-policy (offline) enfrentam gargalos severos de escalabilidade:

• On-Policy: Estratégias de exploração padrão como Thompson Sampling (TS) ou Upper Confidence Bound (UCB) tipicamente dependem de modelos disjuntos onde cada ação possui um parâmetro independente. Em grandes espaços de ação, aprender cada parâmetro independentemente é estatisticamente ineficiente, levando a um alto regret cumulativo. Por outro lado, modelos conjuntos que compartilham parâmetros entre todas as ações são frequentemente computacionalmente intratáveis devido à complexidade $O(K^2)$ ou $O(K^3)$ de manter e atualizar uma matriz de covariância completa.
• Off-Policy: Aprender a partir de dados estáticos registrados por uma política de registro $\pi_0$ enfrenta três problemas principais:
  1. Ineficiência Estatística: Métodos diretos (DM) sofrem de alto viés quando as ações são raramente observadas.
  2. Variância: Estimadores de Inverse Propensity Scoring (IPS) exibem variância explosiva quando a probabilidade de registro $\pi_0(a|x)$ é pequena.
  3. Intratabilidade de Otimização: A tese argumenta que, em grandes espaços de ação, o panorama de otimização dos objetivos padrão baseados em IPS torna-se altamente não-côncavo, com platôs planos e exponencialmente muitos máximos locais, fazendo com que otimizadores baseados em gradiente falhem, independentemente da qualidade estatística do estimador.

Metodologia e Contribuições

A tese é dividida em duas partes, propondo novos métodos para cada paradigma de aprendizado.

Parte I: Aprendizado On-Policy (Escalando o Thompson Sampling)

A ideia central é manter a flexibilidade de modelos de recompensa disjuntos ao mesmo tempo em que introduz priors Bayesianos estruturados que permitem o compartilhamento de informações entre as ações.

1. Mixed-Effect Thompson Sampling (meTS) - Capítulo 3

• Metodologia: Os autores introduzem um modelo Bayesiano hierárquico onde os parâmetros das ações $\theta_a$ são acoplados através de $L$ parâmetros de efeitos latentes compartilhados $\Psi = (\psi_\ell)_{\ell \in [L]}$. O processo generativo assume $\theta_a | \Psi \sim p_0(\cdot|\Psi)$.
• Algoritmo: O meTS realiza amostragem hierárquica: primeiro amostrando os efeitos globais $\Psi_t$ de sua posterior, depois amostrando os parâmetros de ação individuais $\theta_{t,a}$ condicionados a $\Psi_t$.
• Resultados Teóricos: Para modelos lineares-Gaussianos, os autores derivam atualizações de posterior exatas em forma fechada. Eles provam um limite de regret Bayesiano de $\tilde{O}(\sqrt{Td K_{eff}})$, onde $K_{eff}$ é um número efetivo de ações. Quando o número de efeitos $L \ll K$, $K_{eff} \ll K$, resultando em uma melhoria multiplicativa sobre o TS padrão.
• Complexidade: O método reduz a complexidade de memória de $O(K^2d^2)$ para $O((L^2 + K)d^2)$ e o tempo de execução de $O(K^3d^3)$ para $O((L^3 + K)d^3)$.
• Extensões: O framework é estendido para Modelos Lineares Generalizados (GLMs) usando aproximações de Laplace tratáveis.

2. Diffusion Thompson Sampling (dTS) - Capítulo 4

• Metodologia: Para capturar dependências não lineares mais complexas entre ações, os autores substituem a estrutura latente de camada única por uma hierarquia profunda de variáveis latentes governadas por modelos de difusão pré-treinados. A prior é definida como uma cadeia de Markov de variáveis latentes $\psi_L \to \dots \to \psi_1 \to \theta_a$ conectadas por funções de ligação não lineares $f_\ell$.
• Algoritmo: O dTS emprega um procedimento de inferência recursivo. Ele aproxima a posterior intratável mantendo um "modelo de difusão de posterior", onde as funções de ligação e as covariâncias são atualizadas via atualizações do tipo Gaussiano (combinando precisão da prior e precisão dos dados) sem realizar backpropagation através da rede neural.
• Resultados Teóricos: Em um cenário linear-Gaussiano, o limite de regret escala com o número efetivo de ações e a soma das variâncias através das $L$ camadas. A complexidade escala linearmente com $L$, ou seja, $O((L+K)d^2)$, melhorando o meTS.
• Significância: Isso demonstra que modelos generativos profundos podem ser usados não apenas para representação, mas para estruturar a incerteza necessária para uma exploração eficiente.

Parte II: Aprendizado Off-Policy (Abordando Estimativação e Otimização)

A tese desafia o paradigma predominante "centrado na estimativação" e propõe três abordagens complementares.

1. Structured Direct Method (sDM) - Capítulo 6

• Metodologia: Analogamente ao meTS, o sDM introduz um vetor latente compartilhado $\psi$ para acoplar os parâmetros de ação no ambiente offline. Ele computa a posterior sobre os efeitos latentes e as posteriors condicionais para os parâmetros de ação.
• Resultados: Os autores provam que o sDM alcança convergência de $O(1/\sqrt{n})$ em subotimalidade Bayesiana sem exigir a restritiva suposição de "suporte total de registro" (full logging support). O limite depende do alinhamento entre a política de registro e a política ótima.
• Insight: Sob o critério de subotimalidade Bayesiana considerado, mostra-se que políticas gananciosas (greedy) são ótimas e podem superar políticas pessimistas, contrastando com cenários frequentistas onde o pessimismo é frequentemente necessário.

2. A Otimização Importa Mais que a Estimativação - Capítulo 7

• Metodologia: Os autores demonstram que, em grandes espaços de ação, o erro de otimização domina o erro de estimativação. Objetivos baseados em IPS padrão induzem paisagens não-côncavas que prendem os otimizadores.
• Proposta: Em vez de estimar o valor e então otimizar, a tese defende objetivos de Log-Likelihood Ponderado pela Política (PWLL):
  $$\hat{U}_g(\pi) = \frac{1}{n} \sum_{i=1}^n g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$$
• Resultados: Para políticas softmax lineares, os objetivos PWLL são côncavos (e fortemente côncavos com regularização $\ell_2$), garantindo um máximo global único. Experimentos em conjuntos de dados com até um milhão de ações mostram que esses objetivos simples e estáveis superam consistentemente métodos baseados em estimadores de valor sofisticados.

3. Pessimismo Baseado em Princípios para Suavização Exponencial - Capítulo 8

• Metodologia: Para abordar a variância do IPS, os autores introduzem estimadores de Suavização Exponencial (ES) diferenciáveis que interpolam entre nenhuma regularização e redução de variância forte.
• Teoria: Um limite de generalização PAC-Bayesiano de dois lados é derivado para esses estimadores regularizados. Este limite decompõe o erro em divergência, viés de regularização e variância restante.
• Aplicação: O limite gera um objetivo de aprendizado pessimista totalmente diferenciável, que pode ser otimizado via ascensão de gradiente estocástico. O framework é unificado para cobrir outros regularizadores como clipping e exploração implícita.
• Extensão: Os autores também introduzem a Suavização Logarítmica (LS), uma alternativa suave e diferenciável ao clipping que alcança limites de concentração mais estreitos.

Resultados Experimentais

Os métodos propostos são validados em conjuntos de dados sintéticos e reais:

• On-Policy: Em bandidos lineares e logísticos sintéticos, meTS e dTS superam significativamente os baselines (LinTS, GLM-TS, HierTS), com a lacuna de desempenho aumentando conforme o espaço de ação $K$ cresce. Nos experimentos de MovieLens (sistemas de recomendação), o meTS alcança o menor regret mesmo quando o modelo de recompensa real é mal especificado, demonstrando robustez.
• Off-Policy:
  • O sDM supera os Métodos Diretos padrão, com ganhos aumentando conforme $K$ cresce.
  • Objetivos PWLL (Capítulo 7) superam consistentemente os métodos baseados em IPS de última geração em conjuntos de dados com até um milhão de ações, mostrando superior robustez ao ajuste de hiperparâmetros.
  • Os objetivos pessimistas PAC-Bayesianos (Capítulo 8) alcançam melhores recompensas que os baselines (incluindo London et al. e Sakhi et al.) através de várias qualidades de política de registro, particularmente quando a política de registro não é uniforme.

Significância e Alegações

A tese afirma preencher a lacuna entre algoritmos de bandidos teóricos e as restrições dos sistemas industriais modernos (ex: sistemas de recomendação com milhões de itens). Seu argumento central é que escalar para grandes espaços de ação requer:

1. Estruturar a Incerteza: Usar priors hierárquicos e baseados em difusão para compartilhar força estatística entre as ações (On-Policy).
2. Reavaliar Objetivos: Reconhecer que, em grandes espaços, a tratabilidade do panorama de otimização é tão crítica quanto a precisão estatística do estimador (Off-Policy).
3. Pessimismo Diferenciável: Desenvolver objetivos pessimistas teoricamente fundamentados, porém computacionalmente viáveis, que controlem variância e viés sem depender de constantes intratáveis.

O trabalho afirma que, ao se afastar da modelagem de ações independentes e da estimativa de valor padrão, os bandidos contextuais podem ser efetivamente implantados em ambientes onde os espaços de ação rotineiramente excedem milhares ou milhões.