💻 computer science

Analysis of Search Heuristics in the Multi-Armed Bandit Setting

यह शोध पत्र ड्यूलिंग बैंडिट सेटिंग में सर्च ह्यूरिस्टिक्स का विश्लेषण करता है, जो यह प्रदर्शित करता है कि (1+1) इवोल्यूशनरी एल्गोरिदम, मैक्स-मिन एंट सिस्टम-आधारित ईडीए की तुलना में कोंडोर्सेट विजेता को पहचानने में संघर्ष करता है, और साथ ही ईए के प्रदर्शन को सुधारने के लिए बार-बार होने वाले द्वंद्वों (रिपीटेड ड्यूल्स) को एक प्रभावी उपचार के रूप में प्रस्तावित करता है।

मूल लेखक: Jasmin Brandt, Barbara Hammer, Timo Kötzing, Jurek Sander

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

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

CC BY 4.0

मूल लेखक: Jasmin Brandt, Barbara Hammer, Timo Kötzing, Jurek Sander

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

कल्पना कीजिए कि आप एक कैसीनो में हैं जहाँ आपके पास n अलग-अलग स्लॉट मशीनें (हम इन्हें "आर्म्स" कहते हैं) हैं। आप नहीं जानते कि कौन सी मशीन सबसे ज्यादा पैसा देती है। आपका लक्ष्य जल्द से जल्द सबसे अच्छी मशीन को खोजना है।

हालाँकि, यह शोध पत्र एक नया मोड़ जोड़ता है: आप केवल एक लीवर नहीं खींच सकते और एक नंबर प्राप्त नहीं कर सकते। इसके बजाय, आपको दो मशीनों के बीच "रॉक, पेपर, सिज़र्स" का खेल खेलना होगा।

आप मशीन A और मशीन B चुनते हैं।
वे एक मैच खेलते हैं।
एक जीतता है, एक हारता है।
कभी-कभी बेहतर मशीन हर बार जीतती है (डिटरमिनिस्टिक/निश्चित)।
कभी-कभी बेहतर मशीन 90% बार जीतती है, लेकिन कमजोर मशीन 10% बार भाग्यशाली हो जाती है (स्टोकेस्टिक/शोर वाला/नॉइजी)।

यह शोध पत्र पूछता है: विभिन्न कंप्यूटर खोज रणनीतियाँ (एल्गोरिदम) इस खेल को कैसे संभालती हैं? विशेष रूप से, वे इवोल्यूशनरी एल्गोरिदम (जो प्रकृति के विकास की नकल करते हैं) की तुलना एंट कॉलोनी एल्गोरिदम (जो चींटियों द्वारा भोजन खोजने की नकल करते हैं) से करते हैं।

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

1. "रॉक, पेपर, सिज़र्स" का चैंपियन

इस कैसीनो में, एक मशीन है जो कॉन्डोरसेट विनर (Condorcet Winner) है। यह "किंग ऑफ द हिल" है। यदि आप इस मशीन को किसी भी अन्य मशीन के खिलाफ खड़ा करते हैं, तो यह 50% से अधिक समय जीतती है। लक्ष्य इसी किंग को खोजना है।

2. "सर्वाइवल ऑफ द फिटेस्ट" का संघर्ष (इवोल्यूशनरी एल्गोरिदम)

लेखकों ने एक सरल इवोल्यूशनरी एल्गोरिदम (जिसे (1+1) EA कहा जाता है) का परीक्षण किया।

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

3. "चींटियों" का समाधान (एस्टिमेशन ऑफ डिस्ट्रीब्यूशन एल्गोरिदम)

इसके बाद, उन्होंने एंट कॉलोनी ऑप्टिमाइजेशन (विशेष रूप से MMAS-ib) पर आधारित एक एल्गोरिदम का परीक्षण किया।

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

4. "बेस्ट ऑफ थ्री" फिक्स (बूस्टिंग)

लेखकों को एहसास हुआ कि इवोल्यूशनरी एल्गोरिदम इसलिए विफल हो रहा था क्योंकि यह एकल भाग्यशाली जीत के प्रति बहुत संवेदनशील था। इसलिए, उन्होंने एक ट्रिक आजमाई: "बेस्ट ऑफ थ्री" सीरीज।

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

सारांश में मुख्य बात

