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

1. بيان المشكلة

تتناول الورقة البحثية مسألة التقييم خارج السياسة (Off-Policy Evaluation - OPE) في عمليات ماركوف لاتخاذ القرار (MDPs) ذات الأفق المحدود. الهدف هو تقدير العائد المتوقع $J(\pi)$ لسياسة مستهدفة $\pi$ باستخدام مجموعة بيانات تم جمعها من سياسة سلوكية $\pi_D$. يتضمن الإعداد التقريب الوظيفي العام (General Function Approximation - GFA)، حيث تُستخدم فئة دالية $\mathcal{F}$ لنمذجة دالة Q الخاصة بالسياسة المستهدفة، $Q^\pi$.

حدد المؤلفون فجوتين نظريتين رئيسيتين في أدبيات الـ OPE الحالية:

1. الاعتماد على الأبعاد (Dimension Dependence): عادةً ما تؤدي التحليلات القياسية لـ GFA (مثل Fitted-Q Evaluation، FQE) إلى حدود خطأ تعتمد على التعقيد الإحصائي للفئة الدالية (مثل $\log |\mathcal{F}|$ أو أعداد التغطية). هذا الاعتماد غالبًا ما يكون فضفاضًا، لا سيما في إعدادات السياسة داخل السياسة (on-policy) حيث تكون تقديرات مونت كارلو خالية من الاعتماد على الأبعاد.
2. عدم الاتساق مع التحليلات الخطية/الجدولية: توجد ضمانات منقحة وخالية من الأبعاد للنماذج الخطية والجدولية (غالبًا تحت شرط التحقق/الواقعية فقط)، لكن هذه النتائج لا تمتد بشكل طبيعي إلى الفئات الدالية العامة. علاوة على ذلك، تعتمد التحليلات الخطية غالبًا على شروط أضعف (التحقق/الواقعية) مقارنة بافتراضات اكتمال بيل مان (Bellman-completeness) المطلوبة لتحليلات GFA العامة.

2. المنهجية: Q-MMR

يقترح المؤلفون Q-MMR (إعادة الوزن بمطابقة العزوم القائمة على دالة Q)، وهو إطار خوارزمي مبتكر يتعلم مجموعة من الأوزان القياسية، وزن لكل نقطة بيانات، بشكل استقرائي من الأعلى إلى الأسفل.

نظرة عامة على الخوارزمية

بفرض وجود $n$ من المسارات المستقلة والمتماثلة توزيعيًا (i.i.d.) وفئة دالية $\mathcal{F} = \{\mathcal{F}_h\}_{h=1}^H$:

1. التهيئة: ضبط الأوزان $w^{(i)}_0 \equiv 1$ لجميع نقاط البيانات $i$ (بما أن زوج الحالة-الفعل الأولي ثابت).
2. إعادة الوزن الاستقرائية: لكل خطوة زمنية $h = 1$ إلى $H$، تتعلم الخوارزمية متجه أوزان $w^{[n]}_h = \{w^{(i)}_h\}_{i=1}^n$ عن طريق حل مسألة تحسين (minimax):
   $$\hat{w}^{[n]}_h = \arg\min_{w^{[n]}_h} \sup_{f \in \mathcal{F}_h} \left| \frac{1}{n} \sum_{i=1}^n w^{(i)}_h f(s^{(i)}_h, a^{(i)}_h) - \frac{1}{n} \sum_{i=1}^n \hat{w}^{(i)}_{h-1} f(s^{(i)}_h, \pi) \right|$$
   يهدف هذا الهدف إلى تقليل التباين (عبر مقياس احتمالي تكاملي - Integral Probability Metric) بين التوزيع المعاد وزنه لأزواج الحالة-الفعل الحالية والتوزيع المعاد وزنه للحالة التالية تحت السياسة المستهدفة.
3. التقدير: التقدير النهائي للعائد هو المجموع المعاد وزنه للمكافآت:
   $$\hat{J}(\pi) = \frac{1}{n} \sum_{i=1}^n \sum_{h=1}^H w^{(i)}_h r^{(i)}_h$$

الخيارات التصميمية الرئيسية

• الأوزان غير البارامترية: على عكس طرق إعادة الوزن بالاستيراد الهامشي (MIS) التي تتعلم دالة بارامترية للأوزان، تتعلم Q-MMR قيمة قياسية متميزة لكل نقطة بيانات.
• مبدأ العزم الثاني الأدنى: نظرًا لأن مُقلل خسارة المطابقة ليس فريدًا بشكل عام، تختار الخوارزمية الحل الذي يمتلك أدنى عزم ثاني تجريبي ($\|w^{[n]}_h\|_{[n]}$) للتحكم في التباين.
• الاستقراء من الأعلى إلى الأسفل: يتم حساب الأوزان مستوى بمستوى من $h=0$ إلى $H$، بالاعتماد على الأوزان من الخطوة السابقة.

3. المساهمات الرئيسية والنتائج النظرية

أ. ضمان العينة المحدودة الخالي من الأبعاد

