A Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning

Resumen Técnico: Una Teoría de Iteraciones Finitas para el Aprendizaje Temporal-Diferencial Distribuido Categórico Asíncrono

Enunciado del Problema
Los avances recientes en el aprendizaje por refuerzo (RL) distribuido han establecido garantías asintóticas sólidas para los métodos de evaluación de políticas categóricas, específicamente el aprendizaje temporal-diferencial categórico (CTD) escalar en la métrica de Cramér y el aprendizaje temporal-diferencial categórico firmado multivariado (MTD) en la métrica de discrepancia media máxima (MMD). Sin embargo, los análisis no asintóticos (de iteraciones finitas) existentes se centran en gran medida en actualizaciones de estado completo síncronas, modelos generativos o sustitutos idealizados. En los entornos de RL en línea prácticos, el aprendizaje TD categórico estándar opera de forma asíncrona: realiza actualizaciones de un solo estado en cada iteración impulsadas por una trayectoria markoviana. Esto crea una brecha teórica entre la teoría asintótica establecida y el comportamiento de iteraciones finitas de las recursiones exactas utilizadas en la práctica. Este artículo aborda esta brecha proporcionando garantías de iteraciones finitas para CTD y MTD asíncronos bajo regímenes de horizonte fijo con y sin descuento.

Metodología
Los autores cierran la brecha entre las actualizaciones asíncronas prácticas y la teoría de aproximación estocástica (SA) de iteraciones finitas mediante un marco unificado basado en incrustaciones isométricas estado a estado y geometría de supremo por bloques.

1. Incrustaciones Isométricas y Contracción:

   • Para CTD, los autores utilizan la métrica de Cramér y una incrustación isométrica de masa acumulada ($I_C$). Esto transforma el operador de Bellman proyectado en una contracción en una norma de supremo por bloques ($\|\cdot\|_{2,\infty}$) con módulo $\sqrt{\gamma}$ (con descuento) o una contracción ponderada (horizonte fijo).
   • Para MTD, emplean la métrica MMD con un núcleo característico y una incrustación de matriz de Gram ($I_M$). Esto convierte de manera similar el mapa de Bellman proyectado en una contracción en la geometría MMD de supremo por bloques, con módulo $\gamma^{c/2}$ (con descuento) o una contracción ponderada (horizonte fijo).

2. Formulación de Aproximación Estocástica (SA) Asíncrona:

   • La regla estándar de actualización de un solo estado se reinterpreta como una recursión SA asíncrona: $U_{k+1} = U_k + \alpha_k P_{S_k}(\hat{T}(U_k; S_k, \xi_k) - U_k(S_k))$.
   • El análisis se basa en marcos abstractos de iteraciones finitas para recursiones contractivas bajo muestreo i.i.d. y markoviano (construyendo sobre Chen et al., Robbins-Monro y Borkar).
   • Geometría de Perturbación: Se establece una distinción crítica entre las estructuras de ruido de ambos métodos. CTD opera en un régimen de ruido acotado debido al soporte acotado de las distribuciones categóricas y la geometría de Cramér. En contraste, MTD opera en un régimen de perturbación afín porque la proyección categórica firmada es afín en lugar de uniformemente acotada, lo que conduce a límites de perturbación que escalan con la norma de la iteración actual.

3. Regímenes Analizados:

   • Evaluación de Políticas con Descuento: Analizada bajo muestreo i.i.d. (reproducción/modelo generativo) y muestreo de trayectorias markovianas (RL en línea estándar). El caso markoviano incorpora límites de tiempo de mezcla geométrica.
   • Evaluación de Horizonte Fijo sin Descuento: Analizada para tareas episódicas con un horizonte fijo $H$. Dado que no hay un factor de descuento $\gamma < 1$ que impulse la contracción, los autores introducen una métrica de bloques ponderada ($\lambda^h$) a través de la pila del horizonte. Esto recupera una propiedad de contracción donde el horizonte $h$ se basa en $h-1$. El análisis se realiza en los límites de los episodios para manejar la deriva dependiente de la fase dentro de un episodio.

