Machine learning for intelligent agents

Abstract

This dissertation studies the problem of developing intelligent agents, which are able to acquire skills in an autonomous way, simulating human behaviour. An autonomous intelligent agent acts effectively in an unknown environment, directing its activity towards achieving a specific goal based on some performance measure. Through this interaction, a rich amount of information is received, which allows the agent to perceive the consequences of its actions, identify important behavioural components, and adapt its behaviour through learning. In this direction, the present dissertation concerns the development, implementation and evaluation of machine learning techniques for building intelligent agents. Three important and very challenging tasks are considered: i) approximate reinforcement learning, where the agent's policy is evaluated and improved through the approximation of the value function, ii) Bayesian reinforcement learning, where the reinforcement learning problem is modeled as a decision-theoretic problem, by placing a prior distribution over Markov Decision Processes (MDPs) that encodes the agent's belief about the true environment, and iii) Development of intelligent agents on games, which constitute a really challenging platform for developing machine learning methodologies, involving a number of issues that should be resolved, such as the appropriate choice of state representation, continuous action spaces, etc..In the first part, we focus on the problem of value function approximation suggesting two different methodologies. Firstly, we propose the Relevance Vector Machine Temporal Difference (RVMTD) algorithm, which constitutes an advanced kernelized Bayesian methodology for model-free value function approximation, employing the RVM regression framework as a generative model. The key aspect of RVMTD is the restructure of the policy evaluation problem as a linear regression problem. An online kernel sparsification technique is adopted, rendering the RVMTD practical in large scale domains. Based on this scheme, we derive recursive low-complexity formulas for the online update of the model observations. For the estimation of the unknown model coefficients a sparse Bayesian methodology is adopted that enhances model capabilities. Secondly, a model-based reinforcement learning algorithm is proposed, which is based on the online partitioning of the input space into clusters. As the data arrive sequentially to the learner, an online extension of the vanilla EM algorithm is used for clustering. In this way, a number of basis functions are created and updated automatically. Also, statistics are kept about the dynamics of the environment that are subsequently used for policy evaluation. Finally, the least-squares solution is used for the estimation of the unknown coefficients of the value function model.In the second part, we address the Bayesian reinforcement learning problem proposing two advanced Bayesian algorithms. Firstly, we present the Linear Bayesian Reinforcement Learning (LBRL) algorithm showing that the system dynamics can be estimated accurately by a Bayesian linear Gaussian model, which takes into account correlations in the state features. Policies are estimated by applying approximate dynamic programming on a transition model that is sampled from the current posterior. This form of approximate Thompson sampling results in a good exploration in unknown MDPs. Secondly, the Cover Tree Bayesian Reinforcement Learning (CTBRL) algorithm is proposed which constitutes an online tree-based Bayesian approach for reinforcement learning. The main idea of CTBRL is the construction of a cover tree from the observations, which remains efficient in high dimensional spaces. In this way, we create a set of partitions of the state space. An efficient non-parametric Bayesian conditional density estimator is also introduced on the cover tree structure.This is a generalized context tree, endowed with a multivariate linear Bayesian model at each node and is used for the estimation of the dynamics of the underlying environment. Thus, taking a sample for the posterior, we obtain a piecewise linear Gaussian model of the dynamics. The main advantages of this approach are its flexibility and efficiency, rendering it suitable for reinforcement learning problems in continuous state spaces. In the third part of this thesis, we consider the problem of developing intelligent agents in two challenging games, the Ms.PacMan and the AngryBirds. Firstly, we propose the RL-PacMan agent, which is based on an abstract but informative state space representation. The adopted representation is able to encode a game scene, giving the opportunity to our agent to distinguish different situations. For discovering a good or even optimal policy, we use the model-free SARSA(ι) reinforcement learning algorithm. In our study, we demonstrate that an efficient state representation is of central interest for the design of an intelligent agent. Finally, we propose the AngryBER agent, which is based on an efficient tree structure for representing each game screenshot. This representation has the advantage of establishing an informative feature space and modifying the task of game playing to a regression problem. A Bayesian ensemble regression framework is used for the estimation of the return of each action, where each pair of ‘object material' and ‘bird type' has its own regression model. After each shot, the regression model is incrementally updated, in a fully closed form.The AngryBER agent participated in the international AIBIRDS 2014 competition winning the 2nd price among 12 participants.

