💻 computer science

Twice Sequential Monte Carlo for Tree Search

تقدم الورقة البحثية خوارزمية "البحث في شجرة مونت كارلو المتسلسلة المزدوجة" (TSMCTS)، وهي خوارزمية مبتكرة تعزز قابلية التوسع والاستقرار لـ "مونت كارلو المتسلسلة" في التعلم التعزيزي القائم على النموذج من خلال التخفيف بفعالية من مشكلات تدهور المسار والتباين، مع الحفاظ على مزاياها في التوازي وتسريع وحدة معالجة الرسومات.

المؤلفون الأصليون: Yaniv Oren, Joery A. de Vries, Pascal R. van der Vaart, Matthijs T. J. Spaan, Wendelin Böhmer

نُشر 2026-05-22

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Yaniv Oren, Joery A. de Vries, Pascal R. van der Vaart, Matthijs T. J. Spaan, Wendelin Böhmer

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

تقدم هذه الورقة البحثية طريقة جديدة وأكثر ذكاءً للقيام بعملية "النظر مسبقاً" هذه. يطلق المؤلفون على هذه الطريقة اسم البحث في شجرة مونت كارلو لـ مونت كارلو التسلسلي المزدوج (TSMCTS).

إليك تفصيل للمشكلة التي حلتها والحل الذي قدمته، باستخدام تشبيهات بسيطة.

المشكلة: "الغرفة المزدحمة" مقابل "الغرفة الوحيدة"

لفهم الطريقة الجديدة، نحتاج أولاً إلى النظر في الطريقتين القديمتين اللتين تحاول هذه الطريقة تحسينهما:

الطريقة القديمة (MCTS): تخيل فريقاً من المستكشفين يحاولون رسم خريطة لكهف. يقومون ببناء شجرة ضخمة ومتفرعة من المسارات. في كل مرة يصلون فيها إلى طريق مسدود، يعودون لتجربة فرع مختلف.
- الجانب الجيد: إنهم دقيقون للغاية ولا يرتبكون بسهولة.
- الجانب السيئ: إنهم بطيئون. يجب عليهم بناء هيكل الشجرة بالكامل في ذاكرتهم. ومن الصعب جعل فريق ضخم من أجهزة الكمبيوتر يعملون معاً على هذا الأمر لأنهم يستمرون في الاصطدام ببعضهم البعض أثناء محاولة تحديث نفس الخريطة.
الطريقة البديلة (SMC): تخيل مجموعة من 1000 عداء (جسيمات) يبدأون جميعاً في نفس الوقت، ويركضون في مسارات مختلفة في آن واحد. هم لا يبنون شجرة؛ هم فقط يركضون.
- الجانب الجيد: إنهم سريعون للغاية ومن السهل جداً جعل 1000 جهاز كمبيوتر يشغلون هؤلاء الـ 1000 عداء بشكل متوازٍ.
- الجانب السيئ: كلما تعمق العداءون داخل الكهف، يحدث شيء غريب.
  - مشكلة "التباين" (Variance): كلما ركضوا لمسافة أبعد، أصبحت النتائج أكثر فوضوية. الأمر يشبه محاولة التنبؤ بالطقس بعد 10 سنوات من الآن؛ فكلما نظرت بعيداً، قلّت دقة توقعك.
  - مشكلة "تدهور المسار" (Path Degeneracy): في النهاية، يدرك جميع العداءين تقريباً أن مساراً واحداً معيناً يبدو أفضل قليلاً من غيره. فيتركون جميعاً مساراتهم الفريدة ويتزاحمون في ذلك المسار الواحد "الأفضل". فجأة، يصبح لديك 1000 عداء يفعلون الشيء نفسه تماماً. يتوقف الذكاء الاصطناعي عن "التفكير" ويتبع القطيع فحسب، مما يجعله يفوت مسارات أخرى قد تكون أفضل ومخفية.

الحل: TSMCTS (نهج الـ "مرتين")

ابتكر المؤلفون TSMCTS للحصول على سرعة "العدائين" (SMC) دون الوقوع في مشكلة الفوضى أو "الازدحام". وقد فعلوا ذلك عبر خطوتين رئيسيتين:

الخطوة 1: توقف عن عدّ العدائين، وابدأ في عدّ النقاط (SMCTS)

في طريقة العداء القديمة، كان الذكاء الاصطناعي يهتم فقط بـ المسار الذي سلكه العداءون. إذا سلك جميع العداء مساراً واحداً، فإن الذكاء الاصطنا الرئيسي يظن أن هذا هو الخيار الوحيد.

غير المؤلفون القواعد: بدلاً من مجرد مراقبة العدائين، أصبح الذكاء الاصطناعي الآن يحتفظ بـ لوحة نتائج (Scoreboard) لكل حركة بداية ممكنة.

