کیو-یادگیری

تکنبک یادگیری تقویتی کیو_یادگیری به روس ریاضیاتی

کیو-یادگیری تکنیک یادگیری تقویتی است که با یادگیری یک تابع اقدام/مقدار، سیاست مشخصی را برای انجام حرکات مختلف در وضعیت‌های مختلف دنبال می‌کند. یکی از نقاط قوت این روش، توانایی یادگیری تابع مذکور بدون داشتن مدل معینی از محیط می‌باشد. اخیراً در این روش اصلاحی با نام کیو-یادگیری تأخیری انجام شده که بهبود قابل توجهی ایجاد نموده‌است. در روش اخیر یادگیری PAC با فراینده‌های تصمیم مارکوف ترکیب شده‌اند. کیو-یادگیری در تلاش است با توجه به شرایط فعلی، بهترین اقدامات را انجام دهد. این الگوریتم خارج‌از خط‌مشی در نظر گرفته می‌شود. چراکه، تابع کیو-یادگیری از اقداماتی خارج‌از خط‌مشی فعلی یادمی‌گیرد. به‌طور کلی می‌توان گفت که، کیو-یادگیری به‌دنبال یادگیری خط‌مشی است تا مجموع پاداش را بیشینه کند.

الگوریتم

در اینجا مدل مسئله تشکیل شده از یک عامل، وضعیت‌ها یا حالت S و مجموعه از اقدامات یا عمل A برای هر وضعیت. با انجام یک اقدام $a\in A$، عامل یا بازیگر از یک وضعیت به وضعیت بعدی حرکت کرده و هر وضعیت پاداشی به عامل می‌دهد. هدف عامل حداکثر کردن پاداش دریافتی کل خود است. این کار با یادگیری اقدام بهینه برای هر وضعیت انجام می‌گردد. الگوریتم دارای تابعی است که ترکیب حالت/اقدام را محاسبه می‌نماید:

$Q:S\times A\to \mathbb {R}$

قبل از شروع یادگیری، جدول کیو مقدار ثابتی را که توسط طراح انتخاب شده برمی‌گرداند. سپس هر بار که به عامل پاداش داده می‌شود، مقادیر جدیدی برای هر ترکیب وضعیت/اقدام محاسبه می‌گردد. هسته الگوریتم از یک بروز رسانی تکراری ساده تشکیل شده‌است. به این ترتیب که بر اساس اطلاعات جدید مقادیر قبلی اصلاح می‌شود.

$Q(s_{t},a_{t})\leftarrow \underbrace {Q(s_{t},a_{t})} _{\rm {old~value}}+\underbrace {\alpha _{t}(s_{t},a_{t})} _{\rm {learning~rate}}\times \left[\overbrace {\underbrace {R(s_{t})} _{\rm {reward}}+\underbrace {\gamma } _{\rm {discount~factor}}\underbrace {\max _{a_{t+1}}Q(s_{t+1},a_{t+1})} _{\rm {max~future~value}}} ^{\rm {learned~value}}-\underbrace {Q(s_{t},a_{t})} _{\rm {old~value}}\right]$

که $R(s_{t})$ پاداش حالت $s_{t}$ و عمل $\alpha _{t}(s,a)$ است. نرخ یادگیری ($0<\alpha \leq 1$) ممکن است برای همه زوج‌ها یکسان باشد. مقدار عامل تخفیف $\gamma$ بگونه است که $0\leq \gamma <1$

فرمول فوق معادل عبارت زیر است: $Q(s_{t},a_{t})\leftarrow Q(s_{t},a_{t})(1-\alpha _{t}(s_{t},a_{t}))+\alpha _{t}(s_{t},a_{t})[R(s_{t})+\gamma \max _{a_{t+1}}Q(s_{t+1},a_{t+1})]$

یک اپیزود الگوریتم وقتی $s_{t+1}$ به وضعیت نهایی می سد پایان می‌یابد. توجه کنید که برای همه وضعیت‌های نهایی $s_{f}$ و $Q(s_{f},a)$ مربوطه هیچگاه بروز نمی‌شود و مقدار اولیه خود را حفظ می‌کند.

