ملخص تقني: تحسين السياسة الثنائي-الأولي للنماذج المحدودة من نوع CMDP الخطية مع الخسائر العدائية

إعداد المشكلة

تتناول هذه الورقة تحدي التعلم التعزيزي الآمن (Safe RL) في البيئات التي يجب فيها استيفاء قيود السلامة رغم الاضطرابات العدائية. وتحديداً، ينظر المؤلفون في النماذج المحدودة من نوع CMDP الخطية العدائية ذات الأفق المحدود (Finite-Horizon Adversarial Linear CMDPs).

يتم تعريف الإعداد بواسطة التوبل $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, {P_h}, {f^k}, {g^k}, s_1, b)، حيث:

• الخسائر العدائية: يتم اختيار دالات الخسارة $f^k = \{f^k_h\}$ بشكل تعسفي من قبل خصم في بداية كل حلقة $k$ (تغذية راجعة للمعلومات الكاملة). هذه الخسائر لا تُسحب من توزيع ثابت.
• التكاليف العشوائية: يتم سحب دالات التكلفة $g^k = \{g^k_h\}$ بشكل مستقل وموزع متماثلاً (i.i.d.) من توزيع ثابت $G$ (تغذية راجعة بنظام البانديت/Bandit feedback)، والتي تمثل قيود السلامة.
• البنية الخطية: تمتلك نوى الانتقال (transition kernels)، ودالات الخسارة، ودالات التكلفة بنية خطية بالنسبة لخريطة سمات (feature mapping) معلومة $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$.
• الهدف: يسعى الوكيل إلى تقليل الخسارة المتوقعة التراكمية مع ضمان عدم تجاوز التكلفة المتوقعة التراكمية لميزانية قدرها $b$.

يُقاس الأداء من خلال الندم (Regret) (فرق الخسارة التراكمية مقارنة بالسياسة المثلى) وانتهاك القيود (Constraint Violation) (التكلفة الزائدة التراكمية عن الميزانية). الهدف هو تحقيق حدود دون خطية (sublinear) لكلا المقياسين.

المنهجية

يقترح المؤلفون خوارزمية تحسين السياسة الثنائي-الأولي (Primal-Dual Policy Optimization) (الخوارزمية 1) المصممة للتعامل مع التفاعل بين الخسائر العدائية والتكاليف العشوائية في سياق التقريب الدالي الخطي. تدمج الخوارزمية أربعة مكونات رئيسية:

1. تهيئة الحقبة وانكماش السمات (Epoch Initialization and Feature Contraction):
   تعمل الخوارزامية في حقبات (epochs). تبدأ الحقبة عندما يزداد محدد مصفوفة التصميم $\Lambda^k_h$ بمعامل ضربي. عند التهيئة، يتم إعادة ضبط السياسة إلى سياسة موحدة (uniform policy)، ويتم إعادة ضبط المتغير الثنائي إلى الصفر. والأهم من ذلك، تستخدم الخوارزمية انكماش السمات (feature contraction)، حيث يتم تقليص السمة الأصلية $\phi$ باستخدام دالة سيجمويد (sigmoid) لمنع تقديرات دالة Q من التوسع بشكل غير منضبط. هذه التقنية، المقتبسة من Cassel & Rosenberg (2024)، تبسط تمثيل السياسة لأغراض حساب عدد التغطية (covering number).

2. تنفيذ السياسة والتقدير:
   في كل حلقة، ينفذ الوكيل إجراءات بناءً على السياسة الحالية، ويلاحظ الخسارة العدائية والتكلفة العشوائية، ثم يقوم بتحديث مصفوفة التصميم. بعد ذلك، يقوم بتقدير معاملات دالات الخسارة والتكلفة ويحسب تقديرات دالة Q ($\hat{Q}$) وتقديرات دالة القيمة ($\hat{V}$) باستخدام السمات المنكمشة والمكافآت التفاؤلية (optimistic bonuses).

3. الخلط الدوري للسياسة (Periodic Policy Mixing):
   الابتكار الجوهري هو الخلط الدوري للسياسة. بدلاً من خلط السياسة (اضطرابها نحو سياسة موحدة) في كل حلقة، تطبق الخوارزمية الخلط فقط مرة واحدة كل $K^B$ حلقة (حيث $B=3/4$).

   • الدافع: الخلط المتكرر ضروري للحد من المتغير الثنائي (عبر تحليل الانجراف/drift analysis) ولكنه يزيد من تعقيد فئة السياسة (عدد التغطية). الخلط الدوري يوازن بين هذين المتطلبين المتنافسين.
   • الآلية: كل $K^{3/4}$ حلقة، يتم خلط السياسة الحالية $\hat{\pi}^k$ مع السياسة الموحدة $\pi_{unif}$ عبر توليفة محدبة: $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$.

