🤖 machine learning

NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria

تقدم هذه الورقة NashPG، وهو خوارزمية تدرج سياسة قابلة للتوسع تستخدم تنظيماً مُحسناً بشكل تكراري لضمان التقارب إلى توازنات ناش في ألعاب المعلومات الناقصة ذات اللعبتين الصفريتين، متفوقة بذلك على الأساليب الحالية في كل من المعايير المرجعية الكلاسيكية والمجالات واسعة النطاق مثل لعبة "No-Limit Texas Hold'em".

المؤلفون الأصليون: Eason Yu, Tzu Hao Liu, Clément L. Canonne, Yunke Wang, Chang Xu, Nguyen H. Tran, Stefano V. Albrecht

نُشر 2026-05-01

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

CC BY 4.0

المؤلفون الأصليون: Eason Yu, Tzu Hao Liu, Clément L. Canonne, Yunke Wang, Chang Xu, Nguyen H. Tran, Stefano V. Albrecht

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

تخيل أنك تلعب لعبة ورق عالية المخاطر ضد خصم ذكي، لكن لا يمكنك رؤية أوراقه. كلاكما يريد الوصول إلى الاستراتيجية المثالية حيث لا يمكن لأي منكما أن يُخدع أو يُستغل، بغض النظر عما يفعله الآخر. في نظرية الألعاب، تسمى هذه الحالة المثالية غير القابلة للاستغلال توازن ناش (Nash Equilibrium).

إن العثور على هذا "التوازن المثالي" في الألعاب المعقدة (مثل البوكر أو معركة السفن/Battleship) أمر صعب للغاية على أجهزة الكمبيوتر. تقدم هذه الورقة طريقة جديدة تسمى NASHPG (تدرج سياسة ناش) لمساعدة أجهزة الكمبيوتر على تعلم هذه الاستراتيجيات المثالية.

إليك قصة كيفية عمل ذلك، مشروحة ببساطة:

المشكلة: فخ "الالتصاق"

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

ومع ذلك، كانت هناك عقبة:

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

الحل: "المرساة المتنقلة" (IMMD)

اقترح المؤلفون أولاً فكرة نظرية تسمى IMMD (النزول المرآتي المغناطيسي التكراري).

تخيل أنك تحاول العثد على مركز غرفة مظلمة.

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

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

الأداة العملية: NASHPG

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

لذا، قام المؤلفون ببناء نسخة عملية تسمى NASHPG.

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

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

ما وجدوه

