⚡ electrical engineering

Cooperative Bandit Learning in Directed Networks with Arm-Access Constraints

यह शोध पत्र विषम आर्म एक्सेस (heterogeneous arm access) वाले निर्देशित नेटवर्क में मल्टी-एजेंट मल्टी-आर्म्ड बैंडिट समस्याओं के लिए एक वितरित सर्वसम्मति-आधारित UCB एल्गोरिदम प्रस्तावित करता है, यह सिद्ध करते हुए कि एक द्रव्यमान-संरक्षण सूचना मिश्रण तंत्र (mass-preserving information mixing mechanism) असममित संचार और आंशिक आर्म उपलब्धता के बावजूद सभी एजेंटों के लिए लघुगणकीय पछतावा (logarithmic regret) प्राप्त करता है।

मूल लेखक: Evagoras Makridis, Themistoklis Charalambous

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

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

CC BY 4.0

मूल लेखक: Evagoras Makridis, Themistoklis Charalambous

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

कल्पना कीजिए कि दोस्तों का एक समूह एक विशाल शहर में सबसे अच्छा रेस्टोरेंट खोजने की कोशिश कर रहा है, लेकिन उनके पास कुछ बहुत ही विशिष्ट नियम और सीमाएं हैं। यह उस शोध पत्र (paper) का मूल सार है, जो कोऑपरेटिव बैंडिट लर्निंग (Cooperative Bandit Learning) नामक समस्या से संबंधित है।

यहाँ सरल उपमाओं (analogies) का उपयोग करके इसका विवरण दिया गया है:

1. परिवेश: "रेस्टोरेंट की खोज"

कंप्यूटर विज्ञान की दुनिया में, इसे मल्टी-आर्म्ड बैंडिट (Multi-Armed Bandit) समस्या कहा जाता है।

आर्म्स (Arms): इन्हें अलग-अलग स्लॉट मशीन या हमारे उदाहरण में, अलग-अलग रेस्टोरेंट्स के रूप में सोचें।
लक्ष्य: आप उस एक रेस्टोरेंट को खोजना चाहते हैं जो सबसे अच्छा खाना (उच्चतम रिवॉर्ड) परोसता है ताकि आप हर दिन वहीं खा सकें।
समस्या: शुरुआत में आपको नहीं पता कि कौन सा सबसे अच्छा है। आपको सीखने के लिए उन्हें आज़माना (explore) पड़ता है, लेकिन आप उन अच्छे रेस्टोरेंट्स में भी जाना चाहते हैं जिन्हें आपने पहले ही खोज लिया है (exploit)। यदि आप लगातार खराब रेस्टोरेंट्स आज़माते रहते हैं, तो आपको "पछतावा" (regret) होता है (आपने समय और पैसा बर्बाद किया)।

2. ट्विस्ट: "विशेषज्ञ मित्र"

अधिकांश पुराने अध्ययनों में, समूह में हर कोई शहर के किसी भी रेस्टोरेंट में जा सकता था। लेकिन वास्तविक दुनिया में ऐसा नहीं है।

आर्म-एक्सेस कंस्ट्रेंट्स (Arm-Access Constraints): कल्पना कीजिए कि आपके दोस्तों का समूह शहर के विभिन्न हिस्सों में बिखरा हुआ है।
- एलिस केवल इटालियन डिस्ट्रिक्ट के पास रहती है, इसलिए वह केवल इटालियन रेस्टोरेंट्स में जा सकती है।
- बॉब के पास केवल एक साइकिल है, इसलिए वह केवल 2 मील के दायरे में आने वाले कैफे तक ही पहुँच सकता है।
- चार्ली के पास कार है लेकिन उसे सीफूड (seafood) से एलर्जी है, इसलिए वह मछली वाले स्थानों पर नहीं जा सकता।
चुनौती: कोई भी अकेला व्यक्ति शहर के हर रेस्टोरेंट में नहीं जा सकता। यदि एलिस कभी उस बेहतरीन सुशी (sushi) प्लेस पर नहीं जाती, तो उसे कभी पता नहीं चलेगा कि वह सबसे अच्छा है। उसे मदद की ज़रूरत है।

