من الـ one-armed bandit لترتيب ما بتقدر تقيسه

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

يعني تخيّل لو في خمس مطاعم قريبة منك، وانت بدك تعرف أي واحد فيهم ممتاز عشان تعزمني عليه. طبعا لازم تبيّض وجهك مع الضيف. لو كان عندك تقييم دقيق لكل مطعم، الموضوع بيكون سهل: مطعم المشاوي 4.8، التركي 4.3، الإيطالي 4.1، وهكذا. بنرتّب المطاعم حسب التقييم، وبنختار الأعلى، وخلصنا.

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

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

هون بدل ما تكون المسألة “رتّب الأرقام وخذ الأعلى”، بتصير: “كيف أكتشف أي مطعم هو الأفضل، من غير ما أدفع تمن كتير بتجارب مؤلمة؟”

هاد السؤال هو قلب البوست. بالبداية رح نحكي عنه بأبسط نسخة: عندك كذا خيار، بتقدر تجرّب خيار واحد كل مرة، وبدك تتعلم من التجربة بدون ما تضيع محاولاتك كلها على اختيارات سيئة. بعدين رح نكبر نفس الفكرة شوي شوي. شو بصير لو القرار مش مطعم واحد، بل طريق كامل بمدينة، وكل شارع عنده وقت سفر مش أكيد؟ شو بصير لو بدك توفّق بين زبون وخبير، وجودة الـ match ما بتبين إلا بعد التجربة؟ شو بصير لو القرار مش اختيار عنصر واحد، بل اختيار مجموعة كاملة من العناصر مع بعض؟

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

بس قبل كل هاد، خلينا نلاقي أفضل مطعم.

الفكرة اللي بتربط كل شي ما بتتغيّر: explore مقابل exploit — وين أصرف محاولتي الجاية؟

الجزء الأول — الـ one-armed bandit: نختار العشا

مشكلة العشا هاي هي بالضبط الـ multi-armed bandit: اختار خيار واحد، شوف نتيجة وحدة فيها ضجيج، عدّل توقّعك، وكرّر. الجزء الصعب مش الاختيار نفسه — الصعب إنك تقرّر قدّيش عشا سيّء مستعدّ تدفع تمنه لتتعلّم أي مطعم هو فعلاً الأفضل.

المصطلحات هي قصة المطاعم بصيغة تانية. كل مطعم هو arm. والزيارة هي pull. والـ reward هو إذا كانت الليلة منيحة لدرجة إنك بترجعله. انت بتعمرك ما بتشوف المعدّل الحقيقي لجودة المطعم — بس بتشوف عشا واحد فيه ضجيج بالمرّة، وبس للمطعم اللي اخترته. الباقيين بيضلّوا احتمالات: ما رح تعرف أبداً شو فاتك.

لما تقدر تقرا الأرقام، المسألة مملّة

لو عطيتك خمس علامات لخمس مطاعم — 0.3، 0.7، 0.5، 0.4، 0.6 — و«لاقي الأفضل»، بتمشّي عليهم بخمس خطوات وخلصنا. النسخة المثيرة هي اللي بتخبّي عنك العلامات. كل عشا هو عيّنة فيها ضجيج لجودة ما بتشوفها: يمكن الشيف كان بمزاج منيح هاليلة، يمكن انت طلبت غلط. الزيارة الوحدة بتعطيك إشارة، بس مش كفاية. وعندك مية عشا — أو عشرة آلاف. رتّبهم.

تمن إنك ما بتعرف: الـ regret

هاد شكل أي قرار بيتكرّر تحت عدم اليقين — وين ناكل، أي عنوان إيميل نبعت، أي widget نعرض. بالصيغة الرسمية: عندك $k$ من الـ arms، كل واحد إله توزيع reward مخفي؛ كل جولة بتعمل pull واحد؛ بتشوف reward فيه ضجيج؛ والهدف تعظّم مجموع الـ reward. أو بصيغة تانية، تقلّل الـ regret — وهو الفرق بينك وبين oracle بيلعب دايماً الـ arm الأفضل:

$\text{Regret}(T) = \sum_{t=1}^{T}\big(\mu^* - \mu_{a_t}\big), \qquad \mu^* = \max_i \mu_i$

الـ regret هو الجودة اللي خلّيتها وراك. لو كان Sushi هو فعلاً الأفضل وانت أكلت بمطعم أضعف هاليلة، الفرق بين المعدّلين المخفيين هدول هو الـ regret المتوقّع لليلتك. وهون المأزق: ما بتقدر تلتزم بالـ arm الأفضل بعد كم pull (التقديرات الأولى فيها ضجيج، وكتير بتختار الغلط)، بس برضو ما بتقدر تستكشف بالتساوي للأبد (كل جولة على arm سيّء هي regret ما بيرجع). كل خوارزمية هي مجرّد طريقة معيّنة لتقسيم محاولاتك بين إنك تكتشف وإنك تستفيد.

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

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

تلت سياسات بتغطّي معظم الصورة

الدرس المفاجئ من البداية: السياسات اللي شكلها ساذج بتشتغل بشكل ممتاز، والذكية بتتفوّق بفرق أقل مما بتتوقّع.

ε-greedy. العب الأفضل-لهسّا 90% من الوقت؛ والـ 10% الباقية العب arm عشوائي. العشوائية هي الضريبة اللي بتحميك من إنك تعلق على تخمين أوّلي غلط. صعب تخرّبها، بس بتضل تضيّع هالـ 10% حتى بعد ما يصير الفائز واضح.
UCB1 — التفاؤل وقت ما تكون مش متأكّد. قيّم كل arm بـ $\hat{\mu}_i + \sqrt{2\ln t / n_i}$ والعب الأعلى: اللي بتعرفه، زائد قدّيش ممكن تكون غلطان. الـ arms اللي جرّبتها قليل بتاخد bonus بيصغر كل ما تجرّبها أكتر، فبيصير الاستكشاف موجّه نحو عدم اليقين الحقيقي بدل ما يكون موزّع بالتساوي.
Thompson sampling — مطابقة الاحتمال. احتفظ بتوزيع توقّع لكل arm (توزيع Beta لمكافآت فوز/خسارة)؛ كل جولة اسحب عيّنة وحدة من كل توزيع والعب صاحب أعلى سحبة. الـ arm اللي جرّبته قليل إله posterior واسع، فبيطلع له أحياناً رقم عالي وبينستكشف؛ والـ arm المعروف إنه سيّء إله posterior ضيّق ومنخفض وبالكاد بيفوز. الاستكشاف بيخفّ من حاله. ونتيجته ممتازة عملياً.

لاحظ المشترك بيناتهم: الـ loop صغير — ابدأ كل arm بـ prior ضعيف، اختار، اعمل pull، عدّل هالـ arm بس، وكرّر. الفرق الوحيد بين الخوارزميات هو كيف بتترجم «التقدير زائد عدم اليقين» للـ pull الجاي.

سابق بين ε-greedy و UCB و Thompson على سيناريو hard (أعلى arm-ين شبه متعادلين)، وبعدين سابق ε-greedy ضد pure exploit على balanced. القصة بتحكي عن حالها: الـ pure-exploit بيلتزم بالـ arm الغلط تقريباً بنفس عدد المرات اللي بيلتزم فيها بالصح؛ و ε-greedy بيتفوّق عليه لأن ضريبة الـ 10% العشوائية أرخص من إنك تثبّت على غلطة؛ و UCB و Thompson بيتفوّقوا على ε-greedy لأن استكشافهم موجّه؛ و UCB و Thompson بيتبادلوا الصدارة بفرق بسيط فيه ضجيج — الـ bandits مش المكان اللي رح تلاقي فيه ميزتك.

