Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks

إليك ملخص تقني مفصل للورقة البحثية بعنوان "العدالة للعمال الذين يسحبون الأذرع: سياسة قائمة على المؤشر لتخصيص مهام المجموعات المستمرة (Restless Bandits)".

1. تعريف المشكلة: المجموعات المستمرة متعددة الأذرع ومتعددة العمال (MWRMAB)

تعالج هذه الورقة فجوة في الأدبيات الحالية حول المجموعات المستمرة متعددة الأذرع (RMABs). بينما تفترض نماذج RMAB التقليدية اتخاذ القرار المتسلسل حيث يخصص المخطط موارد محدودة لـ $N$ من الأذرع المستقلة (عمليات ماركوف لاتخاذ القرار - MDPs) لتعظيم المكافآت طويلة الأجل، فإنها تفترض أن جميع الموارد متجانسة (قابلة للتبادل) ومستمدة من ميزانية عالمية واحدة.

قدم المؤلفون مشكلة المجموعات المستمرة متعددة الأذرع ومتعددة العمال (MWRMAB)، والتي تعكس قيود العالم الحقيقي حيث تكون موارد التدخل عبارة عن عمال بشريين غير متجانسين.

• الإعداد: يوجد $N$ من الأذرع (المهام) و $M$ من العمال. كل ذراع $i$ يتبع عملية ماركوف لاتخاذ القرار (MDP).
• عدم التجانس: لكل عامل $j$ تكاليف محددة ($c_{ij}$) وآثار تدخل (احتمالات الانتقال $P_{ij}$) عند العمل على الذراع $i$.
• القيود:
  1. ميزانية لكل عامل: لكل عامل $j$ ميزانية تكلفة صارمة $B$ في كل خطوة زمنية.
  2. العدالة: يجب ألا يتجاوز التفاوت في التكاليف المتكبدة من قبل أي زوج من العمال في أي خطوة زمنية عتبة $\epsilon$ (أي أن $\max_j C_j(t) - \min_j C_j(t) \leq \epsilon$).
• الهدف: تعظيم المكافأة المتوقعة طويلة الأجل مع الالتزام بقيود الميزانية الفردية وضمان عدالة الحمل بين العمال.

ثبت أن هذه المشكلة هي من نوع PSPACE-hard بسبب الانفجار التوليفي للحالات والأفعال عندما يكون $M > 1$.

2. المنهجية

اقترح المؤلفون إطار عمل مكون من ثلاث خطوات لحل مشكلة MWRMAB بكفاءة:

الخطوة 1: التفكيك وحساب المؤشر المنفصل

قام المؤلفون بتخفيف قيود الميزانية لكل خطوة زمنية إلى قيود متوسطة زمنياً لتفكيك المشكلة العالمية إلى $N \times M$ من المشكلات الفرعية المستقلة.

• قاموا بحساب مؤشرات ويتل (Whittle Indices) ($\lambda^*_{ij}$) لكل زوج (ذراع-عامل).
• يثبت النظرية 1 العلاقة بين المؤشرات والتكاليف: إذا كان لدى عاملين احتمالات انتقال متطابقة ولكن تكاليف مختلفة، فإن مؤشرات ويتل الخاصة بهما تتناسب عكسياً مع تكاليفهما ($\lambda^*_{ij} / \lambda^*_{ij'} = c_{ij'} / c_{ij}$).
• تفترض هذه الخطوة أن العمال يعملون بشكل مستقل، وهو ما يعد تقريباً.

الخطوة 2: حساب المؤشر المعدل (التعامل مع آثار التفاعل بين الأفعال)

المؤشرات المنفصلة من الخطوة 1 غير كافية لأن قيمة فعل العامل غالباً ما تعتمد على أفعال العمال الآخرين (على سبيل المثال، أحد العمال ينظف الأعشاب، والآخر يكشف الفخاخ).

• المشكلة: قد يكون المؤشر المنفصل للعامل (أ) صفراً إذا كان العامل (أ) لا يستطيع الوصول إلى حالة مكافأة بمفرده، حتى لو كان العامل (أ) ضرورياً عند الجمع مع العامل (ب).
• الحل: عرّف المؤلفون مؤشراً معدلاً ($\lambda^{adj,*}_{j}$). يمثل هذا المؤشر الحد الأدنى من الرسوم التي تجعل التدخل من قبل العامل $j$ ذا قيمة مساوية لأي عامل آخر $j'$ في عملية ماركوف لاتخاذ القرار (MDP) مشتركة تحتوي على $M+1$ من الأفعال.
• الخوارزمية: استخدموا البحث الثنائي لإيج "المؤشر المعدل"، من خلال ضبط الرسوم ($\lambda$) للعمال الآخرين لتكون مساوية لمؤشراتهم المنفصلة المحسوبة مسبقاً ($\lambda^*$).
  • المنطق: استخدام المؤشرات المنفصلة كرسوم للعمال الآخرين يوفر حداً أدنى واقعياً لقيمتهم، مما يمنع التثبيط الاصطناعي للمؤشرات (وهو خلل تم تحديده في النظرية 2 حيث يؤدي ضبط الرسوم الأخرى إلى 0 إلى سياسات ضعيفة).

