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

بيان المشكلة

يُعد تعلم الفرق الزمني (TD) حجر الزاوية في التعلم المعزز، ومع ذلك، فإن تحليله النظري في حالة المكافأة المتوسطة (average-reward setting) يتخلف بشكل كبير عن حالة المكافأة المخصومة (discounted setting). في الحالة المخصومة، يكون مؤثر بلمان (Bellman operator) تطبيق تقليص (contraction mapping)، مما يضمن حلولاً فريدة وتحليلاً مباشراً للتقارب. وعلى العكس من ذلك، في حالة المكافأة المتوسطة، لا يكون مؤثر بلمان تقليصياً بالنسبة لأي معيار (norm)، كما أن الحل لمعادلة بلمان المقابلة ليس فريداً (فهو مُعرف فقط حتى ثابت مضاف).

تعاني الأدبيات الحالية التي تتناول تعلم TD للمكافأة المتوسطة من عدة قيود مقارنة بالحالة المخصومة:

1. افتراضات مقيدة: تتطلب العديد من الطرق افتراضات (مثل $\Phi\theta \neq ce$) التي تستبعد الإعداد الجدولي (tabular setting).
2. ضمانات التقارب: تضمن بعض النهج التقارب إلى نقطة ثابتة تعتمد على مسار العينة أو إلى مجموعة، بدلاً من حل محدد وفريد.
3. الاعتماد على الأبعاد: غالباً ما تحتوي حدود التقارب على عوامل صريحة لـ بُعد المعاملات $d$.
4. تدرج معامل الحالة (Condition Number Scaling): تُظهر تعقيدات العينات في أحدث ما توصل إليه العلم اعتماداً رباعياً على معامل حالة المسألة ($O(\eta^{-4})$)، بينما يحقق الإعداد المخصوم تدرجاً تربيعياً ($O(\eta^{-2})$).
5. التعقيد الخوارزمي: تطلب تحقيق تدرج أفضل في الأعمال السابقة تقنيات معقدة لتقليل التباين (مثل الحلقات المتداخلة)، مما يبتعد عن بساطة خوارزميات TD القياسية.

المنهجية

يقترح المؤلفون نهجاً جديداً لتقييم السياسة في حالة المكافأة المتوسطة من خلال صياغة حل معادلة بلمان كـ مسألة تحسين مقيدة. وتتمثل الرؤية الجوهرية في أن دالة القيمة النسبية $W^*$ يجب أن تحقق قيد الحالة المستقرة ($\mu^\top W^* = 0$).

1. خوارزمية السلسلة المزدوجة (Double-Chain Algorithm)

لحل معادلة بلمان المسقطة $W^* = \Pi T_\pi W^*$، حيث $\Pi = I - e\mu^\top$، يشتق المؤلفون قاعدة تحديث عشوائية. ويتمثل التحدي الرئيسي في التقريب العشوائي لهذا الإعداد في مشكلة "العينات المزدوجة": تقدير حد $\mu\mu^\top(R + W_t)$ يتطلب توقع حاصل ضرب متغيرات عشوائية، وهو أمر لا يمكن تقديره من مسار واحد بسبب الارتباط.

لحل هذه المشكلة، يقدم المؤلفون خوارزمية السلسلة المزدوجة التي تستخدم سلسلتين ماركوف مستقلتين ($\{s_t\}$ و $\{\hat{s}_t\}$) في كل تكرار.

