Resumen Técnico: Límites PAC Minimax para el Aprendizaje en MDPs Contextuales Exógenos

1. Configuración del Problema

Este artículo investiga la complejidad de muestra para el aprendizaje en procesos de decisión de Markov (MDP) tabulares con contextos exógenos i.i.d. El modelo se define mediante una tupla $\mathcal{M} = (\mathcal{X}, \mathcal{Z}, \mathcal{A}, P, r, \mu, \gamma)$, donde:

• $\mathcal{X}$ es un espacio de estados controlados finito.
• $\mathcal{A}$ es un espacio de acciones finito.
• $\mathcal{Z}$ es un espacio de contextos finito.
• $\gamma \in [0, 1)$ es el factor de descuento.
• $P: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to \Delta(\mathcal{X})$ es el núcleo de transición.
• $r: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to [0, 1]$ es la función de recompensa.
• $\mu$ es la distribución desconocida sobre los contextos.

En cada paso de tiempo $t$, se extrae un contexto $Z_t$ de forma independiente de $\mu$ y se revela al agente antes de la selección de la acción. El agente elige $A_t$, recibe una recompensa $r(X_t, A_t, Z_t)$ y transiciona a $X_{t+1} \sim P(\cdot | X_t, A_t, Z_t)$. Crucialmente, el contexto $Z_{t+1}$ es independiente de las acciones del agente y del estado actual, dependiendo únicamente de $\mu$.

Los objetivos de aprendizaje son Evaluación de Política (PE), Estimación del Mejor Valor (BVE) y Extracción de la Mejor Política (BPE). La complejidad de muestra se mide mediante un par $(n_{\text{learn}}, m_{\text{query}})$, que representa el número de llamadas al oráculo realizadas durante una fase de aprendizaje offline y el número de llamadas realizadas durante la fase de decisión (consulta), respectivamente. El artículo considera dos regímenes:

1. Dinámica Conocida: $P$ y $r$ son conocidos; solo $\mu$ es desconocido.
2. Totalmente Desconocido: Tanto $\mu$ como $P$ son desconocidos.

2. Metodología

2.1 Intuición Central: Funciones de Valor Promediadas