Contribuciones Clave

1. Garantías de Iteraciones Finitas para CTD y MTD Asíncronos: El artículo establece tasas de convergencia no asintóticas explícitas para las recursiones asíncronas estándar de CTD y MTD. Esta es la primera teoría de este tipo para estos métodos específicos bajo actualizaciones de un solo estado impulsadas por trayectorias.
2. Marco Unificado para Entornos con Descuento y de Horizonte Fijo: Los autores proporcionan un tratamiento teórico coherente que cubre tanto problemas con descuento (con muestreo i.i.d. y markoviano) como problemas de horizonte fijo sin descuento (bajo muestreo episódico i.i.d.).
3. Descomposición Determinista del Error de Representación: El artículo registra una descomposición que separa el error total en un término algorítmico (controlado por los límites de iteraciones finitas) y un término de sesgo de proyección determinista (dependiente de la familia de soporte categórico). Esto permite analizar el análisis SA y el sesgo de discretización de forma independiente.
4. Constantes Explícitas y Regímenes de Tamaño de Paso: El análisis proporciona constantes explícitas para tres regímenes de tamaño de paso:
   • Tamaño de paso constante: Convergencia geométrica a una vecindad de $O(\alpha)$.
   • Tamaño de paso decreciente linealmente: Decaimiento residual de $O(1/k)$ (error cuadrático), lo que implica una complejidad de muestra de $O(\epsilon^{-2})$ para un error medio $\epsilon$.
   • Tamaño de paso decreciente polinomialmente: Decaimiento de $O(1/k^z)$, intercambiando la tasa de convergencia por condiciones de admisibilidad más suaves.

Resultados

• Régimen con Descuento: Tanto para CTD como para MTD, bajo muestreo i.i.d., el error cuadrático converge a una tasa de $O(1/k)$ con tamaños de paso decrecientes linealmente. Bajo muestreo markoviano, la tasa es $\tilde{O}(1/k)$, incurriendo en una sobrecarga logarítmica debido al tiempo de mezcla de la cadena de Markov subyacente.
• Régimen de Horizonte Fijo: Para tareas episódicas sin descuento, el error en los límites de los episodios converge a tasas análogas al caso con descuento. Específicamente, convergencia de $O(1/m)$ para el error cuadrático después de $m$ episodios (equivalente a $O(\epsilon^{-2})$ transiciones).
• Régimenes de Ruido: Los resultados confirman que CTD se beneficia del ruido uniformemente acotado, mientras que MTD requiere manejar límites de ruido afines, lo que introduce constantes adicionales relacionadas con la norma de la iteración en las garantías de convergencia.

Significado y Afirmaciones
El artículo afirma cerrar una brecha teórica significativa entre la comprensión asintótica del RL distribuido y las actualizaciones asíncronas de un solo estado prácticas utilizadas en las implementaciones. Al demostrar que las recursiones categóricas estándar constituyen esquemas SA asíncronos con estructuras contractivas en incrustaciones adecuadas, los autores habilitan un control riguroso de iteraciones finitas.

Los autores notan modestamente el alcance de su trabajo:

• La teoría se limita a la evaluación de políticas tabular y de estado finito y no aborda el control ni la mejora de políticas.
• Las garantías son límites de esperanza en lugar de límites de alta probabilidad.
• Los resultados se aplican a las recursiones asíncronas exactas utilizadas en la práctica, distinguiéndolas de trabajos anteriores que analizaron sustitutos síncronos o basados en modelos.

El trabajo establece que una vez que CTD y MTD se formulan con las incrustaciones estado a estado apropiadas, sus reglas de actualización poseen las propiedades estructurales necesarias (contracción, continuidad Lipschitz y perturbación controlada) para ser analizadas utilizando herramientas modernas de SA no asintótica, proporcionando la primera teoría de iteraciones finitas para estos métodos distribuidos ampliamente utilizados en entornos en línea realistas.