یادگیری تقویتی 1 روشی است که در آن عامل2 با در نظر گرفتن حالت 3محیط، از بین همه اعمال4 ممکن یکی را انتخاب می کند و محیط 5در ازای انجام آن عمل، یک سیگنال عددی به نام پاداش6 به عامل باز می گرداند.
هدف عامل این است که از طریق سعی و خطا سیاستی7 را بیابد که با دنبال کردن آن به بیشترین پاداش ممکن برسد.
در این پروژه سعی داریم به یک عامل یاد بدهیم چگونه مواد مورد نیاز برای درست کردن یک کیک را با استفاده از یادگیری تقویتی جمع آوری کند.
محیط به صورت یک ماز 8است که یک هیولا در آن وجود دارد و در یک سری از خانه ها چاله وجود دارد که مانع عامل ما هستند.
عامل باید سه ماده آرد، شکر و تخم مرغ را در کوتاهترین زمان جمع آوری کند بدون آنکه هیولا او را بگیرد.

تصویر محیط

۱. مقدمه

یادگیری تقویتی دیدگاه نوینی در یادگیری ماشین است که در آن به جای افزودن اطلاعات هنگام پیاده سازی از محیط عامل خود با تجربه کردن محیط کشف میکند که چه عملی در چه حالتی بیشترین پاداش را دارا می باشد مهم ترین شاخصه های یادگیری تقویتی آن است که کاوش بر مبنای آزمون و خطا می باشد و بیشینه پاداش در انتهای فرآیند در اختیار عامل قرار دارد [2]

شماتیک یادگیری تقویتی

معمولا برای یادگیری تقویتی محیط را مارکوف تصور می کنیم این خاصیت برای محیط به ازای هر حالت s و پاداش r در زمان t+1 به صورت زیر تعریف می شود

تعریف خاصیت مارکوف

بر اساس این تعریف هر پاداش به ازای هر حالت در محیط محدود به وضعیت عامل در تنها یک حالت قبل یعنی t می باشد و وضعیت سایر حالات از 0 تا t-1 اگر ما در t+1 باشیم در نظر گرفته نمی شود
تغییر وضعیت از s به 's با انجام عمل a

دریافت پاداش از s به 's با انجام عمل a

در مسایلی که با یادگیری تقویتی سروکار داریم هدف این است که عامل به بیشینه پاداش دست یابد
بیشینه پاداش

برای حل مسئله درست کردن کیک باید عامل بتواند چاله و مواد اولیه کیک را تشخیص بدهد در ازای دریافت مواد اولیه پاداش مثبت دریافت کند و در ازای ورود به چاله پاداش منفی دریافت کند (هزینه بپردازد) در هر حرکت باید تشخیص بدهد که در چهار طرفش هیولا وجود نداشته باشد با حفظ کلیت مسئله فرض میکنیم هیولا در خانه ی تصادفی ثابت است و از زمان 0 تا t در همان خانه می ماند

بر این اساس ما از دو الگوریتم سارسا و یادگیری کیو استفاده می کنیم

Q learning

sarsa

۲. پیاده سازی و بهبود نتایج آزمایش‌ها

یاد گیری Q
ابتدا با یک آزمایش ساده شروع میکنیم و یادگیری Q 9را برای این آزمایش پیاده ساری می کنیم در محیط داده شده عامل (مربع خاکستری) باید به دنبال هدف که به صورت مربع زرد مشخص شده برود و هیولا که توسط مربع قرمز متمایز شده هم به دنبال عامل حرکت می کند

پیاده سازی ساده شده از مساله یادگیری تقویتی

هر سلول نقشه در صورتی که مسدود نباشد دارای آرایه ای است که مقدار action value را نگه داری میکند آرایه action value
دارای حداکثر 8 مقدار است که به جهت های شمال,جنوب ,شرق,غرب ,شمال شرقی ,شمال غربی و جنوب شرقی و جنوب غربی اشاره می کند
حرکت عامل به این صورت است که در ابتدا به خانه های آرایه action value نگاه می کند اگر خالی بود یک جهت را تصادفی انتخاب می کند تا زمانی که به هدف نرسیده این کار را تکرار می کند زمانی که به هدف رسید به ازای آن حرکتی که عامل را به هدف رساند در خانه ی جهت حرکت مربوطه در آرایه ی action value مقدار 50+ را می افزاید یعنی عناصر واقع در آرایه action value برای محاسبه مقدار Q برای هر حرکت عامل استفاده میشوند با تکرار این آزمایش در اپیزود های مختلف مقدار action value ی هر خانه کامل شده و عامل با محابسه ی مقدار Q می تواند حرکت بعدی خود را غیر تصادفی و با توجه به پاداش هر حرکت انتخاب نماید
نمونه ای از حرکت عامل و دریافت پاداش

