Roboticists have long envisioned fully-automated robots that can operate reliably in unstructured environments. This is an exciting but extremely difficult problem; in order to succeed, robots must reason about sequential decisions and their consequences in face of uncertainty. As a result, in practice, the engineering effort required to build reliable robotic systems is both demanding and expensive. This research aims to provide a set of techniques for efficient and principled robot learning. We approach this challenge from a theoretical perspective that more closely integrates analysis and practical needs. These theoretical principles are applied to design better algorithms in two important aspects of robot learning: policy optimization and development of structural policies. This research uses and extends online learning, optimization, and control theory, and is demonstrated in applications including reinforcement learning, imitation learning, and structural policy fusion. A shared feature across this research is the reciprocal interaction between the development of practical algorithms and the advancement of abstract analyses. Real-world challenges force the rethinking of proper theoretical formulations, which in turn lead to refined analyses and new algorithms that can rigorously leverage these insights to achieve better performance. Advisors/Committee Members: Boots, Byron (advisor), Gordon, Geoff (committee member), Hutchinson, Seth (committee member), Liu, Karen (committee member), Theodorou, Evangelos A. (committee member).