📊 statistics

Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment

यह शोध पत्र अज्ञात ग्राफ वाले कॉज़ल बैंडिट समस्याओं के लिए बैकडोर-एडजस्टमेंट अपर कॉन्फिडेंस बाउंड (BA-UCB) एल्गोरिदम का प्रस्ताव करता है, जो वैध बैकडोर एडजस्टमेंट सेटों की पहचान करने के लिए क्रमिक प्रेक्षण संबंधी और प्रयोगात्मक डेटा का लाभ उठाता है, जिससे मौजूदा तरीकों की तुलना में बेहतर रिग्रेट बाउंड्स और भुजाओं (arms) की संख्या पर कम निर्भरता प्राप्त होती है।

मूल लेखक: Yijia Zhao, Qing Zhou

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

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

CC BY 4.0

मूल लेखक: Yijia Zhao, Qing Zhou

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

कल्पना कीजिए कि आप एक किसान हैं जो यह पता लगाने की कोशिश कर रहे हैं कि कौन सा एकल बदलाव आपकी फसलों को सबसे बड़ा बना देगा। आपके पास एक बगीचा है जिसमें कई चर (variables) हैं: तापमान, मिट्टी की नमी, उर्वरक का प्रकार और धूप। आप जानते हैं कि ये चीजें फसल को प्रभावित करती हैं, लेकिन आप यह नहीं जानते कि वे वास्तव में कैसे परस्पर क्रिया (interact) करती हैं।

यह कॉज़ल बैंडिट प्रॉब्लम (Causal Bandit Problem) है। आपको सबसे अच्छे परिणाम को खोजने के लिए निर्णयों (हस्तक्षेपों) की एक श्रृंखला लेनी होगी, लेकिन हर बार जब आप कुछ बदलते हैं (जैसे गर्मी बढ़ाना), तो उसमें समय और पैसा खर्च होता है। आप संसाधनों को बर्बाद किए बिना जितनी जल्दी हो सके सबसे अच्छी रणनीति सीखना चाहते हैं।

पुराना तरीका: अंधेरे में अनुमान लगाना

पारंपरिक रूप से, किसान (या कंप्यूटर एल्गोरिदम) बस एक-एक करके चीजें आजमाते थे।

"चलो थोड़ा और पानी देते हैं।" (परिणामों का इंतज़ार करें।)
"चलो थोड़ी और धूप देते हैं।" (परिणामों का इंतज़ार करें।)
"चलो थोड़ा कम उर्वरक देते हैं।" (परिणामों का इंतज़ार करें।)

यह 100 लीवर वाली स्लॉट मशीन खेलने जैसा है, जहाँ आप यह देखने के लिए हर लीवर को बेतरतीब ढंग से खींच रहे हैं कि कौन सा सबसे अधिक भुगतान करता है। यह काम तो करता है, लेकिन यह धीमा और महंगा है क्योंकि आपको निश्चित होने के लिए हर लीवर को कई बार खींचना पड़ता है।

नया विचार: "बैकडोर" शॉर्टकट

इस शोध पत्र के लेखक, झाओ और झोउ, एक स्मार्ट तरीका प्रस्तावित करते हैं जिसे BA-UCB (बैकडोर-एडजस्टमेंट अपर कॉन्फिडेंस बाउंड) कहा जाता है।

इसका असली रहस्य यह है: आपके पास पहले से ही एक विशाल लाइब्रेरी में पुराना, मुफ्त डेटा मौजूद है।
कल्पना कीजिए कि आपके पास 10 साल के ऐतिहासिक मौसम और फसल रिकॉर्ड (अवलोकन संबंधी डेटा/Observational Data) हैं जहाँ आपने कुछ भी बदला नहीं था, बस जो स्वाभाविक रूप से हुआ उसे देखा था। आपके पास नए प्रयोग (प्रायोगिक डेटा/Experimental Data) चलाने के लिए एक छोटा बजट भी है।

