TU Darmstadt / ULB / TUbiblio

Sample Efficient Monte Carlo Tree Search for Robotics

Dam, Tuan (2023)
Sample Efficient Monte Carlo Tree Search for Robotics.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00022931
Dissertation, Erstveröffentlichung, Verlagsversion

Kurzbeschreibung (Abstract)

Artificial intelligent agents that behave like humans have become a defining theme and one of the main goals driving the rapid development of deep learning, particularly reinforcement learning (RL), in recent years. Monte-Carlo Tree Search (MCTS) is a class of methods for solving complex decision-making problems through the synergy of Monte-Carlo planning and Reinforcement Learning (RL). MCTS has yielded impressive results in Go (AlphaGo), Chess(AlphaZero), or video games, and it has been further exploited successfully in motion planning, autonomous car driving, and autonomous robotic assembly tasks. Many of the MCTS successes rely on coupling MCTS with neural networks trained using RL methods such as Deep Q-Learning, to speed up the learning of large-scale problems. Despite achieving state-of-the-art performance, the highly combinatorial nature of the problems commonly addressed by MCTS requires the use of efficient exploration-exploitation strategies for navigating the planning tree and quickly convergent value backup methods. Furthermore, large-scale problems such as Go and Chess games require the need for a sample efficient method to build an effective planning tree, which is crucial in on-the-fly decision making. These acute problems are particularly evident, especially in recent advances that combine MCTS with deep neural networks for function approximation. In addition, despite the recent success of applying MCTS to solve various autonomous robotics tasks, most of the scenarios, however, are partially observable and require an advanced planning method in complex, unstructured environments.

This thesis aims to tackle the following question: How can robots plan efficiency under highly stochastic dynamic and partial observability? The following paragraphs will try to answer the question:

First, we propose a novel backup strategy that uses the power mean operator, which computes a value between the average and maximum value. We call our new approach Power Mean Upper Confidence bound Tree (Power-UCT). We theoretically analyze our method providing guarantees of convergence to the optimum. Finally, we empirically demonstrate the effectiveness of our method in well-known Markov decision process (MDP) and partially observable Markov decision process (POMDP) benchmarks, showing significant improvement in terms of sample efficiency and convergence speed w.r.t. state-of-the-art algorithms.

Second, we investigate an efficient exploration-exploitation planning strategy by providing a comprehensive theoretical convex regularization framework in MCTS. We derive the first regret analysis of regularized MCTS, showing that it guarantees an exponential convergence rate. Subsequently, we exploit our theoretical framework to introduce novel regularized backup operators for MCTS based on the relative entropy of the policy update and, more importantly, on the Tsallis entropy of the policy, for which we prove superior theoretical guarantees. Afterward, we empirically verify the consequence of our theoretical results on a toy problem. Eventually, we show how our framework can easily be incorporated in AlphaGo, and we empirically show the superiority of convex regularization, w.r.t. representative baselines, on well-known RL problems across several Atari games.

Next, we take a further step to draw the connection between the two methods, Power-UCT and the convex regularization in MCTS, providing a rigorous theoretical study on the effectiveness of α-divergence in online Monte-Carlo planning. We show how the two methods can be related by using α-divergence. We additionally provide an in-depth study on the range of α parameter that helps to trade-off between exploration-exploitation in MCTS, hence showing how α-divergence can achieve state-of-the-art results in complex tasks.

Finally, we investigate a novel algorithmic formulation of the popular MCTS algorithm for robot path planning. Notably, we study Monte-Carlo Path Planning (MCPP) by analyzing and proving, on the one part, its exponential convergence rate to the optimal path in fully observable MDPs, and on the other part, its probabilistic completeness for finding feasible paths in POMDPs (proof sketch) assuming limited distance observability. Our algorithmic contribution allows us to employ recently proposed variants of MCTS with different exploration strategies for robot path planning. Our experimental evaluations in simulated 2D and 3D environments with a 7 degrees of freedom (DOF) manipulator and in a real-world robot path planning task demonstrate the superiority of MCPP in POMDP tasks.