الخطوة 3: خوارزمية التخصيص المتوازن

لضمان العدالة وجدوى الميزانية، اقترح المؤلفون خوارزمية التخصيص المتوازن (BA):

1. الترتيب: يتم ترتيب العمال بناءً على أعلى مؤشر ويتل متاح لهم لأي ذراع غير مخصص.
2. التخصيص بنظام التناوب (Round-Robin): يتم تخصيص الأذرع للعمال بنظام التناوب بناءً على هذا الترتيب.
3. فحص الميزانية: إذا انتهك ذراع ما ميزانية العامل، تحاول الخوارزمية البحث عن أفضل ذراع تالٍ. إذا تعذر تخصيص أي أذرع لعامل ما بسبب قيود الميزانية، يتم إخراج ذلك العامل مؤقتاً من الدورة.
4. ضمان العدالة: في الإعدادات المتجانسة، ثبت أن هذه الخوارزمية مثالية وعادلة تماماً (النظرية 3).

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

1. صياغة MWRMAB: أول من صاغ مشكلة RMAB مع عمال غير متجانسين، وميزانيات لكل عامل، وقيود صريحة على عدالة توزيع عبء العمل.
2. إطار عمل جديد للمؤشرات: تطوير طريقة لحساب مؤشرات ويتل المعدلة التي تأخذ في الاعتبار التبعيات بين العمال (آثار التفاعل بين الأفعال)، متجاوزةً بذلك حدود المؤشرات المنفصلة القياسية.
3. سياسة تخصيص عادلة: تقديم سياسة جدولة قابلة للتوسع تعتمد على المؤشر وتضمن العدالة دون التضحية الكبيرة بالمكافأة الإجمالية.
4. رؤى نظرية: أثبتوا أنه بالنسبة للعمال المتجانسين، فإن إطار العمل المقترح يعطي حلولاً مثالية وعادلة تماماً.

4. النتائج التجريبية

قيم المؤلفون طريقتهم (CWI+BA: مؤشر ويتل المدمج + التخصيص المتوازن) مقابل عدة نماذج أساسية:

• النماذج الأساسية:
  • PWI+BA: يستخدم المؤشرات المنفصلة (يتخطى الخطوة 2).
  • CWI+GA: يستخدم المؤشرات المعدلة ولكن مع التخصيص الجشع (Greedy Allocation) (يتخطى الخطوة 3).
  • Hawkins / OPT / OPT-fair: حلول مثالية أو قريبة من المثالية (تعقيد أسي، محدودة بالنماذج الصغيرة).
  • Random: التخصيص العشوائي.
• المجالات المختبرة: تكاليف موحدة ثابتة، عمال مرتبين (فعالية غير متجانسة)، ومجالات المتخصصين (مهارات متكاملة).
• مقاييس الأداء:
  • المكافأة: تحقق CWI+BA مكافآت مقاربة للنماذج المثالية (OPT/Hawkins)، مع حد أقصى للنقص قدره 18.95% في سيناريو "العمال المرتبين" الأكثر تحدياً.
  • العدالة: تحقق CWI+BA عدالة أعلى بكثير (نسبة الخطوات الزمنية ذات الحمل المتوازن) من النماذج التي تركز على تعظيم المكافأة. في الحالات واسعة النطاق ($N=150$)، أظهرت تحسناً في العدالة يصل إلى 374.92% مع انخفاض بنسبة 6.06% فقط في المكافأة مقارنة بالحلول التي تعظم المكافأة.
  • القابلية للتوسع: بينما تنفد ذاكرة الحلول المثالية (OPT-fair) عند $N \geq 10$، فإن CWI+BA تتوسع خطياً وتعمل في ثوانٍ حتى عند $N=150$.

5. الأهمية

هذا العمل مهم لعدة أسباب:

• القابلية للتطبيق في الواقع: يسد الفجوة بين نماذج RMAB النظرية والتطبيقات العملية التي تشمل القوى العاملة البشرية (مثل دوريات مكافحة الصيد الجائر، صيانة الآلات، أو التدخلات الصحية) حيث يمتلك العمال مهارات وتكاليف وحدود عمل مختلفة.
• العدالة في الذكاء الاصطناعي: يعالج جانباً حرجاً وغالباً ما يتم تجاهله في تخطيط الذكاء الاصطناعي: العدالة بين الوكلاء (العمال) الذين ينفذون الخطة، وليس فقط العدالة بين المستفيدين (الأذرع).
• القابلية للتوسع: يوفر حلاً قابلاً للتنفيذ حسابياً لمشكلة مستعصية نظرياً (PSPACE-hard) للحلول المثالية، مما يجعلها قابلة للاستخدام في الأنظمة واسعة النطلة في الوقت الفعلي.
• التعميم: يعمم مفهوم مؤشرات ويتل للتعامل مع التفاعلات المعقدة بين العديد من الوكلاء غير المتجانسين، مما يقدم توجهاً جديداً للبحث في اتخاذ القرار المتسلسل المقيد.