Resumen Técnico: Bootstrap Basado en Modelo de Cadenas de Markov Controladas

Enunciado del Problema

El artículo aborda el desafío de la inferencia estadística para Cadenas de Markov Controladas (CMC) finitas en escenarios donde la política de comportamiento que genera los datos puede ser no estacionaria o dependiente de la historia. Este escenario es prevalente en el aprendizaje por refuerzo (RL) fuera de línea, donde los datos son recolectados por una política desconocida $\pi_b$ que no necesariamente satisface las suposiciones de estacionariedad o markovianidad.

Los métodos de bootstrap existentes para cadenas de Markov a menudo dependen de la estacionariedad o de condiciones específicas de mezcla que no se cumplen para CMCs generales con controles dependientes de la historia. Además, los intervalos de confianza (IC) de inserción estándar basados en Teoremas del Límite Central (TLC) requieren estimación de covarianza, lo cual puede degradar el rendimiento en muestras finitas. Los autores identifican dos problemas abiertos:

1. ¿Se puede desarrollar un bootstrap basado en modelo para CMCs finitas sin requerir estacionariedad o markovianidad de la política de control?
2. ¿Se puede establecer la consistencia distribucional de tal estimador de bootstrap y extenderlo a tareas de RL posteriores como Evaluación de Políticas Fuera de Línea (OPE) y Recuperación de Política Óptima (OPR)?

Metodología

Configuración del Modelo y los Datos

Los autores consideran una CMC finita $\{(X_i, A_i)\}_{i \ge 0}$ con espacio de estados $\mathcal{S}$ y espacio de acciones $\mathcal{A}$. El núcleo de transición es $M(a)_{s,t} = P(X_{i+1}=t | X_i=s, A_i=a)$. El conjunto de datos fuera de línea observado $\mathcal{D}_n$ consiste en $K$ episodios de longitud fija $T$ (donde $n=KT$), generados por una política de comportamiento desconocida $\pi_b$. Se permite que la política $\pi_b$ sea no estacionaria y dependiente de la historia.

A partir de $\mathcal{D}_n$, los autores calculan:

• Estimador empírico de transición basado en conteos: $\hat{M}(a)_{s,t} = N(a)_{s,t} / N(a)_s$.
• Política de comportamiento empírica: $\hat{\pi}_b(a|s) = N(a)_s / N_s$.

Procedimiento de Bootstrap Basado en Modelo

El método propuesto construye una CMC de bootstrap $\{(X^*_i, A^*_i)\}_{i \ge 0}$ utilizando el núcleo de transición empírico $\hat{M}$ y la política de comportamiento empírica $\hat{\pi}_b$.

1. Inicialización: Para cada réplica de bootstrap $j$, el proceso comienza en el estado inicial observado del episodio original, $X^{*(k,j)}_0 = X^{(k)}_0$.
2. Simulación: Las transiciones se generan secuencialmente muestreando acciones $A^{*(k,j)}_i \sim \hat{\pi}_b(\cdot | X^{*(k,j)}_i)$ y estados siguientes $X^{*(k,j)}_{i+1} \sim \hat{M}(A^{*(k,j)}_i)_{X^{*(k,j)}_i, \cdot}$.
3. Estimación: A partir del conjunto de datos simulado $\mathcal{D}^*_n$, se calcula un estimador de transición de bootstrap $\hat{M}^*$.
4. Replicación: Este proceso se repite $B$ veces para obtener réplicas de bootstrap $\hat{M}^{*(1)}, \dots, \hat{M}^{*(B)}$.

Aplicaciones Posteriores

El bootstrap se aplica a dos objetivos posteriores:

• Evaluación de Políticas Fuera de Línea (OPE): Estimación de funciones de valor $V_\pi$ y funciones Q $Q_\pi$ para una política objetivo fija $\pi$ resolviendo ecuaciones de Bellman con $\hat{M}$ y $\hat{M}^*$.
• Recuperación de Política Óptima (OPR): Estimación de funciones de valor óptimas $V_\star$ y $Q_\star$ resolviendo ecuaciones de Bellman óptimas con $\hat{M}$ y $\hat{M}^*$.

Los intervalos de confianza se construyen utilizando los cuantiles empíricos de las réplicas de bootstrap (IC percentil) o mediante métodos pivote.

Contribuciones Teóricas Clave

1. Consistencia Distribucional del Bootstrap

El artículo establece los primeros resultados de consistencia distribucional para bootstraps basados en modelo en CMCs finitas con políticas potencialmente no estacionarias o dependientes de la historia.

