📊 statistics

Sharper Guarantees for Misspecified Kernelized Bandit Optimization

यह शोध पत्र सिद्ध करता है कि कर्नेलकृत बैंडिट ऑप्टिमाइज़ेशन (kernelized bandit optimization) में मिसस्पेसिफिकेशन पेनल्टी को — ऑफलाइन (सिंपल रिग्रेट) और ऑनलाइन (क्युमुलेटिव रिग्रेट) दोनों ही मामलों में — ऑफलाइन सेटिंग में स्पेक्ट्रल लोकलाइजेशन (spectral localization) और ऑनलाइन सेटिंग में स्पेक्ट्रल डोमेन-स्प्लिटिंग (spatial domain-splitting) का लाभ उठाकर, जटिलता के वर्गमूल कारक (square-root-of-complexity factor) से घटाकर एक लॉगरिदमिक या पॉलीलॉगरिदमिक (logarithmic or polylogarithmic) कारक तक कम किया जा सकता है।

मूल लेखक: Davide Maran, Csaba Szepesvári

प्रकाशित 2026-05-08✓ Author reviewed ⓘ

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

CC BY 4.0

मूल लेखक: Davide Maran, Csaba Szepesvári

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

एक बड़ी तस्वीर: "बादलों में पहाड़" की समस्या

कल्पना कीजिए कि आप एक विशाल पर्वत श्रृंखला के ऊपर एक हेलीकॉप्टर में उड़ रहे एक खोजकर्ता हैं। आपका काम सरल है: एकल सबसे ऊँची चोटी को खोजना। पेच यह है कि पूरी पर्वत श्रृंखला घने बादलों में लिपटी हुई है — उड़ते समय, आप वास्तव में पहाड़ों को देख नहीं सकते।

आप जो कर सकते हैं वह यह है कि मानचित्र पर किसी भी स्थान की ओर इशारा करें और पायलट को वहां उड़ने के लिए कहें। एक बार जब आप वहां पहुँच जाते हैं, तो आप उस स्थान पर एक एकल ऊंचाई का माप लेते हैं, जो आपके मानचित्र को थोड़ा परिष्कृत करता है। फिर आप अगले स्थान की ओर इशारा करते हैं, वहां उड़ते हैं, माप लेते हैं, और इसी तरह आगे बढ़ते हैं। हर माप में समय और ईंधन खर्च होता है, इसलिए आप हर जगह माप नहीं ले सकते।

एक चीज़ जो आप पहले से जानते हैं — और यह महत्वपूर्ण है — वह यह है कि पर्वत श्रृंखला बहुत अधिक ऊबड़-खाबड़ नहीं है: ऊंचाइयां मानचित्र पर सुचारू रूप से बदलती हैं, जो एक सीमित मिसस्पेफिकेशन एरर (misspecification error) तक सीमित है। (यह पेपर के स्पेक्ट्रल / RKHS रेगुलैरिटी धारणा का सरल भाषा वाला संस्करण है: वास्तविक ऊंचाई फलन उस श्रेणी का हिस्सा है जिसकी अपेक्षा मॉडल करता है, लेकिन केवल अनुमानित रूप से।)

यह कर्नेलइज़्ड बैंडिट ऑप्टिमाइज़ेशन (kernelized bandit optimization) का सेटअप है: "हेलीकॉप्टर खोजकर्ता" एल्गोरिदम है, "पहाड़" अज्ञात फलन है जिसे एल्गोरिदम अधिकतम करने की कोशिश कर रहा है, और प्रत्येक "उड़ान + माप" फलन के एक प्रश्न (query) को दर्शाता है।

पैसे पाने के दो तरीके

यह पेपर इस बात का अध्ययन करता है कि यह आंकने के दो अलग-अलग तरीके हैं कि खोजकर्ता कितना अच्छा है।

ऑफलाइन परिदृश्य — अंतिम अनुमान के लिए भुगतान किया जाता है

आपको हेलीकॉप्टर यात्राओं का एक निश्चित बजट दिया जाता है। आप अपने सभी माप लेते हैं, अपना सर्वश्रेष्ठ मानचित्र बनाते हैं, और अंत में आप एक स्थान की ओर इशारा करते हैं — आपका अंतिम अनुमान कि सबसे ऊँची चोटी कहाँ है।

