ملخص تقني: بحث مونت كارلو الشجري الإبستيمي (Epistemic Monte Carlo Tree Search)

بيان المشكلة

حققت عائلة خوارزميات ألفا زيرو/موزيرو (A/MZ) نجاحاً كبيراً من خلال دمج بحث مونت كارلو الشجري (MCTS) مع نماذج متعلمة للقيمة وديناميكيات البيئة. ومع ذلك، يوجد قصور جوهري: فبينما تُدخل النماذج المتعلمة الشك الإبستيمي (Epistemic Uncertainty) (الشك الناجم عن محدودية تغطية بيانات التدريب)، فإن خوارزمية MCTS القياسية لا تأخذ في الاعتبار انتشار هذا الشك أثناء عملية البحث. وبناءً على ذلك، لا تستطيع خوارزميات A/MZ استغلال MCTS بفعالية لتحقيق الاستكشاف العميق (Deep Exploration). يتطلب الاستكشاف العميق من الوكيل توجيه نفسه نحو الانتقالات الجديدة بغض النظر عن مسافتها من الحالة الحالية، وهي قدرة أساسية لمهام مثل تصميم الخوارزميات أو البرمجة حيث تكون المكافآت شحيحة والمساحة الحالة شاسعة. وبدون مراعاة الشك الإبستيمي، قد يتقارب البحث نحو سياسات دون المستوى بناءً على تنبؤات نموذج غير دقيقة، مما يؤدي إلى الفشل في استكشاف المناطق الضرورية من مساحة الحالة.

المنهجية: بحث مونت كارلو الشجري الإبستيمي (EMCTS)

يقترح المؤلفون بحث مونت كارلو الشجري الإبستيمي (EMCTS)، وهو إطار عمل مدفوع نظرياً يدمج الشك الإبستيمي في عملية MCTS لتسهيل الاستكشاف العميق. تتضمن المنهجية ثلاثة مكونات رئيسية:

1. صياغة البحث مع الشك

يصيغ المؤلفون نموذج البيئة المتعلم $\hat{M}$ كمتغير عشوائي. ويستنتجون حداً علوياً للثقة (UCB) لدالة القيمة المثلى $Q^*$ بناءً على تباين تنبؤات القيمة داخل النموذج المتعلم.

• الأساس النظري: يثبت المبرهنة 1 أن القيمة المثلى الحقيقية $Q^*(s, a)$ محصورة بين القيمة المتوقعة القصوى في النموذج مضافاً إليها حد يتناسب مع الانحراف المعياري لتلك القيمة، مكيّفاً بمعامل ثقة $\delta$.
• سياسة البحث: يتم تعديل سياسة الاختيار القياسية PUCT (Predictor Upper Confidence Bound) لتصبح Epistemic P/UCT (EP/UCT). يصبح معيار الاختيار هو:
  $$a = \arg\max_{a} \left( q_{\hat{M}}(s, a) + \beta \sqrt{V[q_{\hat{M}}(s, a)]} + \text{Exploration Term} \right)$$
  هنا، تمثل $q_{\hat{M}}$ القيمة المقدرة، وتمثل $\sqrt{V[q_{\hat{M}}]}$ الشك الإبستيمي. يتحكم المعامل الفائق $\beta$ في المقايضة بين الاستغلال والاستكشاف.

2. نشر الشك الإبستيمي

المساهمة الجوهرية هي آلية لنشر الشك عبر شجرة البحث، وليس فقط عبر القيمة.

• الشك في عمليات النسخ الاحتياطي (Backups): يتم حساب شك خطوة النسخ الاحتياطي $\nu$ عن طريق جمع تباينات المكافأة الفورية والتباين المستقبلي للقيمة المخصومة.
• شك قيمة العقدة: بما أن A/MZ يستخدم نفس النموذج طوال عملية التخطيط، فإن عوائد النسخ الاحتياطي تكون مترابطة. ولتجنب افتراض الاستقلالية، يقترح المؤلفون حداً علوياً لتباين قيمة العقدة $V[q_{\hat{M}}(s, a)]$ باستخدام مجموع الانحرافات المعيارية لعمليات النسخ الاحتياطي الفردية:
  $$V[q_{\hat{M}}(s, a)] \leq \left( \frac{1}{N(s, a)} \sum_{i=1}^{N(s, a)} \sqrt{V[\nu_i(s, a)]} \right)^2$$
• المقدرات: تستخدم الطريقة مقدرات الشك الموجودة للمكافآت (مثل تقطير الشبكة العشوائية RND أو العد القائم على الهاش) وللقيم (مثل معادلة بيلمان للشك UBE). بالنسبة للانتقالات غير المرصودة، يتم تعيين التباين إلى أقصى تباين ممكن لمتغير عشوائي محدود.

