🤖 machine learning

Near-Optimal Regret in Adversarial Kernel Bandits

यह शोधपत्र एडवर्सरियल कर्नेल बैंडिट्स के लिए एक नवीन एक्सपोनेंशियल-वेट्स एल्गोरिदम का प्रस्ताव करता है जो स्टोकेस्टिक सेटिंग से मेल खाने वाला एक नियर-ऑप्टिमल रिग्रेट बाउंड प्राप्त करता है, जिससे पूर्व दरों में सुधार होता है और मेटर्न (Matérn) जैसे कर्नेल्स के लिए प्रतिबंधात्मक धारणाओं को हटाया जाता है।

मूल लेखक: Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett, Kevin Jamieson

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

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

CC BY 4.0

मूल लेखक: Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett, Kevin Jamieson

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

मुख्य विचार: "रहस्यमयी फंक्शन का अनुमान लगाओ" खेल

कल्पना कीजिए कि आप एक चालाक प्रतिद्वंद्वी के खिलाफ एक उच्च-दांव वाला खेल खेल रहे हैं।

सेटअप: आपके पास चुनने के लिए विकल्पों की एक विशाल सूची है (मान लीजिए, आइसक्रीम के हजारों अलग-अलग फ्लेवर)।
लक्ष्य: आप वह फ्लेवर चुनना चाहते हैं जो समय के साथ आपको सबसे अधिक खुशी दे।
चुनौती: आप खुशी के स्तरों को नहीं जानते। हर बार जब आप एक फ्लेवर चुनते हैं, तो प्रतिद्वंद्वी गुप्त रूप से तय करता है कि आपको कितनी खुशी मिलेगी। आपको केवल उस एक फ्लेवर के लिए खुशी का स्कोर पता चलता है जिसे आपने चुना है। आपको अन्य फ्लेवरों के स्कोर दिखाई नहीं देते।
"प्रतिद्वंद्वी" (Adversary): प्रतिद्वंद्वी रैंडम नहीं है; वह आपको विफल करने की कोशिश कर रहा है। वह खुशी के नियमों को हर दिन बदल सकता है, जब तक कि वह एक विशिष्ट "स्मूथनेस" (smoothness) नियम का पालन करता है (वह खुशी को एक फ्लेवर से दूसरे पूरी तरह से असंबंधित फ्लेवर तक बहुत अचानक या अजीब तरीके से नहीं बदल सकता)।

कंप्यूटर विज्ञान में, इसे एडवर्सरियल कर्नेल बैंडिट (Adversarial Kernel Bandit) समस्या कहा जाता है। "कर्नेल" का अर्थ केवल यह है कि खुशी के स्कोर एक सुचारू, जटिल पैटर्न (जैसे कि पहाड़ियों और घाटियों का परिदृश्य) का पालन करते हैं, न कि एक साधारण सीधी रेखा का।

समस्या: पिछले प्रयास क्यों विफल हुए

लंबे समय से, शोधकर्ताओं के पास इस खेल के लिए एक अच्छी रणनीति थी, लेकिन इसमें एक बड़ी खामी थी। उन्होंने उन कुछ बिंदुओं को देखकर छिपे हुए खुशी के परिदृश्य (landscape) का अनुमान लगाने की कोशिश की जहाँ वे पहले जा चुके थे।

हालाँकि, क्योंकि संभावनाओं का "परिदृश्य" अविश्वसनीय रूप से जटिल है (गणितीय रूप से, यह "अनंत-आयामी" या infinite-dimensional है), उनका अनुमान लगाने वाला टूल कभी-कभी अनियंत्रित हो जाता था। यह एक ऐसा मान (value) अनुमान लगाने की कोशिश करता था जो इतना बड़ा होता कि गणित ही टूट जाता। इसे ठीक करने के लिए, पिछले शोधकर्ताओं (जैसे चैटरजी एट अल.) को प्रतिद्वंद्वी पर एक बहुत सख्त सीमा लगानी पड़ी: उन्हें यह मानना पड़ा कि प्रतिद्वंद्वी "रैंक-वन" (rank-one) है।

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

