🤖 machine learning

A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming

यह शोध पत्र LinMatch प्रस्तुत करता है, जो मल्टी-ह्यूमन मल्टी-रोबोट टीमिंग के लिए एक ऑनलाइन लर्निंग एल्गोरिदम है, जो असाइनमेंट समस्या को लीनियर मैचिंग बैंडिट के रूप में स्वरूपित करता है, हंगेरियन एल्गोरिदम के माध्यम से मैक्सिमम वेटेड मैचिंग को हल करके $\tilde{\Theta}(d\sqrt{MKT})$ के स्ट्रिक्टली ऑप्टिमल रिग्रेट बाउंड्स प्राप्त करता है, और हाउसिंग एलोकेशन और रिकमेंडेशन सिस्टम जैसे व्यापक अनुप्रयोगों तक विस्तारित होता है।

मूल लेखक: Yaohui Guo, X. Jessie Yang, Cong Shi

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

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

CC BY 4.0

मूल लेखक: Yaohui Guo, X. Jessie Yang, Cong Shi

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

मुख्य चित्र: रोबोट और इंसानों के लिए "ब्लाइंड डेट"

कल्पना कीजिए कि आप एक व्यस्त कार्यक्रम चला रहे हैं जहाँ आपके पास रोबोटों का एक निश्चित समूह है (मान लीजिए 20 रोबोट) और इंसानों का एक समूह है (मान लीजिए 10 इंसान) जो शिफ्ट में आते हैं। हर घंटे, 10 इंसानों का एक नया समूह आता है, और आपको कार्य को पूरा करने के लिए प्रत्येक इंसान को एक रोबोट के साथ जोड़ना होता है।

लक्ष्य सरल है: सभी जोड़ों की कुल खुशी (इनाम/रिवॉर्ड) को अधिकतम करना।

चुनौती: आप रोबोटों को बहुत अच्छी तरह से नहीं जानते।

आप इंसानों को जानते हैं: आप उनके कौशल, उनके व्यक्तित्व और वे किन चीजों में अच्छे हैं (उनके "फीचर्स") को जानते हैं।
आप रोबोटों को नहीं जानते: वे जटिल मशीनें हैं जिनमें छिपी हुई क्षमताएं हैं। आप नहीं जानते कि रोबोट #5 भारी बक्से उठाने में माहिर है या रोबोट #12 नाजुक असेंबली में बेहतर है। आप केवल उन्हें आपस में जोड़कर और यह देखकर पता लगाते हैं कि वे एक साथ कितनी अच्छी तरह काम करते हैं।

यह एक क्लासिक "करते-करते सीखना" (learning while doing) वाली समस्या है। यदि आप गलत अनुमान लगाते हैं, तो टीम विफल हो जाती है। यदि आप सही अनुमान लगाते हैं, तो वे सफल होते हैं। लेकिन आप केवल रैंडम अनुमान नहीं लगा सकते; आपको खराब जोड़ियों पर बहुत अधिक समय बर्बाद किए बिना रोबोटों के बारे में तेजी से सीखने के लिए एक स्मार्ट रणनीति की आवश्यकता है।

समस्या: बहुत सारे विकल्प, बहुत कम समय

यदि आप हर संभव रोबोट-इंसान संयोजन को एक-एक करके सीखने की कोशिश करेंगे, तो आप हमेशा के लिए फंस जाएंगे। 20 रोबोट और 10 इंसानों के साथ, उन्हें जोड़ने के संभावित तरीकों की संख्या अत्यधिक है (जैसे रेगिस्तान में रेत का एक विशिष्ट कण ढूंढना)। इसे "कॉम्बिनेटोरियल एक्सप्लोजन" (combinatorial explosion) कहा जाता है।

इसके अलावा, रोबोट "ब्लैक बॉक्स" हैं। आप उनके कोड को देखकर यह नहीं जान सकते कि वे कैसे काम करते; आपको उनका परीक्षण करना ही होगा।

समाधान: "LinMatch" (एक आशावादी मैचमेकर)

लेखकों ने LinMatch नामक एक नया एल्गोरिदम प्रस्तावित किया है। इसे एक सुपर-स्मार्ट मैचमेकर के रूप में सोचें जो "अनिश्चितता के सामने आशावाद" (Optimism in the Face of Uncertainty) नामक एक विशेष ट्रिक का उपयोग करता है।

LinMatch इस प्रकार काम करता है, चरण-दर-चरण:

"अनुमान लगाने का खेल" (कॉन्फिडेंस इंटरवल):
चूंकि रोबोट रहस्यमय हैं, इसलिए LinMatch को उनकी वास्तविक क्षमताओं का पता नहीं है। इसके बजाय, यह प्रत्येक रोबोट के लिए "संभावनाओं की एक सीमा" बनाता है।

