🤖 AI

Online Algorithms with Unreliable Guidance

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

मूल लेखक: Julien Dallot, Yuval Emek, Yuval Gil, Maciej Pacut, Stefan Schmid

प्रकाशित 2026-05-19

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

CC BY 4.0

मूल लेखक: Julien Dallot, Yuval Emek, Yuval Gil, Maciej Pacut, Stefan Schmid

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

कल्पना कीजिए कि आप एक जटिल, तेज़ गति वाला वीडियो गेम खेल रहे हैं जहाँ आपको पलक झपकते ही निर्णय लेने होते हैं। आप नहीं जानते कि आगे क्या होने वाला है, लेकिन आपके कान में एक "स्मार्ट दोस्त" (एक AI प्रेडिक्टर) सलाह फुसफुसा रहा है। समस्या क्या है? आपका दोस्त कभी बहुत शानदार होता है, तो कभी पूरी तरह से भ्रमित (hallucinating) हो जाता है या आपको धोखा देने की कोशिश करता है।

यह शोध पत्र इस स्थिति को संभालने का एक नया तरीका पेश करता है, जिसे Online Algorithms with Unreliable Guidance (OAG) कहा जाता है। उन्हें यह समझने की कोशिश करने के बजाय कि आपका दोस्त गलत क्यों है या उनकी गलतियों को कैसे मापा जाए, लेखक उनके सुनने का एक सरल, सार्वभौमिक नियम बताते हैं।

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

1. समस्या: "ब्लैक बॉक्स" दोस्त

अतीत में, शोधकर्ताओं ने ऐसे एल्गोरिदम बनाने की कोशिश की जो AI भविष्यवाणियों का उपयोग करते हैं। लेकिन वे विवरणों पर बहस करने में फंस गए:

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

इन बहसों ने ऐसा सामान्य समाधान बनाना कठिन बना दिया जो हर गेम के लिए काम कर सके। लेखक कहते हैं: "आइए AI के आंतरिक मस्तिष्क के बारे में बहस करना बंद करें और केवल उसके द्वारा दी गई सलाह को देखें।"

2. समाधान: "गाइड" और "सिक्का उछालना"

लेखक एक नया मॉडल प्रस्तावित करते हैं जहाँ AI कोई जटिल स्कोर या संभावना नहीं देता। इसके बजाय, यह एक सीधा उत्तर (एक "गाइड") देता है।

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

मॉडल यह मानता है कि आपके द्वारा किए जाने वाले प्रत्येक कदम के लिए, पर्दे के पीछे एक पक्षपाती सिक्का (biased coin flip) उछाला जाता है:

हेड्स (संभावना $1-\beta$ ): आपको एक "अच्छा गाइड" (एक आदर्श उत्तर) मिलता है।
टेल्स (संभावना $\beta$ ): आपको एक "बुरा गाइड" (एक धोखेबाज का उत्तर) मिलता है।

आपको यह नहीं पता कि सिक्के का कौन सा हिस्सा आया है। आपको बस यह तय करना है कि कान में फुसफुसाहट पर कितना भरोसा करना है।

3. जादुई उपकरण: "ड्रॉप और ट्रस्ट ब्लाइंडली" (DTB) कंपाइलर

यह इस पेपर का सबसे बड़ा आविष्कार है। यह एक "यूनिवर्सल अडैप्टर" है जो किसी भी मानक कंप्यूटर एल्गोरिदम (जो AI को पूरी तरह अनदेखा करता है) को एक AI-संवर्धित (AI-augmented) एल्गोरिदम में बदल सकता है।

इसे एक ट्रैफिक लाइट कंट्रोलर की तरह समझें जिसमें एक नया बटन है:

