Μηχανισμοί ενισχυτικής μάθησης και εξελικτικής υπολογιστικής για αυτόνομους πράκτορες

Abstract

The ultimate goal of artificial intelligence is the creation of fully autonomous systems, which will be able to learn, reason, evolve and function in the real world. Such systems are usually referred to as autonomous agents. One of the most appropriate paradigms for creating autonomous agents is that of reinforcement learning. In reinforcement learning problems the goal is to find a policy, a mapping of states to actions, without examples of correct behavior, but only with positive or negative rewards based on the goal the agent is trying to achieve. The optimal policy maximizes the long-term reward of the agent. One of the main ingredients of a reinforcement learning system is the value function, a function that estimates the long-term expected reward for every state or state-action pair. For small-scale problems it can take the form of an array. For larger problems though, the function needs to be represented by a function approximator in parametric form. The reason is the generalization capabilities of the approximator, which will help the agent take correct actions for states that has not encountered before. The goal of the dissertation is the autonomous adaptation of function approximators with the use of reinforcement learning and evolutionary computing. The algorithm will adapt the parameters of the function approximator to the problem at hand with little or no human input. The name of the method developed is NEAR (NeuroEvolution of Augmented Reservoirs) and uses three basic ideas: a) Echo state networks (ESN), as function approximators, a model of reservoir computing with recursive nature and capabilities of linear learning rules and modeling non-linear environments and non-Markovian state signals, b) ΝΕΑΤ (NeuroEvolution of Augmented Topologies) methodology as a meta-search algorithm, adapted to evolve ESNs and c) evolution coupled with learning with the goal of evolving ESNs that are better able to learn. Evolution performs global-search in the space of parameters, while learning performs local-search for the final tweaking of parameters towards the global optimum. Moreover, a transfer learning procedure was tested in order to transfer knowledge in the form of reservoirs, developed in a source task to a similar target task, with the goal to improve the performance and speed of learning in the target task. The NEAR method was tested on ten (10) different reinforcement learning testbeds and four (4) time-series prediction problems in a supervised learning mode. NEAR was compared against state-of-the-art algorithms and was found superior in most of the testbeds. In addition, ESNs and NEAR were tested in three more demanding problems: in the bidding mechanisms of trading agents for supply chain management and advertisement auctions and as a mixed strategy model in the game of Poker.

