🤖 machine learning

Learning in Markovian bandits with non-observable states and constrained decision epochs

यह शोधपत्र गैर-अवलोकन योग्य अवस्थाओं और सीमित निर्णय युगों वाले स्व-अपघटनीय मार्कोवियन बैंडिट्स (self-degrading Markovian bandits) को प्रस्तुत करता है, जो यह प्रदर्शित करता है कि जबकि शुद्ध नीतियां (pure policies) स्पर्शोन्मुख रूप से इष्टतम हैं और पूर्व ज्ञान के बिना लघुगणकीय रिग्रेट (logarithmic regret) सामान्यतः अप्राप्य है, प्रस्तावित UCB-NOM एल्गोरिदम पूर्व ज्ञान के बिना भी लगभग लघुगणकीय रिग्रेट और बायस बाउंड्स के साथ $O(\log T)$ रिग्रेट प्राप्त करता है, जो सभी अंतर्निहित अवस्थाओं की संख्या से स्वतंत्र है।

मूल लेखक: Thomas Hira, Victor Boone, Urtzi Ayesta, Ina Maria Verloop

प्रकाशित 2026-06-29

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

CC BY 4.0

मूल लेखक: Thomas Hira, Victor Boone, Urtzi Ayesta, Ina Maria Verloop

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

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

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

यह शोध पत्र इस समस्या पर चर्चा करता है कि इन सख्त शर्तों के तहत यह कैसे सीखा जाए कि कौन सी मशीन सबसे अच्छी है, बिना यह जाने कि मशीनें आंतरिक रूप से कैसे काम करती हैं।

मुख्य समस्या: "स्विचिंग" कठिन क्यों है?

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

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

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

चुनौती: आप अवस्थाओं (States) को नहीं देख सकते

भले ही एक ही मशीन पर टिके रहना सबसे अच्छी रणनीति है, फिर भी आपको यह पता लगाना होगा कि वह कौन सी मशीन है। चूंकि आप मशीन की आंतरिक स्थिति को नहीं देख सकते, इसलिए आपको प्राप्त रिवॉर्ड के आधार पर अनुमान लगाना होगा।

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

समाधान: UCB-NOM

इस समस्या को हल करने के लिए, लेखकों ने UCB-NOM नामक एक एल्गोरिदम बनाया।

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

परिणाम: यह कितना अच्छा है?

पेपर मुख्य रूप से दो बातें सिद्ध करता है:

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

निष्कर्ष (Takeaway)

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

संक्षेप में: यह पेपर हमें एक ऐसी फैक्ट्री में एक स्मार्ट मैनेजर बनने का तरीका सिखाता है जहाँ आप मशीनों के अंदरूनी हिस्से नहीं देख सकते और उन्हें आसानी से बंद नहीं कर सकते। यह दिखाता है कि यदि मशीनें खाली छोड़ने पर जंग खाती हैं, तो सबसे अच्छा कदम एक को चुनना और उसी के साथ बने रहना है, और यह यह पता लगाने के लिए एक गणितीय रेसिपी प्रदान करता है कि कौन सा चुनना है।

तकनीकी सारांश: गैर-अवलोकन योग्य अवस्थाओं और सीमित निर्णय युगों के साथ मार्कोवियन बैंडिट्स में सीखना

1. समस्या की परिभाषा

यह शोध पत्र मार्कोवियन बैंडिट्स (Markovian bandits) के अंतर्गत दो विशिष्ट बाधाओं के तहत 'रिग्रेट मिनिमाइजेशन' (regret minimization) की समस्या को संबोधित करता है:

गैर-अवलोकन योग्य अवस्थाएँ (Non-observable States): नियंत्रक (controller) भुजाओं (arms) की आंतरिक अवस्था का अवलोकन नहीं कर सकता (जो कि मार्कोव श्रृंखलाएं हैं)। उपलब्ध एकमात्र फीडबैक वह रिवॉर्ड (reward) है जो सक्रिय भुजा द्वारा उत्पन्न किया जाता है। यह एक "फुल बैंडिट फीडबैक" सेटिंग के अनुरूप है जहाँ स्टेट स्पेस छिपा हुआ होता है।
सीमित निर्णय युग (Constrained Decision Epochs): नियंत्रक प्रत्येक समय अंतराल (time step) पर भुजाओं को मनमाने ढंगता से नहीं बदल सकता। इसके बजाय, स्विचिंग केवल विशिष्ट निर्णय युगों ( $\tau_i$ ) पर ही अनुमत है, जो रिवॉर्ड की धारा (stream) द्वारा निर्धारित स्टॉपिंग टाइम्स (stopping times) हैं। विशेष रूप से, नियंत्रक को एक विशिष्ट संकेत (जैसे, गैर-शून्य रिवॉर्ड) प्राप्त होने तक एक भुजा के प्रति प्रतिबद्ध रहना होगा।

