📊 statistics

On the Complexity of Offline Reinforcement Learning with $Q^\star$ -Approximation and Partial Coverage

यह शोध पत्र एक सूचनात्मक निचली सीमा (information-theoretic lower bound) स्थापित करके आंशिक कवरेज के तहत सैंपल-कुशल ऑफलाइन आरएल (RL) के लिए $Q^\star$ -रियलाइज़ेबिलिटी और बेलमैन पूर्णता (Bell-man completeness) की पर्याप्तता का नकारात्मक उत्तर प्रदान करता है, और एक सामान्य निर्णय-अनुमान ढांचे (decision-estimation framework) को प्रस्तुत करता है जो जटिलता को निर्णय और मूल्य अनुमान घटकों में विभाजित करके मौजूदा परिणामों को एकीकृत और बेहतर बनाता है।

मूल लेखक: Haolin Liu, Braham Snyder, Chen-Yu Wei

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

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

CC BY 4.0

मूल लेखक: Haolin Liu, Braham Snyder, Chen-Yu Wei

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

यहाँ इस शोध पत्र "On the Complexity of Offline Reinforcement Learning with Q⋆-Approximation and Partial Coverage" का सरल भाषा और उपमाओं (analogies) के साथ हिंदी अनुवाद दिया गया है।

बड़ी तस्वीर: एक लाइब्रेरी से सीखना, न कि खेल के मैदान से

कल्पना कीजिए कि आप एक जटिल वीडियो गेम खेलना सीखना चाहते हैं, लेकिन आपको खुद इसे खेलने की अनुमति नहीं है। इसके बजाय, आपको अन्य लोगों द्वारा गेम खेलते हुए दिखाए गए वीडियो की एक विशाल लाइब्रेरी दी जाती है। इसे ऑफलाइन रिइन्फोर्समेंट लर्निंग (Offline Reinforcement Learning - RL) कहा जाता है।

समस्या यह है कि लाइब्रेरी में मौजूद वीडियो अधूरे हैं। वे गेम की हर संभव चाल या हर संभव स्थिति को नहीं दिखाते हैं। इसे पार्शियल कवरेज (Partial Coverage) कहा जाता है। आपको केवल उन क्लिप्स के आधार पर सबसे अच्छी रणनीति तय करनी होगी जो आपके पास उपलब्ध हैं, बिना वास्तविक गेम में अपने विचारों का परीक्षण किए।

मौजूदा अधिकांश सिद्धांतों ने माना था कि यदि आपके पास गेम के मूल्य (प्रत्येक चाल कितनी अच्छी है) का एक पर्याप्त अच्छा "मानचित्र" (map) है, तो आप सबसे अच्छी रणनीति निकाल सकते हैं। यह शोध पत्र तर्क देता है कि यह धारणा गलत है। केवल चालों के मूल्य को जानना ही पर्याप्त नहीं है, यदि आपने गेम को पर्याप्त रूप से नहीं देखा है ताकि यह जान सकें कि कौन सी चालें चुनना सुरक्षित है।

मुख्य समस्या: "सुरक्षित दांव" की दुविधा (The "Safe Bet" Dilemma)

लेखक एक विशिष्ट प्रश्न पूछते हैं: यदि हमारे पास सर्वोत्तम संभावित स्कोर का एक सटीक मानचित्र (Q⋆-realizability) है और हमारा मानचित्र गणितीय रूप से सुसंगत (Bellman completeness) है, तो क्या हम अभी भी अधूरे डेटा से कुशलतापूर्वक सीख सकते हैं?

उनका उत्तर है: नहीं।

वे इसे एक गणितीय "लोअर बाउंड" (असंभवता का प्रमाण) के साथ सिद्ध करते हैं। यहाँ इसकी उपमा दी गई है:

कल्पना कीजिए कि आप एक अंधेरे कमरे में दो दरवाजों के साथ हैं, दरवाजा A और दरवाजा B।

दरवाजा A के पीछे $100 का खजाना है।
दरवाजा B के पीछे एक जाल है जिसमें आपको $100 का नुकसान होगा।
हालाँकि, आपके पास कमरे की केवल एक धुंधली फोटो है। फोटो दिखाती है कि एक दरवाजा खजाने की ओर ले जाता है, लेकिन यह स्पष्ट रूप से नहीं दिखाती कि कौन सा।
आप यह भी जानते हैं कि यदि आपने गलत दरवाजा चुना, तो आप सब कुछ खो देंगे।

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

