2025-11-15T02:07:10.757818

Nearly Minimax Optimal Regret for Multinomial Logistic Bandit

Lee, Oh
In this paper, we study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size $K$. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uniform rewards, where all items have the same expected reward, we establish a regret lower bound of $Ω(d\sqrt{T/K})$ and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of $\tilde{O}(d\sqrt{T/K})$. We also provide instance-dependent minimax regret bounds under uniform rewards. Under non-uniform rewards, we prove a lower bound of $Ω(d\sqrt{T})$ and an upper bound of $\tilde{O}(d\sqrt{T})$, also achievable by OFU-MNL+. Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality -- for either uniform or non-uniform reward setting -- and to propose a computationally efficient algorithm that achieves this optimality up to logarithmic factors.
academic

الندم الأمثل تقريباً للعبة البندول متعددة الحدود اللوجستية

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

  • معرّف الورقة: 2405.09831
  • العنوان: Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
  • المؤلفون: Joongkyu Lee (جامعة سيول الوطنية)، Min-hwan Oh (جامعة سيول الوطنية)
  • التصنيف: stat.ML cs.LG
  • وقت النشر/المؤتمر: NeurIPS 2024 (المؤتمر الثامن والثلاثون حول أنظمة معالجة المعلومات العصبية)
  • رابط الورقة: https://arxiv.org/abs/2405.09831

الملخص

تدرس هذه الورقة مشكلة عبة البندول متعددة الحدود اللوجستية (MNL) السياقية، حيث يختار وكيل التعلم مجموعات من المنتجات بشكل متسلسل بناءً على المعلومات السياقية، وتتبع ردود فعل المستخدمين نموذج اختيار MNL. يوجد فجوة كبيرة بين الحدود الدنيا والعليا في الأعمال السابقة، خاصة فيما يتعلق بالحد الأقصى لحجم مجموعة المنتجات K. في إطار المكافآت الموحدة، تثبت الورقة حد ندم أدنى بقيمة Ω(d√T/K) وتقترح خوارزمية OFU-MNL+ ذات وقت ثابت، مما يحقق حد أعلى متطابق بقيمة Õ(d√T/K). في إطار المكافآت غير الموحدة، تثبت حد ندم أدنى بقيمة Ω(d√T) وحد أعلى بقيمة Õ(d√T). هذا هو أول عمل يثبت الأمثلية الصغرى-الكبرى في أدبيات عبة البندول MNL السياقية.

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

خلفية المشكلة

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

دافع البحث

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

قيود الطرق الموجودة

  1. الفجوة النظرية: فجوة بقيمة √K بين الحد الأدنى Ω(d√T/K) والحد الأعلى Õ(d√T)
  2. التعقيد الحسابي: تتطلب الخوارزميات الموجودة تعداد جميع مجموعات المنتجات الممكنة، مما يؤدي إلى تعقيد زمني أسي
  3. الاعتماد على المعاملات: اعتماد سيء على الثابت κ المتعلق بالمشكلة، حيث 1/κ = O(K²)

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

  1. إنشاء حدود ندم محكمة:
    • تحت المكافآت الموحدة: حد أدنى Ω(√(v₀K/(v₀+K))d√T)، حد أعلى Õ(√(v₀K/(v₀+K))d√T)
    • تحت المكافآت غير الموحدة: حد أدنى Ω(d√T)، حد أعلى Õ(d√T)
  2. اقتراح خوارزمية OFU-MNL+ الفعالة:
    • تعقيد زمني ثابت O(1)، مستقل عن عدد الجولات t
    • أول خوارزمية تثبت أن الندم يتناقص مع زيادة K في عبة البندول MNL
  3. الابتكار النظري:
    • أول عرض واضح لتأثير معامل جاذبية الخيار الخارجي v₀ على الندم
    • توفير حدود ندم صغرى-كبرى متعلقة بالمثيل
  4. التحسينات التقنية:
    • مبرهنة الجهد الإهليلجي المحسّنة، التي تزيل الاعتماد على K
    • تحليل دالة الخسارة ذات الخاصية الذاتية المتسقة الثابتة

