التعلم المعزز1992تأسيسي10 دقيقة قراءة

تعلُّم دالة الجودة (Q-Learning)

Q-Learning

Watkins, C. J. C. H. · Dayan, P. — Machine Learning

المشكلة

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

الإسهام

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

الأثر

أصبحت Q-Learning الخوارزمية التأسيسية للتعلم بالتعزيز المبني على القيمة. ألهمت مباشرةً شبكة DQN عام 2013 التي جمعت بين Q-Learning والشبكات العصبية العميقة وحققت أداءً يتفوّق على البشر في ألعاب Atari، فكانت شرارة ثورة . ومن أبرز امتداداتها CQL للتعلم بالتعزيز دون اتصال، وإطار الخيارات للتعلم الهرمي، فضلاً عن تطبيقات واسعة تمتد من الروبوتات إلى أنظمة التوصية. كل خوارزمية تعزيز مبنية على القيمة اليوم تعود في جذورها إلى هذه الخوارزمية.

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

لكنها ذكية: بعد أن تتناول العشاء في المطعم «ب»، تعود وتُعدّل تقييم المطعم «أ» الذي أوصاها بالذهاب إلى «ب». بعد أشهر، يتحوّل دفترها إلى تقييم دقيق لكل مطعم في المدينة — حتى تلك التي لم تزرها سوى مرة واحدة — لأن كل زيارة تنقل القيمة بشكل عكسي عبر سلسلة التوصيات.

خوارزمية Q-Learning هي ذلك الدفتر. كل خانة فيه تمثّل ، وكل وجبة تمثّل ، وانتشار التقييمات هو .

المشكلة: التعلّم بدون خريطة

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

قبل Q-Learning كان هناك منهجان أساسيان:

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

السؤال الجوهري كان: هل يستطيع الوكيل تعلّم السياسة المُثلى بالتجربة وحدها، بلا نموذج للبيئة، مع حرية الاستكشاف الكاملة؟

افتح في المختبر

شاهد الوكيل وهو يستكشف عالم الشبكة. جدول Q يُحدَّث لحظياً — لاحظ كيف تنتشر القيم بشكل عكسي انطلاقاً من الهدف.

تستيقظ التجربة عند وصولك…

الفكرة: تعلّم من أفضل مستقبل ممكن

تُسنِد Q-Learning قيمةً $Q(s, a)$ لكل زوج حالة-فعل: «ما مدى جودة اتخاذ الفعل $a$ في الحالة $s$ ؟» هذه القيمة تعبّر عن مجموع العائد المخصوم الذي يتوقعه الوكيل لو اتخذ الفعل $a$ الآن ثم تصرّف بالشكل الأمثل بعد ذلك.

الفكرة الجوهرية تكمن في طريقة تحديث هذه القيمة. بعد أن يتخذ الوكيل الفعل $a$ في الحالة $s$ ويحصل على المكافأة $r$ وينتقل إلى الحالة $s'$ ، يكون التحديث كالتالي:

Q(s, a) \;\leftarrow\; Q(s, a) \;+\; \alpha \Big[\, r \;+\; \gamma \max_{a'} Q(s', a') \;-\; Q(s, a) \,\Big]

قاعدة تحديث Q-Learning — α هو معدل التعلم (سرعة التحديث)، وγ هو مُعامل الخصم (مقدار اهتمامنا بالمستقبل)، أما max فتختار أفضل فعل في الحالة التالية — بغض النظر عن الفعل الذي اتُّخذ فعلاً.

لنفكّك المقدار الذي بين الأقواس — وهو ما يُسمّى خطأ الفارق الزمني (TD error):

$r$ هو المكافأة الفورية — التغذية الراجعة التي حصل عليها الوكيل من البيئة للتو.
$\gamma \max_{a'} Q(s', a')$ هو أفضل قيمة مستقبلية ممكنة من الحالة التالية. وهنا بيت القصيد: الوكيل لا يستخدم قيمة الفعل الذي سيتخذه فعلاً، بل يستخدم قيمة الفعل الذي ينبغي أن يتخذه لو تصرّف بالشكل الأمثل. هذا ما يجعل Q-Learning خوارزمية تتعلم .
$Q(s, a)$ هو التقدير الحالي — أي ما كان الوكيل يظن أن القيمة عليه.

خطأ الفارق الزمني إذن هو الفجوة بين «ما حدث فعلاً + أفضل مستقبل متوقع» و«ما كنتُ أتوقعه». يُقلّص الوكيل هذه الفجوة بنسبة α في كل خطوة، وبمرور الوقت تتقارب التقديرات نحو القيم المُثلى الحقيقية.

افتح في المختبر

تابع تحديث Q-Learning خطوة بخطوة. شاهد كيف يتقلّص خطأ الفارق الزمني مع استيعاب قيمة Q لإشارة المكافأة القادمة من المستقبل.

تستيقظ التجربة عند وصولك…

الإنجاز: التعلم خارج السياسة

عامل $\max$ في قاعدة التحديث هو ما يميّز Q-Learning عن سابقاتها. قارنها بخوارزمية SARSA التي تُحدّث باستخدام الفعل الذي يتخذه الوكيل فعلاً في الخطوة التالية:

Q_{\text{SARSA}}(s, a) \;\leftarrow\; Q(s, a) + \alpha \Big[\, r + \gamma\, Q(s', a') \;-\; Q(s, a) \,\Big]

تحديث SARSA (مرتبط بالسياسة) — يستخدم الفعل التالي الفعلي a'

لو كان الوكيل يستكشف بـ — أي يختار أفعالاً عشوائية بنسبة ε من الوقت — فإن القيم التي تتعلمها SARSA تتضمّن تكلفة تلك الأفعال العشوائية. بمعنى آخر، SARSA تتعلم قيمة السياسة الاستكشافية لا السياسة المُثلى.

عامل max في Q-Learning يتجاهل ما فعله الوكيل فعلاً ويسأل: «ما أفضل ما يمكنني فعله من هنا؟» هذا يفصل بين (الطريقة التي يستكشف بها الوكيل) و (ما يحاول الوكيل تعلّمه). النتيجة أن الوكيل يستطيع أن يستكشف بحرية تامة وفي الوقت ذاته يتعلم الاستراتيجية المُثلى — تماماً كطالب يتعلم القواعد الصحيحة من الكتاب بينما يحلّ تمارين فوضوية.

افتح في المختبر

قارن بين التحديث المرتبط بالسياسة (SARSA) والتحديث خارج السياسة (Q-Learning). لاحظ كيف تتقارب قيم Q-Learning نحو المسار الأمثل بينما تعكس قيم SARSA الانحرافات الاستكشافية.

تستيقظ التجربة عند وصولك…

الاستكشاف أم الاستغلال: سياسة ε-الجشعة

Q-Learning لا تحدّد كيف يختار الوكيل أفعاله أثناء التعلم — هي تحدّد فقط كيف تُحدَّث قيم Q. لكن طريقة الاختيار مهمة: لا بد أن يجرّب الوكيل كل زوج حالة-فعل مرات كافية حتى تتقارب القيم.

أبسط الاستراتيجيات وأكثرها شيوعاً هي سياسة ε-الجشعة: باحتمال $1 - \varepsilon$ يختار الوكيل الفعل الأفضل حسب القيم الحالية (الفعل ذا أعلى قيمة Q)، وباحتمال $\varepsilon$ يختار فعلاً عشوائياً. هذا يضمن أن كل فعل يُجرَّب عدداً لا نهائياً من المرات — وهو شرط ضروري لبرهان .

عملياً، يبدأ $\varepsilon$ بقيمة مرتفعة (مثلاً 1.0 — أي عشوائية كاملة) ثم يتناقص تدريجياً نحو قيمة صغيرة (مثلاً 0.05)، فينتقل الوكيل من إلى كلما تحسّنت معرفته بالبيئة.

افتح في المختبر

اسحب شريط ε لترى المفاضلة. ε مرتفع يعني استكشافاً أكثر وتقارباً أبطأ. ε منخفض يعني تقارباً أسرع لكن مع خطر تفويت مسارات أفضل.

تستيقظ التجربة عند وصولك…

التقارب: لماذا تنجح الخوارزمية فعلاً

أثبت واتكينز وديان (1992) أن Q-Learning تتقارب نحو دالة قيمة الفعل المُثلى الحقيقية $Q^*$ باحتمال 1، بشرط تحقّق ثلاثة شروط:

زيارة كل زوج حالة-فعل عدداً لا نهائياً من المرات. سياسة ε-الجشعة تكفل ذلك.
أن يُحقّق : $\sum \alpha_t = \infty$ و $\sum \alpha_t^2 < \infty$ . عملياً، معدل تعلم يتناقص ببطء يفي بالغرض.
أن تكون المكافآت محدودة. أي لا وجود لمكافآت لا نهائية.

فكرة البرهان مبنية على نظرية : تحديث Q-Learning عبارة عن مشوب بالضوضاء. كل تحديث يُقرّب Q من $Q^*$ (الجزء الانكماشي)، والضوضاء تتلاشى بالمتوسط عبر الزمن (التقريب العشوائي). $\gamma < 1$ يضمن أن الانكماش صارم، وشروط معدل التعلم تضمن تلاشي الضوضاء.

Q_t(s,a) \;\xrightarrow{t \to \infty}\; Q^*(s,a) \quad \text{w.p. 1} \quad \forall\; s, a

ضمان التقارب — مع تزايد عدد التحديثات، تتقارب كل قيمة Q نحو القيمة المُثلى باحتمال 1 — ما يعني أن Q-Learning ستجد في النهاية أفضل فعل في كل حالة.

جدول Q: ورقة الغش للسلوك الأمثل

في الصيغة الجدولية تُخزَّن قيم Q في يحتوي على صفّ لكل حالة وعمود لكل فعل. بعد التقارب يصبح استخراج السياسة المُثلى بسيطاً: في كل حالة اختر الفعل ذا أعلى قيمة Q.

\pi^*(s) = \arg\max_{a} Q^*(s, a)

استخراج السياسة المُثلى — بمجرد معرفة

Q^*

، تصبح السياسة المُثلى حتمية: اختر دائماً الفعل الأعلى قيمةً.

الخوارزمية الكاملة

خوارزمية Q-Learning مع استكشاف ε-جشعpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import numpy as np
def q_learning(env, n_episodes=1000, alpha=0.1, gamma=0.99,
                epsilon_start=1.0, epsilon_end=0.05, decay=0.995):
    """
    خوارزمية Q-Learning الجدولية.
    env: بيئة تحتوي على .reset()، .step(action)، .n_states، .n_actions
    """
    Q = np.zeros((env.n_states, env.n_actions))

    epsilon = epsilon_start
    for episode in range(n_episodes):
        state = env.reset()
        done = False

        while not done:
            # اختيار الفعل بسياسة ε-الجشعة
            if np.random.random() < epsilon:
                action = np.random.randint(env.n_actions)   # استكشاف
            else:
                action = np.argmax(Q[state])                # استغلال

            next_state, reward, done = env.step(action)

            # تحديث Q-Learning: استخدم القيمة القصوى من الحالة التالية (خارج السياسة)
            td_target = reward + gamma * np.max(Q[next_state]) * (1 - done)
            td_error  = td_target - Q[state, action]
            Q[state, action] += alpha * td_error

            state = next_state

        # تقليص معدل الاستكشاف تدريجياً
        epsilon = max(epsilon_end, epsilon * decay)

    return Q

العلاقة بمعادلة بيلمان

Q-Learning في جوهرها حلّال تدريجي يعمل بالعيّنات لحل معادلة بيلمان المُثلى. تنصّ معادلة بيلمان لـ $Q^*$ على ما يلي:

Q^*(s, a) = \mathbb{E}\Big[\, r + \gamma \max_{a'} Q^*(s', a') \;\Big|\; s, a \,\Big]

معادلة بيلمان المُثلى لـ Q*

البرمجة الديناميكية تحلّ هذه المعادلة بدقة تامة لكنها تحتاج النموذج الكامل للبيئة لحساب التوقع الرياضي. أما Q-Learning فتستبدل التوقع بعيّنة واحدة — الزوج الفعلي $(r, s')$ الذي رصده الوكيل — ثم تُصحّح بشكل تدريجي. ومع تراكم العيّنات، تتلاقى تقديرات العيّنات المنفردة نحو التوقع الحقيقي، وتتقارب قيم Q نحو $Q^*$ .

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

حدود Q-Learning الجدولي

Q-Learning الجدولي يعمل بشكل ممتاز في البيئات الصغيرة ذات الحالات المنفصلة، لكنه يصطدم بحاجز حقيقي حين يتّسع فضاء الحالات أو الأفعال:

الذاكرة: شبكة 100×100 مع 4 أفعال تتطلب 40,000 قيمة Q. لكن لعبة كالشطرنج فيها حالات أكثر من عدد الذرات في الكون.
التعميم: الجدول يعامل كل حالة باعتبارها مستقلة تماماً، فلا يستطيع إدراك أن حالتين متقاربتين ينبغي أن تحملا قيماً متشابهة.
الفضاءات المستمرة: إذا كانت الحالة مثلاً هي زوايا مفاصل روبوت — وهي قيم مستمرة — فلا يوجد جدول منتهٍ يمكن ملؤه.

هذه القيود هي التي دفعت نحو تقريب الدوال — أي استبدال جدول Q بـ قادرة على التعميم عبر الحالات. وهذا تحديداً ما فعلته DQN عام 2013 حين جمعت بين Q-Learning والشبكات العصبية العميقة للعب ألعاب Atari مباشرةً من البكسلات.

المسار التاريخي

1957
بيلمان — البرمجة الديناميكية
ريتشارد بيلمان يصوغ معادلة الأمثلية التي تُفكّك القرارات متعددة المراحل إلى مسائل فرعية عودية. قاعدة تحديث Q-Learning هي نسخة من هذه المعادلة تعمل بالعيّنات بدلاً من النموذج الكامل.
1988
ساتون — التعلم بالفارق الزمني
ريتشارد ساتون يضع الصياغة الرسمية للتعلم بالفارق الزمني: حدّث توقعاتك بناءً على الفرق بين تنبؤين متتاليين دون انتظار النتيجة النهائية. Q-Learning تبني على فكرة التمهيد بخطوة واحدة هذه.
1989
واتكينز — اقتراح Q-Learning
كريستوفر واتكينز يقترح Q-Learning في أطروحته للدكتوراه «التعلم من المكافآت المؤجلة» في كامبردج. أول خوارزمية تحكّم تعمل خارج السياسة وبدون نموذج للبيئة مع ضمانات رياضية للتقارب.
1992
واتكينز وديان — نشر برهان التقارب
يُنشر البرهان الرسمي للتقارب في مجلة Machine Learning، فيُرسي الأسس النظرية لـ Q-Learning ويجعلها الخوارزمية المرجعية للتعلم خارج السياسة.
1999
ساتون وآخرون — إطار الخيارات
يُوسّع نطاق Q-Learning إلى التعلم بالتعزيز الهرمي: «الخيارات» هي أفعال ممتدة زمنياً (أفعال كلية)، وتُتعلَّم قيم هذه الخيارات بآلية تحديث مشابهة لـ Q-Learning.
2013
منيه وآخرون — DQN
شبكة Q العميقة (DQN) تستبدل الجدول بشبكة عصبية، وتُضيف إعادة تشغيل التجارب وشبكة هدف، وتحقق أداءً يتفوق على البشر في ألعاب Atari. بذلك تبدأ حقبة التعلم العميق بالتعزيز.
2020
كومار وآخرون — CQL
Q-Learning المحافظ (CQL) يعالج سيناريو التعلم بالتعزيز دون اتصال: تعلّم سياسة من مجموعة بيانات ثابتة مع معاقبة قيم Q للأفعال التي لم تُرصد، لمنع المبالغة في تقدير أزواج الحالة-الفعل الخارجة عن التوزيع.

من معادلة بيلمان على الورق إلى إتقان DQN لألعاب Atari انطلاقاً من البكسلات — الخيط الناظم هو Q-Learning. كل خوارزمية تعلم عميق بالتعزيز مبنية على القيمة اليوم، من Rainbow إلى ناقد SAC، ترجع في أصلها إلى فكرة واتكينز عام 1989: استخدم القيمة القصوى، تجاهل السياسة، وتعلّم الأفضل.

المرجعWatkins, C. J. C. H., Dayan, P.. Q-Learning. Machine Learning 8(3-4), 1992.

مصطلحات هذه الورقة

تعلم دالة الجودة (Q)Q-Learning
دالة قيمة الفعل المتخذAction-Value Function (Q-Function)
معادلة بيلمان الرياضيةBellman Equation
الفارق الزمني الحسابيTemporal Difference
خوارزمية التعلم خارج السياسة الحاليةOff-Policy
التعلم بالتعزيز المباشر (دون نموذج بيئة)Model-Free RL
معضلة المفاضلة بين الاستكشاف والاستغلالExploration-Exploitation Dilemma
سياسة إبسيلون الجشعةε-Greedy
جدول قيم الجودةQ-Table
مُعامل الخصمDiscount Factor
التقارب الحسابيConvergence
التقليص الانكماشيContraction Mapping
انحياز التعظيمMaximization Bias