Απώτερος στόχος της τεχνητής νοημοσύνης είναι η δημιουργία πλήρως αυτόνομων συστημάτων, τα οποία θα μαθαίνουν, θα συλλογίζονται, θα εξελίσσονται και θα λειτουργούν στον πραγματικό κόσμο. Τα συστήματα αυτά, συχνά αναφέρονται με τον όρο αυτόνομοι πράκτορες. Μία από τις πλέον κατάλληλες προσεγγίσεις για τη δημιουργία αυτόνομων πρακτόρων είναι αυτή της ενισχυτικής μάθησης. Οι αλγόριθμοι ενισχυτικής μάθησης είναι μία κλάση τεχνικών με σκοπό την εύρεση μίας πολιτικής, δηλαδή της αντιστοίχησης των ενεργειών ενός πράκτορα με τις καταστάσεις του, χωρίς παραδείγματα βέλτιστης συμπεριφοράς, παρά μόνο θετικές ή αρνητικές ανταμοιβές για τις ενέργειές του, ανάλογες του στόχου που θέλει να επιτύχει. Η βέλτιστη πολιτική θα πρέπει να μεγιστοποιεί την επιβράβευση του αυτόνομου πράκτορα σε βάθος χρόνου. Ένα από τα κύρια συστατικά ενός αλγορίθμου ενισχυτικής μάθησης είναι η συνάρτηση αξίας, η οποία συσχετίζει καταστάσεις ή ζεύγη καταστάσεων-ενεργειών με μία τιμή, που καθορίζει την μακροπρόθεσμη αξία τους για τον πράκτορα. Για μικρά προβλήματα μπορεί να πάρει τη μορφή ενός απλού πίνακα. Πρόθεση της παρούσας διατριβής είναι η δημιουργία πολιτικών για αυτόνομους πράκτορες σε πραγματικά και σύνθετα προβλήματα, με εξαιρετικά μεγάλο αριθμό καταστάσεων. Σε τέτοιου είδους εφαρμογές, κρίνεται συνήθως αναγκαία η παρουσία μίας συνάρτησης σε παραμετρική μορφή, η οποία θα προσπαθεί να προσεγγίσει τη συνάρτηση αξίας και να γενικεύσει από τα ζεύγη καταστάσεων-ενεργειών που έχει συναντήσει στο παρελθόν, ώστε να βοηθήσει τον πράκτορα να λάβει τις σωστές αποφάσεις και για καταστάσεις που δεν έχει αντιμετωπίσει προηγουμένως. Στόχος της διατριβής είναι η αυτόνομη προσαρμογή συναρτήσεων προσέγγισης με τη χρήση τεχνικών ενισχυτικής μάθησης και εξελικτικής υπολογιστικής. Η προσαρμογή τους πραγματοποιείται ανάλογα με το πρόβλημα, χωρίς να απαιτείται πρότερη λήψη αποφάσεων ως προς το σχεδιασμό τους. Η βασική μέθοδος που αναπτύχθηκε, η NEAR (NeuroEvolution of Augmented Reservoirs), χρησιμοποιεί τρία βασικά συστατικά: α) τα δίκτυα ηχωικών καταστάσεων (ΔΗΚ), ως υπολογιστικό μοντέλο για τις συναρτήσεις προσέγγισης, τα οποία είναι νευρωνικά δίκτυα με αναδράσεις και γραμμικό τρόπο εκμάθησης βαρών, έτσι ώστε να μπορούν να μοντελοποιήσουν και πολιτικές σε μη-γραμμικά περιβάλλοντα, με μη-Μαρκοβιανά σήματα κατάστασης, δηλαδή σε περιβάλλοντα όπου είναι απαραίτητη η ύπαρξη μνήμης, β) τη ΝΕΑΤ (NeuroEvolution of Augmented Topologies), ως μέθοδος μετα-αναζήτησης τοπολογιών και βαρών νευρωνικών δικτύων, προσαρμοσμένη στις ανάγκες των ΔΗΚ, για την εξέλιξη των τοπολογιών των ΔΗΚ και γ) το συνδυασμό εξέλιξης και μάθησης, με απώτερο στόχο την εξέλιξη τοπολογίων ΔΗΚ με αλγορίθμους φυσικής επιλογής, στα οποία η μάθηση είναι πιο αποδοτική. Η εξέλιξη αναζητά στο συνολικό διάστημα των παραμέτρων και αποτελεί τη μακροσκοπική προσέγγιση στο πρόβλημα, ενώ η μάθηση κάνει τοπική βελτιστοποίηση και στοχεύει στη μικροσκοπική βελτίωση του μοντέλου. Πέρα από τη NEAR, αναπτύχθηκε και η επέκτασή του ως προς τεχνικές μεταφοράς μάθησης. Η διαδικασία μεταφοράς μάθησης μεταφέρει τη γνώση που αποκτιέται σε ένα πρόβλημα, το πηγαίο πρόβλημα (source task), σε ένα άλλο, παρόμοιο, το πρόβλημα στόχου (target task). Σκοπός είναι η βελτίωση της επίδοσης και της ταχύτητας μάθησης του πράκτορα στο τελικό πρόβλημα. Στη μεθοδολογία μεταφοράς μάθησης που αναπτύχθηκε στα πλαίσια της διατριβής, μεταφέρονται τοπολογίες δικτύων που βρέθηκαν στο πηγαίο πρόβλημα ως εμπειρία προς χρήση στο πρόβλημα στόχο. Η μέθοδος NEAR αξιολογήθηκε σε δέκα (10) διαφορετικές παραλλαγές προβλημάτων ενισχυτικής μάθησης, σε πρόβλεψη τριών (3) προβλημάτων χρονοσειρών δυναμικών συστημάτων και μίας (1) χρονοσειράς ενεργειακού ενδιαφέροντος σε λειτουργία επιβλεπόμενης μάθησης. Από τη σύγκρισή του με ανταγωνιστικούς αλγορίθμους προκύπτει η επικράτηση της NEAR στα περισσότερα από τα παραπάνω προβλήματα. Στη συνέχεια, ΔΗΚ, υπό το πρίσμα της ενισχυτικής μάθησης, χρησιμοποιήθηκαν ως στοιχεία στρατηγικής σε έναν πράκτορα εμπορίου για τη διαχείριση της εφοδιαστικής αλυσίδας, ως στοιχεία μηχανισμού πλειοδοσίας πράκτορα εμπορίου για τη διαχείριση διαδικτυακής διαφημιστικής καμπάνιας, καθώς και ως μοντέλα μικτής στρατηγικής σε πράκτορα για το παιχνίδι του Πόκερ.