📊 statistics

Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention

تقدم هذه الورقة إطار عمل جديداً للمتعدد الأذرع (multi-armed bandit) يتضمن خيار الامتناع، وتقدم خوارزميات فعالة حاسوبياً تحقق حدود ندم مثالية تقاربياً ومع حد أدنى من الندم (minimax optimal)، مما يطابق الحدود الدنيا لنظرية المعلومات، وقد تم التحقق من ذلك من خلال تجارب عددية مكثفة.

المؤلفون الأصليون: Junwen Yang, Tianyuan Jin, Vincent Y. F. Tan

نُشر 2026-03-24

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Junwen Yang, Tianyuan Jin, Vincent Y. F. Tan

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك ناقد طعام يحاول العثور على أفضل مطعم في مدينة جديدة. لديك قائمة تضم $K$ من المطاعم (الأذرع)، لكنك لا تعرف أي منها يقدم أفضل طعام. هدفك هو تناول أكبر عدد ممكن من الوجبات اللذيذة على مدار العام القادم (الأفق الزمني).

هذه هي مشكلة "المتعدد الأذرع" (Multi-Armed Bandit) الكلاسيكية. عليك الموازنة بين الاستكشاف (تجربة أماكن جديدة ومخاطرة لرؤية ما إذا كانت جيدة) والاستغلال (العودة إلى المكان الذي تعتقد أنه الأفضل).

التحول الجديد: خيار "شبكة الأمان"

يقدم هذا البحث قاعدة جديدة تغير قواعد اللعبة: خيار الامتناع.

في العالم الحقيقي، أحياناً يكون تجربة مطعم جديد أمراً محفوفاً بالمخاطر. ماذا لو كان الطعام سيئاً للغاية؟ ماذا لو كان خطراً على الصحة؟ في اللعبة القياسية، يجب عليك تناول الوجبة وتجرع مرارة الطعم السيئ (الندم).

في هذه اللعبة الجديدة، قبل أن تأخذ قضمة واحدة، يمكنك اختيار الامتناع.

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

السؤال الذي يطرحه البحث هو: هل يمكننا تصميم استراتيجية ذكية تستخدم شبكة الأمان هذه للتعلم بشكل أسرع ومعاناة أقل مما سبق؟

الإجابة هي نعم قاطعة.

السيناريوهان

يستعرض المؤلفون طريقتين لعمل شبكة الأمان هذه:

1. سيناريو "الندم الثابت" (سياسة التأمين)

تخيل أنك تختبر علاجاً طبياً جديداً قد يكون خطيراً.

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

استراتيجية الخوارزمية:
يعمل الكمبيوتر هنا مثل محقق حذر.

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

لقد أثبتت الورقة أن هذه الاستراتيجية فعالة تماماً. فهي تتعلم بأسرء ما يمكن نظرياً (مثالية تقاربياً) وتتعامل مع أسوأ السيناريوهات بشكل أفضل من أي طريقة أخرى (مثالية في حالة الحد الأدنى من الخسارة - minimax optimal).

2. سيناريو "المكافأة الثمن الثابت" (العائد المضمون)

تخيل أنك معلن تختار المنصة التي ستعرض عليها إعلاناتك (Google، LinkedIn، إلخ).

المخاطرة: أنت تدفع مقابل كل نقرة، لكنك لا تعرف ما إذا كانت هذه النقرات ستتحول إلى مبيعات أم لا.
الخيار: يمكنك اختيار صفقة "الدفع مقابل الإجراء" (Cost-Per-Action). أنت تدفع مبلغاً ثابتاً، وتحصل على مبيعة مضمونة.
الدرس المستفاد: إذا كانت نسبة النجاح المضمونة أعلى مما تتوقعه من المنصات المحفوفة بالمخاطر، فإنك تقبل الصفقة. ولكنك لا تزال تراقب أداء المنصات المحفوفة بالمخاطر لتتعلم معدلات تحويلها الحقيقية.

استراتيجية الخوارزمية:
هذا الأمر أبسط بكثير. تختار الخوارزمية منصة بناءً على أفضل تخمين لديها.

إذا كان معدل النجاح المقدر للمنصة أقل من العائد المضمون، فإنها تأخذ العائد المضمون (تمتنع).
إذا بدت المنصة أفضل من الضمان، فإنها تخوض المخاطرة.

تظهر الورقة أنه يمكنك أخذ أي خوارزمية ذكية موجودة وإضافة خطوة "المقارنة والتبديل" هذه فقط لجعلها مثالية لهذا الإعداد الجديد.

لماذا يهم هذا الأمر (لحظة الإدراك!)

