Active Context Selection Improves Simple Regret in Contextual Bandits

तकनीकी सारांश: सक्रिय संदर्भ चयन (Active Context Selection) कॉन्टेक्स्टुअल बैंडिट्स में सरल पछतावे (Simple Regret) में सुधार करता है

समस्या का निरूपण
यह शोध पत्र एक परिमित संदर्भ स्थान (finite context space) के भीतर कॉन्टेक्स्टुअल मल्टी-आर्म्ड बैंडिट समस्या की जांच करता है, जहाँ संदर्भ (contexts) विशिष्ट उप-जनसंख्याओं (जैसे, जनसांख्यिकीय समूह) का प्रतिनिधित्व करते हैं। सीखने का उद्देश्य संदर्भ-भारित सरल पछतावे (context-weighted simple regret) द्वारा परिभाषित किया गया है: एक निश्चित प्रयोगात्मक बजट $T$ के बाद, शिक्षार्थी को प्रत्येक उप-जनसंख्या के लिए एक सर्वोत्तम उपचार (treatment) की सिफारिश करनी चाहिए। प्रदर्शन मीट्रिक $k$ उप-जनसंख्याओं पर जनसंख्या वितरण वेक्टर $p$ द्वारा भारित, इष्टतम और अनुशंसित उपचारों के बीच अपेक्षित अंतर है।

अध्ययन दो नमूनाकरण व्यवस्थाओं (sampling regimes) के बीच अंतर करता है:

1. निष्क्रिय नमूनाकरण (Passive Sampling): संदर्भ $p$ के निश्चित वितरण के अनुसार यादृच्छिक रूप से प्रकट होते हैं, और शिक्षार्थी केवल उपचार चुनता है।
2. सक्रिय नमूनाकरण (Active Sampling): शिक्षार्थी प्रत्येक दौर के लिए उप-जनसंख्या (संदर्भ) और उपचार दोनों को सक्रिय रूप से चुन सकता है।

विश्लेषण पुरस्कार वितरणों के संबंध में एक 'वर्स्ट-केस' (worst-case) सेटिंग मानता है, लेकिन संदर्भ वितरण $p$ के संबंध में यह 'इंस्टेंस-डिपेंडेंट' (instance-dependent) बना रहता है। शोध पत्र उस "डेटा-रिच" (data-rich) शासन पर ध्यान केंद्रित करता है जहाँ क्षितिज (horizon) $T$, उपचारों की संख्या $n$, संदर्भों की संख्या $k$, और न्यूनतम संदर्भ प्रायिकता के व्युत्क्रम से काफी बड़ा है।

कार्यप्रणाली और सैद्धांतिक ढांचा

• ज्ञात $p$ के लिए इष्टतम आवंटन:
  जब उप-जनसंख्या वितरण $p$ ज्ञात होता है, तो लेखक प्रयोगात्मक बजट के इष्टतम आवंटन का लक्षण वर्णन करते हैं। वे सिद्ध करते हैं कि वर्स्ट-केस सरल पछतावा मानदंड के लिए, हिस्ट्री-फ्री नीतियां (जहाँ संदर्भ चयन केवल $p$ पर निर्भर करता है और देखे गए इतिहास पर नहीं) मिनीमैक्स दर प्राप्त करने के लिए पर्याप्त हैं।

  • निष्क्रिय दर: निष्क्रिय नमूनाकरण के तहत, पछतावा $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$ के रूप में स्केल करता है।
  • सक्रिय दर: सक्रिय नमूनाकरण के तहत, इष्टतम रणनीति उप-जनसंख्या $j$ को $p_j^{2/3}$ के समानुपाती प्रायिकता के साथ नमूने आवंटित करती है। यह $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3}$ की पछतावा दर प्राप्त करती है।
  • अंतर (The Gap): निष्क्रिय के ऊपर सक्रिय के सुधार कारक को $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$ के रूप में वर्णित किया गया है। लेखक दिखाते हैं कि अत्यधिक गैर-समान वितरणों के लिए, यह अंतर $\Theta(k^{1/4})$ जितना बड़ा हो सकता है। इष्टतम सक्रिय आवंटन नमूनाकरण प्रायिकताओं को $p$ की तुलना में अधिक समान वितरण की ओर स्थानांतरित करता है, जिससे छोटी उप-जनसंख्याओं में अन्वेषण (exploration) बढ़ता है।

• बजटयुक्त हस्तक्षेप (Budgeted Interventions):
  शोध पत्र इस विश्लेषण का विस्तार उन सेटिंग्स में करता है जहाँ सक्रिय नमूनाकरण महंगा है, जिससे शिक्षार्थी केवल $\alpha$ अंश के दौरों में उप-जनसंख्या चुन सकता है। लेखक एक प्रतिबन्धित अनुकूलन समस्या को सूत्रबद्ध करते हैं ताकि यह सुनिश्चित करने के लिए पछतावे को कम किया जा सके कि आवंटन $q$ इस शर्त को पूरा करे कि $q_j \geq (1-\alpha)p_j$। वे इष्टतम आवंटन के लिए एक थ्रेशोल्ड संरचना प्राप्त करते हैं: जिन उप-जनसंख्याओं की $p_j$ बड़ी है, वे अपने निष्क्रिय आवंटन पर बनी रह सकती हैं यदि बजट उन्हें सुधारने के लिए अपर्याप्त है, जबकि अन्य को $p_j^{2/3}$ अनुपात की ओर बढ़ाया जाता है। वे पूर्णतः सक्रिय इष्टतम दर को पुनः प्राप्त करने के लिए आवश्यक न्यूनतम बजट $\alpha_{\min}(p)$ की पहचान करते हैं।

