📊 statistics

A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation

यह शोध पत्र यह सिद्ध करके एक खुली समस्या का समाधान करता है कि अनप्रोजेक्टेड (unprojected) TD(0) लर्निंग, जो लीनियर फंक्शन एप्रोक्सिमेशन का उपयोग करती है, बिना बाउंडेड इट्रेट्स (bounded iterates) या अतिरिक्त रेगुलैरिटी कंडीशंस की आवश्यकता के, अपडेट्स के एक नवीन सेल्फ-बाउंडिंग प्रॉपर्टी पर भरोसा करते हुए, मार्कोवियन नॉइज़ के तहत एक रोबस्ट $\widetilde{\mathcal{O}}(1/\sqrt{T})$ कन्वर्जेंस रेट प्राप्त करती है।

मूल लेखक: Wei-Cheng Lee, Francesco Orabona

प्रकाशित 2026-06-09

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

CC BY 4.0

मूल लेखक: Wei-Cheng Lee, Francesco Orabona

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

मुख्य चित्र: बिना सुरक्षा जाल के सीखना

कल्पना कीजिए कि आप प्रयास और त्रुटि (trial and error) के माध्यम से एक नया कौशल सीखने की कोशिश कर रहे हैं, जैसे कोई वीडियो गेम खेलना या भूलभुलैया (maze) से बाहर निकलना। आर्टिफिशियल इंटेलिजेंस की दुनिया में, इसे रीइन्फोर्समेंट लर्निंग (Reinforcement Learning) कहा जाता है। इसके लिए सबसे लोकप्रिय उपकरणों में से एक टीडी लर्निंग (TD Learning) है।

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

लंबे समय से, गणितज्ञों को पता था कि यह छात्र अंततः खेल को पूरी तरह से सीख सकता है। हालाँकि, इसे सिद्ध करने के लिए उपयोग किए जाने वाले गणित में एक बड़ी समस्या थी:

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

यह पेपर कहता है: "हाँ, हम कर सकते हैं।"

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

मुख्य अवधारणाओं की व्याख्या

1. "सुरक्षा जाल" (प्रोजेक्शन/Projection)

पुराने गणित में, एल्गोरिदम को फटने से बचाने के लिए, शोधकर्ताओं को यह मानकर चलना पड़ता था कि वे संख्याओं को भौतिक रूप से काट (clip) रहे हैं यदि वे बहुत बड़ी हो जाती हैं।

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

2. "वक्रता" (Curvature) का जाल

कुछ अन्य विधियों ने सुरक्षा जाल से बचने के लिए यह मान लिया कि जिस घाटी में वे चल रहे हैं वह बहुत खड़ी और कटोरे के आकार की (गणितीय रूप से "स्ट्रॉन्गली कॉनवेक्स") है।

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

3. "सेल्फ-बाउंडिंग" (Self-Bounding) का जादू

उन्होंने बिना किसी बाड़ के यह कैसे सिद्ध किया कि नंबर नहीं बढ़ रहे हैं? उन्होंने सीखने की प्रक्रिया के एक छिपे हुए गुण की खोज की जिसे सेल्फ-बाउंडिंग कहा जाता है।

उपमा: एक रबर बैंड की कल्पना करें। यदि आप छात्र के नोट्स को सच्चाई से बहुत दूर खींचते हैं, तो "सीखने की शक्ति" स्वाभाविक रूप से उन्हें वापस खींच लेती है। यह ऐसा है जैसे एल्गोरिदम के पास एक आंतरिक दिशा-सूचक यंत्र (compass) है जो उसे रास्ता भटकने से रोकता है, बशर्ते आप उसे सही मात्रा में "धक्का" (लर्निंग रेट) दें।
ट्रिक: लेखकों ने पाया कि यदि वे थोड़ा सा लॉगरिदमिक सुधार (एक बहुत छोटा गणितीय बदलाव) जोड़कर "धक्के" (लर्निंग रेट) को थोड़ा समायोजित करते हैं, तो एल्गोरिदम स्वाभाविक रूप से खुद को नियंत्रण में रखता है।

4. "शोर युक्त" (Noisy) डेटा

वास्तविक जीवन में, डेटा यादृच्छिक (random) नहीं होता; यह आपस में जुड़ा होता है। यदि आप आज एक शेर देखते हैं, तो इसकी संभावना अधिक है कि आप कल भी एक शेर देखेंगे। इसे मार्कोवियन नॉइज़ (Markovian noise) कहा जाता है।

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

उन्होंने वास्तव में क्या किया?

