📊 statistics

Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

यह शोध पत्र पॉइसन-इक्वेशन सुधारों (Poisson-equation corrections) को मोरो-एनवेलप स्मूथिंग (Moreau-envelope smoothing) के साथ संयोजित करने वाले एक नवीन लयाप्टोव ड्रिफ्ट निर्माण (Lyapunov drift construction) को पेश करते हुए, मार्कोवियन शोर (Markovian noise) के तहत संकुचित अपेक्षित अपडेट्स (contractive expected updates) वाले स्टोकेस्टिक एप्रोक्सिमेशन और सुदृढीकरण लर्निंग (reinforcement learning) एल्गोरिदम के लिए लगभग निश्चित अभिसरण दरों (almost sure convergence rates) को स्थापित करता है, जो पावर-लॉ लर्निंग रेट्स के लिए $o(n^{1-2\eta})$ और हार्मोनिक लर्निंग रेट्स के लिए $o(n^{-1})$ के अत्यंत निकट की दरें प्राप्त करता है।

मूल लेखक: Xinyu Liu, Zixuan Xie, Shangtong Zhang

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

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

CC BY 4.0

मूल लेखक: Xinyu Liu, Zixuan Xie, Shangtong Zhang

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

कल्पना कीजिए कि आप एक विशाल, धुंधले जंगल में कैंपफायर (आग) जलाने के लिए एकदम सही जगह खोजने की कोशिश कर रहे हैं। आप पूरे जंगल को एक साथ नहीं देख सकते; आप केवल अपने पैरों के नीचे की ज़मीन को जानते हैं। आपका हर कदम एक "लर्निंग रेट" (सीखने की दर) द्वारा निर्देशित होता है, जो इस बात की तरह है कि आप कितना बड़ा कदम उठाने का निर्णय लेते हैं। यदि आप बहुत बड़े कदम उठाते हैं, तो आप सटीक स्थान से आगे निकल सकते हैं। यदि कदम बहुत छोटे हैं, तो आप कभी भी उचित समय में वहां तक नहीं पहुँच पाएंगे।

यह शोध पत्र एक गणितीय पद्धति (जिसे स्टोकेस्टिक एप्रोक्सिमेशन कहा जाता है) के बारे में है जो एल्गोरिदम को समाधान के सर्वोत्तम पथ को खोजने में मदद करती है जब उन्हें मिलने वाली जानकारी शोर (noise) से भरी और अप्रत्याशित होती है।

यहाँ लेखकों द्वारा किए गए कार्यों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. समस्या: धुंधला जंगल और "मार्कोवियन" हवा

कई लर्निंग एल्गोरिदम में (जैसे वीडियो गेम AI या सेल्फ-ड्राइविंग कारों में उपयोग किए जाने वाले), डेटा व्यवस्थित या यादृच्छिक पैकेटों में नहीं आता है। इसके बजाय, यह एक श्रृंखला (chain) के रूप में आता है। यदि आप आज एक भालू देखते हैं, तो इस बात की संभावना अधिक है कि आप कल भी एक भालू देखेंगे, बजाय इसके कि आपने आज एक फूल देखा हो। इसे मार्कोवियन नॉइज़ (Markovian noise) कहा जाता है।

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

2. लक्ष्य: एक सटीक स्पीडोमीटर

लेखक एक ऐसा "स्पीडोमीटर" बनाना चाहते थे जो यह गारंटी दे सके कि एक विशिष्ट यात्री (एक विशिष्ट कंप्यूटर प्रोग्राम) कितनी तेज़ी से गंतव्य तक पहुँचेगा, भले ही हवा (शोर) एक जुड़ी हुई, श्रृंखला जैसी पैटर्न में चल रही हो। वे यह सिद्ध करना चाहते थे कि यात्री केवल अंततः वहां नहीं पहुँचता है, बल्कि वह एक विशिष्ट, अनुमानित गति से वहां पहुँचता है।

3. समाधान: "पॉइसन-मोरो ड्रिफ्ट" (Poisson-Moreau Drift)

इस समस्या को हल करने के लिए, लेखकों ने एक नया गणितीय उपकरण बनाया जिसे वे पॉइसन-मोरो ड्रिफ्ट कहते हैं। इसे एक विशेष जोड़ी हाइकिंग बूट्स और एक कंपास के संयोजन के रूप में समझें।

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

4. परिणाम: हम वहां कितनी तेज़ी से पहुँचते हैं?

इस नए उपकरण का उपयोग करके, लेखकों ने यात्रा की गति के बारे में दो मुख्य बातें सिद्ध कीं:

"पावर-लॉ" स्टेप्स के लिए (मध्यम आकार के कदम): यदि एल्गोरिदम ऐसे कदम उठाता है जो एक विशिष्ट दर से छोटे होते जाते हैं (जैसे $1/\sqrt{n}$ ), तो उन्होंने सिद्ध किया कि एल्गोरिदम सैद्धांतिक रूप से संभव अधिकतम गति के लगभग बराबर तेज़ गति से लक्ष्य के करीब पहुँचता है।
"हारमोनिक" स्टेप्स के लिए (परफेक्ट स्टेप साइज): यदि एल्गोरिदम $1/n$ की दर से सिकुड़ते हुए कदम लेता है (जैसे $1/1, 1/2, 1/3...$ ), तो उन्होंने सिद्ध किया कि एल्गोरिदम अविश्वसनीय रूप से तेज़ी से कन्वर्ज होता है। वास्तव में, यह प्रायिकता के नियमों द्वारा अनुमत सबसे अच्छी गति (एक प्रसिद्ध नियम जिसे "लॉ ऑफ इटरेटेड लॉगरिदम" कहा जाता है) के लगभग बराबर तेज़ है।

5. यह AI के लिए क्यों महत्वपूर्ण है?

लेखक विशेष रूप से उल्लेख करते हैं कि यह रीइन्फोर्समेंट लर्निंग (जहाँ AI प्रयास और त्रुटि के माध्यम से सीखता है, जैसे कि चलना सीखने वाला रोबोट या शतरंज खेलना सीखने वाला प्रोग्राम) पर लागू होता है।

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

सारांश

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

तकनीकी सारांश: पॉइसन-मोरो ड्रिफ्ट (Poisson-Moreau Drift) के माध्यम से स्टोकेस्टिक एप्रोक्सिमेशन और रिइन्फोर्समेंट लर्निंग की लगभग निश्चित अभिसरण दरें (Almost Sure Convergence Rates)

समस्या विवरण
यह शोध पत्र मार्कोवियन शोर (Markovian noise) के तहत कार्य करने वाले स्टोकेस्टिक एप्रोक्सिमेशन (SA) और रिइन्फोर्समेंट लर्निंग (RL) एल्गोरिदम के लिए लगभग निश्चित अभिसरण दरों (almost sure convergence rates) को स्थापित करने की मौलिक सैद्धांतिक चुनौती को संबोधित करता है। जबकि शास्त्रीय सिद्धांत (जैसे, ODE विधि) यह स्थापित करते हैं कि अनुक्रम $\{\theta_n\}$ लगभग निश्चित रूप से अभिसरित होते हैं, वे अक्सर व्यक्तिगत सैंपल पाथ (sample paths) के लिए इस अभिसरण की गति को मापने में विफल रहते हैं। लगभग निश्चित दरों से संबंधित मौजूदा साहित्य में महत्वपूर्ण सीमाएँ हैं:

कई परिणाम i.i.d. शोर पर निर्भर करते हैं, जो RL में सामान्य एकल-ट्रैजेक्टरी सैंपलिंग को प्रतिबिंबित नहीं करते हैं।
मार्कोवियन शोर को संभालने वाले परिणाम अक्सर यह मांग करते हैं कि अपेक्षित अपडेट रैखिक (linear) हो या वे प्रतिबंधात्मक लर्निंग रेट व्यवस्था (learning rate regimes) पर निर्भर करते हैं।
कियान एट अल. [2024] का हालिया कार्य सामान्य संकुचनकारी मैपिंग (contractive mappings) के साथ मार्कोवियन शोर को संभालता है, लेकिन यह धीमी अभिसरण दरें देता है और कुछ लर्निंग रेट व्यवस्थाओं (विशेष रूप से $\eta \in (1/2, 2/3]$ ) को कवर करने में विफल रहता है।

लेखक SA एल्गोरिदम के एक वर्ग पर ध्यान केंद्रित करते हैं जहाँ अपेक्षित अपडेट संकुचनकारी (contractive) होता है (संभावित रूप से गैर-यूक्लिडियन नॉर्म, जैसे $\ell_\infty$ में) और शोर एक मार्कोव श्रृंखला बनाता है। यह सेटिंग Q-लर्निंग और लीनियर टेम्पोरल डिफरेंस (TD) लर्निंग जैसे मुख्य RL एल्गोरिदम को समाहित करती है।

