2025-11-25T11:58:17.992104

Multi Timescale Stochastic Approximation: Stability and Convergence

Deb, Ganesh, Bhatnagar
This paper presents the first sufficient conditions that guarantee the stability and almost sure convergence of multi-timescale stochastic approximation (SA) iterates. It extends the existing results on one-timescale and two-timescale SA iterates to general $N$-timescale stochastic recursions, for any $N \geq 1$, using the ordinary differential equation (ODE) method. As an application, we study SA algorithms augmented with heavy-ball momentum in the context of Gradient Temporal Difference (GTD) learning. The added momentum introduces an auxiliary state evolving on an intermediate timescale, yielding a three-timescale recursion. We show that with appropriate momentum parameters, the scheme fits within our framework and converges almost surely to the same fixed point as baseline GTD. The stability and convergence of all iterates including the momentum state follow from our main results without ad hoc bounds. We then study off-policy actor-critic algorithms with a baseline learner, actor, and critic updated on separate timescales. In contrast to prior work, we eliminate projection steps from the actor update and instead use our framework to guarantee stability and almost sure convergence of all components. Finally, we extend the analysis to constrained policy optimization in the average reward setting, where the actor, critic, and dual variables evolve on three distinct timescales, and we verify that the resulting dynamics satisfy the conditions of our general theorem. These examples show how diverse reinforcement learning algorithms covering momentum acceleration, off-policy learning, and primal-dual methods-fit naturally into the proposed multi-timescale framework.
academic

बहु समयमान स्टोकेस्टिक सन्निकटन: स्थिरता और अभिसरण

मूल जानकारी

  • पेपर ID: 2112.03515
  • शीर्षक: Multi Timescale Stochastic Approximation: Stability and Convergence
  • लेखक: Rohan Deb (University of Illinois, Urbana-Champaign), Swetha Ganesh (Purdue University, West Lafayette), Shalabh Bhatnagar (Indian Institute of Science, Bengaluru)
  • वर्गीकरण: eess.SY cs.SY
  • प्रकाशन समय: 16 अक्टूबर, 2025 (arXiv संस्करण)
  • पेपर लिंक: https://arxiv.org/abs/2112.03515v3

सारांश

यह पेपर बहु समयमान स्टोकेस्टिक सन्निकटन (Multi-timescale Stochastic Approximation, SA) पुनरावृत्तियों की स्थिरता और लगभग निश्चित अभिसरण की गारंटी देने वाली पहली पर्याप्त शर्तें प्रस्तुत करता है। यह कार्य मौजूदा एकल समयमान और द्वि-समयमान SA परिणामों को सामान्य N समयमान स्टोकेस्टिक पुनरावर्तन तक विस्तारित करता है, किसी भी N≥1 के लिए, साधारण अवकल समीकरण (ODE) विधि का उपयोग करते हुए। एक अनुप्रयोग के रूप में, प्रवणता समय-अंतर (GTD) शिक्षण में भारी गेंद गति को बढ़ाने वाले SA एल्गोरिदम का अध्ययन किया गया। जोड़ी गई गति ने मध्यवर्ती समयमान पर विकसित होने वाली सहायक अवस्था को प्रस्तुत किया, जिससे त्रि-समयमान पुनरावर्तन उत्पन्न हुआ। यह सिद्ध किया गया कि उपयुक्त गति मापदंडों के तहत, यह योजना ढांचे के अनुरूप है और लगभग निश्चित रूप से आधारभूत GTD के समान निश्चित बिंदु पर अभिसरित होती है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

स्टोकेस्टिक सन्निकटन एल्गोरिदम पुनरावृत्तिमूलक प्रक्रियाओं का एक वर्ग है जो किसी फ़ंक्शन के शून्य को खोजने के लिए उपयोग किया जाता है, जब वास्तविक फ़ंक्शन अज्ञात हो लेकिन शोरपूर्ण अवलोकन उपलब्ध हों। कई अनुकूलन और अनिश्चितता नियंत्रण समस्याओं में, तीन या अधिक समयमान पुनरावर्तन वाले एल्गोरिदम का सामना किया जाता है।

अनुसंधान का महत्व

  1. व्यावहारिक आवश्यकता: सुदृढ़ शिक्षण में, बाधित मार्कोव निर्णय प्रक्रियाओं के actor-critic एल्गोरिदम, पदानुक्रमित सुदृढ़ शिक्षण आदि परिदृश्यों में बहु-समयमान एल्गोरिदम स्वाभाविक रूप से प्रकट होते हैं
  2. सैद्धांतिक अंतराल: मौजूदा साहित्य केवल एकल समयमान और द्वि-समयमान SA की स्थिरता और अभिसरण शर्तें प्रदान करता है, N>2 मामलों के लिए सामान्य सिद्धांत की कमी है

