ملخص تقني: طريقة لاغرانج المعززة للتقارب في التكرار الأخير لعمليات ماركوف لاتخاذ القرار المقيدة

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

تتناول الورقة مشكلة تحسين السياسة لعمليات ماركوف لاتخاذ القرار المقيدة (CMDPs) ذات الأفق اللانهائي والخصم المعتاد. في هذا الإطار، يجب على العميل تعظيم المكافأة التراكمية $V^\pi_r(\rho)$ مع ضمان أن مكافآت القيود التراكمية $V^\pi_{c_i}(\rho)$ تستوفي عتبات محددة $b_i$ لعدد $m$ من القيود. وخلافًا لعمليات ماركوف لاتخاذ القرار (MDPs) القياسية حيث تكون السياسات المثلى حتمية، فإن السياسات المثلى لـ CMDPs هي عمومًا سياسات احتمالية.

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

لقد اقتصرت الأعمال الحديثة التي تحاول إثبات تقارب التكرار الأخير إلى حد كبير على الإعدادات الجدولية (tabular settings) أو اعتمدت على متغيرات خوارزمية (مثل التنظيم الثقيل) التي يصعب تنفيذها أو غير عملية للمشكلات واسعة النطاق.

المنهجية

يقترح المؤلفون إطار عمل عام يعتمد على طريقة لاغرانج المعززة (Augmented Lagrangian - AL)، وهي نهج كلاسيكي للتحسين المقيد، لتحقيق تقارب مثبت في التكرار الأخير لـ CMDPs.

1. إطار لاغرانج المعزز

بدلاً من لاغرانج القياسي المستخدم في طرق PD، يقوم إطار العمل بتحسين دالة لاغرانج المعززة $L_\beta(\pi, \lambda)$:
$$L_\beta(\pi, \lambda) := V^\pi_r(\rho) + \frac{\beta}{2} \sum_{i=1}^m \left( -\min\left\{ V^\pi_{c_i}(\rho) - b_i - \frac{\lambda_i}{\beta}, 0 \right\}^2 + \frac{\lambda_i^2}{\beta^2} \right)$$
حيث $\beta > 0$ هو معامل الجزاء و $\lambda$ هي مضاعفات لاغرانج. يعمل حد الجزاء التربيعي على ردع انتهاكات القيود. تقوم الخوارزمية بتحديث السياسة (المتغير الأولي) بشكل تكراري لتعظيم هذه الدالة تقريبًا، وتحدث المتغيرات الثنائية (مضاعفات لاغرانج) بناءً على انتهاكات القيود.

2. حل المشكلة الفرعية لـ AL

التحدي الجوهري هو أن $L_\beta(\pi, \lambda)$ غير مقعر بالنسبة للسياسة $\pi$، مما يجعل المشكلة الفرعية صعبة الحل. يقوم المؤلفون بتفكيك الحل إلى إعدادين:

• الإعداد الجدولي (Tabular Setting): يقترح المؤلفون حل المشكلة الفرعية لـ AL باستخدام صعود Q المسقط (Projected Q-Ascent - PQA). قاموا باشتقاق تدرج السياسة لمشكلة AL الفرعية، والذي يتضمن مكافأة زيفة غير مستقرة $\Gamma(\pi)$ تعتمد على مستوى استيفاء القيود للسياسة الحالية. ومن خلال استخدام PQA، أثبتوا ضمانات التقارب العالمي في التكرار الأخير للمشكلة الفرعية.
• التقريب الدالي (السياسات اللوغاريتمية الخطية): للتعامل مع مساحات الحالة-الفعل الواسعة، تم توسيع إطار العمل ليشمل السياسات البارامترية (تحديدًا السياسات اللوغاريتمية الخطية). اشتق المؤلفون تدرج سياسة AL الذي يتفكك خطيًا إلى مكونات المكافأة والقيود الأصلية، مما يسمح باستخدام أدوات التقدير القياسية (مثل تلك المستخدمة في PPO أو SPMA). كما قدموا تحديث PQA المسقط (PPQA)، والذي يتضمن:
  1. حساب تحديث السياسة المثالي (خطوة PQA).
  2. إسقاط هذا التحديث على فئة السياسة الممكنة باستخدام تباعد KL الأمامي، والذي تمت صياغته كمشكلة تحسين بديلة (انحدار لوجستي متعدد الفئات مع تسميات ناعمة).

3. تحليل التقارب

يقدم المؤلفون تحليلًا معياريًا:

1. أثبتوا أولاً أن طريقة AL غير الدقيقة تتقارب نحو حل $\epsilon$-أمثل لـ CMDP إذا حقق محلل المشكلة الفرعية دقة محددة ($O(1/\epsilon^2)$ تكرار للحلقة الخارجية).
2. بعد ذلك، قاموا بتحليل الحلول المحددة (PQA و PPQA) لإظهار قدرتها على تحقيق الدقة المطلوبة للمشكلة الفرعية.
3. بدمج هذه النتائج، أثبتوا أن الخوارزمية الإجمالية تحقق تقارب التكرار الأخير العالمي بتعقيد عينات يبلغ $O(1/\epsilon^6)$ من تقييمات التدرج لكل من الإعدادات الجدولية واللوغاريتمية الخطية.

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

1. إطار عمل AL غير دقيق وعام: تقدم الورقة إطار عمل معياري لحل CMDPs باستخدام طريقة AL غير الدقيقة. فهي تفصل تحليل تكرارات AL عن اختيار محلل المشكلة الفرعية، وتثبت أن $O(1/\epsilon^2)$ من التكرارات الخارجية تكفي لإيجاد سياسة $\epsilon$-مثلى، بشرط حل المشكلة الفرعية بدقة كافية.
2. تقارب التكرار الأخير في الإعداد الجدولي: من خلال تطبيق إطار العمل باستخدام صعود Q المسقط (PQA) للإعداد الجدولي، أثبت المؤلفون تقارب التكرار الأخير العالمي بتعقيد قدره $O(1/\epsilon^6)$. وهذا يعالج عدم استقرار المكافأة الزيفة في مشكلة AL الفرعية.
3. التوسع إلى التقريب الدالي: تم تعميم إطار العمل على السياسات اللوغاريتمية الخطية. اشتق المؤلفون تدرج سياسة AL واقترحوا نسخة مسقطة (PPQA) تحقق ضمانات تقارب مماثلة قدرها $O(1/\epsilon^6)$. وعلى عكس الأعمال السابقة، لا تتطلب هذه الطريقة تعديلات خوارزمية غير قياسية (مثل الإسقاط على مجمعات مقيدة) أو افتراضات هيكلية مقيدة (مثل تقريب الوظيفة المتوافق) وتدعم قيودًا متعددة.
4. التحقق التجريبي: تم تطبيق إطار العمل باستخدام PPO و SPMA (خوارزمية تحسين سياسة حديثة) وتقييمه على مهام التحكم المستمر من Safety-Gymnasium. أظهرت النتائج أن نهج AL المترح يقدم أداءً مشابهًا للنماذج المرجعية المصممة بكثافة مثل PPO-Lag و CPO، مع تقديم ضمانات نظرية للسياسة النهائية.

النتائج

• نظريًا: تثبت الورقة أن الخوارزمية المقترحة تعيد سياسة احتمالية هي حل $\epsilon$-تقريبي لمشكلة CMDP بعد $O(1/\epsilon^6)$ من تقييمات التدرج. وينطبق هذا على كل من الإعدادات الجدولية وفئات السياسة اللوغاريتمية الخطية.
• تجريبيًا (الجدولي): في البيئات الجدولية (Constrained Cliff World, Constrained Deep Sea Treasure)، تتقارب طرق PQA-ALM و PPQA-ALM المقترحة بسلاسة نحو السياسة المثلى مع حد أدنى من التذبذب، متفوقة على أو موازية لطرق التكرار الأخير الأخرى مثل RPG-PD و ReLOAD.
• تجريبيًا (التحكم المستمر): في مهام Safety-Gymnasium (SafetyAntVelocity, SafetyHalfCheetahVelocity, SafetyHopperVelocity)، تحقق متغيرات SPMA-ALM و PPO-ALM عوائد وانتهاكات قيود مقاربة لـ PPO-Lag و CPO. والجدير بالذكر أن طرق AL تظهر سلوكًا أقل تذبذبًا وتحقيقًا أكثر اتساقًا للقيود (انتهاكات أقل في المتوسط وفي الذيل) مقارنة بالنماذج المرجعية.

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

تدعي الورقة أنها تسد الفجوة بين الضمانات النظرية والنشر العملي في التعلم المعزز المقيد.

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

يقر المؤلفون بوجود قيود، وتحديدًا الاعتماد القوي على الحد الأدنى من احتمالية زيارة الحالة ($\rho_{min}$) في الإعداد الجدولي، وحد التحيز ($\epsilon_{bias}$) للسياسات اللوغاريتمية الخطية، مما يشير إلى هذه كتوجهات للعمل المستقبلي. كما أشاروا إلى أن التوجهات المستقبلية تشمل دمج أساليب Actor-Critic أو الطرق خارج السياسة (off-policy) في الإطار النظري.