🤖 machine learning

A More Accurate Algorithm Comparison through A/B Testing using Offline Evaluation Methods

Cet article remet en question la vision conventionnelle selon laquelle l'A/B testing est toujours supérieur à l'évaluation hors ligne en révélant que l'A/B testing peut souffrir de taux d'erreur de sélection plus élevés en raison d'un manque de corrélation positive, et propose un nouvel estimateur qui induit intentionnellement cette corrélation par une comparaison par étapes avec un algorithme intermédiaire hypothétique afin de réduire considérablement les données nécessaires pour une sélection d'algorithme précise.

Auteurs originaux : Koki Konishi, Masataka Ushiku, Yuta Saito

Publié 2026-07-03

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Koki Konishi, Masataka Ushiku, Yuta Saito

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le gros problème : Choisir la meilleure recette

Imaginez que vous tenez un restaurant et que vous hésitez entre deux nouvelles recettes de soupe : la Recette A et la Recette B. Vous voulez savoir laquelle les clients préfèrent afin de la servir à tout le monde.

Habituellement, la « référence » (la meilleure façon de faire cela) est le Test A/B. Vous servez la Recette A à la moitié de vos clients et la Recette B à l'autre moitié, puis vous comptez les compliments. C'est considéré comme la méthode la plus précise car vous testez sur des données réelles et fraîches.

Cependant, il y a un piège :

C'est coûteux et risqué : Si la Recette B est terrible, vous risquez de gâcher l'expérience de la moitié de vos clients et de perdre de l'argent pendant que vous le découvrez.
Cela nécessite beaucoup de données : Pour en être sûr à 100 %, vous devez servir des milliers de bols.

C'est pourquoi de nombreux restaurants tentent d'abord l'Évaluation Hors-ligne (Offline Evaluation). C'est comme demander à votre chef cuisinier de goûter la soupe en se basant sur un livre de recettes (données historiques) sans réellement la servir aux clients. C'est sûr et peu coûteux, mais c'est généralement moins précis qu'un véritable test de dégustation.

La découverte surprenante

Les auteurs de cet article ont mené un test et ont découvert quelque chose de très étrange et contre-intuitif :

Parfois, la méthode « sûre » (Évaluation Hors-ligne) est en réalité meilleure pour désigner le vainqueur que la « Référence » (Test A/B).

Dans leur expérience, la méthode standard de test A/B (qu'ils appellent AVG) a commis des erreurs environ 27 % du temps, tandis que la méthode hors-ligne n'en a commis que 9 %.

Pourquoi la « Référence » a-t-elle échoué ?
Imaginez que vous jugiez deux coureurs, Alice et Bob.

La méthode de Test A/B (AVG) envoie Alice sur une piste à New York et Bob sur une piste à Londres. Ils courent séparément. Vous mesurez leurs temps de manière indépendante. Comme ils sont dans des lieux différents, leurs temps n'ont aucun lien entre eux. Si Alice passe une mauvaise journée et que Bob passe une excellente journée, vous pourriez croire à tort que Bob est plus rapide, même si Alice est en réalité la meilleure coureuse.
La méthode Hors-ligne (IPS) fait courir Alice et Bob sur la même piste au même moment. Comme ils courent sous les mêmes conditions (même météo, même qualité de piste), leurs temps sont corrélés. Si la piste est boueuse, les deux courent plus lentement. S'il fait beau, les deux courent plus vite. Cette « condition partagée » annule le bruit, ce qui permet de voir plus facilement qui est réellement le plus rapide.

L'article soutient que le test A/B échoue parce qu'il traite les deux algorithmes comme s'ils étaient dans des mondes complètement séparés, manquant ainsi l'avantage de les comparer côte à côte.

La solution : L'intermédiaire (MID)

Les auteurs proposent une nouvelle méthode appelée MID (Middle-In-Difference ou Différence par l'Intermédiaire). Ils veulent la sécurité du test A/B (utiliser des données réelles) mais la précision de la méthode hors-ligne (comparer les choses côte à côte).

Voici comment ils procèdent, en utilisant l'analogie du Tir à la corde :

La configuration : Vous avez l'Équipe A (Algorithme A) et l'Équipe B (Algorithme B). Vous voulez savoir laquelle est la plus forte.
Le problème : Si vous les faites simplement s'affronter directement, la corde pourrait être trop longue et instable (variance élevée).
L'astuce (L'algorithme du milieu) : Les auteurs inventent une « Équipe du Milieu » hypothétique (Équipe M). Cette équipe est un mélange parfait de l'Équipe A et de l'Équipe B.
La course étape par étape :
- Premièrement, vous faites courir l'Équipe A contre l'Équipe M. Vous utilisez les données provenant du côté de l'Équipe A du test A/B. Comme elles font la course contre un adversaire similaire (l'Équipe M), les résultats sont stables.
- Deuxièmement, vous faites courir l'Équipe B contre l'Équipe M. Vous utilisez les données provenant du côté de l'Équipe B du test A/B.
- Enfin, vous additionnez les deux résultats pour voir qui est le plus fort entre A et B.

