ملخص تقني: التدرج الطبيعي للسياسة كعملية تكرار سياسة مزدوجة التنعيم

بيان المشكلة

تُنمذج مشكلات التعلم التعزيزي (RL) عادةً كعمليات قرار ماركوف (MDPs). وبينما تعتمد طرق البرمجة الديناميكية الكلاسيكية مثل تكرار السياسة (PI) وتكرار القيمة (VI) على خصائص التقلص (contraction) والرتابة (monotonicity) لمؤثر بيلمان، فإن الطرق الحديثة القائمة على التدرج مثل التدرج الطبيعي للسياسة (NPG) ومتوسط التدرج المزدوج للسياسة (PDA) غالباً ما تُحلل من منظور التحسين المستمر عبر فضاء السياسة.

هناك فجوة مفاهيمية في الأدبيات: إذ تفشل التحليلات الخاصة بـ NPG في الاستفادة من خاصية تقلص مؤشر $\ell_\infty$-norm لمؤثر بيلمان، والتي تشكل حجر الزاوية لضمانات التقارب القوية في الطرق الكلاسيكية. ونتيجة لذلك، تعاني النتائج النظرية الحالية لـ NPG من واحد أو أكثر من القيود التالية:

1. غياب التقارب الهندسي العالمي.
2. الاعتماد على توزيعات الحالة الأولية أو معاملات التركيز (concentrability coefficients).
3. الحاجة إلى تنظيم إضافي للمُدخلات (MDP) أو للخوارزمية لاستحثاث الانحناء (curvature).
4. الاعتماد على أحجام خطوة تكيفية تعتمد على المسار (trajectory-dependent).

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

المنهجية: تكرار السياسة مزدوج التنعيم (DSPI)

يقدم المؤلفون إطار عمل خوارزمي موحد يُسمى تكرار السياسة مزدوج التنعيم (DSPI)، وهو مُصاغ كإطار عمل لمؤثر بيلمان. يقوم DSPI بتحديث السياسة عبر خطوة جشعة مُنظمة (regularized greedy step) تُطبق على متوسط مرجح لـ دالات Q السابقة.

يتضمن جوهر DSPI مستويين من التنعيم:

1. تنعيم المتوسط (Averaging Smoothing): بدلاً من استخدام أحدث دالة Q فقط، تحتفظ الخوارزمية بمتوسط متحرك ($\bar{Q}_k$) لجميع دالات Q السابقة.
2. تنعيم التنظيم (Regularization Smoothing): تُستبدل خطوة السياسة الجشعة بخطوة مُنظمة (مثل softmax) تتضمن دالة مقعرة $\nu(\cdot)$ (مثل الإنتروبيا).

يتم تعريف قاعدة التحديث كالتالي:
$$\pi_{k+1}(s) \in \arg\max_{\mu \in \Delta(A)} \left\{ \mu^\top \bar{Q}_{k+1}(s) + \eta_k \nu(\mu) \right\}$$
حيث $\bar{Q}_{k+1} = (1-\beta_k)\bar{Q}_k + \beta_k Q_{\pi_k}$، ويكون معامل التنعيم $\eta_k$ متناقصاً هندسياً بناءً على أحجام الخطوات $\beta_k$.

ومن الأهمية بمكان أن المؤلفين أثبتوا أن DSPI يقبل صياغة مدمجة باستخدام مؤثرات بيلمان المُنعمة ($H_\eta$ و $H^\pi_\eta$). وهذا يسمح بتحليل الخوارزمية باستخدام خصائص الرتابة والتقلص لهذه المؤثرات، بدلاً من الاعتماد حصرياً على أدوات نظرية التحسين.

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

1. توحيد الخوارزميات

يؤسس البحث أن DSPI هو إطار عمل عام يشمل عدة خوارزميات رئيسية كحالات خاصة:

• تكرار السياسة (PI): يتم استرداده عندما يكون حجم الخطوة $\beta_k \equiv 1$ (لا يوجد متوسط) ويتلاشى التنظيم.
• التدرج الطبيعي للسياسة (NPG): يتم استرداده عند ضبط $\nu(\cdot)$ لتكون إنتروبيا شانون واختيار جداول زمنية محددة لحجم الخطوة.
• متوسط التدرج المزدوج للسياسة (PDA): يتم استرداده باختيار $\nu(\cdot)$ كدالة توليد تباعد مُزاحة.
• تكرار السياسة ذو المتوسط المزدوج: وهو نوع جديد حيث تُحدث السياسة بشكل جشع بناءً على متوسط دالات Q ($\nu(\cdot) \equiv 0$).

