⚡ electrical engineering

Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy

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

मूल लेखक: Ishank Juneja, Carlee Joe-Wong, Osman Yağan

प्रकाशित 2026-05-11

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

CC BY 4.0

मूल लेखक: Ishank Juneja, Carlee Joe-Wong, Osman Yağan

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

यहाँ सरल भाषा और रचनात्मक उपमाओं (analogies) का उपयोग करके शोध पत्र (paper) का स्पष्टीकरण दिया गया है।

बड़ी तस्वीर: "बजट-अनुकूल गुणवत्ता" की समस्या

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

समस्या यह है: आपको अभी तक यह नहीं पता कि सबसे अच्छा व्यंजन कौन सा है। उनकी गुणवत्ता समझने के लिए आपको अलग-अलग रेसिपी का स्वाद लेना (सैंपल लेना) होगा। लेकिन हर बार जब आप किसी व्यंजन का स्वाद लेते हैं, तो वह आपसे पैसे खर्च करवाता है (सामग्री, समय, शेफ का वेतन)।

लक्ष्य: सबसे सस्ता व्यंजन ढूँढना जो आपके "सबसे अच्छे का 80%" वाले गुणवत्ता नियम को पूरा करता हो।
जाल: यदि आप हर चीज़ का रैंडम तरीके से स्वाद लेते हैं, तो आप एक बड़ी धनराशि बर्बाद कर देंगे। यदि आप बहुत जल्दी रुक जाते हैं, तो आप एक सस्ता व्यंजन चुन सकते हैं जो वास्तव में बहुत खराब (80% की रेखा से नीचे) निकला।

यह पेपर इस समस्या के एक विशिष्ट संस्करण को संबोधित करता है जिसे मल्टी-आर्म्ड बैंडिट्स विद कॉस्ट सब्सिडी (MAB-CS) कहा जाता है। कंप्यूटर विज्ञान के शब्दों में, "व्यंजनों" को "आर्म्स" (arms) कहा जाता है, और "स्वाद लेने" को "सैंपलिंग" (sampling) कहा जाता है।

पुराना तरीका बनाम नया तरीका

पुराना तरीका (पिछले एल्गोरिदम):
पिछले तरीकों ने इसे दो सख्त चरणों में हल करने की कोशिश की:

चरण 1: तब तक सब कुछ चखें जब तक कि आप 100% सुनिश्चित न हो जाएं कि कौन सा एकल व्यंजन बिल्कुल सबसे अच्छा है।
चरण 2: एक बार जब आपको सबसे अच्छा पता चल जाए, तो 80% की रेखा की गणना करें, और फिर सस्ते व्यंजनों को चखना शुरू करें कि क्या वे पास होते हैं।

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

नया तरीका (COF एल्गोरिदम):
लेखकों ने कॉस्ट-ऑर्डर्ड फिएसिबिलिटी (COF) नामक एक नया एल्गोरिदम प्रस्तावित किया है। "सबसे अच्छे" की तलाश करने के बजाय, COF एक स्मार्ट, लागत-सचेत मैनेजर की तरह काम करता है:

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

नए एल्गोरिदम (COF) की मुख्य विशेषताएं

पेपर इस नए तरीके के दो "सुपरपावर्स" पर प्रकाश डालता है:

1. "ग्रुप हग" (नमूनों को संयोजित करना)
कल्पना कीजिए कि आप यह साबित करने की कोशिश कर रहे हैं कि एक सस्ता व्यंजन बुरा है। एक महंगे व्यंजन के जीतने का इंतज़ार करने के बजाय, COF कई महंगे व्यंजनों से कमजोर साक्ष्य एकत्र करता है।

उपमा: यदि एक व्यक्ति कहता है, "यह बर्गर थोड़ा सूखा लग रहा है," तो यह शेफ को निकालने के लिए पर्याप्त नहीं है। लेकिन यदि 10 लोग कहते हैं, "यह थोड़ा सूखा लग रहा है," और आप उनकी राय को जोड़ देते हैं, तो आपके पास शेफ को हटाने का एक मजबूत मामला है। COF कई महंगे विकल्पों से इन छोटी शंकाओं को जोड़कर तेजी से खराब सस्ते विकल्पों को खारिज कर देता है।