ملاحظة على «UCB بطيء»: مش بطيء بمعنى الـ CPU — هو index واحد لكل arm. البطء اللي بتحسّه هو بطء تعلّم. الـ bonus تبع UCB1، وهو $\sqrt{2\ln t / n_i}$ ، هو نصف قطر ثقة آمن بقصد (Hoeffding) بيشتغل مع أي reward محدود، فبيضل يعيد فحص arms كانت طريقة أذكى رح تتجاهلها بدري. بالإنتاج الناس بتستعمل نسخ أضيق (KL-UCB، UCB-Tuned)، أو Thompson لما يكون عندنا نموذج reward بايزي مناسب.

جرّبه بإيدك — اضغط على مطعم لتاكل فيه الليلة، وتابع خط الـ regret تبعك وهو بيطلع مقابل bot بيشتغل بـ Thompson وعم ياكل بالتوازي معك. مية عشا بإيدك بتكفّي لتحسّ قدّيش صعب تتغلّب على الاستكشاف الموجّه بالحدس لحالك.

الـ context بيغيّر مين هو الـ arm الأفضل

في تفصيل تاني من الواقع: أفضل عشا بيعتمد على الليلة نفسها. غدا سريع، وليلة موعد، وعشا لحالك بيوم شتوي — كل وحدة context مختلفة. الـ bandit العادي بيتعلّم معدّل عام واحد لكل مطعم؛ أما الـ contextual bandit فبيشوف ميزات الموقف الأول، وبعدين بيختار. والـ LinUCB هو UCB بلمسة إضافية — بدل معدّل واحد لكل arm، كل arm بيتعلّم أوزان $\theta_a$ على متّجه الـ context $x_t$ ، بيتوقّع $x_t^\top \theta_a$ ، وبيضيف نفس الـ bonus تبع التفاؤل فوقها. نفس المطعم ممكن يكون خيار سيّء للغدا وممتاز بليلة شتوية لحالك.

الخلاصة بجملة وحدة

شوية ذكاء بتربح كتير؛ وذكاء أكتر بتربح شوي. الـ ε-greedy و UCB و Thompson نقاط على نفس المنحنى الناعم، وأي وحدة فيهم أفضل بكتير من إنك تلتزم بدري أو ما تلتزم أبداً. المشكلة الكلاسيكية محلولة عملياً.

بس هي مشكلة محدّدة كتير: $k$ من الـ arms المستقلة، pull واحد كل جولة، و reward بتشوفه فوراً. الجزء المثير بيبدأ لما هالبنية تنكسر — لما الـ «arm» اللي بتسحبه يصير زوج عناصر، والشي الوحيد اللي بتتعلّمه هو مين الأكبر. هاد هو الترتيب تحت الضجيج، ولهون رايحين.

الجزء الثاني — الترتيب: لما يصير الـ arm زوج

تمن لاعبين، وما في ورقة إحصائيات. ما بتقدر تقرا مهارة حدا؛ كل اللي فيك تعمله إنك تخلّي اثنين يلعبوا وتتفرّج مين فاز — والمباراة الوحدة هي قرعة موزونة حسب فرق المهارة. قدّيش مباراة بدّك لحتى يزبط جدول الدوري، ومين المفروض تنزّله يلعب؟

المهارة الحقيقية المخفية على اليسار، والتقدير على اليمين. اضغط اكشف المهارة الحقيقية بأي وقت لتشوف قدّيش الجدول قريب من الصح. غيّر الـ scheduler لتقرّر مين بيلعب — أو خلّيه على انت الكشّاف وشغّل المباريات بإيدك.

هاد ترتيب (sorting) — بس الـ oracle اللي بيقارن إلك مش موثوق. بالكتاب، بترتّب لما تقرا الأرقام. هون الطريقة الوحيدة لمقارنة لاعبين هي إنك تعمل مباراة، والأفضل بس غالباً بيفوز. الترتيب تحت oracle متل هيك اسمه مشكلة الـ noisy comparison (أو الـ dueling-bandit)، وهي بتحوّل السؤال من «شو الترتيب؟» لـ «وين أصرف مبارياتي؟».

