Teoremas del Límite Central para Q-Learning Promediado Asincrónico

Información Básica

• ID del Artículo: 2509.18964
• Título: Central Limit Theorems for Asynchronous Averaged Q-Learning
• Autor: Xingtu Liu (Simon Fraser University)
• Clasificación: cs.LG math.OC stat.ML
• Conferencia de Publicación: OPT2025: 17th Annual Workshop on Optimization for Machine Learning
• Enlace del Artículo: https://arxiv.org/abs/2509.18964

Resumen

Este artículo establece teoremas del límite central para el Q-learning promediado de Polyak-Ruppert bajo actualizaciones asincrónicas. El artículo demuestra un teorema del límite central no asintótico, cuya tasa de convergencia en la distancia de Wasserstein refleja explícitamente la dependencia del número de iteraciones, el tamaño del espacio de estados-acciones, el factor de descuento y la calidad de exploración. Además, se deriva un teorema del límite central funcional, demostrando que el proceso de sumas parciales converge débilmente a un movimiento browniano.

Antecedentes de Investigación y Motivación

Contexto del Problema

1. Importancia del Q-Learning: El Q-learning es uno de los algoritmos más ampliamente utilizados en aprendizaje por refuerzo, aprendiendo directamente de trayectorias empíricas la función de valor de acción óptima, logrando éxitos significativos en juegos de Atari, Go, manipulación robótica y alineación de modelos de lenguaje grande.
2. Desafíos en el Análisis Teórico:
   • El Q-learning puede interpretarse como una instancia de aproximación estocástica (SA), pero el Q-learning asincrónico es un problema de SA no lineal con ruido markoviano
   • En comparación con SA lineal y aprendizaje TD, el análisis del Q-learning es más desafiante debido a sus características no lineales, operadores no suaves y procesos no estacionarios
   • Las actualizaciones asincrónicas introducen además ruido markoviano, aumentando la complejidad del análisis
3. Limitaciones del Trabajo Existente:
   • Trabajos previos han establecido el TLC funcional para Q-learning sincrónico, pero el Q-learning sincrónico solo considera ruido de martingala
   • Zhang y Xie (2024) establecieron un TLC funcional para Q-learning asincrónico con tamaño de paso constante, pero el tamaño de paso constante no satisface las condiciones necesarias para establecer un TLC no asintótico
   • Actualmente no existe un TLC no asintótico para Q-learning, incluso en configuraciones sincrónicas

Motivación de la Investigación

Establecer teoremas del límite central es crucial para comprender las propiedades estadísticas de los algoritmos. Esta normalidad asintótica tiene importancia significativa para la cuantificación de incertidumbre e inferencia estadística en aprendizaje por refuerzo.

Contribuciones Principales

1. Primer TLC No Asintótico para Q-Learning: Se demuestra el teorema del límite central no asintótico para Q-learning promediado asincrónico, con tasa de convergencia $\tilde{O}((|S||A|)^{1/2}K^{-1/6}\rho^{-2}(1-\gamma)^{-3})$
2. Teorema del Límite Central Funcional: Se establece el TLC funcional para Q-learning asincrónico con tamaño de paso decreciente, mostrando que el proceso de sumas parciales converge débilmente a un movimiento browniano
3. Dependencias Explícitas: La tasa de convergencia refleja explícitamente la dependencia del número de iteraciones K, el tamaño del espacio de estados-acciones |S||A|, el factor de descuento γ y la calidad de exploración ρ
4. Innovación Técnica: Se resuelven los desafíos analíticos derivados de la no linealidad, ruido markoviano y operadores no suaves

Detalles de la Metodología

Definición de la Tarea

Se considera un proceso de decisión de Markov (MDP) de horizonte infinito con descuento $M = \langle S, A, P, r, \gamma \rangle$, donde:

• $S$: conjunto de estados
• $A$: conjunto de acciones
• $P: S \times A \rightarrow \Delta_S$: función de probabilidad de transición
• $\gamma \in [0,1)$: factor de descuento

