मल्टी-आर्म्ड क्वांटम बैंडिट्स: एक्सप्लोरेशन बनाम शोषण जब क्वांटम स्टेट्स के गुण सीखते हैं

स्रोत नोड: 1590105

जोसेप लुम्ब्रेरस1, एरक्का हापसालो1, और मार्को टोमामिचेल1,2

1सेंटर फॉर क्वांटम टेक्नोलॉजीज, नेशनल यूनिवर्सिटी ऑफ सिंगापुर, सिंगापुर
2डिपार्टमेंट ऑफ इलेक्ट्रिकल एंड कंप्यूटर इंजीनियरिंग, फैकल्टी ऑफ इंजीनियरिंग, नेशनल यूनिवर्सिटी ऑफ सिंगापुर, सिंगापुर

इस पेपर को दिलचस्प खोजें या चर्चा करना चाहते हैं? Scate या SciRate पर एक टिप्पणी छोड़ दें.

सार

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

[एम्बेडेड सामग्री]

► BibTeX डेटा

► संदर्भ

[1] टी. लट्टीमोर और सी. ज़ेपेश्वरी। "बैंडिट एल्गोरिदम"। कैम्ब्रिज यूनिवर्सिटी प्रेस. (2020)।
https: / / doi.org/ 10.1017 / १.१३,९४,२०८

[2] ए। स्लिवकिंस। "बहु-सशस्त्र डाकुओं का परिचय"। मशीन लर्निंग 12, 1–286 (2019) में नींव और रुझान।
https: / / doi.org/ 10.1561 / १.१३,९४,२०८

[3] एस. बुबेक और एन. सेसा-बियांची। "स्टोकेस्टिक और नॉनस्टोचैस्टिक मल्टी-आर्म्ड बैंडिट समस्याओं का खेद विश्लेषण"। मशीन लर्निंग 5, 1-122 (2012) में नींव और रुझान।
https: / / doi.org/ 10.1561 / १.१३,९४,२०८

[4] डी. बाउनेफौफ, आई. रिश, और सी. अग्रवाल। "बहु-सशस्त्र और प्रासंगिक डाकुओं के अनुप्रयोगों पर सर्वेक्षण"। 2020 में IEEE कांग्रेस ऑन इवोल्यूशनरी कंप्यूटेशन (CEC)। पेज 1-8. (2020)।
https:////doi.org/10.1109/CEC48606.2020.9185782

एल. तांग, आर. रोज़लेस, ए. सिंह, और डी. अग्रवाल। "प्रासंगिक डाकुओं के माध्यम से स्वचालित विज्ञापन प्रारूप चयन"। सूचना और ज्ञान प्रबंधन पर 22वें एसीएम अंतर्राष्ट्रीय सम्मेलन की कार्यवाही में। पृष्ठ 1587-1594। कम्प्यूटिंग मशीनरी के लिए एसोसिएशन (2013)।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८

[6] एम. कोहेन, आई. लोबेल, और आर. पेस लेमे। "फीचर-आधारित गतिशील मूल्य निर्धारण"। प्रबंधन विज्ञान 66, 4921–4943 (2020)।
https: / / doi.org/ 10.1287 / mnsc.2019.3485

[7] डब्ल्यू थॉम्पसन। "इस संभावना पर कि दो नमूनों के साक्ष्य के मद्देनजर एक अज्ञात संभाव्यता दूसरे से अधिक है"। बायोमेट्रिका 25, 285–294 (1933)।
https://doi.org/10.1093/​बायोमेट/25.3-4.285

[8] एच रॉबिन्स। "प्रयोगों के अनुक्रमिक डिजाइन के कुछ पहलू"। अमेरिकन मैथमेटिकल सोसाइटी का बुलेटिन 58, 527–535 (1952)।
https:/​/​doi.org/​10.1090/​S0002-9904-1952-09620-8

[9] टीएल लाइ और एच. रॉबिन्स। "असामयिक रूप से कुशल अनुकूली आवंटन नियम"। अनुप्रयुक्त गणित में अग्रिम 6, 4–22 (1985)।
https:/​/​doi.org/​10.1016/​0196-8858(85)90002-8

[10] पी. औएर, एन. सेसा-बियांची, और पी. फिशर। "मल्टी-आर्म्ड बैंडिट समस्या का परिमित-समय विश्लेषण"। मच। सीखना। 47, 235–256 (2002)।
https: / / doi.org/ 10.1023 / A: 1013689704352

