📊 statistics

A single algorithm for both restless and rested rotting bandits

यह शोध पत्र रोटिंग अडैप्टिव विंडो यूसीबीबी (RAW-UCB) को प्रस्तुत करता है, जो एक नवीन एल्गोरिदम है जो विशिष्ट वातावरण या रिवॉर्ड डिके (पुरस्कार क्षय) की प्रकृति के पूर्व ज्ञान की आवश्यकता के बिना, रेस्टेड और रेस्टलेस रोटिंग बैंडिट सेटिंग्स दोनों में निकट-इष्टतम रिग्रेट प्राप्त करता है।

मूल लेखक: Julien Seznec, Pierre Ménard, Alessandro Lazaric, Michal Valko

प्रकाशित 2026-04-24

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

CC BY 4.0

मूल लेखक: Julien Seznec, Pierre Ménard, Alessandro Lazaric, Michal Valko

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

कल्पना कीजिए कि आप एक फूड ट्रक चला रहे हैं जिसके मेनू में 10 अलग-अलग व्यंजन हैं। आपका लक्ष्य यह पता लगाना है कि ग्राहक किस व्यंजन को सबसे ज्यादा पसंद करते हैं ताकि आप सबसे अधिक भोजन बेच सकें। यह एक क्लासिक "मल्टी-आर्म्ड बैंडिट" (Multi-Armed Bandit) समस्या है: आपको नए व्यंजनों को परखने के लिए एक्सप्लोरिंग (खोजबीन करने) और उस व्यंजन का एक्सप्लॉइटिंग (उपयोग करने) के बीच संतुलन बनाना होगा जिसे आप वर्तमान में सबसे अच्छा मानते हैं।

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

मुख्य समस्या: "खराब होने वाला" मेनू

इस परिदृश्य में, हर बार जब आप कोई व्यंजन परोसते हैं, तो उसकी लोकप्रियता थोड़ी कम हो जाती है।

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

बड़ी चुनौती:
पहले, कंप्यूटर वैज्ञानिकों का मानना था कि इन दोनों स्थितियों के लिए पूरी तरह से अलग रणनीतियों की आवश्यकता होती है।

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

यह समुद्र में मछली पकड़ने के लिए डिज़ाइन किए गए जाल का उपयोग आकाश में पक्षियों को पकड़ने के लिए करने जैसा है। उपकरण फिट नहीं बैठते।

समाधान: "एडेप्टिव विंडो" (Adaptive Window - RAW-UCB)

लेखक RAW-UCB (रॉटिंग एडेप्टिव विंडो अपर कॉन्फिडेंस बाउंड) नामक एक नया एल्गोरिदम पेश करते हैं।

RAW-UCB को एक अति-बुद्धिमान, अनुकूलन योग्य शेफ के रूप में सोचें जिसे रसोई के नियमों को पहले से जानने की आवश्यकता नहीं है।

"विंडो" (खिड़की) का उदाहरण:
कल्प-ना कीजिए कि आप एक कमरे के औसत तापमान का अनुमान लगाने की कोशिश कर रहे हैं।

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

यह दोनों के लिए क्यों काम करता है:

"रेस्टलेस" दुनिया में (समय क्षय): एल्गोरिदम यह महसूस करता है कि समय बीतने के कारण पुराना डेटा कम प्रासंगिक है। यह हालिया डेटा देखने के लिए स्वाभाविक रूप से अपनी विंडो को छोटा कर देता है।
"रेस्टेड" दुनिया में (क्रिया क्षय): एल्गोरिदम को एहसास होता है कि यदि किसी व्यंजन को कुछ समय से नहीं परोसा गया है, तो उसका "सड़ना" रुक गया है। वह यह देखने के लिए पुराने डेटा का उपयोग कर सकता है कि वह व्यंजन थकने से पहले कैसा था।

यह एक गिरगिट की तरह है जो पर्यावरण के अनुसार अपना रंग बदल लेता है, बिना आपके उसे यह बताए कि वातावरण क्या है।

