🤖 machine learning

Nonlinear Bandit

यह शोध पत्र भारी-पूंछ वाले शोर (heavy-tailed noise) के तहत सामान्य रैखिक बैंडिट्स (generalized linear bandits) के लिए निकट-इष्टतम रिग्रेट (near-optimal regret) प्राप्त करने हेतु ऑनलाइन मिरर डिसेंट (online mirror descent) और एडेप्टिव हूबर लॉस (adaptive Huber loss) पर आधारित EHM एल्गोरिदम का प्रस्ताव करता है, और इस ढांचे को पीसवाइज कांस्टेंट कॉन्टेक्स्ट्स (piecewise constant contexts) और सामान्य नॉनलीनियर बैंडिट समस्याओं को संभालने के लिए विस्तारित करता है।

मूल लेखक: Tianshuo Zheng, Ting Wu, Zhi-Hua Zhou, Keqin Liu

प्रकाशित 2026-07-09

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Tianshuo Zheng, Ting Wu, Zhi-Hua Zhou, Keqin Liu

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक शेफ हैं जो एक नए व्यंजन के लिए एकदम सही रेसिपी खोजने की कोशिश कर रहे हैं। आपके पास सामग्री (कार्यों) का एक विशाल भंडार है, और हर बार जब आप कोई भोजन बनाते हैं, तो आपको एक स्वाद परीक्षण (इनाम) मिलता है। हालाँकि, इसमें दो बड़ी समस्याएँ हैं:

स्वाद कलियाँ खराब हैं (हैवी-टेल्ड नॉइज़/भारी-पूंछ वाला शोर): कभी-कभी, स्वाद परीक्षण बेहद गलत हो सकता है। किसी दिन, एक आलोचक कह सकता है कि सूप "ठीक है," और अगले दिन, वह केवल इसलिए चिल्ला सकता है कि यह "सबसे बुरा व्यंजन है" क्योंकि उसका दिन खराब रहा था। ये अत्यधिक, अप्रत्याशित प्रतिक्रियाएं ही वे हैं जिन्हें पेपर "हैवी-टेल्ड नॉइज़" कहता है। अधिकांश मानक कुकिंग गाइड (एल्गोरिदम) इन जंगली उतार-चढ़ावों के सामने विफल हो जाते हैं।
रेसिपी जटिल है (नॉनलिनियैरिटी/अरेखीयता): आपकी सामग्रियों और अंतिम स्वाद के बीच का संबंध एक साधारण सीधी रेखा नहीं है। थोड़ा अधिक नमक डालने से केवल नमक का स्वाद थोड़ा ही नहीं बढ़ता; यह पूरे फ्लेवर प्रोफाइल को एक जटिल, घुमावदार तरीके से बदल सकता है।

यह पेपर आपको इन पागल आलोचकों और जटिल कुकिंग के बीच भी सबसे अच्छी रेसिपी खोजने में मदद करने के लिए उपकरणों (एल्गोरिदम) का एक नया सेट पेश करता है। यह इसे तीन मुख्य चरणों में कैसे करता है, यहाँ दिया गया है:

1. "स्थिर हाथ" विधि (GLB-EHM)

सबसे पहले, लेखक पागल आलोचकों की समस्या से निपटते हैं। अतीत में, यदि कोई आलोचक चिल्लाकर "भयानक!" (एक आउटलायर) कहता था, तो मानक तरीके इसे औसत निकालने की कोशिश करते थे, जिससे अक्सर पूरी रेसिपी ही बिगड़ जाती थी।

लेखक हूबर लॉस (Huber Loss) तकनीक का उपयोग करते हैं। इसे अपने निर्णय लेने के लिए एक "स्थिर हाथ" के रूप में समझें।

