📊 statistics

Learning from Local Walks on Dynamic Graphs with Bandit Feedback

यह शोधपत्र स्थानीय संचलन बाधाओं वाले गतिशील ग्राफों पर स्टोकेस्टिक मल्टी-आर्म्ड बैंडिट्स को संबोधित करने के लिए टोपोलॉजिकल स्थिरता सुनिश्चित करने हेतु एक स्लाइडिंग-विंडो मिक्सिंग स्थिति पेश करता है और एक्सप्लोर-देन-कमिट एल्गोरिदम का प्रस्ताव करता है जो उप-रैखिक अपेक्षित रिग्रेट (sublinear expected regret) प्राप्त करते हैं।

मूल लेखक: Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen

प्रकाशित 2026-07-14

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

CC BY 4.0

मूल लेखक: Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen

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

कल्पना कीजिए कि आप एक जादुई, बदलते हुए शहर में एक खजाना खोजने वाले (treasure hunter) हैं। यह शहर द्वीपों (विकल्पों या "arms") से बना है, और पुल इन द्वीपों को जोड़ते हैं। हर दिन, ये पुल खुद को पुनर्गठित करते हैं: कुछ खुल जाते हैं, कुछ बंद हो जाते हैं, और नए पुल दिखाई देने लगते हैं। आपका लक्ष्य सरल है: उस द्वीप को ढूंढना जहाँ सुनहरा संदूक (सबसे अच्छा इनाम) है और अपना बाकी समय वहीं सोना इकट्ठा करने में बिताना।

लेकिन इसमें एक पेच है: आप टेलीपोर्ट नहीं कर सकते। आप केवल उसी द्वीप पर जा सकते हैं जहाँ आप वर्तमान में खड़े हैं, या अपने पड़ोसी द्वीप की ओर जा सकते जो अभी खुला हुआ है। यह डायनेमिक ग्राफ बैंडिट्स (Dynamic Graph Bandits) की दुनिया है।

बड़ी समस्या: खोजना बनाम पहुँचना

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

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

समाधान: एक "स्लाइडिंग विंडो" नियम

इसे ठीक करने के लिए, लेखक शहर के लेआउट के लिए एक नया नियम प्रस्तावित करते हैं। पूरे दिन की जाँच करने के बजाय, वे एक स्लाइडिंग विंडो (जैसे, पिछले 5 मिनट) के समय की जाँच करते हैं।

वे कहते हैं कि शहर सीखने के लिए "सुरक्षित" है यदि, किसी भी 5-मिनट की विंडो के भीतर, पर्याप्त "अच्छी तरह से जुड़े हुए" क्षण हों जहाँ पुल एक अच्छे, खुले नेटवर्क का निर्माण करते हैं। यदि ऐसा अक्सर होता है, तो यह गारंटी देता है कि आपकी यादृच्छिक भटकने (random wandering) की प्रक्रिया अंततः आपको पूरे शहर में घुमा देगी, और आप किसी कोने में हमेशा के लिए नहीं फंसेंगे। वे इसे कॉमन-स्टेशनरी स्लाइडिंग-विंडो मिक्सिंग (Common-Stationary Sliding-Window Mixing) स्थिति कहते हैं।

इसे एक डांस फ्लोर की तरह समझें जो हर कुछ सेकंड में अपना आकार बदलता है। जब तक फर्श हर छोटे अंतराल में पर्याप्त बार खुलता रहता है, तब तक आप किसी कोने में नहीं फंस सकते, चाहे आपने नाचना कब भी शुरू किया हो।

रणनीति: अन्वेषण करें, फिर प्रतिबद्ध हों

शोध पत्र तीन तरीकों से खेलने का परीक्षण करता है:

"अंधा" यात्री (LEX): आप केवल यह देखने के लिए एक निश्चित समय के लिए यादृच्छिक रूप से घूमते हैं कि वहाँ क्या-क्या है। एक बार जब समय समाप्त हो जाता है, तो आप उस सबसे अच्छे द्वीप को चुनते हैं जिसे आपने देखा था और वहां पहुँचने की कोशिश करते हैं। गणित यह सिद्ध करता है कि यदि शहर "स्लाइडिंग विंडो" नियम का पालन करता है, तो आप सोना ढूंढ लेंगे और वहां पहुँच जाएंगे, और आपका कुल खोया हुआ सोना (regret) कुल समय की तुलना में बहुत कम होगा।
"आत्मविश्वासी" यात्री (CB-LEX): यह अधिक स्मार्ट है। एक निश्चित समय के लिए घूमने के बजाय, आप तब तक घूमते रहते हैं जब तक कि आप पूरी तरह आश्वस्त न हो जाएं कि आपने सबसे अच्छा द्वीप ढूंढ लिया है। आप तब रुक जाते हैं जब सबूत पर्याप्त मजबूत हो जाते हैं। शोध पत्र सिद्ध करता है कि यह "ब्लाइंड वॉकर" जितना ही प्रभावी है, लेकिन यह जल्दी रुककर समय बचाता है जब सोना आसानी से मिल जाता है।
"सर्चलाइट" यात्री (RALEX): यह थोड़ा चतुर होने की कोशिश करता है। यह अब तक मिले सोने को देखता है और यादृच्छिक रूप से घूमने के बजाय आशाजनक द्वीपों की ओर बढ़ने की कोशिश करता है।
- सुरक्षा जाल (Safety Net): लेखक सिद्ध करते हैं कि भले ही यह "सर्चलाइट" बहुत उत्साहित होकर जल्दबाजी करने की कोशिश करे, इसके कदमों में एक सुरक्षा आधार बना रहता है। यह सुनिश्चित करने के लिए कि यह हमेशा थोड़ा यादृच्छिक भटकना जारी रखे, यह अपने कदमों में थोड़ी सी रैंडम वेंडिंग रखता है। यह गारंटी देता है कि सबसे खराब स्थिति में भी, यह फँसेगा नहीं और अंततः सोना ढूंढ ही लेगा।
- प्रतिफल (Payoff): सिमुलेशन में, यह "सर्चलाइट" रणनीति एक बड़ी हिट रही। एक कठिन मानचित्र पर जहाँ सोना ढूंढना मुश्किल था, सर्चलाइट ने लगभग 1,850 राउंड में इसे ढूंढ लिया, जबकि ब्लाइंड वॉकर को 6,000 राउंड की आवश्यकता पड़ी। यह लगभग 70% तेज़ है।

यह पेपर किसे खारिज करता है

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

वे कितने आश्वस्त हैं?

लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने अपने विचारों के चारों ओर एक गणितीय किला बनाया है।

सिद्ध (Proven): उनके पास कठोर गणितीय प्रमाण हैं जो दिखाते हैं कि यदि शहर उनके "स्लाइडिंग विंडो" नियम का पालन करता है, तो "ब्लाइंड" और "कॉन्फिडेंट" यात्री हमेशा कम रिग्रेट (regret) के साथ सफल होंगे। उन्होंने यह भी सिद्ध किया कि "सर्चलाइट" यात्री सबसे खराब स्थिति में भी सुरक्षित है।
सिमुलेटेड (Simulated): उन्होंने "सर्चलाइट" रणनीति का परीक्षण करने के लिए 205 द्वीपों पर 70,000 राउंड के साथ कंप्यूटर सिमुलेशन चलाए। इन सिमुलेशनों ने दिखाया कि कठिन स्थितियों में सर्चलाइट वास्तव में अन्य लोगों की तुलना में बहुत तेज़ी से सोना ढूंढ लेता है।
कोई जादुई छड़ी नहीं (Not a Magic Bullet): वे स्वीकार करते हैं कि हालांकि सर्चलाइट उनके परीक्षणों में तेज़ है, लेकिन गणित केवल यह गारंटी देता है कि यह सुरक्षित है। अतिरिक्त गति इस बात पर निर्भर करती है कि सोना किसी विशिष्ट स्थान पर हो जिसे सर्चलाइट वास्तव में "देख" सकता है और उसकी ओर बढ़ सकता है।

संक्षेप में, यह शोध पत्र हमें बदलते भूलभुलैया (mazes) में नेविगेट करने के लिए एक नया नियम पुस्तिका देता है। यह सिद्ध करता है कि यदि भूलभुलैया छोटे अंतराल में पर्याप्त बार खुलती है, तो हम खजाना ढूंढ सकते हैं। और यदि हम अपनी भटकने में थोड़ा सा "स्मार्ट" दिशा जोड़ते हैं, तो हम बिना कभी बुरी तरह खोए, इसे और भी तेज़ी से ढूंढ सकते हैं।

