Characterizing Bias in Post-Bandit Inference under Index Algorithms

तकनीकी सारांश: इंडेक्स एल्गोरिदम के तहत पोस्ट-बैंडिट अनुमान में पूर्वाग्रह (Bias) का लक्षण वर्णन

समस्या विवरण
यह शोध पत्र मल्टी-आर्म्ड बैंडिट (MAB) एल्गोरिदम द्वारा उत्पन्न डेटा पर सांख्यिकीय अनुमान लगाने की चुनौती को संबोधित करता है। पारंपरिक स्वतंत्र और समान रूप से वितरित (i.i.d.) डेटा के विपरीत, बैंडिट डेटा अनुकूलित (adaptively) रूप से एकत्र किया जाता है, जिससे एक फीडबैक लूप बनता है जहाँ आवंटन निर्णय पिछले अवलोकनों पर निर्भर करते हैं। यह अनुकूलता नमूना माध्य अनुमानक (sample mean estimator), $\bar{X}_a(N_a(T))$ में एक व्यवस्थित चयन पूर्वाग्रह (selection bias) उत्पन्न करती है, जो कॉन्फिडेंस इंटरवल और परिकल्पना परीक्षणों (hypothesis tests) को विकृत कर सकती है। जबकि पूर्व साहित्य ने यह स्थापित किया है कि ऐसा पूर्वाग्रह मौजूद है (जैसे, Nie et al., 2018) और सामान्य स्पर्शोन्मुख सीमाएँ (asymptotic bounds) प्रदान की हैं (जैसे, Shin et al., 2019a,b; Russo and Zou, 2016), व्यापक रूप से उपयोग किए जाने वाले पूर्णतः अनुकूलनीय इंडेक्स एल्गोरिदम जैसे UCB1 के लिए इस पूर्वाग्रह के सटीक, अग्रणी-क्रम (leading-order) लक्षण वर्णन की कमी है। मुख्य शोध प्रश्न यह निर्धारित करना है कि मानक इंडेक्स एल्गोरिदम के तहत नमूना-माध्य पूर्वाग्रह और संबंधित Z-सांख्यिकी पूर्वाग्रह का सटीक परिमाण क्या है, और यह समझना है कि एल्गोरिदम के डिज़ाइन विकल्प इस पूर्वाग्रह को कैसे प्रभावित करते हैं।

कार्यप्रणाली
लेखक स्थिर इंडेक्स एल्गोरिदम (stable index algorithms) पर ध्यान केंद्रित करते हैं, जो कैनोनिकल अपर कॉन्फिडेंस बाउंड (UCB1) और इसके सामान्यीकरणों को शामिल करने वाला एक वर्ग है। मुख्य पद्धतिगत नवाचार एल्गोरिदम की सैंपलिंग गतिशीलता का एक नया अनुभवजन्य तरल सन्निकटन (empirical fluid approximation) है।

