Causal Inference on Stopped Random Walks in Online Advertising

Resumen Técnico: Inferencia Causal en Caminatas Aleatorias Detenidas en Publicidad en Línea

Planteamiento del Problema
El artículo aborda un desafío de inferencia causal específico para las plataformas de publicidad en línea (editores) donde el objetivo es estimar el efecto de tratamiento a largo plazo de los parámetros del mecanismo, tales como los precios de reserva de las subastas. A diferencia de los entornos clásicos (por ejemplo, ensayos clínicos) donde el tamaño de la población es fijo e independiente del tratamiento, la publicidad en línea involucra un sistema complejo e interconectado de editores, usuarios y anunciantes. En este entorno:

1. El tratamiento afecta el tamaño de la población: Un tratamiento (por ejemplo, un precio de reserva más alto) altera las trayectorias de interacción de los usuarios (longitud de la sesión) y los comportos de puja de los anunciantes (limitados por presupuestos finitos), cambiando así el número total de oportunidades de impresión generadas durante un período de tiempo fijo.
2. Interferencia y Dinámicas: La decisión de medir los efectos del tratamiento altera el sistema que se está midiendo. Las sesiones de usuario se modelan como cadenas de Markov, y los presupuestos de los anunciantes evolucionan como otra cadena de Markov dependiente de los resultados de las subastas pasadas.
3. Desajuste de Escala de Medición: La métrica objetivo es el ingreso a largo plazo (por ejemplo, sobre $k$ días), pero la unidad natural de observación es la impresión publicitaria individual. El número de impresiones en una ventana de tiempo fija es una variable aleatoria (un tiempo de parada) dependiente del tratamiento.

La dificultad central es que los enfoques estándar del Teorema del Límite Central (TLC) que asumen mediciones independientes e idénticamente distribuidas (i.i.d.) o tamaños de muestra fijos son insuficientes. El artículo modela el ingreso acumulado como una caminata aleatoria detenida, donde el tiempo de parada (el total de impresiones en $k$ días) es aleatorio y dependiente del tratamiento.

Metodología

1. Marco de Modelado
Los autores modelan la interacción trilateral entre el editor, los usuarios y los anunciantes como una cadena de Markov de tiempo discreto.

• Espacio de Estados: El estado incluye el perfil de las páginas visitadas por todos los usuarios ($X_n$), los presupuestos restantes de todos los anunciantes ($\Omega_n$) y el índice del usuario activo ($I_n$).
• Dinámicas: Las transiciones de página de los usuarios y las actualizaciones de presupuesto de los anunciantes se rigen por estrategias estacionarias (funciones de precio de reserva y funciones de puja) y variables aleatorias que representan el comportamiento del usuario y la reposición de presupuestos.
• Ingresos: El ingreso del editor es una función no lineal y potencialmente discontinua del precio de reserva y la puja ganadora (lógica de subasta de segundo precio).

2. Reducción de Dimensionalidad: El Truco de la Permutación
Un obstáculo importante es el tamaño exponencial del espacio de estados al modelar simultáneamente $d$ usuarios y $m$ anunciantes. Para abordar esto, los autores introducen un truco de permutación:

• Motivación: Basándose en la observación de que el orden de intercalación de las transiciones de página de diferentes sesiones de usuario concurrentes tiene un efecto insignificante en las ventas agregadas y el flujo de caja, siempre que las escalas de tiempo de las sesiones de usuario sean mucho menores que las duraciones de las campañas de los anunciantes.
• Mecanismo: Los autores definen una permutación $\sigma$ que reordena la secuencia de impresiones para agrupar todas las transiciones de página pertenecientes a la misma sesión de usuario.
• Resultado: Esto transforma la cadena de Markov original de alta dimensión en una cadena aproximada con un espacio de estados significativamente menor ($\mathcal{X} \times \mathbb{R}^m \times [d]$), donde sesiones de usuario completas se intercalan en lugar de transiciones de página individuales. Esta aproximación se basa en el Supuesto 2.1, que postula que los presupuestos y las duraciones de las campañas publicitarias son grandes en relación con los costos de las impresiones individuales y las longitudes de las sesiones.

3. Diseño Experimental: División de Presupuesto
Para estimar el efecto del tratamiento, el artículo propone un diseño experimental de división de presupuesto (inspirado en [LMK21]):

