Characterizing Bias in Post-Bandit Inference under Index Algorithms

Resumen Técnico: Caracterización del Sesgo en la Inferencia Post-Bandido bajo Algoritmos de Índice

Planteamiento del Problema
El artículo aborda el desafío estadístico de realizar inferencia sobre datos generados por algoritmos de Bandidos Multibrazo (MAB). A diferencia de los datos convencionales de distribución independiente e idénticamente distribuida (i.i.d.), los datos de bandidos se recolectan de forma adaptativa, creando un bucle de retroalimentación donde las decisiones de asignación dependen de las observaciones pasadas. Esta adaptatividad induce un sesgo de selección sistemático en el estimador de la media muestral, $\bar{X}_a(N_a(T))$, lo que puede distorsionar los intervalos de confianza y las pruebas de hipótesis. Si bien la literatura previa ha establecido que este sesgo existe (p. ej., Nie et al., 2018) y ha proporcionado límites asintóticos generales (p. ej., Shin et al., 2019a,b; Russo y Zou, 2016), existe una falta de caracterizaciones nítidas de primer orden de este sesgo para algoritmos de índice plenamente adaptativos y ampliamente utilizados como UCB1. La pregunta central de investigación es determinar la magnitud precisa del sesgo de la media muestral y el sesgo asociado del estadístico Z bajo algoritmos de índice canónicos, y comprender cómo las elecciones de diseño algorítmico influyen en este sesgo.

Metodología
Los autores se centran en los algoritmos de índice estables, una clase que incluye el canonical Upper Confidence Bound (UCB1) y sus generalizaciones. La innovación metodológica central es una nueva aproximación de fluido empírico de la dinámica de muestreo del algoritmo.

1. Aproximación de Fluido: Los autores definen primero una aproximación de fluido determinista, $n_T$, reemplazando las medias muestrales empíricas por medias poblacionales ($\mu$) en las ecuaciones de igualación de índices. Esto captura el comportamiento de asignación de primer orden pero ignora las fluctuaciones estocásticas.
2. Aproximación de Fluido Empírico: Para capturar la correlación crítica entre los conteos de extracciones (pulls) y las fluctuaciones de recompensa que impulsa el sesgo, los autores introducen una segunda aproximación de segundo orden, $\tilde{n}_T$. Esta se construye reintroduciendo las medias muestrales evaluadas en los conteos de asignación de fluido ($\bar{X}_a(n_{a,T})$) en las ecuaciones de igualación de índices.
3. Cantidad Clave: El análisis identifica una cantidad crítica dependiente del algoritmo denominada tasa de exploración efectiva, denotada como $\Gamma_{a,T}$. Para una función de índice $I_t(x, n)$, esto se define como $\Gamma_t(x, n) := -2n^{3/2} \frac{\partial_n I_t(x, n)}{\partial_x I_t(x, n)}$. Esta tasa cuantifica qué tan sensible es la asignación a las perturbaciones de la media muestral; una tasa más alta implica menor sensibilidad y, por lo tanto, menor sesgo.
4. Condiciones de Estabilidad: Los resultados teóricos dependen de tres condiciones: regularidad de la función de índice (suavidad y monotonicidad), condiciones de escalamiento de fluido (que aseguran que los brazos subóptimos sean extraídos lo suficiente para la concentración) y condiciones de estabilidad (que aseguran que los conteos de extracciones reales se concentren alrededor de la aproximación de fluido empírica).

Contribuciones Clave y Resultados

• Caracterización Nítida del Sesgo: El artículo deriva expresiones explícitas de orden principal para el sesgo de la media muestral y del estadístico Z a medida que $T \to \infty$.

  • Para cualquier brazo $a$ que no sea el brazo óptimo único, el sesgo estandarizado del estadístico Z, $E[Z_{a,T}]$, converge a:
    $$E[Z_{a,T}] \approx -\left(1 - \frac{1}{|O|}\mathbb{1}\{a \in O\}\right) \frac{\sigma_a}{\Gamma_{a,T}}$$
    donde $O$ es el conjunto de brazos óptimos y $\sigma_a$ es la desviación estándar de la recompensa.
  • Para el brazo óptimo único, el sesgo es de un orden mucho menor, decayendo polinómicamente rápido (por ejemplo, $O(f_T/T)$ para UCB generalizado), mientras que los brazos óptimos no únicos exhiben un sesgo que decae a la tasa de $1/\Gamma_{a,T}$.

