The field of reinforcement learning has made enormous progress in the last few years, largely due to deep neural networks. Despite success on many practical problems, our reinforcement learning algorithms require huge amount of data. In many applications such as healthcare, data of this large scale is simply not available. In this talk, I explore novel approaches from stochastic optimization that open up opportunities for designing sample-efficient reinforcement learning algorithms. First, I will show how state features, which might come from machine learning algorithms or expert domain knowledge, can facilitate the design of data-efficient reinforcement learning algorithms. Next, I will show that reinforcement learning problems are easier to solve compared to Markov decision processes with full knowledge due to the powerful sampling mechanism in reinforcement learning.