तकनीकी सारांश: एक एकल प्रक्षेपवक्र (Single Trajectory) से औसत-पुरस्कार मार्कोव निर्णय प्रक्रिया (Average-Reward MDP) में नीति सीखना

समस्या विवरण (Problem Statement)

यह शोध पत्र औसत-पुरस्कार मार्कोव निर्णय प्रक्रियाओं (average-reward MDPs) में $\epsilon$-इष्टतम नीति खोजने की चुनौती को संबोधित करता है, जो एकल प्रक्षेपवक्र (single trajectory) से प्राप्त सीमित नमूना जटिलता गारंटी (finite sample complexity guarantees) पर आधारित है।

जबकि डिस्काउंटेड (discounted) संचयी-पुरस्कार MDPs के नमूना जटिलता पर व्यापक साहित्य मौजूद है, औसत-पुरस्कार MDPs के लिए विश्लेषण ऐतिहासिक रूप से प्रतिबंधात्मक धारणाओं पर निर्भर रहे हैं। मौजूदा कार्य आमतौर पर इनमें से किसी एक की आवश्यकता रखते हैं:

1. जेनरेटिव मॉडल (Generative models): एक सिम्युलेटर तक पहुंच जो किसी भी अवस्था (state) में रीसेट कर सके।
2. i.i.d. ऑफलाइन डेटा।
3. मजबूत संरचनात्मक धारणाएं, जैसे कि एर्गोडिसिटी (ergodicity) (जहाँ प्रत्येक नीति एक एकल आवर्ती वर्ग (recurrent class) प्रेरित करती है) या व्यवहार नीति (behavior policy) पर विशिष्ट कवरेज स्थितियाँ।

यह कार्य जिस विशिष्ट अंतराल को लक्षित करता है, वह है कमजोर संचारित (weakly communicating) सेटिंग। कमजोर संचारित MDPs में, किसी भी "सुव्यवस्थित" नीति के तहत अवस्था स्थान (state space) एक एकल आवर्ती वर्ग और एक क्षणिक सेट (transient set) में विभाजित हो जाता है, लेकिन सिस्टम अनिवार्य रूप से एर्गोडिक नहीं होता है (क्षणिक अवस्थाएँ मौजूद होती हैं)। इस कार्य से पूर्व, इस सेटिंग में एकल प्रक्षेपवपथ से औसत-पुरस्कार RL के लिए सीमित नमूना जटिलता विश्लेषण अनछुआ था।

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

लेखक एक सैद्धांतिक ढांचा और नवीन मॉडल-मुक्त एल्गोरिदम विकसित करते हैं जो कमजोर रूप से संचारित MDPs के संरचनात्मक गुणों, विशेष रूप से अवस्थाओं के आवर्ती-क्षणिक वर्गीकरण (recurrent-transient classification) का लाभ उठाते हैं।

1. एकल प्रक्षेपवक्र का संरचनात्मक विश्लेषण

मुख्य तकनीकी योगदान एक व्यवहार नीति $\pi_b$ द्वारा उत्पन्न एकल प्रक्षेपवक्र का स्टोकेस्टिक विश्लेषण है। लेखक स्थापित करते हैं कि:

• आवर्ती-क्षणिक अपरिवर्तनीयता (Recurrent-Transient Invariance): नीति स्थान ($\Pi_+$) के भीतर की नीतियों के लिए, अवस्थाओं का एक एकल आवर्ती वर्ग ($R$) और एक क्षणिक सेट ($T$) में वर्गीकरण अपरिवर्तनीय है और केवल संक्रमण कर्नेल (transition kernel) $P$ द्वारा निर्धारित होता है, न कि विशिष्ट नीति चयन द्वारा।
• क्षणिक अवस्थाओं से निकलना (Escaping Transient States): मार्कोव की असमानता (Markov's inequality) और स्ट्रॉन्ग मार्कोव प्रॉपर्टी का उपयोग करते हुए, वे सिद्ध करते हैं कि एक क्षणिक अवस्था से शुरू होने वाला प्रक्षेपवक्र उच्च संभावना के साथ एक परिमित हिटिंग समय (hitting time) ($t_{hit}$) के भीतर आवर्ती वर्ग $R$ तक पहुँच जाएगा।
• आवर्ती वर्ग को कवर करना (Covering the Recurrent Class): एक बार $R$ में पहुँचने के बाद, प्रक्षेपवक्र एक परिमित कवरिंग समय (covering time) ($t_{cov}$) के भीतर $R$ की सभी अवस्थाओं को कवर करता है।
• Stopping Times के माध्यम से i.i.d. नमूनाकरण: स्टॉपिंग टाइम्स (विशेष रूप से, वे समय जब प्रक्षेपवक्र एक विशिष्ट अवस्था $s$ पर वापस आता है) का उपयोग करके, लेखक दिखाते हैं कि एक एकल प्रक्षेपवक्र से प्राप्त नमूनों को सांद्रता असमानताओं (concentration inequalities) के उद्देश्य से स्वतंत्र और समान रूप से वितरित (i.i.d.) माना जा सकता है (लेम्मा 2.3)। यह बिना मिक्सिंग टाइम धारणाओं की आवश्यकता के, एकल-प्रक्षेपवक्र विश्लेषण में निहित निर्भरता संबंधी समस्याओं को हल करता है।

2. वैल्यू-आधारित विधि: SAVIC

स्टोकेस्टिक एंकरड वैल्यू इटरेशन (SAVIC) एक मॉडल-मुक्त वैल्यू-आधारित एल्गोरिदम है जिसे कमजोर रूप से संचारित MDPs के लिए डिज़ाइन किया गया है। यह तीन चरणों में कार्य करता है:

1. आवर्ती अवस्था पहचान (Recurrent State Identification): एजेंट क्षणिक अवस्थाओं से निकलने और सभी आवर्ती अवस्थाओं ($R$) की सूची एकत्र करने के लिए एक व्यवहार नीति चलाता है (Algorithm 1 (RECUR) का उपयोग करके)।
2. एन्करड इटरेशन विद वेरिएंस रिडक्शन (Anchored Iteration with Variance Reduction): आवर्ती वर्ग के भीतर, एल्गोरिदम एन्करड वैल्यू इटरेशन (Anc-QI) करता है। मानक VI के विपरीत, Anc-QI अगले इटरेट को बेलमैन अपडेट और प्रारंभिक बिंदु ($Q_0$) के एक कॉनवेक्स कॉम्बिनेशन के रूप में कंप्यूट करता है। यह "एंकर" शब्द गैर-एसिम्प्टोटिक अभिसरण (non-asymptotic convergence) सुनिश्चित करता है।
   • कुशल नमूना जटिलता प्राप्त करने के लिए, विधि एक रिकर्सिव सैंपलिंग तकनीक का उपयोग करती है। प्रत्येक चरण में पूर्ण बेलमैन ऑपरेटर $T(Q_k)$ का अनुमान लगाने के बजाय, यह वेरिएंस-रिड्यूस्ड सैंपलिंग का उपयोग करके अंतर $T(Q_k) - T(Q_{k-1})$ का अनुमान लगाता है।
3. नीति विचलन (Policy Perturbation): चूँकि एल्गोरिदम केवल आवर्ती वर्ग $R$ पर अनुकूलन करता है, इसलिए अंतिम नीति को पूरे अवस्था स्थान $S$ (जिसमें क्षणिक अवस्थाएँ भी शामिल हैं) पर $\epsilon$-इष्टतम सुनिश्चित करने के लिए विचलित (perturb) किया जाता है।

3. पूर्व ज्ञान के बिना मॉडल-मुक्त विधि: SAVIC+

संचारित MDPs (जहाँ $S=R$, यानी कोई क्षणिक अवस्था नहीं है) के लिए, लेखक SAVIC+ पेश करते हैं।

• यह समस्या-निर्भर स्थिरांक (जैसे $t_{hit}$, $t_{cov}$, या न्यूनतम स्टेशनरी वितरण प्रायिकता $d_{min}$) के पूर्व ज्ञान की आवश्यकता को समाप्त करता है।
• यह एक डबलिंग ट्रिक (doubling trick) और अनुभवजन्य बेलमैन अवशेष त्रुटि ($\|Q - TQ\|_{sp}$) पर आधारित एक स्पष्ट स्टॉपिंग नियम का उपयोग करता है।
• यह प्रत्येक अवस्था-क्रिया युग्म (state-action pair) के लिए पर्याप्त संख्या प्राप्त होने तक स्वचालित रूप से नमूने एकत्र करने के लिए Algorithm 4 (SAMPLE+) का उपयोग करता है।

4. नीति-आधारित विधि: SCPMA

स्टोकेस्टिक $\alpha$-क्लिप्ड पॉलिसी मिरर एसेंट (SCPMA) कमजोर रूप से संचारित MDPs के लिए एक पॉलिसी ग्रेडिएंट विधि है।

• यह एक नवीन पॉलिसी इवैल्यूएशन एल्गोरिदम (SAVIPE) का उपयोग करता है जो उसी एंकरिंग और वेरिएंस-रिडक्शन तंत्र का उपयोग करके अवस्था-क्रिया मान फलन (state-action value function) का अनुमान लगाता है जैसा कि SAVIC में है।
• नीति अपडेट पॉलिसी मिरर एसेंट ढांचे का अनुसरण करता है लेकिन यह सुनिश्चित करने के लिए कि नीति नीति स्थान ($\Pi_\alpha$) के आंतरिक भाग में बनी रहे, $\alpha$-क्लिपिंग लागू करता है। यह क्लिपिंग नमूना जटिलता विश्लेषण में गुणांकों (coefficients) को बांधने के लिए महत्वपूर्ण है।
• यह विधि स्थिर और अनुकूलित (adaptive) दोनों स्टेप साइज़ का समर्थन करती है।

मुख्य परिणाम (Key Results)

यह शोध पत्र कमजोर रूप से संचारित सेटिंग्स में एकल प्रक्षेपवपथ से औसत-पुरस्कार MDPs के लिए पहले परिमित नमूना जटिलता गारंटी स्थापित करता है।

1. SAVIC (वैल्यू-आधारित):

   • $\epsilon$-इष्टतम नीति खोजने के लिए $\tilde{O}(1/\epsilon^2)$ की नमूना जटिलता प्राप्त करता है।
   • यह बाउंड हिटिंग समय ($t_{hit}$), कवरिंग समय ($t_{cov}$), इष्टतम वैल्यू फंक्शन के स्पैन ($\|Q^*\|_{sp}$), और न्यूनतम स्टेशनरी वितरण प्रायिकता के व्युत्क्रम ($1/d_{min}^\pi$) पर निर्भर करता है।

2. SAVIC+ (मॉडल-मुक्त, कोई पूर्व ज्ञान नहीं):

   • संचारित MDPs के लिए, SAVIC+ $\tilde{O}(1/\epsilon^2)$ नमूना जटिलता प्राप्त करता है।
   • महत्वपूर्ण रूप से, इसे पैरामीटर सेट करने के लिए समस्या-निर्भर मात्राओं (जैसे $t_{cov}$ या $d_{min}$) के किसी भी पूर्व ज्ञान की आवश्यकता नहीं है।

3. SCPMA (नीति-आधारित):

   • $\tilde{O}(1/\epsilon^4)$ (स्थिर स्टेप साइज के साथ) या अनुकूलित स्टेप साइज़ के साथ बेहतर दर प्राप्त करता है।
   • यह कमजोर रूप से संचारित MDPs में एकल प्रक्षेपवपथ से पॉलिसी ग्रेडिएंट विधियों के लिए पहली परिमित नमूना जटिलता गारंटी का प्रतिनिधित्व करता है।

महत्व और दावे (Significance and Claims)

लेखक दावा करते हैं कि यह कार्य कमजोर रूप से संचारित सेटिंग में एकल प्रक्षेपवपथ से औसत-पुरस्कार MDPs में सीखने के लिए पहली परिमित नमूना जटिलता गारंटी प्रदान करता है।

• एर्गोडिसिटी धारणाओं को तोड़ना: पिछले कार्यों के विपरीत जिन्हें एर्गोडिसिटी (जहाँ सभी अवस्थाएँ आवर्ती हैं) की आवश्यकता थी, यह कार्य अधिक सामान्य कमजोर रूप से संचारित मामले को संभालता है जहाँ क्षणिक अवस्थाएँ मौजूद होती हैं।
• एकल प्रक्षेपवपथ यथार्थवाद: परिणाम जेनरेटिव मॉडल या i.i.d. डेटा जैसी अवास्तविक धारणाओं से आगे बढ़ते हैं, जो एक मानक ऑनलाइन लर्निंग सेटिंग प्रदान करते हैं जहाँ एक एजेंट क्रमिक रूप से वातावरण के साथ इंटरैक्ट करता है।
• मॉडल-मुक्त दक्षता: प्रस्तावित विधियाँ मॉडल-मुक्त हैं और SAVIC+ के मामले में, उन्हें MDP के मिक्सिंग गुणों या स्टेशनरी वितरण के पूर्व ज्ञान की आवश्यकता नहीं है, जिससे वे अज्ञात वातावरणों के लिए अधिक व्यावहारिक बन जाती हैं।
• सैद्धांतिक मशीनरी: शोध पत्र नवीन सैद्धांतिक उपकरणों को पेश करता है, जिसमें कमजोर रूप से संचारित MDPs में एकल प्रक्षेपवपथ से i.i.d. नमूने उत्पन्न करने के लिए स्टॉपिंग टाइम्स और स्ट्रॉन्ग मार्कोव प्रॉपर्टी का उपयोग शामिल है, जो उन्हें उन सांद्रता असमानताओं (concentration inequalities) को लागू करने में सक्षम बनाता है जो पहले केवल i.i.d. सेटिंग्स के लिए आरक्षित थे।

शोध पत्र यह नोट करते हुए समाप्त होता है कि जबकि वैल्यू-आधारित विधि पॉलिसी-आधारित विधि के $\tilde{O}(1/\epsilon^4)$ की तुलना में अधिक सटीक $\tilde{O}(1/\epsilon^2)$ बाउंड प्राप्त करती है, इस अंतर को पाटना और इन परिणामों को पैरामीटराइज्ड फंक्शन एप्रोक्सिमेशन सेटिंग्स तक विस्तारित करना भविष्य के खुले शोध विषय हैं।