उपमा: कल्पना करें कि रोबोट #5 एक रहस्यमय बॉक्स है। LinMatch कहता है, "मैं 95% आश्वस्त हूँ कि रोबोट #5 'औसत' और 'सुपरस्टार' के बीच कहीं है।" यह उस चीज़ के आसपास जो LinMatch सोचता है कि रोबोट कर सकता है, एक सुरक्षा जाल (कॉन्फिडेंस इंटरवल) खींचता है।

"सर्वश्रेष्ठ स्थिति" (आशावाद):
जब मिलान करने का समय आता है, तो LinMatch किसी रोबोट को उसके औसत अनुमान के आधार पर नहीं चुनता। यह उस रोबोट के सबसे अच्छे संस्करण के आधार पर चुनता है जो अभी भी उसके सुरक्षा जाल के भीतर फिट बैठता है।

उपमा: यदि रोबोट #5 का सुरक्षा जाल कहता है कि वह एक 'सुपरस्टार' हो सकता है, तो LinMatch योजना बनाने के लिए उसे एक सुपरस्टार की तरह मानता है। यह मान लेता है कि जब तक अन्यथा सिद्ध न हो जाए, तब तक सबसे अच्छा सच है। यह सिस्टम को उन रोबोटों को आज़माने के लिए प्रोत्साहित करता जिनके बारे में वह अभी तक ज्यादा नहीं जानता है, क्योंकि वे अद्भुत हो सकते हैं।

"हंगेरियन एल्गोरिदम" (कुशल समाधानकर्ता):
एक बार जब LinMatch के पास प्रत्येक संभावित जोड़ी के लिए ये "सर्वश्रेष्ठ-मामले" वाले स्कोर आ जाते हैं, तो उसे एक विशाल पहेली सुलझानी होती है: "मैं इन 10 इंसानों को 20 रोबोटों के साथ कैसे जोड़ूँ ताकि उच्चतम कुल स्कोर प्राप्त हो सके?"

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

सीखना और अपडेट करना:
रोबोटों और इंसानों के एक साथ काम करने के बाद, LinMatch को फीडबैक मिलता है (क्या वे सफल रहे? वे कितने तेज़ थे?)। यह रोबोटों के आसपास के "सुरक्षा जाल" को छोटा करने के लिए इस नए डेटा का उपयोग करता है।

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

यह पेपर एक बड़ी बात क्यों है

लेखकों ने केवल एक टूल नहीं बनाया; उन्होंने साबित किया है कि यह इस विशिष्ट काम के लिए सबसे अच्छा संभव टूल है।

स्पीड रिकॉर्ड: उन्होंने गणितीय रूप से सिद्ध किया कि उनका एल्गोरिदम भौतिक रूप से संभव जितनी तेजी से सीख सकता है, उतनी तेजी से सीखता है। कोई अन्य एल्गोरिदम LinMatch की तुलना में रोबोटों के बारे में महत्वपूर्ण रूप से तेजी से नहीं सीख सकता।
फॉर्मूला: उन्होंने दिखाया कि एल्गोरिदम द्वारा की जाने वाली "गलतियाँ" (रिग्रेट) समय के साथ बहुत धीरे-धीरे बढ़ती हैं। यह एक "सबलीनियर" (sublinear) विकास है, जिसका अर्थ है कि सिस्टम बेहतर और बेहतर होता जाता है, और सीखने की लागत समय के साथ नगण्य हो जाती है।
रोबोट्स से परे: हालांकि उन्होंने रोबोटों और इंसानों का उदाहरण दिया, लेकिन यह गणित किसी भी ऐसी स्थिति में काम करता है जहाँ आपको दो समूहों को जोड़ना होता है जहाँ एक पक्ष अज्ञात हो।
- पेपर में उल्लेखित उदाहरण: आवास आवंटन (housing allocation), अनुशंसा प्रणाली (recommendation systems - उपयोगकर्ताओं को उत्पादों से मिलाना), और कार्य असाइनमेंट।

सारांश

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

समस्या का निरूपण (Problem Formulation)
यह शोध पत्र ऑनलाइन मल्टी-ह्यूमन मल्टी-रोबोट टीमिंग की चुनौती को संबोधित करता है, जो एक ऐसी स्थिति है जहाँ एक शिक्षार्थी (learner) को $T$ राउंड के दौरान $M$ मानव एजेंटों के विविध सेटों के साथ अज्ञात क्षमताओं वाले $K$ रोबोटों के एक निश्चित पूल को आवंटित करना होता है। इसका उद्देश्य इन मानव-रोबोट टीमों द्वारा उत्पन्न संचयी पुरस्कार (cumulative reward) को अधिकतम करना है। इस समस्या को एक लीनियर मैचिंग बैंडिट फ्रेमवर्क के भीतर रखा गया है। मुख्य कठिनाई दो पहलुओं में निहित है: "असाध्य आर्म स्पेस" (intractable arm space), जहाँ प्रत्येक अद्वितीय मिलान (matching) को एक अलग बैंडिट आर्म मानने से घातीय वृद्धि (exponential growth) होती है, और "कॉम्बिनेटोरियल जटिलता" (combinatorial complexity), जहाँ मिलान संबंधी बाधाएं पुरस्कारों को आपस में जोड़ देती हैं और अनुकूलन (optimization) को जटिल बना देती हैं।