به طور مشخص مقدار Q از رابطه ی
Q(s, a) =Q(s, a)+ alpha * (reward(s,a) + max(Q(s') - Q(s,a))

محاسبه می شود دراین رابطه sو a حال و عمل قبلی هستند که برای آن ها طبق آنچه در بالا آمد پاداش محاسبه می شود سپس در ضریب یادگیری alpha که معمولا 0.5 انتخاب می شود ضرب مشود و با مقدار Q حالت s’ یعنی حالت جاری جمع می گردد
راه حل عادی برای انتخاب بین عمل های مختلف بین عمل های موجود در یک حالت جاری از الگوریتم زیر پیروی میکند:

def select_action(state):
    q =[getQ(state, a) for a in actions]
    maxQ=max(q)
    action=actions[maxQ]
    return action

چالشی که وجود دارد این است که با توجه به این که عامل در طول زمان یادگیری خود را صورت می دهد و در ابتدا هیچ اطلاعاتی ندارد مقدار Q همان طور که از فرمول هم معلوم است وابسته به حالت قبل می باشد انتخاب های تصادفی انجام میدهد اما تا چه زمانی عامل باید انتخاب هایش را تصادفا انجام دهد برای حل چالش می توانیم یک مقداری را تحت نام epsilon تعریف کنیم تا بر روی انتخاب های تصادفی کنترل داشته باشیم یعنی اگر مقدار تصادفی کمتر از epsilon بود مقدار تصادفی را به جای تاکتیک معمول انتخاب مقدار max Q انتخاب می کنیم الگوریتم پیاده سازی این روش به صورت زیر میباشد :

def select_action(state):
    if random.randome() < epsilon:
        best = [i for i in range(len(actions))]
        i = random.choice(best)
    else:
        i = q.index(maxQ)
        action = actions[i]
    return action

اما در این صورت مشکل حل نشده دیگری بروز خواهد کرد و آن این است که عامل تا کی باید مقدار تصادفی تولید کند در حالی که تقریبا به ازای تمام عمل ها بر روی خانه های ماز مقدار Q در جدول خود دارد در این صورت وظیفه طراح است که عامل را طوری سامان دهی کند تا هر چه اپیزود های پیشتری سپری می شود از مقدار epsilon کم شود تا محدوده انتخاب های تصادفی کاهش بیابد در این صورت عامل به مرور زمان انتخاب هایش هوشمندانه تر می گردد مقادیر زیر مبروط به اجرای برنامه با epsilon ثابت به دست آمده است توجه شود که خورده شدن توسط هیولا دارای پاداش منفی صد است(جریمه10) و همان طور که مشاهده می شود در اپیزود های11 پایانی مقادی به دست آمده تقریبا به 300 همگرا 12 می باشند

10000, e: 0.10, W: 23, L: 650
20000, e: 0.10, W: 22, L: 604 
30000, e: 0.10, W: 29, L: 499 
40000, e: 0.10, W: 17, L: 508 
50000, e: 0.10, W: 33, L: 564 
60000, e: 0.10, W: 28, L: 495
70000, e: 0.10, W: 18, L: 454 
80000, e: 0.10, W: 32, L: 443
90000, e: 0.10, W: 30, L: 411
100000, e: 0.10, W: 19, L: 390 
110000, e: 0.10, W: 25, L: 388 
120000, e: 0.10, W: 21, L: 394 
130000, e: 0.10, W: 16, L: 424 
140000, e: 0.10, W: 25, L: 356 
150000, e: 0.10, W: 23, L: 333 

حال نتایج به دست آمده را می توان با نتایج پیاده سازی زمانی که epsilon ثابت نیست مقایسه کرد همان طور که مشاهده می شود epsilon در حال کاهش است و زیرا عامل در طول اجرای اپیزود ها می آموزد که کدام عمل پاداش بیشتری دارد و کدام عمل دارای جریمه است بنابر این با نزدیک شدن به انتخاب معقول 13 انتخاب های تصادفی کاهش پیدا میکنند تا نتایج به دست آمده از آزمایشات ما دقیق تر باشند

10000, e: 0.09, W: 44, L: 778
20000, e: 0.08, W: 39, L: 617
30000, e: 0.07, W: 47, L: 437
40000, e: 0.06, W: 33, L: 376
50000, e: 0.05, W: 35, L: 316
60000, e: 0.04, W: 36, L: 285
70000, e: 0.03, W: 33, L: 255
80000, e: 0.02, W: 31, L: 179
90000, e: 0.01, W: 35, L: 152
100000, e: 0.00, W: 44, L: 130
110000, e: 0.00, W: 28, L: 90
120000, e: 0.00, W: 17, L: 65
130000, e: 0.00, W: 40, L: 117
140000, e: 0.00, W: 56, L: 86
150000, e: 0.00, W: 37, L: 77

همگرایی مقدار باخت 14 یا خورده شدن توسط هیولا با توجه به ارقام بالا نزدیک به 100 است یعنی یک سوم نسبت به حالت قبل بهبود عملکرد مشاهده می شود.
یادگیری SARSA
حالا به پیاده سازی روش SARSA برای مساله می پردازیم
سارسا (SARSA ) مخفف کلمات State Action Reward State Action می باشد یعنی عامل به حالت state 1 با عمل action 1 می رود و پاداش reward 1 را دریافت می کند سپس با action 2 به state 2 می رود و reward 2 را دریافت می کند قبل از اینکه بهstate 1 برود تا reward آن را به روز رسانی نماید در واقع در یادگیری کیو ابتدا با action 1 به state 1 میرویم سپس به دنبال بیشینه ی پاداش ممکن برای عمل در state 2 می گردد بعد از آن performance عمل action1 در state 1 را محاسبه می کند اما در روش سارسا برای رفتن از state 1 به state 2 عمل واقعی مربوط را انتخاب می کند یعنی سیاست الگوریتم سارسا این است که مقدار Q بعدی را با توجه به action بعدی محاسبه میکند به جای اینکه مقدار Q بیشنه مورد توجه قرار دهد
روش محاسبه ی مقدار Q در الگوریتم سارسا به صورت زیر می باشد

Q(s, a) = reward(s) + alpha * Q(s', a')

همان طور که در فرمول هم آمده برای محاسبه ی مقدار (Q(s,a مقدار ('Q(s',a مورد نیاز می باشد که در الگوریتم زیر این مقدار مورد محاسبه قرار گرفته است

def learn(self, state1, action1, reward, state2, action2):
    nextQ =getQ(state2, action2)
    learnQ(state1, action1, reward, reward + gamma * nextQ)
---------------------------------------------------------------------------------
def learnQ(state1, action1, reward, value):
    old_move = Q.get((state, action), None)
    if old_move is null:
        Q[(state, action)] = reward 
    else:
        Q[(state, action)] = old_move + alpha * (value - old_move)

مقادیر ثابت استفاده شده به صورت زیر می باشد

alpha=0.2
gamma=0.9

نتایج به دست آمده از پیاده سازی الگوریتم سارسا به صورت زیر قابل مشاهده است;

10000, e: 0.10, W: 20, L: 672 
20000, e: 0.10, W: 26, L: 639 
30000, e: 0.10, W: 26, L: 574 
40000, e: 0.10, W: 18, L: 555 
50000, e: 0.10, W: 19, L: 494 
80000, e: 0.10, W: 25, L: 414 
90000, e: 0.10, W: 22, L: 374 
100000, e: 0.10, W: 17, L: 386 
110000, e: 0.10, W: 15, L: 389 
120000, e: 0.10, W: 21, L: 346 
130000, e: 0.10, W: 25, L: 414 
140000, e: 0.10, W: 25, L: 373 
150000, e: 0.10, W: 14, L: 308

همان طور که مشاهده می شود استفاده از الگوریتم سارسا شبیه الگوریتم بهینه نشده ی یادگیری Q می باشد با این تفاوت که به زمان همگرایی بیشتری نیاز دارد زیرا برای جابه جایی بین هر حالت performance به جای انتهای فرآیند شبیه آنچه در یادگیری Q اتفاق می افتد همان لحظه محاسبه می شود.

۳. نتیجه گیری و کار های آینده

نمونه پیاده سازی شده مساله ی درست کردن کیک با استفاده از یادگیری تقویتی (لینک پیاده سازی در انتهای مقاله موجود است )عامل با رنگ خاکستری و هیولا با رنگ قرمز در تصویر دیده میشود مربع های رنگی دیگر هر کدام مواد درست کردن کیک هستند که عامل موظف به جمع آوری آن ها می باشد!

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

با توجه به سه آزمایش که انجام گرفت متوجه شدیم که برای حل این مساله ی خاص بهتر است از روش یادگیری Q استفاده کنیم زیرا زمان همگریایی کمتری دارد
چارت زیر تعداد موفقیت های به دست آمده در بازه های زمانی اپیزود ها که به صورت 100000 تایی هستند را نمایش می دهد

مقادی عمودی موفقیت و مقادیر افقی اپیزود های آزمایش هستند

هم چنین باید توجه شود که طراح بهبود مورد نظر را در ساختار یادگیری عامل اعمال نماید تا میزان یادگیری عامل افزایش یابد البته با توجه به وقت کمی که بنده داشتم برای دنیایی که پیاده سازی کردم چاله را در نظر نگرفتم که می توان در آینده به پیاده سازی اضافه شود همچنین می توان چالش جدید به مساله اضافه کرد و آن اینکه عامل پس از جمع آوری مواد اولیه کیک به خانه ی خاص یا همان خانه ی اول باز گردد یک راه حل سریع برای این چالش این است که عامل راه رسیدن به اهدافش را در حافظه ذخیره نماید تا بعد از جمع آوری اهداف بتواند با محاسبه ی پاداش هر عمل در هر حالت به خانه ی اولیه در سریع ترین زمان ممکن برگردد (استراتژی هانسل و گرتل) همچنین در پیاده سازی صورت گرفته به پیشرفت دانش عامل برای انتخاب های معقولانه تر توجه شد در حالی که هیولا هم می تواند در گذر زمان انتخاب های معقولانه تری انجام دهد بنابر این چالش مساله مواجه شدن عامل با یک موجود هوشمند است.

لینک پیاده سازی( برای اجرا باید test_rl_ai.py را اجرا کنید)

۴. مراجع

[1] محمد غضنفری، "بهبود عملکرد عامل شبیه‌سازی فوتبال دوبعدی با استفاده از یادگیری تقویتی "، پایان‌نامه کارشناسی، دانشگاه علم و صنعت ایران، ۱۳۹2. دریافت

[2] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. Cambridge, United States of America: MIT Press, 1998.

پیوندهای مفید


  1. Reinforcement learning

  2. Agent

  3. State

  4. Action

  5. Environment

  6. Reward

  7. Policy

  8. Maze

  9. Q Learning

  10. Penalty

  11. Episode

  12. Convergence

  13. Rational Choice

  14. Lose

رد شده

سلام
پروژتون رو خیلی خوب پیاده‌سازی کردین و پروژه‌ی کاملی هست. کامنت‌گذاری کد به خوبی انجام شده و باعث قابل فهم بودن کد میشه. چند تا نکته رو لازم می‌دونم یادآوری کنم تا در پروژه‌های آینده چنین مشکلاتی وجود نداشته باشه.

  • به قواعد نگارشی توجه زیادی داشته باشید، نیم‌فاصله در موارد زیادی در متن رعایت نشده.

  • برای فرمول‌ها و تصاویر درج شده در مقاله بهتره که شماره‌گذاری کنید.
    موفق باشید.

تایید شده

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

تایید شده

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

تایید شده

سلام
پروژه شما درچند مورد نیاز به بررسی دارد که عبارت اند از:
1- بهتر بود در قسمت مقدمه، به معرفی اولیه پروژه می پرداختید و بررسی خصوصیات محیط مارکوف و الگوریتم های مربوط به آن را در قسمت کارهای مرتبط قرار می دادید. برخی از تعاریف مانند محیط مارکوف نیاز به بررسی دقیق تری داشتند.
2- تعداد مقالات و سایت ها بسیار کم می باشد و ارجاع به مقالات هم نشده است.
3- تصاویر شماره گذاری نشده اند.
4- بهتر بود در مورد پیاده سازی و کد، توضیحاتی شامل زبان پیاده سازی، داده و... در اینجا یا گیت هاب خود قرار می دادید.
5- تعدادی غلط املایی و ویرایشی در متن وجود دارد که باید اصلاح شود.
موفق باشید

تایید شده

با عرض خسته نباشید به خاطر انجام پروژه،نکاتی به نظر میرسد که خدمتتان عرض می‌کنم:
1- در فاز اول، اصلا شرح مساله بیان نشده و صرفا به توضیح و شرح یادگیری تقویتی پرداختید که اصلا برای شرح مساله کافی نیست و به شرح مساله پروژه‌ی خودتان نپرداختید.
2- اصلا در فاز اول به مشکلات و چالش‌های پیش‌رو اشاره ای نکردید و فقط در فاز پیاده‌سازی به مشکلات بوجودآمده در این فاز پرداختید.
3- کارهای مرتبط اصلا مورد بررسی قرار نگرفته است که از نکات منفی بارز پروژه‌ی شماست و بهتر بود از مقالات و کارهای دیگران بیشتر بهره می‌بردید.
4- در قسمت پیاده‌سازی و کد مربوطه،اصلا توضیحی در مورد کد گیت هاب داده نشده است و بهتر بود از readme در گیت هاب استفاده می‌کردید و یا در همین سایت در مورد کد خودتان توضیح می‌دادید.
5- اصلا نتایج بدست آمده گذاشته نشده و در فاز بهبود نتایج نیز، نتایج بدست آمده باز نمایش داده نشده‌است.
6- بهتر بود روش SARSA و یادگیری ‌Q در فاز اول توضیح داده می‌شد و بعد درفاز بعدی، از این روشها در پروژه‌ی خودتان استفاده می‌کردید.
با تشکر

تایید شده

سلام
امیدوارم از انجام این پروژه لذت برده باشید و انجام این نوع پروژه برایتان تجربه خوبی بوده باشد. تشکر می کنم از زحمتی که کشیدید برای انجام پروژه و چند نکته ای که به نظرم می تواند برای کارهایی که در آینده انجام می دهید مفید باشد را ذکر می کنم:

  • یک سری اشکالات نگارشی در متن وجود دارد که چون سایر دوستان در نقدهایشان به آن ها اشاره کرده اند بنده تکرار نمی کنم. همچنین می توانستید متنتان را مرتب تر و خواناتر بنویسید (به کمک تنظیم بهتر پاراگراف ها و جداول و نمودارهای مرتب تر و ...)

  • نموداری که به عنوان نتیجه ارائه داده اید از یک سری نقطه پراکنده تشکیل شده اند که هیچ ترند معناداری در خود ندارند و دیدن آن به خواننده کمکی نمی کند. معمولا برای اینکه این اتفاق نیوفتد باید آزمایشتان را چندین بار تکرار کنید و میانگین اجراها را در لحظه رسم کنید که این کار باعث از بین رفتن تاثیر اتفاقات تصادفی و شانس در کارتان می شود. همچنین می توانید با استفاده از یک sliding window نمودارتان را خیلی نرم تر رسم کنید.

  • شما در کارتان تحلیل خوبی از نتایج نداشته اید. مثلا فقط نوشته اید یادگیری کیو از سارسا بهتر است چون زودتر همگرا می شود! این که دلیل نشد. شما باید بتوانید با بررسی مقالات مختلف دلیل این تفاوت را تحلیل کنید. مثلا بگویید چون این یک محیط کوچک است و یادگیری کیو نسبت به سارسا exploration بیشتری انجام میدهد در این محیط موفق تر عمل کرده است و یا تحلیل هایی از این دست. همچنین انتظار می رفت نتایج کارتان را با کارهای مشابهی که توسط سایرین شده بود مقایسه می کردید. متاسفانه کلا در بررسی کارهای مشابه و مقایسه نتایج بسیار ضعیف عمل کرده اید.

  • کدی که در گیت هاب قرار داده اید نه readme دارد و نه هیچ راهنما و یا کامنت به دردبخوری. همچنین همانطور که در متن تان هم هیچ جا ذکر نکرده اید که این مطلب را از کجا آورده اید و مرجع خاصی (غیر از ۱-۲ مورد بدیهی) ندارید در کدتان هم به ذکر مرجع و اینکه این کد را از کجا آورده اید نپرداخته اید.

  • ما انتظار داشتیم یا کدتان را خودتان پیاده سازی کنید و یا اگر از کدهای موجود در اینترنت استفاده می کنید آن ها بهبود داده و حتما ذکر کنید از کجا آورده اید. کدهای شما تقریبا کپی پروژه ای در گیت هاب است که لینکش را در زیر قرار می دهم:
    https://github.com/studywolf/blog/tree/master/RL/Egocentric

    امیدوارم این مطالب به شما کمک کند تا در آینده پروژه های بهتری انجام دهید.
    موفق باشید