बाड़ हटा दी: उन्होंने एल्गोरिदम के "अनप्रोजेक्टेड" (Unprojected) संस्करण का विश्लेषण किया (वह संस्करण जिसमें सुरक्षा जाल नहीं है)।
गति का पता लगाया: उन्होंने सिद्ध किया कि यह लगभग 1 ऊपर वर्ग मूल के ( $1/\sqrt{T}$ $1/ T$ ) की दर से अभिसरण (सीखना) करता है।
- नोट: यह "खड़ी कटोरी" वाले अनुमान पर निर्भर करने वाली "तेज" विधियों की तुलना में थोड़ा धीमा है, लेकिन यह बहुत अधिक विश्वसनीय है क्योंकि यह तब भी काम करता है जब कटोरी समतल हो।
कोई अतिरिक्त नियम नहीं: उन्हें किसी भी अतिरिक्त "रेगुलैरिटी कंडीशंस" (डेटा के बारे में अतिरिक्त सख्त नियम) की आवश्यकता नहीं थी।
लर्निंग रेट: उन्होंने दिखाया कि लर्निंग रेट फॉर्मूला में थोड़ा सा बदलाव करके (एक छोटा सा लॉग फैक्टर जोड़कर) एल्गोरिदम को स्थिर रहने की गारंटी देने के लिए पर्याप्त है।

एक वाक्य में सारांश

यह पेपर एक लंबे समय से चले आ रहे पहेली को हल करता है, यह सिद्ध करके कि एक लोकप्रिय AI लर्निंग मेथड बिना किसी कृत्रिम सुरक्षा जाल या डेटा के किसी पूर्ण आकार की धारणा के, केवल सीखने की गति में थोड़ा सा बदलाव करके, अपने आप स्थिर रहता है और प्रभावी ढंग से सीखता है।

तकनीकी सारांश: अनप्रोजेक्टेड (Unprojected) TD लर्निंग के लिए एक सुदृढ़ $O(1/\sqrt{T})$ दर

समस्या विवरण

रैखिक फलन सन्निकटन (Linear Function Approximation) के साथ टेम्पोरल डिफरेंस (TD) लर्निंग, पॉलिसी इवैल्यूएशन के लिए एक मौलिक एल्गोरिदम है। जबकि एसिम्प्टोटिक अभिसरण (Asymptotic Convergence) अच्छी तरह से समझा गया है, यथार्थवादी स्थितियों के तहत—विशेष रूप से जब डेटा एक मार्कोव चेन (मार्कोवियन शोर) द्वारा उत्पन्न किया जाता है न कि स्वतंत्र नमूनों द्वारा—फाइनाइट-टाइम अभिसरण दरों को स्थापित करना चुनौतीपूर्ण बना हुआ है।

एक महत्वपूर्ण सैद्धांतिक अंतराल मौजूद है। पूर्व कार्य (जैसे, भंडारी एट अल., 2018) जो इस दर को स्थापित करते हैं, वे एक कृत्रिम प्रोजेक्शन स्टेप पर निर्भर थे, जहाँ इटरेट्स (Iterates) को विचलन को रोकने के लिए एक सीमित सेट पर मजबूर किया जाता है। यह प्रक्रिया व्यवहार में शायद ही कभी उपयोग की जाती है और इसके लिए $\theta^*$ के एक बाउंड के ज्ञान की आवश्यकता होती है, जो अक्सर उपलब्ध नहीं होता है। इसके विपरीत, अनप्रोजेक्टेड TD लर्निंग के लिए "फास्ट" अभिसरण दरें $O(1/T)$ मौजूद हैं, लेकिन वे पोटेंशियल फंक्शन के न्यूनतम वक्रता ( $\omega$ ) के व्युत्क्रम वर्ग पर निर्भर करती हैं। चूंकि $\omega$ मनमाने ढंग से छोटा हो सकता है (इल-कंडीशन्ड समस्याएं), इसलिए फास्ट रेट नॉन-एसिम्प्टोटिक व्यवस्थाओं में काफी खराब हो सकता है।

बंडारी एट अल. (2018) द्वारा प्रस्तुत खुला प्रश्न यह है कि क्या अतिरिक्त रेगुलैरिटी कंडीशंस या कृत्रिम प्रोजेक्शन के बिना अनप्रोजेक्टेड TD(0) $O(1/\sqrt{T})$ की सुदृढ़ दर प्राप्त कर सकता है।

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

लेखक मार्कोवियन सैंपलिंग के तहत रैखिक फलन सन्निकटन के साथ मानक अनप्रोजेक्टेड TD(0) एल्गोरिदम का विश्लेषण करते हैं। उनका दृष्टिकोण उन पूर्व विश्लेषणों से मौलिक रूप से भिन्न है जो कंट्रैक्शन गुणों या कृत्रिम प्रोजेक्शन पर निर्भर करते हैं।

1. पोटेंशियल फंक्शन का चयन