In summary, this thesis proposes and analyses novel value backup operators and policy selection strategies both in terms of theoretical and experimental perspectives to help cope with sample efficiency and exploration-exploitation trade-off problems in MCTS and bring these advanced methods to robot path planning, showing the superiority in POMDPs w.r.t the state-of-the-art methods.

Typ des Eintrags: Dissertation
Erschienen: 2023
Autor(en): Dam, Tuan
Art des Eintrags: Erstveröffentlichung
Titel: Sample Efficient Monte Carlo Tree Search for Robotics
Sprache: Englisch
Referenten: Peters, Prof. Jan ; Szepesvári, Prof. Csaba ; Pajarinen, Prof. Dr. Joni
Publikationsjahr: 2023
Ort: Darmstadt
Kollation: xvi, 135 Seiten
Datum der mündlichen Prüfung: 22 September 2022
DOI: 10.26083/tuprints-00022931
URL / URN: https://tuprints.ulb.tu-darmstadt.de/22931
Kurzbeschreibung (Abstract):

Artificial intelligent agents that behave like humans have become a defining theme and one of the main goals driving the rapid development of deep learning, particularly reinforcement learning (RL), in recent years. Monte-Carlo Tree Search (MCTS) is a class of methods for solving complex decision-making problems through the synergy of Monte-Carlo planning and Reinforcement Learning (RL). MCTS has yielded impressive results in Go (AlphaGo), Chess(AlphaZero), or video games, and it has been further exploited successfully in motion planning, autonomous car driving, and autonomous robotic assembly tasks. Many of the MCTS successes rely on coupling MCTS with neural networks trained using RL methods such as Deep Q-Learning, to speed up the learning of large-scale problems. Despite achieving state-of-the-art performance, the highly combinatorial nature of the problems commonly addressed by MCTS requires the use of efficient exploration-exploitation strategies for navigating the planning tree and quickly convergent value backup methods. Furthermore, large-scale problems such as Go and Chess games require the need for a sample efficient method to build an effective planning tree, which is crucial in on-the-fly decision making. These acute problems are particularly evident, especially in recent advances that combine MCTS with deep neural networks for function approximation. In addition, despite the recent success of applying MCTS to solve various autonomous robotics tasks, most of the scenarios, however, are partially observable and require an advanced planning method in complex, unstructured environments.

This thesis aims to tackle the following question: How can robots plan efficiency under highly stochastic dynamic and partial observability? The following paragraphs will try to answer the question:

First, we propose a novel backup strategy that uses the power mean operator, which computes a value between the average and maximum value. We call our new approach Power Mean Upper Confidence bound Tree (Power-UCT). We theoretically analyze our method providing guarantees of convergence to the optimum. Finally, we empirically demonstrate the effectiveness of our method in well-known Markov decision process (MDP) and partially observable Markov decision process (POMDP) benchmarks, showing significant improvement in terms of sample efficiency and convergence speed w.r.t. state-of-the-art algorithms.

Second, we investigate an efficient exploration-exploitation planning strategy by providing a comprehensive theoretical convex regularization framework in MCTS. We derive the first regret analysis of regularized MCTS, showing that it guarantees an exponential convergence rate. Subsequently, we exploit our theoretical framework to introduce novel regularized backup operators for MCTS based on the relative entropy of the policy update and, more importantly, on the Tsallis entropy of the policy, for which we prove superior theoretical guarantees. Afterward, we empirically verify the consequence of our theoretical results on a toy problem. Eventually, we show how our framework can easily be incorporated in AlphaGo, and we empirically show the superiority of convex regularization, w.r.t. representative baselines, on well-known RL problems across several Atari games.

Next, we take a further step to draw the connection between the two methods, Power-UCT and the convex regularization in MCTS, providing a rigorous theoretical study on the effectiveness of α-divergence in online Monte-Carlo planning. We show how the two methods can be related by using α-divergence. We additionally provide an in-depth study on the range of α parameter that helps to trade-off between exploration-exploitation in MCTS, hence showing how α-divergence can achieve state-of-the-art results in complex tasks.