पुराना तरीका: कंट्रोलर अपने सख्त नियमों का पालन करता है (जैसे, "30 सेकंड के लिए ग्रीन")।
नया तरीका (DTB): कंट्रोलर के पास एक "ट्रस्ट पैरामीटर" ( $\tau$ $τ$ ) है।
- जब कोई अनुरोध आता है, तो कंट्रोलर एक सिक्का उछालता है।
- यदि यह "ट्रस्ट" पर आता है (संभावना $\tau$ ): यह अंधे होकर AI के गाइड का पालन करता है, लेकिन केवल तभी जब गाइड एक वैध चाल सुझाता हो।
- यदि यह "डाउट" पर आता है (संभावना $1-\tau$ ): यह AI को पूरी तरह से अनदेखा कर देता है और अपने मूल, सुरक्षित नियमों का पालन करता है।

यह क्यों शानदार है?
आपको यह जानने की ज़रूरत नहीं है कि AI का दिन अच्छा चल रहा है या बुरा। आपको बस एक "ट्रस्ट लेवल" चुनना है (मान लीजिए 50%)। गणित गारंटी देता है कि:

यदि AI सटीक है, तो आप लगभग उतना ही अच्छा प्रदर्शन करेंगे जितना कि यदि आप भविष्य जानते होते।
यदि AI बहुत खराब है, तो आप लगभग उतना ही अच्छा करेंगे जितना कि यदि आपने कभी उसकी बात न सुनी होती।
यदि AI "ठीक-ठाक" है, तो आप कहीं बीच में होंगे।

4. "एनीटाइम" गारंटी

आमतौर पर, कंप्यूटर वैज्ञानिक देखते हैं कि एक पूरे गेम में एल्गोरिदम कैसा प्रदर्शन करता है। लेकिन क्या होगा यदि AI शुरुआत में अच्छा शुरू होता है, फिर बीच में बहुत खराब हो जाता है?

लेखक "Anytime Competitiveness" पेश करते हैं। इसका मतलब है कि एल्गोरिदम गारंटी देता है कि वह हर एक क्षण में अच्छा प्रदर्शन करेगा, न कि केवल अंत में।

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

5. सिद्धांत का परीक्षण

लेखकों ने इस "DTB कंपाइलर" का तीन क्लासिक कंप्यूटर साइंस समस्याओं पर परीक्षण किया:

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

सारांश

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

यह "अनुमान लगाने" (AI) को "करने" (एल्गोरिदम) से अलग करता है, जिससे हम उनकी गलतियों का बंधक बने बिना AI सहायकों का उपयोग कर सकते हैं।

तकनीकी सारांश: अविश्वसनीय मार्गदर्शन के साथ ऑनलाइन एल्गोरिदम

समस्या विवरण

यह शोध पत्र लर्निंग-ऑगमेंटेड ऑनलाइन एल्गोरिदम (learning-augmented online algorithms) को डिजाइन करने की चुनौती को संबोधित करता है—ऐसे एल्गोरिदम जो प्रदर्शन में सुधार के लिए मशीन लर्निंग भविष्यवाणियों का उपयोग करते हैं, जबकि सबसे खराब स्थिति (worst-case) की गारंटी भी बनाए रखते हैं। इन एल्गोरिदम के विश्लेषण के लिए मौजूदा ढांचे (frameworks) में व्यापकता का अभाव है। वे आमतौर पर विशिष्ट प्रेडिक्शन सेमेंटिक्स (यह परिभाषित करना कि भविष्यवाणी क्या दर्शाती है), एरर फंक्शन्स (समस्या के उदाहरणों या इष्टतम समाधानों के सापेक्ष भविष्यवाणी की गुणवत्ता को मापना), या प्रोबिंग रणनीतियों (भविष्यवाणी की सटीकता का अनुमान लगाना) पर निर्भर करते हैं। ये निर्भरताएं सैद्धांतिक गारंटियों की प्रयोज्यता को सीमित करती हैं, जिससे परिणाम विभिन्न समस्याओं के बीच तुलनात्मक नहीं रह जाते और धारणा-मुक्त असंभवता परिणामों (assumption-free impossibility results) को प्राप्त करना कठिन हो जाता है।