मौजूदा विधियों की सीमाएं

  1. स्थिरता धारणा: मौजूदा द्वि-समयमान विश्लेषण मानते हैं कि पुनरावृत्तियां स्थिर (परिबद्ध) रहती हैं, यह एक गैर-तुच्छ आवश्यकता है
  2. सत्यापन कठिनाई: हाल ही तक इस स्थिरता आवश्यकता को सत्यापित करने के लिए शर्तें उपलब्ध नहीं थीं
  3. प्रयोज्यता सीमा: तीन से अधिक समयमान वाले जटिल एल्गोरिदम को संभालने में असमर्थ

अनुसंधान प्रेरणा

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

मुख्य योगदान

  1. सैद्धांतिक सफलता: N समयमान SA पुनरावृत्तियों की स्थिरता और लगभग निश्चित अभिसरण की गारंटी देने वाली पहली शर्तें प्रस्तुत करना
  2. विधि विस्तार: Borkar-Meyn एकल समयमान और Lakshminarayanan-Bhatnagar द्वि-समयमान परिणामों को किसी भी N≥1 तक सामान्यीकृत करना
  3. अनुप्रयोग सत्यापन: तीन महत्वपूर्ण सुदृढ़ शिक्षण परिदृश्यों में ढांचे की प्रभावशीलता को सत्यापित करना:
    • गति के साथ प्रवणता समय-अंतर (GTD) शिक्षण
    • नीति-बाहर actor-critic एल्गोरिदम
    • बाधित नीति अनुकूलन
  4. तकनीकी नवाचार: actor अपडेट में प्रक्षेपण चरणों को समाप्त करना, केवल अभिसरण ढांचे पर स्थिरता सुनिश्चित करने के लिए निर्भर करना

विधि विवरण

कार्य परिभाषा

N युग्मित स्टोकेस्टिक पुनरावर्तन पर विचार करें:

x^(j)_{n+1} = x^(j)_n + α^(j)_n (h^(j)(x^(1)_n, x^(2)_n, ..., x^(N)_n) + M^(j)_{n+1})

जहां j = 1, 2, ..., N, निम्नलिखित सुनिश्चित करने की आवश्यकता है:

  • स्थिरता: sup_n ||x^(j)_n|| < ∞ a.s. ∀j
  • अभिसरण: x^(j)n → x^(j)* a.s. ∀j

मुख्य सैद्धांतिक ढांचा

मूल धारणाएं

(A:1) h^(j) Lipschitz सतत फ़ंक्शन है
(A:2) {M^(j)_{n+1}} मार्टिंगेल अंतर अनुक्रम है, जो सशर्त अपेक्षा परिबद्ध को संतुष्ट करता है
(A:3) चरण-आकार अनुक्रम संतुष्ट करते हैं:

  • α^(j)_n > 0, Σα^(j)_n = ∞
  • Σ(α^(j)_n)² < ∞
  • α^(j)_n/α^(j-1)_n → 0 (समयमान पृथक्करण)

स्थिरता शर्त (B.N.i)

स्केलिंग फ़ंक्शन h^(i)_c(x^(i), x^(i+1), ..., x^(N)) = h^(i)(cy^(1), cy^(2), ..., cy^(N))/c के लिए, आवश्यक है:

  1. h^(i)c → h^(i)∞ एकसमान अभिसरण
  2. सीमित ODE ẋ^(i)(t) = h^(i)_∞(x^(i)(t), x^(i+1), ..., x^(N)) का अद्वितीय वैश्विक स्पर्शोन्मुख स्थिर संतुलन बिंदु है
  3. संतुलन बिंदु मानचित्र λ^(i)_∞ Lipschitz सतत है

अभिसरण शर्त (C.N.i)

पदानुक्रमित निश्चित बिंदु संरचना के तहत मूल ODE प्रणाली की वैश्विक स्पर्शोन्मुख स्थिरता।

मुख्य प्रमेय

प्रमेय 1: धारणाओं (A:1)-(A:3), (B.N.i) और (C.N.i) के तहत, N समयमान पुनरावृत्ति पदानुक्रमित निश्चित बिंदु पर अभिसरित होती है:

x^(j)_n → x^(j)_* = λ^(j:N-1)(x^(N)_*)

प्रमाण रणनीति

  1. स्थिरता-अभिसरण अपघटन: पहले परिबद्धता मानकर अभिसरण सिद्ध करना, फिर स्थिरता सिद्ध करना
  2. समयमान कैस्केड: सबसे तेज़ समयमान से शुरू करके, प्रत्येक पैमाने के व्यवहार का क्रमिक विश्लेषण
  3. पुनरावर्ती स्केलिंग तर्क: मूल पुनरावृत्तियों की तुलना करने के लिए स्केलिंग पुनरावृत्तियों का उपयोग करके परिबद्धता सिद्ध करना

