🤖 machine learning

An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

यह शोध पत्र एक ओरकल-कुशल (oracle-efficient), निकट-इष्टतम (near-optimal) एल्गोरिदम प्रस्तुत करता है जो संदर्भ वितरण (context distribution) के ज्ञान की आवश्यकता के बिना, स्टोकेस्टिक एक्शन सेट्स वाले एडवरसेरियल लीनियर कॉन्टेक्स्टुअल बैंडिट्स के लिए $\mathrm{poly}(d)\sqrt{T}$ रिग्रेट को बहुपद समय (polynomial time) में प्राप्त करके एक खुले प्रश्न को हल करता है।

मूल लेखक: Tim van Erven, Jack Mayo, Julia Olkhovskaya, Chen-Yu Wei

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

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

CC BY 4.0

मूल लेखक: Tim van Erven, Jack Mayo, Julia Olkhovskaya, Chen-Yu Wei

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

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

यहाँ इस शोध पत्र की समस्या, समाधान और परिणामों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है।

समस्या: चालाक फूड ट्रक

आप शेफ हैं (learner)। हर दिन (round), ग्राहकों का एक नया समूह आता है जिसके पास व्यंजनों का एक विशिष्ट मेनू होता है जिन्हें वे खरीदने के लिए तैयार होते हैं (action set)।

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

पुराना तरीका:
पिछले शेफों (एल्गोरिदम) को दो बड़ी समस्याओं का सामना करना पड़ा:

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

समाधान: "अनुवाद" वाली ट्रिक (The "Translation" Trick)

लेखकों (वैन एरवेन, मेयो, ओल्खोव्स्काया और वेई) ने खाना पकाने का एक नया तरीका ईजाद किया जिसके लिए क्रिस्टल बॉल की आवश्यकता नहीं है और जो विशाल मेनू के लिए पर्याप्त तेज़ है।

उन्होंने एक चतुर रिडक्शन (अनुवाद ट्रिक) का उपयोग किया। सीधे "बदलते मेनू" वाली कठिन समस्या को हल करने के बजाय, उन्होंने इसे एक सरल, निश्चित समस्या में अनुवादित कर दिया: "मिसस्पेसिफाइड" (Missspecified) लीनियर बैंडिट।

यह अनुवाद कैसे काम करता है, यहाँ बताया गया है:

"औसत" मेनू: चूंकि उन्हें भविष्य के मेनू का ज्ञान नहीं है, इसलिए वे अब तक देखे गए मेनू के आधार पर एक "नकली" मेनू बनाते हैं। इसे पिछले कुछ दिनों की सामग्रियों को औसत निकालकर बनाया गया एक "मिश्रित" मेनू समझें।
अनुवाद अंतराल (Translation Gap): क्योंकि यह नकली मेनू एक अनुमान है, इसलिए यह पूरी तरह से सटीक नहीं है। यह थोड़ा "मिसस्पेसिफाइड" है। यह एक ऐसे शहर में नेविगेट करने जैसा है जहाँ आपका नक्शा 95% सही है, लेकिन कुछ सड़कें गलत जगह पर खींची गई हैं।
मजबूत शेफ (Robust Chef): उन्होंने एक नए प्रकार का शेफ (एक एल्गोरिदम) बनाया जो मिसस्पेसिफिकेशन के प्रति मजबूत (robust) है। यह शेफ जानता है कि नक्शा थोड़ा गलत हो सकता है। भ्रमित होने या हार मानने के बजाय, यह शेफ मानचित्र की त्रुटियों की भरपाई करने के लिए थोड़ा "एक्सप्लोरेशन" (नई चीजें आज़माना) जोड़ता है।

जादुई उपकरण: द ऑरेकल (The Oracle)
इसे तेज़ बनाने के लिए, वे एक "लीनियर ऑप्टिमाइज़ेशन ऑरेकल" पर भरोसा करते हैं।

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

परिणाम: उन्होंने क्या हासिल किया?

1. गति और दक्षता (The "Poly(d)" Breakthrough)

