तकनीकी सारांश: ट्री-गाइडेड आइडेंटिफ़ाई-देन-एक्सप्लॉइट (TG-ITE)

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

यह शोध पत्र कंडोरसेट विजेता (Condorcet winner) धारणा के तहत $N$-आर्म स्टोकेस्टिक ड्यूलिंग बैंडिट्स (N-armed stochastic dueling bandits) की समस्या को संबोधित करता है। इस सेटिंग में, एक शिक्षार्थी (learner) भुजाओं (arms) के जोड़े $(i, j)$ चुनता है और एक बाइनरी परिणाम देखता है जो यह दर्शाता है कि कौन सी भुजा जीती, जो एक अज्ञात प्राथमिकता मैट्रिक्स $P$ द्वारा नियंत्रित होती है। मुख्य धारणा एक अद्वितीय कंडोरसेट विजेता $a^\star$ के अस्तित्व की है, जहाँ $P(a^\star, j) > 1/2$ सभी $j \neq a^\star$ के लिए सत्य है, जबकि गैर-विजेता भुजाओं के बीच प्राथमिकताएँ चक्रीय (cyclic) हो सकती हैं।

यह अध्ययन तीन अलग-अलग उद्देश्यों को एक ही ढांचे के भीतर एकीकृत करने पर केंद्रित है:

1. सर्वश्रेष्ठ भुजा पहचान (Best Arm Identification - BAI): उच्च विश्वास ($1-\delta$) के साथ $a^\star$ को एक डेटा-निर्भर स्टॉपिंग टाइम पर वापस करना।
2. कमजोर पछतावा न्यूनीकरण (Weak Regret Minimization): उस संचयी पछतावे (cumulative regret) को कम करना जहाँ एक दौर में शून्य पछतावा तब होता है जब चुनी गई दो भुजाओं में से कम से कम एक $a^\star$ हो।
3. मजबूत पछतावा न्यूनीकरण (Strong Regret Minimization): उस पछतावे को कम करना जहाँ एक दौर में शून्य पछतावा केवल तभी होता है जब चुनी गई दोनों भुजाएँ $a^\star$ हों (स्व-खेल/self-play)।

मुख्य शोध प्रश्न यह है कि क्या एक एकीकृत एल्गोरिद्मिक ढांचा तीनों उद्देश्यों के लिए समान रूप से इष्टतम प्रदर्शन प्राप्त करने के लिए क्या संभव है, जो अन्वेषण (exploration - जो BAI के लिए आवश्यक है) और दोहन (exploitation - जो पछतावा न्यूनीकरण के लिए आवश्यक है) के बीच पारंपरिक ट्रेड-ऑफ को पार कर सके।

कार्यप्रणाली: ट्री-गाइडेड आइडेंटिफ़ाई-देन-एक्सप्लॉइट (TG-ITE)

प्रस्तावित समाधान, TG-ITE, एक आइडेंटिफ़ाई-देन-एक्सप्लॉइट (Identify-Then-Exploit) प्रतिमान को अपनाता है। यह समस्या को एक साझा पहचान चरण (identification phase) और उसके बाद उद्देश्य-विशिष्ट दोहन रणनीतियों में विभाजित करता है।

1. साझा पहचान प्रिमिटिव (Shared Identification Primitive): TREEASCENT

मुख्य नवाचार एक ट्री-गाइडेड आइडेंटिफिकेशन एल्गोरिदम है जिसे TREEASCENT कहा जाता है। मानक "एक्सप्लोर-देन-कमिट" (ETC) रणनीतियों के विपरीत, जो अक्सर संचयी पछतावे में उप-इष्टतम होती हैं, TREEASCENT कंडोरसेट विजेता की खोज के लिए मार्गदर्शन करने हेतु एक नियत (deterministic), संतुलित बाइनरी ट्री संरचना का उपयोग करता है।

• तंत्र (Mechanism): एक मनमाने भुजा $b$ से शुरू करते हुए, एल्गोरिदम एक निश्चित बाइनरी ट्री के पूर्वज पथ (ancestor path) पर चलता है। प्रत्येक स्तर $h$ पर, यह एक प्रतिनिधि खोजने के लिए एक "सिबलिंग ब्लॉक" (sibling block) की भुजाओं पर नॉकआउट टूर्नामेंट (knockout tournament) आयोजित करता है।
• विलय (Merging): सिबलिंग ब्लॉक से प्राप्त प्रतिनिधि की तुलना फिर एक अनुक्रमिक युग्म परीक्षण (DUELTEST) का उपयोग करके वर्तमान "चैंपियन" (पिछले स्तर का विजेता) के विरुद्ध की जाती है।
• दक्षता (Efficiency): सिबलिंग ब्लॉक्स के आकार (ज्यामितीय रूप से बढ़ते आकार) के अनुपात में कॉन्फिडेंस बजट आवंटित करके, एल्गोरिदम $O(N)$ सैंपल कॉम्प्लेक्सिटी के साथ एक उच्च-विश्वास दावेदार की पहचान करता है। यह केवल कंडोरसेट विजेता के अस्तित्व और एक वैश्विक अंतर $\Delta$ पर भरोसा करते हुए, स्ट्रॉन्ग स्टोकेस्टिक ट्रांसिटिविटी या स्टोकेस्टिक ट्रायंगल इनइक्वालिटी जैसी अधिक मजबूत धारणाओं की आवश्यकता के बिना प्राप्त किया जाता है।

