Causal Inference on Stopped Random Walks in Online Advertising

技術要約：オンライン広告における停止ランダムウォーク上の因果推論

問題提起
本論文は、オンライン広告プラットフォーム（パブリッシャー）に特有の因果推論の課題に取り組んでいる。その目的は、メカニズムのパラメータ（例：オークションの予約価格）の長期的な処置効果を推定することである。薬物試験のような古典的な設定（例：集団のサイズが処置に依存せず固定されている場合）とは異なり、オンライン広告は、パブリッシャー、ユーザー、広告主が相互に連結した複雑なシステムを伴う。この環境では以下の現象が発生する：

1. 処置が集団のサイズに影響を与える： 処置（例：高い予約価格）は、ユーザーのインタラクションの軌跡（セッションの長さ）や、広告主の入札行動（有限の予算による制約を受ける）を変化させ、それによって固定された期間内に生成される総インプレッション機会の数を変化させる。
2. 干渉とダイナミクス： 処置効果を測定するという決定自体が、測定対象となっているシステムそのものを変化させる。ユーザーセッションはマルコフ連鎖としてモデル化され、広告主の予算は過去のオークション結果に依存する別のマルコフ連鎖として進化する。
3. 測定スケールの不一致： ターゲットとなる指標は長期的な収益（例：$k$ 日間）であるが、自然な観測単位は個々の広告インプレッションである。固定された時間窓内におけるインプレッションの数は、処置に依存する確率変数（停止時間）である。

核心となる困難は、独立同一分布（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]に着想を得たもの）を提案している。

• 集団の分割： ユーザーは、確率 $q$ と $1-q$ でサブ集団 $A$ および $B$ にランダムに割り当てられる。
• 処置の割り当て： サブ集団 $A$ は処置 $v$（予約価格 $v$）を受け取り、$B$ は処置 $w$ を受ける。
• 予算の分割： 各広告主の予算は、二つのサブ集団間で比例的（$q$ と $1-q$）に分割される。各グループの広告主は、自身に割り当てられたサブ集団のマルコフ連鎖内でのみ競合する。
• 推定量： 総処置効果に対する推定量 $\hat{\Delta}$ は、サブ集団から観測された平均収益およびインプレッション数をそれぞれ $1/q$ および $1/(1-q)$ でスケーリングすることにより、サブ集団の結果を全集団へと外挿することで構築される。

4. 理論的保証
論文では、以下の手法を用いて、長期的な処置効果 $\Delta$ の信頼区間を導出している。

• マルコフ連鎖のCLT： 置換された連鎖に適用し、収益和の漸近正規性を確立する。
• ワルド型の方程式（Wald-like Equation）： ランダムな停止時間（$k$ 日間の総インプレッション数）を扱うために使用される。
• アンスコムの定理（Anscone Theorem）： ランダムなサンプルサイズにもかかわらず、停止ランダムウォークが正規分布に収束することを正当化するために採用される。
• エルゴード性の仮定： 分析は、基礎となるマルコフ連鎖がハリス・エルゴード的（Harris ergodic）かつ幾何学的エルゴード的であることを前提としており、これにより不変分布の存在が保証される。

主要な貢献

1. モデリング： 集団のサイズ（インプレッション数）がランダムであり、かつ処置に依存する状況における、因果推論のための停止ランダムウォークモデルの導入。これは、通常、集団が固定されていることを想定する古典的な因果推論を一般化するものである。
2. 分析的側面： ユーザーセッションと広告主キャンペーンの時間スケールに関する緩やかな仮定の下で、解析を可能にするために、多ユーザー・多広告主のマルコフ・システムにおける状態空間の次元を削減する置換トリックの開発。
3. 統計的推論： マルコフCLT、ワルド型の方程式、およびアンスコムの定理を組み合わせることで、この複雑な設定における長期的な処置効果の信頼区間を導出すること。これにより、実験期間を決定するための理論的根拠が提供される。

結果
主な結果（定理 3.6）は、定常的な戦略、エルゴード性、およびキャンペーンの規模という仮定の下で、提案された推定量 $\hat{\Delta}$ が真の処置効果 $\Delta$ に収束することを確立している。具体的には、以下を示す：
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
ここで、$\epsilon$ は漸近分散およびサブ集団と全集団の不変分布の差に依存する境界である。著者らは、実務においては、ユーザー集団が大規模であればこれらの分布は互いに近くなると予想され、推定量が有効に機能すると述べている。

意義と主張
本論文は、分析単位（ユーザーセッション）と測定単位（インプレッション）が異なるスケールで動作し、処置自体が生成されるデータの量を変えてしまうオンライン広告システムにおける、厳密な因果推論の枠組みを提供すると主張している。

• これは、古典的な因果推論の「有限集団」の仮定を超え、ランダムで処置依存的な集団へと移行するものである。
• 干渉を制御するために単にラン randomization 手法に頼るのではなく、ユーザーと広告主のダイナミクスを明示的にモデル化することで、二部市場における「干渉」の問題に対する実用的な解決策を提示している。
• 信頼区間の幅を漸近分散および期間数 $k$ に結びつけることで、実行可能な実験期間のガイダンスを提供している。

著者らは、モデルが定常的な戦略を想定しており、非定常なダイナミクス（例：新規広告主の参入）を明示的に扱っていないことを認め、また、予算分割デザインは有効であるものの、特定のマルコフモデルによって捉えられない任意の干渉効果を修正できるわけではない可能性についても示唆している。