Causal Inference on Stopped Random Walks in Online Advertising

Résumé Technique : Inférence Causale sur les Marches Aléatoires Arrêtées dans la Publicité en Ligne

Énoncé du Problème

L'article traite d'un défi d'inférence causale spécifique aux plateformes de publicité en ligne (éditeurs) où l'objectif est d'estimer l'effet de traitement à long terme des paramètres de mécanisme, tels que les prix de réserve des enchères. Contrairement aux contextes classiques (ex. : essais cliniques) où la taille de la population est fixe et indépendante du traitement, la publicité en ligne implique un système complexe et interconnecté d'éditeurs, d'utilisateurs et d'annonceurs. Dans cet environnement :

1. Le traitement affecte la taille de la population : Un traitement (ex. : un prix de réserve plus élevé) modifie les trajectoires d'interaction des utilisateurs (longueur de session) et les comportements d'enchères des annonceurs (contraints par des budgets finis), modifiant ainsi le nombre total d'opportunités d'impressions générées sur une période de temps fixe.
2. Interférence et Dynamique : La décision de mesurer les effets de traitement modifie le système même qui est mesuré. Les sessions d'utilisateurs sont modélisées comme des chaînes de Markov, et les budgets des annonceurs évoluent comme une autre chaîne de Markov dépendant des résultats passés des enchères.
3. Décalage d'Échelle de Mesure : La métrique cible est le revenu à long terme (ex. : sur $k$ jours), mais l'unité naturelle d'observation est l'impression publicitaire individuelle. Le nombre d'impressions dans une fenêtre de temps fixe est une variable aléatoire (un temps d'arrêt) dépendant du traitement.

La difficulté centrale est que les approches classiques du Théorème Central Limite (TCL) supposant des mesures indépendantes et identiquement distribuées (i.i.d.) ou des tailles d'échantillon fixes sont insuffisantes. L'article modélise le revenu cumulé comme une marche aléatoire arrêtée, où le temps d'arrêt (le nombre total d'impressions en $k$ jours) est aléatoire et dépendant du traitement.

Méthodologie

1. Cadre de Modélisation
Les auteurs modélisent l'interaction trilatérale entre l'éditeur, les utilisateurs et les annonceurs comme une chaîne de Markov à temps discret.

