📊 statistics

$\varepsilon$ -Good Action Identification in Fixed-Budget Monte Carlo Tree Search

यह शोधपत्र गहराई-2 वाले वृक्षों (depth-2 trees) में $\varepsilon$ -अच्छे मैक्स-मिनन एक्शन की पहचान के लिए पहले प्रमाणित निश्चित-बजट एल्गोरिदम को प्रस्तुत करता है, जिसमें एक $\varepsilon$ -अज्ञेय (agnostic) दृष्टिकोण शामिल है जो इंस्टेंस-डिपेंडेंट त्रुटि सीमाओं को प्राप्त करता है और मानक मल्टी-आर्म्ड बैंडिट समस्याओं की तुलना में एक विशिष्ट कठिनाई संरचना को प्रकट करता है।

मूल लेखक: Yinan Li, Tuan Nguyen, Kwang-Sung Jun

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

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

CC BY 4.0

मूल लेखक: Yinan Li, Tuan Nguyen, Kwang-Sung Jun

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

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

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

यह शोध पत्र इस बारे में है कि कैसे आप अपने सीमित स्काउट्स का सबसे कुशलता से उपयोग करके सबसे अच्छी सेना को खोज सकते हैं, भले ही आपको अभी यह न पता हो कि सैनिक वास्तव में कितने मजबूत हैं।

समस्या: "कमजोर कड़ी" की पहेली

कंप्यूटर गेम्स और AI की दुनिया में (जैसे शतरंज या गो खेलने वाली प्रणालियाँ), इसे मोंटे कार्लो ट्री सर्च (Monte Carlo Tree Search) कहा जाता है।

वृक्ष (Trees): कल्पना कीजिए कि एक पेड़ है जहाँ ऊपरी शाखाएँ आपके विकल्प (सेनाएँ) हैं, और निचली पत्तियाँ संभावित परिणाम (सैनिक) हैं।
जाल (The Trap): एक साधारण दृष्टिकोण यह होगा कि आप सबसे अच्छी सेना खोजने के लिए हर सेना के हर सैनिक को जांचने के लिए स्काउट भेजें। लेकिन इससे पहले कि आप समाप्त करें, आपके स्काउट खत्म हो जाएंगे।
मोड़ (The Twist): आपको "परफेक्ट" सेना खोजने की आवश्यकता नहीं है। आपको बस एक ऐसी सेना ढूंढनी है जो "काफी अच्छी" हो (एक छोटी त्रुटि सीमा के भीतर, जिसे $\epsilon$ कहा जाता है)। यदि सबसे अच्छी सेना का सबसे कमजोर सैनिक 100 की ताकत रखता है, और आप एक ऐसी सेना पाते हैं जिसका सबसे कमजोर सैनिक 95 है, तो यह एक जीत है।

समाधान: एक मोड़ के साथ "सक्सेसिव रिजेक्ट्स" (Successive Rejects)

लेखक एक नई रणनीति प्रस्तावित करते हैं जिसे SR-MCTS (MCTS के लिए सक्सेसिव रिजेक्ट्स) कहा जाता है। इसे एक टैलेंट शो एलिमिनेशन राउंड की तरह समझें, लेकिन इसमें एक विशेष नियम है।