El objetivo es aprender la función Q óptima $Q^* = \max_\pi Q^\pi$.

Algoritmo de Q-Learning Asincrónico

El Q-learning asincrónico mantiene un estimador de función Q $Q_k$, con regla de actualización: $Q_{k+1} = Q_k + \alpha_k(F_k - Q_k)$

donde:

• $F_k = F(Q_k, y_k)$, $y_k = (s_k, a_k, s_{k+1})$
• $[F(Q_k, s_k, a_k, s_{k+1})](s,a) = \mathbf{1}_{\{(s_k,a_k)=(s,a)\}}\Gamma(Q_k, s_k, a_k, s_{k+1}) + Q_k(s,a)$
• $\Gamma(Q_k, s_k, a_k, s_{k+1}) = r_k(s_k, a_k) + \gamma\max_a Q_k(s_{k+1}, a) - Q_k(s_k, a_k)$

Supuestos Clave

Supuesto 1: Existe una política óptima $\pi^*$ tal que para $Q \in \mathbb{R}^{|S|\times|A|}$: $\|(P^\pi - P^{\pi^*})(Q-Q^*)\|_\infty \leq L\|Q-Q^*\|_2^\infty$

Supuesto 2: $\{y_k\}_{k \geq 0}$ es una cadena de Markov de estado finito irreducible y aperiódica.

Selección del Tamaño de Paso

Se elige un tamaño de paso polinomial $\alpha_k = \alpha(k+b)^{-\beta}$, donde $\alpha, b > 0$, $\beta \in (0.5, 1)$.

Las razones para esta selección:

1. Satisface las condiciones clave del esquema de promediado de Polyak-Juditsky
2. El tamaño de paso constante viola las condiciones (i) y (iii), el tamaño de paso lineal viola la condición (ii)
3. El tamaño de paso polinomial satisface todas las condiciones necesarias

Resultados Teóricos Principales

Teorema del Límite Central No Asintótico

Teorema 4: Bajo los Supuestos 1 y 2, se tiene: $W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, \tilde{N}\right) \leq \frac{(|S||A|)^{1/2}}{\rho(1-\gamma)^2K^{1/2}} \cdot \tilde{O}\left((\rho(1-\gamma))^{\frac{\beta-2}{1-\beta}} + K^{\beta/2}\rho^{-1}(1-\gamma)^{-1} + K^{1-\beta} + K^{\frac{1-\beta}{2}}\rho^{-1-\beta}(1-\gamma)^{-\beta}\right)$

donde $\Delta_k = Q_k - Q^*$, $\tilde{N} = (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)$.

Corolario 5: Cuando $\beta = 2/3$, la tasa de convergencia se simplifica a: $W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)\right) \leq \tilde{O}\left(\frac{(|S||A|)^{1/2}}{K^{1/6}\rho^2(1-\gamma)^3}\right)$

Teorema del Límite Central Funcional

Teorema 6: Bajo la configuración del Teorema 4, el proceso de sumas parciales $\Phi_K(\zeta) = K^{-1/2}\sum_{k=1}^{\lfloor\zeta K\rfloor}\Delta_k$ converge débilmente en $D[0,1]$ a $(A^{-1}\Sigma A^{-\top})^{1/2}B(\cdot)$, donde $B(\cdot)$ es un movimiento browniano estándar.

Innovación Técnica y Estrategia de Demostración

Desafíos Técnicos Principales

1. No Linealidad: El Q-learning es SA no lineal, más complejo que SA lineal
2. Ruido Markoviano: Las actualizaciones asincrónicas introducen ruido markoviano no independiente e idénticamente distribuido
3. Operadores No Suaves: El operador de Bellman empírico en Q-learning asincrónico es no suave

Estrategia de Demostración