यह कैसे काम करता है: यदि स्वाद परीक्षण सामान्य है, तो एल्गोरिदम ध्यान से सुनता है। लेकिन यदि कोई आलोचक कुछ चरम (आउटलायर) चिल्लाता है, तो एल्गोरिदम कहता है, "ठीक है, यह पूरी तरह से भरोसा करने के लिए बहुत पागलपन भरा है," और उस चीख के प्रभाव को सीमित कर देता है। यह चरम त्रुटियों को एक नरम कुशन की तरह कोमलता से लेता है, बजाय इसके कि उन्हें पूरे प्लान को ध्वस्त करने दिया जाए।
परिणाम: उन्होंने GLB-EHM नामक एक एल्गोरिदम बनाया। यह पागल आलोचकों के साथ भी सबसे अच्छी रेसिपी सीखता है, और यह बहुत कुशलता से करता है। इसे हर एक पुराने स्वाद परीक्षण को याद रखने की आवश्यकता नहीं है; यह एक ही त्वरित पास में अपनी स्मृति को अपडेट करता है, जिससे यह तेज़ और हल्का बनता है।

2. "पड़ोस" रणनीति (PGLB-EHM)

इसके बाद, उन्हें एहसास हुआ कि कभी-कभी "सबसे अच्छी रेसिपी" इस बात पर निर्भर करती है कि आप कहाँ खाना बना रहे हैं। शायद "तीखे पड़ोस" में, आपको अधिक मिर्च की आवश्यकता है, लेकिन "मीठे पड़ोस" में, आपको अधिक चीनी की आवश्यकता है। नियम हर जगह एक समान नहीं हैं; वे पीसवाइज कांस्टेंट (piecewise constant) (अलग-अलग क्षेत्रों में अलग-अलग) हैं।

उपमा: कल्पना करें कि रसोई को विभिन्न जिलों में विभाजित किया गया है। एल्गोरिदम महसूस करता है, "मैं पूरी रसोई के लिए एक नियम का उपयोग नहीं कर सकता।" इसके बजाय, यह प्रत्येक जिले के लिए एक छोटी, विशेष टीम स्थापित करता है।
परिणाम: उन्होंने PGLB-EHM बनाया। यह एल्गोरिदम प्रत्येक जिले के लिए अलग-अलग स्कोरकार्ड रखता है। यह जल्दी से पता लगा लेता है कि किस जिले पर ध्यान केंद्रित करना "सबसे अच्छा" है और अपना अधिकांश समय वहीं खाना बनाने में बिताता है, जबकि अभी भी अन्य जिलों पर नज़र रखता है ताकि ज़रूरत पड़ने पर काम आ सके। यह साबित करता है कि इन बदलते नियमों के बावजूद, आप बहुत अधिक समय बर्बाद किए बिना सबसे अच्छा व्यंजन खोज सकते हैं।

3. "ज़ूम-इन" विधि (NB-EHM)

अंत में, उन्होंने सबसे कठिन समस्या का सामना किया: क्या होगा यदि रेसिपी केवल जिलों के अनुसार अलग नहीं है, बल्कि नियम हर जगह सुचारू रूप से और निरंतर बदलते हैं? शायद नमक की सही मात्रा एक जटिल, घुमावदार फॉर्मूले पर निर्भर करती है जो हर छोटे समायोजन के साथ थोड़ा बदल जाता है। यह नॉनलिनियर बैंडिट (Nonlinear Bandit) समस्या है।

उपमा: कल्पना करें कि आप एक विशाल मानचित्र पर छिपे हुए खजाने को देख रहे हैं। आप सटीक स्थान नहीं जानते। यादृच्छिक रूप से अनुमान लगाने के बजाय, आप बाइसेक्शन विधि (Bisection Method) (जैसे "हॉट एंड कोल्ड" का खेल) का उपयोग करते हैं।
- आप पूरे मानचित्र को आधा करके शुरुआत करते हैं।
- आप बीच का परीक्षण करते हैं।
- आपको एहसास होता है कि खजाना बाएं हिस्से में है, इसलिए आप दाएं हिस्से को छोड़ देते हैं।
- आप बाएं हिस्से को फिर से आधा करते हैं, बीच का परीक्षण करते हैं, और ज़ूम-इन करते रहते हैं।
ट्विस्ट: लेखकों ने एक विशेष नियम जोड़ा: आप जिस क्षेत्र में ज़ूम कर रहे हैं, वह जितना छोटा होगा, आपको उस पर समय बिताने की उतनी ही अधिक अनुमति होगी। यह सुनिश्चित करता है कि जैसे-जैसे आप खजाने के करीब पहुँचते हैं, आप जल्दबाजी नहीं करते; आप बहुत सटीक होते हैं।
परिणाम: उन्होंने NB-EHM बनाया। "ज़ूम-इन" रणनीति को चरण 1 से उनके "स्थिर हाथ" (हूबर लॉस) के साथ जोड़कर, उन्होंने साबित किया कि आप सबसे अच्छी रेसिपी पा सकते हैं, भले ही नियम जटिल हों और आलोचक पागल हों।

