Causal Inference on Stopped Random Walks in Online Advertising

ملخص تقني: الاستدلال السببي على المسارات العشوائية المتوقفة في الإعلانات عبر الإنترنت

بيان المشكلة
تتناول الورقة تحديًا في الاستدلال السببي خاص بمنصات الإعلانات عبر الإنترنت (الناشرين)، حيث يكون الهدف هو تقدير تأثير المعالجة طويل الأمد لمعايير الآلية، مثل أسعار الاحتياطي في المزادات. وخلافًا للحالات الكلاسيكية (مثل التجارب السريرية للأدوية) حيث يكون حجم المجتمع ثابتًا ومستقلاً عن المعالجة، تتضمن الإعلانات عبر الإنترنت نظامًا معقدًا ومتداخلًا من الناشرين والمستخدمين والمعلنين. في هذه البيئة:

1. المعالجة تؤثر على حجم المجتمع: تؤدي المعالجة (مثل رفع سعر الاحتياطي) إلى تغيير مسارات تفاعل المستخدم (طول الجلسة) وسلوكيات المزايدة للمعلنين (المقيدة بميزانيات محدودة)، مما يغير إجمالي عدد فرص الظهور (impressions) المتولدة خلال فترة زمنية محددة.
2. التداخل والديناميكيات: قرار قياس تأثير المعالجة يغير النظام الذي يتم قياسه. يتم نمذجة جلسات المستخدمين كسلاسل ماركوف، وتتطور ميزانيات المعلنين كسلسلة ماركوف أخرى تعتمد على نتائج المزادات السابقة.
3. عدم تطابق مقياس القياس: المقياس المستهدف هو الإيرادات طويلة الأمد (على سبيل المثال، خلال $k$ من الأيام)، ولكن وحدة الملاحظة الطبيعية هي الإعلان الفردي. عدد الإعلانات في نافذة زمنية ثابتة هو متغير عشوائي (زمن توقف) يعتمد على المعالجة.

تكمن الصعوبة الجوهرية في أن مقاربات "نظرية النهاية المركزية" (CLT) القياسية التي تفترض قياسات مستقلة ومتماثلة التوزيع (i.i.d.) أو أحجام عينات ثابتة هي غير كافية. تنمذج الورقة الإيرادات التراكمية كـ مسار عشوائي متوقف (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. التصميم التجريبي: تقسيم الميزانية
لتقدير تأثير المعالجة، تقترح الورقة تصميم تجريبي يعتمد على تقسيم الميزانية (مستوحى من [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-like Equation): تُستخدم للتعامل مع أزمنة التوقف العشوائية (إجمالي الإعلانات خلال $k$ من الأيام).
• مبرهنة أنسكوم (Ansceomb Theorem): تُستخدم لتبرير تقارب المسار العشوائي المتوقف إلى توزيع طبيعي رغم حجم العينة العشوائي.
• افتراضات الإرغودية (Ergodicity): يفترض التحليل أن سلاسل ماركوف الأساسية هي سلاسل هاريس إرغودية (Harris ergodic) وإرغودية هندسية، مما يضمن وجود التوزيعات الثابتة.

المساهمات الرئيسية

1. النمذجة: تقديم نموذج المسار العشوائي المتوقف للاستدلال السببي حيث يكون حجم المجتمع (عدد الإعلانات) عشوائياً ويعتمد على المعالجة. وهذا يعمم الاستدلال السببي الكلاسيكي الذي يفترض عادةً مجتمعًا ثابتًا.
2. التحليل: تطوير خدعة التبديل لتقليل أبعاد فضاء الحالة في أنظمة ماركوف متعددة المستخدمين والمتعددة المعلنين، مما يسمح بتحليل قابل للتتبع تحت افتراضات زمنية معتدلة.
3. الاستدلال الإحصائي: اشتقاق فواصل الثقة لتأثيرات المعالجة طويلة الأمد في هذا السياق المعقد من خلال الجمع بين نظرية النهاية المركزية لسلاسل ماركوف، ومعادلة شبيهة بمعادلة والد، ومبرهنة أنسكوم. يوفر هذا أساسًا نظريًا لتحديد مدد التجارب الضرورية.

النتائج
تثبت النتيجة الرئيسية (النظرية 3.6) أنه تحت افتراضات الاستراتيجيات الثابتة زمنياً، والإرغودية، ونطاق الحملة، فإن المُقدِّر المقترح $\hat{\Delta}$ يتقارب مع تأثير المعالجة الحقيقي $\Delta$. وتحديدًا، تثبت الورقة أن:
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
حيث $\epsilon$ هو حد يعتمد على التباينات التقاربية لسلاسل المجموعات الفرعية والفرق بين التوزيعات الثابتة للمجموعات الفرعية والمجتمع الكامل. وتشير الورقة إلى أنه في الممارسة العملية، ومع وجود مجموعات كبيرة من المستخدمين، يُتوقع أن تكون هذه التوزيعات متقاربة، مما يجعل المُقدِّر فعالاً.

الأهمية والادعاءات
تدعي الورقة توفير إطار صارم للاستدلال السببي في أنظمة الإعلانات عبر الإنترنت حيث تعمل "وحدة التحليل" (جلسة المستخدم) و"وحدة القياس" (الإعلان) بمقاييس مختلفة، وحيث يمكن للمعالجة نفسها أن تغير حجم البيانات المتولدة.

• إنها تتجاوز افتراض "المجتمع المحدود" للاستدلال السببي الكلاسيكي إلى مجتمع عشوائي يعتمد على المعالجة.
• تقدم حلاً عمليًا لمشكلة "التداخل" في الأسواق ذات الجانبين من خلال نمذجة ديناميكيات المستخدمين والمعلنين صراحةً بدلاً من الاعتماد فقط على تقنيات العشوائية للتحكم في التداخل.
• توفر توجيهات عملية لمدد التجارب من خلال ربط عرض فاصل الثقة بالتباينات التقاربية وعدد الفترات $k$.

يقر المؤلفون بوجود قيود، مشيرين إلى أن النموذج يفترض استراتيجيات ثابتة ولا يتعامل صراحة مع الديناميكيات غير الثابتة (مثل دخول معلنين جدد إلى النظام). كما يقترحون أنه بينما يعد تصميم تقسيم الميزانية فعالًا، إلا أنه قد لا يصحح آثار التداخل التعسفي التي لا تغطيها النموذج الماركوفي المحدد.