🤖 machine learning

Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning

यह शोध पत्र Graph-SND को प्रस्तुत करता है, जो एक स्केलेबल स्पार्स एग्रीगेशन विधि है जो मल्टी-एजेंट सुदृढीकरण शिक्षण में द्विघाती-लागत वाले सिस्टम न्यूरल डायवर्सिटी (SND) मीट्रिक का अनुमान लगाने के लिए मनमाने ग्राफ किनारों (edges) पर भारित औसत की गणना करती है, जिससे मीट्रिक के अर्थ संबंधी अर्थ को बदले बिना बड़े एजेंट समूहों के लिए कुशल व्यवहारिक विविधता मापन और नियंत्रण सक्षम होता है।

मूल लेखक: Shawn Ray

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

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

CC BY 4.0

मूल लेखक: Shawn Ray

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

कल्पना कीजिए कि आप 100 खिलाड़ियों वाली एक विशाल स्पोर्ट्स टीम के कोच हैं। आपका लक्ष्य यह सुनिश्चित करना है कि हर कोई एक-दूसरे से अलग तरह से खेल रहा हो। यदि सभी बिल्कुल एक जैसा काम करते हैं, तो टीम कमजोर और अनुमानित (predictable) हो जाती है। यदि उन सभी की शैलियाँ अद्वितीय हैं, तो टीम मजबूत और अनुकूलन योग्य (adaptable) होती है।

इस "विविधता" (diversity) को मापने के लिए, आपको हर खिलाड़ी की तुलना हर दूसरे खिलाड़ी से करनी होगी। कंप्यूटर एजेंटों (रोबोट या AI) की दुनिया में, इसे सिस्टम न्यूरल डायवर्सिटी (SND) कहा जाता है।

समस्या: "ऑल-हैंड्स" मीटिंग बहुत धीमी है

विविधता को मापने का पारंपरिक तरीका ऐसा है जैसे एक मीटिंग आयोजित करना जहाँ हर एक खिलाड़ी हर दूसरे खिलाड़ी से हाथ मिलाता है।

10 खिलाड़ियों के साथ, वह 45 हैंडशेक है। आसान है।
100 खिलाड़ियों के साथ, वह लगभग 5,000 हैंडशेक है।
500 खिलाड़ियों के साथ, वह 120,000 से अधिक हैंडशेक है!

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

समाधान: Graph-SND (एक "स्मार्ट नेटवर्क")

यह पेपर एक नया तरीका पेश करता है जिसे Graph-SND कहा जाता है। हर किसी को एक-दूसरे से हाथ मिलाने के लिए मजबूर करने के बजाय, यह एक नेटवर्क मैप (ग्राफ) का उपयोग करता है यह तय करने के लिए कि कौन किससे बात करेगा।

इसे एक पार्टी आयोजित करने की तरह समझें:

पुराना तरीका (कम्प्लीट ग्राफ): हर किसी को एक-दूसरे से परिचय करना होगा। सटीक है, लेकिन थकाऊ है।
नया तरीका (Graph-SND): आप एक नक्शा बनाते हैं कि कौन किसके पास खड़ा है। आप केवल अपने आस-पास के पड़ोसियों से परिचय करने के लिए ही कहते हैं।
- यदि आप एक स्थानीय वाइब चाहते हैं: तो आप केवल पड़ोसियों (जैसे एक ही कमरे में रहने वाले लोग) के बीच विविधता को मापते हैं। यह तब बहुत अच्छा है जब आप केवल स्थानीय टीम वर्क की परवाह करते हैं।
- यदि आप पूरी पार्टी वाइब चाहते हैं: तो आप यादृच्छिक (randomly) रूप से कुछ लोगों को कुछ अन्य लोगों से परिचय करने के लिए चुनते हैं। (एक चालाकी भरी गणित पद्धति जिसे Horvitz-Thompson estimation कहा जाता है का उपयोग करके), आप इन छोटी यादृच्छिक बातचीत को सुनकर पूरी पार्टी की विविधता का अनुमान लगा सकते हैं।

यह तीन परिदृश्यों में कैसे काम करता है

