🤖 machine learning

Online Packet Scheduling with Deadlines and Learning

यह शोध पत्र आंशिक फीडबैक के तहत डेडलाइन के साथ ऑनलाइन पैकेट शेड्यूलिंग (Online Packet Scheduling with Deadlines) की समस्या को स्लीपिंग बैंडिट्स (sleeping bandits) के साथ संबंध स्थापित करके संबोधित करता है, $\widetilde{\mathcal{O}}(\sqrt{KT})$ के इष्टतम $\alpha$ -रिग्रेट बाउंड्स प्राप्त करने वाले एल्गोरिदम प्रस्तावित करता है, और यह प्रदर्शित करता है कि सीमित पैकेट प्रकारों के लिए, नियत (deterministic) रणनीतियाँ शास्त्रीय प्रतिस्पर्धी अनुपात (competitive ratio) $\frac{1+\sqrt{5}}{2}$ की बाधा को पार कर सकती हैं।

मूल लेखक: Gianmarco Genalti, Achraf Azize, Vianney Perchet

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

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

CC BY 4.0

मूल लेखक: Gianmarco Genalti, Achraf Azize, Vianney Perchet

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

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

यहाँ पेचीदा बात यह है: जब तक आप वास्तव में पत्र भेज नहीं देते, तब तक आपको यह नहीं पता चलेगा कि वह कितना "महत्वपूर्ण" या "मूल्यवान" है। हो सकता है कि वह पत्र सिर्फ एक बेकार विज्ञापन हो, या शायद वह एक जीतने वाला लॉटरी टिकट हो। आपको उसका मूल्य भेजने के बाद ही पता चलता है।

आपका लक्ष्य डेडलाइन समाप्त होने से पहले अधिक से अधिक उच्च-मूल्य वाले पत्रों को भेजना है। यही उस शोध पत्र का मुख्य विषय है, जिसे ऑनलाइन पैकेट शेड्यूलिंग विद डेडलाइन्स (Online Packet Scheduling with Deadlines) कहा जाता है।

ट्विस्ट: चलते-चलते सीखना

अतीत में, कंप्यूटर वैज्ञानिक मानते थे कि डाकघर प्रबंधक को केवल अनुमान लगाने या कठोर नियमों के आधार पर निर्णय लेना होता है। यह शोध पत्र एक नया विचार पेश करता है: सीखना (Learning)।

कल्पना कीजिए कि आपके पास विभिन्न प्रकार के लिफाफों का एक बॉक्स है (मान लीजिए कि $K$ प्रकार के लिफाफे हैं)। आप जानते हैं कि "टाइप A" के लिफाफों में आमतौर पर मूल्यवान पत्र होते हैं, जबकि "टाइप B" में आमतौर पर कचरा होता है। लेकिन आप अभी तक उनका सटीक औसत मूल्य नहीं जानते। आपको कुछ पत्रों को भेजकर और उनके परिणाम देखकर यह समझना होगा।

यह शोध पत्र पूछता है: क्या हम एक ऐसा प्रबंधक बना सकते हैं जो डेडलाइन का पालन करते हुए और प्रक्रिया के दौरान बहुत अधिक नुकसान उठाए बिना, यह सीख सके कि कौन से लिफाफे मूल्यवान हैं?

"स्लीपिंग" (सोने वाला) समस्या

लेखक इसकी तुलना एक खेल से करते हैं जिसे "स्लीपिंग बैंडिट" (Sleeping Bandit) कहा जाता है। कल्पना कीजिए कि आप $K$ अलग-अलग स्लॉट मशीनों वाले एक जुआरी हैं।

एक सामान्य खेल में, सभी मशीनें उपलब्ध होती हैं।
"स्लीपिंग" संस्करण में, कुछ मशीनें "सो रही" (अनुपलब्ध) होती हैं। आप केवल उन्हीं मशीनों के लीवर खींच सकते हैं जो जाग रही हैं।
आप यह नहीं जानते कि कौन सी मशीन सबसे अधिक भुगतान करती है, और आपको खेलते समय सीखना भी है।

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