समस्या यह है: आपको "नियम पुस्तिका" (Causal Graph) का ज्ञान नहीं है। आप नहीं जानते कि "गर्मी" से "सूखी मिट्टी" होती है या "सूखी मिट्टी" से "गर्मी" होती है। नियम पुस्तिका के बिना, आप यह अनुमान आसानी से नहीं लगा सकते कि यदि आप कुछ बदलते हैं तो क्या होगा।

जादुई ट्रिक: "बैकडोर" खोजना

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

इसे ठीक करने के लिए, आपको "बारिश" को स्थिर रखकर "बैकडोर को ब्लॉक" करने की आवश्यकता है। लेकिन यदि आपको नियम पुस्तिका का ज्ञान नहीं है, तो आप कैसे जानेंगे कि किन चरों को स्थिर रखना है?

BA-UCB इसे दो चीजें एक साथ करके हल करता है:

जासूस (The Detective): यह पुराने डेटा और नए प्रयोगात्मक डेटा को एक साथ देखता है और अनुमान लगाता है कि कौन से चर वे "बैकडोर" (कन्फाउंडर्स) हैं जिन्हें ब्लॉक करने की आवश्यकता है।
आशावादी (The Optimist): यह प्रत्येक विचार के लिए एक "कॉन्फिडेंस स्कोर" बनाता है। यदि पुराना डेटा और नया डेटा इस बात से सहमत है कि "उर्वरक + बारिश को रोकना = बड़ी फसल," तो स्कोर बढ़ जाता है। यदि वे असहमत हैं, तो स्कोर कम रहता है, और एल्गोरिदम आगे की जांच जारी रखता है।

उपमा: जासूस और प्रयोगशाला

कल्पना कीजिए कि आप एक अपराध सुलझाने की कोशिश कर रहे हैं (सबसे अच्छी फसल रणनीति खोजना) एक जासूस हैं।

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

यह एक बड़ी बात क्यों है?

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

परिणाम

अपने कंप्यूटर सिमुलेशन में, इस नए BA-UCB एल्गोरिदम ने मानक तरीकों की तुलना में बहुत कम गलतियाँ (कम 'रिग्रेट') कीं। इसने बहुत तेज़ी से सबसे अच्छी खेती की रणनीति खोजी, कम पैसा खर्च किया, और इसे पहले से ही बगीचे के गुप्त नियमों को जानने की आवश्यकता नहीं थी।

संक्षेप में: यह एक स्मार्ट, अनुकूलन योग्य (adaptive) लर्निंग सिस्टम है जो जानता है कि मुफ्त ऐतिहासिक डेटा को महंगे नए प्रयोगों के साथ कैसे मिलाना है ताकि सबसे अच्छे निर्णय लिए जा सकें, भले ही उसे अभी पूरी कहानी का ज्ञान न हो।

यहाँ ज़ाओ और झोउ के शोध पत्र "Causal Bandit Over Unknown Graphs: Upper Confidence Bounds with Backdoor Adjustment" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र कॉज़ल बैंडिट (Causal Bandit - CB) समस्या को संबोधित करता है, जो एक अनुक्रमिक निर्णय लेने वाला कार्य (sequential decision-making task) है जहाँ एक एजेंट एक कॉज़ल सिस्टम में अपेक्षित प्रतिफल (expected reward) को अधिकतम करने के लिए हस्तक्षेपों (interventions/arms) का चयन करता है।

