Relating Reinforcement Learning to Dynamic Programming-Based Planning

إليك ملخص تقني مفصل لورقة البحث "ربط التعلم التعزيزي بالتخطيط القائم على البرمجة الديناميكية" (Relating Reinforcement Learning to Dynamic Programming-Based Planning) بقلم جورجيف وآخرون.

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

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

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

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

2. المنهجية

استخدم المؤلفون مزيجاً من التحليل الرياضي النظري والتجارب التجريبية المكثفة عبر بيئات حتمية وعشوائية.

أ. التحليل النظري

1. التعلم التعزيزي منزوع العشوائية (Derandomized RL): قدم المؤلفون نسخة "منزوعة العشوائية" من خوارزمية Q-learning للأنظمة الحتمية. ومن خلال ضبط معدل التعلم $\rho = 1$ (بافتراض عدم وجود عدم يقين)، أظهروا أن Q-learning يصبح خطوة من خطوات التكرار غير المتزامن للقيمة (asynchronous value iteration). وقد أثبتوا أنه إذا تمت زيارة كل زوج (حالة-فعل) لعدد لا نهائي من المرات، فإن Q-learning الحتمي هذا يتقارب نحو الحل الأمثل في وقت محدد.
2. تكافؤ التكلفة والمكافأة: أثبتوا أن تقليل دالة التكلفة الخطية يكافئ رياضياً تعظيم دالة المكافأة الخطية (حيث المكافأة = -التكلفة)، بشرما كانت التكلفة/المكافأة خطية في تسلسل الخطوات.
3. مخاطر الخصم (Discounting): تقدم الورقة برهاناً صارماً (الخاصية 3) يوضح أن استخدام عامل خصم $\alpha < 1$ في مشكلة موجهة نحو هدف قد يؤدي إلى تكلفة حقيقية لانهائية. فإذا وُجدت دورة ذات تكلفة مخصومة أقل من المسار المؤدي إلى الهدف، فإن السياسة المثلى المخصومة ستستمر في الدوران في حلقة مفرغة، مما يؤدي إلى الفشل في الوصول إلى الهدف حتى لو كان الوصول إليه ممكناً.
4. التكافؤ في المرات (Episodic Equivalence): حلل المؤلفون العلاقة بين إنهاء الهدف لمرة واحدة (التخطيط) وبين التعلم ذو الأفق اللانهائي المتكرر (التعلم التعزيزي مع إعادة الضبط). واستنتجوا الشروط التي تظل بموجبها السياسة المثلى لمشكلة المرة الواحدة مثالية لمشكلة الأفق اللانهائي مع "مكافأة إعادة الضبط" (تكلفة سالبة عند الوصول للهدف).

ب. الإعداد التجريبي

• البيئات: مجموعة من مشكلات تخطيط عالم الشبكة (Grid-world) (المشكلات 0–16) بأبعاد مختلفة، وكثافة عوائق، واتصال متغير.
• الخوارزميات المقارنة:
  • التخطيط: خوارزمية Dijkstra الخالية من النموذج، والتكرار المتزامن للقيمة (VI)، والتكرار غير المتزامن للقيمة (VI).
  • التعلم التعزيزي (RL): خوارزمية Q-learning بمعاملات متغيرة:
    • $\epsilon$ (معدل الجشع/الاستكشاف).
    • $\rho$ (معدل التعلم).
    • $\gamma$ (عامل القدرة على التنبؤ، حيث يمثل $\gamma=1$ النظام الحتمي).
• المقاييس: وقت التشغيل، عدد الإجراءات المتخذة، التقارب إلى التكلفة المثلى للوصول، وقت اكتشاف الهدف، وطورية المسار.

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

1. Q-Learning منزوع العشوائية: أظهر المؤلفون أن Q-learning ليس خوارزمية عشوائية بطبيعتها، بل هو تعميم لتكرار القيمة (Value Iteration). وفي البيئات الحتمية، يتقارب نحو الحل الأمثل إذا تم ضبط معدل التعلم على 1 مع كفاية الاستكشاف.
2. نقد الخصم (Discounting): إحدى المساهمات الكبرى هي الإثبات الرسمي بأن الخصم هو مجرد استدلال يمكن أن يسبب الفشل في تحقيق الهدف. في مهام الروبوتات الموجهة نحو الأهداف، يمكن للخصم أن يجعل الروبوت يفضل حلقة محلية على الوصول للهدف، مما ينتج عنه تكلفة حقيقية لانهائية. ويدعو المؤلفون إلى استخدام "التكلفة الحقيقية" (TrueCost) (التكاليف الفيزيائية/المالية) وأفعال الإنهاء بدلاً من الخصم.
3. تكافؤ الصيغ: تثبت الورقة أن:
   • تقليل التكلفة وتعظيم المكافأة متكافئان للدوال الخطية.
   • مشكلات الأفق اللانهائي المتكررة يمكن جعلها مكافئة لمشكلات المرة الواحدة عبر ضبط معامل "مكافأة إعادة الضبط"، بشرما استوفيت شروط محددة حول تكاليف الدورات.
