📊 statistics

Self-Concordant Perturbations for Linear Bandits

यह शोधपत्र सेल्फ-कॉन्कॉर्डेंट (self-concordant) विक्षोभों का उपयोग करके एडवरसेरियल लीनियर बैंडिट्स के लिए FTRL और FTPL विधियों को जोड़ने वाला एक एकीकृत ढांचा प्रस्तुत करता है, जिसके परिणामस्वरूप एक नया एल्गोरिदम प्राप्त होता है जो हाइपरक्यूब और $\ell_2$ बॉल दोनों पर $\mathcal{O}(d\sqrt{n \ln n})$ का इष्टतम रिग्रेट बाउंड प्राप्त करता है।

मूल लेखक: Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini

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

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

CC BY 4.0

मूल लेखक: Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini

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

कल्पना कीजिए कि आप एक चतुर प्रतिद्वंद्वी के खिलाफ "सर्वश्रेष्ठ चाल का अनुमान लगाने" (Guess the Best Move) के एक हाई-स्टेक्स खेल में खेल रहे हैं। आपके पास संभावित चालों का एक विशाल डिब्बा (एक्शन सेट) है, लेकिन आप नहीं जानते कि कौन सी चाल सबसे अच्छी है। हर बार जब आप कोई चाल चुनते हैं, तो प्रतिद्वंद्वी आपको केवल यह बताता है कि वह विशिष्ट चाल कितनी खराब थी, लेकिन वे अन्य सभी चालों के स्कोर गुप्त रखते हैं। आपका लक्ष्य समय के साथ सर्वश्रेष्ठ चालें चुनना है ताकि आपका कुल स्कोर उस स्कोर के जितना संभव हो सके करीब हो सके जो आपको तब मिलता यदि आप शुरुआत से ही सर्वश्रेष्ठ चाल जानते होते। इस अंतर को रिग्रेट (regret) कहा जाता है।

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

यहाँ उनकी खोज का विवरण दिया गया, जिसे सरल रूप में समझाया गया है:

खेलने के दो पुराने तरीके

इस पेपर से पहले, इस खेल के लिए दो मुख्य रणनीतियाँ थीं:

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

समस्या

"अराजक" FTPL विधि अन्वेषण (explore) करने में बहुत अच्छी है, लेकिन जटिल आकृतियों (जैसे एक गेंद या घन) के लिए इसे गणितीय रूप से सटीक साबित करना कठिन था। "सतर्क" FTRL विधि गणितीय रूप से ठोस थी लेकिन कभी-कभी यह बहुत धीरे अन्वेषण करती थी, जिससे कुछ आकृतियों पर अधिक "रिग्रेट" (अधिक गलतियाँ) होता था।

नया समाधान: "सेल्फ-कॉन्कॉर्डेंट पर्टर्बेशन्स"

लेखकों ने इन दोनों दुनियाओं के बीच एक सेतु बनाया। उन्होंने "शोर" (perturbation) का एक नया प्रकार बनाया जो एक जादुई दिशा-सूचक (magic compass) की तरह काम करता है।

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

परिणाम: दो अलग-अलग कमरे

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

हाइपरक्यूब (एक विशाल, बहु-आयामी बॉक्स):
- पुराना तरीका: सतर्क विधि यहाँ धीमी थी, जिससे गलती का कारक $\sqrt{d}$ (जहाँ $d$ आयामों की संख्या है) था।
- नया तरीका: SC-FTPL बहुत तेज़ था। इसने गलतियों को $\sqrt{d}$ के कारक से कम कर दिया। इसने अनिवार्य रूप से इस आकार के लिए "सर्वश्रेष्ठ संभव" प्रदर्शन से मेल खाया। यह ऐसा है जैसे खिलाड़ी को अचानक एहसास होता है कि वह बॉक्स के माध्यम से बहुत अधिक कुशलता से दौड़ सकता है क्योंकि वह हर कोने को मैन्युअल रूप से चेक करने में समय बर्बाद नहीं कर रहा है।
$\ell_2$ बॉल (एक आदर्श गोला):
- पुराना तरीका: सतर्क विधि यहाँ काफी अच्छी थी।
- नया तरीका: SC-FTPL ने मौजूदा सर्वोत्तम विधि के समान प्रदर्शन किया। इसने रिकॉर्ड नहीं तोड़ा, लेकिन इसने साबित कर दिया कि "अराजक" दृष्टिकोण मौजूदा "सतर्क" विधि जितना ही गणितीय रूप से सटीक हो सकता है, बिना किसी जटिल अतिरिक्त चरणों के।

