Causal Inference on Stopped Random Walks in Online Advertising

Technische Samenvatting: Causale Inferentie op Gestopte Random Walks in Online Advertering

Probleemstelling
Het artikel behandelt een uitdaging op het gebied van causale inferentie die specifiek is voor online advertentieplatformen (publishers), waarbij het doel is om het langetermijneffect van mechanismeparameters, zoals de reserveprijzen van veilingen, te schatten. In tegenstelling tot klassieke instellingen (bijv. klinische studies met medicijnen) waarbij de populatiegrootte vaststaat en onafhankelijk is van de behandeling, betreft online advertering een complex, onderling verbonden systeem van uitgevers, gebruikers en adverteerders. In deze omgeving:

1. Behandeling beïnvloedt de populatiegrootte: Een behandeling (bijv. een hogere reserveprijs) verandert de interactietrajecten van gebruikers (sessieduur) en het biedgedrag van adverteerders (beperkt door eindige budgetten), waardoor het totale aantal impressie-gelegenheden over een vaste periode wordt gewijzigd.
2. Interferentie en Dynamiek: De beslissing om het effect van een behandeling te meten, verandert het systeem dat wordt gemeten. Gebruikerssessies worden gemodelleerd als Markov-ketens, en de budgetten van adverteerders evolueren als een andere Markov-keten die afhankelijk is van voorgaande veilingresultaten.
3. Mismatch in Meetschaal: De doelmetriek is de langetermijnomzet (bijv. over $k$ dagen), maar de natuurlijke eenheid van observatie is de individuele advertentie-impressie. Het aantal impressies in een vaste tijdsperiode is een willekeurige variabele (een stoptijd) die afhankelijk is van de behandeling.

De kern van de moeilijkheid is dat standaard Central Limit Theorem (CLT)-benaderingen die uitgaan van onafhankelijke en identiek verdeelde (i.i.d.) metingen of vaste steekproefomvang, ontoereikend zijn. Het artikel modelleert de cumulatieve omzet als een gestopte random walk, waarbij de stoptijd (het totaal aantal impressies in $k$ dagen) willekeurig en behandelingsafhankelijk is.

Methodologie

1. Modelleringskader
De auteurs modelleren de trilaterale interactie tussen de uitgever, gebruikers en adverteerders als een discrete-tijd Markov-keten.

• Toerustingsruimte (State Space): De toestand bevat het profiel van de bezochte pagina's door alle gebruikers ($X_n$), de resterende budgetten van alle adverteerders ($\Omega_n$), en de index van de actieve gebruiker ($I_n$).
• Dynamiek: De paginatransities van gebruikers en de budgetupdates van adverteerders worden beheerst door stationaire strategieën (reserveprijsfuncties en biedfuncties) en willekeurige variabelen die het gebruikersgedrag en de budgetaanvulling vertegenwoordigen.
• Omzet: De omzet van de uitgever is een niet-lineaire, potentieel discontinue functie van de reserveprijs en het winnende bod (second-price auction logica).

2. Dimensiereductie: De Permutatie-truc
Een grote hindernis is de exponentiële grootte van de toestelruimte bij het gelijktijdig modelleren van $d$ gebruikers en $m$ adverteerders. Om dit aan te pakken, introduceren de auteurs een permutatie-truc:

• Motivatie: Gebaseerd op de observatie dat de volgorde van het verweven van paginatransities uit verschillende gelijktijdige gebruikerssessies een verwaarloosbaar effect heeft op de geaggregeerde verkopen en kasstroom, mits de tijdsschalen van gebruikerssessies veel kleiner zijn dan de campagneduur van adverteerders.
• Mechanisme: De auteurs definiëren een permutatie $\sigma$ die de reeks impressies herordent om alle paginatransities die bij dezelfde gebruikerssessie horen, samen te groeperen.
• Resultaat: Dit transformeert de oorspronkelijke hoogdimensionale Markov-keten in een benaderde keten met een aanzienlijk kleinere toestelruimte ($\mathcal{X} \times \mathbb{R}^m \times [d]$), waarbij volledige gebruikerssessies worden verweven in plaats van individuele paginatransities. Deze benadering rust op Assumptie 2.1, die stelt dat de budgetten en de duur van advertentiecampagnes groot zijn in verhouding tot de kosten van individuele impressies en sessieduur.

3. Experimenteel Ontwerp: Budgetsplitsing
Om het behandeldingseffect te schatten, stelt het artikel een budgetsplitsing-experimenteel ontwerp voor (geïnspireerd door [LMK21]):

