2025-11-11T09:55:09.434704

UCB-type Algorithm for Budget-Constrained Expert Learning

Latypov, Suvorikova, Kroshnin et al.
In many modern applications, a system must dynamically choose between several adaptive learning algorithms that are trained online. Examples include model selection in streaming environments, switching between trading strategies in finance, and orchestrating multiple contextual bandit or reinforcement learning agents. At each round, a learner must select one predictor among $K$ adaptive experts to make a prediction, while being able to update at most $M \le K$ of them under a fixed training budget. We address this problem in the \emph{stochastic setting} and introduce \algname{M-LCB}, a computationally efficient UCB-style meta-algorithm that provides \emph{anytime regret guarantees}. Its confidence intervals are built directly from realized losses, require no additional optimization, and seamlessly reflect the convergence properties of the underlying experts. If each expert achieves internal regret $\tilde O(T^α)$, then \algname{M-LCB} ensures overall regret bounded by $\tilde O\!\Bigl(\sqrt{\tfrac{KT}{M}} \;+\; (K/M)^{1-α}\,T^α\Bigr)$. To our knowledge, this is the first result establishing regret guarantees when multiple adaptive experts are trained simultaneously under per-round budget constraints. We illustrate the framework with two representative cases: (i) parametric models trained online with stochastic losses, and (ii) experts that are themselves multi-armed bandit algorithms. These examples highlight how \algname{M-LCB} extends the classical bandit paradigm to the more realistic scenario of coordinating stateful, self-learning experts under limited resources.
academic

خوارزمية من نوع UCB للتعلم من الخبراء مع قيود الميزانية

المعلومات الأساسية

  • معرّف الورقة: 2510.22654
  • العنوان: خوارزمية من نوع UCB للتعلم من الخبراء مع قيود الميزانية
  • المؤلفون: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn
  • التصنيف: cs.LG (التعلم الآلي)، cs.MA (الأنظمة متعددة الوكلاء)
  • تاريخ النشر: 28 أكتوبر 2025 (نسخة أولية)
  • رابط الورقة: https://arxiv.org/abs/2510.22654

الملخص

في العديد من التطبيقات الحديثة، يجب على الأنظمة الاختيار الديناميكي بين عدة خوارزميات تعلم تكيفية مدربة عبر الإنترنت. على سبيل المثال: اختيار النموذج في بيئات البث، تبديل استراتيجيات التداول في المالية، والتنسيق بين عدة آليات سياق أو وكلاء التعلم المعزز. في كل جولة، يجب على المتعلم اختيار منبئ من K خبير تكيفي للتنبؤ، مع إمكانية تحديث M≤K خبير فقط ضمن ميزانية تدريب ثابتة.

تحل هذه الورقة هذه المشكلة في الإعداد العشوائي، وتقترح خوارزمية M-LCB — وهي خوارزمية فوقية من نوع UCB فعالة حسابياً توفر ضمانات ندم في أي وقت. يتم بناء فترات الثقة مباشرة من الخسائر المحققة، دون الحاجة إلى تحسين إضافي، وتعكس بسلاسة خصائص التقارب للخبراء الأساسيين. إذا حقق كل خبير ندماً داخلياً قدره Õ(T^α)، فإن M-LCB تضمن حد ندم إجمالي قدره Õ(√(KT/M) + (K/M)^(1-α)T^α).

خلفية البحث والدافع

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

تتطلب العديد من التطبيقات الواقعية الاختيار الديناميكي بين عدة خبراء يتعلمون ذاتياً:

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

التحديات الأساسية

قيود الطرق التقليدية:

  • آليات متعددة الأذرع الكلاسيكية (MAB): تفترض توزيعات مكافآت ثابتة أو معادية، لا تأخذ في الاعتبار قدرة الأذرع على التعلم
  • خوارزميات الخبراء: عادة ما تتطلب ردود فعل كاملة، لا تأخذ في الاعتبار معدلات التعلم للخبراء
  • الطرق الموجودة: لم تعالج بشكل كافٍ تحدي إدارة عدة خبراء يتعلمون بشكل متزامن تحت قيود ميزانية التدريب لكل جولة

دافع البحث

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

