Introduction to the Analysis of Probabilistic Decision-Making Algorithms

• URL: http://arxiv.org/abs/2508.21620v1
• Date: Fri, 29 Aug 2025 13:33:23 GMT
• Title: Introduction to the Analysis of Probabilistic Decision-Making Algorithms
• Authors: Agustinus Kristiadi,
• Abstract summary: Decision theories offer principled methods for making choices under various types of uncertainty.<n>They have been successfully applied to a wide range of real-world problems, including materials and drug discovery.<n>In scientific discovery, where experiments are costly, these algorithms can thus significantly reduce the cost of experimentation.
• Score: 6.293550968275451
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Position: We Need An Algorithmic Understanding of Generative AI [7.425924654036041]
  This position paper proposes AlgEval: a framework for systematic research into the algorithms that LLMs learn and use.<n>AlgEval aims to uncover algorithmic primitives, reflected in latent representations, attention, and inference-time compute, and their algorithmic composition to solve task-specific problems.
  arXiv  Detail & Related papers  (2025-07-10T08:38:47Z)
• Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection [25.29451529910051]
  We propose the first provable guarantee for algorithm selection based on algorithm features. We analyze the benefits and costs associated with algorithm features and investigate how the generalization error is affected by different factors.
  arXiv  Detail & Related papers  (2024-05-18T17:38:25Z)
• Globally-Optimal Greedy Experiment Selection for Active Sequential Estimation [1.1530723302736279]
  We study the problem of active sequential estimation, which involves adaptively selecting experiments for sequentially collected data. The goal is to design experiment selection rules for more accurate model estimation. We propose a class of greedy experiment selection methods and provide statistical analysis for the maximum likelihood.
  arXiv  Detail & Related papers  (2024-02-13T17:09:29Z)
• Multivariate Systemic Risk Measures and Computation by Deep Learning Algorithms [63.03966552670014]
  We discuss the key related theoretical aspects, with a particular focus on the fairness properties of primal optima and associated risk allocations. The algorithms we provide allow for learning primals, optima for the dual representation and corresponding fair risk allocations.
  arXiv  Detail & Related papers  (2023-02-02T22:16:49Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Performance Analysis of Fractional Learning Algorithms [32.21539962359158]
  It is unclear whether the proclaimed superiority over conventional algorithms is well-grounded or is a myth as their performance has never been extensively analyzed. In this article, a rigorous analysis of fractional variants of the least mean squares and steepest descent algorithms is performed. Their origins and consequences on the performance of the learning algorithms are discussed and swift ready-witted remedies are proposed.
  arXiv  Detail & Related papers  (2021-10-11T12:06:44Z)
• Information-theoretic generalization bounds for black-box learning algorithms [46.44597430985965]
  We derive information-theoretic generalization bounds for supervised learning algorithms based on the information contained in predictions rather than in the output of the training algorithm. We show experimentally that the proposed bounds closely follow the generalization gap in practical scenarios for deep learning.
  arXiv  Detail & Related papers  (2021-10-04T17:28:41Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Nonparametric Estimation of Heterogeneous Treatment Effects: From Theory to Learning Algorithms [91.3755431537592]
  We analyze four broad meta-learning strategies which rely on plug-in estimation and pseudo-outcome regression. We highlight how this theoretical reasoning can be used to guide principled algorithm design and translate our analyses into practice.
  arXiv  Detail & Related papers  (2021-01-26T17:11:40Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.