• अज्ञात $p$ (EETC एल्गोरिदम):
  जब $p$ अज्ञात होता है, तो एक पूर्णतः सक्रिय नीति सीधे $p^{2/3}$ नियम को नहीं अपना सकती। लेखक एक्सप्लोर-एक्सप्लोर-देन-कमिट (EETC) एल्गोरिदम का प्रस्ताव करते हैं, जो तीन चरणों के बीच संतुलन बनाता है:

  1. प्रारंभिक निष्क्रिय अन्वेषण: शिक्षार्थी $p$ का अनुमान लगाने के लिए निष्क्रिय रूप से कार्य करता है।
  2. निरंतर निष्क्रिय नमूनाकरण: शिक्षार्थी तब तक निष्क्रिय नमूनाकरण जारी रखता है जब तक कि शेष बजट वर्तमान अनुमान के आधार पर इष्टतम सक्रिय आवंटन को लागू करने के लिए पर्याप्त न हो जाए।
  3. प्रतिबद्धता (Commitment): शिक्षार्थी शेष दौरों को आवंटित करने के लिए अनुमानित वितरण का उपयोग करके सक्रिय नमूनाकरण की ओर स्विच करता है।
     सैद्धांतिक विश्लेषण दिखाता है कि बड़े क्षितिज के लिए, EETC ज्ञात $p$ के साथ इष्टतम पूर्णतः सक्रिय नीति के समान सरल पछतावा दर प्राप्त करता है, जो स्थिरांक कारकों (constant factors) तक ही सीमित है।

प्रमुख परिणाम और प्रयोग

• सैद्धांतिक गारंटी: यह शोध पत्र कड़े पछतावा दरों को स्थापित करता है। यह सिद्ध करता है कि सक्रिय संदर्भ चयन, निष्क्रिय नमूनाकरण की तुलना में प्रदर्शन में सुधार करता है, और इस सुधार का परिमाण संदर्भ वितरण की विषमता (heterogeneity) पर निर्भर करता है।
• सिंथेटिक प्रयोग: सिंथेटिक डेटा पर प्रयोग पुष्टि करते हैं कि निष्क्रिय और सक्रिय नीतियों के बीच पछतावा अंतराल उप-जनसंख्याओं की संख्या $k$ बढ़ने के साथ बढ़ता है, जो उनके $\Theta(k^{1/4})$ बाउंड के अनुरूप है। यह दिखाया गया है कि EETC एल्गोरिदम ऑरेकल (known-$p$) सक्रिय नीति के प्रदर्शन के बहुत करीब पहुंच जाता है।
• वास्तविक दुनिया का डेटा (MovieLens): लेखकों ने MovieLens 1M डेटासेट का मूल्यांकन किया, जिसमें मूवी अनुशंसाओं को उपचार और जनसांख्यिकीय समूहों को उप-जनसंख्या के रूप में माना गया। परिणाम दर्शाते हैं कि निष्क्रिय नीतियां उच्चतम पछतावा देती हैं। ज्ञात-$p$ सक्रिय नीति और EETC दोनों ही निष्क्रिय बेसलाइन से काफी बेहतर प्रदर्शन करते हैं, और EETC क्षितिज बढ़ने के साथ ऑरेकल सक्रिय नीति के प्रदर्शन के करीब पहुंच जाता है।

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

लेखक इस बात पर जोर देते हैं कि उनका कार्य मानक कॉन्टेक्स्टुअल बैंडिट्स (जहाँ संदर्भ पर्यावरणीय होते हैं) और प्रयोगात्मक डिजाइन (जहाँ प्रयोगकर्ता नमूने को नियंत्रित करता है) के बीच के अंतर को पाटता है। इष्टतम आवंटन नियम ($q_j \propto p_j^{2/3}$) का लक्षण वर्णन करके और एक एल्गोरिदम (EETC) प्रदान करके जो बिना आसिम्प्टोटिक अनुकूलता (asymptotic optimality) से समझौता किए अज्ञात वितरणों के अनुकूल होता है, यह शोध पत्र विषम आबादी में कुशल संसाधन आवंटन के लिए एक कठोर ढांचा प्रदान करता है। यह कार्य सुझाव देता है कि उन परिदृश्यों में जहाँ लक्षित भर्ती या नियंत्रित नमूनाकरण संभव है, संदर्भों को चुनने की क्षमता को अनदेखा करना उप-इष्टतम उपचार अनुशंसाओं की ओर ले जाता है।