• División de la Población: Los usuarios se asignan aleatoriamente a subpoblaciones $A$ y $B$ con probabilidades $q$ y $1-q$.
• Asignación de Tratamiento: La subpoblación $A$ recibe el tratamiento $v$ (precio de reserva $v$) y la $B$ recibe el tratamiento $w$.
• División de Presupuesto: El presupuesto de cada anunciante se divide proporcionalmente ($q$ y $1-q$) entre las dos subpoblaciones. Los anunciantes en cada grupo compiten únicamente dentro de su cadena de Markov de subpoblación asignada.
• Estimador: El estimador $\hat{\Delta}$ para el efecto total del tratamiento se construye escalando el ingreso promedio observado y los conteos de impresiones de las subpoblaciones por $1/q$ y $1/(1-q)$ respectivamente, extrapolando efectivamente los resultados de la subpoblación a la población completa.

4. Garantías Teóricas
El artículo deriva un intervalo de confianza para el efecto del tratamiento a largo plazo $\Delta$ utilizando:

• TLC de Cadenas de Markov: Aplicado a las cadenas permutadas para establecer la normalidad asintótica de las sumas de ingresos.
• Ecuación de tipo Wald: Utilizada para manejar los tiempos de parada aleatorios (total de impresiones durante $k$ días).
• Teorema de Anscombe: Empleado para justificar la convergencia de la caminata aleatoria detenida hacia una distribución normal a pesar del tamaño de muestra aleatorio.
• Supuestos de Ergodicidad: El análisis asume que las cadenas de Markov subyacentes son Harris ergódicas y geométricamente ergódicas, asegurando la existencia de distribuciones invariantes.

Contribuciones Clave

1. Modelado: Introducción de un modelo de caminata aleatoria detenida para la inferencia causal donde el tamaño de la población (número de impresiones) es aleatorio y dependiente del tratamiento. Esto generaliza la inferencia causal clásica, que típicamente asume una población fija.
2. Analítica: Desarrollo de un truco de permutación para reducir la dimensionalidad del espacio de estados en sistemas de Markov de múltiples usuarios y múltiples anunciantes, permitiendo un análisis tratable bajo supuestos moderados respecto a las escalas de tiempo.
3. Inferencia Estadística: Derivación de intervalos de confianza para efectos de tratamiento a largo plazo en este entorno complejo mediante la combinación de un TLC de Markov, una ecuación de tipo Wald y el Teorema de Anscombe. Esto proporciona una base teórica para determinar la duración necesaria de los experimentos.

Resultados
El resultado principal (Teorema 3.6) establece que, bajo supuestos de estrategias invariantes en el tiempo, ergodicidad y escala de campaña, el estimador propuesto $\hat{\Delta}$ converge al verdadero efecto del tratamiento $\Delta$. Específicamente, el artículo demuestra que:
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
donde $\epsilon$ es un límite dependiente de las varianzas asintóticas de las cadenas de las subpoblaciones y la diferencia entre las distribuciones invariantes de la subpoblación y la población completa. El artículo señala que, en la práctica, con poblaciones de usuarios grandes, se espera que estas distribuciones sean cercanas, lo que hace que el estimador sea efectivo.

Significancia y Reclamaciones
El artículo afirma proporcionar un marco riguroso para la inferencia causal en sistemas de publicidad en línea donde la "unidad de análisis" (la sesión de usuario) y la "unidad de medición" (la impresión) operan en diferentes escalas, y donde el tratamiento mismo altera el volumen de datos generados.

• Va más allá del supuesto de "población finita" de la inferencia causal clásica para proponer una población aleatoria y dependiente del tratamiento.
• Ofrece una solución práctica al problema de la "interferencia" en mercados de dos caras mediante el modelado explícito de las dinámicas de usuarios y anunciantes, en lugar de depender únicamente de técnicas de aleatorización para controlar la interferencia.
• Proporciona una guía accionable sobre la duración de los experimentos al vincular el ancho del intervalo de confianza con las varianzas asintóticas y el número de períodos $k$.

Los autores reconocen limitaciones, señalando que el modelo asume estrategias estacionarias y no maneja explícitamente dinámicas no estacionarias (por ejemplo, la entrada de nuevos anunciantes al sistema). También sugieren que, si bien el diseño de división de presupuesto es efectivo, puede no corregir efectos de interferencia arbitrarios no capturados por el modelo de Markov específico.