ملخص تقني: إعادة النظر في تحسين السياسة المنتظمة من أجل تعلم تعزيزي مستقر وفعال في الألعاب ثنائية اللاعبين

بيان المشكلة

كانت الألعاب ثنائية اللاعبين صفرية المجموع، ولا سيما ألعاب اللوحات، بمثابة معايير تقليدية للتعلم التعزيزي (RL). وبينما حققت الأساليب القائمة على البحث مثل AlphaZero (Silver et al., 2018) أداءً فائقًا للبشر من خلال الجمع بين الشبكات العصبية العميقة والبحث الاستباقي (مثل بحث شجرة مونت كارلو (MCTS)، وMCTS)، إلا أنها تتسبب في تكاليف حوسبة باهظة. فعلى سبيل المثال، يتطلب تدريب AlphaZero أكثر من 10 سنوات من معالجات الرسوميات (GPU-years) (Silver et et al., 2018; Tian et al., 2019). هذا الاستهلاك الكثيف للموارد يعيق إمكانية إعادة الإنتاج والتطبيق العملي في البيئات محدودة الموارد (Zhao et al., 2022).

وعلى الرغم من أن الدراسات الحديثة حاولت تقليل العبء الحوسبي للأساليب القائمة على البحث عن طريق تحديد عمق الشجرة أو عدد عمليات التمرير (Hessel et al., 2021; Danihelka et al., 2022)، إلا أنها لا تزال تعتمد بشكل أساسي على البحث الاستباقي. وفي المقابل، لم يتم استكشاف أساليب التعلم التعزيزي الخالية من النموذج (model-free RL)، والتي تتميز بالكفاءة في الروبوتات والتحكم المستمر، بشكل كامل في ألعاب اللوحات بسبب عدم الاستقرار المتصور في بيئات اللعب الذاتي متعددة الوكلاء. والسؤال المركزي الذي تعالجه هذه الدراسة هو: هل يمكن لخوارزمية تعلم تعزيزي خالية من النموذج تحقيق تعلم مستقر وتنافسي في الألعاب ثنائية اللاعبين بموارد تدريب أقل بكثير من النظراء القائمين على البحث؟

المنهجية

يقترح المؤلفون خوارزمية KLENT (تحسين السياسة المنتظمة بـ KL والاعتلاج)، وهي خوارزمية تعلم تعزيزي خالية من النموذج تلغي الحاجة إلى MCTS أثناء التدريب. يستند النهج إلى إعادة النظر في تحسين السياسة المنتظمة من خلال مكونين محددين: تنظيم كولباك - ليبلر العكسي (reverse KL) وتنظيم الاعتلاج (entropy regularization).

1. قاعدة تحديث السياسة

جوهر KLENT هو مسألة تحسين سياسة منتظمة محددة بـ:
$$\max_{\pi'} \mathbb{E}_{A \sim \pi'(\cdot|s)}[Q^\pi(s, A)] - \beta D_{KL}(\pi'(\cdot|s) \parallel \pi(\cdot|s)) + \alpha H(\pi'(\cdot|s))$$
حيث أن:

• $\pi'$ هي السياسة الجديدة، و $\pi$ هي السياسة السابقة.
• $D_{KL}(\pi' \parallel \pi)$ هو تباعد كولباك - ليبلر العكسي، الذي يعزز التحديثات التدريجية للسياسة للتعامل مع عدم الاستقرار في اللعب الذاتي.
• $H(\pi')$ هو الاعتلاج، الذي يشجع على الاستكشاف المستدام لمنع الإفراط في التخصيص (overfitting) لسياسة الوكيل نفسه.
• $\alpha$ و $\beta$ هما معلمات فائقة (hyperparameters) غير سالبة.

نظرًا لمساحة الأفعال المحدودة في ألعاب اللوحات، فإن السياسة المثلى $\pi'$ تقبل حلاً تحليلياً مغلقاً:
$$\pi'(a|s) = \frac{1}{Z(s)} \exp\left( \frac{Q^\pi(s, a) + \beta \log \pi(a|s)}{\alpha + \beta} \right)$$
في KLENT، يتم تدريب شبكة عصبية $\pi_\theta$ لتقليل الاعتلاج المتقاطع (cross-entropy) بين مخرجاتها وهذا الهدف المستمد تحليلياً $\pi'$.

2. تعلم دالة القيمة

على عكس الأساليب القائمة على البحث التي تقدر قيم الأفعال عبر عمليات النسخ الاحتياطي لـ MCTS، تقوم KLENT بتمثيل دالة قيمة الفعل $Q^\pi(s, a)$ مباشرة باستخدام شبكة عصبية. ولتحقيق استقرار التعلم وإدارة المقايضة بين الانحياز والتباين، تستخدم الخوارزمية عائدات $\lambda$ ($G^\lambda$) كهدف للتعلم لدالة القيمة، بدلاً من عائدات مونت كارلو القياسية ($\lambda=1$). وقد أشارت التجارب الأولية إلى أن قيمة متوسطة لـ $\lambda \in (0, 1)$ تقلل من مجموع مربعي الانحياز والتباين بشكل أفضل من $\lambda=1$.

3. هيكل الخوارزمية

تتبادل KLENT بين مرحلة اللعب الذاتي (جمع البيانات داخل السياسة) ومرحلة الملاءمة (تحديث معاملات الشبكة). تقوم دالة الخسارة بتحسين شبكتي السياسة وقيمة الفعل في آن واحد:
$$L(\theta) = \mathbb{E}_D \left[ -\sum_{a \in A} \pi'(a|S) \log \pi_\theta(a|S) + (Q_\theta(S, A) - G^\lambda)^2 \right]$$
ومن المهم أن KLENT لا تتطلب أي بحث في الشجرة أثناء التدريب، بل تعتمد فقط على تنبؤات الشبكة العصبية والتحديث التحليلي للسياسة.

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

تقدم الورقة ثلاث مساهمات رئيسية، تركز على التوصيف النظري والتجريبي لهذا المزيج المحدد من التنظيم بدلاً من اقتراح مكونات خواروارزمية جديدة تماماً:

1. الصياغة الخوارزمية: اشتق المؤلفون خوارزمية تعلم تعزيزي عملية (KLENT) بناءً على الجمع بين تنظيم KL العكسي وتنظيم الاعتلاج، مع توفير قاعدة تحديث سياسة ذات صيغة مغلقة.
2. الضمانات النظرية: تم تقديم ضمانات تقارب جديدة لقاعدة تحديث السياسة في إعدادين:
   • الألعاب ذات الصيغة العادية: تثبت الورقة التقارب الخطي المحلي نحو نقطة ثابتة فريدة تحت الشرط $\alpha(\alpha + 2\beta) > \|R\|_2^2/4$. يغطي هذا الشرط نطاقاً أوسع من معاملات التنظيم مقارنة بالنتائج السابقة (مثل Sokota et al., 2022).
   • الألعاب ذات الطول المحدود: يثبت المؤلفون أن سياسة KLENT تتقارب نحو سياسة مثلى منتظمة بالاعتلاج (توازن الاستجابة الكمية - Quantal Response Equilibrium) عبر الاستقراء الخلفي، بافتراض لعبة ذات أفق زمني محدود.
3. التحقق التجريبي: تُظهر التجارب الشاملة على خمس ألعاب لوحات (Animal Shogi، وGardner Chess، و9x9 Go، وHex، وOthello) أن KLENT تحقق كفاءة تدريب أعلى بكثير من النماذج المرجعية الحالية القائمة على البحث أو الخالية من النموذج.

النتائج

كفاءة التدريب

تُظهر التجارب أن KLENT تتعلم بكفاءة أكبر من الأساليب الحالية عبر جميع البيئات المختبرة.

• مكاسب الأداء: حققت KLENT في المتوسط كفاءة تدريب أعلى بـ 4 أضعاف مقارنة بـ Gumbel AlphaZero (أقوى نموذج مرجعي قائم على البحث في الدراسة). على سبيل المثال، تطلب Gumbel AlphaZero 300 مليون تقييم للمحاكي للوصول إلى معدل فوز 50%، بينما تطلبت KLENT 75 مليوناً فقط.
• القابلية للتوسع: تتسع فجوة الكفاءة في الألعاب ذات عوامل التفرع العالية (مثل 9x9 Go وHex)، حيث تتطلب الأساليب القائمة على البحث ميزانيات ضخمة للمحاكي. وتُعزى ميزة KLENT إلى تجنب البحث الاستباقي واستخدام عائدات $\lambda$ المستقرة.
• الأداء واسع النطاق: في لعبة 19x19 Go، حافظت KLENT على كفاءة تعلم تنافسية مقارنة بـ AlphaZero، رغم زيادة التعقيد.

دراسات الاستئصال (Ablation Studies)

تؤكد الدراسة ضرورة التقنيات الثلاث الرئيسية:

• تنظيم KL العكسي: يؤدي إزالته (ضبط $\beta=0$) إلى تحديثات سياسة مفاجئة وتدهور الأداء، خاصة في 9x9 Go.
• تنظيم الاعتلاج: يؤدي إزالته (ضبط $\alpha=0$) إلى جعل السياسة حتمية للغاية (ينخفض الاعتلاج إلى ما يقرب من الصفر)، مما يؤدي إلى تعلم غير مستقر وانهيار الأداء.
• عائدات $\lambda$: أدت استبدال عائدات $\lambda$ بعمليات النسخ الاحتياطي لخطوة واحدة أو عائدات مونت كارلو إلى انخفاض الأداء، مما يؤكد أهمية موازنة الانحياز والتباين.

أداء وقت الاختبار

عند تجهيزها بـ MCTS وقت الاختبار (800 عملية تمرير)، حققت وكلاء KLENT معدلات فوز عالية ضد النماذج المرجعية، متفوقة على AlphaZero وGumbel AlphaZero في المواجهات المباشرة على 9x9 Go و19x19 Go.

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

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

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

باختصار، تقدم KLENT بديلاً فعالاً من حيث الحوسبة للتعلم التعزيزي القائم على البحث في ألعاب اللوحات، محققة أداءً تنافسياً بجزء بسيط من موارد التدريب من خلال الاستفادة من استقرار تنظيم KL العكسي والاعتلاج.