Pourquoi cela fonctionne :
En introduisant l'« Équipe du Milieu », vous forcez les deux comparaisons à partager un point de référence commun. Tout comme la méthode hors-ligne, cela crée une corrélation positive. Même si l'Équipe A et l'Équipe B sont dans des groupes différents, elles sont toutes deux mesurées par rapport à la même « Équipe du Milieu ». Cela annule le bruit aléatoire et rend la décision finale beaucoup plus précise.

Les résultats

Les auteurs ont testé cela sur des données réelles provenant d'une application de recommandation de vidéos (comme TikTok ou YouTube).

Efficacité : La nouvelle méthode MID a été capable de choisir le meilleur algorithme avec la moitié (voire le quart) de la quantité de données requise par la méthode standard de test A/B.
Stabilité : Lorsque les deux algorithmes étaient très différents l'un de l'autre (ce qui casse habituellement les méthodes hors-ligne), la méthode MID fonctionnait toujours parfaitement.
Précision : Elle a commis moins d'erreurs que le test A/B standard et que la méthode hors-ligne.

Résumé

L'article dit : « Nous avons découvert que la façon standard de réaliser des tests A/B est en fait un peu maladroite car elle ne compare pas les deux options équitablement, côte à côte. Nous avons inventé une nouvelle astuce utilisant un "Algorithme du Milieu" pour forcer une comparaison équitable. Cette nouvelle astuce nous permet de trouver le vainqueur plus rapidement, avec moins de données et avec moins d'erreurs. »

Résumé Technique : Une comparaison d'algorithmes plus précise par des tests A/B utilisant des méthodes d'évaluation hors ligne

1. Énoncé du problème

Dans le développement de services en ligne tels que les systèmes de recommandation et les moteurs de recherche, la sélection de l'algorithme supérieur est critique. Bien que les tests A/B soient largement considérés comme la « référence absolue » pour la sélection d'algorithmes en raison de leur capacité à éliminer les facteurs de confusion par la randomisation, ils sont souvent coûteux et comportent des risques de dégradation de l'expérience utilisateur ou des revenus si un mauvais algorithme est déployé. À l'inverse, l'évaluation hors ligne (utilisant des données de journaux historiques) est plus sûre mais traditionnellement considérée comme moins précise en raison d'une variance d'estimation plus élevée et d'un biais potentiel.

Les auteurs identient un phénomène contre-intuitif : dans certains scénarios, l'estimateur de Moyenne (AVG) standard utilisé dans les tests A/B produit un taux d'erreur de sélection d'algorithme plus élevé que les méthodes d'évaluation hors ligne comme le Score de Propension Inverse (IPS). Le problème central réside dans les propriétés statistiques des estimateurs :