حتى لو انتهى الأمر بجميع العداء الـ 1000 في نفس المسار، فإن الذكاء الاصطناعي يتذكر: "مهلاً، لقد جربنا ذلك المسار، وهذا هو متوسط النقاط الذي حصلنا عليه".
إذا سقط عداء من فوق منحدر، فإن الذكاء الاصطناعي لا ينسى ذلك المسار فحسب؛ بل يقوم بتحديث لوحة النتائج بالدرجة السيئة.
النتيجة: يحتفظ الذكاء الاصطناعي بـ "متوسط متحرك" لمدى جودة كل حركة بداية، حتى لو توقف العداءون عن استكشاف ذلك المسار المحدد. هذا يمنع مشكلة "الازدحام" لأن الذكاء الاصطناعي لا يزال يمتلك بيانات حول المسارات التي هجرها العداءون.

الخطوة 2: استراتيجية "البطولة" (المرتين)

الجزء الثاني من الحل يتعلق بكيفية استهلاك وقت الكمبيوتر.

تخيل أن لديك ميزانية لاختبار 100 حركة بداية مختلفة.
الطريقة القديمة: قد تختبر الـ 100 حركة قليلاً، أو تختبر بعض الحركات كثيراً.
طريقة TSMCTS: يستخدمون استراتيجية تسمى التقليص المتتالي (Sequential Halving) (مثل نظام خروج المغلوب في البطولات).
1. الجولة الأولى: تختار 16 حركة واعدة. ترسل فريقاً صغيراً من العدائين لاختبار جميع الحركات الـ 16.
2. الجولة الثانية: تنظر إلى النتائج. يتم استبعاد أفضل 8 حركات الأسوأ أداءً. تأخذ الثمانية المتبقية وترسل إليها المزيد من العدائين لاختبارها بعمق أكبر.
3. الجولة الثالثة: تستبعد أفضل 4 حركات الأسوأ. ترسل المزيد من العدائين إلى أفضل 4 حركات.
4. النهائي: تركز جميع مواردك على الحركة الواحدة الأفضل.

لماذا تسمى "مرتين" (Twice)؟
تقوم الخوارزمية بتشغيل "محاكاة العداء" (SMCTS) مرتين في حلقة تكرارية:

أولاً، تقوم بتشغيل محاكاة سريعة لمعرفة أي الحركات تبدو واعدة.
ثم، تقوم بتشغيل محاكاة ثانية، أكثر عمقاً، فقط على الفائزين من الجولة الأولى، باستخدام عدد أكبر من العدائين للحصول على درجة دقيقة للغاية.

لماذا يهم هذا الأمر (النتائج)

اختبرت الورقة البحثية هذه الطريقة الجديدة مقابل الطرق القديمة في بيئات متنوعة تشبه ألعاب الفيديو (بعضها يحتوي على خيارات محددة مثل الشطرنج، وبعضها يحتوي على حركات مستمرة مثل التحكم في روبوت).

تتوسع بشكل أفضل: مع إعطاء الذكاء الاصطناعي مزيداً من الوقت لـ "التفكير" (بحث أعمق)، كانت طريقة العداء القديمة تسوء (بسبب الفوضى والازدحام). أما TSMCTS فقد أصبحت أفضل.
أكثر استقراراً: التوقعات التي تقدمها النتائج أقل "تذبذباً" (تباين أقل).
لا تتعثر: نجحت في تجنب "تدهور المسار" حيث يتوقف الذكاء الاصطنا عن التفكير ويتبع القطيع فحسب.
لا تزال سريعة: حافظت على الطبيعة فائقة السرعة والمتوازية لطريقة العداء، مما يجعل من السهل تشغيلها على بطاقات الرسوميات (GPUs) الحديثة.

الملخص

فكر في TSMCTS كمدرب ذكي يدير فريقاً من الكشافين.

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

النتيجة هي ذكاء اصطناعي يمكنه التفكير بعمق أكبر، واتخاذ قرارات أفضل، والقيام بذلك بشكل أسرع من الطرق السابقة.

ملخص تقني: مونت كارلو المتسلسل مرتين للبحث في الأشجار (Twice-Sequential Monte Carlo for Tree Search)

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

حققت خوارزميات التعلم المعزز القائمة على النماذج (Model-based RL) التي تستخدم البحث (التخطيط) طفرات كبيرة في مجالات تتراوح من الألعاب إلى الروبوتات. الخوارزمية المهيمنة في هذا المجال هي بحث مونت كارلو في الأشجار (MCTS)، والتي تشغل أنظمة مثل AlphaGo وMuZero. ومع ذلك، تواجه MCTS عقبتين رئيسيتين:

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

