Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

Resumen Técnico: Exploración Pura Más Allá de la Retroalimentación de Recompensa: El Papel del Contexto Post-Acción

Formulación del Problema
Este artículo introduce una nueva variante del problema de Identificación del Mejor Brazo (BAI, por sus siglas en inglés) dentro del escenario de confianza fija de los banditos multi-brazo estocásticos (MAB). En este escenario, denominado "BAI con contexto post-acción", el agente selecciona una acción (brazo) $X$ y observa no solo la recompensa $Y$, sino también un contexto intermedio post-acción $Z$. El contexto $Z$ se genera como consecuencia de la acción elegida, lo que distingue este problema de los banditos contextuales estándar donde el contexto precede a la acción.

Los autores analizan dos regímenes estructurales definidos por la relación causal entre acción, contexto y recompensa:

1. Contexto Separador: La recompensa $Y$ depende únicamente del contexto $Z$, haciendo que $X$ e $Y$ sean condicionalmente independientes dado $Z$ ($P(Y|X, Z) = P(Y|Z)$). En este caso, la distribución de recompensas está determinada enteramente por el contexto observado.
2. Contexto No Separador: La recompensa $Y$ depende tanto de la acción $X$ como del contexto $Z$ ($P(Y|X, Z) \neq P(Y|Z)$). Aquí, el contexto proporciona información adicional pero no es un estadístico suficiente para la recompensa.

El objetivo es identificar el brazo con la mayor recompensa esperada con una probabilidad de error de como máximo $\delta$, minimizando al mismo tiempo la complejidad de la muestra (el número de rondas requeridas).

Metodología y Algoritmos
El artículo deriva cotas inferiores dependientes de la instancia sobre la complejidad de la muestra para ambos escenarios y propone algoritmos que alcanzan asintóticamente estas cotas.

• Escenario Separador:

  • Cota Inferior: Los autores derivan una cota inferior que depende de las frecuencias de los contextos observados en lugar de las frecuencias de los brazos extraídos. Esto se debe a que, en el escenario separador, cualquier observación de un contexto específico $Z=j$ proporciona información sobre la recompensa media de ese contexto, independientemente de qué brazo lo generó.
  • Algoritmo (STS): El algoritmo propuesto "Rastrear y Detener Separador" (STS, por sus siglas en inglés) utiliza una regla de muestreo novedosa llamada Rastreo-G. A diferencia de los métodos tradicionales que rastrean las frecuencias óptimas de extracción de brazos, el Rastreo-G rastrea las frecuencias óptimas de observación de contextos. Trata el problema como una tarea de aprendizaje fuera de política activa donde el agente selecciona una distribución sobre los brazos para lograr una distribución objetivo sobre los contextos. El algoritmo resuelve un problema de optimización convexa para encontrar las frecuencias óptimas de contexto y utiliza una proyección geométrica para seleccionar la siguiente distribución de brazos, asegurando que las frecuencias de contexto observadas converjan al objetivo óptimo.

• Escenario No Separador:

  • Cota Inferior: La cota inferior derivada tiene en cuenta la distribución conjunta de acciones y contextos.
  • Algoritmo (NSTS): El algoritmo "Rastrear y Detener No Separador" (NSTS, por sus siglas en inglés) extiende el marco clásico de Rastrear y Detener. Emplea el Rastreo-D para estimar y rastrear las proporciones óptimas de extraer brazos específicos, utilizando la información conjunta de las acciones y sus contextos resultantes para refinar las estimaciones de las medias de recompensa.

Contribuciones Clave

1. Definición del Problema: Formalización del BAI con contexto post-acción, distinguiendo entre regímenes estructurales separadores y no separadores.
2. Cotas Teóricas: Derivación de cotas inferiores dependientes de la instancia sobre la complejidad de la muestra para ambos regímenes. Se demuestra que la cota separadora es estrictamente más ajustada que las cotas derivadas de ignorar el contexto.
3. Diseño de Algoritmos:
   • Introducción del Rastreo-G, una regla de muestreo que optimiza directamente las frecuencias de observación de contextos en el escenario separador, aprovechando la geometría del espacio de contextos.
   • Extensión del marco de Rastrear y Detener al escenario no separador (NSTS).
4. Análisis de Suboptimalidad: Demostración teórica y empírica de que los algoritmos que ignoran el contexto post-acción (como el Rastrear y Detener estándar) son estrictamente subóptimos. En el escenario separador, ignorar el contexto puede conducir a aumentos arbitrariamente grandes en la complejidad de la muestra, incluso cuando las brechas de recompensa son pequeñas, debido a que no aprovecha la estructura de independencia condicional.
5. Análisis de Reducción: El artículo analiza la reducción del problema separador a banditos lineales, mostrando que tales reducciones aumentan la cota inferior de complejidad de la muestra en comparación con el enfoque directo propuesto.

Resultados

• Teóricos: Se demuestra que los algoritmos propuestos (STS y NSTS) son $\delta$-correctos y alcanzan optimalidad asintótica, coincidiendo con las cotas inferiores derivadas cuando $\delta \to 0$.
• Empíricos: Los experimentos con datos sintéticos y datos del mundo real (registros de recomendación de KuaiSAR) demuestran ganancias significativas en el rendimiento.
  • En el escenario separador, STS supera drásticamente a las líneas base (Rastrear y Detener y Rastrear y Detener Perezoso), las cuales a menudo fallan en detenerse dentro de horizontes temporales razonables.
  • En el escenario no separador, NSTS reduce significativamente el número de muestras requeridas en comparación con Rastrear y Detener, que ignora la información contextual.
  • Los gráficos de rastreo confirman que STS converge a las frecuencias óptimas de contexto, mientras que las líneas base fallan en alinearse con la estrategia óptima.

Significado y Afirmaciones
El artículo afirma que aprovechar el contexto post-acción altera fundamentalmente la estrategia óptima para la exploración pura. Los autores enfatizan que en escenarios donde están disponibles observaciones intermedias (mediadores), ignorarlas conduce a una ineficiencia sustancial. Específicamente, en el escenario separador, la capacidad de agrupar información a través de diferentes brazos que generan el mismo contexto permite una identificación mucho más rápida del mejor brazo. El trabajo destaca que los algoritmos estándar de BAI no son meramente subóptimos, sino que pueden ser arbitrariamente ineficientes en estos entornos estructurados. El artículo concluye que el trabajo futuro podría abordar el caso donde la matriz de probabilidad de contexto es desconocida, señalando que esto introduce desafíos de no convexidad que dificultan el diseño de algoritmos eficientes.