📊 statistics

Adaptive Bandit Algorithms for Contextual Matching Markets

تقترح هذه الورقة خوارزميات "بانديت" (bandit) تكيُّفية لأسواق المطابقة السياقية ذات المنفعات الخطية، محققةً ندمًا لوغاريتميًا متعدد المرات يعتمد على الحالة في السياقات العشوائية، وندمًا دون خطي غير معتمد على الحالة في السياقات التنافسية، وذلك من خلال معالجة عدم الاستقرار الناتج عن التحولات السياقية الطفيفة.

المؤلفون الأصليون: Shiyun Lin, Simon Mauras, Vianney Perchet, Nadav Merlis

نُشر 2026-05-28

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

CC BY 4.0

المؤلفون الأصليون: Shiyun Lin, Simon Mauras, Vianney Perchet, Nadav Merlis

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

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

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

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

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

إليك تفصيل حلهم، باستخدام تشبيهات بسيطة:

1. نوعا الأسواق

أدرك المؤلفون أن الأسواق تتصرف بطريقتين مختلفتين تماماً، لذا بنوا استراتيجيتين مختلفتين.

سوق "الطقس" (السياقات العشوائية - Stochastic Contexts):
تخيل أن أوصاف الوظائف تشبه الطقس. لا يمكنك التنبؤ بدرجة الحرارة الدقيقة غداً، لكنك تعرف وجود نمط ما. ربما وظائف "التصميم الجرافيكي" عادة ما تكون ميزانيتها بين 500 و1000 دولار. تفترض الخوارزمية أن هذه الدلائل تأتي من توزيع خفي ومتسق. الأمر يشبه تعلم المناخ المحلي: قد تحصل على يوم ممطر، لكنك تعرف النمط العام.
- التحدي: أحياناً، قد تبدو وظيفتان متشابهتين تماماً تقريباً. إذا لم تستطع الخوارزمية التمييز بينهما، فقد ترتكب خطأً. تقدم الورقة طريقة جديدة لقياس مدى "صعوبة" السوق من خلال النظر إلى أصغر فرق بين خيارين للوظائف. إذا كان الفرق ضئيلاً، يكون التعلم صعباً؛ وإذا كان كبيراً، يكون التعلم سهلاً.
- الحل: بنوا خوارزمية تسمى BARB (الموازنة التكيفية للندم بالدفعات - Batched Adaptive Regret-Balancing). فكر في BARB كمدير ذكي يعمل بنظام "الدفعات".
  - المرحلة 1 (الاستكشاف): يحاول المدير تجربة اقترانات مختلفة لجمع البيانات، مثل عالم يجري تجارب علمية.
  - المرحلة 2 (الاستغلال): بمجرد أن يثق المدير في البيانات، يبدأ في إجراء أفضل المطابقات الممكنة.
  - السر السحري: إذا أدرك المدير أن البيانات لا تزال غير واضحة (الوظائف تبدو متشابهة جداً)، فإنه يقلل من ثقته ويعود إلى المرحلة الأولى. إنه يوازن بشكل تكيفي بين "التعلم" و"التنفيذ" دون الحاجة لمعرفة قواعد اللعبة مسبقاً.
سوق "الفوضى" (السياقات العدائية - Adversarial Contexts):
الآن، تخيل سوقاً حيث تُكتب أوصاف الوظائف بواسطة شخص مخادع. ربما يقوم عميل بتغيير وصف الوظيفة كل يوم فقط لإرباك العمال، أو أن السوق متقلب للغاية بحيث لا يوجد نمط على الإطلاق.
- التحدي: في هذا السيناريو، لا يمكنك الاعتماد على الأنماط. إذا حاولت تعلم "الحد الأدنى من الفرق" بين الوظائف، يمكن للمخادع جعل هذا الفرق صفراً للأبد، مما يؤدي لكسر الخوارزميات القياسية.
- الحل: أدرك المؤلفون أنه في السوق الفوضوية، لا يمكنك الوعد بـ "مطابقة مثالية". بدلاً من ذلك، اقترحوا هدفاً جديداً: الاستقرار التقريبي (Approximate Stability).
- فكر في الأمر كالتالي: إذا كانت الوظائف مربكة لدرجة أنك لا تستطيع التمييز بين "وظيفة رائعة" و"وظيفة جيدة"، فإن الخوارزمية لا تصاب بالذعر. بل تقول: "حسناً، سأعطيك وظيفة قريبة جداً من الأفضل". لقد بنوا خوارزمية تسمى AdECO تنتقل بين محاولة إيجاد المطابقة المثالية (عندما تكون الأمور واضحة) والاستقرار على مطابقة "جيدة بما يكفي" (عندما تكون الأمور فوضوية).

