Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction

فيما يلي ملخص تقني مفصل للورقة البحثية بعنوان "Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction" (المقبولة في ICLR 2026).

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

تتناول الورقة تحدي التعلم المعزز متعدد الوكلاء المتين توزيعياً (DR-MARL) في البيئات عبر الإنترنت (online).

• السياق: غالباً ما يفشل التعلم المعزز متعدد الوكلاء القياسي (MARL) في النشر الواقعي بسبب فجوة "من المحاكاة إلى الواقع" (Sim-to-Real)، حيث تؤدي عدم المطابقة في النماذج (مثل الضجيج، أو الهجمات العدائية، أو الديناميكيات غير المفسرة) إلى فشل السياسات التي تم تدريبها في المحاكاة.
• الألعاب الماركوفية المتينة توزيعياً (DRMGs): يصيغ المؤلفون البيئة كـ "لعبة ماركوف" حيث يمتلك كل وكيل $i$ مجموعة عدم يقين $\mathcal{P}_i$ من نواة الانتقال (transition kernels) المحتملة المتمحورة حول نواة اسمية $P^\star$. الهدف هو إيجاد سياسة تعظم العائد المتوقع في الحالة الأسوأ عبر مجموعة عدم اليقين هذه.
• الفجوة: تعتمد أبحاث DRMG الحالية على النماذج التوليدية (محاكيات مثالية) أو مجموعات البيانات غير المتصلة (offline) (بيانات ضخمة جُمعت مسبقاً). هذه الافتراضات غير واقعية للتطبيقات عالية المخاطر (مثل القيادة الذاتية، أو الرعاية الصحية) حيث يجب على الوكلاء التعلم مباشرة من التفاعل المتسلسل مع بيئة مجهولة ومشوبة بالضجيج دون بيانات سابقة.
• الهدف: تصميم خوارزمية تعلم عبر الإنترنت (online learning) لـ DRMGs تتعلم مباشرة من التفاعل، وتوفر ضمانات نظرية لـ "الندم" (regret guarantees)، وتتعامل مع الألعاب ذات المجموع العام (general-sum games) باستخدام مجموعات عدم يقين قائمة على مسافة التباين الكلي (TV) وتباعد كولباك-لايبلر (KL).

2. المنهجية: f-MORNAVI

يقترح المؤلفون خوارزمية Multiplayer Optimistic Robust Nash Value Iteration (f-MORNAVI)، وهي خوارزمية ميتا (meta-algorithm) تعتمد على النموذج ومصممة للألعاب الماركوفية ذات الأفق الزمني المحدود والحلقات المتكررة (episodic).

المكونات الجوهرية:

1. التقدير القائم على النموذج (Model-Based Estimation):

   • يحافظ الوكلاء على تقدير تجريبي لنواة الانتقال الاسمية $\hat{P}^k$ بناءً على بيانات التفاعل التاريخية $D$.
   • تستخدم الخوارزمية نهجاً قائماً على النموذج لأن المقدرات التي لا تعتمد على النموذج (model-free) تكون منحازة أو غير فعالة في استهلاك العينات لـ DRMGs بسبب عدم خطية مؤثر التوقع في الحالة الأسوأ.

2. التخطيط المتين المتفائل (مبدأ UCB):

   • تبني الخوارزمية حداً علوياً للثقة (UCB) على دالة القيمة المتينة لتشجيع الاستكشاف.
   • تحافظ على تقديرين لدالة Q المتينة:
     • التقدير المتفائل ($\bar{Q}$): $r + \sigma_{\hat{\mathcal{P}}}[\bar{V}] + \beta$
     • التقدير المتشائم ($\underline{Q}$): $r + \sigma_{\hat{\mathcal{P}}}[\underline{V}] - \beta$
   • هنا، $\sigma_{\mathcal{P}}[V] = \inf_{P \in \mathcal{P}} \mathbb{E}_P[V]$ هي دالة الدعم التي تمثل التوقع في الحالة الأسوأ.
   • حد الإضافة ($\beta$): يُضاف حد مكافأة يعتمد على البيانات لضمان أن التقدير المتفائل هو حد علوي للقيمة المتينة الحقيقية باحتمالية عالية. بناء $\beta$ مصمم خصيصاً لهندسة مجموعة عدم اليقين (TV أو KL).

3. حساب التوازن (Equilibrium Computation):

   • في كل خطوة، تحل الخوارزمية لعبة مصفوفة باستخدام قيم Q المتفائلة المقدرة لإيجاد سياسة التوازن ($\pi^k$).
   • يدعم الإطار عملياً كل من توازن ناش (NE)، وتوازن الارتباط الخشن (CCE)، والتوازن المرتبط (CE).
   • ملاحظة: بينما يعد إيجاد NE مسأًلة من نوع PPAD-hard، تركز الورقة على تعقيد العينات وتفترض أن إجراءات التوازن الفرعية قابلة للتنفيذ، على غرار أدبيات ألعاب ماركوف القياسية.

4. التعامل مع مجموعات عدم اليقين:

   • تباعد التباين الكلي (TV-Divergence): يتطلب افتراض "حالة الفشل" (Assumption 3) للتعامل مع إزاحة الدعم (حيث يكون لنواة الحالة الأسوأ دعم خارج نطاق النواة الاسمية).
   • تباعد كولباك-لايبلر (KL-Divergence): يتجنب طبيعياً مشكلات إزاحة الدعم لأن كرة KL تقع ضمن الدعم الاسمي.

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

