مُلَخَّصُ

نَحْنُ نَسْتَكْشِف تَحَدِّي تَعْلَم التَعْزِيز العَمِيقِ مُتَعَدِّدِ الوُكَلاءِ فِي بِيئات تَنافُسِيَّةٌ جُزْئِيَّةٍ، حَيْثُ تُواجِه الطُرُقِ التَقْلِيدِيَّةِ صُعُوباتٍ فِي تَعْزِيزِ التَعاوُنِ القائِمِ عَلَى المُعامَلَةِ بِالمِثْلِ. يَتَعَلَّم وُكَلاءُ LOLA وَ POLA سِياساتِ تَعاوُنِيَّةِ قائِمَةً عَلَى المُعامَلَةِ بِالمِثْلِ مِن خِلالَ التَفاضُل عَبْرَ عَدَدٍ قَلِيلٍ مِن خَطَواتٍ التَحْسِين المُسْتَقْبَلِيَّةِ لَخَصْمهم. وَمَعَ ذٰلِكَ، هُناكَ قَيْدِ رَئِيسِيٍّ فِي هٰذِهِ التَقْنِيّاتِ. نَظَراً لِأَنَّها تَأْخُذ فِي الاِعْتِبارِ عَدَدٍ قَلِيلٍ مِن خَطَواتٍ التَحْسِين، فَقَد يَسْتَغِلّ خَصْمِ يَتَعَلَّم وَيَأْخُذ العَدِيدَ مِن الخَطَواتِ لِتَحْسِينِ عائِده هٰذِهِ التَقْنِيّاتِ. رَدّاً عَلَى ذٰلِكَ، نُقَدِّم نَهْجاً جَدِيداً، تَشْكِيلِ الاِسْتِجابَةُ الأَمْثَلُ (BRS)، الَّذِي يُفاضِل مِن خِلالَ خَصْمِ يَقْرُب الاِسْتِجابَةُ الأَمْثَلُ، المُسَمَّى “المُحَقَّقِ”. لَتَكْيِيف المُحَقَّقِ عَلَى سِياسَةِ الوَكِيلَ فِي الأَلْعابُ المُعَقَّدَةِ نَقْتَرِح آلِيَّةِ تَكْيِيفَ قابِلَةٍ لِلتَفاضُل تَعْتَمِد عَلَى الحالَةِ، مُيَسَّرَةٍ بِواسِطَةِ طَرِيقَةِ الإِجابَةَ عَلَى الأَسْئِلَةِ الَّتِي تَسْتَخْرِج تَمْثِيلاً لِلوَكِيل بِناءَ عَلَى سُلُوكه فِي حالاتِ بِيئِيَّةٍ مُحَدَّدَةٍ. لِلتَحَقُّقِ مِن صِحَّةِ طَرِيقَتِنا تَجْرِيبِيّا، نَعْرِض أَداءها المُحْسِن ضِدَّ خَصْمِ Monte Carlo Tree Search (MCTS)، الَّذِي يَعْمَل كَتَقْرِيب لِلاِسْتِجابَةِ الأَمْثَلُ فِي لُعْبَةِ العُمْلَةِ. تَوَسُّع هٰذِهِ الأَعْمالِ تَطْبِيقِ تَعْلَم التَعْزِيز مُتَعَدِّدِ الوُكَلاءِ فِي البِيئات التَنافُسِيَّةِ الجُزْئِيَّةِ وَتَوَفُّرُ مَسارا جَدِيداً نَحْوَ تَحْقِيقِ رَفاهِيَّة اِجْتِماعِيَّةٍ مُحَسِّنه فِي الأَلْعابُ ذاتِ المَجْمُوعِ العامِّ.

مُقَدِّمَةِ

لَقَد مَكَّنَت خوارزميات تَعْلَم التَعْزِيز الوُكَلاءِ مِن الأَداءِ بِشَكْلٍ جَيِّدٍ فِي أَلْعابِ مُعَقَّدَةٌ ذاتِ أَبْعادَ عالِيَةٍ مِثْلَ لُعْبَةِ الذَهابِ (alphago) وستاركرافت (alphastar). الهَدَفَ النِهائِيِّ مِن تَعْلَم التَعْزِيز هُوَ تَدْرِيبِ وُكَلاءُ يُمْكِنهم مُساعَدَةِ البَشَرِ فِي حَلٍّ المُشْكِلاتِ الصَعْبَةِ. لا مَحالّه، سَيَحْتاج هٰؤُلاءِ الوُكَلاءِ إِلَى الاِنْدِماجِ فِي سِينارِيُوهاتٍ الحَياةِ الواقِعِيَّةِ الَّتِي تَتَطَلَّب التَفاعُل مَعَ البَشَرِ وَوُكَلاء تَعْلَم آخَرِينَ. بَيْنَما يَتَأَلَّق تَدْرِيبِ تَعْلَم التَعْزِيز مُتَعَدِّدِ الوُكَلاءِ فِي البِيئات التَعاوُنِيَّة أَو التَنافُسِيَّةِ بِالكامِلِ، فَإِنَّهُ غالِباً ما يَفْشَل فِي إِيجادِ تَعاوُنٍ قائِمٌ عَلَى المُعامَلَةِ بِالمِثْلِ فِي البِيئات التَنافُسِيَّةِ الجُزْئِيَّةِ. مِثالٌ عَلَى ذٰلِكَ هُوَ فَشَلِ وُكَلاءُ تَعْلَم التَعْزِيز مُتَعَدِّدِ الوُكَلاءِ فِي تَعْلَم سِياساتِ مِثْلَ المُعامَلَةِ بِالمِثْلِ فِي مُعْضِلَةِ السَجِينُ المُتَكَرِّرَةِ (LOLA).

عَلَى الرَغْمِ مِن الطابِعِ اللعبي لَأَلْعاب المَجْمُوعِ العامِّ الشائِعَةُ مِثْلَ مُعْضِلَةِ السَجِينُ، فَإِنَّ هٰذِهِ الأَنْواع مِن المُشْكِلاتِ مُنْتَشِرَةٌ فِي المُجْتَمَعِ وَالطَبِيعَة عَلَى حَدٍّ سَواءُ. فِكْرِ فِي سِينارِيو حَيْثُ تَسْعَى دَوْلَتانِ (وُكَلاءُ) لَتَعْظِيم الإِنْتاجِ الصِناعِيِّ لَهُما مَعَ ضَمانِ مُناخٍ مُناسِبٍ لِلإِنْتاجِ مِن خِلالَ الحَدِّ مِن الاِنْبِعاثات الكربونيه. مِن ناحِيَةٍ، تُود كُلِّ دَوْلَةٍ أَنَّ تَرِي الدَوْلَةِ الأُخْرَى تَفِي بِاِلْتِزاماتها لِلحَدِّ مِن الاِنْبِعاثات الكربونيه. وَمِن ناحِيَةٍ أُخْرَى، يَحْفِز كُلِّ مِنهُما إِصْدارِ المَزِيدِ مِن الكَرْبُون لِتَحْقِيقِ عَوائِد صِناعِيَّةٍ أَعْلَى. سَيُجْبَر مُعاهَدَةِ المَناخِ الفَعّالَةَ كُلِّ دَوْلَةٍ - عَلَى الأَرْجَحِ مِن خِلالَ تَهْدِيدٍ بِالعُقُوبات - عَلَى الاِلْتِزامِ بِالحُدُودِ المُتَّفَقِ عَلَيها لِلاِنْبِعاثات الكربونيه. إِذا فَشَلِ هٰؤُلاءِ الوُكَلاءِ فِي تَطْوِيرِ إِسْتراتِيجِيّاتِ مِثْلَ المُعامَلَةِ بِالمِثْلِ، فَمِن المُحْتَمَلِ أَنَّ يَتَقارَبُوا نَحْوَ تَصْعِيدِ مُتَبادَلٍ مُؤْسِفٌ لِلاِسْتِهْلاكِ وَالاِنْبِعاثات الكربونيه.

اِقْتَرَحَ (LOLA) خوارزميه تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ، وَهِيَ خوارزميه نَجَحَت فِي تَعْلَم سُلُوكِ المُعامَلَةِ بِالمِثْلِ فِي إِعْدادِ مُعْضِلَةِ السَجِينُ المُتَكَرِّرَةِ مِن خِلالَ التَمْيِيزِ عَبْرَ خَطْوَةٍ تُدْرِج بَسِيطَةً مُفْتَرَضَةٍ يَتَّخِذها الخَصْمِ. بِناءَ عَلَى ذٰلِكَ، قَدَّمَ (POLA) تَحْدِيثِ سِياسَةِ الخَصْمِ القَرِيبِ، وَالَّذِي يُعَزِّز خوارزميه تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ مِن خِلالَ اِفْتِراضِ تَحْدِيثِ سِياسَةِ قَرِيبٍ لِلخَصْم. يَسْمَح هٰذا التَحْسِين بِتَدْرِيبِ سِياساتِ الشَبَكَةِ العَصَبِيَّةِ فِي أَلْعابِ أَكْثَرَ تَعْقِيداً، مِثْلَ لُعْبَةِ العُمْلَةِ (LOLA). حَسَبَ عَلَّمَنا، تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ هُوَ الأُسْلُوبِ الوَحِيدُ الَّذِي يُدَرِّب بِشَكْلٍ مَوْثُوقٌ وُكَلاءُ تَعاوُنِيَّيْنِ قائِمَيْنِ عَلَى المُعامَلَةِ بِالمِثْلِ فِي لُعْبَةِ العُمْلَةِ.

عَلَى الرَغْمِ مِن نَجاحِهِ فِي لُعْبَةِ العُمْلَةِ، فَإِنَّ تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ لَهُ قُيُوده. بَيْنَما يَتَعَلَّم تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ، فَإِنَّ نمذجته لِتَعْلَم الخَصْمِ مَحْدُودَةٍ بِبِضْعِ خَطَواتٍ تَحْسِينِ مُسْتَقْبَلِيَّةٍ. يَجْعَل هٰذا تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ عُرْضَةً لِلاِسْتِغْلال مِن قِبَلَ الخُصُومِ الَّذِينَ يُشارِكُونَ فِي تَحْسِينِ إِضافِيٍّ. عَلَى وَجْهِ الخُصُوصِ، تُظْهِر تَحْلِيلاتنا لَوُكَلاء تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ المُدَرِّبِينَ عَلَى لُعْبَةِ العُمْلَةِ أَنَّ تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ عُرْضَةً لِلاِسْتِغْلال مِن قِبَلَ الخَصْمِ الَّذِي يَسْتَجِيب بِشَكْلٍ أَفْضَلَ. عِنْدَما يَتِمّ تَدْرِيبِ الخَصْمِ خَصِيصاً لَتَعْظِيم عائِده الخاصِّ ضِدَّ سِياسَةِ ثابِتَةٍ تَمَّ تَدْرِيبها بِواسِطَةِ تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ، فَإِنَّ الأَوَّلِ يَسْتَغِلّ الأَخِيرِ. أَيْضاً، يُمْكِن أَنَّ تُعِيق هٰذِهِ القُيُودِ قابِلِيَّةِ تَوَسُّع تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ؛ لا يُمْكِنه التَمْيِيزِ مِن خِلالَ جَمِيعِ خَطَواتٍ تَحْسِينِ الخَصْمِ. هٰذِهِ مُشْكِلَةِ خاصَّةٍ إِذا كانَ الخَصْمِ شَبَكَةِ عَصَبِيَّةُ مُعَقَّدَةٌ، حَيْثُ تَكُون العَدِيدَ مِن خَطَواتٍ التَحْسِين مَطْلُوبَةٌ لِتَقْرِيبِ تَعْلَمها.

فِي هٰذِهِ الوَرَقَةَ، نُقَدِّم نَهْجاً جَدِيداً يُسَمَّى تَشْكِيلِ الاِسْتِجابَةُ الأَفْضَلِ. يَعْتَمِد أُسْلُوبِنا عَلَى بِناءَ خَصْمِ يَقْرُب سِياسَةِ الاِسْتِجابَةُ الأَفْضَلِ ضِدَّ وَكِيلُ مُعَيَّنٍ. نُشِير إِلَى هٰذا الخَصْمِ بِاِسْمِ “المُحَقَّقِ”. يَتِمّ تَصْوِيرَ المَفْهُومُ العامِّ فِي الشَكْلِ [fig:cobalt]: يَخْضَع المُحَقَّقِ لِلتَدْرِيبِ ضِدَّ وُكَلاءُ مَأْخُوذَيْنِ مِن تَوْزِيعِ مُتَنَوِّعِ. لِتَدْرِيبِ الوَكِيلَ، نُمَيِّز مِن خِلالَ خَصْمِ المُحَقَّقِ. عَلَى عَكْسَ الأَسالِيبِ مِثْلَ تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ وَتَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ، الَّتِي تَفْتَرِض بِضْعَ خَطَواتٍ تَحْسِينِ مُسْتَقْبَلِيَّةٍ، يَعْتَمِد أُسْلُوبِنا عَلَى إِصْدارِ المُحَقَّقِ لِلاِسْتِجابَةِ الأَفْضَلِ لِلوَكِيل الحالِيَّ مِن خِلالَ تَكْيِيفَ السِياسَةِ.

