Contributions to stochastic bandits and link prediction problems ; Contributions aux problèmes de bandits stochastiques et de prévision de liens manquants
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
Electronic Thesis;
E-Book
Title:
Contributions to stochastic bandits and link prediction problems ; Contributions aux problèmes de bandits stochastiques et de prévision de liens manquants
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Dans cette thèse, nous nous intéressons dans un premier temps à deux problèmes de bandits stochastiques. Le premier problème étudié modélise la situation d'allocation de ressources suivantes : un agent doit choisir séquentiellement T actions indexées par des covariables parmi un ensemble plus grand de N choix. Chaque fois qu'il choisit une action, il reçoit un paiement dépendant de façon non paramétrique de l'action choisie.; puis cette action est retirée de l'ensemble des choix. Dans le second problème, on suppose que le paiement reçu est une fonction linéaire d'une covariable décrivant l'action choisie, mais que celui-ci n'est pas observé par l'agent ; à la place, celui-ci observe une évaluation injuste de ce paiement, systématiquement biaisée à l'encontre d'un groupe d'actions. Nous proposons pour chaque problème un algorithme dont nous bornons le regret. Nous établissons également des bornes inférieures sur le regret, montrant que ces algorithmes sont optimaux à un facteur (poly)logarithmique près. Dans un second temps, nous abordons le problème de prévision de lien manquant dans un réseau partiellement observé. Pour ce faire, nous étudions différentes méthodes pour estimer la matrice de probabilités de connexion entre les nœuds du réseau. Nous développons tout d'abord un algorithme de descente de gradient mixte par coordonnées pour estimer robustement et efficacement les probabilités de connexion dans un réseau creux en présence de liens manquants et d'intrus. Ensuite, nous étudions l'estimateur du maximum de vraisemblance dans le modèle à blocs stochastiques, et nous montrons que celui-ci est optimal au sens minimax sous une hypothèse d'homogénéité sur les probabilités de connexion des nœuds. Cet estimateur n'étant pas calculable en temps polynomial, on étudie également son approximation variationnelle, et nous montrons que ces deux derniers estimateurs sont asymptotiquement équivalents. ; In this thesis, we first focus on two stochastic bandit problems. The first problem deals with the following resource ...