कार्यप्रणाली: पॉइसन-मोरो ड्रिफ्ट (The Poisson-Moreau Drift)
मुख्य तकनीकी नवीनता एक नया लयाप्टोव ड्रिफ्ट फंक्शन (Lyapunov drift function) है, जिसे पॉइसन-मोरो ड्रिफ्ट कहा गया है। लेखक दो स्थापित तकनीकों को एक नए सुधार तंत्र (correction mechanism) के साथ जोड़ते हैं:

मोरो-एनवेलप स्मूथिंग (Moreau-Envelope Smoothing): उस संकुचनकारी मैपिंग $T$ को संभालने के लिए जो गैर-यूक्लिडियन नॉर्म $\|\cdot\|$ के तहत परिभाषित हो सकती है, लेखक मोरो एनवेलप $M_\xi$ का उपयोग करते हैं। यह गैर-विभेदक (non-differentiable) नॉर्म-आधारित ऊर्जा फलन को एक निरंतरतः अवकलनीय (continuously differentiable) फलन $M_\xi(x)$ में सुचारू (smooth) बनाता है, जिससे संकुचन गुणों को संरक्षित करते हुए ग्रेडिएंट-आधारित विश्लेषण संभव हो पाता है।
पॉइसन-इक्वेशन सुधार (Poisson-Equation Correction): मार्कोवियन शोर को संबोधित करने के लिए, लेखक पॉइसन समीकरण के आधार पर एक सुधार लागू करते हैं। शोर पद $F(\theta, Y) - f(\theta)$ को पॉइसन समीकरण के एक समाधान $H_\theta$ का उपयोग करके एक मार्टिंगेल डिफरेंस और एक टेलिस्कोपिंग शेष भाग (telescoping remainder) में विभाजित किया जाता है: $H_\theta(y) - (PH_\theta)(y) = F(\theta, y) - f(\theta)$ ।
नवीन निर्माण: उन कार्यों के विपरीत जो या तो कुल अपेक्षा (total expectations) लेते हैं (जिससे पाथवाइज नियंत्रण खो जाता है) या "स्केलेटन इटरहेट्स" (subsequences) का उपयोग करते हैं, लेखक सीधे पॉइसन सुधार को लयाप्टोव फलन में शामिल करते हैं। वे ड्रिफ्ट को इस प्रकार परिभाषित करते हैं:
$V_n^\xi = M_\xi(e_n) + \alpha_n \langle \nabla M_\xi(e_n), H_{\theta_n}(Y_n) \rangle + K \alpha_n^2$
जहाँ $e_n = \theta_n - \theta^*$ $e_{n} = θ_{n} - θ^{*}$ त्रुटि (error) है, $\alpha_n$ $α_{n}$ लर्निंग रेट है, और $K$ $K$ एक पर्याप्त बड़ा स्थिरांक है।
- मध्य पद (पॉइसन सुधार) सशर्त ड्रिफ्ट (conditional drift) में मार्कोवियन निर्भरता से उत्पन्न होने वाले अग्रणी बायस पद को रद्द करता है।
- अंतिम पद ( $K \alpha_n^2$ ) यह सुनिश्चित करता है कि ड्रिफ्ट गैर-ऋणात्मक बना रहे और अवशेष पदों (residual terms) को नियंत्रित करे।

यह निर्माण लेखकों को यह स्थापित करने की अनुमति देता है कि $V_n^\xi$ सीधे सशर्त अपेक्षा पर एक लगभग-सुपरमार्टिंगेल (almost-supermartingale) असमानता को संतुष्ट करता है, जिससे पूरे इटरहेट्स के अनुक्रम पर (केवल सब-सीक्वेंस पर नहीं) हालिया लगभग-सुपरमार्टिंगेल अभिसरण दर सिद्धांतों (Liu और Yuan [2024]) को लागू करना संभव हो जाता है।

प्रमुख परिणाम
संकुचनकारी अपेक्षित अपडेट, लिप्सिट्ज़ निरंतरता (Lipschitz continuity), और मार्कोव श्रृंखला के लिए पॉइसन समीकरण समाधान के अस्तित्व की धारणाओं के तहत, यह शोध पत्र त्रुटि $\|\theta_n - \theta^*\|$ के लिए निम्नलिखित लगभग निश्चित अभिसरण दरें प्राप्त करता है:

पावर-लॉ लर्निंग रेट्स $\alpha_n = O(n^{-\eta})$ के साथ $\eta \in (1/2, 1)$ :
त्रुटि लगभग निश्चित रूप से $o(n^{-(2\eta - 1)})$ के करीब की दर से अभिसरित होती है।
हारमोनिक लर्निंग रेट्स $\alpha_n = O(n^{-1})$ $α_{n} = O (n^{- 1})$ (अर्थात $\eta = 1$ $η = 1$ ):
त्रुटि लगभग निश्चित रूप से $o(n^{-1})$ के करीब की दर से अभिसरित होती है।
- लेखक नोट करते हैं कि यह एक मजबूत परिणाम है, जो i.i.d. शोर के लिए लॉ ऑफ द इटरेटेड लॉगरिदम द्वारा दिए गए इष्टतम दर $O(n^{-1} \log \log n)$ के करीब पहुँचता है।

पूर्व कार्य के साथ तुलना

कियान एट अल. [2024] बनाम: प्रस्तावित विधि लर्निंग रेट की एक विस्तृत श्रृंखला को कवर करती है (विशेष रूप से $\eta \in (1/2, 2/3]$ जहाँ कियान एट अल. कोई दर प्रदान नहीं करते हैं) और $\eta \in (2/3, 1]$ के लिए स्पष्ट रूप से तेज़ अभिसरण दरें प्राप्त करती है।
अपेक्षा-आधारित विश्लेषण बनाम: यह पद्धति केवल अपेक्षा या प्रायिकता में अभिसरण के बजाय पाथवाइज (लगतः निश्चित) गारंटी प्रदान करती है।
साइड रिजल्ट: ड्रिफ्ट असमानता की अनकंडीशनल एक्सपेक्टेशन (unconditional expectations) लेकर, लेखक $\eta \in (0, 1]$ की पूरी रेंज के लिए $L_2$ अभिसरण दरें भी प्राप्त करते हैं, जो दिखाते हैं कि $E[\|\theta_n - \theta^*\|^2] = O(n^{-\eta})$ है जब $\eta < 1$ ।

अनुप्रयोग
इस सैद्धांतिक ढांचे को सामान्यीकृत महत्व सैंपलिंग कारकों (generalized importance sampling factors) वाले एक सामान्यीकृत टैबुलर TD एल्गोरिदम परिवार पर लागू किया जाता है। यह एकीकृत टेम्पलेट कई मानक एल्गोरिदम को पुनः प्राप्त करता है, जिनमें शामिल हैं:

ऑन-पॉलिसी और ऑफ-पॉलिसी $n$ -स्टेप TD।
$Q^\pi(\lambda)$ , Tree-Backup, Retrace, और Q-trace।

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

महत्व और दावे
यह शोध पत्र मार्कोवियन शोर और गैर-यूक्लिडियन संकुचनशीलता के तहत सामान्य स्टोकेस्टिक एप्रोक्सिमेशन के लिए तीक्ष्ण लगभग निश्चित अभिसरण दरें (sharper almost sure convergence rates) प्रदान करने का दावा करता है। इसका महत्व यहाँ है:

तकनीकी नवीनता: "पॉइसन-मोरो ड्रिफ्ट" को एक नवीन निर्माण के रूप में प्रस्तुत किया गया है जो सफलतापूर्वक गैर-यूक्लिडियन संकुचन (मोरो एनवेलप के माध्यम से) और मार्कोवियन शोर (पॉइसन सुधार के माध्यम से) को संभालने के बीच के अंतर को एक एकल लगभग-सुपरमार्टिंगेल ढांचे के भीतर पाटता है।
टाइटनेस (Tightness): हारमोनिक लर्निंग रेट्स ( $\eta=1$ ) के लिए प्राप्त दरें इष्टतम के करीब हैं, जो RL साहित्य में पिछले परिणामों से बेहतर हैं।
पूर्णता: यह कार्य मार्कोवियन शोर और सामान्य (गैर-रैखिक, गैर-यूक्लिडियन) संकुचनकारी मैपिंग के विशिष्ट संयोजन को संबोधित करके साहित्य के अंतराल को भरता है, जो आधुनिक RL एल्गोरिदम की विशेषता है।

लेखक दरों की तीक्ष्णता (tightness) के संबंध में विनम्र बने रहते हैं, यह स्वीकार करते हुए कि हालांकि उनके परिणाम मौजूदा साहित्य की तुलना में अधिक तीक्ष्ण हैं, वे अभी भी पूरी तरह से $O(n^{-1} \log \log n)$ बाउंड से मेल नहीं खाते हैं। वे यह भी नोट करते हैं कि $\eta \in (0, 1]$ की पूरी रेंज के लिए लगभग निश्चित दरों को विस्तारित करना (जो वर्तमान में $L_2$ के लिए सिद्ध है) एक खुला प्रश्न बना हुआ है।