"परफेक्ट मैच" (रिकवरी): यदि आप एक ऐसा नक्शा खींचते हैं जहाँ हर कोई सभी से जुड़ा हुआ है, तो Graph-SND वही उत्तर देता है जो पुराने, धीमे तरीके ने दिया था। यह सिद्ध करता है कि नया तरीका गणितीय रूप रूप से सुदृढ़ है।
"स्थानीय पड़ोस" (फिक्स्ड स्पार्स ग्राफ): आप एक ऐसा मैप सेट कर सकते हैं जहाँ एजेंट केवल अपने 5 निकटतम पड़ोसियों से बात करते हैं। यह सुपर फास्ट है। यह केवल वहीं विविधता को मापता है जहाँ इसकी आवश्यकता है (जैसे एक शहर के ब्लॉक में पड़ोसी)।
"रैंडम सैंपलिंग" (अनबायस्ड एस्टिमेटर): आप जोड़ों के एक छोटे प्रतिशत (मान लीजिए 10%) को यादृच्छिक रूप से चुनते हैं और उन्हें मापते हैं। पेपर यह सिद्ध करता है कि भले ही आप डेटा के केवल 10% हिस्से को देख रहे हैं, आपकी कुल विविधता का अनुमान सांख्यिकीय रूप से सही है और बहुत अधिक गलत नहीं होगा। यह सूप के एक चम्मच को चखने जैसा है यह जानने के लिए कि क्या पूरा बर्तन नमकीन है।

प्रयोगों ने क्या दिखाया

लेखकों ने सिम्युलेटेड रोबोट टीमों (VMAS नामक सिस्टम का उपयोग करके) पर इनका परीक्षण किया और पाया:

गति: केवल 10% जोड़ों की जांच करके, उन्होंने विविधता गणना को 10 गुना तेज़ बना दिया।
सटीकता: 100 एजेंटों के साथ भी, "रैंडम सैंपलिंग" विधि वास्तविक विविधता का लगभग पूरी तरह से पता लगाती है।
नियंत्रण: उन्होंने इस तेज़ विधि का उपयोग रोबोट के व्यवहार को सक्रिय रूप से नियंत्रित करने के लिए किया (उन्हें अधिक या कम विविध होने के लिए कहना)। उन्होंने धीमे, पूर्ण तरीके का उपयोग करने की तुलना में उतनी ही अच्छी तरह से सीखा।
स्केल: उन्होंने 500 एजेंटों तक की टीमों पर इसका परीक्षण किया। पुराना तरीका इतना धीमा होता कि वह चल भी नहीं पाता, लेकिन नए तरीके ने इसे आसानी से संभाल लिया।

मुख्य निष्कर्ष (The Bottom Line)

Graph-SND पुराने डायवर्सिटी कैलकुलेटर का एक "ड्रॉप-इन" रिप्लेसमेंट है। यह "हर किसी की हर किसी के खिलाफ जांच करने" के असंभव कार्य को एक स्मार्ट, तेज़ और गणितीय रूप से सिद्ध शॉर्टकट से बदल देता है।

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

पेपर का दावा है कि यह AI टीमों को गणितीय गणनाओं में उलझे बिना बड़ा और स्मार्ट बनने की अनुमति देता है। यह नए प्रकार की समस्याओं को हल करने का दावा नहीं करता है, बल्कि उन समस्याओं को मापने के "बॉटलनेक" (रुकावट) को हल करता है जिन्हें हम पहले से ही जानते हैं।

तकनीकी सारांश: Graph-SND: मल्टी-एजेंट सुदृढीकरण शिक्षण (MARL) में व्यवहारिक विविधता के लिए स्पार्स एग्रीगेशन

1. समस्या विवरण

