R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimes

Resumo Técnico: R-GTD: Uma Análise Geométrica da Aprendizagem por Diferença Temporal de Gradiente em Regimes Singulares

Declaração do Problema
Os algoritmos de aprendizagem por Diferença Temporal de Gradiente (GTD), particularmente o GTD2, são métodos estabelecidos para avaliação de políticas fora de política com aproximação linear de funções. Eles minimizam o Erro de Bellman Projetado Quadrático Médio (MSPBE) para encontrar uma aproximação da função valor que satisfaça a equação de Bellman dentro de um espaço de características. No entanto, as garantias teóricas de convergência dos métodos GTD existentes dependem de uma suposição restritiva: a Matriz de Interação de Características (FIM), definida como $\Phi^\top D_\beta (\gamma P^\pi - I) \Phi$, deve ser não singular. Na prática, a FIM pode tornar-se singular ou quase singular (mal condicionada), levando a instabilidade, divergência ou desempenho degradado. Embora trabalhos anteriores tenham tentado abordar isso por meio de regularização, suas garantias teóricas frequentemente dependem de outras condições altamente restritivas, como restringir a solução ótima à origem ou assumir não singularidade global para derivar limites de erro. Além disso, a relação geométrica entre soluções regularizadas e o conjunto de soluções original do GTD2 em regimes singulares permanece inexplorada.

Metodologia
Os autores propõem o R-GTD (Diferença Temporal de Gradiente Regularizada), um novo algoritmo derivado de uma reformulação do objetivo de otimização. A metodologia central envolve as seguintes etapas:

1. Reformulação do Objetivo: Os autores estendem o problema de otimização com restrições do GTD2 introduzindo uma variável de folga auxiliar $w$ e um termo de penalidade quadrática. Isso leva a um problema de otimização regularizado (Problema 4) que minimiza uma soma ponderada do erro de Bellman projetado e um termo envolvendo a variável auxiliar.
2. Formulação de Ponto de Sela: Este problema com restrições é reescrito como um problema de ponto de sela min-max convexo-concavo (Problema 5) usando uma função Lagrangiana. Demonstra-se que a Lagrangiana é estritamente convexa nas variáveis primais ($\theta, w$) e côncava na variável dual ($\lambda$), garantindo a existência de um ponto de sela único mesmo quando a FIM é singular.
3. Derivação do Algoritmo: Ao aplicar Dinâmicas de Gradiente Primal-Dual (PDGD) à Lagrangiana, os autores derivam as regras de atualização do R-GTD (Algoritmo 1). Essas regras incorporam amostragem por importância para dados fora de política e atualizam três parâmetros: os pesos da função valor ($\theta$), a variável auxiliar ($w$) e a variável dual ($\lambda$).
4. Análise Geométrica: O artigo fornece uma análise geométrica rigorosa do comportamento da solução. Caracteriza a solução do R-GTD como uma perturbação do conjunto de soluções do GTD2. Especificamente, analisa o comportamento limite quando o parâmetro de regularização $c \to \infty$, distinguindo entre casos não singulares e singulares.

Principais Contribuições
O artigo faz três contribuições primárias:

• Remoção de Suposições de Não Singularidade: O R-GTD garante convergência para uma solução única sem exigir que a FIM seja não singular. Diferentemente de métodos regularizados anteriores que impõem condições adicionais restritivas para lidar com singularidades, o R-GTD alcança isso através de sua formulação específica, sem suposições extras.
• Caracterização Geométrica e Limites de Erro: Os autores fornecem uma análise geométrica detalhada do regime singular. Eles estabelecem limites de erro explícitos entre a solução do R-GTD e a solução projetada verdadeira. No caso singular, provam que a solução do R-GTD converge para a projeção ortogonal do conjunto de soluções do GTD2 sobre o complemento do espaço nulo da matriz $G = M^\top B^{-1} M$. Isso esclarece exatamente qual solução dentro do conjunto afim do GTD2 é selecionada pela regularização.
• Validação Empírica: O algoritmo é validado em configurações onde a FIM é estritamente singular. Os experimentos demonstram que o R-GTD converge consistentemente para uma solução única de ponto de sela com maior estabilidade em comparação ao GTD2 e outras bases regularizadas (por exemplo, Ghiassian et al., 2020; Yu, 2017).

Resultados

• Convergência: A análise teórica confirma que as dinâmicas de tempo contínuo do R-GTD convergem globalmente para um ponto de sela único. Usando o método da Equação Diferencial Ordinária (EDO), mostra-se que as iterações estocásticas do Algoritmo 1 convergem para esta solução com probabilidade um.
• Limites de Erro: No caso não singular, o erro entre a solução do R-GTD e a solução do GTD2 é limitado por $O(1/c)$. No caso singular, a solução do R-GTD converge para um elemento específico do conjunto de soluções afins do GTD2 (aquele ortogonal ao espaço nulo de $G$) com um limite de erro de $O(1/c)$.
• Desempenho Experimental: Em experimentos envolvendo MDPs singulares, o contraexemplo de Baird e ambientes estocásticos (Frozen Lake), o R-GTD suprime consistentemente o componente do espaço nulo que causa instabilidade no GTD2 padrão. Ele alcança erro final menor e variância reduzida em comparação com métodos de base, particularmente quando a FIM é mal condicionada. A análise de sensibilidade sugere que valores intermediários do parâmetro de regularização $c$ (por exemplo, $c \in [1, 4]$) oferecem o melhor compromisso entre estabilidade e viés.

Significado
O artigo afirma que o R-GTD preenche uma lacuna teórica na compreensão da aprendizagem GTD sob condições singulares. Ao remover a suposição de não singularidade, fornece um framework robusto para avaliação fora de política em cenários onde as interações de características são degeneradas. A análise geométrica oferece uma compreensão precisa de como a regularização seleciona uma solução única do potencialmente infinito conjunto de soluções do GTD2, garantindo estabilidade sem sacrificar a estrutura teórica central do GTD2. Os autores observam que a análise atual é limitada à aproximação linear de funções e à convergência assintótica, deixando a aproximação não linear e garantias de tempo finito como direções para trabalhos futuros.