Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment

إليك ملخص تقني مفصل لورقة البحث "Causal Bandit Over Unknown Graphs: Upper Confidence Bounds with Backdoor Adjustment" من تأليف Zhao و Zhou.

1. صياغة المشكلة

تتناول الورقة مشكلة المنظم السببي (Causal Bandit - CB)، وهي مهمة اتخاذ قرار متسلسل حيث يختار الوكيل تدخلات (أذرع) لتعظيم المكافأة المتوقعة في نظام سببي.

• التحدي: على عكس خوارزميات المجموعات متعددة الأذرع القياسية (MAB) حيث تكون الأذرع صناديق سوداء مستقلة، تعمل المنظمات السببية ضمن رسم بياني موجه غير حلقي (DAG) حيث ترتبط المتغيرات سببياً؛ فالتدخل في متغير واحد يؤثر على المتغيرات الأخرى.
• الفجوة: تفترض طرق الـ CB الحالية عادةً أن بنية الرسم البياني السببي معلومة أو تفرض افتراضات هيكلية مقيدة. وفي الواقع، غالباً ما يكون الرسم البياني (DAG) الأساسي مجهولاً.
• الإعداد المحدد: يركز المؤلفون على نماذج DAG الغاوسية (نماذج المعادلات الهيكلية الخطية) حيث تكون المكافأة دالة خطية للمتغيرات. الهدف هو تحديد التدخل الذري $do(X_i = x_i)$ الذي يعظم المكافأة المتوقعة $E[Y | do(X_i = x_i)]$ دون معرفة مسبقة بالرسم البياني.
• مصادر البيانات: يستفيد هذا الإعداد من مصدرين للبيانات:
  1. البيانات التجريبية: يتم جمعها بشكل متسلسل أثناء عملية المنظم (مكلفة، ومحدودة).
  2. البيانات الرصدية: بيانات تاريخية تم جمعها دون تدخلات (وفيرة، ومنخفضة التكلفة).

2. المنهجية: خوارزمية BA-UCB

يقترح المؤلفون خوارزمية الحد الأعلى للثقة مع تعديل الباب الخلفي (Backdoor-Adjustment Upper Confidence Bound - BA-UCB). الابتكار الجوهري يكمن في دمج البيانات الرصدية لتقدير التأثيرات السببية عبر تعديل الباب الخلفي (backdoor adjustment)، حتى عندما يكون الرسم البياني مجهولاً.

المكونات الرئيسية:

1. تحديد تعديل الباب الخلفي:

   • بدلاً من استعادة الرسم البياني (DAG) كاملاً (وهو أمر صعب حاسوبياً وغالباً ما يكون مستحيلاً بسبب التكافؤ الماركوفي)، تحدد الخوارزمية مجموعات مرشحة لتعديل الباب الخلفي ($S$) لكل ذراع تدخل $X_i$.
   • الآلية: بالنسبة لمجموعة مرشحة $S$، تقارن الخوارزمية بين تقدير التأثير السببي المستمد من البيانات الرصدية (باستخدام الانحدار $Y \sim X_i + X_S$) وبين التقدير المستمد من البيانات التجريبية (التدخل المباشر على $X_i$).
   • معيار الاختيار: تُعتبر المجموعة $S$ مجموعة مرشحة صالحة إذا كان فاصل الثقة للفرق بين التقدير الرصدي والتقدير التجريبي يحتوي على الصفر. هذا النهج القائم على البيانات يستبعد مجموعات التعديل غير الصالحة دون الحاجة إلى الرسم البياني الحقيقي.

2. التقدير الموزون:

   • بمجرد تحديد مجموعة مرشحة $S$، تبني الخوارزمية مقدراً متوسطاً موزوناً للمكافأة المتوقعة $\mu_i$.
   • تقوم بدمج التقدير الرصدي ($\hat{\mu}_{i,obs}$) والتقدير التجريبي ($\hat{\mu}_{i,int}$) بناءً على أحجام العينات والتباين الخاص بكل منهما.
   • المتانة: تجادل الورقة ضد نهج "الانحدار الواحد" (تجميع كل البيانات في انحدار واحد) لأنه قد يكون منحازاً إذا كانت مجموعة التعديل المختارة غير صالحة. نهج المتوسط الموزون أكثر متانة تجاه الخطأ في التوصيف.

