🤖 machine learning

The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration

यह शोध पत्र परिमित-क्षितिज (finite-horizon) MDPs में सहकारी बहु-एजेंट रिवॉर्ड-फ्री अन्वेषण (reward-free exploration) की जांच करता है, जिसमें एक महत्वपूर्ण सीमा (threshold) की पहचान की गई है जहाँ लगभग $H$ लर्निंग चरणों का होना एजेंट जटिलता को बहुपद (polynomial) बनाए रखने की अनुमति देता है, जबकि कम चरणों के लिए सटीक डायनेमिक्स अनुमान प्राप्त करने हेतु एजेंटों की घातांकीय (exponential) संख्या की आवश्यकता होती है।

मूल लेखक: Idan Barnea, Orin Levy, Yishay Mansour

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

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

CC BY 4.0

मूल लेखक: Idan Barnea, Orin Levy, Yishay Mansour

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

कल्पना कीजिए कि आप एक विशाल, रहस्यमय भूलभुलैया (maze) के लेआउट को सीखने की कोशिश कर रहे हैं ताकि अंततः आप एक रोबोट को खजाना खोजने के लिए निर्देशित कर सकें। हालाँकि, एक पेच है: आपको अभी तक यह नहीं पता कि खजाना कहाँ है। वास्तव में, खजाना कल या अगले सप्ताह किसी अलग स्थान पर भी हो सकता है। आपका एकमात्र काम अभी दीवारों, दरवाजों और गलियारों का सटीक मानचित्र बनाना है, बिना किसी लक्ष्य के संकेत के।

यह "रिवॉर्ड-फ्री एक्सप्लोरेशन" (Reward-Free Exploration) की समस्या है।

अब, कल्पना कीजिए कि आपके पास एक अकेला व्यक्ति नहीं, बल्कि खोजकर्ताओं (एजेंटों) की एक टीम है। वे सभी एक ही समय में भूलभुलैया के माध्यम से दौड़ सकते हैं। मुख्य प्रश्न जो यह शोध पत्र पूछता है, वह यह है: आपको कितने खोजकर्ताओं की आवश्यकता होगी, और भूलभुलैया के माध्यम से दौड़ने के कितने राउंड की आवश्यकता होगी, ताकि एक सटीक मानचित्र मिल सके?

यहाँ उनकी खोज का विवरण दिया गया है, कुछ रोज़मर्रा के उदाहरणों का उपयोग करते हुए।

दो संसाधन: समय बनाम लोग

शोधकर्ताओं ने दो चीजों के बीच एक ट्रेड-ऑफ (trade-off) की पहचान की है:

समानांतर समय (फेजेस/Phases): आप अन्वेषण के कितने राउंड (rounds) की अनुमति देते हैं। (इसे इस तरह सोचें कि आप टीम को दौड़ने के लिए कितने दिन देते हैं)।
एजेंट जटिलता (लोग): प्रत्येक राउंड में कितने खोजकर्ता भेजे जाते हैं।

"क्षितिज" (Horizon) ही कुंजी है

भूलभुलैया की एक लंबाई है, जिसे क्षितिज ( $H$ ) कहा जाता है। यह उन अधिकतम कदमों की संख्या है जो आप लेने से पहले भूलभुलैया समाप्त हो सकती है।

यदि भूलभुलैया 100 कदम लंबी है, तो $H = 100$ है।

शोधकर्ताओं ने ठीक इस संख्या ( $H$ ) पर एक "टिपिंग पॉइंट" (Tipping Point) खोजा है।

परिदृश्य A: "बस पर्याप्त" रणनीति ( $H$ राउंड)

यदि आप अपनी टीम को भूलभुलैया के माध्यम से $H$ राउंड (भूलभुलैया के प्रत्येक कदम के लिए एक राउंड) तक दौड़ने की अनुमति देते हैं, तो आप उचित संख्या में लोगों के साथ काम चला सकते हैं।

