असिंक्रोनस औसत Q-लर्निंग के लिए केंद्रीय सीमा प्रमेय

बुनियादी जानकारी

• पेपर ID: 2509.18964
• शीर्षक: असिंक्रोनस औसत Q-लर्निंग के लिए केंद्रीय सीमा प्रमेय
• लेखक: Xingtu Liu (साइमन फ्रेजर विश्वविद्यालय)
• वर्गीकरण: cs.LG math.OC stat.ML
• प्रकाशन सम्मेलन: OPT2025: मशीन लर्निंग के लिए अनुकूलन पर 17वीं वार्षिक कार्यशाला
• पेपर लिंक: https://arxiv.org/abs/2509.18964

सारांश

यह पेपर असिंक्रोनस अपडेट के तहत Polyak-Ruppert औसत Q-लर्निंग के लिए केंद्रीय सीमा प्रमेय स्थापित करता है। लेख एक गैर-स्पर्शोन्मुख केंद्रीय सीमा प्रमेय साबित करता है, जिसका Wasserstein दूरी में अभिसरण दर पुनरावृत्तियों की संख्या, स्थिति-क्रिया स्पेस के आकार, छूट कारक और अन्वेषण गुणवत्ता पर निर्भरता को स्पष्ट रूप से प्रतिबिंबित करता है। इसके अतिरिक्त, एक कार्यात्मक केंद्रीय सीमा प्रमेय भी प्राप्त किया गया है, जो दर्शाता है कि आंशिक योग प्रक्रिया ब्राउनियन गति में कमजोर रूप से अभिसरित होती है।

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

समस्या पृष्ठभूमि

1. Q-लर्निंग का महत्व: Q-लर्निंग सुदृढ़ शिक्षा में सबसे व्यापक रूप से उपयोग किए जाने वाले एल्गोरिदम में से एक है, जो अनुभवजन्य प्रक्षेपवक्र से सीधे इष्टतम क्रिया-मूल्य फ़ंक्शन सीखता है, और Atari गेम, Go, रोबोटिक्स हेराफेरी और बड़े भाषा मॉडल संरेखण जैसे क्षेत्रों में विशाल सफलता प्राप्त की है।
2. सैद्धांतिक विश्लेषण की चुनौतियाँ:
   • Q-लर्निंग को स्टोकेस्टिक सन्निकटन (SA) का एक उदाहरण माना जा सकता है, लेकिन असिंक्रोनस Q-लर्निंग मार्कोवियन शोर के साथ एक गैर-रैखिक SA समस्या है
   • रैखिक SA और TD लर्निंग की तुलना में, Q-लर्निंग का विश्लेषण अधिक चुनौतीपूर्ण है क्योंकि इसकी गैर-रैखिकता, गैर-चिकनी ऑपरेटर और गैर-स्थिर प्रक्रिया की विशेषताएं हैं
   • असिंक्रोनस अपडेट मार्कोवियन शोर को और भी जोड़ता है, जिससे विश्लेषण की जटिलता बढ़ जाती है
3. मौजूदा कार्य की सीमाएं:
   • पूर्ववर्ती कार्य ने सिंक्रोनस Q-लर्निंग के लिए कार्यात्मक CLT स्थापित किया है, लेकिन सिंक्रोनस Q-लर्निंग केवल मार्टिंगेल शोर पर विचार करता है
   • Zhang और Xie (2024) ने स्थिर चरण-लंबाई के असिंक्रोनस Q-लर्निंग के लिए कार्यात्मक CLT स्थापित किया है, लेकिन स्थिर चरण-लंबाई गैर-स्पर्शोन्मुख CLT स्थापित करने के लिए आवश्यक शर्तों को पूरा नहीं करती है
   • वर्तमान में Q-लर्निंग के लिए कोई गैर-स्पर्शोन्मुख CLT नहीं है, यहां तक कि सिंक्रोनस सेटिंग में भी

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

केंद्रीय सीमा प्रमेय स्थापित करना एल्गोरिदम के सांख्यिकीय गुणों को समझने के लिए महत्वपूर्ण है, यह स्पर्शोन्मुख सामान्यता सुदृढ़ शिक्षा में अनिश्चितता परिमाणीकरण और सांख्यिकीय अनुमान के लिए महत्वपूर्ण है।

मुख्य योगदान

1. Q-लर्निंग का पहला गैर-स्पर्शोन्मुख CLT: असिंक्रोनस औसत Q-लर्निंग के लिए गैर-स्पर्शोन्मुख केंद्रीय सीमा प्रमेय साबित किया गया है, अभिसरण दर $\tilde{O}((|S||A|)^{1/2}K^{-1/6}\rho^{-2}(1-\gamma)^{-3})$ है
2. कार्यात्मक केंद्रीय सीमा प्रमेय: क्षय चरण-लंबाई के तहत असिंक्रोनस Q-लर्निंग के लिए कार्यात्मक CLT स्थापित किया गया है, जो दर्शाता है कि आंशिक योग प्रक्रिया ब्राउनियन गति में कमजोर रूप से अभिसरित होती है
3. स्पष्ट निर्भरता संबंध: अभिसरण दर पुनरावृत्तियों की संख्या K, स्थिति-क्रिया स्पेस के आकार |S||A|, छूट कारक γ और अन्वेषण गुणवत्ता ρ पर निर्भरता को स्पष्ट रूप से प्रतिबिंबित करता है
4. तकनीकी नवाचार: गैर-रैखिकता, मार्कोवियन शोर और गैर-चिकनी ऑपरेटर द्वारा लाई गई विश्लेषणात्मक चुनौतियों को हल किया गया है

