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 noeuds 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 noeuds. 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.