🤖 machine learning

Stochastic Linear Bandits with Parameter Noise

यह शोध पत्र पैरामीटर शोर (parameter noise) वाले स्टोकेस्टिक लीनियर बैंडिट्स के लिए टाइट रिग्रेट बाउंड्स स्थापित करता है, यह प्रदर्शित करते हुए कि एक सरल एक्सप्लोर-एक्सप्लोइट एल्गोरिदम विशिष्ट एक्शन सेट्स के लिए $\widetilde{\Theta}(\sqrt{dT})$ का मिनिमैक्स रिग्रेट प्राप्त करता है, जो क्लासिक एडिटिव नॉइज़ मॉडल्स में पाए जाने वाले $d\sqrt{T}$ ऑर्डर में महत्वपूर्ण सुधार करता है।

मूल लेखक: Daniel Ezer, Alon Peled-Cohen, Yishay Mansour

प्रकाशित 2026-05-26

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

CC BY 4.0

मूल लेखक: Daniel Ezer, Alon Peled-Cohen, Yishay Mansour

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

कल्पना कीजिए कि आप एक शेफ हैं जो एक आदर्श व्यंजन बनाने की कोशिश कर रहे हैं, लेकिन आपको सटीक रेसिपी नहीं पता है। आपके पास सामग्री (क्रियाओं) से भरी एक पेंट्री है, और हर बार जब आप खाना बनाते हैं, तो आपको एक टेस्ट टेस्ट (पुरस्कार/रिवॉर्ड) मिलता है। आपका लक्ष्य यह पता लगाना है कि कम से कम असफल व्यंजनों के साथ कौन सा सामग्रियों का संयोजन सबसे अच्छा स्वाद देता है। यही एक "बैंडिट प्रॉब्लम" (bandit problem) का सार है।

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

यह पेपर एक थोड़ा अलग, और आश्चर्यजनक रूप से आसान परिदृश्य पेश करता है: पैरामीटर नॉइज़ (Parameter Noise)।

मुख्य विचार: "बदलता हुआ शेफ" बनाम "शोरयुक्त चम्मच"

इस पेपर की सफलता को समझने के लिए, आइए दो रूपकों का उपयोग करें:

क्लासिक मॉडल (एडिटिव नॉइज़ - Additive Noise): कल्पना कीजिए कि रेसिपी स्थिर है (सूप नमकीन है), लेकिन आपकी स्वाद ग्रंथियां अविश्वसनीय हैं। कभी-कभी आपको नमक महसूस होता है जहाँ नमक नहीं है, और कभी-कभी आप नमक को पहचान नहीं पाते। "शोर" आपके मापन में है।
नया मॉडल (पैरामीटर नॉइज़ - Parameter Noise): कल्पना कीजिए कि आपकी स्वाद ग्रंथियां एकदम सटीक हैं, लेकिन हर बार चम्मच लेने पर सूप खुद बदल जाता है। एक चम्मच शायद थोड़े अधिक नमक वाले बैच से हो सकता है, अगला थोड़ा कम नमक वाला हो सकता है। "शोर" स्वयं सामग्री में है।

लेखक इस दूसरे परिदृश्य का अध्ययन करते हैं। वे पूछते हैं: यदि हर बार प्रयास करने पर सामग्री स्वयं यादृच्छिक (randomly) रूप से बदलती है, तो क्या हम यह पता लगाने में अधिक तेज़ी से सक्षम हैं कि सबसे अच्छी रेसिपी क्या है, बजाय इसके कि सामग्री स्थिर हो लेकिन हमारी स्वाद ग्रंथियां खराब हों?

उत्तर: हाँ! कई मामलों में, "बदलती हुई सामग्री" वाला मॉडल "खराब स्वाद ग्रंथियों" वाले मॉडल की तुलना में सीखना वास्तव में आसान है।

आश्चर्यजनक मोड़: "यूनिट बॉल" पहेली

बैंडिट्स की दुनिया में, यूनिट बॉल (Unit Ball) नामक एक आकार (सोचिए आटे के एक गोल गोले या एक पूर्ण गोले के बारे में) से जुड़ी एक प्रसिद्ध पहेली है।

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

यह ऐसा है जैसे यह महसूस करना कि क्योंकि सूप हर बार थोड़ा बदलता है, आप आधारभूत रेसिपी का पता लगाने के लिए बदलाव के पैटर्न को चख सकते हैं, बजाय इसके कि सूप स्थिर हो लेकिन आपकी जीभ भ्रमित हो।

