Causal Inference on Stopped Random Walks in Online Advertising

技术摘要：在线广告中停止随机游走（Stopped Random Walks）的因果推断

问题陈述
本文探讨了在线广告平台（发布商）中一个特定的因果推断挑战，其目标是估计机制参数（如拍卖底价）的长期处理效应（treatment effect）。与经典设置（如药物试验，其中总体规模固定且独立于处理因素）不同，在线广告涉及一个复杂的、相互关联的系统，由发布商、用户和广告主组成。在这种环境下：

1. 处理因素影响总体规模： 处理因素（例如更高的底价）会改变用户交互轨迹（会话长度）和广告主的竞价行为（受限于有限预算），从而改变在固定时间段内生成的总广告展示机会数量。
2. 干扰与动态性： 测量处理效应的决策会改变正在被测量的系统。用户会话被建模为马尔可夫链，而广告主预算随时间演化，成为另一个依赖于过去拍卖结果的马尔可夫链。
3. 测量尺度不匹配： 目标指标是长期收益（例如 $k$ 天内的收益），但观测的自然单位是单个广告展示（impression）。在固定时间窗口内的展示次数是一个随机变量（停止时间），该变量取决于处理因素。

核心难点在于，假设测量值是独立同分布（i.i.d.）或样本量固定的标准中心极限定理（CLT）方法是不够的。本文将累积收益建模为一个停止随机游走（stopped random walk），其中停止时间（$k$ 天内的总展示次数）是随机的且依赖于处理因素。

方法论

1. 建模框架
作者将发布商、用户和广告主之间的三方交互建模为一个离散时间马尔可夫链。

• 状态空间： 状态包括所有用户访问页面的概况（$X_n$）、所有广告主的剩余预算（$\Omega_n$）以及当前活跃用户的索引（$I_n$）。
• 动态特性： 用户页面跳转和广告主预算更新受平稳策略（底价函数和竞价函数）以及代表用户行为和预算补充的随机变量控制。
• 收益： 发布商的收益是底价和中标出价（第二价格拍卖逻辑）的非线性、可能是不连续的函数。

2. 降维：置换技巧（The Permutation Trick）
当同时对 $d$ 个用户和 $m$ 个广告主进行建模时，状态空间的大小呈指数级增长，这是一个主要障碍。为了解决这个问题，作者引入了一个置换技巧：

• 动机： 基于以下观察：只要用户会话的时间尺度远小于广告活动持续时间，那么交织不同并发用户会话的页面跳转顺序对总销售额和现金流的影响可以忽略不计。
• 机制： 作者定义了一个置换 $\sigma$，通过重新排列展示序列，将属于同一用户会话的所有页面跳转组合在一起。
• 结果： 这将原始的高维马尔可夫链转化为一个近似的、状态空间显著缩小的链（$\mathcal{X} \times \mathbb{R}^m \times [d]$），其中整个用户会话被交织在一起，而非单个页面跳转。这种近似依赖于假设 2.1，即假设广告活动的预算和持续时间相对于单个展示成本和会话长度较大。

3. 实验设计：预算拆分（Budget Splitting）
为了估计处理效应，本文提出了一种预算拆分实验设计（受 [LMK21] 启发）：

• 总体划分： 用户被随机分配到子群体 $A$ 和 $B$，概率分别为 $q$ 和 $1-q$。
• 处理分配： 子群体 $A$ 接收处理 $v$（底价 $v$），子群体 $B$ 接收处理 $w$。
• 预算拆分： 每个广告主的预算按比例（$q$ 和 $1-q$）拆分到两个子群体中。每个群体中的广告主仅在各自分配的马尔可夫链内进行竞争。
• 估计量： 处理效应的估计量 $\hat{\Delta}$ 通过将观测到的各子群体的平均收益和展示次数分别乘以 $1/q$ 和 $1/(1-q)$ 来构建，从而有效地将子群体结果外推至全量总体。

4. 理论保证
作者利用以下工具为长期处理效应 $\Delta$ 的置信区间提供了推导：

• 马尔可夫链 CLT： 应用于置换后的链，以建立收益和的渐近正态性。
• 类 Wald 方程： 用于处理随机停止时间（$k$ 天内的总展示次数）。
• Ansce 理论（Anscombe Theorem）： 用于证明尽管样本量是随机的，停止随机游走仍收敛于正态分布。
• 遍历性假设： 分析假设底层马尔可夫链是 Harris 遍历且几何遍历的，从而确保了不变分布的存在。

核心贡献

1. 建模： 引入了用于因果推断的停止随机游走模型，在该模型中，总体规模（展示次数）是随机的且依赖于处理因素。这推广了通常假设总体固定的经典因果推断。
2. 分析方法： 开发了一种置换技巧，用于降低多用户、多广告主马尔可夫系统中状态空间的维度，在关于时间尺度的温和假设下实现了可处理的分析。
3. 统计推断： 通过结合马尔可夫链 CLT、类 Wald 方程和 Ansce 理论，推导了复杂环境下的长期处理效应置信区间。这为确定必要的实验持续时间提供了理论依据。

结果
本文的主要结果（定理 3.6）表明，在假设策略时间不变、具有遍历性且广告规模足够大的条件下，所提出的估计量 $\hat{\Delta}$ 收敛于真实的处理效应 $\Delta$。具体而言，本文证明了：
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
其中 $\epsilon$ 是取决于子群体链的渐近方差以及子群体与全量总体不变分布之间差异的界限。作者指出，在实际操作中，随着用户规模的扩大，这些分布预计会非常接近，从而使估计量有效。

意义与主张
本文声称为在线广告系统提供了一个严谨的因果推断框架，在这些系统中，“分析单元”（用户会话）与“测量单元”（广告展示）运行在不同的尺度上，且处理因素本身会改变产生的数据量。

• 它超越了经典因果推断中的“有限总体”假设，转向了随机且依赖于处理因素的总体。
• 它通过显式建模用户和广告主的动态过程，为解决双边市场中的“干扰”问题提供了一个实用的解决方案，而不仅仅是依赖于随机化技术来控制干扰。
• 它通过将置信区间宽度与渐近方差及周期数 $k$ 联系起来，为实验持续时间提供了可操作的指导。

作者承认存在局限性，指出该模型假设策略是平稳的，并且没有显式处理非平稳动态（例如新广告主的进入）。他们还指出，虽然预算拆分设计是有效的，但它可能无法纠正未被特定马尔可夫模型所捕获的任意干扰效应。