🤖 machine learning

Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction

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

मूल लेखक: Zain Ulabedeen Farhat, Debamita Ghosh, George K. Atia, Yue Wang

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

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

CC BY 4.0

मूल लेखक: Zain Ulabedeen Farhat, Debamita Ghosh, George K. Atia, Yue Wang

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

यहाँ "Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction" नामक शोध पत्र का सरल भाषा और रचनात्मक उपमाओं (analogies) का उपयोग करते हुए विवरण दिया गया है।

बड़ी तस्वीर: "Sim-to-Real" की आपदा

कल्पना कीजिए कि आप एक वीडियो गेम में रेस करने के लिए सेल्फ-ड्राइविंग कारों की एक टीम को प्रशिक्षित कर रहे हैं। गेम (सिम्युलेटर) में, सड़कें एकदम सही हैं, मौसम सुहावना है, और अन्य कारें हमेशा नियमों का पालन करती हैं। आपका AI एक चैंपियन बनना सीख जाता है।

लेकिन फिर, आप असली कारों को वास्तविक दुनिया में भेजते हैं। अचानक, बारिश होने लगती है, एक सेंसर खराब हो जाता है, और एक मानव चालक आपकी कार के सामने आ जाता है। क्योंकि AI को "परफेक्ट" डेटा पर प्रशिक्षित किया गया था, वह घबरा जाता है और दुर्घटनाग्रस्त हो जाता है। यह "Sim-to-Real" गैप है।

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

समाधान: "पैरानॉयड" (शंकालु) योजना

लेखक इन टीमों को प्रशिक्षित करने का एक नया तरीका प्रस्तावित करते हैं जिसे Distributionally Robust Markov Games (DRMGs) कहा जाता है।

इसे अपने एजेंटों को "पैरानॉयड आशावादी" (Paranoid Optimists) बनाने के रूप में सोचें।

स्टैंडर्ड AI: "मैं मानूँगा कि दुनिया बिल्कुल वैसी ही है जैसी अभी मुझे दिख रही है।"
रोबस्ट (Robust) AI: "मैं मानूँगा कि दुनिया थोड़ी खराब, शोर-शराबे वाली या यहाँ तक कि शत्रुतापूर्ण भी हो सकती है। मैं उस सबसे खराब स्थिति (worst-case scenario) के लिए योजना बनाऊँगा जो संभव है।"

केवल जीत के एक रास्ते को सीखने के बजाय, AI एक ऐसी रणनीति सीखता है जो तब भी काम करे जब वातावरण उसे बाधित करने की कोशिश करे (एक सीमा के भीतर)।

समस्या: "ब्लैक बॉक्स" की दुविधा

यहाँ एक पेंच है: AI को 'पैरानॉयड' बनने के लिए सिखाने के लिए, आपको आमतौर पर दो चीजों की आवश्यकता होती है जो वास्तविक दुनिया में प्राप्त करना अक्सर असंभव होता है:

एक परफेक्ट सिम्युलेटर: एक अत्यंत सटीक वीडियो गेम जो वास्तविकता की हूबहू नकल करता हो। (जटिल वास्तविक कार्यों जैसे स्वास्थ्य सेवा या आपदा राहत के लिए ऐसा सिम्युलेटर मौजूद नहीं है)।
एक विशाल ऑफलाइन डेटासेट: शुरू करने से पहले अध्ययन करने के लिए लाखों पिछले परिदृश्यों (scenarios) का एक पुस्तकालय। (आप शुरू करने से पहले हर संभावित आपदा के लिए डेटा एकत्र नहीं कर सकते)।

मौजूदा अधिकांश विधियाँ कहती हैं: "यदि आपके पास सिम्युलेटर या विशाल डेटासेट नहीं है, तो आप यह नहीं कर सकते।"

नवाचार: करके सीखना (Online Interaction)

यह शोध पत्र कहता है: "हाँ, आप कर सकते हैं।"

