Exploiting Similarities in A/B Testing with Off-Policy Estimation

Résumé Technique : Exploiter les similitudes dans les tests A/B via l'estimation hors-politique (Off-Policy Estimation)

Énoncé du Problème
Le test A/B est le protocole standard pour mesurer le gain de performance d'un nouveau système de décision ($\pi_A$) par rapport à une base de référence ($\pi_B$). Traditionnellement, cela est effectué à l'aide d'un estimateur de différence de moyennes, qui traite les deux systèmes comme des boîtes noires. Bien qu'impartial, cet estimateur est statistiquement sous-optimal car il ignore les similitudes structurelles potentielles entre les politiques. Dans les applications en ligne modernes (par exemple, la publicité, la recommandation), les systèmes de décision sont souvent stochastiques et partagent une structure significative, ce qui signifie qu'ils ont des « propensions » similaires à prendre des décisions spécifiques. L'article soutient que lorsque les politiques se chevauchent, l'estimateur classique souffre d'une variance inutile, tandis que les méthodes classiques d'estimation hors-politique (OPE), qui reposent sur la pondération par l'importance, sont souvent trop biaisées ou instables pour remplacer directement le test A/B.

Méthodologie
Les auteurs proposent une famille d'estimateurs de tests A/B qui exploitent les techniques d'estimation hors-politique pour tirer parti du chevauchement entre $\pi_A$ et $\pi_B$ sans modifier le protocole expérimental standard.

1. Cadre : Le problème est modélisé dans un cadre étendu de processus de décision de Markov non markovien (NMDP) où les utilisateurs interagissent avec le système via des trajectoires $\tau$. L'objectif est d'estimer l'amélioration $I(\pi_A, \pi_B) = V(\pi_A) - V(\pi_B)$.
2. Construction de l'estimateur : L'estimateur proposé $\hat{I}_f$ combine deux composantes :
   • Un terme de score d'importance inverse (IPS) régularisé par $f$ utilisant les données de la politique de base ($D_B$).
   • Un terme de correction de biais utilisant les données de la politique cible ($D_A$).
   • La fonction $f: \mathbb{R}_+ \to \mathbb{R}$ transforme les poids d'importance $w(\tau) = \pi_{target}(\tau) / \pi_{source}(\tau)$.
3. Conditions Théoriques :
   • Impartialité (Unbiasedness) : L'estimateur est impartial si $f(0) = -1$. Cette condition garantit que lorsque les politiques ont des supports disjoints (aucun chevauchement), l'estimateur revient naturellement à l'estimateur standard de différence de moyennes.
   • Réduction de la Variance : Pour réduire la variance, les auteurs définissent un substitut de variance $S_f$. Ils dérivent des conditions sur $f$ (spécifiquement $f(1)=0$ et des bornes sur $f(x)$) qui garantissent une variance plus faible que l'estimateur de différence de moyennes lorsque les politiques sont similaires.
4. Transformations Optimales :
   • Surrogate-Optimale ($f^*_{n_r}$) : Les auteurs dérivent une fonction en forme fermée $f^*_{n_r}(x) = \frac{x-1}{n_r x + 1}$ (où $n_r = n_A/n_B$) qui minimise le substitut de variance. Cet estimateur repondère efficacement les données des deux populations pour tenir compte du déséquilibre des échantillons.
   • Sensible à la spécification erronée (Misspecification-Aware) ($f^*_{\lambda, \Delta}$) : Reconnaissant que les propensions sont souvent estimées à partir de données plutôt que connues, les auteurs introduisent un paramètre de régularisation $\lambda$ pour équilibrer le biais et la variance sous la spécification erronée des propensions. Cela produit un estimateur robuste qui se dégrade gracieusement vers l'estimateur de différence de moyennes à mesure que la spécification erronée augmente.

Contributions Clés

• Nouvelle famille d'estimateurs : Introduction d'une famille flexible d'estimateurs de tests A/B basés sur la pondération par l'importance qui exploite explicitement le chevauchement des politiques.
• Garanties Théoriques : Preuve que les estimateurs sont impartiaux sous des conditions spécifiques sur $f$ et démontrent des propriétés de concentration améliorées (variance réduite) lorsque les politiques sont similaires.
• Robustesse : Développement de variantes sensibles à la spécification erronée qui restent robustes lorsque les propensions sont estimées à partir de données, évitant la variance élevée ou le biais typique des méthodes OPE standard.
• Dégradation Gracieuse : Les estimateurs sont conçus pour revenir automatiquement à l'estimateur standard de différence de moyennes lorsque les politiques sont distinctes (aucun chevauchement) ou lorsque la spécification erronée est sévère, garantissant l'absence de perte de performance dans les scénarios défavorables.

Résultats Expérimentaux
Les auteurs valident leur approche à travers trois contextes expérimentaux :

1. Politiques de Chevauchement et Déséquilibre de Données : Dans un cadre de bandit simplifié, les estimateurs proposés ont obtenu une réduction de variance substantielle (jusqu'à 27x dans certains scénarios) lorsque les politiques étaient proches. La réduction était particulièrement efficace pour gérer les allocations d'utilisateurs déséquilibrées ($n_A \neq n_B$), là où l'estimateur de différence standard peine.
2. Sensibilité à la Spécification Erronée : Dans des scénarios avec des erreurs induites dans l'estimation des propensions, l'IPS standard et les estimateurs régularisés naïfs ($h_1$) ont montré une erreur quadratique moyenne (MSE) élevée. En revanche, les estimateurs sensibles à la spécification erronée proposés ont systématiquement surpassé l'estimateur de référence de différence de moyennes, maintenant une MSE plus faible même sous des niveaux de spécification erronée modérés à élevés.
3. Problème de Recommandation Réaliste : Simulant un environnement de recommandation non markovien avec ennui de l'utilisateur, les auteurs ont testé des horizons $T \in \{1, \dots, 32\}$. L'estimateur optimal de variance ($f^*_1$) a considérablement réduit la MSE pour les horizons courts à modérés. Cependant, pour les horizons longs, l'accumulation d'erreurs dans l'estimation des propensions a dégradé les performances. L'estimateur sensible à la spécification erronée a fourni des gains stables et modestes sur tous les horizons, surpassant à la fois l'estimateur de différence standard et les autres approches OPE comme DiffQ.

Signification et Revendications
L'article soutient que les idées d'estimation hors-politique ne doivent pas simplement servir de substitut aux tests A/B, mais comme un outil pour améliorer l'efficacité statistique des tests A/B eux-mêmes. En exploitant les propensions connues ou estimées des systèmes testés, les praticiens peuvent obtenir des estimations d'amélioration plus précises avec la même taille d'échantillon. La méthode proposée est significative car elle :

• Ne nécessite aucun changement au protocole de collecte de données standard des tests A/B.
• Est robuste à la réalité pratique des propensions estimées.
• Offre un scénario de « meilleur des deux mondes » : elle offre une réduction de variance substantielle lorsque les politiques sont similaires (le cas courant dans les mises à jour itératives de systèmes) tout en garantissant la sécurité (pas pire que les tests A/B standards) lorsqu'elles ne le sont pas.

Les auteurs concluent que bien que leur approche traite le problème de la variance dans les politiques chevauchantes, des défis subsistent pour les horizons très longs où la dérive de la propension est significative, suggérant que les travaux futurs devraient exploiter les structures séquentielles et les méthodes de double robustesse.