While deep reinforcement learning achieves tremendous successes in practice, its efficiencies are rarely understood in theory. The dissertation contains three parts, with each part corresponding to the study of an independent theoretical reinforcement learning problem. The three parts in all discuss the mechanism of how (deep) reinforcement learning efficiently solves...