مقدمه‌ای بر انواع الگوریتم‌های یادگیری تقویتی

 

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

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

۱. یادگیری تقویتی ۱۰۱

سازوکار یادگیری تقویتی متشکل از دو عنصر عامل تصمیم‌گیرنده و محیط است.

تصویری از الگوریتم یادگیری تقویتی(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 است. نماد نیز بیان‌گر تعدادی از پارامترهای شبکه عصبی است که خارج از بحث ما هستند. بنابراین، تابع زیان شبکه به صورت مربعات خطای Q-value هدف و Q-valueای که شبکه به عنوان خروجی به ما می‌دهد، تعریف می‌شود.

نمونه کد شبکه DNQ (https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf)

 

دو تکنیک دیگر نیز برای آموزش شبکه DNQ ضروری است:

1. تکرار تجریه: در سازوکار متداول یادگیری تقویتی، نمونه‌های آموزشی همبستگی بالایی دارند و ازنظر مقدار داده موردنیاز نیز کارآمد نیستند. به همین دلیل، رسیدن به مرحله همگرایی برای مدل سخت خواهد بود. یک راه برای حل مسئله توزیع نمونه، به‌کارگیری تکنیک تکرار تجربه است. در این روش، تابع انتقال نمونه‌ها ذخیره می‌شود و سپس الگوریتم این تجربیات را از محلی به نام مجموعه انتقال» به طور تصادفی انتخاب می‌کند تا دانش خود را براساس آن به‌روزرسانی نماید.
2. شبکه هدف مجزا: ساختار شبکه هدف Q مشابه ساختار شبکه‌ای است که ارزش را تخمین می‌زند. همان‌طور در نمونه کد بالا ملاحظه کردید، در به تعداد C مرحله، شبکه هدف جدیدی تعریف می‌شود تا از شدت نوسانات کاسته شود و فرایند آموزش ثبات بیشتری داشته باشد.

 

۴.۲. الگوریتم DDPG

اگرچه شبکه DQN در مسائلی که ابعاد زیادی دارند (همچون بازی آتاری)، بسیار موفق عمل کرده است، اما فضای اقدام در این شبکه گسستهمی‌باشد و از آن‌جا که بسیاری از مسائل موردعلاقه و حائز اهمیت برای ما از جمله مسائل مربوط به کنترل فیزیکی، دارای فضای اقدام پیوسته هستند، گسسته بودن فضا در شبکه DQN یک نقطه‌ضعف به‌شمار می‌آید. اگر یک فضای اقدام پیوسته را به‌طور دقیق و جزئی به یک فضای گسسته تبدیل کنید، درنهایت، یک فضای اقدام بسیار گسترده خواهید داشت. برای مثال، فرض کنید درجه آزادی سیستم تصادفی ۱۰ باشد.  به‌ازای هر درجه، باید فضا را به ۴ قسمت تقسیم کنیم. به این ترتیب، در آخر ۱۰۴۸۵۷۶=۴⁰ عدد اقدام خواهیم داشت. در چنین فضای اقدام بزرگی رسیدن به همگرایی بسیار سخت خواهد بود.

الگوریتم DDPG مبتنی بر معماری عملگر منتقداست. این معماری دو عنصر اصلی دارد: عملگر و منتقد. عنصر عملگر، تنظیم پارامتر با تابع ترا برعهده دارد، به این ترتیب، عملگر تصمیم می‌گیرد که بهترین اقدام ممکن برای هر وضعیت چیست.

تابع ت(https://zhuanlan.zhihu.com/p/25239682)

 

وظیفه منتقد نیز ارزیابی تابع تی است که عملگر براساس تابع خطای تفاوت موقتیتخمین زده است.

تابع خطای تفاوت زمانی (http://proceedings.mlr.press/v32/silver14.pdf)

 

در این تابع حرف v کوچک نمایان‌گر تی است که عملگر برمی‌گزیند. این فرمول کمی آشنا به‌نظر نمی‌رسد؟ بله، درست است. این فرمول دقیقاً مشابه معادله به‌روزرسانی الگوریتم یادگیری Q است. یادگیری تفاوت زمانی روشی است که الگوریتم به کمک آن می‌تواند نحوه پیش‌بینی یک تابع ارزش را بر پایه ارزش‌های آتی یک وضعیت معین بیاموزد. الگوریتم یادگیری Q نوعی خاصی از یادگیری تفاوت زمانی در حوزه یادگیری Q-value است.

معماری عملگر-منتقد (https://arxiv.org/pdf/1509.02971.pdf)

 

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

(https://blog.openai.com/better-exploration-with-parameter-noise/)

 

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

نمونه کد الگوریتم DDPG (https://arxiv.org/pdf/1509.02971.pdf)

۳. سخن نهایی

در این مقاله به برخی از مفاهیم پایه‌ای و ساده الگوریتم‌های یادگیری Q، SARSA، DQN و DDPG پرداختیم. در مقاله بعدی و در ادامه همین بحث، به بررسی پیشرفته‌ترین الگوریتم‌های یادگیری تقویتی از جمله NAF، A3C و غیره خواهیم پرداخت و در آخر نیز تمامی الگوریتم‌های مذکور را با یک‌دیگر مقایسه خواهیم کرد. اگر ابهام یا سؤالی درخصوص این مقاله دارید، آن را در بخش نظرات با ما به اشتراک بگذارید.

منبع: hooshio.com