🤖 machine learning

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

यह शोध पत्र एक नवीन एल्गोरिदम प्रस्तावित करता है जो एपिसोडिक MDPs में रिवॉर्ड-अग्नोस्टिक एक्सप्लोरेशन (reward-agnostic exploration) पर सटीकता संबंधी बाधाओं को महत्वपूर्ण रूप से शिथिल करता है और रिवॉर्ड-फ्री एक्सप्लोरेशन (reward-free exploration) के लिए एक सटीक निचली सीमा (tight lower bound) स्थापित करता है, जिससे ज्ञात ऊपरी और निचली सीमाओं के बीच के अंतर को समाप्त किया जा सके।

मूल लेखक: Oran Ridel, Alon Cohen

प्रकाशित 2026-05-18

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

CC BY 4.0

मूल लेखक: Oran Ridel, Alon Cohen

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

कल्पना कीजिए कि आप एक जासूस हैं जिसे शहर के लेआउट को सीखने के लिए एक विशाल, अज्ञात शहर में भेजा गया है। हालाँकि, एक शर्त है: आपको दिशा पूछने की अनुमति नहीं है, और आपको अभी अपना अंतिम मिशन भी नहीं पता है।

हो सकता है कि कल आपको अस्पताल तक पहुँचने का सबसे तेज़ रास्ता ढूँढना हो। परसों, आपको शायद सबसे सुंदर पार्क ढूँढना हो। या शायद आपको कोई विशिष्ट बेकरी ढूँढनी हो। आप नहीं जानते कि आपको इनमें से कौन से कार्यों का सामना करना पड़ेगा, लेकिन आप जानते हैं कि आपको हर चीज़ के लिए तैयार रहना होगा।

यह इस शोध पत्र (paper) का मूल विषय है: आप एक वातावरण को कुशलतापूर्वक कैसे एक्सप्लोर (explore) करते हैं जब आपको यह नहीं पता होता कि "रिवॉर्ड" (लक्ष्य) क्या है?

लेखक, ओरान रिडेल और एलन कोहेन, इस पहेली को हल करने का एक नया तरीका प्रस्तावित करते हैं जो पिछले तरीकों की तुलना में बहुत अधिक कुशल है। यहाँ उनके काम का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है।

दो परिदृश्य (The Two Scenarios)

यह पेपर इस "ब्लाइंड एक्सप्लोरेशन" समस्या के दो थोड़े अलग संस्करणों को देखता है:

रिवॉर्ड-फ्री एक्सप्लोरेशन (The "Blank Canvas" Scenario - खाली कैनवास परिदृश्य):
आप शहर को पूरी तरह से अंधेरे में एक्सप्लोर करते हैं। आपको नहीं पता कि आपको कभी अस्पताल, पार्क या बेकरी जाने की आवश्यकता होगी या नहीं। आपको बस शहर का मानचित्र (map) इतनी अच्छी तरह से बनाना है कि बाद में जो भी लक्ष्य आपको दिया जाए, आप तुरंत सबसे अच्छा रास्ता निकाल सकें।
- चुनौती: चूंकि लक्ष्य कुछ भी हो सकता है, इसलिए आपको अविश्वसनीय रूप से गहन (thorough) होना होगा।
रिवॉर्ड-एग्नोस्टिक एक्सप्लोरेशन (The "Menu" Scenario - मेनू परिदृश्य):
आप अभी भी विशिष्ट लक्ष्य नहीं जानते, लेकिन आप पहले से ही संभावित लक्ष्यों की सूची जानते हैं। शायद आप जानते हैं कि एकमात्र संभावित गंतव्य "अस्पताल," "पार्क," या "बेकरी" हैं।
- लाभ: क्योंकि आप जानते हैं कि सूची छोटी है, इसलिए आपको हर एक गली को समान तीव्रता के साथ मैप करने की आवश्यकता नहीं है। आप थोड़े अधिक रणनीतिक हो सकते हैं।

पुराना तरीका: "ट्रायल एंड एरर" दृष्टिकोण

पिछले तरीकों (जैसे ली एट अल., 2024 द्वारा) ने इसे कई अलग-अलग, छोटे प्रयोग चलाकर हल करने की कोशिश की।

