📊 statistics

Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

यह शोध पत्र बिना आशावाद (optimism) के अनंत-क्षितिज (infinite-horizon) डिस्काउंटेड MDPs में शास्त्रीय ऑनलाइन Q-लर्निंग के लिए प्रथम रिग्रेट और सैंपल कॉम्प्लेक्सिटी बाउंड्स स्थापित करता है, यह प्रदर्शित करते हुए कि जहाँ बोल्ट्ज़मैन एक्सप्लोरेशन का प्रदर्शन महत्वपूर्ण रूप से उप-इष्टतम अंतराल (suboptimality gaps) पर निर्भर करता है, वहीं एक प्रस्तावित स्मूद्ड $\epsilon_n$ -ग्रीडी योजना, समय-असंगत स्टोकेस्टिक एप्रोक्सिमेशन (time-inhomogeneous stochastic approximation) के लिए एक नवीन उच्च-संभाव्यता एकाग्रता बाउंड (high-probability concentration bound) का लाभ उठाकर, निकट-इष्टतम और गैप-रोबस्ट गारंटी प्राप्त करती है।

मूल लेखक: Rahul Singh, Siddharth Chandak, Eric Moulines, Vivek S. Borkar, Nicholas Bambos

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

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

CC BY 4.0

मूल लेखक: Rahul Singh, Siddharth Chandak, Eric Moulines, Vivek S. Borkar, Nicholas Bambos

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

कल्पना कीजिए कि आप एक रोबोट को खजाना खोजने के लिए एक विशाल, जटिल भूलभुलैया (maze) में रास्ता बनाना सिखा रहे हैं। रोबोट के पास कोई नक्शा नहीं है; उसे केवल यह पता चलता है कि कदम उठाने पर क्या होता है (क्या वह दीवार से टकराता है? क्या उसे कोई सिक्का मिलता है?)। यह रीइन्फोर्समेंट लर्निंग (Reinforcement Learning) की दुनिया है, और जिस विशिष्ट विधि का उपयोग रोबोट सीखने के लिए करता है, उसे Q-लर्निंग (Q-Learning) कहा जाता है।

आपके द्वारा प्रदान किया गया पेपर एक बहुत ही विशिष्ट, कठिन समस्या पर काम करता है: हम यह कैसे सिद्ध करें कि यह रोबोट कुशलतापूर्वक सीख रहा है और बिना धोखाधड़ी किए बहुत अधिक समय गलतियाँ करने में बर्बाद नहीं कर रहा है?

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

1. समस्या: "ऑप्टिमिज़्म" (Optimism) वाला चीट कोड

अतीत में, शोधकर्ताओं ने यह सिद्ध करने के लिए कि रोबोट अच्छी तरह से सीखते हैं, उन्हें ऑप्टिमिज़्म (Optimism) नामक एक "चीट कोड" दिया। कल्पना कीजिए कि रोबोट को बताया गया है, "हर बार जब आप एक नया रास्ता आज़माते हैं, तो जब तक कि अन्यथा सिद्ध न हो जाए, मान लें कि यह सबसे अच्छा रास्ता है।" यह रोबط को आक्रामक रूप से अन्वेषण (explore) करने के लिए मजबूर करता है। हालांकि यह गणितीय रूप से काम करता है, लेकिन यह वास्तविक दुनिया के AI (जैसे कि वे जो वीडियो गेम खेलते हैं या रोबोट को नियंत्रित करते हैं) की तरह काम नहीं करता है। वास्तविक AI आमतौर पर अधिक सरल, अधिक "ईमानदार" रणनीतियों का उपयोग करता है जैसे कि बोल्ट्ज़मैन एक्सप्लोरेशन (Boltzmann exploration) (वर्तमान में वे कितने अच्छे दिख रहे हैं, इसके आधार पर कार्यों को आज़माना, कुछ यादृच्छिकता के साथ) या $\epsilon$ -greedy (ज्यादातर सबसे अच्छा काम करता है, लेकिन सुरक्षा के लिए कभी-कभी एक यादृच्छिक कार्य चुनता है)।

