Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards

1. Problématique et Contexte

Le problème des Bandits Multi-Bras (MAB) est un cadre fondamental pour la prise de décision séquentielle sous incertitude, où un décideur doit équilibrer l'exploration (tester de nouvelles actions) et l'exploitation (choisir la meilleure action connue) pour maximiser la récompense cumulative.

Le défi principal : Les algorithmes traditionnels (comme UCB ou Thompson Sampling) reposent uniquement sur des données en ligne, qui sont souvent rares et coûteuses à collecter car elles nécessitent de tirer les bras activement. Dans de nombreux scénarios réels (essais cliniques, recommandation de contenu, sélection de modèles de langage), des données auxiliaires riches (historiques, caractéristiques des utilisateurs) sont disponibles avant le déploiement, mais les récompenses réelles ne le sont pas.

L'approche proposée : Utiliser des modèles d'apprentissage automatique (ML) pré-entraînés pour générer des récompenses surrogées (prédictions) basées sur ces données offline.

• Le problème de biais : Ces récompenses surrogées sont souvent biaisées par rapport aux vraies récompenses (les moyennes ne correspondent pas) et peuvent nécessiter une extrapolation vers des environnements non vus.
• L'hypothèse clé : Bien que biaisées, les récompenses surrogées sont corrélées avec les vraies récompenses. L'objectif est d'exploiter cette corrélation pour réduire la variance de l'estimation, même en présence d'un biais arbitraire, sans connaître la matrice de covariance ni le biais lui-même.

2. Méthodologie : L'algorithme MLA-UCB

Les auteurs proposent l'algorithme MLA-UCB (Machine Learning-Assisted Upper Confidence Bound), qui intègre les récompenses surrogées dans le cadre classique UCB.

Estimation de la moyenne assistée par ML

L'estimateur central est une variante de l'inférence alimentée par la prédiction (Prediction-Powered Inference - PPI). Pour un bras $k$, l'estimateur de la moyenne $\hat{\mu}_k$ combine :

1. La moyenne des vraies récompenses en ligne ($\bar{R}_{online}$).
2. La différence entre la moyenne des prédictions en ligne et la moyenne des prédictions offline ($\bar{\hat{R}}_{online} - \bar{\hat{R}}_{offline}$).
3. Un coefficient de pondération $\hat{\lambda}$ estimé à partir des données, qui agit comme un estimateur de contrôle de variance.

Formellement, l'estimateur est défini comme l'ordonnée à l'origine d'une régression des moindres carrés (OLS) des vraies récompenses sur les prédictions, ajustée pour inclure les données offline.

Construction de la borne de confiance

Contrairement aux UCB classiques qui supposent souvent une variance connue ou utilisent des bornes asymptotiques, MLA-UCB construit des bornes de confiance exactes pour des échantillons finis :

• Modèle Gaussien : En supposant que les vraies et surrogées récompenses suivent une loi normale bivariée, les auteurs dérivent la distribution exacte de l'erreur d'estimation. Ils utilisent une statistique t de Student avec une estimation de variance adaptative et un niveau de signification dépendant du temps ($1/(2t\sqrt{\log t})$).
• Cas Batché et Non-Gaussien : Pour des distributions non gaussiennes et des données en lots (batched rewards), l'algorithme utilise des bornes de déviation modérée autonormalisées (self-normalized moderate deviation bounds) pour garantir la validité des intervalles de confiance.

Algorithme

À chaque tour $t$, l'algorithme sélectionne le bras maximisant la borne supérieure de confiance :
$$A_t = \arg\max_k \left( \hat{\mu}^{MLA}_{k, n_k, t} + \text{Terme d'incertitude} \right)$$
Le terme d'incertitude est proportionnel à la racine carrée de la variance résiduelle réduite par la corrélation $\rho_k$.

3. Contributions Clés

1. Nouveau Cadre Théorique : Introduction d'un cadre MAB où les récompenses surrogées peuvent être arbitrairement biaisées (les moyennes ne préservent pas le classement) mais sont corrélées aux vraies récompenses.
2. Algorithme MLA-UCB : Un algorithme qui ne nécessite aucune connaissance a priori de la variance des récompenses, de la corrélation $\rho$, ou du biais. Il est applicable à n'importe quel modèle de prédiction ML.
3. Garanties de Regret Asymptotiquement Optimales :
   • Sous hypothèse gaussienne, les auteurs prouvent que le regret cumulé est borné par :
     $$O\left( \sum_{k \neq k^*} \frac{\Delta_k \log T}{\log(1 + \frac{\Delta_k^2}{\sigma_k^2 (1-\rho_k^2)})} \right)$$
   • Cela démontre que le regret est réduit d'un facteur proportionnel à $(1-\rho_k^2)$. Si la corrélation est forte ($\rho \to 1$), le regret tend vers zéro plus rapidement.
   • Ils établissent également une borne inférieure prouvant que MLA-UCB atteint l'optimalité asymptotique pour cette classe de problèmes.
4. Extension aux Données Non-Gaussiennes et Batchées : Dérivation de garanties de regret pour des distributions générales (via des bornes de déviation modérée) et pour des scénarios où les décisions sont appliquées à des lots d'individus (batched rewards), ce qui est courant dans les applications industrielles.

4. Résultats Expérimentaux

Les auteurs valident leur approche par des simulations et des études de cas réels :

• Simulations Gaussiennes : MLA-UCB surpasse systématiquement l'UCB classique. La réduction du regret est plus marquée avec un nombre accru d'échantillons offline et une corrélation plus forte. Même avec un biais important, la méthode fonctionne.
• Simulations Non-Gaussiennes (ML Généré) : Utilisation de modèles ML réels (Régression Linéaire, SVR, Réseaux de Neurones, Arbres de Décision) pour générer des surrogés non gaussiens. Malgré la violation des hypothèses gaussiennes strictes, MLA-UCB réduit significativement le regret par rapport à UCB.
• Études de Cas Réels :
  1. Sélection de Modèles de Langage (LLM) : Utilisation de modèles open-source (Llama) comme surrogés pour sélectionner des modèles propriétaires (GPT-4, Claude). Les résultats montrent une réduction proportionnelle du regret.
  2. Recommandation Vidéo : Utilisation d'un modèle de régression sur les caractéristiques utilisateurs/vidéos pour guider la recommandation de vidéos sur la plateforme Kuaishou. L'algorithme améliore l'engagement utilisateur par rapport à UCB standard.

5. Signification et Impact

Ce travail est significatif car il comble le fossé entre l'inférence statique assistée par ML (PPI) et la prise de décision dynamique (Bandits).

• Robustesse au Biais : Contrairement aux méthodes précédentes qui nécessitent que les données offline soient non biaisées ou que le biais soit borné, MLA-UCB fonctionne même si les prédictions ML sont totalement désalignées en moyenne, tant qu'elles sont corrélées.
• Efficacité des Données : Il permet d'utiliser massivement des données historiques bon marché (surrogées) pour accélérer l'apprentissage en ligne, réduisant ainsi le coût et le temps nécessaires pour identifier les meilleures actions.
• Applicabilité Générale : L'absence de besoin de connaître les paramètres de variance ou de covariance rend l'algorithme prêt à l'emploi dans des environnements complexes où ces métriques sont inconnues.

En résumé, l'article propose une méthode rigoureuse et théoriquement fondée pour intégrer l'intelligence artificielle générative dans les boucles de décision séquentielle, transformant les prédictions imparfaites en un levier puissant pour réduire l'incertitude et le regret.