Hierarchical reinforcement learning in complex wargame environments

Kompleks savaş oyunu ortamlarında hiyerarşik pekiştirmeli öğrenme

PDF İndir

Tez No: 854254
Yazar: KUBİLAY KAĞAN KÖMÜRCÜ
Danışmanlar: DOÇ. DR. NAZIM KEMAL ÜRE
Tez Türü: Yüksek Lisans
Konular: Astronomi ve Uzay Bilimleri, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Uçak Mühendisliği, Astronomy and Space Sciences, Computer Engineering and Computer Science and Control, Aeronautical Engineering
Anahtar Kelimeler: Belirtilmemiş.
Yıl: 2024
Dil: İngilizce
Üniversite: İstanbul Teknik Üniversitesi
Enstitü: Lisansüstü Eğitim Enstitüsü
Ana Bilim Dalı: Uçak ve Uzay Mühendisliği Ana Bilim Dalı
Bilim Dalı: Uçak ve Uzay Mühendisliği Bilim Dalı
Sayfa Sayısı: 111

Özet

Pekiştirmeli öğrenme, temelinde herhangi bir ortamda öznelerin numerik ödüllerini maksimize etmesi için hangi eylemleri yapması gerektiğine karar verme sürecidir ve bu süreçte öğrenme işlemini gerçekleştiren öğreniciye (robot vs.) hangi eylemleri yapacağı önceden verilmez (yani elinde herhangi bir veri seti yoktur) ve maksimum ödüle ulaşmak için öğrenicinin bulunduğu ortamı keşfetmesi gerekmektedir. Bu alan, derin yapay sinir ağlarının da pekiştirmeli öğrenmede daha yaygın kullanımı ile birlikte Derin Pekiştirmeli Öğrenme olarak da adlandırılmıştır. Bu öğrenicilerin sayısının birden fazla olduğu duruma ise“Çok Özneli Pekiştirmeli Öğrenme”denmektedir. Birden fazla öğrenici durumunda keşif, genelleştirme, planlama gibi pekiştirmeli öğrenmenin temel problemlerinin yanına görev dağılımı, öğrenicilerin iletişimi, öğrenicilere verimli ödül dağıtımı gibi birçok problem de dahil olmaktadır ve bu problemlerin çözümü için klasik pekiştirmeli öğrenmenin yanı sıra,“Oyun Teorisi”ve“Direkt Prensip (Policy) Araması Teknikleri”gibi alanlar ve fikirlerden de yararlanılmaktadır. Yeni algoritmaların öğrenilmesi sürecinde ihtiyaç duyulan ortamları sağlamak için Deepmind 2017 yılında Starcraft II adlı strateji oyunu ve OpenAI 2019 yılında DOTA 2 adlı çok oyunculu savaş arenası (MOBA) oyunu üzerine gerekli eklemeleri yapmak için çalışmalara başlamıştır. Deepmind, bu alandaki araştırmacıların kendi algoritmalarını eğitebilmeleri için, oluşturdukları Starcraft II ortamını demokratize etmiştir ve bu alanda yeni çıkan algoritmalar kaliteli bir ölçüm için bu ortamda denenmeye başlanmıştır. Öğrenicilerin iletişimi, limitli bir merkezi iletişim sistemiyle, yani her öğrenicinin kendi işini yaparken, sadece muğlakta kaldığında diğer öğrenicilerle iletişime geçmesiyle, sağlanabilmektedir. Ödül dağıtımı konusunda, (tipik ama hesaplama ve ödüllerin dağıtımı konusunda pek verimli olmayan bir şekilde) merkezi bir ödülle her öğreniciyi eğitilebilmektedir. Bu probleme başka bir çözüm ise her öğrenicinin kendi prensipleri doğrultusunda aldığı öznel ödülleri değerlendirip ona göre hareket etmesidir fakat merkezi tanımlanmış başka bir ödül sistemi bu öğrenicilerinin hareketlerini sistemin iyiliği için kısıtlayacak şekildedir. Görev dağılımı konusunda da farklı metotlarla öznel işlemler yapılmasına rağmen sistem için merkezi bir sürecin de devam ettiği algoritmalar kullanılmaktadır. Son zamanlarda, Pekiştirmeli Öğrenme (RL) özneleri, zorlu savaş oyunlarını başarıyla ele alma konusunda bazen insan oyuncuları bile geride bırakmıştır. Bu durum, RL yöntemlerinin uzun karar alma süreleri, seyrek ödüller ve geniş olası hareket setleri ile karakterize edilen savaş oyunları için uygun olduğunu düşündürmektedir. Ancak, savaş oyunları son derece karmaşıktır ve RL ile bile neredeyse optimum bir çözüme ulaşmak için büyük miktarda deneyim gerektirir ve örnek verimliliğini (sample efficiency) zorlar. Bu tez çalışmasında verimlilik düşüklüğünü ele almak için oyunu daha basit alt oyunlara bölerek bir hiyerarşik yapı kurmak, ve bu yapı ile genel oyunu çözmek önerilmiştir. Alt oyunların her biri genel oyundaki belirli bir temel beceriye odaklanmaktadır. Bu alt oyunlar, ana oyuna kıyasla daha kısa karar horizonlarına ve daha küçük durum ve aksiyon kümelerine sahiptir. Öğrenme sürecini yönlendirmek için, bu daha basit alt oyunlardan oluşan bir müfredatı içeren hiyerarşik bir kontrol yapısı benimsenmiştir. Eğitimler için test ortamı olarak StarCraft II seçilmiştir, çünkü StarCraft II, uzmanlara göre savaş oyunlarıyla en çok ortak özelliğe sahip ortamdır ve bu tür senaryolarda yaygın olarak kullanılmıştır. Ampirik değerlendirme yoluyla, tanıtılan hiyerarşik mimarinin StarCraft II tabanlı karmaşık savaş oyunu ortamını başarıyla çözebildiği gösterilirken, bir hiyerarşik olmayan öznenin bunu başaramadığı gösterilmektedir. Ayrıca, alt oyunların başka varyasyonları oluşturulmuş ve bu varyasyon alt oyunlar da ana oyunun opsiyonlarına eklenerek etkisi gözlemlenmiştir. Alınan sonuçlar, bütün temel becerileri kapsayan alt oyunlar eklendikten sonra daha fazla alt oyun eklemenin ana oyuna sadece marjinal derecede bir etkisi olduğunu göstermiştir. Ayrıca, Pekiştirmeli Öğrenme (RL) çeşitli uygulamalarda dikkat çekici başarılar elde etmiş olmasına rağmen, Markov Karar Süreçleri'ni (MDP) oluştururken seçtiğimiz“karar sıklığı”teriminin gerçek dünya senaryolarında yeterince takdir edilmediği görülmektedir. Bu tez, karar sıklığının önemli rolünü ve RL eğitimi üzerindeki etkilerini aydınlatmayı da amaçlamaktadır. Bu, bir toy MDP ortamının detaylı analiziyle birlikte gerçekleştirilmiştir ve ardından bu bilginin karmaşık bir StarCraft 2 ortamını çözmek için uygulanmasıyla devam etmektedir. Bulgularımız, karar sıklığına ince ayar yapmanın, RL eğitiminin başarılı veya başarısız olmasını belirlemede kilit rol oynayabileceğini göstermektedir. Gözlemlerimizi açıklamak için, karar sıklığı ayarlama için sezgisel bir yöntem önerilmiştir ve bunun etkisi kontrol edilmiş bir toy deney ve StarCraft 2 mini oyunları ile temel beceriler bağlamında sergilenmiştir. Bu temel becerileri kullanarak, bir RL modelini StarCraft 2 oyunlarının en zorlu türlerinden biri için eğitmek için hiyerarşik bir yaklaşım benimsenmiştir. sonuçlar karşılaştırıldığında, yöntemimizin benzer yaklaşımlara üstünlüğünü, ve benzer sonuçlara ulaşmak için benzer yöntemlerin yaklaşık 30 yıl süren eğitim gerektirmesine karşı, bu yöntemin yaklaşık 30 gün gerçek zamanlı deneyimle benzer puanlar elde edebildiğini göstermektedir. Bu tez çalışmasında, ilk odak noktamız ana görevi alt görevlere ayırmakla ilgilidir; her bir alt görev, hiyerarşik olmayan bir özne tarafından bağımsız bir şekilde ele alınabilen ve ana görevde ustalaşmak için kritik öneme sahip olan temel bir beceriyi temsil etmektedir. Bu hiyerarşik yapı oluşturma çalışmasının iki ana katkısı vardır: Birincisi, önerilen hiyerarşik yaklaşımın, savaş oyunu ortamlarında karşılaşılan karmaşık zorlukları etkili bir şekilde çözdüğü gösterilmektedir. Bu zorluklar, klasik yöntemlerle eğitim gören bir özne için aşılamaz zorluklardır. Ayrıca her öznenin kendi temel becerisine özel optimize edildiği durumda ve politikaları hiyerarşik bir çerçeve içinde birleştirildiğinde, StarCraft II ortamında hiyerarşinin üst katmandaki öznesi optimize edilmese bile yüksek performans elde edilebileceğini gösteren bulguları ortaya koymaktadır. İkincisi, temel beceri setinin ötesine geçen alt görev kümesini genişletmenin performansta önemli bir iyileme sağlamadığı gözlemlenmiştir. Deneylerin gerçeklenmesinde bir müfredat ortamı tanımlanmıştır ve ilgili alt görevlerde eğitilen alt politikalar için hiyerarşik kontrol uygulanmaktadır. Ana görevin temel becerileri, yönetilmesi daha kolay ancak yine de kendi içerisinde kapsamlı bir alt görev kümesine bölünmektedir. Her bir alt görev, gerekli örnek büyüklüğü açısından daha basit bir şekilde elde edilebilen bir amaç fonksiyonunu içermektedir. Tüm alt görevlerde benzer oyun mekaniklerine rağmen, rakip davranışlarındaki değişiklikler, her bir alt görevin MDP içinde geçiş dağılımında ve başlangıç durumu dağılımında farklılıklara yol açmaktadır. Her alt görev için farklı amaç fonksiyonları bulunduğundan, her bir alt görev, farklı ödül kümeleri ve farklı indirim faktörleri ile ilişkilidir. Bu karmaşıklığı ele almak için her bir alt görev için bağımsız bir özne eğitilmiştir. Her bir alt görevden elde edilen her bir politika, ana görev içerisinde hiyerarşik bir kontrol yapısı kullanarak birleştirilmiştir. Eğitimler ve deneyler StarCraft II Öğrenme Ortamları (SC2LE) ile gerçekleştirilmiştir. StarCraft II, gerçek zamanlı bir strateji oyunudur ve karmaşık askeri oyun dinamiklere sahiptir. Geniş bir gözlem (durum) ve eylem (aksiyon) uzayı içermektedir. İçsel zorlukları nedeniyle pek çok kez Pekiştirmeli Öğrenme araştırmalarında yaygın bir şekilde kullanılmıştır. Ayrıca, StarCraft II, askeri dinamikler açısından en gerçekçi ortamlardan biri olarak kabul edilmekte olup, özel oyun senaryoları ve amaçları farklı harita seçenekleri oluşturma kolaylığını da sunmaktadır. Deneylerde, SC2LE'den sağlanan ortamları kullanmanın yanı sıra oyunun harita düzenleyicisini kullanarak bize özel ortamlar da oluşturulmuştur. Bu tezde, StarCraft II ortamını RL ile çözmek için bir Hiyerarşik Pekiştirmeli Öğrenme metodu olan Temel Beceri Ayrıştırımı isimli Algoritma Oluşturulmuştur. Bu algoritma, her bir alt görev için bireysel alt politikaları ve bu alt politikalar arasından seçim yapan bir yönetici politikayı öğrenmekte, böylece hiyerarşik bir özne oluşturmaktadır. Bu yaklaşım, karmaşık bir savaş oyunu ortamını, ortamın temel yönlerini koruyarak hiyerarşik olmayan A2C algoritması gibi klasik bir RL algoritmasıyla çözülebilecek alt görevlere ayrıştırmayı içermektedir. Yöntem, oldukça kapsamlı StarCraft II ortamlarında değerlendirilmiştir ve bu ortamlar alt görevlere ayrıştırıldığında, hiyerarşik mimarinin ortamı başarıyla çözdüğü, bahsedilen tarzda klasik yöntemleri kullanan bir öznenin bunu başaramadığı gösterilmiştir. Bu tezde aynı zamanda, Pekiştirmeli Öğrenme'de Markov Karar Süreçleri oluştururken genellikle küçümsenen ancak deneylerin gözlemlerine bakıldığında hayati öneme sahip bir faktör olan karar sıklığına da değinilmiştir. Deneyler, karar sıklığına ince ayar yapılmasının RL eğitiminin etkinliği üzerinde önemli bir etkiye sahip olduğunu ortaya koymuştur. Bu tezin elde ettiği sonuçlar, 3 ana kategoride sınıflandırılabilir. Birincisi, SC2LE'de hazır olarak bulunan ortamların ham aksiyonların yanı sıra makro aksiyonlar kullanarak çözülmesiyle birlikte oldukça basit ve ilkel bir hiyerarşik yapının etkisinin gözlemlenmesidir. Bu yaklaşım, klasik metodların zorlandığı SC2LE ortamlarını maksimum skora yakın skorlar alarak çözmüştür. İkincisi, Temel Beceri Ayrıştırması metodu kullanılarak dinamiklerinin birbirleriyle olan ilişkileri karmaşık olan ve klasik metodlar ile çözülemeyen SC2LE ortamlarının çözülmesi ve anlamlı ve karmaşık savaş stratejilerinin geliştirilmesidir. Sonuncusu ise, karar sıklığı parametresinin önemini açıklarken, bu değerin Temel Beceri Ayrıştırması'nın alt oyunlarında optimize edilerek ve oluşan büyük hiyerarşik yapının nizami Starcraft II oyunu oynatılması suretiyle Starcraft II oyununun bütün botlarını yenilgiye uğratacak bir başarı alınmasıdır.

