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

बहुपद लॉजिस्टिक बैंडिट के लिए लगभग न्यूनतम अनुकूल खेद

मूल जानकारी

  • पेपर ID: 2405.09831
  • शीर्षक: बहुपद लॉजिस्टिक बैंडिट के लिए लगभग न्यूनतम अनुकूल खेद
  • लेखक: जूंगक्यु ली (सियोल नेशनल विश्वविद्यालय), मिन-ह्वान ओह (सियोल नेशनल विश्वविद्यालय)
  • वर्गीकरण: stat.ML cs.LG
  • प्रकाशन समय/सम्मेलन: NeurIPS 2024 (तंत्रिका सूचना प्रसंस्करण प्रणाली पर 38वां सम्मेलन)
  • पेपर लिंक: 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. सैद्धांतिक अंतराल: निचली सीमा Ω(d√T/K) और ऊपरी सीमा Õ(d√T) के बीच √K का अंतराल
  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 से स्वतंत्र
    • MNL बैंडिट में K बढ़ने के साथ खेद में कमी दिखाने वाला पहला एल्गोरिदम
  3. सैद्धांतिक नवाचार:
    • बाहरी विकल्प आकर्षण पैरामीटर v₀ के खेद पर प्रभाव को स्पष्ट रूप से प्रदर्शित करना
    • उदाहरण-संबंधित न्यूनतम-अधिकतम खेद सीमा प्रदान करना
  4. तकनीकी सुधार:
    • सुधारी गई दीर्घवृत्तीय संभावना लेम्मा, K पर निर्भरता को समाप्त करना
    • स्थिर स्व-सामंजस्यपूर्ण हानि फ़ंक्शन विश्लेषण

विधि विवरण

कार्य परिभाषा

इनपुट:

  • प्रत्येक दौर t में, N वस्तुओं की विशेषता वेक्टर x_ ∈ ℝᵈ का अवलोकन
  • अधिकतम वस्तु समूह आकार 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-स्व-सामंजस्य गुण सिद्ध करना, पिछले √(6K) से √K कारक में सुधार
  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 बैंडिट लॉजिस्टिक बैंडिट का बहु-चयन विस्तार है

संयोजन बैंडिट

  • शीर्ष-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 बैंडिट क्षेत्र की मुख्य खुली समस्या को सफलतापूर्वक हल करता है, तकनीकी नवाचार उल्लेखनीय है, प्रायोगिक सत्यापन पर्याप्त है, और संबंधित क्षेत्रों के लिए महत्वपूर्ण प्रेरणा प्रदान करता है।