📊 statistics

Instance-dependent Stochastic Lipschitz bandit

यह शोधपत्र लिप्सचिट्ज़ बैंडिट्स (Lipschitz bandits) के लिए एक एल्गोरिदम प्रस्तुत करता है जो लेवल सेट्स (level sets) पर सबऑप्टिमैलिटी गैप (suboptimality gap) के समाकलनों (integrals) के माध्यम से प्रदर्शन को अभिलक्षणित करके बेहतर, इंस्टेंस-डिपेंडेंट रिग्रेट बाउंड्स प्राप्त करता है, जिससे उन स्थानीय संरचनात्मक गुणों को पकड़ा जा सके है जिन्हें पारंपरिक ज़ूमिंग-आधारित विधियाँ चूक जाती हैं।

मूल लेखक: Marius Potfer, Vianney Perchet

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

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

CC BY 4.0

मूल लेखक: Marius Potfer, Vianney Perchet

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

एक बड़ी तस्वीर: धुंधले शहर में सबसे अच्छी जगह खोजना

कल्पना कीजिए कि आप एक विशाल, धुंधले शहर (जिसे "एक्शन स्पेस" कहा जाता है) में सबसे ऊंचे बिंदु को खोजने की कोशिश कर रहे हैं। आप पूरे नक्शे को नहीं देख सकते। आप केवल एक स्थान पर खड़े हो सकते हैं, वहां के स्थानीय गाइड से पूछ सकते हैं कि ऊंचाई कितनी है, और फिर एक नए स्थान पर जा सकते हैं। गाइड आपको एक उत्तर देता है, लेकिन वे थोड़े शोर-शराबे वाले (noisy) हो सकते हैं और थोड़ा झूठ भी बोल सकते हैं (यह "नॉइजी इवैल्यूएशन" है)।

आपका लक्ष्य जितनी जल्दी हो सके, जितना संभव हो सके ऊँचा चढ़ना है। हर बार जब आप किसी ऐसी पहाड़ी पर खड़े होते हैं जो सबसे ऊँची नहीं है, तो आप थोड़ा सा "रिग्रेट" (अवसर लागत/opportunity cost) खो देते हैं।

इस समस्या को लिप्सचिट्ज बैंडिट (Lipschitz Bandit) कहा जाता है। "लिप्सचिट्ज" का सीधा सा मतलब है कि शहर में चिकनी पहाड़ियाँ और घाटियाँ हैं; यहाँ कोई ऐसी खड़ी ढलान नहीं है जो एक ही कदम में 1,000 फीट ऊपर कूद जाए। यदि आप एक बिंदु पर ऊंचाई जानते हैं, तो आप जानते हैं कि पास के बिंदुओं की ऊंचाई भी लगभग समान होगी।

पुराना तरीका: सबसे खराब स्थिति का अनुमान लगाना

लंबे समय तक, कंप्यूटर वैज्ञानिकों ने इसे सबसे खराब संभव शहर की स्थिति मानकर हल करने की कोशिश की। उन्होंने पूछा, "क्या होगा अगर पहाड़ियाँ हर जगह बहुत कठिन हों?" इससे एक ऐसा फॉर्मूला निकला जो उन्हें बताता था कि उन्हें कितने कदम उठाने की आवश्यकता होगी, वह भी बिल्कुल सबसे खराब स्थिति (worst case) में।

हालाँकि, यह दृष्टिकोण एक ऐसी यात्रा के लिए पैकिंग करने जैसा है मानकर कि वहां बर्फीला तूफान आएगा, भले ही आप एक उष्णकटिबंधीय समुद्र तट (tropical beach) पर जा रहे हों। यह सुरक्षित तो है, लेकिन अक्षम (inefficient) है। यह इस तथ्य को ध्यान में नहीं रखता कि आपका विशिष्ट शहर ऊपर एक विशाल, सपाट पठार (plateau) वाला हो सकता है, या कुछ क्षेत्रों में पहाड़ियाँ बहुत हल्की और कुछ में बहुत खड़ी हो सकती हैं।

