ملخص تقني: إعادة النظر في تدرجات السياسة للفئات المقيدة من السياسات

بيان المشكلة

تُستخدم طرق تدرج السياسة (Policy Gradient - PG) القياسية على نطاق واسع لحل عمليات ماركوف لاتخاذ القرار (MDPs). وبينما تضمن هذه الطرق نظرياً التقارب نحو السياسة المثلى في فئات السياسات غير المقيدة تحت شروط الاستكشاف الكافي، إلا أنها غالباً ما تفشل في فئات السياسات المقيدة. وفي هذه الإعدادات، التي تشمل تجميع الحالات (state aggregation)، والأنظمة متعددة الوكلاء اللامركزية، والبيئات ذات الرؤية الجزئية، غالباً ما تعجز طرق PG وتستقر عند نقاط حرجة دون المستوى الأمثل.

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

المنهجية

1. صياغة السياسة المترابطة (Correlated Policy)

لمعالجة قصر النظر، يقترح المؤلفون إعادة صياغة للسياسة. بدلاً من النظر إلى السياسة العشوائية كخريطة مباشرة $\pi: S \to \Delta(A)$، فإنهم يعرفون السياسة المترابطة $\tilde{\pi}$ كـتوزيع على مجموعة من السياسات الحتمية $\Pi_{det}$.

• الفئة المقيدة: تعمل عملية التعلم على $\tilde{\Pi}_{res} = \Delta(\Pi_{det})$، وهي مجموعة جميع التوزيعات على مجموعة محددة مسبقاً من السياسات الحتمية.
• التنفيذ: في عملية التدفق القياسية (standard rollout)، يتم أخذ عينة من سياسة حتمية من $\tilde{\pi}$ عند كل خطوة بشكل مستقل. ومع ذلك، يقدم المؤلفون آلية التقييم لـ k-خطوة.

2. تدرجات السياسة لـ k-خطوة (k-step Policy Gradients)

الابتكار الجوهري هو تدرج السياسة لـ k-خطوة، والذي يعدل أفق التقييم للهروب من الأمثلة المحلية (local optima).

• دالة القيمة لـ k-خطوة ($J_{\tilde{\pi}, k}$): بدلاً من أخذ عينة من سياسة حتمية جديدة عند كل خطوة، تقوم الخوارزمية بأخذ عينة من سياسة حتمية $\pi_{det} \sim \tilde{\pi}$ وتنفيذها لـ $k$ من الخطوات المتتالية قبل إعادة أخذ العينة.
• دالة Q لـ k-خطوة ($Q_{\tilde{\pi}, k}$): تقيم هذه الدالة العائد من اتخاذ سياسة حتمية معينة $\pi'_{det}$ لأول $k$ من الخطوات، متبوعة بالتدفق القياسي لـ $\tilde{\pi}$ لـ k-خطوة.
• النظرية 5.5 (نظرية PG لـ k-خطوة): يتم التعبير عن تدرج دالة القيمة لـ k-خطوة بالنسبة لمعلمات $\tilde{\pi}$ باستخدام دالة Q لـ k-خطوة:
  $$\nabla_\alpha J_{\tilde{\pi}_\alpha, k}(\mu) = \frac{1}{1-\gamma^k} \mathbb{E}_{s \sim d_{\tilde{\pi}_\alpha, k}^\mu} \left[ \mathbb{E}_{\pi_{det} \sim \tilde{\pi}_\alpha} [Q_{\tilde{\pi}_\alpha, k}(s, \pi_{det}) \nabla_\alpha \log \tilde{\pi}_\alpha(\pi_{det})] \right]$$
  من خلال تقييم الإجراءات عبر نافذة زمنية قدرها $k$ خطوة، يمكن للتدرج أن "يرى" الفوائد طويلة المدى للسياسة الحتمية التي قد تتكبد تكاليف قصيرة المدى، مما يصحح الانحياز الناتج عن قصر النظر.

3. خوارزميات التحسين

يحلل البحث تقارب الاشتقاق المتدرج المسقط (Projected Gradient Descent - PGD) والاشتقاق المتدرج المرآتي (Mirror Descent) عند تطبيقهما على هدف k-خطوة. يفترض التحليل فقط سلاسة وقابلية اشتقاق دالة القيمة، متجنباً الافتراضات القوية مثل اكتمال بلمان (Bellman completeness) أو هيمنة التدرج (gradient dominance) الشائعة في الأدبيات السابقة.