यह क्यों मायने रखता है

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

बॉक्स के लिए: उन्होंने इस पर पूर्ण दक्षता से खेलने का एक तरीका खोजा।
बॉल के लिए: उन्होंने साबित किया कि अराजक तरीका सबसे अच्छे सतर्क तरीके जितना ही अच्छा काम करता है।

संक्षेप में, उन्होंने एक एकीकृत ढांचा बनाया जो "अराजक" रणनीति को जटिल खेलों में "सतर्क" रणनीति जितना शक्तिशाली और गणितीय रूप से सुदृढ़ बनाता है।

तकनीकी सारांश: लीनियर बैंडिट्स के लिए सेल्फ-कॉन्कॉर्डेंट परटर्बेशन्स (Self-Concordant Perturbations)

समस्या का परिवेश (Problem Setting)
यह शोधपत्र एडवर्सरियल लीनियर बैंडिट्स (adversarial linear bandits) की समस्या को संबोधित करता है, जो एक ऑनलाइन ऑप्टिमाइज़ेशन सेटिंग है जहाँ एक एजेंट एक उत्तल पिंड (convex body) $K \subset \mathbb{R}^d$ से क्रमिक रूप से क्रियाएँ $a_t$ चुनता है। प्रत्येक दौर में, एजेंट को अज्ञात लॉस वेक्टर $y_t$ द्वारा निर्धारित हानि $\langle y_t, a_t \rangle$ उठानी पड़ती है, और उसे केवल स्केलर फीडबैक प्राप्त होता है। उद्देश्य रिग्रेट (regret) को कम करना है, जिसे एजेंट के संचयी लॉस और पिछले अनुभवों के आधार पर सर्वोत्तम निश्चित क्रिया (best fixed action) के संचयी लॉस के बीच के अंतर के रूप में परिभाषित किया गया है।

इस सेटिंग के लिए दो प्राथमिक एल्गोरिद्मिक परिवार मौजूद हैं: फॉलो-द-रेगुलराइज्ड-लीडर (FTRL) और फॉलो-द-परटर्बड-लीडर (FTPL)। जबकि एक एकीकृत ढांचा (GBPA) फुल-इन्फॉर्मेशन सेटिंग में इन दोनों को जोड़ता है, बैंडिट सेटिंग में इनका अंतर महत्वपूर्ण है: FTRL को स्पष्ट स्टोकेस्टिक एक्सप्लोरेशन तंत्रों की आवश्यकता होती है, जबकि FTPL स्वाभाविक रूप से स्टोकेस्टिक है, जो एक्शन सेट के चरम बिंदुओं (extreme points) से क्रियाएँ चुनता है। मौजूदा इष्टतम-दर वाले एल्गोरिदम अक्सर जटिल, डोमेन-विशिष्ट प्रीप्रोसेसिंग या एक्सप्लोरेशन स्कीमों (जैसे स्पैनिंग एलिप्सॉइड्स) पर निर्भर करते हैं, न कि SCRIBLE एल्गोरिदम में उपयोग किए गए सेल्फ-कॉन्कॉर्डेंट बैरियर फ्रेमवर्क से स्वाभाविक रूप से उत्पन्न होते हैं। SCRIBLE सामान्य उत्तल पिंडों पर $O(d^{3/2}\sqrt{n \ln n})$ और $\ell_2$ बॉल पर $O(d\sqrt{n \ln n})$ का रिग्रेट प्राप्त करता है, लेकिन हाइपरक्यूब पर सब-ऑप्टिमल एक्सप्लोरेशन वेरिएंस से ग्रस्त है।

कार्यप्रणाली: SC-FTPL ढांचा (Methodology: The SC-FTPL Framework)
लेखक BANDITS-GBPA पेश करते हैं, जो फुल-इन्फॉर्मेशन GBPA को बैंडिट सेटिंग में विस्तारित करने वाला एक एकीकृत ढांचा है। यह ढांचा एल्गोरिदम को एक पोटेंशियल फंक्शन $\Phi$ , एक सैंपलिंग स्कीम $S$ , और एक एस्टिमेशन स्कीम $E$ में विभाजित करता है।

इस ढांचे के भीतर, शोधपत्र सेल्फ-कॉन्कॉर्डेंट फॉलो-द-परटर्बड-लीडर (SC-FTPL) एल्गोरिदम प्रस्तावित करता है। मुख्य नवाचार सेल्फ-कॉन्कॉर्डेंट परटर्बेशन्स का परिचय है।