मानक $D$ -नॉर्म दूरी $\|V_{\bar{\theta}_T} - V_{\theta^*}\|_D^2$ के बजाय, लेखक लियू और ओल्शेव्स्की (2021) द्वारा प्रस्तावित पोटेंशियल फंक्शन का उपयोग करते हैं:
$f(\theta) := (1 - \gamma) \|V_\theta - V_{\theta^*}\|_D^2 + \gamma \|V_\theta - V_{\theta^*}\|_{\text{Dir}}^2$
यह पोटेंशियल फायदेमंद है क्योंकि:

यह तब भी सुव्यवस्थित रहता है जब डिस्काउंट फैक्टर $\gamma \to 1$ होता है।
स्टेशनरी अपडेट फील्ड $\bar{g}(\theta)$ समानता $\langle -\bar{g}(\theta), \theta - \theta^* \rangle = f(\theta) - f(\theta^*)$ को संतुष्ट करता है, जो अन्य कार्यों में उपयोग किए जाने वाले असमानताओं (Inequalities) की तुलना में विश्लेषण को सरल बनाता है।

2. इंडक्शन के माध्यम से सेल्फ-बाउंडिंग प्रॉपर्टी

मुख्य तकनीकी योगदान TD अपडेट्स का एक नवीन सेल्फ-बाउंडिंग गुण है। लेखक सिद्ध करते हैं कि, बिना इटरेट्स को प्रोजेक्ट किए, यदि स्टेपसाइज़ को सावधानीपूर्वक चुना जाए, तो अनुक्रम $\{\theta_t\}$ इष्टतम समाधान $\theta^*$ के आसपास अपेक्षा (Expectation) में सीमित रहता है।

स्टेपसाइज़ डिज़ाइन: स्टेपसाइज़ को $\eta_t = \frac{1}{c \phi_\infty^2 \log(T) \log(t+3) \sqrt{t+1}}$ के रूप में परिभाषित किया गया है, जहाँ $c$ एक स्थिरांक है जो $c > 15 + 18\sqrt{2}$ को संतुष्ट करता है।
इंडक्टिव तर्क (Inductive Argument): प्रमाण इंडक्शन (Induction) द्वारा आगे बढ़ता है। यह मानते हुए कि समय $t-1$ तक इटरेट्स सीमित हैं, लेखक दिखाते हैं कि समय $t$ पर अपडेट सीमित रहता है। यह अपडेट को मार्टिंगेल डिफरेंस सीक्वेंस (शोर) और बायस टर्म में विघटित करने पर निर्भर करता है।
मार्कोवियन शोर को संभालना: मार्कोवियन सहसंबंधों (जहाँ $E[g(\theta, Z_t) | \mathcal{F}_{t-1}] \neq \bar{g}(\theta)$ ) द्वारा उत्पन्न बायस को संबोधित करने के लिए, लेखक अंतर्निहित मार्कोव चेन की ज्यामितीय मिक्सिंग (Geometric Mixing) का लाभ उठाते हैं (थ्योरम 3.2)। वे वर्तमान अवस्था वितरण को एक अंतराल $k'$ पर स्टेशनरी वितरण से जोड़कर बायस को सीमित करते हैं, जिसमें क्षय दर $\alpha^k$ का उपयोग किया जाता है।

3. बाउंडेडनेस विश्लेषण (Boundedness Analysis)

लेखक प्रदर्शित करते हैं कि इटरेट्स निम्नलिखित को संतुष्ट करते हैं:
$E[\|\theta_t\|^2] \leq \rho_c^2 \max\left(\frac{r_\infty^2}{\phi_\infty^2}, \|\theta^*\|^2\right)$
जहाँ $\rho_c$ स्टेपसाइज़ पैरामीटर पर निर्भर एक स्थिरांक है। यह बाउंडेडनेस बिना इटरेट्स को प्रोजेक्ट किए प्राप्त की गई है, जो प्रभावी रूप से इंडक्शन लूप को बंद करती है।

मुख्य परिणाम

सैद्धांतिक गारंटी

थ्योरम 4.2: निर्दिष्ट स्टेपसाइज़ के साथ अनप्रोजेक्टेड TD(0) द्वारा उत्पन्न वेटेड एवरेज इटरेट $\bar{\theta}_T$ के लिए, इटरेट्स का अपेक्षित स्क्वेर्ड नॉर्म एक स्थिरांक द्वारा सीमित है जो मिक्सिंग टाइम और वक्रता $\omega$ से स्वतंत्र है।

कोरोलरी 4.3: एल्गोरिदम निम्नलिखित दर प्राप्त करता है:
$f(\bar{\theta}_T) - f(\theta^*) = \tilde{O}\left( \frac{c \rho_c^2 \max\{r_\infty^2, \phi_\infty^2 \|\theta^*\|^2\}}{\sqrt{T}} \right)$
महत्वपूर्ण रूप से, $\tilde{O}$ नोटेशन में छिपे हुए स्थिरांक $\|\theta^*\|$ और फीचर बाउंड्स पर निर्भर करते हैं, लेकिन वे न्यूनतम वक्रता $\omega$ (या मिक्सिंग टाइम $\alpha$ ) पर निर्भर नहीं करते हैं (स्टेपसाइज़ कंडीशन में एक मामूली पॉलीलॉगैरिथमिक सुधार को छोड़कर)।

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