परिणाम: "गोल्डन रेशियो" को मात देना

दशकों से, विशेषज्ञों का मानना था कि इस परिदृश्य में एक प्रबंधक कितनी अच्छी तरह प्रदर्शन कर सकता है, इसकी एक कठिन सीमा है। उन्होंने इस सीमा को गोल्डेन रेशियो (Golden Ratio) (लगभग 1.618) कहा था। इसका अर्थ था कि एक "परफेक्ट" प्रबंधक (जिसे भविष्य का पता हो) की तुलना में, सबसे अच्छा संभव प्रबंधक भी, सबसे खराब स्थिति में, केवल लगभग 62% मूल्य ही प्राप्त कर पाएगा।

यह शोध पत्र विशिष्ट स्थितियों में इस बाधा को तोड़ देता है:

डिटरमिनिस्टिक मैनेजर (एक सख्त योजनाकार):
यदि डाकघर केवल लिफाफों की एक निश्चित, सीमित संख्या (उदाहरण के लिए, केवल 2 या 3 प्रकार के लिफाफे) के साथ काम करता है, तो लेखकों ने एक नया एल्गोरिदम बनाया है जिसे ALGθ कहा जाता है।

उपमा: एक कठोर नियम का उपयोग करने के बजाय, यह प्रबंधक एक गतिशील "स्मार्ट स्केल" का उपयोग करता है। यह पत्र की तात्कालिकता (urgency) और उसके अनुमानित मूल्य को तौलता है।
परिणाम: जब पत्रों के प्रकार कम होते हैं, तो यह प्रबंधक गोल्डन रेशियो की सीमा को पार कर सकता है, और सर्वोत्तम मामलों में 1.41 (2 का वर्गमूल) के करीब पहुँच सकता है। यह ऐसा है जैसे किसी गुप्त शॉर्टकट को ढूंढ लिया गया हो जिसकी पुराने नियमों ने अनुमति नहीं दी थी।

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

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

वे इसे कैसे करते हैं: कॉन्फिडेंस इंटरवल्स (विश्वास अंतराल)

चूंकि प्रबंधक को लिफाफों का वास्तविक मूल्य नहीं पता होता, इसलिए वे कॉन्फिडेंस इंटरवल्स (Confidence Intervals) नामक उपकरण का उपयोग करते हैं।

रूपक: कल्पना कीजिए कि प्रबंधक प्रत्येक लिफाफे के प्रकार के लिए एक "सर्वश्रेष्ठ अनुमान" और एक "सबसे खराब अनुमान" रखता है।
- UCB (Upper Confidence Bound): "इस लिफाफे का मूल्य बहुत अधिक हो सकता है, इसलिए आइए आशावादी बनें और इसे आजमाएं।"
- LCB (Lower Confidence Bound): "यह लिफाफा शायद सुरक्षित है, लेकिन हमें सतर्क रहना चाहिए।"
एल्गोरिदम लगातार इन अनुमानों को अपडेट करते हैं। यदि किसी लिफाफे के प्रकार से लगातार उच्च मूल्य मिलता रहता है, तो प्रबंधक का "सर्वश्रेष्ठ अनुमान" बढ़ जाता है, और वह उसे प्राथमिकता देता है। यदि वह आमतौर पर कचरा है, तो प्रबंधक अपना समय बर्बाद करना बंद कर देता है।

निष्कर्ष

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

सरल प्रणालियों के लिए (कम पैकेट प्रकार): हम गोल्डन रेशियो की लंबे समय से चली आ रही बाधा को तोड़ सकते हैं और पूर्ण प्रदर्शन के बहुत करीब पहुँच सकते हैं।
जटिल प्रणालियों के लिए: हम अभी भी गणित के लिए ज्ञात सर्वोत्तम संभव प्रदर्शन सीमाओं को प्राप्त कर सकते हैं, जिससे यह सुनिश्चित होता है कि अनिश्चितता के बावजूद, सिस्टम अत्यधिक कुशल बना रहे।

