Off-Policy Learning in Large Action Spaces: Optimization Matters More Than Estimation

Resumo Técnico: Aprendizado Off-Policy em Grandes Espaços de Ação: A Otimização Importa Mais do que a Estimativa

Definição do Problema
O aprendizado off-policy (OPL) em bandits contextuais offline visa aprender uma política $\hat{\pi}$ a partir de dados registrados $D_n = \{(X_i, A_i, R_i)\}$ que maximize a recompensa esperada $V(\pi)$. O paradigma dominante envolve a otimização de um estimador de avaliação off-policy (OPE), tipicamente baseado em Inverse Propensity Scoring (IPS), tal como $\hat{\pi} = \arg\max_\pi \hat{V}_{IPS}(\pi)$. Enquanto pesquisas recentes têm se focado no desenvolvimento de estimadores sofisticados com propriedades estatísticas aprimoradas (ex: redução de variância ou viés) para aproximar $V(\pi)$ de forma mais precisa, este artigo argumenta que essa abordagem centrada no estimador negligencia um obstáculo prático crítico: o landscape de otimização.

Em grandes espaços de ação (onde o número de ações $K$ pode atingir milhões), objetivos baseados em IPS combinados com parametrizações de política padrão (ex: softmax) exibem patologias de otimização severas. Estas incluem longos patamares (plateaus) onde o gradiente ascendente estagna e um número exponencial de máximos locais pobres. O artigo postula que mesmo estimadores com garantias estatísticas superiores falham em produzir boas políticas porque o problema de otimização subjacente torna-se intratável à medida que $K$ aumenta.

Metodologia e Análise
Os autores fornecem tanto análise teórica quanto evidência empírica para apoiar a afirmação de que a estabilidade da otimização é mais crítica do que a precisão da estimativa em grandes espaços de ação.

1. Análise Teórica de Objetivos Baseados em IPS:

   • O artigo analisa "políticas oráculo" (os maximizadores teóricos dos objetivos esperados) para vários estimadores baseados em IPS, incluindo IPS padrão, Clipped IPS (cIPS), Exponential Smoothing (ES), Doubly Robust (DR), Marginalized IPS (MIPS), OffCEM, POTEC e Policy Convolution (PC).
   • Patologias de Otimização: Os autores provam que, para estimadores lineares-em-$\pi$ com políticas softmax, o gradiente ascendente pode permanecer preso em regiões subótimas por $O(K_{eff})$ iterações, onde $K_{eff}$ é o tamanho do espaço de ação efetivo. Além disso, o landscape contém um número de máximos locais exponencial em $K_{eff}$.
   • O Papel de $K_{eff}$: Mesmo métodos projetados para grandes espaços de ação (como MIPS ou OffCEM) frequentemente falham em mitigar isso se otimizarem sobre o espaço de ação total $A$ ($K_{eff} = K$). A única exceção identificada é o POTEC, que restringe a otimização a um nível de cluster, reduzindo efetivamente o $K_{eff}$.
   • Parametrização Consciente do Objetivo: Os autores propõem alinhar a classe de política com o viés indutivo do estimador. Por exemplo, restringir o suporte da política ao suporte da política de registro $S_0$ para métodos baseados em IPS, ou usar uma decomposição em dois estágios para métodos baseados em clusters, pode reduzir o $K_{eff}$ e melhorar a treinabilidade sem alterar o alvo estatístico. No entanto, isso apenas mitiga os sintomas; não cura a não-concavidade fundamental dos objetivos baseados em IPS.

2. Objetivos de Log-Likelihood Ponderados pela Política (PWLL):

   • Como uma alternativa fundamental, o artigo explora objetivos PWLL, que assumem a forma $\hat{U}_g(\pi) = \frac{1}{n} \sum g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$.
   • Concavidade: Ao contrário dos objetivos IPS, os objetivos PWLL são inerentemente côncavos (e fortemente côncavos com regularização $\ell_2$) quando utilizando políticas linear-softmax. Isso ocorre porque o mapeamento de scores para log-probabilidades é côncavo.
   • Garantias de Otimização: Os autores estabelecem que o gradiente ascendente estocástico em objetivos PWLL alcança taxas de convergência global de $O(1/\sqrt{T})$ em geral, acelerando para taxas geométricas com regularização.
   • Variantes: O estudo avalia variantes específicas de PWLL, incluindo Local Policy Improvement (LPI), Clipped LPI (cLPI) e Regularized KL (RegKL). Notavelmente, mostra-se que o cLPI induz a mesma regra de decisão gananciosa (greedy) do cIPS, mas através de um problema de otimização convexo.

