ملخص تقني: الاستكشاف الصرف للوصول إلى سياسة جيدة في التعلم المعزز مع تغذية راجعة من نوع "بانديت" (Bandit Feedback)

1. صياغة المشكلة

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

رسمياً، وبالنظر إلى عملية ماركوف لاتخاذ القرار (MDP) مرحلية ذات خصائص انتقال $P$ وتوزيع أولي $p$ غير معروفين، وفضاء حالات $S$، وفضاء أفعال $A$، وأفق زمني $H$، يتم تزويد الوكيل بعتبة مكافأة $\mu_0$. الهدف هو تصميم خوارزمية $\delta$-Probably Approximately Correct ($\delta$-PAC) تقوم بما يلي:

• الحالة الإيجابية: إذا وُجدت سياسة $\pi$ بحيث تكون مكافأتها الإجمالية المتوقعة $V^\pi_0(s_0) \ge \mu_0$، يجب على الخوارزمية إخراج مثل هذه السياسة باحتمال لا يقل عن $1-\delta$.
• الحالة السلبية: إذا كانت قيمة السياسة المثلى $V^*_0(s_0) < \mu_0$، يجب على الخوارزمية إخراج "لا يوجد" (None) باحتمال لا يقل عن $1-\delta$.

مقياس الأداء هو تعقيد العينات المتوقع (عدد الحلقات المستكشفة المتوقع، ويُرمز له بـ $\tau$) اللازم للوصول إلى قرار صحيح. تستبعد الورقة صراحةً الحالة التي يكون فيها $V^*_0(s_0) = \mu_0$، حيث أثبتت الأعمال السابقة (Degenne and Koolen [2019]) أن أي خوارزمية $\delta$-PAC ستتطلب عينات لانهائية في هذه الحالة الحدية.

2. المنهجية: BEE-GPI

يقترح المؤلفون خوارزمية جديدة تسمى BEE-GPI (التوازن بين الاستكشاف والاستغلال لتحديد السياسة الجيدة). تعمل الخوارزمية عبر مراحل $k=1, 2, \dots$، حيث تتكون كل مرحلة من مرحلة استكشاف تكيفية تليها آلية تفرع اتخاذ القرار.

المكونات الرئيسية:

1. مرحلة الاستكشاف (ES-BPI-UCRL):

   • تستخدم هذه المرحلة أوراكل (Oracle) من نوع Early-Stopping BPI-UCRL. وهي توظف استراتيجية أخذ عينات متفائلة (مشابهة لـ BPI-UCRL) لتقدير نواة الانتقال ودوال القيمة.
   • تقدم هذه المرحلة آلية إيقاف مبكر مبتكرة؛ حيث يتحقق الأوراكل من شرطين في كل خطوة:
     • الشرط (3): يتجاوز الحد الأدنى لثقة القيمة للسياسة المتفائلة الحالية العتبة $\mu_0$ (معدلة بمعامل $C$). إذا تحقق هذا، يتم تحديد سياسة مرشحة.
     • الشرط (4): يكون الحد الأعلى لثقة دالة القيمة المثلى أقل من $\mu_0$. إذا تحقق هذا، تُعلن الحالة كحالة سلبية.
   • إذا لم يتحقق أي من الشرطين ولم يتم تجاوز ميزانية الاستكشاف $T^{ee}_k$، تستمر الخوارمة في أخذ العينات.

2. تفرع القرار:

   • إذا أعاد الأوراكل نتيجة "لم يكتمل" (Not Completed)، تنتقل الخوارزمية إلى المرحلة التالية مع تحمل خطأ $\delta_k$ أكثر صرامة وميزانية أكبر.
   • إذا أعاد الأوراكل نتيجة "لا يوجد" (None) ولكن الثقة غير كافية ($\delta_k \ge \delta/10$)، تستمر الخوارزمية إلى المرحلة التالية لضمان ضمان $\delta$-PAC.
   • إذا أعاد الأوراكل سياسة مرشحة $\hat{\pi}_k$، تدخل الخوارزمية في مرحلة الاستغلال.

3. الاستغلال والتحقق:

   • في هذه المرحلة، يتم تنفيذ السياسة المرشحة $\hat{\pi}_k$ بشكل متكرر لتقدير قيمتها الحقيقية.
   • تبني الخوارزمية فاصلاً للثقة لمتوسط المكافأة التجريبي. إذا تجاوز الحد الأدنى لثقة المكافأة العتبة $\mu_0$ ضمن ميزانية عينات محددة، تُخرج السياسة كحل.
   • إذا استنفدت الميزانية دون التحقق، تعود الخوارزمية إلى مرحلة الاستكشاف في التكرار التالي.

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

