Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

ملخص تقني: اتباع القائد المضطرب (Follow-the-Perturbed-Leader) للنماذج متعددة الأذرع المنفصلة

إعداد المشكلة
تتناول هذه الورقة مشكلة النماذج متعددة الأذرع (MAB) المنفصلة، وهو إطار عمل يختار فيه المتعلم ذراعين متميزين في كل جولة $t$: ذراع $i_t$ لغرض الاستغلال (تحمل الخسارة $\ell_{t, i_t}$ دون ملاحظتها) وذراع $j_t$ لغرض الاستكشاف (ملاحظة الخسارة $\ell_{t, j_t}$ دون تحملها). ينمذج هذا الإطار سيناريوهات مثل أنظمة الاتصالات ذات النطاق فائق العرض (استشعار قناة تختلف عن قناة الإرسال) ونقل التعلم من المحاكاة إلى الواقع (sim-to-real) في الروبوتات. الهدف هو تقليل الندم الزائف (pseudo-regret)، المعرّف بالفرق بين الخسارة التراكمية لخيارات الاستغلال للمتعلم وخسارة أفضل ذراع ثابت في الماضي.

تستهدف الورقة ضمانات "الأفضل من كلا العالمين" (BOBW)، بهدف تحقيق:

1. ندم أمثل قدره $O(\sqrt{KT})$ في النظام التنافسي (حيث يتم تحديد الخسائر بواسطة خصم متكيف).
2. ندم قريب من الأمثل، وغير مرتبط بالزمن قدره $O(K/\Delta_{\min})$ في نظام التنافس المقيد عشوائياً (SCA) (والذي يتضمن الإعداد العشوائي القياسي)، حيث $\Delta_{\min}$ هو الحد الأدنى لفجوة عدم المثالية.

المنهجية
يقترح المؤلفون سياسة جديدة تعتمد على إطار عمل "اتباع القائد المضطرب" (FTPL)، مصممة خصيصاً للتغلب على الاختناقات الحسابية للسياسات الحالية لـ BOBW في الإعدادات المنفصلة.

• استراتيجية الاستغلال: يختار المتعلم ذراع الاستغلال $i_t$ عن طريق تقليل تقدير الخسارة التراكمية المضطربة:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  حيث $\hat{L}_{t,i}$ هو الخسارة التراكمية المقدرة، و$\eta_t$ هو معدل التعلم، و$r_{t,i}$ هي اضطرابات عشوائية مستقلة وموزعة بشكل متماثل (i.i.d.) مأخوذة من توزيع باريتو $P_\alpha$ بمعلم شكل $\alpha > 1$. هذا النوع من الاضطراب يتوافق مع سياسة $\beta$-Tsallis-INF (مع $\alpha = 1/(1-\beta)$)، المعروفة بتحقيق ضمانات BOBW.

• استراتيجية الاستكشاف (الابتكار الرئيسي): في خوارزميات FTPL التقليدية، يتطلب بناء مُقدّر خسارة غير منحاز يعتمد على الوزن (IW) معرفة الاحتمال الدقيق $w_{t,i}$ لاختيار الذراع $i$. في النماذج المنفصلة، يجب ضبط احتمال الاستكشاف $p_{t,i}$ بناءً على $w_{t,i}$. ومع ذلك، فإن FTPL لا يوفر تعبيراً مغلق الصيغة لـ $w_{t,i}$ (على عكس FTRL)، كما أن تقدير المتجه الكامل عبر إعادة أخذ العينات الهندسي مكلف حسابياً ($O(K^2)$ أو أعلى).
  لحل هذه المشكلة، يقدم المؤلفون احتمالاً بديلاً $q_{t,i}$ يمكن حسابه مباشرة من تقديرات الخسارة الحالية دون الحاجة لإعادة أخذ العينات أو التحسين المحدب:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  حيث $\sigma_{t,i}$ هو رتبة $\hat{L}_{t,i}$ بين جميع الأذرع. يتم بعد ذلك اختيار ذراع الاستكشاف $j_t$ وفقاً للتوزيع الطبيعي $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$. يتجنب هذا النهج الحاجة إلى قيم $w_{t,i}$ الصريحة مع الحفاظ على الخصائص النظرية المطلوبة لضمانات BOBW.

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

1. أول سياسة قائمة على FTPL لتحقيق BOBW في النماذج المنفصلة: تقدم الورقة أول سياسة تحقق ضمانات BOBW في النماذج المنفصلة دون الحاجة لحل مسائل التحسين المحدب (المطلوبة في نهج FTRL مثل Decoupled-Tsallis-INF) أو استخدام إجراءات إعادة أخذ العينات (المطلوبة عادةً لتقدير احتمالات FTPL).
2. الكفاءة الحسابية: من خلال استبدال حساب متجه الاحتمال الكامل بـ الاحتمال البديل $q_{t,i}$ القابل للحساب بكفاءة، تقلل السياسة المقترحة من التعقيد الحسابي لكل خطوة. وبينما يستغرق فرز تقديرات الخسارة $O(K \log K)$، يشير المؤلفون إلى أن التنفيذ الأمثل يمكن أن يحقق تحديثات بقوة $O(K)$ عبر تتبع تغيرات الرتب بشكل تدريجي. وهذا يتناقض مع سياسات FTRL التي تتطلب تحسيناً محدباً تكرارياً (مثل طريقة نيوتن) في كل خطوة.
3. الضمانات النظرية:
   • النظام التنافسي: تحقق السياسة حد ندم قدره $O(\sqrt{KT})$، وهو ما يطابق الحد الأدنى المعروف للنماذج المنفصلة.
   • النظام العشوائي/SCA: تحقق السياسة حداً للندم قدره $O(K/\Delta_{\min})$ (تحديداً $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$ لـ $\alpha=3$)، وهو قريب من الأمثل ويحسن الحدود المرتبطة بالزمن في النماذج العشوائية القياسية.

النتائج

• نظرياً: تقدم الورقة براهين صارمة (عبر تفكيك الندم إلى حدود الاستقرار والعقوبة) توضح أن الاحتمال البديل $q_{t,i}$ قريب بما يكفي من احتمال الاستغلال الحقيقي للحفاظ على حدود الندم اللازمة.
• تجريبياً: تُظهر التجارب على البيانات الاصطناعية (في كل من الأنظمة التنافسية والعشوائية) ومحاكاة واقعية باستخدام مجموعة بيانات MovieLens 100K أن سياسة FTPL المقترحة:
  • تحقق ندماً تراكمياً أقل مقارنة بسياسات BOBW الحالية (Decoupled-Tsallis-INF/FTRL و EXP3).
  • تُظهر كفاءة حسابية فائقة. في النظام التنافسي، تعمل السياسة المقترحة بسرعة أكبر بكثير من النماذج المرجعية القائمة على FTRL. بالنسبة لـ $K=64$، لوحظ أن نسبة وقت التشغيل لـ FTRL إلى FTPL كانت أبطأ بحوالي 1363 مرة.
  • تتوسع بفعالية مع عدد الأذرع $K$، وتحافظ على المتانة عبر أحجام الفجوات $\Delta$ المختلفة.

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