पुराना तरीका: यदि व्यंजनों की संख्या ( $K$ ) बहुत बड़ी (जैसे $2^{100}$ ) थी, तो पुराने एल्गोरिदम $2^{100}$ स्टेप्स लेंगे। वे "एक्सपोनेंशियल टाइम" में फंस जाते थे।
नया तरीका: नए एल्गोरिदम की गति केवल सामग्रियों की जटिलता ( $d$ ) और दिनों की संख्या ( $T$ ) पर निर्भर करती है, न कि कुल व्यंजनों की संख्या पर। यह "पॉलीनोमियल टाइम" में चलता है।
महत्व: यह पहली बार है जब किसी ने इस विशिष्ट "बदलते मेनू" वाली समस्या को कुशलतापूर्वक हल किया है जब मेनू विकल्प कॉम्बिनेटोरियल (जैसे विशाल नेटवर्क में सबसे छोटा रास्ता खोजना या लोगों को नौकरियों से मिलाना) हों।

2. स्कोर (Regret)
इस खेल में, "रिग्रेट" (Regret) वह अंतर है जो आपने परफेक्ट शेफ की तुलना में अधिक खराब प्रदर्शन किया है।

सिमुलेटर के बिना: यदि आपको शुद्ध अनुभव से सीखना पड़ता है (कोई क्रिस्टल बॉल या सिम्युलेटर नहीं), तो उन्होंने लगभग $\sqrt{T}$ (समय का वर्गमूल) का स्कोर प्राप्त किया। इसे "नियर-ऑप्टिमल" माना जाता है।
सिमुलेटर के साथ: यदि आपके पास एक सिम्युलेटर है (एक ऐसा टूल जो आपको मुफ्त में नकली मेनू पर अभ्यास करने देता है), तो उन्होंने स्कोर को और भी बेहतर बना दिया, जिससे यह नुकसान ( $L^*$ ) की गंभीरता पर निर्भर करता है। यदि नुकसान कम हैं, तो स्कोर और भी बेहतर होता है।

बड़ी तस्वीर (The Big Picture)

यह शोध पत्र एक लंबे समय से खुले प्रश्न को हल करता है: क्या हम बिना भविष्य जाने, जटिल और बदलते मेनू को कुशलतापूर्वक संभाल सकते हैं?

पहले: नहीं। या तो आपको भविष्य के वितरण (distribution) का पता होना चाहिए था, या आपको उत्तर की गणना करने के लिए अनंत काल तक प्रतीक्षा करनी पड़ती थी।
अब: हाँ। समस्या को एक "रोबस्ट" संस्करण में अनुवादित करके और भारी काम को संभालने के लिए एक "जादुई सहायक" (oracle) का उपयोग करके, उन्होंने एक ऐसा एल्गोरिदम बनाया जो तेज़ भी है और स्मार्ट भी।

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

तकनीकी सारांश: रिडक्शन के माध्यम से एक उन्नत एडवर्सरियल लीनियर कॉन्टेक्स्टुअल बैंडिट एल्गोरिदम

समस्या की परिभाषा

यह शोध पत्र एडवर्सरियल लीनियर कॉन्टेक्स्टुअल बैंडिट (adversarial linear contextual bandit) समस्या को संबोधित करता है। इस सेटिंग में, एक ओब्लिवियस एडवर्सरी (oblivious adversary) इंटरैक्शन शुरू होने से पहले ही छिपे हुए लॉस वेक्टर्स $\theta_t \in \mathbb{R}^d$ का एक अनुक्रम चुनता है। प्रत्येक दौर $t$ में, एक निश्चित लेकिन अज्ञात वितरण $\mathcal{D}$ से एक्शन सेट $A_t \subset \mathbb{R}^d$ i.i.d. रूप से खींचा जाता है और लर्नर को दिखाया जाता है। लर्नर को एक एक्शन $a_t \in A_t$ चुनना होता है और वह लॉस $\ell_t$ का सामना करता है जिसका अपेक्षित मान $\mathbb{E}[\ell_t] = a_t^\top \theta_t$ है। लक्ष्य सर्वोत्तम स्थिर नीति (fixed policy) $\pi$ के विरुद्ध रिग्रेट (regret) को कम करना है, जहाँ एक नीति किसी भी देखे गए एक्शन सेट $A$ को उसके कॉनवेक्स हल (convex hull) $\text{conv}(A)$ के भीतर एक बिंदु पर मैप करती है।