3. जटिलता: "वन-वे स्ट्रीट" नेटवर्क

अब, कल्पना कीजिए कि ये दोस्त एक अजीब से मैसेजिंग ऐप के माध्यम से संवाद करते हैं।

डायरेक्टेड ग्राफ्स (Directed Graphs): कुछ दोस्त दूसरों को टेक्स्ट कर सकते हैं, लेकिन वे दूसरे वापस टेक्स्ट नहीं कर सकते।
- एलिस बॉब को टेक्स्ट कर सकती है।
- बॉब चार्ली को टेक्स्ट कर सकता है।
- लेकिन चार्ली एलिस को टेक्स्ट नहीं कर सकता।
समस्या: सूचना का प्रवाह एकतरफा है। यदि चार्ली को एक बेहतरीन सुशी प्लेस मिलता है, तो वह बॉब को बताता है, जो फिर एलिस को बताता है। लेकिन अगर एलिस को एक बेहतरीन पिज्जा प्लेस मिलता है, तो बॉब को तो पता चलता है, लेकिन चार्ली को इसके बारे में कभी पता नहीं चलता क्योंकि संदेश वापस नहीं जा सकता। इससे सूचना में "ट्रैफिक जाम" पैदा होता है।

4. समाधान: "स्मार्ट ग्रुप चैट" (A2C-UCB)

इस पेपर के लेखकों ने इन दोस्तों के सहयोग करने का एक नया तरीका बनाया है, जिसे A2C-UCB कहा जाता है। यह सरल भाषा में इस प्रकार काम करता है:

A. "मास-प्रिजर्विंग" मैसेंजर (द्रव्यमान-संरक्षण करने वाला संदेशवाहक)
आमतौर पर, जब लोग वन-वे स्ट्रीट में जानकारी साझा करते हैं, तो संदेश विकृत हो जाता है। यदि बॉब 10 लोगों से बात करता है, तो उसकी राय कमज़ोर पड़ जाती है।

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

B. "कॉन्फिडेंस स्कोर" (विश्वास स्कोर)
रेस्टोरेंट चुनने का निर्णय लेते समय, एल्गोरिदम एक "कॉन्फिडेंस स्कोर" का उपयोग करता है।

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

5. परिणाम: यह क्यों मायने रखता है

यह पेपर दो मुख्य बातें सिद्ध करता है:

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

बड़ा चित्र मेटाफर (The Big Picture Metaphor)

एक जासूस टीम की कल्पना करें जो एक रहस्य सुलझा रही है।

पुराना तरीका: प्रत्येक जासूस अकेले काम करता है। यदि जासूस A केवल रसोई देख सकता है और जासूस B केवल बेडरूम देख सकता है, तो वे हॉलवे में मिले उस सुराग को मिस कर सकते हैं जो केस को सुलझाने के लिए ज़रूरी था।
नया तरीका (यह पेपर): वे अपने नोट्स साझा करते हैं। लेकिन क्योंकि जासूस A सीधे जासूस C से बात नहीं कर सकता, इसलिए उन्हें अपने नोट्स जासूस B के माध्यम से भेजने पड़ते हैं। नया एल्गोरिदम यह सुनिश्चित करता है कि भले ही इन उलझे हुए, एकतरफा नोट-पासिंग नियमों के साथ काम करना पड़े, फिर भी प्रत्येक जासूस के पास मौजूद अंतिम "केस फ़ाइल" 100% सटीक है। वे अकेले की तुलना में मिलकर रहस्य को तेज़ी से सुलझाते हैं।

