Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization

Resumen Técnico: Selección de Episodios Inspirada en Computación Cuántica para el Aprendizaje por Refuerzo de Monte Carlo mediante Optimización QUBO

Planteamiento del Problema
El aprendizaje por refuerzo de Monte Carlo (MC) enfrenta desafíos significativos en cuanto a la eficiencia de muestreo, particularmente en entornos caracterizados por recompensas dispersas, espacios de estados extensos y trayectorias temporalmente correlacionadas. Los métodos MC estándar dependen del supuesto de que las muestras de datos son independientes e idénticamente distribuidas (i.i.d.), un supuesto que se viola debido a la naturaleza markoviana de las trayectorias de RL. En consecuencia, los estimadores de MC sufren de:

1. Propagación de la Varianza: Los retornos exhiben una varianza compuesta, lo que requiere un número de episodios ($N_s$) que escala como $O(\epsilon^{-2})$ para reducir el error de estimación.
2. Dilución de Trayectorias Subóptimas: En dominios de recompensa dispersa, el estimador se ve diluido por trayectorias de baja recompensa, lo que requiere un crecimiento exponencial en el tamaño de la muestra para asegurar una cobertura suficiente de las rutas óptimas.
3. Explosión Combinatoria: Teóricamente, seleccionar un subconjunto óptimo de $m$ episodios de $N$ candidatos para maximizar la precisión de la estimación de valor es un problema NP-duro isomórfico a la selección de características y a la cobertura de conjuntos, con un espacio de soluciones de $\binom{N}{m}$.

Metodología
Los autores proponen MC+QUBO, un marco que reformula el proceso de selección de episodios como un problema de Optimización Binaria No Restringida Cuadrática (QUBO). En lugar de utilizar todos los episodios muestreados para las actualizaciones de la política, el método filtra un lote de trayectorias para seleccionar un subconjunto que maximice la recompensa acumulada mientras promueve la cobertura del espacio de estados (diversidad).

• Formulación QUBO: El problema de selección se codifica como:
  $$\min_{x \in \{0,1\}^n} \left( -\alpha \sum_{i=1}^n R_i x_i + \gamma \sum_{i<j} w_{ij} x_i x_j \right)$$
  Donde:

  • $x_i = 1$ indica la selección del episodio $\tau_i$.
  • $R_i$ es la recompensa acumulada del episodio $i$.
  • $w_{ij}$ representa la similitud por pares entre episodios (por ejemplo, la similitud de Jaccard de los conjuntos de estados visitados).
  • $\alpha$ es un multiplicador de escala de recompensa, y $\gamma$ pondera la penalización por similitud.
  • El término lineal ($-\alpha R_i$) favorece los episodios de alta recompensa, mientras que el término cuadrático ($\gamma w_{ij}$) penaliza la redundancia, fomentando la selección de trayectorias diversas.

• Solvers Inspirados en Cuántica: El problema QUBO se resuelve utilizando samplers de caja negra inspirados en la computación cuántica, específicamente Recocido Cuántico Simulado (SQA) y Bifurcación Simulada (SB).

  • SQA imita el recocido cuántico utilizando actualizaciones estocásticas clásicas y Monte Carlo de integral de trayectoria para simular el tunelamiento cuántico entre mínimos de energía.
  • SB utiliza un enfoque de sistema dinámico clásico donde las variables continuas evolucionan hacia estados binarios a través de fenómenos de bifurcación.
  • Los autores tratan estos solvers como oráculos que proporcionan soluciones aproximadas de alta calidad dentro de presupuestos computacionales prácticos.

• Integración: El flujo de trabajo implica generar un lote de episodios, calcular recompensas y similitudes, formular el QUBO, enviar el problema al solver y utilizar la mejor solución observada (el vector binario $x^*$) para determinar qué episodios se utilizan para actualizar la tabla de valores de acción $Q(s, a)$ mediante MC de primera visita.

Contribuciones Clave

1. Reformulación de la Selección de Episodios: El artículo establece un vínculo formal entre la selección de episodios de MC y la optimización combinatoria, demostrando que el problema de selección puede mapearse a una formulación QUBO.
2. Integración Algorítmica: Introduce un pipeline concreto (Algoritmo 2) que inserta un paso de filtrado basado en QUBO entre el muestreo de trayectorias y la evaluación de la política en el aprendizaje MC estándar.
3. Validación Empírica: El estudio evalúa el método en entornos GridWorld de horizonte finito de diversos tamaños ($3\times3$ a $20\times20$), comparando MC+QUBO contra un baseline de MC vanilla.

Resultados
Los experimentos realizados en entornos GridWorld demuestran que MC+QUBO supera consistentemente al MC vanilla en términos de velocidad de convergencia y calidad de la política final.

• Escalabilidad: La brecha de rendimiento se amplía en entornos más grandes ($\ge 10\times10$), donde las recompensas dispersas y el crecimiento exponencial del espacio de estados suelen dificultar la evaluación de MC estándar.
• Convergencia: MC+QUBO converge en menos lotes al centrar el aprendizaje en trayectorias informativas y diversas, filtrando eficazmente los episodios redundantes.
• Perspectiva de Diseño: Los autores señalan que priorizar la cobertura del espacio de estados (estableciendo la influencia del peso de la recompensa cerca de cero) produjo un aprendizaje más equilibrado y una mejor generalización que la selección impulsada por la recompensa, la cual tendía a causar una convergencia más rápida pero menos estable.
• Rendimiento del Solver: Los solvers inspirados en la cuántica (SQA y SB) superaron a las heurísticas clásicas (como la Búsqueda Tabú y el Recocido Simulado) en este contexto. La latencia computacional estuvo dominada por la comunicación en la nube más que por el tiempo del solver en sí (que fue insignificante para $n \le 200$).

Significancia y Reclamaciones
El artículo afirma que la integración de la optimización inspirada en la cuántica como un subproceso de toma de decisiones ofrece una mejora práctica para los métodos de MC, particularmente para problemas con recompensas dispersas y trayectorias correlacionadas. Al unir el RL con la optimización combinatoria, el estudio sugiere una vía para algoritmos donde los métodos cuánticos y de inspiración cuántica guíen activamente el proceso de aprendizaje para superar la ineficiencia de muestreo.

Los autores mantienen la modestia respecto al alcance, señalando que, si bien el marco muestra promesa en GridWorld, se requiere trabajo futuro para explorar extensiones al control continuo, RL jerárquico y sistemas multi-agente, así como el despliegue en hardware cuántico real. El presente trabajo sirve como una prueba de concepto para el uso de solvers inspirados en la física para optimizar la fase de selección de datos en el aprendizaje por refuerzo.