आपको कितनी चूक हुई (how much you miss) के आधार पर भुगतान किया जाता है:

वास्तविक उच्चतम शिखर की ऊंचाई − आपके अंतिम अनुमान की ऊंचाई = आपकी चूक
छोटी चूक = बेहतर भुगतान।

इसे ही पेपर में सिंपल रिग्रेट (simple regret) कहा गया है। शुरुआती माप केवल इस हद तक मायने रखते हैं कि वे आपके अंतिम अनुमान में मदद करते हैं।

ऑनलाइन परिदृश्य — हर यात्रा के लिए भुगतान किया जाता है

अब कल्पना कीजिए कि खोजकर्ता को दौर-दर-दौर भुगतान किया जाता है। हर बार जब वे कहीं उड़ते हैं, तो उस स्थान की ऊंचाई उनके चल रहे कुल योग (running total) में जुड़ जाती है। सभी यात्राओं के बाद, चल रहे कुल योग की तुलना उस कुल से की जाती है जो वे तब एकत्र करते यदि उन्हें शुरुआत से ही सबसे ऊंचे शिखर के स्थान का पता होता और वे बस वहीं उड़ते रहते।

यह अंतर उन दोनों के बीच का है: कुल योग जो खोजकर्ता ने एकत्र किया और वह कुल योग जो वे तब एकत्र करते यदि उन्हें सबसे ऊंचे शिखर का स्थान पता होता। इसे संचयी पछतावा (cumulative regret) कहा जाता है: वह ऊंचाई जो खोजकर्ता ने पूरी खोज के दौरान छोड़ दी।

ऑनलाइन समस्या कठिन है, क्योंकि हर खराब तरीके से चुना गया माप सीधे आपके भुगतान को नुकसान पहुँचाता है — आप कुछ शुरुआती उड़ानों को बिना किसी परिणाम के केवल अन्वेषण (exploration) के लिए "खर्च" नहीं कर सकते।

पेपर वास्तव में क्या करता है

दशकों से, सिद्धांत कहता आया है कि: जब आपका मानचित्र मॉडल मिसस्पेफाइड (misspecified) होता है (अर्थात वास्तविक पहाड़ उस प्रकार का फलन नहीं है जिसकी अपेक्षा मॉडल करता है, जिसमें कुछ त्रुटि $\varepsilon$ है), तो यह मिसस्पेफिकेशन कर्नेल की जटिलता के साथ बढ़ने वाले एक कारक द्वारा प्रवर्धित (amplified) हो जाता है; ऑफलाइन गारंटी में वह कारक $\sqrt{d_\mathrm{eff}}$ (कर्नेल का प्रभावी आयाम) था; ऑनलाइन गारंटी में यह $\sqrt{\gamma_n}$ (n राउंड के बाद अधिकतम सूचना लाभ) था।

यह पेपर सिद्ध करता है कि कर्नेल के एक बड़े वर्ग के लिए, उस प्रवर्धन को जटिलता के वर्गमूल (square-root-of-complexity) निर्भरता से घटाकर एक लॉगारिदमिक (logarithmic) या पॉलीलॉगारिदमिक (polylogarithmic) निर्भरता तक कम किया जा सकता है। दूसरे शब्दों में: मॉडल के बारे में थोड़ा गलत होने की लागत उतनी नहीं बढ़ती जितनी कि लोग सोचते थे।

इसका तरीका है लोकलाइजेशन (localization):

