🤖 machine learning

Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation

تقترح هذه الورقة أول خوارزميات مثبتة الكفاءة في البيانات للألعاب الماركوفية المتينة توزيعياً ذات فضاءات الحالات الكبيرة باستخدام التقريب الدالي الخطي، والتي نجحت في كسر لعنة تعدد الوكلاء في كل من الإعدادات التوليدية والإعدادات التفاعلية عبر الإنترنت المقترحة حديثاً.

المؤلفون الأصليون: Jingchu Gai, Laixi Shi

نُشر 2026-05-06

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Jingchu Gai, Laixi Shi

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل مجموعة من الأصدقاء يحاولون التنقل معاً عبر متاهة ضخمة ومتغيرة. هذا هو عالم التعلم المعزز متعدد الوكلاء (Multi-Agent Reinforcement Learning - MARL). كل صديق (وكيل) يريد الوصول إلى المخرج، لكن المتاهة تتغير قليلاً في كل مرة يخطون فيها خطوة، وهم لا يعرفون بالضبط كيف ستتغير.

يتناول البحث الذي قدمته مشكلتين كبيرتين في هذا السيناريو:

"لعنة تعدد الوكلاء" (The Curse of Multiagency): مع إضافة المزيد من الأصدقاء إلى المجموعة، ينفجر عدد الطرق الممكنة التي يمكنهم بها التحرك معاً. الأمر يشبه محاولة التنبؤ بنتيجة لعبة شطرنج حيث يمتلك كل لاعب مليون حركة مختلفة، وعليك حساب كل تلك التوليفات. وهذا يجعل التعلم بطيئاً للغاية ويستهلك كميات هائلة من البيانات.
مشكلة "المتانة" (Robustness): ماذا لو لم تكن المتاهة تتغير عشوائياً فحسب، بل كانت تحاول بنشاط خداع المجموعة؟ أو ماذا لو كانت الخريطة التي أُعطيت لهم خاطئة قليلاً؟ تفشل طرق التعلم القياسية هنا لأنها تفترض أن العالم هو تماماً كما تم وصفه.

إليك كيف قام المؤلفون بـ "ترويض" هذه اللعنات باستخدام مجموعة جديدة من الأدوات.

1. المشكلة: متغيرات كثيرة جداً، وغموض شديد

في العالم الحقيقي (مثل السيارات ذاتية القيادة أو أسراب الطائرات بدون طيار)، تكون "مساحة الحالة" (عدد المواقف الممكنة) ضخمة، وغالباً ما تكون لانهائية. لا يمكنك ببساطة إعداد قائمة بكل سيناريو ممكن (نهج "جدولي") لأن القائمة ستكون أطول من عمر الكون.

علاوة على على ذلك، إذا كان لديك 10 وكلاء، فإن عدد الأفعال المشتركة هو حاصل ضرب أفعالهم الفردية. إذا كان لكل منهم 10 حركات، فإن 10 وكلاء يعني $10^{10}$ من التوليفات. هذه هي "لعنة تعدد الوكلاء".

2. الحل: التقريب الدالي الخطي (طريقة "الرسم التخطيطي")

بدلاً من حفظ كل تفصيل في المتاهة، يقترح المؤلفون استخدام التقريب الدالي الخطي (Linear Function Approximation - LFA).

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

3. الابتكار: كسر اللعنة

كانت الطرق السابقة قادرة على التعامل مع "المتاهة اللانهائية" (مساحة حالة كبيرة) أو "الأصدقاء الكثر" (تعدد الوكلاء)، ولكن ليس كليهما معاً دون المعاناة من اللعنة.

طوّر المؤلفون خوارزميتين جديدتين تكسران هذه اللعنة:

أ. إعداد "النموذج التوليدي" (المحاكي)

السيناريو: تخيل أن الأصدقاء لديهم محاكي سحري. يمكنهم سؤال المحاكي: "ماذا يحدث إذا قفزنا جميعاً إلى اليسار؟" ويحصلون على إجابة فورية دون الحاجة للقفز فعلياً.
الحيلة: بما أنهم لا يستطيعون السؤال عن كل قفزة ممكنة في متاهة لانهائية، فإنهم يستخدمون "منخلاً" رياضياً. يختارون عينة صغيرة ومختارة بعناية من القفزات التي تمثل المتاهة بأكملها.
النتيجة: يثبتون أنه من خلال أخذ هذه العينة الصغيرة والذكية، يمكنهم تعلم استراتيجية تعمل للمتاهة اللانهائية بأكملها، وأن الوقت الذي يستغرقه الأمر لا ينفجر مع إضافة المزيد من الأصدقاء.

