🤖 AI

Functional multi-armed bandit and the best function identification problems

यह शोध पत्र प्रतिस्पर्धी LLM प्रशिक्षण जैसे वास्तविक परिदृश्यों को संबोधित करने के लिए फंक्शनल मल्टी-आर्म्ड बैंडिट और बेस्ट फंक्शन आइडेंटिफिकेशन समस्या वर्गों को पेश करता है, जो एक नवीन F-LCB रिडक्शन स्कीम का प्रस्ताव करता है जो गैर-रेखीय अनुकूलन अभिसरण दरों (nonlinear optimization convergence rates) पर आधारित सिद्ध रिग्रेट बाउंड्स के साथ UCB-प्रकार के एल्गोरिदम का निर्माण करता है।

मूल लेखक: Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva

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

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

CC BY 4.0

मूल लेखक: Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva

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

कल्पना कीजिए कि आप एक शेफ हैं जो एक भव्य दावत के लिए सौ उम्मीदवारों में से एक सबसे बेहतरीन रेसिपी खोजने की कोशिश कर रहे हैं। आपके पास समय और सामग्री (एक "बजट") सीमित है।

पुराने तरीकों में (पारंपरिक तरीकों में), आप शायद हर केक का थोड़ा-थोड़ा हिस्सा बेक करेंगे, उन्हें चखेंगे, और फिर निर्णय लेंगे। या, आप एक केक को अंत तक पूरा बेक करेंगे, फिर अगले को, और फिर अगले को। ये दोनों दृष्टिकोण धीमे और बर्बादी वाले हैं। यदि आपके पास 100 केक हैं, तो हो सकता है कि आप पहले कुछ केक खत्म करने से पहले ही अपना समय समाप्त कर दें।

यह शोध पत्र इस समस्या को हल करने के एक स्मार्ट तरीके को पेश करता है, जिसे लेखक फंक्शनल मल्टी-आर्म्ड बैंडिट (FMAB) और बेस्ट फंक्शन आइडेंटिफिकेशन (BFI) कहते हैं।

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

1. समस्या: "ब्लैक बॉक्स" केक प्रतियोगिता

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

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

2. नया विचार: "स्मार्ट टेस्टिंग" (F-LCB)

लेखक एक नया एल्गोरिदम प्रस्तावित करते हैं जिसे F-LCB कहा जाता है। इसे एक बहुत ही स्मार्ट 'सू-शेफ' (sous-chef) के रूप में समझें जो केवल केक का स्वाद नहीं लेता; वह बेकिंग के भौतिक विज्ञान (physics) को भी समझता है।

प्रत्येक रेसिपी को एक रहस्यमयी बॉक्स मानने के बजाय, F-LCB प्रत्येक रेसिपी को एक ज्ञात गति सीमा (known speed limit) वाली प्रक्रिया के रूप में देखता है।

उपमा: कल्पना करें कि आप जानते हैं कि "रेसिपी A" (एक साधारण स्पंज केक) आमतौर पर हर मिनट में आकार में दोगुना होता है। "रेसिपी B" (एक घना फ्रूटकेक) केवल 1% बढ़ता है।
F-LCB कैसे काम करता है:
1. यह सभी रेसिपीज़ को थोड़ा सा बेक करना शुरू करता है।
2. यह "लोअर कॉन्फिडेंस बाउंड" (LCB) को देखता है। यह एक फैंसी तरीका है यह कहने का: "इस केक के बढ़ने की गति के आधार पर, इसके अंतिम स्वाद के लिए सबसे खराब स्थिति (worst-case scenario) क्या हो सकती है?"
3. यदि कोई केक इसकी क्षमता की तुलना में बहुत धीरे बढ़ रहा है, तो एल्गोरिदम कहता है, "यह एक हारने वाला (loser) होने की संभावना है," और उसे बेक करना बंद कर देता है।
4. यह अपना सारा बचा हुआ समय और सामग्री उन रेसिपीज़ में डाल देता है जो सबसे अधिक संभावना दिखा रही हैं।

3. यह पुराने तरीकों से बेहतर क्यों है?

पेपर अपने तरीके की तुलना दो प्रसिद्ध प्रतिस्पर्धियों से करता है: सक्सेसिव हैल्विंग (Successive Halving) और हाइपरबैंड (Hyperband)।

