یادگیری تقویتی

صفحه 1:
یادگیری تقویتی destructor > Gueed Ghiqv 0 Mitchell Ch. 13 

صفحه 2:
2 ایادگیری تقویتی * در یک مسئله یادگیری تقویتی با عاملی روبرو هستیم که از طریق سعی و خطا با محیط تعامل کرده و یاد میگیرد تا عملی بهینه را برای رسیدن به هدف انتخاب نماید. percept Environment ion 

صفحه 3:
© ایادگیری تقوبتی * یادگیری نقویتی از اینرو مورد توجه است که راهی برای آموزش عاملها برای انجام یک عمل از طریق دادن پاداش و تنبيه است بدون اینکه لازم باشد نحوه انجام عمل را براى عامل مشخص نمائیم. دو استراتژی اصلی برای اینکار وجود دارد: * یکی استفاده از الگوریتم های ژنتیکی است که در آن در فضای رفتارها عملی جستجو میگردد که در محیط بتواند هدف مورد نظر را بر آورده نماید. * و ديكرى استفاده از روشهاى آمارى و يوسم عامددمرك در اين درس روش دوم مد نظر است. 

صفحه 4:
22 امقایسه را با یادگیری با ناظر © یادگیری تقویتی از دو جنبه با یادگیری با ناظر تفاوت دارد: © مثالهائی یادگیری بصورت زوج >ورودی/ خروجی< مطرح نمیشوند. بلکه بعد از اينکه عامل عملی را انجام داد پاداشی را دریافت میکند و به مرحله بعدی میرود.عامل هیچ گونه اطلاعی در مورد اينکه در هر حالت بهترین عمل چیست را ندارد. بلکه اين وظیفه عامل است که در طول زمان تجربه کافی در مورد حالتهاء عمل هاى ممكنء انتقال و پاداش جمع آوری نموده و عملکرد بهینه را ياد بكيرد. © تفاوت ديكر در اينجاست كه سيستم بايد كارائى آنلاين بالائى داشته باشد. زيرا اغلب ارزيابى سيستم با عمل يادكيرى بطور همزمان صورت می پذیرد. 

صفحه 5:
نت ‎eo‏ مقایسه رااآ) با یادگیری با ناظر Supervised Learning: = Example Class Reinforcement Learning: Situation Reward Situation Reward 

صفحه 6:
یادگیری با ناظر حنج (صعه) لصفو < و ومسا صحف عجو" ‎oct vulput)‏ - الجرنج أصرحم) ‏ - سس 

صفحه 7:
‎evctvatios (“rewards” | “pecrties”)‏ = ۵ ممصم ‏(سسه) صست سم ‏هدف: جمع کردن حداکثر پاداش ممکن «هیچگونه اطلاعات مربوط به گرادیان خطا موجود نیست. ‏«حالت بعدی از روی عمل فعلی تعیین میشود. ‏یادگیری مبتنی بر سعی و خطاست. ‎ ‎ 

صفحه 8:
5 مشخصه های اصلی یادگیری قویتی © به يادكير كفته نمى شود كه جه عملى را بايد انجام دهد ‎٩‏ جستجو بر اساس سعی و خطا انجام ميشود. يادكير سعى ميكند اعمالى را يادبكيرد كه بيشترين ياداش را توليد ميكنند. ‏© ياداش از نوع تاخيرى است: از اينرو دست آوردهاى كوتاه مدت فداى مزاياى بلند مدت تر ميشوند. ‏© بايد بين كاوش موارد جديد و استفاده از دانش قبلى تناسب ايجاد نمود. #وادوجج ‎pr‏ رورم ‎٩‏ مسئله را بصورت یک عامل هدفمند که با یک محیط نامعین در ارتباط است می بیند. 

صفحه 9:
* در یک مسئله را*6 استاندارد با اجزای اصلی زیر روبرو هستیم: ‎٠‏ عامل كه قرار است يادكيرى را از طريق تعامل با محيط انجام دهد. برا يذكار بايد ‎ *‏ اعمالى كه عامل ميتوائد در محيط انجام دهد مشخص باشند. * محیط برای محیط باید مشخصه های زیر تعیین شوند: Action * ياش عامل ميتواند از طريق وروديهايش تشخيص دهد كه در جه وضعیتی قرار دارد. عامل در وضعیت ,9) عمل ع را انجام میدهد. اینکار باعث میشود وضعیت محیطربه 8 اتغيير نمايد. در اثر اين تغيير وضعيت عامل سيكنال سس و یا پاداش ,درا از محیط دریافت می نماید. عمل یادگیری عبارت است ازیاد گرفتن یک سیاست که در واق نکشتی از وضنعیت به حل لس بهتهری كد لتقف أ این سیاست برای انتخاب اعمال منجر به دریافت پاداش حداکثر از محیط گردد. ساختار کلی مسئله یادگیری تقویتی AGENT ENVIRONMENT State/ Situation s 5 Reward 1 a. (5, a) =Prf, =als, =s} 5 

صفحه 10:
* در ,ا«)عامل يادكير بطور سعى و خطا با يك محيط بويا دركير شده و ياد مى كيرد كه براى هر موقعيت جه عملى را انجام دهد. © اين محيط بايد قابل مشاهده ويا حداقل تا قسمتى قابل مشاهده براى عامل ‎(portialy obeervable) Sl:‏ مشاهده محیط ممکن است از طریق خواندن اطلاعات یک سنسور؛ توضیح سمبلیک و غیره باشد. ‎٩‏ در حالت ایده ال عامل باید بطور کامل قادر به مشاهده محیط باشد زیرا اغلب تنوریهای مربوطه بر اساس این فرض بنا شده اند. 

صفحه 11:
محيط ‎٩‏ محیط مجموعه ای از 8) حالت ممکن است. * در هر لحظه ؛ عامل میتواند یکی از 69 عمل ممکن را انجام دهد. 6 عامل ممکن است در مقابل عمل وربا مجموعه ای از اعمالی که از را دریافت کند. این پاداش ممکن است مثبت 4 ‎(ars herent) Aldo SR a (ase ۰‏ )58 یعنی انجام یک عمل مشابه در یک وضعیت یکسان به وضعیت بعدی یکسان و یا مقدار پاداش یکسانی منجر نشود. ‏* با اين وجود محيط بصورت ,بهم فرض ميشود. يعنى احتمال تغيير وضعيت و يا دريافت پاداش در طول زمان یکسان ‎a‏ ايد ‎Nay ‎ ‎ ‎Ty, Ts +‏ و5 ... 55 54 53 52 51 ‎a‏ ‏و . ... و8 يق وق و8 ب8 

صفحه 12:
$8 ارفتار عامل * عامل در محیط حرکت کرده و حالتها و پاداشهای مربوطه را به خاطر می سپارد. © عامل سعی میکند طوری رفتار کند که تابع پاداش را ماکزیمم نماید. 1-5 3+ لمر ”م ‎cede Lake ele‏ و5 ... 55 54 و5 82 ر5 32 a, a, ‏و8‎ a, a, .., ag 

صفحه 13:
The QetPorcewed Cuaiod #در ‎dle GERD‏ در یک حالت خاص عملی را انجام میدهد» در مقابل ياداش (وجمجحصص“*اوادم عس لسوررص) دريافت ميكند. در اين سيستم عامل وظيفه دارد تا ياداش دريافتى در دراز مدت را حداكثر نمايد. ار اح ‎Ry pias‏ ریک یک وصادوى ا امجح نابج بمناسب با اهداف عامل است. اينكار به طرق مختلف انجام ميشود. 

صفحه 14:
پاداش © اگر دنباله ای از پاداش ها بصورت زیر موجود باشند: Tas Ta Ting. ‏عامل بايد سعى نمايداتا ياداشى'را كه از محيط دريافت ميكند خد اكش‎ 6 E{r} ‏نماید. در واقع امید ریاضی پاداش را به حداکثر میرساند.‎ © در بسیاری از مسایل تعامل با محیط بصورت اپیزودی انجام میشود. مثلا روباتی که قرار است خروج از اتاق را یاد بگیرد به محض خارج شدن از اتاق یک اپیزود یادگیری خاتمه می یابد. لذا کل پاداشی که با شروع از یک حالت ,9) و رسیدن به حالت نهائی ( خاتمه اپیزود یادگیری) ,9) بدست می آید برابر است با: 17 +... + لجرت إل 

صفحه 15:
أذ در نظر گرفتن پاداشهای آینده ۶ اگر پاداش ‎٩‏ مجموع پاداشی باشد که عامل با شروع از زمان؛ ماد جمم كند بد حرق مكتلقك ميتوان اين مادا ۱۱ ساره ‎capa‏ ‏یک راه بصورت زير است که در آن به پاداشهای نزدیکتر ارزش بیشتری داده میشود. R=raty Tint ¥ Trot =, VYtum ‏د‎ ‎+3 5 Sf YT, Ty, Ts To R=3+... Yl (1+... 0 ۳ 

صفحه 16:
مدلهای عملکرد بهینه ۶ یکی از نکات مهم در انتخاب عمل نحوه لحاظ کردن رخداد های آ عامل است. برای اینکه یک عامل بتواند تاثیر رخدادهای آینده در برای حالت فعلی را در نظر بگیرد مدلهای مختلفی پیشنهاد شده است: ؟ مسا ‎Piette‏ ساده تین مدل این است که عامل برای انتخاب عمل مقادیر پاداشی را که در با مرحله بعد یگیرد محاسبه نموده و عملی را انتخاب نماید که مجموع پاداش را حداگثر نماید. h ViQ=2 Tax ‎fePtaite hora (discounted muxmutative reward) ©‏ در اين روش بجای :| مرحله» پاداش درازمدت دریافتی در نظر گرفته میشود. اين روش بسیار مرسوم بوده و به پاداشهانی که در آینده گرفته خواهد شد ارزش کمتری نسبت ‏به پاداشهای فوری داده ميشود. ‎ ‎oxy <1‏ عجر زط دشيور أرخمير ۱۵ ‎ 

صفحه 17:
مدلهای عملکرد بهینه ‎reward &‏ موه در اين روش فرقی بین پاداشهای نزدیک و دور در نظر گرفته نميشود. ‎V(9)=lim..53 rn ‎spe py ‏تب بر‎ 1) Finite horizon, n= SMe Mee? | OO0-0-09 Infinite horizon, y=0.9 ‎ ‎1 ‏سي م سم‎ ©9999 Average reward igs 

