{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2944070"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2944070","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Mathematical properties of the Stochastic Approximation and the Multi-Armed Bandit problem","abstract":"Παρά το γεγονός ότι τα νευρωνικά δίκτυα χρησιμοποιούνταν επί δεκαετίες με εντυπωσιακά αποτελέσματα, η ανάπτυξη ενός θεωρητικού υπόβαθρου που θα εξηγούσε αυτήν τους την επιτυχία είναι σχετικά πρόσφατο επίτευγμα. Στο Κεφάλαιο 2, παρουσιάζουμε τα κυριότερα αποτελέσματα που έδωσαν απάντηση σε αυτά τα ερωτήματα. Αποδεικνύουμε το θεώρημα του Cybenko, σύμφωνα με το οποίο κάθε συνεχής και σιγμοειδής συνάρτηση είναι καθολικός προσεγγιστής. Παρουσιάζουμε επίσης αρκετές επεκτάσεις του θεωρήματος αυτού. Το Κεφάλαιο 3 είναι αφιερωμένο στη μελέτη αλγορίθμων στοχαστικής προσέγγισης, οι οποίοι στοχεύουν στην εύρεση του σταθερού σημείου ενόςτελεστή, όταν οι ακριβείς τιμές που παίρνει δεν είναι γνωστές σε εμάς, αλλά μας αποκαλύπτονται με την παρουσία θορύβου. Παρουσιάζουμε επίσης την απόδειξη του αλγορίθμου της Q-Μάθησης, η οποία αποτελεί γενίκευση μιας μεθόδου που χρησιμοποιείται ευρέως στον κλασσικό δυναμικό προγραμματισμό, της μεθόδου των διαδοχικών προσεγγίσεων, για προβλήματα στα οποία δεν έχουμε γνώση των διαφόρων παραμέτρων (πιθανότητες μετάβασης και δομή κόστους), αλλά αντίθετα μπορούμε μόνο να προσομοιώνουμε παρατηρήσεις από αυτές. Τέλος, στο Κεφάλαιο 4, μελετάμε το πρόβλημα των multi-armed bandit, το αντικείμενο του οποίου είναι ο προσδιορισμός της πιο κερδοφόρας δράσης από ένα δοσμένο σύνολο, μαζί με την ταυτόχρονη μεγιστοποίηση του αναμενόμενου κέρδους μας σε βάθος χρόνου. Αποδεικνύουμε το φράγμα των Lai-Robbins, σύμφωνα με το οποίο για μια συγκεκριμένη κλάση κατανομών, υπάρχουν όρια στο πόσο γρήγορα μπορούμε να πλησιάσουμε το βέλτιστο κέρδος, ενώ επίσης παρουσιάζουμε και έναν αλγόριθμο που επιτυγχάνει το φράγμα αυτό. Ο αλγόριθμος των Lai-robbins περιέχει αρκετά σκοτεινά σημεία τα οποία προσπαθεί να απλοποιήσει η μέθοδος upper confidence bounds των Auer et al., με την οποία ολοκληρώνουμε την εργασία μας.","abstract_html":"Παρά το γεγονός ότι τα νευρωνικά δίκτυα χρησιμοποιούνταν επί δεκαετίες με εντυπωσιακά αποτελέσματα, η ανάπτυξη ενός θεωρητικού υπόβαθρου που θα εξηγούσε αυτήν τους την επιτυχία είναι σχετικά πρόσφατο επίτευγμα. Στο Κεφάλαιο 2, παρουσιάζουμε τα κυριότερα αποτελέσματα που έδωσαν απάντηση σε αυτά τα ερωτήματα. Αποδεικνύουμε το θεώρημα του Cybenko, σύμφωνα με το οποίο κάθε συνεχής και σιγμοειδής συνάρτηση είναι καθολικός προσεγγιστής. Παρουσιάζουμε επίσης αρκετές επεκτάσεις του θεωρήματος αυτού. Το Κεφάλαιο 3 είναι αφιερωμένο στη μελέτη αλγορίθμων στοχαστικής προσέγγισης, οι οποίοι στοχεύουν στην εύρεση του σταθερού σημείου ενόςτελεστή, όταν οι ακριβείς τιμές που παίρνει δεν είναι γνωστές σε εμάς, αλλά μας αποκαλύπτονται με την παρουσία θορύβου. Παρουσιάζουμε επίσης την απόδειξη του αλγορίθμου της Q-Μάθησης, η οποία αποτελεί γενίκευση μιας μεθόδου που χρησιμοποιείται ευρέως στον κλασσικό δυναμικό προγραμματισμό, της μεθόδου των διαδοχικών προσεγγίσεων, για προβλήματα στα οποία δεν έχουμε γνώση των διαφόρων παραμέτρων (πιθανότητες μετάβασης και δομή κόστους), αλλά αντίθετα μπορούμε μόνο να προσομοιώνουμε παρατηρήσεις από αυτές. Τέλος, στο Κεφάλαιο 4, μελετάμε το πρόβλημα των multi-armed bandit, το αντικείμενο του οποίου είναι ο προσδιορισμός της πιο κερδοφόρας δράσης από ένα δοσμένο σύνολο, μαζί με την ταυτόχρονη μεγιστοποίηση του αναμενόμενου κέρδους μας σε βάθος χρόνου. Αποδεικνύουμε το φράγμα των Lai-Robbins, σύμφωνα με το οποίο για μια συγκεκριμένη κλάση κατανομών, υπάρχουν όρια στο πόσο γρήγορα μπορούμε να πλησιάσουμε το βέλτιστο κέρδος, ενώ επίσης παρουσιάζουμε και έναν αλγόριθμο που επιτυγχάνει το φράγμα αυτό. Ο αλγόριθμος των Lai-robbins περιέχει αρκετά σκοτεινά σημεία τα οποία προσπαθεί να απλοποιήσει η μέθοδος upper confidence bounds των Auer et al., με την οποία ολοκληρώνουμε την εργασία μας.","abstract_has_math":false,"creators":["Σταμάτης Νικόλαος","Stamatis Nikolaos"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021","date_published":"2021","updated_at":"2026-11-19T05:42:40Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2944070"],"render_values":[{"text":"uoadl:2944070","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2944070","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2944070","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A2944070","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Σταμάτης Νικόλαος","Stamatis Nikolaos"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2944070","https://pergamos.lib.uoa.gr/uoa/dl/object/2944070"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Παρά το γεγονός ότι τα νευρωνικά δίκτυα χρησιμοποιούνταν επί δεκαετίες με εντυπωσιακά αποτελέσματα, η ανάπτυξη ενός θεωρητικού υπόβαθρου που θα εξηγούσε αυτήν τους την επιτυχία είναι σχετικά πρόσφατο επίτευγμα. Στο Κεφάλαιο 2, παρουσιάζουμε τα κυριότερα αποτελέσματα που έδωσαν απάντηση σε αυτά τα ερωτήματα. Αποδεικνύουμε το θεώρημα του Cybenko, σύμφωνα με το οποίο κάθε συνεχής και σιγμοειδής συνάρτηση είναι καθολικός προσεγγιστής. Παρουσιάζουμε επίσης αρκετές επεκτάσεις του θεωρήματος αυτού. Το Κεφάλαιο 3 είναι αφιερωμένο στη μελέτη αλγορίθμων στοχαστικής προσέγγισης, οι οποίοι στοχεύουν στην εύρεση του σταθερού σημείου ενόςτελεστή, όταν οι ακριβείς τιμές που παίρνει δεν είναι γνωστές σε εμάς, αλλά μας αποκαλύπτονται με την παρουσία θορύβου. Παρουσιάζουμε επίσης την απόδειξη του αλγορίθμου της Q-Μάθησης, η οποία αποτελεί γενίκευση μιας μεθόδου που χρησιμοποιείται ευρέως στον κλασσικό δυναμικό προγραμματισμό, της μεθόδου των διαδοχικών προσεγγίσεων, για προβλήματα στα οποία δεν έχουμε γνώση των διαφόρων παραμέτρων (πιθανότητες μετάβασης και δομή κόστους), αλλά αντίθετα μπορούμε μόνο να προσομοιώνουμε παρατηρήσεις από αυτές. Τέλος, στο Κεφάλαιο 4, μελετάμε το πρόβλημα των multi-armed bandit, το αντικείμενο του οποίου είναι ο προσδιορισμός της πιο κερδοφόρας δράσης από ένα δοσμένο σύνολο, μαζί με την ταυτόχρονη μεγιστοποίηση του αναμενόμενου κέρδους μας σε βάθος χρόνου. Αποδεικνύουμε το φράγμα των Lai-Robbins, σύμφωνα με το οποίο για μια συγκεκριμένη κλάση κατανομών, υπάρχουν όρια στο πόσο γρήγορα μπορούμε να πλησιάσουμε το βέλτιστο κέρδος, ενώ επίσης παρουσιάζουμε και έναν αλγόριθμο που επιτυγχάνει το φράγμα αυτό. Ο αλγόριθμος των Lai-robbins περιέχει αρκετά σκοτεινά σημεία τα οποία προσπαθεί να απλοποιήσει η μέθοδος upper confidence bounds των Auer et al., με την οποία ολοκληρώνουμε την εργασία μας.","Despite the fact that neural networks had been used extensively for decades, a theoretical background that would explain their success was, until recently, elusive. In Chapter 2, we present the main results which settled this question, developed mostly in the early `90s. We prove Cybenko's theorem, which states that continuous and sigmoidal functions are always universal approximators, and we also study some extensions of this result. Chapter 3 is devoted to the study of stochastic approximation algorithms. The goal of these algorithms is to determine the fixed point of an operator when its values are not known to us, but they are revealed perturbed by some noise. We also present the proof of the convergence of the Q-Learning algorithm which is based on this theory. The Q-Learning algorithm is a generalization of the successive approximation method, a method used extensively in classical dynamic programming, when we have no prior information on the underlying process (transition probabilities and cost functions), but we can only draw and observe values from it. In the final chapter, we study the multi-armed bandit problem, a subfield of reinforcement learning, where the goal is to determine the most profitable action among a given set, while simultaneously, maximizing one's profit. We prove the Lai-Robbins lower bound, which shows that for a certain class of reward distributions there are limits to how fast one can reach a maximum profit, and we also present an algorithm that attains it. We conclude the chapter by studying the upper confidence bound algorithm, introduced by Auer et al., which resolves several issues of the Lai-Robbins approach."]},{"key":"dc:title","label":"Title","values":["Mathematical properties of the Stochastic Approximation and the Multi-Armed Bandit problem"]}]}],"canonical_facts":{"dc:creator":["Σταμάτης Νικόλαος","Stamatis Nikolaos"],"dc:date":["2021"],"dc:description":["Παρά το γεγονός ότι τα νευρωνικά δίκτυα χρησιμοποιούνταν επί δεκαετίες με εντυπωσιακά αποτελέσματα, η ανάπτυξη ενός θεωρητικού υπόβαθρου που θα εξηγούσε αυτήν τους την επιτυχία είναι σχετικά πρόσφατο επίτευγμα. Στο Κεφάλαιο 2, παρουσιάζουμε τα κυριότερα αποτελέσματα που έδωσαν απάντηση σε αυτά τα ερωτήματα. Αποδεικνύουμε το θεώρημα του Cybenko, σύμφωνα με το οποίο κάθε συνεχής και σιγμοειδής συνάρτηση είναι καθολικός προσεγγιστής. Παρουσιάζουμε επίσης αρκετές επεκτάσεις του θεωρήματος αυτού. Το Κεφάλαιο 3 είναι αφιερωμένο στη μελέτη αλγορίθμων στοχαστικής προσέγγισης, οι οποίοι στοχεύουν στην εύρεση του σταθερού σημείου ενόςτελεστή, όταν οι ακριβείς τιμές που παίρνει δεν είναι γνωστές σε εμάς, αλλά μας αποκαλύπτονται με την παρουσία θορύβου. Παρουσιάζουμε επίσης την απόδειξη του αλγορίθμου της Q-Μάθησης, η οποία αποτελεί γενίκευση μιας μεθόδου που χρησιμοποιείται ευρέως στον κλασσικό δυναμικό προγραμματισμό, της μεθόδου των διαδοχικών προσεγγίσεων, για προβλήματα στα οποία δεν έχουμε γνώση των διαφόρων παραμέτρων (πιθανότητες μετάβασης και δομή κόστους), αλλά αντίθετα μπορούμε μόνο να προσομοιώνουμε παρατηρήσεις από αυτές. Τέλος, στο Κεφάλαιο 4, μελετάμε το πρόβλημα των multi-armed bandit, το αντικείμενο του οποίου είναι ο προσδιορισμός της πιο κερδοφόρας δράσης από ένα δοσμένο σύνολο, μαζί με την ταυτόχρονη μεγιστοποίηση του αναμενόμενου κέρδους μας σε βάθος χρόνου. Αποδεικνύουμε το φράγμα των Lai-Robbins, σύμφωνα με το οποίο για μια συγκεκριμένη κλάση κατανομών, υπάρχουν όρια στο πόσο γρήγορα μπορούμε να πλησιάσουμε το βέλτιστο κέρδος, ενώ επίσης παρουσιάζουμε και έναν αλγόριθμο που επιτυγχάνει το φράγμα αυτό. Ο αλγόριθμος των Lai-robbins περιέχει αρκετά σκοτεινά σημεία τα οποία προσπαθεί να απλοποιήσει η μέθοδος upper confidence bounds των Auer et al., με την οποία ολοκληρώνουμε την εργασία μας.","Despite the fact that neural networks had been used extensively for decades, a theoretical background that would explain their success was, until recently, elusive. In Chapter 2, we present the main results which settled this question, developed mostly in the early `90s. We prove Cybenko's theorem, which states that continuous and sigmoidal functions are always universal approximators, and we also study some extensions of this result. Chapter 3 is devoted to the study of stochastic approximation algorithms. The goal of these algorithms is to determine the fixed point of an operator when its values are not known to us, but they are revealed perturbed by some noise. We also present the proof of the convergence of the Q-Learning algorithm which is based on this theory. The Q-Learning algorithm is a generalization of the successive approximation method, a method used extensively in classical dynamic programming, when we have no prior information on the underlying process (transition probabilities and cost functions), but we can only draw and observe values from it. In the final chapter, we study the multi-armed bandit problem, a subfield of reinforcement learning, where the goal is to determine the most profitable action among a given set, while simultaneously, maximizing one's profit. We prove the Lai-Robbins lower bound, which shows that for a certain class of reward distributions there are limits to how fast one can reach a maximum profit, and we also present an algorithm that attains it. We conclude the chapter by studying the upper confidence bound algorithm, introduced by Auer et al., which resolves several issues of the Lai-Robbins approach."],"dc:identifier":["uoadl:2944070","https://pergamos.lib.uoa.gr/uoa/dl/object/2944070"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Mathematical properties of the Stochastic Approximation and the Multi-Armed Bandit problem"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:42:40Z"}