उपमा: कल्पना कीजिए कि आप हर सड़क के कोने के लिए एक अलग गाइड किराए पर लेकर शहर को सीखने की कोशिश कर रहे हैं। आप उत्तर दिशा सीखने के लिए गाइड A को किराए पर लेते हैं, फिर उन्हें हटा देते हैं और दक्षिण दिशा के लिए गाइड B को किराए पर लेते हैं, इत्यादि।
समस्या: यह अविश्वसनीय रूप से विनाशकारी (wasteful) है। आप बार-बार एक ही शहर के बुनियादी नियमों को फिर से सीखते रहते हैं। यह काम तो करता है, लेकिन इसमें बहुत अधिक समय और डेटा लगता है, खासकर यदि आपको बहुत सटीक होने की आवश्यकता हो।

नया तरीका: "स्मार्ट टूर गाइड"

लेखक एक नया एल्गोरिदम प्रस्तावित करते हैं जो एक एकल, अत्यधिक बुद्धिमान टूर गाइड की तरह कार्य करता है जो एक निरंतर, स्मार्ट यात्रा में शहर को सीखता है।

1. "क्यूरियोसिटी" रणनीति (चरण 1)
अलग-अलग प्रयोग चलाने के बजाय, एल्गोरिदम एक लंबा "ऑनलाइन लर्निंग" सत्र चलाता है। यह नकली, अस्थायी लक्ष्यों (रिवॉर्ड्स) की एक श्रृंखला बनाता है जो विशेष रूप से एजेंट को उन हिस्सों में जाने के लिए मजबूर करने के लिए डिज़ाइन किए गए हैं जहाँ पहुँचना सबसे कठिन है या जिन्हें कम समझा गया है।

रूपक: कल्पना कीजिए कि गाइड कहता है, "ठीक है, आज हम उस जगह जाएंगे जहाँ कोई नहीं जाता। कल, हम उस जगह जाएंगे जिसे ढूँढना कठिन है।" लगातार लक्ष्य को "सबसे कठिन" स्थानों की ओर बदलकर, एजेंट स्वाभाविक रूप से शहर का एक पूर्ण मानचित्र बनाता है बिना उन जगहों पर समय बर्बाद किए जिन्हें वह पहले से जानता है।
परिणाम: यह एक एकल "एक्सप्लोरेशन पॉलिसी" (एक मास्टर प्लान) बनाता है जो शहर की गतिशीलता (कि सड़कें कैसे जुड़ती हैं) को समझने के लिए पर्याप्त डेटा एकत्र करता है, और यह पिछले तरीकों की तुलना में बहुत कम यात्राओं में होता है।

2. "मैप मेकर" (चरण 2)
एक बार जब एजेंट अपना एक्सप्लोरेशन पूरा कर लेता है, तो वह शहर के ट्रांजिशन (जैसे, "यदि मैं फव्वारे पर बाईं ओर मुड़ता हूँ, तो मैं चौक पर पहुँच जाता हूँ") का एक सटीक मानचित्र बनाने के लिए एकत्र किए गए सभी डेटा का उपयोग करता है।

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

यह शोध पत्र क्यों महत्वपूर्ण है

लेखकों ने दो प्रमुख सफलताएं हासिल की हैं:

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

समाधान: नया एल्गोरिदम इस आवश्यकता को शिथिल (relax) करता है। यह तब भी कुशलता से काम करता है जब आपको पूर्ण होने की आवश्यकता नहीं होती, जिससे यह वास्तविक दुनिया की स्थितियों की एक विस्तृत श्रृंखला के लिए उपयोगी बन जाता है।

2. उन्होंने सिद्ध किया कि "ब्लैंक कैनवस" परिदृश्य उतना ही कठिन है जितना कि सोचा गया था।
"रिवॉर्ड-फ्री" (ब्लैंक कैनवस) परिदृश्य के लिए, सबसे अच्छे ज्ञात तरीके (हम कितनी तेज़ी से कर सकते हैं) और सैद्धांतिक सीमा (हमें कितनी तेज़ी से करना चाहिए) के बीच एक अंतर था।