प्रतिस्पर्धी: ये एक ऐसे शेफ की तरह हैं जो हर राउंड में अपना बजट आधा कर देता है। वे सबको थोड़ा बेक करते हैं, नीचे के 50% को हटा देते हैं, बाकी को थोड़ा और बेक करते हैं, फिर से नीचे के 50% को हटा देते हैं। यह कुशल है, लेकिन थोड़ा कठोर (rigid) है। इसे इस बात की परवाह नहीं है कि केक कैसे बढ़ रहा है, यह केवल वर्तमान स्वाद की परवाह करता है।
F-LCB (लेखकों का तरीका): यह शेफ ट्रैजेक्टरी (trajectory/पथ) को देखता है। यदि कोई केक तेजी से बढ़ रहा है, तो F-LCB जानता है कि यह जल्द ही शानदार होगा और इस पर ध्यान केंद्रित करता है। यदि कोई केक धीरे बढ़ रहा है, तो वह जानता है कि यह कभी भी मुकाबला नहीं कर पाएगा।
परिणाम: अपने प्रयोगों में (कंप्यूटर पर डिजिटल केक बेक करते हुए), F-LCB ने अन्य प्रतिस्पर्धियों की तुलना में तेजी से और कम कंप्यूटिंग पावर के साथ सबसे अच्छा मॉडल खोज निकाला, खासकर जब बजट कम था।

4. उन्होंने क्या साबित किया?

लेखकों ने केवल यह अनुमान नहीं लगाया कि यह काम करेगा; उन्होंने गणित के माध्यम से इसे सिद्ध किया।

लोअर बाउंड (Lower Bound): उन्होंने सिद्ध किया कि आप चाहे कितने भी चतुर क्यों न हों, एक निश्चित समय आपको सबसे अच्छा केक खोजने के लिए खर्च करना ही होगा।
अपर बाउंड (Upper Bound): उन्होंने सिद्ध किया कि उनका F-LCB एल्गोरिदम उस न्यूनतम समय सीमा के बहुत करीब पहुँच जाता है। यह गणितीय रूप से जितना संभव है उतना कुशल है (एक छोटी त्रुटि के अंतर के भीतर)।

5. वास्तविक दुनिया के परीक्षण

उन्होंने इसे तीन परिदृश्यों में टेस्ट किया:

स्मूथ केक्स (Smooth Cakes): मानक, सुव्यवस्थित गणितीय फलन (functions)। F-LCB ने सबसे अच्छे को जल्दी खोज लिया।
रफ केक्स (Rough Cakes): फलन जो ऊबड़-खाबड़ और अनुकूलित (optimize) करने में कठिन हैं। F-LCB अभी भी अच्छा काम करता है।
न्यूरल नेटवर्क: उन्होंने इमेज क्लासिफिकेशन टास्क (तस्वीरों में वस्तुओं की पहचान) के लिए सबसे अच्छा AI आर्किटेक्चर चुनने के लिए इसका उपयोग किया। F-LCB ने अन्य तरीकों की तुलना में कम ट्रेनिंग स्टेप्स का उपयोग करके सबसे अच्छा मॉडल पहचाना।

सारांश

पेपर कहता है: "अंधाधुंध अनुमान लगाना बंद करें। अपने ऑप्टिमाइजेशन प्रोसेस की ज्ञात गति का उपयोग यह अनुमान लगाने के लिए करें कि कौन से मॉडल जीतेंगे, और उन पर समय बर्बाद करना बंद करें जो पहले से ही हार रहे हैं।"

उन्होंने एक उपकरण (F-LCB) बनाया है जो एक स्मार्ट मैनेजर की तरह काम करता है, जो लगातार प्रत्येक उम्मीदवार की प्रगति की जांच करता रहता है, धीमी गति वाले उम्मीदवारों को जल्दी बाहर कर देता है, और सारा संसाधन विजेता में डाल देता है, जिससे इस प्रक्रिया में समय और पैसे की भारी बचत होती है।

तकनीकी सारांश: फंक्शनल मल्टी-आर्म्ड बैंडिट और बेस्ट फंक्शन आइडेंटिफिकेशन

1. समस्या विवरण