• Régimen de Cadena Única ($K=1, T \to \infty$): El Teorema 1 prueba que, condicionado a los datos $\mathcal{D}_n$, $\sqrt{n} \text{vec}(\hat{M}^* - \hat{M})$ converge en distribución a un límite gaussiano $N(0, \bar{\Lambda})$, coincidiendo con la distribución asintótica del estimador original $\sqrt{n} \text{vec}(\hat{M} - M)$.
• Régimen Episódico ($T$ fijo, $K \to \infty$): La Proposición 1 extiende este resultado al escenario episódico mediante la incrustación de los episodios en una sola cadena a través de pseudo-transiciones. Confirma que el bootstrap permanece consistente incluso cuando los episodios están separados por reinicios.

Herramientas Técnicas:

• Una nueva Ley de los Grandes Números (LLN) de Bootstrap para conteos de visita ($N^*_s/n \to p_s$ c.s.).
• Una nueva aplicación del Teorema del Límite Central (TLC) de Martingalas para incrementos de transición de bootstrap, utilizando condiciones de mezcla débil (Suposiciones 1–3) para manejar la estructura de dependencia.

2. Validez para OPE y OPR

La Proposición 2 extiende la consistencia distribucional a los estimadores de funciones de valor y Q utilizando el Método Delta.

• Los autores verifican la diferenciabilidad de Hadamard de los operadores de Bellman con respecto a la matriz de bloques de transición.
• Para OPE, las réplicas de bootstrap de $V_\pi$ y $Q_\pi$ convergen a los mismos límites gaussianos que los estimadores originales.
• Para OPR, bajo una condición de no degeneración (brecha estrictamente positiva entre acciones óptimas y subóptimas), las réplicas de bootstrap de $V_\star$ y $Q_\star$ también logran consistencia distribucional.

Resultados Experimentales

Los autores evalúan el rendimiento en muestras finitas en el problema RiverSwim ($S=6, A=2$), un punto de referencia conocido por su exploración difícil debido a frecuencias de visita desequilibradas y políticas óptimas casi degeneradas.

• Configuración: Se realizaron comparaciones contra el bootstrap episódico (Hao et al., 2021) y los IC de TLC de inserción (Zhu et al., 2024; Su et al., 2026) a través de varios tamaños de muestra ($n$) y longitudes de episodio ($T$).
• Hallazgos:
  • Los IC percentil de bootstrap basado en modelo propuestos superan sustancialmente a las líneas base, logrando coberturas cercanas a las nominales (por ejemplo, 0.48–0.54 para 50%, 0.87–0.94 para 90%, 0.92–0.97 para 95%) en regímenes bien muestreados ($n \ge 500$).
  • Las líneas base (bootstrap episódico y TLC de inserción) exhiben una subcobertura sistemática, particularmente en tamaños de muestra pequeños y longitudes de episodio cortas.
  • El bootstrap episódico falla completamente en $n=50$ cuando $T \ge 50$ (colapsando a una cobertura cero) porque un solo episodio elimina la variación del bootstrap.
  • El rendimiento es más débil para pares estado-acción raramente visitados (cerca del estado 6) y horizontes cortos ($T=10$), lo cual es consistente con las restricciones teóricas de normalidad asintótica y no degeneración.

Significado y Limitaciones

Significado:
El artículo proporciona una base teórica rigurosa para el uso de bootstraps basados en modelo en RL fuera de línea, abordando específicamente la brecha donde las políticas de comportamiento son no estacionarias o dependientes de la historia. Demuestra que tales bootstraps producen intervalos de confianza asintóticamente válidos tanto para núcleos de transición como para objetivos de RL posteriores sin requerir estimación explícita de covarianza.

Limitaciones y Direcciones Futuras (según lo declarado por los autores):

• Función de Recompensa: El análisis asume una función de recompensa conocida. Si bien los autores notan que la validez probablemente se mantiene si la estimación de la recompensa converge, los efectos en muestras finitas del error de estimación de la recompensa no se analizan.
• Espacio Estado-Acción: Los resultados actuales se limitan a espacios estado-acción finitos. La extensión a aproximación de funciones o espacios continuos queda para trabajos futuros.
• Régimenes Asintóticos: El análisis episódico asume que $T$ es fijo y $K \to \infty$. La consistencia del bootstrap en el régimen donde $K$ es fijo ($K>1$) y $T \to \infty$ sigue siendo una pregunta abierta.
• Políticas No Estacionarias: Si bien la teoría acomoda políticas no estacionarias, los experimentos numéricos utilizaron principalmente políticas de comportamiento estacionarias; se sugieren experimentos adicionales con políticas no estacionarias.