नई खोज: चलते-चलते नक्शा पढ़ना

यह पेपर इस समस्या के बारे में सोचने का एक स्मार्ट तरीका पेश करता है। केवल "सबसे खराब स्थिति" वाले शहर को देखने के बजाय, लेखक आपके वर्तमान शहर में पहाड़ियों के विशिष्ट आकार को देखते हैं।

उन्होंने "रिग्रेट" (आप कितना समय बर्बाद करते हैं) को मापने का एक नया तरीका विकसित किया जो आपकी पहाड़ी के शिखर की ज्यामिति (geometry) पर निर्भर करता है।

"ज़ूमिंग" का उदाहरण

कल्पना कीजिए कि आप शिखर खोजने के लिए कैमरे का उपयोग कर रहे हैं।

पुराना तरीका: आप पूरी दुनिया को देखने के लिए ज़ूम आउट करते हैं, फिर धीरे-धीरे ज़ूम इन करते हैं, हर एक पिक्सेल की जाँच करते हैं। आप मान लेते हैं कि शिखर कहीं भी छिपी हुई एक छोटी, नुकीली सुई हो सकती है।
नया तरीका: आप महसूस करते हैं कि कभी-कभी शिखर एक सुई नहीं होता; वह एक विशाल, सपाट मेज की तरह होता है। यदि आप जानते हैं कि शिखर एक बड़ी मेज है, तो आपको इसके हर इंच की जाँच करने की आवश्यकता नहीं है। आप बस किनारों की जाँच कर सकते हैं और जान सकते हैं कि बीच का हिस्सा अच्छा है।

लेखक इसे "इंस्टेंस-डिपेंडेंट" (Instance-Dependent) कहते हैं। इसका अर्थ है कि एल्गोरिदम उस विशिष्ट "इंस्टेंस" (विशिष्ट फंक्शन या शहर) के अनुकूल होता है जिसका वह सामना कर रहा है।

असली मंत्र: इंटीग्रल्स और "स्लाइस"

पेपर की मुख्य गणितीय सफलता एक इंटीग्रल (स्लाइस जोड़ने का एक शानदार तरीका) का उपयोग करके समस्या की कठिनाई का वर्णन करना है।

एक ब्रेड के लोफ (loaf of bread) के रूप में शहर की कल्पना करें।

क्रस्ट (Crust): लोफ का निचला हिस्सा बहुत निचले, बुरे स्थानों को दर्शाता है। आप इन्हें जल्दी से हटा देते हैं।
क्रंब (Crumb): बीच का हिस्सा "ठीक-ठाक" स्थानों को दर्शाता है।
टॉप (Top): सबसे ऊपरी स्लाइस बेहतरीन स्थानों को दर्शाती है।

लेखक दिखाते हैं कि शिखर को खोजने में लगने वाला समय इस बात पर निर्भर करता है कि ऊपरी स्लाइस कितनी मोटी है।

यदि शीर्ष एक छोटा, नुकीला बिंदु (सुई) है, तो इसे खोजना कठिन है।
यदि शीर्ष एक चौड़ा, सपाट पठार (मेज) है, तो यह आसान है।

उनका फॉर्मूला इन निकट-इष्टतम (near-optimal) स्लाइस के "वॉल्यूम" की गणना करता है। यदि ऊपर का हिस्सा चौड़ा है, तो फॉर्मूला कहता है, "बहुत बढ़िया, आप अपनी खोज जल्दी समाप्त कर सकते हैं!" यदि ऊपर का हिस्सा संकरा है, तो यह कहता है, "ठीक है, खुदाई जारी रखें।"

दो एल्गोरिदम: PACO और SOUS

