عنوان پایان‌نامه
بهبود ساخت درخت تصمیم در یادگیری تقویتی سلسله مراتبی با استفاده از سری فوریه
- دانشجو
- محمدامین نیازی رضوی
- استاد راهنما
- مسعود اسدپور
- رشته تحصیلی
- مهندسی کامپیوتر - هوش مصنوعی - رباتیک
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 2611;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 66597
- تاریخ دفاع
- ۱۵ شهریور ۱۳۹۳
- چکیده
- یک راه‌‌حل برای یادگیری تقویتی در فضای حالت پیوسته، گسسته‌سازی فضای حالت و استفاده از روش‌های مرسوم در فضای حالت گسسته مانند روش‌های جدولی است. این روش‌ها با افزایش ابعاد مقیاس‌پذیر نیستند و زمان یادگیری آنها به‌صورت نمایی افزایش می‌یابد. یکی از راه‌هایی که برای رفع این مشکل معرفی شده استفاده از گسسته‌سازی ناهمگون است، به این صورت که نواحی مهم‌تر فضای حالت که دارای تغییرات زیادی هستند بیشتر تقسیم شده ولی در نواحی ساده و با تغییرات کمتر، فضا بزرگ‌تر در نظر گرفته می‌شوند. با این‌کار سعی می‌شود تعادلی بین نیاز به دقت بالاتر برای افزایش پاداش و تعداد نواحی کمتر برای افزایش سرعت یادگیری برقرار کرد. درخت تصمیم یکی از مرسوم‌ترین روش‌ها برای گسسته‌سازی ناهمگون است. اما کاربرد این روش در یادگیری تقویتی به دلیل ماهیت تعاملی و در حال تغییر مساله یادگیری تقویتی با مشکلاتی روبه‌رو است. روش‌های موجود سعی می‌کنند با تعیین یک ارزش به‌ازای هر نمونه براساس تابع ارزش مساله، قابلیت تفکیکی بین نمونه‌های موجود ایجاد کنند. این‌کار دو مشکل بوجود می‌آورد، اول آنکه تشکیل نمونه‌های با ارزش تخمینی دقیق برای تقسیم، زمان‌بر و وابسته به تقسیمات قبلی است. دیگر آنکه تا زمانی که یادگیری به حد کافی انجام نشود، ارزش نمونه‌ها دارای اعتبار زیادی نخواهند بود و تمام تقسیمات انجام شده بر اساس این نمونه‌ها می‌تواند در آینده نقض شود و یا بهبود یابد. عدم اعتبار و افزایش تدریجی اعتبار نمونه‌ها باعث می‌شود تعداد زیادی ناحیه بیهوده ایجاد شود که منجر به افزایش زمان یادگیری خواهد شد. در این پایان‌نامه ابتدا توسط یک روش مبتنی بر تخمین تابع خطی و با استفاده از پایه‌های فوریه، یادگیری را سریع‌تر و تعمیم یافته‌تر کرده و براساس آن به گسسته‌سازی ناهمگون فضای‌حالت می‌پردازیم. از طرفی روش‌های تخمین تابع خطی نیازمند تعیین درجه آزادی تابع هستند تا بتوانند پیچیدگی‌های محیط را تخمین بزنند. برای رفع این مشکل، با شناسایی نواحی پیچیده در تخمین، اقدام به گسسته‌سازی فضا می‌کنیم و در هر زیر ناحیه یک تابع‌تخمین ساده با درجه آزادی کم، قرار می‌دهیم. با این‌کار تعدادی تابع تخمین با درجه آزادی کم در فضای گسسته‌سازی شده قرار می‌دهیم، به طوری‌که هر ناحیه پیچیده‌تر از تابع تخمین خطی متناظر با آن نباشد. با استفاده از این ایده به تدریج فضای حالت را از یک حالت پیوسته پیچیده و بزرگ به تعدادی حالات کوچک‌تر و ساده تقسیم کرده و در یک ساختار درختی ذخیره می‌کنیم. این روش روی مساله ماشین کوهستان آزمایش شده است. نتایج این آزمایش بیانگر این است که روش ارائه شده کارایی بهتری از نظر متوسط پاداش، پاداش لحظه‌ای و مدت زمان‌پردازش دارد. کلمات کلیدی: یادگیری تقویتی، گسسته‌سازی فضای حالت، درخت تصمیم، تخمین‌تابع خطی، پایه فوریه
- Abstract
- State discretization is a common approach for solving Reinforcement Learning (RL) problems with continuous state-spaces. Based on this approach we can employ conventional tabular learning methods in continuous state-spaces. Although tabular methods perform well in small problems, they are not scalable and their learning time grows exponentially with the size and dimensions of the state-space. Heterogeneous discretization tries to reduce the number of states by having course discretization when possible and more accurate discretization where it is needed. Decision trees are a common way of heterogeneous discretization. However, in RL they cannot easily be used due to the interactive nature and improving policy of RL. Current methods work by storing samples from agent's transactions in the environment and defining a value for each sample, in the next step they split those samples according to differences in distribution of their values. These methods have two problems, first learning the true value of a sample requires a lot of sampling and the estimated value is also dependent on the previous splits. Second, split criteria are based on the value of samples, and at some point there could be differences in what the tree structure describes and the distribution of the values. This would cause more splits to correct it. This results into more splits and more resolution in places where the estimated value of samples are not mature enough. In this thesis, first we improve the speed of learning and the amount of generalizations in the learning process by employing linear function approximation with Fourier basis. Later we propose a heterogeneous discretization method according to the learned values. The conventional linear function approximation methods require a predefined degree of freedom, which defines how complex the approximated function could be. However, in our approach we overcome this, by identifying an area with a complex value function of the state-space and splitting it into two less complex sub-spaces. Then, we put a simple linear function approximator with small degree of freedom in each sub-space. We repeat this procedure for each sup-space until the value function in the sub-space is not more complex than its corresponding simple linear function approximator. Using this idea, we hierarchically split a big and complex state-space into a small and simple sub-states in a decision tree. The method is tested on the ``mountain car'' problem and it could outperform the conventional methods in terms of accumulated reward, rewards per episode, and computation time. Keywords: Reinforcement Learning, State-space discretization, Decision tree, Linear function approximation, Fourier basis
