Resumen Técnico: Ataques Adversariales Prácticos a Bandidos Estocásticos mediante Inyección de Datos Falsos

1. Declaración del Problema

Los algoritmos de bandidos de múltiples brazos (MAB) son fundamentales para los sistemas de toma de decisiones en línea, equilibrando la exploración y la explotación en aplicaciones como la recomendación personalizada, la publicidad en línea y los ensayos clínicos. Aunque investigaciones anteriores han establecido que los algoritmos MAB son vulnerables a ataques adversariales, los modelos de amenazas existentes se basan en suposiciones poco realistas que limitan su relevancia para los sistemas del mundo real.

Específicamente, trabajos anteriores (por ejemplo, Jun et al., 2018; Liu y Shroff, 2019; Zuo, 2024) adoptan predominantemente un modelo de perturbación de retroalimentación. En este modelo, el atacante observa el brazo elegido por el aprendiz y su recompensa en cada ronda, y luego modifica arbitrariamente la recompensa antes de que esta sea revelada al aprendiz. Este modelo otorga al atacante control total sobre el canal de retroalimentación en cada paso de tiempo y asume capacidades de perturbación ilimitadas.

En la práctica, tales capacidades suelen ser inviables. Por ejemplo, en una plataforma de recomendación de restaurantes, un adversario no puede sobrescribir continuamente las calificaciones genuinas de miles de clientes reales. En cambio, los ataques realistas implican crear cuentas falsas para inyectar reseñas fabricadas o interacciones sintéticas (por ejemplo, fraude de clics). Estos ataques añaden datos falsos en lugar de alterar datos existentes, están sujetos a la detección a nivel de sistema o a límites de recursos, y deben ajustarse a rangos de retroalimentación válidos (por ejemplo, calificaciones de 1 a 5 estrellas).

Este artículo aborda la brecha entre los modelos teóricos de ataque y las restricciones prácticas proponiendo un nuevo modelo de amenaza: Inyección de Datos Falsos. El desafío central es diseñar estrategias de ataque que puedan engañar a un aprendiz para que seleccione un brazo subóptimo específico (objetivo) en casi todas las rondas, incurriendo solo en un costo sublineal, bajo las siguientes restricciones:

1. Sin modificación de la retroalimentación genuina: El atacante no puede sobrescribir los datos reales de los usuarios.
2. Recompensas acotadas: Las recompensas falsas inyectadas deben estar dentro del rango de retroalimentación válido $[r_l, r_u]$.
3. Restricciones temporales: El atacante puede estar limitado en la cantidad de muestras falsas que puede inyectar por ronda (tamaño del lote) o en la frecuencia de inyección.

2. Metodología y Conceptos Clave

2.1 El Modelo de Amenaza de Inyección de Datos Falsos

Los autores formalizan un escenario donde el atacante inyecta $N_F$ muestras de datos falsos $\{(a^F_s, r^F_s)\}$ en el historial del aprendiz. El aprendiz trata estas muestras inyectadas de manera indistinguible de las interacciones legítimas, actualizando las medias empíricas, los conteos de extracciones y los contadores internos de rondas en consecuencia.

• Costo del Ataque: Definido como $C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$.
• Criterio de Éxito: Un ataque es exitoso si induce al aprendiz a seleccionar el brazo objetivo en $T - o(T)$ rondas, asegurando al mismo tiempo que $C_F(T) = o(T)$.

2.2 El Principio de Supresión

La idea técnica central es el Principio de Supresión. En lugar de perturbar continuamente las recompensas, el atacante busca inyectar suficiente retroalimentación falsa acotada para suprimir la estimación empírica de un brazo no objetivo por debajo de un umbral inferior estable del brazo objetivo. Una vez que un brazo no objetivo está suficientemente suprimido, el propio mecanismo de exploración del aprendiz evita que sea seleccionado nuevamente durante un período significativo.

El Lema de Supresión Exponencial (para UCB)

Para el algoritmo de Límite Superior de Confianza (UCB), los autores demuestran que si un brazo no objetivo $i$ es extraído suficientemente ($N_i(t) \geq \log T/\delta_0^2$) y su media empírica se reduce por debajo de un límite inferior específico $\hat{\ell}_K(t)$ del brazo objetivo $K$, entonces el brazo $i$ no será seleccionado nuevamente hasta al menos la ronda $\exp(N_i(t)\delta_0^2)$ con alta probabilidad. Esta "supresión exponencial" permite al atacante lograr una manipulación a largo plazo con un único evento de inyección por brazo.

2.3 Estrategias de Ataque

A. Inyección Simultánea (SI)

Diseñada para un escenario donde el atacante puede inyectar datos según sea necesario sin límites estrictos por ronda.

• Mecanismo: Para cada brazo no objetivo $i$, el atacante espera hasta que haya sido extraído $\lceil \log T/\delta_0^2 \rceil$ veces. Luego, el atacante inyecta un lote de muestras falsas con la recompensa mínima válida $r_l$ para reducir la media empírica del brazo por debajo del límite inferior de confianza del brazo objetivo.
• Resultado: Esto fuerza al algoritmo UCB a seleccionar el brazo objetivo durante $T - o(T)$ rondas con un costo acumulativo de $\tilde{O}(K\sigma\sqrt{\log T})$, coincidiendo con los límites inferiores conocidos.

B. Inyección Acotada Periódica (PBI)

Diseñada para restricciones realistas donde el atacante enfrenta un límite de tamaño de lote ($f$ muestras por ronda) y debe evitar activar la detección de anomalías.