1. Técnica de Cotas Superior e Inferior: Se introducen secuencias de cota superior $\Delta_k^{\uparrow}$ y cota inferior $\Delta_k^{\downarrow}$, utilizando el teorema del sándwich
2. Descomposición de Términos: Se descompone $\sum_{k=1}^K \Delta_k$ en 6 términos:
   • Término (1): término de error inicial
   • Término (2): término de error no lineal
   • Término (3): término de ruido markoviano
   • Términos (4-5): términos de corrección de orden superior
   • Término (6): secuencia de diferencias de martingala
3. Técnica de Ecuación de Poisson: Se transforma el ruido markoviano en una secuencia de diferencias de martingala
4. Teorema del Límite Central de Martingala: Se aplica el TLC de martingala no asintótico de Srikant (2024)

Trabajo Relacionado

Teoría de Aproximación Estocástica

• Polyak y Juditsky (1992): Técnica clásica de reducción de varianza mediante promediado
• Anastasiou et al. (2019): TLC no asintótico para SGD promediado de Polyak-Ruppert
• Mou et al. (2020): TLC no asintótico para SA lineal

TLC en Aprendizaje por Refuerzo

• Xie y Zhang (2022), Li et al. (2023): TLC funcional para Q-learning sincrónico
• Zhang y Xie (2024): TLC funcional para Q-learning asincrónico con tamaño de paso constante
• Srikant (2024), Samsonov et al. (2024): TLC no asintótico para aprendizaje TD

Conclusiones y Discusión

Conclusiones Principales

1. Se establece el primer TLC no asintótico para Q-learning, con tasa de convergencia que depende explícitamente de parámetros del problema
2. Se demuestra la convergencia débil del proceso de sumas parciales de Q-learning asincrónico
3. Se proporciona una base teórica para la cuantificación de incertidumbre en aprendizaje por refuerzo

Limitaciones

1. Se requieren supuestos de Lipschitz relativamente fuertes (Supuesto 1)
2. Solo se considera espacio de estados-acciones finito
3. La tasa de convergencia podría no ser óptima

Direcciones Futuras

1. Mejorar la tasa de convergencia
2. Extender a otras métricas más allá de la distancia 1-Wasserstein
3. Considerar configuraciones con aproximación de funciones

Evaluación Profunda

Fortalezas

1. Contribución Teórica Significativa: Primer TLC no asintótico para Q-learning, llenando un vacío teórico importante
2. Innovación Técnica: Combinación ingeniosa de técnicas de cotas superior e inferior, ecuación de Poisson y TLC de martingala para resolver desafíos técnicos
3. Resultados Completos: Se proporcionan tanto TLC no asintótico como funcional
4. Dependencias Explícitas: La tasa de convergencia refleja explícitamente el impacto de cada parámetro

Deficiencias

1. Supuestos Fuertes: El supuesto de Lipschitz puede ser difícil de verificar en la práctica
2. Tasa de Convergencia: La tasa de convergencia $K^{-1/6}$ es relativamente lenta
3. Estado Finito: No se consideran espacios de estado continuo o aproximación de funciones

Impacto

1. Valor Teórico: Proporciona nuevas herramientas y perspectivas para el análisis teórico del Q-learning
2. Significado Práctico: Sienta las bases teóricas para la cuantificación de incertidumbre en algoritmos de aprendizaje por refuerzo
3. Metodología: Las técnicas de demostración pueden generalizarse a otros problemas de SA no lineal

Escenarios Aplicables

1. Análisis teórico de problemas de aprendizaje por refuerzo tabular
2. Investigación de convergencia de algoritmos con actualizaciones asincrónicas
3. Inferencia estadística y construcción de intervalos de confianza en aprendizaje por refuerzo

Referencias

• Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging.
• Xie, C. and Zhang, Z. (2022). A statistical online inference approach in averaged stochastic approximation.
• Zhang, Y. and Xie, Q. (2024). Constant stepsize q-learning: Distributional convergence, bias and extrapolation.