Résumé Technique : Classement et Sélection avec Réponses Multiples et Estimations Non-Répondables

Formulation du Problème

Cet article traite des problèmes de classement-et-sélection (R&S) à précision fixe dans des contextes structurés caractérisés par deux défis spécifiques qui compliquent les modèles traditionnels d'identification du meilleur bras :

1. Réponses Multiples : L'ensemble des bonnes réponses, $A^\star(\theta)$, peut contenir plus d'un élément (par exemple, sélectionner n'importe quelle alternative « bonne » dans une tolérance $\epsilon$).
2. Estimations Non-Répondables : En raison d'observations bruitées, les estimations empiriques peuvent temporairement tomber en dehors de l'ensemble « répondable » $\Theta^\star$, où aucune réponse valide n'existe. Cela se produit dans des scénarios comme le R&S multi-fidélité (où les moyennes empiriques violent les contraintes de biais) ou les bandits duels (où les préférences estimées induisent des cycles, empêchant un vainqueur de Condorcet).

L'objectif est de concevoir une règle d'arrêt $\tau_\delta$ et une règle de décision $\hat{a}_{\tau_\delta}$ telles que la probabilité de sélectionner une réponse correcte soit d'au moins $1-\delta$ pour tout $\theta \in \Theta^\star$, tout en minimisant le coût total d'échantillonnage attendu $E_\theta[B_{\tau_\delta}]$. Le cadre permet des types de mesures hétérogènes avec des coûts variables.

Méthodologie : Le Cadre Unifié

Les auteurs proposent un cadre unifié qui généralise la perspective de la « nomination adaptée aux pièges » (Qin et You, 2026) pour gérer les réponses sous forme d'ensembles et la non-répondabilité transitoire. Les composantes centrales sont :

1. Ensembles d'Acceptation par Réponse et Pièges

Au lieu de se concentrer sur une seule véritable réponse, le cadre décompose le problème par réponses candidates $a \in A$.

• Ensembles d'Acceptation ($\Theta^\star_a$) : L'ensemble des paramètres où la réponse $a$ est correcte.
• Régions de Rejet ($Alt_a$) : L'ensemble des instances répondables où $a$ est incorrecte.
• Pièges ($X_a$) : La région de rejet $Alt_a$ est décomposée en une union finie d'ensembles convexes plus simples, $Alt_{a,x}$, indexés par des « pièges » $x$. Un piège représente une manière spécifique dont une réponse peut échouer (par exemple, une alternative de défi spécifique battant le candidat actuel).

2. Rapport de Vraisemblance Généralisé (GLR) Restreint pour l'Arrêt

Pour gérer les estimations non-répondables, les auteurs définissent un statistique de GLR restreint $Z_n(a)$ pour chaque candidat $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)$$
où $\Gamma$ est la somme des divergences de Kullback–Leibler (KL) par coordonnée et $\hat{\theta}_n$ est le MLE non contraint.

• Si l'estimation est non-répondable, la statistique reste bien définie en comparant le meilleur ajustement dans la région de rejet contre le meilleur ajustment dans la région d'acceptation.
• La règle d'arrêt $\tau_\delta$ se déclenche lorsque $\max_{a \in A} Z_n(a) \geq \beta_{n,\delta}$.
• La règle de décision sélectionne la réponse maximisant cette statistique, offrant une robustesse contre les gagnants empiriques indéfinis.

3. La Valeur Caractéristique Max-Max-Min

L'article dérive une borne inférieure sur le coût attendu, motivée par une valeur caractéristique $\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)$$
où $D_{a,x}$ est le taux d'information normalisé par le coût pour écarter le piège $x$ pour la réponse $a$.

• Le min intérieur identifie le piège le plus difficile à écarter pour une réponse spécifique.
• Le max intermédiaire permet à l'apprenant de nommer l'« easiest » (la plus facile) réponse à certifier (crucial lorsque les estimations sont non-répondables ou que plusieurs réponses sont correctes).
• Le max extérieur optimise l'allocation d'échantillonnage $p$.
  Cette valeur dicte l'échelle asymptotique du budget d'arrêt : $E_\theta[B_{\tau_\delta}] \gtrsim \log(1/\delta) / \Gamma^\star(\theta)$.