उदाहरण: कल्पना कीजिए कि आप एक गाना सीख रहे हैं जो $H$ नोट्स लंबा है। यदि आप $H$ दिनों में एक नोट प्रति दिन अभ्यास करते हैं, तो आप संगीतकारों के एक छोटे समूह के साथ पूरा गाना सीख सकते हैं।
परिणाम: शोध पत्र एक एल्गोरिदम प्रदान करता है (जिसे H-MARFE कहा जाता है) जो "पॉलीनोमियल" (polynomial) संख्या में एजेंटों का उपयोग करता है। गणित की भाषा में, इसका अर्थ है कि आवश्यक लोगों की संख्या एक प्रबंधनीय तरीके से बढ़ती है (जैसे $H^6$ )। यह बहुत है, लेकिन असंभव नहीं है।

परिदृश्य B: "जल्दबाजी वाली" रणनीति (H से कम राउंड)

क्या होगा यदि आप जल्दी में हैं? क्या होगा यदि आपके पास आधा समय ही है (H से कम राउंड)?

उदाहरण: कल्पना कीजिए कि आप वही 100-नोट वाला गाना केवल 10 दिनों में सीखने की कोशिश कर रहे हैं। ऐसा करने के लिए, आपको अत्यधिक, घातांकीय (exponential) संख्या में संगीतकारों को नियुक्त करना होगा ताकि वे हर संभावित नोट संयोजन को एक साथ बजा सकें।
परिणाम: शोध पत्र यह सिद्ध करता है कि यदि आप $H$ से कम राउंड में इसे पूरा करने की कोशिश करते हैं, तो एजेंटों की संख्या विस्फोट की तरह बढ़ जाती है। यह "बहुत अधिक" से बदलकर "एक असंभव संख्या" (जैसे $2^{100}$ लोगों की आवश्यकता) हो जाती है। गणित दिखाता है कि आप एक घातांकीय सेना के बिना इतनी जल्दी मानचित्र नहीं सीख सकते।

एल्गोरिदम कैसे काम करता है (द "सिंक" ट्रिक)

शोधकर्ताओं का एल्गोरिदम, H-MARFE, चतुर है। यह पूरी भूलभुलैया को एक साथ सीखने की कोशिश नहीं करता है। इसके बजाय, यह इसे परत-दर-परत (layer by layer) सीखता है।

पहुंच योग्यता (Reachability) पर ध्यान दें: यह पूछता है, "हम भूलभुलैया के किन हिस्सों तक वास्तव में पहुँच सकते हैं?"
"सिंक" (Sink) अवस्था: यदि भूलभुलैया का कोई हिस्सा इतना कठिन है कि वहां पहुँचना लगभग असंभव है, तो एल्गोरिदम उसे एक "ब्लैक होल" (जिसे सिंक कहा जाता है) की तरह मानता है। यदि आप इसमें गिर जाते हैं, तो आप वहीं रह जाते हैं।
- क्यों? क्योंकि यदि कोई रास्ता इतना दुर्लभ है कि आप उसे लगभग कभी नहीं देखते, तो इससे कोई फर्क नहीं पड़ता कि उस विशिष्ट कोने का आपका मानचित्र थोड़ा गलत है। यह समग्र योजना को बहुत अधिक प्रभावित नहीं करेगा।
स्तरित शिक्षण (Layered Learning): राउंड 1 में, वे पहले कदम का मानचित्र बनाते हैं। राउंड 2 में, वे दूसरे कदम का मानचित्र बनाते हैं, राउंड 1 के मानचित्र का उपयोग यह जानने के लिए करते हैं कि कहाँ देखना है। वे ठीक $H$ राउंड तक ऐसा ही करते हैं।

"छिपी हुई कुंजी" का निचला स्तर (Lower Bound)

यह सिद्ध करने के लिए कि आप इसे तेज़ी से नहीं कर सकते, उन्होंने एक विशेष, पेचीदा भूलभुलैया बनाई है जिसे "की-डायनेमिक" (Key-Dynamic) कहा जाता है।

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

सारांश

लक्ष्य: बिना लक्ष्य जाने एक जटिल वातावरण का मानचित्र बनाना।
ट्रेड-ऑफ: आप प्रक्रिया को तेज़ (राउंड कम) नहीं कर सकते बिना जनशक्ति (एजेंटों) की एक भारी कीमत चुकाए (घातांकीय वृद्धि)।
स्वीट स्पॉट (Sweet Spot): यदि आप प्रक्रिया को वातावरण की लंबाई ( $H$ ) के बराबर राउंड लेने देते हैं, तो आप इसे एक प्रबंधनीय टीम के साथ कर सकते हैं।
चेतावनी: यदि आप जल्दबाजी करने की कोशिश करते (H से कम राउंड), तो लागत अत्यधिक हो जाएगी।