شرح الطريقة

تعريف المهمة

المدخلات:

  • في كل جولة t، ملاحظة متجهات الميزات x_ ∈ ℝᵈ لـ N منتج
  • الحد الأقصى لحجم مجموعة المنتجات K
  • معامل جاذبية الخيار الخارجي v₀

المخرجات:

  • اختيار مجموعة منتجات S_t ⊆ {1,...,N}، |S_t| ≤ K
  • ملاحظة اختيار المستخدم c_t ∈ S_t ∪ {0}، يتبع نموذج MNL

الهدف: تقليل الندم التراكمي Reg_T(w*) = Σ_^T R_t(S_t, w) - R_t(S_t, w*)

معمارية النموذج

نموذج اختيار MNL

احتمالية اختيار المستخدم للمنتج i ∈ S_t:

p_t(i|S_t, w*) = exp(x_{ti}^T w*) / (v₀ + Σ_{j∈S_t} exp(x_{tj}^T w*))

احتمالية الخيار الخارجي (عدم اختيار أي منتج):

p_t(0|S_t, w*) = v₀ / (v₀ + Σ_{j∈S_t} exp(x_{tj}^T w*))

المكونات الأساسية لخوارزمية OFU-MNL+

  1. تقدير المعاملات عبر الإنترنت:
    w_{t+1} = argmin_{w∈W} ⟨∇ℓ_t(w_t), w⟩ + (1/2η)||w - w_t||²_{H̃_t}

    حيث H̃_t = H_t + ηG_t(w_t)، و G_t(w) هي مصفوفة هسيان لخسارة MNL
  2. بناء مجموعة الثقة:
    C_t(δ) = {w ∈ W : ||w_t - w||_{H_t} ≤ β_t(δ)}

    حيث β_t(δ) = O(√(d log t log K))
  3. حساب المنفعة المتفائلة:
    α_{ti} = x_{ti}^T w_t + β_t(δ)||x_{ti}||_{H_t^{-1}}
  4. اختيار مجموعة المنتجات:
    • المكافآت الموحدة: اختيار K منتج بأعلى قيم α_
    • المكافآت غير الموحدة: حل مشكلة تحسين توليفية في وقت متعدد الحدود

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

  1. تحليل الاتساق الذاتي المحسّن: إثبات أن دالة خسارة MNL تتمتع بخاصية اتساق ذاتي بقيمة 3√2، محسّنة بعامل √K مقارنة بـ √(6K) السابق
  2. مبرهنة الجهد الإهليلجي المستقلة عن K:
    Σ_{t=1}^T Σ_{i∈S_t} p_t(i|S_t,w_{t+1})p_t(0|S_t,w_{t+1})||x_{ti}||²_{H_t^{-1}} ≤ 2d log(1 + T/(dλ))
  3. حد تباعد KL محكم: إنشاء حد أعلى أكثر محكماً لتباعد KL، محسّن من نتائج Chen وآخرين

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

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

  • مجموعات بيانات اصطناعية، حيث يتم أخذ عينات من المعاملات w* ∈ ℝᵈ بشكل موحد من -1/√d, 1/√dᵈ
  • يتم أخذ عينات من ميزات السياق x_ من التوزيع الغاوسي متعدد المتغيرات N(0_d, I_d) وقطعها إلى -1/√d, 1/√dᵈ
  • الإعدادات: N=100, K∈{5,10,15}, d=5, T=3000

مقاييس التقييم

  • الندم التراكمي: Σ_^T R_t(S_t, w) - R_t(S_t, w*)
  • وقت الحساب لكل جولة