उपकरण: दो नए एल्गोरिदम

यह पेपर आपकी "पेंट्री" के आकार के आधार पर दो विशिष्ट रणनीतियों (एल्गोरिदम) का प्रस्ताव करता है:

1. VASE (सामान्य पेंट्री के लिए)

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

2. VALEE (गोल पेंट्री / यूनिट बॉल्स के लिए)

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

मुख्य निष्कर्ष

यह पेपर दिखाता है कि जब "शोर" हमारे सेंसर के खराब होने के बजाय पर्यावरण के बदलने (पैरामीटर नॉइज़) से आता है, तो हम अधिक स्मार्ट हो सकते हैं।

विकल्पों की सरल सूचियों के लिए: हम विचरण (यह देखना कि रिवॉर्ड कितना उछलता-कूदता है) का उपयोग कर सकते हैं ताकि स्थिर विकल्पों पर समय बर्बाद करना बंद किया जा सके।
जटिल, गोल विकल्पों के लिए: हम एक बहुत ही सरल "बुनियादी चीज़ों को चखो, फिर प्रतिबद्ध हो जाओ" रणनीति का उपयोग कर सकते हैं जो गणितीय रूप से लगभग पूर्ण है।

लेखकों ने यह भी सिद्ध किया कि आप उनके परिणामों से बेहतर नहीं कर सकते; उन्होंने एक "सबसे खराब स्थिति" (lower bound) बनाई ताकि यह दिखाया जा सके कि इन विशिष्ट स्थितियों में कोई अन्य शेफ उनके एल्गोरिदम की तुलना में तेज़ खाना नहीं बना सकता।

संक्षेप में: यदि दुनिया थोड़ी अराजक है और हर बार देखने पर बदल जाती है, तो आप इसे सीखने में वास्तव में तेज़ हो सकते हैं बजाय इसके कि दुनिया स्थिर हो लेकिन आपका दिन बुरा चल रहा हो।

तकनीकी सारांश: पैरामीटर शोर के साथ स्टोकेस्टिक लीनियर बैंडिट्स

समस्या की परिभाषा
यह कार्य पैरामीटर शोर वाले स्टोकेस्टिक लीनियर बैंडिट्स मॉडल की जांच करता है। इस सेटिंग में, एक लर्नर समय क्षितिज $T$ के दौरान एक एक्शन सेट $\mathcal{A} \subseteq \mathbb{R}^d$ से क्रियाएं $a_t$ चुनकर वातावरण के साथ अंतःक्रिया करता है। मानक एडिटिव नॉइज़ मॉडल (जहाँ रिवॉर्ड $X_t = a_t^\top \theta^\star + \eta_t$ है, जिसमें $\theta^\star$ स्थिर है और शोर $\eta_t$ है) के विपरीत, पैरामीटर शोर मॉडल यह मानता है कि रिवॉर्ड $X_t = a_t^\top \theta_t$ द्वारा दिया जाता है, जहाँ $\theta_t$ एक निश्चित, अज्ञात वितरण $\nu$ से i.i.d. (स्वतंत्र और समान रूप से वितरित) रूप से लिया गया है, जिसका माध्य $\theta^\star$ और कोवेरियेंस मैट्रिक्स $\Sigma$ है।

पेपर एक मुख्य अंतर पर प्रकाश डालता है: पैरामीटर शोर मॉडल में, लर्नर रिवॉर्ड के वेरिएंस (विचरण) को प्रभावित कर सकता है। विशेष रूप से, $\text{Var}(X_t) = a_t^\top \Sigma a_t$ , जबकि एडिटिव नॉइज़ मॉडल में, वेरिएंस केवल वातावरण द्वारा निर्धारित होता है। लेखक नोट करते हैं कि जबकि पैरामीटर शोर मॉडल एडवरसेरियल लीनियर बैंडिट मॉडल (जहाँ $\theta_t$ एक एडवरसरी द्वारा चुना जाता है) का एक रिलैक्सेशन है, यह कुछ ज्यामितीय सेटिंग्स में एडिटिव नॉइज़ मॉडल की तुलना में संभावित रूप से अधिक टाइट (tight) रिग्रेट बाउंड्स की अनुमति देने वाले अद्वितीय संरचनात्मक गुण प्रस्तुत करता है।

