مدلی مبتنی بر آنتروپی و اتوماتاهاي یادگیر برای حل بازیهای تصادفی
محورهای موضوعی : مهندسی برق و کامپیوتربهروز معصومی 1 , محمدرضا میبدی 2
1 - دانشگاه آزاد اسلامی واحد قزوین
2 - دانشگاه صنعتی امیرکبیر
کلید واژه: آنتروپی اتوماتاهاي يادگير بازیهای تصادفی سيستمهاي چندعامله,
چکیده مقاله :
بازیهای غیر قطعی (تصادفی) بهعنوان توسعهای از فرآیندهای تصادفی مارکوف با چندین عامل در سیستمهای چندعامله و مدلسازی آنها حائز اهمیت بوده و بهعنوان چارچوبی مناسب در تحقیقات یادگیری تقویتی چندعامله بهکار رفتهاند. در حال حاضر اتوماتاهای یادگیر بهعنوان ابزاری ارزشمند در طراحی الگوریتمهای یادگیری چندعامله بهکار رفتهاند. در این مقاله مدلی مبتنی بر اتوماتای یادگیر و مفهوم آنتروپی برای حل بازیهای غیر قطعی و پیداکردن سیاست بهینه در این بازیها ارائه شده است. در مدل پیشنهادی بهازای هر عامل در هر حالت از محیط بازی یک اتوماتای یادگیر با ساختار متغیر از نوع S قرار داده شده است که اعمال بهینه را در هر حالت یاد میگیرند. تعداد اعمال هر اتوماتا با توجه به همسایگان مجاور هر حالت تعیین شده و ترکیب اعمال اتوماتاها حالت بعدی محیط را انتخاب میکند. در مدل پیشنهادی از آنتروپی بردار احتمالات اتوماتای یادگیر حالت جدید برای کمک به پاداشدهی اتوماتاها و بهبود یادگیری استفاده شده است. برای بررسی و تحلیل رفتار الگوریتم یادگیری پارامتری بهنام آنتروپی کلی تعریف گردیده که میزان همگرایی را در الگوریتم یادگیری بیان میکند. در نهایت الگوریتمی اصلاحیافته با ایجاد تعادل بین جستجو و استناد بر تجربیات پیشنهاد شده است. نتایج آزمایشها نشان میدهد الگوريتم ارائهشده از کارایی مناسبی از هر دو جنبه هزينه و سرعت رسيدن به راه حل بهينه برخوردار است.
Stochastic games, as the generalization of Markov decision processes to the multi agent case, have long been used for modeling multi-agent system and are used as a suitable framework for Multi Agent Reinforcement Learning. Learning Automata (LA) were recently shown to be valuable tools for designing Multi-Agent Reinforcement Learning algorithms. In this paper a model based on learning automata and the concept of entropy for finding optimal policies in stochastic games is proposed. In the proposed model, for each state in the environment of the game and for each agent an S-model variable structure learning automaton is placed that tries to learn the optimal action probabilities in those states. The number of its adjacent states determines the number of actions of each learning automaton in each state and every joint action corresponds to a transition to an adjacent state. Entropy of the probability vector for the learning automaton of the next state is used to help learning process and improve the learning performance and is used a quantitative problem independent measurement for learning progress. We have also implemented a new version of the proposed algorithm that balances exploration with exploitation yielding improved performance. The experimental results show that the proposed algorithm has better learning performance than the other learning algorithms in terms of cost and the speed of reaching the optimal policy.
