🤖 machine learning

Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

यह शोधपत्र एक एल्गोरिदम प्रस्तुत करके कॉन्टेक्स्टुअल बैंडिट्स (contextual bandits) के एक केंद्रीय खुले प्रश्न को हल करता है जो ओब्लिवियस एडवरसेरियल लॉस (oblivious adversarial losses) के तहत ग्राफिकल फीडबैक के साथ क्रॉस-लर्निंग के लिए इष्टतम $\widetilde O(\sqrt{\alpha T})$ रिग्रेट बाउंड प्राप्त करता है, जो प्रभावी रूप से उन ग्राफों के लिए भी संदर्भों (contexts) की संख्या पर बहुपद निर्भरता (polynomial dependencies) को हटा देता है जिनमें बिना सेल्फ-लूप वाले आर्म्स (arms without self-loops) शामिल हैं।

मूल लेखक: Ruiyuan Huang, Zengfeng Huang

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

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

CC BY 4.0

मूल लेखक: Ruiyuan Huang, Zengfeng Huang

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

कल्पना कीजिए कि आप एक उच्च-दांव वाला वीडियो गेम खेल रहे हैं जहाँ आपको हर सेकंड एक चुनाव करना होता है, लेकिन आप अभी तक लेवल के नियमों को नहीं जानते। आप केवल एक विकल्प चुनने के बाद ही यह सीखते हैं कि क्या हुआ और कभी-कभी गेम उन विकल्पों के परिणाम भी छिपा देता है जिन्हें आपने नहीं चुना। यह "कॉन्टेक्स्टुअल बैंडिट्स" (contextual bandits) की दुनिया है, जो कंप्यूटर विज्ञान की एक शाखा है जहाँ एल्गोरिदम परीक्षण और त्रुटि (trial and error) के माध्यम से सर्वोत्तम रणनीति सीखने की कोशिश करते हैं। अब, कल्पना कीजिए कि गेम और भी पेचीदा हो जाता है: आप न केवल अपनी गलतियों से सीखते हैं; आपको अपने दोस्तों की चालों के परिणामों पर भी नज़र रखने का मौका मिलता है, लेकिन केवल तभी जब वे एक विशिष्ट तरीके से आपसे "जुड़े" (connected) हों। यह "ग्राफिकल फीडबैक" (graphical feedback) है। अंत में, कल्पना कीजिए कि गेम हर बार खेलने पर अपने नियमों को थोड़ा बदल देता है, जो एक छिपे हुए "कॉन्टेक्स्ट" (जैसे दिन का समय या आपके चरित्र का मूड) पर आधारित होता है, लेकिन आप अगले गेम में मदद के लिए पिछले संस्करणों से सीखे गए सबक का उपयोग कर सकते हैं। यह "क्रॉस-लर्निंग" (cross-learning) है।

बड़ा सवाल जो वैज्ञानिक पूछ रहे हैं, वह यह है: यदि आपके पास इन विभिन्न गेम संस्करणों (कॉन्टेक्सट्स) का एक विशाल पुस्तकालय है, तो क्या आप संस्करणों की भारी संख्या से दबे बिना एक आदर्श रणनीति सीख सकते हैं? आमतौर पर, अधिक संस्करण होने से सीखने की प्रक्रिया धीमी और कठिन हो जाती है, जैसे कि एक ही मैप के बजाय दस लाख अलग-अलग मैप याद करने की कोशिश करना। शोधकर्ता जानना चाहते थे कि क्या कोई जादुई ट्रिक है जिससे आप संस्करणों की संख्या को अनदेखा कर सकें और ठीक उसी गति से सीख सकें जैसे कि केवल एक संस्करण हो, जबकि आप अपने दोस्तों से "झलक लेने" (peeking) की क्षमता का उपयोग भी कर सकें।

यह शोध पत्र, जिसे रुइयुआन हुआंग और जेंगफेंग हुआंग ने लिखा है, कहता है "हाँ, हम यह कर सकते हैं!" उन्होंने एक नया एल्गोरिदम डिज़ाइन किया है जो एक सुपर-स्मार्ट जासूस की तरह काम करता है। यह तीन जटिल विचारों को जोड़ने की पहेली को हल करता है—विभिन्न कॉन्टेक्स्ट से सीखना, पड़ोसियों की चालों पर नज़र रखना, और पेचीदा, बदलते नियमों का सामना करना—बिना कॉन्टेक्स्ट की संख्या से धीमा हुए। लेखकों ने गणितीय रूप से सिद्ध किया कि उनका तरीका काम करता है, भले ही खेल एक चालाक प्रतिद्वंद्वी (एडवर्सरियल लॉसेस) द्वारा बिगाड़ा गया हो और नियम सख्त हों। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने एक कठोर गणितीय प्रमाण बनाया, जिसे उन्होंने 'लीन' (Lean) नामक एक कंप्यूटर-सत्यापित भाषा में भी अनुवादित किया, जिसमें हर कदम की शुद्धता सुनिश्चित करने के लिए 1,000,000 से अधिक लाइनों का कोड शामिल था। उनके प्रयोग दिखाते हैं कि यह नया तरीका पिछले प्रयासों की तुलना में काफी तेजी से सीखता है, और यह गेम की जटिलता के साथ पूरी तरह से स्केल (scale) करता है न कि विवरणों में फंस जाता है।