यह शोध पत्र मूल रूप से कहता है: "एक स्प्रिंट में मैराथन दौड़ने की कोशिश न करें। यदि आप कुशलतापूर्वक एक लंबे रास्ते का मानचित्र बनाना चाहते हैं, तो आपको इसे चरण-दर-चरण चलने के लिए पर्याप्त समय देना होगा।"

तकनीकी सारांश: सहकारी बहु-एजेंट रिवॉर्ड-फ्री एक्सप्लोरेशन में होराइजन थ्रेशोल्ड (क्षितिज सीमा)

समस्या विवरण (Problem Statement)

यह कार्य टैबुलर फाइनाइट-होराइजन मार्कोव डिसीजन प्रोसेस (MDPs) के ढांचे के भीतर सहकारी बहु-एजेंट रिवॉर्ड-फ्री एक्सप्लोरेशन की जांच करता है। इस सेटिंग में, $m$ एजेंट $\rho$ लर्निंग फेजेस (सीखने के चरणों) के दौरान एक अज्ञात वातावरण $M = (S, s_0, A, H, P, r)$ के साथ समानांतर रूप से अंतःक्रिया करते हैं। महत्वपूर्ण रूप से, एक्सप्लोरेशन चरण के दौरान, एजेंट रिवॉर्ड फंक्शन $r$ को नहीं देखते हैं; उनका उद्देश्य ट्रांजिशन डायनेमिक्स $P$ को इतना सटीक रूप से सीखना है कि एक्सप्लोरेशन के बाद प्रकट होने वाले किसी भी रिवॉर्ड फंक्शन के लिए एक $\epsilon$ -ऑप्टिमल पॉलिसी की गणना की जा सके।

केंद्रीय शोध प्रश्न दो संसाधनों के बीच के ट्रेड-ऑफ (समझौते) को संबोधित करता है:

पैरलेल टाइम (समानांतर समय): लर्निंग फेजेस की संख्या $\rho$ ।
एजेंट कॉम्प्लेक्सिटी (एजेंट जटिलता): प्रति चरण तैनात किए गए एजेंटों की संख्या $m$ ।

यह शोध यह निर्धारित करने का प्रयास करता है कि क्या चरणों की संख्या सीमित होने पर भी पॉलीनोमियल (बहुपद) संख्या में एजेंट पर्याप्त होती है, और यह कैसे क्षितिज (horizon) $H$ सीखने की दक्षता को नियंत्रित करता है।

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

अपर बाउंड (Upper Bound): H-MARFE एल्गोरिदम

लेखक H-MARFE (H-Phase Multi-Agent Reward-Free Exploration) प्रस्तावित करते हैं, जो एक ऐसा एल्गोरिदम है जिसे ठीक $\rho = H$ चरणों में संचालित करने के लिए डिज़ाइन किया गया है, जिसमें पॉलीनोमियल संख्या में एजेंटों का उपयोग होता है।

मुख्य तंत्र (Core Mechanism):
सीक्वेंशियल रिग्रेट-मिनिमाइजेशन दृष्टिकोणों के विपरीत, H-MARFE एक लेयर-वाइज एक्सप्लोरेशन रणनीति का उपयोग करता है जो रीचेबिलिटी (पहुंच योग्यता) के आधार पर अनुमान सटीकता को स्केल करती है।