Finally, we investigate a novel algorithmic formulation of the popular MCTS algorithm for robot path planning. Notably, we study Monte-Carlo Path Planning (MCPP) by analyzing and proving, on the one part, its exponential convergence rate to the optimal path in fully observable MDPs, and on the other part, its probabilistic completeness for finding feasible paths in POMDPs (proof sketch) assuming limited distance observability. Our algorithmic contribution allows us to employ recently proposed variants of MCTS with different exploration strategies for robot path planning. Our experimental evaluations in simulated 2D and 3D environments with a 7 degrees of freedom (DOF) manipulator and in a real-world robot path planning task demonstrate the superiority of MCPP in POMDP tasks.

In summary, this thesis proposes and analyses novel value backup operators and policy selection strategies both in terms of theoretical and experimental perspectives to help cope with sample efficiency and exploration-exploitation trade-off problems in MCTS and bring these advanced methods to robot path planning, showing the superiority in POMDPs w.r.t the state-of-the-art methods.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Künstliche intelligente Agenten, die sich wie Menschen verhalten, sind in den letzten Jahren zu einem bestimmenden Thema und einem der Hauptziele geworden, die die rasante Entwicklung des Deep Learning, insbesondere des Reinforcement Learning (RL), vorantreiben. Monte-Carlo Tree Search (MCTS) ist eine Klasse von Methoden zur Lösung komplexer Entscheidungsprobleme durch die Synergie von Monte-Carlo-Planung und Reinforcement Learning (RL). MCTS hat beeindruckende Ergebnisse bei Go (AlphaGo), Schach (AlphaZero) oder Videospielen erzielt und wurde auch bei der Bewegungsplanung, dem autonomen Fahren von Autos und der autonomen Montage von Robotern erfolgreich eingesetzt. Viele der MCTS-Erfolge beruhen auf der Kopplung von MCTS mit neuronalen Netzen, die mit RL-Methoden wie Deep Q-Learning trainiert werden, um das Lernen von großen Problemen zu beschleunigen. Obwohl MCTS den neuesten Stand der Technik erreicht, erfordert die hochgradig kombinatorische Natur der Probleme, die üblicherweise mit MCTS behandelt werden, den Einsatz effizienter Strategien für die Navigation im Planungsbaum und schnell konvergierende Methoden für die Wertsicherung. Darüber hinaus erfordern große Probleme wie Go- und Schachspiele eine Sampling-Effizienz-Methode, um einen effektiven Planungsbaum zu erstellen, der für die fliegende Entscheidungsfindung entscheidend ist. Diese akuten Probleme sind besonders offensichtlich, vor allem bei den jüngsten Fortschritten, die MCTS mit tiefen neuronalen Netzen zur Funktionsannähe-rung kombinieren. Trotz der jüngsten Erfolge bei der Anwendung von MCTS zur Lösung verschiedener Aufgaben der autonomen Robotik sind die meisten Szenarien jedoch teilweise beobachtbar und erfordern eine fortschrittliche Planungsmethode in komplexen, unstrukturierten Umgebungen.

Diese Arbeit zielt darauf ab, die folgenden Fragen zu beantworten: Wie können Roboter unter hoch stochastischer Dynamik und partieller Beobachtbarkeit effizient planen? In den folgenden Abschnitten wird versucht, diese Frage zu beantworten: Zunächst schlagen wir eine neuartige Backup-Strategie vor, die den Power-Mittelwert-Operator verwendet, der einen Wert zwischen dem Durchschnitts- und dem Maximalwert berechnet. Wir nennen unseren neuen Ansatz Power-UCT. Wir analysieren unsere Methode theoretisch und geben Garantien für die Konvergenz zum Optimum. Schließlich demonstrieren wir empirisch die Effektivität unserer Methode in bekannten MDP- und POMDP-Benchmarks, die eine signifikante Verbesserung in Bezug auf die Stichprobeneffizienz und die Konvergenzge-schwindigkeit im Vergleich zu modernen Algorithmen zeigen.