لقد برزت مونت كارلو المتسلسلة (SMC) كبديل قابل للموازاة لـ MCTS. فمن خلال تقريب التوزيع عبر المسارات باستخدام $N$ من الجسيمات (particles) بالتوازي، توفر SMC توسعاً خطياً في الذاكرة وملاءمة فائقة للتسريع باستخدام وحدات معالجة الرسومات. ومع ذلك، تعاني SMC التقليدية عند تطبيقها على بحث التعلم المعزز من فشلين حرجين يمنعانها من التوسع مع زيادة عمق البحث (الحوسبة المتسلسلة):

التباين الأسي: يزدويد التباين في المقدر بشكل حاد مع عمق البحث بسبب النمو الأسي للمسارات الممكنة.
تدهور المسار (Path Degeneracy): ظاهرة حيث يصبح جميع الجسيمات، بعد عمق معين، مرتبطين بنفس إجراء الجذر (root action). يؤدي هذا إلى انهيار تقدير السياسة إلى توزيع دلتا (delta distribution)، مما يجعل البحث الإضافي عديم الفائدة ويتسبب في "تدهور الهدف" (target degeneracy) في إشارة التدريب.

2. المنهجية

يقترح المؤلفون بحث مونت كارلو المتسلسل مرتين في الأشجار (TSMCTS)، وهي خوارزمية جديدة مصممة للاحتفاظ بمزايا الموازاة لـ SMC مع التخفيف من مشكلات التباين والتدهور. تعتمد المنهجية على ثلاث تحولات مفاهيمية ومكونات خوارزمية:

2.1. إعادة صياغة SMC للتعلم المعزز (RL-SMC)

قام المؤلفون أولاً بإعادة صياغة SMC لتحسين السياسة من خلال الابتعاد عن إطار عمل "التحكم كاستدلال" (Control as Inference - CAI) المستخدم في الأعمال السابقة (مثل Piché et al., 2019). بدلاً من ذلك، قاموا بتعريف التوزيع المستهدف مباشرة فوق المسارات الناتجة عن سياسة محسنة $\pi'$ مشتقة من عامل جشع عام $I$ .

تحول المنظور: بدلاً من تقدير توزيع على المسارات، يركز البحث على تقدير قيم الأفعال ( $Q$ -values) للسياسة المحسنة عند الجذر.
الفائدة: يسمح هذا بدمج آلية الانتشار العكسي (backpropagation) مشابهة لـ MCTS، حيث يتم تجميع تقديرات القيمة عبر الجسيمات، مما يخفف من فقدان المعلومات عندما تتدهور الجسيمات إلى مسار واحد.

2.2. بحث مونت كارلو المتسلسل في الأشجار (SMCTS)

بناءً على صياغة RL-SMC، قدم المؤلفون SMCTS، التي تدمج خطوة انتشار عكسي قائمة على القيمة:

التوسع (Expansion): تنتقل الجسيمات إلى حالات جديدة.
البحث (Search): يتم حساب أوزان أخذ العينات بالأهمية (importance sampling weights) لمواءمة الجسيمات مع السياسة المحسنة.
الانتشار العكسي (Backpropagation): يتم تقييم العوائد (returns) ومتوسطها عبر الجسيمات المرتبطة بنفس إجراء الجذر لتحديث المتوسط المتحرك لقيم الأفعال ( $\bar{Q}_t$ ).

النتيجة: يعمل هذا التجميع على منع انهيار هدف السياسة إلى توزيع دلتا (تخفيف تدهور المسار) ويقلل من تباين المقدر عن طريق متوسط العوائد عبر الزمن.

2.3. بحث مونت كارلو المتسلسل مرتين في الأشجار (TSMCTS)

لمعالجة التباين وتحسين ميزانية البحث عند الجذر بشكل أكبر، تعامل TSMCTS اختيار إجراء الجذر كمسألة تحديد أفضل إجراء بأسلوب الندم البسيط (simple-regret) مع ميزانية معروفة. وهي تستخدم خوارزمية "التنصيف المتسلسل" (Sequential Halving - SH) كغلاف حول SMCTS:

التنصيف المتكرر: تعمل الخوارزمية في $\log_2 m_1$ من التكرارات (حيث $m_1$ هو عدد الإجراءات الأولية للبحث).
تخصيص الموارد: في كل تكرار، يتم تنصيف مجموعة الإجراءات المرشحة، بينما يتضاعف عدد الجسيمات المخصصة لكل إجراء متبقٍ.
تقليل التباين: تقلل هذه الاستراتيجية من أفق البحث لكل تكرار (بما أن إجمالي الحوسبة ثابت)، مما يقلل بطبيعته من التباين (بما أن تباين SMC ينمو مع العمق). علاوة على ذلك، تستخدم أوزان عكس التباين لتجميع تقديرات القيمة عبر التكرارات، مما يعطي الأولوية للإجراءات الأكثر احتمالاً لأن تكون مثالية.
الموازاة: من المهم ملاحظة أن البحث عن كل إجراء في تكرار معين يتم بشكل مستقل ومتوازٍ، مما يحافظ على الطبيعة الصديقة لوحدات معالجة الرسومات لـ SMC.

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

