مُلَخَّص
نستكشف تحدّي تعلُّم التعزيز العميق متعدِّد الوكلاء في بيئاتٍ تنافسيّة جزئيًّا، حيث تواجه الأساليب التقليديّة صعوباتٍ في تعزيز التعاون المبنيّ على المعاملة بالمِثل. يتعلّم وكلاء LOLA وPOLA سياساتٍ تعاونيّة قائمة على المعاملة بالمِثل بالتفاضل خلال عددٍ محدود من خطوات تحديث الخصم المستقبلية. غير أنّ لهذه التقنيات قيدًا أساسيًّا: لاعتمادها على عددٍ قليل من خطوات التحسين، قد يستغلّها خصمٌ قادرٌ على إجراء مزيدٍ من التحديثات لتعظيم عائده. استجابةً لذلك، نقدّم نهجًا جديدًا نسمّيه تشكيل الاستجابة المثلى (BRS)، يُوظِّف خصمًا يُقارِب الاستجابة المثلى ويُشار إليه بـ"المُحَقِّق". ولِتكييف المُحَقِّق مع سياسة الوكيل في الألعاب المعقّدة، نقترح آليّة تكيُّف قابلةً للتفاضل ومُشْتَرَطةً بالحالة، تُيَسِّرها آليّة "طَرْح الأسئلة" لاستخلاص تمثيلٍ للوكيل انطلاقًا من سلوكه في حالاتٍ بيئيّة مُعيَّنة. وللتحقُّق تجريبيًّا من صحّة طريقتنا، نُبيِّن تفوُّق أدائها في مواجهة خصمٍ قائمٍ على بحث شجرة مونتِ كارلو (MCTS)، الذي يعمل كتقريبٍ للاستجابة المثلى في لعبة القطع النقديّة. يُوسِّع هذا العمل نطاق تطبيق تعلُّم التعزيز متعدِّد الوكلاء في البيئات التنافسيّة الجزئيّة، ويمهِّد مسارًا جديدًا نحو تحقيق رفاهيّة اجتماعيّة أفضل في الألعاب ذات المصلحة الجماعيّة.
مُقَدِّمَة
مكَّنَت خوارزميّات تعلُّم التعزيز متعدِّد الوكلاء من تحقيق أداءٍ مُتميِّز في ألعابٍ معقّدة وعالية الأبعاد مثل لعبة الغو (AlphaGo) وستاركرافت (AlphaStar). الهدف الأسمى من تعلُّم التعزيز هو تدريب وكلاء قادرين على مساعدة البشر في حلّ المشكلات الصعبة. ولا محالة، سيحتاج هؤلاء الوكلاء إلى الاندماج في سيناريوهاتٍ واقعيّة تتطلّب التفاعل مع البشر ووكلاء تعلُّمٍ آخرين. فعلى الرغم من تفوُّق التدريب متعدِّد الوكلاء في البيئات التعاونيّة أو التنافسيّة الخالصة، فإنّه كثيرًا ما يعجز عن اكتشاف تعاونٍ قائمٍ على المعاملة بالمثل في البيئات التنافسيّة الجزئيّة. ومثالٌ بارزٌ على ذلك فشل وكلاء MARL في تعلُّم سياساتٍ على غرار المعاملة بالمثل في معضلة السجين المتكرّرة (IPD)، وهو ما عالجته LOLA.
رغم الطابع التمثيلي لمعضلات المصلحة الجماعيّة مثل معضلة السجين، تتكرّر هذه الإشكالات في المجتمع والطبيعة. تخيَّل سيناريو تحاول فيه دولتان (وكلاء) تعظيم إنتاجهما الصناعي مع الإبقاء على مناخ عملٍ يحدّ من الانبعاثات الكربونيّة. من جهة، ترغب كلّ دولة في التزام الدولة الأخرى بتعهّداتها البيئيّة؛ ومن جهةٍ أخرى، يَغريهما إطلاقُ مزيدٍ من الكربون لتحصيل عوائد صناعيّة أكبر. ستُرغِم معاهدةٌ فعّالة كلّ دولة—بواسطة التهديد بالعقوبات—على التزام حدود الانبعاثات المتّفق عليها. وإذا أخفق الوكلاء في تطوير استراتيجياتٍ كالمعاملة بالمثل، فالأرجح أن ينتهي الأمر بتصعيدٍ مُتبادَلٍ مؤسفٍ في استهلاك الطاقة والانبعاثات.
قدَّمت LOLA خوارزميّة "التعلُّم مع الوعي بتعلُّم الخصم"، ونجحت في إظهار سلوك المعاملة بالمثل في IPD عبر التفاضل خلال خطوة تحديثٍ واحدة يتّخذها الخصم. وبالبناء على ذلك، قدَّمت POLA أسلوب "الوعي بتعلُّم الخصم التقاربي"، الذي يُقرِّب تحديثات سياسة الخصم على نحوٍ مُقيَّد ويُمكِّن من تدريب الشبكات العصبيّة في ألعابٍ أكثر تعقيدًا، مثل لعبة القطع النقديّة. وبحسب علمنا، تُعدّ POLA النهج الوحيد الذي يدرِّب بصورةٍ موثوقة وكلاء يَلتزمون تعاونًا قائمًا على المعاملة بالمثل في هذه اللعبة.
وعلى الرغم من نجاحها في لعبة القطع النقديّة، فإنّ لـPOLA حدودًا واضحة. إذ يقتصر استشرافها لتعلُّم الخصم على عددٍ محدود من خطوات التحديث المستقبلية، ما يجعلها عرضةً للاستغلال من قِبل خصوم يمكنهم إجراء مزيدٍ من التحسين. تُظهر تحليلاتُنا أنّ خصمًا يُدرِّب نفسه خصّيصًا لتعظيم عائده ضدّ سياسةٍ ثابتة مُدرَّبة بهذه الطريقة يستطيع استغلال الوكيل القائم على LOLA/POLA. كما أنّ هذه القيود تُعيق قابلية التوسّع حين يكون الخصم شبكةً عصبيّةً معقّدة تتطلّب العديد من خطوات التحسين لمحاكاة تعلّمها الفعلي.
في هذه الورقة نُقدِّم نهجًا جديدًا نسمّيه تشكيل الاستجابة المثلى. يرتكز على بناء خصمٍ يُقارِب سياسة الاستجابة المثلى ضدّ وكيلٍ معيّن، نُسمّيه "المُحَقِّق". يُوضِّح [fig:cobalt] الإطار العام: نُدرِّب المُحَقِّق ضدّ مجموعةٍ متنوّعة من وكلاء التدريب، ثم نُدرِّب الوكيل بالتفاضل خلال المُحَقِّق. وعلى خلاف LOLA وPOLA اللتين تفترضان عددًا يسيرًا من خطوات التحسين المستقبلية للخصم، يفترض أسلوبُنا أن يُنتِج المُحَقِّق استجابةً مُثلى للوكيل الحالي عبر تكييفٍ ديناميّ لسياسته.
نختبر طريقتنا في معضلة السجين المتكرّرة ولعبة القطع النقديّة. وبما أنّ تقييم الوكيل يتوقّف على قدرته في مواجهة خصمٍ مُجيد الاستجابة، فإنّ المقارنة المنطقيّة تكون مقابل خصمٍ يستجيب بأفضل شكلٍ ممكن، وهو ما نُقرِّبه عبر بحث شجرة مونتِ كارلو. نُظهر أنّه بينما لا يتعاون MCTS تعاونًا كاملًا مع وكلاء LOLA/POLA، فإنّه يتعاون بالكامل مع وكلاء تشكيل الاستجابة المثلى.
المُسَاهَمَات الرَّئِيسِيَّة: نُلخِّص مساهماتنا فيما يلي:
نُبيّن أنّ خصمًا مُحسَّنًا بواسطة بحث شجرة مونتِ كارلو لا يتعاون مع وكلاء LOLA/POLA، بل يستغلّهم لتحصيل عوائد أعلى من عائد التعاون الكامل.
لتجاوز هذا الضعف، نُقدِّم أسلوب تشكيل الاستجابة المثلى، الذي يُدرِّب وكيلًا بالتفاضل عبر خصمٍ يُحاكي الاستجابة المثلى ("المُحَقِّق"). ونُبرهن تجريبيًّا أنّ وكلاء BRS يتعاونون تعاونًا كاملًا، كما هو مُبيَّن في [fig:coin_main_compare].
نقترح كذلك آليّة تكيُّف للمُحَقِّق قابلةً للتفاضل ومُشْتَرَطةً بالحالة، تُمكِّنه من التكيُّف مع سياسة الوكيل.
الخَلْفِيَّة
تَعَلُّمُ التَّعْزِيزِ مُتَعَدِّدُ الوُكَلاءِ
تُعرَّف لعبةُ ماركوف متعدِّدةُ الوكلاء بالرمز \(\left( N, \mathcal{S},\left\{\mathcal{A}^i\right\}_{i=1}^N, \mathbb{P},\left\{r^i\right\}_{i = 1}^N, \gamma \right)\). هنا، \(N\) يمثّل عددَ الوكلاء، و\(\mathcal{S}\) فضاء الحالات، و\(\mathcal{A}:=\mathcal{A}^1 \times \cdots \times \mathcal{A}^N\) مجموعةُ الأفعال المشتركة. احتمالاتُ انتقال الحالة ممثّلةٌ بـ\(\mathbb{P}: \mathcal{S} \times \mathcal{A} \rightarrow \Delta(\mathcal{S})\)، ودالّةُ المكافأة لكلّ وكيلٍ \(i\) هي \(r^i: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}\). أخيرًا، \(\gamma \in [0,1]\) هو مُعامِلُ الخصم. يحاول كلّ وكيلٍ تعظيم عائده \(R^i = \sum_{t=0}^\infty \gamma^t r^i_t\). تُعرَّف سياسة الوكيل \(i\) بـ\(\pi^{i}_{\theta_{i}}\) حيث \(\theta_i\) معاملاتُ الشبكة العصبيّة. وتُدرَّب هذه السياسات باستخدام مُقَدِّرات التدرُّج مثل REINFORCE.
المُعْضِلاتُ الاِجْتِمَاعِيَّةُ وَمُعْضِلَةُ السَّجِينِ المُتَكَرِّرَةُ
في الألعاب ذات المصلحة الجماعيّة، تنشأ معضلاتٌ اجتماعيّة حين يسعى كلّ وكيلٍ إلى تعظيم مكافأته الشخصيّة بما يُقوِّض الناتج الجماعي أو الرفاهيّة الاجتماعيّة. يتبدّى ذلك حين تكون النتيجةُ الجماعيّة أدنى ممّا يمكن بلوغُه عبر التعاون الكامل. وتُظهر نماذجُ نظريّةٌ كمعضلة السجين أنّ كلّ مشاركٍ، رغم أنّ الخيانة قد ترفع عائده الفردي الآني، فإنّ الخيانة المُتبادَلة تؤدّي إلى مكافأةٍ جماعيّةٍ أدنى ممّا لو تعاوَن الطرفان.
في معضلة السجين المتكرّرة (IPD)، لا تَعود الخيانةُ الدائمةُ استراتيجيةً مُثلى. فعند مواجهة خصمٍ يتّبع استراتيجية الْمُعامَلَةِ بِالْمِثْل (TFT)، يؤدّي التعاونُ المُستمرّ إلى عوائدَ أعلى. وقد نتوقّع أن يكتشف وكلاءُ MARL—المُصمَّمون لتعظيم عائدهم الفردي—استراتيجياتٍ على غرار TFT لكونها تُحسِّن العوائدَ الفرديّة والجماعيّة معًا ولا تُغري بالانحراف عنها. ومع ذلك، تُظهِر المُشاهداتُ التجريبيّة أنّ الوكلاء المُدرَّبين على تعظيم عائدهم الخاص يميلون عادةً إلى الخيانة الدائمة.
يُمثّل هذا أحدَ التحدّيات الرئيسة لتعلُّم التعزيز متعدِّد الوكلاء في بيئات المصلحة الجماعيّة: إذ يتجاهل الوكلاء أثناء التدريب أنّ الآخرين يتعلّمون أيضًا. فإذا كان الهدفُ رفاهيّةً اجتماعيّة، أمكن تشاركُ المكافآت بين الوكلاء أثناء التدريب، وهو ما يضمن تعاونًا كاملًا في إعداد IPD. لكنّ ذلك لا يكفي حين نبتغي تعاونًا مبنيًّا على المعاملة بالمثل—إذ يلزم ابتكارُ خوارزميّاتٍ قادرةٍ على اكتشاف سياساتٍ تُحفِّز الخصم على التعاون لتعظيم عائده الخاص.
الأَعْمَالُ ذاتُ الصِّلَة
تحاول LOLA تشكيلَ الخصم عبر أخذ تدرُّج قيمة الوكيل مع مراعاة خطوةٍ واحدةٍ مُستقبليّة من تحديثات الخصم. فبدلًا من تحسين \(V^1(\theta^1, \theta^2)\) فحسب، تسعى LOLA إلى احتساب تأثير تحديث الخصم المرتقَب في هدف التحسين.