अंतराल (The Gap): किसी ने भी गणितीय रूप से यह सिद्ध नहीं किया था कि ये "ईमानदार" रणनीतियाँ बिना "ऑप्टिमिज़्म" चीट के एक सीमित समय में वास्तव में कुशलतापूर्वक सीखेंगी। बस यह मान लिया गया था कि वे काम करती हैं।

2. समाधान: रोबोट को देखने के लिए एक नया लेंस

लेखकों ने रोबोट की सीखने की प्रक्रिया को देखने के लिए एक नया गणितीय "लेंस" (एक कंसन्ट्रेशन बाउंड) विकसित किया।

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

3. दो रणनीतियाँ जिनका उन्होंने परीक्षण किया

लेखकों ने दो सामान्य तरीकों का परीक्षण किया जिनसे रोबोट तय करता है कि उसे क्या करना है:

A. बोल्ट्ज़मैन एक्सप्लोरेशन (The "Temperature" Strategy)

रोबोट एक ऐसे शेफ की तरह व्यवहार करता है जो सूप चख रहा है। यदि सूप बहुत गर्म है (उच्च "तापमान"), तो शेफ सब कुछ यादृच्छिक रूप से चखता है। जैसे-जैसे सूप ठंडा होता है (तापमान गिरता है), शेफ केवल सबसे स्वादिष्ट चम्मचों पर ध्यान केंद्रित करने लगता है।

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

B. स्मूद्ड $\epsilon$ -ग्रीडी (The "Safety Net" Strategy)

पहले रणनीति की कमजोरी को ठीक करने के लिए, उन्होंने एक हाइब्रिड बनाया। कल्पना कीजिए कि रोबोट के पास एक "सेफ्टी नेट" (सुरक्षा जाल) है।

90% समय, वह वह कार्य चुनता है जिसे वह सबसे अच्छा समझता है।
10% समय, वह यह सुनिश्चित करने के लिए एक यादृच्छिक कार्य चुनता है कि उसने कुछ छोड़ा तो नहीं है।
महत्वपूर्ण बात यह है कि यह "10%" समय के साथ धीरे-धीरे कम होता जाता है, लेकिन पूरी तरह से गायब नहीं होता।
निष्कर्ष: यह "सेफ्टी नेट" दृष्टिकोण बहुत अधिक मजबूत है। जब पथ बहुत समान दिखते हैं, तब भी रोबोट यादृच्छिक पथों की जाँच करता रहता है। उन्होंने सिद्ध किया कि यह विधि सबलीनियर रिग्रेट (sublinear regret) प्राप्त करती है।
- इसका क्या मतलब है? इसका मतलब है कि रोबोट गलतियाँ करता है, लेकिन गलतियों की दर समय के साथ धीमी हो जाती है। वह केवल हर दिन एक ही संख्या में गलतियाँ नहीं करता; वह समय के साथ और अधिक स्मार्ट होता जाता है।

4. बड़ा परिणाम: "नियर-ऑप्टिमल" बिना चीटिंग के

इस पेपर का सबसे रोमांचक दावा यह है कि उन्होंने सिद्ध किया कि यह "सेफ्टी नेट" रणनीति (Smoothed $\epsilon$ -Greedy) "ऑप्टिमिज़्म" चीट के बिना भी लगभग उतना ही अच्छा काम करती है।

गणित: उन्होंने दिखाया कि रोबोट का कुल "रिग्रेट" (खोए हुए अवसर) लगभग $N^{0.9}$ की दर से बढ़ता है (जहाँ $N$ कदमों की संख्या है)।
तुलना: "चीटिंग" विधियाँ $N^{0.5}$ तक जा सकती हैं। लेखक स्वीकार करते हैं कि उनकी विधि "चीटर्स" जितनी तेज़ नहीं है, लेकिन यह पहली बार है जब किसी ने सिद्ध किया है कि एक मानक, गैर-चीटिंग Q-लर्निंग एल्गोरिदम लंबे समय में कुशलतापूर्वक सीख सकता है।

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