"असंभव" मिश्रण

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

हालाँकि, यदि आप ऐसी दुनिया में हैं जहाँ चीजें केवल खराब होती हैं (कभी बेहतर नहीं होतीं), तो RAW-UCB नायक है।

वास्तविक दुनिया के परिणाम: Yahoo! News टेस्ट

कागज पर गणित साबित करने के बजाय, लेखकों ने Yahoo! Front Page (एक न्यूज़ रिकमेंडेशन डेटासेट) के वास्तविक डेटा पर RAW-UCB का परीक्षण किया।

परिदृश्य: उन्होंने एक न्यूज़ फीड का अनुकरण किया जहाँ लेख समय के साथ कम दिलचस्प हो जाते हैं (Restless) या बहुत अधिक क्लिक होने पर (Rested)।
प्रतिस्पर्धा: उन्होंने RAW-UCB को Exp3.S (एक सामान्यज्ञ) और GLR-UCB (एक विशेषज्ञ) जैसे प्रसिद्ध एल्गोरिदम के खिलाफ खड़ा किया।
परिणाम: RAW-UCB लगातार जीता। यह इतनी अच्छी तरह से अनुकूलित हुआ कि इसे यह बताने की आवश्यकता नहीं थी कि "हे, यह एक न्यूज़ फीड है!" या "हे, यह एक संगीत प्लेलिस्ट है!" इसने बस इसे समझ लिया और दूसरों की तुलना में तेज़ी से बेहतर सिफारिशें करना शुरू कर दिया।

संक्षेप में सारांश

समस्या: चीजें समय के साथ खराब होती हैं, या तो समय बीतने के कारण या आपके द्वारा उनके उपयोग के कारण। पुराने एल्गोरिदम केवल एक प्रकार के "खराब होने" को संभाल सकते थे।
नवाचार: एक नया एल्गोरिदम (RAW-UCB) एक लचीले लेंस की तरह काम करता है। यह स्वचालित रूप से तय करता है कि निर्णय लेने के लिए कितना "इतिहास" देखना है, चाहे क्षय समय के कारण हो या उपयोग के कारण।
लाभ: यह एक "वन-साइज़-फिट्स-ऑल" समाधान है जो पहले के तरीकों की तुलना में तेज़, सरल और अधिक सटीक है, जो इसे Spotify, Netflix या न्यूज़ फीड जैसे वास्तविक दुनिया के ऐप्स के लिए आदर्श बनाता है जहाँ उपयोगकर्ता की रुचि कम हो जाती है।

संक्षेप में, RAW-UCB निर्णय लेने के लिए एक यूनिवर्सल रिमोट कंट्रोल है, उस दुनिया में जहाँ सब कुछ अंततः थोड़ा पुराना और उबाऊ हो जाता है।

यहाँ जूलियन सेज़नेक और अन्य द्वारा लिखित शोध पत्र "A single algorithm for both restless and rested rotting bandits" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा (Problem Definition)

यह शोध पत्र मल्टी-आर्म्ड बैंडिट (MAB) समस्या को उन गैर-स्थिर (non-stationary) वातावरणों में संबोधित करता है जहाँ किसी क्रिया (action) का अपेक्षित प्रतिफल (expected reward) समय के साथ घटता जाता है। इस घटना को "रॉटिंग" (rotting - सड़ना/घटना) कहा जाता है, जो दो अलग-अलग सेटिंग्स में होती है:

रेस्टेड रॉटिंग बैंडिट्स (Rested Rotting Bandits): एक आर्म का प्रतिफल केवल तभी घटता है जब उस आर्म को खींचा (pull किया) जाता है (जैसे, बार-बार मिलने वाले सुझावों से उपयोगकर्ता की बोरियत)। यहाँ क्षय (decay) खिंचने की संख्या $n$ का एक फलन (function) है।
रेस्टलेस रॉटिंग बैंडिट्स (Restless Rotting Bandits): एक आर्म का प्रतिफल समय के साथ घटता रहता है, चाहे उसे खींचा जाए या नहीं (जैसे, समाचार लेखों का पुराना या अप्रासंगिक होना)। यहाँ क्षय समय $t$ का एक फलन है।

