💬 NLP

Online Learning and Equilibrium Computation with Ranking Feedback

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

المؤلفون الأصليون: Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

نُشر 2026-03-20

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, Kaiqing Zhang

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

تخيل أنك شيف يدير مطعماً مزدحماً، لكن لديك مشكلة غريبة جداً: لا يمكنك أبداً تذوق طعامك الخاص.

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

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

هذه الورقة البحثية تدور حول حل هذه المشكلة تحديداً، ولكن في عالم الحواسيب والذكاء الاصطناعي. يتساءل الباحثون: "هل يمكننا اتخاذ قرارات مثالية إذا لم نحصل إلا على 'قائمة ترتيب' كتعليقات بدلاً من درجة رقمية؟"

إليك تفصيل اكتشافهم، باستخدام استعارات بسيطة.

1. نوعا التعليقات (Feedback)

تنظر الورقة إلى طريقتين مختلفتين قد يقدم بهما "الزبون" قائمة الترتيب تلك:

الزبون "اللحظي" (InstUtil Rank): هذا الزبون يرتب الطعام بناءً على مذاقه في هذه اللحظة فقط. ربما يكون جائعاً اليوم، لكن ليس غداً. مزاجه يتغير لحظياً.
الزبون "ذا الذاكرة" (AvgUtil Rank): هذا الزبون يرتب الطعام بناءً على كيف كان مذاقه طوال الأسبوع. هو يتذكر أن المعكرونة كانت رائعة بالأمس، لذا يضعها في مرتبة عالية اليوم، حتى لو كانت دفعة اليوم عادية فحسب.

2. الأخبار السيئة: أحياناً لا يمكنك الفوز

حاول الباحثون أولاً إيجاد خوارزمية سحرية تعمل في أي موقف. واكتشفوا حقيقة قاسية: أحياناً، يكون من المستح المستحيل رياضياً أن تتعلم.

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

3. الأخبار الجيدة: الحل "الناعم"

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

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

كيف يفعلون ذلك؟
لقد اخترعوا نوعاً جديداً من خوارزمية "المترجم":

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

4. التواء نظرية الألعاب: إيجاد تطابق عادل

تطبق الورقة هذا أيضاً على الألعاب، وتحديداً أشياء مثل تطبيقات المواعدة عبر الإنترنت أو تطبيقات النقل الذكي.

تخيل تطبيق مواعدة. هو يقترح توافقات للمستخدمين. المستخدمون لا يقولون "أقيم هذا الشخص بـ 8/10". هم فقط يقولون "أفضل الشخص (أ) على الشخص (ب)".

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

5. الاختبار في العالم الحقيقي: توجيه الذكاء الاصطناعي (AI Routing)

أخيراً، اختبروا هذا على النماذج اللغوية الكبيرة (LLMs).

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

الخلاصة الكبرى

هذه الورقة هي دليل لمستقبل الذكاء الاصطناعي في عالم لا يمكننا فيه دائماً الحصول على بيانات مثالية. إنها تخبرنا:

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

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

إليك ملخص تقني مفصل للورقة البحثية بعنوان "التعلم عبر الإنترنت وحساب التوازن باستخدام التغذية الراجعة القائمة على التصنيف" (Online Learning and Equilibrium Computation with Ranking Feedback).

1. تعريف المشكلة

تتناول الورقة مشكلة التعلم عبر الإنترنت في البيئات غير العشوائية (التي قد تكون خصمية/Adversarial) حيث لا يتلقى المتعلم تغذية راجعة رقمية (مثل الدرجات أو المكافآت الدقيقة). بدلاً من ذلك، يلاحظ المتعلم فقط تغذية راجعة قائمة على التصنيف (Ranking Feedback) لمجموعة من الإجراءات المقترحة.

الإعداد: يتفاعل وكيل مع بيئة عبر $T$ من الخطوات الزمنية. في كل خطوة $t$ ، يقترح الوكيل مجموعة من الإجراءات $o(t)$ (إما مجموعة الإجراءات الكاملة في إعدادات المعلومات الكاملة Full-Information أو مجموعة فرعية بحجم $K$ في إعدادات البنديت Bandit).
التغذية الراجعة: تعيد البيئة تبديلاً (Permutation) $\sigma(t)$ يمثل تصنيفاً للإجراءات المقترحة.
نموذج التصنيف: يتم توليد التغذية الراجعة عبر نموذج Plackett-Luce (PL)، المتمثل بمعامل درجة حرارة $\tau$ . يعتمد احتمال التصنيف على متجه المنفعة (Utility vector) الأساسي $r(t)$ .
آليتان للتغذية الراجعة:
1. تصنيف المنفعة اللحظية (InstUtil Rank): تعتمد التصنيفات على المنفعة اللحظية $u(t)$ عند الخطوة الزمنية الحالية. هذا يحاكي مقدمي التغذية الراجعة الذين يعملون بنظام "المرة الواحدة" أو غير المطلعين على الماضي.
2. تصنيف متوسط المنفعة (AvgUtil Rank): تعتمد التصنيفات على متوسط المنفعة الزمني حتى الخطوة الزمنية الحالية ( $u_{avg}^{(t)} = \frac{1}{t}\sum_{s=1}^t u(s)$ ). هذا يحاكي مقدمي التغذية الراجعة الذين لديهم ذاكرة (مثل المستخدمين طويلي الأمد).
الهدف: تقليل الندم الخارجي (External Regret) (الفرق بين المنفعة التراكمية للوكيل وأفضل إجراء ثابت في الماضي) وفي الإعدادات النظرية للألعاب، حساب توازن الارتباط الخشن (Coarse Correlated Equilibrium - CCE) التقريبي.

