Resumen Técnico: Comprometerse con el Bit: Aprendizaje por Refuerzo Reactivo Hecho Correctamente

1. Declaración del Problema

Los algoritmos de aprendizaje por refuerzo (RL) están tradicionalmente diseñados y analizados bajo la suposición de Markov, donde el agente tiene acceso completo al estado. Sin embargo, los entornos prácticos a menudo son parcialmente observables (POMDPs) o requieren aproximación de funciones que restringen al agente a características de estado no markovianas (agregación de estados rígida). En tales configuraciones, el agente debe aprender una política reactiva—una mapeo desde características observadas hacia distribuciones de acciones (opciones)—sin memoria de las observaciones pasadas.

Los resultados teóricos existentes para aprender políticas reactivas óptimas bajo agregación de estados rígida suelen depender de la suposición de $q^\star$-realizabilidad. Esta condición requiere que la función óptima de valor-acción $q^\star(x, u)$ sea constante dentro de cada característica (es decir, $q^\star(x, u) = q(\phi(x), u)$). Los autores argumentan que esta suposición es excesivamente restrictiva, excluyendo entornos simples (como el ejemplo del "corredor") donde existe una política reactiva óptima pero los estados subyacentes dentro de una característica tienen valores óptimos diferentes. Además, el Q-learning estándar falla en estos escenarios porque intenta aproximar una función de valor que es ambigua dentro de la característica agregada.

El artículo aborda el problema de aprender una política reactiva óptima en POMDPs finitos y episódicos con observaciones deterministas, con el objetivo de relajar las suposiciones de realizabilidad requeridas para la convergencia.

2. Metodología

Q-learning Comprometido

Los autores proponen Q-learning Comprometido, una variante del Q-learning clásico. El mecanismo central es una estrategia de "compromiso":