मुख्य चुनौती: पिछला साहित्य इन दोनों को मौलिक रूप से भिन्न समस्याओं के रूप में देखता था। रेस्टलेस बैंडिट्स के लिए डिज़ाइन किए गए एल्गोरिदम (जो मानते हैं कि प्रतिफल क्रियाओं से स्वतंत्र रूप से बदलते हैं) रेस्टेड सेटिंग्स में खराब प्रदर्शन करते थे, और इसके विपरीत भी। इसके अलावा, यह एक खुला प्रश्न था कि क्या कोई एकल एल्गोरिदम बिना क्षय के प्रकार, परिवर्तन के परिमाण, या समय सीमा (time horizon) के पूर्व ज्ञान के, दोनों सेटिंग्स में निकट-इष्टतम (near-optimal) रिग्रेट प्राप्त कर सकता है।

लेखक प्रतिफल फलनों $\mu_i(t, n)$ को $t$ और $n$ दोनों में गैर-बढ़ते (non-increasing) के रूप में परिभाषित करते हैं। वे यह भी स्थापित करते हैं कि यदि प्रतिफल को बढ़ने (non-monotonic) की अनुमति दी जाती, तो मिश्रित सेटिंग में कोई भी एल्गोरिदम उप-रैखिक (sub-linear) रिग्रेट प्राप्त नहीं कर पाता। हालाँकि, घटने (decreasing) की धारणा के तहत, वे सिद्ध करते हैं कि एक एकीकृत दृष्टिकोण संभव है।

2. कार्यप्रणाली: RAW-UCB (Methodology: RAW-UCB)

लेखक रॉटिंग एडेप्टिव विंडो UCB (RAW-UCB) का प्रस्ताव करते हैं, जो एक नवीन इंडेक्स-आधारित एल्गोरिदम है जो रेस्टेड और रेस्टलेस रॉटिंग बैंडिट्स के उपचार को एकीकृत करता है।

मुख्य तंत्र (Core Mechanism)

एक वैश्विक औसत या निश्चित स्लाइडिंग विंडो का उपयोग करने वाले मानक UCB एल्गोरिदम के विपरीत, RAW-UCB प्रत्येक आर्म के लिए उसके अपर कॉन्फिडेंस बाउंड (UCB) की गणना करने के लिए एक अनुकूलित "विंडो आकार" $h$ का चयन करता है।

इंडेक्स गणना (Index Calculation): समय $t$ पर प्रत्येक आर्म $i$ के लिए, एल्गोरिदम प्रत्येक संभावित विंडो आकार $h$ (1 से लेकर आर्म को खींचे जाने की कुल संख्या तक) के लिए UCB इंडेक्स की गणना करता है:
$\text{ind}(i, t) = \min_{h \le N_{i,t-1}} \left( \hat{\mu}^h_i(t) + c(h, \delta_t) \right)$
जहाँ $\hat{\mu}^h_i(t)$ पिछले $h$ खिंचवों का अनुभवजन्य औसत (empirical average) है, और $c(h, \delta_t)$ कॉन्फिडेंस रेडियस है।
चयन (Selection): जिस आर्म का इंडेक्स न्यूनतम (minimum) होता है, उसे चुना जाता है।
- न्यूनतम क्यों? चूँकि प्रतिफल घट रहे हैं (rotting), वास्तविक भविष्य का मूल्य पिछले $h$ खिंचवों के औसत द्वारा सीमित होता है। सभी $h$ के लिए न्यूनतम मान लेकर, एल्गोरिदम प्रभावी रूप से वर्तमान मूल्य पर सबसे कड़ा (सबसे रूढ़िवादी) ऊपरी बाउंड पाता है, जिससे उन आर्म्स के चयन को रोका जा सके जो पुराने, उच्च-मूल्य वाले खिंचवों के कारण अच्छे दिख रहे थे लेकिन अब घट चुके हैं।

