Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

ملخص تقني: المندليات السياقية للموارد المحدودة باستخدام التعلم الاحتمالي

بيان المشكلة
تعد المندليات السياقية (Contextual Bandits - CB) أساسية لاتخاذ القرار المتسلسل عبر الإنترنت في الخدمات التكيفية مثل التوصيات الشخصية والحوسبة الطرفية. ومع ذلك، فإن نشر وكلاء المندليات السياقية مباشرة على الأجهزة ذات الموارد المحدودة (مثل الهواتف المحمولة، والأجهزة القابلة للارتداء، والأجهزة الجوية) يفرض تحديات كبيرة. تتطلب خوارزميات المندليات السياقية الخطية القياسية، رغم فعاليتها، صيانة مصفوفات التباين التي تتوسع تربيعياً مع أبعاد السياق ($O(Nd^2)$ من حيث الذاكرة) وتتضمن عمليات جبر خطي مكلفة حاسوبياً ($O(d^3)$ من حيث التعقيد)، مما يجعلها غير مناسبة للأجهزة ذات قيود الذاكرة، والحوسبة، والطاقة الصارمة.

قدمت الأعمال الحديثة "المندليات السياقية فائقة الأبعاد" (Hyperdimensional Contextual Bandits - HD-CB)، والتي تستفيد من الحوسبة فائقة الأبعاد (HDC) لحل مشكلات المندليات السياقية في فضاءات عالية الأبعاد باستخدام عمليات متجهة خفيفة الوزن. وبينما توفر HD-CB تعقيداً زمنياً خطياً وتحسناً في القابلية للتوسع، فإن تنفيذها القياسي يعتمد على التحديثات القائمة على التراكم، حيث تنمو مكونات المتجه بشكل غير محدود. وهذا يستليزم استخدام أنواع رقمية عالية الدقة (مثل الأرقام العشرية 32 بت) لمنع تجاوز السعة (overflow)، مما يلغي مكاسب كفاءة الذاكرة. وقد عالج متغير سابق منخفض الدقة، وهو HD-CBBIN، مشكلة تجاوز السعة عن طريق ثنائية (binarization) المتجهات بشكل دوري وإعادة ضبط العدادات؛ ومع ذلك، فإن عملية الثنائية الحتمية هذه تتجاهل معلومات المقدار المتراكمة، مما يؤدي إلى تدهور الأداء، لا سيما في الأنظمة ذات الضجيج العالي أو ندرة البيانات.

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

1. مكونات صحيحة محدودة: بدلاً من السماح لمكونات المتجه بالنمو بلا حدود، تقوم HD-CBPROB بتقييد كل مكون ضمن نطاق عدد صحيح محدد مسبقاً $[-\kappa, +\kappa]$. وهذا يسمح باستخدام عدادات صحيحة منخفضة الدقة وذات تشبع (مثل 2، 3، أو 4 بت).
2. قاعدة التحديث الاحتمالية: لتمكين التعلم ضمن هذه الحدود الضيقة دون فقدان المعلومات، تستبدل الخوارزمية التحديث القائم على المقدار بتحديث قائم على التردد. في كل خطوة زمنية $t$، يتم تحديث مجموعة فرعية عشوائية فقط من مكونات المتجه بناءً على احتمال يتلاشى زمنياً $\alpha_t$.
   • يُعرف احتمال التحديث بـ $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$.
   • لكل مكون $i$، يتم أخذ قيمة عشوائية $m_{t,i} \sim U(0, 1)$. يحدث التحديث فقط إذا كان $m_{t,i} \leq \alpha_t$.
   • عندما يحدث التحديث، يتم زيادة أو إنقاص المكون بمقدار $\pm 1$ (بناءً على ربط المتجهات السياقية ومتجهات المكافأة) ثم يتم قصّه (clipping) ضمن النطاق $[-\kappa, +\kappa]$.
3. الآلية: ينفذ هذا النهج فعلياً "سير عشوائي مشبع" (saturating random walk). ومن خلال التحكم في تردد التحديثات بدلاً من مقدار القيم المخزنة، يحتفظ الوكيل بالمعلومات التاريخية بدقة عالية حتى في المكونات منخفضة الدقة. وهذا يلغي الحاجة إلى عدادات مساعدة وخطوات الثنائية الدورية المطلوبة في HD-CBBIN.

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

• الابتكار الخوارزمي: تقديم قاعدة تحديث احتمالية لـ HD-CB تتيح استخدام مكونات صحيحة مشبعة ومنخفضة الدقة دون فقدان المعلومات الدوري.
• كفاءة الموارد: تقلل هذه الطريقة من بصمة الذاكرة عن طريق إلغاء الحاجة إلى العدادات المساعدة والنسخ الثنائية المنفصلة من المتجهات المطلوبة في المتغيرات السابقة منخفضة الدقة. كما أنها تقلل التكلفة الحسابية لأن العدد المتوقع للتحديثات يتناقص بمرور الوقت بسبب الاحتمال المتلاشي $\alpha_t$.
• الحفاظ على الأداء: تحافظ هذه الطريقة على جودة ترتيب الإجراءات من خلال الحفاظ على معلومات المقدار عبر تردد التحديث، متجنبة التدهور المرتبط بالثنائية القاسية.

النتائج التجريبية
قام المؤلفون بتقييم HD-CBPROB باستخدام التقييم خارج السياسة (off-policy evaluation) على معايير اصطناعية قياسية للمندليات السياقية عبر "خط أنابيب البنديت المفتوح" (Open Bandit Pipeline - OBP)، مقارنة بكل من:

1. LinEPS: المندليات السياقية الخطية القياسية (الأساس).
2. HD-CBREAL: HD-CB ذات القيم الحقيقية.
3. HD-CBBIN: HD-CB الثنائية مع إعادة الضبط الدورية.
4. HD-CBPROB: المتغير الاحتمالي المقترح.

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

• التفوق على المتغيرات الثنائية: تفوقت HD-CBPROB باستمرار على HD-CBBIN عند مستويات الدقة المتساوية في جميع التكوينات المختبرة (تنوع أبعاد السياق $d$ وعدد الإجراءات $N$). وتحديداً، حقق تنفيذ HD-CBPROB بـ 3 بت تحسناً في المكافآت التراكمية بنسبة 5.8% تقريباً مقارنة بتنفيذ HD-CBBIN بـ 3 بت.
• الاقتراب من أداء القيم الحقيقية: حقق تكوين HD-CBPROB بـ 3 بت (مع عتبة تشبع $\kappa=3$) أداءً يقترب من خط الأساس HD-CBREAL ذي القيم الحقيقية، بفارق متوسط قدره 2.5% فقط.
• تناقص العوائد على الدقة: أظهرت زيادة الدقة من 3 إلى 4 بت عوائد متناقصة أو سلبية قليلاً لـ HD-CBPROB، مما يشير إلى أن 3 بت كافية لالتقاط جودة الإجراء في هذه البيئات الاصطناعية.
• كفاءة الذاكرة: تتطلب HD-CBPROB ذاكرة أقل بصرامة من HD-CBBIN عند نفس عرض البت، لأنها لا تتطلب آليات مساعدة (عدادات ونسخ مؤقتة ثنائية المتجهات). وعلى عكس المندليات السياقية الخطية، تظل بصمة ذاكرتها ثابتة بالنسبة لأبعاد السياق.

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

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