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

Resumen Técnico: Sobre la Varianza del Aprendizaje de Diferencia Temporal y su Reducción mediante Variables de Control

Planteamiento del Problema
La evaluación de políticas es un desafío fundamental en el aprendizaje por refuerzo (RL). Mientras que los métodos de Monte Carlo (MC) proporcionan estimaciones insesgadas de las funciones de valor, sufren de una alta varianza debido a la necesidad de promediar sobre trayectorias completas. Por el contrario, el aprendizaje de Diferencia Temporal (TD) utiliza el bootstrapping (actualizar estimaciones basadas en otras estimaciones) para reducir la varianza, pero esto introduce sesgo. El mecanismo preciso mediante el cual el TD reduce la varianza, particularmente en el régimen online, y cómo se compara asintóticamente con MC, ha sido objeto de un debate matizado. Además, aunque la Estimación Directa de la Ventaja (DAE) ha mostrado éxito empírico en el aprendizaje profundo por refuerzo, su justificación teórica con respecto a la reducción de la varianza se ha limitado a las propiedades de convergencia en lugar de un análisis riguroso de sus límites de varianza comparados con el TD estándar.

Metodología
Los autores analizan la varianza del aprendizaje TD de múltiples pasos dentro de un entorno de fases (sincrónico) utilizando representaciones tabulares. Este entorno abstrae las complejidades asociadas con las actualizaciones asíncronas y las aproximaciones estocásticas, permitiendo un aislamiento más claro de los mecanismos de varianza.

1. Descomposición de la Varianza: El artículo deriva una relación de recurrencia para la varianza de las actualizaciones TD de múltiples pasos. Al expandir esta recursión, los autores comparan la varianza asintótica de TD frente a los estimadores de MC.
2. Marco de Variables de Control: Los autores enmarcan la función de ventaja ($A^\pi$) como una variable de control para la evaluación de la política. Utilizan el concepto de variables de control ajustadas por regresión, donde la función de ventaja se estima simultáneamente con la función de valor para minimizar la varianza del estimador del retorno.
3. Estimación Directa de la Ventaja (DAE): El artículo analiza la DAE (Pan et al., 2022) como un problema de mínimos cuadrados restringido. Al tratar las estimaciones de la función de ventaja como parámetros molestos (nuisance parameters) en un marco de regresión, los autores reformulan la regla de actualización de la DAE para mostrar explícitamente su estructura como una variable de control ajustada por regresión.
4. Validación Empírica: Las afirmaciones teóricas se ilustran mediante entornos de MDP de cadena cuidadosamente diseñados. Estos experimentos varían el grado de estocasticidad (enmascaramiento de recompensas, transiciones persistentes o sticky) y la cobertura de estados-acciones para probar los comportos asintóticos de MC, TD y DAE bajo diferentes condiciones.

Contribuciones Clave

1. Límite de Varianza Asintótica de TD: Los autores demuestran que tanto en entornos de fases (sincrónicos) como en entornos IID (asíncronos), la varianza asintótica del aprendizaje TD de múltiples pasos está acotada superiormente por la de los métodos de Monte Carlo.

   • Mecanismo: El artículo identifica que el TD reduce la varianza no meramente por el compromiso entre sesgo y varianza (bias-variance tradeoff), sino al agregar efectivamente sobre un grupo más grande de trayectorias independientes. Cuando los estados de bootstrapping son diversos y débilmente correlacionados, el promedio de sus valores reduce la varianza. Por el contrario, si los estados de bootstrapping son idénticos (altamente correlacionados), la capacidad de reducción de varianza del TD disminuye y se aproxima asintóticamente a la varianza de MC.
   • Efecto del Horizonte: Para un número fijo de muestras, las actualizaciones de horizonte más corto (menor $k$) incurren en menos varianza que las actualizaciones de un solo horizonte largo.

2. DAE como Variable de Control Ajustada por Regresión: El artículo demuestra que la función de ventaja puede servir como una variable de control para los estimadores de MC. Además, establece que la Estimación Directa de la Ventaja (DAE) es una forma de variable de control ajustada por regresión que estima simultáneamente las funciones de valor y de ventaja.

   • Límite de Varianza: En el límite de grandes muestras, la DAE logra un límite de varianza más ajustado en comparación con el TD estándar. Específicamente, la varianza de la DAE está acotada por la varianza de un estimador de MC ajustado por la ventaja (MC-A), que es, a su vez, menor o igual a la varianza de un MC estándar.

3. Ilustraciones Empíricas:

   • En entornos deterministas donde los estados de bootstrapping son idénticos, el TD no logra reducir la varianza respecto a MC, confirmando la dependencia teórica de la diversidad de las trayectorias.
   • En entornos de transición estocástica, el TD exhibe el esperado compromiso entre sesgo y varianza, y la DAE converge rápidamente (similar a las iteraciones de Bellman) porque la función de ventaja explica completamente la varianza.
   • En escenarios de enmascaramiento de recompensa (donde la varianza de la recompensa no puede explicarse por las acciones), las estimaciones de ventaja de la DAE no pueden eliminar completamente la varianza, lo que resulta en una ligera brecha asintótica en comparación con las iteraciones de Bellman, aunque sigue superando al TD.
   • En entornos de baja cobertura (espacios de acción submuestreados), la DAE puede sufrir de un sesgo de muestra pequeña debido a estimaciones de ventaja poco fiables, pero aun así converge a un Error Cuadrático Medio (MSE) menor que el TD, lo que sugiere robustez incluso con variables de control imperfectas.

Resultos y Significado
El artículo proporciona una explicación teórica rigurosa de las capacidades de reducción de varianza del bootstrapping, yendo más allá del intuitivo "compromiso entre sesgo y varianza" hacia un mecanismo basado en la agregación de trayectorias. Aclara que la superioridad del TD sobre MC es condicional a la diversidad de los estados de bootstrapping.

Además, este trabajo ofrece una base teórica para la DAE, explicando su éxito empírico en el aprendizaje profundo por refuerzo al enmarcarla como un método de variable de control. Los resultados sugieren que aprovechar la función de ventaja como una variable de control puede, teóricamente, lograr límites de varianza más ajustados que el TD estándar.

Limitaciones y Alcance
Los autores señalan varias limitaciones:

• Los resultados teóricos se derivan para entornos de fases e IID; la generalización a esquemas de muestreo Markovianos realistas sigue siendo una pregunta abierta.
• El análisis se centra en la reducción de la varianza; la DAE incurre en costos computacionales adicionales (resolver mínimos cuadrados) y requisitos de almacenamiento.
• Los límites de varianza ajustados para la DAE dependen de una aproximación de grandes muestras donde los coeficientes de la variable de control son óptimos. Aunque los resultados empíricos sugieren beneficios en regímenes de muestras pequeñas, un análisis riguroso del sesgo de muestra pequeña en la DAE queda para trabajos futuros.

El artículo concluye que comprender la agregación de trayectorias independientes es central para la reducción de la varianza del TD, y que la regresión de la variable de control (vía DAE) ofrece un camino fundamentado para reducir aún más la varianza.