Αξιοποίηση Εκτιμήσεων Διασποράς σε Στοχαστικά MAB Προβλήματα με Αλλοιωμένες Ανταμοιβές

Abstract

Στην παρούσα διπλωματική εργασία μελετάμε το πρόβλημα των Multi Armed Bandits (MAB), το οποίο αφορά την άμεση μάθηση σε περιβάλλοντα περιορισμένης ανάδρασης. Το πρώτο μέρος της διπλωματικής αφορά τη στοχαστική μορφή του προβλήματος. Διάφοροι αλγόριθμοι έχουν προταθεί και μελετηθεί για αυτό το πρόβλημα, μερικοί πιο απλοί και ’μη προσαρμοστικοί’, ενώ άλλοι πιο ισχυροί, αλλά πιο περίτεχνοι. Μελετάμε τους σημαντικότερους από αυτούς και αναλύουμε την απόδοση τους μέσω της μετρικής της ’μετάνοιας’ (regret), αποδεικνύοντας εγγύησεις με υψηλή πιθανότητα (high probability regret guarantees). Ακόμα, μελετάμε τον αλγόριθμο UCBV που εκτιμάει πέρα από τη μέση τιμή και την διασπορά κάθε ενέργειας. Αυτό οδηγεί σε βελτιωμένη εγγύηση όταν οι ενέργειες είναι πιο στατικές, παράλληλα εξασφαλίζοντας την εγγύηση των σχεδόν βέλτιστων αλγορίθμων που διατηρούν μόνο εκτιμήσεις μέσης τιμής. Ταυτόχρονα, αποδεικνύουμε αυτό το αποτέλεσμα με μια σημαντικά απλούστερη ανάλυση από αυτή στην αρχική δημοσίευση. Στο δεύτερο μέρος μελετάμε το πρόβλημα των ανταγωνιστικών MAB (Adversarial MAB), όπου δεν κάνουμε καμία στατιστική υπόθεση. Αρχικά μελετάμε το πρόβλημα του Online Learning για να κατανοήσουμε στην πορεία τον ευρέως γνωστό αλγόριθμο Exp3. Στη συνέχεια εστιάζουμε στο πρόβλημα των Στοχαστικών MAB υπό ανταγωνιστικές αλλοιώσεις (Adversarially Corrupted MABs). Σε αυτό το πρόβλημα το υποκείμενο περιβάλλον είναι στοχαστικό, αλλά κάποιος ανταγωνιστής μπορεί να αλλοιώσει τις ανταμοιβές πριν παρατηρηθούν. O πρώτος αλγόριθμος που μελετάμε σε αυτό το πρόβλημα εξασφαλίζει σχεδόν βέλτιστη εγγυήση μετάνοιας στο αμιγώς στοχαστικό περιβάλλον η οποία μεταβάλλεται ομαλά με την αύξηση της σωρευτικής αλλοίωσης. Ακόμη, μελετάμε τον αλγόριθμο BARBAR ο οποίος επιτυγχάνει σημαντικά καλύτερη εγγύηση. Τέλος, βασισμένοι σε αυτόν παρουσιάζουμε έναν αλγόριθμο ο οποίος χρησιμοποιεί επιπλέον εκτιμήσεις διασποράς των ανταμοιβών, σε μια προσπάθεια να επιτύγχουμε μετάνοια η οποία μεταβάλλεται ομαλά από αυτό που εξασφαλίζει ο UCBV σε στοχαστικό περιβάλλον. Πράγματι, αποδεικνύουμε ότι ο αλγόριθμος μας εξασφαλίζει σχεδόν όμοια εγγύηση μετάνοιας σε αμιγώς στοχαστικό περιβάλλον, αλλά ένα παράδειγμα οικογενειών στιγμιοτύπων δείχνει ότι ο αλγόριθμος στην τωρινή μορφή του δεν μπορεί να επιτύχει τα επιθυμητά αποτελέσματα.