तकनीकी सारांश: रीचेबिलिटी के लिए सुदृढीकरण शिक्षण (Reinforcement Learning): स्पर्शोन्मुख इष्टतमता (Asymptotic Optimality) की गारंटी

1. समस्या विवरण

यह शोध पत्र अज्ञात मार्कोव निर्णय प्रक्रियाओं (MDPs) में रीचेबिलिटी स्पेसिफिकेशन (reachability specifications) के तहत इष्टतम नीतियों (optimal policies) को सीखने की चुनौती का समाधान करता है। जबकि रिवॉर्ड-आधारित उद्देश्यों के लिए सुदृढीकरण शिक्षण (RL) के पास मजबूत सैद्धांतिक गारंटी (स्पर्शोन्मुख अभिसरण और PAC गारंटी) है, उच्च-स्तरीय टेम्पोरल लॉजिक स्पेसिफिकेशन (जैसे कि लीनियर टेम्पोरल लॉजिक, LTL) के तहत सीखना सैद्धांतिक रूप से कम खोजा गया विषय रहा है।

विशेष रूप से, लेखक मौजूदा साहित्य में दो अंतराल (gaps) को रेखांकित करते हैं:

1. PAC सीमाएँ: सामान्य LTL स्पेसिफिकेशन को बिना आंतरिक MDP मापदंडों (जैसे कि न्यूनतम गैर-शून्य संक्रमण संभाव्यता $p_{min}$, मिक्सिंग टाइम) को जाने PAC गारंटी के साथ नहीं सीखा जा सकता है। ये पैरामीटर मानक RL सेटिंग्स में आमतौर पर अज्ञात होते हैं।
2. स्पर्शोन्मुख (Asymptotic) सीमाएँ: LTL के लिए स्पर्शोन्मुख अभिसरण प्राप्त करने वाला पिछला कार्य (जैसे कि Le et al., 2024) लिमिट-एवरेज रिवॉर्ड उद्देश्यों में स्पेसिफिकेशन को बदलने पर निर्भर करता है। यह दृष्टिकोण बाहरी मापदंडों (डिस्काउंट फैक्टर्स) पर निर्भर है जो MDP की आंतरिक संरचना से कटे हुए हैं, जिससे यह कोई अंतर्दृष्टि नहीं मिलती कि कब इष्टतमता उभरती है या अभिसरण की गति क्या है।

मुख्य समस्या एक अज्ञात MDP में रीचेबिलिटी के लिए एक शिक्षण एल्गोरिदम डिजाइन करना है जो स्पर्शोन्मुख अभिसरण (संभाव्यता 1 के साथ इष्टतम नीति की ओर अभिसरण) प्राप्त करता है, जबकि रिवॉर्ड रूपांतरण या बाहरी मापदंडों पर निर्भर किए बिना अवलोकनीय गारंटी (observable guarantees) प्रदान करता है कि इष्टतम नीति कब उभरती है।

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

लेखक एक स्टेज्ड डायरेक्ट लर्निंग एल्गोरिदम (staged direct learning algorithm) प्रस्तावित करते हैं जो रीचेबिलिटी उद्देश्य को रिवॉर्ड फंक्शन में बदले बिना कार्य करता है। इसके बजाय, यह आंतरिक MDP मापदंडों के अनुमानों को पुनरावृत्त रूप से परिष्कृत करने पर निर्भर करता है।

मुख्य एल्गोरिद्मिक ढांचा

एल्गोरिदम असतत चरणों (discrete stages) $k = 1, 2, 3, \dots$ में आगे बढ़ता है। प्रत्येक चरण में, तीन प्रमुख मापदंडों को तेजी से (exponentially) घटते हुए सेट किया जाता है:

• न्यूनतम संक्रमण संभाव्यता का अनुमान: $p_k = 1/2^k$
• कॉन्फिडेंस एरर (Confidence error): $\delta_k = 1/2^k$
• अनुमान कारक (Approximation factor): $\epsilon_k = 1/2^k$

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