कुशल कार्यान्वयन (Efficient Implementation)

नैव (naive) कार्यान्वयन की जटिलता प्रति राउंड $O(t)$ है। लेखक EFF-RAW-UCB पेश करते हैं, जो विंडो आकारों के एक ज्यामितीय ग्रिड ( $h, mh, m^2h, \dots$ ) और एक लेज़ी अपडेट तंत्र का उपयोग करता है। यह समय और स्थान की जटिलता को $O(K \log_m t)$ तक कम कर देता है, जिससे यह बड़े हॉरिज़न्स के लिए स्केलेबल बन जाता है।

3. प्रमुख योगदान (Key Contributions)

सामान्य गैर-स्थिरता के लिए असंभवता का परिणाम: लेखक सिद्ध करते हैं कि यदि प्रतिफल बढ़ने (non-monotonic) की अनुमति दी जाती है, तो कोई भी लर्निंग रणनीति मिश्रित रेस्टेड और रेस्टलेस आर्म्स वाली सेटिंग में $o(T)$ रिग्रेट प्राप्त नहीं कर सकती। यह "रॉटिंग" (घटने) की धारणा के महत्वपूर्ण महत्व को रेखांकित करता है।
एकीकृत एल्गोरिदम (RAW-UCB): वे RAW-UCB पेश करते हैं, जिसे निम्नलिखित के लिए पूर्व ज्ञान की आवश्यकता नहीं है:
- यह कि सेटिंग रेस्टेड है या रेस्टलेस।
- गैर-स्थिरता का प्रकार (piece-wise constant, bounded variation, आदि)।
- समय सीमा $T$ या वेरिएशन बजट $V_T$ ।
सैद्धांतिक गारंटी (Theoretical Guarantees):
- मिनिमैक्स इष्टतमता (Minimax Optimality): RAW-UCB दोनों सेटिंग्स के लिए मिनिमैक्स रिग्रेट दर प्राप्त करता है (पॉली-लॉगारिदमिक कारकों तक):
  - रेस्टलेस (वेरिएशन बजट $V_T$ के लिए): $O((V_T K T^2 \log T)^{1/3})$ ।
  - पीस-वाइज स्टेशनरी ( $\Upsilon_T$ ब्रेकपॉइंट्स के लिए): $O(\sqrt{\Upsilon_T K T \log T})$ ।
- समस्या-निर्भर सीमाएँ (Problem-Dependent Bounds): दोनों सेटिंग्स में, एल्गोरिदम $O(\log T)$ रिग्रेट बाउंड प्राप्त करता है जब आर्म्स के बीच का अंतर स्थिर होता है, जो कि एक ऐसा परिणाम है जिसे सक्रिय अन्वेषण (active exploration) के बिना रेस्टलेस सेटिंग्स में पहले असंभव माना जाता था।
FEWA की श्रेष्ठता: यह पेपर अत्याधुनिक FEWA (फिल्टरिंग एक्सपैंडिंग विंडो एल्गोरिदम) की तुलना में RAW-UCB का मूल्यांकन करता है। जबकि FEWA समान सांख्यिकी का उपयोग करता है, इसकी जटिल फ़िल्टरिंग प्रक्रिया ढीले (looser) बाउंड की ओर ले जाती है। RAW-UCB एक कड़ा बाउंड प्राप्त करता है (रेस्टेड मामले में स्थिरांक कारक को 4 गुना सुधारता है) और गणनात्मक रूप से अधिक सरल है।

4. परिणाम और प्रयोग (Results and Experiments)

लेखकों ने सिंथेटिक डेटा और वास्तविक दुनिया के डेटासेट दोनों पर अपने सिद्धांत को मान्य किया।