صفحه 18:
و اخط هشتی دا تسناستت: ‎٩‏ فرض می کنیم که اعمال عامل از قانونی مثل 77 تبعیت میکند كه آنرا خط مشى و يا ‎eel cx policy‏ ‏0 از آنجانیکه ‎)٩‏ یک متغیر تصادفی است لذا اميد رياضى آن تحت یک خط مشی خاصن و برای یک حالت معین براير خواهد بود با: ‏| 8( و وه ‎vs)‏ ‏هدف یادگیری تقویتی این است که یک خط مشی بهینه ای مثل * بيدا نمايد به نحويكه مقدار اميد رياضى فوق را براى تمامى حالات ماكزيمم كند. ‎ ‎ ‎ ‎ 

صفحه 19:
پادگیری خط مشی با سیاست Policy at step t. 7, : a mapping from states to action probabilities 7,(s.a) = probability that a, = a when s, = s © در واقع ,اه) سعى دارد عامل را وادار كند در اثر تجربه با محيط سياست خود را تغيير داده و طورى رفتار نمايد كه در دراز مدت ياداش بيشترى كسب نمايد. 

صفحه 20:
الگوریتم کلی یادگیری تقویتی جلمد أمجسجها ى مها عطاه‌و|» ‎Op Porever (!?):‏ Observe vored stite = Choose uniive 7 usiey sowe euotvaiod ‏یط‎ ‎Cxevute urticd 7 ۱۳ reward, 5’ cew state Opdate fotercd state based pa 50,55" ۲ a 

صفحه 21:
برخورد میله با زمين يك ابيزود يادكيرى با افتادن ميله خاتمه يافته و بايد پیزود بعدی را شروع نمود. reward = + Por each step bePore Poke ‏میم < مار‎ of ‏سا سوه‎ (> 

صفحه 22:
:* ابرخی کاربردهای برتر یادگیری تقویتی © ‏باعل له من(‎ Peso, Ook ‎player‏ ماما با وللو() و ‎© Clevator Ovatrol Cries & ‏سوه‎ ‎© (Probebl)) world's best douse pedk elevator ‏ام‎ ‎©» Uob-Skhop Scbkeduticgy ‏سا 6 مان‎ ‎© Work!’s best schedler of space-shutle ‏مودصم لمجايدم‎ ‎Opeeavic Chancel Ossinrect Grn & Bertschos, Die &‏ 5 روا اس سرا ارام با ان ول اه میت سا لبون و ‎ee 

صفحه 23:
‎ee‏ فرق پاداش و هدف ‎٩‏ آیا یک سیگنال عددی میتواند نشاندهنده دقیقی از یک هدف ‏باشد؟ ‎٩‏ _ممکن است نباشد! اما در عمل بطرز شگفت آوری خوب عمل كرده اسث, ‏هدف باید خارج از کنترل عامل باشد. ‏هدف باید آنچه که میخواهیم به آن برسیم را مشخص نماید و ‏اطلاعاتی در مورد نحوه رسیدن به آن را نداشته باشد. ‏© عامل بايد قادر به اندازه گیری میزان موفقیت خود باشد. 

صفحه 24:
0 ‏ووس 1۳۷) سنسمن‎ Be ‏یادگیری تقویتی با ترکیب تکنیک هر م()‎ © مس )با یادگیری با کمک ناظر به حل مسئله میپردازد. er 

صفحه 25:
Opens proyrawwicy © بطور کلی کاری که رس عنسمیی) انجام میدهد عبارت است ازحل یک مسئله چند متغیره از طریق حل مجموعه ای مسائل تک opie © مبناى بجر بر پایه اصل بهینگی مجملو9) بنا شده است ‎oF Optazaly ©‏ 0 ماو الاك ‏این اصل بسادگی بیان میکند که یک خط مشی بهینه باید داراى اين خاصیت باشد که بدون توجه به حالت اولیه و تصمیمات اولیه گر فته شده؛ باقی تصمیمات باید با درنظر گرقتن حالت ایجاد شده از تصمیمات اولیه به ‎es 

صفحه 26:
)1( 7 2۲7 ۶ در واقع وجنسممصبسسر حوممس(0 روشی است که برای حل یک مسئله از آخرین حالت ممکن شروع کرده و آنچه را که در آن حالت امکان پذیر است بررسی مینماید» سپس با استفاده از اطلاعات بدست آمده از فرض بودن در آخرین حالت به حل حالت ماقبل آخر میپردازد و اینکار برای حالت های قبل از آن ادامه می یابد. 

صفحه 27:
خاصیت مارکف © وضعیت مرحله 9 تمامی اطلاعات لازم را در اختیار عامل قرار میدهد. یعنی عامل به اطلاعات دیگری نیاز ندارد. © بعبارت دیگر قرار گرفتن در یک وضعیت به معنای داشتن خلاصه گذشته عامل است و نیازی نیست تا از گذشته آن چیز دیگری بدانیم. © نمايش یک وضعیت میتواند شامل ورودیهای فوری» ورودیهای پردازش شده و یا ساختارهای داده ای باشد که در طول زمان از روی ورودی های حس شده تشکیل شده باشند. -1 ۲ ۲ مومع ‎x ghia‏ سک حل وک دواد ‎QM Sp 42 Or‏ برك | 7 = ‎Pr Sea = Sha‏ مرح عو فود | و وگ هورگ1 .6و5 قعللهاعنط مضه .7 :5 له نم ee 

صفحه 28:
Qarhov Oecisiog Processes ‏اگرایک مسئله یادگیری نقویتی دارای خاصیت مارکف باشد مبتوان آنرا‎ * ‏یک (2006)) عووس<) مسصو() روطلی() دانست.‎ ۴ )2000* ‏اگر تعداد حالت ها و عملها محدودباشند مسئله بصورت‎ © ‏خواهد بود که با اجزای زیر تعریف یشود:‎ ۶ ‏اوه مرت لو وب‎ * dePiced by trowstion probabil /=(S_4, PR} 6 arb a As) a ‏م‎ = | $,= 5.0, < a} for all s,s’ reward 3 Ri = Eh, = 5,0, = ‏ميقع “,د له دم و مدق‎ € Als) 

صفحه 29:
Oearkov Oevision Processes (ODPs) ‎٩‏ در مسائل ‎DOP‏ با شرایطی مواجه هستیم که عامل میتواند 9) حالت ‏مجزا را درمحیط تشخیص دهد.این عامل قادر به انجام 9 عمل مجزا © در هر لحظه ؛ عامل حالت « را تشخیص داده و عمل و را انجام میدهد. 9 محیط در پاسخ به این عمل پاداش (ه,<)< را به عامل میدهد و به ‏حالت بعدی (»,ح)۵بپد میرود. ‎ ‏۶ توابع ۵ ‎ ,‏ جزئی از محیط بوده و برای عامل ناشناخته هستند. © در 000005 توابع فقط به حالت و عمل فعلی بستگی داشته و از حالت وعمل های قبلی مستقل است. 

صفحه 30:
®u ‏عم‎ Piette OOP Recycling Robot © Gieak step, robot hes to ceoide wheter i shoud (0) tel seack Poo cos, (CG) wal Por sowever ‏ذا‎ bres ta co, oy (8) 9a howe base ‏ما لت‎ ۶ ۵ beer bude ‏ی ۱ اور‎ oP ‏رو‎ bie seerchtery, hes 7 be rested (wick ts bord). © Oevisices wade va basis oP purred roery level: high, Low. © Reward = auwber oP coc ovlevted ow 

صفحه 31:
Revpoleay ®vbot DOP 0 |S = {high, low} Re" — expecteduno, of cans while searchmg A(high) = jsearch, wait} R= expectedno. of cans while waiting 4(Low) = {search wait, recharge} pessoa pease 1B, ‏ف‎ 1, rate سور و wait aL, Reece Ta, Revere 1, 2 

صفحه 32:
Opec Proqgraneicry 9 در واقع 00) روشی براى حل مسايل 000005 است. © ابن روش نیازمند دانستن نینامیک کامل سیستم است. () لب ۳) * پیاده سازی آن پرهزینه و معمولا غیر عملی است ۶ با مشکل نفرین ابعادی روبروست * تضمین شده که همگرا خواهد شد. آن راا) را یک تقریب ‎ula OP oly ba‏ نیازی به دانستن ‎)٩,)۳‏ ندارد * در فضای حالت به نمونه برداری میپردازد. © تئوریهانی در مورد همگرائی آن وجود دارد. ee 