رح نبنيها بتلت خطوات: نموذج الضجيج (كيف المباراة بتصير دليل)، والـ estimator (كيف المباريات بتصير ترتيب)، والـ scheduler (أي مباراة نلعب بعدين) — وبعدها نشوف ليش نسخة الـ bandit اللي بتهتمّ بالقمة بس بتتصرّف بشكل مختلف.

الفصل الأول — الترتيب لما تقدر تقرا الأرقام

Mergesort، quicksort، heapsort: $O(n \log n)$ مقارنة مقابل oracle مضبوط بيقول إلك «x أكبر» بثقة كاملة. الكتاب أغلق هالموضوع سنة 1962. كل مقارنة من غير أي شك، فما بتسأل نفس المقارنة مرتين، وما في شي تقدّره. شيل هالثقة — وكل شي بيتغيّر.

الفصل الثاني — الـ oracle مباراة، مش قياس

هلأ التمن أشياء صاروا لاعبين كورة، أو أنواع نبيد، أو إعلانات، أو لاعبين شطرنج — أي شي إله جودة حقيقية بس ما بتنشاف. ما بتقدر تقرا المهارة؛ بس بتقدر تعمل مباراة، والمباراة فيها ضجيج. المباراة اللي فرقها كبير بتطلع صح دايماً تقريباً؛ والمتقاربة أقرب لقرعة. النموذج لهالقرعة اسمه قانون Bradley-Terry:

$P(i \succ j) = \sigma\!\big(\beta\,(s_i - s_j)\big)$

كل لاعب حامل رقم مخفي واحد $s_i$ (مهارته)؛ و $\sigma$ هي منحنى الـ logistic؛ و $\beta$ قدّيش الرياضة حاسمة. كل الحكاية بالفرق $s_i - s_j$ : مهارة متساوية ( $s_i = s_j$ ) بتعطي قرعة عادلة 50/50؛ والفرق الكبير بيدفع القرعة لنتيجة شبه مؤكّدة. يعني المباراة الوحدة هي عيّنة وحدة فيها ضجيج لفرق زوج واحد — وهاد بالضبط Bernoulli arm. الترتيب تحت الضجيج هو إنك تشغّل $n(n-1)/2$ من هالـ arms بالتوازي، وتسأل عن كل زوج: «على أي طرف رح تقع الفوزة؟».

تمن اليقين بيطلع من هون مباشرة. الزوج اللي فرقه $\Delta$ بدّه حوالي $\log(1/\delta)/\Delta^2$ مباراة متكرّرة لتقدر تحكم عليه بثقة $1-\delta$ . الفروقات الكبيرة بتنحسم بمباراة وحدة؛ الأزواج المتقاربة هي اللي بتاكل الميزانية. انتبه لهالفكرة — هي اللي بتقرّر كل شي بخصوص الجدولة.

كيف الجدول بيتعلّم فعلياً: من fit دفعة وحدة لخطوة وحدة كل مباراة

عنا نتائج مباريات، وبدنا مهارات. في طريقتين، والتانية هي اللي بتكبّر.

الـ batch fit (اللي بيعمله جدول التمن لاعبين). خُد كل المباريات، ودوّر على المهارات اللي بتفسّرها أحسن تفسير — maximum likelihood لنموذج Bradley-Terry. الـ widget بيعملها بكم دورة من نوع minorize-maximize؛ ما إلك دخل بالاشتقاق، يكفي تتخيّل الصورة: بيظبّط مهارة كل واحد لحتى تتطابق نسبة فوزه المتوقّعة مع نسبة فوزه الفعلية. وبعدها الترتيب ببساطة هو اللاعبين مرتّبين حسب المهارة المقدّرة. حلوة، بس إعادة الـ fit من الصفر بعد كل مباراة مستحيلة لما يصير عندك آلاف اللاعبين.

الـ online fit = Elo = خطوة gradient وحدة كل مباراة. اعتبر كل مباراة مثال logistic regression واحد، وخُد خطوة SGD وحدة عليه. لمباراة فاز فيها $i$ على $j$ :

