📊 statistics

Fundamental Limitations of Fixed-Budget Best-Arm Identification

यह शोध पत्र सिद्ध करता है कि तीन या अधिक भुजाओं (arms) वाले किसी भी निश्चित-बजट सर्वश्रेष्ठ-भुजा पहचान (best-arm identification) एल्गोरिदम के लिए, कम से कम एक ऐसा समस्या उदाहरण मौजूद है जहाँ त्रुटि क्षय दर (error decay rate) इष्टतम स्थिर ओरेकल (optimal static oracle) की तुलना में स्पष्ट रूप से बदतर है, जिससे यह प्रदर्शित होता है कि कोई भी एकल एल्गोरिदम सभी उदाहरणों में समान अनुकूलता प्राप्त नहीं कर सकता है।

मूल लेखक: Motti Goldberger

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

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

CC BY 4.0

मूल लेखक: Motti Goldberger

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

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

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

बड़ा सवाल यह था: क्या एक वास्तविक जासूस, जो स्कोर नहीं जानता और जैसे-जैसे समय बीतता है वैसे ही सीखता है, अंततः इस जादुई नुस्खे का इतनी पूर्णता से पालन करना सीख सकता है कि वह उतनी ही कम गलतियाँ करे जितनी कि वह सर्वज्ञ मार्गदर्शक करता है?

इस शोध पत्र के अनुसार, इसका उत्तर एक दृढ़ "नहीं" है—लेकिन केवल तभी जब संदिग्धों की संख्या 3 या अधिक हो ( $K \ge 3$ )।

वह "जादुई नुस्खा" जो अस्तित्व में नहीं है

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

विशेष रूप से, पेपर दिखाता है कि आपकी कितनी भी चतुर अनुकूल (adaptive) रणनीति क्यों न हो, हमेशा एक ऐसी पेचीदा स्थिति होगी जहाँ आपकी त्रुटि घटने की दर मार्गदर्शक की त्रुटि घटने की दर के अधिकतम:
$\left(1 + \frac{\log(K)}{8}\right)^{-1}$
गुना होगी।

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

हम बराबरी क्यों नहीं कर सकते?

यह पेपर इस विचार को खारिज करता है कि हम केवल "सीखकर" पूर्णता तक पहुँच सकते हैं। यह तर्क देता है कि एक निश्चित-बजट सेटिंग में सबसे अच्छे हाथ (या संदिग्ध) को खोजने की समस्या में कॉम्प्लेक्सिटी (complexity) नहीं होती।

साधारण शब्दों में, इसका अर्थ यह है कि कोई एक एकल, सार्वभौमिक कठिनाई स्कोर नहीं है जिसे एक स्मार्ट एल्गोरिदम हमेशा मात दे सके। कठिनाई संदिग्धों के विशिष्ट लाइनअप के आधार पर बदलती रहती है, जिसे कोई भी एकल रणनीति पूरी तरह से संभाल नहीं सकती।

लेखकों ने इस बात को सिद्ध करने के लिए एक विशिष्ट "ट्रैप" (जाल) परिदृश्य बनाया। उन्होंने एक ऐसा लाइनअप बनाया जहाँ:

दो संदिग्ध कौशल में बहुत करीब हैं, जिससे उन्हें अलग पहचानना कठिन है।
अन्य संदिग्ध दूर हैं, लेकिन उनमें से एक अचानक सबसे अच्छा बन सकता है।

इसे हल करने के लिए, एक जासूस को पहले दो संदिग्धों पर बहुत अधिक समय खर्च करना होगा और अन्य लोगों पर भी बहुत अधिक समय खर्च करना होगा। लेकिन आप एक साथ दोनों संभावनाओं के लिए समय को पूरी तरह से विभाजित नहीं कर सकते। यदि आप पहले दो पर ध्यान केंद्रित करते हैं, तो आप तीसरे के अचानक उभार को मिस कर सकते हैं। यदि आप तीसरे पर ध्यान केंद्रित करते हैं, तो आप पहले दो के बीच के सूक्ष्म अंतर को मिस कर सकते हैं। पेपर सिद्ध करता है कि यह ट्रेड-ऑफ अपरिहार्य है।

हम कितने आश्वस्त हैं?