المساهمات الأساسية

  1. خوارزمية فوقية جديدة من نوع UCB (M-LCB): تقترح خوارزمية جديدة لإدارة مجموعة من K خبير يتعلم ذاتياً، مع الأخذ في الاعتبار ميزانية التعلم المحدودة M لكل جولة (M≤K)
  2. الكفاءة الحسابية: توفر طريقة لبناء حدود الثقة مباشرة من الخسائر المحققة، فعالة حسابياً وتتجنب التحسين المساعد المكلف
  3. التحليل النظري: تقدير أداء الخوارزمية الفوقية بناءً على معدلات التقارب الفردية للخبراء، عندما يكون ندم الخبير Õ(n^α)، يكون الندم الإجمالي Õ(√(KT/M) + (K/M)^(1-α)T^α)
  4. توسيع آليات السياق متعددة: إثبات أن M-LCB قابلة للتوسيع إلى إعداد آليات السياق متعددة

شرح الطريقة

تعريف المهمة

  • فضاء القرار U: فضاء توصيات الخبراء
  • فضاء البيئة E: فضاء النتائج العشوائية
  • دالة الخسارة: ℓ : U×E → R₊
  • مواصفات الخبير: يتم تحديد كل خبير k بواسطة صف (Wₖ,Hₖ,Aₖ,gₖ,υₖ)
    • Wₖ: فضاء الحالة/المعاملات
    • Hₖ: فضاء السجل
    • Aₖ: خوارزمية التعلم عبر الإنترنت
    • gₖ: الخريطة من الحالة إلى التوصية
    • υₖ: منشئ التوصية الآمنة

بروتوكول التنفيذ

تسلسل التنفيذ لكل جولة t:

  1. يختار البرنامج الفوقي المستشار iₜ∈K ومجموعة التدريب Sₜ⊆K، مع |Sₜ|≤M و iₜ∈Sₜ
  2. يقدم الخبير iₜ توصية آمنة uₜ = υᵢₜ(Hᵢₜᵗ)∈U
  3. تأخذ البيئة عينة ξᵗ～D، ويتحمل البرنامج خسارة ℓ(uₜ,ξᵗ)
  4. يحدث الخبير k∈Sₜ السجل والحالة الداخلية

جوهر خوارزمية M-LCB

تعريف فترات الثقة

بالنسبة للخبير k، حدد:

  • الخسارة المعايرة المتراكمة: LAₖ(t) = (1/nₖᵗ)∑_{τ∈Iₖ(t)} ℓₖᵗ(wₖᵗ)
  • حد الثقة الأدنى: LCBₖ(t,δ) = LAₖ(t) - Uₖ(nₖᵗ,δₐᵣₘ)/nₖᵗ - G(nₖᵗ,δₙᵗ)
  • حد الثقة الأعلى: UCBₖ(t,δ) = LAₖ(t) + H(nₖᵗ,δₙᵗ)

حيث:

  • δₐᵣₘ = δ/(2K), δₙ = δ/(7Kn²)
  • G(n,δ) = √(2log(1/δ)/n) + 2log(1/δ)/(3n)
  • H(n,δ) = √(2log(1/δ)/n)

استراتيجية الاختيار

  • اختيار مجموعة التدريب: Sₜ := argmin_{S⊆K,|S|≤M} ∑_{k∈S} LCBₖ(t,δ)
  • اختيار المستشار: iₜ := argmin_{k∈Sₜ} UCBₖ(t,δ)

نقاط الابتكار التقني

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

إعداد التجارب

مجموعات البيانات

أجرت الورقة بشكل أساسي تجارب اصطناعية:

اختيار النموذج الخطي المعمم

  • عدد الخبراء: K=10 نماذج خطية معممة
  • بُعد الميزة: يتم أخذ عينات متجهات الميزات بشكل موحد من الكرة الوحدة Sᵈ⁻¹
  • إعداد التحدي: الدوال f₇,f₈,f₉ متشابهة جداً في مناطق البيانات الكثيفة، مما يزيد من صعوبة الاستكشاف

مؤشرات التقييم

  1. الخسارة المتراكمة: ∑ᵗ₌₁ᵀ ℓ(uᵗ,ξᵗ)
  2. توزيع اختيار الذراع: التكرار النهائي لاختيار كل خبير
  3. توزيع ميزانية الحساب: توزيع عدد مرات التدريب التي يحصل عليها كل خبير

طرق المقارنة

  1. ED2RB: خوارزمية بضمانات الأذرع القابلة للتعلم
  2. LimitedAdvice: خوارزمية خبراء يمكنها التعامل مع تحديثات متعددة الأذرع لكل جولة

تفاصيل التنفيذ

  • حد التحديث: M∈{1,2,3}
  • عدد التكرارات: 30 تشغيل مستقل للحصول على المتوسط
  • فترات الثقة: عرض ±0.5 انحراف معياري
  • ضبط المعاملات الفائقة: معامل الاستكشاف ED2RB c=0.1، مقياس حد التركيز M-FLCB 0.3

نتائج التجارب