Estimateur AVG : Utilise des données indépendantes pour l'Algorithme A et l'Algorithme B. Par conséquent, les estimations de performance ne sont pas corrélées. La variance de l'estimateur de différence est simplement la somme des variances individuelles ( $Var(\hat{V}_A) + Var(\hat{V}_B)$ ), n'offrant aucun mécanisme pour réduire la variance par la corrélation.
Estimateurs hors ligne (ex: IPS) : Utilisent des données historiques partagées pour estimer la performance de plusieurs algorithmes. Cela induit involontairement une corrélation positive entre les estimateurs. Selon la formule de décomposition de la variance ($Var(X-Y) = Var(X) + Var(Y) - 2Cov(X,Y)$), cette covariance positive réduit la variance totale de l'estimateur de différence, diminuant ainsi la probabilité d'erreurs de sélection critiques (sous-estimer l'algorithme supérieur ou surestimer l'inférieur).

L'article postule que le test A/B échoue à exploiter cette corrélation bénéfique, conduisant à une précision de sélection sous-optimale par rapport aux méthodes hors ligne dans certains pré-expérimentations.

2. Méthodologie : L'estimateur Middle-In-Difference (MID)

Pour remédier au manque de corrélation dans les tests A/B, les auteurs proposent un nouvel estimateur appelé Middle-In-Difference (MID). L'idée centrale est d'induire intentionnellement une corrélation positive au sein du cadre de test A/B en introduisant un algorithme intermédiaire hypothétique ( $\pi_M$ ).

Processus d'estimation par étapes :
Au lieu de comparer directement l'Algorithme A ( $\pi_A$ ) et l'Algorithme B ( $\pi_B$ ), le MID décompose la différence de performance en deux étapes :

Estimer la différence entre $\pi_A$ et $\pi_M$ en utilisant les données de log collectées de $\pi_A$ ( $D_A$ ).
Estimer la différence entre $\pi_M$ et $\pi_B$ en utilisant les données de log collectées de $\pi_B$ ( $D_B$ ).

L'estimateur final est la somme de ces deux différences :
$\Delta \hat{V}_{MID} = (\hat{V}_{IPS}(\pi_A; D_A) - \hat{V}_{IPS}(\pi_M; D_A)) + (\hat{V}_{IPS}(\pi_M; D_B) - \hat{V}_{IPS}(\pi_B; D_B))$

Mécanisme de réduction de la variance :

Corrélation induite : Étant donné que le premier terme utilise des données partagées $D_A$ pour estimer à la fois $\pi_A$ et $\pi_M$ , et que le second terme utilise $D_B$ pour $\pi_M$ et $\pi_B$ , des corrélations positives sont induites au sein de chaque étape. Cela réduit la variance des termes de différence individuels.
Algorithme intermédiaire optimal : Les auteurs dérivent l'algorithme intermédiaire optimal $\pi_M^*$ qui minimise la variance de l'estimateur. La politique optimale est définie comme la moyenne harmonique des politiques de journalisation :
$\pi_M^*(a|x) = \frac{2\pi_A(a|x)\pi_B(a|x)}{\pi_A(a|x) + \pi_B(a|x)}$
Cette conception garantit que $\pi_M$ reste très similaire à la fois à $\pi_A$ et $\pi_B$ , atténuant l'« explosion de variance » souvent observée dans l'évaluation hors ligne lors de la comparaison d'algorithmes très dissemblables (un mode de défaillance courant du standard IPS).

Propriétés théoriques :

Absence de biais (Unbiasedness) : Les auteurs prouvent que si l'algorithme intermédiaire respecte la condition selon laquelle il ne sélectionne que des actions où au moins l'un des algorithmes originaux a une probabilité non nulle, l'estimateur reste sans biais.
Comparaison de variance : L'analyse théorique démontre que le terme de récompense de la variance du MID est strictement inférieur ou égal à celui de l'estimateur AVG standard. De plus, contrairement à l'IPS standard, le MID évite l'explosion de variance $1/\pi_A$ lorsque la similitude entre les algorithmes est faible, car les comparaisons intermédiaires impliquent des politiques similaires.

