🤖 machine learning

Universal Multiclass Transductive Online Learning

यह शोध पत्र "लेवल-कंस्ट्रेंड-लिटिलस्टोन-लिटिलस्टोन (LCLL) ट्री" संरचना को पेश करते हुए असीमित लेबल स्पेस वाले यूनिवर्सल ट्रांसडक्टिव ऑनलाइन क्लासिफिकेशन की सीखने की क्षमता (learnability) को अभिलक्षित करता है, यह प्रदर्शित करते हुए कि सीखने योग्य कॉन्सेप्ट क्लासेस या तो सीमित या लघुगणकीय (logarithmic) मिस्टेक रेट प्रदर्शित करती हैं, और इन परिणामों को एगोस्टिक (agnostic) और स्टोकेस्टिक सेटिंग्स तक विस्तारित करता है।

मूल लेखक: Steve Hanneke, Hongao Wang

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

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

CC BY 4.0

मूल लेखक: Steve Hanneke, Hongao Wang

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

कल्पना कीजिए कि आप एक चालाक प्रतिद्वंद्वी के खिलाफ एक उच्च-दांव वाले अनुमान लगाने वाले खेल (guessing game) में खेल रहे हैं। यहाँ सेटअप दिया गया है:

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

यह शोध पत्र, जिसका शीर्षक "यूनिवर्सल मल्टीक्लास ट्रांसडक्टिव ऑनलाइन लर्निंग" है, इस बात की जांच करता है कि आप इस खेल को कितनी अच्छी तरह खेल सकते हैं जब उत्तर (लेबल स्पेस) केवल "हाँ" या "नहीं" नहीं होते, बल्कि अनंत सूची में कोई भी संख्या हो सकते हैं (जैसे 1, 2, 3... अनंत तक)।

यहाँ उनके निष्कर्षों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. तीन संभावित परिणाम (त्रिरूपता - The Trichotomy)

लेखकों ने पाया कि प्रतिद्वंद्वी की नियम पुस्तिका कितनी भी जटिल क्यों न हो, सीखने की क्षमता के लिए केवल तीन संभावित परिणाम ही होते हैं। यह एक ट्रैफिक लाइट की तरह है जिसमें केवल तीन रंग होते हैं:

🟢 हरा (स्थिर गलतियाँ - Constant Mistakes): यदि नियम पुस्तिका पर्याप्त सरल है, तो आप केवल शुरुआत में कुछ ही बार गलती करेंगे, और उसके बाद हमेशा सब कुछ सही करेंगे। इससे कोई फर्क नहीं पड़ता कि खेल कितने लंबे समय तक चलता है; आपकी कुल गलतियाँ कम और स्थिर रहती हैं।
🟡 पीला (लघुगणकीय गलतियाँ - Logarithmic Mistakes): यदि नियम पुस्तिका थोड़ी अधिक जटिल है, तो आप अधिक गलतियाँ करेंगे, लेकिन वे बहुत धीरे-धीरे बढ़ती हैं। कल्पना करें कि खेल 1,000 राउंड तक चलता है; आप शायद 10 गलतियाँ करेंगे। यदि खेल 1,000,000 राउंड तक चलता है; तो आप शायद 20 गलतियाँ करेंगे। गलतियाँ बढ़ती हैं, लेकिन वे कुल समय की तुलना में इतनी धीमी गति से बढ़ती हैं कि वे नगण्य हैं।
🔴 लाल (अशिक्षणीय - Unlearnable): यदि नियम पुस्तिका बहुत अधिक अराजक (chaotic) है, तो प्रतिद्वंद्वी आपको लगभग हर राउंड में गलती करने के लिए मजबूर कर सकता है। चाहे आप कितने भी स्मार्ट क्यों न हों, आप पैटर्न को नहीं सीख सकते। आपकी गलतियाँ खेल की गति के साथ ही बढ़ेंगी।

2. नया "मानचित्र" (The LCLL Tree)

यह पता लगाने के लिए कि किसी विशिष्ट नियम पुस्तिका के लिए कौन सा रंग लागू होता है, लेखकों ने संभावनाओं का एक नया तरीका से मानचित्र बनाने का आविष्कार किया है। वे इसे लेवल-कंस्ट्रेंड-लिटलस्टोन-लिटलस्टोन (LCLL) ट्री कहते हैं।