1. तरल सन्निकटन (Fluid Approximation): लेखक पहले एक नियत (deterministic) तरल सन्निकटन, $n_T$ को परिभाषित करते हैं, जो इंडेक्स-समीकरणों में जनसंख्या माध्य ($\mu$) को अनुभवजन्य नमूना माध्यओं से बदलकर प्राप्त किया जाता है। यह प्रथम-क्रम आवंटन व्यवहार को पकड़ता है लेकिन स्टोकेस्टिक उतार-चढ़ाव को अनदेखा करता है।
2. अनुभवजन्य तरल सन्निकटन (Empirical Fluid Approximation): पुल काउंट (pull counts) और रिवॉर्ड उतार-चढ़ाव के बीच महत्वपूर्ण सहसंबंध को पकड़ने के लिए, जो पूर्वाग्रह को संचालित करता है, लेखक एक द्वितीय-क्रम सन्निकटन, $\tilde{n}_T$ पेश करते हैं। इसे इंडेक्स-समीकरणों में तरल आवंटन काउंट पर मूल्यांकित नमूना माध्यों ($\bar{X}_a(n_{a,T})$) को पुनः शामिल करके बनाया गया है।
3. प्रमुख मात्रा (Key Quantity): विश्लेषण एक महत्वपूर्ण एल्गोरिदम-निर्भर मात्रा की पहचान करता है जिसे प्रभावी अन्वेषण दर (effective exploration rate) कहा जाता है, जिसे $\Gamma_{a,T}$ द्वारा दर्शाया गया है। एक इंडेक्स फ़ंक्शन $I_t(x, n)$ के लिए, यह $\Gamma_t(x, n) := -2n^{3/2} \frac{\partial_n I_t(x, n)}{\partial_x I_t(x, n)}$ के रूप में परिभाषित है। यह दर इस बात को मापती है कि आवंटन नमूना माध्य विक्षोभ (perturbations) के प्रति कितना उत्तरदायी है; उच्च दर कम उत्तरदायित्व और इस प्रकार कम पूर्वाग्रह का संकेत देती है।
4. स्थिरता स्थितियाँ (Stability Conditions): सैद्धांतिक परिणाम तीन शर्तों पर निर्भर करते हैं: इंडेक्स फ़ंक्शन की नियमितता (smoothness और monotonicity), तरल स्केलिंग स्थितियाँ (यह सुनिश्चित करना कि उप-इष्टतम भुजाओं को पर्याप्त रूप से खींचा जाए), और स्थिरता स्थितियाँ (यह सुनिश्चित करना कि वास्तविक पुल काउंट अनुभवजन्य तरल सन्निकटन के आसपास केंद्रित हों)।

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

• पूर्वाग्रह का सटीक लक्षण वर्णन: लेखक क्षितिज $T \to \infty$ होने पर नमूना माध्य और Z-सांख्यिकी के पूर्वाग्रह के स्पष्ट अग्रणी-क्रम व्यंजक प्राप्त करते हैं।

  • किसी भी भुजा $a$ के लिए जो एकमात्र इष्टतम भुजा नहीं है, Z-सांख्यिकी का मानकीकृत पूर्वाग्रह, $E[Z_{a,T}]$, इस रूप में अभिसरित होता है:
    $$E[Z_{a,T}] \approx -\left(1 - \frac{1}{|O|}\mathbb{1}\{a \in O\}\right) \frac{\sigma_a}{\Gamma_{a,T}}$$
    जहाँ $O$ इष्टतम भुजाओं का सेट है और $\sigma_a$ रिवॉर्ड का मानक विचलन है।
  • एकमात्र इطतम भुजा के लिए, पूर्वाग्रह बहुत छोटे क्रम का है, जो बहुपद दर से घटता है (जैसे, सामान्यीकृत UCB के लिए $O(f_T/T)$), जबकि गैर-इष्टतम इष्टतम भुजाओं में पूर्वाग्रह $1/\Gamma_{a,T}$ की दर से घटता है।

• सामान्यीकृत UCB पर अनुप्रयोग: इंडेक्स $I_t(x, n) = x + f_t/\sqrt{n}$ वाले सामान्यीकृत UCB एल्गोरिदम के विशेषकरण के साथ, प्रभावी अन्वेषण दर $\Gamma_{a,T} = f_T$ है।

  • UCB1 का मामला: मानक UCB1 के लिए, $f_T = \sqrt{2 \log T}$ है। फलस्वरूप, मानकीकृत पूर्वाग्रह अत्यंत धीमी दर $1/\sqrt{\log T}$ पर घटता है। इसका तात्पर्य यह है कि बड़े $T$ के लिए भी, पूर्वाग्रह अनुमान संबंधी पैमाने पर पर्याप्त बना रहता है।
  • सामान्यीकृत मामला: पूर्वाग्रह $1/f_T$ के रूप में स्केल करता है।

