📊 statistics

Optimal Regret for Single Index Bandits

यह शोधपत्र एक दो-चरणीय $\texttt{ZoomSIB-UCB}$ एल्गोरिदम का प्रस्ताव करके सामान्य सिंगल-इंडेक्स बैंडिट्स के लिए इष्टतम रिग्रेट (regret) की खुली समस्या को हल करता है जो $\tilde{\mathcal{O}}(T^{2/3})$ का एक टाइट (tight) $\tilde{\mathcal{O}}(T^{2/3})$ रिग्रेट बाउंड प्राप्त करता है, जो पिछले $\tilde{\mathcal{O}}(T^{3/4})$ परिणाम में महत्वपूर्ण सुधार करता है और एक नव-स्थापित मिनिमैक्स लोअर बाउंड (minimax lower bound) से मेल खाता है।

मूल लेखक: Devdan Dey, Sujoy Bhore, Avishek Ghosh

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

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

CC BY 4.0

मूल लेखक: Devdan Dey, Sujoy Bhore, Avishek Ghosh

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

कल्पना कीजिए कि आप एक विशाल, फैले हुए शहर में नींबू पानी का स्टॉल (lemonade stand) लगाने के लिए सबसे अच्छी जगह खोजने की कोशिश कर रहे हैं।

समस्या: "छिपा हुआ मानचित्र" (The "Hidden Map")
इस शहर में, आपको मिलने वाले ग्राहक (आपका रिवॉर्ड) एक एकल, छिपे हुए दिशा पर निर्भर करते हैं। मान लीजिए कि सबसे अच्छी जगहें एक विशिष्ट तिरछी सड़क (diagonal street) के साथ हैं, लेकिन आपको नहीं पता कि वह कौन सी तिरछी सड़क है। इसके अलावा, आपको वह "नियम" भी नहीं पता जो उस सड़क के स्थान को ग्राहकों की संख्या से जोड़ता है। हो सकता है कि सड़क का मध्य भाग सबसे अच्छा हो, या किनारे सबसे अच्छे हों, या यह एक अजीब टेढ़े-मेढ़े पैटर्न जैसा हो।

यह सिंगल इंडेक्स बैंडिट (Single Index Bandit) समस्या है। आपके पास उच्च-आयामी डेटा (पूरे शहर का नक्शा) है, लेकिन रिवॉर्ड उस नक्शे के एक छिपे हुए, एक-आयामी प्रोजेक्शन (one-dimensional projection) पर निर्भर करता है। चुनौती दोहरी है:

आप "सुनहरी सड़क" (golden street) की दिशा ( $\theta^*$ ) नहीं जानते।
आप उस वक्र (curve) के आकार को नहीं जानते जो यह बताता है कि एक बार सड़क मिल जाने के बाद कोई स्थान कितना अच्छा है (अज्ञात फलन $f$ )।

पुराना तरीका: अनुमान लगाना और जांचना
पिछले शोधकर्ताओं ने इसे हल करने की कोशिश की। यदि उन्हें पता होता कि वक्र हमेशा "ऊपर की ओर" (monotone) जाता है, तो उनके पास एक शानदार समाधान होता। लेकिन सामान्य, टेढ़े-मेढ़े, गैर-मोनोटोनिक वक्रों के लिए (जहाँ सबसे अच्छी जगह बीच में हो सकती है, या किनारों पर, या दोनों जगह), पिछला सबसे अच्छा तरीका एक अनाड़ी खोजकर्ता जैसा था। वे बहुत समय अंधाधुंध अनुमान लगाने, फिर एक अनुमान पर टिक जाने और फिर से दोहराने में बिता देते थे। इसके परिणामस्वरूप उनका "रिग्रेट" (संभावित ग्राहकों का नुकसान) समय के साथ काफी तेजी से बढ़ता था—विशेष रूप से $T^{3/4}$ के अनुपात में (जहाँ $T$ समय है)।

