Finite-Time Convergence of Distributionally Robust Q-Learning with Linear Function Approximation

Resumen Técnico: Convergencia en Tiempo Finito de Q-Learning Distribucionalmente Robusto con Aproximación de Funciones Lineales

Planteamiento del Problema
El artículo aborda el desafío de aprender políticas óptimas en el Aprendizaje por Refuerzo Distribucionalmente Robusto (DRRL) cuando el entorno de despliegue difiere del entorno de entrenamiento (nominal). Específicamente, los autores se centran en el Q-learning robusto descontado, libre de modelo y de tipo $(s, a)$-rectangular bajo un conjunto de incertidumbre de chi-cuadrado.

El escenario involucra a un aprendiz que opera sobre una única trayectoria de Markov generada por un núcleo de transición nominal desconocido $P_0$ y una política de comportamiento $\pi_b$. El aprendiz carece de acceso generativo (no puede muestrear pares estado-acción arbitrarios) y desconoce $P_0$. El objetivo es aprender la función Q robusta óptima, $Q^\star_\chi$, que maximiza el valor descontado en el peor de los casos sobre el conjunto de incertidumbre.

El problema presenta dos dificultades acopladas:

1. Dificultad de la Aproximación de Funciones: Aunque el operador de Bellman robusto exacto es una contracción en $\ell_\infty$, el operador de Bellman robusto proyectado inducido por la aproximación de funciones lineales no es conocido por ser una contracción para factores de descuento generales $\gamma \in (0, 1)$.
2. Dificultad de la Estimación Robusta: La actualización de Bellman de Q de chi-cuadrado implica una minimización interna sobre distribuciones de transición. Su gradiente dual depende de momentos condicionales (específicamente, la parte positiva de la brecha de Bellman y su cuadrado) que deben estimarse a partir de una sola trayectoria. Los análisis estándar para el Q-learning robusto tabular o de Q lineal no se extienden directamente a este escenario.

Metodología
Los autores proponen el Algoritmo 1, un algoritmo de aproximación estocástica de múltiples etapas que combina un bucle externo de red de objetivo (target-network) con un esquema de aproximación de funciones dual. El algoritmo opera en bloques externos donde la función Q de objetivo está congelada. Dentro de cada bloque, ocurren tres etapas:

1. Etapa 1: Optimización Dual con Seguimiento de Momentos.
   El algoritmo resuelve la minimización interna de la actualización de Bellman de Q de chi-cuadrado a través de su forma dual escalar. En lugar de resolver un problema dual separado para cada par estado-acción, la variable dual $\eta$ se aproxima linealmente ($\eta_\nu(i) = \psi(i)^\top \nu$).

   • Esquema de Dos Escalas Temporales: La variable dual $\nu$ se actualiza en una escala de tiempo lenta, mientras que dos "críticos de seguimiento de momentos" ($\omega_1, \omega_2$) estiman los momentos condicionales requeridos ($Z_1$ y $Z_2$) en una escala de tiempo más rápida.
   • Suavizado: Para manejar la falta de suavidad global en el objetivo dual de chi-cuadrado (que causa problemas con el análisis de ruido de Markov), los autores optimizan un objetivo subrogado suavizado utilizando un parámetro ajustable $\tau > 0$. Esto asegura que el gradiente dual sea Lipschitz continuo.
   • Promedio de Sufijo: Las iteraciones duales se promedian mediante sufijos para obtener una estimación estable $\bar{\nu}_t$.

2. Etapa 2: Evaluación Fresca.
   Antes de actualizar la función Q, el algoritmo realiza una "evaluación fresca" del momento de tipo varianza ($Z_1$) utilizando el parámetro dual promediado $\bar{\nu}_t$. Esta etapa aísla la estimación del momento de la trayectoria de optimización, evitando la acumulación de sesgo que ocurriría si se reutilizaran directamente los críticos de la Etapa 1 (aprendidos mientras $\nu$ se movía).

3. Etapa 3: Actualización de Q.
   El algoritmo realiza una actualización lenta de diferencia temporal para el parámetro $\theta$ de la función Q robusta contra el objetivo evaluado y fijo derivado de las Etapas 1 y 2.

Contribuciones Clave

1. Garantía de Convergencia en Tiempo Finito: El artículo proporciona la primera cota de convergencia en tiempo finito para el Q-learning robusto con aproximación de funciones lineales y de un solo paso (model-free) bajo un factor de descuento, sin imponer restricciones de factor de descuento pequeño.
2. Análisis de Red de Objetivo para RL Robusto: Los autores adaptan la técnica de red de objetivo (común en el RL profundo no robusto) al entorno robusto. Al congelar la función Q de objetivo dentro de bloques externos, evitan la no-contractividad del operador de Bellman robusto proyectado, permitiendo que el análisis dependa de la contracción del operador no proyectado a través de los bloques.
3. Estimación Dual Escalable: Introducen un método para aproximar la propia variable dual utilizando una clase de funciones lineales, junto con críticos de seguimiento de momentos. Esto evita los problemas de escalabilidad de resolver problemas duales independientes para grandes espacios de estados.
4. Suavizado y Control de Sesgo: El artículo introduce un subrogado suavizado para el objetivo dual de chi-cuadrado. Esto resuelve el problema de la gradiente no Lipschitz inherente a la formulación exacta de chi-cuadrado, permitiendo límites rigurosos de aproximación estocástica de tiempo finito bajo ruido de Markov. Los autores señalan explícitamente que las pruebas anteriores para el Q-learning robusto tabular con incertidumbre de chi-cuadrado dependían de supuestos de suavidad global que no se cumplen; su prueba corrige este vacío.

Resultados
El principal resultado teórico (Teorema 1) establece una cota de convergencia de extremo a extremo de la forma:
$$\mathbb{E}[\| \hat{Q}_T - Q^\star_\chi \|_\infty] \leq \gamma^T \| \hat{Q}_0 - Q^\star_\chi \|_\infty + \frac{E_{stat}(N, M, K, \tau) + E_{app}(\tau)}{1 - \gamma}$$
donde:

• El primer término representa el error de contracción de la red de objetivo.
• $E_{stat}$ captura los errores de muestra finita de la actualización de Q, la optimización dual, el sesgo de suavizado y la evaluación fresca.
• $E_{app}$ captura los errores de aproximación debidos a la aproximación de funciones y al suavizado.

El experimento en el MDP FrozenLake valida la teoría, demostrando la convergencia hacia el valor de referencia robusto e ilustrando el compromiso introducido por el parámetro de suavizado $\tau$ (un $\tau$ más pequeño reduce el sesgo pero aumenta la varianza/error de optimización).

Significado y Reivindicaciones
El artículo afirma cerrar una brecha significativa entre el éxito empírico de los algoritmos de RL robusto y las garantías teóricas disponibles para sus contrapartes no robustas. Los trabajos previos de RL robusto libre de modelo estaban limitados a entornos tabulares, requerían acceso generativo, asumían exploración activa o imponían condiciones restrictivas sobre el factor de descuento.

Los autores afirman que su trabajo proporciona la primera garantía de convergencia en tiempo finito para el Q-learning robusto con aproximación de funciones lineales a partir de datos de una sola trayectoria sin supuestos de factor de descuento pequeño. Además, sostienen que su prueba para el caso de chi-cuadrado (incluso en el límite tabular) parece ser la primera prueba de convergencia correcta, ya que aborda la falta de suavidad global en el objetivo dual que otros análisis habían pasado por alto o asumido erróneamente. El marco se presenta como una plantilla analizable que puede extenderse a implementaciones de redes neuronales a gran escala.