Heavy-Ball Q-Learning with Residual Weighting Correction

Resumen Técnico: Q-Learning de Bola Pesada con Corrección de Ponderación Residual

Planteamiento del Problema
El Q-learning es un método fundamental en el aprendizaje por refuerzo (RL) para aprender funciones Q óptimas sin un modelo de transición explícito. Si bien el Q-learning estándar converge basándose en la propiedad de contracción del operador de optimalidad de Bellman, esta contracción puede ser débil cuando el factor de descuento $\gamma$ está cerca de uno, lo que conduce a una convergencia lenta. Los métodos de aceleración existentes, como las actualizaciones basadas en momentum, las iteraciones de tipo PID y las correcciones de rango uno, a menudo carecen de garantías teóricas rigurosas de que superen al Q-learning estándar, particularmente en entornos de control donde la política greedy activa cambia dinámicamente. Un desafío específico surge al aplicar el momentum de bola pesada (heavy-ball momentum) al Q-learning con pesos de muestreo no uniformes: la matriz de ponderación estándar destruye la propiedad del "autovector común" (específicamente el vector de unos) requerida para ciertos análisis espectrales, lo que dificulta certificar la aceleración teóricamente.

Metodología
El artículo propone un método de Q-Learning de Bola Pesada Corregido (HBCQL) y establece sus propiedades de convergencia y aceleración utilizando un marco de Sistemas Lineales Conmutados (SLS).

1. Corrección de Ponderación Residual (CQL):
   Los autores introducen primero una actualización de Q-learning "corregida" (Algoritmo 2) para abordar la pérdida del autovector común en el Q-learning ponderado estándar. Reemplazan la matriz de muestreo diagonal estándar $D$ con una matriz de corrección $H = \delta \Pi_d + D(I - \Pi_d)$, donde $\Pi_d = \mathbf{1}d^\top$. Esta matriz $H$ está diseñada para que mapee el vector constante $\mathbf{1}$ a un múltiplo escalar de sí mismo ($H\mathbf{1} = \delta\mathbf{1}$), restaurando así un autovector común para la dinámica media del algoritmo. Esta corrección preserva el punto fijo $Q^\star$ al tiempo que permite una descomposición estructural específica.

2. Momentum de Bola Pesada (Heavy-Ball Momentum):
   El método extiende el Q-learning corregido añadiendo un término de momentum de bola pesada $\eta(Q_k - Q_{k-1})$ (Algoritmo 3). Esto transforma la recursión de primer orden en un sistema de segundo orden.

3. Análisis de SLS y Radio Espectral Conjunto (JSR):
   La herramienta analítica central es la representación de la dinámica del error del Q-learning como un Sistema Lineal Conmutado. La señal de conmutación está determinada por la selección de la acción greedy en el operador de Bellman. La tasa de convergencia se caracteriza mediante el Radio Espectral Conjunto (Jside JSR) de la familia de matrices de conmutación asociada.

   • Descomposición: Los autores descomponen el espacio de estados en el subespacio generado por el autovector común (o el subespacio invariante en el caso de la bola pesada) y su complemento ortogonal.
   • Mecanismo de Aceleración: El análisis muestra que el JSR del sistema completo es el máximo entre el JSR del sistema proyectado (ortogonal a la dirección común) y el radio espectral de la dinámica a lo largo de la dirección común. La matriz de corrección $H$ permite que la dinámica a lo largo de la dirección común se sintonice de forma independiente mediante el parámetro $\delta$. Se demuestra entonces que el término de bola pesada $\eta$ acelera la convergencia a lo largo de esta dirección específica sin afectar negativamente las dinámicas proyectadas, siempre que $\eta$ sea suficientemente pequeño.

4. Extensión a la Aproximación de Función Lineal:
   El marco se extiende a la aproximación de función lineal (LQL). Se construye una matriz de corrección $G$ similar en el espacio de características para asegurar la existencia de una dirección de autovector común (generada por un vector $c$ tal que $\Phi c = \mathbf{1}$). El mismo análisis de SLS y JSR produce resultados de convergencia y aceleración análogos.

Contribuciones Clave

• Q-Learning Corregido (CQL): La propuesta de una corrección estructural a la actualización de Q-learning que restaura la propiedad del autovector común para el muestreo no uniforme, permitiendo un análisis espectral riguroso.
• Garantía de Aceleración Teórica: La derivación de condiciones suficientes (Suposiciones 4.1, 4.2 y 5.1) bajo las cuales el método HBCQL tiene un JSR estrictamente menor que tanto el Q-learning estándar como el Q-learning corregido (sin momentum). Esto proporciona una "tasa certificada" de aceleración en una dirección analíticamente identificable específica.
• Marco SLS/JSR: La aplicación de Sistemas Lineales Conmutados y el análisis del Radio Espectral Conjunto al Q-learning, ofreciendo una perspectiva complementaria a los argumentos de contracción estándar. Este enfoque maneja explícitamente la naturaleza de conmutación de la política greedy.
• Extensión a la Aproximación de Funciones: Generalización de la teoría de corrección y aceleración al entorno de la aproximación de funciones lineales.

Resultados

• Convergencia: El artículo demuestra que, bajo las suposiciones establecidas, la recursión del error converge uniformemente de forma exponencial a cero (o a un vecindario de ruido en el caso estocástico) con una tasa limitada por el JSR.
• Aceleración: El análisis teórico (Teorema 5.1 y 10.1) demuestra que para parámetros de momentum $\eta$ pequeños, el JSR del sistema corregido de bola pesada es estrictamente menor que el del baseline estándar o corregido.
• Ilustraciones Numéricas:
  • En un entorno tabular determinista, el HBCQL alcanzó un umbral de error relativo significativamente más rápido que el CQL.
  • En un entorno tabular estocástico, el HBCQL redujo el tiempo de la mediana para alcanzar un umbral de error específico en comparación con tanto el Q-learning estándar como el CQL.
  • En entornos de aproximación de función lineal (tanto deterministas como estocásticos), el método corregido de bola pesada (HBCLQL) superó consistentemente a los métodos de Q-learning lineal estándar y corregidos en términos de velocidad de convergencia.

Significancia y Reivindicaciones
El artículo afirma proporcionar un certificado preciso de aceleración en una dirección analíticamente identificable (la dirección del autovector común), en lugar de un teorema de aceleración para todas las direcciones. Los autores enfatizan que la contribución es una garantía teórica para una dirección geométrica específica, lo que ofrece una nueva perspectiva sobre la geometría del Q-learning de bola pesada.

El trabajo se distingue de la literatura existente sobre momentum por:

1. Centrarse en el entorno de control (donde la política cambia) en lugar de solo en la evaluación de la política.
2. Utilizar SLS y JSR en lugar de argumentos de política fija o límites de aproximación estocástica por sí solos.
3. Proporcionar una corrección estructural que hace que el análisis de aceleración sea tratable para el muestreo no uniforme, un escenario donde el Q-learning de bola pesada estándar carece de un autovector común.

Los autores señalan que la garantía de aceleración es condicional a la suposición de la "brecha proyectada" (que las dinámicas proyectadas son más rápidas que las dinámicas de la dirección común) y a parámetros de momentum pequeños. No pretenden una aceleración universal para todos los parámetros o todos los MDP, sino que identifican un régimen donde el método es teóricamente más rápido. El análisis se realiza principalmente sobre dinámicas medias deterministas, con extensiones a entornos estocásticos mediante argumentos estándar de media condicional.