📊 statistics

Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

यह शोध पत्र सिंगल-पॉलिसी कंसेंट्रैबिलिटी के तहत फॉरवर्ड-केएल (forward-KL) रेगुलाइजेशन वाले ऑफलाइन कॉन्टेक्स्टुअल बैंडिट्स के लिए पहले $\tilde{O}(\epsilon^{-1})$ फास्ट सैंपल कॉम्प्लेक्सिटी अपर बाउंड्स स्थापित करता है, जो एक नवीन कॉनवेक्स-एनालिटिकल विश्लेषण के माध्यम से टैबुलर और जनरल फंक्शन एप्रोक्सिमेशन सेटिंग्स को एकीकृत करता है और मैचिंग लोअर बाउंड्स के माध्यम से इन दरों की टाइटनेस को सिद्ध करता है।

मूल लेखक: Qingyue Zhao, Kaixuan Ji, Heyang Zhao, Quanquan Gu

प्रकाशित 2026-05-12

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

CC BY 4.0

मूल लेखक: Qingyue Zhao, Kaixuan Ji, Heyang Zhao, Quanquan Gu

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

मुख्य विचार: एक नोटबुक से रोबोट को सिखाना

कल्पना कीजिए कि आप एक रोबोट को वीडियो गेम खेलना सिखाने की कोशिश कर रहे हैं। आप रोबोट को लाइव गेम नहीं खेलने देते (जो कि "ऑनलाइन लर्निंग" होगा)। इसके बजाय, आप उसे एक नोटबुक देते हैं जिसमें एक विशिष्ट खिलाड़ी (मान लीजिए "प्लेयर X") के गेम खेलने की रिकॉर्डिंग भरी हुई है। यह ऑफलाइन लर्निंग (Offline Learning) है।

आपका लक्ष्य केवल प्लेयर X की नोटबुक के आधार पर रोबốt के लिए सबसे अच्छे मूव्स (चालों) का पता लगाना है।

समस्या: "फॉरवर्ड-केएल" (Forward-KL) पहेली

आधुनिक एआई (AI) में, हम अक्सर रोबोट को पागल होने से रोकने के लिए एक विशेष गणितीय नियम का उपयोग करते हैं जिसे रेगुलराइजेशन (Regularization) कहा जाता है। यह एक पट्टे (leash) की तरह काम करता है, जो रोबोट के व्यवहार को प्लेयर X की शैली के करीब रखता है।

इस पट्टे को पकड़ने के दो तरीके हैं:

रिवर्स केएल (Reverse KL - "मोड-सीकिंग" पट्टा): यह एक लोकप्रिय तरीका है। यह रोबोट को बताता है, "वह कुछ भी न करें जो प्लेयर X ने नहीं किया।" यदि प्लेयर X कभी नहीं कूदा, तो रोबोट कूदने से डरता है।
फॉरवर्ड केएल (Forward KL - "मास-कवरिंग" पट्टा): यह वह तरीका है जिस पर यह पेपर केंद्रित है। यह रोबोट को बताता है, "आपको उस सभी ज़मीन को कवर करना होगा जिसे प्लेयर X ने कवर किया था।" यदि प्लेयर X एक संकीर्ण रास्ते पर चला, तो रोबोट को भी उस रास्ते पर चलना होगा, लेकिन वह उस रास्ते को खाली नहीं छोड़ सकता।

रहस्य:
वैज्ञानिकों को पहले से पता था कि "रिवर्स केएल" पट्टा बहुत कुशल था। वे रोबोट को अपेक्षाकृत छोटी नोटबुक (जिसे "फास्ट रेट" या $\epsilon^{-1}$ कहा जाता है) के साथ लगभग पूर्ण बनाने के लिए सिखा सकते थे।

हालाँकि, "फॉरवर्ड केएल" पट्टे के लिए, पिछले गणित ने सुझाव दिया कि यह बहुत धीमा और अनाड़ी था। ऐसा लग रहा था कि समान परिणाम प्राप्त करने के लिए आपको चार गुना बड़ी नोटबुक (एक "स्लो रेट" या $\epsilon^{-2}$ ) की आवश्यकता होगी। बड़ा सवाल यह था: क्या फॉरवर्ड केएल वास्तव में धीमा है, या हमारे पास इसे मापने के लिए गलत गणितीय उपकरण थे?

