🤖 machine learning

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

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

المؤلفون الأصليون: Oran Ridel, Alon Cohen

نُشر 2026-05-18

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

CC BY 4.0

المؤلفون الأصليون: Oran Ridel, Alon Cohen

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

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

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

هذا هو جوهر المشكلة التي تتناولها الورقة البحثية: كيف تستكشف بيئة ما بكفاءة عندما لا تعرف ما هي "المكافأة" (الهدف)؟

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

السيناريوهان

تتناول الورقة نسختين مختلفتين قليلاً من مشكلة "الاستكشاف الأعمى" هذه:

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

التحدي: بما أن الهدف قد يكون أي شيء، يجب أن تكون دقيقاً للغاية.

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

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

الطريقة القديمة: نهج "التجربة والخطأ"

حاولت الطرق السابقة (مثل طريقة Li et al., 2024) حل ذلك عبر إجراء العديد من التجارب الصغيرة والمنفصلة.

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

الطريقة الجديدة: "الدليل السياحي الذكي"

يقترح المؤلفان خوارزمية تعمل مثل دليل سياحي واحد ذكي للغاية يتعلم المدينة في رحلة واحدة مستمرة وذكية.

1. استراتيجية "الفضول" (الخطوة 1)
بدلاً من إجراء تجارب منفصلة، تقوم الخوارزمية بجلسة "تعلم عبر الإنترنت" (online learning) طويلة واحدة. فهي تنشئ سلسلة من الأهداف الوهمية والمؤقتة (المكافآت) المصممة خصيصاً لإجبار العميل (agent) على زيارة الأجزاء التي يصعب الوصول إليها أو التي لا تُفهم جيداً.

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

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

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

لماذا تهم هذه الورقة البحثية؟

حقق المؤلفان إنجازين كبيرين:

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

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

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

الحل: أثبت المؤلفان "حداً أدنى" (lower bound) جديداً. لقد أظهرا أنه مهما كنت بارعاً، لا يمكنك القيام بالأمر بشكل أسرع من حد معين. هذا يغلق الفجوة، ويثبت أن أفضل الطرق الموجودة هي بالفعل مثالية (بأفضل قدر ممكن).

الملخص

فكر في هذه الورقة البحثية كعملية ترقية لطريقة تعلم الروبوت لبيئة جديدة.

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

لقد أثبت المؤلفون أن نهج "الجولة الذكية" هذا ليس أسرع فحسب، بل هو أيضاً مثبَت رياضياً كأكثر الطرق كفاءة ممكنة لأنواع معينة من المشكلات.

ملخص تقني: حدود محسنة للاستكشاف غير المرتبط بالمكافأة والاستكشاف الخالي من المكافأة

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

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

الاستكشاف الخالي من المكافأة (RFE): يستكشف الوكيل بيئة مجهولة دون أي إشارة مكافأة. والهدف هو إنتاج سياسة تكون $\epsilon$ -مثالية لأي دالة مكافأة تعسفية يتم الكشف عنها بعد مرحلة الاستكشاف.
الاستكشاف غير المرتبط بالمكافأة (RAE): مشابه لـ RFE، ولكن دالة المكافأة تُستمد من فئة محدودة مسبقة وصغيرة (حجمها متعدد الحدود في $|S|, |A|, H$ ). الهدف هو إيجاد سياسة $\epsilon$ -مثالية لدالة المكافأة المحددة المستمدة من هذه الفئة.

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

المنهجية

يستبدل النهج المقترح الاعتماد على عدة إجراءات فرعية خالية من الندم (no-regret subroutines) مستقلة كما في الأعمال السابقة، بإجراء تعلم عبر الإنترنت (online learning procedure) موحد. تعمل الخوارزمية (الخوارزمية 1) عبر ثلاث مراحل:

1. إنشاء سياسة الاستكشاف

بدلاً من تشغيل عدة خوارزميات عشوائية خالية من الندم (كما فعل Jin et al., 2020b; Li et al., 2024b)، يستخدم المؤلفون تشغيلًا واحدًا لخوارزمية الاشتقاق المرآتي عبر الإنترنت (Online Mirror Descent - OMD) عبر سلسلة من دوال المكافأة المساعدة المصممة بعناً.

الآلية: تولد الخوارزمية سلسلة من المكافآت $\{\lambda_t\}$ المصممة لتوجيه الوكيل نحو أزواج (الحالة-الفعل) الأقل زيارة. وتكون المكافأة عند الخطوة $t$ متناسبة عكسياً مع عدد الزيارات لزوج (الحالة-الفعل) (بالإضافة إلى ثابت $c$ للتعامل مع الزيارات ذات الاحتمالية المنخفضة).
منظور الأمثلية: يتم تأطير هذه العملية كحل تقريبي لمشكلة تحسين محدبة فوق فضاء مقاييس الإشغال (occupancy measures) الصالحة. وتحديداً، تهدف إلى تقليل هدف حاجز اللوغاريتم السالب $f(\mu) = -\sum \log \mu_h(s,a)$ .
الأهمية: من خلال استخدام خوارزمية واحدة لعمليات ماركوف عبر الإنترنت (مقتبسة من Rosenberg & Mansour, 2019) بدلاً من تكرارات أسلوب Frank-Wolfe، تقلل الطريقة بشكل كبير من حدود تعقيد العينات من الرتبة المنخفضة. وهي تعيد استخدام العينات طوال عملية التعلم لبناء "غطاء سياسة" (policy cover) يضمن استكشافاً شبه منتظم لثلاثيات (الحالة-الفعل-الزمن) الهامة.

