Introduction to the Analysis of Probabilistic Decision-Making Algorithms
This work addresses the need for non-experts in fields like scientific discovery to understand algorithm behavior, but it is incremental as it focuses on educational synthesis rather than new research.
The monograph tackles the problem of inaccessible theoretical analyses of probabilistic decision-making algorithms by providing an accessible introduction to their analysis, covering algorithms like bandit algorithms and Bayesian optimization, with no specific numerical results reported.
Decision theories offer principled methods for making choices under various types of uncertainty. Algorithms that implement these theories have been successfully applied to a wide range of real-world problems, including materials and drug discovery. Indeed, they are desirable since they can adaptively gather information to make better decisions in the future, resulting in data-efficient workflows. In scientific discovery, where experiments are costly, these algorithms can thus significantly reduce the cost of experimentation. Theoretical analyses of these algorithms are crucial for understanding their behavior and providing valuable insights for developing next-generation algorithms. However, theoretical analyses in the literature are often inaccessible to non-experts. This monograph aims to provide an accessible, self-contained introduction to the theoretical analysis of commonly used probabilistic decision-making algorithms, including bandit algorithms, Bayesian optimization, and tree search algorithms. Only basic knowledge of probability theory and statistics, along with some elementary knowledge about Gaussian processes, is assumed.