نَقُوم بِالتَحَقُّق التَجْرِيبِيُّ مِن أُسْلُوبِنا فِي مُعْضِلَةِ السَجِينُ المُتَكَرِّرَةِ وَلَعْبه العُمْلَةِ. نَظَراً لِلاِعْتِماد عَلَى سِياسَةِ الخَصْمِ لِنَتائِجِ وَكِيلُ، فَإِنَّهُ لَيِسَ مِن السَهْلِ دائِماً تَقْيِيمِ وَمُقارَنَة سِياساتِ وُكَلاءُ مُخْتَلِفِينَ فِي الأَلْعابُ. هٰذا صَحِيحٌ بِشَكْلٍ خاصٍّ فِي الأَلْعابُ غَيْرِ المُتَساوِيَةُ الَّتِي تُظْهِر جَوانِبَ تَعاوُنِيَّةِ وَتَنافُسِيّه. فِي هٰذِهِ الوَرَقَةَ، نُدافِع عَن أَنَّ نُقْطَةً المُقارَنَةِ المَعْقُولَة هِيَ نَتِيجَةَ الوَكِيلَ عِنْدَ مُواجَهَةِ خَصْمِ يَسْتَجِيب بِشَكْلٍ أَفْضَلَ، وَالَّذِي نَقْرُبه بِواسِطَةِ بَحَثَ شَجَرَةَ مَوَّنْتُ كارْلُو. نُظْهِر أَنَّهُ بَيْنَما لا يَتَعاوَن بَحَثَ شَجَرَةَ مَوَّنْتُ كارْلُو بِالكامِلِ مَعَ وُكَلاءُ تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ، فَإِنَّهُم يَتَعاوَنُونَ بِالكامِلِ مَعَ وَكِيلُ تَشْكِيلِ الاِسْتِجابَةُ الأَفْضَلِ لَدَينا.

المُساهَماتِ الرَئِيسِيَّةِ: نُلَخِّص مُساهَماتنا الرَئِيسِيَّةِ أَدَنّاهُ:

• نُحَدِّد أَنَّ الخَصْمِ الَّذِي يَسْتَجِيب بِشَكْلٍ أَفْضَلَ، كَما هُوَ مُقَرَّبٍ بِواسِطَةِ بَحَثَ شَجَرَةَ مَوَّنْتُ كارْلُو، لا يَتَعاوَن مَعَ وُكَلاءُ تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ. يَسْتَغِلّ بَحَثَ شَجَرَةَ مَوَّنْتُ كارْلُو وُكَلاءُ تَعْلَم مَعَ وَعْيِ بِتَعَلُّمِ الخَصْمِ القَرِيبِ لِتَحْقِيقِ عائِدٌ أَعْلَى مِمّا كانَ سَيُحَقِّقه مِن خِلالَ التَعاوُنِ الكامِلِ.

• لِمُعالَجَةِ هٰذِهِ الضُعْفِ، نُقَدِّم أُسْلُوبِ تَشْكِيلِ الاِسْتِجابَةُ الأَفْضَلِ، الَّذِي يُدَرِّب وَكِيلا مِن خِلالَ التَمْيِيزِ مِن خِلالَ خَصْمِ يَقْرُب الاِسْتِجابَةُ الأَفْضَلِ (يُشار إِلَيهِ بِاِسْمِ ’خَصْمِ المُحَقَّقِ’). نَقُوم بِالتَحَقُّق التَجْرِيبِيُّ مِن أُسْلُوبِنا وَنُظْهَر أَنَّ الاِسْتِجابَةُ الأَفْضَلِ لَوُكَلاء تَشْكِيلِ الاِسْتِجابَةُ الأَفْضَلِ هِيَ بِالفِعْلِ التَعاوُنِ الكامِلِ كَما هُوَ مُوَضِّح فِي الشَكْلِ [fig:coin_main_compare].

• بِالإِضافَةِ إِلَى ذٰلِكَ، نَقْتَرِح آلِيَّةِ تَكْيِيفَ قابِلَةٍ لِلتَفاضُل واعِيَةٌ بِالحالَةِ لَخَصْم المُحَقَّقِ، مِمّا يُمْكِنه مِن التَكَيُّفِ مَعَ سِياسَةِ الوَكِيلَ.

الخَلْفِيَّةِ

تَعْلَم التَعْزِيز المُتَعَدِّدِ العَوامِلُ

لُعْبَةِ ماركوف المُتَعَدِّدَةِ العَوامِلُ تَعْرِف بِالرَمْز \(\bm{(} N, \mathcal{S},\left\{\mathcal{A}^i\right\}_{i=1}^N, \mathbb{P},\left\{r^i\right\}_{i = 1}^N, \gamma \bm{)}\). هُنا، \(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})\) وَدالّه المُكافَأَةَ ب \(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 (reinforce).

المُعْضِلات الاِجْتِماعِيَّةِ وَمُعْضِلَة السَجِينُ المُتَكَرِّرَةِ

فِي سِياقِ الأَلْعابُ ذاتِ المَجْمُوعِ العامِّ، تُظْهِر المُعْضِلات الاِجْتِماعِيَّةِ عِنْدَما يَسْعَى الوُكَلاءِ الفرديون لِتَحْسِينِ مُكافَآتهم الشَخْصِيَّةِ وَلٰكِنَّهُم بِذٰلِكَ يُقَوِّضُونَ النَتِيجَةُ الجَماعِيَّةِ أَو الرَفاهِيَّةِ الاِجْتِماعِيَّةِ. هٰذِهِ الظاهِرَةِ تَكُون أَكْثَرَ وُضُوحاً عِنْدَما تَكُون النَتِيجَةُ الجَماعِيَّةِ أَدَّنِي مِن النَتِيجَةُ الَّتِي كانَ يُمْكِن تَحْقِيقِها مِن خِلالَ التَعاوُنِ الكامِلِ. تُوَضِّح الدِراساتِ النَظَرِيَّةِ، مِثْلَ مُعْضِلَةِ السَجِينُ، السِينارِيُوهات الَّتِي يَكُون فِيها كُلِّ مُشارِكٍ، عَلَى الرَغْمِ مِن أَنَّهُ يَكُون فِي وَضْعِ أَفْضَلَ عِنْدَ الاِعْتِرافِ، يُحَقِّق مُكافَأَةٍ جَماعِيَّةٍ أَقَلَّ مُقارَنَةً بِالبَقاءِ صامِتاً.

وَمَعَ ذٰلِكَ، فِي مُعْضِلَةِ السَجِينُ المُتَكَرِّرَةِ (IPD)، لا يَعُود التَخَلِّي غَيْرِ المَشْرُوطِ هُوَ الإِسْتراتِيجِيَّةِ السائِدَةِ. عَلَى سَبِيلِ المِثالِ، فِي مُواجَهَةِ خَصْمِ يَتْبَع إِسْتراتِيجِيَّةِ الرَدِّ بِالمِثْلِ (TFT)، يُؤَدِّي التَعاوُنِ المُسْتَمِرِّ إِلَى عائِدٌ أَعْلَى لِلوَكِيل. قَد يُتَوَقَّع المَرْء أَنَّ التَعَلُّمِ الآلِيِّ المُعَزِّز لِلوُكَلاء المُتَعَدِّدَيْنِ (MARL)، المُصَمِّم لَتَعْظِيم عائِدٌ كُلِّ وَكِيلُ، سَيَكْتَشِف إِسْتراتِيجِيَّةِ TFT، حَيْثُ تُعَزِّز كُلّاً مِن العَوائِد الجَماعِيَّةِ وَالفَرْدِيَّة، وَلا تُوَفِّر حافِزاً لِتَغْيِيرِ السِياسَةِ، مُجَسَّده تَوازُنٍ ناش. وَمَعَ ذٰلِكَ، تَكْشِف المُلاحَظاتِ التَجْرِيبِيَّة أَنَّ الوُكَلاءِ القِياسِيَّيْنِ فِي التَعَلُّمِ المُعَزِّز، المُدَرِّبِينَ لَتَعْظِيم عائِدهم الخاصِّ، يَمِيلُونَ عادَةً إِلَى التَخَلِّي غَيْرِ المَشْرُوطِ.

هٰذا يُمَثِّل أَحَدُ التَحَدِّياتِ الرَئِيسِيَّةِ لِلتَعَلُّمِ المُعَزِّز لِلوُكَلاء المُتَعَدِّدَيْنِ فِي الأَلْعابُ ذاتِ المَجْمُوعِ العامِّ: خِلالَ التَدْرِيبِ، غالِباً ما يَتَجاهَل الوُكَلاءِ حَقِيقَةِ أَنَّ الوُكَلاءِ الآخَرِينَ أَيْضاً فِي عَمَلِيَّةِ التَعَلُّمِ. لِمُعالَجَةِ هٰذِهِ المُشْكِلَةِ، وَإِذا كانَت الرَفاهِيَّةِ الاِجْتِماعِيَّةِ هِيَ الاِعْتِبارِ الرَئِيسِيُّ، يُمْكِن مُشارَكَةِ المُكافَآتُ بَيِّنَ الوُكَلاءِ أَثْناءَ التَدْرِيبِ. عَلَى سَبِيلِ المِثالِ، تَدْرِيبِ كُلّاً الوَكِيلَيْنِ فِي إِعْدادِ IPD لَتَعْظِيم العائِدِ الجَماعِيِّ سَيُؤَدِّي إِلَى تَعاوُنٍ مُسْتَمِرٍّ. وَمَعَ ذٰلِكَ، هٰذا النَهْجِ غَيْرِ كافٍ إِذا كانَ الهَدَفَ هُوَ تَعْزِيزِ التَعاوُنِ المَبْنِيَّ عَلَى المُعامَلَةِ بِالمِثْلِ. تَطْلُب سِياسَةِ تَحْفِز الخَصْمِ عَلَى التَعاوُنِ مِن أَجْلِ تَعْظِيمِ عائِده الخاصِّ. بَيْنَما TFT هِيَ إِحْدَى هٰذِهِ السِياساتِ، فَإِنَّ تَصْمِيمِ سِياساتِ مُماثِلَةٍ لِ TFT يَدَوِيّاً فِي مَجالاتِ أُخْرَى لَيِسَ مَرْغُوبا فِيهِ وَلا يُمْكِن تَحْقِيقِهِ، مِمّا يَبْرُز الحاجَةِ إِلَى تَطْوِيرِ خوارزميات تَدْرِيبِ جَدِيدَةٍ يُمْكِنها اِكْتِشافِ هٰذِهِ السِياساتِ.

الأَعْمالِ ذاتِ الصِلَةِ

تُحاوِل (LOLA) تَشْكِيلِ الخَصْمِ مِن خِلالَ أَخَذَ التَدَرُّج لِلقِيمَةِ بِالنَظَرِ إِلَى خَطْوَةٍ واحِدَةٍ لِلأَمام مِن مُعامَلاتِ الخَصْمِ. بَدَلاً مِن النَظَرِ فِي العائِدِ المُتَوَقَّعِ تَحْتَ زَوْج مُعامَلاتِ السِياسَةِ الحالِيَّةِ، \(V^1(\theta_i^1, \: \theta_i^2)\)، تَقُوم (LOLA) بِتَحْسِين \(V^1(\theta_i^1, \: \theta_i^2 + \Delta \theta_i^2)\) حَيْثُ يُشِير \(\Delta \theta_i^2\) إِلَى خَطْوَةٍ تَعْلَم بَسِيطَةً لِلخَصْم. لِإِجْراءِ حِسابِ التَدَرُّج لِلتَحْدِيث \(\Delta \theta_i^2\)، تُعْتَبَر (LOLA) القِيمَةِ البَدِيلَةِ المُعْطاة بِواسِطَةِ تَقْرِيبِ تايْلُور مِن الدَرَجَةِ الأُولَى لِ \(V^1(\theta_i^1, \: \theta_i^2 + \Delta \theta_i^2)\). نَظَراً لِأَنَّهُ لا يُمْكِن حِسابِ القِيمَةِ الدَقِيقَةِ تَحْلِيلِيّا فِي مُعْظَمَ الأَلْعابُ، يُقَدِّم المُؤَلِّفُونَ صِيغَةِ تُدْرِج السِياسَةِ الَّتِي تَعْتَمِد عَلَى تَدَحْرُجات البِيئَةِ لَتَقْرِيبها. تَمَكَّنَت هٰذِهِ الطَرِيقَةِ مِن إِيجادِ إِسْتراتِيجِيّاتِ الرَدِّ المُتَبادَلِ فِي لُعْبَةِ السَجِينُ المُتَكَرِّرَةِ.

تَقَدَّمَ (POLA) نُسْخَةً مِثالِيَّةٍ مِن (LOLA) لا تَتَأَثَّر بِمُعامَلات السِياسَةِ. لِلقِيامِ بِذٰلِكَ، يُحاوِل كُلِّ لاعِبٍ زِيادَةِ اِحْتِمالِ الأَفْعال الَّتِي تُؤَدِّي إِلَى عَوائِد أَعْلَى مَعَ مُعاقَبَةِ التَبايُنِ كولباك-لايبلر فِي فَضاءِ السِياسَةِ بِالنِسْبَةِ لَسِياساتهم فِي الخَطْوَةِ الزَمَنِيَّةِ السابِقَةِ. مُشابِهَةٍ لِطَرِيقَةِ النُقْطَةِ القَرِيبَةِ، تُشَكِّل كُلِّ خَطْوَةٍ مِن خَطَواتٍ (POLA) مُشْكِلَةِ تَحْسِينِ يَتِمّ حَلِّها تَقْرِيباً مِن خِلالَ التَنازُلِ التَدْرِيجِيِّ. مِثْلَ (LOLA)، تُسْتَخْدَم (POLA) تَدَحْرُجات المَسارُ لَتَقْدِير قِيمَةَ كُلِّ لاعِبٍ وَتُطَبِّق مُقَدَّر التَعْزِيز لِحِسابِ التَدَرُّجات. تَحَقَّقَ (POLA) تَعاوُناً غَيْرِ قابِلٌ لِلاِسْتِغْلال بِفَعّالِيَّةٍ فِي لُعْبَةِ السَجِينُ المُتَكَرِّرَةِ وَلَعْبه العُمْلَةِ مَعَ تَحْسِينِ العُيُوبِ فِي سابِقَتِها.

يُعْتَبَر (mfos) لُعْبَةِ فَوْقِيّه حَيْثُ يَتِمّ لَعِبَ لُعْبَةِ كامِلَةٍ فِي كُلِّ خَطْوَةٍ فَوْقِيّه وَالمُكافَأَة الفَوْقِيَّةِ هِيَ عائِدٌ تِلْكَ اللُعْبَةِ. العامِلِ هُوَ سِياسَةِ فَوْقِيّه تَتَعَلَّم التَأْثِيرِ عَلَى سُلُوكِ الخَصْمِ خِلالَ هٰذِهِ التَدَحْرُجات. يُغَيِّر (mfos) اللُعْبَةِ وَلا يُمْكِن مُقارَنَته بِطَرِيقَتنا الَّتِي تُعْتَبَر تَعْلَم سِياسَةِ واحِدَةٍ. يُغَيِّر (rusp) هَيْكَلِ اللُعْبَةِ حَيْثُ يُشارِك كُلِّ عامِلٍ فِي المُكافَأَةَ مَعَ عُمَلاءِ آخَرِينَ. يُدْرِك العُمَلاءِ هٰذا التَجْمِيع لِلمُكافَآت مِن خِلالَ نُسْخَةً مَشُوشه مِن مَصْفُوفه مُشارَكَةِ المُكافَآتُ. فِي وَقْتٍ الاِخْتِبارُ، يَتِمّ ضَبْطِ مَصْفُوفه التَمْثِيلِ عَلَى عَدَمِ مُشارَكَةِ المُكافَآتُ وَلا يَتِمّ إِضافَةً ضَوْضاء إِلَى هٰذِهِ المَصْفُوفَة.

تَدُور أَلْعابِ (colman1998stackelberg) حَوْلَ اِخْتِيارِ الفِعْلِ الأُولَى لِلقائِد يَلِيه حَرَكَةِ الأَتْباع اللاحِقَةِ. يُقَدِّم إِطارِ العَمَلِ المُمَثِّلُ-الناقِد ثُنائِيٍّ المُسْتَوَياتِ (zhang2020bi) نَهْجاً مُبْتَكَرا لِتَدْرِيبِ كُلِّ مِن القائِدُ وَالأَتْباع فِي نَفْسِ الوَقْتِ خِلالَ فَتْرَةٍ التَدْرِيبِ مَعَ الحِفاظِ عَلَى قابِلِيَّةِ التَنْفِيذِ المُسْتَقِلَّةِ، مِمّا يَجْعَله مُناسِبا لِمُعالَجَةِ تَحَدِّياتٍ التَنْسِيقِ فِي التَعَلُّمِ المُتَعَدِّدِ لِلعُمَلاءِ. عَلَى عَكْسَ أَعْدادنا، حَيْثُ يَعْمَل المُحَقَّقِ كَأَداة تَدْرِيبِ يَتِمّ التَخَلُّصِ مِنها بُعْدَ التَدْرِيبِ، يَخْتَلِف (zhang2020bi) مِن خِلالَ نَشْرِ كُلِّ مِن القائِدُ وَالأَتْباع مَعاً خِلالَ وَقْتٍ الاِخْتِبارُ (حَيْثُ الاِهْتِمامِ الرَئِيسِيُّ هُوَ التَنْسِيقِ بَيِّنَ القائِدُ وَالأَتْباع). تَعْكِس التَفاعُلات بَيِّنَ العامِلِ وَالمُحَقِّق الإِعْدادُ الأَساسِيُّ لِ (colman1998stackelberg)، حَيْثُ يَلْعَب العامِلِ دَوْرِ القائِدُ وَالمُحَقِّق دَوْرِ الأَتْباع.

يُدَرِّب (balaguer2022good) أَفْضَلَ اِسْتِجابَةً لَعامِل تَعْلَم، معكسا فِكْرَةَ أَفْضَلَ اِسْتِجابَةً لِأُفَضِّل اِسْتِجابَةً. يُقَدِّم المُؤَلِّفُونَ طَرِيقَتَيْنِ لِلتَدْرِيبِ ضِدَّ هٰذِهِ الاِسْتِجابَةُ المُثْلَى. أَوَّلاً، مِن خِلالَ إِنْشاءِ رَسْمِ بَيانَيَّ حِسابَيَّ واسِعٍ لِتَحْسِينِ العامِلِ. ثانِياً، بِاِسْتِخْدامِ إِسْتراتِيجِيّاتِ تَطَوُّرَيْهِ. لا تَتَّسِم أَيّ مِن هٰذِهِ الطُرُقِ بِالقابِلِيَّة لِلتَوَسُّع. إِنْشاءِ رَسْمِ بَيانَيَّ حِسابَيَّ كامِلٍ لِكُلِّ خَطْوَةٍ تَحْسِينِ لِلعامِل غَيْرِ فَعّالٌ لِلغايَةِ. عِلاوَةً عَلَى ذٰلِكَ، تَتَطَلَّب الإِسْتراتِيجِيّات التَطَوُّرِيَّة تَدْرِيبِ الخَصْمِ ضِدَّ نِقاطٍ بَياناتٍ جَدِيدَةٍ فِي كُلِّ مَرَّةً. تَتَجَنَّب طَرِيقَتِنا هٰذِهِ المُشْكِلَةِ بِاِسْتِخْدامِ شَبَكَةِ عَصَبِيَّةُ لِتَقْلِيلِ عَمَلِيَّةِ التَحْسِين. يُوَحِّد (lanctot2017unified) العَدِيدَ مِن إِطارات تَدْرِيبِ التَعَلُّمِ المُتَعَدِّدِ لِلعُمَلاءِ مِثْلَ التَعَلُّمِ المُسْتَقِلِّ، الاِسْتِجابَةُ الأَفْضَلِ المُتَكَرِّرَةِ، وَاللَعْبِ الذاتِيِّ الخَيالِيّ. تَمْدُد طُرُقٍ عائِلَةِ (PSRO) مَجْمُوعَةِ مِن السِياساتِ السابِقَةِ بِشَكْلٍ تَكْرارِي، مِن خِلالَ إِضافَةً أَفْضَلَ اِسْتِجابَةً لَمَزِيج مِن تِلْكَ السِياساتِ السابِقَةِ. عَلَى عَكْسَ (BRS), لا تُمَيِّز (PSRO) مِن خِلالَ أَفْضَلَ اِسْتِجابَةً.

تَشْكِيلِ الاِسْتِجابَةُ الأَمْثَلُ

تُدَرِّب خوارزميه تَشْكِيلِ الاِسْتِجابَةُ الأَمْثَلُ (Best Response Shaping) العامِلِ مِن خِلالَ التمايز عَبْرَ تَقْرِيبِ لِلخَصْم ذُو الاِسْتِجابَةُ الأَمْثَلُ (كَما وَصَفَ فِي القِسْمِ [sec:method:bestresponse]). هٰذا الخَصْمِ، المُسَمَّى المُحَقَّقِ، يَعْتَمِد عَلَى سِياسَةِ العامِلِ مِن خِلالَ آلِيَّةِ الإِجابَةَ عَلَى الأَسْئِلَةِ لِاِخْتِيارِ أَفْعالِهِ (القِسْمِ [sec:method:detective]). بُعْدَ ذٰلِكَ، نَقُوم بِتَدْرِيبِ العامِلِ مِن خِلالَ التمايز عَبْرَ المُحَقَّقِ بِاِسْتِخْدامِ مُقَدَّر التَدَرُّج REINFORCE (reinforce) (القِسْمِ [sec:method:agent]). كَما نَقْتَرِح اللَعْبِ الذاتِيِّ كَطَرِيقه تَنْظِيمَيْهِ لِتَشْجِيعِ السُلُوكِ التَعاوُنِيّ، مِمّا يُشَجِّع العامِلِ عَلَى اِسْتِكْشافٍ السِياساتِ التَعاوُنِيَّة. نُثْبِت أَيْضاً أَنَّ هٰذا اللَعْبِ الذاتِيِّ يُعادِل اللَعْبِ الذاتِيِّ مَعَ مُشارَكَةِ المُكافَآتُ. يَتِمّ تَوْفِيرِ الشَفْرَة الزائِفَة لِ BRS فِي الخوارزميه [algo:cobalt].

وَكِيلُ الاِسْتِجابَةُ الأَمْثَلُ لِلخَصْم ذُو الاِسْتِجابَةُ الأَمْثَلُ

تَتْبَع تَعْرِيفاتنا وَرُمُوزنا مِن (Agarwal2021)، نَرْمُز لِ \(\tau\) كَمَسار تُوَزِّعه، \(\text{Pr}_\mu^{\theta_1, \theta_2}(\tau)\)، بِتَوْزِيعِ الحالَةِ الاِبْتِدائِيَّةُ \(\mu\)، يُعْطَى بِواسِطَةِ \[\begin{aligned} \text{Pr}_\mu^{\theta_1, \theta_2}(\tau) = \mu(s_0) \pi_{\theta_1}(a_0 | s_0)\pi_{\theta_2}(b_0 | \pi_{\theta_1}, s_0) P(s_1 | s_0, a_0, b_0) \hdots\end{aligned}\] هُنا \(a\) تَدُلّ عَلَى الفِعْلِ الَّذِي يَتَّخِذه الوَكِيلَ وَ\(b\) الفِعْلِ الَّذِي يَتَّخِذه الخَصْمِ. الخَصْمِ ذُو الاِسْتِجابَةُ الأَمْثَلُ هُوَ السِياسَةِ الَّتِي تَحْصُل عَلَى أَعْلَى عائِدٌ مُتَوَقَّعٌ ضِدَّ وَكِيلُ مُعَيَّنٍ. بِشَكْلٍ رَسْمِيٌّ، بِالنَظَرِ إِلَى \(\theta_1\)، فَإِنَّ سِياسَةِ الخَصْمِ ذُو الاِسْتِجابَةُ الأَمْثَلُ \(\theta_2^*\) تُحِلّ لِلمُعادَلَة التالِيَةِ: \[\begin{aligned} \theta_2^* = \argmax_{\theta_2} \mathbb{E}_{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_2}} \left[ R^2(\tau)\right]\end{aligned}\]