सिंथेटिक बेंचमार्क (Synthetic Benchmarks):
- रेस्टेड सेटिंग्स में, RAW-UCB ने लगातार FEWA, Exp3.S, और GLR-UCB से बेहतर प्रदर्शन किया। इसने दिखाया कि पैसिव फॉरगेटिंग (जो FEWA द्वारा उपयोग किया जाता है) एडेप्टिव विंडो दृष्टिकोण की तुलना में कम प्रभावी है।
- रेस्टलेस सेटिंग्स में, RAW-UCB ने विशेष रूप से रेस्टलेस बैंडिट्स के लिए डिज़ाइन किए गए एल्गोरिदम (जैसे AdSwitch और Exp3.S) के प्रदर्शन के बराबर या उससे अधिक प्रदर्शन किया, बावजूद इसके कि इसे सेटिंग के प्रकार का कोई ज्ञान नहीं था।
वास्तविक दुनिया का प्रयोग (Yahoo! Front Page):
- Yahoo R6A क्लिक-लॉग डेटासेट का उपयोग करके, लेखकों ने एक रॉटिंग परिदृश्य का अनुकरण किया जहाँ समाचार लेख समय के साथ अपनी प्रासंगिकता खो देते हैं।
- प्रदर्शन: RAW-UCB (विशेष रूप से $\alpha=1.4$ के अनुभवजन्य ट्यूनिंग के साथ कुशल संस्करण) ने कई दिनों के डेटा में सबसे कम संचयी रिग्रेट (cumulative regret) प्राप्त किया।
- दक्षता: कुशल RAW-UCB संस्करण ने बेहतर या तुलनीय रिग्रेट प्रदर्शन बनाए रखते हुए GLR-UCB की तुलना में लगभग 10 गुना तेज़ गति से काम किया।
- मजबूती (Robustness): RAW-UCB "कठिन" दिनों (अनुकूल आर्म्स में बार-बार बदलाव) और "आसान" दिनों (एक प्रभावी आर्म) दोनों पर अच्छा प्रदर्शन करता है, और आसान उदाहरणों पर लॉगरिदमिक रिग्रेट प्राप्त करता है।

5. महत्व (Significance)

यह शोध पत्र गैर-स्थिर बैंडिट सिद्धांत में एक बड़े अंतर को पाटता है।

एकीकरण (Unification): यह प्रदर्शित करता है कि एक ही सरल इंडेक्स पॉलिसी दोनों प्रकार के (एक्शन-डिपेंडेंट और टाइम-डिपेंडेंट) रॉटिंग को संभाल सकती है, जिससे अभ्यासकर्ताओं को गैर-स्थिरता की विशिष्ट प्रकृति को पहले से जानने की आवश्यकता समाप्त हो जाती है।
व्यावहारिकता (Practicality): एक कुशल कार्यान्वयन ( $O(K \log t)$ ) पेश करके और यह दिखाकर कि अनुभवजन्य ट्यूनिंग ( $\alpha \approx 1.4$ ) अच्छी तरह काम करती है, लेखक इस एल्गोरिदम को अनुशंसा प्रणाली (recommendation systems) और इंटेलिजेंट ट्यूटरिंग जैसे वास्तविक अनुप्रयोगों के लिए व्यवहार्य बनाते हैं।
सैद्धांतिक अंतर्दृष्टि (Theoretical Insight): यह स्पष्ट करता है कि "रॉटिंग" की धारणा एक शक्तिशाली संरचनात्मक बाधा है जो रेस्टलेस सेटिंग्स में बेहतर लर्निंग रेट ( $O(\log T)$ ) की अनुमति देती है, जो पूरी तरह से एडवर्सरियल (adversarial) या नॉन-मोनोटोनिक वातावरण में असंभव होती है।

निष्कर्षतः, RAW-UCB रॉटिंग बैंडित्स के लिए एक अत्याधुनिक समाधान है, जो विविध गैर-स्थिर वातावरणों में निकट-इष्टतम सैद्धांतिक गारंटी और बेहतर अनुभवजन्य प्रदर्शन प्रदान करता है।