कार्यप्रणाली और एल्गोरिदम
लेखक विभिन्न एक्शन सेट ज्योमेट्री के लिए अनुकूलित दो एल्गोरिदम प्रस्तावित करते हैं:

VASE (वैरिएंस अवेयर ऑप्टिमल डिज़ाइन सक्सेसिव एलिमिनेशन):
- लक्ष्य: सामान्य परिमित (finite) एक्शन सेट्स (और कवरिंग आर्गुमेंट्स के माध्यम से अनंत सेट्स)।
- तंत्र: यह एक सक्सेसिव एलिमिनेशन एल्गोरिदम है जो वेरिएंस जानकारी का लाभ उठाता है। प्रत्येक चरण में, यह क्रियाओं को चुनने के लिए एक G-ऑप्टिमल डिज़ाइन $\pi_\ell$ की गणना करता है। यह डिज़ाइन के सपोर्ट में क्रियाओं के वेरिएंस को अनुमानित करने के लिए एक स्टॉपिंग रूल (SR) एल्गोरिदम का उपयोग करता है।
- मुख्य नवाचार: एल्गोरिदम अनुमानित वेरिएंस का उपयोग दो तरीकों से करता है: अन्वेषण (exploration) के लिए आवश्यक नमूनों की संख्या को कम करने के लिए और एक वेटेड लीस्ट स्क्वायर्स एस्टीमेटर में वेट के रूप में। यह वेटिंग सुनिश्चित करती है कि एस्टीमेटर का कोवेरियेंस कम नमूनों के साथ भी नियंत्रित रहे, जिससे वेरिएंस-डिपेंडेंट रिग्रेट बाउंड्स प्राप्त होते हैं।
VALEE (वैरिएंस अवेयर लीनियर एक्सप्लोर-एक्सप्लोइट):
- लक्ष्य: $\ell_p$ यूनिट बॉल्स जहाँ $p \in (1, 2]$ (और उनके ड्यूल नॉर्म्स $q \ge 2$ )।
- तंत्र: यह एक सरल एक्सप्लोर-एक्सप्लोइट एल्गोरिदम है।
  - अन्वेषण (Exploration): एल्गोरिदम मानक बेसिस वेक्टर्स $e_i$ का उपयोग करता है। यह मीडियन-ऑफ-मीन्स (MoM) तकनीक का उपयोग करके माध्य वेक्टर $\theta^\star$ का कोआर्डिनेट-वाइज अनुमान लगाता है। यदि कोवेरियेंस मैट्रिक्स $\Sigma$ अज्ञात है, तो यह पहले बेसिस वेक्टर्स के वेरिएंस का अनुमान लगाता है।
  - शोषण (Exploitation): एक बार जब अनुमान त्रुटि (estimation error) वेरिएंस और समय क्षितिज के सापेक्ष पर्याप्त रूप से कम हो जाती है, तो यह अनुमानित माध्य $\hat{\theta}$ से प्राप्त क्रिया $\hat{a}$ के प्रति प्रतिबद्ध हो जाता है, विशेष रूप से $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$ ।
- मुख्य नवाचार: विश्लेषण $\ell_p$ बॉल की ज्यामिति और पैरामीटर शोर संरचना का लाभ उठाता है। लेखक दिखाते हैं कि बेसिस वेक्टर्स का अन्वेषण करने से अनुमान त्रुटि $\sqrt{\sigma^2(e_i)}$ के समान होती है, जो एडिटिव नॉइज़ मॉडल्स में मानक $\epsilon$ बाउंड की तुलना में अधिक टाइट है। यह एल्गोरिदम को रिवॉर्ड वितरण के वेरिएस स्ट्रक्चर पर निर्भर होने वाले इष्टतम रिग्रेट बाउंड्स प्राप्त करने की अनुमति देता है।

प्रमुख परिणाम
पेपर दोनों अपर और लोअर बाउंड्स स्थापित करता है, यह प्रदर्शित करते हुए कि प्रस्तावित एल्गोरिदम विशिष्ट सेटिंग्स के लिए मिनिमैक्स ऑप्टिमल (लॉगैरिद्मिक फैक्टर्स तक) हैं।