1. सिमुलेशन और मॉडल निर्माण: एल्गोरिदम आंशिक मॉडल बनाने के लिए MDP को $N_k$ बार सिम्युलेट करता है, जिसमें स्टेट-एक्शन ट्रांजिशन के लिए काउंटर्स बनाए रखे जाते हैं।
2. ट्रांजिशन एस्टीमेशन: यह होफडिंग बाउंड्स (Hoeffding bounds) का उपयोग करके संक्रमण संभाव्यता के निचले अनुमानों की गणना करता है।
3. एंड-कंपोनेंट्स (ECs) को संभालना: ECs (चक्र जहाँ एजेंट फंस सकता है) की उपस्थिति में वैल्यू इटरेशन के अभिसरण को सुनिश्चित करने के लिए, एल्गोरिदम ECs का पता लगाता है और उन्हें सुपर-स्टेट्स में कोलैप्स (collapse) कर देता है। यह एक "कोलैप्स्ड MDP" बनाता है जहाँ ECs को विशिष्ट बाउंड्री कंडीशंस (लक्ष्य अवस्था होने के आधार पर मान 0 या 1) के साथ एकल अवस्थाओं के रूप में माना जाता है।
4. बाउंडेड वैल्यू इटरेशन (BVI): एल्गोरिदम रीचेबिलिटी संभाव्यता के निचले ($L$) और ऊपरी ($U$) बाउंड्स की गणना करने के लिए कोलैप्स्ड आंशिक मॉडल पर BVI चलाता है।
5. पॉलिसी एक्सट्रैक्शन: आंशिक मॉडल में ऊपरी बाउंड्स के आधार पर एक मेमोरीलेस डिटर्मिनिस्टिक पॉलिसी निकाली जाती है।

अभिसरण के लिए सैद्धांतिक तंत्र

अभिसरण तीन सैद्धांतिक स्तंभों पर निर्भर करता है:

1. PAC गारंटी (थ्योरम 3.1): एक बार जब चरण सूचकांक $k$ इतना बड़ा हो जाता है कि अनुमानित $p_k \le p_{min}$ (वास्तविक न्यूनतम गैर-शून्य संक्रमण संभाव्यता) हो, तो एल्गोरिदम गारंटी देता है कि निकाला गया पॉलिसी $1 - \delta_k$ प्रायिकता के साथ $\epsilon_k$-इष्टतम है।
2. सटीक इष्टतमता (थ्योरम 3.2): लेखक $\epsilon_{diff}$ को इष्टतम नीति और सर्वश्रेष्ठ उप-इष्टतम मेमोरीलेस डिटर्मिनिस्टिक नीति के बीच न्यूनतम मान पृथक्करण (value separation) के रूप में परिभाषित करते हैं। चूंकि ऐसी कई पॉलिसियाँ सीमित हैं, इसलिए $\epsilon_{diff} > 0$ है। जैसे-जैसे $k$ बढ़ता है, $\epsilon_k$ सिकुड़ता जाता है। इस बिंदु पर (चरण $K_{opt}$), कोई भी $\epsilon_k$-इष्टतम नीति सटीक रूप से इष्टतम होनी चाहिए।
3. लगभग-निश्चित अभिसरण (Almost-Sure Convergence) (थ्योरम 3.3): $\delta_k = 1/2^k$ चुनकर, सभी चरणों में विफलता की प्रायिकताओं का योग परिमित (finite) है। बोरेल-कैंटीली लेम्मा (Borel–Cantelli Lemma) द्वारा, प्रायिकता 1 के साथ, केवल सीमित संख्या में चरण विफल होंगे। फलस्वरूप, एक परिमित चरण $K$ के बाद, एल्गोरिदम केवल इष्टतम पॉलिसियाँ ही उत्पन्न करता है।

3. मुख्य योगदान

• डायरेक्ट लर्निंग दृष्टिकोण: यह शोध पत्र रीचेबिलिटी स्पेसिफिकेशन के लिए पहला प्रत्यक्ष शिक्षण दृष्टिकोण प्रस्तुत करता है जो LTL को रिवॉर्ड-आधारित उद्देश्यों में बदलने से बचता है, जिससे MDP की अंतर्निहित संरचना सुरक्षित रहती है।
• स्पर्शोन्मुख अभिसरण से अधिक मजबूत: मानक स्पर्शोन्मुख गारंटी के विपरीत जहाँ पॉलिसियाँ केवल इष्टतमता की ओर बढ़ती हैं, यह कार्य सिद्ध करता है कि प्रायिकता 1 के साथ, एक परिमित चरण $K_{opt}$ के बाद केवल इष्टतम पॉलिसियाँ ही देखी जाती हैं।
• अभिसरण गतिकी का लक्षण वर्णन: चरण $K_{opt}$ को आंतरिक MDP मात्राओं, विशेष रूप रूप से वैल्यू सेपरेशन $\epsilon_{diff}$ द्वारा स्पष्ट रूप से वर्णित किया गया है। यह यह समझने के लिए एक सैद्धांतिक सीमा प्रदान करता है कि इष्टतमता कब उभरती है।
• वैल्यू सेपरेशन पर बाउंड्स: पेपर $\epsilon_{diff}$ के लिए एक निचला बाउंड (lower bound) MDP की ट्रांजिशन जटिलता के आधार पर निकालता है (थ्योरम 4.1), यह दिखाते हुए कि इष्टतम और उप-इष्टतम पॉलिसियों के बीच का अंतर ट्रांजिशन प्रोबेबिलिटी के हर (denominators) पर निर्भर करता है।
• अनुभवजन्य सत्यापन (Empirical Validation): एल्गोरिदम को 9 मानक MDP बेंचमार्क पर लागू किया गया और परीक्षण किया गया। परिणाम दिखाते हैं कि इष्टतम पॉलिसियाँ तेजी से उभरती हैं (औसत चरण $k=2$), जो अक्सर वैल्यू बाउंड्स ($L$ और $U$) के पूरी तरह से अभिसरण करने से बहुत पहले होता है।

