Papers
The notes cite the original papers where their ideas arise. This index collects the principal ones by topic; the chapters give further references inline.
Search, constraint satisfaction, and games
| Work | Idea developed in the module |
|---|---|
| Hart, Nilsson, and Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths (1968) | A* and its optimality with admissible heuristics (chapter 2). |
| Dechter and Pearl, Generalized Best-First Search Strategies and the Optimality of A* (1985) | The sense in which A* is optimally efficient (chapter 2). |
| Korf, Depth-First Iterative-Deepening: An Optimal Admissible Tree Search (1985) | Iterative deepening and IDA* (chapters 1–2). |
| Culberson and Schaeffer, Pattern Databases (1998), and Felner, Korf, and Hanan, Additive Pattern Database Heuristics (2004) | Abstraction heuristics stored in tables, and when they can be added (chapter 2). |
| Likhachev, Gordon, and Thrun, ARA*: Anytime A* with Provable Bounds on Sub-Optimality (2003) | Weighted A* without reopening and anytime search (chapter 2). |
| Agostinelli, McAleer, Shmakov, and Baldi, Solving the Rubik’s Cube with Deep Reinforcement Learning and Search (2019) | A learned cost-to-go heuristic inside weighted A* (chapter 2). |
| Minton, Johnston, Philips, and Laird, Minimizing Conflicts: A Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems (1992) | The min-conflicts heuristic (chapter 3). |
| Kirkpatrick, Gelatt, and Vecchi, Optimization by Simulated Annealing (1983), and Hajek, Cooling Schedules for Optimal Annealing (1988) | Simulated annealing and its logarithmic schedule (chapter 3). |
| Cheeseman, Kanefsky, and Taylor, Where the Really Hard Problems Are (1991) | Hard instances cluster at phase transitions (chapters 3 and 5). |
| Knuth and Moore, An Analysis of Alpha-Beta Pruning (1975) | Correctness and the best case of alpha–beta (chapter 4). |
| Campbell, Hoane, and Hsu, Deep Blue (2002), and Schaeffer et al., Checkers Is Solved (2007) | Game-tree search at scale (chapter 4). |
| Auer, Cesa-Bianchi, and Fischer, Finite-Time Analysis of the Multiarmed Bandit Problem (2002), and Kocsis and Szepesvári, Bandit Based Monte-Carlo Planning (2006) | UCB1 and UCT (chapter 4). |
| Silver et al., Mastering the Game of Go with Deep Neural Networks and Tree Search (2016), and A General Reinforcement Learning Algorithm That Masters Chess, Shogi, and Go through Self-Play (2018) | AlphaGo and AlphaZero (chapter 4). |
| Brown and Sandholm, Superhuman AI for Heads-Up No-Limit Poker: Libratus Beats Top Professionals (2018), and Zinkevich et al., Regret Minimization in Games with Incomplete Information (2007) | Counterfactual regret minimization and imperfect-information games (chapters 4 and 15). |
Logic and planning
| Work | Idea developed in the module |
|---|---|
| Cook, The Complexity of Theorem-Proving Procedures (1971) | NP-completeness of satisfiability (chapter 5). |
| Davis, Logemann, and Loveland, A Machine Program for Theorem-Proving (1962) | The DPLL procedure (chapter 5). |
| Marques-Silva and Sakallah, GRASP: A Search Algorithm for Propositional Satisfiability (1999), and Moskewicz et al., Chaff: Engineering an Efficient SAT Solver (2001) | Conflict-driven clause learning, watched literals, and VSIDS (chapter 5). |
| Selman, Kautz, and Cohen, Noise Strategies for Improving Local Search (1994) | WalkSAT (chapter 5). |
| Mitchell, Selman, and Levesque, Hard and Easy Distributions of SAT Problems (1992), and Mézard, Parisi, and Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems (2002) | The random 3-SAT threshold (chapter 5). |
| Haken, The Intractability of Resolution (1985) | Exponential lower bounds for resolution proofs (chapter 5). |
| Robinson, A Machine-Oriented Logic Based on the Resolution Principle (1965) | Resolution with unification (chapter 6). |
| Church, A Note on the Entscheidungsproblem (1936), and Turing, On Computable Numbers (1936) | Undecidability of first-order validity (chapter 6). |
| McCarthy and Hayes, Some Philosophical Problems from the Standpoint of Artificial Intelligence (1969) | The situation calculus and the frame problem (chapters 5–7). |
| McCarthy, Circumscription (1980), and Reiter, A Logic for Default Reasoning (1980) | Nonmonotonic reasoning (chapter 6). |
| Fikes and Nilsson, STRIPS (1971), and Bylander, The Computational Complexity of Propositional STRIPS Planning (1994) | The STRIPS formalism and its PSPACE-completeness (chapter 7). |
| Blum and Furst, Fast Planning through Planning Graph Analysis (1997), and Kautz and Selman, Pushing the Envelope (1996) | Graphplan and planning as satisfiability (chapter 7). |
| Bonet and Geffner, Planning as Heuristic Search (2001), and Hoffmann and Nebel, The FF Planning System (2001) | Delete-relaxation heuristics and relaxed plans (chapter 7). |
| Richter and Westphal, The LAMA Planner (2010) | Landmarks in satisficing planning (chapter 7). |
| Nau et al., SHOP2: An HTN Planning System (2003) | Hierarchical task network planning (chapter 7). |
| Valmeekam et al., On the Planning Abilities of Large Language Models (2023) | What language models do and do not do on planning benchmarks (chapter 7). |
Graphical models and inference
| Work | Idea developed in the module |
|---|---|
| Pearl, Probabilistic Reasoning in Intelligent Systems (1988) | Bayesian networks, d-separation, and belief propagation (chapters 8–9). |
| Geiger, Verma, and Pearl, Identifying Independence in Bayesian Networks (1990), and Lauritzen et al., Independence Properties of Directed Markov Fields (1990) | Soundness and completeness of d-separation, and the moral-graph criterion (chapter 8). |
| Verma and Pearl, Equivalence and Synthesis of Causal Models (1990) | Markov equivalence: same skeleton and v-structures (chapters 8 and 13). |
| Lauritzen and Spiegelhalter, Local Computations with Probabilities on Graphical Structures (1988) | The junction tree algorithm and the Asia network (chapters 8–9). |
| Cooper, The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks (1990), and Dagum and Luby, Approximating Probabilistic Inference in Bayesian Belief Networks Is NP-Hard (1993) | Hardness of exact and approximate inference (chapter 9). |
| Kschischang, Frey, and Loeliger, Factor Graphs and the Sum-Product Algorithm (2001) | Message passing on factor graphs (chapters 8–9). |
| Darwiche, A Differential Approach to Inference in Bayesian Networks (2003) | Arithmetic circuits and knowledge compilation (chapter 9). |
| Metropolis et al., Equation of State Calculations by Fast Computing Machines (1953), and Hastings, Monte Carlo Sampling Methods Using Markov Chains and Their Applications (1970) | The Metropolis–Hastings algorithm (chapters 3 and 10). |
| Geman and Geman, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images (1984) | Gibbs sampling (chapter 10). |
| Neal, MCMC Using Hamiltonian Dynamics (2011) | Hamiltonian Monte Carlo (chapter 10). |
| Murphy, Weiss, and Jordan, Loopy Belief Propagation for Approximate Inference: An Empirical Study (1999), and Yedidia, Freeman, and Weiss, Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms (2005) | Loopy belief propagation and the Bethe free energy (chapter 10). |
| Blei, Kucukelbir, and McAuliffe, Variational Inference: A Review for Statisticians (2017) | Mean-field and stochastic variational inference (chapter 10). |
| Kalman, A New Approach to Linear Filtering and Prediction Problems (1960) | The Kalman filter (chapter 11). |
| Viterbi, Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm (1967), and Baum et al., A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains (1970) | Viterbi decoding and Baum–Welch learning (chapter 11). |
| Gordon, Salmond, and Smith, Novel Approach to Nonlinear/Non-Gaussian Bayesian State Estimation (1993) | The bootstrap particle filter (chapter 11). |
| Besag, Statistical Analysis of Non-Lattice Data (1975) | Pseudolikelihood (chapter 14). |
| Lafferty, McCallum, and Pereira, Conditional Random Fields (2001) | Conditional random fields for sequence labeling (chapters 8 and 14). |
| Chow and Liu, Approximating Discrete Probability Distributions with Dependence Trees (1968) | Optimal tree-structured models (chapter 14). |
Decisions, causality, and multiagent systems
| Work | Idea developed in the module |
|---|---|
| Howard, Information Value Theory (1966), and Howard and Matheson, Influence Diagrams (1984, reprinted 2005) | The value of information and decision networks (chapter 12). |
| Kahneman and Tversky, Prospect Theory (1979) | Systematic departures of human choice from expected utility (chapter 12). |
| Smith and Winkler, The Optimizer’s Curse (2006) | Post-decision disappointment from choosing by noisy estimates (chapter 12). |
| Rubin, Estimating Causal Effects of Treatments in Randomized and Nonrandomized Studies (1974) | Potential outcomes (chapter 13). |
| Pearl, Causal Diagrams for Empirical Research (1995), and Shpitser and Pearl, Identification of Joint Interventional Distributions (2006) | The do-calculus and its completeness (chapter 13). |
| Rosenbaum and Rubin, The Central Role of the Propensity Score (1983), and Robins, Rotnitzky, and Zhao, Estimation of Regression Coefficients When Some Regressors Are Not Always Observed (1994) | Propensity scores and doubly robust estimation (chapter 13). |
| Angrist, Imbens, and Rubin, Identification of Causal Effects Using Instrumental Variables (1996) | Instruments and the local average treatment effect (chapter 13). |
| Shimizu et al., A Linear Non-Gaussian Acyclic Model for Causal Discovery (2006), and Peters, Bühlmann, and Meinshausen, Causal Inference by Using Invariant Prediction (2016) | Identifiability beyond Markov equivalence and invariance across environments (chapter 13). |
| Schölkopf et al., Toward Causal Representation Learning (2021) | Causality and representation learning (chapter 13). |
| Nash, Equilibrium Points in n-Person Games (1950) | Existence of mixed equilibria (chapter 15). |
| Aumann, Subjectivity and Correlation in Randomized Strategies (1974) | Correlated equilibrium (chapter 15). |
| Daskalakis, Goldberg, and Papadimitriou, The Complexity of Computing a Nash Equilibrium (2009), and Chen, Deng, and Teng, Settling the Complexity of Computing Two-Player Nash Equilibria (2009) | PPAD-completeness of equilibrium computation (chapter 15). |
| Freund and Schapire, Adaptive Game Playing Using Multiplicative Weights (1999), and Hart and Mas-Colell, A Simple Adaptive Procedure Leading to Correlated Equilibrium (2000) | No-regret learning and convergence to equilibria (chapter 15). |
| Roughgarden and Tardos, How Bad Is Selfish Routing? (2002) | The price of anarchy (chapter 15). |
| Vickrey, Counterspeculation, Auctions, and Competitive Sealed Tenders (1961) | The second-price auction and truthful mechanisms (chapter 15). |