Ημερολόγιο Εκδηλώσεων

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

Αποστόλου Τσάμπουρα

με θέμα

Προσεγγιστικοί Αλγόριθμοι Ενισχυτικής Μάθησης για Φιλικές προς το Δίκτυο Συστάσεις

Approximate Reinforcement Learning Algorithms for Network-Friendly Recommendations

Εξεταστική Επιτροπή
Καθηγητής Θρασύβουλος Σπυρόπουλος (επιβλέπων)
Καθηγητής Άγγελος Μπλέτσας
Καθηγητής Μιχαήλ Λαγουδάκης 

Περίληψη
Ο έλεγχος του κόστους παράδοσης μέσω δικτύου, με ταυτόχρονη διατήρηση της υψηλής ποιότητας εμπειρίας των χρηστών, αποτελεί μια κρίσιμη πρόκληση για τους σύγχρονους παρόχους περιεχομένου. Ενώ οι παραδοσιακές προσεγγίσεις βελτιστοποιούν τα Δίκτυα Παράδοσης Περιεχομένου (CDNs) και τα Συστήματα Συστάσεων (RS) ανεξάρτητα, πρόσφατες έρευνες προτείνουν την ανατροπή του προβλήματος, αξιοποιώντας το σύστημα συστάσεων για να «ωθήσει» τους χρήστες προς περιεχόμενο που βρίσκεται ήδη στην τοπική μνήμη. Αυτό το παράδειγμα, γνωστό ως Φιλικές προς το Δίκτυο Συστάσεις, μοντελοποιείται ως μια ακολουθιακή Διαδικασία Απόφασης Markov (MDP), σχεδιασμένη να ελαχιστοποιεί το μακροπρόθεσμο κόστος δρομολόγησης, διατηρώντας παράλληλα αυστηρά την Ποιότητα της Σύστασης (QoR).
Ο πρωταρχικός στόχος αυτής της διπλωματικής εργασίας είναι η διερεύνηση τόσο ακριβών όσο και προσεγγιστικών  μεθόδων Ενισχυτικής Μάθησης, προκειμένου να αυξηθεί η δυνατότητα εφαρμογής αυτής της μεθοδολογίας σε μεγαλύτερα, εν δυνάμει άγνωστα σενάρια. Για να επιτευχθεί αυτό, η πρώτη μας συνεισφορά είναι η διατύπωση ενός αλγορίθμου Tabular Q-learning, ο οποίος εξισώνεται επιτυχώς με την απόδοση των ακριβών αλγορίθμων βάσης «(oracle), δηλαδή των Value Iteration και Policy Iteration, σε σενάρια μικρού έως μεσαίου μεγέθους. Ωστόσο, επειδή ο διαρκώς αυξανόμενος χώρος καταστάσεων-ενεργειών καθιστά τις tabular μεθόδους μη εφαρμόσιμες για μεγαλύτερους καταλόγους, η δεύτερη συνεισφορά μας εισάγει προσεγγιστικές λύσεις Βαθιάς Ενισχυτικής Μάθησης (Deep RL) βασισμένες σε Βαθιά Δίκτυα Q (DQNs). Και συνδυάζοντας τα DQNs με δομικές ενσωματώσεις γράφων, αντιμετωπίζουμε επιτυχώς τον αυξανόμενο χώρο καταστάσεων και βελτιώνουμε δραστικά τη γενίκευση των συστάσεων.
Τέλος, αν και το τυπικό DQN ξεπερνά αυτή την πολυπλοκότητα,  δυσκολεύεται να αναπτύξει επίγνωση του δικτύου. Ως τρίτη συνεισφορά, προτείνουμε μια νέα αρχιτεκτονική Graph Q-Network (GQN), η οποία αξιοποιεί τις ιδιότητες των γράφων μεταξύ σχετικού περιεχομένου, προκειμένου να πραγματοποιεί έξυπνες συστάσεις αξιοποιώντας graph convolutional layers. Και με αξιολογήσεις σε αραιά  σύνολα δεδομένων αποδεικνύουμε ότι το πλαίσιο GQN μπορεί να φτάσει την απόδοση των βελτιστοποιημένων αλγορίθμων βάσης μας, επιτυγχάνοντας παράλληλα ταχύτερη σύγκλιση. Εν κατακλείδι, αυτή η διπλωματική εργασία καταδεικνύει πώς μπορούμε να προχωρήσουμε προοδευτικά από τις ακριβείς tabular μεθόδους σε προσεγγιστικές, βαθιές αρχιτεκτονικές γράφων και να μετασχηματίσουμε επιτυχώς την  κλίμακα των NFR.

Abstract 
Controlling network delivery costs while maintaining high-quality user experiences is a critical challenge for modern content providers (CP). While traditional approaches optimize Content Delivery Networks (CDNs) and Recommendation Systems (RS) independently, recent work has proposed turning the problem on its head by leveraging the RS to seamlessly ``nudge'' users toward locally cached content. This paradigm, known as Network-Friendly Recommendations (NFR), is modeled as a sequential Markov Decision Process (MDP) designed to minimize long-term routing costs while strictly preserving the Quality of Recommendation (QoR). 
The primary goal of this thesis is to investigate both exact and approximate Reinforcement Learning (RL) methods to increase the applicability of this methodology to larger, potentially unknown scenarios. To achieve this, our contributions are ,firstly, to formulate a Tabular Q-learning algorithm that successfully matches the performance of the exact ``oracle'' Value Iteration and Policy Iteration baselines in small-to-medium sized scenarios. However, because the expanding state-action space makes tabular methods infeasible for larger catalogs, our second contribution introduces approximate Deep RL solutions based on Deep Q-Networks (DQNs) and by pairing DQNs with structural graph embeddings, we successfully deal with the increasing state space and drastically improve the generalization of the method.
Finally, while the standard DQN overcomes the sample complexity, it also struggles to navigate through the network-awareness . As our third contribution, we propose a novel Graph Q-Network (GQN) architecture that leverages the MDP graphs properties between related contents to make intelligent recommendations by utilizing graph convolutional layers. The evaluations on sparse, real-world datasets demonstrateσ that the GQN framework can effortlessly match our optimized baseline algorithms while achieving faster convergence. Ultimately, this thesis demonstrates how we can progressively advance from exact tabular methods to approximate deep graph architectures and successfully transform NFR's scale.