Resumen Técnico: Cerrando la Brecha entre el Aprendizaje TD Promedio y el Descuento

Enunciado del Problema

El aprendizaje de Diferencias Temporales (TD) es una piedra angular del aprendizaje por refuerzo, sin embargo, su análisis teórico en el entorno de recompensa promedio se retrasa significativamente en comparación con el entorno de descuento. En el caso de descuento, el operador de Bellman es una aplicación contractiva, lo que garantiza soluciones únicas y un análisis de convergencia sencillo. Por el contrario, en el entorno de recompensa promedio, el operador de Bellman no es contractivo con respecto a ninguna norma, y la solución a la ecuación de Bellman correspondiente no es única (se define solo hasta una constante aditiva).

La literatura existente que aborda el TD de recompensa promedio adolece de varias limitaciones en comparación con el caso de descuento:

1. Suposiciones Restrictivas: Muchos métodos requieren suposiciones (por ejemplo, $\Phi\theta \neq ce$) que excluyen el entorno tabular.
2. Garantías de Convergencia: Algunos enfoques solo garantizan la convergencia a un punto fijo dependiente de la trayectoria de la muestra o a un conjunto, en lugar de una solución única y determinista.
3. Dependencia de la Dimensión: Los límites de convergencia a menudo contienen factores explícitos de la dimensión del parámetro $d$.
4. Escalado del Número de Condición: Las complejidades de muestra más avanzadas a menudo exhiben una dependencia cuártica del número de condición del problema ($O(\eta^{-4})$), mientras que el entorno de descuento logra un escalado cuadrático ($O(\eta^{-2})$).
5. Complejidad Algorítmica: Lograr un mejor escalado en trabajos anteriores a menudo requería técnicas complejas de reducción de varianza (por ejemplo, bucles anidados), desviándose de la simplicidad del TD estándar.

Metodología

Los autores proponen un enfoque novedoso para la evaluación de políticas en el entorno de recompensa promedio formulando la solución a la ecuación de Bellman como un problema de optimización con restricciones. La idea central es que la función de valor relativo $W^*$ debe satisfacer una restricción de estado estacionario ($\mu^\top W^* = 0$).

1. Algoritmo de Doble Cadena

Para resolver la ecuación de Bellman proyectada $W^* = \Pi T_\pi W^*$, donde $\Pi = I - e\mu^\top$, los autores derivan una regla de actualización estocástica. Un desafío clave en la aproximación estocástica para este entorno es el problema del "doble muestreo": estimar el término $\mu\mu^\top(R + W_t)$ requiere la esperanza de un producto de variables aleatorias, lo cual no puede estimarse a partir de una sola trayectoria debido a la correlación.

Para resolver esto, los autores introducen un Algoritmo de Doble Cadena que utiliza dos cadenas de Markov independientes ($\{s_t\}$ y $\{\hat{s}_t\}$) en cada iteración.

