🤖 AI

Auto-exploration for online reinforcement learning

यह शोधपत्र ऑनलाइन सुदृढीकरण शिक्षण (reinforcement learning) के लिए एक पैरामीटर-मुक्त ऑटो-एक्सप्लोरेशन फ्रेमवर्क प्रस्तुत करता है जो पॉलिसी मिरर डिसेंट (policy mirror descent) में अन्वेषण (exploration) को एकीकृत करके टैबुलर और लीनियर फंक्शन एप्रोक्सिमेशन दोनों सेटिंग्स में एल्गोरिदम-स्वतंत्र $O(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी प्राप्त करता है।

मूल लेखक: Caleb Ju, Guanghui Lan

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

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

CC BY 4.0

मूल लेखक: Caleb Ju, Guanghui Lan

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

यहाँ "Auto-exploration for online reinforcement learning" का सरल भाषा और रचनात्मक उपमाओं (analogies) का उपयोग करते हुए विवरण दिया गया है।

मुख्य समस्या: "खोया हुआ पर्यटक" दुविधा (The "Lost Tourist" Dilemma)

कल्पना कीजिए कि आप एक पर्यटक हैं जिसे बिना किसी मानचित्र के एक विशाल, अपरिचित शहर (Environment) में छोड़ दिया गया है। आपका लक्ष्य शहर के सबसे अच्छे रेस्टोरेंट (Optimal Policy) को खोजना है, जिसके लिए आप अलग-अलग जगहों पर घूमकर और उन्हें आजमाकर यह काम करेंगे।

Reinforcement Learning (RL) में, इसे Exploration-Exploitation Dilemma कहा जाता है:

Exploitation (दोहन): आप उसी रेस्टोरेंट में बार-बार जाते हैं जिसे आप पहले से जानते हैं कि वह अच्छा है।
Exploration (अन्वेषण): आप नए मोहल्लों में घूमते हैं ताकि देख सकें कि क्या वहां इससे भी बेहतर कुछ मौजूद है।

समस्या यह है कि यदि आप केवल 'exploit' करते हैं, तो आप सबसे अच्छे रेस्टोरेंट को मिस कर सकते हैं क्योंकि आपने कभी उस हिस्से की यात्रा ही नहीं की। यदि आप बहुत अधिक 'explore' करते हैं, तो आप खराब खाना खाकर अपना समय बर्बाद कर देते हैं।

अधिकांश मौजूदा एल्गोरिदम यह मान लेते हैं कि आपके पास एक "जादुई दिशा-सूचक यंत्र" (magic compass) है जो आपको ठीक-ठीक बताता है कि प्रत्येक मोहल्ले में कितनी देर घूमना है और फिर आगे बढ़ना है। यह दिशा-सूचक यंत्र शहर के लेआउट (Mixing Time और Stationary Distribution) को पहले से जानने पर निर्भर करता है। लेकिन वास्तविक जीवन में, आपके पास ऐसा कोई नक्शा नहीं होता। आप बस अनुमान लगा रहे होते हैं। यदि आपका अनुमान गलत निकलता है, तो या तो आप एक बंद गली में फंस सकते हैं या वर्षों तक बिना किसी उद्देश्य के भटकते रह सकते हैं।

समाधान: "Auto-Exploration"

लेखक एक नई विधि प्रस्तावित करते हैं जिसे Auto-Exploration कहा जाता है। एक पूर्व-निर्धारित मानचित्र या निश्चित शेड्यूल की आवश्यकता के बजाय, यह एल्गोरिदम चलते-फिरते अन्वेषण करना सीखता है। यह स्वचालित रूप से समझ जाता है कि उसने किसी विशिष्ट क्षेत्र को पर्याप्त रूप से देख लिया है और उसे कब और अधिक खोजने की आवश्यकता है।

इसे इस प्रकार समझें: एक सख्त यात्रा कार्यक्रम वाले पर्यटक के बजाय ("10 मिनट चलो, फिर बाएं मुड़ो"), इस पर्यटक के पास एक स्मार्ट वॉच है। वॉच ट्रैक करती है कि एक नया लैंडमार्क खोजने में उसे कितना समय लगता है। यदि किसी नई गली को खोजने में बहुत समय लगता है, तो वॉच जान जाती है, "ठीक है, यह क्षेत्र कठिन है, मुझे और तलाश जारी रखनी होगी।" यदि वह चीजें जल्दी ढूंढ लेता है, तो वह जान जाता है, "मैंने यहाँ पर्याप्त देख लिया है, अब आगे बढ़ते हैं।"

यह कैसे काम करता है: दो मुख्य तकनीकें

पेपर इस समाधान को दो सेटिंग्स में प्रस्तुत करता है: एक जहाँ शहर छोटा और पूरी तरह से मैप किया गया है (Tabular), और एक जहाँ शहर विशाल है और आपके पास केवल रफ स्केच हैं (Function Approximation)।

1. छोटा शहर (Tabular Setting)

सीमित गलियों वाले एक छोटे शहर में, लेखक Dynamic Exploration Time नामक तकनीक का उपयोग करते हैं।

पुराना तरीका: पिछले तरीकों के लिए आपको "mixing time" जानने की आवश्यकता थी—अर्थात, एक रैंडम वॉकर को शहर के हर हिस्से को समान रूप से देखने में कितना समय लगता है। यह संख्या अज्ञात होती है और बहुत बड़ी हो सकती है।
नया तरीका: एल्गोरिदम एक Hitting Time का उपयोग करता है। यह बस यह गिनता है कि किसी विशिष्ट स्थिति (गली के कोने) तक पहुँचने में कितने कदम लगे।
उपमा: कल्पना कीजिए कि आप बगीचे में एक विशेष दुर्लभ फूल खोजने की कोशिश कर रहे हैं। "मैं 5 घंटे खोजूँगा" जैसा अनुमान लगाने के बजाय, आप कहते हैं, "मैं तब तक खोजता रहूँगा जब तक मुझे फूल नहीं मिल जाता, और साथ ही थोड़ा अतिरिक्त बफर समय भी रखूँगा।" एल्गोरिदम इस "बफर समय" की गणना इस आधार पर करता है कि वह फूल ढूंढना कितना कठिन था। यह विधि parameter-free बनाती है—आपको अज्ञात शहर के डेटा के आधार पर नॉब्स (knobs) को ट्यून करने की आवश्यकता नहीं है।

2. विशाल शहर (Function Approximation)

एक विशाल शहर में, आप हर गली को याद नहीं कर सकते। आप सामान्यीकरण (generalize) करने के लिए एक सरलीकृत मानचित्र (न्यूरल नेटवर्क या लीनियर मॉडल) का उपयोग करते हैं।

चुनौती: सरलीकृत मानचित्र का उपयोग करते समय, त्रुटियाँ आ सकती हैं। यदि आप केवल अपने वर्तमान सर्वोत्तम अनुमान के आधार पर अन्वेषण करते हैं, तो आप एक "लोकल ऑप्टिमम" (एक अच्छा रेस्टोरेंट, लेकिन सबसे अच्छा नहीं) में फंस सकते हैं क्योंकि आपका मानचित्र थोड़ा गलत हो सकता है।
नया तरीका: लेखक एक Conditional Temporal Difference (CTD) विधि पेश करते हैं। वे एक विशेष सैंपलिंग रणनीति बनाते जो यह सुनिश्चित करती है कि एल्गोरिदम ऐसे तरीके से राज्यों (states) का दौरा करे जिससे पूरे शहर का कवरेज हो सके, भले ही मानचित्र अपूर्ण हो।
उपमा: कल्पना कीजिए कि आप एक धुंधले मानचित्र का उपयोग कर रहे हैं। यह सुनिश्चित करने के लिए कि आप सबसे अच्छी जगह न चूकें, आप कभी-कभी खुद को एक विशिष्ट "एंकर पॉइंट" (जैसे शहर का केंद्र) तक जाने के लिए मजबूर करते हैं और फिर वहां से बाहर की ओर अन्वेषण करते हैं। यह "एंकर" यह सुनिश्चित करता है कि आप अपने धुंधले मानचित्र के ब्लाइंड स्पॉट में न खो जाएं। एल्गोरिदम स्वचालित रूप से इस आधार पर समायोजित करता है कि उसे कितनी बार उस एंकर पर वापस आना है।

यह बेहतर क्यों है?

"मैजिक नंबर्स" की आवश्यकता नहीं: पिछले तरीकों को "mixing rate" या "stationary distribution" जैसे पैरामीटर डालने की आवश्यकता थी, जो अज्ञात होते हैं। यदि आपने इनका गलत अनुमान लगाया, तो एल्गोरिदम विफल हो गया। यह नई विधि parameter-free है। यह एकत्र किए गए डेटा के आधार पर आवश्यक अन्वेषण समय को स्वतः ही समझ लेती है।
तेज़ और अधिक कुशल: पेपर सिद्ध करता है कि यह विधि $O(\epsilon^{-2})$ के सैंपल कॉम्प्लेक्सिटी के साथ उच्च स्तर की सटीकता ( $\epsilon$ -accuracy) प्राप्त करती है। सरल शब्दों में, इसका मतलब है कि यह पिछले तरीकों की तुलना में बहुत तेज़ी से सीखती है, जिन्हें समान सटीकता के लिए अक्सर $O(\epsilon^{-4})$ नमूनों की आवश्यकता होती थी (यानी चार गुना अधिक डेटा)।
बिना सटीक मानचित्र के काम करता है: यह "ऑनलाइन" सेटिंग को संभालता है, जहाँ आप केवल अनुभव के एक निरंतर प्रवाह (जैसे शहर के माध्यम से एक एकल यात्रा) से सीख सकते हैं, न कि किसी सिम्युलेटर का उपयोग करके जहाँ से आप कहीं से भी शुरू कर सकते हैं।

मुख्य अंतर्दृष्टि: Implicit Exploration

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

सारांश

यह पेपर AI एजेंटों के लिए अनुभव से सीखने का एक स्मार्ट तरीका पेश करता है। पूर्व-निर्धारित मानचित्रों या अन्वेषण के निश्चित शेड्यूल्स पर निर्भर रहने के बजाय, एजेंट auto-exploration का उपयोग करता है: यह सूचना कितनी कठिन है, इसके आधार पर अपने खोज प्रयास को गतिशील रूप से समायोजित करता है। यह सीखने की प्रक्रिया को तेज़, अधिक कुशल और लागू करने में आसान बनाता है क्योंकि इसके लिए पर्यावरण के छिपे हुए विवरणों को पहले से जानने की आवश्यकता नहीं होती है। यह एक पर्यटक को स्मार्ट वॉच देने जैसा है जो उसे ठीक-ठीक बताती है कि कब भटकना बंद करना है और कब और तलाश जारी रखनी है, जिससे यह सुनिश्चित होता है कि वह सबसे अच्छा रेस्टोरेंट खोज ले और खो न जाए।

तकनीकी सारांश: ऑनलाइन सुदृढीकरण शिक्षण (Reinforcement Learning) के लिए ऑटो-एक्सप्लोरेशन (Auto-exploration)

समस्या विवरण (Problem Statement)
यह शोध पत्र अनंत-क्षितिज (infinite-horizon) डिस्काउंटेड मार्कोव निर्णय प्रक्रियाओं (MDPs) के लिए ऑनलाइन सुदृढीकरण शिक्षण (RL) में 'एक्सप्लोरेशन-एक्सप्लोइटेशन' (exploration-exploitation) दुविधा को संबोधित करता है, जिसमें अवस्था (state) और क्रिया (action) के स्थान सीमित हैं। ऑनलाइन सेटिंग में, डेटा एक एकल प्रक्षेपवक्र (trajectory) (मार्कोवियन शोर) के माध्यम से उत्पन्न होता है, जिससे अवस्था-क्रिया स्थान (state-action space) का पर्याप्त कवरेज सुनिश्चित करना चुनौतीपूर्ण हो जाता है। मौजूदा एल्गोरिदम आमतौर पर "पर्याप्त अन्वेषण" (sufficient exploration) की धारणाओं पर निर्भर करते हैं, जिसके लिए अक्सर मध्यवर्ती नीतियों (intermediate policies) द्वारा प्रेरित मार्कोव श्रृंखलाओं के मिक्सिंग टाइम (mixing time) और स्टेशनरी डिस्ट्रीब्यूशन (stationary distribution) जैसे समस्या-निर्भर मापदंडों के ज्ञान की आवश्यकता होती है। ये पैरामीटर सामान्यतः अज्ञात और एल्गोरिदम-निर्भर होते हैं, जिससे या तो गैर-कार्यान्वयन योग्य एल्गोरिदम बनते हैं या उप-इष्टतम (sub-optimal) सैंपल कॉम्प्लेक्सिटी बाउंड्स (जैसे कि स्पष्ट अन्वेषण के लिए $O(\epsilon^{-4})$ , या $D_{expl}$ जैसे मनमाने रूप से बड़े अन्वेषण स्थिरांकों पर निर्भर बाउंड्स) प्राप्त होते हैं। लेखक ऑनलाइन, ऑन-पॉलिसी परिदृश्य में टैबुलर (tabular) और लीनियर फंक्शन एप्रोक्सिमेशन (linear function approximation) दोनों सेटिंग्स के लिए एल्गोरिदम-स्वतंत्र $O(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी प्राप्त करने के अंतराल को पहचानते हैं।

कार्यप्रणाली (Methodology)
लेखक "ऑटो-एक्सप्लोरेशन" नामक विधियों के एक वर्ग को पेश करते हैं, जिसे स्टोकेस्टिक पॉलिसी मिरर डिसेंट (SPMD) में एकीकृत किया गया है। मुख्य तकनीकी योगदान दो सेटिंग्स में विभाजित हैं:

टैबुलर सेटिंग (Tabular Setting):
- डायनेमिक एक्सप्लोरेशन टाइम (Dynamic Exploration Time): अज्ञात मिक्सिंग टाइम पर निर्भरता से बचने के लिए, लेखक एक डेटा-संचालित, डायनेमिक एक्सप्लोरेशन टाइम $\tilde{m}_\pi(\pi, \varsigma)$ प्रस्तावित करते हैं। यह समय अवस्था-क्रिया युग्मों के हिटिंग टाइम (hitting times) पर आधारित है, जिसे विशेष रूप से $\tilde{m}_\pi(\pi, \varsigma) := \max_{z \in Z_\pi(\pi)} \tau^\pi_\infty(z) + \lceil \log_\gamma((1-\gamma)\varsigma) \rceil$ के रूप में परिभाषित किया गया है, जहाँ $\tau^\pi_\infty(z)$ अवस्था-क्रिया युग्म $z$ का प्रथम हिटिंग टाइम है।
- इंप्लिसिट एक्सप्लोरेशन (Implicit Exploration): यह विधि धारणा 3.2 (Assumption 3.2) पर निर्भर करती है, जो एक नियतात्मक इष्टतम नीति $\pi^*$ के अस्तित्व का दावा करती है जो एक अपरिवर्तनीय (irreducible) मार्कोव श्रृंखला को प्रेरित करती है जिसका स्टेशनरी डिस्ट्रीब्यूशन शून्य से दूर (bounded away from zero) है। लेखक सिद्ध करते हैं कि यदि वर्तमान नीति $\pi$ इष्टतम क्रियाओं को गैर-शून्य प्रायिकता प्रदान करती है (इंप्लिसिट एक्शन एक्सप्लोरेशन), तो यह परोक्ष रूप से पर्याप्त अवस्था अन्वेषण (state exploration) सुनिश्चित करती है। यह मध्यवर्ती नीतियों के मिक्सिंग गुणों पर एल्गोरिदम-स्वतंत्र बाउंड्स के व्युत्पत्ति की अनुमति देता है।
- ब्रेगमैन डायवर्जेंस (Bregman Divergence): एक विशिष्ट ब्रेगमैन डायवर्जेंस, जो नेगेटिव टैलिस एंट्रॉपी (negative Tsallis entropy) पर आधारित है, का उपयोग किया गया है, जिसमें एंट्रॉपी इंडेक्स $p$ को कन्वर्जेंस बाउंड्स को कड़ा करने के लिए डिस्काउंट फैक्टर $\gamma$ के अनुकूल बनाया गया है।
लीनियर फंक्शन एप्रोक्सिमेशन सेटिंग (Linear Function Approximation Setting):
- नया सैंपलिंग डिस्ट्रीब्यूशन (New Sampling Distribution): अज्ञात स्टेशनरी डिस्ट्रीब्यूशन $\nu_\pi$ से नमूना लेने के बजाय, लेखक एक निश्चित ओरिजिन स्टेट $sor $से **डिस्काउंटेड विज़िटेशन डिस्ट्रीब्यूशन**$ \kappa^\pi_{sor}(s) $और एक$ \epsilon $-ग्रीडी एक्शन पॉलिसी पर आधारित वितरण$ w(z)$ से नमूना लेने का प्रस्ताव करते हैं। यह वितरण हमेशा सुपरिभाषित (well-defined) होता है और इसके लिए मिक्सिंग रेट के अनुमान की आवश्यकता नहीं होती है।
- कंडीशनल टेम्पोरल डिफरेंसिंग (Conditional Temporal Differencing - CTD): लेखक प्रोजेक्टेड बेलमैन समीकरणों को हल करने के लिए एक स्टोकेस्टिक ऑपरेटर $\hat{F}(\theta)$ विकसित करते हैं। इसका निर्माण एक रैंडम ज्योमेट्रिक ट्रंकेशन टाइम और एक डायनेमिक एक्सप्लोरेशन चरण में शामिल है, जो ओरिजिन स्टेट $sor$ के हिट होने तक नमूना लेता है, और उसके बाद वर्तमान नीति के तहत नमूना लेता है। यह अज्ञात फंक्शन एप्रोक्सिमेशन बायस (bias) से बचने के लिए ऑफ-पॉलिसी सैंपलिंग को सुगम बनाता है।

मुख्य योगदान (Key Contributions)

एल्गोरिदम-स्वतंत्र सैंपल कॉम्प्लेक्सिटी: यह शोध पत्र कमजोर अन्वेषण धारणाओं के तहत टैबुलर RL के लिए पहला एल्गोरिदम-स्वतंत्र, ऑन-पॉलिसी $O(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी स्थापित करता है। यह बाउंड $D_{expl}(\delta)$ पर निर्भर है, जिसमें $1/\delta$ पर पॉिलोगारिदमिक निर्भरता और समस्या-विशिष्ट मापदंडों (जैसे कि इष्टतम नीति की मिक्सिंग दर) पर बहुपद (polynomial) निर्भरता है, लेकिन $\epsilon$ या एल्गोरिदम-निर्भर पदों पर कोई निर्भरता नहीं है।
पैरामीटर-मुक्त कार्यान्वयन (Parameter-Free Implementation): प्रस्तावित विधियाँ पैरामीटर-मुक्त हैं, जिन्हें मिक्सिंग रेट या स्टेशनरी डिस्ट्रीब्यूशन के पूर्व ज्ञान की आवश्यकता नहीं है। डायनेमिक एक्सप्लोरेशन टाइम वास्तविक समय के हिटिंग टाइम के अवलोकन के माध्यम से आसानी से सुलभ है।
हाई-प्रोबेबिलिटी लास्ट-इटरेट कन्वर्जेंस (High-Probability Last-Iterate Convergence): लेखक SPMD के लिए नए हाई-प्रोबेबिलिटी लास्ट-इटरेट कन्वर्जेंस गारंटी प्राप्त करते हैं। यह पूर्व औसत-इटरेट (average-iterate) या अपेक्षित लास्ट-इटरेट परिणामों में सुधार करता है। सैंपल कॉम्प्लेक्सिटी, छोटे बायस और वेरिएंस की आवश्यकता वाले पिछले कार्यों की तुलना में $O((1-\gamma)^{-2})$ के कारक से और औसत-इटरेट कन्वर्जेंस तक सीमित इंप्लिसिट एक्सप्लोरेशन परिणामों की तुलना में $O(|A|^{1/2}/(1-\gamma))$ के कारक से बेहतर है।
सामान्यीकृत मार्कोव चेन कवरेज (Generalized Markov Chain Coverage): फंक्शन एप्रोक्सिमेशन सेटिंग में, डिस्काउंटेड विज़िटेशन डिस्ट्रीब्यूशन का उपयोग करने से यह विधि उन मार्कोव श्रृंखलाओं के अधिक व्यापक वर्ग को कवर कर सकती है जिन्हें स्टेशनरी डिस्ट्रीब्यूशन की आवश्यकता होती है।

परिणाम (Results)

थ्योरम 3.5 (टैबुलर): धारणा 3.2 के तहत, ऑटो-एक्सप्लोरेशन के साथ SPMD, $1-\delta$ प्रायिकता के साथ $\epsilon$ -सटीकता प्राप्त करने के लिए $\tilde{O}(D_{expl}(\delta) \cdot |A|^{2-p} (1-\gamma)^{-5} \epsilon^{-2})$ सैंपल का उपयोग करता है। पद $D_{expl}(\delta)$ एल्गोरिदम-स्वतंत्र है।
फंक्शन एप्रोक्सिमेशन: यह शोध पत्र लीनियर फंक्शन एप्रोक्सिमेशन के साथ ऑटो-एक्सप्लोरेटरी SPMD के लिए समान सैंपल कॉम्प्लेक्सिटी बाउंड्स स्थापित करता है। यह एक ट्रेड-ऑफ प्रकट करता है: यदि फंक्शन एप्रोक्सिमेशन एरर ज्ञात है तो इंप्लिसिट एक्सप्लोरेशन पर्याप्त है; यदि एरर अज्ञात है तो बायस से बचने के लिए एक्सप्लिसिट एक्सप्लोरेशन आवश्यक है।
कन्वर्जेंस रेट्स (Convergence Rates): विश्लेषण ऑप्टिमलिटी गैप $V^{\pi_k}(s) - V^{\pi^*}(s)$ के लिए हाई-प्रोबेबिलिटी बाउंड प्रदान करता है, जो $k$ इटरेशन पर निर्भर उप-रैखिक (sublinear) कन्वर्जेंस रेट दिखाता है।

महत्व (Significance)
लेखक दावा करते हैं कि यह कार्य मौजूदा ऑनलाइन RL एल्गोरिदम की सीमाओं को हल करता है जो अन्वेषण के लिए अज्ञात, एल्गोरिदम-निर्भर मापदंडों पर निर्भर करते हैं। ऑटो-एक्सप्लोरेशन पेश करके, विधियाँ सरल (पैरामीटर-मुक्त) हैं और बिना किसी स्पष्ट एक्सप्लोरेशन शेड्यूल या वातावरण के मिक्सिंग गुणों के ज्ञान के, इष्टतम $O(\epsilon^{-2})$ सैंपल कॉम्प्लेक्सिटी प्राप्त करती हैं। ये परिणाम चुनौतीपूर्ण ऑनलाइन, ऑन-पॉलिसी सेटिंग में सैद्धांतिक गारंटियों और व्यावहारिक कार्यान्वयन के बीच के अंतर को पाटते हैं।