On the Variance of Temporal Difference Learning and its Reduction Using Control Variates

Resumo Técnico: Sobre a Variância do Aprendizado de Diferença Temporal e sua Redução Usando Variáveis de Controle

Definição do Problema
A avaliação de política é um desafio fundamental no aprendizado por reforço (RL). Enquanto os métodos de Monte Carlo (MC) fornecem estimativas não viesadas das funções de valor, eles sofrem de alta variância devido à necessidade de realizar a média sobre trajetórias completas. Por outro modo, o aprendizado de Diferença Temporal (TD) utiliza o bootstrapping (atualizar estimativas com base em outras estimativas) para reduzir a variância, mas isso introduz viés. O mecanismo preciso pelo qual o TD reduz a variância, particularmente no regime online, e como ele se compara assintoticamente ao MC, tem sido objeto de um debate sutil. Além disso, embora a Estimativa Direta de Vantagem (DAE) tenha demonstrado sucesso empírico no aprendizado profundo por reforço, sua justificativa teórica em relação à redução de variância tem sido limitada a propriedades de convergência, em vez de uma análise rigorosa de seus limites de variância comparados ao TD padrão.

Metodologia
Os autores analisam a variância do aprendizado TD de múltiplos passos dentro de um contexto faseado (síncrono) utilizando representações tabulares. Este cenário abstrai complexidades associadas a atualizações assíncronas e aproximações estocásticas, permitindo um isolamento mais claro dos mecanismos de variância.

1. Decomposição de Variância: O artigo deriva uma relação de recorrência para a variância das atualizações TD de múltiplos passos. Ao expandir essa recursão, os autores comparam a variância assintótica do TD contra estimadores MC.
2. Estrutura de Variável de Controle: Os autores enquadram a função de vantagem ($A^\pi$) como uma variável de controle para a avaliação de política. Eles utilizam o conceito de variáveis de controle ajustadas por regressão, onde a função de vantagem é estimada simultaneamente com a função de valor para minimizar a variância do estimador de retorno.
3. Estimativa Direta de Vantagem (DAE): O artigo analisa a DAE (Pan et al., 2022) como um problema de mínimos quadrados restrito. Ao tratar as estimativas da função de vantagem como parâmetros de incômodo em um framework de regressão, os autores reformulam a regra de atualização da DAE para mostrar explicitamente sua estrutura como uma variável de controle ajustada por regressão.
4. Validação Empírica: As alegações teóricas são ilustradas usando ambientes de Cadeia MDP cuidadosamente projetados. Estes experimentos variam o grau de estocasticidade (mascaramento de recompensa, transições pegajosas/sticky) e a cobertura de estados-ações para testar os comportamentos assintóticos de MC, TD e DAE sob diferentes condições.

Principais Contribuições

1. Limite de Variância Assintótica de TD: Os autores provam que, tanto em contextos faseados (síncronos) quanto IID (assíncronos), a variância assintótica do aprendizado TD de múltiplos passos é limitada superiormente pela variância dos métodos de Monte Carlo.

   • Mecanismo: O artigo identifica que o TD reduz a variância não meramente por um tradeoff viés-variância, mas por agregar efetivamente um pool maior de trajetórias independentes. Quando os estados de bootstrapping são diversos e fracamente correlacionados, a média de seus valores reduz a variância. Inversamente, se os estados de bootstrapping forem idênticos (altamente correlacionados), a capacidade de redução de variância do TD diminui e ele se aproxima assintoticamente da variância do MC.
   • Efeito do Horizonte: Para um número fixo de amostras, atualizações de horizonte mais curto (menor $k$) incorrem em menos variância do que atualizações de horizonte longo único.

2. DAE como Variável de Controle Ajustada por Regressão: O artigo demonstra que a função de vantagem pode servir como uma variável de controle para estimadores MC. Ele estabelece ainda que a Estimativa Direta de Vantagem (DAE) é uma forma de variável de controle ajustada por regressão que estima simultaneamente as funções de valor e de vantagem.

   • Limite de Variância: No limite de grandes amostras, a DAE alcança um limite superior de variância mais apertado comparado ao TD padrão. Especificamente, a variância da DAE é limitada pela variância de um estimador MC ajustado pela vantagem (MC-A), que é, por si só, menor ou igual à variância do MC padrão.

3. Ilustrações Empíricas:

   • Em ambientes determinísticos, onde os estados de bootstrapping são idênticos, o TD falha em reduzir a variância em relação ao MC, confirmando a dependência teórica da diversidade de trajetórias.
   • Em ambientes de transição estocástica, o TD exibe o tradeoff viés-variância esperado, e a DAE converge rapidamente (semelhante às iterações de Bellman), porque a função de vantagem explica totalmente a variância.
   • Em cenários de mascaramento de recompensa (onde a variância da recompensa não pode ser explicada pelas ações), as estimativas de vantagem da DAE não podem eliminar totalmente a variância, resultando em uma pequena lacuna assintótica em comparação com as iterações de Bellman, mas ainda assim supera o TD.
   • Em cenários de baixa cobertura (espaços de ação subamostrados), a DAE pode sofrer de viés de pequena amostra devido a estimativas de vantagem não confiáveis, mas ainda assim converge para um Erro Quadrático Médio (MSE) menor do que o TD, sugerindo robustez mesmo com variáveis de controle imperfeitas.

Resultos e Significância
O artigo fornece uma explicação teórica rigorosa para as capacidades de redução de variância do bootstrapping, indo além do intuitivo "tradeoff viés-variância" para um mecanismo baseado na agregação de trajetórias. O trabalho esclarece que a superioridade do TD sobre o MC é condicional à diversidade dos estados de bootstrapping.

Além disso, o trabalho oferece uma base teórica para a DAE, explicando seu sucesso empírico no aprendizado profundo por reforço ao enquadrá-la como um método de variável de controle. Os resultados sugerem que aproveitar a função de vantagem como uma variável de controle pode, teoricamente, alcançar limites de variância mais estreitos do que o TD padrão.

Limitações e Escopo
Os autores observam várias limitações:

• Os resultados teóricos são derivados para contextos faseados e IID; a generalização para esquemas de amostragem Markoviana realistas permanece uma questão aberta.
• A análise foca na redução de variância; a DAE incorre em custos computacionais adicionais (resolução de mínimos quadrados) e requisitos de armazenamento.
• Os limites estreitos de variância para a DAE dependem de uma aproximação de grandes amostras onde os coeficientes da variável de controle são ótimos. Embora os resultados empíricos sugiram benefícios em regimes de pequenas amostras, uma análise rigorosa do viés de pequena amostra na DAE é deixada para trabalhos futuros.

O artigo conclui que entender a agregação de trajetórias independentes é central para a redução de variância do TD, e que a regressão de variável de controle (via DAE) oferece um caminho fundamentado para reduzir ainda mais a variância.