Finite-Time Convergence of Distributionally Robust Q-Learning with Linear Function Approximation

तकनीकी सारांश: रैखिक फलन सन्निकटन के साथ वितरण रूप से सुदृढ़ (Distributionally Robust) Q-लर्निंग का परिमित-समय अभिसरण

समस्या विवरण
यह शोध पत्र एक चुनौती को संबोधित करता है: जब तैनाती का वातावरण प्रशिक्षण (नाममात्र) वातावरण से भिन्न होता है, तो वितरण रूप रूप से सुदृढ़ सुदृढीकरण शिक्षण (Distributionally Robust Reinforcement Learning - DRRL) में इष्टतम नीतियों को सीखना। विशेष रूप से, लेखक $(s, a)$-आयताकार (rectangular) ची-स्क्वायर अनिश्चितता सेट के तहत मॉडल-मुक्त, छूट प्राप्त (discounted) सुदृढ़ Q-लर्निंग पर ध्यान केंद्रित करते हैं।

इस सेटिंग में एक शिक्षार्थी एक अज्ञात नाममात्र संक्रमण कर्नेल (transition kernel) $P_0$ और एक व्यवहार नीति $\pi_b$ द्वारा उत्पन्न एकल मार्कोवियन प्रक्षेपवक्र (trajectory) पर कार्य करता है। शिक्षार्थी के पास जेनेरेटिव एक्सेस (किसी भी अवस्था-क्रिया युग्मों को नमूना लेने की क्षमता) नहीं है और वह $P_0$ को नहीं जानता है। लक्ष्य इष्टतम सुदृढ़ Q-फंक्शन $Q^\star_\chi$ को सीखना है, जो अनिश्चितता सेट के ऊपर सबसे खराब स्थिति वाले छूट प्राप्त मान (worst-case discounted value) को अधिकतम करता है।

यह समस्या दो जुड़ी हुई कठिनाइयों को प्रस्तुत करती है:

1. फलन सन्निकटन (Function Approximation) की कठिनाई: हालांकि सटीक सुदृढ़ बेलमैन ऑपरेटर $\ell_\infty$ में एक संकुचन (contraction) है, लेकिन रैखिक फलन सन्निकटन द्वारा प्रेरित प्रक्षेपित (projected) सुदृढ़ बेलमन ऑपरेटर सामान्य छूट कारक $\gamma \in (0, 1)$ के लिए संकुचन के रूप में ज्ञात नहीं है।
2. सुदृढ़ अनुमान (Robust Estimation) की कठिनाई: ची-स्क्वायर सुदृढ़ बेलमैन अपडेट में संक्रमण वितरणों पर आंतरिक न्यूनीकरण (inner minimization) शामिल है। इसका द्वैत ग्रेडिएंट (dual gradient) सशर्त क्षणों (conditional moments) (विशेष रूप से, बेलमैन गैप और उसके वर्ग के धनात्मक भाग) पर निर्भर करता है जिन्हें एक एकल प्रक्षेपवक्र से अनुमानित किया जाना चाहिए। मानक विश्लेषण या तो टैबुलर सुदृढ़ Q-लर्निंग या रैखिक Q-लर्निंग के लिए सीधे इस सेटिंग में विस्तारित नहीं होते हैं।

कार्यप्रणाली (Methodology)
लेखक एल्गोरिदम 1 का प्रस्ताव करते हैं, जो एक टार्गेट-नेटवर्क बाहरी लूप के साथ एक बहु-चरणीय स्टोकेस्टिक सन्निकटन एल्गोरिदम है। यह एल्गोरिदम टार्गेट Q-फंक्शन को फ्रीज करने वाले बाहरी ब्लॉक्स में कार्य करता है। प्रत्येक ब्लॉक के भीतर, तीन चरण होते हैं:

1. चरण 1: मोमेंट ट्रैकिंग के साथ द्वैत अनुकूलन (Dual Optimization with Moment Tracking)।
   एल्गोरिदम ची-स्क्वायर सुदृढ़ बेलमन अपडेट के आंतरिक न्यूनीकरण को इसके स्केलर द्वैत रूप के माध्यम से हल करता है। प्रत्येक अवस्था-क्रिया युग्म के लिए अलग से द्वैत समस्या को हल करने के बजाय, द्वैत चर $\eta$ को रैखिक रूप से अनुमानित किया जाता है ($\eta_\nu(i) = \psi(i)^\top \nu$)।

   • दो-समय-पैमाने वाली योजना (Two-Time-Scale Scheme): द्वैत चर $\nu$ को एक धीमी समय-सीमा पर अपडेट किया जाता है, जबकि दो "मोमेंट-ट्रैकिंग क्रिटिक्स" ($\omega_1, \omega_2$) एक तेज़ समय-सीमा पर आवश्यक सशर्त क्षणों ($Z_1$ और $Z_2$) का अनुमान लगाते हैं।
   • स्मूथिंग (Smoothing): ची-स्क्वायर द्वैत उद्देश्य में वैश्विक सुगमता (global smoothness) के अभाव को संभालने के लिए (जो मार्कोवियन शोर विश्लेषण के साथ समस्या उत्पन्न करता है), लेखक एक ट्यूनेबल पैरामीटर $\tau > 0$ का उपयोग करके एक स्मूथड सरोगेट ऑब्जेक्टिव को अनुकूलित करते हैं। यह सुनिश्चित करता है कि द्वैत ग्रेडिएंट लिप्सचिट्ज़ निरंतर (Lipschitz continuous) हो।
   • सफिक्स एवरेजिंग (Suffix Averaging): स्थिर अनुमान $\bar{\nu}_t$ प्राप्त करने के लिए द्वैत इटरेटों का सफिक्स-एवरेजिंग किया जाता है।

2. चरण 2: ताज़ा मूल्यांकन (Fresh Evaluation)।
   Q-फंक्शन को अपडेट करने से पहले, एल्गोरिदम औसत द्वैत पैरामीटर $\bar{\nu}_t$ का उपयोग करके विचरण जैसे क्षण ($Z_1$) का "ताज़ा मूल्यांकन" करता है। यह चरण क्षण के अनुमान को अनुकूलन प्रक्षेपवक्र से अलग करता है, जिससे उस पूर्वाग्रह (bias) को रोका जा जाता है जो तब होता यदि चरण 1 के क्रिटिक्स (जिन्हें $\nu$ के चलते समय सीखा गया था) का सीधे पुन: उपयोग किया जाता।

3. चरण 3: Q-अपडेट।
   एल्गोरिदम चरणों 1 और 2 से प्राप्त निश्चित, मूल्यांकित लक्ष्य के विरुद्ध सुदृढ़ Q-फंक्शन पैरामीटर $\theta$ के लिए एक धीमा टेम्पोरल डिफरेंस (TD) अपडेट करता है।

प्रमुख योगदान

