क्यू-वैल्यू में असंबद्ध वृद्धि, क्यू-लर्निंग

Question

में एक ही कार्रवाई को दोहराने के बाद आवर्ती इनाम के परिणामस्वरूप मैं एक छोटे से आवेदन पर एक सरल क्यू-लर्निंग कार्यान्वयन के विकास की प्रक्रिया में हूं, लेकिन ऐसा कुछ है जो मुझे परेशान करता रहता है ।

के मानक तैयार करने क्यू सीखना

Q(S, A) = Q(S, A) + alpha * [R + MaxQ(S', A') - Q(S, A)] 

के इस राज्य K दो संभव कार्रवाई है कि मान लेते हैं, दोनों हमारे एजेंट R और R' पुरस्कार A और A' द्वारा देने पर विचार करें।

यदि हम लगभग पूरी तरह से लालची दृष्टिकोण का पालन करते हैं (मान लीजिए कि हम एक 0.1 ईपीएसलॉन मानते हैं), तो मैं सबसे पहले यादृच्छिक रूप से क्रियाओं में से एक का चयन करूंगा, उदाहरण के लिए A। अगली बार, मैं शायद (90% बार) फिर से A चुनूंगा और इससे कारण होगा कि क्यू (के, ए) बढ़ता जा रहा है और बढ़ रहा है, इस मामले को सच होने के बावजूद कि अगर मैं मौका से A' की कोशिश करता हूं, इनाम ए के समान परिमाण पर है, हम एक ऐसी स्थिति में आ जाएंगे जहां शेष सीखने के दौरान, हमारे पहले अनुमान से "पुनर्प्राप्त" करना वास्तव में असंभव है।

मुझे लगता है कि ऐसा नहीं होना चाहिए, अन्यथा एजेंट मूल रूप से नहीं सीखेंगे - यह सिर्फ एक साधारण नुस्खा का पालन करेगा: जैसा आपने पहली बार किया था सब कुछ करें।

मैं कुछ याद आ रही है? मुझे पता है कि मैं अल्फा मान को ट्विक कर सकता हूं (आमतौर पर, समय के साथ घट रहा है), लेकिन यह किसी भी तरह से हमारी स्थिति में सुधार नहीं करता है।

Answer 1

Q(K, A)minus Q(S, A) अवधि के कारण, असीम रूप से बढ़ता रहता है।

Q(S, A) <-- Q(S, A)(1 - a) + a(R + maxQ(S', A'))

यह दिखाता है कि Q(K, A) धीरे धीरे अपनी "वास्तविक" R + maxQ(S', A') का मूल्य की तरफ बढ़ता है: यह अधिक स्पष्ट करता है, तो आप के लिए नवीनीकरण नियम पुनर्लेखन है। Q(K, A) केवल उस तक पहुंचने के लिए बढ़ता है; असीम नहीं। जब यह बढ़ता रहता है (इसके वास्तविक मूल्य का अनुमान लगाया गया है), Q(K, A) अन्य A एस के लिए पकड़ सकता है।

वैसे भी, एप्सिलॉन के पूरे मुद्दे हैं कि क्या आप सीखने की प्रक्रिया अधिक लालची (अनुमानी) या खोजपूर्ण (यादृच्छिक) होना चाहता हूँ नियंत्रित करते हैं, तो यह वृद्धि करता है, तो सीखने की प्रक्रिया बहुत संकीर्ण है के लिए है।

यह भी ध्यान दें कि क्यूएल अभिसरण के लिए औपचारिक स्थितियों में से एक यह है कि (S, A) की प्रत्येक जोड़ी एक अनंत संख्या (पैराफ्रेशेड) का दौरा किया जाता है! तो हाँ, प्रशिक्षण प्रक्रिया के अंत में, आप चाहते हैं कि प्रत्येक जोड़ी को सभ्य समय का दौरा किया जाए।

गुड लक!

Answer 2

this, हम जानते हैं:

क्यू सीखने के अभिसरण किसी भी अन्वेषण नीति का उपयोग धारण, और केवल आवश्यकता है कि प्रत्येक राज्य कार्रवाई युग्म (s,a)निष्पादित होता है असीम अक्सर।

epsilon-greedy policy अन्वेषण और शोषण के बीच संतुलन है, जो दोनों अभिसरण और अक्सर अच्छे प्रदर्शन की गारंटी देता है।लेकिन व्यावहारिक समस्याओं में, हमें बेहतर रिटर्न का प्रतिनिधित्व करने के लिए सीखने की गति alpha बदलने के लिए अक्सर कुछ हेरिस्टिक की आवश्यकता होती है। अन्यथा, infinite often आवश्यकता को पूरा करना मुश्किल है।

मैं नीचे एक उदाहरण सूचीबद्ध करता हूं। यह एक शास्त्रीय समस्या है, जिसमें आपके पास ग्रिड है और आपके पास प्रत्येक सेल में संभवतः अलग इनाम राशि है। उदाहरण के लिए, एक 4x4 ग्रिड नीचे दिखाया गया है, जिसमें प्रत्येक सेल में 1 का इनाम होता है, शीर्ष-बाएं सेल को छोड़कर (आपके पास 10 की राशि के साथ एक बड़ा इनाम है)। ग्रिड में एक रोबोट चल रहा है। कानूनी कार्य LEFT, RIGHT, UP और DOWN पर जा रहे हैं, लेकिन रोबोट ग्रिड से बाहर नहीं जा सकता है।

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

+++++++++++++++++++++ 
+ 10 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 

