📊 statistics

Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors

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

मूल लेखक: Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun

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

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

CC BY 4.0

मूल लेखक: Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun

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

कल्पना कीजिए कि आप एक खाद्य समीक्षक (food critic) हैं जो 100 अलग-अलग पिज़्ज़ेरिया वाले शहर में सबसे बेहतरीन पिज़्ज़ा खोजने की कोशिश कर रहे हैं। आपके पास इस मिशन के लिए दो अलग-अलग तरीके हैं, और यह शोध पत्र उन्हीं दो रणनीतियों की तुलना करने के बारे में है।

दो रणनीतियाँ

रणनीति 1: "कॉन्फिडेंस" दृष्टिकोण (Fixed-Confidence या FC)
आप पिज़्ज़ेरिया मालिकों से कहते हैं: "मैं तब तक पिज़्ज़ा के स्लाइस खाता रहूँगा जब तक कि मैं 99% सुनिश्चित न हो जाऊँ कि मुझे सबसे अच्छा पिज़्ज़ा मिल गया है। फिर, मैं रुक जाऊँगा।"

लक्ष्य: उच्च निश्चितता के साथ सही होना।
लागत: आप नहीं जानते कि आप कितने स्लाइस खाएंगे। इसमें 10 स्लाइस लग सकते हैं, या 1,000 भी। लेकिन आप ठीक तभी रुकते हैं जब आप आश्वस्त महसूस करते हैं।

रणनीति 2: "बजट" दृष्टिकोण (Fixed-Budget या FB)
आप खुद से कहते हैं: "मेरे पास पिज़्ज़ा के लिए ठीक $50 हैं। मैं इसे पूरा खर्च कर दूँगा, और फिर मैं अनुमान लगाऊँगा कि कौन सा पिज़्ज़ेरिया सबसे अच्छा था।"

लक्ष्य: जितना संभव हो सके उतना अच्छा अनुमान लगाना, एक सख्त सीमा के भीतर।
लागत: आप यह नहीं कह सकते कि "मैं 99% सुनिश्चित हूँ।" आपको बस उम्मीद करनी होगी कि अपना पैसा खर्च करने के बाद आपका अनुमान सही निकले।

बड़ा सवाल

लंबे समय तक, मशीन लर्निंग के शोधकर्ताओं (वह क्षेत्र जहाँ कंप्यूटर डेटा से सीखते हैं, जैसे कि हमारा पिज़्ज़ा समीक्षक) के मन में यह सवाल था: कौन सी रणनीति अधिक कठिन है?

क्या एक सख्त बजट (FB) के साथ सबसे अच्छा पिज़्ज़ा खोजना कठिन है, या उच्च आत्मविश्वास के साथ खुद को सही साबित करना (FC) कठिन है?

साधारण मामलों में (जैसे मानक पिज़्ज़ेरिया), गणित ने दिखाया कि वे लगभग समान रूप से कठिन थे, जिनमें केवल एक बहुत छोटा अंतर था। लेकिन अधिक जटिल स्थितियों में (जैसे ऐसे पिज़्ज़ेरिया जहाँ कुछ अधिक शोर वाले/अनिश्चित हैं, या जहाँ गुणवत्ता एक विशिष्ट पैटर्न का पालन करती है), यह स्पष्ट नहीं था। कुछ विशेषज्ञों का मानना था कि बजट दृष्टिकोण काफी कठिन हो सकता है क्योंकि आपको तब तक नहीं रुकने दिया जाता जब तक आप "निश्चित" न हो जाएँ—आपको बस तब रुकना होता है जब आप "कंगाल" हो जाते हैं।

शोध पत्र की खोज

यह शोध पत्र एक आश्चर्यजनक और सुंदर परिणाम सिद्ध करता है: बजट दृष्टिकोण, कॉन्फिडेंस दृष्टिकोण से अधिक कठिन नहीं है।

