Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

तकनीकी सारांश: डिकपल्ड बैंडिट्स के लिए फॉलो-द-पर्टर्बड-लीडर (Follow-the-Perturbed-Leader)

समस्या सेटिंग
यह शोध पत्र डिकपल्ड मल्टी-आर्म्ड बैंडिट (MAB) समस्या को संबोधित करता है, जो एक ऐसी सेटिंग है जहाँ शिक्षार्थी (learner) प्रत्येक दौर $t$ में दो अलग-अलग आर्म्स (arms) चुनता है: शोषण (exploitation) के लिए एक आर्म $i_t$ (जो हानि $\ell_{t, i_t}$ का सामना करता है लेकिन उसे देखता नहीं है) और अन्वेषण (exploration) के लिए एक आर्म $j_t$ (जो हानि $\ell_{t, j_t}$ को देखता है लेकिन उसका सामना नहीं करता है)। यह ढांचा अल्ट्रा-वाइडबैंड संचार प्रणालियों (ट्रांसमिशन चैनल से भिन्न चैनल को सेंस करना) और रोबोटिक्स में सिम-टू-रियल ट्रांसफर जैसे परिदृश्यों को मॉडल करता है। लक्ष्य छद्म-पछतावा (pseudo-regret) को कम करना है, जिसे शिक्षार्थी के शोषण विकल्पों द्वारा किए गए संचयी नुकसान और पश्चदृष्टि (hindsight) में सर्वश्रेष्ठ स्थिर आर्म के बीच के अंतर के रूप में परिभाषित किया गया है।

यह शोध पत्र बेस्ट-ऑफ-बोथ-वर्ल्ड्स (BOBW) गारंटी को लक्षित करता है, जिसका उद्देश्य निम्नलिखित प्राप्त करना है:

1. एडवर्सियल रिजीम (adversarial regime) (जहाँ हानियाँ एक अनुकूलित प्रतिपक्षी द्वारा निर्धारित होती हैं) में $O(\sqrt{KT})$ का इष्टतम पछतावा (optimal regret)।
2. स्टोकेस्टिकली कंस्ट्रेंड एडवर्सरियल (SCA) रिजीम (जिसमें मानक स्टोकेस्टिक सेटिंग शामिल है) में $O(K/\Delta_{\min})$ का निकट-इष्टतम, समय-स्वतंत्र पछतावा, जहाँ $\Delta_{\min}$ न्यूनतम उप-इष्टतमता अंतराल (suboptimality gap) है।

कार्यप्रणाली (Methodology)
लेखक फॉलो-द-पर्टर्बड-लीडर (FTPL) ढांचे पर आधारित एक नई नीति प्रस्तावित करते हैं, जिसे विशेष रूप से डिकपल्ड सेटिंग्स में मौजूदा BOBW नीतियों की कम्प्यूटेशनल बाधाओं को दूर करने के लिए डिज़ाइन किया गया है।

• शोषण रणनीति (Exploitation Strategy): शिक्षार्थी एक विक्षेपित संचयी हानि अनुमान (perturbed cumulative loss estimate) को न्यूनतम करके शोषण आर्म $i_t$ चुनता है:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  जहाँ $\hat{L}_{t,i}$ अनुमानित संचयी हानि है, $\eta_t$ लर्निंग रेट है, और $r_{t,i}$ एक पारेटो वितरण (Pareto distribution) $P_\alpha$ से लिए गए i.i.d. रैंडम पर्टर्बेशन्स हैं, जिसका शेप पैरामीटर $\alpha > 1$ है। यह पर्टर्बेशन प्रकार $\beta$-Tsallis-INF नीति (जहाँ $\alpha = 1/(1-\beta)$) के अनुरूप है, जो BOBW गारंटी प्राप्त करने के लिए जानी जाती है।

• अन्वेषण रणनीति (Exploration Strategy - मुख्य नवाचार): मानक FTPL बैंडिट एल्गोरिदम में, एक निष्पक्ष इम्पॉर्टेंस-वेटेड (IW) लॉस एस्टीमेट बनाने के लिए आमतौर पर यह जानना आवश्यक होता है कि आर्म $i$ चुनने की सटीक प्रायिकता $w_{t,i}$ क्या है। डिकपल्ड बैंडिट्स में, अन्वेषण प्रायिकता $p_{t,i}$ को $w_{t,i}$ के आधार पर सेट किया जाना चाहिए। हालाँकि, FTPL $w_{t,i}$ के लिए कोई क्लोज्ड-फॉर्म अभिव्यक्ति प्रदान नहीं करता है (FTRL के विपरीत), और जियोमेट्रिक रीसैंपलिंग के माध्यम से पूर्ण वेक्टर का अनुमान लगाना कम्प्यूटेशनल रूप से महंगा ($O(K^2)$ या अधिक) है।
  इसे हल करने के लिए, लेखक एक सरोगेट प्रायिकता (surrogate probability) $q_{t,i}$ पेश करते हैं जिसे बिना रीसैंपलिंग या कॉनवेक्स ऑप्टिमाइज़ेशन के सीधे वर्तमान हानि अनुमानों से कंप्यूट किया जा सकता है:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  जहाँ $\sigma_{t,i}$ सभी आर्म्स के बीच $\hat{L}_{t,i}$ का रैंक है। अन्वेषण आर्म $j_t$ को फिर नॉर्मलाइज्ड डिस्ट्रीब्यूशन $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$ के अनुसार चुना जाता है। यह दृष्टिकोण वास्तविक $w_{t,i}$ मानों की आवश्यकता के बिना BOBW गारंटी के लिए आवश्यक सैद्धांतिक गुणों को बनाए रखते हुए किया जाता है।

