🤖 machine learning

Finite-Time Regret Analysis of Retry-Aware Bandits

यह शोधपत्र गॉसियन रिवॉर्ड्स वाले स्टोकेस्टिक बैंडिट्स में ReMax एल्गोरिदम के लिए पहले सबलीनियर रिग्रेट बाउंड को स्थापित करता है, जो इसके इष्टतम सैंपलिंग वितरण को स्पष्ट करता है और इसके अद्वितीय अंडरएस्टिमेशन प्रभाव की व्याख्या करता है जो थॉम्पसन सैंपलिंग की तुलना में अधिक एक्सप्लोइटेटिव व्यवहार की ओर ले जा सकता है।

मूल लेखक: Bingkui Tong, Junpei Komiyama, Soichiro Nishimori, Paavo Parmas

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

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

CC BY 4.0

मूल लेखक: Bingkui Tong, Junpei Komiyama, Soichiro Nishimori, Paavo Parmas

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

कल्पना कीजिए कि आप एक शेफ हैं जो एक नए व्यंजन के लिए एकदम सही रेसिपी खोजने की कोशिश कर रहे हैं। आपके पास सामग्रियों (हाथों/arms) से भरी एक पेंट्री है, लेकिन आप यह नहीं जानते कि वे कितनी अच्छी हैं। आपको उन्हें एक-एक करके चखना होगा ताकि आप सीख सकें।

अधिकांश कुकिंग एल्गोरिदम (जैसे प्रसिद्ध "थॉम्पसन सैंपलिंग") इसी तरह काम करते हैं: "मुझे लगता है कि यह सामग्री सबसे अच्छी है, इसलिए मैं इसका उपयोग करूँगा। लेकिन कभी-कभी, मैं बेतरतीब ढंग से किसी अजीब चीज़ को चुन लेता हूँ बस इस डर से कि कहीं मैं गलत न हूँ।" यह उपयोग करने (exploitation) और प्रयोग करने (exploration) के बीच का एक संतुलन है।

यह पेपर एक नए शेफ ReMax को पेश करता है। ReMax केवल सबसे अच्छी सामग्री चुनने के बारे में नहीं सोचता। इसके बजाय, ReMax सोचता है: "अगर मैं इस सामग्री को लगातार M बार आज़मा सकूँ, तो उन प्रयासों का सबसे अच्छा परिणाम कैसा होगा?"

इसे एक "रिट्राय-अवेयर" (retry-aware) उद्देश्य कहा जाता है। यह एक वीडियो गेम की तरह है जहाँ आपको एक लेवल पार करने के लिए k जीवन मिलते हैं; आपको केवल इस बात से फर्क नहीं पड़ता कि आप हर बार जीतते हैं या नहीं, आप केवल इस बात पर ध्यान देते हैं कि आप कम से कम एक बार जीत जाएँ।

यहाँ Re-Max द्वारा पाए गए निष्कर्षों का सरल उपमाओं के साथ विवरण दिया गया है:

1. मुख्य विचार: "बेस्ट ऑफ k" की मानसिकता

वास्तविक दुनिया में, हम अक्सर कई प्रयासों के सर्वोत्तम परिणाम की परवाह करते हैं। उदाहरण के लिए, जब कोई AI कोड लिखता है, तो वह 10 समाधान उत्पन्न कर सकता है, और हमें केवल इस बात से फर्क पड़ता है कि उनमें से एक भी काम कर जाए (pass@10)।

पुराना तरीका: औसत या सबसे संभावित विजेता पर ध्यान केंद्रित करना।
ReMax का तरीका: इस बात पर ध्यान केंद्रित करना कि यदि आपको M बार प्रयास करने का मौका मिले, तो अधिकतम संभव इनाम क्या होगा।

2. ReMax तय करता है कि क्या आज़माना है

पेपर सिद्ध करता है कि ReMax एक विशिष्ट नियम का पालन करता है जिसे "एक्सपेक्टेड-इम्प्रूवमेंट बैलेंस" (Expected-Improvement Balance) कहा जाता है।

