Active Context Selection Improves Simple Regret in Contextual Bandits

ملخص تقني: الاختيار النشط للسياق يحسن الندم البسيط في المخططات السياقية (Contextual Bandits)

صياغة المشكلة
تتقصى هذه الورقة مشكلة المخطط السياقي متعدد الأذرع (contextual multi-armed bandit) ضمن فضاء سياق محدود، حيث تمثل السياقات مجموعات سكانية فرعية متميزة (مثل الفئات الديموغرافية). يتم تعريف هدف التعلم من خلال الندم البسيط الموزون سياقياً: بعد ميزانية تجريبية ثابتة $T$، يجب على المتعلم التوصية بأفضل علاج واحد لكل مجموعة سكانية فرعية. مقياس الأداء هو الفجوة المتوقعة بين العلاج الأمثل والعلاجات الموصى بها، والموزونة بمتجه توزيع السكان $p$ عبر $k$ من المجموعات السكانية الفرعية.

تميز الدراسة بين نظامي أخذ عينات:

1. أخذ العينات السلبي (Passive Sampling): يتم الكشف عن السياقات عشوائياً وفقاً للتوزيع الثابت $p$، ويقوم المتعلم فقط باختيار العلاج.
2. أخذ العينات النشط (Active Sampling): يمكن للمتعلم اختيار كل من المجموعة السكانية الفرعية (السياق) والعلاج لكل جولة بشكل نشط.

يفترض التحليل إعداداً في أسوأ الحالات فيما يتعلق بتوزيعات المكافأة، لكنه يظل معتمداً على الحالة فيما يتعلق بتوزيع السياق $p$. تركز الورقة على نظام "الغنى بالبيانات" حيث يكون الأفق $T$ أكبر بكثير من عدد العلاجات $n$، والسياقات $k$، ومعكوس الحد الأدنى لاحتمالية السياق.

المنهجية والإطار النظري

• التخصي-ص التوزيع الأمثل لتوزيع $p$ المعروف:
  عندما يكون توزيع المجموعات السكانية الفرعية $p$ معروفاً، يقوم المؤلفون بتوصيف التخصيص الأمثل للميزانية التجريبية. يثبتون أنه بالنسبة لمعيار الندم البسيط في أسوأ الحالات، فإن السياسات الخالية من التاريخ (حيث يعتمد اختيار السياق فقط على $p$ وليس على التاريخ المرصود) كافية لتحقيق معدل الـ minimax.

  • المعدل السلبي: تحت أخذ العينات السلبي، يتناسب الندم مع $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$.
  • المعدل النشط: تحت أخذ العينات النشط، تخصص الاستراتيجية المثلى العينات للمجموعة السكانية الفرعية $j$ باحتمالية تتناسب مع $p_j^{2/3}$. وهذا يحقق معدل ندم قدره $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3})$.
  • الفجوة: يتم توصيف عامل التحسن من أخذ العينات السلبي إلى النشط من خلال النسبة $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$. يظهر المؤلفون أنه بالنسبة للتوزيعات غير المنتظمة للغاية، يمكن أن تصل هذه الفجوة إلى $\Theta(k^{1/4})$. يعمل التخصيص النشط الأمثل على تحويل احتمالات أخذ العينات نحو توزيع أكثر انتظاماً مقارنة بـ $p$، مما يزيد من الاستكشاف في المجموعات السكانية الفرعية الأصغر.

• التدخلات المقيدة بالميزانية:
  توسع الورقة التحليل ليشمل الحالات التي يكون فيها أخذ العينات النشط مكلفاً، مما يسمح للمتعلم باختيار المجموعة السكانية الفرعية في نسبة $\alpha$ فقط من الجولات. يصيغ المؤلفون مشكلة تحسين مقيدة لتقليل الندم مع مراعاة القيد الذي يقضي بأن التخصيص $q$ يجب أن يحقق $q_j \geq (1-\alpha)p_j$. ويستنتجون بنية عتبة للتخصيص الأمثل: المجموعات السكانية ذات $p_j$ الكبيرة قد تظل عند تخصيصها السلبي إذا كانت الميزانية غير كافية لتحسينها، بينما يتم تعزيز المجموعات الأخرى نحو نسبة $p_j^{2/3}$. كما يحددون الحد الأدنى للميزانية $\alpha_{\min}(p)$ المطلوب لاستعادة معدل التخصيص النشط الكامل الأمثل.

• توزيع $p$ غير المعروف (خوارزمية EETC):
  عندما يكون $p$ غير معروف، لا يمكن لسياسة نشطة بالكامل أن تتبنى ببساطة قاعدة $p^{2/3}$. يقترح المؤلفون خوارزمية الاستكشاف-الاستكشاف-ثم-الالتزام (EETC)، والتي توازن بين ثلاث مراحل:

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

النتائج الرئيسية والتجارب

• الضمانات النظرية: تثبت الورقة معدلات ندم دقيقة لكل من $p$ المعروف وغير المعروف. وتثبت أن اختيار السياق النشط يحسن الأداء دائماً مقارنة بأخذ العينات السلبية، وأن حجم التحسن يعتمد على عدم تجانس توزيع السياق.
• التجارب الاصطناعية: تؤكد التجارب على البيانات الاصطناعية أن الفجوة في الندم بين السياسات السلبية والنشطة تتسع مع زيادة عدد المجموعات السكانية الفرعية $k$، وهو ما يتماشى مع حد $\Theta(k^{1/4})$ النظري. كما أظهرت خوارزمية EETC أنها تقترب من أداء سياسة "الأوراكل" (التي تعرف $p$).
• بيانات العالم الحقيقي (MovieLens): قيم المؤلفون أساليبهم باستخدام مجموعة بيانات MovieLens 1M، حيث تم التعامل مع توصيات الأفلام كعلاجات والمجموعات الديموغرافية كمجموعات سكانية فرعية. تشير النتائج إلى أن السياسات السلبية تسجل أعلى ندم. وتتفوق كل من السياسة النشطة ذات $p$ المعروف وخوارزمية EETC بشكل كبير على الخط المرجعي السلبي، حيث تقترب E_ETC من أداء سياسة الأوراكل النشطة مع زيادة الأفق.

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

يؤكد المؤلفون أن عملهم يسد الفجوة بين المخططات السياقية القياسية (حيث السياقات بيئية) والتصميم التجريبي (حيث يتحكم المجرب في العينة). ومن خلال توصيف قاعدة التخصيص المثلى ($q_j \propto p_j^{2/3}$) وتوفير خوارزمية (EETC) تتكيف مع التوزيعات غير المعروفة دون التضحية بالأمثلية التقاربية، تقدم الورقة إطاراً صارماً لتخصيص الموارد بكفاءة. ويشير العمل إلى أنه في السيناريوهات التي يكون فيها التجنيد المستهدف أو أخذ العينات المتحكم فيه ممكناً، فإن تجاهل القدرة على اختيار السياقات يؤدي إلى توصيات علاجية دون المستوى الأمثل.