2. مفهوم "الندم" (Regret)

في هذا المجال، "الندم" هو كلمة منمقة تعني "الفرصة الضائعة".

إذا كان بإمكان العامل كسب 100 دولار ولكنه كسب 80 دولاراً فقط لأن الخوارزمية اختارت الوظيفة الخاطئة، فهذا يعني أن لديه 20 دولاراً من الندم.
الهدف من هذه الخوارزميات هو تقليل هذا الندم بمرور الوقت. إنهم يريدون للعمال كسب ما يقرب من "السيناريو المثالي" حتى أثناء مرحلة التعلم.

3. لماذا يهم هذا الأمر (وفقاً للورقة)

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

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

ملخص التشبيه

تخيل أنك "خاطبة" (Matchmaker) في حفلة.

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

تقدم الورقة البرهان الرياضي على أن هؤلاء "الخاطبين الأذكياء" (الخوارزميات) سيتعلمون في النهاية القيام بعمل رائع، سواء كان السوق قابلاً للتنبؤ أو فوضوياً تماماً.

ملخص تقني: خوارزميات "بانديت" التكيفية لأسواق المطابقة السياقية

صياغة المشكلة

تبحث هذه الورقة في مشكلة المجموعات السياقية متعددة الأذرع (Contextual Multi-armed Bandits) في أسواق المطابقة ثنائية الجانب. يتكون السوق من $N$ من اللاعبين و $K$ من الأذرع (حيث $N \le K$ ). يكمن التحدي الجوهري في الطبيعة الديناميكية لتفضيلات اللاعبين، والتي يتم نمذجتها عبر دالة منفعة سياقية خطية: $U_{i,j}(t) = \theta_i^\top x_j(t)$ . هنا، يمثل $\theta_i$ متجه تفضيلات ثابت وغير معروف للاعب $i$ ، بينما يمثل $x_j(t)$ متجه سياق مرصود للذراع $j$ عند الزمن $t$ .

على خلاف الإعدادات التقليدية ذات التفضيلات الثابتة، يتغير السياق $x_j(t)$ بمرور الوقت، مما قد يؤدي إلى تغيير المعيار المستقر للمطابقة. الهدف هو تصميم خوارزمية عبر الإنترنت (online algorithm) لمطابقة اللاعبين بالأذرع لتقليل الندم المستقر الأمثل للاعب (player-optimal stable regret). ويُعرف هذا الندم بأنه الفرق التراكمي بين المنفعة التي يحصل عليها اللاعب تحت مطابقة الخوارزمية والمنفعة التي كان سيحصل عليها تحت المطابقة المستقرة المثلى للاعب (أفضل مطابقة مستقرة لذلك اللاعب) بناءً على المنافع الحقيقية في كل جولة.

تتناول الورقة إعدادين متميزين فيما يتعلق بتوليد السياق:

السياقات العشوائية (Stochastic Contexts): حيث تُسحب السياقات بشكل مستقل وموزع بشكل متماثل (i.i.d.) من توزيع ثابت ولكن غير معروف.
السياقات العدائية (Adversarial Contexts): حيث يمكن أن تكون السياقات تعسفية ويمكن اختيارها من قبل خصم متكيف، مما يمثل بيئات غير مستقرة في أسوأ الحالات.

المنهجية

يقترح المؤلفون خوارمازميات تكيفية بالكامل لا تتطلب معرفة مسبقة بفجوة التفضيل الدنيا أو بنية التغاير (covariance structure) للسياقات. تستخدم كلتا الخوارزميتين مخطط انتقال طوري متكيف بنظام الدفعات (batched adaptive phase transition scheme)، حيث تتناوب بين الاستكشاف (تحسين تقديرات المعلمات) والاستغلال (إجراء مطابقات مستقرة).