4. L'Algorithme ENDS

Les auteurs introduisent ENDS (Estimation, Nomination, Détection, Sélection), une procédure générale :

1. Estimation : Calculer un estimateur $\theta_n$ (par exemple, un échantillon a posteriori).
2. Nomination : Sélectionner la réponse provisoire $a_n$ maximisant la statistique GLR $Z(a; p_n, \theta_n)$.
3. Détection : Identifier le piège principal $x_n$ pour $a_n$ (l'instance alternative la plus déroutante).
4. Sélection : Échantillonner la mesure suivante à partir d'une distribution d'Échantillonnage Dirigé par l'Information (IDS) sensible au coût $H_{a_n, x_n}$, qui minimise le coût pour distinguer l'estimation actuelle de l'alternative la pire pour le piège identifié.

Contributions Clés

1. Cadre Unifié : Une recette structurelle unique pour le R&S à précision fixe sensible au coût qui gère simultanément les réponses multiples et les estimations non-répondables, comblant les lacunes entre l'exploration pure des bandits et l'optimisation de simulation.
2. Caractérisation Théorique : La dérivation de la valeur caractéristique max-max-min, qui généralise les bornes inférieures existantes aux contextes où la carte des réponses est un ensemble et où les estimations peuvent être temporairement invalides.
3. Recette Algorithmique (ENDS) : Un algorithme portable combinant l'estimation, la nomination, la détection de pièges et l'IDS. L'article fournit des instanciations explicites pour :
   • La sélection d'une bonne alternative ($\epsilon$-best-arm).
   • Le classement-et-sélection multi-fidélité.
   • Les bandits duels avec vainqueurs de Condorcet.
4. Formules Explicites : Dérivation d'expressions en forme fermée pour les distributions IDS et les statistiques GLR pour les trois classes de problèmes représentatives.

Résultats Expérimentaux

Des expériences numériques approfondies démontrent qu'ENDS est robuste et compétitif à travers des problèmes qualitativement différents :

• Sélection d'une Bonne Alternative : Dans des contextes gaussiens avec variance inconnue, ENDS a systématiquement atteint le budget d'arrêt attendu le plus bas par rapport aux méthodes de pointe (KN, Paulson, ZH-Proc2) et à l'allocation uniforme, avec un avantage qui croît avec le nombre d'alternatives.
• R&S Multi-Fidélité : ENDS a surpassé MF-GRAD et les bases à haute fidélité uniquement (TS-KKT-IDS, GRAD) dans la plupart des instances synthétiques. Notamment, il a géré efficacement les pièges de faible fidélité « trompeurs », là où les méthodes reposant uniquement sur la haute fidélité ou le suivi d'optimisation continue ont subi des coûts plus élevés.
• Bandits Duels : ENDS a significativement surpassé les bases (SAVAGE, DKWT, SEEBS) en termes de coût d'arrêt attendu. Les auteurs notent que la performance supérieure est en partie attribuée à la règle d'arrêt GLR découplée et plus forte par rapport aux règles d'élimination utilisées par les bases.

Signification et Revendications

L'article se positionne comme une preuve de concept qu'un langage algorithmique unique peut se transférer à travers divers modèles.

• Unification : Il soutient que la présence conjointe de réponses multiples et d'estimations non-répondables, précédemment traitée de manière spécifique à chaque problème, peut être adressée via une décomposition « par réponse » unifiée.
• Praticité : La « recette unifiée » proposée offre un cadre pratique pour les problèmes d'exploration pure où les scores absolus ne sont pas disponibles ou les estimations sont structurellement contraintes.
• Modestie : Les auteurs reconnaissent que le calibrage précis du seuil pour la règle d'arrêt reste une question ouverte et dépendante du problème (utilisant une heuristique dans les expériences) et que les bornes supérieures asymptotiques rigoureuses correspondant à la valeur caractéristique sont laissées à des travaux futurs. Ils notent également qu'ENDS n'est pas actuellement conçu pour les problèmes à grande échelle en raison des charges de calcul.