2. उद्देश्य-विशिष्ट दोहन रणनीतियाँ (Objective-Specific Exploitation Strategies)

एक बार जब TREEASCENT के माध्यम से एक उच्च-विश्वास दावेदार की पहचान कर ली जाती है, तो ढांचा विशिष्ट दोहन नीतियों में बदल जाता है:

• BAI के लिए (TG-ITE-BAI): एल्गोरिदम बस TREEASCENT चलाता है और पहचाने गए हाथ को वापस करने पर रुक जाता है। यह $O(N)$ सैंपल कॉम्प्लेक्सिटी प्राप्त करता है, जो BAI के लिए सैद्धांतिक निचली सीमा (lower bound) से मेल खाता है।
• कमजोर पछतावे के लिए (TG-ITE-WEAK): एल्गोरिदम एक प्रारंभिक विजेता खोजने के लिए TREEASCENT को एक निरंतर-कॉन्फिडेंस "वार्म स्टार्ट" के रूप में उपयोग करता है। इसके बाद यह SCREENANDREPLACE नामक एक विजेता-बना-रहता-है (Winner-Stays) शैली की रणनीति का उपयोग करता है। प्रत्येक एपोक (epoch) में, वर्तमान दावेदार की सभी चुनौतियों के विरुद्ध स्क्रीनिंग की जाती है। यदि कोई चुनौती दावेदार को हराती हुई प्रतीत होती है, तो एक प्रतिस्थापन टूर्नामेंट आयोजित किया जाता है। यह दृष्टिकोण $O(N)$ कमजोर पछतावा प्राप्त करता है, जो पिछले $O(N \log N)$ परिणामों में सुधार करता है।
• मजबूत पछतावे के लिए (TG-ITE-STRONG): एल्गोरिदम TREEASCENT के माध्यम से एक विश्वसनीय दावेदार की पहचान करता है और फिर स्व-खेल (self-play) (दावेदार की स्वयं के विरुद्ध तुलना) में संलग्न होता है।
  • ज्ञात क्षितिज (Known Horizon): $1/(H+1)$ कॉन्फिडेंस के साथ TREEASCENT चलाएं, फिर स्व-खेल करें।
  • एनीटाइम क्षितिज (Anytime Horizon): तेजी से बढ़ते स्व-खेल ब्लॉकों के साथ तेजी से बढ़ते कॉन्फिडेंस वाले पहचान चरणों को बारी-बारी से चलाएं।
  • यह $O(N \log T)$ मजबूत पछतावा प्राप्त करता है, जो विशेषीकृत मजबूत-पछतावा एल्गोरिदम से मेल खाता है।

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

1. एकीकृत ढांचा (Unified Framework)

TG-ITE पहला ढांचा है जो एक साझा पहचान प्रिमिटिव का उपयोग करके ड्यूलिंग बैंडिट्स में BAI, कमजोर पछतावा और मजबूत पछतावे को एकीकृत करता है। यह प्रदर्शित करता है कि ड्यूलिंग बैंडिट सेटिंग में पहचान और पछतावा न्यूनीकरण के बीच का ट्रेड-ऑफ "सौम्य" (benign) है क्योंकि एक भुजा का उपयोग अन्वेषण के लिए और दूसरी का दोहन के लिए किया जा सकता है।

2. बेहतर सैंपल कॉम्प्लेक्सिटी और पछतावा सीमाएँ

• BAI: बिना किसी स्ट्रॉन्ग स्टोकेस्टिक ट्रांसिटिविटी या टोटल ऑर्डर धारणा की आवश्यकता के $O(N)$ सैंपल कॉम्प्लेक्सिटी प्राप्त करता है, जो BAI के सर्वोत्तम ज्ञात परिणामों से मेल खाता है।
• कमजोर पछतावा: $O(N)$ कमजोर पछतावा प्राप्त करता है, जो पिछले संयुक्त अनुकूलन दृष्टिकोणों (जैसे मा एट अल., 2025) में पाए गए $O(\log N)$ अंतराल को पाटता है और सर्वोत्तम इंस्टेंस-इंडिपेंडेंट बाउंड्स से मेल खाता है।
• मजबूत पछतावा: $O(N \log T)$ पछतावा प्राप्त करता है, जो WS-S और RUCB जैसे विशेषीकृत एल्गोरिदम के बराबर है।
• संयुक्त अनुकूलन: यह ढांचा ड्यूलिंग बैंडित्स में BAI और कमजोर पछतावे का एक साथ अनुकूलन करने की अनुमति देता है, दोनों के लिए $O(N)$ गारंटी प्राप्त करता है, जिससे पिछले कार्यों में मौजूद उप-इष्टतम $O(\log N)$ कारकों को समाप्त किया जा सकता है।