उपमा: एक विशाल पारिवारिक वृक्ष (family tree) की कल्पना करें। आमतौर पर, इन खेलों में, आप केवल शाखाओं को देखते हैं कि क्या पेड़ बहुत बड़ा है। लेकिन क्योंकि उत्तर अनंत संख्याएँ हो सकते हैं, एक मानक पेड़ पर्याप्त नहीं है।
"उदासीनता" (Indifferent) का गुण: लेखकों ने पाया कि पेड़ में एक विशेष गुण होना चाहिए जिसे "उदासीनता" कहा जाता है। एक ऐसे पेड़ की कल्पना करें जहाँ, यदि आप किसी विशिष्ट शाखा को देखते हैं, तो उस शाखा के सभी वंशज (बच्चे, पोते, आदि) उस बात पर सहमत होते हैं जो उस शाखा से पहले हुई थी। यह एक ऐसे परिवार की तरह है जहाँ हर कोई उस इतिहास पर सहमत होता है जो उस शाखा तक हुआ था, भले ही वे इस पर असहमत हों कि आगे क्या होगा।
खोज:
- यदि यह विशेष "उदासीन" पेड़ परिमित (finite) है, तो आप हरे क्षेत्र में हैं (सीखना आसान है)।
- यदि पेड़ अनंत है लेकिन उसकी एक विशिष्ट संरचना है (यह एक "लिटलस्टोन" पेड़ है लेकिन अधिक जटिल "LCLL" पेड़ नहीं है), तो आप पीले क्षेत्र में हैं (धीरे-धीरे सीखा जा सकता है)।
- यदि पेड़ जटिल, अनंत "LCLL" प्रकार का है, तो आप लाल क्षेत्र में हैं (सीखना असंभव है)।

3. पिछले मानचित्र क्यों विफल रहे

लेखकों ने पुराने मानचित्रों (जैसे "VCL ट्री" या "DSL ट्री") का उपयोग करने का प्रयास किया जो "हाँ/नहीं" वाले सरल खेलों के लिए काम करते थे। उन्होंने पाया कि जब उत्तर अनंत संख्याएँ हो सकती हैं, तो वे मानचित्र विफल हो जाते हैं।

उपमा: यह एक छोटे शहर के मानचित्र का उपयोग करके एक विशाल, फैलते हुए महानगर में नेविगेट करने की कोशिश करने जैसा है। पुराने मानचित्रों ने एक महत्वपूर्ण विवरण छोड़ दिया: अनंत दुनिया में, प्रतिद्वंद्वी एक ऐसा पैटर्न छिपा सकता है जो एक साधारण पेड़ जैसा दिखता है लेकिन वास्तव में एक जाल है। नया "LCLL ट्री" मानचित्र ही एकमात्र ऐसा विस्तृत मानचित्र है जो इन जालों को पकड़ सकता है।

4. "खेल" की रणनीति

अपने सिद्धांत को सिद्ध करने के लिए, लेखकों ने एक नए प्रकार के खेल (एक "गेल-स्टुअर्ट गेम") को डिज़ाइन किया है।

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

5. क्या होगा यदि उत्तर अस्त-व्यस्त हैं? (Agnostic Case)

यह शोध पत्र यह भी पूछता है: "क्या होगा यदि प्रतिद्वंद्वी एक आदर्श नियम पुस्तिका का पालन नहीं करता है, बल्कि केवल यादृच्छिक (random) उत्तर देता है?"

इस अस्त-व्यस्त परिदृश्य में, आप पूर्ण होने की उम्मीद नहीं कर सकते। इसके बजाय, आप उस सर्वश्रेष्ठ संभव नियम पुस्तिका के जितना अच्छा कर सकते हैं, उतना करने की कोशिश करते हैं जो डेटा की व्याख्या कर सके।
लेखकों ने दिखाया कि यदि "LCLL ट्री" अनंत नहीं है, तो आप अभी भी प्रभावी ढंग से सीख सकते हैं, जिसमें आपका "पछतावा" (regret - कि आपने सर्वश्रेष्ठ संभव अनुमान की तुलना में कितना खराब प्रदर्शन किया) बहुत धीरे-धीरे (लगभग राउंड की संख्या के वर्गमूल के रूप में) बढ़ता है।

