تعلّم القيمة Q

التعلّم بلا خريطة

حلّ الدرس 14.2 عملية قرار ماركوف بتكرار القيمة وتكرار السياسة. وكلتا الطريقتين تحتاج إلى شيء لا تملكه في الغالب: احتمالات الانتقال. فلكي تحسب القيمة المتوقعة لفعلٍ ما، عليك أن تجمع على كل حالة قد تنقلك إليها البيئة، مرجَّحةً باحتمال كل واحدة منها. جدول الاحتمالات ذاك هو النموذج، وخارج ألعاب الطاولة وأمثلة الكتب لا أحد يسلّمك إياه.

الروبوت لا يعرف احتمال انزلاق عجلته. ونظام التوصية لا يعرف احتمال أن ينقر المستخدم. وكتابة تلك الأرقام أصعب في كثير من الأحيان من المسألة الأصلية نفسها. فالسؤال العملي هو: هل يستطيع عاملٌ أن يتعلم التصرّف الجيد بمجرد أن يتصرّف ويلاحظ ما يحدث، دون أن يقدّر احتمال انتقال واحدًا؟

الجواب نعم، وعائلة الطرق التي تفعل ذلك تُسمى الطرق الخالية من النموذج (model-free). فبدلًا من التفكير في ما قد يحدث، يستخدم الوكيل ما حدث فعلًا. وكتاب ساتون وبارتو Reinforcement Learning: An Introduction (الطبعة الثانية، 2018) هو المرجع المعياري لكل ما في هذا الدرس، وهو يرسم هذا الخط بالضبط: البرمجة الديناميكية تحتاج نموذجًا، وتعلّم الفرق الزمني لا يحتاجه.

فكرة الفرق الزمني

هناك استراتيجية بديهية خالية من النموذج: العب حلقة كاملة، اجمع المكافأة التي حصلت عليها فعلًا، واستخدم هذا المجموع كقيمة للحالات التي زرتها. هذا هو نهج مونت كارلو، وهو يعمل. لكن له شرطًا قاسيًا — يجب أن تنتهي الحلقة قبل أن تتعلم أي شيء. مباراة شطرنج، أو مسار توصيل، أو جلسة عميل: تنتظر النهاية، ثم تُحدّث.

تعلّم الفرق الزمني (temporal-difference، اختصارًا TD) يرفض الانتظار. فبعد خطوة واحدة صار لديه تقدير يمكنه تحسينه. انتقل من الحالة S_t إلى الحالة S_t+1 وجمع المكافأة R_t+1. كان رأيه القديم «القيمة هنا هي هذه». ورأيه الجديد، الأفضل بخطوة واحدة، هو «القيمة هنا هي المكافأة التي قبضتها للتو، زائد القيمة المخصومة للمكان الذي وصلت إليه». والفجوة بين الرأيين هي إشارة تعلّم.

يُسمى هذا الاستنهاض الذاتي (bootstrapping): يستخدم التحديث تقدير الوكيل الحالي لقيمة الحالة التالية بدلًا من القيمة الحقيقية التي لا يعرفها. يبدو الأمر دائريًا، وهو كذلك — لكنه يتقارب، لأن الحدّ الوحيد الذي ليس تقديرًا، وهو المكافأة المرصودة، يواصل بثّ معلومة حقيقية في الجدول.

قاعدة تحديث Q-Learning

يأخذ Q-learning خطأ الفرق الزمني ويستخدمه لإزاحة جدول من قيم الأفعال. قدّم كريس واتكينز الخوارزمية في رسالة الدكتوراه الخاصة به عام 1989، وأثبت واتكينز ودايان (1992) أنها تتقارب إلى دالة قيمة الفعل المثلى، بشروط مناسبة على حجم الخطوة وبشرط أن يستمر زيارة كل زوج حالة-فعل.