मुख्य समस्या यह स्थापित करना है कि भविष्यवाणियों के साथ ऑनलाइन निर्णय लेने का एक ऐसा मॉडल, जहाँ औपचारिक गारंटी केवल समस्या की संरचना पर निर्भर हो (न कि प्रेडिक्टर-विशिष्ट विकल्पों जैसे कि त्रुटि की प्रकृति या भविष्यवाणी के अर्थ पर)।

कार्यप्रणाली: OAG मॉडल

लेखक ऑनलाइन एल्गोरिदम विद अनरिलायबल गाइडेंस (OAG) पेश करते हैं, जिसे रिक्वेस्ट-आंसर गेम्स (request-answer games) के दृष्टिकोण से तैयार किया गया है। यह मॉडल प्रेडिक्टिव और एल्गोरिथमिक घटकों को तीन प्रमुख नवाचारों के माध्यम से स्पष्ट रूप से अलग करता है:

गाइडेंस (प्रेडिक्शन सेमेंटिक्स): अमूर्त भविष्यवाणी प्रकारों को परिभाषित करने के बजाय, यह मॉडल मानता है कि भविष्यवाणियाँ सीधे समस्या के आंसर स्पेस (उत्तर स्थान) से ली गई गाइडेंस (मार्गदर्शन) हैं। एक अनुरोध $\rho_t$ के लिए, गाइडेंस $\gamma_t$ एक संभावित उत्तर है जिसे प्रेडिक्टर सुझाता है। यह विभिन्न समस्याओं में सेमान्टिक्स को एकीकृत करता है (जैसे, कैश पेज को हटाने या नोड को मैच करने का सुझाव देना)।
द गाइड एंड बैड गाइडेंस (त्रुटि मॉडलिंग): मॉडल एक "गाइड" पेश करता है जो गाइडेंस उत्पन्न करता है। आदर्श रूप से, गाइड को पूरे इनपुट अनुक्रम का ज्ञान होता है और वह इष्टतम उत्तर प्रदान करता है। हालाँकि, मॉडल अविश्वसनीयता को भी ध्यान में रखता है: प्रत्येक चरण में, एल्गोरिदम को दी गई गाइडेंस या तो इष्टतम गाइडेंस होती है (संभावना $1-\beta$ के साथ), या एक एडवर्सैरियल रूप से दूषित (adversarially corrupted) गाइडेंस होती है (संभावना $\beta$ के साथ)। पैरामीटर $\beta$ "बैड गाइडेंस" (खराब मार्गदर्शन) की संभावना को दर्शाता है। यह विशिष्ट त्रुटि मेट्रिक्स के बजाय विफलता के एक संभाव्य मॉडल के रूप में कार्य करता है।
एनीटाइम कॉम्पिटिटिवनेस (Anytime Competitiveness): समय के साथ बदलते प्रेडिक्टर की सटीकता की समस्या को हल करने के लिए (जो स्थिर प्रोबिंग रणनीतियों को बाधित करती है), लेखक एनीटाइम कॉम्पिटिटिवनेस को परिभाषित करते हैं। एक एल्गोरिदम 'एनीटाइम $c$ -कॉम्पिटिटिव' है यदि उसका प्रदर्शन अनुपात उत्तरों के इतिहास के आधार पर, इनपुट के प्रत्येक उप-अनुक्रम (subsequence) के लिए बना रहता है। यह सुनिश्चित करता है कि एल्गोरिदम को $\beta$ को गतिशील रूप से प्रोब करने या अनुमान लगाने की आवश्यकता नहीं है; वे $\beta$ के उतार-चढ़ाव के बावजूद अच्छा प्रदर्शन करते हैं।

DTB कंपाइलर