फेज्ड डायनेमिक्स एस्टीमेशन: चरण $i$ (जहाँ $i \in \{0, \dots, H-1\}$ ) में, एल्गोरिदम विशेष रूप से टाइमस्टेप $i$ पर ट्रांजिशन डायनेमिक्स $P_i$ का अनुमान लगाने पर ध्यान केंद्रित करता है।
रीचेबिलिटी फ़िल्टरिंग: एल्गोरिदम प्रत्येक टाइमस्टेप पर "एक्टिव" स्टेट्स का एक सेट $\hat{S}^\beta_i$ परिभाषित करता है, जिसमें वे स्टेट्स शामिल हैं जिनकी वर्तमान अनुमानित डायनेमिक्स के तहत रीचेबिलिटी प्रोबेबिलिटी कम से कम $\beta$ है। कम रीचेबिलिटी वाले स्टेट्स को एक सिंक स्टेट $s_{sink}$ में ट्रांजिशन करके प्रभावी रूप से हटा (prune) दिया जाता है।
पॉलिसी कंस्ट्रक्शन: प्रत्येक एक्टिव स्टेट-एक्शन पेयर $(s, a)$ के लिए, एल्गोरिदम एक पॉलिसी $\hat{\pi}_{i,s,a}$ की गणना करता है जो पिछले चरणों में सीखे गए डायनेमिक्स के आधार पर टाइमस्टेप $i$ पर स्टेट $s$ तक पहुँचने और एक्शन $a$ लेने की संभावना को अधिकतम करती है।
पैरलेल एक्जीक्यूशन: प्रत्येक चरण में, $m$ एजेंटों को एक्टिव सेट से रैंडम स्टेट-एक्शन पेयर्स दिए जाते हैं। वे अपने सौंपे गए पॉलिसियों को निष्पादित करते हैं ताकि वर्तमान लेयर के लिए एम्पिरिकल ट्रांजिशन अनुमान एकत्र किए जा सकें, जिन्हें एकत्रित करके वर्तमान लेयर के लिए एम्पिरिकल ट्रांजिशन अनुमान बनाए जाते हैं।

तकनीकी नवाचार (Technical Innovation):
विश्लेषण एक मध्यवर्ती डायनेमिक्स मॉडल $P^1$ पेश करता है जो एक्टिव सेट पर वास्तविक डायनेमिक्स $P$ के साथ सहमत होता है लेकिन अन्यथा $s_{sink}$ की ओर ट्रांजिशन करता है। प्रमाण का आधार वर्तमान अनुमानित डायनेमिक्स $\hat{P}$ और $P^1$ के बीच पॉलिसी-वेटेड एरर को बांधना है। रीचेबिलिटी के सापेक्ष ऑक्यूपेंसी मेजर्स में एडिटिव एरर को नियंत्रित करके, एल्गोरिदम यह सुनिश्चित करता है कि किसी भी रिवॉर्ड फंक्शन के लिए वैल्यू एस्टीमेशन एरर सीमित रहे, जिससे नेइव पैरेललाइजेशन में होने वाला एक्सपोनेंशियल एरर संचय (accumulation) टल जाता है।

लोअर बाउंड कंस्ट्रक्शन (Lower Bound Construction)

होराइजन-स्केल चरणों की आवश्यकता को स्थापित करने के लिए, लेखक एक "की-डायनेमिक" (Key-Dynamic) MDP का निर्माण करते हैं।

संरचना: MDP में स्टेट स्पेस का आकार 2 ( $s^\star$ और $s_{sink}$ ) है। एक छिपा हुआ "की" (key) एक्शन सीक्वेंस $a^\star_0, \dots, a^\star_{H-1}$ मौजूद है। स्टेट $s^\star$ पर सही एक्शन $a^\star_h$ लेने से एजेंट $s^\star$ में ही रहता है; कोई भी अन्य एक्शन उसे एब्जॉर्बिंग सिंक स्टेट $s_{sink}$ में ट्रांजिशन कर देता है।
रिवॉर्ड: एक विशिष्ट रिवॉर्ड फंक्शन $r_{key}$ केवल तभी रिवॉर्ड 1 देता है जब एजेंट अंतिम टाइमस्टेप में $s^\star$ स्टेट में सही अंतिम एक्शन निष्पादित करते हुए पहुँचता है।
निहितार्थ: डायनेमिक्स (और इस प्रकार अनुकूलतम पॉलिसी) को सीखने के लिए, एक एल्गोरिदम को पूरी "की" सीक्वेंस की खोज करनी चाहिए। एक सिंगल फेज में, $m$ एजेंट "की" के अधिकतम $\log_A(m)$ बिट्स को उजागर कर सकते हैं। यदि चरणों की संख्या $\rho$ , $H$ से काफी कम है, तो पूरी "की" की खोज करने की संभावना $H/\rho$ के संदर्भ में एक्सपोनेंशियल रूप से गिर जाती है, जब तक कि एजेंटों की संख्या $m$ , $H/\rho$ के साथ एक्सपोनेंशियल रूप से न बढ़े।