यह शोध पत्र सीमित कम्प्यूटेशनल बजट वाले परिदृश्यों में मॉडल चयन समस्या (model selection problem) को संबोधित करता है, जैसे कि प्रतिस्पर्धी न्यूरल नेटवर्क प्रशिक्षण। मुख्य चुनौती $K$ संभावित पैरामेट्रिक फलनों $\{f_1, \dots, f_K\}$ में से इष्टतम फलन (जैसे, सबसे अच्छा न्यूरल नेटवर्क आर्किटेक्चर या हाइपरपैरामीटर सेटिंग) की पहचान करना है, जहाँ प्रत्येक फलन एक उत्तल निर्णय सेट (convex decision set) $X_i$ पर परिभाषित है।

लेखक दो नए समस्या सेटअप पेश करते हैं जो शास्त्रीय मल्टी-आर्म्ड बैंडिट (MAB) और बेस्ट आर्म आइडेंटिफिकेशन (BAI) का सामान्यीकरण करते हैं:

फंक्शनल मल्टी-आर्म्ड बैंडिट (FMAB): एजेंट प्रत्येक समय चरण $t$ पर एक इंडेक्स $i_t$ और एक निर्णय वेक्टर $x_{t, i_t} \in X_{i_t}$ चुनता है। लक्ष्य संचयी रिग्रेट (cumulative regret) $R_O(T) = \sum_{t=1}^T [f_{i_t}(x_{t, i_t}) - f^*]$ को कम करना है, जहाँ $f^* = \min_{i} \min_{x \in X_i} f_i(x)$ है। मानक MAB के विपरीत, जहाँ आर्म्स रैंडम वेरिएबल्स होते हैं, यहाँ प्रत्येक आर्म एक अज्ञात फलन है जिसे एक ब्लैक-बॉक्स ऑरेकल (जैसे, ग्रेडिएंट्स) के माध्यम से अनुकूलित किया जाता है।
बेस्ट फंक्शन आइडेंटिफिकेशन (BFI): एजेंट $T$ राउंड के बाद एक एकल सर्वश्रेष्ठ फलन $J_T$ की पहचान करने का लक्ष्य रखता है ताकि अंतिम रिग्रेट $R_B(T) = \min_{x \in X_{J_T}} f_{J_T}(x) - f^*$ को न्यूनतम किया जा सके।

लेखक तर्क देते हैं कि इन समस्याओं को मानक MAB में बदलने (प्रत्येक बिंदु $x$ को एक आर्म मानकर) से निरंतर निर्णय स्थानों (continuous decision spaces) के कारण अत्यधिक कम्प्यूटेशनल लागत आएगी। इसके बजाय, प्रस्तावित ढांचा आधारभूत अनुकूलन एल्गोरिदम की आंतरिक गतिशीलता का लाभ उठाता है।

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

FMAB और BFI को हल करने के लिए, लेखक F-LCB (फंक्शनल लोअर कॉन्फिडेंस बाउंड) एल्गोरिदम का प्रस्ताव करते हैं। यह एक UCB-प्रकार का एल्गोरिदम है जो रैंडम वेरिएबल्स के सांख्यिकीय संकेंद्रण (statistical concentration) के बजाय आधारभूत अनुकूलन एल्गोरिदम की अभिसरण दरों (convergence rates) के आधार पर कॉन्फिडेंस इंटरवल का निर्माण करता है।

मुख्य तंत्र

आधारभूत ऑप्टिमाइज़र (Base Optimizers): प्रत्येक संभावित फलन $f_i$ एक आधारभूत अनुकूलन एल्गोरिदम $A_i$ (जैसे, प्रोजेक्टेड ग्रेडिएंट डिसेंट, एक्सीलरेटेड ग्रेडिएंट डिसेंट) से जुड़ा होता है, जिसकी एक विशिष्ट अभिसरण दर $g_i(k, \delta)$ ज्ञात होती है।
लोअर कॉन्फिडेंस बाउंड (LCB): प्रत्येक चरण में, एल्गोरिदम प्रत्येक फलन $i$ के लिए एक LCB बनाए रखता है:
$LCB_i(k_i, \delta) = f_i(x_{i, k_i}) - g_i(k_i, \delta)$
यहाँ, $k_i$ फलन $i$ को आवंटित किए गए चरणों की संख्या है, और $g_i(k_i, \delta)$ $k_i$ चरणों के बाद सब-ऑप्टिमलिटी गैप (sub-optimality gap) पर सैद्धांतिक ऊपरी सीमा है।
चयन नियम (Selection Rule): एल्गोरिदम न्यूनतम LCB मान वाले आर्म $i_t$ का चयन करता है।
अपडेट: यह आधारभूत ऑप्टिमाइज़र $A_{i_t}$ का एक इटरेशन करता है, फलन मान को अपडेट करता है, और LCB की पुनर्गणना करता है।
स्टॉपिंग क्राइटेरिया (BFI के लिए): प्रक्रिया तब रुक जाती है जब वर्तमान सर्वोत्तम अनुमान और LCB के बीच का अंतर $\epsilon$ थ्रेसहोल्ड से नीचे गिर जाता है, जिससे यह सुनिश्चित होता है कि पहचाना गया फलन ग्लोबल ऑप्टिमम के $\epsilon$ के भीतर है।

