Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs

ملخص تقني: التقارب الخطي العالمي لتدرج سياسة "softmax" المنظمة بالإنتروبي لما وراء النماذج الماركوفية (MDPs) الجدولية

بيان المشكلة
تبحث هذه الورقة في خصائص التقارب العالمي لطرق تدرج السياسة (Policy Gradient - PG) للنماذج الماركوفية (MDPs) ذات الأفق اللانهائي والمنظمة بالإنتروبي (entropy-regularized) في فضاءات الحالة والفعل المستمرة. من المعروف أن تنظيم الإنتروبي (الذي يُدخل حداً لتباعد KL بحدة $\tau > 0$) يحسن مشهد التقارب لسياسات "softmax" في الإعدادات الجدولية (فضاءات حالة $S$ وفعل $A$ محدودة)، إلا أن توسيع هذه الضمانات لتشمل الفضاءات المستمرة مع التقريب الدالي يظل تحدياً نظرياً كبيراً.

تدرس المؤلفة تحديداً سياسات "softmax" اللوغاريتمية الخطية المعرفة بـ:
$$\pi_\theta(da|s) \propto \exp(\langle \theta, g(s, a) \rangle) \mu(da)$$
حيث يمثل $g: S \times A \to \mathbb{R}^p$ قاعدة الميزات، و $\theta \in \mathbb{R}^p$ هي المعلمات، و $\mu$ هو مقياس مرجعي. الهدف هو تقليل دالة القيمة المنظمة $V^\pi_\tau(\rho)$. يكمن الصعوبة الجوهرية في عدم تقعب (non-convexity) الهدف بالنسبة لـ $\theta$، حتى مع تنظيم الإنتروبي، وفي احتمال تدهور مصفوفة معلومات فيشر (FIM) أو مصفوفات تغاير الميزات في الإعدادات المستمرة، مما قد يمنع صحة براهين التقارب القياسية.

المنهجية
يعتمد التحليل على صياغة تدفق التدرج في الزمن المستمر:
$$\frac{d}{dt}\theta_t = -\nabla_\theta V^{\pi_{\theta_t}}_\tau(\rho)$$
تتبع استراتيجية الإثبات ثلاث مراحل رئيسية:

1. متباينة "Polyak–Łojasiewicz" (PŁ) غير المنتظمة:
   يؤسس المؤلفون أولاً متباينة PŁ غير منتظمة من الشكل:
   $$V^{\pi_\theta}_\tau(\rho) - V^{\pi^*_\tau}_\tau(\rho) \leq C(\theta) \|\nabla_\theta V^{\pi_\theta}_\tau(\rho)\|^2$$
   تربط هذه المتباينة بين فجوة دون الأمثلية وبين مربع معيار التدرج. ومن الأهمية بمكان أن الثابت $C(\theta)$ يعتمد على هندسة السياسة، وتحديداً أصغر قيمة ذاتية لـ FIM (أو مصفوفة تغاير الميزات غير المركزية للميزات من نوع simplex) وحدود كثافة السياسة. وخلافاً للحالة الجدولية حيث يكون $C$ ثابتاً منتظماً، فإن $C(\theta)$ هنا غير منتظم ويمكن أن يتدهور نظرياً عندما $\|\theta\| \to \infty$.

2. افتراض تحقق $Q\pi_\tau$:
   يفترض التحليل أنه لأي سياسة $\pi$، يمكن تمثيل دالة قيمة الحالة-الفعل المنظمة $Q^\pi_\tau$ بدقة باستخدام قاعدة الميزات الخطية:
   $$\langle \theta(\pi), g(s, a) \rangle = -\frac{1}{\tau} Q^\pi_\tau(s, a)$$
   يضمن هذا الافتراض أن السياسة المثلى $\pi^*_\tau$ تقع ضمن الفئة المعلمة، أي $\pi^*_\tau = \pi_{\theta^*}$ لبعض $\theta^*$.