उपमा: कल्पना कीजिए कि आप घोड़ों पर दांव लगा रहे हैं। एक मानक एल्गोरिदम उस घोड़े पर दांव लगाता है जिसके जीतने की संभावना सबसे अधिक होती है। ReMax उस घोड़े पर दाв लगाता है जो, यदि जीतता है, तो आपको आपके कुल स्कोर में सबसे बड़ा सरप्राइज बूस्ट देता है।
नुकसान: ReMax अनिश्चितता (variance) के प्रति बहुत संवेदनशील है। यदि किसी सामग्री का स्वाद अजीब और अप्रत्याशित है (उच्च विचलन/high variance), तो ReMax उसे पसंद करता है, क्योंकि यह अनिश्चितता इस संभावना को दर्शाती है कि वह एक "सुपर-स्टार" सामग्री हो सकती है जो दिन बचा ले।

3. अच्छी खबर: यह अक्सर बेहतर होता है

लेखकों ने सिम्युलेटेड समस्याओं और वास्तविक दुनिया के डेटा (जैसे मूवी रेटिंग और विज्ञापन क्लिक) पर ReMax का परीक्षण किया।

परिणाम: कई मामलों में, ReMax ने मानक तरीकों (थॉम्पसन सैंपलिंग और KL-UCB) की तुलना में बेहतर विकल्पों को तेज़ी से खोजा।
क्यों? क्योंकि ReMax "बेस्ट ऑफ k" विजेता खोजने के लिए अनिश्चित विकल्पों पर गणनात्मक जोखिम लेने के लिए तैयार रहता है। यह अपने अन्वेषण (exploration) में अधिक आक्रामक है।

4. बुरी खबर: "अंडरएस्टिमेशन ट्रैप" (कम आंकने का जाल)

पेपर ने ReMax में एक विशिष्ट कमजोरी की खोज की।

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

5. समाधान: "वैरिएंस इन्फ्लेशन" (विचलन मुद्रास्फीति)

लेखक इस जाल को ठीक करने के लिए एक सरल समाधान सुझाते हैं: अनिश्चितता को बढ़ा दें।

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

सारांश

यह क्या है? निर्णय लेने का एक नया तरीका जब AI को कई प्रयासों के सर्वोत्तम परिणाम की परवाह होती है, न कि केवल औसत की।
क्या काम करता है? यह मानक तरीकों को अक्सर मात देता है क्योंकि यह साहसी है और "छिपे हुए रत्नों" की तलाश करता है।
कहाँ विफल होता है? यह तब भ्रमित हो सकता है जब यह सोच ले कि सबसे अच्छा विकल्प खराब है, जिससे यह अन्य विकल्पों पर समय बर्बाद करने लगता है।
समाधान: पेपर इस भ्रम से उबरने में मदद करने के लिए एक गणितीय सुधार (वैरिएंस इन्फ्लेशन) का सुझाव देता है।

यह पेपर एक सैद्धांतिक प्रमाण है कि यह "रिट्राय-अवेयर" रणनीति अच्छी तरह काम करती है, यह भी समझाता है कि यह कभी-कभी क्यों फंस जाती है, और इसे ठीक करने का एक व्यावहारिक तरीका भी प्रदान करता है।

तकनीकी सारांश: रिट्राय-अवेयर बैंडिट्स का फाइनाइट-टाइम रिग्रेट विश्लेषण

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

यह शोध पत्र स्टोकेस्टिक मल्टी-आर्म्ड बैंडिट (MAB) समस्या को संबोधित करता है, जिसे पारंपरिक रूप से अन्वेषण (exploration) और दोहन (exploitation) के बीच संतुलन बनाकर संचयी पुरस्कार (cumulative reward) को अधिकतम करने के रूप में फ्रेम किया जाता है। हालाँकि, लेखक रिट्राय-अवेयर उद्देश्यों (retry-aware objectives) की ओर एक बदलाव का तर्क देते हैं, जहाँ प्रदर्शन का मूल्यांकन एकल ड्रॉ के पेऑफ के बजाय कई प्रयासों के सर्वोत्तम परिणाम (जैसे कि लार्ज लैंग्वेज मॉडल मूल्यांकन में pass@k या max@k) के आधार पर किया जाता है।

