ABSTRACT OF THE DISSERTATION STOCHASTIC DILEMMAS: FOUNDATIONS AND APPLICATIONS

One of the significant challenges when solving optimization problems is ad-dressing possible inaccurate or inconsistent function evaluations. Surprisingly and interestingly, this problem is far from trivial even in one of the most ba-sic possible settings: evaluating which of two options is better when the val-ues of the two options are random variables (a stochastic dilemma). Problems in this space have often been studied in the statistics, operations research and computer-science communities under the name of ”multi-armed bandits”. While most of the previous work has focused on dealing with noise in an online set-ting, in this dissertation, I will focus on offline optimization where the goal is to return a reasonable solution with high probability using a finite number of samples. I will discuss a set of problem settings of increasing complexity that allow one to derive formal algorithmic bounds. I will point to and dis-cuss interesting connections between stochastic optimization and noisy data ii annotation, a problem where the goal is to identify the label of an object from a series of noisy evaluations. As a first contribution, I will introduce and formally analyze a set of novel algorithms that improve the state of the art and provide new insights for solv-ing the stochastic optimization and noisy data-annotation problems. I will then formally prove a novel result: That a widely used derivative-free optimization algorithm (the cross-entropy method) is optimizing for quantiles instead of expectation in stochastic optimization settings. I will back up the theoretical claims on the optimization side with experimental results in a set of non-trivial planning and reinforcement-learning domains. Finally, I will discuss the ap-plication of the above algorithms for solving noisy data-annotation problems in a setting involving real crowdsourcing experiments. ii