तकनीकी सारांश: दुर्बल रूप से युग्मित (Weakly-Coupled) MDPs के लिए लियापुनोव-आधारित नमूना जटिलता विश्लेषण

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

यह शोध पत्र औसत-पुरस्कार (average-reward) वाले दुर्बल रूप से युग्मित मार्कोव निर्णय प्रक्रियाओं (WCMDPs) और रेस्टलेस बैंडिट्स (RBs) में निकट-इष्टतम नीतियों (near-optimal policies) को सीखने की नमूना जटिलता (sample complexity) को संबोधित करता है।

इन प्रणालियों में, $N$ स्वतंत्र भुजाएँ (subsystems), जिनमें से प्रत्येक एक MDP के रूप में मॉडल की गई है, वैश्विक लागत बाधाओं (जैसे कि सक्रिय भुजाओं की कुल संख्या पर बजट) के माध्यम से जुड़ी होती हैं। उद्देश्य दीर्घकालिक औसत पुरस्कार को अधिकतम करना है। मुख्य चुनौती "आयामीता का अभिशाप" (curse of dimensionality) है: प्रणाली को एक एकल अखंड (monolithic) MDP के रूप में देखने पर अवस्था-क्रिया स्थान (state-action space) का आकार $|S|^N \times |A|^N$ हो जाता है, जो $N$ के सापेक्ष चरघातांकीय (exponential) है। मौजूदा टैबुलर MDPs के लिए नैव (naive) अनुप्रयोग से प्राप्त होने वाले नमूना जटिलता सीमाएं, जो अवस्था-क्रिया स्थान के आकार के साथ स्केल करती हैं, $N$ में चरघातांकीय निर्भरता देती हैं, जिससे बड़े सिस्टम के लिए सीखना अव्यवहारिक हो जाता है।

यह शोध पत्र इस प्रश्न का उत्तर खोजने का प्रयास करता है: कोई व्यक्ति $N$ भुजाओं पर चरघातांकीय निर्भरता प्राप्त किए बिना औसत-पुरस्कार WCMDPs (या RBs) में एक निकट-इष्टतम नीति कैसे सीख सकता है?

2. कार्यप्रणाली

2.1. संदर्भ नीतियों के साथ प्लग-इन दृष्टिकोण

लेखक एक प्लग-इन दृष्टिकोण अपनाते हैं। सीधे अंतःक्रिया (interaction) से नीति सीखने के बजाय, वे:

1. प्रत्येक भुजा के प्रत्येक अवस्था-क्रिया युग्म के लिए $n$ i.i.d. नमूने एकत्र करते हैं ताकि एक अनुभवजन्य संक्रमण कर्नेल ($\hat{P}$) का निर्माण किया जा सके।
2. इस अनुभवजन्य मॉडल पर एक योजना एल्गोरिदम (planning algorithm) को हल करके एक नीति प्राप्त करते हैं।
3. विशिष्ट, कुशल योजना एल्गोरिदम को संदर्भ नीतियों (reference policies) के रूप में उपयोग करते हैं:
   • विषम (Heterogeneous) WCMDPs के लिए: ID नीति (Zhang et al., 2025), जो नियोजन शासन (planning regime) में $O(1/\sqrt{N})$ इष्टतमता अंतराल (optimality gap) प्राप्त करती है।
   • सजातीय (Homogeneous) RBs के लिए: दो-सेट नीति (two-set policy) (Hong et al., 2024a), जो विशिष्ट संरचनात्मक शर्तों के तहत एक चरघातांकीय रूप से छोटा इष्टतमता अंतराल ($O(e^{-cN})$) प्राप्त करती है।

2.2. नवीन लियापुनोव-आधारित विश्लेषण ढांचा

मुख्य तकनीकी नवाचार प्लग-इन दृष्टिकोण की नमूना जटिलता का विश्लेषण करने के लिए एक नया ढांचा है।