अध्ययन किया गया विशिष्ट एल्गोरिदम ReMax (रिट्राय-अवेयर मैक्सिमम) है, जिसे निशिमोरी एट अल. [2026] द्वारा प्रस्तुत किया गया है। बैंडिट सेटिंग में, ReMax $M$ वर्चुअल ड्रॉज़ पर $\pi_t$ के ऊपर एक सैंपलिंग डिस्ट्रीब्यूशन को चुनने का कार्य करता है जो पोस्टीरियर अपेक्षित अधिकतम पुरस्कार (posterior expected maximum reward) को अधिकतम करता है। जबकि पूर्व के कार्यों ने सुझाव दिया था कि ReMax प्रभावी ढंग से अन्वेषण करता है, इसके फाइनाइट-टाइम रिग्रेट गुण सैद्धांतिक रूप से स्पष्ट नहीं थे। यह शोध पत्र $M=2$ (पहला गैर-तुच्छ मामला) के साथ गॉसियन रिवॉर्ड सेटिंग पर ध्यान केंद्रित करता है ताकि एल्गोरिदम के व्यवहार को स्पष्ट किया जा सके और एक रिग्रेट बाउंड प्राप्त किया जा सके।

2. कार्यप्रणाली और सैद्धांतिक ढांचा (Methodology and Theoretical Framework)

2.1 ReMax उद्देश्य (The ReMax Objective)

एक आर्म वैल्यूज पर पोस्टीरियर डिस्ट्रीब्यूशन $\Pi_{t-1}$ दिए जाने पर, ReMax $\pi_t$ को चुनता है जो निम्नलिखित को अधिकतम करता है:
$J^{(M)}_{\text{ReMax}}(\pi; \Pi_{t-1}) := \mathbb{E}_{\theta \sim \Pi_{t-1}} \left[ \mathbb{E}_{A_{1:M} \sim \pi} \left[ \max_{m \in [M]} \theta_{A_m} \mid \theta \right] \right]$
जहाँ $A_{1:M}$ , $\pi$ से $M$ i.i.d. ड्रॉज़ हैं। यदि एक ही आर्म को कई बार खींचा जाता है, तो उसी पोस्टीरियर सैंपल का पुन: उपयोग किया जाता है।

2.2 एक्सपेक्टेड-इम्प्रूवमेंट (EI) बैलेंस कंडीशन

इस शोध पत्र का एक केंद्रीय संरचनात्मक अंतर्दृष्टि एक्सपेक्टेड-इम्प्रूवमेंट (EI) बैलेंस कंडीशन (प्रपोजिशन 1) है। इष्टतम सैंपलिंग डिस्ट्रीब्यूशन $\pi_t$ के लिए, सपोर्ट में किसी भी आर्म का "बेस्ट-ऑफ-टू" उद्देश्य में पोस्टीरियर-एवरेज मार्जिनल योगदान समान होता है। विशेष रूप से, सपोर्ट में किन्हीं भी दो आर्म्स $i, j$ के लिए:
$\bar{s}_{t,i} = \bar{s}_{t,j}$
जहाँ $\bar{s}_{t,i}$ अन्य $M-1$ ड्रॉज़ के अधिकतम के ऊपर आर्म $i$ का अपेक्षित सुधार (expected improvement) है। यह स्थिति ReMax को थॉम्पसन सैंपलिंग (TS) से अलग करती है; जबकि TS इस आधार पर रैंडमाइज करता है कि किसी आर्म के इष्टतम होने की संभावना कितनी है, ReMax अधिकतम रिवॉर्ड में संभावित सुधार के परिमाण (magnitude) को ध्यान में रखता है।

2.3 रिग्रेट विश्लेषण रणनीति (Regret Analysis Strategy)

लेखक $M=2$ के लिए गॉसियन रिवॉर्ड्स के लिए एक फाइनाइट-टाइम रिग्रेट बाउंड निकालते हैं। विश्लेषण रिग्रेट को दो अलग-अलग श्रेणियों में विभाजित करता है:

सैचुरेशन टर्म (Saturation Term): वे राउंड्स जहाँ इष्टतम आर्म को कम करके नहीं आंका गया है। विश्लेषण दिखाता है कि एक बार जब सब-ऑप्टिमल आर्म्स को पर्याप्त रूप से सैंपल कर लिया जाता है, तो ReMax सही ढंग से इष्टतम आर्म को प्राथमिकता देता है, जिससे मानक बैंडिट एल्गोरिदम के समान लॉगरिदमिक रिग्रेट ग्रोथ होती है।
अंडरएस्टिमेशन टर्म (Underestimation Term): वे राउंड्स जहाँ इष्टतम आर्म का एम्पिरिकल मीन उसके वास्तविक मीन से काफी कम है ( $\hat{\mu}_1(t) < \mu_1 - \epsilon$ )। इसे प्राथमिक तकनीकी बाधा (bottleneck) के रूप में पहचाना गया है।

प्रमुख तकनीकी चुनौती: शोध पत्र प्रदर्शित करता है कि ReMax, थॉम्पसन सैंपलिंग की तुलना में अधिक एक्सप्लोइटेटिव (exploitative) हो सकता है। यदि इष्टतम आर्म को कम करके आंका गया है, तो EI बैलेंस कंडीशन के कारण एल्गोरिदम इष्टतम आर्म पर वापस आने में देरी कर सकता है क्योंकि सब-ऑप्टिमल आर्म्स (जिनमें उच्च वेरिएंस या अनुकूल पेयरवाइज कंपैरिजन हो सकता है) "बेस्ट-ऑफ-टू" ऑब्जेक्टिव के लिए एक बड़ा अपेक्षित सुधार प्रदान करते हैं। इससे रिकवरी की अवधि लंबी हो जाती है।

3. प्रमुख योगदान (Key Contributions)

ऑप्टिमाइज़र का लक्षण वर्णन: यह शोध पत्र एक बेयसियन एक्सपेक्टेड-इम्प्रूवमेंट बैलेंस कंडीशन के माध्यम से ReMax ऑप्टिमाइज़र का पहला लक्षण वर्णन प्रदान करता है, जो स्पष्ट करता है कि एल्गोरिदम पोस्टीरियर अनसर्टेन्टी का उपयोग कैसे करता है।
प्रथम सबलिनियर रिग्रेट बाउंड: गॉसियन रिवॉर्ड्स के लिए $M=2$ के साथ, लेखक एक सबलिनियर रिग्रेट बाउंड सिद्ध करते हैं:
$\mathbb{E}[\text{Reg}(T)] \leq \sum_{i=2}^K O\left(\frac{\log T}{\Delta_i}\right) + \Delta_{\max} \tilde{O}\left(\frac{K^{1/3} T^{2/3}}{\Delta_{\min}^3}\right)$
पहला पद मानक सैचुरेशन व्यवहार के अनुरूप है, जबकि दूसरा पद ( $\tilde{O}(T^{2/3})$ ) अंडरएस्टिमेशन प्रभाव से उत्पन्न होता है।
अंडरएस्टिमेशन को बाधा के रूप में पहचानना: विश्लेषण स्पष्ट रूप से पहचानता है कि ReMax का आक्रामक शोषण (aggressive exploitation) इष्टतम आर्म के अंडरएस्टिमेशन से रिकवरी को धीमा कर सकता है, जो यह बताता है कि क्यों इसका रिग्रेट बाउंड UCB या TS जैसे एसिम्प्टोटिकली ऑप्टिमल एल्गोरिदम की तुलना में ढीला (looser) है।
शमन रणनीति (Mitigation Strategy): लेखक अंडरएस्टिमेशन प्रभाव को कम करने के लिए एक ह्यूरिस्टिक के रूप में पोस्टीरियर-वेरिएंस स्केलिंग (पोस्टीरियर वेरिएंस को $c \geq 1$ के कारक से बढ़ाना) प्रस्तावित करते हैं और उसका अनुभवजन्य सत्यापन करते हैं, जो यह सुझाव देता है कि यह रिकवरी समय को कम कर सकता है।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखक ReMax ( $M=2$ ) का सिंथेटिक इंस्टेंस और रियल-वर्ल्ड डेटासेट पर Thompson Sampling (TS) और KL-UCB के विरुद्ध मूल्यांकन करते हैं:

सिंथेटिक इंस्टेंस: 2, 3, और 10 आर्म्स वाले गॉसियन बैंडिट्स, जिनमें बेस्ट और सेकंड-बेस्ट आर्म्स के बीच छोटे गैप्स हैं ताकि अंडरएस्टिमेशन रिजीम का परीक्षण किया जा सके।
रियल-वर्ल्ड डेटासेट्स: ओपन बैंडिट डेटासेट (OBD, 80 आर्म्स) और मूवीलेंस 1M (31 आर्म्स) से प्राप्त उदाहरण।