स्पेक्ट्रल लोकलाइजेशन (Spectral localization) ऑफलाइन सेटिंग में उस मात्रा को नियंत्रित करता है जिसे अप्रोक्सिमेशन ऑपरेटर का लेबेग कांस्टेंट (Lebesgue constant) कहा जाता है, जो वास्तव में यह तय करता है कि मिसस्पेफिकेशन आपको कितना नुकसान पहुँचाता है। पेपर सिद्ध करता है कि एक-आयामी मोनोटोन स्पेक्ट्रा के लिए लॉगरिदमिक प्रवर्धन और मल्टीवेरिएट फूरियर-डायगोनल प्रोडक्ट कर्नेल्स के लिए पॉलीलॉगारिदमिक प्रवर्धन होता है।
डोमेन स्प्लिटिंग (Domain splitting) ऑनलाइन सेटिंग में स्थानिक समकक्ष (spatial counterpart) है: मानचित्र को क्षेत्रों में विभाजित करें, प्रत्येक पर एल्गोरिदम चलाएं, और स्थानीय त्रुटियों को वैश्विक स्तर पर प्रवर्धित होने से रोकें। यह ऑनलाइन मिसस्पेफिकेशन टर्म से अतिरिक्त $\sqrt{\gamma_n}$ कारक को हटा देता है, जिससे संचयी पछतावे का एक $\widetilde{\mathcal O}(\sqrt{\gamma_n n} + n\varepsilon)$ का बाउंड प्राप्त होता है।

एक-वाक्य का सार

यह अधिक सावधानी बरतने के बारे में है कि मिसस्पेफिकेशन त्रुटि कहाँ संचित (compound) हो सकती है — ऑफलाइन समस्या के लिए स्पेक्ट्रली, और ऑनलाइन समस्या के लिए स्थानिक रूप से — जिससे खोजकर्ता का भुगतान (दोनों रिग्रेट धारणाओं में) पिछले परिणामों की तुलना में मॉडलिंग त्रुटियों के प्रति बहुत अधिक मजबूत हो जाता है।

तकनीकी सारांश: मिसस्पेसिफाइड कर्नलाइज्ड बैंडिट ऑप्टिमाइजेशन के लिए शार्पर गारंटी

समस्या विवरण (Problem Statement)

यह शोध पत्र मिसस्पेसिफाइड कर्नलाइज्ड बैंडिट ऑप्टिमाइजेशन की समस्या को संबोधित करता है, जिसमें एक एजेंट एक अज्ञात लक्ष्य फलन (target function) $f$ को एक कर्नेल $k$ का उपयोग करके अनुकूलित (optimize) करने का प्रयास करता है, लेकिन वास्तविक फलन $f$ उस रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस (RKHS) $\mathcal{H}$ में नहीं होता है जिससे $k$ संबद्ध है। इसके बजाय, $f$ को एक फलन $f^\star \in \mathcal{H}$ द्वारा एक समान सन्निकटन त्रुटि (uniform approximation error) या मिसस्पेसिफिकेशन स्तर $\varepsilon = \sup_{x} |f(x) - f^\star(x)|$ के साथ अनुमानित किया जाता है।

मुख्य चुनौती यह है कि (बैंडिट्स जैसे) अनुक्रमिक निर्णय लेने और अनुकूल डेटा संग्रह (adaptive data collection) के तहत, मिसस्पेसिफिकेशन त्रुटियां सुपरवाइज्ड लर्निंग की तरह केवल औसत (average out) नहीं होती हैं; इसके बजाय, वे ज्यामितीय प्रवर्धन (geometric amplification) से गुजरती हैं। रैखिक सेटिंग्स (linear settings) में, यह प्रवर्धन आयाम $d$ में $\Theta(\sqrt{d}\,\varepsilon)$ के रूप में स्केल करता है। कर्नेल सेटिंग्स में, पूर्व कार्य (जैसे बोगुनोविक और क्रौज़, 2021) ने दिखाया कि सिंपल-रिग्रेट बाउंड्स में मिसस्पेसिफिकेशन पेनल्टी $\sqrt{\gamma_n}\,n\varepsilon$ के रूप में स्केल करती है, जहाँ $\gamma_n$ अधिकतम सूचना लाभ (maximum information gain) है। व्यावहारिक महत्व के कई कर्नेल्स (जैसे उच्च स्मूथनेस वाले मेटर्न कर्नेल्स) के लिए, यह $\sqrt{\gamma_n}$ कारक $n$ के लगभग रैखिक होता है, जो इन बाउंड्स को तब तक निरर्थक (vacuous) बना देता है जब तक कि $\varepsilon$ अत्यंत छोटा ( $O(n^{-1/2})$ ) न हो।