• Mecanismo: En lugar de una única inyección grande, el atacante distribuye las muestras falsas necesarias a lo largo del tiempo. Una vez que un brazo no objetivo alcanza el umbral de extracción, el atacante calcula el número total de muestras necesarias y un período de "tiempo de espera" $R_i$. El atacante inyecta lotes de tamaño $f$ periódicamente, separados por $R_i$ rondas, asegurando que el brazo permanezca suprimido entre inyecciones.
• Resultado: PBI logra ataques exitosos con costo sublineal incluso bajo restricciones temporales y de magnitud estrictas, equilibrando el sigilo con la eficacia.

C. Marco General de Supresión Acotada

Los autores extienden estos hallazgos más allá de UCB a una clase de algoritmos denominados Supresión Acotada. Un algoritmo es de supresión acotada si, una vez que un brazo subóptimo está empíricamente dominado por el brazo objetivo, el algoritmo extrae ese brazo solo un número acotado de veces adicionales.

• Este marco se aplica a los algoritmos de Muestreo de Thompson y $\epsilon$-greedy.
• La estrategia de ataque implica inyectar el número mínimo de muestras falsas para satisfacer una condición donde la media empírica del brazo no objetivo se mantiene por debajo del umbral del objetivo, aprovechando el límite inherente del algoritmo en las extracciones posteriores a la supresión.

3. Contribuciones Clave

1. Nuevo Modelo de Amenaza: Introducción de la Inyección de Datos Falsos, que refleja restricciones realistas (recompensas acotadas, frecuencia de inyección limitada, incapacidad de sobrescribir datos genuinos) pasadas por alto por los modelos anteriores de perturbación de retroalimentación.
2. Principio de Supresión: Formalización de un mecanismo donde las inyecciones falsas acotadas pueden suprimir permanentemente los brazos no objetivos, convirtiendo el ataque en un problema de establecer y mantener la supresión en lugar de una perturbación continua.
3. Estrategias Algorítmicas:
   • Inyección Simultánea (SI): Una estrategia óptima para UCB bajo restricciones mínimas.
   • Inyección Acotada Periódica (PBI): Una estrategia robusta para UCB bajo restricciones de tamaño de lote y temporales.
   • Marco General: Extensión del análisis de supresión al Muestreo de Thompson y a los algoritmos $\epsilon$-greedy.
4. Garantías Teóricas: Demostración de que estos ataques pueden engañar a los aprendices para que seleccionen un brazo objetivo en $T - o(T)$ rondas con un costo de ataque sublineal ($o(T)$), incluso con valores de recompensa acotados.
5. Validación Empírica: Experimentos con datos sintéticos y el conjunto de datos MovieLens 25M que demuestran que datos falsos dispersos y acotados pueden sesgar significativamente a los aprendices de bandidos en la práctica.

4. Resultados Experimentales

Los autores evaluaron sus estrategias en:

• Datos Sintéticos: Distribuciones de recompensa gaussianas con $K=10$ brazos.
• Datos del Mundo Real: Conjunto de datos MovieLens 25M, simulando un sistema de recomendación con 10 brazos (películas) e interacciones de usuarios.

Hallazgos Clave:

• Eficacia: Tanto SI como PBI forzaron exitosamente a los aprendices de UCB y Muestreo de Thompson a seleccionar el brazo objetivo en más del 95% de las rondas después de una fase inicial de supresión.
• Eficiencia de Costo: PBI logró un rendimiento comparable a SI pero con costos de ataque más bajos en escenarios de horizonte largo al distribuir las inyecciones a lo largo del tiempo.
• Comparación con Líneas Base: Una línea base heurística que inyectaba muestras aleatoriamente (proporcional al tiempo restante) no logró converger al aprendiz hacia el brazo objetivo, destacando la importancia crítica del cronograma de inyección y el principio de supresión.
• Robustez ante Restricciones: PBI demostró que incluso con límites estrictos en el tamaño del lote ($f=5$ o $f=10$), el ataque sigue siendo efectivo, mientras que las estrategias ilimitadas (como la Inyección Mínima) incurren en el costo teórico más bajo pero pueden ser menos prácticas en entornos con alta detección.

5. Significado y Limitaciones

Significado:
El artículo cierra la brecha entre la robustez adversarial teórica y la seguridad práctica en el aprendizaje en línea. Demuestra que la suposición de "manipulación de recompensas ilimitada por ronda" sobreestima significativamente la dificultad de atacar sistemas del mundo real. Al mostrar que datos falsos dispersos, acotados y distribuidos temporalmente pueden subvertir los algoritmos estándar de bandidos, el trabajo revela una vulnerabilidad crítica en los sistemas de toma de decisiones secuenciales utilizados en dominios de alto riesgo. El Lema de Supresión propuesto proporciona una herramienta general para analizar vulnerabilidades en algoritmos que dependen de medias empíricas y bonos de exploración.

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

• Aprendiz Pasivo: El análisis asume un aprendiz pasivo que procesa toda la retroalimentación sin mecanismos de defensa (por ejemplo, filtrado o auditoría).
• Entorno Estocástico: El marco se limita actualmente a bandidos estocásticos; extenderlo a bandidos contextuales o aprendizaje por refuerzo sigue siendo un problema abierto.
• Riesgos de Detección: El modelo actual no captura explícitamente la interacción dinámica entre atacantes y aprendices adaptativos que emplean detección de anomalías o auditoría a nivel de brazo.

Los autores concluyen que, aunque sus resultados exponen una brecha entre las garantías de robustez clásicas y la seguridad práctica, el trabajo futuro debe investigar defensas como la detección de anomalías y la interacción dinámica entre atacantes y aprendices adaptativos y defensivos.