Zweitens untersuchen wir eine effiziente Explorations-Ausnutzungs-Planungsstrategie, indem wir einen umfassenden theoretischen konvexen Regularisierungsrahmen in MCTS bereitstellen. Wir leiten die erste Regret-Analyse von regularisierten MCTS ab und zeigen, dass sie eine exponentielle Konvergenzrate garantiert. Anschließend nutzen wir unseren theoretischen Rahmen, um neuartige regularisierte Backup-Operatoren für MCTS einzu-führen, die auf der relativen Entropie der Politikaktualisierung und, was noch wichtiger ist, auf der Tsallis-Entropie der Politik basieren, für die wir überlegene theoretische Garantien beweisen. Anschließend verifizieren wir die Konsequenz unserer theoretischen Ergebnisse empirisch an einem Spielzeugproblem. Schließlich zeigen wir, wie unser Rahmenwerk leicht in AlphaGo integriert werden kann, und wir zeigen empirisch die Überlegenheit der konvexen Regularisierung im Vergleich zu repräsentativen Baselines bei bekannten RL-Problemen in mehreren Atari-Spielen.

In einem weiteren Schritt stellen wir die Verbindung zwischen den beiden Methoden, Power-UCT und der konvexen Regularisierung in MCTS, her und liefern eine rigorose theoretische Studie über die Effektivität der α-Divergenz in der Online Monte-Carlo Planung. Wir zeigen, wie die beiden Methoden durch die Verwendung der α-Divergenz miteinander verbunden werden können. Darüber hinaus bieten wir eine detaillierte Studie über den Bereich des α-Parameters, der dabei hilft, einen Kompromiss zwischen exploration-exploitation in MCTS zu finden, und zeigen somit, wie α-Divergenz in AlphaGo und AlphaZero integriert werden kann, um bei komplexen Aufgaben die besten Ergebnisse zu erzielen.

Schließlich untersuchen wir eine neuartige algorithmische Formulierung des beliebten MCTS-Algorithmus für die Roboterbahnplanung. Insbesondere untersuchen wir die Monte-Carlo-Pfadplanung (MCPP), indem wir zum einen ihre exponentielle Konvergenzrate zum optimalen Pfad in vollständig beobachtbaren MDPs analysieren und beweisen und zum anderen ihre probabilistische Vollständigkeit für das Finden machbarer Pfade in POMDPs (Beweisskizze) unter der Annahme begrenzter Beobachtbarkeit der Entfernung. Unser algorithmischer Beitrag ermöglicht es uns, kürzlich vorgeschlagene Varianten von MCTS mit verschiedenen Explorationsstrategien für die Roboterbahnplanung einzusetzen. Unsere experimentellen Auswertungen in simulierten 2D- und 3D-Umgebungen mit einem Manipulator mit 7 Freiheitsgraden (DOF) und in einer realen Roboter-Bahnplanungsaufgabe zeigen die Überlegenheit von MCPP in POMDP-Aufgaben.

Zusammenfassend lässt sich sagen, dass in dieser Arbeit neuartige Value-Backup-Operatoren und Policy-Selection-Strategien sowohl aus theoretischer als auch aus experimenteller Sicht vorgeschlagen und analysiert werden, um mit den Trade-Off-Problemen Stichproben-Effizienz und Exploration-Exploitation in MCTS zurechtzukommen und diese fortschrittlichen Methoden in die Roboterbahnplanung einzubringen.

Deutsch
Status: Verlagsversion
URN: urn:nbn:de:tuda-tuprints-229318
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Intelligente Autonome Systeme
Hinterlegungsdatum: 03 Feb 2023 13:15
Letzte Änderung: 15 Feb 2023 13:26
PPN:
Referenten: Peters, Prof. Jan ; Szepesvári, Prof. Csaba ; Pajarinen, Prof. Dr. Joni
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 22 September 2022
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen