Cette thèse traite des domaines suivant en Apprentissage Automatique: la théorie des Bandits, l'Apprentissage statistique et l'Apprentissage par renforcement. Son fil rouge est l'étude de plusieurs notions d'adaptation, d'un point de vue non asymptotique : à un environnement ou à un adversaire dans la partie I, à la structure d'un signal dans la partie II, à la structure de récompenses ou à un modèle des états du monde dans la partie III. Tout d'abord nous dérivons une analyse non asymptotique d'un algorithme de bandit à plusieurs bras utilisant la divergence de Kullback-Leibler. Celle-ci permet d'atteindre, dans le cas de distributions à support fini, la borne inférieure de performance asymptotique dépendante des distributions de probabilité connue pour ce problème. Puis, pour un bandit avec un adversaire possiblement adaptatif, nous introduisons des modèles dépendants de l'histoire et traduisant une possible faiblesse de l'adversaire et montrons comment en tirer parti pour concevoir des algorithmes adaptatifs à cette faiblesse. Nous contribuons au problème de la régression en montrant l'utilité des projections aléatoires, à la fois sur le plan théorique et pratique, lorsque l'espace d'hypothèses considéré est de dimension grande, voire infinie. Nous utilisons également des opérateurs d'échantillonnage aléatoires dans le cadre de la reconstruction parcimonieuse lorsque la base est loin d'être orthogonale. Enfin, nous combinons la partie I et II : pour fournir une analyse non-asymptotique d'algorithmes d'apprentissage par renforcement; puis, en amont du cadre des Processus Décisionnel de Markov, pour discuter du problème pratique du choix d'un bon modèle d'états.

La surveillance de phénomènes physiques à l’aide d’un réseau de capteurs (autonomes mais communicants) est fortement contrainte en consommation énergétique, principalement pour la transmission de données. Dans ce cadre, cette thèse propose des méthodes de traitement du signal permettant de réduire les communications sans compromettre la précision des calculs ultérieurs. La complexité de ces méthodes est réduite, de façon à ne consommer que peu d’énergie supplémentaire. Deux éléments servent à leur synthèse : la compression dès l’acquisition (Acquisition compressive) et la quantification grossière (sur 1 bit). D’abord, on étudie le corrélateur compressé, un estimateur qui permet d’évaluer les fonctions de corrélation, temps de retard et densités spectrales en exploitant directement des signaux compressés. Ses performances sont comparées au corrélateur usuel. Si le signal à traiter possède un support spectral étroit, l’estimateur proposé s’avère sensiblement meilleur que l’usuel. Ensuite, inspirés par les corrélateurs à forte quantification des années 50 et 60, deux nouveaux corrélateurs sont étudiés : le compressé sur 1 bit et le compressé hybride, qui peuvent également surpasser les performances de leurs contreparties non-compressées. Finalement, on montre la pertinence de ces méthodes pour les applications envisagées à travers l’exploitation de données réelles. / Monitoring physical phenomena by using a network of sensors (autonomous but interconnected) is highly constrained in energy consumption, mainly for data transmission. In this context, this thesis proposes signal processing tools to reduce communications without compromising computational accuracy in subsequent calculations. The complexity of these methods is reduced, so as to consume only little additional energy. Our two building blocks are compression during signal acquisition (Compressive Sensing) and CoarseQuantization (1 bit). We first study the Compressed Correlator, an estimator which allows for evaluating correlation functions, time-delay, and spectral densities directly from compressed signals. Its performance is compared with the usual correlator. As we show, if the signal of interest has limited frequency content, the proposed estimator significantly outperforms theconventional correlator. Then, inspired by the coarse quantization correlators from the 50s and 60s, two new correlators are studied: The 1-bit Compressed and the Hybrid Compressed, which can also outperform their uncompressed counterparts. Finally, we show the applicability of these methods in the context of interest through the exploitation of real data.