Ανάπτυξη Αποδοτικών Αλγορίθμων για Markov Decision Processes

Abstract

Οι Διαδικασίες Αποφάσεων Markov (Markov Decision Processes ή MDP για συντομία) αποτελούν ένα από τα σημαντικότερα εργαλεία επίλυσης προβλημάτων αποφάσεων υπό αβεβαιότητα την σήμερον ημέρα. Χρησιμοποιούνται κατά κόρον σε σύγχρονες εφαρμογές, ιδιαίτερα σε αυτές που αφορούν Ενισχυτική Μάθηση. Σε αυτά, ένας παίκτης καλείται να λάβει αποφάσεις οι οποίες προκαλούν μεταβολές στο περιβάλλον του ενώ επιπλέον του αποδίδουν μια ανταμοιβή-κίνητρο, προκειμένου να μεγιστοποιήσει αυτήν την ανταμοιβή. Αναλόγως με το αν ο αριθμός των αποφάσεων που καλείται να κάνει ο πράκτορας είναι πεπερασμένος ή άπειρος, το MDP χαρακτηρίζεται ως Πεπερασμένου ή Απείρου Ορίζοντα. Τα MDP Πεπερασμένου Ορίζοντα επιλέγονται σε αρκετές εφαρμογές έναντι του Απείρου, εφόσον αντικατοπτρίζουν καλύτερα προβλήματα του πραγματικού κόσμου, τα οποία εξ ορισμού κάποτε θα ολοκληρωθούν, όπως σε προβλήματα διαχείρισης πόρων. Εντούτοις, ένα σημαντικό πρόβλημα που εμφανίζουν έγκειται στην μνήμη που καταλαμβάνει η λύση που υπολογίζεται, ιδιαίτερα σε περιπτώσεις όπου ο αλγόριθμος εκτελείται σε συσκευές περιορισμένων δυνατοτήτων υλικού, όπως κινητά ή tablets. Στην παρούσα εργασία προτείνονται δυο νέες μέθοδοι που αντιμετωπίζουν το πρόβλημα μνήμης των MDP Πεπερασμένου Ορίζοντα. Οι μέθοδοι αυτές επιλέγουν να αποθηκεύουν στη μνήμη ένα μέρος της λύσης και στη συνέχεια να χρησιμοποιούν αυτό για επανυπολογισμό της υπόλοιπης, ανάλογα με τις εκάστοτε ανάγκες. Η πρώτη, που ονομάζεται Λύση Ρίζας, απαιτεί σημαντικά λιγότερη μνήμη και σχεδόν ίδιο χρόνο εκτέλεσης με την επικρατέστερη μέθοδο που χρησιμοποιείται ως τώρα για επίλυση MDP. Η δεύτερη λύση (Λογαριθμική Λύση) αποθηκεύει ακόμη μικρότερο μέρος της λύσης στη μνήμη (σχεδόν μηδαμινό), με μια μικρή επιβάρυνση χρόνου. Τα παραπάνω συμπεράσματα, αφού θεμελιώθηκαν πρωτίστως θεωρητικά, επιβεβαιώθηκαν και πειραματικά, σε ήδη υπάρχοντα, προσαρμοσμένα στις ανάγκες, τεχνητά δεδομένα που αφορούν διαχείριση πόρων συστάδων υπολογιστών, τόσο για τον χρόνο εκτέλεσης των αλγορίθμων όσο και για την μνήμη που καταλαμβάνουν. Επιπλέον, συγκρίθηκαν τόσο με ήδη υπάρχοντες μεθόδους καθώς και με προσεγγιστικές μεθόδους επίλυσης. Η συνεισφορά μας μέσω αυτής της εργασίας έγκειται στο γεγονός πως, με την πρόταση αυτών των νέων αλγορίθμων, ο χρήστης που αξιοποιεί MDP στην εκάστοτε εφαρμογή έχει την δυνατότητα να επιλέξει την λύση-αλγόριθμο που εξυπηρετεί όσο το δυνατόν καλύτερα τις ανάγκες του, αναλόγως με το σύστημα που διαθέτει. Τέλος, έγινε προσπάθεια βελτιστοποίησης του χρόνου εκτέλεσης του βασικού επαναληπτικού αλγορίθμου επίλυσης MDP Απείρου Ορίζοντα (Value Iteration) με χρήση φραγμάτων ώστε να μειωθεί ο χρόνος σύγκλισης. Εντούτοις, οι προσπάθειες ήταν ανεπιτυχείς, πιθανώς εξαιτίας της εφαρμογής που επιλέχθηκε για αξιολόγηση.