Resumen Técnico: Una tasa robusta de $O(1/\sqrt{T})$ para el aprendizaje TD sin proyección con aproximación de funciones lineales

Planteamiento del Problema

El aprendizaje de Diferencia Temporal (TD) con aproximación de funciones lineales es un algoritmo fundamental para la evaluación de políticas en el aprendizaje por refuerzo. Si bien la convergencia asintótica está bien comprendida, establecer tasas de convergencia en tiempo finito bajo condiciones realistas —específicamente cuando los datos son generados por una cadena de Markov (ruido de Markov)— sigue siendo un desafío.

Existe una brecha teórica crítica respecto a la tasa de convergencia "robusta" de $O(1/\sqrt{T})$. El trabajo previo que estableció esta tasa (por ejemplo, Bhandari et al., 2018) dependía de un paso de proyección artificial, donde las iteraciones se fuerzan hacia un conjunto acotado para evitar la divergencia. Esta proyección rara vez se utiliza en la práctica y requiere el conocimiento de un límite sobre la solución óptima $\theta^*$, el cual suele ser desconocido. Por el contrario, existen tasas de convergencia "rápidas" de $O(1/T)$ para el aprendizaje TD sin proyección, pero estas dependen del inverso del cuadrado de la curvatura mínima ($\omega$) de la función de potencial. Dado que $\omega$ puede ser arbitrariamente pequeño (problemas mal condicionados), la tasa rápida puede degradarse significativamente en regímenes no asintóticos.

El problema abierto, planteado por Bhandari et al. (2018), es si el TD(0) sin proyección puede alcanzar la tasa robusta de $O(1/\sqrt{T})$ sin condiciones de regularidad adicionales o proyecciones artificiales.

Metodología

Los autores analizan el algoritmo estándar de TD(0) sin proyección con aproximación de funciones lineales bajo muestreo de Markov. Su enfoque difiere fundamentalmente de los análisis previos que dependen de propiedades de contracción o proyecciones artificiales.

1. Selección de la Función de Potencial

En lugar de utilizar la distancia de norma $D$ estándar $\|V_{\bar{\theta}_T} - V_{\theta^*}\|_D^2$, los autores utilizan la función de potencial propuesta por Liu y Olshevsky (2021):
$$f(\theta) := (1 - \gamma) \|V_\theta - V_{\theta^*}\|_D^2 + \gamma \|V_\theta - V_{\theta^*}\|_{\text{Dir}}^2$$
Esta función de potencial es ventajosa porque:

• Se mantiene bien comportada incluso cuando el factor de descuento $\gamma \to 1$.
• El campo de actualización estacionaria $\bar{g}(\theta)$ satisface la igualdad $\langle -\bar{g}(\theta), \theta - \theta^* \rangle = f(\theta) - f(\theta^*)$, lo que simplifica el análisis en comparación con las desigualdades utilizadas en otros trabajos.

2. Propiedad de Auto-acotación mediante Inducción

La contribución técnica central es una novedosa propiedad de auto-acotación de las actualizaciones de TD. Los autores demuestran que, sin proyectar las iteraciones, la secuencia $\{\theta_t\}$ permanece acotada en esperanza alrededor de la solución óptima $\theta^*$, siempre que el tamaño del paso se elija cuidadosamente.

• Diseño del Tamaño del Paso (Stepsize): El tamaño del paso se define como $\eta_t = \frac{1}{c \phi_\infty^2 \log(T) \log(t+3) \sqrt{t+1}}$, donde $c$ es una constante que satisface $c > 15 + 18\sqrt{2}$.
• Argumento Inductivo: La demostración procede por inducción. Asumiendo que las iteraciones están acotadas hasta el tiempo $t-1$, los autores muestran que la actualización en el tiempo $t$ permanece acotada. Esto se basa en descomponer la actualización en una secuencia de diferencia de martingala (ruido) y un término de sesgo.
• Manejo del Ruido de Markov: Para abordar el sesgo introducido por las correlaciones de Markov (donde $E[g(\theta, Z_t) | \mathcal{F}_{t-1}] \neq \bar{g}(\theta)$), los autores aprovechan la mezcla geométrica de la cadena de Markov subyacente (Teorema 3.2). Acotan el sesgo relacionando la distribución del estado actual con la distribución estacionaria sobre un retardo $k'$, utilizando la tasa de decaimiento $\alpha^k$.