मल्टी-एजेंट सुदृढीकरण शिक्षण (MARL) में, सिस्टम न्यूरल डायवर्सिटी (SND) एक मीट्रिक है जिसका उपयोग एजेंटों के बीच व्यवहारिक विषमता (heterogeneity) को मापने के लिए किया जाता है, जो उनके एक्शन डिस्ट्रीबशंस के बीच पेयरवाइज वासरस्टीन दूरियों (Wasserstein distances) का औसत लेकर निकाला जाता है। जबकि SND विविधता नियंत्रण (जैसे, DiCo एल्गोरिदम के माध्यम से) को सक्षम बनाता है, इसकी गणना एक गंभीर स्केलेबिलिटी बाधा प्रस्तुत करती है। पूर्ण SND की गणना करने के लिए सभी $\binom{n}{2}$ एजेंट जोड़ों का मूल्यांकन करना आवश्यक है, जिसके परिणामस्वरूप एजेंटों की संख्या $n$ में द्विघाती $O(n^2)$ जटिलता आती है। यह एग्रीगेशन लागत बड़े पैमाने की टीमों के लिए निषेधात्मक हो जाती है, जिससे विविधता-जागरूक प्रशिक्षण और नियंत्रण का व्यावहारिक अनुप्रयोग सीमित हो जाता है। यह शोध पत्र "सबग्रुप-टू-सिस्टम एग्रीगेशन" चरण को प्राथमिक खुली चुनौती के रूप में पहचानता है, यह नोट करते हुए कि मौजूदा मीट्रिक्स सभी-जोड़ों के औसत को एक निश्चित, गैर-परक्राम्य आवश्यकता के रूप में देखते हैं।

2. कार्यप्रणाली: Graph-SND

लेखक Graph-SND पेश करते हैं, जो SND का एक सामान्यीकरण है जो पूर्ण-ग्राफ औसत को एक मनमाने ग्राफ $G = (A, E, w)$ के किनारों (edges) पर एक भारित औसत (weighted average) से बदल देता है।

परिभाषा

मान लीजिए कि $d(i, j)$ एजेंट $i$ और $j$ के बीच मोंटे कार्लो व्यवहारिक दूरी है। Graph-SND को इस प्रकार परिभाषित किया गया है:
$\text{SND}_G(D, G) = \frac{1}{W(G)} \sum_{\{i,j\} \in E} w_{ij} d(i, j)$
जहाँ $W(G) = \sum_{\{i,j\} \in E} w_{ij}$ कुल किनारा भार (total edge weight) है।

तीन परिचालन व्यवस्थाएं (Operational Regimes)

यह ढांचा ग्राफ $G$ के चयन के आधार पर तीन अलग-अलग व्यवस्थाओं का समर्थन करता है:

सटीक रिकवरी ( $G = K_n$ ): जब $G$ यूनिट वेट्स के साथ एक पूर्ण ग्राफ (complete graph) है, तो Graph-SND मूल SND को सटीक रूप से रिकवर करता है।
स्थानीयकृत विविधता (निश्चित स्पार्स ग्राफ): जब $G$ एक निश्चित स्पार्स ग्राफ है (जैसे, $k$ -निकटतम पड़ोसी, संचार टोपोलॉजी), तो मीट्रिक केवल कार्य-प्रासंगिक अंतःक्रियाओं पर विविधता को मापता है। यह कम्प्यूटेशनल लागत को $O(|E|)$ तक कम कर देता है।
स्पार्स एस्टीमेशन (रैंडम ग्राफ): जब किनारों को रैंडमली सैंपल किया जाता है (जैसे, बर्नौली सैंपलिंग), तो Graph-SND पूर्ण SND के एक स्पार्स एस्टीमेटर के रूप में कार्य करता है।
- अनबायस्ड एस्टीमेशन: हॉरविट्ज़-थॉम्पसन वेट्स ( $w_{ij} = 1/p$ ) का उपयोग करके, एस्टीमेटर बिना किसी शर्त के अनबायस्ड (unbiased) है।
- कंसंट्रेशन: नॉर्मलाइज्ड सैंपल मीन (यूनिफॉर्म वेट्स) होफडिंग-टाइप कंसंट्रेशन बाउंड्स को संतुष्ट करता है, जो $m$ (सैंपल किए गए किनारों की संख्या) के लिए $O(1/\sqrt{m})$ दर से वास्तविक SND की ओर अभिसरित होता है।

सैद्धांतिक सीमाएं (Theoretical Bounds)