• Espace d'États : L'état comprend le profil des pages visitées par tous les utilisateurs ($X_n$), les budgets restants de tous les annonceurs ($\Omega_n$), et l'indice de l'utilisateur actif ($I_n$).
• Dynamique : Les transitions de pages des utilisateurs et les mises à jour de budget des annonceurs sont régies par des stratégies stationnaires (fonctions de prix de réserve et fonctions d'enchères) et des variables aléatoires représentant le comportement des utilisateurs et le réapprovisionnement des budgets.
• Revenu : Le revenu de l'éditeur est une fonction non linéaire, potentiellement discontinue, du prix de réserve et de l'enchère gagnante (logique d'enchère au second prix).

2. Réduction de Dimensionnalité : L'Astuce de la Permutation
Un obstacle majeur est la taille exponentielle de l'espace d'états lors de la modélisation simultanée de $d$ utilisateurs et $m$ annonceurs. Pour y remédier, les auteurs introduisent une astuce de permutation :

• Motivation : Basée sur l'observation que l'ordre d'entrelacement des transitions de pages provenant de différentes sessions d'utilisateurs concurrentes a un effet négligeable sur les ventes globales et les flux de trésorerie, à condition que les échelles de temps des sessions d'utilisateurs soient beaucoup plus courtes que les durées des campagnes des annonceurs.
• Mécanisme : Les auteurs définissent une permutation $\sigma$ qui réordonne la séquence des impressions pour regrouper toutes les transitions de pages appartenant à une même session d'utilisateur.
• Résultat : Cela transforme la chaîne de Markov de haute dimension originale en une chaîne approximative avec un espace d'états considérablement réduit ($\mathcal{X} \times \mathbb{R}^m \times [d]$), où des sessions d'utilisateurs entières sont entrelacées plutôt que des transitions de pages individuelles. Cette approximation repose sur l'Hypothèse 2.1, qui postule que les budgets et les durées des campagnes publicitaires sont grands par rapport aux coûts d'impression individuels et aux longueurs de session.

3. Conception Expérimentale : Division du Budget
Pour estimer l'effet de traitement, l'article propose une conception expérimentale par division de budget (inspirée de [LMK21]) :

• Division de la Population : Les utilisateurs sont assignés aléatoirement à des sous-populations $A$ et $B$ avec des probabilités $q$ et $1-q$.
• Assignation du Traitement : La sous-population $A$ reçoit le traitement $v$ (prix de réserve $v$) et la sous-population $B$ reçoit le traitement $w$.
• Division du Budget : Le budget de chaque annonceur est divisé proportionnellement ($q$ et $1-q$) entre les deux sous-populations. Les annonceurs de chaque groupe ne concourent que dans la chaîne de Markov de leur sous-population assignée.
• Estimateur : L'estimateur $\hat{\Delta}$ de l'effet de traitement total est construit en mettant à l'échelle le revenu moyen observé et les nombres d'impressions des sous-populations par $1/q$ et $1/(1-q)$ respectivement, extrapolant ainsi les résultats des sous-populations à la population entière.

4. Garanties Théoriques
Les auteurs dérivent un intervalle de confiance pour l'effet de traitement à long terme $\Delta$ en utilisant :

• TCL pour les Chaînes de Markov : Appliqué aux chaînes permutées pour établir la normalité asymptotique des sommes de revenus.
• Équation de type Wald : Utilisée pour gérer les temps d'arrêt aléatoires (nombre total d'impressions sur $k$ jours).
• Théorème d'Anscombe : Employé pour justifier la convergence de la marche aléatoire arrêtée vers une distribution normale malgré la taille d'échantillon aléatoire.
• Hypothèses d'Ergodicité : L'analyse suppose que les chaînes de Markov sous-jacentes sont Harris ergodiques et géométriquement ergodiques, garantissant l'existence de distributions invariantes.

Contributions Clés

1. Modélisation : Introduction d'un modèle de marche aléatoire arrêtée pour l'inférence causale où la taille de la population (nombre d'impressions) est aléatoire et dépendante du traitement. Cela généralise l'inférence causale classique qui suppose généralement une population fixe.
2. Analytique : Développement d'une astuce de permutation pour réduire la dimensionnalité de l'espace d'états dans les systèmes markoviens multi-utilisateurs et multi-annonceurs, permettant une analyse traitable sous des hypothèses modérées concernant les échelles de temps.
3. Inférence Statistique : Dérivation d'intervalles de confiance pour les effets de traitement à long terme dans ce contexte complexe en combinant un TCL markovien, une équation de type Wald et le théorème d'Anscombe. Cela fournit une base théorique pour déterminer la durée nécessaire des expériences.

Résultats
Le résultat principal (Théorème 3.6) établit que sous les hypothèses de stratégies invariantes dans le temps, d'ergodicité et d'échelle de campagne, l'estimateur proposé $\hat{\Delta}$ converge vers le véritable effet de traitement $\Delta$. Plus précisément, l'article prouve que :
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
où $\epsilon$ est une borne dépendant des variances asymptotiques des chaînes des sous-populations et de la différence entre les distributions invariantes de la sous-population et de la population totale. L'article note qu'en pratique, avec de grandes populations d'utilisateurs, ces distributions sont censées être proches, rendant l'estimateur efficace.

Signification et Revendications
L'article prétend fournir un cadre rigoureux pour l'inférence causale dans les systèmes de publicité en ligne où l'« unité d'analyse » (la session utilisateur) et l'« unité de mesure » (l'impression) opèrent à des échelles différentes, et où le traitement lui-même modifie le volume de données générées.

• Il dépasse l'hypothèse de « population finie » de l'inférence causale classique pour une population aléatoire et dépendante du traitement.
• Il offre une solution pratique au problème d'« interférence » dans les marchés à deux faces en modélisant explicitement la dynamique des utilisateurs et des annonceurs plutôt qu'en s'appuyant uniquement sur des techniques de randomisation pour contrôler l'interférence.
• Il fournit des orientations exploitables sur la durée des expériences en liant la largeur de l'intervalle de confiance aux variances asymptotiques et au nombre de périodes $k$.

Les auteurs reconnaissent des limites, notant que leur modèle suppose des stratégies stationnaires et ne traite pas explicitement les dynamiques non stationnaires (ex. : entrée de nouveaux annonceurs dans le système). Ils suggèrent également que, bien que la conception par division de budget soit efficace, elle peut ne pas corriger les effets d'interférence arbitraires non capturés par le modèle markovien spécifique.