📊 statistics

Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

यह शोध पत्र यह प्रदर्शित करता है कि GP-UCB, समय-परिवर्ती गॉसियन प्रोसेस बैंडिट्स (time-varying Gaussian process bandits) में प्रति-राउंड स्थानीय विश्वास घटनाओं (per-round local confidence events) का उपयोग करके, मौजूदा विश्लेषणों के लिए आवश्यक क्षितिज-बढ़ते पैरामीटर (horizon-growing parameter) के बजाय एक स्थिर अन्वेषण पैरामीटर (constant exploration parameter) के साथ संचालित होकर, अधिक सटीक अपेक्षित और वास्तविक रिग्रेट बाउंड्स (expected and realized regret bounds) प्राप्त कर सकता है।

मूल लेखक: Matthias Mandl, Hanne Kekkonen

प्रकाशित 2026-08-20

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

CC BY 4.0

मूल लेखक: Matthias Mandl, Hanne Kekkonen

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

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

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

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

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

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

इन सैद्धांतिक निष्कर्षों को सत्यापित करने के लिए, टीम ने व्यापक कंप्यूटर सिमुलेशन चलाए। उन्होंने एक आभासी परिदृश्य बनाया जो दस हजार राउंड के निर्णय लेने के दौरान विकसित हुआ, और विभिन्न परिवर्तन की गति और जिज्ञासा के विभिन्न निश्चित स्तरों के साथ एल्गोरिदम का परीक्षण किया। परिणामों ने उनके सिद्धांत की पुष्टि की: एल्गोरिदम तब सबसे अच्छा प्रदर्शन करता था जब जिज्ञासा के स्तर को 'ड्रिफ्ट' (विचलन) की गति के अनुरूप ट्यून किया गया था, और यह निश्चित सेटिंग उन पुराने तरीकों से लगातार बेहतर रही जो समय के साथ अन्वेषण बढ़ाने का प्रयास करते थे। सिमुलेशन ने दिखाया कि एल्गोरिदम त्रुटि के एक स्थिर, निम्न स्तर को बनाए रख सकता है, जो यह सिद्ध करता है कि एक निरंतर दृष्टिकोण बदलते परिवेश में दीर्घकालिक कार्यों के लिए मजबूत और प्रभावी है।

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

तकनीकी सारांश: स्थिर अन्वेषण (Constant Exploration) के साथ समय-परिवर्तनीय गाऊसी प्रक्रिया बैंडिट्स के लिए तीक्ष्ण रिग्रेट बाउंड्स (Sharper Regret Bounds)

समस्या का परिवेश (Problem Setting)
यह शोधपत्र गैर-स्थिर वातावरणों (non-stationary environments) में बेयसियन ऑप्टिमाइज़ेशन को संबोधित करता है जहाँ अज्ञात रिवॉर्ड फंक्शन $f_t: S \to \mathbb{R}$ समय के साथ विकसित होता है। विशेष रूप से, लेखक बोगुनोविक एट अल. [2016] द्वारा प्रस्तुत टाइम-वेरिंग गाऊसी प्रोसेस (TV-GP) मॉडल पर विचार करते हैं। इस सेटिंग में, लेटेंट फंक्शन (latent function) एक मार्कोव रिकर्सन के अनुसार विकसित होता है जो GP इनोवेशन द्वारा संचालित होता है:
$f_{t+1}(x) = \sqrt{1-\epsilon} f_t(x) + \sqrt{\epsilon} g_{t+1}(x)$
जहाँ $g_t$ स्थानिक गाऊसी प्रक्रिया (spatial Gaussian process) से लिए गए i.i.d. ड्रॉ हैं जिसका कर्नेल $k_S$ है, और $\epsilon \in (0, 1]$ एक ड्रिफ्ट पैरामीटर है जो अस्थायी परिवर्तन की दर को नियंत्रित करता है। लक्ष्य संचयी रिग्रेट (cumulative regret) $R_T = \sum_{t=1}^T (f_t(x_t^*) - f_t(x_t))$ को कम करना है। स्थिर सेटिंग्स के विपरीत, यहाँ सबलीनियर संचयी रिग्रेट (sublinear cumulative regret) सामान्यतः अप्राप्य है; यहाँ उद्देश्य ड्रिफ्ट दर $\epsilon$ के फलन के रूप में औसत रिग्रेट $R_T/T$ को बाउंड करना है।