मान लीजिए हम प्रयोग epsilon=0.1 के साथ एक epsilon-greedy policy, एक निरंतर सीखने की दर alpha=0.1। हम ग्रिड पर एक यादृच्छिक स्थिति के साथ शुरू करते हैं। जब भी हम ऊपरी बाएं कोने तक पहुंचते हैं, हम फिर से एक यादृच्छिक स्थिति के साथ पुनरारंभ करते हैं।

नीचे 200,000 चालों का सिमुलेशन चलाने का परिणाम है। बाएं सबसे अधिक ब्लॉक प्रत्येक सेल पर वर्तमान लालची नीति को दृष्टि से दिखाता है।

• --> सही
• <-- छोड़ दिया चलती
• ^ अप
• v चलती नीचे चलती

तो आप देख यह सर्वोत्कृष्ट नीति से दूर है। स्पष्ट रूप से एक इष्टतम नीति में, प्रत्येक सेल को या तो बाएं या ऊपर इंगित करना चाहिए क्योंकि हमारे पास (0,0) स्थिति पर एक बड़ा बड़ा इनाम है।

v v v v |  2  9  5  4 
v v v v |  14  98  75  14 
--> v v <-- | 258 3430 3312 245 
--> --> <-- <-- | 3270 93143 92978 3191 

सही ब्लॉक दिखाता है कि हम कितनी बार प्रत्येक सेल पर जाते हैं। आप देखते हैं कि हम नीचे की अधिकांश यात्राओं का खर्च करते हैं लेकिन हम शीर्ष पंक्ति पर बहुत दुर्लभ जाते हैं। यही कारण है कि हम अभी तक इष्टतम नीति तक नहीं पहुंच पाए हैं।

यदि हम सीखने की दर alpha=1/(number of times you visited (s,a) so far) पर बदलते हैं, तो हम 20,000 चरणों के भीतर इष्टतम नीति (नीचे दिखाए गए) तक पहुंचने में सक्षम हैं। साथ ही हम प्रत्येक सेल का दौरा करने की संख्या को समान रूप से वितरित नहीं करते हैं, हालांकि यह सही नहीं है।

--> <-- <-- <-- |  34 7997 7697 294 
^^^<-- | 731 898 524 132 
^^^^ | 709 176  88  94 
^^^^ | 245 256  96  77 

अधिक राज्यों के साथ एक बड़ा समस्या के लिए, उदाहरण के लिए, एक 10x10 ग्रिड, मैं इसे बड़ा epsilon उपयोग करना बेहतर है पाते हैं। उदाहरण के लिए, epsilon=0.5 के साथ 10x10 ग्रिड पर 80,000 चाल के बाद सिमुलेशन का परिणाम नीचे दिया गया है। यह नीचे-दाएं कोने को छोड़कर लगभग इष्टतम है। क्यू-लर्निंग की अभिसरण दर में सुधार करने में मदद के लिए सिम्युलेटेड एनीलिंग का उपयोग करने के बारे में idea भी है।

v <-- <-- <-- <-- <-- <-- <-- <-- <-- |  19 2500 1464 716 386 274 216 159 121  71 
^ <-- <-- <-- <-- v <-- <-- <-- <-- | 9617 11914 3665 1071 580 410 319 225 207 131 
^ ^^<-- <-- <-- <-- v <-- <-- | 5355 5716 2662 1675 1465 611 302 183 162 101 
^ ^^^^<-- <-- <-- <-- <-- | 1604 1887 1192 621 1056 882 693 403 206 100 
^ ^^^^^^<-- <-- <-- | 639 735 731 333 412 399 480 294 172 114 
^ ^^<--^^^<-- <--^ | 373 496 640 454 272 266 415 219 107  98 
^ ^^^^^^^<--^ | 251 311 402 428 214 161 343 176 114  99 
^ ^^^<-- -->^<-- <-- <-- | 186 185 271 420 365 209 359 200 113  70 
^ ^^^^^^^ v v | 129 204 324 426 434 282 235 131  99  74 
^ ^^^^<--^<-- <-- <-- | 100 356 1020 1233 703 396 301 216 152  78 

Btw, खिलौना समस्या के लिए मेरे अजगर कोड (~ 100 लाइनों) here है।

Answer 3

टिप्पणियों में से एक में उल्लेख किया है, गामा मूल्य जा रहा है कम से कम एक क्या guaranties कि योग सकारात्मक अनंत के बहाव नहीं होगा (यह देखते हुए कि पुरस्कार के लिए खुद को घिरा रहे हैं)।

लेकिन यह वास्तव में थोड़ी देर के लिए एक बुरी पसंद पर अटक सकता है।

आशावादी प्रारंभ: वहाँ कुछ चीजें हैं जो किया जा सकता है यदि आप आशावादी सब क्यू मूल्यों प्रारंभ करें, फिर हर बार जब आप कुछ नया करने की आप एक "मायूस" मिल जाएगा कोशिश ताकि अगली बार जब आप करेंगे कुछ और कोशिश करना चाहते हैं। यह तब तक चलता रहता है जब तक कि आपके पास प्रत्येक क्रिया के मूल्य की यथार्थवादी भावना न हो।

लाभ कार्यों के साथ कार्य करना: मामले में जहां हर कार्रवाई अच्छा है में लेकिन कुछ दूसरों से बेहतर हैं यह एक अच्छा विचार (कि कितना बेहतर इस कार्रवाई इस की उम्मीद इनाम के लिए है लाभ समारोह का उपयोग करने के लिए है राज्य) अपने पैरामीटर को अद्यतन करने के लिए। यह नीतिगत ग्रेडियेंट्स के लिए विशेष रूप से उपयोगी है।