🤖 machine learning

On Randomized Algorithms in Online Strategic Classification

यह शोध पत्र रियलाइज़ेबल सेटिंग में रैंडमाइज्ड लर्नर्स के लिए पहला लोअर बाउंड स्थापित करके और एगोस्टिक सेटिंग में एक इमप्रॉपर रैंडमाइज्ड एल्गोरिदम पेश करके ऑनलाइन स्ट्रैटेजिक क्लासिफिकेशन को आगे बढ़ाता है जो कि इष्टतम $O(\sqrt{T\log|\mathcal H|)$ रिग्रेट रेट प्राप्त करता है, जिससे डिटर्मिनिस्टिक और प्रॉपर लर्निंग दृष्टिकोणों की सीमाओं को दूर करने के लिए रैंडमाइजेशन और इमप्रॉपरनेस की आवश्यकता को सिद्ध किया जाता है।

मूल लेखक: Chase Hutton, Adam Melrod, Han Shao

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

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

CC BY 4.0

मूल लेखक: Chase Hutton, Adam Melrod, Han Shao

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

कल्पना कीजिए कि आप एक ऋण अधिकारी (Learner) हैं जो यह तय करने की कोशिश कर रहे हैं कि किसे ऋण मिलना चाहिए। आपके पास आवेदकों के क्रेडिट इतिहास के आधार पर निर्णय लेने के लिए नियमों का एक सेट (एक Classifier) है। हालाँकि, आवेदक (Agents) चतुर हैं; वे आपके नियमों को जानते हैं और अपने क्रेडिट इतिहास को बस इतना बदलने की कोशिश करेंगे कि वे स्वीकृत हो सकें, भले ही उनकी वास्तविक वित्तीय स्थिति में कोई बदलाव न आया हो। यह स्ट्रैटेजिक क्लासिफिकेशन (Strategic Classification) है।

अब, कल्पना कीजिए कि यह हर दिन एक नए आवेदक के साथ होता है। आप भविष्य को नहीं जानते, और आपको अपने नियमों को चलते-फिरते सीखना पड़ता है। यह ऑनलाइन लर्निंग (Online Learning) है।

हटन, मेलरोड और शाओ का शोध पत्र एक सरल लेकिन पेचीदा सवाल पूछता है: क्या ऋण अधिकारी के लिए थोड़ा सा रैंडम (अनिश्चित) होना मददगार है? एक निश्चित नियम का उपयोग करने के बजाय, क्या अधिकारी को दिन के लिए कौन सा नियम उपयोग करना है, यह तय करने के लिए सिक्का उछालना चाहिए?

यहाँ उनके निष्कर्षों का रोजमर्रा के उदाहरणों का उपयोग करके विवरण दिया गया है।

सेटअप: द "मैनिपुलेशन ग्राफ" (हेरफेर का ग्राफ)

आवेदकों के संभावित कार्यों को एक मानचित्र के रूप में सोचें।

मानचित्र (ग्राफ): एक शहर की कल्पना करें जहाँ हर घर एक क्रेडिट स्कोर है। कुछ घर सड़कों से जुड़े हुए हैं। यदि आप घर A में रहते हैं, तो आप घर B (अपना स्कोर बदलने के लिए हेरफेर करना) तक जा सकते हैं यदि वहाँ एक सड़क है।
डिग्री ( $\Delta$ ): यह किसी भी एकल घर से निकलने वाली सड़कों की अधिकतम संख्या है। यदि किसी घर में 10 सड़कें हैं, तो आवेदक के पास अपना स्कोर बदलने के 10 तरीके हैं।
नियम (हाइपोथीसिस क्लास): ये आवेदकों को परखने के अलग-अलग तरीके हैं।

बड़ा सवाल: रैंडमनेस बनाम निश्चितता

सामान्य लर्निंग (जहाँ लोग आपको धोखा देने की कोशिश नहीं करते) में, रैंडम होना वास्तव में आपको तेजी से सीखने में मदद नहीं करता है। आपको बस एक अच्छा नियत (deterministic) रणनीति की आवश्यकता होती है।

लेकिन इस "पेचीदा" दुनिया में जहाँ लोग सिस्टम के साथ खेल रहे हैं, पिछले शोध ने सुझाव दिया था कि रैंडम होना शायद आपकी चालों से बचने में मदद कर सकता है। लेखक जानना चाहते थे कि: क्या रैंडमनेस एक जादुई हथियार है, या इसकी भी सीमाएँ हैं?

भाग 1: "परफेक्ट वर्ल्ड" परिदृश्य (रियलाइजेबल सेटिंग)

एक ऐसी दुनिया की कल्पना करें जहाँ नियमों का एक आदर्श सेट मौजूद है जो कभी गलती नहीं करेगा, यदि केवल आवेदक झूठ न बोल रहे होते।

पुरानी धारणा:
पिछले अध्ययनों ने दिखाया कि यदि ऋण अधिकारी कठोर (deterministic) है, तो उन्हें कई गलतियाँ करने के लिए मजबूर किया जा सकता है। लेकिन यदि वे रैंडम थे, तो वे कभी-कभी इन जालों से बच सकते थे। ऐसा लग रहा था कि रैंडमनेस एक सुपरपावर है।

नई खोज:
लेखकों ने इस परीक्षण के लिए एक विशिष्ट "जाल" (एक गणितीय निर्माण) बनाया।

जाल: उन्होंने एक ऐसी स्थिति बनाई जहाँ आवेदक "लुका-छिपी" के खेल की तरह हैं। आवेदक कई संभावनाओं के बीच अपनी असली पहचान छिपाते हैं।
परिणाम: उन्होंने साबित किया कि भले ही ऋण अधिकारी रैंडम हो, वह इस जाल से बच नहीं सकता। यदि खेल लंबे समय तक चलता है, तो रैंडम अधिकारी भी उतने ही गलतियाँ करेगा जितनी एक कठोर अधिकारी करता है।
निष्कर्ष: रैंडमनेस कोई जादुजी हथियार नहीं है। लंबे समय में, आप सिक्के उछालकर समस्या की मौलिक कठिनाई को नहीं हरा सकते। आप जो सर्वश्रेष्ठ कर सकते हैं वह अभी भी इस बात से सीमित है कि नियम कितने जटिल हैं और आवेदक हेरफेर करने के कितने तरीके अपना सकते हैं।

हालाँकि, एक उम्मीद की किरण है:
जबकि रैंडमनेस लंबे समय में मदद नहीं करती है, यह कम समय में मदद करती है। यदि खेल छोटा है (कम आवेदक), तो एक रैंडम रणनीति एक ज्ञात कठोर रणनीति की तुलना में कम गलतियाँ करती है। यह एक भाग्यशाली ताबीज की तरह है जो कुछ राउंड के लिए काम करता है लेकिन अंततः खत्म हो जाता है।

भाग 2: "मेसी वर्ल्ड" परिदृश्य (एग्नोस्टिक सेटिंग)

अब, एक ऐसी दुनिया की कल्पना करें जहाँ कोई भी पूर्ण सेट ऑफ रूल्स नहीं है। शायद आवेदक इतने चालाक हैं कि कोई भी नियम जो आप बनाते हैं, वह अंततः कुछ लोगों पर विफल हो जाएगा। यह "एग्नोस्टिक" सेटिंग है।

समस्या:
इस अस्त-व्यस्त दुनिया के लिए सबसे अच्छा पिछला तरीका धीमा और बोझिल था। यह घास के ढेर में सुई खोजने की कोशिश करने जैसा था, लेकिन आपको केवल एक पल के लिए एक तिनके को देखने का मौका मिलता है। त्रुटि दर (error rate) अधिक थी।

नया समाधान:
लेखकों ने एक नया, थोड़ा "बेईमानी वाला" (इम्प्रापर) एल्गोरिदम बनाया।

चाल: अपने आधिकारिक स्वीकृत नियमों की सूची से ही नियम चुनने के बजाय, एल्गोरिदम को कभी-कभी यह कहने की अनुमति है, "मुझे नहीं पता, चलो बस सभी को YES कह देते हैं।"
यह क्यों काम करता है: "सभी को YES" कहकर, ऋण अधिकारी आवेदकों को हेरफेर करना बंद करने के लिए मजबूर करता है। यदि अधिकारी सभी को "YES" कहता है, तो आवेदक के पास अपना स्कोर बदलने का कोई प्रोत्साहन नहीं होता है। यह आवेदक के मूल स्कोर के बारे में सच्चाई प्रकट करता है।
परिणाम: यह "बेईमानी" वाली रणनीति सीखने वाले को बहुत तेजी से सीखने में मदद करती है। वे सीखने की सैद्धांतिक "गोल्ड स्टैंडर्ड" गति प्राप्त करते हैं, जो उस गति से मेल खाती है जहाँ कोई भी आपको धोखा देने की कोशिश नहीं करता है।

पकड़ (The Catch):
लेखकों ने सिद्ध किया है कि गोल्ड स्टैंडर्ड गति प्राप्त करने के लिए आपको इस "बेईमानी" (इम्प्रापर) रणनीति का उपयोग करना ही होगा। यदि आप ऋण अधिकारी को केवल अपने आधिकारिक नियमों का उपयोग करने के लिए मजबूर करते हैं (एक "प्रॉपर" लर्नर), तो वे धीमी और बोझिल सीखने की गति के साथ फंसे रहेंगे।

शोध पत्र के दावों का सारांश

रैंडमनेस कोई रामबाण नहीं है: एक दुनिया में जहाँ एक पूर्ण नियम मौजूद है, रैंडम होना आपको समस्या की मौलिक सीमाओं से हमेशा के लिए बचने में मदद नहीं करता है। आपको अभी भी "लागत" चुकानी होगी जो इस बात पर निर्भर करती है कि आवेदक कितने चालाक हैं।
रैंडमनेस शुरुआत में मदद करती है: यदि आवेदकों की संख्या कम है, तो एक रैंडम रणनीति एक कठोर रणनीति की तुलना में बेहतर होती है।
मेसी वर्ल्ड में तेजी से सीखने के लिए, आपको "बेईमानी" करनी होगी: जब कोई पूर्ण नियम मौजूद नहीं होता है, तो सैद्धांतिक रूप से संभव सबसे तेज़ गति से सीखने के लिए, एल्गोरिदम को ऐसे रणनीतियों का उपयोग करने के लिए तैयार रहना चाहिए जो सख्त "नियमों" में नहीं आते (जैसे सभी को "YES" कहना)। यदि आप सख्ती से नियमों का पालन करते हैं, तो आप धीमी गति से सीखेंगे।
"डिग्री" मायने रखती है: आप कितनी तेजी से सीखते हैं, यह काफी हद तक इस बात पर निर्भर करता है कि आवेदक के पास अपने डेटा में हेरफेर करने के कितने तरीके हैं (मानचित्र पर कितनी सड़कें हैं)। वे जितने अधिक तरीके से धोखाधड़ी कर सकते हैं, सीखना उतना ही कठिन होता है।

संक्षेप में: रैंडमनेस अल्पकालिक लाभ के लिए एक उपयोगी उपकरण है, लेकिन एक पेचीदा वातावरण में लंबे खेल को जीतने के लिए, कभी-कभी आपको सच्चाई देखने के लिए अपने स्वयं के खेल के नियमों को तोड़ने की आवश्यकता होती है।

तकनीकी सारांश: ऑनलाइन रणनीतिक वर्गीकरण में रैंडमाइज्ड एल्गोरिदम पर

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

यह कार्य ऑनलाइन रणनीतिक वर्गीकरण (Online Strategic Classification) के विषय को संबोधित करता है, जो एक ऐसा परिवेश है जहाँ एक शिक्षार्थी (learner) स्व-हितकारी एजेंटों के साथ क्रमिक रूप से अंतःक्रिया करता है, जो अनुकूल भविष्यवाणियों को प्राप्त करने के लिए अपने अवलोकन योग्य फीचर वेक्टर्स (feature vectors) को रणनीतिक रूप से संशोधित करते हैं। शिक्षार्थी का लक्ष्य इस हेरफेर के बावजूद रिग्रेट (regret) या मिस्टेक बाउंड्स (mistake bounds) को कम करना है।

अंतःक्रिया को इस प्रकार मॉडल किया गया है:

हेरफेर ग्राफ (Manipulation Graph): एक ज्ञात ग्राफ $G = (X, E)$ व्यवहार्य हेरफेर को परिभाषित करता है। एक एज $(x, x') \in E$ इंगित करता है कि मूल फीचर्स $x$ वाला एक एजेंट $x'$ तक हेरफेर कर सकता है।
एजेंट का व्यवहार: एक क्लासिफायर $h$ को देखने के बाद, एक एजेंट एक सुलभ फीचर वेक्टर $z$ पर जाता है जो सकारात्मक भविष्यवाणी ( $h(z)=+1$ ) देता है; यदि संभव न हो, तो वे $x$ पर ही रहते हैं।
फीडबैक: शिक्षार्थी हेरफेर किए गए फीचर्स $z_t$ और वास्तविक लेबल $y_t$ को देखता है, लेकिन मूल फीचर्स $x_t$ को नहीं देख पाता। इसके परिणामस्वरूप आंशिक सूचना फीडबैक (partial information feedback) प्राप्त होता है।
रैंडमाइज्ड मॉडल (Randomized Model): यह शोध रैंडमाइज्ड एल्गोरिदम मॉडल में कार्य करता है, जहाँ शिक्षार्थी एक वितरण (distribution) से एक परिकल्पना (hypothesis) $h_t$ का नमूना लेता है, उस विशिष्ट प्राप्ति (realization) को एजेंट के सामने प्रकट करता है, और एजेंट इस प्राप्ति के प्रति सर्वोत्तम प्रतिक्रिया देता है। यह "फ्रैक्शनल मॉडल" से भिन्न है जहाँ एजेंट स्वयं वितरण के प्रति प्रतिक्रिया देते हैं।

यह अध्ययन दो स्थितियों पर विचार करता है:

रियलाइजेबल (Realizable): हाइपोथीसिस क्लास $H$ में एक ऐसी परिकल्पना मौजूद है जो अनुक्रम पर शून्य रणनीतिक हानि (zero strategic loss) सहन करती है।
एग्नोस्टिक (Agnostic): $H$ में कोई भी परिकल्पना शून्य हानि की गारंटी नहीं देती है; लक्ष्य पिछले अनुभव के आधार पर सर्वश्रेष्ठ स्थिर परिकल्पना के सापेक्ष रिग्रेट को कम करना है।

2. कार्यप्रणाली (Methodology)

लेखक नवीन लोअर-बाउंड कंस्ट्रक्शंस और रैंडमाइज्ड एल्गोरिदम डिजाइनों के संयोजन का उपयोग करते हैं जो हेरफेर ग्राफ की संरचना का लाभ उठाते हैं।

लोअर बाउंड कंस्ट्रक्शन (Lower Bound Constructions)

रैंडमाइज्ड लर्नर्स की सीमाओं को स्थापित करने के लिए, लेखक विशिष्ट हेरफेर ग्राफ और हाइपोथीसिस क्लासेज का निर्माण करते हैं जो लर्निंग समस्या को एक हिडन इंडेक्स गेम (hidden index game) में बदल देते हैं।

ग्राफ संरचना: वे वर्टिसों ( $U, P$ ) की परतों और सहायक नोड्स ( $L, R, z$ ) वाला एक ग्राफ बनाते हैं जहाँ एज इस तरह व्यवस्थित होते हैं कि विशिष्ट हाइपोथीसिस केवल एक नोड $P$ को पॉजिटिव लेबल करती है।
एडवर्सरियल रणनीति (Adversarial Strategy): एडवर्सरी एक हिडन इंडेक्स $i^*$ का नमूना लेती है और ऐसे एजेंट प्रस्तुत करती है जो शिक्षार्थी को $i^*$ की पहचान करने के लिए मजबूर करते हैं। एडवर्सरी अनुकूल रूप से एजेंटों का चयन करती है जो शिक्षार्थी के वितरण $D_t$ पर आधारित होते हैं, जो "बुरे" क्लासिफायर्स (जो विशिष्ट संरचनात्मक नोड्स पर त्रुटियां करते हैं) को दंडित करते हैं जबकि शिक्षार्थी को हिडन इंडेक्स का अनुमान लगाने के लिए मजबूर करते हैं यदि वे "अच्छे" क्लासिफायर खेलते हैं।
प्रॉपर बनाम इमप्रॉपर (Proper vs. Improper): निर्माण प्रॉपर लर्नर्स (जो $H$ से ही हाइपोथीसिस आउटपुट करते हैं) और इमप्रॉपर लर्नर्स (जो $H$ के बाहर की हाइपोथीसिस आउटपुट कर सकते हैं) के बीच अंतर करता है।

एल्गोरिद्मिक दृष्टिकोण (Algorithmic Approaches)

प्रस्तावित एल्गोरिदम एक "मिक्सिंग" रणनीति का उपयोग करते हैं, जो एक्सप्लोरेशन (पूर्ण जानकारी प्राप्त करने के लिए ऑल-पॉजिटिव क्लासिफायर का उपयोग करना) और एक्सप्लोइटेशन (विशेषज्ञों के भारित वितरण से नमूना लेना) के बीच यादृच्छिक रूप से चयन करता है।

रियलाइजेबल सेटिंग (सीमित और अनंत):
- सीमित क्लासेज (Finite Classes): एल्गोरिदम सुसंगत हाइपोथीसिस के सेट से यूनिफॉर्मली सैंपल करने और एक ऑल-पॉजिटिव क्लासिफायर का उपयोग करने के बीच मिश्रण करता है। एक्सप्लोरेशन की संभावना मिस्टेक प्रोबेबिलिटी और हाइपोथीसिस सेट के आकार को कम करने के बीच संतुलन बनाने के लिए ट्यून की जाती है।
- अनंत क्लासेज (Infinite Classes): एल्गोरिदम एक भारित विशेषज्ञों की प्रणाली बनाए रखता है, जहाँ प्रत्येक विशेषज्ञ एक मानक ऑनलाइन लर्निंग एल्गोरिदम (जैसे, स्टैंडर्ड ऑप्टिमल एल्गोरिदम, SOA) में फीड किए गए एजेंटों के अनुक्रम के अनुरूप होता है। विशेषज्ञ प्रणाली को एसिमेट्रिकल रूप से अपडेट किया जाता है, चाहे वास्तविक लेबल पॉजिटिव हो या नेगेटिव, यह सुनिश्चित करते हुए कि गलत विशेषज्ञों का कुल भार पर्याप्त रूप से कम हो जाए जबकि एक रियलाइजेबल विशेषज्ञ बना रहे।
एग्नोस्टिक सेटिंग:
- लेखक एक्सपोनेंशियल वेट्स के साथ हेज (Hedge) एल्गोरिदम पर आधारित एक इमप्रॉपर रैंडमाइज्ड एल्गोरिदम (एल्गोरिदम 3) प्रस्तावित करते हैं।
- मुख्य नवाचार: एल्गोरिदम "रिवील इवेंट्स" (reveal events) का लाभ उठाता है। एक 'रिवील' तब होता है जब शिक्षार्थी ऑल-पॉजिटिव क्लासिफायर खेलता है या यदि सैंपल की गई हाइपोथीसिस हेरफेर किए गए फीचर पर $-1 $प्रेडिक्ट करती है। इन मामलों में, शिक्षार्थी यह प्रमाणित कर सकता है कि कोई हेरफेर नहीं हुआ है ($ z_t = x_t$) और सभी हाइपोथीसिस के लिए स्ट्रैटेजिक लॉस की गणना कर सकता है।
- एस्टिमेटर (Estimator): आंशिक फीडबैक को संभालने के लिए, वे इम्प्लिसिट एक्सप्लोरेशन तकनीकों से प्रेरित एक अनबायस्ड लॉस एस्टिमेटर का निर्माण करते हैं। यह एस्टिमेटर बाउंडेड है और इसका बायस और वेरिएंस नियंत्रित है, जिससे हेज एल्गोरिदम को इष्टतम रिग्रेट रेट प्राप्त करने में मदद मिलती है।

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

रियलाइजेबल सेटिंग

लोअर बाउंड: पेपर सिद्ध करता है कि किसी भी रैंडमाइज्ड लर्नर के लिए, अपेक्षित मिस्टेक की संख्या $\Omega(\min\{\sqrt{T \cdot L_{\text{dim}}(H)}, L_{\text{dim}}(H) \cdot \Delta\})$ $Ω (min {T \cdot L_{dim} (H), L_{dim} (H) \cdot Δ})$ है, जहाँ $L_{\text{dim}}(H)$ $L_{dim} (H)$ लिटलस्टोन डायमेंशन (Littlestone dimension) है और $\Delta$ $Δ$ हेरफेर ग्राफ की अधिकतम डिग्री है।
- महत्व: यह एक खुले प्रश्न को हल करता है, यह दिखाते हुए कि $T > L_{\text{dim}}(H)\Delta^2$ के लिए, रैंडमाइजेशन सुधार नहीं करता है और यह $\Omega(L_{\text{dim}}(H)\Delta)$ के डिटर्मिनिस्टिक लोअर बाउंड के समान ही रहता है।
अपार बाउंड (Upper Bound): एक रैंडमाइज्ड एल्गोरिदम प्रस्तुत किया गया है जो $O(\sqrt{T \cdot L_{\text{dim}}(H) \log \Delta})$ $O (T \cdot L_{dim} (H) lo g Δ)$ का अपेक्षित मिस्टेक बाउंड प्राप्त करता है।
- महत्व: यह $T$ के छोटे होने पर (विशेष रूप से $T < L_{\text{dim}}(H) \Delta^2 \log \Delta$ ) सबसे अच्छे ज्ञात डिटर्मिनिस्टिक अपार बाउंड $O(L_{\text{dim}}(H) \cdot \Delta \log \Delta)$ में स्पष्ट सुधार करता है।

एग्नोस्टिक सेटिंग

अपार बाउंड: लेखक अडैप्टिव एडवर्सरीज के विरुद्ध $O(\sqrt{T \log |H|})$ $O (T lo g ∣ H ∣)$ का अपेक्षित रिग्रेट प्राप्त करने वाला एक इमप्रॉपर रैंडमाइज्ड एल्गोरिदम प्रदान करते हैं।
- महत्व: यह नॉन-स्ट्रैटेजिक ऑनलाइन लर्निंग के लिए मानक इष्टतम दर से मेल खाता है, जो $O(T^{3/4} \log^{1/4}(T|H|))$ के पिछले सर्वश्रेष्ठ बाउंड में सुधार करता है।
प्रॉपर लर्नर्स के लिए लोअर बाउंड: वे सिद्ध करते हैं कि किसी भी प्रॉपर लर्नर को कम से कम $\Omega(\min\{\sqrt{T \log |H| + |H|}, \sqrt{T|H| \log |H|}\})$ $Ω (min {T lo g ∣ H ∣ + ∣ H ∣, T ∣ H ∣ lo g ∣ H ∣})$ का रिग्रेट उठाना होगा।
- महत्व: यह दर्शाता है कि इष्टतम $O(\sqrt{T \log |H|})$ दर प्राप्त करने के लिए इमप्रॉपर लर्निंग आवश्यक है। प्रॉपर लर्नर्स $T < |H|^2 / \log |H|$ के लिए स्पष्ट रूप से खराब दर का सामना करते हैं।

4. कार्य का महत्व

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

रैंडमाइजेशन की भूमिका का समाधान: यह रियलाइजेबल सेटिंग में रैंडमाइजेशन की सीमाओं को स्पष्ट करता है, यह दिखाते हुए कि जबकि यह विशिष्ट शासन (regimes) में सुधार प्रदान करता है, यह सामान्य मामले में मौलिक डिटर्मिनिस्टिक लोअर बाउंड को पार नहीं कर सकता है।
इष्टतम एग्नोस्टिक दरें: यह स्थापित करता है कि रणनीतिक सेटिंग में मानक इष्टतम रिग्रेट दर प्राप्त की जा सकती है, लेकिन केवल तभी जब शिक्षार्थी को इमप्रॉपर हाइपोथीसिस का उपयोग करने की अनुमति हो।
इमप्रॉपर लर्निंग की आवश्यकता: प्रॉपर लर्नर्स के लिए एक लोअर बाउंड सिद्ध करके, जो इष्टतम दर से अधिक है, यह पेपर रणनीतिक वातावरण में प्रॉपर और इमप्रॉपर लर्निंग के बीच एक सख्त अलगाव को उजागर करता है।
परिष्कृत बाउंड्स (Refined Bounds): परिणाम पहली बार ऐसे बाउंड प्रदान करते हैं जो स्पष्ट रूप से हाइपोथीसिस क्लास के लिटलस्टोन डायमेंशन और हेरफेर ग्राफ की अधिकतम डिग्री दोनों पर निर्भर करते हैं, जो रणनीतिक लर्निंग की जटिलता की अधिक सूक्ष्म समझ प्रदान करते हैं।

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