विधि विवरण

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

अनंत क्षितिज छूट मार्कोव निर्णय प्रक्रिया (MDP) $M = \langle S, A, P, r, \gamma \rangle$ पर विचार करें, जहां:

• $S$: स्थिति समुच्चय
• $A$: क्रिया समुच्चय
• $P: S \times A \rightarrow \Delta_S$: संक्रमण संभाव्यता फ़ंक्शन
• $\gamma \in [0,1)$: छूट कारक

लक्ष्य इष्टतम Q फ़ंक्शन $Q^* = \max_\pi Q^\pi$ सीखना है।

असिंक्रोनस Q-लर्निंग एल्गोरिदम

असिंक्रोनस Q-लर्निंग Q फ़ंक्शन अनुमानक $Q_k$ को बनाए रखता है, अपडेट नियम है: $Q_{k+1} = Q_k + \alpha_k(F_k - Q_k)$

जहां:

• $F_k = F(Q_k, y_k)$, $y_k = (s_k, a_k, s_{k+1})$
• $[F(Q_k, s_k, a_k, s_{k+1})](s,a) = \mathbf{1}_{\{(s_k,a_k)=(s,a)\}}\Gamma(Q_k, s_k, a_k, s_{k+1}) + Q_k(s,a)$
• $\Gamma(Q_k, s_k, a_k, s_{k+1}) = r_k(s_k, a_k) + \gamma\max_a Q_k(s_{k+1}, a) - Q_k(s_k, a_k)$

मुख्य मान्यताएं

मान्यता 1: एक इष्टतम नीति $\pi^*$ मौजूद है जैसे कि $Q \in \mathbb{R}^{|S|\times|A|}$ के लिए: $\|(P^\pi - P^{\pi^*})(Q-Q^*)\|_\infty \leq L\|Q-Q^*\|_2^\infty$

मान्यता 2: $\{y_k\}_{k \geq 0}$ एक अपरिवर्तनीय और अ-आवधिक परिमित-स्थिति मार्कोव श्रृंखला है।

चरण-लंबाई चयन

बहुपद चरण-लंबाई $\alpha_k = \alpha(k+b)^{-\beta}$ चुनें, जहां $\alpha, b > 0$, $\beta \in (0.5, 1)$।

इस चयन के कारण:

1. Polyak-Juditsky औसत योजना की मुख्य शर्तों को पूरा करता है
2. स्थिर चरण-लंबाई शर्तें (i) और (iii) का उल्लंघन करती है, रैखिक चरण-लंबाई शर्त (ii) का उल्लंघन करती है
3. बहुपद चरण-लंबाई सभी आवश्यक शर्तों को पूरा करती है

मुख्य सैद्धांतिक परिणाम

गैर-स्पर्शोन्मुख केंद्रीय सीमा प्रमेय

प्रमेय 4: मान्यताओं 1 और 2 के तहत: $W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, \tilde{N}\right) \leq \frac{(|S||A|)^{1/2}}{\rho(1-\gamma)^2K^{1/2}} \cdot \tilde{O}\left((\rho(1-\gamma))^{\frac{\beta-2}{1-\beta}} + K^{\beta/2}\rho^{-1}(1-\gamma)^{-1} + K^{1-\beta} + K^{\frac{1-\beta}{2}}\rho^{-1-\beta}(1-\gamma)^{-\beta}\right)$

जहां $\Delta_k = Q_k - Q^*$, $\tilde{N} = (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)$।

परिणाम 5: जब $\beta = 2/3$ हो, तो अभिसरण दर सरल हो जाता है: $W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)\right) \leq \tilde{O}\left(\frac{(|S||A|)^{1/2}}{K^{1/6}\rho^2(1-\gamma)^3}\right)$

कार्यात्मक केंद्रीय सीमा प्रमेय

प्रमेय 6: प्रमेय 4 की सेटिंग में, आंशिक योग प्रक्रिया $\Phi_K(\zeta) = K^{-1/2}\sum_{k=1}^{\lfloor\zeta K\rfloor}\Delta_k$ $D[0,1]$ पर $(A^{-1}\Sigma A^{-\top})^{1/2}B(\cdot)$ में कमजोर रूप से अभिसरित होती है, जहां $B(\cdot)$ एक मानक ब्राउनियन गति है।

तकनीकी नवाचार और प्रमाण रणनीति

मुख्य तकनीकी चुनौतियां

1. गैर-रैखिकता: Q-लर्निंग एक गैर-रैखिक SA है, जो रैखिक SA से अधिक जटिल है
2. मार्कोवियन शोर: असिंक्रोनस अपडेट गैर-स्वतंत्र समान वितरण वाले मार्कोवियन शोर को प्रस्तुत करता है
3. गैर-चिकनी ऑपरेटर: असिंक्रोनस Q-लर्निंग में अनुभवजन्य Bellman ऑपरेटर गैर-चिकना है

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