4. تحليل حساسية المعاملات: توفر الدراسة خريطة شاملة لكيفية تأثير $\epsilon$ و $\rho$ و $\gamma$ على التقارب والأداء، مما يسلط الضضواء على أن المعاملات الفائقة (Hyperparameters) القياسية في التعلم التعزيزي غالباً ما تتطلب ضبطاً كبيراً لتضاهي كفاءة خوارزميات التخطيط.

4. النتائج

النتائج الحتمية

• السرعة: خوارزميات Dijkstra الخالية من النموذج وتكرار القيمة (VI) أسرع بعدة مراتب من Q-learning. على سبيل المثال، في المشكلة 10، كانت خوارزمية Dijkstra الخالية من النموذج أسرع بـ 134 مرة من Q-learning مع $\epsilon=0$.
• التقارب: Q-learning الجشع تماماً ($\epsilon=0$) يجد الهدف بأسرع وقت ولكنه غالباً ما يفشل في التقارب نحو التكلفة المثلى للوصول لكامل مساحة الحالة لأنه لا يستكشف بما يكفي. أما $\epsilon$ العالي (الاستكشاف العشوائي) فيضمن التقارب ولكنه يزيد وقت التشغيل بشكل كبير.
• عدد الإجراءات: تتطلب خوارزمية Q-learning عدداً أكبر بكثير من الإجراءات (غالباً 20-40 ضعفاً) للتقارب مقارنة بخوارزميات التخطيط التي تستفيد من النموذج (أو التنقل في الرسم البياني الخالي من النموذج).

النتائج العشوائية

• معدل التعلم ($\rho$): في البيئات العشوائية، غالباً ما يكون مطلوباً معدل تعلم $\rho$ منخفض (مثلاً 0.5) لتحقيق الاستقرار مع انخفاض عامل القدرة على التنبؤ $\gamma$. ومع ذلك، فإن هذا يبطئ التقارب.
• فشل التقارب: مع زيادة العشوائية (انخفاض $\gamma$)، تجد خوارزمية Q-learning صعوبة في التقارب نحو التكلفة المثلى العالمية لكافة الحالات، حتى مع عدد هائل من الحلقات (Episodes). في بعض الحالات (مثل $\gamma=0.5$)، لم يتحقق التقارب العالمي إلا باستخدام معدلات تعلم متناقصة واستكشاف عالٍ.
• فجوة الأداء: تتسع الفجوة في الأداء بين الديناميكا (DP) والتعلم التعزيزي (RL) في البيئات العشوائية. طرق الديناميكا (DP) تتقارب بسرعة أكبر بنحو رتبتين من حيث المقدار من التعلم التعزيزي، مما يبرز "ثمن التعلم أثناء العمل".

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

• إعادة صياغة التعلم التعزيزي للروبوتات: تجادل الورقة بأنه للمهام الروبوتية الموجهة نحو الأهداف، يجب أن يبتعد التعلم التعزيزي عن عوامل الخصم التعسفية وتشكيل المكافآت المستوحى بيولوجياً. بدلاً من ذلك، يجب تبني نماذج "التكلفة الحقيقية" (TrueCost) مع "أفعال الإنهاء"، مما يجعل التعلم التعزيزي أكثر توافقاً مع كفاءة خوارزميات التخطيث المثبتة.
• اختيار الخوارزمية: تشير النتائج إلى أنه إذا كان النموذج متاحاً (حتى لو كان نموذجاً مُتعلماً) أو إذا كانت البيئة حتمية، فإن خوارزميات التخطيط الكلاسيكية (Dijkstra, VI) هي الأفضل من حيث السرعة والموثوقية. التعلم التعزيزي ضروري فقط عندما يكون النموذج غير معروف ويجب تعلمه بالتزامن مع التخطيط، ولكن هذا يأتي بتكلفة حوسبية باهظة.
• ضبط المعاملات: توفر الدراسة إرشادات ملموسة لضبط Q-learning. فعلى سبيل المثال، في البيئات الحتمية، غالباً ما يكون $\epsilon=0$ هو الأمثل لإيجاد مسار، بينما يلزم $\epsilon \approx 0.9$ للتقارب الكامل لمساحة الحالة. وفي البيئات العشوائية، يجب تقليل $\rho$ أو إبقاؤه منخفضاً للتعامل مع الضجيج.
• التوحيد النظري: من خلال إثبات التكافؤ الرياضي بين التكلفة والمكافأة وشروط التكافؤ في المرات، توفر الورقة إطاراً نظرياً موحداً يسمح للباحثين بنقل الرؤى بين مجتمعات التخطيط والتعلم التعزيزي.

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