Résumé technique : Au-delà du biais statique : Bandits multi-fidélités adaptatifs avec proxies améliorants

Définition du problème

Ce travail aborde une extension spécifique du problème des bandits stochastiques à plusieurs bras (MAB) connue sous le nom de Bandits Multi-Armes Multi-Fidélités (MF-MAB). Dans les configurations MF-MAB standard, les bras peuvent être évalués à l'aide de multiples sources de feedback (fidélités) qui arbitrent entre coût et précision. Les cadres traditionnels supposent un biais statique entre les sources de faible fidélité (bon marché) et de haute fidélité (coûteuses) ; l'écart est fixe, indépendamment du nombre de requêtes effectuées auprès de la source de faible fidélité.

Cependant, les applications modernes impliquant des simulateurs basés sur l'apprentissage et des Modèles de Langage à Grande Échelle (LLM) en tant qu'évaluateurs présentent une dynamique différente : la source de proxy de faible fidélité peut s'améliorer avec un étalonnage supplémentaire ou une utilisation répétée. L'article examine un cadre MF-MAB contraint par un budget où :

1. Il existe $K$ bras avec une moyenne cible stationnaire de haute fidélité $\mu^{(H)}_k$.
2. Une source de faible fidélité fournit des observations $Y^{(L)}_{k,\tau}$ qui évoluent en fonction du nombre de requêtes $\tau$ effectuées auprès de ce bras spécifique.
3. La source de faible fidélité commence avec un décalage par rapport à la cible de haute fidélité, mais ce décalage diminue à mesure que la source est interrogée plus fréquemment (par exemple, via un étalonnage).
4. L'objectif est de minimiser le pseudo-regret pondéré par le coût, défini comme le coût cumulatif encouru en sélectionnant des bras sous-optimaux, plutôt que simplement le nombre de tirages.

Le défi central consiste à déterminer quand arrêter d'interroger la source de faible fidélité améliorante et passer à la source de haute fidélité coûteuse. Une règle de seuil statique pourrait déclencher la transition trop tôt, manquant ainsi l'opportunité pour la source de faible fidélité de devenir suffisamment précise grâce à un échantillonnage bon marché continu.

Méthodologie

Modélisation du proxy améliorant

Les auteurs introduisent une borne d'écart moyen sélectionné pour capturer l'évolution du décalage. Au lieu de supposer un biais fixe $|\mu^{(L)}_k - \mu^{(H)}_k| \le \zeta$, ils supposent un certificat évolutif $U_k(n)$ tel que l'écart cumulatif soit borné :
$$\sum_{\tau=1}^n |\mu^{(L)}_k(\tau) - \mu^{(H)}_k| \le U_k(n)$$
Cela conduit à une borne d'écart moyen sélectionné $B_k(n) = \sup_{s \ge n} U_k(s)/s$, qui borne le décalage entre la moyenne empirique de faible fidélité et la vraie cible de haute fidélité. À mesure que $n$ augmente, $B_k(n)$ diminue, reflétant la fiabilité améliorée du proxy.

L'algorithme TACC

L'article propose l'algorithme Threshold-Based Adaptive Continuation Companion (TACC) (Compagnon Adaptatif de Continuation Basé sur Seuil). TACC fonctionne sur un modèle basé sur la confiance mais introduit une nouvelle règle de continuation bornée pour la source de faible fidélité.

1. Bornes de confiance : TACC construit des bornes de confiance supérieures (UCB) pour la cible de haute fidélité $\mu^{(H)}_k$ en utilisant les deux fidélités.
   • UCB haute fidélité : Intervalle statistique standard.
   • UCB faible fidélité : Intervalle statistique standard plus la correction d'écart $B_k(n)$.