المساهمة النظرية الرئيسية هي النظرية 1، والتي تقدم حدًا يعتمد على البيانات لعينة محدودة لخطأ OPE. تحت افتراض التحقق/الواقعية (Realizability Assumption) القياسي ($Q^\pi \in \mathcal{F}$)، وباحتمال لا يقل عن $1-\delta$:
$$|\hat{J}(\pi) - J(\pi)| \leq \sum_{h=1}^H \hat{L}_h(\hat{w}^{[n]}_h; \hat{w}^{[n]}_{h-1}) + \sum_{h=0}^H \epsilon^{\text{stat}}_h$$
حيث أن:

• $\hat{L}_h$ هي خسارة المطابقة التجريبية التي حققتها الخوارزمية.
• $\epsilon^{\text{stat}}_h \propto \| \hat{w}^{[n]}_h \|_{[n]} \sqrt{\frac{\log(1/\delta)}{n}}$.

الأهمية:

• خالٍ من الأبعاد: لا يعتمد الحد صراحة على التعقيد الإحصائي لـ $\mathcal{F}$ (أي لا يوجد حد $\log |\mathcal{F}|$) في الرتبة الأولى. ويتحقق ذلك من خلال تجنب حدود الاتحاد (union bounds) فوق الفئة الدالية والاعتماد بدلاً من ذلك على حجج التركيز الخاصة بالأوزان المحققة.
• ما تراه هو ما تحصل عليه (WYSIWYG): الحد قابل للحساب مباشرة من البيانات، حيث يعتمد على خسارة المطابقة المرصودة والعزم الثاني للأوزان المتعلمة.
• افتراضات أضعف: يسري الضمان تحت شرط التحقق/الواقعية وحده، دون الحاجة إلى افتراض اكتمال بيل مان (Bellman-completeness) الأكثر قوة المطلوب عادةً لـ GFA.

ب. الارتباط بالطرق الموجودة

توضح الورقة أن Q-MMR توحد وتستعيد النتائج المعروفة في حالات خاصة:

• الإعدادات الخطية والجدولية: عندما يتم تخصيصها للفئات الدالية الخطية (مع مصفوفة تغطية عينات قابلة للعكس) أو الإعدادات الجدولية، تتطابق Q-MMR مع Linear FQE و Tabular FQE (أو نموذج اليقين المكافئ - model-based certainty-equivalence)، على التوالي.
• استعادة الحدود دقيقة التفاصيل: في هذه الحالات الخاصة، تستعيد تحليل Q-MMR معدلات $O(1/\sqrt{n})$ الخالية من الأبعاد والموجودة في الأدبيات الخطية/الجدولية السابقة (مثل Duan et al., 2020; Yin and Wang, 2021)، مما يسد الفجوة بين التحليلات العامة والخطية.
• مونت كارلو واستيراد الأهمية: في إعدادات داخل السياسة (on-policy)، يؤدي ضبط الأوزان إلى 1 إلى استعادة مقدر مونت كارلو. ومع تعديلات محددة، يمكنها أيضًا استعادة استيراد الأهمية خطوة بخالخطوة (step-wise importance sampling).

ج. رؤى حول التغطية (Coverage)

تقدم الورقة فهمًا نظريًا أعمق لـ التغطية في التعلم المعزز خارج السياسة (offline RL):

• مقدار الوزن كمعيار للتغطية: يعمل المصطلح $\|w^{[n]}_h\|_{[n]}$ (ونظيره في المجتمع $\|w^\star_h\|_{2, d_D}$) كمعيار تجريبي للتغطية.
• طبيعة التغطية: من خلال تحليل إضافي (القسم 4)، يظهر المؤلفون أن "التغطية" المطلوبة ليست مجرد تغطية إشغال الميزات للسياسة المستهدفة $E_{d^\pi}[\phi]$، بل هي تغطية لمتجه محدد بواسطة نظام ديناميكي خطي معين (مشابه لـ $\psi_h$ في التحليلات الخطية).
• اكتمال بيل مان (Bellman Completeness): تحت شرط اكتمال بيل مان، تقوم الأوزان السكانية $w^\star_h$ باستعادة التوزيع المستهدف $d^\pi_h$ تمامًا، ويكون حد الاستقرار الذي يتحكم في انفجار الأوزان محدودًا بـ 1. بدون الاكتمال، يعتمد الاستقرار على معيار مؤثر التحويل المسقط، مما قد يؤدي إلى نمو أسي في الأوزان إذا كان النظام غير مستقر.

4. الأهمية والادعاءات

تدعي الورقة تقديم إطار نظري موحد يحل التوتر بين التقريب الوظيفي العام والتحليلات الخطية/الجدولية في OPE.

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

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

باختصار، تقدم Q-MMR نهجًا رصينًا نظريًا وخاليًا من الأبعاد لـ OPE، يعمم الخصائص المواتية للطرق الخطية على الفئات الدالية العامة مع الاعتماد فقط على شرط التحقق/الواقعية.