भुजाओं को मार्कोव डिसीजन प्रोसेस (MDPs) के रूप में मॉडल किया गया है जहाँ ट्रांजिशन डायनेमिक्स इस बात पर निर्भर करते हैं कि भुजा सक्रिय है या निष्क्रिय। सिस्टम इस प्रकार विकसित होता है कि गैर-सक्रिय भुजाएं अपने निष्क्रिय कर्नेल ( $p^0_a$ ) के अनुसार परिवर्तित होती रहती हैं, जबकि सक्रिय भुजाएं अपने सक्रिय कर्नेल ( $p^1_a$ ) के अनुसार परिवर्तित होती हैं।

2. लर्निंग फ्रेमवर्क और बेंचमार्क

लेखक अपने विश्लेषण को एक "प्योर रिग्रेट" (pure regret) बेंचमार्क तक सीमित रखते हैं।

प्योर पॉलिसी (Pure Policies): एक पॉलिसी को तब "प्योर" कहा जाता है यदि वह लर्निंग होराइजन की शुरुआत से अंत तक एक ही भुजा का चयन करती है और कभी स्विच नहीं करती।
रिग्रेट की परिभाषा: रिग्रेट, लर्निंग एल्गोरिदम के संचयी रिवॉर्ड (cumulative reward) और सर्वश्रेष्ठ प्योर पॉलिसी (उच्चतम स्पर्शोन्मुखी लाभ/asymptotic gain वाली भुजा) के संचयी रिवॉर्ड के बीच का अंतर है।

प्योर पॉलिसी के लिए प्रेरणा:
जबकि "रेस्टलेस" (restless) बैंडिट्स (जहाँ निष्क्रिय भुजाएं भी विकसित होती हैं) के लिए प्योर पॉलिसी सामान्यतः उप-इष्टतम (sub-optimal) होती हैं, लेखक "सेल्फ-डिग्रेडिंग रेस्टलेस बैंडिट्स" (self-degrading restless bandits) नामक एक वर्ग पेश करते हैं। इन मामलों में, यदि किसी भुजा को निष्क्रिय छोड़ दिया जाता है, तो उसका अपेक्षित बायस (एक गेन का माप) नियंत्रक के अवलोकनों के सापेक्ष घटता है या स्थिर रहता है। यह शोध पत्र सिद्ध करता है कि सेल्फ-डिग्रेडिंग बैंडिट्स के लिए, प्योर पॉलिसी स्पर्शोन्मुखी रूप से इष्टतम (asymptotically optimal) होती हैं। यह वर्ग "रेस्टेड" (rested) बैंडिट्स (जहाँ निष्क्रिय भुजाएं फ्रीज हो जाती हैं) का सामान्यीकरण करता है और इसमें गैर-प्रीएम्प्टिव गिलबर्ट-एलियट चैनल्स और नेरलवे-एरो मॉडल्स जैसे गैर-तुच्छ (non-trivial) रेस्टलेस उदाहरण शामिल हैं।

3. कार्यप्रणाली: UCB-NOM

शोध पत्र UCB-NOM (Non-Observable Markovian bandits के लिए Upper Confidence Bound) प्रस्तावित करता है, जो UCB सिद्धांत से प्रेरित एक आशावादी (optimistic) एल्गोरिदम है।

UCB-NOM के मुख्य घटक:

अनुभवजन्य गेन एस्टीमेटर (Empirical Gain Estimator): एल्गोरिदम एक भुजा ( $a$ ) के गेन ( $g_a$ ) का अनुमान उस औसत रिवॉर्ड से लगाता है जो उस भुजा के सक्रिय होने पर एकत्र किया गया था।
आशावादी इंडेक्स निर्माण (Optimistic Index Construction): गैर-अवलोकन योग्य अवस्थाओं और बाधाओं को संभालने के लिए, एल्गोरिदम वास्तविक गेन के लिए एक आशावादी ऊपरी सीमा $\tilde{g}_a(t)$ $\tilde{g}_{a} (t)$ का निर्माण करता है। इस इंडेक्स में शामिल हैं:
- अनुभवजन्य माध्य रिवॉर्ड (empirical mean reward)।
- एक एक्सप्लोरेशन बोनस (कॉन्फिडेंस इंटरवल) जो निम्नलिखित को ध्यान में रखता है:
  - पुल्स की संख्या ( $N_a(t)$ )।
  - कितनी बार एल्गोरिदम ने भुजा $a$ की ओर स्विच किया (स्विचिंग कॉस्ट)।
  - भुजा के मार्कोव चेन का बायस स्पैन ( $sp(b_a)$ ), जो बायस फंक्शन के अधिकतम विचलन को मापता है।
डबलिंग ट्रिक (Doubling Trick): सैद्धांतिक गारंटियों के लिए आवश्यक "दुर्लभ स्विचिंग" (rarely switching) गुण को पूरा करने के लिए, एल्गोरिदम एक डबलिंग ट्रिक का उपयोग करता है। एक बार भुजा चुनी जाने के बाद, उसे तब तक चलाया जाता है जब तक कि उसके विज़िट्स की संख्या दोगुनी न हो जाए। यह सुनिश्चित करता है कि स्विचों की संख्या पुल्स की संख्या के साथ लॉगरिदमिक रूप से बढ़ती है।

संबोधित किए गए सैद्धांतिक चुनौतियां:

गैर-अवलोकन क्षमता (Non-observability): टेकिन और लियू (Tekin & Liu) के पिछले कार्यों (RCA) के विपरीत, जो पुनरुत्थान चक्रों (regeneration cycles) को ट्रिगर करने के लिए अवस्थाओं के अवलोकन पर निर्भर करते हैं, UCB-NOM पुनरुत्थान (regeneration) का उपयोग नहीं कर सकता। इसके बजाय, यह बायस स्पैन और स्विचों की संख्या का उपयोग करके त्रुटि को सीमित करता है।
सीमित युग (Consted Epochs): एल्गोरिदम को अगले निर्णय युग तक के विलंब (delay) को ध्यान में रखना चाहिए। विश्लेषण अगले निर्णय युग तक के अपेक्षित समय पर एक सीमा ( $C_\tau$ ) मानता है।

4. मुख्य परिणाम और सैद्धांतिक गारंटी

A. लोअर बाउंड्स (लॉगारिदमिक रिग्रेट की असंभवता)

शोध पत्र स्थापित करता है कि बैंडिट की संरचना का पूर्व ज्ञान होने के बिना, लॉगारिदमिक रिग्रेट ( $O(\log T)$ ) अप्राप्य है।

थ्योरम 4: किसी भी सुसंगत (consistent), दुर्लभ-स्विचिंग एल्गोरिदम के लिए, अपेक्षित रिग्रेट $\omega(\log T)$ (सुपर-लॉगारिदमिक) होता है। यह उन वैकल्पिक मॉडलों का निर्माण करके सिद्ध किया गया है जो रिवॉर्ड के माध्यम से वास्तविक मॉडल से अविभेद्य (indistinguishable) हैं लेकिन उनके अनुकूलतम (optimal) भुजाएं अलग हैं, जिससे एल्गोरिदम को उन्हें अलग करने के लिए अत्यधिक उप-इष्टतम भुजाओं को खींचने के लिए मजबूर होना पड़ता है।

B. UCB-NOM का प्रदर्शन (सामान्य मामला)

थ्योरम 6: UCB-NOM $O(f(T)^2 \log T)$ का रिग्रेट बाउंड प्राप्त करता है, जहाँ $f(T)$ एक "स्पैन प्रॉक्सी" फंक्शन है जो अनंत की ओर बढ़ता है।
महत्व: $f(T)$ को स्वेच्छा से बहुत धीरे-धीरे बढ़ने देने के लिए चुनकर, UCB-NOM आदर्श लॉगरिदमिक शासन के करीब पहुँच सकता है, जो प्रभावी रूप से सुपर-लॉगारिदमिक लोअर बाउंड के साथ मेल खाता है।

C. पूर्व ज्ञान के साथ प्रदर्शन (बाउंडेड बायस स्पैन)

यदि एल्गोरिदम को सभी भुजाओं के बायस स्पैन के लिए एक ज्ञात ऊपरी सीमा $D$ (और निर्णय युग विलंब) प्रदान की जाती है, तो प्रदर्शन काफी सुधर जाता है।