जासूस की दुविधा: बहुत सारे मैप, बहुत कम सुराग

आइए उस समस्या को समझें जिसे लेखकों ने हल किया है। कल्पना कीजिए कि आप एक ऑनलाइन नीलामी में बोली लगाने वाले (bidder) हैं। हर दिन, आपके पास किसी वस्तु के लिए एक गुप्त मूल्य (आपका "कॉन्टेक्स्ट") होता है, और आपको अनुमान लगाना होता है कि कितनी बोली लगानी है। यदि आप बहुत कम बोली लगाते हैं, तो आप हार जाते हैं और आपको कोई जानकारी नहीं मिलती। यदि आप जीतने के लिए पर्याप्त ऊंची बोली लगाते हैं, तो आप उच्चतम हारने वाली बोली देखते हैं। लेकिन यहाँ दिलचस्प बात यह है: भले ही आप हार जाएं, आप यह पता लगा सकते हैं कि यदि आपने थोड़ी अधिक बोली लगाई होती तो क्या होता। आप इस जानकारी का उपयोग यह अनुमान लगाने के लिए भी कर सकते हैं कि यदि आपके दोस्त (जिनका गुप्त मूल्य अलग है) ने बोली लगाई होती तो क्या होता।

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

"स्पेशल आर्म" की समस्या

लेखकों ने एक ऐसी चाल का पता लगाया जिसने पिछले शोधकर्ताओं को उलझा दिया था। कुछ खेलों में, ऐसे "आर्म्स" (विकल्प) होते हैं जिनमें "सेल्फ-लूप" (self-loop) नहीं होता है। सरल शब्दों में, इसका मतलब है कि यदि आप इस विशिष्ट विकल्प को चुनते हैं, तो आप यह नहीं देख पाते कि यदि आपने इसे फिर से चुना होता तो क्या होता। आप परिणाम केवल तभी देखते हैं जब कोई और इसे चुनता है।

कल्पना कीजिए कि एक खेल है जहाँ एक विशिष्ट कार्ड, "जोकर", पेचीदा है। यदि आप जोकर खेलते हैं, तो गेम आपको यह नहीं बताता कि यदि आपने जोकर को फिर से खेला होता तो आप जीतते या हारते। आपको केवल तभी पता चलता है जब आपका प्रतिद्वंद्वी जोकर खेलता है। यदि आपकी रणनीति जोकर को बहुत अधिक खेलने का निर्णय लेती है, तो गेम इसके बारे में बताना बंद कर देता है, और आप अंधे हो जाते हैं। पिछले तरीके यहाँ संघर्ष करते थे क्योंकि वे शोर (noise) में खोए बिना जोकर के बारे में कैसे सीखें, यह नहीं समझ पा रहे थे।

समाधान: "फ्रीज एंड स्प्लिट" (Freeze and Split) ट्रिक

लेखकों का एल्गोरिदम, जिसे वे कुछ शानदार अपग्रेड के साथ "FTRL" (फॉलो-द-रेगुलराइज्ड-लीडर) विधि कहते हैं, इसे एक चतुर तीन-चरणीय नृत्य के साथ हल करता है:

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

परिणाम: तेज़ और घातक

लेखकों ने सिद्ध किया कि उनकी नई विधि एक ऐसा "रिग्रेट" (यह मापने का तरीका कि आपने आदर्श रणनीति की तुलना में कितना बुरा प्रदर्शन किया) प्राप्त करती है जो राउंड्स की संख्या ( $T$ ) के वर्गमूल और ग्राफ की जटिलता ( $\alpha$ ) के वर्गमूल के लगभग बराबर होता है। महत्वपूर्ण रूप से, यह दर कॉन्टेक्स्ट की संख्या ( $M$ ) पर निर्भर नहीं करती है।

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

यह क्यों मायने रखता है

