PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

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

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

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

---

पासे के साथ लुका-छिपी का महान खेल

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

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

"प्रतीक्षा का खेल" (The "Waiting Game" Problem)

यह समझने के लिए कि यह इतना कठिन क्यों है, कल्पना कीजिए कि एक ऐसा खेल है जहाँ खजाना एक ऐसे दरवाजे के पीछे छिपा है जो केवल दस लाख वर्षों में एक बार खुलता है। यदि खिलाड़ी केवल अनुमान लगा रहे हैं, तो वे अनंत काल तक प्रतीक्षा कर सकते हैं। गणित की दुनिया में, इसे "इनफिनिट होराइजन" (infinite horizon) समस्या कहा जाता है। यदि खेल अनंत काल तक चल सकता है, और प्रतिद्वंद्वी आपको रोकने में सक्षम है, तो आप कभी भी सुनिश्चित नहीं हो सकते कि आप सही चीज़ सीख रहे हैं या बस एक ऐसे चमत्कार का इंतजार कर रहे हैं जो शायद कभी नहीं होगा।

लेखकों ने महसूस किया कि सीखने के लिए संभव होने हेतु, उन्हें एक सुरक्षा जाल की आवश्यकता थी। उन्होंने एक अवधारणा पेश की जिसे एक्सपेक्टेड कंडिशनल डिस्टेंस (Expected Conditional Distance - ECD) कहा जाता है। इसे खेल के लिए "धैर्य मीटर" (patience meter) के रूप में सोचें। यह मापता है: "यदि लक्ष्य तक पहुँचना संभव है, तो वहाँ पहुँचने में औसतन कितना समय लगता है?" यदि ECD कम है, तो इसका मतलब है कि खेल बहुत लंबा नहीं खिंचता; खजाना आमतौर पर अपेक्षाकृत जल्दी मिल जाता है। यदि ECD बहुत बड़ा है, तो इसका मतलब है कि खेल अनंत समय तक इंतजार करने के चक्र में फंस सकता है।

पत्र यह सिद्ध करता है कि यदि यह "धैर्य मीटर" सीमित है (यानी खेल समाप्त होने में अनंत समय नहीं लगता), तो अंधेरे में भी सीखना संभव है। उन्होंने दिखाया कि इस संख्या को जानकर, आप प्रभावी रूप से अनंत खेल को एक सीमित खेल में बदल सकते हैं, जैसे कि खेल को कुछ चालों के बाद रोक देना क्योंकि आप जानते हैं कि तब तक खजाना मिल चुका होता। यह ध्यान देना महत्वपूर्ण है कि बिना ऐसे अनुमान (जैसे ECD, या पिछले साहित्य में पाए जाने वाले अन्य समान प्रतिबंध) के, इस प्रकार के खेलों के लिए सीखना सामान्य रूप से असंभव है। शोध पत्र यह दावा नहीं करता कि ECD एकमात्र तरीका है, लेकिन यह वह विशिष्ट कुंजी है जिसका उपयोग उन्होंने इस नए परिवेश में समस्या को सुलझाने के लिए किया है।

गुप्त नुस्खा: चरणों में सीखना

तो, वे वास्तव में खिलाड़ियों को कैसे सिखाते हैं? लेखकों ने लर्निंग एल्गोरिदम की एक चतुर जोड़ी (एक मैक्स के लिए, एक मिन के लिए) डिजाइन की है जो एक गुफा का मानचित्र बनाने वाले खोजकर्ताओं की टीम की तरह काम करती है।

1. मानचित्र विस्तार (The Map Expansion): केवल "स्टेट A" या "स्टेट B" के बारे में सोचने के बजाय, खिलाड़ी एक 3D मानचित्र की कल्पना करते हैं जहाँ तीसरा आयाम "समय" है। वे खेल को "स्टेट-स्टेप" जोड़ों में तोड़ देते हैं। यह यह कहने जैसा है कि, "स्टेप 1 पर, मैं किचन में हूँ; स्टेप 2 पर, मैं हॉलवे में हूँ।" यह उन्हें अंत से पीछे की ओर योजना बनाने में मदद करता है।
2. "बेस्ट आर्म" तकनीक (The "Best Arm" Trick): अपने मानचित्र के हर स्थान पर, खिलाड़ियों को एक क्रिया चुननी होती है। वे "बैंडिट लर्निंग" (कल्पना कीजिए कि एक जुआरी सबसे अच्छा स्लॉट मशीन खोजने की कोशिश कर रहा है) नामक क्षेत्र की एक तकनीक का उपयोग करते हैं। वे अलग-अलग चालें आजमाते हैं, देखते हैं कि कौन सी सबसे अच्छी है, और उसी पर टिके रहते हैं। लेकिन वे इसे उच्च विश्वास के साथ करते हैं, यह सुनिश्चित करते हुए कि वे केवल भाग्यशाली नहीं हैं।
3. एक्सप्लोरेशन लूप (The Exploration Loop): खिलाड़ी अपने मानचित्र के अनछुए हिस्सों की खोज करके शुरुआत करते हैं। वे इन अज्ञात स्थानों को खोजने के लिए नए "खजाने" के रूप में देखते हैं। एक बार जब वे किसी विशिष्ट स्थान के लिए सबसे अच्छी चाल समझ लेते हैं, तो वे उसे "एक्सप्लोर किया गया" के रूप में चिह्नित करते हैं और आगे बढ़ जाते हैं। वे ऐसा करते रहते हैं, चरण-दर-चरण अपनी रणनीति बनाते हैं, जब तक कि उनके पास पूरे खेल के लिए एक योजना न हो।
4. निजी सहमति (The Private Agreement): यहाँ जादू है। भले ही वे कभी बात नहीं करते, वे दोनों एक समान लय का पालन करते हैं। वे तब तक खेलते रहते हैं जब तक कि दोनों को यह महसूस न हो जाए कि उन्होंने पर्याप्त अन्वेषण कर लिया है। जब कोई भी खिलाड़ी अपने निजी दृष्टिकोण में कोई नया "अनएक्सप्लोर्ड" स्थान नहीं ढूंढ पाता, तो वे दोनों गेम सिम्युलेटर को संकेत देते हैं: "हम समाप्त! यह हमारी रणनीति है।"

परिणाम: सीखने का एक नया प्रकार

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

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

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

आपको इसकी परवाह क्यों करनी चाहिए?

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

यह शोध पत्र हमें एक नया टूलकिट देता है। यह हमें बताता है कि भले ही हम अपने सभी AI एजेंटों को अपने रहस्य साझा करने के लिए मजबूर न कर सकें, और भले ही वे एक-दूसरे को मात देने की कोशिश कर रहे हों, फिर भी हम उन्हें स्मार्ट और सुरक्षित होने के लिए सिखा सकते हैं, बशर्ते हमें पता हो कि "बुरी चीजें" अनंत समय के बाद नहीं होंगी। यह हमें ऐसे AI बनाने की दिशा में एक कदम है जो बिना किसी केंद्रीय बॉस के निर्देश के, एक अराजक और अनिश्चित दुनिया में नेविगेट कर सके।

संक्षेप में, लेखकों ने एक ऐसी समस्या को हल किया जो असंभव लग रही थी—एक प्रतिद्वंद्वी के साथ अंधेरे में एक खेल सीखना—और धैर्य के एक चतुर माप और बहुत अधिक पीछे की ओर सोचने (backward thinking) का उपयोग करके धीरे-धीरे रोशनी लाने का एक तरीका खोज निकाला।