🤖 machine learning

A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging

यह शोध पत्र यह प्रदर्शित करता है कि पॉलीक-रुपर्ट एवरेजिंग (Polyak-Ruppert averaging) के साथ एक प्लेन अनप्रोजेक्टेड लीनियर TD(0) एल्गोरिदम, जो केवल मिक्सिंग टाइम (mixing time) पर निर्भर एकल स्टेपसाइज़ का उपयोग करता है, बिना समस्या के कर्वेचर पैरामीटर के पूर्व ज्ञान के, स्वचालित पथवार स्थिरता (pathwise stability) और एक उच्च-संभाव्यता अभिसरण दर (high-probability convergence rate) को एक साथ प्राप्त करता है जो कि रोबस्ट (वक्रता-मुक्त/curvature-free) और तेज़ (वक्रता-निर्भर/curvature-dependent) दोनों है।

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

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

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

CC BY 4.0

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

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

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

समस्या यह है कि रोबोट का पथ सिक्का उछालने जैसा यादृच्छिक (random) नहीं है। यह एक निरंतर यात्रा है जहाँ आज का कदम कल के कदम पर बहुत अधिक निर्भर करता है। यह एक "मार्कोवियन" (Markovian) शोर की समस्या पैदा करता है: डेटा "चिपचिपा" और सह-संबंधित (correlated) है, जिससे यह अनुमान लगाना कठिन हो जाता है कि रोबोट कितनी तेजी से सीखेगा या क्या वह नियंत्रण से बाहर होकर भटक जाएगा।

वर्षों तक, गणितज्ञों के सामने एक दुविधा थी:

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

बड़ी सफलता
वेई-चेंग ली और फ्रांसेस्को ओराबना का यह शोध पत्र कहता है: "आपको किसी बाड़ की आवश्यकता नहीं है, और न ही आपको पहले से वक्रता जानने की आवश्यकता है। आपको बस एक विशिष्ट, सरल नियम की आवश्यकता है कि रोबोट को कितनी तेजी से कदम बढ़ाना चाहिए।"

उन्होंने इसे कैसे किया, इसके लिए यहाँ कुछ रचनात्मक उपमाएँ दी गई हैं:

1. "एक ही आकार सबके लिए उपयुक्त" (One-Size-Fits-All) स्टेप साइज

कल्पना कीजिए कि आप एक ऊबड़-खाबड़ रास्ते पर चल रहे हैं। आमतौर पर, यदि रास्ता फिसलन भरा है (रोबस्ट/robust), तो आप धीरे चलेंगे या यदि रास्ता चिकना है (फास्ट/fast), तो आप तेज़ चलेंगे।
लेखकों ने एक एकल चलने की लय (स्टेप साइज शेड्यूल) खोज निकाली जो इन दोनों परिदृश्यों के लिए एक साथ काम करती है।

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

2. "स्व-सीमांकन" (Self-Bounding) तकनीक (बाड़ की आवश्यकता नहीं)

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

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

3. "पॉइसन समीकरण" (Poisson Equation) टूलकिट (गाँठ को सुलझाना)

समस्या का सबसे कठिन हिस्सा यह है कि रोबोट का डेटा "मार्कोवियन" है—आज का डेटा कल के डेटा के साथ उलझा हुआ है। यह शोर भरे कमरे में बातचीत सुनने जैसा है जहाँ पिछले वाक्य का शोर अगले वाक्य में गूँज रहा होता है।

समाधान: लेखकों ने पॉइसन समीकरण (Poisson Equation) नामक एक गणितीय उपकरण का उपयोग किया।
उपमा: कल्पना कीजिए कि कमरे में शोर धागे की एक उलझी हुई गेंद की तरह है। पॉइसन समीकरण एक विशेष कैंची है जो धागे को दो साफ ढेरों में काट देती है:
1. मार्टिंगेल ढेर (The Martingale Pile): यह "निष्पक्ष" शोर है। यह एक सिक्के के उछाल की तरह है; यह समय के साथ शून्य पर औसत हो जाता है।
2. शेष ढेर (The Remainder Pile): यह "गूँज" वाला शोर है। लेखकों ने सिद्ध किया कि यह ढेर छोटा और नियंत्रणीय है।
  शोर को इस तरह अलग करके, वे सिद्ध कर सके कि रोबोट का सीखने का पथ स्थिर और अनुमानित है, भले ही उसे भूलभुलैया के सटीक आकार का पता न हो।

