#multi-armed-bandit — التعلّم بالتعزيز

القاطع متعدّد الأذرع: أتستكشف أم تستغلّ؟

ما ستُجرّبه

1. مرحبًا بك في #multi-armed-bandit. على الشاشة خمس آلات قمار مصطفّة. كلٌّ منها تُخفي احتمال ربح مختلفًا — رقمٌ لن يُخبرك به أحد. فوق كل آلة شريطٌ أزرق: تقديرك Q(a) لمتوسّطها (الكل صفر، لم تسحب بعد)؛ وشريطٌ نيليٌّ رفيع: عدم يقينك. تحت كل آلة، ستعُدّ كومةٌ من الرقاقات سحباتك؛ وعلى اليمين، منحنيان يتتبّعان مكافأتك التراكمية (بالأزرق) وأسفك التراكميّ (بالورديّ). المعضلة: كل سحبةٍ على آلة تعرفها هي سحبةٌ أقلّ لاكتشاف ما إذا كانت أخرى تدفع أكثر. استغلّ ما تعرفه أو استكشف ما تجهله — تلك هي مسألة القاطع متعدّد الأذرع (multi-armed bandit)، وهي أيضًا مسألة اختبار A/B، ومحرّك التوصية، واختيار مطعم لهذه الليلة.
2. اسحب عشر مرّات باستراتيجية الجشعة الافتراضية: /pull 10. تلعب دائمًا الآلة صاحبة أكبر Q (عند التعادل، عشوائيًا). راقب الكرات وهي تسقط: أخضرُ يعني أنّ الآلة دفعت؛ وأحمرُ يعني لا شيء.
3. فلنتحقّق. اكشف الاحتمالات الحقيقية: /reveal. يظهر شريطٌ رماديّ خلف كلّ شريط أزرق — المتوسّط الحقيقيّ للآلة — وتُميَّز الذراع الأفضل بالأخضر.
4. لنُضِف قليلًا من العشوائية: /strategy epsilon. مع ε-الجشعة، سحبةٌ من كلّ عشر (ε = 0.10) تذهب إلى آلة مُختارة عشوائيًا؛ والتسع الأخريات تستغلّ التقدير الأفضل الحاليّ.
5. ابدأ جولةً طويلة: /play 500. خمسمئة سحبة دفعةً واحدة؛ تنزلق الأشرطة نحو قيمها الجديدة وتُرسَم المنحنيات.
6. انتقل إلى استراتيجية أدقّ: /strategy ucb. تلعب UCB (الحدّ الأعلى للثقة) الآلةَ صاحبةَ أكبر Q(a) + c·√(ln t / N(a)): التقدير مضافًا إليه مكافأةٌ لعدم اليقين تتقلّص كلّما سُحِبت الآلة.
7. أعِد لعب خمسمئة سحبة، هذه المرّة بـ UCB: /play 500.
8. جرِّد الحساب: /regret. يُعطيك الردّ الأسف التراكميّ، والآلة المُثلى، وتكلفة كلّ آلة عليك؛ ويكتبه المشهد بالورديّ على كلّ آلة.
9. دورك: /strategy thompson ثم /play 2000 (معاينةٌ بايزيّة: كثيرًا ما يكون أسفها الأفضل)، /arms 10 لعشر آلات (يزداد ثمن الاستكشاف)، /epsilon 0.3 أو /c 0.5 لضبط الشهيّة للاستكشاف، /seed 42 لآلات مختلفة، /reveal لإخفاء المتوسّطات الحقيقية من جديد، /reset لإعادة البدء. المحطّة التالية: #q-learning، حيث يجب على العميل أن يأخذ في الحسبان أيضًا الحالة التي هو فيها — يتحوّل القاطع إلى مسألة قرار تسلسليّة.

أوامر القناة

• /arms <2..10> — عدد الآلات؛ متوسّطات مخفيّة جديدة، والعدّادات تُصفَّر.
• /strategy <greedy|epsilon|ucb|thompson> — طريقة اختيار الآلة عند كلّ سحبة؛ يُحتفَظ بـ Q وN.
• /epsilon <0..1> — معدّل الاستكشاف ε لاستراتيجية ε-الجشعة.
• /c <0..3> — مكافأة استكشاف UCB وهي c: Q(a) + c·√(ln t / N(a)).
• /pull <1..50> — بضع سحبات، يُعاد لعبها واحدةً واحدة على الشاشة (كرة خضراء = ربح، حمراء = لا شيء).
• /play <100..2000> — محاكاةٌ طويلة: العب n من السحبات دفعةً واحدة وارسم المنحنيات.
• /reveal — أظهِر أو أخفِ المتوسّطات الحقيقية (الأشرطة الرمادية) والذراع الأفضل.
• /regret — ملخّص: الأسف التراكميّ، والآلة المُثلى، وحصّة كلّ آلة (تُظهَر أو تُخفى في المشهد).
• /seed <1..9999> — تُغيّر المتوسّطات المخفيّة والسحوبات العشوائية؛ العدّادات تُصفَّر.
• /reset — العودة إلى خمس آلات، الاستراتيجية الجشعة، ε = 0.10، c = 1، متوسّطاتٌ مخفيّة.

