Resumen Técnico: La reutilización de trayectorias en los gradientes de política permite una convergencia rápida

Planteamiento del problema

Los métodos de Gradiente de Política (PG) son efectivos para problemas de control continuo, pero sufren de una baja eficiencia de muestreo. Los algoritmos de PG "vanilla" estándar (por ejemplo, REINFORCE, GPOMDP) dependen exclusivamente de datos on-policy frescos, lo que requiere $O(\epsilon^{-2})$ trayectorias para alcanzar un punto estacionario $\epsilon$-aproximado. Esta ineficiencia se deriva de la alta varianza de las estimaciones de gradiente, la cual no desaparece porque los gradientes siempre se estiman a partir de nuevas muestras.

Si bien la reutilización de datos pasados (trayectorias o gradientes off-policy) es una estrategia común para mejorar la eficiencia, el trabajo teórico existente se ha centrado principalmente en la reutilización de gradientes (por ejemplo, SVRPG, SRVRPG, STORM-PG), logrando tasas de hasta $O(\epsilon^{-3/2})$. La reutilización de trayectorias pasadas, aunque intuitiva, ha permanecido mayormente inexplorada desde una perspectiva teórica rigurosa. Los intentos previos de reutilizar trayectorias carecían de garantías de convergencia o dependían de supuestos fuertes y estimadores complejos (por ejemplo, requiriendo el almacenamiento de todas las políticas pasadas o sufriendo una alta varianza debido al pesaje de importancia ingenuo).

La pregunta central abordada es: ¿Puede la reutilización de trayectorias off-policy pasadas conducir a mejoras probables en la complejidad de muestreo de los métodos de PG?

Metodología

El algoritmo RT-PG

Los autores proponen RT-PG (Reusing Trajectories – Policy Gradient), un nuevo algoritmo que estima el gradiente de la política aprovechando las trayectorias recolectadas de las últimas $\omega$ iteraciones. La innovación central es el estimador de Media de Potencia Múltiple (MPM), que combina datos on-policy y off-policy utilizando un esquema de Pesaje de Importancia Múltiple (MIW) corregido.

El estimador MPM

Para abordar los desafíos estadísticos de la reutilización de datos (específicamente el sesgo introducido por la dependencia entre los parámetros de la política actual y las trayectorias pasadas), el estimador MPM emplea dos mecanismos clave:

1. Coeficientes Deterministas: A diferencia del Heurístico de Balance (BH) que utiliza coeficientes dependientes de todas las políticas pasadas (introduciendo "sesgo de tiempo cruzado"), RT-PG utiliza coeficientes deterministas $\alpha_{i,k}$ que dependen solo del recuento de iteraciones y el índice de la ventana. Esto elimina el sesgo de tiempo cruzado.
2. Corrección de Media de Potencia (PM): Para asegurar que los pesos de importancia permanezcan acotados (una propiedad "defensiva") y para controlar el sesgo introducido por los coeficientes deterministas, el estimador aplica una corrección de PM a los pesos de importancia vanilla. El peso corregido para una trayectoria $\tau$ recolectada bajo la política $\pi_{\theta_i}$ y evaluada bajo $\pi_{\theta_k}$ es:
   $$\left( (1 - \lambda_{i,k}) \frac{p_{\theta_i}(\tau)}{p_{\theta_k}(\tau)} + \lambda_{i,k} \right)^{-1}$$
   donde $\lambda_{i,k} \in [0, 1]$ es un parámetro de corrección. Este término representa una media armónica entre el peso vanilla y 1, asegurando que el peso esté acotado por $1/\lambda_{i,k}$.

Análisis Teórico

Los autores proporcionan un análisis de tiempo finito riguroso del estimador MPM:

• Límites de Concentración: Derivan límites de concentración de alta probabilidad para el estimador utilizando la desigualdad de Freedman para martingalas y un argumento de recubrimiento para manejar la naturaleza vectorial del gradiente.
• Control de Sesgo: El análisis separa y controla explícitamente dos fuentes de sesgo:
  • Sesgo de Objetivo (Target Bias): Resultante de que el parámetro objetivo $\theta_k$ depende de la historia de las trayectorias. Esto se controla mediante un argumento de recubrimiento sobre un subconjunto del espacio de parámetros que contiene el objetivo dependiente de la historia.
  • Sesgo de PM: Resultante del término de corrección de PM. Esto se gestiona seleccionando cuidadosamente $\lambda_{i,k}$ basado en el tamaño del lote y el límite de divergencia $\chi^2$ entre las distribuciones de las trayectorias.

Contribuciones Clave