3. सैद्धांतिक गारंटी

शोध पत्र TREEASCENT और उसके बाद के दोहन चरणों की शुद्धता और लागत के लिए कठोर प्रमाण प्रदान करता है।

• प्रमेय 1 (Theorem 1): TREEASCENT $O(N)$ तुलनाओं का उपयोग करके $1-\epsilon$ प्रायिकता के साथ कंडोरसेट विजेता की पहचान करता है।
• प्रमेय 2 (Theorem 2): TG-ITE-WEAK का कमजोर पछतावा $O(N/\Delta^2)$ द्वारा सीमित है, जो $N$ में रैखिक है और समय क्षितिज $T$ से स्वतंत्र है।
• प्रमेय 3 और 4 (Theorem 3 & 4): ज्ञात और अज्ञात दोनों क्षितिजों के लिए मजबूत पछतावा सीमाएँ $O(N \log T)$ हैं।

4. विस्तार (Extensions)

शोध पत्र एक ज्ञात-गैप बजटेड एक्सटेंशन (अनुभाग 5) भी प्रस्तुत करता है। यदि कंडोरसेट गैप $g$ का निचला स्तर ज्ञात है, तो एल्गोरिदम एनीटाइम DUELTEST को एक निश्चित-बजट परीक्षण से बदल सकता है। यह $\log(1/\Delta)$ कारक को हटाकर, नियत तुलना बजट और कड़े गारंटी प्रदान करता है, हालांकि इसके लिए गैप के पूर्व ज्ञान की आवश्यकता होती है।

प्रयोगात्मक सत्यापन (Experimental Validation)

लेखक सिंथेटिक उदाहरणों पर प्रतिनिधि बेसलाइनों (जिसमें WS-W, WS-S, RUCB, WR-TINF, और WSW-PE शामिल हैं) के विरुद्ध TG-ITE का मूल्यांकन करते हैं, जिन्हें गैर-पारस्परिकता (non-transitivity) और असममित अंतराल (asymmetric gaps) का परीक्षण करने के लिए डिज़ाइन किया गया है।

• BAI स्केलिंग: TG-ITE-BAI, $N$ के साथ लगभग रैखिक रूप से स्केल करता है, जो चक्रीय उदाहरणों पर एडेप्टिव पेयरवाइज एलिमिनेशन विधियों से बेहतर प्रदर्शन करता है।
• कमजोर पछतावा: TG-ITE-WEAK सबसे कम संचयी पछतावा प्राप्त करता है और जल्दी से स्थिर (plateau) हो जाता है, जो वार्म-स्टार्ट रणनीति की प्रभावकारिता को प्रदर्शित करता है।
• मजबूत पछतावा: TG-ITE-STRONG महत्वपूर्ण रूप से बेसलाइनों से बेहतर प्रदर्शन करता है, और स्व-खेल शुरू होने के बाद वक्र समतल हो जाता है, जो इसके सैद्धांतिक $O(N \log T)$ व्यवहार की पुष्टि करता है।

महत्व और दावे

शोध पत्र दावा करता है कि TG-ITE इस बात का सैद्धांतिक प्रमाण प्रदान करता है कि ड्यूलिंग बैंडिट्स में बेस्ट आर्म आइडेंटिफिकेशन और पछतावा न्यूनीकरण के बीच का ट्रेड-ऑफ अपेक्षाकृत सौम्य है। ड्यूलिंग बैंडिट्स की अनूठी संरचना (दो भुजाओं का चयन करना) का लाभ उठाते हुए, यह ढांचा सफलतापूर्वक पहचान और दोहन चरणों को बिना किसी उप-इष्टतमता के अलग करने में सफल होता है, जैसा कि मानक मल्टी-आर्म्ड बैंडिट्स में देखा जाता है।

लेखक इस बात पर जोर देते हैं कि उनका दृष्टिकोण:

1. एक साझा, पुन: प्रयोज्य पहचान प्रिमिटिव (TREEASCENT) का उपयोग करके तीन अलग-अलग उद्देश्यों को एकीकृत करता है।
2. कुल क्रम (total order) की धारणा को शिथिल करके और $O(\log N)$ कारक को हटाकर कमजोर पछतावे के लिए अत्याधुनिक (state-of-the-art) परिणामों में सुधार करता है।
3. उन मजबूत संरचनात्मक धारणाओं (जैसे स्ट्रॉन्ग स्टोकेस्टिक ट्रांसिटिविटी) की आवश्यकता के बिना इष्टतम दरों से मेल खाता है जिन पर पिछले इष्टतम एल्गोरिदम निर्भर थे।

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