Resumen Técnico: Límites Mejorados para la Exploración Agnóstica a la Recompensa y Libre de Recompensa

Formulación del Problema

Este artículo aborda el desafío de la exploración en Procesos de Decisión de Markov (MDP) tabulares episódicos de horizonte finito, donde el agente opera sin observar señales de recompensa externas durante la fase de recopilación de datos. Los autores estudian dos marcos específicos:

1. Exploración Libre de Recompensa (RFE): El agente explora un entorno desconocido sin ninguna señal de recompensa. El objetivo es producir una política que sea $\epsilon$-óptima para cualquier función de recompensa arbitraria revelada después de la fase de exploración.
2. Exploración Agnóstica a la Recompensa (RAE): Similar a RFE, pero la función de recompensa se extrae de una clase finita pequeña y predefinida (de tamaño polinómico en $|S|, |A|, H$). El objetivo es encontrar una política $\epsilon$-óptima para la recompensa específica extraída de esta clase.

La dificultad central radica en recopilar datos suficientes para estimar con precisión la dinámica de transición estado-acción sin la guía de una señal de recompensa, asegurando que el modelo resultante soporte el cálculo de políticas casi óptimas para tareas posteriores.

Metodología

El enfoque propuesto reemplaza la dependencia de múltiples subrutinas independientes sin arrepentimiento encontradas en trabajos anteriores con un procedimiento de aprendizaje en línea unificado. El algoritmo (Algoritmo 1) opera en tres etapas:

1. Creación de la Política de Exploración

En lugar de ejecutar múltiples algoritmos estocásticos sin arrepentimiento (como lo hicieron Jin et al., 2020b; Li et al., 2024b), los autores emplean una sola ejecución de un algoritmo de Descenso de Espejo en Línea (OMD) sobre una secuencia de funciones de recompensa auxiliares cuidadosamente construidas.

• Mecanismo: El algoritmo genera una secuencia de recompensas $\{\lambda_t\}$ diseñada para dirigir al agente hacia pares estado-acción menos visitados. La recompensa en el paso $t$ es inversamente proporcional al conteo de visitas del par estado-acción (más una constante $c$ para manejar visitas de baja probabilidad).
• Perspectiva de Optimización: Este proceso se enmarca como la resolución aproximada de un problema de optimización convexa sobre el espacio de medidas de ocupación válidas. Específicamente, busca minimizar el objetivo de barrera logarítmica negativa $f(\mu) = -\sum \log \mu_h(s,a)$.
• Significado: Al utilizar un solo algoritmo de MDP en línea (adaptado de Rosenberg & Mansour, 2019) en lugar de iteraciones al estilo Frank-Wolfe, el método reduce significativamente los términos de complejidad de muestra de orden inferior. Reutiliza muestras a lo largo del proceso de aprendizaje para construir una "cobertura de políticas" que garantiza una exploración casi uniforme de las triples estado-acción significativas.

2. Estimación de la Dinámica

Utilizando la política de exploración generada en el Paso 1, el agente recopila $N$ trayectorias. Para manejar las correlaciones temporales inherentes a los datos de las trayectorias, los autores utilizan un marco de submuestreo doble (Li et al., 2024a). Esta técnica divide el conjunto de datos en un conjunto principal y un conjunto auxiliar para inducir independencia estadística, permitiendo la construcción de un núcleo de transición empírico $\hat{P}$ con garantías rigurosas de concentración.

3. Estimación de la Política

Una vez revelada la función de recompensa verdadera, el algoritmo calcula una política $\epsilon$-óptima utilizando pesimismo ante la incertidumbre.

• El algoritmo construye un MDP empírico utilizando $\hat{P}$ y la recompensa revelada.
• Aplica un término de penalización $b_h(s,a)$ derivado de desigualdades de concentración al estilo de Bernstein a las estimaciones del valor Q. Esta penalización escala con la varianza empírica y los conteos de visitas, desalentando que la política visite pares estado-acción mal cubiertos.
• La política final $\hat{\pi}$ es la política óptima para este MDP empírico pesimista.

Contribuciones y Resultados Clave

1. Complejidad de Muestra Mejorada para la Exploración Agnóstica a la Recompensa (RAE)

El artículo presenta un nuevo algoritmo que logra la complejidad de muestra de orden alto óptima para RAE, igualando el límite inferior para la Identificación de la Mejor Política (BPI).

• Resultado: La complejidad de muestra es $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$.
• Mejora: Mientras que trabajos anteriores (Li et al., 2024b) lograron el término de orden alto óptimo $O(|S||A|H^3/\epsilon^2)$, su límite sufría de un término de orden inferior de alta complejidad que hacía que el límite fuera óptimo solo para $\epsilon$ extremadamente pequeños. El método propuesto reduce significativamente este término de orden inferior, haciendo que el algoritmo sea aplicable a un rango más amplio de parámetros de precisión.

2. Límite Inferior Ajustado para la Exploración Libre de Recompensa (RFE)

Los autores prueban un límite inferior ajustado para la complejidad de muestra de RFE en MDPs no homogéneos en el tiempo.

• Resultado: Cualquier algoritmo de RFE requiere $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$ trayectorias en expectativa.
• Significado: Esto resuelve una conjetura de Li et al. (2024b) de que el límite inferior minimax para RFE no homogéneo en el tiempo es un factor de $H$ mayor que el caso homogéneo en el tiempo. Esto establece que los límites superiores existentes (por ejemplo, M´enard et al., 2021) son óptimos hasta factores logarítmicos.

3. Marco Teórico

El artículo proporciona una perspectiva técnica novel al vincular la creación de la política de exploración con la minimización de un objetivo de barrera logarítmica sobre medidas de ocupación. Demuestra que un enfoque de descenso de espejo en línea puede aproximar esta solución de manera más eficiente que los métodos anteriores basados en Frank-Wolfe, reduciendo así la dependencia de las dimensiones del problema en los términos de orden inferior.

Significado y Afirmaciones

El artículo afirma avanzar en la comprensión teórica de la exploración sin recompensas mediante:

1. Desenredar la Exploración y la Explotación: Aclara la complejidad de muestra intrínseca de la exploración en MDPs de horizonte finito.
2. Practicidad de RAE: Al relajar los requisitos restrictivos sobre el parámetro de precisión $\epsilon$ encontrados en límites óptimos anteriores, el método propuesto hace que la exploración agnóstica a la recompensa sea práctica incluso en regímenes de precisión moderada.
3. Completitud de la Caracterización: La combinación del nuevo límite superior para RAE y el límite inferior ajustado para RFE proporciona una caracterización minimax completa de la complejidad de muestra para estos problemas (hasta factores logarítmicos).

Los autores declaran explícitamente que su enfoque está en el análisis teórico de MDPs tabulares de horizonte finito, dejando los MDPs no tabulares y los resultados empíricos como vías para trabajo futuro. No afirman una aplicación inmediata a dominios específicos del mundo real como la robótica o la medicina, sino que enfatizan las mejoras teóricas fundamentales que permiten tales aplicaciones.