• शास्त्रीय सीमा: पारंपरिक विश्लेषण सिमुलेशन लेम्मा (simulation lemma) पर निर्भर करता है, जो MDP के बायस फंक्शन (सापेक्ष मूल्य फलन) का उपयोग करके प्रदर्शन अंतराल को सीमित करता है। बायस फंक्शन अक्सर अंतर्नि phép (implicit), जटिल और कठिन होता है, विशेष रूप से ID या दो-सेट नीतियों जैसे परिष्कृत योजना एल्गोरिदम के लिए।
• प्रस्तावित समाधान: लेखक बायस फंक्शन को एक स्पष्ट रूप से निर्मित लियापुनोव फलन ($V$) से बदल देते हैं।
  • चरण 1 (लियापुनोव विश्लेषण): वे स्थापित करते हैं कि संदर्भ नीति एक ड्रिफ्ट बाउंड (लियापुनोव फलन अपेक्षा में घटता है) और एक गैप डोमिनेंस स्थिति (पुरस्कार अंतराल लियापुनोव फलन द्वारा सीमित है) को संतुष्ट करती है।
  • चरण 2 (ड्रिफ्ट ट्रांसफर): वे इन सीमाओं को अनुभवजन्य प्रणाली में स्थानांतरित करते हैं। निर्मित लियापुनोव फलन के नॉर्म (norm) को स्पष्ट रूप से सीमित करके, वे मॉडल मिसमैच ($P - \hat{P}$) से उत्पन्न त्रुटि को नियंत्रित करते हैं।
  • लाभ: चूंकि $V$ को स्पष्ट रूप से निर्मित किया गया है, इसलिए इसके नॉर्म को सीमित करना सुलभ है, जिससे अंतर्नि phép बायस फंक्शन से जुड़ी कठिनाइयों से बचा जा सकता है।

2.3. सूक्ष्म-स्तरीय LP विक्षोभ विश्लेषण (Fine-Grained LP Perturbation Analysis)

सजातीय RB मामले के लिए, एक महत्वपूर्ण चरण में एकल-भुजा नीति को प्राप्त करने के लिए उपयोग किए जाने वाले रैखिक प्रोग्रामिंग (LP) विश्रांति (relaxation) का विश्लेषण शामिल है।

• लेखक सिद्ध करते हैं कि हल्के संरचनात्मक अनुमानों (ergodicity, non-degeneracy, local stability) के तहत, LP का समाधान संक्रमण कर्नेल में विक्षोभों के प्रति मजबूत (robust) है।
• विशेष रूप से, वे दिखाते हैं कि इष्टतम समाधान का समर्थन (support) (कौन सी क्रियाएं किन अवस्थाओं में ली जाती हैं) छोटे विक्षोभों के तहत स्थिर रहता है, सिवाय संभवतः एक एकल "तटस्थ अवस्था" (neutral state) के।
• यह सुनिश्चित करता है कि अनुभवजन्य नीति उन संरचनात्मक गुणों को बनाए रखती है जो लियापुनोव विश्लेषण को मान्य करने के लिए आवश्यक हैं।

3. मुख्य परिणाम

3.1. विषम WCMDPs

पूर्णतः विषम WCMDPs के लिए, यह शोध पत्र पहला परिमित-नमूना PAC (Probably Approximately Correct) गारंटी स्थापित करता है जिसमें बहुपद जटिलता (polynomial complexity) है।

• परिणाम: सीखी गई नीति $\hat{\pi}_{ID}$ निम्नलिखित इष्टतमता अंतराल प्राप्त करती है:
  $$\rho^* - \rho_{\hat{\pi}_{ID}} \leq O\left(\frac{\sqrt{S + \log(N/\eta)}}{\sqrt{n}} \cdot N\right) + O\left(\frac{1}{\sqrt{N}}\right)$$
  जहाँ $n$ प्रत्येक भुजा के प्रत्येक अवस्था-क्रिया युग्म के लिए नमूनों की संख्या है।