मानक दृष्टिकोण (दोष): आमतौर पर, इन एलिमिनेशन शो में, आप हर किसी का थोड़ा परीक्षण करते हैं, फिर सबसे कम स्कोर वाले व्यक्ति को बाहर निकाल देते हैं।
- समस्या: हमारे "सेना" वाले परिदृश्य में, यदि आप एक खराब सेना के सबसे कमजोर सैनिक को बाहर निकाल देते हैं, तो वह सेना अचानक मजबूत दिखने लगती है! (क्योंकि आपने उसकी कमजोर कड़ी को हटा दिया है)। यह सिस्टम को एक खराब सेना को बनाए रखने के लिए धोखा देता है।
लेखक का नवाचार: लेखकों ने एक "ट्री-सेफ" (Tree-Safe) एलिमिनेशन नियम बनाया है।
- नियम: यदि साक्ष्य संकेत देते हैं कि पूरी सेना खराब है, तो पूरी सेना को एक साथ बाहर निकाल दें, न कि केवल एक सैनिक को।
- क्यों? यह उस "धोखे" को रोकता है जहाँ एक कमजोर सैनिक को हटाने से एक खराब सेना अच्छी दिखने लगती है। यह सुनिश्चित करता है कि आप प्रत्येक सेना के वास्तविक 'वर्स्ट-केस' (सबसे खराब स्थिति) परिदृश्यों की तुलना कर रहे हैं।
"जादुई" विशेषता ( $\epsilon$ -Agnostic):
- आमतौर पर, एक "काफी अच्छी" सेना खोजने के लिए, आपको कंप्यूटर को बताना पड़ता है: "मैं सबसे अच्छी से 5 अंक के भीतर चाहता हूँ।"
- ब्रेकथ्रू: यह नया एल्गोरिदम आपको वह नंबर बताने की आवश्यकता नहीं देता है। इसे पहले से नहीं पता होता कि "काफी अच्छा" क्या है। फिर भी, यह स्वचालित रूप से अपनी रणनीति को समायोजित करता है। यदि सेनाएँ बहुत समान हैं, तो यह अधिक मेहनत करता है। यदि वे बहुत अलग हैं, तो यह तेजी से काम करता है। यह बिना किसी नियम को सेट किए, यह जाने बिना कि "काफी अच्छा" क्या है, सही सेना को खोज लेता है।

परिणाम: यह क्यों मायने रखता है

यह शोध पत्र गणितीय रूप से सिद्ध करता है कि यह तरीका अविश्वसनीय रूप से अच्छा काम करता है।

गति: यह पुराने तरीकों की तुलना में बहुत तेज़ी से सही उत्तर खोजता है जो हर सेना के भीतर हर छोटे पहेली को हल करने की कोशिश करते हैं।
दक्षता: यह स्काउट्स को बर्बाद होने से बचाता है। यह अपनी ऊर्जा उन "महत्वपूर्ण" सैनिकों पर केंद्रित करता है—जो वास्तव में तय करते हैं कि कोई सेना अच्छी है या बुरी—बजाय उन सैनिकों पर समय बर्बाद करने के जिनका कोई महत्व नहीं है।
"लोअर बाउंड" (Lower Bound) की खोज: लेखकों ने यह भी सिद्ध किया कि यह समस्या केवल सबसे अच्छे एकल सैनिक को चुनने की तुलना में मौलिक रूप से कठिन है। आप केवल हर सैनिक को समान नहीं मान सकते; "सेना" (वृक्ष) की संरचना खेल के नियमों को बदल देती है।

एक सरल उपमा: रेस्टोरेंट समीक्षक

कल्पना कीजिए कि आप एक खाद्य समीक्षक (Food Critic) हैं जिसके पास खाने के लिए सीमित भोजन (आपका बजट) है। आप शहर के सबसे अच्छे रेस्टोरेंट को खोजना चाहते हैं।

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

सारांश

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

तकनीकी सारांश: फिक्स्ड-बजट मोंटे कार्लो ट्री सर्च में $\epsilon$ -गुड एक्शन की पहचान

1. समस्या का निरूपण (Problem Formulation)

यह शोध पत्र डेप्थ-2 ट्री के भीतर फिक्स्ड-बजट मैक्स-मिन (max–min) एक्शन आइडेंटिफिकेशन समस्या को संबोधित करता है, जो दो-खिलाड़ी शून्य-योग (zero-sum) खेलों के लिए मोंटे कार्लो ट्री सर्च (MCTS) का एक मौलिक एब्स्ट्रैक्शन है।