Özet (Çeviri)

In recent times, Reinforcement Learning (RL) agents have achieved remarkable success in tackling difficult games, sometimes outperforming human players. This suggests that RL methods are well-suited for wargames, which are characterized by long decision-making periods, infrequent rewards, and extensive sets of possible actions. However, wargames are highly complex, and even with RL, convergence to a near-optimum solution requires an immense amount of experience and makes the solution sample inefficient. To address this inefficiency, we propose dividing the game into simpler sub-games, each focusing on a specific core skill of the overall game. These sub-games have shorter decision horizons and smaller action sets compared to the main game. To guide the learning process, we adopt a curriculum learning approach, employing a hierarchical control structure where the curriculum comprises these simpler sub-games. For my experimentation, we select StarCraft II as the test environment, as it shares common characteristics with wargames and has been extensively used in such scenarios. Through empirical evaluation, we demonstrate that our hierarchical architecture can successfully solve the complex wargame environment based on StarCraft II, whereas a non-hierarchical agent fails to do so. Additionally we plan to conduct an ablation study to investigate the impact of action frequency on training quality, which we believe to be a crucial factor. Since Starcraft II is a real-time strategy game, and not a turn-based strategy game, it is possible to take actions in different time intervals. we believe that taking actions rarely, as well as too frequently, will hinder the training quality. The recent achievements of Reinforcement Learning (RL) methods have garnered widespread attention across various domains. Among the notable applications, wargames stand out, encompassing a diverse array of games like board games such as chess and Go, as well as strategy games like StarCraft and MicroRTS. Despite the broad spectrum within wargames, they share common features that distinguish them from other domains. These include large action spaces, whether discrete or hybrid, branching actions, adversarial opponent dynamics, and notably sparse reward functions. Additionally, wargames exhibit a characteristic where decisions made by an agent have a delayed impact on the game dynamics, posing challenges for optimization. To tackle these obstacles, several methods have been proposed, including Hierarchical Reinforcement Learning (HRL), forward planning, and curriculum learning. In this study, we primarily employ curriculum learning and a straightforward HRL approach in the real-time strategy game StarCraft II, comparing these techniques with a non-hierarchical agent. Also, although Reinforcement Learning (RL) has exhibited remarkable success across various applications, yet the significance of selecting what we term“decision frequency”in constructing Markov Decision Processes (MDPs) remains underappreciated in real-world scenarios. This thesis sheds light on the crucial role of decision frequency and its impact on RL training through a thorough analysis of a toy experiment, followed by the application of this knowledge to solve a complex StarCraft 2 environment. Our findings underscore that finely tuning decision frequency can be pivotal in determining the success or failure of RL training. To illustrate our insights, we propose an intuitive method for decision frequency tuning, showcasing its effectiveness in both a controlled toy experiment and within the context of StarCraft 2 minigames, known as core skills. Utilizing these core skills, we employ a hierarchical approach to train a model for one of the most challenging types of StarCraft 2 games. Benchmarking results highlight the superiority of our method over similar approaches, achieving competitive scores with approximately 30 days of real-time experience, compared to the approximately 30 years required by comparable methods to achieve similar results. In this study, our initial focus involves the dissection of the primary task into sub-tasks, with each sub-task representing a fundamental skill that can be independently addressed by a non-hierarchical agent and is crucial for mastering the primary task. Our contribution encompasses two key aspects: Firstly, we demonstrate that the proposed hierarchical approach effectively resolves complex challenges presented in wargame environments, challenges that remain insurmountable for a non-hierarchical agent. Additionally, our findings reveal that optimizing dedicated agents for each individual sub-task and combining their policies within a hierarchical framework yields commendable performance scores in the StarCraft II environment, even in the absence of optimization for the hierarchical controller. Secondly, we observe that expanding the set of sub-tasks beyond the core-skill set does not yield a substantial improvement in performance. We introduce a curriculum setting and implement hierarchical control for the sub-policies trained in their respective sub-tasks. The overarching objective of the main task is partitioned into a more manageable yet still comprehensive set of sub-tasks. Each sub-task involves an objective function that is simpler to achieve in terms of the required sample size. Despite uniform game mechanics across all sub-tasks, variations in opponent behaviors lead to differences in the transition distribution and the initial state distributio within the Markov Decision Process (MDP) of each sub-task. Owing to distinct objective functions, each sub-task is associated with a unique reward setand a discount factor. To address this complexity, we independently train an agent for each sub-task, with a corresponding policy, subsequently merging them using a hierarchical control structure within the main task. Our experimentation is conducted within the StarCraft II Learning Environments (SC2LE). StarCraft II, operating as a real-time strategy game, features complex military dynamics, presenting an extensive observation space and a diverse set of actions. It has been widely utilized in reinforcement learning (RL) research due to its inherent challenges. Moreover, StarCraft II is recognized as one of the most realistic environments in terms of military dynamics, offering the flexibility of creating custom game scenarios and objectives across a varied selection of maps. In our experiments, we utilize both the provided environments from SC2LE and construct our own custom environments using the game's map editor. We've introduced a Core Skill Decomposition algorithm, a form of Hierarchical Reinforcement Learning. This algorithm learns individual sub-policies for each sub-task and a manager policy that selects among these sub-policies to create a hierarchical agent. Our approach involves decomposing a complex wargame environment into sub-tasks that can be solved by a non-hierarchical A2C algorithm, while retaining the core aspects of the environment. We evaluate our method in three challenging StarCraft II environments and demonstrate that, when these environments are decomposed into sub-tasks, our hierarchical architecture successfully solves the environment, whereas a non-hierarchical agent fails to do so. Additionally, we observe that expanding the core set of skills only results in a marginal increase in performance. This thesis also addresses the often underestimated yet pivotal factor of decision frequency in the construction of Markov Decision Processes (MDPs) in Reinforcement Learning (RL). Our investigation has unveiled that the careful adjustment of decision frequency holds substantial sway over the efficacy of RL training, presenting potential implications across a diverse array of applications.

