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

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

اسلاید 1: 1یادگیری تقویتیInstructor : Saeed Shiry& Mitchell Ch. 13

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

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

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

اسلاید 5: 5Supervised Learning:Example ClassReinforcement Learning:Situation RewardSituation Reward…مقایسه RL با یادگیری با ناظر

اسلاید 6: یادگیری با ناظرSupervised Learning SystemInputsOutputsTraining Info = desired (target) outputsError = (target output – actual output)6

اسلاید 7: یادگیری تقویتیRLSystemInputsOutputs (“actions”)Training Info = evaluations (“rewards” / “penalties”)هدف: جمع کردن حداکثر پاداش ممکنهیچگونه اطلاعات مربوط به گرادیان خطا موجود نیست.حالت بعدی از روی عمل فعلی تعیین میشود.یادگیری مبتنی بر سعی و خطاست. 7

اسلاید 8: مشخصه های اصلی یادگیری تقویتیبه یادگیر گفته نمی شود که چه عملی را باید انجام دهدجستجو بر اساس سعی و خطا انجام میشود. یادگیر سعی میکند اعمالی را یادبگیرد که بیشترین پاداش را تولید میکنند.پاداش از نوع تاخیری است: از اینرو دست آوردهای کوتاه مدت فدای مزایای بلند مدت تر میشوند.باید بین کاوش موارد جدید و استفاده از دانش قبلی تناسب ایجاد نمود. explore or exploitمسئله را بصورت یک عامل هدفمند که با یک محیط نامعین در ارتباط است می بیند.8

اسلاید 9: ساختار کلی مسئله یادگیری تقویتیدر یک مسئله RL استاندارد با اجزای اصلی زیر روبرو هستیم:عاملکه قرار است یادگیری را از طریق تعامل با محیط انجام دهد. برای اینکار بایداعمالی که عامل میتواند در محیط انجام دهد مشخص باشند.محیطبرای محیط باید مشخصه های زیر تعیین شوند:وضعیتپاداشعامل میتواند از طریق ورودیهایش تشخیص دهد که در چه وضعیتی قرار دارد. عامل در وضعیت St عمل at را انجام میدهد. اینکار باعث میشود وضعیت محیط به St+1 تغییر نماید. در اثر این تغییر وضعیت عامل سیگنال reinforcement و یا پاداش rt+1 را از محیط دریافت می نماید.عمل یادگیری عبارت است ازیاد گرفتن یک سیاست که در واقع نگاشتی از وضعیت به عمل است به نحوی که استفاده از این سیاست برای انتخاب اعمال منجر به دریافت پاداش حداکثر از محیط گردد.9سیاست

اسلاید 10: 10محیطدر RLعامل یادگیر بطور سعی و خطا با یک محیط پویا درگیر شده و یاد می گیرد که برای هر موقعیت چه عملی را انجام دهد.این محیط باید قابل مشاهده ویا حداقل تا قسمتی قابل مشاهده برای عامل باشد. (partially observable) مشاهده محیط ممکن است از طریق خواندن اطلاعات یک سنسور، توضیح سمبلیک و غیره باشد.در حالت ایده ال عامل باید بطور کامل قادر به مشاهده محیط باشد زیرا اغلب تئوریهای مربوطه بر اساس این فرض بنا شده اند.