वास्तव में, वे कठिनाई के स्तर पर लगभग समान हैं। यदि आपके पास "कॉन्फिडेंस" दृष्टिकोण के लिए एक बेहतरीन रणनीति है, तो आप उसे आसानी से "बजट" दृष्टिकोण में बदल सकते हैं। एकमात्र दंड एक छोटा, लॉगरिदमिक कारक (logarithmic factor) है (इसे एक बहुत छोटे सर्विस शुल्क की तरह समझें)।

जादुई टूल: FC2FB

लेखकों ने एक "मेटा-एल्गोरिदम" (अन्य रेसिपी बनाने वाली रेसिपी) बनाया जिसे FC2FB (Fixed-Confidence to Fixed-Budget) कहा जाता है।

FC2FB को एक अनुवादक या कनवर्टर के रूप में सोचें।

इनपुट: आप इसे एक "कॉन्फिडेंस" रणनीति देते हैं (एक ऐसी रणनीति जो तब रुकती है जब वह सुनिश्चित हो जाती है)।
आउटपुट: यह आपको एक "बजट" रणनीति देता है (जो एक निश्चित राशि के भीतर काम करती है)।

यह कैसे काम करता है?
कल्पना कीजिए कि आपके पास $50 का सख्त बजट है। FC2FB अनुवादक पैसे को बेतरतीब ढंग से खर्च नहीं करता है। यह $50 को छोटे हिस्सों में तोड़ता है।

यह बहुत कम कॉन्फिडेंस आवश्यकता (जैसे, "मैं केवल 50% सुनिश्चित हूँ") के साथ "कॉन्फिडेंस" रणनीति को आजमाता है।
यदि रणनीति जल्दी समाप्त हो जाती है, तो बहुत अच्छा! यह आपको उत्तर दे देता है।
यदि यह समाप्त नहीं होती है, तो अनुवादक अगले पैसे के हिस्से पर जाता है और थोड़ी उच्च कॉन्फिडेंस आवश्यकता के साथ फिर से प्रयास करता है।
यह यह करता रहता है, अधिक से अधिक आश्वस्त होता जाता है, जब तक कि या तो इसे उत्तर नहीं मिल जाता या इसके पास पैसे खत्म नहीं हो जाते।

क्योंकि यह कम कॉन्फिडेंस से शुरू होता है और धीरे-धीरे बढ़ता है, यह बजट का कुशलतापूर्वक उपयोग करता है। यह सिद्ध करता है कि इसे काम करने के लिए आपको पिज़्ज़ेरिया के "गुप्त नंबरों" (जैसे कि वे कितने शोर वाले या कठिन हैं) को जानने की आवश्यकता नहीं है।

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

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

अब, FC2FB की बदौलत:

आप पुराने काम का पुन: उपयोग कर सकते हैं: यदि किसी ने पहले से ही एक जटिल समस्या के लिए एक महान "कॉन्फिडेंस" एल्गोरिदम बनाया है, तो आप बस उसे FC2FB में डालकर एक महान "बजट" एल्गोरिदम प्राप्त कर सकते हैं।
बेहतर परिणाम: कई जटिल परिदृश्यों में (जैसे कि जब "शोर" या अनिश्चितता विभिन्न विकल्पों के बीच भिन्न होती है, या जब विकल्पों में एक रैखिक संरचना होती है), FC2FB द्वारा बनाए गए नए बजट एल्गोरिदम वास्तव में मौजूदा सर्वश्रेष्ठ बजट एल्गोरिदम से बेहतर हैं। वे सही उत्तर पाने के लिए कम नमूनों (या कम पैसे) का उपयोग करते हैं।

शोध पत्र में उल्लेख किए गए वास्तविक दुनिया के उदाहरण

शोध पत्र दिखाता है कि यह काम करता है:

विषम शोर (Heterogeneous Noise): कल्पना करें कि कुछ पिज़्ज़ेरिया बहुत सुसंगत (कम शोर) हैं और अन्य बहुत अस्थिर (उच्च शोर) हैं। FC2FB पुराने तरीकों की तुलना में इसे बेहतर तरीके से संभालता है।
लीनियर बैंडिट्स (Linear Bandits): कल्पना करें कि पिज़्ज़ा की गुणवत्ता सामग्री (जैसे पनीर + पेपरोनी) के रैखिक संयोजन पर निर्भर करती है। FC2FB यहाँ दक्षता में सुधार करता है।
यूनिमॉडल बैंडिट्स (Unimodal Bandits): कल्पना करें कि पिज़्ज़ेरिया एक रेखा में व्यवस्थित हैं, और गुणवत्ता एक शिखर तक जाती है और फिर नीचे गिरती है (जैसे एक पहाड़)। FC2FB पिछले तरीकों की तुलना में शिखर को अधिक कुशलता से खोज सकता है।

सरल शब्दों में

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

यह ऐसा है जैसे यह पता चलना कि यदि आप जानते हैं कि असीमित समय होने पर एक आदर्श केक कैसे बनाया जाता है, तो आप एक सरल, सार्वभौमिक ट्रिक का उपयोग करके ठीक 30 मिनट में लगभग एक आदर्श केक भी बना सकते हैं।

तकनीकी सारांश: लॉगैरिद्मिक कारकों तक, बेस्ट-आर्म आइडेंटिफिकेशन में फिक्स्ड बजट, फिक्स्ड कॉन्फिडेंस से अधिक कठिन नहीं है

समस्या विवरण
यह शोध पत्र इंटरैक्टिव मशीन लर्निंग में बेस्ट-आर्म आइडेंटिफिकेशन (BAI) समस्या को संबोधित करता है, जो विशेष रूप से दो मानक सेटिंग्स के बीच संबंध पर केंद्रित है: फिक्स्ड-कॉन्फिडेंस (FC) और फिक्स्ड-बजट (FB)। FC सेटिंग में, एक लर्नर का लक्ष्य $\delta$ से अधिक विफलता की संभावना के साथ सर्वश्रेष्ठ आर्म (arm) की पहचान करना होता है, जिससे सैंपल कॉम्प्लेक्सिटी (स्टॉपिंग टाइम) को न्यूनतम किया जा सके। FB सेटिंग में, लर्नर को एक निश्चित सैंपलिंग बजट $B$ दिया जाता है और उसका लक्ष्य त्रुटि की संभावना को कम करना होता है। जबकि अनस्ट्रक्चर्ड $K$ -आर्म्ड बैंडिट्स के लिए दोनों सेटिंग्स में इष्टतम सैंपल कॉम्प्लेक्सिटी ज्ञात लॉगैरिद्मिक कारकों तक मेल खाती है, यह स्पष्ट नहीं था कि क्या यह संबंध जेनेरिक, संभावित रूप से स्ट्रक्चर्ड BAI समस्याओं के लिए भी लागू होता है। विशेष रूप से, लेखक जांच करते हैं कि क्या FB मौलिक रूप से FC से कठिन है, या इसके विपरीत, यह देखते हुए कि मौजूदा साहित्य मिश्रित परिणाम दिखाता है, जिसमें कुछ मामलों में FB एल्गोरिदम अतिरिक्त लॉगैरिद्मिक कारक का सामना करते हैं या ज्ञात FB कॉम्प्लेक्सिटी, FC समकक्षों की तुलना में क्रम-वार (order-wise) छोटी होती है।

कार्यप्रणाली (Methodology)
लेखक एक कंस्ट्रक्टिव रिडक्शन फ्रेमवर्क प्रस्तावित करते हैं यह प्रदर्शित करने के लिए कि FB, लॉगैरिद्मिक कारकों तक, FC से अधिक कठिन नहीं है। मुख्य योगदान एक नवीन मेटा-एल्गोरिदम है जिसे FC2FB (फिक्स्ड कॉन्फिडेंस टू फिक्स्ड बजट) कहा जाता है।