यह सेटिंग शास्त्रीय लीनियर बैंडिट्स का सामान्यीकरण करती है क्योंकि इसमें एक्शन सेट्स (कॉन्टेक्स्ट्स) समय के साथ स्टोकेस्टिक रूप से बदल सकते हैं, जबकि लॉस एडवर्सरियल रहते हैं। एक महत्वपूर्ण चुनौती यह है कि वितरण $\mathcal{D}$ अज्ञात है, और लर्नर के पास ऐसा सिम्युलेटर नहीं है जो $\mathcal{D}$ से मुफ्त सैंपल जनरेट कर सके। इसके अलावा, संभावित एक्शन्स की संख्या $K$ आयाम $d$ के संदर्भ में घातीय (exponentially) रूप से बड़ी हो सकती है (जैसे शॉर्टेस्ट पाथ जैसी कॉम्बिनेटोरियल समस्याओं में), जिससे $K$ के बहुपद (polynomial) जटिलता वाले एल्गोरिदम अव्यवहारिक हो जाते हैं।

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

मुख्य योगदान एक कंप्यूटेशनल रूप से कुशल रिडक्शन (computationally efficient reduction) है जो एडवर्सरियल लीनियर कॉन्टेक्स्टुअल बैंडिट समस्या को एक निश्चित एक्शन सेट वाली मिसस्पेफिकेशन-रोबस्ट एडवर्सरियल लीनियर बैंडिट समस्या में परिवर्तित करता है।