4. परिणाम

• सैद्धांतिक: एल्गोरिदम को प्रायिकता 1 के साथ स्पर्शोन्मुख रूप से अभिसरण करने के लिए सिद्ध किया गया है। इसके अलावा, यह गारंटी देता है कि एक विशिष्ट परिमित चरण के बाद, आउटपुट केवल इष्टतम नीति है, न कि केवल एक सन्निकटन (approximation)।
• अनुभवजन्य:
  • बेंचमार्क (जैसे कि डाइनिंग फिलोसोफर्स, CSMA, Zeroconf) पर प्रयोगों से पता चलता है कि "केवल-इष्टतम-पॉलिसी" वाला शासन (regime) जल्दी उभर आता है।
  • एक उल्लेखनीय अवलोकन यह है कि पॉलिसी सटीकता, वैल्यू बाउंड्स की तुलना में काफी पहले स्थिर हो जाती है। उदाहरण के लिए, डाइनिंग फिलोसोफर्स बेंचमार्क में, पॉलिसी सटीकता चरण $k=2$ पर स्थिर हुई, जबकि वैल्यू बाउंड्स केवल $k=16$ के आसपास अभिसरित होना शुरू हुए। यह सुझाव देता है कि एल्गोरिदम सही नीति तब भी खोज लेता है जब वैल्यू अनुमान अभी तक सटीक (tight) नहीं होते हैं।
  • एल्गोरिदम विभिन्न रीचेबिलिटी प्रोबेबिलिटीज़ (0.00 से 1.00 तक) वाले बेंचमार्क को सफलतापूर्वक संभालता है।

5. महत्व और दावे

लेखक दावा करते हैं कि यह कार्य समृद्ध टेम्पोरल स्पेसिफिकेशन से सीखने वाले व्यावहारिक RL सिस्टम के लिए एक ठोस आधार प्रदान करता है।

• मौलिक प्रिमिटिव (Fundamental Primitive): रीचेबिलिटी को सभी $\omega$-रेगुलर और LTL स्पेसिफिकेशन के लिए मुख्य कम्प्यूटेशनल प्रिमिटिव के रूप में पहचाना गया है। इसलिए, रीचेबिलिटी अभिसरण के लिए एक सिद्धांतपूर्ण एल्गोरिदम तुरंत पूर्ण L_T_L उद्देश्यों के लिए भी एक एल्गोरिदम प्रेरित करता है।
• अवलोकनीय गारंटी: बाहरी रिवॉर्ड रूपांतरण के बजाय आंतरिक MDP मापदंडों के संदर्भ में अभिसरण को चित्रित करके, यह दृष्टिकोण एल्गोरिदम डिजाइन के बारे में गहरी अंतर्दृष्टि प्रदान करता है और अवलोकनीय अभिसरण गारंटी के साथ कार्यान्वयन को सक्षम बनाता है।
• विनम्रता: लेखक स्वीकार करते हैं कि उनका वर्तमान दृष्टिकोण मॉडल-आधारित (model-based) है। वे स्पष्ट रूप से कहते हैं कि इस ढांचे को मॉडल-मुक्त तरीकों (model-free methods) (स्पष्ट मॉडल निर्माण के बिना सीधे पॉलिसियों को सीखना) तक विस्तारित करना भविष्य के व्यावहारिक परिनियोजन और स्केलेबिलिटी के लिए एक महत्वपूर्ण मार्ग है। वे तत्काल सामाजिक प्रभाव का दावा नहीं करते हैं, बल्कि इस कार्य को विश्वसनीय मशीन लर्निंग थ्योरी में एक प्रगति के रूप में रखते हैं।