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

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

يتناول هذا العمل التعلم التعزيزي ثنائي المستوى (BRL) في الإعدادات التي لا تكون فيها المشكلة في المستوى الأدنى (LL) عبارة عن عملية قرار ماركوف (MDP) قياسية ذات سياسة واحدة، بل هي لعبة ماركوفية ذات مجموع صفري (min–max) منتظمة (MMZSMG).

في هذا الإطار الهرمي:

• المستوى الأعلى (UL): يقوم المُحسِّن باختيار المعلمات $x$ (مثل هياكل الحوافز أو تشكيل المكافآت) لتقليل دالة الهدف $f(x, \phi, \psi)$.
• المستوى الأدنى (LL): يتفاعل وكيلان متضادان (لاعب الحد الأدنى بسياسة $\pi_\phi$ ولاعب الحد الأقصى بسياسة $\pi_\psi$) في لعبة ماركوف محكومة بالمعلمة $x$. يسعيان للوصول إلى توازن نقطة السرج (توازن ناش) الذي يحل:
  $$(\phi^*(x), \psi^*(x)) \in \arg\min_{\phi'} \max_{\psi'} J(x, \phi', \psi')$$
  حيث تمثل $J$ دالة القيمة المنتظمة للعبة.
• الهدف: يتم تقييم هدف المستوى الأعلى عند التوازن المستحث من لعبة المستوى الأدنى:
  $$\min_x F(x) \equiv f(x, \phi^*(x), \psi^*(x))$$

يكمن التحدي الجوهري في الاقتران الاستراتيجي بين لاعبي المستوى الأدنى. فخلافًا لعمليات MDP ذات السياسة الواحدة، يعتمد الاستجابة المثلى لأحد اللاعبين على سلوك الآخر، مما يجعل حساب التدرجات الفائقة (hypergradients) (مشتقات هدف المستوى الأعلى بالنسبة لـ $x$) مكلفًا حوسبيًا ومعقدًا بنيويًا. تعتمد طرق BRL الحالية غالبًا على معلومات الدرجة الثانية (معكوسات هسيان) أو افتراضات هيكلية خاصة بـ MDPs ذات السياسة الواحدة، والتي تفشل في التعميم على البنية المقترنة لـ MMZSMGs.

2. المنهجية: PANDA

يقترح المؤلفون خوارزمية PANDA (النزول-الصعود لنيكايدو-إيسودا المعزز بالعقوبة - Penalty-Augmented Nikaido–Isoda Descent–Ascent)، وهي خوارزمية تدرج سياسة عشوائية من الدرجة الأولى مصممة لحل التحسين ثنائي المستوى فوق نقاط السرج للألعاب الماركوفية (BOSMG) دون الحاجة إلى مشتقات الدرجة الثانية.

المكونات الرئيسية:

1. إعادة الصياغة القائمة على العقوبة:
   بدلاً من حساب التدرجات الفائقة مباشرة، تعيد PANDA صياغة مشكلة المستوى الثنائي المقيدة باستخدام دالة نيكايدو-إيسودا (NI)، $g(x, \phi, \psi)$، التي تقيس الفجوة بين زوج السياسات الحالي وتوازن ناش. يتم تحويل المشكلة المقيدة إلى هدف عقوبة غير مقيد:
   $$L_\lambda(x, \phi, \psi) = f(x, \phi, \psi) + \lambda g(x, \phi, \psi)$$
   حيث $\lambda$ هو معامل العقوبة.

2. خوارزمية تكرارية ثلاثية الخطوات:
   تعمل الخوارزمية في حلقة خارجية (لتحديث $x$) وحلقة داخلية (لتحديث السياسات $\phi, \psi$):

   • الخطوة 1: تقريب الاستجابة المثلى: تقرب الخوارزمية سياسات الاستجابة المثلى ($\tilde{\phi}, \tilde{\psi}$) للسياسات الحالية باستخدام تدرج السياسة للنزول (للاعب الحد الأدنى) والصعود (للاعب الحد الأقصى). يسمح هذا بتقدير دالة NI كالتالي: $g(x, \phi, \psi) \approx J(x, \phi, \tilde{\psi}) - J(x, \tilde{\phi}, \psi)$.
   • الخطوة 2: تقريب المسألة الفرعية للعقوبة: تقوم الخوارزمية بتحديث معلمات السياسة $(\phi, \psi)$ عبر تدرج السياسة العشوائي لتقليل الهدف البديل المعزز $h(x, \phi, \psi) = \frac{1}{\lambda}f(x, \phi, \psi) + g(x, \phi, \psi)$. هذه الخطوة تدفع سياسات المستوى الأدنى نحو نقطة السرج.
   • الخطوة 3: خطوة التدرج الفائق: يتم تحديث معلمة المستوى الأعلى $x$ باستخدام تقدير تدرج عشوائي للهدف المعزز $L_\lambda$. ومن الأهمية بمكان أن هذا التدرج يُحسب باستخدام معلومات الدرجة الأولى من المسارات المختارة، مما يتجنب قلب مصفوفة هسيان المستوى الأدنى.