बड़ी तस्वीर (The Big Picture)

पेपर का दावा है कि इन विचारों को मिलाकर:

मजबूती (Robustness): आप जंगली, अप्रत्याशित डेटा (हैवी-टेल्ड नॉइज़) को बिना टूटे संभाल सकते हैं।
दक्षता (Efficiency): आपको सुपर कंप्यूटर की आवश्यकता नहीं है; गणित को तेज़ (वन-पास अपडेट) होने के लिए डिज़ाइन किया गया है।
लचीलापन (Flexibility): आप सरल नियम, ज़ोन-आधारित नियम और जटिल, घुमावदार नियमों को संभाल सकते हैं।

उन्होंने इन विचारों का परीक्षण कंप्यूटर सिमुलेशन (जैसे एक वर्चुअल किचन) के साथ किया और दिखाया कि उनके तरीके पुराने तरीकों की तुलना में लगातार बेहतर परिणाम तेजी से पाते हैं, और साथ ही उन "चिल्लाने वाले" आउटलेयर्स को अनदेखा करते हैं जो आमतौर पर सिस्टम को भ्रमित कर देते हैं।

संक्षेप में: उन्होंने अनुभव से सीखने का एक स्मार्ट, अधिक मजबूत और अधिक अनुकूल तरीका बनाया है जब दुनिया अव्यवस्थित, अप्रत्याशित और जटिल होती है।

तकनीकी सारांश: हैवी-टेल्ड नॉइज़ के साथ नॉनलीनियर बैंडिट

समस्या की परिभाषा

यह शोध पत्र जनरलाइज्ड लीनियर बैंडिट्स (GLB) और नॉनलीनियर बैंडिट्स (NB) के अंतर्गत हैवी-टेल्ड नॉइज़ (भारी-पूंछ वाले शोर) की स्थितियों में अनुक्रमिक निर्णय लेने (sequential decision-making) की चुनौती को संबोधित करता है। पारंपरिक बैंडिट एल्गोरिदम अक्सर लाइट-टेल्ड (जैसे सब-गॉसियन) रिवॉर्ड डिस्ट्रीब्यूशन मानकर चलते हैं, जो वास्तविक दुनिया के परिदृश्यों में विफल हो जाते हैं, जैसे कि वित्तीय बाजार, व्यक्तिगत अनुशंसाएं (personalized recommendations), और चिकित्सा उपचार, जहाँ रिवॉर्ड्स हैवी-टेल्ड (जैसे पारेटो या स्टूडेंट टी-डिस्ट्रीब्यूशन) प्रदर्शित करते हैं।

मुख्य समस्या में एक लर्नर प्रत्येक दौर $t$ पर एक व्यवहार्य सेट (feasible set) से एक एक्शन $X_t$ चुनता है ताकि अपेक्षित संचयी रिवॉर्ड को अधिकतम किया जा सके। रिवॉर्ड मॉडल को इस प्रकार परिभाषित किया गया है:
$r_t = \mu(\langle X_t, \theta^* \rangle) + \varepsilon_t$
जहाँ $\mu$ एक लिंक फंक्शन है, $\theta^*$ एक अज्ञात पैरामीटर है, और $\varepsilon_t$ ऐसा शोर है जिसके बाउंडेड $(1+\epsilon)$ -थ मोमेंट्स ( $\epsilon \in (0, 1]$ ) हैं, न कि बाउंडेड वेरिएंस। लक्ष्य संचयी रिग्रेट (cumulative regret) $R(T)$ को कम करना है जबकि कम्प्यूटेशनल दक्षता और आउटलेयर्स के प्रति मजबूती बनाए रखना है।

