Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

إليك ملخص تقني مفصل للورقة البحثية بعنوان "التعلم المعزز القائم على النموذج مع كفاءة الأوراكل المزدوج" (Model-Based Reinance Learning with Double Oracle Efficiency) من إعداد هو، وتشيان، وسيمتشي-ليفي.

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

يواجه التعلم المعزز (RL) في البيئات واسعة النطاق أو المستمرة اختناقات حوسبية شديدة. تتطلب خوارزميات تقليل الندم (regret minimization) التقليدية القائمة على النماذج استدعاءات متكررة لنوعين من "الأوراكل" (Oracles):

1. أوراكل التقدير الإحصائي (Statistical Estimation Oracle): يُستخدم لتقدير نموذج البيئة (ديناميكيات الانتقال والمكافآت) من البيانات.
2. أوراكل تحسين السياسة/التخطيط (Policy Optimization/Planning Oracle): يُستخدم لحساب السياسة المثلى بناءً على النموذج المقدر.

تعاني النهج الحالية من مشكلتين رئيسيتين:

• ارتفاع وتيرة استدعاء الأوراكل: تتطلب معظم الخوارزميات $O(T)$ من الاستدعاءات لهذه الأوراكل، حيث $T$ هو الأفق الزمني، مما يجعلها مكلفة حوسبياً للأفق الزمني الكبير $T$.
• الاعتماد على حجم فضاء الحالة/الأفعال: يتوسع تعقيد التخطيط غالباً مع عدد عناصر فضاء الحالة ($S$) وفضاء الأفعال ($A$). وهذا يجعل الطرق الحالية غير قابلة للتطبيق في البيئات ذات الفضاءات الكبيرة، أو اللانهائية، أو المستمرة (مثل نماذج ماركوف لاتخاذ القرار الخطية - Linear MDPs - ذات الحالات اللانهائية).

بينما حققت أعمال حديثة (مثل Qian et al., 2024) "كفاءة أوراكل التقدير أوفلاين" (عدد قليل من الاستدعاءات لأوراكل التقدير) لنماذج ماركوف لاتخاذ القرار الجدولي (Tabular MDPs)، إلا أن تعقيد أوراكل التخطيط لديها كان لا يزال يتوسع مع $S$ و $A$ (تحديداً $O(HSA \log \log T)$). تعالج هذه الورقة السؤال المفتوح: هل يمكننا تصميم خوارزمية تكون كفؤة في كل من أوراكل التقدير وأوراكل التخطيط، بحيث يكون تعقيدها مستقلاً عن $S$ و $A$، وقابلة للتطبيق على فضاءات الحالة/الأفعال اللانهائية؟

2. المنهجية

يقترح المؤلفون DOERL (التعلم المعزز ذو كفاءة الأوراكل المزدوج)، وهو إطار خوارزمي مبتكر يعتمد على تنظيم الحاجز اللوغاريتمي (log-barrier) والمحدد اللوغاريتمي (log-determinant). يكمن الابتكار الجوهري في كيفية إدارة الخوارزمية للمفاضلة بين الاستكشاف والاستغلال مع تقليل استدعاءات الأوراكل.

المكونات التقنية الرئيسية:

1. التعلم القائم على الحقبات مع التحديثات المبتورة (Epoch-Based Learning with Truncated Updates):

   • يتم تقسيم عملية التفاعل إلى $N$ من الحقبات (epochs). داخل كل حقبة، ينفذ الوكيل سياسة ثابتة لفترة زمنية محددة.
   • من المهم ملاحظة أن أوراكل التقدير "أوفلاين" لا يتم استدعاؤه إلا في نهاية كل حقبة (أو جزء)، حيث يقوم بتجميع البيانات لتحديث النموذج. هذا يقلل عدد استدعاءات التقدير إلى $O(N)$.
   • كما يتم استدعاء أوراكل التخطيط فقط في بداية الأجزاء، مما يقلل بشكل كبير من وتيرة التخطيط.

2. مقاييس الإشغال الموثوقة (Trusted Occupancy Measures):

   • لتجنب استكشاف انتقالات الحالة-الفعل النادرة أو غير الموثوقة، تحدد الخوارزمية "مجموعة انتقال موثوقة" $\mathcal{T}_m^h$.
   • تُعتبر الانتقالات "موثوقة" فقط إذا تجاوز حاصل ضرب مقياس الإشغال المقدر في احتمال الانتقال قيمة العتبة ($1/\zeta_m$).
   • هذا المفهوم، المقتبس من Qian et al. (2024)، تم تعديله ليكون قابلاً للحساب دون الحاجة للمرور عبر كامل فضاء السياسات، وهو أمر بالغ الأهمية للكفاءة.