• रिग्रेट-पूर्वाग्रह ट्रेड-ऑफ (Regret-Bias Trade-off): लेखक रिग्रेट न्यूनीकरण और अनुमान पूर्वाग्रह के बीच एक मौलिक ट्रेड-ऑफ स्थापित करते हैं।

  • सामान्यीकृत UCB के लिए रिग्रेट $f_T^2$ के रूप में स्केल करता है।
  • पूर्वाग्रह $1/f_T$ के रूप में स्केल करता है।
  • इसलिए, पूर्वाग्रह $1/\sqrt{\text{Regret}}$ के रूप में स्केल करता है। वे एल्गोरिदम जो रिग्रेट को आक्रामक रूप से कम करने के लिए डिज़ाइन किए गए हैं (जैसे धीमी बढ़ती $f_T$ के साथ UCB1), अधिक पूर्वाग्रह रखते हैं। इसके विपरीत, अधिक अन्वेषणात्मक एल्गोरिदम (तेजी से बढ़ती $f_T$) पूर्वाग्रह को कम करते हैं लेकिन रिग्रेट बढ़ाते हैं।

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

महत्व और दावे
शोध पत्र का दावा है कि यह पूर्णतः अनुकूलनीय, स्थिर इंडेक्स एल्गोरिदम के लिए पहला सटीक, अग्रणी-क्रम लक्षण वर्णन प्रदान करता है। इसका महत्व निम्नलिखित में निहित है:

1. अनुमानत्मक लागत का परिमाणीकरण: यह प्रदर्शित करता है कि UCB1 जैसे मानक एल्गोरिदम के लिए, पूर्वाग्रह इतनी धीमी दर ($1/\sqrt{\log T}$) से घटता है कि यह व्यावहारिक अनुमान सेटिंग्स में मानक त्रुटि (standard error) पर हावी हो सकता है, जो बिना सुधार के मानक पोस्ट-बैंडिट अनुमान की वैधता को चुनौती देता है।
2. एल्गोरिदम संबंधी अंतर्दृष्टि: यह स्पष्ट करता है कि पूर्वाग्रह केवल अनुकूलता (adaptivity) का कार्य नहीं है बल्कि संरचनात्मक रूप से इंडेक्स फ़ंक्शन के विशिष्ट रूप (प्रभावी अन्वेषण दर के माध्यम से) द्वारा निर्धारित होता है।
3. डिज़ाइन निहितार्थ: यह एकमात्र इष्टतम भुजा वाले मामलों (कम पूर्वाग्रह) और कई इष्टतम भुजाओं वाले मामलों (उच्च पूर्वाग्रह) के बीच एक गुणात्मक अंतर को उजागर करता है, और रिग्रेट को न्यूनतम करने और पूर्वाग्रह को न्यूनतम करने के बीच के ट्रेड-ऑफ को स्पष्ट रूप से मैप करता है।
4. पद्धतिगत योगदान: अनुभवजन्य तरल सन्निकटन ढांचा अनुकूलित सैंपलिंग में जटिल अस्थायी निर्भरताओं (temporal dependencies) के विश्लेषण के लिए एक सुलभ उपकरण के रूप में प्रस्तुत किया गया है, जो अन्य बैंडिट एल्गोरिदम के अन्य अनुमानित गुणों पर भी लागू हो सकता है।

लेखक नोट करते हैं कि उनके परिणाम विशिष्ट रूप से स्थिर इंडेक्स एल्गोरिदम के लिए हैं और सीधे अस्थिर एल्गोरिदम (जैसे थॉम्पसन सैंपलिंग या $\epsilon$-greedy) या गैर-इंडेक्स विधियों पर लागू नहीं होते हैं, जो भविष्य के कार्य के लिए दिशाओं के रूप में इन्हें सुझाते हैं। वे यह भी जोर देते हैं कि हालांकि पूर्वाग्रह सूत्र प्राकृतिक सुधारों का सुझाव देता है, बेहतर परिमित-नमूना प्रदर्शन के साथ व्यावहारिक कॉन्फिडेंस इंटरवल का निर्माण करना एक खुला कार्य (open task) बना हुआ है।