اسلاید 11: 11محیطمحیط مجموعه ای از S حالت ممکن است.در هر لحظه t عامل میتواند یکی از A عمل ممکن را انجام دهد.عامل ممکن است در مقابل عمل و یا مجموعه ای از اعمالی که انجام میدهد پاداش r را دریافت کند. این پاداش ممکن است مثبت و یا منفی )تنبیه(باشد.در حالت کلی محیط میتواند غیر قطعی (non deterministic) باشد. یعنی انجام یک عمل مشابه در یک وضعیت یکسان به وضعیت بعدی یکسان و یا مقدار پاداش یکسانی منجر نشود.با این وجود محیط بصورت stationary فرض میشود. یعنی احتمال تغییر وضعیت و یا دریافت پاداش در طول زمان یکسان فرض میشود.s9s5s4s2………s3+50-1-1+3r9r5r4r1s1a9a5a4a2…a3a1

اسلاید 12: 12رفتار عاملعامل در محیط حرکت کرده و حالتها و پاداشهای مربوطه را به خاطر می سپارد.عامل سعی میکند طوری رفتار کند که تابع پاداش را ماکزیمم نماید.s9s5s4s2………s3+50-1-1+3r9r5r4r1s1a9a5a4a2…a3a1

اسلاید 13: 13The Reinforcement Functionدر RLوقتی عامل در یک حالت خاص عملی را انجام میدهد، در مقابل پاداش (reward or reinforcement) دریافت میکند. در این سیستم عامل وظیفه دارد تا پاداش دریافتی در دراز مدت را حداکثر نماید.یکی از نکات طراحی یک سیستم RL تعریف یک reinforcement functionمناسب با اهداف عامل است. اینکار به طرق مختلف انجام میشود.

اسلاید 14: پاداشاگر دنباله ای از پاداش ها بصورت زیر موجود باشند:عامل باید سعی نماید تا پاداشی را که از محیط دریافت میکند حد اکثر نماید. در واقع امید ریاضی پاداش را به حداکثر میرساند.در بسیاری از مسایل تعامل با محیط بصورت اپیزودی انجام میشود. مثلا روباتی که قرار است خروج از اتاق را یاد بگیرد به محض خارج شدن از اتاق یک اپیزود یادگیری خاتمه می یابد. لذا کل پاداشی که با شروع از یک حالت St و رسیدن به حالت نهائی ( خاتمه اپیزود یادگیری) ST بدست می آید برابر است با:

اسلاید 15: 15در نظر گرفتن پاداشهای آیندهاگر پاداش Rt مجموع پاداشی باشد که عامل با شروع از زمانt میتواند جمع کند به طرق مختلف میتوان این پاداش را محاسبه نمود. یک راه بصورت زیر است که در آن به پاداشهای نزدیکتر ارزش بیشتری داده میشود.+50-1-1+3r9r5r4r1

اسلاید 16: 16مدلهای عملکرد بهینهیکی از نکات مهم در انتخاب عمل نحوه لحاظ کردن رخداد های آینده در تصمیم فعلی عامل است. برای اینکه یک عامل بتواند تاثیر رخدادهای آینده در انتخاب عمل مناسب برای حالت فعلی را در نظر بگیرد مدلهای مختلفی پیشنهاد شده است: finite horizonساده ترین مدل این است که عامل برای انتخاب عمل مقادیر پاداشی را که در h مرحله بعد میگیرد محاسبه نموده و عملی را انتخاب نماید که مجموع پاداش را حداکثر نماید.(discounted cumulative reward) infinite horizonدر این روش بجای h مرحله، پاداش درازمدت دریافتی در نظر گرفته میشود. این روش بسیار مرسوم بوده و به پاداشهائی که در آینده گرفته خواهد شد ارزش کمتری نسبت به پاداشهای فوری داده میشود.

اسلاید 17: 17مدلهای عملکرد بهینهaverage rewardدر این روش فرقی بین پاداشهای نزدیک و دور در نظر گرفته نمیشود.

اسلاید 18: 18خط مشی یا سیاستفرض می کنیم که اعمال عامل از قانونی مثل p تبعیت میکند که آنرا خط مشی و یا policy می نامیم.از آنجائیکه Rt یک متغیر تصادفی است لذا امید ریاضی آن تحت یک خط مشی خاص و برای یک حالت معین برابر خواهد بود با:هدف یادگیری تقویتی این است که یک خط مشی بهینه ای مثل p* پیدا نماید به نحویکه مقدار امید ریاضی فوق را برای تمامی حالات ماکزیمم کند.

اسلاید 19: یادگیری خط مشی یا سیاستدر واقع RL سعی دارد عامل را وادار کند در اثر تجربه با محیط سیاست خود را تغییر داده و طوری رفتار نماید که در دراز مدت پاداش بیشتری کسب نماید.

اسلاید 20: الگوریتم کلی یادگیری تقویتیInitialise learner’s internal stateDo forever (!?):Observe current state sChoose action a using some evaluation functionExecute action a Let r be immediate reward, s’ new stateUpdate internal state based on s,a,r,s’

اسلاید 21: مثالهدف: پرهیز از افتادنافتادن یعنی:افزایش زاویه میله از یک حد مشخصبرخورد میله با زمینیک اپیزود یادگیری با افتادن میله خاتمه یافته و باید اپیزود بعدی را شروع نمود.reward = +1 for each step before failure-> return = number of steps before failure

اسلاید 22: برخی کاربردهای برتر یادگیری تقویتیTD-Gammon and Jellyfish Tesauro, DahlWorlds best backgammon playerElevator Control Crites & Barto(Probably) worlds best down-peak elevator controllerJob-Shop Scheduling Zhang & DietterichWorld’s best scheduler of space-shuttle payload processingDynamic Channel Assignment Singh & Bertsekas, Nie & HaykinWorlds best assigner of radio channels to mobile telephone calls22

اسلاید 23: 23فرق پاداش و هدفآیا یک سیگنال عددی میتواند نشاندهنده دقیقی از یک هدف باشد؟ممکن است نباشد! اما در عمل بطرز شگفت آوری خوب عمل کرده است.هدف باید خارج از کنترل عامل باشد.هدف باید آنچه که میخواهیم به آن برسیم را مشخص نماید و اطلاعاتی در مورد نحوه رسیدن به آن را نداشته باشد.عامل باید قادر به اندازه گیری میزان موفقیت خود باشد.

اسلاید 24: 24Dynamic Programmingیادگیری تقویتی با ترکیب تکنیک Dynamic Programming با یادگیری با کمک ناظر به حل مسئله میپردازد.

اسلاید 25: 25Dynamic programmingبطور کلی کاری که Dynamic programming انجام میدهد عبارت است ازحل یک مسئله چند متغیره از طریق حل مجموعه ای مسائل تک متغیرهمبنای dynamic programming بر پایه اصل بهینگی Bellman بنا شده استRichard Bellman’s Principle of Optimalityاین اصل بسادگی بیان میکند که یک خط مشی بهینه باید دارای این خاصیت باشد که بدون توجه به حالت اولیه و تصمیمات اولیه گرفته شده، باقی تصمیمات باید با درنظر گرفتن حالت ایجاد شده از تصمیمات اولیه به خط مشی بهینه برسند.

اسلاید 26: 26Dynamic programming در واقع Dynamic programming روشی است که برای حل یک مسئله از آخرین حالت ممکن شروع کرده و آنچه را که در آن حالت امکان پذیر است بررسی مینماید، سپس با استفاده از اطلاعات بدست آمده از فرض بودن در آخرین حالت به حل حالت ماقبل آخر میپردازد و اینکار برای حالت های قبل از آن ادامه می یابد.

اسلاید 27: 27خاصیت مارکفوضعیت مرحله St تمامی اطلاعات لازم را در اختیار عامل قرار میدهد. یعنی عامل به اطلاعات دیگری نیاز ندارد.بعبارت دیگر قرار گرفتن در یک وضعیت به معنای داشتن خلاصه گذشته عامل است و نیازی نیست تا از گذشته آن چیز دیگری بدانیم.نمایش یک وضعیت میتواند شامل ورودیهای فوری، ورودیهای پردازش شده و یا ساختارهای داده ای باشد که در طول زمان از روی ورودی های حس شده تشکیل شده باشند.

اسلاید 28: 28Markov Decision Processesاگر یک مسئله یادگیری تقویتی دارای خاصیت مارکف باشد میتوان آنرا یک Markov Decision Process (MDP) دانست.اگر تعداد حالت ها و عملها محدودباشند مسئله بصورت finite MDP خواهد بود که با اجزای زیر تعریف یشود:state and action setsone-step “dynamics” defined by transition probabilities:reward expectations:

اسلاید 29: 29Markov Decision Processes (MDPs)در مسائل MDP با شرایطی مواجه هستیم که عامل میتواند S حالت مجزا را درمحیط تشخیص دهد.این عامل قادر به انجام A عمل مجزا میباشد.در هر لحظه t عامل حالت st را تشخیص داده و عمل at را انجام میدهد. محیط در پاسخ به این عمل پاداش rt=(st,at) را به عامل میدهد و به حالت بعدی st+1=d(st,at) میرود.توابع r , d جزئی از محیط بوده و برای عامل ناشناخته هستند.در MDP توابع فقط به حالت و عمل فعلی بستگی داشته و از حالت وعمل های قبلی مستقل است.

اسلاید 30: 30Recycling Robot An Example Finite MDPAt 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

اسلاید 31: 31Recycling Robot MDPaction node

اسلاید 32: 32Dynamic Programmingدر واقع DP روشی برای حل مسایل MDP است.این روش نیازمند دانستن دینامیک کامل سیستم است. (P and R)پیاده سازی آن پرهزینه و معمولا غیر عملی استبا مشکل نفرین ابعادی روبروستتضمین شده که همگرا خواهد شد.میتوان RL را یک تقریب برخط برای DP دانست.نیازی به دانستن R,P ندارددر فضای حالت به نمونه برداری میپردازد.تئوریهائی در مورد همگرائی آن وجود دارد.

اسلاید 33: StartS2S3S4S5GoalS7S8Arrows indicate strength between two problem statesStart maze …Reinforcement learning example

اسلاید 34: StartS2S3S4S5GoalS7S8The first response leads to S2 …The next state is chosen by randomly sampling from the possible next states weighted by their associative strengthAssociative strength = line width

اسلاید 35: StartS2S3S4S5GoalS7S8Suppose the randomly sampled response leads to S3 …

اسلاید 36: StartS2S3S4S5GoalS7S8At S3, choices lead to either S2, S4, or S7.S7 was picked (randomly)

اسلاید 37: StartS2S3S4S5GoalS7S8By chance, S3 was picked next…

اسلاید 38: StartS2S3S4S5GoalS7S8Next response is S4

اسلاید 39: StartS2S3S4S5GoalS7S8And S5 was chosen next (randomly)

اسلاید 40: StartS2S3S4S5GoalS7S8And the goal is reached …

اسلاید 41: StartS2S3S4S5GoalS7S8Goal is reached,strengthen the associative connection between goal state and last responseNext time S5 is reached, part of the associative strength is passed back to S4...

اسلاید 42: StartS2S3S4S5GoalS7S8Start maze again…

اسلاید 43: StartS2S3S4S5GoalS7S8Let’s suppose after a couple of moves, we end up at S5 again

اسلاید 44: StartS2S3S4S5GoalS7S8S5 is likely to lead to GOAL through strenghtened routeIn reinforcement learning, strength is also passed back to the last stateThis paves the way for the next time going through maze

اسلاید 45: StartS2S3S4S5GoalS7S8The situation after lots of restarts …

اسلاید 46: 46یادگیری خط مشیاگر چه هدف نهائی یادگیری تقویتی یادگیری تابعی بصورت p*:SA است با این وجود در عمل انجام آن بسیار مشکل است زیرا مثالها بصورت <s,a> عرضه نمیشوند.برای یادگیری خط مشی از دو تکنیک زیر استفاده خواهیم کرد:Value FunctionQ Value

اسلاید 47: 47Value Functionمقدار یک حالت عبارت است ازمجموع مقدار پاداشی که با شروع از آن حالت و پیروی از خط مشی مشخصی که به حالت نهائی ختم شود، دریافت میگردد.تابع مقدار یا Value Function عبارت است از نگاشتی ازstates به state values که میتواند توسط هر تقریب زننده تابع نظیر یک شبکه عصبی تخمین زده شود.

اسلاید 48: 48مثالیک مسئله MDP با 16 حالتعامل دارای 4 عمل مختلف است: حرکت به چپ، به راست، به بالاو به پائینپاداش برای تمامی حرکتها برابر -1 است.هدف رسیدن به دو گوشه سمت راست پائین و یا گوشه سمت چپ بالاستمقادیر نشان داده شده مقدار مورد انتظار برای هر حالت در صورت انجام یک حرکت تصادفی برای رسیدن به هدف است.

اسلاید 49: 49The optimal value functionدر شکل مقابل مقادیر بهینه حالتها نشان داده شده است.در صورتی که امکان بدست آوردن این مقادیر وجود داشته باشد میتوان با انجام یک جستجو به optimal policy نیز دست یافت.در یادگیری تقویتی بجای یافتن خط مشی بهینه که مدل کردن آن میتواند مشکل باشد، میتوان تلاش نمود تا مقدار تابع بهینه حالتها را بدست آورد. The optimal value functionThe optimal policy

اسلاید 50: مثال Value Iteration

اسلاید 51: 51Approximating the Value Functionیادگیری تقویتی میتواند کار بسیار سختی باشد زیرا عامل در مقابل کاری که انجام میدهد پاسخ مستقیمی در مورد درست یا نادرستی آن دریافت نمیکند.برای مثال عاملی که میخواهد از طریق شبیه سازی یک هواپیما را هدایت نماید در هر لحظه مجبور است تا تصمیم جدید بگیرد و اگر بعد از هزاران عمل هواپیما سقوط نماید، عامل چگونه میتواند عملی که به سقوط هواپیما منجر شده را شناسائی نماید؟در اینجا Dynamic Programming با معرفی دو اصل ساده سعی در ارائه راه حل مینماید:اگر عملی انجام شود که بلافاصله منجر به نتیجه بدی نظیر سقوط هواپیما گردد عامل باید یاد بگیرد که در دفعات بعدی در حالت مشابه آن عمل را تکرار نکند. لذا عامل باید از عملی که بلافاصله قبل از سقوط هواپیما انجام داده بود پرهیز کند.اگر عملی در یک موقعیت خاص منجر به نتیجه بدی شد، باید از قرار گرفتن در آن موقعیت پرهیز نمود.بنا بر این اگر قرار گرفتن در جهت و موقعیت خاصی منجر به سقوط هواپیما میشود، عامل یاد میگیرد که از انجام عملیاتی که منجر به قرار گرفتن هواپیما در چنین شرائطی میگردند پرهیر نماید.

اسلاید 52: 52The Essence of Dynamic Programmingهدف ازبکار گیری Dynamic Programming در یادگیری تقویتی محاسبه تابع مقدار است. روش کلی انجام اینکار بصورت زیر است:V*(St)= Optimal value functionV (St)= approximate of optimal value functiong=discount factorدر حالت کلی V (St) با مقداری تصادفی عدد دهی میشود که با مقدار بهینه فرق دارد. در نتیجه خطائی در تقریب بروز کرده ورابطه زیررا خواهیم داشت.V (St)= V *(St)+ e(St) این رابطه برای حالت بعدی نیز صادق خواهد بودV (St+1)= V *(St+1)+ e(St+1)

اسلاید 53: 53Bellman equationبا توجه به تعریف تابع مقدار بهینه، رابطه بین مقادیر value functionدر حالتهای مختلف را میتوان توسط Bellman equationبیان کرد:با بسط این معادله به مقدار تابع تقریب زده شده خواهیم داشت:

اسلاید 54: 54Bellman equationاهمیت رابطه فوق در اینجاست که اگر خطا در مرحله نهائی یعنی وقتی که به هدف میرسیم صفر باشد، در صورت انتخاب خط مشی بهینه خطا در مراحلی که منجر به مرحله آخر میگردد نیز تابعی از آن بوده وصفر خواهد شد.

اسلاید 55: 55تقریب تابع Value Functionاگربتوان مقادیر تقریبی V* را توسط یک جدول نشان داد، در اینصورت میتوان برای بدست آوردن آن این جدول را جاروب نموده و بطور مدام مقدار حالتها را طبق رابطه زیر تغییر داد. اینکار تا زمانی که تغییری در جدول رخ ندهد تکرار میشود.برای انجام چنین عملی مدل دینامیکی سیستم لازم خواهد بود.

اسلاید 56: 56بدست آوردن سیاست بهینهبا یادگیری مقادیر میتوان از آن برای جستجوی بهترین عمل استفاده نمود.لازمه اینکار دانستن تابع  و مقدار r است. که در حالت کلی برای عامل ناشناخته هستندو انتخاب عمل را مشکل میسازند. لذا باید از تکنیک های دیگری استفاده نمود.

اسلاید 57: 57Residual Gradient Algorithmsدیدیم که چگونه میتوان تقریب تابع را از طریق جدول انجام داد.استفاده از جدول محدودیتهائی را از لحاظ اندازه و پیچیدگی مسائل قابل حل بوجود میاورد.زیرا بسیاری از مسایل عملی دارای فضای حالت بسیار بزرگ و یا پیوسته هستند که نمیتوان مقادیر آنها را با جدول نشان داددر چنین مواقعی میتوان از تخمین زننده ای استفاده نمود که قابلیت تعمیم داشته و قادر به درونیابی حالتهائی باشد که مشاهده نشده اند.برای مثال شبکه عصبی میتواند برای تخمین مقدار V *(St) بکار رود.

اسلاید 58: 58استفاده از شبکه عصبی یرای تخمین تابع مقداراگر تقریب V *(St) را با V (St,Wt) نشان دهیم که در آن Wt بردار پارامترها باشد در اینصورت برای تغییر این پارامترها میتوان از رابطه زیر استفاده نمود.از آنجائیکه خروجی مطلوب نیز تابعی از Wt است با تغییر بردار پارامترها خروجی نیز تابعی از این مقدار جدید شده و این احتمال وجود خواهد داشت که مقدار Bellman residual کاهش نیابد.نرخ یادگیریخروجی مطلوبخروجی شبکه عصبیمقدار گرادیان

اسلاید 59: 59Residual Gradient Algorithmsیک راه حل این مسئله استفاده از تکنیک residual gradient algorithm است که در اینصورت برای تغییر پارامترهای شبکه از رابطه زیر استفاده میشود:در این الگوریتم gradient descent بر روی mean squared Bellman residualانجام میشود.

اسلاید 60: 60Q-learning Q-learning حالت گسترش یافته الگوریتم Value Iteration است که برای مسایل nondeterministic نیز بکار میرود.یادگیری Q-learning نوعی از یادگیری تقویتی بدون مدل است که بر پایه برنامه ریزی پویای اتفاقی عمل میکند.[Watkins,1989]

اسلاید 61: 61Q-learningدر یادگیری Q –Learning بجای انجام یک نگاشت از States به مقادیر حالتها، نگاشتی از زوج state/action به مقادیری که Q-value نامیده میشوند انجام میگردد.Q-Functionبه هرزوج > حالت ، عمل< یک مقدار Q(s,a) نسبت داده میشود. این مقدار عبارت است از مجموع پاداشهای دریافت شده وقتی که از حالت S شروع و عمل a را انجام وبدنبال آن خط مشی موجود را دنبال کرده باشیم.تفاوت این روش با قبلی در اینجاست که نیازی به انجام تمامی اعمال ممکن یک حالت نیست.

اسلاید 62: 62الگوریتم یادگیری Q برای یادگیری تابع Q میتوان از جدولی استفاده کرد که هر ورودی آن یک زوج <s,a> به همراه تقریبی است که یادگیر از مقدار واقعی Q بدست آورده است.مقادیر این جدول با مقدار اولیه تصادفی ) معمولا صفر( پر میشودعامل بطور متناوب وضعیت فعلی S را تشخیص داده و عملی مثل a را انجام میدهد. سپس پاداش حاصله r(s,a) و همچنین حالت جدید ناشی از انجام عملs’=d(s,a) را مشاهده میکند.مقادیر جدول با استفاده از رابطه زیر تغییر میکنند:

اسلاید 63: 63الگوریتم یادگیری Q برای MDP قطعیFor each s,a initialize the table entry to zeroObserve the current state sDo forever:Select an action a and execute itreceive immediate reward rObserve the new state s’update the table entry for as followsss’

اسلاید 64: 64مثالدر این مثالمقادیر Q هرعمل/حالت در کنار آن درج شده است با هر حرکت عامل به سمت راست پاداش صفر به آن تعلق میگیرد.اگر عامل از حالت sl شروع کرده و به سمت راست حرکت کند مقدار جدید Q برابر است با: 100738166sl100908166

اسلاید 65: 65مثال

اسلاید 66: 66اپیزود های یادگیریاز آنجائیکه در محیط یک حالت هدف جذب کننده absorbing state در نظر گرفته میشود که با قرار گرفتن عامل درآن حرکت عامل متوقف میشود، عمل یادگیری بصورت اپیزودی انجام میشود.در هر اپیزود عامل در یک محل تصادفی قرار داده میشود و تا رسیدن به حالت جذبی به تغییر مقادیر Q ادامه میدهد.اگر مقادیر اولیه Q صفر در نظر گرفته شده باشند، در هر اپیزود فقط یکی از مقادیر که به مقدار نهائی نزدیکتر هستند تغییر کرده و بقیه صفر باقی میمانند.با افزایش تکرار اپیزود ها این مقادیر غیر صفر به سایر مقادیر جدول گسترش پیدا کرده و درنهایت به مقادیر بهینه همگرا خواهند شد.

اسلاید 67: 67اثبات همگرائیفرض های لازم:محیط deterministic MDP است.پاداش های فوری محدود هستند|r(s,a)|<c : عامل تمامی حالت/عمل های موجود را بینهایت بار امتحان میکندایده اصلی:اثبات میشود که ورودی با بیشترین مقدار خطا در جدول Qبا هربار بازدید به نسبت g از خطای آن کاسته میشود.

اسلاید 68: 68اثبات همگرائیبا توجه به اینکه تمامی عمل/حالتها بینهایت بار تکرار خواهند شد، اگر فاصله ای را در نظر بگیریم که هرکدام حداقل یکبار تکرار شده باشند، در اینصورت خطا در مرحله n ام تغییر مقدار جدول برابر است با:مقدار خطا در مرحله n+1 ام تغییر برابر خواهد بود با:

اسلاید 69: 69نحوه انجام آزمایشبرای اینکه شرط همگرائی برقرار باشد باید هر عمل/حالت بینهایت بار تکرار شود. در یادگیری Q معمولابرای انتخاب عمل ها از یک رابطه احتمالاتی استفاده میشود که در آن عمل های با مقادیرQ بالا با احتمال بیشتری انتخاب میشوند.K>0ثابتی است که میزان ارجحیت عمل های با مقدار بزرگ Q را مشخص میکند.مقادیر بزرگk منجر به استفاده از دانش آموخته شده میگرددexploit مقادیر کوچک k به بقیه عمل ها شانس بیشتری میدهد. explore احتمال انتخاب عمل ai وقتی عامل در حالت s است

اسلاید 70: 70یادگیری Q برای MDP غیرقطعیدر یک سیستم deterministic MDP انجام یک عمل مشخص در حالت St همواره به حالت بعدی یکسان St+1 منجر میشود.در حالیکه در یک non-deterministic MDP از یک تابع توزیع احتمال برای تعیین حالت بعدی ناشی از انجام یک عمل استفاده میشود.در چنین حالتی توابع d(s,a) و r(s,a) دارای توزیع احتمال بوده و بر اساس آن خروجی تصادفی خواهند داشت.

اسلاید 71: 71یادگیری Q برای MDP غیرقطعیبرای حالت غیر قطعی تابع Q بصورت زیر بازنویسی میشود.در چنین حالتی نیاز به قانون جدیدی برای یادگیری خواهد بود زیرا قانون قبلی در صورت تصادفی بودن مقادیر r ,s’ قادر به همگرائی نخواهد بود.

اسلاید 72: 72یادگیری Q برای MDP غیرقطعیبرای رسیدن به همگرائی از قانون زیر استفاده میشودکه در آندر این رابطه visitsn(s,a) برابر است با مجموع دفعاتی که زوج (s,a ) مورد استفاده قرار گرفته اند.

اسلاید 73: 73Temporal difference learningیادگیری Q حالت خاصی از الگوریتم یادگیری Temporal difference learning است.در یادگیری Q از اختلاف بین مقدار حالت فعلی و حالت بعد از آن استفاده میشد. این امر را میتوان به اختلاف بین حالت فعلی و چند حالت بعدی تعمیم داد.اگر الگوریتم یادگیری Q را بصورت زیر نشان دهیم:حالت تعمیم یافته آنرا میتوان بصورت زیر نشان داد:

اسلاید 74: 74الگوریتم TD(l)در این الگوریتم سعی میشود تا با معرفی ثابت0=< l<=1 تخمین حاصله از فواصل مختلف را با هم ترکیب نموداین الگوریتم را میتوان بصورت بازگشتی زیر نوشتبرای حالت l=0 این الگوریتم برابربا الگوریتم یادگیری Q خواهد بود.

اسلاید 75: 75الگوریتم TD(l)در برخی از مسائل استفاده از این روش میتواند سرعت یادگیری را افزایش دهد.

اسلاید 76: 76ترکیب شبکه عصبی با یادگیری Q در مواقعی که امکان ذخیره مقادیر Qدر جدول وجود نداشته باشد، میتوان یک تابع تقریب زننده نظیر شبکه عصبی را جایگزین این جدول نمود.برای مثال میتوان مقادیر s,a را بعنوان ورودیهای شبکه عصبی درنظرگرفته و شبکه را طوری آموزش داد که مقادیرتقریبی Q را در خروجی ایجاد نماید.دربرخی کاربردها استفاده از یک شبکه عصبی جداگانه برای هر یک از عمل ها مفید بوده است.باید توجه نمود که در صورت استفاده از شبکه عصبی احتمال عدم همگرائی وجود خواهد داشت.زیرا تغییر در مقادیر وزنهای شبکه در هنگام یادگیری میتواند منجر به افزایش خطا در مقادیر Q گردد.

اسلاید 77: 77مسایل مطرح در یادگیری تقویتییادگیری تقویتی با دو چالش عمده روبروست:چگونگی توسعه به مسایل بزرگترامکان استفاده در مسایل partially-observable Markov decision که در آنها عامل قادر به درک کامل محیط نیست

اسلاید 78: 78سیستمهای بزرگوقتی که سیستم خیلی بزرگ میشود، یادگیری Q قادر به نمونه برداری از تمامی زوجهای عمل/حالت نخواهد بود.در چنین حالتی از دسته بندی کننده ها و ترکیب آنها با الگوریتمهای ژنتیک استفاده میشوداستفاده از شبکه عصبی برای تقریب تابع در چنین حالتی عملی نبوده و معمولا از روشهای رگراسیون دیگری استفاده میشود.

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