यह केवल एक अनुमान या सिमुलेशन नहीं है। लेखकों ने इस परिणाम को गणितीय रूप से सिद्ध किया है। उन्होंने केवल कंप्यूटर टेस्ट नहीं चलाए; उन्होंने कठोर तर्क का उपयोग करके यह दिखाया कि किसी भी एल्गोरिदम के लिए, एक ऐसा गणितीय उदाहरण मौजूद है जहाँ वह स्टैटिक ओरकल से मेल करने में विफल रहता है।

वे यह भी स्पष्ट करते हैं कि यह "नो-गो" (no-go) नियम तब लागू होता है जब पुरस्कार (स्कोर) वन-पैरामीटर नेचुरल एक्सपोनेंशियल फैमिलीज़ (जिसमें सामान्य/गाऊसी और बरनौली वितरण शामिल हैं) नामक वितरणों के एक विशिष्ट परिवार से आते हैं।

निष्कर्ष

यदि आपके पास केवल 2 संदिग्ध हैं, तो एक पूर्ण रणनीति मौजूद है (जैसा कि पिछले कार्यों में दिखाया गया है)। लेकिन जैसे ही आप तीसरा संदिग्ध जोड़ते हैं, हर स्थिति के लिए काम करने वाले एक एकल, पूर्ण एल्गोरिदम का सपना गायब हो जाता है। "स्टैटिक ओरकल" एक उपयोगी बेंचमार्क बना रहता है, लेकिन यह एक ऐसी सीमा है जिसे कोई भी अनुकूल जासूस सभी संभावित मामलों में समान रूप से प्राप्त नहीं कर सकता। यह समस्याओं का ब्रह्मांड इतना पेचीदा है कि एक ही आकार सभी के लिए फिट नहीं बैठता।

तकनीकी सारांश: फिक्स्ड-बजट बेस्ट-आर्म आइडेंटिफिकेशन की मौलिक सीमाएँ

समस्या का निरूपण
यह शोध पत्र फिक्स्ड-बजट बेस्ट-आर्म आइडेंटिफिकेशन (BAI), जिसे रैंकिंग एंड सिलेक्शन भी कहा जाता है, की समस्या को संबोधित करता है। इस सेटिंग में, एक निर्णय लेने वाला $K$ भुजाओं (arms) से क्रमिक रूप से नमूने (samples) लेता है, जिनमें से प्रत्येक एक अज्ञात माध्य $\mu_k$ वाले वितरण से स्वतंत्र पुरस्कार (rewards) उत्पन्न करता है। लक्ष्य सबसे बड़े माध्य $\mu_k$ वाली भुजा $i^*(\mu)$ की पहचान करना है, जिसके लिए कुल नमूना बजट $T$ निश्चित है। प्रदर्शन मीट्रिक गलत पहचान की संभावना $p_{\mu, T}$ है, विशेष रूप से $T \to \infty$ होने पर इसका घातांकीय क्षय दर (exponential decay rate):
$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$

केंद्रीय सैद्धांतिक प्रश्न यह है कि क्या इस समस्या के लिए कोई "जटिलता" (complexity) मौजूद है। एक जटिलता को एक ऐसे फलन $\Gamma^*(\mu)$ के रूप में परिभाषित किया गया है जो दो शर्तों को पूरा करता है:

सार्वभौमिक ऊपरी सीमा (Universal Upper Bound): प्रत्येक एल्गोरिदम और प्रत्येक इंस्टेंस $\mu$ के लिए, त्रुटि क्षय दर $\Gamma^*(\mu)$ द्वारा ऊपरी रूप से सीमित है।
समान रूप से प्राप्त करने की क्षमता (Uniform Achievability): एक एकल एल्गोरिदम मौजूद है जो सभी समस्या इंस्टेंस $\mu$ में समान रूप से इस क्षय दर $\Gamma^*(\mu)$ को प्राप्त करता है।

शोध पत्र इस बात की जांच करता है कि क्या स्टैटिक ओरकल (static oracle) दर, $\Gamma^*_{so}(\mu)$ , इस जटिलता के रूप में कार्य करती है। स्टैटिक ओरकल एक गैर-अनुकूली (non-adaptive) रणनीति का प्रतिनिधित्व करता है जो वास्तविक माध्य $\mu$ को अग्रिम रूप से जानता है और क्षय दर को अधिकतम करने के लिए निश्चित अनुपातों में नमूनों का आवंटन करता है। हालांकि अनुकूल (adaptive) एल्गोरिदम को ऐसे डिज़ाइन किया गया है कि उनके नमूनाकरण अनुपात इन इष्टतम स्टैटिक अनुपातों की ओर अभिसरित (converge) होते हैं, लेकिन यह एक खुला प्रश्न बना हुआ था कि क्या कोई भी अनुकूल एल्गोरिदम सभी इंस्टेंस के लिए समान रूप से स्टैटिक ओरकल की त्रुटि क्षय दर से मेल खा सकता है।

