ملخص تقني: تقارب التكرار الأخير شبه الأمثل في الألعاب ذات المجموع الصفري مع تغذية راجعة من نوع "البانديت" وأفعال الخصم

بيان المشكلة

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

الهدف الرئيسي هو تحقيق تقارب التكرار الأخير (Last-Iterate Convergence) نحو توازن ناش، ويُقاس ذلك عبر فجوة الثنائية $DGap(x_t, y_t) \to 0$ مع مرور الجولات $t \to \infty$. وهذا يختلف عن تقارب متوسط التكرار (تقارب الاستراتيجيات المتوسطة زمنياً) أو تقارب التكرار العشوائي، وهو مفهوم أقوى منه.

لقد أثبتت الأعمال السابقة وجود انفصال صارخ بين تقارب متوسط التكرار وتقارب التكرار الأخير في غياب التغذية الراجعة حول أفعال الخصم:

• متوسط التكرار: معدل أمثل قدره $O(t^{-1/2})$.
• التكرار الأخير (بدون أفعال الخصم): المعدلات المثلى محدودة بـ $O(t^{-1/3})$ في التوقع و $O(t^{-1/4})$ باحتمالية عالية.

السؤال المركزي الذي تطرحه الورقة هو ما إذا كانت المعلومات الإضافية المتمثلة في ملاحظة فعل الخصم تسمح بتقارب أسرع للتكرار الأخير، وتحديداً سد الفجوة للوصول إلى المعدل الأمثل $O(t^{-1/2})$.

المنهجية

الخوارزمية: PMO-LB

يقترح المؤلفون خوارزمية التحسين ذو المراحل المتعددة مع تنظيم حاجز اللوغاريتم (Phased Minimax Optimization with Log-Barrier Regularization - PMO-LB). تعمل الخوارزمية في حقبات (epochs) ذات طول مضاعف ($2^{s-1}$ إلى $2^s - 1$).

1. التقدير: ضمن كل حقبة $s$، يجمع اللاعبون البيانات لحساب مُقدّر تجريبي $\hat{A}_s$ لمصفوفة اللعبة $A$.
2. تحديث الاستراتيجية: في بداية كل حقبة، يحسب اللاعبون زوج الاستراتيجيات المختلطة الجديد $(x_s, y_s)$ عن طريق حل لعبة مُقدرة ومنظمة بحاجز لوغاريتمي. تُعرف دالة العائد بـ:
   $$\Phi_s(x, y) \triangleq x^\top \hat{A}_s y + \gamma_s \sum_{i=1}^d \log \frac{1}{x_i} - \gamma_s \sum_{j=1}^d \log \frac{1}{y_j}$$
   حيث $\gamma_s$ هو معدل تعلم يتناقص مع الحقبة.
3. التنفيذ: يختار اللاعبون إجراءات من $(x_s, y_s)$ طوال مدة الحقبة.
4. الاستقلالية: على الرغم من الطبيعة المترابطة للعبة، فإن الخوارزمية غير مترابطة (uncoupled)؛ حيث يمكن لكل لاعب حساب استراتيجيته بشكل مستقل باستخدام أفعال الخصم الملحوظة وخسائره الخاصة.

النهج التحليلي

تجادل الورقة بأن التقنيات القياسية من أدبيات "البانديت" (سواء الاستبعاد الصعب Hard-elimination أو الاستبعاد الناعم Soft-elimination) تفشل في التعميم على الألعاب حتى مع وجود تغذية راجعة لأفعال الخصم.

• الاستبعاد الصعب: يفشل لأن تقدير فجوة الثنائية لزوج من الاستراتيجيات النقية $(e_i, e_j)$ يتطلب لعب استراتيجيات أخرى قد تكون "سيئة" للعثور على أفضل الاستجابات، وهو ما يتعارض مع الهدف المتمثل في الحفاظ على ندم (regret) منخفض في كل جولة.
• الاستبعاد الناعم القياسي (نمط FALCON): تعتمد التحليلات الحالية على خاصية "الندم المنخفض-التباين المنخفض"، حيث يتم التحكم في تباين تقدير إجراء ما من خلال الندم الخاص به. يوضح المؤلفون أن هذه الخاصية غير كافية للألعاب لأن تقدير فجوة الثنائية لزوج من الاستراتيجيات يتطلب لعب استراتيجيات قد تكون لها فجوات ثنائية عالية بحد ذاتها.

للتغلب على ذلك، طور المؤلفون تحليلاً جديداً يعتمد على الاستقرار الضربي (Multiplicative Stability).