समाधान: "स्मार्ट गेसिंग" एल्गोरिदम

लेखकों ने एक नया एल्गोरिदम बनाया है जो उस प्रतिबंधात्मक "सिंगल रैंप" धारणा के बिना काम करता है। वे इसे "ए एक्सपोनेंशियल वेट्स एल्गोरिदम विद अ रेगुलराइज्ड एस्टिमेटर एंड अ करेक्शन टर्म" कहते हैं।

यह कैसे काम करता है, इसे तीन सरल चरणों में समझा जा सकता है:

1. "रफ ड्राफ्ट" अनुमान (रेगुलराइज्ड एस्टिमेटर)
जब एल्गोरिदम छिपे हुए खुशी के परिदृश्य का अनुमान लगाने की कोशिश करता है, तो यह "रेगुलराइजेशन" नामक तकनीक का उपयोग करता है।

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

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

उदाहरण: यह एक ऐसे शेफ की तरह है जिसे पता है कि उसका ओवन तापमान से 10 डिग्री कम चलता है। वे केवल तापमान का अनुमान नहीं लगाते; वे उस त्रुटि की भरपाई करने के लिए रेसिपी में ठीक 10 डिग्री जोड़ देते हैं।
यह क्यों महत्वपूर्ण है: इस विशिष्ट "करेक्शन टर्म" को जोड़कर, एल्गोरिदम सुरक्षा "गुरुत्वाकर्षण" के कारण होने वाली त्रुटि को रद्द कर देता है। यह एल्गोरिदम को प्रतिद्वंद्वी के जटिल, गैर-रेखीय (non-linear) तरीकों को बिना टूटे संभालने की अनुमति देता है।

3. "एक्सप्लोरेशन" मिश्रण
एल्गोरिदम केवल उस फ्लेवर को नहीं चुनता जिसे वह सबसे अच्छा मानता है। यह यह सुनिश्चित करने के लिए कि वह किसी छिपे हुए रत्न (gem) को मिस न कर दे, थोड़ा सा रैंडम टेस्टिंग (exploration) मिलाता है। यह सुनिश्चित करता है कि "गुरुत्वाकर्षण" बल नियंत्रण में रहे।

परिणाम: यह क्यों मायने रखता है

लेखकों ने सिद्ध किया है कि उनकी नई विधि "नियर-ऑप्टिमल" (near-optimal) है।

पुराना तरीका: यदि प्रतिद्वंद्वी जटिल था (जैसे कि मेटर्न कर्नेल, जिसका उपयोग कई वास्तविक विज्ञान समस्याओं में किया जाता है), तो पुराना तरीका धीमा और अक्षम था। यह एक भारी बैकपैक के साथ मैराथन दौड़ने जैसा था।
नया तरीका: उनका तरीका इस प्रकार के खेल के लिए सबसे अच्छे संभावित तरीके की गति से चलता है।
- मेटर्न कर्नेल (Matérn kernel) के लिए (विज्ञान में उपयोग किया जाने वाला एक मानक टूल), उन्होंने गति में काफी सुधार किया, जिससे "सिंगल रैंप" प्रतिबंध की आवश्यकता समाप्त हो गई।
- स्क्वेयर्ड एक्सपोनेंशियल कर्नेल (Squared Exponential kernel) के लिए, उन्होंने सबसे अच्छी ज्ञात गति से मेल खाया और साथ ही प्रतिबंधात्मक धारणाओं को भी हटा दिया।

निष्कर्ष

इस पेपर को एक जीपीएस (GPS) नेविगेशन सिस्टम के अपग्रेड के रूप में देखें।

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