समस्या: शोर वाले वातावरण में (जहाँ भाग्य की भूमिका होती है), सरल "हारने वाले को बदलें" वाली रणनीतियाँ (जैसे बुनियादी इवevolutionary एल्गोरिदम) आसानी से बुरे भाग्य से ठगी जा सकती हैं। वे सच को बहुत जल्दी भूल जाते हैं।
समाधान 1 (स्मृति): वे एल्गोरिदम जो समय के साथ एक "प्रतिष्ठा" या "गंध" बनाते हैं (जैसे चींटियाँ), शोर को छानने और वास्तविक सर्वश्रेष्ठ विकल्प को खोजने में बहुत बेहतर होते हैं।
समाधान 2 (सत्यापन): यदि आपको सरल "हारने वाले को बदलें" रणनीति का ही उपयोग करना है, तो आप इसे एक सीरीज के माध्यम से मैचों (जैसे "बेस्ट ऑफ 3" या "बेस्ट ऑफ 5") में खुद को साबित करने के लिए कहकर ठीक कर सकते हैं।

संक्षेप में: यदि आप भाग्य और शोर से भरी दुनिया में सबसे अच्छा विकल्प खोजना चाहते हैं, तो केवल पिछली घटना पर प्रतिक्रिया न दें। एक चलता हुआ स्कोर रखें (चींटियाँ) या प्रमाणों की एक श्रृंखला की मांग करें (बेस्ट ऑफ 3) ताकि आप किसी भाग्यशाली संयोग से धोखा न खाएं।

यहाँ ब्रांड्ट एट अल. के शोध पत्र "Analysis of Search Heuristics in the Multi-Armed Bandit Setting" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

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

सेटिंग: लेखक ड्यूलिंग बैंडिट (Dueling Bandit) वेरिएंट पर ध्यान केंद्रित करते हैं। संख्यात्मक रिवॉर्ड प्राप्त करने के बजाय, एल्गोरिदम "आर्म्स" (सर्च पॉइंट्स/इंडिविजुअल्स) के बीच युग्मवार तुलना (duels) के आधार पर फीडबैक प्राप्त करता है।
उद्देश्य: लक्ष्य कॉन्डोरसेट विजेता (Condorcet winner) की पहचान करना है—एक ऐसा आर्म जो अन्य प्रत्येक आर्म को $1/2$ से अधिक प्रायिकता के साथ हरा देता है।
चुनौती: यह शोध पत्र विशेष रूप से उस स्टोकेस्टिक (stochastic) सेटिंग का विश्लेषण करता है जहाँ ड्यूल के परिणाम संभाव्य (probabilistic) होते हैं। मुख्य प्रश्न यह है: मानक सर्च ह्यूरिस्टिक्स (जैसे कि (1+1) EA) अपनी स्टेशनरी डिस्ट्रीब्यूशन में कॉन्डोरसेट विजेता की ओर कितनी अच्छी तरह अभिसरित (converge) होते हैं, यदि उनकी तुलना विशिष्ट एल्गोरिदम या अन्य ह्यूरिस्टिक्स (जैसे EDAs) से की जाए?

2. कार्यप्रणाली (Methodology)

लेखक मार्कोव चेन थ्योरी (Markov Chain theory), ड्रिफ्ट एनालिसिस (Drift Analysis), और कपलिंग तकनीकों (Coupling techniques) का उपयोग करके कठोर सैद्धांतिक विश्लेषण करते हैं।