بُعْدَ ذٰلِكَ، نَقُوم بِتَدْرِيبِ سِياسَةِ الوَكِيلَ لِلحُصُولِ عَلَى أَعْلَى عائِدٌ مُتَوَقَّعٌ ضِدَّ وَكِيلُ الاِسْتِجابَةُ الأَمْثَلُ. يَتِمّ حَلٍّ تَدْرِيبِ سِياسَةِ الوَكِيلَ لِلمُعادَلَة التالِيَةِ: \[\begin{aligned} \theta_1^{**} = \argmax_{\theta_1} \mathbb{E}_{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_2^*}} \left[R^1(\tau)\right] \end{aligned}\] لاحَظَ أَنَّ هٰذِهِ مُشْكِلَةِ تَحْسِينِ ثُنائِيَّةٍ المُسْتَوَى. نَفْتَرِض أَنَّ الوَكِيلَ \(\pi_{\theta_1}^{**}\) يُظْهِر خَصائِصِ وَكِيلُ غَيْرِ قابِلٌ لِلاِسْتِغْلال، حَيْثُ يَتَعَلَّم إِسْتراتِيجِيّاتِ الاِنْتِقامِ رَدّاً عَلَى خَصْمِ مُتَخَلِّفٍ، مِمّا يَخْلُق حَوافِزِ لَخَصْم عَقْلانِيٌّ لِلتَعاوُنِ.

تَدْرِيبِ الخَصْمِ الكاشِف

فِي التَعَلُّمِ المُعَزِّز العَمِيقِ، يَعْتَمِد تَدْرِيبِ الوُكَلاءِ عَلَى اِسْتِخْدامِ التَحْسِين المَبْنِيَّ عَلَى التَدَرُّج. وَنَتِيجَةَ لِذٰلِكَ، نَحْتاج إِلَى خَصْمِ قابِلٌ لِلتَفاضُل يَقْرُب أَفْضَلَ اِسْتِجابَةً مُمْكِنَةٍ. نُسَمَّى هٰذا الخَصْمِ ب “الكاشِف”. تَعْتَمِد سِياسَةِ الكاشِف عَلَى سِياسَةِ الوَكِيلَ بِالإِضافَةِ إِلَى حالَةِ البِيئَةِ، وَالَّتِي نَرْمُز لَها ب \(\pi_{\theta_2} (a|\pi_{\theta_1}, s)\). نَقُوم بِتَدْرِيبِ الكاشِف لِيُحَقِّق أَقْصَى عائِدٌ لَهُ ضِدَّ وُكَلاءُ مُخْتَلِفِينَ. مِن الناحِيَةِ الرَسْمِيَّةِ، يَتِمّ تَدْرِيبِ الكاشِف بِواسِطَةِ الخَطْوَةِ التدرجيه التالِيَةِ: \[\begin{aligned} \nabla_{\theta_2} \underset{\theta_1 \sim \mathcal{B}}{\mathbb{E}}\underset{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_2}}{\mathbb{E}} \left[R^2(\tau)\right]\end{aligned}\] حَيْثُ يُمَثِّل \(\mathcal{B}\) تَوْزِيعاً لِسِياساتِ مُتَنَوِّعَةٍ لِلوَكِيل \(1\). يَجِب الإِشارَةُ إِلَى أَنَّ الكاشِف يَتِمّ تَدْرِيبه عَبْرَ الإِنْتِرْنِت وَيَتِمّ تَحْدِيثِ الذاكِرَةِ المُؤَقَّتَةِ، \(\mathcal{B}\)، بِمُعَلِّمات الوَكِيلَ الحالِيَّةِ.

التَكْيِيف عَلَى سِياسَةِ الوَكِيلَ