लेखक एक लीनियर रिवॉर्ड स्ट्रक्चर का अनुमान लगाते हैं जहाँ मानव एजेंट $m$ (ज्ञात फीचर वेक्टर $X_{m,t} \in \mathbb{R}^d$ के साथ) और रोबोट $k$ (अज्ञात फीचर वेक्टर $\theta_k \in \mathbb{R}^d$ के साथ) द्वारा बनाई गई टीम का अपेक्षित पुरस्कार आंतरिक गुणनफल (inner product) $X_{m,t}^\top \theta_k$ द्वारा दिया जाता है। जबकि मानव फीचर्स अवलोकन योग्य होते हैं (प्रोफाइल या कार्य संदर्भ से प्राप्त), रोबोट फीचर्स अज्ञात होते हैं क्योंकि उन्नत AI सिस्टम की जटिलता और पारदर्शिता की कमी होती है। शिक्षार्थी आने वाले मनुष्यों के फीचर्स को देखता है, एक मिलान (मानवों से रोबोटों तक एक इंजेक्शन फंक्शन) चुनता है, और शोर युक्त (noisy) पुरस्कार प्राप्त करता है।

कार्यप्रणाली: LinMatch एल्गोरिदम (Methodology: LinMatch Algorithm)
इसे हल करने के लिए, लेखक "अनिश्चितता के सामने आशावाद" (Optimism in the Face of Uncertainty - OFU) सिद्धांत पर आधारित एक ऑनलाइन लर्निंग एल्गोरिदम, LinMatch का प्रस्ताव करते हैं। यह एल्गोरिदम राउंड में संचालित होता है और निम्नलिखित चरणों से मिलकर बना है:

कॉन्फिडेंस इंटरवल निर्माण (Confidence Interval Construction): रिज़ रिज रिग्रेशन (ridge regression) का उपयोग करके, LinMatch प्रत्येक रोबोट के लिए अज्ञात फीचर वेक्टर्स $\theta_k$ का अनुमान लगाता है। यह ऐतिहासिक असाइनमेंट के आधार पर प्रत्येक रोबोट के लिए कोवेरिएंस मैट्रिक्स $V_{k,t}$ और रिवॉर्ड के भारित योग (weighted sum) $H_{k,t}$ को बनाए रखता है। यह प्रत्येक $\theta_k$ के लिए एक दीर्घवृत्तीय कॉन्फिडेंस इंटरवल (ellipsoidal confidence interval) $\hat{\Theta}_{k,t}$ के निर्माण की अनुमति देता है, जो यह सुनिश्चित करता है कि वास्तविक पैरामीटर उच्च संभावना के साथ इस अंतराल के भीतर रहे।
आशावादी मिलान (Optimistic Matching): प्रत्येक राउंड में, एल्गोरिदम एक "आशावादी" मिलान की गणना करता है। $\theta_k$ के पॉइंट एस्टीमेट्स का उपयोग करने के बजाय, यह कॉन्फिडेंस इंटरवल्स के भीतर उन पैरामीटर वेक्टर्स का चयन करता है जो कुल अपेक्षित पुरस्कार को अधिकतम करते हैं।
लीनियर प्रोग्रामिंग के माध्यम से कुशल समाधान (Efficient Solving via Linear Programming): एक प्रमुख तकनीकी योगदान आशावादी मिलान समस्या का पुनर्गठन है। लेखक प्रदर्शित करते हैं कि कॉन्फिडेंस सेट्स पर आंतरिक गुणनफल के योग को अधिकतम करने वाले मिलान को खोजने के लिए आवश्यक मिक्स्ड-इंटिजर प्रोग्राम को विघटित (decouple) किया जा सकता है। प्रत्येक मानव-रोबोट जोड़ी के लिए आशावादी रिवॉर्ड एस्टीमेट्स $\tilde{y}_{mk,t}$ को परिभाषित करके, समस्या एक द्विपक्षीय ग्राफ (bipartite graph) में मानक मैक्सिमम वेटेड मैचिंग समस्या में बदल जाती है। इसे हंगेरियन एल्गोरिदम (Hungarian algorithm) का उपयोग करके $O(K^3)$ समय में कुशलतापूर्वक हल किया जा सकता है।