2. "स्पीड बंप" (एक्सक्लूसिव सैंपलिंग)
कभी-कभी, एल्गोरिदम भ्रमित हो जाता है। यह एक सस्ते व्यंजन का परीक्षण कर रहा है, लेकिन यह गुणवत्ता का मानक (quality bar) निर्धारित करने के लिए महंगे व्यंजनों का भी स्वाद ले रहा है। यदि सस्ता व्यंजन महंगे व्यंजनों की तुलना में कितनी बार चखा गया है, इस मामले में पीछे रह जाता है, तो COF एक पल के लिए महंगे व्यंजनों को चखना बंद कर देता है और केवल सस्ते व्यंजन पर ध्यान केंद्रित करता है ताकि उसे बराबरी पर लाया जा सके।

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

उन्होंने क्या सिद्ध किया?

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

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

एक वाक्य में सारांश

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

तकनीकी सारांश: मल्टी-आर्म्ड बैंडिट्स के लिए कॉस्ट-ऑर्डर्ड फिजिबिलिटी (Cost-Ordered Feasibility)

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

यह शोध पत्र मल्टी-आर्म्ड बैंडिट्स विद कॉस्ट सब्सिडी (MAB-CS) समस्या को संबोधित करता है, जो एक लागत-संवेदनशील ऑनलाइन निर्णय लेने का ढांचा है जिसे संचयी लागत (cumulative cost) को एक गुणवत्ता बाधा (quality constraint) के अधीन न्यूनतम करने के लिए डिज़ाइन किया गया है। मानक MABs के विपरीत, जो संचयी पुरस्कार (cumulative reward) को अधिकतम करते हैं, MAB-CS उन सबसे सस्ते 'आर्म्स' (arms) की खोज करता है जो न्यूनतम अपेक्षित पुरस्कार थ्रेशोल्ड को पूरा करते हैं।

यहाँ जांचा गया विशिष्ट परिवेश एक गुणवत्ता बाधा है जो अज्ञात सर्वोत्तम पुरस्कार के सापेक्ष परिभाषित है। $\mathcal{A} = \{a_1, \dots, a_K\}$ आर्म्स के एक सेट के साथ, जिनके अपेक्षित पुरस्कार $\mu_k$ और ज्ञात सैंपलिंग लागत $c_k$ हैं, व्यवहार्य सेट (feasible set) $S = \{a_k \in \mathcal{A} \mid \mu_k \geq \mu_{CS}\}$ है। थ्रेशोल्ड $\mu_{CS} = (1-\alpha)\mu^*$ द्वारा परिभाषित है, जहाँ $\mu^* = \max_{a_k \in \mathcal{A}} \mu_k$ सिस्टम में अज्ञात सर्वोत्तम पुरस्कार है और $\alpha \in (0, 1)$ एक सब्सिडी कारक (subsidy factor) है। इष्टतम आर्म $a^*$ व्यवहार्य सेट $S$ में सबसे सस्ता आर्म है।

यह पत्र दो रिग्रेट मेट्रिक्स को परिभाषित करता है:

कॉस्ट रिग्रेट (Cost Regret): इष्टतम आर्म $a^*$ के सापेक्ष होने वाली अतिरिक्त लागत।
क्वालिटी रिग्रेट (Quality Regret): जब चयनित आर्म का अपेक्षित पुरस्कार व्यवहार्यता थ्रेशोल्ड $\mu_{CS}$ से नीचे गिर जाता है, तो होने वाला दंड।

मुख्य चुनौती इन दोनों रिग्रेट्स को कम करने के साथ-साथ अज्ञात थ्रेशोल्ड $(1-\alpha)\mu^*$ का अनुमान लगाने और अज्ञात $\mu^*$ के बिना सबसे सस्ते व्यवहार्य आर्म की पहचान करने की है।

कार्यप्रणाली: COF एल्गोरिदम

लेखक MAB-CS समस्या को हल करने के लिए कॉस्ट-ऑर्डर्ड फिजिबिलिटी (COF) एल्गोरिदम प्रस्तावित करते हैं। COF ज्ञात लागतों के बढ़ते क्रम में आर्म्स का मूल्यांकन करके कार्य करता है। प्रत्येक संभावित आर्म $a_\ell$ के लिए, एल्गोरिदम "गेटिंग आर्म्स" (वे आर्म्स जो $a_\ell$ से अधिक महंगे हैं) के एक सेट के विरुद्ध तुलना करके व्यवहार्यता निर्धारित करता है।

COF में मुख्य तंत्र शामिल हैं:

कॉस्ट-ऑर्डर्ड इवैल्यूएशन (Cost-Ordered Evaluation): आर्म्स का परीक्षण सबसे सस्ते से सबसे महंगे के क्रम में किया जाता है। जो पहला आर्म व्यवहार्य पाया जाता है, उसे शेष क्षितिज (horizon) के लिए इष्टतम आर्म के रूप में चुना जाता है।
सैंपल्स को संयोजित करना (Combining Samples/Aggregation): यह निर्धारित करने के लिए कि क्या एक संभावित आर्म $a_\ell$ गैर-व्यवहार्य है, COF केवल एक युग्मवार (pairwise) तुलना पर निर्भर नहीं रहता है। इसके बजाय, यह उन सभी आर्म्स के साथ तुलनाओं से साक्ष्य एकत्र करता है जो $a_\ell$ को अयोग्य घोषित करने में सक्षम हैं। यह प्रत्येक गेटिंग आर्म के सापेक्ष $a_\ell$ के व्यवहार्य होने की संभावना का ऊपरी स्तर (upper bound) निकालता है और $a_\ell$ को तब गैर-व्यव्यवहार्य मानता है जब इन संभावनाओं का गुणनफल एक सहनशीलता $\delta$ से नीचे गिर जाता है।
एक्सक्लूसिव सैंपलिंग (Exclusive Sampling): यदि किसी संभावित आर्म की सैंपल संख्या सबसे अधिक सैंपल वाले गेटिंग आर्म से पीछे रह जाती है, तो COF "पकड़ने" के लिए केवल उस उम्मीदवार का विशेष रूप से नमूना लेता है, जिससे उप-इष्टतम नमूनों की कुल संख्या कम हो जाती है।
BAI-फिल्टर: एक उम्मीदवार के मूल्यांकन के दौरान, COF एक फिल्टर का उपयोग करता है जो उन गेटिंग आर्म्स की सैंपलिंग को रोकता है जिनका अपर कॉन्फिडेंस बाउंड (UCB) दूसरे गेटिंग आर्म के लोअर कॉन्फिडेंस बाउंड (LCB) से नीचे गिर जाता है। यह उन आर्म्स पर नमूने बर्बाद करने से बचाता है जिनके सर्वोत्तम पुरस्कार ( $i^*$ ) होने की सांख्यिकीय संभावना कम है।

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

यह पत्र MAB-CS का एक कठोर सैद्धांतिक विश्लेषण प्रदान करता है, जो रिग्रेट के लिए निचले (lower) और ऊपरी (upper) दोनों स्तरों को स्थापित करता है।

इंस्टेंस-डिपेंडेंट लोअर बाउंड्स (Instance-Dependent Lower Bounds):
- लेखक सस्ते आर्म्स (लागत $< c_{a^*}$ ) और महंगे आर्म्स (लागत $> c_{a^*}$ ) के लिए नमूनों की अपेक्षित संख्या पर लोअर बाउंड प्राप्त करते हैं।
- एक अभिनव योगदान समूह के लिए संयुक्त लोअर बाउंड (joint lower bound) है। यह विचार दर्शाता है कि एक आर्म को तब अयोग्य घोषित किया जा सकता है यदि उसका पुरस्कार किसी भी मनमाने आर्म के सब्सिडीकृत पुरस्कार से खराब हो, न कि केवल सर्वोत्तम पुरस्कार $i^*$ से। यह उन पूर्ववर्ती बाउंड्स का सामान्यीकरण करता है जिन्होंने $i^*$ को एकल रूप से माना था।
COF के लिए रिग्रेट अपर बाउंड्स:
- यह पत्र COF के लिए अपेक्षित संचयी लागत और क्वालिटी रिग्रेट पर इंस्टेंस-डिपेंडेंट अपर बाउंड स्थापित करता है।
- सस्ते आर्म्स के लिए, बाउंड $O(\log T / \Delta_{Q,k}^2)$ निर्भरता के साथ ऑर्डर-ऑप्टिमल है, जो लोअर बाउंड्स में पाई गई निर्भरता से मेल खाता है।
- महंगे आर्म्स के लिए, बाउंड दो पदों के अधिकतम पर निर्भर करता है: एक आर्म और इष्टतम आर्म के बीच के अंतर से संबंधित, और दूसरा सबसे सस्ते व्यवहार्य आर्म को हटाने के लिए आवश्यक संयुक्त अंतर से संबंधित। लेखक महंगे आर्म्स के लिए लोअर और अपर बाउंड के बीच मामूली विसंगति देखते हैं, जो सैंपल कॉम्प्लेक्सिटी के सैद्धांतिक विश्लेषण में सुधार की गुंजाइश का सुझाव देती है।

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