यह शोध दो अधिक जटिल सेटिंग्स में जांच का विस्तार करता है:

पीसवाइज GLB (Piecewise GLB): जहाँ अज्ञात पैरामीटर $\theta^*$ एक्शन स्पेस के विभिन्न क्षेत्रों में पीसवाइज कांस्टेंट है।
सामान्य नॉनलीनियर बैंडिट्स (General Nonlinear Bandits): जहाँ रिवॉर्ड फंक्शन $b(X)$ एक सामान्य नॉनलीनियर फंक्शन है, जो किसी विशिष्ट लिंक फंक्शन संरचना तक सीमित नहीं है, और इसके लिए उच्च-आयामी लीनियर स्पेस में मैप करने के लिए "अफ़ाइन लिफ्टिंग" (affine lifting) की आवश्यकता हो सकती है।

कार्यप्रणाली (Methodology)

लेखक ऑनलाइन मिरर डिसेंट (OMD) फ्रेमवर्क पर आधारित एल्गोरिदम की एक श्रृंखला प्रस्तावित करते हैं, जो हैवी-टेल्ड नॉइज़ को संभालने के लिए एक एक्सटेंडेड हबर लॉस (Extended Huber Loss) का उपयोग करते हैं।

1. GLB-EHM (जनरलाइज्ड लीनियर बैंडिट विद एक्सटेंडेड हबर मेथड)

मुख्य तंत्र: एल्गोरिदम मानक मैक्सिमम लाइकलीहुड एस्टीमेशन (MLE) को एक एक्सटेंडेड हबर लॉस फंक्शन से बदल देता है। यह लॉस फंक्शन छोटे एरर के लिए $L_2$ लॉस के क्वाड्रेटिक व्यवहार और बड़े एरर के लिए $L_1$ लॉस के लीनियर व्यवहार को जोड़ता है, जो आउटलेयर्स के विरुद्ध मजबूती प्रदान करता है।
वन-पास अपडेट: एक प्रमुख विशेषता वन-पास अपडेट तंत्र है। एल्गोरिदम शेर्मन-मोरिसन फॉर्मूला और प्रोजेक्शन डीकंपोजिशन का उपयोग करके पैरामीटर्स को अपडेट करता है, जिससे टाइम होराइजन $T$ के संबंध में $O(1)$ कम्प्यूटेशनल कॉम्प्लेक्सिटी प्राप्त होती है (विशेष रूप से प्रत्येक स्टेप के लिए $O(d^3)$ , जो $T$ से स्वतंत्र है)।
पैरामीटर एलिमिनेशन: यह विधि अग्रणी रिग्रेट टर्म में संवेदनशील पैरामीटर $\kappa$ (लिंक फंक्शन के डेरिवेटिव का लोअर बाउंड) पर निर्भरता को समाप्त करने के लिए एक विशिष्ट पैरामीटर सेटिंग पेश करती है, जो पिछले कार्यों में मौजूद थी।

2. PGLB-EHM (पीसवाइज GLB-EHM)

अनुकूलन: उन परिदृश्यों के लिए जहाँ कॉन्टेक्स्टुअल कैरेक्टरिस्टिक $\theta^*$ पीसवाइज कांस्टेंट है, एल्गोरिदम प्रत्येक क्षेत्र $A_i$ के लिए अलग-अलग एस्टीमेशन बनाए रखता है।
रणनीति: यह "डिस्टिंग्विश एंड एक्सप्लॉइट" (विभेद और शोषण) दृष्टिकोण अपनाता है। यह सुनिश्चित करके कि इष्टतम क्षेत्र अन्य उप-इष्टतम क्षेत्रों की तुलना में काफी अधिक (एक स्थिरांक $a$ द्वारा) रिवॉर्ड देता है, एल्गोरिदम एक सीमित समय लागत के साथ इष्टतम क्षेत्र की पहचान करता है और वहां अन्वेषण (exploration) पर ध्यान केंद्रित करता है।