2. Sélection de bras : L'algorithme sélectionne le bras ayant le score optimiste le plus élevé, défini comme le minimum des UCB de faible et de haute fidélité.
3. Sélection de fidélité (l'innovation centrale) :
   • Pré-seuil : Si l'incertitude statistique de faible fidélité (rayon) est supérieure à un seuil $\gamma$, l'algorithme continue l'échantillonnage de faible fidélité.
   • Post-seuil : Une fois que le rayon statistique tombe en dessous de $\gamma$, une règle statique passerait immédiatement à la haute fidélité. TACC, cependant, vérifie si une continuation bornée est rentable.
   • Règle de continuation : L'algorithme calcule la diminution anticipée de la correction d'écart $V_{k,t}(s)$ si $s$ requêtes supplémentaires de faible fidélité sont effectuées. Si la réduction de l'écart est suffisante pour potentiellement certifier la sous-optimalité du bras sans confirmation de haute fidélité, et si le coût de ces requêtes supplémentaires est borné (spécifiquement, $S_0 \lambda^{(L)} \le \lambda^{(H)}$), TACC continue l'échantillonnage de faible fidélité. Sinon, il passe à la haute fidélité.

Contributions clés

1. Formulation du problème : L'article formalise le cadre MF-MAB avec des sources de proxy améliorantes, dépassant l'hypothèse de biais statique prévalant dans la littérature antérieure. Il introduit la borne d'écart moyen sélectionné pour modéliser la réduction dynamique du décalage.
2. Conception de l'algorithme : TACC est proposé comme un algorithme optimiste qui associe une sélection de bras standard à une règle de continuation post-seuil bornée. Cette règle décide explicitement si l'« amélioration » de la source de faible fidélité justifie de retarder la requête coûteuse de haute fidélité.
3. Analyse théorique : Les auteurs dérivent une borne de regret dépendante de l'instance. L'analyse partitionne les bras sous-optimaux en trois classes :
   • Bras faciles ($A_\gamma$) : Certifiés par la faible fidélité avant le seuil.
   • Bras intermédiaires ($C_\gamma$) : Non certifiés au seuil statique mais deviennent certifiables après une continuation bornée de faible fidélité.
   • Bras difficiles ($H_\gamma$) : Nécessitent une confirmation de haute fidélité.
     La borne démontre que pour les bras intermédiaires détectés, TACC remplace le coût de confirmation de haute fidélité logarithmique par un coût de continuation de faible fidélité borné.
4. Validation empirique : Des expériences sur des bandits synthétiques et une tâche d'évaluation de politique contrôlée LLM-as-a-judge (LLM en tant que juge) démontrent que TACC réduit le regret pondéré par le coût par rapport aux règles multi-fidélités statiques (MF-UCB) et aux bases de référence uniquement haute fidélité (UCB).

Résultats

Expériences synthétiques

Dans des configurations synthétiques avec 200 et 500 bras, TACC a constamment obtenu un regret pondéré par le coût inférieur à celui de UCB, MF-UCB et des règles à deux fidélités statiques. L'avantage était le plus prononcé dans les scénarios avec des coûts de haute fidélité élevés (par exemple, $\lambda^{(H)} = 50$), où l'évitement de confirmations de haute fidélité inutiles via une continuation bornée a généré des économies significatives.

Expérience LLM-as-a-Judge

Les auteurs ont évalué TACC dans un pipeline d'évaluation de politique où les bras étaient des politiques de prompts pour l'Inférence de Langage Naturel (NLI).

• Configuration : La faible fidélité était un « juge faible » (un LLM plus petit) qui s'améliorait avec l'étalonnage ; la haute fidélité était un « vérificateur » (vérité terrain).
• Constats : TACC a surpassé toutes les bases de référence, y compris une ablation directe (DNC) qui utilisait les mêmes bornes d'écart mais manquait la logique de continuation. TACC a réduit le regret pondéré par le coût final d'environ 10 à 20 % par rapport aux meilleures bases de référence statiques, confirmant que le mécanisme de continuation bornée exploite efficacement la nature améliorante du juge faible pour éviter une escalade prématurée vers le vérificateur coûteux.

Importance et revendications

L'article revendique que la principale signification de ce travail réside dans la reconnaissance que les sources de proxy dans les systèmes d'IA modernes ne sont pas statiques. En traitant la source de faible fidélité comme une entité améliorante, les auteurs montrent que la stratégie optimale ne consiste pas simplement à changer de fidélité en fonction de l'incertitude actuelle, mais à continuer de manière adaptative l'échantillonnage de la source bon marché si l'on s'attend à ce qu'elle s'améliore suffisamment pour résoudre l'ambiguïté.

Les auteurs présentent modestement leur contribution comme un modèle canonique à deux fidélités. Ils reconnaissent les limites, notant que le travail actuel suppose une borne d'écart connue et se concentre sur l'évolution locale au niveau du bras (où l'amélioration se produit uniquement lorsqu'un bras spécifique est interrogé), plutôt que sur un ajustement fin de modèle global affectant tous les bras simultanément. Ce travail sert de étape fondamentale vers des stratégies d'allocation de fidélité plus complexes et dynamiques dans des contextes impliquant des LLM et des simulateurs basés sur l'apprentissage.