Resumen Técnico: Árbol de Guía para la Identificación y Luego Explotación (TG-ITE)

Formulación del Problema

El artículo aborda el problema de los bandidos de duelo estocásticos de $N$ brazos bajo la suposición del ganador de Condorcet. En este entorno, un aprendiz selecciona pares de brazos $(i, j)$ y observa un resultado binario que indica qué brazo gana, regido por una matriz de preferencias $P$ desconocida. La suposición central es la existencia de un ganador de Condorcet único $a^\star$ tal que $P(a^\star, j) > 1/2$ para todo $j \neq a^\star$, mientras que las preferencias entre los brazos no ganadores pueden ser cíclicas.

El estudio se centra en unificar tres objetivos distintos dentro de este único marco:

1. Identificación del Mejor Brazo (BAI): Devolver $a^\star$ con alta confianza ($1-\delta$) en un tiempo de parada dependiente de los datos.
2. Minimización de Regret Débil: Minimizar el regret acumulado donde una ronda incurre en cero regret si al menos uno de los dos brazos elegidos es $a^\star$.
3. Minimización de Regret Fuerte: Minimizar el regret donde una ronda incurre en cero regret solo si ambos brazos elegidos son $a^\star$ (auto-juego).

La pregunta de investigación central es si un marco algorítmico unificado puede lograr un rendimiento óptimo en los tres objetivos simultáneamente, superando el compromiso tradicional entre exploración (necesaria para BAI) y explotación (necesaria para la minimización del regret).

Metodología: Árbol de Guía para la Identificación y Luego Explotación (TG-ITE)

La solución propuesta, TG-ITE, adopta un paradigma de Identificación y Luego Explotación. Desacopla el problema en una fase de identificación compartida seguida de estrategias de explotación específicas para cada objetivo.

1. Primitiva de Identificación Compartida: TREEASCENT

La innovación central es un algoritmo de Identificación Guiada por Árbol llamado TREEASCENT. A diferencia de las estrategias estándar de "Explorar y Luego Comprometerse" (ETC), que suelen ser subóptimas en el regret acumulado, TREEASCENT utiliza una estructura de árbol binario determinista y balanceada para guiar la búsqueda del ganador de Condorcet.

• Mecanismo: Partiendo de un brazo arbitrario $b$, el algoritmo recorre la ruta de ancestros de un árbol binario fijo. En cada nivel $h$, realiza un torneo de eliminación sobre un "bloque de hermanos" de brazos (brazos recién adjuntos en ese nivel) para encontrar un representante.
• Fusión: El representante del bloque de hermanos se compara luego contra el "campeón" actual (el ganador del nivel anterior) utilizando una prueba de pares secuencial (DUELTEST).
• Eficiencia: Al asignar presupuestos de confianza proporcionales al tamaño de los bloques de hermanos (tamaños que crecen geométricamente), el algoritmo identifica un incumbente de alta confianza con una complejidad de muestreo de $O(N)$. Esto se logra sin requerir suposiciones más fuertes como la transitividad estocástica fuerte o la desigualdad del triángulo estocástico, basándose únicamente en la existencia del ganador de Condorcet y una brecha global $\Delta$.

2. Estrategias de Explotación Específicas de Objetivo

Una vez que se identifica un incumbente de alta confianza mediante TREEASCENT, el marco cambia a políticas de explotación específicas:

• Para BAI (TG-ITE-BAI): El algoritmo simplemente ejecuta TREEASCENT y se detiene al devolver el brazo identificado. Esto logra una complejidad de muestreo de $O(N)$, igualando el límite inferior teórico para BAI.
• Para Regret Débil (TG-ITE-WEAK): El algoritmo utiliza TREEASCENT como un "arranque en caliente" de confianza constante para encontrar un ganador inicial. Luego emplea una estrategia de estilo Ganador se Queda (WS) llamada SCREENANDREPLACE. En cada época, el incumbente actual es evaluado contra todos los desafiantes. Si un desafiante parece vencer al incumbente, se lleva a cabo un torneo de reemplazo. Este enfoque logra un regret débil de $O(N)$, mejorando los resultados previos de $O(N \log N)$.
• Para Regret Fuerte (TG-ITE-STRONG): El algoritmo identifica un incumbiente confiable mediante TREEASCENT y luego se involucra en un auto-juego (comparando al incumbente contra sí mismo).
  • Horizonte Conocido: Ejecutar TREEASCENT con una confianza de $1/(H+1)$, luego auto-juego.
  • Horizonte de Tiempo Cualquiera: Intercalar pasadas de identificación cada vez más confiables con bloques de auto-juego cada vez más largos.
  • Esto logra un regret fuerte de $O(N \log T)$, igualando algoritmos especializados de regret fuerte.