कार्यप्रणाली (Methodology)
लेखक इस गतिशील सेटिंग में गाऊसी प्रोसेस अपर कॉन्फिडेंस बाउंड (GP-UCB) एल्गोरिदम का पुनर्मूल्यांकन करते हैं। TV-GP बैंडिट्स के लिए मानक विश्लेषणों में आमतौर पर पूरे होराइजन (horizon) पर यूनिफॉर्म कॉन्फिडेंस बाउंड बनाए रखने के लिए समय $t$ के साथ बढ़ने वाले अन्वेषण पैरामीटर $\beta_t$ की आवश्यकता होती है। यह शोधपत्र एक अलग विश्लेषणात्मक दृष्टिकोण प्रस्तावित करता है:

स्थानीय कॉन्फिडेंस इवेंट्स (Local Confidence Events): पूरे होराइजन पर एक एकल वैश्विक कॉन्फिडेंस इवेंट (जो समय के साथ बढ़ते $\beta_t$ की मांग करता है) पर निर्भर रहने के बजाय, यह विश्लेषण प्रत्येक राउंड $t$ के लिए स्थानीय कॉन्फिडेंस इवेंट्स $E_t$ का निर्माण करता है।
स्थिर अन्वेषण पैरामीटर (Constant Exploration Parameter): इन स्थानीय इवेंट्स का उपयोग करके, लेखक यह प्रदर्शित करते हैं कि GP-UCB को एक स्थिर अन्वेषण पैरामीटर $\beta_t \equiv \beta$ के साथ चलाया जा सकता है।
विस्क्रीटीकरण और टेल बाउंड्स (Discretization and Tail Bounds): प्रमाण एक स्थानीय कॉन्फिडेंस इवेंट पर प्रति-राउंड UCB रिग्रेट बाउंड को एक दुर्लभ पूरक इवेंट (rare complement event) के एल्गोरिदम-अज्ञेय (algorithm-agnostic) बाउंड के साथ जोड़ता है। इसमें शामिल है:
- एक स्थानिक ग्रिड विस्क्रीटीकरण जिसका आकार $\tau^d$ है।
- विस्क्रीटीकरण त्रुटि को नियंत्रित करने के लिए डेरिवेटिव टेल बाउंड्स (Assumption 1)।
- फंक्शन स्पैन $W_t = \sup f_t - \inf f_t$ का सब-गाऊसी कॉन्सन्ट्रेशन (sub-Gaussian concentration)।
समय-घटता सूचना लाभ (Time-Decayed Information Gain): लेखक एक समय-परिवर्तनीय अधिकतम सूचना लाभ $\tilde{\gamma}_T$ के लिए एक तीक्ष्ण बाउंड प्राप्त करते हैं, जो पोस्टीरियर वेरिएंस के योग को नियंत्रित करता है। वे $\tilde{\gamma}_T$ को स्टेटिक सूचना लाभ $\gamma_N$ और ड्रिफ्ट पैरामीटर $\epsilon$ से जोड़ने के लिए एक ब्लॉक डिकंपोजिशन तकनीक का उपयोग करते हैं।

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