• قاعدة التحديث: يتم تحديث متجه المعامل $\theta_t$ باستخدام مكونين:
  • $g(s_t, s'_t, \theta_t)$: يُقدر حد خطأ TD القياسي $D(R + P\Phi\theta_t - \Phi\theta_t)$.
  • $f(s_t, \hat{s}_t, \theta_t)$: يُقدر حد القيد $-\mu\mu^\top(R + \Phi\theta_t)$ باستخدام العينة المستقلة $\hat{s}_t$ لكسر الارتباط.
• التقريب الخطي: تعمم الطريقة إلى التقريب الوظيفي الخطي ($W \approx \Phi\theta$) عن طريق إسقاط التحديثات على فضاء السمات.

2. خوارزمية السلسلة الواحدة (Single-Chain Algorithm)

لتجنب التكاليف الحسابية الإضافية للحفاظ على سلسلتين، يقترح المؤلفون خوارزمية السلسلة الواحدة المستوحاة من (Gradient TD (GTD.

• الآلية: بدلاً من أخذ عينة ثانية مستقلة $\hat{s}_t$، تحتفظ الخوارزمية بمتغير مساعد $w_t$ يتتبع التوقع $E[\phi(s)] = \Phi^\top\mu$.
• التحديث: يتم استبدال الحد $\phi(\hat{s}_t)$ في تحديث السلسلة المزدوجة بـ $w_t$. ويتم تحديث المتغير $w_t$ عبر خطوة تقريب عشوائي منفصلة للتقارب إلى $\Phi^\top\mu$.
• المقايضة: على الرغم من أن هذا يبسط متطلبات أخذ العينات لتصبح مساراً واحداً، إلا أن التحليل يظهر اعتماداً أسوأ قليلاً على معامل الحالة مقارنة بمتغير السلسلة المزدوجة.

3. الإطار النظري: تقسيم التدرج (Gradient Splitting)

يعتمد تحليل التقارب على تقنية تقسيم التدرج [19]. يوضح المؤلفون أن اتجاه التحديث المتوقع لخوارمايتهم يعمل كـ "تقسيم تدرج" لدالة تربيعية مركبة محددة:
$$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$$
يسمح هذا للمؤلفين بتحليل الخوارزمية باستخدام تقنيات تكرار التدرج الاشتقاقي العشوائي (SGD) القياسية، رغم الطبيعة غير التقليصية لمؤثر بلمان الأساسي.

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

يدعي البحث أنه يسد الفجوة النظرية بين تعلم TD للمكافأة المتوسطة والمخصومة من خلال تحقيق الميزات التالية في آن واحد:

1. نقطة ثابتة فريدة ومستقلة عن العينة: تتلازم الخوارزميات المقترحة تقارباً شبه مؤكد نحو حل واحد محدد $\theta^*$ يكون مستقلاً عن المسار العشوائي والتهيئة الأولية.
2. القابلية للتطبيق في الإعدادات الجدولية والخطية: ينطبق التحليل على كل من الحالات الجدولية (حيث $\Phi = I$) والتقريب الوظيفي الخطي، دون الحاجة إلى الافتراض المقيد $e \notin \text{span}(\Phi)$.
3. حدود خالية من الأبعاد: لا تحتوي حدود التقارب على عوامل صريحة للبعد $d$ (بخلاف تلك المتأصلة في $\|\theta^*\|$ أو $\|\theta_0\|$).
4. تقارب التكرار الأخير: النتائج مضمونة للتكرار الأخير، مما يطابق معايير TD المخصوم القياسية، بدلاً من الاعتماد على متوسط التكرارات.
5. تحسين تدرج معامل الحالة:
   • تحقق خوارزمية السلسلة المزدوجة تعقيد عينات قدره $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$، حيث $\eta_1$ هو معامل حالة معرف كـ $\min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$. وهذا يطابق التدرج التربيعي المشاهد في الإعداد المخصوم.
   • تحقق خوارزمية السلسلة الواحدة تعقيداً قدره $\tilde{O}(\epsilon^{-1}\eta^{-4})$ (رباعي)، وهو تحسن عن بعض الأعمال السابقة ولكنه أسوأ قليلاً من متغير السلسلة المزدوجة.
6. بساطة الخوارزمية: تم تحقيق التدرج التربيعي دون استخدام تقنيات تقليل التباين (مثل الحلقات المتداخلة أو الدفعات الكاملة الدورية)، مما يحافظ على بساطة تحديثات TD العادية.

النتائج

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

• الحدود النظرية: تثبت النظريات 4.1–4.3 معدلات التقارب وتعقيدات العينات. وتطابق طريقة السلسلة المزدوجة أحدث ما توصل إليه العلم في الـ TD المخصوم من حيث تدرج المعاملات.
• التجارب العددية: تم اختبار الخوارزميات على 15 بيئة MDP جدولية من OpenAI Gym و MO-Gymnasium.
  • تُظهر النتائج أن الطرق المقترحة تتفوق عموماً على النماذج المرجعية السابقة (بما في ذلك [10]، [11]، [12]، [17]، [18]، و [21]) من حيث خطأ التقريب بالنسبة للحل الحقيقي.
  • تؤكد التجارب أن الطرق تتقارب نحو الحل الفريد، بينما تُظهر بعض النماذج المرجعية (التي تتقارب نحو مجموعات أو نقاط تعتمد على العينة) تبايناً أو خطأً أعلى في الإعداد الجدولي.

الأهمية

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

• الوحدانية: التقارب نحو حل فريد ومعرف جيداً.
• العمومية: القابلية للتطبيق في الإعدادات الجدولية والخطية دون افتراضات مقيدة.
• الكفاءة: اعتماد تربيعي على معامل الحالة دون الحاجة إلى آليات معقدة لتقليل التباين.

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