चुनौती: मानक मल्टी-आर्म्ड बैंडिट्स (MAB) के विपरीत, जहाँ आर्म्स स्वतंत्र ब्लैक बॉक्स होते हैं, कॉज़ल बैंडिट्स एक निर्देशित अचक्रीय ग्राफ (Directed Acyclic Graph - DAG) के भीतर कार्य करते हैं जहाँ चर (variables) कॉज़ली जुड़े होते हैं। एक चर पर हस्तक्षेप करने से अन्यों पर प्रभाव पड़ता है।
अंतराल (The Gap): मौजूदा CB विधियाँ आमतौर पर यह मान लेती हैं कि कॉज़ल ग्राफ संरचना ज्ञात है या वे प्रतिबंधात्मक संरचनात्मक धारणाएँ लागू करती हैं। वास्तविकता में, अंतर्निहित DAG अक्सर अज्ञात होता है।
विशिष्ट सेटिंग: लेखक गौसियन DAG मॉडल (लीनियर स्ट्रक्चरल इक्वेशन मॉडल्स) पर ध्यान केंद्रित करते हैं जहाँ रिवॉर्ड चरों का एक लीनियर फंक्शन होता है। लक्ष्य बिना किसी पूर्व ज्ञान के अपेक्षित रिवॉर्ड $E[Y | do(X_i = x_i)]$ को अधिकतम करने वाले एटोमिक इंटरवेंशन $do(X_i = x_i)$ की पहचान करना है।
डेटा स्रोत: यह सेटिंग दो डेटा स्रोतों का लाभ उठाती है:
1. प्रायोगिक डेटा (Experimental Data): बैंडिट प्रक्रिया के दौरान अनुक्रमिक रूप से एकत्र किया गया (महंगा, सीमित)।
2. अवलोकन संबंधी डेटा (Observational Data): बिना किसी हस्तक्षेप के एकत्र किया गया ऐतिहासिक डेटा (प्रचुर, सस्ता)।

2. कार्यप्रणाली: BA-UCB एल्गोरिदम

लेखक बैकडोर-एडजस्टमेंट अपर कॉन्फिडेंस बाउंड्स (Backdoor-Adjustment Upper Confidence Bounds - BA-UCB) एल्गोरिदम का प्रस्ताव करते हैं। मुख्य नवाचार यह है कि यह अज्ञात ग्राफ होने पर भी बैकडोर एडजस्टमेंट के माध्यम से कॉज़ल प्रभावों का अनुमान लगाने के लिए अवलोकन संबंधी डेटा को एकीकृत करता है।

मुख्य घटक:

बैकडोर एडजस्टमेंट की पहचान (Backdoor Adjustment Identification):
- पूर्ण DAG को रिकवर करने के बजाय (जो गणनात्मक रूप से कठिन है और मार्कोव इक्विवेलेंस के कारण अक्सर असंभव है), एल्गोरिदम प्रत्येक इंटरवेंशन आर्म $X_i$ के लिए कैंडिडेट बैकडोर एडजस्टमेंट सेट्स ( $S$ ) की पहचान करता है।
- तंत्र: एक कैंडिडेट सेट $S$ के लिए, एल्गोरिदम अवलोकन संबंधी डेटा (उपयोग करके रिग्रेशन $Y \sim X_i + X_S$ ) से प्राप्त कॉज़ल प्रभाव अनुमान की तुलना प्रायोगिक डेटा (सीधे $X_i$ पर इंटरवेंशन) से प्राप्त अनुमान से करता है।
- चयन मानदंड: एक सेट $S$ को वैध कैंडिडेट माना जाता है यदि अवलोकन संबंधी अनुमान और प्रायोगिक अनुमान के बीच के अंतर का कॉन्फिडेंस इंटरवल शून्य को समाहित करता है। यह डेटा-संचालित दृष्टिकोण बिना वास्तविक ग्राफ की आवश्यकता के अमान्य एडजस्टमेंट सेट्स को फ़िल्टर करता है।
वेटेड एस्टीमेशन (Weighted Estimation):
- एक बार कैंडिडेट सेट $S$ की पहचान हो जाने के बाद, एल्गोरिदम अपेक्षित रिवॉर्ड $\mu_i$ के लिए एक वेटेड एवरेज एस्टीमेटर बनाता है।
- यह उनके संबंधित सैंपल साइज और वेरिएंस के आधार पर अवलोकन संबंधी अनुमान ( $\hat{\mu}_{i,obs}$ ) और प्रायोगिक अनुमान ( $\hat{\mu}_{i,int}$ ) को जोड़ता है।
- मजबूती (Robustness): पेपर "सिंगल रिग्रेशन" दृष्टिकोण (सभी डेटा को एक ही रिग्रेशन में मिलाना) के विरुद्ध तर्क देता है क्योंकि यदि चयनित एडजस्टमेंट सेट अमान्य है तो यह पक्षपाती (biased) हो सकता है। वेटेड एवरेज दृष्टिकोण मिस-स्पेसिफिकेशन के प्रति अधिक मजबूत है।
निर्णय नियम (Decision Rule - UCB):
- एल्गोरिदम उस आर्म $A_{t+1}$ का चयन करता है जो अपर कॉन्फिडेंस बाउंड को अधिकतम करता है:
  $\hat{\mu}_i(t, S) + \hat{\sigma}_i(t, S) \cdot c \sqrt{\log t}$
