Resumo Técnico: Aprendizado Off-Policy Sequencial com Suavização Logarítmica

Declaração do Problema

O aprendizado off-policy permite o treinamento de políticas a partir de dados de interação registrados gerados por uma política de comportamento. Embora os fundamentos teóricos do aprendizado off-policy estejam bem estabelecidos no cenário em lote (onde uma única política é aprendida a partir de um conjunto de dados estático gerado por uma política de comportamento), os sistemas do mundo real operam de forma diferente. Na prática, as políticas são atualizadas e reimplantadas repetidamente de forma sequencial: uma política é treinada em todos os dados históricos, implantada para gerar novas interações e, em seguida, retreinada no conjunto de dados expandido para a próxima iteração.

Apesar da onipresença desse paradigma sequencial em aplicações como sistemas de recomendação e posicionamento de anúncios, ele permanece amplamente inexplorado teoricamente. As abordagens sequenciais existentes frequentemente dependem de suposições fortes, como cobertura uniforme do espaço de ações ou estratégias de coleta de dados irreais (por exemplo, tamanhos de lote que crescem exponencialmente). Além disso, os algoritmos offline de última geração atuais, que utilizam o princípio do pessimismo e frameworks PAC-Bayesianos, não foram estendidos com sucesso ao cenário sequencial com garantias rigorosas de convergência. Este artigo aborda a lacuna entre a implantação sequencial prática e as garantias teóricas, visando desenvolver algoritmos de aprendizado off-policy sequencial que sejam teoricamente sólidos e empiricamente eficazes.

Metodologia

Os autores propõem um framework baseado em Bandits Contextuais, onde um agente interage com um fluxo de dados ao longo de passos de tempo $k \geq 0$. Em cada passo, uma nova política de comportamento $\pi_k$ é implantada para coletar um lote de dados $S_k$, e o agente atualiza sua política usando o histórico cumulativo $S_{0:k}$.

A metodologia é construída sobre duas principais contribuições algorítmicas, ambas aproveitando ferramentas de aprendizado Online PAC-Bayesiano e estimadores de Suavização Logarítmica (LS):

1. Suavização Logarítmica Sequencial (Algoritmo 1)

A primeira contribuição estende o estimador de Suavização Logarítmica offline (introduzido por Sakhi et al., 2024) para o cenário sequencial.

• Estimador: O algoritmo utiliza o regularizador LS padrão $h_{LS}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q})$.
• Mecanismo: Em cada passo $k$, o algoritmo minimiza um limite superior PAC-Bayesiano sobre o risco, combinando o risco LS empírico sobre todos os dados acumulados $S_{0:k}$ e um termo de divergência KL relativo a uma priori $P$.
• Garantia Teórica: O Teorema 3.2 estabelece um limite de generalização para a saída sequencial $\pi_{k+1}$. A taxa de convergência é mostrada como $O(1/\sqrt{N_k})$, onde $N_k$ é o número total de amostras. Isso corresponde à taxa ótima do cenário em lote, mas aplica-se à acumulação sequencial de dados.
• Limitação: Os autores identificam que o termo de pseudo-variância no limite de convergência não desaparece mesmo que a política de comportamento se aproxime da política ótima, levando a uma taxa de convergência que não acelera além de $O(1/\sqrt{N_k})$.

2. Suavização Logarítmica Ajustada Sequencial (Algoritmo 2)

Para superar a convergência lenta do Algoritmo 1, os autores introduzem um novo estimador de Suavização Logarítmica Ajustada (AdjLS).

