Effective subgoal discovery and option generation in reinforcement learning

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2016

Öğrenci: ALPER DEMİR

Danışman: FARUK POLAT

Özet:

Subgoal discovery is proven to be a practical way to cope with large state spaces in Reinforcement Learning. Subgoals are natural hints to partition the problem into sub-problems, allowing the agent to solve each sub-problem separately. Identification of such subgoal states in the early phases of the learning process increases the learning speed of the agent. In a problem modeled as a Markov Decision Process, subgoal states possess key features that distinguish them from the ordinary ones. A learning agent needs a way to reach an identified subgoal, and this can be achieved by forming an option to reach it. Most of the studies in the literature focus on finding useful subgoals by employing statistical methods and graph-based methods. On the other hand, there are few studies working on how to improve the process of forming options. In this thesis, an efficient subgoal discovery making use of local information is proposed. Unlike other methods, it has lower time complexity and does not require additional problem specific parameters. Furthermore, a better heuristic for forming options is proposed. It focuses on collecting a set of states that an option is really useful to employ from, leading to more effective options.