तकनीकी सारांश: डायनेमिक ग्राफ पर लोकल वॉक से सीखना (बैंडिट फीडबैक के साथ)

समस्या का निरूपण (Problem Formulation)
यह शोध पत्र स्टोकेस्टिक मल्टी-आर्म्ड बैंडिट (MAB) समस्या को एक ऐसे परिवेश में संबोधित करता है जहाँ शिक्षार्थी (learner) एक डायनेमिक ग्राफ पर लोकल मूवमेंट (स्थानीय गति) के लिए बाध्य है। क्लासिकल MAB मॉडल्स के विपरीत, जहाँ प्रत्येक दौर में कोई भी आर्म उपलब्ध होती है, या फीडबैक-ग्राफ मॉडल्स के विपरीत, जहाँ साइड ऑब्जर्वेशन उपलब्ध होते हैं, यहाँ शिक्षार्थी केवल अपने वर्तमान नोड या उस विशिष्ट समय अंतराल पर ग्राफ की कनेक्टिविटी के आधार पर अपने तत्काल पड़ोसी को ही चुन सकता है।

सेटिंग: आर्म्स (arms) एक समय-परिवर्तनीय अनडिरेक्टेड ग्राफ $G_t = (A, E_t)$ के वर्टिस (vertices) $A = \{1, \dots, n\}$ के अनुरूप हैं।
बाधाएं (Constraints): दौर $t$ पर, शिक्षार्थी केवल स्थानीय पड़ोस $L_t(a_{t-1})$ को देखता है और $a_t \in L_t(a_{t-1})$ को चुनना होता है। ग्राफ प्रक्रिया 'ऑब्लिवियस' (learner के कार्यों से स्वतंत्र) है।
मुख्य चुनौती: यह सेटिंग सर्वश्रेष्ठ-आर्म पहचान (best-arm identification) को एक्सप्लॉइटेशन (exploitation) से अलग कर देती है। क्लासिकल बैंडिट्स में, $a^\star$ की पहचान करने के बाद तुरंत एक्सप्लॉइटेशन संभव है। इस डायनेमिक सेटिंग में, $a^\star$ की पहचान होने के बाद भी, शिक्षार्थी विकसित होती टोपोलॉजी के कारण संरचनात्मक रूप से उससे अलग (isolated) हो सकता है। सीखने की क्षमता (learnability) के लिए यह आवश्यक है कि वातावरण लगातार नेविगेबल पथ (navigable pathways) प्रदान करे, न कि केवल यह कि पूरे क्षितिज (horizon) के दौरान सभी ग्राफों का यूनियन कनेक्टेड हो।

कार्यप्रणाली और संरचनात्मक स्थितियाँ (Methodology and Structural Conditions)
लेखक एक एक्सप्लोर-देन-कमिट (explore-then-commit) ढांचे को अपनाते हैं, जो समस्या को अन्वेषण (exploration - डेटा एकत्र करना) और नेविगेशन (navigation - पहचाने गए लक्ष्य तक पहुँचना) में विभाजित करता है। सीखने की क्षमता सुनिश्चित करने के लिए, वे कैनोनिकल वॉक (एक साधारण रैंडम वॉक जहाँ शिक्षार्थी रुकता है या समान रूप से किसी पड़ोसी की ओर बढ़ता है) पर आधारित एक प्रोसेस-एग्नोस्टिक संरचनात्मक स्थिति पेश करते हैं।