परिणामस्वरूप, यह एक ऐसी प्रणाली है जो तेजी से सीखती है, कम गलतियां करती है, और पिछले तरीकों की तुलना में बहुत अधिक जटिल, वास्तविक दुनिया के परिदृश्यों को संभाल सकती है, जबकि गणितीय रूप से यह लगभग सबसे अच्छे समाधान के रूप में सिद्ध है।

तकनीकी सारांश: एडवर्सरियल कर्नल बैंडिट में नियर-ऑप्टिमल रिग्रेट (Near-Optimal Regret in Adversarial Kernel Bandit)

1. समस्या का स्वरूप (Problem Formulation)

यह शोध पत्र एडवर्सरियल कर्नल बैंडिट (adversarial kernel bandit) समस्या को संबोधित करता है, जो एडवर्सरियल लीनियर बैंडिट का एक सामान्यीकरण है जहाँ लॉस फंक्शन (loss functions) एक रिप्रोडसिंग कर्नेल हिलबर्ट स्पेस (RKHS) से संबंधित होते हैं।

सेटिंग (Setting): प्रत्येक राउंड $t \in [T]$ में, एक लर्नर एक परिमित एक्शन सेट $\mathcal{X} \subset \mathbb{R}^d$ से एक एक्शन $x_t$ चुनता है। साथ ही, एक ओब्लिवियस एडवर्सरी (oblivious adversary) RKHS में एक वेक्टर $w_t$ चुनती है।
लॉस (Loss): लर्नर एक लॉस $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$ का सामना करता है, जहाँ $\Phi: \mathcal{X} \to \mathcal{H}$ एक सिमेट्रिक पॉजिटिव डेफिनिट कर्नेल $K$ से जुड़ा फीचर मैप है।
फीडबैक (Feedback): लर्नर केवल स्केलर लॉस $\ell_t(x_t)$ को देखता है, न कि वेक्टर $w_t$ या पूर्ण लॉस फंक्शन को।
लक्ष्य (Goal): पिछले अनुभवों के आधार पर सर्वश्रेष्ठ निश्चित एक्शन $x^*$ के विरुद्ध अपेक्षित रिग्रेट (expected regret) $R_T$ को कम करना:
$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$
मान्यताएँ (Assumptions): एडवर्सरी बाउंडेड है ( $\|w_t\|_{\mathcal{H}} \le B$ ), और कर्नेल बाउंडेड है ( $K(x,x) \le 1$ )। महत्वपूर्ण रूप से, Chatterji et al. [2019] के पिछले कार्य के विपरीत, एडवर्सरी को रैंक-वन लॉस (rank-one losses) तक सीमित नहीं किया गया है (अर्थात, $w_t$ को $\Phi(z_t)$ के रूप में होने की आवश्यकता नहीं है); $w_t$ बाउंडेड नॉर्म वाले $\mathcal{H}$ का कोई भी तत्व हो सकता है।

2. कार्यप्रणाली और एल्गोरिदम (Methodology and Algorithm)

लेखक एक्सपोनेंशियल वेट्स (Exp2) पर आधारित एक एल्गोरिदम प्रस्तावित करते हैं जिसे अनंत-आयामी (infinite-dimensional) फीचर स्पेस के लिए अनुकूलित किया गया है। मुख्य चुनौती यह है कि महत्व-भारित अनुमानक (importance-weighted estimators), जो लीनियर बैंडिट में उपयोग किए जाते हैं, अनंत-आयामी RKHS में अनबाउंडेड हो सकते हैं क्योंकि कोवेरिएंस ऑपरेटर के आइगेनवैल्यू शून्य की ओर घटते हैं।

इस चुनौती से निपटने के लिए, लेखक दो प्रमुख संशोधन पेश करते हैं:

रेगुलराइज्ड इम्पॉर्टेंस-वेटेड एस्टीमेटर (Regularized Importance-Weighted Estimator):
एम्पिरिकल कोवेरिएंस ऑपरेटर $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$ को इनवर्ट करने के बजाय, एल्गोरिदम एक रिज-रेगुलराइज्ड संस्करण $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$ का उपयोग करता है। एस्टीमेटर को इस प्रकार परिभाषित किया गया है:
$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$
यह रेगुलराइजेशन सुनिश्चित करता है कि एस्टीमेटर बाउंडेड रहे, भले ही $\Sigma_t$ के आइगेनवैल्यू शून्य के करीब हों। हालाँकि, यह एक व्यवस्थित बायस (systematic bias) भी लाता है: $\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$ ।
स्पष्ट बायस करेक्शन टर्म (Explicit Bias Correction Term):
रेगुलराइजेशन बायस की भरपाई के लिए, एल्गोरिदम एक सुधारा गया लॉस प्रॉक्सी (corrected loss proxy) $\hat{\ell}_t(x)$ बनाता है:
$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$
जहाँ करेक्शन टर्म $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$ है।
- तंत्र (Mechanism): करेक्शन टर्म को सीधे क्लोज्ड-फॉर्म बायस एक्सप्रेशन से प्राप्त किया गया है। यह बायस के पॉइंटवाइज अपर बाउंड (pointwise upper bound) के रूप में कार्य करता है, जिससे यह सुनिश्चित होता है कि अपेक्षित लॉस प्रॉक्सी, कंपैरेटर (बेस्ट फिक्स्ड एक्शन) के लिए वास्तविक लॉस से कम हो। यह संरचनात्मक विकल्प यह सुनिश्चित करता है कि रिग्रेट डिकंपोजिशन में कंपैरेटर-साइड रेसिड्यूल (residual) नॉन-पॉजिटिव हो, जिससे केवल एक नियंत्रणीय लर्नर-साइड रेसिड्यूल ही बचता है।
एक्सप्लोरेशन स्ट्रैटेजी (Exploration Strategy):
एल्गोरिदम एक वितरण $p_t$ बनाए रखता है जो वर्तमान एक्सपोनेंशियल वेट्स वितरण $q_t$ और एक फिक्स्ड एक्सप्लोरेशन वितरण $\nu_G$ का मिश्रण है। प्रभावी आयाम (effective dimension) को नियंत्रित करने के लिए एक्सप्लोरेशन वितरण को रेगुलराइज्ड G-ऑप्टिमल डिज़ाइन के माध्यम से चुना जाता है।

3. मुख्य योगदान (Key Contributions)

एल्गोरिदम डिज़ाइन: एक्सपोनेंशियल वेट्स को एक रेगुलराइज्ड एस्टीमेटर और एक स्पष्ट बायस करेक्शन टर्म के साथ संयोजित करने वाला एक सिद्धांत आधारित एल्गोरिदम। यह दृष्टिकोण Chatterji et al. [2019] द्वारा आवश्यक प्रतिबंधात्मक रैंक-वन एडवर्सरी धारणा को हटा देता है।
इफेक्टिव डायमेंशन के माध्यम से रिग्रेट विश्लेषण: लेखक कर्नेल के इफेक्टिव डायमेंशन $d^*(\lambda)$ पर निर्भर रिग्रेट बाउंड प्राप्त करते हैं, जिसे इस प्रकार परिभाषित किया गया है:
$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$
रैंक-वन धारणा को हटाना: यह फ्रेमवर्क सामान्य बाउंडेड RKHS लॉसों की अनुमति देता है, जो प्रोजेक्शन-आधारित एस्टीमेटरों की आवश्यकता वाले पिछले कार्यों की तुलना में काफी व्यापक अनुप्रयोग प्रदान करता है।

4. मुख्य परिणाम (Main Results)

पेपर निम्नलिखित रूप में एक रिग्रेट बाउंड स्थापित करता है:
$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$
जहाँ $d^*(\lambda)$ , कर्नेल की जटिलता को दर्शाता है। यह दर स्टोकेस्टिक कर्नेल बैंडिट समस्या के लिए ज्ञात ऑप्टिमल दरों से मेल खाती है (लॉगफैक्टर के अपवाद के साथ)।