ب. الإعداد "التفاعلي عبر الإنترنت" (العالم الحقيقي)

السيناريو: هذه هي الحالة الأصعب والأكثر واقعية. لا يوجد محاكي سحري. يجب على الأصدقاء السير فعلياً عبر المتاهة.
التحول: في هذه النسخة، قد تكون المتاهة تحاول بنشاط أن تكون "السيناريو الأسوأ" بالنسبة لهم (بيئة معادية).
الاستراتيجية الجديدة (أخذ العينات الهجين):
- عادةً، يتعلم الوكلاء من خلال التفاؤل ("أظن أن هذا المسار آمن!").
- يقدم هؤلاء المؤلفون طبقة تشاؤمية (Pessimistic). يتخيلون نسخة "الأسوأ" من المتاهة بناءً على تخميناتهم الحالية.
- الخطوة الهجينة: في الجزء الأول من رحلتهم، يتصرفون كما لو كانوا في هذه المتاهة "الأسوأ" (للاستعداد للأسوأ). ولكن في الخطوة الأخيرة تماماً، يعودون للعمل بالمتاهة "الطبيعية" لجمع البيانات.
- لماذا ينجح ذلك: يسمح لهم هذا بتقدير قواعد "الحالة الأسوأ" دون الحاجة فعلياً لرؤية الحالة الأسوأ الحقيقية (التي لا يمكنهم معرفتها بعد). الأمر يشبه التدرب على العاصفة عبر محاكاة الأمطار الغزيرة، ولكنك تتحقق من مظلتك فقط في الرذاذ الفعلي لترى مدى فعاليتها.

4. "مجموعة عدم اليقين التصورية"

يستخدم البحث طريقة محددة لتعريف "عدم اليقين". بدلاً من القول إن "المتاهة قد تتغير بنسبة 5%"، يستخدمون مسافة التباين الكلي (Total Variation Distance).

التشبيه: تخيل أنك تلعب لعبة قد تكون قواعدها مختلفة قليلاً. بدلاً من التخمين بالضبط كيف تغيرت، تفترض أن القواعد يمكن أن تكون أي تغيير ضمن "نصف قطر" معين من القواعد الأصلية. تجد الخوارزمية استراتيجية تعمل حتى لو انتقلت القواعد إلى حافة ذلك النصف قطر.

ملخص الإنجازات

يدعي البحث أنه الأول الذي يقدم ضماناً رياضياً بأن:

يمكنك تعلم استراتيجيات متينة في بيئات لانهائية.
يمكنك القيام بذلك مع وكلاء كثر دون أن ينفجر وقت التعلم (كسر لعنة تعدد الوكلاء).
هذا يعمل في كل من أوضاع "المحاكي" والأنماط "التفاعلية في العالم الحقيقي".

إنهم يحققون ذلك من خلال الجمع بين التقريب الدالي الخطي (تبسيط العالم اللانهائي إلى قواعد قليلة) وتقنية أخذ العينات الهجينة الذكية التي توازن بين التفاؤل (تعلم القواعد) والتشاؤم (الاستعداد للأسوأ).

ما لا يدعيه البحث:

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

ملخص تقني: ترويض لعنات تعدد الوكلاء في ألعاب ماركوف القوية ذات مساحات الحالة الكبيرة عبر التقريب الخطي للدوال

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

يتناول هذا العمل تحدي التعلم المعزز متعدد الوكلاء المتسم بالمتانة التوزيعية (Distributionally Robust MARL) في الإعدادات ذات مساحات الحالة الكبيرة أو اللانهائية. يركز المؤلفون على ألعاب ماركوف الخطية القوية (Robust Linear Markov Games - R-LMGs)، والتي تجمع بين صعوبتين حرجتين:

المتانة (Robustness): يجب على الوكلاء تحسين الأداء في أسوأ الحالات عندما ينحرف البيئة عن النموذج الاسمي ضمن مجموعة عدم يقين محددة (المعرفة تحديداً بمسافة التباين الكلي - Total Variation distance).
القابلية للتوسع (لعنة تعدد الوكلاء - The Curse of Multiagency): في التعلم المعزز متعدد الوكلاء القياسي (MARL)، تنمو مساحة العمل المشتركة للوكلاء بشكل أسي مع عدد الوكلاء ( $n$ )، مما يؤدي إلى تعقيد العينات الذي يتناسب أسياً مع $n$ . ويتفاقم هذا الأمر عندما تكون مساحات الحالة كبيرة أو لانهائية، مما يجعل الطرق الجدولية (Tabular methods) غير مجدية.

