Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

कल्पना कीजिए कि आप एक अंतरिक्ष यान के कप्तान हैं जो एक ऐसी आकाशगंगा में नेविगेट कर रहे हैं जहाँ हर बार पलक झपकने पर भौतिकी के नियम बदल जाते हैं। आपका लक्ष्य अपना ईंधन खत्म होने से पहले अधिक से अधिक "स्टार-डस्ट" (तारा-धूल) अंक एकत्र करना है। इसके लिए, आपको एक सटीक मानचित्र और निर्देशों के एक सेट की आवश्यकता है जो आपको हर क्षण ठीक से बता सके कि किस दिशा में मुड़ना है। यह रीइन्फोर्समेंट लर्निंग (Reinforcement Learning) का हृदय है, जो कंप्यूटर विज्ञान की एक शाखा है जहाँ एक कृत्रिम "एजेंट" दुनिया के साथ अंतःक्रिया करके, चीज़ों को आज़माकर और यह देखकर कि क्या सबसे बड़ा इनाम दिलाता है, स्मार्ट निर्णय लेना सीखता है।

जिस दुनिया में यह एजेंट रहता है, उसे अक्सर एक मार्कोव डिसीजन प्रोसेस (MDP) के रूप में मॉडल किया जाता है। इसे एक विशाल, बहु-स्तरीय बोर्ड गेम के रूप में सोचें। आप एक विशिष्ट वर्ग (एक "स्टेट") में हैं, और आप चालों की एक सूची (एक "एक्शन") में से चुन सकते हैं। प्रत्येक चाल आपको एक स्कोर (एक "रिवॉर्ड") देती है और शायद आपको एक नए वर्ग पर पहुँचा देती है, लेकिन इसमें एक पेंच है: बोर्ड फिसलन भरा है। आप निश्चित रूप से नहीं जानते कि आप किस वर्ग पर उतरेंगे; आप केवल वहाँ उतरने की संभावनाओं को जानते हैं। चुनौती यह है कि यदि बोर्ड बहुत बड़ा है (लाखों वर्गों और चालों के साथ), तो एक नियमित कंप्यूटर के लिए एक आदर्श रणनीति बनाना असंभव हो जाता है। इसे "कर्स ऑफ डायमेंशनैलिटी" (dimensionality का अभिशाप) कहा जाता है।

यहाँ आता है क्वांटम कंप्यूटिंग। जबकि नियमित कंप्यूटर बिट्स (0 और 1) में सोचते हैं, क्वांटम कंप्यूटर "क्यूबिट्स" का उपयोग करते हैं जो एक साथ कई अवस्थाओं में मौजूद हो सकते हैं, जैसे कि एक घूमता हुआ सिक्का जो एक ही समय में चित (heads) और पट (tails) दोनों है। यह उन्हें समानांतर (parallel) में कई संभावनाओं को खोजने की अनुमति देता है, जिससे वे जटिल पहेलियों को पहले से कहीं अधिक तेज़ी से हल कर सकते हैं। वैज्ञानिक इस सुपरपावर का उपयोग रीइन्फोर्समेंट लर्निंग के कोड को तोड़ने के लिए करने की कोशिश कर रहे हैं, ताकि हमारे अंतरिक्ष यान के लिए एक आदर्श नेविगेशन रणनीति खोज सकें, बिना उत्तर के लिए एक जीवनकाल प्रतीक्षा किए।

शोध का बड़ा कदम: तेज़ क्वांटम नेविगेशन

इस कार्य में, लेखक, जोआओ एफ. डोरिगुएलो (Joao F. Doriguello), नए क्वांटम एल्गोरिदम का एक सेट प्रस्तावित करते हैं जो इन नेविगेशन रणनीतियों को पिछले तरीकों की तुलना में बहुत तेज़ी से खोजने के लिए डिज़ाइन किए गए हैं। वे दो विशिष्ट प्रकार के बोर्ड गेम को लक्षित करते हैं: फाइनाइट-होराइजन MDPs (जहाँ खेल निर्धारित संख्या में टर्न के बाद समाप्त हो जाता है, जैसे कि फिनिश लाइन वाली एक रेस) और इनफिनिट-होराइजन डिस्काउंटेड MDPs (जहाँ खेल अनंत काल तक चलता है, लेकिन बाद में अर्जित किए गए अंक अभी के अंकों की तुलना में कम मूल्य के होते हैं)।

लेखक का मुख्य निष्कर्ष यह है कि वे एक "लगभग पूर्ण" रणनीति (जिसे $\epsilon$-ऑप्टिमल पॉलिसी कहा जाता है) को गेम के नियमों के प्रति पहले के किसी भी तरीके की तुलना में काफी कम "क्वेरीज़" (प्रश्नों) के साथ कंप्यूट कर सकते हैं। कंप्यूटर विज्ञान की भाषा में, उन्होंने क्वेरी कॉम्प्लेक्सिटी (query complexity) में सुधार किया है। "क्वेरीज़" को यह समझने के लिए कि किसी चाल की संभावना क्या है, कंप्यूटर द्वारा गेम बोर्ड की कितनी बार 'झाँकने' की आवश्यकता होती है, समझें। जितनी कम बार झाँकना पड़ेगा, समाधान उतना ही तेज़ होगा।