मुख्य परिणाम (Key Results)

1. अपर बाउंड (Theorem 3.1)

H-MARFE एल्गोरिदम उच्च प्रायिकता के साथ किसी भी रिवॉर्ड फंक्शन के लिए एक $\epsilon$ -ऑप्टिमल पॉलिसी प्राप्त करता है, जिसमें उपयोग होता है:

फेजेस: $\rho = H$ ।
एजेंट्स: $m = \tilde{O}\left(\frac{S^6 H^6 A}{\epsilon^2}\right)$ ।

यह दर्शाता है कि जब लर्निंग फेजेस की संख्या होराइजन के रैखिक (linear) रूप से स्केल करती है, तो कुशल लर्निंग (जो $S, A, H, \epsilon^{-1}$ में पॉलीनोमियल है) संभव है।

2. लोअर बाउंड (Theorem 4.1)

किसी भी सहकारी बहु-एजेंट एल्गोरिदम के लिए जो $\rho < H$ लर्निंग फेजेस तक सीमित है, निरंतर सटीकता (जैसे, $\epsilon = 0.1$ ) प्राप्त करने के लिए आवश्यक है:

एजेंट्स: $m = \Omega\left(\frac{A^{(H-1)/\rho}}{\rho}\right)$ ।

यह लोअर बाउंड सिद्ध करता है कि चरणों की संख्या को $H$ से कम करने के लिए एजेंटों की संख्या में एक्सपोनेंशियल वृद्धि की आवश्यकता होती है।

3. होराइजन थ्रेशोल्ड (The Horizon Threshold)

संयुक्त परिणाम एक स्पष्ट रिजीम चेंज (regime change) की पहचान करते हैं जो होराइजन $H$ द्वारा शासित है:

पॉलीनोमियल रिजीम: जब $\rho \approx H$ , तो एजेंट कॉम्प्लेक्सिटी पॉलीनोमियल होती है।
एक्सपोनेंशियल रिजीम: जब $\rho \ll H$ , तो एजेंट कॉम्प्लेक्सिटी $H/\rho$ के संदर्भ में एक्सपोनेंशियल हो जाती है।

महत्व और दावे (Significance and Claims)

यह शोध दावा करता है कि इसने टैबुलर MDPs में रिवॉर्ड-फ्री एक्सप्लोरेशन की पैरेलल एफिशिएंसी (समानांतर दक्षता) पर एक मौलिक सीमा स्थापित की है। इसका प्राथमिक योगदान होराइजन $H$ को समानांतर समय के लिए एक क्रिटिकल थ्रेशोल्ड के रूप में पहचानना है।

होराइजन-स्केल फेजेस की आवश्यकता: यह कार्य प्रदर्शित करता है कि एक्सपोनेंशियल एजेंट कॉम्प्लेक्सिटी से बचने के लिए, एक्सप्लोरेशन को केवल एक स्थिर या सब-लीनियर संख्या में फेजेस में संकुचित नहीं किया जा सकता है। फेजेस की संख्या को होराइजन के साथ स्केल करना ही होगा।
एल्गोरिद्मिक दक्षता: H-MARFE एक कम्प्यूटेशनल रूप से कुशल तरीका प्रदान करता है, जो पूर्व रिवॉर्ड-फ्री साहित्य से भिन्न है जो स्वाभाविक रूप से सीक्वेंशियल है या जिसमें स्विचिंग कॉस्ट्स होते हैं जो एपिसोड्स के साथ लीनियर रूप से स्केल करते हैं।
सैद्धांतिक अंतर (Theoretical Gap): लेखक नोट करते हैं कि जबकि उनका अपर बाउंड पॉलीनोमियल कॉम्प्लेक्सिटी प्राप्त करता है, $S$ और $H$ ( $S^6 H^6$ ) पर उनकी निर्भरता स्टेट-ऑफ-द-आर्ट सिंगल-एजेंट बाउंड्स ( $S^2 H^3$ ) से अधिक है। वे स्पष्ट रूप से कहते हैं कि यह एक खुला प्रश्न है कि क्या यह गैप पैरेललाइजेशन की एक अंतर्निहित लागत है या उनके विश्लेषण का एक आर्टिफैक्ट।

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