पेपर इन सिद्धांतों को व्यवहार में लाने के लिए दो विशिष्ट रणनीतियाँ (एल्गोरिदम) प्रस्तावित करता है:

PACO (फेज्ड एडेप्टिव कविंग ऑप्टिमाइजेशन): यह उस "धुंधले शहर" के लिए है जहाँ आपको एक समय में केवल एक डेटा पॉइंट मिलता है।
- यह कैसे काम करता है: यह पूरे शहर को देखकर शुरू होता है। यह परीक्षण करने के लिए कुछ यादृच्छिक (random) स्थान चुनता है। यदि कोई स्थान आशाजनक दिखता है, तो यह उसके चारों ओर एक छोटा घेरा बनाता है और अगले दौर के लिए केवल उसी घेरे पर ध्यान केंद्रित करता है। यह खोज क्षेत्र को छोटा करता रहता है, यानी जहाँ पहाड़ियाँ ऊँची दिख रही हैं, वहीं "ज़ूम इन" करता रहता है।
- जादू: यह केवल बेतरतीब ढंग से छोटा नहीं होता; यह इस आधार पर छोटा होता है कि ऊँची भूमि कितनी "मोटी" है। यदि ऊँची भूमि एक चौड़ा पठार है, तो यह उसे कुशलतापूर्वक कवर करता है।
SOUS (सीक्वेंशियल ऑप्टिमिज्म विद यूनिफॉर्म सैंपलिंग): यह तब के लिए है जब आपको पूर्ण जानकारी (full information) मिलती है (जैसे केवल एक स्थान के बजाय पूरे मौसम मानचित्र को देखना)।
- यह कैसे काम करता है: चूंकि आप पूरा नक्शा देख सकते हैं, इसलिए आपको अनुमान लगाने की आवश्यकता नहीं है। आप बस नक्शा देखते हैं, "अच्छे पर्याप्त" क्षेत्रों को ढूंढते हैं, और उन क्षेत्रों के भीतर यादृच्छिक रूप से एक स्थान चुनते हैं।
- जादू: यदि सबसे अच्छा क्षेत्र बहुत बड़ा है, तो इसकी बहुत अधिक संभावना है कि आप तुरंत एक अच्छा स्थान चुन लेंगे। यदि सबसे अच्छा क्षेत्र बहुत छोटा है, तो हो सकता है कि आप इसे मिस कर दें, लेकिन गणित यह सिद्ध करता है कि आप इसे बहुत अधिक बार मिस नहीं करेंगे।

यह क्यों महत्वपूर्ण है (पेपर के अनुसार)

लेखक सिद्ध करते हैं कि उनका नया तरीका कई स्थितियों में पुराने "वर्स्ट-केस" तरीकों की तुलना में स्पष्ट रूप से बेहतर है।

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

एक वाक्य में सारांश

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

तकनीकी सारांश: इंस्टेंस-डिपेंडेंट स्टोकेस्टिक लिप्सचिट्ज़ बैंडिट (Instance-dependent Stochastic Lipschitz bandit)

समस्या सेटिंग (Problem Setting)

यह शोध पत्र स्टोकेस्टिक लिप्सचिट्ज़ बैंडिट समस्या को संबोधित करता है, जहाँ एक शिक्षार्थी (learner) एक सीमित डोमेन $X \subset [0, 1]^d$ पर एक अज्ञात $L$ -लिप्सचिट्ज़ फलन $f: X \to \mathbb{R}$ को क्रमिक रूप से अधिकतम करने का प्रयास करता है। प्रत्येक दौर $t$ में, शिक्षार्थी एक एक्शन $x_t \in X$ चुनता है और एक शोरयुक्त रिवॉर्ड (noisy reward) $Y_t = f(x_t) + \eta_t$ प्राप्त करता है, जहाँ $\eta_t$ एक शून्य-माध्य (zero-mean), सशर्त रूप से 1-सब-गासियन (1-sub-Gaussian) शोर है। उद्देश्य अपेक्षित संचयी पछतावा (expected cumulative regret) $R_T = \mathbb{E}[\sum_{t=1}^T (f^* - f(x_t))]$ को कम करना है, जहाँ $f^* = \max_{x \in X} f(x)$ है।

