Fundamental Limitations of Fixed-Budget Best-Arm Identification

Resumen Técnico: Limitaciones Fundamentales de la Identificación del Mejor Brazo con Presupuesto Fijo

Formulación del Problema
El artículo aborda el problema de la Identificación del Mejor Brazo (Best-Arm Identification, BAI) con Presupuesto Fijo, también conocido como Clasificación y Selección (Ranking and Selection). En este escenario, un tomador de decisiones muestrea secuencialmente de $K$ brazos, cada uno de los cuales genera recompensas independientes de una distribución con una media desconocida $\mu_k$. El objetivo es identificar el brazo con la mayor media, $i^*(\mu)$, utilizando un presupuesto total de muestreo fijo $T$. La métrica de rendimiento es la probabilidad de identificación incorrecta, $p_{\mu, T}$, específicamente su tasa de decaimiento exponencial cuando $T \to \infty$:
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

La cuestión teórica central es si existe una "complejidad" para este problema. Una complejidad se define como una función $\Gamma^*(\mu)$ que satisface dos condiciones:

1. Cota Superior Universal: Para cada algoritmo y cada instancia $\mu$, la tasa de decaimiento del error está acotada superiormente por $\Gamma^*(\mu)$.
2. Logro Uniforme: Existe un único algoritmo que alcanza esta tasa de decaimiento $\Gamma^*(\mu)$ uniformemente en todas las instancias del problema $\mu$.

El artículo investiga si la tasa del oráculo estático, $\Gamma^*_{so}(\mu)$, sirve como esta complejidad. El oráculo estático representa la tasa de decaimiento de error óptima alcanzable mediante una estrategia no adaptativa que conoce las medias verdaderas $\mu$ de antemano y asigna proporciones fijas de muestreo para maximizar la tasa de decaimiento. Aunque se han diseñado algoritmos adaptativos para que sus proporciones de muestreo converjan a estas proporciones estáticas óptimas, seguía siendo una pregunta abierta si algún algoritmo adaptativo podría igualar la tasa de decaimiento del oráculo estático de forma uniforme en todas las instancias.

Metodología
Los autores emplean una prueba por contradicción para demostrar que ningún algoritmo único puede alcanzar la tasa del oráculo estático uniformemente para todas las instancias cuando $K \geq 3$. La metodología se basa en los siguientes componentes:

1. Razones de Dificultad: Siguiendo a Degenne (2023), el artículo utiliza la razón de dificultad $R_{H, \infty}(A, \mu)$, que mide el rendimiento de un algoritmo $A$ en relación con una función de dificultad de referencia $H(\mu)$. Si existiera una complejidad, debe existir un algoritmo donde el supremo de esta razón sobre todas las instancias sea $\leq 1$.
2. Teorema 1 (Degenne 2023): La prueba aprovecha una desigualdad clave de Degenne (2023) que acota el rendimiento de cualquier familia de algoritmos adaptativos consistentes. Para cualquier referencia $H$ y un conjunto de instancias alternativas $D(\mu)$, el inverso de la peor razón de dificultad está acotado por un problema de optimización estática sobre las proporciones de muestreo $\omega$:
   $$\left( \sup_{\lambda \in D(\mu)} R_{H, \infty}(A, \lambda) \right)^{-1} \leq \sup_{\omega \in \Delta_K} \inf_{\lambda \in D(\mu)} \left( H(\lambda) \sum_{k=1}^K \omega_k \text{KL}(\mu_k, \lambda_k) \right)$$
3. Construcción de Instancias: Para probar la no existencia de complejidad, los autores construyen una instancia "base" específica $x$ y una familia de instancias alternativas $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$.
   • $\lambda_A$: Difiere de $x$ solo en los brazos 1 y 2. Distinguir $x$ de $\lambda_A$ requiere un muestreo significativo de los brazos 1 y 2.
   • $\lambda_{B,j}$ (para $j \in \{3, \dots, K\}$): Difiere de $x$ solo en el brazo $j$, haciendo que el brazo $j$ sea el nuevo mejor brazo. Distinguir $x$ de $\lambda_{B,j}$ requiere un muestreo significativo del brazo $j$.
     El estudio asegura que los brazos "más difíciles" de distinguir varían a través de la familia. Una única asignación de muestreo $\omega$ no puede ser simultáneamente óptima para distinguir $x$ de todos los miembros de $D(x)$ porque la información requerida está concentrada en conjuntos disjuntos de brazos.

Resultados Clave
El artículo establece un resultado negativo fundamental para la BAI de presupuesto fijo:

• Recompensas Gaussianas: Para $K \geq 3$ brazos con recompensas gaussianas (varianza 1), los autores demuestran que para cualquier familia de algoritmos consistentes, existe una instancia $\mu$ tal que la razón de dificultad relativa al oráculo estático excede 1. Específicamente:
  $$\inf_{A \in \mathcal{C}_{cons}} \sup_{\mu} R_{H_{so}, \infty}(A, \mu) \geq 1 + \sum_{j=3}^K \frac{1}{(1 + \sqrt{j-1})^2} > 1 + \frac{1}{8} \log(K)$$
  Esta cota inferior es estrictamente mayor que 1 para todo $K \geq 3$, demostiendo que ningún algoritmo puede igualar uniformemente al oráculo estático.

• Generalización a Familias Exponenciales Naturales (NEF): El resultado se extiende a cualquier familia exponencial natural (NEF) de un parámetro. Utilizando una aproximación cuadrática local de la divergencia de Kullback-Leibler (KL), los autores muestran que el resultado gaussiano implica la misma limitación para todas las NEF regulares de un parámetro.

• Respuesta a la Pregunta Abierta: Este trabajo responde definitivamente a la pregunta planteada por Qin (2022) y formalizada por Degenne (2023): la BAI de presupuesto fijo no admite una complejidad para $K \geq 3$. Aunque el oráculo estático proporciona una cota inferior en la tasa de decaimiento del error, ningún algoritmo adaptativo único puede alcanzar este límite de forma uniforme en todas las instancias del problema.

Significado y Reivindicaciones
El artículo afirma resolver un vacío teórico fundamental en la comprensión de la BAI de presupuesto fijo.

• Limitación de la Adaptividad: Demuestra que la convergencia de las proporciones de muestreo hacia el oráculo estático (un objetivo de diseño común en algoritmos adaptativos) es insuficiente para garantizar el emparejamiento con la tasa de decaimiento del error del oráculo estático. El "precio de la adaptividad" en el entorno de presupuesto fijo es que un algoritmo no puede ser óptimo para todas las instancias simultáneamente.
• Alcance: El resultado llena un vacío en la literatura para $3 \leq K < e^{80/3}$ para recompensas gaussianas y extiende la no existencia de complejidad a todas las NEF de un parámetro.
• Frontera Teórica: El trabajo establece que la tasa del oráculo estático no es una complejidad universal para la BAI de presupuesto fijo cuando $K \geq 3$. Los autores sugieren que esto implica la necesidad de objetivos o referencias teóricas alternativas, ya que el oráculo estático no puede ser alcanzado uniformemente.

El artículo no propone nuevos algoritmos para superar esta limitación, ni sugiere aplicaciones específicas más allá de las implicaciones teóricas para la Clasificación y Selección y los Bandidos Multibrazo (Multi-Armed Bandits). La contribución es estrictamente un resultado negativo que define los límites fundamentales de lo que es alcanzable en este entorno.