Principales Contribuciones y Resultados

1. Marco Unificado

TG-ITE es el primer marco que unifica BAI, regret débil y regret fuerte en bandidos de duelo utilizando una primitiva de identificación compartida. Demuestra que el intercambio entre identificación y minimización del regret es "benigno" en el entorno de los bandidos de duelo debido a la capacidad de usar un brazo para la exploración y otro para la explotación.

2. Mejora en la Complejidad de Muestreo y Límites de Regret

• BAI: Logra una complejidad de muestreo de $O(N)$ sin requerir transitividad estocástica fuerte o suposiciones de orden total, igualando los mejores resultados conocidos para BAI.
• Regret Débil: Logra un regret débil de $O(N)$, cerrando la brecha de $O(\log N)$ encontrada en enfoques de optimización conjunta previos (por ejemplo, Ma et al., 2025) e igualando los mejores límites independientes de la instancia.
• Regret Fuerte: Logra un regret de $O(N \log T)$, igualando las garantías de algoritmos especializados como WS-S y RUCB.
• Optimización Conjunta: El marco permite la optimización simultánea de BAI y el regret débil, logrando garantías de $O(N)$ para ambos, eliminando los factores subóptimos de $O(\log N)$ presentes en trabajos anteriores.

3. Garantías Teóricas

El artículo proporciona pruebas rigurosas de la corrección y el costo de TREEASCENT y las fases de explotación subsiguientes.

• Teorema 1: TREEASCENT identifica al ganador de Condorcet con una probabilidad de $1-\epsilon$ usando $O(N)$ comparaciones.
• Teorema 2: El regret débil de TG-ITE-WEAK está acotado por $O(N/\Delta^2)$, lo cual es lineal en $N$ e independiente del horizonte de tiempo $T$.
• Teoremas 3 y 4: Los límites de regret fuerte son de $O(N \log T)$ tanto para horizontes conocidos como desconocidos.

4. Extensiones

El artículo también presenta una Extensión Presupuestada de Brecha Conocida (Sección 5). Si se conoce un límite inferior $g$ sobre la brecha de Condorcet, el algoritmo puede reemplazar la prueba DUELTEST de tiempo cualquiera con una prueba de presupuesto fijo. Esto elimina el factor $\log(1/\Delta)$ de los límites, proporcionando presupuestos de comparación deterministas y garantías más ajustadas, aunque a costa de requerir conocimiento previo de la brecha.

Validación Experimental

Los autores evalúan TG-ITE frente a líneas base representativas (incluyendo WS-W, WS-S, RUCB, WR-TINF y WSW-PE) en instancias sintéticas diseñadas para poner a prueba la no transitividad y las brechas asimétricas.

• Escalado de BAI: TG-ITE-BAI escala de forma casi lineal con $N$, superando a los métodos de eliminación por pares adaptativos en instancias cíclicas.
• Regret Débil: TG-ITE-WEAK logra el menor regret acumulado y se estabiliza rápidamente, demostando la eficacia de la estrategia de arranque en caliente.
• Regret Fuerte: TG-ITE-STRONG supera significativamente a las líneas base, con la curva aplanándose una vez que comienza el auto-juego, confirmando su comportamiento teórico de $O(N \log T)$.

Significado y Reivindicaciones

El artículo afirma que TG-ITE proporciona evidencia teórica de que el intercambio entre la Identificación del Mejor Brazo y la Minimización del Regret es relativamente benigno en los bandidos de duelo. Al aprovechar la estructura única de los bandidos de duelo (seleccionar dos brazos), el marco logra desacoplar con éxito las fases de exploración y explotación sin la suboptimidad típica observada en los bandidos multi-brazos estándar.

Los autores enfatizan que su enfoque:

1. Unifica tres objetivos distintos bajo una única primitiva de identificación reutilizable (TREEASCENT).
2. Mejora el estado del arte para el regret débil al eliminar el factor $O(\log N)$ y relajar la suposición de orden total.
3. Iguala las tasas óptimas para BAI y regret fuerte sin requerir suposiciones estructurales más fuertes (como la transitividad estocástica fuerte) en las que dependían algoritmos previos óptimos.

El trabajo sugiere que la plantilla de "Identificar y Luego Explotar", cuando es guiada por una descomposición de torneo basada en árboles, es una estrategia poderosa y generalizable para el aprendizaje basado en preferencias.