जबकि मौजूदा साहित्य $\tilde{\Theta}(T^{\frac{d+1}{d+2}})$ के रूप में स्केल होने वाले वर्स्ट-केस (worst-case) पछतावा बाउंड और ज़ूमिंग डायमेंशन (zooming dimension) $d_z$ पर आधारित एडेप्टिव बाउंड $\tilde{\Theta}(T^{\frac{d_z+1}{d_z+2}})$ प्रदान करता है, लेखक तर्क देते हैं कि ये अपर्याप्त हैं। ज़ूमिंग-आधारित गारंटी केवल निकट-इष्टतम लेवल सेट्स (near-optimal level sets) की एसिम्प्टोटिक वृद्धि पर निर्भर करती है और विशिष्ट इंस्टेंस $(X, f)$ के सूक्ष्म संरचनात्मक गुणों, विशेष रूप से मैक्सिमाइज़र सेट $X^*$ की ज्यामिति को पकड़ने में विफल रहती है।

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

1. एल्गोरिद्मिक फ्रेमवर्क: PACO

लेखक बैंडिट सेटिंग के लिए फेज्ड एडेप्टिव कवरिंग ऑप्टिमाइजेशन (PACO) प्रस्तावित करते हैं। यह एल्गोरिदम चरणों (phases) $k=1, 2, \dots$ में कार्य करता है, जहाँ समय के साथ रेजोल्यूशन (resolution) $r_k = 2^{-k}$ घटता जाता है।

विवक्तीकरण (Discretization): प्रत्येक चरण में, PACO एक डिस्क्रीटाइजेशन ऑरेकल (Discretization Oracle) का उपयोग करके एक बिंदुओं का एक परिमित सेट $S_k$ बनाता है जो वर्तमान "सक्रिय" क्षेत्र $A_k$ को $r_k/L$ त्रिज्या वाले $\ell_\infty$ -बॉल्स के साथ कवर करता है। ऑरेकल यह सुनिश्चित करता है कि बिंदु अच्छी तरह से अलग (well-separated) हों और सेट का आकार क्षेत्र की कवरिंग संख्या द्वारा सीमित हो।
क्रमिक उन्मूलन (Successive Elimination): प्रत्येक चरण के भीतर, एल्गोरिदम $S_k$ पर एक क्रमिक उन्मूलन सबरूटीन (एल्गोरिदम 2) चलाता है। यह उनके माध्यों का अनुमान लगाने के लिए आर्म्स (arms) को खींचता है और उन्हें हटा देता है जो चरण की रेजोल्यूशन $r_k$ के सापेक्ष सांख्यिकीय रूप से उप-इष्टतम (suboptimal) हैं, जिसे सर्वश्रेष्ठ जीवित आर्म के लिए समायोजित किया गया है।
सक्रिय क्षेत्र अपडेट (Active Region Update): अगले चरण के लिए सक्रिय क्षेत्र को जीवित आर्म्स द्वारा केंद्रित बॉल्स के यूनियन के रूप में अपडेट किया जाता है।

2. सैद्धांतिक विश्लेषण: इंटीग्रल कैरेक्टराइजेशन (Integral Characterization)

मुख्य सैद्धांतिक योगदान एसिम्प्टोटिक डायमेंशन-आधारित बाउंड से हटकर नॉन-एसिम्प्टोटिक, इंस्टेंस-डिपेंडेंट इंटीग्रल बाउंड्स की ओर बदलाव है।