सेटिंग: समस्या में $K$ सबट्री (रूट एक्शन्स) शामिल हैं, जिनमें से प्रत्येक में $L$ लीव्स (विरोधी प्रतिक्रियाएं) हैं। प्रत्येक लीफ $(i, j)$ का एक अज्ञात रिवॉर्ड डिस्ट्रीब्यूशन है जिसका माध्य $\mu_{i,j}$ है।
उद्देश्य: एक रूट एक्शन $i$ का मान उसके सबसे खराब परिणाम (worst-case outcome) द्वारा परिभाषित किया जाता है: $v_i = \min_{j \in [L]} \mu_{i,j}$ । लक्ष्य एक ऐसा रूट एक्शन $i$ पहचानना है जो इस मान को अधिकतम करता है ( $v^* = \max_i v_i$ )।
प्रतिबंध: शिक्षार्थी एक फिक्स्ड बजट $T$ के तहत कार्य करता है, जिसका अर्थ है कि उन्हें $T$ लीफ सैंपल्स को क्रमिक रूप से चुनना होगा और बिना किसी पूर्व विश्वास (confidence) के जल्दी रुकने की क्षमता के बिना एक सिफारिश देनी होगी (जैसा कि फिक्स्ड-कॉन्फिडेंस सेटिंग्स में होता है)।
अनुमानित लक्ष्य ( $\epsilon$ -good): सटीक इष्टतम (optimal) सबट्री की आवश्यकता के बजाय, यह शोध पत्र $\epsilon$ -गुड आइडेंटिफिकेशन पर ध्यान केंद्रित करता है। एक सबट्री $i$ को $\epsilon$ -गुड कहा जाता है यदि $v_i \ge v^* - \epsilon$ हो। यह छूट व्यावहारिक योजना (planning) से प्रेरित है जहाँ अनुमानित इष्टतमता पर्याप्त होती है और अक्सर सैंपल कॉम्प्लेक्सिटी को कम करती है।
$\epsilon$ -एग्नोस्टिसिटी ( $\epsilon$ -Agnosticism): एक प्रमुख डिज़ाइन बाधा यह है कि एल्गोरिदम को $\epsilon$ को इनपुट के रूप में लेने की आवश्यकता नहीं होनी चाहिए। इसे स्वचालित रूप से लक्ष्य सटीकता के अनुकूल होना चाहिए, जो बिना किसी पूर्व ज्ञान के किसी भी सार्थक $\epsilon$ के लिए गारंटी प्रदान करता है।

2. कार्यप्रणाली: MCTS के लिए सकसेसिव रिजेक्ट्स (Successive Rejects for MCTS)

लेखक एक एल्गोरिदम, सक्सेसिव रिजेक्ट्स फॉर MCTS (SR-MCTS) प्रस्तावित करते हैं, जो मल्टी-आर्म्ड बैंडिट्स से क्लासिक सक्सेसिव रिजेक्ट्स (SR) एल्गोरिदम को मैक्स-मिन सेटिंग में अनुकूलित करता है।

मैक्स-मिन ट्रीज़ में मुख्य चुनौतियाँ

मानक एलिमिनेशन रणनीतियाँ मैक्स-मिन ट्रीज़ में विफल हो जाती हैं क्योंकि:

संरचनात्मक निर्भरता (Structural Dependency): एक एकल लीफ को हटाने से एक सबट्री का एम्पेरिकल मिनिमम बदल सकता है, जिससे एक उप-इष्टतम (suboptimal) सबट्री कृत्रिम रूप से मजबूत दिखाई दे सकता है (यदि उसका वास्तविक मिनिमाइज़र हटा दिया गया हो)।
गैप कॉम्प्लेक्सिटी (Gap Complexity): कठिनाई क्रॉस-सबट्री गैप्स ( $v_i$ मानों की तुलना करना) और इंट्रा-सबट्री गैप्स (उस विशिष्ट लीफ की पहचान करना जो $v_i$ को मिनिमाइज करता है) दोनों पर निर्भर करती है।

एल्गोरिदम डिज़ाइन

एल्गोरिदम चरणों (phases) में आगे बढ़ता है, जो सक्रिय लीफ्स का एक सेट $A$ बनाए रखता है।

