یادگیری تقویتی در سیستم های چند عاملی بر اساس رویکردهای نظریه بازی

مسئلهراننده‌ای را در نظر بگیرید، این راننده می خواهد از یک چهارراه شلوغ عبور کند. راننده چراغ راهنمایی، خط‌کشی‌های خیابان و سنگ‌های جدول را می بینید و بر اساس آن‌ها تصمیم می‌گیرد که کدام پدال ماشین را بیشتر فشار دهد، با کدام دنده به حرکت خود ادامه دهد و فرمان را به کدام سمت بچرخاند. لذا، می توان فرض کرد برای رسیدن به هدف عبور ایمن از چهارراه، راننده براساس داده‌های دریافتی خود از محیط، سلسله ای از اعمال را در گام های زمانی گسسته انجام می دهد.یادگیری تقویتیدر این مثال، راننده عامل (agent) و گاز دادن، پیچیدن و ترمز گرفتن عمل‌های عامل (Action) هستند و شرایط محیطی که راننده با حواس خود درک کرده را حالت (State/Observation) می گوییم. برای اینکه معیاری برای مقایسه نتایج تصمیم‌گیری داشته باشیم، پاداش (ًReward) تعریف می کنیم، مثلا تصادف کردن راننده پاداش 10000-، نزدیک شدن به ماشین روبرو پاداش 5000- و فشردن زیاد گاز و ترمز درگام‌های متوالی پاداش 100- تعریف می‌کنیم. سیاست (Policy) تعیین می کند که در یک حالت خاص با چه احتمالی هر استراتژی انجام شود. در دیاگرام زیر فرآیند استاندارد یادگیری تقویتی (Reinforcment Learning) را نشان می دهد. یادگیری تقویتی، یادگیری یک عامل از طریق تعاملات تکراری آزمون و خطا با محیط ناشناخته است.یادگیری تقویتی چند عامله لحظه‌ای را در نظر بگیرد که چهارراه خالی است، راننده با گاز دادن می تواند، سریع تر عبور کند و سود خود را افزایش دهد اما در چهارراه رانندگان و عابرهای پیاده نیز حضور دارند که همزمان با راننده در حال تصیمیم‌گیری هستند. پس، در تصمیم در هر گام، باید راننده علاوه بر نتیجه فوری، باید اثر این تصمیم در گام‌های آینده نیز در نظر بگیرد. همچنین تصمیمات دیگر عامل‌های حاضر در محیط بر تصمیمات راننده اثر گذار است.یادگیری تقویتی چند عامله(MARL)، مسئله‌ی تصمیم‌گیری متوالی برای چندین عامل در تعامل باهم، در یک مشترک محیط تصادفی را بررسی می کند. پیچیدگی‌های تئوری زیر به عنوان مسائل اصلی MARL شناخته می شوند:پیچیدگی ترکیبی: برای در نظر گرفتن تاثیرات دیگر عامل ها، در MARL عمل‌ها به صورت عمل‌های توام هستند، با افزایش تعداد عامل‌ها، بعد این عمل‌های توام به صورت نمایی رشد می کند و در نتیجه استفاده از روش‌های MARL را در مقایس بزرگ محدود می‌شود. برخلاف یادگیری تقویتی تک عامله که هدف بیشینه کردن پاداش طولانی مدت عامل است، هدف در MARL ذاتا چند بعدی است و لزوما نمی توان با سنجه‌ای یکسان همه عامل ها را سنجید. همچنین بیشینه شدن سود یک عامل منجر به بیشینه سود کل در بازی نمی شود. تحلیل با رویکرد نظریه بازیاگر عامل‌ها را بازیکنان یک بازی در نظر بگیریم، می‌توان مسئله یادگیری تقویتی چند عامله را با یک بازی با اطلاعات ناتام و تکرار شونده در فرم نرمال توصیف کرد که با تکرار بازی، بازیکنان سعی می کنند استراتژی خود را بهبود دهند. برای اینکه این مدل سازی دقت کافی را داشته باشد، فرض های زیر ضروری هستند:تمام تغییرات در سود عامل‌ها و حالات محیط تنها حاصل از تغییر استراتژی بازیکن ها است، یعنی هیچ چیز خارجی در تغییر حالت‌های محیط و سود بازیکن‌ها دخیل نیست. در آغاز این بازی، بازیکنان از تابع سود یکدیگر اطلاعی ندارند ولی در طول بازی، آگاه هستند که در این گام حریف‌ها چه عملی انتخاب کرده و چه سودی بدست آورده اند.تابع سود بازیکنان تصادفی است، یعنی یک پروفایل استراتژی خاص برای یک بازیکن خاص همواره منجر به سود ثابتی نخواهد شد.هدف یادگیریقرار دادن موازنه نش به عنوان هدف بازی در این بازی‌ها دو مشکل دارد:در حالت کلی ماتریس سود بازیکن‌ها یکسان نبوده و موازنه نش یکتا نیست، لذا نیاز است تا بازیکن‌ها بر یک موازنه نش توافق کنند.موازنه نش نقطه بهینه اجتماعی نیست و لزوما در موازنه نش سود کلی بیشینه نمی شود.لذا در مسئله یادگیری تقویتی چند عامله با شرایط بیان شده، موازنه نش نمی تواند هدف یادگیری باشد و بهتر است مفاهیمی مثل موازنه تکاملی پایدار (ESS)، موازنه همبسته (CE) و افسوس (regret) به عنوان هدف یادگیری تعیین شوند. روش Q-learningروش Q-learning ، یک روش شناخته شده در یادگیری تقویتی تک عامله است که به هر عامل یک مقدار Q نسبت می دهد. رابطه کلی Q-learning به صورت زیر است:که در این رابطه، a پروفایل استراتژی بازیکن ها و s حالت و r تابع از پاداش های دریافت شده از ابتدای بازی هستند. با توجه به فرض عدم دخالت عوامل خارج از بازی در حالت‌های محیط در بازی مدل شده در قسمت تحلیل با رویکرد نظریه بازی، به رابطه زیر ساده می شود:ثابت شده است تحت برخی شرایط رابطه فوق به یک تعادل بهینه همگرا می شود.خلاصهدر این پست به مسئله راننده در یک چهارراه شلوغ پرداخته شد و نحوه استفاده از یادگیری تقویتی برای تصمیم‌گیری راننده مورد بررسی قرار گرفت. سپس به بررسی یادگیری تقویتی چند عامله پرداخته شد که در آن محیطی را بررسی می‌کند که چندین عامل در آن با یکدیگر در تعامل هستند. پیچیدگی‌های نظری این رویکرد بررسی شده و نکاتی مانند پیچیدگی ترکیبی و هدف‌های چند بعدی در مسئله یادگیری تقویتی چند عامله مطرح شدند. در نهایت، به تحلیل این مسئله با رویکرد نظریه بازی پرداخته شد و هدف یادگیری و نحوه ترکیب یادگیری تقویتی و نظریه بازی در حل مسئله شرح داده شد.منابعNowe, Ann & Vrancx, Peter & De Hauwere, Yann-Michaël. (2012). Game Theory and Multi-agent Reinforcement Learning. 10.1007/978-3-642-27645-3_14. Yang, Yaodong & Wang, Jun. (2020). An Overview of Multi-Agent Reinforcement Learning from Game Theoretical Perspective. https://www.coursera.org/learn/fundamentals-of-reinforcement-learning