Algorithme en ligne pour la sélection séquentielle non supervisée avec information contextuelle

Résumé

Dans cet article, nous étudions la sélection séquentielle contextuelle non supervisée (USS), une nouvelle variante du problème des bandits contextuels stochastiques où la perte d'un bras ne peut être déduite du feedback observé. Dans notre configuration, les bras sont associés à des coûts fixes et sont ordonnés, formant une cascade. A chaque tour, un contexte est présenté, et l'apprenant sélectionne les bras séquentiellement jusqu'à une certaine profondeur. Le coût total encouru en s'arrêtant à un bras est la somme des coûts fixes des bras sélectionnés et de la perte stochastique associée à ce bras. L'objectif de l'apprenant est d'apprendre une règle de décision qui associe les contextes aux bras dans le but de minimiser la perte totale attendue. Le problème est difficile car nous sommes confrontés à un cadre non supervisé et la perte totale ne peut être estimée. Il est clair que l'apprentissage n'est possible que si le bras optimal peut être déduit (explicitement ou implicitement) de la structure du problème. Nous observons que l'apprentissage est toujours possible lorsque l'instance du problème satisfait à la propriété dite de "faible dominance contextuelle" (CWD). Sous la propriété CWD, nous proposons un algorithme pour le problème USS contextuel et démontrons qu'il a un regret sub-linéaire. Des expériences sur des ensembles de données synthétiques et réelles valident notre algorithme.