Information-Theoretic Generalization Bounds for Sequential Decision Making

तकनीकी सारांश: अनुक्रमिक निर्णय लेने के लिए सूचना-सैद्धांतिक सामान्यीकरण सीमाएँ (Information-Theoretic Generalization Bounds for Sequential Decision Making)

समस्या विवरण
सूचना-सैद्धांतिक (IT) सामान्यीकरण सीमाएँ, विशेष रूप से कंडीशनल म्यूचुअल इंफॉर्मेशन (CMI) और सुप्रासैंपल (supersample) निर्माणों पर आधारित, बैच, स्वतंत्र और समान रूप से वितरित (i.i.d.) सेटिंग में एल्गोरिदम-निर्भर विश्लेषण के लिए एक मानक उपकरण बन गई हैं। ये विधियाँ यह मापती हैं कि एक लर्निंग एल्गोरिदम कितनी मजबूती से प्रशिक्षण डेटा को अपने आउटपुट के साथ जोड़ता है, जो एक युग्मित सुप्रासैंपल के भीतर चयनित प्रशिक्षण निर्देशांकों (coordinates) की तुलना "घोस्ट" (अचयनित) निर्देशांकों से करके किया जाता है। हालाँकि, मौजूदा CMI ढांचे युग्मित i.i.d. सुप्रासैंपल्स की समरूपता (symmetry) पर निर्भर करते हैं, जो अनुक्रमिक निर्णय लेने वाली समस्याओं जैसे कि ऑनलाइन लर्निंग, स्ट्रीमिंग एक्टिव लर्निंग और स्टोकेस्टिक बैंडिट्स (stochastic bandits) में सीधे तौर पर लागू नहीं होता है। इन अनुकूलित (adaptive) सेटिंग्स में, डेटा इतिहास-निर्भर इंटरैक्शन के माध्यम से प्रकट होता है, और शिक्षार्थी (learner) एक कारणजन्य प्रक्षेपवक्र (causal trajectory) के साथ विकसित होता है। पूरे सेलेक्टर वेक्टर पर निर्भरता को मापने वाला एक टर्मिनल CMI टर्म यह बताने में विफल रहता है कि सूचना विशिष्ट राउंड में प्रक्षेपवक्र में कैसे प्रवेश करती है, जिससे अनुकूलित वातावरण में जनरलाइजेशन गैप (generalization gap) को नियंत्रित करना कठिन हो जाता है।

कार्यप्रणाली: अनुक्रमिक सुप्रासैंपल ढांचा (The Sequential Supersample Framework)
अनुकूलित सेटिंग्स में बैच CMI की सीमाओं को दूर करने के लिए, लेखक एक अनुक्रमिक सुप्रासैंपल ढांचे का प्रस्ताव करते हैं जो शिक्षार्थी के फिल्ट्रेशन (filtration) को प्रमाण-पक्ष विस्तार (proof-side enlargement) से अलग करता है।