नया समाधान: "ZoomSIB-UCB"
लेखक एक स्मार्ट, दो-चरणीय रणनीति प्रस्तावित करते हैं जिसे ZoomSIB-UCB कहा जाता है। इसे एक दो-चरणीय अभियान के रूप में सोचें:

चरण 1: दिशा सूचक (Compass) खोजना (पैरामीटर अनुमान)
बिना किसी उद्देश्य के भटकने के बजाय, एल्गोरिदम पहले एक गणना किए गए थोड़े से समय के लिए यादृच्छिक (randomly) रूप से लीवर खींचने (अलग-अलग स्थानों को आज़माने) में समय बिताता है। यह एक चतुर गणितीय ट्रिक का उपयोग करता है जिसे स्टीन एस्टीमेटर (Stein Estimator) कहा जाता है।

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

चरण 2: ज़ूम किया हुआ मानचित्र (विभाजन और UCB)
एक बार जब एल्गोरिदम के पास दिशा का एक अच्छा अनुमान होता है, तो वह सभी जटिल शहर के मानचित्रों को उस एकल रेखा पर प्रोजेक्ट करता है। अब, 100-आयामी शहर के बजाय, यह केवल एक 1D सड़क है।

उपमा: कल्पना कीजिए कि आप उस सड़क की एक हाई-रिज़ॉल्यूशन फोटो लेते हैं और उसे एक साधारण रूलर (पैमाने) में सिकोड़ देते हैं जिसमें 100 चिह्नित ज़ोन (bins) हैं।
एल्गोरिदम इन ज़ोन के साथ एक क्लासिक स्लॉट मशीन गेम की तरह व्यवहार करता है। यह UCB (Upper Confidence Bound) नामक एक रणनीति का उपयोग करता है, जो नए ज़ोन को खोजने (explore) और अच्छे दिखने वाले ज़ोन का लाभ उठाने (exploit) के बीच संतुलन बनाता है।
ट्विस्ट: क्योंकि शहर बहुत बड़ा है, इसलिए हर ज़ोन में हर दिन नींबू पानी का स्टॉल उपलब्ध नहीं होगा। इसे "स्लीपिंग बैंडिट" (Sleeping Bandit) समस्या कहा जाता है (कुछ 'हाथ' या विकल्प "सोए हुए" या अनुपलब्ध हैं)। एल्गोरिदम स्मार्ट है क्योंकि यह केवल "जागृत" (awake) हाथों को खेलता है और उनकी निष्पक्ष तुलना करता है।

परिणाम: एक आदर्श संतुलन
रूलर पर कितने ज़ोन (bins) बनाने हैं, इसे सावधानीपूर्वक चुनकर, लेखकों ने "गोल्डिलॉक्स" (Goldilocks) का सही स्थान ढूंढ लिया।

यदि आपके पास बहुत कम ज़ोन हैं, तो आपका मानचित्र बहुत धुंधला है (आप सबसे अच्छी जगह चूक जाते हैं)।
यदि आपके पास बहुत अधिक ज़ोन हैं, तो आप खाली स्थानों की जाँच करने में बहुत समय बिताते हैं।
उन्होंने सिद्ध किया कि लगभग $T^{1/3}$ ज़ोन होना एकदम सही है।

इससे एक नया, इष्टतम "रिग्रेट" दर $T^{2/3}$ प्राप्त होता है।

अनुवाद: नया तरीका समय के साथ काफी कम संभावित ग्राहकों को खोता है (पुराने तरीके की तुलना में)। यह एक गणितीय प्रमाण है कि इस प्रकार की समस्या के लिए आप अधिक जानकारी जाने बिना इससे बेहतर कुछ नहीं कर सकते।

यह क्यों महत्वपूर्ण है (पेपर के अनुसार)
लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने सिद्ध किया कि यह इस प्रकार की समस्या के लिए सबसे अच्छी गति है।