एक केंद्रीय योगदान ड्रॉप-ऑर-ट्रस्ट-ब्लाइंडली (DTB) कंपाइलर है। यह एक सामान्य, ब्लैक-बॉक्स रूपांतरण है जो किसी भी मानक, प्रेडिक्शन-मुक्त रैंडमाइज्ड ऑनलाइन एल्गोरिदम ($Alg$) को एक लर्निंग-ऑगमेंटेड OAG एल्गोरिदम ( $Alg^*$ ) में बदल देता है।

DTB तंत्र प्रत्येक आने वाले अनुरोध के लिए इस प्रकार कार्य करता है:

मान लीजिए $D_t$ वह संभाव्यता वितरण (probability distribution) है जिससे मूल एल्गोरिदम $Alg$ एक उत्तर चुनता है।
मान लीजिए $\gamma_t$ आने वाली गाइडेंस है।
संभावना $\tau$ (ट्रस्ट पैरामीटर) के साथ, $Alg^*$ अंधाधुंध रूप से $\gamma_t$ को अपना लेता है (बशर्ते $\gamma_t$ , $D_t$ के सपोर्ट में एक वैध उत्तर हो)।
संभावना $1-\tau$ के साथ, $Alg^*$ गाइडेंस को अनदेखा कर देता है और $D_t$ से एक उत्तर चुनता है।

यह सरल नियम एल्गोरिदम को सटीक भविष्यवाणियों का लाभ उठाने की अनुमति देता है, जबकि भविष्यवाणियां अविश्वसनीय होने पर मूल एल्गोरिदम की मजबूती (robustness) पर वापस लौटने की सुविधा भी देता है।

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

यह शोध पत्र DTB कंपाइलर को तीन क्लासिक ऑनलाइन समस्याओं पर लागू करता है, जिससे कंसिस्टेंसी (जब $\beta=0$ हो) और रोबस्टनेस (जब $\beta=1$ हो) के बीच नए ट्रेड-ऑफ, साथ ही मध्यवर्ती $\beta$ के लिए स्मूथनेस गारंटी प्राप्त होती है।

1. ऑनलाइन बाईपार्टाइट मैचिंग (एडवर्सैरियल अराइवल)

संदर्भ: लेखक रैंकिंग (Karp, Vazirani, Vazirani) एल्गोरिदम पर DTB लागू करते हैं।
महत्व: यह एडवर्सैरियल अराइवल ऑर्डर के तहत ऑनलाइन बाईपार्टाइट मैचिंग के लिए पहला गैर-तुच्छ (non-trivial) लर्निंग-ऑगमेंटेड एल्गोरिदम है। पिछले कार्यों ने रैंडम अराइवल या विशिष्ट ग्राफ मॉडल पर ध्यान केंद्रित किया था।
परिणाम: रैंकिंग-DTB एल्गोरिदम निम्नलिखित एनीटाइम कॉम्पिटिटिव रेशियो प्राप्त करता है:
$\max \left\{ \frac{1}{2}, (1 - \beta\tau) \cdot \frac{1 - e^{-(1-\tau)}}{1-\tau} \right\}$
यह मानक कॉम्पिटिटिव रेशियो ( $1 - 1/e$ जब $\tau \to 0, \beta=0$ ) और रोबस्टनेस बाउंड ( $1/2$ जब $\beta=1$ ) के बीच एक सुचारू इंटरपोलेशन प्रदान करता है।

2. ऑनलाइन कैशिंग

संदर्भ: लेखक रैंडम मार्क (Random Mark) एल्गोरिदम पर DTB लागू करते हैं।
परिणाम: मार्किंग-DTB एल्गोरिदम निम्नलिखित एनीटाइम कॉम्पिटिटिव रेशियो प्राप्त करता है:
$\min \left\{ \frac{2}{\tau(1-\beta)}, \frac{2H_k}{1-\tau\beta}, k \right\}$
जहाँ $H_k$ $k$ -वाँ हार्मोनिक नंबर है।
महत्व: एल्गोरिदम एसिम्प्टोटिकली ऑप्टिमल कांस्टेंट कंसिस्टेंसी और लॉगरिदमिक रोबस्टनेस प्राप्त करता है। लेखक नोट करते हैं कि हालांकि बाउंड्स अत्याधुनिक परिणामों से मेल खाते हैं, लेकिन एल्गोरिदम मौजूदा लर्निंग-ऑगमेंटेड समाधानों की तुलना में अधिक सरल है।