تأثیر متغیرها بر الگوریتم

نرخ یادگیری

این نرخ تعیین می‌کند که تا چه میزان اطلاعات به‌دست آمده جدید بر اطلاعات قدیمی ترجیح داده شود. مقدار صفر باعث می‌شود عامل چیزی یادنگیرد و مقدار یک باعث می‌شود عامل فقط اطلاعات جدید را ملاک قرار دهد.

عامل تخفیف

عامل تخفیف به‌صورت مستقیم روی پاداش منتقل شده از محیط به بازیگر، تأثیر می‌گذارد

عامل تخفیف اهمیت پاداش‌های آینده را تعیین می‌کند. مقدار صفر باعث می‌شود عامل ماهیت فرصت طلبانه گرفته و فقط پاداش‌های فعلی را مد نظر قرار می‌دهد. در حالی که مقدار یک عامل را ترغیب می‌کند برای یک دوره زمانی طولانی برای پاداش تقلا کند. اگر این عامل، یک یا بیشتر از یک باشد مقادیر در جدول کیو واگرا می‌شود.

شرایط اولیه (Q_0)

از آنجایی که یادگیری کیو یک الگوریتم تکرار شونده است، شرایط اولیه را به‌صورت شهودی فرض می‌کند و سپس بروزشدن‌ها از آن آغاز می‌شود. شرایط اولیه خوشبینانه باعث می‌شود خیلی سریع ماتریس کیو به یک مقدار مشخص همگرا شود و در مقایسه با شرایط اولیه تصادفی، به نتایج بهتری در زمان آموزش مدل خواهد رسید ولی در هنگام کارکردن با آن در داده‌های تست، این موضوع برقرار نیست.

کارایی عملی

در ساده‌ترین شکل کیو-یادگیری از جداول برای ذخیره داده استفاده می‌شود. این روش با پیچیده شدن سیستم مورد نظر، به سرعت کارایی خود را از دست می‌دهد. یک راه حل استفاده از شبکه عصبی به عنوان تخمین‌گر تابع است. از این روش تسارو در بازی تخته نرد استفاده کرد.

تخمین‌گر تابع

گاهی اوقات که فضای حالت ما بزرگ می‌شود یا به سمت پیوسته می‌رود، دیگر بصرفه نیست از ماتریس کیو معمولی استفاده کنیم، زیرا که اردر محاسباتی و فضا، بالا خواهد رفت. در این زمان‌ها ما از تخمین‌گر تابع استفاده می‌کنیم. یک راه برای تشکیل تخمین‌گر تابع، استفاده از شبکه عصبی مصنوعی است و راه دیگر، استفاده از قوانین فازی پراکنده خواهد بود.

هرچند ماتریس کیو گسسته، درک بیشتری برای انسان داشت، اما تخمینگر تابع سرعت پردازش را بهبود و اردر فضایی را کاهش می‌دهد زیرا در بعضی اوقات تجربیات قبلی را به تجربیات فعلی تعمیم می‌دهد.

گسسته سازی(Quantization)

یک روش دیگر برای کاهش فضای حالت/عمل گسسته سازی فضا است. برای مثال بازی تعادل چوپ روی انگشت را درنظر بگیرید. در این بازی ما یک حالت را به وسیلهٔ موقعیت انگشت در فضا بر روی چوب، سرعت، زاویه چوب و سرعت زاویه ای مشخص می‌کنند. اما مشکل در این است که ممکن است بینهایت حالت وجود داشته باشد؛ مثلاً موقعیت انگشت در فضا بر روی چوب، از نقطهٔ شروع خود می‌تواند بینهایت فاصله ممکن داشته باشد. ما به وسیله گسسته سازی می‌توانیم حالت‌های نزدیک به هم را در یک دسته قرار دهیم و فضای حالت را محدود تر کنیم.

تاریخچه

کیو-یادگیری اولین بار توسط واتکینز معرفی شد. in 1989. برهان همگرایی بعداً توسط واتکینز و دایان ارائه شد. in 1992.