1. الإعداد العشوائي: موازنة الندم التكيفية بالدفعات (BARB)

بالنسبة للإعداد العشوائي، تقدم الورقة خوارزمية BARB، التي تعمل بنظام الدفعات.

تقدير الفجوة التكيفي: تحافظ الخوارزمية على فجوة تفضيل دنيا مرشحة $\Delta_k$ ، تبدأ بقيمة مدخلة ثم تتقلص بعامل $\sqrt{2}$ في كل دفعة تالية. يسمح هذا للخوارزمية بالتقريب التكيفي لصعوبة المشكلة الحقيقية دون معرفة الفجوة الحقيقية مسبقاً.
الاستكشاف مقابل الاستغلال:
- الاستكشاف: إذا تجاوز معيار ماهالانوبيس لمتجه السياق $\|x_j(t)\|_{V_i(t)^{-1}}$ عتبة $\xi_k$ ، تدخل الخوارزمية في مرحلة استكشاف. تقوم الخوارزمية ببناء رسم بياني ثنائي الأجزاء للأزواج ذات عدم اليقين العالي وتجري مطابقة قصوى للعدد (Maximum Cardinality Matching) لجمع عينات معلوماتية لتحديثات انحدار ريدج (ridge regression).
- الاستغلال: إذا كان عدم اليقين منخفضاً، تستخدم الخوارزمية خوارزمية جال-شابلي (GS) بناءً على المنافع المقدرة. كما تراقب تداخل فترات الثقة للمنافع المقدرة؛ فإذا كانت التداخلات مفرطة (مما يشير إلى أن تقدير الفجوة الحالي $\Delta_k$ كبير جداً)، تنتهي الدفعة، وتنتقل الخوارزمية إلى الدفعة التالية مع تقدير أصغر للفجوة.
الضمانات النظرية: تحت فرضيات بسيطة، تحقق BARB حداً أعلى للندم يعتمد على الحالة من النوع $\tilde{O}(\log^2 T / \Delta_{\min}^2)$ . علاوة على ذلك، في حال تحقق شرط أن مصفوفة تغاير السياق تمتلك قيمة ذاتية دنيا موجبة تماماً، يتحسن الحد إلى $O(\log T / \Delta_{\min}^2)$ . وفي النظام التقاربي، تثبت الورقة حداً أدنى للندم غير معتمد على الحالة من النوع $\tilde{\Theta}(T^{2/3})$ .

2. الإعداد العدائي: أوراكل الاختيار الاستكشافي المتكيف (AdECO)

بالنسب بالنسبة للإعداد العدائي، تصبح تعريفات الندم القياسية غير قابلة للحل لأن الخصم يمكنه إجبار الحد الأدنى لفرق المنفعة $\delta_{\min}$ على أن يكون صغيراً جداً لفترات طويلة جداً.

تعريف الندم القابل للحل: تقترح الورقة مفهوماً منقحاً للندم يقوم بالاستكمال بين الفجوات الكبيرة والصغيرة. عندما تكون $\delta_{\min}(t) > \Delta$ ، يكون المعيار هو الحصة المستقرة المثلى للاعب $U^*_i(t)$ . وعندما تكون $\delta_{\min}(t) \le \Delta$ ، يكون المعيار هو تقريب $\alpha$ للحصة المستقرة $\epsilon$ -المثلى $U^\epsilon_i(t)$ ، باستخدام أوراكل تقريب خارجي (offline approximation oracle).
تصميم الخوارزمية: تتبع AdECO هيكلاً تكيفياً مشابهاً لـ BARB.
- في مرحلة الاستكشاف، تستخدم مطابقة قصوى للعدد لتقليل عدم اليقين.
- في مرحلة الاستغلال، إذا كانت فترات الثقة متباعدة جيداً، تستخدم خوارزمية جال-شابلي. أما إذا تداخلت (مما يشير إلى فجوات صغيرة)، فإنها تستدعي أوراكل تقريب $\alpha$ (بناءً على Lin et al., 2026) لتوليد مطابقة عشوائية تضمن كسرًا من الحصة المستقرة المثلى.
الضمانات النظرية: تحقق AdECO حداً أدنى للندم غير معتمد على الحالة من النوع $O(T^{2/3})$ من خلال ضبط المعلمة الخوارزمية $\Delta = O(T^{-1/3})$ .

