Achieving $\epsilon^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Resumen Técnico: Logro de una complejidad de muestra $\tilde{O}(\epsilon^{-2})$ para Actor-Critic de bucle único bajo supuestos mínimos

Planteamiento del Problema
El aprendizaje por refuerzo (RL) busca resolver Procesos de Decisión de Markov (MDP) mediante métodos basados en datos. Si bien los métodos en el espacio de valores, como Q-learning, han establecido una complejidad de muestra $\tilde{O}(\epsilon^{-2})$ bajo supuestos mínimos (específicamente, la existencia de una política de comportamiento irreducible), los métodos en el espacio de políticas, como actor-critic, han quedado históricamente rezagados en cuanto a garantías teóricas. Los análisis existentes de actor-critic que logran una complejidad $\tilde{O}(\epsilon^{-2})$ dependen típicamente de dos condiciones restrictivas:

1. Implementaciones de bucles anidados: Donde el crítico se actualiza múltiples veces mientras el actor permanece fijo, una estructura distinta a los algoritmos prácticos de bucle único.
2. Supuestos fuertes y dependientes del algoritmo: Como requerir que todas las políticas encontradas durante la trayectoria del algoritmo (o toda la clase de políticas) induzcan cadenas de Markov irreducibles y aperiódicas con tasas de mezcla y propiedades de exploración uniformemente acotadas.

Estos supuestos crean una dependencia circular: verificar las propiedades de mezcla requiere controlar la secuencia de políticas generada por el algoritmo, que es precisamente el objeto del análisis de convergencia. Además, los algoritmos prácticos de actor-critic operan de manera de bucle único y escala de tiempo única con aprendizaje fuera de política, donde el crítico rastrea una política objetivo que varía en el tiempo. Esto introduce desafíos relacionados con ecuaciones de actualización acopladas e iterados potencialmente no acotados debido al muestreo por importancia, problemas que los marcos teóricos existentes tienen dificultades para abordar sin supuestos fuertes.

Metodología
Los autores proponen un algoritmo actor-critic fuera de política, de bucle único y escala de tiempo única, donde el actor y el crítico se actualizan simultáneamente en cada iteración. El actor emplea actualizaciones incrementales hacia una política objetivo $\tilde{\pi}_t$ derivada mediante iteración de políticas aproximada (API) o gradiente de política natural (NPG), mientras que el crítico realiza aprendizaje de diferencias temporales (TD) fuera de política. Los autores consideran dos variantes del crítico:

• Muestreo por Importancia (IS): Corrige el desajuste de distribución utilizando una razón de pesos de importancia.
• Diferencia Temporal Esperada (ETD): Calcula directamente la función Q esperada en el siguiente estado, evitando pesos de importancia explícitos.

La innovación técnica central reside en el marco de análisis. Para manejar el acoplamiento entre las actualizaciones del actor y el crítico y la naturaleza no acotada de los iterados fuera de política, los autores emplean un marco de deriva de Lyapunov acoplado.

1. Funciones de Lyapunov: Construyen funciones de Lyapunov separadas para el actor ($V_t = \|Q^* - Q_{\pi_t}\|_\infty^2$) y para el crítico ($W_t = \|Q_t - Q_{\pi_t}\|_\nu^2$).
2. Desigualdades de Deriva: Establecen desigualdades de deriva negativa para ambas funciones. Crucialmente, estas desigualdades contienen términos cruzados que representan el error del sistema acoplado (por ejemplo, el error del crítico apareciendo en la deriva del actor y viceversa).
3. Dominio Cruzado: El análisis se basa en una propiedad de "dominio cruzado". Mediante la selección cuidadosa de las relaciones de tamaño de paso y asegurando que los términos de error de acoplamiento estén dominados por los términos de deriva negativa de los sistemas respectivos, los autores combinan las dos desigualdades de deriva en una sola recursión para $V_t + W_t$. Este enfoque se inspira en la teoría de ganancia pequeña en sistemas dinámicos, pero se adapta aquí para manejar ruido markoviano, objetivos variables en el tiempo e iterados no acotados de manera unificada.

Contribuciones y Resultados Clave
El artículo establece las primeras tasas de convergencia de última iteración para un algoritmo actor-critic de bucle único que logra una complejidad de muestra $\tilde{O}(\epsilon^{-2})$ bajo supuestos mínimos.

• Supuestos Mínimos: El único supuesto requerido es la existencia de una política que induzca una cadena de Markov irreducible sobre el espacio de estados. Esta política no necesita ser visitada por el algoritmo, ni el algoritmo necesita controlar las propiedades de mezcla de las políticas que genera. Esto contrasta con trabajos anteriores que requerían ergodicidad uniforme a lo largo de la trayectoria o de toda la clase de políticas.
• Complejidad de Muestra: Bajo este supuesto mínimo, el algoritmo logra una complejidad de muestra $\tilde{O}(\epsilon^{-2})$ para encontrar una política $\epsilon$-óptima. Esta tasa es casi minimax óptima con respecto a $\epsilon$.
• Esquemas de Tamaño de Paso: Los resultados se mantienen para secuencias de tamaño de paso constantes, armónicas y polinómicas. Específicamente, el uso de tamaños de paso armónicos con parámetros apropiados produce la tasa óptima.
• Variantes del Algoritmo: El análisis cubre tanto a críticos basados en IS como a los basados en ETD. Si bien ambos logran el mismo orden de complejidad, la variante ETD exhibe una dependencia más suave con los parámetros del problema (tamaño del espacio de estados $n$, tamaño del espacio de acciones $m$ y factor de descuento $\gamma$) porque evita la estocasticidad adicional introducida por las razones de muestreo por importancia.
• Iterados No Acotados: El marco maneja con éxito los iterados potencialmente no acotados inducidos por el aprendizaje fuera de política (particularmente con IS), un desafío que a menudo requería supuestos fuertes de acotación en la literatura anterior.

Significado y Afirmaciones
Los autores afirman que este trabajo cierra una brecha teórica significativa entre los métodos en el espacio de valores y los métodos en el espacio de políticas. Al demostrar que los métodos actor-critic pueden lograr una complejidad de muestra minimax óptima sin bucles anidados ni supuestos fuertes de mezcla dependientes del algoritmo, el artículo desafía la noción de que los métodos en el espacio de políticas son inherentemente menos eficientes en muestras o requieren condiciones más fuertes.

El marco analítico basado en la deriva de Lyapunov acoplada y el dominio cruzado se presenta como una contribución de interés independiente, potencialmente aplicable a otros algoritmos iterativos acoplados con iterados no acotados. El artículo señala explícitamente que, aunque la dependencia de $\epsilon$ es casi óptima, la dependencia de las constantes específicas del problema ($n, m, (1-\gamma)^{-1}$) puede ser subóptima en comparación con los métodos basados en valores, lo que sugiere que las técnicas de reducción de varianza podrían ser una dirección para mejoras futuras. El trabajo evita hacer afirmaciones sobre configuraciones de aproximación de funciones (el "triángulo mortal") o aplicaciones empíricas específicas, centrándose estrictamente en el entorno tabular y en las garantías teóricas.