डिटरमिनिस्टिक डिस्ट्रोशन: निश्चित जुड़े हुए ग्राफों के लिए, शोध पत्र एज फॉरवर्डिंग इंडेक्स $\pi(G)$ का उपयोग करके $\text{SND}_G$ को $\text{SND}$ से संबंधित करने वाले बाउंड्स व्युत्पन्न करता है। विशेष रूप से, $|\text{SND}_G - \text{SND}|$ $\pi(G)$ से जुड़े कारकों द्वारा सीमित है।
एक्सपैंडर ग्राफ्स: रैंडम $d$ -रेगुलर एक्सपैंडर ग्राफों के लिए, फॉरवर्डिंग इंडेक्स $O(n \log n / d)$ स्केल करता है। लेखक सिद्ध करते हैं कि $d = \Theta(\log n)$ के साथ, वर्स्ट-केस रिलेटिव डिस्ट्रोशन $O(\log n)$ है।
स्पेक्ट्रल रिफाइनमेंट: लो-रैंक डिस्टेंस स्ट्रक्चर (नियंत्रित नॉर्मलाइज्ड न्यूक्लियर नॉर्म) के तहत, एक्सपैंडर्स के लिए एरर बाउंड $O(\rho^*/\sqrt{d})$ में सुधर जाता है, जो प्रायोगिक निकट-इकाई अनुपातों (near-unit ratios) की व्याख्या करता है।
प्रोबेबिलिस्टिक बाउंड्स: रैंडम $d$ -रेगुलर ग्राफों के लिए, एक अनकंडीशनल प्रोबेबिलिस्टिक बाउंड $\tilde{O}(D_{\max}/\sqrt{n})$ स्थापित किया गया है।

3. मुख्य योगदान

Graph-SND की परिभाषा: एक स्पार्स एग्रीगेशन लेयर जो पूर्ण ग्राफ पर SND को रिकवर करती है और प्री-कंप्यूटेड ग्राफों पर $O(|E|)$ लागत लेती है।
सैद्धांतिक गारंटी: रिकवरी, नॉन-नेगेटिविटी, ग्राफ-ऑटोमोर्फिज्म इनवेरिएंस, हॉरविट्ज़-थॉम्पसन अनबायस्डनेस, और कंसंट्रेशन इनइक्वेलिटीज (होफडिंग/सेर्फलिंग) के प्रमाण। शोध पत्र निश्चित ग्राफों के लिए डिटरमिनिस्टिक डिस्ट्रोशन बाउंड्स और रैंडम रेगुलर ग्राफों के लिए अनकंडीशनल प्रोबेबिलिस्टिक बाउंड्स भी स्थापित करता है।
प्रायोगिक सत्यापन:
- रिकवरी और अनबायस्डनेस: VMAS वातावरण में सत्यापित किया गया, जो $K_4$ पर सटीक रिकवरी और $n=8$ पर हॉरविट्ज़-थॉम्पसन एस्टीमेटर की अनबायस्डनेस दिखाता है।
- स्केलेबिलिटी: $n=500$ तक $\binom{n}{2}/|E|$ की वॉल-क्लॉक स्पीडअप प्रदर्शित की गई।
- क्लोज्ड-लूप कंट्रोल: DiCo डायवर्सिटी कंट्रोलर में Graph-SND को एकीकृत किया गया। $n=50$ पर, Bernoulli-0.1 Graph-SND ने सब-1% रिलेटिव एरर के साथ सेट-पॉइंट्स को ट्रैक किया और पूर्ण SND की तुलना में शून्य के करीब रिवॉर्ड अंतर पैदा किया, जबकि प्रति-कॉल मीट्रिक लागत को $\sim 9.5\times$ कम कर दिया।
- एक्सपैंडर प्रदर्शन: रैंडम $d$ -रेगुलर एक्सपैंडर्स ने $\Theta(n \log n)$ किनारों पर $\text{SND}_G/\text{SND} \in [0.9987, 1.0013]$ प्राप्त किया, जो डिस्ट्रोशन-टू-कॉस्ट रेशियो में अन्य स्पार्स बेसलाइन्स से काफी बेहतर प्रदर्शन करता है।

4. परिणाम

