العدالة في التعلم: اللصوص الكلاسيكيون والسياقيون

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