طرق المقارنة

  • UCB-MNL: طريقة قائمة على الحد الأعلى للثقة
  • TS-MNL: طريقة قائمة على عينات Thompson

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

  • معامل التنظيم λ = 84√(2d)η
  • حجم الخطوة η = (1/2)log(K+1) + 2
  • نصف قطر الثقة β_t(δ) = O(√(d log t log K))

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

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

  1. أداء الندم:
    • تحت المكافآت الموحدة، ينخفض الندم التراكمي لجميع الخوارزميات مع زيادة K
    • تحت المكافآت غير الموحدة، لا تضمن زيادة K تحسن الندم
    • تتفوق OFU-MNL+ بشكل كبير على طرق الأساس في جميع الإعدادات
  2. الكفاءة الحسابية:
    • تحافظ OFU-MNL+ على تكلفة حسابية ثابتة، مستقلة عن عدد الجولات t
    • ينمو وقت الحساب لطرق الأساس خطياً مع t
    • وقت التشغيل تحت إعداد المكافآت الموحدة حوالي 1/10 من الإعداد غير الموحد

التحقق النظري

تتحقق نتائج التجارب من التحليل النظري:

  • عندما v₀ = Θ(1)، ينخفض الندم مع K
  • عندما v₀ = Θ(K)، يكون الندم مستقلاً عن K
  • تحت المكافآت غير الموحدة، يكون الندم مستقلاً عن K

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

أبحاث عبة البندول MNL

  1. الإعدادات غير السياقية: أثبت Agrawal وآخرون حد ندم أدنى بقيمة Ω(√(NT/K))
  2. الإعدادات السياقية: اقترح Chen وآخرون حد ندم أدنى بقيمة Ω(d√T/K)، لكن تعقيد الخوارزمية أسي
  3. الكفاءة الحسابية: اقترح Oh و Iyengar خوارزمية في وقت متعدد الحدود، لكن حد الندم يعتمد على 1/κ

عبة البندول اللوجستية

  • تم تطوير خوارزميات مثلى لعبة البندول اللوجستية الثنائية
  • عبة البندول MNL هي امتداد متعدد الاختيار لعبة البندول اللوجستية

عبة البندول التوليفية

  • مرتبطة بعبة البندول التوليفية top-k لكن بهيكل مكافآت مختلف
  • في نموذج MNL، تعتمد مكافآت المنتج الفردي على المجموعة بأكملها

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

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

  1. الاكتمال النظري: تحقيق الأمثلية الصغرى-الكبرى لأول مرة في عبة البندول MNL
  2. كفاءة الخوارزمية: اقتراح أول خوارزمية مثلى بتعقيد زمني ثابت
  3. تأثير المعاملات: تحديد كمي واضح لتأثير v₀ و K على الندم

القيود

  1. افتراضات محدودة: يتطلب ||w*||₂ ≤ 1، وتخفيف هذا سيؤدي إلى عوامل أسية إضافية في حد الندم
  2. حدود متعلقة بالمثيل: لا يمكن إنشاء حدود متعلقة بالمثيل تحت المكافآت غير الموحدة
  3. عوامل ثابتة: قد تكون العوامل اللوغاريتمية في الحدود النظرية كبيرة في الممارسة

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

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

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

المزايا

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

أوجه القصور

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

التأثير

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

السيناريوهات القابلة للتطبيق

  1. أنظمة التوصيات: توصيات المنتجات عبر الإنترنت، توصيات المحتوى
  2. الإعلانات عبر الإنترنت: اختيار مجموعة الإعلانات وتحسين النشر
  3. التجارة الإلكترونية: تحسين عرض المنتجات واستراتيجيات الترويج

المراجع

تستشهد الورقة بـ 52 مرجعاً ذا صلة، تشمل بشكل أساسي:

  • الأعمال الأساسية لعبة البندول MNL: Agrawal et al., Chen et al.
  • نظرية عبة البندول اللوجستية: Faury et al., Abeille et al.
  • أساسيات التعلم عبر الإنترنت: Lattimore & Szepesvári
  • نظرية الدوال ذاتية الاتساق: Tran-Dinh et al.

التقييم الإجمالي: هذه ورقة عالية الجودة بمساهمات نظرية بارزة، حيث حلت بنجاح مشكلة أساسية مفتوحة في مجال عبة البندول MNL، مع ابتكار تقني ملحوظ وتحقق تجريبي كافٍ، وتتمتع بتأثير مهم على دفع المجالات ذات الصلة.