في العالم القديم، لكي تعرف ما إذا كان المطعم سيئاً، كان عليك تناول وجبة سيئة. وكان ذلك مؤلماً.
في هذا العالم الجديد، يمكنك التعلم دون الشعور بالألم.

فكر في الأمر مثل طيار يتدرب في جهاز محاكاة الطيران.

الطريقة القديمة: تطير بطائرة حقيقية. إذا تحطمت، فقد تحطمت.
الطريقة الجديدة (الامتناع): تطير بالطائرة، ولكن لديك "زر إيقاف مؤقت" يجمّد المحاكاة قبل أن تصطدم بالأرض. ترى الحادث وشيكاً، وتتعلم لماذا حدث، ولكنك لا تصطدم فعلياً. لا تزال تحصل على الخبرة، ولكنك تحافظ على سلامة طائرتك.

النتائج

لم يكتفِ المؤلفون بالتخمين؛ بل قاموا بالحسابات وأجروا عمليات محاكاة.

النظرية: أثبتوا أن خوارزمياتهم هي الأفضل على الإطلاق. لا يمكنك التفوق على ما حققوه.
التطبيق: أجروا تجارب حاسوبية. أظهرت النتائج أن استخدام خيار "الامتناع" قلل بشكل كبير من إجمالي "الندم" (الألم/المال المفقود) مقارنة بالطرق التقليدية.

ملخص في جملة واحدة

يقدم هذا البحث طريقة ذكية لاتخاذ القرارات في المواقف غير المؤكدة من خلال السماح لك بـ "الانسحاب" من النتائج المحفوفة بالمخاطر مع الاستمرار في التعلم منها، مما يثبت أن هذه الاستراتيجية تؤدي إلى أسرع تعلم ممكن وأقل قدر من الندم.

إليك ملخص تقني مفصل للورقة البحثية بعنوان "حدود الندم المثلى تقاربياً وفي الحد الأدنى الأقصى للمتعدد من الأذرع مع الامتناع" (Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention) للباحثين جونوين يانغ، وتيان يوان جين، وفينسنت واي إف تان.

1. صياغة المشكلة

تتناول الورقة امتداداً جديداً لمشكلة المتعدد من الأذرع العشوائي (Stochastic Multi-Armed Bandit - MAB) التقليدية، حيث تقدم خياراً استراتيجياً وهو الامتناع (Abstention).

الإعداد القياسي: يختار الوكيل ذراعاً $A_t$ في كل خطوة زمنية $t$ ويلاحظ مكافأة عشوائية $X_t$ . الهدف هو تقليل الندم التراكمي بالنسبة للذراع المثالية.
إعداد الامتناع: في كل خطوة، بعد اختيار الذراع $A_t$ $A_{t}$ ، يمكن للوكيل أن يختار الامتناع (يُشار إليه بالمتغير الثنائي $B_t=1$ $B_{t} = 1$ ) عن قبول المكافأة العشوائية $X_t$ $X_{t}$ قبل ملاحظتها.
- من المهم ملاحظة أنه حتى إذا امتنع الوكيل، فإنه لا يزال يلاحظ تحقق $X_t$ من الذراع المختارة. وهذا يسمح للوكيل بـ "الاستكشاف الآمن" من خلال جمع معلومات حول توزيع الذراع دون تحمل التكلفة الكاملة لمكافأة قد تكون سيئة.
متغيران: تحلل الورقة إعدادين متميزين بناءً على كيفية تأثير الامتناع على الهدف:
1. إعداد الندم الثابت (Fixed-Regret Setting): يترتب على الامتناع ندم ثابت $c > 0$ . الندم اللحظي هو $\mu_1 - X_t$ إذا كان $B_t=0$ ، و $c$ إذا كان $B_t=1$ .
2. إعداد المكافأة الثابتة (Fixed-Reward Setting): ينتج عن الامتناع مكافأة حتمية $c \in \mathbb{R}$ . يُعرَّف الندم اللحظي بالنسبة لـ $\max(\mu_1, c)$ .

الدوافع: يستشهد المؤلفون بتطبيقات في التجارب السريرية (حيث يمكن للباحثين دفع تكلفة ثابتة للحماية من النتائج السلبية مع الاستمرار في مراقبة البيانات) والإعلانات عبر الإنترنت (حيث يمكن للشركات الانتقال إلى نموذج التكلفة لكل إجراء لضمان نتيجة ثابتة مع تتبع معدلات التحويل).

2. المنهجية والخوارزميات