صفحه 33:


صفحه 34:


صفحه 35:


صفحه 36:
GO, chowes lewd to viher GO, GP, 3 GP. GP was picked (ancl) وبهب-_-« 

صفحه 37:


صفحه 38:


صفحه 39:


صفحه 40:


صفحه 41:
Dent tere GS ts reuched, port oF ie SSUCKIIVE strech iF posed buck to OF... 

صفحه 42:


صفحه 43:
ی ‎OS‏ وب لد 

صفحه 44:


صفحه 45:


صفحه 46:
!£ ایادگیری خط مشی 9 اگر چه هدف نهانی یادگیری تقویتی یادگیری تابعی بصورت 00-:7۳ است با این وجود در عمل انجام آن بسیار مشکل است زیرا مثالها بصورت <ب,ج> عرضه نمیشوند. © برای یادگیری خط مشی از دو تکنیک زیر استفاده خواهیم کرد: ۶ مسمه عون ۶ موه و 6م 

صفحه 47:
Oude (Pucrtion ‎٩‏ مقدار یک حالت عبارت است ازمجموع مقدار پاداشی که با شروع از آن حالت و پیروی از خط مشی مشخصی که به حالت نهائی ختم شود» دریافت میگردد. ‎٩‏ تابع مقدار یا موسی<) ساه() عبارت است از نگاشتی ‎Law gi all sie 4S state volues 44 states J!‏ هر تقریب زننده تابع نظیر یک شبکه عصبی تخمین زده شود. ‎we 

صفحه 48:
alle (OL DD ‏یک مسئله‎ ‎ale ©‏ دارای 6 عمل مختلف است: حرکت به چپ به راست» به بالاو به يائين ‏© ياداش براى تمامى حركتها برابر -) است. ‏© هدف رسيدن به دو كوشه سمت راست يائين و يا كوشه سمت جب بالاست ‏© مقادير نشان داده شده مقدار مورد انتظار براى هر حالت در صورت انجام يك حركت تصادفى براى رسيدن به هدف است. ‏م 

صفحه 49:
# در شکل مقابل مقادیر بهینه حالتها نشان 91 داده شده است. 9 در صورتی که امکان بدست آوردن اين مقادیر وجود داشته باشد میتوان با انجام یک جستجو به ,رام امین نیز دست ‎vee Powis‏ ۱۳۲۲ یافت. ‎٩‏ در یادگیری تقویتی بجای یافتن خط مشی بهينه كه مدل کردن آن میتواند مشکل باشد» میتوان تلاش نمود تا مقدار تابع بهینه حالتها ‎Phe opted pokey pce ‎eo 

صفحه 50:


صفحه 51:
Opproxtwuttay the Odue (uariiod * یادگیری نقویتی میتواند کار بسیار سختی باشد زیرا عامل در مقابل کاری که انجام میدهد پاسخ مستقیمی در مورد درست یا نادرستی آن دریافت نمیکند. برای مثال عاملی که میخواهد از طریق شبیه سازی یک هواپیما را هدایت نماید در هر لحظه مجبور است تا تصمیم جدید بگیرد و اگر بعد از هزاران عمل هواپیما سقوط نماید؛ عامل چگونه میتواند عملی که به سقوط هواپیما منجر شده را شناسائی نماید؟ در اینجا پمسوس۳) منیجمم() با معرفی دو اصل ساده سعی در ارائه راه حل مینماید: اگر عملی انجام شود که بلافاصله منجر به نتیجه بدی نظیر سقوط هواپیما گردد عامل بايد ياد بكيرد كه در دفعات بعدى در حالت مشابه آن عمل را تکرار نکند. لذا عامل باید از عملی که بلافاصله قبل از سقوط هواپیما انجام داده بود پرهیز کند. اگر عملی در یک موقعيت خاص منجر به نتيجه ى شدء بايد از قرار گرفتن در آن موقعيت يرهيز نمود.بنا بر اين اكر قرار كر سقوط هوابيما ميشود. عامل ياد ميكيرد كه از هوابيما در جنين شرانطی میگردند پرهیر نماید. 

صفحه 52:
Tre Esseuwer vP Opannic ‏دودو بت‎ & هدف ازبكار كيرى يوس :ة) اددج ,00 در يادكيرى تقويتى محاسبه تابع مقدار است. روش كلى انجام اينكار بصورت زير است: ‎vohue Puccio‏ انم -(8) *0 * 00 ا ف نا ‎Pastor‏ ما ‎(G) Gs alls 52 ©‏ با مقدارى تصادفى عدد دهى ميشود كه با مقدار بهينه فرق 0 در نتيجه خطائی در تقریب بروز کرده ورابطه زیررا خواهیم داشت. (۶)۵ +(۵)* 0۵ <(۵) ۵ # این رابطه برای حالت بعدی نیز صادق خواهد بود ‎٩۵ ۹۵, ۶۵,0‏ <(,6) ۵ ee 

صفحه 53:
@ekvoa Poviog 9 با توجه به تعریف تابع مقدار بهینه رابطه بین مقادیر لد در حالتهای مختلف را میتوان توسط وهو اع 8) ‎Olsequatiod‏ کرد: ‎V(x) =x) tw *(X)‏ ‎٩‏ با بسط اين معادله به مقدار تابع تقریب زده شده خواهیم داشت: ‎VX =X + WO)‏ e(X, FV *(x,) = 70K, + YC) +V * Xp) ‎*(X,) = 1(X,) +O + W "OX )‏ باه ‎e(X,) = 7e(X,41) 5 

صفحه 54:
@ekvoa Patio eo © اهمیت رابطه فوق در اینجاست که اگر خطا در مرحله نهائی یعنی وقتی که به هدف میرسیم صفر باشد» در صورت انتخاب خط مشی بهینه خطا در مراحلی که منجر به مرحله آخر میگردد نیز تابعی از آن بوده وصفر خواهد شد. (X,) = OX) 1 a es G@++@++@+-@) 

صفحه 55:
Ove @uaniiva ‏تقریب تابع‎ ss * اگربتوان مقادیر تقریبی (6* را توسط یک جدول نشان داد» در اینصورت میتوان برای بدست آوردن آن اين جدول را جاروب نموده و بطور مدام مقدار حالتها را طبق رابطه زیر تغییر داد. ی( ,)0۵ ۵ © اینکار تا زمانی که تغییری در جدول رخ ندهد تکرار میشود. * برای انجام چنین عملی مدل دینامیکی سیستم لازم خواهد بود. es 

صفحه 56:
*؟ ابدست آوردن سیاست بهینه ۶ با یادگیری مقادیر میتوان از آن برای جستجوی بهترين عمل استفاده نمود. ‎x’(s) =argnaxi(s,a)+ WV (6(s,a))}‏ © لازمه اینکار دانستن تابع 8 و مقدار م است. که در حالت کلی برای ‎ale‏ ناشناخته هستندو انتخاب عمل را مشكل میسازند. لذا باید از تکنیک های دیگری استفاده نمود. هه 

صفحه 57:
oe Residual Bradicat O@kyorikws دیدیم که چگونه میتوان تقریب تابع را از طریق جدول انجام داد. استفاده از جدول محدودیتهائی را از لحاظ اندازه و پبچیدگی مسائل قابل حل بوجود میاورد.زیرا بسیاری از مسایل عملی دارای فضای حالت بسیار بزرگ و یا پیوسته هستند که نمیتوان مقادیر آنها را با جدول نشان داد در چنین مواقعی میتوان از تخمین زننده ای استفاده نمود که قابلیت تعمیم داشته و قادر به درونیابی حالتهائی باشد که مشاهده نشده اند. برای مثال شبکه عصبی میتواند برای تخمین مقدار (9))* () بکار رود. 

صفحه 58:
استفاده از شبکه عصبی یرای تخمین تابع مقدار * اگر تقریب (69)* ۵ را با (,0) ) نشان دهیم که در آن ,0) بردار پارامترها باشد در اینصورت برای تغییر اين پارامترها میتوان از رابطه زیر استفاده نمود. 21 5 2 سیر ی ‎Aw, =-a{ max(r(x,.u)+7)‏ ‎ow,‏ 1 ۲ 7 مقدار كراديان خروجى شبكه عصبى ‎<١‏ خروجى مطلوب نرخ يادكيرى * از آنجانیکه خروجی مطلوب نیز تابعی از ,() است با تغيير بردار پارامترها خروجی نیز تابعی از این مقدار جدید شده و اين احتمال وجود خواهد داشت که مقدار امسلنویر موسبلو) کاهش نیابد. هه 

صفحه 59:
Residual Bradicat O@kyorikws © يك راه حل اين مسئله استفاده )5 ‎revicksal yrodivat S355‏ ناه است که در اینصورت برای تغییر پارامترهای شبکه از رابطه زیر استفاده میشود: 9۷ _ (,۱۷,ربیط) 101 Aw, ‏بر‎ + WV (XW) V(X, (| ow ae t ween squared 65) 2 yrodicdt ‏در اين الگوریتم موی‎ ۶ te eul@ekwad residual هه 

صفحه 60:
64 [Oaks 1909] se ۶ ,مد حالت گسترش یافته الگوریتم مها ‎Ocha‏ ‏است که برای مسایل حوطس نیز بکار میرود. © یادگیری ,0-9 نوعی از یادگیری تقویتی بدون مدل است که بر پایه برنامه ریزی پویای اتفاقی عمل میکند. en 

صفحه 61:
64 * در یادگیری ,سور ) بجای انجام یک نگاشت از عس9) به مقادير حالتهاء نگاشتی از زوج «اس/صهبه به مقادیری که سادر6 نامیده میشوند انجام میگردد. © م6 ۶ به هرزوج > حالت » عمل< یک مقدار (3)5,0) نسبت داده میشود. این مقدار بارت است از مجموع پاداشهای دریافت شده وقتی که از حالت 3) شروع و عم را انجام وبدنبال آن خط مشى موجود را دنبال کرده باشیم. © تفاوت ا ‎au‏ اینجاست که نیازی به انجام تمامی ۱ ن یک اوت اين روش > یازی ام تمامی حالت نيست. 