1. Primera Evidencia Rigurosa: El artículo proporciona la primera prueba teórica de que la reutilización de trayectorias pasadas off-policy puede acelerar significativamente la convergencia de PG.
2. Nuevo Estimador (MPM): Introducción del estimador MPM, que mezcla efectivamente datos on-policy frescos con trayectorias off-policy de las últimas $\omega$ iteraciones, manteniendo pesos de importancia acotados y eliminando el sesgo de tiempo cruzado.
3. Complejidad de Muestreo Mejorada:
   • Reutilización Parcial: Cuando se reutilizan trayectorias de las últimas $\omega$ iteraciones (donde $\omega < K$), RT-PG logra una complejidad de muestreo de $\tilde{O}(\epsilon^{-2}\omega^{-1})$.
   • Reutilización Total: Cuando se reutilizan todas las trayectorias pasadas disponibles (donde $\omega \ge K$), el algoritmo logra una complejidad de muestreo de $\tilde{O}(\epsilon^{-1})$. Esto iguala las mejores tasas conocidas en la literatura para métodos de PG y representa una mejora significativa sobre la tasa estándar de $O(\epsilon^{-2})$.
4. Implementación Práctica: Se propone una variante práctica de RT-PG que pondera adaptativamente los datos off-policy basándose en estimaciones empíricas de la disimilitud de la política (divergencia), eliminando la necesidad del límite global teórico $D$ en la práctica.

Resultados

Resultados Teóricos

Bajo supuestos estándar (divergencia $\chi^2$ acotada entre distribuciones de trayectoria y regularidad de la clase de política), los autores demuestran que RT-PG encuentra un punto estacionario $\epsilon$-aproximado con:

• Complejidad de muestreo de $\tilde{O}(\epsilon^{-1})$ en el régimen de reutilización total.
• Complejidad de muestreo de $\tilde{O}(\epsilon^{-2}\omega^{-1})$ en el régimen de reutilización parcial.

Estos resultados se mantienen sin requerir el almacenamiento de las políticas pasadas (a diferencia de los métodos basados en BH), requiriendo solo el almacenamiento de las trayectorias pasadas.

Resultados Empíricos

Se realizaron experimentos en tareas de control continuo (Cart Pole, Half Cheetah, Swimmer) utilizando políticas gaussianas lineales y profundas.

• Eficiencia de Muestreo: RT-PG supera consistentemente a las líneas base on-policy estándar (GPOMDP) y a los métodos de reducción de varianza de vanguardia (SVRPG, SRVRPG, STORM-PG, DEF-PG) en términos de eficiencia de muestreo. En el entorno Half Cheetah, RT-PG logró casi el doble del rendimiento final de la mayoría de las líneas base.
• Impacto de la Reutilización de Trayectorias: Los experimentos variando el tamaño de la ventana $\omega$ demostraron que aumentar la ventana de reutilización acelera la convergencia. RT-PG mostró rendimientos decrecientes para ventanas muy grandes, pero superó significativamente a las líneas base incluso con una reutilización moderada.
• Comparación con la Reutilización Ingenua: RT-PG superó significativamente a MIW-PG (que utiliza un pesaje uniforme), validando la efectividad de la corrección de PM y el esquema de pesaje adaptativo para controlar la varianza.
• Eficiencia de Memoria: A diferencia de los métodos basados en BH que requieren almacenar todos los parámetros de la política pasados para calcular los pesos, RT-PG solo requiere almacenar las trayectorias pasadas, lo que lo hace más escalable para espacios de política de alta dimensión.

Significancia y Reivindicaciones

El artículo afirma proporcionar la primera evidencia teórica rigurosa de que la reutilización de trayectorias es un mecanismo viable y poderoso para acelerar la convergencia de Gradiente de Política. Al introducir el algoritmo RT-PG y el estimador MPM, los autores cierran la brecha entre la idea intuitiva de reutilizar datos pasados y las garantías de convergencia demostrables.

La significancia radica en:

1. Avance Teórico: Establecer que la reutilización de trayectorias puede lograr la tasa $\tilde{O}(\epsilon^{-1})$, anteriormente considerada difícil para los métodos de PG sin supuestos fuertes o reutilización de gradientes.
2. Utilidad Práctica: Demostrar que la reutilización de trayectorias reduce el costo de muestreo sin comprometer la estabilidad del aprendizaje, ofreciendo una alternativa práctica a los métodos de reutilización de gradientes que pueden requerir tamaños de lote más grandes o técnicas complejas de reducción de varianza.
3. Eficiencia de Memoria: Lograr tasas mejoradas sin la sobrecarga de memoria de almacenar las parametrizaciones de la política pasadas, una limitación de otros enfoques de reutilización de trayectoria como el Heurístico de Balance.

Los autores se mantienen modestos respecto a las limitaciones, señalando que sus resultados dependen del supuesto de divergencia $\chi^2$ acotada entre las distribuciones de trayectoria y que la complejidad de muestreo depende de la dimensionalidad $d_\Theta$. Identifican la eliminación de este supuesto y la eliminación de la dependencia de la dimensión como trabajo futuro.