يَسْتَعْلِم المُحَقَّقِ عَن سُلُوكِ الوَكِيلَ فِي حالاتِ مُخْتَلِفَةٍ مِن اللُعْبَةِ. لِلقِيامِ بِذٰلِكَ، يَقُوم بِتَقْيِيم اِحْتِمالاتِ أَفْعالٍ الوَكِيلَ (الإِجاباتِ) عَلَى حالَةِ مِن اللُعْبَةِ (الأَسْئِلَةِ). بِشَكْلٍ رَسْمِيٌّ، لِنَفْتَرِض أَنَّ \(\mathcal{Q}_{\psi}(\theta_1, s)\) هِيَ الدالَّةِ الَّتِي يَسْتَخْدِمها المُحَقَّقِ لَاِسْتِخْراج تَمْثِيلِ وَأَعِي بِالحالَةِ لِلوَكِيل. نُسَمَّى \(\mathcal{Q}\) دالَّةٍ الإِجابَةَ عَلَى الأَسْئِلَةِ (QA) إِذا كانَ يُمْكِن التَعْبِيرِ عَن \(\mathcal{Q}\) بِأَنَّها تَمْتَلِك الوُصُولِ فَقَط إِلَى دالَّةٍ السِياسَةِ، أَيّ \(\mathcal{Q}_{\psi}(\pione, s)\). هُناكَ العَدِيدَ مِن الطُرُقِ المُمْكِنَةِ لِتَصْمِيمِ دالَّةٍ QA. بُعْدَ ذٰلِكَ، نُحَدِّد طَرِيقَةِ أَظْهَرَت نَجاحاً فِي لُعْبَةِ العُمْلَةِ.

الإِجابَةَ عَلَى الأَسْئِلَةِ بِناءَ عَلَى المُحاكاة

سُلُوكِ الوَكِيلَ فِي استمراريات مُحْتَمَلَةٍ لِلُعْبَةِ بَدْءاً مِن الحالَةِ \(s\) يَحْمِل مَعْلُوماتٍ قِيمَةَ. عَلَى وَجْهِ التَحْدِيدِ، يُمْكِننا تَقْيِيمِ سُلُوكِ الوَكِيلَ مُقابِلَ وَكِيلُ عَشْوائِيٍّ يَبْدَأ مِن حالَةِ اللُعْبَةِ \(s\). رَسْمِيّاً، لِيَكُن \(\delta_A\) معرفا كَما يَلِي حَيْثُ \(\tau\) هُوَ مَسارِ يَبْدَأ مِن الحالَةِ \(s\) فِي الوَقْتِ \(t\):

\[\begin{aligned} \delta_A := \underset{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_r}}{\mathbb{E}} \left[R^r(\tau) | s_t = s\right]\end{aligned}\]

حَيْثُ \(\pi_{\theta_r}\) هُوَ خَصْمِ يَخْتار الفِعْلِ \(A\) فِي الوَقْتِ \(t\) وَبُعْدَ ذٰلِكَ يَأْخُذ عَيِّناتٍ مِن تَوْزِيعِ مُوَحَّدٍ عَلَى جَمِيعِ الأَفْعال المُمْكِنَةِ: \[\begin{aligned} \pi_{\theta_r}(a_i = A| s_i) = \begin{cases} \frac{1}{|\mathcal{A}|} & \text{if } i > t \\ \mathbbm{1}_{\{a_i = A\}} & \text{if } i = t \\ \end{cases}\end{aligned}\] يُقَدَّر المُحَقَّقِ \(\delta_A\) بِواسِطَةِ تَدَحْرُجات مَوَّنْتُ كارْلُو لِلُعْبَةِ إِلَى طُولِ مُعَيَّنٍ بَيِّنَ الوَكِيلَ وَالخَصْمِ العَشْوائِيِّ، \(\pi_{\theta_r}\). نَرْمُز لَتَقْدِير \(\delta_A\) ب \(\hat{\delta}_{A}\). ثُمَّ نَعْرِف \(\mathcal{Q}^{\text{simulation}}\) = \([\hat{\delta}_{A_1}, \hat{\delta}_{A_2}, \cdots, \hat{\delta}_{A_{|\mathcal{A}|}}]\). يُعْتَبَر عَدَدٍ العَيْنات المُسْتَخْدَمَةِ لَتَقْدِير عَوائِد اللُعْبَةِ وَطُول الأَلْعابُ المُحاكاة مُعَلِّمات فائِقه لِ \(\mathcal{Q}^{\text{simulation}}\) الإِجابَةَ عَلَى الأَسْئِلَةِ. لاحَظَ أَنَّهُ يُمْكِن تَمْيِيزٍ \(\mathcal{Q}^{\text{simulation}}\) بِالنِسْبَةِ لَمُعَلِّمات سِياسَةِ الوَكِيلَ عَبْرَ مُصْطَلَحُ تَعْزِيزِ (reinforce). عَلَى وَجْهِ التَحْدِيدِ، نَسْتَخْدِم عامِلٍ النَرْد (LOLA).

[sec:method:agent]

التَمْيِيزِ مِن خِلالَ المُحَقَّقِ

تَمَّ تَدْرِيبِ سِياسَةِ الوَكِيلَ لَتَعْظِيم عائِده ضِدَّ خَصْمِ المُحَقَّقِ مِن خِلالَ مُقَدَّر التَدَرُّج REINFORCE. وَمَعَ ذٰلِكَ، نَظَراً لِأَنَّ سِياسَةِ المُحَقَّقِ تَأْخُذ سِياسَةِ الوَكِيلَ كمدخلات، فَإِنَّ مُصْطَلَحُ REINFORCE سَيَشْمَل مُصْطَلَحاً إِضافِيّا لِلاِنْتِشار العَكْسِيّ لِلمُحَقِّق فَوْقَ المُصْطَلَحِ المُعْتادُ لِ REINFORCE: \[\begin{aligned} \underset{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_2}}{\mathbb{E}} \left[R^{1}(\tau) \sum_{t=1}^{T} \left[\nabla_{\theta_1} \log(\pione(a_{t}|s_t)) + \underbrace{\nabla_{\theta_1}\log(\pitwo(b_{t}|\pi_{\theta_1}, s_t))}_{\text{مُصْطَلَحُ الاِنْتِشارِ العَكْسِيّ لِلمُحَقِّق}}\right]\right]\end{aligned}\]

يُمْكِن اِعْتِبارِ هٰذا المُصْطَلَحِ الإِضافِيّ كَالاِتِّجاه فِي فَضاءِ السِياساتِ الَّذِي يُشَجِّع فِيهِ تَغْيِيرٍ مُعامَلاتِ الوَكِيلَ المُحَقَّقِ عَلَى اِتِّخاذِ إِجْراءاتِ تَزِيد مِن عائِدٌ الوَكِيلَ الخاصِّ.

تَنْظِيمِ التَعاوُنِ مِن خِلالَ اللَعْبِ الذاتِيِّ مَعَ مُشارَكَةِ المُكافَآتُ

العَوامِلُ الَّتِي تَتَدَرَّب ضِدَّ خُصُوم عَقْلانِيَّيْنِ تَمِيل إِلَى الاِعْتِمادِ عَلَى الاِفْتِراضُ بِأَنَّ العامِلِ المُعارِضِ مُتَساهِل تُجاهَ أَفْعالهم غَيْرِ التَعاوُنِيَّة. يَسْمَح هٰذا الاِعْتِمادِ عَلَى السُلُوكِ العَقْلانِيّ لَهُم بِأَنَّ يَسْتَغِلُّوا الخَصْمِ إِلَى حَدٍّ ما. وَنَتِيجَةَ لِذٰلِكَ، قَد لا يَتَعَلَّمُونَ بِفَعّالِيَّةٍ كَيْفِيَّةِ التَعاوُنِ مَعَ أَنْفُسِهِم. فِي السِينارِيُوهات الَّتِي يَكُون الهَدَفَ فِيها هُوَ تَعْزِيزِ السُلُوكِ التَعاوُنِيّ، وَخاصَّةً تَشْجِيعِ العامِلِ عَلَى التَعاوُنِ مَعَ نَفْسِهِ، فَإِنَّ النَهْجِ المُباشِرِ هُوَ تَدْرِيبِ العامِلِ فِي إِعْدادِ اللَعْبِ الذاتِيِّ، مَعَ الاِفْتِراضُ بِأَنَّ سِياسَةِ الخَصْمِ تَعْكِس سِياسَةِ العامِلِ. مِن الناحِيَةِ الرَسْمِيَّةِ، نَقُوم بِتَحْدِيثِ العامِلِ بِاِسْتِخْدامِ قاعِدَةِ التَحْدِيثِ التالِيَةِ: \[\begin{aligned} \label{eqn:selfplayrewardsharing} \nabla_{\theta_1} \underset{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_1}}{\mathbb{E}} \left[ R^1(\tau)\right]\end{aligned}\] نُثْبِت أَنَّهُ فِي الأَلْعابُ المُتَماثِلَة مِثْلَ لُعْبَةِ السُجَناءِ التَكْرارِيَّة وَلَعْبه العُمْلَةِ، هٰذا يُعادِل تَدْرِيبِ عامِلٍ مَعَ اللَعْبِ الذاتِيِّ مَعَ مُشارَكَةِ المُكافَآتُ (أَنْظُر البُرْهانُ فِي §[app:self-play]). يَبْرُز هٰذا التَدْرِيبِ العُنْصُرُ التَعاوُنِيّ لَأَلْعاب المَجْمُوعِ العامِّ. فِي الأَلْعابُ ذاتِ المَجْمُوعِ الصِفْرِيّ، لَن يَكُون لِهٰذا التَحْدِيثِ أَيّ تَأْثِيرِ حَيْثُ سَيَكُون التَدَرُّج صِفْرا (أَنْظُر البُرْهانُ فِي §[app:self-play]). نُشِير إِلَى هٰذا المُصْطَلَحِ الخَسارَةِ التَنْظِيمِيَّةِ بِاِسْمِ اللَعْبِ الذاتِيِّ مَعَ مُشارَكَةِ المُكافَآتُ طِوالَ الوَرَقَةَ. نَقُوم أَيْضاً بِإِجْراءِ تَجْرِبَةِ عَلَى BRS-NOSP حَيْثُ نَتَخَطَّى خَسارَةِ اللَعْبِ الذاتِيِّ لِدِراسَةِ تَأْثِيرِها.

التَجارِبِ

لُعْبَةِ اللُوجِسْتِيّات

المُعْتَقَلُ المُتَكَرِّرَ

بِاِتِّباعِ (LOLA)، نَدْرُس لُعْبَةِ المُعْتَقَلُ المُتَكَرِّرَ حَيْثُ يُلاحِظ الوُكَلاءِ الإِجْراءاتِ الأَخِيرَةِ الَّتِي اِتَّخَذَها الوُكَلاءِ. وَبِالتالِي، جَمِيعِ المُلاحَظاتِ المُمْكِنَةِ لِلوَكِيل هِيَ \(\mathcal{S} = \{\text{C}, \text{CC}, \text{CD}, \text{DC}, \text{DD}\}\)، حَيْثُ \(C\) هُوَ الحالَةِ الأَوَّلِيَّةِ، وَيُمْكِن وَصَفَ سِياسَةِ كُلِّ وَكِيلُ بِالاِحْتِمالِيَّة لِلتَعاوُنِ لِكُلِّ \(s \in \mathcal{S}\). نَعْتَبِر لُعْبَةِ المُعْتَقَلُ المُتَكَرِّرَ الَّتِي تَسْتَمِرّ لُسْتُ خَطَواتٍ. كَما أَظْهَرَت (LOLA) وَ (POLA)، يُؤَدِّي تَدْرِيبِ وَكِيلَيْنِ يَتَعَلَّمانِ بِشَكْلٍ ساذِجٌ إِلَى إِسْتراتِيجِيّاتِ تَنْتَهِي دائِماً بِالتَخَلِّي عَن التَعاوُنِ. عَلَى الرَغْمِ مِن أَنَّ هٰذا يُمَثِّل تَوازُنٍ ناش، إِلّا أَنَّ كُلّاً الوَكِيلَيْنِ يَتَلَقَّيانِ عَوائِد سَلْبِيَّةٍ.

نَخْتَبِر طَرِيقَتِنا مِن خِلالَ تَدْرِيبِ الوَكِيلَ ضِدَّ مُحَقَّقٍ بَحَثَ الشَجَرَة. يَقُوم مُحَقَّقٍ بَحَثَ الشَجَرَة بِبِناءِ شَجَرَةَ، تَبْدَأ مِن الحالَةِ الحالِيَّةِ. خِلالَ هٰذِهِ العَمَلِيَّةِ، يَتِمّ أَخَذَ إِجْراءاتِ الوَكِيلَ مِن سِياسَةِ الوَكِيلَ، بَيْنَما تَسْتَكْشِف فُرُوعِ الشَجَرَة جَمِيعِ الخِياراتِ المُمْكِنَةِ لِإِجْراءاتٍ المُحَقَّقِ. يَخْتار المُحَقَّقِ الإِجْراءاتِ الَّتِي تُعَظِّم عائِده، أَيّ الإِجْراءاتِ الَّتِي تُشَكِّل أَفْضَلَ مَسارِ اِسْتِجابَةً داخِلَ الشَجَرَة. يَتَلَقَّى الوَكِيلَ العائِدِ الَّذِي يَتَوافَق مَعَ هٰذا المَسارُ بِالذاتِ (أَنْظُر §[app:tree] لِلتَفاصِيل). وَكِيلنا هُوَ شَبَكَةِ عَصَبِيَّةُ مُتَعَدِّدَةِ الطَبَقاتِ ذاتِ طَبَقَتَيْنِ تَتَلَقَّى الحالاتِ الخَمْسِ المُمْكِنَةِ وَتَخْرُج اِحْتِمالَيْهِ التَعاوُنِ. نَخْتار شَبَكَةِ عَصَبِيَّةُ مُتَعَدِّدَةِ الطَبَقاتِ لِعَرْضِ إِمْكانِيَّةَ تَدْرِيبِ الشَبَكاتِ العَصَبِيَّةِ عَبْرَ BRS. نَحْدُث سِياسَةِ وَكِيلنا عَبْرَ تُدْرِج السِياسَةِ. كَما هُوَ مُوَضِّح فِي الشَكْلِ [fig:cobalt_ipd]، يَتَعَلَّم وَكِيلُ BRS سِياسَةِ tit-for-tat (TFT).

لُعْبَةِ العُمْلَةِ