यह शोध पत्र जांच करता है कि क्या वह निराशावादी वर्स्ट-केस प्रवर्धन (pessimistic worst-case amplification) अंतर्निहित है या क्या इसे कर्नेल पर विशिष्ट स्पेक्ट्रल और संरचनात्मक धारणाओं के तहत कम किया जा सकता है।

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

लेखक एक एकल एकीकृत सिद्धांत: लोकलाइजेशन (localization) के तहत दो अलग-अलग सेटिंग्स का विश्लेषण करते हैं — ऑफलाइन ऑप्टिमाइजेशन (निश्चित डेटासेट) और ऑनलाइन ऑप्टिमाइजेशन (अनुकूली अंतःक्रिया)।

1. ऑफलाइन ऑप्टिमाइजेशन: स्पेक्ट्रल लोकलाइजेशन (Spectral Localization)

ऑफलाइन सेटिंग में, एजेंट एक वितरण $D$ से i.i.d. रूप से लिए गए एक निश्चित डेटासेट पर कार्य करता है। विश्लेषण का आधार कर्नेल रिज रिग्रेशन (KRR) को एस्टीमेटर के रूप में उपयोग करना है।

ऑपरेटर-थ्योरेटिक फ्रेमवर्क: KRR की पॉइंटवाइज त्रुटि को रेगुलराइज्ड पॉपुलेशन एप्रोक्सिमेशन ऑपरेटर $P_\tau$ के लेबेग कॉन्स्टेंट (Lebesgue constant) $\Lambda(P_\tau)$ के संदर्भ में वर्णित किया गया है। लेखक सिद्ध करते हैं कि सिंपल-रिग्रेट बाउंड में मिसस्पेसिफिकेशन टर्म $\Lambda(P_\tau)\,\varepsilon$ द्वारा नियंत्रित होता है।
स्पेक्ट्रल विश्लेषण: जेनेरिक बाउंड $\Lambda(P_\tau) \le \sqrt{d_{\mathrm{eff}}}$ $Λ (P_{τ}) \leq d_{eff}$ (जहाँ $d_{\mathrm{eff}}$ $d_{eff}$ प्रभावी आयाम है) पर निर्भर रहने के बजाय, वे कर्नेल की स्पेक्ट्रल संरचना से शार्पर बाउंड्स निकालते हैं:
- वे लॉगैरिद्मिक स्पेक्ट्रल लेबेग ग्रोथ की अवधारणा पेश करते हैं, जो $\Lambda(P_\tau)$ को आइगेनवैल्यू अनुक्रम के डिस्क्रीट डेरिवेटिव के $\ell_1$ -नॉर्म से जोड़ता है।
- मोनोटोन स्पेक्ट्रा (जैसे पीरियोडिक मेटर्न कर्नेल्स) वाले कर्नेल्स के लिए, वे सिद्ध करते हैं कि $\Lambda(P_\tau) \lesssim \log(e + \kappa/\tau)$ ।
- मल्टीवेरिएट फूरियर-डायगोनल प्रोडक्ट कर्नेल्स के लिए, वे $\log^{2m-1}(e + \kappa^m/\tau)$ क्रम का पॉ लिरिक्स (polylogarithmic) प्रवर्धन प्राप्त करते हैं।
- उन कर्नेल्स के लिए जो पॉलिनोमियल आइजनडिके (polynomial eigendecay) (D2) का पालन करते हैं, वे दिखाते हैं कि एक मोनोटोन-एनवेलप कर्नेल का निर्माण किया जा सकता है जिसमें समान RKHS नॉर्म प्रॉपर्टीज हों लेकिन गैर-बढ़ता हुआ स्पेक्ट्रम हो, जिससे लॉगरिदमिक / पॉ लिरिक्स बाउंड्स प्राप्त होते हैं।
- इसके विपरीत, वे एक काउंटर-एग्जांपल प्रस्तुत करते हैं जो दिखाता है कि केवल पॉलिनोमियल प्रभावी आयाम (D1) ही लॉगरिदमिक प्रवर्धन के लिए पर्याप्त नहीं है; विशिष्ट स्पेक्ट्रल स्मूथनेस आवश्यक है।

2. ऑनलाइन ऑप्टिमाइजेशन: स्पेक्ट्रल लोकलाइजेशन (Spatial Localization)

