Efficient Learning & Decision Making in Environments with Structured Uncertainty

A prominent feature of modern machine learning is acting in environments with high degrees of uncertainty. Without enforcing structure on the environment or its type of uncertainty, efficiently making intelligent decisions is impossible. This thesis studies and formalizes structure under which machine learning systems can efficiently learn and make decisions that maximize our utility. It is split into two parts. The first part focuses on research that has identified the presence of such structure in a variety of sequential decision making problems, particularly in reinforcement learning and online learning settings. This structure is motivated by real world problems. We present formal theoretical results which guarantee that such structure permits efficient learning. Various notions of efficiency are considered, including both statistical and computational. The second part describes research on solving empirical risk minimization (ERM) problems, while being robust to uncertainty in the data. Under mild assumptions on the loss functions and uncertainty sets, we provide a framework via which a practitioner can specify and solve robust ERM problems. Notably, this can be done in just a few lines of code, in a manner that naturally follows the math.