Active Context Selection Improves Simple Regret in Contextual Bandits

Resumen Técnico: La Selección Activa de Contextos Mejora el Arrepentimiento Simple en Banditos Contextuales

Formulación del Problema
Este artículo investiga el problema del bandito contextual de múltiples brazos dentro de un espacio de contextos finito, donde los contextos representan subpoblaciones distintas (por ejemplo, grupos demográficos). El objetivo de aprendizaje se define mediante el arrepentimiento simple ponderado por contexto: tras un presupuesto experimental fijo $T$, el aprendiz debe recomendar un único tratamiento óptimo para cada subpoblación. La métrica de rendimiento es la brecha esperada entre los tratamientos óptimo y recomendado, ponderada por el vector de distribución de la población $p$ sobre las $k$ subpoblaciones.

El estudio distingue entre dos regímenes de muestreo:

1. Muestreo Pasivo: Los contextos se revelan aleatoriamente según la distribución fija $p$, y el aprendiz solo elige el tratamiento.
2. Muestreo Activo: El aprendiz puede elegir activamente tanto la subpoblación (contexto) como el tratamiento en cada ronda.

El análisis asume un escenario de peor caso respecto a las distribuciones de recompensa, pero permanece dependiente de la instancia con respecto a la distribución de contextos $p$. El artículo se centra en el régimen "rico en datos" donde el horizonte $T$ es significativamente mayor que el número de tratamientos $n$, el número de contextos $k$ y el inverso de la probabilidad mínima de contexto.

Metodología y Marco Teórico

• Asignación Óptima para $p$ Conocida:
  Cuando la distribución de subpoblaciones $p$ es conocida, los autores caracterizan la asignación óptima del presupuesto experimental. Demuestran que, para el criterio de arrepentimiento simple de peor caso, las políticas libres de historia (donde la selección de contexto depende únicamente de $p$ y no del historial observado) son suficientes para lograr la tasa minimax.

  • Tasa Pasiva: Bajo muestreo pasivo, el arrepentimiento escala como $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$.
  • Tasa Activa: Bajo muestreo activo, la estrategia óptima asigna muestras a la subpoblación $j$ con una probabilidad proporcional a $p_j^{2/3}$. Esto logra una tasa de arrepentimiento de $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3})$.
  • La Brecha: El factor de mejora del muestreo activo sobre el pasivo se caracteriza por la relación $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$. Los autores muestran que, para distribuciones altamente no uniformes, esta brecha puede ser tan grande como $\Theta(k^{1/4})$. La asignación activa óptima desplaza las probabilidades de muestreo hacia una distribución más uniforme en comparación con $p$, aumentando así la exploración en subpoblaciones más pequeñas.

• Intervenciones con Presupuesto:
  El artículo extiende el análisis a escenarios donde el muestreo activo es costoso, permitiendo al aprendiz elegir la subpoblación solo en una fracción $\alpha$ de las rondas. Los autores formulan un problema de optimización restringida para minimizar el arrepentimiento sujeto a la restricción de que la asignación $q$ debe satisfacer $q_j \geq (1-\alpha)p_j$. Derivan una estructura de umbral para la asignación óptima: las subpoblaciones con un $p_j$ grande pueden mantener su asignación pasiva si el presupuesto es insuficiente para mejorarlas, mientras que otras se impulsan hacia la proporción $p_j^{2/3}$. Identifican un presupuesto mínimo $\alpha_{\min}(p)$ necesario para recuperar la tasa óptima totalmente activa.

• $p$ Desconocida (El Algoritmo EETC):
  Cuando $p$ es desconocida, una política totalmente activa no puede simplemente adoptar la regla $p^{2/3}$. Los autores proponen el algoritmo Explorar-Explorar-Comprometer (EETC), que equilibra tres fases:

  1. Exploración Pasiva Inicial: El aprendiz actúa pasivamente para estimar $p$.
  2. Muestreo Pasivo Continuo: El aprendiz continúa el muestreo pasivo hasta que el presupuesto restante es suficiente para implementar la asignación activa óptima basada en la estimación actual.
  3. Compromiso: El aprendiz cambia al muestreo activo utilizando la distribución estimada para asignar las rondas restantes.
     El análisis teórico muestra que, para horizontes grandes, EETC logra la misma tasa de arrepentimiento simple que la política activa totalmente óptima con $p$ conocida, hasta factores constantes.

Resultados Clave y Experimentos

• Garantías Teóricas: El artículo establece tasas de arrepentimiento ajustadas tanto para $p$ conocida como desconocida. Prueba que la selección activa de contextos mejora estrictamente el muestreo pasivo, siendo la magnitud de la mejora dependiente de la heterogeneidad de la distribución de contextos.
• Experimentos Sintéticos: Los experimentos con datos sintéticos confirman que la brecha de arrepentimiento entre las políticas pasivas y activas se amplía a medida que aumenta el número de subpoblaciones $k$, alineándose con el límite teórico $\Theta(k^{1/4})$. Se demuestra que el algoritmo EETC coincide estrechamente con el rendimiento de la política activa óptima (con $p$ conocida).
• Datos del Mundo Real (MovieLens): Los autores evaluaron sus métodos en el conjunto de datos MovieLens 1M, tratando las recomendaciones de películas como tratamientos y los grupos demográficos como subpoblaciones. Los resultados indican que las políticas pasivas generan el arrepentimiento más alto. Tanto la política activa con $p$ conocida como EETC superan significativamente la línea base pasiva, acercándose EETC al rendimiento de la política activa óptima a medida que aumenta el horizonte.

Significado y Afirmaciones
El artículo afirma cuantificar el valor específico de seleccionar activamente subpoblaciones en el diseño experimental y el aprendizaje de políticas. Su contribución principal es demostrar que la selección activa de subpoblaciones siempre mejora el rendimiento sobre el muestreo pasivo, siendo la ganancia sustancial cuando la distribución de la población está sesgada.

Los autores enfatizan que su trabajo cierra la brecha entre los banditos contextuales estándar (donde los contextos son ambientales) y el diseño experimental (donde el experimentador controla la muestra). Al caracterizar la regla de asignación óptima ($q_j \propto p_j^{2/3}$) y proporcionar un algoritmo (EETC) que se adapta a distribuciones desconocidas sin sacrificar la optimalidad asintótica, el artículo ofrece un marco riguroso para la asignación eficiente de recursos en poblaciones heterogéneas. El trabajo sugiere que, en escenarios donde el reclutamiento dirigido o el muestreo controlado son factibles, ignorar la capacidad de seleccionar contextos conduce a recomendaciones de tratamiento subóptimas.