1. कारणजन्य निर्माण (Causal Construction): यह ढांचा एक राउंड-दर-राउंड निर्माण पेश करता है जहाँ, प्रत्येक समय चरण $t$ पर, वातावरण एक युग्मित गुप्त पंक्ति $\tilde{Z}_t = (Z_{t,0}, Z_{t,1})$ उत्पन्न करता है। एक निष्पक्ष सेलेक्टर $U_t \in \{0, 1\}$ एक निर्देशांक चुनता है ($Z_t = Z_{t, U_t}$) जिसे शिक्षार्थी देखता है और अपडेट करता है। अचुने हुए निर्देशांक ($Z'_{t} = Z_{t, 1-U_t}$) को शिक्षार्थी द्वारा नहीं देखा जाता है, लेकिन इसे प्रमाण-पक्ष विश्लेषण के लिए एक "घोस्ट" निर्देशांक के रूप में रखा जाता है।
2. फिल्ट्रेशन पृथक्करण (Filtration Separation):
   • शिक्षार्थी इतिहास ($H_t$): इसमें केवल चयनित पथ के साथ रखे गए सूचना का विवरण होता है (पिछले अवलोकन, अवस्थाएँ और चयनित क्रियाएँ)।
   • प्रमाण-पक्ष विस्तार ($G_{t-1}$): एक स्थानीय सिग्मा-फील्ड जो $G_{t-1} = H_{t-1} \vee \sigma(\tilde{Z}_t)$ है। यह क्षेत्र प्रमाण के उद्देश्य के लिए वर्तमान युग्मित पंक्ति $(Z_{t,0}, Z_{t,1})$ को पूरी तरह से उजागर करता है, जिससे चयनित और घोस्ट निर्देशांकों के बीच तुलना संभव होती है, जबकि यह सुनिश्चित किया जाता है कि शिक्षार्थी की अवस्था $W_t$ केवल चयनित निर्देशांक से उत्पन्न हो।
3. अनुक्रमिक CMI (SCMI): लेखक अनुक्रमिक CMI को प्रमाण-पक्ष विस्तार पर आधारित शिक्षार्थी-प्रेरित लॉस (loss) या अवस्था और वर्तमान सेलेक्टर के बीच म्यूचुअल इंफॉर्मेशन के रूप में परिभाषित करते हैं: $I(L^+_t; U_t \mid G_{t-1})$। यह उस विशिष्ट दौर में सेलेक्टर के बारे में प्रकट होने वाली सूचना को मापता है जहाँ तुलना होती है, न कि टर्मिनल समय पर सूचना को एकत्रित करता है।
4. मान्यताएँ (Assumptions): यह ढांचा एक चयनित-निर्देशांक अपडेट स्थिति (शिक्षार्थी केवल चयनित निर्देशांक का उपयोग करके अपडेट होता है) और रो-वाइज एक्सचेंजैबिलिटी (दिए गए अतीत की स्थिति में जोड़ी $(Z_{t,0}, Z_{t,1})$ का संयुक्त वितरण स्वैपिंग के तहत अपरिवर्तित रहता है) पर निर्भर करता है।

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

1. सामान्य SCMI सीमाएँ (प्रमेय 2):
   लेखक स्थापित करते हैं कि अनुक्रमिक जनरलाइजेशन गैप (ट्रेन-होल्डआउट अंतर) राउंडवाइज SCMI टर्म्स के योग द्वारा नियंत्रित होता है। विशेष रूप से, गैप $I(L^+_t; U_t \mid G_{t-1})$ के वर्गमूल द्वारा नियंत्रित होता है। यह बैच CMI पहचान को अनुक्रमिक सेटिंग्स में सामान्य करता है, जो जनरलाइजेशन एरर को सेलेक्टर सूचना के कारणजन्य वृद्धों (causal increments) में विभाजित करता है।

2. बर्नस्टीन-टाइप परिशोधन (Bernstein-Type Refinement) (प्रमेय 3):
   एक बर्नस्टीन स्थिति (अतिरिक्त लॉस के कंडीशनल सेकंड मोमेंट पर एक सीमा) के तहत, लेखक एक "फास्ट-रेट" सीमा प्राप्त करते हैं जहाँ सूचना टर्म वर्गमूल के बजाय रैखिक रूप से प्रवेश करती है। यह तब अधिक सटीक सीमाएँ प्रदान करता है जब लॉस का वेरिएंस कम होता है।

3. विशिष्ट अनुक्रमिक समस्याओं पर अनुप्रयोग:

   • ऑनलाइन लर्निंग (सेक्शन 3.3): इस ढांचे को ऑनलाइन लर्निंग पर लागू किया गया है, जो SCMI को अनुक्रमिक रेडमेकर कॉम्प्लेक्सिटी और लिटलस्टोन डायमेंशन (Littlestone dimension) से जोड़ता है। पाथवाइज रियलाइजेबिलिटी (pathwise realizability) के तहत, SCMI का योग अनुक्रमिक पैटर्न ग्रोथ के लॉगरिदम द्वारा सीमित होता है, जो सूचना सीमा की एक कॉम्बिनेटोरियल व्याख्या प्रदान करता है।
   • स्ट्रीमिंग एक्टिव लर्निंग (सेक्शन 4): यह ढांचा इम्पोर्टेंस-वेटेड एक्टिव लर्निंग को संभालता है जहाँ क्वेरी निर्णय अनुकूलित होते हैं। प्रमाण-पक्ष विस्तार में क्वेरी कॉइन्स और लेबल मास्क शामिल हैं। लेखक टर्मिनल प्रेडिक्टर के पॉपुलेशन रिस्क के लिए एक सीमा प्राप्त करते हैं, जो यह दर्शाता है कि जनरलाइजेशन गैप इम्पोर्टेंस-वेटेड लॉस के SCMI द्वारा नियंत्रित होता है।
   • स्टोकेस्टिक मल्टी-आर्म्ड बैंडिट्स (सेक्शन 5): लेखक इस ढांचे को स्मूथिंग (एक्सपोनेंशियल वेट्स) वाले बैंडिट्स पर लागू करते हैं। यहाँ एक प्रमुख तकनीकी योगदान सेलेक्टर-तुलना सुधार (लेम्मा 12) है, जो आवश्यक है क्योंकि टर्मिनल पोस्टीरियर पूरे चयनित प्रक्षेपवक्र पर निर्भर करता है। अतीत को बनाए रखने वाले प्रमाण संदर्भ और बैंडिट गैप के विशिष्ट वेरिएंस गणना का उपयोग करके, वे एक रिग्रेट बाउंड प्राप्त करते हैं जिसमें $\sqrt{KT}$ हॉरिजन डिपेंडेंस होता है (लॉगरिदमिक और गैप-डिपेंडेंट कारकों तक)। यह मौजूदा PAC-Bayes बैंडिट बाउंड्स में सुधार करता है जो आमतौर पर $O(K^{1/3}T^{2/3})$ डिपेंडेंस प्रदर्शित करते हैं।

महत्व और दावे
लेखक का दावा है कि प्राथमिक योगदान एक कारणजन्य सुप्रासैंपल ढांचा विकसित करना है जो बैच CMI विश्लेषण को राउंडवाइज सेलेक्टर-सूचना वृद्धों के योग में बदल देता है। यह दृष्टिकोण:

• CMI बाउंड्स के लिए आवश्यक "घोस्ट-सैंपल" तुलना को बनाए रखता है जबकि अनुक्रमिक निर्णय लेने की कार्य-कारणता (causality) का सम्मान करता है।
• ऑनलाइन लर्निंग, एक्टिव लर्निंग और बैंडिट्स में जनरलाइजेशन का विश्लेषण करने के लिए एक एकीकृत टेम्पलेट प्रदान करता है।
• यह प्रदर्शित करता है कि SCMI, बैच CMI के अनुक्रमिक एनालॉग के रूप में कार्य करता है, जो लिटलस्टोन डायमेंशन जैसे कॉम्बिनेटोरियल कॉम्प्लेक्सिटी मेजर्स के साथ संबंध बनाए रखता है।
• वेरिएंस-अवेयर बर्नस्टीन बाउंड्स और एक नवीन सेलेक्टर-तुलना सुधार के एकीकरण के माध्यम से बैंडिट सेटिंग्स में बेहतर हॉरिजन डिपेंडेंस प्रदान करता है।

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