2. المساهمات الرئيسية والمنهجية

يضع المؤلفون حدوداً أساسية لما يمكن تحقيقه ويقترحون خوارزميات جديدة للتغلب على هذه الحدود تحت شروط محددة.

أ. نتائج الصعوبة (نظريات الاستحالة)

تثبت الورقة أن الندم دون الخطي (Sublinear Regret) مستحيل بشكل عام دون افتراضات إضافية:

تصنيف المنفعة اللحظية (InstUtil Rank): لأي درجة حرارة ثابتة $\tau$ ، يستحيل تحقيق ندم دون خطي في كل من إعدادات المعلومات الكاملة وإعدادات البنديت. يمكن للخصم بناء تسلسلات منفعة تنتج توزيعات تصنيف متطابقة ولكن بمنفعات متوقعة مختلفة، مما يؤدي إلى ندم خطي.
تصنيف متوسط المنفعة (AvgUtil Rank):
- في إعداد المعلومات الكاملة، إذا كانت $\tau$ صغيرة بما يكفي ( $\tau \le O(\frac{1}{T \log T})$ )، يستحيل تحقيق ندم دون خطي.
- في إعداد البنديت، إذا كانت $\tau$ صغيرة ( $\tau \le O(\frac{1}{\log T})$ )، يستحيل أيضاً تحقيق ندم دون خطي.
- رؤية: عندما تقترب $\tau$ من الصفر، يصبح التصنيف حتمياً (اختيار المنفعة الأعلى دائماً). في البيئات الخصمية، تمنع هذه العشوائية المفقودة المتعلم من التمييز بين متجهات المنفعة التي تسبب نفس التصنيف ولكن بنتائج تراكمية مختلفة.

ب. الحلول الخوارزمية

لتحقيق ندم دون خطي، يقدم المؤلفون افتراض التباين دون الخطي (Sublinear Variation) في تسلسل المنفعة (الافتراض 5.2): $\sum_{t=2}^T \|u(t) - u(t-1)\| \le O(T^q)$ حيث $q < 1$ .

المنهجية الجوهرية: تقدير المنفعة عبر التفكيك الثنائي (Pairwise Decomposition)
بما أن نموذج PL غير محدب (Non-convex)، طور المؤلفون أوراكل لتقدير المنفعة (الخوارزمية 1) مبتكراً:

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

خوارزميات محددة:

لتصنيف المنفعة اللحظية (الخوارزمية 2):
- تستخدم مُقدر المنفعة لتوليد متجه عددي $\hat{u}(t)$ .
- تغذي هذا المتجه $\hat{u}(t)$ في أوراكل قياسي لا يسبب ندماً (مثل FTRL أو PGD).
- إعداد البنديت: تضيف حداً للاستكشاف (توزيع موحد) لضمان عينة كافية من جميع الإجراءات.
- النتيجة: تحقق ندماً دون خطي تحت افتراض التباين دون الخطي.
لتصنيف متوسط المنفعة (الخوارزمية 3):
- المعلومات الكاملة: تقوم بتقدير متوسط المنفعة الزمني مباشرة. ومن المهم أن المؤلفين يوضحون أنه إذا كان الأوراكل الأساسي مستقراً (يحقق الافتراض 7.1، مثل FTRL مع التحدب القوي)، فإن افتراض التباين دون الخطي ليس مطلوباً. تحقق الخوارزمية ندماً دون خطي حتى مع وجود تغيرات عشوائية في المنفعة.
- البنديت: تقدير متوسط المنفعة الزمني أصعب لأن التغذية الراجعة تعتمد على المتوسط التجريبي للإجراءات التي تم أخذ عينات منها. يقدم المؤلفون استراتيجية تقدير قائمة على الكتل (Block-based estimation) (تقسيم الوقت إلى كتل بحجم $M$ ) للموازنة بين الانحياز والتباين. وهذا يتطلب افتراض التباين دون الخطي مع $q < 1/3$ .