संक्षेप में, यह शोध पत्र हमें सिखाता है कि जब आपको पत्र भेजने के बाद ही उसका मूल्य पता चलता है, तो एक बेहतर डाकघर प्रबंधक कैसे बना जाए, और यह सिद्ध करता है कि काम करते-करते सीखना लगभग पूर्ण परिणामों की ओर ले जा सकता है।

तकनीकी सारांश: डेडलाइन्स और लर्निंग के साथ ऑनलाइन पैकेट शेड्यूलिंग

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

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

लेखक एक नया वेरिएंट पेश करते हैं जिसे स्टोकेस्टिक ऑनलाइन K-पैकेट शेड्यूलिंग विद डेडलाइन्स (K-OPSD) कहा जाता है। इस सेटिंग में:

पैकेट $K$ अलग-अलग प्रकारों (types) से संबंधित होते हैं जिन्हें शेड्यूलर द्वारा जाना जाता है।
एक पैकेट का वास्तविक वेट (weight) तब तक अज्ञात रहता है जब तक उसे प्रोसेस नहीं किया जाता; इसके बजाय, वेट्स को पैकेट के प्रकार के विशिष्ट प्रायिकता वितरण (probability distribution) से सैंपल किया जाता है।
शेड्यूलर आंशिक फीडबैक (बैंडिट सेटिंग) के तहत कार्य करता है, जहाँ निष्पादन (execution) के बाद ही वेट्स देखे जाते हैं।
लक्ष्य अपेक्षित संचयी लाभ (expected cumulative gain) को अधिकतम करना और $\alpha$ -रेग्रेट ( $\alpha$ -regret) को न्यूनतम करना है, जिसे $R_{\alpha, T} = \mathbb{E}[G_{OPT}] - \alpha \mathbb{E}[G_{ALG}]$ के रूप में परिभाषित किया गया है, जहाँ $G_{OPT}$ सभी प्रकारों के औसत वेट्स को जानने वाले एक इष्टतम शेड्यूलर का अपेक्षित लाभ है।

यह शोध पत्र डिटरमिनिस्टिक (जहाँ इतिहास के आधार पर निर्णय अनुमानित होते हैं) एल्गोरिदम और रैंडमाइज्ड (यादृच्छिक) एल्गोरिदम के बीच अंतर करता है। यह "स्लैकनेस" (slackness) के संबंध में विशिष्ट बाधाओं पर ध्यान केंद्रित करता है, विशेष रूप से $s$ -बाउंडेड उदाहरण जहाँ एक पैकेट की डेडलाइन उसके आगमन के अधिकतम $s-1$ चक्रों के भीतर होती है।

कार्यप्रणाली (Methodology)

लेखक K-OPSD और स्लीपिंग बैंडिट्स (Sleeping Bandits) समस्या के बीच एक संबंध स्थापित करते हैं, जहाँ उपलब्ध क्रियाओं (पैकेट प्रकारों) का सेट प्रत्येक दौर में प्रतिकूल रूप से बदलता है। वे मल्टी-आर्म्ड बैंडिट्स (MAB) की तकनीकों, विशेष रूप से अपर कॉन्फिडेंस बाउंड्स (UCB) और लोअर कॉन्फिडेंस बाउंड्स (LCB) का उपयोग करते हैं, ताकि पैकेट वेट्स की अनिश्चितता को संभाला जा सके।

मुख्य कार्यप्रणाली में शामिल हैं:

कॉन्फिडेंस बाउंड्स: देखे गए सैंपल्स के आधार पर पैकेट प्रकारों के औसत वेट्स के लिए UCB और LCB का निर्माण करना। कॉन्फिडेंस विड्थ $\beta_{i,t}$ , $\sqrt{\frac{\log(KT)}{N_i(t)}}$ के अनुपात में स्केल होती है।
चार्जिंग स्कीम्स (Charging Schemes): $\alpha$ -रेग्रेट का विश्लेषण करने के लिए, लेखक एल्गोरिदम की क्रियाओं को इष्टतम शेdule (OPT) के साथ मैप करने के लिए चार्जिंग स्कीम्स का उपयोग करते हैं। यह गैर-तुच्छ (non-trivial) है क्योंकि K-OPSD में एक एकल निर्णय भविष्य के राउंड्स के लिए बफर की स्थिति को बदल देता है, जबकि मानक MABs के विपरीत जहाँ क्रियाएं स्वतंत्र होती हैं।
एपॉक-आधारित विश्लेषण (Epoch-Based Analysis): डिटरमिनिस्टिक एल्गोरिदम के लिए, शेड्यूल को विशिष्ट समाप्ति स्थितियों (जैसे, जब एक विशिष्ट डेडलाइन वाला पैकेट प्रोसेस किया जाता है) के आधार पर "एपॉक्स" (epochs) में विभाजित किया जाता है। यह प्रत्येक एपॉक के भीतर कॉम्पिटिटिव रेश्यो को बाउंड करने की अनुमति देता है।
पोटेंशियल फंक्शन्स (Potential Functions): रैंडमाइज्ड एल्गोरिदम के लिए, विश्लेषण पर्यावरण और एल्गोरिदम के निर्णयों की स्टोकेस्टिक प्रकृति को ध्यान में रखते हुए, OPT पर एल्गोरिदम के लाभ को मापने के लिए पोटेंशियल फंक्शन्स का उपयोग करता है।

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

1. डिटरमिनिस्टिक एल्गोरिदम

2/3-बाउंडेड सेटिंग्स में $\Phi$ -रेग्रेट: लेखक UCBs का उपयोग करके $\beta$ -रेशियो अर्लिएस्ट डेडलाइन फर्स्ट एल्गोरिदम का एक अनुकूलन, EDF $^\Phi_L$ प्रस्तावित करते हैं। वे सिद्ध करते हैं कि यह एल्गोरिदम $\tilde{O}(\sqrt{KT})$ द्वारा बाउंड $\Phi$ -रेग्रेट (जहाँ $\Phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ ) प्राप्त करता है। यह स्लीपिंग बैंडिट्स के लिए AUER एल्गोरिदम के रेग्रेट बाउंड से मेल खाता है।
$\Phi$ बैरियर को तोड़ना: 2-बाउंडेड सेटिंग में, जहाँ प्रकारों की संख्या $K$ $K$ सीमित है, यह शोध पत्र ALG $_\theta$ पेश करता है। यह एल्गोरिदम एक डायनेमिक थ्रेशोल्ड $\theta_K$ $θ_{K}$ निर्धारित करने के लिए समीकरणों के एक सिस्टम को हल करता है।
- परिणाम: ALG $_\theta$ एक $\theta_K$ कॉम्पिटिटिव रेशो प्राप्त करता है, जहाँ $\theta_K \in [\sqrt{2}, \Phi)$ है। जैसे-जैसे $K \to \infty$ , $\theta_K \to \Phi$ होता है। यह सीमित $K$ के लिए बाउंडेड-डिली शेड्यूलिंग में डिटरमिनिस्टिक एल्गोरिदम के लिए स्थापित $\Phi$ लोअर बाउंड को बेहतर बनाने वाला पहला परिणाम है।
$\theta_K$ -रेग्रेट के साथ लर्निंग: एल्गोरिदम को ALG $_{\theta, U}$ के रूप में विस्तारित किया गया है, जो वास्तविक वेट्स के बजाय UCBs का उपयोग करता है। यह $\tilde{O}(\sqrt{KT})$ का $\theta_K$ -रेग्रेट अपर बाउंड प्राप्त करता है।
लोअर बाउंड्स: 2-बाउंडेड $(K+1)$ -OPSD इंस्टेंस के लिए $\theta_K$ -रेग्रेट के लिए एक लोअर बाउंड $\Omega(\sqrt{T})$ सिद्ध किया गया है, जो यह दर्शाता है कि ALG $_{\theta, U}$ लगभग इष्टतम है।

2. रैंडमाइज्ड एल्गोरिदम

