📊 statistics

Maximizing Rollout Informativeness under a Fixed Budget: A Submodular View of Tree Search for Tool-Use Agentic Reinforcement Learning

تقدم هذه الورقة البحثية InfoTree، وهو إطار عمل للبحث الشجري أثناء وقت التدريب لتعلم التعزيز الوكيل لاستخدام الأدوات، والذي يصيغ معلوماتية التدفق (rollout informativeness) كمسألة تعظيم شبه نمطية (submodular maximization) لاشتقاق استراتيجية اختيار واعية بعدم اليقين (UUCB) ومخصص ميزانية تكيفي، مما يؤدي إلى تفوق كبير على الأساليب الحالية عبر مختلف معايير الاستدلال واستخدام الأدوات مع الحفاظ على المتانة والكفاءة.

المؤلفون الأصليون: Yuelin Hu, Zhenbo Yu, Zhengxue Cheng, Wei Liu, Li Song

نُشر 2026-05-08

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Yuelin Hu, Zhenbo Yu, Zhengxue Cheng, Wei Liu, Li Song

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

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

ومع ذلك، هناك مشكلة كبيرة: تأثير "غرفة الصدى" (The Echo Chamber Effect).

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

تقدم هذه الورقة البحثية طريقة جديدة تسمى INFOTREE لإصلاح ذلك. وإليك كيف تعمل، باستخدام تشبيهات بسيطة:

1. المشكلة: "الفصل الدراسي الممل"

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

2. الحل: "المستكشف الفضولي" (التعظيم تحت المجموعات الجزئية - Submodular Maximization)

بدلاً من ترك الروبوت يختار الإجابات عشوائياً، يستخدم INFOTREE استراتيجية ذكية لاختيار أي مسار يجب استكشافه بعد ذلك. يعامل المؤلفون هذا الأمر كأنه لعبة "تعظيم التنوع".

يستخدمون مفهوماً رياضياً يسمى "التبعية الجزئية" (Submodularity). فكر في الأمر كأنك تجهز حقيبة سفر:

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

يعمل INFOTREE كحامل حقائب ذكي. فهو ينظر إلى محاولات الروبوت الحالية ويتساءل: "أي خطوة تالية ستعطينا أكبر قدر من المعلومات الجديدة؟" هو لا يبحث فقط عن الإجابة "الأفضل"؛ بل يبحث عن الإجابة التي تختلف عن غيرها.

3. المكونات الثلاثة لـ "المُحدد الذكي"

لتحديد المسار الذي يجب استكشافه، يستخدم النظام صيغة (تسمى UUCB) تمزج بين ثلاثة مكونات، مثل وصفة لطهي حساء جيد:

مكون "الثقة" (التغطية - Coverage): "هل جربنا هذا المسار من قبل؟" إذا كان الروبوت واثقاً وقد رأى هذا المسار كثيراً، فلا داعي للذهاب إلى هناك مجدداً.
مكون "الفضول" (الحداثة - Novelty): "هل زرنا هذا الجزء من الخريطة من قبل؟" إذا كان المسار جديداً وغير مستكشف، فسيتم تشجيع الروبوت على الذه_ب إلى هناك.
مكون "الفوضى" (التباين/الاعتلاج - Contrast/Entropy): "هل الإجابات هنا فوضوية ومختلفة؟" يبحث النظام بنشاط عن الأماكن التي يكون فيها الروبوت مرتبكاً أو حيث تؤدي المحاولات المختلفة إلى نتائج مختلفة. هذه "الفوضى" هي في الواقع خبر جيد لأنها تعني أن هناك الكثير لتعلمه.

من خلال موازنة هذه العناصر الثلاثة، يتجنب الروبوت "الفصل الدراسي الممل" ويضمن أن كل جلسة تدريب تعلمه شيئاً جديداً.

4. شبكة الأمان: "فريق الإنقاذ" (مخصص الميزانية التكيفي - Adaptive Budget Allocator)

أحياناً، حتى المحدد الذكي قد يعلق. ربدما يكون الروبوت مرتبكاً لدرجة أن كل مسار يجربه يؤدي إلى طريق مسدود.

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

5. دفعة السرعة: "التوسع التخميني" (Speculative Expansion)

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

الحل: يستخدم INFOTREE خدعة "تخمينية". فهو يسمح للكمبيوتر بتخمين الخطوة التالية قبل أن تنتهي العملية الحسابية السابقة بالكامل. إذا كان التخمين صحيحاً، فذلك رائع! وإذا كان خاطئاً، فإنه ببسا يعمل تراجع ويحاول مجدداً.
النتيجة: هذا يجعل العملية برمتها أسرع بكثير (مما يقلل الوقت الضائع بأكثر من 10%)، مما يسمح للروبوت بالتعلم في وقت أقل.

الخلاصة

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

النتائج:

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

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