लेखकों ने एक नया गणितीय उपकरण बनाया है यह सिद्ध करने के लिए कि एक रोबोट, जो मानक और ईमानदार अन्वेषण विधियों (बिना "ऑप्टिमिज़्म" चीट के) का उपयोग करके भूलभुलैया सीख रहा है, अंततः गलतियाँ करना बंद कर देगा और कुशलतापूर्वक सीखेगा, बशर्ते वह अपने निर्णय लेने की प्रक्रिया में थोड़ी सी यादृच्छिकता (randomness) बनाए रखे।

उन्होंने क्या दावा नहीं किया:

उन्होंने यह नहीं कहा कि यह विशेष रूप से लार्ज लैंग्वेज मॉडल्स (LLMs) के लिए काम करता है, हालांकि वे उल्लेख करते हैं कि RL वहां उपयोग किया जाता है।
उन्होंने यह दावा नहीं किया कि यह तुरंत स्वास्थ्य सेवा या रोबोटिक्स की समस्याओं को हल करता है; उन्होंने केवल सैद्धांतिक प्रमाण दिया है कि गणित काम करता है।
उन्होंने यह दावा नहीं किया कि उनकी विधि "चीटिंग" विधियों से तेज़ है; उन्होंने केवल यह दावा किया कि यह बिना चीट किए काम करने वाली पहली सिद्ध कुशल विधि है।

तकनीकी सारांश: समय-असंगत मार्कोव श्रृंखलाओं के साथ स्टोकेस्टिक एप्रोक्सिमेशन के संकेंद्रण के माध्यम से ऑनलाइन Q-लर्निंग का रिग्रेट और सैंपल कॉम्प्लेक्सिटी

1. समस्या विवरण (Problem Statement)

यह कार्य अनंत-क्षितिज (infinite-horizon) डिस्काउंटेड मार्कोव डिसीजन प्रोसेस (MDPs) में शास्त्रीय, मॉडल-मुक्त ऑनलाइन Q-लर्निंग के सैद्धांतिक विश्लेषण को संबोधित करता है। जबकि Q-लर्निंग एक मौलिक सुदृढीकरण शिक्षण (Reinforcement Learning - RL) एल्गोरिदम है, जो डीप Q-नेटवर्क्स (DQN) जैसे आधुनिक तरीकों का आधार है, मौजूदा परिमित-समय (finite-time) विश्लेषणों में महत्वपूर्ण सीमाएँ हैं:

ऑफलाइन पूर्वाग्रह (Offline Bias): अधिकांश सैंपल कॉम्प्लेक्सिटी परिणाम ऑफलाइन सेटिंग पर केंद्रित हैं, जहाँ डेटा एक निश्चित व्यवहार संबंधी नीति (behavioral policy) द्वारा उत्पन्न किया जाता है। ये विश्लेषण अनुमान त्रुटि ( $\|Q_n - Q^\star\|_\infty$ ) को तो नियंत्रित करते हैं लेकिन सीखने की प्रक्रिया के दौरान प्रदर्शन (regret) की गारंटी नहीं देते हैं।
आशावाद पर निर्भरता (Reliance on Optimism): ऑनलाइन Q-लर्निंग के लिए मौजूदा रिग्रेट बाउंड्स आमतौर पर "अनिश्चितता के विरुद्ध आशावाद" (जैसे, बोनस टर्म्स) या मॉडल-आधारित दृष्टिकोणों पर निर्भर करते हैं।
एक्सप्लोरेशन अंतराल (Exploration Gaps): बिना संशोधित Q-लर्निंग अपडेट के ऑनलाइन सेटिंग में उपयोग किए जाने वाले मानक एक्सप्लोरेशन रणनीतियों जैसे $\epsilon$ -greedy या बोल्ट्जमैन (softmax) एक्सप्लोरेशन के लिए कोई सैद्धांतिक गारंटी नहीं है।