يقترح المؤلفون خوارزميات محددة لكل إعداد تحقق كلاً من الأمثلية التقاربية (معدل نمو الندم الأمثل مع وصول $T \to \infty$ لحالة ثابتة) وأمثلية الحد الأدنى الأقصى (Minimax Optimality) (الندم الأسوأ في أسوأ الحالات عبر جميع الحالات).

أ. إعداد الندم الثابت: FRG-TSwA

صمم المؤلفون خوارماية "عينات ثومبسون للندم الثابت مع الامتناع" (Fixed-Regret Thompson Sampling with Abstention - FRG-TSwA)، المبنية على خوارزمية "عينات ثومبسون ذات الاستكشاف الأقل".

اختيار الذراع: تستخدم قاعدة معدلة لعينات ثومبسون حيث يتم سحب المكافأة المقدرة من التوزيع البعدي باحتمالية $1/K$ أو تعيين المتوسط التجريبي بخلاف ذلك.
معايير الامتناع: يعتمد قرار الامتناع ( $B_t=1$ $B_{t} = 1$ ) على شرطين:
1. الاعتماد على الفجوة (القائم على LCB): الامتناع إذا تجاوز الحد الأدنى لنطاق الثقة (LCB) لأي ذراع غير مختارة المتوسط التجريبي للذراع المختارة بمقدار $c$ على الأقل. هذا يعني أن الذراع المختارة من المرجح أن تكون دون المستوى الأمثل بفارق أكبر من تكلفة الامتناع.
2. عدم الاعتماد على الفجوة (الحالة الأسوأ): الامتناع إذا كان $\sqrt{K/t} \geq c$ . هذا يتعامل مع الخطوات الزمنية المبكرة أو السيناريوهات التي تكون فيها الندم $c$ صغيراً جداً، مما يضمن تجنب الخوارزمية لسيناريوهات الحالة الأسوأ.
الرؤية الجوهرية: تقوم الخوارزمية بفصل التعلم عن قبول المكافأة. من خلال الامتناع عندما يكون الفارق المقدر كبيراً، يدفع الوكيل تكلفة ثابتة $c$ (وهي أقل من الفارق المحتمل $\Delta_i$ ) مع الاستمرار في تحديث إحصائيات الذراع.

ب. إعداد المكافأة الثابتة: FRW-ALGwA

بالنسبة لإعداد المكافأة الثابتة، يقترح المؤلفون استراتيجية اختزال عامة تسمى "خوارزمية المكافأة الثابتة مع الامتناع" (Fixed-Reward Algorithm with Abstention - FRW-ALGwA).

الآلية: تأخذ هذه الخوارزمية أي خوارزمية أساسية (ALG) تكون بالفعل مثالية تقاربياً وفي الحد الأدنى الأقصى للمسألة التقليدية (مثل KL-UCB++، أو Less-Exploring TS) وتقوم بتعزيزها.
قاعدة الامتناع: في كل خطوة، إذا اختارت الخوارزمية الأساسية الذراع $A_t$ $A_{t}$ ، يقارن الوكيل المتوسط التجريبي $\hat{\mu}_{A_t}(t-1)$ $\overset{μ}{^}_{A_{t}} (t - 1)$ مع المكافأة $c$ $c$ للتعاقد.
- إذا كان $\hat{\mu}_{A_t}(t-1) \leq c$ ، يمتنع الوكيل ( $B_t=1$ ).
- خلاف ذلك، يقبل الوكيل المكافأة ( $B_t=0$ ).
الأهمية: يوضح هذا أن خيار الامتناع في إعداد المكافأة الثابتة لا يتطلب خوارزمية تعلم جديدة جذرياً؛ بل يمكن دمجه فوق الحلول المثلى الموجودة.

3. النتائج النظرية

تقدم الورقة براهين صارمة تثبت أن الخوارزميات المقترحة مثالية في كلا النظامين.

أ. إعداد الندم الثابت

الحد الأعلى التقاربي: يتدرج الندم كـ $O(\sum_{i>1} \frac{\Delta_i \wedge c}{\Delta_i^2} \log T)$ $O (\sum_{i > 1} \frac{Δ _{i} \land c}{Δ _{i}^{2}} lo g T)$ .
- التفسير: يشير المصطلح $\Delta_i \wedge c$ إلى أنه إذا كان فارق عدم المثالية $\Delta_i$ أكبر من تكلفة الامتناع $c$ ، فإن التكلفة الفعلية لاستكشاف تلك الذراع تُحدد بسقف قدره $c$ . وهذا يحسن بشكل مباشر من الحد التقليدي $\sum \frac{1}{\Delta_i} \log T$ .
حد الحد الأدنى الأقصى العلوي: يتم تحديد الندم بـ $O(\sqrt{KT} \wedge cT)$ $O (K T \land c T)$ .
- الانتقال الطوري: إذا كان $c$ صغيراً ( $c \leq \sqrt{K/T}$ )، فإن الاستراتيجية المثلى هي الامتناع باستمرار، مما يؤدي إلى ندم خطي $cT$ . إذا كان $c$ كبيراً، تتصرف الخوارزمية مثل مسألة متعددة من الأذرع قياسية بندم قدره $O(\sqrt{KT})$ .
الحدود الدنيا: يثبت المؤلفون حدوداً دنيا مطابقة، مما يؤكد أن لا خوارزمية يمكنها تحقيق معدلات تقاربية أو حد أدنى أقصى أفضل.

