Learning Kernel-Based MDPs from Episodic Preferential Feedback

ملخص تقني: تعلم نماذج ماركوف لاتخاذ القرار (MDPs) القائمة على النواة من التغذية الراجعة التفضيلية العرضية

صياغة المشكلة
يتناول هذا العمل مشكلة التعلم المعزز من التغذية الراجعة البشرية (RLHF) ضمن إطار عمليات ماركوف لاتخاذ القرار (MDPs) العرضية. وخلافاً للتعلم المعزز القياسي حيث يتلقى الوكلاء مكافآت عددية، يتلقى المتعلم هنا تغذية راجعة تفضيلية ثنائية فقط. في كل حلقة (episode) $k$، يقوم المتعلم بنشر سياسات، $\pi$ و $\pi'$، من حالة بداية مشتركة لتوليد مسارين، $\tau_k$ و $\tau'_k$. وتتكون التغذية الراجعة من تسمية ثنائية واحدة $y_k \in \{0, 1\}$ تشير إلى أي المسارين هو المفضل. يتم نمذجة هذا التفضيل عبر دالة ربط "برادلي-تيري-لوتش" (BTL) مطبقة على الفرق بين المكافآت التراكمية (غير المرصودة):
$$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$$
حيث $\sigma$ هي دالة السجمويد (sigmoid). والهدف هو تعلم سياسة تعظم دالة القيمة $V^\pi_1$ مع تقليل الندم التراكمي، المعرف بأنه الفرق بين القيمة المثلى ومتوسط قيم السياسات المستخدمة.

يفترض هذا الإعداد هيكل نواة MDP، حيث تكون دالة المكافأة $r_h$ وعامل الانتقال $P_h$ عناصر في فضاء هيلبرت لإعادة الإنتاج (RKHS) $\mathcal{H}_k$ المستحث بواسطة نواة معروفة $k$. وبشكل محدد، يركز المؤلفون على عائلة نواة ماتيرن (Matérn kernel family)، التي تلتقط الهياكل غير الخطية وتكافئ في خصائصها فضاءات سوبوليف (Sobolev spaces)، مما يوفر تعميماً يتجاوز نماذج MDP الخطية.

المنهجية: خوارزمية PROSTO
يقترح المؤلفون خوارزمية PROSTO (التحسين المنظم القائم على التفضيل عبر التفاؤل المستحث من المسارات المأخوذة بالعينة). تعمل الخوارزمية في حلقات وتستخدم نهج تكرار القيمة (value iteration) المتكيف مع التغذية الراجعة التفضيلية وتقريب دالة النواة.

1. تقدير المكافأة عبر الانحدار اللوجستي للنواة المنظم (KLRR):
   بما أن التغذية الراجعة على مستوى المسار وثنائية، يتم تقدير متجه المكافأة $\theta$ باستخدام تقدير الإمكان الأعظم مع عقوبة موزونة بالمعيار. يقوم المقدر $\hat{\theta}_k$ بتقليل السلب اللوغاريتمي للاحتمالية للمفضلات المرصودة بالإضافة إلى حد التنظيم $\tau \|\theta\|^2_{\mathcal{H}_k}$. وتكون المتغيرات التفسيرية لهذا الانحدار هي ميزات فرق المسار $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$.

2. الاستكشاف عبر اضطراب العملية الغاوسية (GP) العشوائي:
   لضمان استكشاف كافٍ على مستوى المسار دون معرفة ديناميكيات الانتقال مسبقاً (مما يمنع مكافآت الإهليلج الحتمية)، تستخدم PROSTO استكشافاً عشوائياً. يتم أخذ متجه ضوضاء الاستكشاف $\epsilon_k$ من عملية غاوسية (GP) ذات هيكل تباين يعتمد على التباين التجريبي لفروق المسارات. تُضاف هذه الضوضاء إلى تقدير المكافأة لإحداث حالة من التفاؤل.

3. تقدير دالة القيمة عبر انحدار ريج من النواة (KRR):
   يتم تقدير دالة القيمة بشكل تكراري. يتم تقريب القيمة المتوقعة للحالة التالية باستخدام انحدار ريج من النواة القياسي على عينات الانتقال. يجمع تقدير دالة Q النهائي $\hat{Q}^k_h$ بين تقدير المكافأة (KLRR + ضوضاء GP) وتقدير الانتقال (KRR)، مع الخضوع للقص (clipping) لضمان المحدودية.

4. تنفيذ السياسة:
   يختار المتعلم سيستين، $\pi$ و $\pi'$، وهما سيستان "جشعتان" بالنسبة لتقديرات دالة Q المتفائلة الخاصة بهما. يتم تنفيذ هاتين السيستين لتوليد مسارات الحلقة التالية والتغذية الراجعة التفضيلية.

المساهمات التقنية والتحديات الرئيسية
حدد البحث ثلاثة تحديات تقنية رئيسية خاصة بدمج نماذج Kernel MDP مع التغذية الراجعة التفضيلية على مستوى المسار، وقدم حلولاً مبتكرة لها:

• التحكم في أعداد التغطية اللوغاريتمية: في نماذج Kernel MDP، ينمو العدد اللوغاريتمي لتغطية فئة دالة القيمة بشكل متعدد الحدود مع مقلوب مش (mesh) التغطية $\epsilon$ ويعتمد على معايير RKHS للمقدرات. وخلافاً لنماذج MDP الخطية، حيث تكون أعداد التغطية لوغاريتمية في عدد الحلقات، يمكن أن تؤدي إعدادات النواة إلى حدود ندم غير ذات معنى إذا نمت معايير المقدرات بشكل كبير جداً.

  • الحل: قام المؤلفون بضبط معلمة التنظيم $\tau$ في KLRR بدقة للتحكم صراحة في معيار RKHS لمقدر المكافأة. هذا يحافظ على صغر عدد التغطية للفئة الدالية المستحثة، مما يتيح حدود ثقة ذات معنى.

• الاستكشاف على مستوى المسار مع ضوضاء غير سلسة: تتطلب مكافآت الاستكشاف القياسية (الإهليلجية) معرفة المسار الكامل، وهو أمر غير متاح وقت اتخاذ القرار. تم استخدام الاستكشاف العشوائي عبر أخذ عينات من GP، ولكن مسارات العينات من نواة ماتيرن لا تنتمي عموماً إلى RKHS المقابلة (فهي أقل سلاسة). وهذا يجعل حدود التغطية القياسية غير قابلة للتطبيق.

  • الحل: اشتق المؤلفون حدود تغطية غاوسية جديدة عالية الاحتمالية لمسارات عينات GP اللاحقة. لقد استفادوا من نتائج van der Vaart و van Zanten [2008] لإظهار أنه بينما تقع مسارات GP خارج كرة RKHS، فإنها تقع ضمن جوار $\epsilon$ لكرة RKHS موسعة بشكل مناسب باحتمالية عالية. وهذا يسمح باشتقاق حدود التغطية اللازمة لتحليل الندم.

• الموازنة بين التنظيم ومعلمات التغطية: ضبط معلمات التنظيم ($\tau$ للمكافأة، $\lambda$ للانتقال) والـ $\epsilon$ الخاصة بالتغطية ليس بالأمر السهل. إن $\epsilon$ الصغير يقلل خطأ سوء التوصيف ولكنه يضخم عدد التغطية؛ بينما $\epsilon$ الكبير يفعل العكس.

  • الحل: يقوم المؤلفون بتحسين $\tau$ و $\lambda$ و $\epsilon$ بشكل مشترك كدوال لعدد الحلقات $K$ ومعلمة سلاسة النواة $\beta_p$. تضمن عملية الموازنة هذه بقاء عرض الثقة ضيقاً بما يكفي لتحقيق ندم دون خطي مع التحكم في تعقيد الدالة.

النتائج وحدود الندم
يثبت البحث أن PROSTO تحقق ندماً تراكمياً دون خطي لجميع النوى في عائلة ماتيرن. وتحديداً، ينمو الندم $R(K)$ كـ:
$$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$$
حيث $\beta_p > 1$ هو معلمة اضمحلال القيم الذاتية للنواة، و $H$ هو الأفق، و $\kappa_Z$ هو أقصى تدرد لربط العكسي. الأس الخاص بـ $K$ أقل من 1، مما يعني التقارب نحو السياسة المثلى مع اقتراب $K \to \infty$.

علاوة على ذلك، فإن الخوارزمية فعالة حاسوبياً، مع وقت تشغيل متعدد الحدود في عدد الحلقات $K$. وهذا يميزها عن الأعمال السابقة لنماذج Kernel MDP ذات المكافآت القياسية (مثل Maran et al. [2024b]) والتي، رغم تحقيقها لندم دون خطي، تعتمد على تقسيم النطاق أو أدوات التحسين التي لا تُعرف بأنها قابلة للتطبيق حاسوبياً في وقت متعدد الحدود للإعدادات العامة للنواة.

الأهمية والادعاءات
يزعم المؤلفون أن هذا العمل يوفر أول خوارزمية للتعلم المعزز القائم على التفضيل في نماذج Kernel MDP تحقق ندمًا دون خطي مثبت لجميع عائلات نواة ماتيرن مع كونها فعالة حاسوبياً.

• الجدة النظرية: يجسّر هذا العمل الفجوة بين التعلم المعزز القائم على التفضيل (الذي يتعامل عادةً مع الإعدادات الجدولية أو الخطية) وتقريب الدوال القائم على النواة (الذي يتعامل مع الإعدادات غير الخطية). كما يقدم تقنيات جديدة للتعامل مع نقص السلاسة في ضوضاء استكشاف GP ضمن سياق تكرار القيمة.
• الكفاءة الحسابية: بخلاف خوارزميات عدم الندم السابقة للنماذج السلسة التي قد تتطلب تحسيناً مستعصياً، تقدم PROTO تطبيقاً في وقت متعدد الحدود.
• القيود: يقر المؤلفون بأن حد الندم المستمد قد لا يكون أمثل من حيث الرتبة (order-optimal). ويشيرون إلى أن نهج تقسيم النطاق، الذي يقدم حالياً حدوداً مثالية من حيث الرتبة في بعض إعدادات النواة، لا يتوافق مع التغذية الراجعة على مستوى المسار بسبب عشوائية الانتقالات التي تمنع تقدير مؤثر بيلمان محلي.

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