نَتْبَع (POLA) فِي تَدْرِيبِ وَكِيلُ GRU (gated recurrent unit) عَلَى لُعْبَةِ العُمْلَةِ بِحَجْمِ \(3 \times 3\) وَطُول لُعْبَةِ يَبْلُغ \(50\) وَعامِلٌ تَخْفِيضِ يَبْلُغ \(0.96\). الخَصْمِ المُحَقَّقِ هُوَ أَيْضاً وَكِيلُ GRU مَعَ MLP (multi-layer perceptron) يَعْتَمِد عَلَى نَتِيجَةَ ال QA (question answering) (لِمَزِيدٍ مِن التَفاصِيلِ أَنْظُر \(\S\ref{app:details}\)). نَقُوم بِتَقْيِيم وُكَلاءُ BRS وَPOLA ضِدَّ أَرْبَع سِياساتِ: خَصْمِ يَأْخُذ دائِماً أَقْصَرُ طَرِيقِ نَحْوَ العُمْلَةِ بِغَضِّ النَظَرِ عَن لَوْنِ العُمْلَةِ (يَخْتار دائِماً العَيْبِ)، خَصْمِ يَأْخُذ أَقْصَرُ طَرِيقِ نَحْوَ عَمِلَتْهُ المُرْتَبِطَةِ وَلٰكِن لا يَلْتَقِط أَبْدَأ عُمْلَةَ الوَكِيلَ المُرْتَبِطَةِ (يَتَعاوَن دائِماً)، خَصْمِ Monte Carlo Tree Search الَّذِي يُقِيم تَعَدُّدِ تَدَحْرُجات اللُعْبَةِ ضِدَّ الوَكِيلَ لِاِتِّخاذِ إِجْراءِ (MCTS)، وَنَفْسه (الذاتِ). لاحَظَ أَنَّ MCTS سَيَقْرُب الخَصْمِ الأَفْضَلِ اِسْتِجابَةً.

هَل يَتَعاوَن الخَصْمِ الأَفْضَلِ اِسْتِجابَةً مَعَ الوَكِيلَ؟ بِالنِسْبَةِ لِبِيئَةٍ مُعَيَّنَةٍ، سَيَتَعَلَّم الخُصُومِ الاِسْتِجابَةُ الأَفْضَلِ لَوَكِيلنا. نُرِيد مِن هٰؤُلاءِ الخُصُومِ أَنَّ يَكْتَشِفُوا أَنَّهُم لا يُمْكِن أَنَّ يَكُونُوا أَفْضَلَ مِن التَعاوُنِ دائِماً ضِدَّ. بِمَعْنَى آخَرِ، العَيْبِ ضِدَّ وَكِيلنا سَيَقْلِل مِن عائِدهم. MCTS يَقْرُب الخَصْمِ الأَفْضَلِ اِسْتِجابَةً. كَما هُوَ مُوَضِّح فِي الشَكْلِ، MCTS وَBRS يَتَعاوَنانِ دائِماً مَعَ بِعَضِّهِما البَعْضُ. عَلَى النَقِيض مِن ذٰلِكَ، MCTS لا يَتَعاوَن بِشَكْلٍ كامِلٍ مَعَ POLA. MCTS حَصَلَ عَلَى عائِدٌ أَعْلَى مِن التَعاوُنِ دائِماً ضِدَّ POLA عَن طَرِيقِ العَيْبِ.

هَل يَرُدّ الوَكِيلَ عَلَى الاِخْتِيارُ دائِماً بِالعَيْب؟ إِذا لَم يَرُدّ الوَكِيلَ أَبْدَأ عَلَى الاِخْتِيارُ دائِماً بِالعَيْب، فَإِنَّ أَقْصَى عائِدٌ لَهُ سَيَكُون قَرِيباً مِن التَعاوُنِ دائِماً ضِدَّ الاِخْتِيارُ دائِماً بِالعَيْب وَالَّذِي يَبْلُغ \(-0.31\). BRS يَحْصُل عَلَى عائِدٌ مُتَوَسِّطُ يَبْلُغ \(-0.11\) ضِدَّ الاِخْتِيارُ دائِماً بِالعَيْب مِمّا يُشِير إِلَى أَنَّهُ يَرُدّ عَلَى العُيُوبِ. وَمَعَ ذٰلِكَ، POLA يَحْصُل عَلَى \(-0.03\) ضِدَّ الاِخْتِيارُ دائِماً بِالعَيْب مِمّا يُشِير إِلَى رَدٍّ فِعْلٍ أَقْوَى.

هَل يَتَعاوَن الوَكِيلَ مَعَ نَفْسِهِ؟ كَما هُوَ مُوَضِّح فِي الشَكْلِ، وُكَلاءُ BRS يَحْصُلُونَ عَلَى عائِدٌ يَبْلُغ \(0.33\) ضِدَّ أَنْفُسِهِم وَهُوَ قَرِيبٍ جِدّاً مِن عائِدٌ التَعاوُنِ دائِماً ضِدَّ التَعاوُنِ دائِماً الَّذِي يَبْلُغ \(0.34\). وُكَلاءُ POLA يَحْصُلُونَ عَلَى عائِدٌ يَبْلُغ \(0.23\) ضِدَّ أَنْفُسِهِم مِمّا يُشِير إِلَى تَعاوُنٍ أَقَلَّ. بِاِخْتِصار، وُكَلاءُ BRS أَكْثَرَ مُلاءَمَةِ كَسِياسَةٍ تَعاوُنِيَّةِ اِنْتِقامِيَّةٍ. بَيْنَما الاِسْتِجابَةُ الأَفْضَلِ لَهُم هِيَ دائِماً التَعاوُنِ، فَإِنَّهُم أَيْضاً يَتَعاوَنُونَ بِشَكْلٍ كامِلٍ مَعَ أَنْفُسِهِم. عَلَى النَقِيض مِن ذٰلِكَ، الاِسْتِجابَةُ الأَفْضَلِ لَوُكَلاء POLA لَيِسَت تَعاوُناً كامِلاً، وَأَيْضاً لا يَتَعاوَنُونَ بِشَكْلٍ كامِلٍ مَعَ أَنْفُسِهِم.

تَجْرِيد ذاكِرَةِ التَكْرارِ

كَما هُوَ مُوَضِّح فِي الخوارزميه [algo:cobalt]، نَقُوم بِتَدْرِيبِ المُحَقَّقِ ضِدَّ الوُكَلاءِ المَأْخُوذَيْنِ مِن ذاكِرَةِ التَكْرارِ. كَما نُضِيف ضَوْضاء صَغِيرَةٌ إِلَى مُعامَلاتِ الوَكِيلَ المَأْخُوذَةِ. فِي الشَكْلِ [fig:coin_ablation] نَعْرِض BRS-NORB الَّذِي يَمْتَلِك نَفْسِ إِعْدادِ التَدْرِيبِ كَما فِي BRS بِدُونِ ذاكِرَةِ التَكْرارِ وَبِدُونِ ضَوْضاء. بَيْنَما يَمْتَلِك BRS-NORB تَبايُناً أَعْلَى فِي الأَداءِ مُقارَنَةً ب BRS، إِلّا أَنَّ أَداؤه قَرِيبٍ مِن BRS.

اِسْتِبْعادِ اللَعْبِ الذاتِيِّ

وَجَدْنا أَنَّ نِظامِ الاِسْتِجابَةُ السُلُوكِيَّة مَعَ عَدَمِ وُجُودِ لَعِبَ ذاتِيٍّ (نِظامِ الاِسْتِجابَةُ السُلُوكِيَّة-بِدُونِ لَعِبَ ذاتِيٍّ) يَتَعَلَّم سِياساتِ تُشْبِه الاِبْتِزاز المُحَدَّدِ لِلصِفْر (zd)، وَالَّتِي تَسْتَغِلّ عَقْلانِيَّةُ الخَصْمِ لِزِيادَةِ عائِدهم وَلا تَتَعاوَن مَعَ نَفْسِها (التَفاصِيلِ فِي §[app:self-play-ablation]) مِمّا يَجْعَلها غَيْرِ مِثالِيَّةٍ لِلسِينارِيُوهات الَّتِي تَكُون فِيها الرَفاهِيَّةِ الاِجْتِماعِيَّةِ مُهِمَّةً.

القُيُودِ

يُرَكِّز هٰذا البَحْثِ عَلَى تَطْبِيقِ فَكُرَتنا المُقْتَرَحَةِ فِي الأَلْعابُ ثُنائِيَّةٍ اللاعِبِينَ. تَوْسِيعِ هٰذا النَهْجِ لِأَكْثَرِ مِن لاعِبِينَ اِثْنَيْنِ لَيِسَ بِالأَمْرِ إِلٰهَيْنِ¹. بِالإِضافَةِ إِلَى ذٰلِكَ، يَقُوم العامِلِ المُحَقَّقِ بِتَقْرِيب أَفْضَلَ اِسْتِجابَةً لِلمُنافِس مِن خِلالَ التَدْرِيبِ ضِدَّ مَجْمُوعَةِ مُتَنَوِّعَةٍ مِن العُمَلاءِ. فِي هٰذِهِ الدِراسَةُ، نُقَدِّم مَخْزَنٍ إِعادَةِ التَشْغِيلِ الَّذِي يَحْتَوِي عَلَى العُمَلاءِ السابِقِينَ الَّذِينَ تَمَّ مُواجَهَتِهِم أَثْناءَ التَدْرِيبِ كَبَدِيل لِمَجْمُوعَةِ العُمَلاءِ المُتَنَوِّعَةَ. فِي [sec:rb_ablation] أَظْهَرَنا أَنَّ اِسْتِجابَةً الأَفْضَلِ تَعْمَل حَتَّى بِدُونِ مَخْزَنٍ إِعادَةِ التَشْغِيلِ فِي لُعْبَةِ العُمْلَةِ. وَمَعَ ذٰلِكَ، لِلإِعْدادات الأَكْثَرَ تَعْقِيداً، قَد لا تَكُون هٰذِهِ المُسْتَوَى مِن التَنَوُّعِ كافِيَةٍ.

الخُلاصَةِ

مَدْفُوعَيْنِ بِالتَعَلُّم مَعَ الوَعْيِ بِالتَعَلُّم كَإِطار لِتَعْلَم سِياساتِ التَعاوُنِ المَبْنِيَّةُ عَلَى المُعامَلَةِ بِالمِثْلِ، قَدَّمْنا BRS. يَتَمَيَّز BRS مِن خِلالَ خَصْمِ يُقَدَّر أَفْضَلَ اِسْتِجابَةً مُمْكِنَةٍ. لَتَمْكِين الخَصْمِ مِن التَكَيُّفِ مَعَ سِياسَةِ العامِلِ، قَدَّمْنا آلِيَّةِ تَكْيِيفَ جَدِيدَةٍ قابِلَةٍ لِلتَفاضُل وَمُدْرِكه لِلحالَةِ. بِالإِضافَةِ إِلَى ذٰلِكَ، تَمَّ دَمْجِ اللَعْبِ الذاتِيِّ لَتَقْيِيد مِساحَةِ البَحْثِ لِلسِياساتِ التَعاوُنِيَّة الذاتِيَّةِ. قُمْنا بِتَقْيِيم وُكَلاءُ BRS بِالتَفْصِيلِ فِي لُعْبَةِ العُمْلَةِ. يَصِل وَكِيلُ BRS إِلَى سِياسَةِ حَيْثُ التَعاوُنِ الدائِمِ هُوَ أَفْضَلَ اِسْتِجابَةً. نَأْمَل أَنَّ يُساعِد هٰذا العَمَلِ فِي تَحْسِينِ قابِلِيَّةِ التَوَسُّعِ وَعَدَمِ الاِسْتِغْلالِ لِلوُكَلاء فِي تَعْلَم تَعْزِيزِ الوُكَلاءِ المُتَعَدِّدَيْنِ مِمّا يُمْكِن الوُكَلاءِ الَّذِينَ يَتَعَلَّمُونَ التَعاوُنِ المَبْنِيَّ عَلَى المُعامَلَةِ بِالمِثْلِ فِي الأَلْعابُ المُعَقَّدَةِ.

الشُكْرِ وَالتَقْدِيرِ

نَوَدّ أَنَّ نَتَقَدَّم بِالشُكْر إِلَى مَيْلاً وكومبيوت كَنَدا لِتَوْفِيرِ المَوارِدِ الحِسابِيَّة المُسْتَخْدَمَةِ فِي هٰذِهِ الوَرَقَةَ. نَوَدّ أَنَّ نَشْكُر اوليكسا بيلانيوك عَلَى دَعْمِهِ التَقْنِيِّ الثَمِين طِوالَ المَشْرُوعِ. نَعْتَرِف بِالدَعْمِ المالِيِّ مِن شَرِكَةِ هيتاشي المَحْدُودَةَ، كُرْسِيِّ آرُون سَيُفار الكَنَدِيُّ لِلذَكاء الاِصْطِناعِيِّ وَكُرْسِيّ أَبْحاثٍ كَنَدا فِي تَعْلَم التَمْثِيلات الَّتِي تُعَمِّم بِشَكْلٍ مَنْهَجِيٍّ. نَوَدّ أَنَّ نَشْكُر نِظامِ جاكس (jax2018github).

تَفاصِيلَ التَجْرِبَةِ

تَجارِبِ الاِنْحِراف السَجْنَى المُتَكَرِّرَ

فِي تَجارِبِ الاِنْحِراف السَجْنَى المُتَكَرِّرَ، نَقُوم بِإِجْراءِ التَجارِبِ عَلَى الاِنْحِراف السَجْنَى المُتَكَرِّرَ مَعَ 6 خَطَواتٍ وَعامِلٌ تَخْفِيضِ قَدَّرَهُ 1.، أَيّ بِدُونِ عامِلٍ تَخْفِيضِ. تُظْهِر مَصْفُوفه الأَرْباح لِلُعْبَةِ الاِنْحِراف السَجْنَى فِي [tab:prisoners-dilemma].