اقرأها كتصحيح لا كحساب. لدى الوكيل رأي؛ والعالَم يعطيه دليلًا؛ فيُزيح رأيه جزئيًا نحو الدليل. عند α = 1 كان سيمحو القيمة القديمة كليًا ويصبح رهينة عيّنة واحدة مشوّشة؛ وعند α = 0 لن يتعلم أبدًا. وبينهما يحسب متوسطًا على الخبرة.

محلول باليد: ممر من أربع خلايا

القاعدة قصيرة إلى حدّ أنك تستطيع تشغيلها بالقلم. وهذا أصغر عالَم شبكي يُظهر السلوك المثير للاهتمام — ممر من أربع خلايا:

التحديث 1 — الوكيل في C ويتحرك يمينًا فيدخل G. يقبض R = +10 ويهبط في حالة نهائية، فحدّ الاستنهاض صفر.

التحديث 2 — حلقة جديدة؛ الوكيل في B ويتحرك يمينًا فيصل إلى C. المكافأة 0. لكن C لم تعد بلا قيمة: الجدول يقول الآن Q(C, right) = 5.0، وقاعدة التحديث تأخذ الأعظم على الأفعال المتاحة من C، وهو max(Q(C, left) = 0، Q(C, right) = 5.0) = 5.0.

التحديث 3 — الوكيل في C مرة أخرى ويتحرك يمينًا إلى G. الانتقال نفسه كما في التحديث 1، لكن الجدول تغيّر، فتتغير الحسابات معه.

شغّل خطوة أخرى لتظهر النمط. إذا تحرك الوكيل بعد ذلك يمينًا من A إلى B، فالمكافأة 0 وmax_a Q(B, a) = 2.25، إذن Q(A, right) ← 0 + 0.5 × (0 + 0.9 × 2.25 − 0) = 0.5 × 2.025 = 1.0125.

ثلاثة أمور صارت ظاهرة الآن لا ينقلها أي قدر من الصياغة الرياضية بهذا الوضوح. أولًا، القيمة تسيل إلى الخلف من المكافأة — خلية واحدة لكل حلقة، C قبل B قبل A. ثانيًا، لم يحتج الوكيل قطّ إلى معرفة أين سيأخذه فعل يمين؛ عرف ذلك بأن ذهب. ثالثًا، القيم تتقارب إلى الجواب الصحيح. القيم المثلى الحقيقية هنا هي Q*(C, يمين) = 10، وQ*(B, يمين) = 0.9 × 10 = 9، وQ*(A, يمين) = 0.9 × 9 = 8.1 — كل خلية تساوي عامل خصم واحد أقل من التي تليها، لأن المكافأة أبعد بخطوة.

إبسيلون-الجشعة، وتخفيضها تدريجيًا

افترض المثال المحلول بهدوء أن الوكيل استمر في اختيار يمين. ولماذا يفعل ذلك؟ في البداية كل خانة 0 وكل فعل يبدو مماثلًا للآخر. وبعد أن تصبح Q(C, right) = 5.0، فالوكيل الذي يأخذ دائمًا أفضل فعل حالي لن يجرّب يسار مرة أخرى أبدًا — ولن يكتشف طريقًا أفضل، لأنه لا ينظر.

العلاج المعياري هو قاعدة إبسيلون-الجشعة (epsilon-greedy) التي عرّفها الدرس 14.1: باحتمال 1 − ε خُذ الفعل ذا أعلى قيمة Q، وباحتمال ε خُذ فعلًا منتظم العشوائية. إنه علاج خشن وهو يعمل. ووعد الدرس 14.1 كذلك بأن تعلّم Q يستبدل متوسط 1/n في مسألة الأذرع بخطوة ثابتة α — وهي بعينها α في التحديث أعلاه. ونتيجة تقارب واتكينز ودايان تحتاج أن يُزار كل زوج حالة-فعل عددًا غير منته من المرات، وأبسط ضمان لذلك هو ε موجبة ثابتة.

