Title (eng)
Learning when to plan
Advisor
Sebastian Tschiatschek
Assessor
Sebastian Tschiatschek
Abstract (deu)
Verstärkendes Lernen (Reinforcement Learning, RL) Algorithmen haben aufgrund ihrer beeindruckenden Leistung und breiten Anwendbarkeit in verschiedenen Bereichen große Aufmerksamkeit erlangt. Ein prominenter Algorithmus, der sich auf Spiele konzentriert, AlphaZero, kombiniert neuronale Netzwerke mit Monte Carlo Tree Search (MCTS), um das Lernen zu beschleunigen. Allerdings kann das feste Suchbudget von AlphaZero (d.h. die Anzahl der MCTS-Suchspuren) zu Ineffizienzen führen, indem zu viel Planung auf vorhersehbare Ergebnisse und zu wenig auf unsichere Ergebnisse verwendet wird. In dieser Arbeit schlagen wir Änderungen am AlphaZero-Algorithmus vor, um das Suchbudget dynamisch basierend auf der geschätzten Unsicherheit in seinen Komponenten – dem neuronalen Netzwerk und MCTS – anzupassen. Um die Unsicherheit des neuronalen Netzwerks zu schätzen, erweitern wir AlphaZero unter Verwendung von Prinzipien aus dem distributionellen Verstärkungslernen, wobei die Varianz in den Quantilen als Unsicherheit betrachtet wird. Die Unsicherheit von MCTS wird basierend auf der Tiefe und Größe von Teilbäumen geschätzt. Diese Unsicherheiten werden dann von einem Deep Q-Network (DQN)-Agenten genutzt, um das Suchbudget bei jedem Schritt anzupassen. Unser vorgeschlagener Ansatz wird an den CartPole- und MinAtar-Umgebungen unter Verwendung von AlphaZero und DQN als Baselines evaluiert. Die Ergebnisse zeigen, dass die dynamische Zuweisung der Anzahl von Suchspuren basierend auf Unsicherheit die Effizienz des Algorithmus verbessert, was durch ein verbessertes Verhältnis von Belohnung pro Suchspur belegt wird. Darüber hinaus, obwohl unsere Änderungen zusätzliche Rechenkosten eingeführt haben, wurde die Gesamt-Laufzeit in bestimmten Umgebungen reduziert, während die Baseline-Leistung in Bezug auf die Gesamtbelohnung beibehalten oder sogar übertroffen wurde.
Abstract (eng)
Reinforcement Learning (RL) algorithms have gained significant attention due to their impressive performance and wide applicability across various domains. A prominent algorithm focused on games, AlphaZero, combines neural networks with Monte Carlo Tree Search (MCTS) to accelerate learning. However, AlphaZero's fixed search budget (i.e., the number of MCTS search traces) can lead to inefficiencies by dedicating too much planning to predictable outcomes or insufficient planning to uncertain ones. In this thesis, we propose modifications to the AlphaZero algorithm to dynamically adjust the search budget based on the estimated uncertainty in its components: the neural network and MCTS. To estimate the first, we extend AlphaZero using principles from distributional reinforcement learning, taking the variance in quantiles as uncertainty. MCTS uncertainty is estimated based on the depth and size of subtrees. These uncertainties are then leveraged by a Deep Q-Network (DQN) agent to adjust the search budget at each step. Our proposed approach is evaluated on the CartPole and MinAtar environments using AlphaZero and DQN as baselines. The findings show that dynamically allocating the number of search traces based on uncertainty enhances algorithm efficiency, as evidenced by an improved reward-per-trace ratio. Furthermore, even though our modifications introduced additional computation costs, the overall run-time was reduced in certain environments while maintaining or exceeding baseline performance in terms of total reward.
Keywords (deu)
Verstärkendes LernenAlphazeroUnsicherheitMaschinelles Lernen
Keywords (eng)
reinforcement learningalphazerouncertaintymachine learning
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:2112854
rdau:P60550 (deu)
xiii, 55 Seiten : Illustrationen
Number of pages
71
Study plan
Masterstudium Data Science
[UA]
[066]
[645]
Association (deu)
Title (eng)
Learning when to plan
Abstract (deu)
Verstärkendes Lernen (Reinforcement Learning, RL) Algorithmen haben aufgrund ihrer beeindruckenden Leistung und breiten Anwendbarkeit in verschiedenen Bereichen große Aufmerksamkeit erlangt. Ein prominenter Algorithmus, der sich auf Spiele konzentriert, AlphaZero, kombiniert neuronale Netzwerke mit Monte Carlo Tree Search (MCTS), um das Lernen zu beschleunigen. Allerdings kann das feste Suchbudget von AlphaZero (d.h. die Anzahl der MCTS-Suchspuren) zu Ineffizienzen führen, indem zu viel Planung auf vorhersehbare Ergebnisse und zu wenig auf unsichere Ergebnisse verwendet wird. In dieser Arbeit schlagen wir Änderungen am AlphaZero-Algorithmus vor, um das Suchbudget dynamisch basierend auf der geschätzten Unsicherheit in seinen Komponenten – dem neuronalen Netzwerk und MCTS – anzupassen. Um die Unsicherheit des neuronalen Netzwerks zu schätzen, erweitern wir AlphaZero unter Verwendung von Prinzipien aus dem distributionellen Verstärkungslernen, wobei die Varianz in den Quantilen als Unsicherheit betrachtet wird. Die Unsicherheit von MCTS wird basierend auf der Tiefe und Größe von Teilbäumen geschätzt. Diese Unsicherheiten werden dann von einem Deep Q-Network (DQN)-Agenten genutzt, um das Suchbudget bei jedem Schritt anzupassen. Unser vorgeschlagener Ansatz wird an den CartPole- und MinAtar-Umgebungen unter Verwendung von AlphaZero und DQN als Baselines evaluiert. Die Ergebnisse zeigen, dass die dynamische Zuweisung der Anzahl von Suchspuren basierend auf Unsicherheit die Effizienz des Algorithmus verbessert, was durch ein verbessertes Verhältnis von Belohnung pro Suchspur belegt wird. Darüber hinaus, obwohl unsere Änderungen zusätzliche Rechenkosten eingeführt haben, wurde die Gesamt-Laufzeit in bestimmten Umgebungen reduziert, während die Baseline-Leistung in Bezug auf die Gesamtbelohnung beibehalten oder sogar übertroffen wurde.
Abstract (eng)
Reinforcement Learning (RL) algorithms have gained significant attention due to their impressive performance and wide applicability across various domains. A prominent algorithm focused on games, AlphaZero, combines neural networks with Monte Carlo Tree Search (MCTS) to accelerate learning. However, AlphaZero's fixed search budget (i.e., the number of MCTS search traces) can lead to inefficiencies by dedicating too much planning to predictable outcomes or insufficient planning to uncertain ones. In this thesis, we propose modifications to the AlphaZero algorithm to dynamically adjust the search budget based on the estimated uncertainty in its components: the neural network and MCTS. To estimate the first, we extend AlphaZero using principles from distributional reinforcement learning, taking the variance in quantiles as uncertainty. MCTS uncertainty is estimated based on the depth and size of subtrees. These uncertainties are then leveraged by a Deep Q-Network (DQN) agent to adjust the search budget at each step. Our proposed approach is evaluated on the CartPole and MinAtar environments using AlphaZero and DQN as baselines. The findings show that dynamically allocating the number of search traces based on uncertainty enhances algorithm efficiency, as evidenced by an improved reward-per-trace ratio. Furthermore, even though our modifications introduced additional computation costs, the overall run-time was reduced in certain environments while maintaining or exceeding baseline performance in terms of total reward.
Keywords (deu)
Verstärkendes LernenAlphazeroUnsicherheitMaschinelles Lernen
Keywords (eng)
reinforcement learningalphazerouncertaintymachine learning
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:2118040
Number of pages
71
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0