Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

ملخص تقني: معدلات التقارب شبه المؤكد للتقريب العشوائي والتعلم التعزيزي عبر انزياح بويسون-مورو

بيان المشكلة
يتناول البحث التحدي النظري الجوهري المتمثل في إثبات معدلات التقارب شبه المؤكد لخوارزميات التقريب العشوائي (SA) والتعلم التعزيزي (RL) التي تعمل تحت ظروف الضجيج الماركوفي (Markovian noise). بينما تثبت النظرية الكلاسيكية (مثل طريقة الـ ODE) أن المتتاليات $\{\theta_n\}$ تتقارب شبه مؤكد، إلا أنها غالباً ما تفشل في تحديد سرعة هذا التقارب لمسارات العينات الفردية. تواجه الأدبيات الحالية المتعلقة بمعدلات التقارب شبه المؤكد قيوداً كبيرة:

1. تعتمد العديد من النتائج على ضجيج مستقل ومتماثل التوزيع (i.i.d.)، وهو ما لا يعكس عملية أخذ العينات من المسار الواحد الشائعة في التعلم التعزيزي.
2. تتطلب النتائج التي تتعامل مع الضجيج الماركوفي أن يكون التحديث المتوقع خطياً أو تعتمد على أنظمة معدل تعلم مقيدة.
3. العمل الأخير لـ Qian وآخرون [2024] يتعامل مع الضجيج الماركوفي باستخدام خرائط تقبض عامة، لكنه يعطي معدلات تقارب أبطأ ويفشل في تغطية أنظمة معينة لمعدل التعلم (تحديداً $\eta \in (1/2, 2/3]$).

يركز المؤلفون على فئة من خوارزميات التقريب العشوائي حيث يكون التحديث المتوقع تقبضياً (ربما في معيار غير إقليدي، مثل $\ell_\infty$) ويكون الضجيج عبارة عن سلسلة ماركوف. يشمل هذا الإطار خوارزميات أساسية في التعلم التعزيزي مثل Q-learning وتعلم الفرق الزمني (TD) الخطي.

المنهجية: انزياح بويسون-مورو (Poisson-Moreau Drift)
الابتكار التقني الجوهري هو بناء دالة انزياح ليبوف (Lyapunov drift) جديدة، تُسمى انزياح بويسون-مورو. يجمع المؤلفون بين تقنيتين راسختين مع آلية تصحيح جديدة:

1. تنعيم غلاف مورو (Moreau-Envelope Smoothing): للتعامل مع الخريطة التقبضية $T$ التي قد تكون معرفة تحت معيار غير إقليدي $\|\cdot\|$, يستخدم المؤلفون غلاف مورو $M_\xi$. يقوم هذا بتنعيم دالة الطاقة القائمة على المعيار غير القابلة للاشتقاق إلى دالة $M_\xi(x)$ قابلة للاشتقاق باستمرار، مما يسمح بالتحليل القائم على التدرج مع الحفاظ على خصائص التقبض.
2. تصحيح معادلة بويسون (Poisson-Equation Correction): لمعالجة الضجيج الماركوفي، يطبق المؤلفون تصحيحاً يعتمد على معادلة بويسون. يتم تفكيك حد الضجيج $F(\theta, Y) - f(\theta)$ إلى فرق مارتينجال وباقٍ متسلسل (telescoping remainder) باستخدام حل $H_\theta$ لمعادلة بويسون: $H_\theta(y) - (PH_\theta)(y) = F(\theta, y) - f(\theta)$.
3. البناء المبتكر: على عكس الأعمال السابقة التي إما تأخذ التوقعات الكلية (مما يفقد التحكم في المسار) أو تستخدم "المتتاليات الهيكلية" (subsequences)، يدمج المؤلفون التصحيح البويسوني مباشرة في دالة ليبوف. يعرّفون الانزياح كالتالي:
   $$V_n^\xi = M_\xi(e_n) + \alpha_n \langle \nabla M_\xi(e_n), H_{\theta_n}(Y_n) \rangle + K \alpha_n^2$$
   حيث $e_n = \theta_n - \theta^*$ هو الخطأ، و$\alpha_n$ هو معدل التعلم، و$K$ ثابت كبير بما يكفي.
   • الحد الأوسط (تصحيح بويسون) يلغي حد الانحياز الرئيسي الناجم عن الاعتماد الماركوفي في الانزياح الشرطي.
   • الحد الأخير ($K \alpha_n^2$) يضمن بقاء الانزياح غير سالب ويتحكم في الحدود المتبقية.

يسمح هذا البناء للمؤلفين بإثبات أن $V_n^\xi$ يحقق متباينة شبه-سوبر-مارتينج (almost-supermartingale) مباشرة على التوقع الشرطي، مما يتيح تطبيق نظريات معدلات تقارب شبه-السوبر-مارتينج الحديثة (Liu and Yuan [2024]) على المتتالية الكاملة من التكرارات، وليس فقط على المتتاليات الفرعية.