निष्कर्ष:

प्रदर्शन: ReMax आमतौर पर संचयी रिग्रेट (cumulative regret) में TS और KL-UCB से बेहतर प्रदर्शन करता है, विशेष रूप से हल्के अंडरएस्टिमेशन वाले सिंथेटिक इंस्टेंस में।
अंडरएस्टिमेशन डायनेमिक्स: कई आर्म्स वाले परिदृश्यों (जैसे 10-आर्म सिंथेटिक, OBD) में, ReMax बेसलाइन्स की तुलना में इष्टतम आर्म के अधिक बार या लंबे अंडरएस्टिमेशन को प्रदर्शित करता है। यह इसके रिग्रेट एडवांटेज में कमी के साथ सह-संबंधित है।
वेरिएंस स्केलिंग: "डिज़ाइन किए गए फेल्योर मोड" (जहाँ अंडरएस्टिमेशन की संभावना अधिक है) में प्रयोग दिखाते हैं कि पोस्टीरियर वेरिएंस को बढ़ाने से संचयी अंडरएस्टिमेशन काफी कम हो जाता है और रिग्रेट में सुधार होता है, जो इसके सैद्धांतिक अंतर्ज्ञान का समर्थन करता है।
$M$ का प्रभाव: $M > 2$ के साथ प्रयोग (ग्रेडिएंट-आधारित एप्रोक्सिमेशन, ReMaxGrad का उपयोग करके) दिखाते हैं कि बड़ा $M$ अंडरएस्टिमेशन राउंड्स को कम करता है लेकिन आवश्यक रूप से संचयी रिग्रेट में सुधार नहीं करता है, जो यह सुझाव देता है कि $M$ एक यूनिवर्सल परफॉरमेंस बूस्टर के बजाय एक एक्सप्लोरेशन नॉब के रूप में कार्य करता है।

5. महत्व और दावे (Significance and Claims)

यह शोध पत्र दावा करता है कि यह बैंडिट सेटिंग में ReMax एल्गोरिदम के लिए पहला सैद्धांतिक रिग्रेट विश्लेषण प्रदान करता है। इसका महत्व निम्नलिखित में निहित है:

उद्देश्यों को जोड़ना: रिट्राय-अवेयर उद्देश्यों (जो LLM मूल्यांकन में सामान्य हैं) को औपचारिक बैंडिट थ्योरी से जोड़ना।
व्यवहार की व्याख्या करना: यह समझाने के लिए एक संरचनात्मक स्पष्टीकरण प्रदान करना कि ReMax, TS से अलग व्यवहार क्यों करता है, विशेष रूप से सुधार के परिमाण (magnitude of improvement) के शोषण और अंडरएस्टिमेशन के जोखिम के बीच ट्रेड-ऑफ को उजागर करना।
व्यावहारिक अंतर्दृष्टि: यह प्रदर्शित करना कि हालांकि ReMax अक्सर अनुभवजन्य रूप से श्रेष्ठ होता है, लेकिन इसके सैद्धांतिक गारंटी वर्तमान में अंडरएस्टिमेशन बॉटलनैक के कारण ढीली हैं। शोध पत्र विनम्रतापूर्वक निष्कर्ष निकालता है कि रिग्रेट बाउंड को परिष्कृत करना (संभावित रूप से वेरिएंस इन्फ्लेशन विश्लेषण के माध्यम से) भविष्य के कार्य के लिए एक आवश्यक दिशा है ताकि एसिम्प्टोटिकली ऑप्टिमल एल्गोरिदम के साथ अंतर को पाटा जा सके।

लेखक इस बात पर जोर देते हैं कि उनका रिग्रेट बाउंड संभवतः टाइट (tight) नहीं है (विशेष रूप से $T^{2/3}$ पद) और उनके अनुभवजन्य साक्ष्य बताते हैं कि अंडरएस्टिमेशन रिग्रेट बहुत धीरे बढ़ता है, जिसका अर्थ है कि सैद्धांतिक बाउंड रूढ़िवादी (conservative) हो सकता है।