الآلات ذات الأذرع والاستكشاف
Multi-Armed Bandits and Exploration
أبسط صورة لمعضلة الاستكشاف والاستغلال، واستراتيجيات ε-greedy وUCB وطريقة طومسون.
المسألة
عدد \(K\) من الأذرع، لكل منها متوسط مكافأة مجهول \(\mu_k\). في كل خطوة نختار ذراعاً ونرى مكافأته فقط. الهدف تعظيم المجموع، أو تقليل الندم:
$$\text{Regret}(T) = T\mu^* – \sum_{t=1}^{T} \mathbb{E}[r_t]$$
ثلاث استراتيجيات
| الاستراتيجية | الفكرة | ملاحظات |
|---|---|---|
| ε-greedy | استكشاف عشوائي بنسبة ε | بسيطة، لكنها تستكشف حتى الأذرع الرديئة الواضحة |
| UCB1 | التقدير + علاوة لعدم اليقين | ندم لوغاريتمي في الحالة القياسية |
| طومسون | معاينة من التوزيع اللاحق | فعالة عملياً وطبيعية مع الإطار البايزي |
UCB1
$$a_t = \arg\max_k \left( \hat{\mu}_k + \sqrt{\frac{2 \ln t}{n_k}} \right)$$
محاكاة صغيرة
import numpy as np
rng = np.random.default_rng(0)
true_p = np.array([0.05, 0.10, 0.12]) # احتمالات النجاح الحقيقية
a, b = np.ones(3), np.ones(3) # توزيع Beta مسبق لكل ذراع
for t in range(5000):
k = np.argmax(rng.beta(a, b)) # معاينة طومسون
r = rng.random() < true_p[k]
a[k] += r; b[k] += 1 - r
print((a + b - 2).astype(int)) # عدد مرات اختيار كل ذراعتطبيقات
- اختبارات A/B التكيفية في المواقع.
- التوصيات وتخصيص المحتوى (الآلات ذات السياق contextual bandits).
- التجارب السريرية التكيفية، مع ضوابط أخلاقية وتنظيمية صارمة.
الآلات ذات الأذرع حالة خاصة من MDP بحالة واحدة: الأفعال لا تغيّر الحالة، فلا توجد مشكلة إسناد فضل عبر الزمن.
مصطلحات الدرس
- الاستكشاف والاستغلال Exploration vs Exploitation
- الموازنة بين تجربة أفعال جديدة لاكتشاف مكافآت أفضل واستغلال أفضل فعل معروف حالياً.
- الندم Regret
- الفرق بين المكافأة الكلية لأفضل استراتيجية ممكنة والمكافأة التي حصّلها الوكيل فعلاً.
- معاينة طومسون Thompson Sampling
- اختيار الفعل بمعاينة قيمة لكل ذراع من توزيعها اللاحق ثم اختيار الأكبر.
الملخص
في مسألة الآلات ذات الأذرع يختار الوكيل كل مرة ذراعاً من عدة أذرع لكل منها توزيع مكافأة مجهول. الاستغلال يعني اختيار أفضل ذراع حسب التقديرات الحالية، والاستكشاف يعني تجربة أذرع أخرى لتحسين التقدير. استراتيجية ε-greedy تستكشف عشوائياً بنسبة ε، وUCB تضيف علاوة لعدم اليقين، وطريقة طومسون تعاين من التوزيع اللاحق. تُستخدم في التجارب الإلكترونية والتوصيات والتجارب السريرية التكيفية.
أسئلة مراجعة
-
لماذا تفشل الاستراتيجية الجشعة البحتة؟
لأنها قد تثبت على ذراع رديئة بسبب تقدير أولي محظوظ ولا تجرب الأذرع الأخرى بما يكفي.
-
ما فكرة UCB؟
اختيار الذراع ذات أعلى حد ثقة علوي، أي التقدير مضافاً إليه علاوة تكبر مع قلة التجارب.
المصادر والمراجع
إكمال الدرس
أكملت كل دروس المسار! يمكنك الآن طلب شهادة إكمال المسار.
اطلب الشهادة