समाधान: सफलता को मापने का एक नया तरीका

इस पेपर के लेखक कहते हैं: "यह पट्टा नहीं है; यह हमारा मापने वाला टेप है।"

उन्होंने फॉरवर्ड केएल पट्टे का विश्लेषण करने के लिए एक बिल्कुल नया गणितीय टूलकिट विकसित किया है। इसे एक रूलर (रैली) से लेजर स्कैनर में बदलने जैसा समझें।

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

परिणाम: रोबोट की गति बढ़ाना

अपने नए "लेजर स्कैनर" का उपयोग करके, लेखकों ने दो प्रमुख बातें सिद्ध कीं:

1. हमें बड़ी नोटबुक की आवश्यकता नहीं है
उन्होंने सिद्ध किया कि फॉरवर्ड केएल पट्टे के साथ, आपको एक विशाल नोटबुक की आवश्यकता नहीं है। आप रिवर्स केएल विधि के समान "फास्ट रेट" ( $\epsilon^{-1}$ ) प्राप्त कर सकते हैं। इसका अर्थ है कि आप पहले की तुलना में कम डेटा के साथ उच्च गुणवत्ता वाले एआई मॉडल को प्रशिक्षित कर सकते हैं।

2. "सिंगल-पॉलिसी" का रहस्य
ऑफलाइन लर्निंग में, कॉन्सेंट्रैबिलिटी (Concentrability) की एक अवधारणा है। यह पूछती है: "क्या नोटबुक सबसे अच्छे संभावित मूव्स को कवर करती है?"

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

"फेज़ ट्रांजिशन" ट्विस्ट

पेपर ने एक दिलचस्प "टिपिंग पॉइंट" भी पाया।

मजबूत पट्टा (उच्च रेगुलराइजेशन): यदि आप पट्टे को कसकर खींचते हैं (उच्च रेगुलराइजेशन), तो रोबोट बहुत तेज़ी से सीखता है, ठीक वैसे ही जैसे रिवर्स केएल विधि।
कमजोर पट्टा (कम रेगुलराइजेशन): यदि आप पट्टे को बहुत ढीला छोड़ देते हैं, तो रोबोट पुरानी, धीमी गति ( $\epsilon^{-2}$ ) पर वापस चला जाता है।

यह पुष्टि करता है कि फॉरवर्ड केएल, रिवर्स केएल के समान व्यवहार करता है: यह तेज़ होता है जब नियम सख्त होते हैं, लेकिन यदि नियम बहुत ढीले हों तो धीमा हो जाता है।

एक वाक्य में सारांश

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

यहाँ "Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability" शोध पत्र का विस्तृत तकनीकी सारांश दिया गया है।

समस्या विवरण (Problem Statement)

यह शोध पत्र कॉन्टेक्स्टुअल बैंडिट्स (CBs) में ऑफलाइन लर्निंग की सांख्यिकीय दक्षता (statistical efficiency) को संबोधित करता है, जब सीखने का उद्देश्य फॉरवर्ड-कुलबैक-लीब्लर (Forward-KL) रेगुलराइजेशन से संबंधित हो। उद्देश्य फलन (objective function) को इस प्रकार परिभाषित किया गया है:
$J_{FKL}(\pi) := \mathbb{E}[r] - \eta^{-1} \text{KL}(\pi_{\text{ref}} \| \pi)$
जहाँ $r$ रिवॉर्ड (reward) है, $\eta$ इनवर्स रेगुलराइजेशन इंटेंसिटी है, और $\pi_{\text{ref}}$ एक रेफरेंस (व्यवहार संबंधी) पॉलिसी है।