कार्यप्रणाली
लेखक यह प्रदर्शित करने के लिए विरोधाभास द्वारा प्रमाण (proof by contradiction) का उपयोग करते हैं कि जब $K \geq 3$ हो, तो कोई भी एकल एल्गोरिदम सभी इंस्टेंस के लिए स्टैटिक ओरकल दर को समान रूप से प्राप्त नहीं कर सकता है। कार्यप्रणाली निम्नलिखित घटकों पर निर्भर करती है:

कठिनाई अनुपात (Difficulty Ratios): डेगेने (2023) का अनुसरण करते हुए, शोध पत्र कठिनाई अनुपात $R_{H, \infty}(A, \mu)$ का उपयोग करता है, जो एक बेंचमार्क कठिनाई फलन $H(\mu)$ के सापेक्ष किसी एल्गोरिदम $A$ के प्रदर्शन को मापता है। यदि कोई जटिलता मौजूद है, तो एक ऐसा एल्गोरिदम होना चाहिए जहाँ इस अनुपात का सुप्रीमकम (supremum) सभी इंस्टेंस पर $\leq 1$ हो।
थ्योरम 1 (डेगेने 2023): प्रमाण एक प्रमुख असमानता का लाभ उठाता जो किसी भी सुसंगत (consistent) अनुकूल एल्गोरिदम परिवार को सीमित करती है। किसी भी बेंचमार्क $H$ और वैकल्पिक इंस्टेंस के सेट $D(\mu)$ के लिए, सबसे खराब स्थिति वाले कठिनाई अनुपात का व्युत्क्रम एक स्टैटिक ऑप्टिमाइज़ेशन समस्या द्वारा सीमित होता है:
$\left( \sup_{\lambda \in D(\mu)} R_{H, \infty}(A, \lambda) \right)^{-1} \leq \sup_{\omega \in \Delta_K} \inf_{\lambda \in D(\mu)} \left( H(\lambda) \sum_{k=1}^K \omega_k \text{KL}(\mu_k, \lambda_k) \right)$
इंस्टेंस निर्माण (Instance Construction): जटिलता के अस्तित्व को नकारने के लिए, लेखक एक विशिष्ट "बेसलाइन" इंस्टेंस $x$ $x$ और वैकल्पिक इंस्टेंस का एक परिवार $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$ $D (x) = {λ_{A}, λ_{B, 3}, \dots, λ_{B, K}}$ निर्मित करते हैं।
- $\lambda_A$ : यह केवल भुजा 1 और 2 में $x$ से भिन्न है। $x$ को $\lambda_A$ से अलग करने के लिए भुजा 1 और 2 के महत्वपूर्ण नमूनाकरण की आवश्यकता है।
- $\lambda_{B,j}$ (जहाँ $j \in \{3, \dots, K\}$ ): यह केवल भुजा $j$ में $x$ से भिन्न है, जिससे भुजा $j$ नई सर्वश्रेष्ठ भुजा बन जाती है। $x$ को $\lambda_{B,j}$ से अलग करने के लिए भुजा $j$ के महत्वपूर्ण नमूनाकरण की आवश्यकता है।
- निर्माण यह सुनिश्चित करता है कि परिवार में अलग-अलग करने के लिए "सबसे कठिन" भुजाएं भिन्न होती हैं। एक एकल नमूना आवंटन $\omega$ एक साथ $D(x)$ के सभी सदस्यों से $x$ को अलग करने के लिए इष्टतम नहीं हो सकता है, क्योंकि आवश्यक सूचना विसंयुक्त (disjoint) भुजाओं के सेटों पर केंद्रित है।

मुख्य परिणाम
शोध पत्र फिक्स्ड-बजट BAI के लिए एक मौलिक नकारात्मक परिणाम स्थापित करता है:

गौसियन पुरस्कार (Gaussian Rewards): $K \geq 3$ भुजाओं (वेरिएंस 1 के साथ गौसियन पुरस्कारों) के लिए, लेखक सिद्ध करते हैं कि किसी भी सुसंगत एल्गोरिदम परिवार $A$ के लिए, एक इंस्टेंस $\mu$ मौजूद है जिसके लिए स्टैटिक ओरकल के सापेक्ष कठिनाई अनुपात 1 से अधिक है। विशेष रूप से:
$\inf_{A \in \mathcal{C}_{cons}} \sup_{\mu} R_{H_{so}, \infty}(A, \mu) \geq 1 + \sum_{j=3}^K \frac{1}{(1 + \sqrt{j-1})^2} > 1 + \frac{1}{8} \log(K)$
यह निचला स्तर (lower bound) सभी $K \geq 3$ के लिए 1 से स्पष्ट रूप से अधिक है, जो यह सिद्ध करता है कि कोई भी एल्गोरिदम समान रूप से स्टैटिक ओरकल से मेल नहीं खा सकता।
नेचुरल एक्सपोनेंशियल फैमिली (NEF) में सामान्यीकरण: यह परिणाम किसी भी एक-पैरामीटर नेचुरल एक्सपोनेंशियल फैमिली (NEF) के लिए विस्तारित किया गया है। KL डाइवर्जेंस के स्थानीय द्विघात सन्निकटन (local quadratic approximation) का उपयोग करके, लेखक दिखाते हैं कि गौसियन परिणाम सभी नियमित एक-पैरामीटर NEF के लिए समान सीमा लागू करता है।
खुले प्रश्न का उत्तर: यह कार्य किन (2022) द्वारा उठाए गए और डेगेने (2023) द्वारा औपचारिक रूप दिए गए खुले प्रश्न का निर्णायक उत्तर देता है: फिक्स्ड-बजट BAI के लिए $K \geq 3$ के मामले में जटिलता मौजूद नहीं है। जबकि स्टैटिक ओरकल त्रुटि क्षय दर के लिए एक निचली सीमा प्रदान करता है, कोई भी एकल अनुकूल एल्गोरिदम सभी समस्या इंस्टेंस के लिए इस दर को समान रूप से प्राप्त नहीं कर सकता है।

महत्व और दावे
शोध पत्र दावा करता है कि यह फिक्स्ड-बजट BAI की समझ में एक मौलिक सैद्धांतिक अंतर को हल करता है।

अनुकूलता की सीमा (Limitation of Adaptivity): यह दर्शाता है कि नमूनाकरण अनुपातों का स्टैटिक ओरकल की ओर अभिसरण (जो अनुकूल एल्गोरिदम का एक सामान्य डिज़ाइन लक्ष्य है) स्टैटिक ओरकल की त्रुटि क्षय दर से मेल खाने की गारंटी नहीं देता है। फिक्स्ड-बजट सेटिंग में "अनुकूलता की कीमत" (price of adaptivity) यह है कि एक एल्गोरिदम सभी इंस्टेंस के लिए एक साथ इष्टतम नहीं हो सकता है।
क्षेत्र (Scope): यह कार्य गौसियन पुरस्कारों के लिए $3 \leq K < e^{80/3}$ के बीच के साहित्य के अंतराल को भरता है और जटिलता के गैर-अस्तित्व को सभी एक-पैरामीटर NEF तक विस्तारित करता है।
सैद्धांतिक सीमा: यह कार्य स्थापित करता है कि स्टैटिक ओरकल दर $K \geq 3$ के लिए फिक्स्ड-बजट BAI के लिए एक सार्वभौमिक जटिलता नहीं है। लेखक सुझाव देते हैं कि यह वैकल्पिक सैद्धांतिक लक्ष्यों या बेंचमार्क की आवश्यकता की ओर संकेत करता है, क्योंकि स्टैटिक ओरकल को समान रूप से प्राप्त नहीं किया जा सकता है।

यह शोध पत्र इस सीमा को दूर करने के लिए नए एल्गोरिदम प्रस्तावित नहीं करता है, न ही रैंकिंग-एंड-सिलेक्शन और मल्टी-आर्म्ड बैंडिट्स के अलावा विशिष्ट अनुप्रयोगों का सुझाव देता है। इसका योगदान पूरी तरह से एक नकारात्मक परिणाम है जो इस सेटिंग में जो कुछ भी प्राप्त किया जा सकता है, उसकी मौलिक सीमाओं को परिभाषित करता है।

वह "जादुई नुस्खा" जो अस्तित्व में नहीं है

हम बराबरी क्यों नहीं कर सकते?

हम कितने आश्वस्त हैं?

निष्कर्ष

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