3. التعامل مع نماذج الانتقال المتعلمة

بينما يفترض الاشتقاق النظري نموذج انتقال معروف، يعالج المؤلفون تحديات ديناميكيات الانتقال المتعلمة (كما في MuZero). يقترحون تقريباً "متفائلاً إلى أقصى حد" حيث، عند مواجهة أول انتقال غير مؤكد في مسار ما، يُفترض أن جميع التنبؤات اللاحقة في ذلك المسار تمتلك أقصى درجات الشك. يضمن ذلك أن يظل UCB حداً علوياً صالحاً لأغراض الاستكشاف.

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

1. بحث مونت كارلو الشجري الإبستيمي (EMCTS): خوارزمية مبتكرة توسع نطاق MCTS لتقدير ونشر الشك الإبستيمي من نماذج القيمة و/أو المكافأة المتعلمة، مما يمكن عملية البحث من السعي بنشاط نحو المناطق غير المؤكدة.
2. إطار عمل نظري: اشتقاق لسياسات بحث قائمة على UCB (وهي EP/UCT) مستندة نظرياً إلى تباين النماذج المتعلمة، مما يوفر آلية رسمية للاستكشاف العميق.
3. التنفيذ: تنفيذ موازٍ باستخدام JAX لـ EMCTS مقترناً بوكيل AlphaZero، تم تطبيقه على بيئة لغة التجميع subleq ومعيار Deep Sea.

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

يقيم المؤلفون EMCTS في مجالين يتسمان بشح المكافآت:

1. مهمة البرمجة بلغة Subleq

• المهمة: كتابة كود بلغة التجميع subleq لحل وظائف محددة (Negate Positives و Identity Function). يتضمن هذا البحث في مساحة حالة تبلغ حوالي $16^{10}$ حالة.
• النتائج: تفوق EMCTS المقترن بـ AlphaZero (E-AZ) بشكل كبير على AlphaZero الأساسي. حل E-AZ المهمة الأصعب "Identity Function" بعدد أقل بكثير من العينات مقارنة بالنموذج الأساسي. أظهرت الطريقة أن استخدام مقدر شك مناسب (مثل IO hash مقابل full state hash) يحسن كفاءة العينات بشكل أكبر.

2. معيار Deep Sea

• المهمة: بيئة عالم شبكي (grid-world) حيث يجب على الوكيل إيجاد مسار مثالي فريد ذي مكافآت شحيحة. احتمالية العثัง على الحل عبر الاستكشاف العشوائي تتضاءل أسياً مع حجم الشبكة.
• النتائج:
  • الاستكشاف العميق: فشلت وكلاء A/MZ الأساسيون في حل متغيرات Deep Sea (سواء كانت ذات مكافآت حتمية أو عشوائية) ضمن ميزانيات تدريب معقولة. في المقابل، نجح وكلاء EMCTS (E-AZ و E-MZ) في حل هذه المهام، مما أظهر نمواً تحت-أسياً في تعقيد العينات مع حجم البيئة.
  • فائدة البحث: تفوق EMCTS بشكل كبير على نسخة Ablation (وهي A/MZ+UBE) التي استخدمت الشك لاختيار الإجراء ولكن لم تستخدم البحث لتقدير هذا الشك. وهذا يؤكد أن البحث نفسه يحسن جودة تقدير الشك، مما يؤدي إلى استكشاف أكثر كفاءة.
  • المتانة: ظلت الطريقة فعالة حتى عند استخدام ديناميكيات الانتقال المتعلمة الخاصة بـ MuZero (التجريد المكافئ للقيمة) وفي وجود مكافآت عشوائية.

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

يزعم الورقة أن EMCTS يعالج فجوة أساسية في التعلم المعزز القائم على النماذج: عدم قدرة MCTS القياسية على استخدام الشك الإبستيمي للاستكشاف. من خلال دمج نشر الشك في شجرة البحث، تمكن EMCTS وكلاء A/MZ من:

• تحقيق كفاءة أعلى بكثير في العينات في البيئات ذات المكافآت الشحيحة.
• حل معايير الاستكشاف الصعبة (مثل Deep Sea) التي يستحيل حلها عملياً بواسطة خوارزميات A/MZ الأساسية.
• تحسين الموثوقية المحتمل في التعلم المعزز خارج السياسة (offline RL) وتوليد الأهداف خارج السياسة (off-policy target generation) من خلال توفير تقديرات أفضل للشك في تنبؤات القيمة.

يضع المؤلفون EMCTS كتحسين عملي ومدفوع نظرياً لعائلة A/MZ، مما يجعل هذه الخوارزميات مجهزة بشكل أفضل للتطبيقات الواقعية التي تتضمن تصميم الخوارزميات والمكافآت الشحيحة، حيث يكون الاستكشاف العميق أمراً حاسماً.