FC2FB एल्गोरिदम: यह मेटा-एल्गोरिदम एक इनपुट FC एल्गोरिदम $\mathcal{A}$ को लेता है और उसे एक FB एल्गोरिदम में परिवर्तित करता है। यह कुल बजट $B$ को $R$ चरणों (stages) में विभाजित करके कार्य करता है। प्रत्येक चरण $r$ में, यह एक विशिष्ट विफलता दर $\delta_r$ के साथ इनपुट FC एल्गोरिदम $\mathcal{A}$ को चलाता है, जो चरणों के माध्यम से डबली एक्सपोनेंशियल (doubly exponential) दर से बढ़ती है। यदि $\mathcal{A}$ उस चरण के आवंटित सब-बजट के भीतर स्वयं समाप्त हो जाता है, तो FC2FB उसके आउटपुट को स्वीकार करता है और रुक जाता है। यदि $\mathcal{A}$ समाप्त नहीं होता है, तो चरण को जबरन समाप्त कर दिया जाता है, और एल्गोरिदम उच्च विफलता दर (कम कॉन्फिडेंस आवश्यकता) के साथ अगले चरण की ओर बढ़ता है।
स्ट्रॉन्ग बनाम वीक FC एल्गोरिदम: लेखक "स्ट्रॉन्ग" FC एल्गोरिदम को उन एल्गोरिदम के रूप में परिभाषित करते हैं जिनकी हाई-प्रोबेबिलिटी सैंपल कॉम्प्लेक्सिटी $1/\delta$ के साथ लॉगरिदमिक रूप से स्केल करती है (अर्थात, $T^*_\delta = A \ln(1/\delta) + C$ )। वे शुरू में एक स्ट्रॉन्ग FC इनपुट मानते हुए FC2FB का विश्लेषण करते हैं।
FCW2S फ्रेमवर्क: उन मामलों को संभालने के लिए जहाँ केवल एक "वीक" FC एल्गोरिदम उपलब्ध है (जो एक स्थिर $\delta_0$ के लिए गारंटी देता है या जिसमें $1/\delta$ पर लॉगरिदमिक निर्भरता का अभाव है), लेखक FCW2S (फिक्स्ड-कॉन्फिडेंस वीक टू स्ट्रॉन्ग) पेश करते हैं। यह मेटा-फ्रेमवर्क $L$ स्वतंत्र इंस्टेंस को राउंड-रॉबिन आवंटन का उपयोग करके समानांतर में चलाता है। यह समाप्त हुए इंस्टेंस के बीच बहुमत मतदान (majority voting) के माध्यम से आउटपुट को एकत्रित करता है ताकि एक स्ट्रॉन्ग FC गारंटी प्राप्त की जा सके। यह FC2FB को एल्गोरिदम के एक व्यापक वर्ग पर लागू करने की अनुमति देता है।

मुख्य योगदान और परिणाम

