Resumen Técnico: Un único tamaño de paso es suficiente para TD(0) lineal no proyectado

Declaración del Problema

El artículo aborda el análisis de convergencia en tiempo finito y con alta probabilidad de la diferenciación temporal lineal con sesgo cero (TD(0)) bajo muestreo markoviano. En este entorno, los datos se generan a lo largo de una única trayectoria de una cadena de Markov en lugar de como muestras independientes e idénticamente distribuidas (i.i.d.).

El desafío central radica en que TD(0) no es un método de gradiente estocástico estándar; sus actualizaciones están sesgadas, son no simétricas y el ruido está correlacionado temporalmente. Además, la magnitud de la actualización depende de la magnitud de las iteraciones actuales. Los análisis no asintóticos existentes suelen apoyarse en uno de dos enfoques restrictivos:

1. Proyecciones: Imponer la acotación proyectando las iteraciones sobre una bola conocida. Esto simplifica los argumentos de concentración pero altera el algoritmo y requiere el conocimiento previo de un radio adecuado (a menudo vinculado a la curvatura del problema).
2. Estabilidad Dependiente de la Curvatura: Explotar la naturaleza contractiva de la dinámica media para argumentar la estabilidad sin proyecciones. Sin embargo, esto típicamente produce condiciones de tamaño de paso o límites de estabilidad que dependen de un parámetro de curvatura desconocido ($\omega$). Cuando $\omega$ es pequeño, estos límites se vuelven arbitrariamente lentos, y el tamaño de paso no puede elegirse independientemente de $\omega$.

Los autores pretenden establecer un cronograma de un único tamaño de paso que sea independiente del parámetro de curvatura $\omega$ y que no requiera proyecciones, logrando simultáneamente garantizar:

• Robustez: Una tasa de convergencia de $\tilde{O}(1/\sqrt{T})$ que se mantenga independientemente de $\omega$.
• Rapidez: Una tasa de convergencia de $\tilde{O}(1/(\omega T))$ que explote la curvatura favorable cuando esta existe.

Metodología

1. Argumento de Auto-acotación vía Ecuaciones de Poisson

La novedad técnica central es un nuevo argumento inductivo de "auto-acotación" (self-bounding) que controla la acotación de trayectoria de las iteraciones $\theta_t$ sin depender de la curvatura $\omega$ o de proyecciones artificiales.

• El Bucle: Un análisis de concentración ingenuo es circular: acotar el error requiere actualizaciones acotadas, pero las actualizaciones acotadas requieren iteraciones acotadas.
• La Solución: Los autores descomponen el ruido de Markov utilizando la ecuación de Poisson asociada con la cadena de Markov de mezcla geométrica. Para un término de forzamiento centrado $h$, resuelven $u - P_Z u = \tilde{h}$.
• Descomposición: Esto permite que la acumulación de los términos de ruido de Markov se descomponga en un término de martingala ($M_t$) y un término de residuo controlado ($R_t$).
• Inducción: Establecen una hipótesis inductiva donde la acotación de las iteraciones hasta el tiempo $t-1$ implica la acotación en el tiempo $t$. Al controlar el término de la martingala mediante la desigualdad de Pinelis y el término de residuo mediante las propiedades de Lipschitz de la solución de Poisson, demuestran que las iteraciones permanecen uniformemente acotadas con alta probabilidad, independientemente de $\omega$.

2. Promedio de Polyak–Ruppert (PR)

El artículo analiza la iteración promediada de Polyak–Ruppert $\bar{\theta}_T = \frac{1}{S_T} \sum_{t=1}^T \eta_{t-1} \theta_{t-1}$, donde $S_T = \sum \eta_{t-1}$.

• Una vez establecida la acotación uniforme de $\theta_t$, los autores pueden controlar la variación cuadrática de los términos de la martingala y los términos de sesgo en el análisis de convergencia.
• Derivan dos límites superiores distintos para el error de la función potencial $f(\bar{\theta}_T) - f(\theta^*)$:
  • Un límite robusto derivado de un análisis clásico de descenso de gradiente estocástico promediado, que arroja $\tilde{O}(1/\sqrt{T})$.
  • Un límite rápido derivado al analizar la evolución del error $e_t = \theta_t - \theta^*$ y aprovechar la definición positiva de la parte simétrica de la matriz TD (curvatura $\omega$), lo que arroja $\tilde{O}(1/(\omega T))$.