ملخص تقني: تعظيم معلوماتية التدفق (Rollout Informativeness) تحت ميزانية ثابتة

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

تتناول الورقة البحثية عقبة هيكلية في التعلم المعزز (RL) للنماذج اللغوية الكبيرة (LLMs) المعززة بالأدوات، وذلك في ظل المكافآت النهائية المتفرقة (على سبيل المثال، $R \in \{-1, +1\}$ ). تكمن المشكلة الجوهرية في معلوماتية التدفق تحت ميزانية ثابتة (RIFB).

في خوارزمية تحسين السياسة النسبية للمجموعات (GRPO) القياسية، يتم تطبيع إشارة الميزة (advantage signal) عن طريق الانحراف المعياري للمكافآت ضمن مجموعة من $B$ من عمليات التدفق (rollouts). إذا أدت جميع عمليات التدفق المستقلة الـ $B$ لـ "مطالبة" (prompt) معينة إلى نفس النتيجة (كلها نجاح أو كلها فشل)، فإن الانحراف المعياري يصبح صفرًا، مما يؤدي إلى انهيار الميزة إلى الصفر. ونتيجة لذلك، لا يتم ضخ أي كتلة تدرج (gradient mass) في السياسة، مما يجعل الحوسبة المستهلكة في عمليات التدفق تلك عديمة الفائدة.

صاغ المؤلفون هذا كأحد نتائج الاستحالة للعينات المستقلة:

النظرية 1: لأي عينة مستقلة غير مقيدة بالميزانية، فإن احتمال الانهيار (التباين الصفري) هو $p^B + (1-p)^B$ ، حيث $p$ هو احتمال النجاح لكل مطالبة.
الاستنتاج: عندما تقترب $p$ من $0 $أو$ 1 $(المطالبات الصعبة)، ينمو احتمال عدم الانهيار خطيًا بحد أقصى مع الميزانية ($ B \cdot \min(p, 1-p) $). وبالتالي، فإن مجرد زيادة ميزانية التدفق$ B$ لا يمكنه الهروب من نظام التدرج الصفري للمطالبات الصعبة؛ إذ يظل معدل الانهيار بعيدًا عن الصفر بغض regardless عن حجم الميزانية.

2. المنهجية: INFOTREE

للتغلب على قيود العينات المستقلة، يقترح المؤلفون INFOTREE، وهو إطار عمل للبحث في الأشجار أثناء التدريب، يعمل على تحسين أي الحالات يجب توسيعها بدلاً من عدد العينات.

2.1 الصياغة تحت المجموعات الجزئية (Submodular Formulation)

الرؤية المركزية هي أن مشكلة اختيار الحالة الوسيطة المراد توسيعها لتعظيم معلوماتية الشجرة يمكن صياغتها كمسألة تعظيم دالة جزئية رتيبة (monotone submodular maximization). تتكون دالة الهدف $F$ من ثلاثة عناصر:

التغطية (Coverage): تتبع القيمة المرتدة الخلفية $\bar{Q}(s)$ للأوراق.
الحداثة (Novelty): تتبع مصطلح الاستكشاف بناءً على عدد الزيارات (مصطلح UCB الكلاسيكي).
التباين (Contrast): يتتبع تنوع النتائج بين العقد الشقيقة، والمستمد من إنتروبيا مستوى الرمز (token-level entropy).

أثبت المؤلفون أن $F$ هي دالة رتيبة وجزئية (submodular). وهذا يسمح باستخدام مُنتقي جشع (greedy selector) مع ضمان تقريب نظري قدره $(1 - 1/e)$ للجدول الأمثل للتوسع.

2.2 مُنتقي UUCB

الحل الجشع للمسألة الجزئية ينتج عنه درجة الحد الأعلى لعدم اليقين (Uncertainty-aware Upper Confidence Bound - UUCB)، وهي ليست مجرد استدلال تجريبي بل هي ربح هامشي مغلق الصيغة من الهدف:
$\text{UUCB}(v) = \bar{Q}(v) + c\sqrt{\frac{\ln N(p_a(v))}{N(v)+1}} + \lambda_H \tilde{H}(v) - \lambda_C \tilde{C}(v) - \lambda_D \tilde{d}(v)$

$\bar{Q}(v)$ : ربح التغطية.
الحد الثاني: ربح الحداثة (استكشاف UCB القياسي).
$\lambda_H \tilde{H}(v)$ : ربح التباين، ويمثل إنتروبيا مستوى الرمز الموزعة طبقياً حسب العمق (مقيسة لتكون قابلة للمقارنة عبر الأعماق).
العقوبات: تقوم $\lambda_C$ و $\lambda_D$ بمعاقبة تكاليف استدعاء الأدوات وعمق التوسع، على التوالي، لاحترام قيد الميزانية.

2.3 مكونات النظام

يدمج INFOTREE مُنتقي UUCB مع آليتين إضافيتين لمعالجة نقاط الضعف العملية:

مخصص الميزانية التكيفي (Adaptive Budget Allocator - ABA): شبكة MLP خفيفة الوزن يتم تدريبها خارج الخط (offline) للتنبؤ بما إذا كانت المطالبة ذات شجرة ذات نتيجة موحدة (عرضة للانهيار) يمكن "إنقاذها" بواسطة عملية تدفق واحدة ذات درجة حرارة عالية. إذا تجاوز احتمال الإنقوات المتوقع عتبة معينة، يتم إطلاق عملية تدفق إضافية. هذا يرفع نسبة النتائج المختلطة من ~58% إلى ~76% مع زيادة في الميزانية تقل عن 5%.
التوسع التخميني (Speculative Expansion): لتقليل زمن الاستجابة (latency)، يقوم العمال بتقييم درجات UUCB باستخدام قيم Q التي قد تكون قديمة (stale) ضمن حدود معينة. وتعمل خطوة المصالحة على قبول أو التراجع عن التوسعات بناءً على علامات الإصدار (version tags). هذا يقلل من التكاليف الإضافية من 14.3% إلى 4.8%.
الميزة الهرمية (Hierarchical Advantage): إشارة تدرج مشتقة من التباين بين الأشقاء على طول المسار من الجذر إلى الورقة، مما يوفر آلية بديلة لتخصيص الائتمان (credit assignment) تكمل ميزة GRPO المعتمدة على تطبيع المجموعة.

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

الصياغة النظرية: حددت الورقة مفهوم RIFB وأثبتت أن العينات المستقلة تعاني من انهيار مستمر في المطالبات الصعبة، بغض النظر عن حجم الميزانية.
الاختزال الجزئي (Submodular Reduction): أثبتت أن بناء الشجرة تحت ميزانية ثابتة هو مسألة تعظيم جزئية، مما يوفر ضماناً نظرياً قدره $(1-1/e)$ لمُنتقي UUCB الجشع.
الاشتقاق التحليلي: أظهرت أن مكافأة الإنتروبيا في UUCB هي نتيجة تحليلية للهدف الجزئي (مصطلح التباين)، وليست مجرد حيلة تجريبية.
تصميم النظام: تقديم ABA والتوسع التخميني يخلق إطار عمل عملياً يوازن بين المعلوماتية والكفاءة الحسابية.
التعامد (Orthogonality): أظهر المؤلفون أن آلية الاختيار الخاصة بهم تعمل على محور متعامد مع إعادة وزن المسارات (مثل CW-GRPO) وإعادة استخدام التدفق (مثل مشاركة البادئة في Tree-GRPO).

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

تم تقييم الطريقة على تسعة اختبارات معيارية تشمل الاستدلال الرياضي، والبحث عبر الويب، ووكلاء البرمجة/أنظمة التشغيل الغنية بالأدوات.

الأداء: تفوق INFOTREE باستمرار على كل من Flat GRPO و DeepSearch و Tree-GRPO و AT2PO و CW-GRPO و RC-GRPO.
- في اختبار AIME 2025، حقق INFOTREE درجة Mean@32 بلغت 30.2 (مقابل 27.7 لـ Flat GRPO و 29.1 لـ Tree-GRPO).
- في اختبار GAIA، حقق دقة بنسبة 56.0% (مقابل 44.8% لـ Flat GRPO).
القابلية للتركيب: أدى الجمع بين INFOTREE ومشاركة بادئة Tree-GRPO أو أوزان مساهمة CW-GRPO إلى تحقيق مكاسب إضافية، مما يؤكد تعامد هذه المنهجيات.
المتانة: أظهرت شبكة المعلمات الفائقة (hyperparameter grid) بحجم $5 \times 5 \times 5$ لمعاملات UUCB ( $\lambda_H, \lambda_C, \lambda_D$ ) أن أكثر من 75% من المساحة تقع ضمن 2.1 نقطة من القيمة المثلى، مما يشير إلى أن الطريقة ليست هشة تجاه ضبط المعلمات.
الكفاءة: رغم البحث في الأشجار، تم تقليل زمن الاستجابة الفعلي إلى 4.8% عبر التوسع التخميني. انخفضت "الخطوات للوصول للهدف" (الخطوات للوص reach Mean@32 قدره 28) من 248 (في Flat GRPO) إلى 138 (في INFOTREE)، وهو تحسن بمقدار 1.57 ضعف في زمن التنفيذ الفعلي.
معلوماتية التدرج: أظهر القياس المباشر لنورم التدرج التربيعي (squared gradient norm) أن INFOTREE ينتج RIFB أعلى بمقدار 3.9 ضعف مقارنة بـ Flat GRPO.

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

تدعي الورقة إعادة تموضع تصميم استراتيجيات التدفق من مجرد تفضيل هندسي إلى مسألة تحسين مؤسسة نظرياً.

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

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