اختبر المؤلفون هذا على عدة ألعاب، من ألعاب الورق البسيطة (Kuhn Poker) إلى ألعاب ضخمة ومعقدة مثل معركة السفن (Battleship) و تكساس هولدم بلا حدود (No-Limit Texas Hold'em).

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

الخلاصة

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

إنه جسر بين النظرية الرياضية المعقدة والبرمجيات العملية التي يمكنها هزيمة البشر في ألعابهم الخاصة.

إليك ملخص تقني مفصل لورقة البحث بعنوان: "NASHPG: طريقة تدرج السياسة مع تنظيم متكرر التحسين لإيجاد توازن ناش."

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

تتناول الورقة تحدي إيجاد توازن ناش (Nash Equilibria - NE) في الألعاب ذات المعلومات الناقصة ذات اللعبتين الصفريتين (2p0s IIGs) باستخدام التعلم المعزز متعدد الوكلاء (MARL).

الصعوبة الجوهرية: بينما نجح التعلم المعزز العميق (DRL) في ألعاب المعلومات الكاملة، فإن ألعاب (2p0s IIGs) (مثل البوكر) تنطوي على ملاحظة جزئية ومعلومات مخفية.
محدودية الأساليب الحالية:
- الأساليب القائمة على المجموعات (مثل PSRO و NFSP): غالبًا ما تتطلب حسابات مكلفة للاستجابة المثلى (best-response)، وتضمن فقط التقارب إلى متوسط السياسة، وليس إلى السياسة في التكرار الأخير. كما أن استخراج سياسة نهائية في بيئات التعلم المعزز العميق أمر غير يسير.
- تقليل الندم المضاد (CFR): يتطلب تعداداً كاملاً لشجرة اللعبة (نموذج قائم على النموذج)، مما يجعله غير قابل للتطبيق في النطاقات الكبيرة.
- الأساليب القائمة على التنظيم (مثل R-NaD): تستخدم الأساليب الحديثة التنظيم لضمان التقارب في التكرار الأخير إلى توازن منظم. ومع ذلك، هذه ليست بالضرورة توازنات ناش حقيقية (تظل قابلة للاستغلال). علاوة على ذلك، تعتمد التطبيقات العملية الحالية (مثل R-NaD) على ديناميكيات المكرر العصبي (NeuRD)، والتي أظهرت أداءً أدنى مقارنة بطرق تدرج السياسة القياسية.
الفجوة: هناك نقص في وجود خوارزمية قابلة للتوسع، خالية من النموذج (model-free)، وقائمة على تدرج السياسة يمكنها التقارب بشكل مثبت نحو توازن ناش دقيق في الألعاب واسعة النطاق.

2. المنهجية

يقترح المؤلفون نهجاً ذا مرحلتين: إطار نظري (IMMD) وخوارزمية عملية (NASHPG).

أ. الإطار النظري: MMD المتكرر (IMMD)

يوسع المؤلفون طريقة النزول المرآتي المغناطيسي (Magnetic Mirror Descent - MMD)، وهي طريقة تحل المتباينات المتغيرة المنظمة (Regularized Variational Inequalities - VI).

المتباينات المتغيرة المنظمة (Regularized VI): مسائل الـ VI القياسية لتوازن ناش هي مسائل رتيبة ولكنها ليست رتيبة بقوة، مما يجعل حلها مباشرة أمراً صعباً. تضيف MMD منظماً متصلب التحدب (strongly convex regularizer) يعتمد على تباعد بريجمان (Bregman divergence) لإنشاء مؤثر رتيب بقوة، مما يضمن حلاً فريداً.
التحسين المتكرر: بدلاً من حل مشكلة منظمة واحدة، تقوم IMMD بحل سلسلة منها.
1. ابدأ بملف استراتيجية أولي $\rho$ .
2. حل مشكلة $VI(Z, G_\rho)$ المنظمة لإيجاد استراتيجية جديدة $z = M(\rho)$ .
3. استخدم هذه الاستراتيجية الجديدة $z$ كمرجع $\rho$ للجولة التالية.
الضمان النظري: تثبت الورقة أن هذه العملية التكرارية تؤدي إلى تقليل صارم في الرتابة لتباعد بريجمان تجاه أي توازن ناش. وبناءً على ذلك، فإن سلسلة الاستراتيجيات تتقارب نحو توازن ناش حقيقي.

ب. الخوارزمية العملية: تدرج سياسة ناش (NASHPG)

لجعل IMMD قابلة للتطبيق في الألعاب واسعة النطاق حيث يكون التعداد الكامل مستحيلاً، اشتق المؤلفون NASHPG:

من الاستراتيجيات المختلطة إلى الاستراتيجيات السلوكية: يقومون بتقريب تباعد بريجمان للاستراتيجية المختلطة (المستخدم في IMMD) باستخدام تباعد كولباك - ليبلر (KL divergence) بين السياسات السلوكية (السياسات العشوائية في التعلم المعزز).
دالة الهدف: تقوم الخوارزمية بتحسين هدف السياسة المنظم:
$\text{Objective} = \mathbb{E}[R] - \alpha \cdot \mathbb{E}_{o} [ D_{KL}(\pi(\cdot|o) \parallel \rho(\cdot|o)) ]$
حيث $\pi$ هي السياسة الحالية، و $\rho$ هي السياسة المرجعية (من الحلقة الخارجية السابقة)، و $\alpha$ هي قوة التنظيم.
هيكل الخوارماية:
1. الحلقة الداخلية: تنفيذ $K$ من خطوات تحديثات تدرج السياسة القياسية (مثل استخدام PPO) لتحسين الهدف المنظم مقابل المرجع الحالي $\rho$ .
2. الحلقة الخارجية: بعد $K$ من الخطوات، يتم تحديث السياسة المرجعية $\rho$ لتصبح السياسة الحالية $\pi$ ، ثم التكرار.
النمطية: خوارزمية NASHPG مستقلة عن مقدر تدرج السياسة المحدد؛ حيث يمكنها التكامل بسلاسة مع خوارزميات التعلم المعزز أحادية الوكيل المتقدمة مثل PPO (التحسين السياسة القريبة).

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

التقارب النظري: تقديم IMMD، وهو إطار عمل تنظيمي متعدد الجولات يضمن تقليلاً صارماً في الرتابة لتباعد بريجمان والتقارب نحو توازن ناش دقيق في ألعاب الصيغة الممتدة ذات المعلومات الناقصة (2p0s extensive-form games).
الخوارزمية العملية (NASHPG): تطوير خوارزمية قابلة للتوسع وخالية من النموذج تنفذ إطار عمل IMMD باستخدام طرق تدرج السياسة القياسية (مثل PPO) وتنظيم KL.
التحقق من الفرضية: تقديم دليل تجريبي على أن الأداء الضعيف لطرق التنظيم السابقة (مثل R-NaD) كان بسبب استخدام NeuRD كمحلل داخلي، وليس بسبب إطار عمل التنظيم نفسه. وقد أدى استبدال NeuRD بـ PPO في إطار عمل مشابه إلى تحسين الأداء بشكل كبير.
القابلية للتوسع: إثبات القدرة على حل النطاقات واسعة النطاق (مثل Battleship، وHeads-Up No-Limit Texas Hold'em) حيث يكون التعداد الدقيق مستحيلاً.

4. النتائج التجريبية

قيم المؤلفون NASHPG في سبع ألعاب تتراوح من الصغيرة (Kuhn Poker) إلى الضخمة (Heads-Up No-Limit Texas Hold'em).

التقارب والاستقرار: أظهرت NASHPG تقارباً مستقراً دون حدوث تباعد، حتى مع قوى التنظيم العالية، على عكس بعض الخطوط المرجعية.
الأداء مقابل الخطوط المرجعية:
- الألعاب الصغيرة: حققت NASHPG توازناً أو أقل في قابلية الاستغلال (exploitability) مقارنة بـ NFSP و PSRO و MMD و R-NaD في ألعاب Kuhn Poker و Leduc Poker و Dark Hex و Phantom Tic-Tac-Toe.
- الألعاب الكبيرة: في Battleship و Heads-Up No-Limit Texas Hold'em (حيث تكون قابلية الاستغلال الدقيقة غير قابلة للقياس)، حققت NASHPG عائدات متوسطة أعلى في المواجهات المباشرة ضد جميع الخطوط المرجعية (NFSP, PSRO, R-NaD, MMD).
دراسة الاستئصال (R-NaD مقابل PPO): أجريت تجربة مضبوطة استبدلت NeuRD بـ PPO في إطار عمل R-NaD (مما خلق RNaD-PPO).
- في الألعاب الصغيرة، كانت قاعدة التحديث أقل أهمية.
- في الألعاب الكبيرة، تفوق RNaD-PPO بشكل كبير على R-NaD القياسي، مما قلص الفجوة مع NASHPG. وقد أكد هذا أن قاعدة التحسين الداخلية (PPO مقابل NeuRD) هي العائق الأساسي في التنظيم متعدد الجولات القائم على العينات.
الكفاءة: تطلب التنفيذ تعديل حوالي 20 سطراً فقط من الكود البرمجي فوق خوارزمية Independent PPO القياسية، مما يبرز سهولة الوصول إليها.

5. الأهمية

الجسر بين النظرية والتطبيق: نجحت الورقة في سد الفجوة بين ضمانات التقارب النظرية (التي غالباً ما تقتصر على الألعاب الصغيرة المعددة) وبين خوارزميات MARL العملية والقابلة للتوسع.
نموذج جديد لـ MARL: تؤسس الورقة لفكرة أن التحسين المتكرر للمرجع التنظيمي جنباً إلى جنب مع تدرجات السياسة القياسية هو نهج متفوق لإيجاد توازنات ناش مقارنة بالأساليب القائمة على المجموعات أو تقنيات التنظيم القديمة.
سهولة الوصول: من خلال الاعتماد على PPO القياسي وتنظيم KL البسيط، تخفض NASHPG حاجز الدخول للممارسين، مما يسمح لهم بتطبيق ضمانات تقارب نظرية الألعاب المتقدمة دون الحاجة إلى حلول مخصصة معقدة أو تعداد كامل لشجرة اللعبة.
أداء الحالة الراهنة (State-of-the-Art): وضعت معياراً جديداً للطرق الخالية من النموذج في ألعاب المعلومات الناقصة، متفوقة على الخطوط المرجعية الراسخة في كل من النطاقات الصغيرة والكبيرة.