फिक्स्ड एक्शन सेट्स में रिडक्शन:
लेखक एक मैपिंग $\Psi(\pi) = \mathbb{E}_{A \sim \mathcal{D}}[\pi(A)]$ को परिभाषित करते हैं, जो एक नीति $\pi$ को उसके माध्य एक्शन (mean action) पर मैप करती है। चूंकि $\mathcal{D}$ अज्ञात है, इसलिए माध्य एक्शन्स के वास्तविक सेट $\Omega = \{\Psi(\pi) \mid \pi \in \Pi\}$ तक सीधे पहुँच प्राप्त नहीं की जा सकती। इसके बजाय, एल्गोरिदम $N$ i.i.d. सैंपल का उपयोग करके एक अनुभवजन्य सन्निकटन (empirical approximation) $\hat{\Omega}$ का निर्माण करता है।
- $\hat{\Omega}$ को सैंपल किए गए एक्शन सेट्स के कॉनवेक्स हल के मिंकोव्स्की सम (Minkowski sum) के रूप में परिभाषित किया गया है: $\hat{\Omega} = \frac{1}{N} \sum_{i=1}^N \text{conv}(A_i)$ ।
- यह रिडक्शन इस तथ्य पर आधारित है कि लीनियर क्लासिफायर पॉलिसियों के लिए, वास्तविक वितरण पर अपेक्षित लॉस और अनुभवजन्य वितरण के बीच का अंतर छोटा होता है (यूनिफॉर्म कन्वर्जेंस), बशर्ते $N$ पर्याप्त बड़ा हो।
मिसस्पेफिकेशन के माध्यम से विसंगति (Discrepancy) को संभालना:
चूंकि लर्नर $\Omega$ के बजाय $\hat{\Omega}$ पर कार्य करता है, इसलिए अंडरलाइंग लीनियर बैंडिट एल्गोरिदम द्वारा प्राप्त फीडबैक "मिसस्पेफाइड" होता है। विशेष रूप से, लीनियर बैंडिट एल्गोरिदम द्वारा देखा गया अपेक्षित लॉस, वास्तविक अपेक्षित लॉस से एक सीमित त्रुटि पद $\epsilon$ द्वारा भिन्न होता है।
- लेखक एक $\alpha$ -मिसस्पेफिकेशन-रोबस्ट एडवर्सरियल लीनियर बैंडिट एल्गोरिदम को एक ब्लैक बॉक्स के रूप में उपयोग करते हैं। यह एल्गोरिदम तब भी कम रिग्रेट की गारंटी देता है जब फीडबैक $|\mathbb{E}[c_t] - \langle y_t, \theta_t \rangle| \le \epsilon$ को संतुष्ट करता है।
- लीनियर बैंडिट एल्गोरिदम द्वारा सुझाए गए बिंदु $y_t \in \hat{\Omega}$ को निष्पादित करने के लिए, लर्नर $\hat{\Omega}$ की सीमा (boundary) पर स्थित बिंदुओं के कॉनवेक्स कॉम्बिनेशन के रूप में $y_t$ को व्यक्त करने के लिए एक फ्रैंक-वोल्फ-आधारित अपघटन (Frank-Wolfe-based decomposition) (एल्गोरिदम 2) का उपयोग करता है। ये बाउंड्री पॉइंट्स लीनियर क्लासिफायर पॉलिसियों $\pi_\phi$ के अनुरूप होते हैं, जिन्हें व्यक्तिगत एक्शन सेट्स $A_t$ के लिए एक लीनियर ऑप्टिमाइजेशन ऑरेकल का उपयोग करके निष्पादित किया जा सकता है।
एल्गोरिथमिक घटक:
- एल्गोरिदम 1: मुख्य फ्रेमवर्क जो वातावरण के साथ इंटरैक्ट करता है, लीनियर बैंडिट के सुझाव को लीनियर पॉलिसियों के मिश्रण में विघटित करता है, और परिणामी लॉस को लीनियर बैंडिट एल्गोरिदम को वापस फीड करता है।
- एल्गोरिदम 3 (मिसस्पेफिकेशन-रोबस्ट कंटीन्यूअस एक्सपोनेंशियल वेट्स): रोबस्ट लीनियर बैंडिट एल्गोरिदम का एक विशिष्ट इंस्टेंशिएशन। यह लॉस एस्टिमेटर में एक "बोनस टर्म" $b_t$ जोड़कर क्लिप्ड कंटीन्यूअस एक्सपोनेंशियल वेट्स विधि (Ito et al., 2020) को अनुकूलित करता है। यह बोनस अन्वेषण (exploration) को प्रोत्साहित करता है और मिसस्पेफिकेशन के कारण होने वाले रिग्रेट ओवरहेड को संतुलित करता है।
- डबलिंग ट्रिक (Doubling Trick): अज्ञात इष्टतम सैंपल आकार $N$ को संभालने के लिए, एल्गोरिदम एक डबलिंग ट्रिक का उपयोग करता है, जो $2, 4, 8, \dots$ के एपोक्स (epochs) पर प्रक्रिया को पुनरारंभ करता है और $\hat{\Omega}$ को परिष्कृत करने के लिए सभी संचित कॉन्टेक्स्ट सैंपल्स का उपयोग करता है।

मुख्य योगदान

ऑरेकल-एफिशिएंट एल्गोरिदम: यह शोध पत्र एक ऐसा एल्गोरिदम प्रस्तुत करता है जो एडवर्सरियल लीनियर कॉन्टेक्स्टुअल बैंडिट्स के लिए पहला है, जिसकी कम्प्यूटेशनल जटिलता में एक्शन की संख्या $K$ पर निर्भरता नहीं है। इसे केवल प्रत्येक दौर में व्यक्तिगत एक्शन सेट्स के लिए एक लीनियर ऑप्टिमाइजेशन ऑरेकल की आवश्यकता होती है।
कॉम्बिनेटोरियल अनुप्रयोग: यह विधि पहली है जो स्टोकेस्टिक एक्शन सेट्स और एडवर्सरियल लॉस के साथ कॉम्बिनेटोरियल बैंडिट्स के लिए बहुपद समय (polynomial time) में $\text{poly}(d)\sqrt{T}$ रिग्रेट प्राप्त करती है। पिछले एल्गोरिदम या तो सेमी-बैंडिट फीडबैक की आवश्यकता रखते थे या उनकी कम्प्यूटेशनल जटिलता $K$ के साथ बहुपद रूप से बढ़ती थी (जो कई समस्याओं के लिए $d$ के संदर्भ में घातीय है)।
नया रिडक्शन: यह कार्य एडवर्सरियल लीनियर कॉन्टेक्स्टुअल बैंडिट्स से मिसस्पेफिकेशन-रोबस्ट लीनियर बैंडिट्स में एक बहुपद-समय रिडक्शन स्थापित करता है। पिछले रिडक्शन (जैसे Hanna et al., 2023) के विपरीत, जो स्टोकेस्टिक सेटिंग्स पर केंद्रित थे या जिनमें बहुपद-समय कार्यान्वयन की कमी थी, यह रिडक्शन एडवर्सरियल लॉस के तहत काम करता है और कंप्यूटेशनल रूप से कुशल है।