अपर बाउंड (Upper Bound): उन्होंने दिखाया कि उनका एल्गोरिदम $T^{2/3}$ की गति प्राप्त करता है।
लोअर बाउंड (Lower Bound): उन्होंने एक "वर्स्ट-केस सिनेरियो" (एक कठिन, ऊबड़-खाबड़ रिवॉर्ड फंक्शन) बनाया और सिद्ध किया कि कोई भी एल्गोरिदम, चाहे वह कितना भी स्मार्ट क्यों न हो, $T^{2/3}$ की गति को मात नहीं दे सकता।
वास्तविक दुनिया के परीक्षण: उन्होंने सिंथेटिक डेटा और वास्तविक दुनिया के डेटासेट (जैसे नेटवर्क घुसपैठ का पता लगाना और वन आवरण प्रकार) पर इसका परीक्षण किया। हर मामले में, उनके तरीके ने पिछले सर्वोत्तम तरीकों की तुलना में बहुत तेज़ी से सबसे अच्छी जगह खोजी और कम "रिग्रेट" दिखाया। इसने उच्च-आयामी डेटा (कई फीचर्स) को भी बहुत बेहतर ढंग से संभाला, जो अनिवार्य रूप से सब कुछ उस एकल 1D रेखा में संकुचित करके "डाइमेंशनलिटी के अभिशाप" (curse of dimensionality) को अनदेखा कर देता है।

सारांश में
यह पेपर इस पहेली को हल करता है कि जब आपके पास एक जटिल, उच्च-आयामी दुनिया हो जो एक छिपे हुए, एक-आयामी नियम पर निर्भर करती है जिसे आप पूरी तरह से नहीं समझते, तो कुशलतापूर्वक कैसे सीखा जाए। उन्होंने एक उपकरण बनाया जो पहले छिपी हुई दिशा को खोजता है, फिर निर्णय लेने के लिए एक सरलीकृत मानचित्र पर ज़ूम करता है, और यह भी सिद्ध करता है कि इस विशिष्ट परिदृश्य में सीखने का यह सबसे तेज़ तरीका है।

तकनीकी सारांश: सिंगल इंडेक्स बैंडिट्स के लिए इष्टतम रिग्रेट (Optimal Regret)

समस्या की परिभाषा

यह शोध पत्र सिंगल-इंडेक्स बैंडिट (SIB) समस्या को संबोधित करता है, जो एक अनुक्रमिक निर्णय लेने वाला ढांचा (sequential decision-making framework) है जहाँ पुरस्कार (rewards) अज्ञात, उच्च-आयामी संदर्भ वेक्टर्स (context vectors) के एक अज्ञात, गैर-पैरामीट्रिक रिवॉर्ड फंक्शन के माध्यम से एक अज्ञात एक-आयामी प्रोजेक्शन पर निर्भर करते हैं।

औपचारिक रूप से, प्रत्येक दौर $t$ में, शिक्षार्थी (learner) $K$ संदर्भ वेक्टर्स का एक सेट $X_t = \{x_{t,a} \in \mathbb{R}^d\}_{a \in [K]}$ देखता है। शिक्षार्थी एक आर्म $x_{t,a}$ चुनता है और एक स्टोकेस्टिक रिवॉर्ड देखता है:
$y_t = f(x_{t,a}^\top \theta^*) + \eta_t$
जहाँ:

$\theta^* \in \mathbb{R}^d$ एक अज्ञात पैरामीटर वेक्टर (इंडेक्स दिशा) है।
$f: \mathbb{R} \to \mathbb{R}$ एक अज्ञात, निरंतरतः अवकलनीय (continuously differentiable) लिंक फंक्शन है।
$\eta_t$ एक शून्य-माध्य (zero-mean) शोर है जिसका बाउंडेड वेरिएंस है।