3. Cronograma de Tamaño de Paso

El tamaño de paso propuesto es:
$$\eta_t = \frac{1}{c \tau_{\text{mix}} \phi_\infty^2} \cdot \frac{1}{\sqrt{t+1} \log(t+3)}$$
donde $c$ es una constante numérica, $\tau_{\text{mix}}$ es el tiempo de mezcla y $\phi_\infty$ acota las normas de las características. Crucialmente, este cronograma depende del tiempo de mezcla pero no de la curvatura $\omega$.

Resultados Clave

1. Acotación de Alta Probabilidad (Teorema 4.1)

Bajo supuestos estándar (MRP ergódico, características de rango completo), las iteraciones de TD(0) no proyectadas están uniformemente acotadas con alta probabilidad ($1-\delta$):
$$\sup_{t \ge 0} \|\theta_t\|^2 \le \rho R_{\text{base}}$$
donde $R_{\text{base}}$ depende del error inicial, la norma de la solución óptima y las constantes del problema, pero es independiente de $\omega$. Este es el primer resultado que muestra tal acotación para TD(0) no proyectado bajo muestreo de Markov sin utilizar $\omega$ en el tamaño de paso o en el argumento de estabilidad.

2. Tasas de Convergencia Simultáneas (Teorema 4.2)

Utilizando el mismo tamaño de paso y el promedio de PR, el algoritmo logra una tasa de convergencia de alta probabilidad para el error de la función potencial:
$$f(\bar{\theta}_T) - f(\theta^*) \le \min \left\{ \frac{C_{\text{fast}}}{\omega S_T^2}, \frac{C_{\text{robust}}}{S_T} \right\}$$
Sustituyendo el cronograma del tamaño de paso, esto se traduce en:

• Tasa Robusta: $\tilde{O}\left( \frac{\tau_{\text{mix}} R_{\text{base}}^2}{\sqrt{T}} \right)$
• Tasa Rápida: $\tilde{O}\left( \frac{\tau_{\text{mix}}^2 R_{\text{base}}^2}{\omega T} \right)$

El límite se adapta automáticamente al mínimo de estas dos tasas sin conocimiento previo de $\omega$.

3. Variante Libre de Mezcla (Apéndice E)

Los autores también proponen un tamaño de paso modificado $\eta_t \propto \frac{1}{\sqrt{t} \log^2 t}$ que no requiere el conocimiento de $\tau_{\text{mix}}$. Sin embargo, esto conlleva un costo de una dependencia doblemente exponencial de $\tau_{\text{mix}}$ en las constantes del límite de convergencia, específicamente a través de $B_{m^*}$ del prefijo inicial.

Significación y Reivindicaciones

El artículo afirma ser el primero en establecer que TD(0) lineal con muestreo de Markov puede lograr tanto tasas de convergencia robustas como rápidas de alta probabilidad utilizando un único tamaño de paso que es:

1. Independiente del parámetro de curvatura $\omega$.
2. Libre de proyecciones.

Los autores enfatizan que los trabajos previos o requerían proyecciones (cambiando el algoritmo), dependían de tamaños de paso dependientes de la curvatura (fallando cuando $\omega$ es pequeño), o solo proporcionaban límites de esperanza (por ejemplo, Lee y Orabona [2025]) en lugar de garantías de alta probabilidad.

La significación reside en el argumento de auto-acotación mediante ecuaciones de Poisson, el cual rompe la dependencia circular entre la acotación de las iteraciones y la magnitud de la actualización sin recurrir a las propiedades de contracción de la dinámica media. Esto permite que el algoritmo permanezca estable y converja rápidamente incluso cuando la curvatura es arbitrariamente pequeña, un escenario donde los análisis previos libres de proyección típicamente fallaban o requerían estrategias de descarte de datos.

El artículo mantiene la modestia respecto a la dependencia del tiempo de mezcla $\tau_{\text{mix}}$. Si bien la tasa rápida tiene una dependencia de $\tau_{\text{mix}}^2$ (peor que la dependencia lineal de $\tau_{\text{mix}}$ en algunos trabajos previos con proyecciones o descarte de datos), los autores señalan que la dependencia óptima de $\tau_{\text{mix}}$ en ausencia de proyecciones y descarte de datos sigue siendo una pregunta abierta. También reconocen que su término de error inicial decae a una tasa de $1/T$ en lugar de exponencial, una consecuencia de evitar argumentos basados en la contracción.