معرفی بر الگوریتم های تقویتی(RL)

در حالت کلی در حوزه یادگیری ماشین سه دسته الگوریتم وجود دارند که عبارت هستند از الگوریتم های supervised یا یادگیری با نظارت، الگوریتم های unsupervised یا یادگیری بدون نظارت و الگوریتم های Reinforcement learning یا یادگیری تقویتی. در الگوریتم های یادگیری با نظارت هدف یافتن یک تابع است که داده های ورودی را به برچسب ها نگاشت می‌کند برای مثال فرض کنید از روی یک تصویر می‌خواهید تشخیص دهید که در آن تصویر پراید وجود دارد یا نه؟ داده های ورودی شما در حالتی که به دنبال آموزش از طریق یادگیری با نظارت باشید عبارت است از عکس و برچسب های آن پراید یا غیر پراید می‌باشد. در نوع دوم یادگیری که تحت عنوان یادگیری بدون نظارت مطرح است داده ها برچسب ندارند و به دنبال یافتن الگو های پنهان در داده ها هستیم. الگوریتم معروفی که همه به نوعی با آن آشنا هستند الگوریتم kmeans می‌باشد که نوعی از الگوریتم بدون نظارت است. اما نوع سوم یادگیری که به یادگیری تقویتی معروف است. در این الگوریتم دیگر با برچسب ها سرکار نداریم و برعکس با سیگنال های تنبیه و تشویق مواجهیم. این نوع از الگوریتم که از یادگیری انسان ها الگو گرفته است مبنا را بر این قرار می‌دهد که در صورتی که الگوریتم به درستی عمل کند باید تشویق شود و برعکس. حال به بررسی بیشتر این الگوریتم می‌پردازیم.

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

Agent

عامل تصمیم گیرنده تحت عنوان agent شناخته می‌شود.

Environment

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

Action

تمام حرکت های ممکنی که عامل ‌می‌تواند انجام دهد.

Reward

سیگنال جایزه که بازخوردی است از این که action انتخاب شده توسط عامل چه مقدار خوب یا بد است.

State

شرایط حال حاضری که محیط آن را برمی‌گرداند. (شرایطی که در هر لحظه عامل با آن روبرو است. )

برای مثال برای بازی شطرنج عامل، یک کامپیوتر است که در حال بازی کردن است.

تعرفAction: مجموعه حرکاتی است که کامپیوتر در بازی شطرنج می‌تواند انتخاب کند.

تعریف State: در هر لحظه حالت صفحه شطرنج است و reward جایزه‌ای است که در هر حرکت توسط کامپیوتر اخذ می‌شود.

Policy

یک تابع وظیفه نگاشت state به action ها را بر عهده دارد.

Value function

سیگنال reward برای بازه زمانی کوتاهی استفاده می‌شود حال آن که برای بازی مثل بازی شطرنج حالت نهایی مهم است. به عبارتی ممکن است در حرکت های کوتاه مدت عامل جایزه زیادی دریافت نکند و حتی reward منفی بگیرد اما برای بلند مدت نتیجه مناسبی داشته باشد. (مثلا الگوریتم وزیر را فدا می‌کند تا حریف را کیش و مات کند!)

V(s0, s1, …) = r(s0) + γ*r(s1) + γ2*r(s2) + …

Action value function

همانند value function است با این تفاوت که تابع value function ارزش یک state را نشان می‌دهد حال آن که تابع action value میزان ارزش بودن در یک state و انتخاب یک action را نمایان می‌کند.

یک مفهوم دیگر تحت عنوان optimal policy وجود دارد. این مفهوم بیان کننده policy است که تحت این policy مقدار Q ماکزیمم می‌شود.

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

مفهوم on policy و off policy نیز مفهوم مهمی است که تفاوت بین الگوریتم های آتی را مشخص خواهد کرد. الگوریتم های مبتنی بر on policy الگوریتم هایی هستند که تابع value را از روی policy فعلی که action فعلی نیز از روی آن انتخاب شده است یاد می‌گیرند. حال آنکه off policy اینگونه نیستد.

الگوریتم های policy iteration:

این الگوریتم از دو قسمت شکل گرفته است. درقسمت اول ارزیابی policy اتفاق می‌افتد و در قسمت دوم بهبود policy اتفاق می‌افتد.

در حالت ارزیابی policy ، تابع V که همان value function است از روی policy قبلی تخمین زده میشود. حال در حالت بهبود policy از روی تابع تخمین زده شده در مرحله قبل آن policy یافته میشود که value function را بیشینه کند. این حلقه تا زمانی که الگوریتم همگرا شود ادامه خواهد یافت. در ادامه یک شبه کد از این الگوریتم را مشاهده می‌کنید.

Value Iteration

در این الگوریتم فقط تابع Value function آپدیت می شود. شبه کد این الگوریتم در ادامه می‌آید.

Q learning

اگر به مدل های قبلی توجه داشته باشید همه این الگوریتم های مبتنی بر مدل بودند که در عمل چنین مسئله ای کمتر اتفاق می‌افتد. راه حل این مسئله استفاده از الگوریتم q learning هست. نحوه آپدیت کردن دراین الگوریتم به شکل زیر است :

همانطور که مشخص است این الگوریتم یک الگوریتم off policy است. چرا که action انتخاب شده در State بعدی است که تابع q مربوط به state بعدی را ماکزیمم میکند( به عبارتی policy فعلی انتخاب شده بیشینه نشده است.) شبه کد این الگوریتم در ادامه می آید.