संक्षेप में: यह पेपर कंप्यूटर को यह सिखाता है कि सीमित उपकरणों और एकतरफा संचार के बावजूद कुशलतापूर्वक एक साथ कैसे काम किया जाए। यह सुनिश्चित करता है कि चाहे कोई भी क्या देख सकता है, पूरा समूह सच्चाई को सीख ही लेगा।

यहाँ शोध पत्र "Cooperative Bandit Learning in Directed Networks with Arm-Access Constraints" का विस्तृत तकनीकी सारांश दिया गया है:

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

यह शोध पत्र मल्टी-एजेंट मल्टी-आर्म्ड बैंडिट (MAMAB) समस्या को दो विशिष्ट, यथार्थवादी बाधाओं के तहत संबोधित करता है जिन्हें अक्सर शास्त्रीय साहित्य में अनदेखा किया जाता है:

निर्देशित संचार नेटवर्क (Directed Communication Networks): एजेंट एक निर्देशित ग्राफ (digraph) पर संचार करते हैं जो असंतुलित हो सकता है। यह असममित सूचना प्रवाह (asymmetric information flow) पैदा करता है, जिसका अर्थ है कि मानक औसत सहमति तंत्र (averaging consensus mechanisms) वैश्विक सांख्यिकी को संरक्षित नहीं कर पाते या बिना किसी पूर्वाग्रह (bias) के वास्तविक माध्य तक नहीं पहुँच पाते।
विषम आर्म-एक्सेस बाधाएं (Heterogeneous Arm-Access Constraints): एजेंटों के पास सभी उपलब्ध 'आर्म्स' (arms) तक पहुँच नहीं होती है। प्रत्येक एजेंट $i$ केवल आर्म्स के एक विशिष्ट उपसमूह $K_i \subseteq K$ तक ही पहुँच सकता है। फलस्वरूप, कोई भी एकल एजेंट वैश्विक इष्टतम (globally optimal) आर्म तक पहुँच रखने की गारंटी नहीं देता, और एक विशिष्ट आर्म के सीखने की दर "जनरेशन मास" (generation mass - उन एजेंटों की संख्या जो उस आर्म को सैंपल करने में सक्षम हैं) पर निर्भर करती है।

उद्देश्य: लक्ष्य प्रत्येक एजेंट के लिए संचयी छद्म-पछतावा (cumulative pseudo-regret) को कम करना है। महत्वपूर्ण रूप से, पछतावा (regret) एजेंट के सर्वश्रेष्ठ सुलभ आर्म ( $\mu_i^*$ ) के सापेक्ष परिभाषित किया गया है, न कि वैश्विक इष्टतम के सापेक्ष, क्योंकि वैश्विक इष्टतम कुछ एजेंटों के लिए भौतिक रूप से अप्राप्य हो सकता है। यह शोध पत्र "बाधा-प्रेरित हानि" (constraint-induced loss - अप्राप्यता के कारण अपरिहार्य रैखिक पछतावा) और "सीखने योग्य पछतावा" (learnable regret - सीखने की गतिशीलता के कारण उप-रैखिक पछतावा) के बीच अंतर करता है।

2. कार्यप्रणाली: A2C-UCB एल्गोरिदम

लेखक A2C-UCB (Arm Access Constrained Cooperative Upper Confidence Bound) प्रस्तावित करते हैं, जो एक वितरित एल्गोरिदम है जो रेशियो कंसेंसस (Ratio Consensus) को UCB एक्सप्लोरेशन के साथ जोड़ता है।

मुख्य तंत्र:

द्रव्यमान-संरक्षण सूचना मिश्रण (Mass-Preserving Information Mixing):
निर्देशित और असंतुलित ग्राफों को संभालने के लिए, एल्गोरिदम एक रनिंग रेशियो कंसेंसस दृष्टिकोण का उपयोग करता है। साधारण औसत (जो निर्देशित ग्राफ में पूर्वाग्रह पैदा करता है) के बजाय, एजेंट प्रत्येक आर्म $k$ के लिए दो रनिंग सम (running sums) बनाए रखते हैं:
1. $\hat{s}_i^k(t)$ : संचयी रिवॉर्ड अनुमान।
2. $\hat{n}_i^k(t)$ : संचयी पुल काउंट (pull count) अनुमान।
  इनका अपडेट आउट-डिग्री (out-degrees) के आधार पर कॉलम-स्टोकेस्टिक वेट्स का उपयोग करके किया जाता है। एजेंट $\hat{\mu}_i^k(t) = \hat{s}_i^k(t) / \hat{n}_i^k(t)$ की गणना करते हैं ताकि नेटवर्क-व्यापी अनुभवजन्य माध्य (empirical mean) का निष्पक्ष अनुमान प्राप्त किया जा सके, भले ही वे स्वयं उस आर्म को न खींच सकें।
संरचनात्मक मापदंडों का वितरित अनुमान (Distributed Estimation of Structural Parameters):
चूंकि एजेंटों को वैश्विक टोपोलॉजी या यह जानकारी नहीं होती कि कौन से एजेंट किन आर्म्स तक पहुँच सकते हैं, उन्हें दो महत्वपूर्ण मात्राओं का स्थानीय स्तर पर अनुमान लगाना होता है:
1. वैश्विक पुल काउंट ( $\hat{\nu}_i^k(t)$ ): पूरे नेटवर्क में कितनी बार आर्म $k$ को खींचा गया है।
2. जनरेशन मास ( $\hat{g}_i^k(t)$ ): उन एजेंटों की संख्या जो आर्म $k$ तक पहुँचने में सक्षम हैं।
  एल्गोरिदम सहायक चरों ( $\hat{y}_i(t)$ और $\hat{u}_i^k(t)$ ) का उपयोग करता है जिन्हें कंसेंसस के माध्यम से अपडेट किया जाता है। अनुपात लेकर (जैसे, $\hat{n}_i^k(t) / \hat{y}_i(t)$ ), एजेंट निर्देशित ग्राफ के कारण होने वाले स्टेशनरी डिस्ट्रीब्यूशन बायस को समाप्त कर देते हैं, जिससे वे वास्तविक वैश्विक औसतों को अतुल्य रूप से ट्रैक कर पाते हैं।
नेटवर्क-जागरूक UCB इंडेक्स (Network-Aware UCB Index):
निर्णय नीति एक संशोधित UCB इंडेक्स का उपयोग करती है:
$Q_i^k(t) = \hat{\mu}_i^k(t) + \sqrt{\frac{\alpha \log(t \hat{g}_i^k(t))}{\hat{\nu}_i^k(t)}}$
- हर (denominator) $\hat{\nu}_i^k(t)$ प्रभावी वैश्विक नमूना आकार को दर्शाता है।
- लॉगैरिदम में $\hat{g}_i^k(t)$ का पद एक सुधार कारक (correction factor) के रूप में कार्य करता है: यदि कोई आर्म बहुत कम एजेंटों के लिए सुलभ है (कम जनरेशन मास), तो सूचना प्रसार की धीमी गति की भरपाई के लिए एक्सप्लोरेशन बोनस को बढ़ाया जाता है।

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