صفحه 62:
الگوریتم یادگیری 6 © براى يادكيرى تابع © میتوان از جدولی استفاده کرد که هر ورودی آن يك زوج <ه,ج> به همراه تقریبی است که یادگیر از مقدار واقعی 6 بدست آورده است. * مقادیر اين جدول با مقدار اولیه تصادفی ) معمولا صفر( پر ميشود ۴ عامل بطور متناوب وضعیت ‎led‏ ) را تشخیص داده و عملی مثل » را انجام میدهد. سپس پاداش حاصله (,ج) و همچنین ‎ata Cilla‏ ناشی از انجام عمل(ه,ج)۵<"و را مشاهده میکند. ۶ مقادیر جدول با استفاده از رابطه زیر تغییر میکنند: ‎1(sa)+ymaxds. a)‏ جرج 

صفحه 63:
hi OOP ‏الگوریتم یادگیری برای‎ موجه ی مادعا ادها مر ‎Por ewk‏ و © Obsenve ‏او سس عا‎ > © Ov Porever: ۱ goed exerute it reveive koxvedate reward ‏عر‎ ‎Observe the vew states” * verte fe tbe ‏در‎ (S.@)Pobowe Asa< 1(5a)+ymaxds a) "وی 

صفحه 64:
© دراين مثال © مقادير 9© هرعمل/حالت در كنار آن درج شده است ‎٩‏ با هر حرکت عامل به سمت راست پاداش صفر به آن تعلق ‎a ‏۶ اگر عامل از حالت « شروع ‏کرده و به سمت راست حرکت ‏کند مقدار جدید ) برابر است ‎Asa 1sa+ymaxds, ‏با: ام‎ 2 ‎0- 0+0 0 Ou 90 ‎or ‎ ‎aod ‎64 ‎aod ‎ea ‎ ‎ ‎ ‎ ‎ ‎ ‏اه ‎5 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 65:
20 ] values v7Gs) values One optimal policy 

صفحه 66:
* از آنجانیکه در محیط یک حالت هدف جذب ‎absorbing state 8S‏ در نظر گرفته میشود که با قرار گرفتن عامل درآن حرکت عامل متوقف میشود» عمل یادگیری بصورت اپیزودی انجام ميشود. * در هر اپیزود عامل در یک محل تصادفی قرار داده میشود و تا رسیدن به حالت جذبی به تغییر مقادیر 6 ادامه میدهد. * اگر مقادیر اولیه 6 صفر در نظر گرفته شده باشند. در هر اپیزود فقط یکی از مقادیر که به مقدار نهانی نزدیکتر هستند تغیبر کرده و بقیه صفر باقی میمانند. © با افزايش تكرار اييزود ها اين مقادير غير صفر به سایر مقادیر جدول كسترش بيدا كرده و درنهايت به مقادير بهينه همكرا خواهند شد. 

صفحه 67:
:؟ ااثبات همگرائی ‎٩‏ فرض های لازم: ‎.0 ‎ee ‎tel deterxvicisic DDC Lass ‏پاداش های فوری محدود هستند|>|(,۳)2: ‏عامل تمامی حالت/عمل های موجود را بینهایت بار امتحان میکند ‏ايده اصلى: ‏اثبات ميشود كه ورودى با بيشترين مقدار خطا در جدول ©با هربار بازديد به نسبت ب از خطاى آن كاسته ميشود. 

صفحه 68:
‎aaa aye‏ آینکه تامی حملبخلتها زینه یت پار تکرزار واه شد» اگر فاصله ای را در نظر بگیریم که هرکدام حداقل یکبار تکرار شده باشند» در اینصورت خطا در مرحله ب ام تغییر مقدار جدول برابر است با: 1 ‎A,=max As a)- Asa)|‏ ‎٩‏ مقدار خطا در مرحله 0+0 ام تغيير برابر خواهد بود با: |((8,2) تميس رمم )| ‎(r+ ymax0,(s, a)‏ ع9 -9 ع9 ‎=ylmar0,(s,2)- mar0,(s, a)|‏ ‎<ymayQ,(s,4)- 0,)8,2( | ۳‏ ‎A,‏ 

صفحه 69:
* برای اینکه شرط همگرائی برقرار باشد باید هر عمل/حالت بینهایت بار تکرار شود. * در یادگیری:) معمو لایرای انتخاب عمل ها از یک رابطه احتمالاتى استفده میشود که در آن عمل های با مقاذیر ‏ با با احتمال بیشتری انتخاب ميشوند. ‎Hald=‏ احتمال انتخاب عمل > وقتى عامل در ‎era ‏حالت ج است‎ 5, Ke a) ‏(1<0_ابتی‌لستکه میزان‌ار جحیت‌صل‌هایب | مقدار بزرگ را مشخص‌میکند. مقادیر بزرگب! منجر به استفاده از دانش آموخته شده میگر ددهرامورج ‎og‏ مقادیر کوچک ‏ به بقیه عمل ها شانس بیشتری میدهد. رورس 

صفحه 70:
:؟ ایادگیری ) برای ‎orbit OOP‏ © در يك سيستم ©000() جود مص انجام يك عمل مشخص در حالت 9) همواره به حالت بعدی یکسان ,,9) منجر ميشود. * در حالیکه در یک <0006) تسیل مس از یک تابع توزیع احتمال برای تعیین حالت بعدی ناشی از انجام یک عمل استفاده میشود. #در چنین حالتی توابع (8)2,0 و (0,<) دارای توزیع احتمال بوده و بر اساس آن خروجی تصادفی خواهند داشت. 

صفحه 71:
*؟ ایادگیری ‏ برای 2000) غیرقطعی # برای حالت غير قطعى تابع ) بصورت زير بازنویسی میشود. Asa=Ex(sa)+ys As|sa)maxds a a ‏در چنین حالتی نیاز به قانون جدیدی برای یادگیری خواهد بود‎ * ‏زیرا قانون قبلی در صورت تصادفی بودن مقادیر جر قادر به‎ ‏همگرائی نخواهد بود.‎ 

صفحه 72:
:؟ ایادگیری ‏ برای ‎hie ODP‏ * برای رسیدن به همگرائی از قانون زیر استفاده میشود قا ,تسر لمعا رع +20 5)ر م (رى -0) -(۵ 9 1 ol ase On “Te visits a) در اين رابطه ‎visite (v0)‏ برابر است با مجموع دفعاتی که زوج (ه,< ) مورد استفاده قرار گرفته اند. ۵ 

صفحه 73:
Tewpord ‏ساوح(‎ se یادگیری ) حالت خاصی !5 ‎Dewoporel SSL ay Sl‏ ها مرو( است. »در يادكيرى © از اختلاف بين مقدار حالت فعلی و حالت بعد از آن استفاده ميشد. اين امر را ميتوان به اختلاف بين حالت فعلى و جند حالت بعدى تعميم داد. © اكر الكوريتم يادكيرى © را بصورت زير نشان دهيم: )0 5, ‏جك ره‎ + ymaxQs,.,a) ‏تعميم رفته در( ميتوان لسرت ير شان لا‎ este )عر ‏ميك ال تقطط ”رج يجنا "مرج + هجوت (ع‎ 2 ( 0 

صفحه 74:
الگوریتم (۳۵06» * در اين الگوریتم سعی میشود تا با معرفی ثابت(2< 2,>20 تخمین حاصله از فواصل مختلف را با هم ترکیب نمود ‎Os.a)=0- | Os,a)+2 05.042 Ols,a)+.|‏ ‎٩‏ اين الگوریتم را میتوان بصورت بازگشتی زیر نوشت 9 # برای حالت 2:50 اين الگوریتم برابربا الگوریتم یادگیری 6 خواهد بود. هریج ۵ 2+( ,مهرد -) 0 

صفحه 75:
الگوریتم (۳۵06» و درا مسانل استاده ۰ ۲ ر برخی از مسائل استفاده از این روش میتواند سرعت یادگیری را افزايش دهد. 

صفحه 76:
کیب شبکه عصبی با یادگیری 6 9 در مواقعی که امکان ذخیره مقادیر )در جدول وجود نداشته باشد» میتوان یک تابع تقریب زننده نظیر شبکه عصبی را جایگزین اين جدول نمود. © برای مثال میتوان مقادیر ه,و را بعنوان ورودیهای شبکه عصبی درنظرگرفته و شبکه را طوری آموزش داد که مقادیرتقریبی 6 را در خروجی ایجاد نماید * دربرخی کاربردها استفاده از یک شبکه عصبی جداگانه برای هر یک از عمل ها مفید بوده است. ‎٩‏ باید توجه نمود که در صورت استفاده از شبکه عصبی احتمال عدم همگرائی وجود خواهد داشت.زیرا تغییر در مقادیر وزنهای شبکه در هنگام یادگیری میتواند منجر به افزايش خطا در مقادیر ) گردد. 