- यहाँ, $\hat{\mu}_i$ और $\hat{\sigma}_i$ को अवलोकन संबंधी और प्रायोगिक डेटा के वेटेड कॉम्बिनेशन से प्राप्त किया गया है।
लेटेंट कॉन्फ़ाउंडर्स को संभालना (Handling Latent Confounders):
- इस फ्रेमवर्क को एसाइक्लिक डायरेक्टेड मिक्स्ड ग्राफ्स (ADMGs) के लिए विस्तारित किया गया है जहाँ लेटेंट कॉन्फ़ाउंडर्स (द्विदिश किनारों द्वारा दर्शाए गए) मौजूद होते हैं।
- यदि किसी विशिष्ट आर्म के लिए कोई वैध एडजस्टमेंट सेट मौजूद नहीं है (लेटेंट कॉन्फ़ounding के कारण), तो एल्गोरिदम स्वचालित रूप से उस आर्म के लिए केवल प्रायोगिक डेटा का उपयोग करने के लिए डिफ़ॉल्ट हो जाता है, जिससे सैद्धांतिक वैधता सुनिश्चित होती है।

3. मुख्य योगदान

अज्ञात ग्राफ धारणा (Unknown Graph Assumption): अज्ञात कॉज़ल ग्राफ के साथ, बिना यह माने कि ग्राफ प्रदान किया गया है या एक्शन स्पेस को रिवॉर्ड के पेरेंट्स तक सीमित किया गया है, कॉज़ल बैंडिट्स को हल करने वाली यह पहली विधि है।
डेटा एकीकरण (Data Integration): एक नया फ्रेमवर्क जो लर्निंग को तेज करने और रिग्रेट (regret) को कम करने के लिए प्रचुर, कम लागत वाले अवलोकन संबंधी डेटा को महंगे प्रायोगिक डेटा के साथ सहजता से एकीकृत करता है।
सैद्धांतिक गारंटी (Theoretical Guarantees):
- रिग्रेट बाउंड्स (Regret Bounds): संचयी रिग्रेट (cumulative regret) पर परिमित-समय (finite-time) ऊपरी सीमाएं स्थापित की गई हैं।
- $K$ पर निर्भरता: लेटेंट कॉन्फ़ाउंडर्स की अनुपस्थिति में, रिग्रेट बाउंड $O(\sqrt{T \log T / (m+n)})$ है, जो आर्म्स की संख्या $K$ पर निर्भर नहीं करता है (पर्याप्त अवलोकन संबंधी डेटा मानते हुए)। यह मानक MAB बाउंड $O(\sqrt{KT \log T})$ की तुलना में एक महत्वपूर्ण सुधार है।
- लेटेंट कॉन्फ़ाउंडर्स: विस्तारित बाउंड्स दिखाते हैं कि रिग्रेट कुल $K$ के बजाय $K_1$ (उन आर्म्स की संख्या जिनके पास कोई वैध एडजस्टमेंट सेट नहीं है) पर निर्भर करता है।
गणना दक्षता (Computational Efficiency): बेयसियन दृष्टिकोणों के विपरीत जिन्हें सभी संभावित ग्राफ स्ट्रक्चरों पर पोस्टीरियर अपडेट करने की आवश्यकता होती है (एक्सपोनेंशियल कॉम्प्लेक्सिटी), BA-UCB रिग्रेशन-आधारित नेबरहुड एस्टीमेशन का उपयोग करता है, जिससे यह बड़े ग्राफ के लिए स्केलेबल बनता है।