3. यूनिफॉर्म मेट्रिकल टास्क सिस्टम्स (MTS)

संदर्भ: लेखक बोरोडिन, लिनियल और सैक्स द्वारा किए गए क्लासिकल एल्गोरिदम को OAG मॉडल में विस्तारित करते हैं।
परिणाम: MTS-DTB एल्गोरिदम निम्नलिखित एनीटाइम कॉम्पिटिटिव रेशियो प्राप्त करता है:
$2 \cdot \min \left\{ \frac{1}{\tau(1-\beta)} + 1, \frac{1-\tau}{(1-\tau\beta)^2} H_n + 1, n \right\}$
महत्व: यह यूनिफॉर्म मेट्रिक मामले के लिए इष्टतम कंसिस्टेंसी और रोबस्टनेस ट्रेड-ऑफ प्रदान करता है।

महत्व और दावे

शोध पत्र का दावा है कि OAG मॉडल एक स्वच्छ, जेनेरिक ढांचा प्रदान करता है जो प्रेडिक्टर की विशिष्टताओं से एल्गोरिदम के डिजाइन को अलग करता है। भविष्यवाणियों को "गाइडेंस" के रूप में मानने और त्रुटियों को संभाव्य "बैड गाइडेंस" पैरामीटर के माध्यम से मॉडल करने से, यह मॉडल एरर फंक्शन और प्रेडिक्शन सेमेंटिक्स के संबंध में पिछले दृष्टिकोणों की विसंगतियों से बचता है।

लेखक इस बात पर जोर देते हैं कि DTB कंपाइलर किसी भी मानक, प्रेडिक्शन-मुक्त रैंडमाइज्ड ऑनलाइन एल्गोरिदम को लर्निंग-ऑगमेंटेड OAG एल्गोरिदम में बदलने के लिए एक व्यवस्थित विधि के रूप में कार्य करता है, जो एक "कैनोनिकल रेफरेंस पॉइंट" है। परिणाम प्रदर्शित करते हैं कि एक सरल "ट्रस्ट और ड्रॉप" रणनीति विविध समस्या डोमेन में मजबूत सैद्धांतिक गारंटी प्रदान कर सकती है।

सीमाएं

लेखक OAG मॉडल की दो प्राथमिक सीमाओं को स्वीकार करते हैं:

संभाव्य धारणा (Probabilistic Assumption): मॉडल प्रत्येक चरण पर "बैड गाइडेंस" पैरामीटर $\beta$ के लिए स्वतंत्र कॉइन टॉस (coin tosses) मानता है। हालांकि इसे प्रेडिक्टर-विशिष्ट धारणाओं से बचने के लिए डिज़ाइन किया गया है, फिर भी यह प्रेडिक्टर के व्यवहार पर एक संभाव्य संरचना लागू करता है।
क्वांटिटेटिव बनाम क्वालिटेटिव एरर्स: मॉडल क्वांटिटेटिव एरर्स ( $\beta$ के माध्यम से) को कैप्चर करता है, लेकिन यह क्वालिटेटिव एरर्स (जैसे, विशिष्ट प्रकार की गलत लेबलिंग) को एरर-फंक्शन-आधारित मॉडलों की तरह प्रभावी ढंग से व्यक्त नहीं कर सकता है। लेखक सुझाव देते हैं कि OAG मॉडल उन समस्याओं के लिए सबसे उपयुक्त है जिनमें लंबे इनपुट अनुक्रम होते हैं, जबकि "वन-शॉट" समस्याओं को क्वांटिटेटिव एरर कैरेक्टराइजेशन से अधिक लाभ हो सकता है।