लेखकों ने MORNAVI (Multiplayer Optimistic Robust Nash Value Iteration) नामक एक नया एल्गोरिदम पेश किया है। यह एजेंटों को बिना किसी सिम्युलेटर या पूर्व-संग्रहित डेटासेट के, सीधे वास्तविक दुनिया से, चरण-दर-चरण सीखने की अनुमति देता है।

MORNAVI कैसे काम करता है (उपमा)

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

"आशावादी" हिस्सा (Exploration): खोजकर्ता जिज्ञासु हैं। वे सोचते हैं, "शायद यहाँ कोई गुप्त शॉर्टकट है जिसे हमने अभी तक नहीं देखा है!" वे नई जानकारी जुटाने के लिए जोखिम उठाने को तैयार हैं। यह Optimism (आशावाद) है।
"रोबस्ट" हिस्सा (Safety): लेकिन वे डरे हुए भी हैं। वे सोचते हैं, "क्या होगा अगर यह रास्ता किसी जाल की ओर ले जाए? क्या होगा अगर जमीन धंस जाए?" इसलिए, वे अपने द्वारा उठाए गए हर कदम के लिए सबसे खराब संभावित परिणाम की गणना करते हैं। यदि कोई रास्ता अच्छा दिखता है जब तक कि उस पर कोई पत्थर न गिर जाए, तो वे उससे बच सकते हैं। यह Robustness (मजबूती/सुरक्षा) है।
"बोनस" सिस्टम: एल्गोरिदम एक चतुर ट्रिक का उपयोग करता है। यह खोजकर्ताओं को एक "कॉन्फिडेंस बोनस" देता है। यदि उन्होंने काफी समय से भूलभुलैया के किसी हिस्से में कदम नहीं रखा है, तो एल्गोरिदम कहता है, "वहाँ जाओ! यह सुरक्षित हो सकता है, और हमें यह जानने की जरूरत है।" लेकिन यह सुनिश्चित करने के लिए कि यदि वे सुरक्षा के बारे में गलत भी हों, तो भी वे कुचले न जाएँ, यह उनकी गणनाओं में एक "सेफ्टी बफर" भी जोड़ देता है।

कड़वा सच: "कई एजेंटों का अभिशाप" (Curse of Many Agents)

यह शोध पत्र एक कठोर वास्तविकता भी प्रकट करता है। जब आपके पास कई एजेंट होते हैं (जैसे 10 रोबोट्स की एक टीम), तो कठिनाई केवल जुड़ती नहीं है; यह गुणा (multiply) हो जाती है।

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

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

यह शोध एक सफलता है क्योंकि यह सिद्धांत (theory) और वास्तविकता (reality) के बीच के अंतर को पाटता है।

पहले: हम केवल तभी रोबस्ट AI बना सकते थे जब हमारे पास परफेक्ट सिम्युलेटर (जैसे वीडियो गेम के लिए) या विशाल डेटासेट (जैसे स्टॉक ट्रेडिंग के लिए) हों।
अब: हमारे पास एक गणितीय गारंटी है कि एक एल्गोरिदम अराजक, अप्रत्याशित वास्तविक दुनिया के साथ बातचीत करते हुए भी रोबस्ट बनना सीख सकता है।

संक्षेप में

लेखकों ने एक नया प्रशिक्षण तरीका (MORNAVI) बनाया है जो AI एजेंटों की टीमों को बिना किसी परफेक्ट सिम्युलेटर के, एक अराजक और अनिश्चित दुनिया में जीवित रहना सिखाता है। उन्होंने एजेंटों को विपत्तियों में जीवित रहने के लिए पर्याप्त 'पैरानॉयड' और सीखते रहने के लिए पर्याप्त 'आशावादी' बनाया है। हालांकि उन्होंने यह सिद्ध किया कि कई एजेंटों के साथ सीखना बेहद कठिन है, फिर भी उन्होंने दिखाया कि यह संभव है, जिससे वास्तविक दुनिया में सुरक्षित और अधिक विश्वसनीय स्वायत्त प्रणालियों (autonomous systems) का मार्ग प्रशस्त हुआ है।

यहाँ पेपर "Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction" (ICLR 2026) का विस्तृत तकनीकी सारांश दिया गया है।

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

