ملخص تقني: التعلم متى تتوقف: التعلم بالتقليد الانتقائي تحت تحول ديناميكي تعسفي

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

تتناول الورقة البحثية تحدي التعلم بالتقليد (Imitation Learning - IL) في الإعدادات التي تختلف فيها ديناميكيات الانتقال في بيئة الاختبار بشكل تعسفي عن بيئة التدريب. في التعلم بالتقليد غير المتصل (offline IL) الكلاسيكي، يتعلم المتعلم من عروض الخبراء في بيئة مصدر $M$ ثم يتم نشره في بيئة هدف $N$. إذا كانت مجموعات دعم الحالات (state supports) في $M$ و $N$ منفصلة أو مزاحة بشكل كبير، فقد يؤدي السياسة القياسية إلى أداء سيء للغاية لأنها لا تستطيع إدراك متى لم تعد بيانات تدريبها توفر توجيهاً موثوقاً.

يقترح المؤلفون إطار عمل لـ التعلم بالتقليد الانتقائي (Selective Imitation Learning)، حيث يُمنح المتعلم خيار الامتناع (إيقاف التنفيذ) في منتصف المسار (trajectory) عندما يكتشف أن الحالة الحالية تقع خارج نطاق الدعم الموثوق لبيانات التدريب الخاصة به. الهدف هو تعلم سياسة انتقائية $(\pi, \tau)$، تتكون من سياسة أساسية $\pi$ ووقت توقف $\tau$، تحقق هدفين متنافسين:

1. الاكتمال (Completeness): يجب أن تمتنع السياسة نادراً في بيئة التدريب $M$ (أي $\alpha_M(\pi, \tau) \le \epsilon$).
2. الموثوقية (Soundness): يجب أن تحقق السياسة ندماً منخفضاً في بيئة الاختبار $N$ قبل توقفها (أي $Regret_N(\pi, \tau) \le \epsilon$).

يفترض هذا الإعداد الوصول إلى:

• مسارات تدريب موسومة: أزواج (الحالة، الإجراء) $(s, a)$ من الخبير $\pi^\star$ في البيئة $M$.
• مسارات اختبار غير موسومة: مسارات حالة فقط من الخبير $\pi^\star$ في البيئة $N$. هذا التباين يحاكي السيناريوهات الواقعية حيث تكون بيانات الأفعال مكلفة أو مملوكة لجهة معينة (مثل لقطات كاميرا لوحة القيادة للسيارات ذاتية القيادة دون أوامر التوجيه).

2. المنهجية: SeqRejectron

يعمم الخوارزم الأساسي، SeqRejectron، خوارزمية Rejectron من مجال التصنيف الانتقائي (Goldwasser et al., 2020) إلى اتخاذ القرار المتسلسل. الفكرة الجوهرية هي أنه بدلاً من اتخاذ قرارات مستقلة عند كل خطوة زمنية (مما يؤدي إلى تعقيد عينة يعتمد على الأفق $H$)، يقوم الخوارزم بتوثيق بادئات المسارات (trajectory prefixes) الكاملة باستخدام مجموعة متفرقة من سياسات التحقق (validator policies).

الآلية الجوهرية

1. السياسة الأساسية: يختار المتعلم سياسة أساسية $\pi_0$ متوافقة مع بيانات التدريب (على سبيل المثال، تقدير الاحتمال الأقصى MLE).
2. مجموعات التحقق: يبني الخوارزم مجموعة صغيرة من سياسات "التحقق" $\Phi$ المستمدة من فضاء النسخة (version space) (السياسات المتوافقة مع بيانات التدريب).
3. قاعدة التوقف: ينفذ المتعلم $\pi_0$ ويستمر طالما أن كل سياسة تحقق في $\Phi$ تتفق مع $\pi_0$. أول نقطة اختلاف تؤدي إلى التوقف (الامتناع).
4. توزيع التحقق المتفرق: المساهمة النظرية الحاسمة هي الإثبات بأن مجموعة تحقق متفرقة (حجمها مستقل عن الأفق $H$) كافية لضمان السلامة. يتم تحقيق ذلك عبر حجة "مينيمكس" (minimax) على لعبة صفرية بين "المتحدي" (الذي يختار سياسة منافسة) و"المتحقق" (الذي يختار مجموعة من المتحققين).

المتغيرات لمختلف الإعدادات

تكيف الورقة هذا الإطار لثلاثة إعدادات تزداد تعميماً:

• السياسات الحتمية (Deterministic Policies):

  • الآلية: يستخدم اختبار اختلاف ثنائي. وقت التوقف $\tau$ هو الخطوة الأولى التي تختلف فيها أي سياسة تحقق $\pi \in \Phi$ مع $\pi_0$.
  • التنفيذ: يتم بناء توزيع المتحقق باستخدام ديناميكيات عدم الندم (تحديداً اختزال فعال للأوراكل إلى التعلم متعدد الأمثلة الواقعي الموزون).
  • النتيجة: يحقق تعقيد عينة مستقلاً عن الأفق $\tilde{O}(\sqrt{\log|\Pi|/n})$ تحت التكاليف المتفرقة.