परिणाम: दोनों दुनियाओं का सर्वश्रेष्ठ संगम

क्योंकि वे बिना बाड़ के रोबोट को स्थिर रखने और शोर वाले डेटा को सुलझाने में सफल रहे, उन्होंने एक ही एल्गोरिदम के साथ दो चीजें एक साथ हासिल कीं:

मजबूती (Robustness): भले ही भूलभुलैया बहुत खराब हो (वक्रता शून्य के करीब हो), रोबोट एक स्थिर, गारंटीकृत गति से सीखता है।
गति (Speed): यदि भूलभुलैया अच्छी है (वक्रता उच्च है), तो रोबोट बहुत तेज़ी से सीखता है, और अच्छी स्थितियों का लाभ उठाता है।

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

तकनीकी सारांश: अनप्रोजेक्टेड लीनियर TD(0) के लिए एक एकल स्टेपसाइज़ पर्याप्त है

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

यह शोध पत्र मार्कोवियन सैंपलिंग के तहत ज़ीरो-बायस (TD(0)) के लीनियर टेम्पोरल डिफरेंस लर्निंग के फाइनाइट-टाइम, हाई-प्रोबेबिलिटी कन्वर्जेंस विश्लेषण को संबोधित करता है। इस सेटिंग में, डेटा एक मार्कोव चेन की एकल प्रक्षेपवक्र (trajectory) के साथ उत्पन्न होता है, न कि स्वतंत्र और समान रूप से वितरित (i.i.d.) नमूनों के रूप में।

मुख्य चुनौती यह है कि TD(0) एक मानक स्टोकेस्टिक ग्रेडिएंट विधि नहीं है; इसके अपडेट बायस्ड (biased), नॉन-सिमेट्रिक हैं और शोर (noise) टेम्पोरली कोरिलेटेड (temporally correlated) है। इसके अलावा, अपडेट का परिमाण वर्तमान इटरैट्स (iterates) के परिमाण पर निर्भर करता है। मौजूदा नॉन-एसिम्पटोटिक विश्लेषण आमतौर पर दो प्रतिबंधात्मक दृष्टिकोणों में से एक पर निर्भर करते हैं:

प्रोजेक्शन (Projections): इटरैट्स को एक ज्ञात बॉल पर प्रोजेक्ट करके उन्हें बाउंड (bounded) रखना। यह कंसंट्रेशन आर्गुमेंट्स को सरल बनाता है लेकिन एल्गोरिदम को बदल देता है और इसके लिए एक उपयुक्त रेडियस के पूर्व ज्ञान की आवश्यकता होती है (जो अक्सर समस्या के कर्वेचर से जुड़ा होता है)।
कर्वेचर-डिपेंडेंट स्टेबिलिटी (Curvature-Dependent Stability): बिना प्रोजेक्शन के स्थिरता सुनिश्चित करने के लिए मीन डायनेमिक्स की कॉन्ट्रैक्टिव प्रकृति का लाभ उठाना। हालाँकि, यह आमतौर पर ऐसे स्टेपसाइज़ कंडीशंस या स्टेबिलिटी बाउंड्स देता है जो एक अज्ञात कर्वेचर पैरामीटर ( $\omega$ ) पर निर्भर होते हैं। जब $\omega$ छोटा होता है, तो ये बाउंड्स अत्यधिक धीमे हो जाते हैं, और स्टेपसाइज़ को $\omega$ से स्वतंत्र रूप से नहीं चुना जा सकता है।

लेखक एक एकल स्टेपसाइज़ शेड्यूल स्थापित करने का लक्ष्य रखते हैं जो कर्वेचर पैरामीटर $\omega$ से स्वतंत्र हो और जिसमें किसी प्रोजेक्शन की आवश्यकता न हो, फिर भी साथ ही यह गारंटी दे सके:

रोबस्टनेस (Robustness): एक कन्वर्जेंस रेट $\tilde{O}(1/\sqrt{T})$ जो $\omega$ के बावजूद बना रहता है।
फास्टनेस (Fastness): एक कन्वर्जेंस रेट $\tilde{O}(1/(\omega T))$ जो अनुकूल कर्वेचर होने पर इसका लाभ उठाता है।

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