यह पेपर ऑनलाइन (online) परिवेश में डिस्ट्रीब्यूशनली रोबस्ट मल्टी-एजेंट रिइन्फोर्समेंट लर्निंग (DR-MARL) की चुनौती को संबोधित करता है।

संदर्भ: मानक मल्टी-एजेंट रिइन्फोर्समेंट लर्निंग (MARL) अक्सर वास्तविक दुनिया के परिनियोजन (deployment) में विफल हो जाता है क्योंकि "सिम-टू-रियल" (Sim-to-Real) गैप के कारण, जहाँ मॉडल मिसमैच (शोर, प्रतिकूल हमले, अनमॉडल डायनेमिक्स) से प्रशिक्षित नीतियां विफल हो जाती हैं।
डिस्ट्रीब्यूशनली रोबस्ट मार्कोव गेम्स (DRMGs): लेखक एक मार्कोव गेम के रूप में वातावरण को मॉडल करते हैं जहाँ प्रत्येक एजेंट $i$ के पास एक नाममात्र कर्नेल (nominal kernel) $P^\star$ के आसपास संभावित ट्रांजिशन कर्नेल का एक अनिश्चितता सेट $\mathcal{P}_i$ होता है। लक्ष्य एक ऐसी नीति खोजना है जो इस अनिश्चितता सेट पर सबसे खराब स्थिति के अपेक्षित रिटर्न (worst-case expected return) को अधिकतम करे।
गैप: मौजूदा DRMG शोध जेनरेटिव मॉडल (परफेक्ट सिम्युलेटर) या ऑफलाइन डेटासेट (बड़े पूर्व-संग्रहित डेटा) पर निर्भर करते हैं। ये धारणाएं उच्च-जोखिम वाले अनुप्रयोगों (जैसे स्वायत्त ड्राइविंग, स्वास्थ्य सेवा) के लिए अवास्तविक हैं, जहाँ एजेंटों को बिना किसी पूर्व डेटा के, एक अज्ञात और शोर वाले वातावरण के साथ क्रमिक अंतःक्रिया (sequential interaction) से सीधे सीखना होता है।
उद्देश्य: DRMGs के लिए एक ऑनलाइन लर्निंग एल्गोरिदम डिजाइन करना जो सीधे अंतःक्रिया से सीखता है, सैद्धांतिक रिग्रेट गारंटी प्रदान करता है, और टोटल वेरिएशन (TV) तथा कुलबैक-लीब्लर (KL) डाइवर्जेंस अनिश्चितता सेट्स के साथ जनरल-सम गेम्स को संभालता है।

2. कार्यप्रणाली: f-MORNAVI

लेखक मल्टीप्लेयर ऑप्टिमिस्टिक रोबस्ट नैश वैल्यू इटरेशन (f-MORNAVI) का प्रस्ताव करते हैं, जो एपिसोडिक, फाइनाइट-होरिज़न DRMGs के लिए डिज़ाइन किया गया एक मॉडल-आधारित मेटा-एल्गोरिदम है।

मुख्य घटक:

मॉडल-आधारित अनुमान (Model-Based Estimation):
- एजेंट ऐतिहासिक अंतःक्रिया डेटा $D$ के आधार पर नाममात्र ट्रांजिशन कर्नेल $\hat{P}^k$ का एक अनुभवजन्य अनुमान बनाए रखते हैं।
- एल्गोरिदम एक मॉडल-आधारित दृष्टिकोण का उपयोग करता है क्योंकि DRMGs के लिए मॉडल-फ्री एस्टिमेटर, 'वर्स्ट-केस एक्सपेक्टेशन ऑपरेटर' की नॉन-लीनियरिटी के कारण पक्षपाती या सैंपल-अक्षम (sample-inefficient) होते हैं।
ऑप्टिमिस्टिक रोबस्ट प्लानिंग (UCB सिद्धांत):
- एल्गोरिदम अन्वेषण (exploration) को प्रोत्साहित करने के लिए रोबस्ट वैल्यू फंक्शन पर एक अपर कॉन्फिडेंस बाउंड (UCB) बनाता है।
- यह रोबस्ट Q-फंक्शन के लिए दो अनुमान बनाए रखता है:
  - ऑप्टिमिस्टिक एस्टीमेट ( $\bar{Q}$ ): $r + \sigma_{\hat{\mathcal{P}}}[\bar{V}] + \beta$
  - पेसिमिस्टिक एस्टीमेट ( $\underline{Q}$ ): $r + \sigma_{\hat{\mathcal{P}}}[\underline{V}] - \beta$