पैकिंग से इंटीग्रल का लिंक: लेखक लेवल-सेट एन्युली (level-set annuli) पर पैकिंग नंबरों के योग के रूप में एक पछतावा बाउंड व्युत्पन्न करते हैं। वे फिर गैप फंक्शन $\Delta(x) = f^* - f(x)$ के लेवल सेट्स पर एक "पीलिंग" (peeling) तर्क का उपयोग करके इस डिस्क्रीट सम को एक निरंतर इंटीग्रल से जोड़ते हैं।
ज्यामितीय धारणाएँ (Geometric Assumptions): इंटीग्रल रूप को स्थापित करने के लिए, वे एक हल्की ज्यामितीय स्थिति (Assumption 3/4) मानते हैं: किसी भी निकट-इष्टतम बिंदु के लिए, उस बिंदु पर केंद्रित बॉल का एक छोटा हिस्सा $X$ के भीतर होता है। यह सुनिश्चित करता है कि लेवल सेट्स का वॉल्यूम अनुमानित व्यवहार करता है।
ट्रंकेटेड इंटीग्रल बाउंड: परिणामी पछतावा बाउंड एक ट्रंकेटेड इंटीग्रल के रूप में होता है:
$R_T \leq C R \log(T) \int_{X \setminus X^*} \frac{dx}{\max(\Delta(x), 2^{-k_T})^{d+1}}$
जहाँ $k_T$ क्षितिज (horizon) $T$ पर चरण सूचकांक (phase index) है। यह इंटीग्रल स्पष्ट रूप से $f$ के लेवल सेट्स की ज्यामिति पर निर्भर करता है न कि केवल एक एसिम्प्टोटिक एक्सपोनेंट पर।

3. लिप्सचिट्ज़ एक्सपर्ट्स का विस्तार

यह शोध पत्र फुल-इन्फॉर्मेशन लिप्सचिट्ज़ एक्सपर्ट्स सेटिंग (एल्गोरिदम 3: SOUS) में इन परिणामों का विस्तार करता है। यहाँ, शिक्षार्थी प्रत्येक दौर में संपूर्ण रिवॉर्ड फंक्शन $f_t(\cdot)$ देखता है। लेखक एक ऐसा एल्गोरिदम प्रस्तावित करते हैं जो "उचित रूप से अच्छे" अनुमानों वाले बिंदुओं के सेट से समान रूप से नमूना (sample) लेता है। वे एक समान इंस्टेंस-डिपेंडेंट इंटीग्रल बाउंड व्युत्पन्न करते हैं और दिखाते हैं कि कैसे $X^*$ की ज्यामिति वर्स्ट-केस दरों को परिष्कृत करती है।

4. रिलैक्सेशन (Relaxations)

विश्लेषण को वन-साइडेड लिप्सचिट्ज़ (One-sided Lipschitz) फलनों (Assumption 6) के लिए विस्तारित किया गया है, जहाँ लिप्सचिट्ज़ स्थिति केवल $x \preceq y$ के लिए लागू होती है। इसके लिए डिस्क्रीटाइजेशन ऑरेकल को "फॉरवर्ड कवरिंग्स" प्रदान करने के लिए संशोधित करने और इंटीग्रल प्रमाण को "बैकवर्ड बॉक्स" का उपयोग करने के लिए समायोजित करने की आवश्यकता होती है, लेकिन मूल इंटीग्रल कैरेक्टराइजेशन वैध रहता है।

मुख्य परिणाम (Key Results)

1. इंस्टेंस-डिपेंडेंट अपर और लोअर बाउंड्स

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

अपर बाउंड: पछतावा डोमेन पर इनवर्स गैप के इंटीग्रल द्वारा सीमित है।
लोअर बाउंड: किसी भी $a_0$ -कंसिस्टेंट एल्गोरिदम (जहाँ $a_0 = \frac{d+1}{d+2}$ ) के लिए, ऐसे इंस्टेंस मौजूद हैं जहाँ पछतावा एक समान इंटीग्रल टर्म द्वारा लोअर-बाउंडेड है। यह प्रदर्शित करता है कि इंस्टेंस-डिपेंडेंट कैरेक्टराइजेशन अनिवार्य रूप से टाइट (tight) है।