प्रायोगिक सेटअप

अनुप्रयोग परिदृश्य

1. गति के साथ GTD शिक्षण

  • डेटासेट: 5-State Random Walk, 7-state Boyan Chain
  • एल्गोरिदम: GTD2-M-3TS, TDC-M-3TS (त्रि-समयमान), GTD2-M-4TS, TDC-M-4TS (चतुर्थ-समयमान)
  • पैरामीटर सेटिंग:
    • 5-State RW: α=0.4, β=0.4, ϱ^(1)=0.5, ϱ^(2)=0.25
    • Boyan Chain: α=0.35, β=0.35, ϱ^(1)=0.45, ϱ^(2)=0.35

2. नीति-बाहर Actor-Critic

  • सेटअप: Gibbs नीति पैरामीटरकरण, महत्व नमूनाकरण अनुपात
  • अपडेट नियम: critic (सबसे तेज़), actor (मध्यम), baseline (सबसे धीमा) समयमान

3. बाधित Actor-Critic

  • समस्या: औसत पुरस्कार बाधित अनुकूलन
  • समयमान: critic (सबसे तेज़), actor (मध्यम), द्वैत चर (सबसे धीमा)

मूल्यांकन मेट्रिक्स

  • GTD: Root Mean Square Projected Bellman Error (RMSPBE)
  • Actor-Critic: नीति प्रदर्शन और अभिसरण
  • सैद्धांतिक सत्यापन: लगभग निश्चित अभिसरण प्रमाण

प्रायोगिक परिणाम

मुख्य परिणाम

GTD गति प्रयोग

  1. प्रदर्शन सुधार: गति संस्करण दोनों MDP पर vanilla संगत संस्करणों से बेहतर हैं
  2. अभिसरण सत्यापन: सभी एल्गोरिदम सैद्धांतिक रूप से पूर्वानुमानित निश्चित बिंदु θ* = -Ā^(-1)b̄ पर अभिसरित होते हैं
  3. समयमान तुलना:
    • GTD2: 4-TS योजना बेहतर प्रदर्शन करती है
    • TDC: 3-TS संस्करण बेहतर प्रदर्शन करता है

सैद्धांतिक सत्यापन

  1. स्थिरता: सभी तीन अनुप्रयोग धारणाओं (B.N.i) और (C.N.i) को संतुष्ट करते हैं
  2. अभिसरण: अपेक्षित पदानुक्रमित निश्चित बिंदु पर लगभग निश्चित अभिसरण सिद्ध किया गया
  3. कोई प्रक्षेपण नहीं: actor अपडेट में प्रक्षेपण संचालन को सफलतापूर्वक समाप्त किया गया

तकनीकी निष्कर्ष

  1. गति प्रभाव: भारी गेंद गति ने GTD एल्गोरिदम के अनुभवजन्य अभिसरण गति में महत्वपूर्ण सुधार किया
  2. ढांचे की सार्वभौमिकता: एक ही सैद्धांतिक ढांचा गति त्वरण, नीति-बाहर शिक्षण और प्राथमिक-द्वैत विधियों को सफलतापूर्वक संभालता है
  3. व्यावहारिक मूल्य: जटिल बहु-समयमान एल्गोरिदम के अभिसरण को सत्यापित करने के लिए व्यावहारिक उपकरण प्रदान करता है

संबंधित कार्य

सैद्धांतिक आधार

  1. एकल समयमान SA: Borkar-Meyn (2000) की ODE विधि और स्थिरता शर्तें
  2. द्वि-समयमान SA: Borkar (1997) का अभिसरण, Lakshminarayanan-Bhatnagar (2017) की स्थिरता
  3. सुदृढ़ शिक्षण अनुप्रयोग: Actor-critic एल्गोरिदम, GTD विधियां, बाधित MDP

इस पेपर के लाभ

  1. सैद्धांतिक पूर्णता: N समयमान के लिए पहली बार पूर्ण स्थिरता और अभिसरण सिद्धांत प्रदान करना
  2. व्यावहारिकता: शर्तें सत्यापन योग्य हैं, वास्तविक एल्गोरिदम डिजाइन के लिए लागू हैं
  3. अनुप्रयोग की व्यापकता: गति विधियां, नीति-बाहर शिक्षण, बाधित अनुकूलन आदि कई महत्वपूर्ण क्षेत्रों को शामिल करता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. N समयमान SA के लिए पहली व्यापक सैद्धांतिक ढांचा सफलतापूर्वक स्थापित किया गया
  2. तीन महत्वपूर्ण सुदृढ़ शिक्षण एल्गोरिदम वर्गों की स्थिरता और अभिसरण सिद्ध की गई
  3. समय-अंतर शिक्षण में गति तकनीकों की सैद्धांतिक व्यवहार्यता प्रदर्शित की गई