4. परिणाम

लेखकों ने BA-UCB की निम्नलिखित के साथ व्यापक सिमुलेशन तुलना की:

स्टैंडर्ड UCB: केवल प्रायोगिक डेटा का उपयोग करता है।
CN-UCB (सेंट्रल नोड): पहले रिवॉर्ड के पेरेंट्स की पहचान करने का प्रयास करता है (यदि इष्टतम आर्म पेरेंट नहीं है तो विफल हो जाता है)।
BBB-UCB (बेयसियन बैकडोर): एक बेयसियन विधि जो बड़े ग्राफ के लिए गणनात्मक रूप से अत्यधिक कठिन (prohibitive) है।

मुख्य निष्कर्ष:

प्रदर्शन: BA-UCB, स्टैंडर्ड UCB और CN-UCB की तुलना में काफी कम संचयी रिग्रेट प्राप्त करता है।
स्केलेबिलिटी: BA-UCB गणनात्मक रूप से कुशल है और नोड्स ( $p$ ) की संख्या के साथ अच्छी तरह से स्केल करता है, जबकि BBB-UCB $p \ge 20$ के लिए अव्यवहार्य (intractable) हो जाता है।
मजबूती (Robustness): जब इष्टतम इंटरवेंशन रिवॉर्ड का पेरेंट नहीं होता है (CN-UCB के लिए एक सामान्य विफलता मामला), तब भी BA-UCB उच्च प्रदर्शन बनाए रखता है।
अभिसरण (Convergence): सिमुलेशन दिखाते हैं कि एल्गोरिदम समय के साथ वैध एडजस्टमेंट सेट्स की सफलतापूर्वक पहचान करता है, और संयुक्त एस्टीमेटर वास्तविक कॉज़ल प्रभाव की ओर अभिसरित होता है।

5. महत्व

यह कार्य कॉज़ल इंफरेंस और अनुक्रमिक निर्णय लेने के बीच के अंतर को उन वास्तविक स्थितियों में पाटता है जहाँ:

ग्राफ अज्ञात हैं: यह अज्ञात कॉज़ल स्ट्रक्चर की अवास्तविक धारणा को हटा देता है।
डेटा विषम (Heterogeneous) है: यह लर्निंग को तेज करने और महंगे प्रयोगों की आवश्यकता को कम करने के लिए "मुफ्त" अवलोकन संबंधी डेटा का प्रभावी ढंग से लाभ उठाता है।
स्केलेबिलिटी महत्वपूर्ण है: यह उच्च-आयामी (high-dimensional) कॉज़ल बैंडिट समस्याओं के लिए एक गणनात्मक रूप से व्यवहार्य विकल्प प्रदान करता है।

प्रस्तावित BA-UCB एल्गोरिदम कॉज़ल बैंडिट्स के लिए एक अत्याधुनिक दृष्टिकोण का प्रतिनिधित्व करता है, जो विशेष रूप से बड़े एक्शन स्पेस और उपलब्ध ऐतिहासिक अवलोकन संबंधी डेटा वाले परिदृश्यों में मजबूत सैद्धांतिक गारंटी और व्यावहारिक दक्षता प्रदान करता है।