थ्योरम 8 (इंस्टेंस-डिपेंडेंट): एक निश्चित स्पैन प्रॉक्सी $f \equiv D$ के साथ, UCB-NOM $O(\log T)$ इंस्टेंस-डिपेंडेंट रिग्रेट प्राप्त करता है।
थ्योरम 9 (वर्स्ट-केस): इसी बाउंडेड स्पैन धारणा के तहत, एल्गोरिदम $O(\sqrt{T \log T})$ का वर्स्ट-केस रिग्रेट प्राप्त करता है।

D. ट्यूनिंग और कॉन्फिडेंस पैरामीटर्स

शोध पत्र कॉन्फिडेंस पैरामीटर $\delta(t)$ के चयन का विश्लेषण करता है। यह सुझाव देता है कि स्टोकेस्टिक बैंडिट्स की तुलना में मार्कोवियन सेटिंग्स में "अंडर-ऑप्टिमिस्टिक" (कॉन्फिडेंस इंटरवल को चौड़ा करने के लिए छोटा $\delta(t)$ चुनना) होना बेहतर है। ऐसा इसलिए है क्योंकि मार्कोवियन एस्टिमेटर्स में शोर (noise), बायस स्पैन के कारण रिवॉर्ड वेरिएंस की तुलना में अधिक हो सकता है, जिसके लिए आशावादी गुण बनाए रखने के लिए बड़े एक्सप्लोरेशन बोनस की आवश्यकता होती है।

5. महत्व और योगदान

शोध पत्र निम्नलिखित योगदानों का दावा करता है:

समस्या का स्वरूप (Problem Formulation): इसने गैर-अवलोकन योग्य अवस्थाओं और एंडोजेनस (endogenous) सीमित निर्णय युगों को मिलाने वाले एक लर्निंग सेटिंग को औपचारिक रूप दिया है, जो संचार नेटवर्क (जैसे, नॉन-प्रीएम्प्टिव चैनल शेड्यूलिंग) से प्रेरित है।
सेल्फ-डिग्रेडिंग बैंडिट्स: इसने 'प्योर पॉलिसीज' के एक वर्ग की पहचान की और उसे परिभाषित किया जहाँ प्योर पॉलिसी इष्टतम होती हैं, जो प्योर रिग्रेट को बेंचमार्क के रूप में उपयोग करने को न्यायसंगत बनाता है।
मौलिक सीमाएं (Fundamental Limits): यह सिद्ध करता है कि अवस्थाओं की गैर-अवलोकन क्षमता और सीमित युगों का संयोजन स्वाभाविक रूप से सामान्य मामले में लॉगरिदमिक रिग्रेट को रोकता है, जिससे एक सुपर-लॉगारिदमिक लोअर बाउंड स्थापित होता है।
एल्गोरिदम डिजाइन: यह UCB-NOM पेश करता है, जो अवस्था अवलोकन के बिना इष्टतम के करीब रिग्रेट प्राप्त करता है। महत्वपूर्ण रूप से, इसके रिग्रेट बाउंड्स अंडरलाइंग मार्कोव चेन के अवस्थाओं की संख्या ( $|S_a|$ ) पर नहीं, बल्कि बायस स्पैन पर निर्भर करते हैं।
संरचनात्मक अंतर्दृष्टि (Structural Insights): यह प्रदर्शित करता है कि एक सरल पूर्व ज्ञान (बायस स्पैन का बाउंड) के साथ, स्टोकेस्टिक बैंडिट्स के शास्त्रीय लॉगरिदमिक रिग्रेट गारंटियों को पुनः प्राप्त किया जा सकता है, जो यह सुझाव देता है कि यदि संरचनात्मक बाउंड ज्ञात हों, तो अवस्था गैर-अवलोकन क्षमता सेल्फ-डिग्रेडिंग सेटिंग्स में एक "हल्की असुविधा" मात्र है।

लेखक निष्कर्ष निकालते हैं कि हालांकि यह सेटिंग मानक स्टोकेस्टिक बैंडिट्स की तुलना में अधिक जटिल है, फिर भी प्रस्तावित फ्रेमवर्क और एल्गोरिदम मजबूत सैद्धांतिक गारंटी प्रदान करते हैं, बशर्ते कि एक प्योर रिग्रेट बेंचमार्क का पालन किया जाए।