• Populatiesplit: Gebruikers worden willekeurig toegewezen aan subpopulaties $A$ en $B$ met kansen $q$ en $1-q$.
• Toewijzing van Behandeling: Subpopulatie $A$ ontvangt behandeling $v$ (reserveprijs $v$) en $B$ ontvangt behandeling $w$.
• Budgetsplitsing: Het budget van elke adverteerder wordt proportioneel gesplitst ($q$ en $1-q$) tussen de twee subpopulaties. Adverteerders in elke groep concurreren alleen binnen hun toegewezen subpopulatie Markov-keten.
• Estimator: De estimator $\hat{\Delta}$ voor het totale behandeldingseffect wordt geconstrueerd door de geobserveerde gemiddelde omzet en impressieaantallen van de subpopulaties te schalen met respectievelijk $1/q$ en $1/(1-q)$, wat effectief de resultaten van de subpopulatie extrapoleert naar de volledige populatie.

4. Theoretische Garanties
Het artikel leidt een betrouwbaarheidsinterval af voor het langetermijneffect van de behandeling $\Delta$ met behulp van:

• Markov-keten CLT: Toegepast op de gepermuteerde ketens om de asymptotische normaliteit van de omzet-sommen vast te stellen.
• Wald-achtige Vergelijking: Gebruikt om de willekeurige stoptijden (totaal aantal impressies over $k$ dagen) te behandelen.
• Anscombe-stelling: Toegepast om te rechtvaardigen dat de convergentie van de gestopte random walk naar een normale verdeling plaatsvindt, ondanks de willekeurige steekproefomvang.
• Ergodiciteitsveronderstellingen: De analyse gaat ervan uit dat de onderliggende Markov-ketens Harris-ergodisch en geometrisch ergodisch zijn, wat de existentie van invariante distributies waarborgt.

Belangrijkste Bijdragen

1. Modellering: Introductie van een gestopte random walk model voor causale inferentie waarbij de populatiegrootte (aantal impressies) willekeurig en behandelingsafhankelijk is. Dit generaliseert de klassieke causale inferentie die doorgaans een vaste populatie veronderstelt.
2. Analytisch: Ontwikkeling van een permutatie-truc om de dimensionaliteit van de toestelruimte te reduceren in multi-gebruiker, multi-adverteerder Markoviaanse systemen, wat een hanteerbare analyse mogelijk maakt onder milde aannames over de tijdschalen.
3. Statistische Inferentie: Afleiding van betrouwbaarheidsintervallen voor langetermijn-behandelingseffecten in deze complexe setting door een Markoviaanse CLT, een Wald-achtige vergelijking en de Anscombe-stelling te combineren. Dit biedt een theoretische basis voor het bepalen van de noodzakelijke experimentduur.

Resultaten
De belangrijkste resultaat (Theorem 3.6) stelt vast dat onder aannames van tijd-invariante strategieën, ergodiciteit en campagne-schaal, de voorgestelde estimator $\hat{\Delta}$ convergeert naar het ware behandeldingseffect $\Delta$. Specifiek bewijst het artikel dat:
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
waarbij $\epsilon$ een grens is die afhankelijk is van de asymptotische varianties van de subpopulatie-ketens en het verschil tussen de subpopulatie en de volledige populatie invariante distributies. Het artikel merkt op dat in de praktijk, bij grote gebruikerspopulaties, deze distributies naar verwachting dicht bij elkaar liggen, wat de estimator effectief maakt.

Betekenis en Claims
Het artikel beweert een rigoureus kader te bieden voor causale inferentie in online advertentiesystemen waar de "analyse-eenheid" (gebruikerssessie) en de "meet-eenheid" (impressie) op verschillende schalen opereren, en waar de behandeling zelf het volume van de gegenereerde data verandert.

• Het gaat verder dan de "eindige populatie"-aanname van de klassieke causale inferentie door een willekeurige, behandelingsafhankelijke populatie.
• Het biedt een praktische oplossing voor het "interferentie"-probleem in tweezijdige markten door de dynamiek van gebruikers en adverteerders expliciet te modelleren, in plaats van enkel te vertrouwen op randomisatie om interferentie te beheersen.
• Het biedt bruikbare richtlijnen voor de experimentduur door het verband tussen de breedte van het betrouwbaarheidsinterval, de asymptotische varianties en het aantal perioden $k$ te leggen.

De auteurs erkennen beperkingen, zoals het feit dat het model stationaire strategieën veronderstelt en geen niet-stationaire dynamiek (bijv. nieuwe adverteerders die het systeem betreden) expliciet behandelt. Ze suggereren ook dat hoewel het budgetsplitsingsontwerp effectief is, het mogelijk niet alle willekeurige interferentie-effecten corrigeert die niet door het specifieke Markoviaanse model worden gevangen.