समाधान: समस्या को दो भागों में विभाजित करना

चूंकि सोचने का पुराना तरीका काम नहीं आया, इसलिए लेखकों ने एक नया ढांचा तैयार किया। उन्होंने सीखने की कठिनाई को दो अलग-अलग चुनौतियों में विभाजित किया:

एस्टिमेशन एरर (अनुमान की त्रुटि - "धुंधली फोटो" वाली समस्या): हम सीमित डेटा के आधार पर प्रत्येक चाल के मूल्य का अनुमान कितनी अच्छी तरह लगा सकते हैं?
डिसीजन कॉम्प्लेक्सिटी (निर्णय की जटिलता - "सुरक्षित दांव" वाली समस्या): हमारे धुंधले अनुमानों को देखते हुए, एक ऐसी पॉलिसी (खेलने के नियमों का एक सेट) चुनना कितना कठिन है जो विनाशकारी रूप से विफल न हो?

वे अपने नए टूल को Ordec (Offline Robust Decision-Estimation Coefficient) कहते हैं। Ordec को एक "रिस्क मैनेजर" (जोखिम प्रबंधक) के रूप में समझें। यह केवल उच्चतम संभव स्कोर की तलाश नहीं करता; यह उस रणनीति की तलाश करता है जो धुंधले डेटा द्वारा दर्शाए गए सबसे खराब मामले (worst-case scenario) में भी अच्छा प्रदर्शन करे।

यह कैसे काम करता है: "पेसमिस्टिक" (निराशावादी) खेल

लेखक एक एल्गोरिदम प्रस्तावित करते हैं जिसे E2D.OR (Estimation-to-Decision) कहा जाता है। यह सरल अंग्रेजी में इस प्रकार काम करता है:

कॉन्फिडेंस सेट (Confidence Set): सबसे पहले, एल्गोरिदम उन सभी संभावित "मानचित्रों" को देखता है जो उन वीडियो क्लिप्स के अनुरूप हैं जिन्हें उसने देखा है। यह "संभावित दुनियाओं" की एक सूची बनाता है।
खेल (The Game): एल्गोरिदम एक "एडवर्सरी" (विरोधी) के खिलाफ एक मानसिक खेल खेलता है।
- एडवर्सरी का लक्ष्य सीखने वाले को चकमा देने के लिए उपलब्ध संभावित दुनियाओं की सूची में से सबसे भ्रमित करने वाली दुनिया चुनना है।
- लर्नर (सीखने वाला) ऐसी रणनीति चुनने की कोशिश करता है जो उन सभी भ्रमित करने वाली दुनियाओं में अच्छा काम करे।
पेनल्टी (दंड): यदि सूची में कोई ऐसी दुनिया है जिसके लिए लर्नर को ऐसी चालें चलनी पड़ती हैं जो वीडियो क्लिप्स में कभी नहीं देखी गईं, तो एडवर्सरी को दंडित किया जाता है। यह एल्गोरिदम को असंभव परिदृश्यों के बारे में चिंता करने से रोकता है।

यह दृष्टिकोण पुराने तरीकों से अलग है जो केवल "सबसे खराब मामले" वाले मानचित्र को चुनते थे और उसके विरुद्ध अनुकूलतम रूप से खेलते थे। लेखक दिखाते हैं कि उनकी नई विधि अधिक मजबूत है और सुरक्षित निर्णय लेती है।

पिछले कार्यों की तुलना में प्रमुख सुधार

यह शोध पत्र पिछले शोधों की तुलना में कई सुधारों का दावा करता है:

बेहतर सैंपल एफिशिएंसी (नमूना दक्षता): पिछले तरीकों को सुरक्षित रूप से सीखने के लिए भारी मात्रा में डेटा ( $\epsilon^{-4}$ के साथ स्केल होता हुआ) की आवश्यकता थी। इस नए तरीके में बहुत कम डेटा ( $\epsilon^{-2}$ के साथ स्केल होता हुआ) की आवश्यकता है। सरल शब्दों में, आपको वही सबक सीखने के लिए कम वीडियो क्लिप्स की आवश्यकता होती है।
"वैल्यू गैप्स" की आवश्यकता नहीं: पुराने तरीकों ने माना था कि सबसे अच्छी चाल दूसरी सबसे अच्छी चाल से स्पष्ट रूप से बेहतर (एक बड़ा "गैप") है। यह नया तरीका तब भी काम करता है जब सबसे अच्छी चाल अन्य विकल्पों से केवल थोड़ी सी बेहतर हो, जो जटिल खेलों में अधिक यथार्थवादी है।
निरंतर क्रियाओं (Continuous Actions) के लिए उपयुक्त: यह उन खेलों को संभालता है जहाँ आप सुचारू रूप से हिल सकते हैं (जैसे कार चलाना) न कि केवल डिस्क्रीट बटन (जैसे बाएँ/दाएँ) दबा सकते हैं।
CQL का पहला विश्लेषण: यह शोध पत्र पहला सैद्धांतिक प्रमाण प्रदान करता है कि कन्ज़र्वेटिव Q-लर्निंग (CQL), जो एक लोकप्रिय व्यावहारिक एल्गोरिदम है, इन स्थितियों में अच्छी तरह से काम करता है। CQL एक वास्तविक दुनिया का एल्गोरिदम है जिसका उपयोग रोबोटिक्स और AI में किया जाता है, और यह शोध पत्र अंततः गणितीय रूप से बताता है कि यह क्यों काम करता है।

सारांश

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

संक्षेप में, यह शोध पत्र कहता है, "केवल सर्वोत्तम स्कोर का अनुमान लगाने की कोशिश न करें। ऐसी रणनीति खोजने का प्रयास करें जो आपके अधूरे डेटा की अनिश्चितता के विरुद्ध मजबूत (robust) हो।"

तकनीकी सारांश: $Q^\star$ -अनुमान और आंशिक कवरेज के साथ ऑफलाइन सुदृढीकरण शिक्षण (Reinforcement Learning) की जटिलता पर

समस्या का परिवेश और प्रेरणा
यह शोध पत्र दो विशिष्ट स्थितियों के तहत ऑफलाइन सुदृढीकरण शिक्षण (RL) के सैद्धांतिक आधारों को संबोधित करता है: $Q^\star$ -अनुमान (जहाँ अनुकूलतम Q-फंक्शन एक फलन वर्ग (function class) के भीतर यथार्थसाध्य है) और आंशिक कवरेज (जहाँ ऑफलाइन डेटासेट संपूर्ण अवस्था-क्रिया (state-action) स्थान को कवर नहीं करता है)। जबकि $Q^\pi$ -यथार्थसाध्यता (realizability) का अच्छी तरह से लक्षण वर्णन किया जा चुका है, $Q^\star$ -यथार्थसाध्यता और आंशिक कवरेज के तहत ऑफलाइन RL में नमूना दक्षता (sample efficiency) एक खुला प्रश्न बना हुआ है। विशेष रूप से, यह अज्ञात है कि क्या $Q^\star$ -यथार्थसाध्यता और बेलमैन पूर्णता (Bellman completeness) का संयोजन इस शासन (regime) में नमूना-कुशल शिक्षण के लिए पर्याप्त है। लेखक इसे सूचना-सैद्धांतिक सीमाओं को स्थापित करके और एक एकीकृत ढांचा प्रदान करके हल करने का लक्ष्य रखते हैं जो सीखने योग्य होने के लिए आवश्यक संरचनात्मक स्थितियों की पहचान करता है।

कार्यप्रणाली: निर्णय-अनुमान अपघटन (Decision-Estimation Decomposition)
मुख्य पद्धतिगत योगदान ऑफलाइन RL की जटिलता का दो अलग-अलग घटकों में अपघटन है: निर्णय जटिलता (decision complexity) और मूल्य अनुमान त्रुटि (value estimation error)। यह ढांचा ऑनलाइन RL में उपयोग किए जाने वाले 'डिसीजन-एस्टिमेशन कोएफिशिएंट' (DEC) से प्रेरित है लेकिन इसे ऑफलाइन सेटिंग के लिए अनुकूलित किया गया है।