मुख्य चुनौती बिना आशावाद पदों को जोड़े, मानक एक्सप्लोरेशन नीतियों का उपयोग करके ऑनलाइन Q-लर्निंग के लिए रिग्रेट (regret) और सैंपल कॉम्प्लेक्सिटी (sample complexity) गारंटी स्थापित करना है, जबकि इस तथ्य को ध्यान में रखना है कि नीति (और इस प्रकार डेटा वितरण) समय के साथ विकसित होती है, जो एक समय-असंगत (time-inhomogeneous) मार्कोवियन शोर संरचना (noise structure) बनाती है।

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

लेखक Q-लर्निंग के अभिसरण (convergence) और रिग्रेट का विश्लेषण करने के लिए स्टोकेस्टिक एप्रोक्सिमेशन (SA) पर आधारित एक नवीन विश्लेषणात्मक ढांचे को विकसित करते हैं।

2.1 समय-असंगत श्रृंखलाओं के साथ स्टोकेस्टिक एप्रोक्सिमेशन ढांचा

Q-लर्निंग अपडेट को एक कॉन्ट्रैक्टिव SA इटरेशन के रूप में प्रस्तुत किया गया है:
$x_{n+1} = x_n + \beta_n (F(x_n, y_n) - x_n + M_{n+1})$
जहाँ $x_n$ Q-वैल्यू को दर्शाता है, $y_n = (s_n, a_n)$ वर्तमान नीति द्वारा उत्पन्न स्टेट-एक्शन पेयर है, और $M_{n+1}$ मार्टिंगेल शोर (martingale noise) है।

प्रमुख नवाचार समय-असंगत मार्कोव श्रृंखला $\{y_n\}$ को संभालने में निहित है। पूर्ववर्ती कार्यों के विपरीत जो समय-समरूप (time-homogeneous) श्रृंखलाओं या समान मिश्रण समय (uniform mixing times) को मानते हैं, यह ढांचा निम्नलिखित की अनुमति देता है:

परिवर्तशील संक्रमण गतिकी (Time-Varying Transition Dynamics): ट्रांजिशन कर्नेल $p(\zeta_n, x_n)$ इटरेट $x_n$ और एक बाहरी नियंत्रण अनुक्रम $\zeta_n$ (जैसे, तापमान $\lambda_n$ या एक्सप्लोरेशन दर $\epsilon_n$ ) पर निर्भर करता है।
अनंत काल तक लुप्त होता संकुचन (Asymptotically Vanishing Contraction): कॉन्ट्रैक्शन फैक्टर $\alpha(\zeta_n)$ को $n \to \infty$ होने पर 1 की ओर अभिसरित होने की अनुमति है। यह उस परिदृश्य को मॉडल करता है जहाँ उप-इष्टतम क्रियाएं लुप्त होती संभावना के साथ चुनी जाती हैं, जिससे प्रेरित मार्कोव श्रृंखला का मिक्सिंग टाइम (mixing time) बढ़ जाता है।
लिप्सचिट्ज़ संवेदनशीलता (Lipschitz Sensitivity): इटरेट $x$ के परिवर्तनों के प्रति ट्रांजिशन कर्नेल की संवेदनशीलता को बढ़ने की अनुमति है (उदाहरण के लिए, जैसे-जैसे तापमान $\lambda_n \to 0$ होता है, सॉफ्टमैक्स नीति Q-वैल्यू के अंतर के प्रति अधिक संवेदनशील हो जाती है)।

2.2 उच्च-संभाव्यता संकेंद्रण बाउंड (High-Probability Concentration Bound)

लेखक SA इटरेट्स के लिए एक उच्च-संभाव्यता संकेंद्रण बाउंड व्युत्पन्न करते हैं। प्रमाण तकनीक में शामिल हैं:

पॉइसन समीकरण अपघटन (Poisson Equation Decomposition): परिवर्तनशील ट्रांजिशन कर्नेल से जुड़े पॉइसन समीकरण के समाधान का उपयोग करके मार्कोवियन शोर को एक मार्टिंगेल डिफरेंस सीक्वेंस और एक अवशेष पद (residual term) में बदलना।
शोर औसत (Noise Averaging): कमजोर होते संकुचन और परिवर्तनशील ट्रांजिशन कर्नेल के बावजूद शोर के क्षय (decay) को सीमित करने के लिए एक नवीन तर्क विकसित करना।
परिणाम: बाउंड यह दिखाता है कि $\|x_n - x^\star\|$ स्टेपसाइज़ शेड्यूल और कॉन्ट्रैक्शन फैक्टर के 1 की ओर बढ़ने की दर तथा ट्रांजिशन कर्नेल के परिवर्तन की दर पर निर्भर दर से घटता है।

2.3 विश्लेषित एक्सप्लोरेशन स्कीम्स

ढांचे को दो विशिष्ट एक्सप्लोरेशन नीतियों पर लागू किया गया है:

बोल्ट्जमैन Q-लर्निंग: क्रियाओं को घटते तापमान $\lambda_n$ के साथ एक सॉफ्टमैक्स वितरण $\sigma(Q_n/\lambda_n)$ के माध्यम से चुना जाता है।
स्मूद्थ $\epsilon_n$ -ग्रीडी (S $\epsilon$ G): एक यूनिफॉर्म पॉलिसी और एक सॉफ्टमैक्स पॉलिसी का एक कॉनवेक्स कॉम्बिनेशन। यह स्मूथिंग यह सुनिश्चित करने के लिए पेश की गई है कि ट्रांजिशन कर्नेल Q-वैल्यू के सापेक्ष स्मूथ बना रहे, जिससे विश्लेषण सुगम हो सके, जबकि यह प्रभावी रूप से मानक $\epsilon$ -greedy व्यवहार की नकल करती है।

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

3.1 शास्त्रीय ऑनलाइन Q-लर्निंग के लिए प्रथम रिग्रेट बाउंड्स

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

बोल्ट्जमन Q-लर्निंग: रिग्रेट MDP के सब-ऑप्टिमलिटी गैप ( $\text{gap}(M)$ $gap (M)$ ) पर महत्वपूर्ण रूप से निर्भर करता है।
- बड़े गैप के लिए, रिग्रेट सबलीनियर (sublinear) है।
- छोटे गैप के लिए, रिग्रेट बिगड़ सकता है और लीनियर ग्रोथ ( $O(N)$ ) की ओर बढ़ सकता है, जो बैंडिट्स में बोल्ट्जमन एक्सप्लोरेशन की ज्ञात सीमाओं के अनुरूप है।
स्मूद्थ $\epsilon_n$ -ग्रीडी (S $\epsilon$ G): यह स्कीम $\tilde{O}(N^{9/10})$ के निकट-गैप-रोबस्ट रिग्रेट बाउंड प्राप्त करती है। हालांकि यह आशावाद-आधारित तरीकों द्वारा प्राप्त $\tilde{O}(\sqrt{N})$ से खराब है, यह प्रदर्शित करता है कि अनमॉडिफाइड ऑनलाइन Q-लर्निंग के लिए सबलीनियर रिग्रेट प्राप्त करना संभव है।

3.2 सैंपल कॉम्प्लेक्सिटी गारंटी

लेखक उच्च-संभाव्यता सैंपल कॉम्प्लेक्सिटी बाउंड्स स्थापित करते हैं जो सब-गौसियन टेल व्यवहार प्रदर्शित करते हैं:

