Chapter 1: Discovery As Search | Building Discovery AI

Overview

Every act of discovery, from identifying a new chemical compound to finding a bug in a million-line codebase, can be understood as search. This chapter formalizes that intuition. We define discovery as navigation through a space of states $S$ guided by actions $A$, a transition function $T$, an objective $f$, and constraints $C$. We derive the fundamental trade-off between exploration (gathering information) and exploitation (using what we know), quantify it through regret bounds and information gain, and build a working simulator that lets you watch four different search strategies compete on a synthetic discovery landscape.

By the end of this chapter, you will have both the mathematical vocabulary to reason about discovery as a formal process and the Python code to experiment with it. These foundations surface repeatedly throughout the book: search becomes reasoning in Chapter 4, optimization in Chapter 45, and automated experiment design in Chapter 46.

Prerequisites

This is the first chapter of the book. No prior chapters are required. We assume familiarity with Python programming (functions, classes, NumPy basics), undergraduate probability (expectation, variance, Bayes' theorem), and comfort reading mathematical notation. If you need a refresher, Appendix A: Mathematical Foundations and Appendix B: Python for Discovery AI cover everything you need.

Learning Outcomes

Formalize discovery as search over a state space with actions, transitions, objectives, and constraints.
Distinguish discovery, invention, and innovation, and map each to its search structure.
Quantify the exploration/exploitation trade-off using regret, information gain, and entropy reduction.
Derive Upper Confidence Bound (UCB) from first principles and connect it to Thompson Sampling.
Model discovery workflows as state transition systems and identify where AI accelerates each step.
Build a working discovery simulator in Python that compares random search, greedy search, UCB, and Thompson Sampling.

Sections

1.1 Discovery, Invention, and Innovation

Discovery, invention, and innovation as human activities. Search spaces, solution spaces, and objective functions. The formal tuple $(S, A, T, f, C)$ that structures every discovery problem.

1.2 Exploration Versus Exploitation

Utility, regret, information gain, and uncertainty. The multi-armed bandit as the simplest discovery model. UCB derivation and Thompson Sampling.

1.3 Discovery Workflows

Discovery workflows as state transition systems. Sequential, iterative, and branching workflows. The role of AI in accelerating search at each stage.

1.4 Building a Discovery Simulator

Recipe: build a discovery simulator comparing random search, greedy search, UCB, and Thompson Sampling on a synthetic multi-modal objective landscape.

What's Next

With discovery formalized as search, Chapter 2: Scientific Discovery and Knowledge Creation narrows the lens to scientific discovery specifically: hypothesis generation, experimental design, and the epistemological foundations that distinguish scientific knowledge from other forms of search outcomes. The search framework you built here becomes the skeleton on which scientific methodology hangs.

Bibliography

Foundational Papers

Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2), 235-256.

The paper that introduced the UCB1 algorithm and proved its logarithmic regret bound, establishing the modern theory of multi-armed bandits.

Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4), 285-294.

The original Thompson Sampling paper, rediscovered decades later as one of the most effective bandit algorithms in practice.

Langley, P., Simon, H. A., Bradshaw, G. L., & Zytkow, J. M. (1987). Scientific Discovery: Computational Explorations of the Creative Processes. MIT Press.

A landmark book framing scientific discovery as heuristic search, introducing the BACON and GLAUBER programs.

Merchant, A., et al. (2023). Scaling deep learning for materials discovery. Nature, 624, 80-85.

DeepMind's GNoME system that discovered 2.2 million new crystal structures, a dramatic example of AI-accelerated search in materials science.

Books

Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.

The definitive modern reference on bandit algorithms, covering UCB, Thompson Sampling, and contextual bandits with full proofs.

Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach, 4th edition. Pearson.

The standard AI textbook, whose treatment of search algorithms (Chapters 3-5) provides essential background for this chapter.

Tools & Libraries

NumPy

The foundation of numerical computing in Python. Every code example in this chapter uses NumPy for array operations and random number generation.

NetworkX

A Python library for creating and analyzing graphs and networks, used in this chapter to model state transition graphs in discovery workflows.

Matplotlib

The plotting library used throughout this chapter to visualize search trajectories, regret curves, and discovery landscapes.

Tutorials & Surveys

Slivkins, A. (2019). Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2), 1-286.

An accessible survey of bandit algorithms that bridges theory and practice, excellent supplementary reading for Section 1.2.

Wang, H., et al. (2023). Scientific discovery in the age of artificial intelligence. Nature, 620, 47-60.

A comprehensive review of AI for scientific discovery, providing context for how the search framework connects to real scientific applications.