संरचनात्मक सीमाओं का औपचारिक लक्षण वर्णन: यह शोध पत्र "जनरेशन मास" की अवधारणा पेश करता है और पछतावे को अपरिहार्य संरचनात्मक हानि (अप्राप्यता के कारण) और सीखने योग्य पछतावे में औपचारिक रूप से विभाजित करता है। यह सिद्ध करता है कि सीखने की गति मौलिक रूप से नेटवर्क टोपोलॉजी और आर्म-एक्सेसिबिलिटी बाधाओं के मिलन बिंदु से जुड़ी है।
निष्पक्ष वितरित अनुमान: पिछले कार्यों के विपरीत जो रो-स्टोकेस्टिक मिक्सिंग (जो निर्देशित ग्राफ में पूर्वाग्रह लाता है) का उपयोग करते हैं या पूर्ण आर्म एक्सेस मानते हैं, यह कार्य एक सम-संरक्षण रेशियो कंसेंसस (sum-preserving ratio consensus) का उपयोग करता है। यह सुनिश्चित करता है कि विषम संचार और विषम एक्सेस के बावजूद नेटवर्क में रिवॉर्ड अनुमान निष्पक्ष रहें।
लॉगैरिथमिक पछतावा गारंटी: लेखक सिद्ध करते हैं कि मानक स्टोकेस्टिक धारणाओं के तहत, प्रस्तावित एल्गोरिदम प्रत्येक एजेंट के लिए लॉगैरिथमिक पछतावा ( $O(\log T)$ $O (lo g T)$ ) प्राप्त करता है। पछतावा बाउंड स्पष्ट रूप से इन पर निर्भर करता है:
- सुलभ आर्म्स का सब-ऑप्टिमलिटी गैप।
- नेटवर्क मिक्सिंग गुण (कंसेंसस मैट्रिक्स का स्पेक्ट्रल गैप)।
- आर्म एक्सेसिबिलिटी संरचना (जनरेशन मास)।

4. परिणाम

सैद्धांतिक विश्लेषण:
- लेम्मा 1 और 2: स्थापित करते हैं कि रनिंग रेशो कंसेंसस, निर्देशित ग्राफों में भी, सीमित त्रुटि के साथ वास्तविक नेटवर्क-व्यापी सांख्यिकी को ट्रैक करता है।
- प्रमेय 1: सिद्ध करता है कि प्रत्येक एजेंट के लिए अपेक्षित पछतावा $\log T$ के साथ स्केल होने वाले एक पद और नेटवर्क टोपोलॉजी एवं एक्सेसिबिलिटी बाधाओं पर निर्भर एक स्थिरांक (constant term) द्वारा सीमित है।
सिमुलेशन:
- परिदृश्य: 7 सर्वरों (आर्म्स) तक सीमित पहुँच वाले 6 एज डिवाइसेस का एक नेटवर्क।
- तुलना 1 (गैर-सहकारी बनाम): A2C-UCB स्वतंत्र UCB1 एजेंटों की तुलना में काफी बेहतर प्रदर्शन करता है। सहयोग एजेंटों को उन आर्म्स के बारे में सीखने की अनुमति देता है जिन्हें वे सीधे नहीं खींच सकते, जिससे संचयी पछतावा काफी कम हो जाता है।
- तुलना 2 (स्टेट-ऑफ-द-आर्ट बनाम): ज़ु (Zhu) एट अल. [17] के एक सहकारी एल्गोरिदम (जो पूर्ण आर्म एक्सेस मानता है) की तुलना में, A2C-UCB पूर्ण-एक्सेस परिदृश्यों में भी बेहतर प्रदर्शन करता है और आंशिक एक्सेस बाधाओं के तहत काम करने में सक्षम एकमात्र विधि है।

5. महत्व

यह कार्य नेटवर्क टोपोलॉजी और एक्शन स्पेस बाधाओं के बीच के जुड़ाव को संबोधित करके सहयोगात्मक शिक्षण सिद्धांत में एक महत्वपूर्ण अंतर को पाटता है।

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

संक्षेप में, यह शोध पत्र निर्देशित और बाधित वातावरण में सहयोगात्मक शिक्षण के लिए एक कठोर ढांचा प्रदान करता है, और यह सिद्ध करता है कि एजेंट नेटवर्क और उपलब्ध क्रियाओं (actions) दोनों के अधूरे स्थानीय दृश्यों के बावजूद इष्टतम शिक्षण दर प्राप्त कर सकते हैं।