La contribución metodológica central es la reducción del problema desde el espacio aumentado $\mathcal{X} \times \mathcal{Z}$ hacia el espacio de estados controlados $\mathcal{X}$. Los autores definen la función de valor promedio $\bar{V}(x) := \mathbb{E}_{Z \sim \mu}[V(x, Z)]$.
Debido a que el siguiente contexto se extrae independientemente de $\mu$, la ecuación de optimalidad de Bellman para el valor promedio $\bar{V}^\star$ depende únicamente del núcleo de transición promediado sobre $\mu$:
$$\bar{V}^\star(x) = \mathbb{E}_{Z \sim \mu} \left[ \max_{a \in \mathcal{A}} \left( r(x, a, Z) + \gamma \sum_{x'} P(x' | x, a, Z) \bar{V}^\star(x') \right) \right]$$
Esta formulación permite al aprendiz estimar un vector en $\mathbb{R}^{|\mathcal{X}|}$ en lugar de $\mathbb{R}^{|\mathcal{X}||\mathcal{Z}|}$, desacoplando efectivamente la complejidad del tamaño del espacio de contextos $|\mathcal{Z}|$.

2.2 Marco Algorítmico: Reducción de Varianza por Mitad (Halving)

El artículo emplea un esquema de iteración de valor con reducción de varianza (adaptado de Sidford et al., 2019) para estimar las funciones de valor promedio. El algoritmo opera en dos fases:

1. Fase Offline (Estimación de Ancla): El algoritmo calcula un límite inferior de alta probabilidad (ancla) para el operador de Bellman aplicado a una estimación de valor inicial. Esto requiere un gran lote de muestras para controlar la varianza de la media empírica.
2. Fase Online/Iterativa (Actualizaciones de Reducción de Varianza): Las iteraciones subsiguientes estiman solo la diferencia entre el actual respaldo de Bellman y el ancla. Al reutilizar las mismas muestras para el término de la diferencia, la varianza se reduce significamente, permitiendo tamaños de muestra más pequeños por iteración.

El algoritmo utiliza una estrategia de "mitad" (halving), llamando repetidamente a una subrutina (HALFERR) que reduce a la mitad el límite de error $u$ hasta alcanzar la precisión objetivo $\epsilon$.

2.3 Manejo de Dinámicas Desconocidas

En el régimen totalmente desconocido, el algoritmo no puede calcular el respaldo de Bellman exactamente incluso con un contexto muestreado. En su lugar, para cada contexto $Z$ muestreado, el algoritmo extrae una muestra de transición $X' \sim P(\cdot | x, \pi(x, Z), Z)$ para formar una estimación insesgada del respaldo. Esto introduce un término de varianza adicional relacionado con el núcleo de transición, el cual es acotado rigurosamente mediante una descomposición de martingala que tiene en cuenta tanto la aleatoriedad del contexto como la de la transición.

3. Resultados Clave

3.1 Dinámica Conocida, Distribución de Contexto Desconocida ($P, r$ conocidos, $\mu$ desconocido)

Cuando el núcleo de transición y las recompensas son conocidos, el artículo establece que la complejidad de muestra es independiente del tamaño del espacio de contextos $|\mathcal{Z}|$.

• Complejidad: El algoritmo logra los objetivos con $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(\beta^3/\epsilon^2), 0)$, donde $\beta = (1-\gamma)^{-1}$.
• Optimalidad: Se demuestra un límite inferior minimax de $\Omega(\beta^3/\epsilon^2)$, lo que muestra que el límite superior es ajustado (tight) salvo por factores logarítmicos.
• Implicación: El aprendiz no necesita estimar valores para cada par $(x, z)$; estimar el valor promedio $\bar{V}$ es suficiente. La fase de consulta no requiere muestras adicionales ($m_{\text{query}}=0$) porque el levantamiento (lift) de $\bar{V}$ a $V(x, z)$ es un respaldo de Bellman determinista usando $P$ y $r$ conocidos.

3.2 Aplicación a la Mirada Anticipada Perfecta de un Paso (Perfect One-Step Lookahead)

El marco se aplica al escenario de mirada anticipada de transición perfecta de un paso (donde el agente observa todos los posibles estados siguientes para todas las acciones antes de actuar).

• Se demuestra que este escenario es un caso especial de los MDP contextuales exógenos donde el espacio de contexto es el conjunto de todos los tensores de transición posibles.
• El resultado arroja una complejidad de muestra de $\tilde{O}(\beta^3/\epsilon^2)$ muestras de mirada anticipada.
• En términos de transiciones tabulares individuales, esto corresponde a $\tilde{O}(\beta^3 |\mathcal{X}||\mathcal{A}|/\epsilon^2)$, mejorando el límite previo de Lu et al. (2025) por un factor de $\beta$.

3.3 Régimen Totalmente Desconocido ($P$ y $\mu$ desconocidos)

Cuando tanto la dinámica como la distribución del contexto son desconocidas, el artículo se centra en la Evaluación de Política (PE).

• Complejidad: El algoritmo logra $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2), \tilde{O}(\beta^2/\epsilon^2))$.
• Compromiso (Trade-off): La fase offline aprende el valor promedio $\bar{V}^\pi$ (costando $|\mathcal{X}|$ transiciones por muestra de contexto). La fase de consulta estima la expectativa de la transición de un paso final en el $(x, z)$ realizado utilizando muestras frescas.
• Límites Inferiores: El artículo demuestra límites inferiores coincidentes, demostrando que:
  • $m_{\text{query}} = \Omega(\beta^2/\epsilon^2)$ es necesario para la precisión en el tiempo de decisión.
  • $n_{\text{learn}} + |\mathcal{X}| m_{\text{query}} = \Omega(|\mathcal{X}|\beta^3/\epsilon^2)$ es necesario para el aprendizaje offline.
• Significado: Incluso en el régimen totalmente desconocido, la complejidad sigue siendo independiente de $|\mathcal{Z}|$. Las dinámicas desconocidas no fuerzan la estimación en el espacio aumentado; solo introducen estocasticidad en el "levantamiento" de decisión de $\bar{V}$ a $V(x, z)$.

4. Significancia y Reivindicaciones

El artículo afirma proporcionar los primeros límites PAC minimax-óptimos para el aprendizaje en MDPs contextuales exógenos. Sus principales contribuciones son:

1. Desacoplamiento del Tamaño del Contexto: Demuestra que el precio estadístico de los espacios de contexto grandes es evitable. La complejidad de la muestra depende del espacio de estados controlado $|\mathcal{X}|$ pero no del espacio de contextos $|\mathcal{Z}|$.
2. Tasas Óptimas: Se demuestra que las tasas derivadas ($\tilde{O}(\beta^3/\epsilon^2)$ para dinámica conocida y $\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2)$ para totalmente desconocida) son minimax-óptimas salvo por factores logarítmicos.
3. Marco Unificado: El marco subsume y mejora resultados existentes de mirada anticipada perfecta de un paso y proporciona un análisis riguroso del compromiso de muestras offline/online.

Los autores señalan que, si bien el límite inferior es ajustado en el punto puramente online ($n_{\text{learn}}=0$) y en el punto de oráculo reutilizable (su algoritmo propuesto), la ajustabilidad del límite para compromisos intermedios sigue siendo una pregunta abierta. Además, la extensión de estos resultados a la Extracción de la Mejor Política (BPE) en el régimen totalmente desconocido se deja como trabajo futuro debido a la dificultad de manejar el sesgo de selección al estimar el máximo sobre las acciones a partir de muestras de transición.