Η παρούσα διατριβή πραγματεύεται το πρόβλημα της ανάπτυξης ευφυών πρακτόρων, οι οποίοι έχουν την ικανότητα να αποκτούν δεξιότητες αυτόνομα. Ένας ευφυής πράκτορας δρα σε ένα άγνωστο περιβάλλον, κατευθυνόμενος προς την επίτευξη ενός συγκεκριμένου στόχου. Μέσω της αλληλεπίδρασης του με το περιβάλλον, ο πράκτορας λαμβάνει ένα τεράστιο όγκο πληροφοριών, που του δίνει τη δυνατότητα να αντιλαμβάνεται της συνέπειες των ενεργειών του, προσαρμόζοντας ανάλογα τη συμπεριφορά του. Στο πλαίσιο αυτό, η διατριβή επικεντρώνεται στην παρουσίαση μεθόδων Μηχανικής Μάθησης για την ανάπτυξη ευφυών πρακτόρων, εστιάζοντας σε τρεις βασικούς θεματικούς άξονες: α) προσεγγιστική ενισχυτική μάθηση, όπου η πολιτική του πράκτορα εκτιμάται και βελτιώνεται μέσω της προσέγγισης της συνάρτησης αξίας (Value Function), β) Μπεϋζιανή ενισχυτική μάθηση, όπου το πρόβλημα της ενισχυτικής μάθησης μοντελοποιείται ως ένα θεωρητικό πρόβλημα απόφασης, τοποθετώντας μια εκ των προτέρων κατανομή στο σύνολο των πιθανών Μαρκοβιανών Διαδικασιών Απόφασης (ΜΔΑ), και γ) Τεχνητή Νοημοσύνη σε Παίγνια, τα οποία αποτελούν δελεαστικά προβλήματα για την ανάπτυξη και μελέτη μεθοδολογιών μηχανικής μάθησης.Το πρώτο μέρος της διατριβής εστιάζει στο πρόβλημα της προσέγγισης της συνάρτησης αξίας, παρουσιάζοντας δυο διαφορετικές μεθοδολογίες. Αρχικά, προτείνουμε τη μέθοδο Relevance Vector Machine Temporal Difference (RVMTD), η οποία αποτελεί μια προηγμένη Μπεϋζιανή μεθοδολογία πυρήνων για την προσέγγιση της συνάρτησης αξίας, εφαρμόζοντας το μοντέλο παλινδρόμησης RVM. Η βασική ιδέα της προτεινόμενης μεθόδου είναι ο μετασχηματισμός του προβλήματος της εκτίμησης μιας πολιτικής σε ένα πρόβλημα παλινδρόμησης. Προκειμένου ο αλγόριθμος RVMTD να καταστεί εφαρμόσιμος σε προβλήματα μεγάλης κλίμακας, υιοθετήσαμε μια τεχνική αραιών πυρήνων πραγματικού χρόνου. Βασιζόμενοι στη συγκεκριμένη τεχνική, εξάγουμε αναδρομικούς κανόνες ενημέρωσης, χαμηλής πολυπλοκότητας, που επιτρέπουν την ανανέωση των παρατηρήσεων του μοντέλου μας σε πραγματικό χρόνο. Για την εκτίμηση των άγνωστων συντελεστών του μοντέλου, υιοθετήσαμε μια αραιή Μπεϋζιανή μεθοδολογία η οποία βελτιώνει την γενικευτική ικανότητα του μοντέλου. Στη συνέχεια, προτείνουμε έναν αλγόριθμο ενισχυτικής μάθησης, ο οποίος βασίζεται στο μοντέλο του περιβάλλοντος, διαχωρίζοντας σε πραγματικό χρόνο τον χώρο εισόδου σε ομάδες (clusters). Καθώς στο πρόβλημα της ενισχυτικής μάθησης τα δεδομένα καταφθάνουν με σειριακό τρόπο, για το πρόβλημα της ομαδοποίησης χρησιμοποιήσαμε μια εκδοχή πραγματικού χρόνου του βασικού αλγορίθμου EM. Με αυτόν τον τρόπο, επιτυγχάνουμε τη αυτόματη δημιουργία και ενημέρωση ένας συνόλου συναρτήσεων βάσης, που χρησιμοποιείται στο πρόβλημα της προσέγγισης της συνάρτησης αξίας. Τέλος, για την εκτίμηση των αγνώστων παραμέτρων του μοντέλου της συνάρτησης αξίας χρησιμοποιήσαμε τη μέθοδο των ελαχίστων τετραγώνων (least-squares solution).Το δεύτερο μέρος της διατριβής αντιμετωπίζει το πρόβλημα της Μπεϋζιανης ενισχυτικής μάθησης, όπου προτείνονται δύο καινοτόμες μεθοδολογίες. Πρώτα, παρουσιάζεται ο αλγόριθμος Linear Bayesian Reinforcement Learning (LBRL), ο οποίος θεμελιώνει την παρατήρηση ότι ένα Μπεϋζιανό γραμμικό (Γκαουσιανό) μοντέλο είναι σε θέση να προσεγγίζει με μεγάλη ακρίβεια την δυναμική του μοντέλου του περιβάλλοντος. Οι πολιτικές εκτιμώνται εφαρμόζοντας προσεγγιστικό δυναμικό προγραμματισμό (approximate dynamic programming) στο μοντέλο μετάβασης το όποιο έχει εξαχθεί από την εκ των υστέρων κατανομή. Η συγκεκριμένη προσεγγιστική τεχνική είναι γνωστή ως δειγματοληψία Thompson και προωθεί την εξερεύνηση αγνώστων περιβαλλόντων. Στη συνέχεια, προτείνεται ο αλγόριθμος Cover Tree Bayesian Reinforcement Learning (CTBRL), ο οποίος αποτελεί μια πραγματικού χρόνου Μπεϋζιανή προσέγγιση ενισχυτικής μάθησης βασιζόμενη σε μία δενδρική δομή. Η βασική ιδέα του αλγορίθμου CTBRL είναι η κατασκευή δένδρων κάλυψης (cover trees) με βάση τις παρατηρήσεις του περιβάλλοντος, τα οποία παραμένουν αποδοτικά σε χώρους υψηλής διάστασης και χρησιμοποιούνται για την εκτίμηση της δυναμικής του προς εξέταση περιβάλλοντος. Παίρνοντας ένα δείγμα από την εκ των υστέρων κατανομή, λαμβάνουμε ένα τμηματικά, γραμμικό (piecewise linear) Γκαουσιανό μοντέλο της δυναμικής του περιβάλλοντος. Όπως και στην περίπτωση του αλγορίθμου LBRL, συνδυάζουμε τη δειγματοληψία (Thompson) με τον προσεγγιστικό δυναμικό προγραμματισμό, λαμβάνοντας αποδοτικές πολιτικές σε άγνωστα περιβάλλοντα. Τα κύρια πλεονεκτήματα της συγκεκριμένης μεθόδου είναι η αποδοτικότητά της καθώς επίσης και η ευελιξία της, καθιστώντας την κατάλληλη για προβλήματα ενισχυτικής μάθησης με συνεχείς χώρους καταστάσεων.Το τρίτο και τελευταίο μέρος της παρούσας διατριβής, επικεντρώνεται στο πρόβλημα της ανάπτυξης ευφυών πρακτόρων για δύο δελεαστικά και συνάμα υψηλών απαιτήσεων παίγνια, το Ms. PacMan και AngryBirds. Αρχικά, προτείνουμε τον πράκτορα RL-PacMan, ο οποίος βασίζεται σε μια περιγραφική και ταυτόχρονα περιεκτική αναπαράσταση του χώρου καταστάσεων. Η προτεινόμενη αναπαράσταση κωδικοποιεί την σκηνή του παιχνιδιού με τέτοιο τρόπο έτσι ώστε να δίνεται η δυνατότητα στο πράκτορα να διακρίνει και να αντιμετωπίσει διαφορετικές καταστάσεις. Για την εξεύρεση μίας καλής πολιτικής, χρησιμοποιήσαμε τον αλγόριθμο ενισχυτικής μάθησης SARSA(λ). Η συγκεκριμένη μελέτη, επιδεικνύει ότι η σχεδίαση μιας αποδοτικής αναπαράστασης είναι σημαντική για την ανάπτυξη ενός αποδοτικού πράκτορα. Τέλος, προτείνουμε τον αλγόριθμο AngryBER ο οποίος βασίζεται σε μια αποδοτική δενδρική δομή για την αναπαράσταση της σκηνής του παιχνιδιού. Η συγκεκριμένη δομή έχει το πλεονέκτημα της εξαγωγής πληροφοριακών χαρακτηριστικών και μετατρέπει το πρόβλημα της επίλυσης του παιχνιδιού σε ένα πρόβλημα παλινδρόμησης. Πιο συγκεκριμένα, χρησιμοποιούμε ένα σύνολο από Μπεϋζιανούς παλινδρομητές για την πρόβλεψη της ανταμοιβής μίας ενέργειας, όπου κάθε ζεύγος ''υλικό κατασκευής αντικειμένου'' και ''τύπος πουλιού'' έχουν το δικό τους μοντέλο παλινδρόμησης. Μετά το πέρας κάθε βολής, το αντίστοιχο μοντέλο παλινδρόμησης ενημερώνεται επαυξητικά, σε κλειστή μορφή. Ο πράκτορας AngryBER έλαβε μέρος στον παγκόσμιο διαγωνισμό AIBIRDS 2014, τερματίζοντας στη 2η θέση μεταξύ των 12 συμμετεχόντων.