📊 statistics

A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

यह शोध पत्र HCW-GLB-OMD प्रस्तुत करता है, जो प्रतिकूल भ्रष्टाचार (adversarial corruptions) के तहत हेटरोस्केडास्टिक सामान्यीकृत रैखिक बैंडिट्स (heteroskedastic generalized linear bandits) के लिए एक गणनात्मक रूप से कुशल एल्गोरिदम है, जो एक ऑनलाइन मिरर डिसेंट अनुमानक (online mirror descent estimator) को हेसियन-आधारित आत्मविश्वास भारों (Hessian-based confidence weights) के साथ जोड़कर निकट-इन्स्टेंस-वाइज मिनिमैक्स इष्टतम रिग्रेट (near-instance-wise minimax optimal regret) प्राप्त करता है।

मूल लेखक: Sanghwa Kim, Junghyun Lee, Se-Young Yun

प्रकाशित 2026-06-23

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

CC BY 4.0

मूल लेखक: Sanghwa Kim, Junghyun Lee, Se-Young Yun

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

कल्पना कीजिए कि आप एक जासूस हैं जो सवाल पूछकर एक रहस्य सुलझाने की कोशिश कर रहे हैं। इस शोध पत्र की दुनिया में, "जासूस" एक एल्गोरिदम है, "सवाल" उसके द्वारा किए गए चुनाव हैं (जैसे कोई उत्पाद सुझाना या किसी उपचार का परीक्षण करना), और "जवाब" वह पुरस्कार है जो उसे वापस मिलता है।

आमतौर पर, ये जवाब ईमानदार होते हैं। लेकिन वास्तविक दुनिया में, एक चालाक "विरोधी" (एक दुर्भावनापूर्ण एजेंट) उन्हें झूठ बोलकर धोखा देने की कोशिश कर सकता है। इसे एडवर्सरियल करप्शन (adversarial corruption) कहा जाता है।

इसके अलावा, जवाब हमेशा समान रूप से विश्वसनीय नहीं होते। कभी शोर कम होता है (एक स्पष्ट फुसफुसाहट), और कभी शोर बहुत अधिक होता है (एक तेज़, अराजक शोर)। इसे हेटरोस्केडास्टिसिटी (heteroskedasticity) (बदलने वाला विचरण) कहा जाता है।

यह शोध पत्र एक नया जासूस पेश करता है, जिसका नाम HCW-GLB-OMD है, जिसे रहस्य सुलझाने के लिए बनाया गया है, भले ही जवाब शोरपूर्ण (noisy) और झूठे दोनों हों। यह कैसे काम करता है, इसके सरल उदाहरण यहाँ दिए गए हैं:

1. समस्या: "शोरपूर्ण, झूठ बोलने वाला" साक्षात्कार

कल्पना कीजिए कि आप नौकरी के लिए उम्मीदवारों का साक्षात्कार ले रहे हैं।

नॉनलीनियर ट्विस्ट (Nonlinear Twist): उम्मीदवार केवल "हाँ" या "नहीं" नहीं कहते। वे जटिल उत्तर देते हैं (जैसे "शायद, लेकिन केवल तभी जब मौसम अच्छा हो")। यह जनरलाइज्ड लीनियर बैंडिट (Generalized Linear Bandit) वाला हिस्सा है।
बदलता हुआ शोर: कभी कमरे में शांति होती है (कम शोर), और कभी बाहर निर्माण कार्य चल रहा होता है (उच्च शोर)। एल्गोरिदम को यह जानना चाहिए कि ड्रिलिंग के शोर के बीच सुनी गई "हाँ" की तुलना में शांत कमरे में सुनी गई "हाँ" अधिक विश्वसनीय है।
झूठा: कमरे में एक साज़िशकर्ता मौजूद है। वे किसी उम्मीदवार के उत्तर को "नहीं" से बदलकर "हाँ" कर सकते हैं ताकि एक बुरे उम्मीदवार को अच्छा दिखाया जा सके। उनके पास झूठ बोलने का एक सीमित बजट है (उदाहरण के लिए, वे कुल मिलाकर केवल 10 बार झूठ बोल सकते हैं)।

