Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

Resumen Técnico: Follow-the-Perturbed-Leader para Bandidos Desacoplados

Configuración del Problema
Este artículo aborda el problema de bandidos multi-brazo desacoplados (MAB), un escenario donde el aprendiz selecciona dos brazos distintos en cada ronda $t$: un brazo $i_t$ para explotación (incurriendo en la pérdida $\ell_{t, i_t}$ sin observarla) y un brazo $j_t$ para exploración (observando la pérdida $\ell_{t, j_t}$ sin incurir en ella). Este marco modela escenarios como sistemas de comunicación de banda ultraancha (sensando un canal diferente al de transmisión) y la transferencia sim-a-real en robótica. El objetivo es minimizar el pseudo-arrepentimiento, definido como la diferencia entre la pérdida acumulada incurrida por las decisiones de explotación del aprendiz y la pérdida acumulada del mejor brazo fijo a posteriori.

El artículo apunta a garantías de Mejor de Ambos Mundos (BOBW), buscando lograr:

1. Arrepentimiento óptimo de $O(\sqrt{KT})$ en el régimen adversario (donde las pérdidas son determinadas por un adversario adaptativo).
2. Arrepentimiento casi óptimo e independiente del tiempo de $O(K/\Delta_{\min})$ en el régimen adversario estocásticamente restringido (SCA) (que incluye el escenario estocástico estándar), donde $\Delta_{\min}$ es la brecha de suboptimalidad mínima.

Metodología
Los autores proponen una nueva política basada en el marco Follow-the-Perturbed-Leader (FTPL), diseñada específicamente para superar los cuellos de botella computacionales de las políticas BOBW existentes en entornos desacoplados.

• Estrategia de Explotación: El aprendiz selecciona el brazo de explotación $i_t$ minimizando una estimación de pérdida acumulada perturbada:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  donde $\hat{L}_{t,i}$ es la estimación de pérdida acumulada, $\eta_t$ es la tasa de aprendizaje, y $r_{t,i}$ son perturbaciones aleatorias i.i.d. muestreadas de una distribución Pareto $P_\alpha$ con parámetro de forma $\alpha > 1$. Este tipo de perturbación corresponde a la política $\beta$-Tsallis-INF (con $\alpha = 1/(1-\beta)$), conocida por lograr garantías BOBW.

• Estrategia de Exploración (Innovación Clave): En los algoritmos estándar de bandidos FTPL, construir un estimador de pérdida ponderado por importancia (IW) sin sesgo típicamente requiere conocer la probabilidad exacta $w_{t,i}$ de seleccionar el brazo $i$. En los bandidos desacoplados, la probabilidad de exploración $p_{t,i}$ debe establecerse basándose en $w_{t,i}$. Sin embargo, FTPL no proporciona una expresión de forma cerrada para $w_{t,i}$ (a diferencia de FTRL), y estimar el vector completo mediante muestreo geométrico es computacionalmente costoso ($O(K^2)$ o superior).
  Para resolver esto, los autores introducen una probabilidad sustituta $q_{t,i}$ que puede calcularse directamente a partir de las estimaciones de pérdida actuales sin necesidad de muestreo o optimización convexa:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  donde $\sigma_{t,i}$ es el rango de $\hat{L}_{t,i}$ entre todos los brazos. El brazo de exploración $j_t$ se selecciona entonces según la distribución normalizada $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$. Este enfoque evita la necesidad de valores explícitos de $w_{t,i}$ mientras mantiene las propiedades teóricas requeridas para las garantías BOBW.

Contribuciones Clave

1. Primera política basada en FTPL para BOBW en Bandidos Desacoplados: El artículo presenta la primera política que logra garantías BOBW en bandidos desacoplados sin resolver problemas de optimización convexa (requeridos por enfoques basados en FTRL como Decoupled-Tsallis-INF) ni emplear procedimientos de remuestreo (típicamente requeridos para la estimación de probabilidades en FTPL).
2. Eficiencia Computacional: Al reemplazar el cálculo del vector completo de probabilidades con la sustituta computable eficientemente $q_{t,i}$, la política propuesta reduce la complejidad computacional por paso. Aunque ordenar las estimaciones de pérdida toma $O(K \log K)$, los autores notan que una implementación optimizada puede lograr actualizaciones de $O(K)$ rastreando los cambios de rango de manera incremental. Esto contrasta con las políticas FTRL que requieren optimización convexa iterativa (por ejemplo, el método de Newton) en cada paso.
3. Garantías Teóricas:
   • Régimen Adversario: La política logra un límite de arrepentimiento de $O(\sqrt{KT})$, igualando el límite inferior conocido para bandidos desacoplados.
   • Régimen Estocástico/SCA: La política logra un límite de arrepentimiento de $O(K/\Delta_{\min})$ (específicamente $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$ para $\alpha=3$), que es casi óptimo y mejora los límites dependientes del tiempo de los bandidos estocásticos estándar.

Resultados

• Teóricos: El artículo proporciona pruebas rigurosas (mediante la descomposición del arrepentimiento en términos de estabilidad y penalización) que muestran que la probabilidad sustituta $q_{t,i}$ está suficientemente cerca de la verdadera probabilidad de explotación para mantener los límites de arrepentimiento necesarios.
• Empíricos: Experimentos con datos sintéticos (ambos regímenes adversario y estocástico) y una simulación del mundo real utilizando el conjunto de datos MovieLens 100K demuestran que la política FTPL propuesta:
  • Logra un arrepentimiento acumulado menor en comparación con las políticas BOBW existentes (Decoupled-Tsallis-INF/FTRL y EXP3).
  • Muestra una eficiencia computacional superior. En el régimen adversario, la política propuesta se ejecuta significativamente más rápido que las líneas base basadas en FTRL. Para $K=64$, se observó que la relación de tiempo de ejecución de FTRL respecto a FTPL fue aproximadamente 1363 veces más lenta.
  • Escala efectivamente con el número de brazos $K$, manteniendo robustez a través de tamaños de brecha $\Delta$ variables.

Significado y Afirmaciones
El artículo afirma que su contribución principal es cerrar la brecha entre la optimalidad teórica de las políticas BOBW basadas en FTRL y la eficiencia computacional de FTPL en el contexto de los bandidos desacoplados. Al eliminar la necesidad de optimización convexa y remuestreo, el método propuesto permite que FTPL realice plenamente sus ventajas de eficiencia sin sacrificar el rendimiento en arrepentimiento. Los autores sugieren que la técnica de usar probabilidades sustitutas computables eficientemente en lugar de vectores de probabilidad exactos puede ser aplicable a otros marcos algorítmicos (como la familia Prod) más allá de FTPL, posiblemente habilitando una eficiencia computacional mejorada en configuraciones de bandidos más amplias. El trabajo está motivado por aplicaciones prácticas en sistemas de comunicación y robótica donde la latencia computacional por paso es crítica.