Answer-Set-Programming-based Abstractions for Reinforcement Learning

بيان المشكلة
تتيح التعلم المعزز (RL) للوكلاء تعلم السياسات من خلال التفاعل، ولكن التطبيقات الواقعية غالباً ما تعاني من مساحات شاسعة من الحالات والأفعال، مما يجعل مناهج التعلم البدائية غير قابية للتطبيق. وبينما توفر طرق التقريب مثل "Deep Q-Learning" قدرة على التعميم، إلا أنها غالباً ما تتطلب كميات هائلة من بيانات التدريب ويمكن أن تظهر عدم استقرار. يعالج التعلم المعزز العلاقاتي (RRL) هذه القيود من خلال استخدام المنطق من الدرجة الأولى للاستدلال حول الكائنات وعلاقاتها، مما يسهل التعميم عبر حالات متشابهة. وتحديداً، يقوم إطار عمل CARCASS (التجريد المدمج باستخدام الروابط العلاقاتية لتجميع مساحات الحالة-الفعل) بواسطة فان أوترلو (2004) بنمذجة عمليات ماركوف لاتخاذ القرار (MDPs) باستخدام التجريدات المنطقية. ومع ذلك، فإن التنفيذ الأصلي لـ CARCASS يعتمد على لغة Prolog وحل SLDNF، والتي، رغم كونها تصريحية في المبدأ، غالباً ما تتطلب ميزات إجرائية (مثل ترتيب القواعد أو الـ cuts) من أجل الكفاءة، وتفتقر إلى الدعم الأصلي للاستدلال غير الرتيب، والتحسين، ومعالجة التفضيلات.

المنهجية
يقترح المؤلفون طريقة عامة لإعادة تنفيذ إطار عمل CARCASS باستخدام برمجة مجموعات الإجابة (ASP). تعد ASP لغة تمثيل معرفي قائمة على المنطق وهي تصريحية بالكامل، وتدعم الاستدلال غير الرتيب، والتحسين، والقيود.

1. ترميز ASP لـ CARCASS: يحدد المؤلفون دالة تسمية لربط الحالات المجردة وأزواج الحالة-الفعل بالمصطلحات الأساسية. ويقومون ببناء ترميز معياري يتكون من:

• البرامج ($P_{\hat{s}_i}$) التي ترمز الحالات المجردة الفردية كقواعد تتكون أجسامها من الحروف التي تُعرف الحالة المجردة.
• البرامج ($P_{\hat{s}_i, \hat{a}_{i,j}}$) التي ترمز علاقة التغطية لأزواج الحالة-الفعل المجردة، وتربط الأفعال الملموسة بالمجردة عبر ذرات aCov.
• آلية قائمة القرار ($P_{\hat{C}}$) باستخدام قاعدة اختيار لاختيار حالة تغطية مجردة واحدة بالضبط لكل حالة ملموسة، وقيد لضمان أن الاختيار يتبع القائمة المرتبة (بإعطاء الأولوية لأدنى مؤشر).
• حالة مجردة "فارغة" ($\hat{s}_\infty$) ذات أعلى مؤشر تغطي جميع الحالات التي لا تغطيها قواعد محددة، لضمان وجود بديل افتراضي.

2. تكامل التعلم عبر الإنترنت: يدمج المؤلفون هذا الترميز في حلقة Q-learning عبر الإنترنت (الخوارزمية 2). بالنسبة لحالة ملموسة معينة، يقوم حلّال ASP بحساب مجموعة الإجابات المثلى لتحديد الحالة المجردة المغطاة ومجموعة الأفعال المجردة المقبولة. ثم يختار الوكيل فعلاً ملموساً من المجموعة المغطاة بواسطة الفعل المجرد المختار ويقوم بتحديث قيمة Q لزوج الحالة-الفعل المجرد.

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

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

1. طريقة ترميز عامة: يقدم البحث طريقة منهجية لترميز تجريدات CARCASS في ASP، موضحاً كيف يمكن للغة تصريحية بالكامل أن تحقق تجريدات الحالة-الفعل العلاقاتية.
2. تكييف التعلم عبر الإنترنت: يوضح المؤلفون كيفية استخدام تجريدات CARCASS القائمة على ASP ضمن إعداد Q-learning عبر الإنترنت، مع التعامل مع الاختيار الديناميكي للحالات والأفعال المجردة.
3. التقييم التجريبي: تم تقييم التنفيذ في مجالين متميزين:

• عالم الكتل (Blocks World): مهمة تكديس $n$ من الكتل حيث يقلل التجريد مساحة الحالة-الفعل إلى حجم ثابت بغض النظر عن قيمة $n$.
• MiniGrid: مجموعة من مهام التنقل في عالم الشبكة (مثل Door Key و Multi Room) حيث تُستخدم المعرفة الخلفية لاستنتاج تخطيطات الغرف وأقصر المسارات، وبناء حالات مجردة بناءً على العقدة التالية في المسار.

النتائج
يقارن التقييم التجريبي بين Q-learning المجرد وQ-learning الملموس عبر عالم مكون من 20 كتلة وثلاث بيئات MiniGrid.

• الاستقرار: أظهر Q-learning المجرد استقراراً ثابتاً، حيث ظل الوسيط والعرض الربيعي للمردود مرتفعاً بعد التعلم الأولي، بينما أظهر Q-learning الملموس تقلبات كبيرة أو فشلاً في التقارب في البيئات المعقدة.
• الجودة: حقق Q-learning المجرد معدلات نجاح عالية (على سبيل المثال، قريبة من 100% في آخر 500 حلقة لمهام MiniGrid)، متفوقاً بشكل كبير على Q-learning الملموس، الذي غالباً ما فشل في تحقيق عوائد إيجابية في نفس الإطار الزمني.
• كفاءة العينات: تطلب النهج المجرد عدداً أقل بكثير من الحلقات لتعلم سياسات عالية الجودة مقارنة بالنهج الملموس. على سبيل المثال، في عالم الـ 20 كتلة، حقق التعلم المجرد عوائد وسيطة إيجابية بحلول الحلقة 376، بينما ظل التعلم الملموس عند خط الأساس السلبي.
• اختلافات النمذجة: في دراسة حالة MiniGrid، سمح ترميز ASP بمواصفات مدمجة وتصريحية للبحث عن المسار والقيود، بينما تطلب تنفيذ Prolog المماثل بحثاً خوارزمياً صريحاً (البحث بالعرض)، مما يسلط الضوء على ميزة ASP في الفصل بين مواصفات المشكلة ومنطق التحكم.

الأهمية والادعاءات
يخلص البحث إلى أن تنفيذ CARCASS باستخدام ASP يوفر نهجاً واعداً لبناء التجريدات في RL، خاصة عندما تكون المعرفة بالمجال متاحة. يدعي المؤلفون أن التجريدات القائمة على ASP توفر بديلاً مرناً لـ CARCASS القائم على Prolog من خلال دعم:

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

يشير المؤلفون بتواضع إلى أنه بينما جودة السياسات المتعلمة مقبولة وتم تعلمها بعينات أقل، لا يوجد ضمان للتقارب نحو سياسة مثلى بشكل عام، وأن التجريد نفسه قد لا يحافظ على السياسة المثلى للمشكلات التي تُصنف ضمن NP-hard (كما هو موضح في حالة عالم الكتل حيث يضحي التجريد بالمثالية مقابل القابلية للتطبيق). يضع هذا العمل نفسه كخطوة نحو أطر عمل مدفوعة بالمعرفة للتعلم المعزز العلاقاتي تدعم تعلم السياسات القابل للتطوير (elaboration-tolerant).