المسرد

القاطع متعدّد الأذرع (multi-armed bandit)

مسألةٌ تختار فيها مرارًا واحدةً من k آلات قمار ("أذرع") ذات مكاسب متوسّطة مجهولة، ملاحظًا فقط المكسب من الذراع المسحوبة. نموذجٌ لاختبار A/B والتوصية وتخصيص التجارب السريرية: التعلّم بالعمل، دون رؤية «ما كان سيفعله الخيار الآخر».

الاستكشاف والاستغلال

المعضلة المركزية: الاستغلال يعني لعب الذراع التي تظنّها الأفضل للحصاد؛ الاستكشاف يعني تجربة أخرى للتحقّق من عدم خطأك. الاستغلال الزائد يُغلقك على خطأ؛ والاستكشاف الزائد يُهدر. كلّ استراتيجية قاطعٍ هي طريقةٌ لجرعة هذه المقايضة.

الاستراتيجية الجشعة

تلعب دائمًا الذراع صاحبة أكبر Q(a) مُقدَّرة. بدون استكشاف، تنغلق على أوّل ذراعٍ دفعت: يبقى Q موجبًا بينما الأذرع التي لم تُجرَّب تبقى عند صفر. أسفٌ خطّيّ في أسوأ الحالات — «الدرس السلبيّ» للقاطع.

ε-الجشعة

باحتمال ε، ذراعٌ عشوائية؛ وإلا فأفضل Q. تُصحّح عيب الجشعة، لكنّ ε ثابتة تعني حصّة ثابتة من السحبات المهدورة: أسفٌ خطّيّ بميل ≈ ε × الفارق المتوسّط. يمكن تخفيض ε مع الزمن للوصول إلى أسفٍ تحت خطّيّ.

UCB (الحدّ الأعلى للثقة)

تلعب الذراع التي تُعظِّم Q(a) + c·√(ln t / N(a)): التقدير مضافًا إليه مكافأة عدم يقين، كبيرة لذراعٍ قليلة السحب وتتقلّص مع N(a). مبدأ التفاؤل عند مواجهة عدم اليقين. تضمن UCB1 (أوير، 2002) أسفًا من رتبة O(ln t)، وهي الرتبة المُثلى.

معاينة طومسون

المقاربة البايزيّة: لكلّ ذراع توزيعُ اعتقادٍ على متوسّطها — لمكاسب 0/1، توزيع Beta(1 + مكاسب, 1 + إخفاقات). في كلّ جولة نسحب قيمةً من كلّ توزيع ونلعب الذراع صاحبة أكبر عيّنة: تُختار الذراع إذًا باحتمال أنها الأفضل. بسيطةٌ وبلا معاملات، وكثيرًا ما تكون الأكثر فاعليةً عمليًّا.

الأسف (regret)

ما خسرته مقارنةً بلاعبٍ يعرف الذراع الأفضل: L(t) = Σ (μ* − μ_{a_s}) على t من السحبات. تكون الاستراتيجية جيّدةً إذا كان أسفها تحت خطّيّ (ينمو أبطأ من t): نسبة السحبات المهدورة تؤول إلى صفر. لا يمكن حسابه إلا حين تُعرَف المتوسّطات الحقيقية — عمليًّا تحدُّه، ولا تقيسه.

قيمة الفعل Q(a)

تقديرٌ للمكسب المتوسّط للذراع a: متوسّط المكاسب المُلاحظة، يُحدَّث بـ Q ← Q + (r − Q) / N(a) بعد كلّ سحبة (متوسّطٌ تزايديّ). نفس الكميّة Q(s, a) في تعلّم Q، من دون الحالة s: القاطع مسألة تعزيز ذات حالة واحدة.

المكافأة العشوائية

مكسب الذراع عشوائيّ: هنا 1 باحتمال μ_a، و0 خلاف ذلك (قانون برنولي). سحبةٌ واحدة لا تقول شيئًا تقريبًا عن μ_a؛ تحتاج N من السحبات لتقديرها بدقّة نحو 1/√N — عدم اليقين هذا هو ما تُظهِره الأشرطة الرفيعة وما يجب على الاستكشاف تقليله.

القاطع السياقيّ (contextual bandit)

متغيّرٌ تُلاحظ فيه سياقًا (ملفّ المستخدم، وقت اليوم، الصفحة) قبل اختيار الذراع، ويعتمد المكسب المتوسّط على هذا السياق. نموذجٌ لأنظمة التوصية والإعلانات الإلكترونية؛ خطوةٌ أخرى، بحالةٍ تتطوّر مع الأفعال، وتصل إلى التعلّم المعزَّز الكامل.

قنوات أخرى في التعلّم بالتعزيز

• #multi-armed-bandit — القاطع متعدّد الأذرع: أتستكشف أم تستغلّ؟
• #q-learning — تعلّم Q: تعلّم مسارٍ بالتجربة والخطأ.