1. परिमित-समय अभिसरण गारंटी: यह शोध पत्र एकल-प्रक्षेपवक्र डेटा से, बिना किसी छोटे-छूट-कारक प्रतिबंध के, रैखिक फलन सन्निकटन के साथ छूट प्राप्त मॉडल-मुक्त सुदृढ़ Q-लर्निंग के लिए पहली परिमित-समय अभिसरण सीमा प्रदान करता है।
2. टार्गेट-नेटवर्क विश्लेषण सुदृढ़ RL के लिए: लेखक टार्गेट-नेटवर्क तकनीक (जो गैर-सुदृढ़ डीप RL में सामान्य है) को सुदृढ़ सेटिंग में अनुकूलित करते हैं। ब्लॉक्स के भीतर टार्गेट Q-फंक्शन को फ्रीज करके, वे प्रक्षेपित सुदृढ़ बेलमान ऑपरेटर की गैर-संकुचनता (non-contractivity) को दरकिनार करते हैं, जिससे विश्लेषण को ब्लॉक्स के बीच अनप्रोजेक्टेड ऑपरेटर के संकुचन पर भरोसा करने की अनुमति मिलती है।
3. स्केलेबल द्वैत अनुमान: वे द्वैत चर को स्वयं एक रैखिक फलन वर्ग का उपयोग करके अनुमानित करने के लिए एक विधि पेश करते हैं, जो मोमेंट-ट्रैकिंग क्रिटिक्स के साथ जुड़ा हुआ है। यह बड़े अवस्था स्थानों के लिए स्वतंत्र द्वैत समस्याओं को हल करने की स्केलेबिलिटी समस्याओं से बचता है।
4. स्मूथिंग और बायस कंट्रोल: यह शोध पत्र ची-स्क्वायर द्वैत ऑब्जेक्टिव के लिए एक स्मूथड सरोगेट पेश करता है। यह लिप्सचिट्ज़ निरंतरता की समस्या को हल करता है जो सटीक ची-स्क्वायर फॉर्मूलेशन में निहित है, जिससे मार्कोवियन शोर के तहत कठोर परिमित-समय स्टोकेस्टिक सन्निकटन सीमाएं संभव होती हैं। लेखक स्पष्ट रूप से नोट करते हैं कि पिछले टैबुलर सुदृढ़ Q-लर्निंग के प्रमाण वैश्विक सुगमता धारणाओं पर निर्भर थे जो मान्य नहीं हैं; उनका प्रमाण इस कमी को सुधारता है।

परिणाम
मुख्य सैद्धांतिक परिणाम (थ्योरम 1) एक एंड-टू-एंड अभिसरण सीमा स्थापित करता है जिसका रूप है:
$$\mathbb{E}[\| \hat{Q}_T - Q^\star_\chi \|_\infty] \leq \gamma^T \| \hat{Q}_0 - Q^\star_\chi \|_\infty + \frac{E_{stat}(N, M, K, \tau) + E_{app}(\tau)}{1 - \gamma}$$
जहाँ:

• पहला पद टार्गेट-नेटवर्क संकुचन त्रुटि को दर्शाता है।
• $E_{stat}$ Q-अपडेट, द्वैत अनुकूलन, स्मूथिंग बायस और फ्रेश इवैल्यूएशन से होने वाली परिमित-नमूना त्रुटियों को कैप्चर करता है।
• $E_{app}$ फलन सन्निकटन और स्मूथिंग के कारण होने वाली सन्निकटन त्रुटियों को कैप्चर करता है।

कोरोलरी 2 सैंपल कॉम्प्लेक्सिटी (नमूना जटिलता) को व्युत्पन्न करती है, जो दिखाती है कि $\epsilon$ त्रुटि प्राप्त करने के लिए, कुल प्रक्षेपवक्र लंबाई $\tilde{O}(\epsilon^{-5/(1-a)})$ (जहाँ $a$ एक स्टेप-साइज़ पैरामीटर है) के क्रम में स्केल करती है, लॉगरिदमिक कारकों तक।

FrozenLake MDP पर प्रयोग सिद्धांत को मान्य करते हैं, जो सुदृढ़ संदर्भ मान की ओर अभिसरण को प्रदर्शित करते हैं और स्मूथिंग पैरामीटर $\tau$ द्वारा उत्पन्न ट्रेड-ऑफ को दर्शाते हैं (छोटा $\tau$ बायस को कम करता है लेकिन वेरिएंस/ऑप्टिमाइजेशन एरर को बढ़ाता है)।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह उन गैप को भरता है जो सुदृढ़ RL एल्गोरिदम की अनुभवजन्य सफलता और उनके गैर-सुदृढ़ समकक्षों के लिए उपलब्ध सैद्धांतिक गारंटी के बीच मौजूद है। पूर्ववर्ती कार्य या तो टैबुलर सेटिंग्स तक सीमित थे, या उनमें जेनेरेटिव एक्सेस की आवश्यकता थी, या उन्होंने सक्रिय अन्वेषण (active exploration) की धारणा ली थी, या वे छूट कारक पर प्रतिबंधात्मक शर्तें थोपते थे।

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