Lagrangian Index Policy for Restless Bandits with Average Reward

कल्पना कीजिए कि आप छोटे, स्वायत्त ड्रोनों (autonomous drones) के एक विशाल बेड़े के कप्तान हैं, जिनमें से प्रत्येक को एक अलग काम सौंपा गया है। शायद एक सेंसर की जांच कर रहा है, दूसरा एक दस्तावेज़ को स्कैन कर रहा है, और तीसरा एक सिग्नल का इंतज़ार कर रहा है। पेच यह है कि आपके पास सीमित संख्या में रिमोट कंट्रोल हैं—मान लीजिए, आप एक समय में केवल दस ड्रोनों को ही "जगा" सकते हैं और सक्रिय रूप से प्रबंधित कर सकते हैं। बाकी को सोना होगा। लेकिन इसमें एक ट्विस्ट है: ये ड्रोन "बेचैन" (restless) हैं। सोते समय भी, उनकी आंतरिक बैटरी खत्म होती रहती है, उनके सेंसर भटक जाते हैं, या उनका डेटा पुराना हो जाता है। वे केवल स्थिर नहीं रहते; वे अपने आप अपनी स्थिति (state) बदलते रहते हैं। आपका लक्ष्य है, हर एक सेकंड में, यह तय करना कि प्रदर्शन को लंबे समय तक बेहतर बनाए रखने के लिए किन दस ड्रोनों को जगाना सबसे अच्छा होगा। यह "रेस्टलेस मल्टी-आर्म्ड बैंडिट" (Restless Multi-Armed Bandit) समस्या नामक कंप्यूटर विज्ञान और गणित की एक प्रसिद्ध पहेली का मूल है। यह स्लॉट मशीनों के एक उच्च-दांव वाले खेल जैसा है जहाँ मशीनें आपकी नज़र के बिना बदलती रहती हैं और आपको यह पता लगाए बिना कि वे अंदर से कैसे काम करती हैं, आपको यह तय करना होता है कि कब कौन सी मशीन चलानी है।

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

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

मुख्य विचार: विजेताओं को चुनने का एक नया तरीका

लेखक जो कर रहे हैं उसे समझने के लिए, आइए इस समस्या को एक रूपक (metaphor) के माध्यम से देखें। कल्पना कीजिए कि आप 100 छात्रों (यानी "आर्म्स" या "ड्रोन") की एक कक्षा के शिक्षक हैं। हर दिन, आप केवल 16 छात्रों को सवाल पूछने के लिए बुला सकते हैं (सक्रिय अवस्था)। बाकी 84 को चुपचाप बैठना होगा। हालाँकि, चुपचाप बैठे रहने के दौरान भी, छात्र बेचैन हो रहे हैं: कुछ जो सीखा था उसे भूल रहे हैं, कुछ ऊब रहे हैं, और कुछ अपने आप स्मार्ट हो रहे हैं। आपका लक्ष्य पूरे स्कूल वर्ष के दौरान कक्षा के औसत ज्ञान को अधिकतम करना है।

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

लेखक एक अलग दृष्टिकोण प्रस्तावित करते हैं: लैग्रेंजियन इंडेक्स। "कितना भुगतान करें?" पूछने के बजाय, वे एक सरल प्रश्न पूछते हैं: "इस छात्र को बुलाना उन्हें बैठने देने की तुलना में कितना बेहतर है?" वे छात्र को जगाने और उसे अकेला छोड़ने के बीच के "स्कोर" (इनाम) के अंतर की गणना करते हैं। यही अंतर लैग्रेंजियन इंडेक्स है। शिक्षक फिर बस उन 16 छात्रों को चुनता है जिनमें सबसे बड़ा अंतर होता है।

यह नया तरीका गेम चेंजर क्यों है

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

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

बिना मानचित्र के सीखना

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

उन्होंने दो प्रकार के लर्नर बनाए:

1. टेबुलर लर्निंग (Tabular Learning): यह एक विशाल स्प्रेडशीट को याद करने वाले छात्र जैसा है। यह छोटे समस्याओं के लिए अच्छा काम करता है लेकिन विशाल बेड़ों के लिए बहुत बड़ा हो जाता है।
2. डीप लर्निंग (न्यूरल नेटवर्क): यह एक ऐसे छात्र जैसा है जिसके पास सामान्यीकरण (generalize) करने वाला मस्तिष्क है। उन्होंने स्कोर का अनुमान लगाने के लिए एक न्यूरल नेटवर्क का उपयोग किया। लेखक मिले कि क्योंकि लैग्रेंजियन विधि सरल है, इसलिए न्यूरल नेटवर्क आर्किटेक्चर व्हिटल विधि के लिए आवश्यक आर्किटेक्चर की तुलना में बहुत कम जटिल और अधिक स्थिर है। यह एक साधारण घर बनाम एक गगनचुंबी इमारत बनाने के बीच के अंतर जैसा है; दोनों आश्रय दे सकते हैं, लेकिन साधारण घर बनाना और बनाए रखना आसान है।

यह साबित करना कि यह लंबे समय में काम करता है

लेखक केवल सिमुलेशन पर निर्भर नहीं रहे; उन्होंने एक कठोर गणितीय प्रमाण भी दिया है। उन्होंने दिखाया कि यदि आपके पास अनंत संख्या में आर्म्स (ड्रोन) हैं, और आप इस लैग्रेंजियन पॉलिसी का उपयोग करते हैं, तो आप अंततः सर्वोत्तम औसत इनाम प्राप्त करेंगे। उन्होंने डी फिनेटी के प्रमेय (de Finetti's theorem) नामक एक चतुर गणितीय उपकरण का उपयोग किया, जो अनिवार्य रूप से कहता है कि यदि आपके पास समान व्यवहार करने वाली चीजों का एक बड़ा समूह है, तो आप उन्हें समग्र समूह व्यवहार को ध्यान में रखते हुए स्वतंत्र मान सकते हैं। इसने उन्हें यह सिद्ध करने की अनुमति दी कि जैसे-जैसे आर्म्स की संख्या अनंत तक बढ़ती है, लैग्रेंजियन पॉलिसी पूरी तरह से इष्टतम हो जाती है।

वास्तविक दुनिया के परीक्षण

यह सुनिश्चित करने के लिए कि उनका सिद्धांत काम करता है, लेखकों ने कई संख्यात्मक प्रयोग किए:

• रीस्टार्ट समस्या (The Restart Problem): यह वेब क्रॉलिंग (यह जांचना कि वेबपेज बदला है या नहीं) या जानकारी को ताज़ा रखने जैसी चीजों को मॉडल करता है। यहाँ, लैग्रगेशन विधि व्हिटल विधि के समान ही प्रदर्शन करती है, लेकिन बहुत कम गणनात्मक प्रयास के साथ।
• "टूटी हुई" समस्या (The "Broken" Problem): उन्होंने मौजूदा साहित्य से एक समस्या का परीक्षण किया जिसे व्हिटल विधि को विफल करने के लिए जाना जाता है। जैसा कि अनुमान था, व्हिटल विधि संघर्ष करती रही, जबकि लैग्रेंजियन विधि ने बहुत अधिक इनाम दिया।
• डेडलाइन शेड्यूलिंग (Deadline Scheduling): उन्होंने नौकरियों (jobs) के डेडलाइन वाले परिदृश्य का अनुकरण किया। विषम (heterogeneous) आर्म्स के साथ भी, लैग्रेंजियन विधि ने मौजूदा सर्वोत्तम विधियों के प्रदर्शन की बराबरी की।

निष्कर्ष

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