2. تحليل تقارب موحد

من خلال الاستفادة من خصائص مؤثرات بيلمان المُنعمة، يقدم المؤلفون تحليلاً موحداً للتقارب لـ DSPI:

• التقارب التقاربي (Asymptotic Convergence): تم إثباته لأي تسلسل أحجام خطوة غير قابل للجمع (non-summable).
• التقارب الهندسي العالمي: تم إثباته لأحجام الخطوة الثابتة. ويُعطى حد الخطأ كما يلي:
  $$\|V^* - V^{\pi_k}\|_\infty \leq (1 - (1-\gamma)\beta)^{k-1} (\gamma \|V^* - V^{\pi_0}\|_\infty + \tau \nu_{\max})$$
  حيث $\gamma$ هو عامل الخصم و $\beta$ هو حجم الخطوة الثابت.

3. ضمانات نظرية محسنة لـ NPG و PDA

بتطبيق إطار DSPI على NPG و PDA، نحصل على النتائج التالية، والتي تُحسن أو تضاهي أحدث ما توصل إليه العلم دون اشتراط فرضيات مقيدة:

• خالٍ من التوزيع (Distribution-Free): تعتمد حدود التقارب فقط على $\ell_\infty$-norm لفجوة دالة القيمة، وليس على توزيع الحالة الأولية أو معاملات التركيز.
• لا يتطلب تنظيماً إضافياً: يظل التحليل صالحاً دون تعديل الـ MDP أو إضافة منظمات إضافية بخلاف حد الإنتروبيا المتأصل في NPG القياسي.
• أحجام خطوة بسيطة: تسري النتائج على جدول أحجام خطوة متزايد هندسياً بسيط ومحدد مسبقاً ($\alpha_k = \beta \alpha_0 / (1-\beta)^k$)، مما يلغي الحاجة إلى أحجام الخطوة التكيفية التي تعتمد على مسار السياسة أو خطأ بيلمان.
• تعقيد التكرار: يحقق NPG و PDA سياسة مثالية بمقدار $\epsilon$ في عدد تكرارات قدره $O((1-\gamma)^{-1} \log((1-\gamma)^{-1}\epsilon^{-1}))$.

4. الإنهاء المحدود لـ Dual-Averaged PI

بالنسبة للحالة غير المنظمة (Dual-Averaged PI)، أثبت المؤلفون الإنهاء المحدود. تجد الخوارزمية سياسة مثالية في $O(mn(1-\gamma)^{-1} \log((1-\gamma)^{-1}))$ تكراراً على الأكثر، حيث $n$ و $m$ هما حجم فضاء الحالة والفعل. ويتحقق ذلك من خلال إظهار أن الخوارزمية تستبعد فعلاً واحداً على الأقل غير مثالي كل $k^*$ تكرار.

5. التوسعات

يُظهر الإطار أنه يتوسع بشكل طبيعي ليشمل:

• التقريب الوظيفي الخطي (Linear Function Approximation): يحقق DSPI مع التقريب الوظيفي الخطي تقارباً هندسياً حتى خطأ التقريب الوظيفي.
• مشكلات المسار الأقصر العشوائي (SSP): يمتد التحليل إلى مشكلات SSP غير مخصومة، مما يثبت التقارب الهندسي العالمي الخالي من التوزيع تحت افتراض أن جميع السياسات المستقرة هي سياسات ملائمة (proper).

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

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

1. استعادة الضمانات القوية: إرساء تقارب هندسي عالمي لـ NPG و PDA باستخدام الخصائص الجوهرية لمؤثر بيلمان (الرتابة والتقلص).
2. إزالة الشوائب: التخلص من الحاجة إلى التنظيم الذي "يستحث الانحناء" أو أحجام الخطوة التكيفية التي كانت مطلوبة غالباً في التحليلات القائمة على التحسين.
3. تبسيط التحليل: تقديم تحليل أبسط وأكثر منهجية يتجنب تعقيدات معاملات عدم تطابق التوزيع.

يشير المؤلفون إلى أنه بينما يفترض تحليلهم الحالي الوصول إلى دالات Q الدقيقة (لعزل ديناميكيات تحسين السياسة)، فإن هذا الإطار يمهد الطريق للعمل المستقبلي في البيئات التي لا تعتمد على النموذج (model-free)، حيث يجب تقدير دالات Q. وقد حددوا الجمع بين DSPI وضمانات تقييم السياسة في زمن محدود كخطوة تالية غير بديهية لتحقيق نتائج حادة في تعقيد العينات للتعلم التعزيزي الذي لا يعتمد على النموذج.