समाधान: लेखकों ने एक नया "लोअर बाउंड" (lower bound) सिद्ध किया। उन्होंने दिखाया कि आप कितने भी चतुर क्यों न हों, आप एक निश्चित सीमा से तेज़ नहीं कर सकते। यह अंतर को पाट देता है, यह सिद्ध करता है कि मौजूदा सर्वोत्तम तरीके वास्तव में इष्टतम (optimal) हैं।

सारांश

इस शोध पत्र को एक नए वातावरण को सीखने के तरीके के अपग्रेड के रूप में देखें।

पुराना रोबोट: "मैं हर सड़क को 1,000 बार अलग-अलग जाकर सीखने की कोशिश करूँगा। इसमें अनंत काल लग जाएगा।"
नया रोबोट: "मैं एक स्मार्ट, घुमावदार दौरे पर जाऊँगा जो मुझे हर कठिन कोने में ठीक एक बार जाने के लिए मजबूर करेगा, और इस प्रक्रिया में एक पूर्ण मानचित्र बनाएगा। फिर, जब आप मुझे बताएंगे कि कहाँ जाना है, तो मुझे रास्ता तुरंत पता चल जाएगा।"

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

तकनीकी सारांश: रिवॉर्ड-अग्नोस्टिक और रिवॉर्ड-फ्री एक्सप्लोरेशन के लिए बेहतर बाउंड्स

समस्या का निरूपण (Problem Formulation)

यह शोध पत्र एपिसोडिक परिमित-क्षिति (finite-horizon) टेबुलर मार्कोव डिसीजन प्रोसेस (MDPs) में अन्वेषण (exploration) की चुनौती को संबोधित करता है, जहाँ एजेंट डेटा संग्रह चरण के दौरान बाहरी रिवॉर्ड सिग्नल देखे बिना कार्य करता है। लेखक दो विशिष्ट ढाँचों का अध्ययन करते हैं:

रिवॉर्ड-फ्री एक्सप्लोरेशन (RFE): एजेंट बिना किसी रिवॉर्ड सिग्नल के एक अज्ञात वातावरण का अन्वेषण करता है। लक्ष्य एक ऐसी पॉलिसी तैयार करना है जो एक्सप्लोरेशन चरण के बाद प्रकट होने वाले किसी भी मनमाने रिवॉर्ड फंक्शन के लिए $\epsilon$ -ऑप्टिमल हो।
रिवॉर्ड-अग्नोस्टिक एक्सप्लोरेशन (RAE): RFE के समान, लेकिन यहाँ रिवॉर्ड फंक्शन एक छोटे, पूर्व-निर्धारित परिमित वर्ग (वर्ग का आकार $|S|, |A|, H$ के बहुपद में है) से लिया जाता है। लक्ष्य इस वर्ग से लिए गए विशिष्ट रिवॉर्ड के लिए $\epsilon$ -ऑप्टिमल पॉलिसी खोजना है।

मुख्य कठिनाई रिवॉर्ड सिग्नल के मार्गदर्शन के बिना स्टेट-एक्शन ट्रांज़िशन डायनेमिक्स का सटीक अनुमान लगाने के लिए पर्याप्त डेटा एकत्र करने में निहित है, जिससे यह सुनिश्चित हो सके कि परिणामी मॉडल डाउनस्ट्रीम कार्यों के लिए निकट-इष्टतम (near-optimal) नीतियों की गणना का समर्थन करता है।

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

प्रस्तावित दृष्टिकोण पिछले कार्यों में पाए जाने वाले कई स्वतंत्र नो-रिग्रेट सबरूटीन्स (no-regret subroutines) पर निर्भरता को एक एकीकृत ऑनलाइन लर्निंग प्रक्रिया से बदल देता है। एल्गोरिदम (एल्गोरिदम 1) तीन चरणों में कार्य करता है:

1. एक्सप्लोरेशन पॉलिसी निर्माण

कई स्टोकेस्टिक नो-रिग्रेट एल्गोरिदम चलाने के बजाय (जैसा कि जिन एट अल., 2020b; ली एट अल., 2024b द्वारा किया गया है), लेखक सावधानीपूर्वक निर्मित सहायक रिवॉर्ड फंक्शन्स के एक अनुक्रम पर एक एकल ऑनलाइन मिरर डिसेंट (OMD) एल्गोरिदम का उपयोग करते हैं।