ऑनलाइन सेटिंग में, एजेंट क्वेरी पॉइंट्स को एडैप्टिव रूप से चुनता है ताकि संचयी रिग्रेट (cumulative regret) को कम किया जा सके। ऑफलाइन स्पेक्ट्रल विश्लेषण सीधे लागू नहीं होता क्योंकि डेटा अब i.i.d. नहीं है।

डोमेन-स्प्लिटिंग एल्गोरिदम: लेखक $\pi$ -GP-UCB एल्गोरिदम (जैनज़ एट अल., 2020) को संशोधित करते हैं। एल्गोरिदम इनपुट डोमेन को क्षेत्रों (regions) में विभाजित करता है; एक बार जब कोई क्षेत्र पर्याप्त सैंपल (एक थ्रेशोल्ड) एकत्र कर लेता है, तो उसे $2^m$ सब-रीजन में विभाजित कर दिया जाता है।
लोकलाइज्ड एस्टीमेशन: प्रत्येक क्षेत्र के लिए एक अलग KRR एस्टीमेट फिट किया जाता है। एक्सप्लोरेशन बोनस (UCB) में एक टर्म शामिल किया जाता है जो $\varepsilon\sqrt{N_A/\lambda}$ के समानुपाती है, जहाँ $N_A$ क्षेत्र $A$ में स्थानीय सैंपल काउंट है।
धारणाएं (Assumptions): विश्लेषण के लिए आवश्यक है:
- D2+ (सब-डोमेन पर पॉलिनोमियल आइजनडिके): छोटे सब-डोमेन पर प्रतिबंधित होने पर आइजनवैल्यूज तेजी से घटते हैं।
- D3 (बाउंडेड आइजनफंक्शंस): आइजनफंक्शंस सब-डोमेन पर यूनिफॉर्मली बाउंडेड हैं।
तंत्र (Mechanism): डोमेन को विभाजित करना मिसस्पेसिफिकेशन त्रुटि को स्थानीय रूप से सीमित करता है। सब-डोमेन आइजनडिके प्रत्येक छोटे क्षेत्र के भीतर सूचना लाभ को कम रखता है, जिससे स्थानीय मिसस्पेसिफिकेशन त्रुटियों को वैश्विक रूप से बढ़ने से रोका जा सके।

मुख्य योगदान और परिणाम (Key Contributions and Results)

ऑफलाइन

थ्योरम 3.1 और कोरोलरी 3.2: उच्च-संभावना वाले सिंपल-रिग्रेट बाउंड्स स्थापित करते हैं जिनका मिसस्पेसिफिकेशन टर्म $\Lambda(P_\tau)\,\varepsilon$ है।
थ्योरम 3.8 और कोरोलरी 3.9: सिद्ध करते हैं कि लॉगरिदमिक स्पेक्ट्रल लेबेग ग्रोथ और गैर-बढ़ते आइजनवैल्यूज वाले कर्नेल्स के लिए, लेबेग कॉन्स्टेंट $O(\log(1/\tau))$ के रूप में स्केल करता है, जो लॉगरिदमिक मिसस्पेसिफिकेशन प्रवर्धन देता है — जो जेनेरिक $\sqrt{d_{\mathrm{eff}}}$ की तुलना में एक महत्वपूर्ण सुधार है।
थ्योरम 3.12: इन परिणामों को $O(\log^{2m-1}(1/\tau))$ क्रम के पॉल लिरिक्स प्रवर्धन वाले मल्टीवेरिएट प्रोडक्ट कर्नेल्स तक विस्तारित करता है।
थ्योरम 3.11: सिद्ध करता है कि केवल पॉलिनोमियल प्रभावी आयाम ही लॉगरिदमिक प्रवर्धन के लिए पर्याप्त नहीं है; विशिष्ट स्पेक्ट्रल संरचना (स्मूथनेस / मोनोटोनिसिटी) आवश्यक है।

ऑनलाइन

