الـ Q-learning (تعلّم القيمة Q) | ML-101

التعلّم من غير خريطة

الدرس 14.2 حل الـ Markov decision process بالـ value iteration والـ policy iteration. والطريقتين محتاجين حاجة غالبًا مش معاك: الـ transition probabilities. فعشان تحسب القيمة المتوقّعة لـ action معيّن، لازم تجمع على كل state الـ environment ممكن توديك لها، موزونة باحتمال كل واحدة. وجدول الاحتمالات ده هو الـ model، وبره ألعاب الطاولة وأمثلة الكتب محدش بيسلّمهولك.

الروبوت مبيعرفش احتمال إن عجلته تتزحلق. والـ recommendation system مبيعرفش احتمال إن المستخدم يدوس. وكتابة الأرقام دي كتير بتبقى أصعب من المسألة الأصلية نفسها. فالسؤال العملي: هل agent يقدر يتعلّم يتصرّف كويس بمجرد إنه يتصرّف ويلاحظ اللي بيحصل، من غير ما يقدّر ولا transition probability واحدة؟

الإجابة أيوه، وعيلة الطرق اللي بتعمل ده اسمها الطرق الـ model-free (الخالية من النموذج) (model-free). فبدل ما يفكّر في اللي ممكن يحصل، الـ agent بيستخدم اللي حصل فعلًا. وكتاب ساتون وبارتو Reinforcement Learning: An Introduction (الطبعة التانية، 2018) هو المرجع المعتاد لكل اللي في الدرس ده، وهو بيرسم الخط ده بالظبط: الـ dynamic programming محتاج model، والـ temporal-difference learning مش محتاجه.

فكرة الـ temporal difference

فيه استراتيجية model-free بديهية: العب episode كاملة، واجمع الـ reward اللي خدتها فعلًا، واستخدم المجموع ده كقيمة للـ states اللي زرتها. ده أسلوب الـ Monte Carlo، وهو بيشتغل. بس ليه شرط قاسي — الـ episode لازم تخلص قبل ما تتعلّم أي حاجة. ماتش شطرنج، أو مسار توصيل، أو جلسة عميل: بتستنّى النهاية، وبعدين تحدّث.

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

الـ TD error (خطأ الفرق الزمني)

\delta_t = R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)

الـ temporal-difference error. أول حدّين هما التقدير الجديد: الـ reward اللي اتقبضت فعلًا زائد القيمة المخصومة لأحسن action متاح من الـ state اللي الـ agent وصل لها فعلًا. والحد الأخير هو التقدير القديم. والفرق بينهم هو الـ agent غلط قد إيه، وهو متاح بعد خطوة واحدة — من غير episode كاملة، ومن غير transition probabilities.

ده اسمه الـ bootstrapping (الاستنهاض الذاتي) (bootstrapping): التحديث بيستخدم تقدير الـ agent الحالي لقيمة الـ state الجاية بدل القيمة الحقيقية اللي مبيعرفهاش. شكله دايري، وهو فعلًا كده — بس بيعمل convergence، لأن الحد الوحيد اللي مش تقدير، وهو الـ reward المرصودة، بيفضل يدخّل معلومة حقيقية في الجدول.

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

الـ Q-learning (تعلّم القيمة Q) بياخد الـ TD error ويستخدمه يزقّ جدول من الـ action values. كريس واتكينز قدّم الـ algorithm في رسالة الدكتوراه بتاعته سنة 1989، وواتكينز ودايان (1992) أثبتوا إنها بتعمل convergence للـ optimal action-value function، بشروط مناسبة على حجم الخطوة وبشرط إن كل زوج state-action يفضل يتزار.

تحديث Q-Learning

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t) \right]

حرّك التقدير الحالي جزء قده α في اتجاه التقدير الأحسن بخطوة واحدة. اللي بين القوسين هو الـ TD error اللي فوق بالظبط. وα هي الـ learning rate، ونفس الرمز اللي الوحدات من 1 لـ 3 بتستخدمه لحجم خطوة الـ gradient descent، وγ هو الـ discount factor من الدرس 14.2. ومفيش حاجة في التعبير ده transition probability.

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

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

القاعدة قصيّرة لدرجة إنك تقدر تشغّلها بالقلم. وده أصغر grid world بيبيّن السلوك المثير — ممر من أربع خلايا:

الإعداد