صفحه 77:
:؟ |مسايل مطرح در یادگیری تقویتی یادگیری تقویتی با دو چالش عمده روبروست: © چگونگی توسعه به مسایل بزرگتر امکان استفاده در مسایل ‎panttaly-pbservable Darko‏ ‎devisiva‏ که در آنها عامل قادر به درک کامل محیط نیست 

صفحه 78:
22 سیستمهای بزرگ # وقتی که سیستم خیلی بزرگ میشود. یادگیری ) قادر به نمونه برداری از تمامی زوجهای عمل/حالت نخواهد بود. ‎٩‏ در چنین حالتی از دسته بندی کننده ها و ترکیب آنها با الگوریتمهای ژنتیک استفاده میشود ‏© استفاده از شبکه عصبی برای تقریب تابع در چنین حالتی عملی نبوده و معمولا از روشهای رگراسیون دیگری استفاده ميشود. 

صفحه 79:
قابل بیان باشد» استفاده نمود. ‎٩‏ برخلاف یادگیری با ناظرنیازی به زوج ورودی/خروجی ندارد در صورت ترکیب با شبکه های عصبی میتواند مسایل زیادی را حل کند 

یادگیری تقویتی Instructor : Saeed Shiry Mitchell Ch. 13 1 یادگیری تقویتی در یک مسئله یادگیری تقویتی با عاملی روبرو هستیم که از طریق سعی و خطا با محیط تعامل کرده و یاد میگیرد تا عملی بهینه را برای رسیدن به هدف انتخاب نماید. 2 یادگیری تقویتی ‏ ‏ یادگیری تقویتی از اینرو مورد توجه است که راهی برای آموزش عاملها برای انجام یک عمل از طریق دادن پاداش و تنبیه است بدون اینکه الزم باشد نحوه انجام عمل را برای عامل مشخص نمائیم. دو استراتژی اصلی برای اینکار وجود دارد: ‏ ‏ ‏ 3 یکی استفاده از الگوریتم های ژنتیکی است که در آن در فضای رفتارها عملی جستجو میگردد که در محیط بتواند هدف مورد نظر را بر آورده نماید. و دیگری استفاده از روشهای آماری و dynamic programming در این درس روش دوم مد نظر است. مقایسه RLبا یادگیری با ناظر ‏ یادگیری تقویتی از دو جنبه با یادگیری با ناظر تفاوت دارد: ‏ ‏ 4 مثالهائی یادگیری بصورت زوج >ورودی /خروجی< مطرح نمیشوند .بلکه بعد از اینکه عامل عملی را انجام داد پاداشی را دریافت میکند و به مWرحله بعدی میرود.عامل هیچ گونه اطالعی در مورد اینکه در هر حالت بهترین عمل چیست را ندارد .بلکه این وظیفه عامل است کWه در طول زمان تجربه کWافی در مورد حالتها، عمل های ممکن ،انتقال و پاداش جمWع آوری نموده و عمWلکرد بهینه را یاد بگیرد. تفاوت دیگر در اینجاست که سیستم باید کارائی آنالین باالئی داشته باشد .زیرا اغلب ارزیابی سیستم با عمل یادگیری بطور همزمان صورت می پذیرد.  با یادگیری با ناظرRL مقایسه Supervised Learning: Example Class Reinforcement Learning: … Situation Reward Situation Reward 5 یادگیری با ناظر Training Info = desired (target) outputs Inputs Supervised Learning System Outputs Error = (target output – actual output) 6 یادگیری تقویتی )”Training Info = evaluations (“rewards” / “penalties )”Outputs (“actions ‏RL ‏System هدف :جمع کردن حداکثر پاداش ممکن •هیچگونه اطالعات مربوط به گرادیان خطا موجود نیست. •حالت بعدی از روی عمل فعلی تعیین میشود. •یادگیری مبتنی بر سعی و خطاست. 7 ‏Inputs مشخصه های اصلی یادگیری تقویتی به یادگیر گفته نمی شود که چه عملی را باید انجام دهد جستجو بر اساس سعی و خطا انجام میشود .یادگیر سعی میکند اعمالی را یادبگیرد که بیشترین پاداش را تولید میکنند. پاداش از نوع تاخیری است :از اینرو دست آوردهای کوتاه مدت فدای مزایای بلند مدت تر میشوند. باید بین کاوش موارد جدید و استفاده از دانش قبلی تناسب ایجاد نمودexplore or exploit . مسئله را بصورت یک عامل هدفمند کWه با یک محیط نامعین در ارتباط است می بیند. 8 ساختار کلی مسئله یادگیری تقویتی در یک مسئله RLاستاندارد با اجزای اصلی زیر روبرو هستیم: عامل ‏ ‏ که قرار است یادگیری را از طریق تعامل با محیط انجام Wدهد .برای اینکار باید اعمالی که عامل میتواند در محیط انجام دهد مشخص باشند. محیط برای محیط باید مشخصه های زیر تعیین شوند: ‏ ‏ وضعیت پاداش عامل میتواند از طریق ورودیهایش تشخیص دهد که در چه وضعیتی قرار دارد .عامل در وضعیت Stعمل atرا انجام میدهد .اینکار باعث میشود وضعیت محیط به St+1 تغییر نماید .در اثر این تغییر وضعیت عامل سیگنال reinforcementو یا پاداش rt+1را از محیط دریافت می نماید. عمل یادگیری عبارت است ازیاد گرفتن یک سیاست که در واقع نگاشتی از وضعیت به عمل است به نحوی که استفاده از این سیاست برای انتخاب اعمال منجر به دریافت پاداش حداکثر از محیط گردد. 9 } t (s, a) Pr{at a | st s سیاست محیط ‏ ‏ ‏ ‏ 10 در RLعامل یادگWیر بطور سعی و خطا با یک محیط پویا درگیر شده و یاد مWی گیرد کWه برای هر موقعWیت چه عملی را انجام دهد. این محیط باید قابل مشاهده ویا حداقل تا قسمتی قابل مWشاهده برای عامل باشد)partially observable( . مشاهده محیط ممکن است از طریق خواندن اطالعات یک سنسور، توضیح سمبلیک و غیره باشد. در حالت ایده ال عامل باید بطور کامل قادر به مشاهده محیط باشد زیرا اغلب تئوریهای مربوطه بر اساس این فرض بنا شده اند. محیط ‏ ‏ ‏ محیط مجموعه ای از Sحالت ممکن است. در هر لحظه tعامل میتواند یکی از Aعمل ممکن را انجام دهد. عامل ممکن است در مقابل عمل و یا مجموعه ای از اعمالی که انجام میدهد پاداش rرا دریافت کند .این پاداش ممکن است مثبت و یا منفی )تنبیه(باشد. ‏ ‏ در حالت کلی محیط میتواند غیر قطعی ( )non deterministicباشد .یعنی انجام یک عمل مشابه در یک وضعیت یکسان به وضعیت بعدی یکسان و یا مقدار پاداش یکسانی منجر نشود. با این وجود محیط بصورت stationaryفرض میشود .یعنی احتمال تغییر وضعیت و یا دریافت پاداش در طول زمان یکسان فرض میشود. +5 0 11 +3 -1 -1 … r4 r 5 ‏r9 … ‏s9 ‏a9 … s1 s2 s3 s4 s5 … a1 a2 a3 a4 a5 ‏r1 رفتار عامل ‏ ‏ عامل در محیط حرکWت کرده و حالتها و پاداشهای مربوطه را به خاطر می سپارد. عامل سعی میکند طوری رفتار کند که تابع پاداش را ماکزیمم نماید. +5 0 12 +3 -1 -1 … r4 r 5 ‏r9 … ‏s9 ‏a9 … s1 s2 s3 s4 s5 … a1 a2 a3 a4 a5 ‏r1 The Reinforcement Function در RLوقتی عامل در یک حالت خاص عملی را انجام میدهد، در مقابل پاداش ( )reward or reinforcementدریافت میکند .در این سیستم عامل وظیفه دارد تا پاداش دریافتی در دراز مدت را حداکثر نماید. یکی از نکات طراحی یک سیستم RLتعریف یک ‏reinforcement functionمناسب با اهداف عامل است .اینکار به طرق مختلف انجام میشود. 13 پاداش ‏ اگر دنباله ای از پاداش ها بصورت زیر موجود باشند: ‏ عامل باید سعی نماید تا پاداشی را که از محیط دریافت میکند حد اکثر }E{rt نماید .در واقع امید ریاضی پاداش را به حداکثر میرساند. در بسیاری از مسایل تعامل با محیط بصورت اپیزودی انجام میشود. مثال روباتی که قرار است خروج از اتاق را یاد بگیرد به محض خارج شدن از اتاق یک اپیزود یادگیری خاتمه می یابد .لذا کل پاداشی که با شروع از یک حالت Stو رسیدن به حالت نهائی ( خاتمه اپیزود یادگیری) STبدست می آید برابر است با: ‏rt1, rt2, rt3... ‏ ‏Rt rt1rt2  ... rT در نظر گرفتن پاداشهای آینده اگر پاداش Rtمجموع پاداشی باشد که عامل با شروع از زمانt میتواند جمع کند به طرق مختلف میتوان این پاداش را محاسبه نمود. یک راه بصورت زیر است که در آن به پاداشهای نزدیکتر ارزش بیشتری داده میشود. 0  1 ‏r ‏t k1 ‏k ‏ ‏ ...  ‏k0 ‏r ‏t3 +5 0 15 ‏ ‏R r   r ‏t 2 ‏t ‏t1 +3 -1 -1 ‏r9 8 2 ‏r1 ‏r4 r 5 4 1 ‏R 3 ...  1  1 ...  50 9 مدلهای عملکرد بهینه یکی از نکات مهم در انتخاب عمل نحوه لحاظ کردن رخداد های آینده در تصمیم فعلی عامل است .برای اینکه یک عامل بتواند تاثیر رخدادهای آینده در انتخاب عمل مناسب برای حالت فعلی را در نظر بگیرد مدلهای مختلفی پیشنهاد شده است: ‏finite horizon  ساده ترین مدل این است که عامل برای انتخاب عمل مقادیر پاداشی را که در hمرحله بعد میگیرد محاسبه نموده و عملی را انتخاب نماید که مجموع پاداش را حداکثر نماید. ‏h ‏V (S)  r ‏t k ‏ ‏k0 ‏t ‏infinite horizon )discounted cumulative reward(  در این روش بجای hمرحله ،پاداش درازمدت دریافتی در نظر گرفته میشود .این روش بسیار مرسوم بوده و به پاداشهائی که در آینده گرفته خواهد شد ارزش کمتری نسبت به پاداشهای فوری داده میشود. 0  1 16 ‏r ‏t k ‏k ‏ ‏ ...  ‏k0 2 ‏V (S) r   r   r ‏t 2 ‏ ‏t1 ‏t ‏t مدلهای عملکرد بهینه ‏average reward  در این روش فرقی بین پاداشهای نزدیک و دور در نظر گWرفته نمیشود. 1 h (St) limh   rtk ‏h k0 17 ‏ ‏V خط مشی یا سیاست فرض می کنیم که اعمال عامل از قانونی مثل تبعیت میکند که آنرا خط مشی و یا policyمی نامیم. از آنجائیکه Rtیک متغیر تصادفی است لذا امید ریاضی آن تحت یک خط مشی خاص و برای یک حالت معین برابر خواهد بود با: ‏ ‏ ‏k ‏V  St E{R | S ,}E   rtk1|St,  ‏k0 18 ‏t ‏t هدف یادگیری تقویتی این است که یک خط مشی بهینه ای مثل *پیدا نماید به نحویکه مقدار امید ریاضی فوق را برای تمامی حاالت ماکزیمم کند. یادگیری خط مشی یا سیاست در واقع RLسعی دارد عامل را وادار کند در اثر تجربه با محیط سیاست خود را تغییر داده و طوری رفتار نماید که در دراز مدت پاداش بیشتری کسب نماید. الگوریتم کلی یادگیری تقویتی i. ii. Initialise learner’s internal state Do forever (!?): a. Observe current state s b. Choose action a using some evaluation function c. Execute action a d. Let r be immediate reward, s’ new state e. Update internal state based on s,a,r,s’ مثال هدف :پرهیز از افتادن افتادن یعنی: افزایش زاویه میله از یک حد مشخص برخورد میله با زمین یک اپیزود یادگیری با افتادن میله خاتمه یافته و باید اپیزود بعدی را شروع نمود. ‏reward = +1 for each step before failure ‏return = number of steps before failure >- برخی کاربردهای برتر یادگیری تقویتی  TD-Gammon  Control Crites & Barto (Probably) world's best down-peak elevator controller  Job-Shop  Tesauro, Dahl World's best backgammon player  Elevator  and Jellyfish Scheduling Zhang & Dietterich World’s best scheduler of space-shuttle payload processing  Dynamic Channel Assignment Singh & Bertsekas, Nie & Haykin  World's best assigner of radio channels to mobile telephone calls 22 فرق پاداش و هدف ‏ آیا یک سیگنال عددی میتواند نشاندهنده دقیقی از یک هدف باشد؟ ‏ ‏ ‏ ‏ 23 ممکن است نباشد! اما در عمل بطرز شگفت آوری خوب عمل کرده است. هدف باید خارج از کنترل عامل باشد. هدف باید آنچه که میخواهیم به آن برسیم را مشخص نماید و اطالعاتی در مورد نحوه رسیدن به آن را نداشته باشد. عامل باید قادر به اندازه گیری میزان موفقیت خود باشد. Dynamic Programming یادگیری تقویتی با ترکیب تکنیک Dynamic Programmingبا یادگیری با کمک ناظر به حل مسئله میپردازد. 24 Dynamic programming بطور کلی کاری که Dynamic programmingانجام میدهد عبارت است ازحل یک مWسئله چند متغیره از طریق حل مجموعه ای مسائل تک مWتغWیره مWبنای dynamic programmingبر پایه اصل بهینگی Bellmanبنا شده است ‏Richard Bellman’s Principle of Optimality  این اصل بسادگWی بیان میکند که یک خط مشی بهینه باید دارای این خاصیت باشد کWه بدون توجه به حالت اولیه و تصمیمات اولیه گرفته شده ،باقی تصمیمات باید با درنظر گرفتن حالت ایجاد شده از تصمیمات اولیه به خط مWشی بهینه برسند. 25 Dynamic programming در واقع Dynamic programmingروشی است که برای حل یک مسئله از آخرین حالت ممکن شروع کرده و آنچه را که در آن حالت امکان پذیر است بررسی مینماید ،سپس با استفاده از اطالعات بدست آمده از فرض بودن در آخرین حالت به حل حالت ماقبل آخر میپردازد و اینکار برای حالت های قبل از آن ادامه می یابد. 26 خاصیت مارکف ‏ ‏ ‏ 27 وضعیت مرحله Stتمامی اطالعات الزم را در اختیار عامل قرار میدهد. یعنی عامل به اطالعات دیگری نیاز ندارد. بعبارت دیگر قرار گرفتن در یک وضعیت به معنای داشتن خالصه گذشته عامل است و نیازی نیست تا از گذشته آن چیز دیگری بدانیم. نمایش یک وضعیت میتواند شامل ورودیهای فوری ،ورودیهای پردازش شده و یا ساختارهای داده ای باشد که در طول زمان از روی ورودی های حس شده تشکیل شده باشند. Markov Decision Processes اگر یک مسئله یادگیری تقویتی دارای خاصیت مارکف باشد میتوان آنرا . دانستMarkov Decision Process (MDP) یک finite MDP اگر تعداد حالت ها و عملها محدودباشند مسئله بصورت :خواهد بود که با اجزای زیر تعریف یشود  state and action sets one-step “dynamics” defined by transition probabilities:  reward expectations:    28 Markov Decision Processes )(MDPs ‏ در مسائل MDPبا شرایطی مواجه هستیم که عامل میتواند Sحالت مجزا را درمحیط تشخیص دهد.این عامل قادر به انجام Aعمل مجزا میباشد. در هر لحظه tعامل حالت stرا تشخیص داده و عمWل atرا انجام میدهد. ‏ مWحیط در پاسخ به این عمل پاداش ) rt=(st,atرا به عامل مWیدهد و به حالت بعدی ) st+1=(st,atمیرود. ‏ توابع r , جزئی از محیط بوده و برای عامل ناشناخته هستند. در MDPتوابع فقط به حالت و عمل فعWلی بستگی داشته و از حالت وعمWل های قبلی مستقل است.W ‏ ‏ 29 An Example Finite MDP Recycling Robot At each step, robot has to decide whether it should (1) actively search for a can, (2) wait for someone to bring it a can, or (3) go to home base and recharge.  Searching is better but runs down the battery; if runs out of power while searching, has to be rescued (which is bad).  Decisions made on basis of current energy level: high, low.  Reward = number of cans collected  30 Recycling Robot MDP 31 action node Dynamic Programming در واقع DPروشی برای حل مسایل MDPاست. ‏ ‏ ‏ ‏ این روش نیازمند دانستن دینامیک کامل سیستم است)P and R( . پیاده سازی آن پرهزینه و معموال غیر عملی است با مشکل نفرین ابعادی روبروست تضمین شده که همگرا خواهد شد. میتوان RLرا یک تقریب برخط برای DPدانست. ‏ ‏ ‏ 32 نیازی به دانستن R,Pندارد در فضای حالت به نمونه برداری میپردازد. تئوریهائی در مورد همگرائی آن وجود دارد. Reinforcement learning example Start S2 S4 S3 S8 S5 Arrows indicate strength between two problem states Start maze … S7 Goal Start S2 The first response leads to S2 … S4 S3 S8 S7 The next state is chosen by randomly sampling from the possible next states weighted by their associative strength Associative strength = line width S5 Goal Start S2 S4 S3 S8 S5 Suppose the randomly sampled response leads to S3 … S7 Goal Start S2 At S3, choices lead to either S2, S4, or S7. S4 S3 S8 S5 S7 was picked (randomly) S7 Goal Start S2 By chance, S3 was picked next… S4 S3 S8 S5 S7 Goal Start S2 Next response is S4 S4 S3 S8 S5 S7 Goal Start S2 And S5 was chosen next (randomly) S4 S3 S8 S5 S7 Goal Start S2 And the goal is reached … S4 S3 S8 S5 S7 Goal Start S2 S4 S3 S8 S5 S7 Goal is reached, strengthen the associative connection between goal state and last response Next time S5 is reached, part of the associative strength is passed back to S4... Goal Start S2 …Start maze again S4 S3 S8 S5 S7 Goal Start S2 S4 S3 S8 S5 Let’s suppose after a couple of moves, we end up at S5 again S7 Goal Start S2 S4 S3 S8 S5 S7 S5 is likely to lead to GOAL through strenghtened route In reinforcement learning, strength is also passed back to the last state This paves the way for the next time going through maze Goal Start S2 The situation after lots of restarts … S4 S3 S8 S5 S7 Goal یادگیری خط مشی اگر چه هدف نهائی یادگیری تقویتی یادگیری تابعی بصورت *:SAاست با این وجود در عمل انجام آن بسیار مشکل است زیرا مثالها بصورت < >s,aعرضه نمیشوند. برای یادگیری خط مشی از دو تکنیک زیر استفاده خواهیم کرد: ‏ ‏ 46 ‏Value Function ‏Q Value Value Function مقدار یک حالت عبارت است ازمجموع مقدار پاداشی که با شروع از آن حالت و پیروی از خط مشی مشخصی که به حالت نهائی ختم شود ،دریافت میگردد. تابع مقدار یا Value Functionعبارت است از نگاشتی از statesبه state valuesکه میتواند توسط هر تقریب زننده تابع نظیر یک شبکه عصبی تخمین زده شود. 47 مثال یک مسئله MDPبا 16حالت عامل دارای 4عمل مختلف است :حرکت به چپ ،به راست، به باالو به پائین پاداش برای تمامی حرکتها برابر 1-است. هدف رسیدن به دو گوشه سمت راست پائین و یا گوشه سمت چپ باالست مقادیر نشان داده شده مقدار مورد انتظار برای هر حالت در صورت انجام یک حرکت تصادفی برای رسیدن به هدف است. 48 The optimal value function در شکل مقابل مقادیر بهینه حالتها نشان داده شده است. در صورتی که امکان بدست آوردن این مقادیر وجود داشته باشد میتوان با انجام یک جستجو به optimal policyنیز دست یافت. در یادگیری تقویتی بجای یافتن خط مشی بهینه که مدل کردن آن میتواند مشکل باشد، میتوان تالش نمود تا مقدار تابع بهینه حالتها را بدست آورد. 49 ‏The optimal value function ‏The optimal policy Value Iteration مثال with primitive actions (cell-to-cell) V(goal )=1 Iteration #1 Iteration #2 Iteration #3 with behaviors (room-to-room) V(goal )=1 Iteration #1 Iteration #2 Iteration #3 Approximating the Value Function ‏ ‏ ‏ 51 یادگیری تقویتی میتواند کار بسیار سختی باشد زیرا عامل در مقابل کاری که انجام میدهد پاسخ مستقیمی در مورد درست یا نادرستی آن دریافت نمیکند. برای مثال عاملی که میخواهد از طریق شبیه سازی یک هواپیما را هدایت نماید در هر لحظه مجبور است تا تصمیم جدید بگیرد و اگر بعد از هزاران عمل هواپیما سقوط نماید، عامل چگونه میتواند عملی که به سقوط هواپیما منجر شده را شناسائی نماید؟ در اینجا Dynamic Programmingبا معرفی دو اصل ساده سعی در ارائه راه حل مینماید: اگر عملی انجام شود که بالفاصله منجر به نتیجه بدی نظیر سقوط هواپیما گردد عامل باید یاد بگیرد که در دفعات بعدی در حالت مشابه آن عمل را تکرار نکند .لذا عامل باید از عملی که بالفاصله قبل از سقوط هواپیما انجام داده بود پرهیز کند. اگر عملی در یک موقعیت خاص منجر به نتیجه بدی شد ،باید از قرار گرفتن در آن موقعیت پرهیز نمود.بنا بر این اگر قرار گرفتن در جهت و موقعیت خاصی منجر به سقوط هواپیما میشود ،عامل یاد میگیرد که از انجام عملیاتی که منجر به قرار گرفتن هواپیما در چنین شرائطی میگردند پرهیر نماید. The Essence of Dynamic ‏Programming ‏ ‏ ‏ 52 هدف ازبکار گیری Dynamic Programmingدر یادگیری تقویتی مWحاسبه تابع مقدار است .Wروش کلی انجام اینکار بصورت زیر است: ‏ V*(S )= Optimal value function ‏t ‏ V (S )= approximate of optimal value function ‏t ‏ =discount factor در حالت کلی ) V (Stبا مقداری تصادفی عدد دهی میشود که با مقدار بهینه فرق دارد .در نتیجه خطائی در تقریب بروز کرده ورابطه زیررا خواهیم داشت.W )V (St)= V *(St)+ e(St این رابطه برای حالت بعدی نیز صادق خواهد بود )V (St+1)= V *(St+1)+ e(St+1 Bellman equation با توجه به تعریف تابع مقدار بهینه ،رابطه بین مقادیر value ‏functionدر حالتهای مختلف را میتوان توسط Bellman ‏equationبیان کرد: با بسط این معادله به مقدار تابع تقریب زده شده خواهیم داشت: 53 Bellman equation اهمیت رابطه فوق در اینجاست که اگر خطا در مرحله نهائی یعنی وقتی که به هدف میرسیم صفر باشد ،در صورت انتخاب خط مشی بهینه خطا در مراحلی که منجر به مرحله آخر میگردد نیز تابعی از آن بوده وصفر خواهد شد. 54 تقریب تابع Value Function اگربتوان مقادیر تقریبی *Vرا توسط یک جدول نشان داد ،در اینصورت میتوان برای بدست آوردن آن این جدول را جاروب نموده و بطور مدام مقدار حالتها را طبق رابطه زیر تغییر داد. اینکار تا زمانی که تغییری در جدول رخ ندهد تکرار میشود. برای انجام چنین عملی مدل دینامیکی سیستم الزم خواهد بود. 55 بدست آوردن سیاست بهینه با یادگیری مقادیر میتوان از آن برای جستجوی بهترین عمل استفاده نمود. * * })) (s) argmax{r(s, a)  V ( (s, a ‏a الزمه اینکار دانستن تابع و مقدار r Wاست .که در حالت کلی برWای عامل ناشناخته هستندو انتخاب عمل را مشکل میسازند .لذا باید از تکنیک های دیگری استفاده نمود. 56 Residual Gradient Algorithms ‏ ‏ ‏ ‏ 57 دیدیم که چگونه میتوان تقریب تابع را از طریق جدول انجام داد. استفاده از جدول محدودیتهائی را از لحاظ اندازه و پیچیدگی مWسائل قابل حل بوجود میاورد.زیرا بسیاری از مسایل عمWلی دارای فضای حالت بسیار بزرگ و یا پیوسته هستند که نمیتوان مWقادیر آنها را با جدول نشان داد در چنین مواقعی میتوان از تخمWین زننده ای استفاده نمود که قابلیت WتعمWیم داشته و قادر به درونیابی حالتهائی باشد که مشاهده نشده اند. برای مثال شبکه عصبی میتواند برای تخمین مقدار ) V *(Stبکار رود. استفاده از شبکه عصبی یرای تخمین تابع مقدار ‏ اگWر تقریب ) V *(Stرا با ) V (St,Wtنشان دهیم که در آن Wt بردار پارامWترها باشد در اینصورت برای تغWییر این پارامترها میتوان از رابطه زیر استفاده نمود. مقدار گرادیان ‏ 58 خروجی شبکه عصبی خروجی مطلوب نرخ یادگیری از آنجائیکه خروجی مطلوب نیز تابعی از Wtاست Wبا تغییر بردار پارامترها خروجی نیز تابعWی از این مWقدار جدید شده و این احتمال وجود خواهد داشت WکWه مقدار Bellman residualکاهش نیابد. Residual Gradient Algorithms یک راه حل این مسئله استفاده از تکنیک residual gradient algorithmاست که در اینصورت برای تغییر پارامترهای شبکه از رابطه زیر استفاده میشود: در این الگوریتم gradient descentبر روی mean squared ‏Bellman residualانجام میشود. 59 []Watkins,1989 ‏Q-learning Q-learning حالت گسترش یافته الگوریتم Value Iteration است که برای مسایل nondeterministicنیز بکار میرود. یادگیری Q-learningنوعی از یادگیری تقویتی بدون مدل است که بر پایه برنامه ریزی Wپویای اتفاقی عمل میکند. 60 Q-learning ‏ ‏ 61 در یادگیری Q –Learningبجای انجام یک نگاشت از Statesبه مWقادیر حالتهWا ،نگاشتی از زوج state/actionبه مقادیری که Q-value نامیده میشوند انجام میگردد. ‏Q-Function ‏ به هرزوج > حالت ،عمل< یک مقدار ) Q(s,aنسبت داده میشود .این مقدار عبارت است از مجموع پاداشهای دریافت شده وقتی که از حالت Sشروع و عمل aرا انجام وبدنبال آن خط مشی موجود را دنبال کرده باشیم. ‏ تفاوت این روش با قبلی در اینجاست که نیازی به انجام تمامی اعمال ممکن یک حالت نیست. الگوریتم یادگیری Q ‏ ‏ ‏ ‏ برای یادگWیری تابع Qمیتوان از جدولی استفاده کرد که هر ورودی آن یک زوج < >s,aبه همراه تقریبی است Wکه یادگیر از مقدار واقعWی Q بدست آورده است.W مWقادیر این جدول با مقدار اولیه تصادفی ) معموال صفر( پر میشود عامل بطور مWتناوب وضعیت فعWلی Sرا تشخیص داده و عملی مثل a را انجام میدهد .سپس پاداش حاصله ) r(s,aو همچنین حالت جدید ناشی از انجام عمل) s’=(s,aرا مشاهده میکند. مWقادیر جدول با استفاده از رابطه زیر تغییر میکنند: ‏ ‏Q(s,a) r(s,a) maxQ s, a 'a ' 62 ‏ ‏ ‏ '  قطعیMDP برایQ الگوریتم یادگیری     Q(tos,zero a) For each s,a initialize the table entry Observe the current state s Do forever:     Select an action a and execute it receive immediate reward r Observe the new state s’  Q(s,as a)follows update the table entry for   ss’   Q(s,a) r(s,a) maxQ s, a a' '  ' 63 مثال ‏ ‏ ‏ ‏ ' ‏ 64 100 در این مثال مقادیر Qهرعمل/حالت در کنار آن درج شده است با هر حرکت عامل به Wسمت راست پاداش Wصفر به آن تعلق میگیرد. اگر عامل از حالت slشروع کرده و به سمت راست حرکت کند مقدار جدید Qبرابر است ‏ باQ(s,a) r(s,a) maxQs,a : ' ' 73 ‏ ‏a 0 00.9 max 66,81,100 0 90 81 66 90 100 81 66 ‏sl مثال 65 اپیزود های یادگیری ‏ ‏ ‏ ‏ 66 از آنجائیکه در محیط یک حالت هدف جذب کننده absorbing stateدر نظر گWرفته میشود که با قرار گرفتن عامل درآن حرکت عامWل متوقف میشود ،عمل یادگیری بصورت اپیزودی انجام میشود. در هر اپیزود عامل در یک مWحل تصادفی قرار داده میشود و تا رسیدن به حالت جذبی به تغییر مقادیر Qادامه میدهد. اگر مقادیر اولیه Qصفر در نظر گرفته شده باشند ،در هر اپیزود فقط یکی از مقادیر کWه به مقدار نهائی نزدیکتر هستند تغییر کWرده و بقیه صفر باقی میمانند. با افزایش تکرار اپیزود ها این مقادیر غیر صفر به سایر مقادیر جدول گسترش پیدا کرده و درنهایت به مقادیر بهینه همWگرا خواهند شد. اثبات همگرائی ‏ .1 .2 .3 ‏ ‏ 67 فرض های الزم: محیط deterministic MDPاست. پاداش های فوری محدود هستند|: r(s,a)|<c عامل تمامی حالت/عمل های موجود را بینهایت بار امتحان میکند ایده اصلی: اثبات میشود که ورودی با بیشترین مقدار خطا در جدول Qبا هربار بازدید به نسبت از خطای آن کاسته میشود. اثبات همگرائی با توجه به اینکه تمامی عمل/حالتها بینهایت بار تکرار خواهند شد ،اگر فاصله ای را در نظر بگیریم که هرکدام حداقل یکبار تکرار شده باشند ،در اینصورت خطا در مرحله nام تغییر مقدار جدول برابر است با: | )|Q(s, a)  Q(s, a ‏n max ‏sa ‏ , مقدار خطا در مرحله n+1ام تغییر برابر خواهد بود با: ‏ ‏ | ))'|Qn1(s, a)  Q(s, a) || (r   maxQn (s', a')) | (r   maxQn (s', a 'a 'a ‏ | )' | maxQn (s', a')  maxQn (s', a 'a 'a ‏ 68 | )' max|Qn (s', a')  Qn (s', a 'a ‏ n نحوه انجام آزمایش برای اینکه شرط همگرائی برقرار باشد باید هر عمل/حالت بینهایت بار تکرار شود. در یادگیری Qمعموالبرای انتخاب عمل ها از یک رابطه احتماالتی استفاده میشود که در آن عمل های با مقادیر Qباال با احتمال بیشتری انتخاب میشوند. ‏ ‏Q s,ai  ‏k ‏Q a  ‏k ‏ ‏j ‏s, ‏Pai | s  احتمال انتخاب عمل aiوقتی عامل در حالت sاست ‏j 69 ‏K>0ثWWWابتیاWستکWWWه WمیزاWنارجحیتعملهایبWWWا مقدار بWWWزرگ Qرا مشخصمیکند. مقادیر بزرگ kمنجر به استفاده از دانش آموخته شده میگرددexploit مقادیر کوچک kبه بقیه عمل ها شانس بیشتری میدهدexplore . یادگیری Qبرای MDPغیرقطعی در یک سیستم deterministic MDPانجام یک عمل مشخص در حالت Stهمواره به حالت بعدی یکسان St+1منجر میشود. در حالیکه در یک non-deterministic MDPاز یک تابع توزیع احتمال برای تعیین حالت بعدی ناشی از انجام یک عمل استفاده میشود. در چنین حالتی توابع ) (s,aو ) r(s,aدارای توزیع احتمال بوده و بر اساس آن خروجی تصادفی خواهند داشت. 70 یادگیری Qبرای MDPغیرقطعی برای حالت غیر قطعی تابع Qبصورت زیر بازنویسی میشود. ‏ ‏ ‏Q(s,a)E r(s,a)  P(s'|s,a) maxQ s, a 's 'a ' ' ‏ ‏ در چنین حالتی نیاز به قانون جدیدی برای یادگیری خواهد بود زیرا قانون قبلی در صورت تصادفی بودن مقادیر ’r ,sقادر به همگرائی نخواهد بود. 71 یادگیری Qبرای MDPغیرقطعی برای رسیدن به همگرائی از قانون زیر استفاده میشود ‏ ‏ ‏ ‏ ' ' ‏Qn(s,a)  (1  n)Qn 1(s,a)  n r(s,a) maxQn 1s,a  'a ‏ ‏ که در آن 1 ) n 1 visitsn(s, a در این رابطه ) visitsn(s,aبرابر است با مجموع دفعاتی که زوج ( ) s,aمورد استفاده قرار گرفته اند. 72 Temporal difference learning یادگیری Qحالت خاصی از الگوریتم یادگیری Temporal difference learningاست. در یادگیری Qاز اختالف بین مقدار حالت فعلی و حالت بعد از آن استفاده میشد .این امر را میتوان به اختالف بین حالت فعلی و چند حالت بعدی تعمیم داد. اگر الگوریتم یادگیری Qرا بصورت زیر نشان دهیم: ) Q (st , at ) rt   maxQ(st , a ‏ 1 ‏1 ‏a حالت تعمیم یافته آنرا میتوان بصورت زیر نشان داد: ‏n ) Q (st , at ) rt  rt  ...  n rt n   n maxQ(st n, a ‏ ‏1 73 ‏ 1 ‏ ‏a ‏1 الگوریتم )TD( در این الگوریتم سعی میشود تا با معرفی ثابت<=1 <=0 تخمین حاصله از فواصل مختلف را با هم ترکیب نمود 1 2 3 2 ‏ (st , at ) (1  ) Q (st , at )   Q (st , at )   Q (st , at )  ... ‏ ‏ ‏Q ‏ این الگوریتم را میتوان بصورت بازگشتی زیر نوشت ‏ ‏ ‏ ‏ (st , at ) rt    (1  ) maxQ(st , at )   Q (st1, at1) ‏a ‏ ‏ ‏Q ‏ برای حالت =0این الگوریتم برابربا الگوریتم یادگیری Q خواهد بود. 74 الگوریتم )TD( در برخی از مسائل استفاده از این روش میتواند سرعت یادگیری را افزایش دهد. 75 ترکیب شبکه عصبی با یادگیری Q ‏ ‏ ‏ ‏ 76 در مواقعی که امWکان ذخیره مقادیر Qدر جدول وجود نداشته باشد، مWیتوان یک تابع تقریب زننده نظیر شبکه عصبی را جایگزین این جدول نمود. برای مثال میتوان مقادیر s,aرا بعنوان ورودیهای شبکه عصبی درنظرگرفته و شبکه را طوری آموزش داد کWه مWقادیرتقریبی Qرا در خروجی ایجاد نماید. دربرخی کاربردها استفاده از یک شبکه عصبی جداگانه برای هر یک از عمWل ها مفید بوده است.W باید توجه نمود که در صورت استفاده از شبکه عصبی احتمال عدم همWگرائی وجود خواهد داشت.زیرا تغییر در مقادیر وزنهای شبکه در هنگام یادگیری میتواند منجر به افزایش خطا در مWقادیر Qگردد. مسایل مطرح در یادگیری تقویتی ‏ ‏ ‏ 77 یادگیری تقویتی با دو چالش عمده روبروست: چگونگی توسعه به مسایل بزرگتر امکان استفاده در مسایل partially-observable Markov decisionکه در آنها عامل قادر به درک کامل محیط نیست سیستمهای بزرگ وقتی که سیستم خیلی بزرگ میشود ،یادگیری Qقادر به نمونه برداری از تمامی زوجهای عمل/حالت نخواهد بود. در چنین حالتی از دسته بندی کننده ها و ترکیب آنها با الگوریتمهای ژنتیک استفاده میشود استفاده از شبکه عصبی برای تقریب تابع در چنین حالتی عملی نبوده و معموال از روشهای رگراسیون دیگری استفاده میشود. 78 نتیجه گیری یادگیری تقویتی را میتوان درهرمسئله ایکه بصورت MDP قابل بیان باشد ،استفاده نمود. برخالف یادگیری با ناظرنیازی به زوج ورودی/خروجی ندارد در صورت ترکیب با شبکه های عصبی میتواند مسایل زیادی را حل کند 79