3. Contributions clés

Insight statistique : L'article clarifie que l'estimateur AVG standard dans les tests A/B n'est pas nécessairement optimal pour la sélection d'algorithmes car il ne parvient pas à exploiter les avantages de réduction de la variance offerts par la corrélation positive entre les estimateurs.
Nouvel estimateur (MID) : Les auteurs proposent l'estimateur MID, qui induit intentionnellement une corrélation positive via un algorithme intermédiaire et une estimation par étapes, atteignant des taux d'erreur de sélection inférieurs à la fois au test A/B standard (AVG) et à l'évaluation hors ligne (IPS).
Dérivation théorique : L'article dérive l'algorithme intermédiaire optimal pour minimiser la variance et fournit une analyse biais-variance montrant pourquoi le MID surpasse les méthodes existantes.
Validation empirique : En utilisant des données de recommandation de vidéos réelles (KuaiRec), les auteurs démontrent que le MID atteint systématiquement des taux d'erreur de sélection plus bas dans diverses configurations.

4. Résultats expérimentaux

Les auteurs ont mené des expériences utilisant le jeu de données KuaiRec, un ensemble de données de recommandation de vidéos entièrement observé permettant le calcul de la performance réelle des algorithmes. Ils ont simulé un environnement de test A/B avec des tailles d'échantillon et des similitudes d'algorithmes variables.

Efficacité de l'échantillonnage : Le MID a atteint le même taux d'erreur de sélection que les méthodes existantes (AVG et IPS) en utilisant seulement la moitié ou le quart de la taille d'échantillon des tests A/B. Par exemple, alors que l'AVG nécessitait 350 à 400 échantillons pour atteindre un taux d'erreur de 5 %, le MID atteignait ce même résultat avec 100 à 200 échantillons.
Robustesse à la similitude :
- Dans les scénarios de haute similitude, le MID a surpassé l'IPS (qui peine généralement avec la variance dans les contextes hors ligne) et l'AVG.
- Dans les scénarios de faible similitude, où l'IPS souffre d'une explosion de variance due à la pondération par importance, le MID est resté stable et a surpassé à la fois l'IPS et l'AVG.
Vérification du mécanisme : Les diagrammes de dispersion des estimations ont confirmé que le MID induit avec succès une corrélation positive entre les estimateurs par étapes, résultant en une distribution plus serrée de l'estimation de la différence finale par rapport à la distribution circulaire (non corrélée) de l'AVG. Cet écart plus étroit est directement corrélé à une réduction des erreurs de sélection critiques.

5. Signification et affirmations

L'article affirme que l'estimateur MID proposé améliore fondamentalement l'efficacité et la précision des tests A/B pour la sélection d'algorithmes. En empruntant le mécanisme statistique de l'évaluation hors ligne (données partagées induisant la corrélation) et en l'appliquant au cadre du test A/B via un algorithme intermédiaire hypothétique, le MID surmonte les limites du test A/B traditionnel (variance élevée due à l'indépendance) et de l'évaluation hors ligne (instabilité due à la faible similitude ou au manque de nouvelles données).

Les auteurs soulignent que cette approche permet aux organisations de prendre des décisions de sélection d'algorithmes plus précises avec nettement moins d'utilisateurs ou des durées d'expérimentation plus courtes, réduisant ainsi le coût et le risque associés à l'expérimentation en ligne. Le travail suggère que la « référence absolue » du test A/B peut être améliorée, non pas en l'abandonnant, mais en affinant la technique d'estimation pour exploiter des corrélations statistiques qui n'étaient auparavant pas exploitées dans les contextes en ligne.