तंत्र (Mechanism): एल्गोरिदम $\{\lambda_t\}$ रिवॉर्ड्स का एक अनुक्रम उत्पन्न करता है जो एजेंट को कम-विजिट किए गए स्टेट-एक्शन पेयर्स की ओर ले जाने के लिए डिज़ाइन किया गया है। स्टेप $t$ पर रिवॉर्ड, स्टेट-एक्शन पेयर के विज़िटेशन काउंट (एक स्थिरांक $c$ के साथ, जो कम-संभावना वाली विजिट्स को संभालने के लिए है) के व्युत्क्रमानुपाती होता है।
ऑप्टिमाइज़ेशन परिप्रेक्ष्य: इस प्रक्रिया को वैध ऑक्यूपेंसी मेजर्स के स्पेस पर एक कॉनवेक्स ऑप्टिमाइज़ेशन समस्या को लगभग हल करने के रूप में फ्रेम किया गया है। विशेष रूप से, यह नेगेटिव लॉग-बैरियर ऑब्जेक्टिव $f(\mu) = -\sum \log \mu_h(s,a)$ को न्यूनतम करने का लक्ष्य रखता है।
महत्व: फ्रैंक-वोल्के (Frank-Wolfe) स्टाइल इटरेशन के बजाय एक एकल ऑनलाइन MDP एल्गोरिदम (रोसेनबर्ग और मंसौर, 2019 से अनुकूलित) का उपयोग करके, यह विधि लो-ऑर्डर सैंपल कॉम्प्लेक्सिटी टर्म्स को काफी कम कर देती है। यह एक "पॉलिसी कवर" बनाने के लिए पूरे लर्निंग प्रोसेस के दौरान सैंपल्स का पुन: उपयोग करता है जो महत्वपूर्ण स्टेट-एक्शन ट्रिपल्स के निकट-समान (near-uniform) एक्सप्लोरेशन को सुनिश्चित करता है।

2. डायनेमिक्स एस्टीमेशन

स्टेप 1 में उत्पन्न एक्सप्लोरेशन पॉलिसी का उपयोग करके, एजेंट $N$ ट्रेजेक्टरीज एकत्र करता है। ट्रेजेक्टरी डेटा में अंतर्निहित टेम्पोरल कोरिलेशन को संभालने के लिए, लेखक एक टू-फोल्डड सबसैंपलिंग फ्रेमवर्क (ली एट अल., 2024a) का उपयोग करते हैं। यह तकनीक डेटासेट को एक मुख्य सेट और एक सहायक सेट में विभाजित करती है ताकि सांख्यिकीय स्वतंत्रता प्रेरित की जा सके, जिससे एक अनुभवजन्य ट्रांज़िशन कर्नेल $\hat{P}$ का निर्माण किया जा सके जिसके पास कठोर कंसन्ट्रेशन गारंटी हो।

3. पॉलिसी एस्टीमेशन

एक बार वास्तविक रिवॉर्ड फंक्शन प्रकट हो जाने के बाद, एल्गोरिदम अनिश्चितता के विरुद्ध निराशावाद (pessimism in the face of uncertainty) का उपयोग करके एक $\epsilon$ -ऑप्टिमल पॉलिसी की गणना करता है।

एल्गोरिदम प्रकट रिवॉर्ड और $\hat{P}$ का उपयोग करके एक एम्पिरिकल MDP बनाता है।
यह Q-वैल्यू अनुमानों पर बर्नस्टीन-शैली के कंसन्ट्रेशन इनइक्वेलिटीज से प्राप्त पेनल्टी टर्म $b_h(s,a)$ लागू करता है। यह पेनल्टी अनुभवजन्य वेरिएंस और विज़िट काउंट के साथ स्केल होती है, जो पॉलिसी को कम-कवर्ड स्टेट-एक्शन पेयर्स को विज़िट करने से रोकती है।
अंतिम पॉलिसी $\hat{\pi}$ इस निराशावादी एम्पिरिकल MDP के लिए इष्टतम पॉलिसी है।

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

1. रिवॉर्ड-अग्नोस्टिक एक्सप्लोरेशन (RAE) के लिए बेहतर सैंपल कॉम्प्लेक्सिटी