लक्ष्य क्षितिज $T$ के ऊपर इष्टतम आर्म और चुने गए आर्म के अपेक्षित रिवॉर्ड के बीच के अंतर, जिसे संचयी रिग्रेट (cumulative regret) कहा जाता है, को कम करना है।

संदर्भ और अंतराल (Gap):
जबकि लीनियर बैंडिट्स ( $\tilde{O}(\sqrt{T})$ ) और जनरलाइज्ड लीनियर बैंडिट्स (जहाँ $f$ ज्ञात है) के लिए इष्टतम रिग्रेट दरें स्थापित हैं, SIB सेटिंग अधिक चुनौतीपूर्ण है क्योंकि यहाँ $f$ अज्ञात है। कंग एट अल. [2025] के पिछले कार्य ने उस मामले को संबोधित किया जहाँ $f$ अज्ञात लेकिन मोनोटोन (monotone) था, जिससे स्टाइन अनुमानकों (Stein estimators) का उपयोग करके $\tilde{O}(\sqrt{T})$ रिग्रेट प्राप्त हुआ। हालाँकि, सामान्य गैर-मोनोटोन (non-monotone) मामले के लिए (केवल बाउंडेडनेस और लिप्सचिट्ज़ निरंतरता मानते हुए), अब तक का सबसे अच्छा ज्ञात बाउंड $\tilde{O}(T^{3/4})$ था। इस कार्य का केंद्रीय प्रश्न यह है: सामान्य (गैर-मोनोटोन) सिंगल-इंडेक्स बैंडिट्स के लिए इष्टतम रिग्रेट स्केलिंग क्या है?

कार्यप्रणाली: ZoomSIB-UCB

लेखक ज़ूम्ड सिंगल इंडेक्स बैंडिट विद अपर कॉन्फिडेंस बाउंड (ZoomSIB-UCB) नामक एक दो-चरणीय एल्गोरिदम प्रस्तावित करते हैं। मुख्य अंतर्दृष्टि यह है कि उच्च-आयामी समस्या को अज्ञात दिशा $\theta^*$ और फिर प्रक्षेपित स्थान (projected space) के विविक्तीकरण (discretization) के माध्यम से एक अनुक्रमिक एक-आयामी बैंडिट समस्याओं की श्रृंखला में कम करना।

चरण 1: पैरामीटर अनुमान (Parameter Estimation)

एल्गोरिदम अज्ञात दिशा $\theta^*$ का अनुमान लगाने के लिए पहले $T_0$ दौर समर्पित करता है।

एक्सप्लोरेशन (Exploration): आर्म्स को समान रूप से यादृच्छिक (uniformly at random) रूप से चुना जाता है।
अनुमान (Estimation): एल्गोरिदम एक नॉर्मलाइज्ड स्टाइन एस्टीमेटर (normalized Stein estimator) का उपयोग करता है। स्टाइन की पहचान (Stein's Identity) का लाभ उठाते हुए, जो कहता है कि $E[y S(x)] = E[f'(x^\top \theta^*)] \theta^* = \mu^* \theta^*$ (जहाँ $S(x)$ संदर्भ वितरण का स्कोर फंक्शन है), एल्गोरिदम $\theta^*$ की दिशा के लिए एक निष्पक्ष (unbiased) एस्टीमेटर बनाता है।
नॉर्मलाइजेशन (Normalization): स्केलिंग और साइन अस्पष्टता को हल करने के लिए, एस्टीमेटर को $\ell_1$ -नॉर्म का उपयोग करके नॉर्मलाइज किया जाता है।
कैलिब्रेशन (Calibration): $T_0$ को इस प्रकार चुना जाता है कि अनुमान त्रुटि $\|\hat{\theta}_0 - \theta^*\|_1$ पर्याप्त रूप से छोटी हो (विशेष रूप से $\Delta / 2L$ द्वारा सीमित, जहाँ $\Delta$ बिन की चौड़ाई है और $L$ संदर्भ का लिप्सचिट्ज़ स्थिरांक है)।