सैद्धांतिक गारंटी: लेखक सिद्ध करते हैं कि FC2FB, इनपुट FC एल्गोरिदम की सैंपल कॉम्प्लेक्सिटी को पॉलीलॉगैरिद्मिक कारकों तक संरक्षित करता है। विशेष रूप से, यदि एक FC एल्गोरिदम की सैंपल कॉम्प्लेक्सिटी $T^*_\delta = A \ln(1/\delta) + C$ है, तो FC2FB के माध्यम से प्राप्त होने वाला FB एल्गोरिदम एक त्रुटि संभावना सीमा प्राप्त करता है जो $\tilde{O}(A \ln(1/\delta))$ की सैंपल कॉम्प्लेक्सिटी को दर्शाती है। यह स्थापित करता है कि इष्टतम FC सैंपल कॉम्प्लेक्सिटी, लॉगैरिद्मिक कारकों तक, इष्टतम FB सैंपल कॉम्प्लेक्सिटी के लिए एक ऊपरी सीमा (upper bound) के रूप में कार्य करती है।
स्ट्रक्चर्ड बैंडिट्स पर अनुप्रयोग: पेपर यह प्रदर्शित करता है कि FC2FB को अत्याधुनिक FC एल्गोरिदम के साथ जोड़ने से कई FB समस्याओं के लिए सैंपल कॉम्प्लेक्सिटी गारंटी में सुधार होता है:
- हेटरोजीनियस नॉइज़ (ज्ञात वेरिएंस): एक फेज़्ड एलिमिनेशन एल्गोरिदम पर FC2FB लागू करने से $\tilde{O}(\sum_{i=2}^K \frac{\sigma_i^2}{\Delta_i^2})$ की सैंपल कॉम्प्लेक्सिटी प्राप्त होती है, जो विशिष्ट उदाहरणों में मौजूदा FB एल्गोरिदम जैसे SHVar ( $\tilde{O}(\sum_{i=2}^K \frac{\sigma_i^2}{\Delta_2^2})$ ) की तुलना में क्रम-वार छोटी है।
- हेटरोजीनियस नॉइज़ (अज्ञात वेरिएंस): VD-BESTARMID के साथ FC2FB का उपयोग करने से उन रेगिम्स में $K$ के कारकों से मौजूदा FB बाउंड्स (जैसे VBR) में सुधार होता है जहाँ सर्वश्रेष्ठ आर्म का वेरिएंस अन्य की तुलना में काफी अधिक होता है।
- लीनियर बैंडिट्स: फिक्स्ड कॉन्फिडेंस पीस (Peace) एल्गोरिदम के साथ FC2FB को मिलाने से डबली लॉगरिदमिक कारकों तक FC लोअर बाउंड से मेल खाने वाली सैंपल कॉम्प्लेक्सिटी प्राप्त होती है, जो अतिरिक्त लॉगरिदमिक निर्भरताओं वाले पिछले FB परिणामों में सुधार करती है।
- यूनिमोडल बैंडिट्स: पहले एक कमजोर FC एल्गोरिदम (UniTT) को FCW2S के माध्यम से एक स्ट्रॉन्ग एल्गोरिदम में बदलकर, और फिर FC2FB लागू करके, लेखक एक FB सैंपल कॉम्प्लेक्सिटी प्राप्त करते हैं जो स्थानीय सूचना-सैद्धांतिक मात्राओं ( $T_\mu(\delta)$ ) पर निर्भर है, जो मौजूदा FB एल्गोरिदम की ग्लोबल गैप-डिपेंडेंट कॉम्प्लेक्सिटी ( $\Delta^{-2}$ ) की तुलना में क्रम-वार छोटी है।

महत्व और दावे
पेपर का दावा है कि यह FB और FC सेटिंग्स के बीच एक मौलिक संबंध को प्रकट करता है, यह हल करते हुए कि सापेक्ष कठिनाई का प्रश्न क्या है—यह दिखाकर कि FB, लॉगैरिद्मिक कारकों तक, FC से अधिक कठिन नहीं है। इसका महत्व FC2FB मेटा-एल्गोरिदम की व्यावहारिक उपयोगिता में निहित है: यह शोधकर्ताओं को FC साहित्य से बेहतर सैंपल कॉम्प्लेक्सिटी गारंटियों को FB सेटिंग में स्थानांतरित करने की अनुमति देता है। यह विभिन्न स्ट्रक्चर्ड बैंडिट समस्याओं के लिए बेहतर सैद्धांतिक गारंटी वाले FB एल्गोरिदम बनाने का एक व्यवस्थित तरीका प्रदान करता है। लेखक नोट करते हैं कि उनका परिणाम सैंपल-कॉम्प्लेक्सिटी गारंटियों के बीच एक नॉन-एसिम्प्टोटिक रिडक्शन है और यह एक सार्वभौमिक रूप से एक्सपोनेंट-ऑप्टिमल FB एल्गोरिदम के अस्तित्व का दावा नहीं करता है। गाऊसी (Gaussian) बैंडिट्स पर अनुभवजन्य (empirical) परिणाम सैद्धांतिक निष्कर्षों का समर्थन करते हैं, जो दिखाते हैं कि FC2FB विभिन्न बजट और आर्म्स की संख्या के तहत मिस-आइडेंटिफिकेशन प्रोबेबिलिटी के मामले में मौजूदा FB एल्गोरिदम जैसे Sequential Halving (SH) और SHVar को पछाड़ता है।