2-बाउंडेड सेटिंग्स में 5/4-रेग्रेट: शोध पत्र ALG $^R_2$ प्रस्तावित करता है, जो एक रैंडमाइज्ड एल्गोरिदम है जो $\tilde{O}(\sqrt{KT})$ का 5/4-रेग्रेट अपर बाउंड प्राप्त करता है। यह बिना लर्निंग के 2-बाउंडेड OPSD सेटिंग में ज्ञात सर्वश्रेष्ठ कॉम्पिटिटिव रेश्यो से मेल खाता है।
अनबाउंडेड सेटिंग्स में $e/(e-1)$ -रेग्रेट: सामान्य $s$ -बाउंडेड इंस्टेंस के लिए, ALG $^R_s$ प्रस्तावित है। यह $\tilde{O}(\sqrt{KT})$ का $\frac{e}{e-1}$ -रेग्रेट अपर बाउंड प्राप्त करता है, जो सामान्य OPSD सेटिंग में रैंडमाइज्ड एल्गोरिदम के लिए सर्वश्रेष्ठ मौजूदा कॉम्पिटिटिव रेश्यो से मेल खाता है।
तकनीकी अंतर: लेखक नोट करते हैं कि जबकि डिटरमिनिस्टिक लर्निंग एल्गोरिदम केवल UCBs (ऑप्टिमिज्म) पर निर्भर करते हैं, रैंडमाइज्ड एल्गोरिदम को अनुमानों के अनुपातों को स्वाभाविक रूप से संभालने के लिए UCBs और LCBs दोनों की आवश्यकता होती है।

महत्व और दावे

यह शोध पत्र दावा करता है कि यह बैंडिट लर्निंग और ऑनलाइन पैकेट शेड्यूलिंग विद डेडलाइन्स के बीच परस्पर क्रिया का अन्वेषण करने वाला पहला कार्य है। इसका प्राथमिक महत्व है:

सामान्यीकरण (Generalization): यह $K$ -आर्म्ड स्लीपिंग बैंडिट समस्या को K-OPSD सेटिंग में कड़ाई से सामान्यीकृत करता है, जो QoS बफर प्रबंधन में लर्निंग के लिए एक सैद्धांतिक ढांचा प्रदान करता है।
बैरियर को तोड़ना: यह प्रदर्शित करता है कि पैकेट प्रकारों की संख्या ( $K$ ) की धारणा डिटरमिनिस्टिक एल्गोरिदम को लंबे समय से स्थापित $\Phi$ कॉम्पिटिटिव रेश्यो बैरियर को तोड़ने की अनुमति देती है, जिससे एक बेहतर $\theta_K$ रेश्यो प्राप्त होता है।
टाइट रेग्रेट बाउंड्स: प्रस्तावित एल्गोरिदम $\tilde{O}(\sqrt{KT})$ के $\alpha$ -रेग्रेट अपर बाउंड प्राप्त करते हैं, जो मानक बैंडिट सेटिंग्स के लोअर बाउंड से मेल खाते हैं, जो यह संकेत देता है कि डेडलाइन्स की अतिरिक्त जटिलता लर्निंग रेट को कम नहीं करती है।
व्यावहारिक प्रेरणा: यह कार्य डिजिटल विज्ञापन (कम जीवनकाल वाली नीलामियों) और सेंसर नेटवर्क जैसे वास्तविक दुनिया के अनुप्रयोगों से प्रेरित है, जहाँ सख्त डेडलाइन्स के तहत अज्ञात रिवार्ड्स के साथ निर्णय लेने होते हैं।

लेखक निष्कर्ष निकालते हैं कि हालांकि उन्होंने विशिष्ट परिदृश्यों (विशेष रूप से 2-बाउंडेड इंस्टेंस) के लिए टाइट बाउंड स्थापित किए हैं, फिर भी सामान्य इंस्टेंस के लिए और कॉम्पिटिटिव रेश्यो को और कम करने के लिए रैंडमाइजेशन को सीमित-प्रकार (finite-type) धारणा के साथ जोड़ने के लिए चुनौतियाँ बनी हुई हैं।