Benzer Tezler

Tez No
714508
Reinforcement learning in fighting games
Dövüş oyunlarında pekiştirmeli öğrenme
MUHAMMET SADIK UĞURSOY
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol İstanbul Teknik Üniversitesi
Oyun ve Etkileşim Teknolojileri Ana Bilim Dalı
DOÇ. DR. SANEM SARIEL UZER
Tez No
390690
Hierarchical reinforcement learning on non-stationary environments
Devingen ortamlarda sıradüzensel pekiştirmeli öğrenme
YİĞİT EFE YÜCESOY
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol Marmara Üniversitesi
Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA BORAHAN TÜMER
Tez No
238790
Development of an autonomous sailor: An application of hierarchical reinforcement learning to sailing
Yelken yapmayı öğrenen sanal etmenlerin pekiştirmeli öğrenme yöntemleri kullanılarak benzetim ortamındaki eğitimi
HÜSEYİN ŞENCAN
Yüksek Lisans
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol Marmara Üniversitesi
Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. BORAHAN TÜMER
Tez No
895551
Resource allocation mechanisms for end-to-end delay optimization of 5G URLLC services
5G URLLC hizmetlerinin uçtan uca gecikme optimizasyonu için kaynak aktarım mekanizmaları
HASAN ANIL AKYILDIZ
Doktora
İngilizce
2024
Mühendislik Bilimleri İstanbul Teknik Üniversitesi
Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. HAKAN ALİ ÇIRPAN
DR. İBRAHİM HÖKELEK
Tez No
784500
Hiyerarşik başlangıç pozisyonlu derin Q-ağı algoritması ile mobil robot uygulaması
Mobile robot application with hierarchical start position deep Q-network algorithm
EMRE ERKAN
Doktora
Türkçe
2022
Elektrik ve Elektronik Mühendisliği Dicle Üniversitesi
Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUHAMMET ALİ ARSERİM

Geri Dön