कॉमन-स्टेशनरी स्लाइडिंग-विंडो मिक्सिंग (परिभाषा 1): यह शोध पत्र पूरे-क्षितिज कनेक्टिविटी स्थितियों (जैसे, सभी ग्राफों का यूनियन कनेक्टेड होना) को अपर्याप्त मानता है, क्योंकि वे मनमाने स्टॉपिंग टाइम पर पहुँच (reachability) की गारंटी देने में विफल रहती हैं। इसके बजाय, वे प्रेरित रैंडम वॉक पर एक शर्त लगाते हैं:
1. कॉमन स्टेशनरी डिस्ट्रीब्यूशन: प्रत्येक ग्राफ स्नैपशॉट $G_t$ एक कॉमन स्टेशनरी डिस्ट्रीब्यूशन $\pi$ के साथ एक रिवर्सिबल कर्नेल $U_t$ प्रेरित करता है (उदाहरण के लिए, फिक्स्ड-डिग्री सीक्वेंस द्वारा प्राप्त)।
2. स्लाइडिंग-विंडो मिक्सिंग: प्रत्येक विंडो $W$ की लंबाई में, कम से कम एक अंश $\rho$ दौरों में स्पेक्ट्रल गैप $\ge \gamma$ होना चाहिए।
  यह स्थिति सुनिश्चित करती है कि वॉक समय के साथ $\pi$ की ओर समान रूप से मिक्स होती है, जिससे शिक्षार्थी अनिश्चित काल के लिए स्थानीय सब-ग्राफ में फंसने से बच जाता है, चाहे अन्वेषण (exploration) कब भी समाप्त हो।

एल्गोरिदम (Algorithms)
यह शोध पत्र इस व्यवस्था के तहत कार्य करने वाले एल्गोरिदम के एक परिवार का विश्लेषण करता है:

LEX (फिक्स्ड-बजट लेजी एक्सप्लोरेशन): मिक्सिंग पैरामीटर्स और रिवॉर्ड गैप्स द्वारा निर्धारित एक निश्चित बजट $T_{exp}$ के लिए कैनोनिकल वॉक का उपयोग करता है। यदि लक्ष्य तुरंत सुलभ नहीं है, तो यह एम्पिरिकल लीडर पर कमिट करता है और नेविगेट करने के लिए कैनोनिकल वॉक का उपयोग करता है।
CB-LEX (कॉन्फिडेंस-बेस्ड स्टॉपिंग): फिक्स्ड बजट के स्थान पर एक डेटा-डिपेंडेंट स्टॉपिंग रूल का उपयोग करता है। यह तब समाप्त होता है जब एम्पिरिकल लीडर का लोअर कॉन्फिडेंस बाउंड (LCB), अन्य सभी आर्म्स (न कि केवल रनर-अप) के अपर कॉन्फिडेंस बाउंड्स (UCBs) पर हावी हो जाता है, जो असमान सैंपलिंग के विरुद्ध मजबूती सुनिश्चित करता है।
RALEX (रिवॉर्ड-अवेयर एक्सप्लोरेशन): एक रिवॉर्ड-बायस्ड कर्नेल पेश करता है जो कैनोनिकल वॉक को एक ऑप्टिमिस्टिक प्रपोजल (अनुमानित रिवॉर्ड्स पर सॉफ्टमैक्स) के साथ मिलाता है। महत्वपूर्ण रूप से, यह "कैनोनिकल फ्लोर" ( $\epsilon_0$ ) को बनाए रखता है ताकि कैनोनिकल वॉक के स्ट्रक्चरल मिक्सिंग गुणों को सुरक्षित रखा जा सके, जो वर्स्ट-केस सुरक्षा की गारंटी देता है।

प्रमुख परिणाम और रिग्रेट बाउंड्स (Key Results and Regret Bounds)
$(W, \rho, \gamma, \pi)$ -मिक्सिंग स्थिति के तहत, लेखक प्रस्तावित सभी एल्गोरिदम के लिए सबलीनियर एक्सपेक्टेड रिग्रेट ( $o(T)$ ) स्थापित करते हैं। रिग्रेट बाउंड्स दो अलग-अलग घटकों में विभाजित हैं:

लर्निंग रिग्रेट: यह सांख्यिकीय कठिनाई ( $\Delta^{-2}$ ) और मिक्सिंग ओवरहेड ( $\tau_0$ ) के साथ स्केल करता है, जो सर्वश्रेष्ठ आर्म की पहचान करने की लागत को दर्शाता है।
नेविगेशन रिग्रेट: यह क्षितिज $T$ से स्वतंत्र एक संरचनात्मक लागत है, जो स्टॉपिंग पॉइंट से पहचाने गए इष्टतम आर्म तक पहुँचने के अपेक्षित समय को दर्शाता है।