एम्पेरिकल गैप्स: प्रत्येक सक्रिय लीफ $(i, j)$ $(i, j)$ के लिए, एल्गोरिदम एक एम्पेरिकल गैप $\hat{\Delta}_{i,j}$ $\hat{Δ}_{i, j}$ की गणना करता है।
- यदि $i$ वर्तमान एम्पेरिकल बेस्ट सबट्री ( $\hat{a}$ ) है, तो $\hat{\Delta}_{i,j} = \hat{\mu}_{i,j} - \max_{i' \neq \hat{a}} \hat{v}_{i'}$ ।
- यदि $i$ बेस्ट नहीं है, तो $\hat{\Delta}_{i,j} = \max(\hat{v}^* - \hat{v}_i, \hat{\mu}_{i,j} - \hat{v}_i)$ ।
  ये गैप्स या तो बेस्ट प्रतियोगी से अलगाव या सबट्री के मिनिमम की आंतरिक अनिश्चितता, दोनों को कैप्चर करते हैं।
ट्री-अवेयर एलिमिनेशन: मानक SR के विपरीत, जो प्रति चरण एक आर्म हटाता है, SR-MCTS एक सबट्री एलिमिनेशन नियम का उपयोग करता है:
- यह सभी सक्रिय लीफ्स के बीच अधिकतम एम्पेरिकल गैप $\hat{\Delta}_{\max}$ की गणना करता है।
- सिंगल लीफ रिमूवल: यदि एक एकल लीफ का अधिकतम गैप है, तो उसे हटा दिया जाता है।
- सबट्री रिमूवल: यदि एक विशिष्ट सबट्री $x$ (जहाँ $x \neq \hat{a}$ ) के सभी सक्रिय लीफ्स एक साथ अधिकतम गैप $\hat{\Delta}_{\max}$ प्राप्त करते हैं, तो पूरे सबट्री को हटा दिया जाता है।
- यह नियम उस "फेलियर मोड" को रोकता है जहाँ एक लीफ को हटाने से उप-इष्टतम सबट्री का मान कृत्रिम रूप से बढ़ जाता है।
बजट आवंटन: बजट को चरणों के बीच एक शेड्यूल का उपयोग करके आवंटित किया जाता है, जो मानक SR के समान है, लेकिन चरणों की संख्या डेटा-डिपेंडेंट होती है (यह निर्धारित होता है कि कब केवल एक सबट्री शेष रह जाता है)।

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

अपर बाउंड: $\epsilon$ -एग्नोस्टिक गारंटी

प्राथमिक सैद्धांतिक योगदान थ्योरम 2 है, जो एक गैर- $\epsilon$ -गुड सबट्री की सिफारिश करने की संभावना पर एक ऊपरी सीमा (upper bound) प्रदान करता है।

कॉम्प्लेक्सिटी मेजर: बाउंड एक इंस्टेंस-डिपेंडेंट कॉम्प्लेक्सिटी टर्म $H_2(\epsilon)$ द्वारा नियंत्रित होता है, जिसे सॉर्टेड गैप्स के माध्यम से परिभाषित किया गया है:
$H_2(\epsilon) := \max_{r \ge m+1} r \Delta_{(r)}^{-2}$
जहाँ $\Delta_{(r)}$ सॉर्टेड गैप वैल्यूज़ हैं और $m$ $\epsilon$ -गुड सबट्रीज़ की संख्या से संबंधित है। यह टर्म क्रॉस-सबट्री और इंट्रा-सबट्री दोनों कठिनाइयों को कैप्चर करता है।
परिणाम: विफलता की संभावना तेजी से घटती है:
$P(\hat{i}_T \notin G_\epsilon) \le 2K^2L^2 \exp\left( - \frac{T - KL}{128 \log(KL) H_2(\epsilon)} \right)$
महत्व: एल्गोरिदम $\epsilon$ -एग्नोस्टिक है; यह $\epsilon$ को इनपुट के रूप में नहीं लेता है, फिर भी इसका एरर बाउंड अज्ञात लक्ष्य सटीकता के साथ सही ढंग से स्केल करता है।
विशेष मामला: जब $L=1$ (स्टैंडर्ड मल्टी-आर्म्ड बैंडिट्स), तो परिणाम सक्सेसिव रिजेक्ट्स के ज्ञात $\epsilon$ -गुड गारंटियों को रिकवर करता है, जो एप्रोक्सिमेट आइडेंटिफिकेशन के लिए SR का एक नया विश्लेषण प्रदान करता है।