विशिष्ट कर्नेल दरें (Specific Kernel Rates):

Matérn $(\nu, d)$ कर्नेल: $\mathbb{R}^d$ पर Matérn कर्नेल के लिए, इफेक्टिव डायमेंशन निम्नलिखित रिग्रेट बाउंड देता है:
$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$
यह Chatterji et al. [2019] के $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$ के पिछले सर्वोत्तम ज्ञात दर में सुधार करता है और लॉगरिदमिक फैक्टर्स तक समवर्ती कार्य [Iwazaki, 2026] से प्राप्त लोअर बाउंड से मेल खाता है। विशेष रूप से, पिछला दर $\nu < d/2$ की स्थिति में सबलीनियर (sublinear) भी नहीं था, जबकि नया बाउंड हमेशा सबलीनियर है।
स्क्वेर्ड एक्सपोनेंशियल (SE) कर्रल: बाउंड $\tilde{O}(\sqrt{T})$ की नियर-ऑप्टिमल दर को रिकवर करता है, जो रैंक-वन प्रतिबंध के बिना Chatterji et al. [2019] से मेल खाता है।
सामान्य आइगेनवैल्यू डिके (General Eigenvalue Decay):
- पॉलीनोमियल डिके ( $\mu_j \le C j^{-\beta}$ ): $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$ प्राप्त करता है।
- एक्सपोनेंशियल डिके ( $\mu_j \le C e^{-\beta j}$ ): $\tilde{O}(\sqrt{T})$ प्राप्त करता है।

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

यह पेपर एडवर्सरियल और स्टोकेस्टिक कर्नेल बैंडिट प्रदर्शन के बीच के अंतर को पाटने का दावा करता है। विशेष रूप से:

इष्टतमता (Optimality): व्युत्पन्न दरें (लॉगफैक्टर के अपवाद के साथ) स्टोकेस्टिक कर्नेल बैंडिट्स (जैसे, SupKernelUCB या बायेसियन ऑप्टिमाइज़ेशन विधियों के माध्यम से) के लिए ज्ञात ऑप्टिमल दरों से मेल खाती हैं।
सैद्धांतिक प्रगति: रैंक-वन एडवर्सरी धारणा को हटाकर, परिणाम एडवर्सरियल वातावरणों के एक अधिक सामान्य और यथार्थवादी वर्ग पर लागू होते हैं जहाँ लॉस फंक्शन RKHS का एक मनमाना बाउंडेड तत्व होता है।
पिछले कार्य से तुलना: यह कार्य Matérn कर्नेल और सामान्य पॉलीनोमियल डिके के लिए Chatterji et al. [2019] में सुधार करता है, उन स्थितियों में टाइट बाउंड प्रदान करता है जहाँ पिछले बाउंड सबलीनियर नहीं थे।
समवर्ती कार्य: लेखक Iwazaki [2026] के स्वतंत्र समवर्ती कार्य को स्वीकार करते हैं जो रेगुलराइज्ड एस्टीमेटर्स और बायस करेक्शन के साथ एक्सपोनेंशियल वेट्स का उपयोग करके समान परिणाम प्राप्त करता है। पेपर नोट करता है कि समस्या सेटअप (जैसे, ओब्लिवियस बनाम अडैप्टिव एडवर्सरी, विशिष्ट जटिलता माप) में मामूली अंतर है, लेकिन यह दावा करता है कि मुख्य एल्गोरिद्मिक और विश्लेषणात्मक योगदान अनिवार्य रूप से समान हैं।

पेपर निष्कर्ष निकालता है कि प्रस्तावित विधि एडवर्सरियल कर्नेल बैंडिट समस्या के लिए एक नियर-ऑप्टिमल समाधान प्रदान करती है, जो रेगुलराइजेशन और स्पष्ट बायस करेक्शन के माध्यम से अनंत-आयामी फीचर स्पेस की चुनौतियों को प्रभावी ढंग से संभालती है।