LEX/CB-LEX: $O(\tau_0 \cdot \Psi \cdot \log T)$ ऑर्डर का रिग्रेट प्राप्त करते हैं, जहाँ $\Psi$ गैप्स और स्टेशनरी मास की जटिलता को दर्शाता है।
RALEX: सिद्ध करता है कि रिवॉर्ड-अवेयर बायस (reward-aware bias) सबलीनियर रिग्रेट के साथ संगत है। हालाँकि वर्स्ट-केस बाउंड कंजर्वेटिव है (कैनोनिकल फ्लोर के कारण), शोध पत्र एक अलग प्रमेय (थ्योरम 4) प्रदान करता है जो दिखाता है कि यदि रिवॉर्ड-अवेयर बायस "नियर-बॉटलनेक" आर्म्स की विज़िटेशन प्रोबेबिलिटी को सफलतापूर्वक बढ़ाता है, तो एक प्रमाणित प्रदर्शन लाभ (लर्निंग टर्म में मल्टीप्लिकेटिव सुधार) प्राप्त होता है।

महत्व और दावे (Significance and Claims)
यह शोध पत्र स्वयं को विशिष्ट ग्राफ परिवारों (जैसे पूर्ण ग्राफ) पर निकट-इष्टतम रिग्रेट मिनिमाइजेशन के प्रस्ताव के बजाय, स्थानीय रूप से बाधित बैंडिट्स के लिए सीखने की क्षमता के संरचनात्मक लक्षण वर्णन (structural characterization) के रूप में प्रस्तुत करता है।

शिफ्ट-इनवेरिएंस (Shift-Invariance): प्राथमिक योगदान शिफ्ट-इनवेरिएंट, स्लाइडिंग-विंडिंग मिक्सिंग कंडीशन है। यह सुनिश्चित करता है कि नेविगेशन के लिए आवश्यक संरचनात्मक धारणाएं अन्वेषण के रैंडम स्टॉपिंग टाइम के बाद भी बनी रहती हैं, एक ऐसी आवश्यकता जिसे पूरे-क्षितिज वाले नियम पूरा करने में विफल रहते हैं।
डिकपलिंग (Decoupling): यह कार्य स्पष्ट रूप से सीखने की सांख्यिकीय लागत को नेविगेशन की संरचनात्मक लागत से अलग करता है, जो डायनेमिक वातावरण के लिए एक स्वच्छ सैद्धांतिक ढांचा प्रदान करता है।
प्रोसेस-एग्नोस्टिसिज्म (Process-Agnosticism): विशिष्ट ग्राफ प्रक्रियाओं (जैसे i.i.d. Erdős–Rény– या एज-मार्कोवियन) पर निर्भर पिछले कार्यों के विपरीत, यह शोध पत्र एक ऐसा प्रमेय प्रदान करता है जो वॉक-केंद्रित मिक्सिंग कंडीशन को संतुष्ट करने वाले किसी भी ग्राफ अनुक्रम के लिए मान्य है, जिसमें रोटेटिंग रेगुलर ओवरले और डिग्री-प्रिजर्विंग रीवायरिंग जैसी प्राकृतिक प्रक्रियाएं शामिल हैं।
सेफ्टी बनाम गेन (Safety vs. Gain): RALEX विश्लेषण एक "सेफ्टी थ्योरम" (किसी भी बायस पैरामीटर के साथ सबलीनियर रिग्रेट की गारंटी देना) और एक "गेन थ्योरम" (रिवॉर्ड-अवेयर प्रपोजल पर विशिष्ट स्थितियों के तहत प्रदर्शन सुधार को प्रमाणित करना) के बीच अंतर करता है।

लेखक निष्कर्ष निकालते हैं कि उनका कार्य एक "पॉजिटिव रिजीम" स्थापित करता है जहाँ स्वाभाविक कैनोनिकल वॉक सीखने के लिए पर्याप्त है, जो मेट्रोपोलिस-टाइप वॉक जैसे अधिक जटिल कर्नेल्स के लिए भविष्य के विस्तार हेतु एक आधार प्रदान करता है।

बड़ी समस्या: खोजना बनाम पहुँचना

समाधान: एक "स्लाइडिंग विंडो" नियम

रणनीति: अन्वेषण करें, फिर प्रतिबद्ध हों

यह पेपर किसे खारिज करता है

वे कितने आश्वस्त हैं?

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