2. تقدير الديناميكيات

باستخدام سياسة الاستكشاف الناتجة من الخطوة 1، يجمع الوكيل $N$ من المسارات. وللتعامل مع الارتباطات الزمنية المتأصلة في بيانات المسار، يستخدم المؤلفون إطار عمل فرعي العينات ثنائي الطور (Li et al., 2024a). تقوم هذه التقنية بتقسيم مجموعة البيانات إلى مجموعة رئيسية ومجموعة مساعدة لإحداث استقلال إحصائي، مما يسمح ببناء نواة انتقال تجريبية $\hat{P}$ مع ضمانات تركيز صارمة.

3. تقدير السياسة

بمجرد الكشف عن دالة المكافأة الحقيقية، تحسب الخوارزمية سياسة $\epsilon$ -مثالية باستخدام التشاؤم في مواجهة عدم اليقين (pessimism in the face of uncertainty).

تبني الخوارزمية نموذج MDP تجريبي باستخدام $\hat{P}$ والمكافأة المكشوفة.
تطبق حداً جزائياً $b_h(s,a)$ مشتقاً من تفاوتات التركيز من نوع بيرنشتين (Bernstein-style concentration inequalities) على تقديرات قيم Q، حيث يتناسب هذا الجزاء مع التباين التجريبي وعدد الزيارات، مما يثبط السياسة عن زيارة أزواج (الحធាតុ-الفعل) المغطاة بشكل ضعيف.
السياسة النهائية $\hat{\pi}$ هي السياسة المثلى لهذا الـ MDP التجريبي المتشائم.

المساهمات الرئيسية والنتائج

1. تحسين تعقيد العينة للاستكشاف غير المرتبط بالمكافأة (RAE)

تقدم الورقة خوارزمية جديدة تحقق التعقيد الأمثل للعينات من الرتبة العالية لـ RAE، وهو ما يطابق الحد الأدنى لتعريف أفضل سياسة (Best Policy Identification - BPI).

النتيجة: تعقيد العينة هو $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$ .
التحسين: بينما حقق العمل السابق (Li et al., 2024b) حد الرتبة العالية الأمثل $O(|S||A|H^3/\epsilon^2)$ ، إلا أن حدّهم عانى من حد ذي تعقيد عالٍ من الرتبة المنخفضة مما جعل الحد أمثلياً فقط لقيم $\epsilon$ صغيرة للغاية. تقلل الطريقة المقترحة هذا الحد من الرتبة المنخفضة بشكل كبير، مما يجعل الخوارزمية قابلة للتطبيق على نطاق أوسع من معاملات الدقة.

2. حد أدنى وثيق للاستكشاف الخالي من المكافأة (RFE)

يثبت المؤلفون حداً أدنى وثيقاً لتعقيد العينة لـ RFE في نماذج MDP غير متجانسة زمنياً.

النتيجة: تتطلب أي خوارزمية RFE عدد $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$ من المسارات في التوقع.
الأهمية: يحل هذا التخمين الذي طرحه Li et al. (2024b) بأن الحد الأدنى لـ minimax في حالة RFE غير المتجانس زمنياً أكبر بعامل قدره $H$ عن الحالة المتجانسة زمنياً. وهذا يثبت أن الحدود العليا الموجودة (مثل M´enard et al., 2021) هي مثالية حتى لوjarithmic factors.

3. الإطار التقني

تقدم الورقة منظوراً تقنياً جديداً من خلال ربط إنشاء سياسة الاستكشاف بتقليل هدف حاجز اللوغاريتم فوق مقاييس الإشغال. وتوضح أن نهج الاشتقاق المرآتي عبر الإنترنت يمكنه تقريب هذا الحل بكفاءة أكبر من أساليب Frank-Wolfe السابقة، وبالتالي تقليل الاعتماد على أبعاد المشكلة في حدود الرتبة المنخفضة.

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

تدعي الورقة أنها تساهم في تطوير الفهم النظري للاستكشاف بدون مكافآت من خلال:

الفصل بين الاستكشاف والاستغلال: توضح التعقيد الجوهري للعينات للاستكشاف في نماذج MDP ذات الأفق المحدود.
الواقعية في RAE: من خلال تخفيف المتطلبات المقيدة على معامل الدقة $\epsilon$ الموجودة في الحدود المثالية السابقة، تجعل الطريقة المقترحة الاستكشاف غير المرتبط بالمكافأة عملياً حتى في أنظمة الدقة المتوسطة.
اكتمال التوصيف: يوفر الجمع بين الحد العلوي الجديد لـ RAE والحد الأدنى الوثيق لـ RFE توصيف minimax كاملاً لتعقيد العينة لهذه المشكلات (حتى العوامل اللوغاريتمية).

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