उन्होंने यह कैसे किया: "सुपर-स्कैनर" और "सेफ्टी नेट"

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

1. "सुपर-स्कैनर" (क्वांटम मीन एस्टीमेशन): किसी चाल के औसत रिवॉर्ड का केवल अनुमान लगाने के बजाय, नया एल्गोरिदम एक क्वांटम ट्रिक का उपयोग करता है जो औसत और यह भी अनुमान लगाता है कि परिणाम कितने भिन्न हो सकते हैं (वैरिएंस/विचलन) - यह सब एक साथ। यह एक ऐसे स्कैनर की तरह है जो न केवल हाईवे पर कारों की औसत गति बताता है, बल्कि यह भी बताता है कि सवारी कितनी ऊबड़-खाबड़ है, वह भी एक ही नज़र में।
2. "सेफ्टी नेट" (मोनोटोनिसिटी और टोटल-वैरिएंस): लेखक शास्त्रीय गणित से एक चतुर तकनीक उधार लेते हैं जिसे "टोटल-वैरिएंस" कहा जाता है। कल्पना कीजिए कि आप एक लंबे, अंधेरे गलियारे में चल रहे हैं। यदि आप लड़खड़ाते हैं, तो आप गिर सकते हैं। लेकिन यदि आप जानते हैं कि आपकी लड़खड़ाहट एक दूसरे को संतुलित करने की प्रवृत्ति रखती है (कुछ कदम डगमगाते हैं, कुछ स्थिर), तो आप बिना डर के तेज़ी से चल सकते हैं। एल्गोरिदम इस गणित का उपयोग यह साबित करने के लिए करता है कि भले ही व्यक्तिगत अनुमान पूर्ण न हों, फिर भी पूरे खेल में कुल त्रुटि (error) छोटी रहती है। यह क्वांटम कंप्यूटर को कम सतर्क और अधिक आक्रामक खोज करने की अनुमति देता है, जिससे अनावश्यक जाँचों को छोड़ा जा सके।

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

परिणाम: एक नया रिकॉर्ड

यह शोध पत्र गणितीय रूप से सिद्ध करता है कि उनका नया एल्गोरिदम उच्च संभावना के साथ काम करता है। वे दिखाते हैं कि $S$ स्टेट्स, $A$ एक्शन्स और $H$ (या $\Gamma$) हॉराइजन वाले गेम के लिए, उनके तरीके को लगभग आवश्यक है:

• फाइनाइट-होराइजन गेम्स के लिए: $\tilde{O}\left(\frac{H^{2.5} S \sqrt{A}}{\epsilon}\right)$ क्वेरीज़।
• इनफिनिट-होराइजन गेम्स के लिए: $\tilde{O}\left(\frac{\Gamma^{2.5} S \sqrt{A}}{\epsilon}\right)$ क्वेरीज़।

यहाँ, $\epsilon$ यह दर्शाता है कि समाधान कितना सटीक होना चाहिए (एक छोटा $\epsilon$ अधिक सटीक उत्तर का अर्थ है)। "टिल्डे" ($\tilde{O}$) नोटेशन का अर्थ है कि वे कुछ बहुत छोटे, जटिल विवरणों जैसे कि लॉगरिदम को अनदेखा कर रहे हैं, और मुख्य विकास दर पर ध्यान केंद्रित कर रहे हैं।

ये संख्याएँ पिछले सर्वश्रेष्ठ क्वांटम एल्गोरिदम की तुलना में एक मापने योग्य सुधार हैं, जो $H^3$ या $\Gamma^3$ जैसी उच्च घातों पर अटके हुए थे। लेखक ने प्रभावी रूप से गणना के काम का एक महत्वपूर्ण हिस्सा कम कर दिया है। हालांकि वे अभी तक पूर्ण सैद्धांतिक सीमा (लोअर बाउंड) तक नहीं पहुँचे हैं, फिर भी उन्होंने लक्ष्य को काफी करीब ला दिया है, यह सिद्ध करते हुए कि क्वांटम कंप्यूटर वास्तव में इन जटिल निर्णय लेने वाली दुनियाों को पहले की तुलना में अधिक दक्षता के साथ नेविगेट कर सकते हैं।

संक्षेप में, यह शोध पत्र केवल यह सुझाव नहीं देता कि गेम खेलने का एक नया तरीका क्या है; यह एक कठोर गणितीय प्रमाण प्रदान करता है कि एक नई क्वांटम रणनीति मौजूद है जो पुरानी रणनीतियों की तुलना में स्पष्ट रूप से तेज़ और अधिक कुशल है, जो हमें आर्टिफिशियल इंटेलिजेंस के "कर्स ऑफ डायमेंशनैलिटी" को हल करने के एक कदम और करीब ले जाती है।