1. पॉइसन समीकरणों के माध्यम से सेल्फ-बाउंडिंग तर्क (Self-Bounding Argument via Poisson Equations)

केंद्रीय तकनीकी नवीनता एक नया "सेल्फ-बाउंडिंग" इंडक्टिव तर्क है जो कर्वेचर $\omega$ या कृत्रिम प्रोजेक्शन पर निर्भर किए बिना इटरैट्स $\theta_t$ की पाथवाइज बाउंडेडनेस को नियंत्रित करता है।

लूप (The Loop): एक नेटिव कंसंट्रेशन विश्लेषण गोलाकार (circular) है: एरर को बाउंड करने के लिए बाउंडेड अपडेट की आवश्यकता है, लेकिन बाउंडेड अपडेट के लिए बाउंडेड इटरैट्स की आवश्यकता है।
समाधान: लेखक ज्यामितीय रूप से मिक्सिंग मार्कोव चेन से जुड़े पॉइसन समीकरण (Poisson equation) का उपयोग करके मार्कोवियन नॉइज़ को डीकंपोज़ करते हैं। एक सेंटर्ड फोर्सिंग टर्म $h$ के लिए, वे $u - P_Z u = \tilde{h}$ को हल करते हैं।
डीकंपोजिशन: यह मार्कोव नॉइज़ के संचय को एक मार्टिंगेल टर्म ( $M_t$ ) और एक नियंत्रित रिमाइंडर टर्म ( $R_t$ ) में डीकंपोज़ करने की अनुमति देता है।
इंडक्शन: वे एक इंडक्टिव हाइपोथेसिस स्थापित करते हैं जहाँ समय $t-1$ तक इटरैट्स की बाउंडेडनेस, समय $t$ पर बाउंडेडनेस को दर्शाती है। पिनेलिस इनइक्वालिटी (Pinelis' inequality) के माध्यम से मार्टिंगेल टर्म को और पॉइसन सॉल्यूशन के लिप्सचिट्ज़ गुणों के माध्यम से रिमाइंडर टर्म को नियंत्रित करके, वे यह सिद्ध करते हैं कि इटरैट्स उच्च संभाव्यता के साथ यूनिफॉर्मली बाउंड रहते हैं, जो $\omega$ से स्वतंत्र है।

2. पोलियाक-रुपर्ट (PR) एवरेजिंग

शोध पत्र पोलियाक-रुपर्ट एवरेजड इटरैट $\bar{\theta}_T = \frac{1}{S_T} \sum_{t=1}^T \eta_{t-1} \theta_{t-1}$ का विश्लेषण करता है, जहाँ $S_T = \sum \eta_{t-1}$ है।

एक बार जब $\theta_t$ की यूनिफॉर्म बाउंडेडनेस स्थापित हो जाती है, तो लेखक मार्टिंगेल टर्म्स के क्वाड्रेटिक वेरिएशन और कन्वर्जेंस विश्लेषण में बायस टर्म्स को नियंत्रित कर सकते हैं।
वे पोटेंशियल फंक्शन एरर $f(\bar{\theta}_T) - f(\theta^*)$ $f (\overset{ˉ}{θ}_{T}) - f (θ^{*})$ के लिए दो अलग-अलग अपर बाउंड प्राप्त करते हैं:
- एक रोबस्ट बाउंड जो क्लासिक एवरेजड स्टोकेस्टिक ग्रेडिएंट डिसेंट विश्लेषण से प्राप्त होता है, जो $\tilde{O}(1/\sqrt{T})$ प्रदान करता है।
- एक फास्ट बाउंड जो एरर $e_t = \theta_t - \theta^*$ के विकास का विश्लेषण करके और TD मैट्रिक्स के सिमेट्रिक पार्ट की पॉजिटिव डेफिनेटनेस (कर्वेचर $\omega$ ) का लाभ उठाकर प्राप्त होता है, जो $\tilde{O}(1/(\omega T))$ प्रदान करता है।

3. स्टेपसाइज़ शेड्यूल

प्रस्तावित स्टेपसाइज़ है:
$\eta_t = \frac{1}{c \tau_{\text{mix}} \phi_\infty^2} \cdot \frac{1}{\sqrt{t+1} \log(t+3)}$
जहाँ $c$ एक संख्यात्मक स्थिरांक है, $\tau_{\text{mix}}$ मिक्सिंग टाइम है, और $\phi_\infty$ फीचर नॉर्म्स को बाउंड करता है। महत्वपूर्ण रूप से, यह शेड्यूल मिक्सिंग टाइम पर निर्भर करता है लेकिन $\omega$ पर नहीं।

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

1. हाई-प्रोबेबिलिटी बाउंडेडनेस (Theorem 4.1)

मानक धारणाओं (एर्गोडिक MRP, फुल-रैंक फीचर्स) के तहत, अनप्रोजेक्टेड TD(0) इटरैट्स उच्च संभाव्यता ( $1-\delta$ ) के साथ यूनिफॉर्मली बाउंड हैं:
$\sup_{t \ge 0} \|\theta_t\|^2 \le \rho R_{\text{base}}$
जहाँ $R_{\text{base}}$ प्रारंभिक एरर, ऑप्टिमल सॉल्यूशन नॉर्म, और समस्या के स्थिरांकों पर निर्भर करता है, लेकिन $\omega$ से स्वतंत्र है। यह बिना $\omega$ का उपयोग किए स्टेपसाइज़ या स्टेबिलिटी आर्गुमेंट के, मार्कोवियन सैंपलिंग के तहत अनप्रोजेक्टेड TD(0) के लिए ऐसी बाउंडेडनेस दिखाने वाला पहला परिणाम है।

2. समवर्ती कन्वर्जेंस रेट्स (Theorem 4.2)

उसी स्टेपसाइज़ और PR एवरेजिंग का उपयोग करके, एल्गोरिदम पोटेंशियल फंक्शन एरर के लिए एक हाई-प्रोबेबिलिटी कन्वर्जेंस रेट प्राप्त करता है:
$f(\bar{\theta}_T) - f(\theta^*) \le \min \left\{ \frac{C_{\text{fast}}}{\omega S_T^2}, \frac{C_{\text{robust}}}{S_T} \right\}$
स्टेपसाइज़ शेड्यूल को प्रतिस्थापित करने पर, यह निम्नलिखित में अनुवादित होता है:

रोबस्ट रेट: $\tilde{O}\left( \frac{\tau_{\text{mix}} R_{\text{base}}^2}{\sqrt{T}} \right)$
फास्ट रेट: $\tilde{O}\left( \frac{\tau_{\text{mix}}^2 R_{\text{base}}^2}{\omega T} \right)$

यह बाउंड बिना किसी पूर्व ज्ञान के $\omega$ के न्यूनतम दो दरों में से स्वतः अनुकूलित हो जाता है।

3. मिक्सिंग-फ्री वेरिएंट (Appendix E)

लेखक एक संशोधित स्टेपसाइज़ $\eta_t \propto \frac{1}{\sqrt{t} \log^2 t}$ भी प्रस्तावित करते हैं जिसके लिए $\tau_{\text{mix}}$ के ज्ञान की आवश्यकता नहीं है। हालांकि, यह कन्वर्जेंस बाउंड के स्थिरांकों में $\tau_{\text{mix}}$ पर डबल एक्सपोनेंशियल डिपेंडेंस की कीमत पर आता है।

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

शोध पत्र दावा करता है कि यह पहले कार्यों में से एक है जिसने यह स्थापित किया है कि लीनियर TD(0) मार्कोवियन सैंपलिंग के साथ एक एकल स्टेपसाइज़ का उपयोग करके दोनों रोबस्ट और फास्ट हाई-प्रोबेबिलिटी कन्वर्जेंस रेट प्राप्त कर सकता है जो:

कर्वेचर पैरामीटर $\omega$ से स्वतंत्र है।
प्रोजेक्शन-फ्री है।

लेखक इस बात पर जोर देते हैं कि पिछले कार्यों ने या तो प्रोजेक्शन की आवश्यकता थी (एल्गोरिदम को बदल दिया), या कर्वेचर-डिपेंडेंट स्टेपसाइज़ पर निर्भर किया (जब $\omega$ छोटा हो तो विफल हो गए), या केवल एक्सपेक्टेशन बाउंड प्रदान किए (जैसे ली और ओराबोना [2025]) न कि हाई-प्रोबेबिलिटी गारंटी।

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

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