यह केवल नीलामी जीतने के बारे में नहीं है। "सेंसर्ड फीडबैक" (जहाँ आप सब कुछ नहीं देख पाते) से कुशलतापूर्वक सीखने की क्षमता, कई अलग-अलग स्थितियों में बहुत बड़ी है, जैसे कि:

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

लेखकों ने केवल यह सुझाव नहीं दिया कि यह काम कर सकता है; उन्होंने इसके समर्थन में एक कठोर गणितीय प्रमाण और एक कंप्यूटर-सत्यापित सत्यापन प्रदान किया। उन्होंने दिखाया कि सही प्रकार की "झलक लेने" की क्षमता को सही तरह के तरीके से जोड़ने से, हम कितनी भी अलग स्थितियाँ सामने आएँ, तेज़ी से और समझदारी से सीख सकते हैं। यह कंप्यूटर को दुनिया से सीखने के लिए प्रशिक्षित करने की दिशा में एक बड़ा कदम है।

तकनीकी सारांश: ग्राफिकल फीडबैक के साथ क्रॉस-लर्निंग कॉन्टेक्स्टुअल बैंडिट्स के लिए लगभग टाइट बाउंड्स

1. समस्या सेटअप

यह शोध पत्र ग्राफिकल फीडबैक के साथ क्रॉस-लर्निंग कॉन्टेक्स्टुअल बैंडित्स को संबोधित करता है, जो तीन अलग-अलग शिक्षण प्रतिमानों (learning paradigms) का एक संयोजन है:

कॉन्टेक्स्टुअल बैंडिट्स (Contextual Bandits): शिक्षार्थी (learner) अज्ञात वितरण $\nu$ (जो $[M]$ के एक परिमित सेट पर है) से प्राप्त i.i.d. संदर्भ $c_t$ के अनुक्रमों का सामना करता है।
ग्राफिकल फीडबैक (Graphical Feedback): शिक्षार्थी एक भुजा (arm) $a_t$ चुनता है और न केवल चुनी गई भुजा के नुकसान (loss) को देखता है, बल्कि एक निश्चित, ज्ञात निर्देशित फीडबैक ग्राफ $G = ([K], E)$ में उसकी आउट-नेबरों (out-neighbors) के नुकसान को भी देखता है।
क्रॉस-लर्निंग (Cross-Learning): महत्वपूर्ण रूप से, फीडबैक "पुन: प्रयोज्य" (reusable) है। संदर्भ $c_t$ में भुजा $a$ के नुकसान को देखने से शिक्षार्थी को किसी भी संदर्भ $c \in [M]$ के तहत भुजा $a$ के काउंटरफैक्चुअल लॉस का मूल्यांकन करने की अनुमति मिलती है।

माना जाता है कि फीडबैक ग्राफ $G$ स्ट्रॉन्गली ऑब्जर्वेबल (strongly observable) है: प्रत्येक भुजा या तो स्वयं की लूप (self-loop) रखती है या अन्य सभी भुजाओं द्वारा देखी जाती है (अर्थात, $N_{in}(a) = [K] \setminus \{a\}$ )। लक्ष्य एक ओब्लिवियस एडवर्सरी (oblivious adversary) के विरुद्ध अपेक्षित रिग्रेट (expected regret) को कम करना है, जो लॉस टेबल्स $\ell_{t,c}(a) \in [0,1]$ को अग्रिम रूप से निर्धारित करता है, जबकि एडवर्सरी को शिक्षार्थी के रैंडमाइजेशन (randomization) का ज्ञान नहीं होता।

केंद्रीय प्रश्न: क्या एक एल्गोरिदम $\tilde{O}(\sqrt{\alpha T})$ का रिग्रेट बाउंड प्राप्त कर सकता है—जहाँ $\alpha$ ग्राफ का इंडिपेंडेंस नंबर है और $T$ क्षितिज (horizon) है—बिना संदर्भों की संख्या $M$ पर एक बहुपद निर्भरता (polynomial dependence) के? पिछले कार्यों ने गैर-कॉन्टेक्स्टुअल ग्राफिकल बैंडिट्स और बिना ग्राफ वाले क्रॉस-लर्निंग के लिए यह दर स्थापित की थी, लेकिन संयुक्त सेटिंग अभी भी खुली थी, विशेष रूप से उन ग्राफों के लिए जिनमें बिना सेल्फ-लूप वाली भुजाएं शामिल हैं।

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

