Imaginons que nous ayons accès à un simulateur qui modélise le comportement d’une tâche numérique complexe. Considéré comme une boîte noire, nous ne pouvons obtenir des informations utiles qu’en exécutant le simulateur avec différentes entrées. Par exemple, le processus d’inférence de la structure 3D d’une protéine à partir de sa séquence d’acides aminés peut être considéré comme une tâche complexe, qui peut être modélisée par un simulateur. Les entrées du simulateur sont les séquences d’acides aminés et les sorties sont les structures 3D prédites. Une famille populaire de méthodes cherche à optimiser une fonction énergétique appropriée - produite par le simulateur - qui décrit la relation entre la structure d’une protéine et sa séquence d’acides aminés. Ces méthodes sont intéressantes car elles sont capables de construire des structures de protéines sans connaissance préalable des structures résolues.Dans cette thèse, nous modélisons des scénarios précédents comme un problème d’optimisation séquentielle dans des environnements stochastiques. A chaque instant, nous pouvons interroger un point de l’environnement, et recevoir une récompense bruitée. Nous nous concentrons d’abord sur le cas où l’environnement est représenté par un nombre fini de points, et ensuite sur le cas plus général où l’environnement est composé d’un nombre infini dénombrable de points, voire continu. Dans les deux cas, le coût d’une requête pouvant être élevée, nous envisageons ainsi à repérer au plus vite le point (quasi)-optimal. Cette étude est motivée par de nombreux scénarios réels comme, entre autres, les essais cliniques, les tests A/B, ou l’optimisation des placements publicitaires. Ainsi pour terminer, nous nous intéressons en particulier à l’une de ces applications plus importantes pour la communauté d’apprentissage statistique, c’est-à-dire l’optimisation des hyper-paramètres.