परिभाषा: एक प्रायिकता वितरण $D$ , $\mathbb{R}^d$ पर, $K$ के लिए एक $\vartheta$ -सेल्फ-कॉन्कॉर्डेंट परटर्बेशन है यदि $K$ पर एक $\vartheta$ -सेल्फ-कॉन्कॉर्डेंट बैरियर $R$ मौजूद है ताकि $R$ के फेंचल कंजुगेट (Fenchel conjugate) का ग्रेडिएंट, $K$ के सपोर्ट फंक्शन के ग्रेडिएंट का प्रत्याशा (expectation) है, जो परटर्बेशन के तहत है:
$\nabla R^*(\theta) = \mathbb{E}_{\xi \sim D}[\nabla \phi_K(\theta + \xi)]$
यह परिभाषा सुनिश्चित करती है कि परटर्बेशन वितरण $D$ , FTPL संदर्भ के भीतर $R$ के ज्यामितीय गुणों को "प्रतिलिपि" (replicate) करता है।
एल्गोरिदम: SC-FTPL संचयी अनुमानित लॉस $\hat{Y}_{t-1}$ को बनाए रखता है। प्रत्येक चरण में, यह एक परटर्बेशन $\xi_t \sim D$ को सैंपल करता है और क्रिया चुनता है:
$a_t = \arg \min_{a \in K} \langle a, \eta \hat{Y}_{t-1} - \xi_t \rangle$
लॉस वेक्टर का अनुमान मानक इनवर्स सेकंड-मोमेंट मैट्रिक्स एस्टिमेटर $\hat{y}_t = Q_t^{-1} a_t \langle y_t, a_t \rangle$ का उपयोग करके लगाया जाता है, जहाँ $Q_t = \mathbb{E}_{t-1}[a_t a_t^\top]$ है।

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

एकीकृत ढांचा (BANDITS-GBPA): लेखक एक ढांचा औपचारिक रूप प्रदान करते हैं जो लीनियर बैंडिट्स के लिए FTRL और FTPL दोनों दृष्टिकोणों को समाहित करता है, जो बैंडिट फीडबैक के लिए GBPA विश्लेषण का विस्तार करता है। फुल-इन्फॉर्मेशन सेटिंग के विपरीत, यहाँ FTPL कड़ाई से FTRL का उपसमुच्चय नहीं है, लेकिन ढांचा एक सामान्य विश्लेषणात्मक संरचना की अनुमति देता है।
सेल्फ-कॉन्कॉर्डेंट परटर्बेशन्स: शोधपत्र परटर्बेशन वितरणों के एक परिवार की पहचान और विश्लेषण करता है जो सेल्फ-कॉन्कॉर्डेंट बैरियर्स के गुणों को दोहराते हैं। यह SCRIBLE के रेगुलराइजेशन गुणों और FTPL की अंतर्निहित एक्सप्लोरेशन के बीच के अंतर को पाटता है।
स्पष्ट निर्माण (Explicit Constructions): लेखक दो कैनोनिकल एक्शन सेट्स के लिए विशिष्ट सेल्फ-कॉन्कॉर्डेंट परटर्बेशन्स का निर्माण करते हैं:
- हाइपरक्यूब $[-1, 1]^d$ : एंट्रोपिक बैरियर का उपयोग करके, वे स्वतंत्र मार्जिनल्स के साथ एक परटर्बेशन प्राप्त करते हैं।
- $\ell_2$ बॉल $B_d$ : लॉग-बैरियर का उपयोग करके, वे स्केल्ड मल्टीवेरिएटट $t$ -डिस्ट्रीब्यूशन पर आधारित एक परटर्बेशन का निर्माण करते हैं।

परिणाम और रिग्रेट बाउंड्स (Results and Regret Bounds)
शोधपत्र हाइपरक्यूब और $\ell_2$ बॉल पर SC-FTPL के लिए रिग्रेट गारंटी प्रदान करता है, यह मानते हुए कि लर्निंग रेट और हॉराइजन स्थितियाँ ( $n/\ln n$ आयाम के सापेक्ष पर्याप्त रूप से बड़ा है) उपयुक्त हैं।