स्थिर अन्वेषण रिग्रेट बाउंड: प्राथमिक सैद्धांतिक परिणाम (Theorem 1) स्थिर- $\beta$ TV-GP-UCB के लिए अपेक्षित संचयी रिग्रेट बाउंड स्थापित करता है:
$E[R_T] \le \sqrt{C_1 T \beta \tilde{\gamma}_T} + T C_2 + T \delta C_3$
जहाँ $\tilde{\gamma}_T$ समय-परिवर्तनीय अधिकतम सूचना लाभ है। यह बाउंड किसी भी निश्चित ड्रिफ्ट दर $\epsilon > 0$ के लिए मान्य है और इसके लिए $\beta$ को $T$ के साथ स्केल करने की आवश्यकता नहीं है।
तीक्ष्ण सूचना लाभ स्केलिंग: लेखक एक नए बाउंड के माध्यम से समय-परिवर्तनीय सूचना लाभ प्राप्त करते हैं। यदि स्टेटिक सूचना लाभ $\gamma_N = \tilde{O}(N^q)$ है, तो पर्सिस्टेंट-ड्रिफ्ट रिजीम (जहाँ होराइजन $T$ प्रभावी ब्लॉक लंबाई से अधिक है) में, औसत सूचना लाभ इस प्रकार स्केल होता है:
$\frac{\tilde{\gamma}_T}{T} = \tilde{O}\left(\epsilon^{\frac{2(1-q)}{4-q}}\right)$
परिणामस्वरूप, अपेक्षित औसत रिग्रेट इस प्रकार स्केल होता है:
$\frac{E[R_T]}{T} = \tilde{O}\left(\epsilon^{\frac{1-q}{4-q}}\right)$
स्क्वेर्ड एक्सपोनेंशियल कर्नेल ( $q=0$ ) के लिए, यह $\tilde{O}(\epsilon^{1/4})$ का औसत रिग्रेट देता है।
बाउंड-सुझाया गया अन्वेषण पैरामीटर: विश्लेषण यह प्रकट करता है कि रिग्रेट बाउंड के टर्म्स को संतुलित करने से सुझाया गया इष्टतम स्थिर $\beta$ (जिसे $\beta_{opt}$ कहा जाता है) ड्रिफ्ट दर के व्युत्क्रम के लॉगरिदमिक पर निर्भर करता है:
$\beta_{opt} \propto \log(1/\epsilon)$
यह उन शेड्यूल्स के विपरीत है जहाँ $\beta_t$ , $\epsilon$ से स्वतंत्र होता है। लेखक तर्क देते हैं कि जैसे-जैसे ड्रिफ्ट धीमा होता है ( $\epsilon \to 0$ ), पिछले अवलोकन लंबे समय तक सूचनात्मक बने रहते हैं, जिससे पोस्टीरियर वेरिएंस कम हो जाता है; एक बड़ा $\beta$ शेष अनिश्चितता को कम करने पर उच्च मूल्य रखकर इसकी भरपाई करता है।
वास्तविक रिग्रेट गारंटी: शोधपत्र वास्तविक रिग्रेट के लिए पोस्ट-हॉक (post-hoc) और प्रिसक्राइबड-कॉन्फिडेंस (prescribed-confidence) गारंटी प्रदान करता है। प्रिसक्राइबड-कॉन्फिडेंस सेटिंग में, एल्गोरिदम एक स्थिर $\beta$ के साथ चल सकता है और विफलता की संभावना $\omega$ पर लॉगरिदमिक निर्भरता के साथ उच्च-संभावना रिग्रेट बाउंड प्राप्त कर सकता है।
सैंपलिंग फ्रीक्वेंसी अनुकूलन: फ्रेमवर्क $\beta$ को समायोजित करने के लिए एक ह्यूरिस्टिक प्रदान करता है जब सैंपलिंग फ्रीक्वेंसी बदलती है। यदि अवलोकन प्रत्येक $\Delta$ समय इकाइयों के बाद एकत्र किए जाते हैं, तो प्रभावी ड्रिफ्ट $\epsilon_\Delta = 1 - (1-\epsilon)^\Delta$ हो जाता है, और सुझाया गया $\beta$ , $\log(1/\epsilon_\Delta)$ के साथ स्केल करता है।

