Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards

إليك ملخص تقني مفصل للورقة البحثية بعنوان "المتعدد الأذرع مع مكافآت بديلة مولدة بواسطة تعلم الآلة" (Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards).

1. بيان المشكلة

تتناول الورقة مشكلة المتعدد الأذرع (Multi-Armed Bandit - MAB)، وهي إطار لاتخاذ القرارات المتسلسلة في ظل عدم اليقين، حيث يجب على الوكيل الموازنة بين الاستكشاف (تجربة إجراءات جديدة) والاستغلال (اختيار أفضل إجراء معروف) لتقليل الندم التراكمي (cumulative regret).

التحدي الجوهري:
تعتمد خوارزميات MAB التقليدية حصرياً على البيانات المتصلة (online data) التي يتم جمعها أثناء عملية اتخاذ القرار. ومع ذلك، في العديد من السيناريوهات الواقعية (مثل التجارب السريرية، وأنظمة التوصية)، تتوفر بيانات تاريخية/خارجية (offline/historical data) غنية (متغيرات، سمات مستخدمين) قبل بدء المرحلة المتصلة.

• الفرصة: يمكن تدريب نماذج تعلم الآلة (ML) على هذه البيانات الخارجية للتنبؤ بالنتائج، مما يولد مكافآت بديلة (surrogate rewards).
• الصعوبة: غالباً ما تكون هذه البدائل المولدة بواسطة تعلم الآلة منحازة (biased). فقد تتنبأ بأن دواءً جديداً فعال بينما هو ليس كذلك، أو العكس، لأنها تعتمد غالباً على الاستقراء (extrapolation) لبيئات غير مرئية.
• الفجوة: تفترض الطرق الحالية إما أن البيانات الخارجية غير منحازة (وهو أمر نادر الحدوث) أو تتطلب معرفة بحد الانحياز. هناك نقص في الخوارزميات التي يمكنها الاستفادة من المكافآت البديلة المرتبطة ولكن المنحازة لتقليل الندم دون معرفة مسبقة بمقدار الانحياز أو هيكل التباين (covariance structure).

2. المنهجية: MLA-UCB

يقترح المؤلفون خوارزمية الحد الأعلى للثقة بمساعدة تعلم الآلة (Machine Learning-Assisted Upper Confidence Bound - MLA-UCB). الابتكار الأساسي يكمكمن في دمج تقنيات الاستدلال المدعوم بالتنبؤ (Prediction-Powered Inference - PPI) في إطار عمل UCB لإزالة انحياز تقدير متوسط المكافأة.

أ. المُقدِّر (The Estimator)

بدلاً من استخدام المتوسط العيني للمكافآت الحقيقية، تقوم MLA-UCB ببناء مُقدِّر متوسط مدعوم بتعلم الآلة ($\hat{\mu}^{MLA}$) لكل ذراع $k$:
$$\hat{\mu}^{MLA}_{k,n} = \bar{R}_{k,n} - \hat{\lambda}_{k,n} (\bar{\hat{R}}_{k,n} - \bar{\hat{R}}^{off}_{k})$$
حيث أن:

• $\bar{R}_{k,n}$: المتوسط العيني للمكافآت الحقيقية (متصل/online).
• $\bar{\hat{R}}_{k,n}$: المتوسط العيني للمكافآت البديلة (متصل/online).
• $\bar{\hat{R}}^{off}_{k}$: المتوسط العيني للمكافآت البديلة (خارجي/offline).
• $\hat{\lambda}_{k,n}$: وزن مستمد من البيانات (plug-in estimate) ناتج عن التباين العيني بين المكافآت الحقيقية والبديلة.

يعامل هذا المُقدِّر المتوسط البديل الخارجي كـ "متغير تحكم" (control variate). فهو يطرح الانحياز الملاحظ في بيانات المكافآت البديلة المتصلة بالنسبة للمكافآت البديلة الخارجية، مما يصحح تقدير المكافأة الحقيقية.

ب. حدود الثقة (Confidence Bounds)

لضمان الضمانات النظرية، يستنتج المؤلفون حداً أعلى للثقة (UCB) صارماً لـ $\hat{\mu}^{MLA}_{k,n}$.

• التحليل التوزيعي: تحت افتراض التوزيع الطبيعي ثنائي المتغير (للمكافآت الحقيقية والبديلة)، يثبتون أن خطأ التقدير يمكن تفكيكه إلى مكونين مستقلين: أحدهما يتعلق بعدم اليقين في المتوسط البديل الخارجي والآخر يتعلق بـ "بواقي الانحدار" (regression residual).
• تقليل التباين: يتناسب حد الثقة مع تباين البواقي، والذي يتم تقليله بعامل $(1 - \rho_k^2)$، حيث $\rho_k$ هو معامل الارتباط بين المكافآت الحقيقية والبديلة.
• لا معرفة مسبقة: من المهم ملاحظة أن الخوارزمية لا تتطلب معرفة مسبقة بتباين المكافآت الحقيقية، أو تباين البدائل، أو مصفوفة التباين المشترك. فهي تقدر هذه القيم عبر الإنترنت باستخدام الإحصاءات العينية.

