Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games

إليك ملخص تقني مفصل لورقة البحث بعنوان "تكرار السياسة لألعاب ستيكلبرج العشوائية ذات المجموع العام بين لاعبين" من قبل كودو وأكيموتو.

1. تعريف المشكلة

تتناول الورقة ألعاب ستيكلبرج العشوائية (SSGs) ذات المجموع العام بين لاعبين.

• الإطار: بيئة ديناميكية تُنمذج كـ "لعبة ماركوف" مع وكيلين: القائد (الوكيل A) والتابع (الوكيل B).
• الهدف: يسعى القائد إلى تعظيم مكافأته التراكمية المخصومة المتوقعة، متوقعاً أن التابع سيلعب دائماً أفضل استجابة (Best Response - BR) لسياسة القائد.
• القيد الأساسي: التابع غير قصير النظر (non-myopic) (يأخذ في الاعسبار المكافآت المستقبلية) ويتصرف كوكيل عقلاني يحسن دالة مكافأته الخاصة. البيئة (احتمالات الانتقال ودوال المكافأة) معروفة.
• التحدي الجوهري:
  • في إعدادات المجموع العام، قد لا يوجد دائماً توازن ستيكلبرج مستقر (SSE) — وهو زوج من السياسات حيث يعظم القائد عائده بناءً على أفضل استجابة للتابع.
  • الطرق الموجودة (مثل تكرار القيمة القائم على البرمجة الديناميكية أو طرق تدرج السياسة) غالباً ما تفشل في ضمان التحسن الرتيب (monotone improvement) في أداء القائد.
  • وبناءً على ذلك، قد تؤدي هذه الطرق إلى سياسات منخفضة الجودة أو تفشل في التقارب نحو SSE حتى لو كان موجوداً، لأن النقاط الثابتة لمعاملاتها لا تتوافق بالضرورة مع دالة قيمة ستيكلبرج الحقيقية.

2. المنهجية

يقترح المؤلفون خوارزمية مبتكرة لـ تكرار السياسة الأمثل لباريتو (Pareto-Optimal Policy Iteration). تتكون المنهجية من ثلاث ركائز نظرية رئيسية:

أ. تحليل معاملات البرمجة الديناميكية (DP) الحالية

يحلل المؤلفون معاملات البرمجة الديناميكية المستخدمة في الأعمال السابقة (مثل Bucarey et al., 2022).

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

ب. اشتقاق مبرهنة تحسين السياسة

للتغلب على غياب التحسن الرتيب، يشتق المؤلفون مبرهنة تحسين السياسة (المبرهنة 8) لألعاب SSG ذات التابع الذي يلعب "أفضل استجابة".