थ्योरम 4.3: संशोधित $\pi$ -GP-UCB एल्गोरिदम के लिए एक संचयी रिग्रेट बाउंड सिद्ध करता है जो
$\widetilde{O}\!\left(\sqrt{\gamma_n n} + n\varepsilon\right)$
के क्रम का है। यह पिछले कार्य (बोगुनोविक और क्रौज़, 2021) के मिसस्पेसिफिकेशन टर्म से अतिरिक्त $\sqrt{\gamma_n}$ कारक को हटा देता है, जिसने $\widetilde{O}(\sqrt{\gamma_n n} + \sqrt{\gamma_n}\,n\varepsilon)$ दिया था।
निहितार्थ (Implication): मेटर्न कर्नेल्स के लिए जहाँ $\gamma_n \asymp n^{m/(m+2\nu)}$ , नया बाउंड $n\varepsilon$ टर्म तक इष्टतम वेल-स्पेसिफाइड रेट को रिकवर करता है, जबकि पिछला बाउंड गैर-निरर्थक होने के लिए $\varepsilon \lesssim n^{-1/2}$ की आवश्यकता रखता था।

महत्व और दावे (Significance and Claims)

यह शोध पत्र तर्क देता है कि कर्नेलाइज्ड बैंडिट्स में वर्स्ट-केस मिसस्पेसिफिकेशन प्रवर्धन अंतर्निहित नहीं है, बल्कि अतिरिक्त स्पेक्ट्रल या संरचनात्मक धारणाओं के तहत अक्सर टाला जा सकता है।

लोकलाइजेशन सिद्धांत। केंद्रीय अंतर्दृष्टि यह है कि मिसस्पेसिफिकेशन कम हानिकारक हो जाता है जब सन्निकटन (approximation) समस्या को लोकलाइज किया जा सकता है।
- ऑफलाइन सेटिंग में, लोकलाइजेशन स्पेक्ट्रल है: $\Lambda(P_\tau)$ को स्पेक्ट्रल स्मूथनेस के माध्यम से नियंत्रित करना वैश्विक प्रवर्धन को रोकता है।
- ऑनलाइन सेटिंग में, लोकलाइजेशन स्पेशियल (स्थानिक) है: डोमेन स्प्लिटिंग स्थानीय मिसस्पेसिफिकेशन त्रुटियों को प्रति-क्षेत्र सूचना लाभ को कैप करके वैश्विक रूप से बढ़ने से रोकती है।
बाउंड्स की टाइटनेस। लेखक प्रदर्शित करते हैं कि जबकि जेनेरिक बाउंड्स निराशावादी हैं, विशिष्ट कर्नेल क्लासेस (जैसे कि वे जिनमें मोनोटोन स्पेक्ट्रा या प्रोडक्ट स्ट्रक्चर है) बहुत शार्पर गारंटी प्रदान करते हैं।
सीमाएं। यह दिखाया गया है कि केवल पॉलिनोमियल प्रभावी आयाम शार्प बाउंड्स के लिए पर्याप्त नहीं है (थ्योरम 3.11); सामान्य सेटिंग्स में शार्पर ऑनलाइन गारंटी के लिए न्यूनतम संरचनात्मक धारणाओं की पहचान करना अभी भी खुला विषय है।
सैद्धांतिक दायरा। यह कार्य विशुद्ध रूप से सैद्धांतिक है, जो दिए गए बाउंड्स और काउंटर-एग्जांपल के लिए प्रमाण प्रदान करता है। यह नए प्रायोगिक प्रोटोकॉल का प्रस्ताव नहीं करता है और न ही प्रत्यक्ष व्यावहारिक अनुप्रयोगों का दावा करता है; बल्कि, यह मिसस्पेसिफिकेशन के अनुक्रमिक निर्णय लेने में सैद्धांतिक समझ को परिष्कृत करता है।

संक्षेप में: यह शोध पत्र एक परिष्कृत ऑपरेटर-थ्योरेटिक और एल्गोरिद्मिक फ्रेमवर्क प्रदान करता है जो कर्नेलाइज्ड बैंडिट्स में मॉडल-मिसस्पेसिफिकेशन पेनल्टी को कर्नेल के स्पेक्ट्रल गुणों और स्थानीयकृत एस्टीमेशन रणनीतियों के उपयोग के आधार पर, संभावित रूप से रैखिक या स्क्वायर-रूट कारक से घटाकर लॉगरिदमिक या कांस्टेंट कारकों तक कम करता है।