3. التقدير العشوائي:
   تعتمد الطريقة على عمليات سحب (roll-outs) مونت كارلو مع آفاق مقطوعة لتقدير تدرجات دالات القيمة وفجوة NI، مما يجعلها مناسبة للإعدادات واسعة النطاق والقائمة على العينات.

3. المساهمات النظرية

تضع الورقة ضمانات تقارب صارمة لخوارزمية PANDA تحت افتراضات قياسية (مكافآت محدودة، استمرارية ليبشيتز، وشروط بولياك-لوجاستيك - PŁ).

• التقارب إلى النقاط الثابتة: ثبت أن PANDA تتقارب إلى نقطة ثابتة $\epsilon$ للمشكلة ثنائية المستوى الأصلية دون الحاجة إلى افتراضات التحدب لكل من أهداف المستوى الأعلى أو المستوى الأدنى.
• حدود التعقيد:
  • تعقيد التكرار: $\tilde{O}(\epsilon^{-1})$ من التكرارات الخارجية.
  • تعقيد العينات: $\tilde{O}(\epsilon^{-3})$.
    تطابق هذه المعدلات حدود الحالة الراهنة المعروفة فقط لـ BRL مع MDPs ذات السياسة الواحدة، رغم التعقيد المضاف للعبة الماركوفية ذات المجموع الصفري المقترنة.
• الخصائص الهيكلية: يثبت المؤلفون نتائج هيكلية جديدة لـ MMZSMGs المنتظمة، بما في ذلك:
  • تفرد زوج سياسات التوازن تحت التنظيم العام.
  • خاصية PŁ غير الموحدة لدالة NI بالنسبة لمعلمات السياسة، وهو أمر بالغ الأهمية لتحليل التقارب.
  • خصائص النعومة واستمرارية ليبشيتز لدالة NI والهدف الفائق.

4. النتائج التجريبية

يتحقق المؤلفون من صحة PANDA من خلال تجارب عددية في إعدادين:

1. مشكلة تصميم الحوافز الاصطناعية:

   • الإعداد: يضع مصمم المستوى الأعلى حوافز للتأثير على وكيلين متنافسين في MDP صغير.
   • المقارنة المرجعية: تمت المقارنة مع Meta-Gradient (استدلالي)، وDifferentiable Arbitrating (DA، درجة ثانية)، وPBRL (قائم على العقوبة لسياسة واحدة).
   • النتائج: تحقق PANDA أعلى مكافأة حوافز للمستوى الأعلى وتتقارب إلى فجوة توازن ناش (NE gap) قريبة من الصفر. كما تؤدي أداءً مشابهًا لخط الأساس "الكمال" (Oracle) الذي يستخدم البرمجة الديناميكية الدقيقة ومعلومات الدرجة الثانية، وتتفوق بشكل كبير على غيرها من خطوط الأساس من الدرجة الأولى.

2. لعبة الحارس والمتسلل (Sentinel-Intruder):

   • الإعداد: لعبة عالم شبكي حيث يحاول الحارس القبض على المتسلل. هدف المستوى الأعلى هو تقليل زيارات الحارس للمناطق المحظورة (الخطرة) مع الحفاظ على اللعب التنافسي.
   • النطاق: تم الاختبار على شبكات $5 \times 5$ و $20 \times 20$.
   • النتائج: تحقق PANDA باستمرار خسارة أقل للمستوى الأعلى (زيارات أقل للمناطق المحظورة) وفجوات NE أصغر مقارنة بـ DA وPBRL وMeta-Gradient، مما يظهر القابلية للتوسع والمتانة في البيئات الأكبر والأكثر تعقيدًا.

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

تدعي الورقة أن PADA هي أول خوارزمية عشوائية من الدرجة الأولى ذات ضمانات تقارب مثبتة للمشكلات التي يكون فيها المستوى الأدنى عبارة عن MMZSMG منتظمة.

• سد الفجوة: تعالج فجوة حرجة في أدبيات BRL حيث تفشل الطرق الحالية في التعامل مع التفاعلات متعددة الوكلاء التنافسية في المستوى الأدنى بكفاءة.
• الكفاءة: من خلال تجنب معلومات الدرجة الثانية (قلب مصفوفة هسيان)، تظل PANDA قابلة للتنفيذ حوسبيًا للمشكلات واسعة النطاق مع تحقيق معدلات تعقيد عينات ($\tilde{O}(\epsilon^{-3})$) تطابق أفضل النتائج المعروفة للإعدادات الأبسط ذات السياسة الواحدة.
• القابلية للتطبيق العملي: تم تصميم الطريقة للإعدادات القائمة على العينات، مما يجعلها قابلة للتطبيق مباشرة في سيناريوهات العالم الحقيقي مثل تصميم الحوافز، وتصميم الآليات، والتدريب الخصمي حيث تكون التوازنات التنافسية مركزية.

يخلص المؤلفون إلى أنه بينما يركز عملهم الحالي على MMZSMGs المنتظمة، فإن الإطار يقدم اتجاهًا واعدًا لتوسيع التحسين ثنائي المستوى ليشمل ألعاب min–max عامة وإعدادات أوسع متعددة الوكلاء.