3. NB-EHM (नॉनलीनियर बैंडिट विद एक्सटेंडेड हबर मेथड)

बाइसेक्शन मेथड: सामान्य नॉनलीनियर रिवॉर्ड फंक्शन्स $b(X)$ को संभालने के लिए, एल्गोरिदम व्यवहार्य स्पेस (यूनिट बॉल) को छोटे उप-क्षेत्रों में पुनरावर्ती रूप से परिष्कृत करने के लिए एक बाइसेक्शन मेथड का उपयोग करता है।
एक्सप्लोरेशन रिस्ट्रिक्शन: एक महत्वपूर्ण घटक प्रत्येक क्षेत्र $A$ के लिए निर्धारित टाइम लिमिट $T(A) \propto 1/d(A)^2$ है, जहाँ $d(A)$ क्षेत्र की चौड़ाई है। जैसे-जैसे क्षेत्र सूक्ष्म होते जाते हैं, अनुमत अन्वेषण समय बढ़ जाता है, जिससे एस्टीमेशन एरर स्वतः कम हो जाता है।
अफ़ाइन लिफ्टिंग: उन सामान्य नॉनलीनियर फंक्शन्स के लिए जो स्वाभाविक रूप से पीसवाइज स्ट्रक्चर में फिट नहीं होते हैं, पेपर एक अफ़ाइन लिफ्टिंग अप्रोच का उपयोग करता है। यह समस्या को एक उच्च-आयामी स्थान में बदल देता है जहाँ फंक्शन को विशेष नॉनलीनियर केस की तरह माना जा सकता है, जिससे NB-EHM फ्रेमवर्क को लागू करना संभव हो जाता है।

मुख्य योगदान

रोबस्ट GLB एल्गोरिदम (GLB-EHM): यह पेपर हैवी-टेल्ड नॉइज़ के तहत GLB के लिए पहला एल्गोरिदम पेश करता है जो $O(1)$ कम्प्यूटेशनल कॉम्प्लेक्सिटी बनाए रखते हुए लगभग इष्टतम रिग्रेट बाउंड $\tilde{O}(T^{\frac{1}{1+\epsilon}})$ प्राप्त करता है। यह अग्रणी गुणांक में $\kappa$ की निर्भरता को हटाकर मौजूदा विधियों में सुधार करता है।
पीसवाइज और नॉनलीनियर एक्सटेंशन: लेखक सफलतापूर्वक रोबस्ट फ्रेमवर्क को पीसवाइज GLB और नॉनलीनियर बैंडिट्स के एक विशेष वर्ग तक विस्तारित करते हैं। वे सिद्ध करते हैं कि रिग्रेट ऑर्डर (regret order) सबलीनियर ( $\tilde{O}(T^\alpha)$ जहाँ $\alpha < 1$ ) बना रहता है, भले ही अंतर्निहित संरचना पीसवाइज कांस्टेंट या स्मूथ नॉनलीनियर हो।
सैद्धांतिक गारंटी: पेपर पैरामीटर एस्टीमेशन के लिए कठोर उच्च-संभावना (high-probability) कॉन्फिडेंस बाउंड स्थापित करता है और रिग्रेट अपर बाउंड्स निकालता है जो लीनियर केस के ज्ञात लोअर बाउंड्स से मेल खाते हैं (लॉगारिदमिक फैक्टर्स तक)।
कम्प्यूटेशनल दक्षता: नॉनलीनियर बैंडिट्स के लिए कर्नेल-आधारित या न्यूरल नेटवर्क दृष्टिकोणों के विपरीत, जो अक्सर $O(T^2)$ या $O(T^3)$ कम्प्यूटेशनल लागत से ग्रस्त होते हैं, प्रस्तावित विधियाँ लंबे टाइम होराइजन के लिए उपयुक्त कम कम्प्यूटेशनल कॉम्प्लेक्सिटी बनाए रखती हैं।