ج. التوسع إلى الحالات غير الطبيعية (Non-Gaussian) وحالات الدفعات (Batched)

توسع الورقة الطريقة لتشمل:

1. المكافآت بنظام الدفعات (Batched Rewards): حيث تُطبق القرارات على دفعة من $m$ من المستخدمين في وقت واحد.
2. التوزيعات غير الطبيعية (Non-Gaussian): باستخدام حدود الانحراف المتوسط ذاتية التنميط (Cramér-type inequalities) لبناء فترات ثقة صالحة حتى عندما لا تكون المكافآت طبيعية، بشرطاء أن يكون حجم الدفعة كبيراً بما يكفي لإحداث تقارب نحو التوزيع الطبيعي.

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

1. إطار عمل جديد لـ MAB: صياغة إطار عمل لـ MAB مع مكافآت بديلة مولدة بتعلم الآلة منحازة بشكل عشوائي ولكنها مرتبطة. هذا يخفف من الافتراض غير الواقعي بأن البيانات الخارجية يجب أن تكون غير منحازة أو أن الانحياز محكوم بثابت معروف.
2. خوارزمية MLA-UCB: تقترح خوارمة:
   • تعمل مع أي نموذج تنبؤ بالمكافآت (نماذج خطية، شبكات عصبية، إلخ).
   • لا تتطلب معرفة مسبقة بالانحياز أو هيكل التباين المشترك.
   • تحقق الأمثلية التقاربية (asymptotic optimality).
3. الضمانات النظرية:
   • الحد الأعلى للندم: تثبت أن الندم التراكمي أقل بشكل صارخ من خوارزمية UCB الكلاسيكية عندما يكون $\rho_k \neq 0$. حيث يتم تقليل الحد الرئيسي للندم بعامل يتناسب مع $(1 - \rho_k^2)$.
   • الحد الأدنى للندم: تستنتج حداً أدنى مطابقاً، مما يثبت أن MLA-UCB هي أمثل سياسة من الناحية المعلوماتية.
   • المتانة: توضح أنه حتى لو كان المتوسط البديل غير متوافق تماماً مع المتوسط الحقيقي (انحياز عالٍ)، فإن الخوارزمية لا تزال تحسن الأداء طالما وجد ارتباط غير صفري.
4. نظرية الدفعات وغير الطبيعية: توسع النظرية لتشمل سيناريوهات الدفعات مع مكافآت غير طبيعية، وتوفر حدود ثقة قابلة للحساب باستخدام الإحصاءات ذاتية التنميط.

4. النتائج

النتائج النظرية

• الحالة الطبيعية (Gaussian Case): إذا كان حجم العينة الخارجي $N_k$ هو متعدد لوغاريتمي في الأفق $T$ (أي $N_k = \Omega((\log T)^{4/3})$)، فإن الندم المتوقع يُحد بـ:
  $$E[Reg_T] \leq \sum_{k \neq k^*} \frac{2\Delta_k \log T}{\log\left(1 + \frac{\Delta_k^2}{\sigma_k^2(1-\rho_k^2)}\right)}$$
  هذا يوضح أن التباين الفعال قد تم تقليله من $\sigma_k^2$ إلى $\sigma_k^2(1-\rho_k^2)$.
• الأمثلية: تحقق الخوارزمية الحد الأدني للندم من الناحية المعلوماتية لهذا الإعداد.

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

تحقق المؤلفون من صحة الطريقة من خلال محاكاة واسعة ودراسات حالة واقعية:

1. بيانات Gaussian اصطناعية: تفوقت MLA-UCB بشكل كبير على UCB الكلاسيكية. كان تقليل الندم خطياً في $\rho_k^2$ ووصل إلى حالة التشبع مع زيادة حجم العينة الخارجية.
2. بدائل غير طبيعية مولدة بتعلم الآلة: باستخدام نماذج متنوعة (الانحدار الخطي، SVR، الشبكات العصبية، أشجار القرار) لتوليد بدائل لدالة مكافأة غير خطية، قللت MLA-UCB باستمرار من الندم مقارنة بـ UCB، حتى عند انتهاك افتراض التوزيع الطبيعي.
3. دراسات حالة واقعية:
   • اختيار النماذج اللغوية الكبيرة (LLM Selection): استُخدمت نماذج مفتوحة المصدر (مثل Llama) كبدائل لاختيار أفضل نموذج ملكي (مثل GPT-4o أو Claude). قللت MLA-UCB من الندم مقارنة بطرق الاختيار القياسية.
   • توصية الفيديو: استُخدم نموذج تعزيز التدرج (Gradient Boosting) مُدرب على تفاعلات المستخدم والمنتج التاريخية لتوليد بدائل لتوصيات فيديوهات جديدة. حسنت MLA-UCB من تفاعل المستخدمين (نسبة المشاهدة) وقللت الندم.

5. الأهمية

تجسّر هذه الورقة الفجوة بين تعلم الآلة الخارجي (Offline ML) واتخاذ القرار المتسلسل المتصل (Online Sequential Decision-Making).

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

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