[11] बी. कासाले, जी. डि मोल्फ़ेटा, एच. कादरी, और एल. रैलाइवोला। "क्वांटम बैंडिट्स"। क्वांटम मच। इंटेल। 2 (2020)।
https:/​/​doi.org/​10.1007/​s42484-020-00024-8

[12] डी. वैंग, एक्स. यू, टी. ली, और ए. चिल्ड्स। "मल्टी-आर्म्ड बैंडिट्स के लिए क्वांटम एक्सप्लोरेशन एल्गोरिदम"। आर्टिफिशियल इंटेलिजेंस पर एएएआई सम्मेलन की कार्यवाही में। खंड 35, पृष्ठ 10102–10110। (2021)।

[13] पी. रेबेंट्रोस्ट, वाई. हमौदी, एम. रे, एक्स. वांग, एस. यांग, और एम. संथा। "क्वांटम एल्गोरिदम हेजिंग और आइसिंग मॉडल के सीखने के लिए"। भौतिक। रेव ए 103, 012418 (2021)।
https: / / doi.org/ 10.1103 / PhysRevA.103.012418

[14] ओ शमीर। "बैंडिट रैखिक अनुकूलन की जटिलता पर"। लर्निंग थ्योरी पर 28वें सम्मेलन की कार्यवाही में। मशीन लर्निंग रिसर्च की कार्यवाही का खंड 40, पृष्ठ 1523-1551। पीएमएलआर (2015)।

[15] पी. रुस्मेविचिएंटोंग और जे. सितसिक्लिस। "रैखिक रूप से परिचालित डाकुओं"। संचालन अनुसंधान का गणित 35 (2008)।
https: / / doi.org/ 10.1287 / moor.1100.0446

[16] जे. बैरी, डीटी बैरी, और एस. आरोनसन। "क्वांटम आंशिक रूप से देखने योग्य मार्कोव निर्णय प्रक्रियाएं"। भौतिक। रेव। ए 90, 032311 (2014)।
https: / / doi.org/ 10.1103 / PhysRevA.90.032311

[17] एम यिंग, वाई फेंग, और एस यिंग। "क्वांटम मार्कोव निर्णय प्रक्रियाओं के लिए इष्टतम नीतियां"। इंटरनेशनल जर्नल ऑफ ऑटोमेशन एंड कंप्यूटिंग 18, 410-421 (2021)।
https: / / doi.org/ 10.1007 / s11633-021-1278-z

[18] एम. पेरिस और जे. रेहासेक। "क्वांटम राज्य अनुमान"। स्प्रिंगर पब्लिशिंग कंपनी, निगमित। (2010)। पहला संस्करण।
https: / / doi.org/ 10.1007 / b98673

[19] एस आरोनसन। "क्वांटम राज्यों की छाया टोमोग्राफी"। कम्प्यूटिंग के सिद्धांत पर 50वें वार्षिक ACM SIGACT संगोष्ठी की कार्यवाही में। पृष्ठ 325-338। STOC 2018. कंप्यूटिंग मशीनरी एसोसिएशन (2018)।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८

[20] एस. आरोनसन, एक्स. चेन, ई. हजान, एस. काले, और ए. नायक। "क्वांटम राज्यों की ऑनलाइन शिक्षा"। जर्नल ऑफ़ स्टैटिस्टिकल मैकेनिक्स: थ्योरी एंड एक्सपेरिमेंट 2019 (2018)।
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988

[21] जे. ब्रेटाग्नोल और सी. ह्यूबर। "एस्टीमेशन डेस डेंसिटेस: रिस्क मिनिमैक्स"। Zeitschrift फर Wahrscheinlichkeitstheorie und verwandte Gebiete 47, 119–137 (1979)।
https: / / doi.org/ 10.1007 / BF00535278

[22] एम. मुलर-लेनर्ट, एफ. डुपोइस, ओ. स्जेहर, एस. फेहर, और एम. टॉमामिकेल। "क्वांटम रेनी एन्ट्रॉपीज़ पर: एक नया सामान्यीकरण और कुछ गुण"। गणितीय भौतिकी जर्नल 54, 122203 (2013)।
https: / / doi.org/ 10.1063 / १.१३,९४,२०८