सीमाएं

  1. मार्कोव शोर: वर्तमान ढांचा मार्टिंगेल अंतर शोर तक सीमित है, अधिक सामान्य मार्कोव शोर को संभालता नहीं है
  2. चरण-आकार आवश्यकता: सैद्धांतिक विश्लेषण को वर्ग-योग्य चरण-आकार की आवश्यकता है, लेकिन प्रयोग दिखाते हैं कि गैर-वर्ग-योग्य चरण-आकार भी प्रभावी हैं
  3. सीमित समय विश्लेषण: अभिसरण दर का मात्रात्मक विश्लेषण की कमी

भविष्य की दिशाएं

  1. मार्कोव शोर तक विस्तार: Ramaswamy-Bhatnagar के एकल समयमान परिणामों को सामान्यीकृत करना
  2. समुच्चय-मूल्यवान मानचित्र: आंशिक अवलोकन/सूचना के तहत RL एल्गोरिदम को संभालना
  3. अभिसरण दर: N समयमान के लिए कमजोर अभिसरण दर सिद्धांत विकसित करना
  4. सीमित समय व्यवहार: गति एल्गोरिदम के सीमित समय प्रदर्शन लाभ को मापना

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक सफलता: बहु-समयमान SA सिद्धांत में महत्वपूर्ण अंतराल को भरता है, ऐतिहासिक महत्व रखता है
  2. विधि कठोरता: प्रमाण तकनीकें परिष्कृत हैं, पुनरावर्ती स्केलिंग तर्क जैसी नवीन तकनीकें उपयोग करती हैं
  3. अनुप्रयोग मूल्य: तीनों अनुप्रयोग परिदृश्य महत्वपूर्ण व्यावहारिक महत्व रखते हैं, ढांचे की सार्वभौमिकता प्रदर्शित करते हैं
  4. लेखन स्पष्टता: संरचना अच्छी है, 3 समयमान से शुरू करके N समयमान तक सामान्यीकृत करता है, समझने में सहायक

कमियां

  1. धारणा सीमाएं: i.i.d. नमूनाकरण धारणा वास्तविक RL में काफी सीमित है
  2. प्रयोग पैमाना: प्रयोग अपेक्षाकृत सरल हैं, बड़े जटिल वातावरण में सत्यापन की कमी
  3. कम्प्यूटेशनल जटिलता: सैद्धांतिक शर्तों को सत्यापित करने की कम्प्यूटेशनल जटिलता पर चर्चा नहीं की गई
  4. व्यावहारिक मार्गदर्शन: समयमान पृथक्करण मापदंडों को कैसे चुनें, इस पर विशिष्ट मार्गदर्शन की कमी

प्रभाव

  1. सैद्धांतिक योगदान: बहु-समयमान एल्गोरिदम डिजाइन के लिए ठोस सैद्धांतिक आधार प्रदान करता है
  2. व्यावहारिक मूल्य: जटिल RL एल्गोरिदम के अभिसरण विश्लेषण को संभव बनाता है
  3. प्रेरणादायक: अधिक बहु-समयमान एल्गोरिदम अनुसंधान को प्रेरित कर सकता है
  4. पुनरुत्पादनीयता: सैद्धांतिक परिणाम सत्यापन योग्य हैं, प्रयोग सेटअप स्पष्ट हैं

प्रयोज्य परिदृश्य

  1. बाधित सुदृढ़ शिक्षण: प्राथमिक-द्वैत अपडेट को संभालने की आवश्यकता वाले परिदृश्य
  2. पदानुक्रमित सुदृढ़ शिक्षण: बहु-स्तरीय निर्णय जिन्हें विभिन्न समयमान की आवश्यकता है
  3. गति त्वरण विधियां: RL में गति तकनीकों के लिए सैद्धांतिक समर्थन
  4. एल्गोरिदम डिजाइन: नए बहु-समयमान एल्गोरिदम के अभिसरण सत्यापन के लिए उपकरण

संदर्भ

यह पेपर मुख्य रूप से निम्नलिखित महत्वपूर्ण कार्यों पर आधारित है:

  1. Borkar, V.S. (2008). Stochastic Approximation: A Dynamical Systems Viewpoint
  2. Lakshminarayanan, C. & Bhatnagar, S. (2017). A stability criterion for two-timescale stochastic approximation schemes
  3. Sutton, R. et al. (2009). Fast gradient-descent methods for temporal-difference learning with linear function approximation

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