• Estimador: Um novo regularizador é definido: $h_{adj}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q(1+\lambda c)})$. Esse ajuste modifica o objetivo de desempenho para controlar a diferença entre o risco da política atual e uma média ponderada dos riscos passados.
• Mecanismo: O Algoritmo 2 minimiza o estimador de risco ajustado sobre os dados cumulativos.
• Garantia Teórica: O Teorema 4.4 prova que, sob suposições leves (especificamente, que as ações ótimas são cobertas pela classe de políticas e que o problema possui um certo grau de separabilidade, quantificado por $\Delta_u > 0$), o Algoritmo 2 alcança uma taxa de convergência acelerada de $O(1/N_k^\alpha)$ para qualquer $\alpha \in [0.5, 1)$.
• Insight Chave: Diferentemente do estimador LS padrão, o termo de erro do estimador ajustado $L(\pi^*, \pi_j)$ desaparece à medida que a política de comportamento $\pi_j$ se aproxima da política ótima $\pi^*$, permitindo uma convergência mais rápida.

Contribuições Principais

1. Primeiros Algoritmos PAC-Bayes Sequenciais: O artigo apresenta os primeiros algoritmos off-policy PAC-Bayesianos projetados especificamente para o cenário sequencial, fornecendo garantias teóricas de convergência que interpolam entre os regimes totalmente em lote e totalmente online.
2. Convergência Acelerada via Ajuste: Os autores identificam uma limitação fundamental na aplicação sequencial de estimadores offline padrão e propõem um ajuste principiado (AdjLS) que produz taxas de convergência aceleradas comprovadamente sob suposições razoáveis.
3. Suposições Relaxadas: A análise teórica requer apenas que a classe de políticas cubra as ações ótimas (Suposição 3.4), o que é estritamente mais fraco do que as suposições de cobertura uniforme exigidas por trabalhos sequenciais anteriores (por exemplo, Zenati et al., 2023).
4. Generalização para Contextos Não-IID: O framework é mostrado como adaptável a ambientes não estacionários onde as distribuições de contexto evoluem ao longo do tempo, relaxando a suposição de i.i.d. sobre os contextos.

Resultados Empíricos

Os autores avaliam seus métodos em conjuntos de dados multiclasse padrão (MNIST, FashionMNIST, EMNIST, CIFAR100) convertidos em problemas de bandit contextual.

• Sequencial vs. Lote: Os experimentos demonstram que aumentar o número de atualizações intermediárias de política ($k$) melhora consistentemente o desempenho final da política em comparação com uma única atualização em lote ($k=1$). Isso valida o benefício do framework sequencial.
• Comparação de Algoritmos:
  • SeqAdjLS (Algoritmo 2) supera consistentemente o SeqLS (Algoritmo 1), confirmando a vantagem teórica do estimador ajustado.
  • Ambos os métodos propostos superam significativamente o SCRM (Minimização Sequencial de Risco Contrafactual, Zenati et al., 2023). Os autores observam que o SCRM tende a ser excessivamente conservador, especialmente nos primeiros rounds com tamanhos de lote pequenos, e depende de estratégias de coleta de dados irreais (lotes que crescem exponencialmente) que descartam dados históricos.
• Impacto da Política Inicial: A abordagem sequencial mostra ganhos substanciais quando a política de comportamento inicial está longe da ótima, particularmente em espaços de ação de alta dimensionalidade (por exemplo, CIFAR100 com 100 ações).

Significado e Alegações

O artigo afirma fechar a lacuna teórica entre o aprendizado off-policy sequencial prático e garantias rigorosas. Ao combinar técnicas de PAC-Bayes online com um novo estimador de suavização logarítmica, os autores fornecem algoritmos que:

• Generalizam abordagens offline de última geração (correspondendo ao seu desempenho no limite em lote).
• Aceleram o aprendizado em cenários sequenciais aproveitando o refinamento progressivo da política de comportamento.
• Evitam suposições irreais (como cobertura uniforme) que impedem a aplicabilidade dos métodos sequenciais existentes.

Os autores enfatizam que, embora sua análise teórica dependa da classe de políticas cobrir ações ótimas, isso é um relaxamento significativo em comparação com trabalhos anteriores. Eles concluem que a combinação de PAC-Bayes online e bandits contextuais sequenciais oferece uma direção promissora para aprendizado robusto e eficiente em sistemas dinâmicos do mundo real.