3. Análisis de Acotación

Los autores demuestran que las iteraciones satisfacen:
$$E[\|\theta_t\|^2] \leq \rho_c^2 \max\left(\frac{r_\infty^2}{\phi_\infty^2}, \|\theta^*\|^2\right)$$
donde $\rho_c$ es una constante que depende del parámetro del tamaño del paso $c$. Esta acotación se logra sin proyectar las iteraciones, cerrando efectivamente el bucle de inducción.

Resultados Clave

Garantías Teóricas

Teorema 4.2: Para la iteración de promedio ponderado $\bar{\theta}_T$ generada por TD(0) sin proyección con el tamaño de paso especificado, la esperanza de la norma al cuadrado de las iteraciones está acotada por una constante independiente del tiempo de mezcla y de la curvatura $\omega$.

Corolario 4.3: El algoritmo logra una tasa de convergencia de:
$$f(\bar{\theta}_T) - f(\theta^*) = \tilde{O}\left( \frac{c \rho_c^2 \max\{r_\infty^2, \phi_\infty^2 \|\theta^*\|^2\}}{\sqrt{T}} \right)$$
Crucialmente, las constantes ocultas en la notación $\tilde{O}$ dependen de $\|\theta^*\|$ y de los límites de las características, pero no dependen de la curvatura mínima $\omega$ ni del tiempo de mezcla $\alpha$ (excepto por una corrección polilogarítmica menor en la condición del tamaño del paso).

Comparación con Trabajos Previos

• Vs. Tasas Robustas Proyectadas: A diferencia de Bhandari et al. (2018), este resultado elimina el paso de proyección y el requisito de conocer a priori los límites de $\theta^*$. La tasa es comparable ($\tilde{O}(1/\sqrt{T})$) pero se logra sin restricciones artificiales.
• Vs. Tasas Rápidas Sin Proyección: A diferencia de Srikant y Ying (2019) y trabajos posteriores que logran $O(1/T)$, este resultado no depende del parámetro de curvatura desconocido $\omega$. Los autores muestran mediante un contraejemplo que $\omega$ puede ser arbitrariamente pequeño, lo que hace que las tasas rápidas sean potencialmente arbitrariamente lentas en la práctica, mientras que la tasa robusta permanece estable.

Significancia y Reivindicaciones

El artículo afirma resolver un problema abierto específico identificado por Bhandari et al. (2018): proporcionar un análisis de tiempo finito para TD(0) sin proyección con aproximación de funciones lineales que logre una tasa de convergencia robusta.

• Eliminación de Supuestos Artificiales: El trabajo demuestra que el paso de proyección, considerado previamente necesario para un análisis robusto, no es requerido. La acotación de las iteraciones surge naturalmente de la dinámica del algoritmo cuando el tamaño del paso se escala adecuadamente con factores logarítmicos.
• Sin Regularidad Adicional: El resultado se sostiene sin asumir condiciones de regularidad adicionales sobre la estructura del problema más allá de los supuestos estándar (irreducibilidad, aperiodicidad, rango de columna completo de las características).
• Relevancia Práctica: Los autores enfatizan que, aunque las proyecciones se utilizan en la teoría para simplificar las pruebas, no se utilizan en la práctica. Este análisis cierra la brecha entre las garantías teóricas y el diseño de algoritmos prácticos.
• Umbral de Estabilidad: El artículo identifica un umbral para la constante del tamaño del paso $c$ (específicamente $c > 15 + 18\sqrt{2}$) como una condición suficiente para la estabilidad. Los resultados experimentales en datos sintéticos sugieren que este umbral captura un efecto genuino de estabilidad en tiempo finito; si $c$ es demasiado pequeño, las iteraciones pueden divergir.

Los autores señalan que el umbral sobre $c$ es una condición suficiente conservadora derivada de las constantes de la prueba (desigualdad triangular, Cauchy-Schwarz, pruebas integrales) y no es necesariamente una regla de ajuste práctico estricta. Además, se reconoce que el requisito de que $T$ sea suficientemente grande en relación con el tiempo de mezcla $\alpha$ es una limitación compartida por la literatura más amplia sobre cotas robustas, aunque los autores prefieren una presentación ejecutable de los supuestos sobre una formulación "en cualquier momento" (anytime) que requeriría el conocimiento de parámetros de mezcla desconocidos.