3. التنظيم من أجل الاستكشاف (Regularization for Exploration):

   • لنماذج ماركوف الجدولية (Tabular MDPs): تستخدم الخوارزمية تنظيم الحاجز اللوغاريتمي. يتضمن هدف تحسين السياسة حداً هو $\sum \log(\text{trusted occupancy} + \beta)$. هذا يشجع الوكيل على زيارة أزواج (الحالة-الفعل) التي تُعد "موثوقة" ولكن ذات احتمالية منخفضة، مما يضمن استكشافاً كافياً دون الحاجة لحصر جميع الحالات.
   • للنماذج الخطية (Linear MDPs - الفضاءات اللانهائية): تقدم الخوارزمية تنظيم المحدد اللوغاريتمي. بدلاً من الجمع عبر حالات منفصلة، تقوم بتعظيم المحدد اللوغاريتمي لمصفوفة التباين المميز (feature covariance matrix) الموزونة بمقياس الإشغال الموثوق: $\log \det(\mathbf{K} + \beta \mathbf{I})$. هذا يعزز استكشاف فضاء السمات (feature space)، مما يضمن جمع بيانات متنوعة لتقدير المعاملات الخطية بدقة.

4. استراتيجية التجميع (Aggregation Strategy):

   • تقوم الخوارزمية بتجميع التقديرات على مستوى الطبقات (kernels الانتقال والمكافآت) من الأوراكل "أوفلاين" في نموذج عالمي واحد للحقبة التالية، بدلاً من تحديث النموذج عند كل خطوة فردية.

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

1. كفاءة الأوراكل المزدوج (Double Oracle Efficiency):

   • تقدم الورقة أول خوارزمية تحقق كفاءة في كل من أوراكل التقدير الإحصائي وأوراكل تحسين السياسة.
   • تعقيد استدعاء الأوراكل: تتطلب الخوارزمية $O(H \log \log T)$ فقط من الاستدعاءات لكلا الأوراكل عندما يكون $T$ معروفاً (و $O(H \log T)$ عندما يكون غير معروف).
   • الاستقلال عن الأبعاد: من الأهمية بمكان أن هذا التعقيد مستقل تماماً عن حجم فضاء الحالة ($S$) وفضاء الأفعال ($A$).

2. التوسع إلى الفضاءات اللانهائية:

   • تم تعميم الإطار ليشمل النماذج الخطية (Linear MDPs) ذات فضاءات الحالة اللانهائية وفضاءات الأفعال التعسفية.
   • هي أول خوارزمية كفؤة في الأوراكل "أوفلاين" تحقق ندمًا (regret) دون خطي في هذا السياق، متجاوزة "لعنة الأبعاد" التي تعاني منها الطرق الجدولية.

3. حدود الندم المثلى (Optimal Regret Bounds):

   • نماذج ماركوف الجدولية: تحقق حد الندم الأمثل $O(\sqrt{T})$.
   • النماذج الخطية: تحقق حداً للندم دون خطي قدره $O(T^{4/5})$ (مع عوامل لوغاريتمية)، وهو أمر ذو مغزى في الإعدادات ذات الأبعاد اللانهائية تحت قيود الأوراكل المعطاة.

4. النتائج

تم وضع الضمانات النظرية لكل من الحالات المنتهية (الجدولية) والخطية (اللانهائية):

• نماذج ماركوف الجدولية:

  • الندم (Regret): $O(\sqrt{T})$ (أمثل).
  • استدعاءات الأوراكل: $O(H \log \log T)$ لكل من التقدير والتخطيط.
  • المقارنة: تحسن بشكل كبير على Qian et al. (2024)، التي كانت تتطلب $O(HSA \log \log T)$ من استدعاءات التخطيط.

• النماذج الخطية (حالة/فعل لانهائية):

  • الندم: $O(T^{4/5} \cdot \text{polylog}(T))$.
  • استدعاءات الأوراكل: $O(H \log \log T)$ لكلا الأوراكل.
  • الأهمية: قبل هذا العمل، لم تكن هناك خوارزمية يمكنها حل نماذج ماركوف ذات الحالة اللانهائية مع مثل هذا التردد المنخفض لاستدعاء الأوراكل مع الحفاظ على ندم دون خطي.

5. الأهمية والأثر

• الربط بين النظرية والتطبيق: من خلال فصل التعقيد الحوسبي عن حجم فضاءات الحالة/الأفعال، يجعل هذا العمل التعلم المعزز القائم على النموذج قابلاً للتطبيق نظرياً في التطبيقات المعقدة والواقعية مثل الروبوتات والأنظمة ذاتية القيادة حيث تكون $S$ و $A$ لانهائية فعلياً.
• الكفاءة في الأنظمة واسعة النطاق: يمثل تقليل استدعاءات الأوراكل من $O(T)$ أو $O(SA)$ إلى $O(\log \log T)$ انخفاضاً هائلاً في العبء الحوسبي، مما يسمح باستخدام المقدرات "أوفلاين" المكلفة (مثل الشبكات العصبية العميقة) في حلقات التعلم المعزز حيث كانت مكلفة جداً سابقاً.
• نموذج جديد للاستكشاف: يوفر دمج تنظيم الحاجز اللوغاريتمي والمحدد اللوغاريتمي مع المقاييس "الموثوقة" آلية نظرية قوية للاستكشاف تتوسع بسلاسة مع الأبعاد، مما يقدم مخططاً لخوارزميات التحكم عالية الأبعاد في المستقبل.

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