Resumen Técnico: Q-Learning bajo el Criterio de Costo Promedio para MDPs Continuos

1. Formulación del Problema

Este artículo aborda el desafío de resolver Procesos de Decisión de Markov (MDP) con espacios de estados y acciones continuos bajo el criterio de costo promedio de horizonte infinito. El modelo se define mediante una tupla $(X, U, \mathcal{T}, c)$, donde $X$ y $U$ son espacios de Borel estándar (espacios métricos completos y separables), $\mathcal{T}$ es el núcleo de transición y $c$ es la función de costo. El objetivo es encontrar una política $\pi$ que minimice el costo promedio a largo plazo:
$$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$$

Los autores destacan que, si bien los problemas de horizonte finito y de costo descontado para espacios continuos están bien estudiados utilizando las propiedades de contracción de los operadores de Bellman, los problemas de costo promedio presentan dificultades únicas. Específicamente, la falta de un factor de descuento elimina la contracción inmediata del mapeo, lo que requiere supuestos alternativos de estabilidad y ergodicidad. Además, la literatura existente sobre aprendizaje por refuerzo (RL) de costo promedio se centra mayoritariamente en espacios finitos o impone supuestos estructurales restrictivos (por ejemplo, dinámicas lineales, políticas Lipschitz) que limitan su aplicabilidad a espacios continuos generales.

2. Metodología

El artículo emplea un enfoque de dos vertientes: aproximación finita mediante cuantización y algoritmos de aprendizaje por refuerzo diseñados para estas aproximaciones.

2.1 Discretización y Aproximación

La metodología central consiste en construir un MDP aproximado de estados y acciones finitos cuantizando los espacios continuos.

• Cuantización del Estado: El espacio de estados $X$ se particiona en contenedores disjuntos $\{B_i\}_{i=1}^M$ con estados representativos $y_i$. Se define una aplicación $q: X \to Y$ (donde $Y$ es el conjunto finito de representantes).
• Cuantización de la Acción: El espacio de acciones $U$ se aproxima mediante un conjunto finito $\Lambda$.
• Construcción del Modelo Aproximado: El modelo aproximado $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$ se define utilizando una medida de peso $\mu$ (frecuentemente la medida invariante del proceso de estado). Los núcleos de costo y transición aproximados son promedios de las funciones originales sobre los contenedores de cuantización:
  $$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$$
• Relajación de las Condiciones de Continuidad: Un cambio metodológico significativo es la relajación de la condición de continuidad de Variación Total (TV), que es estándar en la literatura de aproximación previa (por ejemplo, Saldi et al., 2018). Los autores establecen resultados de aproximación bajo:
  1. Continuidad Débil (Feller): Suficiente para la convergencia asintótica de los errores a medida que los tamaños de la rejilla se desvanecen.
  2. Continuidad de Wasserstein: Suficiente para establecer tasas de convergencia explícitas (límites de error) a medida que los tamaños de la rejilla se desvanecen.

2.2 Algoritmos de Aprendizaje por Refuerzo

El artículo propone algoritmos de Q-Learning Cuantizado para aprender la política óptima del modelo aproximado directamente a partir de los datos.

• Algoritmo Sincrónico (Algoritmo 1): Actualiza los valores Q para todos los pares estado-acción en la rejilla finita simultáneamente. Depende del muestreo de estados de cada contenedor según una medida predeterminada.
• Algoritmo Asincrónico (Algoritmo 2): Actualiza los valores Q basándose en una única trayectoria del proceso continuo original. Esto es más práctico pero introduce un término de ruido no markoviano porque el proceso cuantizado $q(X_t)$ no es una cadena de Markov (es un MDP parcialmente observable desde la perspectiva del estado cuantizado).
• Mecanismo de Convergencia: Para manejar el criterio de costo promedio y la falta de acotación en las iteraciones de Q (a diferencia de los casos descontados), los autores utilizan:
  • Semi-normas de Span para actualizaciones sincrónicas.
  • Supuestos de Ergodicidad: La política de exploración debe inducir una medida invariante única con soporte completo sobre los contenedores cuantizados.
  • Actualizaciones Desplazadas: El algoritmo asincrónico resta un valor de referencia (basado en un contenedor específico) para estabilizar la iteración, tratando el proceso cuantizado como un POMDP.

3. Contribuciones Clave

El artículo realiza tres contribuciones principales, avanzando en el estado del arte del control de espacios continuos con costo promedio:

1. Teoría de Aproximación con Condiciones más Débiles:

   • Los autores proporcionan límites de error para aproximaciones finitas bajo continuidad débil y continuidad de Wasserstein, relajando la estricta continuidad de Variación Total requerida por trabajos previos (por ejemplo, Saldi et al., 2018).
   • Establecen que, bajo continuidad de Wasserstein (con una constante de contracción $K_T < 1$), el error en el costo promedio óptimo decae a una tasa proporcional al error de cuantización (específicamente $L_X^\delta$).
   • Bajo continuidad débil únicamente, demuestran la convergencia asintótica del costo de la política aproximada al costo óptimo a medida que la discretización se vuelve más fina.

2. Convergencia de Q-Learning Cuantizado:

   • El artículo establece la convergencia casi segura de los algoritmos de Q-learning sincrónico y asincrónico para espacios continuos.
   • Crucialmente, demuestra que estos algoritmos convergen a los valores Q óptimos del modelo finito aproximado construido, no solo al modelo continuo original. Esta distinción es vital porque el proceso cuantizado no es estrictamente markoviano.
   • El análisis generaliza resultados previos (por ejemplo, Kara y Yüksel, 2023) de costos descontados al más desafiante criterio de costo promedio, requiriendo un nuevo análisis técnico para manejar iteraciones de Q no acotadas.

3. Garantías de Cuasi-Optimalidad:

   • Al combinar los límites de error de aproximación con la convergencia de los algoritmos de aprendizaje, el artículo demuestra que las políticas aprendidas mediante Q-learning cuantizado son cuasi-óptimas para el MDP continuo original.
   • La pérdida de rendimiento está explícitamente acotada en términos de la resolución de cuantización y las constantes de Lipschitz de las funciones de costo y de transición.

4. Resultados y Teoremas Clave

• Teorema 1 y 2 (Límites de Aproximación): Establecen límites superiores en la diferencia entre el costo promedio óptimo del modelo original ($\rho$) y el modelo aproximado ($\hat{\rho}$).
  • Bajo continuidad de Wasserstein: $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$, donde $L_X$ es el error de cuantización.
  • Bajo continuidad débil: $\lim_{n \to \infty} \rho(\pi_n) = \rho$.
• Teorema 5 y 6 (Convergencia del Algoritmo): Prueban que las iteraciones de Q-learning sincrónico y asincrónico convergen a los valores Q óptimos del modelo finito aproximado. La convergencia asincrónica depende de la ergodicidad del proceso de estado bajo la política de exploración.
• Corolario 1: Combina los resultados de aproximación y aprendizaje para mostrar que la política aprendida $\hat{\pi}$ satisface $\rho(\hat{\pi}) - \rho \leq \epsilon$, donde $\epsilon$ se desvanece a medida que el tamaño de la rejilla de discretización tiende a cero.

5. Significado y Pretensiones

Los autores posicionan este trabajo como una solución a problemas abiertos en la literatura sobre aprendizaje por refuerzo para MDP de costo promedio con espacios continuos.

• Relajación de Supuestos: El artículo reclama un avance teórico significativo al alejarse de la continuidad de Variación Total, que suele ser demasiado restrictiva para modelos prácticos, hacia la continuidad Débil y de Wasserstein. Esto amplía la clase de sistemas (por ejemplo, aquellos con ruido aditivo o dinámicas específicas) para los cuales se pueden proporcionar garantías teóricas.
• Puente entre Teoría y Práctica: Al demostrar que el Q-learning converge a la solución de una aproximación finita bien definida, el artículo proporciona una justificación rigurosa para el uso de RL basado en discretización en entornos de costo promedio continuos. Clarifica que la "cuasi-optimalidad" es una consecuencia directa de la calidad de la aproximación, no un artefacto del algoritmo de aprendizaje.
• Manejo de la Cuantización No-Markoviana: El artículo aborda explícitamente la dificultad técnica de que el proceso de estado cuantizado es un POMDP, no un MDP, y proporciona una prueba de convergencia para el aprendizaje asincrónico en este entorno bajo el criterio de costo promedio, un vacío previamente señalado en la literatura (por ejemplo, Wan et al., 2021).

El artículo concluye con un estudio de caso numérico sobre un problema de control continuo, demostrando la convergencia de las funciones de valor y la reducción del arrepentimiento (regret) a medida que aumenta la tasa de cuantización, validando los límites teóricos.