[23] एम. वाइल्ड, ए. विंटर, और डी. यांग। "सैंडविच्ड रेनी रिलेटिव एंट्रॉपी के माध्यम से एंटैंगलमेंट-ब्रेकिंग और हैडमार्ड चैनल्स की शास्त्रीय क्षमता के लिए मजबूत बातचीत"। गणितीय भौतिकी में संचार 331, 593–622 (2014)।
https: / / doi.org/ 10.1007 / s00220-014-2122-x

[24] डब्ल्यू होफडिंग। "संभवत: बंधित यादृच्छिक परिवर्तों की राशियों के लिए असमानताएं"। जर्नल ऑफ़ द अमेरिकन स्टैटिस्टिकल एसोसिएशन 58, 13–30 (1963)।
https: / / doi.org/ 10.1080 / १.१३,९४,२०८

[25] पी। और। "शोषण-अन्वेषण व्यापार-नापसंद के लिए विश्वास सीमा का उपयोग करना"। जे मच। सीखना। रेस। 3, 397–422 (2003)।
https: / / doi.org/ 10.5555 / १.१३,९४,२०८

[26] डी. वर्षा, टी. हेस, और एस. काकडे। "बैंडिट फीडबैक के तहत स्टोकेस्टिक लीनियर ऑप्टिमाइज़ेशन।"। लर्निंग थ्योरी पर 21वें सम्मेलन की कार्यवाही में। पृष्ठ 355-366। (2008)।

[27] पी रुस्मेविचिएंटोंग और जेएन त्सित्सिकलिस। "रैखिक रूप से परिचालित डाकुओं"। संचालन अनुसंधान का गणित 35, 395–411 (2010)।
https: / / doi.org/ 10.1287 / moor.1100.0446

[28] वाई. अब्बासी-यादकोरी, डी. पाल, और सी.एस. ज़ेपेश्वरी। "रैखिक स्टोचैस्टिक बैंडिट्स के लिए बेहतर एल्गोरिदम"। तंत्रिका सूचना प्रसंस्करण प्रणालियों में अग्रिम। वॉल्यूम 24. कुरान एसोसिएट्स, इंक। (2011)।

[29] टी एल लाइ। "अनुकूली उपचार आवंटन और मल्टी-आर्म्ड बैंडिट समस्या"। सांख्यिकी के इतिहास 15, 1091 - 1114 (1987)।
https: / / doi.org/ 10.1214 / AOS / +११७६३४९८३०

[30] एम. गुओ, जे. कान, आर. कुएंग, और जेए ट्रॉप। "इष्टतम त्रुटि सीमा के साथ फास्ट स्टेट टोमोग्राफी"। जर्नल ऑफ फिजिक्स ए: गणितीय और सैद्धांतिक 53, 204001 (2020)।
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111

[31] टी. लट्टीमोर और बी. हाओ। "बैंडिट चरण पुनर्प्राप्ति"। तंत्रिका सूचना प्रसंस्करण प्रणालियों में अग्रिम। खंड 34, पृष्ठ 18801-18811। कुरान एसोसिएट्स, इंक। (2021)।

द्वारा उद्धृत

[1] ज़ोंग्की वान, झिजी झांग, टोंगयांग ली, जियालिन झांग, और श्याओमिंग सन, "क्वांटम मल्टी-आर्म्ड बैंडिट्स एंड स्टोचैस्टिक लीनियर बैंडिट्स एन्जॉय लॉगरिदमिक रिग्रेट्स", arXiv: 2205.14988.

[2] ज़िन्यी चेन, एलाद हज़ान, टोंगयांग ली, झोउ लू, शिन्झाओ वांग, और रुई यांग, "क्वांटम राज्यों की अनुकूली ऑनलाइन शिक्षा", arXiv: 2206.00220.

उपरोक्त उद्धरण से हैं SAO / NASA ADS (अंतिम अद्यतन सफलतापूर्वक 2022-07-24 00:26:50)। सूची अधूरी हो सकती है क्योंकि सभी प्रकाशक उपयुक्त और पूर्ण उद्धरण डेटा प्रदान नहीं करते हैं।

On Crossref की उद्धृत सेवा द्वारा कार्यों का हवाला देते हुए कोई डेटा नहीं मिला (अंतिम प्रयास 2022-07-24 00:26:48)।

समय टिकट:

से अधिक क्वांटम जर्नल