यह शोध पत्र एक नया एल्गोरिदम प्रस्तुत करता है जो RAE के लिए इष्टतम हाई-ऑर्डर सैंपल कॉम्प्लेक्सिटी प्राप्त करता है, जो बेस्ट पॉलिसी आइडेंटिफिकेशन (BPI) के लोअर बाउंड से मेल खाता है।

परिणाम: सैंपल कॉम्प्लेक्सिटी $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$ है।
सुधार: जबकि पिछले कार्य (ली एट अल., 2024b) ने इष्टतम हाई-ऑर्डर टर्म $O(|S||A|H^3/\epsilon^2)$ प्राप्त किया था, उनका बाउंड एक उच्च-जटिलता वाले लो-ऑर्डर टर्म से ग्रस्त था जिसने बाउंड को केवल अत्यंत छोटे $\epsilon$ के लिए ही इष्टतम बनाया। प्रस्तावित विधि इस लो-ऑर्डर टर्म को काफी कम कर देती है, जिससे एल्गोरिदम सटीकता मापदंडों की एक विस्तृत श्रृंखला के लिए लागू करने योग्य हो जाता है।

2. रिवॉर्ड-फ्री एक्सप्लोरेशन (RFE) के लिए टाइट लोअर बाउंड

लेखक टाइम-इनहोमोजेनियस (time-inhomogeneous) MDPs में RFE के सैंपल कॉम्प्लेक्सिटी के लिए एक टाइट लोअर बाउंड सिद्ध करते हैं।

परिणाम: किसी भी RFE एल्गोरिदम को अपेक्षा (expectation) में $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$ ट्रेजेक्टरीज की आवश्यकता होती है।
महत्व: यह ली एट अल. (2024b) के उस अनुमान को हल करता है कि टाइम-इनहोमोजेनियस RFE के लिए मिनिमैक्स लोअर बाउंड, टाइम-होमोजेनियस मामले की तुलना में $H$ फैक्टर बड़ा है। यह स्थापित करता है कि मौजूदा अपर बाउंड्स (जैसे मेनार्ड एट अल., 2021) लॉगरिदमिक फैक्टर्स तक इष्टतम हैं।

3. सैद्धांतिक ढांचा (Theoretical Framework)

यह शोध पत्र ऑक्यूपेंसी मेजर्स पर लॉग-बैरियर ऑब्जेक्टिव के मिनिमाइजेशन के साथ एक्सप्लोरेशन पॉलिसी क्रिएशन को जोड़कर एक नया तकनीकी परिप्रेक्ष्य प्रदान करता है। यह प्रदर्शित करता है कि एक ऑनलाइन मिरर डिसेंट दृष्टिकोण पिछले फ्रैंक-वोल्के आधारित तरीकों की तुलना में इस समाधान को अधिक कुशलता से अनुमानित कर सकता है, जिससे लो-ऑर्डर टर्म्स में समस्या के आयामों (dimensions) पर निर्भरता कम हो जाती है।

महत्व और दावे

यह शोध पत्र रिवॉर्ड के बिना अन्वेषण की सैद्धांतिक समझ को आगे बढ़ाने का दावा करता है:

एक्सप्लोरेशन और एक्सप्लोइटेशन को अलग करना: यह परिमित-क्षिति MDPs में अन्वेषण की अंतर्निहित सैंपल कॉम्प्लेक्सिटी को स्पष्ट करता है।
RAE की व्यावहारिकता: पिछले इष्टतम बाउंड्स में पाए जाने वाले $\epsilon$ सटीकता मापदंड की प्रतिबंधात्मक आवश्यकताओं को शिथिल करके, प्रस्तावित विधि रिवॉर्ड-अग्नोस्टिक एक्सप्लोरेशन को मध्यम-सटीकता वाले शासन (regimes) में भी व्यावहारिक बनाती है।
चरित्र चित्रण की पूर्णता: RAE के नए अपर बाउंड और RFE के टाइट लोअर बाउंड के संयोजन से इन समस्याओं के लिए सैंपल कॉम्प्लेक्सिटी का पूर्ण मिनिमैक्स कैरेक्टराइजेशन (minimax characterization) प्राप्त होता है (लॉगरिदमिक फैक्टर्स तक)।

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