सारांश

यह शोध पत्र इस पहेली को हल करता है कि जब आप भविष्य के प्रश्नों को जानते हैं लेकिन उत्तरों को नहीं, और संभावित उत्तर अनंत हैं, तो सीखने के बारे में क्या होता है। उन्होंने साबित किया कि सीखना या तो आसान है, धीरे-धीरे संभव है, या असंभव है। उन्होंने पाया कि यह जानने की कुंजी कि इसमें से कौन सा है, एक नए, जटिल वृक्ष संरचना में निहित है जिसे LCLL ट्री कहा जाता है, और पिछले तरीके अनंत प्रकृति को संभालने के लिए बहुत सरल थे।

तकनीकी सारांश: यूनिवर्सल मल्टीक्लास ट्रांसडक्टिव ऑनलाइन लर्निंग

समस्या विवरण
यह शोध पत्र गणना योग्य अनंत लेबल स्पेस (countably infinite label space) के साथ यूनिवर्सल ट्रांसडक्टिव ऑनलाइन क्लासिफिकेशन की समस्या की जांच करता है। इस सेटिंग में, एक लर्नर (learner) एक एडवर्सरी (adversary) के विरुद्ध एक क्रमिक खेल (sequential game) में भाग लेता है। खेल शुरू होने से पहले, एडवर्सरी इंस्टेंस का एक अनुक्रम $X = \{X_t\}_{t \in \mathbb{N}}$ चुनता है और पूरे अनुक्रम को लर्नर के सामने प्रकट कर देता है। प्रत्येक दौर $t$ में, लर्नर ज्ञात इंस्टेंस अनुक्रम और वास्तविक लेबल्स के इतिहास $Y_{<t}$ के आधार पर एक लेबल $\hat{Y}_t$ का अनुमान लगाता है। इसके बाद एडवर्सरी वास्तविक लेबल $Y_t$ प्रकट करता है। लर्नर के प्रदर्शन को गलतियों की संख्या (रियलाइजेबल सेटिंग में) या रिग्रेट (एग्नोस्टिक सेटिंग में) द्वारा मापा जाता है।

मुख्य उद्देश्य एक कॉन्सेप्ट क्लास $\mathcal{H}$ की यूनिवर्सल लर्नैबिलिटी (universal learnability) को लक्षणित करना है। यूनिफॉर्म रेट्स के विपरीत, जो विशिष्ट डेटा अनुक्रम से स्वतंत्र बाउंड प्रदान करते हैं, यूनिवर्सल लर्नैबिलिटी के लिए यह आवश्यक है कि प्रत्येक रियलाइजेबल अनुक्रम के लिए, एक ऐसा एल्गोरिदम मौजूद हो जिसका मिस्टेक काउंट समय क्षितिज (time horizon) $T$ के साथ उप-रैखिक (sublinearly) बढ़ता है (या विशिष्ट बाउंड को संतुष्ट करता है)। यह पेपर मौजूदा साहित्य में मौजूद अंतराल को संबोधित करता है, जिसने मुख्य रूप से बाइनरी क्लासिफिकेशन या यूनिफॉर्म रेट्स पर ध्यान केंद्रित किया है, और इन अवधारणाओं को अनबाउंडेड लेबल्स वाले मल्टीक्लास सेटिंग्स तक विस्तारित करता है।

कार्यप्रणाली और प्रमुख अवधारणाएं
लेखक कॉन्सेप्ट क्लासेस के संरचनात्मक विश्लेषण और कॉम्बिनेटरियल गेम थ्योरी का उपयोग करके लर्नैबिलिटी स्थितियों को प्राप्त करते हैं।

