🤖 machine learning

Value Functions as Supermartingale Certificates

تؤسس هذه الورقة صلة نظرية تُظهر أن دوال القيمة للسياسات التي تستوفي خصائص $\omega$ -regular تشفر شهادات ستريت (Streett) من نوع "سوبر مارتينجال" (supermartingale)، مما يجسر الفجوة بين التحقق الصوري والتعلم التعزيزي لتمكين التخليق المنهجي للشهادات عبر فضاءات الحالات المتناهية، واللانهائية كعدّية، والمتصلة.

المؤلفون الأصليون: Alessandro Abate, Daniel Contro, Mirco Giacobbe, Agustín Martínez-Suñé, Diptarko Roy

نُشر 2026-06-01

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

CC BY 4.0

المؤلفون الأصليون: Alessandro Abate, Daniel Contro, Mirco Giacobbe, Agustín Martínez-Suñé, Diptarko Roy

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

تخيل أنك تعلم روبوتاً كيفية التنقل في متاهة. تريد من الروبوت أن يتبع مجموعة معقدة من القواعد، مثل "استمر في التحرك حتى تجد الكنز، ثم ابقَ في المنطقة الآمنة للأبد، ولا تطأ الحمم البركانية أبداً". في عالم علوم الحاسوب، يُسمى هذا تحقيق "خاصية أوميغا-منتظمة" (omega-regular property) (وهي طريقة فنية للقول بأن القاعدة تنطبق على رحلة لانهائية).

لفترة طويلة، كان هناك طريقتان منفصلتان للتعامل مع هذا الأمر:

طريقة "البرهان الرياضي" (التحقق - Verification): يستخدم الرياضيون ما يسمى بـ شهادة السوبرمارتينجال (Supermartingale Certificate). تخيلها كأنها "بطاقة تقييم سلامة". إذا استطعت رسم خريطة حيث ينخفض "التقييم" دائماً (أو يبقى ثابتاً) مع تحرك الروبوت، وكان يصل إلى الصفر فقط عندما يكون الروبوت آمناً، فلديك برهان رياضي على أن الروبوت لن يفشل أبداً، بغض النظر عن تقلبات الحظ (stochasticity). المشكلة هي أن رسم هذه الخريطة يدوياً للمتاهات المعقدة أمر صعب للغاية ولا يتناسب مع الأنظمة الضخمة.
طريقة "التجربة والخطأ" (التعلم التعزيزي - Reinforcement Learning): هنا يتعلم الروبوت من خلال الممارسة. يجرب الروبوت أفعالاً، ويحصل على مكافآت مقابل التحركات الجيدة، ويتعلم دالة القيمة (Value Function). فكر في دالة القيمة كأنها "خريطة سعادة" تخبر الروبوت بمقدار المكافأة المستقبلية التي يمكنه توقعها من أي مكان. وبينما يعمل هذا بشكل رائع لإيجاد مسار جيد، إلا أنه يفتقر عادةً إلى ضمان رسمي بأن الروبوت سينجح بالفعل، خاصة في العوالم المعقدة أو اللانهائية أو المستمرة.

الاختراق الكبير

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

لقد فعلوا ذلك باستخدام التشبيهات التالية:

وصفتي المكافأة

يقترح المؤلفون طريقتين مختلفتين لمنح الروبوت مكافآت بحيث تصبح "خريطة سعادته" تلقائياً شهادة سلامة صالحة.

الوصفة 1: مكافأة "المنطقة الآمنة"

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

الوصفة 2: مكافأة "العقوبة والجائزة"

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

ما الذي أثبتوه؟

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

وهذا يعني:

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

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

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

لماذا هذا مهم (وفقاً للورقة البحثية)

هذا يخلق مساراً مبدئياً جديداً نحو "التعلم التعزيزي الموثق" (Certified Reinforcement Learning). فبدلاً من مجرد الأمل في أن تعمل السياسة المتعلمة، أو المعاناة في كتابة براهين معقدة يدوياً، يمكننا الآن:

تدريب سياسة باستخدام طرق الذكاء الاصطناعي القياسية.
تقييم "دالة القيمة" الخاصة بها.
التحقق مما إذا كانت هذه الدالة تحقق قواعد "شهادة سلامة".

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

ملخص تقني: دوال القيمة كشهادات فوق مارينجال (Supermartingale Certificates)

بيان المشكلة

تعتمد عملية التحقق من الأنظمة العشوائية مقابل خصائص $\omega$ -regular (بما في ذلك المنطق الزمني الخطي LTL) عبر فضاءات حالات عامة (منتهية، أو منتهية عدداً، أو مستمرة) عادةً على شهادات فوق مارينجال (supermartingale certificates). هذه الشهادات هي دوال ذات قيم حقيقية تحقق قواعد إثبات محددة، وتعمل كضمانات رياضية للوفاء بالمواصفات بالاحتمال شبه المؤكد (almost-sure satisfaction). ومع ذلك، فإن تخليق هذه الشهادات يمثل تحدياً؛ إذ تعتمد الطرق الحالية غالباً على التحسين المقيد (constrained optimization)، وهو ما لا يتوسع بشكل جيد مع فضاءات الحالات الكبيرة أو المستمرة.