प्रमुख योगदान और सैद्धांतिक परिणाम (Key Contributions and Theoretical Results)
यह शोध पत्र दो प्राथमिक योगदान देता है:

एल्गोरिद्मिक पुनर्गठन (Algorithmic Reformulation): यह प्रत्येक राउंड में आशावादी मिलिंग समस्या को मैक्सिमम वेटेड मैचिंग के लीनियर प्रोग्राम के रूप में पुनर्गठित करता है, जिससे हंगेरियन एल्गोरिदम के माध्यम से यह गणनात्मक रूप से सुलभ हो जाता है।
टाइट रिग्रेट बाउंड्स (Tight Regret Bounds): लेखक LinMatch के लिए कठोर सैद्धांतिक गारंटी प्रदान करते हैं।
- अपर बाउंड (Upper Bound): वे LinMatch के संचयी रिग्रेट (cumulative regret) के लिए एक इंस्टेंस-स्वतंत्र अपर बाउंड $\tilde{O}(d\sqrt{MKT})$ स्थापित करते हैं, जहाँ $d$ फीचर डायमेंशन है, $M$ मनुष्यों की संख्या है, $K$ रोबोटों की संख्या है, और $T$ टाइम होराइजन है।
- लोअर बाउंड (Lower Bound): वे इस सेटिंग में किसी भी मैचिंग पॉलिसी के लिए $\Omega(d\sqrt{MKT})$ का मिनिमैक्स लोअर बाउंड सिद्ध करते हैं।
- इष्टतमता (Optimality): अपर और लोअर बाउंड का मिलान $\tilde{\Theta}(d\sqrt{MKT})$ की एक टाइट इष्टतम रिग्रेट दर स्थापित करता है। यह दर्शाता है कि LinMatch सभी समस्या मापदंडों ( $T, d, M, K$ ) के संबंध में सख्ती से इष्टतम प्राप्त करने योग्य रिग्रेट दर प्राप्त करता है।

प्रायोगिक परिणाम (Experimental Results)
लेखक $K=20$ रोबोट और $M=10$ मनुष्यों के साथ संख्यात्मक सिमुलेशन के माध्यम से LinMatch को मान्य करते हैं।

ETC के साथ तुलना: LinMatch की तुलना 'एक्सप्लोर-देन-कमिट' (ETC) एल्गोरिदम से की गई है। जबकि ETC एक इष्टतम अन्वेषण चरण की लंबाई के साथ सबलीनियर रिग्रेट प्राप्त कर सकता है, यदि अन्वेषण अपर्याप्त है तो यह लीनियर रिग्रेट से ग्रस्त होता है। LinMatch, ETC की तुलना में संकीर्ण कॉन्फिडेंस इंटरवल के साथ अधिक सुसंगत प्रदर्शन प्रदर्शित करता है।
रेगुलराइजेशन संवेदनशीलता (Regularization Sensitivity): रेगुलराइजेशन पैरामीटर $\lambda$ को बदलते हुए प्रयोग दिखाते हैं कि हालांकि सैद्धांतिक अपर बाउंड के लिए $\lambda \ge L^2$ की आवश्यकता है, व्यवहार में, छोटे मान (जैसे $\lambda=1$ ) अक्सर कम रिग्रेट देते हैं, जो यह सुझाव देता है कि सैद्धांतिक स्थिति रूढ़िवादी (conservative) है।

महत्व और दायरा (Significance and Scope)
यह शोध पत्र दावा करता है कि LinMatch पहला कार्य है जो यह दिखाता है कि लीनियर बैंडिट संरचना वाली मैचिंग समस्याओं के लिए इंस्टेंस-स्वतंत्र इष्टतम प्राप्त करने योग्य रिग्रेट दर सटीक रूप से $\tilde{\Theta}(d\sqrt{MKT})$ है। प्रस्तावित दृष्टिकोण को मानव-रोबोट टीमिंग से परे किसी भी केंद्रीकृत मिलान समस्या के लिए लागू करने के लिए डिज़ाइन किया गया है, जैसे आवास आवंटन (housing allocation) और अनुशंसा प्रणाली (recommendation systems)। यह कार्य रेखांकित करता है कि लीनियर स्ट्रक्चर और कुशल कॉम्बिनेटोरियल ऑप्टिमाइजेशन का लाभ उठाकर, ऑनलाइन लर्निंग सेटिंग्स में आमतौर पर जुड़ी मल्टी-एजेंट मैचिंग की घातीय जटिलता को दूर किया जा सकता है।

मुख्य चित्र: रोबोट और इंसानों के लिए "ब्लाइंड डेट"

समस्या: बहुत सारे विकल्प, बहुत कम समय

समाधान: "LinMatch" (एक आशावादी मैचमेकर)

यह पेपर एक बड़ी बात क्यों है

सारांश

इसी तरह के और पेपर