2. रिफाइंड एसिम्प्टोटिक रेट्स

ज़ूमिंग डायमेंशन $d_z$ और मैक्सिमाइज़र सेट के डायमेंशन $d^*$ के संदर्भ में इंटीग्रल बाउंड्स का विश्लेषण करके, लेखक बेहतर एसिम्प्टोटिक दरें व्युत्पन्न करते हैं।

मुख्य कोरोलरी: जब मैक्सिमाइज़र सेट $X^*$ का डायमेंशन $d^* > 0$ होता है, तो पछतावा इस प्रकार स्केल होता है:
$R_T \leq \tilde{O}\left( T^{\frac{d_z+1}{\max(d_z, d^*) + 2}} \right)$
सुधार: यह शास्त्रीय ज़ूमिंग बाउंड्स ( $\tilde{O}(T^{\frac{d_z+1}{d_z+2}})$ ) की तुलना में तब स्पष्ट सुधार करता है जब $d^* > d_z$ हो।
ज्यामितीय संबंध: लेखक हल्की कनेक्टिविटी धारणाओं के तहत सिद्ध करते हैं कि $d_z + 1 \geq d^*$ , जिससे यह सुनिश्चित होता है कि एक्सपोनेंट नॉन-नेगेटिव रहे और बाउंड वैध रहे।

3. फुल-इन्फॉर्मेशन सेटिंग

लिप्सचिट्ज़ एक्सपर्ट्स सेटिंग के लिए, एक समान रिफाइंड रेट प्राप्त किया गया है:
$R_T \leq \tilde{O}\left( T^{\frac{1+d_z-\max(d_z, d^*)}{2}} \right)$
यह उजागर करता है कि मैक्सिमाइज़र सेट की ज्यामिति फुल-इन्फॉर्मेशन रिजीम में भी पछतावा सुधार को निर्देशित करती है।

महत्व और दावे (Significance and Claims)

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

एसिम्प्टोटिक्स से परे: पिछले कार्यों के विपरीत जो एसिम्प्टोटिक कॉम्प्लेक्सिटी पैरामीटर्स (जैसे $d_z$ ) पर निर्भर करते हैं, यह कार्य पछतावे को लेवल सेट्स पर सब-ऑप्टिमलिटी गैप के इंटीग्रल के माध्यम से कैरेक्टराइज़ करता है। यह इंस्टेंस $(X, f)$ के विशिष्ट ज्यामिति को कैप्चर करता है न कि केवल इसकी एसिम्प्टोटिक वृद्धि को।
ज़ूमिंग बाउंड्स का परिशोधन: यह कार्य प्रदर्शित करता है कि शास्त्रीय ज़ूमिंग बाउंड्स हमेशा टाइट नहीं होते हैं जब मैक्सिमाइज़र सेट "बड़ा" (उच्च $d^*$ ) होता है। नए बाउंड्स इन रेगिम्स में मौजूदा दरों में स्पष्ट सुधार करते हैं।
टाइटनेस (Tightness): मिलान वाले लोअर बाउंड्स प्रदान करना यह पुष्टि करता है कि व्युत्पन्न इंटीग्रल कैरेक्टराइजेशन अनिवार्य रूप से सबसे अच्छा संभव है।
सामान्यीकरण: फ्रेमवर्क को कमजोर रेगुलैरिटी धारणाओं (वन-साइडेड लिप्सचिट्ज़) और फुल-इन्फॉर्मेशन सेटिंग में अनुकूलनीय दिखाया गया है, जो निरंतर-आर्म्ड ऑप्टिमाइजेशन के लिए एक मजबूत सैद्धांतिक आधार का सुझाव देता है।

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