लेखक व्यापक सिमुलेशन के माध्यम से COF को सत्यापित करते हैं:

वास्तविक डेटासेट: Goodreads (बुक रेटिंग) और MovieLens (मूवी रेटिंग), जहाँ शैलियाँ (genres) बैंडिट आर्म्स के रूप में कार्य करती हैं।
सिंथेटिक इंस्टेंस: विशिष्ट एल्गोरिथम व्यवहारों का परीक्षण करने के लिए डिज़ाइन किए गए समस्याएं।

मुख्य निष्कर्ष:

प्रदर्शन: COF लगातार बेसलाइन एल्गोरिदम, जिनमें ETC-CS (फिक्स्ड बजट एक्सप्लोरेशन), PE-CS (पेयरवाइज एलिमिनेशन), UCB-CS, और TS-CS शामिल हैं, को पछाड़ता है।
मजबूती (Robustness): UCB-CS और TS-CS के विपरीत, जो अपने अनुभवजन्य व्यवहार्य सेटों में सस्ते, गैर-व्यवहार्य आर्म्स को गलत तरीके से शामिल करने के कारण लीनियर रिग्रेट का शिकार हो सकते हैं, COF व्यवहार्यता का कड़ाई से परीक्षण करके सब-लीनियर रिग्रेट बनाए रखता है।
सब्सिडी फैक्टर संवेदनशीलता: जबकि PE-CS बहुत छोटे सब्सिडी कारकों ( $\alpha$ ) के लिए थोड़ा बेहतर प्रदर्शन करता है, COF उस प्रदर्शन ठहराव (plateauing) से बचता है जो $\alpha$ बढ़ने पर PE-CS में देखा जाता है।
एब्लेशन स्टडीज (Ablation Studies): प्रयोग पुष्टि करते हैं कि "कंबाइनिंग सैंपल्स" और "एक्सक्लूसिव सैंपलिंग" की विशेषताएं एल्गोरिदम की दक्षता के लिए महत्वपूर्ण हैं, जो बिना इन तंत्रों वाले वेरिएंट की तुलना में रिग्रेट को काफी कम करती हैं।

महत्व और दावे

यह पत्र दावा करता है कि COF उन लागत-संवेदनशील बैंडिट समस्याओं के लिए एक गुणात्मक रूप से बेहतर सैद्धांतिक ढांचा और अनुभवजन्य प्रदर्शन प्रदान करता है जहाँ गुणवत्ता बाधा अज्ञात सर्वोत्तम पुरस्कार के सापेक्ष होती है।

सैद्धांतिक प्रगति: यह कार्य पहला इंस्टेंस-डिपेंडेंट लोअर बाउंड प्रदान करता है जो कई आर्म्स की सैंपल कॉम्प्लेक्सिटी को संयुक्त रूप से चित्रित करता है, जो पिछले वर्स्ट-केस या सिंगल-आर्म विश्लेषणों की तुलना में MAB-CS की संरचनात्मक चुनौतियों की गहरी अंतर्दर्दष्टि प्रदान करता है।
एल्गोरिथम दक्षता: व्यवहार्यता परीक्षण करने से पहले समर्पित बेस्ट आर्म आइडेंटिफिकेशन (BAI) चरण को टालकर, COF अनावश्यक सैंपलिंग को कम करता है। "कंबाइनिंग सैंपल्स" की रणनीति एल्गोरिदम को पेयरवाइज तुलना विधियों की तुलना में गैर-व्यवहार्य आर्म्स को अधिक कुशलता से हटाने की अनुमति देती है।
व्यावहारिक प्रयोज्यता: लेखक LLM मॉडल रूटिंग जैसे वास्तविक दुनिया के परिदृश्यों में इसकी प्रासंगिकता पर प्रकाश डालते हैं, जहाँ विभिन्न मॉडलों की लागत और अज्ञात गुणवत्ता होती है, और सिस्टम को सर्वश्रेष्ठ उपलब्ध मॉडल के सापेक्ष प्रदर्शन फ्लोर के विरुद्ध लागत को संतुलित करना होता है। इसी तरह, यह फ्रेमवर्क विज्ञापन मोडैलिटी चयन और स्ट्रीमिंग सेवा कंटेंट डिलीवरी पर भी लागू होता है।

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