3. الامتداد اللامركزي

توسع الورقة باختصار إطار عمل BARB ليشمل الأسواق اللامركزية حيث يعمل اللاعبون بشكل مستقل دون منسق مركزي. من خلال إدخال افتراض حول تحديد البيئة (ترتيبات الـ top- $N$ متميزة للبيئات المختلفة)، تحقق الخوارزمية اللامركزية نفس رتبة الندم كالنسخة المركزية، مع حد إضافي ثابت يعتمد على عدد البيئات.

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

مقاييس مبتكرة لصعوبة المشكلة:
- بالنسبة للسياقات العشوائية، تقدم الورقة فجوة تفضيل دنيا ( $\Delta_{\min}$ )، تُعرّف احتماليًا لالتقاط احتمالية وجود فروق منفعة صغيرة، مما يوفر مقياساً أكثر واقعية من الحدود الدنيا الحتمية المستخدمة في الأعمال السابقة.
- بالنسبة للسياقات العدائية، تحدد مفهوم ندم قابل للحل ينتقل بين معايير المطابقة المستقرة الدقيقة ومعايير التقريب اعتماداً على حجم الفجوة، مما يتيح ضمانات ذات معنى في السيناريوهات الأسوأ.
خوارزميات تكيفية بالكامل:
- الخوارزميات المقترحة (BARB و AdECO) هي خوارزميات تكيفية بالكامل، لا تتطلب معرفة مسبقة بفجوة التفضيل الدنيا أو بنية تغاير توزيع السياق. فهي تعدل تلقائياً مقايضات الاستكشاف والاستغلال بناءً على البيانات المرصودة.
حدود نظرية محكمة:
- العشوائي: توفر الورقة حدوداً عليا للندم تعتمد على الحالة من النوع poly-logarithmic، وتحت فرضية تغاير بسيطة، توفر حدوداً لوغاريتمية. والأهم من ذلك، أنها تثبت حداً أدنى مطابقاً غير معتمد على الحالة من النوع $\Omega(T^{2/3})$ ، مما يثبت دقة المعدل التقاربي.
- العدائي: تحقق حداً أدنى للندم غير معتمد على الحالة من النوع $O(T^{2/3})$ للمقياس المقترح للندم القابل للحل.
التكيف اللامركزي: توضح الورقة كيف يمكن تكييف هذه الآليات التكيفية مع الإعدادات اللامركزية بأقل قدر من الافتراضات الإضافية.

النتائج والأهمية

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

المتانة: تسمح الطبيعة التكيفية للخوارزميات المقترحة بالتعامل مع أي هياكل تغاير سياقي (في الحالة العشوائية) وأي تسلسلات سياقية (في الحالة العدائية)، مما يجعلها تتفوق على النماذج غير التكيفية مثل ETC (الاستكشاف ثم الالتزام) في السيناريوهات التي يكون فيها توزيع السياق ضعيف التكييف (مثل القيم الذاتية الدنيا الصغيرة).
الدقة النظرية: يوفر اشتقاق الحدود العليا والدنيا المتطابقة ( $\tilde{\Theta}(T^{2/3})$ ) للندم غير المعتمد على الحالة في الإعداد العشوائي فهماً جوهرياً لصعوبة المطابقة السياقية مع تفضيلات غير معروفة.
القابلية للتطبيق العملي: من خلال إزالة الحاجة إلى معرفة مسبقة بتوزيع البيئة أو بارامترات الفجوة، فإن الخوارزميات تعد أكثر ملاءمة للتطبيقات الواقعية مثل أسواق العمل عبر الإنترنت، وتطبيقات مشاركة الركوب، ومطابقة الإقامة الطبية، حيث تكون ديناميكيات التفضيل وتوزيعات السياق غالباً غير معروفة وغير مستقرة.

يخلص المؤلفون إلى أنه بينما يفترض الإطار الحالي منافع سياقية خطية، فإن الآليات التكيفية التي تم تطويرها توفر أساساً متيناً للعمل المستقبلي في هياكل سوق أكثر تعقيداً.