بينما تقتقتصر الخوارزميات الفعالة من حيث إثبات الكفاءة لألعاب ماركوف القوية (RMGs) الموجودة حالياً على الإعدادات الجدولية (مساحات حالة وأفعال محدودة)، والعمل الوحيد السابق على التقريب الخ funzionalità الخطي (LFA) لألعاب RMGs يعتمد على افتراضات مقيدة (القيمة الدنيا المتلاشية) ولا يزال يعاني من لعنة تعدد الوكلاء، تطرح هذه الورقة السؤال التالي: هل يمكن ترويض لعنة تعدد الوكلاء في ألعاب ماركوف القوية ذات مساحات الحالة واسعة النطاق؟

2. المنهجية

تقترح الورقة خوارزميات فعالة من حيث البيانات بشكل مثبت لألعاب R-LMGs تحت آليتين متميزتين لجمع البيانات: إعداد النموذج التوليدي (Generative Model) وإعداد التفاعل عبر الإنترنت (Online Interactive) المقترح حديثاً. يستخدم كلا الإعدادين التقريب الخطي المستقل لكل وكيل (Independent Per-Agent LFA)، حيث يتم نمذجة دوال الانتقال والمكافأة لكل وكيل كدوال خطية لمتجه سمات $\phi(s, a_i)$ ، بشكل مستقل عن أفعال الوكلاء الآخرين.

2.1 إعداد النموذج التوليدي

في هذا الإعداد، تمتلك الخوارزمية إمكانية الوصول إلى محاكي يمكنه توليد عينات من نواة الانتقال الاسمية $P^0$ لأي زوج من الحالة والفعل.

الخوارزمية: L-Robust-Q-FTRL.
الابتكار الرئيسي (الاختزال من اللانهائي إلى المنتهي): على عكس الطرق الجدولية التي تتطلب أخذ عينات شاملة، يقوم المؤلفون ببناء مجموعة دعم منتهية من أزواج الحالة والفعل ( $Y_i$ ) باستخدام توزيع $\rho_i$ مشتق من Lemma 1 (بناءً على هندسة فضاء السمات). يسمح هذا بأخذ عينات فقط من مجموعة فرعية منتهية بحجم $O(d^2)$ مع ضمان تغطية مساحة الحالة بأكملها (التي قد تكون لانهائية) عبر انحدار ريدج (Ridge Regression).
الآلية: تقوم الخوارزمية بعملية تراجع عكسي (Backward recursion). في كل تكرار، تأخذ عينات من المجموعة المنتهية المنشأة، وتقدر النموذج الاسمي (المكافآت والانتقالات) عبر انحدار ريدج، وتحدث دالة Q القوية باستخدام الصيغة المزدوجة لمعادلة بل مان القوية. وهي تستخدم استراتيجية "اتبع القائد المنتظم" (Follow-the-Regularized-Leader - FTRL) لتحديث السياسات.

2.2 إعداد التفاعل عبر الإنترنت

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

الخوارزمية: Online-L-Robust-Q-FTRL.
الابتكار الرئيسي (أخذ العينات الهجين والتقديرات المتشائمة):
- تقريب الخصم: بما أن نواة الانتقال الأسوأ حالة الحقيقية غير معروفة، فلا يمكن للخوارزمية أخذ عينات منها مباشرة. بدلاً من ذلك، تقدم سلسلة من تقديرات القيمة المتشائمة القوية. تُستخدم هذه التقديرات للاستعلام من "بيئة خصم تقريبية" (Definition 1) داخل مجموعة عدم اليقين.
- استراتيجية أخذ العينات الهجين: للحفاظ على صحة تقدير النموذج الخطي (الذي ينطبق فقط على النوا kernels الاسمية)، تستخدم الخوارزمية مخطط أخذ عينات هجين. في الخطوات $h-1$ الأولى من المسار، يتفاعل الوكلاء مع البيئة الخصم التقريبية (باستخدام التقديرات المتشائمة). وفي الخطوة النهائية $h$ ، ينتقلون إلى أخذ العينات من النوا الاسمية. هذا يحافظ على توزيع إشغال الحالة-الفعل الناجم عن الديناميكيات الأسوأ حالة حتى الخطوة $h-1$ مع ضمان أن بيانات الانتقال النهائية تأتي من النموذج الاسمي القابل للتقريب خطياً.
- التقديرات المزدوجة: تحافظ الخوارزمية على كل من تقديرات القيمة المتفائلة (لتحديث السياسة) والتقديرات المتشائمة (لتوجيه أخذ العينات الخصمية)، وهو ما يعد خروجاً عن نماذج ماركوف الخطية القياسية التي تعتمد عادةً على التفاؤل فقط.

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