تقدم الورقة ثلاث مساهمات نظرية رئيسية:

1. صياغة GPI: عرّف المؤلفون رسمياً مشكلة تحديد السياسة الجيدة في إطار الثقة الثابتة، متميزين عن $\epsilon$-BPI. ويوضحون أن اختزالات $\epsilon$-BPI القياسية هي دون المستوى الأمثل لـ GPI لأن الفجوة $V^*_0(s_0) - \mu_0$ غير معروفة مسبقاً، مما يجعل اختيار $\epsilon$ أمراً صعباً.
2. تصميم الخوارزمية والحدود العليا: يقترحون BEE-GPI ويستنتجون حدوداً نظرية لتعقيد العينات الخاص بها لكل من الحالات الإيجابية والسلبية.
   • الحالات الإيجابية: يُحد تعقيد العينات بـ $O\left(\frac{H^2 \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right) + O\left(\frac{\text{poly}(S, A, H)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
   • الحالات السلبية: يتضمن الحد حدوداً مرتبطة بأحجام فضاء الحالة والفعل، وتحديداً $O\left(\frac{(H+1)^4 SA \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
3. الحدود الدنيا والقرب من المثالية: يضع المؤلفون حدوداً دنيا لمشكلة GPI باستخدام "نماذج موحدة" (Uniform Instances) (للحالات الإيجابية) و"نماذج شجرية" (Tree Instances) (للحالات السلبية).
   • يثبتون أنه بالنسبة للحالات الإيجابية، يجب أن تتحمل أي خوارزمية $\delta$-PAC تعقيد عينات قدره $\Omega\left(\frac{H \log(1/\delta)}{(V^*_0 - \mu_0)^2} + \frac{H^2 SA}{(V^*_0 - \mu_0)^2}\right)$.
   • بالنسبة للحالات السلبية، الحد الأدنى هو $\Omega\left(\frac{HSA \log(1/\delta)}{(\mu_0 - V^*_0)^2}\right)$.
   • توضح هذه النتائج أن BEE-GPI قريبة من المثالية، حيث يقتصر الفارق بين الحدود العليا والدنيا على عوامل متعددة الحدود لـ $S, A, H$.

4. النتائج والتحليل

الرؤى النظرية

• فك الارتباط بين الحدود اللوغاريتمية: أحد الاكتشافات الهامة هو أنه بالنسبة لـ الحالات الإيجابية، فإن معامل حد $\log(1/\delta)$ في تعقيد العينات هو $O(H^2)$ وهو مستقل عن حجم فضاء الحالة $S$ وفضاء الفعل $A$. وهذا يتناقض بشدة مع اختزالات BPI القياسية، حيث يتوسع المعامل عادةً بشكل متعدد الحدود مع $S$ و $A$.
• عدم التماثل: هناك عدم تماثل متأصل بين الحالات الإيجابية والسلبية. فبينما تسمح الحالات الإيجابية بتحديد سياسة جيدة بكفاءة دون استكشاف كامل فضاء الحالة-الفعل، تتطلب الحالات السلبية استكشافاً شاملاً لإثبات أنه لا توجد سياسة تحقق العتبة، ومن هنا يأتي الاعتماد على $S$ و $A$ في حد $\log(1/\delta)$.

التجارب العددية

يتحقق المؤلفون من نهجهم باستخدام بيئتين كلاسيكيتين: السلسلة المفردة (Single Chain) و السلسلة المزدوجة (Double Chain) من عمليات ماركوف لاتخاذ القرار (MDPs).

• الإعداد: يقارنون BEE-GPI بخوارزمية BPI-UCRL المتطورة (Kaufmann et al. [2021]). ولضمان مقارنة عادلة، تم تزويد BPI-UCRL بمعامل الأوراكل $\epsilon = V^*_0 - \mu_0$، مما منحها معرفة مسبقة كبيرة.
• النتائج: عبر مختلف العتبات $\mu_0$، تتطلب BEE-GPI باستمرار عدداً أقل بكثير من الحلقات لتحديد سياسة مؤهلة مقارنة بـ BPI-UCRL. وتؤكد النتائج التجريبية الميزة النظرية المتمثلة في فك ارتباط حد $\log(1/\delta)$ بأحجام فضاء الحالة والفعل.

5. الأهمية والادعاءات

تدعي الورقة أن BEE-GPI تقدم حلاً أكثر كفاءة لسيناريوهات التعلم المعزز العملية حيث يكون العثور على السياسة المثلى المطلقة غير ضروري أو صعباً من الناحية الحسابية، ولكن العثور على سياسة "جيدة بما يكفي" (تتجاوز معياراً معيناً) هو أمر بالغ الأهمية.

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

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