The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective

إليك ملخص تقني مفصل للورقة البحثية بعنوان "تعقيد العينة للتعلم التعزيزي عبر الإنترنت: منظور متعدد النماذج" المنشورة في مؤتمر ICLR 2026.

1. صياغة المشكلة

تتناول الورقة البحثية تعقيد العينة للتعلم التعزيزي عبر الإنترنت (Online Reinforcement Learning) في إطار غير حلقي (non-episodic) يتضمن أنظمة ديناميكية غير خطية ذات فضاءات حالة مستمرة ($x \in \mathbb{R}^{d_x}$) وأفعال مستمرة ($u \in \mathbb{R}^{d_u}$).

• ديناميكيات النظام: يتطور النظام وفق المعادلة $x_{k+1} = f(x_k, u_k) + n_k$، حيث $f$ هي دالة غير خطية مجهولة و $n_k$ هو ضجيج العملية (غاوسي أو تحت-غاوسي).
• الهدف: يسعى صانع القرار إلى تقليل التكلفة المرحلية التراكمية المتوقعة $\mathbb{E}[\sum_{k=1}^N l(x_k, u_k)]$ من خلال تعلم سياسة تغذية راجعة $u_k = \mu_k(x_k)$.
• التحديات الرئيسية:
  • غير حلقي (Non-episodic): لا يمكن إعادة تعيين (reset) النظام؛ فالحالات مرتبطة ببعضها عبر الزمن، مما يمنع التطبيق المباشر للأدوات الإحصائية القياسية المستقلة والمتماثلة توزيعياً (i.i.d.).
  • معضلة الاستكشاف مقابل الاستغلال (Exploration-Exploitation Dilemma): يجب أن تعمل الأفعال على تحسين الأداء وكشف المعلومات حول الديناميكيات المجهولة في آن واحد.
  • اللاخطية والاستمرارية: الديناميكيات هي دوال غير خطية عامة، والفضاءات مستمرة، مما يجعل الطرق الجدولية أو الخطية التقليدية غير كافية.
  • الاستقرار: ضمان مسارات حالات محدودة وعمليات انتقالية حميدة أثناء مرحلة التعلم.

تدرس الورقة ثلاثة إعدادات محددة لفئة النماذج المرشحة $\mathcal{F}$:

1. S1 (النماذج المحدودة): مجموعة محدودة من $m$ من النماذج المرشحة غير الخطية.
2. S2 (اللانهائية/غير المعلمية): مجموعة محدودة من الدوال في فضاء متجه ذي معيار (مثل دوال ليبشيتز المحدودة).
3. S3 (المعلمية): نماذج يتم تحديد معاملاتها بواسطة متجه حقيقي مضغوط $\theta \in \Omega \subset \mathbb{R}^p$ (مثل الشبكات العصبية، أو المحولات "Transformers"، أو الأنظمة الخطية).

2. المنهجية

يقترح المؤلفون مجموعة من الخوارزميات القائمة على أخذ عينات من اللاحق (Posterior Sampling Reinforcement Learning - PSRL) مدمجة مع تحديثات من نوع Hedge والتحكم بالتكافؤ اليقيني (Certainty-Equivalent Control).

الاستراتيجية الخوارزمية الأساسية

تعمل الخوارطة في خطوات زمنية منفصلة، حيث يتم تحديث اختيار النموذج كل $M$ خطوة لضمان وجود إثارة كافية:

1. تسجيل نقاط النموذج (Model Scoring): في كل خطوة تحديث، تحسب الخوارزمية درجة خطأ التنبؤ $s_k^i$ لكل نموذج مرشح $f^i$:
   $$s_k^i = \sum_{j=1}^{k-1} \frac{|x_{j+1} - f^i(x_j, u_j)|^2}{1 + |(x_j, u_j)|^2/b^2}$$
   تعمل هذه الدرجة كلوغاريتم سالب للاحتمالية (بافتراض الضجيج الغاوسي). ويضمن حد التطبيع بقاء القيمة محدودة حتى مع الحالات الكبيرة.
2. أخذ عينات من اللاحق (تحديث Hedge): تأخذ الخوارزمية عينة من المؤشر $i_k$ (أو المعلم $\theta_k$) من توزيع يتناسب مع $\exp(-\eta s_k^i)$، حيث $\eta$ هو معدل التعلم. هذا يشبه خوارزمية Hedge في التعلم عبر الإنترنت ولكن تم تكييفه للأنظمة الديناميكية المعتمدة.
3. التحكم بالتكافؤ اليقيني: بمجرد أخذ عينة من نموذج ما، يتم حساب سياسة تحكم $\mu_{i_k}$ لهذا النموذج المحدد (على سبيل المثال، عبر البرمجة الديناميكية، أو التحكم التنبئي بالنماذج "MPC"، أو PPO).
4. الإثارة (Excitation): يكون مدخل التحكم الفعلي هو $u_k = \mu_{i_k}(x_k) + n_{u_k}$، حيث $n_{u_k}$ هو ضجيج غاوسي مضاف. هذا الاستمرار في الإثارة (Persistence of Excitation - PE) أمر بالغ الأهمية لضمان تقارب توزيع اللاحق بسرعة نحو النموذج الحقيقي.