واتکینز اولین بار در مقاله ای با عنوان «یادگیری از پاداش تاخیری» در رسالهٔ دکترایش به این موضوع اشاره کرد. هشت سال زودتر در سال ۱۹۸۱ مسئله ای با عنوان «یادگیری تقویتی تاخیری» توسط بولونسزکی حل شد.

درسال۲۰۱۴ تیم گوگل دیپ مایند یادگیری کیو را با یادگیری عمیق ترکیب کرد و با نام «یادگیری عمیق کیو» منتشر کرد که می‌توانست بازی آتاری۳۶۰۰ را در سطح انسان بازی کند.

مشتقات

یادگیری عمیق کیو

یادگیری عمیق کیو

در یادگیری کیو معمولی، فقط اعداد داخل ماتریس اهمیت دارند زیرا فضای حالت محیط مارا مشخص می‌کنند، اما با بزرگتر شدن محیط مسئله، این نوع یادگیری کاربرد خود را از دست می‌دهد و نمی‌تواند در زمان معقول به جواب برسد. اینجا زمانی بود که تیم گوگل دیپ مایند، یادگیری عمیق کیو را وارد میدان کرد. در این الگوریتم به‌جای ماترس کیو اولیه، ما از یک شبکه عصبی استفاده می‌کنیم و هر اکشن را با توجه به خروجی شبکه عصبی پیش‌بینی می‌کنیم. این روش بر این قاعده توجیه می‌شود که مقادیر داخل ماتریس کیو، فقط اهمیت نسبی دارند و هرکدام جدا جدا تأثیر خاصی در مسئله ندارند.

یادگیری دوگانه کیو

همان‌طور که دیدیم، یادگیری کیو معمولی بر اساس تخمین پاداش در آینده عمل می‌کرد و اکشن مناسب را انتخاب می‌کرد. اما گاهی اوقات و به‌خصوص در مسائل نویزی، یادگیری کیو معمولی به سختی به جواب بهینه، همگرا می‌شوند و ممکن است در داخل یک حلقه تکرار شونده تا بی‌نهایت پیش روند و خیلی کند یا حتی هرگز به جواب بهینه برسند. در اینجا یادگیری کیو دوگانه این مشکل را حل می‌کند.

این روش، دو ماتریس کیو دارد که هردو به‌وسیلهٔ تجربیات مجزا و مستقل از یکدیگر آموزش دیده‌اند:

$Q_{t+1}^{A}(s_{t},a_{t})=Q_{t}^{A}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{B}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{A}(s_{t+1},a)\right)-Q_{t}^{A}(s_{t},a_{t})\right)$ و

$Q_{t+1}^{B}(s_{t},a_{t})=Q_{t}^{B}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{A}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{B}(s_{t+1},a)\right)-Q_{t}^{B}(s_{t},a_{t})\right).$

در هنگام اتخاذ تصمیم برا اساس ماتریس کیو، اگر یکی از این دو ماتریس به وسیلهٔ نویزها یا تغیرات تصادفی دچار مشکل شود، ماتریس دیگر این مشکل را حل می‌کند و الگوریتم به سمت همگرا شدن پیش خواهد رفت.

در سال ۲۰۱۵ نیز روش یادگیری دوگانه کیو با یادگیری عمیق کیو ترکیب شد و روشی جدید به نام یادگیری عمیق دوگانه کیو را به‌وجود آورد که برآیند دو روش ذکر شده در بالا هستند.

جستارهای وابسته

یادگیری تقویتی

یادگیری تقویتی عمیق

استراتژی مین مکس

شبکه عصبی

پیوند به بیرون

• Q-Learning topic on Knol
• Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England.
• Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning
• Q-Learning by Examples
• Reinforcement Learning: An Introduction by Richard Sutton and Andrew S. Barto, an online textbook. See "6.5 Q-Learning: Off-Policy TD Control".
• Connectionist Q-learning Java Framework
• Piqle: a Generic Java Platform for Reinforcement Learning
• Reinforcement Learning Maze, a demonstration of guiding an ant through a maze using Q-learning.
• Q-learning work by Gerald Tesauro
• Q-learning work by Tesauro Citeseer Link
• Q-learning algorithm implemented in processing.org language
• Example java applet for pole balancing in 2D with source code