لكنك لا تريد ε نفسها إلى الأبد. ففي البداية الجدول بلا معنى والاستكشاف شبه مجاني؛ ولاحقًا يصبح الجدول جيدًا وتصير الأفعال العشوائية كلفة خالصة. لذا تُخفَّض ε تدريجيًا — تُضرَب عادةً في ثابت أقل قليلًا من 1 بعد كل حلقة، حتى أرضية صغيرة. فالبداية عند ε = 1.0 والضرب في 0.995 لكل حلقة تعطي ε ≈ 0.08 بعد 500 حلقة؛ وأرضية عند ε = 0.05 تُبقي بعدها خيطًا من الاستكشاف حيًا بدل تجميد السياسة.

داخل السياسة وخارجها: SARSA بجانب Q-Learning

انظر مرة أخرى إلى ما بين القوسين في تحديث Q-learning. إنه يحتوي على max_a Q(S_t+1, a) — قيمة أفضل فعل من الحالة التالية. لكن الوكيل، بحكم كونه إبسيلون-جشعًا، لن يأخذ ذلك الفعل بالضرورة. فـQ-learning إذن يتعلم قيمة سياسة لا يتبعها. وهذا ما يعنيه خارج السياسة (off-policy).

وصف رَمِري ونيرانجان (1994) البديل داخل السياسة، الذي سُمّي لاحقًا SARSA على الخماسية التي يستخدمها — حالة، فعل، مكافأة، حالة، فعل. وهو التحديث نفسه مع استبدال واحد: بدلًا من الأعظم، يستخدم قيمة الفعل الذي أخذه الوكيل فعلًا بعد ذلك.

الممر يجعل الفرق ملموسًا. عُد إلى التحديث الثاني — الوكيل يتحرك يمينًا من B إلى C — وافترض أن اختياره الإبسيلون-الجشع من C صادف أن يكون الاستكشافي، أي يسار. يستخدم Q-learning القيمة max(0، 5.0) = 5.0 ويتعلّم القيمة Q(B, right) = 2.25، تمامًا كما حُسب أعلاه. أما SARSA فيستخدم Q(C, left) = 0 بدلًا منها، فيكون خطؤه الزمني 0 + 0.9 × 0 − 0 = 0 وتبقى Q(B, right) عند 0. الانتقال نفسه، والمكافأة نفسها، ودرسان مختلفان مستخلصان منهما.

وليس أحدهما أفضل ببساطة. فلأن SARSA يحاسب على الاستكشاف الذي يجري فعلًا، فهو يتعلم سياسات أكثر أمانًا عندما تكون أخطاء الاستكشاف مكلفة — ومثال السير على الجُرف عند ساتون وبارتو هو البرهان المتعارف عليه، حيث يأخذ SARSA الطريق الأطول بعيدًا عن الحافة ويسير Q-learning على المسار الأمثل بمحاذاتها فيسقط أحيانًا. أما Q-learning فيتعلم السياسة المثلى مباشرة، وهو ما تريده إذا كان الاستكشاف رخيصًا أو يجري في محاكاة. وللتعلّم خارج السياسة ميزة عملية حاسمة أيضًا: لأنه لا يشترط أن تأتي البيانات من السياسة الحالية، فبإمكانه أن يتعلم من خبرة ماضية مخزّنة. وهذه الخاصية هي ما يجعل القسم التالي ممكنًا.

لماذا ينفد الجدول

كل ما سبق يفترض أن Q جدول بصفٍّ لكل حالة وعمودٍ لكل فعل. الممر يحتاج ثماني خانات. وهذا النهج ينتهي فجأة بمجرد أن تكبر الحالات.

تأمّل تعلّم لعب لعبة أتاري من الشاشة. كل إطار شبكة من البكسلات لكل منها قيم كثيرة ممكنة، فعدد الشاشات المتمايزة أكبر بشكل فلكي من عدد الذرات في الكون المرصود — والجدول يحتاج صفًا لكل واحدة منها. والمشكلة ليست التخزين فقط. المشكلة أن الجدول ليس لديه أي مفهوم للتشابه: شاشتان تختلفان ببكسل واحد هما صفّان منفصلان لا علاقة بينهما، والخبرة المكتسبة في أحدهما لا تُعلّم الوكيل شيئًا عن الآخر. وحتى بذاكرة لا نهائية، فالوكيل الذي عليه زيارة كل حالة على حدة لن ينتهي أبدًا.

