⚡ electrical engineering

Fully Byzantine-Resilient Distributed Multi-Agent Q-Learning

تقترح هذه الورقة خوارزمية تعلم كيو (Q-learning) موزعة ومبتكرة تحقق تقارباً شبه مؤكد نحو دالات القيم المثلى في التعلم التعزيزي متعدد الوكلاء تحت هجمات الحافة البيزنطية، وذلك عبر استخدام آلية ترشيح قائمة على التكرار تستفيد من معلومات الجيران بمسافة قفزتين وشرط طوبولوجي قابل للتحقق في وقت حدودي.

المؤلفون الأصليون: Haejoon Lee, Dimitra Panagou

نُشر 2026-04-06

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Haejoon Lee, Dimitra Panagou

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

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

ومع ذلك، هناك مشكلة: هناك مخرب يتسلل في الشبكة.

هذا المخرب لا يحاول اختراق عقول الروبوتات (الروبوتات نفسها صادقة وتتبع القواعد)، بل هو يعبث بالأسلاك وأجهزة اللاسلكي التي تربط بينهم. قد يقوم بـ:

إسقاط ملاحظة بحيث لا يسمعها الروبوت أبداً.
تغيير الأرقام الموجودة على الملاحظة (على سبيل المثال، تحويل "التكلفة: 5" إلى "التكلفة: 10,000").
إرسال ملاحظات مزيفة لإرباك المجموعة.

في عالم علوم الحاسوب، يسمى هذا هجوم الحافة البيزنطي (Byzantine Edge Attack).

الطريقة القديمة: "ثق ولكن تحقق (إلى حد ما)"

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

تخيل الأمر كأنها مجموعة من الأصدقاء يحاولون تخمين سعر سيارة. إذا صرخ أحد الأصدقاء قائلاً: "إنها تكلف مليار دولار!"، فقد تتجاهل المجموعة هذا الصوت الواحد. لكن هنا تكمن الخدعة: المخرب يمكنه همس أكاذيب مختلفة لأشخاص مختلفين.

إلى الروبوت (أ)، يهمس المخرب: "السعر هو 1 دولار".
إلى الروبوت (ب)، يهمس المخرب: "السعر هو 1,000,000 دولار".

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

الحل الجديد: "النميمة ذات الخطوتين"

ابتكر مؤلفا هذه الورقة البحثية، هيجون لي وديمي ترا باناغاو، استراتيجية ذكية جديدة تسمى FRQD-learning.

بدلاً من مجرد الاستماع إلى الجيران المباشرين، تستخدم الروبوتات نظام "النميمة ذات الخطوتين" (Two-Step Gossip). وإليك كيف يعمل، باستخدام تشبيه بسيط:

1. "التحقق المزدوج" عبر الترحيل

تخيل أنك الروبوت (أ). تريد معرفة سعر السيارة من الروبوت (ج).

الخطوة 1: يسأل الروبوت (أ) الروبوت (ب) (جار مباشر له): "ماذا سمعت من الروبوت (ج)؟"
الخطوة 2: يسأل الروبوت (أ) أيضاً الروبوت (د) (جار آخر له): "ماذا سمعت من الروبوت (ج)؟"

إذا قال كل من الروبوت (ب) والروبوت (د) أن "الروبوت (ج) قال 50,000 دولار"، فإن الروبوت (أ) يعرف بالتأكيد أن 50,000 دولار هي الحقيقة.

2. "كاشف الكذب"

ماذا لو كان المخرب يعبث بالسلك بين الروبوت (ب) والروبوت (أ)؟

يخبر المخرب الروبوت (أ): "الروبوت (ج) قال 1,000,000 دولار!"
لكن الروبوت (د) (المتصل بـ (ج) عبر سلك آخر آمن) يخبر الروبوت (أ): "الروبوت (ج) قال 50,000 دولار".

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

السر الكامن: "الجوار المتكرر"