2. समाधान: "स्मार्ट वेट" जासूस

लेखकों ने एक ऐसा एल्गोरिदम बनाया है जो एक बहुत ही स्मार्ट जासूस की तरह काम करता है जो दो मुख्य तरकीबों का उपयोग करता है:

तरकीब A: "ट्रस्ट स्कोर" (हेसियन-आधारित कॉन्फिडेंस वेट्स)
अधिकांश जासूस हर उत्तर के साथ एक जैसा व्यवहार करते हैं। हालाँकि, यह जासूस हर एक उत्तर के लिए एक "ट्रस्ट स्कोर" (विश्वास स्कोर) की गणना करता है।

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

तरकीब B: "वन-पास नोटबुक" (ऑनलाइन मिरर डिसेंट)
पुराने जासूस सभी उत्तर लिखते थे, घर जाते थे, पूरी नोटबुक पढ़ते थे, और फिर निर्णय लेते थे। यह धीमा है और इसके लिए एक बहुत बड़ी नोटबुक की आवश्यकता होती है। यह नया जासूस ऑनलाइन मिरर डिसेंट (Online Mirror Descent) का उपयोग करता है। वे हर एक सवाल के तुरंत बाद अपने सिद्धांत को अपडेट करते हैं।

लाभ: उन्हें नोटों की एक विशाल लाइब्रेरी की आवश्यकता नहीं है। उन्हें केवल एक बहुत ही छोटा, कुशल मानसिक स्थान (O(1) कॉम्प्लेक्सिटी) चाहिए। वे तेज़ हैं, हल्के हैं, और वास्तविक समय में जानकारी को प्रोसेस कर सकते हैं।

3. परिणाम: "दोनों दुनियाओं का सर्वश्रेष्ठ"

यह शोध पत्र सिद्ध करता है कि यह जासूस इष्टतम (optimal) है।

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

4. "लोअर बाउंड" प्रमाण

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

सारांश

संक्षेप में, यह शोध पत्र एक नया एल्गोरिदम प्रस्तुत करता है जो:

ध्यान से सुनता है: वह जानता है कि कब किसी उत्तर पर भरोसा करना है और वातावरण के शोर के आधार पर कब संशय करना है।
झूठ बोलने वालों से लड़ता है: वह संदिग्ध उत्तरों को बस इतना अनदेखा करता है कि एक साज़िशकर्ता जांच को बर्बाद न कर सके।
तेज़ी से चलता है: वह भारी मात्रा में डेटा संग्रहीत किए बिना अपनी जानकारी को तुरंत अपडेट करता है।
अजेय है: यह इस प्रकार की समस्या के लिए सैद्धांतिक रूप से सर्वोत्तम संभव प्रदर्शन प्राप्त करता है।

लेखकों ने विभिन्न परिदृश्यों पर इस तर्क का परीक्षण किया, जिसमें लॉजिस्टिक बैंडिट्स (जैसे हाँ/ना के निर्णय) और पॉइसन बैंडिट्स (जैसे घटनाओं की गिनती) शामिल हैं, यह दिखाते हुए कि उनका "स्मार्ट वेट" जासूस सभी क्षेत्रों में पूरी तरह से काम करता है।

तकनीकी सारांश: विषम विचरता (Heteroskedastic) सामान्यीकृत रैखिक बैंडिट्स के लिए एक संयुक्त रूप से कुशल और इष्टतम एल्गोरिदम

1. समस्या सेटिंग

यह शोध पत्र प्रतिकूल भ्रष्टाचार (adversarial corruptions) की उपस्थिति में विषम विचरता वाले सामान्यीकृत रैखिक बैंडिट्स (Heteroskedastic Generalized Linear Bandits - GLBs) की समस्या को संबोधित करता है। यह सेटिंग अनुक्रमिक निर्णय लेने के तीन चुनौतीपूर्ण पहलुओं को एकीकृत करती है:

सामान्यीकृत रैखिक मॉडल (GLMs): एक आर्म $x_t \in \mathbb{R}^d$ के लिए अपेक्षित पुरस्कार एक GLM का अनुसरण करता है, $E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$ , जहाँ $\mu$ एक ज्ञात इनवर्स लिंक फंक्शन है और $\theta^\star$ एक अज्ञात पैरामीटर है। यह ढांचा लॉजिस्टिक, पॉइसन (Poisson), और गौसियन रैखिक बैंडिट्स को समाहित करता है।
विषम विचरता (Heteroskedasticity): पुरस्कार का विचरण (variance) स्थिर नहीं है बल्कि आर्म्स और समय के चरणों में भिन्न होता है। विशेष रूप से, $\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$ , जहाँ $g(\tau_t)$ एक प्रकीर्णन (dispersion) पैरामीटर है जो बाह्य रूप से समय-परिवर्तनीय हो सकता है (जैसे गौसियन बैंडिट्स में) या आर्म के चयन द्वारा अंतर्जात रूप से निर्धारित किया जा सकता है (जैसे लॉजिस्टिक/पॉइसन बैंडिट्स में)।
प्रतिकूल भ्रष्टाचार (Adversarial Corruptions): एक अनुकूलनशील विरोधी (adaptive adversary) प्रत्येक चरण पर देखे गए पुरस्कार में एक भ्रष्टाचार $c_t$ जोड़कर हेरफेर करता है, जिससे शिक्षार्थी $\tilde{r}_t = r_t + c_t$ देखता है। विरोधी एक कुल बजट बाधा $\sum_{t=1}^T |c_t| \le C$ के तहत कार्य करता है।

लक्ष्य $T$ राउंड में इष्टतम आर्म और चुने गए आर्म के बीच अपेक्षित पुरस्कार के अंतर के रूप में परिभाषित संचयी छद्म-पछतावा (cumulative pseudo-regret) को कम करना है।

2. कार्यप्रणाली: HCW-GLB-OMD

लेखक HCW-GLB-OMD (हेसियन-कॉन्फिडेंस वेटेड GLB-OMD) प्रस्तावित करते हैं, जो एक एल्गोरिदम है जिसे कम्प्यूटेशनल रूप से कुशल और सांख्यिकीय रूप से इष्टतम होने के लिए डिज़ाइन किया गया है। यह एल्गोरिदम दो प्राथमिक घटकों को एकीकृत करता है:

A. ऑनलाइन मिरर डिसेंट (OMD) एस्टिमेटर

उन पिछले दृष्टिकोणों के विपरीत जो बैच मैक्सिमम लाइकलीहुड एस्टीमेशन (MLE) पर निर्भर करते हैं, जो स्थानीय भार (local weights) और वैश्विक अनुमानों के बीच एक समय-सूचकांक बेमेल (time-index mismatch) पैदा करते हैं, HCW-GLB-OMD एक ऑनलाइन OMD एस्टिमेटर का उपयोग करता है। चरण $t$ पर पैरामीटर अपडेट को इस प्रकार परिभाषित किया जाता है:
$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$
जहाँ $\tilde{\ell}_t$ एक वेटेड नेगेटिव लॉग-लाइक्लीहुड है। यह ऑनलाइन दृष्टिकोण सुनिश्चित करता है कि एस्टिमेटर, आर्म, और भार एक ही स्थानीय समय चरण पर संरेखित हों, जिससे भ्रष्टाचार के प्रभावों का कठोर विश्लेषण सुलभ हो सके।

B. हेसियन-आधारित कॉन्फिडेंस वेट्स

भ्रष्टाचार के विरुद्ध मजबूती प्राप्त करने के लिए, एल्गोरिदम लिंक फंक्शन के स्थानीय हेसियन (वक्रता) और प्रकीर्णन पैरामीटर के आधार पर प्रत्येक अवलोकन को एक कॉन्फिडेंस वेट $w_t$ आवंटित करता है:
$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$
यहाँ, $\|x_t\|_{H_t^{-1}}$ दिशा $x_t$ के अनुदिश अनिश्चितता को मापता है।