दक्षता: $n=100$ के साथ 500-इटरेशन PPO रन में, Bernoulli-0.1 Graph-SND ने पूर्ण SND को ट्रैक किया और प्रति-कॉल मीट्रिक समय को लगभग $10\times$ कम कर दिया।
स्केलेबिलिटी: $n=500$ तक फ्रोजन-पॉलिसी GPU टाइमिंग ने अनुमानित $\binom{n}{2}/|E|$ स्पीडअप की पुष्टि की, जिससे $n=500$ पर 10% एज डेंसिटी के साथ मीट्रिक समय ~15.5 सेकंड से घटकर ~1.5 सेकंड रह गया।
कंट्रोल स्टेबिलिटी: $n=50$ पर DiCo प्रयोगों में, स्पार्स कंट्रोलर ने सेट-पॉइंट ट्रैकिंग बनाए रखी और नौ मैच किए गए सेल्स में शून्य के करीब पेयर्ड रिवॉर्ड डिफरेंस दिया, जिसमें औसत रिवॉर्ड अंतर $-6.2 \times 10^{-4}$ था।
मजबूती (Robustness): विधि ने नॉन-गौसियन सेटिंग्स (कैटेगोरिकल पॉलिसी और टोटल वेरिएशन डिस्टेंस के साथ PettingZoo MPE) में सफलतापूर्वक ट्रांसफर किया, जिसमें छोटा बायस और लागत में कमी बनी रही।

5. महत्व और दावे

शोध पत्र का दावा है कि Graph-SND सफलतापूर्वक SND के एग्रीगेशन बॉटलनेक को हटा देता है, बिना इसके मीट्रिक के अर्थ को बदले या पॉलिसी आर्किटेक्चर या प्रशिक्षण एल्गोरिदम में बदलाव की आवश्यकता के।

ड्रॉप-इन विकल्प: यह एक "ड्रॉप-इन स्पार्स विकल्प" प्रदान करता है जो पूर्ण-ग्राफ SND से परे स्केल करता है, जो निष्क्रिय माप (passive measurement) और क्लोज्ड-लूप डायवर्सिटी कंट्रोल दोनों का समर्थन करता है।
सिमेंटिक लचीलापन: ग्राफ $G$ $G$ को केवल एक पैरामीटर के रूप में नहीं, बल्कि एक विचारशील विकल्प के रूप में प्रस्तुत किया गया है जो माप लक्ष्य को निर्धारित करता है:
- पूर्ण सिस्टम डायवर्सिटी का अनुमान लगाने के लिए Bernoulli sampling का उपयोग करें।
- विशिष्ट अंतःक्रिया संरचनाओं के लिए प्रासंगिक विविधता को मापने के लिए फिक्स्ड लोकल ग्राफ्स (जैसे, कम्युनिकेशन, $k$ -NN) का उपयोग करें।
- मजबूत वर्स्ट-केस स्ट्रक्चरल गारंटी के साथ डिटरमिनिस्टिक, निकट-लीनियर स्पार्स प्रॉक्सी के लिए एक्सपैंडर ग्राफ्स का उपयोग करें।
मामूली सीमाएं: लेखक स्वीकार करते हैं कि हालांकि एक्सपैंडर्स के लिए सैद्धांतिक बाउंड $O(\log n)$ हैं, देखे गए निकट-इकाई अनुपात डेटा-निर्भर हैं और आंशिक रूप से MARL डिस्टेंस मैट्रिसेस के स्पेक्ट्रल गुणों द्वारा स्पष्ट किए जाते हैं। वे यह भी नोट करते हैं कि वर्तमान प्रयोग स्वतंत्र PPO पर केंद्रित हैं, जबकि सेंट्रलाइज्ड-क्रिटिक एल्गोरिदम भविष्य के कार्य के लिए छोड़े गए हैं।

संक्षेप में, Graph-SND डायवर्सिटी एग्रीगेशन को एक ग्राफ-सिलेक्शन समस्या के रूप में पुनर्गठित करता है, जो MARL में व्यवहारिक विविधता के लिए सैद्धांतिक गारंटी के साथ कम्प्यूटेशनल दक्षता का संतुलन प्रदान करता है।