$s_i \leftarrow s_i + \eta\,(1 - p), \qquad s_j \leftarrow s_j - \eta\,(1 - p), \qquad p = \sigma(s_i - s_j)$

هاد هو Elo (والـ step size $\eta$ بيلعب دور الـ $K$ تبع Elo). والحدس وراه حلو: التحديث هو المفاجأة، $1 - p$ . لو فاز المرشّح المتوقّع ( $p \approx 1$ ) المهارات بالكاد بتتحرّك — ما تعلّمت شي جديد. ولو عمل الطرف الأضعف مفاجأة ( $p$ صغير) المهارات بتتأرجح بقوة. النظام بيصحّح حاله لحتى يلحق اللي المباريات بتقوله، $O(1)$ لكل مباراة، بدون إعادة fit.

فالوصفة كلها بعالم الضجيج هي تلت أزرار منفصلة:

قدّر المهارات بـ SGD على المباريات → اقرا الترتيب من ترتيبهم → اختار أي مباراة تنزّل بعدين.

غيّر الـ estimator (batch مقابل Elo) من غير ما تلمس الباقي؛ وغيّر الـ scheduler من غير ما تلمس الـ estimator. الجزئين الجايّين عن هالزرّ التالت — لأن أي مباريات بتطعميها للـ SGD هي اللي بتقرّر قدّيش الترتيب بيتقارب بسرعة.

الفصل الثالث — وين تصرف المباريات

هون بتبيّن فايدة ميزانية الـ $\Delta^2$ . خُد نظرة تانية على خطوة Elo، $\eta(1-p)$ :

المباراة غير المتكافئة ( $p \approx 1$ ) بتعطي خطوة قريبة من الصفر وما بتعيد ترتيب حدا. هي بس بتأكّد اللي بتعرفه أصلاً.
المباراة المتقاربة ( $p \approx \tfrac12$ ) بتعطي خطوة حقيقية و بين لاعبين ترتيبهم فعلاً مش محسوم.

المباريات اللي بتعلّمك هي المتقاربة على الحدود. الـ scheduler المنيح بيصوّب لهناك. أربع سياسات، نفس الدوري، بتتسابق على الشارت تحت:

Random — اختار أي زوج. سهل، بس بيصرف على المباريات المحسومة بقدّ ما بيصرف على القرعات.
Round-robin — العب الزوج الأقل لعباً، $\arg\min_{(i,j)} n_{ij}$ . تغطية عادلة، بس عمياء: بتضل تعيد مباريات محسومة.
Ladder — العب بس اللاعبين اللي بينهم رتبة وحدة على الجدول الحالي. الترتيب مش محسوم بين الجيران، مش بين #1 و #8، فهاد بيصوّب على الحدود — حوالي 1.5× مباريات أقل من random — بس بيثق بترتيب فيه ضجيج لما بيقرّر مين «جنب مين».
Active — العب الزوج الأقرب والأقل استقراراً، $\arg\max_{(i,j)}\big[\text{closeness}(|\hat{s}_i - \hat{s}_j|) + \text{uncertainty}(1/(1+n_{ij}))\big]$ . بيوجّه كل مباراة لوين بتشتري أكبر تحسين بصحّة الجدول.

هاد هو مقايضة الـ explore/exploit بأنقى شكل: مباراة على زوج انت متأكّد منه أصلاً هي استغلال محض بلا معلومة؛ ومباراة على زوج مش محسوم هي استكشاف بيحرّك الجواب فعلاً.

نفس الدوري المخفي للأربعة؛ المنحنى هو Kendall $\tau$ (صحّة الجدول) مقابل عدد المباريات. اللي بيوصل للقمة أوّل بيزبّط الجدول أوّل — واللي بيصوّبوا على الحدود هم اللي بيفوزوا.

هلأ صار دورك تكون الكشّاف

