Causal Inference on Stopped Random Walks in Online Advertising

Technisches Resümee: Kausale Inferenz bei gestoppten Random Walks in der Online-Werbung

Problemstellung
Das Paper adressiert eine Herausforderung der kausalen Inferenz, die spezifisch für Online-Werbeplattformen (Publisher) ist, bei der das Ziel darin besteht, den langfristigen Behandlungseffekt von Mechanismusparametern, wie etwa Auktions-Reservepreisen, zu schätzen. Im Gegensatz zu klassischen Settings (z. B. klinische Studien), bei denen die Populationsgröße fix und unabhängig von der Behandlung ist, beinhaltet Online-Werbung ein komplexes, vernetztes System aus Publishern, Nutzern und Werbetreibenden. In dieser Umgebung:

1. Die Behandlung beeinflusst die Populationsgröße: Eine Behandlung (z. B. ein höherer Reservepreis) verändert die Interaktionstrajektorien der Nutzer (Sitzungsdauer) und das Gebotsverhalten der Werbetreibenden (beschränkt durch endliche Budgets), wodurch die Gesamtzahl der generierten Impression-Gelegenheiten über einen festen Zeitraum verändert wird.
2. Interferenz und Dynamik: Die Entscheidung, Behandlungseffekte zu messen, verändert das gemessene System. Nutzersitzungen werden als Markov-Ketten modelliert, und die Budgets der Werbetreibenden entwickeln sich als eine weitere, von vergangenen Auktionsausgängen abhängige Markov-Kette.
3. Skalen-Mismatch der Messung: Die Zielmetrik ist der langfristige Umsatz (z. B. über $k$ Tage), aber die natürliche Beobachtungseinheit ist die einzelne Werbeimpression. Die Anzahl der Impressionen in einem festen Zeitfenster ist eine Zufallsvariable (eine Stoppzeit), die behandlungsabhängig ist.

Die zentrale Schwierigkeit besteht darin, dass Standard-Zentral-Limit-Theorem-Ansätze (CLT), die von identisch und unabhängig verteilten (i.i.d.) Messungen oder festen Stichprobengrößen ausgehen, unzureichend sind. Das Paper modelliert den kumulativen Umsatz als einen gestoppten Random Walk, wobei die Stoppzeit (Gesamtzahl der Impressionen in $k$ Tagen) zufällig und behandlungsabhängig ist.

Methodik

1. Modellierungsrahmen
Die Autoren modellieren die trilaterale Interaktion zwischen Publisher, Nutzern und Werbetreibenden als diskrete Markov-Kette.

• Zustandsraum: Der Zustand umfasst das Profil der besuchten Seiten aller Nutzer ($X_n$), die verbleibenden Budgets aller Werbetreibenden ($\Omega_n$) und den Index des aktiven Nutzers ($I_n$).
• Dynamik: Die Seitenübergänge der Nutzer und die Budgetaktualisierungen der Werbetreibenden werden durch stationäre Strategien (Reservepreis-Funktionen und Gebots-Funktionen) und Zufallsvariablen gesteuert, die das Nutzerverhalten und die Budget-Regeneration repräsentieren.
• Umsatz: Der Umsatz des Publishers ist eine nicht-lineare, potenziell diskontinuierliche Funktion des Reservepreises und des Gewinngebots (Second-Price-Auktionslogik).

2. Dimensionsreduktion: Der Permutations-Trick
Ein großes Hindernis ist die exponentielle Größe des Zustandsraums bei der gleichzeitigen Modellierung von $d$ Nutzern und $m$ Werbetreibenden. Um dies zu adressieren, führen die Autoren einen Permutations-Trick ein:

• Motivation: Basierend auf der Beobachtung, dass die Reihenfolge der Verschachtelung von Seitenübergängen aus verschiedenen gleichzeitigen Nutzersitzungen einen vernachlässigbaren Effekt auf den aggregierten Umsatz und den Cashflow hat, sofern die Zeitskalen der Nutzersitzungen wesentlich kleiner sind als die Dauer der Werbekampagnen.
• Mechanismus: Die Autoren definieren eine Permutation $\sigma$, welche die Sequenz der Impressionen so umordnet, dass alle zu einer Nutzersitzung gehörenden Seitenübergänge zusammen gruppiert werden.
• Ergebnis: Dies transformiert die ursprüngliche hochdimensionale Markov-Kette in eine approximative Kette mit einem signifikant kleineren Zustandsraum ($\mathcal{X} \times \mathbb{R}^m \times [d]$), wobei ganze Nutzersitzungen verschachtelt statt einzelner Seitenübergänge auftreten. Diese Approximation stützt sich auf Annahme 2.1, die postuliert, dass die Budgets und die Dauer der Werbekampagnen groß im Verhältnis zu den Kosten der einzelnen Impressionen und den Sitzungslängen sind.

3. Experimentelles Design: Budget-Splitting
Um den Behandlungseffekt zu schätzen, schlägt das Paper ein Budget-Splitting-Experimentdesign vor (inspiriert durch [LMK21]):