كسر لعنة تعدد الوكلاء في مساحات الحالة الكبيرة: توفر الورقة أول خوارزميات فعالة من حيث العينات لألعاب R-LMGs ذات مساحات الحالة الكبيرة (أو اللانهائية) التي تكسر لعنة تعدد الوكلاء. تعتمد تعقيد العينات وحدود الندم (Regret bounds) بشكل متعدد الحدود على بُعد السمات $d$ والحد الأقصى لحجم فضاء الفعل الفردي $\max_i A_i$ ، بدلاً من مساحة الفعل المشتركة $\prod A_i$ .
ضمانات النموذج التوليدي: في إعداد النموذج التوليدي، تحقق الخوارزمية $\epsilon$ -approximate Coarse Correlated Equilibrium (CCE) بتعقيد عينات $\tilde{O}(H^9 d^3 / \epsilon^4)$ . هذه هي أول ضمانة من هذا النوع لألعاب R-LMGs تحت إعداد النموذج التوليدي، بغض النظر عن صياغة مجموعة عدم اليقين.
بروتوكول التفاعل عبر الإنترنت: يقترح المؤلفون بروتوكولاً عملياً عبر الإنترنت حيث يمكن للوكلاء أخذ عينات من أنوية الانتقال داخل مجموعة عدم اليقين (بيئات خصم تقريبية). يثبتون أن خوارزميتهم تحقق ندماً دون خطي قدره $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$ .
الجدة التقنية:
- الاختزال من اللانهائي إلى المنتهي: طريقة لأخذ عينات من مجموعة فرعية منتهية للتعميم على مساحات الحالة اللانهائية في السياقات القوية.
- أخذ العينات الهجين: آلية مبتكرة لتقدير النموذج الاسمي مع الحفاظ على توزيع إشغال البيئة الخصمية، مما يتغلب على عدم الخطية في مجموعة عدم اليقين.
- الثنائية المتشائمة-المتفائلة: تقديم تقديرات القيمة المتشائمة لتقريب البيئة الخصمية في غياب القيم القوية الحقيقية.

4. النتائج والضمانات النظرية

النموذج التوليدي (Theorem 2): تنتج الخوارزمية $\epsilon$ -robust CCE باحتمالية $1-\delta$ باستخدام $N_{all} \ge O(H^9 d^3 / \epsilon^4)$ من العينات. في الاختزال الجدولي ( $d = S \max A_i$ )، يعطي هذا تعقيداً قدره $\tilde{O}(H^9 S^3 (\max A_i)^3 / \epsilon^4)$ ، وهو ما يمثل تعقيداً متعدد الحدود في جميع المعاملات، على النقييد مع الاعتماد الأسي في طرق Robust الجدولية السابقة.
إعداد عبر الإنترنت (Theorem 3): تحقق الخوارما خوارزمية حد ندم قدره $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$ . إذا كان عدد الحلقات $T$ يحقق $T > H^4 d^2 (\max_i A_i)^2 / \epsilon^2$ ، فإن المخرج هو $\epsilon$ -robust CCE.
المقارنة: تحسن النتائج بشكل كبير العمل الوحيد الموجود (Zheng and Lin, 2025)، الذي تطلب افتراض "القيمة الدنيا المتلاشية" المقيد وعانى من لعنة تعدد الوكلاء ( $d_{curse} = S \prod A_i$ ). تزيل الطريقة المقترحة هذه القيود وتحقق اعتماداً متعدد الحدود على أعداد الوكلاء.

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

يدعي المؤلفون أن هذا العمل يوفر أول خوارزميات فعالة من حيث العينات لألعاب ماركوف الخطية القوية ذات مساحات الحالة الكبيرة (أو اللانهائية) التي تنجح في التغلب على لعنة تعدد الوكلاء.

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

تخلص الورقة إلى أن استراتيجية أخذ العينات الهجينة واستخدام التقديرات المتشائمة هي مساهمات تقنية رئيسية قد تكون ذات أهمية مستقلة للأبحاث المستقبلية في التعلم المعزز القوي.