जबकि रिवर्स-KL रेगुलराइजेशन ( $\text{KL}(\pi \| \pi_{\text{ref}})$ ) का व्यापक अध्ययन किया गया है और सिंगल-पॉलिसी कॉन्सेंट्रैबिलिटी (जहाँ व्यवहार पॉलिसी केवल इष्टतम पॉलिसी को कवर करती है) के तहत इसे $\tilde{O}(\epsilon^{-1})$ सैंपल कॉम्प्लेक्सिटी (फास्ट रेट्स) प्राप्त करने में सक्षम दिखाया गया है, फॉरवर्ड-KL का मामला एक खुला प्रश्न बना हुआ है। फॉरवर्ड-KL के लिए मौजूदा विश्लेषण या तो लागू नहीं होते या $\tilde{O}(\epsilon^{-2})$ जैसे धीमे (slow) रेट्स देते हैं। इसके अतिरिक्त, यह स्पष्ट नहीं है कि क्या सिंगल-पॉलिसी कॉन्सेंट्रैबिलिटी फॉरवर्ड-KL के लिए पर्याप्त है, क्योंकि फॉरवर्ड-KL एक "मास-कवरिंग" (mass-covering) प्रकृति का है (जो $\pi \to 0$ होने पर दंड देता है जहाँ $\pi_{\text{ref}} > 0$ ) न कि "मोड-सीकिंग" (mode-seeking), जिससे संभावित रूप से अधिक मजबूत कवरेज धारणाओं की आवश्यकता हो सकती है।

यह शोध पत्र दो मुख्य प्रश्नों का उत्तर देने का प्रयास करता है:

फॉरवर्ड-KL रेगुलराइज्ड उद्देश्यों के लिए निर्णय लेने की सांख्यिकीय दर (statistical rate) क्या है?
क्या सिंगल-पॉलिसी कॉन्सेंट्रैबिलिटी इस सेटिंग में रेट-ऑप्टिमल ऑफलाइन लर्निंग के लिए पर्याप्त है?

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

लेखक फॉरवर्ड-KL-रेगुलराइज्ड पेसिमिस्टिक कॉन्टेक्स्टुअल बैंडिट्स (FKL-PCB) के लिए एक सुव्यवस्थित विश्लेषण प्रस्तावित करते हैं। यह कार्यप्रणाली पिछले कार्यों से काफी भिन्न है जो टेलर एक्सपेंशन (Taylor expansions) और मीन वैल्यू थ्योरम (Mean Value Theorem - MVT) पर निर्भर करते हैं।

1. पारंपरिक MVT-आधारित विश्लेषण का खंडन:
रेगुलराइज्ड उद्देश्यों का विश्लेषण करने वाले पिछले कार्य अक्सर सबऑप्टिमलिटी गैप (suboptimality gap) को डीकंपोज करने के लिए एक मध्यवर्ती बिंदु $\bar{u}$ के आसपास टेलर एक्सपेंशन (MVT के माध्यम से) का उपयोग करते हैं। रिवर्स-KL के लिए, परिणामी पद पेसिमिज्म के तहत एक मोनोटोनिसिटी गुण प्रदर्शित करते हैं जो सिंगल-प性和 कॉन्सेंट्रैबिलिटी का उपयोग करके त्रुटि को बांधने की अनुमति देते है।
हालाँकि, लेखक (लेम्मा 5.3 के माध्यम से) यह प्रदर्शित करते हैं कि फॉरवर्ड-KL के लिए, सबऑप्टिमलिटी डीकंपोजिशन टर्म का डेरिवेटिव एक सेंटर्ड रैंड वेरिएबल के "टिल्टेड स्क्यूनेस" (tilted skewness) को शामिल करता है। इस डेरिवेटिव का साइन अनिश्चित (indefinite) है, जिसका अर्थ है कि मोनोटोनिसिटी तर्क विफल हो जाता है। फलस्वरूप, मानक MVT-आधारित प्रक्रियाएं मजबूत (ऑल-पॉलिसी) कॉन्सेंट्रैबिलिटी धारणाओं का सहारा लिए बिना फास्ट रेट्स प्राप्त नहीं कर सकतीं।

2. कॉनवेक्स-एनालिटिकल पाइपलाइन (Convex-Analytical Pipeline):
MVT की सीमाओं को दरकिनार करने के लिए, लेखक कॉनवेक्स कंजुगेट्स (convex conjugates) और ब्रेगमैन डायवर्जेंस (Bregman divergences) पर आधारित एक नवीन प्रमाण तकनीक पेश करते हैं:

ड्यूल पर्सपेक्टिव (Dual Perspective): वे प्रोबेबिलिटी सिम्प्लेक्स पर अपने कॉनवेक्स कंजुगेट के माध्यम से रेगुलराइज्ड उद्देश्य का लक्षण वर्णन करते हैं।
सेल्फ-बाउंडिंग तर्क (Self-Bounding Argument): वे एक सबऑप्टिमलिटी गैप के लिए एक पहचान (identity) व्युत्पन्न करते हैं (लेम्मा 5.5) जो त्रुटि को सीधे वास्तविक रिवॉर्ड और पेसिमिस्टिक अनुमान के बीच के वर्ग अंतर के रूप में व्यक्त करता है, जिसे रेफरेंस पॉलिसी के सापेक्ष ऑप्टिमल पॉलिसी के अनुपात द्वारा भारित (weighted) किया गया है।
मुख्य पहचान (Key Identity): मुख्य तकनीकी योगदान निम्नलिखित असमानता है:
$\text{SubOpt}_{FKL}(\hat{\pi}) \leq 2\eta \sum_{a} \frac{(\pi^*_{FKL}(a))^2}{\pi_{\text{ref}}(a)} (r(a) - \hat{r}(a))^2$
यह बाउंड केवल सिंगल-पॉलिसी कॉन्सेंट्रैबिलिटी गुणांक $C_{\pi^*} = \sup \frac{\pi^*}{\pi_{\text{ref}}}$ पर निर्भर करता है, जिससे ऑल-पॉलिसी कॉन्सेंट्रैबिलिटी की आवश्यकता समाप्त हो जाती है।

3. एल्गोरिदम डिज़ाइन:
यह शोध पत्र टैबुलर और फंक्शन एप्रोक्सिमेशन दोनों सेटिंग्स के लिए एक पेसिमिस्टिक एल्गोरिदम, FKL-PCB प्रस्तुत करता है:

एस्टिमेशन (Estimation): रिवॉर्ड फंक्शन का अनुमान लगाने के लिए लीस्ट-स्क्वायर्स (least-squares) का उपयोग करता है।
पेसिमिज्म (Pessimism): यह सुनिश्चित करने के लिए एक पेनल्टी टर्म (कॉन्फिडेंस बाउंड) घटाता है कि अनुमानित रिवॉर्ड $\hat{r}$ , उच्च प्रायिकता के साथ वास्तविक रिवॉर्ड $r$ से कम हो।
ऑप्टिमाइजेशन (Optimization): उस पॉलिसी को आउटपुट करता है जो पेसिमिस्टिक रेगुलराइज्ड ऑब्जेक्ट को मैक्सिमाइज करती है।

मुख्य योगदान और परिणाम (Key Contributions and Results)

1. फास्ट सैंपल कॉम्प्लेक्सिटी अपर बाउंड्स:
यह शोध पत्र सिंगल-पॉलिसी कॉन्सेंट्रैबिलिटी के तहत फॉरवर्ड-KL रेगुलराइज्ड ऑफलाइन CBs के लिए पहले $\tilde{O}(\epsilon^{-1})$ सैंपल कॉम्प्लेक्सिटी बाउंड्स स्थापित करता है:

टैबुलर सेटिंग: $\tilde{O}\left( \eta (C_{\pi^*})^2 |S||A| \epsilon^{-1} \right)$ ।
फंक्शन एप्रोक्सिमेशन: $\tilde{O}\left( \eta C_{\pi^*} D^2_{\pi^*} \log N_G \epsilon^{-1} \right)$ , जहाँ $D^2_{\pi^*}$ एक $D^2$ -टाइप का कॉन्सेंट्रैबिलिटी गुणांक है और $N_G$ फंक्शन क्लास का कवरिंग नंबर है।
ये परिणाम अमीनियन एट अल. (2025) के $\tilde{O}(\epsilon^{-2})$ बाउंड की तुलना में बेहतर हैं और ऑल-पॉलिसी कॉन्सेंट्रैबिलिटी की आवश्यकता को सिंगल-पॉलिसी कॉन्सेंट्रैबिलिटी में शिथिल (relax) करते हैं।

