التعلّم المعزّز وتعلّم Q

حلّت عمليات القرار الماركوفية مسألة التخطيط: بمعلومية $P(s' \mid s, a)$ و$R(s)$، يعيد تكرار القيمة سياسةً مثلى. لكن الوكيل المُلقى في بيئة غير مألوفة لا يملك أياً منهما. فهو لا يعرف ماذا تفعل أفعاله، ولا أين المكافآت. وعليه أن يكتشف ذلك بالتصرّف.

تلك هي مسألة التعلّم المعزّز، وهي أقرب بكثير إلى الوضع الذي يوجد فيه أي وكيل حقيقي.

أ. التعلّم من الفرق بين تقديرين متعاقبين

لنفترض أن الوكيل يتبع سياسةً $\pi$ في عالم $4 \times 3$ عند Russell وNorvig، حيث تكلّف كل خطوة $R = -0.04$ ولا تُخصم المكافآت ($\gamma = 1$)، ويعتقد حالياً $U^{\pi}(1,3) = 0.84$ و$U^{\pi}(2,3) = 0.92$. ثم يرصد انتقالاً من $(1,3)$ إلى $(2,3)$. فلو وقع ذلك الانتقال في كل مرة، لوجب أن تحقّق المنفعتان علاقة بلمان لـ$\pi$، أي $U^{\pi}(1,3) = -0.04 + 0.92 = 0.88$ - وهما لا تحقّقانها تماماً. فالتقدير عند $(1,3)$ يبدو منخفضاً قليلاً. (ومع $\gamma = 0.9$ المستعملة لاحقاً في هذه المقالة يصير الهدف $0.788$، ويبدو التقدير نفسه مرتفعاً.)

والعلاج دفعُه نحو الاتّساق. فعند رصد انتقال $s \to s'$:

$$U^{\pi}(s) \leftarrow U^{\pi}(s) + \alpha\big(R(s) + \gamma\, U^{\pi}(s') - U^{\pi}(s)\big),$$

حيث $\alpha$ معدّل التعلّم. وهذا تحديث الفرق الزمني (TD)، سُمّي كذلك لأنه مدفوع بالفرق بين تقديري المنفعة في خطوتين زمنيتين متعاقبتين.

والكمية بين القوسين هي خطأ TD: أي ما رصدناه للتوّ، $R(s) + \gamma U(s')$، ناقص ما كنا نعتقده، $U(s)$. والخطأ الصفري يعني أن تقديراتنا متّسقة محلياً فلا شيء يتغيّر. وكل طرق TD تعمل هكذا - بتعديل التقديرات نحو التوازن الذي يصحّ حين تكون صحيحة.

لماذا هذا لافت. لا يذكر التحديث أي احتمالات إطلاقاً. فالوكيل لا يقدّر $P(s' \mid s, a)$ أبداً. ومع ذلك، لأن الانتقالات تُعايَن من النموذج الحقيقي، تقود الانتقالاتُ المتكرّرة التحديثَ بتناسب مع تكرارها، ويحدث المتوسّط ضمنياً. فالنموذج لا يُتعلَّم قط، بل يُطاع فحسب.

ب. من المنافع إلى قيم الأفعال

يتعلّم TD كما كُتب $U^{\pi}(s)$ - أي مدى جودة الحالة. وهذا غير قابل للتنفيذ مباشرةً: فلكي يختار الوكيل عليه معرفة جودة كل فعل متاح، وتحويل $U$ إلى اختيار يستلزم معرفة إلى أين تؤدّي الأفعال، وهو بالضبط النموذج الذي لا نملكه.

فلنتعلّم قيم الأفعال بدلاً من ذلك. عرّف $Q(s, a)$ بأنها المنفعة المتوقّعة لاتّخاذ الفعل $a$ في الحالة $s$. وترتبط الاثنتان بـ

$$U(s) = \max_{a} Q(s, a),$$

ويستطيع الوكيل الذي يملك $Q$ أن يتصرّف بلا أي نموذج البتّة: انظر في صف الحالة الحالية وخذ أكبر مدخلة.

ج. تحديث تعلّم Q

$$Q(s, a) \leftarrow Q(s, a) + \alpha\Big(R(s) + \gamma \max_{a'} Q(s', a') - Q(s, a)\Big)$$

ويُطبَّق كلما اتُّخذ الفعل $a$ في $s$ وأدّى إلى $s'$. وهو فكرة TD مع استبدال أفضل قيمة فعل متاحة عند الحالة التالية بمنفعة الحالة.

و$\max_{a'}$ هي التفصيلة الحاسمة. فالوكيل يرجّع قيمة أفضل فعل عند $s'$، بغضّ النظر عمّا يفعله تالياً فعلاً. وهذا يجعل تعلّم Q خارج السياسة: فهو يتعلّم عن السياسة المثلى بينما يتصرّف وفق سياسة أخرى أكثر استكشافاً.

أما قريبه SARSA - اختصاراً لحالة، فعل، مكافأة، حالة، فعل - فيستخدم بدل ذلك الفعل $a'$ المتَّخذ فعلاً:

$$Q(s, a) \leftarrow Q(s, a) + \alpha\big(R(s) + \gamma\, Q(s', a') - Q(s, a)\big).$$

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

د. الآلية، خطوةً خطوة

خذ عالم المقالة السابقة: حالتان غير نهائيتين $s_1, s_2$ بـ$R(s) = -0.04$، ونهائيتان GOAL بـ$(+1)$ وPIT بـ$(-1)$، و$\gamma = 0.9$. وتبدأ كل قيم $Q$ من الصفر. ولنستخدم $\alpha = 0.5$.

لنفترض أن الوكيل يسلك $s_1 \to s_2 \to$ GOAL، مرتين.

التحديث 1، $(s_1, \text{Right}) \to s_2$. وكل $Q(s_2, \cdot)$ ما زالت $0$:

$$Q(s_1, \text{Right}) \leftarrow 0 + 0.5\big(-0.04 + 0.9 \times 0 - 0\big) = -0.02 .$$

التحديث 2، $(s_2, \text{Right}) \to$ GOAL، وقيمتها $+1$:

$$Q(s_2, \text{Right}) \leftarrow 0 + 0.5\big(-0.04 + 0.9 \times 1 - 0\big) = 0.5 \times 0.86 = 0.43 .$$

التحديث 3، $(s_1, \text{Right}) \to s_2$ مرة أخرى - لكن لـ$s_2$ الآن قيمة:

$$Q(s_1, \text{Right}) \leftarrow -0.02 + 0.5\big(-0.04 + 0.9 \times 0.43 - (-0.02)\big) = 0.1635 .$$

التحديث 4، $(s_2, \text{Right}) \to$ GOAL: $0.43 + 0.5(0.86 - 0.43) = 0.645$.

لاحظ كيف تنتشر القيمة إلى الوراء: فلا يصل شيء مفيد إلى $s_1$ قبل أن تتعلّم $s_2$ شيئاً أولاً.

هذه المتتالية بعينها تتقارب إلى الرقم الخطأ، وهذا هو المقصود. فكلتا الحلقتين أعلاه انتُقيتا يدوياً لبلوغ GOAL. وتكرارهما وحدهما يدفع $Q(s_2, \text{Right})$ نحو $-0.04 + 0.9(1) = 0.86$ - وهي قيمة Right الذي ينجح دائماً. لكن Right لا يبلغ GOAL إلا 80٪ من الوقت؛ وفي الـ20٪ الباقية يسقط في PIT. والقيمة الصحيحة $-0.04 + 0.9\,(0.8 \times 1 + 0.2 \times (-1)) = 0.5$. ولا يبلغها تعلّم Q إلا لأن التجربة الحقيقية تعاين النتيجتين بالنسبة الصحيحة. فالعيّنة المتحيّزة تعطي إجابة متحيّزة.

هـ. الاستكشاف في مقابل الاستثمار

الوكيل الذي يأخذ دائماً أفضل فعل حالي قد لا يكتشف أفضل منه أبداً. والوكيل الذي يتصرّف دائماً عشوائياً يتعلّم عن كل شيء ولا يستثمر شيئاً. وهذه هي مقايضة الاستكشاف والاستثمار.

وأبسط جواب عملي هو الجشِع-$\varepsilon$: تصرّف جشِعاً باحتمال $1 - \varepsilon$، وعشوائياً باحتمال $\varepsilon$. وما دام $\varepsilon$ يتناقص مع الزمن، يستكشف الوكيل بما يكفي مبكراً ليجد الأفعال الجيدة ويستثمر بما يكفي لاحقاً ليراكم المكافأة. وتستخدم المخطّطات الأدقّ دالةَ استكشاف تضخّم قيمة أزواج الحالة-الفعل التي جُرّبت نادراً، وهو ما يقتضي حفظ عدّادات الزيارات.

يطبّق الشكل أدناه التحديث نفسه في عالم مختلف قليلًا، فأرقامه ليست أرقام الجدول: حالتان A وB، وحالة نهائية قيمتها $+1$ تُبلغ بالذهاب يمينًا من B، وحركة يمين تفشل في 20% من المرات فتعيد العميل إلى A بدل أن تُسقطه في حفرة. ويبدأ بخمس رحلات مرسومة سلفًا تنجح كلها، بالترتيب B، B، A، B، A. تنقّل بينها وراقب الترتيب لا الأرقام. فـA يبقى عند الصفر تمامًا في الرحلتين الأوليين، لأن أيًّا منهما لا تبدأ من A، ثم يجد تحديثه الأول B وقد بلغ $0.42$. ثم حاكِ البيئة التي يواجهها العميل فعلًا. فنظامٌ من الرحلات الناجحة دائمًا يتقارب إلى 0.8600 عند B، وهي قيمة عالمٍ ينجح فيه الذهاب يمينًا دائمًا. ولا يعلّم خلافَ ذلك إلا الانزلاق.

و. هل يستعيد فعلاً الأمثلية المخطَّطة؟

حسبت المقالة السابقة الإجابة الدقيقة بالتخطيط مع معرفة كاملة بالنموذج: $U(s_1) = 0.3902$ و$U(s_2) = 0.5000$. ولا يرى متعلّم Q ذلك النموذج قط. شغّله 200,000 حلقة بـ$\varepsilon = 0.2$ ومعدّل تعلّم متناقص:

يطبع:

وأخذ $U(s) = \max_a Q(s,a)$ يعطي $0.3847$ و$0.4926$، مقابل $0.3902$ و$0.5000$ المخطَّطتين - والسياسة الجشِعة المقروءة من هذه القيم هي Right في الحالتين، وهي بالضبط السياسة التي أنتجها تكرار القيمة. فقد استعاد الوكيل السلوك الأمثل دون أن يُخبَر قط بما تفعله أفعاله.

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

ز. الحدود

كل ما هنا يفترض جدول $Q$ بمدخلة لكل زوج حالة-فعل. وهذا حسن لأربع مدخلات وميؤوس منه للشطرنج أو لأي بيئة ذات حالة متصلة. فالمسائل الحقيقية تحتاج التعميم: تقريب $Q$ بدالة مُبارَمة بدل تعدادها، وهنا يلتقي التعلّم المعزّز ببقية تعلّم الآلة.

والحدّ الثاني أن وكلاء تعلّم Q لا يستطيعون النظر إلى الأمام. فلأنهم لا يعرفون إلى أين تؤدّي الأفعال، لا يستطيعون تخطيط متتالية كما يفعل وكيل قائم على نموذج - بل يستطيعون فقط مقارنة قيم الأفعال التي تعلّموها. فالتحرّر من النموذج يُشترى بثمن بُعد النظر.

الخلاصات الأساسية

• يُسقط التعلّم المعزّز افتراض عملية القرار الماركوفية بأن النموذج معلوم؛ ويتعلّم الوكيل من التجربة بدلاً من ذلك.
• تحديث TD يدفع التقديرات نحو الاتّساق المحلي، بلا أي احتمالات - إذ توفّر المعاينة المتوسّط ضمنياً.
• $Q(s,a)$ تجعل اختيار الفعل خالياً من النموذج، مع $U(s) = \max_a Q(s,a)$.
• قاعدة تعلّم Q ترجّع $\max_{a'} Q(s', a')$، فتجعله خارج السياسة؛ بينما يرجّع SARSA الفعل المتَّخذ فعلاً فيكون داخل السياسة.
• تنتشر القيمة إلى الوراء من المكافآت، بتحديث واحد لكل خطوة.
• العيّنة المتحيّزة من الانتقالات تعطي $Q$ متحيّزة؛ والصحّة تعتمد على تجربة النتائج بنسبها الحقيقية.
• بلغ متعلّمنا $0.3847$ و$0.4926$ مقابل $0.3902$ و$0.5000$ المخطَّطتين، فاستعاد السياسة المثلى بلا نموذج.
• و$Q$ الجدولية لا تتوسّع؛ والتعميم هو الجسر إلى بقية تعلّم الآلة.

ما التالي

مسألة الاستكشاف، وخطأ المعاينة أعلاه، وسؤال إسناد الفضل، كلها ذات نكهة معلوماتية. وتجعل الإنتروبيا والمعلومات فكرةَ «كم بقي من اللايقين» دقيقة.