Resumen Técnico: Clasificación y Selección con Múltiples Respuestas Correctas y Estimaciones No Contestables

Formulación del Problema

Este artículo aborda problemas de clasificación y selección (R&S) de precisión fija en entornos estructurados caracterizados por dos desafíos específicos que complican los plantillas tradicionales de "identificación del mejor brazo":

1. Múltiples Respuestas Correctas: El conjunto de respuestas correctas, $A^\star(\theta)$, puede contener más de un elemento (por ejemplo, seleccionar cualquier alternativa "buena" dentro de una tolerancia $\epsilon$).
2. Estimaciones No Contestables: Debido a observaciones ruidosas, las estimaciones empíricas pueden caer temporalmente fuera del "conjunto contestable" $\Theta^\star$, donde no existe una respuesta válida. Esto ocurre en escenarios como el R&S de multi-fidelidad (donde las medias empíricas violan las restricciones de sesgo) o los bandits duelistas (donde las preferencias estimadas inducen ciclos, impidiendo un ganador de Condorcet).

El objetivo es diseñar una regla de parada $\tau_\delta$ y una regla de decisión $\hat{a}_{\tau_\delta}$ tales que la probabilidad de seleccionar una respuesta correcta sea al menos $1-\delta$ para todo $\theta \in \Theta^\star$, minimizando al mismo tiempo el costo total de muestreo esperado $E_\theta[B_{\tau_\delta}]$. El marco permite tipos de medición heterogéneos con costos variables.

Metodología: El Marco Unificado

Los autores proponen un marco unificado que generaliza la perspectiva de "nominación adaptada a trampas" (Qin y You, 2026) para manejar respuestas con valores de conjunto y no-contestabilidad transitoria. Los componentes principales son:

1. Conjuntos de Aceptación por Respuesta y Trampas (Pitfalls)

En lugar de centrarse en una única respuesta verdadera, el marco descompone el problema por respuestas candidatas $a \in A$.

• Conjuntos de Aceptación ($\Theta^\star_a$): El conjunto de parámetros donde la respuesta $a$ es correcta.
• Regiones de Rechazo ($Alt_a$): El conjunto de instancias contestables donde $a$ es incorrecta.
• Trampas ($X_a$): La región de rechazo $Alt_a$ se descompone en una unión finita de conjuntos convexos más simples, $Alt_{a,x}$, indexados por "trampas" $x$. Una trampa representa una forma específica en que una respuesta puede fallar (por ejemplo, un desafiante específico que supera al nominado actual).

2. Razón de Verosimilitud Generalizada (GLR) Restringida de Parada

Para manejar estimaciones no contestables, los autores definen un estadístico GLR restringido $Z_n(a)$ para cada candidato $a$:
$$Z_n(a) = \inf_{\vartheta \in Alt_a} \Gamma(N_n; \hat{\theta}_n, \vartheta) - \inf_{\vartheta \in \Theta^\star_a} \Gamma(N_n; \hat{\theta}_n, \vartheta)$$
donde $\Gamma$ es la suma de las divergencias de Kullback–Leibler (KL) por coordenadas y $\hat{\theta}_n$ es el MLE sin restricciones.

• Si la estimación es no contestable, el estadístico sigue estando bien definido al comparar el mejor ajuste en la región de rechazo contra el mejor ajuste en la región de aceptación.
• La regla de parada $\tau_\delta$ se activa cuando $\max_{a \in A} Z_n(a) \geq \beta_{n,\delta}$.
• La regla de decisión selecciona la respuesta que maximiza este estadístico, proporcionando robustez contra ganadores empíricos indefinidos.

3. El Valor Característico Max-Max-Min

El artículo deriva una cota inferior en el costo esperado, motivada por un valor característico $\Gamma^\star(\theta)$:
$$\Gamma^\star(\theta) \triangleq \max_{p \in \Delta_U} \max_{a \in A} \min_{x \in X_a} D_{a,x}(p; \theta)$$
donde $D_{a,x}$ es la tasa de información normalizada por costo para descartar la trampa $x$ para la respuesta $a$.

