کیو-یادگیری

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

الگوریتم

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

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

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

${\displaystyle 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]}$

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

فرمول فوق معادل عبارت زیر است: ${\displaystyle 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})]}$

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

نرخ یادگیری

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

عامل تخفیف

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

پیاده سازی

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

مطالعات اولیه

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

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

• 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

منابع

1. Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L. Littman. Pac model-free reinforcement learning. In Proc. 23nd ICML 2006, pages 881–888, 2006.
2. میلاد وزان، یادگیری عمیق: اصول، مفاهیم و رویکردها، میعاد اندیشه، 1399
3. Watkins, C.J.C.H., (1989), Learning from Delayed Rewards. Ph.D. thesis, Cambridge University.
4. Watkins and Dayan, C.J.C.H., (1992), 'Q-learning.Machine Learning',