Online learning algorithms with time-varying partial feedback.

Abstract

Προτείνουμε ένα μοντέλο μάθησης με ανατροφοδότηση τύπου bandit που λαμβάνει υπόψη μη παρατηρήσιμες καταστάσεις οι οποίες εξελίσσονται ντετερμινιστικά. Το μοντέλο αυτό το ονομάζουμε Bandits with Deter- ministically Evolving States (B-DES). Οι βασικές εφαρμογές του μοντέλου μας αφορούν τη μάθηση σε συστήματα προτιμήσεων και τη μάθηση για προσωποποιημένες διαφημίσεις. Και στις δύο περιπτώσεις, η ανταμοιβή που λαμβάνει ο αλγόριθμος σε κάθε γύρο είναι συνάρτηση της βραχυπρόθεσμης ανταμοιβής της επιλεγμένης ενέργειας και του πόσο≪υγιές≫ είναι το σύστημα (δηλαδή, όπως μετράται από την κατάσ- τασή του). Για παράδειγμα, στα συστήματα συστάσεων, η ανταμοιβή που αποκομίζει η πλατφόρμα από την αλληλεπίδραση ενός χρήστη με έναν συγκεκριμένο τύπο περιεχομένου εξαρτάται όχι μόνο από τα εγγενή χαρακτηριστικά του ίδιου του περιεχομένου, αλλά και από το πώς έχουν εξελιχθεί οι προτιμήσεις του χρήστη ως αποτέλεσμα της αλληλεπίδρασής του με άλλους τύπους περιεχομένου στην πλατφόρμα. Το γενικό μας μοντέλο λαμβάνει υπόψη τον διαφορετικό ρυθμό λ ∈[0,1] με τον οποίο εξελίσσεται η κατάσταση (π.χ., πόσο γρήγορα μεταβάλλονται οι προτιμήσεις ενός χρήστη ως αποτέλεσμα της προηγούμενης κατανάλωσης περιεχομένου) και περιλαμβάνει ως ειδική περίπτωση τα κλασικά multi-armed bandits. Στόχος του αλ- γορίθμου είναι η ελαχιστοποίηση μιας έννοιας regret ως προς την καλύτερη σταθερή ακολουθία επιλογών, κάτι που είναι σημαντικά δυσκολότερο σε σύγκριση με το καθιερωμένο κριτήριο της καλύτερης σταθερής ενέργειας εκ των υστέρων. Παρουσιάζουμε αλγορίθμους διαδικτυακής μάθησης για κάθε δυνατή τιμή του ρυθμού εξέλιξης λ.