National and Kapodistrian University of Athens
Mathematical properties of the Stochastic Approximation and the Multi-Armed Bandit problem
Abstract
dc:descriptionΠαρά το γεγονός ότι τα νευρωνικά δίκτυα χρησιμοποιούνταν επί δεκαετίες με εντυπωσιακά αποτελέσματα, η ανάπτυξη ενός θεωρητικού υπόβαθρου που θα εξηγούσε αυτήν τους την επιτυχία είναι σχετικά πρόσφατο επίτευγμα. Στο Κεφάλαιο 2, παρουσιάζουμε τα κυριότερα αποτελέσματα που έδωσαν απάντηση σε αυτά τα ερωτήματα. Αποδεικνύουμε το θεώρημα του Cybenko, σύμφωνα με το οποίο κάθε συνεχής και σιγμοειδής συνάρτηση είναι καθολικός προσεγγιστής. Παρουσιάζουμε επίσης αρκετές επεκτάσεις του θεωρήματος αυτού. Το Κεφάλαιο 3 είναι αφιερωμένο στη μελέτη αλγορίθμων στοχαστικής προσέγγισης, οι οποίοι στοχεύουν στην εύρεση του σταθερού σημείου ενόςτελεστή, όταν οι ακριβείς τιμές που παίρνει δεν είναι γνωστές σε εμάς, αλλά μας αποκαλύπτονται με την παρουσία θορύβου. Παρουσιάζουμε επίσης την απόδειξη του αλγορίθμου της Q-Μάθησης, η οποία αποτελεί γενίκευση μιας μεθόδου που χρησιμοποιείται ευρέως στον κλασσικό δυναμικό προγραμματισμό, της μεθόδου των διαδοχικών προσεγγίσεων, για προβλήματα στα οποία δεν έχουμε γνώση των διαφόρων παραμέτρων (πιθανότητες μετάβασης και δομή κόστους), αλλά αντίθετα μπορούμε μόνο να προσομοιώνουμε παρατηρήσεις από αυτές. Τέλος, στο Κεφάλαιο 4, μελετάμε το πρόβλημα των multi-armed bandit, το αντικείμενο του οποίου είναι ο προσδιορισμός της πιο κερδοφόρας δράσης από ένα δοσμένο σύνολο, μαζί με την ταυτόχρονη μεγιστοποίηση του αναμενόμενου κέρδους μας σε βάθος χρόνου. Αποδεικνύουμε το φράγμα των Lai-Robbins, σύμφωνα με το οποίο για μια συγκεκριμένη κλάση κατανομών, υπάρχουν όρια στο πόσο γρήγορα μπορούμε να πλησιάσουμε το βέλτιστο κέρδος, ενώ επίσης παρουσιάζουμε και έναν αλγόριθμο που επιτυγχάνει το φράγμα αυτό. Ο αλγόριθμος των Lai-robbins περιέχει αρκετά σκοτεινά σημεία τα οποία προσπαθεί να απλοποιήσει η μέθοδος upper confidence bounds των Auer et al., με την οποία ολοκληρώνουμε την εργασία μας.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Σταμάτης Νικόλαος
- Stamatis Nikolaos
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:2944070