الـ states: أربع خلايا في صف واحد، A – B – C – G. والخلية G هي الهدف وهي terminal.

الـ actions: شمال ويمين. والحركة يمين من C بتدخل G.

الـ rewards: كل خطوة بتدّي reward 0، ما عدا الخطوة اللي بتدخل G فبتدّي reward +10.

الإعدادات: الـ learning rate α = 0.5، والـ discount factor γ = 0.9، وكل خانة في جدول Q بتبدأ من 0.

الاصطلاح: G terminal، فـ max_a Q(G, a) = 0 بالتعريف. مفيش مستقبل بعد الهدف.

التحديث 1 — الـ agent في C وبيتحرّك يمين فبيدخل G. بيقبض R = +10 وبينزل في state terminal، فحد الـ bootstrapping صفر.

حسابات التحديث 1

الـ TD error: δ = 10 + 0.9 × 0 − 0 = 10

Q(C, right) ← 0 + 0.5 × 10 = 5.0

وكل خانة تانية لسه 0. خطوة خبرة واحدة عملت القيمة الوحيدة اللي مش صفر في الجدول — وخد بالك إنها 5.0 مش 10. نص الدليل، لأن α = 0.5.

التحديث 2 — episode جديدة؛ الـ agent في B وبيتحرّك يمين فبيوصل لـ C. الـ reward 0. بس C مبقتش من غير قيمة: الجدول بيقول دلوقتي Q(C, right) = 5.0، وقاعدة التحديث بتاخد الأكبر على الـ actions المتاحة من C، وهو max(Q(C, left) = 0، Q(C, right) = 5.0) = 5.0.

حسابات التحديث 2

الـ TD error: δ = 0 + 0.9 × 5.0 − 0 = 4.5 − 0 = 4.5

Q(B, right) ← 0 + 0.5 × 4.5 = 2.25

الـ agent مقبضش أي reward في الخطوة دي خالص، ومع كده اتعلّم حاجة. والقيمة اللي اتعلّمها جت كلها من تقديره هو لـ C — وده الـ bootstrapping شغّال.

التحديث 3 — الـ agent في C تاني وبيتحرّك يمين لـ G. نفس الانتقال اللي في التحديث 1، بس الجدول اتغيّر، فالحسابات بتتغيّر معاه.

حسابات التحديث 3

الـ TD error: δ = 10 + 0.9 × 0 − 5.0 = 5.0

Q(C, right) ← 5.0 + 0.5 × 5.0 = 7.5

الخطأ بيصغر: 10، وبعدين 5.0. كل زيارة بتقفل نص الفجوة اللي فاضلة ناحية القيمة الحقيقية 10، فالسلسلة بتمشي 5.0، 7.5، 8.75، 9.375، وهكذا.

شغّل خطوة كمان عشان الـ pattern يبان. لو الـ agent اتحرّك بعد كده يمين من A لـ B، فالـ reward 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.

تلات حاجات بقت باينة دلوقتي مفيش أي قدر من الصياغة الرياضية بيوصّلها بالوضوح ده. أولًا، القيمة بتسيل لورا من الـ reward — خلية واحدة لكل episode، C قبل B قبل A. تانيًا، الـ agent عمره ما احتاج يعرف الـ action يمين هيوديه فين؛ عرف ده لما راح. تالتًا، القيم بتعمل convergence للإجابة الصح. القيم الـ optimal الحقيقية هنا هي Q*(C, يمين) = 10، وQ*(B, يمين) = 0.9 × 10 = 9، وQ*(A, يمين) = 0.9 × 9 = 8.1 — كل خلية أقل بـ discount factor واحد من اللي بعدها، لأن الـ reward أبعد بخطوة.

الـ epsilon-greedy، وتقليلها تدريجيًا

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

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

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

شكلين للفشل

ε بتتقلّل بسرعة زيادة: الـ agent بيلتزم بأول طريق مقبول يقابله بالصدفة وعمره ما بيلاقي الطريق الكويس. وده بيبان كتعلّم ناجح — policy مستقرة، ومنحنى reward مفرود — وده بالظبط اللي بيخلّيه خطير.

ε بتتقلّل ببطء زيادة: الـ agent عارف الإجابة الصح وبيفضل يرمي الزهر برضه، فأداؤه المتقاس بيفضل أقل بكتير من اللي الجدول بتاعه بيسنده أصلًا.