सामान्य परिमित एक्शन सेट्स ( $K$ क्रियाएं):
- अपर बाउंड: VASE $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$ का रिग्रेट प्राप्त करता है, जहाँ $M_\sigma$ एक वेरिएंस-डिपेंडेंट मात्रा है जो $\max_a \sigma^2(a)$ द्वारा सीमित है।
- लोअर बाउंड: $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ का एक लोअर बाउंड सिद्ध किया गया है, जो दिखाता है कि जब $\log(K) \approx d$ हो, तो अपर बाउंड लॉगैरिद्मिक फैक्टर्स तक टाइट है।
$\ell_p$ यूनिट बॉल्स ( $p \le 2$ ):
- ज्ञात कोवेरियेंस: VALEE $\tilde{O}(d + \sqrt{dT \sigma^2_q})$ का रिग्रेट प्राप्त करता है, जहाँ $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$ है। इसे $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$ के मिलान वाले लोअर बाउंड के माध्यम से इष्टतम दिखाया गया है।
- अज्ञात कोवेरियेंस: VALEE एक अतिरिक्त एडिटिव टर्म (term) का सामना करता है, जिसके परिणामस्वरूप $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$ का रिग्रेट होता है। लेखक नोट करते हैं कि यह एडिटिव टर्म वेरिएंस एस्टिमेशन चरण से उत्पन्न होता है।
$\ell_p$ यूनिट बॉल्स ( $p > 2$ ):
- पेपर $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ का एक लोअर बाउंड प्रदान करता है, जो इन ज्योमेट्रीज़ में एडवरसेरियल सेटिंग के लिए ज्ञात लोअर बाउंड से मेल खाता है।

महत्व और दावे
पेपर एक "जिज्ञासु मामले" को हल करने का दावा करता है जहाँ लीनियर बैंडिट्स में एडिटिव नॉइज़ मॉडल अक्सर $\ell_2$ यूनिट बॉल जैसी विशिष्ट एक्शन सेट्स के लिए एडवरसेरियल मॉडल ( $\sqrt{dT}$ ) की तुलना में खराब रिग्रेट बाउंड्स ( $d\sqrt{T}$ ) देता है। लेखक प्रदर्शित करते हैं कि पैरामीटर शोर मॉडल उस अंतर्ज्ञान के साथ अधिक निकटता से संरेखित होता है कि स्टोकेस्टिक मॉडल एडवरसेरियल मॉडल्स की तुलना में आसान होने चाहिए।

टाइट बाउंड्स: $p \le 2$ के लिए $\ell_p$ बॉल्स के लिए, पैरामीटर शोर मॉडल $\sqrt{dT \sigma^2_q}$ के क्रम के रिग्रेट बाउंड्स की अनुमति देता है, जो एडिटिव नॉइज़ मॉडल्स में विशिष्ट $d\sqrt{T}$ बाउंड की तुलना में काफी छोटा हो सकता है जब वेरिएंस कम हो।
संरचनात्मक लाभ: परिणाम इस बात पर प्रकाश डालते हैं कि रियलाइजेशन (न केवल अपेक्षा/expectation) की रैखिकता और लर्नर द्वारा वेरिएस को प्रभावित करने की क्षमता बेहतर बाउंड्स प्राप्त करने के लिए महत्वपूर्ण है।
सरलता: आश्चर्यजनक रूप से, $\ell_p$ बॉल्स ( $p \le 2$ ) के लिए इष्टतम रिग्रेट एक बहुत ही सरल एक्सप्लोर-एक्सप्लोइट एल्गोरिदम (VALEE) का उपयोग करके प्राप्त किया जा सकता है, जो एडिटिव नॉइज़ सेटिंग्स में अक्सर आवश्यक जटिल ऑप्टिमल डिज़ाइन एल्गोरिदमों के विपरीत है।

लेखक निष्कर्ष निकालते हैं कि जबकि $p \le 2$ के लिए उनके परिणाम (लॉग्स तक) इष्टतम हैं जब कोवेरियेंस ज्ञात होता है, अज्ञात कोवेरियेंस मामला ( $T^{1/3}$ टर्म के साथ) एक खुला अंतराल छोड़ता है जिसे भविष्य का कार्य संबोधित कर सकता है। वे $p > 2$ के लिए लोअर बाउंड से मेल खाने वाले एल्गोरिदम के डिज़ाइन को भी एक खुला प्रश्न (open question) के रूप में छोड़ देते हैं।

मुख्य विचार: "बदलता हुआ शेफ" बनाम "शोरयुक्त चम्मच"

आश्चर्यजनक मोड़: "यूनिट बॉल" पहेली

उपकरण: दो नए एल्गोरिदम

मुख्य निष्कर्ष

इसी तरह के और पेपर