درجة UCB1

Auer, Cesa-Bianchi & Fischer, 2002

نشر Peter Auer وزملاؤه UCB1 في عام 2002 كسياسة للـbandit محدودة الوقت مع حد للندم O(log N). يختار UCB1 ذراعًا بجمع متوسط مكافآته الحالي مع مكافأة استكشاف تتقلص مع زيادة سحب الذراع.

الصيغة

UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)

عنصرًا بعنصر:

- mean_reward(k): المتوسط الجائزة المُلاحظة للذراع k عبر n_k سحبات. مصطلح الاستغلال.

- N: إجمالي السحبات عبر جميع الأذرع حتى الآن. ينمو في كل خطوة.

- n_k: سحبات الذراع k تحديداً. ينمو فقط عندما يتم اختيار k.

- C: ثابت الاستكشاف. القيمة القياسية في الكتب الدراسية: 1.4 (sqrt(2)). ANDREA تستخدم C=0.5.

- sqrt(ln(N) / n_k): نصف قطر الثقة. ذراع نادراً ما يُسحب له n_k صغير ويحصل على مكافأة كبيرة؛ ذراع يُسحب جيداً له n_k كبير ويحصل على مكافأة صغيرة.

لماذا تعمل الصيغة

ln(N) ينمو ببطء (لوغاريتمي)، لذا يرتفع البسط بلطف مع الخبرة الإجمالية. n_k في المقام يقلل المصطلح مع تراكم الأدلة لذراع معين. الجذر التربيعي يلطف الاستجابة، مما يمنع ذراعاً غير مستكشف بما فيه الكفاية من السيطرة إلى الأبد.

اختيار argmax_k UCB(k) في كل خطوة يوازن بين الضغطين تلقائيًا. لا حاجة لمعامل إبسيلون، ولا جدول زمني، ولا درجة حرارة. الرياضيات تتعامل مع الأمر.

حساب درجة UCB

لماذا C=0.5 بدلاً من 1.4

القيمة المدرسية

يشتق Auer وCesa-Bianchi وFischer ربطًا للندم بافتراض أن المكافآت تقع في [0, 1]. ينطبق الربط لـ C = sqrt(2) تقريبًا 1.414. تعلم معظم الكتب المدرسية C=1.4 كقيمة افتراضية آمنة.

مقاييس مكافآت ANDREA

تقرير ANDREA تحسينات الخسارة لكل خطوة كمكافأة. التحسينات الخام تدور حول 0.001 (تنخفض الخسارة من 4.521 إلى 4.520). بعد عامل التوسيع 1000x (الموضح في النشاط 78، نسبة المكافأة)، تهبط المكافآت الموسعة قرب 1.0 في المقياس. تتراوح متوسطات المكافآت عبر تاريخ الذراع في نطاق 0.5 إلى 3.0.

الآن فكر في مكافأة الاستكشاف عند C=1.4 مع N=10000، n_k=100:

1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425

0.425 يقع داخل نطاق المكافأة. مقبول. الآن n_k=10 (ذراع نادر):

1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344

1.344 يقع فوق معظم متوسطات المكافآت المُلاحظة. الاستكشاف يسيطر: الذراع النادر يفوز بغض النظر عن متوسطِهِ الحقيقي. مع العديد من المصادر والتدريبات الطويلة، هذا يُغرق الجدول بالأذرع ذات المتوسط المنخفض.

الحل: C=0.5

0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480

0.480 يقع أقل من معظم متوسطات المكافآت. لا يزال الاستكشاف يحدث (الذراعات النادرة لا تزال تحصل على مكافأة)، لكن متوسط_المكافأة يقود. ANDREA تستغل أكثر، تستكشف أقل، وتتجنب هيمنة الاستكشاف.

ضبط الإعدادات كمهندسة، لا كنظرية

الحد النظري في الكتاب الدراسي يفترض مكافآت في [0, 1]. مكافآت ANDREA تعيش تقريباً في [0, 5]. توسيع الثابت يطابق الثابت مع حجم المكافأة. نفس الخوارزمية، بيئة معايرة.

تشخيص هيمنة الاستكشاف

القادم بعد ذلك

ما لديك

UCB1 يختار الذراع ذو الحد العلوي الأعلى للثقة. الحد يجمع متوسط المكافأة (استغلال) مع sqrt(ln(N) / n_k) مقياس بـ C (استكشاف). ANDREA يضبط C=0.5 لأن مكافآت الخطوة تتراوح في نطاق 0.5 إلى 3.0، والقيمة النصية 1.4 تغرق الجدول بالذراعات ذات المتوسط المنخفض.

ما الذي يتبقى

Vanilla UCB1 picks one arm at a time. ANDREA picks several focus arms per phase, mixes random arms first, & holds each phase for 7 to 42 steps. That structure (activity 77: dice phases) keeps UCB from overcommitting to early winners while still letting it concentrate effort.

Reward attribution (activity 78) shows where mean_reward(k) actually comes from. Floors & epoch penalties (activity 79) layer protective rules on top of UCB output.

المرجع

- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.

- ورقة بيضاء ANDREA، الأقسام 3.1 و 3.4.