Differentially Private Best-Arm Identification

1. Introducción y Problema

El artículo aborda el problema de la Identificación del Mejor Brazo (BAI, por sus siglas en inglés) en el contexto de Confianza Fija (FC-BAI) bajo restricciones de Privacidad Diferencial (DP).

• Contexto: En problemas de BAI, un agente interactúa con $K$ distribuciones de recompensa desconocidas (brazos) para identificar aquel con la mayor recompensa esperada ($a^*$). En aplicaciones sensibles como ensayos clínicos adaptativos, ajuste de hiperparámetros o estudios de usuarios, los datos de recompensa pueden revelar información privada de los individuos.
• Objetivo: Diseñar algoritmos que garanticen una recomendación $\delta$-correcta (probabilidad de error $\leq \delta$) mientras satisfacen la privacidad diferencial, minimizando la complejidad de la muestra (número de muestras necesarias).
• Modelos de Privacidad Estudiados:
  1. $\epsilon$-Privacidad Diferencial Local (LDP): Los usuarios no confían en el curador de datos; cada usuario perturba su propia recompensa antes de enviarla.
  2. $\epsilon$-Privacidad Diferencial Global (GDP): El curador central tiene acceso a los datos crudos, pero debe proteger la privacidad al publicar el resultado o la secuencia de acciones.

2. Metodología y Contribuciones Clave

Los autores abordan dos preguntas fundamentales: ¿Cuántas muestras adicionales se necesitan para garantizar LDP y GDP? Para responder, desarrollan cotas inferiores teóricas y algoritmos superiores que las igualan.

A. Cotas Inferiores (Lower Bounds)

El artículo deriva cotas inferiores para la complejidad de la muestra esperada de cualquier algoritmo $\delta$-correcto que satisfaga DP.

• Dos Regímenes de Dureza: Las cotas revelan la existencia de dos regímenes dependiendo del presupuesto de privacidad $\epsilon$:
  1. Regímen de Baja Privacidad ($\epsilon$ alto): La complejidad de la muestra coincide con la del caso no privado (la privacidad se logra "gratis").
  2. Regímen de Alta Privacidad ($\epsilon$ bajo): La complejidad aumenta significativamente.
• Nuevas Cantidades Teóricas:
  • Para LDP, la dureza depende de una combinación de la divergencia de Kullback-Leibler (KL) y la distancia de Variación Total (TV) al cuadrado ($TV^2$). La cota inferior es $\max(T^*_{KL}, T^*_{TV^2}/\epsilon^2)$.
  • Para GDP, la dureza depende de la distancia de Variación Total (TV) (no al cuadrado). La cota inferior es $\max(T^*_{KL}, T^*_{TV}/\epsilon)$.
• Herramientas Nuevas: Se introduce una versión privada del "lema de cambio de medida" (change-of-measure lemma) para GDP, utilizando técnicas de acoplamiento secuencial (sequential coupling) para relacionar la privacidad con la información teórica.

B. Diseño de Algoritmos

Los autores proponen variantes de algoritmos de tipo "Top Two" (que seleccionan entre un líder y un retador), conocidos por su buen rendimiento empírico y bajo costo computacional.

1. Para LDP: Algoritmo CTB-TT

   • Mecanismo: Utiliza el estimador CTB (Convert-To-Bernoulli) basado en la Respuesta Aleatorizada (Randomised Response).
   • Funcionamiento: Transforma las recompensas en una instancia de Bernoulli modificada donde la privacidad se garantiza localmente.
   • Resultado: Es asintóticamente óptimo. La complejidad de la muestra coincide con la cota inferior hasta una constante multiplicativa (factor 4 cuando $\epsilon \to 0$).

2. Para GDP: Algoritmos AdaP-TT y AdaP-TT$^\star$

   • Estimador Privado (DAF): Introducen el estimador DAF (Doubling-And-Forgetting). Este mecanismo actualiza las medias en episodios adaptativos por brazo, "olvida" las observaciones pasadas al final de cada episodio (cuando el conteo se duplica) y añade ruido de Laplace. Esto evita la composición secuencial de privacidad, manteniendo el costo de privacidad bajo control.
   • AdaP-TT (Enfoque Plug-in): Inserta el estimador DAF en el algoritmo TTUCB estándar, ajustando solo el umbral de parada para tener en cuenta el ruido.
     • Limitación: No es óptimo en el régimen de alta privacidad para instancias con brechas de medias muy diferentes.
   • AdaP-TT$^\star$ (Enfoque Adaptado): Modifica los costos de transporte (transportation costs) y el umbral de parada para adaptarse explícitamente a la cota inferior de GDP.
     • Ventaja: Logra la cota inferior asintótica en el régimen de alta privacidad (hasta una constante multiplicativa pequeña, factor 48), superando las limitaciones de la aproximación "plug-in".

3. Resultados Principales

• Óptimidad Asintótica:
  • CTB-TT alcanza la cota inferior para LDP.
  • AdaP-TT$^\star$ alcanza la cota inferior para GDP en el régimen de alta privacidad, cerrando la brecha dejada por algoritmos anteriores.
• Regímenes de Transición: Los experimentos confirman teóricamente la existencia de dos regímenes. En el régimen de baja privacidad, el rendimiento es casi idéntico al caso no privado. En el régimen de alta privacidad, el número de muestras crece proporcionalmente a $1/\epsilon^2$ (para LDP) o $1/\epsilon$ (para GDP).
• Comparación Empírica:
  • Los algoritmos propuestos superan significativamente a la adaptación del algoritmo DP-SE (Successive Elimination), especialmente en el régimen de alta privacidad.
  • AdaP-TT$^\star$ muestra una superioridad clara sobre AdaP-TT cuando $\epsilon \to 0$, demostrando que adaptar los costos de transporte es crucial para la eficiencia en privacidad estricta.
• Adaptabilidad: Los algoritmos requieren un número logarítmico de rondas de adaptividad ($O(K \log^2(T^* \log(1/\delta)))$), lo que los hace prácticos para implementaciones en lotes (batched).

4. Significado e Impacto

Este trabajo es fundamental por varias razones:

1. Cierre de Brechas Teóricas: Proporciona las primeras cotas inferiores explícitas y algoritmos que las igualan para el problema de BAI con Confianza Fija bajo privacidad diferencial, un área que anteriormente carecía de resultados sólidos en comparación con la minimización de arrepentimiento (regret minimization).
2. Nuevas Métricas de Dureza: Introduce la distancia de Variación Total (TV) como la medida natural para cuantificar la dificultad de la privacidad en BAI, en lugar de solo la divergencia KL. Esto cambia la comprensión teórica de cómo la privacidad afecta la identificabilidad de los brazos.
3. Aplicabilidad Práctica: Ofrece soluciones listas para usar en aplicaciones críticas como ensayos clínicos adaptativos, donde la privacidad de los pacientes es primordial, pero la eficiencia en la identificación del tratamiento óptimo es vital.
4. Innovación en Estimación: El mecanismo DAF (duplicación y olvido) es una contribución técnica importante para lograr privacidad global eficiente sin acumular ruido excesivo, aplicable más allá de BAI.

En resumen, el artículo establece el estado del arte en la intersección de la privacidad diferencial y la exploración pura (pure exploration) en banditos, demostrando que es posible lograr privacidad sin sacrificar excesivamente la eficiencia, siempre que se utilicen algoritmos diseñados específicamente para los regímenes de privacidad correspondientes.