خوارزمية TSMCTS: خوارزمية بحث جديدة تجمع بين SMC، والانتشار العكسي بأسلوب MCTS، والتنصيف المتسلسل لتحقيق تحسين السياسة.
إعادة الصياغة النظرية: اشتقاق لـ SMC للتعلم المعزز مستقل عن إطار عمل "التحكم كاستدلال"، مما يسمح بعوامل جشع عام والتركيز المباشر على تقدير القيمة.
تخفيف قيود SMC: يوضح البحث أن TSMCTS تعالج بفعالية نمطي الفشل الرئيسيين لـ SMC القياسية:
- تتوسع بشكل ملائم مع زيادة الحوسبة المتسلسلة (عمق البحث)، بينما يتدهور أداء SMC القياسية.
- تقلل بشكل كبير من تباين المقدر وتمنع تدهور المسار عند الجذر مقارنة بـ SMC القياسية.
الحفاظ على الموازاة: تحتفظ TSMCTS بالتعقيد الخطي للمساحة وقابلية الموازاة الطبيعية لـ SMC، مما يجعلها مناسبة للتسريع باستخدام وحدات معالجة الرسومات.

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

قيم المؤلفون TSMCTS عبر مجموعة من البيئات المنفصلة (Jumanji: Snake, Rubik's Cube) والمستمرة (Brax: Ant, HalfCheetah, Humanoid)، مقارنة بكل من:

خط الأساس SMC: نهج SMC القياسي المستخدم في SPO (Macfarlane et al., 2024).
SMCTS: خوارزمية SMC المتوسطة القائمة على القيمة.
GumbelAZ: وكيل حديث يعتمد على MCTS يستخدم GumbelMCTS (Danihelka et al., 2022).
TRT SMC: متغير حديث من SMC مع تحسين منطقة الثقة.

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

التوسع مع العمق: على عكس خط الأساس SMC، الذي يتدهور أداؤه مع زيادة عمق البحث بسبب التباين والتدهور، فإن أداء TSMCTS يتحسن أو يظل مستقراً مع زيادة العمق.
التباين والتدهور: تظهر TSMCTS تبايناً أقل بكثير في مقدر الجذر وتحافظ على عدد أعلى من الأفعال النشطة في هدف السياسة (تجنب الانهيار إلى إجراء واحد) مقارنة بخط الأساس SMC وTRT SMC.
الأداء: تتفوق TSMCTS بشكل كبير على خط الأساس SMC وSMCTS في جميع البيئات. كما أنها تتفوق على أو تضاهي أداء GumbelAZ (المعتمد على MCTS) مع الحفاظ على مزايا الكفاءة الحسابية لـ SMC.
الكفاءة: تظهر TSMCTS كفاءة زمن تشغيل أفضل من GumbelMCTS وكفاءة مماثلة لخط الأساس SMC، مع زيادة طفيفة فقط في تكلفة الحوسبة.

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

يدعي البحث أن TSMCTS تمثل تقدماً كبيراً في تحسين السياسة القائم على البحث للتعلم المعزز. من خلال النجاح في سد الفجوة بين مزايا الموازاة لـ SMC ومتانة MCTS، تقدم TSMCTS بديلاً قابلاً للتوسع للتعلم المعزز القائم على النماذج.

يؤكد المؤلفون أن نهجهم:

يحل مفارقة القابلية للتوسع: يسمح لـ SMC بالاستفادة من زيادة الحوسبة المتسلسلة (البحث الأعمق) دون المعاناة من انفجار التباين أو تدهور المسار الذي يحد عادة من قدراتها.
يعمم تحسين السياسة: تدعم الصياغة الأساسية أي عامل جشع، مما يجعل الطريقة قابلة للتكيف مع التحسينات المستقبلية في عوامل تحسين السياسة.
يحافظ على التوافق مع الأجهزة: يحتفظ بخصائص جعلت SMC مثالية لأجهزة التعلم المعزز العميق الحديثة (GPUs)، وتحديداً الموازاة والنمو الخطي في الذاكرة، على عكس MCTS التي تواجه صعوبات مع هذه القيود.

يضع هذا العمل TSMCTS ليس فقط كمتغير لـ SMC، بل كعامل بحث قوي وعام يمكن أن يحل محل MCTS في السيناريوهات التي تكون فيها الموازاة وكفاءة الذاكرة أمراً بالغ الأهمية، مع تجنب عيوب SMC القياسية.