یادگیری تقویتی روشی است که در آن عامل با در نظر گرفتن حالت محیط، از بین همه اعمال ممکن یکی را انتخاب می کند و محیط در ازای انجام آن عمل، یک سیگنال عددی به نام پاداش به عامل باز می گرداند. هدف عامل این است که از طریق سعی و خطا سیاستی را بیابد که با دنبال کردن آن به بیشترین پاداش ممکن برسد. در این پروژه سعی داریم به یک عامل یاد بدهیم چگونه مواد مورد نیاز برای درست کردن یک کیک را با استفاده از یادگیری تقویتی جمع آوری کند. محیط به صورت یک ماز است که یک هیولا در آن وجود دارد و در یک سری از خانه ها چاله وجود دارد که مانع عامل ما هستند. عامل باید سه ماده آرد، شکر و تخم مرغ را در کوتاهترین زمان جمع آوری کند بدون آنکه هیولا او را بگیرد.  # مقدمه در این پروژه محیطی داریم به صورت شطرنجی که عامل با جمع کردن سه ماده آرد، شکر و تخم مرغ و عدم برخورد با غول میتواند کیک مورد علاقه اش را درست کند و بازی را میبرد. در این میان عامل باید سعی کند کمتر به دیوار برخورد کند و یا در چاله بیفتد. عامل ما در هر لحظه در خانه ای به سر میبرد . او میتواند در هر خانه به چهار سمت حرکت کند. در یادگیری تقویتی برای هر حرکت پاداشی در نظر گرفته میشود . <br> توضیحی بر یادگیری تقویتی : در این موضوع عامل علاوه بر اینکه در هر حالت باید بهترین تصمیم را بگیرد ، باید نسبت به پاداشی که در آینده در حرکتاتی که بعد از حرکت فعلی نسیبش میشود ، حساس باشد . دو معیار اکتشاف و بهره برداری از عواملی هستند که عامل در انتخاب مسیر در هر خانه باید از آن ها کمک بگیرد . اکتشاف یا همان سعی و خطا یعنی امتحان کردن حرکتی جدیدی که در گذشته امتحان نکرده ، به این امید که باعث افزایش پاداش او شود (که همراه با ریسک است) . منظور از بهره برداری نیز این است که عامل متناسب با تجربیات گذشته خویش ، مسیری را انتخاب کند که بیشترین امتیاز را در گذشته به او داده است . هرکدام ازین دو راه اگر به تنهایی مورد توجه عامل قرار گیرند ،باعث شکست خواهد شد . پس برای تعیین خط مشی خود باید هر دو معیار را با نسبت مناسبی مورد توجه قرار دهد. <br> در پایان عامل باید خط مشیی را پیدا کند که که با استفاده از آن بتواند حالات را به اعمالی نگاشت دهد که بیشترین امتیاز را برای او به ارمغان آورد . یعنی با رجوع با آن در هر موقعیتی که قرار دارد بتواند بهترین عمل را انجام دهد . <br> # کارهای مرتبط در این پروژه من میخواهم موضوع را با دو الگوریتم Q-learning و sarsa بررسی کرده و میان این دو الگوریتم ، روش بهتر را انتخاب کنم . هر دو روش ذکر شده بر پایه ی یادگیری تقویتی عمل میکنند ، به این صورت که در الگوریتم سارسا ، عامل در مرحله ی یادگیری همراه با یادگیری رویه ی خود را هم بهینه میکند ولی در روش یادگیری Q عامل رویه خود را حین عمل خود تغییر نداده و در پایان خط مشی را به صورت کلی تغییر میدهد . <br> در فاز سوم روش sarsa را تشریح کرده ، و نتایج آزمایشات را ثبت میگردد . <h3> روش sarsa</h3> <br> روش سارسا یک روش TD(0) online میباشد که همان سیاستی را بهینه میکند که در طول یادگیری از آن استفاده میکند. در عکس زیر الگوریتم آن را مشا هده میکنیم : <br> <img border="0" src="http://cld.persiangig.com/preview/aOIZOMdEIt/ax1.jpg" alt="Pulpit rock" width="450" height="350"> <br> ابتدا مقادیر Q را برای همه حالت -عمل ها برابر صفر قرار میدهیم. سپس در هر اپیزود با استفاده از یک سیاست نرم بر پایه Qهای تخمین زده شده تا آن لحظه یک عمل را انتخاب میکنیم و انجام میدهیم. پاداش لحظه ای دریافت میشود و به یک حالت جدید میرویم. در این حالت جدید نیز عمل دلخواه را انتخاب میکنیم و ارزش حالت-عمل اولیه را بر اساس پاداش لحظه ای آن و ارزش حالت-عمل بعدی بروزرسانی میکنیم. <br><br> با تکرار مداوم این کار سعی در یافتن ارزشهای بهینه میکنیم. سیاست مورد استفاده برای زمان یادگیری در ابتدا ε-greedy و سپس Boltzman استفاده شدند. سیاست ε-greedy مقدار regret کمتری نسبت به Boltzman دارد ولی Boltzman به مقدار بهتری همگرا میگردد. سیاست ε-greedy به دلیل اینکه Q-based نیست و rank-based است دارای مشکلات و نواقص زیادی است ( مثلا چون همه اعمال غیر بهینه را با احتمالی برابر انتخاب میکند، یک عمل با پاداش بسیار منفی مثل رفتن به خانه غول و یک عمل تقریبا خوب را مثل حرکت به سمت شکر را با احتمالی برابر انتخاب میکند) و این نواقص در Boltzman وجود ندارد ولی با این حال regret در ε-greedy کمتر است. دلیل این امر اولا دشواری مقدار دهی به پارامتر دما در Boltzman است و ثانیا تاثیر نمایی مقدار Q در احتمال انتخابها است. این دو مشکل در ε-greedy وجود ندارد و لذا کمی regret بهتری دارد. هرچند اگر پارامتر دما در Boltzman خیلی خوبی تنظیم شود حتما نتیجه بهتری از ε-greedy خواهد داد. <br> <br> برای تنظیم پارامتر τ از تابع کاهشی (( ΤAW = 1000 * (1.05 ^ (-ep/60 استفاده شده که در آن ep شمارنده اپیزود است. مدت زمان اجرای روش سارسا با سیاست بولتزمن و تعداد اپیزود 10000 ، برابر 161 ثانیه میباشد. کد پیاده سازی روش sarsa را میتوان از لینک زیر دانلود کرد . <br> <a href="http://cld.persiangig.com/download/926Xfk9P1K/sarsa-firstedition.rar/dl" target="_blank" title="برای دانلود کلیک کنید"><img src="http://cld.persiangig.com/images/pgdl.png" alt="دانلود"></a> # آزمایش‌ها # کارهای آینده در فاز های بعدی به پیاده سازی روش Q-learning ، آزمایش روش سارسا ، آزمایش روش Q-learning و در نهایت مقایسه این دو روش خواهم پرداختبا تکرار مداوم این کار سعی در یافتن ارزشهای بهینه میکنیم. سیاست مورد استفاده برای زمان یادگیری در ابتدا ε-greedy و سپس Boltzman استفاده شدند. سیاست ε-greedy مقدار regret کمتری نسبت به Boltzman دارد ولی Boltzman به مقدار بهتری همگرا میگردد. سیاست ε-greedy به دلیل اینکه Q-based نیست و rank-based است دارای مشکلات و نواقص زیادی است ( مثلا چون همه اعمال غیر بهینه را با احتمالی برابر انتخاب میکند، یک عمل با پاداش بسیار منفی مثل رفتن به خانه غول و یک عمل تقریبا خوب را مثل حرکت به سمت شکر را با احتمالی برابر انتخاب میکند) و این نواقص در Boltzman وجود ندارد ولی با این حال regret در ε-greedy کمتر است. دلیل این امر اولا دشواری مقدار دهی به پارامتر دما در Boltzman است و ثانیا تاثیر نمایی مقدار Q در احتمال انتخابها است. این دو مشکل در ε-greedy وجود ندارد و لذا کمی regret بهتری دارد. هرچند اگر پارامتر دما در Boltzman خیلی خوبی تنظیم شود حتما نتیجه بهتری از ε-greedy خواهد داد. <br> # آزمایش‌ها <br> برای تنظیم پارامتر τ از تابع کاهشی (( ΤAW = 1000 * (1.05 ^ (-ep/60 استفاده شده که در آن ep شمارنده اپیزود است. مدت زمان اجرای روش سارسا با سیاست بولتزمن و تعداد اپیزود 10000 ، برابر 161 ثانیه میباشد. <br> لازم به ذکر است به دلیل اینکه حالت آغازین هر اپیزود به صورت تصادفی انتخاب می شود و همچنین در انتخاب اعمال نیز عامل شانس دخیل است، بعضی اوقات (به ندرت) این الگوریتمها در مدت زمان زندگی محدود (10000 اپیزود) به جواب مناسبی نمیرسند. همگی نمودارها حاصل اجرای 5 بار یادگیری است که با استفاده از یک پنجره به طول 1000 smooth شده اند. مسیر طی شده عامل از نقطه شروع تا انتهای اپیزود با استفاده از روش سارسا در شکل زیر آمده است . عامل در خانه ستاره دار یک بار توقف داشته است. <br> <img border="0" src="http://cld.persiangig.com/preview/8vXHrp3IfI/2.png" alt="Pulpit rock" width="450" height="350"> <br> همچنین میانگین پاداش لحظه ای در 5 بار اجرای این روش مطابق نمودار زیر است: <img border="0" src="http://cld.persiangig.com/preview/H9v3Bry1l1/3.png" alt="Pulpit rock" width="450" height="350"> <br> توضیحات : در این چند روز برای سایت git مشکلی ایجاد شد که من نتوانستم در آن فضا کد را بگذارم . برای مشاهده فایل ها از لینک زیر استفاده نمایید : <br> <a href="http://cld.persiangig.com/download/pWAwo7V4Ai/sarsa-firstedition.rar/dl" target="_blank" title="برای دانلود کلیک کنید"><img src="http://cld.persiangig.com/images/pgdl.png" alt="دانلود"></a> <br> # کارهای آینده در فاز های بعدی به پیاده سازی روش Q-learning و آزمایش آن خواهم پرداخت تا با مقایسه این دو روش بتوان از بین این دو روش ، روش بهتر را به دست آورد. # مراجع + محمد غضنفری، "بهبود عملکرد عامل شبیه‌سازی فوتبال دوبعدی با استفاده از یادگیری تقویتی "، پایان‌نامه کارشناسی، دانشگاه علم و صنعت ایران، ۱۳۹2. [لینک](https://www.dropbox.com/s/2elzbgh9qnym476/Performance%20Improvement%20of%20a%202D%20Soccer%20Simulation%20agent%20using%20Rainforcement%20Learning.pdf) R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. Cambridge, United States of America: MIT Press, 1998. <br> <a href="http://en.wikipedia.org/wiki/SARSA">sarsa</a> <a href="http://en.wikipedia.org/wiki/Q-learning">Q-lerning</a> F. S. Melo and M. I. Ribeiro, "Q-learning with linear function approximation," pp. 602-607, Mar. 2007. a href = "">Q-learning >> # پیوندهای مفید + [یک نمونه استفاده از این مسئله برای پیاده‌سازی روش سارسا و یادگیری کیو](https://www.dropbox.com/s/zi1p2jkgohjhv5b/TD_Sarsa.pdf) + [یک نمونه استفاده از این مسئله برای پیاده‌سازی روش value iteration و policy iteration ](https://www.dropbox.com/s/6c5q3lbppa8qaag/Value_Iteration.pdf) + [Reinforcement learning](http://en.wikipedia.org/wiki/Reinforcement_learning)