الـ on-policy والـ off-policy: الـ SARSA جنب الـ Q-Learning

بص تاني على اللي بين القوسين في تحديث الـ Q-learning. فيه max_a Q(S_t+1, a) — قيمة أحسن action من الـ state الجاية. بس الـ agent، بحكم إنه epsilon-greedy، مش لازم ياخد الـ action ده. فالـ Q-learning بيتعلّم قيمة policy مش ماشي وراها. وده معنى الـ off-policy (خارج السياسة) (off-policy).

رَمِري ونيرانجان (1994) وصفوا البديل الـ on-policy، اللي اتسمّى بعد كده SARSA على الخماسية اللي بيستخدمها — state، action، reward، state، action. ونفس التحديث مع تبديل واحد: بدل الأكبر، بيستخدم قيمة الـ action اللي الـ agent خده فعلًا بعد كده.

تحديث SARSA

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right]

الفرق الوحيد عن تحديث الـ Q-learning هو الحد اللي في النص: γQ(S_t+1, A_t+1) بدل γmax_aQ(S_t+1, a). فالـ Q-learning بيعمل bootstrapping من أحسن action متاح؛ والـ SARSA بيعمل bootstrapping من الـ action اللي اتاخد فعلًا، بأخطاء الـ exploration وكل حاجة.

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

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

ليه الجدول بيخلص

كل اللي فات بيفترض إن Q جدول فيه صف لكل state وعمود لكل action. الممر محتاج تمن خانات. والأسلوب ده بيخلص فجأة أول ما الـ states تكبر.

خد مثلًا إنك تتعلّم تلعب لعبة أتاري من الشاشة. كل frame عبارة عن grid من الـ pixels وكل pixel ليه قيم كتير ممكنة، فعدد الشاشات المختلفة أكبر بشكل فلكي من عدد الذرّات في الكون المرصود — والجدول محتاج صف لكل واحدة فيهم. والمشكلة مش التخزين بس. المشكلة إن الجدول مالوش أي مفهوم للتشابه: شاشتين بيختلفوا في pixel واحد هما صفّين منفصلين مالهمش علاقة ببعض، والخبرة اللي اتكسبت في واحد مبتعلّمش الـ agent أي حاجة عن التاني. وحتى بـ memory لا نهائية، الـ agent اللي لازم يزور كل state لوحدها عمره ما هيخلّص.

الحل إنك تبطّل تخزّن Q وتبدأ تقرّبها. بدّل الجدول بـ function ليها parameters — neural network بتاخد الـ state كـ input وبتطلّع قيمة Q متقدّرة لكل action — ودرّب الـ weights بتاعتها بدل خانات الجدول. دلوقتي الـ states اللي شبه بعض بتطلّع outputs شبه بعض بحكم البنا، فالتعلّم بيتعمّم. ده الـ Deep Q-Network (الشبكة العصبية العميقة للقيمة Q) (Deep Q-Network، أو DQN): الجدول هو اللي اتبدّل، مش قاعدة التحديث.

الـ DQN والحاجتين اللي ثبّتوه

إنك تركّب neural network على تحديث الـ Q-learning بسذاجة مبيشتغلش؛ عدم استقراره كان معروف من قبل ما ينجح بكتير. ونجّحه منيه وزمايله في ورقتهم «Human-level control through deep reinforcement learning» (Nature، 2015) على ألعاب أتاري 2600 متعلّمة من الـ pixels على طول — architecture واحدة ومجموعة hyperparameters واحدة على عشرات الألعاب، بمستوى قريب من game tester بني آدم محترف في كتير منها. واللي ثبّته آليتين، وكل واحدة بتعالج مشكلة محدّدة ليها اسم.

الـ experience replay (إعادة تشغيل الخبرة) (experience replay) بيعالج ارتباط البيانات. الـ supervised learning بيفترض إن أمثلة التدريب تقريبًا مستقلة؛ والـ frames اللي ورا بعض في لعبة عمرها ما بتبقى كده، والتدريب عليها بالترتيب معناه إن كل خطوة gradient بتتحسب على batch من عينات شبه متطابقة ومرتبطة جامد. فالـ DQN بيخزّن الانتقالات — state، action، reward، state جاية — في buffer كبير وبيتدرّب على mini-batches بتتسحب منه عشوائي. وده بيكسر الارتباط، وبيخلّي كل انتقال يتعاد استخدامه مرات كتير بدل ما يتصرف مرة واحدة. وخد بالك إن ده مقبول بس لأن الـ Q-learning off-policy: الـ buffer فيه actions اختارتها policies أقدم وأوحش، وطريقة on-policy متقدرش تتعلّم منها.