لكي يعمل هذا النظام، يجب ترتيب الروبوتات بطريقة محددة. تقدم الورقة مفهوماً يسمى "(r, r') - redundancy" (التكرار r, r').

فكر في الأمر كأنه شبكة اجتماعية:

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

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

النتيجة

في عمليات المحاكاة الحاسوبية الخاصة بهم:

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

الملخص

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

إليك ملخص تقني مفصل لورقة البحث بعنوان "التعلم بـ Q الموزع متعدد الوكلاء المقاوم للخطأ البيزنطي بالكامل" (Fully Byzantine-Resilient Distributed Multi-Agent Q-Learning) من تأليف هيجون لي وديميرا باناجو.

1. بيان المشكلة

تتناول الورقة تحدي التعلم المعزز متعدد الوكلاء الموزع (MARL) في ظل وجود هجمات معادية. وتحديداً، تركز على شبكة من الوكلاء الذين يتعاونون لتعلم دوال القيم المثلى (قيم Q) لهدف عالمي مشترك (تقليل متوسط التكاليف المحلية) عبر شبكة اتصالات.

نموذج التهديد: يعتبر المؤلفون هجمات الحواف البيزنطية (Byzantine edge attacks). وخلافاً لهجمات العقد حيث يتم اختراق الوكيل نفسه، يستهدف المهاجم هنا روابط الاتصال. يسمح هجوم الحواف البيزنطي بإجمالي $F$ من الهجمات للمهاجم بتغيير أو إسقاط الرسائل تعسفياً على ما لا يزيد عن $F$ من الحواف في كل جولة اتصال.
قصور الأعمال السابقة: خوارزميات التعلم المعزز متعدد الوكلاء المقاومة السابقة (مثل تلك التي تستخدم الإجماع القوي أو تصفية القيم المتطرفة) تضمن عموماً التقارب إلى دوال قيم قريبة من المثالية. وغالباً ما تفشل في الوصول إلى الحل الأمثل الدقيق لأن تصفية المعلومات غير المتماثلة تُدخل تحيزات، أو تتطلب شروطاً طوبولوجية مقيدة (مثل متانة $(2F+1)$ ) والتي يصعب التحقق منها حسابياً (وهي مسألة من فئة co-NP-complete).
الهدف: تصميم خوارزمية لامركزية حيث يحقق الوكلاء تقارباً شبه مؤكد إلى دوال القيم المثلى الدقيقة رغم هجمات الحواف البيزنطية بإجمالي $F$ ، دون الحاجة إلى منسق مركزي موثوق.

2. المنهجية: تعلم FRQD (التعلم بـ Q الموزع المقاوم للخطأ بالكامل)

يقترح المؤلفون خوارزمية جديدة تسمى FRQD-learning، والتي تدمج تعلم Q القائم على الإجماع القياسي مع آلية تصفية قائمة على التكرار.

أ. الآلية الجوهرية: التكرار عبر قفزتين (Two-Hop Redundancy)

خلافاً للطرق التقليدية التي تصفي القيم المتطرفة من الجيران المباشرين (مما يكسر التماثل)، يستخدم FRQD معلومات الجيران عبر قفزتين للتحقق من صحة الرسائل.

الجولة الأولى (التبادل المباشر): يبث الوكلاء قيم Q الحالية الخاصة بهم إلى الجيران المباشرين.
الجولة الثانية (الترحيل والتحقق): يقوم الوكلاء بترحيل قيم Q التي تلقوها من جيرانهم إلى جيرانهم أنفسهم.
منطق التصفية:
- الخطوة 1: يتجاهل الوكيل أي رسالة يظهر فيها فهرس المرسل أكثر من مرة (لاكتشاف التكرار أو التزوير الفوري).
- الخطوة 2: يجمع الوكيل القيم المرحلة من جيران القفزة الثانية. يقوم الوكيل بعدّ مرات ظهور كل قيمة Q فريدة تم استلامها لجار محدد $k$ .
- العتبة: تعتبر القيمة الخاصة بالجار $k$ موثوقة ويتم تضمينها في مجموعة التحديث $P_i(t)$ فقط إذا ظهرت $3F + 1$ مرة على الأقل.
- التعليل: في ظل هجوم حافة بيزنطي بإجمالي $F$ ، يمكن أن تصل $3F$ قيمة فاسدة كحد أقصى إلى الوكيل فيما يتعلق بجار محدد (التمهيد 2). لذلك، فإن أي قيمة تظهر $\ge 3F+1$ مرة يجب أن تكون هي القيمة الحقيقية.

ب. الشرط الطوبولوجي: التكرار $(r, r')$

يعتمد تقارب FRQD على خاصية رسومية جديدة تسمى التكرار $(r, r')$ .

التعريف: يكون الرسم البياني $G(t)$ $G (t)$ مكرراً $(r, r')$ $(r, r^{'})$ إذا كان:
1. رسمه البياني ذو الـ $r$ -قفزة ثنائية (حيث توجد حافة بين $i$ و $j$ إذا كانا يتشاركان في $r$ من الجيران المشتركين على الأقل) متصلاً.
2. لأي زوج من الوكلاء $(i, j)$ غير متصلين في الرسم البياني ذو الـ $r$ -قفزة ثنائية، فإنهما يتشاركان في $r'$ من الجيران على الأكثر.
الأهمية: يضمن هذا الشرط أنه لأي زوج متصل في رسم الاتصال الفعال، يوجد تكرار كافٍ عبر المسارات المتعددة لتصفية الهجمات، مع منع المهاجم من خلق تدفقات معلومات غير متماثلة من شأنها أن تسبب تحيزاً للإجماع.
المتطلب المحدد: تثبت الورقة أنه إذا كان الرسم البياني مكرراً $(6F+1, 0)$ ، فإن الخوارزمية تتقارب نحو الحل الأمثل.

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

الابتكار الخوارزمي: تقديم FRQD-learning، وهو أول خوارزمية تعلم Q موزعة تضمن التقارب شبه المؤكد إلى دوال القيم المثلى الدقيقة تحت هجمات الحواف البيزنطية، دون افتراضات هيكلية على قيم Q.
شرط طوبولوجي جديد: تعريف التكرار $(r, r')$ . هذا يحل محل شرط المتانة $(2F+1)$ $(2 F + 1)$ المستخدم سابقاً.
- الميزة الحسابية: يمكن التحقق من التكرار $(r, r')$ في وقت حدودي ( $O(n^3)$ )، بينما التحقق من متانة $(2F+1)$ هو مسألة من فئة co-NP-complete. وهذا يجعل النهج قابلاً للتوسع في الشبكات الكبيرة.
البناء المنهجي: قدمت الورقة طريقة بنائية (الافتراض 1) لبناء رسوم بيانية مكررة $(r, r')$ بكفاءة.
الإثبات النظري: أثبتت الورقة أنه تحت شرط التكرار $(6F+1, 0)$ ، فإن قاعدة تحديث FRQD مكافئة رياضياً لتشغيل تعلم QD القياسي على رسم بياني متصل وغير موجه، مما يجعلها ترث ضمانات التقارب من خوارزمية QD الأصلية.

4. النتائج والتحقق

تحقق المؤلفون من نهجهم من خلال عمليات محاكاة تضمنت 10 وكلاء و6 مهام متتالية (مشكلة تخصيص الروبوتات).

الإعداد:
- المرجع (Oracle): تعلم QD القياسي (بدون هجوم) يعمل كالحقيقة الأرضية.
- الأساس (Baseline): طريقة سابقة لتعلم Q المقاوم (من [22]، [24]) التي تصفي القيم المتطرفة.
- الهجوم: هجوم حافة بيزنطي بإجمالي $F=1$ ، حيث يقوم المهاجم بحقن قيم Q متطرفة (مثلاً 10,000) في الحواف المخترقة.
النتائج:
- التقارب: تقاربت خوارزمية FRQD بشكل شبه مؤكد إلى قيم Q المثلى الدقيقة والسياسات، مطابقةً المرجع (Oracle).
- فشل الأساس: فشلت خوارزمية الأساس في التقارب إلى الحل الأمثل؛ حيث تقاربت إلى جوار الحل الأمثل ولكنها اختارت سياسات غير صحيحة لعدة حالات (مثل الحالات 1، 4، 5، و6).
- الجدول I: أظهر صراحةً أن FRQD حدد نفس أزواج الروبوتات المثلى مثل المرجع، بينما انحرف الأساس عنها بشكل كبير.

5. الأهمية

يمثل هذا العمل تقدماً نظرياً وعملياً كبيراً في التعلم الموزع المقاوم:

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

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