3. قاعدة القرار (UCB):

   • تختار الخوارزمية الذراع $A_{t+1}$ الذي يعظم الحد الأعلى للثقة:
     $$\hat{\mu}_i(t, S) + \hat{\sigma}_i(t, S) \cdot c \sqrt{\log t}$$
   • حيث يتم اشتقاق $\hat{\mu}_i$ و $\hat{\sigma}_i$ من الجمع الموزون بين البيانات الرصدية والتجريبية.

4. التعامل مع المربكات الكامنة (Latent Confounders):

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

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

• افتراض الرسم البياني المجهول: أول طريقة تحل مشاكل المنظمات السببية مع رسوم بيانية مجهولة دون افتراض أن الرسم البياني مقدم أو تقييد مساحة العمل لتكون هي الآباء (parents) للمكافأة.
• تكامل البيانات: إطار عمل مبتكر لدمج البيانات الرصدية الوفيرة ومنخفضة التكلفة بسلاسة مع البيانات التجريبية المكلفة لتقليل الندم (regret).
• الضمانات النظرية:
  • حدود الندم: وضع حدود عليا للندم التراكمي في زمن محدد.
  • الاعتماد على $K$: في غياب المربكات الكامنة، يكون حد الندم هو $O(\sqrt{T \log T / (m+n)})$، وهو ما لا يعتمد على عدد الأذرع $K$ (بافتراض وجود بيانات رصدية كافية). وهذا يمثل تحسناً كبيراً عن حدود MAB القياسية التي تبلغ $O(\sqrt{KT \log T})$.
  • المربكات الكامنة: تظهر الحدود الموسعة أن الندم يعتمد على $K_1$ (عدد الأذرع التي ليس لها مجموعة تعديل صالحة) بدلاً من $K$ الإجمالي.
• الكفاءة الحسابية: على عكس النهج البايزي (Bayesian) التي تتطلب تحديث الاحتمالات اللاحقة لجميع الهياكل البيانية الممكنة (تعقيد أسي)، تستخدم BA-UCB تقدير الجوار القائم على الانحدار، مما يجعلها قابلة للتوسع في الرسوم البيانية الأكبر.

4. النتائج

أجرى المؤلفون عمليات محاكاة واسعة النطاق لمقارنة BA-UCB مع:

• Standard UCB: يستخدم البيانات التجريبية فقط.
• CN-UCB (المركز العصبي): يحاول تحديد آباء المكافأة أولاً (يفشل إذا لم يكن الذراع الأمثل هو أحد الآباء).
• BBB-UCB (الباب الخلفي البايزي): منهج بايزي يصعب تنفيذه حسابياً للرسوم البيانية الأكبر.

النتائج الرئيسية:

• الأداء: تحقق BA-UCB ندماً تراكمياً أقل بكثير من Standard UCB و CN-UCB.
• القابلية للتوسع: تتميز BA-UCB بكفاءة حسابية وتتوسع بشكل جيد مع عدد العقد ($p$)، بينما يصبح BBB-UCB غير قابل للتنفيذ عندما $p \ge 20$.
• المتانة: عندما لا يكون التدخل الأمثل هو أحد آباء المكافأة (حالة فشل شائعة لـ CN-UCB)، تحافظ BA-UCB على أداء عالٍ.
• التقارب: تظهر المحاكاة أن الخوارزمية تنجح في تحديد مجموعات التعديل الصالحة بمرور الوقت، وأن المقدر المدمج يتقارب مع التأثير السببي الحقيقي.

5. الأهمية

يسد هذا العمل الفجوة بين الاستدلال السببي واتخاذ القرار المتسلسل في بيئات واقعية حيث:

1. الرسوم البيانية مجهولة: يزيل الافتراض غير الواقعي بضرورة معرفة الهياكل السببية.
2. البيانات غير متجانسة: يستفيد بفعالية من البيانات الرصدية "المجانية" لتسريع التعلم، مما يقلل الحاجة إلى التجارب المكلفة.
3. القابلية للتوسع أمر بالغ الأهمية: يوفر بديلاً قابلاً للتنفيذ حسابياً للمناهج البايزية لمشاكل المنظمات السببية عالية الأبعاد.

تمثل خوارزمية BA-UCB المقترحة نهجاً متطوراً للمنظمات السببية، حيث تقدم ضمانات نظرية قوية وكفاءة عملية، خاصة في السيناريوهات ذات مساحات العمل الكبيرة والبيانات التاريخية الرصدية المتاحة.