المساهمات والنتائج الرئيسية

1. الضمان النظري للقرب من المثالية

المساهمة النظرية الأساسية هي إثبات أن جميع النقاط الحرجة ذات التدرج الصفري والنهايات الصغرى المحلية عند الحدود لهدف k-خطوة هي قريبة أسياً من السياسة الحتمية المثلى من حيث الأداء.

• النظرية 6.1: لأي نقطة حرجة $\tilde{\pi}_{crit}$، تحقق فجوة الأداء ما يلي:
  $$\mathbb{E}_{\pi_{det} \sim \tilde{\pi}_{crit}}[J_{\pi_{det}}(\mu)] - J_{\pi^*_{det}}(\mu) \leq \frac{8\gamma^k}{1-\gamma} g_{max}$$
  مع زيادة $k$، تضيق الفجوة بشكل أسي، مما يقضي فعلياً على الأمثلة المحلية دون المستوى الأمثل التي تعاني منها طرق الخطوة الواحدة.

2. معدلات التقارب

يوضح المؤلفون أن خوارزميات النزول (PGD و Mirror Descent) تتقارب نحو هذه الحلول القريبة من المثالية بمعدل $O(1/T)$.

• النظرية 6.2 و 6.3: رغم غياب شرط هيمنة التدرج القياسي (الذي يفشل غالباً في الفئات المقيدة)، فإن التقييم لـ k-خطوة يستحث شرط هيمنة تدرج تقريبي. وهذا يسمح للخوارزميات بتحقيق المعدل الأسرع $O(1/T)$، المرتبط عادةً بالمسائل المحدبة أو المسيطرة بالتدرج، بدلاً من المعدل الأبطأ $O(1/\sqrt{T})$ الشائع للدوال الناعمة غير المحدبة.

3. تجنب عدم تطابق التوزيع

من النتائج الهامة أن هذه الحدود لا تعتمد على عوامل عدم تطابق التوزيع $\|d_{\pi^*}^\mu / d_{\pi}^\mu\|_\infty$ أو $\|d_{\pi^*}^\mu / \mu\|_\infty$.

• في نظرية PG القياسية، يمكن أن تكون هذه العوامل لانهائية إذا لم يغطِ التوزيع الأولي دعم نطاق إشغال الحالة للسياسة المثلى، مما يؤدي إلى نقاط حرجة دون المستوى الأمثل حتى في الإعدادات كاملة الرؤية.
• ثبت أن طريقة k-خطوة تهرب من هذه النقاط بغض النظر عن تغطية التوزيع الأولي، بشرط أن تكون $k$ كبيرة بما يكفي.

الأهمية والتطبيقات

يزعم البحث أن هذا العمل يوفر أساساً نظرياً لحل عمليات MDP المعقدة ذات فئات السياسات المقيدة حيث فشلت الطرق السابقة أو اعتمدت على افتراضات غير واقعية.

• تجميع الحالات (State Aggregation): تقدم الطريقة ضمانات قريبة من المثالية للسياسات التي تربط الحالات المجمعة بالإجراءات، وهو أمر ضروري في الأنظمة واسعة النطاق.
• الأنظمة متعددة الوكلاء: تنطبق على الإعدادات التعاونية مع وكلاء مستقلين، ووكلاء لامركزيين، ووكلاء لامركزيين جماعيين. غالباً ما تُنمذج هذه الحالات كـ Dec-POMDPs، المعروفة بأنها مستعصية حسابياً (NEXP-complete). يقدم البحث نتيجة نظرية إيجابية لطرق التدرج في هذه الإعدادات.
• إعدادات كاملة الرؤية: يسلط العمل الضوء على أنه حتى في MDPs كاملة الرؤية، يمكن للاستكشاف الضعيف (توزيع الحالة الأولي) أن يخلق نقاطاً حرجة دون المستوى الأمثل. توفر طريقة k-خطوة آلية للهروب من هذه النقاط دون الحاجة إلى استكشاف أولي مثالي.

الخاتمة

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