خلّي الـ scheduler تبع الـ hero على انت الكشّاف (اضغط 2) ويصير اختيار المباريات إلك: اضغط على لاعبين لتعمل مباراة، اقرا الجدول، وقرّر مين تجرّب بعدين. رح تحسّ بنفس الجذب اللي بتحسّ فيه الخوارزميات: المباريات الضائعة هي غير المتكافئة؛ واللي بتحرّكك هي القرارات المتقاربة جنب خط القطع تبعك.

ليش لازم تكون بِركة المرشّحين أوسع من K

هلأ افرض إنك ما بدّك كل الترتيب — بدّك بس أفضل K. الإغراء هو إنك تلعب مباريات جوّا الـ top-K الحالي بس. وهاد بيرجع يضربك بتلت طرق، وفهمها هو أهمّ فكرة بالبوست:

انحياز الاختيار (الـ feedback loop). لاعب فعلاً من الـ top-K بس حالياً مقدَّر أقل من حقّه عند رتبة K+1، ما رح ينجدول أبداً، وبالتالي ما رح يطلع أبداً. خلّيت خط فيه ضجيج يقرّر مين بينسمح له يلعب، والخط بيجمّد حاله بمكانه.
Gradients ميتة. جوّا top-K مستقرّ، كل مباراة غير متكافئة ( $p \approx 1$ )، فخطوة Elo $\eta(1-p) \approx 0$ . ما في إعادة ترتيب. المباريات اللي فعلاً بتحرّك خط القطع هي المتقاربة اللي بتقع على طرفيه.
Identifiability مكسورة. مهارات Bradley-Terry/Elo بتكون معرّفة منيح بس طول ما graph الـ «مين لعب مع مين» متّصل. جدول top-K-بس بيفصل مجموعة القمة عن الباقي، فبيفقد «المركز K» مرجعه كلياً.

الحل هو بالضبط الغريزة اللي رح تروح إلها بدوري حقيقي: خلّي بِركة مرشّحين حوالي خط القطع — كل واحد لسا عدم اليقين حوله بيتقاطع مع المركز K — وخلّي البِركة تضيق لما تزيد ثقتك. لو ضيّقة كتير (بس K) بتطلع التلت مشاكل؛ ولو واسعة كتير (كل الميدان) بترجع لـ round-robin، عم تحرق مباريات على نتائج محسومة. البِركة اللي بتضيق هاي هي بالضبط successive elimination: خلّي المرشّحين لحتى تشطبهم الداتا.

التمنية كانوا التمرين. هلأ عشرة آلاف.

مع تمن لاعبين بتقدر تقريباً تلعّب الكل. مع 10,000 ما بتقدر: كل الأزواج $n(n-1)/2 \approx 50$ مليون مباراة. فمنعتمد على الفكرتين فوق. الـ estimator: Elo، تحديث الـ SGD بـ $O(1)$ لكل مباراة، لأن إعادة fit لـ Bradley-Terry على 10 آلاف لاعب كل مباراة مستحيلة. والـ scheduler: adaptive، بيقدّر تقييم المركز K (خط القطع) وبيلعّب لاعبين جنبه — بِركة الحدود، بس على نطاق واسع. والمقياس هو recall@100: قدّيش من الـ top-100 الحقيقي مسكه الـ top-100 المقدّر تبعك.

كل مباراة هي duel Bradley-Terry وحدة فيها ضجيج، محسوبة بـ Elo؛ والـ matchmaking الـ adaptive (أخضر) مقابل random (رمادي) بيتسابقوا على recall@100، والـ scatter بيعرض التقييم المقدّر مقابل المهارة الحقيقية مع خط قطع الـ top-100. الـ random بيضيّع نفسه على المباريات المحسومة البعيدة عن الخط؛ والـ adaptive بيرجّع معظم الـ top-100 بـ عشرات الآلاف من المباريات بدل 50 مليون — وكل هاد لأنه بيصرف ميزانيته بالبِركة حوالي خط القطع.

الجزء الثالث — الـ combinatorial bandits: نختار top-K كاملة

