Exploration in Reinforcement Learning : Beyond Finite State-Spaces

L'apprentissage par renforcement (reinforcement learning, RL) est un paradigme de l'apprentissage automatique qui nous permet de concevoir des algorithmes qui apprennent à prendre des décisions et à interagir avec le monde. Les algorithmes de RL peuvent être classés comme hors ligne ou en ligne. Dans le cas hors ligne, l'algorithme dispose d'un ensemble de données fixe, avec lequel il doit calculer une bonne stratégie de prise de décision. Dans le cas en ligne, l'agent doit collecter efficacement des données par lui-même, en interagissant avec l'environnement : c'est le problème que l'on appelle exploration en apprentissage par renforcement. Cette thèse présente des contributions théoriques et pratiques sur le RL en ligne. Nous étudions la performance dans le pire des cas des algorithmes de RL dans des environnements finis, c'est-à-dire, ceux qui peuvent être modélisés avec un nombre fini d'états, et où l'ensemble des actions qui peuvent être prises par un agent est aussi fini. Cette performance se dégrade à mesure que le nombre d'états augmente, alors qu'en pratique, l'espace d'états peut être arbitrairement grand ou continu. Pour résoudre ce problème, nous proposons des algorithmes à noyaux qui peuvent être implémentés pour des espaces d'états généraux, et pour lesquels nous proposons des résultats théoriques sous des hypothèses faibles sur l'environnement. Ces algorithmes reposent sur une fonction noyau qui mesure la similarité entre différents états, qui peut être définie sur des espaces d'état arbitraires, y compris des ensembles discrets et des espaces euclidiens, par exemple. De plus, nous montrons que nos algorithmes à noyaux sont capables d'apprendre dans des environnements non stationnaires en utilisant des fonctions noyau dépendantes du temps, et nous proposons et analysons des versions approximatives de nos méthodes pour réduire leur complexité de calcul. Finalement, nous introduisons une autre approximation de nos méthodes à noyaux, qui peut être implémentée avec des algorithmes d'apprentissage par renforcement profond et intégrer de différentes méthodes d'apprentissage de représentation pour définir un noyau.Reinforcement learning (RL) is a powerful machine learning framework to design algorithms that learn to make decisions and to interact with the world. Algorithms for RL can be classified as offline or online. In the offline case, the algorithm is given a fixed dataset, based on which it needs to compute a good decision-making strategy. In the online case, an agent needs to efficiently collect data by itself, by interacting with the environment: that is the problem of exploration in reinforcement learning. This thesis presents theoretical and practical contributions to online RL. We investigate the worst-case performance of online RL algorithms in finite environments, that is, those that can be modeled with a finite amount of states, and where the set of actions that can be taken by an agent is also finite. Such performance degrades as the number of states increases, whereas in real-world applications the state set can be arbitrarily large or continuous. To tackle this issue, we propose kernel-based algorithms for exploration that can be implemented for general state spaces, and for which we provide theoretical results under weak assumptions on the environment. Those algorithms rely on a kernel function that measures the similarity between different states, which can be defined on arbitrary state-spaces, including discrete sets and Euclidean spaces, for instance. Additionally, we show that our kernel-based algorithms are able to handle non-stationary environments by using time-dependent kernel functions, and we propose and analyze approximate versions of our methods to reduce their computational complexity. Finally, we introduce a scalable approximation of our kernel-based methods, that can be implemented with deep reinforcement learning and integrate different representation learning methods to define a kernel function