3. تحليل ليابونوف وعدم الارتباط الشعاعي:
   لإثبات التقارب الخطي العالمي، يجب على المؤلفين إثبات أن الثابت غير المنتظم $C(\theta_t)$ يظل محدوداً على طول مسار تدفق التدرج. يتطلب ذلك إثبات أن المسار $\{\theta_t\}$ يظل داخل مجموعة متراصة.

   • يستخدمون الهدف المنظم بالإنتروبي $V^{\pi_\theta}_\tau(\rho)$ كدالة ليابونوف، ملاحظين أنها تتناقص رتيباً.
   • يثبتون أنه تحت شروط محددة على قاعدة الميزات $g$، يكون تباعد KL غير مرتبط شعاعياً (أي $KL \to \infty$ عندما $\|\theta\| \to \infty$). هذه الخاصية تمنع المعلمات من التباعد إلى اللانهاية بينما تظل دالة القيمة محدودة، مما يضمن بقاء المسار ضمن منطقة متراصة حيث تكون القيم الذاتية للمصفوفات ذات الصلة محدودة بعيداً عن الصفر.

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

تحدد الورقة نظامين متميزين لقواعد الميزات يتم فيهما تحقيق التقارب الخطي العالمي:

1. ميزات الامتداد الأفقي الكامل (Full-Affine-Span Features):

   • الافتراض: خريطة الميزات $g(s, \cdot)$ تمتلك أبعاداً أفقية كاملة، ومجموعة الماكسيمات (maximizers) لأي إسقاط خطي لـ $g$ لها قياس صفري تحت $\mu$.
   • النتيجة: تباعد KL غير مرتبط شعاعياً في جميع الاتجاهات. وبالتالي، تظل أصغر قيمة ذاتية لـ FIM محدودة من الأسفل بثابت موجب يعتمد على التهيئة الأولية.
   • التقارب: تتناقص دون الأمثلية بمعدل $O(e^{-Ct})$ لبعض $C > 0$.

2. الميزات ذات قيم الـ "simplex":

   • الافتراض: تقع الميزات في "simplex الاحتمالي" ($\sum g_i = 1, g_i \geq 0$). يتم تخفيف الشرط المتعلق بمجموعة الماكسيمات ليطبق فقط على المتجهات المتعامدة مع متجه الواحدات (all-ones vector).
   • النتيجة: تباعد KL غير مرتبط شعاعياً فقط في الفضاء الجزئي المتعامد مع متجه الواحدات (اتجاه تكرار المعلمات). يثبت المؤلفون أن تدفق التدرج يحافظ على إسقاط $\theta$ على متجه الواحدات، مما يحصر الديناميكيات فعلياً في الفضاء الجزئي ذي الصلة.
   • التقارب: باستخدام مصفوفة تغاير غير مركزية بدلاً من FIM، يضعون حداً أدنى منتظماً للقيم الذاتية، مما يؤدي إلى نفس معدل التقارب الخطي العالمي $O(e^{-Ct})$.

الأهمية والادعاءات
يزعم المؤلفون أن هذا العمل يوسع نظرية التقارب العالمي لتدرج سياسة "softmax" المنظمة بالإنتروبي لما وراء الإعدادات الجدولية التي وضعها Agarwal et al. (2020)، و Bhandari and Russo (2024)، و Mei et al. (2020).

• الجدة في الإعدادات المستمرة: تعالج هذه الورقة عدم القدرة الحسابية للطرق الجدولية في الفضاءات المستمرة من خلال تحليل صارم للتقريب الدالي الخطي.
• التعامل مع عدم التقعب: من خلال إنشاء متباينة PŁ غير منتظمة والتحكم في الثابت غير المنتظم عبر تقنيات ليابونوف، يتغلب المؤلفون على عدم تقعب تمثيل "softmax" للمعلمات.
• دور تنظيم KL: تسلط الورقة الضوء على استخدام مبتكر لتباعد KL كدالة ليابونوف لضمان عدم الارتباط الشعاعي، وهي خاصية لا تتحقق في الحالة الجدولية القياسية (حيث يكون حد KL منتهياً لأي سياسة ذات دعم كامل).
• حساسية الميزات: توفر الورقة أمثلة محددة (مثل الميزات المثلثية، أو كثيرات حدود بيرنشتاين) التي تستوفي شروط التقارب، ونماذج مضادة (مثل دالات "hat functions") حيث يفشل الارتباط الشعاعي، مما يوضح الخصائص الهندسية اللازمة لقواعد الميزات لتحقيق التقارب الخطي.

تشير النتائج إلى أنه، تحت شرط تحقق $Q^\pi_\tau$ وشروط الميزات المناسبة، يتقارب تدرج السياسة المنظم بالإنتروبي عالمياً وبشكل خطي نحو السياسة المثلى في فضاءات الحالة والفعل العامة، محققاً المعدلات المواتية المعروفة سابقاً فقط في الإعدادات الجدولية أو الخطية-التربيعية.