- यहाँ, $\sigma_{\mathcal{P}}[V] = \inf_{P \in \mathcal{P}} \mathbb{E}_P[V]$ एक सपोर्ट फंक्शन है जो वर्स्ट-केस एक्सपेक्टेशन को दर्शाता है।
- बोनस टर्म ( $\beta$ ): यह सुनिश्चित करने के लिए कि ऑप्टिमिस्टिक एस्टीमेट उच्च संभावना के साथ वास्तविक रोबस्ट वैल्यू का ऊपरी स्तर (upper bound) हो, एक डेटा-संचालित बोनस टर्म जोड़ा जाता है। $\beta$ का निर्माण अनिश्चितता सेट की ज्यामिति (TV या KL) के अनुरूप तैयार किया गया है।
इक्विलिब्रियम कंप्यूटेशन (Equilibrium Computation):
- प्रत्येक चरण में, एल्गोरिदम अनुमानित ऑप्टिमिस्टिक Q-वैल्यूज़ का उपयोग करके एक मैट्रिक्स गेम को हल करता है ताकि एक इक्विलिब्रियम पॉलिसी ( $\pi^k$ ) प्राप्त की जा सके।
- यह ढांचा नैश इक्विलिब्रियम (NE), कोर्स कोरिलेटेड इक्विलिब्रियम (CCE), और कोरिलेटेड इक्विलिब्रियम (CE) का समर्थन करता है।
- नोट: जबकि NE खोजना PPAD-हार्ड है, यह पेपर सैंपल कॉम्प्लेक्सिटी पर ध्यान केंद्रित करता है और मानता है कि इक्विलिब्रियम सबरूटीन निष्पादन योग्य है, जैसा कि मानक MG साहित्य में होता है।
अनिश्चितता सेट्स को संभालना:
- TV-डाइवर्जेंस: सपोर्ट शिफ्टिंग (जहाँ वर्स्ट-केस कर्नेल का सपोर्ट नाममात्र कर्नेल के बाहर होता है) को संभालने के लिए एक "फेलियर स्टेट" धारणा (Assumption 3) की आवश्यकता होती है।
- KL-डाइवर्जेंस: स्वाभाविक रूप से सपोर्ट शिफ्टिंग समस्याओं से बचता है क्योंकि KL-बॉल नाममात्र सपोर्ट के भीतर ही होती है।

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

A. ऑनलाइन DRMGs का हार्डनेस विश्लेषण

यह पेपर यह सिद्ध करने के लिए मौलिक लोअर बाउंड्स स्थापित करता है कि ऑनलाइन DRMGs, ऑफलाइन या जेनरेटिव सेटिंग्स की तुलना में स्वाभाविक रूप से कठिन क्यों हैं:

सपोर्ट शिफ्टिंग (TV): यदि अनिश्चितता सेट सपोर्ट शिफ्टिंग की अनुमति देता है (जैसे TV दूरी), तो कोई भी ऑनलाइन एल्गोरिदम लीनियर रिग्रेट $\Omega(K \cdot \min\{H, \prod A_i\})$ से ग्रस्त होगा क्योंकि एजेंट उन अवस्थाओं (states) के लिए वर्स्ट-केस ट्रांजिशन नहीं सीख सकता जो नाममात्र मॉडल में कभी विज़िट नहीं की गईं।
मल्टी-एजेंसी का अभिशाप (No Support Shift): बिना सपोर्ट शिफ्ट के भी (जैसे KL डाइवर्जेंस), पेपर एक मिनिमैक्स लोअर बाउंड $\Omega(\sqrt{K \prod A_i})$ सिद्ध करता है। यह दर्शाता है कि ऑनलाइन DRMGs "कर्स ऑफ मल्टी-एजेंसी" से ग्रस्त हैं, जहाँ सैंपल कॉम्प्लेक्सिटी जॉइंट एक्शन स्पेस ( $\prod A_i$ ) के आकार पर निर्भर करती है, जबकि नॉन-रोबस्ट MGs में एजेंट कभी-कभी इस अभिशाप से बच सकते हैं।