ج. حساب التوازن

توسع الورقة هذه النتائج لتشمل الألعاب ذات الصيغة العادية (Normal-Form Games - NFG):

إذا استخدم جميع اللاعبين في لعبة متكررة الخوارزميات المقترحة، فإن متوسط استراتيجيتهم المشتركة الزمني يتقارب نحو توازن ارتباط خشن (CCE) بقيمة $\epsilon$ .
يعتمد معدل التقارب على حدود الندم المستمدة من إعداد التعلم أحادي الوكيل.
ملاحظة: حتى عندما تقترب $\tau$ من الصفر (حيث يكون التعلم عبر الإنترنت صعباً)، يظل حساب التوازن ممكناً لأن التصنيف الحتمي يكشف عن أفضل استجابة، مما يقلل المشكلة فعلياً إلى اللعب الزائف (Fictitious Play)، والذي يتقارب في أنواع معينة من الألعاب.

3. النتائج الرئيسية والحدود النظرية

الإعداد	نوع التغذية الراجعة	الافتراض المطلوب	حد الندم
تصنيف المنفعة اللحظية	معلومات كاملة / بنديت	تباين دون خطي ( $P(T) \le O(T^q)$ )	دون خطي (مثلاً $O(T^{2/3})$ )
تصنيف متوسط المنفعة	معلومات كاملة	لا يوجد (إذا كان الأوراكل مستقراً)	دون خطي (مثلاً $O(T^{5/3} L)$ )
تصنيف متوسط المنفعة	بنديت	تباين دون خطي ( $q < 1/3$ )	دون خطي (مثلاً $O(T^{4/9})$ )
عام	أي نوع	$\tau$ صغيرة (حتمية)	ندم خطي (صعوبة)

الصعوبة: توفر الورقة حدوداً دنيا دقيقة تظهر أنه بدون افتراض التباين (أو مع $\tau$ صغيرة جداً)، يكون الندم هو $\Omega(T)$ .
متوسط المنفعة (معلومات كاملة): مساهمة نظرية هامة هي إظهار أنه بالنسبة لتصنيف متوسط المنفعة في المعلومات الكاملة، يمكن إزالة افتراض التباين دون الخطي تماماً، بشرما كان أوراكل التعلم مستقراً.

4. التحقق التجريبي

يتحقق المؤلفون من نهجهم باستخدام مهمة توجيه النماذج اللغوية الكبيرة (LLM) عبر الإنترنت:

السيناريو: يقوم خادم بتوجيه استفسارات المستخدمين إلى نماذج لغوية كبيرة مختلفة (مثل GPT-4o، Llama-3، Phi-4) بناءً على تفضيلات المستخدم.
التغذية الراجعة: يقوم المستخدمون بتصنيف الاستجبات المولدة بدلاً من تقديم درجات رقمية.
الإعداد: يستخدم النظام الخوارزمية 3 مع تصنيف متوسط المنفعة تحت تغذية بنديت الراجعة.
النتيجة: ينخفض متوسط الندم بمرور الوقت، مما يثبت أن الموجه (Router) ينجح في توجيه الاستفسارات إلى النموذج الأمثل للمستخدم المحدد، حتى مع وجود تفضيلات غير مستقرة وتغذية راجع قائمة على التصنيف فقط.

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

الربط بين RLHF والتعلم عبر الإنترنت: يضفي هذا العمل طابعاً رسمياً على الانتقال من التعلم المعزز من التغذية الراجعة البشرية (RLHF)، الذي غالباً ما يستخدم بيانات التصنيف غير المتصلة (Offline)، إلى الإعدادات عبر الإنترنت (Online) حيث يجب اتخاذ القرارات بشكل متسلسل مع تغذية راجعة محدودة.
الحدود النظرية: تحدد الورقة بدقة حدود التعلم باستخدام التغذية الراجعة القائمة على التصنيف، موضحة أن التصنيفات "الحتمية" في البيئات الخصمية هي في الأساس غير قابلة للتعلم دون افتراضات هيكلية (مثل انخفاض التباين).
نظرية الألعاب: توفر آلية جديدة لحساب التوازنات في الألعاب حيث يلاحظ اللاعبون التفضيلات النسبية (التصنيفات) بدلاً من العوائد الدقيقة، وهو أمر أكثر واقعية في الأنظمة التي تتضمن بشراً في الحلقة (Human-in-the-loop).
الابتكار الخوارزمي: يوفر التقدير المقترح للمنفعة عبر التفكيك الثنائي والمتوسط القائم على الكتل إطاراً قوياً لتحويل التغذية الراجعة الترتيبية (Ordinal) إلى تقديرات رقمية قابلة للتنفيذ لخوارزميات التحسين القياسية.

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