Past-Discounting is Key for Learning Markovian Fairness with Long Horizons

ملخص تقني: الخصم الماضي لتعلم العدالة الماركوفية في الآفاق الزمنية الطويلة

1. بيان المشكلة

يتطلب التخصيص الديناميكي للموارد في الأنظمة متعددة الوكلاء موازنة الكفاءة مع العدالة عبر آفاق زمنية طويلة. تواجه النهج الحالية معضلة جوهرية:

• العدالة اللحظية (الآنية): تقيم العدالة بناءً على خطوة التخصيص الحالية فقط. وبينما هي بسيطة حاسوبياً، إلا أنها تتجاهل السياق التاريخي، مما يؤدي إلى عدم مساواة تراكمي بمرور الوقت.
• عدالة الاستدعاء الكامل (Perfect-Recall): تتبع مجموع كافة المنفعات الماضية لضمان المساواة طويلة الأمد. ورغم أنها عادلة نظرياً، إلا أن هذا النهج يفرض نمط فشل حرج: فالفضاء الحيزي المعزز المطلوب لتتبع المنفعات التراكمية يتوسع بشكل غير محدود مع اتساع الأفق الزمني. هذا الانفجار في مساحة الحالة يجعل خوارزميات التعلم المعزز (RL) غير قابلة للتطبيق حاسوبياً ويمنع التقارب نحو سياسات عادلة في الإعدادات ذات الآفاق الطويلة.

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

2. المنهجية

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

أ. آليات ذاكرة الاستدعاء المخصوم (Discounted-Recall)
بدلاً من جمع كافة المنفعات الماضية ($Z_t = \sum u_\tau$)، يطبق إطار العمل عامل خصم قابل للضبط $\gamma_p \in [0, 1]$ على المنفعات التاريخية. تم تحديد صيغتين محددتين:

1. الاستدعاء المخصوم الجمعي: يتم تحديث حالة الذاكرة كـ $Z_t = \gamma_p Z_{t-1} + u_t$. حيث تؤدي قيمة $\gamma_p=0$ إلى العودة للعدالة اللحظية، و$\gamma_p=1$ إلى استعادة الاستدعاء الكامل.
2. الاستدعاء المخصوم المتوسط: يتم خصم كل من المنفعة المتراكمة والمقام الزمني الفعال، مما يضمن بقاء حالة الذاكرة محدودة حتى عند حساب المتوسط.

ب. التحليل النظري لمساحة الحالة
يقدم البحث براهين صارمة تقارن خصائص مساحة الحالة بين النماذج المختلفة:

• الاستدعاء الكامل (الجمعي): تثبت النظرية 3 أن مساحة الحالة تنمو خطياً مع الأفق الزمني $t$ لكل إحداثي، وتنمو أسياً مع عدد الوكلاء $n$. يؤدي هذا إلى مساحة حالة غير محدودة، مما يجعل التجزئة ثابتة الدقة مستحيلة في الآفاق الطويلة.
• الاستدعاء الكامل (المتوسط): تظهر النظرية 5 أنه بينما تظل قيمة المنفعة المتوسطة محدودة، فإن الحفاظ على خاصية ماركوف يتطلب حمل المؤشر الزمني $t$ (أو ما يعادله من مقام) كجزء من الحالة، وهو أمر غير محدود أيضاً.
• الخصم الماضي (الجمعي والمتوسط): تثبت النظريتان 4 و6 أنه مع وجود $\gamma_p < 1$، تكون حالة الذاكرة $Z_t$ محدودة بشكل موحد بـ $u_{max} / (1 - \gamma_p)$. والأهم من ذلك، أن حجم مساحة الحالة المعززة يصبح مستقلاً عن الأفق الزمني، مما يستوفي شروط التعلم القابل للتطبيق.

ج. الارتباط بنظرية التحكم
يوسع المؤلفون التحليل من خلال نمذجة ذاكرة العدالة كنظام خطي زمني ثابت (LTI). ويوضحون أنه لكي تظل حالة الذاكرة محدودة، يجب أن يكون نصف قطر الطيف لمصفوفة انتقال الذاكرة أقل من واحد ($\rho(A) < 1$). يمثل الاستدعاء الكامل مصفوفة الوحدة ($\rho=1$)، وهي غير مستقرة، بينما يمثل الخصم الماضي مصفوفة وحدة مُقلصة ($\rho = \gamma_p < 1$)، مما يضمن الاستقرار.

د. عمر النصف والنافذة الفعالة
لمساعدة الممارسين في اختيار $\gamma_p$، يقدم البحث مفهوم "عمر النصف" ($t_{1/2}$) و"النافذة الفعالة" ($W_{eff} = 1/(1-\gamma_p)$). تقيس هذه المقاييس عدد الخطوات الماضية التي تؤثر بشكل ملموس على تقييم العدالة الحالي، مما يسمح بمفاضلة مبدئية بين عمق الذاكرة والجدوى الحاسوبية.

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

قام المؤلفون بالتحقق تجريبياً من نظريتهم باستخدام إعداد تعلم معزز متعدد الوكلاء (MARL) مع وكيل يستخدم خوارزمية تحسين السياسة القريبة (PPO) في بيئة تخصيص موارد ديناميكية (10 وكلاء، موردان لكل خطوة).

• الإعداد: تم تدريب الوكلاء عبر آفاق زمنية متغيرة ($T=100$ إلى $T=10,000$) تحت ثلاثة تكوينات للذاكرة: لحظي ($\gamma_p=0$)، استدعاء كامل ($\gamma_p=1$)، وخصم ماضي ($\gamma_p \in \{0.9, 0.99, 0.999\}$).
• النتائج:
  • الوكلاء اللحظيون: فشلوا في تعلم سياسات عادلة، مما أدى إلى عدم مساواة عالية (معامل جيني مرتفع) بسبب غياب السياق التاريخي.
  • وكلاء الاستدعاء الكامل: أبلوا بلاءً حسناً في الآفاق القصيرة ($T \le 500$)، لكنهم عانوا من انهيار كارثي في الأداء مع زيادة الأفق الزمني. عند $T=10,000$، تدهورت قدرتهم على الحفاظ على العدالة لتصل إلى مستوى الوكلاء اللحظيين، مما يؤكد التنبؤ النظري بانفجار مساحة الحالة الذي يعيق التقارب.
  • وكلاء الخصم الماضي: نجحوا في تعلم سياسات عادلة قوية عبر جميع الآفاق الزمنية. سمح التمثيل المحدود للحالة لخوارزمية PPO بالتقارب.
  • حساسية المعلمات: اعتمد $\gamma_p$ الأمثل على كثافة إشارة العدالة. بالنسبة للإشارات الكثيفة (رفاهية ناش)، كانت الذاكرة الأقصر ($\gamma_p=0.9$) كافية. أما بالنسبة للإشارات المتفرقة (الرفاهية المساواتية)، فقد تطلب الأمر ذاكرة أطول ($\gamma_p=0.99$) لتجميع معلومات كافية.

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

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

5. الأهمية والادعاءات

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

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