• Populations-Split: Nutzer werden mit Wahrscheinlichkeiten $q$ und $1-q$ zufällig den Subpopulationen $A$ und $B$ zugewiesen.
• Behandlungszuweisung: Subpopulation $A$ erhält die Behandlung $v$ (Reservepreis $v$) und $B$ erhält die Behandlung $w$.
• Budget-Splitting: Das Budget jedes Werbetreibenden wird proportional ($q$ und $1-q$) zwischen den beiden Subpopulationen aufgeteilt. Werbetreibende in jeder Gruppe konkurrieren nur innerhalb der ihnen zugewiesenen Markov-Kette der Subpopulation.
• Schätzer: Der Schätzer $\hat{\Delta}$ für den gesamten Behandlungseffekt wird konstruiert, indem der beobachtete durchschnittliche Umsatz und die Impression-Anzahlen der Subpopulationen jeweils mit $1/q$ bzw. $1/(1-q)$ skaliert werden, was effektiv eine Extrapolation der Subpopulationsergebnisse auf die gesamte Population darstellt.

4. Theoretische Garantien
Die Autoren leiten ein Konfidenzintervall für den langfristigen Behandlungseffekt $\Delta$ ab unter Verwendung von:

• Markov-Ketten-CLT: Angewendet auf die permutierten Ketten, um die asymptotische Normalität der Umsatzsummen zu etablieren.
• Wald-ähnlicher Gleichung: Zur Handhabung der zufälligen Stoppzeiten (Gesamtzahl der Impressionen über $k$ Tage).
• Anscombe-Theorem: Angewendet, um zu rechtfertigen, dass der gestoppte Random Walk gegen eine Normalverteilung konvergiert, trotz der zufälligen Stichprobengröße.
• Ergodizitäts-Annahmen: Die Analyse setzt voraus, dass die zugrunde liegenden Markov-Ketten Harris-ergodisch und geometrisch ergodisch sind, was die Existenz von invarianten Verteilungen sicherstellt.

Wesentliche Beiträge

1. Modellierung: Einführung eines gestoppten Random-Walk-Modells für die kausale Inferenz, bei dem die Populationsgröße (Anzahl der Impressionen) eine Zufallsvariable und behandlungsabhängig ist. Dies generalisiert die klassische kausale Inferenz, die typischerweise eine feste Population annimmt.
2. Analytik: Entwicklung eines Permutations-Tricks zur Reduktion der Dimension des Zustandsraums in mehr-Nutzer-, mehr-Werbetreibenden-Markov-Systemen, was eine handhabbare Analyse unter milden Annahmen bezüglich der Zeitskalen ermöglicht.
3. Statistische Inferenz: Ableitung von Konfidenzintervallen für langfristige Behandlungseffekte in diesem komplexen Setting durch Kombination eines Markov-CLT, einer Wald-ähnlichen Gleichung und des Anscombe-Theorems. Dies bietet eine theoretische Basis für die Bestimmung der notwendigen Experimentdauer.

Ergebnisse
Das Hauptergebnis (Theorem 3.6) stellt fest, dass unter den Annahmen zeitinvarianter Strategien, Ergodizität und Kampagnenskala der vorgeschlagene Schätzer $\hat{\Delta}$ gegen den wahren Behandlungseffekt $\Delta$ konvergiert. Speziell beweist das Paper, dass:
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
wobei $\epsilon$ eine von den asymptotischen Varianzen der Subpopulationsketten und dem Unterschied zwischen den invarianten Verteilungen der Subpopulation und der Gesamtpopulation abhängige Schranke ist. Das Paper stellt fest, dass in der Praxis bei großen Nutzerpopulationen diese Verteilungen erwartungsgemäß nah beieinander liegen, was den Schätzer effektiv macht.

Bedeutung und Ansprüche
Das Paper beansprucht, einen rigorosen Rahmen für die kausale Inferenz in Online-Werbesystemen bereitzustellen, in denen die "Analyseeinheit" (die Nutzersitzung) und die "Messeinheit" (die Impression) auf unterschiedlichen Skalen operieren und in denen die Behandlung selbst das Volumen der generierten Daten verändert.

• Es geht über die "Finite-Population"-Annahme der klassischen kausalen Inferenz hinaus zu einer zufälligen, behandlungsabhängigen Population.
• Es bietet eine praktische Lösung für das "Interferenz-Problem" in zweiseitigen Märkten, indem es die Dynamiken von Nutzern und Werbetreibenden explizit modelliert, anstatt sich allein auf Randomisierungstechniken zur Kontrolle von Interferenzen zu verlassen.
• Es liefert eine handlungsleitende Orientierung für die Experimentdauer, indem es die Breite des Konfidenzintervalls mit den asymptotischen Varianzen und der Anzahl der Perioden $k$ verknüpft.

Die Autoren räumen Einschränkungen ein und merken an, dass das Modell stationäre Strategien voraussetzt und nicht-stationäre Dynamiken (z. B. neu eintretende Werbetreibende) nicht explizit behandelt. Sie legen zudem nahe, dass das Budget-Splitting-Design zwar effektiv ist, aber möglicherweise keine beliebigen Interferenzeffekte korrigieren kann, die nicht durch das spezifische Markov-Modell erfasst werden.