कॉम्बिनेटरियल स्ट्रक्चर (Combinatorial Structures):
- लिटलस्टोन ट्री (Littlestone Tree): ऑनलाइन लर्निंग के लिए एक मानक संरचना जहाँ नोड्स इंस्टेंस होते हैं और एजेस लेबल्स होते हैं।
- लेवल-कंस्ट्रेंड लिटलस्टोन (LCL) ट्री: एक भिन्नता जहाँ एक ही गहराई (depth) पर सभी नोड्स एक ही इंस्टेंस साझा करते हैं।
- LCL-लिटलस्टोन (LCLL) ट्री: इस कार्य में पेश की गई एक नई संरचना। यह अनबाउंडेड लेबल्स वाले मल्टीक्लास सेटिंग्स के लिए लिटलस्टोन ट्री का विस्तार करती है। एक LCLL ट्री में, गहराई $k$ पर एक नोड $k+1$ इंस्टेंस के अनुक्रम से जुड़ा होता है, और एजेस गहराई- $k+1$ वाले LCL ट्री के पथों के अनुरूप लेबल के अनुक्रमों का प्रतिनिधित्व करते हैं।
- इन्डिफरेंट प्रॉपर्टी (Indifferent Property): बाइनरी क्लासिफिकेशन कार्य (Bousquet et al., 2023) से अनुकूलित एक महत्वपूर्ण गुण। एक ट्री "इन्डिफरेंट" है यदि BFS ऑर्डर में नोड $v$ से पहले आने वाले किसी भी नोड $u$ के लिए, $u$ के सभी वंशज (descendants) $v$ के लेबल पर सहमत होते हैं। यह गुण एडवर्सरी को एक रैंडम वॉक रणनीति का उपयोग करने की अनुमति देता है ताकि गलतियाँ कराई जा सकें, भले ही लर्नर को इंस्टेंस अनुक्रम का पता हो।
गेम-थ्योरेटिक दृष्टिकोण (Gale-Stewart Games):
लेखक लर्नैबिलिटी को लक्षणित करने के लिए एक नया गैल-स्टुअर्ट गेम (Gale-Stewart game) डिजाइन करते हैं। पिछले खेलों के विपरीत, जहाँ एडवर्सरी इंस्टेंस का एक अनुक्रम प्रस्तावित करता है, यहाँ एडवर्सरी एक "लेवल-कंस्ट्रेंड ट्री" (इंस्टेंस का एक अनुक्रम और संभावित लेबल अनुक्रमों का एक सेट) प्रस्तावित करता है। लर्नर (प्लेयर B) कॉन्सेप्ट क्लास के सुसंगत पथ का चयन करने का प्रयास करता है।
- इस गेम को इन्डिफरेंट प्रॉपर्टी को कैप्चर करने के लिए डिजाइन करने में एक प्रमुख तकनीकी योगदान है। लेखक प्रदर्शित करते हैं कि बाइनरी क्लासिफिकेशन ट्री के मानक विस्तार (जैसे DSL या LCL ट्री) अनबाउंडेड मल्टीक्लास सेटिंग में लर्नैबिलिटी को लक्षणित करने में विफल रहते हैं क्योंकि इस संदर्भ में अनंत ट्री के लिए "इन्डिफरेंट" प्रॉपर्टी स्वतः ही लागू नहीं होती है।
- वे यह स्थापित करने के लिए बोरल डिटरमिनेंसी थ्योरम (Borel Determinacy Theorem) का उपयोग करते है कि यदि कॉन्सेप्ट क्लास में अनंत इन्डिफरेंट LCLL ट्री का अभाव है, तो लर्नर (प्लेयर B) के पास जीतने की रणनीति होती है।
एल्गोरिदम डिजाइन:
- रियलाइजेबल सेटिंग: लेखक ऐसे एल्गोरिदम प्रस्तावित करते हैं जो गैल-स्टुअर्ट गेम की प्रगति को ट्रैक करते हैं। यदि गेम आगे बढ़ता है (जो एक शेटर्ड सबसीक्वेंस की उपस्थिति को दर्शाता है), तो एल्गोरिदम अपनी स्थिति अपडेट करता है। यदि गेम रुक जाता है, तो एल्गोरिदम शेष आंशिक कॉन्सेप्ट क्लास को सीखने के लिए एक वेट फंक्शन (शेटर्ड सबसीक्वेंस पर आधारित) का उपयोग करते हुए 'वेटेड मेजॉरिटी स्ट्रेटजी' पर स्विच करता है।
- एग्नोस्टिक सेटिंग: लेखक रियलाइजेबल एल्गोरिदम को "एक्सपर्ट्स के साथ लर्निंग" फ्रेमवर्क का उपयोग करके विस्तारित करते हैं। वे हैलुसिनेटेड (hallucinated) अनुक्रमों और मिस्टेक इंडेक्स पर रियलाइजेबल एल्गोरिदम के व्यवहार के आधार पर विशेषज्ञों का एक गणनीय सेट (countable set) निर्मित करते हैं, जो नॉन-यूनिफॉर्म इनिशियल वेट्स के साथ स्क्विंट एल्गोरिदम (Squint algorithm) (Koolen & van Erven, 2015) का उपयोग करके रिग्रेट को कम करता है।

