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

Resumen Técnico: R-GTD: Un Análisis Geométrico del Aprendizaje de Diferencia Temporal con Gradiente en Regímenes Singulares

Enunciado del Problema
Los algoritmos de aprendizaje de Diferencia Temporal con Gradiente (GTD), particularmente GTD2, son métodos establecidos para la evaluación de políticas fuera de política con aproximación lineal de funciones. Minimizan el Error de Bellman Proyectado de Cuadrado Medio (MSPBE) para encontrar una aproximación de la función de valor que satisfaga la ecuación de Bellman dentro de un espacio de características. Sin embargo, las garantías teóricas de convergencia de los métodos GTD existentes dependen de una suposición restrictiva: la Matriz de Interacción de Características (FIM), definida como $\Phi^\top D_\beta (\gamma P^\pi - I) \Phi$, debe ser no singular. En la práctica, la FIM puede volverse singular o casi singular (mal condicionada), lo que conduce a inestabilidad, divergencia o rendimiento degradado. Aunque trabajos anteriores han intentado abordar esto mediante regularización, sus garantías teóricas a menudo dependen de otras condiciones altamente restrictivas, como restringir la solución óptima al origen o asumir la no singularidad global para derivar cotas de error. Además, la relación geométrica entre las soluciones regularizadas y el conjunto original de soluciones de GTD2 en regímenes singulares permanece inexplorada.

Metodología
Los autores proponen R-GTD (Diferencia Temporal con Gradiente Regularizado), un nuevo algoritmo derivado de un objetivo de optimización reformulado. La metodología central implica los siguientes pasos:

1. Reformulación del Objetivo: Los autores extienden el problema de optimización con restricciones de GTD2 introduciendo una variable de holgura auxiliar $w$ y un término de penalización cuadrática. Esto conduce a un problema de optimización regularizado (Problema 4) que minimiza una suma ponderada del error de Bellman proyectado y un término que involucra la variable auxiliar.
2. Formulación de Punto de Silla: Este problema con restricciones se reescribe como un problema de punto de silla min-max cóncavo-convexo (Problema 5) utilizando una función lagrangiana. Se demuestra que el lagrangiano es estrictamente convexo en las variables primales ($\theta, w$) y cóncavo en la variable dual ($\lambda$), asegurando la existencia de un único punto de silla incluso cuando la FIM es singular.
3. Derivación del Algoritmo: Al aplicar Dinámicas de Gradiente Primal-Dual (PDGD) al lagrangiano, los autores derivan las reglas de actualización de R-GTD (Algoritmo 1). Estas reglas incorporan muestreo de importancia para datos fuera de política y actualizan tres parámetros: los pesos de la función de valor ($\theta$), la variable auxiliar ($w$) y la variable dual ($\lambda$).
4. Análisis Geométrico: El artículo proporciona un análisis geométrico riguroso del comportamiento de la solución. Caracteriza la solución de R-GTD como una perturbación del conjunto de soluciones de GTD2. Específicamente, analiza el comportamiento límite cuando el parámetro de regularización $c \to \infty$, distinguiendo entre casos no singulares y singulares.

Contribuciones Clave
El artículo hace tres contribuciones principales:

• Eliminación de Suposiciones de No Singularidad: R-GTD garantiza la convergencia a una solución única sin requerir que la FIM sea no singular. A diferencia de los métodos regularizados anteriores que imponen condiciones restrictivas adicionales para manejar singularidades, R-GTD logra esto mediante su formulación específica sin suposiciones extra.
• Caracterización Geométrica y Cotas de Error: Los autores proporcionan un análisis geométrico detallado del régimen singular. Establecen cotas de error explícitas entre la solución de R-GTD y la solución proyectada verdadera. En el caso singular, prueban que la solución de R-GTD converge a la proyección ortogonal del conjunto de soluciones de GTD2 sobre el complemento del espacio nulo de la matriz $G = M^\top B^{-1} M$. Esto aclara exactamente qué solución dentro del conjunto afín de GTD2 es seleccionada por la regularización.
• Validación Empírica: El algoritmo se valida en configuraciones donde la FIM es estrictamente singular. Los experimentos demuestran que R-GTD converge consistentemente a una solución única de punto de silla con mayor estabilidad en comparación con GTD2 y otras líneas base regularizadas (por ejemplo, Ghiassian et al., 2020; Yu, 2017).

Resultados

• Convergencia: El análisis teórico confirma que las dinámicas de tiempo continuo de R-GTD convergen globalmente a un único punto de silla. Utilizando el método de la Ecuación Diferencial Ordinaria (ODE), se demuestra que las iteraciones estocásticas del Algoritmo 1 convergen a esta solución con probabilidad uno.
• Cotas de Error: En el caso no singular, el error entre la solución de R-GTD y la solución de GTD2 está acotado por $O(1/c)$. En el caso singular, la solución de R-GTD converge a un elemento específico del conjunto de soluciones afines de GTD2 (el que es ortogonal al espacio nulo de $G$) con una cota de error de $O(1/c)$.
• Rendimiento Experimental: En experimentos que involucran MDPs singulares, el contraejemplo de Baird y entornos estocásticos (Frozen Lake), R-GTD suprime consistentemente el componente del espacio nulo que causa inestabilidad en GTD2 estándar. Logra un error final menor y una varianza reducida en comparación con los métodos base, particularmente cuando la FIM está mal condicionada. El análisis de sensibilidad sugiere que los valores intermedios del parámetro de regularización $c$ (por ejemplo, $c \in [1, 4]$) ofrecen el mejor equilibrio entre estabilidad y sesgo.

Significado
El artículo afirma que R-GTD cierra una brecha teórica en la comprensión del aprendizaje GTD bajo condiciones singulares. Al eliminar la suposición de no singularidad, proporciona un marco robusto para la evaluación fuera de política en escenarios donde las interacciones de características son degeneradas. El análisis geométrico ofrece una comprensión precisa de cómo la regularización selecciona una solución única del potencialmente infinito conjunto de soluciones de GTD2, asegurando estabilidad sin sacrificar la estructura teórica central de GTD2. Los autores señalan que el análisis actual se limita a la aproximación lineal de funciones y la convergencia asintótica, dejando la aproximación no lineal y las garantías de tiempo finito como direcciones para trabajos futuros.