كل شي لهون عايش بعالم واحد: الشي الوحيد اللي بتشوفه هو مين فاز — bit مقارنة. وفي عالم تاني كل شي بتجرّبه بيرجّع إلك رقمه هو: كليك، وقت مشاهدة، علامة benchmark. الـ top-K بيطلع بالعالمين، بس مش نفس المشكلة، وبدهم ماكينات مختلفة.

Feedback مقارنة (كل هالبوست): Bradley-Terry / Elo active sorting. fit للمهارات من «A غلب B»، رتّب، وجدوِل على الحدود.
Feedback مكافأة لكل عنصر: Combinatorial-UCB. هي بالضبط فكرة الـ UCB من الجزء الأول، بس موسّعة من arm واحد لـ slate كاملة. احتفظ لكل عنصر بمعدّل جاري لمكافآته زائد نفس bonus التفاؤل اللي بيكون كبير لما تكون جرّبته قليل، $u_i = \bar{x}_i + \sqrt{c\,\ln t / n_i}$ . كل جولة، اختار الـ top-K حسب $u_i$ (هاد هو الجزء الـ «combinatorial» — حركتك مجموعة K كاملة مش arm واحد)، شوف مكافأة لـ كل واحد من الـ K اللي اخترتهم (feedback «semi-bandit»)، وعدّل هدول بس.

والنقطة المهمة — وهي بيت القصيد: الـ Comb-UCB ما بيقدر يشتغل على «مين فاز». بدّه مكافأة لكل عنصر؛ وعالم الكورة ما بيعطي وحدة أبداً. فالـ panel تحت مش Comb-UCB عم يحل مشكلة الترتيب. هي الماكينتين على نفس جودات العناصر المخفية بس عبر قنوات feedback مختلفة — وحدة بتسحب bits مقارنة، ووحدة بتسحب مكافآت لكل عنصر.

منحنيات معدّلة من تجربة 40 run (N=30، K=5، 1000 جولة). التنين بيوصلوا حوالي 0.90 دقة top-k عند الجولة 1000 — بس قدّيش بسرعة هو اللي بيكشف اللاتماثل: عند الجولة 100 الـ Comb-UCB على 0.80 بينما الـ BT على 0.59، لأن Comb-UCB بيدوق خمس مكافآت كل جولة بينما BT بيطلّع bit مقارنة واحد (الـ «feedback / round: 1 vs 5» بالـ widget). هي عن قصد مش سباق عادل — وهاد هو الدرس، مش الحكم على مين أفضل. ولاحظ إن المُخرجات بتفرق: الـ BT بيتركلك ترتيب كامل ومعاير لكل الـ 30 عنصر زائد نموذج عن ليش (المهارات الكامنة)، قابل لإعادة الاستخدام لأي K؛ والـ Comb-UCB بيتركلك slate منيحة من 5 ومعدّلات لكل عنصر، وما بيعرف شي عن العناصر اللي ما اختارها أبداً. نفس الهدف، feedback مختلف، ماكينة مختلفة — اختار الماكينة اللي إشارتك بتقدر تطعميها فعلاً.

شو شفت

الترتيب تحت الضجيج هو choose-the-max بشكل متنكّر، وبينقسم بنظافة لتلت أزرار: قدّر (SGD على المباريات → مهارات)، اقرا (رتّب)، جدوِل (صوّب على الحدود). وسؤال الميزانية — تصرف على الأزواج اللي متأكّد منهم، ولا على اللي ترتيبهم مش محسوم؟ — هو نفسه explore/exploit تبع الـ bandit، والجواب دايماً «الحدود»، وموسّعة لبِركة لما تحتاج بس الـ top-K.

وكمان هي أول إشارة على الـ structure. مع arms مستقلة كل زوج لحاله؛ هون الأزواج مربوطين بترتيب عام واحد، فـ A ≻ B و B ≻ C بيعطيك A ≻ C ببلاش. هالمعلومة الانتقالية المجانية هي اللي بتنستغل بقوة لما تصير الـ «arms» حواف graph والحركة اللي بتختارها مسار كامل فيه.