बोल्ट्जमन: विशिष्ट पैरामीटर विकल्पों के तहत सैंपल कॉम्प्लेक्सिटी $\tilde{O}((1-\gamma)^{-4}\epsilon^{-2})$ है, जो $b \to 0$ होने पर अनुकूलतम ऑफलाइन दर के करीब पहुँचती है।
S $\epsilon$ G: इसकी सैंपल कॉम्प्लेक्सिटी $\tilde{O}((1-\gamma)^{-5}\epsilon^{-2})$ है, जो SA तकनीकों के माध्यम से प्राप्त ऑफलाइन Q-लर्निंग के ज्ञात बाउंड्स से मेल खाती है लेकिन उन्हें ऑनलाइन सेटिंग में विस्तारित करती है।

3.3 SA के लिए नवीन संकेंद्रण बाउंड

एक प्राथमिक तकनीकी योगदान समय-असंगत गतिकी वाले कॉन्ट्रैक्टिव मार्कोवियन SA के लिए संकेंद्रण बाउंड है।

बाउंड उच्च संभाव्यता के साथ मान्य है और यह अनुमति देता है कि कॉन्ट्रैक्शन फैक्टर एसिम्प्टोटिक रूप से 1 की ओर बढ़े।
यह मामले को संभालता है जहाँ मिक्सिंग टाइम बढ़ जाता है और ट्रांजिशन कर्नेल इटरेट के साथ बदलता है।
यह परिणाम नियंत्रित मार्कोवियन शोर वाले RL और ऑप्टिमाइजेशन एल्गोरिदम के लिए स्वतंत्र रूप से महत्वपूर्ण हो सकता है।

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

यह शोध एक महत्वपूर्ण अंतर को पाटने का दावा करता है, जो मानक Q-लर्निंग एल्गोरिदम (जैसे, $\epsilon$ -greedy या बोल्ट्जमन एक्सप्लोरेशन के साथ DQN) के लिए कठोर परिमित-समय गारंटी प्रदान करता है, जिन्हें पहले ऑनलाइन सेटिंग में सैद्धांतिक औचित्य की कमी थी।

व्यावहारिक प्रासंगिकता: परिणाम उन एल्गोरिदम पर लागू होते हैं जिन्हें मॉडल-आधारित घटकों या जटिल आशावाद बोनस की आवश्यकता नहीं होती है, जो कई सफल आधुनिक RL सिस्टम की "मॉडल-फ्री" प्रकृति के अनुरूप है।
सैद्धांतिक सीमाएँ: लेखक स्वीकार करते हैं कि प्राप्त रिग्रेट दर ( $\tilde{O}(N^{9/10})$ ) आशावाद-आधारित तरीकों ( $\tilde{O}(\sqrt{N})$ ) की तुलना में उप-इष्टतम है। वे इसका श्रेय आशावाद के बिना एक्सप्लोरेशन की मौलिक सीमाओं को देते हैं, जो मल्टी-आर्म्ड बैंडिट परिणामों के साथ समानता दर्शाते हैं जहाँ $\epsilon$ -greedy और बोल्ट्जमन रणनीतियाँ UCB की तुलना में खराब दर देती हैं।
भविष्य की दिशाएँ: पेपर संभावित विस्तार की पहचान करता है, जिसमें रिग्रेट दर को बैंडिट परिणामों ( $\tilde{O}(N^{2/3})$ ) से मेल खाने के लिए सुधारना, फंक्शन एप्रोक्सिमेशन तक विश्लेषण का विस्तार करना, और औसत-रिवॉर्ड (average-reward) RL पर बाउंड लागू करना शामिल है।

संक्षेप में, यह कार्य स्थापित करता है कि शास्त्रीय ऑनलाइन Q-लर्निंग बिना किसी एल्गोरिथम संशोधन के सबलीनियर रिग्रेट और उच्च-संभाव्यता अभिसरण प्राप्त कर सकता है, बशर्ते एक्सप्लोरेशन पैरामीटर्स को सावधानीपूर्वक ट्यून किया जाए, जो समय-असंगत स्टोकेस्टिक एप्रोक्सिमेशन के लिए एक नए विश्लेषणात्मक उपकरण का लाभ उठाता है।