• يثبتون أن الاستراتيجيات المتتالية $x_s$ و $x_{s-1}$ (وكذلك بالنسبة لـ $y$) متقاربة ضربياً ($x_{s,i} \leq \alpha x_{s-1,i}$) باحتمالية عالية.
• يتم تمكين هذا الاستقرار بواسطة منظم حاجز اللوغاريتم (Log-barrier regularizer)، الذي يمنع تركيز الكتلة الاحتمالية بسرعة كبيرة على مجموعة فرعية من الإجراءات، مما يؤدي إلى التحكم في تباين مُقدّرات الخسارة.
• يضع التحليل خاصية "الفجوة الثنائية المنخفضة-التباين المنخفض" التي، جنباً إلى جنب مع الاستقرار الضربي، تسمح بتحديد فجوة الثنائية الحقيقية دون الحاجة لأن تلعب الخوارزمية استراتيجيات سيئة صراحةً.

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

1. تقارب التكرار الأخير الأمثل: تثبت الورقة أنه مع التغذية الراجعة لأفعال الخصم، من الممكن تحقيق تقارب التكرار الأخير بمعدل $O(t^{-1/2})$ باحتمالية عالية. وهذا يطابق المعدل الأمثل لتقارب متوسط التكرار، مما يغلق الفجوة بين المفهومين في هذا السياق.
2. الكفاءة الخوارزمية: الخوارزمية المقترحة فعالة حوسبياً، حيث تتطلب $\log t$ من التحديثات فقط (حل مسألة تحسين نقطة السرج) بعد $t$ من الجولات.
3. الجدة النظرية: تحدد الورقة العقبات الأساسية في تعميم تحليلات "البانديت" أحادية اللاعب على الألعاب متعددة اللاعبين. كما تقدم إطاراً تحليلياً جديداً يعتمد على الاستقرار الضربي بين الاستراتيجيات المتتالية، وهو أمر متميز عن التحليلات القائمة على الندم السابقة.
4. تحسين "البانديت المتنافس" (Dueling Bandits): كحالة خاصة حيث تكون مصفوفة اللعبة متماثلة مائل (skew-symmetric)، توفر النتائج أول ضمانات لتقارب التكرار الأخير لهذا الإعداد، مما يحسن من الأعمال السابقة التي قدمت حدود الندم فقط.

النتائج

الضمانات النظرية

النظرية 4.1: لأي $\delta \in (0, 1)$ ثابت، تضمن الخوارزمية 2 بجدول معدل تعلم محدد أنه باحتمالية لا تقل عن $1-\delta$:
$$DGap(x_t, y_t) = O\left( \frac{d^2 \sqrt{\log(d \log t / \delta)}}{\sqrt{t}} \right)$$
لكل $t \geq 1$. ويمثل هذا معدل تقارب $t^{-1/2}$.

التحقق التجريبي

قيم المؤلفون خوارزمية PMO-LB على نماذج اختبار ألعاب الأمن (بأحجام $61 \times 21$ و $39 \times 35$) مقابل خمسة نماذج أساسية (baselines):

• طرق سابقة بدون تغذية راجعة لأفعال الخصم (Cai et al. [2023, 2025], Fiegel et al. [2025, 2026]).
• نموذج أساسي ساذج يستخدم أفعال الخصم ولكنه يمزج بين أفضل استراتيجية تجريبية والاستكشاف الموحد (الخوارزمية 3).

النتائج:

• تفوقت PMO-LB باستمرار على جميع النماذج الأساسية.
• طابقت منحدرات التقارب التجريبية التوقعات النظرية:
  • PMO-LB: $\approx -0.5$ (مطابق لـ $t^{-1/2}$).
  • النموذج الأساسي الساذج: $\approx -0.25$ (مطابق لـ $t^{-1/4}$).
  • الطرق السابقة (بدون أفعال الخصم): تراوحت المنحدرات بين $-0.175$و$-0.301$(مطابق لـ$t^{-1/8}$إلى$t^{-1/3}$).

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

تدعي الورقة أنها حلت سؤالاً مفتوحاً طال أمده حول تأثير معلومات أفعال الخصم على تقارب التكرار الأخير. ومن خلال إظهار إمكانية تحقيق تقارب $t^{-1/2}$، يوضح العمل أن "المسار الأصعب" لتقارب التكرار الأخير في ظروف التغذية الراجعة من نوع "البانديت" ليس بالضرورة أبطأ من تقارب متوسط التكرار، بشرط أن تكون أفعال الخصم قابلة للملاحظة.

يؤكد المؤلفون أن مساهمتهم هي في المقام الأول نظرية وخوارزمية. ويشيرون إلى أن اعتماد $d^2$ في الحد قد يكون غير أمثل، لكن المعدل $t^{-1/2}$ هو الأمثل فيما يتعلق بعوامل الأبعاد. كما تسلط الورقة الضوء على أن تقنيات التحليل الخاصة بهم (الاستقرار الضربي عبر تنظيم حاجز اللوغاريتم) قد تكون ذات أهمية مستقلة لمشاكل "البانديت" أحادية اللاعب، حيث تقدم بديلاً للتحليلات القائمة على الندم.

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