Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

1. Planteamiento del Problema

El Aprendizaje por Refuerzo (RL) en entornos a gran escala o continuos enfrenta cuellos de botella computacionales severos. Los algoritmos tradicionales de minimización de arrepentimiento basados en modelos requieren llamadas frecuentes a dos tipos de "oráculos":

1. Oráculo de Estimación Estadística: Utilizado para estimar el modelo del entorno (dinámicas de transición y recompensas) a partir de datos.
2. Oráculo de Optimización de Políticas (Planificación): Utilizado para calcular la política óptima dado el modelo estimado.

Los enfoques existentes sufren de dos limitaciones principales:

• Alta Frecuencia de Llamadas al Oráculo: La mayoría de los algoritmos requieren $O(T)$ llamadas a estos oráculos, donde $T$ es el horizonte temporal, lo que los hace computacionalmente prohibitivos para $T$ grande.
• Dependencia del Tamaño del Espacio de Estados/Acciones: La complejidad de la planificación a menudo escala con la cardinalidad del espacio de estados ($S$) y del espacio de acciones ($A$). Esto hace que los métodos existentes sean intratables para entornos con espacios de estados/acciones grandes, infinitos o continuos (por ejemplo, MDPs lineales con estados infinitos).

Aunque trabajos recientes (por ejemplo, Qian et al., 2024) lograron "eficiencia de oráculo fuera de línea" (pocas llamadas al oráculo de estimación) para MDPs tabulares, su complejidad del oráculo de planificación aún escalaba con $S$ y $A$ (específicamente $O(HSA \log \log T)$). El artículo aborda la pregunta abierta: ¿Podemos diseñar un algoritmo que sea eficiente tanto en los oráculos de estimación como de planificación, con complejidad independiente de $S$ y $A$, y aplicable a espacios de estados/acciones infinitos?

2. Metodología

Los autores proponen DOERL (Aprendizaje por Refuerzo Doble-Eficiente en Oráculos), un nuevo marco algorítmico basado en la regularización de barrera logarítmica y log-determinante. La innovación central radica en cómo el algoritmo gestiona la compensación entre exploración y explotación mientras minimiza las llamadas al oráculo.

Componentes Técnicos Clave:

1. Aprendizaje por Épocas con Actualizaciones Truncadas:

   • El proceso de interacción se divide en $N$ épocas. Dentro de cada época, el agente ejecuta una política fija durante un segmento de tiempo.
   • Crucialmente, el oráculo de estimación fuera de línea solo se llama al final de cada época (o segmento), agregando datos para actualizar el modelo. Esto reduce el número de llamadas de estimación a $O(N)$.
   • El oráculo de planificación también se invoca solo al inicio de los segmentos, reduciendo significativamente la frecuencia de planificación.

2. Medidas de Ocupación Confiables:

   • Para evitar explorar transiciones estado-acción raras o poco fiables, el algoritmo define un "conjunto de transiciones confiables" $\mathcal{T}_m^h$.
   • Las transiciones solo se consideran "confiables" si la medida de ocupación estimada multiplicada por la probabilidad de transición supera un umbral ($1/\zeta_m$).
   • Este concepto, adaptado de Qian et al. (2024), se modifica para ser computable sin iterar sobre todo el espacio de políticas, lo cual es crítico para la eficiencia.

3. Regularización para la Exploración:

   • Para MDPs Tabulares: El algoritmo utiliza Regularización de Barrera Logarítmica. El objetivo de optimización de la política incluye un término $\sum \log(\text{ocupación confiable} + \beta)$. Esto incentiva al agente a visitar pares estado-acción que son "confiables" pero tienen baja probabilidad, asegurando una exploración suficiente sin necesidad de enumerar todos los estados.
   • Para MDPs Lineales (Espacios Infinitos): El algoritmo introduce Regularización de Log-Determinante. En lugar de sumar sobre estados discretos, maximiza el log-determinante de la matriz de covarianza de características ponderada por la medida de ocupación confiable: $\log \det(\mathbf{K} + \beta \mathbf{I})$. Esto promueve la exploración del espacio de características, asegurando que el agente recopile datos diversos para estimar los coeficientes lineales con precisión.

