Resumen Técnico: Aprendizaje de Imitación Adversario Off-Policy Probablemente Eficiente con Garantías de Convergencia

Planteamiento del Problema

El Aprendizaje de Imitación Adversario (AIL, por sus siglas en inglés) plantea el aprendizaje de imitación como un juego de dos jugadores donde un agente actualiza su política para igualar el rendimiento de un experto, mientras que un adversario actualiza una función de recompensa para maximizar la brecha de rendimiento entre ambos. Los algoritmos estándar de AIL requieren datos on-policy (muestras generadas por la política actual del agente) para evaluar las recompensas acumuladas esperadas durante las actualizaciones de la función de recompensa. Este requisito conduce a una ineficiencia de muestras significativa, ya que requiere nuevas interacciones con el entorno en cada paso de actualización, lo que hace que el enfoque sea impracticable en entornos donde las interacciones son costosas o limitadas.

Si bien se han propuesto métodos off-policy para reutilizar datos de políticas anteriores para mejorar la eficiencia de muestras, estos introducen un error de desplazamiento de distribución porque los datos ya no coinciden perfectamente con la distribución de visitas de estado-acción de la política actual. Los enfoques de AIL off-policy existentes dependen de la importancia de muestreo (que induce una alta varianza) o de transformaciones de variables complejas que alteran la función objetivo, perdiendo a menudo las garantías teóricas de convergencia. El desafío central abordado en este trabajo es: ¿Podemos garantizar la convergencia del AIL off-policy y asegurar la eficiencia de muestras sin depender de técnicas explícitas de corrección off-policy como el muestreo de importancia?

Metodología

Los autores proponen un algoritmo de AIL off-policy que combina el descenso de espejo basado en modelos para las actualizaciones de la política con el ascenso de gradiente proyectado off-policy para las actualizaciones de la recompensa. La innovación clave reside en controlar el error de desplazamiento de distribución mediante la selección cuidadosa del número de políticas pasadas ($N$) cuyos datos se reutilizan durante las actualizaciones de la recompensa.

1. Actualizaciones de la Política

El algoritmo emplea un enfoque de descenso de espejo basado en modelos.

• Estimación del Modelo: La función de transición de estado $\hat{P}_h$ se estima empíricamente a partir de encuentros de estado-acción.
• Optimización de la Política: La política se actualiza utilizando un paso de descenso de espejo regularizado por divergencia KL (Ecuación 3). Esta regla de actualización, derivada de los valores Q estimados, asegura que los cambios en la política sean lo suficientemente conservadores como para acotar la distancia de Variación Total (TV) entre políticas consecutivas. Esta estabilidad es crucial para controlar el desplazamiento de distribución en las actualizaciones de recompensa off-policy.

2. Actualizaciones de la Recompensa

En lugar de utilizar solo datos de la política actual $\pi_{k-1}$, la actualización de la recompensa utiliza una mezcla de datos de las $N(k)$ políticas más recientes.

• Distribución de Mezcla: El algoritmo muestrea de una distribución de mezcla $d^{k-1, mix}_h = \sum_{n=1}^{N} \beta_n d^{k-n}_h$, donde $\beta_n$ son pesos uniformes.
• Objetivo: Los parámetros de la recompensa $\mu$ se actualizan mediante ascenso de gradiente proyectado para maximizar la pérdida $L(\pi^{k-1, mix}, \mu) = J(\pi_E, \mu) - \frac{1}{N}\sum_{n=1}^N J(\pi_{k-n}, \mu)$.
• Control de Error: El análisis teórico (Lema 4.2 y Teorema 4.3) demuestra que si las actualizaciones de la política son lo suficientemente pequeñas (controladas por el tamaño del paso $\sigma$), la divergencia entre la distribución de mezcla y la distribución de la política actual permanece acotada.

3. Marco Teórico

El regret del algoritmo AIL se descompone en regret de política y regret de recompensa (Lema 3.2). Los autores derivan límites para ambos:

• Regret de Política: Acotado por $\tilde{O}(\sqrt{H^4 S^2 A K})$ utilizando la actualización de descenso de espejo.
• Regret de Recompensa: Acotado por un término que comprende el regret estándar, un término de error inducido por las actualizaciones off-policy y un término de error de estimación (Teorema 4.4).
• Resultado Principal (Teorema 4.5): El regret total es sublineal con respecto al número de iteraciones $K$, siempre que el número de políticas reutilizadas $N(k)$ escale como $o(\sqrt{K})$. Específicamente, si $N$ es fijo, el escalamiento óptimo es $N^* = \tilde{O}((S/(HAB))^{1/3})$.

Contribuciones Clave

1. Garantías de Convergencia sin Corrección: El artículo proporciona las primeras garantías teóricas de convergencia para un algoritmo de AIL off-policy que no requiere técnicas de corrección off-policy (por ejemplo, muestreo de importancia).
2. Análisis de Eficiencia de Muestras: Los autores establecen que la reutilización de muestras de las $o(\sqrt{K})$ políticas más recientes no socava la convergencia. Demuestran que el error de desplazamiento de distribución es dominado por los beneficios de la mayor disponibilidad de datos, particularmente cuando el tamaño del espacio de estados ($S$) es grande en relación con el horizonte ($H$) y el espacio de acciones ($A$).
3. Validación Práctica: El algoritmo se valida tanto en tareas de espacio discreto MiniGrid como en benchmarks de espacio continuo de OpenAI Gym (MuJoCo), demostando que las variantes off-policy ($N > 1$) convergen más rápido y requieren menos muestras que sus contrapartes on-policy.

Resultados Experimentales

• MiniGrid (Discreto): En tareas de EmptyRoom de varios tamaños ($3\times3$, $5\times5$, $9\times9$), los algoritmos off-policy con $N=32$ lograron un rendimiento de nivel experto con aproximadamente 1,000 interacciones, mientras que el algoritmo on-policy ($N=1$) requirió el horizonte completo de 10,000 interacciones para converger. Los resultados confirmaron que los espacios de estados más grandes se benefician de un $N$ mayor.
• MuJoCo (Continuo): En las tareas HalfCheetah, Hopper y Walker2d, los algoritmos off-policy superaron consistentemente a la línea base on-policy. Aunque el $N$ óptimo varió entre entornos, se observaron ganancias significativas incluso con $N$ pequeños (por ejemplo, $N=4$ o $N=16$).
• Observación: Los experimentos respaldan la afirmación teórica de que el AIL off-policy puede lograr una eficiencia de muestras superior, aunque el número óptimo de políticas reutilizadas depende de las características específicas del entorno.

Significado y Reivindicaciones

El artículo afirma cerrar la brecha entre la comprensión teórica y la aplicación práctica del AIL off-policy. Mientras que trabajos anteriores demostraron el éxito práctico del AIL off-policy, carecían de pruebas rigurosas de convergencia. Este trabajo demuestra que:

• Soporte Teórico: Es posible garantizar la convergencia para el AIL off-policy simplemente controlando el desplazamiento de distribución mediante actualizaciones de política conservadoras y limitando el número de políticas reutilizadas.
• Eficiencia de Muestras: Se demuestra teóricamente que el "error" introducido por los datos off-policy es superado por los beneficios estadísticos de tener más datos, especialmente en espacios de estados de alta dimensión.
• Simplicidad: El método propuesto evita técnicas complejas de reducción de varianza como el muestreo de importancia, ofreciendo una alternativa más simple y teóricamente fundamentada que se alinea con las observaciones empíricas de la eficiencia de muestras en la práctica.

Los autores señalan modestamente que su análisis teórico asume configuraciones tabulares (extendidas a MDP lineales en el apéndice) y que el $N$ óptimo en entornos de aprendizaje profundo (MuJoCo) puede no alinearse perfectamente con los límites teóricos del peor de los casos debido a la parametrización de las redes neuronales, aunque las tendencias de rendimiento siguen siendo consistentes con la teoría.