أ. تحليل الصعوبة لـ Online DRMGs

تضع الورقة حدوداً دنيا أساسية تثبت الصعوبة المتأصلة في DRMGs عبر الإنترنت مقارنة بالبيئات التوليدية أو غير المتصلة (offline):

1. إزاحة الدعم (TV): إذا كانت مجموعة عدم اليقين تسمح بإزاحة الدعم (مثل مسافة TV)، فإن أي خوارزمية عبر الإنترنت ستعاني من ندم خطي $\Omega(K \cdot \min\{H, \prod A_i\})$ لأن الوكيل لا يمكنه تعلم انتقالات الحالة الأسوأ للحالات التي لم يتم زيارتها أبداً في النموذج الاسمي.
2. لعنة تعدد الوكلاء (بدون إزاحة الدعم): حتى بدون إزاحة الدعم (مثل تباعد KL)، تثبت الورقة حداً أدنى لـ minimax قدره $\Omega(\sqrt{K \prod A_i})$. هذا يوضح أن DRMGs عبر الإنترنت تعاني من "لعنة تعدد الوكلاء" (curse of multi-agency)، حيث يعتمد تعقيد العينات على حجم فضاء الفعل المشترك ($\prod A_i$)، على عكس ألعاب ماركوف غير المتينة التي يمكن للوكلاء فيها أحياناً كسر هذه اللعنة.

ب. الضمانات النظرية (حدود الندم)

يقدم المؤلفون أول حدود مثبتة للندم (regret bounds) لـ DRMGs عبر الإنترنت:

• تباعد التباين الكلي (TV): تحت افتراض حالة الفشل، يتم تحديد الندم بـ:
  $$\tilde{O}\left( \sqrt{\min\{\rho_{\min}^{-1}, H\} \cdot H^2 S K \prod_{i} A_i} \right)$$
• تباعد كولباك-لايبلر (KL): بدون افتراضات إضافية، يتم تحديد الندم بـ:
  $$\tilde{O}\left( \sqrt{H^4 \exp(2H^2) K S \prod_{i} A_i \cdot (\rho_{\min}^2 P^\star_{\min})^{-1}} \right)$$
  (ملاحظة: حد $\exp(H)$ متأصل في ثنائية التحسين المتين القائمة على KL).

ج. تعقيد العينات

باستخدام التحويل من "عبر الإنترنت إلى الدفعات" (online-to-batch conversion)، تستنتج الورقة تعقيد العينات لإيجاد توازن تقريبي بمقدار $\epsilon$:

• التباين الكلي (TV): $\tilde{O}(\epsilon^{-2} \min\{\rho_{\min}^{-1}, H\} H^3 S \prod A_i)$
• كولباك-لايبلر (KL): $\tilde{O}(\epsilon^{-2} H^5 \exp(2H^2) S \prod A_i (\rho_{\min}^2 P^\star_{\min})^{-1})$

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

4. النتائج والتجارب

• التحقق العددي: أجرى المؤلفون تجارب على نماذج DRMG صغيرة النطاق، سواء كانت تعاونية بالكامل أو ذات مجموع عام.
  • التقارب: نجحت خوارزمية f-MORNAVI في التقارب نحو التوازنات المتينة.
  • المتانة: عند الاختبار تحت مستويات متفاوتة من عدم يقين النموذج (لمحاكاة فجوة Sim-to-Real)، حافظت السياسات المتينة التي تعلمتها f-MORNAVI على أداء مستقر، بينما عانت النماذج المرجعية غير المتينة (مثل Nash Value Iteration القياسي) من تدهور كبير في الأداء مع زيادة عدم اليقين.
• المقارنة: تمت مقارنة النتائج النظرية بالأعمال السابقة (الجدول 1 في الورقة). تحقق الخوارزمية المقترحة تعقيدات مماثلة لأفضل الطرق التوليدية وغير المتصلة، رغم الصعوبة المضافة المتمثلة في الاستكشاف عبر الإنترنت.

5. الأهمية والأثر

• جسر بين النظرية والتطبيق: يعد هذا العمل الأول الذي يقدم ضمانات مثبتة للتعلم عبر الإنترنت (online) في DRMGs، متجاوزاً الافتراضات المقيدة للمحاكيات أو مجموعات البيانات غير المتصلة. إنه يوفر مساراً عملياً لنشر الأنظمة متعددة الوكلاء المتينة في بيئات واقعية غير مؤكدة.
• الحدود الأساسية: من خلال وضع الحدود الدنيا، توضح الورقة الصعوبة الجوهرية للمشكلة، وتحديداً تسلط الض الضوء على "لعنة تعدد الوكلاء" في الإعدادات المتينة. وهذا يشير إلى أنه في حالات DRMG العامة عبر الإنترنت، يبدو أن الاعتماد على حجم فضاء الفعل المشترك أمر لا مفر منه ما لم يتم استيفاء افتراضات هيكلية محددة.
• الإطار الخوارزمي: يوفر إطار f-MORNAVI نموذجاً مرناً للتعلم متعدد الوكلاء المتين الذي يمكن تكييفه مع مقاييس تباعد $f$ المختلفة، مما يوازن بين التفاؤل (للاستكشاف) والتشاؤم (للمتانة).

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