• El mínimo interno identifica la trampa más difícil de descartar para una respuesta específica.
• El máximo intermedio permite al aprendiz nominar la respuesta más "fácil" de certificar (crucial cuando las estimaciones son no contestables o hay múltiples respuestas correctas).
• El máximo externo optimiza la asignación de muestreo $p$.
  Este valor dicta la escala asintótica del presupuesto de parada: $E_\theta[B_{\tau_\delta}] \gtrsim \log(1/\delta) / \Gamma^\star(\theta)$.

4. El Algoritmo ENDS

Los autores introducen ENDS (Estimación, Nominación, Detección, Selección), un procedimiento general:

1. Estimación (Estimate): Calcular un estimador $\theta_n$ (por ejemplo, una muestra posterior).
2. Nominación (Nominate): Seleccionar la respuesta provisional $a_n$ que maximiza el estadístico GLR $Z(a; p_n, \theta_n)$.
3. Detección (Detect): Identificar la trampa principal $x_n$ para $a_n$ (la instancia alternativa más confusa).
4. Selección (Select): Muestrear la siguiente medición de una distribución de Muestreo Dirigido por Información (IDS) sensible al costo $H_{a_n, x_n}$, que minimiza el costo para distinguir la estimación actual de la alternativa peor caso para la trampa identificada.

Principales Contribuciones

1. Marco Unificado: Una receta estructural única para R&S de precisión fija sensible al costo que maneja simultáneamente múltiples respuestas correctas y estimaciones temporalmente no contestables, cerrando la brecha entre los bandits de exploración pura y la optimización de simulación.
2. Caracterización Teórica: La derivación del valor característico max-max-min, que generaliza las cotas inferiores existentes a escenarios donde el mapa de respuestas tiene valores de conjunto y las estimaciones pueden ser temporalmente inválidas.
3. Receta Algorítmica (ENDS): Un algoritmo portable que combina estimación, nominación, detección de trampas y IDS. El artículo proporciona instancias explícitas para:
   • Selección de una alternativa buena ($\epsilon$-best-arm).
   • Ranking-and-selection de multi-fidelidad.
   • Bandits duelistas con ganadores de Condorcet.
4. Fórmulas Explícitas: Derivación de expresiones de forma cerrada para las distribuciones IDS y los estadísticos GLR para las tres clases de problemas representativas.

Resultados Experimentales

Extensos experimentos numéricos demuestran que ENDS es robusto y competitivo a través de problemas cualitativamente diferentes:

• Selección de Alternativa Buena: En entornos gaussianos con varianza desconocida, ENDS alcanzó consistentemente el menor presupuesto de parada esperado comparado con métodos de vanguardia (KN, Paulson, ZH-Proc2) y la asignación uniforme, con una ventaja que escala con el número de alternativas.
• R&S de Multi-Fidelidad: ENDS superó a MF-GRAD y a las líneas base de alta fidelidad únicamente (TS-KKT-IDS, GRAD) en la mayoría de las instancias sintéticas. Notablemente, manejó eficazmente las trampas de baja fidelidad "engañosas", mientras que los métodos que dependen únicamente de alta fidelidad o seguimiento de optimización continua incurrieron en costos más altos.
• Bandits Duelistas: ENDS superó significativamente a las líneas base (SAVAGE, DKWT, SEEBS) en términos de costo de parada esperado. Los autores señalan que el rendimiento superior se atribuye en parte a la regla de parada GLR desacoplada y más fuerte en comparación con las reglas de tipo eliminación utilizadas por las líneas base.

Significado y Reivindicaciones

El artículo se posiciona como una prueba de concepto de que un único lenguaje algorítmico puede transferirse a través de modelos amplios.

• Unificación: Argumenta que la presencia conjunta de múltiples respuestas correctas y estimaciones no contestables, tratados previamente de manera específica para cada problema, puede abordarse mediante una descomposición "por respuesta" unificada.
• Practicidad: El "marco unificado" propuesto ofrece una receta práctica para problemas de exploración pura donde las puntuaciones absolutas no están disponibles o las estimaciones están estructuralmente restringidas.
• Modestia: Los autores reconocen que la calibración exacta del umbral para la regla de parada sigue siendo una cuestión abierta y dependiente del problema (utilizando un heurístico en los experimentos) y que las cotas superiores asintóticas rigurosas que coincidan con el valor característico se dejan para trabajos futuros. También señalan que ENDS no está diseñado actualmente para problemas de gran escala debido a las cargas computacionales.