• Aplicación a UCB Generalizado: Especializando en algoritmos UCB generalizados con índice $I_t(x, n) = x + f_t/\sqrt{n}$, la tasa de exploración efectiva es $\Gamma_{a,T} = f_T$.

  • Caso UCB1: Para el UCB1 estándar, $f_T = \sqrt{2 \log T}$. Consecuentemente, el sesgo estandarizado decae a la tasa extremadamente lenta de $1/\sqrt{\log T}$. Esto implica que incluso para un $T$ grande, el sesgo sigue siendo sustancial en la escala de la inferencia.
  • Caso Generalizado: El sesgo escala como $1/f_T$.

• Compromiso entre Regret y Sesgo (Regret-Bias Trade-off): Los autores establecen un compromiso fundamental entre la minimización del regret y el sesgo de inferencia.

  • El regret para el UCB generalizado escala como $f_T^2$.
  • El sesgo escala como $1/f_T$.
  • Por lo tanto, el sesgo escala como $1/\sqrt{\text{Regret}}$. Los algoritmos diseñados para minimizar el regret agresivamente (como UCB1 con un $f_T$ de crecimiento lento) incurren en un mayor sesgo. Por el contrario, los algoritmos más exploratorios (con un $f_T$ de crecimiento más rápido) reducen el sesgo pero aumentan el regret.

• Origen Algorítmico del Sesgo: Los resultados revelan que el sesgo es impulsado por la "tasa de exploración efectiva". El sesgo surge porque el algoritmo ajusta las asignaciones para igualar los índices; cuando la media muestral de un brazo fluctúa al alza, el algoritmo lo extrae con más frecuencia, creando una correlación positiva entre el número de extracciones y la media muestral. Esta correlación positiva resulta en un sesgo negativo (hacia abajo) en el estimador respecto a la media real, como se refleja en el signo negativo de la expresión de orden principal.

Significancia y Reivindicaciones
El artículo afirma proporcionar la primera caracterización nítida de orden principal del sesgo para algoritmos de índice estables y plenamente adaptativos. Su significancia radica en:

1. Cuantificar el Costo Inferencial: Demuestra que para algoritmos estándar como UCB1, el sesgo decae tan lentamente ($1/\sqrt{\log T}$) que puede dominar el error estándar en entornos de inferencia práctica, desafiando la validez de la inferencia post-bandido estándar sin corrección.
2. Perspectiva Algorítmica: Clarifica que el sesgo no es meramente una función de la adaptatividad, sino que está determinado estructuralmente por la forma específica de la función de índice (a través de la tasa de exploración efectiva).
3. Implicaciones de Diseño: Resalta una distincción cualitativa entre instancias con un brazo óptimo único (bajo sesgo) y aquellas con múltiples brazos óptimos (alto sesgo), y mapea explícitamente el compromiso entre minimizar el regret y minimizar el sesgo.
4. Contribución Metodológica: El marco de la aproximación de fluido empírico se presenta como una herramienta tratable para analizar las complejas dependencias temporales en el muestreo adaptativo, potencialmente aplicable a otras propiedades inferenciales de los algoritmos de bandidos.

Los autores señalan que sus resultados son específicos para algoritmos de índice estables y no se aplican directamente a algoritmos inestables (como Thompson Sampling o $\epsilon$-greedy) o métodos no basados en índices, sugiriendo estos como direcciones para trabajos futuros. También enfatizan que, si bien la fórmula del sesgo sugiere correcciones naturales, la construcción de intervalos de confianza prácticos con un mejor desempeño de muestra finita sigue siendo una tarea abierta.