परिणाम

सैद्धांतिक बाउंड्स:
- GLB-EHM के लिए, रिग्रेट $\tilde{O}(d(1+KS)\nu T^{\frac{1}{1+\epsilon}})$ द्वारा बाउंडेड है, जो लोअर बाउंड $\Omega(dT^{\frac{1}{1+\epsilon}})$ की तुलना में लगभग इष्टतम है।
- PGLB-EHM के लिए, रिग्रेट ऑर्डर $\tilde{O}(T^{\frac{1}{1+\epsilon}})$ बना रहता है, जिसके स्थिरांक टुकड़ों की संख्या $m$ और गैप $a$ पर निर्भर करते हैं।
- NB-EHM के लिए, रिग्रेट $\tilde{O}(T^\alpha)$ द्वारा बाउंडेड है, जहाँ $\alpha = \frac{\gamma+1}{\gamma+2} + \frac{(d+2)(1-\epsilon)}{2(\gamma+2)(1+\epsilon)}$ और $\gamma = (d+2)(C_2-1)+1$ है। विशिष्ट स्थितियों ( $\epsilon > \frac{d}{d+4}$ ) के तहत, यह सबलीनियर रिग्रेट सुनिश्चित करता है।
अनुभवजन्य प्रदर्शन (Empirical Performance): सभी प्रस्तावित एल्गोरिदम के लिए संख्यात्मक सिमुलेशन किए गए।
- GLB-EHM का परीक्षण स्टूडेंट टी-डिस्ट्रीब्यूटेड नॉइज़ के साथ लॉजिट मॉडल पर किया गया, जिसने 11.25 सेकंड के औसत रनटाइम के साथ मजबूत प्रदर्शन दिखाया।
- NB-EHM सिमुलेशन ने इष्टतम बिंदु की ओर अभिसरण (convergence) और सबलीनियर रिग्रेट ग्रोथ दिखाया, जो सैद्धांतिक विश्लेषण की पुष्टि करता है।

महत्व और दावे

पेपर का दावा है कि इसकी प्राथमिक महत्ता हैवी-टेल्ड नॉनलीनियर बैंडिट्स के संदर्भ में सांख्यिकीय दक्षता (statistical efficiency) और कम्प्यूटेशनल कॉम्प्लेक्सिटी के बीच के अंतर को पाटने में निहित है।

मजबूती (Robustness): यह प्रदर्शित करता है कि लाइट-टेल्ड सेटिंग्स की विशिष्ट सबलीनियर रिग्रेट गारंटियों से समझौता किए बिना हैवी-टेल्ड नॉइज़ के प्रति मजबूती प्राप्त की जा सकती है।
व्यापकता (Generality): जनरलाइज्ड लीनियर मॉडल्स (GLM), रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस (RKHS), या न्यूरल टेंगेंट कर्नेल्स (NTK) की प्रतिबंधात्मक धारणाओं से आगे बढ़कर, प्रस्तावित NB-EHM एक अधिक सामान्य फ्रेमवर्क प्रदान करता है।
स्केलेबिलिटी (Scalability): प्रति-राउंड $O(1)$ कॉम्प्लेक्सिटी (T के सापेक्ष) इन एल्गोरिदम को लंबे टाइम होराइजन के लिए स्केलेबल बनाती है, जो मौजूदा नॉनलीनियर बैंडिट विधियों की एक बड़ी बाधा को दूर करती है।

लेखक निष्कर्ष निकालते हैं कि हालांकि उन्होंने सबलीनियर रिग्रेट बाउंड स्थापित कर लिया है, लेकिन सामान्य नॉनलीनियर मामले के लिए रिग्रेट लोअर बाउंड स्थापित करने और लिप्सचिट्ज़ निरंतरता (Lipschitz continuity) जैसी धारणाओं को हॉल्डर निरंतरता (Hölder continuity) तक शिथिल करने के लिए भविष्य के कार्य की आवश्यकता है।