On optimal Sampling in low and high dimension

During my PhD, I had the chance to learn and work under the great supervision of my advisor R emi (Munos) in two elds that are of particular interest to me. These domains are Bandit Theory and Compressed Sensing. While studying these domains I came to the conclusion that they are connected if one looks at them trough the prism of optimal sampling. Both these elds are concerned with strategies on how to sample the space in an e cient way: Bandit Theory in low dimension, and Compressed Sensing in high dimension. In this Dissertation, I present most of the work my co-authors and I produced during the three years that my PhD lasted.