النتائج الرئيسية

  1. أداء التقارب: تحقق M-LCB ندماً دون خطي، مع قدرة تنافسية مقارنة بطرق الخط الأساسي
  2. تحديد الخبير: تحديد ناجح للخبير الأمثل (k=9)
  3. كفاءة الميزانية: توزيع التحديثات بشكل أساسي على الخبراء ذوي الأداء العالية، بينما يوزع LimitedAdvice بشكل أكثر توازناً

النتائج النظرية

نظرية الحد الأعلى

النظرية 2: دع α,δ∈(0,1)، افترض أن كل خبير k يرضي Uₖ(t,δ)=O(t^α c(δ))، ثم باحتمالية لا تقل عن 1-δ، يكون ندم الخوارزمية 1 محدوداً لجميع T≥1:

Reg(T) = O(√(KT/M)log(KT/δ) + (K/M)^(1-α)T^α c(δ))

نظرية الحد الأدنى

النظرية 1: توجد ثوابت c₁,c₂>0 بحيث لأي خوارزمية تعلم وبرنامج فوقي:

sup EReg(T) ≥ c₁√(KT/M) + c₂T^α(K/M)^(1-α)

هذا يشير إلى أن M-LCB تحقق الأمثلية ضمن عوامل لوغاريتمية.

الأعمال ذات الصلة

الخبراء الذين يتعلمون ذاتياً (الأذرع)

  • 6: إدخال أذرع تتعلم ذاتياً في إعداد MAB، حيث تكون كل ذراع دالة معاملة، يتم تحديث المعاملات بعد الاختيار

اختيار النموذج على المستوى الفوقي

  • CORRAL8: إدارة مجموعة من خوارزميات المراهنات من خلال الانحدار المرآوي للحاجز اللوغاريتمي مع ردود فعل الأهمية المرجحة
  • التوازن الديناميكي9: خوارزمية فوقية بناءً على تعبيرات معدل الندم المعروفة، تحديث متعلم واحد فقط لكل جولة
  • 10: تقدير معاملات كل متعلم عبر الإنترنت، الحصول على ضمانات عالية الاحتمالية تعتمد على البيانات للمراهنات العشوائية

MAB مع تحديثات متعددة الأذرع

  • نصائح محدودة12: الاستعلام عن M ذراع على الأكثر، الحصول على حد ندم Õ(√(KT logK/M))
  • 13: ندم minimax الأمثل Õ(max{√(KT/M), √(T logK)})

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. إنشاء ضمانات ندم لأول مرة لعدة خبراء تكيفيين يتم تدريبهم بشكل متزامن تحت قيود الميزانية لكل جولة
  2. تحقق خوارزمية M-LCB الأمثلية ضمن عوامل لوغاريتمية
  3. يوحد الإطار بين التحسين عبر الإنترنت وإعدادات المراهنات العشوائية

القيود

  1. مقياس الثقة المعروف: يفترض التحليل معرفة دالة مقياس الثقة c(δ)
  2. افتراض الخسارة المحدودة: التركيز الأساسي على حالات الخسارة المحدودة
  3. الإعداد العشوائي: التحليل الأساسي في بيئة عشوائية، يتطلب الإعداد المعادي مزيداً من البحث

الاتجاهات المستقبلية

  1. حالة c(δ) غير المعروفة: مثل معالجة Pacchiano وآخرون11
  2. توسيع الملاحظات الإضافية: التوسيع إلى نصائح محدودة وآليات سياق متعددة
  3. نظام السياق: التوسيع إلى الحالات التي يتخصص فيها الخبراء بناءً على ميزات الملاحظة

التقييم المتعمق

المميزات

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

أوجه القصور

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

التأثير

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

السيناريوهات المناسبة

  1. اختيار النموذج عبر الإنترنت: الاختيار الديناميكي للنموذج في بيئات بث البيانات
  2. أنظمة متعددة الاستراتيجية: التداول المالي والإعلانات والسيناريوهات التي تتطلب تبديل الاستراتيجية
  3. التعلم مع موارد محدودة: تنسيق نماذج متعددة عندما تكون الموارد الحسابية محدودة

المراجع

تستشهد الورقة بأدبيات مهمة في مجالات المراهنات متعددة الأذرع والتعلم عبر الإنترنت وخوارزميات الخبراء، خاصة:

  • خوارزمية UCB الكلاسيكية لـ Auer وآخرون1
  • نظرية خوارزميات الخبراء لـ Cesa-Bianchi و Lugosi4
  • التحسين المحدب عبر الإنترنت لـ Hazan5
  • خوارزميات التعلم الفوقي الحديثة مثل CORRAL8

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