प्रस्तावित एल्गोरिदम फॉलो-द-रेगुलराइज्ड-लीडर (FTRL) का उपयोग करता है जिसमें नेगेटिव एंट्रॉपी रेगुलराइजेशन है, जिसे अज्ञात संदर्भ वितरण और ग्राफिकल फीडबैक की विशिष्ट चुनौतियों को संभालने के लिए एक एपॉक-आधारित निर्माण (epoch-based construction) के साथ एकीकृत किया गया है।

मुख्य तकनीकी घटक:

एपॉक निर्माण और रिजेक्शन सैंपलिंग (Epoch Construction and Rejection Sampling):
अज्ञात वितरण $\nu$ को संभालने के लिए, एल्गोरिदम समय को एपॉक्स (epochs) में विभाजित करता है। प्रत्येक एपॉक के भीतर, यह एक निश्चित लक्ष्य वितरण को परिभाषित करने के लिए दो एपॉक पहले के FTRL पॉलिसी के "विलंबित स्नैपशॉट" (delayed snapshot) का उपयोग करता है। यह शिक्षार्थी को एक निश्चित वितरण से खेलने का अनुकरण करने के लिए रिजेक्शन सैंपलिंग का उपयोग करने की अनुमति देता है। यह तकनीक खेलने के लिए उपयोग की जाने वाली पॉलिसी को अनुमान के लिए उपयोग किए जाने वाले डेटा से अलग करती है, जिससे यह सुनिश्चित होता है कि अवलोकन संभावनाओं (observation probabilities) का अनुमान लगाने के लिए उपयोग किए गए संदर्भ वर्तमान पॉलिसी के प्रक्षेपवक्र (trajectory) से स्वतंत्र और ताज़ा हैं।
बिना सेल्फ-लूप वाली भुजाओं को संभालना (The Special Arm):
ग्राफिकल बैंडिट्स में एक प्राथमिक बाधा वह भुजा है जिसमें सेल्फ-लूप नहीं है, क्योंकि इसकी अवलोकन संभावना (observation probability) घट सकती है यदि शिक्षार्थी इसे बार-बार खेलता है। एल्गोरिदम प्रत्येक एपॉक में एक "विशेष भुजा" $j_e$ की पहचान करता है (यदि कोई हो) जिसका बिना सेल्फ-लूप वाली भुजाओं के बीच उच्चतम अनुभवजन्य द्रव्यमान (empirical mass) होता है।
- पेसिमिस्टिक करेक्शन (Pessimistic Correction): विशेष भुजा के लॉस एस्टीमेट में एक बायस टर्म $\beta / W_e(j_e)$ जोड़ा जाता है। यह अप्रत्यक्ष अन्वेषण (implicit exploration) के कारण होने वाले प्रथम-क्रम अनुमानित ड्रिफ्ट (first-order estimation drift) को रद्द करता है (जो कम देखी जाने वाली भुजाओं के लॉस को कम आंकता है)।
- लॉस ट्रांसलेशन (Loss Translation): यह रोकने के लिए कि स्क्वेयर्ड करेक्शन टर्म FTRL विश्लेषण में अनियंत्रित क्वाड्रेटिक लागत पेश न करे, एल्गोरिदम विशेष भुजा के इनपुट को सभी कोऑर्डिनेट से घटा देता है। यह ट्रांसलेशन FTRL इटरेट को अपरिवर्तित रखता है लेकिन यह सुनिश्चित करता है कि विशेष भुजा स्थानीय नॉर्म (local norm) में शून्य योगदान दे, जिससे क्वाड्रेटिक लागत शेष भुजाओं की ओर स्थानांतरित हो जाती है।
रैंडम डिनोमिनेटर और जॉइंट स्टेबिलिटी (Random Denominator and Joint Stability):
चूंकि अवलोकन संभावना अनुमानित मानों के हर (denominator) में दिखाई देते हैं, और पॉलिसी इन अनुमानों पर निर्भर करती है, इसलिए प्रक्षेपवक्र और डिनोमिनेटर सह-संबंधित (correlated) होते हैं। विश्लेषण एक पॉपुलेशन-डिनोमिनेटर स्यूडो-एस्टीमेटर (population-denominator pseudo-estimator) और एक आदर्श प्रक्षेपवक्र (ideal trajectory) पेश करता है। स्नैपशॉट और सेलेक्टर पर कंडीशनिंग लगाकर, प्रमाण को कोऑर्डिनेट-वार स्केलर रैंडम-डिनोमिनेटर मोमेंट बाउंड्स लागू करता है और एक जॉइंट सॉफ्टमैक्स प्रोडक्ट-स्टेबिलिटी इनइक्वेलिटी (joint Softmax product-stability inequality) का उपयोग करता है ताकि सह-संबंधित प्रक्षेपवक्र त्रुटियों को बिना यह माने कि भुजाओं के बीच स्वतंत्रता है, मार्जिनल सेकंड मोमेंट्स के योग में बदला जा सके।

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