• Al entrar en una característica $z$, la política de comportamiento muestrea una sola opción (distribución de acciones) $\omega$.
• El agente se compromete con esta opción y la ejecuta hasta que la característica observada cambia ($z' \neq z$).
• Solo cuando la característica cambia, el agente remuestrea una nueva opción.
• Los valores Q, $Q(z, \omega)$, se actualizan basándose en la transición desde la característica $z$ hacia $z'$.

Esto contrasta con el Q-learning no comprometido, que podría remuestrear acciones en cada paso de tiempo independientemente de la estabilidad de la característica. El compromiso asegura que el proceso de aprendizaje opere en la escala de tiempo de las transiciones de características en lugar de las transiciones de estado brutas.

Marco Teórico: Entornos Cuasi-Markovianos y Robustez ante Reencaminamiento

Para analizar la convergencia, los autores introducen dos conceptos clave:

1. Entornos Cuasi-Markovianos: Un entorno es cuasi-markoviano si, para cada característica, existe una distribución única sobre los estados de entrada (o un único estado de entrada). En tales entornos, la propiedad de Markov se mantiene entre características: la distribución de estados al entrar en una característica es independiente de la característica anterior. Los autores muestran que en entornos cuasi-markovianos, el valor óptimo para una característica corresponde al valor de su estado de entrada, permitiendo que la programación dinámica funcione correctamente.

2. Robustez ante Reencaminamiento: Este es la contribución central del artículo. Un entorno es robusto ante reencaminamiento si la política reactiva óptima permanece inalterada bajo cualquier "reencaminamiento" del entorno. Un reencaminamiento modifica las "dinámicas de entrada" (cómo se entra en una característica) mientras mantiene invariantes las dinámicas internas de la característica y las probabilidades de transición entre características.

   • Reencaminamiento Generalizado: Permite cambios arbitrarios en las distribuciones de entrada.
   • Reencaminamiento $\pi$: Un tipo específico de reencaminamiento donde las distribuciones de entrada se reemplazan por la distribución de entrada "promedio" inducida por la política de comportamiento $\pi$.

Los autores definen Riesgo de Bellman y Riesgo de Valor como objetivos aprendibles (a diferencia del Error de Bellman o el Error de Valor en configuraciones parcialmente observables) y demuestran que minimizar el Riesgo de Bellman en un entorno cuasi-markoviano produce los valores de entrada correctos.

3. Contribuciones Clave

• Algoritmo de Q-learning Comprometido: Un algoritmo que converge demostrablemente a la política reactiva óptima bajo una suposición estrictamente más débil que el trabajo anterior.
• Condición de Robustez ante Reencaminamiento: La introducción de una nueva suposición para la agregación de estados. El artículo demuestra que la robustez ante reencaminamiento es estrictamente más débil que la $q^\star$-realizabilidad. Esto significa que el algoritmo converge en una clase más amplia de entornos, incluidos aquellos donde la función de valor óptima no es constante dentro de una característica (por ejemplo, el entorno del corredor).
• Formalismo Cuasi-Markoviano: Una definición rigurosa de entornos cuasi-markovianos y el MDP agregado asociado, que sirve como puente teórico entre el entorno parcialmente observable y el algoritmo de aprendizaje.
• Prueba de Convergencia: Utilizando una extensión del teorema de Borkar-Meyn para ruido markoviano (Liu et al., 2025), los autores demuestran que el Q-learning Comprometido converge casi seguramente a la política reactiva óptima en cualquier entorno robusto ante reencaminamiento.

4. Resultados

• Convergencia: Las iteraciones $(Q_t)$ del Q-learning Comprometido convergen casi seguramente a una solución $Q^\star$. La política codiciosa derivada de $Q^\star$ es óptima en el entorno si este es robusto ante reencaminamiento.
• Jerarquía de Suposiciones: El artículo establece una jerarquía estricta de suposiciones:
  • $q^\star$-realizabilidad $\implies$ Robustez ante reencaminamiento generalizado $\implies$ Robustez ante reencaminamiento.
  • Las implicaciones inversas no se cumplen. Específicamente, el entorno del corredor es robusto ante reencaminamiento pero no $q^\star$-realizable.
• Validación Empírica: Experimentos numéricos en el entorno del corredor demuestran que, mientras que el Q-learning regular falla en lograr progreso, el Q-learning Comprometido converge rápidamente a la política óptima a través de diversas longitudes de corredor.

5. Significado y Afirmaciones

El artículo afirma que el Q-learning Comprometido proporciona una solución con fundamento teórico para el aprendizaje por refuerzo reactivo en entornos parcialmente observables sin requerir la fuerte suposición de $q^\star$-realizabilidad.

• Relajación de Suposiciones: Al introducir la robustez ante reencaminamiento, el trabajo expande la clase de entornos donde se pueden aprender políticas reactivas óptimas. Los autores notan que encontrar una política reactiva óptima bajo agregación de estados es generalmente NP-completo (Littman, 1994), lo que hace necesarias tales suposiciones para algoritmos eficientes; sin embargo, este trabajo identifica la suposición más débil conocida para la convergencia.
• Interpretabilidad: El algoritmo opera en un "nivel superior" (el espacio de características), resolviendo efectivamente un MDP agregado. El mecanismo de "compromiso" no es una restricción, sino una alineación natural con el objetivo de encontrar una política reactiva que mapee características a opciones.
• Aprendibilidad: El artículo aclara que las métricas de error estándar (Error de Valor, Error de Bellman) no son aprendibles en configuraciones parcialmente observables porque dependen de distribuciones de estado no observables. En contraste, el Riesgo de Bellman propuesto es aprendible a partir de características y recompensas observadas, proporcionando una base sólida para el análisis de convergencia.

Los autores concluyen que su enfoque ofrece un marco robusto para el RL reactivo, cerrando la brecha entre las limitaciones teóricas de la agregación de estados y la necesidad práctica de políticas sin memoria en entornos complejos. Se sugiere trabajo futuro para extender estos resultados a opciones no estacionarias, problemas de horizonte infinito con descuento y robustez ante reencaminamiento aproximada.