مشكلة اللصوص متعددة الأذرع غير العشوائية

في مشكلة اللصوص متعددة الأذرع، يجب على المقامر أن يقرر أي ذراع من K من ماكينات القمار غير المتطابقة للعب في سلسلة من التجارب من أجل تحقيق أقصى قدر من المكافأة. لقد حصلت هذه المشكلة الكلاسيكية على الكثير من الاهتمام بسبب النموذج البسيط الذي تقدمه حول التوازن بين الاستكشاف (تجربة كل ذراع لإيجاد الأفضل) والاستغلال (العب بالذراع الذي يُعتقد أنه يعطي أفضل عائد). كانت الحلول السابقة لمشكلة اللصوص تعتمد تقريبًا دائمًا على افتراضات حول إحصائيات ماكينات القمار. في هذا العمل، لا نضع أي افتراضات إحصائية على الإطلاق حول طبيعة العملية التي تولد عوائد ماكينات القمار. نقدم حلاً لمشكلة اللصوص حيث يتمتع خصم، بدلاً من عملية عشوائية جيدة السلوك، بتحكم كامل على العوائد. في سلسلة من T لعبات، نثبت أن العائد لكل جولة لخوارزمية ours تقترب من أفضل ذراع بمعدل O(T-1/2 ). نوضح من خلال حد أدنى مطابق أن هذه هي أفضل نتيجة ممكنة. كما نثبت أن خوارزميتنا تقترب من العائد لكل جولة لأي مجموعة من الاستراتيجيات بنفس المعدل: إذا تم اختيار أفضل استراتيجية من مجموعة من N استراتيجيات، فإن خوارزميتنا تقترب من العائد لكل جولة للاستراتيجية بمعدل O((log N1/2T-1/2 ). أخيرًا، نطبق نتائجنا على مشكلة لعب لعبة مصفوفة متكررة غير معروفة. نوضح أن خوارزميتنا تقترب من عائد مينيماكس للعبة غير المعروفة بمعدل O(T-1/2 ).