📊 statistics

Achieving $\epsilon^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

यह शोध पत्र एक नवीन युग्मित लियापुनोव ड्रिफ्ट (coupled Lyapunov drift) ढांचे को पेश करके, न्यूनतम धारणाओं के तहत सिंगल-लूप, ऑफ-पॉलिसी एक्टर-क्रिटिक विधियों में $\epsilon$ -इष्टतम नीति खोजने के लिए पहला $\tilde{\mathcal{O}}(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी गारंटी स्थापित करता है, जो युग्मित अपडेट और अनबाउंडेड इटरेट्स की चुनौतियों पर विजय प्राप्त करता है।

मूल लेखक: Ishaq Hamza, Zaiwei Chen

प्रकाशित 2026-05-14

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Ishaq Hamza, Zaiwei Chen

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक रोबोट को खजाना खोजने के लिए एक भूलभुलैया (maze) में रास्ता तय करना सिखाने की कोशिश कर रहे हैं। रोबोट के पास दो दिमाग हैं जो मिलकर काम करते हैं:

द क्रिटिक (The Critic - निर्णायक): यह दिमाग वर्तमान स्थिति को देखता है और कहता है, "यह चाल कितनी अच्छी है? क्या यह खजाने की ओर ले जा रही है या किसी बंद रास्ते की ओर?" यह हर संभावित चाल के मूल्य (value) का अनुमान लगाने की कोशिश करता है।
द एक्टर (The Actor - करने वाला): यह दिमाग क्रिटिक की बात सुनता है और निर्णय लेता है, "ठीक है, मैं उन चालों को आज़माऊँगा जिन्हें क्रिटिक अच्छा समझता है।" यह अपनी रणनीति को बेहतर बनाने के लिए अपडेट करता है।

रीइन्फोर्समेंट लर्निंग (RL) की दुनिया में, ये दोनों दिमाग आमतौर पर एक-दूसरे से बात करके सीखते हैं। मुख्य सवाल जिसका यह पेपर उत्तर देता है, वह है: वे कितनी तेज़ी से सीख सकते हैं, और उन्हें वास्तव में कुशल होने के लिए कितने डेटा की आवश्यकता है?

पुराना तरीका: "इंतज़ार करो और देखो" दृष्टिकोण (The "Wait-and-See" Approach)

लंबे समय तक, यह साबित करने का सबसे विश्वसनीय तरीका कि ये रोबोट तेज़ी से सीख सकते हैं (विशेष रूप से, उस समय सीमा में जिसमें वे आपकी सटीकता के स्तर के साथ तालमेल बिठा सकें), एक नेस्टेड-लूप (Nested-Loop) विधि का उपयोग करना था।

इसे एक सख्त शिक्षक और छात्र के रूप में सोचें:

क्रिटिक (शिक्षक) छात्र के होमवर्क को ग्रेड करने में बहुत अधिक समय बिताता है, यह सुनिश्चित करने के लिए कि ग्रेड एकदम सटीक हो।
केवल तभी जब ग्रेड एकदम सही हो जाए, एक्टर (छात्र) को अपनी रणनीति बदलने की अनुमति दी जाती है।
फिर क्रिटिक फिर से ग्रेड देता है, और एक्टर फिर से बदलता है।

यह काम तो करता है, लेकिन यह धीमा और बोझिल है। यह वैसा ही है जैसे एक शिक्षक कक्षा को हर 5 मिनट में पिछले 5 मिनट के काम को फिर से ग्रेड करने के लिए रोक दे, इससे पहले कि कक्षा आगे बढ़ सके।

नया तरीका: "सिंगल-लूप" नृत्य (The "Single-Loop" Dance)

वास्तविक दुनिया में, रोबॉट्स के पास सब कुछ फिर से ग्रेड करने के लिए रुकने की विलासिता नहीं होती है। वे आमतौर पर एक सिंगल-लूप (Single-Loop) सिस्टम में चलते हैं।

क्रिटिक एक त्वरित, मोटा-मोटा ग्रेड देता है।
एक्टर तुरंत उस मोटे-मोटे ग्रेड के आधार पर अपनी रणनीति में थोड़ा बदलाव करता है।
वे दोनों एक साथ आगे बढ़ते हैं, वास्तविक समय (real-time) में लगातार अपडेट होते रहते हैं।

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

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

इस पेपर की बड़ी सफलता

यह पेपर कहता है: "हम यह साबित कर सकते हैं कि सिंगल-लूप नृत्य उतना ही तेज़ काम करता है जितना कि धीमा नेस्टेड-लूप तरीका, लेकिन हमें उन अजीब धारणाओं की आवश्यकता नहीं है।"

यहाँ उन्होंने क्या हासिल किया, सरल शब्दों में:

1. "न्यूनतम" धारणा (The "Minimal" Assumption)
रोबोट को सब कुछ पूरी तरह से एक्सप्लोर करने की मांग करने के बजाय, लेखकों ने केवल यह माना कि कम से कम एक ऐसा रास्ता मौजूद है जो अंततः हर एक स्थान पर पहुँचता है।

उपमा: आपको रोबोट को एक आदर्श खोजकर्ता (explorer) बनाने की आवश्यकता नहीं है। आपको बस यह जानने की आवश्यकता है कि यदि वह एक विशिष्ट पथ का पालन करता है, तो वह किसी कोने में हमेशा के लिए नहीं फँसेगा। बस इतना ही। यह एक बहुत ही कमजोर, "न्यूनतम" धारणा है।

2. "कप्ल्ड ल्यपुनोव ड्रिफ्ट" फ्रेमवर्क (The "Coupled Lyapunov Drift" Framework - सुरक्षा जाल)
उन्होंने इसे कैसे साबित किया? उन्होंने एक नया गणितीय सुरक्षा जाल बनाया जिसे कप्ल्ड ल्यपुनोव ड्रिफ्ट फ्रेमवर्क कहा जाता है।

उपमा: कल्पना करें कि एक्टर और क्रिटिक एक रस्सी पकड़कर एक साथ फिसलन भरी पहाड़ी पर चढ़ रहे हैं।
- एक्टर ऊपर चढ़ने (रणनीति सुधारने) की कोशिश कर रहा है।
- क्रिटिक ऊंचाई मापने (मूल्य का अनुमान लगाने) की कोशिश कर रहा है।
- क्योंकि ज़मीन फिसलन भरी है (शोर भरा डेटा) और वे एक ही रस्सी को खींच रहे हैं (कप्ल्ड अपडेट्स), वे फिसल सकते हैं।
- लेखकों ने एक नया "रस्सी के तनाव" (rope tension) का विश्लेषण बनाया। उन्होंने दिखाया कि भले ही एक पर्वतारोही थोड़ा फिसले, दूसरे पर्वतारोही की प्रगति उन्हें वापस ऊपर खींच लेती है। उन्होंने साबित किया कि एक का "फिसलना" हमेशा दूसरे के "खींचने" से कम होता है। यह सुनिश्चित करता है कि वे दोनों बिना गिरे पहाड़ पर ऊपर की ओर बढ़ते रहें।

3. परिणाम: बिना "परफेक्ट एक्सप्लोरर" की आवश्यकता के गति
उन्होंने सिद्ध किया कि यह सिंगल-लूप विधि लगभग $1/\epsilon^2$ स्टेप्स में (जहाँ $\epsilon$ वह निकटता है जो आप पूर्णता के करीब चाहते हैं) एक आदर्श रणनीति खोज लेती है।

यह "गोल्ड स्टैंडर्ड" गति है।
महत्वपूर्ण रूप से, उन्होंने यह बिना नेस्टेड लूप के और बिना यह माने कि रोबोट पूरी दुनिया का पूरी तरह से अन्वेषण करता है, हासिल किया। उन्हें केवल "न्यूनतम" धारणा की आवश्यकता थी कि एक पथ मौजूद है।

यह क्यों मायने रखता है (पेपर के अनुसार)

पेपर का तर्क है कि लंबे समय से, "पॉलिसी-स्पेस" विधियों (जैसे एक्टर-क्रिटिक) को "वैल्यू-स्पेस" विधियों (जैसे Q-learning) के "धीमे, उलझे हुए" चचेरे भाइयों के रूप में माना जाता रहा है। लोगों को लगा कि एक्टर-क्रिटिक को काम करने के लिए कड़े नियमों की आवश्यकता है।

यह पेपर इस धारणा को उलट देता है। यह दिखाता है कि एक्टर-क्रिटिक उतना ही कुशल है जितना कि अन्य सर्वोत्तम विधियाँ, बशर्ते आप "उलझे हुए" सिंगल-लूप अपडेट का विश्लेषण करने के लिए सही गणितीय उपकरणों का उपयोग करें। उन्होंने केवल गणित को ठीक नहीं किया; उन्होंने इन एल्गोरिदम के वास्तविक कार्य के अनुरूप बनाने के लिए अवास्तविक "परफेक्ट एक्सप्लोरेशन" धारणाओं को हटा दिया।

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

तकनीकी सारांश: न्यूनतम धारणाओं के तहत सिंगल-लूप एक्टर-क्रिटिक के लिए $\tilde{O}(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी प्राप्त करना

समस्या विवरण
रीइन्फोर्समेंट लर्निंग (RL) डेटा-संचालित विधियों के माध्यम से मार्कोव डिसीजन प्रोसेस (MDPs) को हल करने का लक्ष्य रखती है। जबकि वैल्यू-स्पेस विधियों जैसे Q-लर्निंग ने न्यूनतम धारणाओं (विशेष रूप से, एक अपरिवर्तनीय व्यवहार नीति के अस्तित्व) के तहत $\tilde{O}(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी स्थापित की है, पॉलिसी-स्पेस विधियों जैसे एक्टर-क्रिटिक ऐतिहासिक रूप से सैद्धांतिक गारंटी में पीछे रहे हैं। $\tilde{O}(\epsilon^{-2})$ जटिलता प्राप्त करने वाले मौजूदा एक्टर-क्रिटिक विश्लेषण आमतौर पर दो प्रतिबंधात्मक शर्तों पर निर्भर करते हैं:

नेस्टेड-लूप कार्यान्वयन: जहाँ क्रिटिक कई बार अपडेट होता है जबकि एक्टर स्थिर रहता है, जो व्यावहारिक सिंगल-लूप एल्गोरिदम से भिन्न संरचना है।
मजबूत, एल्गोरिदम-निर्भर धारणाएँ: जैसे कि यह आवश्यकता कि एल्गोरिदम के प्रक्षेपवक्र (trajectory) के दौरान सामना की जाने वाली सभी नीतियाँ (या संपूर्ण पॉलिसी क्लास) अपरिवर्तनीय और एपीरियॉडिक मार्कोव चेन को प्रेरित करती हों, जिनमें समान रूप से बाध्य (bounded) मिक्सिंग दरें और अन्वेषण गुण हों।

ये धारणाएँ एक चक्रीय निर्भरता (circular dependency) पैदा करती हैं: मिक्सिंग गुणों को सत्यापित करने के लिए नीति अनुक्रम (policy sequence) को नियंत्रित करने की आवश्यकता होती है, जो कि स्वयं अभिसरण विश्लेषण (convergence analysis) का विषय है। इसके अतिरिक्त, व्यावहारिक एक्टर-क्रिटिक एल्गोरिदम एक सिंगल-लूप, सिंगल-टाइम्स्केल तरीके से ऑफ-पॉलिसी लर्निंग संचालित करते हैं, जहाँ क्रिटिक एक समय-परिवर्तित टारगेट पॉलिसी को ट्रैक करता है। यह युग्मित अपडेट समीकरणों (coupled update equations) और इम्पोर्टेंस सैंपलिंग के कारण संभावित रूप से अनबाउंडेड इटरेट्स (unbounded iterates) की चुनौतियों को पेश करता है, जिन्हें मौजूदा सैद्धांतिक ढांचे बिना मजबूत धारणाओं के संबोधित करने में संघर्ष करते हैं।

कार्यप्रणाली (Methodology)
लेखक एक सिंगल-लूप, सिंगल-टाइम्स्केल ऑफ-पॉलिसी एक्टर-क्रिटिक एल्गोरिदम प्रस्तावित करते हैं जहाँ प्रत्येक पुनरावृत्ति (iteration) में एक्टर और क्रिटिक को एक साथ अपडेट किया जाता है। एक्टर एक टारगेट पॉलिसी $\tilde{\pi}_t$ की ओर वृद्धिशील (incremental) अपडेट का उपयोग करता है जो एप्रोक्सीमेट पॉलिसी इटरेशन (API) या नेचुरल पॉलिसी ग्रेडिएंट (NPG) के माध्यम से प्राप्त की जाती है, जबकि क्रिटिक ऑफ-पॉलिसी टेम्पोरल-डिफरेंस (TD) लर्निंग करता है। लेखक दो क्रिटिक वेरिएंट्स पर विचार करते हैं:

इम्पोर्टेंस सैंपलिंग (IS): वितरण बेमेल (distribution mismatch) को ठीक करने के लिए इम्पोर्टेंस वेट रेश्यो का उपयोग करता है।
एक्स्पेक्टेड टेम्पोरल डिफरेंस (ETD): अगले स्टेट पर अपेक्षित Q-फंक्शन की सीधे गणना करता है, जिससे स्पष्ट इम्पोर्टेंस वेट्स से बचा जा सकता है।

मुख्य तकनीकी नवाचार विश्लेषण ढांचे में निहित है। एक्टर और क्रिटिक अपडेट के बीच कपलिंग को संभालने और ऑफ-पॉलिसी इटरेट्स की अनबाउंडेड प्रकृति को प्रबंधित करने के लिए, लेखक एक कपल्ड लयापुनोव ड्रिफ्ट फ्रेमवर्क (coupled Lyapunov drift framework) का उपयोग करते हैं।

लयापुनोव फंक्शन्स: वे एक्टर के लिए अलग-अलग लयापुनोव फंक्शन ( $V_t = \|Q^* - Q_{\pi_t}\|_\infty^2$ ) और क्रिटिक के लिए ( $W_t = \|Q_t - Q_{\pi_t}\|_\nu^2$ ) निर्मित करते हैं।
ड्रिफ्ट इनइक्वेलिटीज: वे दोनों फंक्शन्स के लिए नेगेटिव ड्रिफ्ट इनइक्वेलिटीज स्थापित करते हैं। महत्वपूर्ण रूप से, इन इनइक्वेलिटीज में क्रॉस-टर्म्स शामिल हैं जो युग्मित प्रणाली (coupled system) से त्रुटि का प्रतिनिधित्व करते हैं (जैसे, क्रिटिक एरर का एक्टर के ड्रिफ्ट में और इसके विपरीत प्रभाव)।
क्रॉस-डोमिनेशन: विश्लेषण "क्रॉस-डोमिनेशन" संपत्ति पर निर्भर करता है। स्टेपसाइज़ रेश्यो को सावधानीपूर्वक चुनकर और यह सुनिश्चित करके कि कपलिंग एरर टर्म्स संबंधित प्रणालियों के नेगेटिव ड्रिफ्ट टर्म्स द्वारा डोमिनेट किए जाते हैं, लेखक इन दोनों ड्रिफ्ट इनइक्वेलिटीज को $V_t + W_t$ के लिए एक एकल पुनरावृत्ति (recursion) में संयोजित करते हैं। यह दृष्टिकोण डायनेमिकल सिस्टम्स में स्मॉल-गेन थ्योरी (small-gain theory) से प्रेरित है, लेकिन इसे यहाँ मार्कोवियन नॉइज़, समय-परिवर्तित लक्ष्यों और अनबाउंडेड इटरेट्स को एक एकीकृत रूप में संभालने के लिए अनुकूलित किया गया है।

प्रमुख योगदान और परिणाम
यह पेपर एक सिंगल-लूप एक्टर-क्रिटिक एल्गोरिदम के लिए पहले लास्ट-इटरेट कन्वर्जेंस (last-iterate convergence) दरों को स्थापित करता है जो न्यूनतम धारणाओं के तहत $\tilde{O}(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी प्राप्त करता है।

न्यूनतम धारणाएँ: एकमात्र आवश्यक धारणा स्टेट स्पेस पर एक अपरिवर्तनीय मार्कोव चेन को प्रेरित करने वाली एक नीति का अस्तित्व है। इस नीति का एल्गोरिदम द्वारा विज़िट किया जाना आवश्यक नहीं है, और न ही एल्गोरिदम को अपनी उत्पन्न की गई नीतियों के मिक्सिंग गुणों को नियंत्रित करने की आवश्यकता है। यह पूर्व कार्यों के विपरीत है जो पूरे प्रक्षेपवक्र या संपूर्ण पॉलिसी क्लास के लिए यूनिफॉर्म एर्गोडिसिटी की आवश्यकता रखते हैं।
सैंपल कॉम्प्लेक्सिटी: इस न्यूनतम धारणा के तहत, एल्गोरिदम एक $\epsilon$ -ऑप्टिमल पॉलिसी खोजने के लिए $\tilde{O}(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी प्राप्त करता है। यह दर $\epsilon$ के संबंध में नियर-मिनिमैक्स ऑप्टिमल है।
स्टेपसाइज़ स्कीम्स: परिणाम कांस्टेंट, हार्मोनिक और पॉलिनॉमियल स्टेपसाइज़ सीक्वेंस के लिए मान्य हैं। विशेष रूप से, उपयुक्त पैरामीटर्स के साथ हार्मोनिक स्टेपसाइज़ का उपयोग करने से इष्टतम दर प्राप्त होती है।
एल्गोरिदम वेरिएंट्स: विश्लेषण IS-आधारित और ETD-आधारित क्रिटिक्स को कवर करता है। हालांकि दोनों समान कॉम्प्लेक्सिटी ऑर्डर प्राप्त करते हैं, ETD वेरिएंट समस्या के मापदंडों ( $n, m, (1-\gamma)^{-1}$ ) पर हल्का निर्भरता प्रदर्शित करता है क्योंकि यह इम्पोर्टेंस सैंपलिंग रेश्यो द्वारा उत्पन्न अतिरिक्त स्टोकेस्टिसिटी से बचता है।
अनबाउंडेड इटरेट्स: फ्रेमवर्क ऑफ-पॉलिसी लर्निंग (विशेष रूप से IS के साथ) द्वारा प्रेरित संभावित रूप से अनबाउंडेड इटरेट्स को सफलतापूर्वक संभालता है, जो एक ऐसी चुनौती है जिसके लिए अक्सर पिछले साहित्य में मजबूत बाउंडेडनेस धारणाओं की आवश्यकता होती है।

महत्व और दावे
लेखकों का दावा है कि यह कार्य वैल्यू-स्पेस और पॉलिसी-स्पेस विधियों के बीच एक महत्वपूर्ण सैद्धांतिक अंतर को पाटता है। यह प्रदर्शित करके कि एक्टर-क्रिटिक विधियाँ नेस्टेड लूप या मजबूत, एल्गोरिदम-निर्भर मिक्सिंग धारणाओं के बिना मिनिमैक्स-ऑप्टिमल सैंपल कॉम्प्लेक्सिटी प्राप्त कर सकती हैं, यह पेपर इस धारणा को चुनौती देता है कि पॉलिसी-स्पेस विधियाँ स्वाभाविक रूप से कम सैंपल-एफिशिएंट हैं या उन्हें अधिक मजबूत शर्तों की आवश्यकता होती है।

कपल्ड लयापुनोव ड्रिफ्ट और क्रॉस-डोमिनेशन पर आधारित विश्लेषणात्मक ढांचा स्वतंत्र रुचि के योगदान के रूप में प्रस्तुत किया गया है, जो अनबाउंडेड इटरेट्स वाले अन्य कपल्ड इटरेटिव एल्गोरिदम पर भी लागू हो सकता है। पेपर स्पष्ट रूप से नोट करता है कि जबकि $\epsilon$ के संबंध में निर्भरता नियर-ऑप्टिमल है, समस्या-विशिष्ट स्थिरांकों ( $n, m, (1-\gamma)^{-1}$ ) के संबंध में निर्भरता वैल्यू-बेस्ड विधियों की तुलना में सब-ऑप्टिमल हो सकती है, जो यह सुझाव देती है कि वेरिएंस रिडक्शन तकनीकें भविष्य के सुधार के लिए एक दिशा हो सकती हैं। यह कार्य फंक्शन एप्रोक्सिमेशन सेटिंग्स ("डेडली ट्रायड") या विशिष्ट एम्पिरिकल एप्लिकेशन्स के बारे में दावे करने के बजाय, पूरी तरह से टैबुलर सेटिंग और सैद्धांतिक गारंटियों पर ध्यान केंद्रित करता है।

पुराना तरीका: "इंतज़ार करो और देखो" दृष्टिकोण (The "Wait-and-See" Approach)

नया तरीका: "सिंगल-लूप" नृत्य (The "Single-Loop" Dance)

इस पेपर की बड़ी सफलता

यह क्यों मायने रखता है (पेपर के अनुसार)

इसी तरह के और पेपर