हाइपरक्यूब: SC-FTPL $O(d\sqrt{n \ln n})$ का रिग्रेट बाउंड प्राप्त करता है।
- यह लॉगरिदमिक कारकों तक डेनी एट अल. (2007) द्वारा स्थापित मिनिमैक्स लोअर बाउंड से मेल खाता है।
- यह SCRIBLE एल्गोरिदम (जो $O(d^{3/2}\sqrt{n \ln n})$ प्राप्त करता है) पर $\sqrt{d}$ का सुधार है।
- यह सुधार FTPL सैंपलिंग स्कीम से आता है जो एक्सट्रीम पॉइंट्स पर केंद्रित होती है, जिससे SCRIBLE द्वारा उपयोग किए जाने वाले डिकिन एलिप्सॉइड (Dikin ellipsoid) सैंपलिंग की तुलना में लोकल नॉर्म में लॉस वेक्टर एस्टिमेटर का वेरिएंस कम हो जाता है।
- प्रति-राउंड कम्प्यूटेशनल जटिलता $O(d)$ है।
$\ell_2$ बॉल: SC-FTPL $O(d\sqrt{n \ln n})$ का रिग्रेट बाउंड प्राप्त करता है।
- यह $\ell_2$ बॉल पर SCRIBLE के प्रदर्शन से मेल खाता है।
- $\ell_2$ बॉल के लिए विश्लेषण अधिक जटिल है क्योंकि एस्टिमेटर का लोकल नॉर्म संचयी लॉस एस्टिमेट के स्वतंत्र रूप से यूनिफॉर्म अर्थ-नियर बाउंड को स्वीकार नहीं करता है। लेखक संचयी एस्टिमेटर के विकास को नियंत्रित करने और यूनिफॉर्म बाउंड की कमी को संभालने के लिए सुपरमार्टिंगेल और स्टॉपिंग टाइम तर्क (Ville's inequality का उपयोग करते हुए) वाले एक नवीन तर्क का उपयोग करते हैं।
- प्रति-राउंड कम्प्यूटेशनल जटिलता भी $O(d)$ है।

महत्व और दावे (Significance and Claims)
शोधपत्र दावा करता है कि SC-FTPL लीनियर बैंडिट्स के लिए एक एकीकृत, परटर्बेशन-आधारित दृष्टिकोण प्रदान करता है जो FTRL-आधारित विधियों के लिए आवश्यक स्पष्ट, अक्सर जटिल एक्सप्लोरेशन तंत्रों की आवश्यकता के बिना सेल्फ-कॉन्कॉर्डेंट रेगुलराइजेशन के लाभों को पुनः प्राप्त करता है।

हाइपरक्यूब पर इष्टतमता: प्राथमिक महत्व हाइपरक्यूब पर डोमेन-विशिष्ट सैंपलिंग स्कीमों के बिना इष्टतम दर प्राप्त करने में है, जो SCRIBLE एल्गोरिदम की तुलना में $\sqrt{d}$ के कारक से सुधार करता है।
सैद्धांतिक सेतु: यह कार्य प्रदर्शित करता है कि FTPL को सेल्फ-कॉन्कॉर्डेंट बैरियर्स के तंत्र का उपयोग करके कठोरता से विश्लेषित किया जा सकता है, बशर्ते कि परटर्बेशन्स बैरियर की ज्यामिति को दोहराने के लिए चुने गए हों।
सामान्यीकरण पर विनम्रता: लेखक नोट करते हैं कि जबकि वे हाइपरक्यूब और $\ell_2$ बॉल के लिए परटर्बेशन्स का निर्माण करते हैं, सामान्य उत्तल पिंडों के लिए सेल्फ-कॉन्कॉर्डेंट परटर्बेशन्स का अस्तित्व एक खुला प्रश्न बना हुआ है। वे यह भी स्वीकार करते हैं कि $\ell_2$ बॉल पर रिग्रेट बाउंड SCRIBLE से मेल खाता है लेकिन उससे बेहतर नहीं है, और इसके लिए अतिरिक्त तकनीकी मशीनरी (स्टॉपिंग टाइम्स) की आवश्यकता थी जो हाइपरक्यूब के मामले में आवश्यक नहीं थी।

शोधपत्र खुले दिशाओं की पहचान करते हुए समाप्त होता है, जिसमें यह निर्धारित करना शामिल है कि क्या $\ell_2$ बॉल पर FTPL के लिए किसी भी परटर्बेशन स्कीम के लिए $O(d\sqrt{n \ln n})$ दर टाइट है, और यह जांचना कि क्या एंट्रोपिक बैरियर (एक सार्वभौमिक सेल्फ-कॉन्कॉर्डेंट बैरियर) सामान्य उत्तल पिंडों के लिए एक संबंधित परटर्बेशन वितरण को स्वीकार करता है।