कॉन्फिडेंस सेट निर्माण: ऑफलाइन डेटा एक संभावित अनुकूलतम Q-फंक्शन्स का कॉन्फिडेंस सेट $\mathcal{F}_{\text{conf}}$ प्रेरित करता है। यह सेट संभावित मॉडलों का एक सेट $\mathcal{M}_{\text{conf}} = \{M : Q^\star_M \in \mathcal{F}_{\text{conf}}\}$ प्रेरित करता है।
ऑफलाइन रोबस्ट DEC (Ordec): लेखक एक नया जटिलता माप, $\text{Ordec}$ , परिभाषित करते हैं जो कॉन्फिडेंस सेट से रोबस्ट निर्णय लेने की कठिनाई को मापता है। इसे एक नीति खिलाड़ी (policy player) और एक मॉडल खिलाड़ी (model player) के बीच मिनीमैक्स खेल के रूप में परिभाषित किया गया है:
$\text{Ordec}^{\text{OD}}_\gamma(\mathcal{F}_{\text{conf}}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{\text{conf}}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in \mathcal{F}_{\text{conf}}} D_{\pi_M}(f \| M) \right]$
यहाँ, नीति खिलाड़ी उप-इष्टतमता (suboptimality) को कम करने के लिए एक मिश्रण नीति $\rho$ चुनता है, जबकि मॉडल खिलाड़ी कॉन्फिडेंस सेट से एक मॉडल $M$ चुनता है ताकि अंतराल (gap) को अधिकतम किया जा सके, जिसे एक विसंगति पद (discrepancy term) $D$ द्वारा दंडित किया जाता है जो सांख्यिकीय असंगतता को मापता है। महत्वपूर्ण रूप से, विसंगति को उम्मीदवार मॉडल की अपनी अनुकूलतम नीति $\pi_M$ के तहत मापा जाता है, न कि शिक्षार्थी की नीति के तहत, ताकि आंशिक कवरेज को ध्यान में रखा जा सके।
एल्गोरिदम (E2D.OR): प्रस्तावित एल्गोरिदम, ऑफलाइन रोबस्ट एस्टिमेशन-टू-डिसीजन (E2D.OR), Ordec द्वारा परिभाषित मिनीमैक्स समस्या को हल करता है और एक मिश्रण नीति $\hat{\rho}$ आउटपुट करता है।

प्रमुख योगदान और परिणाम