سِياسَةِ الوَكِيلَ مُعَلِّمَةُ بِواسِطَةِ شَبَكَةِ الإِدْراك المُتَعَدِّدِ الطَبَقاتِ (Multi-Layer Perceptron) ذاتِ طَبَقَتَيْنِ مَعَ عَدَمِ خَطَّيْهِ \(\text{tanh}\). تَمَّ اِخْتِيارِ عَدَمِ الخَطِيَّة \(\text{tanh}\) بِسَبَبِ تَأْثِيرِها المُلَطِّف وَقُدْرَتَها عَلَى مَنْعِ التَحْدِيثات الكَبِيرَةِ لِلتَدَرُّج.

أَثْناءَ التَدْرِيبِ، يَتِمّ تَدْرِيبِ الوَكِيلَ ضِدَّ المُحَقَّقِ البَحْثِيّ الشجري (Tree Search Detective) (أَنْظُر المُلْحَقِ [app:tree]) بِاِسْتِخْدامِ مُقَدَّر التَدَرُّج السِياسِيِّ. نَسْتَخْدِم مُعَدَّلِ تَعْلَم قَدَّرَهُ 3e-4 مَعَ مُحْسِن الاِنْحِدارِ العَشْوائِيِّ التَدْرِيجِيِّ (Stochastic Gradient Descent). فِي تَجارِبِ اللَعْبِ الذاتِيِّ مَعَ خَسارَةِ مُشارَكَةِ المُكافَأَةَ، يَتِمّ التَحْسِين بِاِسْتِخْدامِ الاِنْحِدارِ العَشْوائِيِّ التَدْرِيجِيِّ بِنَفْسِ مُعَدَّلِ التَعَلُّمِ 3e-4. لِتَقْلِيلِ التَبايُنِ، تَتَضَمَّن تَدَرُّجات السِياسَةِ قاعِدَةِ أَساسِيَّةٍ.

لِتَكْرارِ النَتائِجِ الدَقِيقَةِ المُقَدَّمَةِ فِي الوَرَقَةَ، نُوَفِّر الكود فِي المُلْحَقِ [app:reproduce]. مِن المُتَوَقَّعِ أَنَّ يَسْتَغْرِق تَشْغِيلِ الكود عَلَى وَحْدَةِ مُعالَجَةِ الرُسُومات A100 حِوالِي ساعَةً. يَتِمّ توسيط الرُسُومِ البَيانِيَّةِ وَشَرِيط الخَطَأ عَلَى 10 بُذُورِ لِكُلِّ مِن تَجارِبِ اللَعْبِ الذاتِيِّ وَاللَعْبِ الذاتِيِّ بِدُونِ مُشارَكَةِ المُكافَأَةَ. تَمَّ إِجْراءِ البَحْثِ عَن المُعَلِّماتُ الفائِقَةِ مِن خِلالَ التَكْرارِ عَلَى مُعَدَّلاتِ التَعَلُّمِ المُخْتَلِفَةِ بِما فِي ذٰلِكَ (1e-4, 3e-4, 1e-3)، وَتَمَّ اِسْتِكْشافٍ المُحَسِّنات بَيِّنَ الاِنْحِدارِ العَشْوائِيِّ التَدْرِيجِيِّ وَآدَم.

لُعْبَةِ العُمْلَةِ

اللُعْبَةِ تَتْبَع تَنْفِيذِ لُعْبَةِ العُمْلَةِ لَدَينا بِالضَبْطِ تَنْفِيذِ (POLA). مِثْلَ (POLA)، نُجْرِي أَيْضاً تَجارِبِ عَلَى طُولِ اللُعْبَةِ الَّذِي يَبْلُغ 50 وَعامِلٌ الخَصْمِ الَّذِي يَبْلُغ 0.96.

هَنْدَسَةُ الوَكِيلَ فِي لُعْبَةِ العُمْلَةِ، لَدَينا إِعْدادِ مُمَثِّلُ-ناقِد. يَتِمّ تَحْدِيدِ سِياسَةِ وَكِيلنا بِواسِطَةِ هَنْدَسَةُ وَحْدَةِ البَوّابَة المُتَكَرِّرَةِ، بِاِتِّباعِ النَهْجِ المُوَضِّح فِي مُسْتَوْدَع (POLA) (المَصْدَرُ). وَمَعَ ذٰلِكَ، نُقَدِّم تَعْدِيلاً مُقارَنَةً ب (POLA) مِن خِلالَ تَضْمِينِ شَبَكَةِ مُتَعَدِّدَةِ الطَبَقاتِ ذاتِ طَبَقَتَيْنِ فَوْقَ المُلاحَظاتِ قِبَلَ إِدْخالُها فِي وَحْدَةِ البَوّابَة المُتَكَرِّرَةِ بَدَلاً مِن شَبَكَةِ مُتَعَدِّدَةِ الطَبَقاتِ ذاتِ طَبَقَةٌ واحِدَةٍ. بِالإِضافَةِ إِلَى ذٰلِكَ، نَسْتَخْدِم رَأْسَيْنِ خَطِّيَّيْنِ لِتَسْهِيلِ التَعَلُّمِ المُنْفَصِل لِلسِياسَةِ وَتَقْدِيرٍ القِيمَةِ.

هَنْدَسَةُ المُحَقَّقِ تَتْبَع هَنْدَسَةُ المُحَقَّقِ كَما يَلِي: يَتِمّ إِدْخالُ تَسَلْسُلُ المُلاحَظاتِ فِي وَحْدَةِ البَوّابَة المُتَكَرِّرَةِ، وَهِيَ نَفْسِ الهَنْدَسَةِ المُسْتَخْدَمَةِ مِن قِبَلَ الوَكِيلَ. فِي كُلِّ خَطْوَةٍ زَمَنِيَّةٍ، يَتِمّ اِسْتِخْراج تَمْثِيلِ الوَكِيلَ بِاِسْتِخْدامِ وَحْدَةِ الأَسْئِلَةِ وَالأَجْوِبَة لِلمُحَقِّق. فِي تَجارِبنا، اُسْتُخْدِمْنا 16 عَيِّنَةً لِمُواصَلَةِ اللُعْبَةِ لِلخَطَوات الأَرْبَعِ التالِيَةِ مِن الحالَةِ الحالِيَّةِ. بُعْدَ ذٰلِكَ، يَتِمّ دَمْجِ مُخْرِجات وَحْدَةِ الأَسْئِلَةِ وَالأَجْوِبَة وَوَحْدَةِ البَوّابَة المُتَكَرِّرَةِ وَتَمْرِيرها مِن خِلالَ شَبَكَةِ مُتَعَدِّدَةِ الطَبَقاتِ ذاتِ طَبَقَتَيْنِ مَعَ عَدَمِ خَطِيّات (ReLU). يَتِمّ بُعْدَ ذٰلِكَ إِدْخالُ المُخْرِجُ الناتِجِ مِن هٰذِهِ الشَبَكَةِ المُتَعَدِّدَةِ الطَبَقاتِ فِي طَبَقَةٌ خَطَّيْهِ لَتَقْدِير القِيمَةِ (الناقِد)، وَطَبَقَة خَطَّيْهِ لِتَحْدِيدِ السِياسَةِ (المُمَثِّلُ).

مُحَسِّنات مُنْفَصِلَةٍ للمصطلحين يَسْتَخْدِم الوَكِيلَ مُحَسِّنات مُنْفَصِلَةٍ للمصطلحين فِي تُدْرِج السِياسَةِ. أَيّ أَنَّهُ يَسْتَخْدِم مُحَسِّنَيْنِ مُنْفَصِلَيْنِ للمصطلحين المُشارِ إِلَيهِما فِي [eq:agent-update-sep]. \[\underset{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_2}}{\mathbb{E}} \left[R^{1}(\tau) \sum_{t=1}^{T} \left[\underbrace{\nabla_{\theta_1} \log(\pione(a_{t}|s_t))}_{\text{المُصْطَلَحِ 1}} + \underbrace{\nabla_{\theta_1}\log(\pitwo(b_{t}|\pi_{\theta_1}, s_t))}_{\text{المُصْطَلَحِ 2}}\right]\right] \label{eq:agent-update-sep}\]

الخَسائِرِ وَالمُحَسِّنات يَتِمّ تَدْرِيبِ دَوال القِيمَةِ فِي أَعْدادنا بِاِسْتِخْدامِ خَسارَةِ (Huber). مِن ناحِيَةٍ أُخْرَى، يَتِمّ تَدْرِيبِ السِياساتِ بِاِسْتِخْدامِ خَسارَةِ تُدْرِج السِياسَةِ القِياسِيَّةِ مَعَ تَقْدِيرٍ المِيزَة المُعَمَّمَ (GAE) (gae). وَمَعَ ذٰلِكَ، مِن المُهِمِّ مُلاحَظَةُ أَنَّ بَحَثْنا عَن المُعَلِّماتُ الفائِقَةِ أَدَّى بِنا إِلَى ضَبْطِ مَعامِلِ (GAE)، \(\lambda\)، عَلَى 1، مِمّا يُؤَدِّي إِلَى تَقْدِيرٍ مُكافِئ لِلمِيزَة بِاِسْتِخْدامِ التَقْدِيرِ (Monte-Carlo). هٰذا الاِخْتِيارُ مُشابِهٍ لِلمُعَلِّمات الفائِقَةِ الَّتِي أَبْلَغَ عَنها (POLA) (المَصْدَرُ).

فِي تَجارِبِ (BRS-NOSP)، يَتِمّ تَدْرِيبِ سِياسَةِ الوَكِيلَ بِاِسْتِخْدامِ مُعَدَّلِ تَعْلَم يَبْلُغ 1e-3، بَيْنَما فِي تَجارِبِ (BRS)، يَتِمّ اِسْتِخْدامِ مُحْسِن (Adam) مَعَ مُعَدَّلِ تَعْلَم يَبْلُغ 3e-4. يَتِمّ تَدْرِيبِ دَوال القِيمَةِ لِكُلِّ مِن الوَكِيلَ وَالمُحَقِّق فِي جَمِيعِ التَجارِبِ بِاِسْتِخْدامِ (Adam) مَعَ مُعَدَّلِ تَعْلَم يَبْلُغ 3e-4. بِالمِثْلِ، يَتِمّ تَدْرِيبِ سِياسَةِ المُحَقَّقِ بِاِسْتِخْدامِ (Adam) مَعَ مُعَدَّلِ تَعْلَم يَبْلُغ 3e-4 فِي جَمِيعِ التَجارِبِ.

مَخْزَنٍ إِعادَةِ تَشْغِيلِ الوُكَلاءِ السابِقِينَ خِلالَ التَدْرِيبِ، نَحْتَفِظ بِمَخْزَن إِعادَةِ تَشْغِيلِ لِلوُكَلاء السابِقِينَ الَّذِينَ تَمَّ رُؤْيَتِهِم خِلالَ التَدْرِيبِ. فِي تَجارِبِ (BRS-NOSP) نَحْتَفِظ ب 2048 وَكِيلا سابِقاً وَفِي تَجارِبِ (BRS) نَحْتَفِظ بِآخَر 512 وَكِيلا. لِتَدْرِيبِ المُحَقَّقِ، نَقُوم بِأَخْذِ عَيِّنَةً مِن هٰذا المَخْزَن بِشَكْلٍ مُوَحَّدٍ. نُضِيف ضَوْضاء عادِيَّةٍ بِتَبايُن يَبْلُغ 0.01 إِلَى مُعَلِّمات هٰؤُلاءِ الوُكَلاءِ لِضَمانِ تَدْرِيبِ المُحَقَّقِ ضِدَّ مَجْمُوعَةِ مُتَنَوِّعَةٍ مِن الوُكَلاءِ.

بَحَثَ المُعَلِّماتُ الفائِقَةِ أَجْرَيْنا بَحْثاً عَن المُعَلِّماتُ الفائِقَةِ بِاِسْتِخْدامِ البَحْثِ العَشْوائِيِّ عَلَى الإِعْدادات المُوَضِّحَة فِي الجَدْوَلُ [tab:hyperparameters]. يَتِمّ إِضافَةً مَعامِلِ الانتروبيا \(\beta\)، الَّذِي يُضْرَب بانتروبيا الاِحْتِمالاتِ اللوغاريتميه المُرْتَبِطَةِ بِأَفْعال اللاعِبَ المُقابِلِ، إِلَى خَسارَةِ تُدْرِج السِياسَةِ لِلاعِبِ المُقابِلِ لِلتَحَكُّمِ فِي التَوازُنِ بَيِّنَ الاِسْتِكْشافِ وَالاِسْتِغْلالِ.

الرُسُومِ البَيانِيَّةِ وَأَشْرِطَةَ الخَطَأ تَمَّ حِسابِ النَتائِجِ فِي الوَرَقَةَ عَلَى ثَلاثِ بُذُورِ لِ (BRS), (BRS-NOSP), (BRS-NOSP-NORB), وَ (BRS-NOSP-NORB) وَسِتُّ بُذُورِ لِ (POLA). مِن الجَدِيرِ بِالذَكَر أَنَّ أَشْرِطَةِ الخَطَأ تَحَسُّب عَلَى البُذُورِ، أَيّ النِقاطِ الفاصِلَةُ. يَتِمّ توسيط نَتِيجَةَ الأَلْعابُ بَيِّنَ كُلِّ زَوْج مِن الوُكَلاءِ عَلَى 32 لُعْبَةِ مُسْتَقِلَّةٍ بَيِّنَ هٰذَيْنِ الوَكِيلَيْنِ.

الحوسبه تُجْرَى تَشْغِيلاتنا لِمُدَّةِ 48 ساعَةً عَلَى وَحْدَةِ مُعالَجَةِ الرُسُومات (A100) بِسَعَةِ 40 غيغابايت مِن الذاكِرَةِ².

حَجْمِ الدُفْعَةِ نَسْتَخْدِم حَجْمِ دَفْعَةً يَبْلُغ 128.