प्रमुख परिणाम

रियलाइजेबल सेटिंग के लिए ट्राइकोटॉमी (Trichotomy):
यह पेपर अनबाउंडेड लेबल्स के साथ यूनिवर्सल ट्रांसडक्टिव ऑनलाइन लर्निंग के लिए इष्टतम मिस्टेक रेट्स के लिए एक ट्राइकोटॉमी स्थापित करता है:
- कॉन्स्टेंट मिस्टेक्स ( $O(1)$ ): तभी संभव है जब $\mathcal{H}$ में कोई अनंत इन्डिफरेंट लिटलस्टोन ट्री न हो।
- लॉगारिदमिक मिस्टेक्स ( $\Theta(\log T)$ ): तभी संभव है जब $\mathcal{H}$ में एक अनंत इन्डिफरेंट लिटलस्टोन ट्री हो लेकिन कोई अनंत इन्डिफरेंट LCLL ट्री न हो।
- लीनियर मिस्टेक्स ( $\Omega(T)$ ): यदि $\mathcal{H}$ में एक अनंत इन्डिफरेंट LCLL ट्री है, तो कोई भी एल्गोरिदम सब-लीनियर मिस्टेक्स की गारंटी नहीं दे सकता।
एग्नोस्टिक सेटिंग:
- एक कॉन्सेप्ट क्लास $\mathcal{H}$ एग्नोस्टिकली यूनिवर्सल ट्रांसडक्टिवली ऑनलाइन लर्न करने योग्य है यदि और केवल यदि उसमें कोई अनंत इन्डिफरेंट LCLL ट्री नहीं है।
- ऐसे क्लासेस के लिए, लेखक एक एल्गोरिदम प्रदान करते हैं जो $\tilde{O}(\sqrt{T})$ का रिग्रेट बाउंड प्राप्त करता है (पॉली-लॉगैरिथमिक फैक्टर्स को छिपाते हुए)।
- एक लोअर बाउंड सिद्ध किया गया है जो दिखाता है कि कम से कम दो अलग-अलग कॉन्सेप्ट्स वाले किसी भी क्लास के लिए, रिग्रेट $o(\sqrt{T})$ नहीं हो सकता।
स्टोकेस्टिक प्रोसेस एक्सटेंशन:
परिणामों को उस सेटिंग में विस्तारित किया गया है जहाँ लर्नर केवल इंस्टेंस अनुक्रम उत्पन्न करने वाली स्टोकेस्टिक प्रोसेस को जानता है (न कि स्वयं अनुक्रम को)। "सभी प्रोसेस जो यूनिवर्सल ऑनलाइन लर्निंग को स्वीकार करती हैं" के लिए शर्त को अनंत इन्डिफरेंट LCLL ट्री की अनुपस्थिति के बराबर दिखाया गया है।

महत्व और दावे
यह पेपर ऑनलाइन लर्निंग के सिद्धांत में कई महत्वपूर्ण योगदानों का दावा करता है:

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

लेखक एग्नोस्टिक सेटिंग के संबंध में विनम्र रहते हैं, ऊपरी बाउंड ( $\tilde{O}(\sqrt{T})$ ) और लोअर बाउंड ( $\Omega(\sqrt{T})$ ) के बीच एक पॉली-लॉगैरिथमिक अंतर को स्वीकार करते हैं, और इस अंतर को कम करने के प्रश्न को एक ओपन क्वेश्चन के रूप में छोड़ देते हैं। वे अनबाउंडेड लेबल्स वाली प्रोसेस के लिए यूनिवर्सल ऑनलाइन लर्निंग के लक्षणण को भी एक ओपन प्रॉब्लम के रूप में पहचानते हैं।