एल्गोरिदम प्रभावी रूप से अन्वेषण (exploration - उन फलनों को बजट आवंटित करना जिनमें उच्च अनिश्चितता या आशाजनक क्षमता है) और दोहन (exploitation - सर्वोत्तम उम्मीदवार को परिष्कृत करना) के बीच संतुलन बनाता है, क्योंकि यह तुरंत प्रतिक्रिया देता है जब किसी आर्म का Lب (LCB) उप-इष्टतम हो जाता है।

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

सैद्धांतिक योगदान

समस्या का स्वरूप (Problem Formulation): यह शोध पत्र FMAB और BFI फ्रेमवर्क पेश करता है, जो आर्म्स को ज्ञात अभिसरण गुणों वाले अनुकूलन कार्यों के रूप में मॉडल करके उन्हें शास्त्रीय MAB से औपचारिक रूप से अलग करता है।
लोअर बाउंड्स (Lower Bounds): लेखक नियत (deterministic) सेटिंग्स में दोनों के लिए मिनिमैक्स लोअर बाउंड्स स्थापित करते हैं। ये बाउंड्स फलन वर्गों (जैसे, कॉनवेक्स $M$ $M$ -लिप्सचिट्ज़, $L$ $L$ -स्मूथ, $\mu$ $μ$ -स्ट्रॉन्गली कॉनवेक्स) की जटिलता पर निर्भर करते हैं।
- उदाहरण के लिए, कॉनवेक्स $M$ -लिप्सचिट्ज़ फलनों के लिए, लोअर बाउंड $\Omega(MR\sqrt{T})$ है।
- $\mu$ -स्ट्रॉन्गली कॉ는 और $L$ -स्मूथ फलनों के लिए, बाउंड $\Omega(R^2)$ है।
रिग्रेट अपर बाउंड्स (Regret Upper Bounds): शोध पत्र सिद्ध करता है कि F-LCB एल्गोरिदम प्राप्त लोअर बाउंड्स के लॉगरिदमिक कारकों तक मेल खाने वाले रिग्रेट अपर बाउंड्स प्राप्त करता है।
- नियत मामले में, रिग्रेट आधारभूत ऑप्टिमाइज़र के अभिसरण दर $r$ पर निर्भर करता है (जैसे, $r=1/2$ के लिए $O(\sqrt{T})$ )।
- स्टोकेस्टिक मामले (इनएक्सैक्ट ऑरेकल) में, बाउंड्स शोर मापदंडों (noise parameters) को शामिल करते हैं और उच्च संभावना के साथ लागू होते हैं।

एल्गोरिद्मिक योगदान

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

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

लेखक सिंथेटिक और वास्तविक दुनिया के डेटासेट पर F-LCB को मान्य करते हैं:

सिंथेटिक कॉनवेक्स फंक्शन्स:
- स्मूथ कॉनवेक्स: F-LCB ने तीन उम्मीदवारों में से ग्लोबल मिनिमम वाले फलन की सफलतापूर्वक पहचान की, और उप-इष्टतम फलनों को अपडेट करना बंद कर दिया।
- नॉन-स्मूथ कॉनवेक्स: पीस-वाइज लीनियर फलनों और सबग्रेडिएंट मेथड का उपयोग करते हुए, F-LCB ने इष्टतम फलन की ओर अभिसरण प्रदर्शित किया, जिसका संचयी रिग्रेट सैद्धांतिक बाउंड्स के अनुरूप था।
- इनएक्सेक्ट ऑरेकल: ग्रेडिएंट नॉइज़ की उपस्थिति में, F-LCB ने अभी भी सर्वश्रेष्ठ फलन की पहचान की, हालांकि अभिसरण वक्र (convergence curves) नियत मामले की तुलना में कम स्पष्ट थे।
न्यूरल नेटवर्क चयन (BFI):
- सेटअप: एल्गोरिदम को CIFAR-100 इमेज क्लासिफिकेशन टास्क पर लागू किया गया, जिसमें 5M से कम पैरामीटर्स वाले 10 मॉडल्स (MobileNet, ShuffleNet, और ResNet वेरिएंट सहित) में से सर्वश्रेष्ठ आर्किटेक्चर को चुना गया।
- तुलना: F-LCB की तुलना SuccessiveHalving (SH) और Hyperband से की गई।
- परिणाम: F-LCB कम-बजट परिदृश्यों (जैसे, $T=50, 100$ ) में दोनों बेसलाइन से बेहतर प्रदर्शन करता है, जिससे चयनित मॉडल के लिए कम औसत रैंक प्राप्त होती है। Hyperband के विपरीत, जो कई SH रन के माध्यम से बजट को विभाजित करता है, F-LCB मॉडल्स को स्थायी रूप से हटाता नहीं है बल्कि संसाधनों को गतिशील रूप से आवंटित करता है। बड़े बजट ( $T \ge 350$ ) में, F-LCB का प्रदर्शन SH के समान रहा, और इसने लगातार सर्वश्रेष्ठ मॉडल की पहचान की।

5. महत्व और दावे

शोध पत्र का दावा है कि F-LCB, हीयुरिस्टिक ऑटोML विधियों (जैसे SuccessiveHalving और Hyperband) और शुद्ध ब्लैक-बॉक्स दृष्टिकोणों (जैसे Bayesian Optimization) के लिए एक सैद्धांतिक रूप से सुदृढ़ (theoretically grounded) विकल्प प्रदान करता है।

सैद्धांतिक गारंटी: हीयुरिस्टिक विधियों के विपरीत, F-LCB औपचारिक रिग्रेट गारंटी और आइडेंटिफिकेशन बाउंड्स प्राप्त करने के लिए अनुकूलन प्रक्रियाओं की ज्ञात अभिसरण दरों का लाभ उठाता है।
दक्षता (Efficiency): यह दृष्टिकोण विशेष रूप से तब प्रभावी है जब कम्प्यूटेशनल बजट कम होता है, क्योंकि यह उन उप-एक्सपोनेंशियल लागतों से बचता है जो अनुकूलन समस्याओं को अनंत आर्म्स वाले मानक MAB के रूप में मानने से जुड़ी होती हैं।
अनुप्रयोग योग्यता: यह ढांचा किसी भी ऐसे परिदृश्य के लिए लागू करने योग्य है जहाँ उम्मीदवार मॉडल्स को ज्ञात अभिसरण गुणों वाले इटरेटिव ऑप्टिमाइज़ेशन के माध्यम से हल किया जाता है (जैसे, कॉनवेक्स रिलैक्सेशन, विशिष्ट ऑप्टिमाइज़ेशन मेथड सिलेक्शन)।

लेखकों द्वारा स्वीकार की गई सीमाएं

शोध पत्र स्पष्ट रूप से नोट करता है कि इस दृष्टिकोण के लिए ऑब्जेक्टिव के फंक्शनल क्लास और आधारभूत एल्गोरिदम की अभिसरण दर $g(k, \delta)$ के पूर्व ज्ञान की आवश्यकता होती है। यह डीप लर्निंग के लिए एक महत्वपूर्ण बाधा है, जहाँ नॉन-कॉन्वेक्स न्यूरल नेटवर्क ट्रेनिंग के लिए अभिसरण दरें एल्गोरिदम की परिभाषा के अनुसार सटीक रूप से परिभाषित नहीं हैं। फलस्वरूप, जबकि यह विधि कॉनवेक्स समस्याओं और विशिष्ट ऑप्टिमाइज़ेशन कार्यों के लिए काम करती है, सामान्य न्यूरल नेटवर्क ट्रेनिंग के लिए इसका अनुप्रयोग $g(k)$ के हीयुरिस्टिक अनुमानों पर निर्भर करता है।