Resumen Técnico: Un poco de libertad llega lejos: Algoritmos clásicos y cuánticos para el aprendizaje por refuerzo bajo un modelo generativo

Declaración del Problema

El artículo aborda el problema de aprender Procesos de Decisión de Markov (MDP) en un entorno online, centráéndose específicamente en la minimización del arrepentimiento (la diferencia entre la recompensa acumulada del agente y la de una política óptima). Los autores consideran tres entornos de MDP distintos:

1. MDP de horizonte finito: Las interacciones ocurren durante un número fijo de pasos $H$.
2. MDP de horizonte infinito con descuento: Las interacciones continúan indefinidamente con recompensas descontadas por un factor $\gamma \in [0, 1)$.
3. MDP de horizonte infinito sin descuento: Las interacciones continúan indefinidamente bajo criterios de recompensa promedio, centrándose específicamente en MDPs débilmente comunicantes.

Un desafío central en el Aprendizaje por Refuerzo (RL) es el compromiso entre exploración y explotación (exploration-exploitation trade-off). En el entorno clásico, los agentes deben aprender las probabilidades de transición $p(\cdot|s, a)$ mientras interactúan con el entorno. En el entorno cuántico, surge un problema fundamental: los oráculos cuánticos estándar permiten la superposición y las operaciones inversas, lo que puede conducir a medidas de arrepentimiento no definidas si el agente interactúa con el entorno de manera cuántica durante todo el proceso de aprendizaje. Además, los trabajos previos de RL cuántico que intentaban lograr un arrepentimiento polilogarítmico en el tiempo $T$ dependían de supuestos erróneos respecto a la aplicación coherente de la estimación de amplitud cuántica.

Metodología

El Modelo Híbrido de RL Online-Offline

Para resolver los problemas de definición del arrepentimiento en RL cuántico y para aprovechar las aceleraciones cuánticas, los autores proponen un modelo de RL híbrido online-offline. Este modelo separa el proceso de aprendizaje en dos fases distintas:

1. Fase Online (Exploración): El agente interactúa con el entorno de forma clásica. Elige acciones, recibe recompensas y observa las transiciones de estado. Crucialmente, el arrepentimiento se acumula durante esta fase. El agente no tiene acceso a oráculos cuánticos aquí.
2. Fase Offline (Aprendizaje Generativo): Se le otorga al agente la "libertad" de interactuar con el entorno a través de un modelo generativo.
   • En la fase offline clásica, el agente accede a un oráculo de muestreo $C_p$ que devuelve los siguientes estados $s'$ dado $(s, a)$.
   • En la fase offline cuántica, el agente accede a un oráculo cuántico $Q_p$ (y su inversa) que prepara superposiciones de los siguientes estados.
   • Restricción: El número de llamadas al oráculo en la fase offline está limitado por una función de la longitud de la fase online previa $\tau$, específicamente $O(\tau^\beta)$, donde $\beta \in [0, \infty)$ es un parámetro de "presupuesto". Esto evita que el agente obtenga una política casi óptima con cero arrepentimiento simplemente consultando el oráculo excesivamente.

Enfoque Algorítmico

Los algoritmos propuestos (Algoritmo 1) progresan por épocas. En cada época $\ell$:

1. Computación Offline: Utilizando los datos recopilados en la fase online anterior (longitud $\tau_{\ell-1}$), el agente computa una política $\epsilon_\ell$-óptima.
   • Clásico: Utiliza algoritmos de muestra-óptimos conocidos (por ejemplo, Sidford et al.) para computar políticas.
   • Cuántico: Los autores introducen nuevos algoritmos cuánticos para computar políticas óptimas bajo un modelo generativo. Estos algoritmos utilizan la estimación de media cuántica (Kothari y O'Donnell) y la búsqueda de mínimo/máximo cuántica (Dürr y Høyer) para acelerar la iteración de valor.
2. Ejecución Online: La política computada $\pi^{(\ell)}$ se ejecuta en el entorno durante una duración determinada por un truco de duplicación (aumentando el horizonte por un factor de 2 o $2H$).
3. Análisis de Arrepentimiento: El arrepentimiento total se acota sumando la sub-optimalidad de las políticas utilizadas en cada fase online.

Principales Contribuciones Técnicas

1. Nuevos Algoritmos Cuánticos para Modelos Generativos:

   • Horizonte Finito: Los autores diseñan algoritmos cuánticos que mejoran la complejidad de consulta clásica. Combinan la iteración de valor cuantizada con técnicas de reducción de varianza. La complejidad de consulta es $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$, mejorando la dependencia de $H$ y $A$ respecto a los límites clásicos.
   • Horizonte Infinito con Descuento: Se logran mejoras similares, con una complejidad de consulta de $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$.
   • Horizonte Infinito sin Descuento: Esta es una nueva contribución. Los autores proponen un algoritmo cuántico para MDPs débilmente comunicantes bajo el supuesto de que el operador de Bellman óptimo es una contracción de span-$\nu$ de $J$-etapas. La complejidad es $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$.

2. Corrección de Trabajos Previos de RL Cuántico:
   El artículo critica trabajos anteriores (por ejemplo, Ganguly et al., Zhong et al.) que afirmaban tener un arrepentimiento polilogarítmico. Los autores argumentan que estos trabajos asumieron incorrectamente que la estimación de amplitud cuántica podía realizarse sobre una colección de estados almacenados en lugar de requerir aplicaciones secuenciales y coherentes del oráculo y su inversa. El modelo híbrido propuesto corrige esto imponiendo una fase offline distinta donde tales operaciones coherentes pueden realizarse sin incurrir en arrepentimiento.

3. Límites de Arrepentimiento bajo el Modelo Híbrido:
   Los autores derivan límites de arrepentimiento tanto para el entorno clásico como para el cuántico en función del parámetro de presupuesto $\beta$:

   • Horizonte Finito:
     • Clásico: $\tilde{O}(\sqrt{HSAT})$ (igualando el estado del arte) cuando $\beta \ge 2$.
     • Cuántico: $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ para $\beta < 1$, y polilogarítmico en $T$ para $\beta \ge 1$.
   • Horizonte Infinito con Descuento:
     • Cuántico: Logra un arrepentimiento de $\tilde{O}(\text{polylog}(T))$ cuando $\beta \ge 1$, rompiendo la barrera clásica de $\Omega(\sqrt{T})$.
   • Horizonte Infinito sin Descuento:
     • Cuántico: Logra un arrepentimiento de $\tilde{O}(\Lambda S \sqrt{A} \cdot \text{polylog}(T))$ para $\beta \ge 1$, mejorando significativamente el límite de $\tilde{O}(\Lambda S^5 A^4)$ de trabajos cuánticos previos.

Resultados y Significado

El artículo afirma que el "poco de libertad" proporcionado por la fase generativa offline permite una mejora sustancial en la eficiencia del aprendizaje.

• Ventaja Cuántica: El resultado más significativo es la demostración de que las computadoras cuánticas pueden lograr un arrepentimiento polilogarítmico en el horizonte de tiempo $T$ (específicamente cuando $\beta \in [1, 2)$), mientras que los algoritmos clásicos están fundamentalmente limitados a un arrepentimiento de $\Omega(\sqrt{T})$ en estos entornos. Esto representa una mejora exponencial en la dependencia de $T$.
• Dependencia de Parámetros: Los algoritmos cuánticos mejoran la dependencia del tamaño del espacio de estados $S$, el tamaño del espacio de acciones $A$ y el horizonte $H$ (o horizonte efectivo $\Gamma$) en comparación con los algoritmos clásicos y los intentos cuánticos previos.
• Validez del Modelo: El artículo establece que el modelo híbrido online-offline es un marco necesario y significativo para el RL cuántico. Resuelve la ambigüedad de definir el arrepentimiento en las interacciones cuánticas y corrige las fallas teóricas de la literatura previa que asumía una exploración cuántica sin arrepentimiento sin tal separación.

Los autores concluyen que, si bien la ventaja exponencial cuántica en $T$ desaparece cuando el presupuesto $\beta$ es muy grande ($\beta \ge 2$, donde los algoritmos clásicos también logran un arrepentimiento polilogarítmico), existe un rango crítico ($\beta \in [1, 2)$) donde las computadoras cuánticas proporcionan una ventaja sustancial. El artículo identifica este rango como el área principal donde las aceleraciones cuánticas en RL son más impactantes bajo el modelo propuesto.