النتائج الرئيسية
تحت فرضيات التحديثات المتوقعة التقبضية، والاستمرارية ليبشيتز، ووجود حل لمعادلة بويسون للسلسلة الماركوفية، يستنتج البحث معدلات التقارب شبه المؤكد التالية للخطأ $\|\theta_n - \theta^*\|$:

• معدلات التعلم ذات القوة (Power-law learning rates) $\alpha_n = O(n^{-\eta})$ مع $\eta \in (1/2, 1)$:
  يتقارب الخطأ شبه مؤكد بمعدل قريب جداً من $o(n^{-(2\eta - 1)})$.
• معدلات التعلم التوافقية (Harmonic learning rates) $\alpha_n = O(n^{-1})$ (أي $\eta = 1$):
  يتقارب الخطأ شبه مؤكد بمعدل قريب جداً من $o(n^{-1})$.
  • يشير المؤلفون إلى أن هذه نتيجة قوية، تقترب من المعدل الأمثل $O(n^{-1} \log \log n)$ الذي تمنحه قانون اللوغاريتم المتكرر للقيم المتطرفة (law of the iterated logarithm) للضجيج المستقل والمتماثل التوزيع (i.i.d.).

المقارنة مع الأعمال السابقة

• مقابل Qian et al. [2024]: الطريقة المقترحة تغطي نطاقاً أوسع من معدلات التعلم (تحديداً $\eta \in (1/2, 2/3]$ حيث لا تقدم Qian et al. أي معدلات) وتحقق معدلات تقارب أسرع بشكل ملحوظ لـ $\eta \in (2/3, 1]$.
• مقابل التحليلات القائمة على التوقع: توفر الطريقة ضمانات مسارية (شبه مؤكدة) بدلاً من مجرد التقارب في التوقع أو الاحتمال.
• نتيجة جانبية: من خلال أخذ التوقعات غير المشروطة لمتساوية الانزياح، يستنتج المؤلفون أيضاً معدلات تقارب $L_2$ للنطاق الكامل $\eta \in (0, 1]$، مما يظهر أن $E[\|\theta_n - \theta^*\|^2] = O(n^{-\eta})$ لـ $\eta < 1$.

التطبيقات
يتم تطبيق الإطار التقني على عائلة معممة من خوارزميات TD الجدولية (tabular TD) مع عوامل أخذ عينات بأهمية متغيرة (importance sampling) معممة. هذا النموذج الموحد يستعيد عدة خوارزميات قياسية، بما في ذلك:

• $n$-step TD (داخل السياسة وخارج السياسة).
• $Q^\pi(\lambda)$، وTree-Backup، وRetrace، وQ-trace.

بالنسبة لهذه الخوارزميات، يتحقق البحث من أن الشروط الهيكلية (مصفوفة هورويتز للمؤثر المتوسط، وجود حلول بويسون للسلاسل ذات الحالات المحدودة) تتحقق، مما يثبت أول معدلات تقارب مسارية شبه مؤكدة لنسخة المسار الواحد من عمليات TD المعممة هذه تحت أخذ العينات الماركوفية.

الأهمية والادعاءات
يدعي البحث تقديم معدلات تقارب شبه مؤكد أكثر دقة للتقريبات العشوائية العامة تحت الضجيج الماركوفي والتقبض غير الإقليدي. تكمن الأهمية في:

1. الابتكار التقني: يُقدم "انزياح بويسون-مورو" كبناء مبتكر ينجح في سد الفجوة بين التعامل مع التقبضات غير الإقليدية (عبر أغلفة مورو) والضجيج الماركوفي (عبر تصحيحات بويسون) ضمن إطار عمل شبه-سوبر-مارتينج واحد.
2. الدقة (Tightness): يُقال إن المعدلات المستمدة للتعلم التوافقي ($\eta=1$) قريبة من الحد الأمثل نظرياً، وتتفوق على النتائج السابقة في أدبيات التعلم التعزيزي.
3. الاكتمال: يسد العمل فجوة في الأدبيات من خلال معالجة الجمع المحدد بين الضجيج الماركوفي وخرائط التقبض العامة (غير الخطية وغير الإقليدية)، وهو إطار يميز خوارزميات التعلم التعزيزي الحديثة.

يظل المؤلفون متواضعين فيما يتعلق بدقة المعدلات، حيث يقرون بأنه رغم كون نتائجهم أكثر دقة من الأدبيات الحالية، إلا أنها لا تطابق تماماً حد $O(n^{-1} \log \log n)$ الخاص بقانون اللوغاريتم المتكرر للقيم المتطرفة. كما يشيرون أيضاً إلى أن تمديد معدلات التقارب شبه المؤكد إلى النطاق الكامل $\eta \in (0, 1]$ (المثبت حالياً لـ $L_2$) يظل سؤالاً مفتوحاً.