Dans cette thèse, nous nous interrogeons sur la vitesse à laquelle on peut résoudre un problème stochastique inconnu. À cette fin, nous introduisons deux domaines de recherche connus sous le nom de Bandit et d’Apprentissage par Renforcement. Dans ces deux champs d’étude, un agent doit séquentiellement prendre des décisions qui affecteront un signal de récompense qu’il reçoit. L’agent ne connaît pas l’environnement avec lequel il interagit, mais pourtant souhaite maximiser sa récompense moyenne à long terme. Plus précisément, on étudie des problèmes de décision stochastique dans lesquels l’agent cherche à maximiser sa récompense moyenne. Dans ces problèmes dit d’apprentissage stochastique, l’agent interagit séquentiellement avec un système dynamique, sans aucune réinitialisation, dans une suite unique, infinie et ininterrompue d’observations, d’actions et de récompenses tout en essayant de maximiser ses récompenses totales accumulées au fil du temps. Nous commençons par présenter le problème de Bandit, dans lequel l’ensemble des décisions est constant, et définissons ce que l’on entend par résoudre le problème. Parmi ces agents, certains sont meilleurs que tous les autres et sont dits optimaux. Nous nous concentrons d’abord sur la manière de tirer le maximum d’information de chaque interaction avec le système en revisitant un algorithme optimal et en réduisant sa complexité numérique. Tout en conservant l’optimalité de la méthode initiale, la méthode proposée réduit la complexité numérique et permet donc d’extraire d’avantage d’information d’un échantillon par unité de temps de calcul. Nous étudions ensuite un problème structuré intéressant dans lequel il est possible d’exploiter la structure sans l’estimer. Ensuite nous nous consacrons à l’Apprentissage par Renforcement, dans lequel les décisions qu’un agent peut prendre dépendent d’une notion d’état. Chaque fois qu’un agent prend une décision, il reçoit une récompense et l’état change selon une loi de transition sur les états. Sous une certaine hypothèse, dite ergodique, un taux optimal de résolution par unité d’interaction est connu et nous introduisons un algorithme dont nous pouvons prouver qu’il est optimal et nous montrons qu’il est numériquement efficace. Dans un dernier chapitre, nous tentons de mieux comprendre ce qu’implique la suppression de l’hypothèse d’ergodicité. Nous considérons le problème a priori plus simple où les transitions sont connues. Cependant, même sous cette hypothèse, il n’est pas évident de comprendre correctement la vitesse à laquelle des informations peuvent être acquises sur une solution optimale.