संदर्भ-स्वतंत्र रिग्रेट प्रश्न का समाधान: यह शोध पत्र एक ऐसा एल्गोरिदम प्रदान करता है जो i.i.d. संदर्भों और ओब्लिवियस एडवर्सियल लॉस के लिए अपेक्षित रिग्रेट $\tilde{O}(\sqrt{\alpha T})$ प्राप्त करता है। यह बाउंड संदर्भों की संख्या $M$ से स्वतंत्र है (लॉगारिदमिक कारकों को छोड़कर), जो गैर-कॉन्टेक्स्टुअल स्ट्रॉन्गली ऑब्जर्वेबल ग्राफिकल बैंडिट्स के मिनिमैक्स रेट से मेल खाता है।
सभी स्ट्रॉन्गली ऑब्जर्वेबल ग्राफों में सामान्यीकरण: पिछले परिणाम जो अक्सर सेल्फ-लूप वाली भुजाओं की आवश्यकता रखते थे, उनके विपरीत, यह विधि उन ग्राफों को संभालती है जिनमें बिना सेल्फ-लूप वाली भुजाएं होती हैं। यह उस विशिष्ट कठिनाई को संबोधित करता है जहाँ बिना सेल्फ-लूप वाली भुजा पर उच्च-संभावना से खेलना, अवलोकन संभावना को शून्य कर देता है।
डिपेंडेंट एस्टिमेटर्स के लिए नवीन विश्लेषण: यह कार्य क्रॉस-लर्निंग की उपस्थिति में अनुकूलित पॉलिसी और अनुभवजन्य अवलोकन संभावनाओं के बीच सहसंबंध को संभालने के लिए एक "रैंडम-डिनोमिनेटर और जॉइंट-स्टेबिलिटी" विश्लेषण ढांचे को विकसित करता है।
औपचारिकीकरण (Formalization): मुख्य प्रमेय को Lean में औपचारिक रूप से सत्यापित किया गया है, जिसमें 100,000 से अधिक लाइनों का एंड-टू-एंड विकास किया गया है, जो जटिल संभाव्यता तर्कों की शुद्धता सुनिश्चित करता है।

4. परिणाम

सैद्धांतिक गारंटी: एल्गोरिदम $\tilde{O}(\sqrt{\alpha T})$ का रिग्रेट बाउंड प्राप्त करता है। छिपे हुए कारक $M, K,$ और $T$ में लॉगरिदमिक हैं। यह पुष्टि करता है कि जटिल ग्राफिकल फीडबैक की उपस्थिति में भी क्रॉस-लर्निंग प्रभावी रूप से संदर्भ स्थान के आकार $M$ पर निर्भरता को समाप्त कर सकती है।
प्रायोगिक सत्यापन: नियंत्रित सिंथेटिक प्रयोगों से पता चलता है कि एल्गोरिदम उन बेसलाइन से बेहतर प्रदर्शन करता है जो केवल ग्राफ फीडबैक या केवल क्रॉस-लर्निंग का उपयोग करते हैं। परिणाम क्षितिज $T$ और इंडिपेंडेंस नंबर $\alpha$ दोनों के संबंध में अनुमानित स्क्वायर-रूट स्केलिंग प्रदर्शित करते हैं।
मजबूती (Robustness): यह विधि तब भी सही ढंग से कार्य करती है जब संदर्भ वितरण अज्ञात होता है, जो 'वार्म-अप' परिदृश्यों की तुलना में एक महत्वपूर्ण सुधार है जहाँ $\nu$ को ज्ञात माना जाता है।

5. महत्व

यह शोध पत्र स्ट्रक्चर्ड फीडबैक वाले कॉन्टेक्स्टुअल बैंडिट्स के क्षेत्र में एक केंद्रीय खुले प्रश्न को हल करने का दावा करता है। ओब्लिवियस एडवर्सियल लॉस के तहत संदर्भ-स्वतंत्र दर $\tilde{O}(\sqrt{\alpha T})$ प्राप्त करने योग्य होने को सिद्ध करके, यह कार्य ग्राफिकल बैंडिट्स की सैद्धांतिक सीमाओं और रिपीटेड फर्स्ट-प्राइस ऑक्शन जैसे व्यावहारिक अनुप्रयोगों की आवश्यकताओं के बीच के अंतर को पाटता है, जहाँ फीडबैक सेंसर (censored) है लेकिन पुन: प्रयोज्य है।

इसका महत्व दोहरा है:

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

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