मार्कोव चेन मॉडलिंग:
- (1+1) EA के लिए: स्टेट स्पेस को वर्तमान इंकंबेंट (अब तक पाया गया सर्वश्रेष्ठ समाधान) द्वारा परिभाषित किया जाता है। ट्रांजिशन प्रोबेबिलिटीज़ इस आधार पर निकाली जाती हैं कि इंकंबेंट की एक रैंडमली सैंपल किए गए चैलेंजर के विरुद्ध जीतने की प्रायिकता क्या है।
- लेखक इस चेन के स्टेशनरी डिस्ट्रीब्यूशन ( $\pi$ ) का विश्लेषण करते हैं ताकि यह निर्धारित किया जा सके कि एल्गोरिदम लंबे समय में कॉन्डोरसेट विजेता को धारण करने की कितनी संभावना रखता है।
- मिक्सिंग टाइम (Mixing Time): वे इस स्टेशनरी डिस्ट्रीब्यूशन तक पहुँचने की गति निर्धारित करने के लिए मिक्सिंग टाइम ( $\tau(\epsilon)$ ) की गणना करते हैं।
प्लैकेट-लूस मॉडल (Plackett-Luce Model):
- ड्यूल्स के लिए एक संरचित संभाव्य मॉडल प्रदान करने के लिए, लेखक प्लैकेट-लूस मॉडल का उपयोग करते हैं, जहाँ किसी आर्म के जीतने की प्रायिकता उसके अंतर्निहित उपयोगिता (utility) के समानुपाती होती है।
- वे "बूस्टिंग" (Boosting) की जांच करते हैं: एक तकनीक जहाँ एक ही इटरेशन में एक ही जोड़ी के बीच कई ड्यूल किए जाते हैं, और बहुमत विजेता को चुना जाता है। इसका उद्देश्य कॉन्डोरसेट विजेता के सिग्नल को बढ़ाना है।
EDA विश्लेषण (MMAS-ib):
- लेखक मैक्स-मिन एंट सिस्टम विद इटरेशन-बेस्ट अपडेट (MMAS-ib) पर आधारित एक विशिष्ट एस्टीमेशन ऑफ डिस्ट्रीब्यूशन एल्गोरिदम का विश्लेषण करते हैं।
- यह एल्गोरिदम प्रत्येक आर्म के लिए मार्जिनल प्रोबेबिलिटीज़ (फेरोमोन्स) का एक वेक्टर बनाए रखता है। यह इन प्रोबेबिलिटीज़ के आधार पर दो आर्म्स को सैंपल करता है, एक ड्यूल करता है, और प्रोबेबिलिटीज़ को अपडेट करता है (विजेता के सुदृढ़ीकरण और इवैपोरेशन के माध्यम से)।
- ड्रिफ्ट एनालिसिस: वे फेरोमोन के कॉन्डोरसेट विजेता के उच्च मान की ओर अभिसरण के अपेक्षित समय को बाउंड करने के लिए एडिटिव और मल्टीप्लिकेटिव ड्रिफ्ट थ्योरम्स का उपयोग करते हैं।

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

A. (1+1) EA की सीमाएँ

यह शोध पत्र प्रदर्शित करता है कि मानक (1+1) EA स्टोकेस्टिक सेटिंग में कॉन्डोरसेट विजेता की पहचान करने में अक्षम (inefficient) है, भले ही विजेता अन्यों से काफी बेहतर हो।

स्टेशनरी डिस्ट्रीब्यूशन: यदि कॉन्डोरसेट विजेता किसी भी अन्य आर्म को $1-p$ की प्रायिकता से हराता है, तो (1+1) EA अपने स्टेशनरी डिस्ट्रीब्यूशन में कॉन्डोरसेट विजेता को लगभग $O(1/n)$ की प्रायिकता के साथ चुनता है यदि $p = \Omega(1/n)$ हो।
निष्कर्ष: (1+1) EA तब तक अनुकूलतम समाधान को अलग नहीं कर पाता जब तक कि जीतने की प्रायिकता अत्यंत उच्च (अर्थात $1 - o(1/n)$ ) न हो। यह पिछले डेटा को "भूल" जाता है क्योंकि यह ऐतिहासिक प्रदर्शन डेटा को स्टोर नहीं करता है।

B. बार-बार ड्यूल के माध्यम से बूस्टिंग (Boosting via Repeated Duels)

(1+1) EA की कमजोरी को दूर करने के लिए, लेखक एक प्रति इटरेशन में $x$ बार-बार ड्यूल करने और बहुमत विजेता चुनने का प्रस्ताव देते हैं।

परिणाम: प्रति इटरेशन में ड्यूल की संख्या बढ़ाकर $x = \Theta((1/\delta)^2 \ln n)$ (जहाँ $\delta$ 0.5 से बढ़त है) करने से, कॉन्डोरसेट विजेता का स्टेशनरी डिस्ट्रीब्यूशन $1 - \Theta(1/n)$ तक बढ़ाया जा सकता है।
ट्रेड-ऑफ: यह सटीकता में सुधार करता है लेकिन ड्यूल की संख्या के साथ प्रति इटरेशन कम्प्यूटेशनल लागत को रैखिक रूप से बढ़ा देता है।

C. EDAs की श्रेष्ठता (MMAS-ib)