الإطار النظري

• مبدأ الفصل (Separation Principle): يفصل النهج بين تحديد النموذج (عبر أخذ عينات من اللاحق) وتخليق التحكم (سياسة التكافؤ اليقيني).
• تحليل ليابونوف (Lyapunov Analysis): يستخدم المؤلفون دالة التكلفة المستقبلية $V(x)$ كدالة ليابونوف لإثبات الاستقرار ومحدودية مسارات الحالة.
• الافتراضات:
  • الواقعية (Realizability): الديناميكيات الحقيقية $f$ موجودة ضمن المجموعة المرشحة $\mathcal-F$ (تم تخفيف هذا الافتراض في الملحق G).
  • الاستمرار في الإثارة (PE): شرط يضمن أن مسار النظام يوفر معلومات كافية للتمييز بين النماذج.
  • النعومة/التبدد (Smoothness/Dissipation): استمرارية ليبشيتز للديناميكيات والسياسات، وعدم تباين من نوع بيلمان يميز تبدد النظام.

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

1. ضمانات الندم التكرارية غير التقاربية (Non-Asymptotic Frequentist Regret Guarantees): على عكس أعمال PSRL السابقة التي غالبًا ما تقدم حدود الندم البايزي أو تعتمد على افتراضات الاختلاط، توفر هذه الورقة حدود ندم السياسة التكرارية (Frequentist) التي تنطبق على أي تحقق محدد للبيئة، وهي قابلة للتطبيق حتى بالقرب من حدود الاستقرار.
2. منظور متعدد النماذج للأنظمة غير الخطية: تعمم هذه الدراسة تحليل تعقيد العينة من الأنظمة الخطية إلى فئات واسعة من الأنظمة غير الخطية، بما في ذلك الأنظمة ذات فئات النماذج اللانهائية والشبكات العصبية المعلمية.
3. حدود الندم المبتكرة:
   • النماذج المحدودة (S1): يتدرج الندم كـ $O(\frac{d_u \ln(N) + d_u \ln(m)}{\Delta})$، حيث $\Delta$ هو انفصال النماذج.
   • غير المعلمية (S2): يتدرج الندم كـ $O(N\epsilon^2 + \frac{d_u \ln(N) + d_u \ln(m(\epsilon))}{\epsilon^2})$، حيث $m(\epsilon)$ هو عدد التعبئة.
   • المعلمية (S3): يتدرج الندم كـ $O(\sqrt{d_u N p})$، حيث $p$ هو عدد المعلمات. وهذا يستعيد النتائج المعروفة للمنظمات التربيعية الخطية (LQR) مع التوسع لتشمل الديناميكيات المعلمية غير الخطية العامة.
4. الاستقرار والمحدودية: تثبت الورقة أن مسارات الحالة تظل محدودة (تحت-غاوسية) وتتقارب في وقت محدد بشكل شبه مؤكد، مما يعالج قلقًا أساسيًا في التحكم التكيفي.
5. العملية: تتجنب الخوارزميات حساب السياسات المتفائلة أو مناطق الثقة المعقدة (خلافًا لطرق "التفاؤل في مواجهة عدم اليقين")، مما يجعلها أسهل في التنفيذ والدمج مع تقنيات التحكم الموجودة مثل MPC.

4. النتائج الرئيسية

• النظرية 2.1 (S1): بالنسبة لمجموعة محدودة من النماذج، يتم تقييد ندم السياسة بمصطلحات لوغاريتمية في الأفق $N$ وعدد النماذج $m$.
• النظرية 2.2 (S2): بالنسبة لفئات الدوال اللانهائية، يعتمد الندم على عدد التعبئة $m(\epsilon)$. بالنسبة لدوال ليبشيتز المحدودة، يكون الندم دون خطي ($o(N)$).
• النظرية 2.3 (S3): بالنسبة للنماذج المعلمية (مثل الشبكات العصبية)، يكون الندم $O(\sqrt{d_u N p})$. وهذا يطابق المعدل الأمثل للأنظمة الخطية ولكنه ينطبق على الديناميكيات المعلمية غير الخطية العامة.
• التجارب العددية:
  • الأنظمة الخطية: أظهرت تقاربًا سريعًا نحو أداء مستقر قريب من الأمثل (في غض- 20 خطوة) حتى مع وجود 10,000 نموذج مرشح.
  • البندول غير الخطي: نجحت في التحكم في مهمة رفع التأرجح لنظام (cart-pole)، حيث لم تكن الديناميكيات الحقيقية ضمن المجموعة المرشحة (خطأ في التوصيف)، حيث تقاربت نحو توازن مستقر في حوالي 100 خطوة.
  • القابلية للتوسع: عملت الخوارزميات بكفاءة على جهاز كمبيوتر محمول قياسي، وكان عنق الزجاجة هو تقييم السياسة (MPC) وليس أخذ عينات النموذج.

5. الأهمية

تجسّر هذه الورقة الفجوة بين نظرية التعلم الإحصائي، التحسين عبر الإنترنت، ونظرية التحكم.

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

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