B. सैद्धांतिक गारंटी (Regret Bounds)

लेखक ऑनलाइन DRMGs के लिए पहले प्रमाण योग्य रिग्रेट बाउंड्स प्रदान करते हैं:

TV-डाइवर्जेंस: फेलियर स्टेट धारणा के तहत, रिग्रेट इस प्रकार सीमित है:
$\tilde{O}\left( \sqrt{\min\{\rho_{\min}^{-1}, H\} \cdot H^2 S K \prod_{i} A_i} \right)$
KL-डाइवर्जेंस: बिना किसी अतिरिक्त धारणा के, रिग्रेट इस प्रकार सीमित है:
$\tilde{O}\left( \sqrt{H^4 \exp(2H^2) K S \prod_{i} A_i \cdot (\rho_{\min}^2 P^\star_{\min})^{-1}} \right)$
(नोट: $\exp(H)$ टर्म KL-आधारित रोबस्ट ऑप्टिमाइजेशन ड्यूअलिटी के लिए अंतर्निहित है।)

C. सैंपल कॉम्प्लेक्सिटी

एक ऑनलाइन-टू-बैच कन्वर्जन का उपयोग करते हुए, पेपर एक $\epsilon$ -अनुमानित इक्विलिब्रियम खोजने के लिए सैंपल कॉम्प्लेक्सिटी निकालता है:

TV: $\tilde{O}(\epsilon^{-2} \min\{\rho_{\min}^{-1}, H\} H^3 S \prod A_i)$
KL: $\tilde{O}(\epsilon^{-2} H^5 \exp(2H^2) S \prod A_i (\rho_{\min}^2 P^\star_{\min})^{-1})$

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

4. परिणाम और प्रयोग

संख्यात्मक सत्यापन: लेखकों ने छोटे पैमाने के पूर्णतः सहकारी (fully cooperative) और जनरल-सम DRMGs पर प्रयोग किए।
- अभिसरण (Convergence): f-MORNAVI एल्गोरिदम सफलतापूर्वक रोबस्ट इक्विलिब्रिया तक पहुँच गया।
- मजबूती (Robustness): जब मॉडल अनिश्चितता के विभिन्न स्तरों (सिम-टू-रियल गैप का अनुकरण करते हुए) के तहत परीक्षण किया गया, तो f-MORNAVI द्वारा सीखी गई रोबस्ट नीतियां स्थिर प्रदर्शन बनाए रखने में सफल रहीं, जबकि नॉन-रोबस्ट बेसलाइन्स (मानक नैश वैल्यू इटरेशन) अनिश्चितता बढ़ने पर महत्वपूर्ण प्रदर्शन गिरावट का शिकार हुए।
तुलना: सैद्धांतिक परिणामों की तुलना पूर्ववर्ती कार्यों से की गई (पेपर में तालिका 1)। प्रस्तावित एल्गोरिदम ऑनलाइन अन्वेषण की अतिरिक्त कठिनाई के बावजूद, सर्वोत्तम जेनरेटिव और ऑफलाइन तरीकों के समान जटिलता प्राप्त करता है।

5. महत्व और प्रभाव

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

संक्षेप में, यह पेपर सीधे पर्यावरणीय अंतःक्रियाओं से सीखने के लिए रोबस्ट मल्टी-एजेंट नीतियों के सैद्धांतिक और एल्गोरिदम आधार की नींव रखता है, यह सिद्ध करते हुए कि हालांकि यह समस्या स्वाभाविक रूप से कठिन है, फिर भी कुशल सैंपल-कॉम्प्लेक्सिटी गारंटी प्राप्त की जा सकती है।