• يعرفون دالة $Q^{f' \dagger}_A(s, f)$ التي تمثل المكافأة الفورية للقائد بالإضافة إلى القيمة المخصومة للحالة التالية، بافتراض أن التابع يلعب أفضل استجابة للسياسة الجديدة $f$، بينما يتم تقييم قيمة الحالة التالية تحت ظل السياسة القديمة $f'$.
• تثبت المبرهنة 8 أنه إذا كانت $Q^{f' \dagger}_A(\cdot, f) \succeq V^{f' \dagger}_A$ (أي أن قيمة Q الجديدة تهيمن على دالة القيمة القديمة)، فإن السياسة الجديدة $f$ ستنتج دالة قيمة $V^{f \dagger}_A$ تهيمن على $V^{f' \dagger}_A$.
• يسمح هذا بتحديثات السياسة دون الحاجة إلى حساب دالة القيمة الكاملة للسياسة الجديدة فوراً، بشكل مشابه لتكرار السياسة القياسي في عمليات ماركوف لاتخاذ القرار (MDPs) أحادية الوكيل.

ج. الأمثلية لباريتو كهدف

بما أن SSE قد لا يوجد (أي لا توجد سياسة واحدة تعظم قيمة القائد في جميع الحالات في آن واحد)، يقدم المؤلفون الأمثلية لباريتو (Pareto-Optimality - PO) كهدف.

• التعريف: تكون دالة القيمة "مثالية لباريتو" إذا لم توجد أي دالة قيمة أخرى يمكن الوصول إليها تهيمن عليها بشكل صارخ في جميع الحالات.
• الخصائص:
  • إذا وجد SSE، فإن دالة قيمة SSE هي دالة قيمة باريتو الوحيدة.
  • إذا لم يوجد SSE، فإن مجموعة دوال القيمة المثالية لباريتو (جبهة باريتو - Pareto front) موجودة دائماً وتوفر مجموعة "معقولة" من المقايضات المثلى.
• التحويل إلى قيم عددية (Scalarization): لتوجيه عملية البحث، تستخدم الخوارزمية دالة تحويل لباريتو $L$ (مثل المجموع الموزون لقيم الحالات) لاختيار السياسة التالية من مجموعة السياسات المحسنة.

د. الخوارزمية (تكرار السياسة الأمثل لباريتو)

تسير الخوارزمية المقترحة (الخوارزمية 1) كما يلي:

1. التهيئة: ابدأ بسياسة قائد أولية $f_0$.
2. التقييم: احسب دالة قيمة القائد $V^{f_t \dagger}_A$ تحت السياسة الحالية وأفضل استجابة للتابع.
3. تحسين السياسة: إنشاء مجموعة السياسات $W_{\succeq}(f_t)$ التي تحقق شرط التحسين $Q^{f_t \dagger}_A(\cdot, f) \succeq V^{f_t \dagger}_A$.
4. الاختيار: اختر السياسة الجديدة $f_{t+1}$ من هذه المجموعة التي تعظم القيمة المحولة عددياً $L[Q^{f_t \dagger}_A(\cdot, f)]$.
5. التكرار: كرر العملية حتى لا يكون هناك مجال لمزيد من التحسين.

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

1. التحليل النظري لمعاملات DP: تشتق الورقة صراحة النقاط الثابتة لمعاملات البرمضاء الديناميكية الحالية لـ SSGs، وتثبت أنها لا تضمن أداء القائد الأمثل عند عدم وجود SSE.
2. مبرهنة تحسين السياسة: تم اشتقاق مبرهنة جديدة خصيصاً لألعاب SSG ذات المجموع العام والتابعين الذين يلعبون "أفضل استجابة"، مما يتيح ضمان التحسن الرتيب.
3. تكرار السياسة الأمثل لباريتو: اقتراح خوارزمية جديدة تضمن التحسن الرتيب في قيم حالات القائد.
4. ضمانات التقارب:
   • ثبت أن الخوارزمية تتقارب إلى حدود فضاء دوال القيمة التي يمكن الوصول إليها.
   • بشكل حاسم، إذا كان القائد قصير النظر ($\gamma_A = 0$)، فإن الخوارزمية تضمن التقارب إلى سياسة مثالية لباريتو. وهذا هو أول ضمان نظري من هذا النوع لألعاب SSG ذات المجموع العام والقائد قصير النظر.
5. التعامل مع عدم وجود SSE: يوفر الإطار حلاً قوياً حتى عندما لا يوجد توازن ستيكلبرج مستقر، حيث يتقارب بدلاً من ذلك نحو جبهة باريتو.

4. النتائج والأهمية

• الأهمية النظرية: تسد هذه الدراسة فجوة في التعلم التعزيزي القائم على نظرية الألعاب من خلال تقديم أول ضمانات تقارب لألعاب SSG ذات المجموع العام حيث يكون التابع غير قصير النظر والقائد قصير النظر. وهي تنقل التركيز من البحث عن SSE (الذي قد لا يكون موجوداً) إلى البحث عن السياسات المثالية لباريتو.
• الآثار العملية:
  • الرتابة (Monotonicity): على عكس طرق تدرج السياسة التي قد تتذبذب أو تتدهور، تضمن هذه الطريقة عدم انخفاض أداء القائد أثناء التكرار.
  • المتانة: تتعامل مع السيناريوهات التي تكون فيها الاستراتيجية "المثلى" عبارة عن مقايضة بين حالات مختلفة (جبهة باريتو)، وهو أمر شائع في التطبيقات الواقعية مثل تصميم منصات التجارة الإلكترونية أو ألعاب الأمن.
  • التطبيق: يناقش المؤلفون تطبيقات في تعليم السياسة (Policy Teaching) (توجيه سلوك الوكيل عبر التلاعب بالبيئة)، حيث يقوم القائد (المعلم) بتعديل احتمالات الانتقال لاستحثاث "أفضل استجابة" محددة لدى التابع (الطالب).
• القيود:
  • تتطلب الخوارزمية معرفة بدالة الانتقال والقدرة على حساب "أفضل استجابة" للتابع (والذي قد يكون مكلفاً حوسبياً).
  • بالنسبة للقادة غير قصيري النظر ($\gamma_A > 0$)، لا يتم ضمان التقارب إلى جبهة باريتو بشكل صارم (يتم التقارب فقط إلى الحدود)، رغم أن التحسن الرتيب يظل مضموناً.
  • مساحة البحث عن السياسة التالية قد تكون كبيرة، مما يتطلب استخدام استدلالات (مثل تقسيم فضاء السياسة) للتنفيذ العملي.

الخاتمة

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