4. Estrategia de Agregación:

   • El algoritmo agrega estimaciones por capas (kernels de transición y recompensas) del oráculo fuera de línea en un único modelo global para la siguiente época, en lugar de actualizar el modelo en cada paso individual.

3. Contribuciones Clave

1. Doble Eficiencia en Oráculos:

   • El artículo presenta el primer algoritmo que logra tanto eficiencia en el oráculo de estimación estadística como eficiencia en el oráculo de optimización de políticas.
   • Complejidad de Llamadas al Oráculo: El algoritmo requiere solo $O(H \log \log T)$ llamadas a ambos oráculos cuando $T$ es conocido (y $O(H \log T)$ cuando es desconocido).
   • Independencia de Dimensiones: Crucialmente, esta complejidad es estrictamente independiente del tamaño del espacio de estados ($S$) y del tamaño del espacio de acciones ($A$).

2. Extensión a Espacios Infinitos:

   • El marco se generaliza a MDPs Lineales con espacios de estados infinitos y espacios de acciones arbitrarios.
   • Es el primer algoritmo eficiente en oráculos fuera de línea que logra un arrepentimiento sublineal en este contexto, superando la "maldición de la dimensionalidad" que afecta a los métodos tabulares.

3. Límites Óptimos de Arrepentimiento:

   • MDPs Tabulares: Logra el límite óptimo de arrepentimiento $O(\sqrt{T})$.
   • MDPs Lineales: Logra un límite de arrepentimiento sublineal de $O(T^{4/5})$ (con factores logarítmicos), lo cual es significativo para configuraciones de dimensión infinita bajo las restricciones dadas de oráculos.

4. Resultados

Se establecen garantías teóricas tanto para configuraciones finitas (tabulares) como infinitas (lineales):

• MDPs Tabulares:

  • Arrepentimiento: $O(\sqrt{T})$ (óptimo).
  • Llamadas al Oráculo: $O(H \log \log T)$ para estimación y planificación.
  • Comparación: Mejora significativamente a Qian et al. (2024), que requería $O(HSA \log \log T)$ llamadas de planificación.

• MDPs Lineales (Estados/Acciones Infinitos):

  • Arrepentimiento: $O(T^{4/5} \cdot \text{polylog}(T))$.
  • Llamadas al Oráculo: $O(H \log \log T)$ para ambos oráculos.
  • Significado: Antes de este trabajo, no existía ningún algoritmo que pudiera resolver MDPs de estados infinitos con llamadas al oráculo de tan baja frecuencia mientras mantenía un arrepentimiento sublineal.

5. Significado e Impacto

• Puente entre Teoría y Práctica: Al desacoplar la complejidad computacional del tamaño de los espacios de estados/acciones, este trabajo hace que el RL basado en modelos sea teóricamente viable para aplicaciones complejas del mundo real, como robótica y sistemas autónomos, donde $S$ y $A$ son efectivamente infinitos.
• Eficiencia en Sistemas a Gran Escala: La reducción de las llamadas al oráculo de $O(T)$ o $O(SA)$a$O(\log \log T)$ representa una disminución masiva en la sobrecarga computacional, permitiendo el uso de estimadores fuera de línea costosos (como redes neuronales profundas) en bucles de RL donde anteriormente eran demasiado costosos.
• Nuevo Paradigma para la Exploración: La integración de la regularización de barrera logarítmica y log-determinante con medidas "confiables" proporciona un mecanismo teórico robusto para la exploración que escala elegantemente con la dimensionalidad, ofreciendo una hoja de ruta para futuros algoritmos en control de alta dimensión.

En resumen, este artículo avanza fundamentalmente el estado del arte en Aprendizaje por Refuerzo al demostrar que se puede lograr un arrepentimiento óptimo con una sobrecarga computacional mínima (independiente del tamaño del entorno) mediante una combinación novedosa de aprendizaje por épocas, medidas confiables y regularización basada en determinantes.