في المقابل، تم تطبيق التعلم التعزيزي (Reinforcement Learning - RL) على نطاق واسع لتخليق السياسات للمهام من نوع $\omega$ -regular. وبينما يمكن لطرق التعلم التعزيزي تعظيم احتمالية الوفاء بالمواصفات، إلا أنها تفتقر عادةً إلى الضمانات الرسمية بأن سياسة (غير مثالية) تم تدريبها ستفي بالمواصفات باحتمالية معينة، خاصة خارج فضاءات الأفعال والحالات المنتهية. هناك فجوة بين الآليات النظرية للتحقق من "فوق مارينجال" والآليات العملية لتقييم سياسة التعلم التعزيزي.

المنهجية

تؤسس هذه الورقة لربط نظري جديد بين دالة القيمة (value function) لسياسة في سياق تعلم تعزيزي مخصوم (discounted RL) وشهادات ستريت فوق مارينجال (Streett supermartingale certificates). الفرضية الأساسية هي أنه تحت تصميمات مكافآت محددة، تقوم دالة القيمة $V^\pi$ لسياسة $\pi$ التي تحقق مواصفات LTL بشكل شبه مؤكد، بترميز شهادة "ستريت فوق مارينجال" صالحة.

يقترح المؤلفون تصميمين مختلفين للمكافآت لتحقيق ذلك:

تصميم المكافأة 1 (معرفة المجموعات الماصة - Absorbing Set Knowledge):
- المتطلب: معرفة المجموعات الماصة الناتجة عن السياسة (تحديداً أكبر مجموعة ماصة فرعية من متممة اتحاد أزواج ستريت).
- الآلية: يتم ضبط المكافأة لتكون 1 عند دخول العملية إلى المجموعة المستهدفة $B$ أو إلى مجموعة ماصة لا يمكن زيارة $A$ أو $B$ منها مرة أخرى.
- الأساس النظري: تمثل دالة القيمة $V^\pi$ مجموع المكافآت المخصومة المتوقعة. ومن خلال تعريف الشهادة $W(s) = C - V^\pi(s)$ (حيث $C$ هو ثابت متعلق بمعامل الخصم)، يثبت المؤلفون أن $W$ تحقق شروط "ستريت فوق مارينجال": فهي تتناقص بشكل صارم في التوقع عندما تكون في $A \setminus B$ (بسبب الحدود الموحدة لأوقات الوصول)، وتظل غير متزايدة في أما-ن أخرى.
تصميم المكافأة 2 (معرفة المواصفات فقط - Specification Knowledge Only):
- المتطلب: معرفة هيكل المواصفات (زوج ستريت $(A, B)$ ) فقط، دون الحاجة لمعرفة المجموعات الماصة الخاصة بالسياسة.
- الآلية: يستخدم هذا التصميم معامل خصم يعتمد على الحالة $\Gamma(s)$ ودالة مكافأة تمنح مكافآت موجبة لزيارة $B$ ومكافآت سالبة لزيارة $A \setminus B$ .
- الأساس النظري: يتم ضبط معامل الخصم ليكون $\gamma < 1$ عندما تكون المكافآت غير صفرية، و $1 $في الحالات الأخرى. وتحت فرضية "حد التكرار الإيجابي" (التي تحد من عدد الخطوات المتوقع في$ A $قبل الوصول إلى$ B$)، تقوم دالة القيمة مرة أخرى بترميز "فوق مارينجال". ويتم ضبط نسبة المكافآت الموجبة إلى السالبة لضمان بقاء الشهادة غير سالبة وتتناقص بشكل صارم حيث يلزم ذلك.

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

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

الجسر النظري: تثبت الورقة أن دالة القيمة لسياسة تحقق مواصفات LTL هي شهادة "ستريت فوق مارينجال" صالحة تحت تصميمات مكافآت مناسبة (النظرية 1 و2).
مخططان للمكافآت: يقدم المؤلفون طريقتين مختلفتين لتخليق هذه المكافآت: إحداهما تستفيد من المجموعات الماصة الخاصة بالسياسة (النظرية 1) والأخرى تعتمد فقط على هيكل المواصفات مع استخدام الخصم المعتمد على الحالة (النظرية 2).
العمومية: النتائج ليست مقتصرة على نماذج ماركوف لاتخاذ القرار (MDPs) المنتهية؛ بل تنطبق على فضاءات الحالات العامة، مما يعالج فجوة في التحقق القائم على التعلم التعزيزي والذي يفتقر غالباً للضمانات الرسمية في الفضاءات اللانهائية أو المستمرة.
التحقق التجريبي: تحقق المؤلفون من النظرية في نماذج ماركوف لاتخاذ القرار (MDPs) المنتهية باستخدام بيئة "عالم الشبكة" (grid-world). قاموا بتخليق شهادات لمختلف مواصفات LTL التي تغطي تسلسل "مانا-بنويل" (Manna-Pnueli hierarchy)، وتحققوا من قواعد إثبات "فوق مارينجال"، وقارنوا نتائج احتمالات الوفاء باستخدام برنامج التحقق من النماذج PRISM.

النتائج

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

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

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

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

تضع الورقة هذا العمل كخطوة تأسيسية نحو التعلم التعزيزي المعتمد (certified reinforcement learning)، حيث يمكن التحقق رسمياً من السياسات المدربة لخصائص $\omega$ -regular بما يتجاوز الحالات المنتهية، مما يسد الفجوة بين قابلية التوسع في التعلم التعزيزي ودقة التحقق الرسمي.