یادگیری تقویتی روشی است که در آن عامل با در نظر گرفتن حالت محیط، از بین همه اعمال ممکن یکی را انتخاب می کند و محیط در ازای انجام آن عمل، یک سیگنال عددی به نام پاداش به عامل باز می گرداند.
هدف عامل این است که از طریق سعی و خطا سیاستی را بیابد که با دنبال کردن آن به بیشترین پاداش ممکن برسد.
در این پروژه سعی داریم به یک عامل یاد بدهیم چگونه مواد مورد نیاز برای درست کردن یک کیک را با استفاده از یادگیری تقویتی جمع آوری کند.
محیط به صورت یک ماز است که یک هیولا در آن وجود دارد و در یک سری از خانه ها چاله وجود دارد که مانع عامل ما هستند.
عامل باید سه ماده آرد، شکر و تخم مرغ را در کوتاهترین زمان جمع آوری کند بدون آنکه هیولا او را بگیرد.
# مقدمه
در این صفحه ماز عامل ما در هر لحظه در خانه ای به سر میبرد . او میتواند در هر خانه به چهار سمت حرکت کند ، چاله ها و هیولا عوامل محدود کننده حرکت او هستند . در یادگیری تقویتی برای هر حرکت پاداشی در نظر گرفته میشود . در اینجا مثلا نزدیک شدن به شیر ، تخم مرغ و آرد میتواند حرکت هایی با امتیاز بالا و نزدیک شدن به هیولا حرکتی با امتیاز منفی باشد . به این صورت که عامل با تجربه کردن راه های متفاوت ، بهترین راه را برای رسیدن به این سه خانه (صرفا با تعامل با محیط) به دست آورد .
توضیحی بر یادگیری تقویتی : در این موضوع عامل علاوه بر اینکه در هر حالت باید بهترین تصمیم را بگیرد ، باید نسبت به پاداشی که در آینده در حرکتاتی که بعد از حرکت فعلی نسیبش میشود ، حساس باشد . دو عامل اکتشاف و بهره برداری باید به طور یکسان مورد بررسی عامل قرار گیرد . اکتشاف یا همان سعی و خطا یعنیامتحان کردن حرکتی جدیدی که باعث افزایش پاداش او شود (که همراه با ریسک است) . منظور از بهره برداری نیز این است که عامل متناسب با تجربیات گذشته خویش ، راهی که بیشترین امتیاز را به او داده برود. هرکدام ازین دو راه اگر به تنهایی مورد تجه قرار گیرند ، شکست خواهند خورد .
در پایان عامل باید خط مشیی را پیدا کند که کا با استفاده از آن بتواند حالات را به اعمالی نگاشت دهد که بیشترین امتیاز را برای او به ارمغان آورد . یعنی با رجوع با آن در هر موقعیتی که قرار دارد بتواند بهترین عمل را انجام دهد .
# کارهای مرتبط
در این پروژه من میخواهم موضوع را با دو الگوریتم Q-learning و sarsa بررسی کرده و میان این دو الگوریتم ، روش بهتر را انتخاب کنم . هر دو روش ذکر شده بر پایه ی یادگیری تقویتی عمل میکنند ، به این صورت که در الگوریتم سارسا ، عامل در مرحله ی یادگیری همراه با یادگیری رویه ی خود را هم بهینه میکند ولی در روش یادگیری Q عامل رویه خود را حین عمل خود تغییر نداده و در پایان خط مشی را به صورت کلی تغییر میدهد .
# آزمایش‌ها
# کارهای آینده
در این پروژه محیطی داریم به صورت شطرنجی که عامل با جمع کردن سه ماده آرد، شکر و تخم مرغ و عدم برخورد با غول میتواند کیک مورد علاقه اش را درست کند و بازی را میبرد. در این میان عامل باید سعی کند کمتر به دیوار برخورد کند و یا در چاله بیفتد. عامل ما در هر لحظه در خانه ای به سر میبرد . او میتواند در هر خانه به چهار سمت حرکت کند. در یادگیری تقویتی برای هر حرکت پاداشی در نظر گرفته میشود . <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 و در نهایت مقایسه این دو روش خواهم پرداخت .
# مراجع
+ محمد غضنفری، "بهبود عملکرد عامل شبیه‌سازی فوتبال دوبعدی با استفاده از یادگیری تقویتی "، پایان‌نامه کارشناسی، دانشگاه علم و صنعت ایران، ۱۳۹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.
http://en.wikipedia.org/wiki/SARSA<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.
http://en.wikipedia.org/wiki/Q-learninga 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)