Principais Contribuições

1. Escalonamento da Teoria de Otimização com o Espaço de Ação: O artigo formaliza como as patologias de otimização (patamares e máximos locais) escalam com o número de ações $K$, explicando por que os objetivos baseados em IPS tornam-se cada vez mais difíceis de otimizar conforme $K$ cresce.
2. Parametrização Consciente do Objetivo: Os autores identificam estruturas de política minimamente suficientes para vários objetivos (derivadas de políticas oráculo) e demonstram que restringir ou fatorizar a política para corresponder a essas estruturas melhora a treinabilidade e o desempenho.
3. PWLL como um Objetivo Amigável à Otimização: O artigo demonstra que, para políticas linear-softmax, os objetivos PWLL produzem landscapes de otimização bem comportados e côncavos, oferecendo uma alternativa robusta para a maximização de valor direta.
4. Testes de Estresse Empíricos em Grande Escala: Experimentos extensos em três conjuntos de dados de grande escala (MovieLens com $K=60k$, Twitch com $K=200k$ e GoodReads com $K=1M$) mostram que os métodos baseados em IPS são altamente sensíveis a hiperparâmetros (tamanho de lote, cronogramas de taxa de aprendizado), enquanto os métodos PWLL são robustos e alcançam consistentemente recompensas mais altas.
5. Orientação Acionável: O artigo destila regras de design para grandes espaços de ação: priorize a estabilidade da otimização usando parametrizações conscientes do objetivo e prefira objetivos do tipo PWLL sobre estimadores IPS complexos para o aprendizado de políticas.

Resultados

• Sensibilidade de Otimização: Em varreduras controladas, os objetivos baseados em IPS (incluindo métodos de estado da arte como POTEC) mostraram alta variância e colapso de desempenho sob hiperparâmetros subótimos. Em contraste, os métodos PWLL (especificamente cLPI) mantiveram alto desempenho em todas as configurações.
• Estimativa vs. Aprendizado: O artigo destaca um achado contraintuitivo: métodos com menor Erro Quadrático Médio (MSE) como estimadores de valor (ex: MIPS) não produziram necessariamente melhores políticas. Inversamente, os métodos PWLL, que são pobres estimadores de valor (alto MSE), produziram as melhores políticas. Isso sugere que, em grandes espaços de ação, a capacidade de otimizar o objetivo é um preditor de qualidade de política mais forte do que a precisão estatística da estimativa de valor.
• Impacto da Parametrização: Restringir o espaço de ação efetivo para corresponder ao viés indutivo do objetivo (ex: usar políticas de suporte restrito para IPS) melhorou significativamente a estabilidade e o desempenho dos métodos IPS, embora ainda tenham ficado atrás dos métodos PWLL.
• Robustez: Os métodos PWLL demonstraram superior robustez ao ruído de recompensa e a diferentes suportes de política de registro em comparação com as abordagens baseadas em IPS.

Significância e Alegações
O artigo alega que o campo do aprendizado off-policy tem focado excessivamente no refinamento de estimadores enquanto negligencia o landscape de otimização, um gargalo crítico em grandes espaços de ação. Os autores argumentam que:

• A otimização é o gargalo: Em grandes espaços de ação, a dificuldade de otimizar objetivos IPS não-côncavos compromete a utilidade prática até mesmo dos estimadores estatisticamente mais sofisticados.
• A simplicidade vence: Objetivos mais simples e amigáveis à otimização, como o PWLL (especificamente o cLPI), superam estimadores IPS complexos com redução de variância porque permitem uma convergência estável e confiável.
• Mudança de Design: O desenvolvimento de algoritmos de OPL para grandes espaços de ação deve abordar explicitamente considerações de otimização. O artigo defende uma mudança do design "centrado no estimador" para o design "centrado na otimização", sugerindo que garantir um landscape de otimização tratável é mais importante do que alcançar uma estimativa de valor de alta fidelidade para fins de aprendizado de política.

Os autores observam limitações: os objetivos PWLL não são adequados para avaliação off-policy (OPE) ou seleção de política onde estimativas de valor precisas são necessárias. Adicionalmente, as garantias de concavidade para PWLL hold estritamente para políticas linear-softmax; embora redes profundas possam perder a concavidade formal, a estrutura do gradiente permanece mais benigna do que a dos objetivos baseados em IPS.