लोअर बाउंड: स्ट्रक्चरल हार्डनेस

पेपर थ्योरम 7 में सटीक (exact) आइडेंटिफिकेशन ( $\epsilon=0$ ) के लिए एक निचली सीमा (lower bound) स्थापित करता है।

कॉम्प्लेक्सिटी: लोअर बाउंड $H_{lb}(\nu)$ द्वारा नियंत्रित होता है, जो केवल "क्रिटिकल" लीफ्स के लिए इनवर्स स्क्वेर्ड गैप्स को जोड़ता है: वे जो प्रतियोगी सबट्रीज़ के मिनिमम को निर्धारित करते हैं और वे जो इष्टतम सबट्री के मिनिमम को प्रमाणित करते हैं।
$H_{lb}(\nu) = \sum_{i \neq 1} \frac{1}{\Delta_{i,1}^2} + \sum_{j \neq 1} \frac{1}{\Delta_{1,j}^2}$
गैप एनालिसिस: लेखक ऊपरी बाउंड ( $H_2$ ) और निचली सीमा ( $H_{lb}$ ) के बीच एक अंतर दिखाते हैं। वे एक नेगेटिव रिजल्ट (Appendix E) के माध्यम से प्रदर्शित करते हैं कि मानक परम्यूटेशन-स्टाइल लोअर बाउंड तकनीकें (जो मानती हैं कि सभी आर्म्स सिमेट्रिक हैं) मैक्स-मिन ट्रीज़ के लिए $H_2$ -टाइप का लोअर बाउंड नहीं दे सकती हैं। यह उजागर करता है कि मैक्स-मिन आइडेंटिफिकेशन, अनस्ट्रक्चर्ड बेस्ट-आर्म आइडेंटिफिकेशन से संरचनात्मक रूप से भिन्न है; सभी लीफ्स समान रूप से कठिनाई में योगदान नहीं देते हैं।

प्रयोगात्मक सत्यापन

प्रयोग (Section G) SR-MCTS की तुलना निम्नलिखित से करते हैं:

यूनिफॉर्म सैंपलिंग: सभी लीफ्स को समान रूप से सैंपल करना।
बॉटम-अप SAR: पहले सबट्री के भीतर मिनिमाइजेशन को हल करना, फिर सबट्री की तुलना करना।
SAR+Compare: एक हाइब्रिड दृष्टिकोण।

निष्कर्ष: SR-MCTS सटीक और $\epsilon$ -गुड आइडेंटिफिकेशन दोनों में बेसलाइन्स से लगातार बेहतर प्रदर्शन करता है। यह एडेप्टिव सैंपल एलोकेशन प्रदर्शित करता है, जो क्रिटिकल लीफ्स पर ध्यान केंद्रित करता है और स्पष्ट रूप से उप-इष्टतम सबट्रीज़ पर प्रयास कम करता है, जबकि बॉटम-अप अप्रोच्स उप-इष्टतम सबट्रीज़ के भीतर अप्रासंगिक लीफ्स पर सैंपल बर्बाद करते हैं।

4. महत्व और दावे

यह पेपर दावा करता है कि यह फिक्स्ड-बजट मैक्स-मिन एक्शन आइडेंटिफिकेशन के लिए पहला प्रमाणित एल्गोरिथमिक गारंटी प्रदान करता है।

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

संक्षेप में, यह कार्य एक मजबूत, $\epsilon$ -एग्नोस्टिक एल्गोरिदम और स्पष्ट फाइनाइट-सैंपल गारंटी प्रदान करके, एडवरसेरियल एनवायरनमेंट में गुड स्ट्रेटेजी को पहचानने के लिए थ्योरिटिकल बैंडिट आइडेंटिफिकेशन और व्यावहारिक MCTS प्लानिंग के बीच के अंतर को पाटता है।