• Regla de Actualización: El vector de parámetros $\theta_t$ se actualiza utilizando dos componentes:
  • $g(s_t, s'_t, \theta_t)$: Estima el término estándar de error TD $D(R + P\Phi\theta_t - \Phi\theta_t)$.
  • $f(s_t, \hat{s}_t, \theta_t)$: Estima el término de restricción $-\mu\mu^\top(R + \Phi\theta_t)$ utilizando la muestra independiente $\hat{s}_t$ para romper la correlación.
• Aproximación Lineal: El método se generaliza a la aproximación lineal de funciones ($W \approx \Phi\theta$) proyectando las actualizaciones sobre el espacio de características.

2. Algoritmo de Cadena Única

Para evitar la sobrecarga computacional de mantener dos cadenas, los autores proponen un Algoritmo de Cadena Única inspirado en el GTD (Gradient TD).

• Mecanismo: En lugar de muestrear un segundo estado independiente $\hat{s}_t$, el algoritmo mantiene una variable auxiliar $w_t$ que rastrea la esperanza $E[\phi(s)] = \Phi^\top\mu$.
• Actualización: El término $\phi(\hat{s}_t)$ en la actualización de doble cadena se reemplaza por $w_t$. La variable $w_t$ se actualiza mediante un paso separado de aproximación estocástica para converger a $\Phi^\top\mu$.
• Compensación: Aunque esto simplifica el requisito de muestreo a una sola trayectoria, el análisis muestra una dependencia ligeramente peor del número de condición en comparación con la variante de doble cadena.

3. Marco Teórico: División de Gradiente

El análisis de convergencia se basa en la técnica de división de gradiente [19]. Los autores demuestran que la dirección de actualización esperada de su algoritmo actúa como una "división de gradiente" de una función cuadrática compuesta específica:
$$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$$
Esto permite a los autores analizar el algoritmo utilizando técnicas estándar de recursión de Descenso de Gradiente Estocástico (SGD), a pesar de la naturaleza no contractiva del operador de Bellman subyacente.

Contribuciones Clave

El artículo afirma cerrar la brecha teórica entre el aprendizaje TD de recompensa promedio y el de descuento al lograr simultáneamente las siguientes características:

1. Punto Fijo Único e Independiente de la Muestra: Los algoritmos propuestos convergen casi seguramente a una solución determinista única $\theta^*$ que es independiente de la trayectoria aleatoria y de la inicialización.
2. Aplicabilidad a Entornos Tabulares y Lineales: El análisis se mantiene tanto para casos tabulares (donde $\Phi = I$) como para aproximación lineal de funciones, sin requerir la suposición restrictiva $e \notin \text{span}(\Phi)$.
3. Límites Libres de Dimensión: Los límites de convergencia no contienen factores explícitos de la dimensión $d$ (más allá de los inherentes a $\|\theta^*\|$ o $\|\theta_0\|$).
4. Convergencia de la Última Iteración: Los resultados están garantizados para la última iteración, coincidiendo con el estándar en el TD de descuento, en lugar de depender del promediado de iteraciones.
5. Mejor Escalado del Número de Condición:
   • El algoritmo de Doble Cadena logra una complejidad de muestra de $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$, donde $\eta_1$ es un número de condición definido como $\min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$. Esto coincide con el escalado cuadrático observado en el entorno de descuento.
   • El algoritmo de Cadena Única logra $\tilde{O}(\epsilon^{-1}\eta^{-4})$ (cuártico), lo cual es una mejora sobre algunos trabajos anteriores pero ligeramente peor que la variante de doble cadena.
6. Simplicidad Algorítmica: El escalado cuadrático se logra sin técnicas de reducción de varianza (por ejemplo, bucles anidados o lotes completos periódicos), manteniendo la simplicidad de las actualizaciones TD simples.

Resultados

Los autores proporcionan un análisis de muestra finita para ambos algoritmos bajo muestreo i.i.d. y de Markov, con tamaños de paso constantes y decrecientes.

• Límites Teóricos: Los Teoremas 4.1–4.3 establecen tasas de convergencia y complejidades de muestra. El método de doble cadena coincide con el estado del arte para el TD de descuento en términos de escalado de parámetros.
• Experimentos Numéricos: Los algoritmos se probaron en 15 MDPs tabulares de OpenAI Gym y MO-Gymnasium.
  • Los resultados muestran que los métodos propuestos generalmente superan a las líneas base anteriores (incluyendo [10], [11], [12], [17], [18] y [21]) en términos de error de aproximación relativo a la solución verdadera.
  • Los experimentos confirman que los métodos convergen a la solución única, mientras que algunas líneas base (que convergen a conjuntos o puntos dependientes de la muestra) muestran una mayor varianza o error en el entorno tabular.

Significado

El artículo afirma resolver las advertencias teóricas persistentes asociadas con el análisis del TD de recompensa promedio. Al utilizar la división de gradiente y una estrategia de muestreo de dos cadenas (o cadena única con variable auxiliar), los autores demuestran que el TD de recompensa promedio puede lograr las mismas propiedades favorables de convergencia que el TD de descuento:

• Unicidad: Convergencia a una solución bien definida y única.
• Generalidad: Aplicabilidad a entornos tabulares y lineales sin suposiciones restrictivas.
• Eficiencia: Dependencia cuadrática del número de condición sin la necesidad de maquinaria compleja de reducción de varianza.

Este trabajo sugiere que las dificultades teóricas del entorno de recompensa promedio pueden superarse reformulando el problema como una tarea de optimización con restricciones y aprovechando estrategias de muestreo específicas para manejar la naturaleza no contractiva del operador de Bellman.