प्रोजेक्टेड रोबस्ट रेट्स के विरुद्ध: भंडारी एट अल. (2018) के विपरीत, यह परिणाम प्रोजेक्शन स्टेप और $\theta^*$ के पूर्व-निर्धारित बाउंड्स की आवश्यकता को हटा देता है। दर तुलनीय ( $\tilde{O}(1/\sqrt{T})$ ) है लेकिन बिना किसी कृत्रिम बाधा के प्राप्त की गई है।
अनप्रोजेक्टेड फास्ट रेट्स के विरुद्ध: स्ट्रिकेंट और यिंग (2019) और बाद के कार्यों के विपरीत, जो $O(1/T)$ प्राप्त करते हैं, यह परिणाम अज्ञात वक्रता पैरामीटर $\omega$ पर निर्भर नहीं है। लेखक एक काउंटर-एग्जांपल के माध्यम से दिखाते हैं कि $\omega$ मनमाने ढंग से छोटा हो सकता है, जिससे फास्ट रेट्स व्यवहार में अत्यधिक धीमे हो सकते हैं, जबकि रोबस्ट रेट स्थिर रहता है।

महत्व और दावे

यह पेपर भंडारी एट अल. (2018) द्वारा पहचाने गए एक विशिष्ट खुले प्रश्न को हल करने का दावा करता है: रैखिक फलन सन्निकटन के साथ अनप्रोजेक्टेड TD(0) का एक फाइनाइट-टाइम विश्लेषण प्रदान करना जो एक सुदृढ़ अभिसरण दर प्राप्त करता है।

कृत्रिम धारणाओं को हटाना: यह कार्य प्रदर्शित करता है कि प्रोजेक्शन स्टेप, जिसे पहले रोबस्ट विश्लेषण के लिए आवश्यक माना जाता था, आवश्यक नहीं है। जब स्टेपसाइज़ को लॉगरिदमिक कारकों के साथ उचित रूप से स्केल किया जाता है, तो इटरेट्स की बाउंडेडनेस एल्गोरिदम की गतिशीलता से स्वाभाविक रूप से उभरती है।
कोई अतिरिक्त रेगुलैरिटी नहीं: परिणाम समस्या की संरचना पर मानक धारणाओं (अपरिवर्तनीयता, एपीरियडिसिटी, फीचर्स का पूर्ण कॉलम रैंक) के अलावा किसी अतिरिक्त रेगुलैरिटी कंडीशन के बिना मान्य है।
व्यावहारिक प्रासंगिकता: लेखक इस बात पर जोर देते हैं कि जबकि थ्योरी में प्रमाणों को सरल बनाने के लिए प्रोजेक्शन का उपयोग किया जाता है, वे व्यवहार में उपयोग नहीं किए जाते हैं। यह विश्लेषण सैद्धांतिक गारंटी और व्यावहारिक एल्गोरिदम डिज़ाइन के बीच के अंतर को पाटता है।
स्थिरता थ्रेशोल्ड (Stability Threshold): पेपर स्टेपसाइज़ स्थिरांक $c$ के लिए एक थ्रेशोल्ड (विशेष रूप से $c > 15 + 18\sqrt{2}$ ) की पहचान करता है जो स्थिरता के लिए पर्याप्त स्थिति है। सिंथेटिक डेटा पर प्रयोगात्मक परिणाम बताते हैं कि यह थ्रेशोल्ड एक वास्तविक फाइनाइट-टाइम स्थिरता प्रभाव को पकड़ता है; यदि $c$ बहुत छोटा है, तो इटरेट्स विचलित (Diverge) हो सकते हैं।

लेखक नोट करते हैं कि $c$ पर थ्रेशोल्ड एक रूढ़वादी पर्याप्त स्थिति है जो प्रमाण स्थिरांकों (ट्रायंगल इनइक्वलिटी, कॉची-श्वार्ज़, इंटीग्रल टेस्ट) से व्युत्पन्न है और यह आवश्यक रूप से एक सटीक व्यावहारिक ट्यूनिंग नियम नहीं है। इसके अलावा, $T$ के लिए मिक्सिंग टाइम $\alpha$ के सापेक्ष पर्याप्त बड़ा होना एक सीमा है जो व्यापक साहित्य में साझा की जाती है, हालांकि लेखक एक "एनीटाइम" (Anytime) फॉर्मूलेशन के बजाय धारणाओं के निष्पादन योग्य प्रस्तुतिकरण को प्राथमिकता देते हैं।