परिणाम

एल्गोरिदम निम्नलिखित रिग्रेट बाउंड्स प्राप्त करता है (लॉगारिदमिक कारकों को छोड़कर):

बिना सिम्युलेटर के: $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3 T \log K}\})$ $\tilde{O} (min {d^{2} T, d^{3} T lo g K})$ ।
- यह Liu et al. (2023) के एक खुले प्रश्न को हल करता है कि क्या बहुपद समय में $K$ से स्वतंत्र $\text{poly}(d)\sqrt{T}$ रिग्रेट प्राप्त किया जा सकता है।
- इसकी कम्प्यूटेशनल जटिलता $\text{poly}(d, T)$ प्लस लीनियर ऑप्टिमाइजेशन ऑरेकल के $\text{poly}(d, T)$ कॉल्स है।
सिम्युलेटर के साथ: यदि लर्नर के पास एक सिम्युलेटर तक पहुँच है जो मुफ्त कॉन्टेक्स्ट जनरेट कर सकता है, तो रिग्रेट बाउंड सुधरकर $\tilde{O}(d\sqrt{L^*})$ हो जाता है, जहाँ $L^*$ सर्वोत्तम नीति का संचयी लॉस है। यह एक फर्स्ट-ऑर्डर बाउंड है जो समस्या के कठिनाई स्तर के अनुसार अनुकूलित होता है।

महत्व और दावे

लेखक दावा करते हैं कि यह कार्य एक सामान्य ढांचा प्रदान करता है जो घातीय रूप से बड़े एक्शन स्पेस (जैसे शॉर्टेस्ट पाथ, फ्लो, बाइटिक मैचिंग) वाली एडवर्सरियल लीनियर कॉन्टेक्स्टुअल बैंडिट्स की प्रयोज्यता को महत्वपूर्ण रूप से बढ़ाता है, बिना कॉन्टेक्स्ट वितरण या सिम्युलेटर के ज्ञान की आवश्यकता के।

लेखक स्पष्ट रूप से उल्लेख करते हैं कि हालांकि $\tilde{O}(d^2\sqrt{T})$ का बाउंड $K$ पर निर्भर पिछले बहुपद-समय परिणामों की तुलना में एक सुधार है, लेकिन यह अभी भी एक खुला प्रश्न है कि क्या बिना सिम्युलेटर के बहुपद समय में निकट-इष्टतम $\tilde{O}(d\sqrt{T})$ बाउंड प्राप्त किया जा सकता है। वे यह भी रेखांकित करते हैं कि उनका दृष्टिकोण उन पूर्व कार्यों (Olkhovskaya et al., 2023) द्वारा आवश्यक अनरियलिस्टिक लॉग-कॉन्केव कॉन्टेक्स्ट डिस्ट्रीब्यूशन की धारणा को हटा देता है, जो कुछ विशिष्ट फॉर्मुलेशन में लागू होते हैं। अंत में, वे सुझाव देते हैं कि रिडक्शन फ्रेमवर्क अन्य सेटिंग्स, जैसे फिक्स्ड ट्रांजिशन और एडवर्सरियल लॉस वाले लीनियर MDPs पर भी लागू हो सकता है।