تَدْرِيبِ وُكَلاءُ (POLA) لَتَقْيِيم وُكَلاءُ (POLA)، قُمْنا بِتَدْرِيبهم مِن خِلالَ تَنْفِيذِ مُسْتَوْدَع (POLA) هُنا (POLA).

إِعادَةِ إِنْتاجِ النَتائِجِ

المُعْتَقَلُ المُتَكَرِّرَ

لِتَكْرارِ النَتائِجِ عَلَى المُعْتَقَلُ المُتَكَرِّرَ، يُرْجَى الرُجُوعِ إِلَى التَعْلِيماتِ المُتَوَفِّرَةِ هُنا. مِن خِلالَ تَشْغِيلِ دَفْتَرِ اليَوْمِيّات Colab المُقَدَّمُ، سَتَحْصُل عَلَى رَسْمِ بَيانَيَّ لِلمُعْتَقَل المُتَكَرِّرَ الَّذِي يَتَضَمَّن فِي الوَرَقَةَ.

لُعْبَةِ العُمْلَةِ

لِتَكْرارِ نَتائِجِ لُعْبَةِ العُمْلَةِ، يُرْجَى الرُجُوعِ إِلَى التَعْلِيماتِ المُتَوَفِّرَةِ هُنا. بِشَكْلٍ أَساسِيٌّ، تَشْمَل الإِرْشادات المُقَدَّمَةِ سكربتات تَدْرِيبِ مُصَمِّمَةً لَغَرَض تَدْرِيبِ نِقاطٍ التَفْتِيشِ لِلوُكَلاء. بُعْدَ ذٰلِكَ، هُناكَ مَرْحَلَةِ تَصْدِيرِ يَتِمّ فِيها تَحْوِيلِ هٰذِهِ النِقاطِ إِلَى نَظائِرها الخَفِيفَةِ. وَأَخِيرا، يَتِمّ تَوْفِيرِ سكربت لِتَسْهِيلِ تَنْفِيذِ دَوْرِيِّ يَضُمّ عِدَّةٍ وُكَلاءُ. [app:curves]

نَتائِجِ الدَوْرِيِّ

لِتَصْوِيرِ نَتائِجِ تَدْرِيبنا بِشَكْلٍ مُفَصَّلٍ، نَعْرِض فِي الشَكْلِ [fig:league] مَصْفُوفه عَلَى شَكْلٍ خَرِيطَةِ حَرارِيَّةٍ لَعَوائِد وُكَلاءُ مُخْتَلِفِينَ فِي مُواجَهَةِ بِعَضُّهُم البَعْضُ. جَمِيعِ النَتائِجِ مُعَدَّله عَلَى أَساسِ 32 لُعْبَةِ مُسْتَقِلَّةٍ بَيِّنَ الوُكَلاءِ المَعْنِيِّينَ. اللُعْبَةِ هِيَ لُعْبَةِ العُمْلَةِ بِطُولِ 50. ³

اللَعْبِ الذاتِيِّ

النَظَرِيَّةِ D.1. لِيَكُن \(o \in \mathcal{S}\) هُوَ الحالَةِ \(s \in \mathcal{S}\) مِن مَنْظُورٍ الخَصْمِ. بِالنِسْبَةِ لِلُعْبَةِ مُتَماثِله، إِذا كانَ يُحَقِّق أَنَّ \(\mu(s_0) = \mu(o_0)\) لِجَمِيعِ \(s_0, o_0 \in \mathcal{S}\)، فَإِنَّ \[\begin{aligned} \expectAA \left[ R^1(\tau)\right] &= \expectAA \left[ R^2(\tau)\right]\end{aligned}\] حَيْثُ \(R^2 := \sum_{t=0}^\infty \gamma^t r^2(o_t, b_t, a_t)\) وَ \(r^2\) يُشِير إِلَى \(r^1\) مِن مَنْظُورٍ الخَصْمِ. البُرْهانُ. لِيَكُن \(\Bar{\tau} = o_0, b_0, a_0, o_1, \hdots\)، ثُمَّ لاحَظَ أَنَّ \[\begin{aligned} \mu(s_0)\piAa{0}\piAb{0} P(s_1|s_0,a_0,b_0)\hdots &= \mu(o_0)\piAb{0}\piAa{0} P(o_1|o_0,b_0,a_0)\hdots\\ \iff \prmuAA(\tau) &= \prmuAA(\Bar{\tau})\end{aligned}\] الآنَ بِمُوجِبِ التَماثُلِ لَدَينا أَنَّ \(r^1(s_t, a_t, b_t) = r^2(o_t, b_t, a_t)\)، وَبِالتالِي \[\begin{aligned} \E_{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_1}} \left[R^1(\tau)\right] &= \E_{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_1}} \left[\sum_{t=0}^\infty \gamma^t r^1(s_t, a_t, b_t)\right]\\ &= \sum_{\tau} \text{Pr}_\mu^{\theta_1, \theta_1}(\tau) \sum_{t=0}^\infty \gamma^t r^1(s_t, a_t, b_t)\\ &= \sum_{\Bar{\tau}} \text{Pr}_\mu^{\theta_1, \theta_1}(\Bar{\tau}) \sum_{t=0}^\infty \gamma^t r^2(o_t, b_t, a_t)\\ &=\E_{\tau \sim \text{Pr}_\mu^{\theta_1, \theta_1}} \left[R^2(\tau)\right]\end{aligned}\] حَيْثُ نَقُوم فَقَط بِإِعادَةِ تَسْمِيَةِ \(\Bar{\tau}\) فِي المُساواةُ الأَخِيرَةِ. \(\blacksquare\) الاِقْتِراحِ D.2 يَنُصّ عَلَى أَنَّ التَدَرُّج فِي المُعادَلَةَ [eqn:selfplayrewardsharing] مُكافِئ لِذٰلِكَ فِي اللَعْبِ الذاتِيِّ مَعَ مُشارَكَةِ المُكافَأَةَ.

الاِقْتِراحِ D.2. بِالنِسْبَةِ لِلُعْبَةِ مُتَماثِله، \[\begin{aligned} \nablaA \expectAA \left[ R^1(\tau)\right] \propto \left[ \nablaA \expectAB \left[ R^1(\tau) + R^2(\tau)\right] + \nablaB \expectAB \left[ R^1(\tau) + R^2(\tau)\right] \right]_{\theta_2=\theta_1}.\end{aligned}\] البُرْهانُ. نَكْتُب التَدَرُّج كَما يَلِي: \[\begin{aligned} \nablaA \expectAA \left[R^1(\tau)\right] \quad &=& &\sum_\tau R^1(\tau) \nablaA \prmuAA(\tau)\\ &=& &\sum_\tau R^1(\tau) \prmuAA(\tau) \nablaA \log \prmuAA(\tau) \\ &=& &\sum_\tau R^1(\tau) \prmuAA(\tau) \sum_{t=0}^\infty \nablaA \log \piAa{t} + \nablaA \log \piAb{t} \\ &=& &\expectAA \left[ R^1(\tau) \sum_{t=0}^\infty \nablaA \log \piAa{t} + \nablaA \log \piAb{t} \right].\end{aligned}\] الآنَ بِمُوجِبِ التَماثُلِ وَالنَظَرِيَّة D.1 لَدَينا \[\begin{aligned} \expectAA \left[ R^1(\tau) \right] &= \expectAA \left[ R^2(\tau) \right],\end{aligned}\] وَبِمُوجِبِ خَطَّيْهِ التَوَقُّعُ، \[\begin{aligned} \expectAA \left[ R^1(\tau) \right] &\propto \expectAA \left[ R^1(\tau) + R^2(\tau) \right].\end{aligned}\] وَمِن ثُمَّ \[\begin{aligned} \nablaA \expectAA \left[R^1(\tau)\right] \quad &\propto& & \expectAA \left[\left(R^1(\tau) + R^2(\tau)\right) \sum_{t=0}^\infty \nablaA\log\piAa{t} + \nablaA\log\piAb{t} \right] \\ &=& &\left[\expectAB \left[\left(R^1(\tau) + R^2(\tau)\right) \sum_{t=0}^\infty \nablaA\log\piAa{t} + \nablaB\log\piBb{t} \right] \right]_{\theta_2=\theta_1} \\ &=& &\left[\expectAB \left[\left(R^1(\tau) + R^2(\tau)\right) \left(\nablaA\log\prmuAB(\tau) + \nablaB\log\prmuAB(\tau)\right) \right] \right]_{\theta_2=\theta_1} \\ &=& &\left[ \nablaA \expectAB \left[R^1(\tau) + R^2(\tau)\right] +\nablaB \expectAB \left[R^1(\tau) + R^2(\tau)\right] \right]_{\theta_2=\theta_1}, \\\end{aligned}\] وَهٰذا ما كانَ يَجِب إِثْباته. \(\blacksquare\) النَتِيجَةُ D.3. بِالنِسْبَةِ لِلُعْبَةِ مُتَماثِله، صِفْرَيْهِ الجَمْع يُحَقِّق أَنَّ \[\begin{aligned} \nablaA \expectAA \left[ R^1(\tau)\right] = 0\end{aligned}\] البُرْهانُ. بِتَعْرِيف اللُعْبَةِ صِفْرَيْهِ الجَمْع، لَدَينا أَنَّ \[\begin{aligned} r^1(s_t, a_t, b_t) + r^2(s_t, b_t, a_t) &= 0\\ \implies \sum_{t=0}^\infty \gamma^t\left(r^1(s_t, a_t, b_t) + r^2(s_t, b_t, a_t)\right) &= 0\\ \iff R^1(\tau) = -R^2(\tau) \text{ لِجَمِيعِ } \tau\end{aligned}\] مِن الاِقْتِراحِ D.2 نَحْصُل \[\begin{aligned} \nablaA \expectAA \left[R^1(\tau)\right]\quad &\propto& &\left[ \nablaA \expectAB \underbrace{\left[R^1(\tau) + R^2(\tau)\right]}_{=0} +\nablaB \expectAB \underbrace{\left[R^1(\tau) + R^2(\tau)\right]}_{=0} \right]_{\theta_2=\theta_1} \\ &=& & \left[ \nablaA 0 + \nablaB 0 \right]_{\theta_2=\theta_1} \\ &=& &0\end{aligned}\] مِمّا يُكْمِل البُرْهانُ. \(\blacksquare\)

اِسْتِئْصال اللَعْبِ الذاتِيِّ

لُعْبَةِ السُجَناءِ المُتَكَرِّرَةِ

فِي لُعْبَةِ السُجَناءِ المُتَكَرِّرَةِ، يَتَعَلَّم الوُكَلاءِ فِي BRS-NOSP نَوْعاً مِن سِياسَةِ الرَدِّ المُتَبادَلِ الَّتِي تَخُون فِي البِدايَةِ وَلٰكِن لَدَيها نَفْسِ اِحْتِمالِ التَعاوُنِ كَما فِي سِياسَةِ الرَدِّ المُتَبادَلِ فِي \(\{\text{CC}, \text{CD}, \text{DC}, \text{DD}\}\). نُسَمَّى هٰذِهِ السِياسَةِ بِسِياسَةِ الرَدِّ المُتَبادَلِ الساخِرُ (CTFT). أَفْضَلَ رَدٍّ عَلَى سِياسَةِ الرَدِّ المُتَبادَلِ الساخِرُ فِي لُعْبَةِ السُجَناءِ المُتَكَرِّرَةِ اللانِهائِيَّةُ هُوَ التَعاوُنِ دائِماً لِأَنَّهُ إِذا خان الخَصْمِ فِي البِدايَةِ، سَيَخُون الوَكِيلَ فِي الدَوْرِ التالِي. كَما أَنَّ CTFT لا تَتَعاوَن مَعَ نَفْسِها.

عِلاوَةً عَلَى ذٰلِكَ، إِذا اُسْتُخْدِمْنا العَوائِد التَفاضُلِيَّةِ التَحْلِيلِيَّة فِي لُعْبَةِ السُجَناءِ المُتَكَرِّرَةِ، يَتَعَلَّم BRS-NOSP سِياسَةِ الاِبْتِزاز ZD (zd) المُشابِهَة لِ(mfos) كَما هُوَ مُوَضِّح فِي الشَكْلِ [fig:brs_nosp_zd]. تَكْتَسِب سِياسَةِ الاِبْتِزاز ZD مِيزَةً مِن خِلالَ الخِيانَةِ بِالقَدْر الَّذِي يَظَلّ فِيهِ أَفْضَلَ رَدٍّ مِن الخَصْمِ هُوَ التَعاوُنِ.

لُعْبَةِ العُمْلَةِ

فِي لُعْبَةِ العُمْلَةِ، يَحْصُل الوُكَلاءِ مِن نَوْعٍ BRS-NOSP عَلَى عائِدٌ مُرْتَفِعٌ ضِدَّ MCTS. وَمَعَ ذٰلِكَ، يَحْصُل خَصْمِ MCTS عَلَى عائِدٌ أَقَلَّ بِكَثِيرٍ ضِدَّ BRS-NOSP مُقارَنَةً ب BRS. هٰذا يَدُلّ عَلَى أَنَّ BRS اِسْتَغَلَّت عَقْلانِيَّةُ MCTS. بَيْنَما يُؤَدِّي MCTS أَفْضَلَ مِن Always Defect ضِدَّ BRS-NOSP، إِلّا أَنَّهُ يُتاجِر بِكَمِّيَّةِ كَبِيرَةٍ مِن التَعاوُنِ لَأَثارَهُ تَعاوُنٍ طَفِيفٍ مِن BRS-NOSP. بِعِبارَةٍ أُخْرَى، يَسْتَغِلّ BRS-NOSP عَقْلانِيَّةُ MCTS. كَما أَنَّ وُكَلاءُ BRS-NOSP لا يَتَعاوَنُونَ مَعَ أَنْفُسِهِم وَيَسْتَغِلُّونَ Always Cooperate.