तंत्र (Mechanism): यदि एक आर्म की दिशा प्रकीर्णन के सापेक्ष अत्यधिक अनिश्चित (इनवर्स हेसियन में बड़ा नॉर्म) है, तो वजन $w_t$ को कम कर दिया जाता है ( $<1$ )। यह उन अवलोकनों को कम महत्व देता है जो प्रतिकूल हेरफेर के प्रति संवेदनशील हैं।
वक्रता जागरूकता (Curvature Awareness): डिज़ाइन मैट्रिक्स का उपयोग करने वाले रैखिक बैंडिट तरीकों के विपरीत, यह विधि हेसियन $\nabla^2 \tilde{\ell}_t$ का उपयोग करती है, जो स्थानीय ढलान $\dot{\mu}$ को शामिल करती है। यह एल्गोरिदम को GLM की विशिष्ट ज्यामिति (जैसे लॉजिस्टिक बैंडिट्स में संतृप्ति/saturation) के अनुकूल होने की अनुमति देता है।

C. भ्रष्टाचार-रोबस्ट कॉन्फिडेंस सीक्वेंस

लेखक एक कॉन्फिडेंस सेट $C_t(\delta)$ का निर्माण करते हैं जो अनुमान त्रुटि और प्रतिकूल भ्रष्टाचार दोनों को ध्यान में रखता है। इस सेट की त्रिज्या में $C$ के समानुपाती एक योगात्मक पद (additive term) शामिल है:
$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$
इस अनुक्रम का प्रमाण एक वेटेड लाइकलीहुड अनुपात पर लागू एक सुपरमार्टिंगेल तर्क (supermartingale argument) पर आधारित है, जो $w_t < 1$ के मामलों को संभालने के लिए $x \mapsto x^{w_t}$ मैपिंग की अवतलता (concavity) का उपयोग करता है।

3. प्रमुख योगदान और परिणाम

A. रिग्रेट अपर बाउंड (Regret Upper Bound)

यह शोध पत्र स्थापित करता है कि यदि लिंक फंक्शन $\mu$ सेल्फ-कॉन्कॉर्डेंट (Assumption 3) है, तो HCW-GLB-OMD के लिए एक रिग्रेट अपर बाउंड मिलता है। कम से कम $1-\delta$ प्रायिकता के साथ, रिग्रेट इस प्रकार सीमित है:
$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$
जहाँ:

$\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$ इष्टतम आर्म पर लिंक फंक्शन का ढलान है।
$g_{\max} = \max_t g(\tau_t)$ अधिकतम प्रकीर्णन है।
$\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$ वक्रता पैरामीटर है।
$C$ कुल भ्रष्टाचार बजट है।

बाउंड का महत्व:

इंस्टेंस-वाइज इष्टतमता (Instance-Wise Optimality): अग्रणी पद $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$ भ्रष्टाचार-मुक्त GLBs के लिए मिनिमैक्स लोअर बाउंड से मेल खाता है, जो किित (worst-case) वक्रता $\kappa$ के बजाय वास्तविक ढलान पर निर्भर करता है।
भ्रष्टाचार मजबूती (Corruption Robustness): भ्रष्टाचार पद $C$ के साथ रैखिक रूप से स्केल करता है (विशेष रूप से $d(g_{\max} + \kappa)C$ ), जो वक्रता कारक $\kappa$ के संबंध में मिनिमैक्स इष्टतम है।
एकीकरण (Unification): यह बाउंड विषम विचरता वाले रैखिक बैंडिट, लॉजिस्टिक बैंडिट और पॉइसन बैंडिट के अत्याधुनिक परिणामों को एक साथ रिकवर करता है।

B. एकीकृत रिग्रेट लोअर बाउंड (Unified Regret Lower Bound)

लेखक किसी भी सेल्फ-कॉन्कॉर्डेंट हेटेरोस्केडास्टिक GLB के लिए एक एकीकृत लोअर बाउंड सिद्ध करते हैं:
$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$
यह लोअर बाउंड:

लॉजिस्टिक बैंडिट, हेटेरोस्केडास्टिक लीनियर बैंडिट और करप्टेड लीनियर बैंडिट के मौजूदा समस्या-विशिष्ट लोअर बाउंड को समाहित करता है।
पुष्टि करता है कि एल्गोरिदम का अग्रणी पद 'इंस्टेंस-वाइज मिनिमैक्स ऑप्टिमल' है।
दर्शाता है कि भ्रष्टाचार पद $dC $अपरिहार्य है, हालांकि अपर बाउंड में वर्तमान में भ्रष्टाचार पद में एक अतिरिक्त$ \kappa $कारक ($ d\kappa C$) शामिल है।

C. कम्प्यूटेशनल दक्षता

एक महत्वपूर्ण योगदान एल्गोरिदम की दक्षता है। ऑनलाइन OMD अपडेट और रिकर्सिव हेसियन अपडेट का उपयोग करके, HCW-GLB-OMD प्रति इटरेशन $O(1)$ स्पेस और टाइम कॉम्प्लेक्सिटी प्राप्त करता है। यह पूर्ववर्ती भ्रष्टाचार-रोबस्ट GLM एल्गोरिदम (जैसे CR-Eluder-UCB, GAdaOFUL) के विपरीत है, जिन्हें बैच प्रोसेसिंग या जटिल कॉन्फिडेंस सेट निर्माण के कारण अक्सर $O(t)$ कॉम्प्लेक्सिटी की आवश्यकता होती है।

4. महत्व और दावे

शोध पत्र का दावा है कि यह प्रतिकूल भ्रष्टाचारों के तहत हेटेरोस्केडास्टिक GLBs के लिए पहला संयुक्त रूप से कुशल और इष्टतम एल्गोरिदम प्रदान करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

अंतराल को भरना (Bridging the Gap): यह करप्टेड GLBs में कम्प्यूटेशनल दक्षता और सांख्यिकीय इष्टतमता के बीच के ट्रेड-ऑफ को हल करता है। पिछले कार्यों ने या तो उच्च कम्प्यूटेशनल लागत के साथ इष्टतमता प्राप्त की या सब-ऑप्टिमल रिग्रेट बाउंड्स (जो अक्सर वर्स्ट-केस वक्रता $\kappa$ के साथ स्केल करते हैं) के साथ दक्षता प्राप्त की।
इंस्टेंस-वाइज इष्टतमता: एल्गोरिदम भ्रष्टाचार की उपस्थिति में भी, वर्स्ट-केस धारणाओं पर निर्भर करने के बजाय, इंस्टेंस की विशिष्ट कठिनाई ( $\dot{\mu}_{t,\star}$ के माध्यम से) के अनुकूल होने वाले रिग्रेट बाउंड प्राप्त करता है।
एकीकृत ढांचा: यह बिना किसी समस्या-विशिष्ट एल्गोरिथम संशोधन की आवश्यकता के, बैंडिट समस्याओं की एक विस्तृत श्रृंखला को कवर करने वाला एक एकल सैद्धांतिक ढांचा प्रदान करता है।

लेखक एक शेष अंतराल (gap) को नोट करते हैं: अपर बाउंड में भ्रष्टाचार पद $d\kappa C$ के साथ स्केल करता है, जबकि लोअर बाउंड $dC $है। वे अनुमान लगाते हैं कि$ \kappa$ कारक विश्लेषण का एक आर्टिफैक्ट (artifact) है और $O(dC) $बाउंड प्राप्त किया जा सकता है, लेकिन यह एक खुला प्रश्न बना हुआ है। इसके अतिरिक्त, वर्तमान विश्लेषण यह मानता है कि प्रकीर्णन पैरामीटर$ \tau_t $शिक्षार्थी को ज्ञात है; अज्ञात$ \tau_t$ को संभालना भविष्य की दिशा के रूप में पहचाना गया है।