ب. إعداد المكافأة الثابتة

الحد الأعلى التقاربي: يتدرج الندم كـ $O(\sum_{i>1} \frac{(\mu_1 \vee c) - (\mu_i \vee c)}{\Delta_i^2} \log T)$ $O (\sum_{i > 1} \frac{( μ _{1} \lor c ) - ( μ _{i} \lor c )}{Δ _{i}^{2}} lo g T)$ .
- إذا كان $c \geq \mu_1$ ، يصبح الندم $o(\log T)$ لأن الامتناع هو الإجراء الأمثل دائماً.
حد الحد الأدنى الأقصى العلوي: الندم هو $O(\sqrt{KT})$ ، وهو ما يطابق الحد التقليدي.
الحدود الدنيا: تم اشتقاق حدود دنيا مطابقة، مما يثبت مثالية الخوارزمية. ومن الملاحظ أنه على عكس إعداد الندم الثابت، لا يوجد انتقال طوري في معدل الحد الأدنى الأقصى؛ إذ يظل ندم الحالة الأسوأ $\Omega(\sqrt{KT})$ بغض النظر عن $c$ .

4. المساهمات الرئيسية

إطار عمل جديد: أول صياغة رسمية لـ MAB مع خيار "الامتناع" حيث يلاحظ الوكيل المكافأة ولكنه يتجنب النتيجة العشوائية، وهو أمر قابل للتطبيق في اتخاذ القرار المتحفظ من المخاطر.
الأمثلية المزدوجة: تصميم خوارزميات تحقق في آن واحد الأمثلية التقاربية وأمثلية الحد الأدنى الأقصى، وهو مزيج نادر في أدبيات المسائل المتعددة من الأذرع (غالباً ما تكون الخوارزميات واحدة منهما فقط).
استراتيجية عامة: إثبات أنه بالنسبة لإعداد المكافأة الثابتة، يمكن تكييف أي خوارزمية قياسية مثلى بسهولة للتعامل مع الامتناع مع الحفاظ على المثالية.
الإحكام النظري: اشتقاق الحدود الدنيا للمعلومات التي تطابق الحدود العليا للخوارزميات المقترحة، مما يثبت أن الحدود محكمة.
التحقق التجريبي: تجارب عددية مكثفة على بيانات اصطناعية تظهر أن الخوارزميات المقترحة تتفوق بشكل كبير على المعايير القياسية (مثل Less-Exploring TS) وتتبع الحدود النظرية الدنيا بدقة.

5. الأهمية والتأثير

إدارة المخاطر: يوفر هذا العمل أساساً نظرياً لـ "الاستكشاف الآمن" في اتخاذ القرار عبر الإنترنت. فهو يحدد المقايضة بين دفع تكلفة ثابتة لتجنب المخاطر مقابل الربح المحتمل من التعلم من النتائج العشوائية.
الكفاءة الخوارزمية: الخوارزميات المقترحة فعالة حاسوبياً، حيث لا تضيف سوى عبء زمني ثابت إلى طرق عينات ثومبسون أو UCB القياسية.
القابلية للتطبيق العملي: تنطبق النماذج مباشرة على مجالات مثل التجارب السريرية (مراقبة السلامة)، والتمويل (التحوط)، والإعلانات (النتائج المضمونة)، حيث يحتاج صناع القرار إلى الموازنة بين التعلم وتخفيف المخاطر الفورية.
الاتجاهات المستقبلية: يقترح المؤلفون توسيع هذا الإطار إلى الأذرع الخطية (Linear Bandits) وإعدادات التغذية الراجعة الرسومية (Graph Feedback)، حيث يمكن أن يجعل التفاعل بين الأذرع خيار الامتناع أكثر قوة.

باختصار، تنجح هذه الورقة في سد الفجوة بين المثالية النظرية وإدارة المخاطر العملية، وتثبت أن "الامتناع" ليس مجرد وسيلة استدلالية (Heuristic) بل هو استراتيجية مثلى رياضياً تحت ظروف معينة.