الكَشْفِ عَن البَحْثِ الشجري

فِي هٰذا القِسْمِ، نِصْفِ الكَشْفِ عَن البَحْثِ الشجري المُسْتَخْدِمُ فِي تَجارِبِ البرُوتُوكُولِ التَفاعُلِيّ المُتَكَرِّرَ. الفِكْرَةِ وَراءَ الكَشْفِ عَن البَحْثِ الشجري هِيَ أَنَّهُ مِن خِلالَ مُحاكاةَ جَمِيعِ المَساراتِ المُمْكِنَةِ بِناءَ عَلَى سِياسَةِ العامِلِ، يُمْكِن لِلخَصْم اِخْتِيارِ المَسارُ الَّذِي يُعَظِّم عَوائِده الخاصَّةِ. وَنَتِيجَةَ لِذٰلِكَ، يُحَقِّق العامِلِ العائِدِ المُرْتَبِطُ بِهٰذا المَسارُ المُحَدَّدِ.

يُنَفِّذ الكَشْفِ عَن البَحْثِ الشجري هٰذِهِ الفِكْرَةِ. يُبْنَى الكَشْفِ عَن البَحْثِ الشجري هَيْكَلِ شَجَرَةَ حَيْثُ يَتِمّ أَخَذَ إِجْراءاتِ العامِلِ مُباشَرَةً مِن سِياسَتِهِ. عِنْدَما يَأْتِي دَوْرِ الكَشْفِ عَن البَحْثِ الشجري فِي العَمَلِ، يَتِمّ تَشْكِيلِ فَرْعِ لِكُلِّ إِجْراءِ لِاِسْتِكْشافِ النَتائِجِ المُحْتَمَلَةِ لِذٰلِكَ الإِجْراءَ المُحَدَّدِ.

سَيُعامِل العامِلِ الكَشْفِ عَن البَحْثِ الشجري كخوارزميه صُنْدُوقِ أَسُود تَسْتَعْلِم عَن سِياسَةِ العامِلِ فِي مَجْمُوعَةِ مِن الحالاتِ وَتُعِيد عائِداً واحِداً، أَيّ العائِدِ الَّذِي يَتَوافَق مَعَ عائِدٌ العامِلِ فِي المَسارُ الَّذِي حَقَّقَ أَعْلَى عائِدٌ لِلكَشْفِ عَن البَحْثِ الشجري. يُمْكِن تَمْيِيزٍ هٰذا الصُنْدُوقِ الأَسْوَدِ مِن خِلالَ مُقَدَّرات تُدْرِج السِياسَةِ. مِن المُهِمِّ مُلاحَظَةُ أَنَّهُ عِنْدَ حِسابِ خَسارَةِ تُدْرِج السِياسَةِ، يَجِب أَخَذَ مَجْمُوعُ جَمِيعِ اِحْتِمالاتِ السِجِلِّ فِي الاِعْتِبارِ، وَلِيس فَقَط تِلْكَ المَوْجُودَةِ فِي المَسارُ المُخْتار. هٰذا أَمْرٌ حاسِمٍ لِأَنَّ إِجْراءاتِ العامِلِ فِي الحالاتِ خارِجَ المَسارُ المُخْتار مُهِمَّةً فِي عَمَلِيَّةِ اِتِّخاذِ قَرارِ الكَشْفِ عَن البَحْثِ الشجري لِاِخْتِيارِ ذٰلِكَ المَسارُ بِالذاتِ.

النَتائِجِ التَفْصِيلِيَّةِ لِلأَلْعابِ بَيِّنَ الوُكَلاءِ

فِي الشَكْلِ المُشارِ إِلَيهِ، قُمْنا بِتَصْوِيرِ مُتَوَسِّطُ نَتائِجِ 32 لُعْبَةِ بَيِّنَ وُكَلاءُ مُخْتَلِفِينَ. لاحَظَ أَنَّهُ بِالنِسْبَةِ لَوُكَلاء BRS اُسْتُخْدِمْنا ثَلاثِ بُذُورِ لِكُلِّ نَوْعٍ مِن الوُكَلاءِ، وَبِالنِسْبَةِ لِ POLA اُسْتُخْدِمْنا سِتَّ بُذُورِ. بِالفِعْلِ، لَدَى وُكَلاءُ POLA تَبايُنٍ أَكْبَرَ فِي أَدائهم لِذٰلِكَ اُسْتُخْدِمْنا المَزِيدِ مِن البُذُورِ لِحِسابِ أَشْرِطَةِ الخَطَأ لَهُم.

الاِبْتِزاز ZD

يَرِي أَنَّ BRS بِدُونِ اللَعْبِ الذاتِيِّ يَتَعَلَّم سِياسَةِ الاِبْتِزاز ZD كَما هُوَ مُتَوَقَّعٌ.

مُنْحَنَيات تَدْرِيبِ BRS وَ BRS-NOSP

نَتائِجِ المُقارَنَةِ بَيِّنَ BRS وَ POLA

فِي هٰذا القِسْمِ، نَتَعَمَّق فِي تَفاصِيلَ المُقارَنَةِ بَيِّنَ POLA وَ BRS. لَقَد قُمْنا بِأَخْذِ عَيِّناتٍ مِن 32 مَسارا بَيِّنَ كُلِّ بِذَرَّةٍ POLA وَكُلُّ بِذَرَّةٍ BRS. بِشَكْلٍ عامَ، لاحَظْنا: 1) بُذُورِ POLA تُظْهِر تَبايُناً أَعْلَى فِي السُلُوكِ. 2) بُذُورِ POLA تَكْسِر حَلْقَةِ التَعاوُنِ أَكْثَرَ بِكَثِيرٍ مِن وُكَلاءُ BRS. 3) وُكَلاءُ POLA يَرُدُّونَ بِضُعْفِ عِنْدَما يَكْسِر وُكَلاءُ BRS التَعاوُنِ بِالتَخَلِّي عَنهُ. بِشَكْلٍ عامَ، هٰذا يَدُلّ عَلَى أَنَّ وُكَلاءُ BRS أَكْثَرَ مُلاءَمَةِ مِن وُكَلاءُ POLA كَوُكَلاء تَعاوُنِيَّيْنِ يَعْتَمِدُونَ عَلَى المُقايَضَةَ.

مُقارَنَةً التَعاوُنِ المَبْنِيَّ عَلَى المُعامَلَةِ بِالمِثْلِ

نَعْتَبِر الآنَ الإِحْصائِيّات التَجْرِيبِيَّة لِلمَسارات المَرْصُودَة بَيِّنَ وُكَلاءُ POLA وَ BRS فِي لُعْبَةِ العُمْلَةِ. هُنا نَعْرِف التَعاوُنِ عَلَى أَنَّهُ دَوْرِ يَتَجَنَّب فِيهِ الخَصْمِ أَخَذَ عُمْلَةَ الوَكِيلَ (وَالعَكْسُ صَحِيحٌ بِالنِسْبَةِ لِلوَكِيل). نَعْرِف لِكُلِّ مِن الخَصْمِ وَالوَكِيلُ الخِيانَةِ عَلَى أَنَّها دَوْرِ يَأْخُذُونَ فِيهِ عُمْلَةَ الآخَرِ.

كَما هُوَ مُوَضِّح فِي الجَدْوَلُ [tab:pola_vs_brs_prob_c] عَلَى عَكْسَ BRS الَّذِي يَبْدَأ تَقْرِيباً دائِماً بِالتَعاوُنِ، يَبْدَأ POLA التَعاوُنِ بِنِسْبَةِ 0.56 مِن الأَوْقات مِمّا يَخْتَلِف عَن سِياسَةِ TFT. يَتَعاوَن كُلِّ مِن POLA وَ BRS بِنِسْبَةِ عالِيَةٍ فِي حالَةِ مُلاحَظَةُ أَنَّ الخَصْمِ قَد تَعاوُنٍ. وَمَعَ ذٰلِكَ، فَإِنَّ سِياسَةِ BRS تَتَعاوَن بِنِسْبَةِ أَعْلَى. يَتَعاوَن كُلِّ مِن POLA وَ BRS بِنِسْبَةِ قَلِيلَةٍ بُعْدَ أَنَّ يُلاحَظُوا أَنَّ الخَصْمِ قَد خان. بَيْنَما يَتَعاوَن POLA بِنِسْبَةِ أَقَلَّ مِن BRS وَهُوَ ما يَبْدُو مَرْغُوبا فِيهِ، يَجِب الإِشارَةُ إِلَى أَنَّ POLA يَزْرَع الخِيانَةِ أَكْثَرَ مُقارَنَةً ب BRS بِشَكْلٍ عامَ. العَمُودِ التالِي يُسَلِّط الضَوْء عَلَى هٰذا. يَجِب أَنَّ تَخُون سِياسَةِ التَعاوُنِ المَبْنِيَّةُ عَلَى المُعامَلَةِ بِالمِثْلِ بُعْدَ أَنَّ تُواجِه تَعاوُنُها بِخِيانَةِ الخَصْمِ. سَيَتَعاوَن POLA 0.70 مَرّاتٍ فِي تِلْكَ المَواقِفِ مِمّا يُشِير إِلَى عَدَمِ وُجُودِ اِنْتِقام قَوِيٍّ. تَتَعاوَن بُذُورِ BRS 0.16 مَرّاتٍ مِمّا يُشِير إِلَى اِنْتِقام قَوِيٍّ. لاحَظَ أَنَّ هٰذِهِ اِحْتِمالاتِ مَشْرُوطَةٌ. كَما هُوَ مُوَضِّح فِي الجَدْوَلُ [tab:pola_vs_brs_freq] فِي هٰذِهِ المَساراتِ ال 32 نُلاحِظ فَقَط 72 مَوْقِفاً حَيْثُ تَعاوُنٍ POLA أَوَّلاً وَخان BRS. فِي 22 مِن هٰؤُلاءِ خان POLA بُعْدَ ذٰلِكَ وَفِي ال 50 الأُخْرَى تَعاوُنٍ POLA. هٰذا مُؤَشِّرُ عَلَى الاِنْتِقامِ الضَعِيفُ. بِالمُقابِلِ، نُلاحِظ 950 مَوْقِفاً حَيْثُ تَعاوُنٍ BRS وَخان POLA. فِي 798 مِن هٰؤُلاءِ، خان BRS بُعْدَ ذٰلِكَ مِمّا يُشِير إِلَى اِنْتِقام قَوِيٍّ. بِشَكْلٍ عامَ، تُظْهِر هٰذِهِ النَتائِجِ أَنَّ وُكَلاءُ POLA مَيّالُونَ نَحْوَ الخِيانَةِ وَأَيْضاً يَنْتَقِمُونَ بِضُعْفِ بَيْنَما يُظْهِر وُكَلاءُ BRS مَيْلاً قَوِيّاً نَحْوَ التَعاوُنِ مَعَ أَظْهار عَلاماتِ قَوِيَّةٍ عَلَى الاِنْتِقامِ عِنْدَما يَخُون الخَصْمِ.

نَتائِجِ الدَوْرِيِّ وَالتَحْلِيلِ

نُلاحِظ أَنَّ وُكَلاءُ نِظامِ الاِسْتِجابَةُ الأَساسِيَّةِ يَتَعاوَنُونَ بِقُوَّةٍ مَعَ أَنْفُسِهِم، وَمَعَ نِظامِ شَجَرَةَ مَوَّنْتُ كارْلُو لِلبَحْثِ، وَمَعَ دائِماً التَعاوُنِ، بَيْنَما يَخْتَلِف سُلُوكِ وُكَلاءُ نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ. نُلاحِظ نَمَطَيْنِ رَئِيسِيَّيْنِ فِي بُذُورِ نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ. نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ-3 وَنِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ-4 اِسْتِغْلالِيّانِ، يَسْتَغِلّانِ بُذُورِ نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ الأُخْرَى وَدائِماً التَعاوُنِ. لٰكِنَّ، لا يُمْكِنهم التَعاوُنِ مَعَ أَنْفُسِهِم. بَيْنَما لا يَتِمّ اِسْتِغْلالَهُم مِن قِبَلَ نِظامِ شَجَرَةَ مَوَّنْتُ كارْلُو لِلبَحْثِ مِن حَيْثُ الحُصُولِ عَلَى عائِدٌ أَقَلَّ مِن نِظامِ شَجَرَةَ مَوَّنْتُ كارْلُو لِلبَحْثِ، يُشِير عائِدهم ضِدَّ نِظامِ شَجَرَةَ مَوَّنْتُ كارْلُو لِلبَحْثِ إِلَى عَدَمِ التَعاوُنِ. نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ-1، نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ-2، نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ-5، وَنِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ-6 أَكْثَرَ تَعاوُناً - حَتَّى التَعاوُنِ مَعَ أَنْفُسِهِم - عَلَى حِسابِ كَوْنِهِم مُسْتَغَلَّيْنِ مِن قِبَلَ بُذُورِ نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ الأُخْرَى وَنِظامِ شَجَرَةَ مَوَّنْتُ كارْلُو لِلبَحْثِ. يَجِب الإِشارَةُ إِلَى أَنَّهُ لِجَمِيعِ بُذُورِ نِظامِ الاِسْتِجابَةُ المُتَقَدِّمَةِ، أَفْضَلَ اِسْتِجابَةً، المُقَدَّرَةِ بِواسِطَةِ وَكِيلُ نِظامِ شَجَرَةَ مَوَّنْتُ كارْلُو لِلبَحْثِ، لَيِسَت دائِماً التَعاوُنِ دائِماً. هٰذا يَتَناقَض مَعَ نِظامِ الاِسْتِجابَةُ الأَساسِيَّةِ الَّذِي لا يَتَعاوَن دائِماً مَعَ نَفْسِهِ فَحَسْب، بَل يُقْنِع أَيْضاً وَكِيلُ نِظامِ شَجَرَةَ مَوَّنْتُ كارْلُو لِلبَحْثِ بِالتَعاوُنِ دائِماً مَعَهُم.