चरण 2: विविक्तीकृत UCB (Discretized UCB)

एक बार $\hat{\theta}_0$ की गणना हो जाने के बाद, एल्गोरिदम प्रक्षेपित स्केलर मानों $z = x^\top \hat{\theta}_0$ पर कार्य करता है।

विविक्तीकरण (Discretization): वास्तविक रेखा को $N = O(T^{1/3})$ बिन्स में विभाजित किया जाता है जिनकी चौड़ाई $\Delta = T^{-1/3}$ है।
स्लीपिंग बैंडिट्स (Sleeping Bandits): प्रत्येक दौर में, केवल बिनों का एक यादृच्छिक उपसमुच्चय "सक्रिय" होता है (जिसमें कम से कम एक उपलब्ध आर्म होता है)। यह एक "स्लीपिंग बैंडिट" संरचना पेश करता है जहाँ उपलब्ध आर्मों का सेट स्टोकेस्टिक रूप से बदलता रहता है।
UCB रणनीति: एल्गोरिदम उपलब्ध बिन्स पर एक UCB एल्गोरिदम चलाता है। यह उस बिन के आर्म को चुनता है जिसका उच्चतम अपर कॉन्फिडेंस बाउंड इंडेक्स होता है।
बायस हैंडलिंग (Handling Bias): एल्गोरिदम दो प्रकार की त्रुटियों को ध्यान में रखता है:
1. विविक्तीकरण बायस (Discretization Bias): निरंतर रिवॉर्ड को बिन सेंटर्स द्वारा अनुमानित करना (लिप्सचिट्ज़ निरंतरता द्वारा सीमित)।
2. अनुमान त्रुटि (Estimation Error): $\theta^*$ अनुमान त्रुटि के कारण इंडेक्स का विस्थापन।
  इन त्रुटियों को एक इन्फ्लेटेड कॉन्फिडेंस रेडियस में समाहित किया जाता है।

मुख्य योगदान

1. बेहतर रिग्रेट अपर बाउंड

यह शोध पत्र सामान्य गैर-मोनोटोन सिंगल-इंडेक्स बैंडिट्स के लिए $\tilde{O}(d^2 T^{2/3})$ का रिग्रेट बाउंड स्थापित करता है।

यह कंग एट अल. [2025] के पिछले सर्वोत्तम $\tilde{O}(T^{3/4})$ बाउंड की तुलना में काफी सुधार करता है।
एल्गोरिदम विविक्तीकरण बायस ( $O(T\Delta)$ ) और 1D बैंडिट समस्या की एक्सप्लोरेशन लागत ( $O(\sqrt{N T})$ ) के बीच संतुलन बनाकर इसे प्राप्त करता है। $N \sim T^{1/3}$ (और इस प्रकार $\Delta \sim T^{-1/3}$ ) सेट करने से कुल रिग्रेट $O(T^{2/3})$ तक न्यूनतम हो जाता है।

2. मैचिंग मिनिमैक्स लोअर बाउंड (Matching Minimax Lower Bound)

लेखक सामान्य गैर-मोनोटोन सेटिंग के लिए एक $\tilde{\Omega}(T^{2/3})$ मिनिमैक्स लोअर बाउंड सिद्ध करते हैं।