الـ target network (الشبكة الهدف) (target network) بتعالج هدف بيتحرّك. في التحديث، نفس الشبكة بتدّي الـ prediction Q(S_t, A_t) والـ target اللي بيتعمل عليه fit، واللي فيه max_a Q(S_t+1, a). فكل خطوة gradient بتغيّر الـ target زي ما بتغيّر الـ prediction — الـ agent بيجري ورا هدف بيتحرّك كل ما هو يتحرّك، والنتيجة تذبذب أو divergence. فالـ DQN بيحتفظ بنسخة تانية متجمّدة من الشبكة بـ parameters θ⁻، وبيستخدم النسخة دي يحسب الـ targets، ومبيحدّثهاش من الشبكة الحيّة غير كل C خطوة.

هدف DQN

y_t = R_{t+1} + \gamma \max_a Q\!\left(S_{t+1}, a; \theta^{-}\right)

target الـ regression في تحديث الـ DQN. الشبكة اللي بتتدرّب ليها الـ parameters θ؛ والـ target بيتحسب بالنسخة المتجمّدة θ⁻، اللي بتتثبّت C خطوة كل مرة. والـ loss هو الفرق المربّع بين y_t وQ(S_t, A_t; θ)، وθ لوحدها هي اللي بتاخد الـ gradients.

ويستاهل توضّح إيه اللي اتغيّر وإيه اللي متغيّرش. قاعدة التعلّم لسه هي تحديث الـ Q-learning اللي واتكينز كتبه سنة 1989. واللي منيه وزمايله ساهموا بيه هو الأدوات اللي بتخلّي function approximator ينجو منه — أما ضمان الـ convergence عند واتكينز ودايان (1992)، اللي اتثبت للحالة الـ tabular، فمبيتنقلش هنا. الـ deep reinforcement learning بيشتغل عمليًا، وبيشتغل من غير شبكة الأمان النظرية اللي الجدول كان عنده.

أهم النقط

الـ Q-learning model-free: مش محتاج transition probabilities، محتاج بس الانتقالات اللي الـ agent عاشها فعلًا.
الـ temporal-difference learning بيحدّث بعد خطوة واحدة مش في آخر الـ episode، عن طريق الـ bootstrapping من تقديره هو لقيمة الـ state الجاية.
التحديث بيحرّك التقدير القديم جزء قده α ناحية الـ reward زائد القيمة المخصومة لأحسن action جاي. في الممر عند α = 0.5 وγ = 0.9: Q(C, right) بتمشي من 0 لـ 5.0 لـ 7.5، وQ(B, right) بتبقى 2.25 من خطوة مدفعتش أي reward خالص.
القيمة بتنتشر لورا من الـ reward، بمعدّل state واحدة لكل episode تقريبًا، وبتعمل convergence لقيم Q* هي 10 و9 و8.1 للتلات خلايا.
الـ exploration بالـ epsilon-greedy بيخلّي كل action ينفع يتوصله؛ وتقليل ε تدريجيًا بينقل الـ agent من الـ exploration للـ exploitation. بسرعة زيادة فبيثبّت طريق متوسط؛ وببطء زيادة فمبيقبضش اللي يعرفه.
الـ Q-learning off-policy (بيعمل bootstrapping من الأكبر)؛ والـ SARSA on-policy (بيعمل bootstrapping من الـ action اللي اتاخد فعلًا). في الممر نفس الانتقال بيدّي 2.25 عند الـ Q-learning و0 عند الـ SARSA لو الـ action اللي بعده كان استكشافي.
الـ Q-learning الـ tabular بيفشل لما يكبر، مش بسبب الـ memory بس لكن لأن الجدول ميقدرش يعمّم بين states شبه بعض. والـ DQN بيبدّل الجدول بـ neural function approximator؛ وقاعدة التحديث متغيّرتش.
الحاجتين اللي ثبّتوا الـ DQN كل واحدة بتعالج مشكلة واحدة: الـ experience replay بيكسر الارتباط بين العينات اللي ورا بعض وبيعيد استخدام البيانات، والـ target network بتمنع target الـ regression إنه يتحرّك مع كل خطوة gradient.