सूचना-सैद्धांतिक निचली सीमा (Lower Bound):
लेखक सिद्ध करते हैं कि $Q^\star$ -यथार्थसाध्यता, आंशिक कवरेज और बेलमैन पूर्णता, $\epsilon$ -इष्टतमता प्राप्त करने के लिए नमूना-कुशल ऑफलाइन RL के लिए पर्याप्त नहीं हैं। वे मॉडलों का एक परिवार निर्मित करते हैं जहाँ ये धारणाएँ लागू होती हैं, फिर भी किसी भी एल्गोरिदम को $\epsilon$ -इष्टतमता प्राप्त करने के लिए $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$ नमूनों की आवश्यकता होती है, जहाँ $\Delta$ मान अंतराल (value gap) है। यह दर्शाता है कि कठिनाई केवल $Q^\star$ के अनुमान से नहीं, बल्कि अस्पष्टता के तहत निर्णय लेने की प्रक्रिया से उत्पन्न होती है।
अपघटन के माध्यम से ऊपरी सीमा (Upper Bound):
एक शोध पत्र यह स्थापित करता है कि E2D.OR एल्गोरिदम की उप-इष्टतमता निर्णय जटिलता (Ordec) और अनुमान त्रुटि के योग द्वारा सीमित है:
$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq \text{Ordec}^{\text{OD}}_\gamma(\mathcal{F}_{\text{conf}}) + \gamma \max_{f \in \mathcal{F}_{\text{conf}}} D_{\pi^\star}(f \| M^\star)$
यह मॉड्यूलर अपघटन लेखकों को प्रत्येक पद को अलग-अलग नियंत्रित करने वाली स्थितियों का विश्लेषण करने की अनुमति देता है।
निर्णय जटिलता को बांधना (Bounding Decision Complexity):
लेखक तीन स्थितियाँ पहचानते हैं जहाँ Ordec सीमित है:
- वैल्यू गैप (Value Gap): अनरेगुलराइज्ड मामले में, यदि वास्तविक Q-फंक्शन में एक वैल्यू गैप $\Delta_{Q^\star}$ है, तो Ordec $\Delta_{Q^\star}^{-2}$ के साथ स्केल करता है। यह पूर्व कार्य (चेन और जियांग, 2022) की तुलना में सुधार करता है क्योंकि यह पूर्व ज्ञान या ऑनलाइन इंटरेक्शन की आवश्यकता के बिना वास्तविक अंतराल के अनुकूल होता है।
- कर्वेड डिसीजन बाउंड्री (Curved Decision Boundary): वक्र निर्णय सीमा वाले लीनियर फंक्शन एप्रोक्सिमेशन के लिए, Ordec सख्त वैल्यू गैप के बिना भी सीमित है, जो निरंतर क्रिया स्थानों (continuous action spaces) में गैप धारणाओं की व्यावहारिकता संबंधी चिंताओं को संबोधित करता है।
- रेगुलराइजेशन (Regularization): रेगुलराइज्ड MDPs (जैसे, KL रेगुलराइजेशन के साथ) में, Ordec रेगुलराइज़र की स्ट्रॉन्ग कॉनवेक्सिटी के कारण सीमित है। यह आंशिक कवरेज के तहत सॉफ्ट Q-लर्निंग के लिए पहला $\epsilon^{-2}$ नमूना जटिलता सीमा प्रदान करता है, जो उहेरा एट अल. (2023) की $\epsilon^{-4}$ सीमा में सुधार करता है।
अनुमान त्रुटि को बांधना (Bounding Estimation Error):
लेखक अनुमान त्रुटि पद को नियंत्रित करने के लिए स्थितियाँ प्रदान करते हैं:
- बेलमैन पूर्णता (Bellman Completeness): मानक बेलमैन पूर्णता के तहत, अनुमान त्रुटि नियंत्रित रहती है, जो सामान्य फंक्शन एप्रोक्सिमेशन सेटिंग में कंजर्वेटिव Q-लर्निंग (CQL) के लिए पहला नमूना जटिलता विश्लेषण प्रदान करती है।
- वेट रियलाइज़ेबिलिटी (Weight Realizability): उन परिणामों को पुनः प्राप्त करता है जहाँ डेंसिटी रेश्यो यथार्थसाध्य होते हैं।
- लो बेलमैन रैंक (Low Bellman Rank): यह शोध पत्र लो-बेलमैन-रैंक MDPs के लिए ऑफलाइन सीखने की क्षमता का पहला लक्षण वर्णन प्रदान करता है। यह दिखाता है कि मानक कवरेज धारणाएँ अपर्याप्त हैं; इसके बजाय, कुशल अनुमान के लिए डबल पॉलिसी सैंपलिंग और पॉलिसी फीचर कवरेज आवश्यक और पर्याप्त स्थितियाँ हैं।

महत्व और दावे
यह शोध पत्र $Q^\star$ -अनुमान और आंशिक कवरेज के तहत ऑफलाइन RL की व्यापक समझ प्रदान करने का दावा करता है। Ordec ढांचे को पेश करके, यह मौजूदा परिणामों को एकीकृत और बेहतर बनाता है, विशेष रूप से:

यह सिद्ध करके कि बेलमैन पूर्णता अकेले पर्याप्त नहीं है, पर्याप्तता के खुले प्रश्न को हल करता है।
रेगुलराइज्ड सेटिंग्स के लिए नमूना जटिलता सीमाओं में सुधार करता है ( $\epsilon^{-4}$ से $\epsilon^{-2}$ तक)।
वैल्यू-गैप सेटिंग्स में ऑनलाइन इंटरेक्शन या ज्ञात गैप मानों की आवश्यकता को हटा देता है।
सीखने की क्षमता को नए क्षेत्रों, जैसे कि कर्वेड डिसीजन बाउंड्री और विशिष्ट डेटा धारणाओं के साथ लो-बेलमैन-रैंक MDPs तक विस्तारित करता है।
सामान्य फंक्शन एप्रोक्सिमेशन के तहत CQL का पहला सैद्धांतिक विश्लेषण प्रदान करता है।

लेखक सीमाओं का उल्लेख करते हैं, जिसमें मिनीमैक्स Ordec ऑब्जेक्टिव को सटीक रूप से हल करने की कम्प्यूटेशनल कठिनाई और Ordec जटिलता माप के लिए मिलान करने वाली निचली सीमा (lower bound) का अभाव शामिल है।