निर्माण (Construction): वे कार्यों के एक परिवार के साथ एक कठिन समस्या का निर्माण करते हैं जिनमें $\sim T^{-1/3}$ ऊंचाई के छोटे, स्थानीयकृत "बम्प्स" होते हैं।
रिडक्शन (Reduction): वे SIB समस्या को $N$ -आर्म बैंडिट समस्या में कम करते हैं (जहाँ $N \sim T^{1/3}$ ) यह सुनिश्चित करते हुए कि प्रत्येक बिन में आर्म उपलब्धता की उच्च संभावना हो।
सूचनात्मक ट्रैप (Information Theoretic Trap): ब्रेटग्नोल-हूबर असमानता (Bretagnolle-Huber inequality) का उपयोग करते हुए, वे दिखाते हैं कि एक 'नल हाइपोथेसिस' और एक 'स्पाइक हाइपोथेसिस' (जहाँ एक विशिष्ट बिन इष्टतम है) के बीच अंतर करने के लिए भारी एक्सप्लोरेशन की आवश्यकता होती है, जो $\Omega(T^{2/3})$ का रिग्रेट मजबूर करता है।
महत्व: यह पुष्टि करता है कि $\tilde{O}(T^{2/3})$ अपर बाउंड टाइट है और प्रस्तावित एल्गोरिदम मिनिमैक्स ऑप्टिमल है।

3. अनुभवजन्य सत्यापन (Empirical Validation)

सिंथेटिक और वास्तविक दुनिया के डेटासेट्स (KDD Cup 99, Forest Cover Type) पर व्यापक प्रयोग प्रदर्शित करते हैं:

बेहतर प्रदर्शन: ZoomSIB-UCB लगातार स्टेट-ऑफ-द-आर्ट GSTOR (कंग एट अल. [2025]) और रैंडम बेसलाइन्स से बेहतर प्रदर्शन करता है, जो काफी कम संचयी रिग्रेट प्राप्त करता है।
स्केलिंग: एल्गोरिदम एक उप-रैखिक (sublinear) रिग्रेट स्केलिंग प्रदर्शित करता है जिसका अनुभवजन्य घातांक (empirical exponent) क्वाड्रेटिक (Quadratic) के लिए $\approx 0.53$ और जिगज़ैग (Zigzag) के लिए $0.57 $है, जो$ 2/3$ के सैद्धांतिक वर्स्ट-केस सीलिंग से काफी नीचे है।
आयामीता (Dimensionality): एल्गोरिदम उच्च-आयामी संदर्भों ( $d$ ) के प्रति मजबूत है, क्योंकि यह प्रारंभिक अनुमान चरण के बाद प्रक्षेपित 1D स्पेस में कार्य करता है, जिससे कर्नेल-आधारित विधियों द्वारा उत्पन्न 'कर्स ऑफ डायमेंशनलिटी' से बचा जा सकता है।
अनुकूली स्टॉपिंग (Adaptive Stopping): एक अनुदायी स्टॉपिंग नियम एल्गोरिदम को एक्सप्लोरेशन चरण को जल्दी समाप्त करने की अनुमति देता है जब पैरामीटर अनुमान स्थिर हो जाता है, जिससे अज्ञात $\mu^*$ या $T$ के आधार पर $T_0$ को पूर्व-निर्धारित करने की आवश्यकता नहीं रहती।

महत्व और दावे

यह शोध पत्र एक स्पष्ट चरित्रण प्रदान करके अनुक्रमिक शिक्षण (sequential learning) की एक खुली समस्या को हल करने का दावा करता है।

इष्टतमता (Optimality): दोनों अपर और मैचिंग लोअर बाउंड प्रदान करके, लेखक स्थापित करते हैं कि सही रिग्रेट स्केलिंग $\Theta(T^{2/3})$ है (लॉगारिदमिक कारकों को छोड़कर)।
व्यापकता (Generality): उन पिछले दृष्टिकोणों के विपरीत जो मोनोटोनिटी या विशिष्ट स्मूथनेस क्लासेज (जैसे RKHS) पर निर्भर थे, यह विधि किसी भी बाउंडेड, लिप्सचिट्ज़ निरंतर रिवॉर्ड फंक्शन के लिए काम करती है जिसमें फंक्शन के आकार या $\mu^*$ के ज्ञान की आवश्यकता नहीं होती।
व्यावहारिकता (Practicality): एक अनुदायी स्टॉपिंग नियम का परिचय एल्गोरिदम को बिना किसी पूर्व ज्ञान के लागू करने योग्य बनाता है।

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