• नमूना जटिलता: $\epsilon = \Omega(1/\sqrt{N})$ अंतराल प्राप्त करने के लिए, आवश्यक कुल नमूनों की संख्या $N$ में बहुपद रूप से (विशेष रूप से $O(N^3)$ कुल नमूने) स्केल करती है, न कि चरघातांकीय रूप से।

3.2. सजातीय रेस्टलेस बैंडिट्स

सजातीय RBs के लिए, हल्के संरचनात्मक अनुमानों (Assumptions 2 and 3) के तहत, सीखी गई नीति $\hat{\pi}_{TS}$ काफी अधिक सटीक (tighter) सीमा प्राप्त करती है।

• परिणाम: इष्टतमता अंतराल इस प्रकार सीमित है:
  $$\rho^* - \rho_{\hat{\pi}_{TS}} \leq O\left(\frac{\sqrt{S + \log(1/\eta)}}{\sqrt{n}} \cdot N\right) + O(e^{-cN})$$
• नमूना जटिलता: चूंकि संदर्भ नीति का अंतर्निहित अंतराल चरघातांकीय रूप से छोटा है, इसलिए सीखने वाला एल्गोरिदम $n$ के ऐसे नमूना आकार के साथ $\epsilon = \Omega(e^{-cN})$ का अंतराल प्राप्त कर सकता है जो $N$ में बहुपद रूप से स्केल करता है।
• ब्लॉकिंग स्कीम: लेखक एक निश्चित नमूना आकार के लिए एक "ब्लॉकिंग" तकनीक भी प्रस्तावित करते हैं, जो परिमित-नमूना त्रुटि और संदर्भ नीति के इष्टतमता अंतराल के बीच संतुलन बनाने के लिए भुजाओं को ब्लॉकों में विभाजित करती है, जो इस दृष्टिकोण के लचीलेपन को और प्रदर्शित करती है।

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

शोध पत्र तीन प्राथमिक योगदानों का दावा करता है:

1. चरघातांकीय बाधा को तोड़ना: यह प्रदर्शित करता है कि दुर्बल रूप से युग्मित संरचना का लाभ उठाकर, एक व्यक्ति $N$ में बहुपद (polynomial) जटिलता के साथ निकट-इष्टतम नीतियां सीख सकता है। यह बड़े पैमाने के WCMDPs और RBs के लिए सीखने की चुनौती को औपचारिक रूप से हल करता है, जो उन्हें एक अखंड MDP के रूप में मानने से होने वाली चरघातांकीय जटिलता के विपरीत है।
2. नवीन विश्लेषण ढांचा: लियापुनोव-आधारित विश्लेषण ढांचे को औसत-पुरस्कार प्रणालियों में प्लग-इन दृष्टिकोणों के विश्लेषण के लिए एक सामान्य उपकरण के रूप में प्रस्तुत किया गया है। कठिन-से-नियंत्रित बायस फंक्शन से विश्लेषण को अलग करके और स्पष्ट लियापुनोव फलनों का उपयोग करके, यह ढांचा जटिल योजना एल्गोरिदम के लिए परिमित-नमूना गारंटी स्थापित करने के लिए एक शक्तिशाली विधि प्रदान करता है।
3. LP-आधारित नीतियों की मजबूती: LP विश्रांति का सूक्ष्म-स्तरीय विक्षोभ विश्लेषण एक अंतर्निहित मजबूती गुण को प्रकट करता: इस LP के माध्यम से निर्मित नीतियां मॉडल विक्षोभों के प्रति स्थिर हैं। यह परिणाम स्वतंत्र रूप से भी महत्वपूर्ण है और साहित्य में अन्य इंडेक्स और LP-प्रायोरिटी नीतियों के विश्लेषण के लिए एक मजबूती मॉड्यूल के रूप में कार्य कर सकता है।

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