मुख्य योगदान

1. डिकपल्ड बैंडिट्स के लिए प्रथम FTPL-आधारित BOBW नीति: यह शोध पत्र पहली ऐसी नीति प्रस्तुत करता है जो डिकपल्ड बैंडिट्स में बिना कॉनवेक्स ऑप्टिमाइज़ेशन समस्याओं को हल किए (जो Decoupled-Tsallis-INF जैसे FTRL-आधारित दृष्टिकोणों के लिए आवश्यक है) या रीसैंपलिंग प्रक्रियाओं (जो आमतौर पर FTPL प्रायिकता अनुमान के लिए आवश्यक होती है) का उपयोग किए बिना BOBW गारंटी प्राप्त करती है।
2. कम्प्यूटेशनल दक्षता: पूर्ण प्रायिकता वेक्टर गणना को कुशलतापूर्वक गणना योग्य सरोगेट $q_{t,i}$ से बदलकर, प्रस्तावित नीति प्रति-चरण कम्प्यूटेशनल जटिलता को कम करती है। जबकि लॉस अनुमानों को सॉर्ट करने में $O(K \log K)$ समय लगता है, लेखक नोट करते हैं कि एक अनुकूलित कार्यान्वयन रैंक परिवर्तनों को वृद्धिशील (incrementally) रूप से ट्रैक करके $O(K)$ अपडेट प्राप्त कर सकता है। यह FTRL नीतियों के विपरीत है जिन्हें प्रत्येक चरण पर पुनरावृत्ति (iterative) कॉनवेक्स ऑप्टिमाइज़ेशन (जैसे न्यूटन विधि) की आवश्यकता होती है।
3. सैद्धांतिक गारंटी:
   • एडवर्सियल रिजीम: नीति $O(\sqrt{KT})$ पछतावा सीमा प्राप्त करती है, जो डिकपल्ड बैंडिट्स के लिए ज्ञात लोअर बाउंड से मेल खाती है।
   • स्टोकेस्टिक/SCA रिजीम: नीति $O(K/\Delta_{\min})$ का पछतावा प्राप्त करती है (विशेष रूप से $\alpha=3$ के लिए $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$), जो इष्टतम के निकट है और मानक स्टोकेस्टिक बैंडिट्स के टाइम-डिपेंडेंट बाउंड्स में सुधार करता है।

परिणाम

• सैद्धांतिक: शोध पत्र कठोर प्रमाण (स्थिरता और दंड पदों में पछतावा अपघटन के माध्यम से) प्रदान करता है जो दिखाता है कि सरोगेट प्रायिकता $q_{t,i}$ वास्तविक शोषण प्रायिकता के पर्याप्त करीब है ताकि आवश्यक पछतावा सीमाओं को बनाए रखा जा सके।
• अनुभवजन्य (Empirical): सिंथेटिक डेटा (एडवर्सियल और स्टोकेस्टिक दोनों रिजीम में) और MovieLens 100K डेटासेट का उपयोग करके एक वास्तविक दुनिया के सिमुलेशन पर प्रयोगों से पता चलता है कि प्रस्तावित FTPL नीति:
  • मौजूदा BOBW नीतियों (Decoupled-Tsallis-INF/FTRL और EXP3) की तुलना में कम संचयी पछतावा प्राप्त करती है।
  • बेहतर कम्प्यूटेशनल दक्षता प्रदर्शित करती है। एडवर्सियल रिजीम में, प्रस्तावित नीति FTRL-आधारित बेसलाइन्स की तुलना में काफी तेज़ चलती है। $K=64$ के लिए, FTRL का रनटाइम अनुपात FTPL की तुलना में लगभग 1363 गुना धीमा देखा गया था।
  • आर्म्स की संख्या $K$ के साथ प्रभावी ढंग से स्केल करती है, और विभिन्न गैप साइज $\Delta$ केAcross मजबूती बनाए रखती है।

महत्व और दावे
शोध पत्र का दावा है कि इसका प्राथमिक योगदान डिकपल्ड बैंडिट्स के संदर्भ में FTRL-आधारित BOBW नीतियों की सैद्धांतिक इष्टतमता और FTPL की कम्प्यूटेशनल दक्षता के बीच के अंतर को पाटना है। कॉनवेक्स ऑप्टिमाइज़ेशन और रीसैंपलिंग की आवश्यकता को समाप्त करके, प्रस्तावित विधि FTPL को पछतावा प्रदर्शन से समझौता किए बिना अपनी दक्षता लाभों को पूरी तरह से साकार करने की अनुमति देती है। लेखक सुझाव देते हैं कि सटीक प्रायिकता वेक्टर के स्थान पर कुशलतापूर्वक गणना योग्य सरोगेट प्रायोंताओं का उपयोग करने की तकनीक, FTPL के अलावा अन्य एल्गोरिथमिक फ्रेमवर्क (जैसे कि Prod परिवार) में भी लागू की जा सकती है, जिससे व्यापक बैंडिट सेटिंग्स में बेहतर कम्प्यूटेशनल दक्षता संभव हो सकती है। यह कार्य उन व्यावहारिक अनुप्रयोगों द्वारा प्रेरित है जहाँ प्रति-चरण कम्प्यूटेशनल लेटेंसी (latency) महत्वपूर्ण है, जैसे संचार प्रणाली और रोबोटिक्स।