1. ऊपरी और निचली सीमा तकनीक: ऊपरी सीमा अनुक्रम $\Delta_k^{\uparrow}$ और निचली सीमा अनुक्रम $\Delta_k^{\downarrow}$ को प्रस्तुत करके, निचोड़ प्रमेय का उपयोग करते हुए
2. पद विघटन: $\sum_{k=1}^K \Delta_k$ को छह पदों में विघटित करें:
   • पद (1): प्रारंभिक त्रुटि पद
   • पद (2): गैर-रैखिक त्रुटि पद
   • पद (3): मार्कोवियन शोर पद
   • पद (4-5): उच्च-क्रम सुधार पद
   • पद (6): मार्टिंगेल अंतर अनुक्रम
3. Poisson समीकरण तकनीक: मार्कोवियन शोर को मार्टिंगेल अंतर अनुक्रम में रूपांतरित करना
4. मार्टिंगेल केंद्रीय सीमा प्रमेय: Srikant (2024) के गैर-स्पर्शोन्मुख मार्टिंगेल CLT को लागू करना

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

स्टोकेस्टिक सन्निकटन सिद्धांत

• Polyak, B. T. और Juditsky, A. B. (1992): औसत द्वारा स्टोकेस्टिक सन्निकटन का त्वरण
• Anastasiou आदि (2019): Polyak-Ruppert औसत SGD का गैर-स्पर्शोन्मुख CLT
• Mou आदि (2020): रैखिक SA का गैर-स्पर्शोन्मुख CLT

सुदृढ़ शिक्षा में CLT

• Xie और Zhang (2022), Li आदि (2023): सिंक्रोनस Q-लर्निंग का कार्यात्मक CLT
• Zhang और Xie (2024): स्थिर चरण-लंबाई असिंक्रोनस Q-लर्निंग का कार्यात्मक CLT
• Srikant (2024), Samsonov आदि (2024): TD लर्निंग का गैर-स्पर्शोन्मुख CLT

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

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

1. Q-लर्निंग के लिए पहला गैर-स्पर्शोन्मुख CLT स्थापित किया गया है, अभिसरण दर समस्या के मापदंडों पर स्पष्ट रूप से निर्भर करता है
2. असिंक्रोनस Q-लर्निंग आंशिक योग प्रक्रिया के कमजोर अभिसरण को साबित किया गया है
3. सुदृढ़ शिक्षा में अनिश्चितता परिमाणीकरण के लिए सैद्धांतिक आधार प्रदान किया गया है

सीमाएं

1. मजबूत Lipschitz मान्यता की आवश्यकता है (मान्यता 1)
2. केवल परिमित स्थिति-क्रिया स्पेस पर विचार करता है
3. अभिसरण दर इष्टतम नहीं हो सकती है

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

1. अभिसरण दर में सुधार
2. 1-Wasserstein दूरी के अलावा अन्य मेट्रिक्स तक विस्तार
3. कार्यात्मक सन्निकटन सेटिंग पर विचार करना

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

लाभ

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

कमियां

1. मजबूत मान्यताएं: Lipschitz मान्यता व्यावहारिक रूप से सत्यापित करना मुश्किल हो सकता है
2. अभिसरण दर: $K^{-1/6}$ की अभिसरण दर अपेक्षाकृत धीमी है
3. परिमित स्थिति: निरंतर स्थिति स्पेस या कार्यात्मक सन्निकटन पर विचार नहीं किया गया है

प्रभाव

1. सैद्धांतिक मूल्य: Q-लर्निंग सैद्धांतिक विश्लेषण के लिए नए उपकरण और दृष्टिकोण प्रदान करता है
2. व्यावहारिक महत्व: सुदृढ़ शिक्षा एल्गोरिदम के अनिश्चितता परिमाणीकरण के लिए सैद्धांतिक आधार स्थापित करता है
3. पद्धति: प्रमाण तकनीक अन्य गैर-रैखिक SA समस्याओं तक सामान्यीकृत की जा सकती है

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

1. तालिका-आधारित सुदृढ़ शिक्षा समस्याओं का सैद्धांतिक विश्लेषण
2. असिंक्रोनस अपडेट एल्गोरिदम के अभिसरण अनुसंधान
3. सुदृढ़ शिक्षा में सांख्यिकीय अनुमान और विश्वास अंतराल निर्माण

संदर्भ

• Polyak, B. T. और Juditsky, A. B. (1992). औसत द्वारा स्टोकेस्टिक सन्निकटन का त्वरण।
• Xie, C. और Zhang, Z. (2022). औसत स्टोकेस्टिक सन्निकटन में एक सांख्यिकीय ऑनलाइन अनुमान दृष्टिकोण।
• Zhang, Y. और Xie, Q. (2024). स्थिर चरण-लंबाई Q-लर्निंग: वितरणात्मक अभिसरण, पूर्वाग्रह और एक्सट्रापोलेशन।