Empirical research in reinforcement learning has achieved impressive results over the past few years. However, many questions remain open regarding the theoretical guarantees of the algorithms used in practice. The PhD project aims to gain a deeper understanding of the challenges posed by large-scale reinforcement learning by identifying and exploiting structural properties of Markov decision processes that make large-scale learning statistically and computationally feasible. In particular, we aim to develop efficient and theoretically grounded reinforcement learning algorithms from the linear programming formulation of optimal control in Markov decision processes, which has been one of the most promising research directions explored in the past few years.