الحل هو التوقف عن تخزين Q والبدء في تقريبها. استبدل الجدول بدالة ذات معاملات — شبكة عصبية تأخذ الحالة مدخلًا وتنتج قيمة Q مقدّرة لكل فعل — ودرّب أوزانها بدلًا من خانات الجدول. الآن تنتج الحالات المتشابهة مخارج متشابهة بحكم البناء، فيتعمّم التعلّم. هذه هي الشبكة العصبية العميقة للقيمة Q (Deep Q-Network، أو DQN): الجدول هو ما استُبدل، لا قاعدة التحديث.

DQN ومُثبِّتاها

تركيب شبكة عصبية على تحديث Q-learning بسذاجة لا يعمل؛ كان عدم استقراره معروفًا قبل زمن طويل من إنجاحه. وقد أنجحه منيه وآخرون في ورقتهم «Human-level control through deep reinforcement learning» (Nature، 2015) على ألعاب أتاري 2600 متعلَّمةً من البكسلات مباشرة — معمارية واحدة ومجموعة واحدة من الوسائط الفائقة عبر عشرات الألعاب، بمستوى مقارب لمختبِر ألعاب بشري محترف في كثير منها. وقد قام بالتثبيت آليتان، وكل واحدة تعالج مشكلة محددة قابلة للتسمية.

إعادة تشغيل الخبرة (experience replay) تعالج ترابط البيانات. التعلّم المُشرَف يفترض أن أمثلة التدريب مستقلة تقريبًا؛ والإطارات المتتالية في لعبة ليست كذلك أبدًا، والتدريب عليها بالترتيب يعني أن كل خطوة تدرّج تُحسب على حزمة من عيّنات شبه متطابقة ومترابطة بشدة. لذا يخزّن DQN الانتقالات — حالة، فعل، مكافأة، حالة تالية — في مخزن كبير ويتدرب على حزم صغيرة مسحوبة منه عشوائيًا. هذا يكسر الترابط، ويسمح بإعادة استخدام كل انتقال مرات عديدة بدلًا من استهلاكه مرة واحدة. ولاحظ أن هذا مشروع فقط لأن Q-learning خارج السياسة: فالمخزن يحتوي أفعالًا اختارتها سياسات أقدم وأسوأ، وطريقة داخل السياسة لا يمكنها التعلّم منها.

الشبكة الهدف (target network) تعالج هدفًا متحركًا. في التحديث، الشبكة نفسها تزوّد التنبؤ Q(S_t, A_t) والهدف الذي يُلائم عليه، والذي يحتوي max_a Q(S_t+1, a). فكل خطوة تدرّج تغيّر الهدف كما تغيّر التنبؤ — الوكيل يطارد غاية تتحرك كلما تحرك، والنتيجة تذبذب أو تباعد. يحتفظ DQN بنسخة ثانية مجمّدة من الشبكة بمعاملات θ⁻، ويستخدم تلك النسخة لحساب الأهداف، ولا يُحدّثها من الشبكة الحيّة إلا كل C خطوة.

ويجدر التوضيح بشأن ما تغيّر وما لم يتغيّر. قاعدة التعلّم لا تزال تحديث Q-learning الذي كتبه واتكينز عام 1989. وما أسهم به منيه وآخرون هو الآلات التي تتيح لمقرّب دوالٍّ أن ينجو منه — أما ضمان التقارب عند واتكينز ودايان (1992)، الذي أُثبت للحالة الجدولية، فلا ينتقل إلى هنا. التعلّم المعزَّز العميق يعمل عمليًا، ويعمل دون شبكة الأمان النظرية التي كان الجدول يتمتع بها.