• السياسات العشوائية (Stochastic Policies):

  • التحديد: الاختلاف الثنائي يعتبر خشناً جداً؛ فقد تختلف التوزيعات "بنعومة" عند كل خطوة دون وجود تباين صارخ واحد.
  • الآلية: يستبدل الاختبار الثنائي بوقت توقف يعتمد على مسافة هيلينجر التراكمية (cumulative Hellinger distance). يتوقف المتعلم عندما يتجاوز تراكم مسافة هيلينجر المربعة بين $\pi_0$ وأي سياسة تحقق العتبة $\theta$.
  • النتيجة: يوفر حدوداً لعينة منتهية لمسافة هيلينجر للمسارات المتوقفة. تثبت الورقة وجود حد أدنى $\Omega(1/\epsilon^3)$ لتعقيد العينة الموسومة في إعداد الخطوة الواحدة العشوائي، وهو ما يطابق الجزء المدفوع بالتكلفة من الحد الأعلى.

• فئات السياسات غير الدقيقة (Misspecified Policy Classes):

  • التحديد: قد لا يقع الخبير $\pi^\star$ ضمن فئة سياسة المتعلم $\Pi$.
  • الآلية: يستبدل قيد فضاء النسخة الصارم بـ لعبة منظمة متماثلة (symmetrically regularized game). يُسمح للمتحققين بالاختلاف مع السياسة الأساسية في بيانات المصدر، ولكن يتم معاقبة هذا الاختلاف.
  • النتيجة: تتدهور الضمانات بشكل تدريجي مع مقدار عدم الدقة (المقاس بخطأ أفضل خطأ في الفئة $\Delta$).

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

الضمانات النظرية

• التعقيد المستقل عن الأفق: بالنسبة للسياسات الحتمية، تعقيد العينة مستقل عن الأفق $H$ (باستثناء مقياس التكلفة الإجمالية $C_{max}$)، حيث يتدرج كـ $\tilde{O}(\sqrt{\log|\Pi|/n})$. هذا يحسن عن عمليات الاختزال الخطوة بخطوة الساذجة التي تعاني من عقوبة $O(H^2)$.
• التحقق المتفرق: تثبت الورقة وجود توزيع متحقق مدعوم على مجموعات بحجم $O(1/\epsilon)$، وهو مستقل عن فضاء الحالة، وفضاء الفعل، أو الأفق.
• الحدود الدنيا: يثبت المؤلفون وجود حد أدنى $\Omega(1/\epsilon^3)$ لتعقيد العينة الموسومة في إعداد الخطوة الواحدة العشوائي، مما يوضح أن الاعتماد التكعيبي على $1/\epsilon$ لا يمكن تجنبه في الأنظمة المدفوعة بالتكلفة.
• المتانة تجاه عدم الدقة: يوسع الإطار إلى الإعدادات "اللا-نماذجية" (agnostic) حيث لا ينتمي الخبير إلى الفئة، مع حدود ندم تتدرج مع الجذر التربيعي لخطأ عدم الدقة.

التقييم التجريبي

قيم المؤلفون SeqRejectron في بيئة LunarLander-v3.

• الإعداد: يتم التدريب في بيئة بلا رياح؛ ويتم الاختبار في بيئة ذات رياح مع دفعات ابتدائية مختلفة.
• النتائج: نجح الخوارزم في اكتشاف تغيرات الديناميكيات الخارجة عن التوزيع (out-of-distribution). ومن خلال ضبط عتبة السلامة $\theta$، أظهر المؤلفون مقايضة حيث يمتنع النموذج بأقل قدر ممكن في البيانات داخل التوزيع (بيانات التدريب) بينما يتوقف بموثوقية عند البيانات الخارجة عن التوزيع (بيانات الاختبار)، مما يمنع الفشل الكارثي. كما وُجد أن عدد المتحققين كان متيناً، حيث استقر الأداء بسرعة.

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

تدعي الورقة أنها أرست الامتناع (abstention) كاستجلة مبدئية ومؤسسة نظرياً لتغيرات الديناميكيات غير المتوقعة في التعلم بالتقليد.

• ما وراء القواعد التجريبية: على عكس التعلم المعزز القوي أو أساليب تنويع النطاق التي تتطلب افتراضات حول طبيعة التحول أو الوصول عبر الإنترنت إلى توزيع الاختبار، يوفر SeqRejectron ضمانات PAC توزيعية (distribution-free PAC guarantees) باستخدام البيانات غير المتصلة فقط.
• المناظر المتسلسل لـ PQ Learning: يضع العمل نفسه كمناظر متسلسل لإطار عمل PQ learning (Goldwasser et al., 2020)، مما يوسع القدرة على الامتناع من التنبؤات الفردية إلى بادئات المسارات الكاملة.
• آلية السلامة: من خلال فصل قرار "ماذا نفعل" عن "متى نتوقف"، يوفر الإطار آلية سلامة تمنع المتعلم من قيادة النظام إلى حالات لا يمكن التعافي منها عندما تكون بيانات تدريبه غير معلوماتية.

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