2. मिनिमैक्स लोअर बाउंड्स (Minimax Lower Bounds):
लेखक अपने अपर बाउंड्स की सटीकता दिखाने के लिए मिलान वाले लोअर बाउंड्स प्रदान करते हैं:

टैबुलर लोअर बाउंड: हाई-रेगुलराइजेशन रिजीम में $\Omega(\eta |S||A| \epsilon^{-1})$ । यह $\eta$ पर रैखिक निर्भरता और $1/\epsilon$ दर की पुष्टि करता है कि वे इष्टतम हैं।
फेज़ ट्रांजिशन (Phase Transition): लोअर बाउंड्स रिवर्स-KL के समान एक "फेज़ ट्रांजिशन" प्रकट करते हैं। लो-रेगुलराइजेशन रिजीम (बड़ा $\eta$ ) में, सैंपल कॉम्प्लेक्सिटी वापस धीमे $\tilde{O}(\epsilon^{-2})$ रेट पर चली जाती है, जो इंगित करती है कि फास्ट रेट्स प्राप्त करने के लिए रेगुलराइजेशन आवश्यक है।

3. तकनीकी नवीनता:
शोध पत्र का दावा है कि "कॉनवेक्स-एनालिटिकल पाइपलाइन" टैबुलर और फंक्शन एप्रोक्सिमेशन सेटिंग्स को एकीकृत करती है और पूरी तरह से मीन वैल्यू थ्योरम पर आधारित प्रमाण प्रक्रियाओं को दरकिनार करती है। इस दृष्टिकोण को अन्य डायवर्जेंस-रेगुलराइज्ड निर्णय लेने वाली समस्याओं के विश्लेषण के लिए स्वतंत्र महत्व के रूप में प्रस्तुत किया गया है।

महत्व और दावे (Significance and Claims)

यह शोध पत्र ऑफलाइन लर्निंग में फॉरवर्ड-KL रेगुलराइजेशन के लिए सांख्यिकीय दरों को सटीक रूप से चरित्रित करने वाला पहला कार्य होने का दावा करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

एक खुले प्रश्न का समाधान: यह सवाल को हल करता है कि क्या फॉरवर्ड-KL के लिए सिंगल-पॉलिसी कॉन्सेंट्रैबिलिटी पर्याप्त है, और फास्ट रेट्स के साथ सकारात्मक उत्तर देता है।
एकीकृत सिद्धांत (Unifying Theory): यह प्रदर्शित करता है कि फॉरवर्ड-KL की "मास-कवरिंग" प्रकृति, यदि एक नवीन विश्लेषणात्मक दृष्टिकोण का उपयोग किया जाए, तो स्वाभाविक रूप से रिवर्स-KL की "मोड-सीकिंग" प्रकृति से अधिक मजबूत कवरेज धारणाओं की आवश्यकता नहीं रखती है।
एल्गोरिद्मिक सरलता: यह दिखाता है कि एक न्यूनतमिस्ट पेसिमिज्म-आधारित एल्गोरिदम (FKL-PCB) इन इष्टतम दरों को प्राप्त करने के लिए पर्याप्त है, जिसमें जटिल एल्गोरिद्मिक संशोधनों की आवश्यकता नहीं है।

लेखक भविष्य की दिशाओं के संबंध में विनम्र रहते हैं, यह नोट करते हुए कि जबकि उन्होंने पर्याप्तता (sufficiency) स्थापित की है, मल्टी-आर्म्ड बैंडिट्स में भी फॉरवर्ड-KL के लिए सिंगल-पॉलिसी कॉन्सेंट्रैबिलिटी की आवश्यकता (necessity) अभी भी एक खुला प्रश्न है। इसके अतिरिक्त, फंक्शन एप्रोक्सिमेशन में $D^2$ -टाइप की कॉन्सेंट्रैबिलिटी के लिए विशेष रूप से मिलान वाला लोअर बाउंड प्राप्त करना भविष्य के कार्य के लिए छोड़ दिया गया है।