یادگیری تقویتییکی از روش‌های یادگیری ماشینی است که در آن، عامل یادگیری پس از ارزیابی هر اقدام عامل ، پاداشی (همراه با تاخیر)به او داده می‌شود. درگذشته، این روش اغلب در بازی‌ها (از جمله بازی‌های آتاری و ماریو) به‌کار گرفته می‌شد و عملکرد آن در سطح انسان و حتی گاهی فراتر از توانایی ما بود. اما در سال‌های اخیر، این الگوریتم‌های یادگیری تقویتی درنتیجه ادغام با شبکه‌های عصبی تکامل پیدا کرده و حال قادر است اعمال پیچیده‌تری از جمله حل کردن مسائل را نیز انجام دهد.
الگوریتم‌های یادگیری تقویتی بسیار متنوع هستند، اما این الگوریتم‌ها هیچ‌گاه به‌طور جامع بررسی و مقایسه نشده‌اند. زمانی که قصد داشتم از این الگوریتم‌ها در پروژه خود استفاده کنم، همین مسئله موجب شد ندانم کدام الگوریتم را باید برای چه فرآیندی به‌کار بگیرم. در این مقاله سعی بر این است که به‌طور خلاصه سازوکار یادگیری تقویتی را بررسی کرده و تعدادی از محبوب‌ترین الگوریتم‌های این حوزه را معرفی نماییم.
۱. یادگیری تقویتی ۱۰۱
سازوکار یادگیری تقویتی متشکل از دو عنصر عامل تصمیم‌گیرنده و محیط است.
تصویری از الگوریتم یادگیری تقویتی(https://i.stack.imgur.com/eoeSq.png)
در این‌جا محیط، معرف شیء‌ای است که عامل تصمیم‌گیرنده عملی بر روی آن انجام می‌دهد (برای مثال، خود بازی در بازی آتاری یک محیط است). این عامل تصمیم‌گیرنده درواقع همان الگوریتم یادگیری تقویتی است. در ابتدا محیط یک وضعیت
را برای عامل ایجاد می‌کند تا عامل براساس دانش خود نسبت به آن عکس‌العمل نشان دهد. سپس محیط، وضعیت بعدی و پاداش اقدام قبلی را با هم برای عامل می‌فرستد. عامل تصمیم‌گیرنده نیز دانش خود را بر پایه پاداشی که در ازای اقدام پیشین خود دریافت کرده، به‌روزرسانی می‌کند. این چرخه ادامه پیدا می‌کند تا محیط وضعیت نهایی را برای عامل بفرستد و چرخه را خاتمه دهد.
اغلب الگوریتم‌های یادگیری تقویتی از این الگو پیروی می‌کنند. در قسمت بعدی، واژه‌ها و اصطلاحات پرکاربرد در حوزه یادگیری تقویتی را به‌طور خلاصه شرح می‌دهیم تا درک مباحث بعدی تسهیل شود.
تعاریف
اقدام (Action|A): شامل تمامی واکنش‌های محتملی است که عامل تصمیم‌گیرنده ممکن است در مواجهه با وضعیت ایجاد شده، از خود نشان دهد.
وضعیت (State|S): وضعیتی که عامل در هرلحظه با آن مواجه است و محیط آن را ایجاد کرده است.
پاداش (Reward|R): بازخورد فوری که پس از ارزیابی هر اقدام عامل تصمیم‌گیرنده، توسط محیط برای آن ارسال می‌شود.
سیاست (Policy|π): استراتژی است که عامل تصمیم‌گیرنده در پاسخ به وضعیت فعلی، برای اقدام بعدی خود درنظر می‌گیرد.
ارزش (Value|V): پاداش بلند مدت موردانتظار تنزیل‌شدهکه برخلاف با پاداش کوتاه‌مدت (R)، بلندمدت می‌باشد. عبارت است از سود موردانتظار در بلندمدت که ناشی از وضعیت کنونی s تحت سیاست π است.
Q-value یا اقدام-ارزش (Q): مفهوم Q-value بسیار شبیه به مفهوم ارزش (V) است. اما در Q-value یک پارامتر بیشتر وجود دارد. این پارامتر اضافه همان اقدام a می‌باشد. Q(s,a) عبارت است از سود بلندمدت ناشی از اقدام a تحت سیاست
π در وضعیت کنونی s.
الگوریتم‌های بدون مدلدر برابر الگوریتم‌های مبتنی بر مدل
مدل یک شبیه‌سازی از پویایی محیط است. یعنی اینکه مدل، تابع احتمال انتقال T(s1|(s0, a)) (یعنی احتمال انتقال وضعیت s1 درصورتی که در وضعیت قبلی یا s0، اقدام a انتخاب شده باشد.) را یاد می‌گیرد. اگر یادگیری تابع انتقال احتمال موفقیت‌آمیز باشد، عامل تصمیم‌گیرنده می‌تواند احتمال رخ دادن یک وضعیت مشخص را براساس وضعیت و اقدام فعلی محاسبه کند. اما با افزایش تعداد وضعیت‌ها و اقدام‌ها (S*S*A، در یک ساختار جدولی)، الگوریتم‌های مبتنی بر مدل کارآمدی خود را از دست می‌دهند.
از سوی دیگر، الگوریتم‌های بدون مدل درواقع مبتنی بر روش آزمون و خطاهستند و براساس نتیجه آن، دانش خود را به‌روزرسانی می‌کنند. درنتیجه، فضایی برای ذخیره ترکیبات احتمالی وضعیت‌ها و اقدام‌ها نیاز نخواهند داشت. الگوریتم‌هایی که در قسمت بعدی معرفی می‌شوند، همگی در این دسته قرار دارند.
روش On-policy و روش Off-policy
در روش On-policy، عامل تصمیم‌گیرنده ارزش را براساس اقدام a که ناشی از سیاست فعلی است، یاد می‌گیرد. اما در روش دیگر یعنی روش Off-policy فرایند یادگیری به این صورت است که عامل، ارزش را از اقدام a* (بهترین اقدام موجود) که نتیجه یک سیاست دیگر می‌باشد، می‌آموزد. این سیاست در الگوریتم یادگیری Q همان سیاست حریصانه است (درادامه این مقاله بیشتر درباره الگوریتم‌های یادگیری Q و SARSA صحبت خواهیم کرد).
۲. مروری بر چند الگوریتم
۱.۲. الگوریتم یادگیری Q
الگوریتم Q-Learning یا یادگیری Q یک الگوریتم یادگیری تقویتی از نوع بدون مدل و Off-policy است که برپایه معادله معروف بِلمَن تعریف می‌شود:
معادله بلمن (https://zhuanlan.zhihu.com/p/21378532?refer=intelligentunit)
در معادله بالا، E نماد انتظارات و λ ضریب تنزیلاست. میتوانیم معادله بالا را در فرم تابعی Q-Value به صورت زیر بنویسیم:
معادله بلمن در فرم تابعیQ-value ( (https://zhuanlan.zhihu.com/p/21378532?refer=intelligentuni
مقدار بهینهQ-value که با نماد نمایش داده می‌شود را می‌توان از فرمول زیر به دست آورد:
مقدار بهینه Q-value (https://zhuanlan.zhihu.com/p/21378532?refer=intelligentunit)
هدف این معادله حداکثرسازی مقدار Q-value است. البته، پیش از پرداختن به روش‌های بهینه‌سازی مقدار Q-value، قصد دارم ۲ روش به‌روزرسانی ارزش را که رابطه نزدیکی با الگوریتم یادگیری Q دارند، معرفی کنم.
تکرار سیاست
در روش تکرار سیاست، یک حلقه بین ارزیابی سیاست و بهبود آن شکل می‌گیرد.
تکرار سیاست (http://blog.csdn.net/songrotek/article/details/51378582)
در ارزیابی سیاست، مقدار تابع V را برحسب سیاست حریصانه‌ای که درنتیجه‌ی بهبود سیاست قبلی به دست آمده، تخمین می‌زنیم. از سوی دیگر، در بهبود سیاست، سیاست فعلی را برحسب اقدامی که مقدار V را در هر وضعیت حداکثر کند، به‌روزرسانی می‌کنیم. به‌روزرسانی معادلات برپایه معادله بلمن انجام می‌گیرد و تکرار حلقه تا زمانی که این معادلات همگرا
شوند، ادامه می‌یابد.
نمونه کد روش تکرار سیاست (http://blog.csdn.net/songrotek/article/details/51378582)
تکرار ارزش
معادله بهینه بلمن (http://blog.csdn.net/songrotek/article/details/51
روش تکرار ارزش تنها یک بخش دارد. در این روش، تابع ارزش براساس مقدار بهینه معادله بلمن به‌روزرسانی می‌شود.
نمونه کد روش تکرار ارزش (http://blog.csdn.net/songrotek/article/details/51378582)
وقتی تکرار به همگرایی برسد، یک سیاست بهینه برای همه وضعیت‌ها مستقیماً توسط تابع argument-max ارائه داده می‌شود.
به‌خاطر داشته باشید که برای استفاده از این دو روش باید احتمال انتقالp را بشناسید. بنابراین، می‌توان گفت که این روش‌ها، الگوریتم‌های مبتنی بر مدل هستند. اما همان‌طور که پیش‌تر نیز ذکر کردیم، الگوریتم‌های مبتنی بر مدل با مشکل مقیاس‌پذیری مواجه هستند. سوالی که در این‌جا پیش می‌آید این است که الگوریتم یادگیری Q چطور این مشکل را حل کرده است؟
معادله به‌روزشده یادگیری Q (https://www.quora.com/What-is-the-difference-between-Q-learning-and-SARSA-learning)
در این معادله، α نماد نرخ یادگیری(یعنی سرعت ما در حرکت به سوی هدف اصلی) است. ایده اصلی یادگیری Q به‌شدت به روش تکرار ارزش متکی است. اما معادله به‌روزشده با فرمول بالا جایگزین می‌شود و درنتیجه، دیگر نیاز نیست نگران احتمال انتقال باشیم.
نمونه کد یادگیری Q (https://martin-thoma.com/images/2016/07/q-learning.png)
بخاطر داشته باشید که اقدام بعدی یعنی ، با هدف حداکثر کردن وضعیت بعدی Q-value انتخاب شده است، نه براساس سیاست مربوطه. درنتیجه یادگیری Q در دسته روش‌های Off-policy قرار می‌گیرد.
۲.۲. الگوریتم «وضعیت-اقدام-پاداش-وضعیت-اقدام» یا SARSA
الگوریتم SARSA (که سرواژه عبارت State-Action-Reward-State-Action است) شباهت زیادی با الگوریتم یادگیری Q دارد. تفاوت کلیدی این دو الگوریتم در این است که SARSA برخلاف الگوریتم یادگیری Q، در دسته الگوریتم‌های On-Policy قرار می‌گیرد. بنابراین، الگوریتم SARSA مقدار Q-value را با توجه به اقدامی که ناشی از سیاست فعلی است محاسبه می‌کند نه اقدام ناشی از سیاست حریصانه.
معادله به‌روزرسانی الگوریتم SARSA (https://www.quora.com/What-is-the-difference-between-Q-learning-and-SARSA-learning)
اقدام اقدامی است که در وضعیت بعدی یعنی تحت سیاست فعلی انجام خواهد گرفت.
نمونه کد الگوریتم SARSA (https://martin-thoma.com/images/2016/07/sarsa-lambda.png)
ممکن است در نمونه کد بالا متوجه شده باشید که هر دو اقدام اجرا شده از سیاست فعلی پیروی می‌کنند. اما در الگوریتم یادگیری Q، تا زمانی که اقدام بعدی بتواند مقدار Q-value برای وضعیت بعدی را حداکثر سازد، هیچ قیدی برای آن تعریف نمی‌شود. بنابراین همان‌طور که گفته شد، الگوریتم SARSA از نوع الگوریتم‌های On-policy است.
۳.۲. شبکه عمیق Q یا DQN
الگوریتم یادگیری Q الگوریتم قدرتمندی است، اما قابلیت تعمیم‌پذیریندارد و همین مسئله را می‌توان بزرگ‌ترین نقطه‌ضعف آن دانست. اگر الگوریتم یادگیری Q را به‌روزرسانی اعداد موجود در یک آرایه دو بعدی (شامل: فضای اقدام×فضای وضعیت) درنظر بگیرید، متوجه شباهت آن با برنامه‌نویسی پویاخواهید شد. این موضوع برای ما روشن می‌سازد که وقتی عامل تصمیم‌گیرنده در الگوریتم یادگیری Q با وضعیتی کاملاً جدید روبه‌رو شود، هیچ راهی برای شناسایی و انتخاب اقدام مناسب نخواهد داشت. به عبارت دیگر، عامل تصمیم‌گیرنده الگوریتم یادگیری Q توانایی تخمین ارزش وضعیت‌های ناشناخته را ندارد. برای حل این مشکل، شبکه DQN آرایه دو بعدی را حذف و شبکه عصبی را جایگزین آن می‌کند.
شبکه DQN به کمک یک شبکه عصبی، تابع Q-value را تخمین می‌زند. وضعیت فعلی به عنوان ورودی به این شبکه داده می‌شود، سپس مقدار Q-value متناظر با هر اقدام به عنوان خروجی از شبکه دریافت خواهد شد.
یک مثال از شبکه DQN در آتاری (https://zhuanlan.zhihu.com/p/25239682)
شرکت دیپ مایند در سال ۲۰۱۳، شبکه DQN را همان‌طور که در تصویر بالا ملاحظه می‌کنید، در بازی آتاری به‌کار گرفت. ورودی که به این شبکه داده می‌شد یک تصویر خام از وضعیت جاری بازی بود. این ورودی از چندین لایه مختلف از جمله لایه‌های پیچشی و تماماً متصل عبور می‌کند و خروجی نهایی شامل مقادیر Q-valueهای مربوط به تمام اقدامات احتمالی عامل تصمیم‌گیرنده است.
حال سؤال اصلی این است که: چطور می‌توان این شبکه را آموزش داد؟
پاسخ این است که ما شبکه را براساس معادله به‌روزرسانی الگوریتم یادگیری Q آموزش می‌دهیم. اگر بخاطر داشته باشید، مقدار Q-value هدف برای الگوریتم یادگیری Q از فرمول زیر به دست می‌آمد:
Q-value هدف (https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf)
نماد ϕ معادل وضعیت s است. نماد