महत्ता और दावे (Significance and Claims)
शोधपत्र का दावा है कि इसका विश्लेषण समय-परिवर्तनीय GP बैंडिट साहित्य की एक आवर्ती सीमा को हल करता है: समय-बढ़ते अन्वेषण शेड्यूल्स की आवश्यकता, जो लंबे होराइजन पर प्रदर्शन को खराब करती है और कठिन ट्यूनिंग की मांग करती है। ग्लोबल से लोकल कॉन्फिडेंस इवेंट्स की ओर शिफ्ट होकर, लेखक दिखाते हैं कि एक स्थिर अन्वेषण पैरामीटर के साथ कठोर प्रदर्शन गारंटी बनाए रखी जा सकती है।

इसकी महत्ता निम्नलिखित है:

बेहतर लॉन्ग-होराइजन स्केलिंग: होराइजन के ऊपर यूनियन बाउंड के कारण अक्सर अग्रणी रिग्रेट टर्म में आने वाले $\sqrt{\log T}$ कारक को हटाना।
स्पष्ट ड्रिफ्ट निर्भरता: यह सैद्धांतिक आधार प्रदान करना कि अन्वेषण पैरामीटर को केवल समय $t$ के बजाय, पर्यावरणीय ड्रिफ्ट दर $\epsilon$ के साथ कैसे स्केल किया जाना चाहिए।
तीक्ष्ण बाउंड्स: पूर्ववर्ती कार्यों (जैसे, बोगुनोविक एट अल. [2016], इमामूरा एट अल. [2020]) की तुलना में समय-परिवर्तनीय सूचना लाभ के लिए अधिक सटीक दरें प्रदान करना।

प्रायोगिक सत्यापन (Empirical Validation)
लेखक अपने सैद्धांतिक निष्कर्षों का समर्थन करने के लिए स्क्वेर्ड एक्सपोनेंशियल कर्नेल का उपयोग करके 2D डोमेन पर एक सिमुलेशन अध्ययन करते हैं। वे समय-परिवर्तनीय पोस्टीरियर को कुशलतापूर्वक संभालने के लिए कलमन फ़िल्टर कार्यान्वयन का उपयोग करके $T=10,000$ राउंड का अनुकरण करते हैं। परिणाम पुष्टि करते हैं कि:

स्थिर $\beta$ के विस्तृत रेंज का प्रदर्शन समय-बढ़ते लॉगरिदमिक ह्यूरिस्टिक्स से बेहतर है।
अनुभवजन्य रूप से इष्टतम स्थिर $\hat{\beta}_{opt}$ , $-\log(\epsilon)$ के साथ रैखिक रूप से बढ़ता है, जो सैद्धांतिक भविष्यवाणी $\beta_{opt} \propto \log(1/\epsilon)$ को मान्य करता है।

सीमाएँ और भविष्य की दिशाएँ (Limitations and Future Directions)
लेखक नोट करते हैं कि उनका विश्लेषण मार्कोव ड्रिफ्ट मॉडल द्वारा प्रेरित विशिष्ट ज्यामितीय टेम्पोरल कर्नेल पर निर्भर करता है। सामान्य टेम्पोरल कर्नेल्स के लिए इन गारंटियों का विस्तार करना एक खुला प्रश्न बना हुआ है। इसके अतिरिक्त, वर्तमान विश्लेषण यह मानता है कि ड्रिफ्ट पैरामीटर $\epsilon$ ज्ञात है; $\epsilon$ अज्ञात होने पर $\beta$ को ऑनलाइन अनुकूलित करना भविष्य के कार्य के लिए एक सुझाया गया दिशा है। शोधपत्र यह भी स्वीकार करता है कि स्थिर-अन्वेषण परिणाम एक "पॉजिटिव-ड्रिफ्ट" परिणाम है, और यह $\epsilon=0$ पर मानक स्टेटिक सबलीनियर रिग्रेट गारंटी को रिकवर नहीं करता है, जिसके लिए अलग विश्लेषण की आवश्यकता है।

इसी तरह के और पेपर