Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

ملخص تقني: الاستكشاف الصرف لما وراء التغذية الراجعة للمكافأة: دور سياق ما بعد الإجراء

صياغة المشكلة
تقدم هذه الورقة نوعاً جديداً من مشكلة "تحديد أفضل ذراع" (Best Arm Identification - BAI) ضمن إطار "الثقة الثابتة" في المسائل العشوائية لمتعدد الأذرع (multi-armed bandits - MAB). في هذا الإطار، والذي يُسمى "تحديد أفضل ذراع مع سياق ما بعد الإجراء"، يختار المتعلم إجراءً (ذراعاً) $X$ ويلاحظ ليس فقط المكافأة $Y$ بل أيضاً سياقاً وسيطاً لما بعد الإجراء $Z$. يتم توليد السياق $Z$ كنتيجة للإجراء المختار، مما يميز هذه المشكلة عن المسائل السياقية القياسية حيث يسبق السياقُ الإجراءَ.

يحلل المؤلفون نظامين هيكليين محددين بالعلاقة السببية بين الإجراء، والسياق، والمكافأة:

1. السياق الفاصل (Separator Context): تعتمد المكافأة $Y$ حصرياً على السياق $Z$، مما يجعل $X$ و $Y$ مستقلين شرطياً بوجود $Z$ ($P(Y|X, Z) = P(Y|Z)$). في هذه الحالة، يتم تحديد توزيع المكافأة بالكامل من خلال السياق الملحوظ.
2. السياق غير الفاصل (Non-Separator Context): تعتمد المكافأة $Y$ على كل من الإجراء $X$ والسياق $Z$ ($P(Y|X, Z) \neq P(Y|Z)$). هنا، يوفر السياق معلومات إضافية ولكنه ليس إحصاءً كافياً للمكافأة.

الهدف هو تحديد الذراع ذات أعلى مكافأة متوقعة باحتمالية خطأ لا تتجاوز $\delta$، مع تقليل تعقيد العينات (عدد الجولات المطلوبة).

المنهجية والخوارزميات
تستنتج الورقة حدوداً دنيا لتعقيد العينات تعتمد على الحالة لكلا الإعدادين، وتقترح خوارمايات تحقق هذه الحدود تقاربياً.

• إعداد السياق الفاصل:

  • الحد الأدنى (Lower Bound): يستنتج المؤلفون حداً أدنى يعتمد على ترددات السياقات الملحوظة بدلاً من ترددات الأذرع المسحوبة. وذلك لأنه في إعداد السياق الفاصل، فإن أي ملاحظة لسياق معين $Z=j$ توفر معلومات حول متوسط مكافأة ذلك السياق، بغض النظر عن الذراع التي ولّدته.
  • الخوارزمية (STS): تستخدم خوارزمية "التتبع والتوقف الفاصل" (Separator Track and Stop - STS) المقترحة قاعدة أخذ عينات مبتكرة تسمى G-tracking. على عكس الطرق التقليدية التي تتبع ترددات سحب الذراع المثلى، تقوم G-tracking بتتبع الترددات المثلى لملاحظة السياقات. وهي تتعامل مع المشكلة كمهمة تعلم نشطة خارج السياسة (off-policy learning) حيث يختار المتعلم توزيعاً على الأذرع لتحقيق توزيع مستهدف للسياقات. تحل الخوارزمية مسألة تحسين محدب لإيجاد ترددات السياق المثلى، وتستخدم إسقاطاً هندسياً لاختيار توزيع الذراع التالي، مما يضمن تقارب ترددات السياق الملحوظة إلى التردد المستهدف الأمثل.

• إعداد السياق غير الفاصل:

  • الحد الأدنى (Lower Bound): يأخذ الحد الأدنى المستنتج في الاعتبار التوزيع المشترك للأفعال والسياقات.
  • الخوارزمية (NSTS): تعمل خوارزمية "التتبع والتوقف غير الفاصل" (Non-Separator Track and Stop - NSTS) على توسيع إطار العمل الكلاسيكي "التتبع والتوقف". وهي تستخدم D-tracking لتقدير وتتبع النسب المثلى لسحب أذرع معينة، مستفيدة من المعلومات المشتركة للأفعال وسياقاتها الناتجة لتنقية تقديرات متوسط المكافأة.

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

1. تعريف المشكلة: صياغة رسمية لـ "تحديد أفضل ذراع مع سياق ما بعد الإجراء"، مع التمييز بين الأنظمة الهيكلية الفاصلة وغير الفاصلة.
2. الحدود النظرية: استنتاج حدود دنيا لتعقيد العينات تعتمد على الحالة لكلا النظامين. وقد ثبت أن حد السياق الفاصل أضيق (tighter) من الحدود المستمدة من تجاهل السياق.
3. تصميم الخوارزميات:
   • تقديم G-tracking، وهي قاعدة أخذ عينات تعمل مباشرة على تحسين ترددات ملاحظة السياق في إعداد السياق الفاصل، مستفلة من هندسة فضاء السياق.
   • توسيع إطار عمل Track-and-Stop في إعداد السياق غير الفاصل (NSTS).
4. تحليل دون المثالية (Sub-optimality): عرض نظري وتجريبي يثبت أن الخوارزميات التي تتجاهل سياق ما بعد الإجراء (مثل Track-and-Stop القياسي) هي دون مثالية بشكل صارخ. في إعداد السياق الفاصل، يمكن أن يؤدي تجاهل السياق إلى زيادة هائلة في تعقيد العينات، حتى عندما تكون فجوات المكافأة صغيرة، لأنه يفشل في استغلال بنية الاستقلال الشرطي.
5. تحليل الاختزال (Reduction Analysis): تحلل الورقة اختزال مشكلة السياق الفاصل إلى المسائل الخطية (linear bandits)، وتظهر أن هذه الاختزالات تزيد من الحد الأدنى لتعقيد العينات مقارنة بالنهج المباشر المقترح.

النتائج

• نظرياً: ثبت أن الخوارزميات المقترحة (STS و NSTS) صحيحة بمقدار $\delta$ وتحقق المثالية التقاربية، مطابقة للحدود الدنيا المستنتجة مع اقتراب $\delta \to 0$.
• تجريبياً: تُظهر التجارب على البيانات الاصطناعية والبيانات الواقعية (سجلات توصية KuaiSAR) مكاسب كبيرة في الأداء.
  • في إعداد السياق الفاصل، تتفوق STS بشكل كبير على النماذج المرجعية (Track-and-Stop و Lazy Track-and-Stop)، والتي غالباً ما تفشل في التوقف ضمن آفاق زمنية معقولة.
  • في إعداد السياق غير الفاصل، تقلل NSTS بشكل كبير من عدد العينات المطلوبة مقارنة بـ Track-and-Stop الذي يتجاهل معلومات السياق.
  • تؤكد مخططات التتبع أن STS تتقارب نحو ترددات السياق المثلى، بينما تفشل النماذج المرجعية في التوافق مع الاستراتيجية المثلى.

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