4. التحديث الثنائي المنظم (Regularized Dual Update):
   يتم تحديث المتغير الثنائي $Y^k$ (المرتبط بقيد التكلفة) باستخدام خطوة صعود التدرج المنظمة:
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   الحدود التنظيمية ($-4\alpha\eta H^3 Y^k$ والثوابت) مصممة لسحب المتغير الثنائي نحو الصفر، مما يسمح بإجراء تحليل انجراف ليابونوف (Lyapunov drift analysis) للحد من $Y^k$ دون الاعتماد على افتراضات التناظر القوي التي تفشل في البيئات العدائية.

5. سياسات LogSumExp Softmax الموزونة:
   فئة السياسة الناتجة هي LogSumExp softmax موزونة. وبسبب الخلط الدوري، لا تكون السياسة مجرد أس لمجموع دالات Q، بل هي مجموع موزون لأسس المجموع الجزئي لتقديرات دالة Q. هذا الهيكل يسم يسمح للسياسة بالتكيف مع الخسائر المختارة عدائياً مع الحفاظ على عدد تغطية قابل للتحكم.

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

1. أول حدود دون خطية لـ CMDPs الخطية العدائية:
   تقدم الورقة أول خوارزمية تحقق حدود ندم وانتهاك قيود دون خطية في سياق CMDPs الخطية ذات الخسائر العدائية والتكاليف العشوائية. الحدود هي $\tilde{O}(K^{3/4})$، حيث $K$ هو عدد الحلقات.

2. حجة عدد التغطية الجديدة:
   وضع المؤلفون حجة جديدة لعدد التغطية لسياسات LogSumExp softmax الموزونة. على عكس سياسات softmax القياسية حيث تكون الأوزان موحدة، يؤدي عملية الخلط إلى إدخال معاملات وزن متغيرة $\zeta_i$. يثبت المؤلفون أن لوغاريتم عدد التغطية لهذه الفئة ينمو كـ $\tilde{O}(n^2 d^2)$، حيث $n$ هو عدد خطوات الخلط و $d$ هو بُعد السمات. هذه النتيجة غير بديهية لأن معاملات الوزن تعتمد على كل من معامل الخلط وتقديرات دالة Q.

3. مكونات خوارزمية للتحكم:
   تقدم الورقة مكونين جديدين للتحكم المشترك في عدد التغطية والمتغير الثنائي:

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

النتائج

الضمانات النظرية:
بموجب شرط سلاتر (Assumption 1) وافتراض أن $H^2 \leq K$، وباحتمال لا يقل عن $1-\delta$، تحقق الخوارزمية:

• الندم (Regret): $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• انتهاك القيود (Constraint Violation): $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

كلا المقياسين يتناسبان دون خطياً مع $K$ (تحديداً $K^{3/4}$)، مما يشير إلى أن متوسط الندم ومتوسط انتهاك القيود يتقاربان نحو الصفر مع زيادة عدد الحلقات.

التجارب العددية:
تم تقييم الخوارزمية على نموذج معدل لـ CMDP لجدولة المهام (job-scheduling) مع خسائر عدائية. عبر $100,000$ حلقة:

• الندم: نما بشكل دون خطي، مما أكد الحد النظري.
• انتهاك القيود: نما في البداية بسرعة ولكن تقارب نحو الصفر بعد حوالي 45,000 حلقة، مما يثبت قدرة الخوارزمية على استيفاء قيود السلامة على المدى الطويل.

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

تدعي الورقة أنها أول خوارزمية فعالة مثبتة للتعلم التعزيزي الآمن مع التقريب الدالي الخطي في البيئات العدائية. تكمن أهميتها في سد الفجوة بين:

1. النماذج التبادلية (Tabular) العدائية لـ CMDP: الأعمال السابقة (مثل Qiu et al., 2020) تعاملت مع البيئات العدائية ولكنها كانت محدودة بمساحات حالات صغيرة ومنتهية.
2. النماذج الخطية العشوائية لـ CMDP: الأعمال السابقة (مثل Ghosh et al., 2022) تعاملت مع مساحات حالات كبيرة ولكنها افترضت بيئات مستقرة (عشوائية).

من خلال تقديم سياسة LogSumExp softmax الموزونة واستراتيجية الخلط الدوري، يوضح المؤلفون أنه من الممكن التعامل مع مساحات حالات كبيرة (عبر التقريب الخطي) والخسائر العدائية في آن واحد. تشير الورقة بتواضع إلى أنه بينما تم تحقيق $\tilde{O}(K^{3/4})$، فإن الحد الأمثل $\tilde{O}(\sqrt{K})$ يظل سؤالاً مفتوحاً لهذا الإعداد المحدد، لا سيما فيما يتعلق بالمفاضلة بين خطوات الخلط وأعداد التغطية. كما يسلط العمل الضوء على صعوبة توسيع التحديثات القائمة على مقاييس الإشغال (occupancy-measure-based) إلى الطرق القائمة على السياسة في نماذج CMDP الخطية العدائية، مما يبرر نهج تحسين السياسة الثنائي-الأولي المقترح.