यह शोध पत्र दिखाता है कि एक सरल EDA (MMAS-ib) बिना बार-बार ड्यूल किए (repeated duels) (1+1) EA की तुलना में काफी बेहतर प्रदर्शन करता है।

अभिसरण (Convergence): यदि कॉन्डोरसेट विजेता $1-p$ की प्रायिकता के साथ दूसरों को हराता है, तो EDA में कॉन्डोरसेट विजेता की मार्जिनल प्रोबेबिलिटी (फेरोमोन) $1 - \Theta(p)$ की ओर अभिसरित होती है।
अपेक्षित समय (Expected Time): उच्च मार्जिनल प्रोबेबिलिटी तक पहुँचने का अपेक्षित समय $O(\frac{1}{\tau_{min}\rho} + \frac{\log(1/p)}{\rho})$ है।
महत्व: EDAs की संचयी प्रकृति (cumulative nature) उन्हें कॉन्डोरसेट विजेता की श्रेष्ठता के साक्ष्य को "याद रखने" और संचित करने की अनुमति देती है, जिससे वे मेमोरीलेस (1+1) EA की तुलना में अनुकूलतम आर्म पर बहुत सटीक ध्यान केंद्रित कर पाते हैं।

4. महत्व और निहितार्थ

सैद्धांतिक अंतर्दृष्टि: यह शोध पत्र एक सैद्धांतिक स्पष्टीकरण प्रदान करता है कि क्यों कुछ इवोल्यूशनरी एल्गोरिदम शोर वाले (noisy), प्राथमिकता-आधारित वातावरण में संघर्ष करते हैं। यह उजागर करता है कि मेमोरीलेस ह्यूरिस्टिक्स (जैसे मानक (1+1) EA) उन स्टोकेस्टिक बैंडिट समस्याओं के लिए अनुपयुक्त हैं जहाँ सिग्नल कमजोर होता है, जबकि डिस्ट्रीब्यूशन-आधारित ह्यूरिस्टिक्स (जैसे EDAs) जानकारी को एकत्रित करके उत्कृष्ट प्रदर्शन करते हैं।
एल्गोरिदम डिज़ाइन: यह सुझाव देता है कि ड्यूलिंग बैंडिट के रूप में मॉडल किए गए समस्याओं के लिए, साक्ष्य एकत्र करने वाले तंत्र (जैसे ACO में फेरोमोन्स या EDAs में प्रोबेबिलिटी वेक्टर्स) को शामिल करना मजबूत प्रदर्शन के लिए महत्वपूर्ण है।
व्यावहारिक उपचार: "बूस्टिंग" रणनीति (बार-बार ड्यूल) सरल एल्गोरिदम के लिए एक व्यावहारिक, हालांकि महंगी, मरम्मत प्रदान करती है, जबकि MMAS-ib का विश्लेषण बताता है कि EDAs का उपयोग करना एक अधिक कुशल संरचनात्मक समाधान है।
भावी कार्य: लेखक नोट करते हैं कि उनका मॉडल एक अनस्ट्रक्चर्ड सर्च स्पेस को मानता है। वे प्रस्तावित करते हैं कि भविष्य के कार्यों में वास्तविक दुनिया की अनुकूलन समस्याओं को बेहतर ढंग से दर्शाने के लिए सर्च स्पेस की संरचना (जैसे कॉम्बिनेटरियल बैंडिट्स) को शामिल किया जाना चाहिए।

सारांश तालिका (Summary Table)

विशेषता	(1+1) EA	(1+1) EA + Boosting	MMAS-ib (EDA)
तंत्र (Mechanism)	मेमोरीलेस, सिंगल ड्यूल	मेमोरीलेस, मल्टीपल ड्यूल	संचयी (Cumulative), फेरोमोन अपडेट
CW की स्टेशनरी प्रोबेबिलिटी	कम ( $O(1/n)$ ) जब तक सिग्नल एकदम सटीक न हो	उच्च ( $1 - \Theta(1/n)$ ) पर्याप्त ड्यूल्स के साथ	उच्च ( $1 - \Theta(p)$ )
आवश्यकता	$M(i^*, i) \approx 1$	$O((1/\delta)^2 \ln n)$ ड्यूल्स/इटरेशन	$M(i^*, i) > 0.5$
दक्षता (Efficiency)	स्टोकेस्टिक सिग्नल के लिए खराब	अच्छी, लेकिन उच्च क्वेरी लागत	उत्कृष्ट, कम क्वेरी लागत